Become a member!

Bloom Filters: La Memoria Approssimativa che Rivoluziona le Performance

· 11 min read
  • 👉 This article is available in english too.
  • 👉 Este artículo también está disponible en español.
  • 👉 Questo articolo è disponibile anche in italiano.
  • 👉 Este artigo também está disponível em português do Brasil.

Il Problema: Quando Controllare Diventa Costoso

Negli ultimi anni DelphiMVCFramework è stato adottato in sistemi mission-critical in tutto il mondo: dalle API bancarie che processano transazioni per milioni di euro, ai sistemi ospedalieri che gestiscono dati vitali di pazienti, fino alle piattaforme industriali che coordinano linee di produzione automatizzate. Questi sistemi condividono una caratteristica comune: devono gestire milioni di chiamate API ogni giorno mantenendo performance eccellenti e tempi di risposta prevedibili.

In contesti del genere, anche le operazioni apparentemente più semplici possono diventare colli di bottiglia critici quando scalate a volumi enterprise. Un perfetto esempio è quello che potresti incontrare sviluppando un’API per la registrazione utenti di un social network che ha raggiunto i 100 milioni di iscritti. Ogni volta che qualcuno tenta di registrarsi, devi verificare se l’email è già presente nel database. Una query apparentemente innocua come SELECT COUNT(*) FROM users WHERE email = ? può sembrare banale, ma quando viene eseguita migliaia di volte al minuto su una tabella di 100 milioni di righe, anche con gli indici migliori, il database inizia a soffrire.

Il paradosso è che la stragrande maggioranza di queste query restituisce zero risultati - la maggior parte delle email che vengono controllate sono effettivamente nuove. Stai letteralmente sprecando risorse computazionali per confermare qualcosa che potresti sapere in anticipo con un metodo molto più efficiente.

Questo scenario si ripete in innumerevoli contesti: controllo di URL già visitati in un web crawler, verifica di chiavi in cache distribuite, filtri anti-spam, sistemi di deduplicazione. Tutte situazioni dove il costo di verificare se un elemento “potrebbe essere presente” è enormemente inferiore al costo di una verifica definitiva.

La Soluzione Tradizionale e i Suoi Limiti

L’approccio classico prevede l’uso di strutture dati come HashSet o Dictionary per mantenere in memoria tutti gli elementi già visti. Per il nostro caso delle email, significherebbe caricare 100 milioni di stringhe in memoria - parliamo di diversi gigabyte di RAM solo per questa funzionalità.

Anche supponendo di avere la memoria disponibile, il costo di mantenere sincronizzata questa struttura con il database diventa proibitivo. Ogni inserimento, modifica o cancellazione richiede aggiornamenti sia sul database che sulla struttura in memoria.

Enter Bloom Filters: La Memoria Approssimativa

Un Bloom Filter è essenzialmente una “memoria approssimativa” che ti permette di rispondere a una domanda fondamentale: “Ho mai visto questo elemento prima?” con due possibili risposte:

  • “Sicuramente NO” (risposta garantita al 100%)
  • “Probabilmente SÌ” (con una probabilità configurabile di errore)

Pensa al Bloom Filter come a quel amico che ha una memoria eccezionale per le cose che NON ha mai visto, ma a volte confonde le cose che ha già incontrato. Se ti dice “Non l’ho mai visto”, puoi fidarti ciecamente. Se ti dice “L’ho già visto”, potrebbe sbagliarsi, ma nella maggior parte dei casi ha ragione.

Come Funziona: L’Eleganza della Semplicità

Un Bloom Filter è costituito da un array di bit (inizialmente tutti a zero) e da un insieme di funzioni hash. Quando vuoi “ricordare” un elemento:

  1. Calcoli diverse funzioni hash dell’elemento
  2. Usi questi valori come indici nell’array di bit
  3. Imposti a 1 tutti i bit corrispondenti

Per verificare se un elemento è già presente:

  1. Calcoli le stesse funzioni hash
  2. Controlli se tutti i bit corrispondenti sono a 1
  3. Se anche solo uno è a 0, l’elemento sicuramente non c’è
  4. Se sono tutti a 1, l’elemento probabilmente c’è

