System Design Interview Vol. 2 · 第 6 章Triton 覆蓋度:🟡 中Triton 線
Ad Click Event Aggregation
每分鐘幫一億則點擊開一次票
原書要做 Facebook / Google 等級的廣告點擊統計:每天 10 億次點擊,用兩個 Kafka、一個 MapReduce 式的聚合服務、watermark、snapshot,加上 exactly-once 的分散式交易。Triton 沒寫過這一章,但他對「資料分析」講過的話很一致:先問資料到底多大、哪些可以掉;不到 100GB,就乖乖回去用 RDBMS。
給文組
全程用「選舉開票」比喻:各開票所唱票、中選會加總、郵寄選票晚到、重複唱票、事後驗票,一階一階爬 13 個概念。頁首標 延伸基礎 的頁是補基礎,懂的人可以跳過。
給工程師
第 6–52 頁完整講原書(30 張圖、18 個表全部重繪),後面是 Triton 的觀點,最後一頁列出所有出處(materials/core)與頁碼對照。
標籤怎麼看
📖 原書 🗣️ Triton 本人說 💬 作者未標示 🔭 依 Triton 原則推論 📅 2026 補充
先用生活理解選舉開票
開票夜:三個開票所,一張總表
廣告點擊統計就是一場永遠不會結束的開票:每個伺服器是一個開票所,每一次點擊是一張票,系統每分鐘要公布一次「每則廣告拿了幾票」。
- 唱票、加總:各開票所先自己數,中選會再合計(原書的 Map → Aggregate → Reduce)
- 郵寄選票晚到:點擊發生在 10:00:59,卻 10:01:10 才送到(event time vs processing time、watermark)
- 重複唱票:開票所斷線、不確定剛剛有沒有送到,只好再送一次(delivery guarantee、exactly-once)
- 事後驗票:隔天用原始選票重數一次,對總表(reconciliation)
選票數錯,結果可能翻盤;廣告點擊數錯,廣告主就多付或少付錢。原書說:差幾個百分點就可能是幾百萬美元。
學習地圖本章的概念階梯
今天爬 13 階。每一階只用前面講過的東西。
- 1event一張選票
- 2QPS · GB票來多快、多重
- 3MQ · offset收件櫃台和流水號
- 4MapReduce分頭唱票再合計
- 5stream · batch流水線 vs 月底結帳
- 6window每幾分鐘結一次
- 7event time看郵戳還是收件日
- 8watermark截止後的寬限期
- 9at-least once沒回條就重送
- 10exactly-once重送也只算一次
- 112PC兩本簿子一起改
- 12reconciliation事後驗票
- 13columnar一欄一本冊子
第 1–3 階 · 票從哪來
要回答:每一次點擊,怎麼送到數票的地方?
第 4–5 階 · 怎麼數
要回答:每秒 5 萬張票,怎麼分頭數、什麼時候數?
第 6–8 階 · 時間
要回答:這張票算哪一分鐘?晚到的怎麼辦?
第 9–11 階 · 不多不少
要回答:斷線重送,怎麼不重複也不漏?
第 12–13 階 · 驗票與存票
要回答:怎麼便宜地驗票?Triton 怎麼存?
全程只用一場開票夜
每爬 2–3 階,有一頁「到這裡你已經會了」。
延伸基礎第 1 階 · event懂的人可以跳過
- event
- QPS · GB
- MQ · offset
- MapReduce
- stream · batch
- window
- event time
- watermark
- at-least once
- exactly-once
- 2PC
- reconciliation
- columnar
每次點擊留下一張小紙條;門口貼的是計票表
① 先想像
有人點了廣告,伺服器就寫下一行小紙條:哪則廣告、幾點幾分、誰、哪個國家。這就是一張選票。
你猜猜看:門口的計票表只寫「ad001:這一分鐘 5 次」。能看出 5 次裡有幾次來自美國嗎?
計票表只留下總數。想用新條件重數,只能翻原始紙條,所以原書兩種都存。
③ 這叫做 event、aggregation
event:一次點擊留下的一行紀錄(log)。aggregation:把很多行數成一個數字,中文叫「聚合」。
④ 跟這章的關係
原始紙條叫 raw data,計票表叫 aggregated data。原書兩種都存(第 11 頁)。
② 動手玩:點廣告,看紙條和計票表
延伸基礎 · 複習第 2 階 · QPS、GB02 章講過,懂的人可以跳過
- event
- QPS · GB
- MQ · offset
- MapReduce
- stream · batch
- window
- event time
- watermark
- at-least once
- exactly-once
- 2PC
- reconciliation
- columnar
一天 10 億張票:每秒幾張?一天多重?
① 先想像
一天有 86,400 秒,心算時當成 10 萬秒。一天的票數除以 10 萬,就是平均每秒幾張。
你猜猜看:一天 10 億次點擊,平均每秒大約幾次?
10 億 ÷ 10 萬 = 1 萬。最忙那一秒還要再乘幾倍:原書抓 5 倍,每秒 5 萬。
③ 這叫做 QPS、GB(複習)
④ 跟這章的關係
原書每天 100 GB(第 8 頁)。Triton 的分界線是「全部 < 100GB 就用一般的資料庫」(第 54 頁)。
② 動手玩:三種規模,每筆紀錄 100 B
原書線上廣告的背景 · Figure 1
廣告是怎麼被買賣的:Real-Time Bidding
這一步要解決的問題廣告是怎麼賣出去的?為什麼「點了幾次」就是錢?
📖 原書 Facebook、YouTube、TikTok 興起後,數位廣告佔整體廣告支出的比例越來越大。線上廣告的一大優點是可衡量:用即時資料量化成效。
- Demand side:Advertiser 透過 DSP(Demand-Side Platform)買廣告版位
- Supply side:Publisher 透過 SSP(Supply-Side Platform)賣版位
- Ad Exchange:中間的市集,撮合 DSP 的 ad request 和 SSP 的 inventory,決定使用者看到哪個廣告
- RTB 要快:通常不到一秒完成
為什麼點擊數要準
點擊彙總決定廣告主付多少錢。campaign manager 依結果控制預算、調整出價策略(換目標受眾、關鍵字)。CTR(click-through rate)和 CVR(conversion rate)這些關鍵指標都靠彙總後的點擊資料。
白話:DSP / SSP=買方 / 賣方的代理平台;CTR=看到廣告的人有幾 % 點下去;CVR=點了的人有幾 % 真的買;campaign=一檔廣告活動。
原書 Step 1釐清需求
面試一開始:資料長怎樣、多大、要查什麼
這一步要解決的問題要數什麼、量有多大、多快要結果?先問清楚,後面才不會白做。
📖 原書 應徵者 × 面試官
| 應徵者問 | 面試官答 |
|---|---|
| 輸入資料的格式? | 散在不同 server 上的 log file,最新點擊 append 在檔尾。欄位:ad_id, click_timestamp, user_id, ip, country |
| 資料量? | 每天 10 億次點擊、總共 200 萬則廣告;點擊數每年成長 30% |
| 最重要的查詢? | ① 某則廣告過去 M 分鐘的點擊數;② 過去 1 分鐘點擊最多的前 100 則(兩個參數都可設定,每分鐘聚合一次);③ 上面兩個都能依 ip、user_id、country 過濾 |
| 要擔心 edge case 嗎?我想到:晚到的事件、重複的事件、系統任何部分隨時會掛,要考慮恢復 | 很好的清單,都要考慮 |
| 延遲要求? | 端到端幾分鐘。RTB 要不到一秒;點擊彙總主要用於計費和報表,幾分鐘可接受 |
📖 原書 Functional requirements
- 彙總
ad_id過去 M 分鐘的點擊數 - 每分鐘回傳點擊最多的前 100 個
ad_id - 支援依不同屬性過濾
- 資料量是 Facebook / Google 等級(見估算)
📖 原書 Non-functional requirements
- 正確性很重要:資料用於 RTB 和廣告計費
- 妥善處理延遲或重複的事件
- Robustness:能撐過部分故障
- 端到端延遲最多幾分鐘
🗣️ Triton 他會在這裡多問一句「哪些資料可以錯?」,見第 53 頁。
原書 Step 1Back-of-the-envelope estimation
10 億點擊,一天 100 GB
這一步要解決的問題「Facebook 等級」到底是每秒幾張票、一天多重?
📖 原書 估算
| DAU | 10 億 |
| 每人每天平均點 1 則廣告 | 每天 10 億次點擊 |
| 平均 QPS | 109 ÷ 105 秒 = 10,000 |
| Peak QPS(平均的 5 倍) | 50,000 |
| 每次點擊 0.1 KB | 每天 0.1 KB × 10 億 = 100 GB;每月約 3 TB |
一天約 86,400 秒,原書取 105 好算。
白話:DAU=每天有幾個人用(daily active users);peak=最忙那一秒(第 5 頁)。
動手算:每年成長 30%
原書在 Scale the system 一節說:每年 30%,大約每 3 年翻倍(1.33 ≈ 2.2)。
🔭 先記住這個數字 原書的規模是「每天 100 GB」。Triton 的分界線是「資料量 < 100GB 就用 RDBMS」(054)。同一個 100 GB,一個是一天,一個是全部。第 54 頁的計算機會用到。
原書 Step 2Query API design · Table 1–6
只要兩支 API:某廣告的點擊數、熱門廣告
這一步要解決的問題看 dashboard 的人,要怎麼問「這則廣告幾次」「誰最熱門」?
📖 原書 這裡的 client 不是一般使用者,而是看 dashboard 的人:data scientist、PM、廣告主。過濾(第三個需求)用 query parameter 就能做,所以兩支 API 就夠了。
白話:API=系統公開的查詢窗口;dashboard=看數字的儀表板網頁;query parameter=網址 ? 後面的條件。
Table 1 GET /v1/ads/{:ad_id}/aggregated_count
回傳指定 ad_id 的彙總事件數量
| Table 2 · request | ||
|---|---|---|
from | 起始分鐘(預設:現在減 1 分鐘) | long |
to | 結束分鐘(預設:現在) | long |
filter | 過濾策略的識別碼,例如 filter = 001 濾掉非美國的點擊 | long |
| Table 3 · response | ||
ad_id | 廣告的識別碼 | string |
count | 起訖分鐘之間的彙總數量 | long |
Table 4 GET /v1/ads/popular_ads
回傳過去 M 分鐘點擊最多的前 N 則廣告
| Table 5 · request | ||
|---|---|---|
count | Top N | integer |
window | 聚合視窗大小 M(分鐘) | integer |
filter | 過濾策略的識別碼 | long |
| Table 6 · response | ||
ad_ids | 點擊最多的廣告清單 | array |
動手試:用原書 Table 8、Table 9 的資料呼叫 API 1
原書 Step 2Data model · Table 7–11
兩種資料:原始的每一張票,和每分鐘的計票結果
這一步要解決的問題要存每一張票,還是只存計票表?兩種各長什麼樣子?
📖 原書 Raw data(散在各 application server 的 log)
[AdClickEvent] ad001, 2021-01-01 00:00:01, user 1, 207.148.22.22, USA
| ad_id | click_timestamp | user | ip | country |
|---|---|---|---|---|
| ad001 | 2021-01-01 00:00:01 | user1 | 207.148.22.22 | USA |
| ad001 | 2021-01-01 00:00:02 | user1 | 207.148.22.22 | USA |
| ad002 | 2021-01-01 00:00:02 | user2 | 209.153.56.11 | USA |
Table 7Raw data
📖 原書 Aggregated data(每分鐘聚合一次)
| ad_id | click_minute | count |
|---|---|---|
| ad001 | 202101010000 | 5 |
| ad001 | 202101010001 | 7 |
Table 8Aggregated data
| ad_id | click_minute | filter_id | count |
|---|---|---|---|
| ad001 | 202101010000 | 0012 | 2 |
| ad001 | 202101010000 | 0023 | 3 |
| ad001 | 202101010001 | 0012 | 1 |
| ad001 | 202101010001 | 0023 | 6 |
Table 9加上 filter_id
Table 10 Filter table
| filter_id | region | IP | user_id |
|---|---|---|---|
| 0012 | US | * | * |
| 0013 | * | 123.1.2.3 | * |
同一個 ad_id + click_minute 的紀錄,再依 filter_id 分組。
Table 11 most_clicked_ads(支援 top N)
window_size | integer | 聚合視窗大小 M(分鐘) |
update_time_minute | timestamp | 最後更新時間(1 分鐘粒度) |
most_clicked_ads | array | JSON 格式的 ad ID 清單 |
文組翻譯
Raw data 是每一張選票,aggregated data 是開票所門口貼的那張「每分鐘計票表」。filter 就是同一張表再拆成「北部票」「南部票」各一欄。
原書 Step 2Comparison · Table 12
存原始資料,還是只存聚合結果?原書:兩個都存
這一步要解決的問題只存計票表最省空間,可是之後還回得去嗎?
| Raw data only | Aggregated data only | |
|---|---|---|
| Pros | 完整資料集 支援資料過濾與重新計算 | 資料集較小 查詢快 |
| Cons | 儲存量龐大 查詢慢 | 資料遺失:這是衍生資料,例如 10 筆聚合成 1 筆 |
📖 原書 Table 12Raw data vs aggregated data
📖 原書 建議兩者都存:
- 保留 raw data:出事時可以拿來 debug;如果 bug 把聚合資料弄壞,修好 bug 後可以從 raw data 重新計算
- 也存 aggregated data:raw data 太大,直接查非常沒效率,所以讀取查詢都打在聚合資料上
- Raw data 是備份資料:平常不查,除非要重算;舊的 raw data 可以搬到 cold storage 省錢
- Aggregated data 是 active data:為查詢效能調校
文組翻譯:計票表貼在門口給大家看(快),原始選票封箱保存(大、慢),有爭議時才開箱重數。
原書 Step 2Choose the right database
選資料庫:先看資料長怎樣、讀多還是寫多
這一步要解決的問題每秒 5 萬張票,要寫進哪一種資料庫?
📖 原書 四個要問的問題
- 資料長什麼樣子?relational?document?blob?
- 工作負載是 read-heavy、write-heavy,還是兩者都是?
- 需要 transaction 嗎?
- 查詢是否大量依賴 OLAP 函數,例如
SUM、COUNT?
白話:relational=一般的表格式資料庫(RDBMS);transaction=一組改動全成或全不算(第 39 頁);OLAP=做分析報表用的;NoSQL=不是表格式的資料庫;columnar 見第 59 頁。
📖 原書 Raw data
- 平常不查,但 data scientist、ML 工程師會拿來研究 user response prediction、behavioral targeting、relevance feedback
- 平均寫入 10,000 QPS、尖峰 50,000 → write-heavy;讀取量理論上很低
- 「Relational database 可以勝任,但 scale 寫入有挑戰」。Cassandra、InfluxDB 這類 NoSQL 為寫入和時間範圍查詢最佳化,比較適合
- 另一個選項:存在 Amazon S3,用 columnar 格式 ORC、Parquet、AVRO;每個檔案設上限(例如 10GB),寫 raw data 的 stream processor 到上限就 rotate 檔案
- 「這種做法很多人不熟」,所以原書用 Cassandra 當例子
📖 原書 Aggregated data
- 本質是 time-series,讀寫都重
- 讀:每則廣告每分鐘都要查一次最新計數,給 dashboard 自動刷新、及時觸發 alert;共 200 萬則廣告 → read-heavy
- 寫:聚合服務每分鐘寫一次 → 也是 write-heavy
- raw 和 aggregated 可以用同一種資料庫
🗣️ Triton 原書說「很多人不熟」而放棄的 S3 + Parquet,正是 Triton 會選的那條路,見第 60 頁。
延伸基礎第 3 階 · MQ、offset懂的人可以跳過
- event
- QPS · GB
- MQ · offset
- MapReduce
- stream · batch
- window
- event time
- watermark
- at-least once
- exactly-once
- 2PC
- reconciliation
- columnar
開票所把結果丟進收件櫃台,就能回去繼續數
① 先想像
中選會門口有個收件櫃台。開票所把結果單丟進去就走,不用等中選會有空。櫃台在每張單上蓋流水號。
你猜猜看:中選會的小陳處理到第 7 號時昏倒,換小林接手。小林該從第幾號開始?
前提是小陳有把「處理到第 7 號」記下來。記早了會漏、記晚了會重複,這是後半章的主題。
③ 這叫做 message queue、offset
message queue(MQ):收件櫃台,先收下、之後再處理;Kafka 是一種。offset:流水號,「處理到第幾號」。
④ 跟這章的關係
原書在流程裡放了兩個 MQ(下一頁)。offset 什麼時候記,決定票會不會重複或漏掉(第 38 頁)。
② 動手玩:收件櫃台
原書 Step 2High-level design · Figure 2–3
從同步的一條線,到用兩個 message queue 拆開
這一步要解決的問題開票所和中選會的速度不一樣,怎麼不互相拖累?
📖 原書 即時大數據處理裡,資料是 unbounded data stream:聚合服務的輸入是 raw data 的無界串流,輸出是聚合結果(Figure 2)。
📖 原書 Asynchronous processing
- Figure 2 是同步的:producer 和 consumer 的處理能力不一定一樣
- 流量突然暴增、事件遠超過 consumer 能消化 → consumer 可能 out-of-memory 或意外關機
- 同步鏈上任何一個元件掛了,整個系統停擺
- 常見解法:用 message queue(Kafka) 解耦 producer 和 consumer,變成非同步,兩邊可以各自 scale
白話:producer=丟單子的一方(開票所);consumer=拿去處理的一方(中選會);out-of-memory=記憶體塞爆;解耦=兩邊不用互等。
📖 原書 Figure 3 Log watcher、aggregation service、database 由兩個 MQ 解耦。Database writer 從 MQ poll 資料、轉成資料庫格式、寫進資料庫。第一個 MQ 也被另一個 database writer 消費,寫進 raw data database。
原書 Step 2兩個 MQ 裡放什麼 · Table 13–15 · Figure 4
為什麼不直接寫進資料庫?為了 exactly-once
這一步要解決的問題兩個收件櫃台裡各放什麼?為什麼不直接寫進資料庫?
Table 13 第一個 MQ:點擊事件
| ad_id | click_timestamp | user_id | ip | country |
|---|
第二個 MQ:兩種資料
每分鐘粒度的點擊數
| ad_id | click_minute | count |
|---|
Table 14
每分鐘粒度的 top N
| update_time_minute | most_clicked_ads |
|---|
Table 15
📖 原書「你可能會想問為什麼不把聚合結果直接寫進資料庫。簡短的答案是:我們需要像 Kafka 這樣的第二個 MQ,才能做到端到端的 exactly-once 語意(atomic commit)。」
原書在這裡只給結論,細節(offset 存哪、什麼時候存、分散式交易)在 Step 3 的 Delivery guarantees,第 36–41 頁。
到這裡你已經會了小結 1 / 5
- event
- QPS · GB
- MQ · offset
- MapReduce
- stream · batch
- window
- event time
- watermark
- at-least once
- exactly-once
- 2PC
- reconciliation
- columnar
到這裡你已經會了:票從哪來、送到哪
- 每次點擊是一個 event(一行紀錄);把很多行數成一個數字叫 aggregation。原書兩種都存。
- 原書的量:每天 10 億次、平均每秒 1 萬(QPS)、尖峰 5 萬、每天 100 GB。
- 開票所把結果丟進收件櫃台(MQ)就能繼續數;接手的人看 offset 知道從哪號接。
下一階要解決的問題
每秒 5 萬張票,一個中選會數不完。怎麼分頭數、再合起來?
延伸基礎第 4 階 · MapReduce懂的人可以跳過
- event
- QPS · GB
- MQ · offset
- MapReduce
- stream · batch
- window
- event time
- watermark
- at-least once
- exactly-once
- 2PC
- reconciliation
- columnar
票太多一個人數不完:分堆、各自數、再合計
① 先想像
一個人數 9,000 張票要 90 分鐘。找三個人:先照候選人號碼分三堆,各數各的,最後把三個數字抄到總表。
你猜猜看:分給 3 個人各數 3,000 張,大約要多久?
三人同時數,各 30 分鐘;再加上分堆和合計的一點時間。人越多越快,但分堆和合計省不掉。
③ 這叫做 MapReduce、partition
MapReduce:先分堆(map),各自數,再合併(reduce)。partition:分出來的那一堆,每堆交給一個人。
④ 跟這章的關係
原書的聚合服務就是 Map → Aggregate → Reduce,用 ad_id 分堆(下一頁)。
② 動手玩:12 張票、3 位候選人
原書 Step 2Aggregation service · Figure 5–7
MapReduce 的 DAG:Map、Aggregate、Reduce
這一步要解決的問題每秒 5 萬張票,怎麼分給好幾台機器一起數?
Reduce node
把所有 Aggregate 的結果合成最終結果。Figure 7:三個 Aggregate 各有自己的 top 3,Reduce 把 9 個縮成 3 個。中間資料放記憶體,節點間用 TCP(不同 process)或 shared memory(不同 thread)溝通,把 big data 變成 little / regular-size data。
📖 原書 MapReduce 框架很適合聚合點擊事件,DAG(directed acyclic graph)是好的模型:把系統拆成小的計算單元,每個節點只做一件事,結果送給下游。
Map node
讀資料、過濾、轉換,例如 ad_id % 2 = 0 送 node 1、其他送 node 2。為什麼不讓 aggregate node 直接訂閱 Kafka partition?可以,但①輸入可能要先清理或正規化;②我們不一定能控制資料怎麼產生,同一個 ad_id 可能落在不同 partition。
Aggregate node
每分鐘在記憶體裡依 ad_id 計數。在 MapReduce 的典範裡它其實是 Reduce 的一部分,所以 map-aggregate-reduce 其實是 map-reduce-reduce。
原書 Step 2Main use cases · Figure 8–9
Use case 1、2:點擊數,和前 N 名
這一步要解決的問題照這個流程,怎麼回答「幾次」和「前幾名」?
📖 原書 Use case 1:彙總點擊數
輸入事件在 Map node 依 ad_id % 3 分區,再由 Aggregation node 計數。Figure 8 的輸出:過去 1 分鐘 ad3 被點 4 次、ad1 3 次、ad2 5 次。
📖 原書 Use case 2:回傳 top N
Figure 9 是 top 3 的簡化版,可以推廣到 top N。事件依 ad_id map;每個 Aggregate node 維護一個 heap,有效率地取得節點內的前 3 名;最後 Reduce node 每分鐘把 9 個(每個 node 3 個)縮成全域前 3 名:ad3、ad1、ad2。
白話:heap=一種隨時拿得到最大值的排法;top N=前 N 名(13 章)。
為什麼可以只送前 3 名?因為依 ad_id 分區,同一則廣告的所有點擊都在同一個 node。如果同一則廣告散在兩個 node,各自的前 3 名加起來就不一定是全域前 3 名了。
原書 Step 2Use case 3 · Table 16 · star schema
Use case 3:過濾,就是先把每個維度都算好
這一步要解決的問題「只看美國的點擊」這種問題,怎麼快速回答?
📖 原書 要支援「只看 ad001 在美國的點擊數」,可以預先定義過濾條件,依條件聚合:
| ad_id | click_minute | country | count |
|---|---|---|---|
| ad001 | 202101010001 | USA | 100 |
| ad001 | 202101010001 | GPB | 200 |
| ad001 | 202101010001 | others | 3000 |
| ad002 | 202101010001 | USA | 10 |
| ad002 | 202101010001 | GPB | 25 |
| ad002 | 202101010001 | others | 12 |
Table 16Aggregation results(filter by country;「GPB」照原書寫法)
這叫 star schema
data warehouse 常用的技巧,過濾欄位叫 dimension。優點:①簡單好懂好做;②現有的聚合服務可以重複使用來建更多 dimension,不需要額外元件;③結果是預先算好的,依條件查很快。限制:會產生多很多 bucket 和紀錄,尤其過濾條件很多時。
動手算:dimension 一多,紀錄會爆多少
🔭 示意 這是上限(每則廣告每分鐘每個組合都有點擊才會到);實際上沒點擊的組合不會產生紀錄。
延伸基礎第 5 階 · stream、batch懂的人可以跳過
- event
- QPS · GB
- MQ · offset
- MapReduce
- stream · batch
- window
- event time
- watermark
- at-least once
- exactly-once
- 2PC
- reconciliation
- columnar
流水線,還是月底結帳?
① 先想像
便當店有兩種算帳法。每賣一個就更新「今天賣了幾個」,像流水線;或收據全丟進抽屜,月底結帳時一次算。
你猜猜看:哪一種比較快知道結果?哪一種比較容易整批重算?
流水線隨時有最新數字;月底結帳要等,但收據都還在抽屜,算錯了整疊倒出來重算就好。
③ 這叫做 stream、batch processing
stream processing:資料一到就處理(流水線)。batch processing:攢一批、定時一次處理(月底結帳)。
④ 跟這章的關係
開票夜的即時看板是流水線,選後封箱重點是月底結帳。原書兩種都用(第 22–24 頁)。
② 動手玩:每分鐘來 10 張票
原書 Step 3Deep dive 目錄 · Streaming vs batching · Table 17
三種系統:online service、batch、streaming
這一步要解決的問題這套系統是流水線,還是月底結帳?三種系統差在哪?
| Services(online system) | Batch system(offline) | Streaming system(near real-time) | |
|---|---|---|---|
| Responsiveness | 快速回應 client | 不需要回應 client | 不需要回應 client |
| Input | 使用者 request | 有界、大小有限的大量資料 | 沒有邊界(無限串流) |
| Output | 回應給 client | Materialized view、聚合指標等 | Materialized view、聚合指標等 |
| Performance measurement | Availability、latency | Throughput | Throughput、latency |
| Example | Online shopping | MapReduce | Flink |
📖 原書 Table 17Comparison of three types of systems(出自 DDIA)
白話:throughput=一段時間處理多少;latency=一件事要等多久;availability=隨時都開著;materialized view=事先算好、存起來的結果。
📖 原書 Step 3 要深入的題目
- Streaming vs batching
- Time 與 aggregation window
- Delivery guarantees
- Scale the system
- Data monitoring 與 correctness
- Final design diagram
- Fault tolerance
📖 原書 這個設計兩種都用
Figure 3 是 stream processing:資料一到就處理,近即時地產生聚合結果。Batch processing 則用在歷史資料備份。
文組翻譯:online 是櫃台結帳,客人在等;batch 是月底關帳,一次算一大疊;streaming 是開票夜的即時看板,票一直來、看板一直更新。
原書 Step 3Lambda vs Kappa · Figure 10
兩條路還是一條路:lambda 與 kappa
這一步要解決的問題流水線和月底結帳,要寫兩套程式,還是一套?
📖 原書 Lambda
同時有 batch 和 streaming 兩條處理路徑。缺點:兩條路就是兩套 codebase 要維護。
📖 原書 Kappa
把 batch 和 streaming 合成一條處理路徑:用同一個 stream processing engine 同時處理即時資料和持續的資料重處理。
📖 原書 本章用 Kappa
歷史資料的重處理,也走即時的聚合服務(見下一頁 Data recalculation)。
文組翻譯:Lambda 是「開票夜一組人即時唱票、另一組人隔天慢慢點全部選票」,兩組規則要一模一樣,否則對不上。Kappa 是「只有一組人,要重數就把選票再唱一次」。
原書 Step 3Data recalculation · Figure 11
發現 bug 之後:從原始資料重算一次
這一步要解決的問題發現算錯了,怎麼重算,又不影響即時看板?
📖 原書 有時候必須重算聚合資料,又叫 historical data replay。例如發現聚合服務有重大 bug,要從 bug 引入的時間點開始,用 raw data 重算。
- Recalculation service 從 raw data storage 取資料,這是 batched job
- 取出的資料送到專用的聚合服務,讓即時處理不受歷史重播影響
- 聚合結果送到第二個 MQ,再更新到 aggregation database
重算流程重用資料聚合服務的程式,只是資料來源不同(raw data)。這就是上一頁說的 Kappa:重算也走同一套聚合邏輯。
文組翻譯:發現某個開票所的計票機有 bug,就把那段時間的原始選票封箱拿出來,交給另一組工作人員用同一套規則重數,數完更新總表;即時開票照常進行。
到這裡你已經會了小結 2 / 5
- event
- QPS · GB
- MQ · offset
- MapReduce
- stream · batch
- window
- event time
- watermark
- at-least once
- exactly-once
- 2PC
- reconciliation
- columnar
到這裡你已經會了:怎麼數
- 一個人數不完就分堆:map 分堆、各堆自己數、reduce 合計,這是 MapReduce。同一則廣告一定分在同一堆(partition)。
- 流水線(stream)隨時有新數字;月底結帳(batch)慢,但好重算。原書兩種都用。
- 發現 bug,就把原始紙條(raw data)倒出來,用同一套規則重數一次(Kappa、資料重算)。
下一階要解決的問題
看板「每分鐘公布一次」,那一分鐘怎麼切?晚到的票又算哪一分鐘?
延伸基礎第 6 階 · window懂的人可以跳過
- event
- QPS · GB
- MQ · offset
- MapReduce
- stream · batch
- window
- event time
- watermark
- at-least once
- exactly-once
- 2PC
- reconciliation
- columnar
看板「每分鐘公布一次」:這一分鐘從哪裡切?
① 先想像
看板 A 每分鐘公布「這一分鐘幾票」,一格接一格、不重疊。看板 B 每分鐘更新一次「最近 3 分鐘」的人氣排行。
你猜猜看:一張 01:30 投的票,在看板 B 會被算進幾次?
結算到 02:00、03:00、04:00 的三個框都包含 01:30,這三個框互相重疊。右邊拖動框的位置看看。
③ 這叫做 tumbling、sliding window
tumbling window:等長、不重疊的格子,一張票只進一格。sliding window:會重疊、往前滑的框,一張票可能進好幾個框。
④ 跟這章的關係
原書:每分鐘點擊數用 tumbling;「最近 M 分鐘的前 N 名」用 sliding(第 32 頁)。
② 動手玩:6 分鐘、12 張票
延伸基礎第 7 階 · event time懂的人可以跳過
- event
- QPS · GB
- MQ · offset
- MapReduce
- stream · batch
- window
- event time
- watermark
- at-least once
- exactly-once
- 2PC
- reconciliation
- columnar
郵寄選票:看郵戳,還是看收件日?
① 先想像
一張郵寄選票 17:59 寄出、18:20 才送到,截止時間是 18:00。這張票該不該算?
你猜猜看:用哪一個時間判斷比較公平?
郵戳才是真正投票的時間。但郵戳是寄件那一端蓋的,可能蓋錯或造假;手機的時鐘也一樣。
③ 這叫做 event time、processing time
event time:點擊發生的時間,像郵戳。processing time:系統收到、處理的時間,像收件日。
④ 跟這章的關係
原書選 event time,因為計費要準;時鐘造假交給防詐元件(下一頁)。
② 動手玩:4 張票,郵局有延遲
原書 Step 3Time · Figure 12 · Table 18
這張票算哪一分鐘?event time vs processing time
這一步要解決的問題一次點擊,該算進哪一分鐘?
📖 原書 聚合需要 timestamp,它可以在兩個地方產生:
- Event time:廣告被點擊的那一刻
- Processing time:處理這筆事件的聚合 server 的系統時間
因為網路延遲和非同步環境(資料要經過 MQ),兩者的差距可能很大。Figure 12 的 event 1 晚了 5 小時才到聚合服務。
| Pros | Cons | |
|---|---|---|
| Event time | 聚合較準確:client 確切知道廣告何時被點 | 依賴 client 產生的 timestamp:client 時間可能錯,或被惡意使用者偽造 |
| Processing time | server timestamp 較可靠 | 事件很晚才到時,timestamp 不準 |
📖 原書 Table 18Event time vs processing time
📖 原書 用 event time 就要處理延遲事件;用 processing time 結果可能不準。沒有完美解。因為資料準確性很重要,原書建議用 event time,再用 watermark 處理「稍微」延遲的事件。
文組翻譯:郵寄選票,該看郵戳日期(event time)還是收件日期(processing time)?看郵戳比較公平,但郵戳可能被偽造;看收件日期很可靠,但郵局慢就不公平。
動手玩Event time vs processing time
同一批點擊,兩種時鐘,兩張不同的計票表
這一步要解決的問題同一批點擊用兩種時鐘分桶,差在哪裡?
怎麼看
- 上面那條是點擊發生的時間,下面那條是聚合 server 收到的時間;中間的斜線就是延遲
- 灰色數字是「正確答案」:照真實點擊時間每分鐘幾次
- 延遲拉大:processing time 的計數開始「搬家」到下一分鐘
- 勾「手機時鐘快了」:event time 的計數反而錯了,這是 Table 18 的 event time 缺點
📖 原書的取捨
原書選 event time,因為計費要準;client 時鐘錯或被偽造的問題,交給 ad fraud / risk control 元件。代價是:要等晚到的事件,就要有 watermark。
延伸基礎第 8 階 · watermark懂的人可以跳過
- event
- QPS · GB
- MQ · offset
- MapReduce
- stream · batch
- window
- event time
- watermark
- at-least once
- exactly-once
- 2PC
- reconciliation
- columnar
18:00 截止,再多等 15 分鐘:寬限期
① 先想像
規定是「郵戳 18:00 前的票,18:15 前送到都算」。18:15 一到,這一格就關門、公布。
你猜猜看:寬限期從 15 分鐘拉長成 2 小時,會怎樣?
等越久接住越多,大家也要等越久。總有幾張晚到很久的,等多久都接不住。
③ 這叫做 watermark
watermark:視窗關門前多等的寬限期。寬限期過了才到的,叫遲到事件(late event)。
④ 跟這章的關係
原書多等 15 秒(下一頁)。少數接不住的,交給事後驗票。
② 動手玩:10 張票,各晚到幾秒
原書 Step 3Watermark · Figure 13–14
視窗關門前多等 15 秒:watermark
這一步要解決的問題稍微晚到的點擊,怎麼不漏掉?
📖 原書 點擊在一分鐘的 tumbling window 裡聚合。如果用 event time 判斷事件屬於哪個視窗,window 1 會漏掉 event 2、window 3 會漏掉 event 5,因為它們在視窗結束後才稍微晚到。
📖 原書 解法:watermark,視為聚合視窗的延伸。多等 15 秒(可調),window 1 就能包含 event 2,window 3 就能包含 event 5。
Watermark 設多長?看業務需求
- 長:能接住很晚到的事件,但系統延遲變大
- 短:資料比較不準,但延遲小
- watermark 處理不了延遲很久的事件。為低機率事件做複雜設計不划算(ROI),少量的誤差用日終對帳修正(第 49 頁)
文組翻譯:開票所 18:00 截止,但規定「郵戳 18:00 前、18:15 前寄到的都算」。寬限期越長越公平,但總表越晚公布。
原書 Step 3Aggregation window · Figure 15–16
四種視窗,原書用其中兩種
這一步要解決的問題「每分鐘」和「最近 M 分鐘」,各用哪一種框?
📖 原書 依 Martin Kleppmann《Designing Data-Intensive Applications》,window function 有四種:tumbling(又叫 fixed)、hopping、sliding、session。原書只討論最相關的兩種:
Tumbling window → use case 1
時間切成等長、不重疊的區塊。很適合「每分鐘聚合一次點擊數」。
Sliding window → use case 2
事件依指定的間隔,被分到一個沿著資料流滑動的視窗裡,視窗可以重疊。很適合「過去 M 分鐘點擊最多的前 N 名」。Figure 16:3 分鐘的視窗,每分鐘跑一次。
文組翻譯:tumbling 是「每小時公布一次這一小時的票數」;sliding 是「每小時更新一次最近三小時的人氣排行」,同一張票會被算進三次排行。
動手玩Tumbling / sliding · 晚到事件 · watermark
把 watermark 拉長:接住更多晚到的票,但更晚公布
這一步要解決的問題寬限期拉長或縮短,取捨在哪裡?
到這裡你已經會了小結 3 / 5
- event
- QPS · GB
- MQ · offset
- MapReduce
- stream · batch
- window
- event time
- watermark
- at-least once
- exactly-once
- 2PC
- reconciliation
- columnar
到這裡你已經會了:時間
- 看板每分鐘結一次:不重疊的格子叫 tumbling window;會重疊、往前滑的框叫 sliding window。
- 一張票有兩個時間:點擊發生時(event time,郵戳)和系統收到時(processing time,收件日)。原書看郵戳。
- 視窗關門前多等一下(watermark):等越久接住越多,也越晚公布;接不住的交給事後驗票。
下一階要解決的問題
開票所斷線,不確定剛剛送到了沒有。再送一次可能重複,不送可能漏掉。怎麼辦?
延伸基礎第 9 階 · at-least once懂的人可以跳過
- event
- QPS · GB
- MQ · offset
- MapReduce
- stream · batch
- window
- event time
- watermark
- at-least once
- exactly-once
- 2PC
- reconciliation
- columnar
回條沒回來:再送一次,還是算了?
① 先想像
開票所送出結果,等中選會回一張「收到了」的回條。回條沒來:可能結果沒到,也可能回條在路上掉了。
你猜猜看:開票所想保證「一張都不漏」,沒收到回條時該怎麼做?
再送一次就不會漏。但如果上一次其實送到了,中選會會收到兩份、算兩次。
③ 這叫做 ack、at-least once
ack:收到的回條。at-least once:沒回條就重送,不會漏、可能重複;不重送的叫 at-most once。
④ 跟這章的關係
Kafka 這類 MQ 提供三種送法(下一頁)。重複了怎麼辦,下一階。
② 動手玩:送 10 批結果
原書 Step 3Delivery guarantees · Data deduplication
at-most once、at-least once、exactly once
這一步要解決的問題斷線重送,怎麼不漏也不重複?
點一個語意,看一場「送到一半當機」
📖 原書 聚合結果用來計費,準確和完整都很重要。系統要能回答:怎麼避免處理重複事件?怎麼確保所有事件都被處理? Kafka 這類 MQ 通常提供三種語意。
- 多數情況,能接受少量重複的話,at-least once 就夠了
- 但本系統不行:「資料差幾個百分點,就可能是幾百萬美元的差異」。所以原書建議 exactly-once,並推薦看 Yelp 的實作
📖 原書 重複資料從哪來
- Client 端:client 可能重送同一事件。惡意重送最好交給 ad fraud / risk control 元件
- Server outage:聚合節點在聚合途中掛掉、上游還沒收到 ack,同一批事件可能被再送一次、再聚合一次
延伸基礎第 10 階 · exactly-once懂的人可以跳過
- event
- QPS · GB
- MQ · offset
- MapReduce
- stream · batch
- window
- event time
- watermark
- at-least once
- exactly-once
- 2PC
- reconciliation
- columnar
每份結果單印上編號:收過的就丟掉
① 先想像
每份結果單印上「B 開票所 · 第 3 批」。中選會先查名單:記過了就丟掉;沒記過,才加進總表、再記上名單。
你猜猜看:「B · 第 3 批」被重送了 3 次,中選會有查名單。總表加了幾次?
第一次加進總表、記上名單;後兩次一查就丟掉。前提是「加總表」和「記名單」一起完成。
③ 這叫做 dedup、exactly-once
dedup:認出重複、丟掉。exactly-once:重送也只算一次,做法是 at-least once 加上 dedup。
④ 跟這章的關係
原書的「編號」就是 offset。Figure 17–19 都在找它該什麼時候記(下一頁)。
② 動手玩:結果單送到中選會
原書 Step 3Data deduplication · Figure 17–18
offset 該什麼時候存?兩個都會出事的版本
這一步要解決的問題編號(offset)什麼時候記,才不會重複也不漏?
📖 原書 Figure 17:步驟 6 失敗 → 重複
Aggregator 把消費進度(offset)存在上游 Kafka。步驟 6 失敗(例如 Aggregator 掛了)時,offset 100–110 的事件已經送到下游,但新的 offset 110 沒寫回上游。新的 Aggregator 從 100 重新消費,同一批又算一次。
白話:Aggregator=數票的節點;upstream / downstream=上游 / 下游的 Kafka;HDFS、S3=放檔案的大倉庫。
📖 原書 Figure 18:先存 offset → 遺失
最直接的解法:offset 存到外部檔案儲存(HDFS 或 S3)。步驟 3 只在外部儲存的最後 offset 是 100 時才處理 100–110;如果已經是 110,就略過 110 之前的事件。
大問題:offset 在聚合結果送下游之前(步驟 3.2)就存了。如果步驟 4 因 Aggregator 掛掉而失敗,新節點看到 offset 是 110,100–110 永遠不會被處理。
延伸基礎第 11 階 · 2PC懂的人可以跳過
- event
- QPS · GB
- MQ · offset
- MapReduce
- stream · batch
- window
- event time
- watermark
- at-least once
- exactly-once
- 2PC
- reconciliation
- columnar
總表和名單在兩個房間:怎麼保證一起改?
① 先想像
總表在 A 房間、名單在 B 房間,各有一位管理員。兩邊都要改,改到一半停電,就會一邊有、一邊沒有。
你猜猜看:A 已經把第 3 批加進總表,B 還沒記上名單就停電。來電後第 3 批重送,會?
名單上沒有第 3 批,所以又加了一次。兩個房間要像一個房間一樣:一起成功、一起不算。
③ 這叫做 transaction、2PC
transaction:一組改動要嘛全成、要嘛全不算。2PC(two-phase commit):兩台機器先各說「準備好了」,再一起生效。
④ 跟這章的關係
原書 Figure 20 的 distributed transaction 就是 2PC(下一頁)。Triton 的看法在第 64 頁。
② 動手玩:點一個步驟,在它之前停電
原書 Step 3Data deduplication · Figure 19–20
收到 ack 才存 offset,最後包進一個分散式交易
這一步要解決的問題怎麼讓「送下游」和「記 offset」一起成功、或一起不算?
📖 原書 Figure 19:避免遺失
為了不掉資料,要在收到下游 ack 之後才存 offset(5.1 Save offset)。但如果 Aggregator 在 5.1 之前掛了,100–110 會再送下游一次:又回到重複。
📖 原書 Figure 20:exactly-once
要做到 exactly-once,要把步驟 4 到步驟 6 的操作放進同一個 distributed transaction。分散式交易是跨多個節點運作的交易,任何一個操作失敗,整個交易 rollback。
📖 原書「在大規模系統裡 dedupe 資料並不容易。怎麼做到 exactly-once 是進階題目」,細節請看參考資料 [19](Flink 的 end-to-end exactly-once)。
🗣️ Triton 「分散式交易」就是 2PC,Triton 的看法見第 64 頁。
動手玩Exactly-once 的當機點
你選在哪一步當機:offset 100–110 會被算幾次?
這一步要解決的問題四個版本,各在哪一步當機會出事?
怎麼玩
上面選原書的四個版本。點任何一個步驟 = Aggregator 在這一步開始前掛掉、新的接手;看下游收到 100–110 這批幾次:0 遺失、2 重複、1 才對。
你會發現
| 版本 | 最壞情況 |
|---|---|
| Fig 17:offset 存上游、最後才 ack | 重複 |
| Fig 18:先存 offset 再送下游 | 遺失 |
| Fig 19:下游 ack 後才存 offset | 重複 |
| Fig 20:4–6 包成分散式交易 | 剛好一次 |
🗣️ Triton 的方法 一個一個當機點去分析,正是 Triton 在 123 分析 Stripe 收款的寫法:「如果在第1-2步之間當掉……」。見第 64 頁。
到這裡你已經會了小結 4 / 5
- event
- QPS · GB
- MQ · offset
- MapReduce
- stream · batch
- window
- event time
- watermark
- at-least once
- exactly-once
- 2PC
- reconciliation
- columnar
到這裡你已經會了:不多不少
- 沒回條就重送(at-least once):不會漏,但可能重複。
- 每批結果有編號(offset),收過就丟(dedup):重送也只算一次(exactly-once)。
- 「送出結果」和「記編號」在兩台機器上又要一起成功,就要分散式交易(2PC)。
下一階要解決的問題
原書接著講:點擊每 3 年翻倍,收件櫃台、數票的人、資料庫怎麼加?最後怎麼驗票?
原書 Step 3Scale the system · message queue · Figure 21
每 3 年翻倍:先 scale message queue
這一步要解決的問題點擊每 3 年翻倍,收件櫃台怎麼跟著變大?
📖 原書 Producers / Consumers
- Producer:不限制數量,很容易 scale
- Consumer:consumer group 的 rebalancing 機制可以加減節點。Figure 21 多加兩個 consumer,每個只處理一個 partition
- 系統有數百個 consumer 時,rebalance 可能要好幾分鐘甚至更久,所以加 consumer 盡量在離峰時段
📖 原書 系統由三個獨立元件組成:message queue、aggregation service、database。它們已經解耦,可以各自 scale。MQ 的 scale 在「Distributed Message Queue」一章講過,這裡只點幾個重點。
📖 原書 Brokers
- Hashing key:用
ad_id當 partition 的 hash key,同一則廣告的事件都在同一個 partition,aggregation service 從一個 partition 就能拿到某則廣告的所有事件 - Partition 數量:partition 數一改,同一個
ad_id可能被 map 到別的 partition。建議事先配足,避免在 production 動態增加 - Topic physical sharding:一個 topic 通常不夠,可依地區(
topic_north_america、topic_europe、topic_asia)或業務(topic_web_ads、topic_mobile_ads)拆。優點:吞吐量提高、每個 topic 的 consumer 變少、rebalance 變快。缺點:更複雜、維護成本更高
原書 Step 3Scale the aggregation service · Figure 22–23
聚合服務怎麼加速:多執行緒,或交給 YARN
這一步要解決的問題數票的機器,怎麼數得更快?
📖 原書 高階設計裡,聚合服務是 map/reduce 操作,Figure 22 是接線方式(細節見參考資料 [20])。加減節點就能水平擴展。怎麼提高聚合服務的吞吐量?兩個選項:
Option 1:不同 ad_id 給不同 thread
Figure 23:node 1 收 ad_id 1–3、node 2 收 4–6,每個 node 內每則廣告一個 thread。
Option 2:部署在 resource provider 上
例如 Apache Hadoop YARN,可以想成利用 multi-processing。
白話:thread=一個程式裡同時做事的工人;resource provider(例如 YARN)=幫你分配一大群機器的管理員;水平擴展=加機器。
📖 原書的結論 Option 1 比較好做、不依賴 resource provider;但實務上 Option 2 用得比較廣,因為加運算資源就能 scale。
原書 Step 3Scale the database · Figure 24
資料庫:Cassandra 的 virtual nodes
這一步要解決的問題資料庫加機器時,怎麼不用手動搬家?
📖 原書 Cassandra 原生支援水平擴展,方式類似 consistent hashing。
- 資料以適當的 replication factor 平均分給每個節點
- 每個節點依 hash 值存自己在環上的那一段,也存其他 virtual node 的副本
- 新增節點時,cluster 自動在所有節點間 rebalance virtual nodes,不需要手動 resharding(細節見 Cassandra 官方文件 [22])
白話:replication factor=每份資料抄幾份;virtual node=每台機器管很多小段(05 章第 19 頁);resharding=重新分堆搬家。
文組翻譯:沒有 virtual node 時,新來的唱票員只能從隔壁那一個人手上接走一大箱;有 virtual node 時,每個人的工作本來就切成很多小份,新人從每個人手上各接一小份,大家都輕鬆一點。
🗣️ Triton「再三警告:流量不夠大請勿用上noSQL」117
原書 Step 3Hotspot issue · Figure 25
大廣告主的廣告特別熱:多派幾個節點分著數
這一步要解決的問題某則廣告特別熱,那一堆特別厚,怎麼辦?
📖 原書 收到的資料比別人多很多的 shard 或服務叫 hotspot。大公司的廣告預算是幾百萬美元,廣告被點得特別多;事件依 ad_id 分區,某些聚合節點就會收到多很多事件,可能過載。
解法:多分配幾個聚合節點處理熱門廣告。假設每個節點只能處理 100 個事件:
- 聚合節點裡有 300 個事件,超過容量,透過 resource manager 申請額外資源
- resource manager 多分配兩個聚合節點
- 原節點把事件切成 3 組,每個節點處理 100 個
- 結果寫回原本的聚合節點
更進階的做法:Global-Local Aggregation、Split Distinct Aggregation(見 Flink 效能調校文件 [23])。
文組翻譯:熱門候選人那一箱特別厚,就臨時找兩個人來分三疊一起數,數完交回給原本的唱票員合計。
原書 Step 3Fault tolerance · Figure 26–27
聚合在記憶體裡,節點掛了怎麼辦:snapshot
這一步要解決的問題數到一半的機器當機,記憶體裡的數字怎麼救回來?
📖 原書 聚合在記憶體裡進行,節點掛掉時聚合結果也跟著不見。可以從上游 Kafka broker replay 事件重建計數。
- 從 Kafka 最開頭 replay 很慢。好做法:把「系統狀態」(例如上游 offset)存成 snapshot,從最後一次的狀態恢復
- 本設計的「系統狀態」不只 offset,還要存「過去 M 分鐘的 top N」這類資料(Figure 26)
- 有了 snapshot,failover 很簡單:節點掛了,起一個新節點,從最新的 snapshot 恢復(Figure 27)
- snapshot 之後才到的新事件,新節點再從 Kafka broker 拉來 replay
文組翻譯:唱票員每數一段,就在小本子上記「數到第幾張、目前各候選人幾票」。他昏倒了,接手的人翻開小本子從那一頁接著數,不用從第一張重來。
延伸基礎第 12 階 · reconciliation懂的人可以跳過
- event
- QPS · GB
- MQ · offset
- MapReduce
- stream · batch
- window
- event time
- watermark
- at-least once
- exactly-once
- 2PC
- reconciliation
- columnar
開票夜過後,把封箱的選票再點一次
① 先想像
開票夜的看板是邊唱邊加的。隔天把封箱的原始選票再點一次,跟看板對:每個開票所的數字一樣嗎?
你猜猜看:看板寫 B 開票所 1,020 票,重點出來是 1,000 票。最可能是?
看板比重點多,表示有票被算了兩次。看板比較少,才比較可能是晚到或漏掉。
③ 這叫做 reconciliation
reconciliation:拿兩份各自算出來的結果互相對,中文叫「對帳」。拿來對的那份,通常是 batch 重算的。
④ 跟這章的關係
原書每天結束時用 batch 重算一次,跟即時結果對(下一頁)。Triton 的省力版在第 66 頁。
② 動手玩:放幾個錯進去,再對帳
原書 Step 3Data monitoring and correctness
持續監控,加上日終對帳
這一步要解決的問題怎麼知道系統數得對、數得夠快?
📖 原書 Continuous monitoring
結果用於 RTB 和計費,監控健康與正確性很關鍵。可以監控:
- Latency:每個階段都可能產生延遲,追蹤事件流經各部分的 timestamp,差值就是 latency metric
- Message queue size:突然變大可能要加聚合節點。Kafka 是以分散式 commit log 實作的 MQ,所以要看 records-lag
- 聚合節點的系統資源:CPU、disk、JVM 等
白話:metric=持續記錄的一個數字;records-lag=櫃台裡還有幾張單沒處理;JVM=跑 Java 程式的環境。
📖 原書 Reconciliation
對帳 = 比較不同的資料集,確保資料完整。和銀行不同:銀行可以拿你的紀錄跟銀行的紀錄比,廣告點擊彙總沒有第三方結果可以對。
- 每天結束時用 batch job,把每個 partition 的點擊事件依 event time 排序,跟即時聚合的結果對帳
- 準確度要求更高,就用更小的視窗,例如 一小時
- 不管用哪種視窗,batch 的結果都可能跟即時結果不完全一致,因為有些事件晚到
文組翻譯
開票夜看板是即時的,隔天選委會把原始選票再點一次,跟看板對。點出來不一樣,先查是不是晚到的郵寄選票,再查是不是哪個開票所算錯。
🗣️ Triton 對帳他有一套「先驗血、再照 MRI」的做法,見第 66 頁。
原書 Step 3Final design · Figure 28
最終設計:即時路徑、重算路徑、對帳
這一步要解決的問題把前面的零件全部接起來,是什麼樣子?
原書 Step 3Alternative design · Figure 29
另一種做法:Hive、ElasticSearch、ClickHouse
這一步要解決的問題一定要自己組管線嗎?有沒有現成的?
📖 原書 通才型的系統設計面試,不期待你懂大數據管線裡各種專門軟體的內部。重點是說明思考過程、討論取捨,所以原書提出的是通用解法。
- 另一個選項:點擊資料存在 Hive,上面建一層 ElasticSearch 加快查詢
- 聚合通常在 OLAP 資料庫做,例如 ClickHouse 或 Druid
- Figure 29 中間還有一個 Risk Control Engine,左邊是 data scientist 的查詢,右邊是給廣告主看的 Merchant Facing Analytics
- 更多細節見參考資料 [26](Uber 用 Flink、Kafka、Pinot 做的 exactly-once 廣告事件處理)
白話:Hive=把一大堆檔案當成表格來查;ElasticSearch=搜尋引擎;OLAP 資料庫=專做分析報表的資料庫。
文組翻譯:與其自己組一台計票機,不如買現成的「計票工廠」:資料倒進去、SQL 問出來。
原書 Step 4Wrap up · Chapter summary
原書的收尾:七個重點,一張心智圖
這一步要解決的問題原書最後要你記住哪些重點?
📖 原書 本章涵蓋
- Data model 與 API design
- 用 MapReduce 典範聚合點擊事件
- Scale message queue、aggregation service、database
- 緩解 hotspot
- 持續監控系統
- 用 reconciliation 確保正確性
- Fault tolerance
點擊彙總是典型的大數據處理系統。如果熟悉 Apache Kafka、Apache Flink、Apache Spark 這類業界標準方案,會更容易理解和設計。
原書到這裡結束。下一頁開始是 Triton 的觀點。
Triton 觀點先問三個問題
動手畫 Kafka 之前:多大、能不能錯、誰在等
你猜猜看:原書的設計是為「每天 10 億次點擊」準備的。如果你家每天只有 1 萬次,照抄會怎樣?
1 萬次是原書的十萬分之一。Triton 先問下面三題,就是為了不要蓋太大的工廠。
① 資料到底多大?
「資料量不夠大 (<100GB) 就乖乖回去用 RDBMS 就好啦」🗣️ Triton 本人說 054-data-analysis.pdf.md · 前言(投影片標題 Data Analysis WITHOUT RDBMS)
「明明是數據分析就叫什麼「BigData」」🗣️ 146 · 談 buzzword
② 這份資料能不能錯?
「談Data嘛,一般我們看的是:A) Consistency 到底這份data是否錯一點也沒所謂的?……還是他絕對不能錯,而且有需要跟其他資料一起all-or-none地改動? B) Durability 你這份資料打算用多久? C) Usage 這份資料的Read freq和Write freq是多少?」🗣️ Triton 本人說 117-喵看Data 的思維.md
③ 誰在等這份報表?
「一切的schema design,都以服務end-user為優先」(同一句寫了四次)🗣️ Triton 本人說 023-OLTP database,偶然要面對reporting相關的query怎麼辦.md
「不要整天看別人FAANG架構怎樣子,我們那來吧。FAANG一小時預算的比大部份公司一年份的都要大。」🗣️ 023
🔭 這三題套到原書 原書的答案是:① 每天 100GB;② 全部都不能錯(計費);③ 幾分鐘內給 dashboard。三題都是「最難」的那一格,所以得出最重的設計。Triton 不是說原書錯,而是說這三題你家的答案很可能不一樣,答案不一樣,設計就該不一樣。
Triton 觀點 · 動手算我的資料有多大?
把你家的點擊數放進去,看落在哪一格
你猜猜看:原書「每天 100 GB」,Triton「< 100GB 用 RDBMS」。兩個 100 GB 一樣嗎?
原書一個月就 3 TB。把你家的數字放進左邊看看。
「對一般中小型公司……資料庫很少> 100GB的」🗣️ Triton 本人說 035-SQL_reporting.pdf.md · 理想與現實
「如果你沒足夠的錢和資料庫( 100GB )– RDBMS 的 Read Replica慢慢跑就好」🗣️ 054 · 總結
「(當然,如果你的系統流量是 100 RPS以下的,你所有東西全用postgresql也沒什麼差)」🗣️ 117
「如果系統還沒到每秒1K Message的,kafka對你會是overkill。」🗣️ 138-喵談 rabbitMQ 和 kafka.md
🔭 100GB、100 RPS、1K msg/s 三條線是 Triton 的原話;判讀文字裡「100GB 以上怎麼辦」是依 054、023 推論。
Triton 觀點哪些點擊可以掉?
原書把每一筆點擊都當成帳單;Triton 會先把資料分級
你猜猜看:原書把每一筆點擊都當成帳單。dashboard 上「這小時的點擊趨勢」差了 0.1%,會怎樣?
趨勢圖錯一點不會死人;月底跟廣告主收錢的數字才要一分不差。Triton 先把資料分級。
「不需要Consistency的東西就別用RDBMS來存啦。 RDBMS為了Strong Consistency犧牲了很很很多的效能。」🗣️ Triton 本人說 117 · 我的建議 1
「別把低價值資料放到RDBMS … 低價值資料 = 輕微誤差也死不了人的數據 – 例子:網站的每秒流量」
「善用 Sampling … 例子:公司的總營業額 – 用來報稅的,一定要完全準確 – 用來做市場計劃/趨勢分析的,不一定需要完全準確」🗣️ Triton 本人說 035 · 正確觀念
「log = 建立了便永不改動的數據,而且這些數據極少被單獨使用,一般都會經過 aggregation 用來產 生報告 – txt檔案是 log 的理想存放位置」🗣️ 012-Advanced_Database_Skills.pdf.md · 常犯錯誤:用 RDBMS作為 logging server
動手分:點一下,把它丟到「不能錯」或「錯一點沒關係」
點任何一個項目看看。
🔭 依 Triton 原則推論 原書用一條 exactly-once 管線同時服務計費、dashboard、top 100 和 data scientist。分級之後,真正要 exactly-once 的通常只剩「月底跟廣告主收錢的那個數字」,而那個數字不用每分鐘出,可以每天 batch 算、用原始 log 對帳。
Triton 的實戰076 HYPEBEAST · My journey in nano "Big-data"
Triton 自己做過的事件管線:S3 存原始、SQS 當緩衝、寫入先聚合
你猜猜看:原書為了不掉資料,加了 snapshot 和分散式交易。Triton 在 HYPEBEAST 做 user profiling,redis 當機掉了一點資料,要緊嗎?
user profiling 錯一點不會死人,原始事件也另外存在 S3。Triton 直接接受損失,換來簡單(下一頁逐項看)。
背景:HYPEBEAST「> 3M MAU」,要做 semi-realtime 的 user profiling。事件是 client side events,不是廣告點擊,但問題的形狀一樣:大量小事件 → 聚合成計數。
076-mini-bigdata.pdf.md · 第 13–17 頁
Triton 的實戰076 · 逐項對照原書
076 的每個元件,對到原書的哪一塊
🗣️ Triton 076 投影片怎麼寫
- Event Receiver:「1st tier write buffering … Pack multiple events to one SQS Message to save money」
- Amazon Firehose and S3:「Store the events for future data mining」
- Amazon SQS:「2nd tier of write buffering, providing unlimited queue」
- Hotdata sync worker:「Put the dirty user profile from redis back to database – For design simplicity, single instance and single thread」
- 「If hotdata redis crashed, the data loss is acceptable」
- 「No need to use Sorted Set in redis – Pick Top N out of random 100 algorithm is good enough」
076-mini-bigdata.pdf.md · 第 13–17 頁
| 原書 | log watcher | Kafka(第一個 MQ) | raw data → Cassandra | aggregation service(記憶體) | database writer | exactly-once |
|---|---|---|---|---|---|---|
| 076 | Event Receiver | SQS | Firehose → S3 | Event Processor + Hotdata redis | Hotdata sync worker(單執行緒) | 接受 redis 當機掉資料 |
🔭 對照表是本簡報整理的。
文組翻譯:開票所把結果先裝箱(Event Receiver 打包),一份副本封存(S3),一份交給櫃台(SQS)。中選會的白板(redis)被擦掉一角也沒關係,封存的那份還在。
Triton 的實戰 · 動手玩Write aggregation
「Database Write is indepentent of traffic」
你猜猜看:先在記憶體加總、每 10 秒寫一次 DB。每秒事件從 1,000 漲到 50,000,DB 寫入次數會?
寫入次數只跟「有幾個 key、多久寫一次」有關。代價:當機時還沒寫的會掉。
「Write Aggregation – Prerequisite – The Write is clustered, not random … – If some system component crash, some data loss can be tolerated – Benefits – Reduce database write operation – Database Write is indepentent of traffic」🗣️ Triton 本人說 076 · 第 16 頁(拼字照原文)
「把要寫到UserStatistics的改動都buffer在Application Server的local memory,再用background thread把改動一點一點flush到DB。(這方案如果AS斷電會有data loss風險。不過嘛UserStatistics不見了一點點是死不了人的)」「(沒10K RPS前別做這種事)」🗣️ 117 · 我的建議 4
🔭 原書的 Aggregate node「每分鐘在記憶體裡計數」其實就是同一招;差別是原書為了不掉資料又加了 snapshot 和分散式交易,Triton 在「可以掉」的資料上直接接受損失,換來簡單。
延伸基礎第 13 階 · columnar懂的人可以跳過
- event
- QPS · GB
- MQ · offset
- MapReduce
- stream · batch
- window
- event time
- watermark
- at-least once
- exactly-once
- 2PC
- reconciliation
- columnar
一頁抄一張票,還是一個欄位一本冊子?
① 先想像
選票資料要抄成冊子。抄法一:一頁抄一張票的全部欄位。抄法二:每個欄位各一本,「廣告」一本、「時間」一本、「國家」一本。
你猜猜看:每張票 5 個欄位,只想數「每則廣告幾次」。抄法二要翻的量,大約是抄法一的幾分之幾?
只要翻「廣告」那一本。同一本裡都是同一種內容,很多重複的「ad001」,還能壓得很小。
③ 這叫做 columnar、Parquet
columnar:同一欄的資料存在一起。Parquet:一種 columnar 檔案格式,常放在 S3(雲端的檔案倉庫)。
④ 跟這章的關係
原書提過 S3 + Parquet,因為「很多人不熟」改用 Cassandra(第 12 頁)。Triton 怎麼看,下一頁。
② 動手玩:6 張票 × 5 個欄位
Triton 觀點原書放棄的那條路:S3 + columnar
寫一次、不改動的資料,就該用 columnar 檔案
你猜猜看:原書把 raw data 放 Cassandra 這種隨時可改的資料庫。可是點擊紀錄寫進去之後,還會再改嗎?
寫一次、不再改的資料,最適合一欄一本壓縮存放(第 59 頁)。Triton 054 講的就是這件事。
「Storage level compression ,理想是配上 Write-once架構 – 例子: SSTable in cassandra / HBase – 例子: apache parquet in OLAP」「OLAP 常常 write-once only – Columnar storage 的 multiple Random IO 不是問題 – Columnar storage 更能有效 compression」🗣️ Triton 本人說 054 · Compression、Why Columnar storage
「使用像 GCP BigQuery / AWS Athena之類的 OLAP服 務 跟據你的 Query 的 Resource 用量來收費 … – 如果你的 schema錯亂/有人下了笨 Query 你的帳單會是天價!!!」🗣️ 054 · 可能方案 2
「就Apache Parquet file with AWS Athena 啦」「parquet配athena可以有超高報表類效能的 但是,其應用有點「劍走偏鋒」 高度吃ETL層整理資料能力」💬 作者未標示 085-pure read-only的應用.md(短串,檔案沒有標作者,後段語氣像他人回覆)
🗣️ 023 的第 6 階段:「你的Reporting開始完全告別RDBMS了 你可能會用上DataLake那邊的方案,像是Apache parquet fileformat」
動手比:同一個查詢,row 和 column 各讀多少
🔭 示意 每筆 100B 依原書,平均分給 5 個欄位;實際壓縮率看資料。Athena 依掃描量收費,所以「讀多少」直接等於「付多少」。
Triton 觀點報表和 OLTP 的距離
報表要不要獨立出來?看你在第幾階段
你猜猜看:原書一開始就把報表獨立出來。小公司常見的反方向是:為了報表快一點,在主帳本上多加幾個 index。會怎樣?
index 是資料庫的目錄,每次寫入都要多維護一份。報表多是大範圍掃描,目錄幫不上忙。右邊揭曉 Triton 的原話。
🗣️ Triton 023 一步一步來的六個階段
「為了報表而建立 index – index 會大幅影響 master的 WRITE 效能 – Oracle 說:每個額外的 index 便多用3倍時間 – 報表能在 slave node 慢慢產生 – 報表很多時候需要 range scan , secondary B+ tree index 幫助不大」🗣️ Triton 本人說 012 · 常犯錯誤(schema 設計 1)
「資料庫重要原則:別為了報表去下index,因為大部份時候都不會真的有幫助的」🗣️ 104-利用Range Scan on Primary Key的好處.md
「在一般的高流量商用系統,是會使用預先運算好的資料,而不是用index去幫助即時性的Query的。」「越即時性的資料便越貴,便需要越好的主機。」🗣️ 149 · 補充補充說明
🔭 原書的 aggregated data 就是「預先運算好的資料」,這點和 Triton 一致;不同的是原書一開始就在第 6 階段。
依 Triton 原則推論如果是你家的量
🔭 小流量版:一張 raw 表、一句 GROUP BY、可以重跑
-- raw data:依天 partition,過了保留期整個 truncate
CREATE TABLE ad_click_raw (
click_id uuid, -- client 產生,重送也一樣
ad_id bigint, click_ts timestamptz,
user_id bigint, ip inet, country char(2),
PRIMARY KEY (click_id, click_ts)
) PARTITION BY RANGE (click_ts);
INSERT INTO ad_click_raw VALUES (...)
ON CONFLICT DO NOTHING; -- 重複點擊直接擋掉
-- 每分鐘的 Table 8:整分鐘重算、覆蓋寫入
INSERT INTO ad_click_minute (ad_id, click_minute, country, cnt)
SELECT ad_id, date_trunc('minute', click_ts), country, count(*)
FROM ad_click_raw
WHERE click_ts >= :from AND click_ts < :to
GROUP BY 1, 2, 3
ON CONFLICT (ad_id, click_minute, country)
DO UPDATE SET cnt = EXCLUDED.cnt;
你猜猜看:原書怕重算會重複,所以要 exactly-once。這裡的每分鐘計數是「整分鐘重算、覆蓋寫入」,不小心跑了 10 次,結果會?
每次都從原始紀錄重數、蓋掉舊的,不是 +1。重做幾次都一樣叫 idempotent,所以不需要分散式交易。
原書的難題,在這個量下各變成什麼
| 原書 | 小流量版 |
|---|---|
| 重複事件、exactly-once | click_id 當 PK,ON CONFLICT DO NOTHING |
| 聚合節點當機、snapshot | 聚合是一句 SQL,失敗就整分鐘重跑,結果一樣 |
| 晚到事件、watermark | 每次重算最近 N 分鐘;一小時後再補跑一次也可以 |
| top N、heap、Reduce | ORDER BY cnt DESC LIMIT 100 |
| star schema 的 dimension | GROUP BY 多一欄 |
| 資料重算、Kappa | 同一句 SQL,換 :from :to |
| cold storage | 舊 partition 匯出成 Parquet 丟 S3,再 truncate |
🔭 依 Triton 原則推論 這頁的 SQL 是本簡報寫的,不是 Triton 的原文。依據:<100GB 用 RDBMS(054)、partition + truncate 做保留期(081、065)、報表放 replica 慢慢跑(023、012)、log 是 aggregation 用的(012)。click_id 要 client 端產生,原書的事件欄位沒有這一欄。
Triton 觀點MQ 用在哪、什麼時候才輪到 Kafka
MQ 當緩衝:同意;Kafka:先看每秒幾則
你猜猜看:原書一開始就用兩個 Kafka。如果你家每天 100 萬次點擊,每秒幾則?需要 Kafka 嗎?
100 萬 ÷ 86,400 ≈ 12。Triton:每秒不到 1K 則,Kafka 是 overkill。
✅ 同意原書 把 MQ 當 buffer
「把工作先丟MQ再慢慢處理,一般而且有3個原因:… 2 這工作是慢慢做也死不了人的,我想把MQ當成一個buffer,讓peak hours的工作可以在non-peak hours時來做。(例子:user profiling的分析)」🗣️ Triton 本人說 185-電商用 queue-.md
原書第 14 頁用 MQ 解耦 producer / consumer,避免 consumer out-of-memory,正是這個理由。
🗣️ Kafka 有門檻
「Kafka不是rabbitMQ的evolution結果」「如果系統還沒到每秒1K Message的,kafka對你會是overkill。」「你可以把kafka看成:把RabbitMQ大量功能砍掉,特化scalibility的MQ」🗣️ Triton 本人說 138
🔭 原書平均 10,000、尖峰 50,000 QPS,遠超過 1K,用 Kafka 合理。每天 100 萬次點擊只有每秒 12 則。
🗣️ 但別拿 Redis 當 queue
「redis本身沒法做到high persistence(斷電後redis會有data loss的)」「如果你的consumer消化速度追不上producer生產速度 你的redis很容易就會爆炸掉。rabbitmq / Kafka是使用HDD來存放buffer的。」🗣️ 030-Redis 不能當 queue 原因.md
真正的 MQ「會把收到的Message先存到HDD,然後才回應成功 – 會等待收件者回傳「工作完成」,才真的把訊息刪掉」078
🔭 076 的 Event Receiver「Pack multiple events to one SQS Message to save money」:每秒幾千個點擊,打包成每秒幾十則 message,就回到 1K 以下了。原書沒有談「一則 message 裝幾個事件」。
Triton 觀點Figure 20 的「distributed transaction」
原書的 exactly-once,就是 2PC
「簡單而言,只要你:1 要改動2份資料 2 這2份資料不是放在同一台主機上 3 這2份資料,最終要一起被改動,或是一起沒被改動 … 如果你要同時滿足這3點,你肯定需要2pc的。」🗣️ Triton 本人說 123-喵談 2pc.md
「那麼你的micro-service API design就一定要造出像stripe / paypal這樣子的2pc架構 很容易出錯(如果你說不用2pc的,你可以寫論文了)你用event-sourcing,也是避不了這堆問題的」🗣️ 100-二份data是存放在不同的machine上(2pc).md
「不管Passkit伺服器在什麼時候當掉,Passkit用戶肯定會被收款,也只會收一次。」🗣️ 123 · 逐一分析第 0–4 步之間當機的結果
你猜猜看:Figure 20 的兩份資料(下游的結果、offset)放在不同機器,又必須一起改。Triton 說這時你需要什麼?
三個條件全中,就躲不掉 2PC。下一頁看 Triton 的思路怎麼繞開它。
📅 2026 補充
原書參考資料 [19] 那篇 Flink 文章(2018)講的 end-to-end exactly-once,用的就是 two-phase commit sink 搭配 Kafka transactions。原書沒說出「2PC」這個字,但 Figure 20 的框就是它。
依 Triton 原則推論Figure 20 的兩份資料,能不能放在同一台?
🔭 不想寫 2PC:讓兩份資料住在同一個 DB
🔭 套到原書
Figure 17–20 的兩份資料是「下游的聚合結果」和「offset」,放在不同的機器(下游 Kafka、HDFS / S3),又必須一起成功:三點全中,所以原書最後只能用分散式交易。Triton 會反過來問:能不能讓這兩份資料在同一台機器上?
BEGIN; -- 聚合結果與 offset 在同一個 DB INSERT INTO ad_click_minute ... ON CONFLICT ... ; UPDATE consumer_offset SET pos = 110 WHERE topic_partition = :p AND pos = 100; -- 影響 0 列 = 別人做過了 → ROLLBACK COMMIT;
一台機器上的普通 transaction,加上 WHERE pos = 100 這種 check-and-set,就不需要 2PC。這是推論,Triton 沒有針對這章寫過。
你猜猜看:總表和名單(offset)如果在同一個房間,還需要兩階段的協調者嗎?
同一台機器上的改動,資料庫本來就能「一起成功、一起不算」(第 39 頁)。2PC 是跨機器才需要的。
文組翻譯
把總表和名單搬進同一個房間、交給同一位管理員,就不用協調者了。WHERE pos = 100 是「名單上寫的還是第 100 號,我才改」:別人先改過,這次就整個作廢。
Triton 觀點 · 動手玩對帳:先驗血,再照 MRI
不要每天逐筆重算,先問「加總對得上嗎?」
「正常人不會沒事去做MRI,而是每年做費用低很多的血液檢查,血液檢查報告不正常才進一步X-ray / MRI檢查。很多時候的例行系統健康檢查,不需要即時找出問題點,而且以很低CPU和IO代價報告「現在系統有沒有不對?」」🗣️ Triton 本人說 081-online game system,想知道怎樣來做到有效的對帳功能….md
「這樣子,除非你用的RDBMS有bug/你的application有bug/你自己就是bug,否則系統中的user_balance和banker的加總應該是永遠都是零的。」「但是加總不是零時,這是不同的banker_record,也許能幫助你知道是那一邊的交易有bug。」🗣️ 081
🔭 套到原書 原書說廣告點擊「沒有第三方結果可以對」,所以用 batch 重算整天來對。Triton 的 banker 是自己造一個不變量:每個 partition 的 raw 筆數 = 該 partition 每分鐘計數的加總。先比一個總數(驗血),不對再逐 partition、逐分鐘找(MRI)。
你猜猜看:原書每天把整天的原始紀錄重算一次來對帳。每年健康檢查,一般人先做哪一個?
驗血便宜,只回答「有沒有不對」。對帳也一樣:先比一個總數,對不上再逐 partition 找。
到這裡你已經會了小結 5 / 5
- event
- QPS · GB
- MQ · offset
- MapReduce
- stream · batch
- window
- event time
- watermark
- at-least once
- exactly-once
- 2PC
- reconciliation
- columnar
到這裡你已經會了:驗票、存票、Triton 的三個問題
- 事後拿原始紀錄重算、跟即時結果對(reconciliation)。Triton:先比一個總數,對不上再逐堆找。
- 寫一次、不再改的點擊紀錄,適合一欄一本(columnar)壓縮存放,例如 S3 上的 Parquet。
- 動手之前先問:資料多大、哪些可以錯、誰在等。每天 1 萬次點擊,一張表和一句可以重跑的 SQL 就夠。
13 階全部走完了
下一頁用一句話收尾;再下一頁是名詞小卡,給大家課後複習。
一句話記住
先算清楚有幾張票、哪些票可以錯,
再決定要不要蓋一座計票工廠。
原書對的地方
- raw data 和 aggregated data 都存;raw 當備份、可重算(Triton:log 存 txt / S3,012、076)
- MQ 當 buffer 解耦 producer / consumer(185 的第 2 個理由)
- 聚合結果預先算好,dashboard 只讀它(149 預先運算、035 materialization)
- watermark 只接「稍微」晚到的,剩下交給日終對帳:不為低機率事件過度設計
- 用 crash 點分析 offset 該何時存(同 123 的寫法)
Triton 會先問的地方
- 每天 100GB 是原書的量;<100GB「就乖乖回去用 RDBMS」(054)
- 全部點擊都當計費資料:可以錯的統計不該付 exactly-once 的代價(117、035)
- Kafka:每秒不到 1K message 是 overkill(138)
- Figure 20 的分散式交易就是 2PC,「很容易出錯」(100、123)
- 原書因「很多人不熟」放下的 S3 + Parquet,正是 write-once 資料該走的路(054)
Triton 式的做法
- 先用計算機算 GB/天、RPS、msg/s
- 把資料分級:計費要準、趨勢可抽樣、統計可掉
- 小量:一張 partition 表 + 可重跑的
GROUP BY(🔭) - 大量:Firehose → S3 Parquet、buffer + write aggregation(076)
- offset 和結果放同一個 DB,避開 2PC(🔭)
- 用加總不變量對帳:先驗血、再 MRI(081)
本章名詞小卡課後複習用 · 每個名詞一句白話
今天出現的名詞,一句話講完
給工程師的重點出處與標籤
引述來源(materials/core)與原書對照
Triton 本人的講義 / 文章
- 054-data-analysis.pdf.md — Data Analysis WITHOUT RDBMS:「資料量不夠大 (<100GB) 就乖乖回去用 RDBMS 就好啦」、OLTP vs OLAP、write-once 才適合壓縮、columnar、BigQuery / Athena 的帳單風險、總結 100GB 與 read replica
- 076-mini-bigdata.pdf.md — HYPEBEAST:Event Receiver、Firehose → S3、SQS 兩層 write buffering、hotdata redis、單執行緒 sync worker、write aggregation 的前提與好處、接受掉資料、random 100 取 top N
- 117-喵看Data 的思維.md — Consistency / Durability / Usage、不需要 consistency 別用 RDBMS、100 RPS、buffer 在 AS 再 flush、「沒10K RPS前別做這種事」、流量不夠大別用 noSQL
- 035 / 034 / 033 SQL reporting — 資料庫很少 >100GB、低價值資料別放 RDBMS、sampling(報稅 vs 趨勢)、materialization
- 023 以 end-user 為優先、報表的六個階段 · 012 log 別放 RDBMS、報表在 slave、別為報表建 index · 149 OLTP 的 index 有害、預先運算 · 104 別為報表下 index
- 081 banker 加總為零、驗血 vs MRI · 123 2PC 三條件與 Stripe 逐步當機分析(第 64–65 頁) · 100 不同機器要 strong consistency 就避不了 2PC · 138 <1K msg/s 用 Kafka 是 overkill · 185 MQ 的三個理由 · 078 真正的 MQ 先寫 HDD 才 ack · 030 Redis 不能當 queue · 146「BigData」buzzword · 065 log 用 txt / Kinesis、數據生命週期
作者未標示:085(Parquet + Athena 短串,標 💬)。不引用:014(NotebookLM 摘要)、058(Roy 的 columnar 筆記,本頁未用)、061(Roy 的專案報告)。
循序漸進(文組版)的頁面
學習地圖(第 3 頁);延伸基礎 13 階:第 4、5、13、17、21、26、27、30、35、37、39、48、59 頁;小結(16、25、34、42、67);名詞小卡(69)。開票夜是示範情境,延伸基礎頁的數字是示意。
原書對照
Alex Xu & Sahn Lam, System Design Interview Vol.2 Ch.6。開頭、RTB 與 Figure 1(第 6 頁);Step 1 需求(7);估算(8);Query API 與 Table 1–6(9);Data model 與 Table 7–11(10);Comparison 與 Table 12(11);Choose the right database(12);High-level design、async processing 與 Figure 2–3(14);Table 13–15 與 Figure 4(15);Aggregation service 與 Figure 5–7(18);Use case 1–2 與 Figure 8–9(19);Use case 3、Table 16、star schema(20);Streaming vs batching 與 Table 17(22);Lambda / Kappa 與 Figure 10(23);Data recalculation 與 Figure 11(24);Time、Figure 12、Table 18(28–29);Watermark 與 Figure 13–14(31);Aggregation window 與 Figure 15–16(32–33);Delivery guarantees、dedup 與 Figure 17–20(36–41);Scale MQ 與 Figure 21(43);Scale aggregation 與 Figure 22–23(44);Scale DB 與 Figure 24(45);Hotspot 與 Figure 25(46);Fault tolerance 與 Figure 26–27(47);Monitoring、reconciliation(49);Final design 與 Figure 28(50);Alternative design 與 Figure 29(51);Wrap up 與心智圖(52)。30 張圖與 18 個表都依原書圖說、alt 與內文重繪,不是原圖。
一個可以直接問自己的問題
你的點擊資料,全部加起來有沒有 100GB?如果答案是「一年也才幾十 GB」,你需要的是一張 partition 好的表和一句可以重跑的 GROUP BY,不是兩個 Kafka 和一個分散式交易。