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

Design A Unique ID Generator
每一張號碼牌都不能重複

原書說 auto_increment 在分散式環境行不通,比較了四種做法,最後選 Twitter snowflake:把 64 bit 切成時間、機房、機器、序號。Triton 的看法剛好相反:auto-increment 本身不是瓶頸;真正的代價是 B+tree 右緣的搶鎖、讓對手猜出你的營業量,而且很多時候你根本不需要一個全域 ID。

給文組

全程用「銀行號碼牌」比喻,一階一階爬 11 個概念。頁首標 延伸基礎 的頁是補基礎,懂的人可以跳過。有二十多個可以動手玩的小模擬:自己組一個 snowflake ID、拆開它、用兩張訂單號碼猜對手一天賣幾單。

給工程師

第 8–20 頁完整講原書(7 張圖全部重繪),後面是 Triton 的批判與做法,最後一頁列出所有出處(materials/core)。

標籤怎麼看

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

先用生活理解銀行號碼牌

四種發號碼牌的方法,哪一種最好?

銀行要發號碼牌:號碼不能重複,最好晚到的人號碼比較大,而且客人很多的時候不能讓大家排隊等一台取號機。

  • 一台取號機:最簡單,但機器壞了全部人都拿不到號(原書的 Ticket server)
  • 兩台取號機,一台只發單號、一台只發雙號(Multi-master)
  • 每個櫃台自己擲骰子,擲出一串很長的亂碼(UUID)
  • 「現在幾點幾分 + 櫃台編號 + 這一分鐘的第幾號」(Snowflake)

右邊每按一次就來一位客人,客人會隨機走到某個櫃台。看看哪一種方法會讓號碼順序和到達順序對不上。

學習地圖本章的概念階梯

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

  1. 1PK不重複的號碼牌
  2. 2bit開關燈泡
  3. 3timestamp從某天開始數
  4. 4SPOF一台壞全部停
  5. 5UUID超大的骰子
  6. 6transaction一筆手續
  7. 7hot spot搶同一支筆
  8. 8B+tree分頁的電話簿
  9. 9contention擠在最後一頁
  10. 10heap / IOT倉庫 vs 圖書館
  11. 11natural key本來就有的名字

第 1–3 階 · 號碼牌是什麼做的

要回答:「64 bit、依時間排序」是什麼意思?

第 4–5 階 · 好幾台取號機

要回答:原書四種做法差在哪?為什麼選 snowflake?

第 6–8 階 · 走進資料庫

要回答:auto-increment 真的是瓶頸嗎?

第 9–11 階 · Triton 的答案

要回答:真正的代價在哪?真的需要 ID 產生器嗎?

全程只用一家銀行:喵喵銀行(虛構)

號碼牌 = ID取號機 = ID generator櫃台 = server分行 = data center登記簿 = database辦一筆手續 = transaction

數學只用三樣:數燈泡、乘以 2、加減心算。每爬 3 階左右,有一頁「到這裡你已經會了」。

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

  1. PK
  2. bit
  3. timestamp
  4. SPOF
  5. UUID
  6. transaction
  7. hot spot
  8. B+tree
  9. contention
  10. heap / IOT
  11. natural key

兩位客人都叫「王小明」,叫號時誰站起來?

① 先想像

銀行把每位客人寫進登記簿,一列一個人。叫號時,櫃台只喊第一欄。

你猜猜看:第一欄寫名字,今天來了兩位「王小明」。叫「王小明」時會怎樣?

③ 這叫做 ID、primary key(PK)

ID:用來認出一筆資料的號碼。PK:登記簿第一欄那個「絕對不能重複」的號碼。

④ 跟這章的關係

這章要設計的,就是「誰來發這個號碼、怎麼保證不重複」。登記簿就是 database(第 1 章簡報第 8 頁)。

② 動手玩:登記簿的第一欄

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

  1. PK
  2. bit
  3. timestamp
  4. SPOF
  5. UUID
  6. transaction
  7. hot spot
  8. B+tree
  9. contention
  10. heap / IOT
  11. natural key

「64 bit」是什麼?先數一排燈泡

① 先想像

一排燈泡,每顆只有亮、暗兩種。把亮暗的組合當成號碼。

你猜猜看:5 顆燈泡,最多排得出幾種不同的亮法?

③ 這叫做 bit、2 的次方

bit:一顆燈泡,暗是 0、亮是 1。n 顆燈泡有 2 × 2 × … × 2(n 個 2)種,寫成 2n,叫「2 的 n 次方」。

④ 跟這章的關係

原書規定 ID 只能用 64 顆燈泡(64 bit)。5 顆 = 32 種、12 顆 = 4,096 種,這兩個數字等一下都會出現。

② 動手玩:點燈泡開關

0這排燈泡代表的號碼32總共幾種亮法

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

  1. PK
  2. bit
  3. timestamp
  4. SPOF
  5. UUID
  6. transaction
  7. hot spot
  8. B+tree
  9. contention
  10. heap / IOT
  11. natural key

「現在幾點」也可以寫成一個數字

① 先想像

喵喵銀行開幕那一刻,牆上的計數器從 0 開始,每過一秒 +1,從來不歸零。

你猜猜看:計數器顯示 3,600,是開幕後多久?

③ 這叫做 timestamp、epoch

timestamp:從某一天開始數的秒數(或毫秒數)。epoch:開始數的那一刻,就是「開幕那一刻」。

④ 跟這章的關係

數字越大=越晚,所以拿它當開頭的號碼,會自動照時間排好。snowflake 數的是毫秒(千分之一秒)。

② 動手玩:牆上的計數器

0

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

  1. PK
  2. bit
  3. timestamp
  4. SPOF
  5. UUID
  6. transaction
  7. hot spot
  8. B+tree
  9. contention
  10. heap / IOT
  11. natural key

到這裡你已經會了:號碼牌是什麼做的

下一階要解決的問題

面試官要的號碼牌:不能重複、64 顆燈泡、照時間排、每秒 10,000 張。先看原書面試一開始問了什麼。

原書 Step 1開場 · 釐清需求 · Figure 1

