Parallelitätsfehler in Lucene: Wie man optimistische Parallelitätsfehler behebt

Möchten Sie eine Elastic-Zertifizierung erwerben? Erfahren Sie, wann die nächste Elasticsearch-Engineer-Schulung stattfindet! Sie können jetzt eine kostenlose Cloud-Testversion starten oder Elastic auf Ihrem lokalen Rechner testen.

Ja, noch ein Blogbeitrag zur Fehlerbehebung. Doch diese Geschichte hat eine Wendung: Ein Open-Source-Held eilt herbei und rettet die Situation.

Das Debuggen von Parallelitätsfehlern ist kein Zuckerschlecken, aber wir werden uns damit befassen. Hier kommt Fray ins Spiel, ein deterministisches Framework für Parallelitätstests aus dem PASTA Lab der CMU, das unzuverlässige Fehler in zuverlässig reproduzierbare Fehler verwandelt. Dank Frays cleverem Shadow-Lock-Design und präziser Gewindesteuerung konnten wir einen kniffligen Fehler in Lucene aufspüren und ihn schließlich beheben. Dieser Beitrag untersucht, wie Open-Source-Helden und -Tools das Debuggen von Parallelverarbeitung weniger schmerzhaft machen – und die Softwarewelt um einiges besser.

Parallelitätsfehler: Der Fluch von Softwareentwicklern

Parallelitätsfehler sind das Schlimmste. Sie sind nicht nur schwer zu reparieren, sondern es ist schon die größte Herausforderung, sie zuverlässig zum Ausfall zu bringen. Nehmen wir diesen Testfehler, TestIDVersionPostingsFormat#testGlobalVersions, als Beispiel. Es erzeugt mehrere Threads zum Schreiben und Aktualisieren von Dokumenten und stellt damit Lucenes optimistisches Parallelitätsmodell in Frage. Dieser Test deckte eine Race Condition in der optimistischen Parallelitätskontrolle auf. Das heißt, eine Dokumentenoperation kann fälschlicherweise als die letzte in einer Abfolge von Operationen ausgegeben werden 😱. Das bedeutet, dass unter bestimmten Bedingungen eine Aktualisierungs- oder Löschoperation tatsächlich erfolgreich sein kann, obwohl sie aufgrund optimistischer Parallelitätsbeschränkungen eigentlich hätte fehlschlagen müssen.

Entschuldigung an alle, die Java-Stacktraces hassen. Hinweis: Löschen bedeutet nicht unbedingt „löschen“. Es kann auch auf eine Dokumentenaktualisierung hinweisen, da die Segmente von Lucene schreibgeschützt sind.

Apache Lucene verwaltet jeden Thread, der Dokumente schreibt, über die Klasse DocumentsWriter . Diese Klasse erstellt oder verwendet Threads zum Schreiben von Dokumenten wieder, wobei jede Schreibaktion ihre Informationen innerhalb der Klasse DocumentsWriterPerThread (DWPT) steuert. Darüber hinaus verfolgt der Autor, welche Dokumente in DocumentsWriterDeleteQueue (DWDQ) gelöscht werden. Diese Strukturen halten alle Dokumentänderungsaktionen im Speicher und werden periodisch geleert, wodurch Speicherressourcen freigegeben und Strukturen auf der Festplatte gespeichert werden.

Um blockierende Threads zu vermeiden und einen hohen Durchsatz in parallelen Systemen zu gewährleisten, versucht Apache Lucene, nur in sehr kritischen Abschnitten zu synchronisieren . Das kann in der Praxis zwar gut sein, aber wie bei jedem System mit parallelen Prozessen gibt es auch hier Tücken.

Eine falsche Hoffnung

Meine ersten Nachforschungen führten mich zu einigen kritischen Abschnitten, die nicht ordnungsgemäß synchronisiert waren. Alle Interaktionen eines gegebenen DocumentsWriterDeleteQueue werden durch das ihn umschließende DocumentsWriter gesteuert. Während also einzelne Methoden in DocumentsWriterDeleteQueue möglicherweise nicht angemessen synchronisiert sind, ist ihr Zugriff auf die Welt (oder sollte es sein) gewährleistet. (Wir wollen uns nicht näher damit befassen, wie dies die Eigentums- und Zugriffsrechte verkompliziert – es handelt sich um ein langjähriges Projekt, an dem viele Mitwirkende beteiligt sind.) Seid etwas nachsichtiger.)

