Graph storage
Adjacency lists at scale and why hops get expensive.
01The intuition
The problem it solves
A school has 2,000 students and you want to know whether Rao and Sharma have a friend in common. Each student's friends are written on their own page. Checking means reading Rao's page (say 50 friends), then each of those 50 pages, 2,500 reads in all, and three degrees out it is 125,000. Now scale the school to a billion members and put the pages on thousands of machines: each hop is a network trip, and the number of pages to read explodes with every degree.
Graphs, things connected to things, are everywhere in system design: social networks, road maps, dependency trees, knowledge graphs. Storing them is easy; traversing them at scale is the hard part, because a walk of k hops touches roughly dk nodes for average degree d, and those nodes live on many machines.
Build it one piece at a time
Step 1: adjacency lists. Store each node once with the list of its neighbours: rao → [sharma, iyer, …]. In a key-value store this is one key per node; in a relational table it is an edge table with an index on from_id. Reading one node's neighbours is one lookup.
Step 2: see the fan-out. A two-hop question reads the start node, then each neighbour. With 50 friends each:
| Degree | Nodes reached | Lookups | Time at 1 ms per lookup, sequential |
|---|---|---|---|
| 1 | 50 | 1 | 1 ms |
| 2 | 2,500 | 51 | 51 ms |
| 3 | 125,000 | 2,551 | 2.5 s |
Step 3: shard with locality in mind. Hash-sharding nodes puts a user's friends on random machines, so every hop is a network round trip. Partitioning by community (friends tend to be in the same region or school) keeps most edges within a shard, so most hops are local. Perfect partitioning is a hard problem; good enough is "shard by region, replicate the hubs".
Step 4: precompute the expensive hops. A nightly job computes and stores each member's second-degree set (precompute versus on the fly). A "how are we connected?" query becomes: same node (degree 0), in my list (1), in my second-degree set (2), else check whether any of my friends has them in their second-degree set (3, done as a set intersection).
Step 5: cache the hubs. A few nodes have millions of edges (a celebrity, a central road junction). Their adjacency lists are read by everyone, so keep them in memory on every shard, and store them in pages so a reader can fetch the first thousand neighbours without the rest.
Why it works, with the numbers
Traversal cost is exponential in hops, so the design is about not traversing:
live cost of a k-hop query ≈ dk lookups; precomputed second-degree sets turn a 3-hop question into about d set lookups, 50 instead of 125,000
Storage for second-degree sets is the price: 2,500 ids × 8 bytes = 20 KB per member, 20 TB for a billion members, which is why they are stored compressed (as Bloom filters or sorted integer lists) and refreshed in batch. The guarantee of an adjacency-list store is that one hop is one lookup; everything beyond that is an engineering choice. The failure modes are supernodes (one hop from a celebrity is a million reads), partitions that cut through dense communities, and stale precomputed sets after a new friendship, which is why the live first-degree list is always consulted alongside the batch result.
The trade-off you must say out loud
A graph database is a convenience over adjacency lists, not a magic machine; at Google scale the question is where the edges live and which hops you refuse to do live. Say the degree limit you answer online (usually 2, with 3 as a set check) and the batch schedule for the rest. The interviewer will press on the graph that does not fit in memory; the answer is sharding by community, precomputed sets, and replicated hubs, in that order.
Where it shows up in the 100 Google problems
- Design LinkedIn-style connection degrees: the reported interview was exactly this, with the instruction not to hide behind a graph-database black box.
- Design Google Maps: the road network is a graph with a billion edges, partitioned by region and precomputed for routing.
- Design a social news feed: the follow graph decides fan-out, and the supernode problem is the celebrity problem.