LSMツリーにおける圧縮ポリシーの再考

ログ構造マージツリー（LSMツリー）は、キーバリューストアを構築するために広く使用されています。これらは、読み取り増幅を減少させるために、重なり合ったソートされたランを定期的に圧縮します。これまでの圧縮ポリシーに関する研究は、書き込み増幅（WA）と読み取り増幅（RA）とのトレードオフに焦点を当ててきました。本論文では、LSMツリーにおける圧縮操作を、システムの将来のクエリスループットを改善するための計算およびI/O帯域幅への投資として扱うことを提案し、圧縮ポリシーの設計を再考します。典型的なLSMツリーのアプリケーションは、安定したが中程度の書き込みストリームを処理し、書き込み停止によるデータ損失を避けるために、小さなソートされたランのトップレベルフラッシュにリソースを優先的に配分します。したがって、圧縮ポリシーの目標は、平均的なクエリスループットを最大化するために最適な数のソートされたランを維持することです。圧縮と読み取り操作は同じプールからCPUおよびI/Oリソースを競合するため、圧縮の適切なタイミングと積極性を決定するために共同最適化を行う必要があります。LSMツリーの三層モデルを導入し、ワークロードの特性に基づいて最適な圧縮ポリシーを見つけるための動的プログラミングに基づくアルゴリズムEcoTuneを提案します。RocksDBでの評価により、EcoTuneは、範囲/ポイントクエリ比のワークロードにおいて、レベリングポリシーに対して平均クエリスループットを1.5倍から3倍、レイジーレベリングポリシーに対して最大で2.5倍改善することが分かりました。