cairn
Phase 1 shipped — custom LSM engine, 32 tests passing

cairn

A from-scratch, sharded, Raft-replicated, LSM-backed distributed key-value store.

Built in Rust to demonstrate hard-systems architecture — a custom storage engine, real consensus, multi-key transactions, and a sharded cluster — not to ship a product. Every guarantee is proven with tests, not asserted in a README.

View on GitHubRead the docs
cargo bench -p cairn-storage
// sequential writes, 1,000 puts
put_1k_seq              time: [548.11µs 552.30µs 556.90µs]

// cold point-read, post flush + compaction
get_hit_cold            time: [6.02µs 6.10µs 6.19µs]

Why it's hard

The complexity is the point

cairn isn't hard because of scale — it's hard because consensus, storage-engine internals, transaction isolation, and shard placement are each genuinely difficult problems on their own, and the design has to be right at every seam between them.

A storage engine, not a wrapper
No embedded database underneath. The WAL, memtable, SSTables, bloom filters, and compaction are all hand-built in Rust — the part most "distributed KV stores" skip by reaching for RocksDB.
Real consensus, not a leader flag
Raft with pre-vote, log replication, read-index linearizable reads, snapshotting, and joint-consensus membership changes — driven through a deterministic simulator so consensus bugs are reproducible, not folklore.
Layered by dependency, not by guesswork
Storage → consensus → transactions → sharding → routing. Each layer has one job and a narrow interface, so the system is a complete, working thing at the end of every phase — never a broken half of a bigger one.
Guarantees you can check, not just claim
Linearizability and snapshot isolation are properties a chaos/Jepsen-style suite has to prove against a captured history — partitions, drops, crashes, and clock skew included.

Architecture

Built strictly bottom-up

Every layer has one job and a narrow interface to the layer above it, so it can be built and proven correct in isolation. If work stopped after any layer, what exists below it is still a complete, working system.

05

Control plane / shard router

Planned

placement · split/rebalance · cluster dashboard

Routes client keys to Raft groups, decides shard placement, and renders a live view of cluster and leadership state.

04

Multi-Raft

Planned

many Raft groups, one node set

One Raft instance per key range, sharing a transport, so the cluster can host many independently-replicated shards.

03

MVCC transaction layer

Planned

snapshot isolation, multi-key

Versioned keys ordered through the Raft log, with snapshot-isolation conflict checks at commit and GC folded into compaction.

02

Raft consensus

In progress

election · replication · read-index · snapshot · membership

Full single-group Raft: pre-vote election, log replication, linearizable read-index reads, and joint-consensus membership changes.

01

Custom LSM storage engine

Shipped

WAL · memtable · SSTables · leveled compaction · bloom

Durable, crash-recoverable local key-value storage. Shipped and tested — 32 tests passing, including property-based verification.

Layers are ordered by dependency (bottom = foundation). The source spec groups the LSM engine and Raft consensus as one delivery cycle — see the roadmap for phase-by-phase status.

Roadmap

Every phase ends at a finished system

If work stops after any phase, what's already built stands alone — never a broken half of a larger system. Status is honest: one phase shipped, one in design, three planned.

Full roadmap
  1. Phase 1Shipped

    Custom LSM storage engine

    WAL, memtable, SSTables, bloom filters, full compaction. 32 tests, including property-based verification against a BTreeMap reference model.

    Durable, crash-recoverable local KV store

  2. Phase 2In progress

    Raft consensus (single group)

    Design spec resolved: real TCP transport behind a pluggable trait, a dedicated Raft log store as the first buildable unit.

    Chaos-tested replicated linearizable KV

  3. Phase 3Planned

    MVCC transactions

    Multi-key transactions at snapshot isolation, layered on Raft's commit ordering for a version source.

    Snapshot-isolation transactions, checker-proven

  4. Phase 4Planned

    Multi-Raft

    Many independent Raft groups on one node set, each owning a contiguous key range — sequenced after 1–3 are chaos-tested.

    Many key ranges, per-group consensus

  5. Phase 5Planned

    Shard router + control plane

    The one language boundary: a TypeScript/Bun control plane for placement, routing, and a live cluster dashboard.

    Live sharded cluster, visualized, fault-tested

Benchmarks

Real numbers from the shipped engine

Single-node, single-thread criterion microbenchmarks on the storage engine — not a production SLA, and not a distributed-system number yet. Full methodology in the docs.

Sequential write throughput

~1.8Mputs/sec

552µs per 1,000 sequential puts

Cold point-read latency

6.1µs

after flush + compaction, bloom-filtered lookup

Crate safety constraints

Zerounsafe

no .unwrap()/.expect() in I/O paths either

Test coverage by module — crates/storage

32 tests total

  • engine
    11
  • bloom
    5
  • wal
    4
  • memtable
    4
  • sstable
    3
  • types
    2
  • recovery
    2

Plus one property-based test (engine_matches_btreemap) that runs ~200 randomized Put/Delete/Flush/Compact/Reopen operations per execution against a BTreeMapreference model — not reflected in the counts above since it isn’t a fixed number of assertions. It caught a real bug: see seqno recovery.

Design decisions

Written as ADRs, not marketing copy

The choice made, the alternative seriously considered, and why the tradeoff went the way it did — including a bug a property test actually caught.

Raft over Paxos

Raft's decomposition into election, replication, and safety gives a chaos suite crisp invariants to check a captured history against — a legibility Paxos variants don't specify for free.

LSM over B-tree

Sequential-append writes now, background merge cost later — and why the Raft log store stays a separate component instead of another LSM consumer.

Atomic flush via temp+rename

A flush or compaction is never discoverable until it's fully written — write to .sst.tmp, rename into place. Closes a real restart-bricking bug.

Seqno recovery across restarts

A property test found a real bug: reopening after a flush under-reported next_seqno and silently resurrected stale data. Here's the repro and the fix.