Битмап индекси во Go: пребарување со дива брзина

воведен говор

Го дадов овој извештај на англиски на конференцијата GopherCon Russia 2019 во Москва и на руски на состанокот во Нижни Новгород. Зборуваме за битмап индекс - поретко од Б-дрвото, но не помалку интересен. Споделување рекорд говори на конференцијата на англиски и текстуални преписи на руски.

Ќе погледнеме како функционира битмап индексот, кога е подобар, кога е полош од другите индекси и во кои случаи е значително побрз од нив; Ајде да видиме кои популарни DBMS веќе имаат битмап индекси; Ајде да се обидеме да го напишеме своето во Go. И „за десерт“ ќе користиме готови библиотеки за да создадеме сопствена супербрза специјализирана база на податоци.

Навистина се надевам дека моите дела ќе бидат корисни и интересни за вас. Оди!

Вовед

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

Здраво на сите! Шест навечер и сите сме супер уморни. Одлично време да се зборува за здодевната теорија на индекси на база на податоци, нели? Не грижете се, ќе имам неколку линии изворен код овде-онде. 🙂

Сите шеги настрана, извештајот е полн со информации, а ние немаме многу време. Па ајде да започнеме.

Денес ќе зборувам за следново:

• што се индекси;
• што е битмап индекс;
• каде се користи и каде НЕ се користи и зошто;
• едноставна имплементација во Go и малку борба со компајлерот;
• малку помалку едноставна, но многу попродуктивна имплементација во Go асемблерот;
• „проблеми“ на битмапи индекси;
• постоечки имплементации.

Значи, што се индексите?

Индексот е посебна структура на податоци што ја одржуваме и ажурираме покрај главните податоци. Се користи за забрзување на пребарувањето. Без индекси, пребарувањето би барало целосно поминување низ податоците (процес наречен целосно скенирање), а овој процес има линеарна алгоритамска сложеност. Но, базите на податоци обично содржат огромни количини на податоци и линеарната сложеност е премногу бавна. Идеално, би добиле логаритамска или константна.

Ова е многу сложена тема, преполна со суптилности и компромиси, но по разгледувањето на деценискиот развој и истражување на базата на податоци, подготвен сум да кажам дека има само неколку широко користени пристапи за креирање на индекси на бази на податоци.

Првиот пристап е хиерархиски да се намали просторот за пребарување, делејќи го просторот за пребарување на помали делови.

Ова обично го правиме користејќи различни видови дрвја. Пример би била голема кутија со материјали во вашиот плакар што содржи помали кутии со материјали поделени на различни теми. Ако ви требаат материјали, веројатно ќе ги барате во кутија на која пишува „Материјали“ наместо „Колачиња“, нели?

Вториот пристап е веднаш да се избере саканиот елемент или група елементи. Ова го правиме во хаш карти или обратни индекси. Користењето хаш мапи е многу слично на претходниот пример, но наместо кутија со кутии, имате куп мали кутии со финални предмети во вашиот плакар.

Третиот пристап е да се елиминира потребата за пребарување. Ова го правиме користејќи филтри Bloom или филтри за кукавица. Првите веднаш даваат одговор, заштедувајќи ве од барањето.

Последниот пристап е целосно да ја искористиме сета моќ што ни ја дава современиот хардвер. Ова е токму она што го правиме во битмап индексите. Да, кога ги користиме понекогаш треба да го поминеме целиот индекс, но тоа го правиме супер ефикасно.

Како што реков, темата за индекси на бази на податоци е огромна и полна со компромиси. Ова значи дека понекогаш можеме да користиме неколку пристапи во исто време: ако треба уште повеќе да го забрзаме пребарувањето или ако треба да ги покриеме сите можни типови на пребарување.

Денес ќе зборувам за најмалку познатиот пристап од овие - битмапи индекси.

Кој сум јас да зборувам на оваа тема?

Работам како тимски лидер во Badoo (можеби сте повеќе запознаени со нашиот друг производ, Bumble). Веќе имаме повеќе од 400 милиони корисници ширум светот и многу функции кои го избираат најдоброто совпаѓање за нив. Ова го правиме користејќи сопствени услуги, вклучувајќи ги и индексите на битмапи.