面試一開始:ID 要長什麼樣子?

這一步要解決的問題號碼要多長、要不要照時間排、一秒要發幾張?沒問清楚,四種做法都可能選錯。

📖 原書 你第一個想法可能是傳統資料庫的 auto_increment 主鍵。但原書說它在分散式環境行不通:單一資料庫伺服器規模不夠,而要在多個資料庫之間以最小延遲產生唯一 ID 很有挑戰。🗣️ Triton 不同意,見第 24 頁

📖 原書 應徵者 × 面試官

應徵者問面試官答
唯一 ID 有哪些特性?必須唯一且可排序
每筆新紀錄的 ID 是否遞增 1?ID 以時間遞增,但不一定只加 1。同一天晚上產生的 ID 比早上的大
ID 是否只包含數值?是
ID 的長度需求?要能放進 64 bit
系統規模多大?每秒能產生 10,000 個 ID

白話:auto_increment=登記簿自動 +1 的號碼;分散式=好幾台電腦一起做(第 9 頁);64 bit=64 顆燈泡(第 5 頁);可排序=號碼大小就是先後。

📖 原書 需求清單

  1. ID 必須唯一
  2. ID 只有數值
  3. ID 放得進 64 bit
  4. ID 依日期排序
  5. 每秒能產生超過 10,000 個唯一 ID

文組換算:每秒 10,000 個 = 每毫秒 10 個。記住這個數字,第 18 頁會用到。

📖 原書 Figure 1唯一 ID 的例子:一欄 user_id(依原書內容重繪;描述沒給數字,這裡用示意值)

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

  1. PK
  2. bit
  3. timestamp
  4. SPOF
  5. UUID
  6. transaction
  7. hot spot
  8. B+tree
  9. contention
  10. heap / IOT
  11. natural key

一台取號機壞了,整間銀行會怎樣?

① 先想像

喵喵銀行門口只有一台取號機。客人越來越多,分行想再多放一台。

你猜猜看:兩台取號機都從 1 號開始發,彼此不講話。會怎樣?

③ 這叫做 distributed、SPOF

distributed(分散式):好幾台機器一起做同一件事。SPOF(single point of failure):只有一個、它一壞全部停的那一點。

④ 跟這章的關係

原書的四種做法,就是在「不撞號」和「不怕壞」之間取捨。沒有 SPOF、壞了會自己恢復,叫 HA(第 2 章簡報第 17 頁)。

② 動手玩:取號機要放幾台?

原書 Step 2四種做法之 1 · Multi-master replication · Figure 2

兩台 MySQL,一台發單號、一台發雙號

這一步要解決的問題一台取號機是 SPOF,那就放好幾台。怎麼讓它們發的號碼不撞?

📖 原書 Step 2 考慮四種做法:Multi-master replication、UUID、Ticket server、Twitter snowflake。第一種用資料庫的 auto_increment,但每次不是加 1,而是加 k(k = 使用中的資料庫台數)。Figure 2 裡 k = 2:同一台的下一個 ID = 上一個 + 2。ID 數量可以隨資料庫台數擴展。

📖 原書 Figure 2兩台 MySQL,各自以 +2 遞增(依原書內容重繪)

白話:MySQL=一種常見的 database;replication=把資料抄到好幾台(第 1 章簡報第 14 頁);multi-master=每一台都能寫;web server=接待客人的櫃台電腦。

動手玩:k 台資料庫,每台 +k

📖 原書 三個主要缺點

  • 難以擴展到多個資料中心
  • 跨多台 server 的 ID 不會隨時間遞增
  • 新增或移除 server 時擴展性不佳

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

  1. PK
  2. bit
  3. timestamp
  4. SPOF
  5. UUID
  6. transaction
  7. hot spot
  8. B+tree
  9. contention
  10. heap / IOT
  11. natural key

不用講好,各自擲骰子,會撞號嗎?

① 先想像

不想讓取號機互相講話?那每個櫃台自己擲骰子,擲出幾點就是幾號。

你猜猜看:班上 23 個人,至少兩人同一天生日的機率大約是?

③ 這叫做 UUID、collision

UUID:每台機器自己擲的「超大骰子」,約有 2122 面。collision:兩次擲出一樣的號碼,就是撞號。

④ 跟這章的關係

原書第 2 種做法就是它。面數夠大,撞號機率就小到可以不管(下一頁算給你看)。

② 動手玩:生日問題

253可以湊出幾對50.7%至少一對撞號的機率

原書 Step 2四種做法之 2 · UUID · Figure 3

每台 web server 自己擲一個 128 bit 的骰子

這一步要解決的問題不想讓機器互相講話,就各自擲骰子。號碼夠不夠短、會不會撞、有沒有照時間?

📖 原書 UUID 是 128 bit 的數字,碰撞機率非常低。原書引用維基百科:「在大約 100 年內每秒生成 10 億個 UUID,產生單一重複的機率才會達到 50%」。例子:09c93e62-50b4-468d-bf8a-c07e1040bfb2。UUID 可以各自產生、不需要 server 之間協調。

📖 原書 Figure 3每台 web server 內建一個 ID generator,各自獨立(依原書內容重繪)

📖 優點

  • 產生很簡單,不用協調,沒有同步問題
  • 好擴展:每台 web server 自己產生自己要用的 ID

📖 缺點

  • 128 bit,需求是 64 bit
  • ID 不會隨時間遞增
  • ID 可能不是純數字

動手玩:擲一個 UUID

撞號機率計算機

用 v4 的 122 個隨機位元、生日問題近似:p ≈ 1 − e−n²/2123

🗣️ Triton「在 1T個UUIDv4 之中,出現相橦的可能性大約是 9.4e-14」070 · Surrogate key 缺點

原書 Step 2四種做法之 3 · Ticket server · Figure 4

所有人都去同一台取號機拿號碼

這一步要解決的問題回到最簡單的:大家都去同一台取號機。它好在哪、怕什麼?

📖 原書 Figure 4四台 web server 都向同一台 Ticket Server 要 ID(依原書內容重繪)

