Membuat mesin Datalog interaktif di Rust

• Menggabungkan pemrograman logika Datalog dengan efisiensi Rust, dan membagikan secara rinci proses pengembangan mesin Datalog interaktif yang sederhana, mudah digunakan, sekaligus mempertimbangkan performa
• Dalam lingkungan CLI yang intuitif, rule dan fact dapat ditambahkan/diperluas secara real-time, sekaligus merasakan pemuatan data dalam jumlah besar, input rule dinamis, dan performa kueri yang cepat
• Parsing, representasi data, dan evaluasi rule (Planning/Evaluation) dijelaskan langkah demi langkah bersama kode Rust sehingga pembaca dapat mempelajari cara implementasinya secara nyata
• Dimulai dari implementasi sederhana yang belum dioptimalkan lalu secara bertahap meningkatkan performa dan strukturnya, sehingga logika lanjutan seperti pemrosesan paralel data dan optimasi join juga bisa dipelajari
• Menjalankan langsung contoh analisis program berbasis dataset besar (Nullability, Aliasing, dll.), sambil membagikan wawasan tentang performa, isu memori, optimasi kueri, dan peningkatan join-plan

---

Pendahuluan: bereksperimen dengan pemrograman logika Datalog di Rust

• Selama periode Memorial Day, dilakukan berbagai praktik dan diskusi tentang pemrograman logika seperti Datalog di konferensi Minnowbrook
• Ditemukan keterbatasan pada alat Datalog yang ada (Soufflé, ctdal, dll.) dari sisi penggunaan nyata, ekstensibilitas, dan performa, sehingga kebutuhan akan alat yang lebih praktis menjadi menonjol
• Penulis memutuskan untuk mengimplementasikan sendiri interpreter Datalog (datatoad) di Rust yang memenuhi kesederhanaan, kemudahan penggunaan, dan performa sekaligus
• Tujuan proyek: memuat data berukuran besar dengan cepat dari CLI, menambah/mengubah rule secara dinamis, melihat hasil secara real-time, dan tetap mendapatkan performa kueri yang baik

Konsep dasar Datalog

• Datalog adalah sistem yang secara otomatis menurunkan semua fakta yang dapat disimpulkan dari fact dan rule yang diberikan, berdasarkan pernyataan logika berbentuk rule (Head :- Body)
• Rule (contoh: tri(a, b, c) :- edge(a, b), edge(b, c), edge(a, c)) tersusun dari variabel dan literal
• Fact adalah nilai yang benar tanpa syarat (contoh: edge(1, 2) :- .)
• Kekuatan Datalog: saat rule ditambahkan, himpunan informasi yang dapat diinferensikan bertambah (monotonisitas), dan hasil yang diperoleh tetap sama terlepas dari urutan rule/fact (konvergensi)
• Di Rust, rule dan fact direpresentasikan dengan struct Atom/Rule/Term, dan himpunan fact dikelola per relation

Desain struktur inti

Representasi data

• Fact awalnya dirancang sebagai Vec<String>, dan himpunan fact sebagai BTreeMap<String, Vec<Fact>> dan sejenisnya
• Untuk mengoptimalkan data berukuran besar, diperkenalkan struktur data columnar guna meminimalkan alloc overhead
• FactContainer: himpunan fact yang sudah diurutkan/dideduplikasi, dengan struktur append-only
• FactLSM: pendekatan LSM (Log-structured merge-tree) yang mengelola FactContainer dalam beberapa lapisan untuk mengefisienkan penyisipan serta pengurutan/penggabungan
• FactSet: mengelola lifecycle fact (baru ditambahkan, baru diturunkan, fact yang sudah stabil) untuk mencegah perhitungan duplikat dan pemborosan memori yang tidak perlu

Penerapan rule dan inferensi

• Setiap rule menghasilkan JoinPlan, lalu melakukan inferensi dengan metode merge join berdasarkan urutan kolom dan kombinasi key yang sesuai
• Merge join: setelah kolom key pada tiap body atom diurutkan, fact baru hanya diturunkan ketika key join cocok, untuk memaksimalkan performa
• Dengan memanfaatkan struktur stable/recent/to_add pada FactSet, fact yang sudah diturunkan dan fact baru dipisahkan untuk mencegah komputasi ulang yang tidak perlu (evaluasi diferensial)
• Loop .update(): semua rule diterapkan berulang sampai tidak ada lagi fact baru yang diturunkan, dan inferensi diulang hingga mencapai fixpoint

