Demnächst in Solr verfügbar: Effiziente Cursor-basierte Iteration

(UPDATE: 2013-12-18 Ich habe unten einige neue Diagramme gepostet, die auf dem überarbeiteten, nicht-strawman, Patch basieren) Eine Sache, bei der…

(UPDATE: 2013-12-18 Ich habe unten einige neue Diagramme gepostet, die auf dem überarbeiteten, nicht-strawman, Patch basieren)

Eine Sache, bei der Solr noch nie sehr effizient war, ist ein Problem, das man als „Deep Paging“ bezeichnet. Einfach ausgedrückt: Solr nach „Seite 1“ eines Suchergebnisses zu fragen, ist sehr effizient, ebenso wie nach Seite 2, Seite 3 usw. für kleine Seitenzahlen zu fragen. Aber wenn die Seitenzahlen größer und größer werden, muss Solr härter arbeiten (und mehr RAM verwenden), um zu wissen, welche Ergebnisse Sie erhalten sollen.

Ich habe an einer Lösung für dieses Problem gearbeitet, aber bevor wir darüber sprechen, lassen Sie uns einen Blick darauf werfen….

Warum ist Deep Paging schwierig?

Um zu verstehen, warum das „Deep Paging“ so viel Arbeitsspeicher und Zeit in Anspruch nimmt, müssen Sie sich vor Augen halten, dass Solr, was Client-Anfragen angeht, im Grunde zustandslos ist. Die Art und Weise, wie ein Client „Seiten“ von Suchergebnissen anfordert, besteht darin, Solr mitzuteilen, wie viele Ergebnisse auf einer Seite angezeigt werden sollen (mit dem Parameter rows ) und an welcher Position in der sortierten Gesamtliste der Dokumente der Client die aktuelle Seite beginnen möchte (mit dem Parameter start ).

Für einen Kunden, der 50 Ergebnisse pro Seite wünscht, wird also Seite 1 über start=0&rows=50 angefordert. Seite #2 ist start=50&rows=50, Seite #3 ist start=100&rows=50, usw…. Damit Solr jedoch weiß, welche 50 Dokumente ab einem beliebigen Punkt N zurückgegeben werden sollen, muss es eine interne Warteschlange der ersten N+50 sortierten Dokumente aufbauen, die der Abfrage entsprechen, so dass es dann die ersten N Dokumente wegwerfen und die restlichen 50 zurückgeben kann. Das bedeutet, dass der für die Rückgabe paginierter Ergebnisse benötigte Speicherplatz linear mit der Erhöhung des start Parameters wächst. Im Fall von SolrCloud wird das Problem sogar noch schlimmer, da die N+50 Top-Dokumente auf jedem Shard gesammelt werden müssen und die Sortierwerte von jedem Shard über das Netzwerk zum Koordinationsknoten gestreamt werden müssen (derjenige, der die ursprüngliche Anfrage vom Endkunden erhalten hat), um sie zusammenzuführen.

Für typische Anwendungen, die einem menschlichen Benutzer Suchergebnisse anzeigen, ist dies in der Regel kein großes Problem, da die meisten Benutzer nicht über die ersten paar Seiten der Suchergebnisse hinausgehen wollen.

Gibt es einen Workaround?

Ein Workaround, der Solr-Kunden schon seit einiger Zeit zur Verfügung steht, um das Abrufen vollständiger Ergebnislisten zu ermöglichen, ist mit einigen Vorbehalten verbunden:

• Die Ergebnisse müssen deterministisch nach Dokumentfeldern sortiert werden – keine Sortierung nach score
  • Kunden können immer noch score unter fl aufrufen, sie können nur nicht nach Punkten sortieren.
• sort muss mindestens ein Feld enthalten, das pro Dokument eindeutig ist – normalerweise nur das Feld uniqueKey
• Alle Felder, nach denen sortiert wird, müssen gespeichert und in die fl

