System Design Interview · 第 5 章Triton 覆蓋度:🟡 中Triton 線

Design Consistent Hashing
多開一台機器,不該讓所有人搬家

原書這章是一個演算法:把 key 和 server 都放到一個圓環上,key 順時針找第一台 server。加機器、少機器時,只有一小段的 key 要搬。這一章 Triton 大致同意原書,他的補充在兩件事:這招該用在哪裡,以及它解決不了什麼。

給文組

全程只用一個情境:期末考分教室,一階一階爬 11 個概念。頁首標 延伸基礎 的頁是補基礎,懂的人可以跳過。

給工程師

原書 15 張圖全部依描述重繪成可播放的 SVG。最後一頁列出引述的出處檔案(materials/core)。

標籤怎麼看

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

先用生活理解為什麼「取餘數」會出事

期末考依學號分教室:多開一間,誰要換教室?

3教室數 N—這次要換教室的人

規則很簡單:學號 % 教室數,餘 0 去 0 號教室,餘 1 去 1 號教室……

平常沒問題:每間人數差不多,大家也算得出自己在哪。可是報名的人一多,教務處多開一間教室,N 從 3 變 4,幾乎每個人算出來的教室都變了,走廊上一片混亂。

把「同學」換成電腦裡的一筆資料、「教室」換成一台電腦,這就是原書這一章開頭的問題。% 是什麼、為什麼會亂,從第 4 頁起一階一階講。

按「多開一間教室」幾次看看:N 間變 N+1 間,大約有 N/(N+1) 的人要搬。後面會看到另一種分法,只要搬大約 1/(N+1)。

學習地圖本章的概念階梯

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

  1. 1餘數 %時鐘繞一圈
  2. 2hash名字變號碼
  3. 3sharding分到好幾間
  4. 4cache miss走錯教室
  5. 5hash ring圓形走廊
  6. 6partition負責的一段
  7. 7virtual node一人管好幾間
  8. 8標準差跟平均差多少
  9. 9hotspot全擠同一間
  10. 10consistency只剩一個座位
  11. 11scale up換大禮堂

第 1–4 階 · 取餘數為什麼會出事

要回答:多開一台,為什麼幾乎大家都要搬家?

第 5–8 階 · 原書的圓環

要回答:怎麼只搬一小段?怎麼分得平均?

第 9–11 階 · Triton 的但書

要回答:這招救不了什麼?資料庫要不要這樣切?

全程只用一個情境:期末考分教室(虛構)

同學 = key(一筆資料)教室 = server用名字算出的號碼 = hash走錯教室 = cache miss教務處 = database圓形大樓的走廊 = hash ring

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

延伸基礎第 1 階 · 餘數 %懂的人可以跳過

  1. 餘數 %
  2. hash
  3. sharding
  4. cache miss
  5. hash ring
  6. partition
  7. virtual node
  8. 標準差
  9. hotspot
  10. consistency
  11. scale up

時鐘過了 12 點,為什麼又從頭數?

① 先想像

時鐘只有 12 格,頂端那格當作 0。數到 12 就繞回 0,再繼續數。所以 13 點和 1 點,指針停在同一格。

你猜猜看:現在 10 點,再過 5 個小時,指針停在幾點?

③ 這叫做 modulo(取餘數)

%:繞圈數完,剩下的那一段。15 % 12 = 3,讀作「15 除以 12 餘 3」。

④ 跟這章的關係

原書開頭用 % N 把資料分給 N 台電腦。N 就是「時鐘有幾格」。

② 動手玩:一格一格數

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

  1. 餘數 %
  2. hash
  3. sharding
  4. cache miss
  5. hash ring
  6. partition
  7. virtual node
  8. 標準差
  9. hotspot
  10. consistency
  11. scale up

名字不是數字,怎麼取餘數?先把名字變成號碼

① 先想像

學號是數字,可以直接取餘數。可是電腦裡的資料常常只有名字。教務處用一個固定的公式,把每個名字變成一個號碼。

你猜猜看:「王小明」今天算一次、明天再算一次,號碼會?

③ 這叫做 hash function(雜湊函數)

hash function:把任何文字變成一個號碼的固定公式。hash 值:算出來的那個號碼。

④ 跟這章的關係

原書把資料的名字(key)丟進 hash,再 % N:hash(key) % N。

② 動手玩:把名字變號碼

延伸基礎 · 複習第 3 階 · sharding懂的人可以跳過

  1. 餘數 %
  2. hash
  3. sharding
  4. cache miss
  5. hash ring
  6. partition
  7. virtual node
  8. 標準差
  9. hotspot
  10. consistency
  11. scale up

一間教室坐不下 40 人:分成 3 間,誰去哪間?

① 先想像

一間教室只坐得下 15 人,40 人要分成 3 間。不想發名單,就請大家自己算:學號 % 3,餘幾就去幾號教室。

你猜猜看:學號 107,去哪一間?

③ 這叫做 sharding(分片)

sharding:把一大堆資料依規則分給好幾台電腦。server pool:這一群電腦,N 是台數。

④ 跟這章的關係

原書第一句:要擴展,就要把資料平均分到各台 server。完整版見第 1 章第 34 頁(會員名冊分冊)。

② 動手玩:學號 % 3

