ievads
Es sniedzu Å”o ziÅojumu angļu valodÄ GopherCon Russia 2019 konferencÄ MaskavÄ un krievu valodÄ sanÄksmÄ Å ižÅijnovgorodÄ. MÄs runÄjam par bitkartes indeksu - retÄk nekÄ B-koks, bet ne mazÄk interesants. DalÄ«Å”anÄs uzstÄÅ”anÄs konferencÄ angļu valodÄ un teksta atÅ”ifrÄjumi krievu valodÄ.
ApskatÄ«sim, kÄ darbojas bitkartes indekss, kad tas ir labÄks, kad sliktÄks par citiem indeksiem un kÄdos gadÄ«jumos tas ir ievÄrojami ÄtrÄks par tiem; ApskatÄ«sim, kurÄm populÄrajÄm DBVS jau ir bitkartes indeksi; MÄÄ£inÄsim uzrakstÄ«t savu Go. Un ādesertÄā mÄs izmantosim gatavas bibliotÄkas, lai izveidotu savu Ä«paÅ”i Ätru specializÄto datu bÄzi.
Ļoti ceru, ka mani darbi jums būs noderīgi un interesanti. Aiziet!
Ievads
Sveiki visiem! Ir seÅ”i vakarÄ, un mÄs visi esam ļoti noguruÅ”i. Lielisks laiks runÄt par garlaicÄ«go datu bÄzes indeksu teoriju, vai ne? Neuztraucieties, man Å”eit un tur bÅ«s dažas avota koda rindiÅas. š
Visus jokus malÄ, ziÅojums ir pilns ar informÄciju, un mums nav daudz laika. TÄtad sÄksim.
Å odien es runÄÅ”u par Å”Ädiem jautÄjumiem:
- kas ir indeksi;
- kas ir bitkartes indekss;
- kur tas tiek izmantots un kur NETIEK lietots un kÄpÄc;
- vienkÄrÅ”a ievieÅ”ana Go un neliela cÄ«Åa ar kompilatoru;
- nedaudz mazÄk vienkÄrÅ”a, bet daudz produktÄ«vÄka ievieÅ”ana Go montÄtÄjÄ;
- bitkartes indeksu āproblÄmasā;
- esoÅ”Äs implementÄcijas.
TÄtad, kas ir indeksi?
Indekss ir atseviŔķa datu struktÅ«ra, kuru mÄs uzturam un atjauninÄm papildus galvenajiem datiem. To izmanto, lai paÄtrinÄtu meklÄÅ”anu. Ja nebÅ«tu indeksu, meklÄÅ”anai bÅ«tu nepiecieÅ”ams pilnÄ«bÄ izpÄtÄ«t datus (process, ko sauc par pilnu skenÄÅ”anu), un Å”im procesam ir lineÄra algoritmiskÄ sarežģītÄ«ba. TaÄu datubÄzÄs parasti ir milzÄ«gs datu apjoms, un lineÄrÄ sarežģītÄ«ba ir pÄrÄk lÄna. IdeÄlÄ gadÄ«jumÄ mÄs iegÅ«tu logaritmisku vai konstantu.
Å Ä« ir ļoti sarežģīta tÄma, kas ir piepildÄ«ta ar smalkumiem un kompromisiem, taÄu, aplÅ«kojot gadu desmitiem ilguÅ”u datubÄzes izstrÄdi un pÄtniecÄ«bu, esmu gatavs teikt, ka ir tikai dažas plaÅ”i izmantotas pieejas datu bÄzes indeksu izveidei.
PirmÄ pieeja ir meklÄÅ”anas telpas hierarhiska samazinÄÅ”ana, sadalot meklÄÅ”anas telpu mazÄkÄs daļÄs.
MÄs parasti to darÄm, izmantojot dažÄda veida kokus. PiemÄrs varÄtu bÅ«t liela materiÄlu kaste jÅ«su skapÄ«, kurÄ ir mazÄkas materiÄlu kastes, kas sadalÄ«tas pa dažÄdÄm tÄmÄm. Ja jums ir nepiecieÅ”ami materiÄli, jÅ«s, iespÄjams, meklÄsit tos lodziÅÄ, kurÄ ir rakstÄ«ts "MateriÄli", nevis tajÄ, kas rakstÄ«ts "SÄ«kfaili", vai ne?
Otra pieeja ir nekavÄjoties atlasÄ«t vajadzÄ«go elementu vai elementu grupu. MÄs to darÄm hash kartÄs vai reversajos indeksos. JaucÄjkartes izmantoÅ”ana ir ļoti lÄ«dzÄ«ga iepriekÅ”Äjam piemÄram, taÄu kastÄ«Å”u vietÄ jÅ«su skapÄ« ir Ä·ekars mazu kastÄ«Å”u ar galÄ«gajiem priekÅ”metiem.
TreÅ”Ä pieeja ir novÄrst nepiecieÅ”amÄ«bu meklÄt. MÄs to darÄm, izmantojot Bloom filtrus vai dzeguzes filtrus. Pirmie sniedz atbildi uzreiz, pasargÄjot jÅ«s no nepiecieÅ”amÄ«bas meklÄt.
PÄdÄjÄ pieeja ir pilnÄ«bÄ izmantot visu jaudu, ko mums sniedz mÅ«sdienu aparatÅ«ra. Tas ir tieÅ”i tas, ko mÄs darÄm bitkartes indeksos. JÄ, tos lietojot, mums dažreiz ir jÄiziet viss rÄdÄ«tÄjs, taÄu mÄs to darÄm ļoti efektÄ«vi.
KÄ jau teicu, datu bÄzes indeksu tÄma ir plaÅ”a un kompromisu pilna. Tas nozÄ«mÄ, ka dažreiz mÄs varam izmantot vairÄkas pieejas vienlaikus: ja mums vÄl vairÄk jÄpaÄtrina meklÄÅ”ana vai ja jÄaptver visi iespÄjamie meklÄÅ”anas veidi.
Å odien es runÄÅ”u par vismazÄk zinÄmo pieeju no tiem - bitkartes indeksiem.
Kas es esmu, lai runÄtu par Å”o tÄmu?
Es strÄdÄju kÄ Badoo komandas vadÄ«tÄjs (iespÄjams, jÅ«s esat vairÄk pazÄ«stams ar citu mÅ«su produktu Bumble). Mums jau ir vairÄk nekÄ 400 miljoni lietotÄju visÄ pasaulÄ un daudzas funkcijas, kas izvÄlas viÅiem piemÄrotÄko. MÄs to darÄm, izmantojot pielÄgotus pakalpojumus, tostarp bitkartes indeksus.
TÄtad, kas ir bitkartes indekss?
Bitkartes indeksi, kÄ norÄda nosaukums, izmanto bitkartes vai bitkopas, lai ieviestu meklÄÅ”anas indeksu. Skatoties no putna lidojuma, Å”is indekss sastÄv no vienas vai vairÄkÄm Å”ÄdÄm bitkartÄm, kas attÄlo jebkuru entÄ«tiju (piemÄram, cilvÄkus) un to Ä«paŔības vai parametrus (vecumu, acu krÄsu utt.), un algoritmu, kas izmanto bitu darbÄ«bas (UN, OR, NOT). ), lai atbildÄtu uz meklÄÅ”anas vaicÄjumu.
Mums ir teikts, ka bitkartes indeksi ir vispiemÄrotÄkie un ļoti efektÄ«vi gadÄ«jumiem, kad tiek veikti meklÄjumi, kuros tiek apvienoti vaicÄjumi daudzÄs zemas kardinalitÄtes kolonnÄs (domÄjiet par "acu krÄsu" vai "Ä£imenes stÄvokli" salÄ«dzinÄjumÄ ar "attÄlumu no pilsÄtas centra"). Bet es parÄdÄ«Å”u vÄlÄk, ka tie lieliski darbojas arÄ« augstas kardinalitÄtes kolonnÄm.
ApskatÄ«sim vienkÄrÅ”Äko bitkartes indeksa piemÄru.
IedomÄjieties, ka mums ir saraksts ar Maskavas restorÄniem ar tÄdÄm binÄrajÄm Ä«paŔībÄm kÄ:
- netÄlu no metro;
- ir privÄta autostÄvvieta;
- ir veranda (ir terase);
- var rezervÄt galdiÅu (pieÅem rezervÄcijas);
- piemÄrots veÄ£etÄrieÅ”iem (draudzÄ«gs vegÄniem);
- dÄrgi (dÄrgi).
PieŔķirsim katram restorÄnam kÄrtas numuru, sÄkot no 0, un atvÄlÄsim atmiÅu 6 bitkartÄm (vienu katram raksturlielumam). PÄc tam mÄs aizpildÄ«sim Ŕīs bitkartes atkarÄ«bÄ no tÄ, vai restorÄnam ir Å”is Ä«paÅ”ums vai nav. Ja 4. restorÄnam ir veranda, bitkartÄ āir verandaā bits Nr. 4 tiks iestatÄ«ts uz 1 (ja nav verandas, tad uz 0).
Tagad mums ir vienkÄrÅ”Äkais iespÄjamais bitkartes indekss, un mÄs varam to izmantot, lai atbildÄtu uz tÄdiem vaicÄjumiem kÄ:
- āRÄdÄ«t man veÄ£etÄrieÅ”iem draudzÄ«gus restorÄnusā;
- "ParÄdiet man lÄtus restorÄnus ar verandu, kur varat rezervÄt galdiÅu."
KÄ? PaskatÄ«simies. Pirmais pieprasÄ«jums ir ļoti vienkÄrÅ”s. Viss, kas mums jÄdara, ir Åemt āveÄ£etÄrieÅ”iem draudzÄ«goā bitkarti un pÄrvÄrst to par restorÄnu sarakstu, kuru fragmenti ir atklÄti.
Otrais pieprasÄ«jums ir nedaudz sarežģītÄks. Mums ir jÄizmanto bitkarte NOT ādÄrgajÄā bitkartÄ, lai iegÅ«tu lÄtu restorÄnu sarakstu, pÄc tam UN tÄ ar bitkarti āvai es varu rezervÄt galdiÅuā un UN rezultÄts ar bitkarti āir verandaā. IegÅ«tajÄ bitkartÄ bÅ«s saraksts ar iestÄdÄm, kas atbilst visiem mÅ«su kritÄrijiem. Å ajÄ piemÄrÄ tas ir tikai Yunost restorÄns.
Ir daudz teoriju, taÄu neuztraucieties, mÄs redzÄsim kodu ļoti drÄ«z.
Kur tiek izmantoti bitkartes indeksi?
Ja jÅ«s Google bitmap indeksus, 90% atbilžu bÅ«s saistÄ«ti ar Oracle DB vienÄ vai otrÄ veidÄ. Bet droÅ”i vien arÄ« citas DBVS atbalsta tik forÅ”u lietu, vai ne? Ne Ä«sti.
IzskatÄ«sim galveno aizdomÄs turamo sarakstu.
MySQL vÄl neatbalsta bitkartes indeksus, taÄu ir priekÅ”likums, kas iesaka pievienot Å”o opciju ().
PostgreSQL neatbalsta bitkartes indeksus, bet izmanto vienkÄrÅ”as bitkartes un bitu darbÄ«bas, lai apvienotu meklÄÅ”anas rezultÄtus vairÄkos citos indeksos.
Tarantool ir bitkopu indeksi un atbalsta vienkÄrÅ”u meklÄÅ”anu tajos.
Redis ir vienkÄrÅ”i bitlauki) bez iespÄjas tos meklÄt.
MongoDB vÄl neatbalsta bitkartes indeksus, taÄu ir arÄ« priekÅ”likums, kas iesaka pievienot Å”o opciju
Elasticsearch iekÅ”Äji izmanto bitkartes).
- Bet mÅ«su mÄjÄ ir parÄdÄ«jies jauns kaimiÅÅ”: Pilosa. Å Ä« ir jauna nerelÄciju datubÄze, kas rakstÄ«ta Go. TajÄ ir tikai bitkartes indeksi un viss tiek balstÄ«ts uz tiem. MÄs par to runÄsim nedaudz vÄlÄk.
IevieŔana Go
Bet kÄpÄc bitkartes indeksi tiek izmantoti tik reti? Pirms atbildÄt uz Å”o jautÄjumu, es vÄlos jums parÄdÄ«t, kÄ programmÄ Go ieviest ļoti vienkÄrÅ”u bitkartes indeksu.
Bitkartes bÅ«tÄ«bÄ ir tikai datu gabali. ProgrammÄ Go Å”im nolÅ«kam izmantosim baitu ŔķÄles.
Mums ir viena bitkarte vienam restorÄna raksturlielumam, un katrs bitkartes bits norÄda, vai konkrÄtam restorÄnam ir Ŕī Ä«paŔība vai nav.
Mums bÅ«s nepiecieÅ”amas divas palÄ«gfunkcijas. Viens tiks izmantots, lai aizpildÄ«tu mÅ«su bitkartes ar nejauÅ”iem datiem. NejauÅ”i, bet ar zinÄmu varbÅ«tÄ«bu, ka restorÄnÄ ir katrs Ä«paÅ”ums. PiemÄram, es uzskatu, ka MaskavÄ ir ļoti maz restorÄnu, kur nevar rezervÄt galdiÅu, un man Ŕķiet, ka aptuveni 20% iestÄžu ir piemÄrotas veÄ£etÄrieÅ”iem.
OtrÄ funkcija pÄrveidos bitkarti restorÄnu sarakstÄ.
Lai atbildÄtu uz vaicÄjumu āRÄdÄ«t man lÄtus restorÄnus, kuriem ir terase un kuros var veikt rezervÄcijasā, mums ir nepiecieÅ”amas divu bitu darbÄ«bas: NOT un UN.
MÄs varam nedaudz vienkÄrÅ”ot savu kodu, izmantojot sarežģītÄku operatoru AND NOT.
Mums ir funkcijas katrai no Ŕīm operÄcijÄm. Abi iziet cauri ŔķÄlÄm, paÅem no katra atbilstoÅ”os elementus, apvieno tos ar bitu darbÄ«bu un ieliek iegÅ«tajÄ Å”Ä·ÄlÄ rezultÄtu.
Un tagad mÄs varam izmantot mÅ«su bitkartes un funkcijas, lai atbildÄtu uz meklÄÅ”anas vaicÄjumu.
VeiktspÄja nav tik augsta, lai gan funkcijas ir ļoti vienkÄrÅ”as un mÄs ietaupÄ«jÄm daudz naudas, neatgriežot jaunu iegÅ«to daļu katru reizi, kad funkcija tika izsaukta.
PÄc nelielas profilÄÅ”anas ar pprof es pamanÄ«ju, ka Go kompilatoram trÅ«kst vienas ļoti vienkÄrÅ”as, bet ļoti svarÄ«gas optimizÄcijas: funkciju iekļauÅ”ana.
Fakts ir tÄds, ka Go kompilators Å”ausmÄ«gi baidÄs no cilpÄm, kas iet cauri ŔķÄlumiem, un kategoriski atsakÄs iekļaut funkcijas, kas satur Å”Ädas cilpas.
Bet es nebaidos un varu apmÄnÄ«t kompilatoru, cilpas vietÄ izmantojot goto, kÄ vecajos labajos laikos.
Un, kÄ redzat, tagad kompilators ar prieku iekļaus mÅ«su funkciju! RezultÄtÄ mums izdodas ietaupÄ«t aptuveni 2 mikrosekundes. Nav slikti!
Otro vÄjo vietu ir viegli pamanÄ«t, rÅ«pÄ«gi aplÅ«kojot montÄžas izvadi. Kompilators pievienoja ŔķÄluma robežu pÄrbaudi tieÅ”i mÅ«su karstÄkajÄ cilpÄ. Fakts ir tÄds, ka Go ir droÅ”a valoda, kompilators baidÄs, ka mani trÄ«s argumenti (trÄ«s ŔķÄles) ir dažÄda izmÄra. Galu galÄ tad teorÄtiski pastÄvÄs tÄ sauktÄ bufera pÄrpildes iespÄjamÄ«ba.
PÄrliecinÄsim kompilatoru, parÄdot, ka visas ŔķÄles ir vienÄda izmÄra. MÄs to varam izdarÄ«t, funkcijas sÄkumÄ pievienojot vienkÄrÅ”u pÄrbaudi.
To redzot, kompilators laimÄ«gi izlaiž pÄrbaudi, un mÄs galu galÄ ietaupÄm vÄl 500 nanosekundes.
Lieli buÄi
Labi, mums izdevÄs izspiest veiktspÄju no mÅ«su vienkÄrÅ”Äs ievieÅ”anas, taÄu Å”is rezultÄts patiesÄ«bÄ ir daudz sliktÄks, nekÄ tas ir iespÄjams ar paÅ”reizÄjo aparatÅ«ru.
MÄs darÄm tikai pamata bitu darbÄ«bas, un mÅ«su procesori tÄs veic ļoti efektÄ«vi. Bet diemžÄl mÄs savu procesoru ābarojamā ar ļoti maziem darbiem. MÅ«su funkcijas veic darbÄ«bas pa baitiem. MÄs varam ļoti viegli pielÄgot savu kodu, lai tas darbotos ar 8 baitu gabaliem, izmantojot UInt64 ŔķÄles.
KÄ redzat, Ŕīs nelielÄs izmaiÅas paÄtrinÄja mÅ«su programmu astoÅas reizes, palielinot partijas lielumu astoÅas reizes. Var teikt, ka ieguvums ir lineÄrs.
IevieÅ”ana montÄtÄjÄ
Bet tas nav beigas. MÅ«su procesori var strÄdÄt ar 16, 32 un pat 64 baitu gabaliem. Å Ädas āplaÅ”asā operÄcijas sauc par vienas instrukcijas vairÄkiem datiem (SIMD; viena instrukcija, daudzi dati), un koda pÄrveidoÅ”anas procesu, lai tas izmantotu Å”Ädas darbÄ«bas, sauc par vektorizÄciju.
DiemžÄl Go kompilators ne tuvu nav izcils vektorizÄcijÄ. PaÅ”laik vienÄ«gais veids, kÄ vektorizÄt Go kodu, ir veikt Ŕīs darbÄ«bas manuÄli, izmantojot Go montÄtÄju.
Go montÄtÄjs ir dÄ«vains zvÄrs. JÅ«s droÅ”i vien zinÄt, ka montÄžas valoda ir ļoti saistÄ«ta ar tÄ datora arhitektÅ«ru, kuram rakstÄt, taÄu tas tÄ nav Go gadÄ«jumÄ. Go assembler ir vairÄk kÄ IRL (starpposma reprezentÄcijas valoda) vai starpvaloda: tÄ ir praktiski neatkarÄ«ga no platformas. Robs Paiks sniedza lielisku sniegumu par Å”o tÄmu pirms vairÄkiem gadiem GopherCon DenverÄ.
TurklÄt Go izmanto neparastu Plan 9 formÄtu, kas atŔķiras no vispÄrpieÅemtajiem AT&T un Intel formÄtiem.
Var droÅ”i teikt, ka rakstÄ«t Go assembler ar roku nav tas jautrÄkais.
Bet, par laimi, jau ir divi augsta lÄ«meÅa rÄ«ki, kas palÄ«dz mums uzrakstÄ«t Go assembler: PeachPy un avo. Abas utilÄ«tas Ä£enerÄ Go montÄtÄju no augstÄka lÄ«meÅa koda, kas rakstÄ«ts attiecÄ«gi Python un Go.
Å Ä«s utilÄ«tas vienkÄrÅ”o tÄdas lietas kÄ reÄ£istru pieŔķirÅ”ana, rakstÄ«Å”anas cilpas un kopumÄ vienkÄrÅ”o procesu, kÄ iekļūt montÄžas programmÄÅ”anas pasaulÄ Go.
MÄs izmantosim avo, tÄpÄc mÅ«su programmas bÅ«s gandrÄ«z parastas Go programmas.
Å Ädi izskatÄs vienkÄrÅ”Äkais avo programmas piemÄrs. Mums ir funkcija main(), kas sevÄ« definÄ Add() funkciju, kuras nozÄ«me ir divu skaitļu pievienoÅ”ana. Å eit ir palÄ«gfunkcijas, lai iegÅ«tu parametrus pÄc nosaukuma un iegÅ«tu kÄdu no bezmaksas un piemÄrotiem procesoru reÄ£istriem. Katrai procesora darbÄ«bai ir atbilstoÅ”a funkcija avo, kÄ redzams ADDQ. Visbeidzot, mÄs redzam palÄ«gfunkciju iegÅ«tÄs vÄrtÄ«bas saglabÄÅ”anai.
Izsaucot go generate, mÄs izpildÄ«sim programmu avo un rezultÄtÄ tiks Ä£enerÄti divi faili:
- add.s ar iegÅ«to kodu Go montÄtÄjÄ;
- stub.go ar funkciju galvenÄm, lai savienotu divas pasaules: Go un assembler.
Tagad, kad esam redzÄjuÅ”i, ko un kÄ dara avo, apskatÄ«sim mÅ«su funkcijas. Es ieviesu gan skalÄrÄs, gan vektora (SIMD) funkciju versijas.
Vispirms apskatÄ«sim skalÄrÄs versijas.
TÄpat kÄ iepriekÅ”ÄjÄ piemÄrÄ, mÄs pieprasÄm bezmaksas un derÄ«gu vispÄrÄjas nozÄ«mes reÄ£istru, mums nav jÄaprÄÄ·ina argumentu nobÄ«des un izmÄri. avo to visu dara mÅ«su vietÄ.
MÄs izmantojÄm etiÄ·etes un goto (vai lÄcienus), lai uzlabotu veiktspÄju un pieviltu Go kompilatoru, bet tagad mÄs to darÄm no paÅ”a sÄkuma. Lieta tÄda, ka cikli ir augstÄka lÄ«meÅa jÄdziens. MontÄtÄjÄ mums ir tikai etiÄ·etes un lÄcieni.
AtlikuÅ”ajam kodam jau vajadzÄtu bÅ«t pazÄ«stamam un saprotamam. MÄs emulÄjam cilpu ar etiÄ·etÄm un lÄcieniem, paÅemam nelielu datu fragmentu no mÅ«su divÄm daļÄm, apvienojam tos ar bitu darbÄ«bu (UN Å”ajÄ gadÄ«jumÄ NE) un pÄc tam ievietojam rezultÄtu iegÅ«tajÄ daļÄ. Visi.
Å Ädi izskatÄs galÄ«gais montÄtÄja kods. Mums nebija jÄaprÄÄ·ina nobÄ«des un izmÄri (izcelti zaÄ¼Ä krÄsÄ) vai jÄseko lÄ«dzi izmantotajiem reÄ£istriem (izcelti sarkanÄ krÄsÄ).
Ja salÄ«dzinÄm montÄžas valodas ievieÅ”anas veiktspÄju ar Go labÄkÄs ievieÅ”anas veiktspÄju, mÄs redzÄsim, ka tÄ ir tÄda pati. Un tas ir gaidÄms. Galu galÄ mÄs neko Ä«paÅ”u nedarÄ«jÄm - mÄs vienkÄrÅ”i reproducÄjÄm to, ko darÄ«tu Go kompilators.
DiemžÄl mÄs nevaram piespiest kompilatoru iekļaut mÅ«su funkcijas, kas rakstÄ«tas montÄžas valodÄ. Go kompilatoram Å”obrÄ«d Å”Ädas iespÄjas nav, lai gan jau labu laiku ir bijis lÅ«gums to pievienot.
TÄpÄc montÄžas valodÄ no mazÄm funkcijÄm nav iespÄjams gÅ«t nekÄdu labumu. Mums ir vai nu jÄraksta lielas funkcijas, vai jÄizmanto jaunÄ matemÄtikas/bitu pakotne, vai arÄ« jÄapiet montÄtÄja valoda.
Tagad apskatīsim mūsu funkciju vektorversijas.
Å ajÄ piemÄrÄ es nolÄmu izmantot AVX2, tÄpÄc mÄs izmantosim darbÄ«bas, kas darbojas ar 32 baitu gabaliem. Koda struktÅ«ra ir ļoti lÄ«dzÄ«ga skalÄrajai versijai: tiek ielÄdÄti parametri, tiek pieprasÄ«ts bezmaksas kopÄ«gs reÄ£istrs utt.
Viens no jauninÄjumiem ir tas, ka plaÅ”ÄkÄs vektoru operÄcijÄs tiek izmantoti Ä«paÅ”i plaÅ”i reÄ£istri. 32 baitu gabalos tie ir reÄ£istri ar prefiksu Y. TÄpÄc kodÄ ir redzama funkcija YMM(). Ja es izmantotu AVX-512 ar 64 bitu gabaliem, prefikss bÅ«tu Z.
Otrs jauninÄjums ir tÄds, ka es nolÄmu izmantot optimizÄciju, ko sauc par cilpas atritinÄÅ”anu, kas nozÄ«mÄ manuÄli veikt astoÅas cilpas darbÄ«bas, pirms pÄriet uz cilpas sÄkumu. Å Ä« optimizÄcija samazina koda filiÄļu skaitu, un to ierobežo pieejamo bezmaksas reÄ£istru skaits.
Nu, kÄ ar sniegumu? ViÅa ir skaista! SalÄ«dzinÄjumÄ ar labÄko Go risinÄjumu mÄs panÄcÄm aptuveni septiÅas reizes lielÄku Ätrumu. IespaidÄ«gi, vai ne?
TaÄu pat Å”o ievieÅ”anu var potenciÄli paÄtrinÄt, vaicÄjumu plÄnotÄjam izmantojot AVX-512, priekÅ”ielÄdÄÅ”anu vai JIT (just-in-time kompilatoru). Bet Ŕī noteikti ir atseviŔķa ziÅojuma tÄma.
ProblÄmas ar bitkartes indeksiem
Tagad, kad esam jau apskatÄ«juÅ”i vienkÄrÅ”u bitkartes indeksa ievieÅ”anu Go un daudz produktÄ«vÄku montÄžas valodÄ, beidzot parunÄsim par to, kÄpÄc bitkartes indeksi tiek izmantoti tik reti.
VecÄki raksti piemin trÄ«s problÄmas ar bitkartes indeksiem, bet jaunÄkos rakstos es apgalvoju, ka tie vairs nav aktuÄli. MÄs neiedziļinÄsimies katrÄ no Ŕīm problÄmÄm, bet aplÅ«kosim tÄs virspusÄji.
Augstas kardinalitÄtes problÄma
TÄtad mums ir teikts, ka bitkartes indeksi ir piemÄroti tikai laukiem ar zemu kardinalitÄti, tas ir, tiem, kuriem ir maz vÄrtÄ«bu (piemÄram, dzimums vai acu krÄsa), un iemesls ir tÄds, ka parastie Å”Ädu lauku attÄlojumi (viens bit per value) augstas kardinalitÄtes gadÄ«jumÄ tas aizÅems pÄrÄk daudz vietas un turklÄt Å”ie bitkartes indeksi tiks slikti (reti) aizpildÄ«ti.
Dažreiz mÄs varam izmantot citu attÄlojumu, piemÄram, standarta, ko izmantojam skaitļu attÄloÅ”anai. Bet tas bija saspieÅ”anas algoritmu parÄdÄ«Å”anÄs, kas mainÄ«ja visu. PÄdÄjo desmitgažu laikÄ zinÄtnieki un pÄtnieki ir izstrÄdÄjuÅ”i lielu skaitu bitkartes saspieÅ”anas algoritmu. To galvenÄ priekÅ”rocÄ«ba ir tÄda, ka nav nepiecieÅ”ams atspiest bitkartes, lai veiktu bitu operÄcijas ā mÄs varam veikt bitu operÄcijas tieÅ”i uz saspiestÄm bitkartÄm.
PÄdÄjÄ laikÄ ir sÄkuÅ”as parÄdÄ«ties hibrÄ«dÄs pieejas, piemÄram, rÅ«coÅ”as bitkartes. Tie vienlaikus izmanto trÄ«s dažÄdus bitkartes attÄlojumus ā paÅ”us bitkartes, masÄ«vus un tÄ sauktos bitu palaiÅ”anas veidus ā un lÄ«dzsvaro starp tiem, lai palielinÄtu veiktspÄju un samazinÄtu atmiÅas patÄriÅu.
PopulÄrÄkajÄs lietojumprogrammÄs varat atrast rÅ«coÅ”as bitkartes. Jau tagad ir milzÄ«gs skaits ievieÅ”anu visdažÄdÄkajÄm programmÄÅ”anas valodÄm, tostarp vairÄk nekÄ trÄ«s ievieÅ”anas Go.
VÄl viena pieeja, kas var mums palÄ«dzÄt tikt galÄ ar augstu kardinalitÄti, tiek saukta par binning. IedomÄjieties, ka jums ir lauks, kas attÄlo cilvÄka augumu. Augstums ir peldoÅ”Ä komata skaitlis, bet mÄs, cilvÄki, par to tÄ nedomÄjam. Mums nav atŔķirÄ«bas starp augumu 185,2 cm un 185,3 cm.
IzrÄdÄs, ka lÄ«dzÄ«gas vÄrtÄ«bas varam sagrupÄt grupÄs 1 cm robežÄs.
Un, ja mÄs zinÄm arÄ« to, ka ļoti maz cilvÄku ir garÄki par 50 cm un garÄki par 250 cm, tad mÄs bÅ«tÄ«bÄ varam pÄrvÄrst lauku ar bezgalÄ«gu kardinalitÄti par lauku, kura kardinalitÄte ir aptuveni 200 vÄrtÄ«bas.
Protams, ja nepiecieÅ”ams, pÄc tam varam veikt papildus filtrÄÅ”anu.
Liela joslas platuma problÄma
NÄkamÄ problÄma ar bitkartes indeksiem ir tÄda, ka to atjauninÄÅ”ana var bÅ«t ļoti dÄrga.
Datu bÄzÄm ir jÄspÄj atjauninÄt datus, kamÄr, iespÄjams, simtiem citu vaicÄjumu meklÄ datus. Mums ir nepiecieÅ”amas slÄdzenes, lai izvairÄ«tos no problÄmÄm ar vienlaicÄ«gu piekļuvi datiem vai citÄm koplietoÅ”anas problÄmÄm. Un kur ir viena liela slÄdzene, tur ir problÄma - slÄdzenes strÄ«ds, kad Ŕī slÄdzene kļūst par pudeli.
Å o problÄmu var atrisinÄt vai apiet, izmantojot sadalÄ«Å”anu vai versiju indeksus.
DalÄ«Å”ana ir vienkÄrÅ”a un labi zinÄma lieta. Varat sadalÄ«t bitkartes indeksu tÄpat kÄ jebkurus citus datus. Vienas lielas slÄdzenes vietÄ jÅ«s iegÅ«sit virkni mazu slÄdzeÅu un tÄdÄjÄdi atbrÄ«vosities no strÄ«diem par slÄdzenÄm.
Otrs veids, kÄ atrisinÄt problÄmu, ir izmantot versiju indeksus. Jums var bÅ«t viena indeksa kopija, ko izmantojat meklÄÅ”anai vai lasÄ«Å”anai, un viena, ko izmantojat rakstÄ«Å”anai vai atjauninÄÅ”anai. Un vienreiz noteiktÄ laika periodÄ (piemÄram, reizi 100 ms vai 500 ms) jÅ«s tos dublÄjat un apmainiet. Protams, Ŕī pieeja ir piemÄrojama tikai gadÄ«jumos, kad jÅ«su lietojumprogramma var apstrÄdÄt nedaudz atpaliekoÅ”u meklÄÅ”anas indeksu.
Šīs divas pieejas var izmantot vienlaikus: jums var būt sadalīts versiju indekss.
SarežģītÄki vaicÄjumi
PÄdÄjÄ problÄma ar bitkartes indeksiem ir tÄda, ka mums tiek teikts, ka tie nav labi piemÄroti sarežģītÄkiem vaicÄjumu veidiem, piemÄram, span vaicÄjumiem.
PatieÅ”Äm, ja tÄ padomÄ, bitu darbÄ«bas, piemÄram, UN, VAI utt., nav Ä«paÅ”i piemÄrotas vaicÄjumiem a la āParÄdÄ«t man viesnÄ«cas ar numuru cenÄm no 200 lÄ«dz 300 dolÄriem par naktiā.
Naivs un ļoti neprÄtÄ«gs risinÄjums bÅ«tu Åemt rezultÄtus katrai dolÄra vÄrtÄ«bai un apvienot tos ar bitwise VAI darbÄ«bu.
Nedaudz labÄks risinÄjums bÅ«tu izmantot grupÄÅ”anu. PiemÄram, grupÄs pa 50 dolÄriem. Tas paÄtrinÄtu mÅ«su procesu 50 reizes.
TaÄu problÄma ir arÄ« viegli atrisinÄma, izmantojot skatu, kas izveidots Ä«paÅ”i Å”Äda veida pieprasÄ«jumam. ZinÄtniskajos rakstos to sauc par diapazonÄ kodÄtÄm bitkartÄm.
Å ajÄ attÄlojumÄ mÄs ne tikai iestatÄm vienu bitu kÄdai vÄrtÄ«bai (piemÄram, 200), bet iestatÄm Å”o vÄrtÄ«bu un visu augstÄku. 200 un vairÄk. Tas pats 300: 300 un vairÄk. Un tÄ tÄlÄk.
Izmantojot Å”o attÄlojumu, mÄs varam atbildÄt uz Å”Äda veida meklÄÅ”anas vaicÄjumu, ŔķÄrsojot indeksu tikai divas reizes. Vispirms mÄs iegÅ«sim sarakstu ar viesnÄ«cÄm, kurÄs numuriÅÅ” maksÄ mazÄk vai 300 USD, un pÄc tam no tÄ izÅemsim tÄs, kurÄs numuriÅa izmaksas ir mazÄkas vai USD 199. Gatavs.
JÅ«s bÅ«siet pÄrsteigts, bet pat Ä£eovaicÄjumi ir iespÄjami, izmantojot bitkartes indeksus. ViltÄ«ba ir izmantot Ä£eometrisku attÄlojumu, kas ieskauj jÅ«su koordinÄtu ar Ä£eometrisku figÅ«ru. PiemÄram, S2 no Google. Ciparu jÄbÅ«t iespÄjai attÄlot trÄ«s vai vairÄku krustojoÅ”u lÄ«niju veidÄ, kuras var numurÄt. TÄdÄ veidÄ mÄs varam pÄrvÄrst savu Ä£eovaicÄjumu vairÄkos vaicÄjumos āgar atstarpiā (pa Ŕīm numurÄtajÄm lÄ«nijÄm).
Gatavi risinÄjumi
Es ceru, ka es jÅ«s nedaudz ieinteresÄju, un tagad jÅ«su arsenÄlÄ ir vÄl viens noderÄ«gs rÄ«ks. Ja jums kÄdreiz bÅ«s jÄdara kaut kas lÄ«dzÄ«gs Å”im, jÅ«s zinÄt, kÄ meklÄt.
TomÄr ne visiem ir laiks, pacietÄ«ba vai resursi, lai izveidotu bitkartes indeksus no nulles. ÄŖpaÅ”i uzlabotas, piemÄram, izmantojot SIMD.
Par laimi, ir vairÄki gatavi risinÄjumi, kas jums palÄ«dzÄs.
RūkojoŔas bitkartes
PirmkÄrt, ir tÄ pati rÅ«coÅ”Ä bitkartes bibliotÄka, par kuru es jau runÄju. TajÄ ir visi nepiecieÅ”amie konteineri un bitu darbÄ«bas, kas jums bÅ«s nepiecieÅ”amas, lai izveidotu pilnvÄrtÄ«gu bitkartes indeksu.
DiemžÄl Å”obrÄ«d neviena no Go implementÄcijÄm neizmanto SIMD, kas nozÄ«mÄ, ka Go implementÄcijas ir mazÄk efektÄ«vas nekÄ, piemÄram, C implementÄcijas.
Pilosa
VÄl viens produkts, kas var jums palÄ«dzÄt, ir Pilosa DBMS, kam faktiski ir tikai bitkartes indeksi. Tas ir salÄ«dzinoÅ”i jauns risinÄjums, taÄu tas ļoti Ätri iekaro cilvÄku sirdis.
Pilosa iekÅ”Äji izmanto rÅ«coÅ”as bitkartes un sniedz jums iespÄju tÄs izmantot, vienkÄrÅ”o un izskaidro visas lietas, par kurÄm es runÄju iepriekÅ”: grupÄÅ”ana, diapazonÄ kodÄtas bitkartes, lauka jÄdziens utt.
ApskatÄ«sim Pilosa izmantoÅ”anas piemÄru, lai atbildÄtu uz jums jau zinÄmu jautÄjumu.
PiemÄrs ir ļoti lÄ«dzÄ«gs tam, ko redzÄjÄt iepriekÅ”. MÄs izveidojam klientu Pilosa serverim, izveidojam indeksu un nepiecieÅ”amos laukus, pÄc tam aizpildÄm savus laukus ar nejauÅ”iem datiem ar varbÅ«tÄ«bÄm un, visbeidzot, izpildÄm pazÄ«stamo vaicÄjumu.
PÄc tam laukÄ "dÄrgs" lietojam NOT, pÄc tam krustojam rezultÄtu (vai UN to) ar lauku "terase" un lauku "rezervÄcijas". Un visbeidzot mÄs iegÅ«stam gala rezultÄtu.
Es ļoti ceru, ka pÄrskatÄmÄ nÄkotnÄ Å”is jaunais indeksa veids parÄdÄ«sies arÄ« tÄdÄs DBVS kÄ MySQL un PostgreSQL - bitkartes indeksos.
SecinÄjums
Ja vÄl neesi aizmigusi, paldies. IerobežotÄ laika dÄļ nÄcÄs Ä«si pieskarties daudzÄm tÄmÄm, taÄu ceru, ka runa bija noderÄ«ga un varbÅ«t pat motivÄjoÅ”a.
Bitkartes indeksus ir labi zinÄt, pat ja jums tie paÅ”laik nav vajadzÄ«gi. Ä»aujiet tiem kļūt par vÄl vienu rÄ«ku jÅ«su rÄ«ku komplektÄ.
MÄs esam apskatÄ«juÅ”i dažÄdus Go veiktspÄjas trikus un lietas, ar kurÄm Go kompilators vÄl netiek galÄ. Bet tas ir absolÅ«ti noderÄ«gi zinÄt ikvienam Go programmÄtÄjam.
Tas ir viss, ko es gribÄju jums pateikt. Paldies!
Avots: www.habr.com