O Filtro de Bloom é uma estrutura de dados probabilística criada em 1970 por Burton Howard Bloom. Ele é composto por um vetor de bits de longo comprimento associado a múltiplas funções de hash aleatórias. O principal objetivo dessa estrutura é determinar se um elemento pertence ou não a um conjunto específico.

Características e Funcionamento

A grande vantagem do Filtro de Bloom reside na sua eficiência de espaço e velocidade de consulta, superando algoritmos de busca tradicionais em cenários de grande volume de dados. Enrtetanto, essa eficiência traz consigo duas contrapartidas: a possibilidade de falsos positivos e a complexidade na remoção de itens.

Quando um elemento é inserido, ele passa por k funções de hash que geram k posições no vetor de bits, as quais são marcadas como 1. No processo de verificação:

• Se qualquer uma das posições mapeadas pelas funções de hash contiver o valor 0, o elemento certamente não está no conjunto.
• Se todas as posições mapeadas contiverem o valor 1, o elemento provavelmente está no conjunto (há uma margem de erro configurável).

Limitações

• Falsos Positivos: Existe o risco de o filtro indicar que um elemento existe quando, na verdade, os bits foram ativados por outros elementos.
• Dificuldade de Remoção: Como múltiplos elementos podem compartilhar os mesmos bits, alterar um bit para 0 para "remover" um item pode afetar outros registros. Para resolver isso, costuma-se utilizar variações como o Counting Bloom Filter.

Implementação Prática com Spring Boot e Redis

Para implementar essa solução, utilizamos o Redis como armazenamento do vetor de bits (via operações de Bitmap) e a biblioteca Guava para auxiliar nos cálculos de hash.

1. Classe Auxiliar de Gerenciamento

Esta classe é responsável por calcular o tamanho ideal do array de bits e gerar os índices baseados nas funções de hash.

import com.google.common.base.Preconditions;
import com.google.common.hash.Funnel;
import com.google.common.hash.Hashing;

public class BloomCalculador<T> {
    private final int totalHashes;
    private final int tamanhoBitSet;
    private final Funnel<T> extrator;

    public BloomCalculador(Funnel<T> extrator, int insercoesEsperadas, double taxaFalsoPositivo) {
        Preconditions.checkArgument(extrator != null, "O extrator (funnel) não pode ser nulo");
        this.extrator = extrator;
        this.tamanhoBitSet = calcularTamanhoBits(insercoesEsperadas, taxaFalsoPositivo);
        this.totalHashes = calcularQuantidadeHashes(insercoesEsperadas, tamanhoBitSet);
    }

    public long[] extrairIndices(T valor) {
        long[] indices = new long[totalHashes];
        long hash64 = Hashing.murmur3_128().hashObject(valor, extrator).asLong();
        int hashSuperior = (int) hash64;
        int hashInferior = (int) (hash64 >>> 32);

        for (int i = 1; i <= totalHashes; i++) {
            int hashCombinado = hashSuperior + (i * hashInferior);
            if (hashCombinado < 0) {
                hashCombinado = ~hashCombinado;
            }
            indices[i - 1] = hashCombinado % tamanhoBitSet;
        }
        return indices;
    }

    private int calcularTamanhoBits(long n, double p) {
        if (p == 0) p = Double.MIN_VALUE;
        return (int) (-n * Math.log(p) / (Math.log(2) * Math.log(2)));
    }

    private int calcularQuantidadeHashes(long n, long m) {
        return Math.max(1, (int) Math.round((double) m / n * Math.log(2)));
    }
}

2. Serviço de Integração com Redis

O serviço utiliza o RedisTemplate para maniuplar os bits diretamente no servidor Redis.

import org.springframework.data.redis.core.StringRedisTemplate;
import org.springframework.stereotype.Service;

@Service
public class RedisBloomService {
    private final StringRedisTemplate redisTemplate;

    public RedisBloomService(StringRedisTemplate redisTemplate) {
        this.redisTemplate = redisTemplate;
    }

    public <T> void salvarNoFiltro(BloomCalculador<T> helper, String chave, T valor) {
        long[] posicoes = helper.extrairIndices(valor);
        for (long pos : posicoes) {
            redisTemplate.opsForValue().setBit(chave, pos, true);
        }
    }

    public <T> boolean verificarExistencia(BloomCalculador<T> helper, String chave, T valor) {
        long[] posicoes = helper.extrairIndices(valor);
        for (long pos : posicoes) {
            Boolean bitAtivo = redisTemplate.opsForValue().getBit(chave, pos);
            if (bitAtivo == null || !bitAtivo) {
                return false;
            }
        }
        return true;
    }
}

3. Exemplo de Utilização

Abaixo, demonstramos como configurar o filtro para IDs de pedidos com uma taxa de erro tolerável de 1%.

import com.google.common.base.Charsets;
import com.google.common.hash.Funnels;

// Configuração para 1000 elementos e 1% de margem de erro
private BloomCalculador<String> filtroPedidos = new BloomCalculador<>(
    (from, into) -> into.putString(from, Charsets.UTF_8), 
    1000, 
    0.01
);

// Adicionando um novo ID de pedido
redisBloomService.salvarNoFiltro(filtroPedidos, "blacklist:pedidos", "ORD-99821");

// Verificando se o pedido existe
boolean existe = redisBloomService.verificarExistencia(filtroPedidos, "blacklist:pedidos", "ORD-99821");