Architecture

Module Structure#

src/
├── main.rs                     — binary entry point (interactive REPL)
├── lib.rs                      — public API exports
├── db.rs                       — public embedded API: Minigraf, OpenOptions, WriteTransaction; register_aggregate / register_predicate for UDFs; prepare(query_str) -> PreparedQuery
├── repl.rs                     — interactive Datalog REPL console
├── temporal.rs                 — UTC timestamp parsing (avoids chrono CVE GHSA-wcg3-cvx6-7396)
├── wal.rs                      — write-ahead log: WalWriter, WalReader, CRC32 entries
├── error.rs                    — structured error codes: MinigrafError, ErrorCategory, ErrorCode registry (PRS/QRY/STG/WAL/API/INT); matches docs/ERROR_REFERENCE.md
├── browser/                    — browser WASM backend (`browser` feature)
│   ├── buffer.rs               — BrowserBufferBackend: in-memory pages with dirty-page tracking
│   └── indexeddb.rs            — IndexedDB persistence for the browser backend
├── graph/
│   ├── types.rs                — Fact, Value, EntityId, Attribute, VALID_TIME_FOREVER
│   └── storage.rs              — FactStorage: in-memory EAV store with temporal query methods
├── query/datalog/
│   ├── parser.rs               — EDN/Datalog parser (incl. not / not-join / expr / window clauses with safety checks)
│   ├── executor.rs             — query executor with temporal filtering, not/not-join post-filters, eval_expr/is_truthy, apply_post_processing (aggregation + window)
│   ├── functions.rs            — FunctionRegistry: string-keyed aggregate/window/predicate registry; AggregateDesc, AggState, WindowOps; AggImpl discriminator (Builtin(WindowOps) vs Udf(UdfOps)); UdfOps (type-erased init/step/finalise closures via Box<dyn Any + Send>); PredicateDesc (Arc<dyn Fn(&Value) -> bool + Send + Sync>); register_aggregate / register_predicate / register_builtin_aggregate; all built-in aggregates registered at startup
│   ├── matcher.rs              — pattern matching engine with variable unification
│   ├── magic_sets.rs           — magic-sets rewriting for demand-driven recursive rules (not applied to rules with not/not-join)
│   ├── evaluator.rs            — RecursiveEvaluator + StratifiedEvaluator + evaluate_not_join + apply_expr_clauses_in_evaluator
│   ├── stratification.rs       — DependencyGraph, stratify(): negative edges + cycle detection
│   ├── rules.rs                — RuleRegistry: thread-safe rule management; stratify() on register
│   ├── optimizer.rs            — selectivity-based query plan optimizer (disabled under wasm); Expr clauses passed through unchanged
│   ├── prepared.rs             — PreparedQuery: parse-once/execute-many with named $slot bind slots; BindValue enum (Entity/Val/TxCount/Timestamp/AnyValidTime); prepare_query(), substitute(); 19 unit tests
│   └── types.rs                — EdnValue (incl. BindSlot), Pattern, DatalogQuery, AsOf (incl. Slot), ValidAt (incl. Slot), WhereClause, BinOp, UnaryOp, Expr (incl. Slot), WindowFunc, Order, WindowSpec, FindSpec::Window; WindowFunc::Udf(String) and UnaryOp::Udf(String) variants for user-defined functions (resolved at runtime)
└── storage/
    ├── mod.rs                  — StorageBackend trait, FileHeader v7, CommittedFactReader / CommittedIndexReader traits
    ├── persistent_facts.rs     — PersistentFactStorage: v7 save/load, auto-migration v1–v6→v7, CommittedFactLoaderImpl
    ├── index.rs                — EAVT/AEVT/AVET/VAET key types, FactRef, encode_value
    ├── btree.rs                — legacy paged-blob B+tree (v5 migration only)
    ├── btree_v6.rs             — on-disk B+tree: build_btree, OnDiskIndexReader, MutexStorageBackend
    ├── cache.rs                — LRU page cache: approximate-LRU, read-lock on hits
    ├── packed_pages.rs         — packed fact page format (~25 facts/4KB), MAX_FACT_BYTES
    └── backend/
        ├── file.rs             — FileBackend: single .graph file, cross-platform
        ├── memory.rs           — MemoryBackend: in-memory backend for testing
        └── fault_inject.rs     — FaultInjectingBackend: injects I/O errors for durability tests (test builds only)

Language bindings (separate repositories)#

The bindings moved out of this repository in #231. Each one has its own repository and release pipeline, and is rebuilt when a new minigraf crate is published.

Data Model#

The unit of storage is a Fact — an Entity-Attribute-Value triple extended with bi-temporal metadata:

struct Fact {
    entity:    EntityId,   // Uuid
    attribute: Attribute,  // String, e.g. ":person/name"
    value:     Value,
    tx_id:     TxId,       // Uuid — transaction that asserted this fact
    tx_count:  u64,        // monotonic transaction counter (used for :as-of queries)
    valid_from: i64,       // Unix ms — when fact became valid in the real world
    valid_to:   i64,       // Unix ms — i64::MAX = open-ended (valid forever)
    asserted:  bool,       // true = assert, false = retract
}

