O que é um Bloom Filter?

Os filtros Bloom são uma função de análise de informações. Isso permite determinar se um dado ou conjunto deles está armazenado em um banco de dados ou conjunto distribuído de dados. Suas principais características são a extrema eficiência nesta tarefa. É por essas características que são amplamente utilizadas em sistemas onde é necessário verificar a existência de um dado específico dentro de um vasto conjunto destes.

Um das ferramentas mais úteis para analisar informações probabilísticas e unidirecionais são os filtros bloom. Esses filtros bloom são ferramentas ou instrumentos que nos permitem analisar grandes quantidades de informações probabilísticas. Isso para saber se um elemento ou dado faz parte de um conjunto. Este é um recurso extremamente útil em momentos em que temos que lidar com grandes volumes de dados. Especialmente quando essas informações não podem ser processadas manualmente de forma rápida.

É por isso que, graças aos filtros bloom, criptomoedas como Bitcoin tem a função de Porta-moedas SPV. Mas também vemos essa função em criptomoedas como Ethereum onde eles permitem que você pesquise informações em seu blockchain eficientemente.

E isso graças ao fato de que os filtros Bloom nos permitem ter apenas dois resultados: falsos positivos ou negativos. Ou seja, ao implementar os filtros bloom, você pode saber de forma rápida e eficiente se certos elementos podem existir na memória ou se definitivamente não existem. Resultados falsos positivos revelam a possibilidade de um item ou dado fazer parte de um conjunto. Enquanto os resultados negativos concluem definitivamente que o elemento ou dado não está incluído no conjunto avaliado. A ferramenta, ao mesmo tempo, nos permite excluir completamente os falsos negativos, o que facilita muito a análise dos dados.

Mas o que levou à criação dos filtros bloom? Qual é a relação deles com o mundo do blockchain? Bem, veremos isso abaixo.

Assim, o desenho desses filtros Bloom permite o manuseio de grandes bancos de dados ou informações em alta velocidade. E, ao mesmo tempo, é feito um uso eficiente do espaço de armazenamento. Isso se deve ao fato de que os filtros bloom não requerem conter ou armazenar os próprios elementos ou dados, mas simplesmente verificar se eles estão ou não dentro do conjunto. Uma operação de dados somente leitura que permite alto desempenho e amplos recursos de processamento de informações.

Como os filtros bloom são configurados?

Filtros Bloom têm o que é conhecido como estrutura de dados de matriz de entrada. Este array tem um comprimento ou capacidade de armazenamento tão grande quanto necessário. Isto quer dizer que no momento de construir um filtro bloom, você pode definir quanto tempo o comprimento do filtro será, como requerido. Definir quantas entradas serão adicionadas à estrutura de dados de base e quantas funções de hash Eles serão usados ​​dentro do filtro, associando-se a cada uma dessas entradas.

Da mesma forma, no momento de sua concepção deve-se levar em consideração que o intervalo de funções hash deve começar em 0 e culminar no número do número de entradas existentes menos 1. Ou seja, se um filtro bloom for projetado para 10 entradas, ele começará com o número 0 e terminará no número 9. Se um for projetado para 20 entradas, o filtro bloom começará no número 0 e terminará no número 19. Uma prática de design computacional que busca otimizar ao máximo os recursos de processamento de filtros.

Da mesma forma, quando o conjunto de entradas existentes encontra todos os seus valores em 0, significa que os dados não estão no filtro bloom. Portanto, está vazio. Assim, no momento em que dados ou elementos forem adicionados ao filtro, a informação será passada pelas respectivas funções hash que colocarão essa informação no local correspondente dentro do filtro bloom. Portanto, esses locais refletirão o valor 1, indicando que contêm elementos que já foram analisados.

A partir desses valores, é construída a operação dos filtros bloom, que explicaremos em detalhes a seguir.

Como funcionam os filtros bloom

Assim, uma vez configurado o filtro bloom, podemos começar a verificar se um elemento faz parte do conjunto ou não. Para conseguir isso, o processo a seguir começa com a passagem da entrada de dados desejada para o algoritmo do filtro bloom. Ou seja, pegamos os dados do sistema e os processamos usando as funções hash do sistema. Essas funções hash retornarão duas posições como resultado.

