Хабрахабр

Хранение данных на Виниле

С тех пор мы добавили много новых возможностей, но хранение данных на диске — такая объемная тема, что основы, о которых идет речь в этой статье, совсем не изменились. В 2016-м я выступил на Highload с докладом про Vinyl, движок для хранения данных на диске в Tarantool.

Содержание (чтобы удобно было ориентироваться):

Почему мы написали новый движок?

Как известно, Tarantool — транзакционная, персистентная СУБД, которая хранит 100 % данных в оперативной памяти. Основные преимущества хранения в оперативной памяти — это скорость работы и простота использования: базу данных не нужно тюнить, тем не менее, производительность остаётся стабильно высокой.

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

В сообществе разработчиков открытого ПО есть готовые библиотеки, которыми можно было воспользоваться. Первый вопрос, на который нужно было ответить: создавать свой движок или использовать уже существующую библиотеку? Но также был целый ряд менее известных библиотек: WiredTiger, ForestDB, NestDB, LMDB. На момент выбора активнее всего развивалась библиотека RocksDB, которая к настоящему времени стала одной из самых популярных.

Тем не менее, посмотрев на исходный код имеющихся библиотек и взвесив все «за» и «против», мы решили написать свою.

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

Наш подход с обработкой транзакций в выделенном потоке позволяет обойтись без лишних блокировок, межпроцессного взаимодействия и других накладных расходов, поедающих до 80 % процессорного времени многопоточных СУБД. Дело в том, что в основе Tarantool лежит архитектура на основе акторов (actor based architecture).


Процесс Tarantool состоит из фиксированного количества «ролевых» потоков.

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

Алгоритм

Отказавшись от идеи встраивания существующих библиотек, необходимо было решить, на основе какой архитектуры строить свою. Сегодня есть два поколения решений для хранения данных на диске: использующие разновидности B-деревьев и новые, построенные на основе LSM-деревьев (Log Structured Merge Tree). Например, MySQL, PostgreSQL, Oracle используют B-деревья, а Cassandra, MongoDB, CockroachDB уже используют LSM.

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

Для этого, разберём устройство обычного B-дерева и связанные с ним проблемы.
«B» в названии B-tree означает Block, то есть это сбалансированное дерево, состоящее из блоков. Прежде чем разбираться с тем, как LSM-деревья устроены в Tarantool, давайте посмотрим, как они работают. Опустим вопросы наполнения дерева, балансировки, разбиения и слияния блоков, подробности вы сможете прочитать в Википедии. Блок содержит отсортированный список элементов, то есть пары ключ + значение. Разберём, как в B-дереве осуществляется поиск и обновление данных. В итоге мы получаем отсортированный по возрастанию ключа контейнер, минимальный элемент которого хранится в крайнем левом узле, а максимальный — в крайнем правом.


Классическое B-дерево

Если ключ обнаружен в корневом блоке, поиск заканчивается; в противном случае мы переходим в блок с наибольшим меньшим ключом, то есть в самый правый блок, в котором ещё есть элементы меньше искомого (элементы на всех уровнях расположены по возрастанию). Если нужно найти элемент или проверить его наличие, мы начинаем поиск, как обычно, с вершины. В конце концов мы окажемся в одном из листьев и, возможно, обнаружим искомый элемент. В случае, если и там элемент не найден, мы снова переходим на уровень ниже. Запись в самом простом и массовом случае осуществляется аналогично: мы находим блок, содержащий искомый элемент и обновляем (вставляем) значение в нём. Предполагается, что блоки дерева хранятся на диске и читаются в оперативную память целиком, то есть за один поиск алгоритм считывает logB(N) блоков, где N — число элементов в дереве.

В блоке, с учётом накладных расходов, можно будет разместить до 40 элементов. Чтобы наглядно представить себе эту структуру, давайте возьмем дерево на 100 000 000 узлов и предположим, что размер блока равен 4096 байт, а размер элемента — 100 байт. Очевидно, что на любом современном компьютере все уровни, кроме последнего, успешно попадут в кэш файловой системы, и фактически любая операция чтения будет требовать не более одной операции ввода-вывода. В дереве будет около 2 570 000 блоков, пять уровней, при этом первые четыре займут порядка 256 МБ, а последний — порядка 10 ГБ.

