Lesson 13.1• 9 min read

Requirements, estimates and the graph model

The primer’s use case and estimates (5 billion friend-list entries, 400 searches per second), friend lists on sharded Person Servers, and TAO’s objects and associations.

What you will learn

  • State the social graph search's use case and assumptions as the primer does.
  • Estimate the size of the friend lists and the search rate.
  • Store a graph too big for one machine without a graph database.

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: every friendship counts as one step.
  • 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

100×106 users×50=5×109 friend relationships100 \times 10^6 \text{ users} \times 50 = 5 \times 10^9 \text{ friend relationships}

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.

1×109 searches per month≈400 per second on average1 \times 10^9 \text{ searches per month} \approx 400 \text{ per second on average}

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

Real social networks are much bigger and denser. Backstrom et al. measured the social network of all Facebook's active users 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, described in a 2013 paper, 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.

Users1× instanceWeb server (reverseproxy)2× instancesSearch API2× instancesUser Graph Service2× instancesLookup Service2× instancesPerson Servers(sharded)4× instancesUsers1× instanceWeb server (reverseproxy)2× instancesSearch API2× instancesUser Graph Service2× instancesLookup Service2× instancesPerson Servers(sharded)4× instances
Figure 1

The primer’s design: the User Graph Service finds each person’s server through the Lookup Service and fetches the person from it.

Follow one search. The web server passes it to the Search API, which hands it to the User Graph Service. For the searcher, and then for each person the search reaches, the User Graph Service asks the Lookup Service which Person Server holds that person, and fetches the person and their friend IDs from that server. People are sharded across the Person Servers because the graph does not fit on one machine; four are drawn, as the primer gives no count. The other servers are counted at the lab’s 1,000 requests a second each for the primer’s 400 searches a second, plus one spare, though each search makes many lookups and fetches, which the next lesson counts.

  • Users: 1 × Users
  • Web server (reverse proxy): 2 × Load balancer
  • Search API: 2 × App server
  • User Graph Service: 2 × App server
  • Lookup Service: 2 × App server
  • Person Servers (sharded): 4 × NoSQL store
  • Users sends requests to Web server (reverse proxy)
  • Web server (reverse proxy) sends requests to Search API
  • Search API sends requests to User Graph Service
  • User Graph Service sends requests to Lookup Service
  • User Graph Service sends requests to Person Servers (sharded)

Key takeaways

  • 100 million users with 50 friends each give 5 billion list entries (2.5 billion friendships), about 40 GB of friend IDs; 1 billion searches a month is about 400 a second.
  • Store each person once with a list of friend IDs, shard people across Person Servers, and find a person's server through a Lookup Service.
  • Facebook's TAO does the same at scale with objects and typed associations, a friendship being two associations, one each way.
Sources4