Esses hashes e as posições que eles retornam são armazenados e relacionados aos dados que os originam. Assim, o filtro continua coletando informações, aplicando funções hash sobre elas e armazenando os resultados de sua operação. Porém, este processo possui um procedimento adicional que maximiza sua eficiência e melhora o tempo de resposta de sistemas que aplicam este tipo de filtros em suas estruturas.

Primeiro, se os dados que foram passados ​​para o filtro passarem pelas funções hash e retornarem posições com valores diferentes de 0, o item estará dentro do conjunto. Isso é conhecido como positivo, indicando a existência daquele elemento no conjunto. Também pode ser o caso em que os hashes retornam resultados com valores diferentes.

Pelo contrário, se uma ou ambas as posições mostram um valor de 0, então o elemento definitivamente não está dentro do conjunto. Outra situação prevista pelo algoritmo e que se denomina negativa ou falso positivo. Este resultado é definitivo ou conclusivo, uma vez que os filtros bloom nunca resultarão em falsos negativos. Ou seja, se o algoritmo de um filtro bloom detecta um negativo ou um falso positivo, essa informação definitivamente não está no conjunto de dados analisado.

Por outro lado, ao configurar um filtro bloom é muito importante definir o número de bits e funções hash que serão aplicadas. Como um número maior de funções hash, a taxa de erro é bastante reduzida, então a probabilidade de ter resultados falsos positivos será menor. Da mesma forma, uma vez que o conjunto de bits do filtro bloom esteja completamente preenchido, os dados inseridos não podem ser apagados. Isso para não causar o aparecimento de falsos negativos no filtro.

Qual a importância dos falsos positivos e negativos nos filtros bloom?

A importância dos estados falsos positivos e negativos dos filtros bloom está na eficiência. Como já mencionamos, os filtros bloom são programados para levar em consideração os dois estados. E, se ocorrerem, podemos tomar as medidas pertinentes para fornecer uma resposta adequada.

Por exemplo, se trabalharmos com um sistema de armazenamento de dados para gerar um cache, um filtro bloom é de grande ajuda. Isto se deve ao fato de que cada vez que o sistema recebe um dado, o que devemos fazer é verificar se o referido dado não está nos dados que armazenamos no cache. Portanto, se introduzirmos esses dados e o filtro bloom retornar um negativo ou um falso positivo, podemos ter certeza de que esses dados não estão no conjunto de informações que tratamos. E nesse ponto, podemos prosseguir para armazenar esses novos dados no cache para que depois possamos acessá-los de forma rápida e eficiente.

Se, ao contrário, o filtro bloom retornar positivo, podemos simplesmente descartar o armazenamento das informações e trabalhar com o que temos no cache, dando melhor acesso às informações e, assim, economizando valiosos recursos computacionais.

Esse tipo de operação não é estranho ao software que usamos diariamente. Por exemplo, os navegadores da web usam o cache armazenado em nossos discos rígidos para nos dar acesso a certos recursos rapidamente, em comparação com a consulta desses dados online. Bancos de dados de servidor e outros sistemas que lidam com grandes quantidades de dados também usam filtros bloom ou algoritmos semelhantes para melhorar a eficiência de suas respostas e tratamento de dados.

Funções de hash dentro de filtros bloom

Ao configurar um filtro bloom, funções hash independentes e uniformemente distribuídas devem ser usadas. Essas funções hash permitem atribuir um identificador a qualquer tipo de dado, que pode ser usado para indexar ou comparar esses dados dentro de um conjunto.

Quando falamos sobre funções hash, falamos sobre os conhecidos SHA-256, MD5 ou outras funções como o CRC32. No entanto, em filtros de flor você deve ter cuidado. O uso de muitas funções hash adiciona segurança, mas também torna mais complexo e lento, portanto, as funções devem ser escolhidas de forma que seus recursos sejam totalmente explorados.

Por sua vez, a característica unidirecional das funções hash permite que um identificador seja determinado ou criado a partir de um elemento ou dado, mas o processo oposto não pode ser realizado. Portanto, se um usuário descobrir um identificador, ele não será capaz de saber quais são os dados ou elementos relacionados a ele.

Vantagens e desvantagens de usar o filtro bloom

Vantagens

