system design · system-design

Design Meta News Feed, Fan-out at Scale

Meta's E5+ Product Design canon. Push (fan-out-on-write) vs Pull (fan-out-on-read) vs hybrid. The interviewer wants the trade-off math, not a buzzword tour.

hard4hgeneralkafkaredissystem-design
Ask GPTConfidence

Theory

Explanation

Intuition first, formal definition second. Skim the bullets if you already know this; read the prose if you don't.

Two opposing strategies share the same goal: deliver each user a fresh, ranked feed in ≤200 ms. Push pre-computes feeds at post time (write-amplified, read-cheap). Pull assembles feeds at read time (read-amplified, write-cheap). Real systems do both, push for the long tail, pull for celebrities, because neither alone scales when one author has 200M followers and another has 12.

Push (fan-out-on-write): when user A posts, the post-id is enqueued and fanned out into per-follower feed inboxes (sorted set keyed by follower_id). Read = O(1) lookup + ranking. Pull (fan-out-on-read): on read, fetch followee post lists, merge top-K via heap, rank. Hybrid: classify authors. High-follower authors are pull-only (skip fan-out at write); low-follower authors are push. The reader's feed = merge(push_inbox, pull_celebrity_posts) → ranker → response.

When to use

Any consumer feed product: Facebook, Twitter/X, Instagram, LinkedIn home, TikTok For You, Pinterest, news aggregators. The pattern repeats whenever you compose a personalized stream from many producers.

When not to

When the feed is the same for everyone (top stories), just cache one rendered feed. When write rate ≤ read rate (rare for feeds). When latency is forgiving (minutes), a batch ranker is cheaper than fan-out.

Time: Read O(K log F_celeb) hybrid, Write O(F_user) · Space: O(N_users * inbox_size)

flowchart TB
  subgraph Write Path
    A[Post API] --> Classify{Author followers > 100k?}
    Classify -- yes --> Skip[/Skip fan-out · pull-only/]
    Classify -- no --> FanQ[[Fan-out Queue · Kafka]]
    FanQ --> Workers[Fan-out Workers]
    Workers --> Inbox[(Per-follower Inbox · Redis ZSET)]
  end
  subgraph Read Path
    R[Feed API] --> Merge[/Merger/]
    Merge --> Inbox
    Merge --> Pull[(Celebrity Post Index)]
    Merge --> Ranker{{Ranker / ML}}
    Ranker --> Cache[(Edge Cache)]
    Cache --> User([User])
  end
  A --> Post[(Post Store · TAO)]
  Pull -.async indexed.-> Post

Key insights

  • Hybrid is the answer. Pure push collapses on celebrities (one post → 200M writes); pure pull collapses on average users (heap merge over 500 followees per read).
  • Inbox storage = users × avg followees × posts/day × retention. At 3B users, 200 avg followees, 0.1 posts/day, 7 days = 4.2T inbox entries. Use TTL eviction + bounded inbox (top-N).
  • Ranking happens AFTER merge, not at fan-out time. Fan-out moves bytes; ranking moves intelligence. Decoupling lets you A/B ranker models without touching delivery.
  • Pagination via cursor (post_id + score), never offset, offsets break when new posts arrive.
  • Edge caching at the user level is dangerous (cold cache after timeline write). Cache the rendered feed only for short windows (30–120 s) or per-session.
  • Quantify the celebrity problem: define threshold F* where O(F) write cost ≥ O(K log F) read cost across all the celebrity's followers. Typically F* ≈ 10K–100K.