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 補充

先用生活理解選舉開票

開票夜:三個開票所,一張總表

0實際投出的票0中選會總表一致差多少

廣告點擊統計就是一場永遠不會結束的開票:每個伺服器是一個開票所,每一次點擊是一張票,系統每分鐘要公布一次「每則廣告拿了幾票」。

  • 唱票、加總:各開票所先自己數,中選會再合計(原書的 Map → Aggregate → Reduce)
  • 郵寄選票晚到:點擊發生在 10:00:59,卻 10:01:10 才送到(event time vs processing time、watermark)
  • 重複唱票:開票所斷線、不確定剛剛有沒有送到,只好再送一次(delivery guarantee、exactly-once)
  • 事後驗票:隔天用原始選票重數一次,對總表(reconciliation)

選票數錯,結果可能翻盤;廣告點擊數錯,廣告主就多付或少付錢。原書說:差幾個百分點就可能是幾百萬美元。

學習地圖本章的概念階梯

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

  1. 1event一張選票
  2. 2QPS · GB票來多快、多重
  3. 3MQ · offset收件櫃台和流水號
  4. 4MapReduce分頭唱票再合計
  5. 5stream · batch流水線 vs 月底結帳
  6. 6window每幾分鐘結一次
  7. 7event time看郵戳還是收件日
  8. 8watermark截止後的寬限期
  9. 9at-least once沒回條就重送
  10. 10exactly-once重送也只算一次
  11. 112PC兩本簿子一起改
  12. 12reconcil­iation事後驗票
  13. 13columnar一欄一本冊子

第 1–3 階 · 票從哪來

要回答:每一次點擊,怎麼送到數票的地方?

第 4–5 階 · 怎麼數

要回答:每秒 5 萬張票,怎麼分頭數、什麼時候數?

第 6–8 階 · 時間

要回答:這張票算哪一分鐘?晚到的怎麼辦?

第 9–11 階 · 不多不少

要回答:斷線重送,怎麼不重複也不漏?

第 12–13 階 · 驗票與存票

要回答:怎麼便宜地驗票?Triton 怎麼存?

全程只用一場開票夜

一次點擊 = 一張選票(event)每台 server = 開票所聚合服務 = 中選會收件櫃台 = MQ計票表 = aggregated data事後驗票 = reconciliation

每爬 2–3 階,有一頁「到這裡你已經會了」。

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

  1. event
  2. QPS · GB
  3. MQ · offset
  4. MapReduce
  5. stream · batch
  6. window
  7. event time
  8. watermark
  9. at-least once
  10. exactly-once
  11. 2PC
  12. reconciliation
  13. columnar

每次點擊留下一張小紙條;門口貼的是計票表

① 先想像

有人點了廣告,伺服器就寫下一行小紙條:哪則廣告、幾點幾分、誰、哪個國家。這就是一張選票。

你猜猜看:門口的計票表只寫「ad001:這一分鐘 5 次」。能看出 5 次裡有幾次來自美國嗎?

③ 這叫做 event、aggregation

event:一次點擊留下的一行紀錄(log)。aggregation:把很多行數成一個數字,中文叫「聚合」。

④ 跟這章的關係

原始紙條叫 raw data,計票表叫 aggregated data。原書兩種都存(第 11 頁)。

② 動手玩:點廣告,看紙條和計票表


      
0原始紙條(raw data)幾行0計票表(aggregated)幾列

延伸基礎 · 複習第 2 階 · QPS、GB02 章講過,懂的人可以跳過

  1. event
  2. QPS · GB
  3. MQ · offset
  4. MapReduce
  5. stream · batch
  6. window
  7. event time
  8. watermark
  9. at-least once
  10. exactly-once
  11. 2PC
  12. reconciliation
  13. columnar

一天 10 億張票:每秒幾張?一天多重?

① 先想像

一天有 86,400 秒,心算時當成 10 萬秒。一天的票數除以 10 萬,就是平均每秒幾張。

你猜猜看:一天 10 億次點擊,平均每秒大約幾次?

④ 跟這章的關係

原書每天 100 GB(第 8 頁)。Triton 的分界線是「全部 < 100GB 就用一般的資料庫」(第 54 頁)。