Значи, што е битмап индекс?

Битмап индексите, како што сугерира името, користат битмапи или битови за да имплементираат индекс за пребарување. Од птичја перспектива, овој индекс се состои од една или повеќе такви битмапи кои ги претставуваат сите ентитети (како што се луѓето) и нивните својства или параметри (возраст, боја на очите, итн.) и алгоритам што користи операции со битови (И, ИЛИ, НЕ ) за да одговорите на барањето за пребарување.

Кажано ни е дека индексите на битмапа се најдобро прилагодени и многу погодни за случаи каде што има пребарувања кои комбинираат прашања низ многу колони со ниска кардиналност (размислете „боја на очите“ или „брачен статус“ наспроти нешто како „оддалеченост од центарот на градот“). Но, подоцна ќе покажам дека тие работат добро и за колони со висока кардиналност.

Да го погледнеме наједноставниот пример на битмап индекс.

Замислете дека имаме список на московски ресторани со бинарни својства како овие:

• во близина на метро;
• има приватен паркинг;
• има веранда (има тераса);
• можете да резервирате маса (прифаќа резервации);
• погоден за вегетаријанци (пријателски за веганите);
• скапо (скапо).

Ајде да му дадеме на секој ресторан пореден број почнувајќи од 0 и да одвоиме меморија за 6 битмапи (по еден за секоја карактеристика). Потоа ќе ги пополниме овие битмапи во зависност од тоа дали ресторанот го има овој имот или не. Ако ресторанот 4 има веранда, тогаш битот бр. 4 во битмапата „има веранда“ ќе биде поставен на 1 (ако нема веранда, тогаш на 0).

Сега го имаме наједноставниот можен индекс на битмапа и можеме да го користиме за да одговориме на прашања како што се:

• „Покажи ми ресторани за вегетаријанци“;
• „Покажете ми евтини ресторани со веранда каде што можете да резервирате маса“.

Како? Ајде да погледнеме. Првото барање е многу едноставно. Сè што треба да направиме е да ја земеме битмапата „погодна за вегетаријанците“ и да ја претвориме во листа на ресторани чии делови се изложени.


Второто барање е малку покомплицирано. Треба да ја користиме НЕ битмапата на „скапата“ битмапа за да добиеме листа на евтини ресторани, потоа И тоа со битмапата „дали можам да резервирам маса“ и И резултатот со битмапата „има веранда“. Резултирачката битмапа ќе содржи листа на претпријатија кои ги исполнуваат сите наши критериуми. Во овој пример, ова е само ресторанот Јуност.


Вклучени се многу теории, но не грижете се, ќе го видиме кодот многу наскоро.

Каде се користат битмапи индексите?

Ако пребарувате индекси на битмапа на Google, 90% од одговорите ќе бидат поврзани со Oracle DB на еден или друг начин. Но, и другите DBMS веројатно поддржуваат таква кул работа, нели? Не навистина.

Ајде да ја разгледаме листата на главни осомничени.

