Fault-Tolerant Distributed Key-Value Store

OrientationStart here

This page is the full technical account of the system, written to be read straight through. Chapters 1–9 build up in order: the problem, the scope boundary, the architecture, how consensus works, how reads and writes flow, what happens when things break, how that was tested, what was measured, and what the results do not support.

Chapter 1The problem

Why replicating data is easy and agreeing on it is hard.

When the network splits

Run one copy of a database and a single machine failure loses everything. The obvious fix is to run several copies. But the moment there is more than one copy, they can disagree — and the network is what makes them disagree, because a network can fail in a way that is far nastier than a machine failing.

A crashed machine is honest: it serves nothing, and everyone can see it is gone. A network partition is not. It severs the cluster into groups that can each still talk internally, and each group cannot tell whether the others are dead or merely unreachable. If both groups keep accepting writes, they diverge, and there is no correct way to merge the result afterwards.

Choosing consistency over availability

Faced with a partition, a system must give something up. It can keep answering everywhere and risk returning stale or conflicting data (AP), or it can refuse to answer where it cannot guarantee correctness (CP). This system chooses CP.

That choice is enforced mechanically rather than by convention. Every read served by the leader is preceded by a VerifyLeader() call, which confirms with a majority of the cluster that this node is still the leader before it answers. A leader that has silently lost contact fails that check and refuses to serve — it returns an error instead of stale data.

Writes do not need this check: a write is only acknowledged once a majority has durably stored it, which already provides the guarantee. VerifyLeader exists because reads otherwise touch only local state and would bypass the cluster entirely (server/node.go:225).

Chapter 2What was built

Being precise about the boundary, because it is the first thing worth asking about any project that says "Raft".

What the library provides

The consensus mathematics were not reimplemented. HashiCorp Raft supplies leader-election mechanics and randomized timers, quorum arithmetic (⌊N/2⌋+1), inter-node heartbeats, log replication and truncation. BoltDB supplies the fsync guarantees that let the Raft log survive a sudden SIGKILL.

Precisely: BoltDB backs the log store and the stable store (server/node.go:89,94). Snapshots use raft.NewFileSnapshotStore (server/node.go:83), and the key-value map itself is in memory — its durability is derivative, reconstructed from the log and snapshots on restart.

What was engineered on top

Everything that turns a consensus library into a service running across physically separate machines under adversarial network conditions:

A sixth binary, kv-chaos, is a userspace TCP proxy that was the project's original fault-injection mechanism. It was superseded in v1.2 by the sidecar agent, because a proxy only affects connections routed through it, while tc netem affects all traffic on the interface — including Raft heartbeats. The source remains in the repository; none of the results below depend on it.

The fault model

A system is only ever correct with respect to a set of assumptions. These are this system's:

• Crash-recovery — nodes may die at any moment, lose in-memory state, and rejoin later.
• Unreliable network — messages may be dropped, delayed arbitrarily, or reordered.
• Split-brain partitions — the network may sever the cluster into isolated groups.
• Non-Byzantine — nodes fail by stopping, not by lying. Malicious participants and packet corruption are out of scope.

Chapter 3Architecture

Five programs, two ports per machine, and one deliberate separation.

Dual-port topology

Each VM runs two processes on separate ports. The separation is deliberate: consensus traffic and client traffic must be independently disruptable, or fault injection cannot isolate which layer a failure affects.

