raftkv

A distributed, linearizable, fault-tolerant key–value store in Go, built on a from-scratch implementation of Raft — no etcd/raft, no hashicorp/raft, no consensus libraries of any kind. The raft package tracks the extended Raft paper section by section (comments cite the sections they implement), and every layer above it is held to a linearizability specification that CI checks against 1000 randomized fault schedules on every push.

Raft core · fsync WAL · lease reads · exactly-once sessions · dynamic sharding with live migration · from-scratch linearizability checker · Jepsen-style fault injection · YCSB benchmarks · Prometheus/Grafana

Why this exists

Consensus is the part of distributed systems where "looks correct" and "is correct" diverge hardest: the bugs live in the interleavings you didn't imagine — a leader that dies in the 5 ms between appending an entry and hearing the majority ack, a follower that installs a snapshot that conflicts with committed log it already truncated, a client that retries a write whose reply was lost but whose effect wasn't. This project treats those interleavings as first-class: the whole store runs on a deterministic simulated network where partitions, message loss, reordering, clock skew, and disk failure are driven by a single seed, and every execution is checked against a formal linearizability model. When a bug is found, its seed replays it deterministically, and it goes in BUGS.md with a root cause. Seven are recorded there so far — including two the store's own CI found that local runs never did.

Architecture at a glance

flowchart TB
    subgraph clients["Clients"]
        C1["kv.Clerk<br/>(single group)"]
        C2["shard.Clerk<br/>(sharded, config-routed)"]
    end

    subgraph service["Service layer — replicated state machine"]
        direction TB
        KV["kv.Server / shard.Group<br/>· apply loop · session table<br/>· lease-read fast path · snapshots · CAS"]
    end

    subgraph consensus["raft — consensus core (from the paper)"]
        direction TB
        R["elections §5.2 · replication §5.3<br/>safety §5.4 · compaction §7 · lease basis §8"]
    end

    subgraph durability["Durability & transport"]
        direction LR
        WAL["raft/wal<br/>fsync'd CRC WAL"]
        SIM["sim<br/>(fault-injecting net, tests)"]
        RPC["rpcnet<br/>(net/rpc over TCP, prod)"]
    end

    C1 & C2 -->|"exactly-once RPC<br/>(clientID, seq)"| KV
    KV -->|"Start(cmd) / ApplyMsg"| R
    R -->|"HardState, log, snapshot"| WAL
    R <-->|"RequestVote · AppendEntries · InstallSnapshot"| SIM
    R <-->|same RPCs| RPC
    KV -.->|"/metrics"| PROM["metrics<br/>(Prometheus)"]

The dependency arrow that matters: the service calls Raft, and Raft calls storage — never the reverse. The apply loop delivers committed commands on a channel and never holds Raft's mutex across the send, so the service can call back into Raft (e.g. Snapshot()) from inside apply without deadlocking. That single rule is what lets snapshotting, lease reads, and the KV state machine compose cleanly.

The consensus core

A single node's control loop:

stateDiagram-v2
    [*] --> Follower
    Follower --> Candidate: election timeout<br/>(randomized, §5.2)
    Candidate --> Candidate: split vote →<br/>new term, retry
    Candidate --> Leader: majority of votes<br/>(with §5.4.1 log restriction)
    Candidate --> Follower: sees higher term<br/>or valid leader
    Leader --> Follower: sees higher term
    Leader --> Leader: heartbeat / replicate<br/>advance commitIndex (§5.4.2)

Safety invariants (and where they live)

The paper's correctness rests on five properties; each maps to specific code with a comment citing its section:

Invariant (Raft Figure 3)	How it's enforced	Where
Election Safety — ≤1 leader per term	A node votes once per term (`votedFor`, persisted before replying)	`election.go`, `storage`
Leader Append-Only — a leader never overwrites its own log	Only followers truncate on conflict; a leader only appends	`replication.go`
Log Matching — same (index, term) ⇒ identical prefixes	`AppendEntries` consistency check on `PrevLogIndex/Term`	`replication.go`
Leader Completeness — a committed entry survives all future leaders	§5.4.1 election restriction: a candidate needs an up-to-date log to win	`election.go` (`HandleRequestVote`)
State Machine Safety — no two nodes apply different commands at one index	§5.4.2 commit rule: a leader commits only entries of its own term by count; earlier entries commit transitively	`replication.go` (`advanceCommitLocked`)

