Bloom-Filter sind platzsparende, probabilistische Datenstrukturen, die die Frage „Ist ein Element möglicherweise vorhanden?" beantworten. Sie wurden 1970 von Burton Howard Bloom entwickelt und sind aus modernen Datenbanken und Caches nicht mehr wegzudenken.
So funktioniert ein Bloom-Filter
Ein Bloom-Filter besteht aus einem Bitfeld fester Größe (z. B. 1 MBit) und mehreren unabhängigen Hashfunktionen. Beim Einfügen eines Elements werden die Positionen aller Hashwerte im Bitfeld auf 1 gesetzt. Bei der Abfrage wird geprüft, ob alle Hashpositionen gesetzt sind:
- Sind alle Bits gesetzt: Das Element ist möglicherweise vorhanden (False Positive möglich).
- Fehlt mindestens ein Bit: Das Element ist sicher nicht vorhanden.
False Positives sind möglich, aber keine False Negatives: Ein Bloom-Filter sagt nie fälschlich „nicht vorhanden". Die Fehlerrate lässt sich über die Filtergröße und die Anzahl der Hashfunktionen steuern. Wichtig: Entfernen ist mit dem klassischen Filter nicht möglich, da gelöschte Bits andere Elemente beschädigen würden — dafür gibt es Varianten wie Counting Bloom Filters.
Anwendungen in Datenbanken
- LSM-Trees: Bevor eine teure Suche in einer SSTable-Datei startet, prüft ein Bloom-Filter, ob der Schlüssel überhaupt enthalten sein kann. Fehlzugriffe auf nicht relevante Dateien werden so vermieden — die klassische Anwendung in LSM-Trees bei LevelDB, RocksDB und Apache Cassandra.
- Datenbank-Engines: PostgreSQL und MySQL nutzen Bloom-Indizes für Equality-Abfragen über viele Spalten, bei denen klassische B-Bäume zu groß würden.
- Cache-Systeme: Ein Bloom-Filter vor einem Cache verhindert Cache-Durchbrüche (Cache Penetration): Anfragen zu sicher nicht existierenden Schlüsseln werden abgewiesen, ohne den teuren Datenspeicher zu belasten.
- Netzwerk und Browser: Chromium nutzt Bloom-Filter für die Phishing-Liste, verteilte Systeme für Gossip-Protokolle und Content-Routing.
Bewertung
Der Bloom-Filter ist ein Paradebeispiel für den Trade-off zwischen Speicher und Genauigkeit: Bei typischen Fehlerraten von 1 % benötigt er nur wenige Bits pro Element — deutlich weniger als eine Trie- oder Hash-Index-Struktur. Für reine Existenzfragen ist er damit die günstigste Lösung.
Verwandte Grundlagen: LSM-Tree, Skip-Liste, Hash-Index, Datenbank-Indizes.