Entwicklung eines neuen JIT-Compilers für PostgreSQL

 (pinaraf.info)
4 Punkte von GN⁺ 2024-03-20 | 1 Kommentare | Auf WhatsApp teilen
  • Die experimentelle JIT-Engine pg-copyjit zielt darauf ab, auch für kurze PostgreSQL-Abfragen „schnell genug“ erzeugten Code mit geringeren Generierungskosten als LLVM zu liefern
  • Die Kostenschätzung von PostgreSQL entspricht nicht direkt der tatsächlichen Laufzeit, weshalb der aufwendige LLVM-JIT bei kurzen Abfragen sogar nachteilig sein kann
  • Der Copy-and-Patch-Ansatz kompiliert Stencils vorab in C und kopiert bzw. patcht zur Laufzeit die benötigten Fragmente, damit sie wie neue Funktionen ausgeführt werden können
  • pg-copyjit wird über die JIT-Provider-Schnittstelle von PostgreSQL eingebunden und fällt bei nicht implementierten Opcodes automatisch auf den PostgreSQL-Interpreter zurück
  • Aktuell befindet sich das Projekt im Proof-of-Concept-Stadium für PostgreSQL 16 und AMD64; die Codegenerierung liegt bei einigen hundert Mikrosekunden, aber Build, Dokumentation und Support sind noch nicht bereit

Worauf pg-copyjit abzielt

  • pg-copyjit ist eine experimentelle JIT-Engine, die den PostgreSQL-Server schneller machen soll
  • Der aktuelle Code ist eher auf einem Niveau, das für erfahrene Hacker zum Experimentieren geeignet ist, als für Produktionsserver
  • Erwünschtes Feedback sind interessante Experimentergebnisse, Performance-Verbesserungen und Implementierungsideen; ein Stadium, in dem man Ausfallzeiten bei geschäftskritischen Anwendungen in Kauf nimmt, ist es noch nicht

Warum LLVM JIT in PostgreSQL belastend sein kann

  • PostgreSQL hat bereits einen von Andres Freund eingeführten LLVM-basierten JIT-Compiler
  • LLVM kann effizienten Code erzeugen, aber in der Art, wie es in PostgreSQL genutzt wird, sind JIT-Kompilierung und Optimierung teuer
  • Ohne Optimierer kann es schlechter sein als gar nicht zu kompilieren, und mit Optimierer können die Kosten noch weiter steigen
  • Zur Entscheidung, ob JIT angewendet wird, wird die allgemeine query cost estimation verwendet
    • Die Kosten in PostgreSQL sind ein Vergleichswert zwischen Abfragen und stehen nicht für die tatsächliche Ausführungszeit
    • Eine Abfrage mit Kosten 100 kann 1 Sekunde dauern, während eine Abfrage mit Kosten 1000 in 100 ms fertig sein kann
  • Wenn eine Abfrage zwar 10 ms schneller wird, die Optimierung aber 50 ms kostet, ist die Gesamtausführungszeit schlechter
  • Eine Möglichkeit, LLVM JIT nützlicher zu machen, wäre, kompilierte Abfragen zu cachen und wiederzuverwenden, aber die Umsetzung ist kein kleines Vorhaben

Struktur des Copy-and-Patch-Ansatzes

  • Copy-and-Patch ist ein 2021 in einer wissenschaftlichen Arbeit vorgestellter Aufbau für JIT-Compiler und wird auch in der JIT-Engine von Python 3.13 verwendet
  • Die Kerneinheit ist ein in C geschriebener Stencil
    • Ein Stencil ist eine Funktion mit Lücken
    • Er wird vorab mit clang kompiliert
    • Unterstützung für gcc ist vorerst zurückgestellt
  • Zur Kompilierzeit werden die benötigten Stencils aneinandergehängt, die Lücken gefüllt und dann in die neu erzeugte „kompilierte“ Funktion gesprungen
  • Der Grundablauf ist einfach
    • Ein Stencil wird in einen neuen Speicherbereich kopiert
    • Die benötigten Werte werden gepatcht
    • Der resultierende Code wird ausgeführt
  • Es gibt Raum für zusätzliche Optimierungen
    • Werte, die sich schon zur Kompilierzeit berechnen lassen, werden vorab berechnet
    • Schleifen werden zum Unrolling in mehrere Stencils aufgeteilt
    • Mehrere Stencils lassen sich zu einem Meta-Stencil kombinieren, um sie gemeinsam zu optimieren

