Muitas queries full-text realtime em stream com grande volume

[Juan Lopes]

Galera, desculpe pela pergunta longa, mas não consegui forma mais sucinta de explicar o meu problema.

Contexto:

Estou desenvolvendo um sistema que indexa full-text um grande volume de dados. Estou usando o Lucene (para Java) como backend. Esse sistema já é capaz de indexar (em cluster) algumas dezenas de TB por dia. Cada nó do cluster atualmente suporta 1~2TB/dia a uma taxa de 10~20MB/s. Cada registro desse sistema é relativamente pequeno (variando entre 100 e 500 bytes).

Como o volume de indexação desse sistema é muito grande, algumas otimizações foram feitas para limitar o tamanho do índice. Não estou armazenando termvectors, freqs, norms, nem nada do Lucene além do necessário. Basicamente meu índice só é capaz de dizer quais documentos batem com uma busca (de forma binária, sem score).

Além disso, como os registros são bem pequenos (e de cardinalidade bem alta), evitamos o overhead da criação de documentos no lucene agrupando esses registros em pacotes de tamanho configurável. Normalmente são pacotes com 1000 ou 10000 registros. Ou seja, a cada 1000 registros, é gerado apenas um documento no Lucene com todos os termos para todos os registros do pacote. E cada pacote é armazenado no disco de forma independente. Com isso, conseguimos manter o índice do Lucene ocupando cerca de 0.5% do total de dados indexados. Está sendo suficiente.

Assim, beneficiando a indexação, penalizamos a busca ao exigir que a cada busca, o Lucene seja apenas um guia para indicar quais pacotes abrir, mas é necessário verificar em cada pacote quais mensagens dele de fato batem com a busca que foi realizada.

Além disso, vários processos do sistema exigem que seja possível verificar para cada registro, se uma certa busca do Lucene dá match com ele.

Então:

Tenho um mecanismo bastante rudimentar fora do Lucene para verificar para cada registro se uma query do Lucene dá match. Basicamente consiste em percorrer o modelo de objetos da query do Lucene criando objetos correspondentes que simulem essa query em real-time. Mais uma vez: sem usar os documentos do Lucene. Os objetos dessa query eu chamo de "predicates" e são basicamente um objeto que tenha um método "evaluate" para dizer se um conjunto de tokens aceita ou não essa query. O correspondente ao TermQuery é algo como isso: https://gist.github.com/2510623

Até agora, isso estava sendo suficiente, pois o volume de queries era bastante baixo, porém, mais processos começaram a precisar desse mecanismo para verificar as mensagens em tempo real. Processos que executam ainda durante a indexação (sem relação com o usuário), como agregação e enriquecimento de mensagens e o que era algo simples começou a ficar bastante custoso na feature principal do sistema (que repito, é a indexação).

O ponto aqui não é o fato de que um predicate seja custoso, mas sim que existam várias queries parecidas rodando sobre o mesmo set de dados repetidamente.

Percebemos também que apesar de um conjunto de 1000 documentos geralmente ter cerca de 30000 tokens, apenas cerca de 2000 deles são distintos. E pensamos que talvez valha a pena aproveitar isso.

A pergunta:

Existe alguma forma conhecidamente fácil de gerar um índice (fora do Lucene) volátil pra cada um desses pacotes e consultá-los de forma barata. Quero dizer, percorrer uma única vez todos os termos de todos os registros de um pacote para gerar um índice reverso. Índice que possa ser usado por algumas centenas de consultas para determinar quais registros num pacote batem com ela sem ter que percorrer novamente os tokens?

Tenho na manga, caso nada funcione, como implementar na mão uma árvore de sufixos (bastante parecida com a que o Lucene faz, mas otimizada para o meu caso), já até fiz um protótipo e funciona bem, mas quero fugir um pouco do NIH e ver se já existe alguma solução de consulta em realtime que seja tão eficiente quanto o próprio Lucene.

O que é importante ter em mente:

A taxa de indexação atualmente é de cerca de 20MB/s, o que significa entre 100~200 mil registros por segundo. Ou seja, 100~200 pacotes por segundo.