② 動手玩:三種規模,每筆紀錄 100 B

10 億每天點擊10,000平均每秒50,000尖峰每秒(×5)100 GB每天多重

原書線上廣告的背景 · Figure 1

廣告是怎麼被買賣的:Real-Time Bidding

這一步要解決的問題廣告是怎麼賣出去的?為什麼「點了幾次」就是錢?

📖 原書 Figure 1RTB process:demand side 與 supply side 在 Ad Exchange 撮合(依原書內容重繪)
整個過程通常不到一秒

📖 原書 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 等級」到底是每秒幾張票、一天多重?

📖 原書 估算

DAU10 億
每人每天平均點 1 則廣告每天 10 億次點擊
平均 QPS109 ÷ 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%

10 億每天點擊50,000Peak QPS100 GB每天新增

原書在 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
countTop Ninteger
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_idclick_timestampuseripcountry
ad0012021-01-01 00:00:01user1207.148.22.22USA
ad0012021-01-01 00:00:02user1207.148.22.22USA
ad0022021-01-01 00:00:02user2209.153.56.11USA

Table 7Raw data

📖 原書 Aggregated data(每分鐘聚合一次)

ad_idclick_minutecount
ad0012021010100005
ad0012021010100017

Table 8Aggregated data

ad_idclick_minutefilter_idcount
ad00120210101000000122
ad00120210101000000233
ad00120210101000100121
ad00120210101000100236

Table 9加上 filter_id

Table 10 Filter table

filter_idregionIPuser_id
0012US**
0013*123.1.2.3*

同一個 ad_id + click_minute 的紀錄,再依 filter_id 分組。

Table 11 most_clicked_ads(支援 top N)

window_sizeinteger聚合視窗大小 M(分鐘)
update_time_minutetimestamp最後更新時間(1 分鐘粒度)
most_clicked_adsarrayJSON 格式的 ad ID 清單

文組翻譯

Raw data 是每一張選票,aggregated data 是開票所門口貼的那張「每分鐘計票表」。filter 就是同一張表再拆成「北部票」「南部票」各一欄。

原書 Step 2Comparison · Table 12

存原始資料,還是只存聚合結果?原書:兩個都存

這一步要解決的問題只存計票表最省空間,可是之後還回得去嗎?

Raw data onlyAggregated 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 萬張票,要寫進哪一種資料庫?

📖 原書 四個要問的問題

  1. 資料長什麼樣子?relational?document?blob?
  2. 工作負載是 read-heavy、write-heavy,還是兩者都是?
  3. 需要 transaction 嗎?
  4. 查詢是否大量依賴 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懂的人可以跳過

  1. event
  2. QPS · GB
  3. MQ · offset
  4. MapReduce
  5. stream · batch
  6. window
  7. event time
  8. watermark
  9. at-least once
  10. exactly-once
  11. 2PC
  12. reconciliation
  13. columnar

開票所把結果丟進收件櫃台,就能回去繼續數

① 先想像

中選會門口有個收件櫃台。開票所把結果單丟進去就走,不用等中選會有空。櫃台在每張單上蓋流水號。

你猜猜看:中選會的小陳處理到第 7 號時昏倒,換小林接手。小林該從第幾號開始?

③ 這叫做 message queue、offset

message queue(MQ):收件櫃台,先收下、之後再處理;Kafka 是一種。offset:流水號,「處理到第幾號」。

④ 跟這章的關係

原書在流程裡放了兩個 MQ(下一頁)。offset 什麼時候記,決定票會不會重複或漏掉(第 38 頁)。

② 動手玩:收件櫃台

0櫃台裡還沒處理#0記事本:處理到第幾號(offset)

原書 Step 2High-level design · Figure 2–3

從同步的一條線,到用兩個 message queue 拆開

這一步要解決的問題開票所和中選會的速度不一樣,怎麼不互相拖累?

📖 原書 Figure 2Aggregation workflow:Input → Process → Output → Display(依原書內容重繪)

📖 原書 即時大數據處理裡,資料是 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_idclick_timestampuser_idipcountry

第二個 MQ:兩種資料

每分鐘粒度的點擊數

ad_idclick_minutecount

