Design a News Feed System

1. The problemCopy Anchor Link

The scrolling list in the middle of Facebook / Instagram / LinkedIn / X: posts from people you follow, newest first (or ranked), loading more as you scroll. Same question as "design the Twitter timeline" or "the Instagram feed."

The whole design reduces to one question:

When do you do the work of assembling a feed — when a post is WRITTEN, or when the feed is READ?

Every component is a consequence of that answer; the celebrity problem is what happens when one answer stops working for a few users.

Contrast with the notification system: that was a funnel fighting flaky third parties. A feed has no third parties. Its difficulty is asymmetry — one person writes one post, thousands must see it, each opens the app many times a day. It's a fight between write cost and read cost.

2. Requirements (extract these)Copy Anchor Link

Senior questions to ask unprompted:

• Friends or followers? Friends = symmetric + capped (5,000) → worst post reaches 5,000 feeds → celebrity problem barely exists. Followers = asymmetric + uncapped → one post may need 100M deliveries → design must change. This one question tells the interviewer you know where it breaks.
• How fresh? "A few seconds late is fine" → fan-out can be asynchronous.
• Must I see my own post immediately? Always yes → read-your-own-writes (§8).

3. EstimationCopy Anchor Link

  Writes:  10M DAU × 2 posts/day  = 2×10⁷/day ÷ 10⁵  ≈ 200 posts/sec
  Reads:   10M DAU × 10 opens/day = 10⁸/day   ÷ 10⁵  ≈ 1,000 feed reads/sec, peak ×5 ≈ 5,000
  Hydrate: ~20 posts per read                       → ~20,000 post lookups/sec

→ ~200 posts created vs ~20,000 displayed per second ≈ 100:1 read:write by item → do the work on the write side so reads stay cheap.

The number that actually matters:

  Fan-out:  200 posts/sec × ~200 friends avg   ≈ 40,000 feed inserts/sec   → fine (sharded Redis)
            worst-case friend (5,000)          = 5,000 inserts per post   → fine
            celebrity with followers (100M)    = 100,000,000 per post     → the problem

Feed cache: ~500 IDs × 16 B × 10M active users ≈ 80 GB raw, a few hundred GB with Redis overhead → sharded cluster, nothing exotic.

4. High-level design — two flowsCopy Anchor Link

• Feed publishing: post written to DB + cache, then delivered into friends' feeds.
• News feed building: reader's feed assembled from friends' posts.

They meet at the news feed cache. Whether it exists and who fills it IS the "when do you do the work" question.

5. The central decision: pull vs push vs hybridCopy Anchor Link

5.1 Naive: fan-out on read (pull)Copy Anchor Link

The feed is a query:

SELECT * FROM posts WHERE author_id IN (<5,000 friend IDs>)
ORDER BY created_at DESC LIMIT 20;

Write = one insert. Breaks at scale:

• Every read does the full job — the expensive operation, 100× more often than writes.
• Sharding makes it worse — posts shard by author, friends are spread across every shard → scatter-gather; slowest shard sets latency.
• Unpredictable latency — 5,000-friend users (your most engaged) get the slowest feed.

5.2 Flip: fan-out on write (push)Copy Anchor Link

On post, insert the post ID into each friend's precomputed feed list. Read = one lookup of the top 20. With ~100:1 reads per write, push wins by default.

Breaks:

• The celebrity. 100M followers × 1 post = 100M inserts ≈ minutes of full cluster capacity. Everyone's posts queue behind it → one celebrity post makes the whole system stale, not just itself.
• Wasted work on inactive users. 70M of those 100M feeds are never read today but still cost writes and memory.

5.3 Fix: hybrid (what real systems do)Copy Anchor Link

Why pull is cheap here when it was the problem before:

1. You follow a handful of celebrities, not 5,000 → merge touches a few lists.
2. Celebrity timelines are the most-read objects → always hot in cache.

• Threshold is a tuning knob (trades write amplification vs read latency; examples cite ~10k followers) — say "a threshold we tune," not a constant.
• Skip inactive users (no login in ~30 days): no fan-out; rebuild their feed by pull on return, then resume push.

Framing: push pays at write time so reads are cheap; pull pays at read time so writes are cheap; the hybrid uses each where it's cheap.

6. Deep dive: the publishing flowCopy Anchor Link

