mufassall

Cheat sheet · Whole systems

Design a news feed

15 min · Advanced · mufassall.dtwin.uz/en/l/design-news-feed/

← Open the lesson

The problem

People post, and everyone who follows them should see it in their feed within seconds. We build the feed step by step: pull on read, push on write, the celebrity problem and a hybrid, ranking, media on a CDN, and what happens when the feed cache dies.

What you learn

  • Fan-out on read vs fan-out on write, and what each costs
  • Why a few huge accounts break push, and how a hybrid fixes it
  • A per-user feed cache that stores ids, not posts
  • Cursor pagination, ranking and media on a CDN
Final scene
20%55%55%35%40%50%10%

Diagram as code

The lesson's final design as text: paste it into Jira, GitLab, GitHub, Notion or your docs, where Mermaid renders by itself. There are D2 and PlantUML (Confluence, IntelliJ) versions too.

Mermaid: flowchart

flowchart LR
  n_author(["Author's app"])
  n_reader(["Reader's app"])
  n_api["Feed API"]
  n_db[("Posts #38; follows DB")]
  n_queue[["Post queue"]]
  n_fanout("Fan-out worker")
  n_feeds{{"Feed cache"}}
  n_cdn[/"CDN"\]
  n_media[("Media storage")]
  n_author --> n_api
  n_api --> n_db
  n_reader --> n_api
  n_api --> n_queue
  n_queue --> n_fanout
  n_fanout --> n_db
  n_fanout --> n_feeds
  n_api --> n_feeds
  n_api --> n_db
  n_reader --> n_cdn
  n_cdn --> n_media

Mermaid: request sequence

sequenceDiagram
  participant n_author as Author's app
  participant n_api as Feed API
  participant n_db as Posts #38; follows DB
  participant n_fanout as Fan-out worker
  participant n_feeds as Feed cache
  participant n_queue as Post queue
  participant n_reader as Reader's app
  participant n_cdn as CDN
  Note over n_author,n_api: Posting: one row, one id
  n_author->>n_api: POST /v1/posts HTTP/1.1
  n_api-->>n_author: HTTP/1.1 201 Created
  Note over n_api,n_db: Fan-out on read: build the feed when it is opened
  n_api->>n_db: SELECT p.id, p.author_id, p.created_at
  n_db-->>n_api: (50 rows)
  Note over n_api,n_db: Pull at scale: the database does it all, every time
  n_api->>n_db: EXPLAIN ANALYZE SELECT p.id ...
  n_db-->>n_api: Sort (top-N heapsort)
  Note over n_fanout,n_feeds: Fan-out on write: deliver at posting time
  n_fanout->>n_feeds: LPUSH feed:u_42 7393018847102976
  n_feeds-->>n_fanout: (integer) 801
  Note over n_api,n_feeds: Reading the feed is now one range read
  n_api->>n_feeds: LRANGE feed:u_42 0 49
  n_feeds-->>n_api: 1) #34;7393018847102976#34;
  Note over n_queue,n_fanout: A celebrity posts: 30 million inserts
  n_queue->>n_fanout: fanout post=7393102255110144 author=u_star
  Note over n_api,n_db: Hybrid: push for most, pull for the famous
  n_api->>n_db: SELECT id, author_id, created_at FROM posts
  n_db-->>n_api: (7 rows)
  Note over n_reader,n_api: Ranking and the cursor
  n_reader->>n_api: GET /v1/feed?limit=20#38;cursor=c_7f2a HTTP/1.1
  n_api-->>n_reader: HTTP/1.1 200 OK
  Note over n_reader,n_cdn: Photos come from a CDN, not the API
  n_reader->>n_cdn: GET /m/m_5521/720.webp HTTP/1.1
  n_cdn-->>n_reader: HTTP/1.1 200 OK
  Note over n_api,n_feeds: A feed cache node dies
  n_api->>n_feeds: LRANGE feed:u_42 0 49
  n_feeds-->>n_api: (error) connection refused

D2

direction: right

n_author: "Author's app" {
  shape: rectangle
}
n_reader: "Reader's app" {
  shape: rectangle
}
n_api: "Feed API" {
  shape: rectangle
}
n_db: "Posts & follows DB" {
  shape: cylinder
}
n_queue: "Post queue" {
  shape: queue
}
n_fanout: "Fan-out worker" {
  shape: rectangle
  style.multiple: true
}
n_feeds: "Feed cache" {
  shape: hexagon
}
n_cdn: "CDN" {
  shape: oval
}
n_media: "Media storage" {
  shape: stored_data
}

n_author -> n_api
n_api -> n_db
n_reader -> n_api
n_api -> n_queue
n_queue -> n_fanout
n_fanout -> n_db
n_fanout -> n_feeds
n_api -> n_feeds
n_api -> n_db
n_reader -> n_cdn
n_cdn -> n_media

PlantUML: request sequence