📅 補充 原書參考資料 [2] 是 Flickr 2010 年的文章,原文就是用兩台 ticket server,一台發單號、一台發雙號,和第 10 頁的 multi-master 是同一招。原書內文沒有寫這段。

📖 原書 Ticket server 是 Flickr 開發來產生分散式 primary key 的。概念是在單一資料庫伺服器(Ticket Server)上用集中式的 auto_increment。

白話:Flickr=照片分享網站;primary key=第 4 頁的 PK;集中式=全部集中在一台。

📖 優點

  • 數字型 ID
  • 實作簡單,適用於中小型應用

📖 缺點:Single point of failure

Ticket server 當機,所有依賴它的系統都會出問題。要避免 SPOF 可以設置多台 ticket server,但會帶來資料同步等新挑戰。

原書 Step 2為什麼前三種都不行

對著需求清單打勾:原書說前三種都不合格

這一步要解決的問題三種都看完了。拿需求清單一條一條對,有沒有哪一種全部打勾?

點欄位標題可以單獨看某一種做法。格子只填原書明確寫到的優缺點,原書沒提的留「—」。

需求
唯一✓✓ 機率極低才撞✓✓
只有數值—✗ 可能不是數字✓ 數字型✓
64 bit—✗ 128 bit—✓ 1+41+5+5+12
依時間排序✗ 跨 server 不遞增✗—✓ 時間戳在最前面
擴展性△ 隨台數擴展,但增減台數、多資料中心都難✓ 隨 web server 擴展△ 適合中小型✓ 分散式環境可擴展
不需協調 / 無 SPOF—✓ 不用協調✗ SPOF✓ 各機器自己產生

📖 原書 「上述方法讓我們了解不同 ID 產生系統的運作方式,但都無法滿足我們的特定需求」。Twitter 的 snowflake 有啟發性,而且能滿足需求。

「Divide and conquer is our friend.」📖 原書:不直接產生一個 ID,而是把 ID 切成不同區段

文組翻譯

一台取號機會壞、單雙號湊不成時間順序、擲骰子號碼太長又亂。最後的答案是把號碼牌印成幾格:第一格是時間、第二格是分行、第三格是櫃台、最後一格是這一毫秒的第幾號。每個櫃台只要看手錶、數自己的人,完全不用問別人。

🔭 先劇透 這張表的每一列都是面試官給的需求。Triton 會先問:「依時間排序」這一條,真的是好事嗎?(第 31 頁)

原書 Step 2四種做法之 4 · Twitter snowflake · Figure 5

把 64 bit 切成五格

這一步要解決的問題不擲骰子、也不問別人,號碼怎麼又短又照時間排?把 64 顆燈泡分成五格。

📖 原書 Figure 564 bit ID 的配置(依原書內容重繪;alt 描述把中間兩格標成「0」和「timestamp...」,與內文不符,這裡以內文的區段名稱為準)

📖 Sign bit · 1

永遠是 0,保留給未來用;可能用來區分有號與無號數字。

📖 Timestamp · 41

自 epoch 或自訂 epoch 起的毫秒數。用 Twitter 預設 epoch 1288834974657 = 2010/11/04 01:42:54 UTC。

📖 Datacenter ID · 5

25 = 32 個資料中心。

📖 Machine ID · 5

每個資料中心 25 = 32 台機器。

📖 Sequence · 12

同一台機器/process 每產生一個 ID 就 +1,每毫秒重置為 0。

原書 Step 3Design deep dive · Figure 6 · 動手組一個 ID

datacenter 和 machine 開機時決定,時間和序號邊跑邊產生

這一步要解決的問題五格裡,哪幾格事先貼在櫃台上、哪幾格要邊跑邊算?

📖 原書 Figure 6深入設計時重列的同一張配置圖(依原書內容重繪;區段名稱依內文)

📖 原書 決定採用 Twitter snowflake 的做法。Datacenter ID 和 machine ID 在啟動時選定,系統跑起來後通常固定。任何更動都要謹慎審查,因為不小心改到可能造成 ID 衝突。Timestamp 和 sequence number 則是 ID 產生器執行時產生的。

白話:datacenter=機房,像分行;machine=機房裡的一台電腦,像櫃台;ID 衝突=撞號(第 11 頁的 collision)。

文組翻譯

分行代號、櫃台代號是開門前就貼在櫃台上的;時間看手錶,序號自己數。兩個櫃台不小心貼了同一個代號,就會在同一毫秒發出一模一樣的號碼牌。

原書 Step 3Timestamp · Figure 7

41 bit 的毫秒數,可以用 69 年

這一步要解決的問題最大的一格是時間。41 顆燈泡能數多少毫秒、用多少年?

📖 原書 Figure 7從二進位到 UTC(依原書內容重繪)

📖 原書 最重要的 41 bit 是 timestamp。時間一直往前,所以 ID 可以依時間排序。反過來也能用同樣方法把 UTC 轉回二進位。

📖 原書 為什麼是 69 年

2^41 − 1 = 2199023255551 ms
÷ 1000 ÷ 365 ÷ 24 ÷ 3600 ≈ 69 年

把自訂 epoch 設在接近今天,可以延後溢位。69 年後要換新的 epoch,或用其他技術遷移 ID。

動手玩:貼一個 ID 拆開來

原書 Step 3Sequence number

一台機器一毫秒最多 4,096 個

這一步要解決的問題同一台機器、同一毫秒來了好幾個人,怎麼分?最多分得了幾個?

📅 補充 原書只說「理論上最多 4096」,沒說第 4097 個怎麼辦。Twitter 開源的原始實作是等到下一毫秒再發,滑桿超過 4096 就是在演這件事。

📖 原書 Sequence number 12 bit,212 = 4096 種組合。除非同一台 server 在同一毫秒產生超過一個 ID,否則這一格是 0。理論上一台機器每毫秒最多支援 4096 個新 ID。

回頭對需求算一下

  • 需求:每秒 10,000 個 = 每毫秒 10 個
  • 一台機器:每毫秒 4,096 個 = 每秒 4,096,000 個
  • 32 × 32 = 1,024 台:每秒約 42 億個

