Уступнае слова
Я выступіў з гэтым дакладам на англійскай мове на канферэнцыі 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 замест цыклу, як у старыя добрыя часы.
І, як бачыце, зараз кампілятар з радасцю інлайніт нашу функцыю! У выніку нам атрымоўваецца зэканоміць каля 2 мікрасекунд. Не дрэнна!
Другое вузкае месца нескладана ўбачыць, калі ўважліва паглядзець на асэмблерную выснову. Кампілятар дадаў праверку на межы слайса прама ўнутр нашага самага гарачага цыклу. Справа ў тым, што 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-індэксы будуць слаба (рэдка) запоўненыя.
Часам мы можам выкарыстоўваць іншае ўяўленне, напрыклад стандартнае, якое мы выкарыстоўваем для прадстаўлення лікаў. Але менавіта з'яўленне алгарытмаў сціску ўсё змяніла. За апошнія дзесяцігоддзі навукоўцы і даследнікі прыдумалі вялікую колькасць алгарытмаў сціску для бітмапаў. Асноўная іх перавага ў тым, што не трэба расціскаць бітмапы для правядзення бітавых аперацый - мы можам здзяйсняць бітавыя аперацыі прама над сціснутымі бітмапамі.
У апошні час сталі з'яўляцца і гібрыдныя падыходы, як, напрыклад, roaring бітмапы. Яны выкарыстоўваюць адначасова тры розных уяўленні для бітмапаў - уласна бітмапы, масівы і так званыя 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