Estrutura de dados: Você sabe o que é Bloom Filter?

Numa oportunidade anterior falamos sobre o sistema de código aberto Cassandra, que é usado para gerenciar grandes volumes de dados em tempo real. Isso permite uma resposta rápida quando acontecem falhas. A questão é que esse sistema, que é extremamente rápido em escrituras e leituras, deve em boa parte suas características a uma estrutura de dados chamada Bloom Filter.

Essa ferramenta é uma maneira muito eficiente de perguntar se tem dados num conjunto ou não (usado por Cassandra para evitar muitos acessos sem resultados). Em outras palavras está desenhado para nos dizer, instantaneamente, se um elemento está presente num conjunto.

Trata-se de um algoritmo que pode mostrar falsos positivos, mas nunca falsos negativos. Conhecer essa probabilidade de ocorrência desses erros e fazer consultas estando ciente que podem acontecer é vital na hora de construir as gigantescas bases de dados que fazem possíveis numerosas aplicações.

Como funciona?

Ele atua com dois elementos. Um chamado de array de m bits, inicializado a zero, e um conjunto de k funções hash que, colocado um dado, gerará números entre zero e m-1.

Quando um especialista insere um dado, ele vai passar pelas funções hash, que indicarão a posição do array onde se mudará seus valores a 1. É um processo complexo, mas que servirá quando chegarem novas cadeias e queiramos saber se um elemento há ou não dentro de um conjunto.

O principal é ficar seguro que algumas posições do array gerada por algumas funções hash nos dê zero.

É como um jogo de quem é quem, mas com muito suspeitos. O jogador “A” agrega suspeitos, enquanto o jogador “B” questiona sobre o jogador “A” em base aos atributos dos suspeitos. Levando isso para área técnica, esses suspeitos seriam os dados e seus atributos as funções hash. A lista total de atributos que tenha o jogador “A” seria o array de bits.

Vejamos um exemplo:

Mark Zuckerberg

• Atributos: “Rico”, “Jovem” e “Americano”.

Tom Hanks

• Atributos: “Rico”, “Ator” e “Americano”.

Vamos supor que o jogador “A” coloca como suspeito o Mark Zuckerberg, o que significa que agora esse jogador tem como qualidades: “Rico”, “Jovem” e “Americano”. Assim quando o jogador “B” perguntar por Tom Hanks, apesar dele ter as qualidades “Rico” e “Americano” não tem “Jovem”, sabemos então que o Tom Hanks não é um dos suspeitos.

É assim como funciona Bloom Filter, mas com muitos mais dados e jogadores. Todo um exército de informação ao serviço dos especialistas.