Implementasi parser

• Mendukung sintaks bergaya Soufflé (?var, :-, ., ,, dll.), dengan tokenizer/parser yang ditulis langsung di Rust
• Saat terjadi error, parser dengan aman mengembalikan None, sebagai desain parser sederhana yang cocok untuk lingkungan eksperimental

Optimasi performa dan contoh analisis nyata

Analisis Nullability (Reachability)

• Pada dataset besar (misalnya httpd_df), didefinisikan rule Datalog untuk melacak jalur penyalinan/perpindahan nilai dan diukur performanya
• Perbedaan performa bisa sangat besar tergantung pola penulisan rule (binding variabel/urutan kolom/kemunculan relation sementara berdasarkan join plan, dll.)
• Bergantung pada bentuk awal data dan strategi join, waktu eksekusi serta penggunaan memori dapat berbeda hingga puluhan kali lipat, sehingga pentingnya optimasi kueri dapat dirasakan langsung
• Setelah optimasi diterapkan, terkonfirmasi peningkatan performa 10 hingga lebih dari 80 kali dibanding alat berbasis C++ yang ada (seperti Graspan)

Analisis Aliasing (Points-to)

• Mengimplementasikan pola Datalog yang kompleks untuk analisis aliasing/pelacakan pointer, dan menjalankan kueri yang sama seperti pada makalah (Graspan, Zheng-Rugina, dll.)
• Operasi iterasi (^*), opsional (^?), dan transpose (^T) dalam rule Datalog diperluas menjadi rekursi/union eksplisit
• Bergantung pada desain penamaan/penggunaan ulang hasil antara (relation alias, temp join, dll.), efisiensi dan konsumsi sumber daya seluruh query plan dapat sangat berbeda
• Jika hasil antara yang besar dibuat tanpa optimasi query plan, performa akan menurun dan penggunaan memori bisa melonjak drastis (contoh: relation V)
• Dibahas pendekatan "demand-driven" (transformasi magic set) yang hanya menghasilkan hasil yang diperlukan, serta ditunjukkan kemungkinan perubahan query plan dan peningkatan performa nyata

Pelajaran yang didapat dari eksperimen langsung di Rust

• Kunci performa mesin Datalog ada pada representasi data (columnar/LSM), inferensi diferensial, dan optimasi join plan
• Jika rule hanya ditulis secara mekanis, hal itu dapat menyebabkan pembentukan data antara yang tidak perlu dan pemborosan sumber daya, sehingga optimasi menjadi penting
• Melalui eksperimen langsung di Rust, fact dengan ratusan juta hingga puluhan juta row pada dataset nyata dapat dikelola secara efisien, sambil mencapai skalabilitas dan kecepatan inferensi sekaligus
• Dalam lingkungan CLI, eksperimen seperti memuat data besar, menambahkan rule secara real-time, dan memeriksa hasil dapat dilakukan dengan mudah
• Peran query optimizer, bushy-tree join (memanfaatkan hasil antara), dan kebiasaan menghindari pembuatan relation yang tidak diperlukan memberi banyak implikasi praktis untuk penulisan dan operasional Datalog

Tugas pengembangan selanjutnya

• Masih ada topik penelitian yang tersisa seperti disk spill, ekspansi terdistribusi multi-worker/proses, streaming join, dan optimasi kompilasi kustom
• Rust Datalog memiliki potensi pemanfaatan tinggi di bidang nyata seperti analisis program skala besar, inferensi graf/relasional, analisis statis, dan pelacakan aliran data

[GN⁺]

Komentar Hacker News

