System Design Interview · 第 11 章Triton 覆蓋度:🟡 中Triton 線
Design A News Feed System
你的首頁,是誰先幫你排好的?
原書把動態牆拆成兩條流程:發文時把貼文 ID 推進每個朋友的 feed cache(fanout),讀取時拿出 ID 再補齊作者和內容。Triton 沒有一篇專講 news feed 的文章,但他的講義剛好寫到這章每個零件會壞的地方:一筆一筆補作者、用 offset 分頁、cache 一過期 DB 就被打爆、名人那一個 key 永遠只住在一台機器。
給文組
全程只用「班長發聯絡單」,一階一階爬 12 個概念。頁首標 延伸基礎 的頁是補基礎,懂的人可以跳過。另有 push/pull 模擬器、N+1 計時器、新貼文插隊的分頁實驗。
給工程師
原書 8 張圖全部依圖說與描述重繪,有流程的都能播放。最後一頁列出引述的出處檔案(materials/core)與原書段落對照。
標籤怎麼看
📖 原書 🗣️ Triton 本人說 🔭 依 Triton 原則推論 📝 上課筆記 📅 2026 補充
先用生活理解班長發聯絡單
聯絡單要塞進每個人的抽屜,還是貼在公佈欄?
班長有一張聯絡單要給全班。兩種做法:
- 塞抽屜:班長影印 12 份,一個一個塞進同學的抽屜。班長很累,但同學一打開抽屜就看到。這是 fanout on write(push)。
- 貼公佈欄:班長只貼一張。輕鬆,但每個同學想看時要自己走過去。這是 fanout on read(pull)。
抽屜 = 每個人的 news feed cache;公佈欄 = 發文者自己的貼文列表。現在把「全班 12 人」換成「全國 1000 萬人」:班長要印 1000 萬份嗎?這就是本章的 名人問題。
學習地圖本章的概念階梯
今天爬 12 階。每一階只用前面講過的東西。
- 1cache手邊的小抄
- 2push / pull塞抽屜或貼公佈欄
- 3名人問題校長的 1,200 份
- 4graph DB畫滿線的通訊錄
- 5MQ待辦籃
- 6feed cache抽屜只放編號
- 7hydrate照編號拿全文
- 8cursor夾一張書籤
- 9PK 順序檔案夾怎麼排
- 10stampede80 人衝辦公室
- 11hot key全校搶同一份
- 12TTL小抄的保存期限
第 1–3 階 · 聯絡單怎麼送
要回答:塞抽屜還是貼公佈欄?校長怎麼辦?
第 4–6 階 · 送給誰、誰來送
要回答:系統怎麼知道朋友是誰?抽屜裡放什麼?
第 7–9 階 · 打開抽屜之後
要回答:編號怎麼變回動態?往下滑怎麼翻頁?
第 10–12 階 · 熱門公告
要回答:全校同時搶同一份,誰先倒?
全程只用一個情境:班長發聯絡單
每爬 3 階,有一頁「到這裡你已經會了」。
原書 Step 1什麼是 news feed · 釐清需求 · Figure 1
先問清楚:誰看、看什麼、排序、規模
這一步要解決的問題動態牆要給誰看、怎麼排、多少人用?這些決定了後面要不要預先算好。
📖 原書 應徵者 × 面試官
| 應徵者問 | 面試官答 |
|---|---|
| Mobile app、web app,還是都要? | 都要 |
| 最重要的功能是什麼? | 使用者可以發文,並在 news feed 頁看到朋友的貼文 |
| 依時間倒序,還是依主題分數(例如好朋友的分數高)? | 簡化起見,依時間倒序(reverse chronological) |
| 一個人最多幾個朋友? | 5000 |
| 流量多大? | 10 million DAU |
| 只有文字,還是有圖片、影片? | 可以有媒體檔,圖片和影片都有 |
白話:時間倒序=最新的在最上面;DAU=每天有幾個人用(daily active users),1000 萬 DAU 的估法見第 2 章第 22 頁。
📖 原書 類似的面試題:設計 Facebook news feed、Instagram feed、Twitter timeline。
📖 原書 引用 Facebook 說明頁的定義:news feed 是「首頁中間不斷更新的故事列表」,包括你追蹤的人、專頁、社團的狀態更新、照片、影片、連結、app 活動和按讚。
Figure 1 是三則上下排列的動態,每則有來源 icon、標題和內文,第二則多了一個影片播放器。
延伸基礎第 1 階 · cache懂的人可以跳過
- cache
- push / pull
- 名人問題
- graph DB
- MQ
- feed cache
- hydrate
- cursor
- PK 順序
- stampede
- hot key
- TTL
同學的電話,每次都跑去教務處查嗎?
① 先想像
每次查同學電話都跑教務處,來回 2 分鐘。抄一份放鉛筆盒,看一眼 2 秒。
你猜猜看:這學期要查 30 次,跑教務處和看小抄各花多久?
30 × 2 分 = 60 分;30 × 2 秒 = 60 秒。代價是同學換號碼時,小抄不會自己更新。
③ 這叫做 cache、database
cache:放在手邊的小抄,拿得快,但不是正本。database(DB):教務處的正本名冊,最可靠、最慢。
④ 跟這章的關係
這章到處都是 cache:Post Cache、User Cache、News Feed Cache。完整版見第 1 章第 18 頁(保溫台)。
② 動手玩:查 30 次電話
前幾章講過的零件,一句話複習
- request、API:送出去的一張單子/店家公開的窗口(第 4 章第 4 頁)
- load balancer:帶位員,把人分給好幾台 server(第 1 章第 12 頁)
- CDN:開在你家附近、放圖片影片的分店(第 1 章第 21 頁)
原書 Step 2兩個流程 · Newsfeed APIs
兩條流程、兩支 API
這一步要解決的問題使用者只做兩件事:發文、看動態。app 要用什麼「窗口」跟 server 說?
📖 原書 設計分成兩個流程
- Feed publishing:使用者發文時,資料寫進 cache 和資料庫;貼文被放進她朋友的 news feed。
- Newsfeed building:簡化起見,把朋友的貼文依時間倒序聚合起來就是 news feed。
📖 原書 API 是 client 和 server 溝通的主要方式
都是 HTTP API,可以發文、拿 news feed、加朋友等。原書只談最重要的兩支:
| API | 參數 |
|---|---|
POST /v1/me/feedFeed publishing API | content:貼文文字auth_token:驗證 API request |
GET /v1/me/feedNewsfeed retrieval API | auth_token:驗證 API request |
白話:POST=送東西過去(發文);GET=拿東西回來(看動態);auth_token=證明「你是你」的通行證;JSON=server 回給 app 的資料格式。
動手試:你發文,朋友來讀
request 依原書的 API;回應原書只說是 JSON,欄位是本簡報的示意。
原書 Step 2High-level design · Figure 2–3
發文怎麼走、讀 feed 怎麼走
這一步要解決的問題一個 request 從手機出發,要經過哪些機器?發文和讀 feed 走的路一樣嗎?
📖 Figure 2 發文
- User:瀏覽器或 app,送
/v1/me/feed?content=Hello&auth_token={auth_token} - Load balancer:把流量分給 web servers
- Web servers:把流量導到不同的內部服務
- Post service:貼文存進資料庫和 cache
- Fanout service:把新內容推到朋友的 news feed;feed 資料存在 cache 方便快速讀取
- Notification service:通知朋友有新內容、送推播
📖 Figure 3 讀 feed
- User 送
/v1/me/feed→ Load balancer → Web servers - Newsfeed service:從 cache 拿 news feed
- Newsfeed cache:存「畫出 news feed 需要的 feed ID」
白話:DNS=把網址翻成機器地址的查號台;service=專做一件事的一組程式;fanout=把貼文送到每個朋友那裡(下一頁)。
延伸基礎第 2 階 · push / pull懂的人可以跳過
- cache
- push / pull
- 名人問題
- graph DB
- MQ
- feed cache
- hydrate
- cursor
- PK 順序
- stampede
- hot key
- TTL
聯絡單:一份一份塞抽屜,還是貼一張在公佈欄?
① 先想像
全班 12 人,每人每天看 3 次聯絡單。班長可以一份一份塞抽屜,也可以只貼一張在公佈欄。
你猜猜看:貼公佈欄的話,全班一天總共要走幾趟去看?
12 人 × 3 次 = 36 趟。塞抽屜的話班長跑 12 趟,同學一趟都不用走。
③ 這叫做 fanout、push / pull
fanout:把一篇貼文送到每個朋友那裡。push(fanout on write)發文時就塞好;pull(fanout on read)要看時才去拉。
④ 跟這章的關係
原書兩種都講,最後選混合(第 11 頁)。寫的時候多做事、讀的時候少做事,就是 push。
② 動手玩:誰比較累?
原書 Step 3Feed publishing deep dive · Figure 4
發文的詳細設計:web servers 把關,fanout 分五步
這一步要解決的問題誰可以發文、一分鐘能發幾篇?貼文要怎麼送到 5000 個朋友手上?
📖 原書 Web servers
除了和 client 溝通,還負責 authentication 和 rate-limiting:只有帶有效 auth_token 登入的使用者能發文;系統限制使用者在一段時間內能發幾篇,用來擋 spam 和濫用內容。
白話:authentication=驗明正身;rate-limiting=門口的保全,見第 4 章。
📖 原書 Fanout service
Fanout 是「把一篇貼文送到所有朋友那裡」的過程。有兩種模型:fanout on write(push)和 fanout on read(pull),第 11 頁比較。限流怎麼做見第 4 章簡報。
白話:圖上的 Graph DB=記誰跟誰是朋友的通訊錄(第 14 頁);Message Queue=待辦籃(第 15 頁);Fanout Workers=從待辦籃拿工作的小幫手。
延伸基礎第 3 階 · 名人問題懂的人可以跳過
- cache
- push / pull
- 名人問題
- graph DB
- MQ
- feed cache
- hydrate
- cursor
- PK 順序
- stampede
- hot key
- TTL
校長也要發聯絡單:全校 1,200 份,要塞多久?
① 先想像
塞一個抽屜要 1 秒。班長的 12 份,12 秒塞完。校長的公告要給全校 1,200 人。
你猜猜看:一份一份塞,最後一位學生要等多久才看到?
1,200 × 1 秒 = 1,200 秒 = 20 分鐘。換成 1000 萬粉絲的明星,要塞 115 天。
③ 這叫做 hotkey problem、hybrid
hotkey problem(名人問題):粉絲太多,push 要寫的份數爆炸。hybrid:一般人照 push,名人改成貼公佈欄(pull)。
④ 跟這章的關係
原書的選擇就是 hybrid(第 11 頁),第 12 頁的模擬器把數字放大到 1000 萬。
② 動手玩:誰發的聯絡單?
原書 Step 3Fanout on write vs fanout on read · Hybrid
寫的時候先算好,還是讀的時候再算?
這一步要解決的問題塞抽屜和貼公佈欄各有代價。原書怎麼比、最後怎麼選?
📖 原書 Fanout on write(push)
寫入時就把 news feed 算好。新貼文一發出,馬上送進朋友的 cache。
- ✓ news feed 即時產生,可以立刻推給朋友
- ✓ 讀 feed 很快,因為寫入時已經算好
- ✗ 朋友很多時,拿好友清單、替每個人產生 feed 又慢又耗時,原書稱為 hotkey problem
- ✗ 不活躍、很少登入的使用者,替他們先算好是浪費運算資源
📖 原書 Fanout on read(pull)
讀取時才產生 news feed,是 on-demand 模型。使用者打開首頁時才去拉最近的貼文。
- ✓ 對不活躍、很少登入的使用者比較好,不會浪費運算資源
- ✓ 資料不推給朋友,所以沒有 hotkey problem
- ✗ 讀 news feed 很慢,因為沒有預先算好
📖 原書的選擇 Hybrid
快速讀 feed 最重要,所以大多數使用者用 push;名人或朋友/追蹤者很多的人,讓追蹤者讀的時候自己拉(on-demand),避免系統過載。原書也說 consistent hashing 能讓 request/資料分布得比較平均,有助於緩解 hotkey problem(Triton 對這句的看法見第 34 頁)。
原書 Step 3 · 動手玩Push / Pull / Hybrid 模擬器
發文的人有 1000 萬粉絲時,push 會發生什麼事?
這一步要解決的問題把上一頁的優缺點變成數字:粉絲多少開始撐不住?hybrid 省了什麼?
示意假設(不是原書數字):fanout workers 合計每秒寫 10 萬筆;讀 feed cache 2ms;pull 每 100 位追蹤對象一次批次查詢、每次 5ms;Hybrid 的名人門檻 1 萬粉絲。
到這裡你已經會了小結 1 / 4
- cache
- push / pull
- 名人問題
- graph DB
- MQ
- feed cache
- hydrate
- cursor
- PK 順序
- stampede
- hot key
- TTL
到這裡你已經會了:聯絡單怎麼送
- 常用的資料抄一份放手邊,就是 cache;正本在 database。
- 發文時先塞進每個人的抽屜是 push,要看時才去公佈欄拉是 pull。push 讀得快、寫得累。
- 粉絲太多的人,push 要塞的份數爆炸(名人問題)。原書的解法是 hybrid:名人改用 pull。
下一階要解決的問題
班長發一篇文,系統怎麼知道要塞給誰?誰來塞?抽屜裡又放什麼?
延伸基礎第 4 階 · graph DB懂的人可以跳過
- cache
- push / pull
- 名人問題
- graph DB
- MQ
- feed cache
- hydrate
- cursor
- PK 順序
- stampede
- hot key
- TTL
誰跟誰是朋友?一張畫滿線的通訊錄
① 先想像
這本通訊錄不是一列名字,而是一張圖:每個人是一個點,是朋友就連一條線。
你猜猜看:小美的朋友是阿明、小華;阿明的朋友是小美、小強。誰可以「推薦給小美當朋友」?
小強是阿明的朋友,但還不是小美的朋友。推薦朋友,就是沿著線多走一步。
③ 這叫做 graph、graph database
graph:點和線組成的關係圖。graph database:專門存這種圖、擅長「沿著線走」的資料庫,例如 Neo4j。
④ 跟這章的關係
原書 fanout 第 1 步:從 graph DB 拿朋友 ID(第 16 頁)。Triton 會問:只拿朋友清單,一般 DB 不行嗎?(第 24 頁)
② 動手玩:點一個人
延伸基礎第 5 階 · MQ懂的人可以跳過
- cache
- push / pull
- 名人問題
- graph DB
- MQ
- feed cache
- hydrate
- cursor
- PK 順序
- stampede
- hot key
- TTL
5,000 份要塞,班長要站著等塞完才回座位嗎?
① 先想像
班長寫一張「幫我塞給這 5,000 人」放進待辦籃,就回座位。小幫手們從籃子裡拿工作,慢慢塞。
你猜猜看:塞一份 1 秒。班長自己塞完才回座位,要站多久?放進待辦籃呢?
工作量沒變,只是班長不用站著等。5 位小幫手一起塞,1,000 秒塞完。
③ 這叫做 message queue、worker
message queue(MQ):待辦籃,工作先排隊。worker:從籃子拿工作來做的小幫手。
④ 跟這章的關係
原書 fanout 第 3–4 步就是這樣(第 16 頁)。完整版見第 1 章第 30 頁(修照片)。
② 動手玩:給 5,000 位朋友
原書 Step 3Fanout service · Figure 5
Fanout service 的五個步驟
這一步要解決的問題貼文要送給誰?誰被靜音?5000 份由誰來寫?
📖 原書 運作方式
- 從 graph database 拿朋友 ID。Graph DB 適合管理朋友關係和朋友推薦(原書參考資料 [2]:Neo4j 與 SQL Server 的 friend-of-friend 推薦)。
- 從 user cache 拿朋友資訊,再依使用者設定過濾。例如你把某人靜音,即使還是朋友,她的貼文也不會出現在你的 feed;使用者也可能只分享給特定朋友、對其他人隱藏。
- 把朋友清單和新貼文 ID 送進 message queue。
- Fanout workers 從 MQ 取出資料,把 news feed 資料存進 news feed cache。
- 在 news feed cache 存
<post_id, user_id>(下一頁 Figure 6)。
延伸基礎第 6 階 · feed cache懂的人可以跳過
- cache
- push / pull
- 名人問題
- graph DB
- MQ
- feed cache
- hydrate
- cursor
- PK 順序
- stampede
- hot key
- TTL
抽屜放不下:只放一張「編號便條」
① 先想像
整張聯絡單(全文加照片)很佔空間。一張寫著「第 205 號,班長發的」的便條,只佔一小格。
你猜猜看:抽屜有 32 格。整張佔 16 格,便條佔 1 格。各放得下幾張?
32 ÷ 16 = 2;32 ÷ 1 = 32。全文放在資料櫃,要看時照編號去拿(第 7 階)。
③ 這叫做 news feed cache、ID
news feed cache:每人一個抽屜,放貼文的編號。ID:每篇貼文、每個人的號碼,例如 post_id、user_id。
④ 跟這章的關係
原書 Figure 6 就是這個抽屜:一張 <post_id, user_id> 表,還有上限(下一頁)。
② 動手玩:塞新聯絡單進抽屜
原書 Step 3News feed cache · Figure 6
每個人的 feed cache:只存 <post_id, user_id>
這一步要解決的問題1000 萬人每人一個抽屜,抽屜裡放什麼、放多少,記憶體才夠?
每有新貼文就 append 進表;超過上限,最舊的那筆被丟掉。
📖 原書 為什麼只存 ID
- 可以把 news feed cache 想成一張
<post_id, user_id>對應表,新貼文 append 進去 - 把整個 user 和 post 物件放進 cache,記憶體會非常大,所以只存 ID
- 設一個可設定的上限讓記憶體保持小
- 使用者滑過幾千篇的機率很低,大多數人只看最新的,所以 cache miss rate 很低
算算看:1000 萬 DAU 的 feed cache 要多大
80 GB
到這裡你已經會了小結 2 / 4
- cache
- push / pull
- 名人問題
- graph DB
- MQ
- feed cache
- hydrate
- cursor
- PK 順序
- stampede
- hot key
- TTL
到這裡你已經會了:發一篇文,背後跑了什麼
- 誰跟誰是朋友,記在點和線的通訊錄(graph DB)。fanout 第一步就是去查它。
- 要塞 5,000 份,發文的人不用等:工作放進待辦籃(MQ),小幫手(worker)慢慢塞。
- 每個人的抽屜(news feed cache)只放編號便條 <post_id, user_id>,有上限,滿了丟最舊的。
下一階要解決的問題
抽屜裡只有編號。打開首頁時,要怎麼把編號變回有名字、照片、全文的動態?
延伸基礎第 7 階 · hydrate懂的人可以跳過
- cache
- push / pull
- 名人問題
- graph DB
- MQ
- feed cache
- hydrate
- cursor
- PK 順序
- stampede
- hot key
- TTL
抽屜裡只有編號:要跑幾趟,才看得到全文?
① 先想像
打開抽屜,10 張編號便條。全文在「貼文櫃」,作者照片在「學生資料櫃」。每跑一趟 1 分鐘。
你猜猜看:一張一張拿,每張都要跑兩個櫃子。總共幾趟?
10 張 × 2 個櫃子 = 20 趟。先把 10 個編號列成一張清單,兩個櫃子各跑一次,只要 2 趟。
③ 這叫做 hydrate、round trip
hydrate:把編號補成完整內容,像泡麵加水泡開。round trip:去一趟再回來;每一趟都要時間。
④ 跟這章的關係
原書讀 feed 的第 5 步就是 hydrate,但沒說怎麼拿(下一頁)。Triton 的答案在第 25 頁;「一趟拿齊」另見第 2 章第 34 頁。
② 動手玩:把便條變成全文
原書 Step 3Newsfeed retrieval deep dive · Figure 7
讀 feed:先拿 ID,再補齊成完整的動態
這一步要解決的問題抽屜裡只有編號。打開首頁時,怎麼變回有名字、照片、全文的動態?
📖 原書 六個步驟
- 使用者送 request 拿 news feed:
/v1/me/feed - Load balancer 把 request 分給 web servers
- Web servers 呼叫 news feed service
- News feed service 從 news feed cache 拿一串 post ID
- news feed 不只是 ID,還有使用者名稱、大頭照、貼文內容、貼文圖片等,所以要從 user cache 和 post cache 拿完整的 user 與 post 物件,組成 fully hydrated 的 news feed
- 完整的 news feed 以 JSON 回給 client 去 render
圖片、影片這些媒體內容存在 CDN,讀得快。第 5 步要「怎麼拿」原書沒寫,Triton 的答案在第 25 頁。
原書 Step 3Cache architecture · Figure 8
Cache 分五層,各存各的
這一步要解決的問題一則動態除了貼文,還有讚數、你按過讚沒。這些小抄要怎麼分類放?
📖 原書 Cache 對 news feed 系統極為重要,原書把 cache tier 分成五層:
- News Feed:存 news feed 的 ID
- Content:存每一篇貼文的資料;熱門內容放 hot cache
- Social Graph:存使用者之間的關係資料
- Action:存使用者有沒有對貼文按讚、回覆或其他動作
- Counters:存按讚數、回覆數、follower 數、following 數等計數器
點左邊任一層,看它在前面哪一張圖出現過。
原書 Step 4Wrap up
原書的收尾:還有時間就談 scalability
這一步要解決的問題主體設計完,面試官常問:使用者再變多 10 倍怎麼辦?
📖 原書 設計回顧
兩個流程:feed publishing 與 news feed retrieval。和所有系統設計題一樣,沒有完美的設計;每家公司有自己的限制,要設計符合那些限制的系統,並理解設計與技術選擇的取捨。
📖 原書 Scaling the database
- Vertical scaling vs Horizontal scaling
- SQL vs NoSQL
- Master-slave replication
- Read replicas
- Consistency models
- Database sharding
白話(都在第 1 章講過):vertical/horizontal scaling=換大鍋/多請廚師(第 1 章第 11 頁);replication=把帳本影印幾本(第 1 章第 14 頁);sharding=名冊分成好幾本(第 1 章第 34 頁)。
📖 原書 Other talking points
- Keep web tier stateless
- Cache data as much as you can 🗣️ Triton:要設 TTL、防 stampede,第 32 頁
- Support multiple data centers
- Loosely coupled components with message queues 🗣️ 見第 24 頁
- Monitor key metrics:例如尖峰時段的 QPS、使用者刷新 news feed 時的延遲
白話:stateless=web server 不記客人的事,誰接都一樣(第 1 章第 24 頁);multiple data centers=在別的城市開分店(第 1 章第 28 頁)。
📅 2026 補充 排序已經不是時間倒序
原書為了簡化假設「依時間倒序」。今天主流社群平台的 feed 多半由排序模型決定順序,這屬於另一本書的題目(本系列 05 ML System Design 的 Personalized news feed 章)。本章的 fanout、cache、hydrate 結構仍然適用:排序模型通常吃的也是一批候選 ID。
原書參考資料:[1] Facebook〈How News Feed Works〉說明頁;[2] Friend of Friend recommendations with Neo4j and SQL Server。
Triton 同意feed 本來就該預先算好
✅ 預先算好、只存 ID、用 MQ 慢慢推:方向都對
你猜猜看:Triton 常罵「別亂用 MQ」。原書在 fanout 用 MQ,他怎麼看?
他列的 MQ 三個理由,fanout 剛好符合兩個(右邊)。
「Data fan-out:Data Materialization的再進一步。例子: facebook newsfeed:每人的 newsfeed都是預先計算,而不是即時地查詢的;用簡單的 Range Scan on PK 便可以。今天 Disk Volume不值錢, Disk IO才值錢」🗣️ Triton 本人說 072-lesson3.pdf.md · RDBMS 課程 v2 第三課 p.12
Triton 拿的例子就是本章。他的理由比原書多一句:空間便宜、IO 貴,所以多存幾份 feed 換讀取時少跑 IO,是划算的。原書的 push 模型就是這筆交易。
「在ActivityHistory的 record內只存了UserID,在顯示給用戶之前,要從 redis以UserID拿回該User的 displayName」🗣️ 088-redis-intro.pdf.md · p.13:跟原書 Figure 6「只存 ID」是同一個做法,差別在怎麼補回來(第 25 頁)
MQ 用在 fanout:符合 Triton 的三個理由之二
「把工作先丟MQ再慢慢處理,一般而且有3個原因:1 這Request需要拿大量資源,而且很可能跑很久,不適合在App. Server上直接來跑。……2 這工作是慢慢做也死不了人的,我想把MQ當成一個buffer,讓peak hours的工作可以在non-peak hours時來做。」🗣️ 185-電商用 queue-.md
🔭 推論 替 5000 個朋友寫 feed 是「拿大量資源、可能跑很久」;朋友晚幾秒看到「死不了人」。這兩條都成立,所以原書在這裡用 MQ,跟 Triton 反對「購物用 MQ」並不衝突。
🔭 推論 Graph DB 一定要嗎?
原書上限 5000 個朋友。Triton 的習慣是先問 N:「了解 N (像是 QPS / user count / data size )」064,並「嚴格遵守"Keep it simple, stupid"」126。拿某人的朋友 ID 只是一次 PK range scan,RDBMS 就做得到;graph DB 的強項是原書參考資料講的 friend-of-friend 推薦。這是推論,Triton 沒有評論過 graph DB。
Triton 補充原書第 5 步:hydrate
❌ 一篇一篇補作者:「10 * 5ms = 50ms」
原書這樣做會出什麼事?一頁 10 篇,每篇一筆一筆補貼文和作者,每次來回 5ms。光來回就要多久?
1 次拿 ID + 10 × 2 次補資料 = 21 次,21 × 5 = 105 ms。一頁 200 篇就超過 2 秒。
「要看討論串X的第11-20個留言,最智障的方法……然後,為了每一個message物件m再拿回他的作者……這樣是否正確,是正確啊!只是,這樣子跑起來會很慢……即使每個select只吃掉5ms(這是算很不錯的數字了),單單因為這些overhead便浪費掉10 * 5ms = 50ms!」🗣️ Triton 本人說 150-在一般的留言版….md
每次 query 的 overhead:TCP/IP、拿 prepared statement、SQL optimizer。解法一:「把要拿的userId先集中到一個array,然後用單一的query去拿全部的record」(WHERE id IN (…),再建 HashMap 填回);解法二:INNER JOIN users。「以上例子,其實只是backend developer的入門級知識。」150
「正常的工作,其 logical IO次數應該 independent of data size的……如果有 1000筆ActivityHistory,就跑 1000次 redis GET」→「以 redis MGET,一次過拿回 1000個User.displayName」🗣️ 088 · Anti pattern: data size-dependent IO operations
🔭 推論 把 150、088 的做法套到原書 Figure 7 第 5 步;程式是示意。注意 Redis cluster 下 MGET 的 key 會分散在不同 node(087:「不同的 KeyValue會放到不同的 redis機器」),client 要依 node 分批。
延伸基礎第 8 階 · cursor懂的人可以跳過
- cache
- push / pull
- 名人問題
- graph DB
- MQ
- feed cache
- hydrate
- cursor
- PK 順序
- stampede
- hot key
- TTL
看到一半,最上面又多了兩張:下次從哪裡看?
① 先想像
抽屜裡一疊聯絡單,最新的在最上面。你看完上面 4 張,記下「下次從第 5 張看」。這時又放進 2 張新的。
你猜猜看:下次的「第 5 張」是哪一張?
上面多了 2 張,全部往下擠 2 格,第 5 張變成你看過的。改記「比 10:09 那張更舊的」就不會錯。
③ 這叫做 offset、cursor
一次只給一頁,叫分頁。offset:記「從第幾張開始」。cursor:記「看到哪一張」的書籤,例如那張的時間。
④ 跟這章的關係
原書的 API 沒有分頁參數。Triton 的講義用時間戳當書籤(第 27 頁)。
② 動手玩:兩種記法
Triton 補充原書沒講分頁
往下滑的時候,新貼文進來了
offset 分頁
時間戳 cursor
原書的 GET /v1/me/feed 沒有分頁參數。如果用「第幾筆開始」分頁,滑到一半新貼文進來,會怎樣?
新貼文把舊的往下擠,「第 5 筆」變成看過的那篇。左邊按按鈕驗證。
「GET /v1/chatrooms/<roomId>/messages:Optional parameter: lastTs;Chronological descending order;支持 pagination ,返回大約上限 50 個訊息。除了 array of message ,還會有 nextPageTs」🗣️ Triton 本人說 062 · 訊息相關 endpoint
「如果沒有 snapshotting,剛好第十名的物品變第十一,然後你拿 Page 2的資料,你就會看到重覆的物品。RESTful endpoint: GET /v1/leaderboard?ts=1561042015」🗣️ 087 · 案例 2:data snapshotting
「若用 page id 會隨著時間回傳內容不同,因為下一秒又發新的 msg,這樣很難做 cache, cache 就會 invalidate」📝 上課筆記 009 · Roy 的 MVP IM 課堂筆記
🔭 推論 原書的 GET /v1/me/feed 沒有分頁參數。照 062 加上 ?lastTs=,回應帶 nextPageTs;同一個 lastTs 的那一頁內容不會變,也就能 cache。
延伸基礎第 9 階 · PK 順序懂的人可以跳過
- cache
- push / pull
- 名人問題
- graph DB
- MQ
- feed cache
- hydrate
- cursor
- PK 順序
- stampede
- hot key
- TTL
檔案夾要照「收到的順序」排,還是照「誰的」排?
① 先想像
全校的聯絡單收進一排檔案夾,一個夾子放 6 張。你要拿小明最新的 6 張。
你猜猜看:照收到的順序放,要翻幾個夾子?照「誰的 + 日期」放呢?
照收到的順序,大家的單子交錯,小明的散在各處。照「誰的 + 日期」,小明的擠在一起,一個夾子拿完。
③ 這叫做 primary key、sequential IO
primary key(PK):資料在磁碟上照它排的那個欄位。sequential IO:照順序一路讀;東翻西找叫 random IO,慢很多。
④ 跟這章的關係
Triton:feed 表的 PK 要跟著「最常查的方式」排(第 29 頁)。電話簿為什麼要照順序排,見第 7 章第 27 頁。
② 動手玩:4 位同學、24 張單
Triton 補充feed 表放在 DB 時
PK 選對:同一個人的 feed 在磁碟上排在一起
feed 表用 auto_increment(自動 +1 的號碼)當 PK。讀 A 的最新 8 筆,資料在磁碟上會?
PK 照寫入順序排,大家的 feed 混在一起。右邊按按鈕看要讀幾個 page。
「相同 chatroom 的 message record ,他們的 phyiscal storage position 應該是相鄰的 這樣子才是 seq IO 而不是 Random IO」「PostgreSQL 不是好選擇,因為其 table 底層是 heap」「跟我說 auto increment id 的,你的大腦被汪吃掉了嗎」「一定是 (chatroomId, createTs)」🗣️ Triton 本人說 062-im-system design.pdf.md · Database/Message Primary Key
「FB 如果用 Mysql post PK 會用哪個 Triton: post : postID (uuid) PK (postID + create_ts) 一個 Seq.Scan IO 依次拿出來 在動態牆」📝 上課筆記 058-…columnar_storage_mini-talk.pdf.md · Roy 的筆記,非本人原文
🔭 推論 062 的規則是「最常用的 query 用什麼排序,PK 就從那個欄位開始」。讀 feed 的 query 是「某人的 feed,依時間倒序」,所以預先算好的 feed 表 PK 應該是 (ownerUserId, createTs),放在 MySQL InnoDB 這類 index-organized table。筆記寫的 (postID + create_ts) 開頭是 postID,照 062 的邏輯排不出「同一個人的動態牆相鄰」,可能是筆記記漏了;這點無法向原文查證。
每一格是 feed 表的一列,字母是「這是誰的 feed」;一欄是一個 data page。
到這裡你已經會了小結 3 / 4
- cache
- push / pull
- 名人問題
- graph DB
- MQ
- feed cache
- hydrate
- cursor
- PK 順序
- stampede
- hot key
- TTL
到這裡你已經會了:打開抽屜之後
- 把編號補成完整內容叫 hydrate。一張一張拿是 1 + 2N 趟,列清單一次拿齊只要幾趟。
- 往下滑翻頁,記「第幾張」(offset)會重複或漏看;夾書籤(cursor,例如 lastTs)不會。
- 同一個人的 feed 要在磁碟上排在一起:PK 跟著最常查的方式排,一次 sequential IO 讀完。
下一階要解決的問題
名人一發文,一百萬人同時打開同一篇。那份 cache 一過期、或只住在一台機器上,會發生什麼事?
延伸基礎第 10 階 · stampede懂的人可以跳過
- cache
- push / pull
- 名人問題
- graph DB
- MQ
- feed cache
- hydrate
- cursor
- PK 順序
- stampede
- hot key
- TTL
公佈欄的影本被撕掉,80 個人同時跑去辦公室
① 先想像
熱門公告每秒有 10 人來看。影本被撕掉了,去辦公室重印要 8 秒。
你猜猜看:沒人協調的話,這 8 秒內會有幾個人跑去辦公室?
每秒 10 人 × 8 秒 = 80 人,辦公室被擠爆。規定「第一個人去印,其他人等他」,就只有 1 人去。
③ 這叫做 cache stampede、lock
cache stampede:cache 一過期,大家同時衝去 DB。lock:「一次只准一個人去」的令牌。
④ 跟這章的關係
原書說「盡量 cache」,沒講這件事(下一頁)。完整版見第 1 章第 44 頁(保溫台空了)。
② 動手玩:影本沒了
Triton 補充Cache data as much as you can 的另一半
熱門貼文的 cache 一過期:80 個 request 同時衝進 DB
原書說「盡量 cache」。熱門貼文每秒被讀 1000 次,cache 過期,DB 要 80ms 才回。這 80ms 裡有幾個 request 衝進 DB?
1000 × 0.08 秒 = 80 個。就是第 31 頁的 80 人衝辦公室。
「如果資料X的 QPS是 1000……如果主資料庫需要 80ms回傳資料X,那麼便有 80個 request進了主資料庫;如果資料X需要複雜運算,需要 8000ms,那便有 8000 個 request進了主資料庫……現實上,你的資料庫已經死了」🗣️ Triton 本人說 087-redis-2019.pdf.md · 「一般」的 caching問題
Triton 的高流量 caching:拿鎖之後再查一次
- 從 Redis 拿資料X;如有則直接回傳
- 拿到資料X的鎖(在離開時釋放)
- 再次從 Redis 拿資料X;如有則直接回傳
- 從主資料拿資料X
- 把資料X放回 Redis
- 把資料X回傳
087 p.14;072 p.11 的 data materialization 也是同樣的「拿 X lock → 再次檢查」
另外兩條:「有笨蛋會設 cache TTL = 一年,不設 TTL後果更嚴重」;首頁排名榜要 5 秒才算得出來時,「土法煉鋼但是有效的做法:寫一個 crontab,在 cache miss前到主資料庫拿資料放到 redis」087。🔭 推論 套到本章:名人貼文、熱門內容(原書的 hot cache)就是「QPS 1000 的資料X」。
延伸基礎第 11 階 · hot key懂的人可以跳過
- cache
- push / pull
- 名人問題
- graph DB
- MQ
- feed cache
- hydrate
- cursor
- PK 順序
- stampede
- hot key
- TTL
四位副班長分管抽屜,全校卻都在問同一份
① 先想像
資料太多,分給 4 位副班長管,每份只歸一位。現在全校 400 人都要看校長那份。
你猜猜看:4 位副班長各要應付幾人?
校長那份只歸一位管,別人幫不上忙。再多請 4 位副班長,那一位還是 400 人。
③ 這叫做 key、hot key
key:一份資料的名字。hot key:大家同時搶同一個 key,只有放它的那台被打爆,也叫 hotspot。
④ 跟這章的關係
原書說 consistent hashing 能緩解,Triton 不同意(第 34 頁)。另見第 4 章第 30 頁、第 5 章第 27 頁。
② 動手玩:400 人來問
Triton 不同意名人問題
Consistent hashing 分得開很多 key,分不開同一個 key
📖 原書
「Consistent hashing is a useful technique to mitigate the hotkey problem as it helps to distribute requests/data more evenly.」
原書這樣做會出什麼事?名人那一個 key,加開 Redis 機器之後,會分散到好幾台嗎?
consistent hashing 決定「每個 key 住哪台」,但同一個 key 永遠只住一台。就是第 33 頁的副班長 2。
「在 redis cluster,一份資料只存放在一個 node上;每一個 node都是 single thread的……容易發生 hotspot,沒法以增加硬體手段解決」🗣️ Triton 本人說 087 · Redis是 Single thread
「因為sorted set只有一個,即使建立了redis-cluster也只會存到其中一台redis上……原來貓咪也會開趴的,開趴時是超級大量貓咪一起開罐罐派對……瞬間有超高流量進了單一台redis。」🗣️ 182-資料結構很重要….md
「那10M user,先random抽一小部份人來push notification,讓CDN和你的server收到這一小波流量後,warm-up後再push剩下的」💬 討論串回覆,作者未標示 137-喵談 push notification.md(留言串):名人發文後的 Notification service 也是同一個問題
🔭 推論 087 講 localcache「很可能是設定 500ms TTL」,並且用「80 台伺服」算 Redis QPS「跟系統流量沒關係」。這裡把同一招套到名人貼文:80 台 AS × 每秒 2 次。其他 key 的流量(總共 4 萬/秒)和 node 上限 10 萬/秒是示意。
延伸基礎第 12 階 · TTL懂的人可以跳過
- cache
- push / pull
- 名人問題
- graph DB
- MQ
- feed cache
- hydrate
- cursor
- PK 順序
- stampede
- hot key
- TTL
公告改了,你的小抄多久之後才跟著改?
① 先想像
你把校長的公告抄成小抄。校長後來改了集合時間,小抄不會自己變。
你猜猜看:規定小抄「30 秒就丟掉重抄」。公告改了之後,你最晚多久會看到新版?
小抄最多活 30 秒,丟掉重抄就是新版。如果沒有期限,小抄永遠是舊的。
③ 這叫做 TTL
TTL(time to live):cache 可以放多久,時間到就丟掉,下次再去正本拿。
④ 跟這章的關係
Triton:cache 一定要設 TTL;動態牆晚幾秒,沒人會死(第 36 頁)。
② 動手玩:快轉時間
Triton 補充HYPEBEAST 的 suggestion feed
動態牆晚 30 秒更新,有人會死嗎?
原書沒說動態牆要多即時。Triton 自己做 feed 時,選了哪一邊?
他的原文就在下面:「Performance is MUCH more important then data freshness」。
「All data is cached:The user profile, the article content, the article score……Performance is MUCH more important then data freshness;"softcache" library to avoid disaster of cache miss in hot data」🗣️ Triton 本人說 076-mini-bigdata.pdf.md · Suggestion Feed Performance
Triton 自己做過的 feed(HYPEBEAST,> 3M MAU)
- Recom Module 從 local database 撈 X 天內的所有文章
- 每篇候選文章的 hashTags 跟 user profile 比對,算出分數
- 只對 top N 的文章發 HTTP request 拿回內容;多篇 cache miss 時用 multi-thread 同時拿
- Suggestion Feed 要和 Latest Feed「100% format compatible」,client 少改程式
076 · Suggestion Feed workflow;Integration with Wordpress
「用戶頁面顯示的,是「某時間點的 snapshot」而不是「即時資訊」;所以,你的 cache需要維持的,很有可能不是「最新資訊」……你需要 Strong Consistency的場合,直接對 DB操作」🗣️ 088 · 反思 caching(1)
動手算:熱門 feed 的 cache 存幾秒
🔭 推論 原書面試官說 feed 依時間倒序、沒有要求「即時」。按讚數、回覆數(原書的 Counters 層)差幾秒也不會有人發現,正是 088 說的「某時間點的 snapshot」。
Triton 補充feed 只放在 cache 裡?
Redis 不是資料庫:feed cache 掉了要能重建
📖 原書 feed 存在 cache
「Newsfeed data is stored in the cache for fast retrieval.」原書的 fanout workers 把 <post_id, user_id> 寫進 news feed cache;原書沒有說 cache 掉了怎麼辦。
原書這樣做會出什麼事?Redis 重開機,feed cache 全清空。
Redis 為了快,不保證資料寫了就不會掉。cache 一定要有正本。
「Redis的設計目標是用作 caching / hot data的短期儲存;因為 caching / hot data都可以從資料庫重建;為了效能, Redis不重視資料 Durability」🗣️ Triton 本人說 088 · Redis不是資料庫
🔭 推論 所以 feed cache 要能從 DB 重建:072 的「預先計算 + Range Scan on PK」就是那份可重建的來源(第 29 頁)。
原書的兩個缺點,用 TTL 和 top-2N 補
「如果 item count >10M,然後 N <= 1000時,以 List來存 Top 2N sorted item……如果 list count > 2N,就丟掉多餘的;如果 list count <= 1.1N,就從資料庫補資料」🗣️ 088 · 實作 top-N item
🔭 推論 原書「可設定的上限」可以照這個寫:存 2N 個 ID,少到 1.1N(例如作者刪文、取消追蹤)就從 DB 補。
🔭 推論 原書說 push 會替不活躍使用者白算。087 的「沒設定合理的 TTL」是常犯錯誤;替每個人的 feed cache 設 TTL,久沒登入的人 cache 自然過期,回來時再從 DB 重建一次,等於只對他做 pull。
三個小地雷
- 「一般來說,不建議使用 redis sorted sets」,因為 Redis 是 single thread,「如果有人在跑 CPU-intensive工作,沒跑完前所有人都會被卡住要等待」088
- 「別在 lua script內跑這種笨事:MGET Key1 Key2 Key3」:不同 key 會在不同 node 上 087 · Single Key Consistency
- 沒有 TTL 的 cache 等 Redis 滿了才 eviction,「是在 peak hours的寫入觸發」087
到這裡你已經會了小結 4 / 4
- cache
- push / pull
- 名人問題
- graph DB
- MQ
- feed cache
- hydrate
- cursor
- PK 順序
- stampede
- hot key
- TTL
到這裡你已經會了:熱門公告不倒的三招
- cache 一過期大家一起衝 DB(stampede):拿鎖之後再查一次,只讓一個人去重建。
- 名人那一個 key 只住一台(hot key),加機器沒用;要在前面先擋,例如每台 AS 自己的本地 cache。
- cache 一定要有期限(TTL),也要能從 DB 重建。動態牆晚幾秒沒關係,效能比新鮮度重要。
12 階全部走完了
下一頁用一句話收尾;再下一頁是名詞小卡,給大家課後複習。
一句話記住
動態牆是一串預先排好的 ID;
補資料一次拿齊,分頁用時間戳,熱 key 要先擋。
原書對的地方
- Push 為主、名人用 pull 的 hybrid
- Feed cache 只存
<post_id, user_id>,設上限 - Fanout 丟 MQ 給 workers 慢慢做
- 媒體走 CDN;cache 分層
原書沒講、會出事的地方
- Hydrate 一篇一篇拿:1 + 2N 次來回
- 沒有分頁設計:offset 會重複、漏看
- 「盡量 cache」但沒講 TTL 與 stampede
- Consistent hashing 解不了單一熱 key
Triton 的做法
IN/JOIN/MGET一次拿齊(150、088)?lastTs=+nextPageTs(062、087)- 上鎖再檢查、cron 預熱、一定設 TTL(087)
- PK 跟著最常用的 query 排序(062)
- 效能比新鮮度重要(076)
本章名詞小卡課後複習用 · 每個名詞一句白話
今天出現的名詞,一句話講完
給工程師的重點出處與標籤
引述來源(materials/core)與原書對照
Triton 本人的講義 / 文章
- 150-在一般的留言版….md — 留言板作者 N+1、每次 select 5ms「10 * 5ms = 50ms」、方案 1
IN+ HashMap、方案 2INNER JOIN - 088-redis-intro.pdf.md — Redis 不是資料庫/MQ、不建議 sorted sets、snapshot 而非即時資訊、data size-dependent IO 與 MGET、top-N 存 2N
- 087-redis-2019.pdf.md — 「一般」caching 的 80/8000 request、上鎖再檢查六步、預熱 crontab、TTL、一份資料只在一個 node、MGET in lua、
?ts=snapshot、localcache 500ms - 062-im-system design.pdf.md —
lastTs/nextPageTs、seq IO、PK(chatroomId, createTs)、PostgreSQL heap - 072-lesson3.pdf.md — Data fan-out:facebook newsfeed 預先計算、Range Scan on PK、Disk IO 才值錢;materialization 的 X lock 步驟
- 076-mini-bigdata.pdf.md — HYPEBEAST suggestion feed workflow、「Performance is MUCH more important then data freshness」、softcache
- 182 單一 sorted set 只在一台 redis、罐罐派對 · 185 MQ 的三個理由 · 137 10M 推播先抽樣暖 CDN(留言串) · 064 了解 N · 126 KISS
上課筆記(非本人原文):058(Roy 的 columnar storage 筆記:FB post PK;欄位順序存疑)、009(Roy 的 MVP IM 筆記:page id 難 cache)。未引用:053(Roy 的 redis 筆記,內容與 088 重複)。
原書對照
Alex Xu, System Design Interview Vol.1 Ch.11。開頭定義與 Figure 1、Step 1 需求(第 4 頁);Step 2 兩個流程與 Newsfeed APIs(6);Feed publishing、Newsfeed building 與 Figure 2–3(7);Feed publishing deep dive、Web servers 與 Figure 4(9);Fanout on write/read 與 hybrid(11–12);Fanout service 五步與 Figure 5(16);News feed cache 與 Figure 6(18);Newsfeed retrieval deep dive 與 Figure 7(21);Cache architecture 與 Figure 8(22);Step 4 Wrap up 與參考資料(23)。原書 8 張圖(Figure 6 原書是表格)都依圖說與 alt 描述重繪,不是原圖。
循序漸進(文組版)的頁面
學習地圖(第 3 頁);延伸基礎 12 階:cache(5)、push / pull(8)、名人問題(10)、graph DB(14)、MQ(15)、feed cache(17)、hydrate(20)、cursor(26)、PK 順序(28)、stampede(31)、hot key(33)、TTL(35);小結(13、19、30、38);名詞小卡(40)。cache、MQ、stampede、hot key、PK 順序只做複習,完整版連到第 1、4、5、7 章簡報。班長、校長與各頁示意數字不是原書數字。
一個可以直接問自己的問題
打開你的 feed API,一頁 20 篇,總共打了幾次 DB/Redis?這個數字跟「一頁幾篇」有關,就是 088 說的 anti-pattern。