System Design Interview · 第 6 章Triton 覆蓋度:🟢 高Triton 線

Design A Key-value Store
三本訂位簿,要怎麼對得上

原書照 Dynamo、Cassandra 的路線,設計一個永遠接單、資料晚一點再對齊的分散式 key-value store(AP + eventual consistency)。Triton 把同一套架構拆開來看之後說:這種 store 做不了 atomic check-and-set,「單用 Cassandra 是寫不出售票系統的」。

給文組

全程只用「連鎖餐廳的三本訂位簿」,一階一階爬 13 個概念。頁首標 延伸基礎 的頁是補基礎,懂的人可以跳過。

給工程師

先完整講原書(21 張圖全部重繪),再講 Triton 的批判;最後一頁列出所有出處(materials/core)和原書段落對照。

標籤怎麼看

📖 原書 🗣️ Triton 本人說 📝 上課筆記 🔭 依 Triton 原則推論 📅 2026 補充

先用生活理解吃飯定理

便宜、好吃、不用排隊:只能挑兩個

「吃飯定理:便宜,好吃,不用排隊。正常的餐廳最多只能滿足二項。同時滿足三項者,最終一定虧本倒閉。」🗣️ Triton 本人說 086-redis-2018.pdf.md · 前言(下一頁就是 CAP 定理);087 前言同一段

點三個看看

這一章的比喻:連鎖餐廳的三本訂位簿

  • 三家分店各有一本一模一樣的訂位簿:這就是資料的三份 replica
  • 平常分店之間打電話互相抄寫,三本隨時一樣
  • 有一天分店之間的電話線斷了(network partition),客人打來要訂 7 點的 13 號桌:
    • A. 「線路修好前先不接訂位」:資料不會錯,但客人訂不到(CP)
    • B. 「先收了再說」:客人都訂得到,但兩家分店可能把同一張桌子賣給兩個人(AP)

🔭 推論 Triton 在 086 把吃飯定理放在 CAP 定理的前一頁當開場,087 則用它引出「Persistence 和 Low latency 只能要一個」。把三項一一對到 C、A、P 是本簡報的比喻,不是 Triton 的原話。

學習地圖本章的概念階梯

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

  1. 1key-value桌號 → 誰訂的
  2. 2replication三本一樣的簿子
  3. 3CAP電話線斷了,二選一
  4. 4hash ring哪家分店管哪些桌
  5. 5quorum幾家回電才算數
  6. 6eventual consistency晚一點才一樣
  7. 7vector clock誰改過幾次的貼紙
  8. 8gossip分店互傳紙條
  9. 9hinted handoff隔壁分店代收
  10. 10Merkle tree對帳先比總數
  11. 11SSTable白板滿了就歸檔
  12. 12bloom filter「一定沒有」的小抄
  13. 13atomic CAS看+寫一口氣做完

第 1–3 階 · 一本變三本

要回答:電話線斷了,分店該怎麼辦?

第 4–6 階 · 分給很多家

要回答:幾家說好才算訂到?

第 7–9 階 · 吵架與倒店

要回答:兩本對不上、分店倒了怎麼辦?

第 10–12 階 · 修復與存放

要回答:怎麼對帳、怎麼寫進硬碟?

第 13 階 · Triton 的問題

要回答:這台機器能拿來賣票嗎?

全程只用一個例子:連鎖餐廳的三本訂位簿(虛構)

整本訂位簿 = key-value store一行「13 號桌 → 王先生」 = key → value分店 = node / server抄本 = replica電話線斷了 = partition接電話的店員 = coordinator

三家分店:台北、台中、彰化(加開時還有高雄)。每爬 3 階,有一頁「到這裡你已經會了」。

延伸基礎第 1 階 · key-value懂的人可以跳過

  1. key-value
  2. replication
  3. CAP
  4. hash ring
  5. quorum
  6. eventual consistency
  7. vector clock
  8. gossip
  9. hinted handoff
  10. Merkle tree
  11. SSTable
  12. bloom filter
  13. atomic CAS

訂位簿每一行只有兩欄:桌號、誰訂的

① 先想像

分店的訂位簿,每一行只寫「13 號桌」和「王先生」。查的時候報桌號,就知道是誰訂的。

你猜猜看:簿子有 1,000 行,每個桌號都有固定的那一頁。查「13 號桌」要看幾行?

③ 這叫做 key-value、hash table

key-value:一個名字(key)對一份內容(value)。hash table:用 key 直接算出放在哪一格的表,一查就到。

④ 跟這章的關係

原書要做的,就是一本放在很多台電腦上的超大訂位簿。動作只有兩個:put 和 get。

② 動手玩:寫一行、查一行


    

原書什麼是 key-value store · 設計範圍 · 單機版

一張只有兩欄的表:key 和 value

這一步要解決的問題要做的東西到底是什麼?要多大、多快、多可靠?

📖 原書 Key-value store(又叫 key-value database)是一種非關聯式資料庫。每個唯一的 key 對應一個 value。

  • Key 必須唯一;可以是純文字 last_logged_in_at,或雜湊值 253DDEC4。為了效能,key 越短越好
  • Value 可以是字串、list、物件;store 通常把 value 當成不透明的一團資料。例子:Amazon Dynamo、Memcached、Redis

📖 原書 Table 1

keyvalue
145john
147bob
160julia

只要兩個 API

put(key, value)
get(key)

插入 key 對應的 value;取得 key 對應的 value

📖 原書 設計範圍

「沒有完美的設計」:每種設計都在讀、寫、記憶體之間取捨,另一個取捨是 consistency 和 availability。本章要做的 store:

  1. 每筆 key-value 很小:< 10 KB
  2. 能存大量資料
  3. 高可用:故障時也要快速回應
  4. 高擴展性
  5. 自動擴展:依流量自動增減 server
  6. 可調整的一致性(tunable)
  7. 低延遲

本章原書沒有應徵者 × 面試官的問答表,直接列出這份需求。

📖 原書 先從一台開始

單機很簡單:全部放進記憶體的 hash table。但記憶體放不下所有資料,兩個優化:① 資料壓縮;② 只把常用資料放記憶體,其他放磁碟。即使這樣,一台很快就滿,所以需要分散式 key-value store(又叫 distributed hash table)。

🗣️ Triton 他對「一台很快就滿」很有意見,見第 49 頁。

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

  1. key-value
  2. replication
  3. CAP
  4. hash ring
  5. quorum
  6. eventual consistency
  7. vector clock
  8. gossip
  9. hinted handoff
  10. Merkle tree
  11. SSTable
  12. bloom filter
  13. atomic CAS

只有一本訂位簿太危險:三家分店各放一本

① 先想像

只有台北有訂位簿,台北一停電,全台都不能訂位。所以台中、彰化也各放一本,一有新訂位就打電話互抄。

你猜猜看:三家都有簿子,台北停電了。客人還查得到 13 號桌是誰訂的嗎?

③ 這叫做 replication、replica

replication:把同一份資料自動抄到好幾台。replica:其中一份抄本。

④ 跟這章的關係

原書每筆資料抄 3 份,寫成 N = 3。完整的延伸基礎在 01 章第 14 頁「影印本」。

② 動手玩:寫在台北,馬上去別家查

去查:

延伸基礎第 3 階 · CAP懂的人可以跳過

  1. key-value
  2. replication
  3. CAP
  4. hash ring
  5. quorum
  6. eventual consistency
  7. vector clock
  8. gossip
  9. hinted handoff
  10. Merkle tree
  11. SSTable
  12. bloom filter
  13. atomic CAS

電話線斷了:先不接訂位,還是先收了再說?

