資料庫底層原理 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。

★ 核心對照（這張表就是全部）

	B-Tree（PG、MySQL InnoDB、SQLite）	LSM-Tree（RocksDB、Cassandra、LevelDB）
寫入	★ 原地更新：找到頁 → 改 → 寫回（隨機寫）	★ 只追加：寫 memtable → 滿了就刷成 SSTable（順序寫）
寫入吞吐	中	★ 高（順序寫快得多）
讀取	★ 可預測：$O(\log n)$ 次 I/O，走一條路徑	⚠️ 可能查多層（memtable → L0 → L1 → …）
寫入放大	中（頁分裂、WAL 寫兩次）	★ 高（compaction 反覆重寫同樣的資料）
空間放大	中（頁內碎片，約 60–70% 填充率）	★ 低（壓縮率好）但 compaction 前會暫時翻倍
範圍掃描	★ 好（葉節點有序且鏈結）	中（要合併多層）
刪除	就地標記	★ 寫一個 tombstone（墓碑）——空間之後才回收
延遲穩定性	★ 穩定	⚠️ compaction 會造成尾延遲尖峰

★ 三種「放大」（理解儲存引擎的核心概念）

放大	定義	誰嚴重
寫入放大	實際寫到磁碟的位元組 ÷ 應用寫入的位元組	★ LSM（compaction 把同一筆資料重寫很多次）
讀取放大	一次查詢要讀幾次磁碟	★ LSM（要查多層）
空間放大	實際佔用 ÷ 有效資料	★ B-Tree（頁未填滿）；LSM 在 compaction 時暫時很高

★ RUM 猜想：Read、Update、Memory 三者最多只能優化兩個。
這就是為什麼沒有「全面更好」的儲存引擎——每一個都是在這個三角上選了一個位置。

★ LSM 的讀取怎麼救

查一個 key：
  ① memtable（記憶體，快）
  ② ★ Bloom filter 判斷「這個 SSTable 可能有嗎」
     → 說「沒有」就是真的沒有（不會偽陰性），直接跳過，不用讀磁碟
  ③ 真的可能有才讀 SSTable

★ Bloom filter 是 LSM 讀取效能的關鍵。沒有它，每次讀都要查所有層。
（它有偽陽性但沒有偽陰性——這個不對稱正是它有用的原因。）

★ Compaction：LSM 的命脈，也是它的痛點

策略	做法	取捨
Size-tiered	同樣大小的 SSTable 合併成更大的	★ 寫入放大低，空間放大高（同一筆資料存在多層）
Leveled	每層大小固定倍增，層內 key 不重疊	★ 讀取與空間好，寫入放大高
混合 / 時間序列專用	Cassandra 的 TWCS（依時間窗）	時序資料專用

★ Compaction 是背景 I/O，會和前台查詢搶資源 →
這就是 LSM 尾延遲不穩定的根源。 生產上要限制 compaction 的頻寬。

★ 實務上什麼時候該在意這件事

多數時候不用在意——你不會因為儲存引擎而選資料庫。但這幾個情況要：

情況	影響
寫入吞吐是瓶頸（日誌、遙測、IoT、事件流）	★ LSM 明顯有利
需要穩定的 p99 讀取延遲	★ B-Tree（LSM 的 compaction 會製造尖峰）
大量範圍掃描 / 分析查詢	B-Tree 或列式儲存
★ 寫入模式是「大量刪除或覆寫」	⚠️ LSM 的 tombstone 會累積；Cassandra 的「墓碑地獄」是經典問題
SSD 壽命敏感（寫入放大 = 磨損）	要算寫入放大

★ 一個實用的觀察：
PostgreSQL 的 MVCC 讓 UPDATE 實際上是「寫新版本 + 標記舊版本」——
行為上有點像 LSM（所以需要 VACUUM 來回收，就像 compaction）。
★ PG 的表膨脹（bloat）與 autovacuum 調校，本質上就是 compaction 的問題。

其他儲存形態

形態	適合
列式（columnar）	★ 分析查詢（只讀需要的欄、壓縮率極高）——ClickHouse、Parquet
雜湊索引	只需要點查、資料能放記憶體（見 雜湊表）
B+Tree vs B-Tree	★ B+Tree 只在葉節點存資料且葉節點互相鏈結 → 範圍掃描快得多，實務上都是 B+Tree

