Skip to content
Published on

LSM-Tree 完全ガイド — RocksDB, LevelDB, Compaction, Bloom Filter, Write Amplification のすべて (2025)

🇰🇷KO🇺🇸EN🇯🇵JA
Split View필사 모드
Authors

はじめに — なぜまた別のストレージエンジンか

前回の記事で PostgreSQL の内部を掘り下げ、B-tree の優雅さを見た。数十年 DB を支配してきたデータ構造である。しかし 2010 年代に入り、別系統が静かに世界を席巻し始めた。Cassandra、HBase、LevelDB、RocksDB、ScyllaDB、InfluxDB、TiKV、CockroachDB、FoundationDB、ClickHouse MergeTree。すべて LSM-Tree (Log-Structured Merge Tree) またはその亜種の上で動く。

なぜ LSM か。B-tree の弱点は明確 — ランダム書き込み。更新のたびにページを探し、修正し、WAL を書き、ディスクの任意の位置に fsync する。HDD 時代は致命的で、SSD 時代も Write Amplification と wear leveling の問題が残る。

LSM の答え: ディスクには順次書き込みのみ。既存データは触らない。更新は新レコードの追加、削除も tombstone の追加として表現。バックグラウンドで compaction により静かにマージする。

この単純な発想が書き込みスループットを 10–100 倍に引き上げ、現代 NoSQL の基盤となった。本稿では 1996 年 O'Neil 論文から RocksDB の最新 compaction 戦略、Bloom Filter、RUM 予想、実システム (Cassandra、ScyllaDB、TiKV)、B-tree との共存戦略まで扱う。

1. LSM の起源 — 1996 年の洞察

1.1 O'Neil 論文

O'Neil、Cheng、Gawlick、O'Neil が 1996 年に提案。当時の問題意識:

  • B-tree の更新はランダム I/O。
  • HDD シークは 10ms → 秒間 100 が限界。
  • TPC-B 規模のベンチマークに B-tree では追従不可。

核心的アイデア: 書き込みをメモリに集約し、大きな塊で順次ディスクへ flush する。順次 I/O はランダム I/O より 100–1000 倍速い。ディスク上の既存データとのマージも順次 merge で解ける。

実応用は 2003 年 Google の Bigtable 論文から。以降 LevelDB、RocksDB (Facebook の LevelDB fork)、Cassandra、HBase へと続いた。

1.2 RUM 予想

Athanassoulis et al. (2016) 論文。ストレージエンジンが最適化したい 3 指標:

  • R (Read Amplification): 論理読み込み 1 回あたりの実ディスク読み回数。
  • U (Update Amplification = Write Amplification): 論理書き込み 1 回あたりの実ディスク書込バイト数。
  • M (Memory Amplification = Space Amplification): 論理データサイズに対するディスク使用量。

RUM 予想: この 3 つを同時に最小化することはできない。

  • B-tree: R 優、U 劣、M 中。
  • LSM: R 劣、U 優、M は状況次第。
  • Hash table: R 最優、U 劣、M 劣。

エンジン設計はこのトレードオフの中でどこに座るかの選択である。

2. LSM の構造 — 3 層の単純さ

2.1 基本構成

+----------+
| Memtable |  <- in-memory, sorted (skiplist)
+----------+
     |
     | flush
     v
+------------+------------+------------+
| SSTable L0 | SSTable L0 | SSTable L0 |
+------------+------------+------------+
     |
     | compaction
     v
+----------+----------+----------+
| SST L1   | SST L1   | SST L1   |
+----------+----------+----------+
     |
     v
+-----+-----+-----+
| L2  | L2  | L2  | ...
+-----+-----+-----+
  • MemTable: メモリ内の整列データ構造。通常 skiplist (RocksDB、LevelDB)。
  • WAL (Write-Ahead Log): MemTable のクラッシュ対策ディスクログ。
  • SSTable (Sorted String Table): 不変 (immutable) な整列ファイル。一度書いたら変更しない。
  • Compaction: 下位レベルの SSTable を集約し上位レベルへマージ。

2.2 書き込みパス

