Elasticsearch de baixo para cima, parte 1

Introdução

A motivação é entender melhor como o Elasticsearch, o Lucene e, até certo ponto, os mecanismos de busca em geral realmente funcionam sob o capô. Embora você possa dirigir um carro girando o volante e pisando em alguns pedais, os motoristas altamente competentes geralmente entendem pelo menos parte da mecânica do veículo. O mesmo vale para os mecanismos de busca. O Elasticsearch fornece APIs muito fáceis de usar, que ajudarão você a começar e a ir longe sem muito esforço. No entanto, para aproveitar ao máximo, é útil ter algum conhecimento sobre os algoritmos subjacentes e as estruturas de dados. Esse entendimento permite que você faça uso total de seu conjunto substancial de recursos para poder melhorar as experiências de busca dos seus usuários e, ao mesmo tempo, manter seus sistemas confiáveis, atualizados (quase) em tempo real e com bom desempenho.

Começaremos com a estrutura básica do índice, o índice invertido. É uma estrutura de dados muito versátil. Ao mesmo tempo, também é fácil de usar e entender. Dito isso, a implementação do Lucene é um feito de engenharia altamente otimizado e impressionante. Não vamos nos aventurar nos detalhes da implementação do Lucene, mas sim nos ater a como o índice invertido é usado e construído. Isso é o que influencia como podemos buscar e indexar.

Tendo introduzido o índice invertido como o “fundo” dos níveis de abstração, veremos:

• Como buscas simples são realizadas.
• Que tipos de busca podem (e não podem) ser feitas com eficácia e por que, com um índice invertido, transformamos os problemas até que se pareçam com problemas de prefixo de string.
• Por que o processamento de texto é importante.
• Como os índices são construídos em “segmentos” e como isso afeta a busca e a atualização.
• O que constitui um índice do Lucene.
• O shard e o índice do Elasticsearch.

Nesse ponto, saberemos muito sobre o que acontece dentro de um único nó do Elasticsearch durante a busca e a indexação. O segundo artigo da série abordará os aspectos distribuídos do Elasticsearch.

Índices invertidos e termos de índice

Digamos que temos estes três documentos simples: “Winter is coming.”, “Ours is the fury.” e “The choice is yours.” Após algum processamento de texto simples (uso de minúsculas, remoção de pontuação e divisão de palavras), podemos construir o “índice invertido” mostrado na figura.

O índice invertido mapeia termos para documentos (e possivelmente posições nos documentos) contendo o termo. Como os termos no dicionário são classificados, podemos encontrar rapidamente um termo e, subsequentemente, suas ocorrências na estrutura de postagens. Isso é o contrário de um “índice avançado”, que lista termos relacionados a um documento específico.

Uma busca simples com vários termos é então feita procurando todos os termos e suas ocorrências e fazendo a interseção (para buscas AND) ou a união (para buscas OR) dos conjuntos de ocorrências para obter a lista de documentos resultante. Tipos de consulta mais complexos são obviamente mais elaborados, mas a abordagem é a mesma: primeiro, operar no dicionário para encontrar termos candidatos, depois nas ocorrências correspondentes, posições etc.

Consequentemente, um termo de índice é a unidade de busca. Os termos que geramos determinam quais tipos de busca podemos (e não podemos) fazer com eficiência. Por exemplo, com o dicionário da figura acima, podemos encontrar com eficiência todos os termos que começam com “c”. No entanto, não podemos realizar uma busca eficiente em tudo que contém “ours”. Para fazer isso, teríamos de percorrer todos os termos, para descobrir que “yours” também contém a substring. Isso é proibitivamente caro quando o índice não é trivialmente pequeno. Em termos de complexidade, procurar termos por seu prefixo é \(\mathcal{O}\left(\mathrm{log}\left(n\right)\right)\), enquanto encontrar termos por uma substring arbitrária é \(\mathcal{O}\left(n\right)\).

Em outras palavras, podemos encontrar coisas de forma eficiente com os prefixos do termo. Quando tudo o que temos é um índice invertido, queremos que tudo pareça um problema de prefixo de string. Aqui estão alguns exemplos de tais transformações. Alguns são simples, mas o último beira a magia.

