Architecture

Module Structure#

src/
├── main.rs                     — binary entry point (interactive REPL)
├── lib.rs                      — public API exports
├── db.rs                       — public embedded API: Minigraf, OpenOptions (incl. read_only), WriteTransaction, IntegrityReport; execute / query / fact_log / prepare / begin_write / checkpoint / verify / rebuild_indexes; register_aggregate / register_predicate for UDFs
├── cursor.rs                   — Cursor / Batch: owned, Send cursor returned by Minigraf::query and PreparedQuery::query
├── fact_log.rs                 — FactLog / FactFilter / FactRecord / FactOrder: every fact version, streamed without Datalog
├── log_writer.rs               — LogWriter: builds a new file from FactRecords, keeping their tx and valid time
├── repl.rs                     — interactive Datalog REPL console
├── temporal.rs                 — UTC timestamp parsing (avoids chrono CVE GHSA-wcg3-cvx6-7396)
├── wal.rs                      — write-ahead log (version 2 header with base generation), CRC32 entries; not built for wasm32
├── 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; BrowserDb.query returns a BrowserCursor
├── graph/
│   ├── types.rs                — Fact, Value, EntityId, Attribute, VALID_TIME_FOREVER
│   └── storage.rs              — FactStorage: in-memory EAV store with temporal query methods
├── query/datalog/              — parser, executor, matcher, evaluator, stratification, rules, functions, optimizer, prepared, magic_sets, types (as in v2.x)
└── storage/
    ├── mod.rs                  — StorageBackend trait, CommittedReader trait, LegacyHeaderV7 (v7 migration only)
    ├── persistent_facts.rs     — PersistentFactStorage: v8 save/load, copy-on-write checkpoint, v7 → v8 migration
    ├── meta.rs                 — meta pages A/B: the only commit point
    ├── page.rs                 — 24-byte common page header (type, count, CRC32, page id, generation), page allocator
    ├── freelist.rs             — free-list chain of reusable pages
    ├── keys.rs                 — byte-comparable keys: FDB integers, value tags, tx↓, FOREVER; MAX_VALUE_BYTES, MAX_IDENT_BYTES
    ├── node.rs                 — prefix-compressed leaves and shortest-separator internal nodes
    ├── btree.rs                — on-disk B+tree over byte keys: build_btree, cow_insert, LeafCursor (seek, prefix_scan, get)
    ├── dict.rs                 — DICT tree: entity and ident ids, tx timestamps, long values; checkpoint-time Encoder
    ├── value_pages.rs          — append-only pages for strings over 64 bytes
    ├── reader.rs               — OnDiskReader: covering reads of committed facts; net-assert on index keys
    ├── verify.rs               — integrity walk for Minigraf::verify and the source choice for rebuild_indexes
    ├── index.rs                — in-memory keys of the pending (uncheckpointed) EAVT/AEVT indexes
    ├── cache.rs                — LRU page cache: approximate-LRU, read-lock on hits
    ├── dir_sync.rs             — fsyncs the parent directory after creating or deleting a file
    ├── packed_pages.rs         — v7 fact pages, read only to migrate a v7 file
    └── 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 (uncheckpointed) facts live in memory, indexed by entity and by attribute. Committed facts live only in the on-disk covering indexes: every index entry is a whole fact, so a read touches index leaves, the dictionary pages that translate its ids, and a value page for a long string, all through the LRU cache (OnDiskReader, through the CommittedReader trait). Nothing is loaded at startup, and memory is O(cache pages), not O(facts).

Covering indexes#

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

Each index entry is the whole fact, as a byte-comparable key, so a query never reads a separate fact page. See File format (v8) for the key layout. Two values of one attribute written in the same transaction are separate keys, and an assertion and a retraction of the same value in one transaction stay apart.

File Format (v8)#