🧪 我實際套用的紀錄

• 2026-07-15：（待填）

⚠️ 注意 / 什麼時候不適用

• ★ 不要為了儲存引擎換資料庫。生態、運維成熟度、團隊熟悉度的權重遠高於此。
  這個知識的用途是「解釋為什麼我的寫入會慢 / p99 會抖」，不是選型的第一準則。
• ★ LSM 的 tombstone 會咬人。大量刪除後空間不會立刻回收，而且讀取時要掃過墓碑。
  Cassandra 的 gc_grace_seconds 與墓碑閾值是必須理解的營運參數。
• ★ PG 的 autovacuum 調校是同一類問題。高更新率的表會膨脹 → 查詢變慢 → 要調 vacuum 的積極度。
• B-Tree 的頁分裂在隨機 key 插入時最嚴重。★ 用遞增的主鍵（如 UUID v7 而非 v4）可以大幅減少分裂與隨機 I/O。
• 索引不是免費的。每個索引都要在寫入時更新 → 寫入放大乘以索引數量。
• 量測的是「你的工作負載」。benchmark 數字與你的讀寫比、key 分布、資料大小高度相關。
• 雲端資料庫的儲存層可能完全不同（Aurora 把 log 直接寫進分散式儲存），上面的模型不完全適用。

🔗 相關工具

• 工具-預寫日誌與崩潰復原 —— 兩種引擎都靠它保證持久性
• 紅黑樹 —— B-Tree 的對照：為什麼磁碟上要用高扇出的樹
• 雜湊表 —— 另一種索引形態
• 工具-用trigram索引加速模糊查詢 —— 特殊索引型別
• 工具-資料分區 —— 更上層的擴展手段
• 工具-快取與資源優化 —— 比換引擎便宜得多
• 工具-程式碼調校 —— 先量再選
• 資料庫底層原理、設計資料密集型應用

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

💾 第一部：儲存引擎結構

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

🎯 什麼情境該想到我

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

⚙️ 怎麼用

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

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

★ 為什麼「先寫日誌」就能保證不壞

根本問題：磁碟寫入不是原子的。 寫一個 8KB 的頁到一半斷電 → 半新半舊的頁，既不是舊狀態也不是新狀態。

❌ 直接改資料頁
   改到一半斷電 → ★ 資料頁毀損，而且「不知道毀在哪」

✅ WAL
   ① 先「順序追加」寫日誌：「我要把 X 從 A 改成 B」
   ② fsync 讓日誌真的落盤
   ③ 回報 commit 成功                     ← ★ 此刻就安全了
   ④ 資料頁稍後再刷（可以批次、可以延後）

   斷電後重啟 → 讀日誌 → 重做已提交但沒刷完的，撤銷沒提交的

★ 關鍵洞察：WAL 把「隨機寫」變成「順序寫」。
資料頁散落在磁碟各處（隨機寫，慢）；日誌只是往檔案尾端追加（順序寫，快得多）。
所以 WAL 不只讓資料安全，還讓寫入變快——這是它能成為所有資料庫標配的真正原因。

★ fsync 才是真正的瓶頸

write()  → 資料只到了「作業系統的 page cache」   ★ 斷電就沒了
fsync()  → 強制刷到「實體儲存」                 ★ 這一步才安全，也是最慢的一步

儲存	單次 fsync 大約
機械硬碟	~10 ms（受限於轉速）
SSD	~0.1–1 ms
有電池保護的 RAID 卡快取	★ 極快（斷電時電池保住快取內容）

★ 這解釋了資料庫的一個核心指標：「每秒能提交幾個交易」約等於「每秒能做幾次 fsync」。

★ 群組提交（group commit）：把多個並行交易的日誌合併成一次 fsync——
這是資料庫提升寫入吞吐最重要的優化之一，也是「批次寫入比逐筆寫入快幾十倍」的原因。

⚠️ 廉價 SSD 會對 fsync 說謊（回報已落盤但其實還在自己的快取裡），斷電就毀。
生產環境要用有斷電保護（PLP）的企業級 SSD。

