Bloom-filter: finnes elementet i mengden?

Et Bloom-filter er en probabilistisk struktur som lar oss med en viss sannsynlighet si om et element x finnes i mengden M.

I systemet vårt trenger vi for eksempel å måle hvor mange ganger brukerne har klikket på et reklamebanner. Etter hvert klikk får vi en HTTP GET-forespørsel som forteller oss at brukeren XYZ klikket på reklamen 123. Av og til hender det at en bruker ved en feil dobbeltklikker med musen, og da får vi to forespørsler. Vi vil gjerne filtrere bort disse forespørslene og ha dem registrert i databasen som ett klikk.

Vi trenger derfor en applikasjon som leser en kanal med meldinger om klikk og filtrerer bort duplikater. Hvordan ville vi gjort det? Hver slik melding har en ID, så vi trenger ikke å sammenligne hele meldingen, det er nok å finne ut om vi tidligere har behandlet en melding med samme ID. Enkel kode i JavaScript som fjernet duplikater fra en strøm (her for enkelhets skyld fra en tabell) av meldinger, kunne se slik ut:

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

Denne løsningen holder til vi går tom for minne — og det kommer vi til å gjøre, for mengden processedIds vil etter hvert bare vokse og vokse. Vi kan selvfølgelig programmere inn en utløpstid for dataene — vi kan alltid fjerne meldinger som er eldre enn én time, eller noe lignende.

Verre er det når ikke engang det er nok. Hva om vi trenger å ha data for minst ett døgn i mengden processedIds, og går gjennom for eksempel ti tusen meldinger i sekundet? I verste fall må vi lagre opptil 864 000 000 ID-er. Hvis vi bruker uuid v4, har hver ID lengde 36, og det betyr at vi må lagre minst 31 GB per døgn. Det er litt mye. Kan vi ikke redusere minnebruken?

Bloom-filter

I stedet for å lagre hele ID-en kan vi lagre bare hashen av den. Vi kan bruke den klassiske murmurhash, som for hver streng gir et 32-bits heltall og dessuten har god fordeling:

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

Videre bruker vi et triks med en bitvektor. Det er en tabell der vi bare lagrer nuller og enere. Hvis vi har en n-bits hashfunksjon, trenger vi en vektor med størrelse 2ⁿ for å kunne adressere alle mulige outputverdier fra hashfunksjonen i vektoren. Ideen er at vektoren i begynnelsen inneholder bare nuller. Hvis hashfunksjonen så gir oss tallet 47 for input "123", setter vi rett og slett inn en ener i vektoren på indeks 47. Dermed har vi markert at vi allerede har sett hashen med verdi 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 bare kuttet murmurhash slik at den ble en n-bits hashfunksjon, ikke noe mer. Og dette er et Bloom-filter. Riktignok en ganske degenerert versjon. Problemet med denne framgangsmåten er selvfølgelig kollisjonene, som nødvendigvis vil oppstå. Ulike inputverdier kan ha den samme outputhashen. For å redusere sannsynligheten for at det skjer en kollisjon, bruker vi derfor ikke bare én hashfunksjon, men flere. Flere hashfunksjoner kan vi lage for eksempel ved å legge til litt salt til inputverdien. En enkel funksjon som lager ulike n-bits hashfunksjoner, kunne se slik ut:

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

Klassen som representerer et Bloom-filter, kan vi skrive slik:

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 legger et element til i Bloom-filteret: den regner ut hashen med alle hashfunksjonene og lagrer true på den tilsvarende indeksen.
• Metoden contains finner så ut om det gitte elementet finnes i Bloom-filteret.

Bloom-filteret kan vi bruke 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" }

Og det er hele magien i et grunnleggende Bloom-filter. Det har disse grunnleggende egenskapene:

• Hvis metoden contains svarer at det gitte elementet ikke er i Bloom-filteret, betyr det at du virkelig aldri har satt det inn i det.
• Hvis metoden svarer at det gitte elementet er til stede i Bloom-filteret, betyr det ikke nødvendigvis at du virkelig har lagret det — det kan nemlig ha oppstått en kollisjon mellom hashfunksjonene.
• Generelt gjelder at hvis du vil redusere sannsynligheten for et feil svar, øker du antall hashfunksjoner eller øker størrelsen deres (ment som størrelsen på outputverdien).
• Jo flere hashfunksjoner du bruker, jo tregere blir Bloom-filteret.
• Jo større hashfunksjoner du bruker, jo mer plass tar Bloom-filteret.
• Når du først har satt et element inn i Bloom-filteret, er det ikke mulig å fjerne det igjen.