Rust में इंटरैक्टिव Datalog इंजन बनाना

 (github.com/frankmcsherry)
1 पॉइंट द्वारा GN⁺ 2025-06-16 | 1 टिप्पणियां | WhatsApp पर शेयर करें
  • Datalog लॉजिक प्रोग्रामिंग और Rust की efficiency को मिलाकर, एक सरल लेकिन उपयोगी और performance-केंद्रित इंटरैक्टिव Datalog इंजन बनाने की प्रक्रिया विस्तार से साझा की गई है
  • सहज CLI environment में rule और fact को रियल टाइम में जोड़ना/विस्तारित करना संभव है, साथ ही बड़े पैमाने पर डेटा लोडिंग, dynamic rule input और तेज query performance का अनुभव किया जा सकता है
  • Parsing, data representation, और rule evaluation (Planning/Evaluation) को चरण-दर-चरण Rust कोड के साथ समझाया गया है ताकि वास्तविक implementation तरीका सीखा जा सके
  • अनऑप्टिमाइज़्ड सरल implementation से शुरू करके performance और structure को धीरे-धीरे बेहतर बनाने की प्रक्रिया के जरिए, data parallelism और join optimization जैसे उन्नत logic भी सीखे जा सकते हैं
  • बड़े dataset-आधारित program analysis (Nullability, Aliasing आदि) के वास्तविक execution के साथ performance और memory issues, query optimization, और join-plan सुधार के व्यावहारिक अनुभव साझा किए गए हैं

परिचय: Rust में Datalog लॉजिक प्रोग्रामिंग का प्रयोग

  • Memorial Day अवधि के दौरान Minnowbrook conference में विभिन्न logic programming (Datalog आदि) पर अभ्यास और चर्चा की गई
  • मौजूदा Datalog tools (Soufflé, ctdal आदि) में वास्तविक उपयोग, extensibility और performance के संदर्भ में सीमाएँ दिखीं, जिससे एक practical tool की ज़रूरत उभरी
  • लेखक ने सीधे Rust में ऐसा Datalog interpreter (datatoad) बनाने का निर्णय लिया जो simplicity, usability और performance तीनों को संतुलित करे
  • प्रोजेक्ट का लक्ष्य: CLI में बड़े डेटा को तेज़ी से लोड करना, नियमों को dynamically जोड़ना/बदलना, रियल टाइम परिणाम देखना, और query performance सुनिश्चित करना

Datalog की बुनियादी अवधारणाएँ

  • Datalog नियमों (Head :- Body) के रूप में लिखे गए logic statements पर आधारित है, और दिए गए fact व rule से सभी संभव निष्कर्षित facts को स्वतः निकालता है
  • नियम (उदाहरण: tri(a, b, c) :- edge(a, b), edge(b, c), edge(a, c)) variables और literals से बने होते हैं
  • fact वह मान है जो बिना किसी शर्त के सत्य होता है (उदाहरण: edge(1, 2) :- .)
  • Datalog की ताकत: जैसे-जैसे नियम जुड़ते हैं, infer की जा सकने वाली जानकारी बढ़ती है (monotonicity), और नियम/तथ्यों के क्रम से स्वतंत्र होकर एक ही परिणाम मिलता है (convergence)
  • Rust में नियम और fact को Atom/Rule/Term structs से व्यक्त किया जाता है, और relation के अनुसार fact sets प्रबंधित किए जाते हैं

मुख्य संरचना डिज़ाइन

डेटा representation

  • Fact को Vec<String> के रूप में, और fact sets को BTreeMap<String, Vec<Fact>> आदि के रूप में प्रारंभिक तौर पर डिज़ाइन किया गया
  • बड़े डेटा के optimization के लिए columnar data structure अपनाया गया ताकि allocation overhead न्यूनतम रहे
  • FactContainer: sorted और deduplicated fact set, append-only संरचना
  • FactLSM: FactContainer की कई परतों को LSM (Log-structured merge-tree) तरीके से प्रबंधित कर insertion तथा sort/merge को अधिक efficient बनाया गया
  • FactSet: fact के lifecycle (नया जोड़ा गया, हाल में निष्कर्षित, स्थिर fact) को प्रबंधित कर duplicate computation और अनावश्यक memory wastage को रोकता है

