Criando um motor de Datalog interativo em Rust

• Combina a programação lógica em Datalog com a eficiência de Rust, compartilhando em detalhes o processo de desenvolvimento de um motor de Datalog interativo que é simples, fácil de usar e também pensado para desempenho
• Permite adicionar e expandir regras (rule) e fatos (fact) em tempo real em um ambiente de CLI intuitivo, além de carregar grandes volumes de dados, inserir regras dinamicamente e obter consultas rápidas
• Explica parsing, representação de dados e avaliação de regras (Planning/Evaluation) passo a passo com código Rust, facilitando o aprendizado da implementação real
• Parte de uma implementação simples e não otimizada e melhora gradualmente desempenho e estrutura, permitindo aprender também lógica avançada como paralelismo de dados e otimização de joins
• Executa casos reais de análise de programas com grandes datasets (como nullability e aliasing), compartilhando experiência prática sobre desempenho, uso de memória, otimização de consultas e melhorias em planos de join

---

Introdução: experimentando programação lógica com Datalog em Rust

• Durante o feriado de Memorial Day, foram realizados exercícios e discussões sobre várias formas de programação lógica (incluindo Datalog) na conferência Minnowbrook
• Ferramentas de Datalog já existentes, como Soufflé e ctdal, mostraram limitações em uso real, extensibilidade e desempenho, reforçando a necessidade de uma ferramenta mais prática
• O autor decidiu implementar diretamente em Rust um interpretador de Datalog (datatoad) que atendesse simultaneamente aos requisitos de simplicidade, usabilidade e desempenho
• Objetivo do projeto: carregar rapidamente grandes volumes de dados em uma CLI, adicionar e modificar regras dinamicamente, verificar resultados em tempo real e ainda manter bom desempenho em consultas

Conceitos básicos de Datalog

• Datalog é baseado em sentenças lógicas no formato de regras (Head :- Body) e deduz automaticamente todos os fatos deriváveis a partir de fact e rule fornecidos
• Regras (ex.: tri(a, b, c) :- edge(a, b), edge(b, c), edge(a, c)) são compostas por variáveis e literais
• fact é um valor verdadeiro sem condição (ex.: edge(1, 2) :- .)
• Pontos fortes do Datalog: ao adicionar regras, o conjunto de informações inferíveis aumenta (monotonicidade), e o resultado final é o mesmo independentemente da ordem de regras e fatos (convergência)
• Em Rust, regras e fatos são representados com structs como Atom, Rule e Term, e os conjuntos de fatos são gerenciados por relação

Projeto da estrutura central

Representação dos dados

• Fact foi inicialmente modelado como Vec<String>, e o conjunto de fatos como algo como BTreeMap<String, Vec<Fact>>
• Para otimizar grandes volumes de dados, foi introduzida uma estrutura columnar orientada a colunas, minimizando overhead de alocação
• FactContainer: conjunto de fatos ordenado, sem duplicatas e com estrutura append-only
• FactLSM: gerencia FactContainer em múltiplas camadas no estilo LSM (Log-structured merge-tree), melhorando inserção, ordenação e merge
• FactSet: gerencia o ciclo de vida dos fatos (novos, recentemente deduzidos, estabilizados), evitando cálculos duplicados e desperdício de memória

Aplicação de regras e inferência

• Cada regra gera um JoinPlan, e a inferência é feita por merge join com base em uma combinação adequada de ordem de colunas e chaves
• merge join: ordena as colunas-chave de cada átomo do corpo e só deduz novos fatos quando as chaves de join coincidem, maximizando desempenho
• Com a estrutura stable/recent/to_add de FactSet, separa fatos já deduzidos de fatos novos para evitar recálculos desnecessários (avaliação diferencial)
• Loop .update(): reaplica todas as regras até que a dedução de novos fatos pare, repetindo a inferência até atingir o ponto fixo

Implementação do parser

• Suporta sintaxe no estilo Soufflé (?var, :-, ., , etc.), com tokenizer e parser implementados manualmente em Rust
• Em caso de erro, retorna None com segurança, mantendo um parser simples adequado a um ambiente experimental

Otimização de desempenho e exemplos reais de análise

Análise de nullability (reachability)

• Define regras de Datalog e mede desempenho em datasets grandes (ex.: httpd_df) para rastrear caminhos de cópia e movimentação de valores
• Dependendo do padrão de escrita das regras, a diferença de desempenho é extrema (por causa de binding de variáveis, ordem de colunas e geração de relações temporárias pelo plano de join)
• Conforme a forma inicial dos dados e a estratégia de join, tempo de execução e uso de memória podem variar em dezenas de vezes, evidenciando a importância da otimização de consultas
• Com otimizações aplicadas, houve melhora de 10 a mais de 80 vezes em relação a ferramentas tradicionais baseadas em C++, como Graspan

