Design a news feed: post, follow, view, page
"A feed is a read-heavy merge of recent posts from everyone you follow, newest first. The question is when the merge happens: at read time or at post time. The answer is both, chosen per account. Precompute feeds for normal accounts, merge huge accounts in at read time, and replicate the post cache so a viral post's reads spread across every copy."
Understanding the problem
5 minFunctional Requirements
- Users create posts.
- Users follow other users (a one-way follow, not two-way friends).
- Users view a feed of posts from people they follow, newest first.
- Users page through the feed (infinite scroll).
Below the line (out of scope):
- Likes and comments, and private or restricted posts.
- Login: users are already authenticated, and the user id comes from the session or JWT.
Non-Functional Requirements
- A feed of 200 post ids is 200 × 10 B = 2 KB per user, and 2 KB × 2B users = 4 TB.
- A fraction of a cent per user per month, against more than $200 a year of revenue per US and Canada user.
- A 64-bit time-sortable post id (Snowflake style, timestamp in the high bits) is 8 bytes, so "about 10 bytes" holds.
- The id sorts by creation time, so the feed orders by id alone.
- One post from an account with 90M followers is 90,000,000 feed writes / 60 s = 1.5M writes/s.
- One DynamoDB partition takes 1,000 writes/s, so one post needs 1,500 partitions' write capacity for a full minute, several times a day.
- One viral post is 90,000,000 reads / 3,600 s = 25,000 reads/s on one key.
- Assumes each of the 90M followers loads a feed showing the post once in its first hour.
- One DynamoDB partition serves 3,000 RCU (6,000 eventually consistent reads/s), so the post item runs about 4x over.
- Available over consistent: a post may take up to 1 minute to reach followers' feeds.
- Posting and viewing the feed both return in under 500 ms.
- Put numbers on NFRs: "fast" and "single-digit ms" lead to different designs.
- 2B users with unlimited follows both ways: anyone can follow or be followed by any number of accounts.
- A huge account can have 90M+ followers.
Entities + API
5 minDefining the Core Entities
- User: posts, follows other users, and reads a feed.
- Follow: a one-way link, follower → followed.
- Its own entity, because the graph is many-to-many.
- Post: made by a user, shown in followers' feeds. Its id is time-sortable.
API or System Interface
POST /posts // { content } -> { postId }
PUT /users/{id}/follow // -> 200, the caller follows {id}
DELETE /users/{id}/follow // -> 200, the caller unfollows {id}
GET /feed?pageSize={n}&cursor={postId} // -> { items: Post[], nextCursor }
- The caller's user id comes from the auth token in the request header.
contentis left open for rich data. - Follow is a PUT so a double click is idempotent.
- The cursor is the last returned post's time-sortable id, opaque to the client. Ids never tie, so no post that shares a timestamp is skipped or repeated at a page boundary.
High-level design
10 min, end to end, no dives yet1) Create a post
- Client → API gateway / load balancer → Post Service → Post table.
- The Post Service is stateless and scales horizontally.
- The Post table is a key-value store such as DynamoDB, which scales when load spreads evenly across partitions.
2) Follow a user
- Follow Service → Follow table, partition key
userFollowing, sort keyuserFollowed. - A reverse global secondary index flips the keys: partition
userFollowed, sortuserFollowing. - Three queries, all key lookups: does A follow B, who does A follow, who follows B.
- "Does A follow B": both keys.
- "Who does A follow": the partition.
- "Who follows B": the reverse index.
- No graph database, because there are no traversals. It also avoids "how do you scale Neo4j?".
- Separate tables are fine for the interview even though DynamoDB recommends single-table design.
3) View the feed
- A separate Feed Service, because reads are heavy and the access pattern differs from posting.
- Naive flow: get everyone the user follows, get their posts, sort by time, return.
- Their posts come from a Post index by creator: partition
creatorId, sortpostId, which is time-sortable. - This does not scale: one feed request becomes thousands of Follow and Post queries; the dive on users who follow many accounts handles it.
- Many follows, many posts each, and a huge merged set to sort.
- Cover breadth first, then depth.
4) Page through the feed
- The same three steps, reading only posts older than the cursor.
- The cursor is the last returned post's time-sortable id, so the creator-index range read never skips or repeats a shared timestamp.
- Each page returns the next n older posts and a new cursor.
Potential deep dives
~20 min, interviewer steers1) Users who follow many accounts: how does the feed read stay fast?
- The Feed Service reads the follow list, queries the creator index once per followed account, and sorts the merged posts, on every feed load.
- The naive read turns one feed request into thousands of Follow and Post queries.
- Tens to hundreds of sub-requests per request are normal. Thousands, at low latency, are not.
- Keep each user's newest ~200 post ids as a precomputed list, and add each new post's id to its followers' lists when it is created.
- A feed load reads one key instead of thousands.
- Still wrong with a plain list updated by
LPUSH:- Two concurrent writers to one feed lose a post.
- A retried write adds the post twice.
- The list orders by arrival, not by creation time.
- Fan out on write: each user's feed is a Redis sorted set of about 200 post ids, scored by the id's time.
- The Feed Service reads the feed from it; each new post is added to the relevant feeds.
- This moves the problem to writes: one huge-account post must reach millions of feeds.
- Add with one atomic Lua script, so concurrent or repeated adds land once, in creation order:
ZADD feed:{userId} score postIdthenZREMRANGEBYRANK feed:{userId} 0 -201.- Concurrent workers: Redis runs a script atomically, so no post is lost.
- Redelivery:
ZADDof an existing member rewrites the same score, so a duplicate changes nothing. - Late arrival: the score orders by creation time, whatever the arrival order.
- A list with
LPUSHfails all three: a read-modify-write loses a post, a redelivery doubles it, and order follows arrival.
- Paging past 200 falls back to reading each followed account's posts from the creator index, and few users ever page that far.
- Memory: 2 KB is raw payload, and the default skiplist encoding costs about 20 KB per user, 40 TB for 2B users.
- Raise
zset-max-listpack-entriesabove 200 so each feed stays in the compact listpack encoding. - Keep feeds only for active users (below). Together these bring it back near 4 TB.
- Raise
- Dormant users: the feed is a cache with a 30-day TTL that a read refreshes, and the add script adds only if the key exists.
- On a miss, the Feed Service creates the key with a sentinel member at score 0 (Redis deletes an empty sorted set; reads skip the sentinel).
- It serves the first page from a bounded naive read (the newest few posts of each followed account) and rebuilds the feed asynchronously.
- A worker that runs during the rebuild lands its post in the key, and
ZADDdedupes the overlap. The first load after dormancy is slower; say so.
- Ask whether the product can cap follows or give heavy followers a slower feed.
- A user following 100K accounts will not notice posts arriving a couple of minutes late.
- A product cap on follows is a legitimate lever: Facebook caps friends at 5,000.
- On DynamoDB the feed is one item per entry (partition
userId, sort keypostId), so no two workers share an item. Trim past 200 with a periodic delete or a TTL.
2) Users with many followers: how does one post reach millions of feeds?
- The 1-minute staleness budget is the time the writes have.
- 90M followers in 60 s is 1.5M writes/s for one post.
- The Post Service blasts all the feed writes inside the create call.
- Connection limits and latency make it unworkable.
- One huge account's post piles 90M writes onto one Post Service host while the others idle.
- The Post table's change stream puts
{postId, creatorId}on an at-least-once queue (SQS, for example).- DynamoDB Streams, or an outbox row written in the same transaction, so a crash between the post write and the enqueue cannot drop a post.
- The first worker pages the reverse Follow index and enqueues one sub-message per 10,000 followers,
{postId, creatorId, followerCursor}.- Each chunk retries on its own, so a failure replays 10,000 writes, not 1M.
- A 1M-follower post becomes 100 chunks that run in parallel.
- Each chunk worker runs the add script on its followers' feeds.
- Cost: enormous worker throughput, and a 90M-follower post still needs 1.5M writes/s.
- Split accounts by follower count: below T followers a post fans out on write; above T (a "huge" account), followers pull its posts at read time. Most users follow both kinds, so their feed is a bit of each.
- T caps per-post write load: the worst post that still fans out costs T writes. T is configuration; T = 1M is 100 chunks inside the minute.
- Fan-out workers skip any post by a huge account.
- The flag is
User.isHuge, mirrored in a HugeAccounts set. - The set lives in memory on every worker and Feed Service host; a worker checks the creator's flag once per post, not once per follower.
- Switching an account's mode is one row write plus a set update, never 90M Follow-row updates.
- The flag is
- Every account above T/2 followers keeps RecentPosts, a cached list of its last ~100 post ids.
- Written through to all N cache replicas.
- A 60 s TTL is the backstop for a replica that missed the write, so a stale list is at most 60 s old, inside the budget.
- A miss is never "no posts": the Feed Service reloads the last ~100 ids from the creator index and sets the key.
- These are the hottest keys in the system (any of 90M followers' feed loads reads one), which the hot-key dive's replicas absorb.
- On each feed load, the Feed Service merges the reader's precomputed feed with the RecentPosts of every huge account they follow, in one multi-get.
- A reader's huge follows = cached follow list ∩ HugeAccounts (5,000 ids × 8 B = 40 KB).
- One multi-get, not k creator-index queries, which would bring back one query per followed account for a user following 500 huge accounts.
- One time-sortable cursor
cbounds both halves of the merge, and each half fetches n.- Precomputed half:
ZREVRANGEBYSCORE feed:{userId} (c -inf LIMIT 0 n. Huge half: up to n ids belowcfrom each RecentPosts. - Merge by id, dedupe by postId, return the top n, and set
nextCursorto the nth id. - When a half runs out (fewer than n ids below
c), stop the page at its oldest id, then read below it from the creator index.- Otherwise older huge-account posts fill the page and the normal-follow posts between them are skipped for good.
- Precomputed half:
- Use hysteresis on the threshold: an account switches to fan-out on read above T followers, and back to fan-out on write only below T/2.
- With one threshold, an account hovering near T would switch modes over and over (flapping), and every switch back costs a backfill.
- Switching to fan-out on read is safe at once: the account has kept RecentPosts since it passed T/2, so readers can merge its posts as soon as workers stop writing them.
- Switching back runs in three steps: workers resume fan-out and wait until every host's HugeAccounts set has the change; a backfill writes the account's recent posts into each follower's feed (at most 200 per follower, T/2 followers); only then do readers stop merging.
- In both directions, every post is covered by at least one path at every moment.
ZADDand the merge dedupe any overlap.
- Cost: more work in the Feed Service at read time.
Follow changes
- New follow: after writing the Follow row, enqueue
{followerId, followedId}.- Normal account: a worker reads its recent posts from the creator index and runs the add script (idempotent, trim keeps 200).
- Huge account: nothing to do, the read-time merge covers it.
- Unfollow: remove the row, then an async job removes that account's posts from the feed with
ZREM.- Until it runs, reads filter hydrated posts by the live follow list, fetching a few more than n.
- Backfill and unfollow jobs for one (follower, followed) pair share a FIFO message group, so a re-follow's backfill cannot interleave with the removal.
3) Uneven reads of posts: how do you survive a hot key?
- Most posts are read for a few days and then never again, but a huge account's post gets heavy reads in its first hours.
- Posts are rarely edited, so they cache well.
- Every feed load reads its posts straight from the Post table, with no cache in front of it.
- One viral post at 25,000 reads/s runs 4x over its DynamoDB partition's 6,000 reads/s.
- Adaptive capacity handles a few hundred req/s on one item; no table capacity fixes 25,000, because one item lives on one partition.
- A Redis post cache sharded by postId, with a long TTL, LRU eviction, and invalidate on edit. Capacity is N hosts × M memory.
- Cost: the hot-key problem returns. The shard holding a viral post is overloaded while the others idle.
- One Redis node serves on the order of 100K GETs/s, so 25,000 reads/s fits on one shard; it breaks when one key needs more than one node.
- Say it out loud: shards add capacity for more keys, never for one key. Replicas do.
- Run N independent post-cache instances behind a load balancer, each able to serve any post, with no coordination.
- A viral post's reads split across all N instances.
- Cost: up to N database misses for a new hot post, and fewer distinct posts fit in total. Both are fine: tiny next to no cache, and DynamoDB absorbs some variance.
- An edit broadcasts the key delete to all N instances, with a TTL as the backstop for one that missed it. Edits are rare, so the broadcast is cheap.
- A deleted post is a tombstone on the Post row plus the same broadcast; the dead id stays in feeds.
- Hydration drops tombstoned posts and reads a few more than n ids to fill the page; the trim removes dead ids over time.
- Fanning a delete out to 1M feeds would cost as much as the post did.
- One feed load becomes a Follow query plus up to 5,000 creator-index queries, then a sort of the merged set.
- Thousands of sub-requests cannot finish in 500 ms.
- Replace it with fan-out on write into a Redis sorted set of ~200 post ids per user (2 KB, 4 TB for 2B users).
- Fall back to the naive query only for the rare page past 200.
- It does not get fanned out: 90M writes in 60 s is 1.5M writes/s for one post.
- Workers skip accounts flagged
User.isHuge(above T), checked once per post against an in-memory HugeAccounts set. - The Feed Service merges it in when each follower loads the feed, from the account's RecentPosts in the replicated post cache.
- Normal accounts still fan out through async workers in 10,000-follower chunks, fed by the Post table's change stream.
- One time-sortable cursor bounds both halves.
- Read up to n ids below the cursor from the precomputed feed, and up to n from each huge follow's RecentPosts in one multi-get.
- Merge by id, dedupe by postId, return the top n, and hand back the nth id as the next cursor.
- When either half runs out, stop the page at its oldest id and read below it from the creator index.
- Sharding puts each key on exactly one node, so every read of the viral post still lands on one shard.
- More shards add room for more keys, never capacity for one key.
- A replicated post cache (N independent full instances behind a load balancer) splits that post's reads N ways.
- Cost: up to N database misses for a new hot post, and fewer distinct posts cached.
- With a plain list, a read-modify-write loses one worker's post, a redelivery adds it twice, and prepending orders by arrival.
- Store the feed as a Redis sorted set of post ids scored by the id's time, and add with one Lua script (
ZADDthen trim to 200). - The script is atomic,
ZADDof an existing member rewrites the same score, and the score keeps creation order.
Final design + what is expected at each level
wrapFinal Design
- Clients → API gateway / load balancer → Post Service, Follow Service, Feed Service.
- The Post Service writes the Post table and its creator index.
- The Follow Service writes the Follow table and its reverse index.
- The Post table's change stream feeds a queue; feed workers fan out in 10,000-follower chunks unless the creator is flagged huge (too many followers to fan out).
- Each feed is a Redis sorted set, updated by one add-and-trim script, with a 30-day TTL for dormant users.
- The Feed Service merges the sorted set with the cached recent posts of followed huge accounts in one multi-get, then hydrates ids from the replicated post cache.
- Every post from an account you follow reaches your feed within a minute exactly once and in time order. That is the invariant to close on: either a feed worker wrote it into your precomputed feed or the Feed Service merged it in at read time, and the design never lets a post fall through both.
What is Expected at Each Level
- Mid (E4):
- Clear API and data model.
- A working high-level design that meets the requirements.
- Maybe some Good answers.
- Not expected to cover every scaling edge.
- Senior (E5):
- Speeds through the high-level design.
- Goes deep on at least 2 of the deep dives.
- Users who follow many accounts: fans out on write into a precomputed list of each user's newest ~200 post ids, and says what a plain list gets wrong under concurrent workers and redelivery.
- Users with many followers: moves the fan-out to async workers behind a queue, in 10,000-follower chunks, and says that a 90M-follower post still needs 1.5M writes/s.
- Uneven reads of posts: puts a post cache sharded by postId in front of the Post table, and says that the shard holding a viral post stays hot.
- Knows the fan-out approaches.
- Finds bottlenecks one after another and weighs the trade-offs.
- Raises fan-out and performance issues before being asked.
- Staff+:
- Likely covers all the deep dives, and maybe more.
- Surfaces issues unprompted.
- Talks performance tuning.
Say the opener out loud without notes: a read-heavy merge, done at post time for normal accounts and at read time for huge ones, with a replicated post cache.
Then write the math from memory: 200 × 10 B = 2 KB per user, × 2B = 4 TB; 90,000,000 / 60 s = 1.5M writes/s for one huge-account post.
Then say the add in one sentence: ZADD feed:{userId} score postId then trim to 200, in one Lua script, so concurrent workers, redelivery and late arrival all land correctly.