Building a Distributed Key-Value Store on a From-Scratch Raft

Motivation

Most distributed key-value stores you use day to day hide their consensus layer behind a library. You get the guarantees without ever seeing how leader election, log replication, or snapshotting actually work. I wanted the opposite: to build a production-grade distributed key-value store backed by a from-scratch implementation of the Raft consensus algorithm, with no external consensus libraries.

The reference is the extended Raft paper by Ongaro and Ousterhout, "In Search of an Understandable Consensus Algorithm". Leader election, log replication, persistence, snapshotting, and membership changes are all implemented directly from the paper, with section numbers cited in the code where a rule comes from. The goal is engineering rigor: correctness, deterministic fault-injection tests, benchmarks, metrics, and design docs, not just a feature checklist.

What It Is

kvraft is a cluster of 3 to 5 node processes that agree on an ordered log of writes via Raft, then apply that log to an in-memory key-value map. The cluster survives crashes and network partitions: as long as a majority of nodes are up and can talk to each other, it stays available and never loses a committed write.

Clients talk plain HTTP/REST, or use the bundled CLI, to any node. Requests are transparently redirected or forwarded to the current leader, so a client does not need to know which node is in charge.

The client API is small on purpose:

• GET, read a key (linearizable).
• PUT, set a key to a value.
• DELETE, remove a key.
• CAS, compare-and-swap: set a key only if its current value matches an expectation.

Writes are idempotent. Each write is tagged with a request ID, so a write that is retried after a timeout is applied at most once rather than twice.

What Raft Actually Requires

The whole of the extended paper is in scope, and I am building it in the order the paper builds the argument:

1. Leader election, randomized election timeouts, terms, and votes (section 5.2).
2. Log replication, the AppendEntries RPC, a commit index, and applying committed entries to the state machine (section 5.3).
3. Safety, term checks, the Log Matching property, and the election restriction that keeps a stale node from becoming leader (section 5.4).
4. Persistence, currentTerm, votedFor, and the log all survive a restart (section 5).
5. Snapshotting and log compaction, the InstallSnapshot RPC to keep the log from growing without bound (section 7).
6. Membership changes, single-server add and remove (section 6), as a stretch goal.

Architecture

                 clients (HTTP / CLI)
                         |
        +----------------+----------------+
        |                |                 |
   +----v-----+     +----v-----+     +-----v----+
   |  node A  |     |  node B  |     |  node C  |
   | (leader) |<--->|(follower)|<--->|(follower)|   gRPC: RequestVote,
   +----+-----+     +----+-----+     +-----+----+   AppendEntries,
        |                |                 |         InstallSnapshot
   +----v----------------v-----------------v----+
   | per node:                                  |
   |   HTTP API --> Raft core --> KV state machine
   |                  |                         |
   |                  v                         |
   |            WAL (append-only, fsync)        |
   |            + snapshots (log compaction)    |
   +--------------------------------------------+
      

Each node is a single Go process that exposes two surfaces: a gRPC server for the inter-node Raft RPCs (node to node), and an HTTP/REST server for clients, plus a small CLI called kvctl.

The Seam That Makes Testing Possible

The most important design decision is that the Raft core depends on only two interfaces, a Clock and a Transport. That means the same consensus code runs over real gRPC and wall-clock time in production, and over an in-memory simulated network with a virtual clock in tests.

That seam is what makes the chaos tests deterministic and fast. Instead of waiting on real timeouts and real sockets, the test harness can drive thousands of partition and crash scenarios in seconds, and replay any failure exactly. Consensus bugs are notoriously hard to reproduce; making the network and clock injectable is the difference between a flaky suite and a trustworthy one.

Repo Layout

api/proto/             Protobuf definitions for the Raft RPCs and KV commands
cmd/kvnode/            One Raft node process (gRPC + HTTP)
cmd/kvctl/             CLI client (get / put / del / cas, cluster status)
cmd/kvbench/           Load generator (throughput + p50/p99)
internal/raft/         Raft core: election, replication, persistence, snapshots
internal/storage/      Append-only WAL + snapshot store
internal/kv/           KV state machine + client-dedupe table
internal/server/       gRPC + HTTP servers, leader redirect, linearizable reads
internal/metrics/      Prometheus collectors
internal/testharness/  Simulated network + clock, linearizability checker
test/                  Unit, integration, and chaos tests
      

Building in Verifiable Milestones

I am building this in small, runnable increments. Each milestone is proven green, meaning the build and its tests pass, before the next one begins. This keeps the project honest: there is always a working system, just one with fewer features.

As of this write-up, M0 is in progress: the scaffold, the protobuf and gRPC stubs, a single-node KV with a write-ahead log, and the Clock and Transport seams that the rest of the project depends on.

Tooling

The project is Go 1.24+. Protobuf code is generated with buf, a pure-Go protobuf compiler, so there is no protoc C++ binary to install. The build is driven through a Makefile: one target to regenerate the gRPC code, one to compile the node, CLI, and benchmark binaries, and one to run the deterministic unit and integration tests. The chaos campaigns and the benchmark numbers land with their respective milestones.

Why Do It This Way

It would be faster to pull in an existing Raft library and wire a key-value map on top. But the point of this project is not to ship a key-value store; it is to understand consensus well enough to implement it correctly, prove it with deterministic fault injection, and be able to point at the exact paragraph of the paper behind each rule. The milestones, the simulated-network seam, and the linearizability checker are all there to make that claim verifiable rather than aspirational.

The system is being built now, and I will update this log as each milestone turns green.

Stack: Go 1.24+ · gRPC and Protobuf (buf) · custom Raft core · append-only WAL with fsync · snapshots · Prometheus metrics · simulated network and virtual clock for tests
Consensus: from scratch, by the extended Raft paper
Status: under active construction (M0 in progress)

All blogs · ← Back to portfolio