Design a news feed

In 2 minutes

I would use a hybrid fan-out design. Publishing stores the post once by ID, queues a small fan-out job and returns straight away. Workers read the author's followers from the follower graph and push the post ID onto each follower's feed list in an in-memory cache. Each list holds only IDs, capped at 800, because IDs are small, so 100 million users take about 640 GB, and edits and deletes only touch one record. Reading takes the first IDs from the cache, fetches the posts in one batch, drops any deleted ones, ranks them and returns 20 with a cursor. Offset paging breaks on a moving feed, so the cursor holds the last post ID or a ranking snapshot. Pushing works because reads outnumber posts about 50 to 1, but an account with 20 million followers would need about 200 seconds of cluster time for one post. So above a follower threshold I skip fan-out, and merge those accounts' latest posts at read time. I also skip push for people inactive for 30 days. The trade-off is two read paths in return for cheap reads and safe writes.

The question

Clarifying questions

• Is the feed in time order, or ranked by relevance? A time-ordered feed is a merge of lists. A ranked feed adds a scoring step that needs more inputs at read time.
• How many accounts does a typical user follow, and how many followers does the largest account have? Fan-out cost is followers per post, so the biggest accounts decide whether a pure push design is safe.
• How quickly must a new post show up in followers' feeds? Seconds of delay allow asynchronous fan-out. Instant visibility would force expensive synchronous work.
• Do posts carry media, and can they be edited or deleted? Edits and deletes are why the feed should store references to posts, not copies of them.
• How far back can a user scroll? A bounded feed, such as the latest 800 posts, can live in a cache. Unlimited history needs a different read path.

Requirements

Functional

• Publish a post, and follow or unfollow an account.
• Show a home feed of recent posts from followed accounts, newest or best first.
• Page through the feed without repeated or skipped posts.
• Reflect edits and deletes in the feed.

Non-functional

• Feed read: p99 under 200 ms for the first page of 20 posts.
• A new post reaches most followers' feeds within 10 seconds.
• Publishing returns in under 300 ms and never waits for fan-out.
• Handles 58,000 feed reads a second at peak.

Back-of-the-envelope estimates

Assumptions for this exercise:

• These numbers are assumptions for the exercise, not facts about any real product.
• 100 million people use the product daily. 20% post once a day, each follows about 200 accounts, and has 200 followers on average.
• A user opens the feed 10 times a day. Peak traffic is 5 times the average.
• A cached feed holds the latest 800 post IDs of 8 bytes each. One cluster can process about 100,000 feed inserts a second.

The arithmetic:

• Posts per second: 20M posts a day ÷ 86,400 s ≈ 231 → ≈ 230/s on average, about 1,200/s at a 5x peak
• Fan-out writes per second: 20M posts × 200 followers = 4B inserts a day ÷ 86,400 s ≈ 46,300 → ≈ 46,000/s on average, about 230,000/s at a 5x peak
• Feed reads per second: 100M × 10 = 1B a day ÷ 86,400 s ≈ 11,600 → ≈ 11,600/s on average, about 58,000/s at a 5x peak
• Feed cache size: 100M users × 800 IDs × 8 bytes → 640 GB, spread over about 10 cache nodes
• One post by an account with 20M followers: 20M inserts ÷ 100,000 a second → ≈ 200 s, too slow and too bursty to push

High-level design

A Client talks to an API gateway. Publishing goes to the Post service, which stores the post once in the Post store and puts a small fan-out job on the Fan-out queue. It then answers right away.

A Fan-out worker takes each job, reads the author's followers from the Follower graph, and adds the new post's ID to the front of each follower's list in the Feed cache. That list is a short, bounded list of IDs, not a copy of the posts.

Reading goes to the Feed service. It reads the first IDs from the Feed cache, fetches the posts themselves from the Post store, and returns the page. For accounts too large to fan out, the Feed service merges their latest posts in at read time.

How a request flows

Publish a post

1. The author submits a new post through the API gateway.
2. The gateway routes it to the Post service, which checks it.
3. The service stores the post once, under a new post ID.
4. It then queues a small job holding the post ID and the author ID.
5. The service answers at once. The author does not wait for followers' feeds to update.
6. The author sees the post as published.

Fan out to followers

1. The Post service has queued a fan-out job for the new post.
2. A fan-out worker takes the job from the queue.
3. It asks the follower graph for the author's followers, one page at a time.
4. The graph returns a page of follower IDs. Very large accounts are skipped, because their posts are merged at read time.
5. The worker adds the post ID to the front of each follower's feed list and trims the list to 800.

Read the home feed

1. A user opens the app and asks for the first page of the feed.
2. The gateway routes the request to the Feed service.
3. The service reads the user's first post IDs from the feed cache.
4. The cache returns a list of IDs, newest first, in one fast call.
5. The service fetches the post bodies for those IDs, and also the latest posts of any very large accounts the user follows.
6. The store returns the posts. Deleted ones are missing and are dropped from the page.
7. The service merges, ranks and cuts the page to 20, and adds a cursor for the next page.
8. The client shows the page and keeps the cursor.

Deep dive: fan-out on write, on read, or both

There are two ways to build a feed.