The .graph file is page-based (4KB pages), endian-safe, cross-platform. The design is in docs/superpowers/specs/2026-10-05-v8-storage-format-design.md (#374, #434, #388, #433).

Layout.

Page 0, 1   Meta pages A and B. Odd generations commit to page 0, even to page 1.
            magic "MGRF"/"META", version 8, CRC32 over the whole page, generation,
            page_count, fact_count, last_checkpointed_tx_count, five tree roots
            (EAVT, AEVT, AVET, VAET, DICT), free-list head and count, next_eid,
            next_iid, required_features. The only commit point.
Page 2+     Any mix of B+tree leaves (0x61) and internal nodes (0x62), value
            pages (0x51) and free-list pages (0x81). Each starts with a 24-byte
            header: type, count, CRC32, its own page id, the generation that
            wrote it. Every read checks all four.
Sidecar     <db>.wal, version 2: the header records the base generation.

Covering keys. Every index entry is a whole fact, encoded so that comparing bytes gives the logical order:

• Entities and idents (attribute names and keyword values) are sequential ids from the DICT tree, assigned at checkpoint. The query layer still sees UUIDs and strings.
• Integers use the FoundationDB tuple encoding; tx↓ is the complemented tx_count, so the newest transaction comes first; vt = FOREVER is one byte.
• Strings over 64 bytes are stored once (deduplicated) in value pages; the key holds a 32-byte prefix, a hash and a reference.
• Leaves are prefix-compressed with restart points; internal nodes hold shortest separators. There are no leaf sibling pointers: scans use a cursor with a parent stack and a forward seek.
• A query reads only index leaves, the DICT pages that translate its ids, and a value page for a long string. Committed results come back in id order.

Checkpoints are copy-on-write.

• A checkpoint writes only:
  • new value pages;
  • the touched leaves and their paths to the root, in each of the five trees;
  • a few free-list pages;
  • the other meta page.
• Pages freed by one checkpoint are reused by later ones. The free list is read only as far as it is needed, and new pages are pushed onto its head.
• A crash or torn write at any point leaves the previous checkpoint intact. Open never rebuilds an index.
• Cost follows the change:

One new fact at 100k facts writes 16 pages.

Density. About 142 bytes per fact, history included, at 1.15M facts in #433's shape (about 10 attributes per entity, 20 % multi-valued, 10 % retracted and re-asserted). v7 used about 2 KB per fact as measured.

Integrity.

• A damaged page fails the read or checkpoint that reaches it, with STG-029 (CRC), STG-030 (page id) or STG-031 (generation). It never returns wrong or fewer rows.
• If the newest meta page is damaged after its WAL is gone, open fails with STG-033 rather than silently opening an older generation.
• Unknown required_features bits fail with STG-034.

Limits. String values up to 4,068 bytes; attribute names and keyword values up to 1,024 bytes (WAL-003).

Migration.

• v7 files (v2.x) upgrade automatically, one way, on first open.
• The upgrade is crash-safe, with a backup meta page. Old pages become free pages that later checkpoints reuse.
• v1–v6 fail with STG-028: open them once with v2.x first.
• Development builds of v3.0.0 from before this format fail with STG-032.

Checking a file. Minigraf::verify() walks every committed page and reports logical damage that page checksums cannot see: indexes that disagree (STG-038), keys out of order or a page reached twice (STG-039), dictionary maps that disagree (STG-040), and leaked or doubly used pages (STG-035). Minigraf::rebuild_indexes() rebuilds the four indexes from an intact one and commits like a checkpoint; if none can serve as the source it fails with STG-041 and writes nothing.

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 (32 bytes): magic "MWAL", version u32 (2),
                     base_generation u64 (the meta generation the WAL extends), 16 reserved bytes
  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

On open, the WAL is replayed only on top of the generation it was written against. A version 1 WAL from v2.x next to a file migrated from v7 is still replayed.

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 over the covering indexes (committed entries that net-assert would hide are skipped on the index keys, before any fact is decoded), then applies the 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)

 The latest assertion's window is the fact's only current valid-time window; earlier windows stay visible through `:as-of` (#435).

• 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.

Read-only opens. OpenOptions::read_only(true) takes the lock in shared mode instead. Any number of read-only handles, in this process or others, can hold the file at once; they exclude a read-write open and it excludes them (STG-025 / STG-026). Nothing done through a read-only handle writes to the .graph file or its WAL: a WAL left by an earlier session is applied in memory only, a v7 file is read into memory instead of migrated, writes fail with API-014, and a missing file is STG-042.

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

• Cursor (from query()) and FactLog (from fact_log()) are owned and Send: they borrow nothing from the handle and can move to another thread. An open FactLog pins the committed generation, so checkpoints wait until it is closed (API-013).

• 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