Pengembangan kompiler JIT baru untuk PostgreSQL

 (pinaraf.info)
4 poin oleh GN⁺ 2024-03-20 | 1 komentar | Bagikan ke WhatsApp
  • Mesin JIT eksperimental pg-copyjit berfokus pada pembuatan kode yang “cukup cepat” bahkan untuk kueri PostgreSQL yang pendek, dengan biaya generasi yang lebih rendah dibanding LLVM
  • Estimasi cost PostgreSQL tidak secara langsung selaras dengan waktu eksekusi nyata, sehingga LLVM JIT yang mahal dari sisi optimasi justru bisa merugikan pada kueri pendek
  • Metode copy-and-patch mengompilasi lebih dulu stencil yang dibuat dengan C, lalu saat runtime menyalin dan menambal bagian yang diperlukan agar berjalan seperti fungsi baru
  • pg-copyjit terpasang melalui antarmuka JIT provider PostgreSQL, dan jika menemui opcode yang belum diimplementasikan akan otomatis fallback ke interpreter PostgreSQL
  • Saat ini masih berada pada tahap proof of concept yang berjalan di PostgreSQL 16 dan AMD64; pembuatan kode berada di kisaran ratusan mikrodetik, tetapi build, dokumentasi, dan dukungan masih belum siap

Titik yang dibidik pg-copyjit

  • pg-copyjit adalah mesin JIT eksperimental untuk membuat server PostgreSQL lebih cepat
  • Kode saat ini lebih dekat ke level yang layak diuji oleh peretas spesialis daripada untuk server produksi
  • Umpan balik yang diharapkan adalah hasil eksperimen yang menarik, contoh peningkatan performa, dan ide implementasi; belum pada tahap yang layak mempertaruhkan downtime aplikasi inti bisnis

Mengapa LLVM JIT terasa memberatkan di PostgreSQL

  • PostgreSQL sudah memiliki kompiler JIT berbasis LLVM yang diperkenalkan oleh Andres Freund
  • LLVM dapat menghasilkan kode yang efisien, tetapi dalam cara pemakaiannya di PostgreSQL, biaya kompilasi dan optimasi JIT cukup besar
  • Tanpa optimizer, hasilnya bisa lebih buruk daripada tidak mengompilasi; jika optimizer dipakai, biayanya bisa makin besar
  • Penentuan apakah JIT akan diterapkan memakai estimasi cost kueri umum
    • Cost di PostgreSQL adalah nilai untuk membandingkan kueri satu sama lain, bukan berarti waktu eksekusi nyata
    • Kueri dengan cost 100 bisa memakan 1 detik, sementara kueri dengan cost 1000 bisa selesai dalam 100 ms
  • Jika kueri menjadi 10 ms lebih cepat tetapi optimasinya memakan 50 ms, total waktu eksekusi justru rugi
  • Salah satu cara membuat LLVM JIT lebih berguna adalah menyimpan cache dan menggunakan ulang kueri yang sudah dikompilasi, tetapi implementasinya bukan pekerjaan kecil

Struktur pendekatan copy-and-patch

  • Copy-and-patch adalah metode penyusunan kompiler JIT yang diperkenalkan lewat makalah pada 2021, dan juga dipakai pada mesin JIT Python 3.13
  • Unit intinya adalah stencil yang ditulis dalam C
    • Stencil adalah fungsi yang memiliki lubang
    • Dikompilasi lebih dulu dengan clang
    • Dukungan gcc masih ditunda untuk saat ini
  • Pada waktu kompilasi, stencil yang diperlukan dirangkai, lubangnya diisi, lalu eksekusi melompat ke fungsi “terkompilasi” yang baru dibuat
  • Alur dasarnya sederhana
    • Menyalin stencil ke area memori baru
    • Menambal nilai yang diperlukan
    • Menjalankan kode hasilnya
  • Masih ada ruang untuk optimasi tambahan
    • Nilai yang bisa dihitung saat kompilasi dihitung lebih dulu
    • Loop dipecah menjadi beberapa stencil untuk di-unroll
    • Beberapa stencil dapat digabung untuk membuat meta-stencil yang dioptimalkan sekaligus

