Größere Datenmengen mit JavaScript performant durchsuchen

Inhaltsverzeichnis

Die Suche nach Textdaten ist eine Kernfunktion vieler Anwendungen. Um sie genau, schnell und fehlertolerant zu gestalten, kommen häufig Suchserver zum Einsatz – es gibt aber auch andere Herangehensweisen.

Suchen laufen meist nach folgendem Schema ab: Der Anwender gibt einen Suchbegriff ein, dieser geht über das Backend an die Datenbank, die die Treffer via Backend wieder zurückgibt. Fortgeschrittene Funktionen wie eine Ähnlichkeitssuche lassen sich in der Datenbank oder mit Indizes wie Lucene abbilden. So weit, so etabliert. Allein für die Initialisierung mit Request und Response sind je nach Serveranbindung 50 bis 200 Millisekunden einzukalkulieren, die eigentliche Suche kostet oft ein Vielfaches davon.

Betrachtet man diesen Umstand, könnte man auf die Idee kommen, die Suche bereits im Client mit JavaScript auszuführen, um den Overhead zu reduzieren. Allerdings stellt sich dabei die Frage, wo die Grenzen einer JavaScript-In-Memory-Suche auf Desktop und Smartphone liegen.

Eine Suche auf dem Client hat viele Vorteile: Je nach Anwendung lassen sich einige Requests einsparen, was vor allem die gefühlte Geschwindigkeit deutlich steigert. Die Suche reagiert sofort und die Bedienung scheint nahtlos. Server und/oder Datenbank kann man unter Umständen spürbar entlasten, denn die Leistung im Client steht dem Inhaltsanbieter letztlich gratis zur Verfügung. Weiterhin entspricht solch ein Vorgehen dem Ansatz "offline first", bei dem es maßgeblich ist, dass ein Anwender auch ohne Internetverbindung möglichst viele Funktionen nutzen kann.

Längst nicht jede Suche lässt sich im Client ausführen – in vielen Fällen verbieten es die Sicherheitskriterien. Zum Beispiel dürfen Daten zu Finanztransaktionen den gesicherten Server nicht verlassen. Auch der Transfer der Nutzdaten fällt ins Gewicht – ein im folgenden beschriebenes Beispiel arbeitet mit 500.000 Datensätzen, die im JSON-Format bereits etwa 100 Megabyte Speicher benötigen. Bei einer Übertragung mit aktiver Zip-Kompression gehen immer noch circa 30 Megabyte über die Leitung, was für die meisten Anwendungen zu viel sein dürfte.

Ein weiteres Thema ist die Synchronisation, da der Client Änderungen am serverseitigen Datenbestand nicht berücksichtigt. Hier kann man sich entweder mit reaktiven Ansätzen wie dem von Meteor oder einem regelmäßig abgefragten Diff behelfen (Abfrage aller geänderten Datensätze seit Zeitpunkt X). Häufige Änderungen an den Daten erschweren Letzteres allerdings.

Insofern kann es meistens nur darum gehen, eine serverseitige Suche sinnvoll durch den Client zu ergänzen. Das Potenzial zur Erhöhung der Benutzerzufriedenheit, eine verringerte Last und letztlich reduzierte Kosten sollten Motivation genug sein.

Hier einige konkretere Use Cases:

• Autocomplete-Suche auf Grundlage von Vorschlagswerten, die nur einmalig vom Server anzufordern sind
• Suche in hochgeladenen Daten (z. B. Office-Dokumente oder XML)
• Suche in öffentlich zugänglichen Daten (beispielsweise Städte- oder Länderlisten)
• Suche in historischen Daten mit Anwenderbezug (etwa gelesene Texte, Einträge einer Timeline der letzten 30 Tage oder Metadaten gekaufter Produkte)
• Suche in clientseitig generierten Daten (z. B. Online-Games)

Voraussetzung für viele der genannten Use Cases ist das Caching der Daten, das mit localStorage und IndexedDB inzwischen auch für größere Bestände möglich ist.

Aus der Praxis

Für den Artikel wurde eine Beispielanwendung implementiert, die eine Suche in strukturierten Daten abbildet. Der Anwender gibt einen Begriff in ein Suchfeld ein und bekommt die Treffer in einer Tabelle ausgegeben. Der komplette Quelltext ist auf GitHub zu finden.

Die Benutzeroberfläche ist simpel und soll Suchtreffer sowie Messwerte zur Suchdauer und -vorbereitung ausgeben. Bei der Umsetzung wurden drei Verfahren untersucht:

1. Filter: Das Suchergebnis erhält alle Datensätze, in denen der Suchbegriff vorkommt (z. B. "Berlin" findet alle Datensätze mit der Stadt "Berlin" aber auch "Berliner Straße").
   
2. Ungenaue Suche (Fuzzy): Das Suchergebnis enthält auch Elemente, die dem Suchbegriff ähneln. Sie wird meist in Autocomplete-Feldern oder als Suchvorschlag verwendet (z. B. "Entwckler" findet auch "Entwickler").
3. Genaue Suche: Die Suche findet nur Ergebnisse, die exakt der Eingabe entsprechen.
   

Die Fuzzy-Suche ist benutzerfreundlich, aber aufgrund ihrer Komplexität auch am langsamsten. Eine genaue Suche ist schnell, toleriert aber keine Ungenauigkeiten oder Schreibfehler. Zwischen beiden Extremen liegen Filter.

Als JavaScript-Funktionen sind die Verfahren zum Beispiel in folgenden Frameworks und Bibliotheken verfügbar:

1. AngularJS hat sich für Single Page Apps etabliert und bringt mit den Filtern eine effiziente Suche mit.
2. Fuse.js ist die Implementierung einer Ähnlichkeitssuche von Kiro Risk, die mit dem Bitap-Algorithmus arbeitet.
   
3. Bloom-Filter: Implementierung eines Bloom-Filters (Vergleich über eine Hashtabelle) von Jason Davies.

identity-generator

• ID (eindeutig)
• Vorname
• Nachname
• Straße
• Hausnummer
• Postleitzahl
• Stadt
• Bundesland
• E-Mail-Adresse
• Telefonnummer
• Geburtstag

Im Beispiel lässt sich die zugrunde liegende Datenmenge in mehreren Schritten von 1000 bis 500.000 setzen und vergleichen. Die Suche geht dabei immer über alle Werte eines Datensatzes (außer die ID). Ein Filtern nach Datentyp findet nicht statt, das heißt, bei einer Suche in 500.000 Datensätzen werden 5.000.000 Werte durchsucht.