資料庫底層原理 Database Internals

📌 30 秒摘要（Layer 3）

拆開資料庫的「引擎蓋」，看它內部到底怎麼運作。上半談儲存引擎：資料在磁碟上如何排列（B-Tree vs LSM-Tree）、如何靠預寫日誌在當機後不丟資料。下半談分散式：節點怎麼偵測彼此死活、怎麼靠 Gossip/反熵把狀態擴散、怎麼用**共識演算法（Paxos/Raft）**在多節點間達成一致。與 設計資料密集型應用 互補——DDIA 教你「該用什麼、為什麼」，本書教你「它內部是怎麼做出來的」。

🗺 心智圖（Canvas）

資料庫底層原理

⚙️ 資料庫底層原理

Database Internals — Alex Petrov 打開引擎蓋看它怎麼做出來

工具-儲存引擎B-Tree與LSM-Tree

🎯 什麼情境該想到我

當你在選資料庫/儲存引擎，或想理解「為什麼某個 DB 寫很快但讀較慢（或相反）」時。

⚙️ 怎麼用（依讀寫特性選）

1. B-Tree（就地更新）：資料原地排序更新，讀優化、範圍查詢好；寫入需隨機 I/O。傳統關聯式 DB（MySQL InnoDB…）。
2. LSM-Tree（追加寫）：寫入先進記憶體，再批次刷成不可變的 SSTable，背景合併（compaction）。寫優化、順序 I/O 快；讀要查多層 + 靠 Bloom filter 加速。RocksDB、Cassandra、LevelDB…
3. 用「三種放大」判斷取捨：讀放大、寫放大、空間放大——沒有引擎三者全贏。寫重 → LSM；讀重/範圍查多 → B-Tree。

🧪 我實際套用的紀錄

• 2026-07-15：（待填）

⚠️ 注意

• LSM 的 compaction 會吃 I/O、造成延遲抖動；B-Tree 的頁分裂會造成寫放大。按工作負載實測。

🔗 相關工具

• 工具-預寫日誌與崩潰復原 —— 兩種引擎共用的底層機制：不管 B-Tree 還是 LSM，斷電不丟資料都靠 WAL
• 工具-可靠可擴展可維護 —— 上位框架：選引擎其實是在三個面向間取捨，這張給你評估的座標

三種放大的取捨 讀放大 / 寫放大 / 空間放大——沒有一種資料結構能同時最佳化三者，只能取捨。

💾 第一部：儲存引擎結構

工具-預寫日誌與崩潰復原

🎯 什麼情境該想到我

當你想理解（或自己實作）「系統當機/斷電後，資料如何不丟、狀態如何回復一致」時。

⚙️ 怎麼用

核心原則：先寫日誌，再改資料（Write-Ahead）。 只要日誌落盤，就算資料還沒寫完，重啟後也能靠日誌重建。

1. 每次修改前，先把「要做什麼」順序追加寫入 WAL 並 fsync 落盤。
2. 提交（commit）以日誌寫入成功為準，實際資料頁可稍後再刷。
3. 崩潰復原（ARIES 三階段）：分析 → 重做（redo 已提交但未落盤的）→ 撤銷（undo 未提交的）。
4. WAL 也是複製與 CDC 的資料來源（把日誌串流給從庫）。

🧪 我實際套用的紀錄

• 2026-07-15：（待填）

⚠️ 注意

• 「寫了」不等於「落盤」；沒 fsync 的日誌在斷電時一樣會丟。持久化的關鍵在 fsync。

🔗 相關工具

• 工具-儲存引擎B-Tree與LSM-Tree —— 使用者，兩種引擎都靠 WAL 保證斷電不丟資料
• 工具-資料複製 —— 延伸應用，複製串流本質上就是把 WAL 傳到其他副本重放
• 工具-Transactional-Outbox-Pattern —— 應用層的同一思路，先寫進同一個交易再由別人重放

ARIES 復原三階段 分析（找出當機時的狀態）→ 重做（重放日誌）→ 回復（撤銷未提交交易）。

🛡 交易處理與崩潰復原

工具-故障偵測

🎯 什麼情境該想到我

當分散式系統需要判斷「某個節點還活著嗎」——但你分不清它是真的掛了還是只是網路慢/GC 停頓時。

⚙️ 怎麼用

