TL
データベース

LSMコンパクション戦略：Leveled vs Tiered vs FIFO

LSMの書き込み・読み取り・空間の増幅は、コンパクション戦略の選択でほぼ決まります。Leveled・Tiered・FIFO を定量的に対比し、RocksDB と Cassandra での選定基準が掴めます。

応用LSM-TreeコンパクションRocksDBCassandraストレージエンジン最終更新: 2026-06-21
TL;DR要点だけ先に
  • 1.Tiered（Size-Tiered）は同サイズの SSTable を一定数ためて一括マージするため書き込み増幅が小さく（おおむね階層数 log_T(N) に比例）、代わりに各レベルに同キーが残り読み取り・空間増幅が大きい。
  • 2.Leveled は各レベルのキー範囲を重複させず、点読み取りで各レベル高々1ファイルに抑える。読み取り・空間増幅は小さいが、上位レベルへ書き直すため書き込み増幅はおおよそ倍率 fanout（既定10）×レベル数になる。
  • 3.FIFO は古い SSTable を丸ごと破棄するだけでマージしない。TTL 主体の時系列・メトリクスで書き込み増幅をほぼ1にできるが、点検索や更新には使えない特殊用途。

コンパクション戦略が増幅を決める

LSM-Tree は更新をメモリ上の MemTable に追記し、満杯になると不変の SSTable としてディスクへ書き出します。SSTable は放置すると増え続けるため、複数を読んでマージし最新値だけを残す コンパクション で畳みます。重要なのは、LSM の三増幅（書き込み・読み取り・空間）がほぼこのコンパクション戦略で決まる点です。同じエンジンでも戦略を変えるだけで性能特性が大きく動きます。本記事では代表的な Size-Tiered・Leveled・FIFO を、増幅の定量的トレードオフと RocksDB / Cassandra での選定基準で対比します。

3つの増幅は同時に最小化できない関係（RUM トレードオフ）にあり、戦略はその三角形のどの頂点を取るかの選択です。

Size-Tiered（Tiered）：まとめてマージ

Size-Tiered Compaction Strategy（STCS、Cassandra の既定）は、同程度のサイズの SSTable が一定数（しきい値 T、Cassandra 既定 4）たまったら、それらをまとめて1つにマージ します。マージ結果は元の約 T 倍のサイズになり、次のサイズ階層の一員になります。

階層イメージ（T=4）:
小サイズ:  s s s s ─┐ 4個たまった
                    └→ マージ → 中サイズ M
中サイズ:  M M M M ─┐ 4個たまった
                    └→ マージ → 大サイズ L
  • 書き込み増幅：小さい。各データはサイズ階層を1段上がるごとに1回書き直されるだけ。階層数は log_T(全データ量 / MemTable サイズ) 程度で、書き込み増幅もおおむねこの階層数に比例します。受け付け時のシーケンシャル書き込みと合わせ、書き込みスループットに強い。
  • 読み取り増幅：大きい。同じキーの新旧版が複数の階層に分散し得るため、点検索で多数の SSTable を横断しがち。各 SSTable のブルームフィルタが「含まれない」を高速に弾くので緩和されますが、存在するキーや範囲検索では効きません。
  • 空間増幅：大きい。最悪ケースでは、最大の SSTable をマージする瞬間に同等サイズの一時コピーが共存し得るため、瞬間的に データ量の約2倍 のディスクを要します。古い版が大きな SSTable に長く残るのも空間を食う要因です。
STCS の空間ピークに注意

STCS では巨大な SSTable 同士のマージ中、入力と出力が一時的に並存するため、ディスク空き容量が論理データ量と同程度ないとコンパクションに失敗します。大きな SSTable が育つと1回のマージで必要な空き容量も増えるため、空きディスクの監視と上限設計が運用の勘所です。

Leveled：レベルごとにキー範囲を重複させない

Leveled Compaction Strategy（LCS、RocksDB の代表的な選択、LevelDB 由来）は、L0 を除く各レベル L1, L2, ... で SSTable 同士のキー範囲が重複しない よう保ちます。各レベルの容量上限は1段ごとに倍率 fanout（既定 10）で増え、Li が満杯になると、その一部 SSTable を Li+1 の重なるファイルと書き直してマージします。

  • 読み取り増幅：小さい。L1 以降は各レベルでキー範囲が一意なので、ある点キーは各レベルで 高々1ファイル しか見ずに済みます。読むファイル数がレベル数で上限を持ち、安定します。
  • 空間増幅：小さい。各レベルにキーは原則1版しか残らず、古い版が早く回収されます。RocksDB のドキュメントでは空間増幅をおおむね 1.1 倍程度 に抑えられるとされます。
  • 書き込み増幅：大きい。Li から Li+1 へ押し上げる際、対象キー範囲に重なる Li+1 側の既存ファイル（平均 fanout 個程度）を巻き込んで書き直すため、1レベル昇格あたり約 fanout 倍の書き直しが発生します。全体ではおよそ fanout × レベル数 の倍率になり、STCS より大きくなりがちです。
Leveled（fanout=10）:
L0  : 新着 SSTable（キー範囲は重なってよい）
L1  : ─────────────  合計 ~ 数百MB（範囲重複なし）
L2  : ───────────────────────  ~10倍
L3  : ...                      ~10倍
点検索: 各レベル高々1ファイル → 読むファイル数が安定
L0 だけは例外

L0 は MemTable のフラッシュ直後の SSTable が並ぶレベルで、ここだけはファイル間でキー範囲が重複し得ます。そのため点検索では L0 の全ファイル（既定で数個）を見る必要があり、L0 のファイル数がたまると読み取りが重くなります。RocksDB が L0→L1 のコンパクションを優先するのはこのためです。

