BOOKS DEEP-READ · SYSTEM DESIGN INTERVIEW VOL 1 · CH 11
System Design Interview Vol 1 · Ch 11 · Alex Xu · 2020
Open any social app and scroll. That endless column of things your friends posted is the news feed. Chapter 11 asks you to build one. It looks like nothing more than "sort your friends' posts by time", and it is in fact the book's best training ground for one instinct: the same work can be done when someone posts or when someone looks, the cost differs by tens of times, and neither side is always the cheaper one.
Think of each person's feed as a personal newspaper. There are two ways to make it.
One: print ahead. The moment anyone posts, you run around and add a line to the newspaper of every single person who follows them. When you wake up, your paper is already printed and waiting. You pick it up and go.
Two: assemble on arrival. You do nothing in advance. The instant a reader shows up, an editor runs to each person they follow, copies down the newest few items, and staples a paper together on the spot.
"Assemble on arrival" is the easier thing to build and the first thing to break. If you follow two hundred people, every refresh means two hundred errands — and if just one of them is slow, you wait. The time to assemble a paper is set by the slowest errand, not by the average one. A refresh that takes several seconds is a product nobody keeps using.
So the mainstream answer is print ahead. You post, and the system immediately looks up your friend list and adds a line to each of their papers. Reading becomes a single action: pick up the copy that is already printed. Refresh feels instant not because anything got faster, but because the work was moved to the moment you hit "post".
Printing ahead has a soft spot: the number of copies equals the number of followers. An account with a hundred million followers posts once, and the system must add a line to a hundred million papers. Even printing a hundred thousand copies a second, that is over a quarter of an hour. Worse, only a few million of those people will actually look today — the rest were printed for nobody.
So real systems split people by who did the posting. Ordinary accounts: print ahead. Huge accounts: don't print, assemble on arrival — because the number of huge accounts any one person follows is a few dozen at most, and a few dozen errands is a bargain. What you see is the pre-printed stack plus the freshly fetched celebrity items, shuffled together by time.
The honest cost: printing ahead means the same post gets copied hundreds or thousands of times inside your system, the write volume and storage go up accordingly, and the vast majority of those copies will never be read by anyone.
Every design decision in a news feed answers one question: do you assemble the paper when somebody posts, or when somebody looks? The first reads instantly but writes brutally; the second writes cheaply but reads painfully. The answer is not to pick one — it is to split by publisher: print ahead for ordinary accounts, assemble on the fly for the huge ones, and merge the two at the end.
Want the fan-out strategies, the cache layers and the real numbers? → Switch to the deep read
This chapter is not about sorting your friends' posts by time. It is a problem in moving compute between the write path and the read path: fan-out on write puts all the work at posting time and buys you a millisecond refresh, at the price of write amplification equal to the follower count; fan-out on read puts all the work at refresh time, costs almost nothing to write, and pays for it with a scatter-gather on every read whose tail latency is set by the slowest shard. The real answer is a hybrid split by publisher — and the judgement that the routing key is the publisher, not the user and not the content is the thing worth taking away.
This is the eighth case study in Part II of Volume 1. It follows Ch10, the notification system — both are fan-out problems, differing in where the fan-out lands: notifications fan out to third-party channels you do not control, a feed fans out into storage you own. It leads into Ch12, chat, which moves from one-to-many broadcast to one-to-one and group real-time delivery. In the wild it is Twitter's home timeline, Facebook's News Feed, the LinkedIn feed — the beating heart of almost every social product.
The chapter's scenario: 10 million daily active users, a cap of 5,000 friends per user, a reverse-chronological feed, posts containing images and video, both web and mobile.
Spread the numbers out and the problem shows itself immediately (what follows is derived from that scenario, not quoted from the book). Say each user posts twice a day: 20 million posts/day ≈ 230 posts/s, peaking around 700/s at 3×. On that number alone, one machine would do.
But the moment you choose to materialise, the accounting changes completely. At an average of 200 friends — well under the 5,000 cap — each post writes 200 inbox rows: 20M × 200 = 4 billion writes/day ≈ 46,000 writes/s, with peaks near 140,000/s. And the read side? Ten million people refreshing ten times a day is 100 million reads/day ≈ 1,160 reads/s.
Which is the first counter-intuitive thing in this chapter: a news feed looks like the textbook read-heavy product, yet the instant you adopt fan-out on write it becomes a write-heavy system — roughly 40:1 writes to reads. Capacity must be planned against fan-out writes, not against refreshes; estimating from refreshes is off by two orders of magnitude.
Both sides have a failure mode: without materialisation, a refresh is 200 shard queries and easily lands in whole seconds; with it, one account with a hundred million followers posts and generates a hundred million writes, turning shards into hotspots and dragging every ordinary user's posting latency down with it.
The first thing the book does is not pick a technology but split the system in two: feed publishing (user posts → content persisted → distributed) and feed building (user refreshes → fetch and render). Two endpoints: POST /v1/me/feed and GET /v1/me/feed.
Why is that cut worth naming? Because every argument about fan-out is really an argument about how work is divided between those two flows. Once split, the question becomes quantitative: write-side cost is proportional to follower count, read-side cost to followee count, and you are simply choosing which of the two numbers to pay. Inside the publishing flow: web servers do authentication and rate limiting (the book names rate limiting explicitly as the anti-spam mechanism), the post service persists the content, and the fan-out service is the real subject of the chapter.
At posting time, push the post ID into every friend's inbox. There is exactly one benefit, and it is worth a great deal: a read becomes one cache lookup — milliseconds to tens of milliseconds, independent of how many accounts you follow.
The costs are two, and the book names both. The hotkey problem: an account with a huge following posts and the fan-out explodes — 100 million followers means 100 million writes for one post; even at 100,000 writes/s that is about 17 minutes, during which different followers see it at visibly different times. Wasted work on dormant users: if only 20% of registered users are active on a given day, four fifths of your fan-out writes are pure waste — written, occupying memory, evicted, never read.
One engineering rule here gets skipped constantly: the inbox stores <post_id, user_id> and nothing else. At 16 bytes a row, 800 recent entries per user across 10 million users is 128 GB — one memory cluster. Store whole post objects at ~1 KB and it is 8 TB, 64× more. And memory is the smaller point: with IDs only, the content has a single source of truth, so an edit or a delete touches one row instead of hunting down a thousand copies.
The mirror image: store nothing in advance, and on refresh fetch the latest few items from each account the user follows, then merge. Write cost drops to the floor — one write per post — and the hotkey problem disappears entirely, because a huge following costs nothing at write time.
The bill arrives on the read side, and it is amplified: 200 followees means 200 shard queries per refresh. On the numbers above, 1,160 refreshes/s becomes roughly 230,000 backend queries/s. Worse is the tail: a scatter-gather finishes when its slowest shard finishes, so one shard doing a GC pause or hitting disk contention slows the whole refresh. More shards means a worse p99 — that is inherent to scatter-gather, not a sign of a sloppy implementation.
The book's answer is a hybrid: the vast majority of users go through push, accounts with enormous followings go through pull, and the two are merged at read time. That is easy to remember as "half push, half pull", which misses the point — what matters is that the split is decided by who posted.
Why does that split work? Because the two costs are proportional to two numbers with completely different distributions. Follower counts are extremely long-tailed (a handful of accounts have hundreds of millions; nearly everyone has a few hundred), while followee counts have a ceiling (following a few thousand accounts is already a lot, and only a few dozen of them are huge). Pulling that small tail out of push kills the hotkey outright, and the read amplification it introduces stays bounded precisely because nobody follows more than a few dozen giant accounts. This is trading on a distributional fact, not splitting the difference.
The book splits the cache into five layers, and the reason they are split is that each one changes on a completely different clock: the news feed layer (lists of post IDs), the content layer (post objects, with hot content in its own cache), the social graph layer (follow relationships), the action layer (has this user liked or replied), and the counter layer (likes, replies, follower counts).
Why not one layer? Because counters change every second while content barely changes at all. Merge them and you must set the TTL for the fastest-moving member, so content gets re-fetched from origin over and over and your hit rate is dragged down by the least stable item. Split, each gets its own policy: content cached for a long time, counters aggregated asynchronously with a few seconds of tolerated error — nobody complains that a like count was 3 seconds stale, and everybody complains that a refresh was 3 seconds slow.
Table 1 · Three fan-out strategies: whichever side holds the work is the side that pays
| Strategy | Work happens | Read latency | Write amplification | How it dies | Fits |
|---|---|---|---|---|---|
| Fan-out on write | write path | Lowest: one cache lookup, independent of followees | Highest: × follower count (≈ 46,000 writes/s here) | Hotkey: 100M followers = 100M writes per post; plus ~80% written for dormant users | Even follower distribution, reads far above writes |
| Fan-out on read | read path | Highest: M scatter-gather queries, p99 held by the slowest shard | Lowest: one write per post | Read amplification: 1,160 refreshes/s → 230,000 queries/s | Bounded followee counts, ranking that changes often |
| Hybrid (the book's choice) | split by publisher | Low: one read plus a few pulls, then merge | Medium: the long tail is lifted out of push | Complexity: two paths, threshold flapping, cross-path duplicates | The default answer in real systems |
Table 2 · Four questions a hybrid must answer before it ships
| Question | Usual answer | Cost / trap |
|---|---|---|
| Where does the threshold go | By follower count (in practice somewhere between tens of thousands and hundreds of thousands, depending on what your fan-out cluster can absorb), not by a business label like "verified celebrity" | Accounts near the line flip back and forth; you need hysteresis — promote at 100k followers, demote only below 80k |
| What happens to already-distributed posts when an account crosses | Change the path for new posts only; neither reclaim nor backfill what is already fanned out | For a while the same author is partly in inboxes and partly pulled, so the read path must dedupe by post_id or users see doubles |
| Which layer merges | The feed-building service merges the inbox list with the latest N from each huge account | One extra fetch per read, growing with how many huge accounts a user follows — usually capped |
| Do dormant users get pushed to | Filter by last-login time; keep long-dormant users on pull only | Saves the bulk of the writes (~80% in this scenario) at the price of a visibly slow first refresh when someone returns |
One more question that always comes up: should fan-out go through a message queue? Yes. Synchronous fan-out makes the posting endpoint's latency proportional to friend count — a user with 5,000 friends posts noticeably slower than everyone else. Enqueue instead and the endpoint costs 1–5ms while the fan-out proceeds in the background. The price is that the feed is no longer consistent in real time: followers see the post seconds to minutes apart. In a reverse-chronological feed that is usually fine; in a live interactive context it is not.
This skeleton is not a teaching model — it is what feed teams actually run. Asked about a news feed in an interview, four points will carry you: split the two flows, know what each side's cost is proportional to, know that the hybrid's routing key is the publisher, and name the two traps you will certainly hit — cross-path duplicates and threshold flapping.
5,000 tweets/s (peaking near 12,000). Fan-out inverts the write/read ratio completely — the real-world version of this chapter's "a read-heavy product becomes a write-heavy system". InfoQ, "Twitter Timeline Scalability" · Raffi Krikorian, QCon 2012 ↗140ms, five times faster than the previous Sensei system, with an index 20× larger on half the servers. Their stated reason is practical: pull lets relevance and ranking experiments iterate faster, because nothing materialised has to be backfilled. LinkedIn Engineering, "FollowFeed: LinkedIn's Feed Made Faster and Smarter", 2016 ↗40:1 in this scenario). Plan capacity against fan-out writes, not refreshes — this is the single most common estimation error here.post_id, users see duplicates — the classic production bug after a hybrid ships.post_id and move on. Chasing end-to-end exactly-once only makes the design more complicated, not more correct.1. The core claim: designing a feed means deciding whether the assembly work happens on the write path or the read path. The cost never disappears, it only relocates.
2. Split the system into publishing and building first; every fan-out argument is an argument about how work divides between those two flows.
3. Write cost ∝ followers, read cost ∝ followees. In this scenario: push ≈ 46,000 writes/s, pull ≈ 230,000 queries/s.
4. Adopt push and a read-heavy product becomes a 40:1 write-heavy system — capacity must be planned against fan-out writes.
5. Push dies of hotkeys (100M followers = 100M writes; ~17 minutes even at 100k writes/s) and of work done for dormant users; pull dies of read amplification and tail latency (p99 owned by the slowest shard).
6. The hybrid is the answer, but the routing key is the publisher: follower counts are long-tailed, followee counts are capped — lifting the tail into pull trades on that asymmetry rather than splitting the difference.
7. Three engineering rules: inboxes hold <post_id, user_id> only (128 GB vs 8 TB, and one source of truth), fan-out goes through a queue (posting latency stops scaling with friend count, at the price of seconds of inconsistency), and reads dedupe by post_id.
8. Cache in five layers (feed / content / graph / action / counters), because their change rates differ by orders of magnitude; merged into one, the hit rate is dragged down by the counters.