enum Value {
    String(String),
    Integer(i64),
    Float(f64),
    Boolean(bool),
    Ref(Uuid),        // reference to another entity
    Keyword(String),  // e.g. ":status/active"
    Null,
}

VALID_TIME_FOREVER = i64::MAX is the sentinel for open-ended valid time.

Storage Architecture#

Layered design#

┌─────────────────────────────────────┐
│  Minigraf / WriteTransaction (db.rs)│  ← public API
├─────────────────────────────────────┤
│  FactStorage (graph/storage.rs)     │  ← in-memory EAV + index-driven scans
│  PersistentFactStorage              │  ← persistence layer
├─────────────────────────────────────┤
│  PageCache (storage/cache.rs)       │  ← LRU page cache (default 256 pages = 1MB)
├─────────────────────────────────────┤
│  StorageBackend trait               │  ← platform-agnostic page I/O
│  FileBackend / MemoryBackend        │
└─────────────────────────────────────┘
       ↕ WAL sidecar (wal.rs)

Pending (uncommitted) facts live in memory. Committed facts are stored in packed pages on disk and resolved on demand via the CommittedFactReader trait — no load-all at startup. Index lookups go through OnDiskIndexReader (Phase 6.5), which traverses B+tree pages via the LRU cache; index memory usage is O(cache_pages), not O(facts).

Covering indexes#

Four Datomic-style covering indexes are maintained for each committed fact:

Each index entry is a FactRef { page_id, slot_index } — a pointer to the fact's location in the packed pages. Values are encoded with sort-order-preserving byte representation so range scans work correctly.

In v7, EavtKey and AevtKey carry no value, so two values of one attribute written in the same transaction share a key, and reads can return only one of them. This is known issue #371, fixed in v3.0.0.

File Format (v7)#

The .graph file is page-based (4KB pages), endian-safe, cross-platform.

Page 0: FileHeader (84 bytes)
  bytes  0.. 4   magic "MGRF"
  bytes  4.. 8   version u32 LE (currently 7)
  bytes  8..16   page_count u64 LE
  bytes 16..24   node_count u64 LE  (fact count)
  bytes 24..32   last_checkpointed_tx_count u64 LE
  bytes 32..40   eavt_root_page u64 LE  (B+tree root for each covering index)
  bytes 40..48   aevt_root_page u64 LE
  bytes 48..56   avet_root_page u64 LE
  bytes 56..64   vaet_root_page u64 LE
  bytes 64..68   index_checksum u32 LE  (CRC32 of committed fact pages)
  byte  68       fact_page_format u8    (0x02 = packed)
  bytes 69..72   _padding [u8; 3]
  bytes 72..80   fact_page_count u64 LE  (new in v6, retained in v7)
  bytes 80..84   header_checksum u32 LE  (new in v7 — CRC32 of header bytes 0..80)

Pages 1+: Packed fact data pages (page_type = 0x02)
  12-byte page header:
    byte  0       page_type (0x02)
    byte  1       _reserved (0x00)
    bytes 2..4    record_count u16 LE
    bytes 4..12   next_page u64 LE  (0 = no overflow)
  Record directory: record_count × 4 bytes
    per entry: offset u16 LE | length u16 LE
  Record data: variable-length postcard-serialised Facts
    (written end-to-start within the page)

Index pages (after fact pages): proper on-disk B+tree nodes (btree_v6.rs)
  Internal node page: sorted keys + child page IDs
  Leaf node page: sorted (key, FactRef) pairs + next_leaf pointer
  Each B+tree node is exactly one 4KB page

Serialisation: facts use postcard — lightweight, embedded-focused, endian-safe.

Migration: from_bytes auto-migrates v1/v2/v3/v4/v5/v6 headers on open. v6 databases migrate to v7 on first checkpoint (header_checksum field added).

WAL (Write-Ahead Log)#

The WAL sidecar (<db>.wal) is present whenever there are uncommitted writes. It is replayed on open and deleted on checkpoint.

WAL file layout:
  Header: magic "MWAL", version u32 (1)
  Entries (repeated):
    checksum u32     — CRC32 of the rest of the entry
    tx_count u64     — transaction counter
    num_facts u64    — number of facts in this entry
    [ len u32 | postcard-bytes ]×num_facts

CRC32-protected entries ensure partial writes (from crashes) are safely discarded. Every WAL write is followed by a flush to disk, controlled by OpenOptions::synchronous (see Performance Tuning):

• SyncMode::Full (default) — fdatasync after every entry. Matches Minigraf's original always-fsync behavior; every committed transact/retract is durable immediately.
• SyncMode::Normal — no per-write flush. Entries are still write_all()'d (safe across an ordinary process crash) but not forced to disk until the next checkpoint (auto-threshold, explicit checkpoint(), or clean close). Data written since the last checkpoint is lost only on OS crash or power loss, not process death. Intended for bulk loaders that can safely re-run from a checkpoint watermark.

