Как написать свой индекс в Tarantool
Tarantool — это сервер приложений и база данных. Серверная часть написана на C, а пользователю предоставлен Lua-интерфейс для работы с ним. Кроме того, Tarantool — это opensource-продукт, а значит, исходный код лежит в открытом доступе, и можно свободно разрабатывать и распространять ПО на основе Tarantool.
Но сегодня рассказ будет немного о другом: об эксперименте, о попытке написать свою структуру данных для поиска (Z-order curve) и встроить её в существующую экосистему Tarantool.
Я разработчик в Tarantool Solution Team, не занимаюсь непосредственной разработкой Tarantool, а отношусь к активным пользователям. Поэтому, для меня этот эксперимент — попытка разобраться, как Tarantool работает на низком уровне.
Что такое Tarantool и где он хранит данные?
Что такое Tarantool? В мире баз данных он позиционируется как in-memory технология. Движок memtx позволяет хранить все ваши данные в оперативной памяти, и удовлетворяет при этом всем принципам ACID.
Аналогом реляционных таблиц в Tarantool являются спейсы (space), которые предназначены для хранения кортежей (tuples). В отличие от реляционных таблиц, кортежи в спейсе в общем случае могут быть произвольной длины. Для их хранения должна быть создана структура данных поиска, при этом ключ поиска — первичный ключ, всегда уникальный.
Можно построить и дополнительные структуры — вторичные индексы, хранящие лишь указатель на кортеж. Вторичный индекс может быть не уникальным, однако это лишь внешнее поведение, видимое пользователю. К любому не уникальному индексу неявно добавляются поля первичного индекса. Так обеспечивается стабильность сортировки кортежей внутри индекса.
Tarantool поддерживает разные типы индексов:
- В-первую очередь, в B-Tree (а если совсем точно, то B+*-Tree). О структуре B-деревьев написано очень много [B-Tree]. Отмечу лишь, что данные хранятся в отсортированном виде, к тому же можно искать по префиксу проиндексированного ключа.
- Индекс на основе hash-таблицы. Подходит, если вам не нужны выборки интервалов. Доступ по полному ключу. В отличие от B-дерева, время доступа к элементу не логарифмическое, а постоянное. Этот индекс всегда уникальный.
- R-Tree. Этот тип индекса уже более специализированный. Предназначен для хранения «многомерных» данных, например, географических координат. Поддерживает индексацию полей только одного типа — массив. Это массив наших условных координат, которые являются обычными числами с плавающей запятой. При этом в плане запросов он достаточно функционален. Позволяет искать точки, лежащие внутри и вне заданной границы, а также ближайших соседей.
- Bitset. Пожалуй, самый таинственный для меня индекс. Ознакомьтесь с ним, если вдруг вам потребуется хранить битовые массивы в спейсах и выполнять запросы, используя битовые маски.
Кривая Z-порядка, или кривая Мортона
Откуда возникла идея написать свой индекс, причем довольно экзотический?
Однажды я наткнулся на статьи Amazon [1, 2], в которых рассказывалось о такой структуре, как кривая Z-порядка, или кривая Мортона. Это рецепт расположения «многомерных» данных внутри плоской структуры (Z-order curve), которая затем укладывается в B-дерево. Такой подход должен помочь избежать сплошного сканирования данных. В целом многомерными данными можно считать информацию о любом объекте, обладающем некоторым набором характеристик. Например, рост, вес, размер ноги и т.д. человека. В большинстве баз данных для подобных целей используется R-Tree.
Немного о том, как устроена кривая Z-порядка.
Кривая Z-порядка, она же кривая Мортона, получается путем перемежения битов координат точки в пространстве. Полученные таким образом Z-адреса обладают свойством локальности. Точки, находившиеся рядом в многомерном пространстве, будут по-прежнему располагаться рядом и при отображении на плоскую линию.
Схематически подобное перемешивание выглядит так:
Как это работает? Мы ограничиваем некоторую область в пространстве — гиперкуб (в двумерном пространстве будет прямоугольник) — с помощью двух точек, лежащих на диагонали, которые отображаются в две точки на прямой. И получаем неприятный побочный эффект: часть точек выходит за границу ограничивающего прямоугольника:
То есть мы не можем просто итерироваться по этой кривой. Но, вооружившись специальным алгоритмом, мы можем при выходе за границу делать прыжок, возвращаясь обратно в область поиска. Как только мы выходим за крайнюю точку кривой (назовем её upper_bound), поиск закончен.
При работе с B-Tree мы имели бы набор интервалов, и этот запрос привел бы к последовательному сканированию B-дерева, что заняло бы очень много времени при большом наборе данных.
Мой интерес подогревали и другие публикации об этой кривой. Например, о том, как она была интегрирована в TransBase [3], проприетарную БД. И, к сожалению своему, я не нашел никаких open source-реализаций этой структуры.
Лежащее в основе этой кривой B-Tree обладает рядом преимуществ перед R-Tree. Например, лучшей заполняемостью и компактностью. Недостатки: большинство используемых алгоритмов ограничено по процессору. Для сравнения я решил воспользоваться Tarantool: интересовали скорости чтения/вставки, а также потребление памяти. Нельзя не упомянуть, что похожая тема уже поднималась на Хабре, но для небольших размерностей (2–3) и применительно к дисковой БД PostgreSQL [ZcurvePostgres].
Что потребовалось для встраивания в Tarantool?
Я находил простенькие реализации этой структуры для размерности 2–3, но мне хотелось сравнить производительность с существующим R-Tree-индексом, поэтому ограничиваться малыми размерностями мне не хотелось. Я выбрал такую же размерность, как и у R-Tree — 20. Для этого мне был нужен битовый массив с поддержкой некоторых примитивных операций: извлечения/изменения бита, сдвига, логических операций OR/AND.
Для прототипа я взял найденную open source-реализацию, но довольно быстро пришел к тому, что мне не нужен битовый массив общего назначения: длина ключа всегда кратна 64, поэтому часть операций существенно упрощается. Я написал собственную реализацию на базе того, что у меня было. Кроме того, вместо использования системных функций выделения памяти я начал использовать специальные аллокаторы, реализованные в Tarantool [4].
Пожалуй, сердце индекса — это набор алгоритмов для работы с Z-кривой. А именно, вычисление Z-адреса (с помощью специальных lookup-таблиц), проверка принадлежности Z-адреса к области поиска и обнаружение первого вхождения в область поиска, начиная с указанной точки. Если хорошо поискать в сети, то можно найти научные публикации с описанием этих алгоритмов, поэтому всё, что мне оставалось, это их реализовать, отладить и, по возможности, оптимизировать. Хранить Z-адреса предполагалось внутри уже реализованного B-дерева, использующегося для TREE-индекса.
Как организована работа с данными?
В самом общем случае нам приходит tuple. Это массив данных в формате message pack. И в идеальном случае мы должны были бы просто вычленить проиндексированные поля, перемешать их биты и вставить адрес с указателем на кортеж внутрь B-дерева.
Однако всё было бы так просто, если бы мы работали только с типом unsigned, когда отсортированные битовые представления чисел соответствовали бы отсортированным числам в натуральном представлении. У знаковых целых чисел свои правила представления, у чисел с плавающей запятой — свои. И это пришлось приводить к общему знаменателю. За счет того, что мы храним Z-адрес отдельно от самих данных, мы можем выполнять любые преобразования над нашими ключами, главное — сохранять порядок сортировки. Это можно делать с помощью несложных битовых манипуляций. Например, для целых знаковых чисел можно просто инвертировать старший байт. Для других типов тоже есть подобные, пусть и чуть более сложные, преобразования.
Все числовые типы умещаются в 8 байтов, поэтому результирующий ключ будет размера N * 8 байтов, где N — размерность нашего пространства. Что делать со строками?
Довольно частая ситуация при работе со строками — префиксный поиск. И его вполне можно поддержать. Первые 8 байтов строки вполне могут быть использованы в качестве ключа. Если строка короче, то её можно дополнить нулями. Поддержка строк накладывает фундаментальное ограничение на наш индекс: мы теряем уникальность. Даже если строки различаются в девятом байте, то с точки зрения системы они всё равно будут одинаковыми.
Посмотрим на код.
API индекса состоит из определенного набора методов. Рассматривать каждый в отдельности мы не будем, пройдемся лишь по самым основным, а именно — по операциям поиска и вставки.
get — поиск элемента по полному ключу. Работает лишь для уникальных индексов. Наш индекс не может быть уникальным, поэтому функция заменяется специальной generic-версией, возвращающей ошибку «Unsupported index feature».
replace — вставка элемента. Рассмотрим подробнее.
static int
memtx_zcurve_index_replace(struct index *base, struct tuple *old_tuple,
struct tuple *new_tuple, enum dup_replace_mode mode,
struct tuple **result)
{
(void)mode;
struct memtx_zcurve_index *index = (struct memtx_zcurve_index *)base;
if (new_tuple) {
struct memtx_zcurve_data new_data;
new_data.tuple = new_tuple;
new_data.z_address = extract_zaddress(new_tuple,
&index->bit_array_pool, index);
struct memtx_zcurve_data dup_data;
dup_data.tuple = NULL;
dup_data.z_address = NULL;
int tree_res = memtx_zcurve_insert(&index->tree, new_data,
&dup_data);
if (tree_res) {
diag_set(OutOfMemory, MEMTX_EXTENT_SIZE,
"memtx_zcurve_index", "replace");
return -1;
}
if (dup_data.tuple != NULL) {
*result = dup_data.tuple;
z_value_free(&index->bit_array_pool, dup_data.z_address);
return 0;
}
}
if (old_tuple) {
struct memtx_zcurve_data old_data, deleted_value;
old_data.tuple = old_tuple;
old_data.z_address = extract_zaddress(old_tuple,
&index->bit_array_pool, index);
memtx_zcurve_delete_value(&index->tree, old_data, &deleted_value);
z_value_free(&index->bit_array_pool, old_data.z_address);
z_value_free(&index->bit_array_pool, deleted_value.z_address);
}
*result = old_tuple;
return 0;
}
На что стоит обратить внимание?
С точки зрения индекса не существует операций update, delete, insert и replace. Вся их логика выполняется в этом методе, получающем старый и новый кортежи, а также mode — информацию о том, является индекс уникальным или нет. Наш индекс не может быть уникальным, поэтому никаких дополнительных проверок не требуется и можно сразу вставлять кортеж.
memtx_zcurve_insert и memtx_zcurve_delete_value — методы B-дерева, которое уже было реализовано в Tarantool и используется в обычном TREE-индексе. На них мы не будем отдельно останавливаться. В отличие от обычного TREE мы храним не просто tuple, а ещё и z-адрес — перемешанные биты проиндексированных частей. За это отвечает функция extract_zadress.
create_iterator — из Lua мы обращаемся к этому методу в случае select«а и pairs«а.
static struct iterator *
memtx_zcurve_index_create_iterator(struct index *base, enum iterator_type type,
const char *key, uint32_t part_count)
{
struct memtx_zcurve_index *index = (struct memtx_zcurve_index *)base;
struct memtx_engine *memtx = (struct memtx_engine *)base->engine;
assert(part_count == 0 || key != NULL);
if (type != ITER_EQ && type != ITER_ALL && type != ITER_GE) {
diag_set(UnsupportedIndexFeature, base->def,
"requested iterator type");
return NULL;
}
uint8_t index_dim = base->def->key_def->part_count;
if (part_count == 0) {
/*
* If no key is specified, downgrade equality
* iterators to a full range.
*/
type = ITER_GE;
key = NULL;
} else if (index_dim * 2 == part_count
&& type != ITER_ALL) {
/*
* If part_count is twice greater than key_def.part_count
* set iterator to range query
*/
type = ITER_GE;
}
struct tree_iterator *it = mempool_alloc(&memtx->zcurve_iterator_pool);
if (it == NULL) {
diag_set(OutOfMemory, sizeof(struct tree_iterator),
"memtx_zcurve_index", "iterator");
return NULL;
}
iterator_create(&it->base, base);
it->pool = &memtx->zcurve_iterator_pool;
it->base.next = tree_iterator_start;
it->base.free = tree_iterator_free;
it->type = type;
if (part_count == 0 || type == ITER_ALL) {
it->lower_bound = zeros(&index->bit_array_pool, index_dim);
it->upper_bound = ones(&index->bit_array_pool, index_dim);
} else if (type == ITER_EQ) {
it->lower_bound = mp_decode_key(&index->bit_array_pool,
key, index_dim, index);
it->upper_bound = NULL;
} else if (base->def->key_def->part_count == part_count) {
it->lower_bound = mp_decode_key(&index->bit_array_pool,
key, index_dim, index);
it->upper_bound = ones(&index->bit_array_pool, index_dim);
} else if (base->def->key_def->part_count * 2 == part_count) {
it->lower_bound = z_value_create(&index->bit_array_pool, index_dim);
it->upper_bound = z_value_create(&index->bit_array_pool, index_dim);
mp_decode_part(key, part_count, index, it->lower_bound, it->upper_bound);
} else {
unreachable();
}
it->tree_iterator = memtx_zcurve_invalid_iterator();
it->current.tuple = NULL;
it->current.z_address = NULL;
return (struct iterator *)it;
}
В зависимости от переданного ключа мы вычисляем нижнюю и верхнюю границу запроса. Однако пока что этот итератор ни на что не указывает. Всего существует несколько типов итераторов. В нашем случае это ALL — получение всех элементов; EQ — получение элементов, z-адрес которых совпадает с переданным; и GE — выборка элементов в гиперкубе.
destroy — удаление индекса. В случае со вторичным индексом просто освобождает ту память, которая выделялась под структуру поиска. А если индекс первичный, то физически удаляет хранящиеся кортежи.
Весь код доступен по адресу: https://github.com/olegrok/tarantool/tree/z-order-curve-index
Давайте посмотрим, что получилось, и подведем итоги.
space = box.schema.space.create('myspace', { engine = 'memtx' })
pk = space:create_index('primary', { type = 'tree', parts = {{1, 'unsigned'}}, unique = true})
sk = space:create_index('secondary', { type = 'zcurve', parts = {{2, 'unsigned'}, {3, 'unsigned'}}})
for i=0,5 do for j=0,5 do space:insert{i * 6 + j, i, j} end end
-- returns all tuples
pk:select{}
-- (2 <= x <= 3) and (3 <= y <= 5)
sk:select{2, 3, 3, 5}
---
- — [15, 2, 3]
- [21, 3, 3]
- [16, 2, 4]
- [22, 3, 4]
- [17, 2, 5]
- [23, 3, 5]
…
-- (x == 2) and (y == 3)
sk:select{2, 3}
---
- — [15, 2, 3]
-- (2 <= x <= 3)
sk:select({2, 3, box.NULL, box.NULL})
---
- — [12, 2, 0]
- [18, 3, 0]
- [13, 2, 1]
- [19, 3, 1]
- [14, 2, 2]
- [20, 3, 2]
- [15, 2, 3]
- [21, 3, 3]
- [16, 2, 4]
- [22, 3, 4]
- [17, 2, 5]
- [23, 3, 5]
...
-- (x >= 2) and (y >= 3)
sk:select({2, box.NULL, 3, box.NULL})
---
- — [15, 2, 3]
- [21, 3, 3]
- [27, 4, 3]
- [33, 5, 3]
- [16, 2, 4]
- [22, 3, 4]
- [17, 2, 5]
- [23, 3, 5]
- [28, 4, 4]
- [34, 5, 4]
- [29, 4, 5]
- [35, 5, 5]
...А что с производительностью?
Оказалось, что всё не так радужно, как я описывал.
Начиная с какого-то момента кривая Z-порядка начинает существенно проседать по скорости доступа к данным. perf top показывал, что основное время тратится на проверку принадлежности точки к области поиска и вычисление очередной точки, к которой необходимо прыгнуть. Обе операции имеют линейную сложность в зависимости от длины ключа — с увеличением размерности увеличивается и длина.
Из приятного — потребление памяти в 2–3 раза меньше и вставка чуть быстрее, чем у R-Tree. Что не особо релевантно, ведь измерения производились с выключенным WAL. Во-первых, в production-среде в случае сбоя отключенный WAL может привести к потере данных. Во-вторых, несмотря на то, что запись в WAL использует батчевый подход, это всё равно запись на диск, которая в тысячи раз медленнее, чем работа с оперативной памятью.
Также интересно сравнить с B-деревом. Тут, как и предполагалось, кривая будет быстрее, чем полное сканирование и проверка каждой точки на принадлежность к заданной области. Даже не смотря на то, что проверка является более легковесной, чем в случае кривой Z-порядка, где всё сводится к побитовому сравнению.
Цифры на графике отличаются по порядку от R-Tree — тест был слегка изменен.
Для теста я генерировал набор точек и сравнивал длительность при запросе с использованием Z-кривой и при обычном сканировании.
Подведем итоги
В мире in-memory эта структура показала себя не лучшим образом, однако у неё все равно есть достоинства:
- Занимает меньше места.
- Типизирована, в отличие от R-Tree (актуально только для Tarantool).
- К ней стоит присмотреться, если есть только B-Tree и нужно делать многомерные запросы (не актуально для Tarantool).
Это был интересный эксперимент. Вряд ли предложенное мной решение когда-нибудь станет частью Tarantool. Тем не менее, не стоит бояться экспериментировать. И если у вас есть какие-то предложения и решения, то не бойтесь делиться ими.
Источники
[B-Tree]:
Индексы в PostgreSQL — 4 / Блог компании Postgres Professional / Хабр
B-tree / Хабр
Структура данных B-дерево / Блог компании OTUS. Онлайн-образование / Хабр
[ZcurvePostgres]:
Про Z-оrder и R-дерево / Хабр
Z-order vs R-tree, продолжение / Хабр
[1] Z-Order Indexing for Multifaceted Queries in Amazon DynamoDB: Part 1 | AWS Database Blog
[2] Z-order indexing for multifaceted queries in Amazon DynamoDB: Part 2 | AWS Database Blog
[3] Integrating the UB-Tree into a Database System Kernel
[4] https://github.com/tarantool/small
