Créer un moteur Datalog interactif en Rust

• Combinaison de la programmation logique Datalog et de l’efficacité de Rust pour détailler le développement d’un moteur Datalog interactif à la fois simple, agréable à utiliser et pensé pour les performances
• Ajout et extension en temps réel de règles (rule) et de faits (fact) dans un environnement CLI intuitif, avec chargement de gros volumes de données, saisie dynamique de règles et performances de requête rapides
• Parsing, représentation des données et évaluation des règles (planning/evaluation) expliqués étape par étape avec du code Rust pour apprendre une méthode d’implémentation concrète
• Démarrage depuis une implémentation simple non optimisée puis amélioration progressive des performances et de la structure, permettant aussi d’apprendre des logiques avancées comme le traitement parallèle des données et l’optimisation des jointures
• Exécution réelle de cas d’analyse de programmes sur de grands jeux de données (nullability, aliasing, etc.), avec partage de retours sur les problèmes de performance et de mémoire, l’optimisation des requêtes et l’amélioration des plans de jointure

---

Introduction : expérimenter la programmation logique Datalog en Rust

• Pendant la période du Memorial Day, divers ateliers pratiques et discussions autour de la programmation logique (dont Datalog) ont eu lieu à la conférence Minnowbrook
• Les outils Datalog existants (Soufflé, ctdal, etc.) ont montré des limites en usage réel, extensibilité et performances, ce qui a mis en évidence le besoin d’un outil plus pratique
• L’auteur a donc décidé d’implémenter lui-même en Rust un interpréteur Datalog (datatoad) réunissant simplicité, ergonomie et performances
• Objectif du projet : charger rapidement de gros volumes de données depuis le CLI, ajouter ou modifier des règles dynamiquement, vérifier les résultats en temps réel et conserver de bonnes performances de requête

Concepts de base de Datalog

• Datalog repose sur des énoncés logiques sous forme de règles (Head :- Body) et déduit automatiquement tous les faits dérivables à partir des fact et rule donnés
• Une règle (par ex. tri(a, b, c) :- edge(a, b), edge(b, c), edge(a, c)) est composée de variables et de littéraux
• Un fact est une valeur vraie sans condition (par ex. edge(1, 2) :- .)
• Points forts de Datalog : l’ajout de règles augmente l’ensemble des informations déductibles (monotonicité), et le résultat final est identique quel que soit l’ordre des règles et des faits (convergence)
• En Rust, les règles et les fact sont représentés par des structures Atom / Rule / Term, et les ensembles de fact sont gérés par relation

Conception des structures clés

Représentation des données

• Les fact sont d’abord conçus comme Vec<String>, et les ensembles de fact comme BTreeMap<String, Vec<Fact>>
• Pour optimiser les gros volumes de données, une structure columnar (orientée colonnes) est introduite afin de minimiser l’overhead d’allocation
• FactContainer : ensemble de fact triés et dédupliqués, avec une structure append only
• FactLSM : gestion de plusieurs couches de FactContainer selon une approche LSM (Log-structured merge-tree) pour améliorer l’efficacité de l’insertion, du tri et de la fusion
• FactSet : gestion du cycle de vie des fact (nouvellement ajoutés, récemment déduits, stabilisés) pour éviter les calculs en double et le gaspillage mémoire inutile

Application des règles et inférence

• Chaque règle génère un JoinPlan, puis l’inférence s’effectue par merge join selon un ordre de colonnes et une combinaison de clés appropriés
• merge join : les colonnes clés de chaque atome du corps sont triées, puis de nouveaux fact ne sont déduits que lorsque les clés de jointure correspondent, ce qui maximise les performances
• La structure stable/recent/to_add de FactSet permet de séparer les fact déjà déduits des nouveaux et d’éviter les recalculs inutiles (évaluation différentielle)
• Boucle .update() : toutes les règles sont appliquées de manière répétée jusqu’à ce que la déduction de nouveaux fact s’arrête, c’est-à-dire jusqu’au point fixe

Implémentation du parseur

• Prise en charge d’une grammaire de style Soufflé (?var, :-, ., ,, etc.), avec tokenizer et parseur écrits directement en Rust
• En cas d’erreur, retour sûr de None, dans une conception volontairement simple adaptée à un environnement expérimental

Optimisation des performances et exemples d’analyse réels

Analyse de nullability (reachability)

• Définition de règles Datalog et mesure des performances sur de grands jeux de données (par ex. httpd_df) pour suivre les chemins de copie et de déplacement de valeurs
• Les performances varient énormément selon la manière d’écrire les règles (liaison des variables, ordre des colonnes, génération de relations temporaires selon le plan de jointure, etc.)
• Selon la forme initiale des données et la stratégie de jointure, le temps d’exécution et l’usage mémoire peuvent varier de plusieurs dizaines de fois, montrant concrètement l’importance de l’optimisation des requêtes
• Après optimisation, des gains de performance de 10 à plus de 80 fois par rapport à des outils existants en C++ (comme Graspan) ont été observés