PUT(key, value)
  1. WAL に (key, value) を append + fsync (オプション)
  2. MemTable に insert
  3. MemTable が閾値超過:
       - 新 MemTable を割り当て (書き込みは継続)
       - 旧 MemTable を immutable にマーク (flush 対象)
       - バックグラウンドスレッドが disk へ flush → 新 L0 SSTable 生成
       - 該当 MemTable 分の WAL を破棄

要点: 書き込みはメモリのみに行く。ディスク書き込みは WAL append (順次) と SSTable flush (順次) で、いずれも順次 I/O。だから速い。

2.3 WAL

Postgres の WAL と概念は同じ。クラッシュ時に MemTable を再構成するために使う。違い:

  • LSM の WAL は flush 後すぐ破棄 (Postgres は checkpoint まで保持)。
  • SSTable 自体が過去状態を保存するため、WAL は MemTable のみを保護。

RocksDB WriteOptions.sync で耐久性を制御。group commit で複数コミットを 1 回の fsync にまとめる。

2.4 SSTable — 不変性の美徳

+-----------------+
| Data Block 1    |  key-value pairs (sorted)
+-----------------+
| Data Block 2    |
+-----------------+
| ...             |
+-----------------+
| Meta Block      |  Bloom filter, stats
+-----------------+
| Meta Index      |
+-----------------+
| Data Index      |  各 Data Block の先頭 key
+-----------------+
| Footer          |  固定サイズ、meta index 位置等
+-----------------+
  • Data Block: 4KB 程度。ブロック内の key は prefix compression (restart interval)。
  • Index: 各ブロックの先頭 key のみ → 二分探索。
  • Bloom Filter: ブロック毎またはファイル全体。「この key 存在するか」に素早く no と答える。

不変性が決定的だ。読んでいる間に誰も書かない → lock-free な読み取り。バックアップも単純なファイルコピー。キャッシュ効率も高い。

2.5 なぜ MemTable が Skiplist か

RocksDB のデフォルトは skiplist。なぜ B+tree や red-black tree でないか:

  1. Lock-free 並行性: CAS で lock-free 挿入が容易。
  2. 単純な実装: B-tree の rebalancing より短くバグが少ない。
  3. 範囲スキャン親和性: leaf が既に linked list。

欠点: B+tree に比べランダムアクセスのキャッシュ効率が低い。RocksDB は skip_list、hash_skip_list (point lookup 中心)、vector (prefix scan 中心) 等を提供する。

3. 読み込みパス — LSM のアキレス腱

3.1 複数箇所を探す

GET(key)
  1. Active MemTable を検査
  2. Immutable MemTables を検査 (flush 中のもの)
  3. L0 SSTables をすべて検査 (overlapping key range)
  4. L1, L2, ... 各レベル 1 つの SSTable のみ (non-overlapping)

最悪の場合 L0 が 5 個 + L1–L6 で 12 箇所。B-tree が O(log N) ページしか読まないのと比べると厳しい。

3.2 Bloom Filter — 「無い」を素早く判定

確率的データ構造で「無いことは確実、あることは確率的」に判定する。

- k 個のハッシュ関数
- m ビット配列
- 挿入: k 個のハッシュ位置に 1
- 問合せ: k 位置すべて 1 → 「ある (確率的)」、そうでなければ「無い (確実)」

偽陽性率 P = (1 - e^(-kn/m))^k。典型値は 10 bits/key で FPR 約 1%。10 億 key で 12.5GB — 払う価値がある。

3.3 Block Cache

頻繁に読まれるブロックをメモリにキャッシュ。RocksDB:

block_cache_size = 16GB
cache_index_and_filter_blocks = true
pin_l0_filter_and_index_blocks_in_cache = true

OS ページキャッシュとは独立管理。圧縮されていても展開後の形でキャッシュ。

3.4 Partitioned Index

インデックス自体が大きくなる問題。100GB DB で 1GB のインデックスだとメモリに全て乗らない。

解決策: partitioned index (RocksDB)。二段インデックス — 小さな top-level のみメモリ、詳細な index block はディスク。

3.5 Point Lookup と Range Scan

