Eine interaktive Datalog-Engine in Rust bauen

• Kombiniert Datalog-Logikprogrammierung mit der Effizienz von Rust und teilt ausführlich den Entwicklungsprozess einer interaktiven Datalog-Engine, die einfach, benutzerfreundlich und zugleich leistungsorientiert ist
• In einer intuitiven CLI-Umgebung lassen sich Regeln (rule) und Fakten (fact) in Echtzeit hinzufügen und erweitern, einschließlich Massendaten-Import, dynamischer Regelerfassung und schneller Query-Performance
• Parsing, Datenrepräsentation und Regelauswertung (Planning/Evaluation) werden Schritt für Schritt zusammen mit Rust-Code erklärt, sodass sich die konkrete Implementierung nachvollziehen lässt
• Ausgehend von einer einfachen, nicht optimierten Implementierung werden Leistung und Struktur schrittweise verbessert, wodurch sich auch fortgeschrittene Logik wie Datenparallelisierung und Join-Optimierung erlernen lässt
• Anhand programmanalytischer Beispiele auf großen Datensätzen (Nullability, Aliasing usw.) werden reale Läufe gezeigt und Erkenntnisse zu Performance- und Speicherproblemen, Query-Optimierung und der Verbesserung von Join-Plänen geteilt

---

Einführung: Experimente mit Datalog-Logikprogrammierung in Rust

• Während des Memorial-Day-Zeitraums fanden auf der Minnowbrook-Konferenz verschiedene Übungen und Diskussionen zu Logikprogrammierung (u. a. Datalog) statt
• Bei bestehenden Datalog-Werkzeugen (Soufflé, ctdal usw.) zeigten sich Grenzen bei praktischer Nutzung, Erweiterbarkeit und Performance, was den Bedarf an einem praxistauglichen Werkzeug deutlich machte
• Der Autor entschied sich daher, selbst in Rust einen Datalog-Interpreter (datatoad) zu implementieren, der Einfachheit, Nutzbarkeit und Performance zugleich erfüllt
• Projektziel: große Datenmengen schnell per CLI laden, Regeln dynamisch hinzufügen und ändern, Ergebnisse in Echtzeit prüfen und zugleich gute Query-Performance sicherstellen

Grundkonzepte von Datalog

• Datalog basiert auf logischen Ausdrücken in Form von Regeln (Head :- Body) und leitet aus gegebenen Fakten und Regeln automatisch alle ableitbaren Tatsachen her
• Regeln (z. B. tri(a, b, c) :- edge(a, b), edge(b, c), edge(a, c)) bestehen aus Variablen und Literalen
• Ein fact ist ein ohne Bedingungen wahrer Wert (z. B. edge(1, 2) :- .)
• Stärken von Datalog: Werden Regeln hinzugefügt, wächst die Menge der ableitbaren Informationen (Monotonie), und unabhängig von der Reihenfolge von Regeln und Fakten entsteht dasselbe Ergebnis (Konvergenz)
• In Rust werden Regeln und Fakten als Strukturen wie Atom/Rule/Term dargestellt, während Faktmengen pro Relation verwaltet werden

Entwurf der Kernstrukturen

Datenrepräsentation

• Fact wurde zunächst als Vec<String> modelliert, Faktmengen anfangs etwa mit BTreeMap<String, Vec<Fact>> verwaltet
• Zur Optimierung großer Datenmengen wurde eine columnar orientierte Datenstruktur eingeführt, um den Alloc-Overhead zu minimieren
• FactContainer: sortierte und deduplizierte Faktmengen in einer append-only-Struktur
• FactLSM: LSM-Ansatz (Log-structured merge-tree), der mehrere Ebenen von FactContainer verwaltet und Einfügen sowie Sortieren/Zusammenführen effizienter macht
• FactSet: verwaltet den Lebenszyklus von Fakten (neu hinzugefügt, kürzlich abgeleitet, stabilisierte Fakten), um doppelte Berechnungen und unnötigen Speicherverbrauch zu vermeiden

Regelanwendung und Inferenz

• Für jede Regel wird ein JoinPlan erzeugt, auf dessen Basis mit geeigneter Spaltenreihenfolge und Schlüsselkombination per Merge Join inferiert wird
• Merge Join: Die Schlüssels palten der Body-Atome werden sortiert; neue Fakten werden nur dann abgeleitet, wenn die Join-Schlüssel übereinstimmen, was die Performance maximiert
• Über die stable/recent/to_add-Struktur von FactSet werden bereits abgeleitete und neue Fakten getrennt gehalten, um unnötige Neuberechnungen zu vermeiden (differentielle Auswertung)
• In der .update()-Schleife werden alle Regeln wiederholt angewendet, bis keine neuen Fakten mehr entstehen und ein Fixpunkt erreicht ist