延伸基礎 · 複習第 4 階 · cache miss懂的人可以跳過

  1. 餘數 %
  2. hash
  3. sharding
  4. cache miss
  5. hash ring
  6. partition
  7. virtual node
  8. 標準差
  9. hotspot
  10. consistency
  11. scale up

走錯教室,座位表上沒有你:只好跑去教務處問

① 先想像

每間教室門口貼一張座位表,看一眼就知道坐哪。正本在教務處,但教務處只有一個窗口,每分鐘只能回答 100 人。

你猜猜看:400 人同時到,75% 走錯教室。最後一位在教務處要等多久?

③ 這叫做 cache、cache miss

cache:放在手邊、看一眼就有的小抄,正本在 database。cache hit / miss:小抄上有/沒有,只好去問正本。

④ 跟這章的關係

原書說:server 數一變,大量 cache miss 一起湧向資料庫。完整版見第 1 章第 18 頁(保溫台)。

② 動手玩:400 人同時到考場

300跑去教務處問的人(cache miss)3 分鐘最後一位要等多久

原書開場 · The rehashing problem · Table 1、2

原書的起點:serverIndex = hash(key) % N

這一步要解決的問題資料多到一台放不下,要分給好幾台。用什麼規則分,大家才找得到?

📖 原書 要水平擴展,就要把 request 和資料有效率又平均地分到各台 server。Consistent hashing 是常用的做法。但原書先講問題。

📖 原書 有 n 台 cache server 時,常見的分法是 serverIndex = hash(key) % N,N 是 server pool 的大小。原書的例子:4 台 server、8 個字串 key(Table 1)。hash(key0) % 4 = 1,所以 client 要去 server 1 拿 key0 的資料。

📖 原書 server 數量固定、資料分布平均時,這方法很好用。問題出在加減 server:server 1 離線,pool 變 3 台,hash 值不變,但 % 3 的結果變了(Table 2)。

白話:水平擴展=多開幾台分工;request=送給電腦的一次請求;client=來拿資料的那一端;serverIndex=第幾號 server。

原書這章不是面試題的格式:沒有應徵者 × 面試官的問答,也沒有容量估算。它從一個問題講到一個演算法,最後是 wrap up。所以這份簡報的「原書」部分是按原書的段落順序走。

—搬家的 key

hash 值與兩個餘數照原書 Table 1、Table 2。* server 1 離線後剩 server 0、2、3,索引 0 / 1 / 2 依序對應它們,這是重繪時的推定,原書只列出 hash % 3 的值。

原書The rehashing problem · Figure 1、2

少一台 server,大部分的 key 都換了位置

這一步要解決的問題少一台 server 時,到底有多少 key 換了位置?後果是什麼?

📖 原書 Figure 1依 Table 1,8 個 key 分到 4 台 server(依原書內容重繪)
📖 原書 Figure 2server 1 離線,依 Table 2 重新分配;紅框是換了 server 的 key(依原書內容重繪;索引對應方式為推定)

📖 原書 Figure 1:上方是 serverIndex = hash % 4,下面是 server 0–3 和分到每台的 key。

📖 原書 Figure 2:serverIndex = hash % 3。大多數 key 被重新分配,不只是原本存在離線 server(server 1)上的那些。

📖 原書 後果:server 1 離線時,大多數 cache client 會連到錯的 server 拿資料,造成 a storm of cache misses(cache miss 風暴)。Consistent hashing 是減輕這個問題的有效技術。

文組翻譯

cache miss 風暴 = 一大群同學走進錯的教室,找不到自己的座位,只好全部跑去教務處(資料庫)問。教務處只有一個窗口,很快就被擠爆(第 7 頁)。

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

  1. 餘數 %
  2. hash
  3. sharding
  4. cache miss
  5. hash ring
  6. partition
  7. virtual node
  8. 標準差
  9. hotspot
  10. consistency
  11. scale up

到這裡你已經會了:為什麼取餘數會出事

下一階要解決的問題

能不能讓每個人的位置跟總共幾間無關,多開一間時只有一小段的人要搬?

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

  1. 餘數 %
  2. hash
  3. sharding
  4. cache miss
  5. hash ring
  6. partition
  7. virtual node
  8. 標準差
  9. hotspot
  10. consistency
  11. scale up

圓形大樓:從你的位置順時針走,第一間就是你的教室

① 先想像

學校是一棟圓形大樓,走廊像時鐘有 12 格。教室蓋在 2、6、10 點。每位同學也有自己的位置。規則:順時針走,遇到第一間就進去。

你猜猜看:同學站在 11 點,順時針走,進哪一間?

③ 這叫做 hash ring(雜湊環)

hash ring:把 hash 號碼排成一圈,最大的接回 0。順時針:只往同一個方向找下一間。

④ 跟這章的關係

原書把 server 和 key 都放上同一個環。多蓋一間,只有它前面那一小段的人換教室。

② 動手玩:12 位同學,3 間教室

原書定義 · Hash space and hash ring · Figure 3、4

把 hash 值的頭尾接起來,變成一個圓環

這一步要解決的問題想讓位置跟「總共幾台」無關。先把所有 hash 號碼排成一圈。