Предположим, что мы обновляем один элемент дерева. Ситуация выглядит существенно менее радужно при смене точки зрения. Таким образом, нам пришлось записать в 40 раз больше, чем реальный объём изменённых данных! Так как операции с деревом работают через чтение и запись блоков, мы вынуждены прочитать 1 блок в память, изменить 100 байт из 4096 и записать новый блок на диск. Принимая во внимание, что внутренний размер блока в SSD-дисках может быть 64 КБ и больше, и не любое изменение элемента меняет его целиком, объём «паразитной» нагрузки на диск может быть ещё выше.

Формально, amplification factor, то есть коэффициент умножения, вычисляется как отношение размера фактически прочитанных (или записанных) данных к реально необходимому (или измененному) размеру. Феномен «паразитных» чтений в литературе и блогах, посвящённых хранению на диске, называется read amplification, а феномен паразитной записи — write amplification. В нашем примере с B-деревом коэффициент составит около 40 как для чтения, так и для записи.

Давайте рассмотрим как это работает. Объём паразитных операций ввода-вывода при обновлении данных является одной из основных проблем, которую решают LSM-деревья.

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

Удаление содержит ключ элемента (хранить значение нет необходимости) и код операции DELETE. Например, элемент для операции вставки, помимо ключа и значения, содержит дополнительный байт с кодом операции — обозначенный на иллюстрации как REPLACE. Таким образом, всё дерево упорядочено сначала по возрастанию ключа, а в пределах одного ключа — по убыванию LSN. Также каждый элемент LSM содержит порядковый номер операции log sequence number (LSN) — значение монотонно возрастающей последовательности, которое уникально идентифицирует каждую операцию.


Устройство одного уровня

Наполнение LSM дерева

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

Объём оперативной памяти ограничен, поэтому для L0 отводится фиксированная область. Часть дерева, расположенную в оперативной памяти, называют L0 (level zero). В начале, когда дерево не содержит элементов, операции записываются в L0. В конфигурации Tarantool, например, размер L0 задаётся опцией vinyl_memory. Представлен L0 может быть любым контейнером, сохраняющим упорядоченность элементов. Напомню, элементы в дереве упорядочены по возрастанию ключа, а затем по убыванию LSN, так что в случае вставки нового значения по данному ключу легко обнаружить и удалить предыдущее. Операции поиска и вставки в L0 — стандартные операции структуры данных, используемой для представления L0, и мы их подробно рассматривать не будем. Например, Tarantool использует для хранения L0 B+*-tree, о которых я рассказывал в своём блоге.

Тогда L0 записывается в файл на диске и освобождается под новые вставки. Рано или поздно количество элементов в дереве превысит размер L0. Эта операция называется дамп (dump).

Представим эти файлы в виде пирамиды, расположив новые файлы вверху, а старые внизу. Все дампы на диске образуют последовательность, упорядоченную по LSN: диапазоны LSN в файлах не пересекаются, а ближе к началу последовательности находятся файлы с более новыми операциями. При этом более свежие файлы могут содержать операции удаления или замены для уже существующих ключей. По мере появления новых файлов, высота пирамиды растёт. Если при слиянии мы встречаем две версии одного и того же ключа, то достаточно оставить только более новую версию, а если после вставки ключа он был удалён, то из результата можно исключить обе операции. Для удаления старых данных необходимо собирать мусор (этот процесс иногда называется merge, что можно перевести как слияние, а иногда compaction, что правильнее перевести как сборка мусора), объединяя нескольких старых файлов в новый.

Представим, что дерево в качестве ключей хранит монотонную последовательность вида 1, 2, 3 …, и операций удаления нет. Ключевым фактором эффективности LSM-дерева является то, в какой момент и для каких файлов делается слияние. Напротив, если дерево содержит много операций удаления, слияние позволит освободить место на диске. В этом случае слияние будет бесполезным — все элементы уже отсортированы, дерево не содержит мусор и можно однозначно определить, в каком файле находится каждый ключ. В этом случае может иметь смысл выполнять слияние после каждого дампа. Но даже если удалений нет, а диапазоны ключей в разных файлах сильно пересекаются, слияние может ускорить поиск, так как сократит число файлов для просмотра. Однако такое слияние будет приводить к перезаписи всех данных на диске, поэтому если чтений мало, то лучше делать слияния реже.

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

