В предыдущей статье о Vinyl я рассказывал об архитектуре LSM-движка Tarantool. 8 лет с написания статьи показали, что Винил настолько хорош, что его не нужно менять :). Если серьёзно, сегодня я расскажу о тех изменениях которые мы внесли в алгоритм в рамках форка от Picodata, и неизбежно коснусь более глубокой проблематики работы LSM-деревьев, а конкретно работы планировщика слияний (compaction scheduler).

В своей статье начну с базы, а именно того, как устроено LSM дерево. Затем расскажу об особенностях Винила и напомню его ключевые отличия от классических LSM движков. Потом поговорим про задачи compaction scheduler, опять же, сравним то что делает текущий Винил, какие с этим есть проблемы, и как эти проблемы можно решить. А закончим собственно описанием ключевых изменений уже доступных в Tarantool 2.11.8 от Picodata и в Picodata 26.1.

Начну с базы, а именно того, как устроено тривиальное LSM дерево. Основная идея LSM - амортизация стоимости вставок за счёт более высокой стоимости чтений. При вставке данные не попадают немедленно в свой целевую локацию во внешней памяти (на SSD), а кэшируются в оперативной памяти. При переполнении кэша, он вытесняется на диск, а после нескольких вытеснений данные из всех вытесненных файлов сортируются и сливаются в новый общий файл где изменения по одному и тому же ключу объединяются. Такой подход фактически меняет субъект хранения - вместо того, чтобы хранить строки, LSM деревья хранят и упорядочивают изменения строк. При чтении все изменения собираются воедино для получения итогового результата.

Подход получил широкое распространение с переходом на SSD диски, где чтение в разы дешевле чем запись, но в целом отлично себя проявляет и с SATA дисками, за счёт снижения рандомизированного ввода-вывода. Подробнее об устройстве Винила вы можете почитать в моей предыдущей статье.

Compaction vs VACUUM

Подход с версионированием изменений не уникален для LSM. Похожим образом MVCC движки, например PostgreSQL управляют множеством версий порождаемых транзакциями над одними и теми же данными. Но между VACUUM в B-tree и слиянием в LSM есть принципиальная разница.

В B-tree стоимость операции предсказуема. Вставка строки — это O(log N) обращений к диску, плюс-минус split страницы. VACUUM работает асинхронно и не влияет на стоимость транзакции. Да, если VACUUM не успевает, таблица «раздувается» (table bloat) — но каждая отдельная транзакция по-прежнему стоит O(log N).

В LSM-дереве такой гарантии нет. Вставка строки в L0 (верхний уровень, in-memory) — O(1). Но если L0 переполняется, запускается дамп (сброс на диск). Дамп может переполнить L1, что вызовет слияние L1 с L2. Слияние L1 с L2 может переполнить L2, что вызовет слияние L2 с L3 — и так далее, каскадом, вплоть до полного слияния всех уровней (major compaction). Одна вставка может спровоцировать перезапись всех данных на диске.

Каскадное слияние

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

Третий пример плохой работы базового алгоритма - time series data, то есть данные временных рядов. Такие данные заведомо упорядочены, но базовый алгоритм будет переупорядочивать их снова и снова, при прохождении по уровням LSM дерева.

Read, write и space amplification

Apache Cassandra в попытке эффективно учесть все специальные случаи реализует 4 “стратегии” слияний, которые могут быть выбраны пользователем при создании таблицы:

  1. STCS — Size-Tiered Compaction Strategy, при слиянии группирует файлы примерно одинакового размера и сливает их. Триггером является количество файлов одинакового размера (по умолчанию 4).

  2. LCS — Leveled Compaction Strategy, организует SSTable в уровни (levels), где каждый следующий уровень в 10 раз больше предыдущего, а внутри уровня файлы не пересекаются по диапазонам ключей.

  3. TWCS — Time Window Compaction Strategy, TWCS разбивает SSTable по временны́м окнам (например, по часам или дням) и применяет STCS внутри каждого окна. Когда все данные в окне истекают по TTL, весь SSTable просто удаляется целиком — без слияния. Удобна в основном для time-series и логов с фиксированным TTL, где данные пишутся и читаются в хронологическом порядке.

  4. UCS — Unified Compaction Strategy (Cassandra 5.0) - попытка объединить идеи STCS и LCS в единую параметризованную стратегию, где для каждого уровня иерархии можно независимо задать tiered или leveled поведение через параметр scaling_parameter (W).

