Что такое LSM-дерево? Объясняем Log-Structured Merge Tree

Что такое LSM-дерево?

Log-structured merge tree (LSM) — это структура данных, которая буферизует входящие операции записи в памяти и переносит их на диск в виде отсортированных неизменяемых пакетов. Она никогда не изменяет данные на месте. Вместо этого она накапливает изменения и откладывает их упорядочивание, обменивая простоту чтения на пропускную способность записи.

LSM-дерево было формализовано в статье 1996 года Патрика О’Нила, Эдварда Ченга, Дитера Гавлика и Элизабет О’Нил под названием The log-structured merge-tree (LSM-tree). Около десяти лет оно оставалось относительно малоизвестной академической структурой, пока Google Bigtable не построила на этой концепции свой слой хранения. Архитектура Bigtable породила LevelDB, LevelDB породила RocksDB, а та или иная разновидность LSM-дерева лежит в основе большинства систем, рассчитанных на интенсивную загрузку данных.  

Название подразумевает одно дерево, что сильно вводит в заблуждение. 

LSM-дерево лучше понимать как слаженную работу трех компонентов:

• Memtable: буфер в памяти, содержащий самые последние записи
• Журнал упреждающей записи (WAL): доступный только для добавления файл на диске, обеспечивающий долговечность этих записей
• Растущая коллекция файлов sorted string table (SST): неизменяемые отсортированные файлы, содержащие все более старые данные

Почти все интересные особенности поведения LSM связаны с перемещением данных между этими тремя компонентами. Все эти перемещения начинаются с одного обманчиво простого вызова функции, обычно называемого put.

Что такое put? 

Put — это удобная обертка, которая внутри создает WriteBatch ровно с одной записью и передает его в Write(), обрабатывающую изменения. 

Естественная отправная точка — Put(key, value), но, строго говоря, в RocksDB такой операции нет. Каждая запись представляет собой пакет, а одиночный put — просто пакет из одной записи. Атомарные операции записи с несколькими ключами доступны в RocksDB без дополнительных затрат, поскольку это нативная операция.

WriteBatch — это компактная байтовая строка фиксированной структуры. Она состоит из 12-байтового заголовка с 8-байтовым номером последовательности и 4-байтовым количеством записей, после которого идут сами записи. Каждая запись содержит однобайтовый тег типа, ключ с префиксом длины и, для операций записи, значение с префиксом длины.

Утверждение из первой статьи серии — ключи и значения представляют собой произвольные массивы байтов — становится буквальным. Кодировка пакета не знает и не учитывает смысл байтов. Единственная заданная структура — префиксы длины. 

Каждый пакет помечается монотонно возрастающим счетчиком, известным как номер последовательности. Он задает полный порядок всех операций записи, когда-либо принятых базой данных. Именно номера последовательности делают возможными снимки, согласованное чтение и восстановление после сбоя. WAL можно воспроизвести, поскольку каждая запись в нем знает свое место в очереди.

Put, Delete, Merge

Важно отметить, что Put — это kTypeValue, а Delete — kTypeDeletion. Поэтому удаление не является физическим удалением. Это запись — tombstone, — которая фиксирует факт удаления, а фактическое освобождение места откладывается до компакции.

Put и Delete используют формат WriteBatch вместе с kTypeMerge, который записывается операцией Merge. Merge существует потому, что цикл «чтение — изменение — запись» губителен для хранилища, оптимизированного под запись. Чтобы увеличить счетчик с помощью Put, нужно прочитать текущее значение, прибавить единицу и записать результат обратно. Для изменения одного числа приходится дважды обходить базу данных, причем чтение несет полную стоимость пути чтения. 

Merge полностью пропускает чтение. 

Вместо этого операция добавляет операнд (то есть описание изменения, например «прибавить единицу») и завершается. Во время записи ничего не вычисляется. Позже база данных сворачивает операнды в итоговое значение с помощью предоставленного приложением оператора слияния — либо при следующем чтении ключа, либо когда цепочку встретит компакция.

Удаления откладывают освобождение места, а слияния — вычисления. 

Вся суть LSM-дерева видна в этих трех тегах типов: каждое изменение, включая логически зависящее от существующего состояния, превращается в слепое добавление. В LSM-дереве все является добавлением. 

Как устроен путь записи LSM-дерева

Проще всего понять LSM-деревья, проследив путь одного вызова Put(key, value) от функции до диска.

Шаг первый: журнал упреждающей записи

Сначала запись добавляется в WAL. Это происходит до обращения к memtable, и такой порядок формирует гарантию долговечности. После завершения добавления в WAL запись существует на диске в форме, способной пережить сбой, хотя она еще не организована для чтения.