नियम लागू करना और inference

  • हर नियम के लिए JoinPlan बनाया जाता है, और उपयुक्त column order/keys के आधार पर merge join से inference किया जाता है
  • merge join: body atom के key columns को sort करने के बाद केवल join key match होने पर नया fact निकाला जाता है, जिससे performance अधिकतम होती है
  • FactSet की stable/recent/to_add संरचना का उपयोग कर पहले से निष्कर्षित facts और नए facts को अलग रखा जाता है, जिससे अनावश्यक recomputation रोकी जाती है (differential evaluation)
  • .update() loop: जब तक नए facts निकलना बंद न हो जाए, तब तक सभी नियमों को बार-बार लागू किया जाता है; fixpoint मिलने तक inference चलता है

parser implementation

  • Soufflé-शैली syntax (?var, :-, ., , आदि) को support किया गया है, और Rust में tokenizer/parser सीधे लिखा गया है
  • error आने पर सुरक्षित रूप से None लौटाया जाता है, और प्रयोगात्मक environment के अनुरूप सरल parser डिज़ाइन किया गया है

Performance optimization और वास्तविक analysis उदाहरण

Nullability analysis (Reachability)

  • बड़े dataset (जैसे httpd_df) पर value copy/move paths को track करने के लिए Datalog rules परिभाषित कर performance मापी गई
  • rule लिखने के अलग-अलग patterns के अनुसार performance में बहुत बड़ा अंतर देखा गया, जैसे variable binding, column order, और join plan के अनुसार temp relation बनना
  • डेटा के शुरुआती रूप और join strategy के आधार पर execution time और memory usage में कई दर्जन गुना अंतर आया, जिससे query optimization का महत्व स्पष्ट हुआ
  • optimization लागू करने पर मौजूदा C++-आधारित tools (Graspan आदि) की तुलना में 10 से 80 गुना या उससे अधिक performance improvement देखा गया

Aliasing analysis (Points-to)

  • aliasing/pointer tracking analysis के लिए जटिल Datalog patterns लागू किए गए, और papers (Graspan, Zheng-Rugina आदि) जैसे ही queries चलाई गईं
  • Datalog rules में repetition (^*), option (^?), और transpose (^T) operations को explicit recursion/union में expand किया गया
  • intermediate results (relation alias, temp join आदि) की naming और reuse design के अनुसार पूरे query plan की efficiency और resource consumption में बड़ा अंतर आया
  • query plan optimization के बिना बड़े intermediate results बनाने पर performance गिरावट और memory explosion हुआ (उदाहरण: V relation)
  • केवल आवश्यक परिणाम निकालने वाले "demand-driven" तरीके (magic-set transformation) पर चर्चा की गई, और query plan बदलकर performance सुधार की संभावना दिखाई गई

Rust में सीधे प्रयोग करके मिली सीख

  • Datalog इंजन की performance का मूल आधार data representation (columnar/LSM), differential inference, और join plan optimization है
  • यदि नियम केवल यांत्रिक ढंग से लिखे जाएँ, तो अनावश्यक intermediate data बनता है और resource wastage बढ़ता है, इसलिए optimization ज़रूरी है
  • Rust में सीधे प्रयोग करते हुए, वास्तविक datasets में लाखों/करोड़ों rows के facts को efficiently प्रबंधित करना, scalability पाना, और inference speed बनाए रखना संभव है
  • CLI environment में बड़े पैमाने पर डेटा लोडिंग, रियल टाइम नियम जोड़ना, और परिणाम देखना आसानी से प्रयोग किया जा सकता है
  • query optimizer की भूमिका, bushy-tree join (intermediate results का उपयोग), और अनावश्यक relations की generation से बचने की आदत जैसे बिंदु, वास्तविक Datalog लेखन और संचालन के लिए महत्वपूर्ण संकेत देते हैं

आगे के विस्तार के कार्य

  • disk spill, multi-worker/process distributed scaling, streaming join, custom compiler optimization आदि जैसे शोध कार्य अभी बाकी हैं
  • बड़े पैमाने के program analysis, graph/relation inference, static analysis, और data flow tracking जैसे व्यावहारिक क्षेत्रों में Rust Datalog के उपयोग की संभावना काफी अधिक है

संबंधित पढ़ाई

