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 階。每一階只用前面講過的東西。
- 1key-value桌號 → 誰訂的
- 2replication三本一樣的簿子
- 3CAP電話線斷了,二選一
- 4hash ring哪家分店管哪些桌
- 5quorum幾家回電才算數
- 6eventual consistency晚一點才一樣
- 7vector clock誰改過幾次的貼紙
- 8gossip分店互傳紙條
- 9hinted handoff隔壁分店代收
- 10Merkle tree對帳先比總數
- 11SSTable白板滿了就歸檔
- 12bloom filter「一定沒有」的小抄
- 13atomic CAS看+寫一口氣做完
第 1–3 階 · 一本變三本
要回答:電話線斷了,分店該怎麼辦?
第 4–6 階 · 分給很多家
要回答:幾家說好才算訂到?
第 7–9 階 · 吵架與倒店
要回答:兩本對不上、分店倒了怎麼辦?
第 10–12 階 · 修復與存放
要回答:怎麼對帳、怎麼寫進硬碟?
第 13 階 · Triton 的問題
要回答:這台機器能拿來賣票嗎?
全程只用一個例子:連鎖餐廳的三本訂位簿(虛構)
三家分店:台北、台中、彰化(加開時還有高雄)。每爬 3 階,有一頁「到這裡你已經會了」。
延伸基礎第 1 階 · key-value懂的人可以跳過
- key-value
- replication
- CAP
- hash ring
- quorum
- eventual consistency
- vector clock
- gossip
- hinted handoff
- Merkle tree
- SSTable
- bloom filter
- atomic CAS
訂位簿每一行只有兩欄:桌號、誰訂的
① 先想像
分店的訂位簿,每一行只寫「13 號桌」和「王先生」。查的時候報桌號,就知道是誰訂的。
你猜猜看:簿子有 1,000 行,每個桌號都有固定的那一頁。查「13 號桌」要看幾行?
桌號直接告訴你翻到哪一行,看 1 行就好。沒有這個規則,才要從頭一行一行找。
③ 這叫做 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
| key | value |
|---|---|
| 145 | john |
| 147 | bob |
| 160 | julia |
只要兩個 API
put(key, value) get(key)
插入 key 對應的 value;取得 key 對應的 value
📖 原書 設計範圍
「沒有完美的設計」:每種設計都在讀、寫、記憶體之間取捨,另一個取捨是 consistency 和 availability。本章要做的 store:
- 每筆 key-value 很小:< 10 KB
- 能存大量資料
- 高可用:故障時也要快速回應
- 高擴展性
- 自動擴展:依流量自動增減 server
- 可調整的一致性(tunable)
- 低延遲
本章原書沒有應徵者 × 面試官的問答表,直接列出這份需求。
📖 原書 先從一台開始
單機很簡單:全部放進記憶體的 hash table。但記憶體放不下所有資料,兩個優化:① 資料壓縮;② 只把常用資料放記憶體,其他放磁碟。即使這樣,一台很快就滿,所以需要分散式 key-value store(又叫 distributed hash table)。
🗣️ Triton 他對「一台很快就滿」很有意見,見第 49 頁。
延伸基礎 · 複習第 2 階 · replication01 章講過,懂的人可以跳過
- key-value
- replication
- CAP
- hash ring
- quorum
- eventual consistency
- vector clock
- gossip
- hinted handoff
- Merkle tree
- SSTable
- bloom filter
- atomic CAS
只有一本訂位簿太危險:三家分店各放一本
① 先想像
只有台北有訂位簿,台北一停電,全台都不能訂位。所以台中、彰化也各放一本,一有新訂位就打電話互抄。
你猜猜看:三家都有簿子,台北停電了。客人還查得到 13 號桌是誰訂的嗎?
另外兩本都有抄。可是抄寫要時間:剛寫完那一秒,別本可能還沒抄到。右邊試試看。
③ 這叫做 replication、replica
replication:把同一份資料自動抄到好幾台。replica:其中一份抄本。
④ 跟這章的關係
原書每筆資料抄 3 份,寫成 N = 3。完整的延伸基礎在 01 章第 14 頁「影印本」。
② 動手玩:寫在台北,馬上去別家查
延伸基礎第 3 階 · CAP懂的人可以跳過
- key-value
- replication
- CAP
- hash ring
- quorum
- eventual consistency
- vector clock
- gossip
- hinted handoff
- Merkle tree
- SSTable
- bloom filter
- atomic CAS
電話線斷了:先不接訂位,還是先收了再說?
① 先想像
台北和彰化之間的電話線斷了。客人打到彰化要訂 7 點 13 號桌;台北可能剛剛也收了同一桌。
你猜猜看:彰化「先收了再說」,台北剛好也收了 13 號桌。會怎樣?
兩邊都以為桌子是空的。換成「先不接」就不會重複,但打到彰化的客人訂不到。
③ 這叫做 CAP、partition
partition:機器之間的線斷了。CAP:C 大家看到一樣的、A 一定接得到電話、P 斷線時還能營業。
④ 跟這章的關係
線一定會斷,所以真正的選擇是 C 或 A。原書選 A(第 18 頁);Triton 說多數生意要 C(第 41 頁)。
② 動手玩:1 小時內來 10 通電話,5 通打台北、5 通打彰化
原書CAP theorem · Figure 1
CAP:三個保證,分散式系統最多拿兩個
這一步要解決的問題網路一定會出問題。出問題的那一刻,系統要先保住什麼?
🗣️ 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 的新資料。要停止接單,還是先收再說?
- 📖 理想世界沒有 partition:寫進 n1 的資料自動複製到 n2、n3,C 和 A 都有
- 📖 真實世界一定會有 partition:寫進 n1、n2 傳不到 n3;寫進 n3 的還沒傳到 n1、n2,它們就是舊資料
動手玩:電話線斷了,分店要怎麼辦
📖 原書 CP 例子是銀行:一定要顯示最新餘額,不一致解決前直接回錯誤。AP 則照樣接受讀寫,可能讀到舊資料,partition 解除後再同步到 n3。「選對 CAP 保證是重要的一步,可以和面試官討論」。
到這裡你已經會了小結 1 / 5
- key-value
- replication
- CAP
- hash ring
- quorum
- eventual consistency
- vector clock
- gossip
- hinted handoff
- Merkle tree
- SSTable
- bloom filter
- atomic CAS
到這裡你已經會了:一本訂位簿變三本
- 訂位簿每一行是一個 key 對一個 value,只有
put、get兩個動作。 - 為了不怕一家停電,同一行抄成 3 份(replication,N = 3)。
- 電話線一定會斷(partition)。斷線時只能二選一:資料不錯(CP),或一定接單(AP)。
下一階要解決的問題
資料多到一台放不下:要怎麼分給很多台?要幾台說「抄好了」才算數?先看原書的零件地圖。
原書System components · 路線圖
一台分散式 KV store 要有八個零件
這一步要解決的問題零件很多。先看地圖:每個零件各自回答哪一個問題?
📖 原書 以下內容主要參考三個知名系統:Dynamo、Cassandra、BigTable。點卡片跳到那一頁。
文組版:八個零件分別回答「訂位簿要分給幾家分店」「每筆訂位抄幾份」「要幾家分店都確認才算訂到」「兩家分店記得不一樣聽誰的」「怎麼知道哪家分店倒了」「誰接電話」「怎麼寫進簿子」「怎麼查」。
延伸基礎第 4 階 · hash ring懂的人可以跳過
- key-value
- replication
- CAP
- hash ring
- quorum
- eventual consistency
- vector clock
- gossip
- hinted handoff
- Merkle tree
- SSTable
- bloom filter
- atomic CAS
桌子太多一本放不下:哪家分店管哪些桌?
① 先想像
把 0–99 號桌排成一個圓圈,像時鐘。三家分店各站在圓圈上一個位置;每張桌順時針走,遇到的第一家分店負責它。
你猜猜看:台北站 30、台中站 60、彰化站 90。45 號桌歸誰?
從 45 順時針走,先遇到 60 的台中。95 號桌呢?走過 99 繞回 0,先遇到 30 的台北。
③ 這叫做 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 放在同一個環上,順時針找
這一步要解決的問題資料多到一台放不下:要怎麼分給很多台?每筆要抄給誰?
- 📖 分區兩大挑戰:平均分散、增減 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懂的人可以跳過
- key-value
- replication
- CAP
- hash ring
- quorum
- eventual consistency
- vector clock
- gossip
- hinted handoff
- Merkle tree
- SSTable
- bloom filter
- atomic CAS
三家要抄:等幾家回電「抄好了」,才跟客人說訂到?
① 先想像
店員接到訂位,打給三家分店抄寫。全部等到最保險,但最慢的那家可能要很久。
你猜猜看:寫的時候等 2 家回電,讀的時候問 2 家,總共 3 家。讀的 2 家裡,至少幾家有最新訂位?
2 + 2 = 4,比 3 家多 1,兩組一定至少重疊 1 家,那家有最新的。
③ 這叫做 quorum、N / W / R
quorum:湊到規定的人數才算數。N 抄幾份、W 寫要等幾家、R 讀要問幾家。
④ 跟這章的關係
原書「可以調整的一致性」,就是調 W 和 R(下兩頁)。
② 動手玩:N = 3,最壞情況
原書Consistency · Quorum consensus · Figure 6
要幾台說 OK,才算寫成功?
這一步要解決的問題每筆抄 3 份。要等幾份抄好,才跟客人說「訂好了」?
📖 原書 三個參數
- 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 要怎麼設,讀的時候才一定讀得到最新?台數不夠時又會怎樣?
📖 原書 為什麼 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懂的人可以跳過
- key-value
- replication
- CAP
- hash ring
- quorum
- eventual consistency
- vector clock
- gossip
- hinted handoff
- Merkle tree
- SSTable
- bloom filter
- atomic CAS
抄寫要時間:剛訂完,別家的簿子還是舊的
① 先想像
台北 7:00:00 記下「13 號桌 → 王先生」。台中 1 秒後抄好,彰化 3 秒後才抄好。
你猜猜看:7:00:02 有人打去彰化問 13 號桌,會聽到什麼?
彰化 7:00:03 才抄到。過了 3 秒,問哪一家都一樣:這就是「最後會一致」。
③ 這叫做 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
- key-value
- replication
- CAP
- hash ring
- quorum
- eventual consistency
- vector clock
- gossip
- hinted handoff
- Merkle tree
- SSTable
- bloom filter
- atomic CAS
到這裡你已經會了:分給很多家、幾家說好才算
- 桌號和分店排在同一個圓圈上,順時針找負責人;加開一家只搬一小段(hash ring)。
- 寫要等 W 家、讀要問 R 家;W + R 大於 N,讀的那幾家一定有一家是最新的(quorum)。
- 原書選「先各自回答,晚一點才一樣」(eventual consistency)。
下一階要解決的問題
既然各自回答,兩家同時改了同一行怎麼辦?分店倒了,又要怎麼知道?
延伸基礎第 7 階 · vector clock懂的人可以跳過
- key-value
- replication
- CAP
- hash ring
- quorum
- eventual consistency
- vector clock
- gossip
- hinted handoff
- Merkle tree
- SSTable
- bloom filter
- atomic CAS
兩本簿子對不上:哪一本改得比較新?
① 先想像
每一行旁邊貼一張小貼紙,記「哪家分店改過幾次」。台北改一次,貼紙就寫「台北 1」。
你猜猜看:甲的貼紙「台北 2、台中 1」,乙的貼紙「台北 1、台中 1」。誰比較新?
甲每一格都 ≥ 乙,甲是從乙改出來的,留甲就好。要是甲有一格比較大、乙有另一格比較大,才是吵架。
③ 這叫做 vector clock、conflict
vector clock:附在資料上的「[分店, 改了幾次]」清單。conflict:兩個版本誰也不是誰改出來的。
④ 跟這章的關係
原書用它「發現」吵架;但「誰對」交給 client 決定(第 23 頁)。Triton 對這點很有意見。
② 動手玩:台北和台中各一本,起點都是「台北 1」
原書Inconsistency resolution · Figure 7–8
兩台 server 同時改同一個名字
這一步要解決的問題抄本多了,兩台同時改同一筆,要聽誰的?
📖 原書 Replication 帶來高可用,也帶來 replica 之間的不一致。解法是 versioning 和 vector clock:每一次修改都當成一個新的、不可變的版本。
- n1、n2 有同一個值,叫它「原始值」。server 1、2 用
get("name")都拿到 john - server 1 改成
johnSanFrancisco,server 2 同時改成johnNewYork,得到兩個互相衝突的版本 v1、v2 - 原始值可以忽略,因為兩個修改都是基於它;但 v1 和 v2 誰對,沒有明確的判斷方法
所以需要一個能偵測衝突、再調解衝突的版本系統:vector clock。
訂位簿版:舊簿子寫「13 號桌:空」。台北店寫「13 號桌:王先生」,台中店同時寫「13 號桌:李小姐」。電話線修好之後兩本對不上,該聽誰的?
原書Vector clock · Figure 9
每份資料帶一串 [server, 版本號]
這一步要解決的問題要怎麼記下「誰改過、改了幾次」,才分得出誰新誰舊?
📖 原書 定義
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])
📖 原書 兩個缺點
- Client 變複雜:衝突解決邏輯要寫在 client
- [server: version] 會越長越多:設長度上限,超過就刪最舊的配對。這會讓祖先關係判斷不準、調解變沒效率;但 Dynamo 論文說 Amazon 在 production 還沒遇到,所以「對大多數公司應該可以接受」
延伸基礎第 8 階 · gossip懂的人可以跳過
- key-value
- replication
- CAP
- hash ring
- quorum
- eventual consistency
- vector clock
- gossip
- hinted handoff
- Merkle tree
- SSTable
- bloom filter
- atomic CAS
8 家分店,怎麼讓大家都知道「彰化好像倒了」?
① 先想像
沒有總部廣播。每一輪,知道消息的分店各自再隨便告訴另 1 家,像傳八卦。
你猜猜看:一開始只有 1 家知道。運氣最好時,幾輪後 8 家都知道?
1 → 2 → 4 → 8,每輪翻倍。運氣差會多幾輪,但不用每家都打給每家。
③ 這叫做 gossip protocol、heartbeat
heartbeat:定期送出的「我還活著」紙條。gossip:每台隨機告訴幾台,很快全部知道。
④ 跟這章的關係
原書用它偵測故障:誰的紙條很久沒更新,大家問過之後就當它倒了(下一頁)。
② 動手玩:每輪隨機傳一家
原書Failure detection · Figure 10–11
怎麼知道某台 server 掛了:聽八卦
這一步要解決的問題幾百台機器,沒有總部。怎麼知道哪一台倒了?
📖 原書 不能因為另一台說它掛了就相信;通常要至少兩個獨立來源才標記某台掛了。
All-to-all multicasting 最直接,但 server 一多就沒效率。更好的是去中心化的 gossip protocol:
- 每台維護一份 membership list:member ID 和 heartbeat counter
- 每台定期把自己的 heartbeat counter 加 1
- 每台定期把 heartbeat 傳給隨機幾台,它們再傳給另外幾台
- 收到 heartbeat 就更新 membership list
- 某台的 heartbeat 超過預定時間沒增加,就當它離線
📖 原書 Figure 11 s0 發現 s2(member ID = 2)的 heartbeat 很久沒動,把含 s2 資訊的 heartbeat 傳給隨機幾台;別台也確認之後,s2 被標記為掛掉,再傳給其他 node。
延伸基礎第 9 階 · hinted handoff懂的人可以跳過
- key-value
- replication
- CAP
- hash ring
- quorum
- eventual consistency
- vector clock
- gossip
- hinted handoff
- Merkle tree
- SSTable
- bloom filter
- atomic CAS
台中今天停電:訂位先寫在高雄,夾一張便條
① 先想像
13 號桌的抄本本來在台北、台中、彰化。台中停電,圓圈上的下一家高雄先代收,夾一張便條「這是台中的」。
你猜猜看:規定要 3 家抄好(W = 3),台中停電。不找人代收,這筆訂位會?
只湊得到 2 家。找高雄代收,就又湊得到 3 家。
③ 這叫做 sloppy quorum、hinted handoff
sloppy quorum:湊人數時跳過倒掉的,找下一家健康的。hinted handoff:代收的夾便條,對方回來再交還。
④ 跟這章的關係
原書處理「暫時故障」就用這兩招(下一頁)。代價:湊到的 3 家,不一定是原本那 3 家。
② 動手玩:W = 3,抄本該在前三家
原書Handling temporary failures · Figure 12
s2 暫時掛了:先請隔壁 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
- key-value
- replication
- CAP
- hash ring
- quorum
- eventual consistency
- vector clock
- gossip
- hinted handoff
- Merkle tree
- SSTable
- bloom filter
- atomic CAS
到這裡你已經會了:吵架和倒店
- 每份資料帶一張「誰改過幾次」的貼紙(vector clock),分得出「改出來的」和「吵架」;吵架交給 client。
- 分店之間互傳「我還活著」的紙條(gossip),很久沒更新、又有別家確認,才當它倒了。
- 暫時倒了,就找下一家代收、夾便條,回來再交還(hinted handoff)。
下一階要解決的問題
分店永久壞了,要重抄一整本;資料又要怎麼寫進硬碟、怎麼最快找到?
延伸基礎第 10 階 · Merkle tree懂的人可以跳過
- key-value
- replication
- CAP
- hash ring
- quorum
- eventual consistency
- vector clock
- gossip
- hinted handoff
- Merkle tree
- SSTable
- bloom filter
- atomic CAS
兩本厚厚的帳要對:不想一頁一頁比
① 先想像
每頁底下寫一個「這頁的指紋」。每 2 頁再合成一個指紋,一路合到封面。對帳時先比封面。
你猜猜看:兩本帳的封面指紋一模一樣。還要一頁一頁比嗎?
任何一頁不一樣,往上合的指紋都會跟著變。封面一樣,就代表每頁都一樣。
③ 這叫做 Merkle tree、root
Merkle tree:一層一層把指紋(hash)合起來的樹。root:最上面那一個,就是封面。
④ 跟這章的關係
replica 永久壞掉要重抄時,用它找出不一樣的那幾桶,只抄那幾桶(下一頁)。
② 動手玩:8 頁帳,點一頁改掉它,再從封面往下比
原書Handling permanent failures · Merkle tree · Figure 13–16
永久掛掉的 replica:只同步不一樣的那一桶
這一步要解決的問題replica 永久壞了要重抄。資料這麼多,怎麼只抄不一樣的那部分?
📖 原書 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
全部組起來:沒有老大,每台都一樣
這一步要解決的問題零件都有了。組起來長什麼樣?誰接電話?
🗣️ 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懂的人可以跳過
- key-value
- replication
- CAP
- hash ring
- quorum
- eventual consistency
- vector clock
- gossip
- hinted handoff
- Merkle tree
- SSTable
- bloom filter
- atomic CAS
每來一筆就翻到那頁去改太慢:先寫白板,滿了一次歸檔
① 先想像
每來一筆訂位就去倉庫翻到那頁改,很慢。改成先寫在手邊的白板,滿 4 筆就排好序、整理成新的一頁歸檔,舊頁不動。
你猜猜看:來了 8 筆訂位。白板滿 4 筆歸檔一次,要跑幾趟倉庫?
8 ÷ 4 = 2。原本每筆一趟要 8 趟,現在 2 趟,而且每趟是一口氣寫一整頁。
③ 這叫做 memory cache、SSTable
memory cache:記憶體裡的白板,寫和查都快。SSTable:排好序、寫好就不再改的一頁名冊。
④ 跟這章的關係
原書的 write path 就是這樣(第 33 頁)。歸檔頁越來越多,要定期合併:Triton 補了這一步(第 48 頁)。
② 動手玩:白板最多 4 筆
原書Write path · Figure 19
寫入:先記帳、再放記憶體、滿了一次倒出去
這一步要解決的問題寫入要快,又不能停電就忘:一筆資料怎麼寫進去?
📖 原書 寫入請求導到某個 node 之後(寫入/讀取路徑主要依 Cassandra 的架構):
- 寫入請求先持久化到 commit log 檔案
- 資料存進 memory cache
- memory cache 滿了、或到達預設門檻,資料 flush 到磁碟上的 SSTable
SSTable(sorted-string table):一份排序好的 <key, value> 清單。
訂位簿版:接到電話先在流水帳上記一筆(commit log,停電也不會忘);再寫在白板上(memory cache,查得快);白板寫滿了,整理成一頁排好序的正式名冊歸檔(SSTable),白板擦掉重來。
🗣️ Triton 這部分他同意,還補了原書沒講的 compaction 和「先 scale up」,見第 47 頁。
延伸基礎第 12 階 · bloom filter懂的人可以跳過
- key-value
- replication
- CAP
- hash ring
- quorum
- eventual consistency
- vector clock
- gossip
- hinted handoff
- Merkle tree
- SSTable
- bloom filter
- atomic CAS
歸檔了好幾頁,要找 13 號桌,每頁都翻嗎?
① 先想像
每頁封面貼一張小抄:10 個格子,0 到 9。這頁有哪張桌,就把桌號個位數那一格塗黑。
你猜猜看:找 23 號桌,某頁小抄的第 3 格是黑的。代表?
13 號桌也會塗黑第 3 格。黑的只代表「可能」;白的才是保證:一定沒有,不用翻。
③ 這叫做 bloom filter、false positive
bloom filter:很小的小抄,回答「一定沒有」或「可能有」。false positive:說可能有,翻開卻沒有,白跑一趟。
④ 跟這章的關係
原書的 read path 先問它,少翻好幾頁 SSTable(第 35 頁)。
② 動手玩:三頁歸檔,各貼一張小抄
原書Read path · Figure 20–21
讀取:記憶體先找,找不到再問 bloom filter
這一步要解決的問題資料散在記憶體和好幾個 SSTable,怎麼最快找到?
- 先看資料在不在 memory,不在就到第 2 步
- 不在 memory,檢查 bloom filter
- bloom filter 找出哪些 SSTable 可能有這個 key
- SSTables 回傳資料
- 結果回傳給 client
動手玩:bloom filter 幫你少翻幾本
三個 SSTable 各有一個 16 bit 的 bloom filter,每個 key 用兩個 hash:k mod 16、(k+5) mod 16。兩格都是 1 才「可能有」。
📖 原書 資料不在記憶體就要從磁碟拿,需要一個有效率的方法找出哪個 SSTable 有這個 key,常用 bloom filter。三個 SSTable 與 hash 函數是示意。
到這裡你已經會了小結 4 / 5
- key-value
- replication
- CAP
- hash ring
- quorum
- eventual consistency
- vector clock
- gossip
- hinted handoff
- Merkle tree
- SSTable
- bloom filter
- atomic CAS
到這裡你已經會了:原書的整台機器
- 對帳先比封面的指紋,只往不一樣的那半邊走(Merkle tree)。
- 寫入先記白板,滿了排好序一次歸檔,舊頁不改(SSTable)。
- 讀取先看每頁的小抄,白的就不翻(bloom filter)。
下一階要解決的問題
原書的機器組好了:永遠接單、晚一點對齊。拿它來賣最後一張票,會發生什麼事?先看原書自己的總表。
原書Summary · Table 2
原書的總表:每個目標用哪個技術
這一步要解決的問題原書把每個目標配上一個技術。這張表少了什麼?
| 目標 / 問題 | 技術 | 頁 |
|---|---|---|
| 儲存大量資料 | consistent hashing 把負載分散到多台 | 13 |
| 高可用的讀取 | 資料複製、multi-datacenter | 13 · 30 |
| 高可用的寫入 | versioning 與 vector clock 解衝突 | 21–23 |
| 資料分割 | consistent hashing | 13 |
| 漸進式擴展 | consistent hashing | 13 |
| 異質性 | consistent hashing | 13 |
| 可調整的一致性 | quorum consensus | 15–16 |
| 暫時故障 | sloppy quorum、hinted handoff | 27 |
| 永久故障 | Merkle tree | 30 |
| data center 停擺 | 跨 datacenter 複製 | 30 |
📖 原書 Table 2 本章沒有另外的 wrap up 討論點,以這張表收尾。
原書到這裡結束。下一頁補最後一階,接著是 Triton 的觀點。
你猜猜看:拿這台機器去賣最後一張 13 號桌,表裡哪一列能保證不賣給兩個人?
可調整的一致性只管「讀不讀得到最新」。兩個人同時寫,表裡沒有一列處理。
看這張表少了什麼
十列裡有可用、擴展、故障、分割,唯一跟「資料對不對」有關的是「可調整的一致性」,而原書在第 18 頁已經推薦 eventual consistency。
表裡沒有這幾個問題:
- 兩個人同時搶最後一張票,誰拿到?
- 「只有在還有空位時才扣」這種 check-and-set 怎麼做?
- 扣錢和出貨兩筆資料要一起成功怎麼辦?
🔭 推論 這三個問題是本簡報整理的,答案來自接下來 Triton 的材料。
延伸基礎第 13 階 · atomic CAS懂的人可以跳過
- key-value
- replication
- CAP
- hash ring
- quorum
- eventual consistency
- vector clock
- gossip
- hinted handoff
- Merkle tree
- SSTable
- bloom filter
- 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 的 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」,會怎樣?
quorum 只保證讀得到最新,不保證「檢查+寫入」是同一個動作。左邊按「下一步」看 Triton 的例子。
「在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。
兩家分店各自接受寫入,timestamp 新的勝出。衝突被發現時,錢已經付了。右邊切到「AP store」按按看。
「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 的條件不成立,一行都沒改到。畫面可以馬上告訴小華「被選走了」,他根本還沒付錢。
白話:where 那幾行就是「還是空的才寫」
- 沒人佔,或佔了超過 5 分鐘還沒付錢
- 而且還沒賣掉
- 檢查和寫入是同一句,中間沒人能插隊:第 38 頁的 atomic CAS
Triton 補充同樣是 NoSQL,HBase 為什麼做得到
一筆資料只交給一個 owner,就能 Atomic CAS
你猜猜看:同樣是 NoSQL,怎樣才做得到 atomic CAS?
只有一台在管這筆資料,「檢查+寫入」就不會被別台插隊。這就是 HBase 的做法。
「每一個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 的實際樣子
可調整的一致性,預設值調在哪裡?
原書這樣做會出什麼事?原書說一致性「可以調整」。實際裝好、沒去調的預設值,比較可能是哪一格?
預設常常是最快、最不一致的設定,要你自己知道去調。Triton 舉的就是 Cassandra 的預設。
「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 真的沒關係?
統計數字少記幾筆「死不了人」;餘額和座位錯了就出事。Triton 的判準在下面。
談 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 停擺,服務還要能用。哪一種比較撐得住?
每家都能接單,一個 region 倒了,別的 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),硬碟要寫多少?
RDBMS 以 data page 為單位讀寫;改一點點也要整頁寫,而且是跳來跳去的 random write。這正是 SSTable 想避開的。
🗣️ 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 只畫到「白板滿了就歸檔」。一直歸檔、從不合併,讀一筆會?
bloom filter 只能少翻幾頁;頁數一直變多,「可能有」的頁也跟著變多。所以要在背景合併。
文組版:白板滿了就歸檔一頁(第 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」
原書這樣做會出什麼事?每秒幾百筆訂位的小專案,也照書「先分散」?
多花錢,還多出一堆一致性問題。Triton 的順序:先問資料能不能錯、先 scale up。
原書舉的 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,後來有沒有補上「還是空的才寫」?
兩邊後來都加了 conditional write/compare-and-set,代價是比較慢。
📅 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
- key-value
- replication
- CAP
- hash ring
- quorum
- eventual consistency
- vector clock
- gossip
- hinted handoff
- Merkle tree
- SSTable
- bloom filter
- atomic CAS
到這裡你已經會了:Triton 為什麼不同意
- Triton 的 C 問的是「兩人同時改,會不會改壞」;讀得到最新值,不等於做得到 atomic CAS。
- 賣票要「還是空的才寫」:RDBMS 一句
UPDATE … WHERE,或每筆資料只有一個 owner 的 HBase。 - 原書那種 AP store 適合「錯了也沒關係」的資料;小流量先 scale up,回去用 pg / mysql。
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
本章名詞小卡課後複習用 · 每個名詞一句白話
今天出現的名詞,一句話講完
給工程師的重點出處與標籤
引述來源(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。連鎖餐廳與分店的數字是示意,不是原書或實測值。