Apache CouchDB
An append-only document database: B-tree indexes, MVCC revisions, masterless replication.
CouchDB stores JSON documents in append-only copy-on-write B-trees — nothing is ever edited in place, so readers never block writers. Every document carries a _rev revision; updates create new versions that compaction later prunes. Databases synchronize bidirectionally with an incremental, conflict-aware replication protocol.
Append-only B-trees
Updates write new nodes and a new root; old structure stays intact until compaction. Crash safety falls out of the design — a torn write leaves the previous root valid.
MVCC revisions
Every update bumps _rev. Concurrent writers create conflicting branches that the replication protocol surfaces as real conflicts — apps resolve, CouchDB never silently picks.
Incremental MapReduce views
Views compute over the B-tree and update incrementally as the tree grows — indexes that cost O(changes) to maintain, not O(database).
Eventual, conflict-aware sync
Replication copies document revisions between databases, detects concurrent edits, and materializes conflicts for application resolution.
Append-only changes everything
Because the storage is copy-on-write, a crash can only ever leave a partially written new tree — the previous root is untouched. Compare with in-place engines that need WAL replay to guarantee the same invariant.
Revisions make concurrency explicit: two clients updating the same document produce two branches with a shared ancestor. Reads specify which revision to trust; conflicts are first-class documents, not silent overwrites.
PUT /db/order-42
{ "customer": "ann", "total": 42 }
→ 201 { "rev": "1-abc123" }
PUT /db/order-42
{ "customer": "ann", "total": 45 }
→ 409 (needs ?rev=1-abc123)
Views that grow with the tree
MapReduce views index documents into B-tree-backed key/value rows. Because documents are immutable, a view only recomputes for changed document IDs — incremental by construction.
Diagrams
[caption] Crash safety by construction: torn writes leave the old root valid.
Updates append new tree nodes and swap the root pointer; compaction reclaims old versions. Replication syncs revisions and surfaces conflicts.
Append-only tree size over document versions, before and after compaction reclaims superseded nodes.
[caption] Illustrative tree for 48K document versions — compaction rewrites live data into a fresh tree and drops the rest.
Append-only tree size over document versions, before and after compaction reclaims superseded nodes.