▲

Rust에서 상호작용형 Datalog 엔진 만들기

 (github.com/frankmcsherry)
1P by GN⁺ 1일전 | ★ favorite | 댓글 1개
  • Datalog 논리 프로그래밍과 Rust의 효율성을 결합하여, 심플하면서도 사용성이 높고, 성능까지 고려한 상호작용형 Datalog 엔진 개발 과정을 상세하게 공유함
  • 직관적 CLI 환경에서 규칙(rule)과 사실(fact)을 실시간으로 추가/확장 가능, 대량 데이터 적재, 동적 규칙 입력 및 빠른 쿼리 성능까지 경험할 수 있음
  • 파싱(Parsing), 데이터 표현(Representation), 규칙 평가(Planning/Evaluation) 를 단계별로 Rust 코드와 함께 설명해 실제 구현 방법을 익힐 수 있음
  • 최적화되지 않은 단순 구현부터 시작해 점진적으로 성능과 구조를 개선하는 과정을 통해, 데이터 병렬처리/조인 최적화 등 고급 로직도 학습할 수 있음
  • 대규모 데이터셋 기반 프로그램 분석(Nullability, Aliasing 등) 사례를 실제로 실행하며 성능 및 메모리 이슈, 쿼리 최적화, join-plan 개선 노하우를 공유함

도입: Rust에서 Datalog 논리 프로그래밍 실험

  • Memorial Day 기간, Minnowbrook 컨퍼런스에서 다양한 논리 프로그래밍(Datalog 등) 실습과 토론 진행
  • 기존 Datalog 도구들(Soufflé, ctdal 등)은 실제 사용/확장성/성능 측면에서 한계 발견, 실용적 도구 필요성 부각
  • 필자는 직접 Rust로 심플/사용성/성능을 모두 만족하는 Datalog 인터프리터(datatoad)를 구현하기로 결정
  • 프로젝트 목표: CLI에서 대용량 데이터를 빠르게 적재하고, 동적으로 규칙 추가/수정하며, 실시간 결과 확인 및 쿼리 성능도 확보

Datalog 기본 개념

  • Datalog는 규칙(Head :- Body) 형태의 논리문을 기반으로, 주어진 fact와 rule로부터 모든 도출 가능한 사실을 자동 유도
  • 규칙(예: tri(a, b, c) :- edge(a, b), edge(b, c), edge(a, c))은 변수/리터럴로 이루어짐
  • fact는 조건 없는 참인 값(예: edge(1, 2) :- .)
  • Datalog의 강점: 규칙 추가 시 추론 가능한 정보 집합이 늘어나고(단조성), 규칙/사실 순서에 상관없이 동일 결과를 도출(수렴성)
  • Rust로는 규칙과 fact를 Atom/Rule/Term 구조체로 표현, relation 별로 fact 집합을 관리함

핵심 구조 설계

데이터 표현

  • Fact는 Vec<String>으로, fact 집합은 BTreeMap<String, Vec<Fact>> 등으로 초기 설계
  • 대용량 데이터 최적화를 위해 columnar(칼럼 지향) 데이터 구조 도입(alloc overhead 최소화)
  • FactContainer: 정렬/중복제거된 fact 집합, append only 구조
  • FactLSM: FactContainer를 여러 계층으로 관리하는 LSM(Log-structured merge-tree) 방식, 삽입 및 정렬/병합 효율화
  • FactSet: fact의 lifecycle(새로 추가, 최근 도출, 안정화된 fact)을 관리하여 중복 계산, 불필요한 메모리 낭비 방지

규칙 적용과 추론

  • 각 규칙은 JoinPlan(조인 플랜) 생성 → 적절한 컬럼 순서/키 조합을 기반으로 merge join 방식으로 추론
  • merge join: body atom별로 key 컬럼 정렬 후, 조인키가 일치하는 경우에만 새로운 fact 도출(성능 극대화)
  • FactSet의 stable/recent/to_add 구조를 활용해, 이미 도출된 fact와 신규 fact를 분리하여 불필요한 재계산 방지(차분 평가)
  • .update() 루프: 신규 fact 도출이 멈출 때까지 모든 규칙 반복 적용, fixpoint 도달 시까지 추론 반복