① 先想像

台北和彰化之間的電話線斷了。客人打到彰化要訂 7 點 13 號桌;台北可能剛剛也收了同一桌。

你猜猜看:彰化「先收了再說」,台北剛好也收了 13 號桌。會怎樣?

③ 這叫做 CAP、partition

partition:機器之間的線斷了。CAP:C 大家看到一樣的、A 一定接得到電話、P 斷線時還能營業。

④ 跟這章的關係

線一定會斷,所以真正的選擇是 C 或 A。原書選 A(第 18 頁);Triton 說多數生意要 C(第 41 頁)。

② 動手玩:1 小時內來 10 通電話,5 通打台北、5 通打彰化

5訂不到的客人(犧牲 A)0重複賣出的桌(犧牲 C)

原書CAP theorem · Figure 1

CAP:三個保證,分散式系統最多拿兩個

這一步要解決的問題網路一定會出問題。出問題的那一刻,系統要先保住什麼?

📖 原書 Figure 1CAP theorem 的三個圓與交集(依原書內容重繪)。alt 描述把 CA 標在三圓正中的小交集,這裡依內文定義畫在 C 和 A 的交集。

🗣️ Triton 他對這三個字母的定義跟原書不一樣,HBase 在他的分類裡是「CA 向」,見第 39 頁。

📖 原書 三個定義

  • Consistency:所有 client 不管連到哪個 node,同一時間看到同樣的資料
  • Availability:就算有 node 掛了,任何要資料的 client 都拿得到回應
  • Partition tolerance:partition 是兩個 node 之間通訊中斷;系統在 partition 時還能繼續運作

📖 原書 依 CAP 分類 key-value store

  • CP:保 consistency + partition tolerance,犧牲 availability
  • AP:保 availability + partition tolerance,犧牲 consistency
  • CA:犧牲 partition tolerance。但網路故障無法避免,分散式系統一定要容忍 partition,所以真實世界不存在 CA 系統

原書Figure 2–3 · 網路斷掉時二選一

n3 斷線了:要停止接單,還是先收了再說?

這一步要解決的問題電話線真的斷了,n3 收不到 n1 的新資料。要停止接單,還是先收再說?

📖 原書 Figure 2資料複製在 n1、n2、n3 三個 replica(依原書內容重繪)
  • 📖 理想世界沒有 partition:寫進 n1 的資料自動複製到 n2、n3,C 和 A 都有
  • 📖 真實世界一定會有 partition:寫進 n1、n2 傳不到 n3;寫進 n3 的還沒傳到 n1、n2,它們就是舊資料

動手玩:電話線斷了,分店要怎麼辦

📖 原書 CP 例子是銀行:一定要顯示最新餘額,不一致解決前直接回錯誤。AP 則照樣接受讀寫,可能讀到舊資料,partition 解除後再同步到 n3。「選對 CAP 保證是重要的一步,可以和面試官討論」。

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

  1. key-value
  2. replication
  3. CAP
  4. hash ring
  5. quorum
  6. eventual consistency
  7. vector clock
  8. gossip
  9. hinted handoff
  10. Merkle tree
  11. SSTable
  12. bloom filter
  13. atomic CAS

到這裡你已經會了:一本訂位簿變三本

下一階要解決的問題

資料多到一台放不下:要怎麼分給很多台?要幾台說「抄好了」才算數?先看原書的零件地圖。

原書System components · 路線圖

一台分散式 KV store 要有八個零件

這一步要解決的問題零件很多。先看地圖:每個零件各自回答哪一個問題?

📖 原書 以下內容主要參考三個知名系統:Dynamo、Cassandra、BigTable。點卡片跳到那一頁。

文組版:八個零件分別回答「訂位簿要分給幾家分店」「每筆訂位抄幾份」「要幾家分店都確認才算訂到」「兩家分店記得不一樣聽誰的」「怎麼知道哪家分店倒了」「誰接電話」「怎麼寫進簿子」「怎麼查」。

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

  1. key-value
  2. replication
  3. CAP
  4. hash ring
  5. quorum
  6. eventual consistency
  7. vector clock
  8. gossip
  9. hinted handoff
  10. Merkle tree
  11. SSTable
  12. bloom filter
  13. atomic CAS

桌子太多一本放不下:哪家分店管哪些桌?

① 先想像

把 0–99 號桌排成一個圓圈,像時鐘。三家分店各站在圓圈上一個位置;每張桌順時針走,遇到的第一家分店負責它。

你猜猜看:台北站 30、台中站 60、彰化站 90。45 號桌歸誰?

③ 這叫做 consistent hashing、hash ring

hash ring:把 key 和 server 放在同一個圓圈上。consistent hashing:順時針找負責人,加一台只搬一小段。

④ 跟這章的關係

原書的 data partition 就用它;抄本也一樣,順時針往下數 3 家。「把資料切開放」見 01 章 sharding,細節在 05 章。

② 動手玩:拉桌號,再加開一家

台中負責這張桌的分店—加開一家:圓圈要搬的桌—改用「桌號 ÷ 分店數的餘數」要搬的桌

原書Data partition · Data replication · Figure 4–5

把 server 和 key 放在同一個環上,順時針找

這一步要解決的問題資料多到一台放不下:要怎麼分給很多台?每筆要抄給誰?

📖 原書 Figure 48 台 server 在 hash ring 上,key0 存在順時針遇到的第一台 s1(依原書內容重繪)
  • 📖 分區兩大挑戰:平均分散、增減 node 時少搬資料。上一章的 consistent hashing 正好解決
  • 📖 優點:Automatic scaling(依負載自動增減)、Heterogeneity(容量大的 server 分到較多 virtual node)
  • 白話:virtual node=一台機器在環上站好幾個位置;data center=一整棟放電腦的機房。

動手玩:key 落在哪、複製到誰

📖 原書 資料非同步複製到 N 台。用 virtual node 時,環上前 N 個點可能屬於不到 N 台實體 server,所以順時針走時只挑不重複的 server。同一個 data center 的 node 常一起掛(停電、網路、天災),所以 replica 放在不同 data center,中間用高速網路連起來。

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

  1. key-value
  2. replication
  3. CAP
  4. hash ring
  5. quorum
  6. eventual consistency
  7. vector clock
  8. gossip
  9. hinted handoff
  10. Merkle tree
  11. SSTable
  12. bloom filter
  13. atomic CAS

三家要抄:等幾家回電「抄好了」,才跟客人說訂到?

① 先想像

店員接到訂位,打給三家分店抄寫。全部等到最保險,但最慢的那家可能要很久。

你猜猜看:寫的時候等 2 家回電,讀的時候問 2 家,總共 3 家。讀的 2 家裡,至少幾家有最新訂位?

③ 這叫做 quorum、N / W / R

quorum:湊到規定的人數才算數。N 抄幾份、W 寫要等幾家、R 讀要問幾家。

④ 跟這章的關係

原書「可以調整的一致性」,就是調 W 和 R(下兩頁)。

② 動手玩:N = 3,最壞情況

2 秒寫的時候要等多久1 家寫和讀重疊讀到最新讀的結果

原書Consistency · Quorum consensus · Figure 6

要幾台說 OK,才算寫成功?

這一步要解決的問題每筆抄 3 份。要等幾份抄好,才跟客人說「訂好了」?

📖 原書 Figure 6N = 3,coordinator 把 put(key1, val1) 送給 s0、s1、s2,收 ACK(依原書內容重繪;alt 描述的箭頭方向相反,依內文畫成 coordinator 送出)

📖 原書 三個參數

  • N:replica 的數量
  • W:write quorum。寫入要收到 W 個 replica 的確認才算成功
  • R:read quorum。讀取要等到至少 R 個 replica 回應才算成功