Добавление в журнал — самая дешевая из возможных дисковых операций, и в этом весь смысл. Долговечность достигается по цене последовательной записи.

RocksDB объединяет параллельные операции записи в групповые фиксации, чтобы дополнительно распределить затраты. Параметр sync определяет, следует ли перед возвратом из вызова сбросить добавленные данные из страничного кеша ОС в постоянное хранилище.

Шаг второй: memtable

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

Skiplist поддерживает неблокирующие параллельные вставки и постоянно сохраняет сортировку данных. Это аналог регистрации документов по мере поступления вместо их накопления в стопке.

Шаг третий: заполнение memtable

Memtable растет, пока не достигнет заданного порога — write_buffer_size, который по умолчанию равен 64 МБ. После этого она помечается как неизменяемая, вместо нее подставляется новая пустая memtable, а входящие записи продолжаются без перерыва. Заполненная и зафиксированная memtable ждет фонового сброса. 

Операции записи никогда не блокируются самим сбросом.

Шаг четвертый: сброс

Фоновый поток записывает неизменяемую memtable на диск в виде SST-файла на уровне 0 (L0) дерева. Поскольку skiplist уже отсортирован, сброс выполняется одним последовательным проходом: записи обходятся по порядку и записываются на диск.

Работа memtable завершена, а соответствующие записи WAL со временем можно удалить. Теперь данные сохраняются на диске в постоянной форме, доступной для чтения.

Что находится внутри SST-файла?

В SST-файле данные проводят остаток своего жизненного цикла. Он состоит из трех блоков и футера:

• Блоки данных: сами отсортированные записи размером по несколько килобайт, сжатые по отдельности
• Индексные блоки: сопоставляют диапазоны ключей со смещениями блоков, чтобы поиск мог сразу перейти к нужному блоку
• Необязательный блок фильтра Блума: компактная вероятностная сводка, способная без дополнительного чтения ответить, что «этого ключа точно нет в данном файле»
• Футер: указывает расположение всего перечисленного выше

Каждый элемент этой структуры нужен для того, чтобы будущие операции чтения обращались к минимально возможному объему данных. Особенно это касается индекса и фильтра Блума.

Пошаговый разбор пути записи

Все описанное выше можно наблюдать напрямую. В этом разделе мы быстро проследим путь одного Put через базу данных с помощью ldb и sst_dump — инструментов анализа, поставляемых вместе с RocksDB. В примере используются Rust и крейт rocksdb, хотя подойдет любая привязка.

Предварительные требования

Чтобы повторить действия, установите инструменты командной строки RocksDB и набор инструментов Rust. 

В macOS команда brew install rocksdb устанавливает и ldb, и sst_dump. В Debian/Ubuntu нужный пакет называется rocksdb-tools.

После установки создайте новый проект:

$ cargo new lsm-trace
$ cd lsm-trace
$ cargo add rocksdb

При первой сборке крейт rocksdb компилирует библиотеку RocksDB на C++ из исходного кода, поэтому первый запуск cargo run может занять несколько минут.

Шаг первый: запись и остановка

Замените содержимое src/main.rs следующим кодом:

use rocksdb::{Options, DB};

fn main() {
    let mut opts = Options::default();
    opts.create_if_missing(true);
    let db = DB::open(&opts, "/tmp/lsm-trace").unwrap();

    db.put(b"slot:0001", b"hello").unwrap();
// Deliberately no flush. Let the process exit.
}

Один раз выполните cargo run, а затем просмотрите созданный каталог базы данных:

$ ls /tmp/lsm-trace
000004.log CURRENT IDENTITY LOCK LOG MANIFEST-000005 OPTIONS-000007

Файлы CURRENT и MANIFEST отслеживают состав файлов базы данных, а OPTIONS хранит конфигурацию, с которой она была открыта. LOG без номера — это удобочитаемый текстовый журнал для отладки. Не путайте его с 000004.log, который является самим журналом упреждающей записи.

Точные номера файлов будут различаться при разных запусках, но структура останется прежней.

Обратите внимание, что в каталоге нет ни одного файла .sst. Запись долговечна, поскольку пережила завершение процесса, но существует только как запись WAL. Так на практике выглядит разделение долговечности и организации.

Шаг второй: вывод содержимого WAL

Укажите ldb любой файл .log, находящийся в каталоге:

$ ldb dump_wal --walfile=/tmp/lsm-trace/000004.log --header
Sequence,Count,ByteSize,Physical Offset,Key(s) 1,1,29,0,PUT(0) : 0x736C6F743A30303031

