Repository navigation
v3.0.0 requirement: incremental checkpointing — checkpoint cost O(pages dirtied since the last checkpoint), never O(graph size), including the Drop-on-close checkpoint #434
Description
Requirement
In v3.0.0 a checkpoint writes only the pages dirtied since the previous checkpoint, plus the header. Its cost, in bytes written and in time, is a function of the change, never of the graph size. This holds for every path that checkpoints: explicit checkpoint(), the wal_checkpoint_threshold auto-checkpoint, and the checkpoint Drop for Inner runs on handle close.
ROADMAP already phrases the v3.0.0 goal as "crash-atomic save(), with checkpoints proportional to the change (#374)", but #374's body asks only for crash-atomicity and says to "evaluate interaction with #315". This issue makes proportional cost a requirement with numbers, so it cannot be traded away while #374 is implemented.
Why (measured, minigraf 2.0.2, file format v7, 2026-09-30)
Ingesting a 54k-commit repository through temporal_reasoning, at a 3.82 GB graph:
| measure | value |
|---|---|
| bytes written per checkpoint | ~3.27 GB (86% of the file; all index pages copied) |
| checkpoints per minute | 8 (one per lease-window handle close) |
| disk write rate | 434 MB/s sustained, 0 reads |
| net growth | ~2 MB/min → write amplification ~13,000× |
| ingestion throughput vs graph size | 230 commits/min at 0 GB, 73/min at 3.8 GB, falling as 1/size |
| projected drive writes for the run | 15–20 TB to store 9 GB |
Full trace in project-minigraf/temporal_reasoning#379. #315's mitigation (copy unchanged leaves verbatim instead of re-encoding) cut CPU but not bytes: every index page is still rewritten on every checkpoint, so the cost is O(N) with a smaller constant. On a 1B-fact graph (#433) an O(N) checkpoint is hundreds of GB per call and cannot be allowed at all.
Acceptance
On a graph of N facts, after a transaction touching k facts:
checkpoint()writes O(k · log N) pages: the dirtied fact pages, the modified B+tree leaves and their ancestors up to the root, and the header. Measured as bytes written per checkpoint ≤ c · (k · log N · page_size) for a constant c, independent of N; verified at 1M, 10M, 100M and 1B (perf: benchmark queries at 100K–10M facts and publish a performance envelope #394 extended).- The same bound holds for the auto-checkpoint and for the
Drop for Innerclose-time checkpoint, or the close-time checkpoint is removed and close relies on the WAL being crash-durable (the CHANGELOG already states a checkpoint is not a durability boundary). - Time per checkpoint after one fact at 1B facts ≤ 50 ms on the reference hardware; after 100k facts ≤ 5 s.
- A checkpoint never rewrites a page it did not dirty; a fault-injection run (test: drive the fault-injection backend through the full save/WAL/recovery paths #390) at every write point still reopens consistently (this is save() is not crash-atomic: new fact pages overwrite old index pages before header commit #374's property and must be preserved).
- Write amplification over a long ingest (bytes written to disk / bytes of live graph growth) ≤ 10 at steady state, reported by the perf: benchmark queries at 100K–10M facts and publish a performance envelope #394 benchmark.
Design direction
Copy-on-write B+tree pages with a free list, as #374 needs anyway for atomicity: a checkpoint allocates fresh pages only for the modified path from each dirty leaf to the root, writes them, then flips the header to the new root(s). Old pages become free after the header commit. This is a format v8 change and so belongs in this release (ROADMAP: "every other layout change this release needs goes into v8 too"), and needs settling before the golden-file corpus (#391) freezes v8. Space reclamation (compaction of freed pages) can be a later, separate operation; correctness and cost bounds cannot.
Related
#374 (crash-atomic save, same mechanism), #315 (closed mitigation, O(N) bytes remain), #322 (the close checkpoint cannot be suppressed from the FFI), #432 (streaming engine), #433 (1B target: this is one of its prerequisites), temporal_reasoning#379 (the field measurement).
Activity
adityamukho commentedon Oct 6, 2026
Done on
v3in #451 (copy-on-write checkpoints), measured in #452. A checkpoint after one new fact takes 3.0 ms at 10k facts, 3.3 ms at 100k and 6.1 ms at 1M, and one new fact at 100k writes 16 pages. This includes the close-time checkpoint.