📖 原書 W = 1 不是只寫一台

資料還是複製到 s0、s1、s2。W = 1 的意思是 coordinator 收到一個 ACK 就回成功:收到 s1 的,就不用等 s0 和 s2。Coordinator 是 client 和 node 之間的 proxy。

白話:ACK=對方回「收到、寫好了」;proxy=代替客人去找各家分店的店員。

📖 原書 延遲 vs 一致性

W = 1 或 R = 1:只要等任一台,很快。W 或 R > 1:一致性比較好,但要等最慢的那台。

原書 · 動手玩W + R > N

讀的那幾台裡,一定有一台拿到最新值嗎?

這一步要解決的問題W、R 要怎麼設,讀的時候才一定讀得到最新?台數不夠時又會怎樣?

點 node 讓它掛掉 / 復活

📖 原書 為什麼 W + R > N 就是 strong consistency

寫入的 W 台和讀取的 R 台加起來超過 N,至少有一台重疊,那台一定有最新資料。

📖 原書 幾種設定

設定效果
R = 1,W = N讀很快
W = 1,R = N寫很快
W + R > N保證強一致(通常 N=3、W=R=2)
W + R ≤ N不保證強一致

依需求調整 W、R、N,得到想要的一致性等級。

模擬規則:寫入只等前 W 台活著的 node,其他台「非同步,還沒到」;讀取挑最舊的 R 台(最壞情況)。活著的 node 不夠 W 或 R 時,strict quorum 就卡住,第 27 頁的 sloppy quorum 就是為這個設計的。

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

  1. key-value
  2. replication
  3. CAP
  4. hash ring
  5. quorum
  6. eventual consistency
  7. vector clock
  8. gossip
  9. hinted handoff
  10. Merkle tree
  11. SSTable
  12. bloom filter
  13. atomic CAS

抄寫要時間:剛訂完,別家的簿子還是舊的

① 先想像

台北 7:00:00 記下「13 號桌 → 王先生」。台中 1 秒後抄好,彰化 3 秒後才抄好。

你猜猜看:7:00:02 有人打去彰化問 13 號桌,會聽到什麼?

③ 這叫做 strong / eventual consistency

strong:任何時候問哪家都是最新的,代價是要等。eventual:先各自回答,過一陣子才一樣。

④ 跟這章的關係

原書選 eventual,跟 Dynamo、Cassandra 一樣(下一頁)。「過一陣子」之前的那位客人,就是後面所有麻煩的開始。

② 動手玩:訂完之後幾秒去問

原書Consistency models

強一致、弱一致、最終一致:原書選了最後一個

這一步要解決的問題三家都抄好之前,要不要讓客人查?原書選了哪一種?

📖 原書 三種一致性模型

  • Strong consistency:任何讀取都回傳最新一次寫入的結果,client 永遠不會看到舊資料
  • Weak consistency:之後的讀取不一定看得到最新值
  • Eventual consistency:weak 的一種。給足夠時間,所有更新都會傳開,所有 replica 會一致

📖 原書 為什麼選 eventual

Strong consistency 通常靠「在所有 replica 都同意這次寫入之前,不接受新的讀寫」,會擋住新操作,不適合高可用系統。Dynamo 和 Cassandra 都採用 eventual consistency,這也是原書推薦的模型。並行寫入時,eventual consistency 讓不一致的值進入系統,再交給 client 讀出來調解(下一頁的 versioning)。

動手玩:寫完 v2 之後,過幾毫秒去讀

模擬假設:v2 在 400 ms 時才傳到所有 replica。數字是示意,不是原書的。

訂位簿版:strong 是「三家都抄好之前,誰都不准翻簿子」;eventual 是「翻到的可能是舊的,過一陣子三本會一樣」。「過一陣子」之前那個客人看到什麼,原書交給 client 處理。

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

  1. key-value
  2. replication
  3. CAP
  4. hash ring
  5. quorum
  6. eventual consistency
  7. vector clock
  8. gossip
  9. hinted handoff
  10. Merkle tree
  11. SSTable
  12. bloom filter
  13. atomic CAS

到這裡你已經會了:分給很多家、幾家說好才算

下一階要解決的問題

既然各自回答,兩家同時改了同一行怎麼辦?分店倒了,又要怎麼知道?

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

  1. key-value
  2. replication
  3. CAP
  4. hash ring
  5. quorum
  6. eventual consistency
  7. vector clock
  8. gossip
  9. hinted handoff
  10. Merkle tree
  11. SSTable
  12. bloom filter
  13. atomic CAS

兩本簿子對不上:哪一本改得比較新?

① 先想像

每一行旁邊貼一張小貼紙,記「哪家分店改過幾次」。台北改一次,貼紙就寫「台北 1」。

你猜猜看:甲的貼紙「台北 2、台中 1」,乙的貼紙「台北 1、台中 1」。誰比較新?

③ 這叫做 vector clock、conflict

vector clock:附在資料上的「[分店, 改了幾次]」清單。conflict:兩個版本誰也不是誰改出來的。

④ 跟這章的關係

原書用它「發現」吵架;但「誰對」交給 client 決定(第 23 頁)。Triton 對這點很有意見。

② 動手玩:台北和台中各一本,起點都是「台北 1」

原書Inconsistency resolution · Figure 7–8

兩台 server 同時改同一個名字

這一步要解決的問題抄本多了,兩台同時改同一筆,要聽誰的?

📖 原書 Figure 7server 1、2 從 n1、n2 讀到同樣的 name: john(依原書內容重繪)

📖 原書 Replication 帶來高可用,也帶來 replica 之間的不一致。解法是 versioning 和 vector clock:每一次修改都當成一個新的、不可變的版本。

  1. n1、n2 有同一個值,叫它「原始值」。server 1、2 用 get("name") 都拿到 john
  2. server 1 改成 johnSanFrancisco,server 2 同時改成 johnNewYork,得到兩個互相衝突的版本 v1、v2
  3. 原始值可以忽略,因為兩個修改都是基於它;但 v1 和 v2 誰對,沒有明確的判斷方法

所以需要一個能偵測衝突、再調解衝突的版本系統:vector clock。

訂位簿版:舊簿子寫「13 號桌:空」。台北店寫「13 號桌:王先生」,台中店同時寫「13 號桌:李小姐」。電話線修好之後兩本對不上,該聽誰的?

原書Vector clock · Figure 9

每份資料帶一串 [server, 版本號]

這一步要解決的問題要怎麼記下「誰改過、改了幾次」,才分得出誰新誰舊?

📖 原書 Figure 9Vector clock 的五個步驟(依原書內容重繪;alt 中 D5 被截斷為 D5([Sx, ...]),完整值依內文)

📖 原書 定義

Vector clock 是附在資料上的 [server, version] 配對,寫成 D([S1, v1], [S2, v2], …, [Sn, vn])。資料 D 寫到 server Si 時:

  • 如果 [Si, vi] 已經存在 → vi 加 1
  • 否則 → 新增一筆 [Si, 1]

按「下一步」

依序演出原書的五個步驟。

原書 · 動手玩祖先還是兄弟

怎麼判斷兩個版本有沒有衝突

這一步要解決的問題兩個版本放在一起,怎麼一眼看出是「改出來的」還是「吵架」?

原書的例子:

📖 原書 兩條規則

  • X 是 Y 的祖先(沒衝突):Y 裡每個參與者的計數都 ≥ X 的。例:D([s0,1],[s1,1]) 是 D([s0,1],[s1,2]) 的祖先
  • X 和 Y 是兄弟(有衝突):Y 裡有某個參與者的計數 < X 的。例:D([s0,1],[s1,2]) 和 D([s0,2],[s1,1])