「Consistent hashing 是一種特殊的 hashing:當 hash table 重新調整大小時,平均只需要重新對應 k/n 個 key(k 是 key 的數量,n 是 slot 的數量)。相比之下,大多數傳統 hash table 只要 slot 數一變,幾乎所有 key 都要重新對應。」📖 原書引用 Wikipedia [1]

📖 原書 假設 hash 函數 f 是 SHA-1,輸出範圍是 x0、x1、x2 … xn。SHA-1 的 hash space 是 0 到 2^160 − 1:x0 對應 0,xn 對應 2^160 − 1,其他值都落在中間(Figure 3)。把兩端接起來,就得到 hash ring(Figure 4)。

白話:hash table=依號碼分格子放東西的表;slot=其中一格;SHA-1=一種有名的 hash 公式;hash space=它算得出來的所有號碼;2^160 大約是 1 後面接 48 個 0。

文組翻譯

一條很長的尺,刻度從 0 到一個天文數字。把尺彎成一圈,最大的刻度接回 0,就像第 11 頁的圓形走廊(也像時鐘):沒有盡頭,走到底就回到起點。

📖 原書 Figure 3hash space:x0 到 xn 排成一條線(依原書內容重繪)
📖 原書 Figure 4兩端接起來,x0 和 xn 在環的頂端相遇(依原書內容重繪)

原書Hash servers · Hash keys · Figure 5、6

server 和 key 用同一個 hash 函數,放到同一個環上

這一步要解決的問題環有了,server 和 key 各自要放在環上的哪裡?

📖 原書 Figure 5用 f 對 server 的 IP 或名稱算 hash,4 台 server 落在環上(依原書內容重繪)
📖 原書 Figure 64 個 cache key(key0–key3)也 hash 到環上(依原書內容重繪)

📖 原書 Hash servers:用同一個 hash 函數 f,依 server 的 IP 或名稱把 server 對應到環上。Figure 5 有 4 台:s0–s3。

📖 原書 Hash keys:值得一提,這裡用的 hash 函數和 rehashing problem 那段的不一樣,而且沒有取餘數(modular operation)。Figure 6 把 key0–key3 hash 到環上。

白話:IP=電腦在網路上的門牌號碼;modular operation=取餘數(第 4 頁)。

文組翻譯

圓形走廊上要蓋教室:每間教室的位置由教室的名字算出來(server = 教室)。每位同學的位置也由名字算出來(key = 同學)。位置只跟自己的名字有關,跟總共幾間無關,所以多蓋一間,別人的位置不會變。

原書Server lookup · Figure 7

從 key 的位置順時針走,遇到的第一台 server 就是它的家

這一步要解決的問題key 和 server 都在環上了。一個 key 要怎麼知道自己住哪一台?

📖 原書 Figure 7順時針:key0 → server 0、key1 → server 1、key2 → server 2、key3 → server 3(依原書內容重繪)

📖 原書 要知道 key 存在哪台 server,就從 key 在環上的位置順時針走,直到遇到一台 server。

📖 原書 依 Figure 7:key0 存在 server 0;key1 存在 server 1;key2 存在 server 2;key3 存在 server 3。

文組翻譯

走廊只准順時針走。同學從自己的位置出發,遇到的第一間教室就進去,那一間就是他的資料所在地。不用查表,不用知道總共有幾間。

工程上的寫法:把所有 server 的位置排序存成陣列,查 key 時用 binary search 找「第一個 ≥ key 位置」的 server,找不到就繞回第一個。這是常見實作方式,原書沒有寫到這一層。

白話:binary search=翻字典,每次翻到中間,看要往前還是往後。

原書Add a server · Remove a server · Figure 8、9

加一台、拿掉一台:只有一段的 key 要搬

這一步要解決的問題多開一台、少一台時,到底誰要搬?

📖 原書 Figure 8加入 server 4 後只有 key0 改存到 s4;虛線是原本去 s0 的路(依原書內容重繪)
📖 原書 Figure 9拿掉 server 1 後只有 key1 改存到 server 2(依原書內容重繪;alt 描述寫箭頭從 k2 出發,這裡依內文畫 key1)

📖 原書 加一台:依照上面的邏輯,新增 server 只需要重新分配一小部分的 key。Figure 8 加入 server 4 後,只有 key0 要搬:原本 key0 存在 server 0,現在從 key0 順時針走,第一個遇到的是 server 4。key1、key2、key3 都留在原地。

📖 原書 拿掉一台:同樣只有一小部分 key 要重新分配。Figure 9 拿掉 server 1 後,只有 key1 要改去 server 2,其他 key 不受影響。

文組翻譯

走廊上新蓋一間,只有「上一間到新教室之間」的同學會改進新教室,其他人照舊。某一間關閉,原本進那間的人往前多走一間就好。

動手玩Hash ring 遊樂場

自己加減 server,數數看有幾個 key 要搬

這一步要解決的問題自己試:40 個 key、加減一台,搬家的真的只有一小段嗎?

—這次搬家的 key(consistent hashing)—同樣變動若用 hash % N

按「加一台 server」,或按下面某台的 ✕ 拿掉它。點環上的 key 看它順時針走到哪台。

「虛擬節點」開關是第 19 頁的概念,講到那裡再回來開。

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

  1. 餘數 %
  2. hash
  3. sharding
  4. cache miss
  5. hash ring
  6. partition
  7. virtual node
  8. 標準差
  9. hotspot
  10. consistency
  11. scale up

