From 782669e61bef42975081c85f73d18682be9cd113 Mon Sep 17 00:00:00 2001 From: Aditya Mukhopadhyay Date: Tue, 6 Oct 2026 09:45:24 +0530 Subject: [PATCH 1/7] docs(v8): detailed plan for PR 5, hardening, benchmarks and docs Co-Authored-By: Claude Opus 5.5 Claude-Session: https://claude.ai/code/session_015GgLEs8YozJjYhwPEYgTUn --- .../plans/2026-10-05-v8-storage-format.md | 67 +++++++++++++++++-- 1 file changed, 62 insertions(+), 5 deletions(-) diff --git a/docs/superpowers/plans/2026-10-05-v8-storage-format.md b/docs/superpowers/plans/2026-10-05-v8-storage-format.md index ba3f4a0440..20fc4f8bf4 100644 --- a/docs/superpowers/plans/2026-10-05-v8-storage-format.md +++ b/docs/superpowers/plans/2026-10-05-v8-storage-format.md @@ -654,10 +654,67 @@ acceptance 1, 2, 4). - [x] `cargo fmt`, clippy, `cargo test`; open the PR into `v3` with `Refs #434 #374`. Own CI until green. Ask before merging. -# PR 5 — Hardening, benchmarks, docs (outline) +# PR 5 — Hardening, benchmarks, docs + +Spec §10, §11, §12. Branch `feat/v8-pr5-hardening`. The format does not change. + +**Outcome:** the remaining acceptance checks of the spec. A damaged page surfaces as its +STG code from every read and checkpoint path, never as wrong or missing data. The size +and checkpoint-cost goals are measured at 1M facts. The docs describe format v8 as it +shipped. + +**Shape decisions (from reading the v3 code after PR 4):** + +- **Error surfacing.** `DatalogExecutor::selective_fact_fetch` swallows lookup errors + (`.ok()?`) and falls back to a full scan, so a damaged AEVT or EAVT page could be + hidden behind another index. It now returns `Result>` and propagates. The + other `unwrap_or_default` reads are of in-memory derived storage, which has no pages, + but they become `?` where the function already returns `Result`. +- **Size test.** A 100k-fact graph in #433's shape (about 10 attributes per entity, 20 % + multi-valued, 10 % retracted and re-asserted) runs in every test run and asserts at + most 200 B per fact. The 1M version is `#[ignore]` and runs in the scheduled job. +- **Benchmarks.** `checkpoint/after_1_fact` gains 1M; a new `checkpoint/after_100k_facts` + runs at 10k and 100k. Pages written per checkpoint are pinned by the cost-bound test + from PR 4; its numbers go into the docs. +- **Read path cost.** Each committed read builds a fresh `DictReader`, so a point lookup + pays for an eid lookup plus a UUID, ident and timestamp lookup per fact. Seed the + memo with what the caller already knows (the entity's UUID, the attribute's name), and + share a bounded cache of idents and transaction timestamps across reads. Neither + changes after commit. -Spec §10, §11, §12. +## Review Focus + +- No read path turns a page error into an empty or partial result. +- The size and cost numbers match the spec's goals (§2 G2, G6). + +### Task 1: Error surfacing + +- [ ] `selective_fact_fetch` propagates errors; `executor.rs` derived reads use `?`. +- [ ] Corruption tests: damage an index leaf, an internal node, a DICT leaf, a value page + and a free-list page in turn (bytes flipped, CRC left stale). Queries through + `Minigraf` on a file, or a checkpoint, return the STG code (STG-029). They never + return rows from the damaged page or silently fewer rows, and a failed checkpoint + leaves the file openable at its last generation. + +### Task 2: Size + +- [ ] `size_per_fact_in_433_shape` (100k, always) and `size_per_fact_1m` (ignored), both + at most 200 B per fact. + +### Task 3: Benchmarks + +- [ ] `checkpoint/after_1_fact/1m` and `checkpoint/after_100k_facts/{10k,100k}`. + +### Task 4: Read path + +- [ ] Seed the `DictReader` memo per call and share an ident and timestamp cache in + `OnDiskReader`, bounded in entries. Re-run `concurrent_btree_scan` and + `btree_lookup/entity_point` against PR 4. + +### Task 5: Docs and PR -- 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. +- [ ] `.wiki/Architecture.md` (format v8 and the read and checkpoint paths), ROADMAP, + CHANGELOG, CLAUDE.md, TEST_COVERAGE, and a status note at the top of the spec. Commit + and push the wiki separately. +- [ ] `cargo fmt`, clippy, `cargo test`; open the PR into `v3` with `Refs #374 #434 #388 #433`. + Own CI until green. Ask before merging. From 3e2feb5b25b66594876299c7a01272478a6fa7c3 Mon Sep 17 00:00:00 2001 From: Aditya Mukhopadhyay Date: Tue, 6 Oct 2026 09:47:15 +0530 Subject: [PATCH 2/7] fix(query): surface damaged-page errors instead of falling back to a full scan selective_fact_fetch swallowed lookup errors and fell back to a full scan, which could hide a damaged index page behind another index. It now returns the error. Corruption tests damage an index leaf, an internal node, a DICT leaf, a value page and a free-list page: every read or checkpoint that reaches the page fails with STG-029, and the file still opens at its last generation. Co-Authored-By: Claude Opus 5.5 Claude-Session: https://claude.ai/code/session_015GgLEs8YozJjYhwPEYgTUn --- src/query/datalog/executor.rs | 26 ++++--- src/storage/persistent_facts.rs | 129 ++++++++++++++++++++++++++++++++ tests/index_corruption_test.rs | 29 +++++++ 3 files changed, 173 insertions(+), 11 deletions(-) diff --git a/src/query/datalog/executor.rs b/src/query/datalog/executor.rs index 298d64f3a0..23de7c9d87 100644 --- a/src/query/datalog/executor.rs +++ b/src/query/datalog/executor.rs @@ -324,7 +324,7 @@ impl DatalogExecutor { // rules require the full fact base to evaluate correctly. if !query.uses_rules() { let patterns = collect_all_patterns(&query.where_clauses); - match self.selective_fact_fetch(&patterns, 4) { + match self.selective_fact_fetch(&patterns, 4)? { Some(facts) => facts, None => self.storage.get_all_facts()?, } @@ -373,9 +373,15 @@ impl DatalogExecutor { /// back to a single whole-entity scan; only if that still exceeds `threshold` does this /// return `None`. Narrowing therefore never turns a selective query into a full scan. /// + /// A lookup error (a damaged page) is returned, never turned into a full scan. + /// /// Results are not deduplicated: the sole caller feeds them to `net_asserted_facts`, /// which is idempotent under duplicated records. - fn selective_fact_fetch(&self, patterns: &[Pattern], threshold: usize) -> Option> { + fn selective_fact_fetch( + &self, + patterns: &[Pattern], + threshold: usize, + ) -> Result>> { use std::collections::{BTreeMap, BTreeSet}; // Per bound entity: Some(attrs) = only these attributes are referenced; @@ -408,7 +414,7 @@ impl DatalogExecutor { if let AttributeSpec::Real(EdnValue::Keyword(attr)) = &pattern.attribute { attributes.insert(attr.clone()); } else { - return None; + return Ok(None); } } @@ -424,7 +430,7 @@ impl DatalogExecutor { entity_attrs.len() + attributes.len() }; if total == 0 || total > threshold { - return None; + return Ok(None); } let mut all_facts: Vec = Vec::new(); @@ -435,20 +441,19 @@ impl DatalogExecutor { for attr in attrs { all_facts.extend( self.storage - .get_facts_by_entity_attribute_indexed(uid, attr) - .ok()?, + .get_facts_by_entity_attribute_indexed(uid, attr)?, ); } } - _ => all_facts.extend(self.storage.get_facts_by_entity(uid).ok()?), + _ => all_facts.extend(self.storage.get_facts_by_entity(uid)?), } } for attr in &attributes { - all_facts.extend(self.storage.get_facts_by_attribute(attr).ok()?); + all_facts.extend(self.storage.get_facts_by_attribute(attr)?); } - Some(all_facts) + Ok(Some(all_facts)) } /// Execute a query: find matching facts and return specified variables @@ -708,8 +713,7 @@ impl DatalogExecutor { // Compute derived_facts Arc once; reuse for plan loop, or-clauses and not-post-filter. // Must use derived_storage (includes rule-derived facts), not filtered_facts (base only). - let derived_facts: Arc<[Fact]> = - Arc::from(derived_storage.get_asserted_facts().unwrap_or_default()); + let derived_facts: Arc<[Fact]> = Arc::from(derived_storage.get_asserted_facts()?); let matcher = PatternMatcher::from_slice_with_valid_at(derived_facts.clone(), valid_at_value.clone()); diff --git a/src/storage/persistent_facts.rs b/src/storage/persistent_facts.rs index b81d4f5bb7..6d718b1e9d 100644 --- a/src/storage/persistent_facts.rs +++ b/src/storage/persistent_facts.rs @@ -1619,4 +1619,133 @@ mod tests { let (one, _) = checkpoint_writes(100_000, 1, true); assert!(one <= 20, "one fact at 100k writes {one} pages"); } + + // ── corruption surfacing (spec §11) ───────────────────────────────────── + + /// A file with several checkpoints, long values and a free list. + fn corruptible() -> MemoryBackend { + let mem = MemoryBackend::new(); + let mut pfs = PersistentFactStorage::new(mem.clone(), 0).unwrap(); + for round in 0..4u64 { + let (asserts, retracts) = mixed_batch(round, 200); + pfs.storage().transact(asserts, None).unwrap(); + pfs.storage().retract(retracts).unwrap(); + pfs.mark_dirty(); + pfs.save().unwrap(); + } + assert!(pfs.meta().freelist_head != 0, "fixture has a free list"); + mem + } + + /// An independent copy of `mem` (`clone` shares the pages). + fn deep_copy(mem: &MemoryBackend) -> MemoryBackend { + let mut copy = MemoryBackend::new(); + for id in 0..mem.page_count().unwrap() { + if let Ok(p) = mem.read_page(id) { + copy.write_page(id, &p).unwrap(); + } + } + copy + } + + /// Flip a body byte of `id`, leaving its CRC stale. + fn flip(mem: &mut MemoryBackend, id: u64) { + let mut p = mem.read_page(id).unwrap(); + p[2000] ^= 0x5A; + mem.write_page(id, &p).unwrap(); + } + + fn leaves_of(root: u64, mem: &MemoryBackend) -> Vec { + let cache = PageCache::new(0); + let mut nodes = Vec::new(); + collect_leaf_pages(root, mem, &cache, Some(&mut nodes)).unwrap(); + nodes + .into_iter() + .filter(|&id| mem.read_page(id).unwrap()[0] == page::PAGE_TYPE_LEAF) + .collect() + } + + /// Every committed read that reaches a damaged page fails with STG-029; it + /// never returns the page's data or silently fewer facts. + #[test] + fn damaged_pages_surface_as_stg_029_on_read() { + let mem = corruptible(); + let m = open_mem(&mem, None).unwrap().meta(); + let value_page = (2..m.page_count) + .find(|&id| mem.read_page(id).unwrap()[0] == page::PAGE_TYPE_VALUE) + .expect("fixture has a value page"); + let eavt_leaf = *leaves_of(m.eavt_root, &mem).last().unwrap(); + let dict_leaf = leaves_of(m.dict_root, &mem)[0]; + let internal = m.eavt_root; + assert_eq!( + mem.read_page(internal).unwrap()[0], + page::PAGE_TYPE_INTERNAL + ); + for (what, id) in [ + ("EAVT leaf", eavt_leaf), + ("EAVT internal node", internal), + ("DICT leaf", dict_leaf), + ("value page", value_page), + ] { + let mut damaged = deep_copy(&mem); + flip(&mut damaged, id); + let pfs = PersistentFactStorage::open(damaged, 0, None).expect("open reads only metas"); + let err = pfs + .storage() + .get_all_facts() + .err() + .unwrap_or_else(|| panic!("{what}: read must fail")); + assert_eq!(code(err), "STG-029", "{what}"); + } + // An AEVT leaf: attribute scans that reach it fail; other reads still work. + let aevt_leaf = leaves_of(m.aevt_root, &mem)[0]; + let mut damaged = deep_copy(&mem); + flip(&mut damaged, aevt_leaf); + let pfs = PersistentFactStorage::open(damaged, 0, None).unwrap(); + let failures = (0..8) + .filter(|a| { + pfs.storage() + .get_facts_by_attribute(&format!(":attr/{a}")) + .is_err() + }) + .count(); + assert!( + failures > 0, + "the attribute stored in the damaged leaf fails" + ); + assert!(pfs.storage().get_all_facts().is_ok(), "EAVT is intact"); + } + + /// A damaged free-list page fails the next checkpoint that pops from it. The + /// file is not changed in any way that matters: it still opens at its last + /// generation and every fact reads back. + #[test] + fn damaged_free_list_page_fails_the_checkpoint_not_the_file() { + let mem = corruptible(); + let before = open_mem(&mem, None).unwrap(); + let m = before.meta(); + let all = as_set(before.storage().get_all_facts().unwrap()); + drop(before); + let mut damaged = deep_copy(&mem); + flip(&mut damaged, m.freelist_head); + let mut pfs = PersistentFactStorage::open(damaged.clone(), 0, None).unwrap(); + assert!( + as_set(pfs.storage().get_all_facts().unwrap()) == all, + "reads do not touch the free list" + ); + let (asserts, _) = mixed_batch(9, 50); + pfs.storage().transact(asserts, None).unwrap(); + pfs.mark_dirty(); + let err = pfs.save().unwrap_err(); + assert_eq!(code(err), "STG-029"); + pfs.dirty = false; + drop(pfs); + let reopened = PersistentFactStorage::open(damaged, 0, None).unwrap(); + assert_eq!( + reopened.generation(), + m.generation, + "the last checkpoint stands" + ); + assert!(as_set(reopened.storage().get_all_facts().unwrap()) == all); + } } diff --git a/tests/index_corruption_test.rs b/tests/index_corruption_test.rs index 42247acd92..cbc7c0b161 100644 --- a/tests/index_corruption_test.rs +++ b/tests/index_corruption_test.rs @@ -124,3 +124,32 @@ fn query_results_after_non_critical_corruption_match_original() { Err(_) => {} } } + +/// v8 (spec §11): a query that reaches a damaged page fails with STG-029. It +/// never returns the page's rows, and never silently returns fewer rows. +#[test] +fn query_over_damaged_leaves_fails_with_stg_029() { + let dir = tempfile::tempdir().unwrap(); + let path = dir.path().join("damaged.graph"); + build_valid_db(&path, 300); + let bytes = std::fs::read(&path).unwrap(); + let leaves: Vec = (2..bytes.len() / PAGE_SIZE) + .filter(|&id| bytes[id * PAGE_SIZE] == 0x61) + .collect(); + assert!(!leaves.is_empty(), "the file has leaf pages"); + for &id in &leaves { + corrupt_bytes_at(&path, (id * PAGE_SIZE + 2000) as u64, 1); + } + let db = Minigraf::open(&path).expect("open reads only the meta pages"); + for q in [ + "(query [:find ?e ?v :where [?e :idx ?v]])", + "(query [:find ?v :where [:e7 :idx ?v]])", + "(query [:find ?e ?a ?v :where [?e ?a ?v]])", + ] { + let err = db + .execute(q) + .err() + .expect("a query over damaged pages must fail"); + assert_eq!(err.code(), "STG-029", "query fails with the checksum code"); + } +} From 6f4a2e56f16fbc97a0a046e45ac8b753a3840137 Mon Sep 17 00:00:00 2001 From: Aditya Mukhopadhyay Date: Tue, 6 Oct 2026 09:49:01 +0530 Subject: [PATCH 3/7] test(storage): bytes per fact in #433's shape at 144k and 1.15M facts 144k facts runs in every test run; 1.15M is ignored and runs in the nightly smoke workflow. Both measure 142 bytes per fact, history included, against the spec's limit of 200. Co-Authored-By: Claude Opus 5.5 Claude-Session: https://claude.ai/code/session_015GgLEs8YozJjYhwPEYgTUn --- .github/workflows/smoke.yml | 5 +++ src/storage/persistent_facts.rs | 61 +++++++++++++++++++++++++++++++++ 2 files changed, 66 insertions(+) diff --git a/.github/workflows/smoke.yml b/.github/workflows/smoke.yml index 80e36fa557..d2296f4322 100644 --- a/.github/workflows/smoke.yml +++ b/.github/workflows/smoke.yml @@ -24,3 +24,8 @@ jobs: run: cargo test --test smoke_test -- --include-ignored --nocapture env: RUST_BACKTRACE: 1 + + - name: Size per fact at 1M facts (spec §11) + run: cargo test --lib size_per_fact_in_433_shape_1m -- --include-ignored --nocapture + env: + RUST_BACKTRACE: 1 diff --git a/src/storage/persistent_facts.rs b/src/storage/persistent_facts.rs index 6d718b1e9d..28c0e85bc7 100644 --- a/src/storage/persistent_facts.rs +++ b/src/storage/persistent_facts.rs @@ -1748,4 +1748,65 @@ mod tests { ); assert!(as_set(reopened.storage().get_all_facts().unwrap()) == all); } + + // ── size (spec §10.1, §11, #433) ──────────────────────────────────────── + + /// File bytes per fact for `entities` entities in #433's acceptance shape: + /// 10 attributes each, 20 % of attributes multi-valued, 10 % retracted and + /// re-asserted, written over 10 checkpoints. + fn bytes_per_fact(entities: u64) -> (u64, u64) { + let mem = MemoryBackend::new(); + let mut pfs = PersistentFactStorage::new(mem.clone(), 256).unwrap(); + let mut facts = 0u64; + let per_round = entities / 10; + for round in 0..10 { + let mut asserts = Vec::new(); + for e in round * per_round..(round + 1) * per_round { + let ent = entity(u128::from(e)); + for a in 0..10u64 { + let attr = format!(":person/a{a}"); + let v = match a { + 0 => Value::String(format!("Name {e}")), + 1 => Value::Keyword(format!(":status/s{}", e % 4)), + 2 => Value::Ref(entity(u128::from((e * 7919) % entities))), + 3 => Value::Float(e as f64 / 3.0), + _ => Value::Integer((e * 10 + a) as i64), + }; + asserts.push((ent, attr.clone(), v)); + if (e + a) % 5 == 0 { + // Multi-valued: a second value. + asserts.push((ent, attr, Value::Integer(-((e * 100 + a) as i64) - 1))); + } + } + } + facts += asserts.len() as u64; + let churn: Vec<_> = asserts.iter().step_by(10).cloned().collect(); + pfs.storage().transact(asserts, None).unwrap(); + pfs.storage().retract(churn.clone()).unwrap(); + pfs.storage().transact(churn.clone(), None).unwrap(); + facts += 2 * churn.len() as u64; + pfs.mark_dirty(); + pfs.save().unwrap(); + } + assert_eq!(pfs.meta().fact_count, facts); + let bytes = mem.page_count().unwrap() * PAGE_SIZE as u64; + (bytes / facts, facts) + } + + /// Spec §11: at most 200 bytes per fact, history included (G6: 300 B at 1B). + #[test] + fn size_per_fact_in_433_shape() { + let (per_fact, facts) = bytes_per_fact(10_000); + assert!(facts > 100_000); + assert!(per_fact <= 200, "{per_fact} bytes per fact"); + } + + /// The same at 1M facts. Slow in a debug build: run by the scheduled job. + #[test] + #[ignore] + fn size_per_fact_in_433_shape_1m() { + let (per_fact, facts) = bytes_per_fact(80_000); + assert!(facts > 1_000_000); + assert!(per_fact <= 200, "{per_fact} bytes per fact"); + } } From 20efd1a28b7c8cb30bd82a2be6741ebe35d48df9 Mon Sep 17 00:00:00 2001 From: Aditya Mukhopadhyay Date: Tue, 6 Oct 2026 09:53:47 +0530 Subject: [PATCH 4/7] bench: checkpoint after one fact at 1M, and after 100k new facts (#434) Co-Authored-By: Claude Opus 5.5 Claude-Session: https://claude.ai/code/session_015GgLEs8YozJjYhwPEYgTUn --- benches/minigraf_bench.rs | 43 ++++++++++++++++++++++++++++++++++++++- 1 file changed, 42 insertions(+), 1 deletion(-) diff --git a/benches/minigraf_bench.rs b/benches/minigraf_bench.rs index cca5fa666f..d9c52bf63e 100644 --- a/benches/minigraf_bench.rs +++ b/benches/minigraf_bench.rs @@ -425,7 +425,7 @@ fn bench_checkpoint_after_1_fact(c: &mut Criterion) { let mut group = c.benchmark_group("checkpoint/after_1_fact"); group.sample_size(20); - for &(label, n) in &[("10k", 10_000usize), ("100k", 100_000)] { + for &(label, n) in &[("10k", 10_000usize), ("100k", 100_000), ("1m", 1_000_000)] { let tmp = NamedTempFile::new().unwrap(); let path = tmp.path().to_str().unwrap().to_string(); helpers::populate_file_no_checkpoint(n, &path); @@ -449,6 +449,46 @@ fn bench_checkpoint_after_1_fact(c: &mut Criterion) { group.finish(); } +// ── checkpoint/after_100k_facts (#434) ─────────────────────────────────────── + +/// Checkpoint cost after 100,000 new facts on an already-checkpointed graph of +/// `n` facts. With copy-on-write checkpoints the cost follows the 100,000 new +/// facts, not `n`. Each sample adds 100,000 more facts, so the graph grows by +/// the sample count over the run. +fn bench_checkpoint_after_100k_facts(c: &mut Criterion) { + use criterion::BatchSize; + use tempfile::NamedTempFile; + + let mut group = c.benchmark_group("checkpoint/after_100k_facts"); + group.sample_size(10); + for &(label, n) in &[("10k", 10_000usize), ("100k", 100_000)] { + let tmp = NamedTempFile::new().unwrap(); + let path = tmp.path().to_str().unwrap().to_string(); + helpers::populate_file_no_checkpoint(n, &path); + let db = helpers::open_file_no_checkpoint(&path); + db.checkpoint().unwrap(); + let mut round = 0u64; + group.bench_function(BenchmarkId::from_parameter(label), |b| { + b.iter_batched( + || { + round += 1; + for chunk in 0..100u64 { + let mut cmd = String::from("(transact ["); + for i in 0..1_000u64 { + cmd.push_str(&format!("[:ck{round}_{chunk}_{i} :val {i}]")); + } + cmd.push_str("])"); + db.execute(&cmd).unwrap(); + } + }, + |()| db.checkpoint().unwrap(), + BatchSize::PerIteration, + ); + }); + } + group.finish(); +} + // ── Task 10: concurrent/ ───────────────────────────────────────────────────── fn bench_concurrent(c: &mut Criterion) { @@ -1828,6 +1868,7 @@ criterion_group!( bench_open, bench_checkpoint, bench_checkpoint_after_1_fact, + bench_checkpoint_after_100k_facts, bench_concurrent, bench_concurrent_file, bench_concurrent_btree_scan, From b8c263d5f7187de73d374f92c06e95dc8307255e Mon Sep 17 00:00:00 2001 From: Aditya Mukhopadhyay Date: Tue, 6 Oct 2026 10:01:33 +0530 Subject: [PATCH 5/7] perf(storage): seed committed reads and share ident/tx lookups Committed reads seed their dictionary memo with the entity UUID and attribute name the caller already passed, and each committed reader keeps a bounded cache of ident and transaction-timestamp lookups shared across reads; neither changes after commit. Concurrent point queries at 100k facts are 19-31 % faster than after PR 4. Co-Authored-By: Claude Opus 5.5 Claude-Session: https://claude.ai/code/session_015GgLEs8YozJjYhwPEYgTUn --- src/storage/dict.rs | 111 +++++++++++++++++++++++++++++++++++++++++- src/storage/reader.rs | 10 +++- 2 files changed, 117 insertions(+), 4 deletions(-) diff --git a/src/storage/dict.rs b/src/storage/dict.rs index ab2d7b2b78..e59435c685 100644 --- a/src/storage/dict.rs +++ b/src/storage/dict.rs @@ -26,11 +26,46 @@ use anyhow::Result; use std::collections::HashMap; use uuid::Uuid; +/// Entries a [`SharedDictCache`] map holds before it is cleared. +const SHARED_CACHE_LIMIT: usize = 65_536; + +/// Ident and transaction lookups shared by every read of one committed meta. +/// They never change once committed, and there are few of them compared with +/// entities, so they are cached across reads; each map is cleared when it +/// reaches [`SHARED_CACHE_LIMIT`] entries. +#[derive(Default)] +pub struct SharedDictCache { + iids: std::sync::RwLock>, + names: std::sync::RwLock>, + tx_ids: std::sync::RwLock>, +} + +fn shared_get( + map: &std::sync::RwLock>, + key: &K, +) -> Option { + map.read().ok()?.get(key).cloned() +} + +fn shared_put( + map: &std::sync::RwLock>, + key: K, + value: V, +) { + if let Ok(mut m) = map.write() { + if m.len() >= SHARED_CACHE_LIMIT { + m.clear(); + } + m.insert(key, value); + } +} + /// Lookups in a committed DICT tree, memoised. pub struct DictReader<'a> { root: u64, backend: &'a dyn StorageBackend, cache: &'a PageCache, + shared: Option<&'a SharedDictCache>, uuids: HashMap, names: HashMap, tx_ids: HashMap, @@ -44,6 +79,7 @@ impl<'a> DictReader<'a> { root, backend, cache, + shared: None, uuids: HashMap::new(), names: HashMap::new(), tx_ids: HashMap::new(), @@ -51,6 +87,22 @@ impl<'a> DictReader<'a> { } } + /// Consult and fill `shared` for idents and transaction timestamps. + pub fn with_shared(mut self, shared: &'a SharedDictCache) -> Self { + self.shared = Some(shared); + self + } + + /// Record a known `eid → uuid` pair (the caller looked the eid up by it). + pub fn seed_entity(&mut self, eid: u64, uuid: Uuid) { + self.uuids.insert(eid, uuid); + } + + /// Record a known `iid → ident` pair. + pub fn seed_ident(&mut self, iid: u32, ident: &str) { + self.names.insert(iid, ident.to_string()); + } + fn get(&self, key: &[u8]) -> Result>> { if self.root == 0 { return Ok(None); @@ -67,12 +119,23 @@ impl<'a> DictReader<'a> { /// The iid of `ident`, if it has one. pub fn iid_of(&self, ident: &str) -> Result> { - self.get(&keys::dict_ident_key(ident))? + if let Some(i) = self + .shared + .and_then(|c| shared_get(&c.iids, &ident.to_string())) + { + return Ok(Some(i)); + } + let found = self + .get(&keys::dict_ident_key(ident))? .map(|v| { u32::try_from(keys::read_uint_bytes(&v)?) .map_err(|_| err_coded!(ErrorCode::Int049, "iid out of range")) }) - .transpose() + .transpose()?; + if let (Some(i), Some(c)) = (found, self.shared) { + shared_put(&c.iids, ident.to_string(), i); + } + Ok(found) } /// The timestamp recorded for `tx_count`, if any. @@ -80,12 +143,19 @@ impl<'a> DictReader<'a> { if let Some(t) = self.tx_ids.get(&tx_count) { return Ok(Some(*t)); } + if let Some(t) = self.shared.and_then(|c| shared_get(&c.tx_ids, &tx_count)) { + self.tx_ids.insert(tx_count, t); + return Ok(Some(t)); + } let found = self .get(&keys::dict_tx_key(tx_count))? .map(|v| keys::read_uint_bytes(&v)) .transpose()?; if let Some(t) = found { self.tx_ids.insert(tx_count, t); + if let Some(c) = self.shared { + shared_put(&c.tx_ids, tx_count, t); + } } Ok(found) } @@ -107,12 +177,19 @@ impl<'a> DictReader<'a> { if let Some(n) = self.names.get(&iid) { return Ok(n.clone()); } + if let Some(n) = self.shared.and_then(|c| shared_get(&c.names, &iid)) { + self.names.insert(iid, n.clone()); + return Ok(n); + } let v = self .get(&keys::dict_iid_key(iid))? .ok_or_else(|| err_coded!(ErrorCode::Stg036, format!("ident id {iid}")))?; let n = String::from_utf8(v) .map_err(|_| err_coded!(ErrorCode::Stg036, format!("ident id {iid}: not UTF-8")))?; self.names.insert(iid, n.clone()); + if let Some(c) = self.shared { + shared_put(&c.names, iid, n.clone()); + } Ok(n) } @@ -692,4 +769,34 @@ mod tests { let err = dict.fact(&kf).unwrap_err(); assert_eq!(crate::error::MinigrafError::from(err).code(), "STG-036"); } + + /// A shared cache answers later readers without changing any result, and + /// clears itself at its size limit instead of growing. + #[test] + fn shared_cache_is_transparent_and_bounded() { + let mut backend = MemoryBackend::new(); + let cache = PageCache::new(256); + let facts = vec![ + fact(1, ":name", Value::Keyword(":k/a".into()), 1), + fact(2, ":name", Value::Keyword(":k/b".into()), 2), + ]; + let (root, enc) = checkpoint(&mut backend, &cache, 0, (1, 1), &facts); + let shared = SharedDictCache::default(); + for _ in 0..2 { + let mut dict = DictReader::new(root, &backend, &cache).with_shared(&shared); + let got: Vec = enc.index[0] + .iter() + .map(|(k, _)| dict.fact(&KeyFact::decode(Index::Eavt, k).unwrap()).unwrap()) + .collect(); + assert!(same_facts(got, facts.clone()), "same facts with a warm cache"); + } + assert!(shared.names.read().unwrap().len() >= 3, "idents cached"); + assert_eq!(shared.tx_ids.read().unwrap().len(), 2, "timestamps cached"); + + let map = std::sync::RwLock::new(HashMap::new()); + for i in 0..SHARED_CACHE_LIMIT as u64 + 10 { + shared_put(&map, i, i); + } + assert!(map.read().unwrap().len() <= SHARED_CACHE_LIMIT, "bounded"); + } } diff --git a/src/storage/reader.rs b/src/storage/reader.rs index f780514f6c..036dd823b8 100644 --- a/src/storage/reader.rs +++ b/src/storage/reader.rs @@ -6,7 +6,7 @@ use crate::graph::types::{EntityId, Fact}; use crate::storage::btree::{LeafCursor, MutexStorageBackend, prefix_scan}; use crate::storage::cache::PageCache; -use crate::storage::dict::DictReader; +use crate::storage::dict::{DictReader, SharedDictCache}; use crate::storage::keys::{self, Index, KeyFact}; use crate::storage::meta::MetaPage; use crate::storage::{CommittedReader, StorageBackend}; @@ -20,6 +20,7 @@ pub struct OnDiskReader { eavt_root: u64, aevt_root: u64, dict_root: u64, + shared: SharedDictCache, } impl OnDiskReader { @@ -30,11 +31,12 @@ impl OnDiskReader { eavt_root: meta.eavt_root, aevt_root: meta.aevt_root, dict_root: meta.dict_root, + shared: SharedDictCache::default(), } } fn dict(&self) -> DictReader<'_> { - DictReader::new(self.dict_root, &self.backend, &self.cache) + DictReader::new(self.dict_root, &self.backend, &self.cache).with_shared(&self.shared) } /// Facts of every `index` entry starting with `prefix`. @@ -74,6 +76,7 @@ impl CommittedReader for OnDiskReader { let Some(e) = dict.eid_of(entity)? else { return Ok(Vec::new()); }; + dict.seed_entity(e, *entity); self.scan( Index::Eavt, self.eavt_root, @@ -87,6 +90,8 @@ impl CommittedReader for OnDiskReader { let (Some(e), Some(a)) = (dict.eid_of(entity)?, dict.iid_of(attribute)?) else { return Ok(Vec::new()); }; + dict.seed_entity(e, *entity); + dict.seed_ident(a, attribute); let prefix = keys::entity_attribute_prefix(e, a); self.scan(Index::Eavt, self.eavt_root, &prefix, &mut dict) } @@ -96,6 +101,7 @@ impl CommittedReader for OnDiskReader { let Some(a) = dict.iid_of(attribute)? else { return Ok(Vec::new()); }; + dict.seed_ident(a, attribute); self.scan( Index::Aevt, self.aevt_root, From af2538eb2b184e104cfe08e13e87f7d505e72ca7 Mon Sep 17 00:00:00 2001 From: Aditya Mukhopadhyay Date: Tue, 6 Oct 2026 10:03:28 +0530 Subject: [PATCH 6/7] docs(v8): PR 5 changelog, roadmap, spec status and test coverage Co-Authored-By: Claude Opus 5.5 Claude-Session: https://claude.ai/code/session_015GgLEs8YozJjYhwPEYgTUn --- CHANGELOG.md | 1 + CLAUDE.md | 2 +- README.md | 2 +- ROADMAP.md | 8 ++++++-- docs/TEST_COVERAGE.md | 7 ++++--- .../plans/2026-10-05-v8-storage-format.md | 14 +++++++------- .../specs/2026-10-05-v8-storage-format-design.md | 1 + 7 files changed, 21 insertions(+), 14 deletions(-) diff --git a/CHANGELOG.md b/CHANGELOG.md index 45b114db5a..b01b6534c6 100644 --- a/CHANGELOG.md +++ b/CHANGELOG.md @@ -13,6 +13,7 @@ and this project adheres to [Semantic Versioning](https://semver.org/spec/v2.0.0 - **Crash-atomic checkpoints with verified pages** (v8 storage format, PR 2 of 5; #374, #388). Two alternating meta pages replace the 84-byte file header and are the only commit point: a checkpoint writes only pages the last commit does not use, syncs, then writes the other meta page and syncs. A crash or torn write at any point leaves the previous checkpoint intact, so opening never rebuilds an index, and the whole-file index checksum is gone. Every other page carries a 24-byte header (type, CRC32, its own page id, the checkpoint generation that wrote it), checked on every read: a torn, corrupted, misplaced or stale page now fails with `STG-029`, `STG-030` or `STG-031` instead of being read. If the newest meta page is damaged after its WAL was already deleted, open fails with `STG-033` rather than silently going back to the previous checkpoint. New codes `STG-029`–`STG-035`. The WAL header gains a base generation (WAL version 2); a v2.x WAL beside a migrated file is still replayed. Pages freed by a checkpoint are reused by later ones. Files written by a v3.0.0 development build before this change fail with `STG-032`. - **Covering indexes with dictionary-coded keys** (v8 storage format, PR 3 of 5; #433). Every index entry now holds the whole fact as a byte-comparable key, so a query reads only index pages, never a separate fact page. Entities and idents (attribute names and keyword values) get sequential internal ids from a dictionary stored in the file, and strings longer than 64 bytes are stored once in value pages and deduplicated. Fact pages are gone. A file with 100,000 facts (10 attributes per entity) takes 88 bytes per fact, down from 314. Facts from committed data now come back in internal-id order (entity, then attribute) rather than insertion or UUID order; query results are sets, and code that relied on an order must sort. New codes `STG-036` (dictionary entry missing) and `STG-037` (one transaction with two timestamps: a checkpoint or v7 upgrade refuses to change a stored timestamp). Files written by a v3.0.0 development build before this change fail with `STG-032`. - **Checkpoints cost what changed, not the size of the database** (v8 storage format, PR 4 of 5; #434). A checkpoint now inserts copy-on-write: it rewrites only the index leaves that receive new facts and their paths to the root, and reuses pages freed by earlier checkpoints through a free list it reads and extends only as far as it needs. A checkpoint after one new fact takes 3.1 ms on a 10,000-fact file and 3.3 ms on a 100,000-fact file (it took 15.5 ms and 43 ms before, and grew with the file). One new fact at 100,000 facts writes 16 pages. The `checkpoint()` and `wal_checkpoint_threshold` docs now describe this cost. +- **A damaged page is reported, not worked around** (v8 storage format, PR 5 of 5). A query whose indexed lookup reaches a damaged page now fails with that page's `STG-029`/`STG-030`/`STG-031`. Before, the query fell back to a full scan, which could hide the damage. Tests damage an index leaf, an internal node, a dictionary leaf, a value page and a free-list page in turn. Every read or checkpoint that reaches the page fails, and the file still opens at its last checkpoint. Measured at 1.15M facts in #433's shape: 142 bytes per fact, history included. A checkpoint after one new fact takes 6.1 ms at 1M facts. Concurrent point queries are 19–31 % faster than before this change: reads reuse the entity and attribute the caller passed, and share cached ident and timestamp lookups. - **Size limits for file-backed databases:** a string value may be up to 4,068 bytes, whatever the rest of the fact, and an attribute name or keyword value up to 1,024 bytes. Both are checked when the transaction is written and fail with `WAL-003`, whose message now names the value. This replaces the 4,080-byte limit on a whole serialised fact (4,052 in earlier v3.0.0 development builds). In-memory databases have no limit. - **Formats v1–v6 are no longer readable.** Opening one fails with the new `STG-028`; open it once with Minigraf v2.x to upgrade it to v7 first. `STG-003` and `STG-004` are deprecated (no longer emitted, still registered, never reused). `STG-005` and `STG-006` message text changed. diff --git a/CLAUDE.md b/CLAUDE.md index 1482563102..522aa67a6d 100644 --- a/CLAUDE.md +++ b/CLAUDE.md @@ -193,7 +193,7 @@ Auto-migrates v7 → v8 on open (spec §9, with a backup meta page). v1–v6 are ## Test Coverage -**1230 tests** (1222 passing, 8 ignored; unit + integration + doc). +**1236 tests** (1227 passing, 9 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/README.md b/README.md index fb5d029946..d22fb3cb5f 100644 --- a/README.md +++ b/README.md @@ -105,7 +105,7 @@ let r2 = pq.execute(&[("tx", BindValue::TxCount(2)), ("entity", BindValue::Entit ```bash cargo run # interactive Datalog REPL -cargo test # run 1230 tests +cargo test # run 1236 tests cargo run < demos/demo_recursive.txt # recursive rules demo ``` diff --git a/ROADMAP.md b/ROADMAP.md index 94e34e22ff..62f435397d 100644 --- a/ROADMAP.md +++ b/ROADMAP.md @@ -41,8 +41,12 @@ This was the GitHub milestone named “2.0” before v2.0.0 used that version nu Scope — format and storage integrity: - v8 index keys with value bytes and v7→v8 migration (#371, #287; done on `v3`) -- Per-page CRC32 checksums on fact pages and B+tree pages (#388) -- Crash-atomic `save()`, with checkpoints proportional to the change (#374) +- v8 storage format, done on `v3` in five PRs (#374, #434, #388, #433): + - per-page CRC32, page id and generation on every page (#388); + - two alternating meta pages; crash-atomic, copy-on-write checkpoints whose cost follows the change (#374, #434); + - covering byte-comparable keys with a dictionary and deduplicated long values, at about 142 bytes per fact (#433). + + The format is frozen for the golden-file corpus (#391). - Index `verify` and public `rebuild_indexes()` (#373) - Net-assert on v8 keys before resolving facts, for O(live) point queries (#379) - `btree_page` fuzz target that reaches node decoding (#375) diff --git a/docs/TEST_COVERAGE.md b/docs/TEST_COVERAGE.md index df9b7bf0cc..7271eaac11 100644 --- a/docs/TEST_COVERAGE.md +++ b/docs/TEST_COVERAGE.md @@ -4,9 +4,9 @@ **Verified**: 2026-10-05 with `cargo test --quiet` -**Result**: 1,222 passing tests and 8 ignored tests (1,230 total) +**Result**: 1,227 passing tests and 9 ignored tests (1,236 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 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). v8 page-format tests (PR 2, #374, #388) check the 24-byte page header (a flipped bit, a wrong page id and a future generation each give their own STG code, legacy page types fail before the CRC, and a failed page is never cached), meta-page encoding, the free-list chain, WAL v2's base generation, and every row of the meta-selection table: both slots valid, a torn newest slot with the WAL's base generation (opens at the older one), a WAL newer than the valid meta, pages of the next generation on the free list or past `page_count` with no WAL (all STG-033, with the file unmodified), an unknown feature bit (STG-034), and a pre-release v8 single header (STG-032). Fault-injection tests crash `save()` at every page write (cleanly and with torn pages, including the meta write) and every sync, and crash a v7 migration at every write; each reopen finds exactly the old or the new checkpoint, and every reachable page plus the free list covers the file exactly. Twenty-five consecutive saves never write a page the previous meta references. Covering-key tests (PR 3, #433) check that byte order equals logical order for every key component and value type on random tuples (negative, zero and large integers, NaN and ±0.0, strings with 0x00, 64- and 65-byte strings, FOREVER, newest-transaction-first) and that every component round-trips; that prefix-compressed leaves and shortest-separator internal nodes round-trip, agree with a linear scan, keep `max(left) < s ≤ min(right)`, and reject an overflow; that the byte-key B+tree's builds, incremental rebuilds, cursor and `seek` match their expected sets; that dictionary ids are assigned once, never reused, shared between a keyword attribute and value, and deterministic; that a re-asserted or retracted long value writes no new value page and a forced hash collision still finds the right value; that one transaction with two timestamps is STG-037 and a missing dictionary entry STG-036; that committed reads by entity, entity and attribute, attribute, and in full equal an in-memory model across eight checkpoints and a reopen; that short-valued reads touch no value page; that a v7 file with every value type, long strings, refs and retractions migrates to exactly the same facts; that a pre-covering-key v8 file is STG-032; and that string values over 4,068 bytes and attributes or keywords over 1,024 bytes are WAL-003. A WAL test checks that reopening next to a fully checkpointed WAL does not reuse transaction numbers (#447). Copy-on-write checkpoint tests (PR 4, #434) check that lazy free-list pops and pushes conserve every page across page boundaries, partial head pages and chain exhaustion, never hand out a page freed in the same generation, and share unread chain pages unchanged; that a copy-on-write insert equals a sorted merge for random batches (including keys below the first and above the last, many into one leaf, root growth to depth 3, and 1 KB separators that split internal nodes), leaves the old tree readable and unchanged, frees exactly the replaced nodes, writes only new pages, writes exactly one leaf and two internal nodes for one entry in a depth-3 tree, and does not fragment leaves under single inserts; that a checkpoint after 1 or 100 right-edge facts writes at most the tree-depth difference more pages at 100,000 facts than at 10,000, and at most one path per new entry per tree for random keys; and that four reader threads querying throughout 40 checkpoints never fail and never see the fact count go backwards. Merged from the v2.x line: storage and `edge_cases_test.rs` tests check that more than 65,535 uncheckpointed facts each resolve to their own fact through entity lookups and attribute scans, in memory and file-backed (#445). +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). v8 page-format tests (PR 2, #374, #388) check the 24-byte page header (a flipped bit, a wrong page id and a future generation each give their own STG code, legacy page types fail before the CRC, and a failed page is never cached), meta-page encoding, the free-list chain, WAL v2's base generation, and every row of the meta-selection table: both slots valid, a torn newest slot with the WAL's base generation (opens at the older one), a WAL newer than the valid meta, pages of the next generation on the free list or past `page_count` with no WAL (all STG-033, with the file unmodified), an unknown feature bit (STG-034), and a pre-release v8 single header (STG-032). Fault-injection tests crash `save()` at every page write (cleanly and with torn pages, including the meta write) and every sync, and crash a v7 migration at every write; each reopen finds exactly the old or the new checkpoint, and every reachable page plus the free list covers the file exactly. Twenty-five consecutive saves never write a page the previous meta references. Covering-key tests (PR 3, #433) check that byte order equals logical order for every key component and value type on random tuples (negative, zero and large integers, NaN and ±0.0, strings with 0x00, 64- and 65-byte strings, FOREVER, newest-transaction-first) and that every component round-trips; that prefix-compressed leaves and shortest-separator internal nodes round-trip, agree with a linear scan, keep `max(left) < s ≤ min(right)`, and reject an overflow; that the byte-key B+tree's builds, incremental rebuilds, cursor and `seek` match their expected sets; that dictionary ids are assigned once, never reused, shared between a keyword attribute and value, and deterministic; that a re-asserted or retracted long value writes no new value page and a forced hash collision still finds the right value; that one transaction with two timestamps is STG-037 and a missing dictionary entry STG-036; that committed reads by entity, entity and attribute, attribute, and in full equal an in-memory model across eight checkpoints and a reopen; that short-valued reads touch no value page; that a v7 file with every value type, long strings, refs and retractions migrates to exactly the same facts; that a pre-covering-key v8 file is STG-032; and that string values over 4,068 bytes and attributes or keywords over 1,024 bytes are WAL-003. A WAL test checks that reopening next to a fully checkpointed WAL does not reuse transaction numbers (#447). Copy-on-write checkpoint tests (PR 4, #434) check that lazy free-list pops and pushes conserve every page across page boundaries, partial head pages and chain exhaustion, never hand out a page freed in the same generation, and share unread chain pages unchanged; that a copy-on-write insert equals a sorted merge for random batches (including keys below the first and above the last, many into one leaf, root growth to depth 3, and 1 KB separators that split internal nodes), leaves the old tree readable and unchanged, frees exactly the replaced nodes, writes only new pages, writes exactly one leaf and two internal nodes for one entry in a depth-3 tree, and does not fragment leaves under single inserts; that a checkpoint after 1 or 100 right-edge facts writes at most the tree-depth difference more pages at 100,000 facts than at 10,000, and at most one path per new entry per tree for random keys; and that four reader threads querying throughout 40 checkpoints never fail and never see the fact count go backwards. Hardening tests (PR 5) damage an index leaf, an internal node, a dictionary leaf, a value page and a free-list page in turn. Every committed read or checkpoint that reaches the damaged page fails with STG-029, never with wrong or fewer rows. A query through `Minigraf` on a file with damaged leaves fails with STG-029, and the file still opens at its last checkpoint. A size test measures at most 200 bytes per fact (142 measured) on 144k facts in #433's shape; its 1.15M-fact variant is ignored locally and runs in the nightly smoke workflow. A shared dictionary-cache test checks that cached ident and timestamp lookups return the same facts and that the cache stays bounded. Merged from the v2.x line: storage and `edge_cases_test.rs` tests check that more than 65,535 uncheckpointed facts each resolve to their own fact through entity lookups and attribute scans, in memory and file-backed (#445). ### Covered Areas @@ -19,11 +19,12 @@ This covers the unreleased file-format-v8 work (#287, #371): the index-key value ### Ignored Tests -The eight ignored tests are intentionally excluded from a normal local run: +The nine ignored tests are intentionally excluded from a normal local run: - Six rustdoc examples that reference internal types and cannot compile as standalone examples. - One high-contention concurrency stress test intended for scheduled runs. - One long-haul smoke test intended for scheduled runs. +- One size test at 1.15M facts (`size_per_fact_in_433_shape_1m`), run by the nightly smoke workflow. ### Reproducing diff --git a/docs/superpowers/plans/2026-10-05-v8-storage-format.md b/docs/superpowers/plans/2026-10-05-v8-storage-format.md index 20fc4f8bf4..3bc0cea71e 100644 --- a/docs/superpowers/plans/2026-10-05-v8-storage-format.md +++ b/docs/superpowers/plans/2026-10-05-v8-storage-format.md @@ -689,8 +689,8 @@ shipped. ### Task 1: Error surfacing -- [ ] `selective_fact_fetch` propagates errors; `executor.rs` derived reads use `?`. -- [ ] Corruption tests: damage an index leaf, an internal node, a DICT leaf, a value page +- [x] `selective_fact_fetch` propagates errors; `executor.rs` derived reads use `?`. +- [x] Corruption tests: damage an index leaf, an internal node, a DICT leaf, a value page and a free-list page in turn (bytes flipped, CRC left stale). Queries through `Minigraf` on a file, or a checkpoint, return the STG code (STG-029). They never return rows from the damaged page or silently fewer rows, and a failed checkpoint @@ -698,23 +698,23 @@ shipped. ### Task 2: Size -- [ ] `size_per_fact_in_433_shape` (100k, always) and `size_per_fact_1m` (ignored), both +- [x] `size_per_fact_in_433_shape` (100k, always) and `size_per_fact_1m` (ignored), both at most 200 B per fact. ### Task 3: Benchmarks -- [ ] `checkpoint/after_1_fact/1m` and `checkpoint/after_100k_facts/{10k,100k}`. +- [x] `checkpoint/after_1_fact/1m` and `checkpoint/after_100k_facts/{10k,100k}`. ### Task 4: Read path -- [ ] Seed the `DictReader` memo per call and share an ident and timestamp cache in +- [x] Seed the `DictReader` memo per call and share an ident and timestamp cache in `OnDiskReader`, bounded in entries. Re-run `concurrent_btree_scan` and `btree_lookup/entity_point` against PR 4. ### Task 5: Docs and PR -- [ ] `.wiki/Architecture.md` (format v8 and the read and checkpoint paths), ROADMAP, +- [x] `.wiki/Architecture.md` (format v8 and the read and checkpoint paths), ROADMAP, CHANGELOG, CLAUDE.md, TEST_COVERAGE, and a status note at the top of the spec. Commit and push the wiki separately. -- [ ] `cargo fmt`, clippy, `cargo test`; open the PR into `v3` with `Refs #374 #434 #388 #433`. +- [x] `cargo fmt`, clippy, `cargo test`; open the PR into `v3` with `Refs #374 #434 #388 #433`. Own CI until green. Ask before merging. 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 index 9e38b24615..060374267b 100644 --- a/docs/superpowers/specs/2026-10-05-v8-storage-format-design.md +++ b/docs/superpowers/specs/2026-10-05-v8-storage-format-design.md @@ -4,6 +4,7 @@ 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 +**Status:** implemented on `v3` in delivery PRs 1–5 (#442, #444, #449, #451 and PR 5); §5.1, §5.2 and §6.1–§6.3 carry the amendments made in PR 3. Measured: 142 B per fact at 1.15M facts in #433's shape; a checkpoint after one new fact takes 3.0 ms at 10k, 3.3 ms at 100k and 6.1 ms at 1M facts. **Builds on:** #315 / `2026-09-26-incremental-checkpoint-design.md` (balanced leaf split, routing) ## 1. Problem From 15417fa92ef66fa91f9108559a3b41351918af3a Mon Sep 17 00:00:00 2001 From: Aditya Mukhopadhyay Date: Tue, 6 Oct 2026 10:03:41 +0530 Subject: [PATCH 7/7] style: cargo fmt Co-Authored-By: Claude Opus 5.5 Claude-Session: https://claude.ai/code/session_015GgLEs8YozJjYhwPEYgTUn --- src/storage/dict.rs | 10 ++++++++-- 1 file changed, 8 insertions(+), 2 deletions(-) diff --git a/src/storage/dict.rs b/src/storage/dict.rs index e59435c685..594443fd77 100644 --- a/src/storage/dict.rs +++ b/src/storage/dict.rs @@ -786,9 +786,15 @@ mod tests { let mut dict = DictReader::new(root, &backend, &cache).with_shared(&shared); let got: Vec = enc.index[0] .iter() - .map(|(k, _)| dict.fact(&KeyFact::decode(Index::Eavt, k).unwrap()).unwrap()) + .map(|(k, _)| { + dict.fact(&KeyFact::decode(Index::Eavt, k).unwrap()) + .unwrap() + }) .collect(); - assert!(same_facts(got, facts.clone()), "same facts with a warm cache"); + assert!( + same_facts(got, facts.clone()), + "same facts with a warm cache" + ); } assert!(shared.names.read().unwrap().len() >= 3, "idents cached"); assert_eq!(shared.tx_ids.read().unwrap().len(), 2, "timestamps cached");