✖

Bloom-Filter: Gibt es ein Element in der Menge?

Ein Bloom-Filter ist eine probabilistische Struktur, mit der wir mit einer gewissen Wahrscheinlichkeit feststellen können, ob ein Element x in der Menge M enthalten ist.

In unserem System müssen wir zum Beispiel messen, wie oft Benutzer auf ein Werbebanner geklickt haben. Nach jedem Klick erhalten wir eine HTTP-GET-Anfrage, die uns mitteilt, dass Benutzer XYZ auf Anzeige 123 geklickt hat. Gelegentlich klickt ein Benutzer versehentlich doppelt und wir erhalten zwei Anfragen. Wir möchten diese Anfragen herausfiltern und sie als einen Klick in der Datenbank aufzeichnen.

Daher benötigen wir eine Anwendung, die den Feed mit den Klickmeldungen liest und Doppelklicks herausfiltert. Wie würden wir das machen? Jede dieser Meldungen hat eine ID, so dass wir nicht die gesamte Meldung vergleichen müssen, sondern nur feststellen müssen, ob wir jemals eine Meldung mit derselben ID verarbeitet haben. Ein einfacher JavaScript-Code, der Duplikate aus dem Nachrichtenstrom (hier der Einfachheit halber das Array) entfernen würde, 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);
    }
});

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

Diese Lösung reicht aus, bis uns der Speicher ausgeht - und das wird irgendwann der Fall sein, denn die Menge der verarbeiteten IDs wird mit der Zeit immer größer. Wir können natürlich etwas für den Verfall der Daten programmieren - wir können immer Nachrichten löschen, die älter als eine Stunde sind oder ähnliches.

Schlimmer ist es, wenn selbst das nicht ausreicht. Was ist, wenn wir mindestens die Daten eines Tages im processedIds-Set haben müssen und wir, sagen wir, zehntausend Nachrichten pro Sekunde durchgehen? Im schlimmsten Fall müssen wir bis zu 864.000.000 Ids speichern. Wenn wir uuid v4 verwenden, hat jede ID eine Länge von 36, was bedeutet, dass wir mindestens 32 GB pro Tag speichern müssen. Das ist ein bisschen viel. Könnte der Speicherbedarf nicht verringert werden?

Bloom-Filter

Anstatt die gesamte ID zu speichern, können wir auch nur den Hash der ID speichern. Wir können den klassischen Murmurhash verwenden, der für jede Zeichenkette eine 32-Bit-Ganzzahl zurückgibt und zudem eine gute Verteilung aufweist:

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

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

Als Nächstes wenden wir den Bitvektortrick an. Dies ist ein Array, in dem wir nur Nullen und Einsen speichern. Wenn wir eine n-Bit-Hash-Funktion haben, brauchen wir einen Vektor der Größe 2n, um alle möglichen Ausgaben der Hash-Funktion im Vektor adressieren zu können. Die Idee ist, dass der Vektor zunächst alle Nullen enthält. Wenn dann die Hash-Funktion für die Eingabe "123" die Zahl 47 zurückgibt , setzen wir einfach eine Eins in den Vektor bei Index 47. Dies zeigt an, dass wir bereits einen Hashwert von 47 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);
    }
});

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

Mit dem Code %numberOfValues haben wir den Murmurhash nur so getrimmt, dass er eine n-Bit-Hash-Funktion ist, mehr nicht. Und das ist der Bloom-Filter. Wenn auch eine sehr entartete Version. Das Problem bei diesem Ansatz sind natürlich die Kollisionen, die zwangsläufig auftreten. Verschiedene Eingabewerte können denselben Ausgabehash haben. Um die Wahrscheinlichkeit von Kollisionen zu verringern, verwenden wir also nicht nur eine Hash-Funktion, sondern mehrere. Wir können zum Beispiel mehrere Hash-Funktionen erstellen, indem wir dem Eingabewert ein Salz hinzufügen. Eine einfache Funktion, die verschiedene n-Bit-Hash-Funktionen erzeugt, könnte wie folgt 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

Wir können eine Klasse schreiben, die einen Bloom-Filter wie folgt darstellt:

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]<4>;
        this.bitVector[checksum] = true;
    }
}

BloomFilter.prototype.contains = function(item) {
    var checksum;
    for (var i = 0; i < this.hashFunctions.length; i++) {
        checksum = this.hashFunctions[i]<5>;
        if (!this.bitVector[checksum]) {
            return false;
        }
    }
    return true;
}
  • Die add-Methode fügt dem Bloom-Filter ein Element hinzu: Sie berechnet den Hash-Wert aller Hash-Funktionen und speichert true am entsprechenden Index.
  • Die contains-Methode findet dann heraus, ob das Element im Bloom-Filter enthalten ist.

Wir können den Bloom-Filter ganz einfach verwenden:

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

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

Und das ist die ganze Magie des grundlegenden Bloom-Filters. Er hat diese grundlegenden Eigenschaften:

  • Wenn die Methode contains antwortet, dass das Element nicht im Bloom-Filter enthalten ist, bedeutet das, dass Sie das Element nie wirklich in den Bloom-Filter aufgenommen haben.
  • Wenn die Methode antwortet, dass das Element im Bloom-Filter vorhanden ist, bedeutet das nicht unbedingt, dass Sie das Element tatsächlich in den Bloom-Filter aufgenommen haben - es könnte eine Hash-Kollision gegeben haben.
  • Wenn Sie die Wahrscheinlichkeit einer falschen Antwort verringern wollen, sollten Sie die Anzahl der Hash-Funktionen oder deren Größe (d. h. die Größe des Ausgabewerts) erhöhen.
  • Je mehr Hash-Funktionen Sie verwenden, desto langsamer wird der Bloom-Filter.
  • Je mehr Hash-Funktionen Sie verwenden, desto mehr Platz nimmt der Bloom-Filter in Anspruch.
  • Sobald ein Element in den Bloom-Filter eingefügt wurde, kann es nicht mehr entfernt werden.