Cruxly › System design › Design Exercises
Social Graph Storage
a relationship, not a record, is the unit of data
Open the interactive lessonPrompt: design the storage layer for a social graph — hundreds of millions of users, each with up to tens of thousands of friends/followers, supporting "are these two connected," "list my friends," and "friends in common" queries at low latency.
40 minutes first. A relational join handles this at small scale. The exercise is what replaces it once the graph is too large and too densely connected for that to still be true.
Applying the four moves: Scope — store connections for hundreds of millions of users, answer "connected?", "list friends", "friends in common" at low latency; recommendations out. Estimate — edges, not users, are the number: users × average connections, with a long tail where a few accounts have enormous degree. Sketch — adjacency lists partitioned by user, so "list my friends" is a single lookup instead of a join. Deep dive — "friends in common" crosses partitions, because two users' lists live on different shards; and the very high-degree node needs special handling, since its adjacency list is too large to load or intersect naively.
Scope, and why a naive relational join doesn't survive scale
Scope. In scope: storing the friend/follow relationship itself, answering connectivity/list/mutual-friends queries at low latency at massive scale. Out of scope: the news-feed content this graph might feed into (this track's activity-feed and news-feed-ranking exercises cover that, downstream of this one), graph algorithms beyond one-hop and two-hop queries (shortest path, community detection — real, harder extensions, named as out of scope rather than attempted).
A friendships(user_a, user_b) table with a join for "friends in common" works cleanly at small scale: SELECT b.friend_id FROM friendships a JOIN friendships b ON a.friend_id = b.friend_id WHERE a.user_id = X AND b.user_id = Y. This degrades badly once users have tens of thousands of connections — a mutual-friends query between two highly-connected users becomes a join across two very large sets, and at hundreds of millions of users this join can no longer be served from a single database's working set in memory, turning a query that should be single-digit milliseconds into something far slower under real production load. Naming precisely why the relational approach breaks — not "SQL doesn't scale" as a vague claim, but "this specific join becomes expensive on two large sets at read time" — is what separates a real answer from a slogan.
Denormalized adjacency lists: trading storage for read speed
Denormalize: store each user's full list of connection IDs as one value under one key (user_id → [friend_id_1, friend_id_2, ...]), in a key-value or wide-column store (Cassandra, HBase, or a similar system are common real choices). "List my friends" becomes a single key lookup, not a join. "Are X and Y connected" becomes checking whether Y is in X's list (or a dedicated existence check, for very large lists, against a set-typed value rather than scanning a list). "Friends in common" becomes fetching both users' lists via two key lookups, then computing the set intersection in application code (or in a data store with native set-intersection support) — the two lists themselves, even at tens of thousands of entries, are still small enough to be fetched and intersected cheaply, unlike the join-based approach, which had to consider the full cross-product-like relationship at query time.
This is a real, deliberate tradeoff, not a free win: adjacency-list denormalization trades storage efficiency (a bidirectional friendship is now stored twice, once in each direction) and write complexity (adding one friendship means updating two adjacency lists, not inserting one row) for read speed at the specific access patterns this system actually needs. Naming that this is a read-optimized, write-more-expensive choice, made deliberately because reads vastly outnumber writes for a social graph, is the point being tested.
Sharding the graph, and why it isn't clean like other data
A social graph resists clean sharding in a way a lot of other data doesn't, because relationships inherently cross shard boundaries — if users are sharded by user ID (the natural choice), a huge fraction of friendships connect users on different shards, and "friends in common" between two users on different shards requires fetching from both shards regardless of how the sharding key is chosen. There is no sharding scheme that makes every graph query single-shard, because the graph's edges don't respect any partition boundary drawn on its nodes — this is a fundamental property of graph data, not a solvable implementation detail, and stating that plainly (rather than searching for a sharding scheme that doesn't exist) is itself the correct answer.
The practical mitigation is co-locating a user's full adjacency list on one shard (sharding by user ID, with each user's complete friend list stored together, even though the friends themselves live on many different shards) — this at least makes "list my friends" and "am I connected to X" single-shard operations, while accepting that "friends in common between X and Y" always requires a cross-shard fetch when X and Y land on different shards, which for most user pairs, they will.
Failure modes and the honest edges
Celebrity/super-node accounts (millions of followers) break the "lists are small enough to fetch cheaply" assumption the whole design rests on. A list of ten thousand friends and a list of ten million followers are very different objects — the followers list for a celebrity account needs pagination and can't be treated as "fetch the whole list" the way an ordinary user's can, and any mutual-connections query involving a celebrity account needs a different, capped strategy (check the first N, don't attempt a full intersection) rather than the same code path as an ordinary user pair.
Bidirectional consistency after a write — if a friendship add updates two separate adjacency-list rows (one per direction) as two separate writes, a crash between them leaves the graph asymmetric (X lists Y as a friend, Y doesn't list X) until repaired. Either a transactional write across both rows (where the store supports it) or an explicit repair process that reconciles asymmetric edges is needed — silently tolerating temporary asymmetry without a repair mechanism lets inconsistencies accumulate indefinitely.
Directed relationships (follow, not mutual friendship) need to be modeled distinctly from undirected ones — a "followers" list and a "following" list are two different adjacency lists per user, not one symmetric relationship stored once, and a system built only for symmetric friendship needs explicit rework, not just relabeling, to support a directed follow model (Twitter/Instagram-style) correctly.
How to say it in the interview
"The three queries this system has to answer fast — am I connected to X, list my connections, and who do we have in common — are all graph-traversal questions, and the entire design decision is whether to answer them with a general-purpose graph database or with a plain key-value store that's been deliberately modeled to make exactly these three queries cheap."
Checklist
- Explained precisely why a relational join degrades at scale, not just that 'SQL doesn't scale'
- Denormalized each user's connections into one directly-keyed adjacency list
- Computed mutual friends as a set intersection of two already-fetched lists, not a database join
- Named the read-speed-for-write-complexity tradeoff of adjacency-list denormalization explicitly
- Stated plainly that no sharding scheme makes every graph query single-shard
- Sharded by user ID with each user's adjacency list co-located, accepting cross-shard mutual-friend queries
- Identified super-node/celebrity accounts as breaking the small-list assumption the whole design depends on
- Addressed bidirectional write consistency explicitly rather than assuming both directions always update together
- Modeled directed follow relationships as two distinct adjacency lists, not one symmetric relationship