Immutable versioned data files

Under the Hood: Copy-on-Write (CoW) & Persistent Data Structures

Traditional database engines (like MySQL InnoDB) overwrite pages in-place. If the server crashes mid-write, the page is corrupt (torn write), requiring complex Doublewrite Buffers and WAL replay. Copy-on-write storage engines (LMDB, CouchDB, ZFS) never overwrite live pages on disk. Instead, every mutation writes a new version of the page and swings an atomic root pointer. Table formats such as Apache Iceberg apply the same idea at file granularity (immutable data files plus a new snapshot metadata file), not as a page tree.

Copy-on-Write B-Tree Pointer Swapping

Why Immutability Eliminates Concurrency Locks

• Lock-Free Readers: Readers take a reference to the active root pointer at transaction start. Because pages are immutable, readers traverse the tree without page locks or latches and without risk of reading inconsistent or partial writes (in LMDB a reader still registers its snapshot in a reader table so the writer does not reuse pages it needs).
• Single Atomic Root Swap: When a writer finishes constructing the new branch, it must persist the new pages before publishing durable commit metadata that identifies the new root. Implementations commonly use checksummed or redundant metadata pages, a WAL, and explicit flush ordering so recovery can select a complete generation after a crash; a CPU-atomic pointer store alone is not a durable commit.
• Instant Time Travel & Snapshots: Creating a snapshot is free: simply preserve the root pointer of that version. Older versions are reclaimed by background garbage collection only when all referencing reader transactions terminate.

Worked example: one update in a copy-on-write B+tree

A tree of depth 3 with 4 KB pages (root, internal, leaf). Updating one key:

1. Write a new leaf containing the change (4 KB).
2. Write a new internal page whose pointer now targets the new leaf (4 KB).
3. Write a new root pointing at the new internal page (4 KB).
4. Flush those pages, then write and flush a meta page: txn_id = 1042, root = page 9913, checksum.

That is 12 KB of page writes plus a meta page for a 100-byte change, the price of never overwriting. LMDB keeps two meta pages and alternates between them; on startup it picks the valid one with the highest transaction id, so a crash during step 4 simply leaves the previous version in force. Pages from transaction 1041 are freed only when no active reader still uses that snapshot.

Table formats do the same thing at file granularity

In Apache Iceberg, a commit writes new data files, new manifest files and a new table metadata file, then atomically swaps the catalog's pointer from v41.metadata.json to v42.metadata.json using compare-and-swap. If another writer committed first, the swap fails and the writer retries against the new base (optimistic concurrency). Old snapshots remain queryable until expired.

Comparison

Failure modes

• Snapshot pinning: a forgotten read transaction stops reclamation; monitor oldest reader age.
• Metadata explosion: frequent tiny commits create thousands of small files and snapshots; table formats need regular compaction and snapshot expiry.
• Single writer: LMDB serializes writers; high write concurrency needs a different engine.