Что такое LSM-дерево и чем оно отличается от B-дерева?
- Почему Cassandra и RocksDB быстро пишут?
- Что такое memtable, SSTable и compaction?
- Что такое усиление записи и чтения?
LSM-дерево превращает случайные записи в последовательные: запись идёт в журнал и в память (memtable), при заполнении memtable сбрасывается на диск отсортированным неизменяемым файлом (SSTable), а файлы в фоне сливаются (compaction).
- Запись очень быстрая, чтение дороже: ключ может лежать в нескольких файлах
- Фильтры Блума отсекают файлы, где ключа точно нет
- Удаление — запись-надгробие, место освобождается при слиянии
А ещё B-дерево — для смешанной нагрузки и чтений, LSM — для потока записей: Cassandra, RocksDB, ClickHouse (MergeTree), Kafka-подобные хранилища
Подробно
Путь записи:
- запись добавляется в конец журнала (WAL) — для надёжности;
- кладётся в memtable — отсортированную структуру в памяти (skip list, красно-чёрное дерево);
- когда memtable заполнилась, она целиком записывается на диск как SSTable — отсортированный по ключу неизменяемый файл с индексом и фильтром Блума. Это одна последовательная запись.
Обновление и удаление — тоже новые записи: новая версия ключа или надгробие (tombstone). Старое значение остаётся в старых файлах.
Путь чтения: memtable → свежие SSTable → старые; первое найденное значение — актуальное. Чтобы не открывать каждый файл, у каждого есть фильтр Блума («ключа здесь точно нет» или «возможно есть») и разреженный индекс.
Compaction. Файлов становится много, в них устаревшие версии и надгробия. Фоновое слияние объединяет несколько SSTable в одну — это слияние отсортированных последовательностей, как в сортировке слиянием, с отбрасыванием устаревшего. Стратегии:
- по размеру (size-tiered) — сливаем файлы похожего размера; мало перезаписи, но много файлов на чтение и временно двойное место;
- по уровням (leveled) — каждый уровень в ~10 раз больше предыдущего, ключи на уровне не пересекаются; чтение быстрее, но больше перезаписи.
Усиления (amplification) — главный язык сравнения:
- записи — сколько байт реально пишется на байт данных (данные переписываются при слиянии): у LSM 10–30, у B-дерева — переписывается целая страница ради одной строки;
- чтения — сколько файлов или страниц читается на запрос: у B-дерева обычно меньше;
- места — сколько лишнего хранится: устаревшие версии в LSM до слияния, недозаполненные страницы в B-дереве.
Когда LSM: много записей и последовательная запись важнее (журналы событий, метрики, временные ряды, счётчики, сообщения), SSD с ресурсом записи, сжатие (неизменяемые файлы хорошо сжимаются). Когда B-дерево: смешанная OLTP-нагрузка, много точечных чтений и диапазонов, предсказуемая задержка — compaction в LSM может давать всплески задержки.
Пример
put(k7, v1) → WAL, memtable {k7: v1}
put(k3, v2) → WAL, memtable {k3: v2, k7: v1}
memtable полна → SSTable-1 [k3: v2, k7: v1]
put(k7, v3), delete(k3) → memtable {k3: ✝, k7: v3} → SSTable-2
get(k7): memtable → SSTable-2 (v3) — найдено, в SSTable-1 не смотрим
compaction(1, 2) → SSTable-3 [k7: v3] — старая версия и k3 исчезлиЧто хотят услышать
- Путь записи: WAL, memtable, сброс в SSTable.
- Путь чтения и роль фильтров Блума.
- Compaction и надгробия.
- Сравнение с B-деревом через усиления записи, чтения и места.
- Примеры систем и когда что выбирать.
Частые ошибки
- Считать, что удалённые данные в LSM сразу освобождают место.
- Говорить, что LSM «быстрее B-дерева» без уточнения — для чего именно.
Проверьте себя
Один верный вариант. Подумайте, потом откройте ответ.
Показать варианты и ответ
- ✗LSM-дерево обновляет страницы на диске на месте, как B-дерево
- ✗В LSM чтение всегда дешевле записи благодаря индексу
- ✗Фильтры Блума в LSM нужны для сжатия данных на диске
- ✓Запись в memtable, сброс в неизменяемые SSTable и слияние — запись быстрая
Что спросят дальше
Связанные вопросы
Разбор собеседования с sotto
После собеседования sotto разбирает разговор: оценка, каждый вопрос — хорошо, частично или слабо, чего не хватило в ответе и над чем поработать к следующему разу. Первые 30 минут бесплатно.