News Feed / Timeline
Aggregate and rank posts per user: fan-out on read vs write, the celebrity hot-partition, a hybrid delivery path, denormalized ranking signals, and a bounded materialized timeline.
~30 min · intermediate
Problem & Requirements
Build the home timeline: given a user, return a ranked list of recent posts from the accounts they follow. Posts are written by authors, the follow graph decides whose posts reach whom, and reads vastly outnumber writes — most users scroll far more often than they post. The query "show me my feed" is the hot path, and it has to stay fast no matter how many accounts a user follows or how many followers an author has.
The entire design turns on one decision made early and re-litigated constantly: when does the work of assembling a feed happen — at write time or at read time? Pushing a post into every follower's precomputed feed on write makes reads trivial but punishes authors with many followers; assembling a feed by querying every followee on read makes writes trivial but punishes users who follow many accounts. This is the fan-out on write vs read tradeoff, and neither pure form survives contact with a real follow graph. The precomputed feed is a materialized view, the accounts that break the write path are a hot-partition problem, and the trick that keeps ranking cheap is denormalization. Those four principles are the whole prototype.
Functional
post(author, content)adds a post;timeline(user, limit)returns that user's ranked recent feed.- A timeline reflects posts from followed accounts, ordered by a relevance score rather than strict time.
- Unfollows and deletes eventually stop appearing, without rewriting every affected feed synchronously.
Non-functional (back-of-envelope, large social graph)
| Quantity | Target | What it forces |
|---|---|---|
| Read : write ratio | ~100 : 1 | Optimize the read path first; spend write-time work to make reads cheap |
| Timeline read p99 | < ~100 ms | Feed must be largely precomputed; no synchronous fan-out across hundreds of followees |
| Follower count | median ~hundreds, max ~10⁸ | A flat fan-out-on-write cost ranges from trivial to catastrophic — the celebrity problem |
| Fan-out write cost | F writes per post | A post by a 100M-follower account is 100M feed writes if done naively |
| Materialized feed length | ~800 entries/user | Bounds memory and write cost; older entries fall off rather than accumulate |
| Following count | up to thousands | A pure pull would query thousands of authors per read — too slow alone |
The asymmetry in the follower-count row is the crux. Most authors are cheap to fan out, so push works for them. A small number of accounts have enough followers that a single post would trigger tens of millions of feed writes, turning one author into a hot partition that stalls the write pipeline. The system that ships handles those accounts differently from everyone else, which is step four.
Design
Five components, each tied to the principle behind it:
- Follow graph —
followers(author)andfollowing(user), plus a follower count per author. The count is what the fan-out decision keys on. - Post store — authoritative posts by id, and a per-author recent-posts list for the pull path.
- Materialized timelines — a precomputed per-user feed (a materialized view) that the write path appends to, so a read is a slice of an already-assembled list rather than a graph traversal.
- Fan-out service — on each post it consults the author's follower count and chooses delivery: push into follower feeds for ordinary accounts, skip for high-follower accounts whose posts are pulled at read time instead. This hybrid is the practical resolution of fan-out on write vs read and the answer to the hot-partition row above.
- Read-time assembler and ranker — merges the pushed feed with pulled celebrity posts, scores each entry, and returns the top slice. Scoring reads only fields carried on the feed entry itself, denormalized at fan-out time, so ranking never fans out a second wave of reads to the post store or graph.
Three real systems map onto this. Twitter's timeline is the canonical hybrid: fan-out on write into per-user Redis timelines for normal accounts, pulled-at-read merging for high-follower accounts, feeds capped at roughly 800 entries. Instagram runs a similar push-based delivery with heavier machine-learned ranking on top. Facebook's News Feed leans further toward pull — an aggregator gathers candidate stories at read time and runs multi-pass ranking over them, backed by the TAO graph store — which is the useful counterpoint to "precompute everything." The choice between them is mostly a bet on read latency versus ranking freshness.
Build it
The simplest correct design does all the work at read time. A timeline is built by asking every account the user follows for its recent posts and merging them by time. Writes are trivial — a post just lands in its author's list — and the feed is always current. This is pure fan-out on read. It falls over on the read side: a user following two thousand accounts triggers two thousand lookups per feed view, and reads outnumber writes a hundred to one, so this spends effort in exactly the wrong place.
Flip the work to write time. When an author posts, append the post into every follower's precomputed feed, so a read is just the tail of an already-built list. The per-user timeline is a materialized view maintained incrementally on each write. Reads are now O(limit) regardless of how many accounts the user follows, which is the right shape for a read-heavy workload. The cost moved, not vanished — it's now on the write path, and step three shows where that becomes unbearable.
Fan-out on write assumes every author has a manageable follower count. The follow graph doesn't. An account with tens of millions of followers turns a single post into tens of millions of feed appends — a burst that monopolizes the write pipeline and makes that one author a hot partition. Worse, those writes are mostly wasted, since many followers won't open their feed before the post ages out. Surfacing the follower count on the post path is the measurement that justifies treating these accounts differently.
Resolve it by splitting authors at a follower-count threshold. Ordinary accounts fan out on write as before. High-follower accounts skip fan-out entirely; their posts stay in the author's own list and are pulled in at read time and merged with the pushed feed. Each post is delivered the cheap way for that author, and a read does a small bounded pull (a user follows few celebrities) on top of an already-materialized base. This hybrid is how the fan-out tradeoff is actually resolved in production and what defuses the hot partition.
A timeline isn't strict reverse-chronological — entries are scored by recency, the viewer's affinity for the author, and engagement. The naive way to score would look each signal up at read time, fanning out a fresh wave of reads to the graph and post store and undoing the latency win. Instead, denormalize the ranking inputs onto the feed entry when it's created, so scoring reads only local fields. The entry carries a snapshot of what ranking needs; it can drift slightly, which is an acceptable trade for ranking that touches nothing but the entry itself.
The materialized timeline can't grow forever, and it has to cope with posts that get deleted and follows that get dropped after the entry was already pushed. Cap each feed at a fixed length so writes and memory stay bounded, dropping the oldest entries. Rather than synchronously scrubbing millions of feeds on every delete or unfollow, filter those out at read time against a tombstone set and the current follow graph — the materialized view stays cheap to write, and correctness is restored on read. Author display fields are denormalized onto the entry too, so rendering needs no extra lookups.
Tradeoffs
| Decision | What it buys | What it costs |
|---|---|---|
| Pure fan-out on read | Trivial writes; always-fresh feed | Read cost scales with following count; wrong for read-heavy load |
| Pure fan-out on write | O(limit) reads from a materialized view | Write cost scales with follower count; celebrities create write storms |
| Hybrid push/pull | Cheap delivery per author; bounded read-time pull | A threshold to tune; read path now merges two sources |
| Denormalized ranking signals | Scoring touches only the entry; no read fan-out | Signals can be stale; more bytes per entry; updates don't propagate |
| Bounded feed length | Predictable write cost and memory | Deep history isn't in the materialized view; must fall back to pull |
| Lazy delete/unfollow filtering | No synchronous scrub of millions of feeds | Tombstone set to maintain; filtered entries still occupy feed slots until evicted |
Scaling it up
The toy omits most of what makes this hard at scale. The big gaps:
Where the materialized feeds actually live. In-process lists stand in for what Twitter keeps as per-user timelines in Redis, sharded across many machines and replicated. Fan-out on write becomes a distributed job: a post enqueues a fan-out task that a fleet of workers spreads across the follower set, with backpressure so a burst doesn't overwhelm the timeline store. The push is asynchronous, so "post" returns before fan-out finishes.
The threshold is a gradient, not a line. A single celebrity cutoff is crude. Real systems consider the viewer too — a follower who never opens their app shouldn't receive eager fan-out at all — and some defer fan-out for inactive users entirely, materializing their feed only when they return. The decision is per (author, follower) pair, informed by activity, not a global constant.
Ranking is a pipeline, not a formula. The linear score here is a placeholder for multi-stage ranking: cheap candidate generation, then a heavier machine-learned model over hundreds of features, then business-rule re-ranking (diversity, ads, freshness). Facebook's News Feed runs several passes at read time precisely because precomputing a final order would freeze ranking that needs to react to fresh signals. The denormalization principle still holds — features get attached to candidates — but the model and feature store are their own systems.
Denormalized signals need a refresh path. Snapshotting like counts and affinity onto entries means they drift. Production systems either accept bounded staleness, periodically refresh hot entries, or update on read for the top slice only. The consistency model for these signals is a deliberate choice, not an oversight to fix.
The graph itself is a hot-partition problem. followers(author) for a celebrity is a huge list that has to be paginated and cached, and the social graph is its own distributed store (Facebook's TAO exists for exactly this). Reading and fanning out across a 100M-entry follower set is a streaming, chunked operation, not a single list traversal.
This is the first feed-and-social prototype, and it leans on the storage prototypes underneath it: the materialized timelines want a fast store like the distributed cache, and the post and graph stores want the document-database and time-series patterns from earlier. The natural next steps are a dedicated fan-out service prototype (the async, backpressured, sharded write pipeline this lesson keeps synchronous), a ranking pipeline prototype that builds the candidate-generation-then-model stages sketched above, and a social graph store prototype for the follower/following access patterns and their hot partitions. Each extends this foundation set without re-covering the delivery tradeoff settled here.
References
- Twitter timelines — the canonical hybrid fan-out and Redis-backed materialized timelines (overview of the architecture and the celebrity exception): https://blog.twitter.com/engineering/en_us/topics/infrastructure/2017/the-infrastructure-behind-twitter-scale
- Facebook TAO — the graph store behind News Feed reads: https://www.usenix.org/system/files/conference/atc13/atc13-bronson.pdf
- Instagram engineering on feed ranking — push delivery with machine-learned ordering: https://instagram-engineering.com/
- Designing Data-Intensive Applications, ch. 1 — the original framing of the Twitter fan-out tradeoff as a system-design example.
- Foundations referenced inline: fan-out on write vs read · hot-partition handling · materialized views · denormalization