สร้างเอนจิน Datalog แบบโต้ตอบได้ใน Rust

 (github.com/frankmcsherry)
1 คะแนน โดย GN⁺ 2025-06-16 | 1 ความคิดเห็น | แชร์ทาง WhatsApp
  • ผสานตรรกะการเขียนโปรแกรมแบบ Datalog เข้ากับประสิทธิภาพของ Rust โดยเล่ากระบวนการพัฒนาเอนจิน Datalog แบบโต้ตอบได้ที่เรียบง่าย ใช้งานสะดวก และคำนึงถึงประสิทธิภาพอย่างละเอียด
  • สามารถเพิ่ม/ขยายกฎ (rule) และข้อเท็จจริง (fact) ได้แบบเรียลไทม์ในสภาพแวดล้อม CLI ที่เข้าใจง่าย พร้อมรองรับการโหลดข้อมูลจำนวนมาก การป้อนกฎแบบไดนามิก และประสิทธิภาพการคิวรีที่รวดเร็ว
  • อธิบาย Parsing, การแทนข้อมูล (Representation), และการประเมินกฎ (Planning/Evaluation) ทีละขั้นพร้อมโค้ด Rust เพื่อให้เรียนรู้วิธีลงมือสร้างจริงได้
  • เริ่มจากการติดตั้งใช้งานแบบง่ายที่ยังไม่ปรับแต่ง แล้วค่อย ๆ ปรับปรุงทั้งประสิทธิภาพและโครงสร้าง ทำให้ได้เรียนรู้ตรรกะขั้นสูงอย่างการประมวลผลข้อมูลแบบขนานและการปรับแต่ง join
  • ยกกรณีศึกษาการวิเคราะห์โปรแกรมบนชุดข้อมูลขนาดใหญ่ (เช่น Nullability, Aliasing) ให้รันจริง พร้อมแบ่งปันประสบการณ์ด้านประสิทธิภาพ ปัญหาหน่วยความจำ การปรับแต่งคิวรี และการปรับปรุง join-plan

บทนำ: ทดลองตรรกะการเขียนโปรแกรม Datalog ใน Rust

  • ในช่วง Memorial Day ได้มีการฝึกปฏิบัติและอภิปรายเกี่ยวกับ logic programming หลากหลายแบบ (เช่น Datalog) ที่งานประชุม Minnowbrook
  • เครื่องมือ Datalog เดิม ๆ (เช่น Soufflé, ctdal) พบข้อจำกัดในด้านการใช้งานจริง การขยายต่อ และประสิทธิภาพ จึงยิ่งเห็นความจำเป็นของเครื่องมือที่ใช้งานได้จริง
  • ผู้เขียนจึงตัดสินใจลงมือสร้าง Datalog interpreter (datatoad) ด้วย Rust เอง เพื่อให้ได้ทั้งความเรียบง่าย การใช้งานที่ดี และประสิทธิภาพ
  • เป้าหมายของโปรเจกต์คือ โหลดข้อมูลขนาดใหญ่ใน CLI ได้รวดเร็ว เพิ่ม/แก้กฎแบบไดนามิก ดูผลลัพธ์แบบเรียลไทม์ และยังคงประสิทธิภาพการคิวรีไว้ได้

แนวคิดพื้นฐานของ Datalog

  • Datalog อิงกับประโยคตรรกะในรูปกฎ (Head :- Body) และสามารถอนุมานข้อเท็จจริงที่สรุปได้ทั้งหมดจาก fact และ rule ที่กำหนดมาโดยอัตโนมัติ
  • กฎ (เช่น tri(a, b, c) :- edge(a, b), edge(b, c), edge(a, c)) ประกอบด้วยตัวแปรและลิเทอรัล
  • fact คือค่าที่เป็นจริงโดยไม่มีเงื่อนไข (เช่น edge(1, 2) :- .)
  • จุดแข็งของ Datalog คือ เมื่อเพิ่มกฎ ชุดข้อมูลที่อนุมานได้จะเพิ่มขึ้นตามไปด้วย (monotonicity) และไม่ว่าลำดับของกฎ/ข้อเท็จจริงจะเป็นอย่างไร ก็ให้ผลลัพธ์เดียวกัน (convergence)
  • ใน Rust มีการแทนกฎและ fact ด้วยโครงสร้าง Atom/Rule/Term และจัดการชุด fact แยกตาม relation