Bloom Filter は point lookup のみ有効。Range scan では範囲内の key をすべて見る必要があり Bloom は役に立たない。LSM は range 重視ワークロードで B-tree に劣る。TSDB は「直近データ中心」のクエリパターンで一部補う。

4. Compaction — LSM の心臓かつ悪夢

4.1 なぜ必要か

Compaction が無いと:

  1. Read Amplification 爆発: L0 が無限成長。
  2. Space Amplification: 削除 key や古いバージョンが残り続ける。
  3. ファイル数爆発: fd 枯渇。

Compaction は複数 SSTable を集約して最新 key のみ保持し、tombstone を削除、レベル内 overlap を解消する。

4.2 Size-Tiered Compaction (STCS) — Cassandra デフォルト

同サイズクラスの SSTable が N 個 (デフォルト 4) 溜まったら 1 つにマージ。

初期:   [10MB] [10MB] [10MB] [10MB]
マージ: [40MB]
以降:   [40MB] [40MB] [40MB] [40MB]
マージ: [160MB]

長所: Write Amplification が小さい。短所: Space Amplification が大きい — 最悪 2 倍。

4.3 Leveled Compaction (LCS) — LevelDB/RocksDB デフォルト

レベル毎のサイズ上限。各レベルは全体として key range が重ならない (L0 除く)。

L0: [a-k] [f-p] [l-z]   (overlap 可)
L1: 10MB 上限 — [a-c] [c-g] [g-m] ...   (non-overlapping)
L2: 100MB 上限
L3: 1GB 上限

Ln が上限超過 → 1 つを選び、L(n+1) の overlap する SSTable と統合。

長所: Space Amplification が小さい (約 1.1 倍)。短所: Write Amplification が大きい (最悪 10–30 倍)。

4.4 Universal Compaction (UCS) — RocksDB 専用

STCS に近いが洗練。全 SSTable を L0 に置き、サイズ条件でマージ。Write-heavy かつ read-light (キャッシュ層、ログ収集) に向く。

4.5 FIFO Compaction

時系列専用。古い SSTable を単に 削除。compaction 無し。ログ/メトリクスに完璧。

4.6 Tombstone と Compaction の難儀な舞

Tombstone: 削除マーカー。実削除は compaction 時。Tombstone は「下位レベルの同 key を覆い隠す」役割のため、該当 key が下位から消えるまで残す必要がある。

Cassandra の有名な zombie rows: tombstone が gc_grace_seconds 経過で GC された後、古いバージョンを持つノードが遅れて同期すると削除データが復活。対策: gc_grace_seconds をノードダウン許容時間より長く設定 (デフォルト 10 日)。

4.7 Subcompaction — 並列 Compaction

大きな compaction を複数スレッドで並列処理。RocksDB の max_subcompactions。入力 SSTable の key range を N 分割 → 各サブレンジを独立スレッドでマージ。CPU 競合で read が遅くなるトレードオフ。

4.8 Compaction Scheduling — 芸術の領域

不適切なスケジューリング:

  • compaction が書き込み速度に追いつかない → L0 蓄積 → read が遅い → アプリ側スロットリング → write stall。
  • compaction が攻撃的すぎる → I/O 競合 → レイテンシスパイク。

RocksDB チューニング:

max_background_compactions = 4
level0_file_num_compaction_trigger = 4
level0_slowdown_writes_trigger = 20
level0_stop_writes_trigger = 36
compaction_readahead_size = 2MB
rate_limiter_bytes_per_sec = 100MB

rate_limiter が鍵。compaction が read/write の I/O を奪わないようにする。

5. Write/Space/Read Amplification を数字で

5.1 Write Amplification

Leveled: WA ≈ 1 + (L-1) * T、L=レベル数、T=レベル間サイズ比 (デフォルト 10)。6 レベル、T=10 → WA=51。1 バイト書くと実ディスク 51 バイト。SSD 寿命に致命的。

Size-tiered: WA = L + 1 で遥かに小さい。Cassandra が STCS をデフォルトにする理由。

5.2 Space Amplification

