Filtro Bloom em Java com goiaba

Bom dia a todos.

Lançamos um novo curso - “Algoritmos para desenvolvedores” , projetado para aqueles que aprimoram seu conhecimento de várias estruturas e algoritmos para processamento de dados, resolvendo problemas algébricos e problemas de programação dinâmica para várias linguagens. Hoje, estamos compartilhando uma pequena nota sobre a operação do filtro Bloom em Java.

1. Introdução

Neste artigo, veremos a estrutura do filtro Bloom da biblioteca Guava. O filtro Bloom é uma estrutura de dados probabilística com uso eficiente de memória que podemos usar para responder à pergunta “Esse elemento está no conjunto?”.

Não há falsos negativos no filtro Bloom; portanto, se ele retornar falso, você poderá ter 100% de certeza de que esse elemento não está no conjunto.

No entanto, o filtro Bloom pode retornar falsos positivos ; portanto, quando true é retornado, a probabilidade é alta de que o elemento realmente esteja no conjunto, mas a probabilidade não é 100%.

Para saber mais sobre a operação do filtro Bloom, consulte este guia.



Maven addiction

Usaremos a implementação Guava do filtro Bloom, portanto, adicionaremos a dependência Guava
A versão mais recente pode ser encontrada no Maven Central .

<dependency> <groupId>com.google.guava</groupId> <artifactId>guava</artifactId> <version>22.0</version> </dependency> 

Por que usar um filtro bloom?

O filtro Bloom foi projetado para ser econômico e rápido . Ao usá-lo, podemos esclarecer a probabilidade de respostas falsas positivas que estamos prontos para aceitar e, de acordo com a configuração, o filtro Bloom ocupará o mínimo de memória possível.

Devido à sua economia, o filtro Bloom cabe facilmente na memória, mesmo com um grande número de elementos. Alguns bancos de dados, incluindo Cassandra e Oracle, usam esse filtro para verificações iniciais antes de acessar o disco ou o cache, por exemplo, quando uma solicitação para um ID específico é recebida.

Se o filtro indicar que não há um ID, o banco de dados poderá parar de processar a solicitação e retornar ao cliente. Caso contrário, a consulta vai para o disco e retorna o item encontrado.

Criando um filtro Bloom

Suponha que desejemos criar um filtro Bloom para não mais que 500 números inteiros e que triplicamos a probabilidade de um por cento (0,01) de falsos positivos.

Para fazer isso, podemos usar a classe BloomFilter da biblioteca Guava. É necessário transferir o número de elementos relatados para o filtro e a probabilidade desejada de falsos positivos:

 BloomFilter<Integer> filter = BloomFilter.create( Funnels.integerFunnel(), 500, 0.01); 

Agora adicione alguns números ao filtro:

 filter.put(1); filter.put(2); filter.put(3); 

Adicionamos apenas três elementos e determinamos o número máximo de inserções - 500, portanto, nosso filtro Bloom deve fornecer resultados bastante precisos. Teste-o com o método mightContain() :

 assertThat(filter.mightContain(1)).isTrue(); assertThat(filter.mightContain(2)).isTrue(); assertThat(filter.mightContain(3)).isTrue(); assertThat(filter.mightContain(100)).isFalse(); 

Como o nome indica, não podemos ter 100% de certeza de que esse elemento realmente esteja no filtro se o método retornou verdadeiro.

No nosso caso, quando o mightContain() retorna true, 99% do elemento está no filtro e 1% do resultado falso positivo. Se o filtro retornar falso, você pode ter 100% de certeza de que o elemento está ausente.

Filtro Bloom excessivamente saturado

Ao projetar um filtro Bloom, é importante fornecer um valor suficientemente preciso para o número esperado de elementos. Caso contrário, nosso filtro retornará falsos positivos com muito mais frequência do que gostaríamos. Considere um exemplo.

Suponha que criamos um filtro com a probabilidade desejada de falso positivo igual a um por cento e o número esperado de elementos igual a cinco, mas depois inserimos 100.000 elementos:

 BloomFilter<Integer> filter = BloomFilter.create( Funnels.integerFunnel(), 5, 0.01); IntStream.range(0, 100_000).forEach(filter::put); 

Esperando tão poucos elementos, o filtro ocupará muito pouca memória.
No entanto, após adicionar um número muito maior de elementos, o filtro fica saturado e tem uma probabilidade maior de produzir um resultado falso positivo do que o desejado por cento.

Observe que o método mightContatin() retorna true mesmo para um valor que não inserimos anteriormente no filtro.

Conclusão

Neste tutorial rápido, analisamos a natureza probabilística da estrutura de dados do filtro Bloom - usando a implementação do Guava.

A implementação de todos esses exemplos e trechos de código pode ser encontrada no projeto GitHub .

Como é um projeto do Maven, a importação e o lançamento não devem ser difíceis.

O FIM

Estamos aguardando comentários e perguntas, que, como sempre, podem ser deixadas aqui e ir para o dia da casa aberta para o professor do curso Mikhail Gorshkov .