Bloom filter je pravděpodobnostní struktura, která nám umožňuje s jistou mírou pravděpodobnosti říci, zda se nějaký prvek x nachází v množině M.

V našem systému například potřebujeme měřit, kolikrát uživatelé klikli na reklamní banner. Po každém kliknutí k nám přijde HTTP GET požadavek informující nás o tom, že uživatel XYZ klikl na reklamu 123. Občas se stane, že uživatel omylem myší dvojklikne a nám tak přijdou dva požadavky. My bychom rádi tyto požadavky odfiltrovali a měli je v databázi zaznamenané jako jeden klik.

Potřebujeme proto aplikaci, která bude číst kanál se zprávami o klicích a bude odfiltrovávat duplikace. Jak bychom to udělali? Každá taková zpráva má nějaké ID, nemusíme proto porovnávat celou zprávu, stačí nám zjistit, jestli jsme už někdy nezpracovali zprávu se stejným ID. Jednoduchý kód v JavaScriptu, který by odstraňoval duplikace ze streamu (zde pro jednoduchost z pole) zpráv by mohl vypadat takto:

1
2
3
4
5
6
7
8
9
10
11

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

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

Toto řešení bude stačit do doby, než nám dojde paměť – a ta jednou dojde, protože množina processedIds bude časem jen a pouze růst. Můžeme samozřejmě doprogramovat nějakou expiraci dat – můžeme vždy odstranit zprávy starší než jedna hodina nebo něco podobného.

Horší je, když ani to nestačí. Co když potřebujeme mít v množině processedIds data za alespoň jeden den a procházíme třeba deset tisíc zpráv za sekundu? V nejhorším případě potřebujeme uložit až 864 000 000 Idéček. Používáme-li uuid v4, má každé ID délku 36, což znamená, že za den potřebujeme uložit nejméně 32 GB. To je trochu hodně. Nešla by ta paměťová náročnost snížit?

Bloom filter

Místo toho, abychom si ukládali celé ID, můžeme si ukládat jen jeho hash. Můžeme použít klasickou murmurhash, která vrací pro každý string 32bitové celé číslo, navíc má dobré rozdělení. Dále použijeme fígl s bitovým vektorem. To je pole, do kterého budeme ukládat jen nuly a jedničky. Máme-li n-bitovou hashovací funkci, potřebujeme vektor o velikosti 2ⁿ, abychom byli schopni ve vektoru adresovat všechny možné výstupy hashovací funkce. Idea je, že na začátku obsahuje vektor samé nuly. Pokud nám pak hashovací funkce pro vstup "123" vrátí číslo 47, jednoduše do vektoru na index 47 vložíme jedničku. Tím si označíme, že hash o hodnotě 47 jsme už viděli.

1
2
3
4
5
6
7
8
9
10
11
12
13
14

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

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

Tím kódem % numberOfValues jsme jen ořezali murmurhash tak, aby z ní byla n-bitová hashovací funkce, nic víc. A toto je Bloom filter. I když taková hodně degenerovaná verze. Problémem tohoto přístupu jsou pochopitelně kolize, které nutně nastanou. Různé vstupní hodnoty mohou mít stejný výstupní hash.

Abychom proto snížili pravděpodobnost, že dojde ke kolizi, nepoužijeme pouze jednu hashovací funkci, ale použijeme jich více. Více hashovacích funkcí můžeme vytvořit například tím, že k vstupní hodnotě přidáme nějakou sůl. Jednoduchá funkce, která by vytvářela různé n-bitové hashovací funkce by mohla vypadat takto:

1
2
3
4
5
6
7
8
9
10
11
12
13
14

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

Tyto dvě hashovací funkce bychom využili tak, že bychom vstupní hodnut zahashovali oběma funkcemi a na oba vygenerované indexy bychom uložili jedničku, tj. pro vstup "123" bychom uložili do bitové vektoru jedničky na indexy 42 i na 174.

Při následném dotazu na to, zda jsme už string "123" viděli, ho opět zahashujeme stejnými funkcemi a opět nám vyjdou indexy 42 a 174. Podíváme se na hodnoty v bitovém vektoru a pokud je na jednom z indexů nula, string jsme si do množiny neuložili. Pokud tam budou dvě jedničky, tento string jsme asi do množiny uložili. Samozřejmě může nastat případ, že nějaký úplně jiný string se zahashoval na dvojici čísel 42 a 174, tj. nastala kolize. To se s Bloom filter může stát.

Algoritmus Bloom filteru

Algoritmus Bloom filteru bychom proto mohli napsat takto:

• Inicializace:
  1. Zvolíme počet hashovacích funkcí a jejich velikost
  2. Inicializujeme bitový vektor nulami, a to tak, abychom v něm mohli adresovat všechny hodnoty hashovací funkce.
• Přidání prvku do pole:
  1. Vstupní hodnotu zahashujeme všemi hashovacími funkcemi a uložíme si do bitového vektoru na příslušná místa jedničku.
• Kontrola existence prvku v množině:
  1. Hledanou hodnotu zahashujeme všemi hashovacími funkcemi
  2. Pokud pro alespoň jeden výsledek hashovací funkce platí, že na daném indexu bitového pole je nula, hledaný prvek v množině není.
  3. V opačném případě tam asi je.

Implementace v JavaScriptu

Třídu reprezentující Bloom filter můžeme napsat takto:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

function BloomFilter(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 přidává prvek do Bloom filteru: spočítá hash všemi hashovacími funkce a na odpovídající index uloží true.
• Metoda contains pak zjišťuje, jestli jedaný prvek obsažen v Bloom filteru.

Bloom filter můžeme použít snadno:

1
2
3
4
5
6
7
8
9
10
11

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

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

A to je celá magie základního Bloom Filteru.

Vlastnosti Bloom filteru

• Nejzásadnější vlastností je, že paměťová náročnost Bloom filteru je velmi nízká, o několik řádů nižší, než kdybychom ukládali všechna IDéčka. Potřebujeme uložit pouze bitový vektor, nic více.
• Pokud metoda contains odpoví, že daný prvek v Bloom Filteru není, znamená, že jsme do něj daný prvek opravdu nikdy nevložili.
• Pokud metoda contains odpoví, že daný prvek v Bloom Filteru je přítomen, nemusí to nutně znamenat, že jsme do něj daný prvek opravdu uložili – mohla totiž nastat kolize hashovacích funkcí.
• Obecně platí, že chceme-li snížit pravděpodobnost nesprávné odpovědi, musíme zvýšit počet hashovacích funkcí nebo zvýšit jejich velikost (myšleno velikost výstupní hodnoty).
• Čím více hashovacích funkcí použijeme, tím pomalejší Bloom Filter bude.
• Čím větší hashovací funkce použijeme, tím více místa bude Bloom Filter zabírat.
• Pokud jednou nějaký prvek do Bloom Filteru vložíme, už ho není možné odstranit.
• Bloom filter nikdy “nenaplníme”, uložíme do něj nekonečně hodnot. Jenom nám bude neustále růst pravděpodobnost kolize.

Existují varianty Bloom filteru, které například umožňují odstraňovat jednou přidané prvky. O těch si povíme příště.

Příklady použití

Bloom filter je v praxi hojně používaný, viz příklady na Wiki.