Хабрахабр

Bitmap-индексы в Go: поиск на дикой скорости

Вступительное слово

Я выступил с этим докладом на английском языке на конференции GopherCon Russia 2019 в Москве и на русском — на митапе в Нижнем Новгороде. Речь в нём идёт о bitmap-индексе — менее распространённом, чем B-tree, но не менее интересном. Делюсь записью выступления на конференции на английском и текстовой расшифровкой на русском.

А «на десерт» мы воспользуемся готовыми библиотеками, чтобы создать свою супербыструю специализированную базу данных. Мы рассмотрим, как устроен bitmap-индекс, когда он лучше, когда — хуже других индексов и в каких случаях он значительно быстрее них; увидим, в каких популярных СУБД уже есть bitmap-индексы; попробуем написать свой на Go.

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

Введение

http://bit.ly/bitmapindexes
https://github.com/mkevac/gopherconrussia2019

Сейчас шесть вечера, мы все суперуставшие. Привет всем! Не волнуйтесь, у меня будет пара строчек исходного кода тут и там. Замечательное время, чтобы поговорить о скучной теории индексов баз данных, да? 🙂

Поэтому давайте начинать.

Сегодня я буду говорить о следующем: Если без шуток, то доклад переполнен информацией, а у нас не так много времени.

  • что такое индексы;
  • что такое bitmap-индекс;
  • где он используется и где он НЕ используется и почему;
  • простая имплементация на Go и немного борьбы с компилятором;
  • чуть менее простая, но гораздо более производительная имплементацию на Go-ассемблере;
  • «проблемы» bitmap-индексов;
  • существующие реализации.

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

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

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

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

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

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

Это мы делаем с помощью Bloom-фильтров или cuckoo-фильтров. Третий подход — избавиться от необходимости поиска. Первые дают ответ мгновенно, избавляя вас от необходимости осуществлять поиск.

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

Это значит, что иногда мы можем использовать несколько подходов одновременно: если нам нужно ещё сильнее ускорить поиск или если необходимо покрыть все возможные типы поиска. Как я уже сказал, тема индексов БД обширна и переполнена компромиссами.

Сегодня я расскажу о наименее известном подходе из названных — о bitmap-индексах.

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

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

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


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

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

Рассмотрим простейший пример bitmap-индекса.

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

  • рядом с метро (near metro);
  • есть частная парковка (has private parking);
  • есть веранда (has terrace);
  • можно забронировать столик (accepts reservations);
  • подходит для вегетарианцев (vegan friendly);
  • дорогой (expensive).


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

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

  • «Покажи мне рестораны, подходящие для вегетарианцев»;
  • «Покажи мне недорогие рестораны с верандой, где можно забронировать столик».

Давайте посмотрим.

Как? Всё, что нам нужно, — это взять битмап «подходит для вегетарианцев» и превратить его в список ресторанов, чьи биты выставлены.


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


Тут очень много теории, но не волнуйтесь, мы увидим код очень скоро.

Где используются bitmap-индексы?


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

Пройдёмся по списку основных подозреваемых.

