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 萬份嗎?這就是本章的 名人問題。

0班長累計跑了幾趟(寫入)–同學看一次要走幾趟(讀取)

學習地圖本章的概念階梯

今天爬 12 階。每一階只用前面講過的東西。

  1. 1cache手邊的小抄
  2. 2push / pull塞抽屜或貼公佈欄
  3. 3名人問題校長的 1,200 份
  4. 4graph DB畫滿線的通訊錄
  5. 5MQ待辦籃
  6. 6feed cache抽屜只放編號
  7. 7hydrate照編號拿全文
  8. 8cursor夾一張書籤
  9. 9PK 順序檔案夾怎麼排
  10. 10stampede80 人衝辦公室
  11. 11hot key全校搶同一份
  12. 12TTL小抄的保存期限

第 1–3 階 · 聯絡單怎麼送

要回答:塞抽屜還是貼公佈欄?校長怎麼辦?

第 4–6 階 · 送給誰、誰來送

要回答:系統怎麼知道朋友是誰?抽屜裡放什麼?

第 7–9 階 · 打開抽屜之後

要回答:編號怎麼變回動態?往下滑怎麼翻頁?

第 10–12 階 · 熱門公告

要回答:全校同時搶同一份,誰先倒?

全程只用一個情境:班長發聯絡單

一張聯絡單 = 貼文(post)班長 = 發文的人同學 = 朋友/粉絲每個人的抽屜 = news feed cache公佈欄 = 發文者自己的貼文列表校長 = 名人通訊錄 = graph DB待辦籃 = MQ

每爬 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。

📖 原書 Figure 1手機上的 news feed(依原書內容重繪)

📖 原書 引用 Facebook 說明頁的定義:news feed 是「首頁中間不斷更新的故事列表」,包括你追蹤的人、專頁、社團的狀態更新、照片、影片、連結、app 活動和按讚。

Figure 1 是三則上下排列的動態,每則有來源 icon、標題和內文,第二則多了一個影片播放器。

延伸基礎第 1 階 · cache懂的人可以跳過

  1. cache
  2. push / pull
  3. 名人問題
  4. graph DB
  5. MQ
  6. feed cache
  7. hydrate
  8. cursor
  9. PK 順序
  10. stampede
  11. hot key
  12. TTL

同學的電話,每次都跑去教務處查嗎?

① 先想像

每次查同學電話都跑教務處,來回 2 分鐘。抄一份放鉛筆盒,看一眼 2 秒。

你猜猜看:這學期要查 30 次,跑教務處和看小抄各花多久?

③ 這叫做 cache、database

cache:放在手邊的小抄,拿得快,但不是正本。database(DB):教務處的正本名冊,最可靠、最慢。

④ 跟這章的關係

這章到處都是 cache:Post Cache、User Cache、News Feed Cache。完整版見第 1 章第 18 頁(保溫台)。

② 動手玩:查 30 次電話

0查了幾次0 秒累計花的時間

前幾章講過的零件,一句話複習

原書 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/feed
Feed publishing API
content:貼文文字
auth_token:驗證 API request
GET /v1/me/feed
Newsfeed 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 2Feed publishing 高階設計(依原書內容重繪)

📖 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懂的人可以跳過

  1. cache
  2. push / pull
  3. 名人問題
  4. graph DB
  5. MQ
  6. feed cache
  7. hydrate
  8. cursor
  9. PK 順序
  10. stampede
  11. hot key
  12. TTL

聯絡單:一份一份塞抽屜,還是貼一張在公佈欄?

① 先想像

全班 12 人,每人每天看 3 次聯絡單。班長可以一份一份塞抽屜,也可以只貼一張在公佈欄。

你猜猜看:貼公佈欄的話,全班一天總共要走幾趟去看?

③ 這叫做 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 與 fanout service。
📖 原書 Figure 4Feed publishing 詳細設計;編號依原書內文的 fanout 五步(alt 描述的編號略有出入,依內文)(依原書內容重繪)

