Design a News Feed
Design the home feed of a social app: users follow others and see their posts, newest or most relevant first. The core decision is fan-out on write vs fan-out on read, and how to handle accounts with millions of followers.
In a nutshell
- Fan-out on write pushes each new post into every follower's feed cache: fast reads, expensive for big accounts.
- Fan-out on read builds the feed when it is opened by merging followees' recent posts: cheap writes, slower reads.
- Real systems use a hybrid: push for normal accounts, pull for celebrities at read time.
- Store feeds as lists of post IDs in a cache; hydrate post content and counts separately.
Requirements
- Functional: publish a post; follow users; see a home feed of followed users' posts, newest first (ranking optional), with pagination.
- Non-functional: feed loads fast (p99 under a few hundred ms); a new post appears in followers' feeds within seconds; highly available (a slightly stale feed is fine).
Estimates
Assume 300 million daily users, each opening the feed 10 times a day and posting once every few days, with an average of 200 followers (assumptions to agree on).
- ~35,000 / sfeed reads on average (3 billion ÷ 86,400)
- ~1,000 / snew posts
- ~200,000 / sfeed inserts with fan-out on write (1,000 × 200)
API
Publish and read
POST /posts { "text": "…", "media_ids": [] } -> 201 { "id": 98123 }
GET /feed?cursor=…&limit=20 -> { "posts": [ … ], "next_cursor": "…" }
POST /users/{id}/followData model
| Store | Holds | Key |
|---|---|---|
| Posts (sharded DB) | Post content, author, time | post_id (time-ordered ID) |
| Follow graph | Who follows whom, both directions | user_id |
| Feed cache (Redis) | Recent post IDs per user, newest first, capped at ~1,000 | feed:{user_id} |
| Counters | Likes, comments per post | post_id |
High-level design
Publishing with fan-out on write
All steps The post is saved once; fan-out workers push its ID into each follower's feed list. Reads just fetch the list and hydrate posts.
- The author publishes a post.
- The post is saved once in the posts database.
- Its ID goes onto a queue so publishing returns immediately.
- Workers look up the author's followers and prepend the ID to each follower's feed list.
- When a follower opens the app, their feed is one cache read, then the posts are fetched by ID.
Diagram as text
- The author publishes a post.
- The post is saved once in the posts database.
- Its ID goes onto a queue so publishing returns immediately.
- Workers look up the author's followers and prepend the ID to each follower's feed list.
- When a follower opens the app, their feed is one cache read, then the posts are fetched by ID.
Deep dive: push, pull or both
| Fan-out on write (push) | Fan-out on read (pull) | |
|---|---|---|
| Read cost | One cache read | Fetch and merge recent posts of every followee |
| Write cost | One insert per follower | One insert |
| Celebrity with 50 M followers | 50 M inserts per post | No problem |
| Inactive users | Wasted work on feeds nobody reads | No waste |
The hybrid: push posts from ordinary accounts; for accounts above a follower threshold, skip fan-out and merge their recent posts at read time. The merge is a k-way merge of already-sorted lists:
Merge the precomputed feed with celebrities' recent posts, newest first
import java.util.*;
class FeedMerge {
record Post(long time, String id) {}
// Each list is sorted newest first. Returns the newest `limit` post IDs overall.
static List<String> merge(List<List<Post>> lists, int limit) {
PriorityQueue<int[]> heap = new PriorityQueue<>(
(x, y) -> Long.compare(lists.get(y[0]).get(y[1]).time(), lists.get(x[0]).get(x[1]).time()));
for (int i = 0; i < lists.size(); i++) {
if (!lists.get(i).isEmpty()) {
heap.add(new int[] { i, 0 });
}
}
List<String> out = new ArrayList<>();
while (!heap.isEmpty() && out.size() < limit) {
int[] top = heap.poll();
out.add(lists.get(top[0]).get(top[1]).id());
if (top[1] + 1 < lists.get(top[0]).size()) {
heap.add(new int[] { top[0], top[1] + 1 });
}
}
return out;
}
}import heapq
from itertools import islice
def merge_feeds(lists, limit):
"""Each list holds (time, post_id) newest first. Returns the newest `limit` post IDs."""
merged = heapq.merge(*lists, key=lambda post: post[0], reverse=True)
return [post_id for _, post_id in islice(merged, limit)]Bottlenecks and trade-offs
- Fan-out lag during bursts: the queue absorbs it; posts appear a few seconds later.
- Feed cache size: cap each list (for example 1,000 IDs) and rebuild from the database for older pages.
- Hot posts: cache post bodies and counters separately, with counters updated asynchronously.
- Ranking: fetch a few hundred candidates, then score them with a ranking service before returning a page.
The last five minutes
Common mistakes
- Pure fan-out on write, ignoring celebrity accounts.
- Storing full post content in every feed list.
- Offset pagination over a feed that changes while the user scrolls; use cursors.
Interview questions
Try answering out loud before you open each one.
A user with 50 million followers posts. What happens?
Their posts are not fanned out. The post is stored once, and when followers open their feed, the service merges recent posts from the few celebrities they follow into their precomputed feed. Followers see it within a normal page load, and the system avoids 50 million writes.
Check yourself
Related topics
Further reading
- System Design Primer: Design the Twitter timeline and search Donne Martin
- heapq.merge Python documentation
Your notes
Saved in this browser as you type.
Finished this topic?
Mark it read to track your progress, then carry on with the next one.