Timeline DB

Overview

timeline-db is an embeddable MVCC key-value store that retains the complete mutation history of every key. It is a single-writer, multi-reader system where reads and writes never block each other. Each reader operates under snapshot isolation, observing a consistent, immutable view of the store at any point in its history.

The timeline

The timeline is the complete, ordered record of every mutation that has ever happened in the store. Rather than storing only the current value of a key, the store retains the full history: every mutation indexed by a monotonically increasing logical clock called commitSeq.

Each key has its own slice of this timeline: an ordered sequence of revisions showing when it was created, updated, deleted, and whether it was recreated. Nothing is overwritten in place. New revisions are appended, and old ones persist until compaction explicitly advances the visibility boundary.

Concurrency model

The store is a single-writer, multiple-reader (SWMR) system. The writer and readers share three structures: the revision-record buffer, the key-timeline index, and the commit-seq bound. All three use carefully ordered volatile writes to establish happens-before without synchronization.

1. buffer.publish(). Volatile write; makes staged records visible.
2. tlTxn.commit(). The B+ tree CoW update is atomic from readers’ perspective.
3. bound.advance(). Volatile write; readers that observe the new end are guaranteed to see the buffer and index updates.

A reader that observes end = N is guaranteed to see all mutations at or below N in both the buffer and the index. No locks. No reader-writer coordination.

Write path

All mutations go through a SessionWriter. A session corresponds to a single backend write transaction that accumulates multiple logical commits before being flushed.

A logical commit (Writer.close()) makes writes visible to new readers immediately, with no backend flush required. The backend write transaction is held open across multiple logical commits and flushed lazily by sync().

Read path

reader() creates a CommitBoundedReader pinned to the current committed state. In order: it reads CommitSeqBound.end first (volatile read), pins a buffer view, takes a B+ tree snapshot, then opens a backend read transaction.

Reading the bound first guarantees that the buffer and index pinned in subsequent steps have already reached that commitSeq.

Compaction

Compaction sets a new lower boundary on the visible history. Reads at any commitSeq strictly below the boundary return Compacted. Physical deletion is deferred: a BatchCompactor removes one batch of backend records per sync(), draining the backlog incrementally to keep write latency flat.

Background

timeline-db was built as the storage engine for Axis, a fault-tolerant, strongly consistent distributed key-value store backed by Raft. Axis needed a storage engine that retains the complete revision history of every key. Rather than adapting an existing store, this engine was built from scratch; the SWMR design with copy-on-write snapshots serves that history without blocking concurrent reads.