Bloom Filters: A Memória Aproximada que Revoluciona a Performance

O Problema: Quando Verificar se Torna Caro

Nos últimos anos, o DelphiMVCFramework foi adotado em sistemas críticos ao redor do mundo: desde APIs bancárias que processam transações de milhões de euros, até sistemas hospitalares que gerenciam dados vitais de pacientes, passando por plataformas industriais que coordenam linhas de produção automatizadas. Esses sistemas compartilham uma característica comum: devem lidar com milhões de chamadas de API diariamente mantendo excelente performance e tempos de resposta previsíveis.

Em tais contextos, até mesmo as operações aparentemente mais simples podem se tornar gargalos críticos quando escaladas para volumes empresariais. Um exemplo perfeito é o que você pode encontrar ao desenvolver uma API de registro de usuários para uma rede social que atingiu 100 milhões de assinantes. Toda vez que alguém tenta se registrar, você precisa verificar se o email já existe no banco de dados. Uma consulta aparentemente inocente como SELECT COUNT(*) FROM users WHERE email = ? pode parecer trivial, mas quando executada milhares de vezes por minuto em uma tabela com 100 milhões de linhas, mesmo com os melhores índices, o banco de dados começa a sofrer.

O paradoxo é que a grande maioria dessas consultas retorna zero resultados - a maioria dos emails sendo verificados são efetivamente novos. Você está literalmente desperdiçando recursos computacionais para confirmar algo que poderia saber antecipadamente com um método muito mais eficiente.

Este cenário se repete em inúmeros contextos: verificação de URLs já visitadas em um web crawler, verificação de chaves em caches distribuídos, filtros anti-spam, sistemas de deduplicação. Todas situações onde o custo de verificar se um elemento “pode estar presente” é enormemente menor que o custo de uma verificação definitiva.

A Solução Tradicional e Seus Limites

A abordagem clássica envolve usar estruturas de dados como HashSet ou Dictionary para manter todos os elementos previamente vistos em memória. Para nosso caso de emails, isso significaria carregar 100 milhões de strings na memória - estamos falando de vários gigabytes de RAM apenas para essa funcionalidade.

Mesmo assumindo que você tenha a memória disponível, o custo de manter essa estrutura sincronizada com o banco de dados se torna proibitivo. Cada inserção, modificação ou exclusão requer atualizações tanto no banco de dados quanto na estrutura em memória.

Apresentando os Bloom Filters: A Memória Aproximada

Um Bloom Filter é essencialmente uma “memória aproximada” que permite responder a uma pergunta fundamental: “Já vi este elemento antes?” com duas possíveis respostas:

• “Definitivamente NÃO” (resposta garantida 100%)
• “Provavelmente SIM” (com uma probabilidade configurável de erro)

Pense em um Bloom Filter como aquele amigo que tem uma memória excepcional para coisas que NUNCA viu, mas às vezes confunde coisas que já encontrou. Se ele te disser “Nunca vi isso”, você pode confiar cegamente. Se ele disser “Já vi isso”, ele pode estar errado, mas na maioria das vezes está certo.

Como Funciona: A Elegância da Simplicidade

Um Bloom Filter consiste em um array de bits (inicialmente todos em zero) e um conjunto de funções hash. Quando você quer “lembrar” de um elemento:

1. Você calcula várias funções hash do elemento
2. Usa esses valores como índices no array de bits
3. Define todos os bits correspondentes como 1

Para verificar se um elemento já está presente:

1. Você calcula as mesmas funções hash
2. Verifica se todos os bits correspondentes estão em 1
3. Se mesmo um estiver em 0, o elemento definitivamente não está lá
4. Se todos estiverem em 1, o elemento provavelmente está lá

A beleza está na compactação: independentemente de quantos elementos você inserir, o tamanho do Bloom Filter permanece constante. Para nosso caso de 100 milhões de emails, em vez de gigabytes de memória, poderíamos usar apenas alguns megabytes mantendo uma probabilidade de falso positivo de 1%.

Resolvendo o Problema Original

Voltando ao nosso cenário de registro de usuários, o fluxo se torna:

1. Usuário tenta registro com email X
2. Verificação rápida no Bloom Filter (microssegundos)
3. Se disser “Definitivamente NÃO”, prossegue diretamente com a inserção
4. Se disser “Provavelmente SIM”, faz a consulta ao banco de dados para confirmação

Considerando que 99% dos emails são efetivamente novos, eliminamos 99% das consultas ao banco de dados. O 1% restante inclui tanto duplicatas reais quanto falsos positivos, mas ambos requerem verificação final de qualquer forma.

Implementação Simples mas Eficiente em Delphi

