Bloom Filter: come memorizzare 1 Milione di stringhe in meno di 2MB?
In questo articolo ci divertiremo con il Bloom Filter, una struttura dati semplice ed elegante che permette (in alcuni casi) di memorizzare molti dati occupando pochissima memoria. Come vedremo nell’esempio sarà possibile memorizzare 1 Milione di stringhe occupando mendo di 2MB, tutto questo indipendentemente dalla loro lunghezza.
Il Bloom Filter di fatto è un implementazione di un Set, ovvero un insieme di dati. Le operazioni supportate sono una “add” con la quale si inserice un nuovo dato, e una “contains” che controlla se un elemento è presente o meno nel Set. Il vantaggio di questa struttura dati è il bassissimo utilizzo di memoria, ma per avere questo dobbiamo accettare che la contains potrebbe darci un informazione errata.
Infatti, la struttura dati in un numero limitato di casi, potrebbe dirci che contiene qualcosa anche se non è vero. Se invece ci dice che non contiene un certo elemento, siamo sicuri al 100% che l’elemento non è presente nell’insieme.
Il Bloom Filter è una struttura dati probabilistica. Esistono delle formule che indicano la probabilità che accada un errore.
Questa struttura dati è molto comoda per implementare una cache compatta per dati in blacklist. Immaginate di dover memorizzare 1 milione di stringhe url o link malevoli. Magari queste informazioni stanno su un database o su un filesystem lento che non volete sovraccaricare di richieste continue per scoprire se un url è in questa blacklist. Bene, basta creare un Bloom Filter con tali stringhe, e se ci accontentiamo di sbagliare 1 volta su 1000 allora lo spazio di memoria da pagare è circa poco meno di 2 MB.
Se l’url non è nel Bloom filter siamo certi che si tratta di un sito sicuro, e questa casistica avviene per la maggior parte dei casi. Se invece l’url è contenuto nel Bloom Filter è impossibile sapere se l’url è veramente in blacklist oppure c’è stato un errore (con la probabilità del 0.001% nel nostro caso). Nell’ipotesi in cui l’url è contenuto nel Bloom filter, possiamo trattare gli errori come “falsi positivi”, oppure (raramente) si può accedere al database o filesystem lento per disambiguare l’informazione.
Ecco l’esempio in java utilizzando la libreria guava (ma esistono implementazioni in qualsisasi linguaggio di vostro piacimento):
Gli unici parametri sono: il numero di elementi che ci aspettiamo di inserire e la probabilità di errore (chiaramente meno si vuole sbagliare, più spazio si deve occupare). Una formula che stima l’utilizzo di memoria si può trovare qua: https://stackoverflow.com/questions/57751044/how-to-get-the-memory-size-of-guavas-bloomfilter
Sembra magia! Ma come fa a funzionare? Proveremo adesso a descrivere il comportamento interno passo dopo passo.
L’unica struttura dati interna al Bloom Filter che occupa memoria è un array di bit di dimensione N.
Per ogni elemento da aggiungere vengono calcolate alcune funzioni di hashing (nel nostro caso 3). Ogni funzione di hashing da un risultato da 0 a N-1, e le posizioni corrispondendi nell’array vengono segnate con il bit 1.
Simuliamo l’aggiunta di altri elementi:
Infine per vedere se un elemento è presente o no, basta calcolare gli hash e controllare se tutti i bit corrispondenti sono a 1. Se anche solo un bit corrispondente vale 0 siamo sicuri che l’elemento cercato non appartiene all’insieme. Se tutti i bit risultano essere 1, o l’elemento è veramente nel Set, oppure alcune funzioni di hash sono andate in “collisione” provocando l’errore.
Il Bloom Filter è una struttura dati molto utile, ma putroppo poco conosciuta, che permette in alcuni casi di risparmiare memoria e accessi a risorse molto lente.
I Bloom Filters vengono implementati nei cosiddetti wallet “leggeri” di Bitcoin, per controllare che una transazione sia valida.
Non è difficile da utilizzare, ed è fondamentale conoscerne anche solo l’esistenza!
