Bloomfilter: finns elementet i mängden?

Bloomfilter är en probabilistisk datastruktur som låter oss med viss sannolikhet avgöra om ett element x finns i en mängd M.

I vårt system behöver vi till exempel mäta hur många gånger användarna har klickat på en reklambanner. Vid varje klick får vi en HTTP GET-förfrågan som talar om att användaren XYZ har klickat på annons 123. Ibland händer det att användaren av misstag dubbelklickar med musen, och då får vi två förfrågningar. Vi vill gärna filtrera bort dubbletterna och ha dem registrerade i databasen som ett enda klick.

Vi behöver därför en applikation som läser en kanal med meddelanden om klick och filtrerar bort dubbletter. Hur skulle vi göra det? Varje sådant meddelande har något id, så vi behöver inte jämföra hela meddelandet, utan det räcker att ta reda på om vi redan har behandlat ett meddelande med samma id. En enkel kod i JavaScript som tar bort dubbletter ur en ström av meddelanden (här för enkelhetens skull ur en array) kunde se ut så här:

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

// Skriver ut: { id: "123" } { id: "456" } { id: "789" }

Den här lösningen räcker tills vi får slut på minne — och det kommer att hända, eftersom mängden processedIds med tiden bara växer och växer. Vi kan förstås programmera in något slags utgångstid för data — vi kan alltid ta bort meddelanden som är äldre än en timme eller något liknande.

Värre är det när inte ens det räcker. Tänk om vi behöver ha data för minst ett dygn i mängden processedIds och går igenom till exempel tiotusen meddelanden per sekund? I värsta fall behöver vi spara upp till 864 000 000 id:n. Om vi använder uuid v4 är varje id 36 tecken långt, vilket betyder att vi behöver spara minst 31 GB per dygn. Det är lite mycket. Går det inte att minska minnesbehovet?

Bloomfilter

I stället för att spara hela id:t kan vi spara bara dess hash. Vi kan använda den klassiska murmurhash, som för varje sträng returnerar ett 32-bitars heltal och dessutom har en bra fördelning:

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

// Skriver ut: { id: "123" } { id: "456" } { id: "789" }

Sedan använder vi ett knep med en bitvektor. Det är en array där vi bara sparar nollor och ettor. Om vi har en n-bitars hashfunktion behöver vi en vektor av storleken 2ⁿ, så att vi kan adressera alla möjliga utdata från hashfunktionen. Tanken är att vektorn från början består av bara nollor. Om hashfunktionen sedan returnerar talet 47 för indata "123" sätter vi helt enkelt in en etta på index 47 i vektorn. På så sätt markerar vi att vi redan har sett hashvärdet 47.

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

// Skriver ut: { id: "123" } { id: "456" } { id: "789" }

Med koden % numberOfValues har vi bara kapat murmurhash så att den blir en n-bitars hashfunktion, inget mer. Och det här är ett Bloomfilter. Visserligen en mycket urartad version. Problemet med det här tillvägagångssättet är förstås kollisioner, som med nödvändighet uppstår. Olika indata kan ge samma hashvärde. För att minska sannolikheten för kollision använder vi därför inte bara en hashfunktion, utan flera. Flera hashfunktioner kan vi skapa till exempel genom att lägga till något salt till indata. En enkel funktion som skapar olika n-bitars hashfunktioner kunde se ut så här:

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

En klass som representerar ett Bloomfilter kan vi skriva så här:

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

• Metoden add lägger till ett element i Bloomfiltret: den räknar ut hashvärdet med alla hashfunktioner och sparar true på motsvarande index.
• Metoden contains tar reda på om elementet finns i Bloomfiltret.

Bloomfiltret kan vi använda enkelt:

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

// Skriver ut: { id: "123" } { id: "456" } { id: "789" }

Och det är hela magin bakom ett grundläggande Bloomfilter. Det har följande grundläggande egenskaper:

• Om metoden contains svarar att elementet inte finns i Bloomfiltret betyder det att du verkligen aldrig har lagt in det.
• Om metoden svarar att elementet finns i Bloomfiltret behöver det inte nödvändigtvis betyda att du har lagt in det — det kan nämligen ha uppstått en kollision mellan hashfunktionerna.
• I allmänhet gäller att om du vill minska sannolikheten för ett felaktigt svar ska du öka antalet hashfunktioner eller göra dem större (med storlek menas storleken på utdata).
• Ju fler hashfunktioner du använder, desto långsammare blir Bloomfiltret.
• Ju större hashfunktioner du använder, desto mer plats tar Bloomfiltret.
• När du en gång har lagt in ett element i Bloomfiltret går det inte att ta bort det.