La bellezza sta nella compattezza: indipendentemente da quanti elementi inserisci, la dimensione del Bloom Filter rimane costante. Per il nostro caso delle 100 milioni di email, invece di gigabyte di memoria, potremmo usare solo qualche megabyte mantenendo una probabilità di falso positivo dell'1%.

Risolvere il Problema Originale

Tornando al nostro scenario di registrazione utenti, il flusso diventa:

  1. Utente tenta registrazione con email X
  2. Controllo rapido nel Bloom Filter (microsecondi)
  3. Se dice “Sicuramente NO”, procedo direttamente con l’inserimento
  4. Se dice “Probabilmente SÌ”, faccio la query al database per conferma

Considerando che il 99% delle email sono effettivamente nuove, eliminiamo il 99% delle query al database. Il restante 1% include sia i veri duplicati che i falsi positivi, ma entrambi richiedono comunque una verifica finale.

Implementazione Semplice ma Efficiente in Delphi

L’implementazione che segue è volutamente semplice ma utilizza tecniche avanzate per massimizzare le performance. Invece di usare un TArray<Boolean> che spreca memoria, utilizziamo un TArray<UInt32> per storage compatto dei bit.

unit BloomFilter;

interface

uses
  System.SysUtils, System.Hash;

type
  TBloomFilter = class
  private
    fBitArray: TArray<UInt32>;    // Storage compatto con array di UInt32
    fBitCount: UInt32;            // Numero totale di bit nel filtro
    fHashFunctions: Integer;      // Numero di funzioni hash da usare
    
    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;
  
  // Calcola la dimensione dell'array UInt32 necessaria
  SetLength(fBitArray, GetBitArraySize);
  Clear;
end;

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

function TBloomFilter.GetBitArraySize: Integer;
begin
  // Divisione ceiling: (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 per prevenire overflow
begin
  // Doppio hashing per simulare funzioni hash indipendenti
  lHash1Val := Cardinal(THashBobJenkins.GetHashValue(aValue));
  lHash2Val := Cardinal(THashFNV1a32.GetHashValue(aValue));
  
  // Combina con seed per creare funzioni hash diverse
  lCombined := UInt64(lHash1Val) + UInt64(aSeed) * UInt64(lHash2Val);
  
  // Il modulo garantisce sempre un risultato nel range valido
  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; // Ottimizzazione: uscita anticipata
    end;
  end;
end;

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

end.

L’implementazione utilizza diversi accorgimenti per massimizzare le performance:

Storage Compatto: L’uso di TArray<UInt32> invece di TArray<Boolean> riduce l’utilizzo di memoria di 32 volte. Ogni UInt32 può memorizzare 32 bit, mentre ogni Boolean ne utilizzerebbe uno intero.

Doppio Hashing: La funzione ComputeHash combina due algoritmi hash diversi (Bob Jenkins e FNV1a) con un seed per simulare funzioni hash indipendenti, evitando la necessità di implementare múltiple funzioni hash separate.

Prevenzione Overflow: L’uso di UInt64 nei calcoli intermedi previene overflow durante le operazioni aritmetiche, garantendo risultati corretti anche con valori grandi.

Uscita Anticipata: In MightContain, il loop si interrompe al primo bit non settato, ottimizzando le performance nel caso più comune (elementi non presenti).

Naming Moderno: La classe segue le convenzioni Delphi moderne con membri privati che iniziano con “f” e variabili locali con “l”, insieme all’uso della sintassi inline per i loop.

Il Segreto del Doppio Hashing: Perché Servono Più Funzioni Hash?

Una domanda fondamentale nell’implementazione dei Bloom Filter è: perché non usare una sola funzione hash? La risposta sta nella matematica della distribuzione probabilistica e nella necessità di minimizzare i falsi positivi.

Il Problema di Una Sola Funzione Hash: Se usassimo una sola funzione hash, elementi diversi potrebbero facilmente “collidere” sullo stesso bit, riducendo drasticamente l’efficacia del filtro. Con più funzioni hash, la probabilità che due elementi diversi abbiano tutte le stesse posizioni hash diventa estremamente bassa.