Mit diesen Einschränkungen können Clients dann „Deep Pages“ von Ergebnissen anfordern, indem sie eine fq (Filterabfrage) erstellen, die die Sortierfeldwerte aus dem zuletzt abgerufenen Dokument in Bereichsabfragen verwendet. Betrachten Sie als triviales Beispiel die folgenden Abfrage-Parameter:

q=foo&fl=id,name,score&sort=id asc&start=0&rows=500

Unter der Annahme, dass id für jedes Dokument eindeutig ist, könnte, wenn das letzte von dieser Abfrage zurückgegebene Dokument einen id von AAA123 hat, die nächste „Seite“ oder die nächsten Ergebnisse abgerufen werden, indem die Abfrage so geändert wird, dass sie einen fq im Feld id enthält:

q=foo&fl=id,name,score&sort=id asc&fq=id:{AAA123 TO *]&start=0&rows=500

Der gleiche Prozess kann mit weiteren Sortierungen nach mehreren Feldern verwendet werden, aber die fq, die angegeben werden muss, wird deutlich komplizierter. Wenn Sie zum Beispiel nach price desc, id asc sortieren, müsste der Filter in etwa so aussehen:

fq=(price:[* TO $LAST_DOC_PRICE} (+price:$LAST_DOC_PRICE +id:{$LAST_DOC_ID TO *]))

Das ist zwar für viele Anwendungen machbar, aber für die Clients ist es ziemlich kompliziert, das richtig hinzubekommen. Außerdem ist es für Situationen wie „Ich möchte die obersten 20% der Ergebnisse nach Punkten sortiert verarbeiten“ nicht sehr nützlich, da der Client alle 100% der Ergebnisse abrufen müsste (sortiert nach etwas wie dem uniqueKey) und dann die Sortierung nach Punkten auf dem Client vornehmen müsste, um die 20% mit der höchsten Punktzahl zu finden.

Erstellen wir eine einfachere API

Mit Lucene 4.0 wurde eine neue Methode in Lucene’s IndexSearcher Klasse, die dieselbe Art der oben beschriebenen Filterlogik auf einer viel niedrigeren Ebene implementiert. Der Methodenaufrufer muss sich nur die Informationen in der letzten FieldDoc die von einer früheren Suche zurückgegeben wurde, die bereits alle Sortierwerte für dieses Dokument enthält – einschließlich der Punktzahl (selbst wenn die Sortierfelder nicht gespeichert sind).

In SOLR-5463 habe ich damit begonnen, diese Art von Logik in Solr zu nutzen. Alle Patches, die ich bisher veröffentlicht habe, enthalten eine Strohmann-Implementierung, die versucht, die bestehende Suchlogik in Solr so wenig wie möglich zu verändern, und die daher (noch) keinen Vorteil aus dem bestehenden searchAfter Code auf niedrigerer Ebene zieht. Das Ziel dieser Strohmann-Implementierung ist es, eine gute Test-Suite für die neue Funktionalität aufzubauen und einige der Fragen zu lösen, wie die Client-API aussehen sollte.

Eine bemerkenswerte Frage zur Funktionsweise der Solr-Client-API ist, wie das Konzept der „letzten FieldDoc“ aus der Low-Level-API von Lucene in etwas umgesetzt werden soll, mit dem Solr-Clients problemlos umgehen können. In einer Java-Anwendung, die die IndexSearcher Methoden von Lucene direkt verwendet, ist es kein Problem, ein FieldDoc Objekt aus einer früheren Suche zu behalten, um es in einem späteren Methodenaufruf wieder zu verwenden. In Solr möchten wir jedoch eine API bereitstellen, die es Solr ermöglicht, unabhängig von der Abfolge der Anfragen zu bleiben. In einem Replicated- oder SolrCloud-System kann der Solr-Server, der die Anfrage „Seite #N“ erhält, ein völlig anderer sein als der Server, der „Seite #N-1“ verarbeitet hat. Die bisher entwickelte Lösung besteht darin, dass Solr die Sortierwerte aus dem „letzten“ zurückgegebenen Dokument in einen einzigen Base64 „Cursor-Totem“ (wir arbeiten noch an einem besseren Namen) String kodiert, der an den Client zurückgegeben wird. Die Clients können den Totem-String dann an Solr zurückgeben, um die nächste Seite mit Ergebnissen abzurufen, woraufhin sie einen neuen Totem-String für die nächste Anfrage erhalten usw. ….