FIFO：マージせず古いものを捨てる

FIFO Compaction（RocksDB の FIFO、Cassandra の TWCS が近い思想）は、マージを一切せず、合計サイズや TTL の上限を超えたら最も古い SSTable を丸ごと削除 します。

  • 書き込み増幅：ほぼ1。一度書いた SSTable は二度と書き直されず、寿命が来たら削除されるだけ。書き込み負荷が最小です。
  • 用途は限定的。点検索は全 SSTable を横断しかねず、古いキーは「マージで上書き」されず削除を待つだけなので、任意キーの更新・点検索を伴うワークロードには不向き。
  • 時系列・メトリクス・ログの定番。新しいデータだけ読み、古いデータは期限で捨てる用途（直近 N 日のみ保持するメトリクス等）に最適です。Cassandra では時間窓ごとに SSTable を分け期限切れ窓を丸ごと落とす TWCS（TimeWindowCompactionStrategy） が同じ狙いで、トゥームストーンや TTL データの回収に強みがあります。

定量比較と選定基準

観点Size-TieredLeveledFIFO / TWCS
書き込み増幅小（~階層数, T依存）大（~fanout×レベル数）最小（~1）
読み取り増幅（点）大（多数SSTable横断）小（各レベル高々1）大（横断、要TTL前提）
空間増幅大（最悪~2倍, 一時コピー）小（~1.1倍）小（期限で削除）
範囲スキャン苦手（重複多い）得意（範囲が一意）時間窓に整列なら良
向くワークロード書き込み多め・更新中心読み多め・空間制約ありTTL前提の時系列/ログ

RocksDB と Cassandra での実務的な選定基準は次のとおりです。

エンジン既定/代表他の選択肢切り替えの目安
RocksDBLeveled（読み・空間を重視）Universal(≒Tiered) / FIFO書き込み律速・WA削減なら Universal、キャッシュ層やTTLログなら FIFO
CassandraSize-Tiered（STCS, 書き込み重視）Leveled(LCS) / TimeWindow(TWCS)読み多め・空間制約なら LCS、時系列・TTLデータなら TWCS
判断の起点はワークロードの読み書き比とデータ寿命

書き込みが律速で更新が分散するなら Size-Tiered（Cassandra なら既定 STCS、RocksDB なら Universal）。読み取りレイテンシの安定や空間効率が要るなら Leveled。データに自然な寿命（TTL）があり古いものを捨てるだけでよいなら FIFO / TWCS。まず「読み書き比」と「データ寿命の有無」の2軸で当たりをつけ、増幅を実測して詰めるのが定石です。

試験・面接で問われる要点

Tiered=書き込み増幅小・読み取りと空間増幅大／Leveled=読み取りと空間増幅小・書き込み増幅大／FIFO=書き込み増幅最小だがTTL用途専用、という対応を即答できるように。Leveled の読み取りが安定する理由は L1 以降でキー範囲が重複せず点検索が各レベル高々1ファイルで済むから、STCS の空間ピークが約2倍になる理由は 大SSTableのマージ中に入力と出力が一時並存するから、が頻出です。

まとめ

まとめ

LSM の三増幅はコンパクション戦略でほぼ決まります。Size-Tiered は同サイズの SSTable をまとめてマージし書き込み増幅を抑える代わりに読み取り・空間増幅が大きく、Leveled はレベルごとにキー範囲を重複させず読み取り・空間増幅を小さく抑える代わりに書き込み増幅が大きく、FIFO / TWCS はマージせず期限で捨てて書き込み増幅をほぼ1にする TTL 専用戦略です。RocksDB は Leveled を軸に Universal / FIFO を、Cassandra は STCS を既定に LCS / TWCS を選びます。選定の起点は読み書き比とデータ寿命で、より広いエンジン比較はストレージエンジンの系譜や B+Tree vs LSM-Tree 比較図も併せて押さえると体系が掴めます。

データベース Article

LSMコンパクション戦略：Leveled vs Tiered vs FIFOを実務で読む

TL;DRは入口です。実際に選ぶ・使う段階では、何を解決するか、何と比較するか、導入後にどこで詰まるかまで見る必要があります。

解決すること

LSM-Tree

比較で見る軸

難易度: advanced / カテゴリ: データベース / タグ数: 5

導入後に効く点

Leveled は各レベルのキー範囲を重複させず、点読み取りで各レベル高々1ファイルに抑える。読み取り・空間増幅は小さいが、上位レベルへ書き直すため書き込み増幅はおおよそ倍率 fanout（既定10）×レベル数になる。

先に潰すリスク

用語だけ覚えても、設計・実装・運用でどこに効くかを確認しないと判断を誤る。

数字・仕様の読み方
難易度
advanced
カテゴリ
データベース
タグ数
5

判断チェックリスト

  • 自社の用途が「LSM-Tree / コンパクション」に近いか確認する。
  • 強みである「Tiered（Size-Tiered）は同サイズの SSTable を一定数ためて一括マージするため書き込み増幅が小さく（おおむね階層数 log_T(N) に比例）、代わりに各レベルに同キーが残り読み取り・空間増幅が大きい。」が本当に評価軸になるか確認する。
  • 注意点の「用語だけ覚えても、設計・実装・運用でどこに効くかを確認しないと判断を誤る。」を運用で吸収できるか確認する。
  • 公開値や仕様値は、対象プラン・対象機種・対象リージョンまで確認する。
  • 既存システム、ID、ネットワーク、監視、バックアップとの接続方法を先に洗い出す。
  • 小さく試してから、本番移行、権限設計、障害時手順、コスト監視を決める。

次に確認する観点

LSM-TreeコンパクションRocksDBCassandraストレージエンジンLSM-TreeコンパクションRocksDB
参考: 公式情報