Соотношение размеров файлов на уровнях определяет пропорции пирамиды, что позволяет оптимизировать дерево под интенсивные вставки, либо интенсивные чтения. Все соседние файлы примерно одинакового размера составляют уровень (level) дерева на диске.

После первых трёх дампов, на диске появится 3 файла по 100 МБ, эти файлы образуют уровень L1. Предположим что размер L0 равен 100 МБ, а шаг (соотношение) размеров файлов на каждом уровне LSM (переменная vinyl_run_size_ratio) равен 5, тогда как на каждом уровне может быть не более 2 файлов (переменная vinyl_run_count_per_level). Спустя ещё 2 дампа снова запустится слияние, на этот раз файлов по 100, 100 и 300 МБ, в результате файл размером 500 МБ переместится на уровень L2 (соотношение размеров уровней равно 5), а уровень L1 «опустеет». Так как 3 > 2, запустится слияние файлов (compaction), в результате появится новый файл размером 300 МБ, а старые будут удалены. Спустя ещё 10 дампов, в процессе которых мы 2 раза произведём слияние 3 файлов по 100 МБ и 2 раза слияние файлов по 100, 100 и 300 МБ, мы получим ещё два файла на уровне L2 по 500 МБ, и в результате запустится слияние уже на уровне L2, которое создаст первый файл в 2500 МБ. Пройдёт ещё 10 дампов, и мы получим 3 файла по 500 МБ на уровне L2, в результате чего будет создан один файл размером 1500 МБ. Этот файл, в силу своего размера, переедет на уровень L3.

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

Управление формой LSM-дерева

Если число файлов для поиска нужно уменьшить, то соотношение размеров файлов на разных уровнях увеличивается, и, как следствие, уменьшается число уровней. Если, напротив, необходимо снизить издержки, вызываемые compaction, то соотношение размеров уровней уменьшается, пирамида становится более высокой, а compaction хоть и выполняется чаще, но работает в среднем с файлами меньшего размера, за счёт чего суммарно выполняет меньше работы. Вообще, при заданных N — суммарном размере всех элементов дерева, L0 — размере level zero и x — соотношении размеров уровней (level_size_ratio), write amplification в LSM дереве описывается формулой logx(N/L0)×x, или x×ln(N/C0)/ln(x), график которой по x при N/C0 = 40 (соотношение диск: память) выглядит примерно вот так:

Стоимость поиска на каждом уровне не превышает стоимости поиска в B-дереве. Read amplification при этом пропорционален количеству уровней. 5 и run_count_per_level=2, мы получим коэффициент write amplification около 13. Для нашего «канонического» дерева в 100 000 000 элементов, 256 МБ оперативной памяти и стандартных значений параметров vinyl_level_size_ratio=3. Давайте разберёмся, почему read amplification будет таким большим. При этом read amplification может доходить до 150.

Поиск

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

Например, при вставке в дерево для первичного или уникального ключа необходимо убедиться в отсутствии дубликатов. К сожалению, на практике этот худший случай довольно распространён. О них мы поговорим более детально в разделе, посвященном внутреннему устройству Vinyl. Для ускорения поиска «несуществующих» значений в LSM применяется вероятностная структура данных — фильтр Блума.

Поиск по диапазону

Если при поиске по одному ключу алгоритм завершается после первого совпадения, то для поиска всех значений в диапазоне, например всех пользователей с фамилией «Иванов», необходимо просматривать все уровни дерева.


Поиск по диапазону [24,30)

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

Удаление

Зачем вообще хранить удаления? И почему это не приводит к переполнению дерева, например, в сценарии for i=1,10000000 put(i) delete(i) end?

Роль операций удаления при поиске — сигнализировать об отсутствии искомого значения, а при слиянии — очищать дерево от «мусорных» записей с более старым LSN.

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


Удаление, шаг 1: вставка в L0