原書的需求一台機器就夠了,只用了 sequence 的 0.24%。

🔭 推論 一台機器就夠,那「分散式」是為了什麼?為了不要有 SPOF(多台一起跑),而不是為了吞吐量。Triton 一再講的「先知道 N」在這裡很好用(126、064)。

原書 Step 4Wrap up · 討論點 1:時鐘同步

如果兩台機器的手錶不一樣快?

這一步要解決的問題每台機器都看自己的手錶。手錶不準、甚至倒退的時候會怎樣?

📖 原書 本章討論了 multi-master replication、UUID、ticket server、類 Twitter snowflake 四種做法,最後選 snowflake,因為它支援所有使用案例,在分散式環境中可擴展。面試還有時間的話,可以再談三個點:

📖 1. Clock synchronization

我們假設 ID 產生 server 的時鐘一致。但 server 跑在多核心上時這個假設可能不成立,多台機器也一樣。時鐘同步的解法不在本書範圍,但要知道這個問題存在。最流行的解法是 Network Time Protocol(NTP)。

白話:多核心=一台電腦裡有好幾個大腦同時做事;NTP=電腦上網對時的方法;時鐘倒退=NTP 發現手錶快了,把它往回撥。

另外兩點 section length tuning 和 high availability 在下一頁。

📅 補充 Twitter 的原始 snowflake 實作遇到「時鐘倒退」會直接拒絕產生 ID,等時間追上上一次的時間戳才恢復,就是為了避免右邊示範的重複。

依 ID 排序之後的順序(數字是真實發生的先後):

原書 Step 4討論點 2、3:Section length tuning · High availability

五格的寬度可以自己調

這一步要解決的問題五格一定要 41 / 5 / 5 / 12 嗎?還有,取號機本身壞了怎麼辦?

📖 原書 例如:sequence 少一點、timestamp 多一點,適合低併發、長期運行的應用。下面的 sign bit 固定 1 位,剩下 63 位自己分。

範例:

📖 3. High availability

ID 產生器是關鍵任務系統(mission-critical),所以必須高可用。

原書就寫到這裡,沒說怎麼做。Triton 對 HA 的定義見第 39 頁。

白話:mission-critical=它一停,整個公司跟著停;高可用(HA)=沒有 SPOF、壞了自己恢復(第 9 頁)。

文組翻譯

號碼牌的長度是固定的(64 格)。「時間」那格寫得越細越久,能用的年數越多;「櫃台代號」那格越長,能開越多櫃台;「序號」那格越長,同一毫秒能發越多張。一格變長,另一格就得變短。

原書最後:「恭喜你已經走到這裡!現在給自己一個讚。做得好!」接下來換 Triton。

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

  1. PK
  2. bit
  3. timestamp
  4. SPOF
  5. UUID
  6. transaction
  7. hot spot
  8. B+tree
  9. contention
  10. heap / IOT
  11. natural key

到這裡你已經會了:原書的完整設計

下一階要解決的問題

原書一開頭說「auto_increment 在分散式行不通」。Triton 不同意。要聽懂他,先學資料庫裡的「一筆手續」和「搶同一支筆」。

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

  1. PK
  2. bit
  3. timestamp
  4. SPOF
  5. UUID
  6. transaction
  7. hot spot
  8. B+tree
  9. contention
  10. heap / IOT
  11. natural key

轉帳辦到一半停電,錢會不見嗎?

① 先想像

轉帳 100 元有兩步:你的帳戶扣 100、對方的帳戶加 100。銀行保證兩步要嘛都做完,要嘛都沒發生。

你猜猜看:扣完你的 100、還沒加給對方就停電。重開機後你的帳戶?

③ 這叫做 transaction(TX)、commit / rollback

TX:一筆「全做或全不做」的手續。commit:簽名,正式生效;反悔、整筆作廢叫 rollback。

④ 跟這章的關係

資料庫裡每一筆 insert(新增一列)都在 TX 裡。Triton 的第一個論點:拿 auto-increment 號碼這一步,不包在 TX 裡(第 25 頁)。

② 動手玩:轉帳 100 元

延伸基礎第 7 階 · hot spot懂的人可以跳過

  1. PK
  2. bit
  3. timestamp
  4. SPOF
  5. UUID
  6. transaction
  7. hot spot
  8. B+tree
  9. contention
  10. heap / IOT
  11. natural key

8 個人要寫登記簿,只有一支筆

① 先想像

登記簿綁著一支筆。拿到筆的人寫,其他人在旁邊等;寫完、放下筆,下一位才能拿。

你猜猜看:8 個人,每人寫 1 分鐘,只有一支筆。最後一個人寫完是第幾分鐘?

③ 這叫做 lock、hot spot

lock:「筆在我手上,別人先等」,等的狀態叫 blocking。hot spot:大家都擠著搶同一個東西,別的地方再空也沒用。

④ 跟這章的關係

auto-increment 只有一個數字,上千筆 insert 都要拿它,聽起來就是 hot spot。Triton 說:其實不是(下兩頁)。

② 動手玩:幾支筆?

—最後一人寫完—大家加起來等了多久

Triton 不同意直球

❌ 原書 「auto_increment 在分散式環境行不通」

📖 原書 單一資料庫撐不住

auto_increment 在分散式環境無法運作,因為單一資料庫伺服器的規模不足,而且在多個資料庫間以最小延遲產生唯一 ID 很有挑戰。

言下之意:只有一個數字、大家都要來搶,一定是瓶頸。

你猜猜看:MySQL 宣稱每秒上百萬筆 insert,每一筆都要拿 auto-increment 的下一號。原書說這個數字是瓶頸,對嗎?

🗣️ Triton 本人說 先想一個很基本的問題

「大家看MySQL,他們的Insert都是宣稱能每秒以百萬級來算的。」「要做到每秒百萬級的Insert,一定是同時打開上千個的資料庫連線,然後每一個連線不停地跑 Insert指令的。」

「Auto-Increment只有一個數值,怎能讓上千個transaction同一時間改動,但是不會發生hot-spot問題讓效能卡住?」

