Bloom-Filter

Ein Bloom-Filter ist ein Trick aus der Informatik, mit dem ein Programm eine einzige Frage beantworten kann: Habe ich diese Sache schon einmal gesehen? Statt alle bisherigen Einträge vollständig zu speichern, merkt sich der Bloom-Filter nur eine Art Kurznotiz zu jedem Eintrag. Das braucht extrem wenig Speicherplatz, hat aber einen Preis. Der Filter kann mit voller Sicherheit sagen, dass etwas noch nie vorkam. Bei einem Treffer sagt er dagegen nur, dass es sehr wahrscheinlich vorkam. Solche Fehltreffer nennt man falsch positive Ergebnisse, und man kann ihre Häufigkeit beim Aufbau des Filters festlegen.

Warum man dafür Speicher opfert

Große Systeme müssen ständig prüfen, ob etwas schon bekannt ist. Eine Suchmaschine will keine Webseite zweimal herunterladen. Eine Datenbank will nicht bei jeder Anfrage die Festplatte durchsuchen, wenn der gesuchte Eintrag ohnehin nicht existiert. Diese Prüfung passiert millionenfach pro Sekunde und muss deshalb winzig und schnell sein.

Eine klassische Liste aller bisherigen Einträge wäre dafür viel zu groß. Für eine Milliarde Web-Adressen bräuchte man leicht mehrere zehn Gigabyte. Ein Bloom-Filter für dieselbe Menge kommt bei einer Fehlerquote von einem Prozent mit etwa einem Gigabyte aus. Der Unterschied entscheidet darüber, ob die Prüfung im schnellen Arbeitsspeicher stattfindet oder auf der langsamen Festplatte.

Wichtig ist die Richtung des Fehlers. Der Filter behauptet nie, etwas sei neu, obwohl es alt ist. Er behauptet höchstens, etwas sei alt, obwohl es neu ist. Für viele Anwendungen ist das genau die harmlose Fehlerrichtung. Im schlimmsten Fall wird eine unnötige, aber korrekte Nachprüfung ausgelöst.

Bits kippen statt Einträge merken

Im Kern besteht ein Bloom-Filter aus einer sehr langen Reihe von Schaltern, die entweder aus oder an sind. Am Anfang stehen alle auf aus. Kommt ein neuer Eintrag hinzu, wird er durch mehrere Rechenverfahren geschickt, sogenannte Hashfunktionen. Jede davon verwandelt den Eintrag in eine Positionsnummer in dieser Reihe. Die Schalter an diesen Positionen werden auf an gestellt.

Bei einer Abfrage passiert dasselbe noch einmal. Das Programm berechnet die Positionen und schaut nach. Ist auch nur ein Schalter aus, war der Eintrag garantiert nie da. Sind alle an, lautet die Antwort: wahrscheinlich schon vorhanden. Sicher ist das nicht, denn diese Schalter könnten von anderen Einträgen umgelegt worden sein.

Man kann sich das wie Stempelabdrücke auf einem Blatt vorstellen. Jeder Besucher hinterlässt drei Stempel an festen Stellen. Findet man alle drei Stempel eines Besuchers, war er vermutlich da. Es könnten aber auch drei andere Leute gewesen sein, deren Stempel zufällig genau dort landeten. Je voller das Blatt wird, desto häufiger passiert das. Deshalb legt man die Größe des Filters vorher passend zur erwarteten Datenmenge fest. Ein typischer Irrtum ist übrigens die Annahme, man könne Einträge wieder löschen. Das geht nicht, weil ein Schalter zu mehreren Einträgen gehören kann.

Wo Bloom-Filter still im Hintergrund laufen

Datenbanken wie Cassandra oder HBase nutzen Bloom-Filter, um Festplattenzugriffe zu vermeiden. Bitcoin-Software verwendete sie zeitweise, damit sparsame Geräte nur die für sie relevanten Transaktionen anfordern. Auch Webbrowser haben ähnliche Verfahren eingesetzt, um Adressen gegen Listen bekannter Betrugsseiten zu prüfen, ohne die ganze Liste lokal zu speichern.

Im KI-Umfeld tauchen Bloom-Filter bei der Aufbereitung von Trainingsdaten auf. Trainingstexte stammen aus riesigen Web-Sammlungen und enthalten massenhaft Dubletten. Diese Duplikate zu entfernen verbessert die Qualität eines Sprachmodells messbar. Bei Milliarden von Textabschnitten ist ein Bloom-Filter oft der einzige praktikable Weg, Wiederholungen zu erkennen.

In Nachrichtenartikeln über Infrastruktur begegnet der Begriff meist als Nebensatz zur Effizienz. Verwandt sind Hashtabellen, die exakt antworten, dafür aber deutlich mehr Speicher brauchen. Wer den Unterschied kennt, versteht eine Grundregel der Informatik: Man tauscht oft ein wenig Genauigkeit gegen sehr viel Geschwindigkeit.