Elasticsearch von unten nach oben, Teil 1

Einführung

Auf diese Weise möchten wir Ihnen näherbringen, wie Elasticsearch, Lucene und – bis zu einem gewissen Grad – Suchmaschinen allgemein „unter der Motorhaube“ funktionieren. Fürs Autofahren reicht es aus, das Lenkrad zu drehen und auf ein paar Pedale zu treten, aber wirklich kompetente Fahrer kennen in der Regel zumindest ein paar der mechanischen Grundlagen ihres Fahrzeugs. Bei Suchmaschinen ist das nicht anders. Elasticsearch bietet APIs, die sich sehr einfach nutzen lassen, und Sie können schnell mit ihnen loslegen und ohne viel Aufwand weit mit ihnen kommen. Aber für eine optimale Ausschöpfung des Potenzials, das das Produkt bietet, braucht es einiges an Wissen über die zugrunde liegenden Algorithmen und Datenstrukturen. Mit diesem Wissen können Sie seine umfangreiche Funktionalität so einsetzen, dass Ihre Nutzerinnen und Nutzer von einem besseren Sucherlebnis profitieren, ohne dass die Performance, Zuverlässigkeit und Aktualisierbarkeit Ihrer Systeme in (nahezu) Echtzeit darunter leidet.

Wir beginnen mit der grundlegenden Indexstruktur, dem invertierten Index. Diese Datenstruktur ist sehr vielseitig. Gleichzeitig ist sie aber auch sehr einfach zu handhaben und zu verstehen. Die Implementierung von Lucene ist ein hochgradig optimiertes und beeindruckendes technisches Meisterwerk. Wir werden uns an dieser Stelle nicht näher mit den Details dieser Implementierung befassen, sondern uns darauf konzentrieren, wie der invertierte Index genutzt und erstellt wird. Das beeinflusst, wie wir suchen und indexieren können.

Nach der Einführung in den invertierten Index als unterste aller Abstraktionsebenen schauen wir uns an,

• wie einfache Suchen durchgeführt werden,
• welche Arten von Suchen effektiv durchgeführt werden können (und welche nicht) und warum wir mit einem invertierten Index Probleme so lange transformieren, bis sie wie String-Präfix-Probleme aussehen,
• warum die vorherige Verarbeitung des Textes wichtig ist,
• wie Indizes in „Segmente“ aufgeteilt werden und welche Auswirkungen das auf das Suchen und Aktualisieren hat,
• woraus ein Lucene-Index besteht und
• was an der Elasticsearch-Shard und am Elasticsearch-Index besonders ist.

Wenn wir damit durch sind, wissen wir eine Menge darüber, was beim Suchen und beim Indexieren in einem einzelnen Elasticsearch-Knoten vor sich geht. Der zweite Artikel in dieser Reihe wird sich mit den verteilten Aspekten von Elasticsearch beschäftigen.

Invertierte Indizes und Indexbegriffe

Nehmen wir als Beispiel diese drei einfachen Dokumente: „Winter is coming.“, „Ours is the fury.“ und „The choice is yours.“. Nach ein paar einfachen Schritten zur Verarbeitung des Textes (Umwandlung in Kleinbuchstaben, Entfernen der Interpunktion und Zerlegen der Wörter) können wir den in der Abbildung gezeigten „invertierten Index“ konstruieren.

Der invertierte Index bildet Begriffe auf Dokumente (und nach Möglichkeit auch auf Positionen in den Dokumenten) ab, die den Begriff enthalten. Da die Begriffe in der Begriffsliste (Dictionary) sortiert sind, lassen sich einzelne Begriffe schnell finden – und anschließend auch deren Vorkommen in der Postings-Struktur. Das unterscheidet den invertierten Index vom „Vorwärtsindex“, der Begriffe aufführt, die mit einem konkreten Dokument in Zusammenhang stehen.

Bei einer einfachen Suche mit mehreren Begriffen werden alle Begriffe und deren Vorkommen gesucht, und zur Generierung der Ergebnisliste wird die Schnittmenge (bei UND-Suchen) oder die Vereinigungsmenge (bei ODER-Suchen) der Vorkommen herangezogen. Bei komplexeren Abfragetypen passiert natürlich noch mehr, aber der generelle Ansatz ist derselbe: Erst wird die sortierte Wortliste durchkämmt, um Kandidaten zu finden, dann wird an den zugehörigen Vorkommen, Positionen und so weiter gearbeitet.

