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
Code exercise · python
Run the numbers that expose fan-out on write's weakness. A normal user's post writes to 200 follower feeds. Then a celebrity with 100 million followers posts.
The hybrid answer
Each pure strategy fails at one end:
| Strategy | Feed load | Post cost | Breaks when |
|---|---|---|---|
| Fan-out on read | Slow: merge ~400 sources | Free | Feeds must be fast (they must) |
| Fan-out on write | Fast: one list read | 1 write per follower | A celebrity posts |
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.
Code exercise · python
Your turn, the read-side cost of the pure fan-out-on-read strategy: Ada follows 400 accounts and the merge examines the 10 newest posts from each. Print the two lines exactly as shown, computing the candidate count.
Quiz
In the hybrid feed, a user posts and their 3,000 followers' feed lists are updated by queue workers over the next 20 seconds. A follower who loads their feed 5 seconds after the post might not see it yet. Is the design broken?
Problem
Final synthesis. Across the three capstones, one technique appeared as the answer to a viral link, a celebrity profile, a flash-sale page, and celebrity posts merged at read time. Name the technique (one word).