每間教室負責一段走廊:這幾段一樣長嗎?

① 先想像

走廊 12 格,教室蓋在哪,就決定它負責「上一間之後到自己」這一段。段越長,進來的同學越多。

你猜猜看:教室蓋在 1、2、3 點。哪一間最擠?

③ 這叫做 partition(分區)

partition:兩台相鄰 server 之間、歸後面那台管的那一段環。

④ 跟這章的關係

原書說基本做法有兩個問題:partition 大小不一、key 擠在一起(下一頁)。

② 動手玩:教室蓋在哪裡

原書Two issues in the basic approach · Figure 10、11

基本做法的兩個問題:分區不一樣大、key 分布不平均

這一步要解決的問題只搬一小段已經很好了。但有沒有某一台特別累?

📖 原書 Figure 10s1 被拿掉後,s2 的 partition(雙向箭頭)是 s0、s3 的兩倍(依原書內容重繪)
📖 原書 Figure 11server 擠在一起時,大部分 key 落到 server 2,server 1、3 沒有資料(依原書內容重繪;白點是 key)

📖 原書 Consistent hashing 由 MIT 的 Karger 等人提出 [1]。基本步驟兩條:

  1. 用均勻分布的 hash 函數把 server 和 key 對應到環上
  2. 從 key 的位置順時針走,第一台遇到的 server 就是它的

📖 原書 問題一:server 會加會減,所以不可能讓每台 server 的 partition 一樣大。partition 是相鄰兩台 server 之間的 hash space,可能很小也可能很大。Figure 10:s1 被拿掉,s2 的 partition 變成 s0、s3 的兩倍。

📖 原書 問題二:key 在環上可能分布不均。Figure 11 的 server 位置下,大部分 key 存在 server 2,server 1 和 server 3 沒有資料。

📖 原書 解法:一種叫 virtual nodes(或 replicas)的技術。

白話:均勻分布=環上每個位置被抽到的機會一樣;partition 見第 17 頁。

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

  1. 餘數 %
  2. hash
  3. sharding
  4. cache miss
  5. hash ring
  6. partition
  7. virtual node
  8. 標準差
  9. hotspot
  10. consistency
  11. scale up

運氣不好包下半圈?讓每位老師在各處管好幾間

① 先想像

3 位監考老師,每人管一間教室,位置用名字算。運氣不好,一位會包下大半圈走廊。

你猜猜看:改成每位老師在走廊各處管 10 間小教室,每人負責的總長度會?

③ 這叫做 virtual node(虛擬節點)

virtual node:同一台 server 在環上的好幾個分身,每個分身都指回真正那一台。

④ 跟這章的關係

原書用它解決上一頁的兩個問題(下一頁)。代價:要記的位置變多。

② 動手玩:3 位老師

原書Virtual nodes · Figure 12、13

每台 server 在環上放好幾個分身

這一步要解決的問題怎麼讓每台 server 分到的那一段環接近一樣長?

📖 原書 Figure 12server 0、server 1 各 3 個虛擬節點;標 s0 的 partition 歸 server 0 管(依原書內容重繪;alt 寫每台 4 個,依內文畫 3 個)
📖 原書 Figure 13k0 順時針遇到的第一個虛擬節點是 s1_1,所以存在 server 1(依原書內容重繪)

📖 原書 virtual node 指向真實的 node,每台 server 在環上由多個 virtual node 代表。Figure 12 中 server 0、server 1 各有 3 個;3 是隨便選的,真實系統裡的數量大得多。

📖 原書 不再只用 s0,而用 s0_0、s0_1、s0_2 代表 server 0;s1_0、s1_1、s1_2 代表 server 1。每台 server 負責多個 partition:標 s0 的 partition 歸 server 0,標 s1 的歸 server 1。

📖 原書 查找一樣順時針,只是找第一個虛擬節點。Figure 13:k0 順時針遇到 s1_1,s1_1 指向 server 1。

文組翻譯

每位監考老師只管一間教室,運氣不好就會包下半圈走廊。改成每位老師在走廊各處管很多間小教室,每人負責的總長度就會接近(第 19 頁)。教室多,門牌也多:要記的位置變多了。

延伸基礎第 8 階 · 標準差懂的人可以跳過

  1. 餘數 %
  2. hash
  3. sharding
  4. cache miss
  5. hash ring
  6. partition
  7. virtual node
  8. 標準差
  9. hotspot
  10. consistency
  11. scale up

四間教室的人數「平不平均」,用一個數字說

① 先想像

兩組考場,都是 40 人分 4 間,平均每間 10 人。可是一組每間剛好 10 人,另一組有的 1 人、有的 19 人。

你猜猜看:A 組 10、10、10、10;B 組 1、19、1、19。哪一組比較「不平均」?

③ 這叫做 standard deviation(標準差)

平均:總人數 ÷ 間數。標準差:每間跟平均「大約差幾人」。越小越平均。

④ 跟這章的關係

原書說:虛擬節點越多,標準差越小;100 個時約是平均的 10%。

② 動手玩:四間教室的人數

10平均0標準差(大約差幾人)0%標準差 ÷ 平均

