Растровые индексы в Go: невероятная скорость поиска

Предисловие

Меня зовут Марко, и в этом году на Gophercon Russia я выступал с докладом об очень интересном виде индексов, называемых растровые индексы. Я хотел поделиться им с сообществом не только в формате видео, но и в виде статьи. Пожалуйста, наслаждайтесь!

Дополнительные материалы, слайды и весь исходный код можно найти здесь:
https://bit.ly/bitmapindexes
https://github.com/mkevac/ gopherconrussia2019

Исходная видеозапись:

Давай начнем!

Вступление

Сегодня я собираюсь поговорить о

• Что такое индексы.
• Что такое растровый индекс.
• Где это используется. Почему не используется там, где не используется.
• Мы увидим простую реализацию в Go, а затем попробуем компилятор.
• Затем мы рассмотрим чуть менее простую, но заметно более быструю реализацию на сборке Go.
• И после этого я собираюсь один за другим заняться «проблемами» растровых индексов.
• И, наконец, посмотрим, какие есть существующие решения.

Так что же такое индексы?

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

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

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

Обычно это достигается с помощью деревьев. Это похоже на то, что в вашем гардеробе есть коробки с коробками. Каждая коробка содержит материалы, которые затем рассортированы по более мелким коробкам, каждая из которых предназначена для конкретного использования. Если нам нужны материалы, лучше поискать коробку с надписью «материал», а не коробку с надписью «печенье».

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

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

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

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

Сегодня я хотел бы поговорить об одном из этих малоизвестных подходов: индексах растровых изображений.

Но кто я такой, чтобы говорить на эту тему?

Я руководитель группы в Badoo (возможно, вы знаете еще один из наших брендов: Bumble). У нас более 400 миллионов пользователей по всему миру, и многие функции, которые мы предлагаем, включают поиск наиболее подходящего для вас! Для этих задач мы используем специализированные сервисы, которые, в частности, используют растровые индексы.

Теперь, что такое растровый индекс?

Как следует из названия, индексы Bitmap используют точечные рисунки, также известные как битовые наборы, для реализации индекса поиска. С высоты птичьего полета этот индекс состоит из одного или нескольких растровых изображений, которые представляют объекты (например, людей) и их параметры (например, возраст или цвет глаз), а также алгоритм ответа на поисковые запросы с использованием побитовых операций, таких как AND, OR, NOT и т. Д. .

Растровые индексы считаются очень полезными и высокопроизводительными, если у вас есть поиск, который должен объединять запросы по нескольким столбцам с низкой мощностью (возможно, по цвету глаз или семейному положению) по сравнению с расстоянием до центра города, которое имеет бесконечную мощность.

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

Давайте посмотрим на простейший пример растрового индекса …

Представьте, что у нас есть список московских ресторанов с бинарными характеристиками:

• возле метро
• есть частная парковка
• есть терраса
• принимает оговорки
• веганский
• дорогие

Дадим каждому ресторану индекс, начиная с 0, и выделим 6 растровых изображений (по одному для каждой характеристики). Затем мы заполняли эти растровые изображения в зависимости от того, есть ли у ресторана конкретная характеристика или нет. Если ресторан номер 4 имеет террасу, то бит номер 4 в битовой карте «терраса» будет установлен в 1 (0 в противном случае).

Теперь у нас есть простейший возможный растровый индекс, который мы можем использовать для ответа на такие вопросы, как:

• Дайте мне рестораны, подходящие для веганов
• Дайте мне рестораны с террасой, которые принимают бронирование, но не дорогие

Как? Давайте посмотрим. Первый вопрос простой. Мы просто берем растровое изображение, подходящее для веганов, и возвращаем все индексы с установленным битом.

Второй вопрос немного сложнее. Мы будем использовать побитовую операцию НЕ с «дорогим» растровым изображением, чтобы получить недорогие рестораны, И его с растровым изображением «принять резервирование» и с «растровым изображением террасы». Полученное растровое изображение будет состоять из ресторанов, обладающих всеми этими характеристиками, которые мы хотели. Здесь мы видим, что все эти характеристики есть только у Юности.

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

Где используются растровые индексы

Если вы введете в Google «растровый индекс», 90% результатов будут указывать на Oracle DB, которая имеет базовые растровые индексы. Но ведь и в других СУБД растровые индексы тоже используются, не так ли? Вообще-то нет. Давайте по очереди рассмотрим обычных подозреваемых.