📖 原書 兩個缺點

  1. Client 變複雜:衝突解決邏輯要寫在 client
  2. [server: version] 會越長越多:設長度上限,超過就刪最舊的配對。這會讓祖先關係判斷不準、調解變沒效率;但 Dynamo 論文說 Amazon 在 production 還沒遇到,所以「對大多數公司應該可以接受」

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

  1. key-value
  2. replication
  3. CAP
  4. hash ring
  5. quorum
  6. eventual consistency
  7. vector clock
  8. gossip
  9. hinted handoff
  10. Merkle tree
  11. SSTable
  12. bloom filter
  13. atomic CAS

8 家分店,怎麼讓大家都知道「彰化好像倒了」?

① 先想像

沒有總部廣播。每一輪,知道消息的分店各自再隨便告訴另 1 家,像傳八卦。

你猜猜看:一開始只有 1 家知道。運氣最好時,幾輪後 8 家都知道?

③ 這叫做 gossip protocol、heartbeat

heartbeat:定期送出的「我還活著」紙條。gossip:每台隨機告訴幾台,很快全部知道。

④ 跟這章的關係

原書用它偵測故障:誰的紙條很久沒更新,大家問過之後就當它倒了(下一頁)。

② 動手玩:每輪隨機傳一家

0第幾輪1 / 8知道的分店0總共傳了幾張紙條56對照:每家打給每家,一輪就要

原書Failure detection · Figure 10–11

怎麼知道某台 server 掛了:聽八卦

這一步要解決的問題幾百台機器,沒有總部。怎麼知道哪一台倒了?

📖 原書 Figure 10All-to-all multicasting:每台都跟每台說(依原書內容重繪)

📖 原書 不能因為另一台說它掛了就相信;通常要至少兩個獨立來源才標記某台掛了。

All-to-all multicasting 最直接,但 server 一多就沒效率。更好的是去中心化的 gossip protocol:

  1. 每台維護一份 membership list:member ID 和 heartbeat counter
  2. 每台定期把自己的 heartbeat counter 加 1
  3. 每台定期把 heartbeat 傳給隨機幾台,它們再傳給另外幾台
  4. 收到 heartbeat 就更新 membership list
  5. 某台的 heartbeat 超過預定時間沒增加,就當它離線

📖 原書 Figure 11 s0 發現 s2(member ID = 2)的 heartbeat 很久沒動,把含 s2 資訊的 heartbeat 傳給隨機幾台;別台也確認之後,s2 被標記為掛掉,再傳給其他 node。

延伸基礎第 9 階 · hinted handoff懂的人可以跳過

  1. key-value
  2. replication
  3. CAP
  4. hash ring
  5. quorum
  6. eventual consistency
  7. vector clock
  8. gossip
  9. hinted handoff
  10. Merkle tree
  11. SSTable
  12. bloom filter
  13. atomic CAS

台中今天停電:訂位先寫在高雄,夾一張便條

① 先想像

13 號桌的抄本本來在台北、台中、彰化。台中停電,圓圈上的下一家高雄先代收,夾一張便條「這是台中的」。

你猜猜看:規定要 3 家抄好(W = 3),台中停電。不找人代收,這筆訂位會?

③ 這叫做 sloppy quorum、hinted handoff

sloppy quorum:湊人數時跳過倒掉的,找下一家健康的。hinted handoff:代收的夾便條,對方回來再交還。

④ 跟這章的關係

原書處理「暫時故障」就用這兩招(下一頁)。代價:湊到的 3 家,不一定是原本那 3 家。

② 動手玩:W = 3,抄本該在前三家

原書Handling temporary failures · Figure 12

s2 暫時掛了:先請隔壁 s3 代收

這一步要解決的問題原本負責的那台暫時倒了,寫入要不要跟著失敗?

📖 原書 Figure 12coordinator 寫 s0、s1 成功,送往 s2 的 put 是虛線(依原書內容重繪;s3 代收與交還的動畫依內文)

📖 原書 Sloppy quorum

Gossip 偵測到故障後,系統要確保可用。Strict quorum 下,讀寫可能被擋住(第 16 頁點掉兩台的情況)。Sloppy quorum 不硬要原本那幾台:在 hash ring 上挑前 W 台健康的 server 寫、前 R 台健康的讀,離線的直接略過。

📖 原書 Hinted handoff

某台因為網路或機器故障不能用,另一台暫時代為處理;故障那台回來後,變更再推回去達成一致。Figure 12 裡 s2 不能用,讀寫暫時由 s3 處理;s2 回來後,s3 把資料交還給 s2。

訂位簿版:台中店倒了一天,訂位先寫在隔壁彰化店的簿子上,夾一張便條「這是台中店的」。台中店重新開門,彰化店把便條上的訂位抄回去。

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

  1. key-value
  2. replication
  3. CAP
  4. hash ring
  5. quorum
  6. eventual consistency
  7. vector clock
  8. gossip
  9. hinted handoff
  10. Merkle tree
  11. SSTable
  12. bloom filter
  13. atomic CAS

到這裡你已經會了:吵架和倒店

下一階要解決的問題

分店永久壞了,要重抄一整本;資料又要怎麼寫進硬碟、怎麼最快找到?

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

  1. key-value
  2. replication
  3. CAP
  4. hash ring
  5. quorum
  6. eventual consistency
  7. vector clock
  8. gossip
  9. hinted handoff
  10. Merkle tree
  11. SSTable
  12. bloom filter
  13. atomic CAS

兩本厚厚的帳要對:不想一頁一頁比

① 先想像

每頁底下寫一個「這頁的指紋」。每 2 頁再合成一個指紋,一路合到封面。對帳時先比封面。

你猜猜看:兩本帳的封面指紋一模一樣。還要一頁一頁比嗎?

③ 這叫做 Merkle tree、root

Merkle tree:一層一層把指紋(hash)合起來的樹。root:最上面那一個,就是封面。

④ 跟這章的關係

replica 永久壞掉要重抄時,用它找出不一樣的那幾桶,只抄那幾桶(下一頁)。

② 動手玩:8 頁帳,點一頁改掉它,再從封面往下比

點下面的頁碼改那一頁
—從封面往下要比幾次8一頁一頁比要比幾次

原書Handling permanent failures · Merkle tree · Figure 13–16

永久掛掉的 replica:只同步不一樣的那一桶

這一步要解決的問題replica 永久壞了要重抄。資料這麼多,怎麼只抄不一樣的那部分?

📖 原書 Figure 13Step 1:key 1–12 分成 4 個 bucket(依原書內容重繪;原圖標籤截斷為 1…、…、7…、10…,每桶的 key 依內文)

📖 原書 Hinted handoff 處理暫時故障;replica 永久不能用,就跑 anti-entropy protocol:比較各 replica 的每筆資料,把每個 replica 更新到最新版。用 Merkle tree 偵測不一致,並把傳輸量降到最低。

Wikipedia:「Merkle tree 是一棵樹,每個非葉節點都標上它子節點標籤(或葉節點的值)的 hash。Hash tree 能有效且安全地驗證大型資料結構的內容。」

比較:先比 root;一樣就代表兩台資料相同。不一樣就比左子樹、再比右子樹,一路往下找出不同步的 bucket,只同步那幾桶。要同步的量跟差異成正比,不是跟資料總量。實際上桶很大:例如 10 億個 key 分 100 萬桶,每桶 1000 個 key。

📖 原書 三種故障,三種處理