Как видно, UCS пытается заменить LCS и STCS, а TWCS - исключение для time series data. UCS наиболее близка к тому что делает Винил. Так, в Винил можно задать run_size_ratio, то есть параметр leveled стратегии, и run_count_per_level, то есть параметр из STCS стратегии. При этом Винил не применяет run_count_per_level к последнему уровню LSM дерева, оставляя на нём лишь один уровень, что было описано в уже более поздних статьях (см. Dostoevsky paper).

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

Эти цели – read, write, и space amplification.

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

Так, read amplification показывает то, во сколько раз больше байт СУБД вынуждена прочитать при чтении 1 байта полезных данных. Ну например, затребовали вы срочно год рождения некоего субъекта, идентифицированного его СНИЛС. Теоретически вам нужно прочитать 4 байта, а вот Б-дерево вам предложит чтение 1 страницы, то есть 4 килобайт. Read amplification составит 4096:4 или 1024.

Write amplification измеряется похожим образом, но применяется к записи на диск. Меняем 10 байт, пишем 100 байт - write amplification составит 10.

Space amplification позволяет учесть затраты на фрагментацию, технические данные и мусор, и измеряет соотношение реальных полезных данных на диске и объёма занимаемого дискового пространства.

Так, для Б-дерева с небольшим размером блока, скажем в 4кб, типичный read/write/space amp составляет 12-15/12-15/1.2-1.5. Легко видеть, что Б-дерево - довольно сбалансированная структура данных.

Для LSM дерева цифры выглядят совсем по-другому: скажем 20-30/2-3/1.5-2. В LSM основная работа происходит при чтениях, но есть и другой аспект - разброс выше и фактические результаты зависят от конкретной нагрузки.

Из приведённых примеров, кажется, очевидно почему цели read, write и space-amplification взаимно противоречивы: снижение write amplification требует снижения compaction, что в свою очередь приводит к повышению read и space amplification. Снижение read amplification требует повышения compaction, что в целом может приводить к временному повышению space amplification, так как необходимо хранить промежуточные результаты слияния, ну и конечно write amplification, т.к. это слияние нужно делать. Ну и снижение space amplification в сценарии удаления мусора из дерева, а конкретно tombstones, конечно приводит к повышению write amplification за счёт более частых слияний.

Также можно прикинуть, что при стоимости чтений в SSD дисках в 4-8 раз ниже стоимости записи (посмотрите характеристики по IOPS у вашего SSD) “на круг” LSM деревья получаются “выгоднее”.

Треугольник amplification

Хотя read, write и space amplification прекрасные индикаторы “отклонения” от идеального результата, из них нельзя очевидным образом вывести единый критерий оптимизации алгоритма. Начнём с того, что сам по себе алгоритм слияний не знает какие будут действия производиться с данными в будущем. Ну, например, нет никакого смысла делать слияние в диапазоне данные в котором будут в ближайшем будущем удалены.

Вторая причина в том, что даже найдя способ оптимизировать каждую из величин, не получится вывести относительную ценность величин между собой. Ну например, если у вас OLTP workload и вы нацелены в первую очередь на снижение 99.9% latency, вы готовы мириться с space amplification. Если вы в основном складируете данные и обращаетесь к ним редко (скажем, лишь в случае инцидента), то ваш главный драйвер - space amplification, иначе вы закупите на ваш склад данных слишком много дисков.

Приоритеты

Нужен какой-то здравый смысл, чтобы привести все три параметра в соответствие друг другу. Забегая вперёд, при реализации нового compaction scheduler цели выстроились в следующий порядок:

  1. Гарантия на худший случай. Как OLTP-first система, мы должны избегать ситуаций когда стоимость чтения или записи, или объём на диске выходит за пределы нормы для каких-то краевых случаев. Даже если при этом средние затраты на compaction вырастут.
  2. Минимизация тюнинга. Даже с пониманием внутреннего устройства у современного разработчика просто нет времени на то, чтобы экспериментировать с нагрузочными тестами, да и нагрузка со временем может поменяться.
  3. При прочих равных, write amplification стоит на первом месте, потому что напрямую влияет на износ SSD. Read amplification можно конвертировать в write amplification по тарифу 8:1 (примерно во столько раз ваш SSD делает больше чтений чем записи, плюс). Space amplification стоит на третьем месте, и на нём можно сфокусироваться если у планировщика нет других задач.

Устройство Vinyl

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