Удаление, шаг 2: tombstone проходит через промежуточные уровни


Удаление, шаг 3: при major compaction tombstone удаляется из дерева.

Эта оптимизация реализована в Vinyl. Если мы знаем что удаление следует сразу за вставкой уникального значения, а это частый случай при изменении значения во вторичном индексе, то операцию удаления можно отфильтровывать уже при слиянии промежуточных уровней.

Преимущества LSM

Помимо снижения write amplification, подход с периодической выгрузкой (dump) уровня L0 и слиянием (compaction) уровней L1-Lk имеет ряд преимуществ перед подходом к записи, используемым в B-дереве:

  • Dump и compaction пишут относительно большие файлы: типичный размер L0 составляет 50-100 MБ, что в тысячи раз превышает размер блока B-дерева.
  • Большой размер позволяет эффективно сжимать данные перед записью. В Tarantool сжатие автоматическое, что позволяет ещё больше снизить write amplification.
  • Издержки фрагментации отсутствуют, потому что в файле элементы следуют друг за другом без пустот/паддинга.
  • Все операции создают новые файлы, а не меняют старые данные по месту. Это позволяет избавиться от столь ненавистных нам блокировок, при этом несколько операций могут идти параллельно, не конфликтуя друг с другом. Это также упрощает создание резервных копий и перенос данных на реплику.
  • Хранение старых версий данных позволяет эффективно реализовать поддержку транзакций, используя подход multi-version concurrency control.

Недостатки LSM и их устранение

Одним из ключевых преимуществ B-дерева как структуры данных для поиска является предсказуемость: любая операция занимает не более чем logB(N). В классическом LSM скорость как чтения, так и записи могут может отличаться в лучшем и худшем случае в сотни и тысячи раз. Например, добавление всего лишь одного элемента в L0 может привести к его переполнению, что в свою очередь может привести к переполнению L1, L2 и т.д. Процесс чтения может обнаружить исходный элемент в L0, а может задействовать все уровни. Чтение в пределах одного уровня также требуется оптимизировать, чтобы добиться скорости, сравнимой с B-деревом. К счастью, многие недостатки можно скрасить или полностью устранить с помощью вспомогательных алгоритмов и структур данных. Систематизируем эти недостатки и опишем способы борьбы с ними, используемые в Tarantool.

Непредсказуемая скорость записи

Вставка данных в LSM дерево почти всегда задействует исключительно L0. Как избежать простоя, если область оперативной памяти, отведенная под L0, заполнена?

Чтобы избежать простоя во время записи L0 на диск, Tarantool использует упреждающую запись.
Допустим, размер L0 составляет 256 MБ. Освобождение L0 подразумевает две долгих операции: запись на диск и освобождение памяти. Тогда для записи L0 на диск понадобится 26 секунд. Скорость записи на диск составляет 10 МБ/с. На время записи необходимо зарезервировать около 26 MБ доступной оперативной памяти, сократив реальный полезный размер L0 до 230 MБ. Скорость вставки данных составляет 10 000 запросов в секунду, а размер одного ключа — 100 байт.

Это позволяет максимально эффективно использовать L0 и избежать таймаутов на ожидание доступной памяти для операций записи. Все эти расчёты Tarantool делает автоматически, постоянно поддерживая скользящее среднее нагрузки на СУБД и гистограмму скорости работы диска. Сама запись осуществляется в выделенных потоках, число которых (2 по умолчанию) задаётся переменной vinyl_write_threads. При резком всплеске нагрузки ожидание всё же возможно, поэтому также существует таймаут для операции вставки (vinyl_timeout), значение которого по умолчанию составляет 60 секунд. Значение 2 позволяет выполнять dump параллельно с compaction, что также необходимо для предсказуемой работы системы.

Это возможно благодаря append-only природе дерева — после записи файлы в дереве никогда не меняются, а compaction лишь создаёт новый файл. Слияния в Tarantool всегда выполняются независимо от дампов, в отдельном потоке выполнения.

