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 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 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 RESTAPI returns the path as a list of people:
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.