Design a news feed

Should a news feed use fan-out on write or fan-out on read?

Both, split by author. Fan-out on write copies a post into every follower’s inbox when it is made, so a read is one lookup; with 100 reads per post and 200 follows each, that costs 92.6 thousand inbox writes a second against 9.26 million lookups a second for fan-out on read. Authors above a follower line, the stars, are not fanned out: their posts stay in their own list and each reader merges them in, a handful of extra lookups per read.

What is the celebrity problem in a news feed design?

An author with tens of millions of followers turns one post into tens of millions of inbox writes. With 20 million followers that is 216 seconds of the whole fan-out fleet’s normal output, and every ordinary post queued behind it waits. The fix is the hybrid: above a follower line the post is not fanned out, and readers pull it at read time.

How do you paginate a news feed?

With a cursor, the id of the last post the reader saw, and never with an offset. Post ids that grow with time let the next page be “the newest ids below the cursor”, which a sorted list or an index answers directly. An offset counts positions, so a post deleted from the first page shifts everything and the second page silently skips one.

How much memory do the feed inboxes need?

Keep a fixed number of ids per user and multiply. At 500 ids of 8 bytes each for 200 million daily users, the inboxes hold 800 GB, which is a partitioned cache cluster, not one machine. The cap is what keeps it bounded: an inbox drops its oldest id when a new one arrives, and older history is read from the authors’ own lists if anyone scrolls that far.

Why use a heap to build the feed page?

At read time you have one sorted list per source: the inbox and each star the reader follows. Taking the newest post across s sorted lists is a k-way merge, and a heap holding one candidate per list gives the next post in O(log s). A page of k posts costs O(k log s) after the cursor is found in each list.