Filtro di Bloom: un elemento appartiene all’insieme?

Il filtro di Bloom è una struttura probabilistica che ci permette di dire, con una certa probabilità, se un elemento x si trova in un insieme M.

Nel nostro sistema, per esempio, dobbiamo misurare quante volte gli utenti hanno cliccato su un banner pubblicitario. A ogni clic ci arriva una richiesta HTTP GET che ci informa che l’utente XYZ ha cliccato sulla pubblicità 123. Ogni tanto capita che l’utente per errore faccia doppio clic con il mouse e a noi arrivino quindi due richieste. Vorremmo filtrare queste richieste e registrarle nel database come un solo clic.

Ci serve quindi un’applicazione che legga il canale dei messaggi sui clic e scarti i duplicati. Come faremmo? Ogni messaggio di questo tipo ha un ID, quindi non dobbiamo confrontare l’intero messaggio: ci basta verificare se abbiamo già elaborato un messaggio con lo stesso ID. Un semplice codice in JavaScript che eliminerebbe i duplicati da un flusso di messaggi (qui, per semplicità, da un array) potrebbe essere questo:

var messages = [{id: "123"}, {id:"456"}, {id:"123"}, {id: "789"}]
var processedIds = {};

messages.forEach(function(message) {
    if (!processedIds[message.id]) {
        processedIds[message.id] = true;
        console.log(message);
    }
});

// Stampa: { id: "123" } { id: "456" } { id: "789" }

Questa soluzione andrà bene finché non finiremo la memoria, e prima o poi finirà, perché l’insieme processedIds col tempo può solo crescere. Possiamo naturalmente aggiungere una qualche scadenza dei dati: possiamo rimuovere sempre i messaggi più vecchi di un’ora o qualcosa di simile.

Peggio ancora se nemmeno questo basta. Che cosa facciamo se nell’insieme processedIds ci servono i dati di almeno un giorno e gestiamo, poniamo, diecimila messaggi al secondo? Nel caso peggiore dobbiamo memorizzare fino a 864.000.000 ID. Se usiamo uuid v4, ogni ID è lungo 36 caratteri, quindi al giorno dobbiamo memorizzare almeno 31 GB. È un po’ tanto. Non si potrebbe ridurre il consumo di memoria?

Il filtro di Bloom

Invece di memorizzare l’intero ID, possiamo memorizzarne solo l’hash. Possiamo usare il classico murmurhash, che per ogni stringa restituisce un numero intero a 32 bit e ha anche una buona distribuzione:

var murmurhash = require("murmurhash");

var messages = [{id: "123"}, {id:"456"}, {id:"123"}, {id: "789"}];
var processedHashedIds = {};

messages.forEach(function(message) {
    var hashedId = murmurhash.v2(message.id);
    if (!processedHashedIds[hashedId]) {
        processedHashedIds[hashedId] = true;
        console.log(message);
    }
});

// Stampa: { id: "123" } { id: "456" } { id: "789" }

Ora usiamo il trucco del vettore di bit. È un array in cui memorizzeremo solo zeri e uni. Se abbiamo una funzione di hash a n bit, ci serve un vettore di dimensione 2ⁿ, per poter indirizzare nel vettore tutti i possibili valori della funzione di hash. L’idea è che all’inizio il vettore contenga solo zeri. Se poi la funzione di hash per l’ingresso "123" restituisce il numero 47, mettiamo semplicemente un 1 nel vettore all’indice 47. Così segniamo che l’hash di valore 47 l’abbiamo già visto.

var n = 8;
var numberOfValues = Math.pow(2, n);
var messages = [{id: "123"}, {id:"456"}, {id:"123"}, {id: "789"}];
var bitVector = new Array(numberOfValues);

messages.forEach(function(message) {
    var hashedId = murmurhash.v2(message.id) % numberOfValues;
    if (!bitVector[hashedId]) {
        bitVector[hashedId] = true;
        console.log(message);
    }
});

