Bloom-Filter: probabilistische Mengenzugehörigkeit ohne falsch-negative Ergebnisse

Worum es geht

Ein Bloom-Filter ist ein Bit-Array aus m Bits und k Hashfunktionen. Das Einfügen eines Elements setzt die k Bits, die seine Hashes auswählen; eine Abfrage prüft sie. Ist auch nur ein Bit nicht gesetzt, wurde das Element nie eingefügt; sind alle gesetzt, wurde es entweder eingefügt, oder die Bits wurden von anderen Elementen gesetzt — ein falsch-positives Ergebnis. Die PostgreSQL-Dokumentation zu ihrem bloom-Index beschreibt die Struktur als speichereffizient und anfällig für falsch-positive Meldungen, weshalb jeder Indextreffer gegen die tatsächliche Zeile nachgeprüft werden muss. Die Redis-Dokumentation stellt einen Filter bereit, der mit einer gewünschten Falsch-Positiv-Rate und einer erwarteten Kapazität erzeugt wird. Der einfache Filter kann nicht löschen: Das Zurücksetzen eines Bits könnte den Nachweis eines anderen Elements auslöschen. Für diesen Bedarf gibt es Counting Bloom Filters und Cuckoo-Filter.

Warum es wichtig ist

Der Filter passt in den Speicher, wo die vollständige Menge das nicht tut, und beantwortet „nein“ günstig, was einen Festplattenzugriff, einen Netzwerk-Roundtrip oder eine Datenbankabfrage für sicher nicht existierende Schlüssel spart. Storage-Engines verwenden einen je Datendatei, um Dateien zu überspringen, Crawler verwenden einen für „diese URL schon gesehen“, Caches verwenden einen, um Backend-Lookups für unbekannte Schlüssel zu vermeiden.

So wird es angewendet

• Den Filter anhand der erwarteten Elementanzahl und der angestrebten Falsch-Positiv-Rate bemessen; die Rate steigt, wenn der Filter über seine Auslegungskapazität hinaus gefüllt wird, deshalb für das Maximum planen oder eine skalierbare Variante verwenden.
• Jedes positive Ergebnis als „im echten Speicher prüfen“ behandeln; die Verifizierung nur dort überspringen, wo ein falsch-positives Ergebnis harmlos ist, etwa ein zusätzlicher Cache-Miss.
• Den Filter zusammen mit den Kennungen seiner Hashfunktionen, seinem Seed und seiner Grösse speichern; jede Änderung bedeutet einen Neuaufbau aus der vollständigen Menge.
• Ihn dort einsetzen, wo negative Lookups überwiegen (unbekannte Benutzernamen, gelöschte Schlüssel, kalte Objekte), und den Anteil der von ihm gefilterten Abfragen messen, bevor er beibehalten wird.
• Nach Zeitplan neu aufbauen, wenn die zugrunde liegende Menge schrumpft; der Filter wächst nur.

Stolpersteine

Werden die k Hashes aus korrelierten Funktionen abgeleitet, steigt die Zahl falsch-positiver Ergebnisse. Ein zwischen Prozessen oder Sprachen geteilter Filter braucht bitidentisches Hashing. Nichts lässt sich auflisten, zählen oder entfernen. Ein Filter, dessen Seed oder Grösse von dem beim Aufbau verwendeten abweicht, liefert still falsche Antworten statt Fehler. Die Bemessung auf den Durchschnitt statt auf die Spitzenmenge verfehlt den Zweck.