The last one is the subtle Figure-8 case, and it's a one-line guard that is easy to get wrong: advanceCommitLocked walks candidate indices downward and breaks the moment it sees an entry from an older term, so a leader can never mark a previous-term entry committed merely because it's replicated on a majority. Getting this wrong passes almost every test and fails catastrophically under the exact partition-then-rejoin sequence the Figure-8 test constructs.

Storage errors are treated as fatal (the choice etcd makes): if a HardState/log/snapshot write fails, the node halts rather than reply to an RPC with state it hasn't durably recorded — because a node that acks a vote or an append it then forgets after a crash can violate Election Safety or Log Matching.

Fast log backtracking

When a follower rejects an AppendEntries, the naïve protocol decrements nextIndex by one and retries — O(entries) round trips to repair a diverged follower. This implementation ships the paper's optional optimization: the follower returns (ConflictTerm, ConflictIndex), and the leader jumps nextIndex past the entire conflicting term in one step.

leader   : [ (1,1) (2,1) (3,1) (4,2) (5,2) (6,2) (7,3) ... ]
follower : [ (1,1) (2,1) (3,1) (4,4) (5,4) ]              ← diverged at 4
                                    ▲
reject → ConflictTerm=4, ConflictIndex=4
leader has no term 4 → nextIndex jumps straight to 4  (not 6→5→4)

Convergence is O(number of distinct terms) rather than O(number of entries) — the difference between a fast catch-up and a follower that stays behind for thousands of round trips after a long partition.

Durability model: the WAL

raft/wal is a real write-ahead log, not an in-memory stand-in. Every mutation is durable before the method returns, because Raft's safety argument assumes term/vote/log reach stable storage before any RPC response (paper Figure 2).

record = [ len:u32 ][ crc32c:u32 ][ gob payload ]      append-only, fsync per record

Torn-tail recovery. A record is acknowledged only after fsync, so on restart the log is replayed record-by-record and any invalid suffix (short read or CRC mismatch from a crash mid-write) is truncated, never half-applied. A single flipped byte inside a record is caught by the Castagnoli CRC and stops replay at that point.
Crash-consistent compaction. SaveSnapshot writes the snapshot file (atomic tmp+rename) first, then rewrites the WAL to just the live suffix. A crash between the two leaves a WAL whose already-covered prefix is simply dropped on recovery — snapshot-then-rewrite ordering means the failure window is recoverable, never lossy.
The log carries a sentinel at slot 0 holding the snapshot boundary (lastIncludedIndex, lastIncludedTerm), so every consistency check — PrevLogTerm at the compaction edge, the election restriction, commit advancement — is uniform with no special cases for "the entry before the snapshot."

The read path: lease reads

A linearizable read does not require a log write. A leader that has heard from a majority recently enough knows no newer leader can exist (followers refuse to vote for ElectionTimeoutMin after hearing from a leader), so it serves the read from local state — the ReadIndex/lease optimization from Raft §8 and Ongaro's thesis §6.4.

flowchart TD
    G["Get(key)"] --> L{"leader holds a<br/>majority lease?"}
    L -->|no| LOG["replicate a no-op-style<br/>read through the log<br/>(always correct, 1 round trip)"]
    L -->|yes| T{"current-term entry<br/>committed?"}
    T -->|no| LOG
    T -->|yes| A["wait until applied ≥ readIndex,<br/>then read local map<br/>(no log write, no fsync)"]
    LOG --> R["value"]
    A --> R

Two safety conditions, both enforced in raft/leaseread.go, and both non-obvious:

