RocksDB 為什麼重要#

很少人直接用 RocksDB，但它在「現代儲存底層」幾乎無處不在：

RocksDB 是 Facebook 從 LevelDB（Google）fork 出來、專為 SSD 與大規模設計的嵌入式 KV 儲存引擎。

LSM-Tree：與 B+ Tree 的對抗#

關係型資料庫（MySQL InnoDB、PG）用 B+ Tree。為什麼 RocksDB 不用？

B+ Tree                      LSM-Tree
─────────                    ──────────
寫：找葉子 + in-place 修改     寫：append 到 log + memtable
讀：log(N) 查找葉子           讀：multi-level 查找
更新：原地改                  更新：寫新版 + 後台合併
刪除：原地標記                刪除：寫 tombstone + 後台合併

權衡：

對「寫多讀少 + SSD」場景，LSM 完勝。

LSM-Tree 結構#

        memtable           （memory，小，新寫入在這）
            ↓ flush
       Level 0：file 1, file 2, ...    （重疊 key 範圍）
            ↓ compact
       Level 1：file 1, file 2, ...    （key 範圍不重疊）
            ↓ compact
       Level 2：...
            ↓ ...
       Level N：（最大、最舊）

寫入流程#

1. WAL 寫一條 log（崩潰恢復用）
2. 寫進 memtable（記憶體跳表 / B-tree）
3. memtable 滿 → flush 成 Level 0 SSTable（不可變檔案）
4. 後台 compaction 把 Level 0 合進 Level 1，Level 1 合進 Level 2，...

寫操作只在記憶體 + 順序磁碟寫 ── 極快。

讀取流程#

1. 查 memtable
2. 查 Level 0 各 SSTable（可能多個有此 key）
3. 查 Level 1（用 key 範圍 prune）
4. 查 Level 2、...
5. 找到第一個（最新版本）回傳

最壞情況要查 N 層 + Level 0 多檔案。RocksDB 用 bloom filter 跳過大部分查找。

Compaction：後台魔法#

LSM 性能的關鍵。把多個小檔案合併成大檔案：

• 合並重複 key（保留最新）
• 應用 tombstone（真正刪除）
• 壓縮（lz4 / zstd）
• key 範圍重新整理

兩種 compaction 策略：

Leveled compaction#

每 level 大小是上一層 N 倍。Level i 與 Level i+1 部分檔案合併到 Level i+1。

L0  ─→ L1（合併重疊 key）
L1  ─→ L2
...

每層大小：L1 = 256 MB，L2 = 2.56 GB，L3 = 25.6 GB ...

優點：讀放大小、空間放大小（< 1.1x）。 缺點：寫放大大（每層都要寫一次）。

預設 RocksDB Leveled。

Tiered / Universal compaction#

每層多個 SSTable，達數量門檻就 merge 成下層一個大 SSTable。

優點：寫放大小。 缺點：讀放大大（多 SSTable 要查）、空間放大可能 2x+。

Cassandra 用 SizeTieredCompactionStrategy 是這個。

三大放大#

LSM-Tree 的權衡核心：

寫密集場景關注 WA（直接影響吞吐）。讀密集關注 RA。容量緊張關注 SA。

LSM-Tree 通常 WA 1030、RA 110、SA 1.1~2。沒有完美 ── 調參數調的就是這三個的取捨。

Leveled vs Size-Tiered 的數量級對比#

前面提過兩種 compaction 策略，這裡用三放大把差距量化。它們是同一張權衡三角形上的兩個極端：

為什麼數量級差這麼多：

• Leveled：L0..Ln 每層大小倍增（如 ×10），key 範圍在 L1 以下不重疊。一筆資料從 memtable 一路下沉，每經過一層就被重寫一次，層數越多寫放大越大 ── 但因為每層 key 不重疊，一次點查每層最多碰一個 SSTable，讀放大就是層數量級；舊版本很快被合併掉，空間放大趨近 1。
• Size-Tiered：同層攢多個同尺寸 SSTable，達數量門檻才合併成下一層一個大表。合併次數少 ➡️ 寫放大低；但同層多個表 key 範圍重疊，點查可能每個都要碰 ➡️ 讀放大高；合併前同一 key 的多份副本與待回收空間並存 ➡️ 空間放大 2× 起跳。

