File format

A format designed from scratch, explicitly independent of SQLite: neither the page layout, the record encoding, nor the journal model derive from it. This page is the on-disk spec — what a byte on disk means, and why the layout gives Arkeion its two headline properties: a single fdatasync per commit, and a history you can prove.

Conventions: header integers are little-endian; B-tree keys use a memcomparable big-endian encoding (so byte order equals key order). The recommended file extension is .arkeion, but it is not enforced — the engine opens any path, zero-config.

Global layout

A database is one file of fixed 4096-byte pages. Only three regions are special; everything else is appended and never overwritten.

page 0        File header      (immutable after creation)
page 1        Meta slot A      (alternating rewrite, LMDB-style)
page 2        Meta slot B
page 3…       Append-only zone: data pages and commit pages

On-disk page — 4096 bytes

PAGE_SIZE = 4096 matches a common OS page and logical sector, which minimises torn writes and aligns the encryption unit. PageId = u64, and a page’s byte offset is simply id × 4096.

Every page has the same three-band layout, encrypted or not — the cryptographic reserve (28 B, 0.7%) is always paid, in exchange for a B-tree that is entirely encryption-agnostic.

0..12    nonce   encrypted: 96-bit GCM counter        · plaintext: zeros
12..28   tag     encrypted: GCM tag, AAD = page_id    · plaintext: SHA-256(LE(page_id) ‖ body)[0..16]
28..4096 body    encrypted: ciphertext of the body    · plaintext: the body as-is

The tag binds the content to its page_id: a page relocated to another offset is detected as corruption, not accepted as valid data in the wrong place. Without encryption the nonce must be zero (this is checked). Integrity is always verified on read, in both modes. With encryption on, every page is encrypted except the header and meta slots — and those hold no user data, only magics, pointers and versions (not even table names sit in plaintext).

Page identification

Data pages carry their type in the first body byte:

Type	Value	Content
B-tree leaf	0x01	Key→value cells
B-tree internal	0x02	Key→child cells
Overflow	0x03	Continuation of large values

Structural pages are identified by an 8-byte magic in body[0..8] — no collision is possible, since no data-type byte equals 0x41 ('A'):

Page	Magic	Position
Header	"ARKEION1"	page 0
Meta slot	"ARKMETA1"	pages 1–2
Commit	"ARKCMT01"	append zone

File header — body of page 0

0..8     magic            "ARKEION1"
8..12    format_version   u32 = 1
12..16   page_size        u32 = 4096
16..20   flags            u32   bit0 = encryption enabled
20..36   file_id          [16]  random at creation (seed of the genesis chain)
36..52   kdf_salt         [16]  reserved (raw 32-byte key today, no KDF)
52..     reserved         zeros

Meta slot — body of pages 1 and 2

0..8     magic              "ARKMETA1"
8..16    version            u64   version of the last commit reflected
16..24   last_commit_page   u64
24..32   n_pages            u64   file length (in pages) at that commit

The writer alternates A/B. On open, the engine takes the valid slot (tag integrity) with the highest version, then does a forward scan from n_pages in case commits landed after the slot was last updated — the slot update is lazy, deliberately kept off the durability critical path.

Commit page — body, type 0x04

0..8      magic           "ARKCMT01"
8..12     flags           u32   bit0 = compaction checkpoint (vacuum)
12..16    reserved        u32
16..24    version         u64   global monotonic, starts at 1
24..32    parent_page     u64   parent commit ON THE BRANCH (0 = genesis)
32..40    prev_page       u64   previous commit GLOBALLY (0 = genesis)
40..48    timestamp_ms    u64   wall clock, informational (version is authoritative)
48..56    data_root       u64   root of the branch's data tree
56..64    meta_root       u64   root of the global meta tree
64..72    nonce_counter   u64   next GCM counter after this commit
72..80    pages_written   u64   pages added by this commit
80..144   branch          [64]  UTF-8 branch name, zero-padded (max 64 B)
144..176  content_hash    [32]  SHA-256 of the PLAINTEXT bodies written by the commit, in order
176..208  prev_chain      [32]  chain_hash of the previous global commit
208..240  chain_hash      [32]  see below
240..     reserved        zeros

Each commit closes a hash chain over the global order of all commits, across every branch:

chain_hash = SHA-256( prev_chain ‖ content_hash ‖ LE(version) ‖ LE(timestamp_ms)
                      ‖ LE(data_root) ‖ LE(meta_root) ‖ branch )
genesis:     prev_chain = SHA-256( "ARKEION1" ‖ file_id )

Tampering with any past write, on any branch, breaks the chain from that point forward. A commit with flags.checkpoint = 1 is written by vacuum: its prev_chain carries the head chain_hash of the truncated history, so the chain stays continuous and verifiable even though the old pages are gone.

B-tree pages

