儲存引擎記憶體與磁碟結構#

16 B-Tree 內部機制講了就地更新引擎的分裂與恢復，15 RocksDB 與 LSM-Tree講了 LSM 的讀寫權衡。本章補的是兩類引擎共用的「結構地圖」── 一個磁碟檔案（SSTable）內部到底長什麼樣、記憶體裡的 memtable 用什麼資料結構、WAL 該多久 fsync 一次、flush 期間新舊狀態怎麼並存不出錯，以及讀路徑上那三層快取與頁面置換演算法。

快取的「業務層策略」（cache-aside、穿透/雪崩/擊穿）在 06 快取策略 已寫過。本章講的是引擎內部的記憶體結構與置換，不重述應用層快取。

SSTable 內部格式#

LSM 的磁碟元件是 SSTable（Sorted String Table）：按鍵排序、寫入後不可變的檔案。它不只是「一堆 KV」── 內部切成多種 block，並用尾部的 footer 串起來，這樣讀一個 key 才不需掃整個檔案。

┌─────────────────────────────────────────┐
│  Data Block 1   （排序 KV，~4-16 KB/塊） │
│  Data Block 2                            │
│  ...                                     │  ← 順序追加，可各自壓縮
│  Data Block N                            │
├─────────────────────────────────────────┤
│  Filter Block   （Bloom filter 位元陣列）│  ← 「key 一定不在」直接跳過
├─────────────────────────────────────────┤
│  Index Block    （每個 data block 的     │  ← key → block 偏移量
│                   起始 key + 偏移量）     │
├─────────────────────────────────────────┤
│  Meta Block     （統計：min/max key、    │
│                   筆數、壓縮資訊…）       │
├─────────────────────────────────────────┤
│  Footer         （固定大小：指向 index   │  ← 讀檔第一步只讀 footer
│                   block 與 filter block）│
└─────────────────────────────────────────┘

讀一個 key 的路徑：讀 footer ➡️ 定位 index block ➡️ 二分找到目標 data block 的偏移 ➡️ 先查 filter block（不在就放棄這個 SSTable）➡️ 解壓並讀該 data block。

設計要點：

  • 固定大小 footer 放尾部：檔案大小已知，從尾部回讀就能拿到所有區段的入口（header/trailer 定址的通用思路）
  • data block 各自壓縮：壓縮後大小不一、無法對齊頁邊界，所以需要 index block 存絕對偏移與長度
  • 每頁 checksum：損壞限制在單一 block，不污染整檔
  • index 也可以是 B-Tree：SSTable 內部常嵌一棵唯讀 B-Tree 當索引 ── B-Tree 與 LSM 在這裡其實是合作關係

Memtable：跳表 vs 平衡樹#

寫入先進記憶體的 memtable，它必須保持有序（flush 時才能順序寫出 SSTable），且支援高並發插入。兩種主流實作：

實作平衡方式並發友善度代表
跳表（Skiplist）概率性（隨機高度）高（CAS + 旗標即可線性化）RocksDB 預設
平衡樹（紅黑/AVL）旋轉維持平衡較低（旋轉需鎖較大範圍）部分引擎

跳表勝出的原因：插入不需旋轉或搬移，只調整少數指標，所以用 fully_linked 旗標搭配 CAS（compare-and-swap）就能做到無鎖並行，多寫者衝突少。各層節點數指數遞減，查找從頂層開始、大於就前進、小於就下降，期望 O(log N)。

跳表也是 Redis 有序集合的底層（見 02-database/07）。同一個資料結構在「記憶體有序索引」這個場景反覆出現，不是巧合 ── 它在並發插入下比平衡樹好寫太多。

WAL 的 fsync 策略#

memtable 在記憶體，斷電就沒，所以每筆寫入先進 WAL（16 章講過 write-ahead 鐵律）。問題是：WAL 寫進 page cache 後，多久真正 fsync 落盤一次？這是「持久性 vs 吞吐」的核心旋鈕。以 Redis AOF 的三檔為典型：

策略fsync 時機斷電最多丟吞吐適用
always每筆寫入後幾乎不丟（0）低金流、賬戶等不可丟場景
everysec每秒一次最多 1 秒高絕大多數線上業務（預設）
no交給 OS（~30s 刷盤）一個刷盤週期的量最高可重建、純快取性質資料

權衡的本質：fsync 是昂貴的同步磁碟操作（要等碟片/SSD 真正寫入），頻率越高吞吐越低。everysec 是工程上的甜蜜點 ── 用「最多丟 1 秒」換接近 no 的吞吐。

class=" " >03 章）。

Flush 期間的新舊 memtable 並存#

memtable 滿了要 flush 成 SSTable，但 flush 是磁碟操作、要時間，這段期間新寫入往哪去、讀請求看哪份資料？答案是新舊兩份 memtable 並存，且狀態切換必須原子。

