Twitter Timelines: Fan-Out on Write, Except for Celebrities
also called Timeline Fan-Out, Hybrid Fan-Out
Precomputing every user's timeline at write time is fast to read and impossible for accounts with millions of followers, so the two approaches are combined.
The problem
A social timeline can be assembled two ways, and both fail at scale for opposite reasons.
Fan-out on read: when a user opens their timeline, query the posts of everyone they follow and merge. Writes are trivial. Reads are expensive and get worse the more accounts someone follows, and timelines are read constantly.
Fan-out on write: when someone posts, immediately insert it into the precomputed timeline of every follower. Reads become a single sequential fetch — very fast. But a post from an account with 50 million followers requires 50 million writes, which is a write amplification problem that cannot be solved by adding capacity.
What they did
The publicly described approach is a hybrid. Ordinary accounts fan out on write into per-user timeline caches, so the overwhelming majority of reads are a cheap fetch from a precomputed list. High-follower accounts are excluded from fan-out; their posts are fetched at read time and merged into the timeline when it is requested.
The cost is paid where it is cheapest in each case: ordinary posts are written to many timelines cheaply, and celebrity posts are read from one place by many people.
The trade-off
The system now has two code paths with different consistency and latency characteristics, and a threshold that decides which applies. Accounts near the threshold behave inconsistently, and the merge at read time must reconcile two sources ordered differently.
There is also a substantial storage cost: precomputed timelines are a materialised view of the same underlying data, duplicated per user.
The transferable lesson
This is materialised views with an escape hatch, and the pattern generalises far beyond social feeds. Precompute the common case; handle the pathological tail differently.
The same shape appears in: search indexes that precompute for common queries and fall back for rare ones; analytics with pre-aggregated rollups plus on-demand queries for unusual cuts; caches with a bypass for the very large object; and notification systems.
The design question to carry away: what is the distribution of your fan-out? If it is uniform, pick one strategy. If it is heavily skewed — and most real-world distributions are — a single strategy will be wrong at one end, and the hybrid is the answer.