LSM-дерево: memtable, SSTable и compaction простыми словами

Как устроено LSM-дерево: memtable, WAL, SSTable, Bloom-фильтры и compaction. Почему RocksDB и Cassandra так быстро пишут, чем LSM отличается от B-дерева и что спросят на собеседовании.

12 мин чтениясистемный дизайн · базы данных · структуры данных · python

Коротко

ВопросОтвет
Что этоДисковая структура для ключ-значение, оптимизированная под запись
Главная идеяПисать только последовательно: сначала в память, потом целыми отсортированными файлами
ЗаписьДописать в 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 стоит O(log⁡n)O(\log n) и не трогает диск вообще.

WAL

Память теряется при падении процесса. Поэтому перед вставкой в memtable операция дописывается в журнал упреждающей записи — WAL. Это файл, куда только добавляют в конец. При рестарте журнал проигрывается, и memtable восстанавливается.

Когда memtable выгружена на диск, соответствующий кусок WAL больше не нужен и удаляется.

SSTable

Когда memtable вырастает до порога (в RocksDB по умолчанию 64 МБ), она становится неизменяемой, а для новых записей заводится свежая. Неизменяемая таблица в фоне сбрасывается на диск в виде SSTable (Sorted String Table) — файла, где пары ключ-значение лежат отсортированными по ключу.

Внутри SSTable обычно есть:

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

Ключевое свойство: SSTable никогда не меняется после записи. Её можно только прочитать или удалить целиком. Это упрощает конкурентный доступ, кэширование и бэкапы: файл, который не меняется, можно копировать без блокировок.

Путь записи и путь чтения

Запись put(k, v):

  1. Дописать операцию в WAL (и, в зависимости от настроек, сделать fsync).
  2. Вставить в memtable.
  3. Если memtable переполнена — заморозить её и сбросить в новую SSTable в фоне.

Никаких чтений с диска. Поэтому LSM-хранилища выдерживают очень высокий поток записи.

Чтение get(k):

  1. Посмотреть в активную memtable, затем в замороженные.
  2. Пройти по SSTable от новых к старым. Первая найденная версия ключа — актуальная.
  3. Если найдено надгробие — ключ удалён, вернуть «нет».

Проблема видна сразу: если ключа нет вовсе, придётся заглянуть в каждый файл. Здесь и спасает 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-tieredLSM leveledB-дерево
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, ScyllaDBPostgreSQL, 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), чтобы не утонуть. Это нужно мониторить.

Вопросы, которые часто задают:

  1. Почему запись в LSM быстрее, чем в B-дерево? — Нет чтения перед записью, всё пишется последовательно крупными кусками.
  2. Как найти ключ, которого нет? — Bloom-фильтры по каждой SSTable отсекают почти все файлы.
  3. Чем leveled отличается от size-tiered? — Leveled даёт быстрые чтения и мало мусора ценой большего числа перезаписей; size-tiered наоборот.
  4. Что будет при падении сервера? — Memtable восстановится из WAL; SSTable неизменяемы и уже на диске.

Итог

LSM-дерево меняет местами привычные компромиссы: вместо того чтобы аккуратно обновлять данные на месте, оно копит изменения в памяти и сбрасывает их на диск большими отсортированными файлами, а порядок наводит потом, в фоне. Запись становится дешёвой и последовательной, а за это платят чтения и фоновый compaction. Если помнить про memtable, WAL, SSTable, надгробия, Bloom-фильтры и две стратегии слияния, любой вопрос про хранилища вроде RocksDB и Cassandra на собеседовании будет понятен.

Потренироваться в спокойной обстановке

Все задачи