跳轉到

6.2 LSM 樹與寫入優化#

概念說明#

LSM 樹（Log-Structured Merge Tree）是寫入優化索引的代表，RocksDB、LevelDB、Cassandra、HBase 的核心。它把「隨機寫入」徹底轉成「順序寫入」：

  1. 寫入先進記憶體表（memtable），例如跳躍表或有序字典；同時寫一條 WAL 日誌保證持久性（見 8.3 節）。
  2. memtable 滿了就整批排序、一次性寫成磁碟上的一個 SSTable（有序字串表）——純順序 I/O。
  3. 磁碟上維護多層 SSTable：L0、L1、L2…，每層容量約為上一層的 10 倍。後台以合併壓實（compaction）把上層與下層歸併，同時丟棄被覆蓋的舊版本與刪除標記（墓碑 tombstone）。

查詢時要從新到舊檢查：memtable → L0 → L1 → …，找到即回。因為同一鍵可能存在多層，需要逐層找，讀取放大是 LSM 的天然代價；Bloom Filter（6.3 節）就是用來削減這個代價的。

寫入成本驚人地低：每筆記錄一生只被「順序寫」約 ⌈log₁₀(N/B)⌉+1 次（tiered）或更多（leveled），全部是順序 I/O。相比之下，B+tree 隨機插入每筆要數次隨機 I/O。

演算法步驟#

寫入（k, v）： 1. 追加 WAL 日誌（順序寫）。 2. 插入 memtable；滿則凍結。 3. 凍結的 memtable 排序後寫成 L0 的新 SSTable。 4. 若 L0 檔案數超過門檻，觸發 compaction：L0 ∪ L1 歸併成新 L1；L1 滿則往 L2 推。

查詢（k）： 1. 先查 memtable。 2. 依新到舊逐層查 SSTable（可用 Bloom Filter 跳過不含此鍵的檔案）。 3. 找到第一個（最新）版本即回傳；遇到墓碑視為不存在。

Python 範例：簡化版 LSM 樹#

import heapq

class LSMTree:
    def __init__(self, mem_cap=8, level_ratio=4):
        self.mem = {}                  # memtable
        self.levels = [[], [], []]     # levels[i] = 該層的 SSTable list
        self.mem_cap = mem_cap
        self.ratio = level_ratio
        self.io = {"w": 0, "r": 0}
        self.tomb = "#TOMB#"

    def put(self, k, v):
        self.mem[k] = v
        if len(self.mem) >= self.mem_cap:      # 凍結 → 寫 L0
            self.io["w"] += 1
            self.levels[0].append(dict(sorted(self.mem.items())))
            self.mem = {}
            self._maybe_compact(0)

    def delete(self, k):
        self.put(k, self.tomb)                 # 墓碑

    def _maybe_compact(self, li):
        if li + 1 >= len(self.levels) or \
           len(self.levels[li]) < self.ratio:
            return
        self.io["w"] += len(self.levels[li]) + len(self.levels[li+1])
        merged = {}
        for tab in self.levels[li+1][::-1] + self.levels[li][::-1]:
            merged.update(tab)                 # 新蓋舊
        merged = {k: v for k, v in merged.items() if v != self.tomb}
        self.levels[li], self.levels[li+1] = [], [dict(sorted(merged.items()))]
        self._maybe_compact(li + 1)            # 下層滿了繼續推

    def get(self, k):
        self.io["r"] += 1
        if k in self.mem:
            v = self.mem[k]
            return None if v == self.tomb else v
        for level in self.levels:
            self.io["r"] += len(level)         # 簡化：每個 SSTable 一次 Bloom 探測
            for tab in level:
                if k in tab:
                    v = tab[k]
                    return None if v == self.tomb else v
        return None

ls = LSMTree(mem_cap=4)
for i in range(30):
    ls.put(f"key{i:02d}", i)
ls.delete("key03"); ls.delete("key07")
print("get key05:", ls.get("key05"), "| get key03（已刪）:", ls.get("key03"))
print("層分布:", [len(l) for l in ls.levels], "I/O:", ls.io)

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

  • 寫入：每筆 1 次順序寫（WAL + memtable 凍結）＋攤提的 compaction 寫；leveled 策略最壞約 10× 寫入放大，tiered 約 ratio×。
  • 讀取（鍵存在）：memtable + 各層探測；有 Bloom Filter 時未命中層幾乎 0 I/O。
  • 空間放大：舊版本在 compaction 前共存，空間放大約 1.1~2×。
  • 光譜：B+tree = 讀優化（寫 1× 空間，寫放大隨機）；LSM = 寫優化（寫順序，讀需多層）。RocksDB 允許調整 compaction 策略在兩者之間取捨。

練習#

  1. 用 mem_cap=4 寫入 20 筆後，列出各層 SSTable 的鍵範圍，驗證層間有序不相交（leveled）。
  2. 測量「寫入 100 筆」與「讀 100 個隨機鍵」的 I/O 統計，與 B+tree 比較寫/讀放大。
  3. 說明墓碑為何必須保留到「最底層 compaction」才能丟棄，若提前丟棄會發生什麼。