• В MySQL пока нет растровых индексов, но есть предложение по их добавлению (https://dev.mysql.com/worklog/task/?id=1524)
• PostgreSQL не имеет индексов растровых изображений, но они используют простые растровые изображения и побитовые операции для объединения результатов нескольких различных индексов.
• Tarantool имеет битовые индексы и позволяет выполнять очень простой поиск по ним.
• Redis имеет битовые поля «https://redis.io/commands/bitfield фактически без возможности поиска.
• В MongoDB их еще нет, но есть предложение добавить их (https://jira.mongodb.org/browse/SERVER-1723)
• Elasticsearch внутренне использует растровые изображения https://www.elastic.co/blog/frame-of-reference-and-roaring-bitmaps.

• Но есть новый мальчик: Пилоса. Pilosa — это новая СУБД, написанная на Go (обратите внимание, что R не существует, это не реляционная система), в основе которой всего лежат растровые индексы. А о Пилосе мы поговорим позже.

Реализация на Go

Но почему? Почему так редко используются растровые индексы? Прежде чем ответить на этот вопрос, я хотел бы провести вас через базовую реализацию растрового индекса в Go.

Растровое изображение представлено как кусок памяти. В Go для этого воспользуемся кусочком байтов.

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

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

Другая функция выдаст нам список ресторанов из растрового изображения.

Чтобы ответить на вопрос «дайте мне рестораны с террасой, которые принимают бронирование, но не дорогие», нам потребуются две операции: NOT и AND.

Мы можем немного упростить код, введя сложную операцию AND NOT.

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

И теперь мы можем использовать наши растровые изображения и наши функции, чтобы получить ответ.

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

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

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

Но я их не боюсь и могу обмануть компилятор, используя goto для своего цикла.

Как видите, встраивание сэкономило нам около 2 микросекунд. Неплохо!

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

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

С этой проверкой компилятор go с радостью пропустит проверки диапазона, и мы сэкономим несколько наносекунд.

Реализация в сборке

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

Видите ли, мы делаем очень простые побитовые операции, и наши процессоры очень эффективны с ними.

К сожалению, мы загружаем наш ЦП очень маленькими порциями работы. Наша функция выполняет операции побайтно. Мы можем легко настроить нашу реализацию для работы с 8-байтовыми фрагментами, используя фрагменты uint64.

Как вы можете видеть здесь, мы получили примерно 8-кратную производительность для 8-кратного размера пакета, поэтому прирост производительности в значительной степени линейный.

Но это еще не конец пути. Наши процессоры могут работать с фрагментами размером 16, 32 и даже 64 байта. Эти операции называются SIMD (Single Instruction Multiple Data), а процесс использования таких операций CPU называется векторизацией.

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

Го сборка — странный зверь. Вы могли подумать, что сборка связана с архитектурой, для которой вы пишете, но сборка Go больше похожа на IRL (язык промежуточного представления): она не зависит от платформы. Роб Пайк сделал потрясающий доклад по этому поводу несколько лет назад.

Кроме того, Go использует необычный формат plan9, который не похож ни на форматы AT&T;, ни на Intel.

Можно с уверенностью сказать, что писать ассемблерный код Go — неинтересно.

К счастью для нас, уже есть два высокоуровневых инструмента для написания сборки Go: PeachPy и escape. Оба они генерируют сборку go из кода более высокого уровня, написанного на Python и Go соответственно.

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

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

Это простейший пример программы избегания. У нас есть функция main (), которая определяет функцию с именем Add (), которая складывает два числа. Существуют вспомогательные функции для получения параметров по имени и для получения одного из доступных общих регистров. Здесь есть функции для каждой операции сборки, такие как ADDQ, и есть вспомогательные функции для сохранения результата из регистра в результирующее значение.

Вызов go generate запустит эту программу, и будут созданы два файла.

• add.s со сгенерированным кодом сборки
• stub.go с заголовками функций, которые необходимы для подключения нашего кода go и сборки.

Теперь, когда мы увидели, что делает escape, давайте посмотрим на наши функции. Я реализовал как скалярную, так и SIMD (векторную) версии наших функций.

Давайте сначала посмотрим, как выглядит скалярная версия.

Как и в предыдущем примере, мы можем запросить общий реестр, а AOO не предоставит нам тот, который доступен. Нам не нужно отслеживать смещения в байтах для наших аргументов, избегайте этого за нас.

Ранее мы перешли с циклов на использование goto из соображений производительности и для обмана компилятора go. Здесь мы используем goto (переходы) и метки с самого начала, потому что циклы — это конструкции более высокого уровня. В сборке у нас только прыжки.

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

Это результирующий asm-код, который мы получаем. Нам не нужно было рассчитывать смещения и размеры (выделены зеленым цветом), нам не приходилось иметь дело с конкретными регистрами (выделены красным).

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

К сожалению, мы не можем заставить компилятор Go встроить наши функции, написанные на asm. В нем полностью отсутствует поддержка, и запрос на эту функцию существует уже некоторое время. Вот почему небольшие asm-функции в go не приносят никакой пользы. Вам нужно либо написать более крупные функции, либо использовать новый пакет math / bits, либо вообще пропустить asm.

Теперь напишем векторную версию наших функций.

Я решил использовать AVX2, поэтому мы будем использовать 32-байтовые блоки. По структуре он очень похож на скаляр. Загружаем параметры, запрашиваем общие регистры и т. Д.

Одно из изменений связано с тем, что векторные операции используют определенные широкие регистры. Для 32 байтов у них есть префикс Y, поэтому вы видите там YMM (). Для 64-байтовых у них был бы префикс Z.

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

Что касается производительности … она потрясающая. Мы получили улучшение примерно в 7 раз по сравнению с предыдущим лучшим результатом. Впечатляет, правда?

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

Проблемы с растровым индексом

Теперь, когда мы увидели базовую реализацию и впечатляющую скорость реализации asm, давайте поговорим о том, что растровые индексы не очень широко используются. Это почему?

Эти три причины дают нам более старые публикации. Но я бы сказал, что недавние проблемы уже «исправлены» или уже решены. Я не буду вдаваться в подробности по этому поводу, потому что у нас мало времени, но, безусловно, стоит взглянуть на него.

Проблема высокой мощности

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

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

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

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

Другой подход, который может помочь с полями с высокой мощностью, называется бинингом. Представьте, что у нас есть поле, представляющее рост человека. Высота — это поплавок, но мы так не думаем. Никому нет дела до того, рост у вас 185,2 или 185,3 см. Таким образом, мы можем использовать «виртуальные бункеры», чтобы втиснуть одинаковые высоты в один и тот же бункер: в данном случае бункер размером 1 см. И если вы предположите, что очень мало людей с ростом менее 50 см или более 250 см, мы можем преобразовать нашу высоту в поле с мощностью элемента примерно 200, вместо почти бесконечной мощности. При необходимости мы могли бы сделать дополнительную фильтрацию результатов позже.

Проблема с высокой пропускной способностью

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

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

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

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

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

Но этот подход возможен только в том случае, если ваше приложение может поддерживать устаревшие индексы поиска, которые немного устарели.

Конечно, эти два подхода можно использовать вместе. У вас могут быть сегментированные версионные индексы.

Нетривиальные запросы

Другая проблема с растровым индексом связана с использованием растровых индексов с запросами диапазона. И на первый взгляд побитовые операции, такие как AND и OR, не кажутся очень полезными для запросов диапазона, таких как «дайте мне номера в отеле по цене от 200 до 300 долларов за ночь».

Наивным и очень неэффективным решением было бы получить результаты для каждой ценовой категории от 200 до 300 и ИЛИ результаты.

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

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

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

Таким образом, с помощью этого диапазона представления растрового изображения на запрос диапазона можно ответить только двумя проходами через растровое изображение. Мы получаем все отели, стоимость которых меньше или равна 300 долларам, и удаляем из результата все отели, стоимость которых меньше или равна 199 долларам. Выполнено.

Вы были бы удивлены, но даже гео-запросы возможны с использованием растровых изображений. Хитрость заключается в том, чтобы использовать представление вроде Google S2 или аналогичного, которое включает координату в геометрическую фигуру, которая может быть представлена ​​в виде трех или более индексированных линий. Если вы используете такое представление, вы можете представить географический запрос в виде нескольких запросов диапазона по этим линейным индексам.

Готовые решения

Что ж, надеюсь, я немного заинтересовал вас. Теперь у вас есть еще один инструмент, и если вам когда-нибудь понадобится внедрить что-то подобное в свой сервис, вы будете знать, где искать.

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

Не бойтесь, есть два продукта с открытым исходным кодом, которые могут помочь вам в ваших усилиях.

Ревущие растровые изображения

Во-первых, есть библиотека, о которой я уже упоминал, под названием «ревущие растровые изображения». Эта библиотека реализует ревущий «контейнер» и все побитовые операции, которые вам понадобятся, если бы вы реализовали полный растровый индекс.

К сожалению, реализации go не используют SIMD, поэтому они дают несколько меньшую производительность, чем, скажем, реализация C.

Пилоса

Другой продукт — СУБД Pilosa, имеющая только растровые индексы. Это недавний проект, но в последнее время он набирает обороты.

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

Давайте кратко рассмотрим пример использования Pilosa …

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

Здесь вы видите тот же базовый образец. НЕ дорого пересекается или пересекается с террасой и пересекается с оговорками.

Результат ожидаемый.

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

Заключительные слова

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

Растровые индексы — это полезная вещь, которую нужно знать и понимать, даже если они вам сейчас не нужны. Сохраните их как еще один инструмент в своем портфолио.

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

И это все, что у меня есть для вас на данный момент. Большое спасибо!