В Vinyl данные на диске хранятся в run-файлах — это отсортированные файлы, аналог SST-файлов в RocksDB. Каждый run-файл содержит набор строк, упорядоченных по ключу. Отличие run-файла от sst-файла в том, что первый не имеет ограничения по размеру, и может быть очень большим - на практике, до 1-2ГБ.

Ключевое пространство индекса разбито на непрерывные диапазоны (в коде — vy_range). Каждый диапазон отвечает за свой участок ключей и содержит упорядоченный список ссылок на данные — от самых свежих к самым старым. Но ссылается диапазон не на целый run-файл, а на его часть, через специальную диапазонную ссылку — slice. Slice — это кортеж вида (run-файл, начальная страница, конечная страница). Один run-файл может быть разделён на несколько slice, каждый из которых принадлежит своему диапазону. Механизм диапазонов позволяет Винилу решить сразу несколько проблем:

  • снизить space amplification при compaction, так как даже major compaction одного диапазона в 128МБ (дефолтное значение) требует лишь 128мб временных данных
  • повысить параллелизм слияний, т.к. одновременно может происходить compaction сразу нескольких ranges
  • исключить неизменяемые диапазоны из слияний, то есть снизить write amplification
  • избежать спайков, т.е. взрывных эффектов от работы compaction scheduler, как это работает - сейчас расскажу.

При дампе (сбросе данных из памяти на диск) создаётся один run-файл, который может пересекать несколько диапазонов. Вместо того чтобы записывать отдельный файл для каждого диапазона, мы записываем один файл и создаём несколько slice — по одному на каждый затронутый диапазон.

Run-файл, slice и диапазоны

Когда диапазон нужно разбить пополам (потому что он стал слишком большим), нам не нужно перезаписывать run-файлы — достаточно создать новые slice.

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

Теперь представьте, у вас 1000 диапазонов, и до дампа в каждом был ровно 1 run-файл при пороге в 2 для старта compaction. После дампа становится 2 – и все 1000 диапазонов одновременно требуют слияния. Пропускная способность записи проваливается, следующий дамп задерживается, квота памяти исчерпывается, транзакции блокируются.

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

Стадный эффект и рандомизация

Как compaction scheduler принимает решение о слиянии

Рассмотрим отдельно взятый диапазон LSM дерева. Slice в диапазоне организованы в уровни, как в классической LСS стратегии. Каждый следующий уровень в run_size_ratio раз (по умолчанию 3.5) больше предыдущего. На каждом уровне может быть не более run_count_per_level файлов (без учёта рандомизации). Когда порог превышен — этот уровень и все уровни выше идут на слияние. Распределение run-файлов по уровням проходит от более новых к более старым: свежие изменения находятся «наверху» пирамиды, старые – внизу.

Shape-based compaction

На последнем (самом нижнем) уровне допускается не более одного файла. Это гарантирует, что space amplification не превышает (run_count_per_level - 1) / (run_size_ratio - 1) + 1. При стандартных настройках (2 файла на уровень, ratio 3.5) – менее 1.4x.

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

RocksDB начиная с версии 8.4 использует аналогичный подход — Dynamic Level Sizing — тоже вычисляя целевые размеры от фактического размера последнего уровня. Но у RocksDB каждый уровень — глобальная структура, а у нас — per-range. Каждый диапазон имеет свою форму дерева, свой приоритет, свой темп слияний.

Что с этим не так.

В целом, стратегии Винила нельзя отказать в универсальности. И триггером для нововведений Picodata была не скорость работы, а досадный баг, который обнаружился на time series data.

Выглядел он следующим образом. Workload вставлял данные в пустую таблицу строго последовательно. Хотя данные были отсортированы, Винил периодически включал compaction, т.к. shape-level стратегия не могла вписать равные по размеру run файлы образующиеся в результате дампов в форму “пирамиды”. За то, чтобы не сливать изменения из непересекающихся диапазонов в Виниле отвечает механизм диапазонов, ну а некоторым количеством ненужных слияний в пределах одного диапазона, казалось, можно было бы пренебречь.

И действительно, проблема вылезла не от бесполезных compaction. Она образовалась при разбиении большого диапазона, образовавшегося в результате слияний, на два меньших. Чтобы избежать ненужной осцилляции слияний и разбиений диапазонов, триггер на разбиение срабатывает лишь тогда, когда диапазон превысил свой сконфигурированный размер в 1.5 раза. Для того чтобы достичь такого размера требовалось 2-3 дампа, после чего диапазон успешно разбивался. В новый диапазон (справа) продолжали добавлять данные, поэтому через какое-то время для него вызывался compaction, а затем и split (разбиение). После завершения вставок объём данных на диске превышал объём данных более чем в два раза!

