Skip to content

Fan-out on write and on read

Fan-out is spreading one message or update to its many readers. Doing it when the item arrives makes reads cheap; doing it when a reader asks makes writes cheap. The right choice depends on audience sizes and the read-to-write ratio.

On this page

What it is

Fan-out, in messaging, means delivering one message to many destinations, often in parallel, without the sender waiting on each one. In a feed or a chat system the term names a design choice: the work of getting an update in front of each of its readers has to happen somewhere, and you decide whether it happens when the update is written or when a reader asks for it.

Fan-out on write (push) does the work at write time. Twitter's 2012 timeline design is a well-documented example: a new tweet goes to a fan-out daemon that asks the social graph service for the author's followers and inserts the tweet's ID into a Redis list kept for each recipient's home timeline, keyed by recipient and pipelined 4,000 destinations at a time. A list entry holds the tweet ID, the author's user ID and 4 bytes of flags, not the text; each home timeline is capped at 800 entries, and the text is fetched by ID in one parallel multiget when the timeline is read. The append used RPUSHX, which adds to a list that already exists, so an account that had not logged in for 30 days had no cached timeline and received no stored insert. Reading a home timeline was then one list fetch: more than 300,000 timeline reads a second against about 6,000 writes a second.

Fan-out on read (pull) stores each item once, under its author or its conversation, and assembles the reader's view on request by fetching from each source and merging. The slides draw the two as mirror images: one is O(n) write and O(1) read, the other O(1) write and O(n) read, where n is the number of followers on one side and the number of followed accounts on the other. The same system's search path worked the pull way, with a tweet indexed on one machine and a query at read time asking each shard, then sorting and merging the results. Pull was also the fallback for the push path: when a user's timeline had fallen out of the Redis cache, it was reconstructed by looking up who they follow and reading each of those accounts from disk.

CostOn write (push)On read (pull)

Work happens

Once per recipient, at write time

Once per source, at request time

Copies stored

One ID per recipient's list

One, under the author or the chat

Who waits

Recipients, until the fan-out reaches them

The reader, while sources are merged

Grows with

The author's audience

The number of accounts the reader follows

The hybrid. Fan-out time grows with the audience. The 2012 figures were about 30 billion timeline deliveries a day, a median of 3.5 seconds to reach one million followers, and up to 5 minutes at the 99th percentile for an account with 31 million followers. That lag produced visible bugs: a reply could show up in a follower's timeline before the tweet it answered. The fix shown in the slides is to leave the largest accounts out of the fan-out and, when a follower opens the app, read the follower's precomputed timeline and the big account's own timeline, then merge the two. Most updates stay cheap to read, and the few expensive authors are paid for at read time by the readers who follow them.

When to use it

Fan out on write when reads greatly outnumber writes and a read has to be fast. The 2012 timeline numbers show the shape: around 300,000 timeline reads a second against about 6,000 writes, roughly fifty reads for each write, so paying once per recipient at write time and almost nothing at read time was the better trade.

Fan out on read when the reader pulls from few sources, when reads are rare compared with writes (an audit log, or a search index that is written constantly and queried now and then), when the view must be ranked or filtered across sources at request time anyway, or when the author's audience is huge and unbounded. A one-to-one or group chat is a clear case: the reader opens one conversation, so a single log per chat, read from the end, is the natural store.

Treat storage and delivery as two separate decisions. Storing a group message once per chat removes the per-member write, but when members are online the system still has to push the message to each connected device, and a member with several devices gets one push per device. How those pushes travel between servers is its own choice: a channel keyed by the chat carries one publish per message, and each receiving server maps the chat to the connections it holds; a channel keyed by the user costs one publish per member but keeps routing simple, and it gives you one place per person to apply ordering across their chats, provided the transport in between preserves it. Routing messages between stateful servers covers that part.

When you pick the hybrid, say what the threshold is based on. We'd cut on follower count, since that is what the fan-out cost grows with, and a strong answer also names what happens when an account crosses it in either direction: when it moves into the write path, its followers' timelines can be backfilled or can simply start receiving new items, and when it moves out, its updates are dropped from the write path and picked up by the read-time merge.

When not to

Don't precompute timelines before you need them. At small scale, one indexed query over items by the accounts a reader follows, ordered by time, is fan-out on read and is the right start. A precomputed timeline is a second copy of the data to keep in step with the first, usually through a worker and a queue, and it brings a new failure mode where an update shows up in some followers' feeds before others. Build it when read latency or read load says so, not before.

Don't fan out to readers who won't read. The 2012 timeline service kept a cached timeline for accounts that had logged in within 30 days and skipped the rest, so dormant accounts cost no inserts and no memory; a design that materializes a timeline for each dormant account spends inserts and memory on lists that may not be opened before their contents are stale.

Don't fan out copies of content that changes. If items are edited or deleted often, each change under fan-out on write has to reach each recipient's copy. The timeline lists described above held tweet IDs with the text fetched at read time, so an edit to the text touched one record; a delete still has to be removed from each list or filtered out when the timeline is read.

Don't fan out on read for a reader who follows thousands of sources and expects a feed in a few milliseconds: merging thousands of per-author lists on each open is the O(n) read. If you then cache the merged result and update that cache as new items arrive, you have arrived at fan-out on write by another route. The 2012 design took the merge path as a fallback, to rebuild a timeline that had fallen out of cache, not as the normal read.

Compared

StrategyWrite costRead costPick it when

Fan-out on write

One append per recipient; seconds for an audience of a million

One list fetch

Reads dominate, audiences are bounded, reads must be fast

Fan-out on read

One write

One fetch per followed source, then a merge

Few sources per reader, rare reads, huge or unbounded audiences, content that is ranked at read time, or a system still small enough for one indexed query

Hybrid

One append per recipient for most authors; one write for the largest

One list fetch plus a merge of the few large authors

Most authors are small but a few have audiences that make write-time fan-out too slow

In a picture

Author writesWrite APIItem store

Step 1 of 3

Store the update

An update arrives through the write API and is stored once. Nothing has reached a reader yet.

How to say it in an interview

The common mistake

Quiz

Under pure fan-out on write, an account with 30 million followers publishes an update. What happens?
A group chat stores each message once in a per-chat log instead of in each member's inbox. Which cost disappears, and which stays?
Why append to a recipient's timeline list with a command that adds to an existing list but creates nothing?
Which situation favors fan-out on read?

Questions that use this

Hear it in

Related

Sources

  1. Raffi Krikorian, Timelines at Scale (QCon SF 2012 slides, on SlideShare)
  2. High Scalability: The Architecture Twitter Uses to Deal with 150M Active Users, 300K QPS
  3. Wikipedia: Fan-out (software)
Sign in to report a mistake