Bloomfilter

Ein Bloom-Filter (benannt nach Burton Howard Bloom) ist eine probabilistische Datenstruktur, mit deren Hilfe sehr schnell festgestellt werden kann, welche Daten in einem Datenstrom schon einmal vorgekommen sind und welche erstmals auftreten. Hierzu wird mit einer geeigneten Zahl von Hash-Funktionen ein „Fingerabdruck“ des gelesenen Datensatzes in einer einzeiligen Hashtabelle hinterlassen.

1970 von Burton H. Bloom zur Rechtschreibkontrolle und zur Worttrennung am Zeilenende entwickelt, werden Bloomfilter heute oft bei der Datenbankverwaltung und für das Routing in Netzwerken eingesetzt. Im Gegensatz zu vergleichbaren Algorithmen brauchen Bloom-Filter nur sehr wenig Speicherplatz. Für die Anwendbarkeit sind aber auch die folgenden Eigenheiten von entscheidender Bedeutung: Schlüsselwerte, die einmal in der Hashtabelle erfasst wurden, verbleiben dort. Weiterhin sind falsch positive Ergebnisse möglich, d. h., was der Filter akzeptiert, war mit hoher Wahrscheinlichkeit in den Schlüsselwerten enthalten; hingegen war definitiv nicht enthalten, was er abweist.

Funktionsprinzip

Ein Beispiel eines Bloomfilters für die Menge {x, y, z}. Die farbigen Pfeile geben die Position im Bit-Array des Bloomfilters an. Das Element w ist nicht in der Menge {x, y, z} enthalten, da es Positionen umfasst, deren Wert 0 ist. In diesem Bild sind m=18 und k=3.

Ein Bloomfilter besteht aus einem m-stelligen Bit-Array (welches zu Beginn mit Nullen gefüllt ist) und aus k unterschiedlichen Hashfunktionen mit einem Wertebereich von 0 bis m-1. Hierbei ist vor allem wichtig, dass die von den Hashfunktionen gelieferten Werte gleichverteilt sind, kryptografische Eigenschaften sind nicht gefordert. Aus diesem Grund werden häufig einfache und sehr schnelle Hashverfahren (z. B. MurmurHash oder FNV) eingesetzt.

Anfangs wird dem Bloomfilter sein Vokabular zugewiesen. Hierzu werden für jedes zu speichernde Wort mittels der k Hashfunktionen k Hashwerte ermittelt. Jeder der ermittelten Hashwerte entspricht einer Position im Bit-Array. Jede dieser Positionen wird nun auf 1 gesetzt, wobei es unerheblich ist, ob sich an dieser Position vorher eine 1 oder eine 0 befand.

Soll nun überprüft werden, ob ein beliebiger Wert im Vokabular enthalten ist, werden wiederum dessen k Hashwerte ermittelt. Enthält eine der k Stellen des Bit-Arrays des Filters eine 0, wo der Hash des zu prüfenden Wertes eine 1 hat, so ist sicher, dass der Wert nicht im Filter enthalten ist. Steht an jeder der k Stellen eine 1 im Filter, wo auch der zu prüfende Wert eine 1 hat, ist es sehr wahrscheinlich, dass der Wert im Filter gespeichert wurde. Ein Bloomfilter kann allerdings nie mit absoluter Gewissheit sagen, dass ein bestimmter Wert wirklich gespeichert ist, da bedingt durch Kollisionen ein gewisses Risiko besteht, Werte irrtümlich als zugehörig einzuordnen (Falsch-positive Klassifikation). Dieses Risiko kann jedoch durch geeignete Wahl von k, m, und Kapazität des Filters (also der Höchstzahl zu speichernder Werte) vermindert werden.

Da eine bestimmte Position im Bit-Array durch das Hinzufügen von unterschiedlichen Werten auf 1 gesetzt worden sein kann, ist es bei herkömmlichen Bloomfiltern nicht möglich, einmal hinzugefügte Werte nachträglich zu löschen. Abhilfe schaffen hier so genannte Zählende Bloomfilter.

Hashfunktionen mit konstanter Bildmenge und variabler Quellmenge sind im Allgemeinen nicht bijektiv, weshalb es mit klassischen Bloomfiltern unmöglich ist, die enthaltenen Werte zurückzugewinnen. Es kann nur mit einer gewissen (ggf. hohen) Wahrscheinlichkeit ermittelt werden, ob ein vorgegebenes Wort enthalten ist oder nicht. Dies ist bei vielen Anwendungsgebieten ein großer Nachteil, da z. B. auch die Suche mit Platzhaltern unmöglich wird.

Bloomfilter können von Nutzen sein, wenn sensible Daten gespeichert werden sollen. Beispielsweise kann das Verfahren dazu verwendet werden, um bei einer Fahndung sicher auszuschließen, dass eine gerade überprüfte Person gesucht wird, ohne dabei Personendaten im Klartext vorhalten zu müssen.

Beispiel

Angenommen, der Filter hat eine Länge von 10 Bit (m=10) und besitzt 3 Hashfunktionen (k=3). Das Vokabular bestehe aus den Wörtern „der“, „die“ und „das“.