A seguinte implementação é deliberadamente simples mas usa técnicas avançadas para maximizar a performance. Em vez de usar um TArray<Boolean> que desperdiça memória, usamos um TArray<UInt32> para armazenamento compacto de bits.

unit BloomFilter;

interface

uses
  System.SysUtils, System.Hash;

type
  TBloomFilter = class
  private
    fBitArray: TArray<UInt32>;    // Armazenamento compacto com array de UInt32
    fBitCount: UInt32;            // Número total de bits no filtro
    fHashFunctions: Integer;      // Número de funções hash a usar
    
    function GetBitArraySize: Integer;
    procedure SetBit(aIndex: UInt32);
    function GetBit(aIndex: UInt32): Boolean;
    function ComputeHash(const aValue: string; aSeed: UInt32): UInt32;
    
  public
    constructor Create(aBitCount: UInt32; aHashFunctions: Integer = 3);
    destructor Destroy; override;
    
    procedure Add(const aValue: string);
    function MightContain(const aValue: string): Boolean;
    procedure Clear;
  end;

implementation

constructor TBloomFilter.Create(aBitCount: UInt32; aHashFunctions: Integer);
begin
  inherited Create;
  
  if aBitCount = 0 then
    raise EArgumentException.Create('Bit count must be greater than 0');
  if aHashFunctions <= 0 then
    raise EArgumentException.Create('Hash function count must be greater than 0');
    
  fBitCount := aBitCount;
  fHashFunctions := aHashFunctions;
  
  // Calcula o tamanho do array UInt32 necessário
  SetLength(fBitArray, GetBitArraySize);
  Clear;
end;

destructor TBloomFilter.Destroy;
begin
  SetLength(fBitArray, 0);
  inherited;
end;

function TBloomFilter.GetBitArraySize: Integer;
begin
  // Divisão teto: (fBitCount + 31) div 32
  Result := (fBitCount + 31) div 32;
end;

procedure TBloomFilter.SetBit(aIndex: UInt32);
var
  lArrayIndex: Integer;
  lBitIndex: Integer;
begin
  lArrayIndex := aIndex div 32;
  lBitIndex := aIndex mod 32;
  fBitArray[lArrayIndex] := fBitArray[lArrayIndex] or (1 shl lBitIndex);
end;

function TBloomFilter.GetBit(aIndex: UInt32): Boolean;
var
  lArrayIndex: Integer;
  lBitIndex: Integer;
begin
  lArrayIndex := aIndex div 32;
  lBitIndex := aIndex mod 32;
  Result := (fBitArray[lArrayIndex] and (1 shl lBitIndex)) <> 0;
end;

function TBloomFilter.ComputeHash(const aValue: string; aSeed: UInt32): UInt32;
var
  lHash1Val, lHash2Val: Cardinal;
  lCombined: UInt64;  // UInt64 para prevenir overflow
begin
  // Duplo hashing para simular funções hash independentes
  lHash1Val := Cardinal(THashBobJenkins.GetHashValue(aValue));
  lHash2Val := Cardinal(THashFNV1a32.GetHashValue(aValue));
  
  // Combina com seed para criar diferentes funções hash
  lCombined := UInt64(lHash1Val) + UInt64(aSeed) * UInt64(lHash2Val);
  
  // O módulo garante que o resultado esteja sempre no intervalo válido
  Result := lCombined mod fBitCount;
end;

procedure TBloomFilter.Add(const aValue: string);
var
  lHashValue: UInt32;
begin
  for var lI := 0 to fHashFunctions - 1 do
  begin
    lHashValue := ComputeHash(aValue, UInt32(lI));
    SetBit(lHashValue);
  end;
end;

function TBloomFilter.MightContain(const aValue: string): Boolean;
var
  lHashValue: UInt32;
begin
  Result := True;
  for var lI := 0 to fHashFunctions - 1 do
  begin
    lHashValue := ComputeHash(aValue, UInt32(lI));
    if not GetBit(lHashValue) then
    begin
      Result := False;
      Exit; // Otimização: saída antecipada
    end;
  end;
end;

procedure TBloomFilter.Clear;
begin
  for var lI := 0 to Length(fBitArray) - 1 do
    fBitArray[lI] := 0;
end;

end.

A implementação usa várias técnicas para maximizar a performance:

Armazenamento Compacto: Usar TArray<UInt32> em vez de TArray<Boolean> reduz o uso de memória em 32 vezes. Cada UInt32 pode armazenar 32 bits, enquanto cada Boolean usaria um inteiro.

Duplo Hashing: A função ComputeHash combina dois algoritmos hash diferentes (Bob Jenkins e FNV1a) com uma seed para simular funções hash independentes, evitando a necessidade de implementar múltiplas funções hash separadas.

