Durch die Bloome gesucht

Bloom-Filter: So beschleunigt man Datenzugriffe
Kommentare

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.

Der Bloom-Filter ist keineswegs eine Neuheit. Ein solcher Filter ist schnell programmiert und bietet sich besonders bei stark frequentierter Suche in größeren Datenmengen an. Bereits um 1970 erfand den einschlägigen Quellen zufolge ein gewisser Burton Howard Bloom den nach ihm benannten Bloom-Filter. 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.

Abb. 1: Funktionsweise des Bloom-Filters

Abb. 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 Performancegewinn liegt demnach in der Zeitdifferenz der eingesparten und potenziell teuren Suchvorgänge abzüglich der für den Zugriff auf den Bloom-Filter benötigten Zeit. Je teurer der Suchvorgang ist, je häufiger gesuchte Elemente in der Datenmenge nicht enthalten sind, und je effizienter der Filter arbeitet, umso höher sind die erzielbaren Performancegewinne. Außerdem ist der Effekt konstruktionsbedingt umso größer, je seltener Elemente der Datenmenge entfernt oder geändert werden.

Wie aus Abbildung 2 ersichtlich, besteht der algorithmische Teil des Bloom-Filters aus einem Satz verschiedener Hash-Funktionen. Während der Initialisierungsphase des Filters werden für jeden Datenwert mittels dieser Hash-Funktionen eine entsprechende Anzahl Bit-Indizes berechnet, üblicherweise per Modulo des berechneten Hash-Werts über die festgelegte Größe Anzahl Bits. Wurde das Bitset also beispielsweise auf 4 096 Bits dimensioniert, ergeben sich bei vier Hash-Funktionen pro Datenwert vier Indexpositionen im Bereich von 0 und 4 095. Die vier Bits an den so ermittelten Positionen des initial komplett leeren Bitsets werden gesetzt, und man verfährt weiter, bis die Positionen berechnet und die entsprechenden Bits für alle Datenwerte gesetzt wurden. Ist ein Bit an einer berechneten Position bereits gesetzt, bleibt es auch in diesem Zustand.

Abb. 2: Ein Bloom-Filter setzt sich aus verschiedenen Hash-Funktionen zusammen

Abb. 2: Ein Bloom-Filter setzt sich aus verschiedenen Hash-Funktionen zusammen

 

Im Suchmodus funktioniert der Bloom-Filter im Grunde analog. Auch hier werden vom Suchwert zunächst wieder über die Hash-Funktionen die zugehörigen Bitpositionen ermittelt. Sodann wird geprüft, ob die Bits an allen berechneten Indizes gesetzt sind. Fehlt mindestens ein Bit, ist der Suchwert mit Sicherheit nicht in den Daten, da ja andernfalls alle Bits gesetzt sein müssten. Sind jedoch tatsächlich alle Bits gesetzt, heißt das im Umkehrschluss nicht zwingend, dass der Suchwert auch tatsächlich in den Daten enthalten ist, weil die Bits wegen möglicher Kollisionen auch durch völlig andere Werte gesetzt worden sein könnten – sowohl Hash als auch Indexposition erlauben ja keinen Rückschluss mehr auf die ursprünglichen Daten. Die Aussage in diesem Fall lautet daher nur: Möglicherweise befindet sich der Suchbegriff in den Daten, man kann es aber nicht mit letzter Bestimmtheit sagen.

Da für Speicherung und Suche eine Hash-Funktion verwendet wird, ergibt sich automatisch eine wichtige Einschränkung des Algorithmus: Eine Suche nach Teilstrings oder in der Schreibweise abweichender Zeichenketten ist prinzipbedingt nicht möglich. Soll zwischen Groß- und Kleinschreibung nicht unterschieden werden, sollte die Schreibweise der Datenwerte daher vor der Berechnung der Hash-Werte entsprechend normiert werden.

Optimale Wahl der Parameter

Zwei Faktoren haben auf die Effizienz des Filters wesentlichen Einfluss. Der erste dieser beiden Faktoren ist der Füllgrad des Bitsets. Je mehr Bits nämlich gesetzt sind, desto höher ist auch die Wahrscheinlichkeit für einen „false positive“, bei dem das gesuchte Element zwar nicht in den Daten enthalten ist, aber aufgrund gefundener Bloom-Bits dennoch eine Suche durchgeführt wird. Im Extremfall eines vollständig mit gesetzten Bits gefüllten Bitsets würde keine Anfrage an den Bloom-Filter mehr verneint, somit der Filter effektiv nutzlos, da immer alle Bits gefunden und somit auch eine Suche durchgeführt würde. Es ist also wünschenswert, das Bitset ausreichend groß zu dimensionieren, sodass möglichst wenige Indexkollisionen auftreten und der Wirkungsgrad des Filters somit recht hoch ist, andererseits soll aber auch der verbrauchte Speicher nicht über Gebühr ansteigen.