📖 原書 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 階 · 名人問題懂的人可以跳過

  1. cache
  2. push / pull
  3. 名人問題
  4. graph DB
  5. MQ
  6. feed cache
  7. hydrate
  8. cursor
  9. PK 順序
  10. stampede
  11. hot key
  12. TTL

校長也要發聯絡單:全校 1,200 份,要塞多久?

① 先想像

塞一個抽屜要 1 秒。班長的 12 份,12 秒塞完。校長的公告要給全校 1,200 人。

你猜猜看:一份一份塞,最後一位學生要等多久才看到?

③ 這叫做 hotkey problem、hybrid

hotkey problem(名人問題):粉絲太多,push 要寫的份數爆炸。hybrid:一般人照 push,名人改成貼公佈欄(pull)。

④ 跟這章的關係

原書的選擇就是 hybrid(第 11 頁),第 12 頁的模擬器把數字放大到 1000 萬。

② 動手玩:誰發的聯絡單?

12要塞幾份12 秒最後一人要等多久

原書 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 省了什麼?

200發一篇文要寫幾份 feed cache0.002 秒fanout 全部寫完要多久80其中白寫(不活躍粉絲)
1讀一次 feed 要查幾個來源2 ms讀取延遲

示意假設(不是原書數字):fanout workers 合計每秒寫 10 萬筆;讀 feed cache 2ms;pull 每 100 位追蹤對象一次批次查詢、每次 5ms;Hybrid 的名人門檻 1 萬粉絲。

到這裡你已經會了小結 1 / 4

  1. cache
  2. push / pull
  3. 名人問題
  4. graph DB
  5. MQ
  6. feed cache
  7. hydrate
  8. cursor
  9. PK 順序
  10. stampede
  11. hot key
  12. TTL

到這裡你已經會了:聯絡單怎麼送

下一階要解決的問題

班長發一篇文,系統怎麼知道要塞給誰?誰來塞?抽屜裡又放什麼?

延伸基礎第 4 階 · graph DB懂的人可以跳過

  1. cache
  2. push / pull
  3. 名人問題
  4. graph DB
  5. MQ
  6. feed cache
  7. hydrate
  8. cursor
  9. PK 順序
  10. stampede
  11. hot key
  12. TTL

誰跟誰是朋友?一張畫滿線的通訊錄

① 先想像

這本通訊錄不是一列名字,而是一張圖:每個人是一個點,是朋友就連一條線。

你猜猜看:小美的朋友是阿明、小華;阿明的朋友是小美、小強。誰可以「推薦給小美當朋友」?

③ 這叫做 graph、graph database

graph:點和線組成的關係圖。graph database:專門存這種圖、擅長「沿著線走」的資料庫,例如 Neo4j。

④ 跟這章的關係

原書 fanout 第 1 步:從 graph DB 拿朋友 ID(第 16 頁)。Triton 會問:只拿朋友清單,一般 DB 不行嗎?(第 24 頁)

② 動手玩:點一個人

2朋友(走 1 條線)2朋友的朋友(走 2 條線)

延伸基礎第 5 階 · MQ懂的人可以跳過

  1. cache
  2. push / pull
  3. 名人問題
  4. graph DB
  5. MQ
  6. feed cache
  7. hydrate
  8. cursor
  9. PK 順序
  10. stampede
  11. hot key
  12. TTL

5,000 份要塞,班長要站著等塞完才回座位嗎?

① 先想像

班長寫一張「幫我塞給這 5,000 人」放進待辦籃,就回座位。小幫手們從籃子裡拿工作,慢慢塞。

你猜猜看:塞一份 1 秒。班長自己塞完才回座位,要站多久?放進待辦籃呢?

③ 這叫做 message queue、worker

message queue(MQ):待辦籃,工作先排隊。worker:從籃子拿工作來做的小幫手。

④ 跟這章的關係