• Para encontrar tudo que termina com “tastic”, podemos indexar o reverso (por exemplo, “fantastic” → “citsatnaf”) e buscar tudo que começa com “citsat”.
• Encontrar substrings geralmente envolve dividir os termos em termos menores chamados “n-gramas”. Por exemplo, “yours” pode ser dividido em “^yo”, “you”, “our”, “urs”, “rs$”, o que significa que obteríamos ocorrências de “ours” fazendo buscas por “our” e “urs”.
• Para idiomas com palavras compostas, como norueguês e alemão, precisamos “decompor” palavras como “Donaudampfschiff” em, por exemplo, {"donau", "dampf", "schiff"} para encontrá-las ao buscar por “schiff”.
• Pontos de coordenadas geográficas como (60.6384, 6.5017) podem ser convertidos em “geo hashes”, neste caso, “u4u8gyykk”. Quanto mais longa a string, maior a precisão.
• Para habilitar a correspondência fonética, que é muito útil para nomes de pessoas, por exemplo, existem algoritmos como o Metaphone que convertem “Smith” em {"SM0", "XMT"} e “Schmidt” em {"XMT", "SMT"}.
• Ao lidar com dados numéricos (e carimbos de data/hora), o Lucene gera automaticamente vários termos com precisão diferente de maneira semelhante a uma árvore de prefixos, para que as buscas por intervalo possam ser feitas com eficiência¹. Simplificado, o número 123 pode ser armazenado como “1”-hundreds, “12”-tens e “123”. Portanto, buscar tudo no intervalo [100, 199] é, portanto, tudo que corresponde ao termo "1"-hundreds. Isso é diferente de buscar tudo que começa com “1”, é claro, pois isso também incluiria “1234” e assim por diante.
• Para fazer buscas do tipo “Você quis dizer?” e encontrar ortografias próximas à entrada, um autômato “Levenshtein” pode ser construído para percorrer o dicionário com eficiência. Isso é excepcionalmente complexo; aqui está uma história fascinante sobre como isso acabou no Lucene.

Uma análise técnica profunda do processamento de texto é assunto para muitos artigos futuros, mas destacamos por que é importante ser meticuloso sobre a geração de termos de índice: para obter buscas que possam ser executadas com eficiência.

Como criar índices

Ao criar índices invertidos, há algumas coisas que precisamos priorizar: a velocidade da busca, a compactação do índice, a velocidade da indexação e o tempo que leva para novas alterações se tornarem visíveis.

A velocidade da busca e a compactação do índice estão relacionadas: ao buscar em um índice menor, menos dados precisam ser processados e mais dados caberão na memória. Como veremos, ambos, particularmente a compactação, vêm ao custo da velocidade da indexação.

Para minimizar os tamanhos dos índices, várias técnicas de compactação são usadas. Por exemplo, ao armazenar as postagens (que podem ficar muito grandes), o Lucene faz truques como codificação delta (por exemplo, [42, 100, 666] é armazenado como [42, 58, 566] ), uso de um número variável de bytes (para que números pequenos possam ser salvos com um único byte) e assim por diante.

Manter as estruturas de dados pequenas e compactas significa sacrificar a possibilidade de atualizá-las com eficiência. Na verdade, o Lucene não as atualiza: os arquivos de índice que o Lucene grava são imutáveis, ou seja, eles nunca são atualizados. Isso é bem diferente das árvores B, por exemplo, que podem ser atualizadas e geralmente permitem que você especifique um fator de preenchimento para indicar quanta atualização você espera.

A exceção são as exclusões. Quando você exclui um documento de um índice, o documento é marcado como tal em um arquivo de exclusão especial, que na verdade é apenas um bitmap que é barato de atualizar. As estruturas do índice em si não são atualizadas.

Consequentemente, a atualização de um documento indexado anteriormente é uma exclusão seguida de uma reinserção do documento. Observe que isso significa que atualizar um documento é ainda mais caro do que adicioná-lo. Portanto, armazenar coisas como contadores que mudam rapidamente em um índice do Lucene geralmente não é uma boa ideia — não há atualização de valores no local.

