Mencari SQLite yang Lebih Cepat

• Saat menjalankan banyak instance SQLite bersama-sama di lingkungan serverless dan edge, menunggu I/O sinkron memperbesar tail latency, dan peneliti dari Helsinki serta Cambridge bereksperimen dengan cara menguranginya lewat I/O asinkron dan pemisahan storage
• io_uring di Linux memungkinkan aplikasi tetap menjalankan pekerjaan lain selama permintaan I/O berlangsung melalui submission queue dan completion queue, menjadi dasar untuk mengurangi pemblokiran thread
• Saat menjalankan sqlite3_step(), jika halaman B-Tree yang dibutuhkan tidak ada di cache, SQLite membaca disk dengan I/O sinkron seperti POSIX read(), sehingga thread berhenti sampai I/O selesai
• Para peneliti tidak sekadar mengganti pemanggilan POSIX, tetapi mengubah VM dan BTree dalam proyek penulisan ulang berbasis Rust, Limbo, agar sesuai dengan model eksekusi asinkron
• Dalam benchmark, p999 tail latency turun hingga 100x, tetapi p90 dan p99 hampir sama dengan SQLite, dan evaluasi multi-reader/writer masih menjadi pekerjaan berikutnya

---

Riset untuk membuat SQLite lebih cepat

• Peneliti dari University of Helsinki dan Cambridge membahas cara menerapkan I/O asinkron dan pemisahan storage pada SQLite dalam “Serverless Runtime / Database Co-Design With Asynchronous I/O”
• Makalah ini menjadi dasar bagi Limbo, proyek penulisan ulang SQLite berbasis Rust
• Karena merupakan makalah workshop, panjangnya singkat, dengan fokus pada serverless dan edge computing
• Intinya, meski SQLite sendiri sudah cepat, tail latency di lingkungan multi-tenant masih bisa dikurangi lebih jauh dengan mengubah model eksekusinya

Penantian I/O yang dikurangi oleh io_uring

• io_uring pada kernel Linux menyediakan antarmuka I/O asinkron
• Namanya berasal dari ring buffer yang dibagi antara user space dan kernel space, yang mengurangi overhead penyalinan buffer di antara kedua ruang tersebut
• Setelah mengirim permintaan I/O, aplikasi dapat menjalankan pekerjaan lain secara paralel hingga OS memberi tahu bahwa operasi selesai
• Alur kerjanya sebagai berikut
  • System call io_uring_setup() menyiapkan dua area memori: submission queue dan completion queue
  • Aplikasi memasukkan permintaan I/O ke submission queue dan memberi tahu OS dengan io_uring_enter() untuk mulai memprosesnya
  • Tidak seperti read() dan write(), kontrol dikembalikan ke user space tanpa memblokir thread
  • Aplikasi melakukan pekerjaan lain, lalu secara berkala melakukan polling pada completion queue untuk memeriksa selesainya I/O

Bottleneck I/O sinkron dalam eksekusi kueri SQLite

• Aplikasi SQLite membuka file database dengan sqlite3_open(), dan dalam proses ini dipanggil I/O OS level rendah seperti POSIX open
• sqlite3_prepare() mengubah pernyataan SQL seperti SELECT dan INSERT menjadi rangkaian instruksi bytecode
• sqlite3_step() mengeksekusi instruksi bytecode hingga menghasilkan baris yang akan dibaca kueri atau hingga eksekusi selesai
  • Jika ada baris yang bisa dibaca, ia mengembalikan SQLITE_ROW
  • Jika pernyataan selesai, ia mengembalikan SQLITE_DONE
• Selama eksekusi, pager backend dipanggil dan B-Tree yang merepresentasikan tabel serta baris ditelusuri
• Jika halaman B-Tree yang dibutuhkan tidak ada di cache halaman SQLite, akses disk terjadi
  • SQLite membaca isi halaman dari disk ke memori dengan I/O sinkron seperti POSIX read
  • Selama itu, sqlite3_step() memblokir thread kernel
  • Agar tetap dapat melakukan pekerjaan bersamaan saat menunggu I/O, aplikasi harus memakai lebih banyak thread

Alasan ingin menyematkan SQL di serverless dan edge