★ ARIES 三階段（崩潰復原的標準做法）

① 分析 Analysis：從最後一個 checkpoint 掃到日誌尾端
                 → 找出崩潰時「哪些交易還沒提交」「哪些頁是髒的」
② 重做 Redo    ：★ 從 checkpoint 重放「所有」變更（包含未提交的）
                 → 把資料庫還原到「崩潰當下」的狀態
③ 撤銷 Undo    ：★ 回捲所有未提交的交易

★ 「為什麼 redo 要包含未提交的」是經典追問：
因為要先把狀態精確還原到崩潰當下，才能正確地執行 undo
（undo 需要知道「當時的值」是什麼）。這叫 repeating history。

Undo 本身也要寫日誌（CLR, compensation log record），否則 undo 到一半又崩潰就無法繼續。

Checkpoint 的作用：標記「這之前的都已經刷到資料頁了」→ 復原只要從 checkpoint 開始，不用從頭重放。
★ checkpoint 太稀疏 → 復原慢；太頻繁 → 平時的 I/O 壓力大。 這是可調的取捨。

★ WAL 的第二個身分：資料的變更串流

WAL 記錄了「每一次變更」，所以它天然就是一個有序的事件流：

用途	怎麼用 WAL
複製	把 WAL 串流給從庫重放（見 工具-資料複製）
★ CDC（變更資料捕捉）	Debezium 讀 PG 的邏輯解碼 / MySQL 的 binlog → 推到 Kafka
時間點復原（PITR）	基礎備份 + 重放到指定時間的 WAL
★ 事件溯源	概念上同源：狀態是事件重放的結果

★ CDC 讀 WAL 而不是「定時輪詢資料庫」，是一個重要的架構選擇：
輪詢會漏掉中間狀態、有延遲、且對主庫造成負載；
讀 WAL 拿到的是完整、有序、低延遲的變更流。
→ 這也是 工具-Transactional-Outbox-Pattern 的一種替代方案。

同源的其他設計

系統	對應
LSM-Tree	memtable 前的 WAL（見 工具-儲存引擎B-Tree與LSM-Tree）
檔案系統	ext4/XFS 的 journal
Kafka	★ 整個系統就是一個 WAL（分散式的有序追加日誌）
Redis	AOF（append-only file）
etcd / Raft	★ 共識演算法的 log 就是 WAL（見 工具-線性一致性與共識）
備忘錄模式	檢查點 + 增量，同一個思路

🧪 我實際套用的紀錄

• 2026-07-15：（待填）

⚠️ 注意 / 什麼時候不適用

• ★ fsync 的成本決定了寫入吞吐上限。想提高就要靠群組提交或批次交易，
  而不是「加機器」——單一交易的提交延遲是物理限制。
• ★ synchronous_commit = off 會讓寫入快很多，但斷電會丟掉最近的交易。
  這是一個明確的取捨（適合可重算的資料，不適合金流）。要有意識地設定，不要當成「效能調校」隨手開。
• WAL 會佔空間且需要管理。PG 的 max_wal_size、歸檔策略設錯 →
  ★ 磁碟被 WAL 塞爆導致資料庫停止寫入（很常見的生產事故）。
• ★ 複製槽（replication slot）洩漏：從庫掛了但 slot 還在 → 主庫的 WAL 永遠不能回收 → 磁碟爆掉。
  CDC 工具離線時特別容易踩到。要監控 slot 的落後量。
• 廉價 SSD 對 fsync 說謊（見上）。
• WAL 保證的是「單機的崩潰安全」，不是「磁碟毀損的安全」——那要靠備份與複製。
• 邏輯複製與實體複製不同：PG 的實體複製（streaming）要求版本一致；
  邏輯複製（logical decoding）才能跨版本、跨系統——做 CDC 要用邏輯的。

🔗 相關工具