Table 14

每分鐘粒度的 top N

update_time_minutemost_clicked_ads

Table 15

📖 原書「你可能會想問為什麼不把聚合結果直接寫進資料庫。簡短的答案是:我們需要像 Kafka 這樣的第二個 MQ,才能做到端到端的 exactly-once 語意(atomic commit)。」

📖 原書 Figure 4End-to-end exactly once:虛線框內視為一次 atomic commit(依原書內容重繪)

原書在這裡只給結論,細節(offset 存哪、什麼時候存、分散式交易)在 Step 3 的 Delivery guarantees,第 36–41 頁。

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

  1. event
  2. QPS · GB
  3. MQ · offset
  4. MapReduce
  5. stream · batch
  6. window
  7. event time
  8. watermark
  9. at-least once
  10. exactly-once
  11. 2PC
  12. reconciliation
  13. columnar

到這裡你已經會了:票從哪來、送到哪

下一階要解決的問題

每秒 5 萬張票,一個中選會數不完。怎麼分頭數、再合起來?

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

  1. event
  2. QPS · GB
  3. MQ · offset
  4. MapReduce
  5. stream · batch
  6. window
  7. event time
  8. watermark
  9. at-least once
  10. exactly-once
  11. 2PC
  12. reconciliation
  13. columnar

票太多一個人數不完:分堆、各自數、再合計

① 先想像

一個人數 9,000 張票要 90 分鐘。找三個人:先照候選人號碼分三堆,各數各的,最後把三個數字抄到總表。

你猜猜看:分給 3 個人各數 3,000 張,大約要多久?

③ 這叫做 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 萬張票,怎麼分給好幾台機器一起數?

📖 原書 Figure 5Aggregation service:上 = 每分鐘計數,下 = Top 100(依原書內容重繪)

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 名

這一步要解決的問題照這個流程,怎麼回答「幾次」和「前幾名」?

📖 原書 Figure 8Aggregate the number of clicks:依 ad_id % 3 分區後計數(依原書內容重繪)

📖 原書 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_idclick_minutecountrycount
ad001202101010001USA100
ad001202101010001GPB200
ad001202101010001others3000
ad002202101010001USA10
ad002202101010001GPB25
ad002202101010001others12

Table 16Aggregation results(filter by country;「GPB」照原書寫法)

這叫 star schema

data warehouse 常用的技巧,過濾欄位叫 dimension。優點:①簡單好懂好做;②現有的聚合服務可以重複使用來建更多 dimension,不需要額外元件;③結果是預先算好的,依條件查很快。限制:會產生多很多 bucket 和紀錄,尤其過濾條件很多時。

動手算:dimension 一多,紀錄會爆多少

6M每分鐘最多幾列8.6B一天最多幾列

🔭 示意 這是上限(每則廣告每分鐘每個組合都有點擊才會到);實際上沒點擊的組合不會產生紀錄。

延伸基礎第 5 階 · stream、batch懂的人可以跳過

  1. event
  2. QPS · GB
  3. MQ · offset
  4. MapReduce
  5. stream · batch
  6. window
  7. event time
  8. watermark
  9. at-least once
  10. exactly-once
  11. 2PC
  12. reconciliation
  13. columnar

流水線,還是月底結帳?

① 先想像

便當店有兩種算帳法。每賣一個就更新「今天賣了幾個」,像流水線;或收據全丟進抽屜,月底結帳時一次算。

你猜猜看:哪一種比較快知道結果?哪一種比較容易整批重算?

③ 這叫做 stream、batch processing

stream processing:資料一到就處理(流水線)。batch processing:攢一批、定時一次處理(月底結帳)。

④ 跟這章的關係

開票夜的即時看板是流水線,選後封箱重點是月底結帳。原書兩種都用(第 22–24 頁)。

② 動手玩:每分鐘來 10 張票

幾秒看板最多落後1 張每次處理幾張

原書 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回應給 clientMaterialized view、聚合指標等Materialized view、聚合指標等
Performance measurementAvailability、latencyThroughputThroughput、latency
ExampleOnline shoppingMapReduceFlink

📖 原書 Table 17Comparison of three types of systems(出自 DDIA)

