News feed
A news feed shows each user the recent posts of everyone they follow. The core decision is when to do the merge: at write time (fan-out on write, push each post id into every follower’s precomputed list) or at read time (fan-out on read, merge followees’ posts on every load). Reads outnumber posts by 20× or more, so the standard answer is a hybrid: push for ordinary accounts, pull for the few with millions of followers. A feed load is then one cache read plus a merge of a handful of hot lists, O(k log k + page); a post costs O(followers) asynchronous list writes, capped by the celebrity threshold.
The problem
Section titled “The problem”Facebook, Instagram, X/Twitter, LinkedIn and Threads all have one: open the app and see posts from accounts you follow, newest or most relevant first. Under the UI it is a many-to-many join between “who I follow” and “what they posted”, evaluated for hundreds of millions of users many times a day.
The goals conflict:
| Goal | What it means | Pulls toward |
|---|---|---|
| Fast feed loads | First page in ~200 ms, even for someone following 2,000 accounts | Precompute (push) |
| Fresh feeds | A new post shows up for followers within seconds | Cheap, quick fan-out; or compute on read |
| Bounded write cost | One post from an account with 100M followers must not stall the system | Don’t push to everyone (pull) |
| Relevance | Show the posts you care about, not just the newest | A ranking stage, which needs candidates to rank |
Requirements and scope
Section titled “Requirements and scope”| In scope (typical) | Ask about | |
|---|---|---|
| Functional | Publish a post. Load the home feed of followed accounts, paginated. Deletes and edits show up. | Chronological or ranked? Include reshares, ads, recommendations from accounts you don’t follow? |
| Scale | 300M DAU, 0.5 posts/user/day, 200 average followers, 10 feed loads/user/day. | The follower distribution: what’s the biggest account? |
| Latency | Feed load p99 under ~300 ms. New posts visible to followers within ~5 s. | Is “within a minute” acceptable for celebrity posts? |
| Consistency | Eventual. Two followers may see a post a few seconds apart. Authors see their own post at once. | Must a delete be instant everywhere? (Usually: hidden on next load.) |
| Availability | Feed must load even when ranking or fan-out is degraded. | Is a stale or unranked feed acceptable as a fallback? |
| Out of scope | Post storage and media, search, notifications, the follow-graph service itself. |
Back of the envelope
Section titled “Back of the envelope”Drag the assumptions. The number to watch is fan-out writes per second: posts per second times followers. Then look at the last row: one celebrity post, pushed.
What to say out loud: “About 1,700 posts a second become ~350K list writes a second on average, and feed reads are ~70K/s at peak. Feed lists of 800 ids are about 2 TB at 8 bytes per id, so they fit in a sharded cache. The average is fine. The problem is the tail: a celebrity post is a 100M-write burst. That’s why I’ll go hybrid.”
API and data model
Section titled “API and data model”POST /posts { text, media_ids[] } -> 201 { post_id }GET /feed?limit=20&cursor=... -> { posts[], next_cursor }DELETE /posts/{id} -> 204
Post (key: post_id) { post_id, author_id, created_at, body, deleted }Follows (key: follower_id) { followee_ids... } -- and the reverse index:Followers (key: followee_id) { follower_ids... } -- paged, used by fan-outFeedList (key: user_id) [post_id, ...] newest first, trimmed to ~800AuthorList (key: author_id) [post_id, ...] that author's own recent postsTwo decisions hide in that sketch:
- Feed lists hold ids, not posts. A post is stored once. Feeds are lists of 8-byte ids, hydrated at read time from a post cache. That makes edits and deletes a single-row change, and it keeps the feed cache small: 300M users × 800 ids × 8 B ≈ 2 TB, not petabytes.
- Post ids are time-ordered. With Snowflake-style ids (timestamp in the high bits), sorting by id is sorting by time, and the cursor can be just
(created_at, post_id). Merging lists needs no extra lookups.
High-level design
Section titled “High-level design”Step through each flow. Notice that the write path ends in the feed cache and the read path starts there: the cache is the meeting point.
| Component | Role | Why it’s there |
|---|---|---|
| Post service | Validates, assigns a time-ordered id, stores the post once, emits an event. | The write path stays short; fan-out happens after the response. |
| Fan-out queue + workers | For each post, page through followers and push the id to each feed list. | Async, retryable, horizontally scaled; absorbs bursts. |
| Social graph | Followers and followees, both directions. | Fan-out needs followers; the pull path and rebuilds need followees. |
| Feed cache | One list of recent post ids per active user, sharded by user. | The precomputed answer: a feed load is one key read. |
| Feed service | Reads the list, pulls celebrity posts, calls the ranker, builds the cursor. | Stateless; owns pagination. |
| Ranker + post cache | Hydrates ids into posts, filters, scores, mixes. | Relevance, and the place where deletes, blocks and privacy are enforced. |
Deep dive: push, pull or hybrid
Section titled “Deep dive: push, pull or hybrid”Pick a model, then change the follower skew and how many people are active today. The left chart shows total work; the right chart is the hybrid trade-off as you move the threshold.
| Fan-out on write (push) | Fan-out on read (pull) | Hybrid | |
|---|---|---|---|
| Cost of a post | O(followers) list writes | O(1) | O(followers) only if below threshold T |
| Cost of a feed load | 1 list read | O(followees) reads + a k-way merge | 1 list read + merge of a few celebrity lists |
| Freshness | Seconds after fan-out finishes | Always current | Both |
| Worst case | One celebrity post = 100M writes, minutes of lag | Following 5,000 accounts = slow every time | Bounded both ways |
| Wasted work | Pushes to followers who never log in | None | Skip inactive followers too |
| Who used it | Twitter’s original home timeline (Redis lists) | Facebook’s feed was assembled at read time | Twitter, Instagram and most large feeds today |
Two refinements make push cheaper still:
- Skip inactive followers. Most of a big account’s followers are not active on a given day. Push only to users seen in the last N days; rebuild the others with the pull model when they return (the “Cold user” flow).
- Choose T by delivery time, not by follower count alone. If the fan-out tier writes 1M ids per second, a post to 5M followers takes 5 s. Pick T so the slowest push is still acceptable.
Deep dive: assembling a page
Section titled “Deep dive: assembling a page”At read time the feed service merges the user’s precomputed list with the recent-post lists of the celebrities they follow. Each list is already sorted newest first, so this is a k-way merge with a heap of k heads (the heap page covers the structure). Step through it, then press next page.
What the stepper shows:
- Fetch at most one page from each list. No single list can contribute more than
limititems to a page, so you fetch k × limit ids and uselimitof them. - The heap holds k items, so building a page costs O(limit × log k). With k ≈ 5 that is nothing; the cost is the k parallel fetches.
- The cursor is
(created_at, post_id)of the last item. Page 2 reads each list strictly after that pair. Offsets (?page=2) break as soon as a new post arrives at the top: everything shifts down one, and the reader sees a duplicate.
The fan-out side is a simple loop. What matters is that it pages, skips, and can be retried safely:
on post_created(post_id, author_id): if follower_count(author_id) >= CELEBRITY_T: append post_id to AuthorList(author_id) -- readers will pull it return for page in followers(author_id), 1,000 at a time: for user in page where last_active(user) > now - 30 days: push post_id onto FeedList(user) -- pipelined, ~1 round trip per page per shard trim FeedList(user) to 800 -- retry-safe: pushing the same id twice is harmless if reads dedupe by post_idRanked feeds change pagination. If scores change between page 1 and page 2, a cursor on (score, id) skips or repeats posts. The usual fix is to rank once per session: compute the ordered list of a few hundred candidate ids, store it under a session key with a short TTL, and let the cursor be an offset into that frozen list.
Deep dive: ranking, edits and hot spots
Section titled “Deep dive: ranking, edits and hot spots”Ranking turns “recent posts from people you follow” into “posts you’ll engage with”. It runs as a funnel, because scoring thousands of posts with a large model per feed load is too slow:
- Candidate generation. The merged list (a few hundred to ~1,500 ids), plus optional out-of-network recommendations.
- Light ranker. A cheap model or heuristic cuts candidates to a few hundred.
- Heavy ranker. A large model predicts engagement (like, reply, dwell time) for each survivor.
- Filters and mixing. Drop deleted, blocked, muted and already-seen posts. Enforce author diversity (not five posts in a row from one account), insert ads.
X’s open-sourced recommendation code describes exactly this shape: candidate sources, a light and a heavy ranker, then filtering and mixing.
Edits, deletes, unfollows and blocks are all handled at read time. Feed lists hold ids; hydration reads the current post and the current relationship, and drops anything that no longer qualifies. A background job may remove stale ids later, as cleanup. Rewriting millions of lists on every delete would be a fan-out storm in reverse.
hydrate(viewer, ids): posts <- post_cache.multi_get(ids) -- one batched round trip per shard keep p where p exists and not p.deleted and not blocked(viewer, p.author) and not muted(viewer, p.author) and visible_to(viewer, p) -- privacy rules, checked now, not at fan-out time return keepHot spots. A celebrity’s AuthorList is read by every follower on every feed load, so it is the hottest key in the system. Replicate it to every cache shard, or cache it in each feed-service process for a second or two. A viral post’s body is likewise hot in the post cache. The distributed cache deep dive covers hot-key replication.
Failure modes
Section titled “Failure modes”| What breaks | What you see | Design response |
|---|---|---|
| Fan-out backlog (celebrity, spike) | New posts reach followers minutes late | Hybrid threshold; partition the queue; prioritise active users; autoscale workers |
| Feed cache shard lost | Affected users get a miss | Rebuild on demand with the pull model; replicas; the cache is derived data, never the source of truth |
| Ranker slow or down | Feed latency spikes | Timeout, then fall back to the chronological merge; serve stale ranked results |
| Duplicate fan-out after a retry | The same post twice in a feed | Dedupe by post_id at read time; or make pushes idempotent per (user, post) |
| Hot celebrity list | One cache shard at 100% | Replicate hot keys; local in-process cache with a 1-2 s TTL |
| User follows 5,000 accounts | Rebuild is slow | Cap the pull on rebuild (most recent N followees by activity); async rebuild then refresh |
| Deleted post still shown | Privacy and trust problem | Filter at hydration; invalidate the post cache on delete |
What it costs
Section titled “What it costs”| Operation | Time | Space |
|---|---|---|
| Publish (store + enqueue) | O(1), ≈10 ms | Post body once |
| Fan-out of one post | O(followers) list pushes, async; ≈ followers / 1M per second of fan-out capacity | 8 B per follower per post (until trimmed) |
| Feed load, push part | O(1) list read + O(limit) hydration | — |
| Feed load, pull part | k parallel fetches + O(limit × log k) merge | O(k × limit) ids in memory |
| Rebuild a cold feed | O(followees) fetches + merge, ≈100s of ms | Writes one list |
| Feed cache total | — | DAU × list length × 8 B ≈ 2 TB at 300M × 800 |
| Fan-out writes | ≈ posts/s × average followers ≈ 350K/s here | — |
In the interview
Section titled “In the interview”A good 45-minute arc:
- Clarify (5 min). Chronological or ranked, follower distribution, freshness target, scale.
- Estimate (5 min). Posts/s, fan-out writes/s, feed reads/s, feed-cache memory, and the celebrity burst.
- Data model (5 min). Posts stored once, feed lists of ids, time-ordered ids, both directions of the graph.
- Push vs pull (10 min). Explain both and their costs. Land on hybrid with a threshold and skipping inactive users.
- Read path (10 min). Merge, cursor pagination, hydration and filtering, ranking funnel.
- Harden (5-10 min). Fan-out backlog, cache loss and rebuild, ranker fallback, hot keys, deletes.
Follow-ups to expect: “A user follows a celebrity: when does that celebrity’s old content appear?” Immediately, because celebrity posts are pulled at read time; for a normal account, backfill its recent posts into the follower’s list on follow. “Make the feed multi-region.” Fan-out writes into a feed cache in each region from a replicated post log; each region serves its own reads. “How do you know ranking helps?” A/B test on engagement and on long-term retention, not just clicks.
Check yourself
Section titled “Check yourself”Go deeper
Section titled “Go deeper”- Raffi Krikorian: Timelines at Scale (InfoQ): Twitter’s home timeline, fan-out into Redis, and the special case for high-follower accounts.
- Bronson et al.: TAO, Facebook’s distributed data store for the social graph (USENIX ATC 2013): the graph store and caching layer behind feed reads at Facebook.
- X: the recommendation algorithm source: candidate sources, light and heavy rankers, and the mixing and filtering stages of the For You timeline.
Concept pages to drill: Heaps · Caching · Event-driven systems · Iterator design · Graph representation · Distributed thinking