checkpoint() itself always fsyncs the main .graph file regardless of synchronous — it remains the hard durability boundary in both modes.

Query Execution Pipeline#

1. Parse — EDN string → DatalogQuery; not / not-join / Expr clauses safety-checked at this stage; regex patterns in matches? validated at parse time
2. Plan — optimizer.rs selects an index hint and reorders join clauses by selectivity; Expr clauses are passed through unchanged (not reordered — ordering guaranteed by safety check)

3. Execute — executor.rs iterates patterns, resolves FactRefs via page cache, applies temporal filter:

• Step 1: tx-time filter (:as-of counter or timestamp)
• Step 2: net-assertion filter — per (entity, attribute, value) triple, keep only the latest tx_count; discard if that record is a retraction (asserted = false)

 (Known issue [#435](https://github.com/project-minigraf/minigraf/issues/435): v2.x keeps the latest record per valid-time window rather than per triple, so a later assertion of the same fact with a different window does not replace the earlier window. Fixed in v3.0.0.)

• Step 3: valid-time filter (:valid-at or :any-valid-time)
• Step 4: not / not-join post-filter — applied per candidate binding after pattern matching
• Step 5: Expr clause evaluation (apply_expr_clauses) — filter predicates drop non-truthy rows; arithmetic bindings extend the binding with the result value; type mismatches and div/0 silently drop the row
• Step 6: apply_post_processing — aggregates collapse rows (grouping by plain-variable :find specs via FunctionRegistry); window functions annotate per-row (sort within partition by :order-by key, walk accumulating window state, emit one output row per input row)

4. Evaluate rules — StratifiedEvaluator stratifies rules; for each stratum:
   • Positive rules evaluated via RecursiveEvaluator (semi-naive fixed-point iteration)
   • Mixed rules (containing not / not-join / Expr) run positive patterns first, then apply negation filters and expr clauses per binding

Rule Registration#

register_rule calls stratify() after adding each rule. If the new rule creates a negative cycle in the dependency graph, stratify() returns Err and the rule is not registered. Non-recursive negation is always safe.

File Locking#

A .graph file is guarded by a kernel file lock taken on the file itself (std::fs::File::try_lock: flock on Unix, LockFileEx on Windows). The lock is released by the kernel whenever the holding process exits, however it exits, so a crashed holder never leaves the database unopenable. Because flock and OFD locks attach to the open file description rather than the process, a second open within one process is refused too.

There is no lock file. A .graph.lock sidecar left behind by versions before 2.0 is ignored and never deleted, since a still-running old process may depend on it. Running mixed versions against one file is not supported.

On a filesystem that cannot lock at all, open() fails rather than proceeding unprotected. OpenOptions::allow_unlocked(true) overrides this, and accepts the corruption risk that comes with it.

On Windows these locks are mandatory rather than advisory, and they exclude every handle but the one holding them — including another handle in the same process. While a database is open you cannot read its .graph file through a second handle, your own included; the attempt fails with os error 33, "another process has locked a portion of the file", even when that process is you. Close the database first. On Unix the lock is advisory and such a read succeeds.

A cross-process WouldBlock is retried with bounded backoff (10 attempts, 5ms doubling, capped at 50ms, ~375ms total) before being reported as a real conflict, to ride out the transient window where a forked-but-not-yet-exec'd subprocess holds a duplicate of someone else's lock — the same class of problem SQLite's busy_timeout solves. A same-process conflict is not retried; it fails immediately, since waiting could never help.

One handle per file, per process. A second open on a file this process already has open is refused, naming the same-process case. This matters because each FileBackend caches its own header.page_count, allocates new pages from that count, and bounds-checks read_page against it — two handles on one file give two page tables that diverge, which surfaces as Page N out of bounds (total pages: M) and, past that, structural corruption. Minigraf is cheap to clone and all clones share one database, so cloning the existing handle is always the right move (#304).

Thread Safety#

• Concurrent reads via Arc<RwLock<FactStorage>>
• Exclusive write via Mutex<WriteTransaction>
• One live handle per file per process, enforced by the kernel file lock (see File Locking above)
• Rule registry is independently Arc<RwLock<RuleRegistry>>
• Function registry (FunctionRegistry) is Arc<RwLock<FunctionRegistry>> — shared between all query executions; built-in aggregates registered at startup; user-defined aggregates and predicates registered via register_aggregate / register_predicate (Phase 7.7b)
• Page cache uses read-lock on hits, write-lock only on misses — minimises contention for read-heavy workloads
• BrowserDb (wasm32-unknown-unknown) runs single-threaded — all Arc/RwLock/Mutex calls compile as single-threaded stubs under the browser feature; no WASM thread support

• PreparedQuery holds Arc clones of FactStorage, RuleRegistry, and FunctionRegistry — each execute() call re-reads live store state (new facts visible) while the query plan is reused