Wie es an PostgreSQL angebunden wird

  • Das JIT-System von PostgreSQL besitzt eine erweiterbare Provider-Struktur
  • Die .so stellt genau eine Funktion _PG_jit_provider_init bereit, die drei Callbacks initialisiert
    • compile_expr
    • release_context
    • reset_after_error
  • Der wichtigste Callback ist compile_expr
    • Die Eingabe ist ein Ausdruckszeiger ExprState*, der aus Opcodes besteht
    • Die Opcodes werden auf beliebige gewünschte Weise kompiliert
    • Der erzeugte Code wird als ausführbar markiert
    • evalfunc wird vom PostgreSQL-Interpreter auf den erzeugten Code umgestellt
  • Wenn ein nicht implementierter Opcode auftaucht, kann automatisch auf den PostgreSQL-Interpreter zurückgefallen werden

Der Kompilierablauf von pg-copyjit

  • Der Copy-and-Patch-Algorithmus von pg-copyjit ist derzeit noch einfach und enthält nur einige kleine Optimierungen
  • Für jeden Opcode prüft der Compiler eine Stencil-Sammlung
    • Wenn es einen zum Opcode passenden Stencil gibt, wird er an den gerade erzeugten Code angehängt
    • Wenn es keinen Stencil gibt, wird die Kompilierung abgebrochen und der PostgreSQL-Interpreter übernimmt die Ausführung
    • Nachdem der Stencil angehängt wurde, werden alle Lücken mit den benötigten Werten gepatcht
  • Der Stencil für den Opcode CONST deklariert op als externes ExprEvalStep, und in der kompilierten .o-Datei bleibt eine Lücke für die Adresse von op
  • Die Stencil-Sammlung bewahrt diese Relocation-Informationen, und der JIT-Compiler setzt die Adresse der aktuellen Opcode-Struktur ein, um ausführbaren Code zu erzeugen
  • Beim Build werden die Stencils zunächst zu einer einzelnen .o-Datei gebaut; daraus werden anschließend Assemblercode und Relocations extrahiert und in in C verwendbare Strukturen umgewandelt

Implementierungsstand und Performance

  • Anfangs wurde der Assemblercode manuell extrahiert, um die drei für SELECT 42; benötigten Opcodes zum Laufen zu bringen
  • Danach wurde ein DirtyPython-Skript geschrieben, das die Extraktion des Assemblercodes automatisiert, und innerhalb weniger Stunden kamen folgende Funktionen hinzu
    • Funktionsaufrufe
    • Abfragen auf einer einzelnen Tabelle
    • Komplexere Datentypen
    • Einige Optimierungen
  • Der aktuell bestätigte Stand ist wie folgt
    • Funktioniert mit PostgreSQL 16
    • Es wird erwartet, dass es auch mit früheren Releases funktioniert, bestätigt ist aber PostgreSQL 16
    • Unterstützte Architektur ist derzeit nur AMD64
    • Unterstützung für ARM64 soll hinzugefügt werden
    • Ziele wie POWER64 und S390x sind ebenfalls von Interesse, könnten aber Compiler-Patches und Zugriff auf die jeweiligen Maschinen erfordern
  • Die Performance-Zahlen stammen noch aus einem Zustand mit kaum Optimierung
    • Die Codegenerierung ist in einigen hundert Mikrosekunden abgeschlossen
    • Das ist ein Niveau, das auch bei kurzen Abfragen nutzbar ist
    • Bei SELECT 42; braucht No JIT 0,3 ms, copyjit 0,6 ms, LLVM ohne Optimierung 1,6 ms und LLVM mit Optimierung 6,6 ms
  • LLVM kann sehr schnellen Code erzeugen, aber das Ziel von pg-copyjit ist es, schnell hinreichend schnellen Code zu erzeugen; daher ist ein direkter Vergleich der beiden Werkzeuge schwierig
  • Auf einer einfachen nicht indizierten Tabelle mit 90k Zeilen wurden zwei Abfragen benchmarked; wenn eine where-Klausel mit CPU-Arbeit enthalten ist, verbessert sich die Performance gegenüber dem Interpreter
  • Die Benchmarks wurden auf einem Laptop durchgeführt und sind daher nur begrenzt belastbar; künftig sind geeignetere Benchmarks auf einem Desktop geplant
  • Auch mit noch wenigen implementierten Opcodes kann jede Abfrage ausgeführt werden
    • Die JIT-Engine gibt für nicht implementierte Teile Meldungen aus
    • Die eigentliche Ausführung übernimmt der Interpreter

