Rust'ta Etkileşimli bir Datalog Motoru Geliştirmek

• Datalog mantıksal programlama ile Rust'ın verimliliğini birleştirerek, sade ama kullanışlı ve performansı da gözeten etkileşimli bir Datalog motorunun geliştirme süreci ayrıntılı biçimde paylaşılıyor
• Sezgisel bir CLI ortamında kural (rule) ve olgu (fact) gerçek zamanlı olarak eklenip genişletilebiliyor; büyük veri yükleme, dinamik kural girişi ve hızlı sorgu performansı deneyimlenebiliyor
• Ayrıştırma (Parsing), veri temsili (Representation), kural değerlendirme (Planning/Evaluation) adım adım Rust kodlarıyla anlatılarak gerçek bir uygulamanın nasıl geliştirileceği gösteriliyor
• Optimize edilmemiş basit bir uygulamadan başlayıp performans ve yapıyı kademeli olarak iyileştirme süreci üzerinden veri paralelliği/join optimizasyonu gibi ileri düzey mantıklar da öğrenilebiliyor
• Büyük veri kümelerine dayalı program analizi (Nullability, Aliasing vb.) örnekleri gerçekten çalıştırılarak performans ve bellek sorunları, sorgu optimizasyonu ve join-plan iyileştirme bilgileri paylaşılıyor

---

Giriş: Rust'ta Datalog mantıksal programlama deneyi

• Memorial Day döneminde Minnowbrook konferansında çeşitli mantıksal programlama (Datalog vb.) uygulamaları ve tartışmalar yapıldı
• Mevcut Datalog araçlarında (Soufflé, ctdal vb.) gerçek kullanım/genişletilebilirlik/performans açısından sınırlamalar görüldü; pratik bir araca olan ihtiyaç öne çıktı
• Yazar, doğrudan Rust ile sadelik/kullanılabilirlik/performansın hepsini karşılayan bir Datalog yorumlayıcısı (datatoad) geliştirmeye karar verdi
• Projenin hedefi: CLI üzerinde büyük hacimli veriyi hızlı yüklemek, kuralları dinamik olarak ekleyip değiştirmek, sonuçları gerçek zamanlı görmek ve sorgu performansını güvenceye almak

Datalog'un temel kavramları

• Datalog, kural (Head :- Body) biçimindeki mantıksal ifadeleri temel alır ve verilen fact ile rule'lar üzerinden çıkarılabilecek tüm olguları otomatik olarak türetir
• Kurallar (ör. tri(a, b, c) :- edge(a, b), edge(b, c), edge(a, c)) değişkenler/literallerden oluşur
• fact, koşulsuz doğru kabul edilen bir değerdir (ör. edge(1, 2) :- .)
• Datalog'un güçlü yanı: yeni kurallar eklendiğinde çıkarılabilir bilgi kümesinin artması (monotonluk) ve kural/olgu sırasından bağımsız olarak aynı sonucun elde edilmesi (yakınsama)
• Rust tarafında kurallar ve fact'ler Atom/Rule/Term yapılarıyla temsil edilir, fact kümeleri ise relation bazında yönetilir

Temel yapı tasarımı

Veri temsili

