Cómo crear un motor Datalog interactivo en Rust

• Combina la programación lógica de Datalog con la eficiencia de Rust y comparte en detalle el proceso de desarrollo de un motor Datalog interactivo que es simple, usable y también considera el rendimiento
• Permite agregar y ampliar reglas (rule) y hechos (fact) en tiempo real desde un entorno CLI intuitivo, además de experimentar con carga masiva de datos, entrada dinámica de reglas y consultas de alto rendimiento
• Explica paso a paso el parsing, la representación de datos y la evaluación de reglas (Planning/Evaluation) junto con código en Rust, para aprender cómo implementarlo en la práctica
• Parte de una implementación simple no optimizada y mejora gradualmente el rendimiento y la estructura, lo que también permite aprender lógica avanzada como procesamiento paralelo de datos y optimización de joins
• Ejecuta casos reales de análisis de programas sobre datasets grandes (nullability, aliasing, etc.), y comparte aprendizajes sobre rendimiento, uso de memoria, optimización de consultas y mejora de planes de join

---

Introducción: experimentar con programación lógica Datalog en Rust

• Durante Memorial Day, en la conferencia Minnowbrook, se realizaron prácticas y discusiones sobre varios enfoques de programación lógica (como Datalog)
• Las herramientas Datalog existentes (Soufflé, ctdal, etc.) mostraron limitaciones en uso real, extensibilidad y rendimiento, lo que hizo más evidente la necesidad de una herramienta práctica
• El autor decidió implementar directamente en Rust un intérprete de Datalog (datatoad) que cumpliera al mismo tiempo con simplicidad, usabilidad y rendimiento
• Objetivo del proyecto: cargar grandes volúmenes de datos rápidamente desde la CLI, agregar y modificar reglas dinámicamente, ver resultados en tiempo real y mantener buen rendimiento de consulta

Conceptos básicos de Datalog

• Datalog se basa en expresiones lógicas con forma de reglas (Head :- Body) y deriva automáticamente todos los hechos inferibles a partir de los fact y rule dados
• Las reglas (por ejemplo, tri(a, b, c) :- edge(a, b), edge(b, c), edge(a, c)) están formadas por variables y literales
• Un fact es un valor verdadero sin condición (por ejemplo, edge(1, 2) :- .)
• Fortalezas de Datalog: al agregar reglas, crece el conjunto de información inferible (monotonicidad), y se obtiene el mismo resultado sin importar el orden de reglas o hechos (convergencia)
• En Rust, las reglas y los fact se representan con estructuras Atom/Rule/Term, y los conjuntos de hechos se administran por relación

Diseño de la estructura principal

Representación de datos

• Un Fact se diseñó inicialmente como Vec<String>, y el conjunto de hechos como algo similar a BTreeMap<String, Vec<Fact>>
• Para optimizar datos a gran escala, se introdujo una estructura columnar para minimizar el overhead de asignación
• FactContainer: conjunto de hechos ordenado, sin duplicados y con estructura append-only
• FactLSM: administra varios niveles de FactContainer con un enfoque LSM (Log-structured merge-tree), mejorando la eficiencia de inserción, ordenamiento y fusión
• FactSet: administra el ciclo de vida de los hechos (recién agregados, recién derivados, estabilizados) para evitar cálculos duplicados y desperdicio innecesario de memoria

Aplicación de reglas e inferencia

• Cada regla genera un JoinPlan y luego realiza inferencia con merge join según el orden de columnas y la combinación de claves más adecuada
• merge join: ordena las columnas clave de cada átomo del cuerpo y solo deriva nuevos hechos cuando las claves de join coinciden, maximizando el rendimiento
• Con la estructura stable/recent/to_add de FactSet, separa los hechos ya derivados de los nuevos para evitar recálculos innecesarios (evaluación diferencial)
• Bucle .update(): aplica todas las reglas repetidamente hasta que ya no se deriven nuevos hechos, y continúa la inferencia hasta llegar a un punto fijo

Implementación del parser

• Soporta una gramática estilo Soufflé (?var, :-, ., ,, etc.) y se implementó un tokenizer/parser directamente en Rust
• En caso de error, devuelve None de forma segura, con un diseño simple de parser adecuado para un entorno experimental

Optimización de rendimiento y ejemplos reales de análisis

Análisis de nullability (reachability)

• Define reglas Datalog para rastrear rutas de copia y movimiento de valores en datasets grandes (por ejemplo, httpd_df) y mide el rendimiento
• El rendimiento varía drásticamente según el patrón de escritura de reglas (binding de variables, orden de columnas, aparición de relaciones temporales según el plan de join, etc.)
• Según la forma inicial de los datos y la estrategia de join, el tiempo de ejecución y el uso de memoria pueden diferir en decenas de veces, mostrando directamente la importancia de optimizar consultas
• Al aplicar optimizaciones, se confirmó una mejora de rendimiento de más de 10 a 80 veces frente a herramientas existentes basadas en C++ (como Graspan)

