Xây dựng engine Datalog tương tác trong Rust

• Kết hợp logic programming Datalog với hiệu quả của Rust để chia sẻ chi tiết quá trình phát triển một engine Datalog tương tác vừa đơn giản, dễ dùng, vừa chú trọng hiệu năng
• Có thể thêm/mở rộng rule và fact theo thời gian thực trong môi trường CLI trực quan, đồng thời trải nghiệm khả năng nạp dữ liệu khối lượng lớn, nhập rule động và hiệu năng truy vấn nhanh
• Giải thích theo từng bước về parsing, biểu diễn dữ liệu và đánh giá rule (Planning/Evaluation) kèm mã Rust để có thể học cách triển khai thực tế
• Bắt đầu từ một bản cài đặt đơn giản chưa được tối ưu rồi dần cải thiện hiệu năng và cấu trúc, qua đó cũng có thể học các logic nâng cao như xử lý song song dữ liệu và tối ưu join
• Chạy thử các trường hợp phân tích chương trình trên tập dữ liệu lớn (Nullability, Aliasing, v.v.) để chia sẻ kinh nghiệm về vấn đề hiệu năng và bộ nhớ, tối ưu truy vấn và cải thiện join-plan

---

Mở đầu: thử nghiệm logic programming Datalog trong Rust

• Trong dịp Memorial Day, tại hội nghị Minnowbrook đã diễn ra nhiều buổi thực hành và thảo luận về logic programming (Datalog, v.v.)
• Các công cụ Datalog hiện có (Soufflé, ctdal, v.v.) bộc lộ giới hạn về khả năng sử dụng thực tế, mở rộng và hiệu năng, làm nổi bật nhu cầu về một công cụ thực dụng hơn
• Tác giả quyết định tự triển khai bằng Rust một trình thông dịch Datalog (datatoad) đáp ứng đồng thời tính đơn giản, khả năng sử dụng và hiệu năng
• Mục tiêu dự án: nạp nhanh dữ liệu lớn trong CLI, thêm/sửa rule động, kiểm tra kết quả theo thời gian thực và vẫn đảm bảo hiệu năng truy vấn

Khái niệm cơ bản về Datalog

• Datalog là một hệ dựa trên các mệnh đề logic dạng rule (Head :- Body), tự động suy ra mọi fact có thể dẫn xuất từ các fact và rule đã cho
• Rule (ví dụ: tri(a, b, c) :- edge(a, b), edge(b, c), edge(a, c)) được tạo thành từ biến và literal
• fact là giá trị đúng mà không có điều kiện (ví dụ: edge(1, 2) :- .)
• Điểm mạnh của Datalog: khi thêm rule thì tập thông tin có thể suy luận tăng lên (tính đơn điệu), và bất kể thứ tự của rule/fact thì vẫn suy ra cùng một kết quả (tính hội tụ)
• Trong Rust, rule và fact được biểu diễn bằng các struct Atom/Rule/Term, và tập fact được quản lý theo từng relation

Thiết kế cấu trúc cốt lõi

Biểu diễn dữ liệu

• Fact ban đầu được thiết kế là Vec<String>, còn tập fact là BTreeMap<String, Vec<Fact>>
• Để tối ưu dữ liệu khối lượng lớn, cấu trúc dữ liệu columnar được đưa vào nhằm giảm tối đa alloc overhead
• FactContainer: tập fact đã được sắp xếp/loại trùng, theo cấu trúc chỉ-append
• FactLSM: quản lý nhiều tầng FactContainer theo kiểu LSM (Log-structured merge-tree) để tối ưu chèn, sắp xếp và hợp nhất
• FactSet: quản lý vòng đời của fact (mới thêm, vừa suy ra gần đây, fact đã ổn định) để tránh tính toán trùng lặp và lãng phí bộ nhớ không cần thiết

Áp dụng rule và suy luận

• Mỗi rule tạo một JoinPlan rồi suy luận theo kiểu merge join dựa trên thứ tự cột/tổ hợp khóa phù hợp
• merge join: sắp xếp các cột khóa theo từng body atom, rồi chỉ suy ra fact mới khi khóa join trùng khớp để tối đa hóa hiệu năng
• Tận dụng cấu trúc stable/recent/to_add của FactSet để tách fact đã suy ra và fact mới, ngăn việc tính lại không cần thiết (đánh giá vi sai)
• Vòng lặp .update(): lặp áp dụng mọi rule cho đến khi không còn fact mới nào được suy ra nữa, tức đạt fixpoint

