LSM-дерево

LSM-дерево (англ. Log-Structured Merge-tree, дерево со структурированным слиянием журнала) — это структура данных, предназначенная для организации высокопроизводительной записи и чтения данных в системах хранения, особенно в базах данных и файловых системах. LSM-дерево оптимизирует операции записи за счёт буферизации данных в оперативной памяти и последующего асинхронного слияния (merge) с данными на диске, что позволяет достигать высокой пропускной способности при работе с большими объёмами данных. В отличие от B-деревьев, LSM-деревья минимизируют случайные операции ввода-вывода, заменяя их последовательными, что особенно эффективно на жёстких дисках (HDD) и твердотельных накопителях (SSD).

История

Концепция LSM-дерева была впервые предложена Патриком О’Нилом (Patrick O'Neil) и его коллегами в 1996 году в статье «The Log-Structured Merge-Tree (LSM-Tree)». Изначально идея возникла как развитие подходов к организации журнально-структурированных файловых систем (LFS), разработанных Джоном Остерхаутом (John Ousterhout) и Фредом Дугласом (Fred Douglas) в начале 1990-х годов. LSM-деревья были созданы для решения проблемы высокой стоимости операций записи в традиционных B-деревьях, где каждая вставка или обновление требовала множества случайных обращений к диску.

В 2000-х годах LSM-деревья начали активно применяться в системах управления базами данных (СУБД), ориентированных на высокую нагрузку записи. Одним из первых коммерческих продуктов, использующих LSM-дерево, стала СУБД Bigtable от Google (2006 год), которая легла в основу многих NoSQL-решений. Впоследствии LSM-деревья стали основой для таких популярных баз данных, как Apache Cassandra, LevelDB (разработана Google), RocksDB (форк LevelDB от Facebook), HBase, MongoDB (с версии 3.0) и ScyllaDB.

Устройство и принцип работы

LSM-дерево состоит из нескольких уровней (компонентов), каждый из которых представляет собой отсортированную структуру данных. Основные компоненты:

• MemTable (таблица в памяти) — структура данных в оперативной памяти (обычно красно-чёрное дерево, дерево поиска или хеш-таблица), в которую сначала записываются все входящие данные. MemTable поддерживает операции вставки, обновления и удаления. Для обеспечения устойчивости к сбоям (durability) все операции также записываются в журнал упреждающей записи (WAL, Write-Ahead Log) на диске.
• SSTable (Sorted String Table, отсортированная таблица строк) — неизменяемый (immutable) файл на диске, содержащий отсортированные пары ключ-значение. Когда MemTable заполняется до определённого порога, она преобразуется в SSTable и сбрасывается на диск. Каждый SSTable имеет индекс для быстрого поиска.
• Уровни (Levels) — SSTable организованы в иерархию уровней (L0, L1, L2 и т.д.). На нулевом уровне (L0) находятся самые свежие SSTable, которые могут перекрываться по диапазонам ключей. На более глубоких уровнях (L1, L2, ...) SSTable не перекрываются и строго отсортированы.

Процесс записи данных в LSM-дерево:

1. Все операции записи (вставка, обновление, удаление) сначала попадают в MemTable в оперативной памяти.
2. Параллельно операции записываются в WAL для восстановления после сбоя.
3. Когда MemTable достигает заданного размера, она блокируется для записи, и создаётся новая пустая MemTable.
4. Заполненная MemTable преобразуется в SSTable и сбрасывается на диск в уровень L0.
5. Периодически запускается процесс слияния (compaction), который объединяет SSTable с разных уровней, удаляя устаревшие и дублирующиеся записи, и перемещает данные на более глубокие уровни.

Процесс чтения данных:

1. Поиск начинается с самой свежей MemTable.
2. Если ключ не найден, поиск продолжается в более старых MemTable (если есть).
3. Затем последовательно проверяются SSTable на уровне L0 (в порядке от новых к старым).
4. Если ключ не найден на L0, поиск осуществляется на уровне L1, L2 и т.д. с помощью бинарного поиска по индексам SSTable.
5. Для ускорения поиска используются блум-фильтры (Bloom filters), которые позволяют быстро определить, что ключа нет в конкретном SSTable, без полного сканирования.

Слияние (Compaction)

Слияние — ключевой процесс в LSM-дереве, который обеспечивает поддержание производительности чтения и эффективное использование дискового пространства. Существует несколько стратегий слияния:

• Уровневое слияние (Leveled Compaction) — используется в LevelDB и RocksDB. SSTable на каждом уровне имеют строго определённый размер. При переполнении уровня запускается слияние с SSTable следующего уровня. Это минимизирует амплитуду чтения (read amplification), но требует больше операций записи (write amplification).
• Слияние по размеру (Size-Tiered Compaction) — используется в Apache Cassandra. SSTable объединяются, когда их количество на одном уровне превышает порог. Это снижает амплитуду записи, но увеличивает амплитуду чтения, так как на одном уровне может быть много перекрывающихся SSTable.
• Слияние по времени (Time-Window Compaction) — используется в системах с временными рядами (time-series). SSTable объединяются на основе временных окон, что позволяет эффективно удалять устаревшие данные.

Классификация

LSM-деревья можно классифицировать по нескольким признакам:

По типу хранения

• Дисковые LSM-деревья — данные хранятся на жёстких дисках или SSD. Примеры: LevelDB, RocksDB, Apache Cassandra.
• Гибридные LSM-деревья — часть данных (обычно горячие данные) хранится в оперативной памяти, а холодные — на диске. Примеры: MongoDB WiredTiger, ScyllaDB.

По стратегии слияния

• Leveled Compaction — ориентирован на низкую амплитуду чтения.
• Size-Tiered Compaction — ориентирован на низкую амплитуду записи.
• Hybrid Compaction — комбинирует подходы, например, в Apache Cassandra можно настроить разные стратегии для разных таблиц.

По поддержке транзакций

• ACID-совместимые — поддерживают атомарность, согласованность, изоляцию и долговечность (например, RocksDB с поддержкой транзакций).
• BASE-совместимые — ориентированы на высокую доступность и масштабируемость, часто используются в NoSQL-системах (например, Apache Cassandra).

Характеристики

Амплитуда записи (Write Amplification)

Амплитуда записи — это отношение объёма данных, фактически записанных на диск, к объёму данных, переданных приложением. В LSM-деревьях амплитуда записи может быть высокой (от 10 до 50 и выше) из-за многократных перезаписей при слиянии. Это особенно критично для SSD, где количество циклов записи ограничено. Для снижения амплитуды записи используются оптимизации, такие как сжатие данных и выбор стратегии слияния.

Амплитуда чтения (Read Amplification)

Амплитуда чтения — это количество операций чтения, необходимых для поиска одного ключа. В LSM-деревьях амплитуда чтения может быть высокой, особенно на ранних уровнях (L0), где много перекрывающихся SSTable. Для снижения амплитуды чтения применяются блум-фильтры, индексы и уровневое слияние.

Производительность записи

LSM-деревья обеспечивают очень высокую производительность записи (до сотен тысяч операций в секунду на одном узле) за счёт буферизации в памяти и последовательных операций с диском. Это делает их идеальными для приложений с интенсивной записью, таких как логирование, аналитика в реальном времени и IoT.

Производительность чтения

Производительность чтения в LSM-деревьях обычно ниже, чем в B-деревьях, особенно для случайных чтений. Однако для последовательных чтений и чтений по диапазону ключей LSM-деревья могут быть эффективнее. Для повышения производительности чтения используются кэширование, блум-фильтры и оптимизация слияния.

Применение

LSM-деревья широко используются в различных системах хранения данных, особенно в тех, где требуется высокая скорость записи и масштабируемость:

• NoSQL-базы данных: Apache Cassandra, HBase, ScyllaDB, MongoDB (с движком WiredTiger), Amazon DynamoDB (частично).
• Встраиваемые базы данных: LevelDB, RocksDB, которые используются в браузерах (Chrome), криптовалютах (Bitcoin, Ethereum), мессенджерах (WhatsApp — организация Meta признана экстремистской и запрещена в РФ) и системах управления данными.
• Системы обработки потоков данных: Apache Kafka (для хранения логов), Apache Flink (для чекпоинтов).
• Файловые системы: журнально-структурированные файловые системы (LFS), такие как F2FS (Flash-Friendly File System) для SSD.
• Хранилища временных рядов: InfluxDB, TimescaleDB (частично).
• Системы кэширования: Redis (с модулем RedisGears), Memcached (в некоторых конфигурациях).

Примеры реализаций

LevelDB

LevelDB — это библиотека для хранения пар ключ-значение, разработанная Google. Она реализует LSM-дерево с уровневым слиянием. LevelDB написана на C++ и используется в браузере Google Chrome для хранения данных IndexedDB. Ключевые особенности: поддержка сжатия (Snappy), блум-фильтры, транзакции (с версии 1.20).

RocksDB

RocksDB — это форк LevelDB, разработанный Facebook (организация Meta признана экстремистской и запрещена в РФ). RocksDB оптимизирован для работы на SSD и в многопоточных средах. Он поддерживает множество стратегий слияния, сжатие (LZ4, ZSTD, Snappy), транзакции с изоляцией, колоночные семейства и динамическое управление памятью. RocksDB используется в MySQL (как движок MyRocks), Apache Flink, Apache Kafka и многих других системах.

Apache Cassandra

Apache Cassandra — это распределённая NoSQL-база данных, использующая LSM-дерево с размерным слиянием (Size-Tiered Compaction) по умолчанию. Cassandra обеспечивает высокую доступность и масштабируемость за счёт децентрализованной архитектуры. В последних версиях добавлена поддержка уровневой компакции и гибридных стратегий.

Критика

Несмотря на преимущества, LSM-деревья имеют ряд недостатков:

• Высокая амплитуда записи — многократные перезаписи данных при слиянии могут сокращать срок службы SSD и увеличивать нагрузку на диск.
• Сложность настройки — выбор стратегии слияния, размера MemTable, частоты слияния и других параметров требует глубокого понимания рабочей нагрузки.
• Проблемы с производительностью чтения — особенно при большом количестве SSTable на уровне L0 и отсутствии блум-фильтров.
• Потребление памяти — для хранения MemTable, блум-фильтров и индексов требуется значительный объём оперативной памяти.
• Сложность реализации транзакций — поддержка ACID-транзакций в LSM-деревьях требует дополнительных механизмов, таких как многоверсионное управление параллелизмом (MVCC) и блокировки.

Интересные факты

• LSM-деревья часто сравнивают с B-деревьями. В то время как B-деревья оптимизированы для чтения, LSM-деревья — для записи. В современных системах часто используются гибридные подходы, например, Bw-Tree (B-tree with Write-Ahead Log) или LSM-деревья с кэшированием горячих данных.
• В RocksDB реализована поддержка «колоночных семейств» (column families), что позволяет хранить разные типы данных в одном LSM-дереве с разными настройками.
• LSM-деревья используются в криптовалютах, таких как Bitcoin (для хранения транзакций в LevelDB) и Ethereum (для хранения состояния в LevelDB или RocksDB).
• В 2020 году компания Amazon представила собственный вариант LSM-дерева — «LSM-tree with B-tree-like reads» (LSM-B), который используется в Amazon DynamoDB для снижения амплитуды чтения.

Источники

• O'Neil, P., Cheng, E., Gawlick, D., & O'Neil, E. (1996). The Log-Structured Merge-Tree (LSM-Tree). Acta Informatica, 33(4), 351-385.
• Chang, F., Dean, J., Ghemawat, S., et al. (2006). Bigtable: A Distributed Storage System for Structured Data. Proceedings of the 7th USENIX Symposium on Operating Systems Design and Implementation (OSDI).
• Facebook (продукт Meta, признанной экстремистской и запрещённой в РФ) Engineering. (2013). RocksDB: A Persistent Key-Value Store for Flash and RAM Storage. Facebook Engineering Blog.
• Lakshman, A., & Malik, P. (2010). Cassandra: A Decentralized Structured Storage System. ACM SIGOPS Operating Systems Review, 44(2), 35-40.
• Sears, R., & Ramakrishnan, R. (2012). bLSM: A General Purpose Log Structured Merge Tree. Proceedings of the 2012 ACM SIGMOD International Conference on Management of Data.