• Jika serverless computing berjalan di edge sementara database berada di lingkungan cloud, muncul biaya round-trip jaringan antara fungsi serverless dan cloud
• Data juga bisa ditempatkan bersama di edge, tetapi pendekatan yang diajukan sebagai opsi lebih baik adalah menyematkan database di dalam runtime edge
• Cloudflare Workers sudah mencapai bentuk seperti ini, tetapi mengekspos antarmuka KV
• KV tidak cocok untuk semua area masalah
  • Memetakan data berbentuk tabel ke model KV membuat pengalaman developer memburuk
  • Ada pula biaya serialisasi dan deserialisasi
• SQL bisa lebih sesuai, dan karena SQLite adalah database embedded, ia dapat dimasukkan langsung ke runtime serverless

Mengapa sulit sekadar mengganti SQLite dengan io_uring

• SQLite menggunakan I/O sinkron berbasis POSIX read() dan write() tradisional
• Meski tidak menjadi masalah besar pada aplikasi kecil, menjalankan ratusan database SQLite di satu server dapat menjadi bottleneck
• Di lingkungan yang harus memaksimalkan tingkat pemakaian resource server, I/O sinkron menjadi kendala
• SQLite memiliki masalah concurrency dan multi-tenancy
  • Karena I/O bersifat sinkron dan memblokir, aplikasi-aplikasi di mesin yang sama berebut resource
  • Akibatnya, latency meningkat
• Sulit untuk sekadar mengganti pemanggilan POSIX I/O dengan io_uring
  • Aplikasi yang memakai blocking I/O harus dirancang ulang agar sesuai dengan model I/O asinkron io_uring
  • Library SQLite harus mampu mengembalikan kontrol ke aplikasi saat I/O sedang berlangsung
• Alih-alih hanya mengubah sebagian pemanggilan SQLite, para peneliti memilih pendekatan menulis ulang SQLite dalam Rust dan menggunakan io_uring

Model eksekusi asinkron Limbo

• Limbo adalah proyek penulisan ulang SQLite dalam Rust, dan komponen VM serta BTree diubah agar mendukung I/O asinkron
• Instruksi bytecode sinkron diganti dengan instruksi padanan asinkron
• Misalnya, instruksi Next memajukan cursor dan mengambil halaman berikutnya jika perlu
  • Pada versi sinkron yang lama, jika terjadi I/O disk, eksekusi akan diblokir sampai halaman dibaca dan dikembalikan ke pemanggil
  • Pada versi asinkron, NextAsync langsung kembali setelah dikirimkan
  • Setelah itu, pemanggil dapat memblokir atau melakukan pekerjaan lain
• I/O asinkron menghilangkan pemblokiran dan meningkatkan concurrency
• Untuk meningkatkan pemakaian resource lebih jauh, juga diusulkan pemisahan storage yang memisahkan query engine dan storage engine
• Sebagai penjelasan terkait, Disaggregated Storage - a brief introduction juga ditautkan

Hasil benchmark dan pertanyaan yang tersisa

• Benchmark mensimulasikan runtime serverless multi-tenant
• Setiap tenant memiliki database embedded miliknya sendiri
• Jumlah tenant diubah dari 1 hingga 100 dengan interval 10
• SQLite menggunakan thread terpisah untuk setiap tenant, dan pengukuran dilakukan dengan menjalankan kueri di tiap thread
• Kueri yang dijalankan adalah SELECT * FROM users LIMIT 100 dan diulang 1000 kali
• Limbo juga menjalankan eksperimen yang sama, tetapi menggunakan coroutine Rust
• Hasilnya, tail latency pada p999 turun hingga 100x
• Latency kueri SQLite tidak memburuk secara bertahap seiring bertambahnya jumlah thread
• Pekerjaan ini masih berlangsung, dan makalahnya menyisakan beberapa pertanyaan terbuka
  • Future Work membahas benchmark tambahan yang mencakup beberapa reader dan writer
  • Manfaatnya baru terlihat jelas setelah p999
  • Kinerja p90 dan p99 hampir sama dengan SQLite
• Kode Limbo tersedia sebagai open source
• Limbo saat ini merupakan proyek resmi Turso, dan artikel perkenalannya juga telah dipublikasikan