การออกแบบโครงสร้างหลัก

การแทนข้อมูล

  • Fact ถูกออกแบบตั้งต้นเป็น Vec<String> และชุด fact ใช้โครงสร้างอย่าง BTreeMap<String, Vec<Fact>>
  • เพื่อปรับให้เหมาะกับข้อมูลขนาดใหญ่ จึงนำโครงสร้างข้อมูลแบบ columnar มาใช้เพื่อลด alloc overhead
  • FactContainer: ชุด fact ที่จัดเรียงและลบข้อมูลซ้ำแล้ว ในโครงสร้างแบบ append-only
  • FactLSM: วิธีจัดการ FactContainer หลายชั้นแบบ LSM (Log-structured merge-tree) เพื่อให้การแทรก การจัดเรียง และการผสานข้อมูลมีประสิทธิภาพขึ้น
  • FactSet: จัดการวงจรชีวิตของ fact (เพิ่งเพิ่ม, เพิ่งอนุมานได้, และ fact ที่นิ่งแล้ว) เพื่อหลีกเลี่ยงการคำนวณซ้ำและการใช้หน่วยความจำเกินจำเป็น

การใช้กฎและการอนุมาน

  • แต่ละกฎจะสร้าง JoinPlan ก่อน แล้วอนุมานด้วยวิธี merge join ตามลำดับคอลัมน์และชุดคีย์ที่เหมาะสม
  • merge join: จัดเรียงคีย์คอลัมน์ของ body atom แต่ละตัว แล้วสร้าง fact ใหม่เฉพาะเมื่อ join key ตรงกัน เพื่อดึงประสิทธิภาพสูงสุด
  • ใช้โครงสร้าง stable/recent/to_add ของ FactSet เพื่อแยก fact ที่อนุมานแล้วออกจาก fact ใหม่ และหลีกเลี่ยงการคำนวณซ้ำที่ไม่จำเป็น (differential evaluation)
  • ลูป .update(): ใช้ทุกกฎซ้ำไปเรื่อย ๆ จนไม่สามารถอนุมาน fact ใหม่ได้อีก และวนต่อจนถึงจุด fixpoint

การสร้าง parser

  • รองรับไวยากรณ์สไตล์ Soufflé (?var, :-, ., , ฯลฯ) และเขียน tokenizer/parser ขึ้นเองด้วย Rust
  • เมื่อเกิดข้อผิดพลาดจะคืนค่า None อย่างปลอดภัย เป็น parser แบบเรียบง่ายที่เหมาะกับสภาพแวดล้อมเชิงทดลอง

การปรับประสิทธิภาพและตัวอย่างการวิเคราะห์จริง

การวิเคราะห์ Nullability (Reachability)

  • นิยามกฎ Datalog และวัดประสิทธิภาพบนชุดข้อมูลขนาดใหญ่ (เช่น httpd_df) เพื่อติดตามเส้นทางการคัดลอก/ย้ายค่า
  • รูปแบบการเขียนกฎที่ต่างกันทำให้ประสิทธิภาพต่างกันอย่างมาก (ขึ้นกับ variable binding, ลำดับคอลัมน์, การเกิด temp relation ตาม join plan ฯลฯ)
  • รูปแบบข้อมูลตั้งต้นและกลยุทธ์ join ที่ต่างกัน ทำให้เวลาในการรันและการใช้หน่วยความจำต่างกันได้หลายสิบเท่า สะท้อนความสำคัญของการปรับคิวรีอย่างชัดเจน
  • เมื่อปรับแต่งแล้ว พบว่าประสิทธิภาพดีกว่าเครื่องมือเดิมที่พัฒนาด้วย C++ (เช่น Graspan) ราว 10–80 เท่าหรือมากกว่า