Leveled: 通常 1.1 倍、compaction 中は一時的に最大 2 倍。Size-tiered: 平均 1.5 倍、最悪 2 倍。

5.3 Read Amplification

Leveled: ベストは Bloom がすべて negative、典型で 1–2 ファイルアクセス、最悪はレベル数 + L0 ファイル数。B-tree: O(log N) ページで定数がより小さい。

5.4 RocksDB の Tiered + Leveled ハイブリッド

最近の潮流: 下位レベルは tiered (書込速度)、上位は leveled (空間効率)。RocksDB も level_compaction_dynamic_level_bytes オプションで類似効果。

6. RocksDB 内部

6.1 アーキテクチャ

Facebook が LevelDB を fork した組込 KV store。KV のみ担当、ネットワーク/分散は上位レイヤ。利用例:

  • MyRocks: MySQL ストレージエンジン。
  • TiKV: 分散 KV、各シャードが RocksDB。
  • CockroachDB: Pebble (Go 移植) に移行。
  • Kafka Streams: state store に RocksDB。

6.2 Column Family

1 つの RocksDB インスタンス内に複数 column family。各 CF は独立 LSM:

rocksdb::ColumnFamilyOptions cf_opts;
rocksdb::ColumnFamilyHandle* cf;
db->CreateColumnFamily(cf_opts, "metadata", &cf);
db->Put(WriteOptions(), cf, "key1", "value1");

CF 毎に compaction 戦略、Bloom Filter、block size を変えられる。「テーブル」に相当する概念。

6.3 Write Batch — 原子性

WriteBatch batch;
batch.Put("key1", "value1");
batch.Put("key2", "value2");
batch.Delete("key3");
db->Write(WriteOptions(), &batch);

複数操作が 1 つの WAL レコードとして原子的に適用。ACID の A を提供。

6.4 Snapshot — 一貫した読み取り

const Snapshot* snap = db->GetSnapshot();
ReadOptions ro;
ro.snapshot = snap;
db->Get(ro, "key1", &value);
db->ReleaseSnapshot(snap);

SSTable が不変なので snapshot 実装が容易。compaction は生存 snapshot がある間その sequence 以下を消せない。

6.5 Transaction API

Optimistic (書込時検査) または Pessimistic (2PL)。MyRocks、TiKV は独自 TX 層を重ねる。

6.6 Merge Operator — Increment 最適化

INCR key 的な操作を 1 回で:

db->Merge(WriteOptions(), "counter", "1");

Get または compaction 時にマージ。Cassandra の counter column が内部的にこの原理を使う。

6.7 TTL

SSTable に expiration メタ情報を付与。read 時フィルタ、compaction 時実削除。

7. Cassandra — 分散 LSM の原型

7.1 Dynamo + Bigtable

2008 年 Facebook 発、現 Apache。Amazon Dynamo の partitioning/replication + Google Bigtable のデータモデル。

  • Partitioning: consistent hashing で key をノード分散。
  • Replication: 各 key を N ノードに複製 (RF)。
  • Storage: 各ノードのローカル LSM。

7.2 Write Path

  1. コーディネータノードが受信。
  2. RF ノードへ並列送信。
  3. 各ノードがローカル commit log + MemTable に書き込み。
  4. N 中 W 個 ack → クライアント ack。

W が consistency level。ONE、QUORUM、ALL。読み書き両方 QUORUM で strong consistency。

7.3 Read Repair

R 個の replica から読む → 差分があれば最新に揃える → 最新をクライアントへ。Eventual consistency だが徐々に収束。

7.4 Bloom Filter + Row Cache + Key Cache

  • Row cache: 実 row データ。
  • Key cache: key → SSTable 位置。
  • Bloom Filter: 各 SSTable に存在。

bloom_filter_fp_chance: STCS で 0.01、LCS で 0.1。

7.5 Compaction 選択

  • STCS: デフォルト、書込中心。
  • LCS: 読込中心、SSD 必須。
  • TWCS: 時系列、ウィンドウ毎。
  • DTCS: TWCS の祖、非推奨。

時系列データでは TWCS がほぼ必須。古いウィンドウを丸ごと削除可能。

