Seite 3: Bloom-Filter, Vergleich

Inhaltsverzeichnis

Bloom-Filter im Überblick

Der Bloom-Filter geht auf Burton H. Bloom zurück und ist eine häufig verwendete Datenstruktur zur effizienten Suche in größeren Datenmengen. Die Funktionsweise hat Bill Mill in einem Tutorial recht anschaulich beschrieben.

Zusammengefasst haben Bloom-Filter folgende Vor- und Nachteile:

Vorteile	Nachteile
sehr performant	keinerlei Ähnlichkeitssuche, keine Fehlertoleranz
Treffergenauigkeit über die Größe des Index konfigurierbar, dabei besteht kein Risiko, dass ein Treffer nicht gefunden wird	Suchergebnisse werden nicht sortiert
kompaktes Speichern der Daten (oft wird nur circa 1/8 der Ausgangs-Datenmenge benötigt)	Risiko, sogenannte False Positives zu erhalten, das heißt, es können Datensätze zurückgegeben werden, die den Suchbegriff nicht enthalten
Implementierungen in allen relevanten Programmiersprachen verfügbar
leicht parallelisierbar (über Aufteilung des Suchindex auf mehrere Server/CPU-Kerne)

Bloom-Filter werden vor allem im Datenbankbereich und in Proxys wie Squid eingesetzt, um zu ermitteln, ob ein bestimmter Wert in einer (großen) Ergebnismenge vorhanden ist. In der Regel liegt die Ausführungszeit dabei deutlich unter der Zeit, die für eine vollständige Datenbankabfrage benötigt würde. Auch der Chrome-Browser nutzt intern Bloom-Filter, um zu prüfen, ob eine eingegebene URL mit der Signatur einer gefährlichen Website übereinstimmt.

Im Praxisbeispiel ist der Suchindex letztlich ein großes Array, das alle Werte eines Datensatzes in einem Bloom-Filter erfasst:

var bloomFilterArray = [];

var bloom = new BloomFilter(bits, 6);
bloom.add(lastName);
bloom.add(firstName); // usw.

bloomFilterArray.push(bloom);
 

Durch das Array iteriert die Anwendung bei jeder Suchanfrage komplett:

for(var i = 0; i < bloomFilterArray.length; i++) {
  if(bloomFilterArray[i].test(term)) {
    // Suchbegriff gefunden
  }
}

Anhand der Bloom-Filter soll auch untersucht werden, inwieweit die Parallelisierung der Suche einen positiven Einfluss auf die Performance haben kann. Letztlich ist dazu das erzeugte Array aufzuteilen und im Anschluss per WebWorker an mehrere Threads zu übergeben. Ein WebWorker ist ein Skript, das die Suche in einer Teilmenge in einem eigenen Thread ausführt und nach Abschluss wieder an das aufrufende Skript übergibt. Die Initialisierung sowie das Zusammenfügen der Ergebnisse dauern einige Millisekunden.

Bei einer kleinen Ergebnismenge fällt das weniger ins Gewicht als bei vielen tausend Suchtreffern. Im Beispiel kommen statisch vier WebWorker zum Einsatz, sobald der Nutzer die entsprechende Checkbox aktiviert. Unter Produktivbedingungen ist es sinnvoll, zunächst die Anzahl verfügbarer Prozessorkerne (z. B. über navigator.hardwareConcurrency) zu ermitteln und die Daten entsprechend aufzuteilen.

Vergleich der Maßnahmen

Bei kleineren Datenmengen (< 10.000 Datensätze) ergeben sich nur unwesentliche Unterschiede zwischen den drei Verfahren. Jeder der vorgestellten Ansätze hat einen anderen Schwerpunkt. Somit ist ein Vergleich zwischen einer (toleranten) Ähnlichkeitssuche und einem einfachen und eher unflexiblen Bloom-Filter nicht wirklich aussagekräftig. Je nach Use Case ist es allerdings wichtig, die Alternativen und damit verbundenen Vor- und Nachteile sowie ihre Beschränkungen zu kennen. Daher wurden im Sinne des Vergleichs letztlich alle Messungen auf der gleichen Datenbasis vorgenommen.

Die Vergleichsergebnisse sind in der folgenden Tabelle zusammengefasst. Jede Suche wurde dreimal ausgeführt und der Mittelwert in Millisekunden notiert. Die Messung fand immer im privaten Modus der Browser statt, um Einflüsse durch Plug-ins und Add-Ons auszuschließen. Als Testsysteme wurden ein iPad Air und ein iPhone 5s unter iOS 8 sowie ein PC mit Core-i7-Prozessor und 12 GB RAM unter Windows 7 verwendet.

				PC