Quando novos documentos são adicionados (talvez por meio de uma atualização), as alterações de índice são primeiramente armazenadas em buffer na memória. No fim, os arquivos de índice em sua totalidade são liberados (flushed) para o disco. Observe que este é o significado de “flush” no Lucene. A operação de liberação do Elasticsearch envolve um commit do Lucene e muito mais, abordado na seção Transações.

Quando liberar pode depender de vários fatores: a rapidez com que as alterações devem ser visíveis, a memória disponível para buffer, saturação de E/S etc. Geralmente, para contarmos com velocidade na indexação, buffers maiores são melhores, desde que sejam pequenos o suficiente para que sua E/S possa acompanhar². Vamos entrar um pouco mais nos detalhes na próxima seção.

Os arquivos gravados formam um segmento de índice.

Segmentos de índice

Um índice do Lucene é composto de um ou mais segmentos de índice imutáveis, que é essencialmente um “mini-índice”. Quando você faz uma busca, o Lucene faz a busca em cada segmento, filtra as exclusões e mescla os resultados de todos os segmentos. Obviamente, isso fica cada vez mais tedioso à medida que o número de segmentos aumenta. Para manter o número de segmentos gerenciável, o Lucene ocasionalmente mescla segmentos de acordo com alguma política de mesclagem à medida que novos segmentos são adicionados. O hacker do Lucene Michael McCandless tem um ótimo post explicando e visualizando a mesclagem de segmentos.³ Quando os segmentos são mesclados, os documentos marcados como excluídos são finalmente descartados. É por isso que adicionar mais documentos pode, na verdade, resultar em um índice menor: pode desencadear uma mesclagem.

O Elasticsearch e o Lucene geralmente fazem um bom trabalho ao decidir quando mesclar segmentos. As políticas do Elasticsearch podem ser ajustadas definindo configurações de mesclagem. Você também pode usar a optimize API para forçar mesclagens.

Antes de os segmentos serem liberados para o disco, as alterações são armazenadas em buffer na memória. Antigamente (antes da versão 2.3 do Lucene), cada documento adicionado realmente existia como seu próprio pequeno segmento⁴, e todos eram mesclados na liberação. Atualmente, existe um DocumentsWriter, que pode criar segmentos maiores na memória a partir de um lote de documentos. Com o Lucene 4, agora pode haver um desses por thread, aumentando o desempenho da indexação ao permitir a liberação simultânea. (Antes, a indexação tinha de esperar a conclusão de uma liberação.)

À medida que novos segmentos são criados (devido a uma liberação ou a uma mesclagem), eles também invalidam determinados caches, o que pode afetar negativamente o desempenho da busca. Caches como os de campo e filtro são por segmento. O Elasticsearch tem uma warmer-API⁵, portanto, os caches necessários podem ser “aquecidos” antes que o novo segmento seja disponibilizado para busca.

A causa mais comum para liberações com o Elasticsearch é provavelmente a atualização contínua do índice, que por padrão ocorre uma vez a cada segundo. À medida que novos segmentos são liberados, eles ficam disponíveis para busca (quase) em tempo real. Embora uma liberação não seja tão cara quanto um commit (já que não precisa esperar uma gravação confirmada), ela faz com que um novo segmento seja criado, invalidando alguns caches e possivelmente desencadeando uma mesclagem.

Quando a taxa de transferência de indexação é importante, por exemplo, quando se faz a (re)indexação em lote, não é muito produtivo gastar muito tempo liberando e mesclando pequenos segmentos. Portanto, nesses casos, geralmente é uma boa ideia aumentar temporariamente a configuração de refresh_interval ou até mesmo desabilitar a atualização automática completamente. Pode-se sempre atualizar manualmente e/ou quando a indexação termina.

Índices do Elasticsearch

“Todos os problemas na ciência da computação podem ser resolvidos por outro nível de indireção.” — David J. Wheeler