• Lucu juga melihat tulisan ini sedang muncul di bagian atas; saya sedang mengerjakan game strategi real-time menggunakan Differential Datalog(repositori ini) dan Rust. Strukturnya DDL menangani logika game, dan tujuannya adalah mempelajari ide-ide baru sambil mengumpulkan berbagai pengalaman trial-and-error.
  • Saya menantikan perkembangan proyek ini; hasil akhirnya jadi sangat bikin penasaran.
  • Karena pengembangan Differential Datalog saat ini tidak aktif, saya penasaran sejauh mana implementasinya memungkinkan dan seberapa matang kondisinya sekarang.
• Saya sempat membuat sedikit kemajuan saat mencoba mem-porting mangle datalog ke Rust. Implementasi Rust-nya bisa dilihat di sini, dan versi golang ada di repositori yang sama. Alasannya lambat bukan cuma karena prioritasnya rendah, tapi juga karena fenomena "second system syndrome" (saat sistem kedua jadi lebih lambat dikerjakan karena ambisinya membesar dibanding yang pertama). Versi Rust dari mangle bisa membaca dan menulis data ke disk kapan saja lewat memory mapping, jadi cocok untuk data berukuran besar. Versi golang memproses semuanya dengan memuat seluruh data ke memori. Hal yang bagus dari tulisan ini adalah susunan parser datalog-nya dijelaskan dengan baik, ada penyebutan LSM tree sehingga mudah dipahami, dan jauh lebih mudah diikuti dibanding data frog. Di Rust juga ada berbagai implementasi datalog seperti ascent dan crepe yang memanfaatkan proc-macros, tetapi ada keterbatasan untuk menangani kueri secara dinamis saat runtime. Kalau kasusnya analisis statis dengan kueri dan program yang tetap, pendekatan proc macro menurut saya juga sangat bagus.
• Menyenangkan melihat sebagian penggemar datalog tetap rutin berkumpul dan aktif. Belakangan suasana "renaissance datalog" terasa agak melambat; konferensi Datalog 2.0 juga lebih kecil daripada sebelumnya, dan pada HYTRADBOI edisi kedua diskusi terkait datalog sendiri jauh berkurang. Saya ingat pada pertemuan pertama sekitar seperempat makalahnya berkaitan dengan datalog. Mendengar peserta lain berbagi pengalaman proyek datalog terbaru benar-benar memberi semangat. Akhir-akhir ini saya sedang menyiapkan migrasi perangkat lunak skala besar dari database SQL lama dan membangun pipeline kualitas data. Kalau kueri datalog disusun dengan baik, keterbacaannya tinggi, jadi menurut saya itu alat yang jauh lebih efisien daripada SQL untuk menelusuri masalah kualitas data.
  • Menurut saya, sedikitnya peserta di konferensi Datalog 2.0 lebih dipengaruhi struktur acaranya daripada kemunduran datalog itu sendiri. Datalog 2.0 adalah acara satelit dari konferensi Eropa yang kurang dikenal bernama LPNMR, dan kali ini diadakan agak random di Dallas, AS. Saya juga mengirim makalah ke Datalog 2.0, tetapi penulis utamanya orang lain, dan pada praktiknya tidak banyak orang yang benar-benar bekerja di bidang datalog ikut hadir. Peserta dari Eropa yang mempresentasikan Nemo solver cukup menonjol. Intinya, sedikitnya peserta tahun ini lebih karena sifat khusus acara tersebut sebagai event satelit, dan saya setuju bahwa dalam implementasi engine datalog sendiri mungkin memang tidak banyak terobosan besar yang tersisa. Arus riset saat ini berkembang ke topik yang lebih menarik daripada datalog dasar, seperti stream-based (HydroFlow), choice (Dusa), dan chase engine (Egglog). Monotonic, chain-forward saturation (Horn clauses) sudah cukup mapan dari sisi engineering, sehingga sekarang eksplorasi teori baru seperti semirings dan Z-sets berkembang di atas fondasi itu.
• Saya rasa penulis sangat piawai dalam pekerjaan terkait datalog, tetapi cara mengajarkan binary join di bagian awal terasa kurang ideal karena di luar kasus yang sederhana, kompleksitasnya cepat meningkat. Menurut saya pendekatan keluarga generic join lebih intuitif untuk digeneralisasi. Disarankan melihat penjelasan wiki tentang worst-case optimal join algorithm.
  • Terkait hal itu, di tulisan blog McSherry sebelumnya juga bisa dilihat bagaimana ia membuktikan bahwa binary join dapat mencapai runtime worst-case optimal melalui penyesuaian query plan yang tepat. Lihat postingan blog.
