Bloomfilter
Ein Bloom-Filter 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 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 den zu speichernden Wert mittels der k Hashfunktionen k Hashwerte ermittelt, wobei jeder der ermittelten k Hashwerte eine Position im Bit-Array darstellt. 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[1] von Broder und Mitzenmacher. Zu diesen Erweiterungen zählen beispielsweise Counting Bloomfilter[2], 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[3]), während weitere Varianten Optionen für probabilistische Multiplizitätsabschätzungen von eingefügten Elementen bieten (z. B. Bloomier Filter[4]).
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[5].
Anwendungen
- Der Proxyserver Squid verwendet Bloomfilter zum Abgleichen von Cache-Einträgen.[6]
- 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.[7]
- 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 (PDF).
- Michael Mitzenmacher, Eli Upfal: Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge University Press, 2005, ISBN 0-521-83540-2 (Google Books [abgerufen am 21. Mai 2013]).
Einzelnachweise
- Andrei Broder, Michael Mitzenmacher: Network applications of bloom filters: A survey. In: Internet Mathematics. 2002, S. 636–646 (psu.edu [abgerufen am 21. Mai 2013]).
- Michael Mitzenmacher: Compressed bloom filters. In: IEEE/ACM Transactions on Networking. 2002, S. 604–612, doi:10.1109/TNET.2002.803864.
- Fan Deng, Davood Rafiei: Approximately detecting duplicates for streaming data using stable bloom filters. In: Proceedings of the 2006 ACM SIGMOD international conference on Management of data. 2006, S. 25–36, doi:10.1145/1142473.1142477.
- Bernard Chazelle, Joe Kilian, Ronitt Rubinfeld, Ayellet Tal: The Bloomier filter: an efficient data structure for static support lookup tables. In: Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms. 2004, S. 30–39 (acm.org [abgerufen am 21. Mai 2013]).
- Mustafa Canim, George A. Mihaila, Bishwaranjan Bhattacharjee: Buffered Bloom Filters on Solid State Storage. In: First International Workshop on Accelerating Data Management Systems Using Modern Processor and Storage Architectures (ADMS). 2010 (vldb.org [PDF; abgerufen am 23. April 2019]).
- SquidFaq/CacheDigests. Abgerufen am 21. Mai 2013.
- Alex Yakunin: Nice Bloom filter application. (Nicht mehr online verfügbar.) Archiviert vom Original am 27. Oktober 2010; abgerufen am 21. Mai 2013 (über die Anwendung von Bloomfiltern für Safe Browsing in Google Chrome).
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