010-喵談 RDBMS PK Auto-Increment(Roy 的 Notion 轉貼 Triton 原文)

答案預告:兩個原因

  1. 拿號碼不包在 transaction 裡,所以 TX 之間不會互相等
  2. 資料庫一次預先配一疊號碼,不用每拿一個就寫一次硬碟

那真正的問題在哪?

「auto-increment的效能隱憂不在auto-increment本身,而是在於你的records怎麼存到HDD上的問題」🗣️ Triton 本人說 010 · 回覆學員提問

Triton 的解釋為什麼 auto-increment 不是瓶頸

號碼拿了就不還,而且一次預訂 20 個

你猜猜看:TX A 拿到 101 號,後來 rollback 反悔了。下一個 TX 會拿到 101 嗎?

「Auto-Increment的改動是不被包在TX內的。如果現在的Auto-increment數值是100,你打開了TX做Insert但是不commit,之後的TX拿到的只會是101而不會是100。」「正正因為Auto-Increment的改動是不被包在TX內,所以才不會因為Auto-Increment而發生TX之間的blocking問題。」🗣️ Triton 本人說 010 · 原因 1

「所以RDBMS是每次要改動HDD內的auto-increment數值時,都是一次地跳動20個號碼的。比如說你現在要拿第101個,RDBMS便會把HDD上的auto-increment改成120。」「當然嘛,如果現在系統當掉,RDBMS需要重新啟動時,即使auto-increment便會直接從121開始……」🗣️ Triton 本人說 010 · 原因 2

🔭 「20」是 Triton 舉的例子;實際一次預訂多少,各家資料庫與設定不同。

TX A
TX B
101記憶體:下一個號碼100硬碟:已預訂到0為號碼寫硬碟次數

Triton 補充真的要連號怎麼辦

要「完全不跳號」,就得付出 hot spot 的代價

「auto-increment沒法保證你的PK是從1開始,中間完全不會跳號碼。如果你的商業邏輯一定一定需要一個完全不會跳號碼的順序,你需要另外建一個table,去存你需要的流水號。(每一個流水號為一個row)」
「只是這麼做,幾乎肯定這個存流水號的table會成為hot spot,不同TX必須為了改動這個流水號而發生blocking,非常大幅地影響到效能。」🗣️ Triton 本人說 010 · 簡單來說

「先說一下:RDBMS的Serializable不等於數學上的Serializable – Auto increment, sequence不被包括到TX」🗣️ Triton 本人說 069-lesson1 · 基於 SX lock 的 Serializable

文組翻譯:號碼牌如果規定「絕對不能跳號」,那每個客人都要等前一個客人真的辦完手續才能拿下一號;前一個人反悔走掉,號碼還得收回來重發。整間銀行變成一次只能服務一個人。

你猜猜看:老闆規定訂單號碼「絕對不能跳號」。同時 8 筆手續要拿號,會怎樣?

延伸基礎第 8 階 · B+tree懂的人可以跳過

  1. PK
  2. bit
  3. timestamp
  4. SPOF
  5. UUID
  6. transaction
  7. hot spot
  8. B+tree
  9. contention
  10. heap / IOT
  11. natural key

電話簿為什麼要分頁、照順序排?

① 先想像

一本電話簿照號碼排好,每頁只寫得下 4 個人。要找 33 號,先看最前面的目錄「27–41 在第 2 頁」,直接翻過去。

你猜猜看:第 3 頁有一個人改了電話,影印店要重印多少?

③ 這叫做 index、B+tree

index:照順序排好、讓你直接翻到那一頁的目錄。B+tree:資料庫的 index;上層是目錄,最底層一頁一頁裝資料(leaf page,一頁 8KB)。

④ 跟這章的關係

資料庫用 PK 排這本電話簿。新號碼插在哪一頁,決定大家擠不擠(下一階)。

② 動手玩:電話簿每頁寫 4 個號碼

4資料頁數—這次改到哪一頁

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

  1. PK
  2. bit
  3. timestamp
  4. SPOF
  5. UUID
  6. transaction
  7. hot spot
  8. B+tree
  9. contention
  10. heap / IOT
  11. natural key

到這裡你已經會了:auto-increment 不是瓶頸

下一階要解決的問題

號碼一直變大,新資料都插在 B+tree 的哪一頁?Triton 說,真正的代價在這裡。

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

  1. PK
  2. bit
  3. timestamp
  4. SPOF
  5. UUID
  6. transaction
  7. hot spot
  8. B+tree
  9. contention
  10. heap / IOT
  11. natural key

號碼一直變大,今天的客人都寫在哪一頁?

① 先想像

登記簿照號碼排。號碼牌一張比一張大,所以今天來的每位客人,都接在最後面。

你猜猜看:登記簿有 6 頁。早上 12 位客人同時來登記,會寫在幾頁上?

③ 這叫做 Monotonic Increasing、contention

Monotonic Increasing(MI):大致一直往上的數字,例如號碼牌、時間、日期。contention:很多人同時要改同一個地方,只好互相等。

④ 跟這章的關係

auto-increment 是 MI。原書的 snowflake 把時間放最前面,所以它也是(第 31 頁)。

② 動手玩:12 位客人同時來登記

—最擠那一頁同時幾人—用到幾頁

Triton:真正的代價 1B+tree 的右邊

所有新資料都擠在 index 最右邊那一頁

你猜猜看:PK 用 auto-increment,同時來 24 筆 insert。會改到 B+tree 的幾頁?

「auto-inc insert在PK的B+ tree index中,只會動到最右邊的那個leaf node。然後uuidV4 insert,是會隨機的改動到PK B+tree的任一leaf node。」「別忘記一點:即使你的8KB leaf node只改動其中一byte也好,也是需要整個8KB node都抄到REDO log的。」🗣️ Triton 094 · auto-inc 為何 benchmark 比較快

「越近期被加入database的資料,就越有可能被拿出來改動。用auto-inc下,所有近期的資料全在PK-index的右邊,所以右邊忙死然後左邊空閒。這讓data contention更有可能發生」「到最後就是:整個database明明有大量的CPU thread可以用,但就看起來是single thread在跑一樣。」🗣️ Triton 094 · 現實上

