Entendendo filtros de Bloom com exemplos

 (llimllib.github.io)
2 pontos por GN⁺ 2025-07-01 | 1 comentários | Compartilhar no WhatsApp
  • Filtro de Bloom é uma estrutura de dados probabilística que verifica rapidamente se um elemento está em um conjunto de forma eficiente em memória
  • Ele só informa se o elemento definitivamente não está no conjunto ou se talvez esteja, com possibilidade de falso positivo
  • A estrutura básica usa um vetor de bits e várias funções de hash para definir como 1 os bits correspondentes a cada elemento
  • Taxa de erro e desempenho são determinados pelo tamanho do filtro e pela quantidade de funções de hash, podendo ser ajustados conforme o uso
  • Também são apresentados funções de hash recomendadas, métodos de configuração ideal, eficiência de espaço e casos reais de aplicação

O que é um filtro de Bloom

  • Filtro de Bloom é uma estrutura de dados para determinar de forma rápida e eficiente em memória se um determinado elemento existe em um conjunto
  • Para obter essa eficiência, o filtro de Bloom é uma estrutura probabilística, e o resultado da verificação se divide entre "definitivamente não está no conjunto" ou "pode estar no conjunto"
  • A estrutura central do filtro de Bloom é um vetor de bits
  • Ao adicionar um elemento, ele é processado por hash várias vezes, e os bits nesses índices são definidos como 1
  • Se os bits correspondentes aos índices produzidos por cada função de hash forem todos 1, considera-se que o elemento "pode existir"; caso contrário, ele é tratado como "definitivamente não existe"

Exemplo do funcionamento

  • Várias funções de hash (ex.: Fnv, Murmur) mapeiam um elemento para vários índices de bits
  • Ao adicionar um elemento, os bits nos índices calculados são alterados para 1
  • Ao verificar a existência de um elemento específico, se os índices calculados da mesma forma com as mesmas funções de hash forem todos 1, considera-se que ele "pode existir"
  • Se ao menos um desses bits for 0, é possível afirmar com certeza que ele "não está no conjunto"
  • Por isso, existe a possibilidade de falso positivo

Tópicos avançados

Atenção: o autor não tem experiência prática de aplicar filtros de Bloom em serviços de grande escala

Escolha da função de hash

  • Recomenda-se usar funções de hash independentes e com distribuição uniforme
  • Funções de hash criptográficas (como sha1) não são adequadas por serem lentas
  • Exemplos de funções de hash rápidas e simples: Murmur, xxHash, Fnv, HashMix etc.
  • Em um caso real, a troca de md5 por murmur resultou em um ganho de velocidade superior a 800%

Como definir o tamanho do filtro de Bloom

  • Quanto maior o tamanho do filtro (m), menor a taxa de falso positivo
  • A taxa de falso positivo geralmente pode ser aproximada por (1-e^(-kn/m))^k
  • É preciso definir adequadamente a quantidade esperada de elementos (n), o tamanho do filtro (m) e o número de funções de hash (k)

Quantas funções de hash?

  • Quanto mais funções de hash, mais lenta fica a operação e mais rápido o filtro se enche
  • Se forem poucas demais, a taxa de falso positivo aumenta
  • O valor ideal de k é calculado como (m/n)ln(2)
  • No projeto, o processo é o seguinte:
    • Estimar a quantidade esperada de elementos n
    • Definir o número de bits m
    • Calcular o k ideal
    • Verificar se a taxa de erro desejada foi atingida; se não, ajustar m

Desempenho e eficiência de espaço

  • No filtro de Bloom, adição de elementos/verificação de existência têm complexidade de tempo O(k)
  • A eficiência de espaço é determinada pela faixa de erro aceitável e pelo intervalo de elementos
  • Se não for possível prever nem aproximadamente o intervalo de elementos, uma tabela hash ou um filtro de Bloom escalável pode ser uma opção melhor

Casos de uso

  • Para exemplos detalhados de uso, consulte Wikipedia
  • C. Titus Brown apresenta casos de aplicação de filtros de Bloom em bioinformática

Materiais de referência

Leituras relacionadas