原書 · 動手算虛擬節點越多越平均,但要付記憶體

虛擬節點要放幾個?看標準差

這一步要解決的問題虛擬節點放幾個才夠平均?放多了要付什麼代價?

—標準差 ÷ 平均(越小越平均)—最忙那台是平均的幾倍—環上要記的位置數

📖 原書 虛擬節點越多,key 的分布越平衡,因為標準差變小。標準差衡量資料有多分散。

📖 原書 原書引用的線上實驗 [2]:一兩百個虛擬節點時,標準差介於平均值的 5%(200 個)到 10%(100 個)之間。虛擬節點再多,標準差更小。

📖 原書 但虛擬節點的資料要更多空間來存。這是取捨,可以依系統需求調整虛擬節點的數量。

左邊的模擬只計算每台分到的 hash space 比例,不是原書引用的那個實驗,所以數字不會完全一樣,趨勢一樣:數量變 4 倍,標準差大約減半。

白話:標準差見第 21 頁;「標準差是平均的 10%」=平均每台 10 個,各台大約差 1 個。

原書Find affected keys · Figure 14、15

哪些 key 要搬?從變動的那台往逆時針找

這一步要解決的問題加減一台時,要怎麼找出「哪一段」的 key 該搬?

📖 原書 Figure 14受影響範圍:從 s4 逆時針走到 s3,中間的 key 搬到 s4(依原書內容重繪)
📖 原書 Figure 15受影響範圍:從 s1 逆時針走到 s0,中間的 key 搬到 s2(依原書內容重繪;alt 寫箭頭從 k2 出發,依內文畫 key1)

📖 原書 server 加入或移除時,有一部分資料要重新分配。怎麼找出受影響的範圍?

📖 原書 加入(Figure 14):受影響範圍從 s4(新加的 node)開始,逆時針沿環走,直到遇到一台 server(s3)。所以 s3 和 s4 之間的 key 要重新分配到 s4。

📖 原書 移除(Figure 15):受影響範圍從 s1(被移除的 node)開始,逆時針走到遇到 server(s0)。所以 s0 和 s1 之間的 key 要重新分配到 s2。

文組翻譯

查找是順時針,找受影響範圍就反過來:站在新教室門口往回看,一路看到上一間為止,這段走廊上的同學以後改進新教室。

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

  1. 餘數 %
  2. hash
  3. sharding
  4. cache miss
  5. hash ring
  6. partition
  7. virtual node
  8. 標準差
  9. hotspot
  10. consistency
  11. scale up

到這裡你已經會了:原書的圓環

下一階要解決的問題

原書最後說這招還能「減輕 hotspot」、Dynamo 和 Cassandra 都在用。Triton 同意幾分?這招救不了什麼?

原書Wrap up

原書的收尾:三個好處、五個真實系統

這一步要解決的問題原書最後整理:這招好在哪?真實世界誰在用?

📖 原書 Consistent hashing 的好處

  1. 加減 server 時,要重新分配的 key 最少
  2. 資料分布比較平均,所以容易水平擴展
  3. 減輕 hotspot key 問題:某個 shard 被存取太多次會讓 server 過載。想像 Katy Perry、Justin Bieber、Lady Gaga 的資料全落在同一個 shard。Consistent hashing 把資料分得比較平均,有助減輕這個問題 Triton 的提醒見第 28 頁

白話:hotspot=大家都擠向同一台(第 27 頁);shard=分出來的其中一份。

📖 原書 真實世界的應用

  • Amazon Dynamo 資料庫的 partitioning 元件 [3]
  • Apache Cassandra 叢集的資料分區 [4]
  • Discord 聊天應用 [5]
  • Akamai CDN [6]
  • Maglev network load balancer [7]

白話:CDN=開在客人附近、放圖片影片的轉運站;load balancer=帶位員,把 request 分給各台。

原書最後一句:「恭喜你讀到這裡!給自己拍拍肩膀。」

原書的參考資料

  1. Wikipedia:Consistent hashing
  2. Tom White:Consistent Hashing(2007)
  3. Dynamo: Amazon’s Highly Available Key-value Store
  4. Cassandra - A Decentralized Structured Storage System
  5. How Discord Scaled Elixir to 5,000,000 Concurrent Users
  6. Stanford CS168 Lecture #1:Consistent Hashing
  7. Maglev: A Fast and Reliable Software Network Load Balancer

Triton 怎麼看大致同意:cache 一定要用 consistent hash

✅ 同意原書 「別使用 mod(md5(cacheKey), n)」

你猜猜看:用原書開頭的 hash % N。系統正忙,加開第 4 台 Redis,那一刻會出什麼事?

「別使用mod( md5(cacheKey), n )來決定某一 keyValue 位置 – n = 你的 redis server 總數 – 嘛,都 2018 年了。用這方法,當你系統繁忙要加開 redis 時, n的改動會讓你的 caching全滅。請學習 consistent hash – 其實 redis cluster內建了」🗣️ Triton 本人說 087-redis-2019.pdf.md · caching 常犯錯誤「沒使用 consistency hash」(086 2018 版同一頁)