Der zweite für die Effizienz wichtige Faktor ist die Anzahl der verwendeten Hash-Funktionen. Hier ist es grundsätzlich wünschenswert, so wenige Hash-Funktionen wie gerade nötig einzusetzen. Bezüglich Laufzeit kostet jede Berechnung eines weiteren Hashes ganz banal auch zusätzliche Rechenzeit. Bezüglich des Speicherverbrauchs muss man mit jedem weiteren Hash auch das Bitset vergrößern, weil ja pro Hash ein weiteres Bit belegt wird, was bei unveränderter Größe des Bitsets dessen Füllgrad ansteigen lässt. Positiv wirkt sich hingegen die Tatsache aus, dass mehrere Bits natürlich wieder die Wahrscheinlichkeit für einen Treffer für die gesamte Bitkombination verringern, sofern das Bitset nur ausreichend groß dimensioniert ist.

Überhaupt empfiehlt es sich, gute gleichverteilte Hash-Funktionen zu verwenden, die sich dennoch möglichst performant berechnen lassen sollten. Die kryptografische Qualität der Hash-Funktion ist für unsere Zwecke hingegen vernachlässigbar, ein 512er SHA wäre also nicht unbedingt eine gute Wahl. An hochgezüchteten Hash-Implementierungen herrscht im Web kein Mangel, sodass sich mit ein wenig Recherche schnell einige brauchbare Kandidaten finden lassen. Im Beispielcode zum Artikel wird eine einfache Pascal-Implementation des Public-Domain-Algorithmus FNV für 32 Bit verwendet. Da die ursprünglichen Entwickler im Gegensatz zu der nach sehr präzisen Kriterien ausgewählten Primzahl nach eigener Aussage den Start-off-Set des Algorithmus völlig willkürlich gewählt haben, bot es sich an, die benötigte Menge an Hash-Funktionen einfach durch weitere zufallsgenerierte Start-off-Sets bei ansonsten unverändertem Algorithmus zu erzeugen. Und tatsächlich funktioniert dieser Ansatz zumindest für unseren Testfall erstaunlich gut.

Für die Wahl der beiden Parameter „Größe des Bitsets“ und „Anzahl verwendeter Hashes“ gibt es ausführliche Untersuchungen und Herleitungen, die den Rahmen des Artikels sprengen würden und sich bei Interesse in der Literatur leicht nachlesen lassen. Die Essenz aus der Theorie sind die beiden von Thomas Jung und Mark Fischer entnommenen Formeln in Abbildung 3, mit deren Hilfe sich beide Parameter automatisch dimensionieren lassen. Als optimaler Wert für die False-Positives-Rate p wird in der Literatur üblicherweise 50 Prozent empfohlen, praktische Tests bestätigen diese Empfehlung als guten Trade-off zwischen Speicherverbrauch und Effizienz. Ein höherer Wert führt recht schnell zu signifikanter Performanceverschlechterung, die genannten 50 Prozent sollten daher auf keinen Fall überschritten werden.

Abb. 3: Mit diesen Formeln lassen sich die Parameter „Größe des Bitsets“ und „Anzahl verwendeter Hashes“ automatisch dimensionieren

Abb. 3: Mit diesen Formeln lassen sich die Parameter „Größe des Bitsets“ und „Anzahl verwendeter Hashes“ automatisch dimensionieren

 

Die erste Formel liefert die Größe m des Bitsets unter der Annahme, dass die noch zu berechnende optimale Anzahl Hash-Funktionen verwendet wird. Diese Größe sollte nach der Berechnung noch auf die nächste Zweierpotenz aufgerundet werden, um die Berechnung des Modulus effizient zu halten. Die für ein konkretes Szenario optimale Anzahl von Hash-Funktionen wird anschließend über die zweite Formel ermittelt. Natürlich sind die gemäß Theorie berechneten Werte zunächst nur die empfohlenen Defaults und somit Richtwerte. In der Praxis hat sich bewährt, das Bitset im Zweifelsfall bei ausreichend freiem Speicher lieber etwas größer zu dimensionieren, was bei gleichbleibender Anzahl Hash-Funktionen effektiv eine Senkung des Füllgrads bewirkt und somit die Wahrscheinlichkeit für Kollisionen absenkt. Als weitere Optimierung empfiehlt Bloom, den Einsatz einer zusätzlichen Liste für erkannte False Positives in Betracht zu ziehen, was im Beispielcode allerdings nicht umgesetzt wurde.

Der Einfluss der Parameterwahl bei ansonsten gleichen Bedingungen ist anhand des in Abbildung 4 gezeigten Beispiels sehr gut zu sehen: Bereits die Halbierung der empfohlenen Bitanzahl verschlechtert die Performance dramatisch, während eine Verdopplung der Performance erst bei der achtfachen Größe erreicht wird. Trotzdem bringt eine gegenüber der Empfehlung verdoppelte Bitanzahl bereits weitere beachtliche 10 Prozent Performancegewinn. Ebenfalls zu sehen sind die eher moderaten Auswirkungen der Hash-Anzahl. Tendenziell führen diese durch die damit verbundenen Berechnungskosten oberhalb einer bestimmten Grenze eher zu sinkender Performance, sodass es tatsächlich angeraten scheint, nicht ohne Not zu viele Hashes einzusetzen. Allerdings muss man auch sagen, dass man nicht zu viel Zeit in den Versuch verschwenden sollte, durch Parametertuning noch ein Prozent mehr Performance herauszuquetschen. Die tatsächliche Effizienz des Algorithmus hängt in hohem Maße nämlich auch von den Daten und sogar noch mehr von den Suchanfragen selbst ab – beides aber sind Größen, die man als Programmierer kaum oder gar nicht kontrollieren kann.