Code-Veröffentlichung und verbleibende Arbeit

  • Der Code ist auf GitHub unter pg-copyjit veröffentlicht
  • Der Fokus liegt derzeit eher auf dem Code selbst als auf bereinigter Git-History oder Dokumentation
  • Zum Bauen muss die Datei build-stencils.sh derzeit zuerst manuell ausgeführt werden
  • Im aktuellen Zustand kann noch kein Support angeboten werden, daher gibt es auch noch keine Dokumentation
  • Die verbleibenden Aufgaben sind vergleichsweise klar
    • Mehr Opcodes implementieren
    • Optimierungen ausloten
    • Den Build-Prozess vereinfachen
    • Alles in einen paketierbaren Zustand bringen
  • Das Build-Skript ist derzeit auf Debian und PostgreSQL 16 zugeschnitten

Erwartete Einsatzgebiete und Architektur-Erweiterung

  • Das Ziel ist, einen Stand zu erreichen, an dem sich das Projekt sicher paketieren und auf dem eigenen Produktionsserver ausrollen lässt
  • Vorgesehen ist auch ein serverweiser Einsatz unterschiedlicher JITs
    • Auf GIS-Servern, wo sich die Optimierungskosten lohnen, könnte LLVM JIT genutzt werden
    • Für Datenbanken von Webanwendungen, bei denen kurze Abfragezeiten wichtig sind, könnte pg-copyjit verwendet werden
  • Auch die Portierung auf andere Architekturen ist ein ernsthaftes Ziel
  • Mit Blick auf die Zeit vieler unterschiedlicher Architekturen wie Alpha, Itanium, Sparc und M68k ist die Haltung, dass man sich nicht an einer Monokultur rund um nur eine Architektur beteiligen möchte

Verwandte Beiträge

