1 · Route the search
A friend search moves from the client through the public web path to Query API.
Flow
Client → DNS and Load Balancer → Web Server → Query API.
Interactive diagram · architecture
Design the data structures for a social network — interactive diagram
2 · Locate the person
The graph service asks Lookup Service which Person Server holds the source person.
Flow
Query API → User Graph Service → Lookup Service → Person Server.
3 · Walk the friend graph
User Graph Service runs breadth-first search and retrieves each adjacent person by ID.
Flow
User Graph Service → Lookup Service → Person Server, repeated for friend IDs.
4 · Reuse cached traversals
Complete or partial BFS traversals can be stored to speed up later lookups.
Flow
User Graph Service → Memory Cache → later graph lookups.
Client
What it is
A person’s app or browser starts a friend search.
Its job here
It resolves the site name with DNS. It then sends the search request to the Load Balancer.
Trade-off
The public request uses a REST API.
In the primer
DNS
What it is
DNS maps the site name to an address.
Its job here
It receives the client lookup. The client then sends the request to the Load Balancer.
Trade-off
It is another service in the request path.
In the primer
Load Balancer
What it is
A load balancer distributes incoming requests.
Its job here
It receives the client request. It forwards the request to a Web Server.
Trade-off
It adds a separate component before the web layer.
In the primer
Web Server
What it is
The web server runs as a reverse proxy.
Its job here
It receives a request from the Load Balancer. It forwards the request to Query API.
Trade-off
The reverse proxy adds another hop before Query API.
In the primer
Query API
What it is
The public REST API accepts a friend search.
Its job here
Web Server forwards the request here. Query API sends it to User Graph Service.
Trade-off
External communication uses REST, while internal communication can use RPC.
In the primer
User Graph Service
What it is
This service finds the shortest path through friend relationships.
Its job here
It receives the search from Query API. It uses Lookup Service, then Person Server, to retrieve people and run BFS.
Trade-off
Searching can take considerable time, so the design can set a time or hop limit.
In the primer
Lookup Service
What it is
A lookup maps a person ID to a Person Server.
Its job here
User Graph Service asks it where a person is stored. It identifies the Person Server for the next retrieval.
Trade-off
The graph service may need this lookup again for every adjacent person ID.
In the primer
Person Server
What it is
A Person Server stores people by person ID.
Its job here
Lookup Service identifies this server. It returns the person and their friend_ids to User Graph Service.
Trade-off
User data must be sharded because all users and relationships do not fit on one machine.
In the primer
Memory Cache
Step 4 · Reuse cached traversals
What it is
A memory cache holds person data and saved BFS traversals.
Its job here
User Graph Service checks or stores complete or partial traversals here. Later searches can reuse them before more Person Server lookups.
Examples
- Redis
- Memcached
Trade-off
Cached traversals need an update strategy.
In the primer
←/→ step · Space play/pause · R replay · Home/End jump
Detail · follows playback, or click any box or step to pin it
Close · follow playbackClick any box for an explanation, or use Next or Play to walk through the four flows.
1 · Route the search
The client resolves DNS and sends the search through the load balancer and reverse proxy to Query API.
Query API receives the public friend-search request.
2 · Locate the person
User Graph Service asks Lookup Service which Person Server contains the source person.
The Person Server returns the person and their friend_ids.
3 · Walk the friend graph
User Graph Service runs BFS from the source person through friend IDs.
Each adjacent person can require another Lookup Service and Person Server retrieval.
4 · Reuse cached traversals
Complete or partial BFS traversals can be stored to speed up later searches.
Memory Cache reduces traffic to downstream services for repeated searches.