• Fan-out on write (push). When a post is published, add its ID to every follower's feed. A read is then one list lookup. Reads are cheap and fast, but each post costs one write per follower.
• Fan-out on read (pull). Store nothing extra. When a user opens the feed, look up the latest posts of everyone they follow and merge them. A post costs one write, but each read costs about 200 lookups. At 58,000 reads a second that is more than 11 million lookups a second.

Since reads outnumber posts by around 50 to 1, push wins for most accounts. Our estimate gives 46,000 inserts a second on average, which a cache cluster handles easily as a background job.

Push breaks for very large accounts. One post by an account with 20 million followers means 20 million inserts, about 200 seconds of the whole cluster in our estimate. Most of those followers will not open the app soon, so most of that work is wasted.

The answer is a hybrid. Choose a follower threshold, say 100,000. Below it, push as usual. Above it, do not fan out. Instead, the Feed service finds which large accounts the user follows and pulls their latest posts at read time, then merges them with the pushed list. A user follows few such accounts, so this adds only a handful of lookups to a read.

Add a second saving for inactive users. Do not push to people who have not opened the app in 30 days. When they return, build their feed on demand with the pull path and then switch push back on. This cuts the write load a lot.

Deep dive: a feed cache of IDs

Store post IDs only: a list of 8-byte numbers, newest first, capped at 800. Do not store the post text, the author name or the images.

There are good reasons.

• Size. 800 IDs take 6.4 KB per user, so 100 million users take 640 GB. Full posts would be hundreds of times larger.
• One copy of the truth. A post is stored once. An edit or a delete changes that one record, and every feed shows the change on the next read. With copies you would have to find and fix every follower's copy.
• Cheap fan-out. Pushing a small ID is much faster than pushing a body with media links.

The price is a second step on read, called hydration. After fetching the IDs, the Feed service loads the posts in a single batch call from a post cache and the post store. A cache in front of the post store takes most of this load, since popular posts are fetched by many people. Missing IDs, which means deleted posts, are filtered out. If a page has fewer than 20 left after filtering, read a few more IDs.

The feed list itself can be a sorted set or a plain list in an in-memory store. Use an atomic push-and-trim command so the list never grows past its cap. Because post IDs are time-ordered, the list is naturally newest first.

If a feed cache is lost, rebuild it by the pull path: collect recent posts from the accounts the user follows, merge them and write the result back. It is slower, but nothing is lost, because the Post store and the Follower graph remain the source of truth.

Deep dive: ranking and cursor pagination

Ranking. A time-ordered feed is just the merged list. A ranked feed takes a larger candidate set, say the 200 newest IDs plus recent posts from large accounts, and scores each one. Typical signals are how recent the post is, how often the user interacts with the author, how many reactions it has, and the type of media. A light model computes the score at read time in the Feed service. Keep ranking separate from fan-out, so you can change the model without touching the write path. Always keep a plain time-ordered fallback for when the ranker is slow or down.

Pagination. Offset paging, such as 'skip 20, take 20', breaks on a feed that keeps changing. If three new posts arrive while the user reads page one, page two shows three posts again. Use a cursor instead. The cursor holds the position of the last item seen, such as its post ID. The next request asks for items older than that ID. New posts at the top do not shift the older ones.

A ranked feed has no simple ID order, so a plain cursor does not work. Two options:

1. Snapshot. On the first request, rank the candidates and cache the ordered list of IDs for a few minutes under a session ID. The cursor then holds the session ID and an offset into that frozen list.
2. Keep ranking local to the page. Rank only within time windows, and move through the windows by time cursor.

Do not insert new posts into a feed the user is reading. Show a 'new posts' banner that loads them on a tap. It avoids the page jumping under the user's thumb.

Trade-offs

• Fan-out: Push for most accounts, pull for very large ones over Push for everyone, or pull for everyone. Reads stay cheap and one huge account cannot flood the queue. The cost is two read paths and a threshold to tune.
• What the feed cache stores: Post IDs only over Full copies of posts. It is small, and edits and deletes take effect everywhere at once. The cost is a hydration step on every read.
• Who gets a cached feed: Active users only over Every user. It saves memory and a large share of write work. The cost is a slower first load for a returning user.
• Publishing: Acknowledge first, fan out asynchronously over Finish fan-out before replying. Publishing stays fast whatever the follower count. The cost is that followers see the post a few seconds later.

Common follow-up questions

How do you handle a new follow or an unfollow?
On a new follow, queue a small job that copies the followed account's last few post IDs into the user's feed. On an unfollow, filter by the current follow list when you read, and let the old IDs fall off the end of the list over time.

What happens when a post is deleted?
Mark it deleted in the Post store. The next hydration finds it missing and skips it, so it vanishes from every feed without touching the lists. A background job can clean up IDs later, but nothing depends on it.

How soon do followers see a post from a very large account?
Immediately, in the sense that it is stored. It appears the next time a follower's feed is read, because the pull path looks up recent posts from large accounts. There is no queue delay for those accounts.

What if one post goes viral and its record is read constantly?
That is a hot key. Cache the post in front of the store, and keep a small in-process copy in each Feed service instance for a few seconds. Reactions and counters can be updated in batches, so they do not make the post record a write hot spot.