La Tecnica del Doppio Hashing: Invece di implementare k funzioni hash completamente indipendenti (computazionalmente costoso), la nostra implementazione usa una tecnica elegante: simulare k funzioni hash usando solo due funzioni base.

La formula matematica è:

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

Dove:

  • Gi(x) è la i-esima funzione hash simulata per l’elemento x
  • H1(x) e H2(x) sono le due funzioni hash base (Bob Jenkins e FNV1a)
  • i è l’indice della funzione hash (0, 1, 2…)
  • m è la dimensione dell’array di bit

Come Funziona nella Nostra Implementazione:

function TBloomFilter.ComputeHash(const aValue: string; aSeed: UInt32): UInt32;
var
  lHash1Val, lHash2Val: Cardinal;
  lCombined: UInt64;
begin
  // Due funzioni hash base
  lHash1Val := Cardinal(THashBobJenkins.GetHashValue(aValue));  // H1(x)
  lHash2Val := Cardinal(THashFNV1a32.GetHashValue(aValue));     // H2(x)
  
  // Formula: G_i(x) = (H1(x) + i * H2(x)) mod m
  lCombined := UInt64(lHash1Val) + UInt64(aSeed) * UInt64(lHash2Val);
  Result := lCombined mod fBitCount;
end;

Il parametro aSeed rappresenta l’indice i della funzione hash. Quando chiamiamo il metodo con seed 0, 1, 2… otteniamo funzioni hash diverse ma correlate matematicamente in modo ottimale.

Vantaggi di Questo Approccio:

  • Efficienza: Calcoliamo solo due hash base invece di k hash separati
  • Indipendenza: Le funzioni risultanti sono sufficientemente indipendenti per minimizzare i falsi positivi
  • Semplicità: Una sola formula invece di k implementazioni diverse
  • Provato: Questa tecnica è stata matematicamente dimostrata quasi equivalente a k funzioni veramente indipendenti

Questo è il motivo per cui il nostro Bloom Filter può essere sia semplice che estremamente efficace: sfruttiamo la matematica per ottenere il massimo risultato con il minimo sforzo computazionale.

Demo Rapida del Funzionamento

Prima di vedere un uso pratico in produzione, ecco una semplice demo console che mostra l’API in azione:

program BloomFilterDemo;
{$APPTYPE CONSOLE}

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

var
  lFilter: TBloomFilter;
begin
  // Crea un Bloom Filter con 10000 bit e 3 funzioni hash
  lFilter := TBloomFilter.Create(10000, 3);
  try
    Writeln('=== BLOOM FILTER DEMO ===');
    Writeln;
    
    // Test su email non ancora inserite
    Write('Email "mario@test.com" presente? ');
    if lFilter.MightContain('mario@test.com') then
      Writeln('PROBABILMENTE SI')
    else  
      Writeln('SICURAMENTE NO');
      
    Write('Email "luigi@test.com" presente? ');
    if lFilter.MightContain('luigi@test.com') then
      Writeln('PROBABILMENTE SI')
    else  
      Writeln('SICURAMENTE NO');
    
    Writeln;
    Writeln('Aggiungo "mario@test.com" al filtro...');
    lFilter.Add('mario@test.com');
    
    Writeln('Aggiungo "francesco@test.com" al filtro...');
    lFilter.Add('francesco@test.com');
    
    Writeln;
    Writeln('=== TEST DOPO INSERIMENTI ===');
    
    // Test elementi inseriti
    Write('Email "mario@test.com" presente? ');
    if lFilter.MightContain('mario@test.com') then
      Writeln('PROBABILMENTE SI (corretto!)')
    else  
      Writeln('SICURAMENTE NO');
      
    Write('Email "francesco@test.com" presente? ');
    if lFilter.MightContain('francesco@test.com') then
      Writeln('PROBABILMENTE SI (corretto!)')
    else  
      Writeln('SICURAMENTE NO');
    
    // Test elemento mai inserito
    Write('Email "luigi@test.com" presente? ');
    if lFilter.MightContain('luigi@test.com') then
      Writeln('PROBABILMENTE SI (falso positivo)')
    else  
      Writeln('SICURAMENTE NO (corretto!)');
      
    Writeln;
    Writeln('Nota: Gli elementi inseriti vengono sempre rilevati (zero falsi negativi)');
    Writeln('Gli elementi non inseriti potrebbero dare falsi positivi occasionali');
    
    Readln;
  finally
    lFilter.Free;
  end;