原書 fanout 第 3–4 步就是這樣(第 16 頁)。完整版見第 1 章第 30 頁(修照片)。

② 動手玩:給 5,000 位朋友

5,000 秒班長(發文的人)要等多久5,000 秒全部塞完要多久

原書 Step 3Fanout service · Figure 5

Fanout service 的五個步驟

這一步要解決的問題貼文要送給誰?誰被靜音?5000 份由誰來寫?

📖 原書 Figure 5Fanout service:Graph DB、User Cache/User DB、Message Queue、Fanout Workers、News Feed(依原書內容重繪)
按「下一步」依序走過 1–5。

📖 原書 運作方式

  1. 從 graph database 拿朋友 ID。Graph DB 適合管理朋友關係和朋友推薦(原書參考資料 [2]:Neo4j 與 SQL Server 的 friend-of-friend 推薦)。
  2. 從 user cache 拿朋友資訊,再依使用者設定過濾。例如你把某人靜音,即使還是朋友,她的貼文也不會出現在你的 feed;使用者也可能只分享給特定朋友、對其他人隱藏。
  3. 把朋友清單和新貼文 ID 送進 message queue。
  4. Fanout workers 從 MQ 取出資料,把 news feed 資料存進 news feed cache。
  5. 在 news feed cache 存 <post_id, user_id>(下一頁 Figure 6)。

延伸基礎第 6 階 · feed cache懂的人可以跳過

  1. cache
  2. push / pull
  3. 名人問題
  4. graph DB
  5. MQ
  6. feed cache
  7. hydrate
  8. cursor
  9. PK 順序
  10. stampede
  11. hot key
  12. TTL

抽屜放不下:只放一張「編號便條」

① 先想像

整張聯絡單(全文加照片)很佔空間。一張寫著「第 205 號,班長發的」的便條,只佔一小格。

你猜猜看:抽屜有 32 格。整張佔 16 格,便條佔 1 格。各放得下幾張?

③ 這叫做 news feed cache、ID

news feed cache:每人一個抽屜,放貼文的編號。ID:每篇貼文、每個人的號碼,例如 post_id、user_id。

④ 跟這章的關係

原書 Figure 6 就是這個抽屜:一張 <post_id, user_id> 表,還有上限(下一頁)。

② 動手玩:塞新聯絡單進抽屜

0抽屜裡有幾張0最舊的被丟掉幾張

原書 Step 3News feed cache · Figure 6

每個人的 feed cache:只存 <post_id, user_id>

這一步要解決的問題1000 萬人每人一個抽屜,抽屜裡放什麼、放多少,記憶體才夠?

📖 原書 Figure 6News feed cache 的樣子:一張 post_id/user_id 對應表(依原書內容重繪)

每有新貼文就 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

  1. cache
  2. push / pull
  3. 名人問題
  4. graph DB
  5. MQ
  6. feed cache
  7. hydrate
  8. cursor
  9. PK 順序
  10. stampede
  11. hot key
  12. TTL

到這裡你已經會了:發一篇文,背後跑了什麼

下一階要解決的問題

抽屜裡只有編號。打開首頁時,要怎麼把編號變回有名字、照片、全文的動態?

延伸基礎第 7 階 · hydrate懂的人可以跳過

  1. cache
  2. push / pull
  3. 名人問題
  4. graph DB
  5. MQ
  6. feed cache
  7. hydrate
  8. cursor
  9. PK 順序
  10. stampede
  11. hot key
  12. TTL

抽屜裡只有編號:要跑幾趟,才看得到全文?

① 先想像

打開抽屜,10 張編號便條。全文在「貼文櫃」,作者照片在「學生資料櫃」。每跑一趟 1 分鐘。

你猜猜看:一張一張拿,每張都要跑兩個櫃子。總共幾趟?

③ 這叫做 hydrate、round trip

hydrate:把編號補成完整內容,像泡麵加水泡開。round trip:去一趟再回來;每一趟都要時間。

④ 跟這章的關係