暫時故障sloppy quorum + hinted handoff
永久故障anti-entropy + Merkle tree
整個 data center 停擺停電、斷網、天災都可能;資料複製到多個 data center,一個完全離線,使用者還能從其他 data center 存取

原書System architecture diagram · Figure 17–18

全部組起來:沒有老大,每台都一樣

這一步要解決的問題零件都有了。組起來長什麼樣?誰接電話?

📖 原書 Figure 17Client 透過 coordinator n6 讀寫,n6 轉給 n0、n1、n2(依原書內容重繪)

🗣️ Triton 080 對 Cassandra 的描述幾乎就是這張圖:「在cluster中,每一個node都是master」。差別在他接著寫的下一句,見第 40 頁。

📖 原書 架構的主要特點

  • Client 用兩個簡單 API 溝通:get(key)、put(key, value)
  • Coordinator 是一個 node,當 client 和 store 之間的 proxy
  • Node 用 consistent hashing 分布在 ring 上
  • 完全去中心化,增加、移動 node 可以自動完成
  • 資料複製在多個 node
  • 沒有 single point of failure:每個 node 的職責都一樣

因為去中心化,每個 node 都身兼多職(Figure 18):Client API、Failure detection、Conflict resolution、Failure repair mechanism、Replication、Storage engine,以及更多。

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

  1. key-value
  2. replication
  3. CAP
  4. hash ring
  5. quorum
  6. eventual consistency
  7. vector clock
  8. gossip
  9. hinted handoff
  10. Merkle tree
  11. SSTable
  12. bloom filter
  13. atomic CAS

每來一筆就翻到那頁去改太慢:先寫白板,滿了一次歸檔

① 先想像

每來一筆訂位就去倉庫翻到那頁改,很慢。改成先寫在手邊的白板,滿 4 筆就排好序、整理成新的一頁歸檔,舊頁不動。

你猜猜看:來了 8 筆訂位。白板滿 4 筆歸檔一次,要跑幾趟倉庫?

③ 這叫做 memory cache、SSTable

memory cache:記憶體裡的白板,寫和查都快。SSTable:排好序、寫好就不再改的一頁名冊。

④ 跟這章的關係

原書的 write path 就是這樣(第 33 頁)。歸檔頁越來越多,要定期合併:Triton 補了這一步(第 48 頁)。

② 動手玩:白板最多 4 筆

0舊做法:跑倉庫改頁0新做法:跑倉庫歸檔

原書Write path · Figure 19

寫入:先記帳、再放記憶體、滿了一次倒出去

這一步要解決的問題寫入要快,又不能停電就忘:一筆資料怎麼寫進去?

📖 原書 Figure 19Write path:commit log、memory cache、flush 成 SSTable(依原書內容重繪;示範用 memory cache 上限 4 筆)

📖 原書 寫入請求導到某個 node 之後(寫入/讀取路徑主要依 Cassandra 的架構):

  1. 寫入請求先持久化到 commit log 檔案
  2. 資料存進 memory cache
  3. memory cache 滿了、或到達預設門檻,資料 flush 到磁碟上的 SSTable

SSTable(sorted-string table):一份排序好的 <key, value> 清單。

訂位簿版:接到電話先在流水帳上記一筆(commit log,停電也不會忘);再寫在白板上(memory cache,查得快);白板寫滿了,整理成一頁排好序的正式名冊歸檔(SSTable),白板擦掉重來。

🗣️ Triton 這部分他同意,還補了原書沒講的 compaction 和「先 scale up」,見第 47 頁。

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

  1. key-value
  2. replication
  3. CAP
  4. hash ring
  5. quorum
  6. eventual consistency
  7. vector clock
  8. gossip
  9. hinted handoff
  10. Merkle tree
  11. SSTable
  12. bloom filter
  13. atomic CAS

歸檔了好幾頁,要找 13 號桌,每頁都翻嗎?

① 先想像

每頁封面貼一張小抄:10 個格子,0 到 9。這頁有哪張桌,就把桌號個位數那一格塗黑。

你猜猜看:找 23 號桌,某頁小抄的第 3 格是黑的。代表?

③ 這叫做 bloom filter、false positive

bloom filter:很小的小抄,回答「一定沒有」或「可能有」。false positive:說可能有,翻開卻沒有,白跑一趟。

④ 跟這章的關係

原書的 read path 先問它,少翻好幾頁 SSTable(第 35 頁)。

② 動手玩:三頁歸檔,各貼一張小抄

找桌號:
—實際翻開幾頁3沒有小抄要翻幾頁

原書Read path · Figure 20–21

讀取:記憶體先找,找不到再問 bloom filter

這一步要解決的問題資料散在記憶體和好幾個 SSTable,怎麼最快找到?

📖 原書 Figure 20資料在 memory cache,直接回傳(依原書內容重繪)
  1. 先看資料在不在 memory,不在就到第 2 步
  2. 不在 memory,檢查 bloom filter
  3. bloom filter 找出哪些 SSTable 可能有這個 key
  4. SSTables 回傳資料
  5. 結果回傳給 client

動手玩:bloom filter 幫你少翻幾本

三個 SSTable 各有一個 16 bit 的 bloom filter,每個 key 用兩個 hash:k mod 16、(k+5) mod 16。兩格都是 1 才「可能有」。

讀 key:

📖 原書 資料不在記憶體就要從磁碟拿,需要一個有效率的方法找出哪個 SSTable 有這個 key,常用 bloom filter。三個 SSTable 與 hash 函數是示意。

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

  1. key-value
  2. replication
  3. CAP
  4. hash ring
  5. quorum
  6. eventual consistency
  7. vector clock
  8. gossip
  9. hinted handoff
  10. Merkle tree
  11. SSTable
  12. bloom filter
  13. atomic CAS

到這裡你已經會了:原書的整台機器

下一階要解決的問題

原書的機器組好了:永遠接單、晚一點對齊。拿它來賣最後一張票,會發生什麼事?先看原書自己的總表。

原書Summary · Table 2

原書的總表:每個目標用哪個技術

這一步要解決的問題原書把每個目標配上一個技術。這張表少了什麼?

目標 / 問題技術頁
儲存大量資料consistent hashing 把負載分散到多台13
高可用的讀取資料複製、multi-datacenter13 · 30
高可用的寫入versioning 與 vector clock 解衝突21–23
資料分割consistent hashing13
漸進式擴展consistent hashing13
異質性consistent hashing13
可調整的一致性quorum consensus15–16
暫時故障sloppy quorum、hinted handoff27
永久故障Merkle tree30
data center 停擺跨 datacenter 複製30

📖 原書 Table 2 本章沒有另外的 wrap up 討論點,以這張表收尾。

原書到這裡結束。下一頁補最後一階,接著是 Triton 的觀點。

你猜猜看:拿這台機器去賣最後一張 13 號桌,表裡哪一列能保證不賣給兩個人?

看這張表少了什麼

十列裡有可用、擴展、故障、分割,唯一跟「資料對不對」有關的是「可調整的一致性」,而原書在第 18 頁已經推薦 eventual consistency。

表裡沒有這幾個問題:

  • 兩個人同時搶最後一張票,誰拿到?
  • 「只有在還有空位時才扣」這種 check-and-set 怎麼做?
  • 扣錢和出貨兩筆資料要一起成功怎麼辦?

🔭 推論 這三個問題是本簡報整理的,答案來自接下來 Triton 的材料。

延伸基礎第 13 階 · atomic CAS懂的人可以跳過

  1. key-value
  2. replication
  3. CAP
  4. hash ring
  5. quorum
  6. eventual consistency
  7. vector clock
  8. gossip
  9. hinted handoff
  10. Merkle tree
  11. SSTable
  12. bloom filter
  13. atomic CAS