flowchart TD
    C["`**kv-client**
leader auto-discovery`"]
    D["`**kv-dashboard**
chaos control`"]

    subgraph CL["Raft cluster · GCP VMs"]
      direction LR
      S1["`**node0** — Leader
kv-store
Raft :12000 · gRPC :50051`"]
      S2["`**node1** — Follower
kv-store
Raft :12001 · gRPC :50052`"]
      S3["`**node2** — Follower
kv-store
Raft :12002 · gRPC :50053`"]
      S1 -- "AppendEntries / RequestVote" --> S2
      S1 -- "AppendEntries / RequestVote" --> S3
    end

    subgraph AG["Fault-injection sidecars · HTTP :9000"]
      direction LR
      A1["node-agent"]
      A2["node-agent"]
      A3["node-agent"]
    end

    C -- "gRPC :5005x" --> S1
    D -- "kill · partition · netem" --> AG
    A1 -. "SIGKILL · iptables · tc" .-> S1
    A2 -.-> S2
    A3 -.-> S3

    style S1 fill:#5b7f9e,color:#fff,stroke:#3f6180
    style S2 fill:__NEUTRAL_FILL__,stroke:__NEUTRAL_STROKE__,color:__NEUTRAL_TEXT__
    style S3 fill:__NEUTRAL_FILL__,stroke:__NEUTRAL_STROKE__,color:__NEUTRAL_TEXT__
    style C fill:__NEUTRAL_FILL__,stroke:__NEUTRAL_STROKE__,color:__NEUTRAL_TEXT__
    style D fill:__NEUTRAL_FILL__,stroke:__NEUTRAL_STROKE__,color:__NEUTRAL_TEXT__
    style A1 fill:#a8813f,color:#fff,stroke:#83642f
    style A2 fill:#a8813f,color:#fff,stroke:#83642f
    style A3 fill:#a8813f,color:#fff,stroke:#83642f
    

Raft configuration

All five set in server/node.go:55-66.

The running system

The dashboard renders live cluster state from each node's health endpoint — who leads, the current term, the applied log index, and how many nodes are reachable — and is also the control surface for injecting faults.

Chapter 4Consensus mechanics

How several machines come to agree on one ordering of events.

The replicated log

Leader election

All writes go through a single leader, which is what makes ordering easy. When the leader dies, the survivors must pick a new one without ever picking two.

sequenceDiagram
    autonumber
    participant F1 as Follower A
    participant L as Leader (dying)
    participant F2 as Follower B

    L->>F1: AppendEntries (heartbeat)
    L->>F2: AppendEntries (heartbeat)
    Note over L: crash / partition
    Note over F1,F2: silence...
    Note over F1: heartbeat timer expires
(randomized, 500-1000 ms)
    F1->>F1: term++, vote for self
    F1->>F2: RequestVote (term N+1)
    F2-->>F1: vote granted
    Note over F1: 2 of 3 = majority
    F1->>F2: AppendEntries (new leader)
    

Here is that sequence captured live — the leader killed, and the cluster after it recovered:

The term increments on every election. It is Raft's logical clock, and it is how a node that rejoins late discovers its information is stale.

Why a majority, specifically

Even node counts are avoided: 4 nodes tolerate the same single failure as 3, while adding a replica's coordination cost. Both 3-node and 5-node clusters were deployed; dynamic_deploy.sh parameterises node count, though raw artifacts from the 5-node run are not committed to the repository.

How long failover takes

Failover time is a distribution, not a constant, and the reason is deliberate. HashiCorp Raft randomizes its timers to prevent split votes — if every follower timed out at exactly the same moment, they would all become candidates simultaneously, split the vote, and have to retry.

In hashicorp/raft@v1.7.3, randomTimeout "returns a value that is between the minVal and 2x minVal" (util.go:33). So with the configuration above:

Chapter 5Read & write paths

What actually happens when a client calls set or get.

The write path

sequenceDiagram
    autonumber
    participant C as kv-client
    participant F as Follower
    participant L as Leader
    participant P as Peers
    participant M as FSM

    C->>F: Set(foo=bar)
    F-->>C: redirect → leader address
    C->>L: Set(foo=bar, clientID, seqNum)
    L->>L: append {SET, foo, bar, clientID, seqNum}
    L->>P: AppendEntries
    P-->>L: ACK (entry fsync'd to BoltDB log)
    Note over L: quorum reached → entry committed
    L->>M: FSM.Apply()
    M->>M: dedup check (clientID, seqNum)
    M->>M: apply to in-memory state
    M->>M: record (clientID → seqNum)
    L-->>C: success
    

Note where durability lives: the log entry is fsync'd to BoltDB by the Raft library before Apply is ever called. FSM.Apply itself only mutates an in-memory map (server/fsm.go:170). The key-value data has no separate disk store — it is rebuilt from the log and snapshots on restart.

Exactly-once writes

A client whose connection drops mid-write does not know whether the write landed. If it retries and the original had in fact committed, a naive system applies it twice.

Two read paths

Both linearizable, trading latency against leader load.

sequenceDiagram
    autonumber
    participant C as kv-client
    participant L as Leader
    participant F as Follower
    participant P as Peers

    rect rgba(91,127,158,.10)
    Note over C,P: Leader read — VerifyLeader
    C->>L: Get(foo)
    L->>P: heartbeat to majority
    P-->>L: ACK
    L-->>C: value
    end

    rect rgba(168,129,63,.10)
    Note over C,P: Follower read — Read-Index (v1.3)
    C->>F: Get(foo, follower_read=true)
    F->>L: GetReadIndex()
    L->>P: confirm leadership
    L-->>F: commit_index = N
    F->>F: block until appliedIndex >= N
    F-->>C: value (served locally)
    end
    

Why the follower path is worth the complexity. A leader read costs the leader a round-trip to a majority on every read, so a read-heavy workload saturates the leader. Read-Index moves the serving work to followers while preserving the guarantee: the follower asks the leader only for a commit index — one small RPC — then waits until its own applied index reaches it. It never returns data older than the moment the read began.

Implemented in server/node.go:241-272 (follower side) and :415-430 (leader side). VerifyLeader() costs one cross-zone round-trip on GCP — estimated at roughly 15 ms, though note that no RTT measurement is committed to the repository.

Chapter 6Failure handling

What the implementation actually does — the behaviour observed under test, not textbook Raft.

stateDiagram-v2
    [*] --> Healthy
    Healthy --> LeaderLost: leader killed / partitioned
    LeaderLost --> Electing: heartbeat timer expires
    Electing --> Healthy: majority elects new leader
    Electing --> Unavailable: no majority reachable

    Healthy --> Partitioned: network split
    Partitioned --> MinorityBlocked: minority side
    Partitioned --> Healthy: majority side continues
    MinorityBlocked --> Healthy: partition heals, log catch-up

    Healthy --> NodeDown: process crash
    NodeDown --> CatchUp: restart
    CatchUp --> Healthy: AppendEntries or InstallSnapshot
    Unavailable --> Healthy: quorum restored
    

Chapter 7Chaos testing

Breaking the system on purpose, from below the application, where it cannot defend itself.

Injection mechanisms

Every fault is delivered by the sidecar agent using OS primitives. This matters: a fault injected inside the application could be caught, retried, or routed around by the application itself, which would make the test meaningless.

All in cmd/agent/main.go (:86, 159, 180, 201, 254, 261, 324).

The control dashboard

kv-dashboard drives all of it from a browser: pick a node, kill it, freeze it, partition it, add latency — and watch the cluster's reaction in the topology view and event log as it happens. It also runs the cluster locally, which makes the whole system reproducible on one machine without any cloud account.

Two tests that were passing for the wrong reason

Chapter 8Empirical results

Test suite

42/42 passing — 37 across six GCP fault-injection phases, plus 5 for follower reads in Phase 7. Separately, 21 Go unit tests cover the FSM (server/fsm_test.go).

Test IDs shown are representative, not exhaustive. Phase 6's denominator is not fully fixed — several checks report success without a matching failure branch, so they can drop out of the count rather than fail. See existing_issues.md §1.4.

The quorum bypass

The clearest result in the project: where latency lands matters far more than how much of it there is.

Durability and recovery

The crash-mid-burst count varies with timing (typically 5–10 writes acknowledged before the kill); the meaningful figure is the ratio, which was 100% every run.

Chapter 9Limitations

Stated plainly, because they bound what everything above means.

ReferenceGlossary

Every term used above, in one place.

Consensus

Getting several machines to agree on one value or one ordering, despite crashes and an unreliable network.

Raft

A consensus algorithm designed to be understandable. One elected leader, an ordered replicated log, and majority agreement.

CP / AP (CAP)

Under a network partition a system can favour consistency (CP — refuse to answer where correctness cannot be guaranteed) or availability (AP — always answer, risking stale or conflicting data). This system is CP.

Linearizability

The strongest single-object consistency guarantee: every operation appears to take effect instantaneously at some point between its start and its completion, so a read never returns data older than the most recent completed write.

Replicated log

The ordered list of state changes that Raft actually replicates. Applying the same entries in the same order gives every node the same state.

Term

Raft's logical clock. It increments on every election and lets a node detect that its information is stale.

Quorum / majority

⌊N/2⌋+1 nodes. Any two quorums overlap in at least one node, which is what makes two simultaneous leaders impossible.

Leader / follower / candidate

The three Raft roles. Followers accept entries; a follower that stops hearing from the leader becomes a candidate and stands for election; the winner becomes leader.

AppendEntries

The RPC the leader uses both to replicate log entries and, when empty, as a heartbeat proving it is alive.

Heartbeat timeout

How long a follower waits without hearing from the leader before standing for election. Randomized in [T, 2T) to prevent split votes.

Split vote

When several candidates start simultaneously and none reaches a majority, forcing a retry. Randomized timers exist to make this rare.

Split-brain

Two nodes both believing they are leader, accepting conflicting writes. Quorum overlap makes it arithmetically impossible in Raft.

Commit index / applied index

The commit index is the highest log entry known to be stored on a majority; the applied index is the highest entry a given node has actually executed against its state.

FSM (finite state machine)

The application state that log entries are applied to. Here, the key-value map plus the dedup table and peer routing table.

VerifyLeader

A round-trip to a majority confirming this node is still leader, run before serving a read so a deposed leader cannot return stale data.

Read-Index

A protocol letting a follower serve a linearizable read: it asks the leader for the current commit index, waits until its own applied index reaches it, then answers locally.

Snapshot / InstallSnapshot

A compacted image of the state machine, so the log need not be replayed from the beginning. A replica too far behind is caught up by shipping it a snapshot instead of individual entries.

Exactly-once semantics

Guaranteeing a retried request takes effect once, achieved here by tracking the last sequence number applied per client inside the FSM.

MTTR

Mean time to recovery — here, how long the cluster is without a leader after one is lost.

Chaos engineering

Deliberately injecting faults into a running system to check its guarantees hold in practice rather than only on paper.

iptables / tc netem

Linux kernel facilities for dropping packets and for adding delay or loss to a network interface. Used here to create real partitions and real latency below the application.

SIGKILL / SIGSTOP / SIGCONT

POSIX signals: kill a process outright (uncatchable), freeze it, and resume it. Freezing simulates a long GC pause or a hung process, which a plain crash cannot.

gRPC

The RPC framework used for client-to-node communication, on ports separate from Raft's own traffic.

BoltDB / bbolt

An embedded key-value store providing the fsync guarantees that let the Raft log survive a sudden crash.