© Liashko/Shutterstock.com
Wie Bloom-Filter Datenzugriffe deutlich beschleunigen

Durch die Bloome gesucht


Eine gängige Theorie besagt, dass die wirklich genialen Erfindungen meist gleichzeitig auch ziemlich simpel und schön sind. Eine dieser technisch unkomplizierten Algorithmen mit dem Potenzial zu durchschlagender Wirkung ist der Bloom-Filter. Ein solcher Filter ist schnell programmiert und bietet sich besonders bei stark frequentierter Suche in ­größeren Datenmengen an.

Der Bloom-Filter ist keineswegs eine Neuheit. Bereits um 1970 erfand den einschlägigen Quellen zufolge ein gewisser Burton Howard Bloom den nach ihm benannten Bloom-Filter [1]. Der Algorithmus ist seitdem weithin erprobt und gründlich untersucht worden, sodass neben der Praxis der Implementierung auch die mathematischen Hintergründe ausführlich beleuchtet worden sind.

Ein typisches Einsatzszenario für einen Bloom-Filter ist die Suche in großen Datenmengen. Das könnte beispielsweise das Nachschlagen eines Schlüssels in einer größeren Tabelle sein, die in einem für die Suche eher ungünstigen Datenformat vorliegt oder womöglich sogar auf einem langsamen Massenspeicher oder in einer Datenbank gespeichert ist und demzufolge bei jedem Zugriff einen vergleichsweise hohen Aufwand verursacht. Wird diese Routine nun im Programmablauf mehrere zehntausend Mal aufgerufen, können sich bereits kleine Laufzeitunterschiede zu großen Performanceproblemen aufsummieren.

Die Funktionsweise im Detail

Das Funktionsprinzip des Bloom-Filters besteht nun darin, dass er der eigentlichen Suche vorgeschaltet wird, um unnötige Suchvorgänge einzusparen (Abb. 1). Im Gegensatz zu einem Cache werden dabei allerdings nicht die Schlüssel und Daten selbst im Speicher vorgehalten, sondern nur ein vergleichsweise kleines Bitfeld. Der Bloom-Filter liefert eine probabilistische Aussage über das Vorhandensein eines gesuchten Schlüssels in der Datenmenge. Diese Auskunft besagt, ob ein gesuchtes Element in der Datenmenge enthalten sein könnte, oder ob es definitiv nicht enthalten ist.

geyer_bloome_1.tif_fmt1.jpgAbb. 1: Funktionsweise des Bloom-Filters

Genau das ist auch der Grund, warum der Filter die Suche nicht vollständig ersetzen kann, sondern ihr nur vorgeschaltet wird: Die Aussage, dass ein Element nicht enthalten ist, ist absolut und hundertprozentig sicher. Die gegenteilige Aussage jedoch, ob ein Element enthalten ist, kann uns der Bloom-Filter nicht mit Sicherheit geben. Er kann nur ermitteln, ob das gesuchte Element möglicherweise enthalten sein könnte. Die letzte Sicherheit liefert in diesem Fall tatsächlich erst die Suche selbst.

Der effektive Per...

Exklusives Abo-Special

Angebote für Teams

Für Firmen haben wir individuelle Teamlizenzen. Wir erstellen Ihnen gerne ein passendes Angebot.

Das Library-Modell:
IP-Zugang

Das Company-Modell:
Domain-Zugang