파서 구현

  • Soufflé 스타일 문법(?var, :-, ., , 등) 지원, Rust로 직접 토크나이저/파서 작성
  • 오류 발생 시 안전하게 None 반환, 실험적 환경에 맞는 심플 파서 설계

성능 최적화와 실제 분석 예시

Nullability 분석(Reachability)

  • 대용량 데이터셋(예: httpd_df)에서 값 복사/이동 경로 추적을 위한 Datalog 규칙 정의 및 성능 측정
  • 다양한 규칙 작성 패턴에 따라 성능 차이 극심(변수 바인딩/컬럼 순서/조인 플랜에 따른 temp relation 발생 등)
  • 데이터 초기 형태/조인 전략에 따라 실행 시간, 메모리 사용량이 수십 배 차이 발생, 쿼리 최적화의 중요성 직접 체험
  • 최적화 적용 시 기존 C++ 기반 도구(Graspan 등) 대비 10~80배 이상 성능 개선 확인

Aliasing 분석(Points-to)

  • aliasing/포인터 추적 분석을 위한 복잡한 Datalog 패턴 구현, 논문(Graspan, Zheng-Rugina 등)과 동일한 쿼리 실행
  • Datalog 규칙 내 반복(^*), 옵션(^?), 전치(^T) 연산을 명시적 재귀/union으로 확장
  • 중간 결과(relation alias, temp join 등)의 네이밍/재사용 설계에 따라, 전체 쿼리 플랜의 효율 및 자원 소모 대폭 차이
  • 쿼리 플랜 최적화 없이 큰 중간 결과를 생성하면, 성능 저하와 메모리 폭증을 초래(예: V relation)
  • 필요한 결과만 산출하는 "demand-driven" 방식(매직셋 변환) 논의, 실제 쿼리 플랜 변형 및 성능 개선 가능성 제시

Rust로 직접 실험하며 얻은 교훈

  • Datalog 엔진 성능의 핵심은 데이터 표현(칼럼ar/LSM), 차분 추론, join 플랜 최적화에 있음
  • 단순히 규칙을 기계적으로 작성하면, 불필요한 중간 데이터 생성과 리소스 낭비로 이어짐(최적화 필요)
  • Rust로 직접 실험하며, 실전 데이터셋에서 수백만/수천만 row의 fact를 효율적으로 관리하고, 확장성과 추론 속도를 동시에 달성할 수 있음
  • CLI 환경에서 대규모 데이터 적재, 실시간 규칙 추가, 결과 확인까지 손쉽게 실험 가능
  • query optimizer의 역할, bushy-tree join(중간 결과 활용), 필요 없는 관계의 생성을 피하는 습관 등, 실제 Datalog 작성 및 운영에 큰 시사점

앞으로의 확장 과제

  • 디스크 스필, 다중 워커/프로세스 분산 확장, 스트리밍 조인, 커스텀 컴파일 최적화 등 연구 과제 남아 있음
  • 대규모 프로그램 분석, 그래프/관계 추론, 정적분석, 데이터 흐름 추적 등 실전 분야에서 Rust Datalog의 활용 가능성 높음
