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 階。每一階只用前面講過的東西。
- 1PK不重複的號碼牌
- 2bit開關燈泡
- 3timestamp從某天開始數
- 4SPOF一台壞全部停
- 5UUID超大的骰子
- 6transaction一筆手續
- 7hot spot搶同一支筆
- 8B+tree分頁的電話簿
- 9contention擠在最後一頁
- 10heap / IOT倉庫 vs 圖書館
- 11natural key本來就有的名字
第 1–3 階 · 號碼牌是什麼做的
要回答:「64 bit、依時間排序」是什麼意思?
第 4–5 階 · 好幾台取號機
要回答:原書四種做法差在哪?為什麼選 snowflake?
第 6–8 階 · 走進資料庫
要回答:auto-increment 真的是瓶頸嗎?
第 9–11 階 · Triton 的答案
要回答:真正的代價在哪?真的需要 ID 產生器嗎?
全程只用一家銀行:喵喵銀行(虛構)
數學只用三樣:數燈泡、乘以 2、加減心算。每爬 3 階左右,有一頁「到這裡你已經會了」。
延伸基礎第 1 階 · PK懂的人可以跳過
- PK
- bit
- timestamp
- SPOF
- UUID
- transaction
- hot spot
- B+tree
- contention
- heap / IOT
- natural key
兩位客人都叫「王小明」,叫號時誰站起來?
① 先想像
銀行把每位客人寫進登記簿,一列一個人。叫號時,櫃台只喊第一欄。
你猜猜看:第一欄寫名字,今天來了兩位「王小明」。叫「王小明」時會怎樣?
名字會重複,所以銀行改發號碼牌:每個號碼只出現一次。右邊兩種都試試。
③ 這叫做 ID、primary key(PK)
ID:用來認出一筆資料的號碼。PK:登記簿第一欄那個「絕對不能重複」的號碼。
④ 跟這章的關係
這章要設計的,就是「誰來發這個號碼、怎麼保證不重複」。登記簿就是 database(第 1 章簡報第 8 頁)。
② 動手玩:登記簿的第一欄
延伸基礎第 2 階 · bit懂的人可以跳過
- PK
- bit
- timestamp
- SPOF
- UUID
- transaction
- hot spot
- B+tree
- contention
- heap / IOT
- natural key
「64 bit」是什麼?先數一排燈泡
① 先想像
一排燈泡,每顆只有亮、暗兩種。把亮暗的組合當成號碼。
你猜猜看:5 顆燈泡,最多排得出幾種不同的亮法?
每多一顆,種類就翻倍:2 → 4 → 8 → 16 → 32。就像一張紙對折 5 次,會疊成 32 層。
③ 這叫做 bit、2 的次方
bit:一顆燈泡,暗是 0、亮是 1。n 顆燈泡有 2 × 2 × … × 2(n 個 2)種,寫成 2n,叫「2 的 n 次方」。
④ 跟這章的關係
原書規定 ID 只能用 64 顆燈泡(64 bit)。5 顆 = 32 種、12 顆 = 4,096 種,這兩個數字等一下都會出現。
② 動手玩:點燈泡開關
延伸基礎第 3 階 · timestamp懂的人可以跳過
- PK
- bit
- timestamp
- SPOF
- UUID
- transaction
- hot spot
- B+tree
- contention
- heap / IOT
- natural key
「現在幾點」也可以寫成一個數字
① 先想像
喵喵銀行開幕那一刻,牆上的計數器從 0 開始,每過一秒 +1,從來不歸零。
你猜猜看:計數器顯示 3,600,是開幕後多久?
1 分鐘 60 秒,1 小時 60 × 60 = 3,600 秒。1 天是 86,400 秒。
③ 這叫做 timestamp、epoch
timestamp:從某一天開始數的秒數(或毫秒數)。epoch:開始數的那一刻,就是「開幕那一刻」。
④ 跟這章的關係
數字越大=越晚,所以拿它當開頭的號碼,會自動照時間排好。snowflake 數的是毫秒(千分之一秒)。
② 動手玩:牆上的計數器
0
到這裡你已經會了小結 1 / 4
- PK
- bit
- timestamp
- SPOF
- UUID
- transaction
- hot spot
- B+tree
- contention
- heap / IOT
- natural key
到這裡你已經會了:號碼牌是什麼做的
- 每筆資料要有一個認得出它的號碼(ID);登記簿第一欄那個絕對不能重複的,叫 PK。
- 一顆燈泡是一個 bit;n 顆有 2n 種亮法。64 bit 就是 64 顆燈泡。
- timestamp 是從某一天開始數的秒數(毫秒數):越大越晚。
下一階要解決的問題
面試官要的號碼牌:不能重複、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 頁);可排序=號碼大小就是先後。
📖 原書 需求清單
- ID 必須唯一
- ID 只有數值
- ID 放得進 64 bit
- ID 依日期排序
- 每秒能產生超過 10,000 個唯一 ID
文組換算:每秒 10,000 個 = 每毫秒 10 個。記住這個數字,第 18 頁會用到。
user_id(依原書內容重繪;描述沒給數字,這裡用示意值)延伸基礎第 4 階 · SPOF懂的人可以跳過
- PK
- bit
- timestamp
- SPOF
- UUID
- transaction
- hot spot
- B+tree
- contention
- heap / IOT
- natural key
一台取號機壞了,整間銀行會怎樣?
① 先想像
喵喵銀行門口只有一台取號機。客人越來越多,分行想再多放一台。
你猜猜看:兩台取號機都從 1 號開始發,彼此不講話。會怎樣?
兩台都從 1 開始,兩邊的第一位客人都拿到 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 數量可以隨資料庫台數擴展。
白話:MySQL=一種常見的 database;replication=把資料抄到好幾台(第 1 章簡報第 14 頁);multi-master=每一台都能寫;web server=接待客人的櫃台電腦。
動手玩:k 台資料庫,每台 +k
📖 原書 三個主要缺點
- 難以擴展到多個資料中心
- 跨多台 server 的 ID 不會隨時間遞增
- 新增或移除 server 時擴展性不佳
延伸基礎第 5 階 · UUID懂的人可以跳過
- PK
- bit
- timestamp
- SPOF
- UUID
- transaction
- hot spot
- B+tree
- contention
- heap / IOT
- natural key
不用講好,各自擲骰子,會撞號嗎?
① 先想像
不想讓取號機互相講話?那每個櫃台自己擲骰子,擲出幾點就是幾號。
你猜猜看:班上 23 個人,至少兩人同一天生日的機率大約是?
比直覺高很多:23 個人可以湊出 253 對,每一對都有機會撞。這叫「生日問題」,右邊拉拉看。
③ 這叫做 UUID、collision
UUID:每台機器自己擲的「超大骰子」,約有 2122 面。collision:兩次擲出一樣的號碼,就是撞號。
④ 跟這章的關係
原書第 2 種做法就是它。面數夠大,撞號機率就小到可以不管(下一頁算給你看)。
② 動手玩:生日問題
原書 Step 2四種做法之 2 · UUID · Figure 3
每台 web server 自己擲一個 128 bit 的骰子
這一步要解決的問題不想讓機器互相講話,就各自擲骰子。號碼夠不夠短、會不會撞、有沒有照時間?
📖 原書 UUID 是 128 bit 的數字,碰撞機率非常低。原書引用維基百科:「在大約 100 年內每秒生成 10 億個 UUID,產生單一重複的機率才會達到 50%」。例子:09c93e62-50b4-468d-bf8a-c07e1040bfb2。UUID 可以各自產生、不需要 server 之間協調。
📖 優點
- 產生很簡單,不用協調,沒有同步問題
- 好擴展:每台 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
所有人都去同一台取號機拿號碼
這一步要解決的問題回到最簡單的:大家都去同一台取號機。它好在哪、怕什麼?
📅 補充 原書參考資料 [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 顆燈泡分成五格。
📖 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 開機時決定,時間和序號邊跑邊產生
這一步要解決的問題五格裡,哪幾格事先貼在櫃台上、哪幾格要邊跑邊算?
📖 原書 決定採用 Twitter snowflake 的做法。Datacenter ID 和 machine ID 在啟動時選定,系統跑起來後通常固定。任何更動都要謹慎審查,因為不小心改到可能造成 ID 衝突。Timestamp 和 sequence number 則是 ID 產生器執行時產生的。
白話:datacenter=機房,像分行;machine=機房裡的一台電腦,像櫃台;ID 衝突=撞號(第 11 頁的 collision)。
文組翻譯
分行代號、櫃台代號是開門前就貼在櫃台上的;時間看手錶,序號自己數。兩個櫃台不小心貼了同一個代號,就會在同一毫秒發出一模一樣的號碼牌。
原書 Step 3Timestamp · Figure 7
41 bit 的毫秒數,可以用 69 年
這一步要解決的問題最大的一格是時間。41 顆燈泡能數多少毫秒、用多少年?
📖 原書 最重要的 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
- PK
- bit
- timestamp
- SPOF
- UUID
- transaction
- hot spot
- B+tree
- contention
- heap / IOT
- natural key
到這裡你已經會了:原書的完整設計
- 只有一台取號機是 SPOF。多台要嘛事先講好(單號、雙號),要嘛各自擲 UUID 骰子:不撞,但太長、沒照時間。
- 原書選 snowflake:64 顆燈泡切成「時間 41、機房 5、機器 5、序號 12」,每台機器只看手錶、數自己的人。
- 時間在最前面,所以號碼照時間排;手錶不準會排錯,倒退還會撞號。
下一階要解決的問題
原書一開頭說「auto_increment 在分散式行不通」。Triton 不同意。要聽懂他,先學資料庫裡的「一筆手續」和「搶同一支筆」。
延伸基礎第 6 階 · transaction懂的人可以跳過
- PK
- bit
- timestamp
- SPOF
- UUID
- transaction
- hot spot
- B+tree
- contention
- heap / IOT
- natural key
轉帳辦到一半停電,錢會不見嗎?
① 先想像
轉帳 100 元有兩步:你的帳戶扣 100、對方的帳戶加 100。銀行保證兩步要嘛都做完,要嘛都沒發生。
你猜猜看:扣完你的 100、還沒加給對方就停電。重開機後你的帳戶?
沒辦完的手續整筆作廢,好像從沒開始過。右邊按「停電」試試。
③ 這叫做 transaction(TX)、commit / rollback
TX:一筆「全做或全不做」的手續。commit:簽名,正式生效;反悔、整筆作廢叫 rollback。
④ 跟這章的關係
資料庫裡每一筆 insert(新增一列)都在 TX 裡。Triton 的第一個論點:拿 auto-increment 號碼這一步,不包在 TX 裡(第 25 頁)。
② 動手玩:轉帳 100 元
延伸基礎第 7 階 · hot spot懂的人可以跳過
- PK
- bit
- timestamp
- SPOF
- UUID
- transaction
- hot spot
- B+tree
- contention
- heap / IOT
- natural key
8 個人要寫登記簿,只有一支筆
① 先想像
登記簿綁著一支筆。拿到筆的人寫,其他人在旁邊等;寫完、放下筆,下一位才能拿。
你猜猜看:8 個人,每人寫 1 分鐘,只有一支筆。最後一個人寫完是第幾分鐘?
一次只能一個人寫,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 的反問。
🗣️ Triton 本人說 先想一個很基本的問題
「大家看MySQL,他們的Insert都是宣稱能每秒以百萬級來算的。」「要做到每秒百萬級的Insert,一定是同時打開上千個的資料庫連線,然後每一個連線不停地跑 Insert指令的。」
「Auto-Increment只有一個數值,怎能讓上千個transaction同一時間改動,但是不會發生hot-spot問題讓效能卡住?」
010-喵談 RDBMS PK Auto-Increment(Roy 的 Notion 轉貼 Triton 原文)
答案預告:兩個原因
- 拿號碼不包在 transaction 裡,所以 TX 之間不會互相等
- 資料庫一次預先配一疊號碼,不用每拿一個就寫一次硬碟
那真正的問題在哪?
「auto-increment的效能隱憂不在auto-increment本身,而是在於你的records怎麼存到HDD上的問題」🗣️ Triton 本人說 010 · 回覆學員提問
Triton 的解釋為什麼 auto-increment 不是瓶頸
號碼拿了就不還,而且一次預訂 20 個
你猜猜看:TX A 拿到 101 號,後來 rollback 反悔了。下一個 TX 會拿到 101 嗎?
號碼拿了就不還,所以 B 不必等 A 決定要不要反悔。代價是 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 舉的例子;實際一次預訂多少,各家資料庫與設定不同。
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 筆手續要拿號,會怎樣?
前一筆可能反悔,號碼要等它 commit 才算數,下一筆只能等。這就是第 23 頁的 hot spot。
延伸基礎第 8 階 · B+tree懂的人可以跳過
- PK
- bit
- timestamp
- SPOF
- UUID
- transaction
- hot spot
- B+tree
- contention
- heap / IOT
- natural key
電話簿為什麼要分頁、照順序排?
① 先想像
一本電話簿照號碼排好,每頁只寫得下 4 個人。要找 33 號,先看最前面的目錄「27–41 在第 2 頁」,直接翻過去。
你猜猜看:第 3 頁有一個人改了電話,影印店要重印多少?
影印一次就是一整頁。資料庫也一樣:只改 1 個字,也要把那一整頁(8KB)重新寫一次。
③ 這叫做 index、B+tree
index:照順序排好、讓你直接翻到那一頁的目錄。B+tree:資料庫的 index;上層是目錄,最底層一頁一頁裝資料(leaf page,一頁 8KB)。
④ 跟這章的關係
資料庫用 PK 排這本電話簿。新號碼插在哪一頁,決定大家擠不擠(下一階)。
② 動手玩:電話簿每頁寫 4 個號碼
到這裡你已經會了小結 3 / 4
- PK
- bit
- timestamp
- SPOF
- UUID
- transaction
- hot spot
- B+tree
- contention
- heap / IOT
- natural key
到這裡你已經會了:auto-increment 不是瓶頸
- 資料庫的一筆手續叫 transaction:commit 生效、rollback 作廢。
- 大家搶同一支筆就是 hot spot。Triton:拿 auto-increment 號碼不包在 TX 裡、一次預訂一疊,所以不搶;真的要「完全不跳號」才會變成 hot spot。
- 資料庫用 B+tree 照 PK 排成一頁一頁,改一個字也要寫整頁。
下一階要解決的問題
號碼一直變大,新資料都插在 B+tree 的哪一頁?Triton 說,真正的代價在這裡。
延伸基礎第 9 階 · contention懂的人可以跳過
- PK
- bit
- timestamp
- SPOF
- UUID
- transaction
- hot spot
- B+tree
- contention
- heap / IOT
- natural key
號碼一直變大,今天的客人都寫在哪一頁?
① 先想像
登記簿照號碼排。號碼牌一張比一張大,所以今天來的每位客人,都接在最後面。
你猜猜看:登記簿有 6 頁。早上 12 位客人同時來登記,會寫在幾頁上?
號碼一直變大,一定接在最後面。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 的幾頁?
號碼一直變大(MI),一定接在最後面,就是第 29 頁的登記簿。右邊按按鈕驗證。
「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 · 現實上
Triton 原則推論原書的 snowflake 也逃不掉
「依時間排序」的 snowflake,一樣擠在最右邊
你猜猜看:原書把 auto_increment 換成 snowflake,時間放在最前面。存進資料庫的 B+tree,新資料會落在哪?
snowflake 的號碼也是一直變大。第 29 頁的登記簿,「照號碼牌」和「照到達時間」結果一模一樣。
哪些號碼是 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 快、寫硬碟比較少。上線之後也一定比較快嗎?
剛下的單最常被改,而它們全擠在最右邊那頁(第 {page:t-edge} 頁)。跑分量不到這種擠。
「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懂的人可以跳過
- PK
- bit
- timestamp
- SPOF
- UUID
- transaction
- hot spot
- B+tree
- contention
- heap / IOT
- 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?
圖書館照 PK 上架,號碼一直變大,新書都接在最後,上架最省事;換成 UUID,新書得插進各個架上。倉庫本來就隨便放,用 UUID 不會打亂資料本身。
文組翻譯
倉庫(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。你知道了什麼?
中間 12 小時賣了大約 3,640 杯。每週買兩杯,連對手的成長曲線都畫得出來。
🗣️ 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懂的人可以跳過
- PK
- bit
- timestamp
- SPOF
- UUID
- transaction
- hot spot
- B+tree
- contention
- heap / IOT
- natural key
資料本身就有名字,還需要另外發號碼嗎?
① 先想像
有些東西天生就有不重複的名字:航班有「日期+班次」,聊天訊息有「哪個聊天室+幾點幾分幾毫秒」。
你猜猜看:「2026/11/12 的 CI 100 班機」這筆資料,需要另外發一個流水號才不會重複嗎?
同一天、同一個班次只有一班。資料本身就有的名字,拿來當 PK 就好,不用另外找取號機。
③ 這叫做 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 則要翻幾頁?
訊息照到達順序排,三個聊天室混在一起,room B 散在各頁。右邊按按鈕驗證。
「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 本人說 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 需要什麼?
每台都只看自己的手錶、數自己的人,沒有誰是 SPOF。唯一要顧好的,是 machine ID 不能重複。
🗣️ 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
- PK
- bit
- timestamp
- SPOF
- UUID
- transaction
- hot spot
- B+tree
- contention
- heap / IOT
- natural key
到這裡你已經會了:真正的代價與 Triton 的做法
- 號碼一直變大(MI:auto-increment、時間、snowflake),新資料全擠在 B+tree 最右邊一頁,造成 contention;號碼還會讓對手數出營業量。
- PostgreSQL 是倉庫(heap),MySQL 是圖書館(IOT):資料怎麼放,決定 PK 該用 UUID 還是 auto-increment。
- 先找資料本身的名字(natural key),像聊天訊息用 (chatroomId, createTs);很多時候根本不需要 ID 產生器。
11 階全部走完了
下一頁是原書寫完之後的新東西(UUIDv7),再來用一句話收尾,最後是名詞小卡。
📅 2026 補充書本身的時間差
原書寫完之後,UUID 也學會了依時間排序
你猜猜看:2024 年的新版 UUID(UUIDv7)把時間放在最前面。存進 B+tree,它比較像 UUID v4,還是像 snowflake?
時間在最前面,號碼就一直變大,就是第 29 頁的 MI。下面按 → 一張一張看。
📅 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)
本章名詞小卡課後複習用 · 每個名詞一句白話
今天出現的名詞,一句話講完
給工程師的重點出處與標籤
引述來源(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 或收據上?