LSM-tree: как устроены хранилища, оптимизированные под запись

Прямой ответ

LSM-tree (log-structured merge-tree) — структура хранения, в которой данные не обновляются на месте, а добавляются в конец потока записи. Это даёт предсказуемо высокую скорость записи ценой усложнения чтения. Именно так устроены RocksDB, LevelDB, Cassandra, ScyllaDB, HBase и ClickHouse (в своей специфической форме).

Как проходит запись:

1. Журнал (WAL). Запись сначала добавляется в последовательный журнал на диске. Это гарантирует долговечность при сбое.
2. Memtable. Та же запись попадает в отсортированную структуру в памяти.
3. Flush. Когда memtable заполняется, она выгружается на диск как неизменяемый отсортированный файл — SSTable.
4. Компакция. Фоновый процесс периодически сливает несколько SSTable в один, отбрасывая устаревшие версии и удалённые ключи.

Как проходит чтение: движок проверяет memtable, затем SSTable от новых к старым. Чтобы не открывать каждый файл, используются Bloom-фильтры — они быстро отвечают, что ключа в файле точно нет (см. Bloom-фильтр), а индексы внутри SSTable сужают поиск до нужного блока.

Удаление выполняется записью специального маркера — tombstone. Физически данные исчезают только при компакции, которая увидит этот маркер.

Ключевая характеристика — распределение расходов:

Практика: уровни, настройка и ограничения

Уровни компакции. SSTable организуются в уровни: L0 содержит свежие выгрузки, каждый следующий уровень примерно в десять раз больше. При переполнении уровня часть файлов сливается с перекрывающимися файлами следующего уровня. Отсюда два режима:

• Leveled. Каждый уровень ограничен по объёму, данные одного диапазона ключей хранятся компактно. Чтение дешёвое, запись дороже.
• Tiered (size-tiered). Файлы накапливаются и сливаются крупными партиями. Запись дешевле, но требуется больше места и чтение может затрагивать много файлов.

Выбор режима — прямой компромисс между скоростью записи, объёмом диска и задержкой чтения.

Read amplification. Если ключа нет в базе, наивная реализация просмотрела бы все уровни. Практически это решают Bloom-фильтры и кэш индексных блоков: типичная реализация даёт не более одного-двух чтений на запрос.

Write amplification. Одна логическая запись может быть перезаписана несколько раз при прохождении через уровни. Подробнее о стоимости этого эффекта и об износе накопителей — в статье про write amplification.

Space amplification. До завершения компакции на диске лежат и старые, и новые версии данных. Для баз с активной перезаписью запас места в полтора-два раза — нормальная практика.

-- ClickHouse: явная модель LSM-подобного хранения — партиции и фоновые слияния
SELECT partition, count() AS parts, sum(bytes_on_disk) AS bytes
FROM system.parts
WHERE database = 'metrics' AND table = 'events' AND active
GROUP BY partition ORDER BY bytes DESC LIMIT 10;

Рекомендации:

1. Не считайте LSM «быстрым везде». Он выигрывает на последовательной записи больших объёмов. Для точечных обновлений небольшого набора строк B-tree часто проще и предсказуемее — сравнение в статье про B-tree.
2. Следите за числом частей. Рост количества SSTable или частей в ClickHouse — признак, что компакция не успевает за записью. Это приводит к деградации чтения.
3. Планируйте место под компакцию. Пиковое потребление диска во время слияния может быть существенно выше полезного объёма.
4. Помните про tombstone. Массовые удаления создают много маркеров; пока они не обработаны компакцией, чтение диапазонов может замедляться.
5. Измеряйте на своём профиле. Настройка уровней и размера memtable сильно зависит от соотношения чтения и записи; универсальных значений нет.

Практический сценарий: деградация чтения после миграции на LSM-движок

Контекст: сервис перешёл с PostgreSQL на Cassandra для потока событий. Запись ускорилась в несколько раз, но p99 чтения вырос со 12 мс до 180 мс.

1. Диагностика. На узле оказалось в среднем 34 части на партицию при норме до десяти. Компакция не успевала за скоростью записи.
2. Причина 1. Размер партиции был выбран по календарному месяцу, из-за чего вся запись шла в одну партицию, а компакция конкурировала с ней за ресурсы.
3. Причина 2. В запросах использовалось условие по колонке без индекса, поэтому движок просматривал много SSTable.
4. Действия. (а) Партиционирование изменили на суточное, что распределило нагрузку; (б) добавили составной первичный ключ, покрывающий типовой запрос, чтобы исключить фильтрацию после чтения; (в) увеличили ресурсы на компакцию и проверили, что число частей вернулось к целевому; (г) включили мониторинг числа частей как алерт-метрику.
5. Результат. p99 чтения вернулся к 18 мс, число частей стабилизировалось на 6–8 на партицию.

Вывод: LSM переносит сложность из момента записи в фоновую компакцию. Если за компакцией не следить, эта сложность возвращается к пользователю в виде задержек чтения.

FAQ

Почему LSM быстрее записывает? Потому что запись превращается в последовательное добавление в журнал и в память вместо случайной перезаписи страниц на диске. Последовательный ввод существенно дешевле случайного, особенно на накопителях с высокой задержкой поиска.

Что такое tombstone и чем он опасен? Это маркер удаления. Пока компакция не обработала его, данные физически присутствуют. Большое число маркеров замедляет чтение диапазонов, потому что движок обязан убедиться, что значение действительно удалено.

Нужны ли транзакции в LSM-движках? Многие из них поддерживают только отдельные операции или лёгкие транзакции в пределах одной партиции. Полноценные транзакционные гарантии — признак реляционных СУБД, см. свойства ACID.

Подходит ли LSM для аналитических запросов? Да, в колоночной реализации: ClickHouse использует партиции и фоновые слияния, что даёт высокую скорость загрузки и сжатия. Но для точечных обновлений и частых удалений он неудобен — это стоит учитывать на этапе проектирования.

Источники: RocksDB docs, Apache Cassandra docs (compaction), Wikipedia (LSM-tree) — ссылки в шапке.