✖

Bloomfilter: Ist ein Element in der Menge enthalten?

Ein Bloomfilter ist eine probabilistische Struktur, die es uns erlaubt, mit einer gewissen Wahrscheinlichkeit zu sagen, ob sich ein Element x in der Menge M befindet.

In unserem System müssen wir zum Beispiel messen, wie oft Nutzer auf ein Werbebanner geklickt haben. Nach jedem Klick erreicht uns eine HTTP-GET-Anfrage, die uns mitteilt, dass der Nutzer XYZ auf die Werbung 123 geklickt hat. Ab und zu passiert es, dass ein Nutzer versehentlich mit der Maus doppelklickt und uns dadurch zwei Anfragen erreichen. Wir würden diese Anfragen gern herausfiltern und in der Datenbank als einen Klick erfassen.

Wir brauchen also eine Anwendung, die den Kanal mit den Klick-Nachrichten liest und Duplikate herausfiltert. Wie würden wir das machen? Jede dieser Nachrichten hat eine ID, wir müssen also nicht die ganze Nachricht vergleichen, es genügt herauszufinden, ob wir nicht schon einmal eine Nachricht mit derselben ID verarbeitet haben. Einfacher JavaScript-Code, der aus einem Stream von Nachrichten (hier der Einfachheit halber aus einem Array) Duplikate entfernt, könnte so aussehen:

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

// Gibt aus: { id: "123" } { id: "456" } { id: "789" }

Diese Lösung reicht, bis uns der Speicher ausgeht – und der geht irgendwann aus, denn die Menge processedIds wird mit der Zeit nur noch wachsen. Wir können natürlich noch eine Art Ablaufzeit für die Daten programmieren – wir können immer Nachrichten entfernen, die älter als eine Stunde sind, oder etwas Ähnliches.

Schlimmer ist es, wenn auch das nicht genügt. Was ist, wenn wir in der Menge processedIds Daten für mindestens einen Tag brauchen und zum Beispiel zehntausend Nachrichten pro Sekunde durchlaufen? Im schlimmsten Fall müssen wir bis zu 864.000.000 IDs speichern. Verwenden wir UUID v4, hat jede ID die Länge 36, das heißt, wir müssen pro Tag mindestens 31 GB speichern. Das ist ziemlich viel. Ließe sich der Speicherbedarf nicht senken?

Bloomfilter

Statt die ganze ID zu speichern, können wir nur ihren Hashwert speichern. Wir können den klassischen MurmurHash verwenden, der für jeden String eine 32-Bit-Ganzzahl zurückgibt und außerdem eine gute Verteilung hat:

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

// Gibt aus: { id: "123" } { id: "456" } { id: "789" }

Als Nächstes verwenden wir den Kniff mit dem Bitvektor. Das ist ein Array, in dem wir nur Nullen und Einsen speichern. Haben wir eine n-Bit-Hashfunktion, brauchen wir einen Vektor der Größe 2n, um im Vektor alle möglichen Ausgaben der Hashfunktion adressieren zu können. Die Idee ist, dass der Vektor am Anfang lauter Nullen enthält. Gibt uns die Hashfunktion für die Eingabe "123" dann die Zahl 47 zurück, schreiben wir einfach an den Index 47 des Vektors eine Eins. Damit markieren wir, dass wir den Hashwert 47 schon gesehen haben.

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

// Gibt aus: { id: "123" } { id: "456" } { id: "789" }

Mit dem Code % numberOfValues haben wir MurmurHash nur so abgeschnitten, dass daraus eine n-Bit-Hashfunktion wird, mehr nicht. Und das ist ein Bloomfilter. Wenn auch eine ziemlich entartete Version. Das Problem dieses Ansatzes sind natürlich Kollisionen, die zwangsläufig auftreten. Verschiedene Eingabewerte können denselben Ausgabe-Hashwert haben. Um die Wahrscheinlichkeit einer Kollision zu verringern, verwenden wir deshalb nicht nur eine Hashfunktion, sondern mehrere. Mehrere Hashfunktionen können wir zum Beispiel erzeugen, indem wir an den Eingabewert ein Salt anhängen. Eine einfache Funktion, die verschiedene n-Bit-Hashfunktionen erzeugt, könnte so aussehen:

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

Die Klasse, die den Bloomfilter darstellt, können wir so schreiben:

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;
}
  • Die Methode add fügt dem Bloomfilter ein Element hinzu: Sie berechnet den Hashwert mit allen Hashfunktionen und speichert am entsprechenden Index true.
  • Die Methode contains stellt dann fest, ob das gegebene Element im Bloomfilter enthalten ist.

Den Bloomfilter können wir ganz einfach benutzen:

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

// Gibt aus: { id: "123" } { id: "456" } { id: "789" }

Und das ist die ganze Magie des grundlegenden Bloomfilters. Er hat diese grundlegenden Eigenschaften:

  • Wenn die Methode contains antwortet, dass das gegebene Element nicht im Bloomfilter ist, bedeutet das, dass du es tatsächlich nie eingefügt hast.
  • Wenn die Methode antwortet, dass das gegebene Element im Bloomfilter enthalten ist, muss das nicht zwangsläufig bedeuten, dass du es dort wirklich gespeichert hast – es kann nämlich eine Kollision der Hashfunktionen aufgetreten sein.
  • Allgemein gilt: Willst du die Wahrscheinlichkeit einer falschen Antwort senken, erhöhe die Anzahl der Hashfunktionen oder erhöhe ihre Größe (gemeint ist die Größe des Ausgabewerts).
  • Je mehr Hashfunktionen du verwendest, desto langsamer wird der Bloomfilter.
  • Je größer die Hashfunktionen sind, die du verwendest, desto mehr Platz belegt der Bloomfilter.
  • Wenn du ein Element einmal in den Bloomfilter eingefügt hast, kann es nicht mehr entfernt werden.