Analisando estrutura de dados: Bloom Filter

Olá!

Este texto faz parte de uma série que eu analiso algoritmos e estrutura de dados. Você encontra os textos anteriores relacionados nos links abaixo:

#1: Geohash
#2: QuadTree

Problema

Em sistemas distribuídos, imagine que você tenha algum tipo de lista com registros que crescem ao longo do tempo, como um filtro de urls maliciosas em uma base de dados de um firewall, uma lista de sites já indexados em web crawler ou até mesmo um controle de mensagens/registros já processados em uma tabela de controle qualquer.

Com o tempo, a quantidade de registros cresce descontroladamente e os clientes desse mecanismos começam a sofrer com problemas de performance. Mesmo que você use técnicas como sharding ou caches para armazenar essa lista de controle, ainda sim há um custo de busca associado que cresce com o tempo, dado que a lista aumentou também.

Porém, há um detalhe: você não precisa de garantias absolutas que o dado de fato está na lista (isso é primordial nesse caso). Portanto, um falso positivo pode ser tolerado (ou seja, em alguns casos o sistema considera que já processou um registro que, na verdade, ainda não foi processado). Daria para adicionar uma segunda camada de verificação mais robusta após a execução desse filtro inicial, por exemplo.

Um jeito de resolver essa natureza de problemas é evoluir a ideia de hash tables, de certa forma. Ou seja, fazer um filtro barato (que consome pouco espaço, por exemplo), porém, sem armazenar de fato os registros para consulta.

Como Funciona?

Um Bloom Filter é composto de dois elementos principais: um array de bits com todos os elementos iniciados em 0 e algumas funções hash que a partir de um determinado valor, mapeia o resultado para um determinado índice do array.

Começamos com isso:

Bit Array com 20 posições

Quando um novo elemento é adicionado ao filtro, ele é processado por várias funções de hash. Cada função gera um índice correspondente no bit array e os bits nesses índices são definidos como 1.

Na imagem abaixo, temos 3 funções (h1, h2, h3) que são aplicadas ao valor apple, gerando o seguinte cenário:

Ou seja, para o valor apple, foram preenchidos os indices [5,11,16] do array.

Em uma implementação real (mais detalhes daqui a pouco), o segredo do bom funcionamento está justamente nas escolha adequada de quais e quantas funções hash usar.

Para verificar se um elemento está no conjunto, ele passa pelas mesmas funções de hash. Se todos os bits nos índices resultantes das funções de hash estiverem definidos como 1, o filtro indica que o elemento está presente (com uma pequena chance de erro). Se algum desses bits for 0, o elemento definitivamente não está no conjunto.

Ou seja, na prática, a bloom filter é uma estrutura de dados probabilistica. Ela pode ou não indicar que o elemento pertence ao conjunto, mas com certeza consegue dizer que não. Esse é o caso de uso ideal para essa estrutura de dados.

Código

Abaixo está uma implementação em python. Adicionei o parâmetro show_steps para exibir o passo-a-passo do algoritmo para quem tiver curiosidade.

Você consegue rodar via web por aqui:

import hashlib


class BloomFilter:
        """
        Construtor
        """
    def __init__(self, size, hash_count, show_steps):
        self.size = size  # Tamanho do bit array
        self.bit_array = [0] * size  # Inicializa a array de bits
        self.hash_count = hash_count  # Número de funções de hash
        self.show_steps = show_steps # Controle de exibição dos passos intermediários

    def _hashes(self, item):
        """
        Gera hash utilizando diferentes algoritmos e converte para índices.
        """
        result = []
        for i in range(self.hash_count):
            # Cria um hash usando SHA256 e uma string única para cada função de hash
            hash_result = hashlib.sha256((item + str(i)).encode()).hexdigest()

            index = int(hash_result, 16) % self.size
            if self.show_steps:
                print(f"Hash Function #{i}")
                print(f"Hash: {hash_result}")
                print(f"Hash as Int: {int(hash_result, 16)}")
                print(f"Hash index: {index}")
            result.append(index)
        return result

    def add(self, item):
        """
        Adiciona um item ao Bloom Filter.
        """
        if self.show_steps:
            print("Add Operation")
        for index in self._hashes(item):
            self.bit_array[index] = 1

    def check(self, item):
        """
        Verifica se um item pode estar no conjunto.
        """
             
        if self.show_steps:
            print("Check Operation")
            
        for index in self._hashes(item):
            if self.bit_array[index] == 0:
                return False  # Com certeza não está no conjunto
        return True  # Pode estar no conjunto (chance de falso positivo)


# Exemplo de uso
# Manipule o parâmetro show_steps para ver o passo-a-passo
bloom = BloomFilter(size=20, hash_count=3, show_steps=True)


# Adicionar elementos
bloom.add("apple")
bloom.add("app")
bloom.add("appl")


# Verificar se os elementos estão no conjunto
print(bloom.check("apple"))  # Saída: True

Trade-Offs a serem considerados

A quantidade e o tipo de algoritmo usado nas funções de hash no Bloom Filter afeta diretamente a probabilidade de falsos positivos e o custo computacional. A escolha desses fatores é um equilíbrio entre a probabilidade de falso positivo e o desempenho.

No exemplo acima, o algoritmo utilizado foi o SHA-256, que tem um bom suporta da maioria das libs, é relativamente rápido e possui uma distribuição uniforme, o que reduz o número de colisões. É possível usar MD5 (mais rápido, porém, mais vulnerável a colisões) ou algum outro como MurmurHash.

Aumentar o número de funções de hash em um Bloom Filter melhora a distribuição dos bits e reduz a taxa de falsos positivos, mas eleva o custo computacional e o risco de colisões, podendo saturar o array de bits. Já reduzir o número de funções de hash torna o filtro mais eficiente e diminui a saturação, porém aumenta a chance de falsos positivos, comprometendo a precisão.

Como usar corretamente

Há uma fórmula ideal para calcular o número de funções de hash que minimiza a probabilidade de falsos positivos, que é a seguinte:

Onde k é o número ótimo de funções de hash, m é o tamanho do bit array, n é o número de elementos esperados no conjunto eln 2é aproximadamente ≃0.69314718056.

Considerando o mesmo exemplo anterior: para 3 elementos em um array de 20 posições, temos: (20/3)*0.69314718056 = 4,62 funções de hash. A recomendação aqui é arredondar para baixo, dado que um uso maior de funções aumenta o custo computacional envolvido. Como a fórmula garante o mínimo de confiabilidade em relação a falsos positivos, não vale a pena o trade-off entre precisão vs processamento nesse caso.

Portanto, em um caso real, teste vários algoritmos de hash e faça essas contas pensando na volumetria esperada para decidir melhor qual caminho seguir.

Espero que o texto tenha sido útil de alguma forma.

Até!

Você gostou do conteúdo e gostaria de fazer mentoria comigo? Clique aqui e descubra como.