Хотя в ротированный L0 элементы не добавляются, он может участвовать в поиске. К задержкам также может приводить ротация L0 и освобождение памяти, записанной на диск: в процессе записи памятью L0 владеют два потока операционной системы — поток обработки транзакций и поток записи. Само освобождение после завершения дампа происходит мгновенно: для этого в L0 используется специализированный аллокатор, позволяющий освободить всю память за одну операцию. Чтобы избежать блокировок на чтение во время поиска, поток записи не освобождает записанную память, а оставляет эту задачу потоку обработки транзакций.


Dump происходит из так называемого «shadow» L0, не блокируя новые вставки и чтения

Непредсказуемая скорость чтений

Чтение — самая сложная задача для оптимизации в LSM-деревьях. Главным фактором сложности является большое количество уровней: это не только кратно замедляет поиск, но и потенциально кратно увеличивает требования к оперативной памяти при почти любых попытках оптимизации. К счастью, append-only природа LSM-деревьев позволяет решать эти проблемы нестандартными для традиционных структур данных способами.

Компрессия и постраничный индекс

Компрессия данных в B-деревьях либо сложнейшая в реализации задача, либо больше средство маркетинга, чем действительно полезный инструмент. Подробнее о сложностях реализации компрессии можно почитать в посте Алексея Копытова, сравнивающего реализацию в MySQL и PostgreSQL. Компрессия в LSM работает следующим образом:

Размер страницы задаётся опцией конфигурации vinyl_page_size, которую можно менять независимо для каждого индекса. При любом дампе или слиянии мы разбиваем все данные в одном файле на страницы. Благодаря этому страница никогда не содержит пустот. Страница не обязана занимать строго то количество байт, что прописано в vinyl_page_size — она может быть чуть больше или чуть меньше, в зависимости от хранящихся в ней данных. Первый ключ каждой страницы и оффсет страницы в файле добавляются в так называемый page index — отдельный файл, позволяющий быстро найти нужную страницу. Для сжатия используется потоковый алгоритм zstd от Facebook. Все .index-файлы кэшируются в оперативной памяти. После дампа или слияния page index созданного файла также записывается на диск. Так как данные в странице отсортированы, после чтения и декомпрессии нужный ключ можно найти простым бинарным поиском. Это позволяет найти нужную страницу за одно чтение из .run-файла (такое расширение имени файла используется в Vinyl для файлов, полученных в результате дампа или слияния). За чтение и декомпрессию отвечают отдельные потоки, их количество определяется в опции конфигурации vinyl_read_threads.

К примеру, формат данных в .run-файле ничем не отличается от формата .xlog-файла, то есть файла журнала. Tarantool использует единый формат для всех своих файлов. Это упрощает бэкап и восстановление, а также работу внешних инструментов.

Bloom-фильтры

Хотя page index позволяет снизить число страниц, просматриваемых при поиске в одном файле, он не отменяет необходимости искать во всех уровнях дерева. Есть важный частный случай, когда необходимо проверить отсутствие данных, и тогда просмотр всех уровней неизбежен: вставка в уникальный индекс. Если данные уже существуют, то вставка в уникальный индекс должна завершиться с ошибкой. Единственный способ вернуть ошибку до завершения транзакции в LSM-дереве — произвести поиск перед вставкой. Такого рода чтения в СУБД образуют целый класс, называемый «скрытыми» или «паразитными» чтениями.

Вторичные ключи представляют собой обычные LSM-деревья, в которых данные хранятся в другом порядке. Другая операция, приводящая к скрытым чтениям — обновление значения, по которому построен вторичный индекс. Тогда при любом изменении значения, по которому построен вторичный ключ, приходится сначала удалять из вторичного индекса старый ключ, и только потом вставлять новый. Чаще всего, чтобы не хранить все данные во всех индексах, значение, соответствующее данному ключу, целиком сохраняется только в первичном индексе (любой индекс, хранящий и ключ, и значение, называется covering или clustered), а во вторичном индексе сохраняются лишь поля, по которым построен вторичный индекс, и значения полей, участвующих в первичном индексе. Старое значение во время обновления неизвестно — именно его и нужно «под капотом» читать из первичного ключа.

Например:

update t1 set city=’Moscow’ where id=1