Análise de aliasing (points-to)

• Implementa padrões complexos de Datalog para análise de aliasing e rastreamento de ponteiros, executando as mesmas consultas de artigos como Graspan e Zheng-Rugina
• Expande explicitamente operações de repetição (^*), opcional (^?) e transposição (^T) em regras de Datalog por meio de recursão e union
• Dependendo do projeto de nomes e reutilização de resultados intermediários (como relation alias e joins temporários), a eficiência e o consumo de recursos do plano de consulta completo mudam drasticamente
• Se grandes resultados intermediários forem gerados sem otimização do plano de consulta, isso causa queda de desempenho e explosão no uso de memória (ex.: relação V)
• Discute uma abordagem "demand-driven" (transformação magic set) que produz apenas os resultados necessários, sugerindo possibilidades reais de alteração do plano de consulta e melhoria de desempenho

Lições aprendidas ao experimentar diretamente com Rust

• O núcleo do desempenho de um motor de Datalog está na representação de dados (columnar/LSM), inferência diferencial e otimização de planos de join
• Escrever regras apenas de forma mecânica leva à geração de dados intermediários desnecessários e desperdício de recursos, o que torna a otimização essencial
• Ao experimentar diretamente em Rust, é possível gerenciar com eficiência fatos com milhões e dezenas de milhões de linhas em datasets reais, alcançando ao mesmo tempo escalabilidade e velocidade de inferência
• Em um ambiente de CLI, é fácil testar carregamento de grandes volumes de dados, adição de regras em tempo real e verificação de resultados
• O papel do query optimizer, joins em bushy tree (aproveitando resultados intermediários) e o hábito de evitar a criação de relações desnecessárias trazem implicações importantes para a escrita e operação prática de Datalog

Próximos desafios de expansão

• Ainda restam temas de pesquisa como spill para disco, expansão distribuída com múltiplos workers/processos, streaming join e otimizações de compilação customizadas
• O uso de Datalog em Rust tem alto potencial prático em áreas como análise de programas em larga escala, inferência em grafos e relações, análise estática e rastreamento de fluxo de dados

[GN⁺]

Comentário do Hacker News

• É engraçado ver este texto no topo agora. Estou trabalhando em um jogo de estratégia em tempo real usando Differential Datalog(este repositório) e Rust. A estrutura é tal que o DDL cuida da lógica do jogo, e a intenção é aprender ideias novas e acumular várias experiências de tentativa e erro.
  • Estou acompanhando com expectativa e curioso para ver o resultado.
  • Como o desenvolvimento de Differential Datalog está inativo, fico curioso sobre até onde essa implementação é viável e o quão completa ela está hoje.
• Compartilhando que consegui algum progresso tentando portar o mangle datalog para Rust. A implementação em Rust pode ser vista aqui, e a versão em golang está no mesmo repositório. O trabalho anda devagar porque a prioridade é baixa, mas também por causa do fenômeno de "second system syndrome" (quando, ao fazer a segunda versão, você fica mais ambicioso do que na primeira e o trabalho desacelera). A versão Rust do mangle pode ler e gravar dados do disco a qualquer momento por meio de memory mapping, então consegue lidar com grandes volumes de dados. A versão em golang carrega tudo na memória para processar. O bom deste texto é que a composição do parser de datalog está bem explicada e a menção a árvores LSM ajuda na compreensão; também é muito mais fácil de acompanhar do que data frog. Em Rust existem várias implementações de datalog com proc-macros, como ascent e crepe, mas elas têm limitações para processar consultas dinamicamente em tempo de execução. Se o caso for análise estática, com consultas e programa fixos, acho que a abordagem com proc macro é excelente.
• É bom ver que alguns entusiastas de datalog continuam se reunindo e produzindo coisas. Ultimamente parece que o renascimento do datalog perdeu fôlego: a conferência Datalog 2.0 também foi menor do que antes, e na segunda edição da HYTRADBOI as discussões sobre datalog diminuíram bastante. Lembro que na primeira edição um quarto dos artigos era sobre datalog. Ouvir outras pessoas compartilhando experiências recentes com projetos em datalog tem sido um grande incentivo. Atualmente estou preparando uma grande migração de software saindo de um banco SQL antigo e montando pipelines de qualidade de dados. Quando bem estruturadas, consultas em datalog ficam muito legíveis, então considero datalog uma ferramenta bem mais eficiente do que SQL para investigar problemas de qualidade de dados.
  • Na minha opinião, o baixo número de participantes na Datalog 2.0 diz mais sobre a estrutura do evento do que sobre uma estagnação do datalog em si. A Datalog 2.0 foi um evento satélite da LPNMR, uma conferência europeia pouco conhecida, e desta vez aconteceu meio aleatoriamente em Dallas, nos EUA. Eu mesmo submeti um artigo para a Datalog 2.0, mas o autor principal era outra pessoa, e na prática quase ninguém que trabalha diretamente com datalog participou do evento. O pessoal europeu que apresentou o solver Nemo se destacou. Em resumo, concordo que o público pequeno da Datalog 2.0 neste ano se explica muito mais pelas particularidades do evento e pelo fato de ser um satélite. Também concordo com a visão de que não resta muita inovação radical na implementação de motores de datalog em si. O fluxo de pesquisa real está avançando para temas mais interessantes do que datalog básico, como abordagens baseadas em stream (HydroFlow), choice (Dusa) e chase engines (Egglog). Métodos monotônicos de saturação chain-forward (Horn clauses) já estão suficientemente consolidados do ponto de vista de engenharia, então a exploração teórica agora acontece em cima disso, com semirings, Z-sets e afins.
