Você já passou por isso: está criando uma conta em um serviço gigante (como o Gmail), digita um nome de usuário e, antes mesmo de terminar de preencher o formulário, aparece a mensagem:
"Esse nome de usuário já está em uso."
Recentemente vi essa clássica pergunta de System Design:
"Existem bilhões de usuários. Como o sistema consegue responder tão rápido se um nome já existe?"
A primeira reação de muita gente é pensar em banco de dados, cache ou Redis. Mas, em escala massiva, consultar sistemas de armazenamento para cada validação pode sair caro.
Uma solução clássica para esse tipo de problema é o Bloom Filter.
O que é um Bloom Filter?
É uma estrutura de dados probabilística que responde duas perguntas:
- Definitivamente não existe
- Talvez exista
E essa diferença é o que a torna tão poderosa.
Quando um novo usuário é criado, o identificador passa por algumas funções de hash que marcam posições em um grande array de bits.
Na validação, o mesmo processo é executado:
- Se algum dos bits esperados estiver em 0, o sistema sabe com 100% de certeza que aquele usuário não existe.
- Se todos estiverem em 1, o sistema responde: "Talvez exista". Nesse caso, uma consulta real ao banco ou cache é feita para confirmação.
O Bloom Filter nunca produz falsos negativos, mas pode produzir falsos positivos.
Exemplo rápido
Imagine que já existem os usuários:
- joao123
- maria99
Após serem cadastrados, algumas posições em um grande array de bits ficam marcadas como 1.
Agora alguém tenta registrar:
pedro_dev
O sistema calcula os hashes desse nome e verifica as posições correspondentes.
Se encontrar pelo menos um bit em 0, já sabe imediatamente que esse usuário não existe.
Se todos os bits estiverem marcados como 1, o resultado é:
"Talvez exista"
Somente nesse momento uma consulta real ao banco ou cache é realizada para confirmar.
Por que isso é interessante?
Na maioria dos sistemas, grande parte das verificações resulta em itens que não existem.
Em vez de consultar banco ou cache para todas as requisições, o Bloom Filter atua como uma primeira camada extremamente barata em memória e CPU, eliminando rapidamente boa parte das consultas desnecessárias.
Por isso ele aparece com frequência em sistemas distribuídos, bancos de dados, caches, CDNs e mecanismos de busca.
Curiosidade: embora ninguém fora da empresa saiba exatamente como serviços como Gmail implementam esse fluxo internamente, Bloom Filters são uma das soluções clássicas ensinadas em System Design para resolver problemas desse tipo em larga escala.
E você? Já utilizou Bloom Filter em produção ou normalmente resolve esse tipo de problema apenas com cache e banco de dados?
SOCIAL SHARE CARD GENERATOR