Análisis de aliasing (points-to)

• Implementa patrones Datalog complejos para análisis de aliasing y seguimiento de punteros, ejecutando las mismas consultas que en artículos como Graspan y Zheng-Rugina
• Expande las operaciones de repetición (^*), opción (^?) y transposición (^T) dentro de reglas Datalog mediante recursión explícita y union
• Según cómo se diseñen el naming y la reutilización de resultados intermedios (como relation alias o temp join), cambia enormemente la eficiencia del plan de consulta completo y el consumo de recursos
• Si se generan grandes resultados intermedios sin optimizar el plan de consulta, se provoca degradación del rendimiento y explosión de memoria (por ejemplo, en la relación V)
• Se discute un enfoque "demand-driven" (transformación magic sets) que produce solo los resultados necesarios, y se plantea la posibilidad real de modificar el plan de consulta y mejorar el rendimiento

Lecciones obtenidas al experimentar directamente con Rust

• La clave del rendimiento de un motor Datalog está en la representación de datos (columnar/LSM), la inferencia diferencial y la optimización del plan de joins
• Si las reglas se escriben de forma mecánica, se termina generando datos intermedios innecesarios y desperdiciando recursos, por lo que la optimización es indispensable
• Al experimentar directamente en Rust, es posible administrar de forma eficiente hechos con millones y decenas de millones de filas en datasets reales, logrando al mismo tiempo escalabilidad y velocidad de inferencia
• En un entorno CLI es fácil probar carga masiva de datos, incorporación de reglas en tiempo real y verificación de resultados
• El papel del query optimizer, los joins tipo bushy-tree (aprovechando resultados intermedios) y el hábito de evitar generar relaciones innecesarias ofrecen ideas muy útiles para escribir y operar Datalog en la práctica

Próximos retos de expansión

• Quedan pendientes temas de investigación como spill a disco, escalado distribuido con múltiples workers/procesos, streaming joins y optimizaciones de compilación personalizadas
• El uso de Datalog en Rust tiene alto potencial en áreas prácticas como análisis de programas a gran escala, inferencia sobre grafos y relaciones, análisis estático y rastreo de flujo de datos

[GN⁺]

Comentarios de Hacker News

• Es curioso vivir la situación de que este artículo esté arriba justo ahora. Estoy trabajando en crear un juego de estrategia en tiempo real usando Differential Datalog (este repositorio) y Rust. La idea es que DDL se encargue de la lógica del juego, y también aprovechar para aprender ideas nuevas y acumular varias experiencias de prueba y error.
  • Tengo interés en ver cómo avanza y me da curiosidad saber cuál será el resultado.
  • Como el desarrollo de Differential Datalog está inactivo, me pregunto hasta dónde llega esa implementación y qué tan terminada está hoy.
• Compartiendo una experiencia en la que logré avanzar un poco al portar mangle datalog a Rust. La implementación en Rust se puede ver aquí, y la versión en golang está en el mismo repositorio. El trabajo va lento en parte porque no es una prioridad alta, pero también por el fenómeno de second system syndrome (cuando en el segundo sistema uno quiere hacer más cosas que en el primero y termina avanzando más despacio). La versión de mangle en Rust puede leer y escribir datos desde disco en cualquier momento mediante memory mapping, así que puede manejar grandes volúmenes de datos. La versión en golang, en cambio, carga todo en memoria para procesarlo. Lo bueno de este artículo es que la construcción del parser de datalog está bien explicada y menciona árboles LSM, así que se entiende bien; además, es mucho más fácil de seguir que data frog. En Rust también existen varias implementaciones de datalog como ascent y crepe usando proc-macros, pero tienen limitaciones para procesar consultas dinámicamente en tiempo de ejecución. Si se trata de un caso de análisis estático donde la consulta y el programa están fijos, creo que el enfoque con proc macro también es bastante bueno.
• Da gusto ver que un grupo de entusiastas de datalog sigue reuniéndose y manteniéndose activo. Últimamente parece que el renacimiento de datalog se ha frenado un poco: la conferencia Datalog 2.0 también fue más pequeña que antes, y en la segunda edición de HYTRADBOI disminuyeron bastante las discusiones sobre datalog. Recuerdo que en la primera edición una cuarta parte de los papers eran sobre datalog. Que otras personas compartan sus experiencias recientes con proyectos de datalog anima mucho. Estos días estoy preparando una gran migración de software desde una base de datos SQL antigua y construyendo un pipeline de calidad de datos. Si las consultas datalog están bien estructuradas, me parecen mucho más legibles y una herramienta mucho más eficiente que SQL para explorar problemas de calidad de datos.
  • Hay una opinión de que la baja asistencia a la conferencia Datalog 2.0 no se debe tanto a un declive de datalog como a la estructura del evento. Datalog 2.0 fue un evento satélite de LPNMR, una conferencia europea menos conocida, y esta vez se realizó algo aleatoriamente en Dallas, Estados Unidos. Yo también envié un paper a Datalog 2.0, pero el autor principal era otra persona, y en la práctica tampoco participaron muchos investigadores del área de datalog. Sí destacó la presencia de participantes europeos que presentaron el solver Nemo. En resumen, estoy de acuerdo en que la baja asistencia de este año se explica más por las particularidades del evento y por ser una actividad satélite, y también en que ya no queda una gran innovación pendiente en la implementación misma de motores datalog. La investigación actual está avanzando hacia temas más interesantes que el datalog básico, como stream-based (HydroFlow), choice (Dusa) y chase engines (Egglog). Los enfoques monotonic y chain-forward saturation (Horn clauses) ya están suficientemente establecidos desde el punto de vista de ingeniería, así que ahora se está explorando teoría nueva por encima de eso, como semirings y Z-sets.
