Bloom-filter: findes elementet i mængden?

Et Bloom-filter er en probabilistisk struktur, som gør det muligt med en vis sandsynlighed at sige, om et element x findes i mængden M.

I vores system har vi fx brug for at måle, hvor mange gange brugerne klikkede på et reklamebanner. Efter hvert klik kommer der en HTTP GET-forespørgsel til os, som fortæller, at brugeren XYZ klikkede på reklamen 123. Af og til sker det, at en bruger ved en fejl dobbeltklikker med musen, og så får vi to forespørgsler. Vi vil gerne filtrere disse forespørgsler fra og have dem registreret i databasen som ét klik.

Vi har derfor brug for en applikation, der læser en kanal med beskeder om klik og filtrerer dubletter fra. Hvordan ville vi gøre det? Hver sådan besked har et ID, så vi behøver ikke sammenligne hele beskeden, det er nok at finde ud af, om vi allerede på et tidspunkt har behandlet en besked med det samme ID. Enkel kode i JavaScript, som ville fjerne dubletter fra en strøm (her for enkelhedens skyld fra et array) af beskeder, kunne se sådan her ud:

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

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

Denne løsning rækker, indtil vi løber tør for hukommelse — og det gør vi en dag, fordi mængden processedIds med tiden kun vil vokse. Vi kan selvfølgelig programmere en form for udløb af data — vi kan altid fjerne beskeder, der er ældre end en time, eller noget lignende.

Værre er det, når selv det ikke er nok. Hvad nu, hvis vi har brug for at have data for mindst et døgn i mængden processedIds, og vi fx gennemgår ti tusind beskeder i sekundet? I værste fald skal vi gemme op til 864.000.000 ID'er. Bruger vi uuid v4, har hvert ID længden 36, hvilket betyder, at vi på et døgn skal gemme mindst 31 GB. Det er lidt meget. Kunne man ikke nedbringe hukommelsesforbruget?

Bloom-filter

I stedet for at gemme hele ID'et kan vi nøjes med at gemme dets hash. Vi kan bruge den klassiske murmurhash, som for hver streng returnerer et 32-bit heltal og desuden har en 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);
    }
});

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

Dernæst bruger vi et trick med en bitvektor. Det er et array, hvori vi kun gemmer nuller og ettaller. Har vi en n-bit hashfunktion, har vi brug for en vektor af størrelsen 2ⁿ, så vi kan adressere alle mulige outputs fra hashfunktionen i vektoren. Ideen er, at vektoren i begyndelsen indeholder udelukkende nuller. Hvis hashfunktionen så for inputtet "123" returnerer tallet 47, sætter vi simpelthen et ettal ind i vektoren på indeks 47. Dermed markerer vi, at vi allerede har set en hash med værdien 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);
    }
});

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

Med koden % numberOfValues har vi blot beskåret murmurhash, så den blev en n-bit hashfunktion, intet mere. Og det er et Bloom-filter. Om end en meget degenereret version. Problemet ved denne tilgang er naturligvis kollisioner, som nødvendigvis vil opstå. Forskellige inputværdier kan have den samme output-hash. For at mindske sandsynligheden for en kollision bruger vi derfor ikke kun én hashfunktion, men flere. Flere hashfunktioner kan vi lave fx ved at føje noget salt til inputværdien. En enkel funktion, der kunne danne forskellige n-bit hashfunktioner, kunne se sådan her ud:

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, der repræsenterer et Bloom-filter, kan vi skrive sådan her:

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 tilføjer et element til Bloom-filteret: den beregner hashen med alle hashfunktionerne og gemmer true på det tilsvarende indeks.
Metoden contains undersøger så, om det givne element er indeholdt i Bloom-filteret.

Bloom-filteret kan vi bruge helt 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);
    }
});

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

Og det er hele magien i et grundlæggende Bloom-filter. Det har disse grundlæggende egenskaber:

Hvis metoden contains svarer, at det givne element ikke er i Bloom-filteret, betyder det, at du virkelig aldrig har indsat det i det.
Hvis metoden svarer, at det givne element er til stede i Bloom-filteret, behøver det ikke nødvendigvis betyde, at du virkelig har gemt det — der kan nemlig være opstået en kollision mellem hashfunktionerne.
Generelt gælder, at hvis du vil mindske sandsynligheden for et forkert svar, skal du øge antallet af hashfunktioner eller øge deres størrelse (altså størrelsen af outputværdien).
Jo flere hashfunktioner du bruger, desto langsommere bliver Bloom-filteret.
Jo større hashfunktioner du bruger, desto mere plads fylder Bloom-filteret.
Når du først har indsat et element i Bloom-filteret, er det ikke muligt at fjerne det igen.

« Forrige: HyperLogLog: Sådan estimerer du meget præcist antallet af unikke værdier

Næste: Cæsarchiffer »