1 Kommentare

 
GN⁺ 2024-03-20
Hacker-News-Kommentare
  • Die Methode, den LLVM-JIT-Compiler einfacher nutzbar zu machen, nämlich kompilierte Query-Caches und Wiederverwendung, ist in LLVM tatsächlich schon seit Jahren implementiert :) https://github.com/llvm/llvm-project/commit/a98546ebcd2a692e...
    • Stimmt, ich hätte das klarer sagen sollen, aber das Problem liegt bei PostgreSQL, nicht bei LLVM
      Der JIT-Compiler muss Speicheradressen direkt einbetten, wodurch der erzeugte Code an die jeweilige Query und den jeweiligen Prozess gebunden ist
    • PG verwendet einen Prozess pro Verbindung, und LLVM-JIT-Code ist pro Prozess fixiert, daher können nicht alle Verbindungen der DB denselben Code gemeinsam nutzen
      Ausführungspläne haben dasselbe Problem, weil sie keine Speicherstrukturen sind, die für die gemeinsame Nutzung zwischen verschiedenen Prozessen ausgelegt wurden
      DBs wie MSSQL haben diese Einschränkung nicht, weil sie als Single-Process-Architektur mit Threads arbeiten, und können deshalb auch ohne externen Pooler mehr gleichzeitige Verbindungen verarbeiten
      MSSQL kann Ausführungspläne außerdem in eine nicht an den Prozess gebundene Darstellung serialisieren und in der DB speichern, was sich für Funktionen wie das Fixieren von Ausführungsplänen nutzen lässt
  • Ich bin der Autor. Danke, dass du den Beitrag auf Hacker News gepostet hast, und wenn es Fragen gibt, versuche ich so gut wie möglich zu antworten
    • Ich frage mich, ob es einen grundlegenden Unterschied gibt zwischen copy-and-patch für C als Ziel und dem, was ein Compiler tut, wenn er auf eine Intermediate Representation abzielt
      Herkömmliche Kompilierung wirkt auch wie eine Art „copy-and-patch“ mit einer anderen Zwischensprache statt C
    • Es ist immer schön, Leistungsverbesserungen bei Postgres zu sehen. Mich würde interessieren, wie viel Zeit tatsächlich in LLVM bei realen Queries steckt und wie LLVM konfiguriert ist
      Zum Beispiel, welche Passes und welche Backend-Optimierungen verwendet werden
      Unserer Erfahrung nach [1] kann selbst LLVM deutlich schneller werden, wenn man die Optimierungen deaktiviert und es auf Kompilierzeit mit einer -O0-Backend-Pipeline abstimmt, ist aber immer noch 10- bis 20-mal langsamer als andere Ansätze
      Außerdem ist in unserer Erfahrung der mit copy-and-patch erzeugte Code bei der Ausführung ziemlich langsam und schwer zu optimieren. Wir haben einiges ausprobiert [2; Sec. 5], aber der Abstand ist immer noch groß. Für die Datenbank-Evaluation siehe Fig. 3
      Mich würde interessieren, ob es Zahlen zum Laufzeitverlust gegenüber LLVM gibt und ob geplant ist, einen mehrstufigen JIT zu implementieren, der dynamisch von schnell kompiliertem Code auf LLVM-optimierten Code umschaltet
      [1]: https://home.in.tum.de/~engelke/pubs/2403-cgo.pdf
      [2]: https://home.in.tum.de/~engelke/pubs/2403-cc.pdf
    • Ich frage mich, ob copy-and-patch wirklich eine neue Idee ist oder nur ein neuer Name für eine alte Idee
      Als ich um 2010 Programmierung gelernt habe, besonders Interpreter, hielt ich es für allgemein bekannt, dass man vom Compiler erzeugte Stücke ausführbaren Codes mit memcpy kopieren kann, wenn man vorsichtig vorgeht
      Damals war eine große Falle, dass sich das NX-Bit gerade erst verbreitete. Selbst unter Linux gingen die meisten immer noch selbstverständlich von 32-Bit-Distributionen aus, und manche waren überrascht, dass ihre CPU 64 Bit unterstützt
      Später benutzte ich sogar ein Netbook, das überhaupt keinen 64-Bit-Code unterstützte
      Leider habe ich zu viel Zeit in den Rest des Codes gesteckt, um das tief genug zu verfolgen und etwas wirklich Brauchbares daraus zu machen
    • Das wäre ein sehr gutes Thema für die pgconf.eu im Juni. Die pgcon wurde nach Vancouver verlegt
      Leider ist der Call for Proposals schon vorbei, aber es gibt noch einen „unconference“-Teil. Die Themen werden allerdings erst vor Ort festgelegt, also gibt es keine Garantie
  • Es überrascht mich immer noch, dass PostgreSQL noch keinen Query-/Ausführungsplan-Cache hat
    Wenn es einen Cache gäbe, könnten häufig ausgeführte Queries zwischengespeichert und aggressiver optimiert werden, sodass die Kompilierkosten kompensiert würden und beide Ansätze gut zusammenspielen könnten
    Natürlich würde das für sich genommen eine ganz neue Ebene an Komplexität und Problemen hinzufügen
    • Auch in PG gibt es eine Form von Ausführungsplan-Caching. Bei Prepared Statements verwendet PG einen „generic plan“, wenn es entscheidet, dass die tatsächlichen Parameterwerte keinen großen Einfluss auf den Ausführungsplan haben, und nutzt dann für alle Ausführungen desselben Prepared Statements denselben Plan erneut
      Siehe „notes“ unter https://www.postgresql.org/docs/current/sql-prepare.html
    • Ich dachte anfangs auch so, aber nachdem ich das selbst gebaut habe, verstehe ich, dass es wirklich schwierig wäre
      Stark vereinfacht leaken überall in der Execution Engine Pointer auf Teile der Query
      Um das zu beseitigen, wäre eine ziemlich umfassende Überarbeitung der Execution Engine, des Planners und wohl noch weiterer Teile nötig
      Selbst innerhalb einer einzelnen Session haben zwei kompilierte Queries deshalb unterschiedlichen kompilierten Code. Sowohl LLVM als auch mein copyjit müssen die Adressen mehrerer Strukturen in den Assemblercode einbetten
    • Oracles Ausführungsplan-Cache war früher ziemlich lästig, wenn der Optimizer die Parameter eines Prepared Statements nicht einsehen konnte
      Normalerweise musste man dann selbst eingreifen und Hints hinzufügen oder den Ausführungsplan erzwingen
      Selbst eine einfache Query wie SELECT * FROM t WHERE x = TRUE; konnte je nach Verteilung der x-Werte in der Tabelle zum Albtraum werden
      Mit Postgres hatte ich solche Probleme fast nie, auch wenn ich zugeben muss, dass ich Postgres nie zusammen mit Prepared Statements verwendet habe
      Ich habe zwar Queries gesehen, deren Planung langsam war (über 100 ms), sodass ein Cache nützlich gewesen sein könnte, aber ich erinnere mich an keinen Fall, in dem die Optimierung wirklich zwingend nötig gewesen wäre
  • In der 386-Ära gab es in Assembler das Konzept des selbstmodifizierenden Codes
    Das ist den hier vorgestellten Stencils ähnlich, aber der Code lag meist nur in einer einzigen Instanz vor, daher wurden nur selten Kopien erzeugt
    Zum Beispiel nutzte auch Doom unter DOS solche Optimierungstechniken. Um in engen Rendering-Loops auf alten CPUs genug Leistung herauszuholen, war das nötig