7.6 Cassandra の苦しみ

JVM の GC pause がレイテンシ直撃、thread-per-request で context switch 多発、複雑な compaction チューニング、read-before-write 不在 (upsert のみ速い、LWT は高コスト)。この苦しみが ScyllaDB を生んだ。

8. ScyllaDB — Cassandra を C++ で書き直す

8.1 Shard-per-core アーキテクチャ

Cassandra プロトコル互換、C++ 再実装。最大の違いは shard-per-core:

  • ノードの各 CPU コアが独立シャード。
  • シャード間通信はメッセージパッシング。
  • スレッド context switch ほぼゼロ。
  • Lock もほぼ無し (シャード内のみ)。

Seastar フレームワーク + DPDK、io_uring、NUMA 活用。

8.2 性能

同一ハードで Cassandra 比 10 倍スループットが珍しくない。特に tail latency (p99) が劇的に低い — GC pause が無いため。

8.3 LSM の再実装

Cassandra の LSM ロジックを移植しつつ、C++ アロケータ最適化、シャード毎独立 LSM、非同期 I/O (io_uring)。SSTable フォーマットは Cassandra 互換 — マイグレーションが容易。

9. TiKV と CockroachDB

9.1 TiKV

CNCF 卒業プロジェクト、Rust 実装、TiDB のストレージ層。

  • データを Region (デフォルト 96MB) で shard。
  • 各 Region は Raft グループで 3 複製。
  • 各ノードの Region データは RocksDB に保存。
  • トランザクションは Percolator (Google 論文) ベース — 2PC + optimistic。

9.2 CockroachDB

Go 実装、Spanner 風マルチリージョン DB。初期は RocksDB、2022 年に Pebble に移行。

Pebble は Go 実装の RocksDB 互換エンジン — CGo 呼び出しオーバーヘッド無し、Go ランタイムとの統合良好。

9.3 なぜ分散 DB は LSM か

分散 DB は書込中心 — Raft log 適用、メタデータ更新、compaction。LSM の順次書込特性がマッチ。また snapshot 生成が容易で region 移動、replica 追加の低コストコピーが可能。

10. B-tree と LSM の比較

10.1 一覧

特性B-tree (Postgres, InnoDB)LSM (RocksDB, Cassandra)
書込in-placeappend-only
書込速度低 (ランダム I/O)高 (順次 I/O)
読込速度高 (O log N)低 (複数レベル)
Range scan優 (leaf linked list)並 (merge iterator)
Write Amplification約 3 倍10–30 倍 (leveled)
Space Amplification1.2–1.4 倍1.1–2 倍
バックアップ難易 (不変ファイルコピー)
Compaction/VACUUM必要必要 (より重い)
SSD 寿命有利不利
運用複雑度低高

10.2 それぞれのスイートスポット

  • B-tree: 読書バランス、複雑クエリ、ACID、OLTP。
  • LSM: 書込集中、時系列、ログ、KV、分散シャード。

10.3 現代の収束

両陣営は互いに似てきている:

  • B-tree 陣営: COW B-tree (LMDB、WiredTiger) — in-place ではない。
  • LSM 陣営: hybrid compaction — 上位 tiered、下位 leveled。

共通目標は 「順次 I/O 親和的だが読込効率も確保」。

11. 運用の現実

11.1 RocksDB チューニング

write_buffer_size = 256MB
max_write_buffer_number = 4
min_write_buffer_number_to_merge = 2
target_file_size_base = 128MB
max_bytes_for_level_base = 1GB
max_bytes_for_level_multiplier = 10
compression_per_level = [none, none, zstd, zstd, zstd, zstd, zstd]
bloom_filter_bits_per_key = 10
cache_index_and_filter_blocks = true
block_cache = 16GB
rate_limiter = 100MB/s

L0/L1 は無圧縮 (flush/compaction 速度優先)、L2+ は zstd (保存効率優先)。

11.2 モニタリング指標

rocksdb.compaction.write.bytes
rocksdb.estimate.num.keys
rocksdb.block.cache.hit
rocksdb.block.cache.miss
rocksdb.bloom.filter.useful
rocksdb.write.stall
rocksdb.pending.compaction.bytes

