introducció
Vaig donar aquest informe en anglès a la conferència GopherCon Russia 2019 a Moscou i en rus en una trobada a Nizhny Novgorod. Estem parlant d'un índex de mapa de bits, menys comú que l'arbre B, però no menys interessant. Compartint discursos de la conferència en anglès i transcripcions de text en rus.
Veurem com funciona un índex de mapa de bits, quan és millor, quan és pitjor que altres índexs i en quins casos és significativament més ràpid que ells; Vegem quins SGBD populars ja tenen índexs de mapa de bits; Intentem escriure el nostre a Go. I "per a les postres" utilitzarem biblioteques ja fetes per crear la nostra pròpia base de dades especialitzada súper ràpida.
Realment espero que els meus treballs us siguin útils i interessants. Va!
Introducció
Hola a tots! Són les sis de la tarda i estem tots súper cansats. Un bon moment per parlar de l'avorrida teoria de l'índex de bases de dades, oi? No us preocupeu, tindré un parell de línies de codi font aquí i allà. 🙂
Totes les bromes a banda, l'informe està ple d'informació i no tenim gaire temps. Així que comencem.
Avui parlaré del següent:
- què són els índexs;
- què és un índex de mapa de bits;
- on s'utilitza i on NO s'utilitza i per què;
- implementació senzilla a Go i una mica de lluita amb el compilador;
- implementació una mica menys senzilla, però molt més productiva a Go assembler;
- "problemes" dels índexs de mapes de bits;
- implementacions existents.
Aleshores, què són els índexs?
L'índex és una estructura de dades separada que mantenim i actualitzem a més de les dades principals. S'utilitza per accelerar la cerca. Sense índexs, la cerca requeriria passar les dades completament (un procés anomenat exploració completa), i aquest procés té una complexitat algorítmica lineal. Però les bases de dades solen contenir grans quantitats de dades i la complexitat lineal és massa lenta. L'ideal seria obtenir un logarítmic o constant.
Aquest és un tema molt complex, ple de subtileses i intercanvis, però després d'observar dècades de desenvolupament i investigació de bases de dades, estic disposat a dir que només hi ha uns quants enfocaments àmpliament utilitzats per crear índexs de bases de dades.
El primer enfocament és reduir jeràrquicament l'espai de cerca, dividint l'espai de cerca en parts més petites.
Normalment ho fem amb diferents tipus d'arbres. Un exemple seria una caixa gran de materials a l'armari que conté caixes més petites de materials dividides en diferents temes. Si necessiteu materials, probablement els buscareu en un quadre que digui "Materials" en lloc d'un que digui "Cookies", oi?
El segon enfocament és seleccionar immediatament l'element o grup d'elements desitjat. Ho fem en mapes hash o índexs inversos. L'ús de mapes hash és molt semblant a l'exemple anterior, però en lloc d'una caixa de caixes, teniu un munt de caixes petites d'articles finals al vostre armari.
El tercer enfocament és eliminar la necessitat de cercar. Ho fem amb filtres Bloom o filtres cucut. Els primers donen una resposta a l'instant, estalviant-te d'haver de cercar.
L'últim enfocament és aprofitar al màxim tota la potència que ens ofereix el maquinari modern. Això és exactament el que fem als índexs de mapes de bits. Sí, quan les fem servir de vegades necessitem revisar tot l'índex, però ho fem de manera molt eficient.
Com he dit, el tema dels índexs de bases de dades és ampli i ple de compromisos. Això vol dir que de vegades podem utilitzar diversos enfocaments al mateix temps: si necessitem accelerar encara més la cerca, o si hem de cobrir tots els tipus de cerca possibles.
Avui parlaré de l'enfocament menys conegut d'aquests: els índexs de mapa de bits.
Qui sóc jo per parlar d'aquest tema?
Treballo com a responsable d'equip a Badoo (potser estàs més familiaritzat amb el nostre altre producte, Bumble). Ja tenim més de 400 milions d'usuaris a tot el món i moltes funcions que seleccionen la millor coincidència per a ells. Ho fem mitjançant serveis personalitzats, inclosos índexs de mapes de bits.
Aleshores, què és un índex de mapa de bits?
Els índexs de mapes de bits, com el seu nom indica, utilitzen mapes de bits o conjunts de bits per implementar un índex de cerca. Des d'una vista d'ocell, aquest índex consta d'un o més mapes de bits que representen qualsevol entitat (com persones) i les seves propietats o paràmetres (edat, color d'ulls, etc.) i un algorisme que utilitza operacions de bits (AND, O, NO). ) per respondre la consulta de cerca.
Ens diuen que els índexs de mapes de bits són els més adequats i són molt eficients per als casos en què hi ha cerques que combinen consultes a moltes columnes de cardinalitat baixa (penseu en "color dels ulls" o "estat civil" en comparació amb "distància del centre de la ciutat"). Però més endavant mostraré que també funcionen bé per a columnes de cardinalitat alta.
Vegem l'exemple més senzill d'índex de mapa de bits.
Imagineu que tenim una llista de restaurants de Moscou amb propietats binàries com aquestes:
- prop del metro;
- hi ha aparcament privat;
- hi ha un porxo (té terrassa);
- pots reservar taula (accepta reserves);
- apte per a vegetarians (vegan friendly);
- car (car).
Donem a cada restaurant un número de seqüència a partir de 0 i assignem memòria per a 6 mapes de bits (un per cada característica). Després omplirem aquests mapes de bits segons si el restaurant té aquesta propietat o no. Si el restaurant 4 té terrassa, el bit núm. 4 del mapa de bits "té terrassa" s'establirà a 1 (si no hi ha terrassa, llavors a 0).
Ara tenim l'índex de mapa de bits més senzill possible i el podem utilitzar per respondre consultes com:
- "Mostra'm restaurants aptes per a vegetarians";
- "Mostra'm restaurants barats amb un porxo on pots reservar taula".
Com? Fem una ullada. La primera petició és molt senzilla. Tot el que hem de fer és agafar el mapa de bits "vegetarian friendly" i convertir-lo en una llista de restaurants els fragments dels quals estan exposats.
La segona petició és una mica més complicada. Hem d'utilitzar el mapa de bits NOT al mapa de bits "car" per obtenir una llista de restaurants barats, després I amb el mapa de bits "puc reservar una taula" i el resultat amb el mapa de bits "hi ha una terrassa". El mapa de bits resultant contindrà una llista d'establiments que compleixen tots els nostres criteris. En aquest exemple, només és el restaurant Yunost.
Hi ha molta teoria involucrada, però no us preocupeu, veurem el codi molt aviat.
On s'utilitzen els índexs de mapes de bits?
Si feu índexs de mapa de bits de Google, el 90% de les respostes estaran relacionades amb Oracle DB d'una manera o altra. Però probablement altres DBMS també admeten una cosa tan interessant, oi? No realment.
Repassem la llista dels principals sospitosos.
MySQL encara no admet índexs de mapes de bits, però hi ha una proposta que suggereix afegir aquesta opció ().
PostgreSQL no admet índexs de mapes de bits, però utilitza mapes de bits simples i operacions de bits per combinar els resultats de la cerca a través d'altres índexs.
Tarantool té índexs de bits i admet cerques senzilles sobre ells.
Redis té camps de bits simples) sense la possibilitat de cercar-los.
MongoDB encara no admet índexs de mapes de bits, però també hi ha una proposta que suggereix que s'afegeixi aquesta opció.
Elasticsearch utilitza mapes de bits internament).
- Però a casa nostra ha aparegut una nova veïna: la Pilosa. Aquesta és una nova base de dades no relacional escrita a Go. Només conté índexs de mapes de bits i es basa tot en ells. En parlarem una mica més endavant.
Implementació a Go
Però, per què els índexs de mapes de bits s'utilitzen tan poques vegades? Abans de respondre aquesta pregunta, m'agradaria mostrar-vos com implementar un índex de mapa de bits molt senzill a Go.
Els mapes de bits són bàsicament peces de dades. A Go, utilitzem porcions de bytes per a això.
Tenim un mapa de bits per a una característica del restaurant, i cada bit del mapa de bits indica si un restaurant en concret té aquesta propietat o no.
Necessitarem dues funcions auxiliars. Un s'utilitzarà per omplir els nostres mapes de bits amb dades aleatòries. Aleatori, però amb certa probabilitat que el restaurant tingui cada propietat. Per exemple, crec que a Moscou hi ha molt pocs restaurants on no es pugui reservar taula, i em sembla que un 20% dels establiments són aptes per a vegetarians.
La segona funció convertirà el mapa de bits en una llista de restaurants.
Per respondre a la consulta "Mostra'm restaurants barats que tenen un pati i poden fer reserves", necessitem operacions de dos bits: NOT i AND.
Podem simplificar una mica el nostre codi utilitzant l'operador AND NOT més complex.
Tenim funcions per a cadascuna d'aquestes operacions. Tots dos passen per les rodanxes, agafen els elements corresponents de cadascun, combineu-los amb una mica d'operació i poseu el resultat a la rodanxa resultant.
I ara podem utilitzar els nostres mapes de bits i funcions per respondre la consulta de cerca.
El rendiment no és tan alt, tot i que les funcions són molt senzilles i hem estalviat molts diners en no retornar una nova porció resultant cada vegada que es cridava la funció.
Després de fer una mica de perfil amb pprof, em vaig adonar que al compilador Go li faltava una optimització molt senzilla però molt important: la integració de funcions.
El fet és que el compilador Go té molta por dels bucles que passen per seccions i es nega categòricament a les funcions en línia que contenen aquests bucles.
Però no tinc por i puc enganyar el compilador fent servir goto en comptes d'un bucle, com en els bons vells temps.
I, com podeu veure, ara el compilador integrarà amb molt de gust la nostra funció! Com a resultat, aconseguim estalviar uns 2 microsegons. No està malament!
El segon coll d'ampolla és fàcil de veure si observeu de prop la sortida del muntatge. El compilador va afegir una comprovació de límits de porció just dins del nostre bucle més calent. El fet és que Go és un llenguatge segur, el compilador té por que els meus tres arguments (tres rodanxes) siguin de diferents mides. Després de tot, llavors hi haurà una possibilitat teòrica que es produeixi l'anomenat desbordament del buffer.
Tranquil·lem el compilador mostrant-li que totes les rodanxes tenen la mateixa mida. Podem fer-ho afegint una comprovació senzilla al començament de la nostra funció.
En veure això, el compilador s'omet alegrement la comprovació i acabem estalviant 500 nanosegons més.
Grans butxaques
D'acord, hem aconseguit treure una mica de rendiment de la nostra senzilla implementació, però aquest resultat és realment molt pitjor del que és possible amb el maquinari actual.
Tot el que fem són operacions bàsiques de bits i els nostres processadors les realitzen de manera molt eficient. Però, malauradament, "alimentem" el nostre processador amb peces de treball molt petites. Les nostres funcions realitzen operacions byte a byte. Podem ajustar molt fàcilment el nostre codi perquè funcioni amb fragments de 8 bytes mitjançant seccions UInt64.
Com podeu veure, aquest petit canvi va accelerar el nostre programa vuit vegades augmentant la mida del lot vuit vegades. Es pot dir que el guany és lineal.
Implementació en assemblador
Però aquest no és el final. Els nostres processadors poden treballar amb fragments de 16, 32 i fins i tot 64 bytes. Aquestes operacions "àmplies" s'anomenen dades múltiples d'instrucció única (SIMD; una instrucció, moltes dades), i el procés de transformació del codi perquè utilitzi aquestes operacions s'anomena vectorització.
Malauradament, el compilador Go està lluny de ser excel·lent en la vectorització. Actualment, l'única manera de vectoritzar el codi Go és agafar i posar aquestes operacions manualment mitjançant l'assemblador Go.
Go assembler és una bèstia estranya. Probablement ja sabeu que el llenguatge assemblador és una cosa que està molt lligada a l'arquitectura de l'ordinador per al qual esteu escrivint, però aquest no és el cas de Go. Go assembler s'assembla més a un IRL (llenguatge de representació intermedi) o un llenguatge intermedi: pràcticament és independent de la plataforma. Rob Pike va fer una actuació excel·lent sobre aquest tema fa uns quants anys a la GopherCon de Denver.
A més, Go utilitza un format inusual Plan 9, que difereix dels formats generalment acceptats d'AT&T i Intel.
És segur dir que escriure Go assembler a mà no és el més divertit.
Però, afortunadament, ja hi ha dues eines d'alt nivell que ens ajuden a escriure Go assembler: PeachPy i avo. Ambdues utilitats generen assemblador Go a partir de codi de nivell superior escrit en Python i Go, respectivament.
Aquestes utilitats simplifiquen coses com l'assignació de registres, els bucles d'escriptura i, en general, simplifiquen el procés d'entrar al món de la programació d'assemblatges a Go.
Farem servir avo, de manera que els nostres programes seran gairebé programes Go normals.
Així és l'exemple més senzill d'un programa avo. Tenim una funció main(), que defineix en si mateixa la funció Add(), el significat de la qual és sumar dos nombres. Aquí hi ha funcions d'ajuda per obtenir paràmetres pel nom i obtenir un dels registres de processador gratuïts i adequats. Cada operació del processador té una funció corresponent a avo, tal com es veu a ADDQ. Finalment, veiem una funció auxiliar per emmagatzemar el valor resultant.
En cridar go generate, executarem el programa a avo i com a resultat, es generaran dos fitxers:
- add.s amb el codi resultant en Go assembler;
- stub.go amb capçaleres de funcions per connectar els dos mons: Go i assembler.
Ara que hem vist què fa avo i com, mirem les nostres funcions. Vaig implementar versions escalar i vectorial (SIMD) de les funcions.
Vegem primer les versions escalars.
Com en l'exemple anterior, demanem un registre d'ús general gratuït i vàlid, no cal calcular desplaçaments i mides per als arguments. avo fa tot això per nosaltres.
Abans fèiem servir etiquetes i goto (o salts) per millorar el rendiment i enganyar el compilador Go, però ara ho estem fent des del principi. La qüestió és que els cicles són un concepte de nivell superior. En assemblador, només tenim etiquetes i salts.
El codi restant ja hauria de ser familiar i comprensible. Emulem un bucle amb etiquetes i salts, agafem un petit tros de dades dels nostres dos talls, els combinem amb una operació de bits (I NO en aquest cas) i després posem el resultat al tall resultant. Tots.
Aquest és el que sembla el codi assemblador final. No hem hagut de calcular desplaçaments i mides (ressaltats en verd) ni fer un seguiment dels registres utilitzats (ressaltats en vermell).
Si comparem el rendiment de la implementació del llenguatge assemblador amb el rendiment de la millor implementació a Go, veurem que és el mateix. I això s'espera. Després de tot, no vam fer res especial, només vam reproduir el que faria un compilador de Go.
Malauradament, no podem forçar el compilador a integrar les nostres funcions escrites en llenguatge assemblador. El compilador Go actualment no té aquesta característica, tot i que fa temps que hi ha una sol·licitud per afegir-la.
És per això que és impossible obtenir cap benefici de les petites funcions en llenguatge assemblador. Hem d'escriure funcions grans, o utilitzar el nou paquet matemàtic/bits, o passar per alt el llenguatge assemblador.
Vegem ara les versions vectorials de les nostres funcions.
Per a aquest exemple, vaig decidir utilitzar AVX2, de manera que utilitzarem operacions que operen en fragments de 32 bytes. L'estructura del codi és molt semblant a la versió escalar: carregar paràmetres, demanar un registre compartit gratuït, etc.
Una innovació és que les operacions vectorials més àmplies utilitzen registres amples especials. En el cas dels fragments de 32 bytes, aquests són registres amb el prefix Y. És per això que veieu la funció YMM() al codi. Si estigués utilitzant AVX-512 amb fragments de 64 bits, el prefix seria Z.
La segona innovació és que vaig decidir utilitzar una optimització anomenada loop unrolling, que significa fer vuit operacions de bucle manualment abans de saltar al començament del bucle. Aquesta optimització redueix el nombre de sucursals del codi i està limitada pel nombre de registres gratuïts disponibles.
Bé, què passa amb el rendiment? Ella és preciosa! Hem aconseguit una acceleració d'unes set vegades en comparació amb la millor solució Go. Impressionant, oi?
Però fins i tot aquesta implementació es podria accelerar mitjançant l'ús d'AVX-512, la recuperació prèvia o un JIT (compilador just a temps) per al planificador de consultes. Però aquest és sens dubte un tema per a un informe separat.
Problemes amb els índexs de mapes de bits
Ara que ja hem mirat una implementació senzilla d'un índex de mapa de bits a Go i una de molt més productiva en llenguatge ensamblador, finalment parlem de per què els índexs de mapa de bits s'utilitzen tan poques vegades.
Els articles més antics esmenten tres problemes amb els índexs de mapes de bits, però els articles més nous i jo argumentem que ja no són rellevants. No ens aprofundirem en cadascun d'aquests problemes, sinó que els mirarem superficialment.
El problema de l'alta cardinalitat
Així, ens diuen que els índexs de mapa de bits només són adequats per a camps amb poca cardinalitat, és a dir, aquells que tenen pocs valors (per exemple, gènere o color d'ulls), i el motiu és que la representació habitual d'aquests camps (un bit per valor) en el cas d'alta cardinalitat, ocuparà massa espai i, a més, aquests índexs de mapes de bits s'ompliran poc (poques vegades).
De vegades podem utilitzar una representació diferent, com la estàndard que fem servir per representar nombres. Però va ser l'arribada dels algorismes de compressió el que ho va canviar tot. Durant les últimes dècades, científics i investigadors han creat un gran nombre d'algoritmes de compressió per a mapes de bits. El seu principal avantatge és que no cal descomprimir mapes de bits per realitzar operacions de bits: podem realitzar operacions de bits directament sobre mapes de bits comprimits.
Recentment, han començat a aparèixer enfocaments híbrids, com ara mapes de bits rugosos. Utilitzen simultàniament tres representacions diferents per als mapes de bits (maps de bits en si, matrius i les anomenades tirades de bits) i s'equilibren entre elles per maximitzar el rendiment i minimitzar el consum de memòria.
Podeu trobar mapes de bits rugosos a les aplicacions més populars. Ja hi ha un gran nombre d'implementacions per a una gran varietat de llenguatges de programació, incloses més de tres implementacions per a Go.
Un altre enfocament que ens pot ajudar a fer front a l'alta cardinalitat s'anomena binning. Imagineu que teniu un camp que representa l'alçada d'una persona. L'alçada és un nombre de coma flotant, però els humans no ho pensem així. Per a nosaltres no hi ha diferència entre 185,2 cm i 185,3 cm d'alçada.
Resulta que podem agrupar valors similars en grups dins d'1 cm.
I si també sabem que molt poques persones fan menys de 50 cm i més altes que 250 cm, llavors podem convertir un camp amb cardinalitat infinita en un camp amb una cardinalitat d'uns 200 valors.
Per descomptat, si cal, podem fer un filtratge addicional després.
Problema d'ample de banda alt
El següent problema amb els índexs de mapes de bits és que actualitzar-los pot ser molt car.
Les bases de dades han de poder actualitzar les dades mentre potencialment centenars d'altres consultes cerquen les dades. Necessitem bloquejos per evitar problemes amb l'accés a les dades simultània o altres problemes per compartir. I on hi ha un gran bloqueig, hi ha un problema: la contenció de bloqueig, quan aquest bloqueig es converteix en un coll d'ampolla.
Aquest problema es pot resoldre o eludir utilitzant sharding o utilitzant índexs versionats.
La fragmentació és una cosa senzilla i coneguda. Podeu fragmentar un índex de mapa de bits com ho faríeu amb qualsevol altra dada. En lloc d'un pany gran, obtindreu un munt de panys petits i així desfer-vos de la contenció de panys.
La segona manera de resoldre el problema és utilitzar índexs versionats. Podeu tenir una còpia de l'índex que utilitzeu per cercar o llegir, i una altra que utilitzeu per escriure o actualitzar. I una vegada en un període de temps determinat (per exemple, una vegada cada 100 ms o 500 ms) els dupliqueu i els intercanvieu. Per descomptat, aquest enfocament només és aplicable en els casos en què la vostra aplicació pot gestionar un índex de cerca lleugerament retardat.
Aquests dos enfocaments es poden utilitzar simultàniament: podeu tenir un índex versionat fragmentat.
Consultes més complexes
L'últim problema amb els índexs de mapa de bits és que se'ns diu que no s'adapten bé per a tipus de consultes més complexes, com ara consultes d'abast.
De fet, si hi penseu bé, les operacions de bits com AND, OR, etc. no són gaire adequades per a consultes com a "Mostra'm hotels amb tarifes d'habitacions de 200 a 300 dòlars per nit".
Una solució ingènua i molt imprudent seria prendre els resultats per a cada valor en dòlars i combinar-los amb una operació OR per bits.
Una solució una mica millor seria utilitzar l'agrupació. Per exemple, en grups de 50 dòlars. Això acceleraria el nostre procés 50 vegades.
Però el problema també es resol fàcilment utilitzant una vista creada específicament per a aquest tipus de sol·licitud. En els articles científics s'anomena mapes de bits codificats per intervals.
En aquesta representació, no només establim un bit per a algun valor (per exemple, 200), sinó que establim aquest valor i tot més alt. 200 i superiors. El mateix per a 300: 300 i superior. Etcètera.
Utilitzant aquesta representació, podem respondre aquest tipus de consulta de cerca recorrent l'índex només dues vegades. En primer lloc, obtindrem una llista d'hotels on l'habitació costa menys o 300 $, i després en eliminarem aquells on el cost de l'habitació és inferior o 199 $. A punt.
Us sorprendrà, però fins i tot les geoconsultes són possibles mitjançant índexs de mapes de bits. El truc és utilitzar una representació geomètrica que envolta la vostra coordenada amb una figura geomètrica. Per exemple, S2 de Google. La figura s'ha de poder representar en forma de tres o més línies d'intersecció que es puguin numerar. D'aquesta manera podem convertir la nostra geoconsulta en diverses consultes "al llarg del buit" (al llarg d'aquestes línies numerades).
Solucions preparades
Espero haver-te interessat una mica i que ara tinguis una altra eina útil al teu arsenal. Si mai necessiteu fer alguna cosa com aquesta, sabreu de quina manera mirar.
Tanmateix, no tothom té el temps, la paciència o els recursos per crear índexs de mapes de bits des de zero. Sobretot els més avançats, utilitzant SIMD, per exemple.
Afortunadament, hi ha diverses solucions ja fetes per ajudar-vos.
Mapes de bits rugents
En primer lloc, hi ha la mateixa biblioteca de mapes de bits de la qual ja he parlat. Conté tots els contenidors i operacions de bits necessaris que necessitareu per fer un índex de mapa de bits complet.
Malauradament, de moment, cap de les implementacions de Go utilitza SIMD, el que significa que les implementacions de Go tenen menys rendiment que les implementacions C, per exemple.
Pilosa
Un altre producte que us pot ajudar és el SGBD Pilosa, que, de fet, només té índexs de mapa de bits. Aquesta és una solució relativament nova, però està guanyant els cors a gran velocitat.
Pilosa fa servir internament mapes de bits rugosos i et dóna la possibilitat d'utilitzar-los, simplifica i explica tot el que he parlat anteriorment: l'agrupació, els mapes de bits codificats per intervals, el concepte de camp, etc.
Fem una ullada ràpida a un exemple d'ús de Pilosa per respondre una pregunta que ja coneixeu.
L'exemple és molt semblant al que has vist abans. Creem un client al servidor de Pilosa, creem un índex i els camps necessaris, després omplim els nostres camps amb dades aleatòries amb probabilitats i, finalment, executem la consulta familiar.
Després d'això, utilitzem NOT al camp "car", i després tallem el resultat (o AND) amb el camp "terrassa" i amb el camp "reserves". I finalment, obtenim el resultat final.
Realment espero que en un futur previsible aquest nou tipus d'índex també aparegui en DBMS com MySQL i PostgreSQL - índexs de mapa de bits.
Conclusió
Si encara no t'has adormit, gràcies. Vaig haver de tocar breument molts temes a causa del temps limitat, però espero que la xerrada hagi estat útil i potser fins i tot motivadora.
És bo conèixer els índexs de mapes de bits, encara que no els necessiteu ara mateix. Deixa que siguin una altra eina a la teva caixa d'eines.
Hem analitzat diversos trucs de rendiment per a Go i coses que el compilador de Go encara no gestiona gaire bé. Però això és absolutament útil per a tots els programadors de Go.
Això és tot el que et volia dir. Gràcies!
Font: www.habr.com