Zunächst ist der Filter leer:

0 0 0 0 0  0 0 0 0 0

Nun werden die Wörter nacheinander zum Filter hinzugefügt. Dazu werden für jedes der Wörter die Ergebnisse der 3 Hashfunktionen ermittelt.

„der“

Angenommen, die Hashfunktionen liefern für das Wort „der“ die Werte 8, 2 und 4. Es werden also die Positionen 8, 2 und 4 im Array auf 1 gesetzt. Das Array sieht jetzt wie folgt aus:

0 1 0 1 0  0 0 1 0 0

„die“

Angenommen, die Hashfunktionen liefern für das Wort „die“ die Werte 7, 4 und 1. Es werden also die Positionen 7, 4 und 1 im Array auf 1 gesetzt. Das Array sieht jetzt wie folgt aus:

1 1 0 1 0  0 1 1 0 0

„das“

Angenommen, die Hashfunktionen liefern für das Wort „das“ die Werte 9, 2 und 8. Es werden die Positionen 9, 2 und 8 im Array auf 1 gesetzt, womit das Array wie folgt aussieht:

1 1 0 1 0  0 1 1 1 0

Es soll nun die Existenz verschiedener Wörter im Filter überprüft werden.

„wer“

Für das Wort „wer“ wird angenommen, dass sich bei der Berechnung der Hashfunktionen die Werte 10, 1 und 3 ergeben. Die Positionen 10 und 3 im Array enthalten eine 0, somit ist das Wort nicht im Filter enthalten, was korrekt ist.

„das“

Da die Hashfunktion für gleiche Eingaben das gleiche Ergebnis liefert, ergeben sich für das Wort „das“ die gleichen Werte wie zuvor beim Einfügen, nämlich 9, 2 und 8. Alle diese Positionen sind im Array auf 1 gesetzt, das Wort könnte also im Filter gespeichert sein, was auch der Fall ist.

„sie“

Für das Wort „sie“ wird angenommen, dass sich bei der Berechnung der Hashfunktionen die Werte 9, 1, 4 ergeben. Da alle diese Positionen im Array auf 1 gesetzt sind, könnte das Wort im Filter gespeichert sein. Da das Wort „sie“ aber oben nicht dem Filter hinzugefügt wurde, handelt es sich um ein falsch positives Ergebnis.

Es sollte bedacht werden, dass dies ein bewusst konstruiertes Extrembeispiel darstellt, welches noch keine Schlüsse auf die Qualität des Verfahrens zulässt.

Varianten

In der wissenschaftlichen Literatur wurden zahlreiche Varianten und Erweiterungen von Bloomfiltern vorgeschlagen. Einen guten Überblick bietet der Artikel Network applications of bloom filters: A survey von Broder und Mitzenmacher. Zu diesen Erweiterungen zählen beispielsweise Counting Bloomfilter, die auf Kosten eines höheren Platzbedarfs das Entfernen von Elementen erlauben. Andere Bloomfilter-Varianten versuchen die Vorteile des Bloomfilters auf Stream-Daten zu erweitern (z. B. Stable Bloomfilter), während weitere Varianten Optionen für probabilistische Multiplizitätsabschätzungen von eingefügten Elementen bieten (z. B. Bloomier Filter).

Im Bereich der Datenbanken werden auch Buffered Bloom Filter verwendet, um insbesondere bei Solid State Discs (SSD) häufig zugegriffene Speicherstellen ermitteln zu können.

Anwendungen

• Der Proxyserver Squid verwendet Bloomfilter zum Abgleichen von Cache-Einträgen.
• Die NoSQL-Datenbanken Bigtable, Apache HBase und Apache Cassandra verwenden Bloomfilter zur Vermeidung von teuren Festplattenzugriffen bei Abfragen auf nicht-existierende Schlüsselwerte.
• Der Webbrowser Google Chrome pflegt einen Bloomfilter mit den Signaturen gefährlicher Webseiten und überprüft bei Eingabe einer URL, ob diese in diesem Filter enthalten ist.
• Die Kryptowährung Bitcoin nutzt Bloomfilter zur Verifikation von Transaktionen in lightweight Clients (SPV)

Literatur

• Burton H. Bloom: Space/Time Trade-offs in Hash Coding with Allowable Errors. In: Communications of the ACM. Band 13, Nr. 7, Juli 1970, ISSN 0001-0782, S. 422–426 (uta.edu [PDF]). 
• Michael Mitzenmacher, Eli Upfal: Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge University Press, 2005, ISBN 0-521-83540-2 (eingeschränkte Vorschau in der Google-Buchsuche). 

Weblinks

• Orestes Bloomfilter – Open-Source Java-Implementierung von Bloomfiltern und Counting Bloomfiltern mit umfangreichen Verteilungs-, Persisitierungs- und Hashingoptionen.
• Libhashish – Bloomfilter-Bibliothek für C und C++
• A Garden Variety of Bloom filters – Umfassende, englischsprachliche Erklärung verschiedener Bloomfilter-Varianten
• Tabelle mit False-Positive Rates für verschiedene Konfigurationen