Badoo corporate blog
Programming
Go
Data storage
Comments 40
+6
Рад, что нашел эту статью на хабре. Недавно был на митапе, где выступал Марко с этим докладом, довольно понятно разложено для тех, кто вообще не знаком с Bitmap-индексами.
Спасибо.
+3

jfyi: на слайде What is a Bitmap Index? случайный набор нулей и единичек :)

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


Разве не Тарас Бульба?
+2
Ох. Кажется я слишком хотел, чтобы это оказалось заведение с вкуснейшими наливками, Юность!
+3
Спасибо за статью!

Я работал с roaring bitmaps в Си, поразительная штука, и, как мне кажется, недостаточно утилизированная в БД.

Но вы меня сильно удивили насчет варианта на Go. Один из авторов оригинальной либы в ее Си исполнении, некий Даниэль Лемирэ, — мирового уровня специалист по векторизации алгоритмов. Собственно, производительность библиотеки (на Си) определяется во многом именно использованием SIMD.

Неужели вариант на Го настолько слабей..? Вы как-нибудь сравнивали производительность? Я не смотрел код, но удивлюсь, если roaring на Go вообще обходится без SIMD.
+1
Обожаю статьи Даниэля и вообще все то, что он делает в области оптимизаций. Специалист мирового уровня и правда!

Напрямую си и go версии я не сравнивал. В репозитории что к докладу есть сравнение cgo и go варианта, но это не совсем то.

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

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

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

А если шире. Почему в roaring bitmaps на Го могли опустить SIMD? Я не слишком хорошо знаком с языком, чисто шапочно. Там есть что-то аналогичное SIMD intrisics в Си? Или надо на ассемблере делать?

+2
Как раз потому, что компилятор Go пока не умеет сам векторизовать, а писать на ассемблере Go — штука не очень удобная и подверженная ньюансам.
Часть из этого я как раз описал в докладке и статье.
Все-таки Go довольно молодой язык. Но все будет, я уверен.

За ассемблер сейчас чаще всего берутся, когда пишут шифрование.
Появление avo/peachpy чуть приоткроет этот мир для более широкого круга лиц.
+1
Ну… Речь даже не об ассемблере идет, а о встроенных функциях, которые позволяют не писать непосредственно на асме, но все же использовать конкретные инструкции при необходимости в рамках Си.

Тот же streamvbyte, или RoaringC, не используют ассемблер, это ж совсем болезненно, да и портируется тяжело, а пишут функциями, специфичными для каждой из платформ. А выбирают функции ifdef-ами.

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

Спасибо за ответы!
0

ifdef или какой-нибудь аналог типа флагов времени компиляции?


Обычно делают скалярный вариант на случай CPU без SIMD вообще, и потом векторные — для актуальных процессоров. Или даже несколько: для ARM NEON, разных поколений Intel и т.д.


Удовольствия в этом мало, конечно. :-) Но когда оно надо, то оно надобно очень.

+1

Представляю ситуацию. Заходит пользователь скачать minio, для файл помойки на core2quad, а там сборка под amd64, amd64-avx и т.д.

+3

У вас это практические вопросы или риторические?


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


Если не подходят ifdef-ы, можно на лету выбирать необходимые функции: можно динамически линковать разные версии функций в зависимости от железа или даже атрибутами указывать под поколения процессоров версии одной и той же функции (https://lwn.net/Articles/691932/). В конце концов, можно вот прям кодом спросить есть ли у процессора соответствеующий набор инструкций.

0
Там не было вопроса и это нормальный кейс. И тут не gcc.
+1

Если уж хочется оптимизировать, то почему не использовать для сравнения gccgo, который куда охотнее оптимизирует пользовательский код?

0

Реально серьезная оптимизация алгоритмов компиляторами не делается, а делается людьми :-)

0

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

+1
gccgo это такая штука, о которой вроде бы все слышали, но которая почти никому не нужна и не интересна. Личный pet project Ian Lance Taylor, который жив только благодаря ему.
99% работы и активности приходится на основной компилятор.
0

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

