Стратегии слияния (compaction strategies) в LSM-деревьях

Стратегия слияний в LSM-деревьях — проблема, для которой сейчас не существует доказанного оптимального решения. RocksDB, Cassandra, CockroachDB реализуют целый ряд эвристик и предлагают пользователю многочисленные настройки по оптимизации под конкретные сценарии нагрузки.

В докладе я попробую разобрать эту проблему в свете последних изменений в аналогичном алгоритме слияний в движке Vinyl для Tarantool и Picodata, который я реализовал. Разберу различные стратегии, настройки, и техники оптимизации. Коснусь последних статей по теме. В результате, надеюсь, у слушателей появится более целостная картина проблемной области и компромиссов, на которые идут разработчики движков хранения данных.