「這時候 cache 全部 miss、全部改成打到 db 去……也就是說,不要自己算 hash。3台 redis 時、每台 33% 資料。加開一台 redis 時,理想是這3台各 8% 轉到第4台……當下會有 25% cache miss。如果機器是 20 台的話,就 5% 的 cache miss。」📝 上課筆記 029-Redis.md(無署名的 Redis 課堂筆記,口語粗話已略)

動手算:加開一台的那一刻,DB 吃多少?

hash % N:N 變 N+1,key 留在原位的機率只有 1/(N+1)

consistent hash:只有新那台的 1/(N+1) 要重新暖

和原書一樣,Triton 把它歸在「caching 常犯錯誤」,和 cache stampede、沒預熱、沒設 TTL 放在同一頁。他多強調一句:不要自己算 hash,用 Redis cluster 內建的。

白話:Redis=放在記憶體裡、大家共用的 cache 軟體;Redis cluster=好幾台 Redis 組成一隊;QPS=每秒幾個 request。

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

  1. 餘數 %
  2. hash
  3. sharding
  4. cache miss
  5. hash ring
  6. partition
  7. virtual node
  8. 標準差
  9. hotspot
  10. consistency
  11. scale up

開了 8 間教室,400 人卻全擠在同一間門口

① 先想像

考完試,全校都要看同一張成績公告。公告只貼在一間教室門口。每間門口最多站 100 人。

你猜猜看:開 8 間教室,400 人都要看那張公告。最擠的門口有幾人?

③ 這叫做 hotspot、hot key

hotspot:大家都擠向同一台,只有它被打爆。hot key:那一筆人人都要的資料。

④ 跟這章的關係

原書說 consistent hashing 能「減輕 hotspot」。Triton 的但書在下一頁。第 4 章第 30 頁也有一版。

② 動手玩:400 人,每個門口最多 100 人

Triton 補充原書的第三個好處要加一句但書

能分開三位巨星,分不開一位超級巨星

🔭 推論 原書說的沒錯:Katy Perry、Bieber、Gaga 三個 key 擠在同一個 shard,consistent hashing 加上虛擬節點能把它們分開。但如果一個 key 自己就超過一台的能力,加多少台都沒用。Triton 的處方是改資料結構:排行榜不要一個大 sorted set,改成每隻貓一個 key-value,「散落在redis cluster上的每一個node上(所以流量也會平均地分散到每一台redis上)」182;寫入熱點用 local buffering(第 4 章 Rate Limiter)。

你猜猜看:原書說 consistent hashing 能減輕 hotspot。如果一個 key 自己就有 3 萬 QPS,Redis 加到 16 台會怎樣?

「不管這世界有多少億正妹,老婆只能有一個。不管你的 redis cluster 有多少個 node,一份資料只能存於一台 redis 上。如果這份資料有 C100K 的流量,存了那份資料的 redis必當~ – 我們實戰經驗,單台的 redis 大約能支持 C10K」🗣️ Triton 本人說 086-redis-2018.pdf.md · 高流量下前言

「在 redis cluster,一份資料只存放在一個 node上……容易發生 hotspot,沒法以增加硬體手段解決」🗣️ Triton 本人說 087-redis-2019.pdf.md · Redis是 Single thread

Triton 自己怎麼用不只用在 cache 分片

Triton 的小技巧:讓同一個 gameId 總是打到同一台 AS

你猜猜看:帶位員依「第幾局遊戲」做 consistent hashing 分桌。有一台 AS 當掉,會怎樣?

「小技巧:提升 local cache hit rate。今天的 LB層,可以理解 Request的 URI(並且維持便宜)……LB層分派 Request的手段不是 random,而是基於 gameId的 Consistent hashing – 同一 gameId的 Request,就會被丟到同一台 AS上 – Consistent hashing不用把歷史存起來,不吃 Memory的 – 即使 AS 當掉, Request 自動丟到別的 AS上」🗣️ Triton 本人說 090-restful-demo.pdf.md · 線上 UNO 範例

這正是原書 wrap up 裡 Maglev(load balancer)那一類用法:hash 的對象不是 cache key,而是 request 要去哪台 application server。好處是同一局遊戲的狀態一直留在同一台 AS 的 local cache 裡。

🔭 依 Triton 原則推論 這三句各自對應原書哪一段

  • 「不用把歷史存起來,不吃 Memory」:位置用算的,不用查表,對應原書 server lookup(第 14 頁)
  • 「AS 當掉,Request 自動丟到別的 AS」:對應 remove a server,只有那台的 gameId 換家(第 15 頁)
  • 但 local cache 只是加速:遊戲狀態本身 Triton 存在 Redis 和資料庫(090 的出牌流程),換了 AS 只是 cache miss 一次,不會掉資料

📅 2026 補充 Redis cluster 的「內建」長什麼樣

Triton 說 consistent hash「redis cluster 內建了」。實際上 Redis Cluster 用的是固定 16384 個 hash slot:CRC16(key) mod 16384 決定 slot,slot 再分給各 node。分母固定不變,加 node 時只把一部分 slot 搬過去,效果和原書的環一樣:只搬一部分。用 {} hash tag 可以讓相關的 key 落在同一個 slot。

