Bloom-Filter anhand von Beispielen verstehen

 (llimllib.github.io)
2 Punkte von GN⁺ 2025-07-01 | 1 Kommentare | Auf WhatsApp teilen
  • Bloom-Filter sind Datenstrukturen, mit denen sich bei großen Mengen die Zugehörigkeit speichersparend und schnell vorprüfen lässt; sie unterscheiden nur zwischen „definitiv nicht enthalten“ und „könnte enthalten sein“
  • Der Kern besteht aus einem Bitvektor und mehreren Hash-Funktionen; beim Einfügen werden die Bits an den durch die Hash-Ergebnisse angegebenen Positionen auf 1 gesetzt
  • Bei einer Abfrage kann ein Element ausgeschlossen werden, wenn auch nur eine dieser Positionen 0 ist; selbst wenn alle 1 sind, bleibt jedoch die Möglichkeit eines False Positive bestehen
  • Die Hash-Funktionen sollten unabhängig sein, eine möglichst gleichmäßige Verteilung liefern und schnell sein; in einem Fall führte der Wechsel von md5 zu murmur zu einer Leistungssteigerung von etwa 800 %
  • Die Genauigkeit und die Kosten des Filters hängen vom Gleichgewicht zwischen der erwarteten Elementanzahl n, der Bitzahl m und der Anzahl der Hashes k ab; Einfügen und Abfragen liegen beide bei O(k)

Funktionsweise von Bloom-Filtern

  • Ein Bloom-Filter ist eine probabilistische Datenstruktur, mit der sich schnell und speichereffizient prüfen lässt, ob ein Element zu einer Menge gehört
  • Das Ergebnis ist auf zwei Fälle beschränkt
    • Das Element ist definitiv nicht in der Menge enthalten
    • Das Element könnte in der Menge enthalten sein
  • Die interne Struktur ist ein Bitvektor; beim Hinzufügen eines Elements wird die Eingabe durch mehrere Hash-Funktionen geleitet
  • Sind die durch die Hash-Werte angegebenen Bit-Indizes auf 1 gesetzt, ist das Einfügen abgeschlossen
  • Im Beispiel werden Fnv und Murmur als einfache Hash-Funktionen verwendet

Prüfung der Zugehörigkeit und False Positives

  • Auch bei der Abfrage werden dieselben Hash-Funktionen wie beim Einfügen verwendet
  • Ist auch nur eines der durch die Hash-Werte angegebenen Bits 0, dann ist das Element definitiv nicht in der Menge enthalten
  • Sind alle zugehörigen Bits 1, dann könnte das Element enthalten sein
    • Dieselben Bits könnten bereits durch ein anderes Element oder durch die Kombination mehrerer anderer Elemente gesetzt worden sein
  • Wegen dieser Kollisionen besteht bei Bloom-Filtern die Möglichkeit von False Positives

Kriterien für die Wahl der Hash-Funktionen

  • Die Hash-Funktionen eines Bloom-Filters sollten unabhängig sein, eine möglichst gleichmäßige Verteilung liefern und so schnell wie möglich sein
  • Kryptografische Hashes wie sha1 sind weit verbreitet, aber für Bloom-Filter nicht immer die beste Wahl
  • Beispiele für schnelle und einfache Hashes sind:
  • Es gibt einen Fall, in dem der Austausch von md5 durch murmur in einer Bloom-Filter-Implementierung eine Leistungssteigerung von etwa 800 % brachte

In realen Implementierungen verwendete Hashes

  • Verschiedene Implementierungen verwenden für Bloom-Filter unterschiedliche Hash-Funktionen
    • Chromium: verwendet murmur
    • Plan9: verwendet einen einfachen Hash, der in Mitzenmacher 2005 vorgeschlagen wurde
    • Sdroege Bloom filter: verwendet fnv1a
    • Squid: verwendet MD5
    • RedisBloom: verwendet murmur
    • Apache Spark: verwendet murmur
    • influxdb: verwendet xxhash
    • bloomd: die ersten beiden Hashes sind murmur, die nächsten beiden SpookyHash, danach wird eine Kombination aus beiden verwendet
    • fleur, flor, bloom: verwenden fnv
    • Sqlite: hat einen Bloom-Filter für Analyseabfragen hinzugefügt
    • RocksDB: ist konfigurierbar; im Quellcode wird angegeben, dass xxh3 aus der xxhash-Familie am besten abgeschnitten hat
    • ScyllaDB: verwendet murmur

