discurso de apertura
Di este informe en inglés en la conferencia GopherCon Rusia 2019 en Moscú y en ruso en una reunión en Nizhny Novgorod. Estamos hablando de un índice de mapa de bits, menos común que el árbol B, pero no menos interesante. Intercambio discursos en la conferencia en inglés y transcripciones de textos en ruso.
Veremos cómo funciona un índice de mapa de bits, cuándo es mejor, cuándo es peor que otros índices y en qué casos es significativamente más rápido que ellos; Veamos qué DBMS populares ya tienen índices de mapa de bits; Intentemos escribir el nuestro en Go. Y “de postre” usaremos bibliotecas ya preparadas para crear nuestra propia base de datos especializada súper rápida.
Realmente espero que mis trabajos sean útiles e interesantes para ti. ¡Ir!
introducción
¡Hola a todos! Son las seis de la tarde y todos estamos muy cansados. Buen momento para hablar sobre la aburrida teoría del índice de bases de datos, ¿verdad? No te preocupes, tendré un par de líneas de código fuente aquí y allá. 🙂
Bromas aparte, el informe está repleto de información y no tenemos mucho tiempo. Entonces empecemos.
Hoy hablaré de lo siguiente:
- ¿Qué son los índices?
- ¿Qué es un índice de mapa de bits?
- dónde se usa y dónde NO se usa y por qué;
- implementación simple en Go y un poco de dificultad con el compilador;
- implementación un poco menos simple, pero mucho más productiva en Go Assamler;
- “problemas” de índices de mapas de bits;
- implementaciones existentes.
Entonces, ¿qué son los índices?
El índice es una estructura de datos separada que mantenemos y actualizamos además de los datos principales. Se utiliza para acelerar la búsqueda. Sin índices, la búsqueda requeriría revisar los datos por completo (un proceso llamado escaneo completo), y este proceso tiene una complejidad algorítmica lineal. Pero las bases de datos suelen contener enormes cantidades de datos y la complejidad lineal es demasiado lenta. Lo ideal sería obtener uno logarítmico o constante.
Este es un tema enormemente complejo, lleno de sutilezas y compensaciones, pero después de analizar décadas de desarrollo e investigación de bases de datos, estoy dispuesto a decir que sólo existen unos pocos enfoques ampliamente utilizados para crear índices de bases de datos.
El primer enfoque consiste en reducir jerárquicamente el espacio de búsqueda, dividiendo el espacio de búsqueda en partes más pequeñas.
Normalmente hacemos esto usando diferentes tipos de árboles. Un ejemplo sería una caja grande de materiales en tu armario que contiene cajas más pequeñas de materiales divididas en diferentes temas. Si necesitas materiales, probablemente los buscarás en un cuadro que dice "Materiales" en lugar de uno que dice "Cookies", ¿verdad?
El segundo enfoque consiste en seleccionar inmediatamente el elemento o grupo de elementos deseado. Hacemos esto en mapas hash o índices inversos. Usar mapas hash es muy similar al ejemplo anterior, pero en lugar de una caja de cajas, tienes un montón de pequeñas cajas de artículos finales en tu armario.
El tercer enfoque es eliminar la necesidad de realizar búsquedas. Hacemos esto usando filtros Bloom o filtros cuco. Los primeros dan respuesta al instante, ahorrándote tener que buscar.
El último enfoque es aprovechar al máximo toda la potencia que nos brinda el hardware moderno. Esto es exactamente lo que hacemos en los índices de mapas de bits. Sí, al usarlos a veces necesitamos revisar todo el índice, pero lo hacemos de manera súper eficiente.
Como dije, el tema de los índices de bases de datos es amplio y está lleno de compromisos. Esto hace que en ocasiones podamos utilizar varios enfoques al mismo tiempo: si necesitamos acelerar aún más la búsqueda, o si necesitamos abarcar todos los tipos de búsqueda posibles.
Hoy hablaré sobre el enfoque menos conocido de estos: los índices de mapas de bits.
¿Quién soy yo para hablar de este tema?
Trabajo como líder de equipo en Badoo (quizás estés más familiarizado con nuestro otro producto, Bumble). Ya tenemos más de 400 millones de usuarios en todo el mundo y muchas funciones que seleccionan la mejor opción para ellos. Hacemos esto utilizando servicios personalizados, incluidos índices de mapas de bits.
Entonces, ¿qué es un índice de mapa de bits?
Los índices de mapas de bits, como su nombre indica, utilizan mapas de bits o conjuntos de bits para implementar un índice de búsqueda. A vista de pájaro, este índice consta de uno o más mapas de bits que representan entidades (como personas) y sus propiedades o parámetros (edad, color de ojos, etc.) y un algoritmo que utiliza operaciones de bits (Y, O, NO ) para responder a la consulta de búsqueda.
Se nos dice que los índices de mapa de bits son los más adecuados y tienen un gran rendimiento para los casos en los que hay búsquedas que combinan consultas en muchas columnas de baja cardinalidad (piense en "color de ojos" o "estado civil" frente a algo como "distancia del centro de la ciudad"). Pero más adelante mostraré que también funcionan bien para columnas de alta cardinalidad.
Veamos el ejemplo más simple de un índice de mapa de bits.
Imaginemos que tenemos una lista de restaurantes de Moscú con propiedades binarias como estas:
- cerca del metro;
- hay aparcamiento privado;
- hay una terraza (tiene terraza);
- puedes reservar mesa (acepta reservas);
- apto para vegetarianos (apto para veganos);
- caro (caro).
Démosle a cada restaurante un número de secuencia a partir de 0 y asignemos memoria para 6 mapas de bits (uno para cada característica). Luego completaremos estos mapas de bits dependiendo de si el restaurante tiene esta propiedad o no. Si el restaurante 4 tiene una terraza, entonces el bit No. 4 en el mapa de bits “tiene una terraza” se establecerá en 1 (si no hay terraza, entonces en 0).
Ahora tenemos el índice de mapa de bits más simple posible y podemos usarlo para responder consultas como:
- “Muéstrame restaurantes vegetarianos”;
- "Muéstrame restaurantes económicos con terraza donde puedas reservar una mesa".
¿Cómo? Echemos un vistazo. La primera petición es muy sencilla. Todo lo que tenemos que hacer es tomar el mapa de bits “vegetariano” y convertirlo en una lista de restaurantes cuyos bits están expuestos.
La segunda petición es un poco más complicada. Necesitamos usar el mapa de bits NOT en el mapa de bits "caro" para obtener una lista de restaurantes económicos, luego Y con el mapa de bits "¿puedo reservar una mesa?" y Y el resultado con el mapa de bits "hay una terraza". El mapa de bits resultante contendrá una lista de establecimientos que cumplen con todos nuestros criterios. En este ejemplo, este es sólo el restaurante Yunost.
Hay mucha teoría involucrada, pero no te preocupes, veremos el código muy pronto.
¿Dónde se utilizan los índices de mapas de bits?
Si busca en Google índices de mapas de bits, el 90% de las respuestas estarán relacionadas con Oracle DB de una forma u otra. Pero probablemente otros DBMS también admitan algo tan interesante, ¿verdad? No precisamente.
Repasemos la lista de principales sospechosos.
MySQL aún no admite índices de mapas de bits, pero hay una propuesta que sugiere agregar esta opción ().
PostgreSQL no admite índices de mapas de bits, pero utiliza mapas de bits simples y operaciones de bits para combinar resultados de búsqueda en muchos otros índices.
Tarantool tiene índices de bits y admite búsquedas simples en ellos.
Redis tiene campos de bits simples) sin la capacidad de buscarlos.
MongoDB aún no admite índices de mapas de bits, pero también hay una propuesta que sugiere que se agregue esta opción
Elasticsearch usa mapas de bits internamente).
- Pero ha aparecido una nueva vecina en nuestra casa: Pilosa. Esta es una nueva base de datos no relacional escrita en Go. Contiene sólo índices de mapas de bits y basa todo en ellos. Hablaremos de ello un poco más tarde.
Implementación en Go
Pero, ¿por qué se utilizan tan raramente los índices de mapas de bits? Antes de responder esta pregunta, me gustaría mostrarle cómo implementar un índice de mapa de bits muy simple en Go.
Los mapas de bits son esencialmente solo fragmentos de datos. En Go, usemos segmentos de bytes para esto.
Tenemos un mapa de bits para una característica de restaurante y cada bit en el mapa de bits indica si un restaurante en particular tiene esta propiedad o no.
Necesitaremos dos funciones auxiliares. Uno se utilizará para llenar nuestros mapas de bits con datos aleatorios. Aleatorio, pero con cierta probabilidad de que el restaurante tenga cada propiedad. Por ejemplo, creo que hay muy pocos restaurantes en Moscú donde no se pueda reservar mesa, y me parece que alrededor del 20% de los establecimientos son aptos para vegetarianos.
La segunda función convertirá el mapa de bits en una lista de restaurantes.
Para responder a la consulta "Muéstrame restaurantes económicos que tengan patio y puedan hacer reservas", necesitamos operaciones de dos bits: NOT y AND.
Podemos simplificar un poco nuestro código usando el operador AND NOT más complejo.
Disponemos de funciones para cada una de estas operaciones. Ambos recorren los sectores, toman los elementos correspondientes de cada uno, los combinan con una operación de bits y ponen el resultado en el sector resultante.
Y ahora podemos usar nuestros mapas de bits y funciones para responder la consulta de búsqueda.
El rendimiento no es tan alto, aunque las funciones son muy simples y ahorramos mucho dinero al no devolver un nuevo segmento resultante cada vez que se llama a la función.
Después de crear un poco de perfil con pprof, noté que al compilador Go le faltaba una optimización muy simple pero muy importante: la inserción de funciones.
El hecho es que el compilador Go tiene mucho miedo de los bucles que pasan por cortes y se niega categóricamente a incorporar funciones que contengan dichos bucles.
Pero no tengo miedo y puedo engañar al compilador usando goto en lugar de un bucle, como en los viejos tiempos.
Y, como puede ver, ¡ahora el compilador incorporará felizmente nuestra función! Como resultado, logramos ahorrar unos 2 microsegundos. ¡Nada mal!
El segundo cuello de botella es fácil de ver si se observa de cerca el resultado del ensamblaje. El compilador agregó una verificación de límites de segmento justo dentro de nuestro bucle más activo. El hecho es que Go es un lenguaje seguro, el compilador teme que mis tres argumentos (tres porciones) sean de diferentes tamaños. Después de todo, entonces existe la posibilidad teórica de que se produzca el llamado desbordamiento del búfer.
Tranquilicemos al compilador mostrándole que todos los sectores son del mismo tamaño. Podemos hacer esto agregando una verificación simple al comienzo de nuestra función.
Al ver esto, el compilador felizmente se salta la verificación y terminamos ahorrando otros 500 nanosegundos.
grandes marimachas
Bien, logramos exprimir algo de rendimiento de nuestra implementación simple, pero este resultado es en realidad mucho peor de lo que es posible con el hardware actual.
Todo lo que hacemos son operaciones básicas de bits y nuestros procesadores las realizan de manera muy eficiente. Pero, lamentablemente, “alimentamos” nuestro procesador con muy pequeñas tareas. Nuestras funciones realizan operaciones byte por byte. Podemos modificar muy fácilmente nuestro código para que funcione con fragmentos de 8 bytes utilizando segmentos UInt64.
Como puede ver, este pequeño cambio aceleró nuestro programa ocho veces al aumentar ocho veces el tamaño del lote. Se puede decir que la ganancia es lineal.
Implementación en ensamblador.
Pero, este no es el final. Nuestros procesadores pueden trabajar con fragmentos de 16, 32 e incluso 64 bytes. Estas operaciones “amplias” se denominan datos múltiples de instrucción única (SIMD; una instrucción, muchos datos), y el proceso de transformar el código para que utilice dichas operaciones se llama vectorización.
Desafortunadamente, el compilador Go está lejos de ser excelente en vectorización. Actualmente, la única forma de vectorizar el código Go es tomar y colocar estas operaciones manualmente usando el ensamblador Go.
Go ensamblador es una bestia extraña. Probablemente sepas que el lenguaje ensamblador es algo que está fuertemente ligado a la arquitectura de la computadora para la que estás escribiendo, pero ese no es el caso en Go. Go ensamblador se parece más a un IRL (lenguaje de representación intermedio) o lenguaje intermedio: es prácticamente independiente de la plataforma. Rob Pike tuvo una excelente actuación sobre este tema hace varios años en GopherCon en Denver.
Además, Go utiliza un formato Plan 9 inusual, que difiere de los formatos generalmente aceptados de AT&T e Intel.
Es seguro decir que escribir Go en ensamblador a mano no es lo más divertido.
Pero, afortunadamente, ya existen dos herramientas de alto nivel que nos ayudan a escribir Go ensamblador: PeachPy y avo. Ambas utilidades generan el ensamblador Go a partir de código de nivel superior escrito en Python y Go, respectivamente.
Estas utilidades simplifican cosas como la asignación de registros, la escritura de bucles y, en general, simplifican el proceso de ingresar al mundo de la programación ensambladora en Go.
Usaremos avo, por lo que nuestros programas serán programas Go casi normales.
Así es como se ve el ejemplo más simple de un programa avo. Tenemos una función main(), que define dentro de sí misma la función Add(), cuyo significado es sumar dos números. Aquí hay funciones de ayuda para obtener parámetros por nombre y obtener uno de los registros de procesador adecuados y gratuitos. Cada operación del procesador tiene una función correspondiente en avo, como se ve en ADDQ. Finalmente, vemos una función auxiliar para almacenar el valor resultante.
Al llamar a go generate, ejecutaremos el programa en avo y como resultado se generarán dos archivos:
- add.s con el código resultante en Go ensamblador;
- stub.go con encabezados de funciones para conectar los dos mundos: Go y ensamblador.
Ahora que hemos visto qué hace avo y cómo, veamos nuestras funciones. Implementé versiones escalares y vectoriales (SIMD) de las funciones.
Veamos primero las versiones escalares.
Como en el ejemplo anterior, solicitamos un registro de propósito general válido y gratuito, no necesitamos calcular compensaciones ni tamaños para los argumentos. avo hace todo esto por nosotros.
Solíamos usar etiquetas y goto (o saltos) para mejorar el rendimiento y engañar al compilador Go, pero ahora lo hacemos desde el principio. La cuestión es que los ciclos son un concepto de nivel superior. En ensamblador sólo tenemos etiquetas y saltos.
El código restante ya debería resultarle familiar y comprensible. Emulamos un bucle con etiquetas y saltos, tomamos una pequeña porción de datos de nuestros dos sectores, los combinamos con una operación de bits (Y NO en este caso) y luego colocamos el resultado en el sector resultante. Todo.
Así es como se ve el código ensamblador final. No tuvimos que calcular compensaciones y tamaños (resaltados en verde) ni realizar un seguimiento de los registros utilizados (resaltados en rojo).
Si comparamos el rendimiento de la implementación en lenguaje ensamblador con el rendimiento de la mejor implementación en Go, veremos que es lo mismo. Y esto es lo que se espera. Después de todo, no hicimos nada especial: simplemente reproducimos lo que haría un compilador de Go.
Desafortunadamente, no podemos obligar al compilador a alinear nuestras funciones escritas en lenguaje ensamblador. El compilador Go actualmente no tiene dicha característica, aunque ha habido una solicitud para agregarla desde hace bastante tiempo.
Por eso es imposible obtener algún beneficio de las funciones pequeñas en lenguaje ensamblador. Necesitamos escribir funciones grandes, usar el nuevo paquete math/bits o evitar el lenguaje ensamblador.
Veamos ahora las versiones vectoriales de nuestras funciones.
Para este ejemplo, decidí usar AVX2, por lo que usaremos operaciones que operan en fragmentos de 32 bytes. La estructura del código es muy similar a la versión escalar: cargar parámetros, solicitar un registro compartido gratuito, etc.
Una innovación es que las operaciones vectoriales más amplias utilizan registros amplios especiales. En el caso de fragmentos de 32 bytes, estos son registros con el prefijo Y. Es por eso que ve la función YMM() en el código. Si estuviera usando AVX-512 con fragmentos de 64 bits, el prefijo sería Z.
La segunda innovación es que decidí utilizar una optimización llamada desenrollado de bucle, que significa realizar ocho operaciones de bucle manualmente antes de saltar al principio del bucle. Esta optimización reduce la cantidad de ramas en el código y está limitada por la cantidad de registros gratuitos disponibles.
Bueno, ¿qué pasa con el rendimiento? ¡Ella es hermosa! Logramos una aceleración de aproximadamente siete veces en comparación con la mejor solución Go. Impresionante, ¿verdad?
Pero incluso esta implementación podría acelerarse mediante el uso de AVX-512, la captación previa o un JIT (compilador justo a tiempo) para el programador de consultas. Pero este es sin duda un tema para un informe aparte.
Problemas con los índices de mapas de bits
Ahora que ya hemos visto una implementación simple de un índice de mapa de bits en Go y una mucho más productiva en lenguaje ensamblador, finalmente hablemos de por qué los índices de mapa de bits se usan tan raramente.
Los artículos más antiguos mencionan tres problemas con los índices de mapas de bits, pero los artículos más nuevos y yo sostenemos que ya no son relevantes. No profundizaremos en cada uno de estos problemas, sino que los analizaremos superficialmente.
El problema de la alta cardinalidad
Entonces, se nos dice que los índices de mapa de bits solo son adecuados para campos con baja cardinalidad, es decir, aquellos que tienen pocos valores (por ejemplo, género o color de ojos), y la razón es que la representación habitual de dichos campos (un bit por valor) en el caso de una cardinalidad alta, ocupará demasiado espacio y, además, estos índices de mapa de bits estarán mal (raramente) llenos.
A veces podemos usar una representación diferente, como la estándar que usamos para representar números. Pero fue la llegada de los algoritmos de compresión lo que lo cambió todo. Durante las últimas décadas, los científicos e investigadores han ideado una gran cantidad de algoritmos de compresión para mapas de bits. Su principal ventaja es que no es necesario descomprimir mapas de bits para realizar operaciones de bits; podemos realizar operaciones de bits directamente en mapas de bits comprimidos.
Recientemente, han comenzado a aparecer enfoques híbridos, como los mapas de bits rugientes. Utilizan simultáneamente tres representaciones diferentes para mapas de bits (mapas de bits en sí, matrices y las llamadas ejecuciones de bits) y equilibran entre ellas para maximizar el rendimiento y minimizar el consumo de memoria.
Puede encontrar mapas de bits rugientes en las aplicaciones más populares. Ya existe una gran cantidad de implementaciones para una amplia variedad de lenguajes de programación, incluidas más de tres implementaciones para Go.
Otro enfoque que puede ayudarnos a lidiar con una cardinalidad alta se llama binning. Imagina que tienes un campo que representa la altura de una persona. La altura es un número de coma flotante, pero los humanos no lo vemos de esa manera. Para nosotros no hay diferencia entre una altura de 185,2 cm y 185,3 cm.
Resulta que podemos agrupar valores similares en grupos dentro de 1 cm.
Y si también sabemos que muy pocas personas miden menos de 50 cm y miden más de 250 cm, entonces esencialmente podemos convertir un campo con cardinalidad infinita en un campo con una cardinalidad de aproximadamente 200 valores.
Por supuesto, si es necesario, podemos realizar un filtrado adicional posteriormente.
Problema de alto ancho de banda
El siguiente problema con los índices de mapas de bits es que actualizarlos puede resultar muy costoso.
Las bases de datos deben poder actualizar los datos mientras potencialmente cientos de otras consultas buscan los datos. Necesitamos bloqueos para evitar problemas con el acceso simultáneo a datos u otros problemas de intercambio. Y donde hay un gran candado, hay un problema: contención de candados, cuando este candado se convierte en un cuello de botella.
Este problema se puede resolver o evitar mediante fragmentación o índices versionados.
La fragmentación es algo simple y bien conocido. Puede fragmentar un índice de mapa de bits como lo haría con cualquier otro dato. En lugar de un candado grande, obtendrá un montón de candados pequeños y así eliminará la contención de candados.
La segunda forma de resolver el problema es utilizar índices versionados. Puede tener una copia del índice que utilice para buscar o leer, y otra que utilice para escribir o actualizar. Y una vez en un determinado período de tiempo (por ejemplo, una vez cada 100 ms o 500 ms), los duplica y los intercambia. Por supuesto, este enfoque sólo es aplicable en los casos en que su aplicación puede manejar un índice de búsqueda ligeramente retrasado.
Estos dos enfoques se pueden utilizar simultáneamente: puede tener un índice versionado fragmentado.
Consultas más complejas
El último problema con los índices de mapas de bits es que se nos dice que no son adecuados para tipos de consultas más complejas, como las consultas de intervalo.
De hecho, si lo piensas bien, las operaciones de bits como AND, OR, etc. no son muy adecuadas para consultas del estilo "Muéstrame hoteles con tarifas de habitación de 200 a 300 dólares por noche".
Una solución ingenua y muy imprudente sería tomar los resultados de cada valor en dólares y combinarlos con una operación OR bit a bit.
Una solución ligeramente mejor sería utilizar la agrupación. Por ejemplo, en grupos de 50 dólares. Esto aceleraría nuestro proceso 50 veces.
Pero el problema también se resuelve fácilmente utilizando una vista creada específicamente para este tipo de solicitud. En artículos científicos se denomina mapa de bits codificado por rango.
En esta representación, no solo configuramos un bit para algún valor (por ejemplo, 200), sino que configuramos este valor y todo lo demás a un valor mayor. 200 y más. Lo mismo para 300: 300 y superiores. Etcétera.
Usando esta representación, podemos responder a este tipo de consulta de búsqueda recorriendo el índice solo dos veces. Primero, obtendremos una lista de hoteles donde la habitación cuesta menos o $300, y luego eliminaremos aquellos donde la habitación cuesta menos o $199. Listo.
Te sorprenderá, pero incluso las consultas geográficas son posibles utilizando índices de mapas de bits. El truco consiste en utilizar una representación geométrica que rodee su coordenada con una figura geométrica. Por ejemplo, S2 de Google. La figura debe poder representarse en forma de tres o más líneas que se cruzan y que se pueden numerar. De esta manera podemos convertir nuestra geoconsulta en varias consultas “a lo largo del espacio” (a lo largo de estas líneas numeradas).
Soluciones listas
Espero haberte interesado un poco y ahora tengas otra herramienta útil en tu arsenal. Si alguna vez necesitas hacer algo como esto, sabrás hacia dónde mirar.
Sin embargo, no todo el mundo tiene el tiempo, la paciencia o los recursos para crear índices de mapas de bits desde cero. Sobre todo los más avanzados, que utilizan SIMD, por ejemplo.
Afortunadamente, existen varias soluciones listas para ayudarle.
Mapas de bits rugientes
En primer lugar, existe la misma biblioteca de mapas de bits de la que ya hablé. Contiene todos los contenedores y operaciones de bits necesarios que necesitará para crear un índice de mapa de bits completo.
Desafortunadamente, por el momento, ninguna de las implementaciones de Go utiliza SIMD, lo que significa que las implementaciones de Go tienen menos rendimiento que las implementaciones de C, por ejemplo.
Pilosa
Otro producto que puede ayudarte es el DBMS Pilosa, que, de hecho, sólo tiene índices de mapa de bits. Se trata de una solución relativamente nueva, pero que está ganando popularidad a gran velocidad.
Pilosa utiliza mapas de bits rugientes internamente y le brinda la posibilidad de usarlos, simplifica y explica todas las cosas de las que hablé anteriormente: agrupación, mapas de bits codificados por rango, el concepto de campo, etc.
Echemos un vistazo rápido a un ejemplo del uso de Pilosa para responder una pregunta con la que ya está familiarizado.
El ejemplo es muy similar a lo que viste antes. Creamos un cliente para el servidor Pilosa, creamos un índice y los campos necesarios, luego llenamos nuestros campos con datos aleatorios con probabilidades y, finalmente, ejecutamos la consulta familiar.
Después de eso, usamos NOT en el campo "caro", luego cruzamos el resultado (o Y) con el campo "terraza" y con el campo "reservas". Y finalmente obtenemos el resultado final.
Realmente espero que en un futuro previsible este nuevo tipo de índice también aparezca en DBMS como MySQL y PostgreSQL: índices de mapa de bits.
Conclusión
Si aún no te has dormido, gracias. Tuve que tocar brevemente muchos temas debido al tiempo limitado, pero espero que la charla haya sido útil y tal vez incluso motivadora.
Es bueno conocer los índices de mapas de bits, incluso si no los necesita en este momento. Déjalos ser una herramienta más en tu caja de herramientas.
Hemos analizado varios trucos de rendimiento para Go y cosas que el compilador de Go aún no maneja muy bien. Pero es absolutamente útil que todo programador de Go lo sepa.
Eso es todo lo que quería decirte. ¡Gracias!
Fuente: habr.com