The lease is measured from the RPC send time, not receive time — the conservative end of the round trip. The lease lasts only ElectionTimeoutMin / 2, leaving margin for bounded clock-rate skew between nodes (the simulator deliberately runs node clocks up to ±15% off, and the lease math has to survive that).
A freshly elected leader must commit an entry of its own term first. It inherits committed entries whose commit point it cannot yet prove (its commitIndex may lag the dead leader's). Serving a lease read before closing that gap could return stale data, so LeaseRead returns !ok until a current-term entry commits, and the caller falls back to the log path — which both returns correct data and closes the gap.

TestStaleLeaseRejected pins the failure mode directly: a partitioned ex-leader whose lease has expired must refuse to serve the old value. TestLeaseReadsBypassLog proves 100 reads add zero log growth. The payoff is in the benchmarks: 1.1M reads/s on the lease path vs an 82k ops/s write path.

Exactly-once semantics

The single most important thing a replicated store must let a client do is retry a write whose outcome is unknown — and the chaos rig proved why by breaking a version that couldn't (double execution, BUGS.md #2).

sequenceDiagram
    participant C as Clerk
    participant L1 as Leader (dying)
    participant L2 as New leader
    C->>L1: Append(k,v) [client=42, seq=7]
    L1->>L1: replicate... (reply lost / L1 crashes)
    Note over C: timeout — did it apply? unknown
    C->>L2: Append(k,v) [client=42, seq=7]   ← same seq
    L2->>L2: apply — but seq 7 already applied?
    Note over L2: dedup: 7 ≤ lastSeq[42] → no-op
    L2-->>C: OK (idempotent)

Each clerk owns a random 62-bit client ID and a monotonic sequence number; the state machine tracks the highest applied seq per client and applies each (clientID, seq) at most once. Retrying an ambiguous failure is therefore always safe. Three details that are easy to miss:

The session table lives inside snapshots. Drop it and a post-restart node forgets which retries already applied, re-executing duplicates. TestSnapshotCarriesSessions fails loudly if the table isn't serialized.
In the sharded store, the session table migrates with its shard — a retry that lands on a shard's new owner must still be deduplicated.
CAS memoizes its result, not just its seq. Compare-and-swap is the one operation whose return value carries information; a duplicate CAS delivery must replay the original outcome, because re-evaluating it against newer state would return a wrong answer. TestCasAtomicIncrementUnreliable runs concurrent CAS-loop counters over a lossy network and checks the total is exact.

Dynamic sharding with live migration

The keyspace is split into shards, assigned to replication groups by a shard controller that is itself a Raft group. Config changes (groups joining/leaving) commit through the controller's log, so every participant sees the same totally-ordered sequence of configs.

Each shard moves through a four-state lifecycle per config transition, and a group advances to config N+1 only once nothing is mid-migration — so transitions happen one at a time and a migration source is always frozen exactly at the right config boundary:

stateDiagram-v2
    direction LR
    Absent --> Serving: assigned from unowned
    Serving --> Offering: reassigned away
    Absent --> Pulling: reassigned to us
    Pulling --> Serving: pulled + installed via log
    Offering --> Absent: new owner confirms install → GC

Pull-based migration. A new owner pulls the frozen shard (data and its session sub-table) from the previous owner and installs it through its own Raft log, so every replica in the group installs identical state.
Confirmed hand-off + garbage collection. The old owner keeps the shard frozen until the new owner confirms installation, then deletes it — no window where a shard is owned by nobody, and no unbounded leak.
Ownership is re-checked at apply time, not just at request time: the config can change between when a client op is proposed and when it commits, and every replica must make the identical routing decision.
Deterministic, minimal-movement rebalancing. The controller balances shard counts across groups while moving as few shards as possible, iterating only over sorted slices (never map order) so every replica computes the byte-identical next config.

TestSessionsSurviveMigration and TestConcurrentOpsDuringChurn keep clients writing while groups join and leave, then assert every append landed exactly once in per-client order.

How correctness is verified

Three layers, each catching a different class of bug.

1. Deterministic simulation

sim is an in-memory network where one seeded RNG drives every drop, delay, reorder, and partition decision — so a failing schedule replays exactly from its seed. It models the failure modes that actually bite RPC systems, not the convenient ones:

A dropped reply still executes the request on the receiver. A false return means "no reply," never "not executed" — which is precisely why the RPCs are idempotent.
Partitions are checked on both the request and the reply path, so a partition that forms mid-RPC eats the reply.
Per-node clock skew (±15%) so timing-based logic (the lease) can't assume synchronized clocks.
Simulated disk-full that halts a node etcd-style, plus crash/restart that preserves storage.

2. The linearizability checker

linz is a from-scratch linearizability checker (the Wing & Gong / Lowe algorithm — the same family as Knossos and Porcupine): a depth-first search over legal linearization orders, memoized on (set-of-linearized-ops, state) so equivalent search branches are visited once.

Per-key compositionality. Operations on distinct keys commute and linearizability is compositional (Herlihy & Wing §3.3), so one exponential search becomes many small ones — the difference between checkable and not.
Indeterminate operations. A client that timed out may have taken effect at any later point, or never. Those ops are modeled with an infinite return time and must still linearize somewhere — sound because a write that never landed can always sit after the last observation.
Bounded search. Both a wall-clock budget and a memory cap; past either it returns Unknown (inconclusive) rather than dying — a verifier needs a memory budget as much as a time budget (BUGS.md #7).

3. The nemesis

chaos is a Jepsen-style rig: a seeded scheduler pulls faults — leader kills mid-commit, random crashes, leader-trapping minority partitions, lossy/reordering delivery, disk-full — while recording clients build a history that's handed to the checker.

CI, every push:  4 shards × 250 seeds = 1000 randomized fault schedules
                 any linearizability violation → build fails
                 + seed, nemesis timeline, and full history uploaded as an artifact
                 + ≥85% consensus-coverage gate, race detector on the functional suite

Replay any failure locally:

RAFTKV_CHAOS_BASE=<seed> RAFTKV_CHAOS_SEEDS=1 go test ./chaos -run Schedules

BUGS.md is the interview-gold artifact — seven real bugs with root causes and the design lesson each forced, including a "safe to retry" reply that wasn't (the canonical argument for sessions), checker false positives from a coarse OS clock producing zero-duration ops, two Raft clusters cross-talking through a shared peer-index namespace, and 16 parallel checkers OOM-ing a CI runner.

Performance

Measured with cmd/raftkv-bench (YCSB A–F, failover, snapshot recovery); full tables, method, and caveats in BENCHMARKS.md. The numbers isolate the consensus path (in-process network, no wire latency), so the shapes are the durable findings, not the absolute figures.

Finding	Number	What it means
Lease reads never touch the log	1.1M ops/s (workload C)	The read fast path is the whole point of leases
Write path, 3 nodes, in-mem storage	82k ops/s	Bounded by single-leader replication
Writes shrink as nodes are added	82k → 60k (3 → 7 nodes)	The single-leader bottleneck is architectural — replicas buy fault tolerance, not write throughput
Real fsync WAL	plateaus at ~3k ops/s	The fsync ceiling: one sync per mutation caps throughput while latency grows linearly with load
Leader failover	p50 ≈ 250–310 ms	Exactly one election-timeout draw; worst case one split vote more
Snapshot recovery	flat in history length	Cost scales with state size, not log length — the point of snapshots

The honest write-throughput analysis, and the ranked fixes (group commit → pipelined replication → multi-raft, which the shard layer already implements as independent per-group logs), is the centerpiece of BENCHMARKS.md.

Running it

# 5-node cluster + Prometheus + a pre-provisioned Grafana dashboard
docker compose up --build -d
# Grafana → http://localhost:3000   Prometheus → http://localhost:9090

# talk to it
go run ./cmd/raftkv-cli -servers localhost:7001,localhost:7002,localhost:7003,localhost:7004,localhost:7005 put hello world
go run ./cmd/raftkv-cli -servers localhost:7001,... get hello
go run ./cmd/raftkv-cli -servers localhost:7001,... txn incr counter 5   # atomic RMW via CAS loop
go run ./cmd/raftkv-cli -servers localhost:7001,... status               # per-node consensus state

# or natively
make build     # raftkvd, raftkv-cli, raftkv-bench
make test      # everything
make race      # race detector, short mode
make chaos     # 50 seeded fault schedules (CI runs 1000)
make cover     # consensus coverage (gated ≥85% in CI)
make bench     # YCSB + failover + recovery

Each raftkvd process is one replica: WAL on disk, one TCP port serving both consensus and client RPCs, Prometheus /metrics, structured JSON logs. The Grafana dashboard shows leader/term, commit index, ops/s by type, lease-vs-log read ratio, apply lag, and un-compacted log bytes (snapshot pressure).

Package map

flowchart LR
    cmd["cmd/*<br/>raftkvd · raftkv-cli · raftkv-bench"] --> kv & shard & metrics & rpcnet
    shard --> kvdep["(sessions, replicator)"]
    kv --> raft
    shard --> raft
    metrics --> kv
    rpcnet --> kv & raft
    chaos --> kv & linz & sim
    kv --> sim
    raft --> wal["raft/wal"]
    raft --> sim

Package	Responsibility
`raft/`	Consensus: elections (§5.2), replication + fast backtracking (§5.3), safety (§5.4), compaction (§7), lease basis (§8)
`raft/wal/`	fsync'd, CRC-checked write-ahead log with torn-tail recovery and crash-consistent compaction
`sim/`	Seed-locked fault-injecting network (drops, delays, reorder, partitions, clock skew, disk-full, crash/restart)
`linz/`	Linearizability checker (Wing & Gong / Lowe, memoized, per-key compositional, indeterminate-op support, bounded)
`chaos/`	Jepsen-style nemesis + recording clients; the 1000-schedule CI suite
`kv/`	Single-group KV: exactly-once sessions, lease reads, CAS, snapshots, op counters
`shard/`	Shard controller + groups: configs via Raft, pull-based migration, per-shard sessions, GC
`rpcnet/`	Production transport: net/rpc over TCP with pooling, timeouts, reconnect
`metrics/`	Prometheus collectors for consensus + service state
`cmd/`	`raftkvd` (daemon), `raftkv-cli` (operator/client), `raftkv-bench` (workloads)

Design decisions and trade-offs

Raft, not Multi-Paxos or EPaxos. Understandability is the point — the code should be auditable against a paper. The single-leader throughput cost is measured, not hidden, and the multi-raft escape hatch is built.
fsync per mutation, no group commit (yet). The simplest correct durability policy; BENCHMARKS.md quantifies exactly what it costs and what group commit would recover. Correctness first, then the optimization with numbers to justify it.
Lease reads are leader-only. Follower reads would spread read load but need per-follower read-index tracking; scoped out deliberately, and the benchmark notes where it would help.
A custom linearizability checker, not an off-the-shelf one. Writing the WGL search (and hitting its own failure modes — false positives, OOM) is half the education; it's also what makes the histories replay by seed.
Static membership per process; data mobility via sharding. Raft-level joint-consensus reconfiguration isn't implemented; the shard layer moves data between groups instead, which covers the operationally common case.

Known limitations

Stated plainly, because an honest boundary is more useful than an implied one:

Single-key linearizable operations; no multi-key transactions, no range scans. The transactional primitive is single-key CAS (txn incr is an atomic read-modify-write built on it).
Lease reads are served by the leader only (no follower reads).
The WAL fsyncs per mutation — no group commit yet (see BENCHMARKS.md).
Cluster membership is fixed per process lifetime; the shard layer migrates data between groups, but Raft-level joint consensus is out of scope.
Benchmarks run on the in-process simulated network: the shapes (flat write scaling, fsync plateau, timeout-bounded failover) are durable; absolute throughput on real hardware would add a network RTT per write.

Built to be broken first. Every claim here is backed by a test that tries to falsify it, a benchmark that measures it, or a bug in BUGS.md that already caught it.

Navigation Menu

Repository files navigation

raftkv

Table of contents

Why this exists

Architecture at a glance

The consensus core

Safety invariants (and where they live)

Fast log backtracking

Durability model: the WAL

The read path: lease reads

Exactly-once semantics

Dynamic sharding with live migration

How correctness is verified

1. Deterministic simulation

2. The linearizability checker

3. The nemesis

Performance

Running it

Package map

Design decisions and trade-offs

Known limitations

About

Releases

Packages

Contributors

Languages

Name		Name	Last commit message	Last commit date
.github/workflows		.github/workflows
chaos		chaos
cmd		cmd
deploy		deploy
kv		kv
linz		linz
metrics		metrics
raft		raft
rpcnet		rpcnet
shard		shard
sim		sim
.gitignore		.gitignore
BENCHMARKS.md		BENCHMARKS.md
BUGS.md		BUGS.md
Dockerfile		Dockerfile
Makefile		Makefile
README.md		README.md
docker-compose.yml		docker-compose.yml
go.mod		go.mod
go.sum		go.sum

Latest commit

History

Folders and files

Repository files navigation

raftkv

Table of contents

Why this exists

Architecture at a glance

The consensus core

Safety invariants (and where they live)

Fast log backtracking

Durability model: the WAL

The read path: lease reads

Exactly-once semantics

Dynamic sharding with live migration

How correctness is verified

1. Deterministic simulation

2. The linearizability checker

3. The nemesis

Performance

Running it

Package map

Design decisions and trade-offs

Known limitations

About

Resources

Stars

Watchers

Forks

Releases

Packages

Contributors

Languages