Palavra de abertura
Eu fiz esta apresentação em inglês na conferência GopherCon Russia 2019 em Moscovo e em russo — no meetup em Nizhny Novgorod. A palestra fala sobre o índice bitmap — menos comum que o B-tree, mas igualmente interessante. Estou compartilhando da apresentação na conferência em inglês e a transcrição em texto em russo.
Vamos examinar como funciona o índice bitmap, quando ele é melhor, quando é pior do que outros índices e em quais casos é significativamente mais rápido; veremos em quais SGBDs populares já existem índices bitmap; tentaremos escrever o nosso em Go. E como 'sobremesa', usaremos bibliotecas prontas para criar nosso banco de dados especializado super rápido.
Espero sinceramente que meu trabalho seja útil e interessante para vocês. Vamos lá!
Introdução
Olá a todos! Agora são seis da tarde, todos estamos super cansados. Um momento maravilhoso para falar sobre a chata teoria dos índices de bancos de dados, né? Não se preocupem, vou ter algumas linhas de código aqui e ali. 🙂
Brincadeiras à parte, a apresentação está repleta de informações e temos pouco tempo. Então, vamos começar.
Hoje eu vou falar sobre o seguinte:
- o que são índices;
- o que é um índice bitmap;
- onde ele é usado e onde ele NÃO é usado e por quê;
- uma implementação simples em Go e um pouco de luta com o compilador;
- uma implementação um pouco menos simples, mas muito mais eficiente em Go-assembly;
- os 'problemas' dos índices bitmap;
- implementações existentes.
Então, o que são índices?
Um índice é uma estrutura de dados separada que mantemos e atualizamos além dos dados principais. Ele é usado para acelerar a busca. Sem índices, a busca exigiria uma varredura completa dos dados (processo chamado de full scan), e esse processo tem complexidade algorítmica linear. Mas os bancos de dados costumam conter uma enorme quantidade de dados e a complexidade linear é demasiado lenta. Idealmente, gostaríamos de obter uma complexidade logarítmica ou constante.
Este é um tema enorme e complexo, repleto de sutilezas e compromissos, mas, após anos de desenvolvimento e pesquisa de vários bancos de dados, estou preparado para afirmar que existem apenas algumas abordagens amplamente utilizadas para a criação de índices de bancos de dados.
A primeira abordagem consiste em reduzir hierarquicamente o espaço de busca, dividindo a área de pesquisa em partes menores.
Normalmente, fazemos isso usando diferentes tipos de árvores. Um exemplo pode ser uma grande caixa com materiais em seu armário, que contém caixas menores com materiais organizados por diferentes temas. Se você precisa de materiais, certamente irá procurar na caixa marcada "Materiais", e não na que diz "Biscoitos", certo?
A segunda abordagem consiste em destacar imediatamente o elemento ou grupo de elementos desejados. Fazemos isso em hash maps ou em índices invertidos. O uso de hash maps é muito semelhante ao exemplo anterior, exceto que, em vez de uma caixa com caixas, você tem no seu armário uma pilha de pequenas caixas com itens finais.
A terceira abordagem é eliminar a necessidade de busca. Fazemos isso com filtros Bloom ou filtros cuckoo. Os primeiros fornecem respostas instantaneamente, livrando você da necessidade de realizar uma busca.
A última abordagem consiste em aproveitar ao máximo todo o poder que a tecnologia moderna nos oferece. É exatamente isso que fazemos em índices bitmap. Sim, ao usá-los, às vezes precisamos percorrer todo o índice, mas fazemos isso de forma super eficiente.
Como eu já disse, o tema dos índices de banco de dados é amplo e repleto de compromissos. Isso significa que, às vezes, podemos usar várias abordagens ao mesmo tempo: se precisarmos acelerar ainda mais a busca ou se for necessário cobrir todos os tipos possíveis de pesquisa.
Hoje, falarei sobre a abordagem menos conhecida das mencionadas — os índices bitmap.
Quem sou eu para falar sobre este assunto?
Eu trabalho como líder de equipe na Badoo (talvez você conheça melhor nosso outro produto — Bumble). Temos mais de 400 milhões de usuários em todo o mundo e muitas funcionalidades que se dedicam a encontrar a melhor combinação para eles. Fazemos isso com serviços personalizados, que utilizam, inclusive, índices bitmap.
Então, o que é um índice bitmap?
Os índices bitmap, como o próprio nome sugere, utilizam bitmaps ou bitsets para implementar um índice de pesquisa. De uma perspectiva geral, esse índice consiste em um ou mais desses bitmaps, representando entidades (como pessoas) e suas propriedades ou parâmetros (idade, cor dos olhos, etc.), além de um algoritmo que usa operações bit a bit (AND, OR, NOT) para responder a consultas de busca.
Dizem que os índices bitmap são mais adequados e extremamente eficazes para casos em que há busca que combina consultas em várias colunas com baixa cardinalidade (imagine 'cor dos olhos' ou 'estado civil' em comparação a algo como 'distância do centro da cidade'). Mas mais adiante, vou mostrar que eles funcionam muito bem também com colunas de alta cardinalidade.
Vamos considerar um exemplo simples de um índice bitmap.
Imagine que temos uma lista de restaurantes em Moscovo com propriedades binárias como estas:
- perto do metrô (near metro);
- tem estacionamento privativo (has private parking);
- tem varanda (has terrace);
- aceita reservas (accepts reservations);
- é adequado para vegetarianos (vegan friendly);
- caro (expensive).
Vamos atribuir a cada restaurante um número sequencial começando de 0 e alocar memória para 6 bitmaps (um para cada característica). Em seguida, preencheremos esses bitmaps dependendo se o restaurante possui ou não a referida propriedade. Se o restaurante 4 tiver uma varanda, o bit nº 4 no bitmap 'tem varanda' será definido como 1 (se não houver varanda, será 0).
Agora temos o índice bitmap mais simples possível, e podemos usá-lo para responder a consultas como:
- "Mostre-me os restaurantes adequados para vegetarianos";
- "Mostre-me restaurantes baratos com varanda, onde posso reservar uma mesa".
Como? Vamos ver. A primeira consulta é muito simples. Tudo que precisamos fazer é pegar o bitmap "é adequado para vegetarianos" e transformá-lo em uma lista de restaurantes cujos bits estão definidos.
A segunda consulta é um pouco mais complicada. Precisamos usar a operação bitwise NOT no bitmap "caro" para obter uma lista de restaurantes baratos, em seguida, realizar um AND com o bitmap "reserva disponível" e depois fazer um AND do resultado com o bitmap "tem varanda". O bitmap resultante conterá uma lista de estabelecimentos que atendem a todos os nossos critérios. Neste exemplo, é apenas o restaurante "Joventude".
Aqui há muita teoria, mas não se preocupe, veremos o código muito em breve.
Onde são utilizados índices bitmap?
Se você "googlar" índices bitmap, 90% das respostas estarão de alguma forma relacionadas ao Oracle DB. Mas outros SGBDs também devem suportar algo tão legal, certo? Nem tanto.
Vamos passar pela lista dos principais suspeitos.
O MySQL ainda não suporta índices bitmap, mas há uma proposta para adicionar esse recurso ().
O PostgreSQL não suporta índices bitmap, mas utiliza bitmaps simples e operações bitwise para combinar os resultados de pesquisas em outros índices.
O Tarantool tem índices de conjuntos de bits e suporta pesquisa simples neles.
O Redis possui campos bitwise simples) sem possibilidade de pesquisa neles.
O MongoDB ainda não suporta índices bitmap, mas também há uma proposta para adicionar esse recurso
O Elasticsearch utiliza bitmaps internamente).
- Mas em nossa casa apareceu um novo vizinho: Pilosa. É um novo banco de dados não relacional, escrito em Go. Ele contém apenas índices bitmap e baseia tudo neles. Vamos falar sobre isso um pouco mais tarde.
Implementação em Go
Mas por que os índices bitmap são tão raramente utilizados? Antes de responder a essa pergunta, gostaria de demonstrar a vocês a implementação de um índice bitmap muito simples em Go.
Os bitmaps, na essência, são representados apenas como pedaços de dados. Em Go, vamos usar slices de bytes para isso.
Temos um bitmap para cada característica do restaurante, e cada bit no bitmap indica se o restaurante específico possui essa característica ou não.
Precisamos de duas funções auxiliares. Uma será usada para preencher nossos bitmaps com dados aleatórios. Aleatórios, mas com uma certa probabilidade de que o restaurante possua cada propriedade. Por exemplo, eu considero que em Moscovo há muito poucos restaurantes onde não é possível reservar uma mesa, e me parece que cerca de 20% dos estabelecimentos são adequados para vegetarianos.
A segunda função converterá o bitmap em uma lista de restaurantes.
Para responder à consulta "Mostre-me restaurantes baratos que tenham varanda e onde seja possível reservar uma mesa", precisaremos de duas operações bit a bit: NOT e AND.
Podemos simplificar um pouco nosso código utilizando uma operação mais complexa: AND NOT.
Temos funções para cada uma dessas operações. Ambas percorrem os slices, pegam os elementos correspondentes de cada um, combinam-nos com a operação bit a bit e colocam o resultado no slice de resultado.
E agora podemos utilizar nossos bitmaps e funções para responder à consulta de busca.
O desempenho não é tão alto, mesmo que as funções sejam muito simples e economizamos bastante por não retornar um novo slice de resultado a cada chamada da função.
Depois de fazer um profiling com pprof, notei que o compilador Go ignorou uma otimização muito simples, mas extremamente importante: inlining de funções.
O fato é que o compilador Go tem muito medo de loops que percorrem slices, e se recusa categoricamente a fazer inlining de funções que contêm tais loops.
Mas eu não tenho esse medo e posso enganar o compilador usando goto em vez de um loop, como nos velhos tempos.
E, como podem ver, agora o compilador se alegra em fazer o inlining da nossa função! No final, conseguimos economizar cerca de 2 microssegundos. Não é mau!
O segundo gargalo é fácil de identificar se olharmos atentamente a saída do assembly. O compilador adicionou uma verificação de limites do slice diretamente dentro do nosso loop mais quente. O fato é que Go é uma linguagem segura, e o compilador teme que meus três argumentos (três slices) tenham tamanhos diferentes. Pois então haveria uma possibilidade teórica de ocorrer um overflow de buffer.
Vamos acalmar o compilador, mostrando que todos os slices têm o mesmo tamanho. Podemos fazer isso adicionando uma simples verificação no início da nossa função.
Vendo isso, o compilador felizmente ignora a verificação, e economizamos mais 500 nanossegundos.
Grandes lotes
Ok, conseguimos extrair um pouco de desempenho da nossa implementação simples, mas esse resultado é, na verdade, muito pior do que o que é possível com o hardware atual.
Tudo o que fazemos são operações básicas com bits, e nossos processadores as executam de forma muito eficiente. Mas, infelizmente, estamos "alimentando" nosso processador com pedaços muito pequenos de trabalho. Nossas funções executam operações byte a byte. Podemos facilmente otimizar nosso código para trabalhar com pedaços de 8 bytes, usando slices UInt64.
Como você pode ver, essa pequena mudança acelerou nosso programa em oito vezes, aumentando o lote também em oito vezes. O ganho pode ser considerado linear.
Implementação em Assembly
Mas isso não é o fim. Nossos processadores podem trabalhar com pedaços de 16, 32 e até 64 bytes. Essas operações "largas" são chamadas de single instruction multiple data (SIMD; uma instrução, muitos dados), e o processo de transformar código para que utilize essas operações é chamado de vetorização.
Infelizmente, o compilador Go não é exatamente um modelo em vetorização. Até o momento, a única forma de vetorizar código em Go é intervir manualmente nas operações usando assembly Go.
Assembly Go é uma coisa estranha. Você provavelmente sabe que o assembly é algo muito ligado à arquitetura do computador para o qual você está escrevendo, mas em Go isso não é o caso. Assembly Go é mais parecido com uma IRL (linguagem de representação intermediária): é praticamente independente de plataforma. Rob Pike fez uma excelente sobre este tema alguns anos atrás no GopherCon em Denver.
Além disso, Go utiliza um formato incomum, o Plan 9, que difere dos formatos reconhecidos AT&T e Intel.
Pode-se afirmar com confiança que escrever assembly Go manualmente não é a tarefa mais divertida.
Mas, felizmente, já existem duas ferramentas de alto nível que nos ajudam a escrever assembly Go: PeachPy e avo. Ambas as ferramentas geram assembly Go a partir de código de nível mais alto escrito em Python e Go, respectivamente.
Essas utilitários simplificam questões como alocação de registradores (escolha do registrador do processador), escrita de loops e, no geral, facilitam a entrada no mundo da programação em assembly no Go.
Usaremos o avo, de modo que nossos programas serão quase programas comuns em Go.
Esta é a aparência do exemplo mais simples de um programa avo. Temos a função main(), que define internamente a função Add(), cuja finalidade é somar dois números. Existem funções auxiliares para obter parâmetros pelo nome e para obter um dos registradores de processador livres e adequados. Cada operação de processador tem uma função correspondente no avo, como pode ser visto pelo ADDQ. Finalmente, vemos uma função auxiliar para armazenar o valor resultante.
Ao chamar go generate, executaremos o programa no avo e, no final, dois arquivos serão gerados:
- add.s com o código resultante em assembly Go;
- stub.go com as declarações de funções para conectar os dois mundos: Go e assembly.
Agora que vimos o que o avo faz e como ele funciona, vamos olhar nossas funções. Eu implementei versões escalar e vetorial (SIMD) das funções.
Primeiro, vamos olhar para as versões escalares.
Como no exemplo anterior, pedimos um registrador de uso geral livre e correto, não precisamos calcular deslocamentos ou tamanhos para os argumentos. Tudo isso o avo faz por nós.
Anteriormente, utilizamos rótulos e goto (ou saltos) para aumentar o desempenho e enganar o compilador Go, mas agora fazemos isso desde o início. O fato é que loops são um conceito de nível mais alto. Em assembly, só temos rótulos e saltos.
O código restante deve já ser familiar e compreensível. Estamos emulando o loop com rótulos e saltos, pegando uma pequena parte de dados de nossas duas listas, combinando-os com uma operação bit a bit (AND NOT, neste caso) e, em seguida, colocando o resultado na lista resultante. Isso é tudo.
Este é o aspecto do código final em assembly. Não precisamos calcular deslocamentos e tamanhos (destacado em verde) ou monitorar os registradores utilizados (destacado em vermelho).
Se compararmos o desempenho da implementação em assembler com o desempenho da melhor implementação em Go, veremos que é igual. E isso é esperado. Afinal, não fizemos nada de especial — apenas reproduzimos o que o compilador Go faria.
Infelizmente, não podemos fazer com que o compilador inlined nossas funções escritas em assembler. O compilador Go atualmente não possui essa capacidade, embora haja um pedido para adicioná-la há bastante tempo.
É por isso que não é possível obter quaisquer vantagens de funções pequenas em assembler. Precisamos ou escrever funções grandes, ou usar o novo pacote math/bits, ou evitar o assembler.
Agora vamos dar uma olhada nas versões vetoriais de nossas funções.
Para este exemplo, decidi aplicar AVX2, portanto, usaremos operações que trabalham com blocos de 32 bytes. A estrutura do código é muito semelhante à versão escalar: carregamento de parâmetros, solicitação de um registro geral livre, etc.
Uma das inovações está relacionada ao fato de que operações vetoriais mais amplas usam registradores especiais. No caso de blocos de 32 bytes, são registradores com o prefixo Y. É por isso que você vê a função YMM() no código. Se eu tivesse usado AVX-512 com blocos de 64 bits, o prefixo seria Z.
A segunda inovação está relacionada ao fato de que decidi usar uma otimização chamada desenrolamento de laço (loop unrolling), ou seja, realizar oito operações do laço manualmente antes de pular de volta ao início do laço. Essa otimização reduz o número de bifurcações no código e é limitada pelo número de registradores livres disponíveis.
E quanto ao desempenho? É maravilhoso! Nós conseguimos uma aceleração de cerca de sete vezes em comparação com a melhor solução em Go. Impressionante, não é?
Mas mesmo essa implementação poderia ser potencialmente acelerada, aproveitando AVX-512, prefetching ou JIT (just-in-time compiler) para o planejador de consultas. Mas isso, sem dúvida, é um tema para uma apresentação separada.
Problemas dos índices bitmap
Agora que já analisamos a implementação simples de um índice bitmap em Go e uma muito mais eficiente em assembler, vamos finalmente falar sobre o porquê de os índices bitmap serem tão raramente utilizados.
Em trabalhos científicos antigos, três problemas dos índices bitmap são mencionados, mas pesquisas mais recentes e eu afirmamos que eles já não são relevantes. Não vamos nos aprofundar em cada uma dessas questões, mas vamos analisá-las superficialmente.
O problema da alta cardinalidade
Assim, nos dizem que os índices bitmap são adequados apenas para campos com baixa cardinalidade, ou seja, aqueles que possuem poucos valores (por exemplo, gênero ou cor dos olhos), e a razão é que a representação comum desses campos (um bit por valor) em caso de alta cardinalidade ocupará muito espaço e, além disso, esses índices bitmap estarão pouco (raramente) preenchidos.
Às vezes, podemos usar outra representação, como a padrão que utilizamos para representar números. Mas foi exatamente o surgimento de algoritmos de compressão que mudou tudo. Nas últimas décadas, cientistas e pesquisadores inventaram uma grande quantidade de algoritmos de compressão para bitmaps. Sua principal vantagem é que não é necessário descomprimir bitmaps para realizar operações de bits — podemos fazer operações de bits diretamente sobre bitmaps comprimidos.
Recentemente, também começaram a surgir abordagens híbridas, como os bitmaps roaring. Eles utilizam simultaneamente três representações diferentes para bitmaps — os próprios bitmaps, arrays e os chamados bit runs — e equilibram entre elas para maximizar o desempenho e minimizar o consumo de memória.
Você pode encontrar bitmaps roaring nas aplicações mais populares. Já existe uma enorme quantidade de implementações para diversas linguagens de programação, incluindo mais de três implementações para Go.
Outra abordagem que pode nos ajudar a lidar com alta cardinalidade é chamada de agrupamento (binning). Imagine que você tem um campo que representa a altura de uma pessoa. A altura é um número de ponto flutuante, mas nós, humanos, não pensamos nisso dessa maneira. Para nós, não há diferença entre uma altura de 185,2 cm e 185,3 cm.
Portanto, podemos agrupar valores semelhantes em grupos dentro de 1 cm.
E se ainda soubermos que muito poucas pessoas têm altura abaixo de 50 cm ou acima de 250 cm, podemos, essencialmente, transformar um campo de cardinalidade infinita em um campo com cardinalidade de aproximadamente 200 valores.
Claro, se necessário, podemos fazer uma filtragem adicional depois.
O problema da alta largura de banda
O próximo problema dos índices bitmap é que sua atualização pode ser muito cara.
Os bancos de dados devem permitir a atualização dos dados no momento em que potencialmente centenas de outras solicitações estão buscando esses dados. Precisamos de bloqueios para evitar problemas de acesso simultâneo aos dados ou outros problemas de compartilhamento. E onde há um grande bloqueio, há um problema - a contenção do bloqueio, quando esse bloqueio se torna um gargalo.
Esse problema pode ser resolvido ou contornado usando sharding ou índices versionados.
Sharding é algo simples e bem conhecido. Você pode shardizar um índice bitmap da mesma forma que shardizaria qualquer outro dado. Em vez de um grande bloqueio, você terá muitos pequenos bloqueios e, assim, eliminará a contenção do bloqueio.
Uma segunda forma de resolver o problema é usar índices versionados. Você pode ter uma cópia do índice que usa para busca ou leitura, e outra para gravação ou atualização. E a cada intervalo de tempo (por exemplo, a cada 100 ms ou 500 ms), você duplica e troca-os de lugar. Claro, essa abordagem é aplicável apenas em casos onde seu aplicativo pode funcionar com um índice de busca um pouco defasado.
Essas duas abordagens podem ser usadas simultaneamente: você pode ter um índice versionado shardizado.
Consultas mais complexas
O último problema dos índices bitmap é que, como nos dizem, eles não são adequados para tipos de consultas mais complexas, como consultas 'por intervalo'.
De fato, se pensarmos bem, operações bit a bit como AND, OR, etc., não são muito adequadas para consultas do tipo 'mostre-me os hotéis com preços de quartos entre 200 e 300 dólares por noite'.
Uma solução ingênua e muito irracional seria pegar os resultados para cada valor em dólar e combiná-los com a operação bit a bit OR.
Uma solução um pouco mais adequada seria usar agrupamento. Por exemplo, em grupos de 50 dólares. Isso aceleraria nosso processo em 50 vezes.
Mas o problema é facilmente resolvido pelo uso de uma representação criada especificamente para esse tipo de consulta. Em trabalhos acadêmicos, é chamada de bitmaps codificados por intervalo.
Nessa representação, não estamos apenas definindo um bit para um certo valor (por exemplo, 200), mas estabelecemos esse valor e tudo acima. 200 e acima. O mesmo se aplica a 300: 300 e acima. E assim por diante.
Usando essa representação, podemos responder a esse tipo de consulta de busca, percorrendo o índice apenas duas vezes. Primeiro, obtemos uma lista de hotéis onde o preço do quarto é menor que 300 dólares, e depois retiramos aqueles onde o preço do quarto é menor que 199 dólares. Pronto.
Você ficará surpreso, mas até mesmo consultas geográficas podem ser feitas usando índices bitmap. O truque é usar uma representação geográfica que cercará sua coordenada com uma figura geométrica. Por exemplo, S2 do Google. A figura deve ser representável por três ou mais linhas cruzadas que podem ser numeradas. Assim, poderemos transformar nossa consulta geográfica em várias consultas 'por intervalo' (por essas linhas numeradas).
Soluções prontas
Espero ter despertado seu interesse e que você tenha um novo instrumento útil em seu arsenal. Se algum dia você precisar fazer algo semelhante, saberá em que direção olhar.
No entanto, nem todos têm tempo, paciência e recursos para criar índices bitmap do zero. Especialmente os mais avançados, usando SIMD, por exemplo.
Felizmente, existem algumas soluções prontas que podem ajudar você.
Bitmaps roaring
Em primeiro lugar, existe a biblioteca de bitmaps roaring, sobre a qual já falei. Ela contém todos os contêineres e operações bit a bit necessários para que você possa criar um índice bitmap completo.
Infelizmente, no momento, nenhuma das implementações em Go utiliza SIMD, o que significa que as implementações em Go são menos eficientes do que as implementações em C, por exemplo.
Pilosa
Outro produto que pode ajudar você é o banco de dados Pilosa, que possui, essencialmente, apenas índices bitmap. Esta é uma solução relativamente nova, mas está conquistando corações rapidamente.
Pilosa utiliza bitmaps roaring internamente e permite que você os utilize, simplificando e explicando todas as coisas que mencionei acima: agrupamento, bitmaps codificados em intervalo, o conceito de campo, etc.
Vamos dar uma rápida olhada em um exemplo de uso do Pilosa para responder a uma pergunta que você já conhece.
O exemplo é muito semelhante ao que você viu antes. Criamos um cliente para o servidor Pilosa, criamos um índice e os campos necessários, em seguida, preenchemos nossos campos com dados aleatórios com probabilidades e, finalmente, executamos uma consulta familiar.
Depois disso, usamos NOT no campo 'expensive', em seguida, cruzamos o resultado (ou AND) com o campo 'terrace' e com o campo 'reservations'. E finalmente, obtemos o resultado final.
Eu realmente espero que em um futuro próximo bancos de dados como MySQL e PostgreSQL também adotem esse novo tipo de índices — índices bitmap.
Conclusão
Se você ainda não está dormindo, obrigado. Tive que tocar em muitos tópicos rapidamente devido ao tempo limitado, mas espero que a palestra tenha sido útil e, talvez, até motivadora.
É bom saber sobre índices bitmap, mesmo que você não precise deles agora. Que eles sejam mais uma ferramenta na sua caixa de ferramentas.
Nós exploramos vários truques para aumentar o desempenho no Go e as coisas com as quais o compilador Go ainda não se sai muito bem. Isso definitivamente é útil saber para qualquer programador em Go.
Isso é tudo o que eu queria compartilhar. Obrigado!
Fonte: habr.com
