8000 feat(storage): v8 covering keys, DICT and value pages (PR 3 of 5) by adityamukho · Pull Request #449 · project-minigraf/minigraf · GitHub
[go: up one dir, main page]
Skip to content

feat(storage): v8 covering keys, DICT and value pages (PR 3 of 5) - #449

Merged
adityamukho merged 9 commits into
v3from
feat/v8-pr3-covering-keys
Oct 6, 2026
Merged

feat(storage): v8 covering keys, DICT and value pages (PR 3 of 5)#449
adityamukho merged 9 commits into
v3from
feat/v8-pr3-covering-keys

Conversation

@adityamukho
@adityamukho adityamukho commented Oct 6, 2026
Copy link
Copy Markdown
Collaborator

Summary

PR 3 of 5 of the v8 storage format (spec docs/superpowers/specs/2026-10-05-v8-storage-format-design.md, plan section "PR 3"). The four indexes become covering indexes: every entry is a whole fact encoded as a byte-comparable key. Entities and idents (attribute names and keyword values) become sequential ids held in a new DICT tree. Strings longer than 64 bytes are stored once in value pages. Fact pages, FactRef and both committed-reader traits are gone. The on-disk format freezes after this PR. save() is still a full rewrite (O(N)); PR 4 makes it O(change).

Size: 100,000 facts (10 attributes per entity) take 88 bytes per fact, down from 314 on PR 2's format.

What changed

  • keys.rs: byte-comparable keys (spec §6).
    • Integers use the FoundationDB tuple encoding. Value tags keep the cross-type order. Short strings are escaped; long strings are stored as a 32-byte prefix, a 00 01 marker, hash64 (FNV-1a) and a value ref. vt = FOREVER is the single byte 0xFF.
    • tx↓ is the complemented tx_count encoding (see deviations).
    • Key layouts: EAVT e a v tx↓ vf vt op, AEVT, AVET, and VAET (refs only).
  • node.rs: node codecs (spec §4.3).
    • Leaves are prefix-compressed with a restart point every 16 entries.
    • Internal nodes hold shortest separators with a slot array.
    • Both reject an overflow with INT-049.
  • btree.rs (replaces btree_v6.rs): the B+tree over (key, value) byte entries.
    • Covers the bulk build, the incremental rebuild (untouched leaves copied and restamped; touched ones split by balanced bytes at cumulative-size cuts), LeafCursor with seek, prefix_scan and point get.
  • value_pages.rs: append-only 0x51 pages. Each checkpoint starts a fresh page.
  • dict.rs:
    • DictReader translates entries back into facts, with lookups memoised per read.
    • Encoder assigns eids and iids at checkpoint, in pending (WAL) order. It records one tx_id per tx_count and deduplicates long values against committed and new ones.
  • reader.rs: OnDiskReader implements the single CommittedReader trait. It provides all facts, by entity, by entity and attribute, and by attribute: the only committed read paths the query layer uses.
  • persistent_facts.rs: save() and the v7 migration share one encode pipeline and rebuild all five trees. The meta records dict_root, next_eid and next_iid.
  • FactStorage:
    • Pending indexes map to usize positions; only EAVT and AEVT remain.
    • The matcher's index lookup was dead code: both of its paths scanned every fact. It is removed, along with the optimizer's unused parameter.
  • packed_pages.rs keeps only the v7 reader (plus a test-only v7 writer for fixtures). Page type 0x41 is retired.
  • Pre-release v8 files from PR 2 builds have valid metas but no DICT tree. They are now refused with STG-032 instead of being misread.

Deviations from the spec (spec amended in this PR)

  1. Ids, value refs and keys are assigned at checkpoint, not at transact (§5.1). A long value's ref exists only once its value page is written, at checkpoint. Ids are never persisted before the commit that writes their DICT entries, so assigning them then is deterministic and crash-safe, and the transact path does no dictionary I/O.
  2. tx↓ is the byte complement of the tx_count encoding (§6.1). The encoding is prefix-free, so the complement reverses order exactly. It costs 2–4 bytes instead of 9.
  3. DICT 0x06 key is hash64 ‖ value ref with an empty value, so several long values can share a hash. DICT 0x03 holds raw ident bytes.

Behaviour changes (CHANGELOG)

  • Size limits. String values are capped at 4,068 bytes, and attributes and keyword values at 1,024 bytes. Both are checked at WAL write (WAL-003, new message text). This replaces the 4,052-byte serialised-fact limit.
  • New error codes.
    • STG-036: a dictionary entry is missing.
    • STG-037: one tx_count with two tx_ids. A checkpoint or v7 upgrade refuses to alter a stored timestamp.
  • Result order. Committed facts come back in id order. The full suite passes unchanged. In the bindings, only the Python and Java tests checkpoint, and neither compares ordered lists of committed results.

