LSM-дерево

У этого сайта 1184 коммита. В них 11 762 раза менялось содержимое какого-нибудь файла: routes/web.php переписан 101 раз, словари интерфейса — по 82, а 131 раз файл удаляли. Представьте, что сайт хранит файлы не на диске, а в базе ключ-значение: путь — ключ, содержимое — значение. Тогда история — это поток записей, полмиллиарда байт. B-дерево правило бы для каждой записи страницу на диске прямо на месте. LSM-дерево поступает иначе: никогда не правит записанное. Нажмите «Пуск» — вся история пройдёт через дерево за полминуты.

Синяя полоса — память: записи копятся в ней, пока не наберётся 4 МБ. Потом память целиком ложится на диск одним отсортированным прогоном в L0. Когда в L0 четыре прогона, они сливаются со следующим уровнем, а переполненный уровень сливается с ещё более глубоким. К концу истории программа записала 477 МБ, а дерево — 1697 МБ, в 3,56 раза больше: каждый байт переписан при слияниях ещё два с половиной раза. Зато ни одна запись не потребовала чтения с диска и не тронула старые данные.

Идея

Новые записи идут в отсортированную структуру в памяти. Когда она заполнится, её целиком пишут на диск одним последовательным куском — неизменяемым отсортированным прогоном. Чтение смотрит в память, потом в прогоны от новых к старым и берёт первую найденную версию. Чтобы прогонов не становилось всё больше, фоновый процесс сливает их, как в сортировке слиянием, оставляя у каждого ключа только новейшую версию. Удаление — тоже запись: «надгробие», которое закрывает старые версии ключа.

Названия пришли из статьи о Bigtable 2006 года: структура в памяти — memtable, прогон на диске — SSTable, sorted string table. Память обычно — список с пропусками или сбалансированное дерево: ключи в ней должны идти по порядку, чтобы сброс был простой выпиской. Чтобы записи не пропали, если процесс упадёт до сброса, каждую сначала дописывают в журнал на диске — последовательно, в конец файла. Внутри SSTable ключи разбиты на блоки по несколько килобайт, а в конце файла лежит индекс: первый ключ каждого блока. Найти ключ в прогоне — двоичный поиск по индексу и одно чтение блока.

Почему не B-дерево

B-дерево хранит каждый ключ на своём месте. Чтобы записать новую версию routes/web.php, нужно найти его лист, прочитать страницу, изменить и записать страницу обратно — чтение и запись в случайном месте диска на каждое обновление. LSM-дерево сначала копит записи в памяти и пишет их пачкой. Последовательная запись на любом носителе в десятки раз быстрее случайной, а на SSD к тому же меньше изнашивает ячейки: разница между «подряд» и «вразнобой» — одна из самых больших в вычислениях. Поэтому базы, куда пишут непрерывным потоком — события, метрики, сообщения, — почти всегда стоят на LSM.

Платят за это трижды. Перезапись: один и тот же байт переписывается при каждом слиянии, через которое проходит. Место: пока слияние не дошло, на диске лежат и старые версии ключа, и надгробия. Чтение: ключ может оказаться в любом из прогонов, и смотреть приходится, пока не найдёшь. Всё устройство LSM-дерева — это выбор, сколько платить каждой из трёх монет.

Версии и надгробия

У каждой записи есть порядковый номер. При слиянии прогонов у ключа остаётся версия с наибольшим номером, остальные пропадают. В истории сайта это работает в полную силу: из 477 МБ записанного живых данных к концу истории — 231 МБ. Остальное — старые версии переписанных файлов, и вычищают их только слияния.

С удалением так не получится: если просто не писать ключ, чтение найдёт его старую версию в глубоком прогоне. Поэтому удаление пишет надгробие — запись «ключа больше нет». Надгробие закрывает все более старые версии, и при слиянии его нельзя выбрасывать, пока где-то ниже может лежать старая версия: иначе удалённый файл «воскреснет». Выбросить надгробие можно, когда слияние дошло до самого нижнего уровня или когда ни в одном более старом прогоне этого ключа нет. Поищите в сцене planetshader.js: его удалили в конце истории, и надгробие ещё лежит в верхнем прогоне. А GameController.php удалили давно — надгробие дошло до дна, исчезло вместе со всеми версиями, и чтение честно проходит все прогоны, ничего не находя. Об этом первая задача.

Уровни и ярусы

Когда сливать — главный вопрос. Два основных ответа.

Уровни (leveled). На каждом уровне — один отсортированный прогон, и каждый уровень в T раз больше предыдущего. Новые данные сливаются с прогоном уровня сразу, а переполненный уровень уходит вниз. Прогонов мало — по одному на уровень, — и чтение быстрое. Зато данные уровня переписываются каждый раз, когда сверху приходит новая порция, — в среднем порядка T/2 раз, пока уровень не заполнится, и так на каждом уровне. Так по умолчанию устроены RocksDB и LevelDB.