• Di pembukaan postingan blog itu, kalimat "I, a notorious villain, was invited for what I was half sure was my long-due comeuppance." adalah bagian yang paling berkesan; menurut saya itu pembuka tulisan blog teknis terbaik tahun ini. Sepanjang tulisan, gaya penulisannya yang jenaka sangat menonjol, dan jarang ada tulisan yang bisa membuat topik teknis sedalam ini terasa menyenangkan dibaca. Perjalanan optimasi kueri aliasing disusun menarik seperti novel detektif. Saat ia frustrasi dengan penggunaan memori 50GB lalu berhasil mengoptimalkannya menjadi 5GB, rasanya pembaca ikut bersorak. Kode maupun kualitas tulisannya sama-sama luar biasa.
• Dulu saya pernah mendengar beberapa penggemar Clojure yakin bahwa datalog lebih unggul daripada SQL, dan menyayangkan bahwa database relasional semuanya hanya mendukung SQL. Saya sendiri belum pernah benar-benar menggali alasan mereka berpikir begitu.
  • Dialek datalog dari Clojure atau Datomic memang tidak terlalu akrab bagi saya, tetapi saya cukup sejalan dengan datalog itu sendiri. Saya merekomendasikan Percival untuk mencoba datalog di lingkungan notebook online: percival.ink. Begitu memahami konsep inti datalog, berpindah antarimplementasi terasa cukup mudah. Saya juga pernah mem-fork Percival dan membuat versi yang mengompilasi datalog ke SQLite; versi fork itu masih belum lengkap untuk fungsi agregasi dan advanced join, tetapi kueri dasarnya berjalan baik. Logica adalah compiler datalog->SQL yang jauh lebih serius dan matang, dibuat oleh peneliti Google, dengan dukungan berbagai dialek SQL seperti BigTable dan DuckDB; lihat Logica. Saat menangani kueri atau aturan rekursif, datalog terasa jauh lebih mudah. Di SQL hal itu memang bisa dilakukan, tetapi rasanya seperti minum tanah liat lewat sedotan. Materialize.com buatan Frank McSherry menyediakan bentuk SQL “WITH MUTUALLY RECURSIVE”; lihat blog Materialize. Saya sedang mempertimbangkan pemakaiannya untuk kueri pemuatan halaman dan sinkronisasi data di Notion. Feldera juga punya bentuk serupa untuk recursive view; lihat postingan blog Feldera. Kelebihan Feldera adalah setiap “aturan” atau subview bisa ditulis sebagai statement terpisah, jadi tidak harus dimasukkan semuanya ke dalam satu statement. Kekurangannya, sintaks SQL-nya punya banyak batasan yang berasal dari Apache Calcite. Sementara itu, Materialize SQL memberi kesan sedang berupaya keras menjaga kompatibilitas dengan PostgreSQL.
• Saya ingat pernah melihat kabar belum lama ini bahwa VMware sudah menjauh dari differential datalog, jadi menyenangkan melihat tulisan baru dari McSharry.
  • Tim Differential Datalog mendirikan perusahaan bernama Feldera, yang bisa dilihat di situs Feldera. Saya menduga alasan mereka beralih dari differential datalog ke differential SQL adalah karena datalog sulit benar-benar diadopsi di pasar.
• Jika ingin memakai datalog bersama Rust, saya merekomendasikan cozodb. Cozodb ditulis dalam Rust dan mendukung sintaks kueri datalog.
  • Cozodb juga proyek yang menarik, tetapi tampaknya sudah tidak aktif. Sekitar November 2024 saya sempat menelusuri source code-nya dan menemukan titik yang bisa diperbaiki dengan cukup sederhana pada backend penyimpanan sqlite (isu #285).
• Tautan ke tulisan terkait yang diposting di Hacker News sehari sebelumnya: langsung ke postingan