• Os filtros bloom, por não armazenar um conjunto de dados como tal, são mais eficientes em termos de uso de espaço de armazenamento. Uma vez que eles só salvam se uma informação ou elemento existe ou não dentro do filtro bloom.
• Da mesma forma, este recurso permite a verificação dos dados ou elementos pode ser feita de forma muito mais rápida e eficiente. Embora também deva ser levado em conta que quanto maior o número de funções hash, maior o tempo necessário para o filtro bloom para verificar a existência dos elementos ou dados.
• Como Os filtros bloom usam o conceito de hash unilateral. Se um usuário obtiver acesso a eles, não poderá saber diretamente nenhuma das informações contidas nesses filtros.

Desvantagens

• Essas ferramentas não retorne os dados verificado. Em vez disso, eles apenas permitem que você verifique se eles existem ou não.
• Quando você obtém resultados positivos, só pode presumir que eles provavelmente estão corretos. Você não pode estar certo ou totalmente certo de que os dados positivos fazem parte do todo. Ao contrário do que acontece em caso de resultados negativos. Onde você pode ter uma resposta ou um resultado final decisivo.
• Ao projetar o filtro bloom, deve ser atribuído um tamanho a ele, independentemente de ser alguns bits ou milhões de bits. Uma vez que um tamanho é designado, ele não vai encolher ou crescer mais do que o estabelecido anteriormente. Portanto, para que o filtro bloom seja eficiente, é necessário definir ou deixar claro com antecedência quantos dados serão adicionados. Portanto, se essa informação não for conhecida, é provável que um filtro bloom seja projetado com muito poucos itens que não sejam tão eficazes para lidar com as informações desejadas. Ou pode ser o caso em que um filtro bloom muito grande é projetado e exige um espaço de armazenamento muito grande para a pequena quantidade de informação a ser tratada. O que resultaria em perda de espaço.

Casos de uso de filtros Bloom

Criptomoedas: Bitcoin e Ethereum

O sistema Bitcoin usa filtros bloom para acelerar a sincronização das carteiras ou porta-moedas SPV; que permitem especificar apenas as transações para as quais desejam receber atualizações do sistema. Formando um conjunto de transações que podem ser transmitidas aos nós completos da rede. Lá você pode verificar esses filtros. Em seguida, receber a confirmação se este conjunto de transações foi ou não adicionado à cadeia. Não há necessidade de lidar com uma cópia completa do blockchain. No Bitcoin, essa funcionalidade está sendo alterada pelos Compact Blocks mencionados no BIP-158.

Por sua vez, a rede Ethereum faz uso de filtros bloom como um mecanismo através do qual você pode encontrar logs dentro de seu blockchain. Assim, ao implementar esses filtros, você pode pesquisar facilmente os eventos que ocorreram no sistema Ethereum. Sem sobrecarregá-lo ao lidar com informações excessivas. Fazer aplicativos pode gerenciar essas informações com muito mais eficiência. Embora não exija uma grande quantidade de espaço de armazenamento. Já que com os filtros bloom, não há necessidade de armazenar dados que podem ser duplicados dentro do sistema.

No Ethereum, quando um bloco é gerado e verificado, o endereço do contrato e os campos indexados dos registros são adicionados a um filtro bloom. Este filtro está localizado no cabeçalho do bloco. Portanto, se um aplicativo deseja localizar todas as entradas do registro, o nó deve verificar apenas o cabeçalho. Assim, você pode reconhecer se os dados necessários estão lá ou não. Portanto, esses elementos não são adicionados ao bloco como tal, a fim de economizar espaço de armazenamento.

Redes e canais de informação

Outra implementação importante dos filtros Bloom permite que redes ou canais de informação possam fazer recomendações de artigos aos usuários. Permitindo que não se repitam. Quer dizer, você pode descobrir quais artigos um usuário leu para recomendar aqueles que ele ainda não viu.

Da mesma forma, grandes centros de distribuição de dados e conteúdo (CDN) usam filtros bloom para maximizar a eficiência do armazenamento de dados e uso da rede, evitando que elementos repetidos ou pouco usados ​​se tornem parte de seus sistemas, sobrecarregando-os. Isso inclui empresas como Akamai, Namecheap CDN, Fastly ou Cloudflare.