Dostoevsky избавляет LSM-деревья от лишних слияний, ускоряя обновления

Better Space-Time Trade-Offs for LSM-Tree Based Key-Value Stores [pdf]

Исследователи из Гарварда показали, что современные key-value хранилища на основе LSM-деревьев неоптимально балансируют между стоимостью обновлений и стоимостью поиска и занимаемым местом. Причина в том, что они выполняют одинаково дорогие слияния на всех уровнях, хотя слияния на всех уровнях кроме самого большого почти не улучшают поиск и не экономят место, но сильно увеличивают стоимость обновлений. Авторы предлагают Lazy Leveling, Fluid LSM-tree и систему Dostoevsky, которая адаптивно убирает лишние слияния в зависимости от нагрузки и оборудования. Реализация на базе RocksDB строго превосходит существующие решения по производительности и объёму хранилища.