Cheat sheet · Whole systems
Design a news feed
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
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_mediaMermaid: 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 refusedD2
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_mediaPlantUML: 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
@endumlPlantUML: 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
@endumlRecap
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
| Metric | Start | End |
|---|---|---|
| Feed load p99 | 80 ms | 60 ms |
| Feed inserts | 0/s | 1 800/s |
| Time to reach followers | 0 s | 2 s |
Steps
- Case Posting: one row, one id
The author sends text and the ids of photos uploaded earlier.
- 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.
- 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.
- Fix Fan-out on write: deliver at posting time
Flip it: when someone posts, a queue hands the post to a fan-out worker.
- 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. - Problem A celebrity posts: 30 million inserts
An account with 30 million followers posts.
- Fix Hybrid: push for most, pull for the famous
Accounts above 100 000 followers are not fanned out.
- Case Ranking and the cursor
A strict time order buries posts from close friends under noise.
- Fix Photos come from a CDN, not the API
Images are most of the bytes.
- Problem A feed cache node dies
One node of the feed cache goes down.
- 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.
- 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.