DostoevskyがLSM-treeの無駄なマージを排除し、性能とストレージを両立
Better Space-Time Trade-Offs for LSM-Tree Based Key-Value Stores [pdf]
LSM-treeベースのキーバリューストアは、更新コストとルックアップ・ストレージコストの間で最適でないトレードオフを行っている。本研究では、最大レベル以外のマージ操作がこれらの指標をほとんど改善しない点に着目し、Lazy LevelingとFluid LSM-treeを導入。さらに、ワークロードとハードウェアに応じて設計空間を適応的にナビゲートするDostoevskyを提案する。RocksDB上に実装し、最先端設計を性能とストレージの両面で厳密に上回ることを示した。
最大レベル以外のすべてのレベルでのマージ操作（つまりほとんどのマージ操作）は、ポイントルックアップコスト、長距離レンジルックアップコスト、およびストレージ空間をごくわずかしか改善しない一方で、更新の償却コストを大幅に増加させる。