白話:throughput=一段時間處理多少;latency=一件事要等多久;availability=隨時都開著;materialized view=事先算好、存起來的結果。

📖 原書 Step 3 要深入的題目

  1. Streaming vs batching
  2. Time 與 aggregation window
  3. Delivery guarantees
  4. Scale the system
  5. Data monitoring 與 correctness
  6. Final design diagram
  7. Fault tolerance

📖 原書 這個設計兩種都用

Figure 3 是 stream processing:資料一到就處理,近即時地產生聚合結果。Batch processing 則用在歷史資料備份。

文組翻譯:online 是櫃台結帳,客人在等;batch 是月底關帳,一次算一大疊;streaming 是開票夜的即時看板,票一直來、看板一直更新。

原書 Step 3Lambda vs Kappa · Figure 10

兩條路還是一條路:lambda 與 kappa

這一步要解決的問題流水線和月底結帳,要寫兩套程式,還是一套?

📖 原書 Figure 10(上)Lambda architecture:batch layer + streaming layer(依原書內容重繪)

📖 原書 Lambda

同時有 batch 和 streaming 兩條處理路徑。缺點:兩條路就是兩套 codebase 要維護。

📖 原書 Kappa

把 batch 和 streaming 合成一條處理路徑:用同一個 stream processing engine 同時處理即時資料和持續的資料重處理。

📖 原書 本章用 Kappa

歷史資料的重處理,也走即時的聚合服務(見下一頁 Data recalculation)。

文組翻譯:Lambda 是「開票夜一組人即時唱票、另一組人隔天慢慢點全部選票」,兩組規則要一模一樣,否則對不上。Kappa 是「只有一組人,要重數就把選票再唱一次」。

原書 Step 3Data recalculation · Figure 11

發現 bug 之後:從原始資料重算一次

這一步要解決的問題發現算錯了,怎麼重算,又不影響即時看板?

📖 原書 Figure 11Recalculation service(依原書內容重繪;alt 說重算結果送進 Database Writer,內文說送進第二個 MQ,依內文)

📖 原書 有時候必須重算聚合資料,又叫 historical data replay。例如發現聚合服務有重大 bug,要從 bug 引入的時間點開始,用 raw data 重算。

  1. Recalculation service 從 raw data storage 取資料,這是 batched job
  2. 取出的資料送到專用的聚合服務,讓即時處理不受歷史重播影響
  3. 聚合結果送到第二個 MQ,再更新到 aggregation database

重算流程重用資料聚合服務的程式,只是資料來源不同(raw data)。這就是上一頁說的 Kappa:重算也走同一套聚合邏輯。

文組翻譯:發現某個開票所的計票機有 bug,就把那段時間的原始選票封箱拿出來,交給另一組工作人員用同一套規則重數,數完更新總表;即時開票照常進行。

到這裡你已經會了小結 2 / 5

  1. event
  2. QPS · GB
  3. MQ · offset
  4. MapReduce
  5. stream · batch
  6. window
  7. event time
  8. watermark
  9. at-least once
  10. exactly-once
  11. 2PC
  12. reconciliation
  13. columnar

到這裡你已經會了:怎麼數

下一階要解決的問題

看板「每分鐘公布一次」,那一分鐘怎麼切?晚到的票又算哪一分鐘?

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

  1. event
  2. QPS · GB
  3. MQ · offset
  4. MapReduce
  5. stream · batch
  6. window
  7. event time
  8. watermark
  9. at-least once
  10. exactly-once
  11. 2PC
  12. reconciliation
  13. columnar

看板「每分鐘公布一次」:這一分鐘從哪裡切?

① 先想像

看板 A 每分鐘公布「這一分鐘幾票」,一格接一格、不重疊。看板 B 每分鐘更新一次「最近 3 分鐘」的人氣排行。

你猜猜看:一張 01:30 投的票,在看板 B 會被算進幾次?

③ 這叫做 tumbling、sliding window

tumbling window:等長、不重疊的格子,一張票只進一格。sliding window:會重疊、往前滑的框,一張票可能進好幾個框。

④ 跟這章的關係

原書:每分鐘點擊數用 tumbling;「最近 M 分鐘的前 N 名」用 sliding(第 32 頁)。

