Design a News Feed medium
The prompt
Build the home timeline: a user opens the app and sees a feed of recent posts from everyone they follow, newest-ish first. The classic Twitter/Instagram/Facebook design question — and the one that hinges on a single brilliant trade-off.
Requirements
- Functional: publish a post; view a feed of posts from followed accounts.
- Non-functional: very read-heavy, low feed-load latency (feed must open fast — sub-200 ms), eventual consistency is fine (a post appearing a few seconds late is acceptable).
Estimation
300 M DAU, each opens the feed ~10×/day → 3 B feed reads/day ≈ 35k/s (peak much higher). Posts are far rarer than reads. Read-dominated → we want feed reads to be cheap, even if posts get more expensive.
The central decision: fan-out on write vs read
This is the whole problem. When does the work of assembling a feed happen?
| Fan-out on write (push) | Fan-out on read (pull) | |
|---|---|---|
| On a post | push the post into every follower’s precomputed feed | do nothing |
| On a feed read | just read your ready-made feed (fast!) | gather recent posts from everyone you follow, merge, sort (slow) |
| Great for | the common case — reads are instant | users with huge follower counts (celebrities) |
| Breaks on | a celebrity with 100 M followers → 100 M writes per post | a user who follows thousands → expensive every read |
The hybrid model (the strong answer)
Neither pure approach survives reality. The production answer is hybrid:
- Most users: fan-out on write. Their posts push to followers’ feed caches; feed reads are instant.
- Celebrities (huge follower counts): fan-out on read for their posts. Don’t push to 100 M feeds. Instead, when a follower loads their feed, merge their precomputed feed with the celebrity’s recent posts at read time.
The celebrity problem is the heart of this question. Pure push dies on a celebrity’s post (100 M writes, a “fan-out storm”). Pure pull dies on every feed read for users who follow many. The hybrid splits the difference: cheap push for the 99.9%, lazy pull for the handful of mega-accounts. Naming this trade-off — and the threshold at which you switch a user from push to pull — is exactly the senior signal interviewers want.
High-level design
Deep dives
- Feed storage: store post IDs in each user’s feed cache (a Redis list, capped at ~hundreds), not full posts — hydrate the actual post content from the posts DB/cache at read time.
- Ranking: chronological is simplest; real feeds use ML ranking. Mention it as an extension, don’t get lost in it.
- Fan-out worker pool: the queue + workers smooth the spike when a popular (non-celebrity) user posts.
Analysis
- Feed read: ~O(1) cache list read + a bounded merge for celebrities → fast.
- Post write: O(followers) for push users (async via queue); O(1) for celebrities (deferred to read).
Same skin
- Notification feeds, activity streams, Twitter timeline, Instagram feed — all the same push/pull/hybrid trade-off.
- The merge step is a k-way merge with a heap (Day 7 / Day 26) — merging time-sorted streams from multiple sources.
- Message queues doing the async fan-out is the same decoupling pattern as the notification service.