Found along the way

The STG-037 check exposed #447, a v2.x data-integrity bug: reopening next to an already-checkpointed WAL rewound the transaction counter, so later transactions reused tx_counts. This PR carries the same one-line fix and test as the v2.x fix (#448), so the next main → v3 merge is clean. #445 (pending-slot overflow) was found while planning; its fix is merged into main (#446). On v3 the code it touched is removed here.

Tests

  • New unit tests for each module:
    • Keys: byte order equals logical order on random tuples of every type; every component round-trips.
    • Nodes: round trip, lookup against a linear scan, separator bounds, corruption.
    • B+tree: builds, incremental equivalence, no fragmentation, cursor and seek, page-read counting.
    • Value pages: round trip and the 4,068-byte limit.
    • Dictionary: determinism, shared iids, dedup, forced hash collision, STG-036/037.
  • Persistent storage:
    • Committed reads equal an in-memory model across 8 checkpoints and a reopen.
    • Short-valued reads touch no value page.
    • Long values are stored once across checkpoints.
    • A v7 file with mixed values migrates exactly.
    • A pre-covering-key file is STG-032.
    • The PR 2 crash-at-every-point suites for save and migration pass unchanged, including torn writes and the space-accounting invariant, which now follows value refs through DICT.
  • WAL: attribute and keyword limits are WAL-003.
  • Full suite: 1,215 passing, 8 ignored. The count is lower than before because the B+tree, packed-page and index tests were rewritten for byte keys, and the fact-page tests were removed with fact pages. cargo clippy --all-features -- -D warnings is clean.

Benchmarks (PR 2 → PR 3, same machine, nothing else running)

