Design a news feed

Interview 3: Design a news feed

The classic closer: design the Twitter or Instagram home feed.

Step 1, requirements. Functional: users follow others, post, and see a reverse-chronological feed of posts from everyone they follow. Non-functional: the feed must load fast (under ~200 ms), it is extremely read-heavy, and slightly delayed posts are acceptable, an explicitly eventually consistent surface (unit 7).

Step 2, estimation. Reuse lesson 9-1 wholesale: 10M DAU, 2 posts each, 100 feed loads per post gives ~1,200 peak writes/sec and ~115,000 peak reads/sec. Read-heavy by 100x.

The core question. When Ada opens her feed, where does it come from? There are exactly two pure strategies, and the whole interview lives in their tradeoff:

• Fan-out on read: store nothing extra. On feed load, fetch recent posts from all ~400 people Ada follows and merge them, every single time
• Fan-out on write: precompute. When someone posts, push the post ID into a stored feed list for each of their followers. Feed load becomes one cheap read

Where fan-out on write breaks

A normal user's post writes to 200 follower feeds, and a celebrity's does not.

average_followers = 200
celebrity_followers = 100_000_000
print("Average user posts ->", average_followers, "feed writes")
print("Celebrity posts ->", celebrity_followers, "feed writes")
print("At 1000 writes/sec that takes", celebrity_followers // 1000 // 3600, "hours")

Output

Average user posts -> 200 feed writes
Celebrity posts -> 100000000 feed writes
At 1000 writes/sec that takes 27 hours

One tweet turning into 100 million queued writes is the hot key problem from lesson 5-2 wearing a new outfit. The same concentration, in the write direction this time.

The 27 hours is what kills the pure strategy, and it is worth stating as a user-visible failure. A post that takes a day to reach followers is not delivered, and followers at the end of the queue see it after it stopped being relevant.

Look at the ratio between the two numbers, which is 500,000 to 1. No amount of tuning closes a gap that size, so a strategy that works beautifully for one case cannot be stretched to cover the other.

The queue also does not save you here, and that is the important distinction from unit 6. A queue absorbs bursts of work that capacity can eventually clear, and this is a sustained deficit, which is exactly the growing-queue alarm from lesson 6-1.

Note that the write cost is only half the problem. A hundred million feed lists each gaining an entry is also a hundred million cache invalidations or updates, so the cost lands on the cache tier too.

The hybrid answer

Each pure strategy fails at one end:

So production systems use the hybrid: fan out on write for the 99.9% of users with normal follower counts, using unit 6 queues and workers to spread the writes. For the few accounts above a follower threshold, do not fan out. Instead, merge celebrity posts in at read time, fetching them from a hot cache (lesson 5-2, the same fix as always).

Feed lists live in Redis or a wide-row store keyed by user, capped to the newest few hundred entries. Posts themselves live once in the sharded post store, feeds hold only IDs.

The read-side cost of fan-out on read

Ada follows 400 accounts, and the merge examines the 10 newest posts from each.

follows = 400
posts_checked_per_follow = 10
candidates = follows * posts_checked_per_follow
print("Feed read must merge", candidates, "candidate posts")
print("Fan-out on write instead reads 1 precomputed list")

Output

Feed read must merge 4000 candidate posts
Fan-out on write instead reads 1 precomputed list

Four thousand candidate posts fetched and merged to produce perhaps 20 visible ones is the cost of computing a feed on demand. The ratio of work to output is what makes this strategy fail the 200 ms requirement.

The number is worse than it looks because those 400 accounts are spread across shards. This is the scatter-gather query from lesson 5-1, so the read touches most of the cluster and is as slow as its slowest shard.

Multiply it by the read rate to see the real problem. At 115,000 peak feed loads per second, 4,000 candidates each is 460 million post fetches per second, which no cluster serves.

Fan-out on write moves that work to post time, where it is done once instead of once per reader. A post read by a thousand followers is merged once rather than a thousand times, which is the entire economic argument.

That is the read-versus-write trade from lesson 4-1's indexes, at architecture scale. Precompute at write time to make reads cheap, and accept that writes now cost more, which is the same bargain an index strikes.

Is a 20-second fan-out delay a broken design

No, the requirements accepted eventual consistency for feeds, and this is exactly that trade.

Step 1 declared feeds eventually consistent, and this 20-second convergence is that choice made real. The design is behaving as specified rather than failing.

Nobody knows a post they have not seen is missing, which is the property that makes the staleness harmless. A feed with 19 posts instead of 20 is indistinguishable from a feed that had 19 posts, so there is no detectable error.

The one person who can detect it is the author, which is the read-your-own-writes case from lesson 4-3. Showing the poster their own post immediately, usually by inserting it client-side, is the standard fix and costs nothing.

Compare lesson 7-1's rule, which is to name the surfaces where staleness harms, meaning money and permissions, and spend consistency there rather than on timelines. Consistency has a price, and paying it for a feed buys nothing a user can perceive.

Requirements written early are what make this answer defensible. Without step 1, a 20-second delay is a bug you are explaining away, and with it, the delay is a documented consequence of an agreed tradeoff.

The technique that answered every hot-anything problem

The answer is caching.

Every hot-anything problem in this course resolved to the same move, which is that the most-requested data earns a spot in the fastest store. Unit 3 introduced it, and lesson 5-2 aimed it at hot keys.

It answered four different-looking problems with one idea. A viral link, a celebrity profile, a flash-sale page, and celebrity posts merged at read time are all concentration of reads on a small amount of data, and concentration is the condition a cache is built for.

That is worth generalizing, since it is the most reusable pattern here. Load concentrating on few items is good news rather than bad, because it means a small fast store can absorb a large share of traffic, and the skew that breaks sharding is the skew that makes caching work.

You now own the full toolkit: stateless services behind load balancers from unit 2, caches from unit 3, replicated and sharded databases from units 4 and 5, queues with idempotent workers from unit 6, consistency chosen per feature from unit 7, observable services from unit 8, and a repeatable method for assembling them under interview pressure from units 9 and 10.

The through-line across all of it is smaller than the list suggests. Measure before fixing, name the bottleneck, start simple, and state what each choice costs, which is the reasoning the techniques hang on.

Go design something.