Ich habe jedoch während eines Spülvorgangs eine Stelle gefunden, die nicht synchronisiert war.

Diese Aktionen werden nicht zu einer einzigen atomaren Operation synchronisiert. Das heißt, zwischen der Erstellung newQueue und dem Aufruf von getMaxSeqNo könnte anderer Code ausgeführt worden sein, der die Sequenznummer in der Klasse documentsWriter inkrementiert. Ich habe den Fehler gefunden!

Doch wie bei den meisten komplexen Fehlern war die Ursachenfindung nicht einfach. Da trat ein Held auf den Plan.

Ein Held im Kampf

Auftritt unseres Helden: Ao Li und seine Kollegen im PASTA-Labor. Ich lasse ihn erklären, wie sie mit Fray die Situation gerettet haben.

Fray ist ein deterministisches Framework für Parallelitätstests, das von Forschern des PASTA Lab an der Carnegie Mellon University entwickelt wurde. Die Motivation für die Entwicklung von Fray liegt in einer deutlich erkennbaren Kluft zwischen Wissenschaft und Industrie: Während deterministisches Concurrency-Testing in der akademischen Forschung seit über 20 Jahren intensiv untersucht wird, verlassen sich Praktiker weiterhin auf Stresstests – eine Methode, die allgemein als unzuverlässig und fehleranfällig gilt – um ihre Concurrency-Programme zu testen. Unser Hauptziel war daher die Entwicklung und Implementierung eines deterministischen Frameworks für Parallelitätstests, bei dem Allgemeingültigkeit und praktische Anwendbarkeit im Vordergrund standen.

Die Kernidee

Im Kern nutzt Fray ein einfaches, aber wirkungsvolles Prinzip: die sequentielle Ausführung. Das Nebenläufigkeitsmodell von Java bietet eine Schlüsseleigenschaft : Wenn ein Programm frei von Datenkonflikten ist, erscheinen alle Ausführungen sequenziell konsistent. Das bedeutet, dass das Verhalten des Programms als eine Folge von Programmanweisungen dargestellt werden kann.

Fray arbeitet, indem es das Zielprogramm sequenziell ausführt: Bei jedem Schritt werden alle Threads außer einem angehalten, wodurch Fray die Thread-Planung präzise steuern kann. Um Parallelität zu simulieren, werden die Threads zufällig ausgewählt, die Auswahl wird jedoch für die spätere deterministische Wiedergabe aufgezeichnet. Um die Ausführung zu optimieren, führt Fray Kontextwechsel nur dann durch, wenn ein Thread im Begriff ist, eine Synchronisierungsanweisung wie Sperren oder atomaren/flüchtigen Zugriff auszuführen. Eine schöne Eigenschaft der Data-Race-Freiheit ist, dass dieser begrenzte Kontextwechsel ausreicht, um alle beobachtbaren Verhaltensweisen aufgrund von Thread-Interleaving zu untersuchen (in unserem Paper findet sich eine Beweisskizze).

Die Herausforderung: die Thread-Planung steuern

Obwohl die Grundidee einfach erscheint, stellte die Implementierung von Fray erhebliche Herausforderungen dar. Um die Thread-Planung zu steuern, muss Fray die Ausführung jedes Anwendungsthreads verwalten. Auf den ersten Blick mag dies unkompliziert erscheinen – die grundlegenden Mechanismen zur Parallelverarbeitung werden einfach durch maßgeschneiderte Implementierungen ersetzt. Die Steuerung der Parallelverarbeitung in der JVM ist jedoch komplex und beinhaltet eine Mischung aus Bytecode-Anweisungen, High-Level-Bibliotheken und nativen Methoden.

Das entpuppte sich als Sackgasse:

• Beispielsweise muss zu jeder MONITORENTER -Anweisung eine entsprechende MONITOREXIT in derselben Methode gehören. Wenn Fray MONITORENTER durch einen Methodenaufruf an einen Stub/Mock ersetzt, muss es auch MONITOREXIT ersetzen.
• In Code, der object.wait/notify verwendet, muss, wenn MONITORENTER ersetzt wird, auch das entsprechende object.wait ersetzt werden. Diese Ersatzkette erstreckt sich bis object.notify und darüber hinaus.
• Die JVM ruft bestimmte Methoden im Zusammenhang mit Parallelität auf (z. B. object.notify , wenn ein Thread beendet wird) innerhalb des nativen Codes. Um diese Operationen zu ersetzen, müsste die JVM selbst modifiziert werden.
• JVM-Funktionen wie Klassenlader und Garbage-Collection-Threads (GC-Threads) nutzen ebenfalls Parallelitätsprimitive. Durch die Modifizierung dieser Grundfunktionen können Inkompatibilitäten mit den entsprechenden JVM-Funktionen entstehen.
• Das Ersetzen von Parallelitätsprimitiven im JDK führt oft zu JVM-Abstürzen während der Initialisierungsphase.

Diese Herausforderungen machten deutlich, dass ein umfassender Ersatz der Parallelverarbeitungsprimitive nicht realisierbar war.

Unsere Lösung: Schattenverriegelungsdesign

Um diese Herausforderungen zu bewältigen, verwendet Fray einen neuartigen Schattensperrmechanismus, um die Thread-Ausführung zu orchestrieren, ohne die Parallelitätsprimitive zu ersetzen. Schattensperren fungieren als Vermittler, die die Thread-Ausführung steuern. Bevor ein Anwendungsthread beispielsweise eine Sperre erwerben kann, muss er mit der entsprechenden Schatten-Sperre interagieren. Die Schattensperre bestimmt, ob der Thread die Sperre erwerben kann. Kann der Thread nicht fortfahren, blockiert die Schattensperre ihn und ermöglicht anderen Threads die Ausführung, wodurch Deadlocks vermieden und eine kontrollierte Parallelität ermöglicht wird. Dieses Design ermöglicht es Fray, die Thread-Verschachtelung transparent zu steuern und gleichzeitig die Korrektheit der Parallelitätssemantik zu erhalten. Jedes Parallelitätsprimitiv wird innerhalb des Shadow-Lock-Frameworks sorgfältig modelliert, um Korrektheit und Vollständigkeit zu gewährleisten. Weitere technische Details finden Sie in unserem Artikel.

Darüber hinaus ist dieses Design zukunftssicher ausgelegt. Da lediglich die Instrumentierung von Schattensperren um Parallelitätsprimitive herum erforderlich ist, wird die Kompatibilität mit neueren JVM-Versionen sichergestellt. Dies ist möglich, da die Schnittstellen der Parallelverarbeitungsprimitive in der JVM relativ stabil sind und seit Jahren unverändert geblieben sind.

Testkampf

Nach der Entwicklung von Fray folgte der nächste Schritt: die Evaluierung. Zum Glück beinhalten viele Anwendungen, wie beispielsweise Apache Lucene, bereits Tests zur Parallelverarbeitung. Bei solchen Parallelitätstests handelt es sich um reguläre JUnit-Tests, die mehrere Threads erzeugen, eine bestimmte Arbeit verrichten, dann (in der Regel) warten, bis diese Threads fertig sind, und dann eine bestimmte Eigenschaft überprüfen. In den meisten Fällen bestehen diese Tests, weil sie nur eine einzige Verschachtelung durchführen. Noch schlimmer ist, dass einige Tests in der CI/CD-Umgebung nur gelegentlich fehlschlagen, wie bereits erwähnt, was die Fehlersuche extrem erschwert. Als wir die gleichen Tests mit Fray durchführten, entdeckten wir zahlreiche Fehler. Besonders bemerkenswert ist, dass Fray zuvor gemeldete Fehler wiederentdeckte, die aufgrund des Fehlens einer zuverlässigen Reproduktion ungelöst geblieben waren, einschließlich des Themas dieses Blogs: TestIDVersionPostingsFormat.testGlobalVersions. Zum Glück können wir mit Fray diese deterministisch wiedergeben und den Entwicklern detaillierte Informationen liefern, sodass sie das Problem zuverlässig reproduzieren und beheben können.