Происходило это из-за следующего. После разбиения, нижняя половинка диапазона казалась shape-based scheduler’у “идеальной”: она состояла из одного ран файла который никогда не менялся. Но этот run-файл содержал лишь 50% полезных данных, а вторые 50% уже давно “уехали” в верхний диапазон и были не нужны. И так для каждого созданного диапазона кроме последнего.

Когда эта проблема вскрылась, в ней бесило сразу всё:

  • ненужные слияния. shape-based scheduler не видел что run-файлы не пересекаются в пределах одного диапазона и слияние бесполезно
  • слепота к bloat образующаяся в результате разбиения
  • разбухание не только данных на диске, но и данных в оперативной памяти, т.к. page index для “мёртвых” данных полностью загружался в RAM и сидел там без дела.

Time-series bloat

Но это ещё полбеды. Вторая проблема наступала при удалении старых time series данных. Скрипт удаления пробегался по данным начиная с конца, читал топ 1000 самых старых данных, и удалял их. И так бесконечно. Что, с учётом того что compaction scheduler запускал compaction только когда значительная часть данных была удалена, приводило к квадратичной стоимости чтений при удалении.

Решение

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

Но это не устраняло непосредственную причину bloat, и оставался риск того, что к нему приведёт какой-то другой сценарий. При любом разбиении vy_range, его run-файлы резались пополам, что, через некоторое время, могло привести к bloat.

Оптимальное решение должно было:

  • при разбиении диапазонов выбирать точку разбиения так, чтобы она находилась примерно посередине разбиваемого диапазона, но при этом минимизировала количество “разрезаемых на части” run-файлов
  • compaction не должен был включать непересекающиеся данные в общий план
  • если bloat всё же появлялся, необходимо было его обнаруживать и удалять,
  • ну и наконец, должен был появиться цикл обратной связи от чтения данных к compaction. Если чтение данных неэффективно из-за мусора, должен был проходить compaction даже если форма дерева и кажется “идеальной”.

Собственно, всё это и было сделано в последнем релизе. Само решение потребовало пересмотреть работу планировщика, что, кажется, пошло ему на пользу. В Виниле появилась явная сущность - план для compaction, все стратегии compaction оказались описаны явно, и приоритеты между ними также поставлены явно. Старый добрый shape based compaction остался на первом месте, но с важным уточнением: для compaction выбирается самый большой кластер из run-файлов с пересекающимися ключами.

Выбор кластера пересекающихся run-файлов

На втором месте стоит read amplification драйвер. Если мы видим, что количество отфильтрованного мусора при чтении зашкаливает – мы также проводим compaction. И на третьем месте стоит space amplification – если работы по первым двум критериям нет, и мы видим что более 10% какого-то run-файла – неиспользуемый мусор, мы переписываем этот run файл.

Результаты

Для тестирования использовались workloads в стиле YCSB на наборе данных в 100 миллионов записей (~20 ГБ). Замеры проводились на одном ядре, со стандартными настройками. Инструмент для бенчмарков – pico_ycsb.

Workload A (50% чтение / 50% запись, Zipfian)

  Baseline Новый Изменение
RPS 224 793 351 427 +56%
Write Amp 3.14x 1.01x -68%
Space Amp 2.11x 1.21x -43%
Read Amp 14.34x 17.68x +23%
Диск 42.1 ГБ 24.1 ГБ -43%

Workload B (последовательная вставка + чтение)

  Baseline Новый Изменение
RPS 361 443 696 148 +93%
Write Amp 3.82x 0.93x -76%
Space Amp 7.74x 6.94x *
Read Amp 12.55x 4.50x -64%
Диск 154.9 ГБ 138.8 ГБ -10%
Compaction I/O 241 ГБ 0 -100%

* Space amplification в workload B нельзя сравнивать напрямую: за счёт удвоения RPS новый планировщик вставил 1.03 млрд записей против 484 млн у baseline. При пересчёте на запись: baseline – 265 байт/запись на диске, новый – 123 байт/запись.

Workload C (вставка + удаление + чтение + скан)

  Baseline Новый Изменение