Daraus ergibt sich, dass ein Indexbegriff die Einheit der Suche ist. Die Begriffe, die wir generieren, bestimmen, was für Suchen wir effizient durchführen (oder eben nicht durchführen) können. Wenn wir uns beispielsweise die obige Begriffsliste ansehen, können wir effizient alle Begriffe finden, die mit einem „c“ beginnen. Dagegen gibt es keine effiziente Möglichkeit, mit einer Suche alles zu finden, was „ours“ enthält. Für eine solche Suche müssten wir sämtliche Begriffe durchgehen, um auch den Begriff „yours“ zu finden, der ebenfalls die Zeichenfolge „ours“ enthält. Das ist bei allen Indizes mit einer nennenswerten Größe so aufwendig, dass eine solche Herangehensweise nicht infrage kommt. Mit Blick auf die Komplexität ist das Suchen nach Begriffen anhand ihres Präfixes \(\mathcal{O}\left(\mathrm{log}\left(n\right)\right)\), während das Finden von Begriffen anhand einer willkürlichen Teilzeichenfolge \(\mathcal{O}\left(n\right)\) ist.

Mit anderen Worten: Anhand von Begriffs-Präfixen ist es möglich, Informationen effizient zu finden. Wenn wir nichts als einen invertierten Index haben, möchten wir, dass alles wie ein String-Präfix-Problem aussieht. Hier ein paar Beispiele für solche Transformationen. Einige sind simpel, das letzte grenzt an Magie.

• Um alles zu finden, was mit „tastic“ endet, können wir die Rückwärtslesung indexieren (beispielsweise „fantastic“ → „citsatnaf“) und nach allem suchen, was mit „citsat“ beginnt.
• Das Auffinden von Teilzeichenfolgen erfordert häufig das Zerlegen von Begriffen in kleinere Begriffseinheiten, die sogenannten „N-Gramme“. So lässt sich zum Beispiel der Begriff „yours“ in „^yo“, „you“, „our“, „urs“ und „rs$“ zerlegen, sodass wir bei der Suche nach „our“ und „urs“ Vorkommen von „ours“ erhalten würden.
• Bei Sprachen mit zusammengesetzten Wörtern, wie Deutsch und Norwegisch, müssen wir ein Wort wie „Donaudampfschiff“ in seine Bestandteile zerlegen, also zum Beispiel {„donau“, „dampf“, „schiff“}, damit es bei der Suche nach „schiff“ gefunden wird.
• Geografische Koordinaten wie „(60.6384, 6.5017)“ lassen sich in „Geo-Hashes“ umwandeln (hier: „u4u8gyykk“). Je länger die Zeichenfolge ist, desto genauer ist die Angabe.
• Für ein phonetisches Matching, was zum Beispiel bei Namen von Personen sehr hilfreich sein kann, gibt es Algorithmen wie Metaphone, die „Smith“ in {„SM0“, „XMT“} und „Schmidt“ in {„XMT“, „SMT“} umwandeln.
• Für den Umgang mit numerischen Daten (und Zeitstempeln) generiert Lucene automatisch verschiedene Begriffe mit unterschiedlicher Präzision in einer Art Baumstruktur, um effiziente Bereichssuchen zu ermöglichen¹. Vereinfacht gesagt, kann die Zahl 123 als „1“-Hunderte, „12“-Zehner und „123“ gespeichert werden. Auf diese Weise wird bei der Suche nach allem im Bereich [100, 199] alles zurückgegeben, auf das der Begriff „1“-Hunderte zutrifft. Das ist natürlich etwas anderes als das Suchen nach allem, was mit „1“ beginnt, denn das würde auch „1234“ und so weiter als Ergebnis liefern.
• Für „Meinten Sie?“-Suchen und das Einschließen von Schreibweisen, die nahe am eingegebenen Suchbegriff sind, kann ein Levenshtein-Algorithmus verwendet werden, mit dem die Wortliste effektiv durchforstet wird. Das ist äußerst komplex und wie das in Lucene umgesetzt wurde, wird in diesem faszinierenden Artikel näher beschrieben.

Die Erläuterung der technischen Details der Verarbeitung von Text muss künftigen Artikeln vorbehalten bleiben, aber wir haben hier herausgearbeitet, wieso es wichtig ist, bei der Generierung von Indexbegriffen besonders sorgfältig zu sein, denn nur so lassen sich effiziente Suchen ermöglichen.

Erstellen von Indizes

