Bloom-szűrő: benne van-e az elem a halmazban?

A Bloom-szűrő valószínűségi adatszerkezet, amely lehetővé teszi, hogy bizonyos valószínűséggel megmondjuk, hogy egy x elem benne van-e az M halmazban.

A rendszerünkben például mérnünk kell, hányszor kattintottak a felhasználók egy reklámbannerre. Minden kattintás után HTTP GET kérés érkezik hozzánk arról, hogy az XYZ felhasználó rákattintott a 123-as reklámra. Néha megesik, hogy a felhasználó véletlenül duplán kattint az egérrel, és így két kérés érkezik. Ezeket a kéréseket szeretnénk kiszűrni, és egy kattintásként rögzíteni az adatbázisban.

Szükségünk van tehát egy alkalmazásra, amely olvassa a kattintásokról szóló üzenetek csatornáját, és kiszűri az ismétlődéseket. Hogyan csinálnánk? Minden ilyen üzenetnek van valamilyen azonosítója, ezért nem kell az egész üzenetet összehasonlítanunk, elég kideríteni, hogy feldolgoztunk-e már valaha azonos azonosítójú üzenetet. Az ismétlődéseket az üzenetek folyamából (itt az egyszerűség kedvéért tömbből) kiszűrő egyszerű JavaScript-kód így nézhet ki:

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

// Kiírja: { id: "123" } { id: "456" } { id: "789" }

Ez a megoldás addig elég, amíg el nem fogy a memória – és el fog fogyni, mert a processedIds halmaz idővel csak és kizárólag nőni fog. Természetesen hozzáprogramozhatunk valamilyen adatlejáratást – mindig eltávolíthatjuk az egy óránál régebbi üzeneteket vagy valami hasonlót.

Rosszabb a helyzet, ha ez sem elég. Mi van, ha a processedIds halmazban legalább egy nap adataira van szükségünk, és másodpercenként mondjuk tízezer üzenetet dolgozunk fel? A legrosszabb esetben akár 864 000 000 azonosítót kell tárolnunk. Ha uuid v4 azonosítót használunk, minden azonosító hossza 36, vagyis naponta legalább 31 GB tárolására van szükségünk. Ez egy kicsit sok. Nem lehetne csökkenteni a memóriaigényt?

Bloom-szűrő

Ahelyett, hogy az egész azonosítót tárolnánk, tárolhatjuk csak a hash-ét. Használhatjuk a klasszikus murmurhash függvényt, amely minden sztringhez 32 bites egész számot ad vissza, ráadásul jó az eloszlása:

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

// Kiírja: { id: "123" } { id: "456" } { id: "789" }

Ezután bevetjük a bitvektoros trükköt. Ez egy olyan tömb, amelyben csak nullákat és egyeseket tárolunk. Ha n bites hash-függvényünk van, 2ⁿ méretű vektorra van szükségünk, hogy a vektorban a hash-függvény minden lehetséges kimenetét megcímezhessük. Az ötlet az, hogy a vektor az elején csupa nullát tartalmaz. Ha a hash-függvény a "123" bemenetre mondjuk a 47-et adja vissza, egyszerűen beírunk egy egyest a vektor 47-es indexére. Ezzel megjelöljük, hogy a 47 értékű hash-t már láttuk.

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

// Kiírja: { id: "123" } { id: "456" } { id: "789" }

A % numberOfValues kóddal csak levágtuk a murmurhasht, hogy n bites hash-függvény legyen belőle, semmi több. És ez a Bloom-szűrő. Igaz, elég elfajult változata. Ennek a megközelítésnek természetesen az ütközések a gondja, amelyek szükségszerűen bekövetkeznek. Különböző bemeneti értékeknek lehet ugyanaz a kimeneti hash-e. Ezért az ütközés valószínűségének csökkentésére nem egyetlen hash-függvényt használunk, hanem többet. Több hash-függvényt készíthetünk például úgy, hogy a bemeneti értékhez hozzáadunk valamilyen sót. Egy egyszerű függvény, amely különböző n bites hash-függvényeket hoz létre, így nézhet ki:

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

A Bloom-szűrőt megvalósító osztályt így írhatjuk meg:

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

• Az add metódus hozzáad egy elemet a Bloom-szűrőhöz: kiszámolja a hash-t az összes hash-függvénnyel, és a megfelelő indexen true értéket tárol.
• A contains metódus pedig azt vizsgálja, hogy az adott elem benne van-e a Bloom-szűrőben.

A Bloom-szűrőt könnyen használhatjuk:

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

// Kiírja: { id: "123" } { id: "456" } { id: "789" }

És ez az alap Bloom-szűrő egész varázsa. Ezek az alapvető tulajdonságai:

• Ha a contains metódus azt feleli, hogy az adott elem nincs a Bloom-szűrőben, az azt jelenti, hogy tényleg soha nem tetted bele.
• Ha a metódus azt feleli, hogy az adott elem benne van a Bloom-szűrőben, az nem feltétlenül jelenti, hogy tényleg betetted – bekövetkezhetett ugyanis a hash-függvények ütközése.
• Általában igaz, hogy ha csökkenteni akarod a helytelen válasz valószínűségét, növeld a hash-függvények számát, vagy növeld a méretüket (a kimeneti érték méretére gondolunk).
• Minél több hash-függvényt használsz, annál lassabb lesz a Bloom-szűrő.
• Minél nagyobb hash-függvényeket használsz, annál több helyet foglal a Bloom-szűrő.
• Ha egyszer beleteszel egy elemet a Bloom-szűrőbe, már nem lehet eltávolítani.