Nächste Schritte für Fray

Wir freuen uns sehr über die Rückmeldung der Entwickler von Elastic, dass Fray bei der Fehlersuche in Parallelverarbeitungsproblemen hilfreich war. Wir werden weiterhin an Fray arbeiten, um es mehr Entwicklern zugänglich zu machen.

Zu unseren kurzfristigen Zielen gehört es, die Fähigkeit von Fray zu verbessern, den Zeitplan deterministisch wiederzugeben, selbst bei Vorhandensein anderer nicht-deterministischer Operationen wie einem Zufallswertgenerator oder der Verwendung von object.hashcode. Wir streben außerdem eine höhere Benutzerfreundlichkeit von Fray an, um Entwicklern die Analyse und das Debuggen bestehender Parallelitätstests ohne manuelle Eingriffe zu ermöglichen. Am wichtigsten ist jedoch, dass wir uns freuen, von Ihnen zu hören, wenn Sie Schwierigkeiten beim Debuggen oder Testen von Parallelitätsproblemen in Ihrem Programm haben. Bitte zögern Sie nicht, ein Problem im Fray GitHub-Repository zu melden.

Es ist an der Zeit, den Parallelitätsfehler zu beheben.

Dank Ao Li und dem PASTA-Labor haben wir nun eine zuverlässig fehlschlagende Instanz dieses Tests! Wir können das Problem endlich lösen. Die Kernfrage bestand darin, wie DocumentsWriterPerThreadPool die Wiederverwendung von Threads und Ressourcen ermöglichte.

Hier können wir sehen, wie jeder Thread erstellt wird, wobei auf die anfängliche Löschwarteschlange in Generation 0 verwiesen wird.

Beim Leeren der Warteschlange erfolgt dann ein Fortschrittsschritt, wobei die vorherigen 7 Aktionen in der Warteschlange korrekt angezeigt werden.

Bevor jedoch alle Threads vollständig verarbeitet werden können, werden zwei für ein zusätzliches Dokument wiederverwendet:

Dadurch wird der Wert seqNo über den angenommenen Maximalwert, der während des Spülvorgangs mit 7 berechnet wurde, erhöht. Beachten Sie die zusätzlichen numDocsInRAM für die Segmente _3 und _0

Dadurch wird die Reihenfolge der Dokumentaktionen während eines Flush-Vorgangs von Lucene falsch berücksichtigt, was zu diesem Testfehler führt.

Wie bei allen guten Bugfixes besteht die eigentliche Korrektur aus etwa 10 Codezeilen. Doch zwei Ingenieure brauchten mehrere Tage, um das herauszufinden:

Nicht alle Helden tragen Umhänge.

Ja, es ist ein Klischee – aber es stimmt.

Das Debuggen von parallelen Programmen ist unglaublich wichtig. Diese kniffligen Parallelitätsfehler erfordern einen unverhältnismäßig hohen Zeitaufwand für die Fehlersuche und -behebung. Während neue Sprachen wie Rust eingebaute Mechanismen zur Vermeidung solcher Race Conditions bieten, ist der Großteil der Software weltweit bereits geschrieben – und zwar in einer anderen Sprache als Rust. Auch nach all den Jahren ist Java immer noch eine der meistgenutzten Programmiersprachen. Eine verbesserte Fehlersuche in JVM-basierten Sprachen macht die Welt der Softwareentwicklung besser. Und angesichts der Tatsache, dass manche Leute glauben, Code werde von großen Sprachmodellen geschrieben, werden unsere Aufgaben als Ingenieure vielleicht irgendwann nur noch darin bestehen, schlechten LLM-Code zu debuggen, anstatt nur unseren eigenen schlechten Code. Doch unabhängig von der Zukunft der Softwareentwicklung wird das Debuggen paralleler Programme für die Wartung und Entwicklung von Software weiterhin von entscheidender Bedeutung sein.

Vielen Dank an Ao Li und seine Kollegen vom PASTA Lab, die das Ganze noch viel besser gemacht haben.

Häufige Fragen