O que o teste de presença informa
O filtro de Bloom é uma estrutura probabilística que testa se um item pode pertencer a um conjunto usando uma representação compacta. No filtro clássico, um resultado negativo indica que o item não foi inserido. Um resultado positivo pode ser falso, por isso a aplicação precisa confirmar a presença quando uma resposta incorreta levaria ao descarte de uma entrada válida.
Essa interpretação vale para o conjunto representado no filtro. Um registro acrescentado ao banco e ainda não incluído no filtro pode aparecer como ausente na consulta ao filtro. Você precisa manter essa representação atualizada antes de usá-la para evitar uma consulta ao banco.
Bits compartilhados entre os itens
O filtro clássico começa com uma sequência de bits em zero. As funções de hash transformam cada item em posições dessa sequência. A inserção marca essas posições com um. A consulta calcula novamente as posições e verifica os bits correspondentes, conforme a explicação do Redis.
Um bit ainda em zero comprova que aquele item não passou pela inserção. Todos os bits em um indicam presença possível, porque outros itens podem ter marcado as mesmas posições. Essa sobreposição explica os falsos positivos e impede recuperar os valores originais a partir dos bits.
Interpretar a resposta no Redis
Como exemplo de consulta, BF.EXISTS conhecidos id-42 pergunta se o identificador id-42 pode pertencer ao filtro conhecidos. O comando exige uma instalação do Redis com suporte a filtros de Bloom. Pela documentação de BF.EXISTS, na forma numérica da resposta, 1 indica presença possível e 0 indica ausência. Uma chave inexistente também produz 0.
Um serviço que verifica identificadores já cadastrados pode consultar a base completa após receber 1. Descartar a entrada apenas com esse retorno poderia eliminar um identificador novo por falso positivo. O retorno 0 só permite concluir algo sobre o banco quando o filtro existe e representa todos os registros relevantes.
O dimensionamento combina a quantidade esperada de itens com a taxa de falsos positivos pretendida. Num filtro de tamanho fixo, acrescentar itens além do previsto aumenta a chance de sobreposição. Implementações escaláveis, como a do Redis, podem acrescentar filtros internos, consumindo mais memória para acompanhar o crescimento.
Dúvidas frequentes
Perguntas frequentes sobre filtro de Bloom
- O filtro permite listar os itens inseridos?
- O filtro de Bloom clássico guarda bits compartilhados entre as representações dos itens. Essa informação permite consultar presença provável, mas não reconstruir a lista dos valores originais.
- Posso remover um item apagando seus bits?
- No filtro clássico, os mesmos bits podem representar outros itens. Apagá-los pode gerar respostas negativas incorretas. A exclusão exige outra estrutura ou uma variante que ofereça suporte a ela.
- O que significa configurar uma taxa de falsos positivos de 1%?
- A taxa expressa a probabilidade pretendida de um item ausente receber uma resposta positiva, dentro das condições de dimensionamento. Não significa que exatamente 1% de todas as respostas positivas esteja errado.
Para continuar
Recursos relacionados
Documentação
Redis: filtros de Bloom
Apresenta os comandos do filtro no Redis e relaciona a capacidade esperada à taxa pretendida de falsos positivos.
Abrir recursoSite de referência
Dev Side Studio: desenvolvimento colaborativo
O Desenvolvimento Colaborativo oferece orientação ao vivo para implementar o filtro e testar como a aplicação trata suas respostas.
Abrir recursoAplicação na formação
Vibe Coding: Do Zero ao MVP
Ao desenvolver a aplicação, você precisa interpretar os falsos positivos antes de usar o filtro para evitar consultas ou identificar entradas repetidas.
Conhecer a formação
Fontes consultadas
Referências deste verbete
Este verbete ajudou você?
Obrigado pela resposta. Ela fica salva apenas neste navegador.