Cara memasangnya ke PostgreSQL

  • JIT PostgreSQL memiliki struktur provider yang bisa diperluas
  • Berkas .so menyediakan satu fungsi _PG_jit_provider_init, dan di fungsi ini tiga callback diinisialisasi
    • compile_expr
    • release_context
    • reset_after_error
  • Callback yang paling penting adalah compile_expr
    • Masukannya adalah pointer ekspresi ExprState* yang terdiri dari opcode
    • Opcode dikompilasi dengan cara yang diinginkan
    • Kode yang dihasilkan ditandai agar bisa dieksekusi
    • evalfunc diubah dari interpreter PostgreSQL menjadi kode yang dihasilkan
  • Jika menemui opcode yang belum diimplementasikan, sistem dapat otomatis fallback ke interpreter PostgreSQL

Prosedur kompilasi pg-copyjit

  • Algoritme copy-and-patch milik pg-copyjit saat ini masih berupa bentuk sederhana yang hanya mencakup beberapa optimasi kecil
  • Untuk setiap opcode, kompiler memeriksa koleksi stencil
    • Jika ada stencil untuk opcode tersebut, stencil itu ditempelkan ke kode yang sedang dibangun
    • Jika tidak ada stencil, kompilasi dihentikan dan interpreter PostgreSQL mengambil alih eksekusi
    • Setelah stencil ditempelkan, setiap lubang ditambal dengan nilai yang diperlukan
  • Stencil opcode CONST mendeklarasikan op sebagai ExprEvalStep eksternal, dan di dalam berkas .o hasil kompilasi disisakan lubang untuk alamat op
  • Koleksi stencil mempertahankan informasi relokasi ini, dan kompiler JIT mengisikan alamat struktur opcode saat ini untuk membuat kode yang bisa dieksekusi
  • Alur build dimulai dengan membuat stencil menjadi satu berkas .o, lalu dari sana kode assembly dan relokasinya diekstrak dan diubah menjadi struktur yang bisa dipakai di C

Status implementasi dan performa

  • Pada awalnya, kode assembly diekstrak secara manual untuk membuat 3 opcode yang dibutuhkan oleh SELECT 42; dapat berjalan
  • Setelah itu dibuat skrip DirtyPython untuk mengotomatisasi ekstraksi kode assembly, dan dalam beberapa jam fitur berikut ditambahkan
    • Pemanggilan fungsi
    • Kueri tabel tunggal
    • Tipe data yang lebih kompleks
    • Beberapa optimasi
  • Status yang telah dipastikan saat ini adalah sebagai berikut
    • Berjalan di PostgreSQL 16
    • Diperkirakan juga baik-baik saja pada rilis sebelumnya, tetapi lingkungan yang telah terverifikasi adalah PostgreSQL 16
    • Arsitektur yang didukung baru AMD64
    • Ada rencana menambahkan dukungan ARM64
    • Target seperti POWER64 dan S390x juga menarik, tetapi mungkin memerlukan patch kompiler dan akses ke mesin terkait
  • Angka performa saat ini masih berasal dari kondisi yang nyaris belum dioptimalkan
    • Pembuatan kode selesai dalam ratusan mikrodetik
    • Sudah cukup untuk dipakai bahkan pada kueri pendek
    • Untuk SELECT 42;, tanpa JIT memerlukan 0,3 ms, copyjit 0,6 ms, LLVM tanpa optimasi 1,6 ms, dan LLVM dengan optimasi 6,6 ms
  • LLVM bisa menghasilkan kode yang sangat cepat, tetapi tujuan pg-copyjit adalah membuat kode yang cukup cepat dengan cepat, sehingga sulit membandingkan kedua alat ini secara langsung
  • Dua kueri dibenchmark pada tabel sederhana tanpa indeks berisi 90 ribu baris, dan ketika ada klausa where yang memuat pekerjaan CPU, performanya membaik dibanding interpreter
  • Benchmark dilakukan di laptop sehingga tingkat keandalannya terbatas, dan ke depan akan dilakukan benchmark yang lebih layak di desktop
  • Meskipun opcode yang diimplementasikan masih sedikit, kueri apa pun tetap bisa dijalankan
    • Mesin JIT akan mengeluarkan pesan untuk bagian yang belum diimplementasikan
    • Eksekusi sebenarnya ditangani oleh interpreter