小明和小華,同時要訂最後一張 13 號桌

① 先想像

兩位店員同時翻簿子,都看到 13 號桌是空的,各自寫上自己客人的名字。

你猜猜看:規則改成「看+寫一口氣做完,中間不准別人碰簿子」。兩人同時按下,結果?

③ 這叫做 race condition、atomic CAS

race condition:兩人同時「看了再寫」,有一筆被蓋掉。atomic CAS(compare-and-set):「還是空的才寫」,檢查和寫入不能被插隊。

④ 跟這章的關係

賣票、扣庫存、轉帳都靠它;Triton 說原書那種 store 做不到。race condition 另見 04 章第 26 頁。

② 動手玩:你來決定誰先動

Triton 觀點他講的 CAP 跟原書不一樣

Triton 的 C:多人同時改同一份資料,會不會 race condition

📖 原書 C = 大家看到一樣的資料

「所有 client 不管連到哪個 node,同一時間看到同樣的資料」。P = 通訊中斷時還能運作。CA 不存在。

這個定義只問讀到的是不是最新,所以 W + R > N 就叫 strong consistency。

原書這樣做會出什麼事?原書的 C 只問「讀不讀得到最新」。小明和小華同時寫 13 號桌,這個 C 管得到嗎?

🗣️ Triton 本人說 CAP 定理(086 第 5 頁)

  • Consistency:「資料一致性,多人試圖改動同一份資料是,是否會發生 race condition」
    • 「RDBMS: multi-row multi-record consistency」
    • 「HBase: single-row single-record consistency」
    • 「Cassandra: No consistency」
  • Availability:「你的資料庫是否高可用」
  • Partition tolerance:「你的資料庫是否容許 multi-master」

086-redis-2018.pdf.md · 第 4 頁吃飯定理、第 5 頁 CAP 定理

🔭 推論 兩個定義差在哪:原書的 C 問「讀不讀得到最新值」,Triton 的 C 問「兩個人同時寫,會不會寫壞」。後者才是賣票、扣庫存、轉帳要的東西。用 Triton 的定義,P 是「容許 multi-master」,所以單一 owner 的 HBase 是「CA 向」(第 43 頁),跟原書「CA 不存在」並不衝突:兩邊的 P 根本不是同一個東西。

Triton 不同意直球 · 080 NoSQL 雜談

❌ 原書的 AP store 無法使用 Atomic CAS

🗣️ Triton 的例子 「整個過程都用 Quorum Consistency」

080-nosql-intro.pdf.md · 第 17 頁「無法 Atomic CAS」(數值與時間照原投影片)

原書這樣做會出什麼事?原書說 N = 3、W = R = 2 就「保證強一致」。用這個設定做「如果是 100 就改成 102」,會怎樣?

「在cluster中,每一個node都是master … Quorum Consistency:不管READ和WRITE,都需要至少 (n/2)+1台成功 … 保證拿到最新版本的 record。Gossip:node之間通訊,交流 record的最新版本。無法使用Atomic CAS」🗣️ Triton 本人說 080 · 第 15 頁「Cassandra架構」

這跟原書有什麼關係

Triton 描述的 Cassandra(每台都是 master、quorum、gossip、新的 timestamp 勝出)就是原書第 16–31 頁那台機器。🔭 推論 他的例子用的正是 W = R = 2、N = 3,也就是原書說「保證強一致」的設定:讀得到最新值,不等於能安全地「檢查之後再改」。

Triton 不同意售票系統

「單用 Cassandra 是寫不出售票系統的」

原書這樣做會出什麼事?用原書那台 AP store 賣座位:小明和小華同時按下 13G。

「Cassandra是AP向的,即是說:你一點也不介意 data consistency。如果沒有 zookeeper / redis作 locking server 或是你走 event-based system路線,你單用Cassandra是寫不出售票系統的。」
「現實上,毫不介意 consistency的商業應用很少的,所以除了開始時熱潮,今天你沒看到什麼商業專案用的。」🗣️ Triton 本人說 080 · 第 18 頁「Cassandra適用場景」

動手玩:小明和小華同時按下 13G

🔭 推論 AP store 那條是依 080 第 17 頁的機制(各 replica 各自接受、timestamp 新的勝出)演出的示意,不是 Triton 的原始例子。

🗣️ Triton 「Consistency 保證系統在移動失敗時,能安全地回到本來正確狀態。所以,RDBMS能保證不會發生付了錢卻搶不到票」065-lesson0.pdf.md · C@RDBMS

Triton 的做法還是空的才寫

RDBMS 一句 update,就是 atomic CAS

🗣️ Triton RDBMS 一句 SQL 就做完的事

update seat set status = 'reserved', reservation_ts = now(),
  user_id = :user_id
where event_id = :event_id and seat_no = :seat_no
  and (reservation_ts is null
     or reservation_ts < now() - interval '5 minute')
  and status != 'sold'

先佔座位,5 分鐘內付款;付款後再一句 update 改成 sold。080 第 12–14 頁「atomic check-and-set案例」;164 是同一個寫法的完整版

你猜猜看:小明和小華同時送出左邊這句 update。小華收到「affected rows = 0」,代表?

白話:where 那幾行就是「還是空的才寫」

  • 沒人佔,或佔了超過 5 分鐘還沒付錢
  • 而且還沒賣掉
  • 檢查和寫入是同一句,中間沒人能插隊:第 38 頁的 atomic CAS

Triton 補充同樣是 NoSQL,HBase 為什麼做得到

一筆資料只交給一個 owner,就能 Atomic CAS

你猜猜看:同樣是 NoSQL,怎樣才做得到 atomic CAS?

「每一個HBase node只負責特定 PK Range的 data operation。Record X的READ / WRITE,肯定會送到同一個 data node,所以能有 strong consistency,也能做到Atomic CAS」🗣️ Triton 本人說 080 · 第 19 頁「HBase架構」

「因為mapping table只由 coordinator一個來管理,這樣子保證同一 record的所有 operation都會送到同一個HBase node上,所以HBase才能做到Atomic CAS」「HBase算是 CA向的,跟 RDBMS一樣。你不能錯了也沒所謂,你需要 Atomic CAS」🗣️ Triton 080 · 第 20、22 頁

📝 上課筆記 學員筆記把它寫成「CAP 定理中的 CP,比起 Cassandra 多了 C 少了 A」。047 · Roy 的上課筆記 用原書的定義是 CP;Triton 原文用的是「CA 向」,原因見第 39 頁。

加一台 node 時,各家搬什麼

搬什麼Triton 說
Cassandra
=原書的設計
每台搬 1/N 的資料「基於 Quorum Consistency機制,少了一個 data node是不影響的,所以對 end user是 zero downtime的」080 p.16
HBase只搬責任範圍,資料在下層 HDFS「在HBase node轉移的,只是責任範圍而不是資料本身。雖然受影響的資料不是完全的 zero downtime,但是非常小」080 p.21
MongoDB要搬資料「因為需要等待資料的搬動,所以 downtime會不短,所以,千萬別在 peak hours時才加上 mongodb data node」080 p.24

🔭 推論 原書說「每個 node 職責一樣,所以沒有 SPOF」。HBase 反其道而行:有一個 coordinator 管 mapping、每筆資料只有一個 owner。代價是 owner 換手時有很短的不可用,換到的是 atomic CAS。訂位簿版:13 號桌只有台北店能寫,其他分店接到電話一律轉台北。

Triton 不同意tunable consistency 的實際樣子

可調整的一致性,預設值調在哪裡?

