Repository navigation
perf: checkpoint copies untouched index leaves instead of rebuilding every index (#315) - #402
Merged
Merged
Conversation
Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com> Claude-Session: https://claude.ai/code/session_01BedF9ZmqVZLkvDwn91fuKy
Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com> Claude-Session: https://claude.ai/code/session_01BedF9ZmqVZLkvDwn91fuKy
Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com> Claude-Session: https://claude.ai/code/session_01BedF9ZmqVZLkvDwn91fuKy
Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com> Claude-Session: https://claude.ai/code/session_01BedF9ZmqVZLkvDwn91fuKy
…build (#315) Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com> Claude-Session: https://claude.ai/code/session_01BedF9ZmqVZLkvDwn91fuKy
Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com> Claude-Session: https://claude.ai/code/session_01BedF9ZmqVZLkvDwn91fuKy
…act pages (#315) save() snapshots each index's raw leaf pages and rebuilds via rebuild_btree_incremental: leaves no pending entry touches are copied verbatim, touched leaves split balanced so repeated checkpoints do not fragment the tree. The CRC32 state over unchanged fact pages is cached so each save hashes only new fact pages and the index region. File format and stored checksum are unchanged. Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com> Claude-Session: https://claude.ai/code/session_01BedF9ZmqVZLkvDwn91fuKy
…oc sync Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com> Claude-Session: https://claude.ai/code/session_01BedF9ZmqVZLkvDwn91fuKy
…#315) Untouched leaves are now copied verbatim and sealed under a fresh file checksum, so collect_leaf_pages bounds-checks each leaf's slot directory and caps the chain at the file's page count instead of looping. Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com> Claude-Session: https://claude.ai/code/session_01BedF9ZmqVZLkvDwn91fuKy
Codecov Report❌ Patch coverage is
📢 Thoughts on this report? Let us know! |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Add this suggestion to a batch that can be applied as a single commit.This suggestion is invalid because no changes were made to the code.Suggestions cannot be applied while the pull request is closed.Suggestions cannot be applied while viewing a subset of changes.Only one suggestion per line can be applied in a batch.Add this suggestion to a batch that can be applied as a single commit.Applying suggestions on deleted lines is not supported.You must change the existing code in this line in order to create a valid suggestion.Outdated suggestions cannot be applied.This suggestion has been applied or marked resolved.Suggestions cannot be applied from pending reviews.Suggestions cannot be applied on multi-line comments.Suggestions cannot be applied while the pull request is queued to merge.Suggestion cannot be applied right now. Please check back later.
Summary
Every
checkpoint()used to stream all four covering indexes off disk, decode every entry, re-serialise everything and bulk-build four new B+trees. It then re-read the whole file for the checksum. So checkpointing after one new fact cost almost as much as after thousands, and the cost grew with graph size. Profiling showed the time was CPU spent decoding and re-encoding entries, not I/O.save()snapshots each old tree's raw leaf pages, then callsrebuild_btree_incremental(src/storage/btree_v6.rs):next_leafpointer is patched.build_btree.PersistentFactStoragecaches the CRC32 state over the fact pages, which are never rewritten. Each save now hashes only the new fact pages and the index region. The storedindex_checksumvalue is unchanged: a CRC over pages1..page_count.collect_leaf_pagesbounds-checks each leaf's slot directory and caps the leaf chain at the file's page count. A damaged index now fails the checkpoint instead of being copied forward under a fresh checksum.checkpoint()andwal_checkpoint_thresholddocs now say that a checkpoint is not a durability boundary (the WAL is already crash-durable) and that its cost grows with graph size. The outdated "same-process double-open" rationale indo_checkpointis trimmed, as the issue's aside asked.The file format is unchanged: v7 node and header layouts are the same, and files written by this branch open on v2.0.1 without the index-rebuild path.
Mitigates #315. Checkpoint cost still grows with graph size, because index pages are copied on every checkpoint; the new fact pages always land on the start of the old index region. Checkpoints proportional to the change alone need copy-on-write pages, which is the same change #374 needs on the v3 branch.
Measurements
cargo bench --bench minigraf_bench -- checkpoint/after_1_fact(new group): an already-checkpointed file receives one new fact, thencheckpoint()runs. tmpfs, same host.Separate harness, 50k facts (13 MB): 80 ms → 10.1 ms. Cost after 3000 consecutive single-fact checkpoints on 10k facts: 3.1 ms. Before the balanced-split fix it was 28.7 ms, from fragmentation.
Type of change
Checklist
cargo testpasses (1182 passed, 0 failed, 8 ignored)cargo clippy -- -D warningsis cleancargo fmt --checkpassesunwrap()/expect()in library code pathsCHANGELOG.mdupdated underUnreleasedTests
btree_v6(10 new):range_scanon random bounds.next_leaf), keys outside the old range, thousands of entries routed into one leaf, an empty old tree, and a new tree written over the old tree's pages.persistent_facts(4 new):Notes for reviewer
sort_unstableis used.stream_all_entriesis now#[cfg(test)]; it has no other caller.docs/superpowers/specs/2026-09-26-incremental-checkpoint-design.mdanddocs/superpowers/plans/. §4.1 of the spec records the switch to balanced splits.🤖 Generated with Claude Code
https://claude.ai/code/session_01BedF9ZmqVZLkvDwn91fuKy