Architecture

The central decision: the file is the WAL

Most databases pair an in-place B-tree with a separate write-ahead log: changes are first appended to the log, then later folded back into the tree in place. Arkeion collapses those two structures into one. It is a copy-on-write (CoW) B-tree living in an append-only file. A data page, once written, is never modified. Every write transaction appends the new and modified pages to the end of the file, followed by a small commit page that records the roots of the new version.

That one decision is the whole engine. The four properties people usually bolt on afterwards all fall out of it for free:

Property	Why it’s automatic
Time-travel	Old pages are immutable, so every past version is still on disk. Reading version N means resolving commit N and reading from its root — O(log n), no log replay.
Branching	A branch is just a named ref pointing at a commit, exactly like git. Two branches physically share every page they haven’t changed.
Hash chain	Each commit page carries the SHA-256 of its own contents plus the chained hash of the previous commit. The chain exists from the first byte, not added later.
Crash recovery	A commit counts only if its commit page is intact. After a crash, a half-written tail is simply ignored. “Replay” is a forward scan, nothing to undo.
Lock-free reads	A reader pins one commit and reads immutable pages. It never coordinates with the writer.

The price is that the file grows with its history. That’s paid back by vacuum, which compacts the file under a retention policy (see File format).

Copy-on-write, worked through

Suppose a small tree whose root points at two leaves, A and B, and you update one row that lives in B. Arkeion does not touch B. It writes a new leaf B′ with the change, then a new root that points at the unchanged A and the new B′, and appends both — followed by the commit page for the new version. A is shared by both versions; B stays on disk untouched. The old root is still valid, so the previous version remains fully readable.

Layers and modules

The engine is a strict stack: dependencies point only downward, and no lower layer ever knows about a higher one. That’s what keeps each piece testable in isolation.

Module	Responsibility	Key types
format	Constants, magic numbers, layout offsets. No logic.	PAGE_SIZE, PageId, PageType
io	Portable positional read/write (Unix read_at, Windows seek_read).	DbFile
crypto	trait CryptoProvider { seal(page), open(page) }. Implementations: Aes256GcmProvider, PlainProvider (integrity via truncated SHA-256).	CryptoProvider, Key
pager	Page append, cached immutable reads (Arc<PageBuf>), A/B meta slots, integrity validation.	Pager, PageBuf
btree	CoW B-tree: get / insert / delete / scan over byte keys, addressed by PageId. Overflow for large values.	Tree, Cursor
commit	Builds the commit page (roots, hashes, nonce counter), the fdatasync protocol, recovery scan, chain verification.	CommitHeader, ChainVerifier
tx	Snapshot (a read, pins a commit) and WriteTx (single, serialised by a Mutex).	Snapshot, WriteTx
record	Memcomparable key encoding and the compact row format.	Value, RowCodec, KeyCodec
catalog	Table schema in the data tree (branches with the data); refs and the history index in the meta tree (global).	Catalog, TableDef
sql	Hand-written lexer and recursive-descent parser. No dependencies.	Token, Stmt, Expr
exec	Planner (full scan + filter) and a row-by-row iterator executor.	Plan, Executor
branch	Diff between branches (skipping physically shared subtrees) and a row-level 3-way merge.	Diff, MergeReport
api	The ergonomic public facade, in the rusqlite style. The only re-exported module.	Database, Connection

The two trees

Every commit references two roots, and they behave differently on purpose:

• Data tree (data_root) — the catalogue and the rows. It follows its branch: a commit on a branch builds on that branch’s previous data root, so a migration or a write on one branch is invisible to the others.
• Meta tree (meta_root) — branch refs plus the history index (version → commit, timestamp → version). It is global and linear: every commit, from any branch, builds on the meta tree of the previous global commit. That’s why refs and the version index are a single shared source of truth that never diverges between branches.

Keeping the schema in the data tree is the reason branching is honest: because the schema travels with the branch, you can evolve the shape of your data on a branch and merge it deliberately, not have it leak across every branch at once.

Concurrency model

• Readers — Connection::snapshot() pins a commit page and reads only immutable pages through a shared cache. Any number of readers run concurrently, none of them sharing a lock with the writer. Isolation is snapshot isolation.
• Writer — exactly one, serialised by a Mutex<Writer> at the Database level. Writes are therefore serialisable by construction. Throughput is capped at a single writer thread today; group commit (batching concurrent fsyncs) is a planned optimisation, not yet shipped.
• Multi-process — an advisory file lock is taken on open(), for a single writer process. Arbitrating writers across processes is out of scope for now.

Write flow

A write turns into pages in memory, appends them, appends one commit page, and reaches durability with a single fdatasync:

execute("UPDATE …")
  → sql::parse → exec::plan
  → WriteTx: btree CoW produces new pages in memory
  → pager: append the new pages, then the commit page
  → commit: one fdatasync                     ← the single durability point
  → meta slot A/B updated (lazy — a boot hint, off the critical path)

There is deliberately no fsync between the data pages and the commit page. Per-page integrity tags make any torn or missing page unreadable, and recovery stops at the first unreadable page — so a half-written commit is simply never adopted. One barrier per commit is all it takes.

Time-travel read flow

Reading the past is not replay; it is a lookup and an ordinary scan from an old root:

query("SELECT … AS OF VERSION 42")
  → meta tree: history[42] → PageId of commit 42
  → Snapshot{commit 42} → btree::scan from data_root(42)