Begriff
Bloom Filter
Warum wichtig?
Dieser Begriff ist ein Knoten im SengakujiWorks-Wissensnetz. Nutze Level 0 für die erste Einordnung, Level 1 für Praxis, Level 2 für technische Struktur und Level 3 für Grenzen, Fallstricke und Expertenkontext.
Du willst prüfen: "Habe ich diese URL schon gecrawlt?" Bei 1 Milliarde URLs brauchst du viel RAM. Ein Bloom Filter ist ein extrem kompakter Weg, Mengen zu speichern. Der Trick: Er speichert nicht die Elemente selbst. Er speichert nur Nullen und Einsen (Bits). Wenn du "google.com" prüfst, sagt er:
- "Definitiv NEIN." (Die URL war noch nie da. Zu 100% sicher).
- "Vielleicht JA." (Die URL war wahrscheinlich da. Zu 99% sicher). Er hat False Positives, aber keine False Negatives. Dafür braucht er 10x weniger Platz als ein Array.
Merksatz: Eine probabilistische Datenstruktur, die verwendet wird, um zu testen, ob ein Element Teil einer Menge ist; sie ist speichereffizient, kann aber falsch-positive Ergebnisse liefern (sagt "Ja", obwohl "Nein" richtig wäre).
In Datenbanken (Cassandra, HBase). Um Disk I/O zu sparen. Bevor die DB auf der Festplatte (SSTable) nachschaut, fragt sie den Bloom Filter im RAM. Filter sagt "Nein" -> DB weiß sofort: "Der Key existiert nicht". (Spart Lesen). Filter sagt "Vielleicht" -> DB muss lesen. Auch in Browsern (Phishing Protection): "Ist diese URL in der Blacklist?"
1. Hash-Funktionen
Man braucht $k$ unabhängige Hash-Funktionen. Für jedes Element setzen wir $k$ Bits auf 1. Beim Prüfen schauen wir, ob diese $k$ Bits alle 1 sind. Wenn auch nur ein Bit 0 ist -> Element war nie da. Wenn alle 1 sind -> Könnte auch Zufall sein (Kollision von anderen Elementen).
2. Dimensionierung
Die Wahrscheinlichkeit für False Positives $p$ hängt von der Größe $m$ (Bits) und der Anzahl $n$ (Elemente) ab. Formel: $m = - \frac{n \ln p}{(\ln 2)^2}$. Für 1% Fehlerwahrscheinlichkeit braucht man ca. 9.6 Bits pro Element. Das ist unschlagbar wenig.
1. Hash-Collision Wahrscheinlichkeiten (Math in Code)
Wenn Engineers Bloom-Filter in Production bauen, raten sie Arraygrößen und Hash-Funktions-Mengen nicht. Die Mathematik gibt exakt an, wie man das $k$ (Anzahl perfekter Hashfunktionen) für eine minimale Fehlerwahrscheinlichkeit (False Positive Probability, $\epsilon$) optimiert: $k = \frac{m}{n} \ln 2$. Frameworks wie Guava (Java) nutzen keine kryptografischen Heavyweights wie SHA-256 (viel zu lahm für $k=7$). Sie greifen konsequent auf ultra-schnelle Non-Cryptographic Functions wie MurmurHash3 (oder CityHash/xxHash) zurück. Es wird oft nicht wirklich 7 mal gehascht. Durch den "Kirsch-Mitzenmacher-Trick" genügen zwei 64-bit Murmur-Hash Aufrufe, um durch Linearkombination $h_i = (h_1 + i \cdot h_2) \pmod{m}$ beliebig viele unabhängige Hash-Spuren vorzutäuschen, ohne CPU Zyklen auszubluten.
2. Cuckoo Filter und Quotient Filter als Ablösung
Weil das "Nicht-Löschbare"-Problem Entwickler oft verrückt macht, drängen zwei revolutionäre Paradigmen an die Front: Der Cuckoo Filter: Er basiert auf Cuckoo Hashing. Er speichert Fingerprints dynamisch und "schubst" bei Kollisionen im Array veraltete Einträge auf Backup-Plätze (wie der Kuckuck, der Eier aus dem Fremdnest kippt). Du kannst Einträge logisch löschen. In Benchmarks erreichen Cuckoo-Filter bei 95% Raum-Fülle weitaus tiefere Fehlerraten und schnellere Cache-Miss Iterationen. Für LSM Trees gibt es zudem Quotient Filter, die sogar Pointerspeicher in extrem cache-effizienten Blöcken minimieren und bei Range-Queries noch skalieren können.
3. L1/L2 Latenz-Misses als Bottleneck
Während die Kapazitätsseite von $O(1)$ perfekt glänzt, schlägt die Architektur-Keule zu: Random Memory Accesses. Hat ein Element $k=8$, muss man bitweise auf 8 wild verteilte Speicherblöcke im DRAM zugreifen ("Pointer Chasing"). Ist der Filter 2 Gigabyte groß (wie bei RocksDB in Facebook), liegen die Bits in unterschiedlichen Cache-Miss Seiten. Die Zeit für einen Access degeneriert dramatisch. Der neuste Defense-Mechanismus heißt hier Blocked Bloom Filters. Man zwingt den Algorithmus, alle $k$ Bits ausschließlich innerhalb einer 64-Byte Hardware-Cache-Linie zu verwalten. Zwar steigt die rechnerische False-Positive-Fehlerquote leicht an, aber der Durchsatz vervielfacht sich durch glatten L1-Cache Erfolg immens.
Quick-Check
Löschen?
Geht nicht! Wenn du ein Bit auf 0 setzt, löschst du vielleicht auch andere Elemente, die zufällig dasselbe Bit nutzen. (Es gibt aber "Counting Bloom Filters", die das können, aber mehr Platz brauchen).Cuckoo Filter?
Die moderne Alternative. Braucht ähnlich wenig Platz, unterstützt aber Löschen und ist oft schneller (wegen CPU-Cache-Lokalität).Name?
Burton Howard Bloom (1970). Damals für Rechtschreibprüfung (Spell Checker) erfunden.