Cài đặt parser

• Hỗ trợ cú pháp kiểu Soufflé (?var, :-, ., ,, v.v.), với tokenizer/parser tự viết bằng Rust
• Khi lỗi xảy ra thì trả về None an toàn, với thiết kế parser đơn giản phù hợp môi trường thử nghiệm

Tối ưu hiệu năng và ví dụ phân tích thực tế

Phân tích Nullability (Reachability)

• Định nghĩa rule Datalog và đo hiệu năng để theo dõi đường đi sao chép/di chuyển giá trị trên các tập dữ liệu lớn (ví dụ: httpd_df)
• Khác biệt hiệu năng rất lớn tùy vào cách viết rule (binding biến/thứ tự cột/phát sinh temp relation theo join plan, v.v.)
• Tùy dạng dữ liệu đầu vào và chiến lược join, thời gian chạy và mức dùng bộ nhớ có thể chênh nhau hàng chục lần, cho thấy rõ tầm quan trọng của tối ưu truy vấn
• Khi áp dụng tối ưu, hiệu năng được xác nhận cải thiện từ 10 đến hơn 80 lần so với các công cụ nền C++ hiện có (Graspan, v.v.)

Phân tích Aliasing (Points-to)

• Triển khai các mẫu Datalog phức tạp cho phân tích aliasing/theo dõi con trỏ, chạy cùng các truy vấn như trong các bài báo (Graspan, Zheng-Rugina, v.v.)
• Mở rộng rõ ràng các phép lặp (^*), tùy chọn (^?), chuyển vị (^T) trong rule Datalog thành đệ quy/union tường minh
• Tùy vào cách đặt tên và tái sử dụng kết quả trung gian (relation alias, temp join, v.v.), hiệu quả và mức tiêu thụ tài nguyên của toàn bộ query plan có thể khác biệt rất lớn
• Nếu tạo ra kết quả trung gian lớn mà không tối ưu query plan, hiệu năng sẽ giảm mạnh và bộ nhớ có thể tăng vọt (ví dụ: relation V)
• Có đề cập tới cách tiếp cận "demand-driven" chỉ tạo kết quả cần thiết (biến đổi magic-set), đồng thời cho thấy khả năng cải thiện hiệu năng qua việc biến đổi query plan thực tế

Bài học rút ra từ quá trình tự thử nghiệm bằng Rust

• Yếu tố cốt lõi của hiệu năng engine Datalog nằm ở biểu diễn dữ liệu (columnar/LSM), suy luận vi sai và tối ưu join plan
• Nếu chỉ viết rule một cách máy móc thì sẽ dẫn tới tạo dữ liệu trung gian không cần thiết và lãng phí tài nguyên (cần tối ưu)
• Qua việc trực tiếp thử nghiệm bằng Rust, có thể quản lý hiệu quả hàng triệu đến hàng chục triệu hàng fact trên các tập dữ liệu thực tế, đồng thời đạt được cả khả năng mở rộng lẫn tốc độ suy luận
• Trong môi trường CLI, có thể dễ dàng thử nghiệm từ nạp dữ liệu lớn, thêm rule thời gian thực cho đến kiểm tra kết quả
• Vai trò của query optimizer, bushy-tree join (tận dụng kết quả trung gian), và thói quen tránh tạo ra các relation không cần thiết đều là những gợi ý quan trọng cho việc viết và vận hành Datalog thực tế

Các hướng mở rộng trong tương lai

• Vẫn còn các chủ đề nghiên cứu như spill ra đĩa, mở rộng phân tán với nhiều worker/process, streaming join, tối ưu biên dịch tùy biến, v.v.
• Datalog trong Rust có tiềm năng ứng dụng cao trong các lĩnh vực thực tế như phân tích chương trình quy mô lớn, suy luận đồ thị/quan hệ, static analysis và theo dõi luồng dữ liệu

[GN⁺]

Ý kiến Hacker News

