LSM-деревья и NoSQL-хранилища

Разбор LSM-деревьев от Ramarathinam Iyer - движка хранения, лежащего в основе Cassandra, RocksDB, LevelDB и большей части мира NoSQL. Статья подробно описывает всю архитектуру: почему B-tree упираются в write amplification, как LSM-деревья решают это с помощью append-only хранилища и какие компромиссы несёт этот подход.

Проблема B-tree

B-tree хранят данные в страницах фиксированного размера (обычно 8 KB). Изменение одного байта требует загрузить страницу, модифицировать её и записать обратно целиком - случайный ввод-вывод (random I/O). В этом и заключается проблема write amplification: отношение реально записанных на диск байт к байтам, которые хотело записать приложение, оказывается сильно больше 1. Это медленно работает на HDD и изнашивает SSD быстрее, чем нужно.

Как работают LSM-деревья

LSM-деревья никогда не перезаписывают данные на месте. Каждая запись происходит только добавлением в конец (append-only), а разные версии система согласует позже.

Путь записи: данные попадают в Write Ahead Log (WAL) на диске для устойчивости к сбоям и параллельно в MemTable - отсортированную структуру в оперативной памяти (skip list или сбалансированное дерево). Когда MemTable достигает порогового размера (обычно 64 MB), она сбрасывается на диск в виде SSTable (Sorted String Table). SSTable после записи неизменяемы.

Путь чтения: сначала проверяется MemTable, затем поиск идёт по SSTable уровень за уровнем, от новых к старым. Первое найденное совпадение побеждает, за счёт чего и работают обновления: значение из более новой SSTable перекрывает старое для того же ключа. При удалении записывается маркер tombstone; чтение, натолкнувшись на tombstone, считает ключ удалённым.

Фильтры Блума

Без оптимизаций чтение сканировало бы каждую SSTable на диске. Это решают фильтры Блума. С каждой SSTable связан свой фильтр Блума в памяти - вероятностная структура, которая может сказать: "этого ключа тут точно нет" (пропустить файл) или "этот ключ может быть здесь" (прочитать файл). Ложноположительные срабатывания случаются, но редки; ложноотрицательных не бывает. Это превращает большинство промахов при чтении в дешёвые проверки в RAM.

Compaction

Со временем накапливается множество SSTable с пересекающимися диапазонами ключей и устаревшими версиями. Compaction объединяет их в фоновом режиме, отбрасывая старые версии и tombstone'ы.

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

Режимы сбоев

Write stalls возникают, когда MemTable заполняется, но не успевает сброситься на диск - compaction отстаёт, диск перегружен или и то, и другое. База данных перестаёт принимать записи, чтобы не исчерпать память. Это backpressure, и оно заложено архитектурно, но в продакшене проявляется внезапными скачками задержек.

Space amplification - ещё одна статья расходов. Если обновить ключ 100 раз, на диске будет лежать 100 копий, пока compaction их не вычистит. Нагрузка с интенсивной записью при медленной compaction может временно занимать в разы больше места, чем логический объём данных.

См. также

• lsm-tree - страница концепции о самой структуре данных