Parser-Implementierung

• Unterstützt eine Soufflé-ähnliche Syntax (?var, :-, ., , usw.); Tokenizer und Parser wurden direkt in Rust geschrieben
• Tritt ein Fehler auf, wird sicher None zurückgegeben; ein einfacher Parser passend für ein experimentelles Umfeld

Performance-Optimierung und praktische Analysebeispiele

Nullability-Analyse (Reachability)

• Auf großen Datensätzen (z. B. httpd_df) werden Datalog-Regeln zur Verfolgung von Wertkopien und Verschiebungspfaden definiert und ihre Performance gemessen
• Je nach Schreibmuster der Regeln fallen die Performance-Unterschiede stark aus, etwa durch Variablenbindung, Spaltenreihenfolge oder das Entstehen temporärer Relationen durch Join-Pläne
• Je nach Ausgangsform der Daten und Join-Strategie können Laufzeit und Speicherverbrauch um ein Vielfaches differieren, was die Bedeutung der Query-Optimierung unmittelbar zeigt
• Mit Optimierungen wurde gegenüber bestehenden C++-basierten Werkzeugen (Graspan usw.) eine 10- bis über 80-fache Leistungssteigerung bestätigt

Aliasing-Analyse (Points-to)

• Komplexe Datalog-Muster für Alias- und Pointer-Tracking-Analysen werden implementiert; dieselben Queries wie in Arbeiten zu Graspan, Zheng-Rugina usw. werden ausgeführt
• Wiederholung (^*), Option (^?) und Transposition (^T) innerhalb von Datalog-Regeln werden in explizite Rekursion bzw. Union erweitert
• Je nach Benennung und Wiederverwendungsdesign von Zwischenergebnissen (Relationsalias, temporäre Joins usw.) unterscheiden sich Effizienz und Ressourcenverbrauch des gesamten Query-Plans erheblich
• Werden ohne Query-Plan-Optimierung große Zwischenergebnisse erzeugt, führt das zu Leistungseinbußen und explosionsartigem Speicherverbrauch (z. B. bei der V-Relation)
• Diskutiert wird auch ein „demand-driven“-Ansatz, der nur benötigte Ergebnisse erzeugt (Magic-Set-Transformation), sowie das Potenzial realer Query-Plan-Anpassungen und Performance-Verbesserungen

Erkenntnisse aus eigenen Experimenten mit Rust

• Der Schlüssel zur Performance einer Datalog-Engine liegt in Datenrepräsentation (columnar/LSM), differentieller Inferenz und der Optimierung des Join-Plans
• Werden Regeln nur mechanisch geschrieben, führt das leicht zu unnötigen Zwischendaten und Ressourcenverschwendung, Optimierung ist daher notwendig
• Eigene Experimente in Rust zeigen, dass sich auf realen Datensätzen Millionen bis zig Millionen Faktzeilen effizient verwalten lassen, bei gleichzeitiger Skalierbarkeit und hoher Inferenzgeschwindigkeit
• In einer CLI-Umgebung lassen sich große Datenmengen laden, Regeln in Echtzeit ergänzen und Ergebnisse bequem prüfen
• Die Rolle des Query-Optimizers, Bushy-Tree-Joins zur Nutzung von Zwischenergebnissen und die Gewohnheit, unnötige Relationen gar nicht erst zu erzeugen, liefern wichtige praktische Einsichten für das Schreiben und Betreiben von Datalog

Zukünftige Erweiterungsaufgaben

• Offene Forschungsaufgaben bleiben etwa Disk-Spilling, verteilte Skalierung über mehrere Worker/Prozesse, Streaming-Joins und benutzerdefinierte Compiler-Optimierungen
• Für große Programmanalysen, Graph- und Relationsinferenz, statische Analyse, Data-Flow-Tracking und andere Praxisfelder erscheint das Einsatzpotenzial von Rust-Datalog hoch

[GN⁺]

Hacker-News-Kommentare

