Classic design · Mid
Social graph: degrees of separation
Classic interview design. Key points: Database Sharding and Data Modeling Fundamentals.
Short answer
Classic interview design. Key points: Database Sharding and Data Modeling Fundamentals. In this exercise, the user looks up someone on a social network and the system shows the shortest path to that person. The service also needs high availability. Pinning this down is the requirements gathering of the problem.
01 · CONTEXT AND REQUIREMENTS
What the search needs to do
In this exercise, the user looks up someone on a social network and the system shows the shortest path to that person. The service also needs high availability. Pinning this down is the requirements gathering of the problem.
The qualitative assumptions already limit the solutions: traffic is not uniform, some searches are much more popular than others and others happen only once, the graph does not fit on one machine and the edges have no weight.
| Grandeza | Valor |
|---|---|
| Users | 100 million |
| Friends per user (average) | 50 |
| Friend searches per month | 1 billion |
| Friendships | 5 billion |
| Searches per second | 400 |
02 · THE PROBLEM
BFS fits on one machine, the graph does not
Without the constraint of millions of vertices and billions of edges, a general breadth-first search (BFS) would solve the shortest path, since the edges have no weight.
But the source states that it will not be possible to put all users on the same machine. The way out is the sharding of users among Person Servers, accessed through a Lookup Service that says where each person is. In the source, each person has an identifier, a name and the list of friend ids, the data model of the exercise.
03 · INITIAL DESIGN
From click to shortest path
The flow crosses several layers before reaching the search. Follow the path of a request.
The client sends the request to the Web Server, which acts as a reverse proxy.
The request is forwarded from the Web Server to the Search API and from there to the User Graph Service.
The User Graph Service queries the Lookup Service to find the Person Server where the user's data lives.
The service reads the user's friend list from the appropriate Person Server.
The service runs the BFS starting from the current user.
For each neighbor to be read, the service needs to locate the correct Person Server again, something the source marks as an optimization opportunity.
04 · SCALING
Cache, precomputation and fewer hops
The source warns against jumping straight to the final design. Among the additions, it proposes serving people data from a in-memory cache, such as Redis or Memcached, to reduce response time and traffic to downstream services. This would be useful for those who make several searches in a row and for highly connected people.
The source cites this latency comparison: reading 1 MB sequentially from memory takes about 250 microseconds, while SSD takes 4 times longer and disk 80 times longer.
People data can be served from the in-memory cache, reducing response time and traffic to downstream services.
The cache can also hold complete or partial BFS traversals to speed up subsequent searches.
An offline batch computation produces complete or partial traversals and stores them in a NoSQL database to speed up subsequent searches.
Batching friend queries hosted on the same Person Server reduces hops between machines.
Partitioning Person Servers by location improves this, since friends tend to live near one another.
05 · SEARCH OPTIMIZATIONS
Less work per search
Beyond infrastructure, there are optimizations in the search itself, summarized below.
| Optimization | What the source describes |
|---|---|
| Bidirectional search | Two BFS runs at the same time, one from the source and one from the target, with the paths joined at the end |
| Start with people who have many friends | These people tend to reduce the degrees of separation to the target |
| Time or hop limit | Before asking whether the user wants to continue, since the search may take a while |
| Graph database | Only if there were no constraint prohibiting it |
Frequently asked questions
What is Social graph: degrees of separation?
Classic interview design. Key points: Database Sharding and Data Modeling Fundamentals.
What does the Social graph: degrees of separation design cover?
It is organized in these sections: What the search needs to do, BFS fits on one machine, the graph does not, From click to shortest path, Cache, precomputation and fewer hops, and Less work per search.
How long is Social graph: degrees of separation and what level is it?
It takes about 14 minutes to read and is rated Mid level.
Now design it yourself
Run this case as an interview in the System Design school: you make the decisions, the tutor challenges them and you see how your design scores.