# PG2 copy-on-write page-index experiment

The `ratdb-page-lab` crate demonstrates incremental, atomic writes over the existing exclusive `Storage` adapter. A batch replacing 16 spaced values among 100,000 keys wrote **69,696 bytes** with PG2 and **4,800,128 bytes** with v1. Each used three durability barriers. The CLI, server, document store, backups, and alpha downloads continue to use v1. PG2 has no migration path from existing v1 documents.

## What the index can store

PG2 is a two-level direct-address index over unsigned keys 0 through 119,999 and exactly 32-byte values. Divide the key by 120 to find a bucket and use its remainder to find a value within that bucket. A zero directory entry or a clear occupancy bit indicates absence. Numeric order equals the byte order of the four-byte big-endian benchmark keys. Sparse or arbitrary string keys would need another index design. This restriction is central to the measurement.

An embedded caller explicitly creates an empty object or opens an existing PG2 object. `get` reads at most one 4 KiB leaf. `scan` visits ascending keys and can stop early. `apply` handles at most 1,024 sorted distinct inserts, replacements or deletions. A successful nonempty batch publishes one generation, including a delete of an absent key. Out-of-range keys, duplicate/unsorted batches and capacity exhaustion from generation counters return an error before writing. Failed storage I/O during a commit poisons the handle. Drop and reopen it to reconcile the observed generation and values.

```rust
use ratdb_core::{MemoryStorage, Result};
use ratdb_page_lab::{Change, PageIndex};

fn example() -> Result<()> {
    let mut index = PageIndex::create(MemoryStorage::default())?;
    index.apply(&[Change { key: 42, value: Some([7; 32]) }])?;
    let mut reopened = PageIndex::open(index.into_storage())?;
    assert_eq!(reopened.get(42)?, Some([7; 32]));
    Ok(())
}
```

The library uses `no_std` and `alloc`. Opening holds one 4 KiB directory plus one leaf scratch buffer during validation. A healthy commit holds the current and candidate directory plus a leaf scratch buffer, totaling 12 KiB of page buffers, excluding vector/allocator metadata, caller-owned changes, stack and adapter memory. Each lookup allocates a fresh leaf buffer when its bucket has a version. File length remains fixed at 8,208,384 bytes (2,004 logical pages). Reusing alternating slots avoids free lists, replay logs and background reclamation. Deletion leaves older copies on media. Once touched, an empty bucket still costs a page read during validation.

## Experimental physical format

Pages are 4,096 bytes. All numeric fields are unsigned little-endian. Every referenced page ends with a four-byte CRC-32/ISO-HDLC over bytes 0–4091. Directory and leaf magics identify this specific experimental layout. Unused bytes start at zero. This format has no long-term compatibility promise.

| Physical page | Byte layout |
|---|---|
| 0 and 1 | Each holds a separate 32-byte publication record at offset zero. Bytes 0–7 are `RAT2PUB1`, bytes 8–15 contain the generation, bytes 16–19 the directory CRC, bytes 20–27 reserved, bytes 28–31 the CRC of bytes 0–27. Remaining page bytes are unused. |
| 2 and 3 | Directory for generation G lives at page `2 + (G % 2)`. Bytes 0–7 are `RAT2DIR1`, 8–15 contain G, 16–4015 contain 1,000 four-byte leaf versions, the remainder before the CRC is reserved. Version zero means this bucket has never been written. |
| 4 through 2003 | Bucket B and positive local version V live at page `4 + 2*B + (V % 2)`. Bytes 0–7 are `RAT2LEF1`, 8–11 contain B, 12–15 contain V, 16–30 contain 120 occupancy bits (least significant bit first), byte 31 is reserved, 32–3871 contain 120 fixed values. |

The directory generation must match the chosen publication record. The directory checksum must match its stored CRC and the value in the publication record. Each referenced leaf must pass its own CRC and match the bucket and exact local version recorded in the directory. A single bucket can receive at most 4,294,967,295 published versions over its lifetime. The directory has a 64-bit generation. The current prototype requires a target with at least 32-bit pointer width.

## Publication and interruption

The exclusive adapter must supply exact reads and writes, zero-filled growth on creation, persistence ordering at successful syncs, and independent write ranges. A failed write or sync may persist none, part or all of its data. A device that loses previously synced data or damages unrelated ranges violates this model. The two publication records occupy separate logical pages on one storage device.