• Ich finde es lustig, dass dieser Artikel gerade ganz oben steht, weil ich im Moment ein Echtzeit-Strategiespiel mit Differential Datalog (diesem Repository) und Rust baue. DDL übernimmt dabei die Spiellogik, und ich mache das auch, um neue Ideen zu lernen und durch Versuch und Irrtum Erfahrungen zu sammeln.
  • Ich bin gespannt, wie das Projekt vorankommt, und neugierig auf das Ergebnis.
  • Da die Entwicklung von Differential Datalog inaktiv ist, frage ich mich, wie weit man mit der Implementierung kommen kann und wie vollständig sie derzeit ist.
• Ich habe ein wenig Fortschritt dabei gemacht, mangle datalog nach Rust zu portieren. Die Rust-Implementierung gibt es hier, die Golang-Version liegt im selben Repository. Dass die Arbeit langsam vorangeht, liegt teils an niedriger Priorität, aber auch am Phänomen des "second system syndrome" — also daran, dass man beim zweiten System zu viel will und dadurch langsamer wird. Die Rust-Version von mangle kann per Memory Mapping jederzeit Daten von der Festplatte lesen und schreiben und ist daher für große Datenmengen geeignet. Die Golang-Version lädt die gesamten Daten in den Speicher und verarbeitet sie dort. Das Gute an diesem Artikel ist, dass der Datalog-Parser gut aufgebaut ist und die Erwähnung von LSM-Trees das Verständnis erleichtert. Im Vergleich zu data frog ist er viel leichter nachzuvollziehen. In Rust gibt es verschiedene Datalog-Implementierungen wie ascent oder crepe, die proc-macros nutzen, aber sie haben Einschränkungen bei der dynamischen Verarbeitung von Queries zur Laufzeit. Für statische Analysefälle mit festen Queries und Programmen halte ich den proc-macro-Ansatz aber für völlig ausreichend.
• Es ist schön zu sehen, dass sich ein Teil der Datalog-Enthusiasten weiterhin regelmäßig trifft und aktiv bleibt. Die jüngste Datalog-Renaissance scheint zwar etwas an Schwung verloren zu haben — auch die Datalog-2.0-Konferenz war kleiner als früher, und bei der zweiten HYTRADBOI-Konferenz gab es insgesamt deutlich weniger Datalog-Diskussionen. Ich erinnere mich, dass bei der ersten Ausgabe etwa ein Viertel der Papers mit Datalog zu tun hatte. Es hilft sehr, wenn andere Teilnehmende ihre jüngsten Erfahrungen mit Datalog-Projekten teilen. Ich arbeite gerade an einer Datenqualitäts-Pipeline zur Vorbereitung einer großen Software-Migration aus einer altmodischen SQL-Datenbank, und ich finde, dass Datalog-Queries, wenn sie gut strukturiert sind, sehr gut lesbar sind und für die Untersuchung von Datenqualitätsproblemen viel effizienter als SQL.
  • Dass die Teilnehmerzahl bei der Datalog-2.0-Konferenz niedrig war, liegt meiner Meinung nach eher an der Struktur der Veranstaltung als an einer Flaute von Datalog selbst. Datalog 2.0 war ein Satelliten-Event der weniger bekannten europäischen Konferenz LPNMR und fand dieses Mal eher zufällig in Dallas in den USA statt. Ich selbst habe zwar ein Paper bei Datalog 2.0 eingereicht, aber die Hauptautoren waren andere, und selbst Leute, die tatsächlich im Datalog-Bereich arbeiten, waren bei der Veranstaltung kaum vertreten. Auffällig war vor allem die europäische Gruppe, die den Nemo Solver vorgestellt hat. Kurz gesagt: Dass Datalog 2.0 dieses Jahr wenig Teilnehmende hatte, lag eher an den besonderen Umständen und daran, dass es ein Satelliten-Event war. Ich stimme aber zu, dass es bei der eigentlichen Implementierung von Datalog-Engines kaum noch große Innovationen gibt. Die Forschung entwickelt sich derzeit eher in spannendere Richtungen wie stream-basierte Ansätze (HydroFlow), choice (Dusa) oder Chase-Engines (Egglog). Monotone, chain-forward saturation (Horn-Klauseln) sind aus Engineering-Sicht inzwischen ausreichend etablierte Methoden, und darauf aufbauend werden nun neue Theorien wie semirings und Z-sets erforscht.