У нас есть один пакет: номер последовательности 1, содержащий 1 запись (29 байт). Это PUT, ключ которого представляет собой шестнадцатеричную кодировку slot:0001. 

Размер соответствует описанной ранее кодировке: 12-байтовый заголовок и 17-байтовая запись, включающая один тег типа, два префикса длины, 9-байтовый ключ и 5-байтовое значение.

Шаг третий: сброс и вывод содержимого SST

Сначала удалите каталог базы данных — rm -rf /tmp/lsm-trace, — чтобы начать этот запуск с чистого состояния.

Добавьте одну строку в main.rs после put:

db.put(b"slot:0001", b"hello").unwrap();
db.flush().unwrap();

Вызов db.flush().unwrap(); принудительно записывает memtable в SST-файл, не дожидаясь ее заполнения.

Снова запустите файл, а затем просмотрите каталог. 

Теперь в выводе появился новый файл .sst. Его можно изучить в обоих полезных режимах sst_dump, подставив фактическое имя файла:

$ sst_dump --file=/tmp/lsm-trace/000010.sst --command=scan
'slot:0001' seq:1, type:1 => hello

Обратите внимание: перед результатами сканирования sst_dump выводит несколько начальных строк о формате файла. Здесь и в результатах ниже они опущены.

Это пара «ключ — значение» в новом постоянном расположении, по-прежнему содержащая свой номер последовательности. 

Затем можно просмотреть ее свойства с помощью следующей команды:

$ sst_dump --file=/tmp/lsm-trace/000010.sst --show_properties

В выводе свойств по пунктам представлена описанная ранее структура SST: количество и размер блоков данных, размер индексного блока, наличие фильтра, алгоритм сжатия и количество записей. 

Хотя у нас только один ключ, перечислены все структурные элементы, за одним показательным исключением. Размер блока фильтра равен нулю, а политика фильтра указана как N/A, потому что фильтры Блума в RocksDB нужно включать явно через filter_policy. В настройках по умолчанию они не заданы. 

В следующей статье этой серии мы разберем, почему в рабочих средах их почти всегда включают. 

Шаг четвертый: повторное открытие и проверка журнала

Закомментируйте строки put и flush, оставив только строку DB::open, и запустите программу еще раз. Теперь в каталоге нет старого файла 000004.log: его заменил новый, почти пустой журнал с более высоким номером. Его содержимое было сброшено в SST на третьем шаге, поэтому записи устарели, и RocksDB удалила файл при повторном открытии.

Это весь механизм связи жизненных циклов WAL и memtable. 

Чтобы опуститься еще на один уровень, в Linux можно запустить исполняемый файл из первого шага через strace -e trace=write,fdatasync и увидеть гарантию долговечности на границе системных вызовов. Последовательные вызовы write добавляют данные в файл .log, а fdatasync появляется только при установленном параметре WriteOptions.sync.

Шаг пятый: удаление ключа и проверка оставшихся данных

Сделанное ранее утверждение о том, что удаление является записью, можно проверить напрямую. 

Измените main.rs, чтобы удалить ключ и принудительно выполнить еще один сброс:

db.delete(b"slot:0001").unwrap();
db.flush().unwrap();

Запустите программу, а затем просмотрите каталог. 

Теперь в нем будет два файла .sst. Старый файл остался неизменным, поскольку он иммутабелен. Поэтому он по-прежнему содержит ключ и его значение. Это можно проверить сканированием:

$ sst_dump --file=/tmp/lsm-trace/000010.sst --command=scan
'slot:0001' seq:1, type:1 => hello

Теперь просканируйте более новый файл:

$ sst_dump --file=/tmp/lsm-trace/000014.sst --command=scan
'slot:0001' seq:2, type:0 =>

Это тот же ключ, но с более высоким номером последовательности, type:0 вместо type:1 и без значения. Это tombstone: запись kTypeDeletion из раздела о WriteBatch, сброшенная в собственный SST. Теперь база данных содержит и значение, и запись о его удалении — рядом, но в разных файлах.

При чтении ключа противоречие разрешится в пользу tombstone. 

Это можно проверить, добавив в программу поиск:

match db.get(b"slot:0001").unwrap() {
    Some(v) => println!("found: {:?}", v),
    None => println!("not found"),
}

Программа выведет not found, поскольку путь чтения сначала проверяет более новые данные, а номер последовательности 2 имеет приоритет над номером 1. С точки зрения базы данных значение удалено, однако оно все еще находится на диске в старом SST-файле. 