การวิเคราะห์ Aliasing (Points-to)

  • สร้างแพตเทิร์น Datalog ที่ซับซ้อนสำหรับการวิเคราะห์ aliasing/การติดตามพอยน์เตอร์ และรันคิวรีเดียวกับในงานวิจัย (Graspan, Zheng-Rugina ฯลฯ)
  • ขยายโอเปอเรชันการทำซ้ำ (^*), ออปชัน (^?), และ transpose (^T) ภายในกฎ Datalog ให้เป็น recursive/union แบบชัดเจน
  • การออกแบบชื่อและการนำผลลัพธ์กลาง (เช่น relation alias, temp join) กลับมาใช้ใหม่ ส่งผลอย่างมากต่อประสิทธิภาพและการใช้ทรัพยากรของ query plan ทั้งหมด
  • หากสร้างผลลัพธ์กลางขนาดใหญ่โดยไม่ปรับ query plan จะทำให้ประสิทธิภาพตกลงและหน่วยความจำพุ่งสูง (เช่น relation V)
  • มีการอภิปรายถึงแนวทางแบบ "demand-driven" (magic-set transformation) ที่คำนวณเฉพาะผลลัพธ์ที่จำเป็น พร้อมชี้ให้เห็นความเป็นไปได้ในการดัดแปลง query plan และปรับปรุงประสิทธิภาพจริง

บทเรียนที่ได้จากการทดลองด้วย Rust โดยตรง

  • หัวใจของประสิทธิภาพในเอนจิน Datalog อยู่ที่การแทนข้อมูลแบบ columnar/LSM การอนุมานเชิงส่วนต่าง และการปรับ query plan ของ join
  • หากเขียนกฎแบบตรงไปตรงมาเชิงกลไกเพียงอย่างเดียว มักนำไปสู่การสร้างข้อมูลกลางที่ไม่จำเป็นและสิ้นเปลืองทรัพยากร จึงต้องมีการปรับแต่ง
  • การทดลองด้วย Rust โดยตรงแสดงให้เห็นว่าสามารถจัดการ fact ระดับหลายล้านถึงหลายสิบล้านแถวบนชุดข้อมูลจริงได้อย่างมีประสิทธิภาพ พร้อมรักษาทั้งความสามารถในการขยายและความเร็วในการอนุมาน
  • ในสภาพแวดล้อม CLI สามารถทดลองโหลดข้อมูลขนาดใหญ่ เพิ่มกฎแบบเรียลไทม์ และตรวจผลลัพธ์ได้อย่างสะดวก
  • บทบาทของ query optimizer, แนวคิด bushy-tree join (ใช้ผลลัพธ์กลางให้เกิดประโยชน์), และการหลีกเลี่ยงการสร้าง relation ที่ไม่จำเป็น ล้วนเป็นข้อคิดสำคัญต่อการเขียนและใช้งาน Datalog จริง

งานต่อยอดในอนาคต

  • ยังมีหัวข้อวิจัยต่อ เช่น disk spill, การกระจายงานด้วยหลาย worker/process, streaming join, และ custom compile optimization
  • Rust Datalog มีศักยภาพสูงสำหรับงานจริง เช่น การวิเคราะห์โปรแกรมขนาดใหญ่ การอนุมานกราฟ/ความสัมพันธ์ การวิเคราะห์เชิงสถิต และการติดตาม data flow

บทความที่เกี่ยวข้อง