Im Wesentlichen kann man sich die klassische Methode des Blätterns durch die Ergebnisse so vorstellen:

while (still want more results) {
  new_page = get(params)
  add new_page to cumulative_results
  params[start] += params[rows]
}

Der neue Cursor-basierte Ansatz ist zwar:

while (still want more results) {
  new_page = get(params)
  add new_page to cumulative_results
  params[totem] = new_page[next totem]
}

Funktioniert es?

Die bisherigen Testergebnisse und Experimente haben gezeigt, dass dieser neue Ansatz definitiv gut funktionieren sollte. Obwohl die Strohmann-Implementierung in mehrfacher Hinsicht extrem ineffizient ist (ich habe bei der Entwicklung Abkürzungen genommen, da ich davon ausgehe, dass ich den Code wegwerfen werde), ist sie dennoch viel schneller und verbraucht viel weniger RAM als die normale Paginierung.

Zur schnellen Demonstration der Leistungsverbesserungen habe ich einige einfache Tests auf meinem Laptop durchgeführt. Dabei habe ich einige synthetische Indizes mit einer Million zufälliger Dokumente erstellt und einige Testskripte verwendet, um die vollständigen Ergebnissätze einiger Abfragen durchzugehen, die mit einer großen Anzahl von Dokumenten übereinstimmten. Ich habe die vollständigen Details der Methodik, einschließlich aller Skripte, auf github zur Verfügung gestellt, aber der grundlegende Prozess in all diesen Tests war:

• Erstellen Sie den Index anhand der Beispielkonfigurationen
• Solr herunterfahren
• Für jedes meiner Testskripte: classic_deep_paging.pl und cursor_deep_paging.pl:
  • Starten Sie Solr und warten Sie, bis firstSearcher warmgelaufen ist.
  • Führen Sie das Skript 3 Mal aus: Jeder Durchlauf erzeugt 2 Dateien: die Zeit pro Seitenanfrage und die zurückgegebenen Docs+Score.
  • Solr herunterfahren
• Vergleichen Sie die von allen 6 Durchläufen zurückgegebenen Dokumente, um die Korrektheit sicherzustellen.
• Führen Sie die 3 Zeitergebnisdateien für jedes Skript zusammen, um den Mittelwert und das stddev zu berechnen.
• Graphen Sie den Mittelwert und die Standardabweichung für jedes Skript

Bevor ich mir die Ergebnisse ansehe, möchte ich Sie an ein paar wichtige Vorbehalte erinnern:

• Ich habe diese Tests auf meinem Laptop durchgeführt, während ich viele andere Aufgaben erledigte
• Während des Tests gab es nur einen Client, der Solr mit Abfragen versorgte. In der realen Welt mit vielen gleichzeitigen Clients würde das klassische „Deep Paging“ in der Regel dazu führen, dass der JVM der Speicher ausgeht, aber mit dem Strohmann-Ansatz sollte der Speicherverbrauch der gleiche sein wie bei einer normalen start=0 Page #1 Anfrage.
• Die Daten in diesen Tests waren zufällig und sehr synthetisch. Sie repräsentieren weder eine typische Begriffsverteilung, die sich auf die Ergebnisse auswirken würde, noch eine typische Verteilung der Sortierwerte, die die allgemeine Sortierleistung in einer realen Anwendung beeinflussen könnte.