• Fact, başlangıçta Vec<String> olarak; fact kümesi ise BTreeMap<String, Vec<Fact>> gibi yapılarla tasarlandı
• Büyük veri optimizasyonu için columnar (sütun odaklı) veri yapısı benimsendi ve allocation overhead en aza indirildi
• FactContainer: sıralanmış ve tekilleştirilmiş fact kümesi, append-only yapı
• FactLSM: FactContainer'ları çok katmanlı yöneten LSM (Log-structured merge-tree) yaklaşımı; ekleme ile sıralama/birleştirme işlemlerini verimli hale getiriyor
• FactSet: fact yaşam döngüsünü (yeni eklenen, yakın zamanda türetilen, kararlı hale gelen fact'ler) yöneterek yinelenen hesaplamaları ve gereksiz bellek israfını önlüyor

Kural uygulama ve çıkarım

• Her kural için bir JoinPlan oluşturuluyor ve uygun sütun sırası/anahtar kombinasyonlarına dayalı merge join ile çıkarım yapılıyor
• merge join: body atomlarındaki anahtar sütunlar sıralanıyor; yalnızca join anahtarları eşleştiğinde yeni fact türetiliyor ve böylece performans en üst düzeye çıkarılıyor
• FactSet'in stable/recent/to_add yapısı kullanılarak önceden türetilmiş fact'lerle yeni fact'ler ayrıştırılıyor, böylece gereksiz yeniden hesaplamalar önleniyor (diferansiyel değerlendirme)
• .update() döngüsü: yeni fact üretimi durana kadar tüm kurallar tekrar tekrar uygulanıyor; fixpoint'e ulaşana dek çıkarım sürüyor

Parser uygulaması

• Soufflé tarzı sözdizimi (?var, :-, ., , vb.) destekleniyor; tokenizer ve parser doğrudan Rust ile yazılmış
• Hata durumunda güvenli biçimde None döndüren, deneysel ortama uygun sade bir parser tasarımı tercih edilmiş

Performans optimizasyonu ve gerçek analiz örnekleri

Nullability analizi (Reachability)

• Büyük veri kümelerinde (ör. httpd_df) değer kopyalama/taşıma yollarını izlemek için Datalog kuralları tanımlanıyor ve performans ölçülüyor
• Farklı kural yazım kalıpları arasında çok büyük performans farkları oluşuyor (değişken bağlama/sütun sırası/join planına bağlı geçici relation üretimi vb.)
• Verinin başlangıç biçimi ve join stratejisine göre çalışma süresi ile bellek kullanımı onlarca kat değişebiliyor; bu da sorgu optimizasyonunun önemini doğrudan gösteriyor
• Optimizasyon uygulandığında mevcut C++ tabanlı araçlara (Graspan vb.) kıyasla 10 ila 80 katı aşan performans artışı görüldü

Aliasing analizi (Points-to)

• Aliasing/pointer izleme analizi için karmaşık Datalog kalıpları uygulanıyor; makalelerdeki (Graspan, Zheng-Rugina vb.) sorgularla aynı sorgular çalıştırılıyor
• Datalog kuralları içindeki tekrar (^*), opsiyon (^?), transpoz (^T) işlemleri açık özyineleme/union olarak genişletiliyor
• Ara sonuçların (relation alias, geçici join vb.) adlandırılması ve yeniden kullanımı, tüm sorgu planının verimliliğinde ve kaynak tüketiminde büyük fark yaratıyor
• Sorgu planı optimize edilmeden büyük ara sonuçlar üretilirse performans düşüşü ve bellek patlaması yaşanabiliyor (ör. V relation)
• Yalnızca gerekli sonuçları üreten "demand-driven" yaklaşım (magic set dönüşümü) tartışılıyor; gerçek sorgu planı dönüşümleri ve performans iyileştirme ihtimali sunuluyor

Rust ile doğrudan deney yaparak çıkarılan dersler

• Datalog motoru performansının özü veri temsili (columnar/LSM), diferansiyel çıkarım ve join plan optimizasyonunda yatıyor
• Kuralları yalnızca mekanik biçimde yazmak, gereksiz ara veri üretimine ve kaynak israfına yol açabiliyor; optimizasyon şart
• Rust ile doğrudan deney yapıldığında, gerçek veri kümelerinde milyonlarca/on milyonlarca satırlık fact'i verimli biçimde yönetip ölçeklenebilirlik ile çıkarım hızını aynı anda elde etmek mümkün
• CLI ortamında büyük veri yükleme, gerçek zamanlı kural ekleme ve sonuç inceleme işlemleri kolayca denenebiliyor
• Query optimizer'ın rolü, bushy-tree join kullanımı (ara sonuçlardan yararlanma), gereksiz relation üretmekten kaçınma alışkanlığı gibi noktalar, gerçek Datalog yazımı ve işletimi için önemli içgörüler sunuyor

Gelecekteki genişleme alanları

• Disk spill, çoklu worker/prosesle dağıtık genişleme, streaming join, özel derleme optimizasyonları gibi araştırma konuları hâlâ açık duruyor
• Büyük ölçekli program analizi, grafik/ilişkisel çıkarım, statik analiz, veri akışı izleme gibi pratik alanlarda Rust tabanlı Datalog'un kullanım potansiyeli yüksek

[GN⁺]

Hacker News yorumu

• Bu yazının şu an üst sıralarda olması eğlenceli; çünkü ben de Differential Datalog'u (bu depo) ve Rust'ı kullanarak gerçek zamanlı bir strateji oyunu yapma işi üzerinde çalışıyorum. Yapı şöyle: oyun mantığını DDL üstleniyor; amaç da yeni fikirler öğrenmek ve bolca deneme-yanılma tecrübesi edinmek.
  • İlerlemenin nasıl gideceğini merak ediyorum, sonucun ne çıkacağı ilginç olacak.
  • Differential Datalog geliştirmesi artık aktif değil; bu yüzden uygulamasının nereye kadar gidebildiğini ve şu anda ne kadar tamamlanmış olduğunu merak ediyorum.
• mangle datalog'u Rust'a port etmeye çalışırken biraz ilerleme kaydettim. Rust uygulamasına buradan bakılabilir; golang sürümü de aynı depoda duruyor. İşin yavaş gitmesinin sebebi biraz düşük öncelikli olması ama asıl olarak "second system syndrome" denilen durum: insan ilk yaptığından sonra ikincide daha fazlasını hedefleyince iş yavaşlıyor. Rust sürümündeki mangle, memory mapping sayesinde veriyi gerektiğinde diskten okuyup yazabildiği için büyük veriyle çalışabiliyor. golang sürümü ise tüm veriyi belleğe alıp işliyor. Bu yazının güzel yanı, datalog parser yapısını iyi anlatması ve LSM tree'den söz etmesi; bu yüzden anlaşılması kolay. data frog'a kıyasla da takip etmesi çok daha rahat. Rust tarafında proc-macros kullanan ascent, crepe gibi çeşitli datalog uygulamaları var ama çalışma anında sorguları dinamik olarak işleme konusunda kısıtları bulunuyor. Eğer sorgular ve program sabit olan statik analiz tipi bir kullanım söz konusuysa, proc macro yaklaşımının da gayet iyi olduğunu düşünüyorum.
• Datalog meraklılarından bazılarının düzenli olarak bir araya gelip üretmeye devam ettiğini görmek güzel. Son dönemde datalog rönesansı biraz yavaşlamış gibi; Datalog 2.0 konferansı da eskisine göre daha küçüktü ve HYTRADBOI konferansının ikinci yılında datalog tartışmaları da belirgin biçimde azaldı. İlk etkinlikte bildirilerin dörtte birinin datalog ile ilgili olduğunu hatırlıyorum. Başka katılımcıların yakın dönem datalog proje deneyimlerini paylaşması ise gerçekten motive edici. Ben de bu aralar eski tarz bir SQL veritabanından büyük ölçekli yazılım geçişine hazırlanırken veri kalitesi için bir pipeline kuruyorum; datalog sorguları iyi yapılandırıldığında çok okunaklı oluyor ve veri kalitesi sorunlarını araştırmada SQL'den çok daha verimli bir araç gibi geliyor.
  • Datalog 2.0 konferansındaki düşük katılımın datalog'un gerilemesinden çok etkinliğin yapısıyla ilgili olduğu görüşündeyim. Datalog 2.0, LPNMR adlı daha az bilinen bir Avrupa konferansının yan etkinliğiydi; bu kez de ABD'de Dallas'ta biraz rastgele bir şekilde düzenlendi. Ben de Datalog 2.0'a bir makale gönderdim ama asıl yazar başkasıydı; ayrıca etkinliğe gerçekten datalog alanında çalışan pek az kişi katıldı. Nemo solver'ı sunan Avrupalı katılımcı dikkat çekiyordu. Özetle, bu yıl Datalog 2.0'a katılımın az olmasında etkinliğin kendine özgü koşulları ve yan etkinlik olması daha belirleyiciydi; bununla birlikte datalog engine uygulamaları konusunda artık büyük yenilikler kalmadığı görüşüne de katılıyorum. Gerçek araştırma akışı bugün temel datalog'dan çok stream tabanlı (HydroFlow), choice (Dusa), chase engine (Egglog) gibi daha ilginç alanlara kaymış durumda. monotonic, chain-forward saturation (Horn clauses) tarafı mühendislik açısından yeterince oturmuş yöntemler; şimdi bunun üzerine semirings, Z-sets gibi yeni teorik yönler araştırılıyor.
• Yazarın datalog konusunda iyi işler çıkardığını düşünüyorum ama girişte binary join öğretme biçimi, ideal olmayan durumlarda hızla karmaşıklaştığı için biraz zayıf kalıyor. Bence generic join ailesi yaklaşımlar daha sezgisel biçimde genellenebiliyor. worst-case optimal join algorithm için wiki açıklamasına bakılması iyi olur.
  • Bununla bağlantılı olarak, McSherry'nin önceki blog yazısında binary join ile uygun sorgu planı ayarlamaları yapıldığında worst-case optimal çalışma süresine ulaşılabildiğinin kanıtlandığı süreci görebilirsiniz. Blog yazısı.
• İlgili blog yazısının açılışındaki "I, a notorious villain, was invited for what I was half sure was my long-due comeuppance." cümlesi, bence bu yıl okuduğum teknik blog yazıları arasındaki en iyi açılıştı. Yazı boyunca yazarın neşeli anlatımı öne çıkıyordu; bu kadar derin teknik bir konuyu bu kadar keyifli okutabilen yazı nadir bulunur. aliasing sorgu optimizasyonu yolculuğunu adeta bir dedektif romanı gibi anlatmış. 50GB bellek kullanımında yaşanan hayal kırıklığını, sonra 5GB'a inmeyi başardığında gelen sevinci birlikte yaşıyorsunuz. Hem kod hem de yazı dili açısından çok başarılı.
• Eskiden bazı Clojure hayranlarının datalog'un SQL'den daha üstün olduğuna inandığını ve ilişkisel veritabanlarının yalnızca SQL desteklemesinden yakındığını duymuştum. Neden böyle düşündüklerini ise hiç derinlemesine incelemedim.
  • Clojure veya Datomic'in datalog lehçelerine çok aşina değilim ama datalog'un kendisine sempati duyuyorum. Çevrimiçi notebook ortamında datalog denemek için Percival öneririm: percival.ink. Datalog'un temel kavramlarını öğrendikten sonra uygulamalar arasında geçiş yapmak kolay oluyor. Hatta Percival'ı fork edip datalog'u SQLite'a derleyen bir sürüm de yaptım; fork sürümü henüz aggregate functions veya gelişmiş join'ler konusunda tamamlanmış değil ama temel sorgular iyi çalışıyor. Logica ise Google'daki araştırmacılar tarafından geliştirilmiş, çok daha ciddi ve olgun bir datalog->SQL derleyicisi; BigTable, DuckDB gibi çeşitli SQL lehçelerini destekliyor. Logica. Özellikle özyinelemeli sorgular/kurallar söz konusu olduğunda datalog'un ne kadar üstün derecede kolay olduğu etkileyici. SQL ile de yapılabiliyor ama sanki kili pipetle içmeye çalışmak gibi. Frank McSherry'nin geliştirdiği Materialize.com, “WITH MUTUALLY RECURSIVE” türü bir SQL biçimi sunuyor; bkz. Materialize blogu. Bunu Notion'ın sayfa yükleme sorguları ve veri senkronizasyonu için kullanmayı değerlendiriyorum. Feldera'da da recursive views için benzer bir form var; bkz. Feldera blog yazısı. Feldera'nın avantajı, her “rule” ya da alt görünümün bağımsız bir statement olarak ayrı ayrı yazılabilmesi; hepsini tek bir ifade içine sıkıştırmak gerekmiyor. Dezavantajı ise SQL sözdiziminin Apache Calcite kaynaklı pek çok kısıt taşıması. Materialize SQL ise PostgreSQL uyumluluğu için çaba gösteriyor izlenimi veriyor.
• Kısa süre öncesine kadar VMware'in differential datalog'dan uzaklaştığına dair bir şeyler okuduğumu hatırlıyorum. Bu yüzden McSharry'nin yeni yazısını görmek sevindirici.
  • Differential Datalog ekibi Feldera adında bir şirket kurdu; Feldera web sitesinden görülebilir. differential datalog'dan differential SQL'e geçmelerinin nedeni muhtemelen datalog'un pazarda gerçek anlamda benimsenmesinin zor olmasıydı.
• Datalog ile Rust'ı birlikte kullanmak istiyorsanız cozodb'ye bakın derim; cozodb Rust ile yazılmış ve datalog sorgu sözdizimini destekliyor.
  • cozodb de ilginç bir proje ama artık aktif görünmüyor. 2024 Kasım civarında kaynak koduna bakarken sqlite depolama backend'inde kolayca iyileştirilebilecek bir nokta (issue #285) fark etmiştim.
• Bununla ilgili bir yazı Hacker News'te 1 gün önce de paylaşılmıştı: gönderiye git