Abb. 4: Performancevergleich bei unterschiedlicher Anzahl von Hashes

Abb. 4: Performancevergleich bei unterschiedlicher Anzahl von Hashes

 

Der Beispielcode

Der Beispielcode zum Thema ist aufgrund der technisch nicht allzu anspruchsvollen Umsetzung vergleichsweise simpel. Um für die Tests ein paar brauchbare Werte zu erhalten und das Ganze bei möglichst geringem Zeitaufwand pro Test trotzdem wenigstens näherungsweise an einen realen Einsatzfall anzupassen, liest das Programm zwei beliebige und möglichst große Textdateien ein. Geeignete Kandidaten findet man beispielsweise auf Projekt Gutenberg. Da der Code besagte Textdateien einliest und in einzelne Wörter auftrennt, der für den Beispielcode geschriebene Einfachst-Parser der untersten Preisklasse jedoch bereits mit Umlauten überfordert ist, sollte der Text nach Möglichkeit Englisch sein. Für die Tests wurden die King-James-Bibel und eine englische Ausgabe von Victor Hugos „Les Miserables“ verwendet. Als interessantes Detail am Rande sei vermerkt, dass die Bibel-Datei geringfügig größer ist, aber Victor Hugos Wortschatz mit 25 500 eindeutigen Phrasen, allerdings inklusiver aller verwendeten Flexionsformen, trotz der geringeren Dateigröße nahezu doppelt so groß ist.

Um Zeit zu sparen, füllt die Applikation bereits beim Eingeben die beiden Stringlisten mit den Phrasen auf. Das geschieht asynchron, sobald in das Textfeld ein als gültiger Dateiname identifizierter Text eingegeben wurde. Nach dem Einlesen wird noch der Bloom-Filter initialisiert und mit den gefundenen Phrasen des zu prüfenden Texts gefüllt. Die Arbeitsthreads zum Einlesen der Daten kommunizieren dabei anhand von Events mit dem UI-Thread, welcher seinerseits über einen Timer und besagte Events prüft, wie weit die laufenden Arbeiten fortgeschritten sind. Sind alle Daten geladen, analysiert worden und ist der Bloom-Filter fertig initialisiert, wird der Start-Button aktiv und die Tests können gestartet werden. Der Algorithmus aller Tests ist stets derselbe: Alle Phrasen des Vergleichstexts werden der Reihe nach in dem zu prüfenden Text gesucht. Je nach Einstellung der Combobox wird dabei der Bloom-Filter aktiviert oder eben nicht.

Schaltet man auf das zweite Tab um, wird wieder derselbe Test durchgeführt, diesmal jedoch mehrfach und mit verschiedenen Kombinationen der beiden Parameter Bitfeldgröße und Hash-Anzahl. In der Statuszeile wird zum Vergleich die optimale Parameterkombination gemäß obengenannter Formeln angezeigt (Abb. 4). Da in diesem zweiten Fall ein Vergleich stattfindet, wird pro Parameterkombination jeweils ein Test mit und ein weiterer Test ohne aktivierten Bloom-Filter durchgeführt. Anschließend wird der mit dieser Kombination erzielte Performancegewinn in Prozent berechnet und in der Tabelle eingetragen. Negative Werte bedeuten also, dass sich die Laufzeit um den angegebenen Prozentwert verschlechtert hat.

Da die Messwerte zum einen schwanken und zum anderen, wie bereits weiter oben dargelegt, auch ziemlich stark von den konkreten Daten und Suchbegriffen abhängen, sollte man ruhig einmal eigene Testdaten in das Programm einlesen und prüfen, wie hoch der erzielbare Leistungsgewinn bei verschiedenen Anfrageprofilen wirklich ausfallen würde. Wie man sieht, ist durch den Einsatz eines Bloom-Filters unter Umständen sogar bei Zugriffen, die völlig ohne Netzwerk- oder Plattenzugriff rein im Hauptspeicher stattfinden, ein durchaus merkbarer Performancegewinn erzielbar. Es ist also ratsam, sich der alten Optimierungsweisheit zu erinnern, nach der man den Effekt jeder Optimierung nicht einfach nur abschätzen, sondern tatsächlich auch nachmessen sollte.

Aufmacherbild: Control programming algorithm block with business person on the background von Shutterstock / Urheberrecht: Sergey Nivens

Unsere Redaktion empfiehlt:

Relevante Beiträge

Meinungen zu diesem Beitrag

X
- Gib Deinen Standort ein -
- or -