benchmark PR 2 PR 3
checkpoint/after_1_fact/100k 60.6 ms 43.4 ms −28 %
checkpoint/after_1_fact/10k 17.9 ms 15.5 ms −14 %
btree_lookup/entity_point/{1k,10k,100k} 6.4 / 7.1 / 6.6 µs 6.1 / 6.1 / 6.5 µs −1 to −14 %
open/checkpointed/* ~23 µs ~23 µs flat
concurrent_btree_scan/100k_{2,4}t 24.3 / 27.9 µs 31.9 / 38.1 µs +31 / +37 %
  • Checkpoints. The first run had the 100k checkpoint at 516 ms: untouched leaves were fully decoded twice per save. Rebuilds now read a copied leaf's last key from its final restart point, and collect_leaf_pages validates structure without copying keys.
  • Concurrent point scans are slower. Each lookup now also resolves the entity's eid and translates the ids through DICT. Single-threaded point lookups are not slower. The remaining work belongs to PR 5's performance pass.
  • btree_lookup/attribute_scan/100k (an in-memory database) reads 106 ms on PR 2 and 246 ms on PR 3, but the two do not do the same work. PR 2's branch still has Queries return wrong results with more than 65,535 uncheckpointed facts #445: past 65,535 pending facts, its attribute scan resolved most facts to one slot and returned far fewer rows. The flat profiles match, and at 10k (below the bug) the two are equal (23.3 vs 23.0 ms).

Docs

Spec amendments (§5.1, §5.2 DICT table, §6.1, §6.2, §6.3, §12), the PR 3 plan, CHANGELOG, CLAUDE.md (module list, File Format, test count), ERROR_REFERENCE (STG-036, STG-037, WAL-003, STG-032) and TEST_COVERAGE.

Refs #433 #374 #434 #388

🤖 Generated with Claude Code

https://claude.ai/code/session_015GgLEs8YozJjYhwPEYgTUn

adityamukho and others added 9 commits October 6, 2026 07:55
@adityamukho @claude
docs(v8): detailed plan for PR 3, covering keys and dictionaries
657c289 
Records two deviations from the spec, to be amended in the same PR: ids,
value refs and keys are assigned at checkpoint rather than at transact, and
tx↓ is the complemented tx_count encoding rather than u64::MAX − tx_count.

Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com>
Claude-Session: https://claude.ai/code/session_015GgLEs8YozJjYhwPEYgTUn
@adityamukho @claude
feat(storage): byte-comparable key codec for v8 covering indexes (#433)
7c150c2 
FoundationDB-style integers, value tags in cross-type order, escaped short
strings, long strings as prefix + hash + value ref, the FOREVER byte, and
tx↓ as the complemented tx_count encoding. EAVT/AEVT/AVET/VAET key builders
and decoders, and DICT keys for tags 0x01-0x06.

Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com>
Claude-Session: https://claude.ai/code/session_015GgLEs8YozJjYhwPEYgTUn
@adityamukho @claude
feat(storage): prefix-compressed leaf and internal node codecs (#433)
38b2aee 
Leaves store prefix-compressed entries with a restart point every 16
entries; internal nodes store shortest separators with a slot array for
binary search. Both reject a page overflow with INT-049.

Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com>
Claude-Session: https://claude.ai/code/session_015GgLEs8YozJjYhwPEYgTUn
@adityamukho @claude
feat(storage): B+tree on byte keys with shortest separators (#433)
f78dc7c 
build_btree, rebuild_btree_incremental, collect_leaf_pages, LeafCursor
(with seek), prefix_scan and point get over (key, value) byte entries in
the new node format. Leaves split by balanced bytes at cumulative-size
boundaries; untouched leaves are copied and restamped. btree_v6.rs stays
until its callers move over.

Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com>
Claude-Session: https://claude.ai/code/session_015GgLEs8YozJjYhwPEYgTUn
@adityamukho @claude
feat(storage): append-only value pages for long strings (#433)
84443fe 
Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com>
Claude-Session: https://claude.ai/code/session_015GgLEs8YozJjYhwPEYgTUn
@adityamukho @claude
feat(storage): DICT reader and checkpoint-time fact encoder (#433)
78c708e 
DictReader translates index entries back into facts through memoised DICT
lookups. Encoder assigns eids and iids in pending order, records one
timestamp per transaction (STG-037 on a conflict), deduplicates long values
against committed and new ones, and builds sorted entries for all five
trees. A missing DICT entry is STG-036.

Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com>
Claude-Session: https://claude.ai/code/session_015GgLEs8YozJjYhwPEYgTUn
@adityamukho @claude
feat(storage): covering indexes with DICT and value pages; drop fact …
20edc85 
…pages (#433)

save() and the v7 migration now encode facts into byte-comparable keys at
checkpoint time (Encoder), write new long strings to value pages, and
rebuild all five trees (EAVT, AEVT, AVET, VAET, DICT). The meta records the
DICT root and the next eid/iid. Fact pages (0x41, now retired), FactRef,
CommittedFactReader/CommittedIndexReader and btree_v6.rs are removed.

Committed reads go through one CommittedReader (all facts, by entity, by
entity and attribute, by attribute) that decodes index entries and
translates ids through DICT; nothing but index leaves, DICT pages and long
values is read. Pending indexes map to usize positions. The matcher's and
optimizer's unused index plumbing is removed.

WAL-003 now limits string values to 4068 bytes (one value page) and
attributes/keywords to 1024 bytes, instead of the serialised fact size.

Also carries the #447 fix (the tx counter never rewinds on WAL replay),
which the new one-timestamp-per-transaction check (STG-037) exposed.

Refs #433 #374 #434 #388 #447

Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com>
Claude-Session: https://claude.ai/code/session_015GgLEs8YozJjYhwPEYgTUn
@adityamukho @claude
test(storage): covering reads, value-page dedup and mixed v7 migration (
bd07dfe 
#433)

Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com>
Claude-Session: https://claude.ai/code/session_015GgLEs8YozJjYhwPEYgTUn
@adityamukho @claude
perf(storage): copy untouched leaves without decoding them twice (#433)
5a9870f 
collect_leaf_pages validates a leaf's structure without copying keys, and
the incremental rebuild reads a copied leaf's last key from its final
restart point. A checkpoint after one fact at 100k facts drops from 516 ms
to 43 ms (PR 2: 61 ms).

Also: pre-covering-key v8 files are refused with STG-032, spec amendments,
CHANGELOG, CLAUDE.md, ERROR_REFERENCE and TEST_COVERAGE for PR 3.

Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com>
Claude-Session: https://claude.ai/code/session_015GgLEs8YozJjYhwPEYgTUn
@adityamukho
adityamukho merged commit 3afa518 into v3 Oct 6, 2026
17 checks passed
@adityamukho
adityamukho deleted the feat/v8-pr3-covering-keys branch October 6, 2026 03:45
@codecov
codecov Bot commented Oct 6, 2026
Copy link
Copy Markdown

Codecov Report

❌ Patch coverage is 95.38816% with 60 lines in your changes missing coverage. Please review.

Files with missing lines Patch % Lines
src/storage/btree.rs 91.26% 22 Missing ⚠️
src/storage/keys.rs 95.91% 12 Missing ⚠️
src/storage/reader.rs 86.27% 7 Missing ⚠️
src/storage/node.rs 97.76% 6 Missing ⚠️
src/storage/persistent_facts.rs 87.50% 6 Missing ⚠️
src/storage/dict.rs 97.64% 5 Missing ⚠️
src/storage/value_pages.rs 97.18% 2 Missing ⚠️

📢 Thoughts on this report? Let us know!

This was referenced Oct 6, 2026
Merged
Closed
Closed
Closed
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Reviewers

No reviews

Assignees

No one assigned

Labels

None yet

Projects

None yet

Milestone

No milestone

Development

Successfully merging this pull request may close these issues.

1 participant

@adityamukho
0