How the append-only btree works (2010)

Original Article ↗ Hacker News Discussion ↗

Append-only and copy-on-write B‑tree designs promise simple crash recovery, cheap snapshots, and strong read concurrency by treating the database itself as a log and never mutating pages in place. Commenters weigh these benefits against heavy write amplification, garbage page buildup, and the need for complex compaction or free‑page management, comparing approaches such as traditional write‑ahead logging, LMDB’s CoW implementation, ZFS’s intent log, and log‑structured or buffered tree variants. The exchange highlights how storage hardware characteristics (SSDs, raw flash, zoned devices) and workload patterns (read‑ vs write‑heavy, multi-threaded access) strongly influence whether immutable tree structures are practical in real systems.

Append-only vs mutable/WAL performance

  • Several commenters argue append-only B-trees are too inefficient for general use due to heavy write amplification and per-operation snapshots.
  • Others counter that on media where sequential writes are cheaper than random writes, log-structured or append-only layouts can be faster, and “write-in-place” on SSDs is largely illusory.
  • Traditional databases often use write-ahead logs (WAL) or undo logs, writing data twice, but can mitigate this with separate hardware for log vs data.
  • Benchmarks from LMDB are cited as evidence that carefully designed copy-on-write (CoW) B-trees can match or beat WAL-based systems, with a size-dependent break-even point.

Immutability, concurrency, and snapshots

  • Immutable/CoW trees naturally support multiple concurrent readers without locks and offer cheap snapshots and clones.
  • They simplify reasoning about correctness and concurrency but make write paths more complex and costly.
  • Single-writer designs are common; meta-page contention is a bottleneck for concurrent writers.

Garbage, compaction, and free-space management

  • Append-only and immutable B+trees create many obsolete pages. Techniques discussed:
    • Tracking in-use pages per transaction and reclaiming when no transactions reference them.
    • Maintaining a free-page list via appended “free list” pages and updating a meta page.
    • Using two fixed-location meta pages that alternate roles to avoid scanning from the end of the file.
  • Purely append-only designs can end up with ~99% obsolete pages in practice; LMDB moved to CoW with page reuse instead of pure append-only.
  • Some see extra “garbage” as aligning with flash wear-leveling; others stress minimizing garbage production despite append-only behavior.

Hardware and filesystem context

  • Raw flash, zoned NVMe, and SMR HDDs are highlighted as environments that effectively enforce append-only or zoned write patterns.
  • Embedded/raw-flash scenarios differ from enterprise SSDs with opaque FTLs, where user-level tweaks may have limited effect.

Alternative tree designs and optimizations

  • Ideas discussed include delta records instead of full node copies (rejected as trading space for extra reads/compute), hot/cold dual trees (akin to WAL+btree), and using write buffers in internal nodes (buffer trees, Bε-trees, Fractal trees, Hitchhiker tree, Bw-tree) to amortize CoW write costs at the expense of slightly slower lookups.
  • ZFS’s intent log and CoW trees, CouchDB’s append-only B+tree with background compaction, and Datomic-style segmented trees are cited as related architectures.

Terminology and language-level parallels

  • “Persistent” is used for immutable, versioned data structures; some confusion arises with “persistent” meaning “on disk.”
  • Experiences with Scala, Clojure, and JS libraries (e.g., transients/Immer) show that idioms and batching have large performance impact beyond the basic immutable vs mutable choice.