Acheron: Persisting Tombstones in LSM Engines

[stonewhitener]

Resources

• https://doi.org/10.1145/3555041.3589719
• https://docs.google.com/document/d/1d3kN5msiwHGVyFilwON9q607mSmsEjTfcX_suEOEK4A/edit#
• https://disc.bu.edu/papers/sigmod23-acheron
• https://disc-projects.bu.edu/acheron/
• https://disc-projects.bu.edu/acheron/research.html

Summary

LSM-tree における削除は墓石を挿入することによる論理削除と，それが反映される物理削除に分けられるが，物理削除が遅れることでデータ保護規制に違反する可能性がある．FADE (FAst DElete) はユーザー定義のスレッショルドで削除を物理的に反映する手法である．本発表では，FADE や他の手法について墓石のライフサイクルを可視化する Acheron をデモする．SOTA の MinOverlappingRatio や Round-robin と比較してタイムリーな物理削除がであること，それによるカスケードコンパクションや書き込み増幅が低減されることを示した．