Design a social graph service

Design the service that stores who follows whom for a social network with two billion users: follow and unfollow, lists of followers and following, "do I follow this person?", counts, and mutual connections. Every feed, profile and notification in the product asks it questions, so it must answer in a few milliseconds, even for an account with 150 million followers.

1. The prompt

"Design the follow graph for a social app: users follow each other, see their followers and who they follow, and other services ask the graph questions."

What makes it hard:

• Reads outnumber writes by about 1,000 to 1. Every profile view, feed build and notification checks the graph.
• Each edge has two owners. "Asha follows Ben" must appear in Asha's following list and in Ben's followers list, which live on different machines.
• The degree is wildly uneven. Most people have a few hundred connections; a few accounts have over a hundred million followers.

2. Frame the problem

3. What it must do

1. Follow and unfollow, including follow requests for private accounts and blocks.
2. Answer point questions fast: does A follow B, and how many followers and followings does someone have.
3. Return lists: someone's followers or following, newest first, a page at a time.
4. Find mutual follows between two users ("followed by Chen and 12 others you know").

Not now: "people you may know" (an offline job over this graph), the feed itself (D06), ranking of followers.

4. How well it must do it

5. Numbers that change the design

Illustrative numbers.

6. The nouns

• User (a node), with a visibility setting.
• Edge: a typed, directed link with a time: follows, requested, blocks.
• Inverse edge: the same link stored on the other user's shard, so each user's lists are local to them.
• Counts per user and edge type.

edge_out   (src_id, type, created_at DESC, dst_id) → state   sharded by src_id   "who does src follow?"
edge_in    (dst_id, type, created_at DESC, src_id) → state   sharded by dst_id   "who follows dst?"
           plus a unique index (src_id, type, dst_id) for "does A follow B?"
counts     (user_id, type) → following, followers           sharded by user_id (split for the largest accounts)
outbox     (shard-local) pending inverse writes and count changes

7. The contract

PUT    /v1/users/{me}/following/{target}        → 200 {state: following | requested}
DELETE /v1/users/{me}/following/{target}        → 204
GET    /v1/users/{id}/following?cursor=…&limit=50   → {users[], next_cursor}
GET    /v1/users/{id}/followers?cursor=…&limit=50   → {users[], next_cursor}
GET    /v1/users/{id}/counts                    → {followers, following}

Internal (other services)
  CheckEdges(src, [dst…])     → which of these does src follow?   (batched; up to 500 at once)
  Mutual(viewer, target, k)   → up to k people the viewer follows who also follow the target

Follow and unfollow are idempotent (PUT and DELETE), so a retried tap can't create two edges. Batched checks matter: building a feed of 50 posts asks "do I follow each author?" in one call, not 50.

8. First working version

A graph service in front of a sharded edge store, with a cache tier for reads. Every edge is written twice, once on each user's shard.

8.1 Asha follows Ben

8.2 Reading through the cache

Cache entries are whole small lists and point answers keyed by user (out:asha:follows, count:ben). A write updates the database and then deletes or updates the affected cache entries, so the next read refills them (Module 09).

9. Make it hold up

9.1 Keeping both directions in step correctness

Unfollow uses the same path with a delete. If a follow and an unfollow race, compare their timestamps (or a version per edge) and keep the later one on both sides.

9.2 Where does an edge live? speed

9.3 An account with 150 million followers hot spots

• Lists are only ever read a page at a time, with a cursor of (created_at, src_id), so a request touches 50 rows however big the list is. Nobody scrolls to follower 80 million; cap deep paging.
• Counts: 5,000 new followers a second during a live event would make one counter row the hottest thing in the system. Split it into, say, 64 sub-counters updated at random and summed on read (and cached), or batch increments in the relay before writing.
• Reads of hot keys (the celebrity's count and first page) are replicated across many cache servers and kept briefly in each graph service instance's memory.
• Fan-out isn't the graph's job. Delivering one post to 150 M followers is the feed's problem (D06); the graph just lets it page through the follower list.

9.4 Mutual follows speed

"Which of the people I follow also follow this account?" is the intersection of my following list (hundreds) with the target's followers list (possibly millions).

Compare the costs in the lab in section 13.

9.5 Regions and reading your own follow consistency

Each shard has one leader region for writes and replicas (database and cache) in every region. Reads are served locally. After Asha follows Ben, her own reads for the next few seconds are routed to the leader (or her region's cache is updated as part of the write), so her button and lists change at once, while other users' views catch up through replication. This is the approach Meta described for TAO: a write-through cache in the leader region, and caches elsewhere refreshed as replication arrives.

9.6 Why not a graph database? architecture

Graph databases (Neo4j, Neptune and others) are excellent at multi-hop questions over a graph that fits a cluster with good locality. A social graph's hot path is different: one hop, enormous volume, uneven degrees, and data that doesn't partition cleanly (any user can follow any other). Large social networks have instead stored adjacency lists in sharded relational or key-value stores with a cache tier in front: Twitter's FlockDB and Meta's TAO both took this shape. Multi-hop work ("friends of friends" for suggestions) runs offline over a snapshot, in a batch or graph-processing system.

9.7 The whole design after the deep dives

10. Interviewer follow-ups

11. When things break

12. Wrap-up and the clock

Trade-offs we made:

• Every edge stored twice, so each user's lists are on their own shard.
• One local write plus an outbox, instead of a distributed transaction; the inverse side catches up within a second.
• Counts stored, not computed; split for the hottest accounts.
• A cache tier answers almost every read; read-your-writes for the actor only.
• One-hop questions online, multi-hop work offline.

What we'd watch: read latency by call type · cache hit rate · outbox age · direction mismatches found by the checker · hot keys · follow write errors and rate-limit rejections.

At 10×: more shards and cache servers; the per-user layout scales linearly. The largest accounts grow faster than the rest, so hot-key handling matters more over time.

Common mistakes:

• One edges table sharded one way, so half the queries go to every shard.
• COUNT(*) for follower counts.
• Two separate writes with no plan for a crash between them.
• Offset pagination over a list of millions.
• Reaching for a graph database without saying which multi-hop query needs it.

13. Try it, check yourself, read more

The mutual follows lab. Set the sizes of the two lists and how many names the profile shows, and compare the ways to find mutual follows.

Illustrative costs: ~1 µs per row scanned in a list, ~0.3 ms per batched round trip of up to 100 point lookups. "Stop after 3" shows the first three names, as a profile does.