8000 feat(storage): v8 copy-on-write checkpoints (PR 4 of 5) by adityamukho · Pull Request #451 · project-minigraf/minigraf · GitHub
[go: up one dir, main page]
Skip to content

feat(storage): v8 copy-on-write checkpoints (PR 4 of 5) - #451

Merged
adityamukho merged 6 commits into
v3from
feat/v8-pr4-cow
Oct 6, 2026
Merged

feat(storage): v8 copy-on-write checkpoints (PR 4 of 5)#451
adityamukho merged 6 commits into
v3from
feat/v8-pr4-cow

Conversation

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

Summary

PR 4 of 5 of the v8 storage format: copy-on-write checkpoints (spec §4.4, §8; plan section "PR 4"). A checkpoint now writes only:

  • new value pages;
  • the touched leaves and their paths to the root in each of the five trees;
  • the free-list pages it pushes;
  • one meta page.

Its cost follows the change, not the graph (#434 acceptance 1, 2, 4). The file format is unchanged.

checkpoint/after_1_fact PR 3 PR 4
10k facts 15.5 ms 3.07 ms
100k facts 43.4 ms 3.27 ms

Pages written by a checkpoint (from the cost-bound test):

change 10k facts 100k facts
1 new fact (right edge) 11 16
100 new facts (right edge) 15 21
100 new facts (random keys) — 196

What changed

  • Lazy free list (PageAllocator::from_chain, finish_free_list).
    • alloc reads the active meta's free-list pages one at a time, only when it needs another id. That is why its signature now takes the backend and the cache.
    • At the end, the replaced pages, the chain pages read and their unused ids are pushed as new head pages in front of the unread tail, which is shared unchanged.
    • The head pages are allocated by the same allocator; a small fixed-point loop sizes them.
    • Nothing freed in a generation is handed out in it (§8.1). Cost: O(pages allocated + pages freed).
  • btree::cow_insert.
    • Routes sorted entries down the tree, merges each touched leaf and repacks it with the balanced split from perf: checkpoint() is O(graph size) and flat in dirty bytes — it rebuilds all four covering indexes every call #315.
    • Rewrites each touched internal node, with each touched child replaced by its pieces. Separators between new pieces are the shortest separators; existing separators stay valid.
    • Splits an internal node that outgrows its page, balanced by bytes: the separator at the cut moves up, and a split with very large separators retries with one more part.
    • Grows the root when it splits. Untouched subtrees are shared by page id, and every replaced page goes to freed.
  • save() uses both and no longer snapshots the old trees.
  • Concurrency (§8.1): a query holds the FactStorage read guard for its whole scan, and installing the new reader needs the write lock. So no query spans two checkpoints, and the page cache stays write-through.
  • Browser (§12): BrowserBufferBackend already tracks dirty pages per write, so its flush is now O(change) too. No code change.

Tests

  • Free list:
    • Pops and pushes across page boundaries, partial head pages and chain exhaustion conserve every page; nothing freed is handed out in the same generation; unread chain pages are shared.
    • A wrong count or a looping chain is STG-035.
  • cow_insert, against a sorted merge, for random batches, keys below the first and above the last, many into one leaf, root growth to depth 3, and 1 KB separators:
    • the old tree streams unchanged;
    • freed is exactly the replaced nodes;
    • only new pages are written;
    • one entry in a depth-3 tree writes exactly 3 pages;
    • single inserts do not fragment leaves.
  • Cost bound: at 100k facts a checkpoint writes at most the tree-depth difference more pages than at 10k, for 1 and 100 right-edge facts; random keys write at most one path per new entry per tree.
  • Concurrency (concurrency_test): four readers query throughout 40 checkpoints. No read fails, and the fact count never goes backwards.
  • Unchanged and passing: the crash-at-every-point suites (with torn writes), the space-accounting invariant after every save, and "no save writes a page the previous meta references".
  • Full suite: 1,222 passing, 8 ignored. cargo clippy --all-features -- -D warnings is clean.

Docs

CHANGELOG, the Minigraf::checkpoint and wal_checkpoint_threshold rustdoc (no longer "proportional to the total index size"), CLAUDE.md, TEST_COVERAGE, and the plan's PR 4 section. The 1M-fact benchmarks and after_100k_facts move to PR 5.

Refs #434 #374

🤖 Generated with Claude Code

https://claude.ai/code/session_015GgLEs8YozJjYhwPEYgTUn

adityamukho and others added 6 commits October 6, 2026 09:21
@adityamukho @claude
docs(v8): detailed plan for PR 4, copy-on-write checkpoints
f273d8c 
Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com>
Claude-Session: https://claude.ai/code/session_015GgLEs8YozJjYhwPEYgTUn
@adityamukho @claude
feat(storage): lazy free-list pop/push and copy-on-write B+tree insert (
59732f2 
#434)

PageAllocator reads the active meta's free-list chain one page at a time as
it needs ids, and finish_free_list pushes freed pages, read chain pages and
unused ids as new head pages in front of the unread tail. cow_insert
rewrites only the touched leaves and their paths to the root, splitting
leaves and internal nodes by balanced bytes and growing the root.

Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com>
Claude-Session: https://claude.ai/code/session_015GgLEs8YozJjYhwPEYgTUn
@adityamukho @claude
feat(storage): copy-on-write checkpoints (#434)
933000e 
save() inserts into each of the five trees copy-on-write and pushes the
replaced pages and the free-list pages it read onto the free list, read
lazily from the active meta. A checkpoint no longer snapshots or copies the
old trees. rebuild_btree_incremental is removed; collect_leaf_pages stays
for the reachability test helpers.

Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com>
Claude-Session: https://claude.ai/code/session_015GgLEs8YozJjYhwPEYgTUn
@adityamukho
Merge remote-tracking branch 'origin/v3' into feat/v8-pr4-cow
fa44c14
@adityamukho @claude
test(storage): checkpoint cost bound and queries during COW checkpoin…
0d9327d 
…ts (#434)

Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com>
Claude-Session: https://claude.ai/code/session_015GgLEs8YozJjYhwPEYgTUn
@adityamukho @claude
docs(v8): PR 4 changelog, checkpoint rustdoc, CLAUDE.md and test cove…
10fa6ac 
…rage

Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com>
Claude-Session: https://claude.ai/code/session_015GgLEs8YozJjYhwPEYgTUn
@codecov
codecov Bot commented Oct 6, 2026
Copy link
Copy Markdown

Codecov Report

❌ Patch coverage is 95.47739% with 9 lines in your changes missing coverage. Please review.

Files with missing lines Patch % Lines
src/storage/btree.rs 96.58% 4 Missing ⚠️
src/storage/persistent_facts.rs 70.00% 3 Missing ⚠️
src/storage/freelist.rs 93.75% 2 Missing ⚠️

📢 Thoughts on this report? Let us know!

@adityamukho
adityamukho merged commit 58aa0ea into v3 Oct 6, 2026
18 checks passed
@adityamukho
adityamukho deleted the feat/v8-pr4-cow branch October 6, 2026 04:14
This was referenced Oct 6, 2026
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