• Ich halte den Autor für sehr kompetent bei Datalog-bezogenen Arbeiten, aber ich finde es schade, dass im Einstieg binäre Joins vermittelt werden, weil das außerhalb idealer Bedingungen schnell kompliziert wird. Ansätze aus der generic-join-Familie lassen sich meiner Meinung nach viel intuitiver verallgemeinern. Empfehlenswert ist die Wiki-Erklärung zu Worst-Case-optimalen Join-Algorithmen.
  • Dazu passend zeigt ein früherer Blogpost von McSherry, wie sich mit binären Joins durch passende Anpassung des Query-Plans eine Worst-Case-optimale Laufzeit erreichen lässt. Siehe Blogpost.
• Im Opening dieses Blogposts fand ich den Satz "I, a notorious villain, was invited for what I was half sure was my long-due comeuppance." am eindrucksvollsten — für mich der beste Einstieg eines technischen Blogposts in diesem Jahr. Durch den ganzen Text hinweg fällt der humorvolle Stil des Autors auf, und es ist selten, einen so tief technischen Text so unterhaltsam lesen zu können. Die Reise durch die Optimierung von Aliasing-Queries ist fast wie ein Detektivroman erzählt. Wenn er über 50 GB Speichernutzung verzweifelt und es dann schafft, auf 5 GB zu optimieren, fiebert man richtig mit. Sowohl der Code als auch der Schreibstil sind hervorragend.
• Ich habe früher einige Clojure-Fans erlebt, die glaubten, Datalog sei SQL überlegen, und es schade fanden, dass relationale Datenbanken nur SQL unterstützen. Warum genau sie das so sahen, habe ich nie selbst genauer untersucht.
  • Mit den Datalog-Dialekten aus Clojure oder Datomic bin ich nicht vertraut, aber mit Datalog selbst kann ich viel anfangen. Für das Ausprobieren in einer Online-Notebook-Umgebung empfehle ich Percival: percival.ink. Wenn man die Grundideen von Datalog verstanden hat, kann man recht leicht zwischen Implementierungen wechseln. Ich habe auch einmal einen Fork von Percival gebaut, der Datalog nach SQLite kompiliert; die Fork-Version unterstützt zwar noch keine Aggregatfunktionen oder erweiterten Joins, aber einfache Queries funktionieren gut. Logica ist ein deutlich ernsthafterer und ausgereifterer Datalog->SQL-Compiler von einem Google-Forscher und unterstützt verschiedene SQL-Dialekte wie BigTable und DuckDB. Siehe Logica. Besonders eindrucksvoll ist, wie viel einfacher Datalog beim Umgang mit rekursiven Queries bzw. Regeln ist. In SQL geht es zwar auch, fühlt sich aber an, als würde man Ton mit einem Strohhalm trinken. Das von Frank McSherry entwickelte Materialize.com bietet eine Form von „WITH MUTUALLY RECURSIVE“-SQL; siehe den Materialize-Blog. Es wird offenbar für Notions Seitenlade-Queries und Datensynchronisierung geprüft. Feldera hat ebenfalls eine ähnliche Form für rekursive Views; siehe den Feldera-Blogpost. Ein Vorteil bei Feldera ist, dass sich jede „Regel“ oder Subview als eigenständiges Statement schreiben lässt, statt alles in eine einzige Anweisung packen zu müssen. Der Nachteil ist, dass die SQL-Syntax viele Einschränkungen von Apache Calcite übernimmt. Bei Materialize SQL habe ich den Eindruck, dass man sich um PostgreSQL-Kompatibilität bemüht.
• Ich erinnere mich, vor nicht allzu langer Zeit gelesen zu haben, dass VMware sich von Differential Datalog entfernt hat. Umso erfreulicher ist McSherrys neuer Artikel.
  • Das Differential-Datalog-Team hat die Firma Feldera gegründet; siehe die Feldera-Website. Ich vermute, dass der Wechsel von Differential Datalog zu Differential SQL damit zusammenhängt, dass Datalog sich am Markt nur schwer tatsächlich durchsetzen lässt.
• Wenn man Datalog und Rust zusammen verwenden möchte, ist CozoDB einen Blick wert. CozoDB ist in Rust geschrieben und unterstützt Datalog-Query-Syntax.
  • CozoDB ist ebenfalls ein interessantes Projekt, wirkt aber inaktiv. Ich habe mir etwa im November 2024 den Source Code angesehen und dabei eine Stelle gefunden, an der sich das SQLite-Storage-Backend recht einfach verbessern ließe (Issue #285).
• Hier ist der Link zu einem verwandten Hacker-News-Post von vor einem Tag: Direkt zum Beitrag