1. 心跳 / 逾時：最簡單——定期回報，逾時未回報視為可疑。缺點：逾時值難調（太短易誤判、太長反應慢）。
2. Gossip 式偵測：節點互相傳播彼此的存活資訊，避免單點誤判、擴展性好。
3. Phi-accrual 偵測器：不給「死/活」的布林，而是輸出一個懷疑程度（機率），讓上層依情境自訂閾值，對網路抖動更穩健。

核心體悟：在分散式下，你永遠無法確定一個節點是「掛了」還是「只是慢」——只能給機率、做取捨。

🧪 我實際套用的紀錄

• 2026-07-15：（待填）

⚠️ 注意

• 誤判節點死亡會觸發不必要的選主/搬資料，代價很高；偵測要在「快」與「準」間權衡。

🔗 相關工具

• 工具-反熵與Gossip傳播 —— Gossip 式偵測的底層機制，同一套傳播方式怎麼讓存活資訊與副本狀態最終一致
• 工具-線性一致性與共識 —— 判定節點死亡之後要做的事（選主、達成一致），也解釋了誤判為何代價這麼高
• 工具-服務容錯設計 —— 偵測到之後怎麼反應：熔斷、艙壁、降級，避免一個慢節點拖垮整條鏈路

工具-反熵與Gossip傳播

🎯 什麼情境該想到我

當你有很多節點/副本、要讓它們的狀態「最終趨於一致」，又不想靠單一協調者時。

⚙️ 怎麼用

1. Gossip（八卦協定）：每個節點週期性隨機挑幾個對象交換資訊，像謠言一樣擴散。去中心化、可擴展、對節點增減有韌性。常用於成員管理、故障偵測、狀態傳播。
2. 反熵（Anti-Entropy）：定期比對副本差異並修補，讓飄移的副本收斂。用 Merkle Tree 高效找出「哪裡不同」，只傳差異。
3. 前景 vs 背景修復：讀取時順手修（read repair）+ 背景反熵掃描，兩者互補。

適合「最終一致」的大規模系統（Cassandra、DynamoDB 風格）。

🧪 我實際套用的紀錄

• 2026-07-15：（待填）

⚠️ 注意

• Gossip 是最終一致、有傳播延遲；需要「立刻強一致」的場景別用它，改用共識。

🔗 相關工具

• 工具-故障偵測 —— Gossip 最常見的用途之一就是傳播「誰活著」的判斷結果
• 工具-資料複製 —— 反熵補的正是複製留下的破口：副本漂移後怎麼慢慢對齊
• 工具-線性一致性與共識 —— 對照組，反熵給的是最終一致，需要強一致時得改走共識協定

🔎 第二部：故障偵測與狀態擴散

Paxos / Multi-Paxos 讓多節點對一個值達成一致；Multi-Paxos 用穩定領導者攤平多輪成本。

Raft：領導者選舉 + 日誌複製 把共識拆成好懂的三塊：選舉、日誌複製、安全性。

概念層對照 一致性模型與 CAP 取捨見 [[工具-線性一致性與共識]]（[[設計資料密集型應用]]）。

🤝 分散式共識

Link to original

🧰 這本書給我的工具

• 工具-儲存引擎B-Tree與LSM-Tree — 選/理解資料庫的讀寫特性時
• 工具-預寫日誌與崩潰復原 — 想理解資料庫如何保證不丟資料時
• 工具-故障偵測 — 分散式系統要判斷「某節點死了沒」時
• 工具-反熵與Gossip傳播 — 想讓大量節點最終狀態一致時

✨ 關鍵重點（Layer 1–2）

• 儲存引擎兩大流派：B-Tree（就地更新、讀優化）vs LSM-Tree（追加寫、寫優化、靠 SSTable + 合併）。
• 三種放大：讀放大、寫放大、空間放大——沒有引擎能同時最佳化三者。
• 崩潰復原：靠 WAL（預寫日誌）+ ARIES；先寫日誌再改資料。
• 故障偵測：心跳、逾時、Gossip、Phi-accrual（把「死活」變成機率而非布林）。
• 狀態擴散：反熵、Gossip 協定讓資訊在節點間最終傳遍。
• 共識：Paxos / Raft / 領導者選舉，讓多節點對值達成一致（概念層見 工具-線性一致性與共識）。

💬 金句原文（Layer 0）

• 「沒有一種資料結構能同時最佳化讀放大、寫放大與空間放大——你只能取捨。」

🔗 相關

• 高層概念與取捨見 設計資料密集型應用；一致性概念見 工具-線性一致性與共識