Designing a Social Graph System
High Level Design·intermediate·~25 min read
- system-design
- social-graph
- graph-traversal
- bfs
- distributed-systems
- hld
What you'll learn
Problem Statement
Design a system that stores a social network's friendship graph (hundreds of millions of users, billions of edges) and answers "shortest path" queries between any two users. This is the system behind features like "How are you connected…
Requirements
Functional Requirements
1. Store friendship relationships between users (bidirectional edges) 2. Given two user IDs, find the shortest connection path between them 3. Display the connecting chain of people (e.g., You → Alice → Bob → Target) 4. Service has high…
Non-Functional Requirements
| Dimension | Target | |-----------|--------| | Users | 100 million | | Average friends per user | 50 | | Total edges (friend relationships) | 5 billion (bidirectional = 2.5B unique) | | Search requests/month | 1 billion | | QPS | ~400 r…
Stage 3 — Bottleneck: Cross-shard BFS traversal latency
At 100M users and 2.5B edges, no single node can hold the graph. You shard the adjacency list across many Person Servers keyed by userid. But now every BFS hop that crosses a shard boundary is a network round-trip — and with 50 friends p…
Stage 4 — Second bottleneck: Hot users, popular paths, and cache stampedes
Social graphs are ruthlessly skewed. A tiny fraction of users (celebrities, brand accounts, verified journalists) are involved in a huge fraction of shortest-path queries — "how am I connected to ?" is the canonical viral query. Two symp…
Stage 5 — Mature architecture
Everything from stages 2–4 wired together: horizontal API tier, sharded Person Servers with read replicas, a lookup service, a two-tier cache, offline precomputation for popular users, and an event stream to invalidate caches when the un…
Cost vs Complexity — When to Pick What
| Concern | MVP choice | Growth choice | Enterprise choice | |---------|-----------|---------------|-------------------| | Compute | Single VM running BFS | K8s deployment of Graph Service (N pods) | Multi-region K8s with cell-based isol…
Migration Path (MVP → Enterprise)
Ordered, with dependencies called out explicitly. Do not skip ahead — later steps assume earlier ones are stable. 1. Canonicalize the cache key (min(A,B)max(A,B)). One-line fix; unlocks the real hit rate you were expecting. 2. Introduce…
Core Data Model
Person Object
Storage on Person Servers
Each Person Server holds a subset of all users. The mapping from personid → server is maintained by the Lookup Service. ---
Core Algorithm: BFS for Shortest Path
Why BFS?
For an unweighted graph, BFS guarantees the shortest path. DFS may find a path but not necessarily the shortest one.
Single-Source BFS
Problem with Single-Source BFS at Scale
With 50 friends per user on average: - 1 hop: 50 nodes - 2 hops: 2,500 nodes - 3 hops: 125,000 nodes - 4 hops: 6,250,000 nodes Each node lookup may require a network call to a different Person Server. At 4 hops, that's potentially millio…
Optimization: Bidirectional BFS
The Key Insight
Instead of searching from source to destination (exploring 6M+ nodes at 4 hops), run two BFS searches simultaneously: 1. Forward BFS from the source 2. Backward BFS from the destination When the two search frontiers meet in the middle, t…
Why This Is Dramatically Faster
The reduction is proportional to branchingfactor^(depth/2) vs branchingfactor^depth.
Bidirectional BFS Algorithm
When Frontiers Meet
---
Handling the Distributed Nature
The Cross-Shard Problem
During BFS, each step requires looking up a person's friend list. If that person lives on a different Person Server, it requires a network call. With millions of nodes explored, this creates a network I/O bottleneck.
Solution 1: Batch Lookups
Instead of looking up friends one at a time, batch all friendids from the current BFS level and send them to the appropriate Person Servers in bulk:
Solution 2: Shard by Location
Friends tend to live near each other geographically. Sharding Person Servers by geographic region increases the probability that a user's friends are on the same server, reducing cross-shard calls.
Solution 3: Start BFS from the Higher-Degree Node
Starting BFS from the person with more friends means the frontier expands faster, increasing the chance of meeting the other search earlier. This is especially useful in bidirectional BFS — start the forward search from the more-connecte…
Caching Strategy
Why Cache?
At 400 QPS with each traversal potentially touching thousands of nodes, caching is essential.
What to Cache
| Data | Cache Strategy | Rationale | |------|---------------|-----------| | Complete BFS results | Key = sorted(userA, userB), TTL = 1 hour | Popular path queries (celebrities) hit repeatedly | | Partial BFS traversals | Store frontier…
Cache-First Query Flow
Offline Batch Computation
For very popular users (celebrities with millions of followers), pre-compute and store shortest paths to the top-N most queried users. These can be stored in a NoSQL database and served without any runtime BFS computation. ---
Handling Scale: Depth Limits and Timeouts
Why Limit Depth?
At 6 degrees of separation, BFS would explore: 50^6 = 15.6 billion nodes — essentially the entire graph. This is computationally infeasible in real-time.
Practical Limits
| Depth | Nodes Explored (single BFS) | Bidirectional | Acceptable? | |-------|---------------------------|---------------|-------------| | 2 | 2,500 | 100 | Fast ( 5s) | | 6 | 15,625,000,000 | 5,000,000 | Infeasible in real-time |
Strategy
- Default limit: 4 hops (covers 99%+ of connected users in real social networks) - If no path found at 4 hops: return "No direct connection found" or offer to search deeper asynchronously - For deeper searches: queue as a batch job, noti…
Fault Tolerance and Availability
Person Server Failure
- Each Person Server has read replicas - If primary fails, read replica serves requests - Lookup Service maintains a mapping of primary and replicas per shard - During failover, queries for users on that shard may have slightly higher la…
User Graph Service Failure
- Stateless — any instance can handle any request - Load balancer routes to healthy instances - In-progress BFS queries are lost on crash (client retries)
Cache Failure
- Graceful degradation: queries fall through to live BFS computation - Increased latency and load on Person Servers, but functionally correct ---
API Design
---
Key Interview Talking Points
1. BFS guarantees shortest path in unweighted graphs — DFS does not 2. Bidirectional BFS reduces explored nodes from O(b^d) to O(b^(d/2)) — potentially 1000x fewer nodes 3. Sharding by geography exploits the fact that friends often live…