1 ความคิดเห็น

 
GN⁺ 2025-06-16
ความคิดเห็นบน Hacker News
  • กำลังเจอสถานการณ์ที่น่าสนใจที่บทความนี้ขึ้นมาอยู่ด้านบนพอดี ระหว่างกำลังทำเกมวางแผนเรียลไทม์โดยใช้ Differential Datalog(รีโพนี้) และ Rust ตามคำอธิบายในบทความ โครงสร้างคือให้ DDL รับผิดชอบตรรกะของเกม และตั้งใจจะเรียนรู้ไอเดียใหม่ ๆ พร้อมเก็บประสบการณ์ลองผิดลองถูกหลายแบบ
    • กำลังเฝ้ารอความคืบหน้า และเป็นสถานการณ์ที่ทำให้อยากรู้ว่าผลลัพธ์จะออกมาเป็นอย่างไร
    • เนื่องจากการพัฒนา Differential Datalog อยู่ในภาวะไม่ค่อยเคลื่อนไหว เลยอยากรู้ว่าการนำไปใช้งานจริงทำได้ไกลแค่ไหน และตอนนี้มันเสร็จสมบูรณ์ประมาณไหนแล้ว
  • แชร์ประสบการณ์ที่พอทำความคืบหน้าได้บ้างในการพอร์ต mangle datalog ไปเป็น Rust ดู implementation ฝั่ง Rust ได้ที่นี่ และเวอร์ชัน golang ก็อยู่ในรีโพเดียวกัน เหตุที่งานคืบหน้าช้า ส่วนหนึ่งเพราะลำดับความสำคัญต่ำ แต่อีกส่วนเป็นเพราะอาการ 'second system syndrome' (พอทำรอบที่สองก็อยากใส่อะไรเพิ่มจนงานช้าลงเมื่อเทียบกับของชิ้นแรก) mangle เวอร์ชัน Rust สามารถอ่านและเขียนข้อมูลจากดิสก์ได้ตลอดผ่าน memory mapping จึงรองรับข้อมูลขนาดใหญ่ได้ ส่วนเวอร์ชัน golang เป็นโครงสร้างที่ยกข้อมูลทั้งหมดขึ้นหน่วยความจำแล้วประมวลผล จุดที่ดีของบทความนี้คืออธิบายการประกอบตัว parser ของ datalog ได้ดี และมีการพูดถึง LSM tree ทำให้เข้าใจง่าย อีกทั้งตามได้ง่ายกว่า data frog มาก ใน Rust มี implementation ของ datalog หลายแบบ เช่น ascent, crepe ที่ใช้ proc-macros แต่มีข้อจำกัดเมื่อต้องจัดการ query แบบไดนามิกระหว่างรัน ถ้าเป็นกรณีวิเคราะห์แบบสถิตที่ query และโปรแกรมถูกกำหนดตายตัวอยู่แล้ว ก็คิดว่าแนวทาง proc macro ก็ยอดเยี่ยมเพียงพอ
  • เป็นเรื่องดีที่ได้เห็นคนที่หลงใหลใน datalog บางส่วนยังคงรวมตัวและทำงานกันอย่างต่อเนื่อง ช่วงหลังบรรยากาศเหมือนกระแส datalog renaissance แผ่วลง โดยงานประชุม Datalog 2.0 ก็เล็กลงกว่าแต่ก่อน และในงาน HYTRADBOI ครั้งที่ 2 การพูดคุยเรื่อง datalog เองก็ลดลงมาก จำได้ว่าในการจัดครั้งแรก บทความราว 1 ใน 4 เกี่ยวข้องกับ datalog การที่ผู้เข้าร่วมคนอื่น ๆ มาแบ่งปันประสบการณ์โปรเจกต์ datalog ล่าสุดของตัวเองช่วยให้มีกำลังใจมาก ตอนนี้กำลังเตรียมย้ายซอฟต์แวร์ขนาดใหญ่จากฐานข้อมูล SQL แบบดั้งเดิม และกำลังสร้าง data quality pipeline อยู่ มองว่าถ้าจัดโครงสร้างดี ๆ แล้ว query แบบ datalog อ่านง่ายมาก และเป็นเครื่องมือที่มีประสิทธิภาพกว่าการใช้ SQL มากสำหรับการสำรวจปัญหาคุณภาพข้อมูล
    • มีความเห็นว่าจำนวนผู้เข้าร่วมงาน Datalog 2.0 ที่น้อย ไม่ได้สะท้อนว่าตัว datalog ซบเซา แต่ได้รับผลจากโครงสร้างของงานมากกว่า Datalog 2.0 เป็นงาน satellite ของการประชุมยุโรปที่คนรู้จักน้อยกว่าอย่าง LPNMR และครั้งนี้ก็ไปจัดแบบค่อนข้างสุ่มที่ Dallas สหรัฐฯ ตัวเองก็ส่งบทความไปที่ Datalog 2.0 แต่ผู้เขียนหลักไม่ใช่ตน และในทางปฏิบัติก็มีคนในสาย datalog ไปร่วมงานไม่มาก ผู้เข้าร่วมจากยุโรปที่นำเสนอ Nemo solver ดูโดดเด่น ใจความคือจำนวนผู้เข้าร่วม Datalog 2.0 ปีนี้น้อยเพราะลักษณะเฉพาะของงานและความเป็นงาน satellite มากกว่า และก็เห็นด้วยว่าในแง่ implementation ของ datalog engine เอง น่าจะไม่ได้เหลือนวัตกรรมใหญ่ ๆ มากแล้ว กระแสวิจัยจริง ๆ ขยับไปยังหัวข้อที่น่าสนใจกว่า datalog พื้นฐาน เช่น แบบ stream-based (HydroFlow), choice (Dusa), chase engine (Egglog) พร้อมอธิบายว่าวิธีอย่าง monotonic, chain-forward saturation (Horn clauses) นั้นถูกทำให้มั่นคงในเชิงวิศวกรรมมากพอแล้ว เลยมีการสำรวจทฤษฎีใหม่ ๆ บนฐานนี้ เช่น semirings, Z-sets
  • คิดว่าผู้เขียนทำงานด้าน datalog ได้ดี แต่รู้สึกเสียดายที่วิธีสอน binary join ในช่วงต้นบทความนั้น ถ้าไม่ใช่กรณีในอุดมคติจะซับซ้อนขึ้นเร็วมาก มองว่าวิธีตระกูล generic join เป็นการทำให้เป็นนามธรรมที่ตรงไปตรงมาและขยายทั่วไปได้ดีกว่า แนะนำให้อ่านคำอธิบายในวิกิเกี่ยวกับ worst-case optimal join algorithm
    • ต่อเนื่องจากประเด็นนี้ ในบล็อกโพสต์ก่อนหน้าของ McSherry มีการพิสูจน์ให้ดูว่าการใช้ binary join ก็สามารถทำให้ได้ runtime ที่เป็น worst-case optimal ได้ หากปรับ query plan ให้เหมาะสม ดูได้ในบล็อกโพสต์
  • ในส่วนเปิดของบล็อกโพสต์นี้ ประโยคที่ว่า "I, a notorious villain, was invited for what I was half sure was my long-due comeuppance." น่าจะเป็นประโยคเปิดของบทความเทคนิคที่ประทับใจที่สุดแห่งปี ผู้เขียนมีสำนวนเล่าที่สนุกตลอดทั้งบทความ และรู้สึกว่าหาได้ยากมากที่จะมีงานเขียนซึ่งทำให้หัวข้อเทคนิคที่ลึกขนาดนี้อ่านได้เพลินขนาดนี้ โครงเรื่องพาเส้นทางการปรับแต่ง query เรื่อง aliasing ออกมาได้น่าติดตามเหมือนนิยายสืบสวน พอผู้เขียนท้อกับการใช้หน่วยความจำ 50GB แล้วไปปรับจนเหลือ 5GB สำเร็จ ก็ให้ความรู้สึกเหมือนเราเอาใจช่วยไปด้วย มองว่าทั้งโค้ดและงานเขียนยอดเยี่ยมมาก
  • เคยได้ยินแฟน Clojure บางคนเมื่อก่อนเชื่อว่า datalog เหนือกว่า SQL และรู้สึกเสียดายที่ฐานข้อมูลเชิงสัมพันธ์ต่าง ๆ รองรับแต่ SQL ทั้งหมด แต่ก็ไม่เคยลงลึกว่าทำไมพวกเขาถึงคิดแบบนั้น
    • แม้จะไม่คุ้นกับ datalog dialect ของ Clojure หรือ Datomic เท่าไร แต่ก็เห็นด้วยกับตัว datalog เอง ขอแนะนำ Percival สำหรับลองใช้ datalog ในสภาพแวดล้อมแบบ notebook ออนไลน์ ใช้ได้ที่ percival.ink แค่เข้าใจแนวคิดหลักของ datalog ก็ย้ายไปมาระหว่าง implementation ต่าง ๆ ได้ไม่ยาก เคย fork Percival แล้วทำเวอร์ชันที่คอมไพล์ datalog ไปเป็น SQLite ด้วย โดยเวอร์ชันฟอร์กยังทำ aggregate function หรือ join ขั้นสูงได้ไม่สมบูรณ์ แต่ query พื้นฐานทำงานได้ดี Logica เป็นคอมไพเลอร์ datalog->SQL ที่จริงจังและสมบูรณ์กว่ามาก สร้างโดยนักวิจัยของ Google และรองรับ SQL dialect หลายแบบ เช่น BigTable, DuckDB ดูได้ที่Logica จุดที่น่าประทับใจคือเวลาเขียน query/rule แบบ recursive นั้น datalog ง่ายกว่าอย่างชัดเจน ใน SQL แม้จะทำได้แต่ให้ความรู้สึกเหมือนดูดดินเหนียวผ่านหลอด Materialize.com ของ Frank McSherry มีรูปแบบ SQL แบบ “WITH MUTUALLY RECURSIVE” ดูได้จากบล็อก Materialize และกำลังพิจารณานำไปใช้กับ query โหลดหน้าเพจของ Notion และการซิงก์ข้อมูล Feldera ก็มีรูปแบบคล้ายกันสำหรับ recursive view ดูบล็อกโพสต์ของ Feldera ข้อดีของ Feldera คือสามารถแยกแต่ละ “rule” หรือ subview ออกเป็น statement อิสระได้ แทนที่จะต้องใส่ทั้งหมดไว้ใน statement เดียว ส่วนข้อเสียคือไวยากรณ์ SQL มีข้อจำกัดมากจาก Apache Calcite ขณะที่ Materialize SQL ดูพยายามรักษาความเข้ากันได้กับ PostgreSQL
  • จำได้ว่าไม่นานมานี้เคยเห็นคนพูดว่า VMware ถอยห่างจาก differential datalog แล้ว เลยรู้สึกดีที่ได้เห็นบทความใหม่ของ McSharry
    • ทีม Differential Datalog ได้ก่อตั้งบริษัทชื่อ Feldera ดูได้ที่เว็บไซต์ Feldera และคาดว่าเหตุผลที่เปลี่ยนจาก differential datalog ไปเป็น differential SQL น่าจะเป็นเพราะ datalog เองนำไปใช้จริงในตลาดได้ยาก
  • ถ้าอยากใช้ datalog กับ Rust ด้วย ขอแนะนำ cozodb ซึ่งเขียนด้วย Rust และรองรับไวยากรณ์ query แบบ datalog
    • cozodb ก็เป็นโปรเจกต์ที่น่าสนใจ แต่ดูเหมือนจะอยู่ในภาวะไม่ค่อยเคลื่อนไหว เคยเปิดดูซอร์สโค้ดราวเดือนพฤศจิกายน 2024 แล้วพบจุดที่น่าจะปรับปรุง backend ที่เก็บข้อมูลบน sqlite ได้ง่าย ๆ (issue #285)
  • แปะลิงก์กระทู้ที่เกี่ยวข้องซึ่งขึ้นบน Hacker News เมื่อ 1 วันก่อน ไปที่โพสต์