1. Client — POST /v1/me/feed with content + auth token. Media uploaded separately to object storage via pre-signed URL; post carries URLs only.
2. Web servers — authenticate; rate-limit (500 posts/min = 500 fan-outs × thousands of feeds; the limit protects the fan-out system from one account).
3. Post service — write the post to the post DB (sharded) and post cache; append post_id to the author timeline (makes the celebrity pull work). Snowflake-style post_id. → Post is durable; user gets "posted". Everything below is asynchronous.
4. Fanout service — decides recipients:
   • follower IDs from the graph DB (book's choice; in practice often adjacency lists in a sharded KV/relational store — the need is fast, paged "all followers of X"),
   • celebrity author? → stop (pull path),
   • filter via user cache: muted, content settings, inactive 30+ days,
   • batch (~1,000 followers) → enqueue {post_id, author_id, [follower_ids]}.
5. Message queue — decouples decision from work; worker pool scales with posting volume; absorbs event bursts.
6. Fanout workers — for each follower, insert into their feed (§7).
7. News feed cache — IDs only, never content.

Why IDs, not content (say all three)Copy Anchor Link

7. Feed storage: the Redis sorted setCopy Anchor Link

A sorted set = unique members, each with a numeric score, kept in score order. Internally a hash table (member → score) + a skip list (by score). Ties ordered lexicographically by member string.

ZADD   feed:{uid}  {created_at_ms}  {post_id}     # fan-out insert, O(log N)
ZRANGE feed:{uid}  0 19 REV                       # newest 20
ZRANGE feed:{uid}  {cursor_ms} -inf BYSCORE REV LIMIT 0 21   # next page (inclusive, see below)
ZREMRANGEBYRANK feed:{uid} 0 -501                 # trim to newest 500

ZADD returns the number of new members; flags: NX (add only), XX (update only), GT/LT (update only if greater/less), CH, INCR.

Idempotent fan-out for free. The queue is at-least-once → a crashed worker's batch is redelivered → replayed inserts. Re-adding an existing member with the same score is a no-op; a set cannot hold a post twice. No dedup layer needed (contrast: the notification system needed one).

⚠️ The precision trap (score = ms timestamp, NOT the Snowflake ID)Copy Anchor Link

Scores are 64-bit floats → integers exact only up to 2⁵³ ≈ 9×10¹⁵. A Snowflake ID's timestamp sits in the top 41 bits, so it passes 2⁵³ about 25 days after the custom epoch (2⁵³ ÷ 2²² ms ≈ 2³¹ ms). Beyond that the low bits (sequence, part of machine ID) round away.

• Order survives — rounding never reverses order; ties fall back to the member string.
• Pagination breaks — near-simultaneous posts share a rounded score → exclusive cursor skips them, inclusive repeats them.

Fix: score = created_at in ms (exact for millennia), member = post_id, cursor = (score, post_id) of the last item shown. Same-ms ties: read inclusive on the cursor score, drop entries at that score whose post_id ≥ cursor post_id.

8. Deep dive: the read flowCopy Anchor Link

1. Request — GET /v1/me/feed?cursor=<ms,post_id>&limit=20 → web servers (auth) → newsfeed service.
2. Two sources in parallel — the user's sorted set (one round trip) + latest ~5 IDs from each followed celebrity's timeline (pipelined).
3. Merge — combine, sort by time, dedup, take 20. Also merge the reader's own recent posts → read-your-own-writes even if self-fan-out lags.
4. Hydrate — IDs → full objects via one multi-get per cache (post, user for name/avatar, counters, action for "did I like it"). 3 batched round trips ≈ 1.5 ms; 60 sequential ≈ 30 ms. Hydration also filters: deleted (tombstoned) posts and posts the reader may no longer see are dropped.
5. Respond — JSON + next_cursor. Media are URLs to a CDN, never bytes from your servers (media is 10–100× the text).

9. Pagination: cursor, not offsetCopy Anchor Link

• Offset = "skip 3, take 3" → anchored to a position. New posts at the top shift everything → duplicates; deletions → skips.
• Cursor = "older than P7" → anchored to a post. Unaffected by changes above.
• New posts at the top are a separate path: client polls or gets a signal (notification service) → "5 new posts" pill → fetch from the top.

10. Caching: five tiersCopy Anchor Link

Lesson: separate caches by access pattern, not entity. Content and like-count are the same entity; one is read-mostly, one is write-heavy — co-locating them makes each pattern hurt the other (1,600 invalidations/sec of the hottest key).

11. Consistency and edge casesCopy Anchor Link

Feed is eventually consistent by choice. Governing rule:

Fan-out decides what's likely relevant; the read path decides what's allowed.

12. Ranking (where the book stops)Copy Anchor Link

The read path becomes a funnel; fan-out stays, ranking is added on top:

  candidate gen   precomputed feed + celebrity pulls, ~500 candidates
  features        author affinity, age, engagement so far, media type
  light ranker    500 → ~100
  heavy ranker    score the 100
  re-rank         rules: diversity, ≤N posts per author in a row

Cost to mention: ordering is no longer by time → cursors get harder. Common fix: rank once per session, store the ranked snapshot briefly, page through it.

13. FailuresCopy Anchor Link

14. End-to-end trace (narrate it, then break it)Copy Anchor Link

  A (300 followers) posts a photo
  client ─► upload photo to object storage → URL
         ─► POST /v1/me/feed → auth, rate limit
         ─► post service: post_id 9001, DB + post cache, append to A's timeline → "posted" (~30 ms)
  async  ─► fanout: 300 follower IDs; not a celebrity → push
            drop 12 muted + 40 inactive → 248 → one batch on the queue
         ─► worker: 248 × ZADD (pipelined) + trim to 500 → in 248 feeds within ~100s of ms

  B opens the app
         ─► newsfeed svc: B's top 20 IDs (9001 near top) + latest 5 from each of B's 2 celebrities
         ─► merge, dedup, sort, take 20 → multi-get posts, authors, counts, B's likes
         ─► JSON + CDN URL for the photo (~50 ms)

  BREAK 1: worker dies after 150 of 248 → redelivered → replay all 248 →
           first 150 no-ops, 98 land → 9001 in every feed exactly once
  BREAK 2: celebrity (80M followers) posts at the same moment → flag → no fan-out,
           1 write to their timeline → A's post not delayed → followers pull it from a hot cache

15. Interview scriptCopy Anchor Link

  1. clarify      web+mobile · publish + view · chronological · 5,000 friends · 10M DAU · media
                  FRIENDS OR FOLLOWERS? freshness? see-own-post?               ← unprompted
  2. estimate     200 posts/s · 1k–5k reads/s · ~100:1 by item · 40k fan-out inserts/s
                  · 100M inserts for one celebrity post
  3. two flows    publishing + building; they meet at the feed cache
  4. pull         feed = a query → every read does the job, scatter-gather, slow heavy users
  5. push         reads 100× writes → precompute → breaks on celebrities + inactive users
  6. hybrid       push normal, pull celebrities, merge at read; skip inactive; tunable threshold ← unprompted
  7. publish      rate limit · persist + author timeline · fanout decides · queue · workers · IDs only
  8. storage      sorted set, ZADD idempotent, score = ms timestamp (float precision trap)
  9. read         two sources · merge + own posts · multi-get hydrate + filter · CDN
 10. paging       cursor, not offset
 11. caches       five tiers by access pattern; hot key; batched counters
 12. edges        delete / unfollow / follow / inactive / privacy → "read path decides what's allowed"
 13. extras       ranking funnel; failures; walk it end to end and break it yourself

Steps 1 (friends vs followers), 6 and 11 separate a pass from a strong pass.

16. The lines that earn the mostCopy Anchor Link

1. "Friends or followers? With a 5,000-friend cap the celebrity problem barely exists; with uncapped follows one post can need 100 million deliveries."
2. "Reads outnumber writes about 100 to 1 by item, so I pay at write time — fan-out on write is derived, not assumed."
3. "One celebrity post on push makes everyone's feed stale. Hybrid: push for normal authors, pull for celebrities, merge at read — their timelines are already the hottest objects in cache."
4. "The feed cache stores IDs, not content — memory, free edit/delete propagation, and a bounded list."
5. "Fan-out runs off the posting path on a queue; the queue is at-least-once but ZADD is idempotent, so redelivery can't duplicate a post."
6. "Score is the millisecond timestamp, not the Snowflake ID — sorted-set scores are doubles and a Snowflake ID loses precision past 2⁵³."
7. "Cursor, not offset — offsets are anchored to positions that shift as new posts land on top."
8. "I separate caches by access pattern: like counts are write-heavy and live apart from read-heavy post content."
9. "Fan-out decides what's likely relevant; the read path decides what's allowed."

17. Numbers to rememberCopy Anchor Link

18. Common follow-upsCopy Anchor Link

19. When NOT to go deepCopy Anchor Link

Inside a bigger product question ("design Instagram"), one sentence:

"Posts fan out on write into per-user sorted sets of post IDs in Redis, except celebrities, whose posts are pulled and merged at read time; the read path hydrates IDs from caches and serves media from a CDN."

Go deep only when the feed IS the question, or the interviewer pushes on celebrities, consistency or ranking.

20. Glossary (A–Z, one line each)Copy Anchor Link