Já tentamos usar o próprio Lucene com um RAMDirectory para gerar esse índice. Mas o overhead de criação do índice é alto, não rola fazer 150~200 vezes por segundo.

As queries são queries do Lucene. Ou seja, não basta dizer se o documento tem ou não aquele termo. Tem que suportar PrefixQuery, WildcardQuery, FuzzyQuery, RangeQuery, etc.

--
https://github.com/juanplopes

[Renato Cantarino]

Juan,
Essa questão é muito complexa.
poste essa duvida no dotnetscientist

Em 27/04/12, Juan Lopes<m...@juanlopes.net> escreveu:

> Galera, desculpe pela pergunta longa, mas não consegui forma mais sucinta
> de explicar o meu problema.

> *
> *
> *Contexto:*

>
> Estou desenvolvendo um sistema que indexa full-text um grande volume de
> dados. Estou usando o Lucene (para Java) como backend. Esse sistema já é
> capaz de indexar (em cluster) algumas dezenas de TB por dia. Cada nó do
> cluster atualmente suporta 1~2TB/dia a uma taxa de 10~20MB/s. Cada registro
> desse sistema é relativamente pequeno (variando entre 100 e 500 bytes).
>
> Como o volume de indexação desse sistema é muito grande, algumas
> otimizações foram feitas para limitar o tamanho do índice. Não estou
> armazenando termvectors, freqs, norms, nem nada do Lucene além do
> necessário. Basicamente meu índice só é capaz de dizer quais documentos
> batem com uma busca (de forma binária, sem score).
>
> Além disso, como os registros são bem pequenos (e de cardinalidade bem
> alta), evitamos o overhead da criação de documentos no lucene agrupando
> esses registros em pacotes de tamanho configurável. Normalmente são pacotes
> com 1000 ou 10000 registros. Ou seja, a cada 1000 registros, é gerado
> apenas um documento no Lucene com todos os termos para todos os registros
> do pacote. E cada pacote é armazenado no disco de forma independente. Com
> isso, conseguimos manter o índice do Lucene ocupando cerca de 0.5% do total
> de dados indexados. Está sendo suficiente.
>
> Assim, beneficiando a indexação, penalizamos a busca ao exigir que a cada
> busca, o Lucene seja apenas um guia para indicar quais pacotes abrir, mas é
> necessário verificar em cada pacote quais mensagens dele de fato batem com
> a busca que foi realizada.
>
> Além disso, vários processos do sistema exigem que seja possível verificar
> para cada registro, se uma certa busca do Lucene dá match com ele.
>

> *Então:*

>
> Tenho um mecanismo bastante rudimentar fora do Lucene para verificar para
> cada registro se uma query do Lucene dá match. Basicamente consiste em
> percorrer o modelo de objetos da query do Lucene criando objetos
> correspondentes que simulem essa query em real-time. Mais uma vez: sem usar
> os documentos do Lucene. Os objetos dessa query eu chamo de "predicates" e
> são basicamente um objeto que tenha um método "evaluate" para dizer se um
> conjunto de tokens aceita ou não essa query. O correspondente ao TermQuery
> é algo como isso: https://gist.github.com/2510623
>
> Até agora, isso estava sendo suficiente, pois o volume de queries era
> bastante baixo, porém, mais processos começaram a precisar desse mecanismo
> para verificar as mensagens em tempo real. Processos que executam ainda
> durante a indexação (sem relação com o usuário), como agregação e
> enriquecimento de mensagens e o que era algo simples começou a ficar
> bastante custoso na feature principal do sistema (que repito, é a
> indexação).
>
> O ponto aqui não é o fato de que um predicate seja custoso, mas sim que
> existam várias queries parecidas rodando sobre o mesmo set de dados
> repetidamente.
>
> Percebemos também que apesar de um conjunto de 1000 documentos geralmente
> ter cerca de 30000 tokens, apenas cerca de 2000 deles são distintos. E
> pensamos que talvez valha a pena aproveitar isso.
>

> *A pergunta:*