• 工具-儲存引擎B-Tree與LSM-Tree —— WAL 在兩種引擎裡的角色
• 工具-資料複製 —— WAL 串流就是複製
• 工具-交易與隔離等級 —— 提交的持久性由 WAL 保證
• 工具-Transactional-Outbox-Pattern —— CDC 是它的替代方案
• 工具-線性一致性與共識 —— Raft 的 log 也是 WAL
• 備忘錄模式 —— 檢查點 + 增量的同一個思路
• 工具-生產故障反模式清單 —— WAL 塞爆磁碟是經典事故
• 設計資料密集型應用、資料庫底層原理

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

🛡 交易處理與崩潰復原

工具-故障偵測

🎯 什麼情境該想到我

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

⚙️ 怎麼用

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

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

★ 根本難題：你無法區分「掛了」和「很慢」

送出請求 → 沒有回應
可能是：① 對方掛了      ② 對方很慢      ③ 請求在路上丟了
        ④ 回應在路上丟了 ⑤ 對方 GC 停頓   ⑥ 你自己的網路壞了
★ 從外面看，這六種完全無法區分。

★ 這不是工程問題，是理論限制（非同步系統中不可能有完美的故障偵測器）。
所以所有故障偵測都是「在誤判與延遲之間選一個位置」，沒有正確答案。

逾時太短	逾時太長
★ 誤判：把健康但暫時慢的節點踢掉	★ 反應慢：故障節點繼續接流量
→ 觸發不必要的 failover / 再平衡	→ 使用者持續看到錯誤
→ ★ 在高負載時特別危險（慢 → 被踢 → 剩下的更慢 → 全部被踢）

★ 「高負載時的誤判」是連鎖故障最常見的起點——這是設定逾時時最該記住的一件事。

★ Phi-accrual：輸出「懷疑度」而不是布林

傳統心跳：超過 5 秒沒回應 → 死了（硬閾值，非黑即白）

Phi-accrual：

① 記錄過去 N 次心跳的「間隔」，建立分布（通常假設常態或指數分布）
② 依「距離上次心跳多久」算出 φ = -log₁₀(P(還活著))
   φ = 1  → 誤判機率 10%
   φ = 2  → 誤判機率 1%
   ★ φ = 8  → 誤判機率 10⁻⁸
③ ★ 不同的上層各自選閾值：
   「把它移出讀取池」用 φ > 3（寬鬆，可逆，代價低）
   「觸發 failover」  用 φ > 8（嚴格，不可逆，代價高）

★ 它真正的價值有兩個：

1. 自適應：網路平時抖就自動放寬，平時穩就自動收緊——不用手調逾時值
2. ★ 讓「代價不同的決策」用不同的閾值 —— 這才是關鍵。
   「暫時不送流量過去」和「宣告它死亡並重新選主」不該用同一個判斷。

（Cassandra、Akka 用它。）

★ 健康檢查的三個層次（常被混為一談）

檢查	問的問題	失敗時該做什麼
Liveness	「行程還活著嗎？」	★ 重啟它
Readiness	「現在能接流量嗎？」（暖機中、依賴掛了、過載）	★ 移出負載平衡，但不要重啟
Startup	「啟動完成了嗎？」	延後前兩者的檢查

★★ 最常見也最危險的錯誤：liveness 檢查裡去查資料庫。

資料庫短暫不可用 → 所有 pod 的 liveness 失敗 → ★ 全部被重啟
→ 重啟風暴 → 連線風暴 → 資料庫更掛 → 永遠起不來

Liveness 只該檢查「這個行程本身是不是卡死了」（例如 deadlock）——
不要檢查任何外部依賴。 外部依賴放 readiness。

Readiness 也要小心：如果所有實例都因為同一個下游而 not ready → 整個服務從 LB 消失。
→ 考慮「下游掛了仍回報 ready，但以降級模式服務」（見 工具-服務容錯設計）。

★ 逾時值該怎麼定（不要拍腦袋）

① 量出這個呼叫的延遲分布（p50 / p95 / p99 / p999）
② 逾時 ≈ p99 × 1.5～2      ← ★ 從資料來，不是從直覺來
③ ★ 確認「逾時 × 重試次數 < 上游的逾時」
   否則上游早就放棄了，你還在重試 —— 純浪費資源
④ 逾時必須配合 context 往下傳（見 [[工具-select超時與競速]]）