原書這樣做會出什麼事?原書說一致性「可以調整」。實際裝好、沒去調的預設值,比較可能是哪一格?

「Cassandra標準設定是ONE 而不是QUOTUM,那代表Cassandra的 READ可能返回舊版本的記錄。」「noSQL需要使用2 phase commit去手動處理 multiple record atomicity。現實上的2pc需求多個步驟,很慢的。」「noSQL的「快」,是建立犠性數據的安全性和正確性上。」🗣️ Triton 本人說 065-lesson0.pdf.md · 「RDBMS真的很慢嗎?」(原文 QUOTUM、犠性照錄)

「同一份的資料,如果你需要維持strong consistency,最終你的Write是沒法distributed,讓你的系統出現hotspot的。」🗣️ Triton 126-喵談 Keep it simple, stupid.md

原書的 API 只有一個 key

put(key, value)、get(key),quorum 也只對一個 key 談。

「如果這二份data是存放在不同的machine上,而你是需要做到strong consistency的(即是說:不能扣了錢但是沒給用戶商品),那麼2pc(或是其變種)是不能避免的」🗣️ Triton 100-二份data是存放在不同的machine上(2pc).md

「只有 relation db 能處理這種 multi state, multi record 的情況」📝 上課筆記 029-Redis.md(無署名的 Redis 課堂筆記) · 一致性(A 轉錢給 B 的例子)

🔭 推論 原書把「tunable」當成優點:W、R 可以隨需求調。Triton 指出的是現實:預設值常常是最快、最不一致的那一格(第 16 頁的 W = R = 1),而且就算調到 quorum,單 key 的 quorum 也管不到「扣錢 + 出貨」這種兩筆資料的事。

Triton 補充那 AP store 什麼時候是對的?

先問:這份資料錯了,會不會死人?

原書這樣做會出什麼事?原書不問資料種類,一律 AP。哪一種資料用 AP store 真的沒關係?

談 data,先看 consistency

「到底這份data是否錯一點也沒所謂的?(例子:Triton今天在fb又發了多少篇廢文的統計數據)還是他絕對不能錯,而且有需要跟其他資料一起all-or-none地改動?(例子:Triton的銀行帳戶。…)」

UserStatistics 這種「即使用戶一些行為沒被記錄到也死不了人」的 counter:「考慮到底層資料結構,用Cassandra看來比較好」,但「再三警告:流量不夠大請勿用上noSQL」。

🗣️ Triton 本人說 117-喵看Data 的思維.md

不是每種 race condition 都要避

「如果你在賣遊戲中的虛寶,賣1萬件和賣1萬+1件沒分別……如果你的系統在賣火車票,當然絕對不能超賣」「最重要一點:讓Race condition發生後不出現「致命錯誤」,讓系統向不致命的方向發生錯誤」「容錯度越高的商業邏輯,其效能一定越快」

🗣️ Triton 本人說 069-lesson1.pdf.md · 實務建議 4

Triton 補充AP store 的真正強項

整個 region 趴掉還要服務:這時才輪到 AP

你猜猜看:假設 AWS 整個東京 region 停擺,服務還要能用。哪一種比較撐得住?

multi-DC 是 AP 的真正強項

「Cassandra的mult-master概念,配上DC awareness。再一句:前提你需要一點也不介意 inconsistent data。能大幅降低你的 latency,你能做到整個AWS / Azure region 趴掉時,還能維持服務」080 p.18;對照 HBase「架構本身沒有 DC awareness」080 p.22。

「對一般中小型公司來說,很多時Master-Slave是在同一datacenter內,而且資料可靠度比效能更加重要」136

🗣️ Triton 本人說 080、136-喵談 pg mysql 的 replication.md

🔭 推論 所以 Triton 不是說原書的設計是錯的技術,而是說它適用的資料很窄:統計 counter、可遺失的 hot data、要扛整個 region 掛掉的全球服務。原書的需求清單第一句就該是「這份資料錯了會怎樣」,而不是「高可用、自動擴展」。訂位簿版:分店記「今天來了幾位客人」可以各記各的,晚上再加總;記「13 號桌給誰」不行。

Triton 同意write path、read path

✅ SSTable 是對的,而且原書少講了一半

你猜猜看:RDBMS 一頁 16KB。你只改了一個字(幾 bytes),硬碟要寫多少?

🗣️ Triton 為什麼不用 RDBMS 的 data page

  • 「所有的 RDBMS,其資料都是存放在 data page 內:Oracle, postgresql: 8KB;MySQL: 16KB」
  • 「即使你只改動一點點,你還是要整個 data page作 file IO,而且是Random Write IO」
  • 「B+ tree的 page splitting和merging會引起廣域 page lock」

080 · 第 3–5 頁

🗣️ Triton SSTable 怎麼做(對照原書 Figure 19–21)

  • 「SSTable一旦建立後就永不改動(immutable)。有資料改動時,DB會把新版本資料留在 main memory,REDO log還是會寫的。Memory buffer快要滿時,再一口氣把全部新資料去建立新的 SSTable file,所以沒有了 Random Write IO」
  • 「Meta data部份:Primary Key的 bloom filter、PK Index」
  • 原書沒講的:「當你要讀取 Record X時,你需要檢查每一個 SSTable,如果 Record X存在於多個 SSTable 便使用最新的一個版本」「database的 background worker,會把多個 SSTable file合成一個」

080 · 第 7–10 頁

Triton 補充原書少講的另一半

歸檔頁越來越多:要合併,也能壓縮

補充

「Storage level compression,理想是配上 Write-once架構,例子:SSTable in cassandra / HBase」054-data-analysis.pdf.md

📝 上課筆記 「bloom filter 大小只有 MB 級,可以駐留在 Main Memory。好處是,如果 bloom filter 問不到 id 就不用找了。而就算 bloom filter 誤以為有,也只是讓他白白跑一趟而已。」047

🔭 推論 「把多個 SSTable 合成一個」就是 compaction。原書的 write path 只畫到 flush,沒畫 compaction;不做 compaction,第 35 頁要翻的 SSTable 會越來越多。

你猜猜看:原書的 write path 只畫到「白板滿了就歸檔」。一直歸檔、從不合併,讀一筆會?

文組版:白板滿了就歸檔一頁(第 32 頁)。晚上打烊後,把好幾頁合成一頁、同一張桌只留最新的,隔天查起來就快。

Triton 不同意「一台很快就滿」

先 scale up,小流量回去用 pg / mysql

「在使用 SSTable的 noSQL(像 Hbase, Cassandra),你應該先 scale up,直到 server cost會 non-linearly增加時才 scale-out。太小的專案,你不應該用很小的機器。他喵的你小流量就回去用 pg / mysql啦!」🗣️ Triton 本人說 080 · 第 11 頁「SSTable注意事項」

「不能不見的data,我一定存到RDBMS」「如果是小型系統,單純scale up便算了;如果是大型系統,始終還是要走Hbase那些方向的」「正常沒亂來的系統,在20core + 200GB RAM的暴力機器下,絕大部份都沒需要玩clustering」🗣️ Triton 106-喵 data.md

「今天 (2018),在 amazon能租上 3904 GB RAM的主機,你的系統真的需要 scale out嗎?」「先把系統正確地做好了,等到RDBMS 沒法支持的那一天,你絕對有錢找高手用 noSQL重寫系統」🗣️ Triton 065 · 「RDBMS 沒有 scalability」

原書這樣做會出什麼事?每秒幾百筆訂位的小專案,也照書「先分散」?

原書舉的 KV store 例子:Redis、Memcached