Ярусы (tiered). Прогоны на уровне копятся, не сливаясь, пока их не станет T; тогда все T сливаются в один и уходят вниз. Каждый байт переписывается примерно по разу на уровень, но на уровне лежит до T прогонов, и чтению, не нашедшему ключ, приходится проверить их все. Так по умолчанию устроена Cassandra.

Ниже та же история сайта через оба вида деревьев с ростом уровней от 2 до 10 раз.

Ярусная схема с ростом в 10 раз переписывает каждый байт всего 1,64 раза, но держит на диске в среднем 6,2 прогона, а к концу истории — 11, и лишнего места занимает 25 %. Уровневая переписывает 3,6–3,9 раза при любом росте, зато прогонов в среднем три, а лишнего места 4–6 %. На такой короткой истории уровней всего три-четыре, и нижний не успевает заполниться, поэтому разница не столь велика, как в больших базах. Но направление то же: нельзя одновременно мало писать, мало хранить и мало читать. Манос Атанассулис с соавторами в 2016 году назвали это гипотезой RUM — read, update, memory: улучшить можно любые две стоимости, но третья вырастет.

Чтение: фильтры Блума

Самое дорогое чтение — ключа, которого нет. Оно проходит все прогоны: в сцене запрос несуществующего файла читает их все. Помогает фильтр Блума у каждого прогона — маленький битовый массив в памяти, который на вопрос «есть ли ключ в прогоне» отвечает «точно нет» или «возможно». При 10 битах на ключ он ошибается примерно в 1 % случаев, и почти все лишние чтения исчезают: прогон открывают только тогда, когда фильтр сказал «возможно». Для 5790 ключей это 7 КБ памяти на фильтры.

Но поровну делить биты не обязательно. Ложное срабатывание фильтра маленького верхнего прогона стоит одно лишнее чтение — ровно столько же, сколько у огромного нижнего, а битов на маленький нужно в сотни раз меньше. Нив Даян, Манос Атанассулис и Стратос Идреос в 2017 году показали, что выгоднее давать верхним прогонам больше бит на ключ, а нижним — меньше: при той же памяти ожидаемое число лишних чтений падает, и тем сильнее, чем больше уровней. Посчитать это распределение — вторая задача.

С диапазонами фильтры не помогают: запрос «все файлы каталога resources/js/» вынужден открыть каждый прогон, найти в нём начало диапазона двоичным поиском и слить все прогоны на лету, кучей по ключам, пропуская устаревшие версии и надгробия. Поэтому длинные сканы в LSM-дереве дороже, чем в B-дереве, где диапазон лежит подряд в листьях.

Код

Листинг проводит историю сайта через оба вида деревьев с теми же параметрами, что сцена: память 4 МБ, четыре прогона в L0, первый уровень 16 МБ, рост в 4 раза. В конце — пять чтений: горячий файл, свежий, только что удалённый, давно удалённый и несуществующий.

Свежий solver.js ещё в памяти, и диск не нужен вовсе. routes/web.php переписывали до последних коммитов, и он в верхнем прогоне. Удалённый недавно planetshader.js находится сразу — как надгробие. А давно удалённый файл и несуществующий проходят все прогоны: четыре у уровневого дерева и пять у ярусного. Модель упрощена: переполненный уровень здесь сливается вниз целиком, а RocksDB режет уровень на файлы по десятки мегабайт и сливает вниз по одному файлу, — переписывать при этом приходится столько же, но ровнее, без всплесков.

Сколько это стоит

Запись — вставка в структуру в памяти, O(log m) для m записей в ней, плюс доля в будущих слияниях. Если уровней L и каждый в T раз больше предыдущего, в уровневой схеме байт переписывается около T·L/2 раз, в ярусной — около L раз, а L ≈ log_T(N/M) для N байт данных и M байт памяти. Чтение — по одному прогону на уровень в уровневой схеме и до T на уровень в ярусной; с фильтрами Блума — почти всегда один прогон на найденный ключ. Место — данные плюс устаревшие версии: в уровневой схеме лишнего порядка 1/T, в ярусной бывает и вдвое больше нужного, пока большое слияние не закончилось.

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

Где работает

Встраиваемые хранилища. LevelDB написали Джефф Дин и Санджай Гемават; RocksDB вырос из него и стал хранилищем под многими базами данных и очередями. Оба по умолчанию сливают уровнями.

Распределённые базы. Bigtable, HBase, Cassandra, ScyllaDB — запись идёт в память и журнал, сброс — в неизменяемые файлы, слияния — в фоне. Неизменяемость здесь особенно удобна: готовый файл можно копировать на другие машины и сравнивать, не боясь, что он изменится.

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

История

Патрик О’Нил, Эдвард Чен, Дитер Гавлик и Элизабет О’Нил описали LSM-дерево в 1996 году в журнале Acta Informatica. Задачей был банковский журнал операций: записей огромный поток, а читают их редко, и B-дерево тратило бы на каждую вставку случайное чтение диска. В 2006 году статья о Bigtable дала структуре нынешние имена — memtable и SSTable — и показала, как строить на ней распределённое хранилище. LevelDB открыли в 2011 году, RocksDB — в 2013-м.

Задачи

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