LSM-дерево

Log-Structured Merge tree (LSM-дерево) - это структура хранения, оптимизированная для записи. Вместо обновления данных на месте (как в B-tree), она буферизует операции записи в памяти, сбрасывает их на диск в виде неизменяемых отсортированных файлов и периодически объединяет эти файлы в фоновом режиме.

Core components

MemTable - структура данных в оперативной памяти (skip list или красно-чёрное дерево), хранящая данные в отсортированном виде и накапливающая операции записи. Отсортированный порядок позволяет сбрасывать данные на диск сразу в виде готового файла без отдельного шага сортировки.

Write Ahead Log (WAL) - последовательный журнал только для добавления (append-only) на диске. Каждая запись сначала попадает в WAL и только затем - в MemTable. При аварийном завершении процесса данные из WAL воспроизводятся заново, чтобы восстановить MemTable. Правило упреждающей записи в журнал (log-before-you-write) и построенный на нём протокол восстановления появились на десятилетия раньше LSM-деревьев; в книге Грея и Ройтера transaction-processing эта тема разобрана от начала до конца, вплоть до того, что именно контрольная точка (checkpoint) обязана сохранять для корректного воспроизведения.

SSTable (Sorted String Table) - неизменяемый файл с отсортированными парами ключ-значение, который записывается на диск, когда MemTable достигает порогового размера. Будучи записанной на диск, SSTable уже никогда не изменяется.

Bloom filter - вероятностный фильтр принадлежности множеству для каждой SSTable, находящийся в оперативной памяти. Отвечает либо "точно нет", либо "возможно есть", избавляя от большинства лишних чтений с диска.

Write path

1. Добавление в WAL (последовательная запись на диск)
2. Вставка в MemTable (RAM)
3. Когда MemTable заполняется, она замораживается и сбрасывается на диск в виде новой SSTable
4. Очистка сегмента WAL, относящегося к сброшенной MemTable

Все операции записи на диск являются последовательными - никакого случайного ввода-вывода (random I/O). Именно поэтому LSM-деревья справляются с нагрузками на интенсивную запись гораздо лучше, чем B-tree, где каждое обновление приводит к случайной записи страницы на диск.

Read path

1. Проверка MemTable
2. Проверка SSTable от самых свежих к самым старым с остановкой на первом совпадении
3. Фильтр Блума перед проверкой каждой SSTable - если фильтр говорит "точно нет", файл пропускается

Чтение в худшем случае происходит медленнее, чем в B-tree, так как может потребоваться обратиться к нескольким файлам. Компромисс осознанный: оптимизировать запись ценой увеличения объёма чтения (read amplification), а затем снизить накладные расходы на чтение с помощью фильтров Блума и compaction.

Compaction

Фоновое слияние SSTable для сокращения количества файлов, освобождения места от устаревших версий и удаления маркёров удаления (tombstones). Две основные стратегии:

• Leveled (RocksDB, LevelDB) - агрессивное слияние файлов по уровням фиксированного размера. Меньше файлов на уровень означает более быстрое чтение, но повышенное усиление записи (write amplification) из-за частого compaction.
• Size-tiered (Cassandra) - слияние файлов схожего размера. Меньше усиление записи, но задержка чтения колеблется по мере изменения количества файлов.

Where it's used

Cassandra, RocksDB, LevelDB, HBase, ScyllaDB, CockroachDB (через RocksDB/Pebble) и множество встроенных движков хранения. RocksDB, в частности, превратился в базовый строительный блок - это слой хранения под TiKV, MyRocks (MySQL) и MongoRocks. ingodb развивает фундамент LSM дальше с помощью реактивного индексирования: движок отслеживает паттерны запросов и создаёт вторичные SSTable, отсортированные по полям, по которым часто происходит фильтрация.

Relationship to other concepts

LSM-деревья и B-tree представляют собой два полюса в архитектуре движков хранения баз данных: только дозапись против обновления на месте, оптимизация под запись против оптимизации под чтение. Большинство реальных систем сочетают разные стратегии - например, используют LSM-дерево для пути записи, но кэшируют горячие данные в оперативной памяти для чтения, либо используют B-tree с упреждающей записью в журнал, беря лучшее от обоих подходов. В книге Клеппмана designing-data-intensive-applications это сравнение разобрано очень подробно: глава про движки хранения - это стандартный материал, к которому обращаются, чтобы понять, почему конкретная система выбрала один полюс, а не другой.

inverted-index для полнотекстового поиска - это отдельная структура, но системы вроде Elasticsearch накладывают инвертированные индексы поверх сегментного хранилища на базе LSM (сегменты Lucene концептуально похожи на SSTable: они неизменяемы и периодически объединяются).

ZeroFS - пример применения того же паттерна в файловых системах: она хранит метаданные в LSM-дереве, упаковывая экстенты файлов в неизменяемые зашифрованные сегменты в объектном хранилище.

Слой индексов над SSTable образует собственное пространство архитектурных решений, и на странице scylladb-trie-index описано, как в ScyllaDB заменили привычную пару из summary- и index-файлов на упакованное по страницам префиксное дерево (trie) - под ним лежат те же SSTable, но поиск строки внутри файла устроен иначе.