10.1 NVMe 與持久性記憶體#

概念說明#

NVMe（Non-Volatile Memory express）是為快閃裝置重新設計的介面協定。SATA 時代的瓶頸是介面本身：AHCI 只有 1 個佇列、深度 32；NVMe 提供多達 65535 個佇列、每個深度 65535，讓多核心 CPU 與 SSD 的多通道快閃晶片充分並行。實測數字：SATA SSD 約 10 萬 IOPS，NVMe SSD 可達 100 萬以上，延遲從 ~100μs 降到 ~10μs。

NVMe 改變了演算法的假設：

隨機與順序的差距縮小：HDD 上隨機比順序慢 100 倍，NVMe 上只慢 2~5 倍。「盡量順序化」的收益降低，但「減少 I/O 次數」的原則不變。
佇列深度變成調校關鍵：單執行緒串行 I/O 用不滿 NVMe，必須以多佇列、非同步 I/O（io_uring）疊高並行度。
B+tree 重新抬頭 vs LSM：LSM 的寫優化建立在「隨機寫很貴」上；NVMe 隨機寫變便宜後，兩者的取捨點移動，讀多寫少的工作負載更常直接用 B+tree。

持久性記憶體（PMem，如 Intel Optane）則是介於 DRAM 與 SSD 之間的層級：位元組可定址（像記憶體）、斷電不失（像磁碟）、延遲約 100~300ns（比 SSD 快 100 倍）、密度高於 DRAM。它催生了新的資料結構：

直接在持久記憶體上建索引：不需要頁緩衝與 fsync（資料寫入即持久，只需 cache line flush 指令），PMDK 函式庫提供事務式分配。
B+tree 變體：如 FPTree 內部節點放 DRAM（指標用 fingerprint 壓縮）、葉節點放 PMem，兼顧速度與持久。
無 WAL：傳統「先寫日誌」的代價可部分免除，改用原子寫入與恢復掃描。

演算法步驟：NVMe 上的調校循環#

量測基準：fio 測 4K 隨機讀/寫、佇列深度 1 vs 64 的 IOPS 與延遲。
依工作負載選結構：讀多 → B+tree + 大緩衝池；寫多 → LSM + 調 compaction。
疊並行：非同步 I/O、多執行緒各開佇列。
監控寫入放大與裝置壽命（SSD 磨損平衡）。

Python 範例：模擬不同裝置的結構選擇#

import math

DEVICES = {
    "HDD":   {"rand": 10_000, "seq_per_page": 0.1},   # 延遲 μs
    "SATA":  {"rand": 100,    "seq_per_page": 0.05},
    "NVMe":  {"rand": 10,     "seq_per_page": 0.02},
    "PMem":  {"rand": 0.3,    "seq_per_page": 0.15},  # 位元組定址，頁概念弱化
}

def point_query_cost(h, device):
    return h * DEVICES[device]["rand"]

def range_scan_cost(k, device):
    return (1 + k) * DEVICES[device]["seq_per_page"]

def choose_structure(read_ratio, writes_per_sec, budget_iops):
    if read_ratio > 0.8:
        return "B+tree + 大緩衝池（讀優化）"
    if writes_per_sec > budget_iops * 0.5:
        return "LSM + Bloom Filter（寫優化）"
    return "混合：B+tree 主鍵 + LSM 冷資料"

h = 3
for dev in DEVICES:
    print(f"{dev:>5}: 點查詢 {point_query_cost(h, dev):>8.1f} μs | "
          f"掃 100 頁 {range_scan_cost(100, dev):>7.2f} μs")
for rr, wps in [(0.95, 1000), (0.2, 50000)]:
    print(f"讀比例 {rr:.0%}、寫 {wps}/s →", choose_structure(rr, wps, 100000))

複雜度與 I/O 成本分析#

NVMe 點查詢（樹高 3）：~30μs，已接近部分網路來回；緩衝池的邊際效益下降，索引常駐記憶體的策略更直接。
PMem：無頁 I/O 概念，成本以 cache line flush（~100ns）計，WAL fsync 消失，提交延遲可降 10 倍以上。
啟示：每次硬體世代交替，「演算法成本模型」都要重新推導——本書的公式（2N、h+1、log_{B-1}(N/B)）骨架不變，但常數項全面改寫。

練習#

用 fio 或範例模型比較 HDD/NVMe 上「外部排序」的總時間，說明排序調校重心的轉移。
設計一個 PMem 上的無 WAL 原子寫入方案（提示：寫入前先寫 shadow 頁 + 版本位）。
討論 NVMe 佇列深度 1 與 64 時，B+tree 範圍掃描的延遲差異如何被並行攤平。