A strongly-consistent, replicated key-value store in Go: Raft for consensus, a log-structured merge-tree for storage, and a linearizability checker that proves the two together behave the way the system claims.
No third-party dependencies. Consensus, the storage engine, the wire protocol and the verification harness are all written here, on the standard library.
| Throughput, 3 nodes / 128 clients | 1,105 ops/sec (50% reads, replicated + durable) |
| Latency | p50 89 ms, p90 152 ms, p99 200 ms |
| Observed failover after killing the leader | 334–526 ms (6 runs, median 451 ms) |
| Storage engine, point read from disk | 1.17 µs |
| Storage engine, read of an absent key | 125 ns — bloom filter skips 98.99% of tables |
| Linearizability under repeated network partitions | 3,150 operations, 15 leader changes, 0 anomalies |
Measured on an Apple M5 (10 cores), Go 1.26.5, real sockets and real fsyncs.
Reproduce with make bench.
Any node accepts a request. One is elected leader. A write is acknowledged only after a majority of nodes have durably logged it. If the leader is killed mid-write, a new one is elected in under a second, and no acknowledged write is ever lost, reordered or applied twice — even under network partitions.
Anyone can put a hashmap behind an HTTP server. The work is keeping that promise true when machines die, disks tear and packets vanish — and, harder, being able to demonstrate it still holds rather than asserting it.
The correctness condition this store claims is linearizability: every operation must appear to take effect instantaneously at some single instant between the client issuing it and receiving a reply, and those instants must form a legal sequential execution.
That is not something an ordinary test can assert. Operations from different
clients overlap in real time, so a recorded history admits an enormous number of
candidate orderings, and the history is correct if any one of them is legal.
Deciding that is NP-complete in general. So internal/linz implements the actual
search — Wing and Gong's algorithm with Lowe's memoisation:
- Walk the history for an operation that is currently minimal and whose response the sequential model accepts in the current state.
- Provisionally linearize it, lift it out of the history, recurse.
- Reaching an operation's return before its call has been linearized means this branch is dead — backtrack.
- Memoise on
(set of linearized operations, resulting state). Two orders that linearize the same set into the same state have identical futures, so the second is never explored. This is what makes the search tractable.
Linearizability is compositional over disjoint objects, so the history is first partitioned by key and each key checked independently.
A checker that accepts everything is worse than no checker, so it is held to both directions:
| Property | Result |
|---|---|
| Rejects a read that misses a completed write | ✅ |
| Rejects a read returning a superseded value (the split-brain signature) | ✅ |
| Rejects a value moving backwards between two reads | ✅ |
| Rejects a lost update between concurrent appends | ✅ |
| Rejects an operation applied twice | ✅ |
| Rejects a read after a completed delete | ✅ |
| 200 randomised histories that are linearizable by construction | 0 false alarms |
| 200 histories with exactly one corrupted read | 200/200 caught |
| Budget exhausted | reports INCONCLUSIVE, never a false pass |
That last row matters: the checker can say I don't know. A verifier that silently returns "fine" when it ran out of search budget is not a verifier.
A history whose operations never overlap has exactly one possible ordering, so it is linearizable almost by construction and a passing verdict proves nothing. Every integration test therefore asserts peak concurrency alongside the verdict, and every chaos test asserts that leadership actually changed — otherwise the fault injection did nothing and the test is theatre. Both assertions caught real vacuous passes while this was being built.
make race runs all 58 tests under the race detector.
Consensus (internal/raft) — every peer's applied entries are cross-checked
against every other peer's at the same index on every apply, so a State Machine
Safety violation fails the test the instant it occurs.
- one leader per term, stable on a healthy network
- a 2|3 partition: the minority side cannot commit; the majority keeps serving
- entries accepted by an isolated leader are discarded when it rejoins
- term, vote and log survive a total cluster restart
- a follower isolated past log compaction is caught up by InstallSnapshot (asserted via metrics, not inferred from behaviour)
- agreement holds under 10% packet loss plus continuous node churn
Storage engine (internal/lsm) — driven against a plain Go map as an
independent oracle over 60,000 randomised operations, verifying after every round
and again after a restart. Also: WAL torn-tail recovery, CRC-detected corruption,
the disjointness invariant that the levelled read path depends on, and tombstones
surviving until the bottom level.
The whole system (internal/kv) — real Raft peers, real storage engines, real
temp directories, under fault injection:
| Scenario | Result |
|---|---|
| 12 clients, healthy network | 480 ops, peak concurrency 12 — linearizable |
| 10 clients, 10% packet loss | 300 ops — linearizable |
| 10 clients, repeated 2 | 3 partitions |
| 8 clients, rolling leader kills + restarts | 997 ops, 4 leader changes — linearizable |
| 100 appends over a lossy network | every one applied exactly once |
| Total cluster restart | all 60 acknowledged writes survived |
The exactly-once test is the countable version of the guarantee: five clients each append their own token twenty times while one message in ten is dropped, forcing constant retries of requests that may already have been applied. The final value must contain each token exactly twenty times — more means a duplicate apply, fewer means a lost update.
client one node
│ ┌───────────────────────────────┐
│ put/get │ kv.Server │
└────────────────►│ dedup table (exactly-once) │
│ waiters by log index │
├───────────────────────────────┤
│ raft.Raft │◄──► peers
│ election · replication │ (TCP)
│ commitment · snapshots │
│ group-commit syncer │
├───────────────────────────────┤
│ lsm.DB │
│ WAL → memtable → SSTables │
│ levelled compaction │
└───────────────────────────────┘
│
append-only
raft log + snapshot
internal/raft — Raft per Ongaro & Ousterhout (2014). Leader election with
the §5.4.1 up-to-date restriction, log replication with fast conflict backup,
§5.4.2 current-term-only commitment, and snapshot-based compaction. Each safety
property is annotated in the source with where it is enforced.
internal/lsm — write-ahead log, skiplist memtable, immutable SSTables
(4 KiB blocks, per-file bloom filter, block index, CRC-framed WAL), and background
levelled compaction with write stalls.
internal/kv — the replicated state machine. Reads go through the log like
writes, so a deposed leader cannot serve a stale value.
internal/linz — the linearizability checker.
internal/fault — an in-process network that drops, delays, reorders and
partitions RPCs on demand. Every argument is gob round-tripped so a handler can
never accidentally share memory with its caller.
internal/transport — length-prefixed binary framing over TCP, with
connection pooling.
The first working version managed 25 ops/sec at 554 ms p50. Turning fsync off barely helped, which ruled out the obvious explanation. The cause was structural: persisting state re-encoded the entire log and fsynced it while holding the Raft mutex, so every client queued behind a full disk round trip.
Five changes, each measured. Throughput is quoted with the client count and engine-fsync setting it was taken at, because both matter:
| Change | 16 clients, engine fsync on | 16 clients, fsync off |
|---|---|---|
| Baseline | 25 ops/sec | 38 |
| Group commit — appends mark state dirty; one syncer goroutine batches them into a single write, and waiters release the Raft mutex while waiting | 33 | — |
| Batched state-machine writes — data, dedup record and applied index reach the journal as one atomic batch instead of three separate syncs | 81 | 274 |
| Append-only Raft log — a durable append costs one sequential write, not a re-serialisation of the whole log | 93 | — |
One replication stream per peer — replaced a goroutine-per-request storm of redundant, overlapping AppendEntries |
— | 262 |
| Lock-free size accounting | — | 518 |
The per-peer replicator barely moved throughput at 16 clients, but it halved p50 latency (81 ms → 37 ms) and removed the RPC storm that made higher concurrency pointless.
The last row is the instructive one. Throughput had flatlined near 250 ops/sec
regardless of client count — 16 clients and 128 clients gave the same number,
with latency simply growing linearly. That is the signature of a per-operation
serialisation rather than a saturated resource. The culprit was StateSize(),
consulted on every applied command to decide whether to snapshot, taking the
persister mutex that is held across the 4 ms fsync. Making it an atomic counter
was a three-line change worth 4× throughput, and it is what let the system finally
scale with concurrency:
| Clients | Before | After |
|---|---|---|
| 16 | 262 ops/sec | 518 |
| 64 | 229 | 669 |
| 128 | 252 | 1,018 |
The storage engine's background loop always preferred flushing the memtable
(cheap) over compacting L0 (expensive), so a fast writer drove L0 to 95 tables
— every one of which sits on the read path for every key. The fix is the write
stall real engines apply at level0_stop_writes_trigger: past a threshold,
writers block until compaction catches up. L0 went from 95 tables to 0, and
compactions from 2 to 47 over the same workload.
TestReElectionAfterLeaderFails caught a node stepping down from leadership
without resetting its election timer. Because leaders do not run one, its deadline
was long expired, so it stood for election immediately and unseated the leader
that had just replaced it. Restarting the clock on step-down and on any term
advance fixes it.
Reads go through the Raft log. A leader that has been partitioned away does not know it yet, and serving a read from its local state would return a value the rest of the cluster has already replaced — the classic stale read. Committing the read costs a round trip and buys linearizability. The standard optimisation is ReadIndex (confirm leadership with a heartbeat quorum, then read locally); it is not implemented here, and log reads are what the checker actually validates.
The state machine's journal does not fsync; the Raft log does. There are two
durable logs, and syncing both is redundant work. Raft's log is the authoritative
record: if the engine loses its most recent writes, replay rebuilds them. Because
the applied index and the data it accounts for are written to the same journal in
one batch, a torn tail truncates both together and can never leave an applied
index claiming more progress than the data behind it. This is the reasoning etcd
and TiKV use. -sync=true enables engine fsync anyway, at roughly 10× the cost.
Snapshots ship the full state. Serialising every key is simple and correct at this scale. A production system ships SSTable files directly and lets the follower ingest them, which is a different and much larger piece of engineering.
No protoc, no gRPC. The wire format is a 4-byte length and a gob frame,
which keeps the build hermetic and dependency-free. This was originally a
constraint rather than a choice, so it was measured afterwards to check it was not
costing anything: the transport sustains 47,566 RPC/sec at 21 µs per round trip,
and the system at full tilt uses under 5% of that. gRPC would bring schema
evolution and HTTP/2 multiplexing — both genuinely useful at larger scale — but no
throughput here, because the transport is not what the system is waiting on.
-
The Raft log fsync is the binding constraint, at roughly 1,100 ops/sec. Measured rather than assumed, by isolating each layer:
Configuration Throughput Full system: real TCP, real fsync ~1,100 ops/sec Same code, no disk and no network (in-memory persister + transport) ~3,900 Transport alone, RPC round trips 47,566 RPC/sec (21 µs) The system issues roughly 2,200 RPCs/sec at its ceiling, which is 4.6% of what the transport can carry — so the network is not the limit, and replacing the hand-rolled transport with gRPC would not move the number. The gap between 1,100 and 3,900 is the ~4 ms
F_FULLFSYNC, amortised over only ~4–5 operations per group-commit batch. Getting further means bigger batches or a faster durability primitive (O_DSYNC, or a dedicated log device). -
A single mutex guards all Raft state. It is not the current bottleneck, but it becomes one once disk is removed: with an in-memory persister, throughput rises to 3,900 ops/sec at 64 clients and then collapses to 1,025 at 128. Sharding the lock is the optimisation that matters after durability.
-
Cluster membership is static. Raft's joint-consensus reconfiguration is not implemented; the peer set is fixed at startup.
-
No PreVote. A node partitioned as a candidate will increment its term repeatedly and can force one unnecessary election on rejoining.
-
The checker excludes operations that never returned. An operation with no response may or may not have taken effect, and assuming either would make the verdict unsound. The harness retries to completion, and abandoned operations are counted and reported separately (they are zero in every run above).
make build # three binaries, no dependencies to download
make race # all 58 tests under the race detector
make bench # engine microbenchmarks + a live cluster benchmark
make demo # bring up 3 nodes, kill the leader, show data survivesA cluster by hand:
PEERS="n1=127.0.0.1:7001,n2=127.0.0.1:7002,n3=127.0.0.1:7003"
for i in 1 2 3; do
bin/kvnode -id n$i -peers "$PEERS" -data data/n$i &
done
bin/kvctl -peers "$PEERS" status
# n1 127.0.0.1:7001 LEADER
# n2 127.0.0.1:7002 follower (leader: n1)
# n3 127.0.0.1:7003 follower (leader: n1)
bin/kvctl -peers "$PEERS" put city Kolkata
bin/kvctl -peers "$PEERS" append city ", India"
bin/kvctl -peers "$PEERS" get city
# Kolkata, India
kill %1 # kill the leader
bin/kvctl -peers "$PEERS" get city # still Kolkata, India
bin/kvctl -peers "$PEERS" put survived yes # and still writable on 2 of 3Or five nodes in containers — docker compose up --build, then kill any two.
cmd/kvnode one server process
cmd/kvctl command-line client
cmd/kvbench live-cluster throughput, latency and failover benchmark
internal/raft consensus: election, replication, commitment, snapshots
internal/lsm storage engine: WAL, memtable, SSTables, compaction
internal/kv the replicated state machine and its client
internal/linz linearizability checker
internal/fault in-process network with drops, delays and partitions
internal/transport length-prefixed RPC over TCP
~6,000 lines of implementation, ~2,600 lines of tests.