LSM-дерево: memtable, SSTable и compaction простыми словами
Как устроено LSM-дерево: memtable, WAL, SSTable, Bloom-фильтры и compaction. Почему RocksDB и Cassandra так быстро пишут, чем LSM отличается от B-дерева и что спросят на собеседовании.
Коротко
| Вопрос | Ответ |
|---|---|
| Что это | Дисковая структура для ключ-значение, оптимизированная под запись |
| Главная идея | Писать только последовательно: сначала в память, потом целыми отсортированными файлами |
| Запись | Дописать в WAL + вставить в memtable — без чтения с диска и без перезаписи страниц |
| Чтение | Memtable, затем SSTable от новых к старым; ускоряют Bloom-фильтры и индексы блоков |
| Цена | Фоновое слияние файлов (compaction): лишние записи на диск и всплески нагрузки |
| Где используется | RocksDB, LevelDB, Cassandra, ScyllaDB, HBase, CockroachDB (Pebble), TiKV |
- LSM-дерево (Log-Structured Merge-tree) описали Патрик О'Нил и соавторы в 1996 году, а популярным его сделала статья Google о Bigtable (2006): оттуда термины memtable и SSTable.
- Обновление и удаление — это тоже запись. Старая версия ключа не стирается сразу, а «перекрывается» новой.
- Удаление — специальная запись-надгробие (tombstone). Реально место освобождается только при compaction.
- По сравнению с B-деревом LSM выигрывает на записи и сжатии, но проигрывает на точечных чтениях и предсказуемости задержек.
Какую проблему решает
B-дерево хранит данные в страницах фиксированного размера и обновляет их на месте. Чтобы вставить ключ, нужно найти лист, прочитать страницу, поменять в ней несколько байт и записать страницу целиком обратно. Это случайный ввод-вывод: одна вставка — чтение и запись в произвольное место диска.
На HDD случайная запись на порядки медленнее последовательной. На SSD разрыв меньше, но никуда не делся: контроллер стирает флеш блоками, и мелкие случайные перезаписи изнашивают диск и съедают пропускную способность.
Теперь представьте нагрузку, где пишут намного больше, чем читают: метрики, логи событий, лента активности, счётчики, история сообщений в чате. Для неё хочется структуру, которая никогда не перезаписывает данные на месте, а только дописывает. Это и есть LSM-дерево.
Устройство: три составные части
Memtable
Все записи сначала попадают в memtable — отсортированную структуру в памяти. Обычно это skip list (RocksDB, LevelDB) или сбалансированное дерево. Отсортированность нужна, чтобы потом выгрузить таблицу на диск одним последовательным проходом.
Вставка в memtable стоит и не трогает диск вообще.
WAL
Память теряется при падении процесса. Поэтому перед вставкой в memtable операция дописывается в журнал упреждающей записи — WAL. Это файл, куда только добавляют в конец. При рестарте журнал проигрывается, и memtable восстанавливается.
Когда memtable выгружена на диск, соответствующий кусок WAL больше не нужен и удаляется.
SSTable
Когда memtable вырастает до порога (в RocksDB по умолчанию 64 МБ), она становится неизменяемой, а для новых записей заводится свежая. Неизменяемая таблица в фоне сбрасывается на диск в виде SSTable (Sorted String Table) — файла, где пары ключ-значение лежат отсортированными по ключу.
Внутри SSTable обычно есть:
- блоки данных по несколько килобайт, часто сжатые;
- индекс блоков: первый ключ каждого блока и его смещение — чтобы найти нужный блок бинарным поиском, не читая файл целиком;
- Bloom-фильтр по всем ключам файла;
- метаданные: минимальный и максимальный ключ, число записей.
Ключевое свойство: SSTable никогда не меняется после записи. Её можно только прочитать или удалить целиком. Это упрощает конкурентный доступ, кэширование и бэкапы: файл, который не меняется, можно копировать без блокировок.
Путь записи и путь чтения
Запись put(k, v):
- Дописать операцию в WAL (и, в зависимости от настроек, сделать
fsync). - Вставить в memtable.
- Если memtable переполнена — заморозить её и сбросить в новую SSTable в фоне.
Никаких чтений с диска. Поэтому LSM-хранилища выдерживают очень высокий поток записи.
Чтение get(k):
- Посмотреть в активную memtable, затем в замороженные.
- Пройти по SSTable от новых к старым. Первая найденная версия ключа — актуальная.
- Если найдено надгробие — ключ удалён, вернуть «нет».
Проблема видна сразу: если ключа нет вовсе, придётся заглянуть в каждый файл. Здесь и спасает Bloom-фильтр: он умеет отвечать «ключа здесь точно нет» без чтения диска. При 10 битах на ключ ложноположительных срабатываний около 1%, то есть 99 из 100 лишних файлов отсекаются по памяти.
Диапазонный запрос scan(from, to) устроен как слияние k отсортированных списков: в каждом источнике (memtable и каждая SSTable) ставим итератор на from и сливаем потоки через кучу, отбрасывая старые версии и надгробия. Bloom-фильтр тут не помогает: он отвечает только на вопрос о конкретном ключе.
Минимальная модель на Python
Ниже игрушечная реализация: memtable — словарь, SSTable — два отсортированных списка с бинарным поиском, compaction — слияние через heapq.merge. WAL и Bloom-фильтры опущены, чтобы было видно главное.
import bisect import heapq TOMBSTONE = object() # маркер удаления class SSTable: """Неизменяемый отсортированный файл: здесь — просто два списка.""" def __init__(self, items): self.keys = [k for k, _ in items] self.values = [v for _, v in items] def get(self, key): i = bisect.bisect_left(self.keys, key) if i < len(self.keys) and self.keys[i] == key: return True, self.values[i] return False, None class LSMTree: def __init__(self, memtable_limit=3): self.memtable = {} self.sstables = [] # от новых к старым self.limit = memtable_limit def put(self, key, value): self.memtable[key] = value if len(self.memtable) >= self.limit: self.flush() def delete(self, key): self.put(key, TOMBSTONE) def flush(self): items = sorted(self.memtable.items()) self.sstables.insert(0, SSTable(items)) self.memtable = {} def get(self, key): if key in self.memtable: value = self.memtable[key] return None if value is TOMBSTONE else value for table in self.sstables: # от новых к старым found, value = table.get(key) if found: return None if value is TOMBSTONE else value return None def compact(self): # (ключ, возраст таблицы, значение): при равных ключах первой идёт новая streams = [ [(k, age, v) for k, v in zip(t.keys, t.values)] for age, t in enumerate(self.sstables) ] merged, last_key = [], None for key, _, value in heapq.merge(*streams): if key == last_key: continue # старая версия ключа — выбрасываем last_key = key if value is not TOMBSTONE: # сливаем всё, надгробия больше не нужны merged.append((key, value)) self.sstables = [SSTable(merged)] db = LSMTree() for k, v in [("b", 1), ("a", 1), ("c", 1), ("a", 2), ("d", 1), ("e", 1)]: db.put(k, v) db.delete("c") db.flush() print(len(db.sstables), db.get("a"), db.get("c"), db.get("e")) # 3 2 None 1 db.compact() print(len(db.sstables), db.sstables[0].keys, db.get("a")) # 1 ['a', 'b', 'd', 'e'] 2
Обратите внимание на две детали.
- Ключ
aзаписан дважды и лежит в двух SSTable. Чтение находит новую версию, потому что идёт от новых файлов к старым. - В
compactк ключу добавлен «возраст» таблицы. При равных ключахheapq.mergeвыдаст сначала запись из более новой таблицы, и мы оставим именно её. Это то же слияние двух отсортированных списков, что и в задаче про слияние отсортированных списков, только источников больше.
В этой модели надгробия выбрасываются, потому что сливаются все таблицы. В настоящей базе при частичном compaction так делать нельзя: если под надгробием в более старом, не участвующем в слиянии файле лежит живое значение, оно «воскреснет». Надгробие можно удалить, только когда слияние дошло до самого нижнего уровня.
Compaction: зачем и как
Без слияния файлов LSM-дерево быстро деградирует:
- файлов становится всё больше, и чтение проходит по всё большему числу SSTable;
- старые версии и удалённые ключи занимают место навсегда.
Compaction — фоновый процесс, который берёт несколько SSTable, сливает их (как в merge sort), выбрасывает перекрытые версии и пишет новые файлы. Старые после этого удаляются. Две основные стратегии:
Size-tiered (по размеру)
Файлы группируются по размеру. Когда набирается несколько (в Cassandra по умолчанию 4) файлов примерно одного размера, они сливаются в один побольше. Получаются «ярусы»: мелкие, средние, крупные.
- Плюс: каждый байт перезаписывается немного раз, записи дешёвые.
- Минус: один ключ может лежать во многих файлах, чтения дороже. Во время слияния крупных файлов нужно до двух раз больше места на диске.
Это стратегия по умолчанию в Cassandra (STCS).
Leveled (по уровням)
Данные разбиты на уровни L0, L1, L2... Каждый следующий уровень примерно в 10 раз больше предыдущего. На L0 лежат свежесброшенные memtable, и их диапазоны ключей могут пересекаться. Начиная с L1, файлы внутри уровня не пересекаются по диапазонам: каждый ключ на уровне живёт ровно в одном файле.
Когда уровень переполнен, один его файл сливается с теми файлами следующего уровня, чьи диапазоны с ним пересекаются.
- Плюс: точечное чтение заглядывает максимум в один файл на уровень, мусора мало (около 10% лишнего места).
- Минус: каждый байт за свою жизнь переписывается много раз: при переходе на каждый уровень он сливается примерно с 10 соседними файлами.
Это стратегия LevelDB и по умолчанию RocksDB. Для временных рядов в Cassandra есть ещё time-window compaction: файлы группируются по временным окнам, и старое окно просто удаляется целиком по TTL.
Три вида амплификации
На собеседовании компромиссы LSM удобно объяснять через три числа:
| Метрика | Что значит | LSM size-tiered | LSM leveled | B-дерево |
|---|---|---|---|---|
| Write amplification | Сколько байт пишется на диск на 1 байт данных | Низкая | Высокая | Высокая (страница целиком) |
| Read amplification | Сколько чтений с диска на один запрос | Высокая | Средняя | Низкая (высота дерева) |
| Space amplification | Во сколько раз данные на диске больше живых данных | Высокая | Низкая | Средняя (неполные страницы) |
Улучшить все три одновременно нельзя: это известное наблюдение, которое называют гипотезой RUM (Read, Update, Memory). Каждая стратегия compaction — это выбор точки в этом треугольнике.
Write amplification у leveled на практике бывает 10–30. Звучит пугающе, но эти записи последовательные и крупные, а B-дерево платит за каждую мелкую вставку записью целой страницы в случайное место. Поэтому по потоку записи LSM обычно всё равно выигрывает.
LSM против B-дерева
| Критерий | LSM-дерево | B-дерево |
|---|---|---|
| Запись | Последовательная, очень быстрая | Случайная, страница на месте |
| Точечное чтение | Несколько мест + фильтры | Один спуск по дереву |
| Диапазонные запросы | Слияние нескольких итераторов | Проход по листьям подряд |
| Сжатие данных | Отличное: файлы неизменяемы и плотно упакованы | Хуже: страницы заполнены не до конца |
| Предсказуемость задержек | Хуже: compaction конкурирует за диск и CPU | Лучше |
| Транзакции и блокировки | Сложнее: версия ключа размазана по файлам | Проще: ключ живёт в одном месте |
| Типичные системы | RocksDB, Cassandra, HBase, ScyllaDB | PostgreSQL, MySQL InnoDB, SQLite |
Короткое правило: много записей, данные больше памяти, нужно сжатие — LSM. Много точечных чтений и транзакционная нагрузка — B-дерево. Подробнее о том, как B-дерево работает в индексах, — в статье об индексах в базах данных.
Граница при этом размыта. MySQL умеет работать поверх RocksDB (движок MyRocks), а CockroachDB и TiDB — полноценные SQL-базы с транзакциями поверх LSM-хранилища.
Где встречается
- RocksDB — встраиваемая библиотека, форк LevelDB от Facebook. На ней построены хранилища в TiKV, Kafka Streams, Flink (state backend), YugabyteDB и многих других.
- Cassandra и ScyllaDB — каждая нода хранит свои партиции в LSM. Отсюда высокая скорость записи и рекомендация не злоупотреблять удалениями: надгробия живут как минимум
gc_grace_seconds(по умолчанию 10 дней) и замедляют чтение. - HBase — наследник идей Bigtable, тот же memtable (MemStore) + HFile.
- CockroachDB — сначала использовала RocksDB, потом перешла на собственный Pebble на Go с похожим форматом.
Если на собеседовании просят спроектировать key-value хранилище или систему с большим потоком записи, LSM — ожидаемый ответ для уровня хранения на отдельной ноде.
Типичные ошибки и вопросы на собеседовании
«Удаление в LSM мгновенно освобождает место». Нет. Удаление — это запись надгробия. Место освободится, когда compaction дойдёт до самых старых файлов с этим ключом. Массовые удаления в Cassandra — известный источник медленных чтений.
«Bloom-фильтр ускоряет range-запросы». Нет, он работает только для точного ключа. Для диапазонов используют префиксные фильтры или просто опираются на индекс блоков.
«Без WAL можно обойтись». Можно, если допустима потеря последней незаписанной memtable. Некоторые системы так и делают для кэшей, но для базы данных это потеря подтверждённых записей.
«Compaction бесплатен, он же в фоне». Он конкурирует с запросами за диск и процессор. Если запись идёт быстрее, чем успевает compaction, файлы копятся на L0, и база начинает притормаживать запись (write stall), чтобы не утонуть. Это нужно мониторить.
Вопросы, которые часто задают:
- Почему запись в LSM быстрее, чем в B-дерево? — Нет чтения перед записью, всё пишется последовательно крупными кусками.
- Как найти ключ, которого нет? — Bloom-фильтры по каждой SSTable отсекают почти все файлы.
- Чем leveled отличается от size-tiered? — Leveled даёт быстрые чтения и мало мусора ценой большего числа перезаписей; size-tiered наоборот.
- Что будет при падении сервера? — Memtable восстановится из WAL; SSTable неизменяемы и уже на диске.
Итог
LSM-дерево меняет местами привычные компромиссы: вместо того чтобы аккуратно обновлять данные на месте, оно копит изменения в памяти и сбрасывает их на диск большими отсортированными файлами, а порядок наводит потом, в фоне. Запись становится дешёвой и последовательной, а за это платят чтения и фоновый compaction. Если помнить про memtable, WAL, SSTable, надгробия, Bloom-фильтры и две стратегии слияния, любой вопрос про хранилища вроде RocksDB и Cassandra на собеседовании будет понятен.