Kode yang dibuka dan pekerjaan yang tersisa

  • Kodenya telah dipublikasikan di GitHub: pg-copyjit
  • Saat ini fokus masih pada kode itu sendiri ketimbang merapikan riwayat git atau dokumentasi
  • Untuk membangun, berkas build-stencils.sh harus dijalankan secara manual terlebih dahulu
  • Dalam kondisi saat ini belum bisa memberikan dukungan, sehingga dokumentasi pun belum disiapkan
  • Pekerjaan yang tersisa relatif jelas
    • Mengimplementasikan lebih banyak opcode
    • Menjelajahi optimasi
    • Meningkatkan kemudahan build
    • Merapikan agar siap dipaketkan
  • Skrip build saat ini dikhususkan untuk Debian dan PostgreSQL 16

Perkiraan penggunaan dan perluasan arsitektur

  • Tujuannya adalah mencapai tingkat yang bisa dipaketkan dengan aman dan dideploy ke server produksi sendiri
  • Ada juga gagasan untuk membagi penggunaan JIT per server
    • Server GIS, tempat kueri layak menanggung biaya optimasi, menggunakan LLVM JIT
    • Basis data aplikasi web, tempat waktu kueri pendek penting, menggunakan pg-copyjit
  • Porting ke arsitektur lain juga merupakan tujuan yang serius
  • Penulis merindukan era beragam arsitektur seperti Alpha, Itanium, Sparc, dan M68k, serta tidak ingin ikut memperkuat masalah monokultur yang berpusat pada satu arsitektur

Bacaan terkait