Bei der Erstellung invertierter Indizes müssen wir ein paar Dinge besonders in den Vordergrund stellen: Suchgeschwindigkeit, Indexgröße, Indexierungsgeschwindigkeit und die Dauer, bis neue Änderungen sichtbar werden.

Die Suchgeschwindigkeit und die Indexgröße hängen eng miteinander zusammen. Wenn die Suche nur einen kleinen Index abarbeiten muss, müssen weniger Daten verarbeitet werden und es passen mehr Daten in den Arbeitsspeicher. Wie wir später sehen werden, beeinträchtigen beide Aspekte, besonders aber die Indexgröße, die Indexierungsgeschwindigkeit.

Zur Reduzierung der Indexgröße kommen verschiedene Komprimierungsverfahren zum Einsatz. So arbeitet Lucene beim Speichern der „Postings“ (die recht groß werden können) mit Tricks wie Delta-Verschlüsselung (so wird zum Beispiel [42, 100, 666] als [42, 58, 566] gespeichert), der Verwendung einer variablen Zahl von Bytes (damit kleine Zahlen als einzelnes Byte gespeichert werden können) und so weiter..

Die Aufrechterhaltung kleiner und kompakter Datenstrukturen geht auf Kosten der effizienten Aktualisierbarkeit dieser Strukturen. Lucene verzichtet sogar ganz darauf, sie zu aktualisieren: Die von Lucene geschriebenen Indexdateien sind unveränderlich, das heißt, sie werden niemals aktualisiert. Das unterscheidet sie deutlich von zum Beispiel B‑Bäumen, die aktualisierbar sind und oftmals auch die Möglichkeit bieten, mit einem Füllfaktor anzugeben, wie viel Aktualisierung Sie erwarten.

Es gibt jedoch eine Ausnahme: Löschungen sind möglich. Wenn ein Dokument aus einem Index gelöscht wird, wird das Dokument in einer speziellen Löschdatei entsprechend gekennzeichnet. Bei dieser Datei handelt es sich nur um ein Bitmap, das sich ohne großen Aufwand aktualisieren lässt. Die Indexstrukturen selbst werden nicht aktualisiert.

Daraus ergibt sich, dass beim Aktualisieren eines bereits indexierten Dokuments das Dokument erst gelöscht und dann erneut hinzugefügt wird. Das bedeutet wiederum, dass das Aktualisieren eines Dokuments noch aufwendiger ist als das erstmalige Hinzufügen. Daher ergibt es in aller Regel wenig Sinn, in einem Lucene-Index sich schnell ändernde Zähler und dergleichen zu speichern – die Werte können nicht einfach so aktualisiert werden.

Wenn neue Dokumente hinzukommen (zum Beispiel bei einem Update), werden die Indexänderungen erst im Arbeitsspeicher gespeichert. Anschließend werden die Indexdateien in ihrer Gesamtheit auf den Datenträger geflusht. „Geflusht“ bezieht sich dabei auf das, was bei Lucene unter „Flush“ verstanden wird. Die Elasticsearch-eigene „Flush“-Operation beinhaltet einen Lucene-Commit und mehr und wird im Abschnitt zu den Transaktionslogs näher beschrieben.

Der richtige Flush-Zeitpunkt kann von verschiedenen Faktoren abhängen: wie schnell Änderungen sichtbar sein müssen, wie viel Arbeitsspeicher für das Puffern verfügbar ist, wie es mit der E/A-Sättigung aussieht und so weiter. Für eine möglichst hohe Indexierungsgeschwindigkeit sind im Allgemeinen größere Puffer besser geeignet, solange ihre Größe nicht die E/A-Verarbeitung überfordert. Dazu ein bisschen mehr im nächsten Abschnitt.

Die geschriebenen Dateien bilden ein Indexsegment.

Indexsegmente

Ein Lucene-Index besteht aus einem oder mehreren unveränderlichen Indexsegmenten, die im Grunde genommen jeweils ein „Mini-Index“ sind. Wenn Sie eine Suche starten, geht Lucene jedes Segment durch, filtert alle Löschungen heraus und führt die Ergebnisse aus allen Segmenten zusammen („Merge“). Je mehr Segmente es gibt, desto aufwendiger wird das. Um die Zahl der Segmente im Griff zu behalten, führt Lucene auf der Grundlage bestimmter Zusammenführungsrichtlinien gelegentlich Segmente zusammen. Von Lucene-Hacker Michael McCandless gibt es einen ausgezeichneten Blogpost, in dem er das Zusammenführen von Segmenten erklärt und visualisiert.³ Beim Zusammenführen von Segmenten werden Dokumente, die als gelöscht gekennzeichnet sind, endgültig verworfen. Aus diesem Grund kann das Hinzufügen zusätzlicher Dokumente tatsächlich dazu führen, dass der Index kleiner wird, denn es kann einen Merge-Vorgang auslösen.