Tarantool не исключение. Чтобы снизить количество чтений с диска, особенно для несуществующих значений, практически все LSM-деревья используют вероятностные структуры данных. При записи, для каждого ключа вычисляется несколько хэш-функций, и в каждом массиве выставляется бит, соответствующий значению хэша. Классический Блум-фильтр (Bloom filter) — это набор из нескольких (обычно 3-5) битовых массивов. Интерес представляют биты, которые оказались не проставлены после записи всех ключей. При хэшировании могут возникнуть коллизии, поэтому некоторые биты могут быть проставлены дважды. Если хотя бы в одном из битовых массивов бит не стоит, то значение в файле отсутствует. При поиске также вычисляются выбранные хэш-функции. Вероятность срабатывания Блум-фильтра определяется теоремой Байеса — каждая хэш-функция представляет собой независимую случайную величину, благодаря чему вероятность того, что во всех битовых массивах одновременно произойдёт коллизия, очень мала.

Единственный параметр конфигурации, который можно менять независимо для каждого индекса, называется bloom_fpr (fpr — сокращение от false positive ratio), который по умолчанию равен 0,05, или 5%. Ключевым преимуществом реализации Блум-фильтров в Tarantool является простота настройки. Сами Блум-фильтры хранятся вместе с page index в .index-файле и кэшируются в оперативной памяти. На основе этого параметра Tarantool автоматически строит Блум-фильтры оптимального размера для поиска как по частичному, так и полному ключу.

Кэширование

Многие привыкли считать кэширование панацеей от всех проблем с производительностью. В любой непонятной ситуации добавляй кэш. В Vinyl мы смотрим на кэш скорее как на средство снижения общей нагрузки на диск, и, как следствие, получения более предсказуемого времени ответов на запросы, которые не попали в кэш. В Vinyl реализован уникальный для транзакционных систем вид кэша: range tuple cache. В отличие от RocksDB, например, или MySQL, этот кэш хранит не страницы, а уже готовые диапазоны значений индекса, после их чтения с диска и слияния всех уровней. Это позволяет использовать кэш для запросов как по одному ключу, так и по диапазону ключей. Поскольку в кэше хранятся только горячие данные, а не, к примеру, страницы (в странице может быть востребована лишь часть данных), оперативная память используется наиболее оптимально. Размер кэша задаётся переменной конфигурации vinyl_cache.

Управление сборкой мусора

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

Vinyl создаёт и обслуживает несколько LSM-деревьев даже для одной таблицы (space) — по одному дереву на каждый индекс. В Vinyl устройство одного LSM-дерева — это лишь фрагмент пазла. Давайте попробуем разобраться, зачем. Но даже один единственный индекс может состоять из десятков LSM-деревьев.

Через некоторое время на самом нижнем уровне LSM у нас может оказаться файл размером 10 ГБ. Рассмотрим наш стандартный пример: 100 000 000 записей по 100 байт каждая. Данные на промежуточных уровнях тоже занимают место — по одному и тому же ключу дерево может хранить несколько операций. Во время слияния последнего уровня мы создадим временный файл, который также будет занимать около 10 ГБ. А если данных не 1 ГБ, а 1 ТБ? Суммарно для хранения 10 ГБ полезных данных нам может потребоваться до 30 ГБ свободного места: 10 ГБ на последний уровень, 10 ГБ на временный файл и 10 ГБ на всё остальное. При любой аварии или рестарте системы операцию придётся начинать заново. Требовать, чтобы количество свободного места на диске всегда в несколько раз превышало объём полезных данных, экономически нецелесообразно, да и создание файла в 1ТБ может занимать десятки часов.

Представим, что первичный ключ дерева — монотонная последовательность, например, временной ряд. Рассмотрим другую проблему. Нет смысла заново производить слияние лишь для того, чтобы дописать в хвост и без того огромного файла ещё несколько миллионов записей.
А если вставки происходят, в основном, в одну часть диапазона ключей, а чтения — из другой части? В этом случае основные вставки будут приходиться на правую часть диапазона ключей. Если оно будет слишком высоким, пострадают чтения, слишком низким — запись. Как в этом случае оптимизировать форму дерева?