Место не было освобождено: удаление лишь зарегистрировано. Оно продолжит скрывать значение, пока компакция не объединит два файла и не удалит и tombstone, и скрытое значение.

Шаг шестой: удаление ключа и проверка оставшихся данных

Тип записи Merge тоже можно наблюдать. Для этого нужно настроить оператор слияния, поскольку без него RocksDB не знает, что означает операнд.

Снова удалите каталог базы данных и замените main.rs следующим кодом:

use rocksdb::{Options, DB, MergeOperands};

fn add(_key: &[u8], existing: Option<&[u8]>, operands: &MergeOperands) -> Option<Vec<u8>> {
    let mut total: i64 = existing
        .and_then(|v| std::str::from_utf8(v).ok())
        .and_then(|s| s.parse().ok())
        .unwrap_or(0);
    for op in operands {
        total += std::str::from_utf8(op).ok().and_then(|s| s.parse().ok()).unwrap_or(0);
    }
    Some(total.to_string().into_bytes())
}

fn main() {
    let mut opts = Options::default();
    opts.create_if_missing(true);
    opts.set_merge_operator_associative("add", add);
    let db = DB::open(&opts, "/tmp/lsm-merge").unwrap();

    db.merge(b"counter", b"1").unwrap();
    db.merge(b"counter", b"1").unwrap();
    db.merge(b"counter", b"1").unwrap();
    println!("{:?}", db.get(b"counter").unwrap());
}

Вывод содержимого WAL показывает три отдельные записи MERGE. То есть три добавления вместо одного чтения:

$ ldb dump_wal --walfile=/tmp/lsm-trace/000004.log --header
Sequence,Count,ByteSize,Physical Offset,Key(s)
1,1,23,0,MERGE(0) : 0x636F756E746572
2,1,23,30,MERGE(0) : 0x636F756E746572
3,1,23,60,MERGE(0) : 0x636F756E746572

Оператор слияния свернул цепочку во время чтения, получив результат в виде необработанных байтов. Программа выводит Some([51]), потому что 51 — это ASCII-код символа 3. Причина та же: ключи и значения представляют собой произвольные массивы байтов.

Также можно добавить db.flush().unwrap(); перед поиском, удалить каталог и снова запустить программу. Сканирование SST покажет одну запись:

'counter' seq:3, type:2 => 3

Сброс применил оператор и объединил записи в один операнд.

Почему уровень 0 особенный?

Новые SST-файлы попадают на уровень 0. Это прямые снимки memtable, каждый из которых охватывает диапазон ключей, попавший в соответствующую memtable. Поэтому файлы L0 могут пересекаться и часто пересекаются. Этим L0 отличается от всех более глубоких уровней, где файлы не пересекаются: каждый владеет отдельным диапазоном ключей, поэтому конкретный ключ может находиться не более чем в одном файле на каждом уровне.

В результате каждый файл L0 становится отдельным местом, где может скрываться ключ. Поэтому количество файлов L0 напрямую снижает производительность чтения. Именно поэтому RocksDB внимательно отслеживает их число и начинает ограничивать или даже приостанавливать запись, если оно становится слишком большим.

Поддержание небольшого размера L0 — одна из основных задач компакции.

Почему LSM-деревья превосходят B-деревья при записи?

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

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

LSM-дерево не платит эту цену во время записи. Оно добавляет данные в WAL, буферизует их в memtable и объединяет в пакеты при сбросе. Каждая запись на диск последовательна, а долг по организации данных откладывается до компакции. Работа не исчезает. Она выполняется позже крупными пакетами, объединенными в форму, которую диски обрабатывают особенно эффективно.

Для SSD это особенно важно, поскольку они вообще не могут перезаписывать данные на месте. 

Флеш-память стирается крупными блоками размером от сотен килобайт до мегабайт, а записывается более мелкими страницами. Поэтому при каждой небольшой произвольной перезаписи слой трансляции флеш-памяти накопителя (FTL) вынужден незаметно перемещать актуальные данные и стирать блоки. 

Произвольная запись страниц B-деревом заставляет FTL делать это постоянно. Устройство создает дополнительное усиление записи поверх того, которое вносит сама структура данных. За это приходится платить и пропускной способностью, и сроком службы накопителя. Крупные последовательные записи LSM-дерева близки к оптимальному сценарию для флеш-оборудования.

Удобнее всего рассматривать это как кредит. Отложенная организация позже оплачивается операциями ввода-вывода при компакции, а чтение вынуждено проверять больше мест, чем в B-дереве. Таким образом, LSM-дерево получает высокую пропускную способность записи сейчас, а позже расплачивается усилением чтения и использования пространства. 