0被改到的 8KB page(要抄進 REDO log)0最擠的那頁同時有幾個 TX

Triton 原則推論原書的 snowflake 也逃不掉

「依時間排序」的 snowflake,一樣擠在最右邊

你猜猜看:原書把 auto_increment 換成 snowflake,時間放在最前面。存進資料庫的 B+tree,新資料會落在哪?

哪些號碼是 MI?

  • auto-increment、timestamp、日期:是(070 的例子)
  • snowflake:時間在最高位,也是 🔭 推論
  • UUID v4:隨機,不是;但每次改到的頁比較分散(094)
  • UUIDv7:時間在最前面,是(第 41 頁)

「Monotonic Increasing:就是說(大致上)持續上升的數值。例子:auto increment,timestamp,日期」「MI PK 問題:同一時期的 record,集中在 PK index的最右邊」🗣️ Triton 070-lesson2 · Monotonic Increasing PK

🔭 依 Triton 原則推論 原書要求「ID 依時間排序」,snowflake 把 timestamp 放在最高位,所以它就是 070 說的 Monotonic Increasing。存進一台資料庫的 B+tree,它跟 auto-increment 一樣擠在最右邊。原書換掉了 auto_increment,卻保留了它真正的代價。Triton 的資料裡沒有直接評論 snowflake。

Triton:跑分不等於上線benchmark vs 現實

100 FPS 偶爾黑畫面,還是 80 FPS 穩穩跑?

你猜猜看:跑分(benchmark)時 auto-increment 比 UUID 快、寫硬碟比較少。上線之後也一定比較快嗎?

顯示卡 A ≈ auto-inc、B ≈ UUID

「benchmarking和現實世界不完全相同的。」「你是寧可80FPS穩穩跑?還是寧可100FPS爽爽跑,但有時會黑畫面???」「用多了io嘛,就拿dxxxxxg數據跟老闆申請加大機器硬體就好。data contention嘛,你是除了被老闆罵,其實你是沒什麼東西能真正做的。」🗣️ Triton 本人說 094-triton 談 pg index uuid 與 auto-inc

文組翻譯

IO 多(多寫幾次硬碟),買大一點的機器就解決了;contention(大家擠同一頁),買再多機器也還是在排隊。Triton 選穩定的那一張顯示卡。

白話:benchmark=跑分;FPS=遊戲每秒畫幾張圖,0 就是黑畫面;IO=讀寫硬碟。

延伸基礎第 10 階 · heap / IOT懂的人可以跳過

  1. PK
  2. bit
  3. timestamp
  4. SPOF
  5. UUID
  6. transaction
  7. hot spot
  8. B+tree
  9. contention
  10. heap / IOT
  11. natural key

書要照號碼上架,還是有空位就放?

① 先想像

圖書館的書照號碼排在架上,旁邊就是下一號。倉庫則是有空位就放,另外用一盒目錄卡記「幾號在哪一格」。

你猜猜看:倉庫裡,3 號和 4 號書會放在同一格架上嗎?

③ 這叫做 heap table、IOT

heap table:倉庫,資料有空位就放,另外用 index 找。IOT(index-organized table):圖書館,資料本身就照 PK 排在 B+tree 裡。

④ 跟這章的關係

PostgreSQL 是倉庫,MySQL(InnoDB)是圖書館。所以兩邊的人選 PK 的習慣不一樣(下兩頁)。

② 動手玩:放 8 本書,再找 3–6 號

Triton:資料庫決定答案PostgreSQL vs MySQL

PostgreSQL 的人偏 UUID,MySQL 的人偏 auto-increment

你猜猜看:PostgreSQL 是倉庫(heap),MySQL 是圖書館(IOT)。哪一邊的人比較習慣用 auto-increment 當 PK?

文組翻譯

倉庫(PG):資料本身不擠,但目錄卡的最後一張還是大家搶(070)。圖書館(MySQL):資料就是目錄,auto-increment 讓新書全上同一格架(094 的右緣)。沒有一種 PK 到哪裡都對,要看資料庫怎麼放資料。

📝 上課筆記 非 Triton 原文

「Mysql 的 PK 大部分都會 用 auto increment id postgrs 的 PK UUId 因為 heap」009 「postgres oracle 底層是不會跟 physical ordering 有關 但 Dynamodb 與 mysql 底層PK 跟physical ordering 有關」「SSD 真的讚 所以今天談到 DB 效能瓶頸都卡在 lock 上」058

🗣️ Triton 本人說 看你用哪一種資料庫

  • 「這會影響到你的PrimaryKey是用UUID還是Auto Increment(前者postgresql,後者MySQL)」060
  • 「為何MySQL / MSSQL的人喜歡用auto-increment?為何oracle / postgreSQL的人喜歡用natural key / UUID?這都是其內部的data structure的不同所引起的結果」132
  • 「postgresql是希望「同一時間能做盡量多的事務」(a.k.a. 迴避data contention)」094
  • Heap table:「即使PK是用上auto-increment,相近PK的 row會散落到整個heap之內」;但「近期新增加的Record的 PK全集中在 PK index的最右邊,引發 index page contention – 在Oracle,這問題非常致命 (呃,在 postgreSQL也很致命的 )」070

Triton:真正的代價 2安全篇

兩張訂單號碼,就能猜出對手一天賣幾單

你猜猜看:早上去對手的店買一杯飲料,收據上是 #10234;晚上再買一杯,是 #13874。你知道了什麼?

🗣️ Triton 本人說 後端自我檢測

效能篇「14 你知道auto-increment在系統效能的隱憂嗎?」

安全篇「15 你知道使用auto-increment,但又不讓競爭對手猜到你的業務量的方法嗎?」

113-喵的 backend 測驗(20 題,Triton 說回答 < 5 分的別自稱 fullstack)

