Repository navigation
save() is not crash-atomic: new fact pages overwrite old index pages before header commit #374
Description
Summary
Split out of #370. PersistentFactStorage::save() is not crash-atomic: it writes new fact pages at 1 + old_fact_page_count, which is where the old index pages live, and rebuilds the new indexes in place, all before writing the header. A kill anywhere between the first page write and the header write leaves the old header pointing at overwritten index pages.
Current behaviour
- The checksum mismatch on next open triggers a full index rebuild from the fact pages (correct only since the bug: after a kill during an active run the EAVT index silently loses most entities' entries while AEVT stays intact — entity-bound lookups return [] and no rebuild path exists #370 fix; before it, the rebuild produced wrong
FactRefs). - So a crash mid-
save()is always followed by an O(graph) rebuild on open, and any bug in that rebuild path becomes a data-visibility bug. - Related: SIGKILL during an active transact has a ~26% chance of permanently corrupting the entire database (header checksum, no recovery path) #308 (header corruption after SIGKILL) and perf: checkpoint() is O(graph size) and flat in dirty bytes — it rebuilds all four covering indexes every call #315 (
checkpoint()cost scales with graph size).
Ask
Make save() crash-safe without a second file: e.g. write the new indexes to fresh pages beyond the old ones (or a shadow region) and only then flip the header, so the old header always references an intact, consistent tree. Evaluate interaction with page reuse/free-list, file growth, and #315 (incremental index update).
Philosophy check
Aligned: reliability over features, single-file. Must not change the file format in a breaking way (v2.x stability); if it needs a format change it belongs in v3.0.0 (v8).
Refs #370
Activity
release: v2.0.1 — fix index rebuild on open (#370)
adityamukho commentedon Sep 26, 2026
Scope note from #315 (checkpoint cost, mitigated on v2.x in #402):
On v7 every checkpoint must relocate the index. New fact pages must stay contiguous at
1..=fact_page_count, so they always overwrite the start of the old index region. #402 cut the per-checkpoint cost by roughly 6–10×: untouched leaves are copied raw, only the leaves that receive new entries are re-encoded, and unchanged fact pages are no longer re-hashed. But checkpoint cost still grows with graph size, because every index page is copied on every checkpoint.The fix for this issue removes that remaining term. With copy-on-write B+tree pages and a free list,
save()can write only the changed leaves and their root paths, then commit by swapping the header. That makes the save crash-atomic and makes checkpoint cost O(delta · log n) instead of O(index size). Whoever designs the v8/v3 layout here should treat O(delta) checkpoints as part of the requirement.Two pieces of #402 carry over:
rebuild_btree_incremental's routing and balanced-split logic, which avoids leaf fragmentation.A full-file CRC over rewritten pages is itself O(file) and would need rethinking, for example per-page checksums.
docs: sync test count (1212) for #374 crash test
test(storage): crash at every write/sync in save() loses no checkpoin…
Merge pull request #442 from project-minigraf/feat/v8-pr1-cursor
Merge pull request #444 from project-minigraf/feat/v8-pr2-page-format
adityamukho commentedon Oct 6, 2026
Fixed on
v3for v3.0.0 by the v8 storage format (#444 crash-atomic save with alternating meta pages; #451 copy-on-write checkpoints). A crash or torn write at any point of a checkpoint leaves the previous checkpoint intact, and open never rebuilds an index. v2.x is still affected and stays listed in #421 until v3.0.0 ships.