• Khá thú vị khi đúng lúc bài này đang nổi lên thì tôi cũng đang làm một game chiến thuật thời gian thực bằng Differential Datalog(kho lưu trữ này) và Rust. Cấu trúc là DDL đảm nhiệm logic game, mục đích là học thêm ý tưởng mới và tích lũy vài kinh nghiệm vấp váp.
  • Tôi đang rất mong chờ tiến triển và tò mò xem kết quả sẽ ra sao.
  • Vì Differential Datalog hiện không còn được phát triển tích cực nữa, nên tôi khá tò mò không biết phần triển khai của nó có thể đi được đến đâu, và hiện giờ đã hoàn thiện đến mức nào.
• Tôi đã có chút tiến triển khi thử port mangle datalog sang Rust. Có thể xem bản triển khai Rust tại đây, nó nằm cùng kho với phiên bản golang. Lý do công việc tiến triển chậm một phần là vì mức ưu tiên thấp, nhưng cũng vì hiện tượng “second system syndrome” (khi làm bản thứ hai thì tham vọng hơn bản đầu nên tiến độ chậm lại). Phiên bản Rust của mangle có thể đọc và ghi dữ liệu từ đĩa bất cứ lúc nào thông qua memory mapping, nên xử lý được dữ liệu dung lượng lớn. Phiên bản golang thì nạp toàn bộ dữ liệu vào bộ nhớ để xử lý. Điểm hay của bài viết này là phần tổ chức parser datalog rất tốt, có nhắc tới LSM tree nên khá dễ hiểu, và dễ theo dõi hơn data frog rất nhiều. Trong Rust cũng có nhiều triển khai datalog như ascent, crepe dùng proc-macros, nhưng chúng bị hạn chế khi cần xử lý truy vấn động trong lúc chạy. Nếu là các trường hợp phân tích tĩnh với truy vấn và chương trình cố định, thì cách tiếp cận proc macro vẫn hoàn toàn rất tốt.
• Thật vui khi thấy một số người đam mê datalog vẫn đều đặn tụ họp và hoạt động. Gần đây có cảm giác làn sóng phục hưng datalog đang chững lại; hội nghị Datalog 2.0 cũng nhỏ hơn trước, và ở kỳ HYTRADBOI lần thứ hai thì bản thân thảo luận về datalog đã giảm đi đáng kể. Tôi nhớ ở lần đầu, khoảng 1/4 số bài báo là về datalog. Việc những người khác chia sẻ trải nghiệm với các dự án datalog gần đây là nguồn động viên rất lớn. Dạo này tôi đang xây dựng pipeline chất lượng dữ liệu để chuẩn bị cho một đợt di chuyển phần mềm quy mô lớn khỏi các cơ sở dữ liệu SQL kiểu cũ. Nếu cấu trúc tốt, truy vấn datalog rất dễ đọc, nên tôi thấy đây là công cụ hiệu quả hơn SQL rất nhiều để khám phá các vấn đề về chất lượng dữ liệu.
  • Ý kiến là việc số người tham dự Datalog 2.0 ít không hẳn do datalog suy thoái, mà phần lớn do cấu trúc sự kiện. Datalog 2.0 là sự kiện vệ tinh của một hội nghị châu Âu ít được biết đến hơn là LPNMR, còn lần này lại được tổ chức khá ngẫu nhiên ở Dallas, Mỹ. Tôi cũng đã gửi bài cho Datalog 2.0, nhưng tác giả chính là người khác, và trên thực tế người làm trong lĩnh vực datalog cũng không tham gia nhiều. Người tham dự từ châu Âu trình bày về Nemo solver là khá nổi bật. Ý chính là số người tham dự ít năm nay chủ yếu do tính chất đặc thù của sự kiện và việc nó là hội nghị vệ tinh, và tôi đồng ý với quan điểm rằng trong bản thân việc triển khai engine datalog thì không còn nhiều đột phá lớn nữa. Dòng nghiên cứu thực tế đang phát triển sang các chủ đề thú vị hơn như stream-based (HydroFlow), choice (Dusa), chase engine (Egglog), hơn là datalog cơ bản. Monotonic, chain-forward saturation (Horn clauses) là các phương pháp đã được định hình khá vững về mặt kỹ thuật, nên giờ người ta đang khám phá các lý thuyết mới hơn bên trên như semirings, Z-sets.
• Tôi nghĩ tác giả làm việc với datalog rất giỏi, nhưng cách phần mở đầu dạy về binary join hơi đáng tiếc vì ngoài tình huống lý tưởng thì nó sẽ nhanh chóng trở nên phức tạp. Tôi thấy các cách thuộc họ generic join trực quan hơn và dễ tổng quát hóa hơn. Khuyến nghị xem giải thích trên wiki về worst-case optimal join algorithm.
  • Nhân tiện, trong một bài blog trước của McSherry có thể thấy quá trình chứng minh rằng binary join cũng có thể đạt runtime tối ưu theo worst-case bằng cách điều chỉnh query plan phù hợp. Xem bài blog.