白話:LB(load balancer)=帶位員,見第 1 章第 12 頁;AS=application server,做事的電腦;URI=request 要去的網址;local cache=那台電腦自己記憶體裡的小抄。

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

  1. 餘數 %
  2. hash
  3. sharding
  4. cache miss
  5. hash ring
  6. partition
  7. virtual node
  8. 標準差
  9. hotspot
  10. consistency
  11. scale up

補考教室只剩 1 個座位,兩個窗口同時收人

① 先想像

補考報名有兩個窗口。為了快,每個窗口各拿一本帳,晚點再對帳。帳上寫著:剩 1 個座位。

你猜猜看:同一秒,兩個窗口各來一人。兩邊都看到「剩 1 個」,總共收了幾人?

③ 這叫做 consistency、atomic CAS

consistency:任何時候、任何人看到的數字都一樣。atomic CAS:「檢查還有沒有、有就扣掉」一口氣做完,中間沒人插隊。

④ 跟這章的關係

原書把 Cassandra 當例子。Triton 說它分區很好,但拿不到 atomic CAS(下一頁)。

② 動手玩:1 個座位、兩個窗口

Triton 補充Cassandra 用它,但 Triton 在意的是另一件事

加一個 node 只搬 1/N:對,但先問你要不要 consistency

你猜猜看:原書把 Cassandra 當 consistent hashing 的代表。用 Cassandra 寫售票系統,最後 1 張票兩人同時按「買」,會出什麼事?

📖 原書 Dynamo、Cassandra 用 consistent hashing 做分區

原書 wrap up 把 Dynamo、Cassandra 列為代表案例,重點放在「加減 node 時搬的資料最少」。

「根據 consistent hash,在 N個 node內加減一個 node時 – 每一個 data node需要搬動 1 / N的資料量。在資料經過 gossip轉移前,新的 node是沒有該份資料的。但是,基於 Quorum Consistency機制,少了一個 data node是不影響的,所以對 end user是 zero downtime的」🗣️ Triton 本人說 080-nosql-intro.pdf.md · 增減 Cassandra node

🗣️ Triton 本人說 同一份講義的下一頁

「Cassandra是AP向的 – 即是說:你一點也不介意 data consistency……你單用Cassandra是寫不出售票系統的」「現實上,毫不介意 consistency的商業應用很少的」080 · Cassandra 適用場景

對照 HBase:「每一個HBase node只負責特定 PK Range」,coordinator「儲存/管理 PK to node的mapping table」,加 node 時「在HBase node轉移的,只是責任範圍而不是資料本身」,所以「HBase才能做到Atomic CAS」。080 · HBase 架構、增加 HBase node

🔭 依 Triton 原則推論 Triton 沒有批評 consistent hashing 本身,他講 Cassandra 時也直接引用「1/N」。他在意的是同一個系統的另一個選擇:multi-master + quorum 讓你拿不到 atomic CAS。所以面試答「用 consistent hashing 分區」之後,下一句應該是「這份資料能不能接受 inconsistent」。HBase 的 PK range mapping table 是另一種分區方式,也只搬一部分,而且同一筆資料只有一個 owner。

延伸基礎 · 複習第 11 階 · scale up懂的人可以跳過

  1. 餘數 %
  2. hash
  3. sharding
  4. cache miss
  5. hash ring
  6. partition
  7. virtual node
  8. 標準差
  9. hotspot
  10. consistency
  11. scale up

教室坐不下:先換大禮堂,還是先分考場?

① 先想像

分考場很麻煩:要算誰去哪、要印准考證、換考場要搬人。換一間大禮堂,大家進去就好。

你猜猜看:120 人考試,學校最大的禮堂坐得下 400 人。要分考場嗎?

③ 這叫做 scale up、scale out

scale up:換一台更大、更強的機器。scale out:多開幾台分工(sharding 就是一種)。

④ 跟這章的關係

Triton:資料庫先 scale up 到頂,真的要切才走傳統 sharding。完整版見第 1 章第 11 頁。

② 動手玩:最大的禮堂坐 400 人

Triton 補充那資料庫要不要也這樣切?

資料庫:先 scale up,真的要切,走傳統 sharding

你猜猜看:原書把 Dynamo、Cassandra 當例子。你的資料庫變大了,Triton 的第一步是?

「主要還是一句:不能不見的data,我一定存到RDBMS」🗣️ Triton 本人說 106-喵 data.md

「如果是小型系統,單純scale up便算了。如果是大型系統,始終還是要走Hbase那些方向的……如果到了scale up盡頭又不想走Hbase那些noSQL,要RDBMS的clustering其中雷區冒險,我還不如走傳統的sharding路線」🗣️ Triton 本人說 106-喵 data.md

「正常沒亂來的系統,在20core + 200GB RAM的暴力機器下,絕大部份都沒需要玩clustering……除非你要面對C100K,何必自找麻煩做db clustering呢」🗣️ Triton 本人說 106-喵 data.md

🔭 依 Triton 原則推論 放回這一章

  • 原書這章是工具,沒有說什麼時候該用。Triton 的順序是:cache 層一開始多台就該用(第 26 頁);資料庫先把一台機器 scale up 到頂。
  • 106 沒有說傳統 sharding 要用 consistent hashing 還是別的分法,這裡不替他決定。能確定的是:他寧可自己掌握 shard 怎麼切,也不想踩 RDBMS clustering 的雷。
  • Cache 的 key 搬家只是 miss 一次,資料庫的資料搬家是真的要複製,還要保證搬的過程不掉、不錯(第 31 頁的 quorum 就是在處理這件事)。