選型直覺：

寫密集（log / metric / event）         → Size-Tiered（省寫放大、省 SSD 壽命）
讀密集 / 容量敏感（線上 KV、訂單）     → Leveled（讀穩定、空間省）
RocksDB 預設 Leveled；Cassandra 預設 Size-Tiered（SizeTieredCompactionStrategy）

用 KaTeX 把直覺寫死。Leveled 下，資料要穿過約 $L$ 層、每層放大係數約為層間倍率 $T$，寫放大量級：

$$ WA_{leveled} \approx T \times L \quad(\text{故 } T=10,\ L \in [4,7] \Rightarrow 40 \sim 70\times) $$

Size-Tiered 下，每層只在攢滿 $T$ 個表時合併一次，每筆資料每層只被重寫約一次：

$$ WA_{tiered} \approx L \quad(\text{量級僅個位數倍}) $$

RocksDB 的關鍵特性#

1. Column Families#

類似 SQL 的 schema：

DB* db = DB::Open(...);
db->CreateColumnFamily("orders", ...);
db->CreateColumnFamily("inventory", ...);

db->Put(orders_cf, "key", "value");
db->Get(inventory_cf, "key", &value);

每個 CF 獨立的 memtable + LSM。可以為每個 CF 設不同 compaction 策略、壓縮、快取策略。

2. WriteBatch#

批次寫入：

WriteBatch batch;
batch.Put("k1", "v1");
batch.Put("k2", "v2");
batch.Delete("k3");
db->Write(write_options, &batch);

批次原子（要嘛全成功要嘛全失敗）+ 性能比逐筆好。

3. Snapshot 與 MVCC#

const Snapshot* snap = db->GetSnapshot();
ReadOptions ropts;
ropts.snapshot = snap;
db->Get(ropts, "key", &value);   // 讀 snapshot 時間版本
db->ReleaseSnapshot(snap);

multiversion concurrency。配合 NewSQL 的事務語意。

4. Bloom filter#

每個 SSTable 內建 bloom filter，跳過大部分「key 一定不在」的檔案。對「不存在的 key」查詢效能極佳。

Bloom filter 是 LSM 對抗讀放大的主力武器。讀放大的根源是「不知道哪張 SSTable 有目標 key」，要逐張查。Bloom filter 是空間效率極高的概率結構：

• 不會偽陰性：回報「不在」就一定不在 ── 可以安心跳過這張表，省一次磁碟讀
• 可能偽陽性（FPR）：回報「可能在」但實際不在 ── 白讀一次，這就是它與讀放大的反向權衡

查詢時每張候選 SSTable 先過 filter：

flowchart TD
    Q[查 key K] --> M{memtable 有？}
    M -->|有| Ret[回傳最新版本]
    M -->|無| L0[逐層走 SSTable]
    L0 --> BF{Bloom filter 報在？}
    BF -->|否，一定不在| Skip[跳過此表，不讀磁碟]
    BF -->|是，可能在| Read[讀 index + data block]
    Read --> Found{真的有？}
    Found -->|是| Ret
    Found -->|否，偽陽性| Skip
    Skip --> Next{還有下層？}
    Next -->|有| L0
    Next -->|無| NotFound[回傳 NOT FOUND]

調參核心是 bits_per_key（每個 key 配幾個 bit），RocksDB 預設約 10。位元越多 FPR 越低、跳過越準（讀放大越小），但 filter 本身佔的記憶體越大。最佳雜湊函數數 $k$ 與偽陽性率 $p$：

$$ k = \frac{m}{n}\ln 2,\qquad p \approx \left(1 - e^{-kn/m}\right)^{k} $$

其中 $m$ 是位元陣列大小、$n$ 是 key 數，$m/n$ 即 bits_per_key。代入 $m/n = 10$ 約得 $p \approx 1%$ ── 即 99% 的「不存在」查詢能省下整次磁碟讀。因為 SSTable 不可變、$n$ 已知，這些參數可在建表時精確算好。

