Course Content
System Design Interview
31 sections · 71 lessons
News Feed: the hybrid design, caching, ranking and follow-ups
News Feed: scope, scale and the fan-out trade-off ended with two designs, each broken by a different part of the traffic. The repair is to route each account to the design that suits it.
This lesson builds that hybrid, then the caching and storage layout that lets its read path stay off disk, and finally ranking and the follow-up questions the problem always attracts.
The hybrid that real systems use
The rule
- Accounts below a follower threshold: fan-out on write. Their posts are pushed into followers' feed lists at publish time.
- Accounts above the threshold: fan-out on read. Their posts are stored once and pulled at read time by anyone who follows them.
- A feed read merges the precomputed list with a pull over the small set of high-follower accounts this reader follows.
Why the merge stays cheap
The pull half looks alarming until you count it. An ordinary user follows perhaps 5 to 20 high-follower accounts. So a feed read is:
1 lookup of the precomputed feed + up to ~20 lookups of "recent posts by account X" + a merge of ~220 candidates, sorted by timestamp, take 20
And the pull half is the most cacheable data in the system. A high-follower account's recent posts are requested by millions of readers per minute, so a small cache of "latest 50 posts per large account" runs at a hit rate close to 100%. The 20 lookups are 20 cache hits of well under a millisecond each, not 20 database queries.
Compare with pure pull's 200 lookups against a long tail of accounts that nothing caches well. That is the difference between the two, and it is why the hybrid is not a compromise but a genuine improvement on both.
Where the threshold sits
Somewhere in the range of tens of thousands to a few hundred thousand followers, and it is tuned, not derived. Be honest about that in the interview — it scores better than a confident invented formula.
The forces pushing it in each direction:
| Lower the threshold | Raise the threshold |
|---|---|
| Fewer fan-out insertions overall | Fewer accounts in the pull path |
| Less write amplification at peak | Cheaper merges at read time |
| More accounts in the merge path | More fan-out load, worse celebrity lag |
A sensible starting point: set it so the pull set covers accounts responsible for a meaningful share of total fan-out volume, then move it based on observed feed-read latency and fan-out queue depth. Both are metrics you would actually have.
The other lever, which is bigger than the threshold
Do not fan out to inactive users.
If 40% of accounts have not opened the app in 30 days, skipping them removes 40% of the 30 billion daily insertions — 12 billion writes a day — for no user-visible cost. Those users get a pull-built feed on the rare occasion they return. This is usually a larger saving than any threshold tuning, and it is the optimisation candidates most often miss.
The publish path, end to end
- Post service writes the post row and returns 202 to the author.
- It emits a
post_createdevent to a distributed log (Kafka is the common implementation). - A fan-out consumer reads the event, looks up the author's follower count.
- Below threshold: fetch followers, filter to active, batch-insert the post identifier into each feed list.
- Above threshold: do nothing. The post is picked up at read time.
Storage and caching
The hybrid only performs if the read path never touches a disk. That means several caches, each holding a different shape of data, and one rule that keeps them small.
The rule: feeds hold identifiers, not content
A feed entry is a post identifier and a sort score. Nothing else.
Identifiers: 300M users × 200 entries × 16 bytes = 960 GB
Full content: 300M users × 200 entries × 1 KB = 60 TB
Sixty times the memory for the same feed. And the identifier version has a second advantage: when a post is edited or deleted, there is one copy of the content to change, not a copy in every follower's feed.
The five caches
| Cache | Key → value | Why it exists |
|---|---|---|
| Feed cache | user ID → ordered list of post IDs | The precomputed half of the hybrid |
| Content cache | post ID → post body and metadata | Hydrates identifiers into posts |
| Social graph cache | user ID → follower and following lists | Read on every publish and every read |
| Action cache | post ID → like, comment, share counts | Changes far faster than the post does |
| Hot-author cache | account ID → latest 50 post IDs | The pull half of the hybrid |
Separating the action cache from the content cache matters. Counters on a popular post change thousands of times a minute while the post body never changes. Storing them together means invalidating an immutable body every time somebody taps like.
The read path, traced
- Look up the feed cache for the reader → 200 post identifiers.
- Look up the hot-author cache for the large accounts this reader follows → up to 1,000 more identifiers.
- Merge by sort score, take the top 20 after the pagination cursor.
- Hydrate: multi-get 20 posts from the content cache, 20 entries from the action cache, and author profiles.
- Filter: blocked authors, deleted posts, and posts the viewer should not see.
Step 5 is deliberately at the end. Filtering at read time is what lets deletion be cheap — the deletion follow-up below returns to this.
Storage behind the caches
Post content sits in a store chosen for a key-value access pattern at 1,500 writes/s — a wide-column or document store partitioned by post identifier (Databases: choosing and justifying). The social graph is the awkward one: it is relational in shape and enormous. Most large systems shard a purpose-built graph store by user, accepting that a two-hop query is expensive, because feeds only ever need one hop.
Feed lists themselves are persisted, not cache-only. An in-memory cluster losing a node must not mean rebuilding a million feeds under live traffic — a cold rebuild by pull is a stampede against the post store.
Ranking and follow-ups
Chronological was the scoping decision in News Feed: scope, scale and the fan-out trade-off. Now pay for it, and take the follow-ups this problem always attracts.
What ranking does to the design
A ranked feed scores each candidate post for this viewer using signals that change constantly: engagement so far, recency, the viewer's affinity with the author, and predicted interaction. A score computed at publish time is stale within minutes and is wrong for every viewer except the one it was computed for.
So ranking splits the read path in two:
- Candidate generation — still fan-out. The precomputed feed list plus the pull over large accounts produces a few hundred candidates. This half is unchanged.
- Scoring — at read time, over those few hundred candidates only.
That is the key structural insight: fan-out produces candidates, ranking orders them. Ranking does not replace fan-out, and it does not make fan-out on write pointless. It changes the feed list from "the feed" into "the candidate pool", and it adds a latency budget for inference — perhaps 30 to 50 ms for a few hundred candidates, which is why models at this stage are lightweight. Machine Learning System Design Interview covers the modelling side.
Pagination that survives new posts
Offset pagination breaks immediately. A reader loads posts 1–20, three new posts arrive, and OFFSET 20 now returns items that were at positions 18–20 — three duplicates and three missed posts.
Use a cursor: an opaque token encoding the sort key of the last item returned, such as (score, post_id). Page two asks for items strictly below that key. New posts arrive above the cursor and are picked up by a separate "new posts" indicator rather than being injected into the page the user is scrolling.
For ranked feeds, even a cursor is not enough, because the score itself changes between requests. The common answer is to freeze a session: compute the ranked candidate list once, cache it for that session with a short lifetime, and paginate within the frozen list.
Deletion and editing
The feed holds identifiers, so deletion does not touch feeds at all. The post is marked deleted, the content cache entry is invalidated, and the read path's step-5 filter drops it. The alternative — scrubbing an identifier from 100 million feed lists — is 100 million writes to remove one item, which is absurd next to one write plus a filter.
The cost is a small amount of wasted read work: a page of 20 might return 19 after filtering. Over-fetch slightly (ask for 25, return 20) and the user never notices.
Cold start
A brand new account follows nobody, so both halves of the hybrid return nothing. The feed cannot be empty, so it is filled from other sources: popular posts in the user's region and language, accounts related to any contacts imported, and topic-based recommendations from an onboarding step. This is a product problem with an engineering consequence — the feed service needs a pluggable fallback source, and it is worth naming rather than leaving as a blank screen.