Вступне слово
Я виступив з цією доповіддю англійською мовою на конференції GopherCon Russia 2019 у Москві та російською – на мітапі в Нижньому Новгороді. Йдеться про bitmap-індекс — менш поширений, ніж B-tree, але не менш цікавий. Ділюсь виступи на конференції англійською та текстовою розшифровкою російською.
Ми розглянемо, як влаштований bitmap-індекс, коли він кращий, коли — гірший за інші індекси і в яких випадках він значно швидше за них; побачимо, у яких популярних СУБД вже є bitmap-індекси; спробуємо написати свій на Go. А на десерт ми скористаємося готовими бібліотеками, щоб створити свою супершвидку спеціалізовану базу даних.
Дуже сподіваюся, що моя праця виявиться для вас корисною та цікавою. Поїхали!
Запровадження
Привіт всім! Зараз шість вечора ми всі супервтомлені. Чудовий час, щоб поговорити про нудну теорію індексів баз даних, так? Не хвилюйтеся, у мене буде кілька рядків вихідного коду тут і там. 🙂
Якщо без жартів, то доповідь переповнена інформацією, а ми не так багато часу. Тож давайте починати.
Сьогодні я говоритиму про наступне:
- що таке індекси;
- що таке bitmap-індекс;
- де він використовується та де він НЕ використовується і чому;
- проста імплементація на Go та трохи боротьби з компілятором;
- трохи менш проста, але набагато продуктивніша імплементацію на Go-ассемблері;
- "проблеми" bitmap-індексів;
- існуючі реалізації.
То що таке індекси?
Індекс – це окрема структура даних, яку ми тримаємо та оновлюємо на додаток до основних даних. Він використовується для прискорення пошуку. Без індексів пошук вимагав повного проходу за даними (процес, званий full scan), і цей процес має лінійну алгоритмічну складність. Але бази даних зазвичай містять величезну кількість даних і лінійну складність — це занадто повільно. В ідеалі нам би отримати логарифмічну чи константну.
Це величезна складна тема, переповнена тонкощами і компромісами, але, подивившись на десятки років розробки та дослідження різних баз даних, я готовий стверджувати, що існує лише кілька підходів до створення індексів БД, які широко використовуються.
Перший підхід полягає в ієрархічному зменшенні області пошуку, поділ області пошуку на більш дрібні частини.
Зазвичай ми робимо це, використовуючи різні дерева. Прикладом може бути велика коробка з матеріалами у вашій шафі, в якій знаходяться дрібніші коробки з матеріалами, розділеними на різні тематики. Якщо вам потрібні матеріали, то ви напевно шукатимете їх у коробці з написом «Матеріали», а не в тій, на якій написано «Печеньки», чи не так?
Другий підхід у тому, щоб відразу виділити потрібний елемент чи групу елементів. Ми робимо це у hash maps або у зворотних індексах. Використання hash maps дуже схоже на попередній приклад, тільки замість коробки з коробками у вас у шафі купа маленьких коробок із фінальними предметами.
Третій підхід - позбутися необхідності пошуку. Це ми робимо за допомогою Bloom-фільтрів чи cuckoo-фільтрів. Перші дають відповідь миттєво, позбавляючи вас необхідності здійснювати пошук.
Останній підхід полягає у повноцінному використанні всіх потужностей, які дає нам сучасне залізо. Саме це ми робимо у bitmap-індексах. Так, при їх використанні нам іноді потрібно пройти по всьому індексу, але робимо це суперефективно.
Як я вже сказав, тема індексів БД велика і переповнена компромісами. Це означає, що іноді ми можемо використовувати кілька підходів одночасно: якщо нам потрібно ще більше прискорити пошук або якщо необхідно покрити всі можливі типи пошуку.
Сьогодні я розповім про найменш відомий підхід із названих — про bitmap-індекси.
Хто я такий, щоб говорити на цю тему?
Я працюю тимлід в Badoo (можливо, ви краще знаєте інший наш продукт - Bumble). У нас вже понад 400 млн користувачів по всьому світу і багато фіч, які займаються тим, що підбирають для них найкращу пару. Робимо ми це за допомогою кастомних сервісів, що використовують у тому числі 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 з пропозицією додати цю опцію ().
PostgreSQL не підтримує bitmap-індекси, але використовує прості бітмапи та бітові операції для об'єднання результатів пошуку за декількома іншими індексами.
Tarantool має bitset-індекси, він підтримує простий пошук по них.
Redis має прості бітові поля.) без можливості пошуку за ними.
MongoDB ще не підтримує bitmap-індекси, але також є Proposal з пропозицією додати цю опцію
Elasticsearch використовує бітмапи всередині).
- Але у нашому будинку з'явився новий сусід: Pilosa. Це нова нереляційна база даних, написана Go. Вона містить лише bitmap-індекси та базує все на них. Ми поговоримо про неї трохи згодом.
Імплементація на Go
Але чому bitmap-індекси так рідко використовуються? Перш ніж відповісти на це питання, я хотів би продемонструвати вам імплементацію дуже простого bitmap-індексу на Go.
Бітмапи, насправді, представлені просто шматками даних. У Go давайте для цього скористаємося слайсами байтів.
У нас є один бітмап на одну ресторанну характеристику, і кожен біт у бітмапі говорить про те, чи є у конкретного ресторану ця властивість чи ні.
Нам знадобляться дві допоміжні функції. Одна використовуватиметься для заповнення наших бітмапів рандомними даними. Рандомними, але з певною ймовірністю того, що ресторан має кожну властивість. Наприклад, я вважаю, що в Москві дуже мало ресторанів, де не можна забронювати столик, і мені здається, що приблизно 20% закладів підходять для вегетаріанців.
Друга функція перетворюватиме бітмап на список ресторанів.
Щоб відповісти на запит «Покажи мені недорогі ресторани, які мають веранда і в яких можна забронювати столик», нам знадобляться дві бітові операції: NOT і AND.
Ми можемо трохи спростити наш код, скориставшись складнішою операцією AND NOT.
Ми маємо функції для кожної з цих операцій. Обидві вони йдуть слайсами, беруть відповідні елементи з кожного, об'єднують їх бітовою операцією і кладуть результат в результуючий слайс.
І ось тепер ми можемо скористатися нашими бітмапами та функціями для відповіді на пошуковий запит.
Продуктивність не така висока, навіть незважаючи на те, що функції дуже прості і ми пристойно заощадили на тому, що не повертали новий результуючий слайс при кожному виклик функції.
Попрофілювавши трохи з pprof, я помітив, що компілятор Go пропустив одну дуже просту, але дуже важливу оптимізацію: function inlining.
Справа в тому, що компілятор Go дуже боїться циклів, які йдуть по слайсах, і категорично відмовляється інлайнувати функції, які містять такі цикли.
Але я не боюся і можу обдурити компілятор, скориставшись goto замість циклу, як у старі добрі часи.
І, як бачите, тепер компілятор із радістю інлайнує нашу функцію! У результаті нам вдається заощадити близько двох мікросекунд. Не погано!
Друге вузьке місце нескладно побачити, якщо уважно подивитися на асемблерний висновок. Компілятор додав перевірку на межі слайсу прямо всередину нашого гарячого циклу. Справа в тому, що Go – безпечна мова, компілятор побоюється, що три мої аргументи (три слайси) мають різний розмір. Адже тоді буде теоретична можливість появи так званого переповнення буфера (buffer overflow).
Давайте заспокоїмо компілятор, показавши йому, що у всіх слайсів однаковий розмір. Ми можемо зробити це, додавши просту перевірку на початку нашої функції.
Бачачи це, компілятор з радістю пропускає перевірку, а ми зрештою заощаджуємо ще 500 наносекунд.
Великі батчі
Окей, нам вдалося вичавити якусь продуктивність з нашої простої імплементації, але цей результат насправді набагато гірший, ніж можливо з поточним залізом.
Все, що ми робимо, це базові бітові операції, і наші процесори дуже ефективно їх виконують. Але, на жаль, ми "годуємо" наш процесор дуже маленькими шматками роботи. Наші функції виконують операції побайтово. Ми можемо дуже просто підтюнити наш код, щоб він працював з 8-байтовими шматками, використовуючи слайси UInt64.
Як бачите, ця маленька зміна прискорила нашу програму у вісім разів за рахунок збільшення батча у вісім разів. Виграш, можна сказати, лінійний.
Імплементація на асемблері
Але це не кінець. Наші процесори можуть працювати зі шматками по 16, 32 і навіть 64 байти. Такі «широкі» операції називаються single instruction multiple data (SIMD; одна інструкція, багато даних), а процес перетворення коду таким чином, щоб він використовував такі операції, називається векторизація.
На жаль, компілятор Go – далеко не відмінник у векторизації. На даний момент єдиний спосіб векторизації коду на Go - це взяти та покласти дані операції вручну з використанням асемблера Go.
Асемблер Go - дивний звір. Ви, напевно, знаєте, що асемблер - це щось, що сильно прив'язане до архітектури комп'ютера, для якого ви пишете, але в Go це не так. Асемблер Go більше схожий на IRL (intermediate representation language) або проміжну мову: він практично платформонезалежний. Роб Пайк виступив із чудовим на цю тему кілька років тому GopherCon в Денвері.
На додаток до цього Go використовує незвичайний формат Plan 9, який відрізняється від загальновизнаних форматів AT&T та Intel.
Можна з упевненістю сказати, що писати асемблер Go вручну - це не найвеселіше заняття.
Але, на щастя, вже є дві високорівневі тулзи, які допомагають нам у написанні Go асемблера: PeachPy та avo. Обидві утиліти генерують Go-асемблер з більш високорівневого коду, написаного на Python і Go відповідно.
Ці утиліти спрощують такі речі, як register allocation (вибір процесорного регістру), написання циклів, і загалом спрощують процес входу у світ асемблерного програмування Go.
Ми будемо використовувати avo, тому наші програми будуть майже звичайними програмами на Go.
Ось так виглядає найпростіший приклад avo-програми. У нас є функція main(), яка визначає в собі функцію Add(), сенс якої полягає у додаванні двох чисел. Тут присутні допоміжні функції для отримання параметрів на ім'я та отримання одного з вільних і відповідних процесорних регістрів. Кожна процесорна операція має відповідну функцію на 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. Саме тому ви бачите функцію YMM() у коді. Якби я використав AVX-512 з 64-бітними шматками, то префікс був би Z.
Друга новація пов'язана з тим, що я вирішив використовувати оптимізацію, яка називається розгортання циклу (loop unrolling), тобто зробити вісім операцій циклу вручну, перш ніж стрибнути на початок циклу. Ця оптимізація зменшує кількість бранчів (розгалужень) у коді, і вона обмежена кількістю вільних регістрів, наявних.
Ну а що щодо продуктивності? Вона прекрасна! Ми отримали прискорення приблизно сім разів порівняно з кращим рішенням на Go. Вражає, так?
Але навіть цю імплементацію можна було б прискорити, скориставшись AVX-512, префетчингом або JIT (just-in-time compiler) для планувальника запитів. Але це точно тема для окремої доповіді.
Проблеми bitmap-індексів
Зараз, коли ми вже розглянули просту реалізацію bitmap-індексу на Go і набагато продуктивнішу на асемблері, давайте, нарешті, поговоримо про те, чому ж bitmap-індекси так рідко використовуються.
У старих наукових працях згадуються три проблеми bitmap-індексів, але нові наукові роботи і я стверджуємо, що вони вже неактуальні. Не глибоко занурюватимемося в кожну з цих проблем, але поверхово їх розглянемо.
Проблема великої кардинальності
Отже, нам кажуть, що bitmap-індекси підходять тільки для полів з малою кардинальністю, тобто таких, у яких мало значень (наприклад, підлога або колір очей), і причина в тому, що звичайне уявлення таких полів (один біт на значення) у разі великої кардинальності буде займати дуже багато місця і, більше того, ці bitmap-індекси будуть слабко (рідко) заповнені.
Іноді ми можемо використовувати інше уявлення, наприклад, стандартне, яке ми використовуємо для представлення чисел. Але саме поява алгоритмів стиснення змінила все. За останні десятиліття вчені та дослідники вигадали велику кількість алгоритмів стиснення для бітмапів. Основна їхня перевага в тому, що не потрібно розтискати бітмапи для проведення бітових операцій - ми можемо здійснювати бітові операції над стислими бітмапами.
Останнім часом почали з'являтися і гібридні підходи, як, наприклад, широкі бітмапи. Вони використовують одночасно три різні уявлення для бітмапів – власне бітмапи, масиви та так звані bit runs – і балансують між ними, щоб максимізувати продуктивність та мінімізувати споживання пам'яті.
Ви можете зустріти roaring біт-мапи в найпопулярніших додатках. Вже існує величезна кількість імплементацій для різних мов програмування, у тому числі більше трьох імплементацій для Go.
Ще один підхід, який може допомогти справитися з великою кардинальністю, називається угруповання (binning). Уявіть, що у вас є поле, яке становить зростання людини. Зростання - це число з плаваючою комою, але ми, люди, не думаємо про нього в такому ключі. Для нас немає різниці між зростом 185,2 см та 185,3 см.
Виходить, ми можемо згрупувати схожі значення групи в межах 1 см.
А якщо ми ще й знаємо, що дуже мало людей мають зріст менше 50 см і більше 250 см, то ми можемо по суті перетворити поле з нескінченною кардинальністю на поле з кардинальністю приблизно в 200 значень.
Звичайно, за потреби ми можемо зробити додаткову фільтрацію вже після.
Проблема великої пропускної спроможності
Наступна проблема bitmap-індексів полягає в тому, що їхнє оновлення може бути дуже дорогим.
Бази даних повинні давати можливість оновлювати дані в той момент, коли потенційно сотні інших запитів шукають ці дані. Нам потрібні локи, щоб уникнути проблем із одночасним доступом до даних чи інших проблем спільного доступу. А там, де є один великий лок, є проблема — lock contention, коли цей лок стає вузьким місцем.
Цю проблему можна вирішити або обійти за допомогою шардингу або використання версійних індексів.
Шардинг - штука проста і загальновідома. Ви можете шардувати bitmap-індекс так, як ви шардували б будь-які інші дані. Замість одного великого локу ви отримаєте купу дрібних локів і таким чином позбавитеся lock contention.
Другий спосіб вирішення проблеми – це використання версіонованих індексів. У вас може бути одна копія індексу, яку ви використовуєте для пошуку або читання, і одна для запису або оновлення. І раз у якийсь проміжок часу (наприклад, раз на 100 мс або 500 мс) ви їх дублюєте та міняєте місцями. Звичайно, цей підхід застосовується лише в тих випадках, коли ваш додаток може працювати з трохи відстаючим пошуковим індексом.
Ці два підходи можна використовувати одночасно: у вас може бути шардований версійний індекс.
Більш складні запити
Остання проблема bitmap-індексів полягає в тому, що, як нам кажуть, вони погано підходять для складніших типів запитів, наприклад, запитів «по проміжку».
І справді, якщо подумати, бітові операції типу AND, OR і т. д. не дуже підходять для запитів а-ля «Покажи мені готелі з вартістю номера від 200 до 300 доларів за ніч».
Наївним і дуже нерозумним рішенням було б взяти результати для кожного доларового значення та поєднати їх бітовою операцією OR.
Трохи правильнішим рішенням було б використовувати угруповання. Наприклад, у групи по 50 доларів. Це прискорило б наш процес у 50 разів.
Але проблема також легко вирішується використанням уявлення, створеного спеціально для такого типу запитів. У наукових працях воно називається range-encoded bitmaps.
У такому поданні ми не просто виставляємо один біт для будь-якого значення (наприклад, 200), а виставляємо це значення і все, що вище. 200 та вище. Те саме для 300: 300 і вище. І так далі.
Використовуючи це уявлення, ми можемо відповісти на такий пошуковий запит, пройшовши по індексу всього два рази. Спочатку ми отримаємо список готелів, де номер коштує менше або 300 доларів, а потім викинемо з нього ті, де вартість номера менша або 199 доларів. Готово.
Ви здивуєтеся, але навіть геозапити можливі за допомогою bitmap-індексів. Хитрість у тому, щоб використовувати геоподання, що оточує вашу координату геометричною фігурою. Наприклад, S2 від Google. Фігуру повинно бути можливо уявити у вигляді трьох або більше прямих, що перетинаються, які можна пронумерувати. Таким чином ми зможемо перетворити наш геозапит на кілька запитів «проміжком» (за цими пронумерованими лініями).
Готові рішення
Сподіваюся, я трохи вас зацікавив і у вас в арсеналі з'явився ще один корисний інструмент. Якщо вам коли-небудь потрібно буде зробити щось подібне, ви знатимете, в який бік дивитися.
Однак не всі мають час, терпіння і ресурси, щоб створити bitmap-індекси з нуля. Особливо просунуті, з використанням SIMD, наприклад.
На щастя, є кілька готових рішень, які допоможуть вам.
Roaring бітмапи
По-перше, є та сама roaring bitmaps-бібліотека, про яку я вже говорив. Вона містить усі необхідні контейнери та бітові операції, які вам знадобляться для того, щоб зробити повноцінний bitmap-індекс.
На жаль, зараз жодна з Go-реалізацій не використовує SIMD, а значить, Go-реалізації менш продуктивні, ніж реалізації на C, наприклад.
Pilosa
Інший продукт, який може вам допомогти, — СУБД Pilosa, яка, по суті, має лише bitmap-індекси. Це відносно нове рішення, але воно завойовує серця із величезною швидкістю.
Pilosa використовує roaring бітмапи всередині себе і дає вам можливість використовувати їх, спрощує та пояснює всі ті речі, про які я говорив вище: угруповання, range-encoded bitmaps, поняття поля тощо.
Давайте швиденько поглянемо на приклад використання Pilosa для відповіді на запитання, що вже знайоме вам.
Приклад дуже подібний до того, що ви бачили раніше. Ми створюємо клієнт до сервера Pilosa, створюємо індекс та необхідні поля, потім заповнюємо наші поля рандомними даними з ймовірностями та, нарешті, виконуємо знайомий запит.
Після цього ми використовуємо NOT на полі «expensive», потім перетинаємо результат (або AND) з полем «terrace» і з полем «reservations». І нарешті отримуємо фінальний результат.
Я дуже сподіваюся, що в найближчому майбутньому в СУБД на кшталт MySQL і PostgreSQL теж з'явиться цей новий тип індексів - bitmap-індекси.
Висновок
Якщо ви ще не заснули, дякую. Мені довелося побіжно торкнутися багатьох тем через обмежену кількість часу, але я сподіваюся, що доповідь була корисною і, може, навіть мотивуючою.
Про bitmap-індекс добре знати, навіть якщо прямо зараз вони вам не потрібні. Нехай вони будуть ще одним інструментом у вашій скриньці.
Ми з вами розглянули різні трюки збільшення продуктивності для Go і ті речі, з якими компілятор Go поки що не дуже добре справляється. А це абсолютно точно корисно знати кожному програмісту на Go.
Це все, що я хотів розповісти. Дякую!
Джерело: habr.com