0

А есть какие-то сравнительные тесты, которые показывают, как использование bitmap-индексов позволяет ускорить работу приложения по сравнению с "обычными" индексами?

0

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


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


На простом Си пока ничего лучше roaring bitmap не придумали, и есть очень читаемая публикация в свободном доступе на эту тему. Там есть сравнения.

0
Всё таки bitmap-индексы это не «классически» индексы, и тот факт, что обе структуры называются индексами может вводить в заблуждение. Я использую битмапы для выбора баннера в системе управления рекламой. В этой задаче практически невозможно использовать индексы, потому как надо проверять десятки ограничений для каждого из баннеров.

Битмапы, думаю, имеет смысл использовать там, где много условий, много данных и требуется полный перебор. В таких задачах они могут давать колосальный выигрыш…
UFO landed and left these words here
0

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


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


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


Но вы зря про редкость объединений. Они в типичных запросах к бд встречаются постоянно.

UFO landed and left these words here
0

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


SIMD это хорошо, но в случае с БД любой дополнительный IO настолько больше ресурсов требует, > что любые выигрыши будут малозаметны.

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


Но есть два "но"! :-) Во-первых, современные битмапы сильно ужаты, и умещаются в единицы кэш-линий. Для винта, тем более — SSD, это чтение одной страницы памяти; в то время как B-деревья трогают по крайней мере пару страницу.


Во-вторых, последнее поколение БД (https://en.wikipedia.org/wiki/NewSQL) использует винт исключительно для хранения лога (WAL), а данные хранятся почти полностью в памяти, и вот тут уже действуют совсем другие правила, и всякие там ускорения вычислений (векторизация запросов, jit-компиляция запросов, различные кеш-ориентированные индексы, безлоковые структуры данных) играют важную роль.


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

Ну да, разумеется. Развитые структуры данных — дело такое, перед применением надо основательно разобраться с преимуществами или недостатками.


B-дерево — прекрасная и почти универсальная структура данных, я спорить тут не могу, но есть множество альтернатив, которые в отдельных слуаях будут себя показывать лучше. Например, MemSQL вообще решили обойтись скип-листом для своих индексов, т.к. решили, что корректно сделать безлоковое B-дерево им не по карману.


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

0

Не сказан главный недостаток таких индексов: сложность поиска по ним O(n) (линейно зависит от размера просматриваемой таблицы), тогда как деревья дают O(log n), а хэши чуть ли не O(1).
Если в таблице с миллиардами записей только 10 удовлетворяют условию, то нам придётся просмотреть весь индекс, в то время, как поиск по дереву пробежит только очень небольшую часть индекса.
Для разреженных данных проблема может быть решена сжатием, о котором писалось в статье, но тут возникают сложности с модификацией данных.

0

Эм.


Современные варианты битмапов ни в коем случае не будут держать все необходимые для сравнения миллиарды бит.

0
А есть ли возможно вписать в эту систему сортировку? Есть нет, то какая возможность сортировки полученных данных есть? Просто воспользовался CRoaring через Redis и был впечатлен соотношением потребляемых ресурсов и скорости. Но получение отфильтрованных это первый шаг, дальше нужно выполнить их сортировку и хочется это сделать как можно быстрее. Пока запилил решение влоб. битмапами получили ID документов и потом тупо сходили в базу за данными через IN навесив туда сортировку. Франкенштейнт получается.
0

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


А что именно вы хотите сортировать? сами айдишники?

0

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


Опять же, сам Редис страшно не любит алгоритмы сложностью от O(n) и выше, т.к. работает в один поток, и такие алгоритмы просто заблокируют на ощутимое время весь процесс. А сортировка, как известно, это O(N*logN).


Так что тут вам традиционная БД в помощь.

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

Собственно, я так их и пользую.


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

Only those users with full accounts are able to leave comments. , please.