Elasticsearch und Lucene schaffen es in der Regel sehr gut zu entscheiden, wann Segmente zusammengeführt werden sollten. Die Elasticsearch-Richtlinien können durch Merge-Einstellungen ergänzt werden. Sie können zum Erzwingen von Merges auch die Optimize API nutzen.

Bevor die Segmente auf den Datenträger geflusht werden, werden die Änderungen im Arbeitsspeicher gepuffert. Früher (vor Lucene 2.3) existierte jedes hinzugefügte Dokument als sein eigenes winziges Segment⁴ und beim Flush wurden alle Dokumente zusammengeführt. Heute gibt es einen DocumentsWriter, der aus einem Dokumentenstapel größere In-Memory-Segmente machen kann. Seit Lucene 4 kann jeder Thread einen davon haben, was ein gleichzeitiges Flushen ermöglicht und so die Indexierungsgeschwindigkeit erhöht. (Davor musste jeweils gewartet werden, bis der gerade laufende Flush beendet ist.)

Die Erstellung neuer Segmente (durch einen Flush- oder einen Merge-Vorgang) führt auch dazu, dass bestimmte Caches ungültig gemacht werden, was sich negativ auf die Performance der Suche auswirken kann. Caches, wie der Feld- und der Filter-Cache, arbeiten segmentweise. Elasticsearch verfügt über eine Warmer-API⁵, mit der die erforderlichen Caches „aufgewärmt“ werden können, bevor das neue Segment für die Suche verfügbar gemacht wird.

Die häufigste Ursache für Flushes bei Elasticsearch dürfte das kontinuierliche Aktualisieren des Index sein – in der Standardeinstellung findet es im Sekundenrhythmus statt. Mit jedem Flush neuer Segmente werden diese für die Suche verfügbar gemacht, was eine (Nahezu-)Echtzeit-Suche ermöglicht. Ein Flush ist zwar nicht so aufwendig wie ein Commit (schließlich muss nicht auf einen bestätigten Schreibvorgang gewartet werden), aber es führt dazu, dass ein neues Segment erstellt wird, was einige Caches ungültig macht und möglicherweise zu einem Merge führt.

Wenn es auf einen möglichst hohen Indexierungsdurchsatz ankommt, zum Beispiel beim Batch-(Re-)Indexieren, ist es produktivitätshemmend, allzu viel Zeit mit Flushes und Merges kleiner Segmente zu verbringen. Stattdessen empfiehlt es sich in solchen Fällen in der Regel, vorübergehend die refresh_interval-Einstellung zu erhöhen oder das automatische Aktualisieren ganz zu deaktivieren. Wenn nötig, kann weiterhin manuell aktualisiert werden, und/oder Refreshes können auf einen Zeitpunkt nach dem Indexieren verschoben werden.

Elasticsearch-Indizes

„Alle Probleme in der Informatik können durch eine andere Indirektionsebene gelöst werden.“ – David J. Wheeler

Ein Elasticsearch-Index besteht aus einer oder mehreren Shards mit null oder mehr Replikas. Diese Indizes sind alle individuelle Lucene-Indizes. Das bedeutet, dass ein Elasticsearch-Index aus vielen Lucene-Indizes besteht, die wiederum aus Indexsegmenten bestehen. Beim Durchsuchen eines Elasticsearch-Index werden alle Shards – und damit alle Segmente – durchsucht und zusammengeführt. Dasselbe gilt, wenn mehrere Elasticsearch-Indizes durchsucht werden. Das Durchsuchen zweier Elasticsearch-Indizes mit je einer Shard unterscheidet sich praktisch nicht vom Durchsuchen nur eines Index mit zwei Shards. In beiden Fällen werden zwei zugrunde liegende Lucene-Indizes durchsucht.

Wenn wir im Weiteren von einem „Index“ reden, meinen wir damit einen Elasticsearch-Index.