• Acho que o autor manda muito bem em datalog, mas fiquei um pouco desapontado com a forma como ele ensina binary join no começo, porque isso fica complicado muito rápido fora de situações ideais. Tenho a impressão de que abordagens da família generic join se generalizam de forma mais intuitiva. Recomendo a explicação na wiki sobre algoritmos de join ótimos no pior caso.
  • A propósito, num post anterior do blog do McSherry dá para ver o processo em que ele provou que binary join pode atingir tempo de execução ótimo no pior caso com o ajuste adequado do plano de consulta. Veja este post do blog.
• A frase "I, a notorious villain, was invited for what I was half sure was my long-due comeuppance." no começo desse post foi, para mim, a melhor abertura de um blog técnico neste ano. O tom divertido do autor brilhou o texto inteiro, e é raro encontrar um texto que consiga tornar um tema técnico tão profundo tão prazeroso de ler. A jornada de otimização de consultas com aliasing foi narrada quase como um romance policial. Quando ele se desespera com 50 GB de uso de memória e depois consegue otimizar para 5 GB, dá vontade de torcer junto. Tanto o código quanto a escrita são excelentes.
• Há algum tempo ouvi alguns fãs de Clojure dizendo que datalog é superior a SQL e lamentando que os bancos de dados relacionais suportem apenas SQL. Nunca fui a fundo para entender exatamente por quê.
  • Embora eu não esteja acostumado aos dialetos de datalog de Clojure ou Datomic, simpatizo com datalog em si. Recomendo o Percival para experimentar datalog em um ambiente de notebook online: percival.ink. Depois de aprender os conceitos centrais de datalog, dá para migrar entre implementações com relativa facilidade. Também já fiz um fork do Percival com uma versão que compila datalog para SQLite; o fork ainda não tem funções de agregação nem joins avançados completos, mas as consultas básicas funcionam bem. O Logica é um compilador datalog->SQL muito mais sério e maduro, feito por pesquisadores do Google, com suporte a vários dialetos SQL como BigTable e DuckDB; veja Logica. O que mais impressiona é como datalog é muito mais fácil para lidar com consultas/regras recursivas. Em SQL até dá para fazer, mas parece tentar beber argila com um canudo. O Materialize.com, criado pelo Frank McSherry, oferece uma forma de SQL com “WITH MUTUALLY RECURSIVE”; veja o blog do Materialize. Estou avaliando usar isso nas consultas de carregamento de páginas e sincronização de dados do Notion. O Feldera também tem uma forma parecida para views recursivas; veja este post do blog da Feldera. A vantagem do Feldera é que cada “regra” ou subview pode ser escrita como um statement independente, em vez de precisar colocar tudo numa única instrução. A desvantagem é que a sintaxe SQL tem muitas limitações vindas do Apache Calcite. Já o SQL do Materialize passa a impressão de buscar compatibilidade com PostgreSQL.
• Lembro de ter visto recentemente que a VMware se afastou do differential datalog. Então foi bom ver esse novo texto do McSharry.
  • A equipe do Differential Datalog fundou a empresa Feldera, que pode ser vista no site da Feldera. Imagino que a mudança de differential datalog para differential SQL tenha acontecido porque datalog é difícil de emplacar no mercado real.
• Se você quiser usar datalog com Rust, recomendo o cozodb. O cozodb é escrito em Rust e oferece sintaxe de consulta em datalog.
  • O cozodb também parece um projeto interessante, mas me parece inativo. Por volta de novembro de 2024, ao olhar o código-fonte, encontrei um ponto que dava para melhorar facilmente no backend de armazenamento SQLite (issue #285).
• Link para um post relacionado que apareceu no Hacker News 1 dia atrás: ir direto ao post