• Creo que el autor es muy bueno trabajando con datalog, pero me decepciona que en la introducción enseñe binary join, porque fuera de situaciones ideales eso se complica muy rápido. Me parece que los enfoques de la familia generic join se generalizan de forma más intuitiva. Recomiendo ver la explicación en wiki sobre algoritmos de join óptimos en el peor caso.
  • Relacionado con eso, en una entrada anterior del blog de McSherry se puede ver el proceso en el que demuestra que los binary joins también pueden alcanzar tiempos de ejecución óptimos en el peor caso mediante ajustes adecuados del plan de consulta. Referencia al post del blog.
• En la apertura de ese post del blog, la frase "I, a notorious villain, was invited for what I was half sure was my long-due comeuppance." fue, para mí, la mejor apertura de un blog técnico de este año. A lo largo de todo el texto destacó el tono divertido del autor, y no es común encontrar un escrito que haga tan entretenido un tema técnico tan profundo. La forma en que cuenta el recorrido de optimización de consultas con aliasing resulta tan interesante como una novela detectivesca. Uno termina frustrándose con los 50 GB de memoria usados y celebrando junto con él cuando logra optimizarlo a 5 GB. Tanto el código como la escritura me parecieron excelentes.
• Hace tiempo escuché a algunos fans de Clojure decir que datalog era superior a SQL y lamentarse de que las bases de datos relacionales solo soportaran SQL. Nunca profundicé personalmente en por qué lo pensaban.
  • No estoy familiarizado con los dialectos de datalog de Clojure o Datomic, pero sí simpatizo con datalog en sí. Recomiendo Percival para probar datalog en un entorno de notebooks en línea: percival.ink. Una vez que aprendes los conceptos básicos de datalog, es fácil cambiar entre implementaciones. Incluso hice un fork de Percival para crear una versión que compila datalog a SQLite; la versión fork todavía no tiene terminadas las funciones de agregación ni los joins avanzados, pero las consultas básicas funcionan bien. Logica es un compilador mucho más serio y pulido de datalog->SQL creado por un investigador de Google, con soporte para varios dialectos SQL como BigTable y DuckDB; ver Logica. Cuando se trata de consultas o reglas recursivas, me impresionó lo mucho más fácil que resulta datalog. En SQL también se puede, pero se siente como beber arcilla con un popote. Materialize.com, creado por Frank McSherry, ofrece una forma SQL de “WITH MUTUALLY RECURSIVE”; ver el blog de Materialize. Estoy considerando usarlo para consultas de carga de páginas y sincronización de datos en Notion. Feldera también tiene una forma similar para vistas recursivas; ver este post del blog de Feldera. La ventaja de Feldera es que cada “regla” o subvista puede escribirse como un statement independiente, en vez de meterlo todo en una sola sentencia. La desventaja es que la sintaxis SQL tiene muchas restricciones heredadas de Apache Calcite. Materialize SQL me da la impresión de estar haciendo un buen esfuerzo por mantener compatibilidad con PostgreSQL.
• Recuerdo haber visto hace poco comentarios de que VMware se alejó de differential datalog. Por eso da gusto ver este nuevo texto de McSharry.
  • El equipo de Differential Datalog fundó una empresa llamada Feldera, que se puede ver en el sitio web de Feldera. Supongo que el motivo para pasar de differential datalog a differential SQL fue que datalog es difícil de adoptar realmente en el mercado.
• Si quieres usar datalog y Rust juntos, recomiendo cozodb. Cozodb está escrito en Rust y soporta sintaxis de consultas datalog.
  • Cozodb también parece un proyecto interesante, pero da la impresión de estar inactivo. Al revisar el código fuente alrededor de noviembre de 2024, encontré un punto que parecía fácil de mejorar en el backend de almacenamiento sqlite (issue #285).
• Comparten el enlace a una publicación relacionada que apareció en Hacker News hace 1 día: ir al post