@startuml
participant "Author's app" as n_author
participant "Feed API" as n_api
database "Posts & follows DB" as n_db
participant "Fan-out worker" as n_fanout
collections "Feed cache" as n_feeds
queue "Post queue" as n_queue
participant "Reader's app" as n_reader
participant "CDN" as n_cdn
note over n_author, n_api : Posting: one row, one id
n_author -> n_api : POST /v1/posts HTTP/1.1
n_api --> n_author : HTTP/1.1 201 Created
note over n_api, n_db : Fan-out on read: build the feed when it is opened
n_api -> n_db : SELECT p.id, p.author_id, p.created_at
n_db --> n_api : (50 rows)
note over n_api, n_db : Pull at scale: the database does it all, every time
n_api -> n_db : EXPLAIN ANALYZE SELECT p.id ...
n_db --> n_api : Sort (top-N heapsort)
note over n_fanout, n_feeds : Fan-out on write: deliver at posting time
n_fanout -> n_feeds : LPUSH feed:u_42 7393018847102976
n_feeds --> n_fanout : (integer) 801
note over n_api, n_feeds : Reading the feed is now one range read
n_api -> n_feeds : LRANGE feed:u_42 0 49
n_feeds --> n_api : 1) "7393018847102976"
note over n_queue, n_fanout : A celebrity posts: 30 million inserts
n_queue -> n_fanout : fanout post=7393102255110144 author=u_star
note over n_api, n_db : Hybrid: push for most, pull for the famous
n_api -> n_db : SELECT id, author_id, created_at FROM posts
n_db --> n_api : (7 rows)
note over n_reader, n_api : Ranking and the cursor
n_reader -> n_api : GET /v1/feed?limit=20&cursor=c_7f2a HTTP/1.1
n_api --> n_reader : HTTP/1.1 200 OK
note over n_reader, n_cdn : Photos come from a CDN, not the API
n_reader -> n_cdn : GET /m/m_5521/720.webp HTTP/1.1
n_cdn --> n_reader : HTTP/1.1 200 OK
note over n_api, n_feeds : A feed cache node dies
n_api -> n_feeds : LRANGE feed:u_42 0 49
n_feeds --> n_api : (error) connection refused
@enduml

PlantUML: components

@startuml
left to right direction
agent "Author's app" as n_author
agent "Reader's app" as n_reader
component "Feed API" as n_api
database "Posts & follows DB" as n_db
queue "Post queue" as n_queue
collections "Fan-out worker" as n_fanout
stack "Feed cache" as n_feeds
frame "CDN" as n_cdn
storage "Media storage" as n_media
n_author --> n_api
n_api --> n_db
n_reader --> n_api
n_api --> n_queue
n_queue --> n_fanout
n_fanout --> n_db
n_fanout --> n_feeds
n_api --> n_feeds
n_api --> n_db
n_reader --> n_cdn
n_cdn --> n_media
@enduml

Recap

A feed is a trade between work on write and work on read.

1) Pull is simple but rebuilds every feed on every open. 2) Push makes reads one cache range, at a cost per follower on write. 3) Big accounts are pulled at read time and merged. 4) Feed lists hold ids, are capped and can always be rebuilt. 5) Rank a few hundred candidates, page by cursor, and serve media from a CDN.

Numbers: at the start and at the end

MetricStartEnd
Feed load p9980 ms60 ms
Feed inserts0/s1 800/s
Time to reach followers0 s2 s

Steps

  1. Case Posting: one row, one id

    The author sends text and the ids of photos uploaded earlier.

  2. Case Fan-out on read: build the feed when it is opened

    The simplest feed: when a reader opens the app, find everyone they follow, take their recent posts, sort by time and return the top 50.

  3. Problem Pull at scale: the database does it all, every time

    20 million readers open the feed about 10 times a day: 2 300 feed builds/s on average, around 10 000 at the evening peak.

  4. Fix Fan-out on write: deliver at posting time

    Flip it: when someone posts, a queue hands the post to a fan-out worker.

  5. Case Reading the feed is now one range read

    The API reads the first 50 ids of feed:u_42, then fetches those posts by id from a post cache (most are hot) and returns them.

  6. Problem A celebrity posts: 30 million inserts

    An account with 30 million followers posts.

  7. Fix Hybrid: push for most, pull for the famous

    Accounts above 100 000 followers are not fanned out.

  8. Case Ranking and the cursor

    A strict time order buries posts from close friends under noise.

  9. Fix Photos come from a CDN, not the API

    Images are most of the bytes.

  10. Problem A feed cache node dies

    One node of the feed cache goes down.

  11. Fix Fall back to pull, rebuild in the background

    For users whose list is missing, the API falls back to pull: recent posts of followed authors, last two days only.

  12. Recap Recap

    A feed is a trade between work on write and work on read.

Terms

Fan-out (on write / on read)
Fan-out on write pushes a new post's id into every follower's feed cache at posting time; fan-out on read builds the feed when it is opened. A hybrid works best: push for most, pull for huge accounts.