systemsadvanced 25m read

Designing for Scale · Newsfeed and Fan-out

Why reading from a database to render a feed is too slow, and how the fan-out-on-write model precomputes millions of feeds in memory before users even ask for them.

The problem this post solves

A newsfeed looks like a simple database query: "Get all posts from everyone I follow, sort by time, limit 20."

When you have twenty followers and a few dozen posts, it is a simple query. When you follow a thousand people, who each have millions of followers, and you expect the feed to load in under 200 milliseconds, that query becomes an impossibility. Relational joins across follower graphs and timeline tables simply cannot execute fast enough at scale.

This post covers the shift from pull-based architectures to push-based architectures. The solution to making the read fast is to do the work before the read happens.

First principles

From first principles

Start with the question

Why does the naive SQL query fail at scale?

1
To build a feed on demand, the database must join the Follower table and the Post table.
forced by · It needs to find who you follow, then find all their posts.
2
It must then sort all of those posts by time, in memory, before discarding all but the top 20.
forced by · You cannot limit the result until the entire merged timeline is sorted.
3
As a user follows more people, the amount of data to join and sort grows.
forced by · The query complexity is proportional to the number of people followed and how active they are.

⇒ Therefore

Computing a feed at read time forces the database to do heavy, unbounded work while the user waits. At scale, reads must be O(1) lookups.

Fan-out on Read vs Fan-out on Write

If we cannot compute the feed when the user asks for it, we must compute it when the post is created. This is the core architectural divide in feed design.

Fan-out on Read (Pull)

This is the naive approach. When Alice posts, nothing special happens. When Bob opens his app, the server pulls Alice's post (and everyone else's) to assemble Bob's feed. Advantage: Writing a post is instant. Disadvantage: Reading a feed is slow.

Fan-out on Write (Push)

When Alice posts, the server immediately finds all of Alice's followers. It takes the ID of Alice's post and pushes it into a pre-computed "feed list" for each follower. When Bob opens his app, his feed is already built; the server just returns the list. Advantage: Reading a feed is instant. Disadvantage: Writing a post triggers a massive background job.

The tradeoff

Which fan-out model to use

Fan-out on Write (Push)

+ you gain Read latency is guaranteed and low. Feed retrieval is an O(1) cache lookup.

− you pay The 'Celebrity Problem'. If a celebrity with 100 million followers posts, pushing to 100 million lists creates a massive backlog and delay.

pick when Default for 99% of users, because the system is vastly read-heavy.

Fan-out on Read (Pull)

+ you gain Handles celebrities perfectly. No massive write-amplification on posting.

− you pay Slower reads.

pick when Only used for celebrity accounts or highly inactive users.

The Hybrid Architecture

Because a strict Fan-out on Write model breaks when a celebrity posts, modern feeds use a hybrid model.

When a user posts:

The post is saved to the database.
If the user is a celebrity (e.g., > 100,000 followers), the process stops.
If the user is normal, the Fan-out Workers fetch their followers.
For each follower, the post_id is prepended to their feed list in Redis.

When Bob requests his feed:

The API fetches Bob's pre-computed feed from Redis (containing posts from normal friends).
The API fetches the recent posts of the celebrities Bob follows. (This is fast because it's a direct lookup of a few specific accounts).
The API merges the two lists, sorts them by time, and returns the top 20 to Bob.

Sizing the Feed Cache

The feed cache (usually Redis) stores lists of post_ids, not the actual post content.

If we have 100 million active users, and we store 500 post IDs per user:

100M users × 500 IDs × 8 bytes (per ID) = roughly 400 GB. This easily fits in a small Redis cluster.

Mental modelCache the ID, not the object

A feed list in Redis contains [104, 88, 72]. The API reads the IDs, then fetches the actual text and images for those IDs from a separate Object Cache.

If a post is edited, you only update the Object Cache. The feed lists don't change.
If you cached the full text in the feed list, you would have to update it in a million different lists.
Data that is duplicated must be immutable or an ID.

🔔 Fires when you see

Use whenever you are storing lists of entities in a cache.

Failure modes

Caching inactive users. If you compute and store feeds for users who haven't logged in for six months, you are wasting RAM and worker CPU. The fan-out process should only push to the cache of users who have been active recently (e.g., in the last 14 days).

The stampede on cache miss. If a user's feed cache is evicted from Redis, and they log in, the system must rebuild it via Fan-out on Read. If it rebuilds the entire history, the database will spike. The rebuild must be strictly limited to the last few days of data.

Sorting by something other than time. The hybrid model works because time-sorting is predictable. If the feed is sorted by a complex machine learning "relevance" score, the pre-computed list approach breaks down, because relevance changes based on the reader's context at read time. Relevance feeds require a completely different architecture (Heavy Ranking/Scoring pipelines at read time).

What to carry forward

Key points

You can now

Explain the read/write trade-offs of the two fan-out models.
Design a hybrid architecture that handles both normal users and celebrities.
Calculate the memory budget for a feed cache.
Prevent cache bloat by identifying and handling inactive users.