// Stampa: { id: "123" } { id: "456" } { id: "789" }

Con il codice % numberOfValues abbiamo solo troncato murmurhash in modo da ottenere una funzione di hash a n bit, niente di più. E questo è un filtro di Bloom, anche se in una versione molto degenerata. Il problema di questo approccio sono naturalmente le collisioni, che si verificano inevitabilmente: valori di ingresso diversi possono avere lo stesso hash in uscita. Per ridurre la probabilità di una collisione non useremo quindi una sola funzione di hash, ma più funzioni. Possiamo creare più funzioni di hash, per esempio, aggiungendo al valore di ingresso un po’ di sale (salt). Una semplice funzione che crei diverse funzioni di hash a n bit potrebbe essere questa:

var murmurhash = require("murmurhash");

function createNBitHashFunction(n, salt) {
    var upperBound = Math.pow(2, n);
    return function(inputString) {
        return murmurhash.v2(inputString + salt) % upperBound;
    }
}

var firstHashFunction = createNBitHashFunction(8, "nejakaSul");
var secondHashFunction = createNBitHashFunction(8, "nejakaJinaSul");

console.log(firstHashFunction("123")); // 42
console.log(secondHashFunction("123")); // 174

Possiamo scrivere così la classe che rappresenta il filtro di Bloom:

function BloomFilter(numberOfHashFunctions, numberOfBits) {
    this.reset(numberOfHashFunctions, numberOfBits);
}

BloomFilter.prototype.reset = function(numberOfHashFunctions, numberOfBits) {
    this.bitVector = new Array(Math.pow(2, numberOfBits));
    this.hashFunctions = [];

    for (var i = 0; i < numberOfHashFunctions; i++) {
        this.hashFunctions.push(createNBitHashFunction(numberOfBits, i.toString()));
    }
}

BloomFilter.prototype.add = function(item) {
    var checksum;
    for (var i = 0; i < this.hashFunctions.length; i++) {
        checksum = this.hashFunctions[i](item);
        this.bitVector[checksum] = true;
    }
}

BloomFilter.prototype.contains = function(item) {
    var checksum;
    for (var i = 0; i < this.hashFunctions.length; i++) {
        checksum = this.hashFunctions[i](item);
        if (!this.bitVector[checksum]) {
            return false;
        }
    }
    return true;
}

Il metodo add aggiunge un elemento al filtro di Bloom: calcola l’hash con tutte le funzioni di hash e salva true all’indice corrispondente.
Il metodo contains verifica invece se l’elemento dato è contenuto nel filtro di Bloom.

Il filtro di Bloom si usa facilmente:

var bloomFilter = new BloomFilter(3, 8);
var messages = [{id: "123"}, {id:"456"}, {id:"123"}, {id: "789"}];

messages.forEach(function(message) {
    if (!bloomFilter.contains(message.id)) {
        bloomFilter.add(message.id);
        console.log(message);
    }
});

// Stampa: { id: "123" } { id: "456" } { id: "789" }

E questa è tutta la magia del filtro di Bloom di base. Ha queste proprietà fondamentali:

Se il metodo contains risponde che l’elemento non è nel filtro di Bloom, significa che quell’elemento non è mai stato inserito.
Se il metodo risponde che l’elemento è presente nel filtro di Bloom, non significa necessariamente che l’elemento sia stato davvero inserito: potrebbe essersi verificata una collisione delle funzioni di hash.
In generale, per ridurre la probabilità di una risposta sbagliata, aumenta il numero di funzioni di hash oppure la loro dimensione (cioè la dimensione del valore in uscita).
Più funzioni di hash usi, più lento sarà il filtro di Bloom.
Più grandi sono le funzioni di hash che usi, più spazio occuperà il filtro di Bloom.
Una volta inserito un elemento nel filtro di Bloom, non è più possibile rimuoverlo.

« Precedente: HyperLogLog: come stimare con grande precisione il numero di valori distinti

Successivo: Cifrario di Cesare »