# 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]]) ## 未解決の問い - EcoTune が将来課題とするクエリ到着率依存のコンパクションは、平均スループット最適化とレイテンシ SLO 制御をどのように同時に扱うべきか。 - 外部コンパクション（Bigtable）とノード内動的計画法（EcoTune）は、クラウドマネージド KVS で組み合わせられるか。コンパクションジョブのオートスケール、失敗時リトライ、SSTable 導入前検証まで含めた目的関数が必要ではないか。 - full index や range filter を前提に top level コンパクションを省く方針は、巨大テーブル、多テナント、更新・削除が多いワークロードでどの程度安定するか。 ## 関連 - 親概念: [[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]] - エンティティ: [[EcoTune]] / [[RocksDB]] / [[Bigtable]] ## 出典 - [[@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 導入前検証）