🔭 推論 113 只出題、沒給答案。可用的工具在 Triton 別的講義裡:012 的「2-way bit shuffling,讓本來相鄰的 PK 被 shuffle 成為不相鄰」、070 的「把 icq_id 倒過來儲存」或加上 MD5。這些原本是為了避開 contention,套來藏營業量是推論。最簡單的仍是對外只露出 UUID。

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

  1. PK
  2. bit
  3. timestamp
  4. SPOF
  5. UUID
  6. transaction
  7. hot spot
  8. B+tree
  9. contention
  10. heap / IOT
  11. natural key

資料本身就有名字,還需要另外發號碼嗎?

① 先想像

有些東西天生就有不重複的名字:航班有「日期+班次」,聊天訊息有「哪個聊天室+幾點幾分幾毫秒」。

你猜猜看:「2026/11/12 的 CI 100 班機」這筆資料,需要另外發一個流水號才不會重複嗎?

③ 這叫做 natural key、composite key

natural key:資料本身就有、不會變的唯一名字。composite key:一欄會撞,兩欄合起來才唯一的 PK。

④ 跟這章的關係

Triton 選 PK 的第一順位就是 natural key(第 38 頁)。聊天訊息的 PK,他用 (chatroomId, createTs)(下一頁)。

② 動手玩:哪一欄當 PK 不會撞?

Triton:常常根本不需要聊天訊息的 PK

「跟我說 auto increment id 的,你的大腦被汪吃掉了嗎」

你猜猜看:聊天 app 最常做的事是「打開一個聊天室,看最近的訊息」。PK 用 auto-increment,讀 room B 最近 6 則要翻幾頁?

「database 最常用的 query 應該是 – query message of SAME chatroom, order by createTs asc」「相同 chatroom 的 message record,他們的 phyiscal storage position 應該是相鄰的 這樣子才是 seq IO 而不是 Random IO」「PostgreSQL 不是好選擇,因為其 table 底層是 heap MySQL / HBase 請你挑一個~」🗣️ Triton 062-im-system design · Database

「跟我說 auto increment id 的,你的大腦被汪吃掉了嗎 一定是 (chatroomId, createTs) – 相同 chatroom 的 message 一定會物理相鄰 而且相同 chatroom 的 message 會以時間來排序」🗣️ Triton 062 · Message Primary Key

📝 上課筆記「createTs ⇒ ms 若一樣時間 就 failed 掉,再重發 request」「若用 auto increment id 而且用 ts 排, room1 room2 room3 沒有受惠的 filter」009

🔭 依 Triton 原則推論 原書整章的前提是「需要一個全公司唯一的數字 ID」。但聊天訊息只需要在同一個 chatroom 裡唯一而且依時間排序,(chatroomId, createTs) 就夠了:不用 ID 產生器、不用時鐘同步到全公司、沒有 SPOF,同一毫秒撞到就讓 PK constraint 擋下來、client 重送。

Triton 的做法選 PK 之前先問三個問題

先問:你真的需要一個「ID 產生器」嗎?

🔭 依 Triton 原則整理的決策流程

🗣️ Triton 本人說 PK 的優先順序

  • 「一般來說,比較好的PK都是以下這3種,不然你一般都會自己找自己的肝麻煩的。1. natural key 2. uuid 3. auto-increment」010
  • 常犯錯誤「使用 auto-increment作為 PK – 別害怕 OR/M 層的麻煩,系統發生 blocking 時要花的氣力遠比 OR/M 的麻煩要多 – 如果有 natural key ,請優先使用 … – 真的不能用 natural key 時,請用 UUID」012
  • 「決定用Surrogate Key時,使用UUID,別用 auto-increment」070
  • Natural key 的例子:「貨運站和香港海關都是以(航次日期+航次編號)作 PK」070

010 把 auto-increment 列為三種好 PK 之一,012 則把它列為常犯錯誤。兩份不衝突:010 是在說它不是效能瓶頸,012 和 070 是在說它集中在右邊造成 contention。Triton 也提醒 natural key 會失效:「某一天,老闆說:我想現在讓用戶也能用 facebook 戶口來登入系統」070。

Triton 補充HA 與時鐘

原書說「必須高可用」,Triton 說 HA 是什麼意思

你猜猜看:原書說 ID 產生器「必須高可用」。snowflake 內嵌在每台 web server,要做到 HA 需要什麼?

🗣️ Triton 本人說 時鐘差多少

「系統同時性問題:請去找NTP的相關文章吧 我不是SRE這方面不算很熟 但是正常SRE他們沒偷懶而且你的硬體沒問題下 同一個data center內的machine不太應該有超過10ms的時差的 如果你不是要做高時間敏感的交易系統,一般應用很足夠用了」

056-database的create_date和update_date的事

這段原本是談 create_date,不是談 ID 產生器。

🗣️ Triton 本人說 HA 的定義

「傳統上我們談High Availability(以下簡稱HA)我們是指:1. 系統中沒有single point of failure 2. 如果single component掛掉,是不需要人類即時行動。」

「有HA不代表系統完全零秒的Downtime, 有HA只代表有single component掛了後系統能自動短時間內回復。(一般來說「短時間」=數分鐘內)」

stateless component「就單純有N個相同的node就好」;資料庫的 failover「請使用像AWS RDS multi-AZ這些別人建好的方案」

017-High Availability stateful component vs stateless component

🔭 依 Triton 原則推論

  • Ticket server 本質上就是一台資料庫:HA 照 017 用 managed failover,不必自己發明「多台 ticket server 同步」
  • Snowflake 內嵌在 web server:幾乎是 stateless,HA 就是「N 個相同的 node」;唯一的狀態是 machine ID 不能重複
  • 獨立的 ID 服務:多一個要 HA 的元件。先問 N,原書需求一台就夠(第 18 頁)
  • 10ms 時差對「依時間大致排序」夠用;對「唯一」不夠,因為倒退會撞號(第 19 頁)

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

  1. PK
  2. bit
  3. timestamp
  4. SPOF
  5. UUID
  6. transaction
  7. hot spot
  8. B+tree
  9. contention
  10. heap / IOT
  11. natural key

到這裡你已經會了:真正的代價與 Triton 的做法

11 階全部走完了