Более подробное сравнение LSM-дерева и B-дерева с точки зрения усиления чтения, записи и использования пространства см. в статье B-Tree и LSM-Tree. 

Что происходит после сбоя RocksDB?

Memtable находится в энергозависимой памяти, поэтому при сбое ее содержимое исчезает. Именно для этого существует WAL.

При перезапуске RocksDB воспроизводит каждую подтвержденную операцию записи, которая еще не была сброшена в SST. Система вставляет эти записи в новую memtable, восстанавливая состояние до сбоя. Стоимость восстановления пропорциональна объему несброшенных данных, поэтому жизненные циклы WAL и memtable связаны. После безопасного сброса содержимого memtable в SST соответствующие записи журнала устаревают, и WAL можно усечь.

Запись становится долговечной сразу после добавления в журнал. Позже, когда сброс организует данные, ее чтение становится дешевым. B-деревья связывают эти процессы, а LSM-деревья разделяют их. Большинство особенностей этой структуры вытекает именно из такого разделения. 

Как Solana нагружает путь записи?

В первой статье этой серии описано, как Agave хранит реестр Solana в RocksDB. С точки зрения пути записи эта нагрузка близка к специально разработанному стресс-тесту. Shred — необработанные единицы данных реестра — непрерывно поступают по сети на линейной скорости. Каждый из них должен пройти добавление в WAL и вставку в memtable, прежде чем слой хранения валидатора выполнит свою работу.

Используется тот же механизм, который рассмотрен в этой статье, но в рабочем масштабе. Когда поступают shred, путь вставки Blockstore в Agave проверяет целый пакет входящих shred, пытается восстановить отсутствующие с помощью Reed-Solomon и помещает все данные — содержимое shred, метаданные слотов, метаданные стирающего кодирования и обновления индекса — в один WriteBatch RocksDB, прежде чем зафиксировать их одной атомарной записью.

Упрощенный фрагмент из insert_data_shred:

// We don't want only a subset of these changes going through.
write_batch.put_bytes::<cf::ShredData>((slot, index), &shred.payload)?;
update_slot_meta(/* ...metadata updates */);
data_index.set_present(index, true);

Этот комментарий выражает основную мысль статьи девятью словами инженеров Agave: пакет является единицей атомарности, и сбой валидатора в процессе вставки никогда не должен оставлять реестр обновленным лишь частично. 

Пакет из одной записи, рассмотренный в пошаговом примере, внутри валидатора превращается в пакет из тысяч записей: shred и их метаданные в нескольких семействах столбцов, один диапазон номеров последовательности, одно добавление в WAL и одна групповая фиксация.

Преимущество здесь в том, что в начале shred указан номер слота — кортеж (slot, index) из упрощенного фрагмента кода является ключом ShredData, — а номера слотов растут почти монотонно. Поэтому каждая memtable принимает узкую, преимущественно последовательную полосу пространства ключей, а при сбросе создаются файлы L0, которые почти не пересекаются.

Мы напрямую ощущаем работу этого пути записи. 

Архивные системы Helius загружают полную историю транзакций Solana в RocksDB. Это сотни терабайт данных в постоянно растущей нагрузке, ориентированной на добавление. Миграция, результатом которой стала эта архитектура, описана в нашей статье о переходе с ClickHouse на RocksDB.

Заключение

LSM-дерево — это сделка с оборудованием. Все операции записи становятся последовательными в обмен на отложенную организацию данных. Поэтому путь чтения вынужден искать данные в большем количестве мест, чем, например, B-дерево. Memtable принимает данные, WAL гарантирует их сохранность, а SST их накапливают. Для флеш-хранилища, где произвольная перезапись наказывается дважды, это отличная сделка.

Однако запись — это простая половина задачи. Цена такой архитектуры оплачивается при чтении, поскольку актуальное значение ключа может находиться в memtable, файле L0 или на любом нижележащем уровне. Механизмы, которые ограничивают эту цену, — самая интересная часть инженерии LSM. 

В следующей статье серии мы разберем путь чтения: memtable, фильтры Блума, кеш блоков и треугольник усиления на практике.

Если перспектива проследить путь одной пары «ключ — значение» через четыре разные структуры данных кажется вам отличным способом провести день, присоединяйтесь к нам. Описанные в этой серии системы мы развертываем, эксплуатируем и настраиваем в масштабе глобальных рынков капитала. Мы расширяем инженерную команду. Все открытые вакансии доступны на helius.dev/careers.