✖

Filtrul Bloom: se află elementul în mulțime?

Filtrul Bloom (Bloom filter) este o structură probabilistică care ne permite să spunem, cu un anumit grad de probabilitate, dacă un element x se află într-o mulțime M.

În sistemul nostru, de exemplu, trebuie să măsurăm de câte ori au dat utilizatorii clic pe un banner publicitar. După fiecare clic primim o cerere HTTP GET care ne informează că utilizatorul XYZ a dat clic pe reclama 123. Uneori se întâmplă ca utilizatorul să dea din greșeală dublu clic cu mouse-ul, iar noi primim astfel două cereri. Am vrea să filtrăm aceste cereri și să le avem în baza de date înregistrate ca un singur clic.

Avem deci nevoie de o aplicație care să citească canalul de mesaje despre clicuri și să filtreze duplicatele. Cum am face asta? Fiecare astfel de mesaj are un ID, deci nu trebuie să comparăm mesajul întreg, ne ajunge să aflăm dacă n-am procesat cumva deja un mesaj cu același ID. Un cod simplu în JavaScript care ar elimina duplicatele dintr-un stream (aici, pentru simplitate, dintr-un tablou) de mesaje ar putea arăta astfel:

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);
    }
});

// Afișează: { id: "123" } { id: "456" } { id: "789" }

Această soluție va funcționa până când ni se termină memoria – și odată se va termina, pentru că mulțimea processedIds va tot crește cu timpul. Putem, desigur, să programăm o expirare a datelor – putem elimina de fiecare dată mesajele mai vechi de o oră sau ceva asemănător.

Mai rău este când nici asta nu ajunge. Ce facem dacă avem nevoie ca în mulțimea processedIds să fie datele pentru cel puțin o zi și parcurgem, să zicem, zece mii de mesaje pe secundă? În cel mai rău caz trebuie să stocăm până la 864.000.000 de ID-uri. Dacă folosim uuid v4, fiecare ID are lungimea 36, ceea ce înseamnă că pe zi trebuie să stocăm cel puțin 31 GB. Este cam mult. Nu s-ar putea reduce consumul de memorie?

Filtrul Bloom

În loc să stocăm ID-ul întreg, putem stoca doar hash-ul lui. Putem folosi clasica murmurhash, care returnează pentru fiecare string un număr întreg de 32 de biți și, în plus, are o repartiție bună:

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);
    }
});

// Afișează: { id: "123" } { id: "456" } { id: "789" }

Mai departe folosim un truc cu vectorul de biți. Este un tablou în care vom stoca doar zerouri și unu. Dacă avem o funcție hash de n biți, avem nevoie de un vector de dimensiune 2n, ca să putem adresa în vector toate ieșirile posibile ale funcției hash. Ideea este că la început vectorul conține numai zerouri. Dacă apoi funcția hash ne returnează pentru intrarea "123" numărul 47, pur și simplu punem un unu în vector la indexul 47. Astfel marcăm că hash-ul cu valoarea 47 l-am văzut deja.

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);
    }
});

// Afișează: { id: "123" } { id: "456" } { id: "789" }

Cu codul % numberOfValues am tăiat doar murmurhash-ul astfel încât să devină o funcție hash de n biți, nimic mai mult. Și acesta este filtrul Bloom. Deși într-o versiune foarte degenerată. Problema acestei abordări sunt, desigur, coliziunile, care apar în mod necesar. Valori de intrare diferite pot avea același hash de ieșire. Pentru a reduce deci probabilitatea unei coliziuni, nu folosim o singură funcție hash, ci mai multe. Mai multe funcții hash putem crea, de exemplu, adăugând la valoarea de intrare un șir suplimentar (așa-numitul salt). O funcție simplă care ar crea diferite funcții hash de n biți ar putea arăta astfel:

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

Clasa care reprezintă un filtru Bloom o putem scrie astfel:

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;
}
  • Metoda add adaugă un element în filtrul Bloom: calculează hash-ul cu toate funcțiile hash și stochează true la indexul corespunzător.
  • Metoda contains verifică apoi dacă elementul dat este conținut în filtrul Bloom.

Filtrul Bloom se poate folosi simplu:

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);
    }
});

// Afișează: { id: "123" } { id: "456" } { id: "789" }

Și asta este toată magia filtrului Bloom de bază. Are aceste proprietăți de bază:

  • Dacă metoda contains răspunde că elementul dat nu se află în filtrul Bloom, înseamnă că nu l-ai introdus niciodată în el.
  • Dacă metoda răspunde că elementul dat este prezent în filtrul Bloom, nu înseamnă neapărat că l-ai introdus într-adevăr – s-ar putea să fi apărut o coliziune a funcțiilor hash.
  • În general, dacă vrei să reduci probabilitatea unui răspuns greșit, mărește numărul de funcții hash sau mărește dimensiunea lor (adică dimensiunea valorii de ieșire).
  • Cu cât folosești mai multe funcții hash, cu atât filtrul Bloom va fi mai lent.
  • Cu cât folosești funcții hash mai mari, cu atât filtrul Bloom va ocupa mai mult loc.
  • Dacă ai introdus o dată un element în filtrul Bloom, nu mai este posibil să îl elimini.