pending.compaction.bytes が増えたら warning、倍まで増えたら write stall 直前。

11.3 運用事故パターン

  • Compaction 追いつかず: 書込集中 + compaction 遅い → L0 蓄積 → write stall。対策: compaction スレッド増、書込 throttle。
  • Bloom の効かない range scan 多発: p99 急騰。対策: クエリパターン見直し、prefix Bloom 検討。
  • Snapshot 保持で compaction 止まる: 長期 iterator が snapshot 保持すると古いデータを消せない。「LSM 版 idle in transaction」。

11.4 バックアップ戦略

SSTable 不変 → hardlink で即座バックアップ可能。

BackupEngine::CreateNewBackup(db)

新 SSTable 生成時に backup engine に link 追加、古い backup 削除時に link 解除。

11.5 災害復旧

LSM は WAL + SSTable のみあれば再構成可能。

1. Checkpoint を強制
2. WAL + SSTable ディレクトリをコピー
3. 復旧ノードでロード + WAL リプレイ

Cassandra の nodetool snapshot がこの役割。

12. 高度なトピック

12.1 Wisckey — Key-Value 分離

2016 年論文。大きな value (1KB+) が compaction の write amp の主犯。解決: key のみ LSM、value は別 append-only log、LSM entry は (key, value_pointer)。

RocksDB の BlobDB、Pebble、Badger DB がこの原理を採用。

12.2 Monkey — Bloom Filter 最適化

2017 年論文。全レベル同じ FPR は非効率。上位 (小さく頻繁アクセス) は密に、下位 (大きく稀アクセス) は疎に。同じメモリで read スループット 2 倍。

12.3 REMIX / Dostoevsky

Compaction 戦略の数学的最適化。Leveled と tiered のハイブリッド。最近の RocksDB もこの方向。

12.4 Learned Index

Kraska et al. 2018。インデックスを ML モデルで代替。予測可能な分布のデータでは B-tree/Bloom Filter 比でメモリ節減可能。

13. どのエンジンをいつ使うか

13.1 決定木

  1. ACID が必要? → Postgres/MySQL (B-tree)。
  2. 時系列/ログ? → InfluxDB/ClickHouse/TimescaleDB。
  3. 分散 KV/wide-column? → Cassandra/ScyllaDB/DynamoDB (LSM)。
  4. 大規模分析? → ClickHouse (MergeTree は LSM 系)。
  5. 組込 KV? → RocksDB/LevelDB。
  6. その他: まず Postgres で大抵大丈夫。

13.2 新興選択肢

FoundationDB、ScyllaDB、TiKV/TiDB、CockroachDB、Neon/PlanetScale/Crunchy。すべて LSM または B-tree (またはその変形) を使う。根本原理は 30 年前と同じ。

結び — 順次 I/O 礼賛

LSM-Tree のあらゆる設計判断は 「順次 I/O はランダム I/O より圧倒的に速い」 の一文から出発する。書込をメモリに集約、ディスクに順次 flush、バックグラウンドで merge。この単純な発想が NoSQL 革命の基盤となった。

しかし LSM は無料ではない。Read Amplification、Write Amplification、compaction オーバーヘッド、複雑なチューニング。だから B-tree は死んでいない。Postgres も MySQL/InnoDB も健在。

答えは ワークロードを理解すること。書込集中なら LSM、複雑クエリ/トランザクションなら B-tree、両方必要ならハイブリッド — hot は Postgres、cold は ClickHouse、state store は RocksDB のような組み合わせ。

運用者として 3 つの本能:

  1. Write Amplification を測れ。SSD 寿命が懸かる。
  2. Compaction 速度を監視せよ。書込に追いつかないと災厄。
  3. Bloom Filter を信頼しつつ検証せよ。FPR はチューニングの第一歩。

次回は ClickHouse MergeTree の内部構造。LSM の従兄弟であり OLAP の現王者。カラム保存、sparse index、materialized view が LSM 原理の上でどう積み上がるかを見る。

Discuss on Twitter • View on GitHub