Filtros de Bloom: pertinência probabilística a conjuntos sem falsos negativos

O que é

Um filtro de Bloom é um array de m bits com k funções de hash. Inserir um item define como 1 os k bits selecionados pelos seus hashes; consultar verifica esses mesmos bits. Se algum bit estiver zerado, o item nunca foi inserido; se todos estiverem definidos, o item foi inserido ou os bits foram marcados por outros itens, o que é um falso positivo. A documentação do PostgreSQL sobre o índice bloom descreve a estrutura como econômica em espaço e sujeita a reportar falsos positivos, o que exige que todo resultado do índice seja reverificado na linha real. A documentação do Redis oferece um filtro criado com uma taxa de falsos positivos desejada e uma capacidade esperada. O filtro básico não permite remoção: zerar um bit poderia apagar o rastro de outro item. Para essa necessidade existem os filtros de Bloom com contadores (counting Bloom filters) e os filtros cuckoo.

Por que importa

O filtro cabe na memória mesmo quando o conjunto completo não cabe, e responde "não" a baixo custo, o que poupa uma leitura em disco, uma ida e volta pela rede ou uma consulta ao banco de dados para chaves que certamente não existem. Engines de armazenamento usam um filtro por arquivo de dados para pular arquivos, crawlers o usam para saber se uma URL já foi vista e caches o usam para evitar consultas ao backend por chaves desconhecidas.

Como aplicar

• Dimensione o filtro a partir do número esperado de itens e da taxa de falsos positivos desejada; a taxa sobe quando o filtro se enche além da capacidade projetada, então planeje para o máximo ou use uma variante escalável.
• Trate todo positivo como "consulte o armazenamento real"; só dispense a verificação quando um falso positivo for inofensivo, como um cache miss a mais.
• Guarde o filtro junto com os identificadores das suas funções de hash, a seed e o tamanho; qualquer mudança exige reconstruí-lo a partir do conjunto completo.
• Use-o onde predominam consultas negativas (nomes de usuário desconhecidos, chaves removidas, objetos frios) e meça a parcela de consultas que ele filtra antes de mantê-lo.
• Reconstrua-o periodicamente quando o conjunto subjacente diminuir; o filtro só cresce.

Armadilhas

Derivar os k hashes de funções correlacionadas aumenta os falsos positivos. Um filtro compartilhado entre processos ou linguagens exige hashing idêntico bit a bit. Nada pode ser listado, contado ou removido. Um filtro cuja seed ou tamanho difere do usado na construção devolve respostas erradas em silêncio, em vez de erros. Dimensionar pela média em vez do tamanho máximo do conjunto anula o propósito do filtro.