Fan-Out and the Twitter Timeline Problem

Build a feed by merging at read time or by copying each post to followers at write time; how Twitter chose between them in 2012, and why accounts with huge followings need a hybrid.

Overview

Fan-out means one event has to reach many places. In a social app, one post has to appear in the home timeline of every follower. You can do that work when someone reads a timeline, or when someone posts. Which is cheaper depends on the load parameters, mainly how often people read compared with how often they post, and how many followers each poster has.

Twitter's home timeline is the classic worked example. In a 2012 talk, Twitter's slides gave about 400 million tweets a day, which is about 5,000 new tweets a second on an average day (over 12,000 during big events), against more than 300,000 home timeline queries a second. Reads outnumbered writes by roughly 60 to 1.

Two ways to build a home timeline

With fan-out on read (pull), a post is written once. When a user opens their timeline, the system looks up everyone they follow, fetches their recent posts and merges them by time. With fan-out on write (push), each new post is copied into a precomputed timeline list for every follower. Reading a timeline is then a single lookup of one list.

Cost of a post — One insert — One insert per follower
Cost of a read — Look up every followed account and merge — Read one precomputed list
Read latency — Grows with how many accounts you follow — Low and steady
Freshness — Always current — Delayed until the fan-out finishes
Storage — Posts only — Posts plus a copy of each post ID per follower
Works well when — Writes are common and reads are rare — Reads far outnumber writes

Doing the arithmetic

The choice comes down to multiplying rates by fan-out degree. The follower and following counts below are assumptions for the example; the two rates are rounded from Twitter's 2012 slides.

Push — 1,000,000 small list inserts — Background workers, off the user's path
Pull — 60,000,000 author lookups to merge — On every timeline read, while the user waits

Push moves the heavy work off the read path and into background workers, where a delay of a few seconds is acceptable. With reads 60 times more common than writes, that is the better trade on average. Twitter moved from pull to push for this reason.

How Twitter's push design worked in 2012

According to the talk, each user's home timeline was a list in a large Redis cluster, replicated on 3 machines. A list held at most 800 entries, and each entry was small: the tweet ID, the author's user ID, and a few bytes of flags such as retweet or reply. Timelines were kept in memory only for users active in the last 30 days; an inactive user's timeline was rebuilt from the social graph on their next visit.

Storing IDs instead of whole tweets keeps each copy tiny, and capping the list bounds memory per user. The cost shows up on the read side as a second step, called hydration: turning IDs into full tweets with a batch lookup.

The celebrity problem and the hybrid

Push breaks down for accounts with enormous followings. One post from an account with tens of millions of followers means tens of millions of inserts. Twitter aimed to finish fan-out within 5 seconds, but for the largest accounts it could take minutes, and users sometimes saw replies before the tweet being replied to.

The fix is a hybrid. Most accounts are pushed as usual. Accounts above a follower threshold are not fanned out; their recent posts are fetched when a follower reads a timeline and merged with the precomputed list. A typical user follows only a handful of such accounts, so this merge stays small.

Ordinary accounts — Push at post time — Few followers, cheap to copy; fast reads for everyone
Very large accounts — Pull at read time and merge — Avoids tens of millions of inserts per post
Inactive readers — Nothing precomputed; rebuild on return — Saves memory for users who are not reading

The same trade-off elsewhere

Notifications — One event to many subscribers — Push through a queue, batched per recipient
Group chat — One message to every member — Push for small groups; large channels are read from a shared log
Search indexing — One record change to many index entries — Push asynchronously, accept a short delay
Parallel search or query — One query to many shards — Fan-out at read time; watch the slowest shard

What you will be able to do

Explain fan-out on read and fan-out on write, and what each costs.
Choose between them from load parameters, with the arithmetic done out loud.
Describe Twitter's 2012 timeline design and the celebrity problem it hit.
Design a hybrid, including where the follower threshold sits and how reads merge.

Key concepts

Fan-out: One event that must reach many destinations, such as one post reaching every follower’s timeline.
Fan-out on read (pull): Store each post once and assemble the timeline when it is read by merging posts from followed accounts.
Fan-out on write (push): Copy each new post into a precomputed timeline for every follower, so reading is one lookup.
Hybrid fan-out: Push for ordinary accounts, pull and merge at read time for accounts with huge followings.
Write amplification: One logical write causing many physical writes. In push fan-out, one post becomes one insert per follower.
Hydration: Turning a list of IDs from a precomputed timeline into full objects with a batch lookup.
Load parameters: The numbers that decide the design here: posts per second, timeline reads per second and the follower distribution.

When to use it

Designing a news feed, timeline or activity stream in a system design interview.
Deciding whether to precompute results at write time or compute them at read time.
Handling skew: a few accounts, keys or channels with vastly more subscribers than the rest.
Sizing a background fan-out pipeline from post rates and follower counts.

Interview questions

How would you design a home timeline for a Twitter-like service?
When is fan-out on read the better choice?
How do you choose the follower threshold for the hybrid, and what goes wrong at the boundary?
What happens if the fan-out pipeline falls behind?