> [!abstract] 概要 > Log-structured merge-tree（LSM-tree）はキーバリューストアの構築に広く使われている。 > LSM-tree は読み取りアンプリフィケーションを減らすため、重なり合うソート済みランを定期的にコンパクションする。 > コンパクション方針に関する先行研究は、書き込みアンプリフィケーション（WA）と読み取りアンプリフィケーション（RA）のトレードオフに焦点を当ててきた。 > 本論文では、LSM-tree におけるコンパクション操作を、システムの将来のクエリスループットを改善するための計算資源と I/O 帯域の投資として扱い、それによってコンパクション方針設計を再考することを提案する。 > 典型的な LSM-tree アプリケーションは安定した中程度の書き込みストリームを処理し、書き込み停止によるデータ損失を避けるため、小さなソート済みランの上位レベルへのフラッシュに資源を優先する。 > したがってコンパクション方針の目標は、平均クエリスループットを最大化するために、ソート済みラン数を最適に保つことである。 > コンパクションと読み取り操作は同じ資源プールから CPU と I/O を奪い合うため、コンパクションの適切な時点と積極度を決めるには共同最適化が必要である。 > 本論文は LSM-tree の三レベルモデルを導入し、ワークロード特性に応じた最適コンパクション方針を見つける動的計画法ベースのアルゴリズム EcoTune を提案する。 > RocksDB 上の評価では、EcoTune は平均クエリスループットを Leveling 方針比 1.5〜3 倍、範囲/ポイントクエリ比を持つワークロードで Lazy Leveling 方針比最大 1.8 倍改善する。 ## 論文情報 | 項目 | 内容 | |---|---| | タイトル | Rethinking The Compaction Policies in LSM-trees | | 著者 | [[Hengrui Wang]]、[[Jiansheng Qiu]]、[[Fangzhou Yuan]]、[[Huanchen Zhang]] | | 所属 | [[Tsinghua University]]、[[Shanghai Qi Zhi Institute]]（Huanchen Zhang の兼務） | | 媒体 | Proceedings of the ACM on Management of Data 3(3), Article 207（SIGMOD 2025） | | 出版日 | 2025-06 | | DOI | 10.1145/3725344 | | PDF | `[[.raw/papers/acm-3725344.pdf]]` | ## 概要 本論文は、LSM ツリーのコンパクション方針を「書き込みアンプリフィケーション対読み取りアンプリフィケーション」から「平均クエリスループットへの資源投資」へ捉え直す。現代 SSD ではフラッシュ用の CPU/I/O を予約すれば書き込み性能はコンパクション方針に左右されにくいため、残り資源をコンパクションとクエリのどちらに使うかが中心問題になる。 提案手法 [[EcoTune]] は、LSM ツリーを top/main/last の三つの論理レベルで見直し、コンパクションラウンド内で早い時点ほど積極的に、終盤ほど怠惰にコンパクションする方針を動的計画法で求める。[[RocksDB]] ベース実装で、範囲スキャン比率・コア数・SSD 種別・書き込み速度を変えた評価を行い、平均スループットとキューイングを含むレイテンシで既存方針を上回る。 ## 問題設定 LSM ツリーはメムテーブルに書き込みを受け、ソート済みラン（SSTable）としてディスクへフラッシュし、複数ランをコンパクションで統合する。従来の Leveling は各レベルに 1 ランだけを許し、読み取りアンプリフィケーションを下げる一方で大量の再書き込みを生む。Lazy Leveling や Tiering は書き込みアンプリフィケーションを下げるが、ラン数が増え、範囲スキャンの読み取りコストが増える。 先行研究は多くの場合、グローバルコンパクション直前の最悪ケース RA を基準にしていた。しかし本論文は、長時間稼働するキーバリューサービスでは、コンパクションラウンド全体の平均クエリスループットがより重要だと主張する。コンパクションはラン数を減らして将来のクエリを速くするが、その実行中は CPU/I/O を占有し、クエリを遅らせる。この二面性を扱うため、コンパクションの「費用」と「効果が続く時間」を同時に考える必要がある。 ## 提案手法 ### 投資としてのコンパクション コンパクションは、CPU と I/O 帯域を消費してソート済みラン数を減らす投資である。即時の見返りはクエリが調べるラン数の減少だが、その投資効果は次のグローバルコンパクションまでしか続かない。したがって、同じデータ量をマージするコンパクションでも、ラウンド初期に行うほど効果が長く続き、ラウンド終盤に行うほど効果が小さい。 この観察から、理想的な方針はラウンド初期に積極的、終盤に怠惰になる。従来の物理レベルは同じレベル内のランを同サイズに保つため、時点ごとに異なる積極度を表現しにくい。本論文は物理レベルを捨て、ソート済みラン集合を top/main/last の論理レベルへ再分割する。 ### 三レベルモデル - **top level**: SSD 上の書き込みバッファ。小さいランは範囲フィルタで I/O 数への影響が小さいため、ここではコンパクションしない。プローブ CPU オーバーヘッドを抑えるため、キーからラン ID への full index を持つ。 - **main level**: 範囲スキャン性能を支配する大きなラン集合。EcoTune の動的計画法がここでのコンパクション方針を決める。 - **last level**: 空間アンプリフィケーションを抑えるため 1 ランのみを許す。main level が容量上限に達するとグローバルコンパクションで last level へ統合する。 top level の容量は、全体サイズを $M$、長い範囲スキャンの平均キー数を $K$ として、おおむね $S=M/K$ に設定する。実装では full index のメモリ増加を制限するため $S=M/max(100,K)$ とし、平均ビット数は約 0.8 bpk 増える。 ### EcoTune の動的計画法 EcoTune は、各 top-to-main コンパクション（TMC）で作られる単位ランを対象に、main level 内コンパクション（MLC）をいつ、どの単位ラン集合に対して行うかを解く。基本形では、既存ラン数 $e$ とこれから来る単位ラン数 $c$ の問題を $(e,c)$ とし、最初の最終ランのサイズ $x$ を全探索することで部分問題に分解する。 論文はさらに、MLC 中もクエリを処理できる現実的条件を扱うため $(e,c,m)$ へ拡張し、MLC が $T_w$ より長く pending sorted runs を生む場合を $(e,b,c,m)$ で扱う。最終版の計算量は $O(R^5)$ だが、実験ではグローバルコンパクションが約 160 秒、コンパクションラウンドが約 350 秒かかるのに対し、方針解決は 1 秒未満で済む。 ## 新規性 - コンパクション方針の目的を、WA/RA の静的トレードオフから平均クエリスループット最大化へ置き換えた。 - コンパクションの時点が投資効果の持続時間を決めるという観察を方針設計に入れた。 - 物理レベルに基づく固定的な積極度ではなく、top/main/last の論理三レベルモデルを導入した。 - RocksDB ベース実装で、既存の Leveling、Lazy Leveling、Moose と比較した。 ## 実験設定 - 実装: Dostoevsky（RocksDB ベース）に EcoTune と Moose を実装。 - ベースライン: Leveling（RocksDB 既定方針）、Lazy Leveling、Moose。 - ハードウェア: AMD EPYC 7742 64-Core、L3 512MB、800GB Intel Optane SSD DC P5800X、3TB D7-P5620 NVMe SSD。 - データ: SOSD の books / osm、64-bit integer key、256 バイト value。 - フィルタ: 各ファイルに SNARF range filter、14 bpk。データブロック用 block cache は 8MB。 - 書き込み速度: 主に 100MB/s。Meta 報告の実ワークロード最大 45MB/s より高く設定。 - クエリ: 長い範囲スキャン（Seek + 100 Next）比率を 0.1〜1.0 で変化。残りは Get と Seek を同数。 ## 実験結果 - 表2では、Optane SSD / NVMe SSD の双方で 1L/2L/3L 方針と CPU コア数を変えても、平均/P99 書き込みレイテンシはほぼ変わらない。100MB/s の書き込み下でも、フラッシュ用資源を予約すればコンパクション方針は書き込み性能に大きく影響しない。 - 図1では、従来の瞬時 RA 分析なら Leveling が有利に見えるにもかかわらず、実験では Leveling のクエリスループットが Lazy Leveling の 64% にとどまる。Leveling がクエリに使える CPU の 62% 超をコンパクションで消費するためである。 - 図7・図8では、EcoTune が長い範囲スキャン比率 0.1〜1.0 の範囲で一貫して最高スループットを示し、Leveling 比 30〜150%、Lazy Leveling 比 15〜80% 改善する。第 2 位手法比では最大 1.8 倍になる。 - 図9では、キューイングを含むクエリレイテンシで EcoTune が最小となり、Leveling 比最大 4 桁、Lazy Leveling 比最大 3 桁の低下を示す。30K/s のスパイクあり到着でも、均一到着比のレイテンシ増加は 2 倍未満にとどまる。 - 表9の YCSB 偏りワークロードでは、EcoTune は Optane で 174.80 KOPS、NVMe で 122.86 KOPS を示し、Lazy Leveling を約 15% 上回る。Leveling はキャッシュ無効化の影響も受け、EcoTune は約 6 倍の平均スループットを示す。 ## 考察 本論文は、LSM ツリーのコンパクションを「できるだけ早く読み取りアンプリフィケーションを下げる」問題として扱うと、現代 SSD では過剰に積極的な方針へ傾くことを示す。コンパクションはクエリと同じ CPU/I/O 資源を奪い合うため、平均性能では「しないほうがよいコンパクション」が存在する。 一方で、EcoTune の方針はワークロード特性を必要とする。論文は長い範囲スキャン比率、書き込み速度、コンパクション速度の 3 パラメータを追跡すればよいと述べるが、クエリ到着率そのものに応じてコンパクション方針を変える点は将来課題として残る。平均スループット最大化とレイテンシ最小化は一致しない場合があり、MLC スレッドとクエリスレッドの配分はさらに別の制御問題になる。 ## 強み / 弱点・課題 **強み** - 従来の WA/RA だけでは見えない、コンパクションとクエリの資源競合を中心に据えた。 - Leveling が理論上の RA では有利でも平均スループットで劣る反例を具体的に示した。 - 動的計画法の入力パラメータが少なく、方針解決コストもラウンド時間に比べて小さい。 - スループットだけでなく、キューイングを含むレイテンシまで評価した。 **弱点・課題** - 主評価は特定の RocksDB ベース実装、特定の SSD、SOSD/YCSB ワークロードに依存する。 - 長い範囲スキャン比率を中心にモデル化しており、複雑な混合クエリやアプリケーション固有キャッシュ効果は単純化されている。 - 方針は平均スループット最適化であり、レイテンシ SLO や到着率変動に合わせた制御は今後の研究として残る。 - top level full index のメモリ増加は約 0.8 bpk と説明されるが、巨大データ・多テナント環境での運用上限は追加検証が必要である。