② 動手玩:6 分鐘、12 張票

0框裡有幾張票101:30 那張被算進幾個框

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

  1. event
  2. QPS · GB
  3. MQ · offset
  4. MapReduce
  5. stream · batch
  6. window
  7. event time
  8. watermark
  9. at-least once
  10. exactly-once
  11. 2PC
  12. reconciliation
  13. 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 小時才到聚合服務。

📖 原書 Figure 12Late events(依原書內容重繪;alt 對 event 1 的描述前後矛盾,依內文「event 1 晚 5 小時才到」)
ProsCons
Event time聚合較準確:client 確切知道廣告何時被點依賴 client 產生的 timestamp:client 時間可能錯,或被惡意使用者偽造
Processing timeserver 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懂的人可以跳過

  1. event
  2. QPS · GB
  3. MQ · offset
  4. MapReduce
  5. stream · batch
  6. window
  7. event time
  8. watermark
  9. at-least once
  10. exactly-once
  11. 2PC
  12. reconciliation
  13. columnar

18:00 截止,再多等 15 分鐘:寬限期

① 先想像

規定是「郵戳 18:00 前的票,18:15 前送到都算」。18:15 一到,這一格就關門、公布。

你猜猜看:寬限期從 15 分鐘拉長成 2 小時,會怎樣?

③ 這叫做 watermark

watermark:視窗關門前多等的寬限期。寬限期過了才到的,叫遲到事件(late event)。

④ 跟這章的關係

原書多等 15 秒(下一頁)。少數接不住的,交給事後驗票。

② 動手玩:10 張票,各晚到幾秒

0 / 10接住0 秒每格晚多久公布10接不住,交給驗票

原書 Step 3Watermark · Figure 13–14

視窗關門前多等 15 秒:watermark

這一步要解決的問題稍微晚到的點擊,怎麼不漏掉?

📖 原書 Figure 13Miss events in an aggregation window:window 1 漏了 event 2、window 3 漏了 event 5(依原書內容重繪)

📖 原書 點擊在一分鐘的 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 分鐘」,各用哪一種框?

📖 原書 Figure 15Tumbling window(1 minute window)(依原書內容重繪)
📖 原書 Figure 16Sliding window(3 minute window, run every minute)(依原書內容重繪)

📖 原書 依 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 拉長:接住更多晚到的票,但更晚公布

這一步要解決的問題寬限期拉長或縮短,取捨在哪裡?

0算進正確視窗0錯過(要靠對帳補)0 秒每個視窗多等多久才公布

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

  1. event
  2. QPS · GB
  3. MQ · offset
  4. MapReduce
  5. stream · batch
  6. window
  7. event time
  8. watermark
  9. at-least once
  10. exactly-once
  11. 2PC
  12. reconciliation
  13. columnar

到這裡你已經會了:時間

下一階要解決的問題

開票所斷線,不確定剛剛送到了沒有。再送一次可能重複,不送可能漏掉。怎麼辦?

延伸基礎第 9 階 · at-least once懂的人可以跳過

  1. event
  2. QPS · GB
  3. MQ · offset
  4. MapReduce
  5. stream · batch
  6. window
  7. event time
  8. watermark
  9. at-least once
  10. exactly-once
  11. 2PC
  12. reconciliation
  13. columnar

回條沒回來:再送一次,還是算了?

① 先想像

開票所送出結果,等中選會回一張「收到了」的回條。回條沒來:可能結果沒到,也可能回條在路上掉了。

你猜猜看:開票所想保證「一張都不漏」,沒收到回條時該怎麼做?

③ 這叫做 ack、at-least once

ack:收到的回條。at-least once:沒回條就重送,不會漏、可能重複;不重送的叫 at-most once。

④ 跟這章的關係

Kafka 這類 MQ 提供三種送法(下一頁)。重複了怎麼辦,下一階。

② 動手玩:送 10 批結果

0漏掉的批0多收到的份數

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

  1. event
  2. QPS · GB
  3. MQ · offset
  4. MapReduce
  5. stream · batch
  6. window
  7. event time
  8. watermark
  9. at-least once
  10. exactly-once
  11. 2PC
  12. reconciliation
  13. columnar