Selbst unter Berücksichtigung dieser Faktoren können wir einige ziemlich offensichtliche Muster in den untenstehenden Ergebnissen erkennen. Bitte beachten Sie, dass die Skalen dieser ersten drei Diagramme nicht identisch sind….

Es ist nicht nur der lineare Anstieg der Reaktionszeit bei der klassischen Paginierung offensichtlich, sondern Sie können auch sehen, dass die Steigung dieses linearen Anstiegs stark von der Komplexität der Sortierung abhängt. Ich kann nicht erklären, warum dieses Wachstum abzuflachen scheint – aber an dem Punkt, an dem es abflacht, sind die Antwortzeiten bereits zu extrem, um nützlich zu sein. Bei einer einfachen SolrCloud-Abfrage mit 2 Shards (Test C) steigen die Antwortzeiten sogar bei einer einfachen Sortierung nach Punkten auf über 2 Sekunden an, sobald wir ~40K Dokumente durchblättern. (Aus diesem Grund habe ich für Test C eine Abfrage gewählt, die nur ~150K Gesamtdokumente umfasst – ich wollte nicht den ganzen Tag damit verbringen, den SolrCloud Deep Paging-Test durchzuführen).

Im Vergleich dazu ist der neue cursorbasierte Paging-Ansatz anfangs etwas langsamer in der Antwortzeit pro Seite, bleibt aber relativ konstant. Die Tatsache, dass es bei niedrigen Seitenzahlen langsamer ist als das klassische Paging, ist mit ziemlicher Sicherheit ein Artefakt der Strohmann-Implementierung. Aufgrund einer gewissen Faulheit in meinem Patch sendet es derzeit mindestens doppelt so viele Daten an die Client-Anwendung wie nötig. Die große Abweichung bei den cursorbasierten Antwortzeiten ist zugegebenermaßen überraschend für mich. Ich vermute, dass dies auch ein Artefakt des Strohmann-Codes ist, und ich werde sicherlich darauf achten, sobald der Patch fertiggestellt ist.

Um die Vergleiche zwischen den einzelnen Tests zu erleichtern, habe ich dieselben Daten noch einmal mit festen Skalen auf der X- und Y-Achse in allen drei Diagrammen dargestellt. Auf diese Weise lässt sich leicht erkennen, wie stark sich die Reaktionszeit des klassischen Deep Paging ändern kann, wenn die Sortierung komplizierter wird – im Falle der neuen Cursor-Logik bleibt die Reaktionszeit jedoch konsistent….

Ich denke, es ist ziemlich klar, dass wir auf dem richtigen Weg zu einer viel besseren API für Kunden sind, die große Mengen an Ergebnissen abrufen möchten.

Update: Nicht-Strawman Leistung

Die Arbeit an SOLR-5463 ist weiter vorangeschritten und wir haben jetzt eine Implementierung ohne Strawman, die einige der oben erwähnten Redundanzen vermeidet. Daher wollte ich einige zusätzliche Diagramme veröffentlichen, um den Vergleich zu zeigen.

In diesen Diagrammen unten sind die roten und grünen Linien identisch, wobei grün der frühere, auf dem Strawman basierende Cursor-Code ist – während die neuen blauen Linien die endgültige Lösung zeigen, die wahrscheinlich bald verabschiedet wird.

Hier sehen Sie dieselben Diagramme mit fester Achse, um sie leichter miteinander vergleichen zu können.

Wie Sie sehen können, ist die neue Implementierung eine große Leistungsverbesserung gegenüber der bereits schnellen Strohmann-Implementierung und steht dem klassischen Paging auch bei niedrigen Seitenzahlen in nichts nach.

Appendix: Code & Methodik

Alle Skripte, die zur Durchführung dieser Tests verwendet wurden, finden Sie auf github, einschließlich der Notizen, die ich während der Ausführung gemacht habe und die alle ausgeführten Befehle zeigen.