「(Persistence、Low latency)以上二者你最多只能要一個。Redis是追求 Low latency,想單用 Redis做到 zero data loss,跟在沙漠中吃生魚片一樣」🗣️ Triton 087-redis-2019.pdf.md · 第 5 頁

「如果跟錢有關的話,千萬不要用 redis」📝 上課筆記 029-Redis.md(無署名的 Redis 課堂筆記)

原書的參考資料 [1] 是 Amazon DynamoDB;Triton 2014 年左右替客戶測 EC2 時寫過:「amazon dynamoDB的使用和其效能,讓我覺得真的不值得。」107-喵 ec2 測試.md

🔭 推論 原書第 5 頁說「單機很快就滿,所以要分散式」。Triton 的順序剛好相反:先問資料能不能錯 → 不能錯就 RDBMS → 一台大機器撐到成本非線性成長 → 才 shard 或換 HBase 這類有 owner 的 NoSQL。

📅 2026 補充書本身的時間差

原書寫的是 Dynamo 論文的世界

你猜猜看:原書參考的 Cassandra、DynamoDB,後來有沒有補上「還是空的才寫」?

📅 2026 補充 Cassandra 後來加了 CAS

Cassandra 2.0 起有 lightweight transactions(INSERT … IF NOT EXISTS、UPDATE … IF col = …),用 Paxos 對單一 partition 做 compare-and-set。代價是一次操作要多次來回,比一般寫入慢很多。Triton 自己的 065 也寫過「所以Cassandra 2.0之前是需要Zookeeper」。但這已經不是原書那套「quorum + 新的 timestamp 勝出」。

📅 2026 補充 DynamoDB ≠ Dynamo 論文

原書參考資料 [1] 是 Amazon DynamoDB 服務,內文卻照 2007 年 Dynamo 論文講 vector clock 和 client 端調解。DynamoDB 這個服務提供 strongly consistent read、conditional write,2018 年起也有 transactions。DynamoDB 不會把 vector clock 交給 client 調解;把原書的 Dynamo 做法直接套在 DynamoDB 上是不準的。

🔭 依 Triton 原則推論 這代表什麼

連原書的範本系統,後來都往「能做 CAS」的方向補。這正好呼應 Triton 080 的判斷:「現實上,毫不介意 consistency的商業應用很少的」。

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

  1. key-value
  2. replication
  3. CAP
  4. hash ring
  5. quorum
  6. eventual consistency
  7. vector clock
  8. gossip
  9. hinted handoff
  10. Merkle tree
  11. SSTable
  12. bloom filter
  13. atomic CAS

到這裡你已經會了:Triton 為什麼不同意

13 階全部走完了

下一頁用一句話收尾;再下一頁是名詞小卡,給大家課後複習。

一句話記住

三本訂位簿永遠接單很容易,
同一張桌子只賣一次很難。

原書對的地方

  • CAP、quorum、W + R > N 的推導
  • Consistent hashing 做 partition 與 replication
  • Gossip、hinted handoff、Merkle tree 這些故障處理零件
  • Commit log → memtable → SSTable、bloom filter(Triton 同意)

Triton 不同意的地方

  • AP + eventual consistency 當預設:「毫不介意 consistency的商業應用很少的」
  • quorum 讀得到最新,不代表能 atomic CAS
  • 衝突交給 client 調解:售票時錢已經付了
  • 「一台很快就滿」:先 scale up,小流量用 pg / mysql

Triton 的做法

  • 先問這份資料錯了會怎樣
  • 不能錯:RDBMS,一句 UPDATE … WHERE 做 check-and-set
  • 真的要 NoSQL:選有單一 owner 的(HBase)
  • 可以錯:counter、hot data、全球 multi-DC 才用 AP

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

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

key-value store一個 key 對一個 value 的資料庫,就是訂位簿
put / get寫一行/查一行
hash table用 key 直接算出放在哪一格,一查就到
node / server一台機器,就是一家分店
replication、replica把資料抄到好幾台/其中一份抄本
partition機器之間的線斷了
CAP一致、可用、斷線還能營業:斷線時 C 和 A 只能挑一個
CP / AP斷線時寧可不接單/斷線時照樣接單
consistent hashing、hash ringkey 和 server 放在同一個圓圈上,順時針找負責人
virtual node一台機器在圓圈上站好幾個位置
coordinator接電話、替 client 去找各台的店員
quorum、N / W / R湊到人數才算數;抄幾份/寫等幾家/讀問幾家
ACK對方回「收到、寫好了」
strong / eventual consistency任何時候都最新(要等)/晚一點才一樣

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

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

Triton 本人的講義 / 文章

  • 080-nosql-intro.pdf.md — noSQL雜談(2023):data page 問題、SSTable 架構與「先 scale up」、atomic check-and-set 售票 SQL、Cassandra 架構「無法使用Atomic CAS」與第 17 頁例子、「單用Cassandra是寫不出售票系統的」「毫不介意 consistency的商業應用很少的」、HBase 單一 owner「CA向」、加 node 比較
  • 086-redis-2018.pdf.md — 吃飯定理、Triton 版 CAP 定義(Cassandra: No consistency)
  • 087-redis-2019.pdf.md — 吃飯定理、Persistence vs Low latency
  • 065-lesson0.pdf.md — Cassandra 預設 ONE、noSQL 的快建立在犧牲正確性、2pc、3904 GB RAM、「付了錢卻搶不到票」
  • 069-lesson1.pdf.md — 實務建議 4:虛寶 vs 火車票
  • 117 談 data 先看 consistency · 106 scale up、不能不見的 data 放 RDBMS · 029 跟錢有關別用 redis、multi record 只有 RDBMS · 100 跨機器 2pc · 126 strong consistency 的 write 無法 distributed · 136 multi-DC 是 Uber 等級 · 054 write-once compression · 164 戲院售票 SQL · 107 DynamoDB 不值得

上課筆記:047(Roy 的 NoSQL 雜談筆記,引用 HBase「CP」與 bloom filter 解讀,非本人原文)。不引用:022(NotebookLM 摘要)、190(AI 生成的「Triton 題庫」)。

一個可以直接問自己的問題

你系統裡最重要的那個 UPDATE,有沒有 WHERE remaining > 0 這種條件?你選的資料庫,能不能讓這句話原子地成立?

原書對照

Alex Xu, System Design Interview Vol.1 Ch.6。開頭定義、Table 1、Understand the problem、Single server(第 5 頁);CAP theorem 與 Figure 1(8);Ideal / Real-world 與 Figure 2–3(9);System components(11);Data partition、Data replication 與 Figure 4–5(13);Consistency、Quorum 與 Figure 6(15–16);Consistency models(18);Inconsistency resolution、vector clock 與 Figure 7–9(21–23);Failure detection 與 Figure 10–11(25);Temporary failures 與 Figure 12(27);Permanent failures、Merkle tree 與 Figure 13–16、Data center outage(30);System architecture 與 Figure 17–18(31);Write path 與 Figure 19(33);Read path 與 Figure 20–21(35);Summary Table 2(37)。原書 21 張圖都依圖說與 alt 描述重繪,不是原圖。

循序漸進(文組版)的頁面

學習地圖(第 3 頁);延伸基礎 13 階:key-value(4)、replication(6,複習 01 章)、CAP(7)、hash ring(12)、quorum(14)、eventual consistency(17)、vector clock(20)、gossip(24)、hinted handoff(26)、Merkle tree(29)、SSTable(32)、bloom filter(34)、atomic CAS(38);小結(10、19、28、36、51);名詞小卡(53)。Triton 段:39–50。連鎖餐廳與分店的數字是示意,不是原書或實測值。

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