Дайджесты для фоновой компактификации динамических таблиц YTsaurus

Фоновая компактификация для удаления устаревших данных в LSM-деревьях традиционно запускается по таймеру - вслепую: на кластерах YTsaurus до 90% данных переписывались без изменений, а период приходилось подбирать вручную. Мы научили компактификацию запускаться по данным: у каждого чанка есть дайджест — сводка в несколько килобайт, по которой заранее видно, сколько места освободит перезапись. Расскажем про структуры данных внутри дайджестов, три алгоритма на их основе и грабли, собранные при раскатке. В продакшне подход срезал поток компактификации в разы, поднял её КПД на порядок и полностью убрал ручную настройку.