Filtergröße und Anzahl der Hash-Funktionen festlegen

  • Bei Bloom-Filtern lässt sich die False-Positive-Rate anpassen
    • Ein größerer Filter reduziert False Positives
    • Ein kleinerer Filter erhöht False Positives
  • Die False-Positive-Rate lässt sich näherungsweise mit (1-e^-kn/m)^k berechnen
    • n: erwartete Anzahl der einzufügenden Elemente
    • m: Anzahl der Bits im Filter
    • k: Anzahl der Hash-Funktionen
  • Je mehr Hash-Funktionen verwendet werden, desto langsamer werden Abfragen und Einfügevorgänge, und desto schneller füllt sich der Filter
  • Umgekehrt kann eine zu kleine Zahl an Hash-Funktionen zu übermäßig vielen False Positives führen
  • Für gegebene m und n kann das optimale k mit (m/n)ln(2) gewählt werden
  • Die Filtergröße kann in der folgenden Reihenfolge bestimmt werden
    • Einen ungefähren erwarteten Wert für n festlegen
    • Einen Wert für m wählen
    • Den optimalen Wert für k berechnen
    • Mit den gewählten n, m und k die Fehlerrate berechnen
    • Falls die Fehlerrate nicht akzeptabel ist, m ändern und erneut berechnen

Leistung und geeignete Einsatzbedingungen

  • Bei einem Bloom-Filter mit m Bits und k Hash-Funktionen liegen sowohl Einfügen als auch Zugehörigkeitsprüfung bei O(k)
  • Beim Hinzufügen oder Abfragen eines Elements muss das Element nur durch k Hash-Funktionen geleitet werden, um die entsprechenden Bits zu setzen oder zu prüfen
  • Die Platzeffizienz hängt von der tolerierbaren Fehlerrate ab
  • Wenn der Bereich möglicher Elemente stark begrenzt ist, kann ein deterministischer Bitvektor besser geeignet sein
  • Wenn sich die Anzahl der einzufügenden Elemente nicht einmal grob abschätzen lässt, können eine Hash-Tabelle oder ein scalable Bloom filter besser passen

Referenzen und Einsatzbeispiele

Verwandte Beiträge

