Requirements, estimates and the graph model

The problem

The primer's Design the data structures for a social network asks for one core feature: a user searches for someone and sees the shortest path to them through mutual friends. The service also needs high availability.

Assumptions (from the primer)

• Traffic is uneven: some searches are far more popular than others.
• Graph data won't fit on a single machine.
• Edges are unweighted.
• 100 million users, 50 friends each on average.
• 1 billion friend searches per month.
• Use traditional systems: no graph database such as Neo4j and no GraphQL, so the design itself has to handle the graph.

---

Back-of-the-envelope estimates

The primer counts each user's friend list, so a friendship appears once in each person's list. That is 5 billion list entries, or 2.5 billion distinct friendships. At 8 bytes per friend id, the lists take about 40 GB before indexes and replication.

using the primer's conversion of 400 requests per second ≈ 1 billion a month.

Real networks are much bigger and denser. Backstrom et al. measured Facebook's whole active network in 2011: about 721 million users and 69 billion friendship links. The average distance between two users was 4.74 hops, "the world is even smaller than we expected". So paths are short, but each hop multiplies the number of people reached.

---

Modeling the graph without a graph database

Store each person once, keyed by id, with a list of friend ids:

class Person(object):
    def __init__(self, id, name, friend_ids):
        self.id = id
        self.name = name
        self.friend_ids = friend_ids

The data is too big for one machine, so the primer shards people across Person Servers. A Lookup Service maps a person's id to the server that holds them.

Facebook's TAO (USENIX ATC 2013) is the industrial version of this idea: a graph served from sharded MySQL through a cache. It has two primitives:

• Objects are "typed nodes", each identified by "a 64-bit integer (id) that is unique across all objects".
• Associations are "typed directed edges between objects", identified by (id1, atype, id2), with a time and data fields. "At most one association of a given type can exist between any two objects."

A friendship is stored as two associations, one in each direction.

---

API

The primer's REST API returns the path as a list of people:

GET /api/v1/friend_search?person_id=1234

→ [ { "person_id": "100", "name": "foo", "link": "https://social.com/foo" },
    { "person_id": "53",  "name": "bar", "link": "https://social.com/bar" },
    { "person_id": "1234", "name": "baz", "link": "https://social.com/baz" } ]

For calls between internal services, the primer suggests RPC.