Примерный размер каждого поддерева задаётся переменной vinyl_range_size и по умолчанию равен 1 ГБ, а само поддерево называется range. Tarantool «факторизует» проблему, создавая не одно, а множество LSM-деревьев для каждого индекса.


Факторизация больших LSM деревьев с помощью ранжирования

По мере наполнения, суммарный объём может превысить vinyl_range_size. Изначально, пока в индексе мало элементов, он состоит из одного range. Разделение происходит по срединному элементу диапазона ключей, хранящихся в дереве. В этом случае выполняется операция split — деление дерева на две равные части. Таким образом, при вставке или чтении мы однозначно знаем, к какому поддереву обращаться. Например, если изначально дерево хранит полный диапазон -inf… +inf, то после сплита по срединному ключу X мы получим два поддерева: одно будет хранить все ключи от -inf до X, другое — от X до +inf. Она объединяет два соседних дерева в одно. Если в дереве были удаления и каждый из соседних диапазонов «похудел», выполняется обратная операция — coalesce.

LSM-дерево — это всего лишь набор файлов. Split и coalesce не приводят к слиянию, созданию новых файлов и прочим тяжеловесным операциям. Журнал имеет разрешение .vylog, по формату совместим с .xlog-файлом, и, как и .xlog-файл, автоматически ротируется при каждом чекпоинте. В Vinyl мы реализовали специальный журнал метаданных, позволяющий легко отслеживать, какой файл принадлежит какому поддереву или поддеревьям. Это ссылка на файл, с указанием диапазона значений ключа, которая хранится исключительно в журнале метаданных. Чтобы избежать пересоздания файлов при split или coalesce, мы ввели промежуточную сущность — slice. А когда необходимо произвести split или coalesce, Tarantool создаёт slice-объекты для каждого нового дерева, старые slice объекты удаляет, и записывает эти операции в журнал метаданных. Когда число ссылок на файл становится равным нулю, файл удаляется. Буквально, журнал метаданных хранит записи вида <id дерева, id слайса> или <id слайса, id файла, min, max>.

Таким образом, непосредственно тяжёлая работа по разбиению дерева на два поддерева, откладывается до compaction и выполняется автоматически.

В результате эти процессы являются управляемыми и предсказуемыми. Огромным преимуществом подхода с разделением всего диапазона ключей на поддиапазоны (ranges) является возможность независимо управлять размером L0, а также процессом dump и compaction для каждого поддерева. Наличие отдельного журнала метаданных также упрощает реализацию таких операций, как truncate и drop — в Vinyl они обрабатываются мгновенно, потому что работают исключительно с журналом метаданных, а удаление мусора выполняется в фоне.

Расширенные возможности Vinyl

Upsert

Ранее я писал лишь о двух операциях, которые хранит LSM-дерево: delete и replace. Давайте рассмотрим, как представлены все остальные. Insert можно представить с помощью replace, нужно лишь предварительно убедиться в отсутствии элемента с таким же ключом. Для выполнения update нам также приходится предварительно считывать старое значение из дерева, так что и эту операцию проще записать в дерево как replace — это ускорит будущие чтения по этому ключу. Кроме того, update должен вернуть новое значение, так что скрытых чтений никак не избежать.

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

На этапе выполнения транзакции Tarantool лишь сохраняет всю операцию в LSM-дереве, а «выполняет» её уже только во время слияния. Такая операция должна содержать как значение по умолчанию, которое нужно вставить, если данных по ключу ещё нет, так и список операций обновления, которые нужно выполнить, если значение существует.


Операция upsert

Поэтому Tarantool стремится максимально валидировать операции upsert перед записью в дерево, но некоторые проверки можно выполнить, лишь имея старые данные на руках. К сожалению, если откладывать выполнение операции на этап слияния, хороших опций для обработки ошибок не остаётся. Например, если update прибавляет число к строке или удаляет несуществующее поле.

Но во всех из них она представляет собой лишь синтаксический сахар, объединяющий update и replace, не избавляя СУБД от необходимости выполнять скрытые чтения. Операция с похожей семантикой присутствует во многих продуктах, в том числе в PostgreSQL и MongoDB. Я предполагаю, что причиной этого является относительная новизна LSM-деревьев в качестве структур данных для хранения.

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

