Bloom filter: nachází se prvek v množině?

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:

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í:

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

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

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.

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:

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

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

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]<4>;
        this.bitVector[checksum] = true;
    }
}

BloomFilter.prototype.contains = function(item) {
    var checksum;
    for (var i = 0; i < this.hashFunctions.length; i++) {
        checksum = this.hashFunctions[i]<5>;
        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:

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. Má tyto základní vlastnosti:

• Pokud metoda contains odpová, že daný prvek v Bloom Filteru není, znamená, že jste do něj daný prvek opravdu nikdy nevložili.
• Pokud metoda odpoví, že daný prvek v Bloom Filteru je přítomen, nemusí to nutně znamenat, že jste do něj daný prvek opravdu uložili — mohla totiž nastat kolize hashovacích funkcí.
• Obecně platí, že chcete-li snížit pravděpodobnost nesprávné odpovědi, zvyšte počet hashovacích funkcí nebo zvyšte jejich velikost (myšleno velikost výstupní hodnoty).
• Čím více hashovacích funkcí použíjete, tím pomalejší Bloom Filter bude.
• Čím větší hashovací funkce použijete, tím více místa bude Bloom Filter zabírat.
• Pokud jednou nějaký prvek do Bloom Filteru vložíte, už ho není možné odstranit.