News feed

01 · CONTEXT

The feed is a read queue

The news feed shows each user the recent posts from the people they follow. The hard part is assembling, for each reader, the right list within moments. According to the High Scalability summary of Twitter's 2013 architecture, almost all the traffic was reads: about 300 thousand requests per second read timelines and only about 6 thousand per second were writes.

This asymmetry organizes the whole case. The design question is at what moment the work of assembling the feed happens: when the post is created or when the reader opens the app. The two answers have different costs, and the real system almost never chooses just one. The design needs load balancing at the entry, partitioned data for the follower graph and for the posts, and a cache that absorbs repeated reads.

02 · FAN-OUT ON READ

Assemble the feed when the reader asks

In the fan-out-on-read model (also called the pull model), nothing is precomputed. When the user opens the feed, the service queries the follower graph to find out who they follow, fetches each one's recent posts and sorts the result. The system design interview source calls this fan-out on read: a single read request fans out into many others.

1. The reader opens the app. The load balancer picks an instance of the feed service, which holds no ready-made feed and has to assemble it now.

2. The service asks the follower graph which accounts this user follows. The more accounts, the more queries will follow.

3. For each followed account, the service looks for recent posts in the cache and, for whatever is missing, goes to the post database. This is where one read becomes many, and the database feels the weight.

4. The service gathers everything, sorts by time and returns it to the reader. The response latency depends on how many accounts the user follows, not on the size of the post.

The advantage, according to the ByteByteGo source, is that data is not pushed to friends, so the hot key problem does not exist. The drawback is that fetching the feed is slow because it was not precomputed.

03 · FAN-OUT ON WRITE

Assemble the feed when the post is born

The opposite model, fan-out on write (push model), changes the moment of the work. Instead of assembling the feed when the reader asks, the system precomputes the feeds when posts are created. The reader now reads a ready-made list, and the cost moves to publishing, which happens off the request path, by asynchronous workers.

1. The author publishes a post. The gateway validates the call and hands it to the post service, which takes care of persisting the content.

2. The service writes the post to the database and publishes an event to the queue. The response to the author does not wait for distribution to followers.

3. A fan-out worker consumes the event and queries the follower graph to find out who the post should reach.

4. The worker inserts the post identifier into each follower's precomputed feed. This is the expensive point: the number of writes grows with the number of followers.

5. Later, a follower opens the feed. The feed service reads the ready list from the cache, without querying the follower graph or scanning accounts.

6. The list stores only identifiers. The feed service fetches the content of those posts from the post database and returns the page to the reader.

The ByteByteGo source describes the fan-out service as the one that pushes new content to friends' feeds, stored in the cache for fast reads. The cost shows up with many followers: fetching the friend list and generating everyone's feeds is slow and time-consuming.

04 · CELEBRITIES

When a post has millions of readers

Fan-out on write breaks at the extremes. For huge accounts, the fan-out workers have a lot of work to do per post, and the Hello Interview source cites an example of tens of millions of followers on a single account. The ByteByteGo source names the problem: hot key.

The common way out is the hybrid model. The Hello Interview source describes flagging the large account with an indicator in the followers table, instead of writing the post to every follower, which lets you choose fan-out on read or on write account by account. ByteByteGo does the same: for those with many followers, followers pull the content on demand. The High Scalability summary of Twitter records the same idea: for very large accounts, do not fan out and merge their content at read time.

1. For an ordinary account, the path is fan-out on write: the worker consumes the event and inserts the post into each follower's precomputed feed.

2. For a large account, the indicator in the followers table makes the worker skip distribution. The post stays only in post storage, and the followers' feed receives nothing.

3. The follower opens the feed. The service starts with the precomputed part, read from the feed cache.

4. Next, the service uses the follower graph to find out which flagged accounts this reader follows.

5. The service fetches those accounts' recent posts from the post cache and, if missing, from the database. This cache receives the reads of all followers, so the hot key shifts to it.

6. The service merges the precomputed part with the large accounts' posts, sorts by time and returns the page to the reader.

The hybrid does not eliminate the hot key; it moves it somewhere else. The Hello Interview source points out that the biggest challenge of the post cache is having the same hot key problem as the post table.

05 · CACHE AND TRADE-OFFS

What to store in the precomputed feed

The precomputed feed is a cache per user with identifiers, not whole posts. In the Hello Interview source, each entry in the precomputed feed table is indexed by user and holds a list of post identifiers. At Twitter in 2013, according to High Scalability, the timeline lived in a Redis cluster with at most 800 entries per user (a value from that time).

Pagination follows this design. According to Hello Interview, a single timestamp indicates where the reader stopped and serves as the cursor for the next set of posts.