leaf (0x01):     [type u8][flags u8][ncells u16] · [plen varint][prefix]? · cells · pointers
                 flags bit0 = COMPRESSED PREFIX: a [plen varint][prefix] shared by every key
                   follows the header, and each cell stores only the SUFFIX key[plen..];
                   full key = prefix ++ suffix. Without the bit: empty prefix, cell = whole key.
                 cell: [cell-flags u8][klen|slen varint][key|suffix][vlen varint][val]
                 cell-flags bit0 = overflow: [...][total len varint][first overflow u64]
                 (a value pushing the cell past 1280 B goes to overflow; key max 1024 B)
internal (0x02): [type][flags][ncells u16][rightmost u64] · cells: [klen varint][key][child u64]
                 cell.key = exclusive upper bound of its child
overflow (0x03): [type][flags][len u16][next u64][bytes…]

Each node ends with an array of cell pointers — one u16 LE per cell, growing from the end of the node toward the content — so descent, get and scans do in-page binary search without materialising the node, and appending the maximum key stays O(1). Cost: 2 B per cell.

Prefix compression in leaves. Keys in a leaf usually share a long prefix — postings for one term ([0x03, fts_id, 0x00, term_id]), entries of one index ([0x02, index_id]). Storing that prefix once per page instead of once per cell shrinks every index (it is a big part of why full-text came in below SQLite’s FTS5), with no change to the logical model: hot-path comparisons strip the target’s prefix and compare suffixes zero-copy; only the scan cursor rebuilds the full key. The append cursor appends a suffix when the key shares the prefix, so the active rightmost leaf stays compressed with O(1) appends, and older pages are read the same way.

Invariants checked on decode: keys are non-empty and strictly increasing within a node. delete does not rebalance underfull nodes — it only drops empty ones; vacuum rebalances on rewrite.

Key spaces

The catalogue stores a schema version with each table. The logical schema has grown v7 (CHECK constraints) → v8 (full-text) → v9 (vector) → v10 (vector re-rank) — each step adds key spaces, so the on-disk format_version (page 0) stays at 1. This is the canonical progression the SQL, full-text and vector docs refer to.

Data tree (data_root — forks with the branch)

[0x00, 0x01, table_name UTF-8]              → {table_id u32, schema}   catalogue
[0x00, 0x02, table_id BE]                   → next_rowid u64           rowid counter
[enc_oint(table_id), enc_oint(rowid)]       → record (row)
[0x02, index_id BE, value*, rowid u64 BE]   → secondary index entry

enc_oint is an order-preserving, self-delimiting, variable-length i64: a one-byte header encodes the sign and the number of significant bytes, so small magnitudes take ~2 B while the B-tree’s (table_id, rowid) order is preserved exactly. The row key needs no namespace byte — table_id ≥ 1 gives an enc_oint header of 0x80+, disjoint from 0x00 (catalogue) and 0x02 (index), so a key self-identifies from its first byte. Index entries keep a fixed rowid u64 BE as a trailing suffix after the variable-length value.

The schema lives in the data tree on purpose: a migration on a branch changes the schema only on that branch.

Meta tree (meta_root — global, linear, never forks)

[0x01, branch_name]                → {head_version u64, head_page u64}    refs
[0x02, version BE]                 → {commit_page u64, ts_ms u64, branch}  history index
[0x03, ts_ms BE, version BE]       → ∅                                     AS OF TIMESTAMP

Record (row)

[ncols varint][tag u8 × ncols][payloads in order]

tags:  0 NULL · 1 FALSE · 2 TRUE · 3 INTEGER (zigzag varint)
       4 REAL (f64 LE, 8 B) · 5 TEXT (varint len + UTF-8) · 6 BLOB (varint len + bytes)

Missing trailing columns read as NULL — which is what lets ALTER TABLE ADD COLUMN work without rewriting a single existing row.

Commit and recovery protocol

A write, from the single writer:

1. new pages (copy-on-write)  → append
2. commit page                → append
3. fdatasync                  ← the durability point — exactly one
4. alternating meta slot      → write in place (lazy hint; no fsync)

One fdatasync per commit, with no barrier between the data pages and the commit page. The per-page integrity tag makes any partially-written or unwritten page unreadable; recovery scans in order and stops at the first unreadable page. Because the data pages are appended before the commit page, a half-written commit is never adopted — only a commit whose pages are all readable (the fdatasync ran to completion) becomes the head. Dropping the second barrier is worth roughly 2–2.5× the durable-write rate versus a SQLite rollback journal, on par with WAL, while keeping full single-file durability.

Open and recovery:

1. Validate the header (magic, format version, flags).
2. Read meta A and B → candidate = the valid one with the highest version. Both corrupt → full scan.
3. Validate the candidate commit page (tag + magic + optional chain).
4. Scan forward from n_pages: each further valid commit page advances the head.
5. A broken tail (pages no valid commit covers) is ignored.

Step 5 is the “WAL replay”: there is no redo and no undo, only discarding what was never confirmed.

Vacuum (compaction)

vacuum(retention) rewrites the live versions into a temporary file according to the policy — KeepAll | KeepLast(u64) | KeepSince(SystemTime) — writes a checkpoint commit that chains onto the truncated history, then does an atomic fsync + rename over the original. It doubles as the key-rotation mechanism: everything is rewritten under the new key.