RPS 149 723 129 930 -13%
Write Amp 2.49x 1.26x -49%
Space Amp 2.75x 1.49x -46%
Read Amp 12.32x 11.81x -4%
Диск 55.0 ГБ 29.8 ГБ -46%

Наиболее впечатляющий результат – workload B (append-only, time series). Старый планировщик бесполезно сливал непересекающиеся файлы, тратя на это почти 4x write amplification. Новый – не трогает то, что не нужно трогать, и RPS почти удваивается. В workload A рост read amplification на 23% – плата за снижение write amp в 3 раза; на практике это означает чуть больше обращений к диску при чтении, но значительно меньше при записи.

Сразу отвечу на вопрос, а как теперь Винил по сравнению с Кассандрой? По нашим измерениям – нигде не хуже, а в ряде задач лучше как с точки зрения I/O, так и с точки зрения RPS. Но пробовать и решать вам.

Что впереди

Мы, кажется, всерьёз взялись за Винил, и новый планировщик

  • лишь часть реализованных изменений. То что я перечислю ниже уже не настолько уникально для дизайна Винила, но будет полезно если вы - пользователь Tarantool или Picodata. Словарную компрессию мы также включили в релиз 2.11.8, а вот остальные изменения лежат на ветке kosja-vinyl-page-index и мы постепенно будем их доводить до production состояния и включать в наш форк.

Страничный индекс нового формата

Сейчас Vinyl хранит индекс страниц (page_info) каждого run-файла целиком в памяти. Для терабайтного набора данных это сотни мегабайт одних только метаданных.

Новый формат (файлы .index2) группирует метаданные в индексные блоки по 64 страницы. Каталог блоков — несколько десятков килобайт — хранится в памяти; сами блоки подгружаются по требованию через 2Q-кэш (по умолчанию 128 МБ). По сути, это двухуровневый B-tree: компактный каталог в RAM, данные на диске. Апгрейд и даунгрейд возможен без реимпорта данных, новые индексы строятся автоматически, а для того чтобы вернуться к старым достаточно лишь удалить все .index2 файлы и рестартовать с –force-recovery.

Binary fuse8 вместо фильтров Блума

Классический фильтр Блума требует ~10 бит на ключ и должен целиком помещаться в памяти. Мы заменяем его на binary fuse8 filter — структуру, требующую ~9 бит на ключ, и со значительно большей точностью. Фильтры хранятся в индексных блоках, а не ассоциированы с run файлами целиком, что также повышает точность фильтра.

MinHash-скетчи

Каждый индексный блок содержит MinHash-скетч (64 хеша) своего набора ключей. При планировании слияния скетчи двух slice можно сравнить за O(1) и оценить коэффициент Жаккара — степень пересечения их ключевых множеств. Если два файла на одном уровне почти не пересекаются — нет смысла их сливать: это не уменьшит ни space amplification, ни read amplification.

TTL

Поддержка TTL на уровне движка позволaет автоматически удалять устаревшие строки. В сочетании с индексными блоками и MinHash-скетчами это даёт возможность эффективно определять, какие run-файлы содержат только истёкшие данные, и удалять их целиком — без слияния.

Словарная компрессия

Vinyl использует ZSTD для сжатия страниц данных. Стандартный ZSTD работает в рамках одной страницы (по умолчанию 8 КБ) – этого контекста недостаточно для построения хорошего словаря. Мы добавили поддержку словарной компрессии (ZSTD dictionary compression): при дампе или слиянии движок собирает сэмпл данных (до 2 МБ) и обучает на нём 64-килобайтный словарь через ZDICT_trainFromBuffer(). Словарь хранится в vylog и используется при сжатии всех последующих страниц данного LSM-дерева.

Обучение происходит адаптивно: если словарь даёт выигрыш более 5% по сравнению со сжатием без словаря, период обучения сокращается вдвое (минимум каждые 4 дампа). Если выигрыша нет – период удваивается (максимум 256 дампов). Словарь включается per-index через compression_dict = true при создании индекса, и может быть включён или выключен на лету через index:alter(). Словарная компрессия наиболее эффективна для данных с повторяющейся структурой – JSON-документы, логи, protobuf.

Итого

Итого не будет. Надеюсь статья была Вам полезна. Всё что в ней описано - открытое программное обеспечение, и у нас на сайте мы предоставляем готовые пакеты под целый ряд операционных систем. Я лично всегда доступен для вопросов и комментариев в профильных чатах – @picodataru, @tarantoolru, @databaseinternalschat. Всего вам доброго, и до скорых встреч.