每份結果單印上編號:收過的就丟掉

① 先想像

每份結果單印上「B 開票所 · 第 3 批」。中選會先查名單:記過了就丟掉;沒記過,才加進總表、再記上名單。

你猜猜看:「B · 第 3 批」被重送了 3 次,中選會有查名單。總表加了幾次?

③ 這叫做 dedup、exactly-once

dedup:認出重複、丟掉。exactly-once:重送也只算一次,做法是 at-least once 加上 dedup。

④ 跟這章的關係

原書的「編號」就是 offset。Figure 17–19 都在找它該什麼時候記(下一頁)。

② 動手玩:結果單送到中選會

0總表0應該是(空)名單

原書 Step 3Data deduplication · Figure 17–18

offset 該什麼時候存?兩個都會出事的版本

這一步要解決的問題編號(offset)什麼時候記,才不會重複也不漏?

📖 原書 Figure 17Duplicate data:步驟 6 失敗(依原書內容重繪;alt 中被截斷的 Upstream… / Downstream… 依內文補成 Kafka)

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

  1. event
  2. QPS · GB
  3. MQ · offset
  4. MapReduce
  5. stream · batch
  6. window
  7. event time
  8. watermark
  9. at-least once
  10. exactly-once
  11. 2PC
  12. reconciliation
  13. columnar

總表和名單在兩個房間:怎麼保證一起改?

① 先想像

總表在 A 房間、名單在 B 房間,各有一位管理員。兩邊都要改,改到一半停電,就會一邊有、一邊沒有。

你猜猜看:A 已經把第 3 批加進總表,B 還沒記上名單就停電。來電後第 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 19Save offset after receiving ack(依原書內容重繪)

📖 原書 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

  1. event
  2. QPS · GB
  3. MQ · offset
  4. MapReduce
  5. stream · batch
  6. window
  7. event time
  8. watermark
  9. at-least once
  10. exactly-once
  11. 2PC
  12. reconciliation
  13. columnar

到這裡你已經會了:不多不少

下一階要解決的問題

原書接著講:點擊每 3 年翻倍,收件櫃台、數票的人、資料庫怎麼加?最後怎麼驗票?

原書 Step 3Scale the system · message queue · Figure 21

每 3 年翻倍:先 scale message queue

這一步要解決的問題點擊每 3 年翻倍,收件櫃台怎麼跟著變大?

📖 原書 Figure 21Add consumers:rebalance 之後每個 consumer 只處理一個 partition(依原書內容重繪)

📖 原書 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

這一步要解決的問題數票的機器,怎麼數得更快?

📖 原書 Figure 22Aggregation service:三個 Kafka → 三台 aggregation server 的 map → shuffle → reduce(依原書內容重繪)

📖 原書 高階設計裡,聚合服務是 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

這一步要解決的問題資料庫加機器時,怎麼不用手動搬家?

📖 原書 Figure 24(上)Ring without virtual nodes(依原書內容重繪;原圖引自 Cassandra 文件)

📖 原書 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

大廣告主的廣告特別熱:多派幾個節點分著數

這一步要解決的問題某則廣告特別熱,那一堆特別厚,怎麼辦?

📖 原書 Figure 25Allocate more aggregation nodes(依原書內容重繪)

📖 原書 收到的資料比別人多很多的 shard 或服務叫 hotspot。大公司的廣告預算是幾百萬美元,廣告被點得特別多;事件依 ad_id 分區,某些聚合節點就會收到多很多事件,可能過載。

解法:多分配幾個聚合節點處理熱門廣告。假設每個節點只能處理 100 個事件:

  1. 聚合節點裡有 300 個事件,超過容量,透過 resource manager 申請額外資源
  2. resource manager 多分配兩個聚合節點
  3. 原節點把事件切成 3 組,每個節點處理 100 個
  4. 結果寫回原本的聚合節點

更進階的做法:Global-Local Aggregation、Split Distinct Aggregation(見 Flink 效能調校文件 [23])。

文組翻譯:熱門候選人那一箱特別厚,就臨時找兩個人來分三疊一起數,數完交回給原本的唱票員合計。

原書 Step 3Fault tolerance · Figure 26–27

