## Memo ## Memo with LLM [[notes/system-engineering/Revisiting B+-tree vs. LSM-tree|LSM-tree]]におけるコンパクション・ポリシーの再評価。従来のWA (Write Amplification) / RA (Read Amplification) トレードオフの視点を脱却し、コンパクションを「将来のクエリ・スループット最大化への投資」と定義。 ### 主な知見 - **投資としてのコンパクション**: コンパクションをRA/WA抑制の管理タスクではなく、CPU/IOリソースを投じて将来のクエリ・スループットを最大化する「投資」として再定義。 - **リソース競合と結合最適化**: コンパクションとクエリ処理のCPU/IOリソース競合を考慮。ワークロード特性に基づき、コンパクションのタイミングと強度を動的に決定する結合最適化アプローチ。 - **EcoTuneアルゴリズム**: 動的計画法 (DP) を用いた最適化アルゴリズム。レンジ/ポイントクエリ比率などのワークロード特性に応じ、スループット最大化のためのポリシーを導出。 - **RocksDBによる評価**: RocksDB実装での評価により、従来のLeveled Compaction比で平均クエリ・スループット1.5〜3倍、Lazy Leveling比で最大2.5倍の向上を確認。 ## Abstract Log-structured merge-trees (LSM-trees) are widely used in key-value stores. Periodically, an LSM-tree compacts overlapping sorted runs to reduce read amplification. Traditionally, research on compaction policies has focused on the trade-off between write amplification (WA) and read amplification (RA). However, this perspective overlooks the fact that compaction and read operations compete for the same CPU and I/O resources. In this paper, we rethink compaction policies from the perspective of query throughput. We treat compaction as an investment in computational and I/O bandwidth to improve future query throughput. We propose EcoTune, an algorithm based on dynamic programming that finds optimal compaction policies tailored to specific workload characteristics. Evaluations on RocksDB show that EcoTune can significantly enhance average query throughput.