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

увод

Дао сам овај извештај на енглеском на конференцији ГопхерЦон Руссиа 2019 у Москви и на руском на састанку у Нижњем Новгороду. Говоримо о индексу битмапа - мање уобичајеном од Б-стабла, али не мање занимљивом. Дељење запис говори на конференцији на енглеском језику и транскрипти текстова на руском језику.

Погледаћемо како функционише битмап индекс, када је бољи, када је лошији од других индекса и у којим случајевима је знатно бржи од њих; Хајде да видимо који популарни ДБМС-ови већ имају битмап индексе; Хајде да покушамо да напишемо своје у Го. И „за десерт“ користићемо готове библиотеке за креирање сопствене супербрзе специјализоване базе података.

Искрено се надам да ће вам моји радови бити корисни и занимљиви. Иди!

Увод

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

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

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

Данас ћу говорити о следећем:

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

Дакле, шта су индекси?

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

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

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

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

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

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

Последњи приступ је да у потпуности искористимо сву моћ коју нам даје савремени хардвер. То је управо оно што радимо у битмап индексима. Да, када их користимо понекад морамо да прођемо кроз цео индекс, али ми то радимо супер ефикасно.

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

Данас ћу говорити о најмање познатом приступу од ових - битмап индексима.

Ко сам ја да говорим о овој теми?

Радим као вођа тима у Бадоо-у (можда сте боље упознати са нашим другим производом, Бумбле). Већ имамо више од 400 милиона корисника широм света и многе функције које бирају најбоље за њих. Ово радимо користећи прилагођене услуге, укључујући индексе битмапа.

Дакле, шта је то битмап индекс?

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

Речено нам је да су битмап индекси најприкладнији и веома ефикасни за случајеве у којима постоје претраге које комбинују упите у многим колонама ниске кардиналности (мислите на „боју очију“ или „брачни статус“ у односу на нешто попут „удаљеност од центра града“). Али касније ћу показати да добро функционишу и за колоне високе кардиналности.

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

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

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

Хајде да сваком ресторану дамо редни број који почиње од 0 и доделимо меморију за 6 битмапа (по једну за сваку карактеристику). Затим ћемо попунити ове битмапе у зависности од тога да ли ресторан има ово својство или не. Ако ресторан 4 има веранду, онда ће бит бр. 4 у битмапу „има веранду“ бити постављен на 1 (ако нема веранде, онда на 0).

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

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

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


Други захтев је мало компликованији. Морамо да користимо НОТ битмап на „скупој“ битмапи да бисмо добили листу јефтиних ресторана, затим И то са битмапом „могу ли резервисати сто“ и резултат И резултат са битмапом „постоји веранда“. Добијена битмапа ће садржати листу установа које испуњавају све наше критеријуме. У овом примеру ово је само ресторан Јуност.


Много је теорије укључено, али не брините, врло брзо ћемо видети код.

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

Ако користите индексе битмапа на Гоогле-у, 90% одговора ће се на овај или онај начин односити на Орацле ДБ. Али други ДБМС-ови вероватно такође подржавају тако кул ствар, зар не? Не баш.

Хајде да прођемо кроз листу главних осумњичених.

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

ПостгреСКЛ не подржава битмап индексе, али користи једноставне битмапе и битне операције да комбинује резултате претраге у више других индекса.

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

