Bloom-Filter anhand eines Beispiels verstehen

• Bloom-Filter sind eine probabilistische Datenstruktur, mit der sich speichereffizient und schnell prüfen lässt, ob ein Element in einer Menge enthalten ist
• Sie können nur angeben, ob ein Element sicher nicht vorhanden ist oder möglicherweise vorhanden sein könnte, wobei eine Wahrscheinlichkeit für False Positives besteht
• Die Grundstruktur verwendet einen Bit-Vektor und mehrere Hash-Funktionen, um die zu einem Element gehörenden Bits auf 1 zu setzen
• Fehlerrate und Performance werden durch die Größe des Filters und die Anzahl der Hash-Funktionen bestimmt und können je nach Einsatzzweck angepasst werden
• Vorgestellt werden außerdem empfohlene Hash-Funktionen, Methoden für optimale Einstellungen, Platzeffizienz und praktische Anwendungsbeispiele

---

Was ist ein Bloom-Filter?

• Ein Bloom-Filter ist eine Datenstruktur, mit der sich schnell und speichereffizient feststellen lässt, ob ein bestimmtes Element in einer Menge vorhanden ist
• Um diese Effizienz zu erreichen, ist der Bloom-Filter eine probabilistische Datenstruktur; das Prüfergebnis fällt daher in die Kategorien „sicher nicht in der Menge“ oder „möglicherweise in der Menge vorhanden“
• Die zentrale Struktur eines Bloom-Filters ist ein Bit-Vektor
• Beim Hinzufügen eines Elements wird dieses mehrfach gehasht, und die Bits an den entsprechenden Indizes werden auf 1 gesetzt
• Wenn die Bits an den von den jeweiligen Hash-Funktionen gelieferten Indizes alle 1 sind, wird das Ergebnis als „möglicherweise vorhanden“ gewertet, andernfalls als „sicher nicht vorhanden“

Beispiel für die Funktionsweise

• Mehrere Hash-Funktionen (z. B. Fnv, Murmur) bilden ein Element auf mehrere Bit-Indizes ab
• Beim Hinzufügen eines Elements werden die Bits an den berechneten Indizes auf 1 gesetzt
• Wenn bei der Prüfung eines bestimmten Elements alle mit denselben Hash-Funktionen und auf dieselbe Weise berechneten Indizes 1 sind, gilt das Element als „möglicherweise vorhanden“
• Falls auch nur eines dieser Bits 0 ist, lässt sich sicher feststellen, dass es nicht in der Menge ist
• Dadurch entsteht die Möglichkeit von False Positives

Fortgeschrittene Themen

Hinweis: Der Autor hat tatsächlich keine Erfahrung damit, Bloom-Filter in großen produktiven Services eingesetzt zu haben

Auswahl der Hash-Funktionen

• Empfohlen werden Hash-Funktionen, die unabhängig sind und eine gleichmäßige Verteilung haben
• Kryptografische Hash-Funktionen (sha1 usw.) sind langsam und daher ungeeignet
• Beispiele für schnelle und einfache Hash-Funktionen sind: Murmur, xxHash, Fnv, HashMix usw.
• In einem Praxisfall führte der Wechsel von md5 zu murmur zu einer Geschwindigkeitssteigerung von über 800 %

Bestimmung der Größe eines Bloom-Filters

• Je größer die Filtergröße (m) ist, desto geringer ist die False-Positive-Rate
• Die False-Positive-Rate lässt sich in der Regel mit (1-e^(-kn/m))^k näherungsweise berechnen
• Die erwartete Anzahl von Elementen (n), die Filtergröße (m) und die Anzahl der Hash-Funktionen (k) müssen passend gewählt werden

Wie viele Hash-Funktionen?

• Je mehr Hash-Funktionen verwendet werden, desto langsamer wird der Filter und desto schneller füllt er sich
• Bei zu wenigen steigt die False-Positive-Rate
• Das ideale k wird mit (m/n)ln(2) berechnet
• Beim Entwurf geht man typischerweise in folgenden Schritten vor:
  • die erwartete Elementanzahl n schätzen
  • die Bit-Anzahl m festlegen
  • das optimale k berechnen
  • prüfen, ob die gewünschte Fehlerrate erreicht wird; falls nicht, m anpassen

Performance und Platzeffizienz

