Dado um nome de usuário em uma página de inscrição de usuário, como sabemos se ele já foi registrado?

Embora a consulta a um banco de dados indexado ajude, ela é lenta e incorre em chamadas de rede.

Para acelerar as coisas, podemos armazenar em cache a lista de nomes de usuário registrados em um armazenamento de chave-valor como o Redis.

No entanto, isso implica armazenar em cache milhões de registros e dobrar nossa pegada de memória.

Como podemos fazer melhor neste problema aparentemente trivial?

O filtro bloom pode ser a resposta, vamos dar uma olhada!

O que é um Filtro Bloom?

Um filtro bloom responde a uma pergunta simples,

Existe um elemento em um determinado conjunto?

Um filtro bloom é uma estrutura de dados probabilística. Dada a pergunta acima, ele gera uma das seguintes respostas

• Provavelmente sim
• 100% Não

E sua maior vantagem é que ele faz isso em tempo e espaço CONSTANTES .

Como funciona?

Um filtro bloom consiste em dois componentes

• Uma matriz de bits de tamanho N
• Várias funções de hash

Ele é primeiro inicializado como uma matriz de bits de tamanho N com todos os seus bits definidos como zero. Vamos supor que o comprimento do array seja 10 por enquanto.

Adicionando um item

Adicionar um item é trivial

• O item dito “tigre” é hash usando uma função de hash
• O hash gerado é modificado pelo comprimento da matriz para obter um índice limitado
• O índice da matriz de bits é então definido como 1

Semelhante à adição de um item, fazemos o hash do elemento usando uma função de hash e o modificamos para obter um índice limitado.

A saída é avaliada da seguinte forma,

• Se o valor do índice da matriz de bits for 0, o item NÃO está no conjunto.
• Caso contrário, o item PROVAVELMENTE está no conjunto

Armazenando um filtro de bloom

Em vez de armazenar o filtro bloom como uma matriz, podemos converter sua representação de bits em um número decimal.

Por exemplo, podemos converter um array contendo 10011em 19 e armazená-lo em um cache.

Se a lista não mudar com muita frequência, o servidor pode enviar o número decimal para o cliente, permitindo que a validação seja feita no lado do cliente.

Podemos fazer melhor?

Se a função hash gerar o índice 1 para “tigre” e “vaca”, verificar se “vaca” está no conjunto produz a resposta Sim , mesmo que não seja .

Podemos reduzir a chance de falsos positivos por meio das seguintes soluções.

• Aumentar o comprimento da matriz
• Aumente o número de funções de hash

Em vez de um índice, podemos obter vários índices usando vários hashes.

Ao adicionar um item, todos os índices obtidos serão definidos como 1.

Um item é considerado provavelmente no conjunto, somente se TODOS os índices forem definidos como 1.

Aproveitando esses métodos, poderíamos reduzir significativamente a probabilidade de falsos positivos.

Formulários

Vamos dar uma olhada em alguns exemplos da vida real.

Verifique se existe um nome de usuário em um fluxo de inscrição do usuário

• Quando um nome de usuário é criado, o nome de usuário é adicionado a um filtro bloom armazenado em um armazenamento de valor-chave.
• Quando um usuário digita um nome de usuário em uma página de inscrição de usuário, o servidor primeiro consulta o filtro bloom.
• Se o nome de usuário NÃO estiver no filtro bloom, o servidor retornará instantaneamente um erro para o cliente.
• Caso contrário, o servidor consulta e verifica no banco de dados.

• O Medium mantém um filtro bloom para cada usuário.
• Antes de recomendar um artigo, o Medium verifica se o ID do artigo existe no filtro bloom do usuário.
• Artigos que certamente NÃO estão no filtro bloom são recomendados ao usuário.

• Ao acessar um URL, o Chrome primeiro valida se o URL faz parte de uma lista maliciosa.
• Em vez de consultar o servidor do Google todas as vezes, o Google cria um filtro bloom usando uma lista maliciosa predeterminada e a envia para o navegador.
• O navegador faz o hash da URL e faz a verificação cruzada com o filtro bloom antes de acessar o site.

Embora possa haver falsos positivos , um filtro bloom é útil quando queremos saber se um item definitivamente não está em uma lista.

Pode ser usado como uma primeira camada de filtragem devido à sua eficiência no tempo e no espaço.

Espero que você ache isso útil, e vejo você no próximo!