Prevenção de Overflow: Usar UInt64 em cálculos intermediários previne overflow durante operações aritméticas, garantindo resultados corretos mesmo com valores grandes.

Saída Antecipada: Em MightContain, o loop para no primeiro bit não definido, otimizando a performance no caso mais comum (elementos não presentes).

Nomenclatura Moderna: A classe segue as convenções modernas do Delphi com membros privados começando com “f” e variáveis locais com “l”, junto com o uso de sintaxe inline para loops.

O Segredo do Duplo Hashing: Por Que Precisamos de Múltiplas Funções Hash?

Uma pergunta fundamental na implementação de Bloom Filters é: por que não usar apenas uma função hash? A resposta está na matemática da distribuição probabilística e na necessidade de minimizar falsos positivos.

O Problema de Uma Única Função Hash: Se usássemos apenas uma função hash, elementos diferentes poderiam facilmente “colidir” no mesmo bit, reduzindo drasticamente a efetividade do filtro. Com múltiplas funções hash, a probabilidade de que dois elementos diferentes tenham todas as mesmas posições hash se torna extremamente baixa.

A Técnica do Duplo Hashing: Em vez de implementar k funções hash completamente independentes (computacionalmente caro), nossa implementação usa uma técnica elegante: simular k funções hash usando apenas duas funções base.

A fórmula matemática é:

Gi(x) = (H1(x) + i * H2(x)) mod m

Onde:

• Gi(x) é a i-ésima função hash simulada para o elemento x
• H1(x) e H2(x) são as duas funções hash base (Bob Jenkins e FNV1a)
• i é o índice da função hash (0, 1, 2…)
• m é o tamanho do array de bits

Como Funciona em Nossa Implementação:

function TBloomFilter.ComputeHash(const aValue: string; aSeed: UInt32): UInt32;
var
  lHash1Val, lHash2Val: Cardinal;
  lCombined: UInt64;
begin
  // Duas funções hash base
  lHash1Val := Cardinal(THashBobJenkins.GetHashValue(aValue));  // H1(x)
  lHash2Val := Cardinal(THashFNV1a32.GetHashValue(aValue));     // H2(x)
  
  // Fórmula: G_i(x) = (H1(x) + i * H2(x)) mod m
  lCombined := UInt64(lHash1Val) + UInt64(aSeed) * UInt64(lHash2Val);
  Result := lCombined mod fBitCount;
end;

O parâmetro aSeed representa o índice i da função hash. Quando chamamos o método com seeds 0, 1, 2… obtemos funções hash diferentes que são correlacionadas matematicamente de forma ótima.

Vantagens desta Abordagem:

• Eficiência: Calculamos apenas dois hashes base em vez de k hashes separados
• Independência: As funções resultantes são suficientemente independentes para minimizar falsos positivos
• Simplicidade: Uma fórmula em vez de k implementações diferentes
• Comprovado: Esta técnica foi matematicamente comprovada quase equivalente a k funções verdadeiramente independentes

Esta é a razão pela qual nosso Bloom Filter pode ser tanto simples quanto extremamente efetivo: aproveitamos a matemática para alcançar o máximo resultado com o mínimo esforço computacional.

Demo Rápida da Funcionalidade

Antes de ver uso prático em produção, aqui está uma demo simples de console que mostra a API em ação:

program BloomFilterDemo;
{$APPTYPE CONSOLE}

uses
  System.SysUtils,
  BloomFilter in 'BloomFilter.pas';

var
  lFilter: TBloomFilter;