▲
GN⁺ 1일전  [-]
Hacker News 의견
  • 지금 이 글이 상위에 떠 있는 게 재밌는 상황 경험 중 설명 Differential Datalog(이 저장소)과 Rust를 활용해서 실시간 전략 게임 만드는 작업 진행 중 DDL이 게임 로직을 담당하는 구조이고, 새로운 아이디어를 배워보고 여러 삽질 경험을 쌓으려는 의도
    • 진행 상황 기대 중인 입장 설명, 결과가 궁금해지는 상황
    • Differential Datalog 개발이 비활성화된 상황이라서, 그 구현이 어디까지 가능한지, 지금 어느 정도 완성되어 있는지 궁금한 상태
  • mangle datalog을 Rust로 포팅하려고 조금 진전 이뤄낸 경험 공유 Rust 구현은 여기에서 확인 가능 golang 버전과 같은 저장소에 존재 작업이 더딘 이유는 우선순위가 낮은 것도 있지만, 'second system syndrome' 현상(처음 만든 것보다 두 번째 만들 때 욕심이 많아져 작업이 느려지는 현상) 때문임 Rust 버전의 mangle은 메모리 매핑을 통해 언제든지 디스크에서 데이터를 가져오고 쓸 수 있어 대용량 데이터 처리 가능 golang 버전은 전체 데이터를 메모리에 올려 처리하는 구조임 이 글이 좋은 점은 datalog 파서 구성이 잘 되어있고, LSM 트리 언급이 있어 이해가 잘 된다는 점, data frog에 비해 훨씬 따라가기 쉽다는 점 Rust에는 proc-macros를 활용한 ascent, crepe 등 다양한 datalog 구현이 존재하지만, 실행 중 쿼리를 동적으로 처리하는 데는 제약이 있음 쿼리와 프로그램이 고정된 정적 분석 케이스라면 proc macro 접근법도 충분히 훌륭하다고 생각하는 입장
  • datalog 열정가들 일부가 꾸준히 모여 활동하는 모습이 보기 좋은 상황 최근 datalog 르네상스가 주춤하는 분위기인데, Datalog 2.0 컨퍼런스도 예전에 비해 소규모였고, HYTRADBOI 컨퍼런스 2회차에서는 datalog 관련 논의 자체가 크게 줄었음 첫 번째 대회에서는 논문의 1/4이 datalog 관련이었던 기억 다른 참가자들이 최근 datalog 프로젝트 경험을 나눠주는 게 큰 힘이 됨 요즘 구식 SQL 데이터베이스에서 대규모 소프트웨어 마이그레이션을 준비하며 데이터 품질 파이프라인을 만들고 있는 중 datalog 쿼리는 잘 구조화하면 가독성이 높아서, 데이터 품질 문제 탐색에 SQL보다 훨씬 효율적인 도구라고 생각
    • Datalog 2.0 컨퍼런스 참석 인원 적은 게 datalog 자체의 침체라기보다는 행사 구조 문제의 영향이 크다는 의견 Datalog 2.0은 LPNMR이라는 덜 알려진 유럽 컨퍼런스의 위성 행사였고, 이번에는 미국 Dallas에서 랜덤하게 진행됨 본인도 Datalog 2.0에 논문을 제출했으나, 핵심 저자는 따로 있었고, 실제로 datalog 분야 종사자도 행사에 별로 참여하지 않았음 Nemo solver를 발표한 유럽 쪽 참가자가 눈에 띄던 상황 요지는 올해 Datalog 2.0 참석자 수 적었던 것은 행사 자체의 특수성과 위성 행사였던 점이 더 크고, datalog 엔진 구현 자체에 대해 큰 혁신은 남아있지 않다는 관점에서는 동의 실제 연구 흐름은 기본 datalog보다는 stream 기반(HydroFlow), choice(Dusa), chase engine(Egglog) 등 더 흥미로운 주제로 발전 monotonic, chain-forward saturation(Horn clauses)가 엔지니어링적으로 충분히 정립된 방법이라서, 이 위에 semirings, Z-sets 등 새로운 이론 탐구가 이루어지고 있는 상황 설명
  • 필자가 datalog 관련 작업을 잘 한다고 생각하지만, 도입부에서 binary join을 가르치는 방식은 이상적 상황이 아니면 금방 복잡해져서 아쉽다는 입장 generic join 계열 방식이 더 직관적으로 일반화 가능하다는 생각 worst-case optimal join algorithm에 대한 wiki 설명 참고 권장
    • 관련 이야기로, McSherry의 이전 블로그 글에서는 binary join을 적절한 쿼리 플랜 조정으로 worst-case 최적화 런타임 달성 가능함을 증명한 과정 확인 가능 블로그 포스트 참고 안내
  • 해당 블로그 포스트 오프닝에서 "I, a notorious villain, was invited for what I was half sure was my long-due comeuppance."라는 문장이 가장 인상적이었던 올해 최고의 기술 블로그 글 오프닝이라는 생각 글 내내 작가의 유쾌한 서술이 돋보였고, 이렇게 깊이 있는 기술적 주제를 재미있게 읽을 수 있는 글은 드물다는 생각 aliasing 쿼리 최적화 여정을 탐정 소설처럼 흥미롭게 풀어낸 구성 50GB 메모리 사용에 좌절하고, 5GB로 최적화 성공했을 때 같이 응원하게 되는 느낌 코드와 글 솜씨 모두 훌륭하다고 평가
  • 예전에 몇몇 Clojure 팬이 datalog가 SQL보다 더 우수하다고 믿었고, 관계형 DB들이 전부 SQL만 지원하는 게 아쉽다고 말하던 경험 들은 적 있음 왜 그렇게 생각하는지는 직접 파고들어보진 못함
    • Clojure나 Datomic의 datalog 방언은 나에게는 익숙하지 않지만, datalog 자체에는 공감하는 입장 온라인 notebook 환경에서 datalog를 활용해볼 수 있는 Percival 추천 percival.ink 활용, datalog의 핵심 개념만 익히면 구현마다 손쉽게 전환 가능 Percival을 fork해서 datalog를 SQLite로 컴파일하는 버전도 만든 경험 있음, 포크 버전은 아직 집계 함수나 고급 조인은 미완성 상태이지만 기본 쿼리는 잘 동작함 Logica는 Google 연구원이 만든 훨씬 진지하고 완성도 높은 datalog->SQL 컴파일러로, BigTable, DuckDB 등 다양한 SQL 방언 지원 Logica 참고 재귀 쿼리/규칙을 다룰 때 datalog가 월등히 쉽다는 점이 인상적 SQL로는 가능은 하지만 마치 점토를 빨대로 마시는 느낌 Frank McSherry가 만드는 Materialize.com은 “WITH MUTUALLY RECURSIVE” SQL 형태를 제공하며, Materialize 블로그 참고 중 Notion의 페이지 로드 쿼리와 데이터 동기화에 활용 검토 중 Feldera도 재귀 뷰를 위한 유사한 폼이 있음 Feldera 블로그 포스트 참고 Feldera의 장점은 각 “규칙” 혹은 서브뷰를 독립된 statement로 분리해 작성 가능, 반면 한 문장에 모두 담을 필요 없음 단점은 SQL 문법이 Apache Calcite에서 온 제약이 많다는 점 Materialize SQL은 PostgreSQL 호환성에 노력 중인 인상
  • 얼마 전까지 VMware가 differential datalog에서 멀어졌다는 이야기 본 것 기억 McSharry의 새로운 글이 반가운 상황
    • Differential Datalog 팀이 Feldera라는 회사를 설립했고, Feldera 웹사이트에서 확인 가능 differential datalog에서 differential SQL로 전환하게 된 이유는 datalog가 시장에서 실제로 채택되기 어렵다는 점 때문이라고 추정
  • datalog와 Rust를 함께 쓰고 싶다면 cozodb 추천 cozodb는 Rust로 작성되어 datalog 쿼리 문법 지원
    • cozodb도 흥미로운 프로젝트지만 비활성화된 프로젝트로 보임 2024년 11월쯤에 소스 코드를 살펴보면서 sqlite 저장 백엔드에 간단하게 개선할 수 있는 포인트(이슈 #285)를 발견한 경험 있음
  • Hacker News에 1일 전에 올라온 관련 글 링크 제공 게시글 바로가기
답변달기