Analyse d’aliasing (points-to)

• Implémentation de motifs Datalog complexes pour l’analyse d’aliasing et le suivi de pointeurs, avec exécution des mêmes requêtes que dans la littérature (Graspan, Zheng-Rugina, etc.)
• Les opérations de répétition (^*), d’option (^?) et de transposition (^T) dans les règles Datalog sont développées en récursion et en union explicites
• Selon la manière de nommer et de réutiliser les résultats intermédiaires (relation alias, jointures temporaires, etc.), l’efficacité et la consommation de ressources du plan de requête global changent fortement
• Sans optimisation du plan de requête, la production de gros résultats intermédiaires entraîne une chute des performances et une explosion de la mémoire (par ex. relation V)
• L’approche « demand-driven » qui ne produit que les résultats nécessaires (transformation magic sets) est discutée, avec des perspectives d’amélioration via la transformation concrète du plan de requête

Enseignements tirés des expérimentations directes en Rust

• Les performances d’un moteur Datalog reposent avant tout sur la représentation des données (columnar/LSM), l’inférence différentielle et l’optimisation du plan de jointure
• Écrire des règles de manière purement mécanique conduit facilement à générer des données intermédiaires inutiles et à gaspiller des ressources, d’où la nécessité de l’optimisation
• En expérimentant directement en Rust, il est possible de gérer efficacement des fact représentant plusieurs millions ou dizaines de millions de lignes sur des jeux de données réels, tout en obtenant extensibilité et rapidité d’inférence
• L’environnement CLI permet d’expérimenter facilement le chargement massif de données, l’ajout de règles en temps réel et la vérification des résultats
• Le rôle du query optimizer, les bushy-tree join utilisant les résultats intermédiaires, et l’habitude d’éviter la création de relations inutiles offrent des enseignements concrets pour l’écriture et l’exploitation de Datalog

Pistes d’extension pour la suite

• Il reste des sujets de recherche comme le spill sur disque, l’extension distribuée sur plusieurs workers/processus, les streaming joins et les optimisations de compilation personnalisées
• Le Datalog en Rust présente un fort potentiel d’usage dans des domaines concrets comme l’analyse de programmes à grande échelle, l’inférence sur graphes et relations, l’analyse statique et le suivi de flux de données

[GN⁺]

Commentaire Hacker News

• C’est amusant de voir cet article remonter en tête en ce moment : je suis justement en train de travailler sur un jeu de stratégie en temps réel avec Differential Datalog (ce dépôt) et Rust. Dans cette architecture, DDL gère la logique du jeu, et l’objectif est aussi d’apprendre de nouvelles idées et d’accumuler de l’expérience à force de tâtonner.
  • J’attends la suite avec intérêt, je suis curieux de voir ce que ça va donner.
  • Comme le développement de Differential Datalog est à l’arrêt, je me demande jusqu’où son implémentation peut aller et dans quel état d’achèvement elle se trouve aujourd’hui.
• Je voulais porter mangle datalog vers Rust et j’ai fait quelques progrès. L’implémentation Rust est visible ici, dans le même dépôt que la version golang. Si ça avance lentement, c’est en partie parce que ce n’est pas prioritaire, mais aussi à cause du phénomène de « second system syndrome » (quand on veut en faire trop sur la deuxième version et que le travail ralentit). La version Rust de mangle peut lire et écrire des données directement sur disque via memory mapping, ce qui permet de traiter de gros volumes, alors que la version golang charge tout en mémoire. Ce que j’aime dans cet article, c’est que la construction du parseur datalog est bien expliquée, qu’il mentionne les arbres LSM, donc c’est facile à suivre, et que c’est bien plus abordable que data frog. Il existe aussi en Rust diverses implémentations de datalog comme ascent ou crepe via les proc-macros, mais elles ont des limites pour traiter dynamiquement des requêtes à l’exécution. Si l’on est dans un cas d’analyse statique avec requêtes et programme figés, l’approche proc macro me paraît tout à fait excellente.
• C’est agréable de voir qu’un petit noyau de passionnés de datalog continue à se retrouver et à faire vivre le sujet. J’ai l’impression que la récente renaissance de datalog s’est un peu calmée : la conférence Datalog 2.0 était plus modeste qu’avant, et lors de la deuxième édition de HYTRADBOI, les discussions autour de datalog ont fortement diminué. Je me souviens que, lors de la première édition, un quart des articles portaient sur datalog. Voir d’autres participants partager leurs projets récents autour de datalog m’encourage beaucoup. En ce moment, je prépare une grande migration logicielle depuis une base SQL ancienne génération et je construis un pipeline de qualité des données ; quand elles sont bien structurées, les requêtes datalog sont à mon avis bien plus lisibles et bien plus efficaces que SQL pour explorer les problèmes de qualité des données.
  • Le faible nombre de participants à Datalog 2.0 tient probablement moins à un déclin de datalog lui-même qu’à la structure de l’événement. Datalog 2.0 était un événement satellite de LPNMR, une conférence européenne peu connue, et cette fois il s’est tenu un peu aléatoirement à Dallas, aux États-Unis. J’y ai moi-même soumis un article, mais l’auteur principal était quelqu’un d’autre, et en pratique il y avait peu de personnes du domaine datalog sur place. On remarquait surtout des participants européens venus présenter Nemo solver. En bref, le faible nombre de participants cette année s’explique davantage par les particularités de l’événement et son statut de satellite. En revanche, je suis d’accord avec l’idée qu’il ne reste plus beaucoup de grandes innovations à faire sur l’implémentation même des moteurs datalog. La recherche avance plutôt vers des sujets plus intéressants que le datalog de base, comme le stream (HydroFlow), le choice (Dusa) ou les chase engines (Egglog). Les approches monotonic et chain-forward saturation (Horn clauses) sont aujourd’hui suffisamment stabilisées sur le plan de l’ingénierie, et l’exploration théorique se fait désormais au-dessus avec des notions comme les semirings ou les Z-sets.