• Ở phần mở đầu của bài blog đó, câu "I, a notorious villain, was invited for what I was half sure was my long-due comeuppance." là câu gây ấn tượng nhất với tôi; có lẽ là phần mở đầu hay nhất của một bài blog kỹ thuật trong năm nay. Xuyên suốt bài viết, lối kể dí dỏm của tác giả thực sự nổi bật, và hiếm có bài nào về một chủ đề kỹ thuật sâu mà lại đọc thú vị đến vậy. Hành trình tối ưu hóa truy vấn aliasing được kể hấp dẫn như một truyện trinh thám. Khi tác giả tuyệt vọng vì dùng tới 50GB bộ nhớ rồi cuối cùng tối ưu xuống 5GB, tôi có cảm giác như mình cũng đang cổ vũ theo. Cả code lẫn văn phong đều rất xuất sắc.
• Trước đây tôi từng nghe vài người hâm mộ Clojure tin rằng datalog vượt trội hơn SQL, và tiếc rằng các cơ sở dữ liệu quan hệ đều chỉ hỗ trợ SQL. Tôi chưa thực sự đào sâu để hiểu tại sao họ nghĩ vậy.
  • Tôi không quen lắm với các phương ngữ datalog của Clojure hay Datomic, nhưng lại rất đồng cảm với datalog nói chung. Tôi gợi ý Percival để thử datalog trong môi trường notebook trực tuyến, xem percival.ink. Chỉ cần nắm các khái niệm cốt lõi của datalog thì có thể chuyển đổi giữa các triển khai khá dễ dàng. Tôi cũng từng fork Percival và làm một phiên bản biên dịch datalog sang SQLite; bản fork đó vẫn chưa hoàn thiện các hàm tổng hợp hay advanced join, nhưng truy vấn cơ bản chạy tốt. Logica là một trình biên dịch datalog->SQL nghiêm túc và hoàn thiện hơn nhiều do một nhà nghiên cứu của Google tạo ra, hỗ trợ nhiều phương ngữ SQL như BigTable, DuckDB, xem Logica. Điều gây ấn tượng là khi xử lý truy vấn/quy tắc đệ quy thì datalog dễ hơn hẳn; làm bằng SQL tuy vẫn được nhưng giống như hút đất sét qua ống hút. Materialize.com do Frank McSherry xây dựng cung cấp dạng SQL “WITH MUTUALLY RECURSIVE”, xem blog Materialize. Tôi đang cân nhắc dùng nó cho truy vấn tải trang và đồng bộ dữ liệu của Notion. Feldera cũng có một dạng tương tự cho recursive view, xem bài blog của Feldera. Điểm mạnh của Feldera là có thể viết từng “rule” hoặc subview thành các statement độc lập, thay vì phải nhét tất cả vào một câu. Điểm yếu là cú pháp SQL chịu nhiều ràng buộc đến từ Apache Calcite. Còn Materialize SQL thì cho cảm giác đang nỗ lực hướng đến tương thích PostgreSQL.
• Tôi nhớ cách đây không lâu có nghe chuyện VMware đã rời xa differential datalog. Vì vậy bài viết mới của McSharry làm tôi rất vui.
  • Đội ngũ Differential Datalog đã thành lập công ty Feldera, có thể xem trên trang web Feldera. Tôi đoán lý do họ chuyển từ differential datalog sang differential SQL là vì datalog khó được thị trường chấp nhận trong thực tế.
• Nếu muốn dùng datalog cùng Rust thì tôi gợi ý cozodb. cozodb được viết bằng Rust và hỗ trợ cú pháp truy vấn datalog.
  • cozodb cũng là một dự án thú vị, nhưng có vẻ như không còn hoạt động tích cực. Khoảng tháng 11 năm 2024, khi xem mã nguồn, tôi từng phát hiện một điểm có thể cải thiện khá đơn giản ở backend lưu trữ sqlite (issue #285).
• Chia sẻ liên kết tới bài liên quan đã được đăng trên Hacker News từ 1 ngày trước: xem bài đăng