1 टिप्पणियां

 
GN⁺ 2025-06-16
Hacker News राय
  • यह मज़ेदार है कि यह लेख अभी ऊपर ट्रेंड कर रहा है। मैं भी Differential Datalog(यह repository) और Rust का इस्तेमाल करके एक real-time strategy game बनाने पर काम कर रहा हूँ। संरचना ऐसी है कि DDL game logic संभालता है, और मेरा इरादा नए ideas सीखने और trial-and-error का अनुभव लेने का है।
    • प्रगति को लेकर उत्सुक हूँ, और जानना चाहता हूँ कि इसका नतीजा कैसा निकलता है।
    • Differential Datalog का development अब निष्क्रिय है, इसलिए मैं जानना चाहता हूँ कि उसकी implementation कहाँ तक संभव है और अभी वह कितनी पूरी हुई है।
  • mangle datalog को Rust में port करने की कोशिश में मैंने थोड़ी प्रगति की है। Rust implementation यहाँ देखी जा सकती है, और golang version उसी repository में मौजूद है। काम धीमा होने की वजह कम priority तो है ही, लेकिन 'second system syndrome' भी है—यानी पहली बार से दूसरी बार बनाते समय ज़्यादा महत्वाकांक्षा आ जाने से काम धीमा हो जाना। Rust version का mangle memory mapping के ज़रिए किसी भी समय disk से data पढ़ और लिख सकता है, इसलिए बड़े data sets संभाल सकता है। golang version की संरचना ऐसी है कि पूरा data memory में लोड करके process किया जाता है। इस लेख की अच्छी बात यह है कि datalog parser की बनावट अच्छे से समझाई गई है, LSM tree का ज़िक्र होने से समझना आसान होता है, और data frog की तुलना में इसे follow करना कहीं आसान है। Rust में proc-macros का उपयोग करने वाले ascent, crepe जैसे कई datalog implementations हैं, लेकिन runtime के दौरान queries को dynamically handle करने में उनकी सीमाएँ हैं। अगर query और program fixed static analysis case हों, तो proc macro approach भी काफ़ी बढ़िया है।
  • datalog के उत्साही लोगों का लगातार मिलते-जुलते रहना अच्छा लगता है। हाल में datalog renaissance थोड़ी धीमी पड़ी हुई लगती है; Datalog 2.0 conference भी पहले की तुलना में छोटी थी, और HYTRADBOI conference के दूसरे edition में datalog पर चर्चा काफ़ी कम थी। मुझे याद है कि पहले event में papers का लगभग एक-चौथाई हिस्सा datalog से जुड़ा था। दूसरे प्रतिभागियों को हाल के datalog projects के अनुभव साझा करते देखना काफ़ी हौसला देता है। इन दिनों मैं पुराने SQL databases से बड़े पैमाने पर software migration की तैयारी करते हुए data quality pipeline बना रहा हूँ, और मेरा मानना है कि datalog queries को अगर अच्छी तरह structure किया जाए तो वे पढ़ने में आसान होती हैं और data quality issues खोजने के लिए SQL से कहीं ज़्यादा असरदार tool बनती हैं।
    • एक राय यह है कि Datalog 2.0 conference में कम attendance, datalog की गिरावट से ज़्यादा event structure की समस्या थी। Datalog 2.0, LPNMR नाम की कम-ज्ञात European conference का satellite event था, और इस बार यह अमेरिका के Dallas में कुछ बेतरतीब ढंग से आयोजित हुआ। मैंने भी Datalog 2.0 में paper submit किया था, लेकिन मुख्य author कोई और था, और वास्तव में datalog field के लोग भी event में बहुत कम थे। Nemo solver प्रस्तुत करने वाला यूरोपीय प्रतिभागी ध्यान खींच रहा था। सार यह है कि इस साल Datalog 2.0 में कम लोग होना event की अपनी परिस्थितियों और satellite format की वजह से ज़्यादा था, और इस बात से सहमत हूँ कि datalog engine implementation में अब बहुत बड़ी innovations शायद शेष नहीं हैं। असली research direction अब basic datalog से आगे stream-based(HydroFlow), choice(Dusa), chase engine(Egglog) जैसे और रोचक topics की ओर बढ़ रही है। monotonic, chain-forward saturation(Horn clauses) engineering के लिहाज़ से काफ़ी स्थापित तरीके हैं, और अब इनके ऊपर semirings, Z-sets जैसी नई theory पर काम हो रहा है।
  • मुझे लगता है कि लेखक datalog से जुड़ा काम अच्छी तरह करते हैं, लेकिन introduction में binary join सिखाने का तरीका आदर्श स्थिति न हो तो जल्दी जटिल हो जाता है, इसलिए थोड़ा अफ़सोस होता है। generic join परिवार का तरीका मुझे ज़्यादा सहज और सामान्यीकृत करने लायक लगता है। wiki explanation on worst-case optimal join algorithm देखने की सलाह है।
    • इसी संदर्भ में, McSherry की एक पुरानी blog post में यह साबित करने की प्रक्रिया देखी जा सकती है कि binary join भी सही query plan adjustment के साथ worst-case optimal runtime हासिल कर सकता है। blog post देखें।
  • उस blog post की opening में "I, a notorious villain, was invited for what I was half sure was my long-due comeuppance." वाली पंक्ति सबसे ज़्यादा असरदार लगी—मुझे लगा यह इस साल की सबसे बेहतरीन technical blog openings में से एक है। पूरे लेख में लेखक की चुटीली शैली उभरकर आती है, और इतने गहरे technical विषय को इतना मज़ेदार पढ़ने लायक बना देने वाले लेख बहुत कम होते हैं। aliasing query optimization की यात्रा को लगभग एक detective novel की तरह रोचक ढंग से पेश किया गया है। 50GB memory usage पर निराश होने और फिर 5GB तक optimization सफल होने पर अनायास ही साथ में खुशी होती है। code और लेखन—दोनों ही शानदार हैं।
  • पहले कुछ Clojure प्रशंसकों को यह मानते सुना था कि datalog, SQL से बेहतर है, और यह अफ़सोस जताते भी सुना था कि relational DBs सिर्फ SQL को support करते हैं। उन्होंने ऐसा क्यों सोचा, यह मैंने ख़ुद गहराई से नहीं देखा।
    • Clojure या Datomic की datalog dialects मेरे लिए उतनी परिचित नहीं हैं, लेकिन datalog खुद मुझे काफ़ी समझ में आता है। online notebook environment में datalog आज़माने के लिए Percival की सिफारिश करता हूँ—percival.ink। datalog के मूल concepts समझ लेने के बाद implementations के बीच आना-जाना आसान हो जाता है। मैंने Percival को fork करके datalog को SQLite में compile करने वाला एक version भी बनाया था; fork version में अभी aggregate functions या advanced joins अधूरे हैं, लेकिन basic queries अच्छी तरह काम करती हैं। Logica, Google researchers द्वारा बनाया गया कहीं ज़्यादा गंभीर और परिपक्व datalog->SQL compiler है, जो BigTable, DuckDB जैसी कई SQL dialects को support करता है। Logica देखें। recursive queries/rules को संभालने में datalog का बहुत आसान होना ख़ास तौर पर प्रभावशाली है। SQL में यह संभव तो है, लेकिन जैसे किसी पुआल से मिट्टी पीने की कोशिश करना। Frank McSherry की Materialize.com “WITH MUTUALLY RECURSIVE” SQL form देती है; Materialize blog देखें। मैं इसे Notion के page load queries और data synchronization में इस्तेमाल करने पर विचार कर रहा हूँ। Feldera में भी recursive views के लिए ऐसा ही एक form है; Feldera blog post देखें। Feldera की ख़ासियत यह है that हर “rule” या subview को अलग statement के रूप में लिखा जा सकता है, सब कुछ एक ही statement में भरना ज़रूरी नहीं। कमी यह है कि उसकी SQL syntax पर Apache Calcite से आई कई पाबंदियाँ हैं। Materialize SQL, PostgreSQL compatibility पर मेहनत करती हुई लगती है।
  • कुछ समय पहले तक VMware के differential datalog से दूर हो जाने की बात पढ़ी थी। McSharry की नई पोस्ट देखकर अच्छा लगा।
    • Differential Datalog टीम ने Feldera नाम की कंपनी बनाई है, जिसे Feldera website पर देखा जा सकता है। मेरा अनुमान है कि differential datalog से differential SQL की ओर जाने की वजह यह रही होगी कि datalog को बाज़ार में वास्तव में अपनाया जाना मुश्किल था।
  • अगर datalog और Rust साथ में इस्तेमाल करना चाहें तो cozodb की सिफारिश है। cozodb, Rust में लिखा गया है और datalog query syntax support करता है।
    • cozodb भी एक दिलचस्प project है, लेकिन यह निष्क्रिय लगता है। 2024 के नवंबर के आसपास source code देखते समय मुझे sqlite storage backend में आसानी से सुधारे जा सकने वाले कुछ points मिले थे(issue #285)।
  • 1 दिन पहले Hacker News पर आए संबंधित लेख का link: पोस्ट सीधे देखें