MySQL ещё не поддерживает bitmap-индексы, но есть Proposal с предложением добавить эту опцию (https://dev.mysql.com/worklog/task/?id=1524).

PostgreSQL не поддерживает bitmap-индексы, но использует простые битмапы и битовые операции для объединения результатов поиска по нескольким другим индексам.

У Tarantool есть bitset-индексы, он поддерживает простой поиск по ним.

У Redis есть простые битовые поля (https://redis.io/commands/bitfield) без возможности поиска по ним.

MongoDB ещё не поддерживает bitmap-индексы, но также есть Proposal с предложением добавить эту опцию https://jira.mongodb.org/browse/SERVER-1723

Elasticsearch использует битмапы внутри (https://www.elastic.co/blog/frame-of-reference-and-roaring-bitmaps).

  • Но в нашем доме появился новый сосед: Pilosa. Это новая нереляционная база данных, написанная на Go. Она содержит только bitmap-индексы и базирует всё на них. Мы поговорим о ней чуть позже.

Имплементация на Go

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

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

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

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

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


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

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

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

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

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

Попрофилировав немного с pprof, я заметил, что компилятор Go пропустил одну очень простую, но очень важную оптимизацию: function inlining.

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

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


В итоге нам удаётся сэкономить около 2 микросекунд. И, как видите, теперь компилятор с радостью инлайнит нашу функцию! Неплохо!

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

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

Видя это, компилятор с радостью пропускает проверку, а мы в итоге экономим ещё 500 наносекунд. Давайте же успокоим компилятор, показав ему, что у всех слайсов одинаковый размер.

Большие батчи

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

Но, к сожалению, мы «кормим» наш процессор очень маленькими кусками работы. Всё, что мы делаем, — это базовые битовые операции, и наши процессоры очень эффективно их выполняют. Мы можем очень просто подтюнить наш код, чтобы он работал с 8-байтовыми кусками, используя слайсы UInt64. Наши функции выполняют операции побайтово.

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

Имплементация на ассемблере


Но это ещё не конец. Наши процессоры могут работать с кусками по 16, 32 и даже 64 байта. Такие «широкие» операции называются single instruction multiple data (SIMD; одна инструкция, много данных), а процесс преобразования кода таким образом, чтобы он использовал такие операции, называется векторизация.

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

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

В дополнение к этому Go использует необычный формат Plan 9, отличающийся от общепризнанных форматов AT&T и Intel.

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

Обе утилиты генерируют Go-ассемблер из более высокоуровневого кода, написанного на Python и Go соответственно.

Эти утилиты упрощают такие вещи, как register allocation (выбор процессорного регистра), написание циклов, и в целом упрощают процесс входа в мир ассемблерного программирования в Go. Но, к счастью, уже есть две высокоуровневые тулзы, которые помогают нам в написании Go ассемблера: PeachPy и avo.

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

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

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

  • add.s с результирующим кодом на Go-ассемблере;
  • stub.go с заголовками функций для связи двух миров: Go и ассемблера.


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

Всё это avo делает за нас.

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

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

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

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

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

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

Нам надо либо писать большие функции, либо использовать новый пакет math/bits, либо обходить ассемблер стороной. Именно поэтому невозможно получить какие-либо преимущества от мелких функций на ассемблере.

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

Для данного примера я решил применить AVX2, поэтому мы будем использовать операции, работающие с 32-байтными кусками. В случае с 32-байтными кусками это регистры с префиксом Y. п.

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

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

Ну а что насчёт производительности? Второе новшество связано с тем, что я решил использовать оптимизацию, которая называется разворачивание цикла (loop unrolling), то есть сделать восемь операций цикла вручную, прежде чем прыгнуть в начало цикла. Мы получили ускорение примерно в семь раз по сравнению с лучшим решением на Go. Она прекрасна! Но это уж точно тема для отдельного доклада. Впечатляет, да?

Но даже эту имплементацию потенциально можно было бы ускорить, воспользовавшись AVX-512, префетчингом или JIT (just-in-time compiler) для планировщика запросов.

Проблемы bitmap-индексов

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

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

Проблема большой кардинальности

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


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

В последнее время стали появляться и гибридные подходы, как, например, roaring битмапы. Они используют одновременно три разных представления для битмапов — собственно битмапы, массивы и так называемые bit runs — и балансируют между ними, чтобы максимизировать производительность и минимизировать потребление памяти.

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

Ещё один подход, который может нам помочь справиться с большой кардинальностью, называется группировка (binning). Вы можете встретить roaring битмапы в самых популярных приложениях. Рост — это число с плавающей запятой, но мы, люди, не думаем о нём в таком ключе. Представьте, что у вас есть поле, представляющее рост человека. Для нас нет разницы между ростом 185,2 см и 185,3 см.

Получается, мы можем сгруппировать похожие значения в группы в пределах 1 см.

А если мы ещё и знаем, что очень мало людей имеют рост меньше 50 см и больше 250 см, то мы можем, по сути, превратить поле с бесконечной кардинальностью в поле с кардинальностью примерно в 200 значений.

Конечно, при необходимости мы можем сделать дополнительную фильтрацию уже после.

Проблема большой пропускной способности

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

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

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

Вы можете шардировать bitmap-индекс так, как вы шардировали бы любые другие данные. Шардинг — штука простая и общеизвестная. Вместо одного большого лока вы получите кучу мелких локов и таким образом избавитесь от lock contention.

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

Эти два подхода можно использовать одновременно: у вас может быть шардированный версионированный индекс.

Более сложные запросы

Последняя проблема bitmap-индексов заключается в том, что, как нам говорят, они плохо подходят для более сложных типов запросов, например запросов «по промежутку».

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

Наивным и очень неразумным решением было бы взять результаты для каждого долларового значения и объединить их битовой операцией OR.

Чуть более правильным решением было бы использовать группировку. Это ускорило бы наш процесс в 50 раз.

В научных работах оно называется range-encoded bitmaps.

В таком представлении мы не просто выставляем один бит для какого-либо значения (например, 200), а выставляем это значение и всё, что выше. Но проблема также легко решается использованием представления, созданного специально для такого типа запросов. То же самое для 300: 300 и выше. 200 и выше. И так далее.

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

Вы удивитесь, но даже геозапросы возможны с использованием bitmap-индексов. Фигуру должно быть возможно представить в виде трёх или более пересекающихся прямых, которые можно пронумеровать. Например, S2 от Google. Таким образом мы сможем превратить наш геозапрос в несколько запросов «по промежутку» (по этим пронумерованным линиям).

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

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

Особенно более продвинутые, с использованием SIMD, например. Однако не у всех есть время, терпение и ресурсы, чтобы создать bitmap-индексы с нуля.

К счастью, есть несколько готовых решений, которые вам помогут.

Roaring битмапы

Во-первых, есть та самая roaring bitmaps-библиотека, о которой я уже говорил. Она содержит все необходимые контейнеры и битовые операции, которые вам понадобятся для того, чтобы сделать полноценный bitmap-индекс.

К сожалению, на данный момент ни одна из Go-реализаций не использует SIMD, а значит, Go-реализации менее производительны, чем реализации на C, например.

Pilosa

Другой продукт, который может вам помочь, — СУБД Pilosa, у которой, по сути, только bitmap-индексы и есть. Это относительно новое решение, но оно завоёвывает сердца с огромной скоростью.

Pilosa использует roaring битмапы внутри себя и даёт вам возможность использовать их, упрощает и объясняет все те вещи, о которых я говорил выше: группировка, range-encoded bitmaps, понятие поля и т. п.

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

Пример очень похож на то, что вы видели раньше.

И наконец, получаем финальный результат.

Я очень надеюсь, что в обозримом будущем в СУБД вроде MySQL и PostgreSQL тоже появится этот новый тип индексов — bitmap-индексы.

После этого мы используем NOT на поле «expensive», затем пересекаем результат (или AND-им) с полем «terrace» и с полем «reservations».

Заключение


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

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

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

Спасибо! Это всё, что я хотел рассказать.

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

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

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

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

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