Bloomfilter: zit een element in de verzameling?

Een bloomfilter is een probabilistische structuur waarmee we met een bepaalde kans kunnen zeggen of een element x in een verzameling M zit.

In ons systeem moeten we bijvoorbeeld meten hoe vaak gebruikers op een advertentiebanner hebben geklikt. Na elke klik krijgen we een HTTP GET-verzoek dat ons meldt dat gebruiker XYZ op advertentie 123 heeft geklikt. Soms gebeurt het dat een gebruiker per ongeluk dubbelklikt met de muis en wij dus twee verzoeken krijgen. Die verzoeken willen we graag wegfilteren en in de database als één klik registreren.

We hebben dus een applicatie nodig die een kanaal met berichten over kliks leest en duplicaten wegfiltert. Hoe zouden we dat doen? Elk zo'n bericht heeft een id, dus we hoeven niet het hele bericht te vergelijken, het volstaat te weten of we al eens een bericht met dezelfde id hebben verwerkt. Een eenvoudige code in JavaScript die duplicaten uit een stream (hier voor de eenvoud uit een array) van berichten zou verwijderen, zou er zo uit kunnen zien:

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

// Drukt af: { id: "123" } { id: "456" } { id: "789" }

Deze oplossing volstaat tot ons geheugen op is — en dat raakt op, want de verzameling processedIds zal na verloop van tijd alleen maar groeien. We kunnen natuurlijk een vervaltermijn voor de gegevens programmeren — we kunnen steeds berichten ouder dan een uur verwijderen of iets dergelijks.

Erger is het als zelfs dat niet volstaat. Wat als we in de verzameling processedIds gegevens van minstens één dag nodig hebben en bijvoorbeeld tienduizend berichten per seconde doorlopen? In het ergste geval moeten we wel 864 000 000 id's opslaan. Als we uuid v4 gebruiken, heeft elke id lengte 36, wat betekent dat we per dag minstens 31 GB moeten opslaan. Dat is nogal veel. Kunnen we dat geheugengebruik niet verlagen?

Bloomfilter

In plaats van de hele id op te slaan, kunnen we alleen de hash ervan opslaan. We kunnen de klassieke murmurhash gebruiken, die voor elke string een geheel getal van 32 bits teruggeeft en bovendien een goede verdeling heeft:

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

// Drukt af: { id: "123" } { id: "456" } { id: "789" }

Vervolgens gebruiken we de truc met een bitvector. Dat is een array waarin we alleen nullen en enen opslaan. Als we een n-bits hashfunctie hebben, hebben we een vector van grootte 2ⁿ nodig om in de vector alle mogelijke uitvoerwaarden van de hashfunctie te kunnen adresseren. Het idee is dat de vector aan het begin alleen nullen bevat. Als de hashfunctie voor de invoer "123" het getal 47 teruggeeft, zetten we gewoon een één in de vector op index 47. Zo noteren we dat we de hash met waarde 47 al hebben gezien.

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

// Drukt af: { id: "123" } { id: "456" } { id: "789" }

Met de code % numberOfValues hebben we murmurhash alleen afgekapt zodat het een n-bits hashfunctie werd, niets meer. En dit is een bloomfilter. Al is het een erg gedegenereerde versie. Het probleem van deze aanpak zijn vanzelfsprekend de botsingen, die onvermijdelijk optreden. Verschillende invoerwaarden kunnen dezelfde uitvoerhash hebben. Om de kans op een botsing te verkleinen, gebruiken we daarom niet maar één hashfunctie, maar meer. Meer hashfuncties kunnen we bijvoorbeeld maken door aan de invoerwaarde een salt toe te voegen. Een eenvoudige functie die verschillende n-bits hashfuncties maakt, zou er zo uit kunnen zien:

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, "eenSalt");
var secondHashFunction = createNBitHashFunction(8, "eenAndereSalt");

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

De klasse die een bloomfilter voorstelt, kunnen we zo schrijven:

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

• De methode add voegt een element toe aan het bloomfilter: ze berekent de hash met alle hashfuncties en slaat op de bijbehorende index true op.
• De methode contains stelt vervolgens vast of het gegeven element in het bloomfilter zit.

Het bloomfilter kunnen we eenvoudig gebruiken:

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

// Drukt af: { id: "123" } { id: "456" } { id: "789" }

En dat is de hele magie van een basaal bloomfilter. Het heeft deze basiseigenschappen:

• Als de methode contains antwoordt dat het gegeven element niet in het bloomfilter zit, betekent dat dat je dat element er echt nooit in hebt gestopt.
• Als de methode antwoordt dat het gegeven element in het bloomfilter aanwezig is, hoeft dat niet noodzakelijk te betekenen dat je dat element er echt in hebt opgeslagen — er kan namelijk een botsing van hashfuncties zijn opgetreden.
• In het algemeen geldt dat als je de kans op een onjuist antwoord wilt verkleinen, je het aantal hashfuncties moet vergroten of hun grootte moet vergroten (bedoeld wordt de grootte van de uitvoerwaarde).
• Hoe meer hashfuncties je gebruikt, hoe trager het bloomfilter wordt.
• Hoe groter de hashfuncties die je gebruikt, hoe meer ruimte het bloomfilter inneemt.
• Als je een element eenmaal in het bloomfilter hebt gestopt, is het niet meer mogelijk om het te verwijderen.