introdución
Dei este informe en inglés na conferencia GopherCon Russia 2019 en Moscova e en ruso nunha reunión en Nizhny Novgorod. Estamos a falar dun índice de mapa de bits, menos común que a árbore B, pero non menos interesante. Compartindo discursos na conferencia en inglés e transcricións de textos en ruso.
Observaremos como funciona un índice de mapa de bits, cando é mellor, cando é peor que outros índices e en que casos é significativamente máis rápido que eles; Vexamos que DBMS populares xa teñen índices de mapas de bits; Imos tentar escribir o noso en Go. E "de sobremesa" usaremos bibliotecas preparadas para crear a nosa propia base de datos especializada superrápida.
Realmente espero que os meus traballos vos sexan útiles e interesantes. Vaia!
Introdución
Ola a todos! Son as seis da noite e estamos todos super cansos. Bo tempo para falar sobre a aburrida teoría do índice de bases de datos, non? Non te preocupes, vou ter un par de liñas de código fonte aquí e alí. 🙂
Todas as bromas aparte, o informe está cheo de información e non temos moito tempo. Entón, imos comezar.
Hoxe falarei do seguinte:
- que son os índices;
- que é un índice de mapa de bits;
- onde se usa e onde NON se usa e por que;
- implementación sinxela en Go e un pouco de loita co compilador;
- implementación un pouco menos sinxela, pero moito máis produtiva en Go assembler;
- "problemas" dos índices de mapas de bits;
- implementacións existentes.
Entón, que son os índices?
O índice é unha estrutura de datos separada que mantemos e actualizamos ademais dos datos principais. Úsase para acelerar a busca. Sen índices, a busca requiriría pasar por completo os datos (un proceso chamado exploración completa), e este proceso ten unha complexidade algorítmica lineal. Pero as bases de datos normalmente conteñen grandes cantidades de datos e a complexidade lineal é demasiado lenta. O ideal sería obter un logarítmico ou constante.
Este é un tema moi complexo, cheo de sutilezas e compensacións, pero despois de mirar décadas de desenvolvemento e investigación de bases de datos, estou disposto a dicir que só hai algúns enfoques moi utilizados para crear índices de bases de datos.
O primeiro enfoque é reducir xerarquicamente o espazo de busca, dividindo o espazo de busca en partes máis pequenas.
Adoitamos facelo usando diferentes tipos de árbores. Un exemplo sería unha caixa grande de materiais no teu armario que conteña caixas máis pequenas de materiais divididas en diferentes temas. Se necesitas materiais, probablemente os busques nunha caixa que di "Materiais" en lugar de "Cookies", non?
O segundo enfoque é seleccionar inmediatamente o elemento ou grupo de elementos desexado. Facemos isto en mapas hash ou índices inversos. Usar mapas hash é moi semellante ao exemplo anterior, pero en lugar dunha caixa de caixas, tes un montón de caixas pequenas de artigos finais no teu armario.
O terceiro enfoque é eliminar a necesidade de buscar. Facemos isto usando filtros Bloom ou filtros cuco. Os primeiros dan resposta ao instante, evitando que teñas que buscar.
O último enfoque é aproveitar ao máximo todo o poder que nos proporciona o hardware moderno. Isto é exactamente o que facemos nos índices de mapas de bits. Si, cando os usamos ás veces necesitamos revisar todo o índice, pero facémolo de forma moi eficiente.
Como dixen, o tema dos índices de bases de datos é amplo e cheo de compromisos. Isto significa que ás veces podemos utilizar varios enfoques ao mesmo tempo: se precisamos acelerar aínda máis a busca ou se necesitamos cubrir todos os tipos de busca posibles.
Hoxe falarei do enfoque menos coñecido destes: índices de mapas de bits.
Quen son eu para falar deste tema?
Traballo como xefe de equipo en Badoo (quizais estea máis familiarizado co noso outro produto, Bumble). Xa temos máis de 400 millóns de usuarios en todo o mundo e moitas funcións que seleccionan a mellor opción para eles. Facemos isto mediante servizos personalizados, incluídos índices de mapas de bits.
Entón, que é un índice de mapa de bits?
Os índices de mapas de bits, como o nome indica, usan mapas de bits ou conxuntos de bits para implementar un índice de busca. Desde a vista de paxaro, este índice consta dun ou máis mapas de bits que representan calquera entidade (como persoas) e as súas propiedades ou parámetros (idade, cor dos ollos, etc.) e un algoritmo que utiliza operacións de bits (AND, OU, NON). ) para responder á consulta de busca.
Dinos que os índices de mapas de bits son os máis axeitados e son moi eficaces para os casos nos que hai buscas que combinan consultas en moitas columnas de cardinalidade baixa (pense en "cor dos ollos" ou "estado civil" fronte a algo así como "distancia do centro da cidade"). Pero mostrarei máis tarde que tamén funcionan ben para columnas de cardinalidade alta.
Vexamos o exemplo máis sinxelo dun índice de mapa de bits.
Imaxina que temos unha lista de restaurantes de Moscova con propiedades binarias como estas:
- preto do metro;
- hai aparcamento privado;
- hai unha terraza (ten terraza);
- podes reservar mesa (acepta reservas);
- adecuado para vexetarianos (vegan friendly);
- caro (caro).
Dámoslle a cada restaurante un número de secuencia a partir de 0 e asignemos memoria para 6 mapas de bits (un por cada característica). Despois encheremos estes mapas de bits dependendo de se o restaurante ten esta propiedade ou non. Se o restaurante 4 ten unha terraza, o bit número 4 do mapa de bits "ten unha terraza" establecerase en 1 (se non hai terraza, entón a 0).
Agora temos o índice de mapa de bits máis sinxelo posible e podemos usalo para responder a consultas como:
- "Amosame restaurantes vexetarianos";
- "Amosame restaurantes baratos cunha terraza onde podes reservar mesa".
Como? Imos botarlle unha ollada. A primeira solicitude é moi sinxela. Todo o que temos que facer é tomar o mapa de bits "vexetariano" e convertelo nunha lista de restaurantes cuxos anacos están expostos.
A segunda solicitude é un pouco máis complicada. Necesitamos usar o mapa de bits NOT no mapa de bits "caro" para obter unha lista de restaurantes baratos, despois AND co mapa de bits "podo reservar unha mesa" e o resultado co mapa de bits "hai unha terraza". O mapa de bits resultante conterá unha lista de establecementos que cumpren todos os nosos criterios. Neste exemplo, este é só o restaurante Yunost.
Hai moita teoría implicada, pero non te preocupes, veremos o código moi pronto.
Onde se usan os índices de mapas de bits?
Se Google indexa mapas de bits, o 90% das respostas estarán relacionadas con Oracle DB dun xeito ou doutro. Pero outros DBMS probablemente tamén admitan unha cousa tan interesante, non? En realidade non.
Imos repasar a lista dos principais sospeitosos.
MySQL aínda non admite índices de mapas de bits, pero hai unha proposta que suxire engadir esta opción ().
PostgreSQL non admite índices de mapas de bits, pero usa mapas de bits sinxelos e operacións de bits para combinar os resultados da busca en varios outros índices.
Tarantool ten índices de conxunto de bits e admite buscas sinxelas neles.
Redis ten campos de bits sinxelos) sen a posibilidade de buscalos.
MongoDB aínda non admite índices de mapas de bits, pero tamén hai unha proposta que suxire que se engada esta opción
Elasticsearch usa mapas de bits internamente).
- Pero na nosa casa apareceu unha nova veciña: Pilosa. Esta é unha nova base de datos non relacional escrita en Go. Contén só índices de mapas de bits e basea todo neles. Falarémolo un pouco máis tarde.
Implementación en Go
Pero por que se usan tan raramente os índices de mapas de bits? Antes de responder a esta pregunta, gustaríame mostrarche como implementar un índice de mapa de bits moi sinxelo en Go.
Os mapas de bits son esencialmente só anacos de datos. En Go, usemos porcións de bytes para iso.
Temos un mapa de bits para unha característica do restaurante e cada bit do mapa de bits indica se un determinado restaurante ten esta propiedade ou non.
Necesitaremos dúas funcións auxiliares. Usarase un para encher os nosos mapas de bits con datos aleatorios. Aleatorio, pero con certa probabilidade de que o restaurante teña cada propiedade. Por exemplo, creo que hai moi poucos restaurantes en Moscova onde non se pode reservar mesa, e paréceme que preto do 20% dos establecementos son aptos para vexetarianos.
A segunda función converterá o mapa de bits nunha lista de restaurantes.
Para responder á pregunta "Móstrame restaurantes baratos que teñan patio e poidan facer reservas", necesitamos dúas operacións de bit: NOT e AND.
Podemos simplificar un pouco o noso código usando o operador AND NOT máis complexo.
Temos funcións para cada unha destas operacións. Ambos os dous pasan polas rebandas, collen os elementos correspondentes de cada un, combínaos cunha operación de bits e pon o resultado na rebanada resultante.
E agora podemos usar os nosos mapas de bits e funcións para responder á consulta de busca.
O rendemento non é tan alto, aínda que as funcións son moi sinxelas e aforramos moito diñeiro ao non devolver unha nova porción resultante cada vez que se chamaba a función.
Despois de facer un pouco de perfís con pprof, notei que ao compilador Go faltaba unha optimización moi sinxela pero moi importante: a función integrada.
O feito é que o compilador Go ten moito medo aos bucles que pasan por porcións e rexeita categoricamente as funcións en liña que conteñan tales bucles.
Pero non teño medo e podo enganar ao compilador usando goto en lugar dun bucle, como nos bos tempos.
E, como podes ver, agora o compilador integrará con gusto a nosa función! Como resultado, conseguimos aforrar uns 2 microsegundos. Non está mal!
O segundo pescozo de botella é fácil de ver se observas atentamente a saída da montaxe. O compilador engadiu unha comprobación de límites de porción xusto dentro do noso bucle máis quente. O caso é que Go é unha linguaxe segura, o compilador ten medo de que os meus tres argumentos (tres porcións) sexan de tamaños diferentes. Despois de todo, entón haberá unha posibilidade teórica de que se produza un chamado desbordamento do buffer.
Imos tranquilizar ao compilador mostrándolle que todas as porcións teñen o mesmo tamaño. Podemos facelo engadindo unha comprobación sinxela ao comezo da nosa función.
Vendo isto, o compilador omite felizmente a comprobación e acabamos aforrando outros 500 nanosegundos.
Grandes carnicerías
Está ben, conseguimos espremer algo de rendemento da nosa sinxela implementación, pero este resultado é en realidade moito peor do que é posible co hardware actual.
Todo o que facemos son operacións básicas de bits, e os nosos procesadores realízanas de forma moi eficiente. Pero, por desgraza, "alimentamos" o noso procesador con pezas de traballo moi pequenas. As nosas funcións realizan operacións byte por byte. Podemos axustar moi facilmente o noso código para que funcione con anacos de 8 bytes usando porcións UInt64.
Como podes ver, este pequeno cambio acelerou o noso programa oito veces ao aumentar o tamaño do lote en oito veces. Pódese dicir que a ganancia é lineal.
Implementación en ensamblador
Pero este non é o final. Os nosos procesadores poden traballar con anacos de 16, 32 e ata 64 bytes. Esas operacións "amplas" chámanse datos múltiples de instrución única (SIMD; unha instrución, moitos datos) e o proceso de transformación do código para que utilice tales operacións chámase vectorización.
Desafortunadamente, o compilador Go está lonxe de ser excelente na vectorización. Actualmente, a única forma de vectorizar o código Go é tomar e poñer estas operacións manualmente usando o ensamblador Go.
Go assembler é unha estraña besta. Probablemente saibas que a linguaxe ensambladora é algo que está moi ligado á arquitectura do ordenador para o que estás escribindo, pero ese non é o caso de Go. Go assembler é máis parecido a un IRL (linguaxe de representación intermedia) ou unha linguaxe intermedia: é practicamente independente da plataforma. Rob Pike deu unha excelente actuación sobre este tema hai varios anos na GopherCon de Denver.
Ademais, Go usa un formato Plan 9 inusual, que é diferente dos formatos AT&T e Intel xeralmente aceptados.
É seguro dicir que escribir Go assembler a man non é o máis divertido.
Pero, afortunadamente, xa hai dúas ferramentas de alto nivel que nos axudan a escribir Go assembler: PeachPy e avo. Ambas as dúas utilidades xeran o ensamblador Go a partir de código de nivel superior escrito en Python e Go, respectivamente.
Estas utilidades simplifican cousas como a asignación de rexistros, os bucles de escritura e, en xeral, simplifican o proceso de entrar no mundo da programación de montaxes en Go.
Usaremos avo, polo que os nosos programas serán programas Go case normais.
Este é o exemplo máis sinxelo dun programa avo. Temos unha función main(), que define dentro de si a función Engadir(), cuxo significado é sumar dous números. Aquí hai funcións auxiliares para obter parámetros polo nome e obter un dos rexistros de procesador gratuítos e axeitados. Cada operación do procesador ten unha función correspondente en avo, como se ve en ADDQ. Finalmente, vemos unha función auxiliar para almacenar o valor resultante.
Ao chamar a go generate, executaremos o programa en avo e, como resultado, xeraranse dous ficheiros:
- add.s co código resultante no ensamblador Go;
- stub.go con cabeceiras de funcións para conectar os dous mundos: Go e assembler.
Agora que vimos o que fai avo e como, vexamos as nosas funcións. Implementei versións escalares e vectoriales (SIMD) das funcións.
Vexamos primeiro as versións escalares.
Como no exemplo anterior, estamos pedindo un rexistro de propósito xeral gratuíto e válido, non necesitamos calcular compensacións e tamaños para os argumentos. avo fai todo isto por nós.
Antes usabamos etiquetas e goto (ou saltos) para mellorar o rendemento e enganar o compilador Go, pero agora facémolo desde o principio. A cuestión é que os ciclos son un concepto de nivel superior. En assembler, só temos etiquetas e saltos.
O código restante xa debería ser familiar e comprensible. Emulamos un bucle con etiquetas e saltos, tomamos un pequeno dato das nosas dúas porcións, combinámolas cunha operación de bits (E NON neste caso) e despois poñemos o resultado na porción resultante. Todos.
Este é o aspecto do código ensamblador final. Non tivemos que calcular compensacións e tamaños (resaltados en verde) nin facer un seguimento dos rexistros utilizados (resaltados en vermello).
Se comparamos o rendemento da implementación da linguaxe ensambladora co rendemento da mellor implementación en Go, veremos que é o mesmo. E isto é de esperar. Despois de todo, non fixemos nada especial, só reproducimos o que faría un compilador de Go.
Desafortunadamente, non podemos obrigar ao compilador a incorporar as nosas funcións escritas en linguaxe ensamblador. O compilador Go non dispón actualmente desta función, aínda que hai tempo que hai unha solicitude para engadila.
É por iso que é imposible sacar proveito de pequenas funcións en linguaxe ensamblador. Necesitamos escribir funcións grandes, ou usar o novo paquete math/bits, ou ignorar a linguaxe ensambladora.
Vexamos agora as versións vectoriais das nosas funcións.
Para este exemplo, decidín usar AVX2, polo que usaremos operacións que operen en anacos de 32 bytes. A estrutura do código é moi semellante á versión escalar: carga de parámetros, solicitude de rexistro compartido gratuíto, etc.
Unha innovación é que as operacións vectoriais máis amplas usan rexistros anchos especiais. No caso dos fragmentos de 32 bytes, estes son rexistros co prefixo Y. É por iso que ve a función YMM() no código. Se estivese usando AVX-512 con anacos de 64 bits, o prefixo sería Z.
A segunda innovación é que decidín usar unha optimización chamada loop unrolling, o que significa facer oito operacións de bucle manualmente antes de saltar ó comezo do bucle. Esta optimización reduce o número de ramas no código, e está limitada polo número de rexistros gratuítos dispoñibles.
Ben, e o rendemento? Ela é fermosa! Conseguimos unha aceleración dunhas sete veces en comparación coa mellor solución Go. Impresionante, non?
Pero incluso esta implementación podería acelerarse usando AVX-512, a captación previa ou un JIT (compilador just-in-time) para o planificador de consultas. Pero este é certamente un tema para un informe separado.
Problemas cos índices de mapas de bits
Agora que xa analizamos unha implementación sinxela dun índice de mapas de bits en Go e outro moito máis produtivo en linguaxe ensamblador, imos finalmente falar de por que os índices de mapas de bits se usan tan raramente.
Os artigos máis antigos mencionan tres problemas cos índices de mapas de bits, pero os artigos máis novos e eu argumento que xa non son relevantes. Non mergullaremos profundamente en cada un destes problemas, senón que os analizaremos superficialmente.
O problema da alta cardinalidade
Entón, dinnos que os índices de mapas de bits só son axeitados para campos con baixa cardinalidade, é dicir, aqueles que teñen poucos valores (por exemplo, xénero ou cor dos ollos), e a razón é que a representación habitual destes campos (unha bit por valor) no caso de cardinalidade alta, ocupará demasiado espazo e, ademais, estes índices de mapas de bits estarán mal (raramente) cubertos.
Ás veces podemos usar unha representación diferente, como a estándar que usamos para representar números. Pero foi a chegada dos algoritmos de compresión o que cambiou todo. Durante as últimas décadas, científicos e investigadores crearon un gran número de algoritmos de compresión para mapas de bits. A súa principal vantaxe é que non hai necesidade de descomprimir mapas de bits para realizar operacións de bits; podemos realizar operacións de bits directamente sobre mapas de bits comprimidos.
Recentemente, comezaron a aparecer enfoques híbridos, como mapas de bits rugidos. Usan simultáneamente tres representacións diferentes para mapas de bits (mapas de bits en si, matrices e as chamadas execucións de bits) e equilibran entre elas para maximizar o rendemento e minimizar o consumo de memoria.
Podes atopar mapas de bits rugidos nas aplicacións máis populares. Xa hai un gran número de implementacións para unha gran variedade de linguaxes de programación, incluíndo máis de tres implementacións para Go.
Outro enfoque que pode axudarnos a tratar con alta cardinalidade chámase binning. Imaxina que tes un campo que representa a altura dunha persoa. A altura é un número de coma flotante, pero os humanos non o pensamos así. Para nós non hai diferenza entre a altura 185,2 cm e 185,3 cm.
Resulta que podemos agrupar valores similares en grupos dentro de 1 cm.
E se tamén sabemos que moi poucas persoas miden menos de 50 cm e miden máis de 250 cm, entón podemos converter esencialmente un campo con cardinalidade infinita nun campo cunha cardinalidade duns 200 valores.
Por suposto, se é necesario, podemos facer un filtrado adicional despois.
Problema de ancho de banda alto
O seguinte problema cos índices de mapas de bits é que actualizalos pode ser moi caro.
As bases de datos deben ser capaces de actualizar os datos mentres centos de outras consultas están a buscar nos datos. Necesitamos bloqueos para evitar problemas co acceso simultáneo aos datos ou outros problemas de uso compartido. E onde hai un bloqueo grande, hai un problema: a disputa do bloqueo, cando este bloqueo se converte nun pescozo de botella.
Este problema pódese resolver ou eludir mediante o uso de fragmentos ou índices versionados.
A fragmentación é unha cousa sinxela e coñecida. Podes fragmentar un índice de mapa de bits como farías con calquera outro dato. En lugar dun bloqueo grande, obterás un montón de peches pequenos e, así, desfacerase da contención de bloqueo.
A segunda forma de resolver o problema é utilizar índices versionados. Podes ter unha copia do índice que utilizas para buscar ou ler, e outra que usas para escribir ou actualizar. E unha vez nun determinado período de tempo (por exemplo, unha vez cada 100 ms ou 500 ms) duplícaos e intercámbias. Por suposto, este enfoque só é aplicable nos casos nos que a súa aplicación pode xestionar un índice de busca lixeiramente atrasado.
Estes dous enfoques pódense usar simultaneamente: pode ter un índice con versión fragmentada.
Consultas máis complexas
O problema final cos índices de mapas de bits é que se nos di que non son moi axeitados para tipos de consultas máis complexas, como consultas de span.
De feito, se o pensas ben, as operacións de bits como AND, OR, etc. non son moi adecuadas para consultas como "Mostrame hoteis con tarifas de habitación de 200 a 300 dólares por noite".
Unha solución inxenua e moi imprudente sería tomar os resultados para cada valor en dólares e combinalos cunha operación OR bit a bit.
Unha solución un pouco mellor sería utilizar o agrupamento. Por exemplo, en grupos de 50 dólares. Isto aceleraría o noso proceso 50 veces.
Pero o problema tamén se soluciona facilmente utilizando unha vista creada especificamente para este tipo de solicitudes. Nos artigos científicos chámase mapas de bits codificados por intervalos.
Nesta representación, non só establecemos un bit para algún valor (por exemplo, 200), senón que establecemos este valor e todo máis alto. 200 e superiores. O mesmo para 300: 300 e superior. Etcétera.
Usando esta representación, podemos responder a este tipo de consulta de busca atravesando o índice só dúas veces. En primeiro lugar, obteremos unha lista de hoteis nos que a habitación custa menos ou 300 dólares e, a continuación, eliminaremos da mesma aqueles nos que o custo da habitación sexa inferior ou 199 dólares. Listo.
Sorprenderás, pero incluso as xeoconsultas son posibles usando índices de mapas de bits. O truco é usar unha representación xeométrica que envolve a túa coordenada cunha figura xeométrica. Por exemplo, S2 de Google. A figura debe poder representarse en forma de tres ou máis liñas de corte que se poidan numerar. Deste xeito, podemos converter a nosa xeoconsulta en varias consultas "ao longo da brecha" (ao longo destas liñas numeradas).
Solucións chave en man
Espero que che interese un pouco e que agora teñas outra ferramenta útil no teu arsenal. Se algunha vez necesitas facer algo así, saberás de que xeito buscar.
Non obstante, non todos teñen tempo, paciencia ou recursos para crear índices de mapas de bits desde cero. Especialmente os máis avanzados, usando SIMD, por exemplo.
Afortunadamente, hai varias solucións preparadas para axudarche.
Mapas de bits rugidos
En primeiro lugar, está a mesma biblioteca de mapas de bits da que xa falei. Contén todos os contedores e operacións de bits necesarios para facer un índice de mapa de bits completo.
Desafortunadamente, polo momento, ningunha das implementacións de Go usa SIMD, o que significa que as implementacións de Go teñen menos rendemento que as implementacións de C, por exemplo.
Pilosa
Outro produto que pode axudarche é o DBMS Pilosa, que, de feito, só ten índices de mapas de bits. Esta é unha solución relativamente nova, pero está a gañar corazóns a gran velocidade.
Pilosa utiliza mapas de bits rugidos internamente e dáche a posibilidade de utilizalos, simplifica e explica todo o que falei anteriormente: agrupación, mapas de bits codificados por intervalos, o concepto de campo, etc.
Vexamos un exemplo de uso de Pilosa para responder a unha pregunta que xa coñeces.
O exemplo é moi parecido ao que viches antes. Creamos un cliente para o servidor de Pilosa, creamos un índice e os campos necesarios, despois enchemos os nosos campos con datos aleatorios con probabilidades e, finalmente, executamos a consulta familiar.
Despois diso, usamos NOT no campo "caro", despois cruzamos o resultado (ou AND) co campo "terraza" e co campo "reservas". E por último, temos o resultado final.
Realmente espero que nun futuro previsible este novo tipo de índice apareza tamén en DBMS como MySQL e PostgreSQL - índices de mapas de bits.
Conclusión
Se aínda non durmiches, grazas. Tiven que tocar brevemente moitos temas debido ao tempo limitado, pero espero que a charla fose útil e quizais mesmo motivadora.
É bo coñecer os índices de mapas de bits, aínda que non os necesites agora mesmo. Deixa que sexan outra ferramenta da túa caixa de ferramentas.
Analizamos varios trucos de rendemento para Go e cousas que o compilador Go aínda non manexa moi ben. Pero isto é absolutamente útil para que todos os programadores de Go o saiban.
Iso é todo o que quería dicirche. Grazas!
Fonte: www.habr.com