原書讀 feed 的第 5 步就是 hydrate,但沒說怎麼拿(下一頁)。Triton 的答案在第 25 頁;「一趟拿齊」另見第 2 章第 34 頁。

② 動手玩:把便條變成全文

20跑幾趟20 分鐘花多久(每趟 1 分鐘)

原書 Step 3Newsfeed retrieval deep dive · Figure 7

讀 feed:先拿 ID,再補齊成完整的動態

這一步要解決的問題抽屜裡只有編號。打開首頁時,怎麼變回有名字、照片、全文的動態?

📖 原書 Figure 7Newsfeed retrieval 詳細設計;媒體檔放 CDN(依原書內容重繪)

📖 原書 六個步驟

  1. 使用者送 request 拿 news feed:/v1/me/feed
  2. Load balancer 把 request 分給 web servers
  3. Web servers 呼叫 news feed service
  4. News feed service 從 news feed cache 拿一串 post ID
  5. news feed 不只是 ID,還有使用者名稱、大頭照、貼文內容、貼文圖片等,所以要從 user cache 和 post cache 拿完整的 user 與 post 物件,組成 fully hydrated 的 news feed
  6. 完整的 news feed 以 JSON 回給 client 去 render

圖片、影片這些媒體內容存在 CDN,讀得快。第 5 步要「怎麼拿」原書沒寫,Triton 的答案在第 25 頁。

原書 Step 3Cache architecture · Figure 8

Cache 分五層,各存各的

這一步要解決的問題一則動態除了貼文,還有讚數、你按過讚沒。這些小抄要怎麼分類放?

📖 原書 Figure 8五層 cache:News Feed、Content、Social Graph、Action、Counters(依原書內容重繪;點任一層)

📖 原書 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,他怎麼看?

「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。光來回就要多久?

「要看討論串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

21round trip 次數105 ms只算來回的延遲

      

🔭 推論 把 150、088 的做法套到原書 Figure 7 第 5 步;程式是示意。注意 Redis cluster 下 MGET 的 key 會分散在不同 node(087:「不同的 KeyValue會放到不同的 redis機器」),client 要依 node 分批。

延伸基礎第 8 階 · cursor懂的人可以跳過

  1. cache
  2. push / pull
  3. 名人問題
  4. graph DB
  5. MQ
  6. feed cache
  7. hydrate
  8. cursor
  9. PK 順序
  10. stampede
  11. hot key
  12. TTL

看到一半,最上面又多了兩張:下次從哪裡看?

① 先想像

抽屜裡一疊聯絡單,最新的在最上面。你看完上面 4 張,記下「下次從第 5 張看」。這時又放進 2 張新的。

你猜猜看:下次的「第 5 張」是哪一張?

③ 這叫做 offset、cursor

一次只給一頁,叫分頁。offset:記「從第幾張開始」。cursor:記「看到哪一張」的書籤,例如那張的時間。

④ 跟這章的關係

原書的 API 沒有分頁參數。Triton 的講義用時間戳當書籤(第 27 頁)。