• Je pense que l’auteur est très bon sur les sujets datalog, mais j’ai trouvé dommage la manière dont l’introduction enseigne le binary join : hors cas idéal, cela devient vite complexe. Les approches de la famille generic join me semblent plus intuitives à généraliser. Je recommande la page wiki sur les worst-case optimal join algorithms.
  • À ce sujet, un précédent billet de blog de McSherry montre comment des binary joins peuvent atteindre un temps d’exécution optimal au pire cas grâce à un ajustement approprié du plan de requête ; voir ce billet de blog.
• Dans l’ouverture de ce billet, la phrase « I, a notorious villain, was invited for what I was half sure was my long-due comeuppance. » m’a le plus marqué ; c’est selon moi la meilleure ouverture de billet technique de l’année. Tout au long du texte, la plume pleine d’humour de l’auteur ressort nettement, et il est rare de pouvoir lire avec autant de plaisir un sujet technique aussi profond. Le parcours d’optimisation de requêtes avec aliasing est raconté presque comme un roman policier. On partage sa frustration face aux 50 GB de mémoire consommés, puis on a envie de l’applaudir quand il réussit à descendre à 5 GB. Le code comme l’écriture sont excellents.
• J’ai déjà entendu autrefois certains fans de Clojure affirmer que datalog était supérieur à SQL et regretter que les bases de données relationnelles ne supportent toutes que SQL. Je n’ai jamais vraiment creusé pour comprendre pourquoi ils le pensaient.
  • Je ne suis pas très familier avec les dialectes datalog de Clojure ou de Datomic, mais le datalog lui-même me parle beaucoup. Je recommande Percival pour expérimenter datalog dans un environnement de notebook en ligne : percival.ink. Une fois les concepts de base assimilés, il est facile de passer d’une implémentation à l’autre. J’ai même forké Percival pour créer une version qui compile datalog vers SQLite ; ce fork n’a pas encore les fonctions d’agrégation ni les jointures avancées, mais les requêtes de base fonctionnent bien. Logica est un compilateur datalog -> SQL beaucoup plus sérieux et abouti, créé par des chercheurs de Google, avec prise en charge de divers dialectes SQL comme BigTable ou DuckDB ; voir Logica. Ce qui frappe, c’est à quel point datalog est plus simple pour exprimer des requêtes ou des règles récursives. C’est faisable en SQL, mais on a l’impression d’aspirer de l’argile avec une paille. Materialize.com, développé par Frank McSherry, propose une forme SQL de type « WITH MUTUALLY RECURSIVE » ; voir le blog Materialize. J’envisage de l’utiliser pour les requêtes de chargement de pages et la synchronisation de données de Notion. Feldera propose aussi une forme similaire pour les vues récursives ; voir ce billet du blog Feldera. L’avantage de Feldera, c’est que chaque « règle » ou sous-vue peut être écrite comme un statement indépendant, sans devoir tout mettre dans une seule instruction. L’inconvénient, c’est que la syntaxe SQL subit beaucoup de contraintes héritées d’Apache Calcite. Materialize SQL donne l’impression de faire davantage d’efforts vers la compatibilité PostgreSQL.
• Je me souviens avoir vu récemment passer des commentaires disant que VMware s’était éloigné de differential datalog. Du coup, ce nouvel article de McSharry fait plaisir.
  • L’équipe Differential Datalog a fondé la société Feldera, comme on peut le voir sur le site de Feldera. Je suppose qu’ils sont passés de differential datalog à differential SQL parce que datalog est difficile à faire adopter réellement sur le marché.
• Si vous voulez utiliser datalog avec Rust, je recommande cozodb. cozodb est écrit en Rust et prend en charge une syntaxe de requêtes datalog.
  • cozodb est aussi un projet intéressant, mais il semble inactif. Vers novembre 2024, j’ai parcouru son code source et trouvé un point d’amélioration simple sur le backend de stockage sqlite (issue #285).
• Lien vers un article connexe publié sur Hacker News il y a un jour : voir le post