end.

L’output tipico mostrerà come il Bloom Filter risponde “SICURAMENTE NO” per elementi mai visti, “PROBABILMENTE SI” per elementi inseriti, e occasionalmente “PROBABILMENTE SI” anche per elementi non inseriti (falsi positivi). Il punto chiave è che non avremo mai falsi negativi: se un elemento è stato inserito, verrà sempre rilevato.

Utilizzo Pratico

// Nel tuo controller di registrazione
var
  lBloomFilter: TBloomFilter;
  
// Inizializzazione (da fare una sola volta)
lBloomFilter := TBloomFilter.Create(1000000, 3); // 1M bit, 3 funzioni hash

// Durante la registrazione
procedure RegisterUser(const aEmail: string);
begin
  if not lBloomFilter.MightContain(aEmail) then
  begin
    // Sicuramente email nuova, inserisci direttamente
    InsertNewUser(aEmail);
    lBloomFilter.Add(aEmail);
  end
  else
  begin
    // Potrebbe essere duplicata, verifica sul database
    if not EmailExistsInDB(aEmail) then
    begin
      InsertNewUser(aEmail);
      lBloomFilter.Add(aEmail);
    end
    else
      raise Exception.Create('Email già registrata');
  end;
end;

Considerazioni Finali

I Bloom Filter rappresentano un perfetto esempio di come a volte la soluzione migliore non sia quella perfetta, ma quella “abbastanza buona” che risolve il problema reale. ☝️ Come diceva Voltaire “l’ottimo è nemico del buono”. Accettando una piccola percentuale di incertezza, otteniamo enormi vantaggi in termini di memoria e performance.

Quando Usare i Bloom Filter

I Bloom Filter sono la scelta ideale quando:

  • Devi fare molte verifiche di appartenenza su un set molto grande
  • La memoria è una risorsa limitata
  • Puoi tollerare una piccola percentuale di falsi positivi (comunque puoi eseguire la ricerca classica in caso di un caso positivo)
  • Non hai bisogno di eliminare elementi dal set (una volta che un bit è a 1, non può tornare a 0)

Casi d’Uso nel Mondo Reale

Oltre al nostro esempio delle API di registrazione, i Bloom Filter sono utilizzati in:

Browser Web: Chrome usa Bloom Filter per il Safe Browsing - verifica rapidamente se un URL è nella lista dei siti dannosi senza dover interrogare il server per ogni link.

Database Distribuiti: Sistemi come Cassandra e HBase li usano per evitare costose letture su disco. Prima di cercare un dato specifico, consultano il Bloom Filter per sapere se vale la pena accedere al disco.

Sistemi di Caching: Per controllare rapidamente se un elemento è già nella cache prima di recuperarlo da una fonte più lenta.

Content Delivery Networks (CDN): Per determinare se un contenuto è già disponibile in un edge server senza dover fare query costose.

Rilevamento Duplicati: In applicazioni dove è importante sapere se un elemento è già stato visto (evitare spam, suggerire contenuti non ancora visualizzati).

I Trade-off da Considerare

Vantaggi:

  • Efficienza di spazio estrema (qualche megabyte per milioni di elementi)
  • Operazioni a tempo quasi costante
  • Nessun falso negativo garantito

Svantaggi:

  • Possibili falsi positivi (configurabili)
  • Impossibilità di rimuovere elementi
  • Dimensione fissa dell’array di bit

Nel mondo delle architetture distribuite e dei big data, i Bloom Filter sono diventati uno strumento indispensabile. La loro semplicità concettuale nasconde un potere sorprendente nell’ottimizzazione di sistemi reali, specialmente quando abbinati a framework come DelphiMVCFramework per creare API ad alte performance.

Comments

comments powered by Disqus