Datensätze	Suchbegriff	Verfahren	Anzahl Treffer	Chrome (v40)	Firefox (v35)	IE11	IE9
1000	Sachs	Angular	204	16	34	19	33
1000	Sachs	Fuzzy	365	125	340	110	144
1000	Sachs	Bloom	1	3	1	3	21
1000	Sachs	Bloom (4 Threads)	1	3	3	4	-
10000	Edvard-Munch-Straße	Angular	1	98	141	89	126
10000	Edvard-Munch-Straße	Fuzzy	19	3423	16711	3060	7429
10000	Edvard-Munch-Straße	Bloom	1	16	11	39	156
10000	Edvard-Munch-Straße	Bloom (4 Threads)	1	18	12	30	-
100000	11.05.1985	Angular	6	413	690	620	1266
100000	11.05.1985	Bloom	6	74	70	128	898
100000	11.05.1985	Bloom (4 Threads)	6	60	46	84	-
250000	Berlin	Angular	12774	1012	2038	1710	3155
250000	Berlin	Bloom	12484	157	98	241	1590
250000	Berlin	Bloom (4 Threads)	12484	234	154	220	-
500000	Neukirch/Lausitz	Angular	34	2148	4390	4032	7382
500000	Neukirch/Lausitz	Bloom	34	280	274	652	5643
500000	Neukirch/Lausitz	Bloom (4 Threads)	34	180	165	-	-

				iPhone 5s	iPad Air
Datensätze	Suchbegriff	Verfahren	Anzahl Treffer	Safari	Safari
1000	Sachs	Angular	204	18	20
1000	Sachs	Fuzzy	365	131	119
1000	Sachs	Bloom	1	8	2
1000	Sachs	Bloom (4 Threads)	1	4	10
10000	Edvard-Munch-Straße	Angular	1	177	202
10000	Edvard-Munch-Straße	Fuzzy	19	4773	5384
10000	Edvard-Munch-Straße	Bloom	1	31	29
10000	Edvard-Munch-Straße	Bloom (4 Threads)	1	42	21
100000	11.05.1985	Angular	6	1526	1200
100000	11.05.1985	Bloom	6	149	190
100000	11.05.1985	Bloom (4 Threads)	6	96	85
250000	Berlin	Angular	12774	4073	3897
250000	Berlin	Bloom	12484	207	150
250000	Berlin	Bloom (4 Threads)	12484	619	395
500000	Neukirch/Lausitz	Angular	34	-	-
500000	Neukirch/Lausitz	Bloom	34	-	-
500000	Neukirch/Lausitz	Bloom (4 Threads)	34	-	-

Daraus ergeben sich folgende wesentlichen Erkenntnisse:

• Der AngularJS-Filter funktioniert mit bis zu 50.000 Datensätzen in allen Browsern gut, generell ist er im Chrome am schnellsten (was nicht verwundert, da AngularJS maßgeblich von Google entwickelt wird).
• Die Ähnlichkeitssuche ist im IE11 am schnellsten, IE9 und vor allem Firefox fallen deutlich ab. Suchen in mehr als 1000 Datensätzen sind generell zu langsam (Optimierungspotenzial).
• Genaue Suchen (Bloom-Filter) sind in allen aktuellen Browsern mit bis zu 100.000 Datensätzen performant, bei größeren Datenmengen ist Firefox am schnellsten.
• Mehrere Threads über WebWorker lohnen sich nur bei großen Datenmengen, sind aber mit <200ms sehr performant (zumindest in Firefox und Chrome).
• WebWorker werden von allen aktuellen Browsern unterstützt, der IE11 lieferte bei 500.000 Datensätzen allerdings nur ein Viertel der Ergebnisse zurück
• Safari auf iPad und iPhone ist meist schneller als IE9 und funktionierte mit bis zu 250.000 Datensätzen, stürzte bei 500.000 Datensätzen aber ab (vermutlich wegen Speichermangel).

Wie bereits erwähnt, wurde jede Suche immer auf dem kompletten Datensatz ausgeführt, was für die Praxis anzupassen wäre, da es beispielsweise nicht sinnvoll ist, in allen Vornamensfeldern nach einem Datum zu suchen. Mit einer entsprechenden Aufbereitung sind dann auch Suchen im Millionenbereich machbar.