下一頁是原書寫完之後的新東西(UUIDv7),再來用一句話收尾,最後是名詞小卡。

📅 2026 補充書本身的時間差

原書寫完之後,UUID 也學會了依時間排序

你猜猜看:2024 年的新版 UUID(UUIDv7)把時間放在最前面。存進 B+tree,它比較像 UUID v4,還是像 snowflake?

📅 2026 補充 UUIDv7

2024 年的 RFC 9562 定義了 UUIDv7:最前面 48 bit 是 Unix 毫秒時間戳,後面是隨機位元。它補上了原書說 UUID「不會隨時間遞增」的缺點,但仍然是 128 bit、仍然可能不是純數字。PostgreSQL 18(2025)內建 uuidv7()。

🔭 依 Triton 原則推論 但它也是 MI

時間戳放在最前面,UUIDv7 就跟 snowflake 一樣是 070 說的 Monotonic Increasing:新資料一樣擠在 PK index 的右邊。Triton 在 PG 上偏好 UUID 的理由(094「迴避 data contention」)是建立在 v4 的隨機上,換成 v7 這個理由就不成立了。

📅 2026 補充 69 年快用掉四分之一了

Twitter epoch 是 2010/11/04,加上 241 毫秒在 2080 年 7 月溢位。今天(2026)才開始用 Twitter epoch,等於一開始就少了 16 年;原書自己也建議自訂 epoch 設在接近今天。

一句話記住

號碼牌本身很便宜,
貴的是大家擠在同一頁、還被對手數得出來。

原書對的地方

  • 四種做法的優缺點:multi-master、UUID、ticket server、snowflake
  • Snowflake 的 1 / 41 / 5 / 5 / 12 配置與換算
  • 時鐘同步、區段長度、HA 是真的要談的點
  • machine ID 改錯會撞號

Triton 不同意的地方

  • auto-increment 不是瓶頸:不包在 TX、一次預配一疊
  • 真正的代價是 B+tree 右緣 contention(094、070)
  • 以及被猜出營業量(113)
  • 「依時間排序」的 ID 一樣擠在右邊(🔭)

Triton 的做法

  • 先 natural key,不行再 UUID(012、070)
  • 依 parent 查的資料用 (chatroomId, createTs)(062)
  • PG 用 UUID、MySQL 才習慣 auto-inc(060、132)
  • 要連號就接受 hot spot(010)

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

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

ID用來認出一筆資料的號碼
primary key(PK)登記簿第一欄,絕對不能重複的那個號碼
database(DB)存資料、不怕斷電的帳本
table、row一張表格/其中的一列(一筆資料)
auto_increment資料庫自動 +1 發的號碼
bit一顆燈泡:暗是 0、亮是 1
2 的 n 次方n 顆燈泡的亮法種數,像紙對折 n 次的層數
64 bit64 顆燈泡,約 1,800 京種號碼
timestamp從某一天開始數的秒數(或毫秒數)
epoch開始數的那一刻;Twitter 用 2010/11/04
毫秒(ms)千分之一秒
UTC世界標準時間,台灣是 UTC+8

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

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

Triton 本人的講義 / 文章

  • 010-喵談 RDBMS PK Auto-Increment(Roy 的 Notion 轉貼 Triton 原文)— 每秒百萬 insert 的反問、不包在 TX、一次跳 20 個、當機從 121 開始、連號要另建 table 會 hot spot、效能隱憂在 records 怎麼存。檔尾「AI」段不引用
  • 094-triton 談 pg index uuid 與 auto-inc — 最右邊 leaf node、8KB 抄 REDO log、近期資料最常被改、locking 滾雪球、顯示卡 FPS 比喻、PG 迴避 data contention
  • 070-lesson2(RDBMS 課程 v2)— heap vs IOT、Monotonic Increasing PK(含 timestamp)、natural vs surrogate、UUID 1T 個 9.4e-14、倒過來存 / MD5
  • 012-Advanced Database Skills — auto-increment 當 PK 是常犯錯誤、先 natural key 再 UUID、2-way bit shuffling
  • 062-im-system design — 「大腦被汪吃掉」、(chatroomId, createTs)、PG heap 不適合訊息表
  • 113 第 14、15 題 · 069 Serializable 不包 auto-inc · 060、132、021(inline comment)PG 偏 UUID / natural key · 015 heap 散落 · 017 HA 定義 · 056 NTP 10ms

上課筆記(非本人原文):009(MVP IM:PG 用 UUID 因為 heap、同毫秒失敗重送)、058(physical ordering、瓶頸在 lock)。不引用:010 與 060 的 AI 段落。Triton 的材料裡沒有談 Twitter snowflake,本簡報所有對 snowflake 的批評都標 🔭。

原書對照

Alex Xu, System Design Interview Vol.1 Ch.7。開場與 Figure 1、Step 1 需求(第 8 頁);Step 2 Multi-master 與 Figure 2(10);UUID 與 Figure 3(12);Ticket server 與 Figure 4(13);四種做法比較(14);Twitter snowflake 與 Figure 5(15);Step 3 deep dive 與 Figure 6(16);Timestamp 與 Figure 7(17);Sequence number(18);Step 4 Wrap up、clock synchronization(19);Section length tuning、high availability(20)。原書 7 張圖都依圖說與 alt 描述重繪,不是原圖;Figure 5、6 的 alt 標籤與內文不一致,依內文。

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

學習地圖(第 3 頁);延伸基礎 11 階:PK(4)、bit(5)、timestamp(6)、SPOF(9)、UUID(11)、transaction(22)、hot spot(23)、B+tree(27)、contention(29)、heap / IOT(33)、natural key(36);小結(7、21、28、40);名詞小卡(43)。Triton 頁:24–39。database、replication、lock、HA 連到第 1、2、4 章簡報的延伸基礎頁。喵喵銀行是虛構的示範情境;燈泡、登記簿、書架的數字是示意。

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

你系統裡最常被 UPDATE 的那張表,最近一小時新增的資料,是不是全擠在 PK index 的同一頁?你的訂單號碼,有沒有出現在給客人看的 URL 或收據上?

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