Архитектура LSM

Мы выяснили, что B+ деревья идеальны для чтения и поиска по диапазону. Но у них есть темная сторона: они ужасно справляются с огромным потоком записей. Каждая вставка может вызвать каскадное разделение узлов (Node Split), переписывая кучу страниц на диске.

Если твой сервис льёт миллионы маленьких записей в секунду (например, логи, метрики IoT или лайки в соцсети), B-Tree индекс просто «сожжет» ресурс твоего SSD диска из-за постоянных случайных перезаписей.

LSM-дерево (Log-Structured Merge-Tree) инвертирует эту модель. Вместо того чтобы постоянно перестраивать дерево на диске, LSM делает все записи исключительно последовательными (просто дописывает в конец файла). Запись стоит копейки, а сложность переносится на этап чтения.

• Facebook: Мигрировал свой социальный граф с классического InnoDB (B+ Tree) на MyRocks (LSM-движок). Результат: сократили занимаемый объем данных на дисках на 62%, при этом количество физически записанных байт снизилось на 75%. Статья инженеров Meta.
• Amazon AWS: В их сервисе RDS for MariaDB переход на движок MyRocks дал 3-кратный прирост пропускной способности на запись (write-TPS) по сравнению со стандартным движком. Case-study от AWS.

Чтобы понять, как данные текут через систему, давай разберем главные компоненты LSM-архитектуры. Она состоит из быстрой памяти и медленного диска.

1. MemTable (Живет в RAM): Это обычное отсортированное дерево (например, Red-Black Tree), которое висит прямо в оперативной памяти. Все новые записи попадают только сюда. Поскольку это RAM, запись происходит моментально (O(log N) в памяти).
2. WAL / Commit Log (Живет на диске): Оперативная память стирается при отключении питания. Чтобы не потерять данные, каждая запись параллельно с MemTable пишется в WAL — текстовый лог на диске. Это очень быстрая последовательная запись (Append-only).
3. SSTable (Живет на диске): Когда MemTable в памяти переполняется (например, достигает 64 МБ), он «замораживается» и целиком сбрасывается на жесткий диск. Этот сброшенный файл называется SSTable (Sorted String Table). Главное правило: SSTable иммутабельны. Их нельзя изменить или дописать, можно только прочитать или удалить целиком.