聚合在記憶體裡,節點掛了怎麼辦:snapshot

這一步要解決的問題數到一半的機器當機,記憶體裡的數字怎麼救回來?

📖 原書 Figure 26Data in a snapshot:過去 5 分鐘 top 3 與每分鐘的明細(依原書內容重繪;alt 只給出 ad1 的每分鐘數字)

📖 原書 聚合在記憶體裡進行,節點掛掉時聚合結果也跟著不見。可以從上游 Kafka broker replay 事件重建計數。

  • 從 Kafka 最開頭 replay 很慢。好做法:把「系統狀態」(例如上游 offset)存成 snapshot,從最後一次的狀態恢復
  • 本設計的「系統狀態」不只 offset,還要存「過去 M 分鐘的 top N」這類資料(Figure 26)
  • 有了 snapshot,failover 很簡單:節點掛了,起一個新節點,從最新的 snapshot 恢復(Figure 27)
  • snapshot 之後才到的新事件,新節點再從 Kafka broker 拉來 replay

文組翻譯:唱票員每數一段,就在小本子上記「數到第幾張、目前各候選人幾票」。他昏倒了,接手的人翻開小本子從那一頁接著數,不用從第一張重來。

延伸基礎第 12 階 · reconciliation懂的人可以跳過

  1. event
  2. QPS · GB
  3. MQ · offset
  4. MapReduce
  5. stream · batch
  6. window
  7. event time
  8. watermark
  9. at-least once
  10. exactly-once
  11. 2PC
  12. reconciliation
  13. 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

最終設計:即時路徑、重算路徑、對帳

這一步要解決的問題把前面的零件全部接起來,是什麼樣子?

📖 原書 Figure 28Final design(依原書內容重繪;alt 的接線描述和內文不一致,這裡依內文:即時路徑同 Figure 3、重算路徑同 Figure 11,Reconciliation 比對 raw data 與 aggregation database)

原書 Step 3Alternative design · Figure 29

另一種做法:Hive、ElasticSearch、ClickHouse

這一步要解決的問題一定要自己組管線嗎?有沒有現成的?

📖 原書 Figure 29Alternative design(依原書內容重繪)

📖 原書 通才型的系統設計面試,不期待你懂大數據管線裡各種專門軟體的內部。重點是說明思考過程、討論取捨,所以原書提出的是通用解法。

  • 另一個選項:點擊資料存在 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

原書的收尾:七個重點,一張心智圖

這一步要解決的問題原書最後要你記住哪些重點?

📖 原書 Chapter Summary本章心智圖(依原書內容重繪)

📖 原書 本章涵蓋

  1. Data model 與 API design
  2. 用 MapReduce 典範聚合點擊事件
  3. Scale message queue、aggregation service、database
  4. 緩解 hotspot
  5. 持續監控系統
  6. 用 reconciliation 確保正確性
  7. Fault tolerance

點擊彙總是典型的大數據處理系統。如果熟悉 Apache Kafka、Apache Flink、Apache Spark 這類業界標準方案,會更容易理解和設計。

原書到這裡結束。下一頁開始是 Triton 的觀點。

Triton 觀點先問三個問題

動手畫 Kafka 之前:多大、能不能錯、誰在等

你猜猜看:原書的設計是為「每天 10 億次點擊」準備的。如果你家每天只有 1 萬次,照抄會怎樣?

① 資料到底多大?

