diff --git a/CHANGELOG.md b/CHANGELOG.md index 2b62740cb8..a57554b51f 100644 --- a/CHANGELOG.md +++ b/CHANGELOG.md @@ -17,6 +17,10 @@ and this project adheres to [Semantic Versioning](https://semver.org/spec/v2.0.0 - Two values of the same attribute written in one transaction are both returned by every query path. Previously only one came back, and entity-bound and attribute-bound queries could return different ones (#371, #287). - A retract that removes several values of one attribute in one call now hides all of them (#371). +### Internal + +- **B+tree reads no longer follow leaf sibling links** (v8 storage format, PR 1 of 5; #374). Every index scan uses a cursor that walks down from the root and keeps the path, with a forward `seek` that climbs only as far as needed. This prepares for copy-on-write index pages, which cannot keep sibling links. The file format and query results are unchanged. Concurrent 100k-fact scans take 25–37 % less time and checkpointing after one fact at 10k facts 9 % less; single point lookups and attribute scans are 2–6 % slower (about 0.4 µs per lookup). A corrupted child pointer now fails with STG-013 (wrong page type) or INT-049 (cycle) instead of following a bad link. + ## v2.0.2 — 2026-09-27 Final planned release on the v2.x line. File format is unchanged (v7). No breaking API changes; one new user-facing error code (API-010). v2.x gets data-integrity and security fixes for 12 months after v3.0.0 ships ([support policy](PHILOSOPHY.md#support-policy)). diff --git a/CLAUDE.md b/CLAUDE.md index ce98405e88..cb30221d0b 100644 --- a/CLAUDE.md +++ b/CLAUDE.md @@ -173,7 +173,7 @@ Auto-migrates v7 → v8 on open (index rebuild). v1–v6 are rejected (STG-028). ## Test Coverage -**1215 tests passing** (1207 passing, 8 ignored; unit + integration + doc). +**1225 tests passing** (1217 passing, 8 ignored; unit + integration + doc). See `docs/TEST_COVERAGE.md` for the full per-file breakdown. **Testing conventions** — see the Testing Conventions section below before writing any tests. diff --git a/docs/TEST_COVERAGE.md b/docs/TEST_COVERAGE.md index 5ec07ee2a3..9d330da729 100644 --- a/docs/TEST_COVERAGE.md +++ b/docs/TEST_COVERAGE.md @@ -2,11 +2,11 @@ ## Coverage Summary -**Verified**: 2026-09-27 with `cargo test --quiet` +**Verified**: 2026-10-05 with `cargo test --quiet` -**Result**: 1,207 passing tests and 8 ignored tests (1,215 total) +**Result**: 1,217 passing tests and 8 ignored tests (1,225 total) -This covers the unreleased file-format-v8 work (#287, #371): the index-key value-collision fix, the v7→v8 migration, and the drop of formats v1–v6. It otherwise still covers the public database API, the Datalog engine, storage and recovery paths, v2.0.0's locking and structured-error-code changes, and v2.0.1's regression test for rebuilding indexes on open after several checkpoints (#370). Merged from the v2.x line: `tests/point_query_history_test.rs` and new storage unit tests check that attribute-narrowed bound-entity lookups return exactly what a full scan returns, and that `net_asserted_facts` matches its previous implementation on randomized histories (#323). Attribute-scan tests check that the AEVT range covers exactly the queried attribute, including non-ASCII names such as `:丿` and prefix siblings such as `:ab` for `:a` (#381). Incremental B+tree rebuild tests check that checkpoints which copy untouched index leaves produce exactly the entries and file checksum a full rebuild would, including over repeated checkpoints, that single-fact checkpoints do not fragment the index, and that a cyclic leaf chain or damaged slot directory is rejected rather than copied (#315). Directory-sync unit tests check that creating the `.graph` file or the WAL, and deleting the WAL, fsync the parent directory after the file operation, and that reopening an existing file does not (#389). Disjunction tests check that `or-join` returns an empty result, not INT-031, when no rows reach it: on an empty database, after a pattern that matches nothing, after a `not` that removes every row, and in a rule body (#405). A stratification unit test builds the same two-rule negative cycle 64 times and checks that the INT-054 message names the same predicate pair every time (#410). Magic-sets tests check that a recursive rule with a literal start that recurses through another rule returns the same results as without the literal (#297). API tests check that `execute()` and `WriteTransaction::execute()` reject `$slot` bind tokens in every position with API-010 (#407). The REPL `run()` test now runs in a child process with null stdin, so it no longer hangs when the test runner's stdin is an open non-TTY stream (#415). A fault-injection test crashes `save()` at each of its 47 page writes and syncs and checks that every reopen finds exactly the old or the new checkpointed facts (#374). +This covers the unreleased file-format-v8 work (#287, #371): the index-key value-collision fix, the v7→v8 migration, and the drop of formats v1–v6. It otherwise still covers the public database API, the Datalog engine, storage and recovery paths, v2.0.0's locking and structured-error-code changes, and v2.0.1's regression test for rebuilding indexes on open after several checkpoints (#370). Merged from the v2.x line: `tests/point_query_history_test.rs` and new storage unit tests check that attribute-narrowed bound-entity lookups return exactly what a full scan returns, and that `net_asserted_facts` matches its previous implementation on randomized histories (#323). Attribute-scan tests check that the AEVT range covers exactly the queried attribute, including non-ASCII names such as `:丿` and prefix siblings such as `:ab` for `:a` (#381). Incremental B+tree rebuild tests check that checkpoints which copy untouched index leaves produce exactly the entries and file checksum a full rebuild would, including over repeated checkpoints, that single-fact checkpoints do not fragment the index, and that a damaged slot directory is rejected rather than copied (#315). B+tree cursor tests check that every scan walks the tree, not the leaf `next_leaf` chain: full scans and start positions match the input, `seek` from the current position lands where a fresh descent from the root would (randomized, plus within a leaf, to a sibling, across subtrees, past the end, into the gap after a leaf, and backwards as a no-op), a seek to the sibling leaf reads exactly one page, reads are unchanged with every `next_leaf` zeroed, a child pointer into a non-B+tree page is STG-013, and a cycle in child pointers is an error, not a hang (v8 storage format PR 1, #374). Directory-sync unit tests check that creating the `.graph` file or the WAL, and deleting the WAL, fsync the parent directory after the file operation, and that reopening an existing file does not (#389). Disjunction tests check that `or-join` returns an empty result, not INT-031, when no rows reach it: on an empty database, after a pattern that matches nothing, after a `not` that removes every row, and in a rule body (#405). A stratification unit test builds the same two-rule negative cycle 64 times and checks that the INT-054 message names the same predicate pair every time (#410). Magic-sets tests check that a recursive rule with a literal start that recurses through another rule returns the same results as without the literal (#297). API tests check that `execute()` and `WriteTransaction::execute()` reject `$slot` bind tokens in every position with API-010 (#407). The REPL `run()` test now runs in a child process with null stdin, so it no longer hangs when the test runner's stdin is an open non-TTY stream (#415). A fault-injection test crashes `save()` at each of its 47 page writes and syncs and checks that every reopen finds exactly the old or the new checkpointed facts (#374). ### Covered Areas diff --git a/docs/superpowers/plans/2026-10-05-v8-storage-format.md b/docs/superpowers/plans/2026-10-05-v8-storage-format.md new file mode 100644 index 0000000000..1f36fd4529 --- /dev/null +++ b/docs/superpowers/plans/2026-10-05-v8-storage-format.md @@ -0,0 +1,192 @@ +# v8 Storage Format Implementation Plan + +> **For agentic workers:** REQUIRED SUB-SKILL: Use superpowers:subagent-driven-development (recommended) or superpowers:executing-plans to implement this plan task-by-task. Steps use checkbox (`- [ ]`) syntax for tracking. + +**Goal:** Implement the v8 storage format: crash-atomic copy-on-write checkpoints whose cost depends only on the change, per-page checksums, and covering indexes with dictionary-coded, byte-comparable keys. This closes #374, #434, #388 and #433's format decisions. + +**Spec:** `docs/superpowers/specs/2026-10-05-v8-storage-format-design.md` (§ numbers below refer to it). + +**Tech Stack:** Rust (MSRV 1.89), postcard (until PR 3), crc32fast, criterion. No new dependencies. + +**Delivery:** five PRs into `v3` (spec §14). This plan details PR 1 task by task. PRs 2–5 are listed at task level. Each gets its own detailed plan section, written when the previous PR has merged, because each builds on the code shape the previous one leaves. + +## Global Constraints + +- Every PR targets `v3` and must pass full CI. Never merge without the user's explicit confirmation. +- Test assert messages never format `Result`, `Fact`, `Value`, `EdnValue`, index keys, `FactRef` or anything containing a `Uuid` with `{:?}` (CodeQL `rust/cleartext-logging`). Use plain string messages, `unwrap`/`expect`, or assertions on counts. +- Match the surrounding clippy style. Functions in `btree_v6.rs` that index or do arithmetic carry `#[allow(clippy::arithmetic_side_effects)]` / `#[allow(clippy::indexing_slicing)]`. Errors use `err_coded!`/`bail_coded!`. B+tree invariant violations use `ErrorCode::Int049`. A page of the wrong type reached during a scan is `ErrorCode::Stg013`. +- Error codes are never removed or recycled. New codes are registered in `src/error.rs` and in `docs/ERROR_REFERENCE.md`. +- `cargo test --release` does not work (panic=abort profile). Use `cargo test` and `cargo bench`. +- Before each commit, run `cargo fmt` and `cargo clippy --all-targets -- -D warnings`. CI's `stable` clippy may be newer than the local one. +- Commit messages end with: + ``` + Co-Authored-By: Claude Opus 5.5 + Claude-Session: https://claude.ai/code/session_015GgLEs8YozJjYhwPEYgTUn + ``` +- PR descriptions end with: + ``` + 🤖 Generated with [Claude Code](https://claude.com/claude-code) + + https://claude.ai/code/session_015GgLEs8YozJjYhwPEYgTUn + ``` +- Issue references: PRs 1–3 use `Refs #374 #434 #388 #433`. Only the PR that completes an issue may say `Closes`. + +--- + +# PR 1 — Cursor scans (no format change) + +**Goal:** All B+tree reads go through a `LeafCursor` that descends with a parent stack and supports a forward `seek`. No read path follows `next_leaf` any more. Writers still set it, and the on-disk format is unchanged. This prepares for spec §4.3, where `next_leaf` is gone. + +**Architecture:** `LeafCursor` (new, in `btree_v6.rs`) keeps a stack of internal frames. Each frame holds the node's decoded separators, its child ids, the index of the child currently taken, and the node's own upper bound, inherited from its parent's separator. The current leaf's decoded entries and position are held alongside. `range_scan`, `stream_all_entries` and `collect_leaf_pages` are rewritten on top of it. `find_leaf_for_key` and `find_leftmost_leaf` become cursor internals. + +## Review Focus + +1. **Seek that crosses subtrees.** Seeking from the last leaf of one subtree into a key several subtrees to the right must pop exactly as far as needed, then descend. Expect: the same position as a fresh descent from the root. Pinned by `cursor_seek_matches_fresh_descent_random` (Task 3). +2. **Key in the gap between a leaf's last entry and its upper bound.** Expect: the cursor parks at the end of that leaf and `next()` moves to the next leaf's first entry. Pinned by `cursor_seek_into_gap_after_leaf_end` (Task 3). +3. **Backward seek.** Expect: a no-op that keeps the position. Pinned by `cursor_seek_backwards_is_noop` (Task 3). +4. **Corrupt child pointer.** A child id pointing at a non-B+tree page, or a cycle back up the tree. Expect: STG-013 for a wrong page type, and Int049 on exceeding the maximum depth, never a hang. Pinned by `cursor_child_pointing_at_fact_page_returns_stg_013` and `cursor_cycle_in_child_pointers_is_bounded` (Task 4). +5. **Seek cost.** A seek to the neighbouring leaf must not re-read internal pages the cursor already holds. Pinned by `cursor_seek_to_next_leaf_reads_one_page` (Task 3), using a page-read counting backend. + +--- + +### Task 1: Page-read counting test backend + +**Files:** +- Modify: `src/storage/btree_v6.rs` (test module, new helper near the top of `mod tests`) + +**Interfaces:** +- Produces: `CountingBackend { inner: MemoryBackend, reads: AtomicU64 }`, implementing `StorageBackend`, which counts `read_page` calls. Used with a page cache of capacity 0 so every page access reaches the backend. + +- [ ] **Step 1:** Add `CountingBackend` to the test module. It delegates every method to `inner`, and `read_page` increments `reads` (`Ordering::Relaxed`). Add `fn reads(&self) -> u64` and `fn reset(&self)`. +- [ ] **Step 2:** Check that `PageCache::new(0)` passes reads straight through (look at `cache.rs`). If capacity 0 still caches, use a cache of capacity 1 and account for that in the expected counts. +- [ ] **Step 3:** `cargo test -p minigraf storage::btree_v6` passes (no behaviour change yet). Commit: `test(btree): page-read counting backend for cursor tests`. + +### Task 2: `LeafCursor` with descend and `next` + +**Files:** +- Modify: `src/storage/btree_v6.rs` (new section `// ─── LeafCursor ───` after the leaf traversal helpers) + +**Interfaces:** +- Produces: + ```rust + pub(crate) struct LeafCursor<'a, K> { /* backend, cache, stack, leaf state */ } + impl<'a, K> LeafCursor<'a, K> + where K: for<'de> Deserialize<'de> + Ord + Clone + { + /// Positions before the first entry ≥ `start` (`None` = leftmost). + pub(crate) fn new(root: u64, start: Option<&K>, backend: &'a dyn StorageBackend, cache: &'a PageCache) -> Result; + /// Next entry in key order, or `None` at the end of the tree. + pub(crate) fn next(&mut self) -> Result>; + /// Moves forward to the first entry ≥ `key`; a key at or before the position is a no-op. + pub(crate) fn seek(&mut self, key: &K) -> Result<()>; + /// Raw page of the current leaf, for `collect_leaf_pages` (None before the first leaf / at end). + pub(crate) fn current_leaf_page(&self) -> Option<&Arc>>; + /// Moves to the start of the next leaf; false at the end of the tree. + pub(crate) fn advance_leaf(&mut self) -> Result; + } + ``` +- Internal: `struct Frame { page_id: u64, children: Vec, seps: Vec, child_idx: usize, upper: Option }`. `children.len() == seps.len() + 1`, and the last child is `rightmost_child`. `seps[j]` is the first key of `children[j+1]`, as in `write_internal_page`. +- Internal: a `decode_internal(page) -> (Vec, Vec)` helper that reuses `read_u16_at`/`read_u64_at` and the slot-directory layout. `find_leaf_for_key` already decodes the same way, so extract the shared logic instead of copying it. +- Constant: `const MAX_TREE_DEPTH: usize = 32;`. Descending deeper than this is `Int049` ("tree deeper than MAX_TREE_DEPTH: cycle or corruption"). + +- [ ] **Step 1: Write failing tests** in `mod tests`: + - `cursor_full_scan_matches_stream` builds trees of 0, 1, 10, 500 and 5,000 entries with `build_btree`. `LeafCursor::new(root, None, ..)` drained with `next()` must equal the sorted input. The 5,000 case must have depth ≥ 2: assert that the root page type is `PAGE_TYPE_INTERNAL`. + - `cursor_start_key_positions_at_first_ge` covers start keys below the minimum, equal to an entry, between entries, at a leaf boundary (the first key of leaf 2) and above the maximum. +- [ ] **Step 2:** Run them and watch them fail (`LeafCursor` doesn't exist). +- [ ] **Step 3: Implement.** + - Descent from a frame: pick child `c` = first `i` with `key < seps[i]`, else `seps.len()` (rightmost). Push a frame with `upper = if c < seps.len() { Some(seps[c].clone()) } else { parent.upper.clone() }`. + - At a leaf, decode its entries (`read_leaf_entries`) and set `pos` = `partition_point(|(k,_)| k < key)`. + - Every page reached by descent must be `PAGE_TYPE_LEAF` or `PAGE_TYPE_INTERNAL`, otherwise `Stg013`. Enforce `MAX_TREE_DEPTH`. + - `advance_leaf` pops frames while `child_idx == seps.len()`. At the first frame with a next child it increments `child_idx`, then descends leftmost, computing upper bounds the same way. + - `next` returns the entry at `pos` and increments it. At the end of a leaf it calls `advance_leaf` and loops, because empty leaves can exist (an empty tree is a single empty leaf). +- [ ] **Step 4:** Tests pass. `cargo clippy --all-targets -- -D warnings`. Commit: `feat(btree): LeafCursor with parent-stack descent (#374 prep)`. + +### Task 3: `seek` + +**Files:** +- Modify: `src/storage/btree_v6.rs` + +- [ ] **Step 1: Write failing tests:** + - `cursor_seek_matches_fresh_descent_random`: a seeded LCG (no new dependency; copy the generator pattern from `test_incremental_matches_merge_random`) builds a 20,000-entry tree. Generate 2,000 ascending seek targets, including duplicates and keys that are not in the tree. After each `seek(t)`, `next()` must equal what `LeafCursor::new(root, Some(&t), ..).next()` gives. + - `cursor_seek_within_leaf`, `cursor_seek_to_sibling_leaf`, `cursor_seek_across_subtrees` and `cursor_seek_past_end` (then `next() == None`). + - `cursor_seek_into_gap_after_leaf_end`: seek to a key greater than leaf L's last entry and smaller than leaf L+1's first entry. `next()` must return L+1's first entry. + - `cursor_seek_backwards_is_noop`: after `seek(k2)`, `seek(k1)` with `k1 < k2` leaves `next()` unchanged. + - `cursor_seek_to_next_leaf_reads_one_page`: using `CountingBackend` with a cache of capacity 0 and a depth ≥ 2 tree. Position at leaf L, reset the counter, then seek to the first key of L+1. Expected reads: exactly 1 (the new leaf), because the parent frame already holds the separators and child ids. A seek into a different parent reads 2 pages (the parent and the leaf). +- [ ] **Step 2:** Run them and watch them fail. +- [ ] **Step 3: Implement `seek(key)`:** + 1. If `key <= ` the entry at `pos` (or the last returned key), return: no-op. + 2. If a leaf is loaded and `upper` of the leaf's frame is `None` or `key < upper`, the key is in this leaf: `pos = max(pos, partition_point(< key))`. Return. + 3. Otherwise pop frames until the top frame's `upper` is `None` or `key < upper`. At that frame, set `child_idx` to the first `i ≥ child_idx` with `key < seps[i]` (else rightmost), then descend as in Task 2. + 4. Track the leaf's own upper bound in the cursor: it is the upper bound computed when the leaf was entered. +- [ ] **Step 4:** Tests pass. Commit: `feat(btree): LeafCursor::seek from the current position`. + +### Task 4: Move `range_scan`, `stream_all_entries` and `collect_leaf_pages` onto the cursor + +**Files:** +- Modify: `src/storage/btree_v6.rs`: `range_scan` (~line 897), `stream_all_entries` (~line 849, test-only), `collect_leaf_pages` (~line 459), `find_leftmost_leaf`/`find_leaf_for_key` (delete if unused, or make them private wrappers over the cursor). +- Modify: tests that corrupt `next_leaf` (~lines 1219 and 1794–1850). + +- [ ] **Step 1: Update tests first.** + - `range_scan_corrupted_next_leaf_pointer_returns_stg_013` is replaced by `cursor_child_pointing_at_fact_page_returns_stg_013`. It overwrites a child id in the root internal node with a packed fact page's id, then calls `range_scan` with a start key routed to that child. It expects STG-013 (`MinigrafError::from(err).code() == "STG-013"`). + - Add `range_scan_ignores_next_leaf`: corrupt every leaf's `next_leaf` to 0. `range_scan` and `collect_leaf_pages` still return everything. This proves no read path follows `next_leaf`. + - `test_collect_leaf_pages_rejects_cyclic_chain` becomes `cursor_cycle_in_child_pointers_is_bounded`: point a child id of an internal node back at the root. Every scan returns Int049 and does not hang. + - Keep `test_collect_leaf_pages_rejects_corrupt_slot_directory`. `collect_leaf_pages` still calls `validate_leaf_slots` on each leaf. +- [ ] **Step 2:** Run the new tests and watch them fail. Old behaviour follows `next_leaf`. +- [ ] **Step 3: Implement.** + - `range_scan`: `let mut c = LeafCursor::new(root, Some(start), ..)?; while let Some((k, fr)) = c.next()? { if end.is_some_and(|e| k >= *e) { break } out.push(fr) }`. + - `stream_all_entries`: drain `LeafCursor::new(root, None, ..)`. + - `collect_leaf_pages`: iterate leaves with `advance_leaf`, calling `validate_leaf_slots` and pushing `current_leaf_page()`. Drop the `max_leaves` chain guard, which `MAX_TREE_DEPTH` and the tree structure now replace. Keep the doc comment's reason for snapshotting. `rebuild_btree_incremental` still writes `next_leaf` (format unchanged). +- [ ] **Step 4:** `cargo test` (full suite) passes. Commit: `refactor(btree): every read path uses LeafCursor; next_leaf is write-only`. + +### Task 5: Benchmark guard and docs + +**Files:** +- Modify: `docs/TEST_COVERAGE.md` (btree_v6 test counts), `CLAUDE.md` (test count line), `CHANGELOG.md` (`[Unreleased]` / v3.0.0 section: internal, "B+tree scans no longer follow leaf sibling links (prep for #374)"). + +- [ ] **Step 1:** `cargo bench --bench minigraf_bench -- 'query/|checkpoint/'` on `v3` (before) and on the branch (after). Record both in the PR description. A regression above 10 % on any `query/` group blocks the PR: investigate separator decoding per frame first. +- [ ] **Step 2:** Update the test counts from `cargo test 2>&1 | grep "test result"`, and update the docs above. +- [ ] **Step 3:** Commit `docs: test counts and changelog for cursor scans`. Push the branch and open a PR into `v3` titled `refactor(btree): cursor-based scans with seek (v8 PR 1, refs #374)`. Include this plan's Review Focus list in the description. Monitor CI until green and fix every failure. Ask the user before merging. + +--- + +# PR 2 — v8 page format (outline) + +Spec §4.1, §4.2, §12. Atomic but still O(N) `save()`. + +- Common 24-byte page header (type, count, CRC, page id, generation): encode and verify helpers. Verification runs in `PageCache::get_or_load`, with new STG codes. +- Renumber page types (0x51, 0x61, 0x62, 0x81). Update constants and the type-check tests. +- Meta pages A/B: `MetaPage` struct, encode/decode, selection by §4.1.1. WAL v2 `base_generation` (`wal.rs` header). Search for evidence of an interrupted commit. +- `required_features` check and error code. +- `save()`: write everything into fresh pages (append), sync, write the inactive meta, sync. Delete `index_checksum`, `fact_prefix_crc` and the rebuild-on-open branch. +- `FaultInjectingBackend` torn-write mode. Extend the crash-at-every-point test, including a torn meta write. +- Browser flush check: the meta page goes in the same IDB transaction. + +# PR 3 — Covering keys and dictionaries (outline) + +Spec §4.3, §5, §6, §9. The format freezes after this PR. + +- Key codec module: FoundationDB-style integers, value tags, string escaping, long-value prefix + hash + ref, FOREVER byte, `tx↓`. Property tests: memcmp order equals logical order. +- Node format: prefix-compressed leaves with restart points; internal nodes with shortest separators; generic `(key bytes, value bytes)` entries. `LeafCursor` moves to byte keys. +- DICT tree with tags 0x01–0x06. Id assignment at transact time in WAL order (`FactStorage` pending index keyed by encoded keys). `next_eid`/`next_iid` in the meta page. +- Value pages with dedup. `MAX_VALUE_BYTES` replaces `MAX_FACT_BYTES`. +- Covering reads: `CommittedIndexReader` returns facts, translating ids through cached DICT lookups. Delete `FactRef`, fact pages, `CommittedFactReader`. +- v7 migration with a backup meta page, and crash tests. +- Audit of result-order assumptions in tests and bindings. + +# PR 4 — Copy-on-write insert, allocator, free list (outline) + +Spec §4.4, §8. + +- Allocator over `M`'s free list plus append. Free-list chain pop/push with copy-on-write head pages. +- Copy-on-write batch insert per tree, reusing #315's balanced split and freeing replaced pages. +- Reachability/free-list invariant checker, used in tests after every checkpoint. +- Cost-bound test with a page-counting backend; a guard that pages referenced by the previous meta are never written. +- Concurrency test: queries during checkpoints. + +# PR 5 — Hardening, benchmarks, docs (outline) + +Spec §10, §11, §12. + +- Benchmarks: `checkpoint/after_1_fact` and `checkpoint/after_100k_facts` at 10k/100k/1M, bytes written per checkpoint, the 1M size test (≤ 200 B per fact). +- Corruption-surfacing tests for leaf, value page and free-list page. +- Docs: rustdoc of `checkpoint`/`wal_checkpoint_threshold`, `CLAUDE.md` File Format, `.wiki/Architecture.md`, CHANGELOG, ROADMAP, `ERROR_REFERENCE.md`, TEST_COVERAGE. diff --git a/docs/superpowers/specs/2026-10-05-v8-storage-format-design.md b/docs/superpowers/specs/2026-10-05-v8-storage-format-design.md new file mode 100644 index 0000000000..e8af4e5128 --- /dev/null +++ b/docs/superpowers/specs/2026-10-05-v8-storage-format-design.md @@ -0,0 +1,699 @@ +# v8 storage format: copy-on-write checkpoints and covering indexes — Design + +**Issues:** #374 (crash-atomic `save()`), #434 (checkpoint cost O(change)), #388 (per-page +checksums), #433 (format decisions for 1B facts) +**Milestone:** v3.0.0, branch `v3`, file format v8 (unreleased; this redefines its layout) +**Must land before:** #391 golden-file corpus freezes v8 +**Builds on:** #315 / `2026-09-26-incremental-checkpoint-design.md` (balanced leaf split, routing) + +## 1. Problem + +**Checkpoints.** `PersistentFactStorage::save()` has three defects that share one cause: +fact pages must stay contiguous at `1..=fact_page_count`, and the indexes sit directly +after them. + +1. **Not crash-atomic (#374).** New fact pages overwrite the start of the old index + region before the header is written. A crash in between leaves the old header + pointing at overwritten index pages. Open then sees a checksum mismatch and rebuilds + every index from the fact pages, which is O(graph). +2. **O(graph) checkpoints (#434).** Every index page is copied on every checkpoint. + Measured at 3.82 GB: ~3.27 GB written per checkpoint, ~13,000× write amplification. + On top of that, the full-file `index_checksum` is O(file) on every save and every open. +3. **No per-page integrity (#388).** Only the header has a checksum. A torn write, a bad + sector or a misdirected write is noticed only if postcard decoding happens to fail. + +A fourth defect sits in the same code: the header is a single page. A torn write of +page 0 leaves a file whose header fails its CRC, and the file cannot be opened at all. + +**Density and access cost (#433).** A fact costs about 520 B on disk at best today, and +about 2 KB as measured. The fact record is ~70 B of postcard data. Each of the four +index entries is ~70–90 B, and each one repeats a 16-byte UUID, the attribute string and +8-byte timestamps. #433 allows at most 300 GB for 1B facts, which is 300 B per fact +including history. Two further costs grow with N: + +- **Indexes are not covering.** `range_scan` returns `FactRef`s, so every match costs a + read of a fact page. A streaming scan that matches 1M facts means 1M random page reads. +- **Keys land on random leaves.** Entity UUIDs derived from keywords (v5) and + caller-supplied UUIDs are effectively random in index order, and so are most values. + A checkpoint of k facts touches about k different leaves in every index. At 1B facts + that is ~40× write amplification, against #434's limit of 10. + +## 2. Goals and non-goals + +**Goals** + +- G1. A crash at any point of a checkpoint (any write, any sync, a torn page write) + reopens to the last committed checkpoint plus WAL replay. No checkpointed fact is lost. + No index rebuild happens on open. (#374) +- G2. A checkpoint writes only new value pages, the copied-on-write path from each + modified leaf to its root in each tree, free-list pages and one meta page. Bytes + written are O(k · log N) after k new facts and never depend on N. This bound covers + `checkpoint()`, the auto-checkpoint and the close-time checkpoint in + `Drop for Inner`. (#434 acceptance 1, 2, 4) +- G3. Every non-meta page carries a CRC32, its own page id and the checkpoint + generation that wrote it. Every read checks them. A failed check returns a structured + `STG-0xx` error and never returns the page's data. (#388) +- G4. Open is O(1) in graph size: no full-file checksum pass. +- G5. v7 files migrate on open. The migration is crash-safe and writes checksums + (#388 migration clause). Pre-release v8 files written by `v3` builds before this + change are not supported: v8 was never released, so they fail to open with the + "no valid meta page" error (§12). +- G6. At most 300 B per fact on disk at 1B facts, including history (estimate in §10: + 110–140 B). A query match never needs a page read beyond the index leaf, except for + long values. (#433) + +**Non-goals (separate issues)** + +- Shrinking the file or compacting free pages. The free list is reused. Vacuum is + a later, separate operation (#434: "space reclamation can be a later operation"). +- The public streaming cursor API (#432). §7 adds an internal leaf cursor with `seek` + that #432 can build on. +- Bε-style buffered internal nodes. They are the v3.x fallback behind a feature bit + (§4.1.2) if #394 still measures write amplification above 10. +- Lost-write detection, where the device acknowledges a write that never lands and an + older valid page stays at that location. Parent-held checksums were considered and + rejected (§13). + +## 3. Decisions + +| # | decision | alternative rejected | +|---|---|---| +| D1 | **Two alternating meta pages** with a generation counter and CRC | Single header page: a torn write makes the file unopenable | +| D2 | **In-page CRC32 + own page id + generation** on every non-meta page | Parent-held checksums: +4 B per pointer and per value ref | +| D3 | **Copy-on-write B+trees with a free list**, no leaf sibling pointers | Today's relocate-everything checkpoint | +| D4 | **Covering indexes.** Every index entry holds the whole fact. Fact pages, `FactRef` and the fact directory are removed. | Fact pages plus reference indexes: one random read per match | +| D5 | **Sequential internal entity ids** (`eid: u64`), with a dictionary mapping UUID ↔ eid. The API still speaks UUIDs. | 16-byte UUIDs in keys: random leaf placement, larger keys | +| D6 | **Ident dictionary** (`iid: u32`) for attribute names and keyword values | Strings in every key | +| D7 | **Out-of-line long values.** Values above 64 B are stored once (deduplicated) in value pages. Keys hold a 32-byte prefix, an 8-byte hash and a value ref. | Always inline: a 4 KB string copied into 3 indexes, leaf fanout of 1 | +| D8 | **Byte-comparable keys** (memcmp order). Integers use order-preserving variable-length encoding. Leaves are prefix-compressed. Separators are truncated to their shortest form. | postcard structs compared after decoding: no prefix compression, decode on every compare | +| D9 | **Datomic component order, newest transaction first:** `(e,a,v)` triples are contiguous, followed by `tx` descending | Today's `(e,a,vf,vt,tx,v)`: history of one triple is scattered | +| D10 | **Close-time checkpoint kept** (it becomes O(change)) | Removing it: slower reopens, binding behaviour change (#322) | + +### 3.1 Covering does not multiply writes + +Each fact is written into 3–4 index entries: EAVT, AEVT and AVET always, and VAET only +for `Ref` values. That is not an added cost. An index ordered by any permutation of +`e a v` must already hold `e`, `a`, `v` and `tx` in its key to order entries and keep +them distinct (#371). Covering adds only `vf`, `vt` and `op`, about 9 B (`vt` FOREVER is +1 byte). That is about the size of the `FactRef` it replaces. + +| per fact | today (v7 / v8 dev) | covering (this design) | +|---|---|---| +| fact record | 1 × ~70 B | none | +| index entries | 4 × ~80 B: already nearly whole facts, plus a `FactRef` | ~3.3 × ~25 B after prefix compression | +| raw bytes written | ~390 B | ~80 B | +| random page reads per query match | 1 (fact fetch) | 0 | + +Checkpoint cost is set by leaves touched per tree, not by entry size. Any design with +four sort orders touches four trees. + +Leaves cannot be shared between the four trees. A leaf is a run of entries that are +contiguous in its own tree's sort order, and the four orders disagree about which facts +are neighbours. Keeping each fact once and pointing at it from the trees is the +clustered-plus-secondary design that D4 rejects. Copy-on-write does share nodes, but +across generations of the same tree (§8). + +## 4. On-disk layout + +All integers in page headers and meta fields are little-endian. Key bytes follow §6. +Page size stays 4096. + +``` +Page 0, 1 Meta pages A and B (alternating commits) +Page 2+ Any mix of: B+tree nodes (EAVT/AEVT/AVET/VAET/DICT), value pages, + free-list pages, free pages +Sidecar .wal — header gains base_generation (§4.1.1); entries unchanged +``` + +### 4.1 Meta pages + +Each checkpoint writes the inactive slot, `slot = generation % 2`. On open, both slots +are read and one is chosen by §4.1.1. + +| offset | field | notes | +|---|---|---| +| 0..4 | magic `"MGRF"` | | +| 4..8 | version `u32` = 8 | | +| 8..12 | meta_magic `"META"` | distinguishes a v8 meta page from a legacy header | +| 12..16 | meta_crc `u32` | CRC32 of bytes 0..PAGE_SIZE with this field zeroed | +| 16..24 | generation `u64` | +1 per checkpoint; 1 = first commit | +| 24..32 | page_count `u64` | high-water mark; pages ≥ this are unallocated | +| 32..40 | fact_count `u64` | | +| 40..48 | last_checkpointed_tx_count `u64` | | +| 48..56 | eavt_root `u64` | 0 = empty tree | +| 56..64 | aevt_root `u64` | | +| 64..72 | avet_root `u64` | | +| 72..80 | vaet_root `u64` | | +| 80..88 | dict_root `u64` | §5.2 | +| 88..96 | freelist_head `u64` | §4.4; 0 = empty | +| 96..104 | freelist_count `u64` | number of free page ids in the chain | +| 104..112 | next_eid `u64` | next entity id (§5.1) | +| 112..120 | required_features `u64` | bitmask; v3.0.0 writes 0 (§4.1.2) | +| 120..124 | next_iid `u32` | next ident id (§5.1) | +| 124..PAGE_SIZE | zero | reserved, covered by meta_crc | + +The CRC covers the whole page, so the reserved bytes must be zero and future fields fit +without a layout change. The 84-byte `FileHeader` and its `index_checksum` and +`header_checksum` are removed. + +#### 4.1.1 Choosing the meta on open + +Each slot is classified as one of: + +- **empty:** no `"MGRF"`/`"META"` magic. This is slot B before generation 2. +- **valid:** magic, version and `meta_crc` all check out. +- **damaged:** magic present, but the CRC or a field fails. + +If both slots are valid, the higher generation wins. If neither is valid, see §9 +(a v7 header, the migration backup meta) or fail with "no valid meta page". + +If exactly one slot is valid, with generation `g`, the other slot either held a newer +commit `g+1` that is torn or rotted, or held the older `g-1` and was damaged later. +Open must never silently drop a checkpoint whose WAL is already gone, so it decides +with two extra facts: + +1. **WAL `base_generation`.** The WAL header records the generation of the meta that + was active when the WAL file was created; it is reserved bytes today, so this is + WAL version 2. A WAL is deleted only after a commit is durable, so an interrupted + commit of `g+1` always leaves a WAL with `base_generation == g`. +2. **Evidence of `g+1` in the data pages.** Generation `g+1` can only have written to + pages on `M_g`'s free list or at or above `M_g.page_count` (§8.1). A valid page in + one of those places stamped `generation == g+1` means `g+1` wrote its data. A + checkpoint with any new data writes at least one such page. The check reads `M_g`'s + free-list pages and the pages from `M_g.page_count` to the end of the file. That cost + is proportional to the last change, and it is paid only in this rare case. + +| WAL | page stamped `g+1` where `g+1` could write | meaning | action | +|---|---|---|---| +| `base_generation == g` | any | torn commit of `g+1`, or the older slot was damaged | open at `g`, replay the WAL | +| `base_generation > g` | any | a later commit existed and its meta is lost | error: meta damaged after commit | +| none | found | `g+1` committed (its WAL was deleted), then its meta rotted | error: meta damaged after commit | +| none | not found | the older slot was damaged, or `g == 1` with B empty | open at `g` | + +The error is a new STG code. The file is not modified. #373's tooling can recover at +`g` explicitly, and that loses the last checkpoint's facts. The next commit always +rewrites the damaged slot, because it is the inactive one. + +The browser backend writes through IndexedDB transactions and has no torn writes. Its +flush keeps the meta page in the same transaction as the data pages (§12). + +#### 4.1.2 Feature bits + +`required_features` lets later v3.x releases add structures without a format v9. +Examples are Bε-style buffered internal nodes, opt-in AVET (§13) or a new leaf encoding, +each as a new page type. Bit `i` set means a reader must understand feature `i` to read +the file correctly. Open fails with a new STG code ("unsupported file feature", naming +the bits) if any set bit is unknown to the running version. Nothing else is checked, so +the format version stays 8. + +- A writer sets a bit at the first commit that writes a page that needs it. Once set, + a bit is never cleared. +- v3.0.0 defines no bits and always writes 0. +- The bit registry lives next to the error-code registry and follows the same rule: + bits are never reused. + +### 4.2 Common page header (all non-meta pages) + +| offset | field | +|---|---| +| 0 | page_type `u8` | +| 1 | reserved `u8` (0) | +| 2..4 | count `u16` (entries, keys, records or ids, by type) | +| 4..8 | crc32 `u32`, over the full page with this field zeroed | +| 8..16 | page_id `u64`, the page's own id (catches misdirected writes) | +| 16..24 | generation `u64`, the checkpoint generation that wrote it | + +Read checks, in the page-cache load path so that every reader gets them: + +1. `page_type` is a known v8 type (table below). This is a cheap first-byte check, so a + legacy or foreign page fails before any CRC is computed. +2. crc32 matches. +3. `page_id` equals the requested id. +4. `generation ≤ active_meta.generation`. +5. `page_type` is the specific type the caller expects. Callers check this after the + cache returns, as they do today. + +Any failure returns a new structured error (§12) and the page is not cached. + +| page_type | name | body after the 24-byte header | +|---|---|---| +| 0x51 | value page | record directory + long values (§6.3) | +| 0x52 | value overflow | reserved, not written | +| 0x61 | B+tree leaf | prefix-compressed entries + restart array (§4.3); **no `next_leaf`** | +| 0x62 | B+tree internal | rightmost_child `u64` + truncated separators/children (§4.3) | +| 0x81 | free-list page | next `u64` + `count` × page id `u64` (up to 508 per page) | + +All five trees (EAVT, AEVT, AVET, VAET, DICT) use 0x61/0x62. A node does not record +which tree it belongs to; its tree is given by the root it was reached from. + +Type values follow the existing convention: the high nibble is the page family and the +low nibble is the variant. No v8 value reuses one from an earlier format. Those are +0x02/0x03 for v5–v7 fact pages, 0x11 for v5 index pages, and 0x21/0x22 for the v6/v7 +B+tree. Every v8 page has a different header from its v7 counterpart, so the type byte +alone tells a v8 page from a legacy one. A legacy page read where a v8 page is expected +fails the type check before the CRC is computed. #373's verify and salvage can classify +any page from its first byte, and v7 migration never confuses an old page with a new +one. Retired values stay reserved and are never reassigned. + +### 4.3 B+tree nodes + +Leaves have no sibling pointer. With copy-on-write, a `next_leaf` pointer means changing +one leaf forces a rewrite of its left neighbour, then that neighbour's left neighbour, +and so on: the O(N) cascade this design removes. Scans use a cursor with a parent stack +instead (§7). + +**Leaf body:** + +- Entries in key order. Each entry is + `varint shared_prefix_len ‖ varint suffix_len ‖ suffix ‖ varint value_len ‖ value`. + `value_len` is always 0 for the four index trees. +- Every 16th entry is a **restart point**: `shared_prefix_len = 0`, and its offset is + stored in a restart array at the end of the page. A lookup binary-searches the + restart points, then scans at most 16 entries. + +**Internal body:** + +- `rightmost_child u64`, then `(separator, child u64)` pairs. +- Separators are the shortest byte string `s` with `max(left) < s ≤ min(right)`. They + are usually a few bytes, so fanout is 200 or more. + +**Splits** are balanced by bytes, as in #315. There is no merging: nothing is ever +removed from a tree. + +### 4.4 Free list + +The free list is a singly linked chain of free-list pages. It holds ids of pages that the +active meta does not reference. The meta records the head and the total count. + +- **Pop (allocation):** whole pages are taken from the head. A free-list page that is + emptied is itself free. A partly used head page is rewritten copy-on-write with the + rest of its ids. +- **Push (release):** page ids freed by this checkpoint, plus the free-list pages it + emptied or rewrote, go into new pages pushed onto the head. +- Tail pages that are not touched are shared unchanged with the new meta. + +Cost is O(pages allocated + pages freed) per checkpoint, never O(free-list size). + +## 5. Data model + +### 5.1 Identifiers + +- **eid** (`u64`, starting at 1): assigned to each entity UUID the first time it appears + as an entity or as a `Ref` value. `next_eid` is stored in the meta page. +- **iid** (`u32`, starting at 1): assigned to each attribute name and each keyword value + the first time it appears. Attribute and keyword values share one namespace, so the + ident `:status/active` gets one id whether it is used as an attribute or a value. + `next_iid` is stored in the meta page. +- **Assignment time.** Ids are assigned in memory at transact time, in WAL order. WAL + replay reassigns them in the same order, starting from the meta page's counters, so the + result is deterministic and crash-safe without logging ids. Assignment at transact + time lets the in-memory pending index use the same encoded keys as the on-disk trees, + so merging pending and committed data is a plain merge of two sorted streams. +- **Translation boundary.** The query layer receives facts with UUIDs and strings, as + today. The reader translates ids through cached dictionary lookups. The streaming + engine (#432) should work on raw ids and translate only at output; this design keeps + that possible but does not require it in 3.0.0. + +### 5.2 Trees + +Five B+trees, all with the node format of §4.3 and all copy-on-write: + +| tree | key | entry value | holds | +|---|---|---|---| +| EAVT | `e a v tx↓ vf vt op` | — | every fact | +| AEVT | `a e v tx↓ vf vt op` | — | every fact | +| AVET | `a v e tx↓ vf vt op` | — | every fact | +| VAET | `v a e tx↓ vf vt op` | — | facts whose value is a `Ref` (`v` = target eid) | +| DICT | tag-prefixed, below | per tag | dictionaries and the tx table | + +EAVT and AEVT each hold the complete fact set. Either one can rebuild every other tree +(#373 `rebuild_indexes`), so a single corrupt index never loses data. There are no fact +pages and no fact directory: EAVT is the complete, ordered list of facts. + +DICT entries: + +| tag | key | value | used for | +|---|---|---|---| +| 0x01 | `uuid[16]` | `eid` | UUID → eid (transact, query constants) | +| 0x02 | `eid` | `uuid[16]` | eid → UUID (results) | +| 0x03 | ident bytes (escaped) | `iid` | name → iid | +| 0x04 | `iid` | ident bytes | iid → name | +| 0x05 | `tx_count` | `tx_id` (wall-clock ms) | `Fact.tx_id`, once per transaction | +| 0x06 | `hash64` of a long value | value ref | dedup of long values (§6.3) | + +Tags 0x02, 0x04 and 0x05 receive increasing keys, so their inserts touch only the +rightmost path. Tags 0x01 and 0x06 are random-key inserts, but they happen once per new +entity or new long value, not once per fact. + +### 5.3 Component order (D9) + +- `(e, a, v)` triples are contiguous in EAVT, and the history of a triple follows its + key, newest first. "Latest assertion per triple" (#435) and "live facts only" (#379) + become streaming operations: read the first entry per triple and skip the rest with + `seek` (§7). +- `:as-of N` seeks to `(e, a, v, ↓N)` and lands directly on the newest assertion at or + before N, in O(log) per triple instead of a scan of its history. +- Valid time (`vf`, `vt`) and `op` (assert or retract) follow `tx`. They are filtered + per entry, as today. +- This changes the order of committed scan results compared with v7: eid order instead + of UUID order, iid order instead of attribute-name order. Query results are sets, but + every test or binding that relies on a particular order must be found and fixed + (§11). + +## 6. Key encoding (D8) + +All components are encoded so that comparing the bytes with memcmp gives the logical +order. Encoded keys are compared without decoding. + +### 6.1 Integers + +Integers use the FoundationDB tuple-layer encoding. A type byte holds the sign and the +byte length, followed by the minimal big-endian magnitude (one's complement for +negatives). + +- 0 takes 1 byte. Values up to 255 take 2 bytes. A ms timestamp (~2^41) takes 7 bytes. +- `eid`, `iid` and `tx_count` use the unsigned form. +- `vt == VALID_TIME_FOREVER`, the common case, is the single byte `0xFF`. It sorts after + every finite time. +- `tx↓` is the encoding of `u64::MAX - tx_count`, so newer transactions sort first. + +### 6.2 Values + +A type tag is followed by the payload. The tag order is unchanged from v7, so +cross-type ordering stays Null < Boolean < Integer < Float < String < Keyword < Ref. + +| type | payload | +|---|---| +| Null | — | +| Boolean | 1 byte | +| Integer | §6.1 signed | +| Float | 8 bytes, the existing order-preserving bit transform, NaN canonicalised | +| String ≤ 64 B | bytes with 0x00 escaped as `00 FF`, terminated by `00 00` | +| String > 64 B | first 32 bytes escaped, then marker `00 01`, `hash64`, value ref (`page u64` + `slot u16`) | +| Keyword | `iid` (§6.1). Keywords sort by id, not by name | +| Ref | `eid` (§6.1). Refs sort by eid, not by UUID | + +**Long strings.** Ordering is exact among short strings, and between strings whose first +32 bytes differ. Strings that share the first 32 bytes and of which at least one is long +are ordered by marker and hash, not by content. Range predicates (`<`, `>`, prefix) over +such values must re-check the full value. Equality is exact: encode the probe the same +way, seek to `prefix ‖ marker ‖ hash`, and compare the full value of each candidate to +rule out hash collisions. + +Comparisons on keywords and refs never relied on the order of names or UUIDs. The query +layer must not use AVET order for keyword ranges; §11 audits this. + +### 6.3 Value pages + +Long values are stored in append-only value pages (0x51), packed like today's fact +pages. They are never rewritten and never freed, because a retraction stores the same +value again rather than deleting it. They are reachable only through value refs in index +keys, so verify (#373) finds them by walking the indexes. + +**Dedup:** before a new long value is written, DICT tag 0x06 is looked up by `hash64`, +and each candidate's full value is compared. A retraction or re-assertion of the same +long value therefore costs no new value page. The 3.0.0 maximum value length is one +value page's payload (4068 B). That is about today's limit, but it now applies to the +value alone rather than the whole fact. `MAX_FACT_BYTES` is replaced by +`MAX_VALUE_BYTES`, a public API change recorded in the CHANGELOG. Values spanning +several pages can come later behind a feature bit. + +## 7. Reads + +- **Cursor.** `LeafCursor` holds a stack of `(internal page, child index)`. To start, + it descends to the first key ≥ `start`. To advance at the end of a leaf, it pops up to + the nearest ancestor with a next child, then descends to that child's leftmost leaf. + The amortised cost per step is O(1), and memory is O(depth). `range_scan`, + `stream_all_entries` and the `CommittedIndexReader` methods are rewritten on top of + it. #432 exposes it later. +- **Seek.** `LeafCursor::seek(key)` moves to the first entry ≥ `key`, never backwards. + If `key` is in the current leaf, it binary-searches that leaf. Otherwise it pops the + stack to the lowest ancestor whose key range still covers `key`, and descends from + there, not from the root. A seek to a nearby key costs O(1) page visits, and one to a + key d leaves away costs O(log d). A seek to a key below the current position is a + no-op. Merge joins and leapfrog-style worst-case-optimal joins in the streaming + engine (#432) call `seek` on each index ordering constantly, so it must stay cheap. +- **Covering reads.** Index entries decode to whole facts. Ids are translated through + DICT (§5.1). No other page is read except a value page for a long value. +- **Full fact scans** are an EAVT cursor scan. +- **Open** reads two meta pages and nothing else. Pages are verified when first read + (§4.2). The rebuild-on-checksum-mismatch branch in `load()` is deleted. A corrupt + page is now an error on the read that hits it. Repairs are explicit through #373: + `verify`, and `rebuild_indexes` from EAVT or AEVT, each of which holds every fact. + +## 8. Checkpoint + +Let `M` be the active meta, with generation `g`. The new checkpoint commits generation +`g' = g + 1` into slot `g' % 2`. + +### 8.1 Invariant + +A checkpoint writes only to pages that `M` does not reference. Those are pages on `M`'s +free list and pages at or above `M.page_count`. Three things follow: + +- A crash before the meta write leaves `M` and everything it references untouched (G1). +- Queries running concurrently through the in-memory `OnDiskIndexReader` (still on `M`'s + roots) never read a page that is being overwritten. +- Pages freed by this checkpoint are not reusable until the next one. The reader swap at + the end of this checkpoint happens before that. + +The implementation must confirm that no query keeps an `OnDiskIndexReader` across two +checkpoints. Today each `range_scan_*` runs under the `FactStorage` guard that +`set_committed_index_reader` needs. Long-value reads go only to value pages, which are +never freed. A test pins this down (§11). + +### 8.2 Allocation policy + +- **Value pages** always append at `page_count`. They are never freed. +- **B+tree and free-list pages** take from `M`'s free list first and append only when + it is empty. In steady state, tree churn reuses the pages freed one checkpoint + earlier, and the file grows only by net tree growth and new long values. +- **Layout over time:** page kinds interleave freely. Nothing needs to be contiguous; + every page is reached from a root in the meta page or from the free-list head. + +### 8.3 Steps + +1. **Snapshot.** Take `M` and the pending facts. Build an allocator from `M`'s free list + and `M.page_count`. +2. **Long values.** Write new long values (after dedup, §6.3) into new value pages, + appended and stamped with `g'`. Their value refs complete the pending keys. +3. **Trees.** For each of the five trees (the four indexes, then DICT with the new + eid/iid/tx/dedup entries), run a copy-on-write batch insert of the sorted pending + entries: descend from the root, route entries to leaves by separator keys, merge + each touched leaf and split it by balanced bytes, then rewrite each touched internal + node into a new page. A root split adds a level. Every page replaced along the way + goes into `freed`. +4. **Free list.** Pop is already done by the allocator. Push `freed` and the consumed + free-list pages as new head pages (§4.4). +5. **Data sync.** All pages above have been written, each stamped with `g'` and its CRC. + Call `backend.sync()`. +6. **Commit.** Write meta `g'` (with the new roots, `next_eid` and `next_iid`) to slot + `g' % 2`, then call `backend.sync()`. This is the only commit point. +7. **Publish.** Swap the in-memory readers to the new roots and clear the pending facts. + Then delete the WAL in `do_checkpoint`, as today. + +`fact_prefix_crc`, `rebuild_btree_incremental`'s copy-every-leaf path, +`collect_leaf_pages`, `invalidate_from` and the full-file checksum are removed. The page +cache stays write-through (`put_dirty` on every write), so a reused page id never serves +stale content. + +### 8.4 Close-time checkpoint + +Kept (D10). Under G2 it costs O(change), so #434 acceptance 2 is met through the bound +and reopen stays fast. + +## 9. Migration from v7 + +A legacy file has an 84-byte v7 `FileHeader` at page 0 (version 7, header CRC valid) +and no valid meta page. Only v7 is migrated. A page 0 that is neither a valid meta page +nor a v7 header, including a pre-release v8 single-header file, is rejected with +"no valid meta page". + +1. Read the legacy header (header CRC checked) and all facts from pages + `1..=fact_page_count` (legacy 12-byte fact header). +2. Assign eids and iids in `tx_count` order (§5.1). From `old_page_count` up, append + value pages for long values, then the five trees built by `build_btree` (bulk build + from sorted input, stamped and checksummed). Set the free list to old pages + `2..old_page_count`. They become unreferenced at commit. Page 1 is excluded because + it is meta slot B. +3. Append a **backup copy of meta generation 1** as the last page, sync, then write meta + generation 1 to page 0 and sync. The commit overwrites the legacy header. Page 1 + still holds old fact bytes, which are not a valid meta, so it is ignored until + generation 2 writes it. The backup page is on the generation-1 free list. +4. A crash before the page 0 write leaves the legacy header intact, and the appended + pages lie beyond its `page_count`. The next open runs the migration again. +5. A torn page 0 write leaves neither a valid meta nor a v7 header, and page 1 is not a + meta either. Only at this point does open read the file's last page. If it is a + valid meta with generation 1 whose `page_count` matches the file, open copies it to + page 0 and continues. Otherwise it fails with "no valid meta page". Generation 2 + reuses the backup page from the free list, so the fallback never sees a stale + backup. + +Cost: one O(N) pass. The file temporarily holds both copies, and the old region becomes +free pages that later tree growth reuses. The file does not shrink until a vacuum +exists. That is an accepted one-time cost, listed in the CHANGELOG. + +## 10. Estimates + +### 10.1 Size at 1B facts + +| component | bytes per fact | +|---|---| +| EAVT entry after prefix compression (e, a usually shared with the previous entry) | ~22 | +| AEVT | ~24 | +| AVET | ~26 | +| VAET (≈30 % of facts are refs) | ~8 | +| leaf fill 75 %, internal nodes ~1 % | × 1.35 | +| DICT (2 entries per entity, 1 per tx, amortised) | ~5 | +| **total, excluding long values** | **~110–140 B → 110–140 GB** | + +This leaves headroom under the 300 GB budget (G6) for long values and for history. The +benchmark in #394 checks the estimate at each decade. + +### 10.2 Write amplification + +New entities get the next eid, so their EAVT and AEVT entries land at the right edge (of +the tree, and of each attribute's range). AVET entries and VAET entries pointing at old +targets stay random; this is the remaining source of write amplification. If #394 +measures more than 10× at steady state, feature bits (§4.1.2) allow Bε-style buffered +internal nodes in v3.x without a format v9. + +## 11. Testing + +TDD per component. No new dependencies. Test assert messages follow the CodeQL rule. + +**Pages and commit** + +- **Page header:** encode/verify round trip; a flipped bit, a wrong `page_id` and a + future `generation` each give their own STG code; a failed page is not cached. +- **Meta selection:** both valid (highest generation wins). Each row of the §4.1.1 + table: torn newer slot with WAL base `g` (open at `g`, replay); WAL base `> g` + (error); no WAL with a `g+1` page on `M_g`'s free list or past `M_g.page_count` + (error, each location tested); no WAL and no `g+1` page (open at `g`); `g == 1` with + slot B empty. Neither valid: v7 header (migration); torn migration commit with backup + meta (recovered); pre-release v8 single header or anything else (error). +- **Feature bits:** a file with an unknown `required_features` bit fails with the new + STG code and is not modified. v3.0.0 writes 0. +- **Allocator and free list:** pop/push across many generations. Invariant check after + each checkpoint: the reachable set (all five trees, the value pages their keys + reference, and the free-list chain) and the free ids are disjoint, and together they + cover `2..page_count` exactly. This also detects leaks. +- **Crash atomicity:** extend `crash_at_every_point_in_save_loses_no_checkpointed_fact`. + Inject a failure at every write and sync, and add torn writes, including a torn meta + write, using a new `FaultInjectingBackend` mode that writes a prefix of the page. After + each, reopen with no index rebuild and check: checkpointed facts equal the model, WAL + replay restores the rest, and the invariant above holds. +- **Cost bound (#434 acceptance 1, 4):** a page-counting backend measures pages written + by a checkpoint after k ∈ {1, 100} facts, on graphs of 10k and 100k facts. The count + must grow by at most the tree-depth difference between the two sizes. A guard asserts + that no page referenced by the previous meta was written. +- **Concurrency:** queries running during checkpoints in `concurrency_test` still return + consistent results, and no read ever fails CRC. +- **Corruption surfacing:** corrupt a leaf, a value page and a free-list page in turn. A + query or a checkpoint returns the STG code and never wrong data. + +**Trees and cursor** + +- **Copy-on-write insert equivalence:** random committed sets and pending batches + (including splits, keys below the first leaf and above the last, root splits). + `stream_all_entries` of the result must equal the merged sorted set. The old root + must still stream its old contents unchanged, which proves it was not written to. +- **Prefix compression and restarts:** random keys round-trip through a leaf; lookup + agrees with a linear scan; separators satisfy `max(left) < s ≤ min(right)`. +- **Cursor:** `range_scan` with random bounds, compared with a filter over the + expected set, across depth 1–4 trees. +- **Seek:** random monotone seek sequences give the same positions as a fresh descent + from the root. This covers seeks within a leaf, to a sibling, across subtrees, past + the end, and backwards (no-op). A page-read counter shows that a seek to the + neighbouring leaf reads no internal page that the cursor already holds. + +**Keys and data model** + +- **Encoding:** memcmp order equals logical order on random component tuples for every + value type: negative, zero and large integers, NaN and ±0.0 floats, strings containing + 0x00, strings at exactly 64 and 65 bytes, FOREVER. Round trip of every component. +- **Long values:** equality lookup finds exactly one match despite a forced hash + collision (test hook). A range predicate over strings sharing a 32-byte prefix gives + the same result as a full sort. Dedup: re-asserting and retracting a long value adds + no value page. +- **Ids:** assignment is deterministic across WAL replay, with a crash between transact + and checkpoint. eids and iids are never reused. Keyword-as-attribute and + keyword-as-value share an iid. +- **Covering:** every query result comes from index entries; a counting backend shows + no value-page reads for facts without long values. +- **Order audit:** grep tests and bindings for assumptions about result order; sort + results in tests that compare lists. + +**Migration, size, benchmarks** + +- **Migration:** v7 fixtures give identical query results (as sets) and the same + `tx_count` floor after migration; crash at every point of the migration; a pre-release + v8 single-header file is rejected. +- **Size:** generate 1M facts in #433's acceptance shape (~10 attributes per entity, + 20 % multi-valued, 10 % retracted and re-asserted). Bytes per fact must be ≤ 200 at + 1M. #394 extends the measurement to 1B. +- **Benchmark:** `checkpoint/after_1_fact` and `checkpoint/after_100k_facts` at 10k, + 100k and 1M facts, recording bytes written per checkpoint. Write amplification is + reported for #394, and 1B is measured there. + +## 12. Errors, docs, compatibility + +- New STG codes: page checksum mismatch, page id mismatch, page generation ahead of + meta, no valid meta page, meta damaged after commit (§4.1.1), unsupported file + feature (§4.1.2), free-list/allocator inconsistency. The codes for the removed paths + (header CRC mismatch `INT-053`, index rebuild) stay registered and are marked + deprecated, never recycled. Update `docs/ERROR_REFERENCE.md`. +- WAL format version 2: the header gains `base_generation u64` at bytes 8..16, taken + from the reserved bytes. A v1 WAL is accepted only next to a v7 file being migrated. +- Public API: `MAX_FACT_BYTES` → `MAX_VALUE_BYTES` (§6.3). Committed scan order changes + (§5.3). +- Browser: `BrowserBufferBackend` dirty sets become O(change). The IndexedDB flush must + write the meta page in the same IDB transaction as the data pages. Verify this, and + fix it if it is not already the case. +- Docs: the `Minigraf::checkpoint` and `wal_checkpoint_threshold` rustdoc drop "copies + pages in proportion to the total index size". Also update the CLAUDE.md "File Format" + section, `.wiki/Architecture.md`, CHANGELOG (format, `MAX_VALUE_BYTES`, migration + file growth, result order) and ROADMAP. +- Philosophy: aligned. Single file, reliability first, no dependencies, and the format + change goes into the unreleased v8, not a v9. + +## 13. Alternatives rejected + +- **Parent-held child checksums (ZFS style).** These would catch lost writes, but every + internal pointer and every value ref would grow by 4 bytes, against the density goal. + In-page CRC plus page id plus generation catches torn, corrupt and misdirected pages. +- **Single header page.** A torn header write would make the file unopenable. +- **Removing the close-time checkpoint.** It is unnecessary once checkpoints are + O(change). Removing it would slow reopens and change binding behaviour (#322). +- **Appending to the last partial value page in place.** Under per-page CRCs, a torn + in-place write would destroy values that were already committed. Each checkpoint + that writes long values therefore starts a fresh value page. The space lost to + partly filled pages is bounded by one page per checkpoint that writes long values. +- **Fact pages plus reference indexes.** One random read per query match, and the fact + stored once more on top of four near-complete index entries (§3.1). +- **Leaves shared across trees.** Not possible: the four sort orders put different + facts next to each other (§3.1). +- **LSM tree.** High ingest rate, but background compaction typically rewrites data + 10–30×, needs background threads and space management, and adds many moving parts. +- **Fewer indexes** (both rejected for 3.0.0): + - **Drop AEVT.** Attribute scans would use AVET, which returns entries in value order + rather than entity order. Joins on `?e` would then need a sort or a hash. It saves + about 30 % of index bytes. + - **Opt-in AVET per attribute** (Datomic's `:db/index`). Value lookups on attributes + without it become full attribute scans. Turning it on per attribute is a schema + setting, which goes against zero-configuration. If #394 shows that index writes + dominate, opt-in AVET can come later behind a feature bit (§4.1.2). + +## 14. Delivery (PRs into `v3`) + +1. **Cursor scans:** add `LeafCursor` with `seek` and move every scan onto it, still on + the current format. Behaviour does not change. +2. **v8 page format:** common page header with CRC/id/generation, verify on read, meta + pages A/B with meta selection, feature bits, WAL v2. `save()` still does a full + rebuild into fresh pages, which is atomic but O(N). (#388, #374 atomicity) +3. **Covering keys (#433):** byte-comparable key encoding, prefix-compressed nodes, DICT, + value pages, eid/iid assignment, covering reads, v7 migration. +4. **Copy-on-write insert, allocator, free list:** O(change) checkpoints. (#434) +5. **Cost and crash test hardening, benchmarks, docs.** + +The format freezes for #391 once PRs 2 and 3 have merged. PRs 4 and 5 do not change it. diff --git a/src/storage/btree_v6.rs b/src/storage/btree_v6.rs index 1c8628cb77..47f523b44d 100644 --- a/src/storage/btree_v6.rs +++ b/src/storage/btree_v6.rs @@ -456,36 +456,46 @@ pub fn merge_sorted_vecs(a: Vec, b: Vec) -> impl Iterator Result>>> { - // A chain longer than the file has pages must contain a cycle. - let max_leaves = backend.page_count()?; + // A tree cannot have more nodes than the file has pages; more visits + // means a cycle in the child pointers. + let max_visits = backend.page_count()?; + let mut visits: u64 = 0; let mut leaves = Vec::new(); - let mut leaf_id = find_leftmost_leaf(root_page_id, backend, cache)?; - loop { - let page = cache.get_or_load(leaf_id, backend)?; - if page.first().copied() != Some(PAGE_TYPE_LEAF) { - bail_coded!( - ErrorCode::Int049, - format!("collect_leaf_pages: expected leaf page at page_id={leaf_id}") - ); - } - if u64::try_from(leaves.len()).map_or(true, |n| n >= max_leaves) { + let mut stack = vec![(root_page_id, 0usize)]; + while let Some((page_id, depth)) = stack.pop() { + visits = visits.saturating_add(1); + if depth > MAX_TREE_DEPTH || visits > max_visits { bail_coded!( ErrorCode::Int049, - format!("collect_leaf_pages: leaf chain longer than the file at page_id={leaf_id}") + format!( + "collect_leaf_pages: cycle or corruption in child pointers at page_id={page_id}" + ) ); } - validate_leaf_slots(&page[..], leaf_id)?; - let next_leaf = read_u64_at(&page[..], 4)?; - leaves.push(page); - if next_leaf == 0 { - break; + let page = cache.get_or_load(page_id, backend)?; + match page.first().copied() { + Some(PAGE_TYPE_LEAF) => { + validate_leaf_slots(&page[..], page_id)?; + leaves.push(page); + } + Some(PAGE_TYPE_INTERNAL) => { + let children = internal_children(&page[..])?; + stack.extend( + children + .into_iter() + .rev() + .map(|c| (c, depth.saturating_add(1))), + ); + } + _ => bail_coded!(ErrorCode::Stg013, page_id), } - leaf_id = next_leaf; } Ok(leaves) } @@ -711,6 +721,7 @@ where // ─── Leaf traversal helpers ─────────────────────────────────────────────────── /// Traverse internal nodes from `root` to find the leftmost (first) leaf page. +#[cfg(test)] #[allow(clippy::arithmetic_side_effects)] fn find_leftmost_leaf(root: u64, backend: &dyn StorageBackend, cache: &PageCache) -> Result { let mut page_id = root; @@ -743,73 +754,6 @@ fn find_leftmost_leaf(root: u64, backend: &dyn StorageBackend, cache: &PageCache } } -/// Traverse from `root` to the leaf that would contain `key`. -// Called by range_scan which is called by OnDiskIndexReader::range_scan_*. -#[allow(dead_code)] -#[allow(clippy::arithmetic_side_effects)] -fn find_leaf_for_key( - root: u64, - key: &K, - backend: &dyn StorageBackend, - cache: &PageCache, -) -> Result -where - K: for<'de> Deserialize<'de> + Ord, -{ - let mut page_id = root; - loop { - let page = cache.get_or_load(page_id, backend)?; - let page_type = page.first().copied().ok_or_else(|| { - err_coded!( - ErrorCode::Int049, - format!("empty page at page_id={page_id}") - ) - })?; - match page_type { - PAGE_TYPE_LEAF => return Ok(page_id), - PAGE_TYPE_INTERNAL => { - let key_count = read_u16_at(&page[..], 2)? as usize; - let rightmost_child = read_u64_at(&page[..], 4)?; - let child_arr_start = INTERNAL_HEADER_SIZE; - let slot_dir_start = INTERNAL_HEADER_SIZE + key_count * 8; - - let mut descended = false; - for i in 0..key_count { - let slot_off = slot_dir_start + i * SLOT_SIZE; - let sep_offset = read_u16_at(&page[..], slot_off)? as usize; - let sep_length = read_u16_at(&page[..], slot_off + 2)? as usize; - let sep_slice = page - .get(sep_offset..sep_offset.saturating_add(sep_length)) - .ok_or_else(|| { - err_coded!(ErrorCode::Int049, format!( - "sep slice out of bounds: offset={sep_offset} len={sep_length} page_len={}", - page.len() - )) - })?; - let sep_key: K = postcard::from_bytes(sep_slice)?; - - if *key < sep_key { - let child_off = child_arr_start + i * 8; - page_id = read_u64_at(&page[..], child_off)?; - descended = true; - break; - } - } - if !descended { - page_id = rightmost_child; - } - } - t => bail_coded!( - ErrorCode::Int049, - format!( - "find_leaf_for_key: unexpected page type 0x{:02x} at page_id={}", - t, page_id - ) - ), - } - } -} - /// Read all `(K, FactRef)` entries from a leaf page's slot directory. #[allow(clippy::arithmetic_side_effects)] fn read_leaf_entries(page: &[u8]) -> Result> @@ -839,6 +783,259 @@ where Ok(entries) } +// ─── LeafCursor ─────────────────────────────────────────────────────────────── + +/// Deepest tree a reader descends. Every internal node has at least two +/// children, so a real tree this deep would need 2^32 leaves; anything deeper +/// is a cycle in the child pointers or corruption. +const MAX_TREE_DEPTH: usize = 32; + +/// Child page ids of an internal node, in key order (`rightmost_child` last). +#[allow(clippy::arithmetic_side_effects)] +fn internal_children(page: &[u8]) -> Result> { + let key_count = read_u16_at(page, 2)? as usize; + let mut children = Vec::with_capacity(key_count + 1); + for i in 0..key_count { + children.push(read_u64_at(page, INTERNAL_HEADER_SIZE + i * 8)?); + } + children.push(read_u64_at(page, 4)?); + Ok(children) +} + +/// One internal node on the cursor's path from the root. +/// +/// Separators are decoded on demand (binary search decodes O(log n) of them), +/// so descending through a node never decodes every key it holds. +struct Frame { + page: Arc>, + key_count: usize, + /// Index into the node's children of the subtree the cursor is in; + /// `key_count` means `rightmost_child`. + child_idx: usize, +} + +impl Frame { + fn new(page: Arc>) -> Result { + let key_count = read_u16_at(&page[..], 2)? as usize; + Ok(Frame { + page, + key_count, + child_idx: 0, + }) + } + + /// Child page id `i` (`i == key_count` is `rightmost_child`). + #[allow(clippy::arithmetic_side_effects)] + fn child(&self, i: usize) -> Result { + if i == self.key_count { + read_u64_at(&self.page[..], 4) + } else { + read_u64_at(&self.page[..], INTERNAL_HEADER_SIZE + i * 8) + } + } + + /// Separator `i`: the first key of child `i + 1`'s subtree, as written by + /// [`write_internal_page`]. + #[allow(clippy::arithmetic_side_effects)] + fn sep Deserialize<'de>>(&self, i: usize) -> Result { + let slot_off = INTERNAL_HEADER_SIZE + self.key_count * 8 + i * SLOT_SIZE; + let sep_offset = read_u16_at(&self.page[..], slot_off)? as usize; + let sep_length = read_u16_at(&self.page[..], slot_off + 2)? as usize; + let sep_slice = self + .page + .get(sep_offset..sep_offset.saturating_add(sep_length)) + .ok_or_else(|| { + err_coded!( + ErrorCode::Int049, + format!( + "sep slice out of bounds: offset={sep_offset} len={sep_length} page_len={}", + self.page.len() + ) + ) + })?; + Ok(postcard::from_bytes(sep_slice)?) + } + + /// The child to take for `key`, searching children `from..`: the number of + /// separators `<= key`, counted from `from`. + #[allow(clippy::arithmetic_side_effects)] + fn route(&self, key: &K, from: usize) -> Result + where + K: for<'de> Deserialize<'de> + Ord, + { + let (mut lo, mut hi) = (from, self.key_count); + while lo < hi { + let mid = lo + (hi - lo) / 2; + if self.sep::(mid)? <= *key { + lo = mid + 1; + } else { + hi = mid; + } + } + Ok(lo) + } +} + +/// Forward cursor over a B+tree's entries in key order. +/// +/// Holds the path from the root as a stack of internal nodes, so moving to +/// the next leaf or seeking forward re-reads only the pages below the lowest +/// ancestor that still covers the target. Leaf `next_leaf` pointers are never +/// read: a copy-on-write tree (#374) cannot keep them. +pub(crate) struct LeafCursor<'a, K> { + backend: &'a dyn StorageBackend, + cache: &'a PageCache, + stack: Vec, + entries: Vec<(K, FactRef)>, + pos: usize, + /// Set once the cursor has moved past the last leaf. + done: bool, +} + +impl<'a, K> LeafCursor<'a, K> +where + K: for<'de> Deserialize<'de> + Ord + Clone, +{ + /// A cursor positioned before the first entry `>= start` (`None`: the first entry). + pub(crate) fn new( + root: u64, + start: Option<&K>, + backend: &'a dyn StorageBackend, + cache: &'a PageCache, + ) -> Result { + let mut cursor = LeafCursor { + backend, + cache, + stack: Vec::new(), + entries: Vec::new(), + pos: 0, + done: false, + }; + cursor.descend(root, start)?; + Ok(cursor) + } + + /// The next entry in key order, or `None` past the last one. + #[cfg(test)] + pub(crate) fn next(&mut self) -> Result> { + Ok(self.next_ref()?.cloned()) + } + + /// Like [`next`](Self::next), but borrows the entry instead of cloning it. + #[allow(clippy::arithmetic_side_effects)] + pub(crate) fn next_ref(&mut self) -> Result> { + loop { + if self.done { + return Ok(None); + } + if self.pos < self.entries.len() { + self.pos += 1; + return Ok(self.entries.get(self.pos - 1)); + } + if !self.advance_leaf()? { + return Ok(None); + } + } + } + + /// Move forward to the first entry `>= key`. A key at or before the + /// current position leaves the cursor where it is. + // Only tests call this until the streaming engine's joins (#432) do. + #[allow(dead_code)] + #[allow(clippy::arithmetic_side_effects)] + pub(crate) fn seek(&mut self, key: &K) -> Result<()> { + if self.done { + return Ok(()); + } + if let Some((next_key, _)) = self.entries.get(self.pos) + && key <= next_key + { + return Ok(()); + } + // Find the lowest node whose range covers `key`. The child a frame + // is in ends at that frame's separator `child_idx`; a rightmost child + // inherits its parent's bound. `reroute` is the frame to route `key` + // in again; `stack.len()` means the current leaf covers it. + let mut reroute = self.stack.len(); + for (d, f) in self.stack.iter().enumerate().rev() { + if f.child_idx < f.key_count { + if *key < f.sep::(f.child_idx)? { + break; + } + reroute = d; + } + } + if reroute == self.stack.len() { + let p = self.entries.partition_point(|(k, _)| k < key); + self.pos = self.pos.max(p); + return Ok(()); + } + self.stack.truncate(reroute + 1); + let top = self + .stack + .last_mut() + .ok_or_else(|| err_coded!(ErrorCode::Int049, "seek: empty cursor stack".to_string()))?; + let c = top.route(key, top.child_idx)?; + top.child_idx = c; + let child = top.child(c)?; + self.descend(child, Some(key)) + } + + /// Move to the start of the next leaf. Returns false past the last leaf. + #[allow(clippy::arithmetic_side_effects)] + pub(crate) fn advance_leaf(&mut self) -> Result { + loop { + let Some(top) = self.stack.last_mut() else { + self.done = true; + self.entries.clear(); + self.pos = 0; + return Ok(false); + }; + if top.child_idx < top.key_count { + top.child_idx += 1; + let child = top.child(top.child_idx)?; + self.descend(child, None)?; + return Ok(true); + } + self.stack.pop(); + } + } + + /// Descend from `page_id` to the leaf that holds `key`, or to the + /// leftmost leaf when `key` is `None`. + fn descend(&mut self, page_id: u64, key: Option<&K>) -> Result<()> { + let mut page_id = page_id; + loop { + if self.stack.len() >= MAX_TREE_DEPTH { + bail_coded!( + ErrorCode::Int049, + format!( + "tree deeper than {MAX_TREE_DEPTH} at page_id={page_id}: cycle or corruption" + ) + ); + } + let page = self.cache.get_or_load(page_id, self.backend)?; + match page.first().copied() { + Some(PAGE_TYPE_LEAF) => { + self.entries = read_leaf_entries(&page[..])?; + self.pos = key.map_or(0, |k| self.entries.partition_point(|(e, _)| e < k)); + return Ok(()); + } + Some(PAGE_TYPE_INTERNAL) => { + let mut frame = Frame::new(page)?; + frame.child_idx = match key { + Some(k) => frame.route(k, 0)?, + None => 0, + }; + page_id = frame.child(frame.child_idx)?; + self.stack.push(frame); + } + _ => bail_coded!(ErrorCode::Stg013, page_id), + } + } + } +} + // ─── stream_all_entries ─────────────────────────────────────────────────────── /// Stream all `(K, FactRef)` entries from a B+tree in sorted order. @@ -852,48 +1049,21 @@ pub fn stream_all_entries( cache: &PageCache, ) -> Result> where - K: for<'de> Deserialize<'de> + Ord, + K: for<'de> Deserialize<'de> + Ord + Clone, { - let first_leaf = find_leftmost_leaf(root_page_id, backend, cache)?; + let mut cursor = LeafCursor::new(root_page_id, None, backend, cache)?; let mut result = Vec::new(); - let mut leaf_id = first_leaf; - - loop { - let page = cache.get_or_load(leaf_id, backend)?; - let page_type = page.first().copied().ok_or_else(|| { - err_coded!( - ErrorCode::Int049, - format!("empty page at page_id={leaf_id}") - ) - })?; - if page_type != PAGE_TYPE_LEAF { - bail_coded!( - ErrorCode::Int049, - format!( - "stream_all_entries: expected leaf page at page_id={}", - leaf_id - ) - ); - } - let next_leaf = read_u64_at(&page[..], 4)?; - result.extend(read_leaf_entries::(&page[..])?); - - if next_leaf == 0 { - break; - } - leaf_id = next_leaf; + while let Some(entry) = cursor.next()? { + result.push(entry); } - Ok(result) } // ─── range_scan ─────────────────────────────────────────────────────────────── -/// Scan the B+tree for all `FactRef`s whose key is in `[start, end]`. +/// Scan the B+tree for all `FactRef`s whose key is in `[start, end)`. /// -/// `end: None` means unbounded (scan to last leaf). -// Called by OnDiskIndexReader::range_scan_* (via trait object dispatch). -#[allow(dead_code)] +/// `end: None` means unbounded (scan to the last leaf). pub fn range_scan( root_page_id: u64, start: &K, @@ -902,44 +1072,16 @@ pub fn range_scan( cache: &PageCache, ) -> Result> where - K: Serialize + for<'de> Deserialize<'de> + Ord, + K: for<'de> Deserialize<'de> + Ord + Clone, { - let start_leaf = find_leaf_for_key(root_page_id, start, backend, cache)?; + let mut cursor = LeafCursor::new(root_page_id, Some(start), backend, cache)?; let mut result = Vec::new(); - let mut leaf_id = start_leaf; - - 'outer: loop { - let page = cache.get_or_load(leaf_id, backend)?; - let page_type = page.first().copied().ok_or_else(|| { - err_coded!( - ErrorCode::Int049, - format!("empty page at page_id={leaf_id}") - ) - })?; - if page_type != PAGE_TYPE_LEAF { - bail_coded!(ErrorCode::Stg013, leaf_id); - } - let next_leaf = read_u64_at(&page[..], 4)?; - let entries: Vec<(K, FactRef)> = read_leaf_entries(&page[..])?; - - for (k, fr) in entries { - if k < *start { - continue; - } - if let Some(e) = end - && k >= *e - { - break 'outer; - } - result.push(fr); - } - - if next_leaf == 0 { + while let Some((k, fr)) = cursor.next_ref()? { + if end.is_some_and(|e| k >= e) { break; } - leaf_id = next_leaf; + result.push(*fr); } - Ok(result) } @@ -1215,15 +1357,49 @@ mod tests { } #[test] - fn test_collect_leaf_pages_rejects_cyclic_chain() { - // A corrupt next_leaf pointing back must be an error, not an endless loop. - let (mut backend, cache, root, ids) = multi_leaf_tree(); - let mut page = cache.get_or_load(ids[1], &backend).unwrap().to_vec(); - page[4..12].copy_from_slice(&ids[0].to_le_bytes()); - overwrite_page(&mut backend, &cache, ids[1], page); + fn cursor_cycle_in_child_pointers_is_bounded() { + // A child pointer leading back up the tree must be an error, not a hang. + let (mut backend, cache, root, _ids) = multi_leaf_tree(); + let mut page = cache.get_or_load(root, &backend).unwrap().to_vec(); + assert_eq!(page[0], PAGE_TYPE_INTERNAL, "fixture root must be internal"); + // First child id lives at INTERNAL_HEADER_SIZE; point it at the root. + page[INTERNAL_HEADER_SIZE..INTERNAL_HEADER_SIZE + 8].copy_from_slice(&root.to_le_bytes()); + overwrite_page(&mut backend, &cache, root, page); assert!( collect_leaf_pages(root, &backend, &cache).is_err(), - "cyclic leaf chain must be rejected" + "cycle must be rejected by collect_leaf_pages" + ); + assert!( + stream_all_entries::(root, &backend, &cache).is_err(), + "cycle must be rejected by the cursor" + ); + } + + #[test] + fn range_scan_ignores_next_leaf() { + // Zeroing every next_leaf pointer must not change any read: the cursor + // walks the tree, which a copy-on-write layout (#374) requires. + let (mut backend, cache, root, ids) = multi_leaf_tree(); + let expected: Vec<(EavtKey, FactRef)> = + (0u128..500).map(|n| make_eavt(n, ":a", n as u64)).collect(); + for &id in &ids { + let mut page = cache.get_or_load(id, &backend).unwrap().to_vec(); + page[4..12].copy_from_slice(&0u64.to_le_bytes()); + overwrite_page(&mut backend, &cache, id, page); + } + let got: Vec<(EavtKey, FactRef)> = stream_all_entries(root, &backend, &cache).unwrap(); + assert!(got == expected, "stream must cover every leaf"); + let refs = range_scan(root, &expected[0].0, None, &backend, &cache).unwrap(); + assert_eq!( + refs.len(), + expected.len(), + "range_scan must cover every leaf" + ); + let leaves = collect_leaf_pages(root, &backend, &cache).unwrap(); + assert_eq!( + leaves.len(), + ids.len(), + "collect_leaf_pages must find every leaf" ); } @@ -1791,56 +1967,28 @@ mod tests { // release-build defensive guard and isn't reachable from a normal test // build. No dedicated regression test for STG-011 as a result. - /// A leaf's `next_leaf` chain pointer corrupted to point at a non-leaf - /// page must surface as the coded STG-013 when `range_scan` follows it, - /// not a generic error. `find_leaf_for_key`'s own traversal only - /// validates the *first* leaf it lands on; a corrupted `next_leaf` on a - /// later page in a multi-leaf scan is caught by `range_scan`'s own - /// per-page check. + /// A child pointer corrupted to point at a page that is not a B+tree node + /// must surface as the coded STG-013 when a scan descends into it. #[test] - fn range_scan_corrupted_next_leaf_pointer_returns_stg_013() { - let mut backend = MemoryBackend::new(); - let cache = PageCache::new(512); - // Enough entries with long keys to force a multi-leaf tree with an - // internal-node root (mirrors test_build_btree_leaf_next_pointers_form_chain). - let entries = (0u128..100).map(|n| make_eavt(n, ":verylongattributename", n as u64 + 1)); - let ser = btree_entries(entries).unwrap(); - let (root, _) = build_btree(ser.into_iter(), &mut backend, &cache, 1).unwrap(); - - let root_page = cache.get_or_load(root, &backend).unwrap(); - assert_eq!( - root_page[0], PAGE_TYPE_INTERNAL, - "100 long-key entries must produce an internal-node root for this test to be valid" - ); - - // Find the leftmost leaf by following first children down from root. - let mut leaf_pid = root; - loop { - let p = cache.get_or_load(leaf_pid, &backend).unwrap(); - if p[0] == PAGE_TYPE_LEAF { - break; - } - leaf_pid = read_u64_at(&p[..], 12).unwrap(); - } - - // Corrupt the leftmost leaf's next_leaf pointer (bytes 4..12) to - // point at the internal-node root instead of the next real leaf. - let mut leaf_bytes = backend.read_page(leaf_pid).unwrap(); - leaf_bytes[4..12].copy_from_slice(&root.to_le_bytes()); - backend.write_page(leaf_pid, &leaf_bytes).unwrap(); - cache.invalidate(leaf_pid); - - let start = EavtKey { - entity: Uuid::from_u128(0), - attribute: String::new(), - valid_from: i64::MIN, - valid_to: i64::MIN, - tx_count: 0, - value_bytes: Vec::new(), - asserted: true, - }; + fn cursor_child_pointing_at_non_btree_page_returns_stg_013() { + let (mut backend, cache, root, _ids) = multi_leaf_tree(); + let mut page = cache.get_or_load(root, &backend).unwrap().to_vec(); + assert_eq!(page[0], PAGE_TYPE_INTERNAL, "fixture root must be internal"); + // A page that is neither leaf nor internal (as a fact page would be). + // Well past every page build_btree wrote (MemoryBackend's page_count + // counts written pages, so it can equal the root's id). + let bogus_id = root + 1_000; + let mut bogus = vec![0u8; PAGE_SIZE]; + bogus[0] = crate::storage::packed_pages::PAGE_TYPE_PACKED; + overwrite_page(&mut backend, &cache, bogus_id, bogus); + // Route the leftmost subtree to it. + page[INTERNAL_HEADER_SIZE..INTERNAL_HEADER_SIZE + 8] + .copy_from_slice(&bogus_id.to_le_bytes()); + overwrite_page(&mut backend, &cache, root, page); + + let start = make_eavt(0, ":a", 0).0; let err = range_scan::(root, &start, None, &backend, &cache) - .expect_err("following a next_leaf pointer into a non-leaf page must fail"); + .expect_err("descending into a non-B+tree page must fail"); let coded: crate::error::MinigrafError = err.into(); assert_eq!(coded.code(), "STG-013"); } @@ -1960,4 +2108,322 @@ mod tests { ); } } + + // ─── LeafCursor ────────────────────────────────────────────────────────── + + /// `MemoryBackend` that counts `read_page` calls, for seek cost tests. + struct CountingBackend { + inner: MemoryBackend, + reads: std::sync::atomic::AtomicU64, + } + + impl CountingBackend { + fn reads(&self) -> u64 { + self.reads.load(std::sync::atomic::Ordering::Relaxed) + } + fn reset(&self) { + self.reads.store(0, std::sync::atomic::Ordering::Relaxed); + } + } + + impl StorageBackend for CountingBackend { + fn write_page(&mut self, page_id: u64, data: &[u8]) -> Result<()> { + self.inner.write_page(page_id, data) + } + fn read_page(&self, page_id: u64) -> Result> { + self.reads + .fetch_add(1, std::sync::atomic::Ordering::Relaxed); + self.inner.read_page(page_id) + } + fn sync(&mut self) -> Result<()> { + self.inner.sync() + } + fn page_count(&self) -> Result { + self.inner.page_count() + } + fn close(&mut self) -> Result<()> { + self.inner.close() + } + fn backend_name(&self) -> &'static str { + "counting" + } + fn is_new(&self) -> bool { + self.inner.is_new() + } + } + + /// Entities `0, 2, 4, ...` so every odd entity is a key that is not in the tree. + fn even_entries(n: u128) -> Vec<(EavtKey, FactRef)> { + (0..n) + .map(|i| make_eavt(i * 2, ":attr", i as u64)) + .collect() + } + + fn key_for(entity: u128) -> EavtKey { + make_eavt(entity, ":attr", 0).0 + } + + fn build_tree( + backend: &mut B, + cache: &PageCache, + entries: &[(EavtKey, FactRef)], + ) -> u64 { + let ser = btree_entries(entries.iter().cloned()).unwrap(); + build_btree(ser.into_iter(), backend, cache, 1).unwrap().0 + } + + fn drain(cursor: &mut LeafCursor<'_, EavtKey>) -> Vec<(EavtKey, FactRef)> { + let mut v = Vec::new(); + while let Some(e) = cursor.next().unwrap() { + v.push(e); + } + v + } + + /// Leaf page ids in key order, found through the tree (not next_leaf). + fn leaf_ids(root: u64, backend: &dyn StorageBackend, cache: &PageCache) -> Vec { + let mut ids = Vec::new(); + let mut stack = vec![root]; + while let Some(id) = stack.pop() { + let page = cache.get_or_load(id, backend).unwrap(); + if page[0] == PAGE_TYPE_LEAF { + ids.push(id); + } else { + let children = internal_children(&page[..]).unwrap(); + stack.extend(children.into_iter().rev()); + } + } + ids + } + + fn first_key_of_leaf(id: u64, backend: &dyn StorageBackend, cache: &PageCache) -> EavtKey { + let page = cache.get_or_load(id, backend).unwrap(); + read_leaf_entries::(&page[..]).unwrap()[0] + .0 + .clone() + } + + fn last_key_of_leaf(id: u64, backend: &dyn StorageBackend, cache: &PageCache) -> EavtKey { + let page = cache.get_or_load(id, backend).unwrap(); + read_leaf_entries::(&page[..]) + .unwrap() + .last() + .unwrap() + .0 + .clone() + } + + #[test] + fn cursor_full_scan_matches_input() { + for n in [0u128, 1, 10, 500, 5_000] { + let mut backend = MemoryBackend::new(); + let cache = PageCache::new(4096); + let entries = even_entries(n); + let root = build_tree(&mut backend, &cache, &entries); + if n == 5_000 { + let root_page = cache.get_or_load(root, &backend).unwrap(); + assert_eq!( + root_page[0], PAGE_TYPE_INTERNAL, + "5000 entries need depth >= 2" + ); + } + let mut cursor = LeafCursor::new(root, None, &backend, &cache).unwrap(); + let got = drain(&mut cursor); + assert_eq!(got.len(), entries.len(), "entry count differs"); + assert!(got == entries, "cursor scan differs from input"); + } + } + + #[test] + fn cursor_start_key_positions_at_first_ge() { + let mut backend = MemoryBackend::new(); + let cache = PageCache::new(4096); + let entries = even_entries(2_000); + let root = build_tree(&mut backend, &cache, &entries); + let leaves = leaf_ids(root, &backend, &cache); + assert!(leaves.len() >= 3, "fixture needs several leaves"); + let second_leaf_first = first_key_of_leaf(leaves[1], &backend, &cache); + let pos_of = |k: &EavtKey| entries.partition_point(|(e, _)| e < k); + + let starts = [ + key_for(0), + key_for(1), + key_for(500), + key_for(501), + second_leaf_first, + key_for(3_998), + key_for(3_999), + ]; + for start in &starts { + let mut cursor = LeafCursor::new(root, Some(start), &backend, &cache).unwrap(); + let got = cursor.next().unwrap(); + let want = entries.get(pos_of(start)).cloned(); + assert!(got == want, "first entry after start differs"); + } + } + + #[test] + fn cursor_seek_matches_fresh_descent_random() { + let mut backend = MemoryBackend::new(); + let cache = PageCache::new(4096); + let entries = even_entries(20_000); + let root = build_tree(&mut backend, &cache, &entries); + let mut rng = Rng(0x9E37_79B9_7F4A_7C15); + let mut targets: Vec = (0..2_000) + .map(|_| u128::from(rng.next() % 40_010)) + .collect(); + targets.sort_unstable(); + + let mut cursor = LeafCursor::new(root, None, &backend, &cache).unwrap(); + for t in targets { + let key = key_for(t); + cursor.seek(&key).unwrap(); + let got = cursor.next().unwrap(); + let mut fresh = LeafCursor::new(root, Some(&key), &backend, &cache).unwrap(); + let want = fresh.next().unwrap(); + assert!(got == want, "seek differs from a fresh descent"); + // Put the entry back in play for the next seek (targets may repeat). + cursor = LeafCursor::new(root, Some(&key), &backend, &cache).unwrap(); + } + } + + #[test] + fn cursor_seek_sequence_without_reset_visits_ascending_entries() { + // Monotone seeks on one cursor, interleaved with next(): each result is + // the first entry >= max(target, previous result + 1). + let mut backend = MemoryBackend::new(); + let cache = PageCache::new(4096); + let entries = even_entries(20_000); + let root = build_tree(&mut backend, &cache, &entries); + let mut rng = Rng(0xD1B5_4A32_D192_ED03); + let mut cursor = LeafCursor::new(root, None, &backend, &cache).unwrap(); + let mut consumed = 0usize; // entries before this index have been returned + let mut target: u128 = 0; + while consumed < entries.len() { + target += u128::from(rng.next() % 200); + let key = key_for(target); + cursor.seek(&key).unwrap(); + let expect_idx = consumed.max(entries.partition_point(|(e, _)| e < &key)); + let got = cursor.next().unwrap(); + assert!( + got == entries.get(expect_idx).cloned(), + "seek/next result differs" + ); + consumed = expect_idx + 1; + } + assert!( + cursor.next().unwrap().is_none(), + "cursor must end after the last entry" + ); + } + + #[test] + fn cursor_seek_within_leaf_sibling_and_across_subtrees() { + let mut backend = MemoryBackend::new(); + let cache = PageCache::new(4096); + let entries = even_entries(20_000); + let root = build_tree(&mut backend, &cache, &entries); + let leaves = leaf_ids(root, &backend, &cache); + assert!(leaves.len() > 20, "fixture needs many leaves"); + let first = first_key_of_leaf(leaves[0], &backend, &cache); + let last_in_first = last_key_of_leaf(leaves[0], &backend, &cache); + let sibling = first_key_of_leaf(leaves[1], &backend, &cache); + let far = first_key_of_leaf(leaves[leaves.len() - 2], &backend, &cache); + + let mut cursor = LeafCursor::new(root, Some(&first), &backend, &cache).unwrap(); + for target in [&last_in_first, &sibling, &far] { + cursor.seek(target).unwrap(); + let (k, _) = cursor.next().unwrap().unwrap(); + assert!(k == *target, "seek must land on the target key"); + } + } + + #[test] + fn cursor_seek_past_end() { + let mut backend = MemoryBackend::new(); + let cache = PageCache::new(4096); + let entries = even_entries(5_000); + let root = build_tree(&mut backend, &cache, &entries); + let mut cursor = LeafCursor::new(root, None, &backend, &cache).unwrap(); + cursor.seek(&key_for(1_000_000)).unwrap(); + assert!( + cursor.next().unwrap().is_none(), + "nothing after the last entry" + ); + cursor.seek(&key_for(2_000_000)).unwrap(); + assert!(cursor.next().unwrap().is_none(), "still at the end"); + } + + #[test] + fn cursor_seek_into_gap_after_leaf_end() { + // A key between leaf L's last entry and leaf L+1's first entry: the + // cursor parks at the end of L, and next() moves to L+1. + let mut backend = MemoryBackend::new(); + let cache = PageCache::new(4096); + let entries = even_entries(5_000); + let root = build_tree(&mut backend, &cache, &entries); + let leaves = leaf_ids(root, &backend, &cache); + let last_in_l = last_key_of_leaf(leaves[2], &backend, &cache); + let first_in_next = first_key_of_leaf(leaves[3], &backend, &cache); + // Entities are even, so last + 1 is absent and lies in the gap. + let gap = key_for(last_in_l.entity.as_u128() + 1); + assert!( + gap > last_in_l && gap < first_in_next, + "gap key must sit between leaves" + ); + + let mut cursor = LeafCursor::new(root, None, &backend, &cache).unwrap(); + cursor.seek(&gap).unwrap(); + let (k, _) = cursor.next().unwrap().unwrap(); + assert!( + k == first_in_next, + "next() after a gap seek is the next leaf's first entry" + ); + } + + #[test] + fn cursor_seek_backwards_is_noop() { + let mut backend = MemoryBackend::new(); + let cache = PageCache::new(4096); + let entries = even_entries(5_000); + let root = build_tree(&mut backend, &cache, &entries); + let mut cursor = LeafCursor::new(root, None, &backend, &cache).unwrap(); + cursor.seek(&key_for(6_000)).unwrap(); + cursor.seek(&key_for(10)).unwrap(); + let (k, _) = cursor.next().unwrap().unwrap(); + assert!( + k.entity.as_u128() == 6_000, + "backward seek must not move the cursor" + ); + } + + #[test] + fn cursor_seek_to_next_leaf_reads_one_page() { + // Cache disabled: every page access reaches the backend. + let mut backend = CountingBackend { + inner: MemoryBackend::new(), + reads: std::sync::atomic::AtomicU64::new(0), + }; + let cache = PageCache::new(0); + let entries = even_entries(20_000); + let root = build_tree(&mut backend, &cache, &entries); + let leaves = leaf_ids(root, &backend, &cache); + assert!(leaves.len() > 3, "fixture needs several leaves"); + + let first = first_key_of_leaf(leaves[0], &backend, &cache); + let next_leaf_first = first_key_of_leaf(leaves[1], &backend, &cache); + let mut cursor = LeafCursor::new(root, Some(&first), &backend, &cache).unwrap(); + backend.reset(); + cursor.seek(&next_leaf_first).unwrap(); + assert_eq!( + backend.reads(), + 1, + "seek to the sibling leaf reads only that leaf" + ); + let (k, _) = cursor.next().unwrap().unwrap(); + assert!( + k == next_leaf_first, + "seek lands on the sibling's first entry" + ); + } }