Um índice do Elasticsearch é composto de um ou mais shards, que podem ter zero ou mais réplicas. Todos esses são índices do Lucene individuais. Ou seja, um índice do Elasticsearch é composto de muitos índices do Lucene, que, por sua vez, são compostos de segmentos de índice. Quando você busca um índice do Elasticsearch, a busca é executada em todos os shards (e, por sua vez, em todos os segmentos) e mesclada. O mesmo acontece quando você busca vários índices do Elasticsearch. Na verdade, buscar dois índices do Elasticsearch com um shard cada é praticamente o mesmo que buscar um índice com dois shards. Em ambos os casos, dois índices do Lucene subjacentes são buscados.

Deste ponto em diante neste artigo, quando nos referirmos a um “índice” por si só, queremos dizer um índice do Elasticsearch.

Um “shard” é a unidade de redimensionamento básica do Elasticsearch. À medida que os documentos são adicionados ao índice, ele é roteado para um shard. Por padrão, isso é feito em round robin, com base no hash do ID do documento. Na segunda parte desta série, veremos mais sobre como os shards são movidos. É importante saber, no entanto, que o número de shards é especificado no momento da criação do índice e não pode ser alterado posteriormente. Uma apresentação mais antiga de Shay sobre o Elasticsearch explica de forma excelente por que um shard é, na verdade, um índice do Lucene completo e apresenta seus vários benefícios e compensações em comparação com outros métodos.

É possível customizar de várias maneiras os índices do Elasticsearch e para quais shards (e réplicas) as solicitações de busca são enviadas. Combinando padrões de indexação, aliases de índice e roteamento de busca e documentos, muitas estratégias diferentes de particionamento e fluxo de dados podem ser implementadas. Não vamos abordá-los aqui, mas podemos recomendar o artigo de Zachary Tong sobre customização do roteamento de documentos e a apresentação de Shay Banon sobre big data, busca e analítica. Apenas para lhe dar algumas ideias, aqui estão alguns exemplos:

• Muitos dados são baseados em tempo, por exemplo, logs, tweets, etc. Ao criar um índice por dia (ou semana, mês…), podemos limitar de forma eficiente as buscas a determinados intervalos de tempo e eliminar dados antigos. Lembre-se de que não é possível excluir algo de um índice existente com eficiência, mas excluir um índice inteiro é barato.
• Quando as buscas precisam ser limitadas a um determinado usuário (por exemplo, “buscar nas suas mensagens”), pode ser útil rotear todos os documentos desse usuário para o mesmo shard, a fim de reduzir o número de índices para busca.

Transações

O Lucene tem um conceito de transações, mas não o Elasticsearch. Todas as operações no Elasticsearch são adicionadas à mesma linha do tempo, o que não é necessariamente consistente inteiramente entre os nós, pois a liberação depende do tempo.

Gerenciar o isolamento e a visibilidade de diferentes segmentos, caches e assim por diante em índices entre nós em um sistema distribuído é muito difícil. Em vez de tentar fazer isso, a prioridade do Elasticsearch é a rapidez.

O Elasticsearch tem um “log de transações” ao qual os documentos a serem indexados são anexados. Anexar a um arquivo de log é muito mais barato do que criar segmentos, então o Elasticsearch pode gravar os documentos para indexar em algum lugar durável — além do buffer na memória, que é perdido quando ocorrem falhas. Você também pode especificar o nível de consistência necessário ao indexar. Por exemplo, você pode exigir que cada réplica tenha indexado o documento antes que a operação de indexação retorne.

Resumo

Para resumir, estas são as propriedades importantes a serem observadas em como o Lucene cria, atualiza e busca índices em um único nó:

• A forma como processamos o texto que indexamos determina como podemos fazer a busca. A análise de texto adequada é importante.
• Os índices são construídos primeiro na memória e, em seguida, ocasionalmente liberados em segmentos para o disco.
• Os segmentos do índice são imutáveis. Os documentos excluídos são marcados como tal.
• Um índice é composto de vários segmentos. Uma busca é feita em cada segmento, com os resultados mesclados.
• Os segmentos são ocasionalmente mesclados.
• Os caches de campo e filtro são por segmento.
• O Elasticsearch não tem transações.

No próximo artigo desta série, veremos como a busca e a indexação são feitas em um cluster.