diff --git a/CHANGELOG.md b/CHANGELOG.md index b4b293f53f..45b114db5a 100644 --- a/CHANGELOG.md +++ b/CHANGELOG.md @@ -10,8 +10,9 @@ and this project adheres to [Semantic Versioning](https://semver.org/spec/v2.0.0 ### Breaking changes - **File format v8** (#287, #371). Index keys now include the encoded value and the assert/retract flag. A v7 file (written by v2.x) is re-indexed and upgraded to v8 the first time it is opened; the upgrade is one-way and v2.x cannot open a v8 file (`STG-006`). Bindings users get this upgrade silently on open. -- **Crash-atomic checkpoints with verified pages** (v8 storage format, PR 2 of 5; #374, #388). Two alternating meta pages replace the 84-byte file header and are the only commit point: a checkpoint writes only pages the last commit does not use, syncs, then writes the other meta page and syncs. A crash or torn write at any point leaves the previous checkpoint intact, so opening never rebuilds an index, and the whole-file index checksum is gone. Every other page carries a 24-byte header (type, CRC32, its own page id, the checkpoint generation that wrote it), checked on every read: a torn, corrupted, misplaced or stale page now fails with `STG-029`, `STG-030` or `STG-031` instead of being read. If the newest meta page is damaged after its WAL was already deleted, open fails with `STG-033` rather than silently going back to the previous checkpoint. New codes `STG-029`–`STG-035`. The WAL header gains a base generation (WAL version 2); a v2.x WAL beside a migrated file is still replayed. Pages freed by a checkpoint are reused by later ones; checkpoints still rewrite all four indexes until copy-on-write insert lands (PR 4). Files written by a v3.0.0 development build before this change fail with `STG-032`. +- **Crash-atomic checkpoints with verified pages** (v8 storage format, PR 2 of 5; #374, #388). Two alternating meta pages replace the 84-byte file header and are the only commit point: a checkpoint writes only pages the last commit does not use, syncs, then writes the other meta page and syncs. A crash or torn write at any point leaves the previous checkpoint intact, so opening never rebuilds an index, and the whole-file index checksum is gone. Every other page carries a 24-byte header (type, CRC32, its own page id, the checkpoint generation that wrote it), checked on every read: a torn, corrupted, misplaced or stale page now fails with `STG-029`, `STG-030` or `STG-031` instead of being read. If the newest meta page is damaged after its WAL was already deleted, open fails with `STG-033` rather than silently going back to the previous checkpoint. New codes `STG-029`–`STG-035`. The WAL header gains a base generation (WAL version 2); a v2.x WAL beside a migrated file is still replayed. Pages freed by a checkpoint are reused by later ones. Files written by a v3.0.0 development build before this change fail with `STG-032`. - **Covering indexes with dictionary-coded keys** (v8 storage format, PR 3 of 5; #433). Every index entry now holds the whole fact as a byte-comparable key, so a query reads only index pages, never a separate fact page. Entities and idents (attribute names and keyword values) get sequential internal ids from a dictionary stored in the file, and strings longer than 64 bytes are stored once in value pages and deduplicated. Fact pages are gone. A file with 100,000 facts (10 attributes per entity) takes 88 bytes per fact, down from 314. Facts from committed data now come back in internal-id order (entity, then attribute) rather than insertion or UUID order; query results are sets, and code that relied on an order must sort. New codes `STG-036` (dictionary entry missing) and `STG-037` (one transaction with two timestamps: a checkpoint or v7 upgrade refuses to change a stored timestamp). Files written by a v3.0.0 development build before this change fail with `STG-032`. +- **Checkpoints cost what changed, not the size of the database** (v8 storage format, PR 4 of 5; #434). A checkpoint now inserts copy-on-write: it rewrites only the index leaves that receive new facts and their paths to the root, and reuses pages freed by earlier checkpoints through a free list it reads and extends only as far as it needs. A checkpoint after one new fact takes 3.1 ms on a 10,000-fact file and 3.3 ms on a 100,000-fact file (it took 15.5 ms and 43 ms before, and grew with the file). One new fact at 100,000 facts writes 16 pages. The `checkpoint()` and `wal_checkpoint_threshold` docs now describe this cost. - **Size limits for file-backed databases:** a string value may be up to 4,068 bytes, whatever the rest of the fact, and an attribute name or keyword value up to 1,024 bytes. Both are checked when the transaction is written and fail with `WAL-003`, whose message now names the value. This replaces the 4,080-byte limit on a whole serialised fact (4,052 in earlier v3.0.0 development builds). In-memory databases have no limit. - **Formats v1–v6 are no longer readable.** Opening one fails with the new `STG-028`; open it once with Minigraf v2.x to upgrade it to v7 first. `STG-003` and `STG-004` are deprecated (no longer emitted, still registered, never reused). `STG-005` and `STG-006` message text changed. diff --git a/CLAUDE.md b/CLAUDE.md index 15d358a0dd..1482563102 100644 --- a/CLAUDE.md +++ b/CLAUDE.md @@ -111,7 +111,7 @@ cargo run < demos/demo_negation.txt - `index.rs`: pending (uncheckpointed) EAVT/AEVT keys over UUIDs and strings, `encode_value` - `keys.rs`: byte-comparable v8 keys (FDB integers, value tags, `tx↓`, FOREVER), DICT keys, `MAX_VALUE_BYTES`, `MAX_IDENT_BYTES` - `node.rs`: prefix-compressed leaf and shortest-separator internal node codecs - - `btree.rs`: On-disk B+tree over byte keys (`build_btree`, `rebuild_btree_incremental`, `LeafCursor` with `seek`, `prefix_scan`, `get`, `MutexStorageBackend`) + - `btree.rs`: On-disk B+tree over byte keys (`build_btree`, `cow_insert`, `LeafCursor` with `seek`, `prefix_scan`, `get`, `MutexStorageBackend`) - `dict.rs`: `DictReader` (id ↔ UUID/ident, tx timestamps, long values) and `Encoder` (checkpoint-time id assignment and key building) - `value_pages.rs`: append-only value pages for strings over 64 bytes - `reader.rs`: `OnDiskReader` — covering reads of committed facts (`CommittedReader`) @@ -182,15 +182,18 @@ Sidecar: .wal — v2 header records the base generation; CRC32-protected e Covering indexes: every index entry is a whole fact as a byte-comparable key (`e a v tx↓ vf vt op` in EAVT order), with entities and idents as sequential ids from the DICT tree, assigned at checkpoint. Strings over 64 bytes live once in value pages. -Committed scans return facts in id order. A checkpoint writes only pages the active -meta does not reference, syncs, then writes the other meta page and syncs, so a crash -at any point keeps the previous checkpoint. +Committed scans return facts in id order. A checkpoint is copy-on-write: it rewrites +only touched leaves and their paths (`btree::cow_insert`), takes pages from the free +list lazily and pushes freed ones (`PageAllocator::from_chain` / `finish_free_list`), +so its cost follows the change. It writes only pages the active meta does not +reference, syncs, then writes the other meta page and syncs, so a crash at any point +keeps the previous checkpoint. Auto-migrates v7 → v8 on open (spec §9, with a backup meta page). v1–v6 are rejected (STG-028). Design: `docs/superpowers/specs/2026-10-05-v8-storage-format-design.md`. ## Test Coverage -**1226 tests** (1218 passing, 8 ignored; unit + integration + doc). +**1230 tests** (1222 passing, 8 ignored; unit + integration + doc). See `docs/TEST_COVERAGE.md` for the full per-file breakdown. **Testing conventions** — see the Testing Conventions section below before writing any tests. diff --git a/README.md b/README.md index 0e0a299c08..fb5d029946 100644 --- a/README.md +++ b/README.md @@ -105,7 +105,7 @@ let r2 = pq.execute(&[("tx", BindValue::TxCount(2)), ("entity", BindValue::Entit ```bash cargo run # interactive Datalog REPL -cargo test # run 1226 tests +cargo test # run 1230 tests cargo run < demos/demo_recursive.txt # recursive rules demo ``` diff --git a/docs/TEST_COVERAGE.md b/docs/TEST_COVERAGE.md index b37ae085cc..df9b7bf0cc 100644 --- a/docs/TEST_COVERAGE.md +++ b/docs/TEST_COVERAGE.md @@ -4,9 +4,9 @@ **Verified**: 2026-10-05 with `cargo test --quiet` -**Result**: 1,218 passing tests and 8 ignored tests (1,226 total) +**Result**: 1,222 passing tests and 8 ignored tests (1,230 total) -This covers the unreleased file-format-v8 work (#287, #371): the index-key value-collision fix, the v7→v8 migration, and the drop of formats v1–v6. It otherwise still covers the public database API, the Datalog engine, storage and recovery paths, v2.0.0's locking and structured-error-code changes, and v2.0.1's regression test for rebuilding indexes on open after several checkpoints (#370). Merged from the v2.x line: `tests/point_query_history_test.rs` and new storage unit tests check that attribute-narrowed bound-entity lookups return exactly what a full scan returns, and that `net_asserted_facts` matches its previous implementation on randomized histories (#323). Attribute-scan tests check that the AEVT range covers exactly the queried attribute, including non-ASCII names such as `:丿` and prefix siblings such as `:ab` for `:a` (#381). Incremental B+tree rebuild tests check that checkpoints which copy untouched index leaves produce exactly the entries and file checksum a full rebuild would, including over repeated checkpoints, that single-fact checkpoints do not fragment the index, and that a damaged slot directory is rejected rather than copied (#315). B+tree cursor tests check that every scan walks the tree, not the leaf `next_leaf` chain: full scans and start positions match the input, `seek` from the current position lands where a fresh descent from the root would (randomized, plus within a leaf, to a sibling, across subtrees, past the end, into the gap after a leaf, and backwards as a no-op), a seek to the sibling leaf reads exactly one page, reads are unchanged with every `next_leaf` zeroed, a child pointer into a non-B+tree page is STG-013, and a cycle in child pointers is an error, not a hang (v8 storage format PR 1, #374). Directory-sync unit tests check that creating the `.graph` file or the WAL, and deleting the WAL, fsync the parent directory after the file operation, and that reopening an existing file does not (#389). Disjunction tests check that `or-join` returns an empty result, not INT-031, when no rows reach it: on an empty database, after a pattern that matches nothing, after a `not` that removes every row, and in a rule body (#405). A stratification unit test builds the same two-rule negative cycle 64 times and checks that the INT-054 message names the same predicate pair every time (#410). Magic-sets tests check that a recursive rule with a literal start that recurses through another rule returns the same results as without the literal (#297). API tests check that `execute()` and `WriteTransaction::execute()` reject `$slot` bind tokens in every position with API-010 (#407). The REPL `run()` test now runs in a child process with null stdin, so it no longer hangs when the test runner's stdin is an open non-TTY stream (#415). v8 page-format tests (PR 2, #374, #388) check the 24-byte page header (a flipped bit, a wrong page id and a future generation each give their own STG code, legacy page types fail before the CRC, and a failed page is never cached), meta-page encoding, the free-list chain, WAL v2's base generation, and every row of the meta-selection table: both slots valid, a torn newest slot with the WAL's base generation (opens at the older one), a WAL newer than the valid meta, pages of the next generation on the free list or past `page_count` with no WAL (all STG-033, with the file unmodified), an unknown feature bit (STG-034), and a pre-release v8 single header (STG-032). Fault-injection tests crash `save()` at every page write (cleanly and with torn pages, including the meta write) and every sync, and crash a v7 migration at every write; each reopen finds exactly the old or the new checkpoint, and every reachable page plus the free list covers the file exactly. Twenty-five consecutive saves never write a page the previous meta references. Covering-key tests (PR 3, #433) check that byte order equals logical order for every key component and value type on random tuples (negative, zero and large integers, NaN and ±0.0, strings with 0x00, 64- and 65-byte strings, FOREVER, newest-transaction-first) and that every component round-trips; that prefix-compressed leaves and shortest-separator internal nodes round-trip, agree with a linear scan, keep `max(left) < s ≤ min(right)`, and reject an overflow; that the byte-key B+tree's builds, incremental rebuilds, cursor and `seek` match their expected sets; that dictionary ids are assigned once, never reused, shared between a keyword attribute and value, and deterministic; that a re-asserted or retracted long value writes no new value page and a forced hash collision still finds the right value; that one transaction with two timestamps is STG-037 and a missing dictionary entry STG-036; that committed reads by entity, entity and attribute, attribute, and in full equal an in-memory model across eight checkpoints and a reopen; that short-valued reads touch no value page; that a v7 file with every value type, long strings, refs and retractions migrates to exactly the same facts; that a pre-covering-key v8 file is STG-032; and that string values over 4,068 bytes and attributes or keywords over 1,024 bytes are WAL-003. A WAL test checks that reopening next to a fully checkpointed WAL does not reuse transaction numbers (#447). Merged from the v2.x line: storage and `edge_cases_test.rs` tests check that more than 65,535 uncheckpointed facts each resolve to their own fact through entity lookups and attribute scans, in memory and file-backed (#445). +This covers the unreleased file-format-v8 work (#287, #371): the index-key value-collision fix, the v7→v8 migration, and the drop of formats v1–v6. It otherwise still covers the public database API, the Datalog engine, storage and recovery paths, v2.0.0's locking and structured-error-code changes, and v2.0.1's regression test for rebuilding indexes on open after several checkpoints (#370). Merged from the v2.x line: `tests/point_query_history_test.rs` and new storage unit tests check that attribute-narrowed bound-entity lookups return exactly what a full scan returns, and that `net_asserted_facts` matches its previous implementation on randomized histories (#323). Attribute-scan tests check that the AEVT range covers exactly the queried attribute, including non-ASCII names such as `:丿` and prefix siblings such as `:ab` for `:a` (#381). Incremental B+tree rebuild tests check that checkpoints which copy untouched index leaves produce exactly the entries and file checksum a full rebuild would, including over repeated checkpoints, that single-fact checkpoints do not fragment the index, and that a damaged slot directory is rejected rather than copied (#315). B+tree cursor tests check that every scan walks the tree, not the leaf `next_leaf` chain: full scans and start positions match the input, `seek` from the current position lands where a fresh descent from the root would (randomized, plus within a leaf, to a sibling, across subtrees, past the end, into the gap after a leaf, and backwards as a no-op), a seek to the sibling leaf reads exactly one page, reads are unchanged with every `next_leaf` zeroed, a child pointer into a non-B+tree page is STG-013, and a cycle in child pointers is an error, not a hang (v8 storage format PR 1, #374). Directory-sync unit tests check that creating the `.graph` file or the WAL, and deleting the WAL, fsync the parent directory after the file operation, and that reopening an existing file does not (#389). Disjunction tests check that `or-join` returns an empty result, not INT-031, when no rows reach it: on an empty database, after a pattern that matches nothing, after a `not` that removes every row, and in a rule body (#405). A stratification unit test builds the same two-rule negative cycle 64 times and checks that the INT-054 message names the same predicate pair every time (#410). Magic-sets tests check that a recursive rule with a literal start that recurses through another rule returns the same results as without the literal (#297). API tests check that `execute()` and `WriteTransaction::execute()` reject `$slot` bind tokens in every position with API-010 (#407). The REPL `run()` test now runs in a child process with null stdin, so it no longer hangs when the test runner's stdin is an open non-TTY stream (#415). v8 page-format tests (PR 2, #374, #388) check the 24-byte page header (a flipped bit, a wrong page id and a future generation each give their own STG code, legacy page types fail before the CRC, and a failed page is never cached), meta-page encoding, the free-list chain, WAL v2's base generation, and every row of the meta-selection table: both slots valid, a torn newest slot with the WAL's base generation (opens at the older one), a WAL newer than the valid meta, pages of the next generation on the free list or past `page_count` with no WAL (all STG-033, with the file unmodified), an unknown feature bit (STG-034), and a pre-release v8 single header (STG-032). Fault-injection tests crash `save()` at every page write (cleanly and with torn pages, including the meta write) and every sync, and crash a v7 migration at every write; each reopen finds exactly the old or the new checkpoint, and every reachable page plus the free list covers the file exactly. Twenty-five consecutive saves never write a page the previous meta references. Covering-key tests (PR 3, #433) check that byte order equals logical order for every key component and value type on random tuples (negative, zero and large integers, NaN and ±0.0, strings with 0x00, 64- and 65-byte strings, FOREVER, newest-transaction-first) and that every component round-trips; that prefix-compressed leaves and shortest-separator internal nodes round-trip, agree with a linear scan, keep `max(left) < s ≤ min(right)`, and reject an overflow; that the byte-key B+tree's builds, incremental rebuilds, cursor and `seek` match their expected sets; that dictionary ids are assigned once, never reused, shared between a keyword attribute and value, and deterministic; that a re-asserted or retracted long value writes no new value page and a forced hash collision still finds the right value; that one transaction with two timestamps is STG-037 and a missing dictionary entry STG-036; that committed reads by entity, entity and attribute, attribute, and in full equal an in-memory model across eight checkpoints and a reopen; that short-valued reads touch no value page; that a v7 file with every value type, long strings, refs and retractions migrates to exactly the same facts; that a pre-covering-key v8 file is STG-032; and that string values over 4,068 bytes and attributes or keywords over 1,024 bytes are WAL-003. A WAL test checks that reopening next to a fully checkpointed WAL does not reuse transaction numbers (#447). Copy-on-write checkpoint tests (PR 4, #434) check that lazy free-list pops and pushes conserve every page across page boundaries, partial head pages and chain exhaustion, never hand out a page freed in the same generation, and share unread chain pages unchanged; that a copy-on-write insert equals a sorted merge for random batches (including keys below the first and above the last, many into one leaf, root growth to depth 3, and 1 KB separators that split internal nodes), leaves the old tree readable and unchanged, frees exactly the replaced nodes, writes only new pages, writes exactly one leaf and two internal nodes for one entry in a depth-3 tree, and does not fragment leaves under single inserts; that a checkpoint after 1 or 100 right-edge facts writes at most the tree-depth difference more pages at 100,000 facts than at 10,000, and at most one path per new entry per tree for random keys; and that four reader threads querying throughout 40 checkpoints never fail and never see the fact count go backwards. Merged from the v2.x line: storage and `edge_cases_test.rs` tests check that more than 65,535 uncheckpointed facts each resolve to their own fact through entity lookups and attribute scans, in memory and file-backed (#445). ### Covered Areas diff --git a/docs/superpowers/plans/2026-10-05-v8-storage-format.md b/docs/superpowers/plans/2026-10-05-v8-storage-format.md index 0eaaf6ea4b..ba3f4a0440 100644 --- a/docs/superpowers/plans/2026-10-05-v8-storage-format.md +++ b/docs/superpowers/plans/2026-10-05-v8-storage-format.md @@ -541,15 +541,118 @@ is still a full rewrite (O(N)); PR 4 makes it O(change). - [ ] `cargo fmt`, clippy, `cargo test`; open the PR into `v3` with `Refs #433 #374 #434 #388`. Own CI until green. Ask before merging. -# PR 4 — Copy-on-write insert, allocator, free list (outline) +# PR 4 — Copy-on-write insert, allocator, free list + +Spec §4.4, §8. Branch `feat/v8-pr4-cow`. The format does not change. + +**Outcome:** a checkpoint writes only new value pages, the copied path from each touched +leaf to its root in each of the five trees, the free-list pages it pushes or rewrites, +and one meta page. Its cost depends on the change, not on the graph size (#434 +acceptance 1, 2, 4). + +**Shape decisions (from reading the v3 code after PR 3):** + +- **Lazy free-list pop.** `PageAllocator` gains a chain source: it reads `M`'s free-list + pages one at a time, only when it needs another id, and hands out ids in page order. + A page whose ids are all handed out becomes free itself (it is unreferenced once the + new meta commits). `alloc` therefore needs read access to the backend and cache: + its signature becomes `alloc(&mut self, backend: &dyn StorageBackend, cache: + &PageCache)`. The eager `Vec` form stays for the migration and for tests. +- **Push at the end of the checkpoint.** The pushed ids are: + - every page the checkpoint replaced (old tree nodes on copied paths); + - every chain page it emptied; + - the head page it partly consumed, plus that page's remaining ids. + + They are written as new head pages whose `next` is the first untouched chain page, + so the untouched tail is shared. The new head pages are allocated through the same + allocator, which may pop more ids; that repeats until stable (it converges in one or + two rounds). Nothing pushed by this checkpoint is reused within it (§8.1). + `freelist_count` is computed as old count − ids in the pages read + ids pushed. The + cost is O(pages allocated + pages freed). +- **Copy-on-write batch insert** (`btree::cow_insert(root, sorted entries, alloc, freed)`): + - **Descent and routing:** descend from the root, partitioning the entries by + `Internal::route`. + - **Leaves:** a touched leaf is merged with its entries and repacked with + `pack_leaves`, the balanced split from #315. + - **Internal nodes:** a touched internal node is rewritten with each touched child + replaced by its pieces. Separators between new pieces are the shortest separators + of the adjacent pieces' last and first keys; existing separators stay valid because + the routed keys lie within them. An internal node that outgrows a page is split, + balanced by bytes, and the separator at the cut moves up. + - **Root:** a root split adds a level. + - **Freeing:** every replaced page goes into `freed`; untouched subtrees are shared + by page id. + - **Edge cases:** an empty tree (root 0) is a bulk build. Nothing is ever removed + from a tree, so there is no merging. +- **`save()`** no longer collects the old trees' leaves. It calls `cow_insert` on each + of the five trees, then pushes onto the free list. `rebuild_btree_incremental` and + the full-tree `collect_leaf_pages` snapshot leave the checkpoint path: + `collect_leaf_pages` stays for the reachability test helpers and for #373's verify. +- **Concurrency (§8.1).** A query holds the `FactStorage` read guard for its whole + scan, and swapping in the new reader needs the write lock. So no query spans two + checkpoints, and pages freed by checkpoint N are written only by N + 1, after every + reader of N − 1 has finished. The page cache stays write-through. +- **Browser (§12).** `BrowserBufferBackend` already tracks dirty pages per write, so a + flush is O(change) once checkpoints are. Verify it, with no code change expected. -Spec §4.4, §8. +## Review Focus -- Allocator over `M`'s free list plus append. Free-list chain pop/push with copy-on-write head pages. -- Copy-on-write batch insert per tree, reusing #315's balanced split and freeing replaced pages. -- Reachability/free-list invariant checker, used in tests after every checkpoint. -- Cost-bound test with a page-counting backend; a guard that pages referenced by the previous meta are never written. -- Concurrency test: queries during checkpoints. +- A checkpoint never writes a page the previous meta references (tested on every save). +- After every save, the reachable pages and the free ids are disjoint and cover + `2..page_count` exactly. +- Copy-on-write insert equals a sorted merge, and the old root still streams its old + contents unchanged. + +### Task 1: Lazy chain allocator and push + +- [x] `PageAllocator::from_chain(head, count, next_append, generation)`; `alloc` reads + chain pages on demand; `finish_free_list(freed, backend, cache) -> (head, count)` + pushes and writes new head pages. +- [x] Tests: pop across page boundaries; partial head rewrite; untouched tail shared + (same page ids); count arithmetic; no id handed out twice; pushed ids never handed + out in the same generation. + +### Task 2: `cow_insert` + +- [x] Recursive insert returning replacement pieces `(Option, page id, + first key, last key)`. Leaf merge and balanced split, internal rewrite and split, + root growth. +- [x] Tests: + - random committed sets and pending batches (below the first key, above the last, + into one leaf, root splits), compared with a sorted union; + - the old root streams its old contents unchanged; + - `freed` equals exactly the old pages on the touched paths; + - single inserts do not fragment leaves; + - depth-1 to depth-4 trees. + +### Task 3: `save()` on copy-on-write + +- [x] Five `cow_insert` calls plus the free-list push. Remove `rebuild_btree_incremental` + from `save()`; port its tests to `cow_insert` or delete those that duplicate. +- [x] The existing crash-at-every-point, space-accounting and never-write-committed-pages + tests keep passing. + +### Task 4: Cost bound + +- [x] A page-counting backend counts pages written by a checkpoint after k ∈ {1, 100} + facts on graphs of 10k and 100k facts. The 100k count may exceed the 10k count by at + most the tree-depth difference per tree plus the free-list pages. +- [x] `checkpoint/after_1_fact` measured at 10k and 100k (3.1 / 3.3 ms). `after_100k_facts` + and 1M move to PR 5. + +### Task 5: Concurrency + +- [x] `concurrency_test`: reader threads query in a loop while the writer transacts + and checkpoints repeatedly. Every read succeeds (no CRC, page-id or generation + error) and sees a consistent fact count. + +### Task 6: Docs, PR + +- [x] CHANGELOG (checkpoint cost, with numbers), `checkpoint()` and + `wal_checkpoint_threshold` rustdoc ("copies pages in proportion to the total index + size" goes), CLAUDE.md, TEST_COVERAGE. +- [x] `cargo fmt`, clippy, `cargo test`; open the PR into `v3` with `Refs #434 #374`. Own + CI until green. Ask before merging. # PR 5 — Hardening, benchmarks, docs (outline) diff --git a/src/db.rs b/src/db.rs index ad6ce92f04..841b9a51fc 100644 --- a/src/db.rs +++ b/src/db.rs @@ -115,9 +115,10 @@ pub struct OpenOptions { /// Defaults to 1000. Lower values mean more frequent checkpoints (smaller WAL, /// more I/O). Higher values mean less frequent checkpoints (larger WAL, less I/O). /// - /// A checkpoint's cost grows with the total size of the database (see - /// [`Minigraf::checkpoint`]), while durability does not depend on it: the WAL - /// is crash-durable. Raise this for write-heavy workloads on large graphs. + /// A checkpoint's cost follows the facts written since the last one, not the + /// size of the database (see [`Minigraf::checkpoint`]), and durability does not + /// depend on it: the WAL is crash-durable. Lower values keep the WAL and reopen + /// time small; higher values batch more facts per checkpoint. pub wal_checkpoint_threshold: usize, /// Number of pages to hold in the LRU page cache. Default: 256 (= 1MB at 4KB pages). /// @@ -706,10 +707,11 @@ impl Minigraf { /// crash-durable in the `.wal` sidecar and are replayed on the next open. /// Checkpointing less often only makes that replay (reopen) slower. /// - /// Cost: every checkpoint rewrites the four covering indexes after the fact - /// pages, so it copies pages in proportion to the total index size; only the - /// index leaves that receive new entries are decoded and re-encoded. Prefer - /// checkpointing on a size or time budget over once per logical unit of work. + /// Cost: a checkpoint is copy-on-write. It writes only the index leaves that + /// receive new facts, their paths to the root, new long-string pages, a few + /// free-list pages and one meta page, so its cost follows the number of new + /// facts, not the size of the database. A crash at any point leaves the + /// previous checkpoint intact. /// /// No-op for in-memory databases. /// diff --git a/src/storage/btree.rs b/src/storage/btree.rs index d6d50c9ffc..786dc0930a 100644 --- a/src/storage/btree.rs +++ b/src/storage/btree.rs @@ -5,16 +5,16 @@ //! empty values and DICT uses real ones. Leaves have no sibling pointers: scans //! use [`LeafCursor`], which keeps the path from the root. //! -//! [`build_btree`] bulk-builds a tree from sorted entries. [`rebuild_btree_incremental`] -//! rebuilds one from its old leaves plus new entries, copying untouched leaves -//! (restamped) and splitting touched ones by balanced bytes. Every page comes -//! from a [`PageAllocator`], so a rebuild never writes a page the old tree uses. +//! [`build_btree`] bulk-builds a tree from sorted entries. [`cow_insert`] adds +//! entries copy-on-write, rewriting only the touched leaves and their paths and +//! splitting by balanced bytes. Every page comes from a [`PageAllocator`], so an +//! insert never writes a page the old tree uses. use crate::error::{ErrorCode, bail_coded, err_coded}; use crate::storage::cache::PageCache; use crate::storage::node::{ Entry, Internal, decode_leaf, encode_internal, encode_leaf, internal_size, leaf_entry_sizes, - leaf_first_key, leaf_get, leaf_last_key, leaf_size, shortest_separator, validate_leaf, + leaf_get, leaf_size, shortest_separator, }; use crate::storage::page::{PAGE_HEADER_SIZE, PAGE_TYPE_INTERNAL, PAGE_TYPE_LEAF, PageAllocator}; use crate::storage::{PAGE_SIZE, StorageBackend}; @@ -90,7 +90,7 @@ fn write_leaf( alloc: &mut PageAllocator, ) -> Result { let page = encode_leaf(entries)?; - let id = alloc.alloc()?; + let id = alloc.alloc(&*backend, cache)?; alloc.write(backend, cache, id, page)?; Ok(id) } @@ -153,7 +153,7 @@ fn build_internal_levels( node_last = n.last; } let page = encode_internal(&children, &seps)?; - let id = alloc.alloc()?; + let id = alloc.alloc(&*backend, cache)?; alloc.write(backend, cache, id, page)?; next.push(NodeInfo { id, @@ -222,64 +222,221 @@ fn merge_entries(old: Vec, new: Vec) -> Result> { } } -/// Rebuild a B+tree from its old leaves (in key order) plus sorted `pending` -/// entries with distinct keys. -/// -/// A pending key routes to leaf `i` when `first_key[i] <= key < first_key[i + 1]` -/// (keys below the first leaf go to leaf 0). Leaves that receive nothing are -/// copied verbatim apart from the page id, generation and CRC; the others are -/// decoded, merged and repacked. Internal levels are rebuilt. With no non-empty -/// old leaf this is a bulk build. Returns the root page id. -pub fn rebuild_btree_incremental( - old_leaves: Vec>>, - pending: Vec, +// ─── Copy-on-write insert (spec §8.3) ──────────────────────────────────────── + +/// A node written by a copy-on-write insert, standing in for one child slot of +/// its parent: the separator that goes before it in the parent (`None` for the +/// first piece, which keeps the parent's existing separator) and its page id. +struct Piece { + sep: Option>, + id: u64, +} + +/// Write internal nodes for `elems`, `(separator before, child)` pairs in key +/// order (the first separator is ignored). One node if they fit in a page, +/// otherwise several of about [`PAGE_FILL_BYTES`] each, balanced by size; the +/// separator at each cut moves up as the next piece's separator. +fn write_internal_pieces( + elems: Vec<(Option>, u64)>, backend: &mut dyn StorageBackend, cache: &PageCache, alloc: &mut PageAllocator, -) -> Result { - check_sorted(&pending)?; - let mut leaves: Vec<(Arc>, Vec)> = Vec::with_capacity(old_leaves.len()); - for page in old_leaves { - if let Some(first) = leaf_first_key(&page[..])? { - leaves.push((page, first)); +) -> Result> { + let sep_size = |s: &Option>| { + s.as_ref() + .map_or(0, |s| internal_size([s.as_slice()]) - internal_size([])) + }; + let sizes: Vec = elems + .iter() + .enumerate() + .map(|(i, (s, _))| if i == 0 { 0 } else { sep_size(s) }) + .collect(); + let total: usize = sizes.iter().sum(); + let body = internal_size([]); + let mut parts = if body + total <= PAGE_SIZE { + 1 + } else { + total.div_ceil(PAGE_FILL_BYTES - body).max(2) + }; + // Group `g` ends where the running size reaches (g + 1) / parts of the + // total. A group's first separator moves up, so it does not count. + let groups = loop { + let mut bounds = Vec::with_capacity(parts); + let mut running = 0usize; + for (i, size) in sizes.iter().enumerate() { + let g = bounds.len(); + if i > 0 && g + 1 < parts && (running + size) * parts > total * (g + 1) { + bounds.push(i); + } + running += size; } + bounds.push(elems.len()); + let mut start = 0; + let mut fits = true; + for &end in &bounds { + let seps = sizes + .get(start + 1..end) + .unwrap_or(&[]) + .iter() + .sum::(); + fits &= body + seps <= PAGE_SIZE; + start = end; + } + if fits { + let mut groups: Vec>, u64)>> = Vec::with_capacity(bounds.len()); + let mut it = elems.into_iter(); + let mut start = 0; + for end in bounds { + groups.push(it.by_ref().take(end - start).collect()); + start = end; + } + break groups; + } + if parts >= elems.len() { + bail_coded!(ErrorCode::Int049, "a separator does not fit in a node"); + } + parts += 1; + }; + let mut pieces = Vec::with_capacity(groups.len()); + for (g, group) in groups.into_iter().enumerate() { + let mut seps = Vec::with_capacity(group.len()); + let mut children = Vec::with_capacity(group.len()); + let mut up = None; + for (i, (sep, child)) in group.into_iter().enumerate() { + if i == 0 { + up = sep; + } else { + seps.push( + sep.ok_or_else(|| err_coded!(ErrorCode::Int049, "child without separator"))?, + ); + } + children.push(child); + } + let page = encode_internal(&children, &seps)?; + let id = alloc.alloc(&*backend, cache)?; + alloc.write(backend, cache, id, page)?; + pieces.push(Piece { + sep: if g == 0 { None } else { up }, + id, + }); + } + Ok(pieces) +} + +/// Insert sorted `entries` below `page_id`, copy-on-write. Returns the pieces +/// that replace the node; the node itself goes into `freed`. +fn insert_node( + page_id: u64, + entries: Vec, + depth: usize, + backend: &mut dyn StorageBackend, + cache: &PageCache, + alloc: &mut PageAllocator, + freed: &mut Vec, +) -> Result> { + if depth > MAX_TREE_DEPTH { + bail_coded!( + ErrorCode::Int049, + format!("tree deeper than {MAX_TREE_DEPTH} at page_id={page_id}") + ); } - if leaves.is_empty() { - return build_btree(pending, backend, cache, alloc); - } - let mut infos: Vec = Vec::new(); - let mut pending = pending.into_iter().peekable(); - for (i, (page, first)) in leaves.iter().enumerate() { - let upper = leaves.get(i + 1).map(|(_, k)| k); - let mut batch = Vec::new(); - while let Some((key, _)) = pending.peek() { - if upper.is_some_and(|u| key >= u) { - break; + let page = cache.get_or_load(page_id, &*backend)?; + freed.push(page_id); + match page.first().copied() { + Some(PAGE_TYPE_LEAF) => { + let merged = merge_entries(decode_leaf(&page[..])?, entries)?; + let mut pieces = Vec::new(); + let mut prev_last: Option> = None; + for group in pack_leaves(merged)? { + let (Some((first, _)), Some((last, _))) = (group.first(), group.last()) else { + continue; + }; + let sep = match &prev_last { + Some(p) => Some(shortest_separator(p, first)?), + None => None, + }; + prev_last = Some(last.clone()); + let id = write_leaf(&group, backend, cache, alloc)?; + pieces.push(Piece { sep, id }); } - batch.extend(pending.next()); + Ok(pieces) } - if batch.is_empty() { - let last = leaf_last_key(&page[..])? - .ok_or_else(|| err_coded!(ErrorCode::Int049, "non-empty leaf without entries"))?; - let id = alloc.alloc()?; - alloc.write(backend, cache, id, (**page).clone())?; - infos.push(NodeInfo { - id, - first: first.clone(), - last, - }); - } else { - let old = decode_leaf(&page[..])?; - emit_leaves( - merge_entries(old, batch)?, - &mut infos, - backend, - cache, - alloc, - )?; + Some(PAGE_TYPE_INTERNAL) => { + let node = Internal::new(&page[..])?; + let count = node.count(); + // Route the entries: they are sorted, so each child takes a run. + let mut runs: Vec<(usize, Vec)> = Vec::new(); + let mut from = 0usize; + for entry in entries { + let c = node.route(&entry.0, from)?; + from = c; + match runs.last_mut() { + Some((last, run)) if *last == c => run.push(entry), + _ => runs.push((c, vec![entry])), + } + } + let mut elems: Vec<(Option>, u64)> = Vec::with_capacity(count + runs.len() + 1); + let mut runs = runs.into_iter().peekable(); + for i in 0..=count { + let sep_before = if i == 0 { + None + } else { + Some(node.sep(i - 1)?.to_vec()) + }; + let child = node.child(i)?; + if runs.peek().is_some_and(|(c, _)| *c == i) { + let (_, run) = runs + .next() + .ok_or_else(|| err_coded!(ErrorCode::Int049, "routed run missing"))?; + let pieces = insert_node(child, run, depth + 1, backend, cache, alloc, freed)?; + for (k, piece) in pieces.into_iter().enumerate() { + let sep = if k == 0 { + sep_before.clone() + } else { + piece.sep + }; + elems.push((sep, piece.id)); + } + } else { + elems.push((sep_before, child)); + } + } + write_internal_pieces(elems, backend, cache, alloc) } + _ => bail_coded!(ErrorCode::Stg013, page_id), } - build_internal_levels(infos, backend, cache, alloc) +} + +/// Insert sorted, distinct `entries` into the tree at `root`, copy-on-write +/// (spec §8.3): only the touched leaves and their paths to the root are +/// rewritten, at ids from `alloc`; every page they replace goes into `freed`. +/// Untouched subtrees are shared with the old tree, which stays readable. A +/// root split adds a level. Root 0 (no tree) is a bulk build. Returns the new +/// root. +pub fn cow_insert( + root: u64, + entries: Vec, + backend: &mut dyn StorageBackend, + cache: &PageCache, + alloc: &mut PageAllocator, + freed: &mut Vec, +) -> Result { + check_sorted(&entries)?; + if root == 0 { + return build_btree(entries, backend, cache, alloc); + } + if entries.is_empty() { + return Ok(root); + } + let mut pieces = insert_node(root, entries, 0, backend, cache, alloc, freed)?; + while pieces.len() > 1 { + let elems = pieces.into_iter().map(|p| (p.sep, p.id)).collect(); + pieces = write_internal_pieces(elems, backend, cache, alloc)?; + } + pieces + .pop() + .map(|p| p.id) + .ok_or_else(|| err_coded!(ErrorCode::Int049, "insert produced no root")) } // ─── Reading ───────────────────────────────────────────────────────────────── @@ -287,6 +444,7 @@ pub fn rebuild_btree_incremental( /// Collect the leaf pages of the tree at `root`, in key order, each checked by /// a full decode. Every node visited is also pushed onto `nodes_out` (when /// given), so a checkpoint can free the whole old tree. +#[cfg(test)] pub fn collect_leaf_pages( root: u64, backend: &dyn StorageBackend, @@ -313,9 +471,7 @@ pub fn collect_leaf_pages( } match page.first().copied() { Some(PAGE_TYPE_LEAF) => { - // Untouched leaves are copied and resealed, so damage the CRC - // cannot see must be caught here, not carried forward. - validate_leaf(&page[..])?; + crate::storage::node::validate_leaf(&page[..])?; leaves.push(page); } Some(PAGE_TYPE_INTERNAL) => { @@ -668,31 +824,6 @@ mod tests { (root, alloc.next_append()) } - fn rebuild_at( - leaves: Vec>>, - pending: Vec, - backend: &mut dyn StorageBackend, - cache: &PageCache, - start: u64, - ) -> (u64, u64) { - let mut alloc = PageAllocator::new(Vec::new(), start, 1); - let root = rebuild_btree_incremental(leaves, pending, backend, cache, &mut alloc).unwrap(); - (root, alloc.next_append()) - } - - fn build_then_incremental( - committed: &[Entry], - pending: &[Entry], - start: u64, - ) -> (MemoryBackend, PageCache, u64) { - let mut backend = MemoryBackend::new(); - let cache = PageCache::new(4096); - let (old_root, _) = build_at(committed.to_vec(), &mut backend, &cache, 2); - let leaves = collect_leaf_pages(old_root, &backend, &cache, None).unwrap(); - let (root, _) = rebuild_at(leaves, pending.to_vec(), &mut backend, &cache, start); - (backend, cache, root) - } - /// Stream equality, no empty leaf in a non-empty tree, and prefix scans /// that agree with the expected set. fn assert_tree_exact( @@ -883,157 +1014,6 @@ mod tests { assert_eq!(crate::error::MinigrafError::from(err).code(), "STG-013"); } - #[test] - fn incremental_without_pending_copies_leaves_verbatim() { - let mut rng = Rng(0x315); - let mut ctr = 0; - let committed = random_entries(&mut rng, 3000, &mut ctr); - let mut backend = MemoryBackend::new(); - let cache = PageCache::new(4096); - let (old_root, old_next) = build_at(committed.clone(), &mut backend, &cache, 2); - let old_leaves = collect_leaf_pages(old_root, &backend, &cache, None).unwrap(); - let (root, _) = rebuild_at( - old_leaves.clone(), - Vec::new(), - &mut backend, - &cache, - old_next, - ); - let new_leaves = collect_leaf_pages(root, &backend, &cache, None).unwrap(); - assert_eq!(new_leaves.len(), old_leaves.len(), "leaf count changed"); - for (o, n) in old_leaves.iter().zip(&new_leaves) { - assert!(o[..4] == n[..4], "leaf type/count changed"); - assert!( - o[PAGE_HEADER_SIZE..] == n[PAGE_HEADER_SIZE..], - "leaf body changed" - ); - } - assert_tree_exact(root, &backend, &cache, &committed, &mut rng); - } - - #[test] - fn incremental_matches_merge_random() { - let mut rng = Rng(0xC0FFEE); - let mut ctr = 0; - for _ in 0..40 { - let (nc, np) = (rng.below(4000), rng.below(300)); - let committed = random_entries(&mut rng, nc, &mut ctr); - let pending = random_entries(&mut rng, np, &mut ctr); - let (backend, cache, root) = build_then_incremental(&committed, &pending, 20_000); - let expected = sorted_union(&committed, &pending); - assert_tree_exact(root, &backend, &cache, &expected, &mut rng); - } - } - - #[test] - fn incremental_pending_outside_old_range_and_into_one_leaf() { - let mut rng = Rng(7); - let committed: Vec = (1000..3000).map(|n| entry(n, n)).collect(); - let pending = vec![entry(1, 1), entry(2, 2), entry(9_000, 9), entry(9_001, 9)]; - let (backend, cache, root) = build_then_incremental(&committed, &pending, 20_000); - assert_tree_exact( - root, - &backend, - &cache, - &sorted_union(&committed, &pending), - &mut rng, - ); - - // Committed 0, 10_000, …: every pending 0 < e < 10_000 routes to leaf 0, - // which must split into several balanced leaves. - let committed: Vec = (0..2000).map(|n| entry(n * 10_000, n)).collect(); - let pending: Vec = (1..3000).map(|n| entry(n, 100_000 + n)).collect(); - let (backend, cache, root) = build_then_incremental(&committed, &pending, 20_000); - assert_tree_exact( - root, - &backend, - &cache, - &sorted_union(&committed, &pending), - &mut rng, - ); - } - - #[test] - fn incremental_empty_old_tree_is_a_bulk_build() { - let mut rng = Rng(13); - let mut ctr = 0; - let pending = random_entries(&mut rng, 500, &mut ctr); - let (backend, cache, root) = build_then_incremental(&[], &pending, 20_000); - assert_tree_exact(root, &backend, &cache, &pending, &mut rng); - let (backend, cache, root) = build_then_incremental(&[], &[], 20_000); - assert_tree_exact(root, &backend, &cache, &[], &mut rng); - } - - #[test] - fn incremental_keeps_shared_entries_once_and_rejects_conflicts() { - let committed: Vec = (0..100).map(|n| entry(n, n)).collect(); - let (backend, cache, root) = build_then_incremental(&committed, &committed[10..20], 5000); - assert_tree_exact(root, &backend, &cache, &committed, &mut Rng(3)); - - let mut backend = MemoryBackend::new(); - let cache = PageCache::new(64); - let old = vec![(b"k".to_vec(), b"1".to_vec())]; - let (root, next) = build_at(old, &mut backend, &cache, 2); - let leaves = collect_leaf_pages(root, &backend, &cache, None).unwrap(); - let mut alloc = PageAllocator::new(Vec::new(), next, 1); - let conflict = vec![(b"k".to_vec(), b"2".to_vec())]; - let err = rebuild_btree_incremental(leaves, conflict, &mut backend, &cache, &mut alloc) - .unwrap_err(); - assert_eq!(crate::error::MinigrafError::from(err).code(), "INT-049"); - } - - #[test] - fn incremental_single_inserts_do_not_fragment_leaves() { - // One random insert per round, like one checkpoint per new fact: leaves - // must stay reasonably full instead of leaving a remainder each time. - let mut rng = Rng(23); - let mut ctr = 0; - let mut backend = MemoryBackend::new(); - let cache = PageCache::new(4096); - let mut expected = random_entries(&mut rng, 3000, &mut ctr); - let (mut root, _) = build_at(expected.clone(), &mut backend, &cache, 2); - let bulk = collect_leaf_pages(root, &backend, &cache, None) - .unwrap() - .len(); - let mut start = 10_000; - for _ in 0..600 { - let pending = random_entries(&mut rng, 1, &mut ctr); - let leaves = collect_leaf_pages(root, &backend, &cache, None).unwrap(); - let (r, next) = rebuild_at(leaves, pending.clone(), &mut backend, &cache, start); - root = r; - start = next; - expected = sorted_union(&expected, &pending); - } - assert_tree_exact(root, &backend, &cache, &expected, &mut rng); - let leaves = collect_leaf_pages(root, &backend, &cache, None) - .unwrap() - .len(); - assert!( - leaves <= bulk * 5 / 2, - "leaf count grew from {bulk} to {leaves}" - ); - } - - #[test] - fn incremental_repeated_rounds() { - let mut rng = Rng(19); - let mut ctr = 0; - let mut backend = MemoryBackend::new(); - let cache = PageCache::new(4096); - let mut expected = random_entries(&mut rng, 1500, &mut ctr); - let (mut root, mut start) = build_at(expected.clone(), &mut backend, &cache, 2); - for _ in 0..30 { - let n = 1 + rng.below(150); - let pending = random_entries(&mut rng, n, &mut ctr); - let leaves = collect_leaf_pages(root, &backend, &cache, None).unwrap(); - let (r, next) = rebuild_at(leaves, pending.clone(), &mut backend, &cache, start); - root = r; - start = next; - expected = sorted_union(&expected, &pending); - assert_tree_exact(root, &backend, &cache, &expected, &mut rng); - } - } - #[test] fn dict_shaped_entries_with_values_round_trip() { let mut backend = MemoryBackend::new(); @@ -1320,4 +1300,181 @@ mod tests { let (root, _) = build_at(entries.clone(), &mut backend, &cache, 2); assert!(stream_all_entries(root, &backend, &cache).unwrap() == entries); } + + // ─── Copy-on-write insert ──────────────────────────────────────────────── + + /// Every node id of the tree at `root`. + fn node_ids(root: u64, backend: &dyn StorageBackend, cache: &PageCache) -> BTreeSet { + let mut nodes = Vec::new(); + collect_leaf_pages(root, backend, cache, Some(&mut nodes)).unwrap(); + nodes.into_iter().collect() + } + + use std::collections::BTreeSet; + + /// Build `committed`, then insert `pending` copy-on-write, and check: the + /// result is the sorted union; the old root still streams `committed` + /// unchanged; `freed` is exactly the old nodes the new tree no longer uses; + /// and the new tree writes no page of the old tree. + fn cow_check(committed: &[Entry], pending: &[Entry], rng: &mut Rng) { + let mut backend = MemoryBackend::new(); + let cache = PageCache::new(4096); + let (old_root, next) = build_at(committed.to_vec(), &mut backend, &cache, 2); + let old_nodes = node_ids(old_root, &backend, &cache); + let mut alloc = PageAllocator::new(Vec::new(), next, 2); + let mut freed = Vec::new(); + let root = cow_insert( + old_root, + pending.to_vec(), + &mut backend, + &cache, + &mut alloc, + &mut freed, + ) + .unwrap(); + let expected = sorted_union(committed, pending); + assert_tree_exact(root, &backend, &cache, &expected, rng); + assert!( + stream_all_entries(old_root, &backend, &cache).unwrap() == committed, + "the old tree is unchanged" + ); + let new_nodes = node_ids(root, &backend, &cache); + let freed: BTreeSet = freed.into_iter().collect(); + let dropped: BTreeSet = old_nodes.difference(&new_nodes).copied().collect(); + if pending.is_empty() { + assert_eq!(root, old_root); + assert!(freed.is_empty()); + } else { + assert!(freed == dropped, "freed is exactly the replaced old nodes"); + } + for id in new_nodes.difference(&old_nodes) { + assert!(*id >= next, "new nodes are new pages"); + } + } + + #[test] + fn cow_insert_matches_merge_random() { + let mut rng = Rng(0xC0FE); + let mut ctr = 0; + for _ in 0..40 { + let (nc, np) = (rng.below(6000), rng.below(400)); + let committed = random_entries(&mut rng, nc, &mut ctr); + let pending = random_entries(&mut rng, np, &mut ctr); + cow_check(&committed, &pending, &mut rng); + } + } + + #[test] + fn cow_insert_edges_splits_and_root_growth() { + let mut rng = Rng(77); + // Below the first key and above the last. + let committed: Vec = (1000..3000).map(|n| entry(n, n)).collect(); + let pending = vec![entry(1, 1), entry(2, 2), entry(9_000, 9), entry(9_001, 9)]; + cow_check(&committed, &pending, &mut rng); + // Many entries into one leaf: it splits into balanced leaves. + let committed: Vec = (0..2000).map(|n| entry(n * 10_000, n)).collect(); + let pending: Vec = (1..3000).map(|n| entry(n, 100_000 + n)).collect(); + cow_check(&committed, &pending, &mut rng); + // A single-leaf root grows to depth 3; an empty tree is a bulk build. + let pending: Vec = (0..60_000).map(|n| entry(n * 3, n)).collect(); + cow_check(&[entry(1, 1)], &pending, &mut rng); + cow_check(&[], &pending[..10], &mut rng); + cow_check(&committed, &[], &mut rng); + // Shared entries are kept once. + cow_check(&committed, &committed[5..50], &mut rng); + } + + #[test] + fn cow_insert_into_root_zero_is_a_bulk_build() { + let mut backend = MemoryBackend::new(); + let cache = PageCache::new(64); + let mut alloc = PageAllocator::new(Vec::new(), 2, 1); + let mut freed = Vec::new(); + let entries: Vec = (0..500).map(|n| entry(n, n)).collect(); + let root = cow_insert( + 0, + entries.clone(), + &mut backend, + &cache, + &mut alloc, + &mut freed, + ) + .unwrap(); + assert!(freed.is_empty()); + assert!(stream_all_entries(root, &backend, &cache).unwrap() == entries); + } + + #[test] + fn cow_insert_large_separators_split_internal_nodes() { + // DICT-shaped keys of about 1 KB: internal nodes hold few separators + // and split often. + let key = |n: u64| { + let mut k = vec![0x03]; + k.extend(format!("{n:08}").into_bytes()); + k.extend(vec![b'k'; 1000]); + k + }; + let mut rng = Rng(5); + let committed: Vec = (0..300).map(|n| (key(n * 2), vec![1])).collect(); + let pending: Vec = (0..300).map(|n| (key(n * 2 + 1), vec![2])).collect(); + cow_check(&committed, &pending, &mut rng); + } + + #[test] + fn cow_single_inserts_do_not_fragment_leaves() { + let mut rng = Rng(23); + let mut ctr = 0; + let mut backend = MemoryBackend::new(); + let cache = PageCache::new(4096); + let mut expected = random_entries(&mut rng, 3000, &mut ctr); + let (mut root, next) = build_at(expected.clone(), &mut backend, &cache, 2); + let bulk = collect_leaf_pages(root, &backend, &cache, None) + .unwrap() + .len(); + let mut alloc = PageAllocator::new(Vec::new(), next, 2); + for _ in 0..600 { + let pending = random_entries(&mut rng, 1, &mut ctr); + let mut freed = Vec::new(); + root = cow_insert( + root, + pending.clone(), + &mut backend, + &cache, + &mut alloc, + &mut freed, + ) + .unwrap(); + expected = sorted_union(&expected, &pending); + } + assert_tree_exact(root, &backend, &cache, &expected, &mut rng); + let leaves = collect_leaf_pages(root, &backend, &cache, None) + .unwrap() + .len(); + assert!( + leaves <= bulk * 5 / 2, + "leaf count grew from {bulk} to {leaves}" + ); + } + + #[test] + fn cow_insert_writes_only_the_touched_paths() { + // One entry into a depth-3 tree writes one leaf and two internal nodes. + let mut backend = MemoryBackend::new(); + let cache = PageCache::new(4096); + let committed: Vec = (0..60_000).map(|n| entry(n * 2, n)).collect(); + let (root, next) = build_at(committed, &mut backend, &cache, 2); + let mut alloc = PageAllocator::new(Vec::new(), next, 2); + let mut freed = Vec::new(); + cow_insert( + root, + vec![entry(77_777, 1)], + &mut backend, + &cache, + &mut alloc, + &mut freed, + ) + .unwrap(); + assert_eq!(alloc.next_append() - next, 3, "leaf + 2 internal nodes"); + assert_eq!(freed.len(), 3); + } } diff --git a/src/storage/dict.rs b/src/storage/dict.rs index ab0cda7c4f..ab2d7b2b78 100644 --- a/src/storage/dict.rs +++ b/src/storage/dict.rs @@ -448,17 +448,14 @@ mod tests { let start = backend.page_count().unwrap().max(2); let mut alloc = PageAllocator::new(Vec::new(), start, 1); let encoded = enc.finish(&mut alloc, backend, cache).unwrap(); - let leaves = if root == 0 { - Vec::new() - } else { - btree::collect_leaf_pages(root, &*backend, cache, None).unwrap() - }; - let new_root = btree::rebuild_btree_incremental( - leaves, + let mut freed = Vec::new(); + let new_root = btree::cow_insert( + root, encoded.dict.clone(), backend, cache, &mut alloc, + &mut freed, ) .unwrap(); (new_root, encoded) diff --git a/src/storage/freelist.rs b/src/storage/freelist.rs index 7c1a84ac1a..94a5cd1cb9 100644 --- a/src/storage/freelist.rs +++ b/src/storage/freelist.rs @@ -2,8 +2,10 @@ //! //! A singly linked chain of 0x81 pages holding ids of pages the active meta does //! not reference. Body after the common header: `next u64`, then `count` page -//! ids (u64 each). This version writes the whole chain afresh on every -//! checkpoint; the format is the same one copy-on-write push/pop will use. +//! ids (u64 each). A checkpoint reads chain pages only as it needs free ids and +//! pushes new head pages in front of the unread tail +//! ([`crate::storage::page::PageAllocator`]), so its cost is set by the pages it +//! allocates and frees, never by the length of the list. use crate::error::{ErrorCode, bail_coded, err_coded}; use crate::storage::PAGE_SIZE; @@ -17,26 +19,31 @@ const IDS_OFFSET: usize = PAGE_HEADER_SIZE + 8; /// Page ids per free-list page: (4096 − 24 − 8) / 8. pub const IDS_PER_PAGE: usize = (PAGE_SIZE - IDS_OFFSET) / 8; -/// Write `ids` as a new chain and return `(head, chain_page_ids)`. -/// -/// Chain pages come from `alloc`, so the chain never lists its own pages. -/// An empty list writes nothing and returns head 0. -pub fn write_chain( +/// Write `ids` into the chain pages `pages` (already allocated, in order), the +/// last one linking to `tail` (0: end of chain). `pages` must hold every id. +pub fn write_pages( ids: &[u64], - alloc: &mut PageAllocator, + pages: &[u64], + tail: u64, + alloc: &PageAllocator, backend: &mut dyn StorageBackend, cache: &PageCache, -) -> Result<(u64, Vec)> { - let chunks: Vec<&[u64]> = ids.chunks(IDS_PER_PAGE).collect(); - let mut page_ids = Vec::with_capacity(chunks.len()); - for _ in &chunks { - page_ids.push(alloc.alloc()?); +) -> Result<()> { + if ids.len().div_ceil(IDS_PER_PAGE) > pages.len() { + bail_coded!(ErrorCode::Int049, "free-list pages too few for their ids"); } - for (i, chunk) in chunks.iter().enumerate() { + for (i, &page_id) in pages.iter().enumerate() { + let chunk = ids + .get(i.saturating_mul(IDS_PER_PAGE)..) + .unwrap_or(&[]) + .iter() + .take(IDS_PER_PAGE) + .copied() + .collect::>(); let count = u16::try_from(chunk.len()) .map_err(|_| err_coded!(ErrorCode::Int048, "free-list page count exceeds u16"))?; let mut page = new_page(PAGE_TYPE_FREELIST, count); - let next = page_ids.get(i.saturating_add(1)).copied().unwrap_or(0); + let next = pages.get(i.saturating_add(1)).copied().unwrap_or(tail); if let Some(dst) = page.get_mut(NEXT_OFFSET..IDS_OFFSET) { dst.copy_from_slice(&next.to_le_bytes()); } @@ -46,12 +53,57 @@ pub fn write_chain( dst.copy_from_slice(&id.to_le_bytes()); } } - let page_id = *page_ids - .get(i) - .ok_or_else(|| err_coded!(ErrorCode::Int049, "free-list page id missing"))?; alloc.write(backend, cache, page_id, page)?; } - Ok((page_ids.first().copied().unwrap_or(0), page_ids)) + Ok(()) +} + +/// Write `ids` as a new chain and return `(head, chain_page_ids)`. +/// +/// Chain pages come from `alloc`, so the chain never lists its own pages. +/// An empty list writes nothing and returns head 0. +pub fn write_chain( + ids: &[u64], + alloc: &mut PageAllocator, + backend: &mut dyn StorageBackend, + cache: &PageCache, +) -> Result<(u64, Vec)> { + let mut pages = Vec::with_capacity(ids.len().div_ceil(IDS_PER_PAGE)); + for _ in 0..ids.len().div_ceil(IDS_PER_PAGE) { + pages.push(alloc.alloc(&*backend, cache)?); + } + write_pages(ids, &pages, 0, alloc, backend, cache)?; + Ok((pages.first().copied().unwrap_or(0), pages)) +} + +/// Read chain page `id`: its free ids and the next page id. A page id or free +/// id below 2 or at or past `page_count` is STG-035. +pub fn read_page( + id: u64, + backend: &dyn StorageBackend, + cache: &PageCache, + page_count: u64, +) -> Result<(Vec, u64)> { + if id < 2 || id >= page_count { + bail_coded!(ErrorCode::Stg035, format!("chain page {id} out of range")); + } + let page = cache.get_or_load(id, backend)?; + if page.first().copied() != Some(PAGE_TYPE_FREELIST) { + bail_coded!(ErrorCode::Stg013, id); + } + let count = usize::from(crate::storage::page::page_count_field(&page)?); + if count > IDS_PER_PAGE { + bail_coded!(ErrorCode::Stg035, format!("page {id} count {count}")); + } + let mut ids = Vec::with_capacity(count); + for j in 0..count { + let free = read_u64(&page, IDS_OFFSET.saturating_add(j.saturating_mul(8)))?; + if free < 2 || free >= page_count { + bail_coded!(ErrorCode::Stg035, format!("free id {free} out of range")); + } + ids.push(free); + } + Ok((ids, read_u64(&page, NEXT_OFFSET)?)) } /// Read the chain at `head` and return `(free_ids, chain_page_ids)`. @@ -68,31 +120,14 @@ pub fn read_chain( let mut chain = Vec::new(); let mut next = head; while next != 0 { - if next < 2 || next >= page_count { - bail_coded!(ErrorCode::Stg035, format!("chain page {next} out of range")); - } // A chain longer than the file has pages must loop. if u64::try_from(chain.len()).unwrap_or(u64::MAX) >= page_count { bail_coded!(ErrorCode::Stg035, "chain loops"); } - let page = cache.get_or_load(next, backend)?; - if page.first().copied() != Some(PAGE_TYPE_FREELIST) { - bail_coded!(ErrorCode::Stg013, next); - } + let (page_ids, after) = read_page(next, backend, cache, page_count)?; chain.push(next); - let count = usize::from(crate::storage::page::page_count_field(&page)?); - if count > IDS_PER_PAGE { - bail_coded!(ErrorCode::Stg035, format!("page {next} count {count}")); - } - for j in 0..count { - let off = IDS_OFFSET.saturating_add(j.saturating_mul(8)); - let id = read_u64(&page, off)?; - if id < 2 || id >= page_count { - bail_coded!(ErrorCode::Stg035, format!("free id {id} out of range")); - } - ids.push(id); - } - next = read_u64(&page, NEXT_OFFSET)?; + ids.extend(page_ids); + next = after; } Ok((ids, chain)) } @@ -152,4 +187,113 @@ mod tests { let err = read_chain(head, &backend, &cache, alloc.next_append()).unwrap_err(); assert_eq!(crate::error::MinigrafError::from(err).code(), "STG-035"); } + + /// Pop `take` ids from a chain of `n` free ids, free `freed` more pages, + /// and push. Space is conserved, nothing freed is handed out, unread chain + /// pages are shared, and the count matches the new chain. + fn pop_then_push(n: u64, take: usize, freed_n: u64) { + use std::collections::BTreeSet; + let mut backend = MemoryBackend::new(); + let cache = PageCache::new(0); + // Free ids 2..2+n; old chain pages appended after them, in generation 1. + let old_ids: Vec = (2..2 + n).collect(); + let mut alloc1 = PageAllocator::new(Vec::new(), 2 + n, 1); + let (head, old_chain) = write_chain(&old_ids, &mut alloc1, &mut backend, &cache).unwrap(); + let page_count = alloc1.next_append(); + // Pages "freed" by generation 2: ids past the file, standing for tree pages. + let freed: Vec = (page_count..page_count + freed_n).collect(); + let bound = page_count + freed_n; + + let mut alloc = PageAllocator::from_chain(head, n, bound, 2); + let handed: Vec = (0..take) + .map(|_| alloc.alloc(&backend, &cache).unwrap()) + .collect(); + let (new_head, count) = alloc + .finish_free_list(freed.clone(), &mut backend, &cache) + .unwrap(); + let (new_ids, new_chain) = + read_chain(new_head, &backend, &cache, alloc.next_append()).unwrap(); + + assert_eq!(count, new_ids.len() as u64, "count matches the chain"); + let set = |v: &[u64]| v.iter().copied().collect::>(); + let (h, ni, nc) = (set(&handed), set(&new_ids), set(&new_chain)); + assert_eq!(h.len(), handed.len(), "no id handed out twice"); + assert_eq!(ni.len(), new_ids.len(), "no duplicate free id"); + assert!(h.is_disjoint(&ni) && h.is_disjoint(&nc) && ni.is_disjoint(&nc)); + assert!( + h.is_disjoint(&set(&freed)), + "freed pages are not reused this generation" + ); + let before: BTreeSet = set(&old_ids) + .union(&set(&old_chain)) + .chain(freed.iter()) + .copied() + .collect(); + let appended: BTreeSet = (bound..alloc.next_append()).collect(); + let after: BTreeSet = h.union(&ni).chain(nc.iter()).copied().collect(); + let expected: BTreeSet = before.union(&appended).copied().collect(); + assert!(after == expected, "every page is accounted for"); + // Chain pages never read are shared unchanged (same ids, generation 1). + let read_pages = take.div_ceil(IDS_PER_PAGE).max(usize::from(take > 0)); + for &id in old_chain.iter().skip(read_pages + 1) { + assert!(nc.contains(&id), "unread tail page is shared"); + let p = backend.read_page(id).unwrap(); + assert_eq!(crate::storage::page::page_generation(&p).unwrap(), 1); + } + } + + #[test] + fn lazy_pop_and_push_conserve_space() { + for (n, take, freed) in [ + (0, 0, 0), + (0, 5, 3), + (1, 1, 0), + (10, 3, 2), + (508, 508, 0), + (509, 508, 1), + (1200, 600, 10), + (1200, 1300, 700), + (5000, 1, 0), + (5000, 2000, 2000), + ] { + pop_then_push(n, take, freed); + } + } + + #[test] + fn untouched_chain_reads_no_page() { + let mut backend = MemoryBackend::new(); + let cache = PageCache::new(0); + let ids: Vec = (2..3002).collect(); + let mut a1 = PageAllocator::new(Vec::new(), 3002, 1); + let (head, chain) = write_chain(&ids, &mut a1, &mut backend, &cache).unwrap(); + // No allocation and nothing freed: the list is unchanged. + let mut alloc = PageAllocator::from_chain(head, 3000, a1.next_append(), 2); + let (h, count) = alloc + .finish_free_list(Vec::new(), &mut backend, &cache) + .unwrap(); + assert_eq!((h, count), (head, 3000)); + assert_eq!(alloc.next_append(), a1.next_append(), "nothing written"); + assert_eq!(chain.len(), 6); + } + + #[test] + fn wrong_count_or_looping_chain_is_stg_035() { + let mut backend = MemoryBackend::new(); + let cache = PageCache::new(0); + let mut a1 = PageAllocator::new(Vec::new(), 12, 1); + let (head, _) = write_chain( + &(2..12).collect::>(), + &mut a1, + &mut backend, + &cache, + ) + .unwrap(); + let mut alloc = PageAllocator::from_chain(head, 3, a1.next_append(), 2); + let err = (0..20) + .map(|_| alloc.alloc(&backend, &cache)) + .find_map(Result::err) + .unwrap(); + assert_eq!(crate::error::MinigrafError::from(err).code(), "STG-035"); + } } diff --git a/src/storage/node.rs b/src/storage/node.rs index d3faccd298..66eaa99772 100644 --- a/src/storage/node.rs +++ b/src/storage/node.rs @@ -241,6 +241,7 @@ pub fn decode_leaf(page: &[u8]) -> Result> { /// Check a leaf's structure without copying keys: every entry and the restart /// array stay inside the page, restart offsets match, and no entry shares more /// than its predecessor's length. Key order is not checked (decode does that). +#[cfg(test)] pub fn validate_leaf(page: &[u8]) -> Result<()> { if page.first().copied() != Some(PAGE_TYPE_LEAF) { bail_coded!(ErrorCode::Int049, "not a leaf page"); @@ -277,24 +278,6 @@ pub fn validate_leaf(page: &[u8]) -> Result<()> { Ok(()) } -/// The last key of a leaf, decoded from its last restart point; `None` if empty. -pub fn leaf_last_key(page: &[u8]) -> Result>> { - let count = node_count(page)?; - if count == 0 { - return Ok(None); - } - let restarts = count.div_ceil(RESTART_INTERVAL); - let end = PAGE_SIZE - .checked_sub(2 * restarts) - .ok_or_else(|| invalid("restart array overflows the leaf"))?; - let mut pos = get_u16(page, end + 2 * (restarts - 1))?; - let mut key: Vec = Vec::new(); - for _ in (restarts - 1) * RESTART_INTERVAL..count { - key = read_leaf_entry(page, &mut pos, &key, end)?.0; - } - Ok(Some(key)) -} - /// The value stored under `key` in a leaf, found by binary search over the /// restart points and a scan of at most [`RESTART_INTERVAL`] entries. pub fn leaf_get(page: &[u8], key: &[u8]) -> Result>> { @@ -333,16 +316,6 @@ pub fn leaf_get(page: &[u8], key: &[u8]) -> Result>> { Ok(None) } -/// The first key of a leaf, or `None` if it is empty. -pub fn leaf_first_key(page: &[u8]) -> Result>> { - if node_count(page)? == 0 { - return Ok(None); - } - let mut pos = PAGE_HEADER_SIZE; - let (k, _) = read_leaf_entry(page, &mut pos, &[], PAGE_SIZE)?; - Ok(Some(k)) -} - // ─── Internal nodes ────────────────────────────────────────────────────────── /// The shortest `s` with `left_last < s <= right_first`: the shortest prefix of @@ -458,6 +431,7 @@ impl<'a> Internal<'a> { } /// All children in key order, `rightmost_child` last. + #[cfg(test)] pub fn children(&self) -> Result> { (0..=self.count).map(|i| self.child(i)).collect() } @@ -549,14 +523,6 @@ mod tests { let page = encode_leaf(entries).unwrap(); assert_eq!(page.len(), PAGE_SIZE); assert_eq!(decode_leaf(&page).unwrap(), entries, "round trip"); - assert_eq!( - leaf_first_key(&page).unwrap(), - entries.first().map(|(k, _)| k.clone()) - ); - assert_eq!( - leaf_last_key(&page).unwrap(), - entries.last().map(|(k, _)| k.clone()) - ); validate_leaf(&page).unwrap(); for (k, v) in entries { assert_eq!(leaf_get(&page, k).unwrap().as_ref(), Some(v), "present key"); @@ -591,7 +557,6 @@ mod tests { let page = encode_leaf(&[]).unwrap(); assert!(decode_leaf(&page).unwrap().is_empty()); assert_eq!(leaf_get(&page, b"x").unwrap(), None); - assert_eq!(leaf_first_key(&page).unwrap(), None); } #[test] diff --git a/src/storage/page.rs b/src/storage/page.rs index 5e4640bacc..c60b3d2ae5 100644 --- a/src/storage/page.rs +++ b/src/storage/page.rs @@ -156,23 +156,57 @@ pub fn new_page(page_type: u8, count: u16) -> Vec { /// Hands out page ids for one checkpoint generation and writes sealed pages. /// -/// `alloc` takes the lowest id from the active meta's free list first, then -/// appends at the high-water mark; `alloc_append` always appends. Every id it -/// hands out is unreferenced by the active meta (spec §8.1), so writing it can -/// never damage the committed state. +/// `alloc` takes an id from the active meta's free list first, then appends at +/// the high-water mark; `alloc_append` always appends. Every id it hands out is +/// unreferenced by the active meta (spec §8.1), so writing it can never damage +/// the committed state. +/// +/// The free list comes either as a list of ids ([`PageAllocator::new`]) or as +/// the meta's on-disk chain ([`PageAllocator::from_chain`]), whose pages are +/// read one at a time, only when another id is needed (spec §4.4). A chain page +/// that has been read is replaced: [`PageAllocator::finish_free_list`] pushes it, +/// its unused ids and every freed page as new head pages in front of the unread +/// tail, which is shared unchanged. pub struct PageAllocator { - /// Free ids, highest first, so `pop` yields the lowest. + /// Free ids ready to hand out, in reverse order (`pop` yields the next). free: Vec, + /// First chain page not read yet (0: none). + chain_next: u64, + /// Ids in the chain pages not read yet. + chain_tail_count: u64, + /// Chain pages read so far; each is free once the new meta commits. + chain_read: Vec, + /// Bound for chain page ids (the active meta's `page_count`). + chain_bound: u64, next_append: u64, generation: u64, } impl PageAllocator { - /// An allocator over `free` (any order) that appends from `next_append`. + /// An allocator over `free` (any order, lowest handed out first) that + /// appends from `next_append`. pub fn new(mut free: Vec, next_append: u64, generation: u64) -> Self { free.sort_unstable_by(|a, b| b.cmp(a)); PageAllocator { free, + chain_next: 0, + chain_tail_count: 0, + chain_read: Vec::new(), + chain_bound: next_append, + next_append, + generation, + } + } + + /// An allocator over the free-list chain at `head` holding `count` ids, in a + /// file whose committed `page_count` is `next_append`. + pub fn from_chain(head: u64, count: u64, next_append: u64, generation: u64) -> Self { + PageAllocator { + free: Vec::new(), + chain_next: head, + chain_tail_count: count, + chain_read: Vec::new(), + chain_bound: next_append, next_append, generation, } @@ -189,11 +223,34 @@ impl PageAllocator { self.next_append } - /// A free id if any is left, otherwise a new one at the end. - pub fn alloc(&mut self) -> Result { - match self.free.pop() { - Some(id) => Ok(id), - None => self.alloc_append(), + /// A free id if any is left, otherwise a new one at the end. Reads the next + /// free-list chain page when the ids read so far are used up. + pub fn alloc( + &mut self, + backend: &dyn crate::storage::StorageBackend, + cache: &crate::storage::cache::PageCache, + ) -> Result { + loop { + if let Some(id) = self.free.pop() { + return Ok(id); + } + if self.chain_next == 0 { + return self.alloc_append(); + } + if u64::try_from(self.chain_read.len()).unwrap_or(u64::MAX) >= self.chain_bound { + bail_coded!(ErrorCode::Stg035, "chain loops"); + } + let id = self.chain_next; + let (mut ids, next) = + crate::storage::freelist::read_page(id, backend, cache, self.chain_bound)?; + self.chain_tail_count = self + .chain_tail_count + .checked_sub(u64::try_from(ids.len()).unwrap_or(u64::MAX)) + .ok_or_else(|| err_coded!(ErrorCode::Stg035, "freelist_count too small"))?; + self.chain_read.push(id); + self.chain_next = next; + ids.reverse(); + self.free = ids; } } @@ -206,13 +263,58 @@ impl PageAllocator { Ok(id) } - /// Free ids not handed out, lowest first. + /// Free ids not handed out, in hand-out order. Chain pages not read yet are + /// not included. + #[cfg(test)] pub fn take_unused_free(&mut self) -> Vec { let mut v = std::mem::take(&mut self.free); v.reverse(); v } + /// Write the new free list and return `(head, count)`. + /// + /// The list is `freed` (pages the new meta no longer references), every + /// chain page read and the ids read but not handed out, as new head pages in + /// front of the unread tail. The head pages themselves are allocated here, + /// which may read more of the chain, so this repeats until the page count + /// covers the ids. Nothing listed here is handed out in this generation. + pub fn finish_free_list( + &mut self, + freed: Vec, + backend: &mut dyn crate::storage::StorageBackend, + cache: &crate::storage::cache::PageCache, + ) -> Result<(u64, u64)> { + use crate::storage::freelist::IDS_PER_PAGE; + let mut pages: Vec = Vec::new(); + let ids = loop { + let mut ids = freed.clone(); + ids.extend(self.chain_read.iter().copied()); + ids.extend(self.free.iter().rev().copied()); + // Use the first `k` allocated pages for the chain and list the rest + // as free: the smallest `k` whose pages hold every listed id. + let n = pages.len(); + let mut k = 0usize; + while k <= n && (ids.len() + n - k).div_ceil(IDS_PER_PAGE) > k { + k += 1; + } + if k > n { + pages.push(self.alloc(&*backend, cache)?); + continue; + } + ids.extend(pages.get(k..).unwrap_or(&[]).iter().copied()); + pages.truncate(k); + break ids; + }; + let tail = self.chain_next; + let count = self + .chain_tail_count + .checked_add(u64::try_from(ids.len()).unwrap_or(u64::MAX)) + .ok_or_else(|| err_coded!(ErrorCode::Int048, "free-list count overflow"))?; + crate::storage::freelist::write_pages(&ids, &pages, tail, self, backend, cache)?; + Ok((pages.first().copied().unwrap_or(tail), count)) + } + /// Seal `page` as `page_id` in this generation, write it, and put it in the /// cache so that a reused id never serves stale bytes. pub fn write( @@ -298,12 +400,14 @@ mod tests { #[test] fn allocator_takes_lowest_free_then_appends() { + let b = crate::storage::backend::MemoryBackend::new(); + let c = crate::storage::cache::PageCache::new(0); let mut a = PageAllocator::new(vec![9, 4, 7], 20, 2); - assert_eq!(a.alloc().unwrap(), 4); + assert_eq!(a.alloc(&b, &c).unwrap(), 4); assert_eq!(a.alloc_append().unwrap(), 20); - assert_eq!(a.alloc().unwrap(), 7); + assert_eq!(a.alloc(&b, &c).unwrap(), 7); assert_eq!(a.take_unused_free(), vec![9]); - assert_eq!(a.alloc().unwrap(), 21); + assert_eq!(a.alloc(&b, &c).unwrap(), 21); assert_eq!(a.next_append(), 22); assert_eq!(a.generation(), 2); } diff --git a/src/storage/persistent_facts.rs b/src/storage/persistent_facts.rs index 5cf4f35655..b81d4f5bb7 100644 --- a/src/storage/persistent_facts.rs +++ b/src/storage/persistent_facts.rs @@ -9,7 +9,7 @@ use crate::error::{ErrorCode, bail_coded, err_coded}; use crate::graph::FactStorage; use crate::graph::types::Fact; -use crate::storage::btree::{build_btree, collect_leaf_pages, rebuild_btree_incremental}; +use crate::storage::btree::{build_btree, cow_insert}; use crate::storage::cache::PageCache; use crate::storage::dict::{DictReader, Encoded, Encoder}; use crate::storage::meta::{MetaPage, SlotState, slot_page}; @@ -283,14 +283,16 @@ impl PersistentFactStorage { } } - /// Commit pending facts as the next generation (spec §8.3, full-rewrite form). + /// Commit pending facts as the next generation, copy-on-write (spec §8.3). /// - /// New long values are appended to fresh value pages. The five trees are - /// rebuilt into pages the active meta does not reference (its free list - /// first, then appended). Every page of the old trees and the old free-list - /// chain joins the new free list. After a sync, the new meta goes to the - /// other slot and is synced: the only commit point. A failure at any step - /// leaves the active meta and all it references untouched. + /// New long values are appended to fresh value pages. Each of the five trees + /// gets a copy-on-write batch insert: only touched leaves and their paths to + /// the root are rewritten, at pages the active meta does not reference (its + /// free list, read lazily, then appended). The replaced pages and the free-list + /// pages read are pushed onto the free list in front of its unread tail. After + /// a sync, the new meta goes to the other slot and is synced: the only commit + /// point. A failure at any step leaves the active meta and all it references + /// untouched. The pages written depend on the change, not on the graph size. pub fn save(&mut self) -> Result<()> { if !self.dirty { return Ok(()); @@ -300,26 +302,8 @@ impl PersistentFactStorage { let next_gen = m.next_generation()?; let mut backend = self.lock()?; - - // Snapshot the old trees (their leaves, and every node for freeing) and - // the old free list. Nothing here is written. - let mut freed: Vec = Vec::new(); - let mut old_leaves = Vec::with_capacity(5); - for root in m.tree_roots() { - old_leaves.push(if root == 0 { - Vec::new() - } else { - collect_leaf_pages(root, &*backend, &self.page_cache, Some(&mut freed))? - }); - } - let (old_free, old_chain) = if m.freelist_head != 0 { - freelist::read_chain(m.freelist_head, &*backend, &self.page_cache, m.page_count)? - } else { - (Vec::new(), Vec::new()) - }; - freed.extend(old_chain); - - let mut alloc = PageAllocator::new(old_free, m.page_count, next_gen); + let mut alloc = + PageAllocator::from_chain(m.freelist_head, m.freelist_count, m.page_count, next_gen); let encoded = encode( &pending_facts, &m, @@ -331,28 +315,21 @@ impl PersistentFactStorage { u64::try_from(encoded.index[0].len()).map_err(|_| err_coded!(ErrorCode::Stg024))?; let (next_eid, next_iid) = (encoded.next_eid, encoded.next_iid); let Encoded { index, dict, .. } = encoded; - let mut roots = [0u64; 5]; - for ((root, leaves), entries) in roots - .iter_mut() - .zip(old_leaves) - .zip(index.into_iter().chain([dict])) - { - *root = rebuild_btree_incremental( - leaves, + let mut freed: Vec = Vec::new(); + let mut roots = m.tree_roots(); + for (root, entries) in roots.iter_mut().zip(index.into_iter().chain([dict])) { + *root = cow_insert( + *root, entries, &mut *backend, &self.page_cache, &mut alloc, + &mut freed, )?; } let [eavt_root, aevt_root, avet_root, vaet_root, dict_root] = roots; - - // New free list: what is left of the old one, plus everything the old - // meta referenced that the new one does not. - let mut new_free = alloc.take_unused_free(); - new_free.extend(freed); - let (freelist_head, _) = - freelist::write_chain(&new_free, &mut alloc, &mut *backend, &self.page_cache)?; + let (freelist_head, freelist_count) = + alloc.finish_free_list(freed, &mut *backend, &self.page_cache)?; backend.sync()?; @@ -372,8 +349,7 @@ impl PersistentFactStorage { next_eid, next_iid, freelist_head, - freelist_count: u64::try_from(new_free.len()) - .map_err(|_| err_coded!(ErrorCode::Int048, "free-list length"))?, + freelist_count, ..m }; backend.write_page(slot_page(next_gen), &new_meta.encode())?; @@ -560,6 +536,7 @@ mod tests { use crate::graph::types::Value; use crate::storage::backend::FaultInjectingBackend; use crate::storage::backend::MemoryBackend; + use crate::storage::btree::collect_leaf_pages; use crate::storage::keys::Index; use crate::storage::reader::all_entries_as_facts; use std::collections::BTreeSet; @@ -1531,4 +1508,115 @@ mod tests { assert_indexes_exact(&pfs.meta(), &mem); assert_space_accounted(&pfs.meta(), &mem); } + + // ── checkpoint cost (spec §11, #434) ──────────────────────────────────── + + /// Depth of the tree at `root` (a lone leaf is depth 1). + fn depth(root: u64, backend: &dyn StorageBackend) -> u64 { + let cache = PageCache::new(0); + let mut d = 1; + let mut id = root; + loop { + let p = cache.get_or_load(id, backend).unwrap(); + if p[0] != page::PAGE_TYPE_INTERNAL { + return d; + } + id = crate::storage::node::Internal::new(&p[..]) + .unwrap() + .child(0) + .unwrap(); + d += 1; + } + } + + /// Entity `i` of the cost tests: spaced so that new UUIDs can fall between. + fn spaced(i: u64) -> Uuid { + Uuid::from_u128(u128::from(i) << 20) + } + + /// Pages written by a checkpoint that adds `k` facts to a graph of `n`, and + /// the summed depth of the five trees. New facts get new entities; with + /// `sequential` their UUIDs and values follow the existing ones, otherwise + /// they are random. + fn checkpoint_writes(n: u64, k: u64, sequential: bool) -> (usize, u64) { + let rec = RecordingBackend { + inner: MemoryBackend::new(), + written: Arc::new(Mutex::new(Vec::new())), + }; + let log = rec.written.clone(); + let mem = rec.inner.clone(); + let mut pfs = PersistentFactStorage::new(rec, 256).unwrap(); + for chunk in (0..n).collect::>().chunks(5000) { + let batch = chunk + .iter() + .map(|&i| (spaced(i), ":n".to_string(), Value::Integer(i as i64 * 1000))) + .collect(); + pfs.storage().transact(batch, None).unwrap(); + } + pfs.mark_dirty(); + pfs.save().unwrap(); + let mut rng: u64 = 0x9E37_79B9_7F4A_7C15; + let batch = (0..k) + .map(|i| { + rng ^= rng << 13; + rng ^= rng >> 7; + rng ^= rng << 17; + if sequential { + ( + spaced(n + i), + ":n".to_string(), + Value::Integer((n + i) as i64 * 1000), + ) + } else { + // Between existing UUIDs and values, so every tree but the + // ones keyed by new ids takes random-position inserts. + let r = rng % n; + ( + Uuid::from_u128(u128::from(r) << 20 | 1), + ":n".to_string(), + Value::Integer(r as i64 * 1000 + 1), + ) + } + }) + .collect(); + pfs.storage().transact(batch, None).unwrap(); + pfs.mark_dirty(); + log.lock().unwrap().clear(); + pfs.save().unwrap(); + let written = log.lock().unwrap().len(); + let m = pfs.meta(); + let depths = m + .tree_roots() + .iter() + .filter(|&&r| r != 0) + .map(|&r| depth(r, &mem)) + .sum(); + assert_space_accounted(&m, &mem); + (written, depths) + } + + /// #434 acceptance: a checkpoint's cost depends on the change, not on the + /// graph. With keys at the right edge, 10x more facts costs at most the + /// extra tree depth; with random keys, at most one path per new entry per + /// tree. + #[test] + fn checkpoint_cost_does_not_grow_with_the_graph() { + for k in [1u64, 100] { + let (small, d_small) = checkpoint_writes(10_000, k, true); + let (large, d_large) = checkpoint_writes(100_000, k, true); + assert!( + large <= small + (d_large - d_small) as usize + 2, + "k={k}: {small} pages at 10k, {large} at 100k" + ); + let (random, d) = checkpoint_writes(100_000, k, false); + // Five trees, one path each per new entry, plus a value-free + // allowance for free-list pages and the meta. + assert!( + random <= (k * d) as usize + 8, + "k={k}: {random} pages for random keys (depth sum {d})" + ); + } + let (one, _) = checkpoint_writes(100_000, 1, true); + assert!(one <= 20, "one fact at 100k writes {one} pages"); + } } diff --git a/tests/concurrency_test.rs b/tests/concurrency_test.rs index 84ae34ca2b..7c183d2751 100644 --- a/tests/concurrency_test.rs +++ b/tests/concurrency_test.rs @@ -487,3 +487,77 @@ fn stress_open_write_loop_nightly() { h.join().expect("thread panicked in nightly stress"); } } + +/// Copy-on-write checkpoints (#434, spec §8.1): queries running while the +/// writer transacts and checkpoints never read a page a checkpoint is +/// rewriting. Every read succeeds and sees a fact count that only grows. +#[test] +fn queries_during_copy_on_write_checkpoints_stay_consistent() { + let dir = tempfile::tempdir().unwrap(); + let path = dir.path().join("cow.graph"); + let db = Arc::new(Minigraf::open(&path).unwrap()); + let mut seed = String::from("(transact ["); + for i in 0..2_000 { + seed.push_str(&format!("[:e{i} :n {i}] ")); + } + seed.push_str("])"); + db.execute(&seed).unwrap(); + db.checkpoint().unwrap(); + + let done = Arc::new(std::sync::atomic::AtomicBool::new(false)); + let readers: Vec<_> = (0..4) + .map(|r| { + let db = Arc::clone(&db); + let done = Arc::clone(&done); + thread::spawn(move || { + let mut last = 0i64; + let mut reads = 0u64; + while !done.load(std::sync::atomic::Ordering::Relaxed) || reads == 0 { + let q = if r % 2 == 0 { + "(query [:find (count ?e) :where [?e :n ?v]])".to_string() + } else { + format!("(query [:find ?v :where [:e{} :n ?v]])", reads % 2_000) + }; + let res = db.execute(&q).expect("a read during checkpoints fails"); + if r % 2 == 0 { + let QueryResult::QueryResults { results, .. } = res else { + panic!("expected query results"); + }; + let n = match &results[0][0] { + minigraf::Value::Integer(n) => *n, + _ => panic!("expected a count"), + }; + assert!(n >= last, "the fact count never goes backwards"); + last = n; + } + reads += 1; + } + reads + }) + }) + .collect(); + + for round in 0..40 { + let mut tx = String::from("(transact ["); + for j in 0..25 { + tx.push_str(&format!("[:w{round}_{j} :n {}] ", 10_000 + round * 25 + j)); + } + tx.push_str("])"); + db.execute(&tx).unwrap(); + db.checkpoint().unwrap(); + } + done.store(true, std::sync::atomic::Ordering::Relaxed); + for r in readers { + assert!(r.join().unwrap() > 0, "every reader ran"); + } + let QueryResult::QueryResults { results, .. } = db + .execute("(query [:find (count ?e) :where [?e :n ?v]])") + .unwrap() + else { + panic!("expected query results"); + }; + assert!( + matches!(results[0][0], minigraf::Value::Integer(3_000)), + "2,000 seed facts plus 40 rounds of 25" + ); +}