>
> Existe alguma forma conhecidamente fácil de gerar um índice (fora do
> Lucene) volátil pra cada um desses pacotes e consultá-los de forma barata.
> Quero dizer, percorrer uma única vez todos os termos de todos os registros
> de um pacote para gerar um índice reverso. Índice que possa ser usado por
> algumas centenas de consultas para determinar quais registros num pacote
> batem com ela sem ter que percorrer novamente os tokens?
>
> Tenho na manga, caso nada funcione, como implementar na mão uma árvore de
> sufixos (bastante parecida com a que o Lucene faz, mas otimizada para o meu
> caso), já até fiz um protótipo e funciona bem, mas quero fugir um pouco do
> NIH e ver se já existe alguma solução de consulta em realtime que seja tão
> eficiente quanto o próprio Lucene.
>

> *O que é importante ter em mente:*

>
> A taxa de indexação atualmente é de cerca de 20MB/s, o que significa entre
> 100~200 mil registros por segundo. Ou seja, 100~200 pacotes por segundo.
>
> Já tentamos usar o próprio Lucene com um RAMDirectory para gerar esse
> índice. Mas o overhead de criação do índice é alto, não rola fazer 150~200

> vezes por *segundo.*

>
> As queries são queries do Lucene. Ou seja, não basta dizer se o documento
> tem ou não aquele termo. Tem que suportar PrefixQuery, WildcardQuery,
> FuzzyQuery, RangeQuery, etc.
>
> --
> https://github.com/juanplopes
>

> --
> Você recebeu esta mensagem porque faz parte do grupo .Net Architects
> hospedado no Google Groups.
> Para postar envie uma mensagem para dotnetar...@googlegroups.com
> Para sair do grupo envie uma mensagem para
> dotnetarchitec...@googlegroups.com
> Para mais opções visite o grupo em
> http://groups.google.com/group/dotnetarchitects?hl=pt-br

[Diego Caxito]

Olá Juan, você já avaliou o uso do Solr e conectar como um client dele ao invés do Lucene puro?

--

[Juan Lopes]

Diego,

Sim, o Solr e o Elastic Search. O problema é que são dezenas de TB por dia. Isso significa dezenas ou centenas de bilhões de registros espalhados em centenas de milhões de documentos.

Não posso arcar com indexar via REST. E o tempo de indexação pra mim é crucial.

--
https://github.com/juanplopes

[Rodrigo Kumpera]

Você quer gerar um índice diferente e ainda usar o lucene para consultas? Meio enrolado.

O problema só piora ao tentar suportar toda variedade de queries do lucene em cima disso.

Provavelmente você vai precisar mais que simplesmente árvores de sufixos pois muita coisa

não rola pesquisar só com elas.

2012/4/27 Juan Lopes <m...@juanlopes.net>

--

[Juan Lopes]

Na verdade o objetivo nem é a consulta em si. Depois de armazenado o registro, esse índice auxiliar não tem tanta utilidade, já que querying não é a funcionalidade crítica do sistema. A questão é que enquanto o registro ainda está sendo processado, diversos processos verificam se o registro atende a certas queries. Como são muitas consultas sobre o stream, queria uma estrutura de dados que fosse otimizada para respondê-las, mas que fosse volátil e de criação mais barata que o índice do lucene.

E eu errei na pergunta, não é uma árvore de sufixos, é uma trie. E pelo que vi, dá pra responder a maior parte das consultas do lucene com ela.

2012/4/29 Rodrigo Kumpera <kum...@gmail.com>

--
https://github.com/juanplopes

[Rodrigo Kumpera]

Você está implementando complex event processing então.

Aplicar todas queries em todos registros é tão mais custoso que construir o índice?

Para algumas dúzias de queries, acho pouco provavel que isso faça tanta diferença.

Já tentou o caminho contrário? Compilar as queries de algo genérico para algo eficiente

e aplicá-las usando tiling (eg, em blocos pequenos o suficiente de entrada p/ caberem no L1)?

Compilar a maioria das formas de queries é mais fácil que construir índices e aplicá-las de qualquer forma.

2012/4/29 Juan Lopes <m...@juanlopes.net>

[Juan Lopes]

