Fan-out Strategies for Feeds

A news feed looks simple: show me the latest posts from the people I follow. The difficulty is in who does the work, and when. Every time someone posts, thousands of other people's feeds should include that post, and every time someone opens the app, their feed has to appear instantly. You can do the work when a post is written or when a feed is read, and the choice, with its numbers, is one of the best-known trade-offs in system design.

Think of how a newspaper reaches its readers. In one model, the paper is printed and a copy is delivered to every subscriber's door, so reading is instant, but the printer and delivery person do a lot of work for every issue. In the other, there are no deliveries: readers walk to the newsstands of everyone they like and assemble their own pile, which costs the publishers nothing but makes reading slow. Most large papers combine the two: home delivery for ordinary subscribers and a stand for the special editions that millions want.

• -Delivering a copy to every door when it is printed is fan-out on write (push).
• -Readers assembling their own pile at read time is fan-out on read (pull).
• -Doing push for ordinary accounts and pull for very popular ones is the hybrid.

The moment someone posts, the system copies that post into the precomputed feed list of every follower. Reads are then extremely cheap: just fetch the ready-made list. For someone with 200 followers, a post is 200 small writes, which is nothing. The catch is the celebrity problem. A user with 50 million followers turns one post into 50 million writes. If the fan-out workers can do 100,000 writes a second, that is 50,000,000 / 100,000 = 500 seconds, over eight minutes, before the last follower sees the post, and the burst delays everyone else's updates queued behind it.

Nothing is precomputed. When a user opens their feed, the system fetches recent posts from everyone they follow and merges them on the spot. Writes stay cheap no matter how many followers someone has. But reads become expensive: a user who follows 1,000 accounts needs up to 1,000 lookups and a merge on every refresh, and reading is the operation that happens most often and must be fastest.

Most large feed systems use both. Ordinary accounts are pushed: their posts are fanned out on write, so most of what a reader sees is already waiting in their list. Celebrity accounts above some follower threshold, say 100,000, are not pushed. Instead, when a reader opens their feed, the system takes their precomputed list and merges in the recent posts of the few celebrities that reader follows, which is cheap because a person follows tens of celebrities, not thousands.

The diagram shows the two paths: ordinary posts go through the fan-out worker into followers' feed caches, and celebrity posts are pulled and merged in at read time.

• -Store post ids, not whole posts, in feed lists. A list entry is a few bytes, and the posts themselves are fetched from a cache when displayed.
• -Cap each list at the latest few hundred entries. Almost nobody scrolls further, and older posts can be fetched on demand.
• -Skip users who have not opened the app in a month. Their feed is built when they come back, which saves a large share of the write load.
• -Fan out through a queue and workers, so a spike in posting is smoothed out, as in the asynchronous module.