Bloom filter 只加速點查（key 等值查詢），對 range query 完全無能為力 ── 範圍掃描要的是「這段區間有哪些 key」，而 filter 只能回答單一 key 的成員測試。範圍掃描仍得靠每層 SSTable 的 index block 與 key 範圍 prune。

5. Block cache#

讀過的 block 快取在記憶體（LRU）。RocksDB 預設用 8 MB block size、LRU cache 32 MB（生產環境調幾 GB ~ 幾十 GB）。

6. Compaction filter#

在 compaction 時自定 callback，可以根據業務邏輯刪除 key（例：TTL）：

class TTLCompactionFilter : public CompactionFilter {
    bool Filter(int level, const Slice& key, const Slice& existing_value, ...) {
        if (is_expired(existing_value)) return true;  // drop
        return false;  // keep
    }
};

適合的工作負載#

適合#

• 寫多讀少（log、metric、event）
• 高並發 KV 訪問
• 範圍掃描（同 prefix 連續）
• SSD 部署
• 大量小 KV（每筆 100 byte ~ KB 級）

不適合#

• 高頻 random read（RA 高）
• 大 value（每筆幾 MB+）── 用 BlobDB 變體
• 強事務跨多 key（要外加層）
• 主要 OLAP 工作負載 ── 用列式

與其他 KV 比較#

電商日誌、訂單、metric 用 LSM 系。設定、user profile 用 B+ Tree 系。

RocksDB 調優入門#

最常碰的幾個參數：

options.write_buffer_size = 64 << 20;        // memtable 大小，64MB
options.max_write_buffer_number = 4;         // memtable 個數
options.target_file_size_base = 64 << 20;    // L1 SSTable 大小
options.max_bytes_for_level_base = 256 << 20;// L1 總大小
options.compression = kSnappyCompression;    // 壓縮
options.level_compaction_dynamic_level_bytes = true;  // 自動調整每層大小

對寫密集場景關鍵：

• write_buffer_size 大 ➡️ 攢更多 ➡️ flush 更少 ➡️ 寫放大小
• max_background_jobs 大 ➡️ 多核 compaction 並行
• compression_per_level：頂層用 lz4（快）、底層用 zstd（壓縮高）

一個觀察#

LSM-Tree 為什麼 2010 後爆發？因為：

• SSD 普及（順序寫遠比 random 寫便宜）
• 寫密集應用增多（log、metric、events）
• 雲端按 IOPS 計費，LSM 寫放大 trade-off 變得重要

過去 InnoDB 統治 OLTP，現在 OLTP（NewSQL）+ NoSQL + 訊息中介 + 監控全部基於 LSM。LSM 是過去 15 年最重要的儲存創新。

進一步閱讀#

• 論文：The Log-Structured Merge-Tree（O’Neil et al., 1996）── LSM 原論文
• RocksDB Wiki：詳細 tuning guide
• Designing Data-Intensive Applications（Martin Kleppmann）── 第 3 章
• LevelDB 原始碼（~10K 行）── 想學 LSM 內部最好起點

小結#

• LSM-Tree：append + 後台 compaction，為 SSD + 寫密集設計
• 三大放大：寫放大、讀放大、空間放大 ── 沒有完美設計
• RocksDB：Facebook 工業級 LSM 引擎，幾乎所有現代分散式 KV 內部
• compaction 策略：Leveled（讀好寫差）、Tiered（寫好讀差）
• column families、snapshot、bloom filter、block cache 是 RocksDB 的關鍵
• 不只 KV ── NewSQL、訊息佇列、監控、流處理全都疊在 LSM 之上

15 章到此結束。從訂單冪等到 LSM-Tree，整條電商儲存架構的演化路徑串完。

下個方向值得讀：跨地域強一致（Spanner 論文）、HTAP 細節（TiDB 論文）、向量資料庫（語意搜尋的下一步）、AI 訓練資料管道。