Eine „Shard“ ist die kleinste Skalierungseinheit für Elasticsearch. Wenn dem Index Dokumente hinzugefügt werden, werden diese einer Shard zugewiesen. Standardmäßig erfolgt dies im sogenannten Round-Robin-Verfahren auf der Basis des Hash-Werts der ID des Dokuments. Im zweiten Teil dieser Serie werden wir uns genauer ansehen, wie Shards hin und her verschoben werden. Es sei jedoch darauf hingewiesen, dass die Zahl der Shards zum Zeitpunkt der Erstellung des Index festgelegt wird und später nicht mehr geändert werden kann. Eine frühe Präsentation von Elasticsearch durch Shay erklärt ausgezeichnet, warum eine Shard eigentlich ein kompletter Lucene-Index ist und welche Vor- und Nachteile sie gegenüber anderen Methoden hat.

An welche Elasticsearch-Indizes und welche Shards (und Replikas) Suchanfragen gesendet werden, kann auf ganz unterschiedlich angepasst werden. Durch die Kombination von Indexmustern, Indexaliassen und Dokument- und Suchanfragen-Weiterleitung lassen sich viele verschiedene Partitionierungs- und Datenflussstrategien implementieren. Wir werden an dieser Stelle nicht näher darauf eingehen, empfehlen aber Zachary Tongs Artikel zur Anpassung der Dokumentweiterleitung und Shay Banons Präsentation zu Big Data, Suche und Analytics. Um Ihnen ein paar Ideen zu geben, haben wir ein paar Beispiele für Sie zusammengestellt:

• Viele Daten sind zeitbasiert, wie Logs, Tweets und so weiter Wenn wir einen Index pro Tag (oder Woche, Monat, …) erstellen, können wir Suchen effizient auf bestimmte Zeiträume einschränken – und alte Daten löschen. Wie oben erwähnt, gibt es keine effiziente Möglichkeit, Dokumente aus einem bestehenden Index zu löschen, aber es ist problemlos möglich, einen kompletten Index zu löschen.
• Wenn Suchanfragen auf einen bestimmten Nutzer eingeschränkt werden müssen (beispielsweise zum Durchsuchen der eigenen Nachrichten), kann es sinnvoll sein, alle Dokumente für diesen Nutzer an dieselbe Shard zu senden. So wird die Zahl der zu durchsuchenden Indizes reduziert.

Transaktionen

Bei Lucene gibt es Transaktionen – bei Elasticsearch nicht. Alle Operationen in Elasticsearch werden derselben Zeitleiste hinzufügt, was knotenübergreifend nicht immer komplett konsistent ist, da das Flushing auf zeitlichen Abfolgen basiert.

Für ein verteiltes System ist es sehr schwer, die Isolierung und Sichtbarkeit unterschiedlicher Segmente, Caches und so weiter index- und knotenübergreifend zu verwalten. Daher versucht es das erst gar nicht, sondern es konzentriert sich darauf, schnell zu sein.

Elasticsearch verfügt über ein „Transaktionslog“, dem Dokumente angehängt werden, die indexiert werden müssen. Das Anhängen von Dokumenten an ein Log ist wesentlich weniger aufwendig als das Erstellen von Segmenten. So kann Elasticsearch die zu indexierenden Dokumente zusätzlich zum Arbeitsspeicherpuffer, dessen Inhalt bei einem Absturz verloren geht, an einem verlustsicheren Ort aufzeichnen. Zudem kann angegeben werden, mit welchem Konsistenzlevel indexiert werden soll. Es kann beispielsweise festgelegt werden, dass jede Replika das Dokument indexiert haben muss, bevor die Indexieren-Operation beendet wird.

Zusammenfassung

Die wichtigen Eigenschaften, die man kennen sollte, wenn es darum geht, wie Lucene Indizes auf einem einzelnen Knoten erstellt, aktualisiert und durchsucht, lassen sich wie folgt zusammenfassen:

• Die Art und Weise, wie wir den zu indexierenden Text verarbeiten, bestimmt, wie wir ihn durchsuchen können. Wichtig ist, den Text ordnungsgemäß zu analysieren.
• Indizes werden zunächst im Arbeitsspeicher erstellt und anschließend bei Gelegenheit in Segmenten auf den Datenträger geflusht.
• Indexsegmente sind unveränderlich. Gelöschte Dokumente werden als gelöscht gekennzeichnet.
• Ein Index besteht aus mehreren Segmenten. Bei der Suche wird jedes Segment durchsucht und die Ergebnisse werden zusammengeführt.
• Die Segmente werden bei bestimmten Gelegenheiten zusammengeführt.
• Feld- und Filter-Caches funktionieren segmentweise.
• Bei Elasticsearch gibt es keine Transaktionen.

Im nächsten Artikel dieser Reihe werden wir uns das clusterübergreifende Suchen und Indexieren ansehen.