★ 一個常見的錯誤配置：
每一層各設 30 秒逾時 + 3 次重試 → 最壞情況 3 × 3 × 3 = 27 次請求、270 秒。
這在故障時會放大流量數十倍，把半掛的下游徹底打死。
→ 正解：端到端一個 deadline，往下傳遞（見 工具-服務容錯設計）。

★ 偵測之後要做什麼（比偵測本身更重要）

判定	行動	可逆嗎
可疑	★ 降低權重（少送一點流量過去）	✅
大概掛了	移出負載平衡池	✅
確定掛了	觸發 failover / 再平衡	❌ 不可逆，要更嚴格的閾值

★ 設計原則：可逆的行動用寬鬆閾值，不可逆的用嚴格閾值。
而且要有「一次最多踢掉幾個節點」的上限——
否則一次網路抖動可能讓整個叢集自我毀滅。

🧪 我實際套用的紀錄

• 2026-07-15：（待填）

⚠️ 注意 / 什麼時候不適用

• ★★ Liveness 檢查不要碰外部依賴（見上）。這是 Kubernetes 環境最常見的自殺方式。
• ★ 誤判的代價往往大於延遲的代價。把健康節點踢掉 → 剩下的負載更高 → 更多節點被判定為慢 → 雪崩。
  → 一定要有「同時最多能移除 N%」的保護（Kubernetes 的 PDB、負載平衡器的 panic threshold）。
• ★ 節點「半死」比「全死」更糟。全死了流量會自動繞過；半死（能回應健康檢查但實際處理失敗）
  會持續吸走流量。→ 健康檢查要檢查「真的能做事」，不是只回 200。
• 不要用單一觀察者判斷。單一節點的網路問題會讓它誤判所有人都掛了。
  → gossip 式的多方確認（見 工具-反熵與Gossip傳播）。
• ★ GC 停頓與 VM 暫停和「網路分區」無法區分（見 工具-線性一致性與共識）。
  所以「偵測到掛了」之後的行動必須是安全的（fencing token）。
• 健康檢查本身會有成本。幾千個節點互相檢查 → $O(n^2)$ 的流量。gossip 是為此設計的。
• 時鐘偏移會讓心跳判斷失準。用單調時鐘計算間隔，不要用 wall clock。

🔗 相關工具

• 工具-服務容錯設計 —— 偵測到之後的降級、重試、斷路器
• 工具-反熵與Gossip傳播 —— 多方確認的故障偵測
• 工具-線性一致性與共識 —— 「掛了還是只是慢」的理論限制與 fencing
• 工具-資料複製 —— failover 的三個坑
• 工具-select超時與競速 —— 逾時必須沿 context 往下傳
• 工具-遙測與監控 —— 逾時值要從延遲分布來
• 工具-生產故障反模式清單 —— 誤判造成的連鎖故障
• 設計資料密集型應用

工具-反熵與Gossip傳播

🎯 什麼情境該想到我

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

⚙️ 怎麼用

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

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

★ Gossip 為什麼可擴展：$O(\log N)$ 輪就傳遍

每輪：每個已知的節點隨機挑 k 個對象傳播
★ 感染的節點數是指數成長的（像流行病模型）

N = 10,000 節點、k = 3
→ 約 log₃(10000) ≈ 9 輪就幾乎全部收到
→ ★ 每個節點每輪只發 3 則訊息，不是 9999 則

	中心化廣播	★ Gossip
訊息數	$O(N)$（中心發給所有人）	★ 每節點 $O(k)$，與 N 無關
單點故障	★ 有（中心掛了就停）	❌ 沒有
收斂速度	1 輪	$O(\log N)$ 輪
節點增減	要更新中心的名單	★ 自動適應

★ 代價是「最終」而非「立即」，而且沒有完成的通知——
你永遠不知道「大家都收到了」，只知道機率上應該收到了。

★ 三種 Gossip 模式（用途不同）

模式	做什麼	適合
Push	「我有新資訊，給你」	更新少時快
Pull	「你有什麼我沒有的？」	★ 更新多時效率高
★ Push-Pull	兩者都做	實務標配，收斂最快

★ 反熵與 Merkle Tree：怎麼「只傳差異」

問題：兩個副本各有 1000 萬筆資料，要找出哪幾筆不一樣。逐筆比對要傳 1000 萬個雜湊。