MySQL сè уште не поддржува битмап индекси, но има предлог кој сугерира додавање на оваа опција (https://dev.mysql.com/worklog/task/?id=1524).

PostgreSQL не поддржува битмапи индекси, но користи едноставни битмапи и бит операции за да ги комбинира резултатите од пребарувањето низ повеќе други индекси.

Tarantool има индекси на битови и поддржува едноставни пребарувања на нив.

Редис има едноставни битови полиња (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).

• Но, во нашата куќа се појави нов сосед: Пилоса. Ова е нова не-релациона база на податоци напишана во Go. Содржи само битмапи индекси и се заснова на нив. Ќе зборуваме за тоа малку подоцна.

Имплементација во Go

Но, зошто битмап индексите толку ретко се користат? Пред да одговорам на ова прашање, би сакал да ви покажам како да имплементирате многу едноставен индекс на битмапа во Go.

Битмапите во суштина се само делови од податоци. Во Go, ајде да користиме парчиња бајти за ова.

Имаме една битмапа за една карактеристика на ресторанот, и секој бит во битмапата покажува дали одреден ресторан го има овој имот или не.

Ќе ни требаат две функции за помош. Еден ќе се користи за пополнување на нашите битмапи со случајни податоци. Случајно, но со одредена веројатност дека ресторанот го има секој имот. На пример, верувам дека има многу малку ресторани во Москва каде што не можете да резервирате маса и ми се чини дека околу 20% од установите се погодни за вегетаријанци.

Втората функција ќе ја претвори битмапата во листа на ресторани.


За да одговориме на прашањето „Покажи ми евтини ресторани кои имаат внатрешен двор и можат да резервираат“, ни требаат две битни операции: НЕ и И.

Можеме малку да го поедноставиме нашиот код со користење на покомплексниот И НЕ оператор.

Имаме функции за секоја од овие операции. И двајцата минуваат низ парчињата, ги земаат соодветните елементи од секоја, ги комбинираат со малку операција и го ставаат резултатот во добиеното парче.

И сега можеме да ги користиме нашите битмапи и функции за да одговориме на барањето за пребарување.

Перформансите не се толку високи, иако функциите се многу едноставни и заштедивме многу пари со тоа што не враќавме ново добиено парче секогаш кога ќе се повикаше функцијата.

Откако направив малку профилирање со pprof, забележав дека на компајлерот Go недостасува една многу едноставна, но многу важна оптимизација: вградување на функции.

Факт е дека компајлерот Go ужасно се плаши од јамки што минуваат низ парчиња и категорично одбива да ги вметнува функциите што содржат такви јамки.

Но, не се плашам и можам да го измамам компајлерот користејќи goto наместо циклус, како во старите добри времиња.

И, како што можете да видите, сега компајлерот среќно ќе ја вгради нашата функција! Како резултат на тоа, успеваме да заштедиме околу 2 микросекунди. Не е лошо!

Второто тесно грло е лесно да се види ако внимателно го погледнете излезот на склопот. Компајлерот додаде проверка на границите на парчето право во нашата најжешка јамка. Факт е дека Go е безбеден јазик, компајлерот се плаши дека моите три аргументи (три парчиња) се со различна големина. На крајот на краиштата, тогаш ќе има теоретска можност за појава на таканаречено прелевање на тампон.

Ајде да го увериме компајлерот покажувајќи му дека сите парчиња се со иста големина. Ова може да го направиме со додавање едноставна проверка на почетокот на нашата функција.

Гледајќи го ова, компајлерот среќно ја прескокнува проверката и на крајот заштедуваме уште 500 наносекунди.

Големи месеци

Во ред, успеавме да притиснеме некои перформанси од нашата едноставна имплементација, но овој резултат е всушност многу полош отколку што е можно со сегашниот хардвер.

Сè што правиме се основни операции со битови, а нашите процесори ги извршуваат многу ефикасно. Но, за жал, ние го „храниме“ нашиот процесор со многу мали парчиња работа. Нашите функции извршуваат операции бајт-по-бајт. Можеме многу лесно да го прилагодиме нашиот код за да работи со делови од 8 бајти користејќи парчиња UInt64.

Како што можете да видите, оваа мала промена ја забрза нашата програма осум пати со зголемување на големината на серијата за осум пати. Добивката може да се каже дека е линеарна.

Имплементација во асемблер

Но, ова не е крајот. Нашите процесори можат да работат со делови од 16, 32, па дури и 64 бајти. Ваквите „широки“ операции се нарекуваат повеќекратни податоци со единечна инструкција (SIMD; една инструкција, многу податоци), а процесот на трансформирање на кодот за да користи такви операции се нарекува векторизација.

За жал, компајлерот Go е далеку од одличен во векторизација. Во моментов, единствениот начин да се векторизира Go кодот е да се земат и стават овие операции рачно со помош на Go асемблерот.

Оди асемблерот е чуден ѕвер. Веројатно знаете дека асемблерскиот јазик е нешто што е силно поврзано со архитектурата на компјутерот за кој пишувате, но тоа не е случај во Go. Go асемблерот е повеќе како IRL (јазик на средно претставување) или среден јазик: тој е практично независен од платформата. Одличен настап имаше Роб Пајк извештај на оваа тема пред неколку години на GopherCon во Денвер.

Покрај тоа, Go користи необичен формат План 9, кој се разликува од општоприфатените формати AT&T и Intel.

Слободно може да се каже дека рачно пишувањето Go асемблерот не е баш најзабавно.

Но, за среќа, веќе постојат две алатки на високо ниво кои ни помагаат да напишеме Go асемблер: PeachPy и avo. Двете алатки генерираат Go асемблер од кодот на повисоко ниво напишан во Python и Go, соодветно.

Овие алатки ги поедноставуваат работите како распределбата на регистрите, циклусите за пишување и генерално го поедноставуваат процесот на влегување во светот на програмирањето на склопување во Go.

Ќе користиме avo, така што нашите програми ќе бидат речиси редовни Go-програми.

Вака изгледа наједноставниот пример на avo програма. Имаме функција main(), која во себе ја дефинира функцијата Add(), чиешто значење е да се соберат два броја. Овде има помошни функции за да ги добиете параметрите по име и да добиете еден од бесплатните и соодветни регистри на процесорот. Секоја операција на процесорот има соодветна функција на avo, како што се гледа во ADDQ. Конечно, гледаме помошна функција за складирање на добиената вредност.

Со повик go generate, ќе ја извршиме програмата на avo и како резултат на тоа ќе се генерираат две датотеки:

• add.s со добиениот код во Go асемблерот;
• stub.go со заглавија на функции за поврзување на двата света: Go и асемблерот.

Сега кога видовме што и како прави avo, да ги погледнеме нашите функции. Имплементирав и скаларна и векторска (SIMD) верзии на функциите.

Ајде прво да ги погледнеме скаларните верзии.

Како и во претходниот пример, бараме бесплатен и валиден регистар за општа намена, не треба да пресметуваме поместувања и големини за аргументите. Аво го прави сето ова за нас.

Порано користевме етикети и goto (или скокови) за да ги подобриме перформансите и да го измамиме компајлерот Go, но сега тоа го правиме од почеток. Поентата е дека циклусите се концепт на повисоко ниво. Во асемблер имаме само етикети и скокови.

Преостанатиот код треба да биде веќе познат и разбирлив. Имитираме јамка со етикети и скокови, земаме мал дел од податоците од нашите два парчиња, ги комбинираме со операција на битови (И НЕ во овој случај) и потоа го ставаме резултатот во добиениот дел. Сите.

Вака изгледа конечниот асемблер код. Не моравме да пресметуваме поместувања и големини (означени со зелено) или да ги следиме употребените регистри (означени со црвено).

Ако ги споредиме перформансите на имплементацијата на асемблерски јазик со перформансите на најдобрата имплементација во Go, ќе видиме дека е исто. И ова е очекувано. На крајот на краиштата, не направивме ништо посебно - само репродуциравме што би направил Go компајлерот.

За жал, не можеме да го принудиме компајлерот да ги вметне нашите функции напишани на асемблер јазик. Компајлерот Go моментално нема таква функција, иако веќе подолго време има барање да се додаде.

Затоа е невозможно да се извлече корист од малите функции во асемблерскиот јазик. Треба или да напишеме големи функции, или да го користиме новиот пакет математика/битови или да го заобиколиме јазикот на асемблер.

Ајде сега да ги погледнеме векторските верзии на нашите функции.

За овој пример, решив да користам AVX2, така што ќе користиме операции што работат на делови од 32 бајти. Структурата на кодот е многу слична на скаларната верзија: вчитување параметри, барање за бесплатен споделен регистар итн.

Една иновација е што пошироките векторски операции користат специјални широки регистри. Во случај на делови од 32 бајти, тоа се регистри со префикс Y. Затоа ја гледате функцијата YMM() во кодот. Ако користев AVX-512 со 64-битни делови, префиксот ќе беше Z.

Втората иновација е тоа што решив да користам оптимизација наречена unrolling на јамката, што значи рачно извршување на осум операции на циклусот пред да се прескокне на почетокот на циклусот. Оваа оптимизација го намалува бројот на гранки во кодот и е ограничена со бројот на достапни бесплатни регистри.

Па, што е со перформансите? Таа е убава! Постигнавме забрзување од околу седум пати во споредба со најдоброто Go решение. Импресивно, нели?

Но, дури и оваа имплементација би можела потенцијално да се забрза со користење на AVX-512, претходно преземање или JIT (компајлер само навреме) за распоредувачот на прашања. Но, ова е секако тема за посебен извештај.

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

Сега, кога веќе разгледавме едноставна имплементација на битмап индекс во Go и многу попродуктивна во асемблерски јазик, ајде конечно да разговараме зошто битмап индексите толку ретко се користат.

Постарите трудови споменуваат три проблеми со индексите на битмапа, но поновите трудови и јас тврдам дека тие повеќе не се релевантни. Ние нема да нурнеме длабоко во секој од овие проблеми, туку ќе ги погледнеме површно.

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

Значи, ни е кажано дека индексите на битмапа се погодни само за полиња со мала кардиналност, односно оние кои имаат малку вредности (на пример, пол или боја на очите), а причината е што вообичаеното претставување на такви полиња (еден бит по вредност) во случај на висока кардиналност, ќе зазема премногу простор и, згора на тоа, овие битмапи индекси ќе бидат слабо (ретко) пополнети.


Понекогаш може да користиме различно претставување, како што е стандардниот што го користиме за претставување на броеви. Но, тоа беше појавата на алгоритми за компресија што промени сè. Во текот на изминатите децении, научниците и истражувачите дојдоа до голем број алгоритми за компресија за битмапи. Нивната главна предност е тоа што нема потреба од декомпресија на битмапи за извршување на операции со битови - можеме да вршиме операции со битови директно на компресирани битмапи.

Неодамна, почнаа да се појавуваат хибридни пристапи, како што се громогласните битмапи. Тие истовремено користат три различни претстави за битмапи - самите битмапи, низи и т.н.

Може да најдете громогласни битмапи во најпопуларните апликации. Веќе има огромен број имплементации за широк спектар на програмски јазици, вклучувајќи повеќе од три имплементации за Go.

Друг пристап кој може да ни помогне да се справиме со високата кардиналност се нарекува бинирање. Замислете дека имате поле што ја претставува висината на една личност. Висината е број со подвижна запирка, но ние луѓето не размислуваме за тоа така. За нас нема разлика помеѓу висина 185,2 cm и 185,3 cm.

Излегува дека можеме да групираме слични вредности во групи во рок од 1 см.

И ако знаеме дека многу малку луѓе се пониски од 50 cm и повисоки од 250 cm, тогаш во суштина можеме да претвориме поле со бесконечна кардиналност во поле со кардиналност од околу 200 вредности.

Се разбира, доколку е потребно, можеме да направиме дополнително филтрирање потоа.

Проблем со висок пропусен опсег

Следниот проблем со битмап индексите е тоа што нивното ажурирање може да биде многу скапо.

Базите на податоци мора да можат да ги ажурираат податоците додека потенцијално стотици други прашања ги пребаруваат податоците. Ни требаат брави за да избегнеме проблеми со истовремен пристап до податоци или други проблеми со споделувањето. И таму каде што има една голема брава, има проблем - расправија за заклучување, кога оваа брава ќе стане тесно грло.

Овој проблем може да се реши или заобиколи со користење на сечење или користење верзии на индекси.

Шардирањето е едноставна и добро позната работа. Можете да го разделите индексот на битмапа како и сите други податоци. Наместо една голема брава, ќе добиете еден куп мали прамени и на тој начин ќе се ослободите од расправијата за бравата.

Вториот начин да се реши проблемот е да се користат верзии на индекси. Може да имате една копија од индексот што ја користите за пребарување или читање и една што ја користите за пишување или ажурирање. И еднаш во одреден временски период (на пример, еднаш на 100 ms или 500 ms) ги дуплирате и заменувате. Се разбира, овој пристап е применлив само во случаи кога вашата апликација може да се справи со малку заостанат индекс на пребарување.

Овие два пристапа може да се користат истовремено: може да имате разделен верзиран индекс.

Покомплексни прашања

Конечниот проблем со битмап-индексите е тоа што ни е кажано дека тие не се добро прилагодени за посложени типови на прашања, како што се барањата за распон.

Навистина, ако размислите за тоа, бит-операциите како И, ИЛИ итн. не се многу погодни за прашања a la „Покажи ми хотели со цени на соби од 200 до 300 долари за ноќ“.

Наивно и многу немудро решение би било да се земат резултатите за секоја вредност на доларот и да се комбинираат со операција на битови ИЛИ.

Малку подобро решение би било да се користи групирање. На пример, во групи од 50 долари. Ова ќе го забрза нашиот процес за 50 пати.

Но, проблемот исто така лесно се решава со користење на приказ создаден специјално за овој тип на барања. Во научните трудови се нарекува битмапи со кодирани опсег.

Во оваа претстава, ние не поставуваме само еден бит за некоја вредност (на пример, 200), туку ја поставуваме оваа вредност и сè повисоко. 200 и погоре. Истото за 300: 300 и погоре. И така натаму.

Користејќи го ова претставување, можеме да одговориме на овој вид на барање за пребарување со поминување на индексот само двапати. Прво, ќе добиеме список на хотели каде што собата чини помалку или 300 долари, а потоа ќе ги отстраниме од неа оние каде цената на собата е помала или 199 долари. Подготвени.

Ќе бидете изненадени, но дури и геопрашања се можни со користење на битмап индекси. Трикот е да користите геометриска претстава што ја опкружува вашата координата со геометриска фигура. На пример, S2 од Google. Фигурата треба да може да се прикаже во форма на три или повеќе линии што се пресекуваат што може да се нумерираат. На овој начин можеме да го претвориме нашиот геодет во неколку прашања „по должината на јазот“ (по овие нумерирани линии).

Подготвени решенија

Се надевам дека малку ве заинтересирав и сега имате уште една корисна алатка во вашиот арсенал. Ако некогаш треба да направите нешто вакво, ќе знаете на која страна да изгледате.

Сепак, не секој има време, трпение или ресурси да креира битмап индекси од нула. Особено понапредните, со користење на SIMD, на пример.

За среќа, постојат неколку готови решенија кои ќе ви помогнат.

Громогласни битмапи

Прво, постои истата библиотека со битмапи за која веќе зборував. Ги содржи сите потребни контејнери и операции со битови што ќе ви требаат за да направите целосен индекс на битмапа.

За жал, во моментов, ниту една од имплементациите на Go не користи SIMD, што значи дека имплементациите на Go се помалку перформанси од имплементациите во C, на пример.

Пилоса

Друг производ што може да ви помогне е Pilosa DBMS, кој, всушност, има само битмапи индекси. Ова е релативно ново решение, но со голема брзина ги освојува срцата.

Pilosa користи внатрешно громогласни битмапи и ви дава можност да ги користите, ги поедноставува и објаснува сите работи за кои зборував погоре: групирање, битмапи кодирани со опсег, концепт на поле итн.

Ајде брзо да погледнеме на пример за користење на Pilosa за да одговориме на прашање со кое веќе сте запознаени.

Примерот е многу сличен на она што го видовте претходно. Ние создаваме клиент на серверот Pilosa, креираме индекс и потребните полиња, потоа ги пополнуваме нашите полиња со случајни податоци со веројатности и, конечно, го извршуваме познатото барање.

После тоа, ние користиме НЕ на полето „скапо“, потоа резултатот (или И тоа) го пресекуваме со полето „тераса“ и со полето „резервации“. И конечно, го добиваме конечниот резултат.

Навистина се надевам дека во догледна иднина овој нов тип на индекс ќе се појави и во DBMS како MySQL и PostgreSQL - bitmap индекси.

Заклучок

Ако сè уште не сте заспале, ви благодариме. Морав накратко да допрам многу теми поради ограниченото време, но се надевам дека разговорот беше корисен, а можеби и мотивирачки.

Битмап индексите е добро да се знаат, дури и ако не ви се потребни во моментов. Нека бидат уште една алатка во вашата кутија со алатки.

Разгледавме различни трикови за изведба на Go и работи со кои компајлерот Go сè уште не се справува многу добро. Но, ова е апсолутно корисно да го знае секој програмер на Go.

Тоа е се што сакав да ти кажам. Ви благодарам!

Извор: www.habr.com