1 komentar

 
GN⁺ 2024-03-20
Komentar Hacker News
  • Cara untuk membuat kompiler JIT LLVM lebih mudah digunakan, yaitu cache kueri terkompilasi dan penggunaan ulang, sebenarnya sudah diimplementasikan di LLVM sejak bertahun-tahun lalu :) https://github.com/llvm/llvm-project/commit/a98546ebcd2a692e...
    • Betul, saya seharusnya menjelaskannya lebih jelas, tetapi masalahnya ada di sisi PostgreSQL, bukan LLVM
      Kompiler JIT harus menyuntikkan alamat memori secara langsung, sehingga kode yang dihasilkan terikat pada kueri dan proses tersebut
    • PG menggunakan satu proses per koneksi dan kode LLVM JIT tetap per proses, jadi semua koneksi ke DB tidak bisa berbagi kode
      Rencana eksekusi juga mengalami masalah yang sama karena bukan struktur data memori yang dirancang untuk dibagikan antarproses berbeda
      DB seperti MSSQL memakai arsitektur proses tunggal dengan thread, jadi tidak punya masalah ini, dan itu juga salah satu alasan mengapa ia bisa menangani lebih banyak koneksi serentak tanpa pooler eksternal
      MSSQL juga bisa menserialisasi rencana eksekusi ke representasi yang tidak terikat pada proses lalu menyimpannya di DB, sehingga bisa dipakai untuk fitur seperti pembekuan rencana eksekusi
  • Saya penulisnya. Terima kasih sudah memposting ini ke Hacker News, dan kalau ada pertanyaan saya akan berusaha menjawab semampu saya
    • Saya penasaran apakah ada perbedaan mendasar antara copy-and-patch yang menargetkan C dan apa yang dilakukan kompiler saat menargetkan representasi antara
      Cara kompilasi tradisional juga terlihat seperti “copy-and-patch” yang memakai bahasa antara selain C
    • Senang selalu melihat peningkatan performa Postgres. Saya penasaran berapa banyak waktu yang habis di LLVM pada kueri nyata, dan seperti apa konfigurasi LLVM-nya
      Misalnya bagian seperti pass apa yang dipakai dan optimisasi backend apa yang digunakan
      Dalam pengalaman kami [1], LLVM juga bisa dibuat cukup cepat jika optimisasi dimatikan dan disetel agar waktu kompilasinya sesuai dengan pipeline backend -O0, tetapi tetap 10–20x lebih lambat daripada pendekatan lain
      Kami juga punya pengalaman bahwa kode yang dihasilkan lewat copy-and-patch cukup lambat saat dijalankan dan sulit dioptimalkan. Kami sudah mencoba beberapa hal [2; Sec. 5], tetapi jaraknya masih besar. Lihat Fig. 3 untuk hasil evaluasi basis data
      Saya juga penasaran apakah ada angka penurunan waktu eksekusi dibanding LLVM, dan apakah ada rencana menerapkan JIT bertingkat yang secara dinamis beralih dari kode yang dikompilasi cepat ke kode LLVM yang sudah dioptimalkan
      [1]: https://home.in.tum.de/~engelke/pubs/2403-cgo.pdf
      [2]: https://home.in.tum.de/~engelke/pubs/2403-cc.pdf
    • Saya penasaran apakah copy-and-patch benar-benar ide baru, atau hanya ide lama dengan nama baru
      Saat belajar pemrograman sekitar 2010, khususnya interpreter, saya mengira sudah umum diketahui bahwa jika dipakai dengan hati-hati, potongan kode eksekusi yang dibuat kompiler bisa disalin dengan memcpy
      Jebakan besarnya saat itu adalah bit NX baru mulai tersebar luas. Bahkan di Linux, kebanyakan orang masih menganggap distribusi 32-bit sebagai hal yang wajar, dan ada juga yang kaget saat tahu CPU mereka mendukung 64-bit
      Belakangan saya bahkan memakai netbook yang sama sekali tidak mendukung kode 64-bit
      Sayangnya, saya terlalu banyak menghabiskan waktu untuk sisa kode lainnya, jadi tidak pernah cukup mendalaminya untuk membuat sesuatu yang benar-benar berguna
    • Ini tampaknya topik yang sangat bagus untuk dibahas di pgconf.eu pada bulan Juni. pgcon sudah dipindahkan ke Vancouver
      Sayangnya, pengumpulan proposal presentasi sudah ditutup, tetapi masih ada bagian “unconference”. Hanya saja topiknya ditentukan di lokasi acara, jadi tidak ada jaminan
  • Saya masih heran PostgreSQL belum punya cache kueri/rencana eksekusi
    Kalau ada cache, kueri yang sering dijalankan bisa di-cache dan dioptimalkan lebih agresif, sehingga dua pendekatan ini tampaknya bisa saling melengkapi untuk menutup biaya kompilasi
    Tentu saja, itu sendiri akan menambahkan lapisan kompleksitas dan sumber sakit kepala yang benar-benar baru
    • PG memang punya satu bentuk caching rencana eksekusi. Dalam prepared statement, jika PG menilai bahwa nilai parameter aktual tidak banyak memengaruhi rencana eksekusi, PG akan memakai “generic plan” sehingga rencana eksekusi yang sama dipakai ulang untuk semua eksekusi prepared statement yang sama
      Lihat bagian “notes” di https://www.postgresql.org/docs/current/sql-prepare.html
    • Saya juga awalnya berpikir begitu, tetapi setelah mencoba membuatnya sendiri, saya jadi paham bahwa ini akan benar-benar sulit
      Jika sangat disederhanakan, ada pointer yang menunjuk ke bagian-bagian kueri yang bocor ke berbagai tempat di mesin eksekusi
      Untuk menghilangkannya, dibutuhkan perombakan besar yang cukup menyeluruh, mencakup mesin eksekusi, planner, dan entah apa lagi
      Bahkan dalam satu sesi tunggal pun, dua kueri yang dikompilasi akan punya kode kompilasi yang berbeda karena hal ini. Baik LLVM maupun copyjit buatan saya harus menyuntikkan alamat beberapa struct ke dalam kode assembly
    • Cache rencana eksekusi Oracle dulu cukup merepotkan ketika optimizer tidak bisa melihat parameter dalam prepared statement
      Biasanya kita harus masuk langsung dan menambahkan hint atau memaksa rencana eksekusi
      Bahkan kueri sederhana seperti SELECT * FROM t WHERE x = TRUE; bisa menjadi mimpi buruk tergantung distribusi nilai x di tabel
      Di Postgres saya hampir tidak pernah mengalami masalah seperti itu, walaupun saya akui belum pernah memakai Postgres bersama prepared statement
      Saya pernah melihat kueri dengan waktu perencanaan lambat (lebih dari 100 ms), jadi cache mungkin akan berguna, tetapi saya tidak ingat pernah ada kasus yang benar-benar membutuhkan optimisasi itu
  • Pada era 386, ada konsep self-modifying code di assembly
    Mirip dengan stencil yang diajukan di sini, tetapi biasanya kodenya berupa satu instans tunggal, jadi jarang membuat salinannya
    Misalnya Doom di DOS juga memakai teknik optimisasi seperti ini. Ini diperlukan untuk benar-benar mengeluarkan performa dari loop rendering yang ketat di CPU lama