文組翻譯

教室不夠,先換一間大教室(scale up)。大到全校最大的禮堂都坐不下,才分成好幾個考場(sharding)。分考場時,准考證上要印清楚你在哪一場,不要讓考生自己用公式算。

白話:RDBMS=傳統的關聯式資料庫(MySQL、PostgreSQL);clustering=讓好幾台資料庫假裝成一台;core=CPU 的核心數。

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

  1. 餘數 %
  2. hash
  3. sharding
  4. cache miss
  5. hash ring
  6. partition
  7. virtual node
  8. 標準差
  9. hotspot
  10. consistency
  11. scale up

到這裡你已經會了:Triton 的但書

11 階全部走完了

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

一句話記住

位置用自己的名字算,不要用總台數算;
但一個太熱的 key,誰也救不了。

原書的演算法

  • hash % N:N 一變,大部分 key 搬家
  • key 和 server 都上環,順時針找第一台
  • 加減一台只搬一段,逆時針找受影響範圍
  • 虛擬節點讓分布平均,代價是記憶體

Triton 同意的

  • 多台 Redis 別用 mod(md5(key), n)
  • 別自己算 hash,用 Redis cluster 內建的
  • Cassandra 加減 node 只搬 1/N
  • LB 用 gameId 做 consistent hashing 提高 local cache 命中

Triton 補上的但書

  • 一份資料只住一個 node:單一熱 key 加機器沒用
  • Cassandra 能分區,但拿不到 atomic CAS
  • 資料庫先 scale up,要切走傳統 sharding
  • 不能不見的資料放 RDBMS

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

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

% / modulo取餘數:繞圈數完,剩下的那一段
hash function把任何文字變成號碼的固定公式
hash 值算出來的號碼;同樣輸入永遠一樣
key一筆資料的名字(一位同學)
server存資料、做事的電腦(一間教室)
server pool、N這一群 server/總共幾台
sharding把資料依規則分給好幾台
cache放在手邊、拿得快的小抄,正本在 database
cache hit / miss小抄上有/沒有,只好去問正本
database(DB)正本所在的帳本,慢但不能錯(教務處)
rehashing problemN 一變,大部分 key 換了位置
a storm of cache misses大量 miss 同時湧向資料庫

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

引述來源(materials/core)

Triton 本人的講義 / 文章

  • 087-redis-2019.pdf.md — caching 常犯錯誤「沒使用 consistency hash」:別用 mod(md5(cacheKey), n)、caching 全滅、redis cluster 內建;一份資料只存一個 node、hotspot 沒法加硬體解決
  • 086-redis-2018.pdf.md — 同一頁的 2018 版;「老婆只能有一個」、單台 Redis 約 C10K
  • 029-Redis.md — 課堂紀錄:不要自己算 hash;3→4 台各轉 8%、25% miss;20 台 5%
  • 080-nosql-intro.pdf.md — Cassandra 加減 node 搬 1/N、quorum zero downtime、無法 atomic CAS;HBase PK range mapping table
  • 106-喵 data.md — 不能不見的 data 存 RDBMS、先 scale up、寧走傳統 sharding 不玩 RDBMS clustering
  • 090-restful-demo.pdf.md — LB 依 gameId 做 consistent hashing 提高 local cache hit rate
  • 182-資料結構很重要….md — 單一 sorted set 只住一台;改成 KV 散落各 node

沒有引用的:006-…喵_Redis.pdf.md(Roy 的筆記)也記了「33%,33%,33% each transfer 8% to new server」,和 029 同一段課,改引 029。011-…質數_bloomfilter 只有開頭兩句是 Triton(bloomfilter 的 m 直接寫質數 1000003),後面談 Redis Cluster 槽位、分片數用質數是 AI 生成的段落,不引用。

原書對照

Alex Xu, System Design Interview Vol.1 Ch.5。開場與 rehashing problem、Table 1–2(第 8 頁)、Figure 1–2(9)、定義與 hash ring、Figure 3–4(12)、Hash servers / keys、Figure 5–6(13)、Server lookup、Figure 7(14)、Add / Remove a server、Figure 8–9(15)、互動遊樂場(16)、Two issues、Figure 10–11(18)、Virtual nodes、Figure 12–13(20)與標準差(22)、Find affected keys、Figure 14–15(23)、Wrap up 與參考資料(25)。15 張圖都依原書的圖說與 alt 描述重繪,不是原圖;alt 與內文不一致處(Figure 9、12、15)以內文為準並在圖說註明。

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

學習地圖(第 3 頁);延伸基礎 11 階:餘數(4)、hash(5)、sharding(6)、cache miss(7)、hash ring(11)、partition(17)、virtual node(19)、標準差(21)、hotspot(27)、consistency(30)、scale up(32);小結(10、24、34);名詞小卡(36)。sharding、cache、scale up 的完整版在第 1 章(第 34、18、11 頁),hotspot 另見第 4 章第 30 頁。期末考是虛構的示範情境,人數、容量都是示意數字。

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

你的系統裡有沒有一行 hash(key) % servers.length?加開一台的那天,DB 撐得住嗎?

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