Vinyl только начинал «взрослеть», и мы впервые запустили upsert в production. Хотел бы рассказать связанную с этим оператором историю. Операции обновления либо вставляют ключ, либо обновляют текущее время. Казалось бы, идеальные условия для upsert: огромный набор ключей, текущее время в качестве значения. Нагрузочные тесты показали отличные результаты. Операции чтения редкие.

Тем не менее, после пары дней работы процесс Tarantool начал потреблять 100 % CPU, а производительность системы упала практически до нуля.

Оказалось, что распределение запросов по ключам существенно отличалось от того, что мы видели в тестовом окружении. Начали копать. Буквально, большая часть ключей обновлялась 1-2 раза за сутки, и база для них явно «курила». Оно было… ну очень неравномерное. Tarantool прекрасно справлялся с этим потоком обновлений. Но были ключи гораздо более горячие — десятки тысяч обновлений в сутки. Чтобы вернуть «последнее» значение, Tarantool приходилось каждый раз прочитать и «проиграть» историю из десятков тысяч команд upsert. А вот когда по ключу с десятком тысяч upsert’ов происходило чтение, можно было тушить свет. Проектируя upsert, мы надеялись, что это произойдёт автоматически, во время слияния уровней, но до слияния дело даже не доходило, памяти L0 было предостаточно, и LSM-дерево не спешило выталкивать его на диск.

Решили мы проблему добавлением фонового процесса, осуществляющего «упреждающие» чтения для ключей, по которым накопилось больше нескольких десятков upsert’ов, с последующей заменой всего стэка upsert’ов на прочитанное значение.

Вторичные ключи

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

Если вторичные индексы не уникальны, то удаление «мусора» из них также можно перенести в фазу слияния, что мы и делаем в Tarantool.

Транзакции

Append-only природа LSM-дерева позволила нам реализовать в Vinyl полноценные сериализуемые транзакции. Read-only запросы при этом используют старые версии данных и не блокируют запись. Сам менеджер транзакций пока довольно простой: в традиционной классификации он реализует класс MVTO, при этом в конфликте побеждает та транзакция, что завершилась первой. Блокировок и свойственных им дедлоков нет. Как ни странно, это скорее недостаток, чем преимущество: при параллельном выполнении можно повысить количество успешных транзакций, «придержав» некоторые из них в нужный момент на блокировке. Развитие менеджера транзакций в наших ближайших планах. В текущем релизе мы сфокусировались на том, чтобы сделать алгоритм корректным и предсказуемым на 100%. Например, наш менеджер транзакций — один из немногих в NoSQL среде, поддерживающих так называемые gap locks.

Заключение

В этой статье я постарался рассказать, как устроен наш дисковый движок. За время работы над ним проект Tarantool серьёзно повзрослел, сегодня он используется не только в Mail.Ru Group и других интернет-компаниях, также мы продаём и поддерживаем Enterprise-версию сервера в банках, телекоммуникационных компаниях, в компаниях промышленного сектора. Сегодня стабильная версия Tarantool с Vinyl прошла испытание боем как в Mail.Ru Group, так и вне её, и доступна для скачивания на нашем сайте.

в офисе Mail. 21 июня 2018 г. На ней я более подробно расскажу о тюнинге и мониторинге Vinyl. Ru Group пройдёт конференция T+ — это наша первая конференция, посвящённая in-memory вычислениям, на которую я бы хотел всех пригласить. Мы уверены, что конференция соберёт множество разработчиков, потому что Tarantool сегодня — одно из немногих российских open source решений, которое можно уверенно использовать для создания решений промышленного уровня. Конференция платная, хотя у нас нет цели заработать деньги на продаже билетов. Поэтому и при проведении конференции мы также решили делать всё максимально профессионально.

И мы постоянно ищем единомышленников, чтобы вместе создать СУБД мирового уровня. Проект Tarantool активно растёт. У нас очень много работы. Если Вы живо интересуетесь темами, затронутыми в этой статье, и наша цель вам кажется важной и интересной — обязательно напишите нам.

Теги
Показать больше

Похожие статьи

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *

Кнопка «Наверх»
Закрыть