sequenceDiagram
    participant W as 寫入
    participant New as 新 memtable（active）
    participant Old as 舊 memtable（immutable）
    participant SST as SSTable（磁碟）
    participant WAL as WAL
    Note over Old: memtable 達閾值，準備 flush
    W->>New: 1. 原子切換：新寫入全導向新 memtable
    Note over Old: 2. 舊 memtable 轉唯讀，仍可被讀
    Old->>SST: 3. 順序寫出為新 SSTable
    Note over Old,SST: 4. flush 完成：原子地用 SSTable 取代舊 memtable
    SST->>WAL: 5. 截斷對應的 WAL 段

三個正確性鐵則（任一違反都出 bug）：

  • 新寫入必須立刻導向新 memtable ── 否則寫進正在 flush 的舊表，資料遺失
  • 舊 memtable 在 flush 完成前必須仍可讀 ── 否則讀請求漏掉這批資料，結果不完整
  • WAL 截斷必須與 flush 同步 ── 太早截斷，崩潰後這段日誌無法重播，資料遺失

所以讀請求在這段期間要合併查：新 memtable + 舊 memtable + 已落盤 SSTable，取最新版本。compaction 期間同理 ── 舊 SSTable 在新表完全就緒前必須保持可讀，且不能讓同一張表同時參與多個 compaction。

三層快取與命中率#

讀路徑上資料可能命中三層記憶體，逐層往磁碟靠近、代價遞增：

層級內容管理者miss 的代價
Bloom filter 記憶體每個 SSTable 的成員測試位元引擎省掉一次磁碟讀（負向過濾）
Block cache解壓後的 data block引擎（LRU 等）讀磁碟 + 解壓
OS page cache檔案系統頁（壓縮態原始位元）作業系統真正的磁碟 I/O

它們的作用不同：

  • Bloom filter 不快取資料，而是避免無謂查找 ── 「這個 key 一定不在這張 SSTable」就跳過，對「查不存在的 key」尤其有效（FPR 與調參見 15 章 擴充段落）
  • Block cache 是引擎自管的 LRU，存解壓後的 block，命中省下解壓 CPU；生產環境常設幾 GB 到幾十 GB
  • OS page cache 存的是壓縮態的檔案頁；有些引擎用 O_DIRECT 繞過它、改用自管緩衝以精細控制 I/O 與預讀

命中率（hit rate）是調優的核心指標：B-Tree 因為「越靠根的節點越常被命中」，可以把高層節點 pin 在快取裡常駐，查詢時只為未快取的低層節點付磁碟 I/O，h 層的樹實際只讀少數幾次磁碟。

頁面置換演算法#

快取容量有限，滿了要**驅逐（evict）**最不可能再被用到的頁。規則：已與磁碟同步且未被 pin/參照的頁可直接驅逐；髒頁必須先刷回才能驅逐；正被使用的頁不驅逐。

演算法機制優點缺點
FIFO按載入順序佇列，最早進的先出簡單不看存取頻率，根節點易被誤逐
LRU重複存取就放回佇列尾貼近時間局部性並發下更新指標代價高
Clock環形緩衝 + 存取位元，掃描時把 1 改 0、遇 0 即驅逐近似 LRU，CAS 即可、並發友善精度略低於 LRU
2Q兩佇列：初訪進冷佇列，再訪移熱佇列區分「最近」與「頻繁」多一層簿記

更進階的策略看頻率而非時間：TinyLFU 用頻率直方圖 + 准入/觀察/保護三佇列，只有存取頻率高於「即將被逐者」的新元素才准入 ── 對「掃描多但真熱點少」的負載比純 LRU 抗污染。Clock 是 LRU 的並發友善近似（Linux 用其變體），環形緩衝的指標與內容都能用 CAS 改、免額外鎖。

小結#

  • SSTable = data / filter / index / meta block + 尾部 footer；讀 key 先讀 footer，再經 index ➡️ filter ➡️ data block
  • memtable 多用跳表：插入免旋轉、CAS 無鎖並發，勝過平衡樹
  • WAL fsync 三檔：always（不丟、慢）、everysec（甜蜜點）、no（最快、丟一個刷盤週期）
  • flush 期間新舊 memtable 並存：新寫導向新表、舊表保持可讀、WAL 同步截斷 ── 三鐵則
  • 三層快取各司其職：Bloom filter 負向過濾、block cache 存解壓 block、OS page cache 存壓縮頁
  • 置換看時間（LRU/Clock/2Q）或頻率（TinyLFU）；大掃描要防 scan 污染，用 FIFO 環形緩衝隔離

至此儲存引擎內部三節（15/16/17）串成一條：LSM 全貌 ➡️ B-Tree 物理機制 ➡️ 兩者共用的記憶體與磁碟結構。

Backward B-Tree 內部機制 分散式系統 Forward