Редис има једноставна битова поља (хттпс://редис.ио/цоммандс/битфиелд) без могућности да их траже.

МонгоДБ још увек не подржава битмап индексе, али постоји и Предлог који предлаже да се ова опција дода https://jira.mongodb.org/browse/SERVER-1723

Еластицсеарцх интерно користи битмапе (хттпс://ввв.еластиц.цо/блог/фраме-оф-референце-анд-роаринг-битмапс).

• Али у нашој кући се појавио нови комшија: Пилоса. Ово је нова нерелациона база података написана у Го. Садржи само битмап индексе и све заснива на њима. Причаћемо о томе мало касније.

Имплементација у Го

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

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

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

Биће нам потребне две помоћне функције. Један ће се користити за попуњавање наших битмапа насумичним подацима. Насумично, али са одређеном вероватноћом да ресторан има свако својство. На пример, верујем да је у Москви врло мало ресторана у којима не можете да резервишете сто, а чини ми се да је око 20% објеката погодно за вегетаријанце.

Друга функција ће претворити битмап у листу ресторана.


Да бисмо одговорили на упит „Покажи ми јефтине ресторане који имају терасу и могу да резервишу“, потребне су нам две битне операције: НОТ и И.

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

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

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

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

Након што сам урадио мало профилисања са ппроф-ом, приметио сам да Го компајлеру недостаје једна врло једноставна, али веома важна оптимизација: уметање функција.

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

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

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

Друго уско грло је лако уочити ако пажљиво погледате излаз склопа. Компајлер је додао проверу граница пресека тачно унутар наше најзабавније петље. Чињеница је да је Го безбедан језик, компајлер се плаши да су моја три аргумента (три пресека) различите величине. Уосталом, тада ће постојати теоретска могућност појаве такозваног преливања бафера.

Хајде да уверимо компајлер тако што ћемо му показати да су сви делови исте величине. То можемо учинити додавањем једноставне провере на почетку наше функције.

Видевши ово, компајлер срећно прескочи проверу и на крају уштедимо још 500 наносекунди.

Биг бутцхес

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

Све што радимо су основне битне операције, а наши процесори их изводе веома ефикасно. Али, нажалост, ми „хранимо“ наш процесор врло малим пословима. Наше функције обављају операције на бази бајт по бајт. Можемо врло лако да подесимо наш код да ради са 8-бајтним деловима користећи УИнт64 резове.

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

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

Али ово није крај. Наши процесори могу да раде са деловима од 16, 32 па чак и 64 бајта. Такве „широке“ операције се називају појединачна инструкција више података (СИМД; једна инструкција, много података), а процес трансформације кода тако да користи такве операције назива се векторизација.

Нажалост, Го компајлер је далеко од одличног у векторизацији. Тренутно, једини начин да се векторизује Го код је да узмете и поставите ове операције ручно помоћу Го асемблера.

Го асемблер је чудна звер. Вероватно знате да је асемблерски језик нешто што је у великој мери повезано са архитектуром рачунара за који пишете, али то није случај у Го-у. Го асемблер је више као ИРЛ (средњи језик представљања) или средњи језик: он је практично независан од платформе. Роб Пике је дао одличну представу извештај на ову тему пре неколико година на ГопхерЦону у Денверу.

Поред тога, Го користи необичан формат План 9, који се разликује од општеприхваћених АТ&Т и Интел формата.

Може се рећи да ручно писање Го асемблера није најзабавније.

Али, на срећу, већ постоје два алата високог нивоа који нам помажу да напишемо Го асемблер: ПеацхПи и аво. Оба услужна програма генеришу Го асемблер из кода вишег нивоа написаног у Питхон-у и Го-у.

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

Користићемо аво, тако да ће наши програми бити скоро редовни Го програми.

Овако изгледа најједноставнији пример аво програма. Имамо функцију маин() која у себи дефинише функцију Адд(), чије је значење сабирање два броја. Овде постоје помоћне функције за добијање параметара по имену и добијање једног од бесплатних и одговарајућих регистара процесора. Свака операција процесора има одговарајућу функцију на аво, као што се види у АДДК. Коначно, видимо помоћну функцију за чување резултујуће вредности.

Позивањем го генерате, ми ћемо извршити програм на аво-у и као резултат ће се генерисати две датотеке:

• адд.с са резултујућим кодом у Го асемблеру;
• стуб.го са заглављима функција за повезивање два света: Го и асемблер.

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

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

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

Раније смо користили ознаке и гото (или скокове) да побољшамо перформансе и преваримо Го компајлер, али сада то радимо од почетка. Поента је да су циклуси концепт вишег нивоа. У асемблеру имамо само ознаке и скокове.

Преостали код би већ требао бити познат и разумљив. Ми емулирамо петљу са ознакама и скоковима, узимамо мали део података из наша два пресека, комбинујемо их малом операцијом (А НЕ у овом случају) и затим стављамо резултат у резултујући пресек. Све.

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

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

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

Због тога је немогуће извући било какву корист од малих функција у асемблерском језику. Морамо или да напишемо велике функције, или да користимо нови пакет математике/битова, или да заобиђемо асемблерски језик.

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

За овај пример, одлучио сам да користим АВКС2, тако да ћемо користити операције које раде на деловима од 32 бајта. Структура кода је веома слична скаларној верзији: учитавање параметара, тражење бесплатног заједничког регистра итд.

Једна од иновација је да шире векторске операције користе посебне широке регистре. У случају 32-бајтних комада, ово су регистри са префиксом И. Због тога видите функцију ИММ() у коду. Да користим АВКС-512 са 64-битним деловима, префикс би био З.

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

Па, шта је са перформансама? Она је лепа! Остварили смо убрзање од око седам пута у поређењу са најбољим Го решењем. Импресивно, зар не?

Али чак и ова имплементација би потенцијално могла да се убрза коришћењем АВКС-512, претходног преузимања или ЈИТ-а (баш-ин-тиме компајлер) за планер упита. Али ово је свакако тема за посебан извештај.

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

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

Старији радови помињу три проблема са битмап индексима, али новији радови и ја тврдим да више нису релевантни. Нећемо се удубљивати у сваки од ових проблема, већ ћемо их сагледати површно.

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

Дакле, речено нам је да су битмап индекси погодни само за поља са ниском кардиналношћу, односно она која имају мало вредности (на пример, пол или боју очију), а разлог је што је уобичајено представљање таквих поља (један бит по вредности) у случају велике кардиналности, заузеће превише простора и, штавише, ови битмап индекси ће бити лоше (ретко) попуњени.


Понекад можемо користити другачији приказ, као што је стандардни који користимо за представљање бројева. Али долазак алгоритама компресије је све променио. Током протеклих деценија, научници и истраживачи су дошли до великог броја алгоритама компресије за битмапе. Њихова главна предност је у томе што нема потребе за декомпресијом битмапа за обављање битних операција – можемо изводити битне операције директно на компресованим битмапама.

Недавно су почели да се појављују хибридни приступи, као што су бучне битмапе. Они истовремено користе три различита представљања за битмапе – саме битмапе, низове и такозвана покретања битова – и балансирају између њих како би максимизирали перформансе и минимизирали потрошњу меморије.

У најпопуларнијим апликацијама можете пронаћи бучне битмапе. Већ постоји огроман број имплементација за широк спектар програмских језика, укључујући више од три имплементације за Го.

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

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

А ако такође знамо да је врло мало људи нижих од 50 цм и виших од 250 цм, онда можемо суштински претворити поље са бесконачном кардиналношћу у поље са кардиналношћу од око 200 вредности.

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

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

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

Базе података морају бити у могућности да ажурирају податке док потенцијално стотине других упита претражују податке. Потребне су нам браве да бисмо избегли проблеме са истовременим приступом подацима или друге проблеме са дељењем. А тамо где постоји једна велика брава, постоји проблем - сукоб браве, када ова брава постане уско грло.

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

Схардинг је једноставна и добро позната ствар. Можете да делите индекс битмапе као и све друге податке. Уместо једне велике браве, добићете гомилу малих брава и тако се ослободити свађе око браве.

Други начин да се реши проблем је коришћење верзионисаних индекса. Можете имати једну копију индекса коју користите за претраживање или читање и једну коју користите за писање или ажурирање. И једном у одређеном временском периоду (на пример, једном сваких 100 мс или 500 мс) ви их дуплирате и мењате. Наравно, овај приступ је применљив само у случајевима када ваша апликација може да обради индекс претраживања који мало заостаје.

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

Сложенији упити

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

Заиста, ако размислите о томе, битне операције попут И, ИЛИ итд. нису баш погодне за упите а ла „Покажите ми хотеле са ценама соба од 200 до 300 долара по ноћи.“

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

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

Али проблем се такође лако решава коришћењем погледа креираног посебно за ову врсту захтева. У научним радовима то се назива битмапама са кодираним опсегом.

У овој представи, не постављамо само један бит за неку вредност (на пример, 200), већ постављамо ову вредност и све више. 200 и више. Исто за 300: 300 и више. И тако даље.

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

Бићете изненађени, али чак су и геоупити могући помоћу битмап индекса. Трик је да користите геометријски приказ који окружује вашу координату геометријском фигуром. На пример, С2 од Гоогле-а. Фигура мора бити могуће представити у облику три или више линија које се секу и које се могу нумерисати. На овај начин можемо да претворимо наш геоупит у неколико упита „дуж процепа“ (дуж ових нумерисаних линија).

Реади Солутионс

Надам се да сам вас мало заинтересовао и да сада имате још једно корисно средство у свом арсеналу. Ако икада будете морали да урадите нешто овако, знаћете на који начин да гледате.

Међутим, немају сви времена, стрпљења или ресурса да креирају битмап индексе од нуле. Нарочито напредније, користећи СИМД, на пример.

Срећом, постоји неколико готових решења која ће вам помоћи.

Роаринг битмап

Прво, ту је иста библиотека битмапа о којој сам већ говорио. Садржи све потребне контејнере и битне операције које ће вам требати да направите пуноправни индекс битмапа.

Нажалост, у овом тренутку, ниједна од имплементација Го не користи СИМД, што значи да су Го имплементације мање ефикасне од Ц имплементација, на пример.

длакав

Још један производ који вам може помоћи је Пилоса ДБМС, који, у ствари, има само битмап индексе. Ово је релативно ново решење, али осваја срца великом брзином.

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

Хајде да накратко погледамо пример коришћења Пилоса за одговор на питање које вам је већ познато.

Пример је веома сличан ономе што сте видели раније. Креирамо клијента за Пилоса сервер, креирамо индекс и потребна поља, затим попуњавамо наша поља случајним подацима са вероватноћама и, на крају, извршавамо познати упит.

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

Заиста се надам да ће се у догледној будућности овај нови тип индекса појавити и у ДБМС-овима као што су МиСКЛ и ПостгреСКЛ – битмап индекси.

Закључак

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

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

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

То је све што сам хтео да ти кажем. Хвала вам!

Извор: ввв.хабр.цом