Merkle Tree 的做法：

             root hash          ← ★ 先只比這一個
            /          \
       h(AB)            h(CD)   ← 不同才往下比
      /     \          /     \
   h(A)   h(B)      h(C)   h(D)
    |       |         |       |
  資料A   資料B     資料C   資料D

① 比 root：相同 → ★ 整棵樹一致，比對結束（傳 1 個雜湊）
② 不同 → 比兩個子節點 → 只往「不同」的那邊下降
③ 走到葉節點 → 就是有差異的那幾筆
★ 比對成本 O(log n)，傳輸量 ∝ 差異的數量，不是資料總量

★ 這是「用樹狀雜湊做高效差異比對」的通用技巧，不只用在資料庫：
Git 的物件模型、區塊鏈的交易驗證、IPFS、rsync 都是同一個思路。

★ 兩種修復路徑（互補，都要）

路徑	時機	特點
★ 讀修復（read repair）	讀取時發現副本不一致，順手修	✅ 免費（搭在讀取上） ❌ ★ 沒人讀的資料永遠不會被修
★ 反熵（anti-entropy）	背景定期掃描	✅ 涵蓋冷資料 ❌ 有 I/O 成本，要限速

★ 只做讀修復的系統，冷資料會無限期地飄移——這就是為什麼 Cassandra 一定要排 nodetool repair。

提示修復（hinted handoff）：寫入時目標節點暫時不可用 → 協調者先暫存，等它回來再補送。
★ 但提示會過期（max_hint_window），超過就只能靠反熵。

★ 「最終」到底是多久

這是最實用的一個問題，而答案是：取決於你有沒有排修復。

情況	收斂時間
正常運作（gossip + 讀修復）	毫秒～秒
節點短暫離線 + 提示修復	回來後幾分鐘
★ 節點離線超過 hint window	★ 直到下一次反熵掃描——可能是幾天
★ 沒排反熵、資料也沒人讀	★ 永遠不收斂

★ 「最終一致」不是自動發生的，是被維運出來的。
這是實務上最容易被忽略的一點——它需要排程、需要監控、需要資源預算。

Gossip 的其他用途

用途	例子
成員管理	誰在叢集裡（Cassandra、Consul、Serf）
故障偵測	傳播「誰可疑」（見 工具-故障偵測）
設定傳播	拓撲、schema 版本
★ CRDT 同步	配合 CRDT 可保證無論傳播順序如何都收斂

🧪 我實際套用的紀錄

• 2026-07-15：（待填）

⚠️ 注意 / 什麼時候不適用

• ★ 需要立即一致就不能用 gossip。選主、唯一性約束、扣庫存要共識（見 工具-線性一致性與共識）。
• ★ 反熵一定要限速。全量 Merkle 比對 + 修復是重度 I/O，不限速會把生產叢集拖垮。
  Cassandra 的 repair 造成線上事故是很常見的。排在離峰時間、限制並行度。
• ★ 修復要排程，不能只靠讀修復（見上）。而且要監控上次成功修復的時間。
• 墓碑（tombstone）與修復的交互：刪除的資料若在 gc_grace_seconds 內沒完成修復，
  ★ 已刪除的資料會「復活」（某個節點沒收到刪除，反過來把它傳播回去）。
  這是 Cassandra 最惡名昭彰的坑。
• Gossip 有流量成本。節點數很多時，光是 gossip 本身就是可觀的頻寬。
• Merkle Tree 的建立成本不低（要掃過所有資料算雜湊），所以不能太頻繁。
• 不要自己實作。用 hashicorp/memberlist（Serf/Consul 的底層）或既有的資料庫機制。

🔗 相關工具

• 工具-故障偵測 —— gossip 最常見的用途之一
• 工具-資料複製 —— 無主複製與讀修復
• 工具-線性一致性與共識 —— 需要強保證時的對照
• 工具-一致性雜湊 —— 副本放在哪些節點
• 工具-儲存引擎B-Tree與LSM-Tree —— 墓碑的來源
• 雜湊表 —— Merkle Tree 的基礎
• 設計資料密集型應用

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

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）

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

🔗 相關

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