| Step | Action | Recovery following interruption |
|---|---|---|
| Creation | Require zero length, resize, write empty generation 1 directory, sync. Write record 0 and sync, then record 1 and sync. | No complete publication record means ordinary open refuses the object. One valid record can expose the empty database. Explicit create refuses nonempty remnants. |
| Reconcile | If recovery saw one missing/invalid/older record, write the chosen record into that slot and sync it. | The sole witness of the chosen state is preserved until the repair is durable. This protects the next commit during successive interruptions. Opening alone performs no repair write. |
| Prepare | For each affected bucket read and check its active leaf (or start empty), modify it, write the inactive version. Write the alternate directory. Sync all of them. | The previous directory and all leaves reachable from it remain intact. Readers choose the previous generation. |
| Publish first record | Write record 0 pointing to the new directory and sync. | A valid new record selects the new state. A torn/old first record leaves record 1 selecting the old state. The new directory and its leaves were synced before this step. |
| Publish second record | Write record 1 pointing to the same directory and sync, then acknowledge. | Record 0 already durably selects the complete new generation. After success both records identify it. A caller missing its acknowledgement must reconcile. |

Recovery accepts matching records, one valid record, or two records where record 0 is exactly one generation newer than record 1. Other combinations fail as ambiguous. A read error on either locator is an I/O failure. An unreadable or invalid *selected* root or leaf returns an error even if a prior image might be readable. Recovery validates all reachable pages before returning a handle. No salvage, memory backstop, secure deletion, encryption or multi-device redundancy is provided. Both witnesses can be lost together. CRCs can collide and cannot establish authenticity or distinguish a coherent replay of an entire older medium.

## Measurement and verification

```sh
cargo run --locked --offline --release -p ratdb-page-lab --example compare
cargo test --locked --offline -p ratdb-page-lab --all-targets
cargo clippy --locked --offline -p ratdb-page-lab --all-targets -- -D warnings
cargo check --locked --offline -p ratdb-page-lab --lib --target thumbv7em-none-eabi
```

The example loads both engines in batches of up to 1,024, reads 256 deterministic keys, changes 16 evenly spaced keys in a single commit and reopens and checks **all 100,000 keys and values** against their expected ordered model. Counts are at the adapter boundary. MemoryStorage's sync is a no-op. Run times below are single release runs; they exclude physical media flush latency and filesystem writeback.

| Platform and engine | Mean point read | Bytes/read | Batch time | Batch bytes | Syncs | Full reopen time | Full reopen bytes | Logical file bytes |
|---|---:|---:|---:|---:|---:|---:|---:|---:|
| Windows x86-64 GNU v1 | 124.7 µs | 37,012 | 38,404 µs | 4,800,128 | 3 | 16,017 µs | 4,800,128 | 9,600,128 |
| Windows x86-64 GNU PG2 | 6.2 µs | 4,096 | 202 µs | 69,696 | 3 | 5,146 µs | 3,420,224 | 8,208,384 |
| Linux x86-64 WSL v1 | 166.4 µs | 37,012 | 42,713 µs | 4,800,128 | 3 | 23,487 µs | 4,800,128 | 9,600,128 |
| Linux x86-64 WSL PG2 | 6.4 µs | 4,096 | 223 µs | 69,696 | 3 | 5,499 µs | 3,420,224 | 8,208,384 |

The 16 changed values total 512 bytes. PG2 wrote 16 leaves plus one directory and two 32-byte records. Replacements clustered within one leaf need only one leaf write. The v1 configuration was sized for this exact workload. PG2 reserves its entire key range even when empty. Cache behavior, production JSON sizes, key distribution, filesystem allocation, flash erase blocks and controller write amplification need separate measurements.

Six model/fault unit tests plus one real host-file integration test cover initialization, mixed changes, strict input rejection, an ordered 1,200-step model, read errors, altered payloads, stale CRC-valid pages, conflicting/missing records, v1 refusal, single-record erasure, exclusive locking and reopen. Fault injection exercises all eight write/sync boundaries in a two-leaf batch with 37 persistence shapes, including every publication-record prefix length, scattered writes, no persistence, and full persistence on a reported failure. Tests also interrupt a repairing commit, reopen, interrupt a subsequent commit again and compare the complete visible state. These are deterministic simulations and host-file tests. Machine power cuts and controller faults remain untested.

Production adoption requires arbitrary binary/document keys, a realistic growth and migration policy, a downgrade/restore drill, operating-system I/O benchmarks and real power-cut qualification. An application should keep its existing databases on v1.