Part 5 · 2 chapters · ~12 min

News Feed

Fan-out on write, fan-out on read and the hybrid for celebrity accounts, timeline caches, ranking and hydration, and skipping inactive users.

11

Brief, questions and numbers

the brief
  1. Users see a feed of posts from accounts they follow, newest and most relevant first.
questionanswer we assume
users?200M daily active
follow graph?median 200 followees; some accounts have 50M followers
freshness?seconds to a minute
ranking?yes, beyond chronological
reads vs writes?about 100 feed reads per post
code
posts      = 200M × 0.5/day ≈ 1,150/s
fan-out    = 1,150 × 200 median followers ≈ 230k timeline writes/s (without celebrities)
feed reads = 200M × 10/day ≈ 23k/s average, ~100k/s peak
timeline   = 800 ids × 8 B ≈ 6.4 KB per user × 200M ≈ 1.3 TB of cache
NEWS FEED: PUSH, PULL AND HYBRID
fan-out on write for most users, fan-out on read for accounts with millions of followers
new postauthorfan-out workerspush to followerscelebrity postsnot fanned outtimeline cacheper user, top 800 idsfeed readmerge + rankpost storeby id
swipe the figure sideways, or tap expand for full screen
1/5
fan-out on write
When a normal user posts, workers push the post id into each follower's timeline cache. Reading a feed is then one cache read: fast.
push ids into followers' timelinesreads become one cache lookup
12

v1, the break, and v2

v1. On each feed read, query all followees' recent posts from the database, merge and sort.

The break. A user following 500 accounts triggers a 500-way query per feed read, 100k times per second: impossible at this scale.

v2. Fan-out on write into per-user timeline caches for normal accounts, fan-out on read for celebrities, a ranking service over merged candidates, hydration from a cached post store, and no fan-out to inactive users.

the sentence
v2 buys fast feed reads at any follower distribution, and pays with heavy write amplification, a large cache, and complexity in the merge.