# LSMツリーコンパクション ## 定義 LSM ツリーコンパクションは、ディスク上の複数のソート済みラン（SSTable）をマージしてラン数を減らし、削除済みデータや古いバージョンを整理し、読み取りアンプリフィケーションと空間アンプリフィケーションを制御するバックグラウンド処理である。従来は書き込みアンプリフィケーション（WA）と読み取りアンプリフィケーション（RA）のトレードオフとして扱われてきたが、[[@2025__SIGMOD__Rethinking The Compaction Policies in LSM-trees]] は、現代 SSD ではコンパクションを将来の平均クエリスループットへ投資する CPU/I/O 資源配分問題として捉え直す。 ## 横断的知見 - **コンパクションは永続化構造の保守から、資源スケジューリング問題へ移る**: Bigtable 2006 はコンパクションを SSTable 群の整理機構として説明し、Bigtable 20 年史は外部コンパクションでタブレットサーバの CPU/RAM をユーザーリクエストへ残す設計を示した。EcoTune はさらに単一ノード内で、コンパクションとクエリが同じ CPU/I/O を奪い合う前提から、平均クエリスループットを最大化する時点選択問題として定式化する。つまり LSM コンパクションの論点は「どのランをマージするか」から「どの資源階層・どの時点でマージするか」へ広がっている。(Source: [[@2006__OSDI__Bigtable - A Distributed Storage System for Structured Data]], [[@2026__SIGMOD Companion__Twenty Years of Bigtable]], [[@2025__SIGMOD__Rethinking The Compaction Policies in LSM-trees]]) - **読み取りアンプリフィケーション最小化は平均性能最大化と一致しない**: EcoTune の図1では、Leveling は従来の瞬時 RA 分析で有利でも、コンパクションが CPU の 62% 超を消費し、平均クエリスループットが Lazy Leveling の 64% に落ちる。LSM ツリーでは、コンパクションが「読み取りを速くする処理」であると同時に「読み取りを妨げる処理」でもある。(Source: [[@2025__SIGMOD__Rethinking The Compaction Policies in LSM-trees]]) - **現代 SSD は WA/RA だけでなく、フラッシュ優先と残余資源配分の二層制御を要求する**: EcoTune は、書き込みストリームが安定して中程度で、フラッシュ用 CPU/I/O を予約できるなら、残り資源上のコンパクション方針は書き込みレイテンシにほぼ影響しないと示す。これは Bigtable 20 年史の「ユーザーリクエスト処理と高価なファイル構築を分離する」運用知見と同型である。(Source: [[@2025__SIGMOD__Rethinking The Compaction Policies in LSM-trees]], [[@2026__SIGMOD Companion__Twenty Years of Bigtable]]) - **教科書の size-tiered/leveled 二分法は、EcoTune の「資源投資問題としてのコンパクション」より粗い、実装非依存の経験則である**: DDIA 第4章は size-tiered compaction(新しく小さい SSTable を古く大きい SSTable へ逐次マージ、高い書き込みスループットだが一時的に多くのディスク空間を要する)と leveled compaction(SSTable サイズを固定し L0, L1, ... のレベルへ段階的にマージ、ディスク使用量を抑え読み取りに有利)を対比し、「書き込み多・読み取り少なら size-tiered、読み取り中心なら leveled」という経験則を提示する。EcoTune はこの経験則の中の leveled 系だけをさらに分解し(Leveling vs Lazy Leveling)、瞬時の読み取りアンプリフィケーションでは Leveling が有利でも平均クエリスループットではコンパクションのCPU占有により不利になりうると示した。つまり教科書レベルの「どちらの方式か」という選択と、研究レベルの「同じ方式内でどう資源配分するか」という選択は、抽象度の異なる2段階の意思決定として整理できる。(Source: [[@2026__OReilly__Designing Data-Intensive Applications 2E - Chapter 4 Storage and Retrieval]] "Compaction strategies", [[@2025__SIGMOD__Rethinking The Compaction Policies in LSM-trees]]) - **詳説 データベースの3戦略(平準化・サイズ階層化・時間枠)の教科書的解説は、DDIAが提示するsize-tiered/leveledの二分法にtime window compactionという第3の戦略を追加し、テーブル枯渇というsize-tiered固有の弱点も明示する**: 既存知見(本概念)はDDIA第4章のsize-tiered/leveled二分法を、EcoTuneの資源投資問題化の前段にある一般化された経験則と位置づけていたが、詳説 データベース第7章はこれをさらに具体化する。テーブル枯渇(コンパクション後も小さいテーブルが上位レベルに昇格せず墓石が考慮されなくなるsize-tiered固有の問題で、強制コンパクションが必要になる)と、有効期限付き時系列データに対する時間枠コンパクション(Apache Cassandra実装、期限切れファイルをコンパクションなしで破棄可能)という、DDIAの教科書的説明には現れない実装上の弱点・第3戦略を補う。またRocksDB(Leveling既定)は最下位レベル到達まで、Cassandraは結果整合性のためGC猶予期間到達まで墓石を保持するという、コンパクション戦略と墓石保持ポリシーの相互作用も具体化する。(Source: [[@2021__OReillyJapan__詳説 データベース - Chapter 7 ログ構造化ストレージ]] §7.1.6, §7.1.6.1, §7.1.6.2, [[@2026__OReilly__Designing Data-Intensive Applications 2E - Chapter 4 Storage and Retrieval]] "Compaction strategies") ## 未解決の問い - EcoTune が将来課題とするクエリ到着率依存のコンパクションは、平均スループット最適化とレイテンシ SLO 制御をどのように同時に扱うべきか。 - 外部コンパクション（Bigtable）とノード内動的計画法（EcoTune）は、クラウドマネージド KVS で組み合わせられるか。コンパクションジョブのオートスケール、失敗時リトライ、SSTable 導入前検証まで含めた目的関数が必要ではないか。 - full index や range filter を前提に top level コンパクションを省く方針は、巨大テーブル、多テナント、更新・削除が多いワークロードでどの程度安定するか。 - DDIA が示す「少数キーを高頻度・大量キーを低頻度で書くワークロードでは leveled が有利」という経験則は、EcoTune の平均スループット最適化モデルにどう定式化して組み込めるか。 ## 関連 - 親概念: [[LSMツリー]] - ソース: [[@2025__SIGMOD__Rethinking The Compaction Policies in LSM-trees]] / [[@2006__OSDI__Bigtable - A Distributed Storage System for Structured Data]] / [[@2026__SIGMOD Companion__Twenty Years of Bigtable]] / [[@2026__OReilly__Designing Data-Intensive Applications 2E - Chapter 4 Storage and Retrieval]] / [[@2021__OReillyJapan__詳説 データベース - Chapter 7 ログ構造化ストレージ]] - エンティティ: [[EcoTune]] / [[RocksDB]] / [[Bigtable]] / [[Apache Cassandra]] ## 出典 - [[@2025__SIGMOD__Rethinking The Compaction Policies in LSM-trees]]（§3 コンパクション再考、§4 EcoTune、§5 評価） - [[@2006__OSDI__Bigtable - A Distributed Storage System for Structured Data]]（SSTable とコンパクション） - [[@2026__SIGMOD Companion__Twenty Years of Bigtable]]（外部コンパクション、SSTable 導入前検証） - [[@2026__OReilly__Designing Data-Intensive Applications 2E - Chapter 4 Storage and Retrieval]]（§Compaction strategies — size-tiered/leveled compactionの教科書的定義と経験則） - [[@2021__OReillyJapan__詳説 データベース - Chapter 7 ログ構造化ストレージ]]（§7.1.6 平準化・サイズ階層化・時間枠コンパクション、テーブル枯渇、墓石保持ポリシー）