Arquitetura de software · Escala e desempenho · 5 min de leitura
Bloom filters: “com certeza não está” em poucos bytes
Uma estrutura probabilística que responde se um item talvez esteja num conjunto — sem falsos negativos — usando uma fração da memória.
Arraste para o lado para ver o diagrama inteiro.
Como funciona
Um vetor de m bits começa zerado. Para inserir, calculam-se k hashes do item e ligam-se essas k posições. Para consultar, verificam-se as mesmas posições: se alguma é 0, o item não está; se todas são 1, o item provavelmente está (outros itens podem ter ligado os mesmos bits). Com cerca de 10 bits por item, a taxa de falso positivo fica perto de 1%.
Onde aparece
- Bancos (LSM-trees, Bigtable, Cassandra): evitam ler arquivos do disco que certamente não contêm a chave.
- Caches e CDNs: não guardar itens vistos uma única vez.
- Verificações rápidas: nome de usuário já usado, URL maliciosa conhecida, artigo já recomendado.
Limites
Não dá para listar os itens nem remover (a variante counting permite remoção com mais memória). O tamanho precisa ser planejado para o número esperado de itens; passando disso, os falsos positivos crescem. Sempre confirme o “talvez” na fonte da verdade quando o erro importar.
Em resumo
- Sem falsos negativos; falsos positivos controlados.
- ~10 bits por item ≈ 1% de erro.
- Evita leituras de disco e consultas caras.
- Não lista nem remove itens (na versão básica).