O problema
Quando voce cria uma conta no Google, ele precisa verificar se o username ja existe entre
bilhoes de contas.
Fazer uma busca no banco de dados para cada tecla que voce digita seria muito lento e caro.
Entao como o Google faz isso parecer instantaneo?
Imagine uma biblioteca com 10 milhoes de livros. Em vez de procurar livro por livro,
voce tem um fichario magico que diz "esse livro DEFINITIVAMENTE nao esta aqui" ou
"esse livro TALVEZ esteja aqui". So quando o fichario diz "talvez", voce vai ate a estante procurar.
Esse fichario e o Bloom Filter.
O pipeline (4 etapas)
1. Debounce
Espera voce parar de digitar (180ms) para nao fazer consultas a cada tecla
→
2. Bloom Filter
Consulta instantanea em memoria (~0.01ms). Responde "nao existe" ou "talvez existe"
→
3. Busca Prefixo
SQL no DuckDB: quantos usernames comecam com o que voce digitou?
→
4. Confirmacao DB
Busca exata no banco. So acontece se o bloom disse "talvez"
O que e um Bloom Filter?
E um array gigante de bits (0s e 1s) — neste caso,
~100 milhoes de bits (~12MB).
Para cada username no dataset, calculamos 7 posicoes no array usando funcoes hash e marcamos esses bits como 1.
Para verificar se um username existe: calculamos as mesmas 7 posicoes.
Se
todos os bits estao marcados → "talvez existe" (pode ser coincidencia).
Se
qualquer um nao esta marcado → "definitivamente nao existe" (certeza 100%).
O "talvez" acontece porque bits de usernames diferentes podem cair na mesma posicao.
Isso e o
falso positivo — esperamos que ocorra em ~0.8% dos casos.
Quando isso acontece, o resultado aparece em amarelo.
O que e DuckDB-WASM?
DuckDB e um banco de dados analitico (como SQLite, mas otimizado para consultas).
A versao WASM roda
direto no seu browser — nao precisa de servidor.
Ele le o arquivo Parquet (formato colunar comprimido) com os 10M usernames e executa SQL real.
A busca por prefixo (
LIKE 'joao%') filtra os candidatos antes da busca exata.
E como um indice telefonico: voce vai direto na letra J em vez de ler o livro inteiro.
Como o Google faz de verdade?
O Google tem ~2 bilhoes de contas Gmail. Com um Bloom Filter usando ~1.2 bytes por elemento
e FPR de ~1%, isso cabe em
~2.4GB de RAM — facilmente armazenado em qualquer servidor.
Esse filtro fica replicado em
~200 localizacoes de edge computing ao redor do mundo.
Quando voce digita um username, a verificacao acontece no servidor mais proximo de voce,
com latencia de rede minima (~1-5ms). O Bloom Filter responde em microsegundos.
So quando o filtro diz "talvez existe" e que a requisicao vai ate o banco de dados central.
Nesta demo, simulamos o mesmo pipeline: bloom filter local + banco (DuckDB-WASM) — tudo no seu browser.
Por que isso importa?
Com o Bloom Filter, ~99.2% das consultas de usernames inexistentes sao resolvidas
sem tocar no banco. Isso economiza milhoes de consultas por segundo
em sistemas como o Google. Acompanhe o contador de "consultas economizadas" abaixo em tempo real.