「資料量不夠大 (<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每天新增3 TB保留期總量11,574平均每秒57,870尖峰每秒(×5,原書假設)

你猜猜看:原書「每天 100 GB」,Triton「< 100GB 用 RDBMS」。兩個 100 GB 一樣嗎?

「對一般中小型公司……資料庫很少> 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%,會怎樣?

「不需要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 當緩衝、寫入先聚合

🗣️ Triton 076High level system design(依 076 投影片的文字重繪,不是原書的圖)

你猜猜看:原書為了不掉資料,加了 snapshot 和分散式交易。Triton 在 HYPEBEAST 做 user profiling,redis 當機掉了一點資料,要緊嗎?

背景: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 watcherKafka(第一個 MQ)raw data → Cassandraaggregation service(記憶體)database writerexactly-once
076Event ReceiverSQSFirehose → S3Event Processor + Hotdata redisHotdata sync worker(單執行緒)接受 redis 當機掉資料

🔭 對照表是本簡報整理的。

文組翻譯:開票所把結果先裝箱(Event Receiver 打包),一份副本封存(S3),一份交給櫃台(SQS)。中選會的白板(redis)被擦掉一角也沒關係,封存的那份還在。

Triton 的實戰 · 動手玩Write aggregation

「Database Write is indepentent of traffic」

1,000不聚合:每秒寫 DB30先聚合:每秒寫 DB10,000當機最多掉幾筆事件

你猜猜看:先在記憶體加總、每 10 秒寫一次 DB。每秒事件從 1,000 漲到 50,000,DB 寫入次數會?

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

  1. event
  2. QPS · GB
  3. MQ · offset
  4. MapReduce
  5. stream · batch
  6. window
  7. event time
  8. watermark
  9. at-least once
  10. exactly-once
  11. 2PC
  12. reconciliation
  13. columnar

一頁抄一張票,還是一個欄位一本冊子?

① 先想像

選票資料要抄成冊子。抄法一:一頁抄一張票的全部欄位。抄法二:每個欄位各一本,「廣告」一本、「時間」一本、「國家」一本。

你猜猜看:每張票 5 個欄位,只想數「每則廣告幾次」。抄法二要翻的量,大約是抄法一的幾分之幾?

③ 這叫做 columnar、Parquet

columnar:同一欄的資料存在一起。Parquet:一種 columnar 檔案格式,常放在 S3(雲端的檔案倉庫)。

④ 跟這章的關係

原書提過 S3 + Parquet,因為「很多人不熟」改用 Cassandra(第 12 頁)。Triton 怎麼看,下一頁。

② 動手玩:6 張票 × 5 個欄位

要用的欄位:
30 / 30要讀幾格

Triton 觀點原書放棄的那條路:S3 + columnar

寫一次、不改動的資料,就該用 columnar 檔案

你猜猜看:原書把 raw data 放 Cassandra 這種隨時可改的資料庫。可是點擊紀錄寫進去之後,還會再改嗎?

「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。會怎樣?

🗣️ 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 次,結果會?

原書的難題,在這個量下各變成什麼

原書小流量版
重複事件、exactly-onceclick_id 當 PK,ON CONFLICT DO NOTHING
聚合節點當機、snapshot聚合是一句 SQL,失敗就整分鐘重跑,結果一樣
晚到事件、watermark每次重算最近 N 分鐘;一小時後再補跑一次也可以
top N、heap、ReduceORDER BY cnt DESC LIMIT 100
star schema 的 dimensionGROUP 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 嗎?

✅ 同意原書 把 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 說這時你需要什麼?

📅 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)如果在同一個房間,還需要兩階段的協調者嗎?

文組翻譯

把總表和名單搬進同一個房間、交給同一位管理員,就不用協調者了。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)。

你猜猜看:原書每天把整天的原始紀錄重算一次來對帳。每年健康檢查,一般人先做哪一個?

到這裡你已經會了小結 5 / 5

  1. event
  2. QPS · GB
  3. MQ · offset
  4. MapReduce
  5. stream · batch
  6. window
  7. event time
  8. watermark
  9. at-least once
  10. exactly-once
  11. 2PC
  12. reconciliation
  13. columnar

到這裡你已經會了:驗票、存票、Triton 的三個問題

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)

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

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

event一次點擊留下的一行紀錄(一張選票)
log只往後寫、不回頭改的流水帳
aggregation把很多行數成一個數字(聚合)
raw / aggregated data原始紙條/計票表
QPS每秒幾次;看最忙那一秒
DAU每天有幾個人用
GB、TB資料多重;1 TB = 1,000 GB
RTB廣告即時競價,通常不到一秒
message queue(MQ)收件櫃台:先收下、之後再處理
Kafka一種專為大量訊息設計的 MQ
offset流水號:處理到第幾號
producer / consumer丟單子的一方/拿去處理的一方
cold storage便宜但拿得慢的倉庫,放少用的舊資料

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

引述來源(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 和一個分散式交易。

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