• In einem Bloom-Filter haben Element hinzufügen / Existenz prüfen eine Zeitkomplexität von O(k)
• Die Platzeffizienz hängt vom tolerierten Fehlerratenbereich und vom Umfang der Elemente ab
• Wenn sich der Umfang der Elemente nicht wenigstens grob abschätzen lässt, sind eine Hash-Tabelle oder ein skalierbarer Bloom-Filter möglicherweise die bessere Wahl

Anwendungsfälle

• Für ausführlichere Beispiele siehe Wikipedia
• C. Titus Brown stellt Anwendungsbeispiele aus der Bioinformatik für Bloom-Filter vor

Referenzmaterial

• Broder, Mitzenmacher : Network Applications of Bloom Filters: A Survey — Überblickspapier zu Bloom-Filtern
• Wikipedia – Bloom Filter
• Kirsch, Mitzenmacher: Less Hashing, Same Performance
• Almeida et al.: Scalable Bloom Filters

[GN⁺]

Hacker-News-Kommentare

• Dieser Artikel ist genau das Richtige für Leute wie mich. Ich hatte den Namen schon mal gehört, wollte ihn jedes Mal nachschlagen und habe es dann immer wieder aufgeschoben. Diesmal habe ich den Artikel endlich gelesen, und er fühlte sich genau wie die Einführung an, die ich gesucht hatte.
  • Ich habe Bloom-Filter zum ersten Mal kennengelernt, als ich die Suchfunktion in iBooks implementiert habe. Das ist inzwischen schon über 10 Jahre her.
  • Bloom-Filter machen wirklich Spaß. Wenn man ein Problem löst und es sich herausstellt, dass man einen Bloom-Filter braucht, ist das richtig aufregend, aber je nach Domäne kommt so etwas leider nicht oft vor.
• Ein Vorschlag an den Autor. Der interaktive Teil ist sehr gelungen. Um die Eigenschaften eines Bloom-Filters noch besser verständlich zu machen, wäre es gut, ein Beispiel zu zeigen, bei dem zwei Strings einen Hash-Kollision verursachen, dann einen davon eingeben zu lassen und den anderen in das zweite Eingabefeld. So lässt sich leicht nachvollziehen, warum dieses typische Ergebnis entsteht: „nicht sicher, aber vielleicht im Set“.
  • Zum Beispiel kollidieren "bloom" und "demonstrators " (mit Leerzeichen am Ende) bei fnv: 7, murmur: 12.
• Ich habe 2009 im Studium einmal einen Bloom-Filter mit CUDA implementiert. Mein Betreuer war früher bei Nvidia. In meiner Laufbahn bin ich dann allerdings in eine völlig andere Richtung gegangen, die mit GPU-Programmierung nichts zu tun hatte. Manchmal denke ich, mit einer anderen Entscheidung hätte ich vielleicht 100 Millionen Dollar verdienen können.
  • Da die Idee aus der Informatik schon aus dem Jahr 1970 stammt, wäre das wohl ohnehin nicht möglich gewesen. Zu GPGPU schien es schon genug erforschte Ideen zu geben. Ich selbst habe vor 10 Jahren einmal Hashcash auf der GPU implementiert, aber aus heutiger Sicht ist das praktisch nichts wert.
  • Ich habe für mein Abschlussprojekt einen Machine-Learning-Algorithmus nach CUDA portiert und dann gedacht, das sei keine große Sache, woraufhin ich in Richtung Embedded-Programmierung gewechselt bin.
  • Ähnliche Erfahrung hier. 2009 habe ich mit einer GeForce 8 und CUDA v1(!) vermutlich als Erster ein GPU-optimiertes Bioinformatik-Toolkit gebaut. Das war reine Neugier, danach bin ich komplett einen anderen Weg gegangen und habe die Chance auf viel Geld verpasst.
  • Der scherzhafte Einwurf, dass man mit dem Kauf von Bitcoin noch mehr Geld hätte verdienen können.
• Ich habe einen Trick, den ich gern mag. Für kleine Sets, bei denen die Anzahl der Elemente gering sein kann, aber Mitgliedschaftsprüfungen häufig stattfinden, packe ich einen 64-Bit-Bloom-Filter zusammen mit einer sehr einfachen Hash-Funktion dazu. Das wirkt vielleicht albern, aber die Kosten sind so gering, dass man es fast wie eine Wette ausprobieren kann. Wenn es nichts bringt, kostet es bei Membership-Checks oder Inserts nur etwa 10 ns extra, aber wenn es passt, spart es enorm viel Arbeit.
  • Chromium verwendet solche Tricks auch an vielen Stellen. Im Artikel wird nur Safe Browsing erwähnt, aber in der Blink-Schicht werden rapidhash und solche Mikro-Filter aktiv eingesetzt. Beispiele sind querySelector(), Vorfilter für Hash-Lookup in CSS-Buckets und schnelles Verwerfen bei der Suche nach ARIA-Attributen für Accessibility. Kleine 32- oder 64-Bit-Filter funktionieren in der Praxis ebenfalls gut. Auch größere Bloom-Filter werden sinnvoll eingesetzt, und ich habe solche Funktionen selbst hinzugefügt.