② 動手玩:兩種記法

    Triton 補充原書沒講分頁

    往下滑的時候,新貼文進來了

    offset 分頁

      時間戳 cursor

        原書的 GET /v1/me/feed 沒有分頁參數。如果用「第幾筆開始」分頁,滑到一半新貼文進來,會怎樣?

        「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 順序懂的人可以跳過

        1. cache
        2. push / pull
        3. 名人問題
        4. graph DB
        5. MQ
        6. feed cache
        7. hydrate
        8. cursor
        9. PK 順序
        10. stampede
        11. hot key
        12. TTL

        檔案夾要照「收到的順序」排,還是照「誰的」排?

        ① 先想像

        全校的聯絡單收進一排檔案夾,一個夾子放 6 張。你要拿小明最新的 6 張。

        你猜猜看:照收到的順序放,要翻幾個夾子?照「誰的 + 日期」放呢?

        ③ 這叫做 primary key、sequential IO

        primary key(PK):資料在磁碟上照它排的那個欄位。sequential IO:照順序一路讀;東翻西找叫 random IO,慢很多。

        ④ 跟這章的關係

        Triton:feed 表的 PK 要跟著「最常查的方式」排(第 29 頁)。電話簿為什麼要照順序排,見第 7 章第 27 頁。

        ② 動手玩:4 位同學、24 張單

        4拿小明(明)的 6 張要翻幾個夾子

        Triton 補充feed 表放在 DB 時

        PK 選對:同一個人的 feed 在磁碟上排在一起

        feed 表用 auto_increment(自動 +1 的號碼)當 PK。讀 A 的最新 8 筆,資料在磁碟上會?

        「相同 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 的邏輯排不出「同一個人的動態牆相鄰」,可能是筆記記漏了;這點無法向原文查證。

        –要讀幾個 data page–IO 類型

        每一格是 feed 表的一列,字母是「這是誰的 feed」;一欄是一個 data page。

        到這裡你已經會了小結 3 / 4

        1. cache
        2. push / pull
        3. 名人問題
        4. graph DB
        5. MQ
        6. feed cache
        7. hydrate
        8. cursor
        9. PK 順序
        10. stampede
        11. hot key
        12. TTL

        到這裡你已經會了:打開抽屜之後

        下一階要解決的問題

        名人一發文,一百萬人同時打開同一篇。那份 cache 一過期、或只住在一台機器上,會發生什麼事?

        延伸基礎第 10 階 · stampede懂的人可以跳過

        1. cache
        2. push / pull
        3. 名人問題
        4. graph DB
        5. MQ
        6. feed cache
        7. hydrate
        8. cursor
        9. PK 順序
        10. stampede
        11. hot key
        12. TTL

        公佈欄的影本被撕掉,80 個人同時跑去辦公室

        ① 先想像

        熱門公告每秒有 10 人來看。影本被撕掉了,去辦公室重印要 8 秒。

        你猜猜看:沒人協調的話,這 8 秒內會有幾個人跑去辦公室?

        ③ 這叫做 cache stampede、lock

        cache stampede:cache 一過期,大家同時衝去 DB。lock:「一次只准一個人去」的令牌。

        ④ 跟這章的關係

        原書說「盡量 cache」,沒講這件事(下一頁)。完整版見第 1 章第 44 頁(保溫台空了)。

        ② 動手玩:影本沒了

        80跑去辦公室的人

        Triton 補充Cache data as much as you can 的另一半

        熱門貼文的 cache 一過期:80 個 request 同時衝進 DB

        原書說「盡量 cache」。熱門貼文每秒被讀 1000 次,cache 過期,DB 要 80ms 才回。這 80ms 裡有幾個 request 衝進 DB?

        「如果資料X的 QPS是 1000……如果主資料庫需要 80ms回傳資料X,那麼便有 80個 request進了主資料庫;如果資料X需要複雜運算,需要 8000ms,那便有 8000 個 request進了主資料庫……現實上,你的資料庫已經死了」🗣️ Triton 本人說 087-redis-2019.pdf.md · 「一般」的 caching問題

        Triton 的高流量 caching:拿鎖之後再查一次

        1. 從 Redis 拿資料X;如有則直接回傳
        2. 拿到資料X的鎖(在離開時釋放)
        3. 再次從 Redis 拿資料X;如有則直接回傳
        4. 從主資料拿資料X
        5. 把資料X放回 Redis
        6. 把資料X回傳

        087 p.14;072 p.11 的 data materialization 也是同樣的「拿 X lock → 再次檢查」

        80同時打進 DB 的 request6.4 秒DB 總共花掉的時間

        另外兩條:「有笨蛋會設 cache TTL = 一年,不設 TTL後果更嚴重」;首頁排名榜要 5 秒才算得出來時,「土法煉鋼但是有效的做法:寫一個 crontab,在 cache miss前到主資料庫拿資料放到 redis」087。🔭 推論 套到本章:名人貼文、熱門內容(原書的 hot cache)就是「QPS 1000 的資料X」。

        延伸基礎第 11 階 · hot key懂的人可以跳過

        1. cache
        2. push / pull
        3. 名人問題
        4. graph DB
        5. MQ
        6. feed cache
        7. hydrate
        8. cursor
        9. PK 順序
        10. stampede
        11. hot key
        12. TTL

        四位副班長分管抽屜,全校卻都在問同一份

        ① 先想像

        資料太多,分給 4 位副班長管,每份只歸一位。現在全校 400 人都要看校長那份。

        你猜猜看:4 位副班長各要應付幾人?

        ③ 這叫做 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 機器之後,會分散到好幾台嗎?

        「在 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懂的人可以跳過

        1. cache
        2. push / pull
        3. 名人問題
        4. graph DB
        5. MQ
        6. feed cache
        7. hydrate
        8. cursor
        9. PK 順序
        10. stampede
        11. hot key
        12. TTL

        公告改了,你的小抄多久之後才跟著改?

        ① 先想像

        你把校長的公告抄成小抄。校長後來改了集合時間,小抄不會自己變。

        你猜猜看:規定小抄「30 秒就丟掉重抄」。公告改了之後,你最晚多久會看到新版?

        ③ 這叫做 TTL

        TTL(time to live):cache 可以放多久,時間到就丟掉,下次再去正本拿。

        ④ 跟這章的關係

        Triton:cache 一定要設 TTL;動態牆晚幾秒,沒人會死(第 36 頁)。

        ② 動手玩:快轉時間

        0 秒時間第 1 版公佈欄(正本)第 1 版你的小抄

        Triton 補充HYPEBEAST 的 suggestion feed

        動態牆晚 30 秒更新,有人會死嗎?

        原書沒說動態牆要多即時。Triton 自己做 feed 時,選了哪一邊?

        「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)

        1. Recom Module 從 local database 撈 X 天內的所有文章
        2. 每篇候選文章的 hashTags 跟 user profile 比對,算出分數
        3. 只對 top N 的文章發 HTTP request 拿回內容;多篇 cache miss 時用 multi-thread 同時拿
        4. 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 存幾秒

        60,000每分鐘問 DB 幾次(QPS 1000)0 秒使用者最多看到多舊

        🔭 推論 原書面試官說 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的設計目標是用作 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

        1. cache
        2. push / pull
        3. 名人問題
        4. graph DB
        5. MQ
        6. feed cache
        7. hydrate
        8. cursor
        9. PK 順序
        10. stampede
        11. hot key
        12. TTL

        到這裡你已經會了:熱門公告不倒的三招

        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)

        本章名詞小卡課後複習用 · 每個名詞一句白話

        今天出現的名詞,一句話講完

        news feed首頁中間不斷更新的動態列表
        cache放在手邊的小抄,拿得快但不是正本
        database(DB)正本名冊,最可靠、最慢
        APIclient 和 server 約好的窗口,例如 GET /v1/me/feed
        auth_token證明「你是你」的通行證,每個 request 都帶著
        load balancer帶位員,把 request 分給好幾台 web server
        DAU每天有幾個人用(daily active users)
        fanout把一篇貼文送到每個朋友那裡
        push(fanout on write)發文時就塞進每個人的抽屜
        pull(fanout on read)要看時才去發文者的公佈欄拉
        hotkey problem名人粉絲太多,push 的份數爆炸
        hybrid一般人 push、名人 pull 的混合做法

        給工程師的重點出處與標籤

        引述來源(materials/core)與原書對照

        Triton 本人的講義 / 文章

        • 150-在一般的留言版….md — 留言板作者 N+1、每次 select 5ms「10 * 5ms = 50ms」、方案 1 IN + HashMap、方案 2 INNER 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。

        ← → 翻頁 · S 講者備註 · D 深/淺色
        1 / 1目錄