begin
  // Cria um Bloom Filter com 10000 bits e 3 funções hash
  lFilter := TBloomFilter.Create(10000, 3);
  try
    Writeln('=== DEMO BLOOM FILTER ===');
    Writeln;
    
    // Testa emails ainda não inseridos
    Write('Email "mario@test.com" está presente? ');
    if lFilter.MightContain('mario@test.com') then
      Writeln('PROVAVELMENTE SIM')
    else  
      Writeln('DEFINITIVAMENTE NÃO');
      
    Write('Email "luigi@test.com" está presente? ');
    if lFilter.MightContain('luigi@test.com') then
      Writeln('PROVAVELMENTE SIM')
    else  
      Writeln('DEFINITIVAMENTE NÃO');
    
    Writeln;
    Writeln('Adicionando "mario@test.com" ao filtro...');
    lFilter.Add('mario@test.com');
    
    Writeln('Adicionando "francesco@test.com" ao filtro...');
    lFilter.Add('francesco@test.com');
    
    Writeln;
    Writeln('=== TESTE APÓS INSERÇÕES ===');
    
    // Testa elementos inseridos
    Write('Email "mario@test.com" está presente? ');
    if lFilter.MightContain('mario@test.com') then
      Writeln('PROVAVELMENTE SIM (correto!)')
    else  
      Writeln('DEFINITIVAMENTE NÃO');
      
    Write('Email "francesco@test.com" está presente? ');
    if lFilter.MightContain('francesco@test.com') then
      Writeln('PROVAVELMENTE SIM (correto!)')
    else  
      Writeln('DEFINITIVAMENTE NÃO');
    
    // Testa elemento nunca inserido
    Write('Email "luigi@test.com" está presente? ');
    if lFilter.MightContain('luigi@test.com') then
      Writeln('PROVAVELMENTE SIM (falso positivo)')
    else  
      Writeln('DEFINITIVAMENTE NÃO (correto!)');
      
    Writeln;
    Writeln('Nota: Elementos inseridos sempre são detectados (zero falsos negativos)');
    Writeln('Elementos não inseridos podem ocasionalmente dar falsos positivos');
    
    Readln;
  finally
    lFilter.Free;
  end;
end.

A saída típica mostrará como o Bloom Filter responde “DEFINITIVAMENTE NÃO” para elementos nunca vistos, “PROVAVELMENTE SIM” para elementos inseridos, e ocasionalmente “PROVAVELMENTE SIM” mesmo para elementos não inseridos (falsos positivos). O ponto chave é que nunca teremos falsos negativos: se um elemento foi inserido, sempre será detectado.

Uso Prático

// No seu controller de registro
var
  lBloomFilter: TBloomFilter;
  
// Inicialização (feita apenas uma vez)
lBloomFilter := TBloomFilter.Create(1000000, 3); // 1M bits, 3 funções hash

// Durante o registro
procedure RegisterUser(const aEmail: string);
begin
  if not lBloomFilter.MightContain(aEmail) then
  begin
    // Definitivamente email novo, inserir diretamente
    InsertNewUser(aEmail);
    lBloomFilter.Add(aEmail);
  end
  else
  begin
    // Pode ser duplicado, verificar com banco de dados
    if not EmailExistsInDB(aEmail) then
    begin
      InsertNewUser(aEmail);
      lBloomFilter.Add(aEmail);
    end
    else
      raise Exception.Create('Email já registrado');
  end;
end;

Considerações Finais

Os Bloom Filters representam um exemplo perfeito de como às vezes a melhor solução não é a perfeita, mas a “suficientemente boa” que resolve o problema real. ☝️ Como dizia Voltaire “o perfeito é inimigo do bom”. Ao aceitar uma pequena porcentagem de incerteza, obtemos enormes vantagens em termos de memória e performance.

Quando Usar Bloom Filters

Os Bloom Filters são a escolha ideal quando:

• Você precisa realizar muitas verificações de pertencimento em um conjunto muito grande
• A memória é um recurso limitado
• Você pode tolerar uma pequena porcentagem de falsos positivos
• Você não precisa remover elementos do conjunto (uma vez que um bit está em 1, não pode voltar a 0)

Casos de Uso no Mundo Real

Além do nosso exemplo de API de registro de usuários, os Bloom Filters são usados em:

Navegadores Web: O Chrome usa Bloom Filters para Safe Browsing - verifica rapidamente se uma URL está na lista de sites maliciosos sem ter que consultar o servidor para cada link.

Bancos de Dados Distribuídos: Sistemas como Cassandra e HBase os usam para evitar leituras caras de disco. Antes de buscar dados específicos, consultam o Bloom Filter para saber se vale a pena acessar o disco.

Sistemas de Cache: Para verificar rapidamente se um item já está no cache antes de recuperá-lo de uma fonte mais lenta.

Redes de Distribuição de Conteúdo (CDN): Para determinar se o conteúdo já está disponível em um servidor edge sem ter que fazer consultas caras.

Detecção de Duplicatas: Em aplicações onde é importante saber se um elemento já foi visto (evitar spam, sugerir conteúdo não visto).

Trade-offs a Considerar

Vantagens:

• Eficiência de espaço extrema (alguns megabytes para milhões de elementos)
• Operações em tempo quase constante
• Garantia de zero falsos negativos

Desvantagens:

• Possíveis falsos positivos (configuráveis)
• Impossibilidade de remover elementos
• Tamanho fixo do array de bits

No mundo das arquiteturas distribuídas e big data, os Bloom Filters se tornaram uma ferramenta indispensável. Sua simplicidade conceitual esconde um poder surpreendente na otimização de sistemas reais, especialmente quando combinados com frameworks como DelphiMVCFramework para criar APIs de alta performance.