1 comentários

 
GN⁺ 2025-07-01
Comentários no Hacker News
  • Tenho a sensação de que este texto é perfeito para gente como eu. Já tinha ouvido o nome antes, mas sempre deixava para pesquisar depois e acabava adiando. Agora finalmente fui ver por causa do texto, e pareceu exatamente a introdução que eu queria
    • Conheci Bloom filter pela primeira vez ao implementar a busca no iBooks. Já faz mais de 10 anos
    • Bloom filter é realmente divertido. Quando aparece um problema em que um Bloom filter é necessário, dá até empolgação, mas é uma pena que isso aconteça pouco dependendo do domínio
  • Uma sugestão para o autor. A parte interativa ficou ótima. Para ajudar a entender melhor as características do Bloom filter, seria legal mostrar um exemplo em que duas strings causam colisão de hash, pedir para inserir uma e depois colocar a outra na segunda caixa de entrada. Assim fica fácil entender por que surge aquele resultado característico de "não dá para ter certeza de que está no conjunto, mas talvez esteja"
    • Como exemplo, "bloom" e "demonstrators " (incluindo o espaço final) colidem em fnv: 7, murmur: 12
  • Na universidade, em 2009, implementei um Bloom filter em CUDA. Meu orientador tinha vindo da Nvidia. Mesmo assim, minha carreira acabou indo para um caminho totalmente sem relação com programação em GPU. Às vezes penso que, se tivesse feito outras escolhas, talvez pudesse ter ganhado 100 milhões de dólares
    • Como a ideia de ciência da computação é de 1970, provavelmente isso não teria sido possível. Dá a impressão de que as ideias relacionadas a GPGPU já tinham sido suficientemente exploradas. Eu também implementei Hashcash em GPU há 10 anos, e olhando hoje isso parece valer quase zero
    • Depois de portar um algoritmo de machine learning para CUDA como projeto de conclusão de curso, achei que não era nada demais e mudei de rumo para programação embarcada
    • Tive uma experiência parecida. Em 2009, com uma GeForce 8 e CUDA v1(!), provavelmente fui um dos primeiros a criar um toolkit de bioinformática otimizado para GPU. Fiz só por curiosidade e depois segui um caminho completamente diferente, perdendo uma chance de ganhar muito dinheiro
    • Um comentário em tom de piada dizendo que teria ganhado ainda mais dinheiro se tivesse comprado Bitcoin
  • Tenho um truque de que gosto muito. Para um pequeno set que pode ter poucos elementos, mas no qual a checagem de pertinência é frequente, coloco junto um Bloom filter de 64 bits com uma função de hash bem simples. Parece bobo, mas o custo é tão baixo que dá para usar quase como uma aposta. Se não funcionar, só adiciona algo como 10ns à checagem de pertinência ou à inserção; se funcionar bem, pode reduzir enormemente a quantidade de trabalho
    • O Chromium também usa esse tipo de truque em vários lugares. O texto só menciona Safe Browsing, mas na camada Blink também se usa muito rapidhash e esses microfiltros. Exemplos: querySelector(), pré-filtro de dicionário para lookup de hash em buckets de CSS, rejeição rápida na busca por atributos Aria para acessibilidade. Filtros pequenos de 32 e 64 bits também funcionam bem na prática. Bloom filters maiores também são usados adequadamente, e eu mesmo adicionei esse tipo de recurso
  • Recentemente usei Bloom filter em um recurso anti-spam para mensagens de log. Eu fazia hash das mensagens e colocava no filtro; se já estivessem no filtro, não eram exibidas. Periodicamente eu zerava todos os bits do filtro. Nem era preciso limpar todos os bits atomicamente: mesmo que alguns bits fossem apagados enquanto mensagens chegavam, o efeito era só a mensagem voltar a aparecer no log. Antes eu mantinha contadores separados por mensagem, mas essa abordagem foi muito mais eficiente. Foi um uso real de Bloom filter de que fiquei bastante satisfeito
  • Como exemplo de visualização de Bloom filter, há um bom material na parte final desta página
  • Recomendo outro texto introdutório sobre Bloom filter, escrito por Eli Bendersky. Se quiser se aprofundar, veja aqui
  • Acho que quase 95% dos conceitos necessários para entender Bloom filter, set e tabela hash se sobrepõem. set é uma tabela hash em que só importam as chaves, e Bloom filter é um set que explora ativamente a característica de colisão do hashing. Usa funções de hash feitas para provocar colisões com facilidade. Se uma determinada chave já foi inserida, ela sempre vai bater. Mas pode existir outra chave com o mesmo valor de hash. Então isso não é um bug, e sim uma característica intencional
    • Eu também costumo pensar em Bloom filter como uma tabela hash da qual os dados em si foram removidos, ficando só o rastreamento dos buckets. Fico feliz de ver que não sou o único com essa forma de pensar
    • Seria bom complementar a explicação sobre o fato de o Bloom filter usar várias funções de hash para reduzir colisões. Por exemplo, se houver 3 funções de hash, só se considera que está no set quando as 3 batem. Essa estrutura reduz a probabilidade de falso positivo, enquanto falso negativo nunca acontece
    • Se você entendeu Bloom filter, provavelmente também vai conseguir entender logo implementações de random projection ou de Locality Sensitive Hashes
  • Durante a depuração de um pico de leituras no Cassandra, mergulhei fundo no uso de Bloom filter. Estava estranho haver tantas consultas a sstable para chaves que nem existiam. Só depois entendi o papel do Bloom filter anexado a cada sstable. A taxa padrão de falso positivo era 0.1, alta demais para o nosso caso. Quase tudo era cache miss, e os falsos positivos geravam muitas consultas inúteis. Ao baixar a taxa para 0.01, o uso de memória aumentou um pouco, mas as leituras desnecessárias caíram bastante, e a latência de leitura p99 melhorou de 16% a 18%
  • Gosto muito de Bloom filter. Quando falo de tecnologia, sempre faço questão de apresentar três conceitos centrais: Bloom filter, Random Weight Hashing (Rendezvous Hashing, Highest Random Weight Hashing) e Cumulative flow diagram. Acho esses três conceitos essenciais para operar sistemas distribuídos complexos
    • Também acho que a estrutura de tabela hash distribuída é um tema igualmente importante. Por exemplo, arquiteturas como circle, chord, CAN e kademlia