Mais ou menos. Temos um outro produto de CEP que funciona bem. A questão é que CEP funciona bem para correlacionar eventos temporais. Mas para esse produto, absolutamente tudo é full-text e não precisamos de correlacionamento. É algo mais simples, mas ao mesmo tempo depende de uma disciplina que a maior parte das ferramentas de CEP não domina muito bem.

Quanto a ter blocos pequenos que caibam em L1, não tenho certeza se sei como fazer isso com strings, que normalmente possuem uma péssima localidade de referência.

2012/4/30 Rodrigo Kumpera <kum...@gmail.com>

--
https://github.com/juanplopes

[Rodrigo Kumpera]

2012/4/30 Juan Lopes <m...@juanlopes.net>

Mais ou menos. Temos um outro produto de CEP que funciona bem. A questão é que CEP funciona bem para correlacionar eventos temporais. Mas para esse produto, absolutamente tudo é full-text e não precisamos de correlacionamento. É algo mais simples, mas ao mesmo tempo depende de uma disciplina que a maior parte das ferramentas de CEP não domina muito bem.

Quanto a ter blocos pequenos que caibam em L1, não tenho certeza se sei como fazer isso com strings, que normalmente possuem uma péssima localidade de referência.

Serialize tudo em um bloco só de memória e seja feliz. 

[Juan Lopes]

Só um follow up rápido.

Acabamos implementando uma Patricia Trie mesmo. Bem parecida com a que o Lucene implementa, mas extremamente lightweight e bem simples. Implementamos também várias navegações na trie, correspondentes às queries do Lucene. Implementamos term, prefix, wildcard, fuzzy, range e boolean queries.

A implementação da trie tem cerca de 200 linhas: https://gist.github.com/2760589

Uma query de prefixo, por exemplo: https://gist.github.com/2760594

Os documentos são indexados em blocos, e cada query retorna um bitset que diz se um documento deu match ou não. A trie é só a estrutura mais básica. Existe uma estrutura superior que guarda uma coleção de tries. Uma para cada field. E ela implementa uma query de mais alto nível, que chamamos de predicate.

Temos um BooleanPredicate que é equivalente à BooleanQuery do Lucene, mas esse trabalha em cima de bitsets retornados pelas navigations: https://gist.github.com/2760602

O resultado é assustadoramente animador. Se "n" é o número de documentos, "t" é a média de termos por documento e "q" o número de consultas ativas, transformamos um processo O(n*t*q) em O(n*t + q) e isso significa que agora consultas em tempo real tem quase custo zero.

Infelizmente ainda não conseguimos isolar isso completamente para transformar em opensource, mas esse é o plano para o futuro.

[Fábio Nascimento]

Juan,

    Fico feliz de ter compartilhado a sua evolução, estou ainda tentando processar e lendo a partir dos links, mas tenho uma pergunta (não sei se vai soar boba ou não) como você faz para realizar testes para saber o quanto de ganho você teve ? Através de Profiling ou você tem alguma outra técnica ?

Obrigado !

Att.:
Fábio Nascimento | 

"O estudo da ciência da computação não consegue transformar qualquer um em um excelente programador, da mesma forma que o estudo de tintas e pinceis não transforma qualquer um em um excelente pintor." – Eric S. Raymond

[Juan Lopes]

Fábio,

Nós temos uma suite de testes de performance automatizados. Mas ela serve mais para medir comportamentos extremos de uso de memória, file handlers, inodes, etc. É só pra garantir que o sistema não vai quebrar em produção por motivos extremos.

Para testar esse tipo de performance, geralmente usamos uma passa padrão de testes, que veio de dados reais. É uma massa bem razoável. Usamos os mesmos arquivos durante o projeto para medir o progresso geral da performance do sistema. Mas tudo isso é manual.

Devo falar mais sobre isso no DNAD.

2012/5/21 Fábio Nascimento <fabio.o.n...@gmail.com>

--
https://github.com/juanplopes

[Fábio Nascimento]

Juan,

Obrigado !

É uma pena, pois não estarei no DNAD ...

Att.:
Fábio Nascimento | 

"O estudo da ciência da computação não consegue transformar qualquer um em um excelente programador, da mesma forma que o estudo de tintas e pinceis não transforma qualquer um em um excelente pintor." – Eric S. Raymond