• Ich habe kürzlich Bloom-Filter für eine Anti-Spam-Funktion bei Log-Meldungen verwendet. Dabei werden Log-Meldungen gehasht und in den Filter eingefügt; wenn sie bereits im Filter sind, werden sie nicht ausgegeben. Die Bits des Filters werden periodisch komplett zurückgesetzt. Man muss nicht atomar alle Bits auf einmal löschen; selbst wenn während eingehender Meldungen einige Bits gelöscht werden, führt das nur dazu, dass die Logs wieder erscheinen. Früher habe ich für jede Meldung einen separaten Zähler geführt, aber diese Methode war deutlich effizienter. Ich habe Bloom-Filter tatsächlich selbst für diesen Anwendungsfall eingesetzt und war damit sehr zufrieden.
• Als Visualisierungsbeispiel für Bloom-Filter gibt es am Ende dieser Seite gutes Material.
• Ich empfehle auch einen weiteren Einführungsartikel zu Bloom-Filtern von Eli Bendersky. Wer es genauer wissen will, kann hier nachsehen.
• Ich finde, dass sich fast 95 % der Konzepte überschneiden, die man zum Verständnis von Bloom-Filtern, Sets und Hash-Tabellen braucht. Ein Set ist eine Hash-Tabelle, bei der nur die Keys wichtig sind, und ein Bloom-Filter ist ein Set, das die Kollisionseigenschaften des Hashings aktiv ausnutzt. Es werden Hash-Funktionen verwendet, die absichtlich leicht Kollisionen erzeugen. Wenn ein bestimmter Key jemals eingefügt wurde, dann passt die Prüfung auf jeden Fall. Es kann aber auch andere Keys geben, die denselben Hash-Wert erzeugen. Das ist also kein Bug, sondern eine beabsichtigte Eigenschaft.
  • Ich stelle mir Bloom-Filter ebenfalls gern als eine Art Hash-Tabelle vor, bei der die eigentlichen Daten fehlen und nur die Buckets verfolgt werden. Schön zu sehen, dass ich mit dieser Denkweise nicht allein bin.
  • Es wäre gut, noch zu ergänzen, dass Bloom-Filter mehrere Hash-Funktionen verwenden, um Kollisionen zu verringern. Zum Beispiel gilt ein Element erst dann als im Set, wenn alle drei Hash-Funktionen übereinstimmen. Diese Struktur senkt die Wahrscheinlichkeit von False Positives, während False Negatives niemals auftreten.
  • Wenn man Bloom-Filter verstanden hat, versteht man bald auch Random Projections oder manche Implementierungen von Locality Sensitive Hashes.
• Beim Debugging eines Cassandra-Read-Spikes bin ich tief in Bloom-Filter eingetaucht. Es war seltsam, dass selbst für nicht existierende Keys so viele SSTable-Lookups stattfanden. Erst später habe ich verstanden, wozu die Bloom-Filter an jeder SSTable dienen. Die standardmäßige False-Positive-Rate von 0,1 war für unsere Situation zu hoch. Die meisten Fälle waren Cache-Misses, und wegen der False Positives gab es zu viele sinnlose Lookups. Nachdem wir die Rate auf 0,01 gesenkt hatten, stieg der Speicherverbrauch nur leicht, aber unnötige Reads gingen stark zurück, und die p99-Read-Latenz sank um 16 bis 18 %.
• Ich liebe Bloom-Filter wirklich. Wenn ich über Technik spreche, nenne ich immer drei Kernkonzepte, die man kennen sollte: Bloom-Filter, Random Weight Hashing (Rendezvous Hashing, Highest Random Weight Hashing) und Cumulative Flow Diagram. Ich halte diese drei Konzepte für essenziell beim Betrieb komplexer verteilter Systeme.
  • Ich denke, dass auch die Struktur verteilter Hash-Tabellen ein ebenso wichtiges Thema ist, etwa circle, chord, CAN oder kademlia.