A system design interview guide to storing and querying who follows whom at scale — the relationship layer underneath feeds, friend suggestions, and follower counts — without letting a single celebrity break the whole system.
Student edition · start with the guarantee
Maintain directed edges and reverse indexes without losing unfollow ordering or using stale edges for authorization.
Correctness contract: One edge version is authoritative. Derived changes are durable, idempotent, and version-ordered; security checks follow an explicit freshness policy.
Basic HTTP, databases, and programming are assumed. Specialized terms are explained below. Named products motivate the problem; this is an educational design, not a claim about their current internals. Capacity numbers are illustrative decimal payload estimates, not benchmarks. Add indexes, protocol overhead, replicas, headroom, and failure capacity before provisioning.
Underneath every social product is a deceptively simple data structure: a set of relationships between users. Who follows whom, who is friends with whom, who blocked whom. It looks like a table of pairs until you confront the numbers — billions of users, hundreds of billions of edges, a handful of accounts with tens of millions of followers each — and the access patterns, where "list this user's followers" and "is A following B" must each return in milliseconds. The interesting design problem is not modeling a relationship; it is storing those relationships so the common queries are fast, sharding them across many machines without making every query touch every machine, and surviving the wildly uneven reality that a few accounts have millions of edges while most have a handful. This guide builds that storage layer up from the model outward.
Each definition includes a concrete example and the condition under which the mechanism is useful. You can read this guide without opening another guide.
Transactional outbox
A business transaction writes its state change and an event row to the same database. A relay publishes committed event rows later, retrying until the broker durably accepts them.
Example. An order and its OrderCreated outbox row commit together. A relay crash after publish but before marking sent publishes the same event ID again on restart.
Limit. The relay is at-least-once, not magically exactly-once. Consumers dedup transactionally; preserve per-entity sequence when order matters. CDC is change data capture: reading committed database changes.
Optimistic concurrency and compare-and-set
Update state only if the expected version or status still matches, in the same atomic operation that changes it. A failed comparison means a conflicting operation won; reread or return a conflict.
Example. UPDATE seats SET status='held', version=version+1 WHERE id=? AND status='available' allows only one concurrent claimant to update the row.
Limit. Application-level GET then unconditional SET is not equivalent. Include acquisition identity to reject stale callbacks, and couple related invariants in a transaction.
Replication
Maintaining copies of data on independent storage nodes. Synchronous acknowledgement waits for specified durable copies; asynchronous replication sends changes after the client has already received success.
Example. A primary acknowledges after two durable copies in different zones. A follower that applies updates later can serve an old value even though the write is durable.
Limit. Replica count is not a complete durability or availability guarantee. State the failure domains, acknowledgement policy, promotion rules, repair process, and what happens if all copies fail.
Fanout on write and read
Fanout distributes one event to many recipients. On-write fanout precomputes recipient inbox entries; on-read fanout merges source events when a recipient asks. A hybrid chooses using measured write amplification and read cost.
Example. One post to 200 followers creates up to 200 inbox inserts. A celebrity's million followers can instead read the author's shared stream when they open their feed.
Limit. Fanout is not atomic across inboxes. Persist the post and delivery work via an outbox, dedup references, catch up after misses, and recheck privacy/deletion at serving time.
Cache-aside and invalidation
A read checks a cache, reads the authoritative store on a miss, then fills the cache. A write commits to the store and invalidates or refreshes the cached value. TTL means time to live, not a freshness proof.
Example. A reader fetches version 1, a writer commits version 2 and invalidates, then the delayed reader caches version 1. DB-first invalidation alone does not prevent this refill race.
Limit. Use invalidation-aware fill leases or version fences for stronger behavior; a TTL only bounds one entry's residence under additional assumptions. Authorization and revocation need an explicit stale-data policy.
Cardinality
The number of distinct identities a store must track. A metric series is its metric name plus the full label combination. The product of label-value counts is an upper bound when not every combination occurs.
Example. 100 hosts × 20 routes × 5 status codes can produce up to 10,000 series. Adding a unique request_id can make every request create a new series.
Limit. Hashing every ID to a distinct digest does not reduce cardinality or guarantee anonymity. Use bounded categories, explicit limits, or intentional fixed-bucket aggregation.
1. Requirements & Clarifying Questions
Clarifying questions to ask
Follow (one-way) or friend (mutual)? How many users, and how many connections each? Which queries matter most: follower lists, "do I follow them", mutual friends, suggestions? How fresh must counts be? Assume: follow model, 1B users, 200 connections on average, heavy skew (some accounts have 30M+ followers).
Functional
Non-functional
Follow and unfollow
One-hop reads in a few ms (they sit on every page)
List followers / following (paged)
Scales to hundreds of billions of edges
Is A following B?
Handles accounts with tens of millions of followers
Follower counts; people-you-may-know
Eventual consistency between directions is OK (seconds)
2. Back-of-the-Envelope Estimation
Quantity
Assumption
Result
Edges
1B users × 200 follows
200B
Stored entries
×2 (following + followers copies)
400B
Raw size
400B × ~24 B (two ids + timestamp)
~9.6 TB
With 3 replicas
9.6 TB × 3
~28.8 TB
Follow writes
100M/day ÷ 86,400
~1.2K/s
One celebrity's follower ids
30M × 8 B
~240 MB
Friends-of-friends work
200 × 200 candidates
40K ids
Takeaway
Data fits on tens of machines; skew and hop-2 cost are the real problems
shard by user id
Intuition
Each person keeps two address books: "people I follow" and "people who follow me". Looking up either one is instant. The catch is that every new follow means writing in two books, often kept in two different buildings.
3. API & Data Model
POST /v1/users/{a}/following/{b} # follow (idempotent)
DELETE /v1/users/{a}/following/{b} # unfollow
GET /v1/users/{a}/following/{b} -> 200 or 404 # is A following B?
GET /v1/users/{id}/followers?cursor=<c>&limit=100 # paged
GET /v1/users/{id}/counts -> { followers, following }
Row key (sorted KV / wide-column)
Value
Serves
(A, "following", created_at, B)
—
A's following list, newest first
(B, "followers", created_at, A)
—
B's followers list, newest first
(A, "edge", B)
created_at
"Is A following B?" as one point get
(A, "counts")
followers, following
Profile counters
All rows that start with user A live on A's shard, so each one-hop query is a single-shard read or range scan.
4. The Edge Model
The first decision is what an edge actually represents, because the two common relationship types behave differently and that difference shapes everything downstream. Getting this right early prevents a lot of confusion later.
Relationship
Direction
Meaning
Example
Follow
Directed
A follows B does not imply B follows A. Each edge is one-way.
Twitter / Instagram following
Friendship
Undirected (mutual)
If A is friends with B, then B is friends with A. The edge is symmetric.
Facebook friends
A follow is a directed edge: it has a source (the follower) and a target (the followee), and the reverse may or may not exist. A friendship is an undirected edge, but it is almost always implemented as two directed edges — one in each direction — precisely so that the storage and query machinery can be identical for both. Once you model friendship as a mutual pair of follow edges, you only ever have to design for the directed case, with the extra rule that friendship edges are created and deleted in pairs. For the rest of this guide we reason in terms of directed follow edges.
Users are nodes and follows are directed edges: an arrow A → B means A follows B. Each user is stored as two adjacency lists — the set of accounts they follow ("following") and the set of accounts that follow them ("followers"). A friendship is simply a pair of follow edges pointing both ways.
5. Adjacency-List Storage
Having decided that the graph is a set of directed edges, the next question is how to lay those edges out in storage so the common queries are cheap. The dominant approach is the adjacency list: for each user, store the list of users they are connected to. The natural alternative — one giant table of (source, target) rows — is simple but forces an index scan for every lookup; adjacency lists put each user's neighbors right where you can grab them in one read.
Concretely, each user gets (at least) two lists:
Following list — the set of accounts this user follows. This is the list you read to build the user's home feed, since their feed is assembled from the people they follow.
Followers list — the set of accounts that follow this user. This is the list you read to show "followers" and, crucially, to know who to deliver this user's new posts to.
# adjacency lists keyed by user id
following[A] = {B, C, D} # accounts A follows (a set, not a list)
followers[A] = {E, F} # accounts that follow A# reading "who does A follow" is a single keyed lookup
function get_following(user_id):
return following[user_id]
The win is that the two most frequent reads — "who does this user follow" and "who follows this user" — each become a single keyed lookup rather than a scan over an edge table. The cost, which the next section addresses head-on, is that you are now storing each relationship twice and must keep the two copies in agreement.
6. Denormalizing Both Directions
A directed edge "A follows B" is logically a single fact, but the two queries it serves pull from opposite ends. "Who does A follow?" needs the fact indexed by A; "who follows B?" needs the same fact indexed by B. If you store the edge only once, one of those two queries always degrades into a scan. The standard answer is to denormalize: store the edge from both ends.
So creating a single follow writes two records:
Append B to following[A] — the forward direction, for A's feed and A's "following" list.
Append A to followers[B] — the reverse direction, for B's "followers" list and B's post fan-out.
function follow(a, b):
if following[a].add(b): # forward edge: A -> B (false if it existed)
followers[b].add(a) # reverse edge: maintained for fast reads
counts[a].following += 1 # denormalized counters, too
counts[b].followers += 1
function unfollow(a, b):
if following[a].remove(b):
followers[b].remove(a) # both copies must change together
counts[a].following -= 1
counts[b].followers -= 1
# a and b usually live on different shards: see Edge Consistency
Keep counts separately
Profiles show "30.2M followers" on every view. Counting a 30M-entry list each time is far too slow, so store the count as its own small value and update it with the edge. The if guard matters: a repeated follow request must not add 1 twice. For very hot accounts, spread the counter over several sub-counters and sum them on read, so one key is not hammered.
This trades write cost and storage for read speed, which is the right trade for a social graph because reads vastly outnumber writes — people view follower lists and load feeds far more often than they follow or unfollow. The price is that every relationship now exists as two physical records that can drift out of sync if a write half-fails, which is exactly the consistency problem addressed later.
The denormalization here is the same instinct as a database secondary index: keep a second copy of the data organized by the other key so the reverse lookup is also O(1). The difference is that you are maintaining that second copy yourself, in application logic, which is why edge consistency becomes your problem.
7. Query Patterns
The storage layout only makes sense in light of the queries it has to serve, so it is worth enumerating them and seeing how each maps onto the adjacency lists. Three patterns dominate, in rough order of difficulty.
Is A following B? A membership test: check whether B appears in following[A] (or, equivalently, whether A appears in followers[B]). With the right structure this is a near-constant-time point lookup, and it is the query behind rendering a "Follow / Following" button. "Right structure" matters: scanning a plain list of 30M ids is O(n). Store the edge under its own key, such as (A, "following", B) in a sorted KV store, or use a hash set, so the check is one get.
List the followers (or following) of a user. A direct read of one adjacency list, returned in pages. Cheap for ordinary users; the pathological case is the celebrity with millions of followers, handled in its own section.
Friends-of-friends. A two-hop traversal: take the user's neighbors, then the neighbors of each of those, then remove the user and anyone already a direct connection. This powers "people you may know." It is the most expensive pattern because the work fans out multiplicatively with each hop.
The friends-of-friends query as a breadth-first expansion: start at a user, read their adjacency list (hop 1, direct connections), then expand each of those to their connections (hop 2), and finally deduplicate and filter out the user and anyone already connected to produce the ranked suggestion set.
# friends-of-friends: a bounded two-hop BFS
function friends_of_friends(a):
direct = set(following[a])
candidates = Counter() # missing keys start at 0
for f in direct:
for ff in following[f]: # hop 2
if ff != a and ff not in direct: # drop self + already-known
candidates[ff] += 1 # count mutual connections
return candidates.most_common(50) # rank by mutual count
Cost check: with 200 connections each, hop 2 reads up to 200 × 200 = 40,000 ids spread over many shards. That is too slow to run on every page view, so "people you may know" is usually computed offline in batch (or sampled: take only the first 50 neighbors of each friend) and cached per user.
8. Sharding by User Id
No single machine can hold hundreds of billions of edges, so the graph has to be partitioned across many shards. The natural partition key is the user id: a user's adjacency lists live on the shard that owns that user. This keeps any single user's data co-located, so "list A's followers" hits exactly one shard.
Edges are sharded by user id: each shard owns a range (or hash bucket) of user ids and stores the adjacency lists for those users. "Is A following B?" reads following[A], so it is answered on A's shard alone. Friends-of-friends is different: the second hop's users live on many shards, so the query must scatter to them and gather the results.
Sharding by user solves the storage problem but introduces the cross-shard query problem. Because an edge connects two users who may be owned by different shards, queries about a single user are clean but queries that span an edge are not:
"List A's followers" stays on one shard — A's followers list lives entirely on A's shard (thanks to denormalization).
"Is A following B?" can be answered on A's shard alone, since A's following list is there — this is a good reason to prefer reading the forward edge.
Friends-of-friends is genuinely cross-shard: the second hop's users are scattered across many shards, so the traversal fans out to many machines and must gather the results. This is why two-hop queries are usually precomputed or served from a separate system rather than run live.
The general lesson is that denormalizing both directions is what keeps the high-frequency queries single-shard; the multi-hop queries that inherently cross edges are the ones you design around — by precomputing, caching, or accepting a scatter-gather.
One follow touches two shards. The forward edge is written first and is authoritative; the reverse copy follows from a durable log.
9. The Celebrity Problem
The distribution of follower counts is extremely skewed: most users have tens or hundreds of followers, but a few have tens of millions. That single fact — the hot key — breaks several assumptions the design has quietly been making.
One adjacency list no longer fits or reads cheaply. A followers list with thirty million entries cannot be loaded in one go; it has to be itself paginated and often split across storage. The shard owning a celebrity also becomes a load hot spot.
It interacts with feed fan-out. The naive way to deliver a post is "fan-out on write": push the post into the feed of every follower. For an ordinary user that is fine. For a celebrity, a single post means writing to millions of feeds at once — a write storm that is wasteful and slow, especially since many of those followers may never log in to see it.
The standard resolution is a hybrid fan-out: use fan-out on write for ordinary accounts, and fan-out on read for celebrities. Ordinary users' posts are pushed to their followers' feeds eagerly; a celebrity's posts are not pre-pushed, and instead each follower's feed query pulls the celebrity's recent posts at read time and merges them in. This caps the write amplification of any single post while keeping the common case fast.
function publish(author, post):
if follower_count(author) < FANOUT_THRESHOLD:
for f in followers[author]:
feed[f].push(post) # fan-out on write (ordinary user)
else:
hot_posts[author].add(post) # celebrity: pulled in at read time
function build_feed(user):
base = feed[user].recent() # pre-pushed posts
celebs = [hot_posts[c] for c in following[user] if is_hot(c)]
return merge(base, celebs) # fan-out on read for hot accounts
The celebrity problem is where the social graph design and the feed design meet. The graph layer must expose follower counts cheaply so the publisher can choose write-time vs read-time fan-out, and it must paginate giant follower lists. A design that ignores the skew works in the demo and falls over the first time a celebrity posts.
10. Edge Consistency
Commit the authoritative forward edge and reverse-index event in one transaction/outbox. Apply derived events idempotently by edge identity and version; retain removal state so delayed follow events cannot undo newer unfollows.
Update counters only for accepted transitions, not retried events; reconcile from authoritative edges or use versioned contributions. A bounded freshness promise needs monitored deadlines and degraded behavior, not just a background scan.
Blocks/privacy/membership need authoritative or carefully bounded freshness checks. Transactional secondary indexes can be simpler at modest scale; storing an edge once with two indexes does not inherently force a scan. Application denormalization is justified by shard/access requirements.
11. KV Store vs Graph DB
A recurring interview question is whether to build the graph on a general-purpose key-value store with adjacency lists or to adopt a dedicated graph database. Both are legitimate; the right answer depends on which queries dominate.
Approach
Strengths
Weaknesses
KV / wide-column store with adjacency lists
Massive horizontal scale; predictable O(1) reads for one-hop queries; operationally well understood; you control sharding and denormalization.
Multi-hop traversals are awkward and must be done in application code or precomputed; you maintain edge consistency yourself.
Dedicated graph database
Multi-hop traversals (friends-of-friends, paths) are first-class and expressive; the model matches the domain directly.
Harder to scale to the very largest graphs; sharding a graph engine is itself a hard problem; can be a heavier operational dependency.
For the bread-and-butter social graph — overwhelmingly one-hop reads (followers, following, is-A-following-B) at enormous scale — most large systems land on a partitioned KV or wide-column store with hand-maintained adjacency lists, precisely because the dominant queries are simple lookups and scale matters more than traversal expressiveness. A dedicated graph database earns its place when deep, ad-hoc traversals are central to the product. The honest interview answer is to pick based on the query mix and to acknowledge that the multi-hop queries are the ones that make a graph database tempting and a KV store work harder.
What real companies built
Facebook TAO (USENIX ATC 2013) stores objects and typed "associations" in sharded MySQL behind a large, graph-aware cache. Many association types have an inverse type (A likes post, post liked-by A); TAO writes both, not atomically, and repairs half-written pairs asynchronously. Twitter FlockDB (open-sourced 2010) stored follow edges in both directions on sharded MySQL and focused on fast one-hop lookups, counts and set operations, not deep traversals. Both are KV-style adjacency stores, which supports the choice above.
12. Failure Modes
What fails
Effect
Handling
Reverse-edge write fails
A follows B, but B's follower list misses A.
Reverse write driven by a durable log and retried; background reconciliation fixes leftovers.
Counter drifts from the list
"1,203 followers" but 1,201 in the list.
Idempotent follow (guarded increment) plus periodic recount jobs.
Celebrity shard overloaded
Slow reads for everyone on that shard.
Cache hot lists, add read replicas, or split a giant list across sub-shards.
Shard down
Its users' lists unavailable.
Replicas with failover; serve cached lists read-only meanwhile.
Follow spam / bots
Millions of fake edges, wrong counts.
Per-user follow rate limits and abuse detection before the write.
13. Tradeoffs & Alternatives
Decision
Option A
Option B
Usual choice
Edge storage
One edge table, index on both columns
Two denormalized adjacency copies
Two copies at large scale; one table with two indexes when small
Consistency
Distributed transaction across shards
Authoritative side + async repair
Async repair
Counts
Count the list on read
Stored counter
Stored counter
Suggestions
Live two-hop query
Offline batch, cached
Offline batch
Engine
Sharded KV / MySQL
Graph database
KV for one-hop at scale; graph DB for deep traversals
14. Summary
A social graph is a store of directed edges engineered so the common queries are cheap and the skew of the real world does not break it. The design is a chain of reinforcing decisions:
Concern
Mechanism
What is a relationship?
A directed follow edge; a friendship is just a mutual pair of directed edges.
How are edges stored for fast reads?
Adjacency lists per user: a "following" list and a "followers" list.
How are both directions made fast?
Denormalize — write each edge from both ends so each lookup is a single keyed read.
What queries must be cheap?
Is A following B (point lookup), list followers/following (paged read), friends-of-friends (two-hop BFS).
How is the graph partitioned?
Shard by user id; single-user queries hit one shard, edge-spanning queries may cross shards.
How do we survive celebrities?
Hybrid fan-out — fan-out on write for ordinary users, fan-out on read for hot accounts; paginate huge lists.
How do the two copies stay in agreement?
Eventual consistency: one authoritative direction, async repair via a log, background reconciliation.
What storage engine?
Partitioned KV / wide-column with adjacency lists for scale; a graph DB when deep traversals are central.
The recurring theme: a social graph is read-heavy and brutally skewed, so the design optimizes the frequent one-hop reads with denormalized adjacency lists and user-id sharding, then spends its remaining complexity budget taming the two things that break that simple picture — cross-shard multi-hop queries and the celebrity hot key.
Worked example: follow and unfollow arrive out of order
A follows B at version 1 and unfollows at version 2.
Read top to bottom. The table below explains the state and guarantee at each step.
Step
State, calculation, and reasoning
1. Commit the forward fact
Write the edge/version and outbox event in one transaction. Update counts only for accepted transitions.
2. Project unfollow v2
The reverse index stores absent at version 2 and retains its removal/version metadata.
3. Receive delayed follow v1
Ignore it. A plain set-add retry could resurrect an already removed relationship.
4. Authorize a read
Use authoritative block/access state or a documented freshness check, not an eventual reverse index as an access grant.
Check your understanding: Does background repair guarantee a fixed convergence time?
Only with enforced coverage, backlog, retries, and failure assumptions. Eventual consistency itself has no fixed deadline.
Run a small, testable model
Download concepts.py. It uses only the Python 3.10+ standard library. From the directory where you saved it, run:
python3 concepts.py projection
python3 concepts.py test
The versioned projection rejects stale updates and retains the newest edge state.
The program contains deterministic assertions and failure traces. It is a learning model, not a production service: it does not implement network consensus, distributed durability, authentication, or third-party delivery. Read its contracts and try changing an input before extending it.
Follow endpoints; row keys for both directions and the edge check.
15–25 min
High-level design
Adjacency lists, denormalization, sharding by user id.
25–40 min
Deep dives
Consistency between copies, counters, celebrities, friends-of-friends cost.
40–45 min
Wrap-up
KV vs graph DB, TAO/FlockDB as evidence, metrics.
16. Common Mistakes
Storing only one direction. Then "who follows B?" scans the whole edge table.
Using a list for membership checks. O(n) on a 30M list; use a keyed edge or a set.
Counting followers on every profile view. Keep a counter.
Running friends-of-friends live. 40K cross-shard reads per request; precompute it.
Demanding a distributed transaction per follow. Costly and unnecessary; one side is truth, the other is repaired.
Ignoring skew. Averages hide the accounts that break the design.
17. Check Yourself
Why is each follow stored twice?
Answer
"Who does A follow" needs the edge keyed by A; "who follows B" needs it keyed by B. Two copies make both a single keyed read.
1B users with 200 follows each, stored both ways at 24 bytes per entry. Raw size?
Answer
200B edges × 2 = 400B entries × 24 B = 9.6 TB, about 28.8 TB with three replicas.
Why does candidates = {} followed by candidates[ff] += 1 fail in Python?
Answer
The key does not exist yet, so reading it raises KeyError. Use collections.Counter() or defaultdict(int).
The reverse-edge write to B's shard fails. What does the user see and how is it fixed?
Answer
A sees "Following", but B's follower list lacks A for a while. The reverse write is retried from a durable log, and a reconciliation job catches anything left.
Why is "is A following B?" answerable on one shard?
Answer
A's forward edges (and the (A, "edge", B) key) live on A's shard, so one point get answers it.
How did Facebook's TAO keep inverse associations in sync?
Answer
It wrote the forward and inverse edges separately (not atomically) and fixed any half-finished pair with asynchronous repair jobs.
18. Key Terms & Further Reading
Directed edge
A one-way link, such as A follows B.
Adjacency list
For each node, the list of nodes it links to.
Denormalization
Storing the same fact twice so both lookups are fast.
Hot key
A key with far more traffic than others.
Scatter-gather
Send a query to many shards and merge the answers.
Eventual consistency
Copies may differ briefly but converge.
Reconciliation
A background job that finds and fixes mismatched copies.
Bronson et al., "TAO: Facebook's Distributed Data Store for the Social Graph", USENIX ATC 2013.
Twitter's FlockDB (open-sourced 2010, GitHub twitter-archive/flockdb): sharded MySQL adjacency store.
Martin Kleppmann, Designing Data-Intensive Applications, Chapter 2 (graph-like data models) and Chapter 6 (partitioning, skewed workloads and hot spots).
Alex Xu, System Design Interview – An Insider's Guide, Volume 1, "Design a News Feed System" (fanout and the follower graph).