1 Kommentare

 
GN⁺ 2025-07-01
Kommentare auf Hacker News

  • Dieser Artikel richtet sich genau an Leute wie mich. Den Namen Bloom-Filter hatte ich schon gehört, und jedes Mal, wenn er erwähnt wurde, dachte ich mir, dass ich ihn endlich nachschlagen sollte. Mit diesem Artikel habe ich es nun endlich getan, und er war genau die Einführung, die ich gesucht hatte :)

    • Vor mehr als zehn Jahren habe ich Bloom-Filter kennengelernt, als ich den Auftrag bekam, sie für die Suchfunktion von iBooks zu implementieren
    • Eine wirklich interessante Struktur. Wenn ein Problem auftaucht, für das man einen Bloom-Filter braucht, ist das spannend; leider kommt das je nach Bereich eher selten vor

  • 2009 habe ich an der Uni einen Bloom-Filter mit CUDA gebaut, und mein Betreuer war früher bei Nvidia. Danach habe ich in meiner Karriere allerdings gar keine GPU-Programmierung mehr gemacht
    Hätte ich damals eine andere Entscheidung getroffen, hätte ich vielleicht 100 Millionen Dollar verdienen können

    • Bei mir ähnlich. 2009 habe ich aus Neugier mit CUDA v1 auf einer GeForce 8 eine sehr frühe Form eines GPU-optimierten Bioinformatik-Toolkits gebaut
      Danach bin ich etwas anderes machen gegangen und habe das große Geld verpasst
    • Wenn man bedenkt, dass die Informatik-Idee von 1970 stammt, wirkt das eher unwahrscheinlich. Ideen, die sich auf universellen GPUs ausprobieren ließen, dürften schon alle im Blick gehabt haben
      Vor 10 Jahren habe ich eine hashcash-Implementierung auf der GPU gebaut; heute wäre sie wohl fast wertlos
    • Für mein Undergraduate-Honors-Projekt habe ich einen Machine-Learning-Algorithmus nach CUDA portiert, dann nur mit den Schultern gezuckt und bin zur Embedded-Programmierung gegangen
    • Mit Bitcoin-Käufen hättest du vermutlich noch viel mehr verdienen können

  • Notiz an den Autor: Der interaktive Teil ist wirklich gut. Um den Kern noch deutlicher zu zeigen, wäre es hilfreich, zwei Beispiel-Strings mit Hash-Kollision zu geben, einen davon in das erste Eingabefeld einzutragen und den anderen im zweiten Feld prüfen zu lassen
    So ließe sich zeigen, warum die Antwort immer „könnte in der Menge sein“ lautet und nicht „ist drin“

    • "bloom" und "demonstrators " kollidieren. Auf das Leerzeichen am Ende des zweiten Strings achten
      Beide kollidieren bei fnv: 7, murmur: 12

  • Ich habe einen Trick, den ich mag. Wenn man viele Membership-Checks für eine Menge machen muss, die manchmal klein sein könnte, kann man spekulativ einen 64-Bit-Bloom-Filter mit einer sehr einfachen Hash-Funktion davorhängen
    Das klingt unglaublich dumm, aber die Kosten sind so gering, dass es den Versuch wert ist. Wenn es nicht gut passt, fügt es beim Einfügen und bei Membership-Checks ungefähr 10 ns hinzu; wenn es gut passt, kann es enorme Arbeit einsparen

    • Chromium macht das an mehreren Stellen auch so. Der Artikel verlinkt nur das Beispiel, in dem Safe Browsing murmur verwendet, aber der Renderer Blink nutzt normalerweise rapidhash und verwendet solche Mikrofilter an mehreren Stellen
      Zum Beispiel bei querySelector() in bestimmten Fällen, zum Vorfiltern von Hash-Lookups in CSS-Buckets und zum schnellen Ablehnen von Elementen, wenn für Accessibility nach bestimmten Aria-Attributen gesucht wird. Es ist erstaunlich, dass so winzige 32- oder 64-Bit-Filter funktionieren, aber in der Praxis sind sie oft wirksam. Es gibt auch einige größere Bloom-Filter. Ein paar davon habe ich hinzugefügt

  • Ich habe ChatGPT gebeten, mir einen in Python zu bauen, und es nutzte den Ansatz, den zugrunde liegenden md5-Digest aufzuteilen und wie mehrere Hashes zu verwenden. Für unwichtige Zwecke dürfte das in Ordnung sein

  • Eine weitere Visualisierung von Bloom-Filtern findet man am Ende dieser Seite:
    https://www.chrislaux.com/hashtable.html

  • Ich dachte, ich hätte das schon einmal gesehen, aber tatsächlich war es diese andere Seite: https://bdupras.github.io/filter-tutorial/
    Diese Seite vergleicht Bloom-Filter und Cuckoo-Filter und liefert dadurch noch etwas mehr Informationen

  • Vor Kurzem habe ich mit einem Bloom-Filter eine Funktion zur Vermeidung von Log-Message-Spam implementiert. Der Logger hashte die Nachricht, legte sie in den Filter, und wenn der Eintrag vorhanden war, wurde die Nachricht nicht ausgegeben
    Alle paar Sekunden bin ich über den Filter gegangen und habe alle Bits gelöscht; das passte gut, weil ich mich nicht darum kümmern musste, alle Bits des Filters atomar zu löschen. Wenn während des Eingangs einer Nachricht auch nur einige dieser Bits gelöscht wurden, reichte das, damit sie wieder ins Log geschrieben wurde. Die frühere Implementierung zählte die Anzahl gesehener Nachrichten und sättigte bei N, was dazu führte, dass eine bestimmte wiederholt ausgegebene Nachricht nur noch höchstens mit der Geschwindigkeit sichtbar wurde, mit der der Filter geleert wurde
    Es war ziemlich befriedigend, Bloom-Filter erst nur zu kennen und dann so natürlich einen realen Anwendungsfall zu finden, der eine deutliche Verbesserung brachte

  • Wer weiterlesen möchte: Eli Benderskys Artikel über Bloom-Filter war ebenfalls gut:
    https://eli.thegreenplace.net/2025/bloom-filters/

  • Die Konzepte, die man braucht, um Bloom-Filter, Mengen und Hash-Tabellen zu verstehen, überschneiden sich gefühlt zu etwa 95 %. Eine Menge ist eine Hash-Tabelle für Membership-Checks, bei der nur Schlüssel und nicht Werte interessieren, und ein Bloom-Filter ist eine Menge, die ausnutzt, dass Many-to-one-Hashing den Schlüsselraum durch Kollisionen „komprimiert“
    Im Grunde verwendet man absichtlich eine Hash-Funktion mit vielen Kollisionen. Wenn ein bestimmter Schlüssel jemals gehasht wurde, kommt garantiert ein Treffer heraus, aber es könnte auch ein anderer Schlüssel denselben Hash erzeugt haben. Das ist kein Bug, sondern ein Feature

    • Schön zu sehen, dass ich nicht der Einzige bin, der einen Bloom-Filter als Hash-Tabelle versteht, die nicht die eigentlichen Daten verfolgt, sondern nur die Buckets, in denen Daten liegen
    • Das Entscheidende, was in dieser Erklärung fehlt, ist, dass Bloom-Filter mehrere Hash-Funktionen verwenden, um Kollisionen zu reduzieren. Wenn es zum Beispiel drei Hashes gibt, müssen alle drei passen, damit ein Schlüssel als in der Menge enthalten gilt
      So sinkt die Wahrscheinlichkeit falsch-positiver Kollisionen, während die Garantie erhalten bleibt, dass es keine falsch-negativen Ergebnisse gibt
    • Wenn man Bloom-Filter richtig verstanden hat, ist man auch schon fast dabei, zufällige Projektionen und einige Implementierungen von Locality-Sensitive Hashing zu verstehen