Linearized KV Store

Overview

Linearized KV Store is a three-node distributed database built as a 48-hour backend engineering exercise. It stores string key-value pairs behind a small HTTP API (GET / PUT / DELETE / CAS), but the actual point of the project is what happens underneath that API: a hand-rolled implementation of the Raft consensus algorithm that gives the cluster a single, ordered view of writes even as nodes crash and restart.

Rather than reaching for etcd, hashicorp/raft, or any existing consensus library, the project implements leader election, heartbeats, log replication, and durable recovery directly, forcing the implementation to reason about terms, commit indices, split votes, and crash consistency instead of treating consensus as a black box.

Problem

Most CRUD backends can get away with a single source of truth: one Postgres primary, one Redis instance, one writer. That model breaks the moment a single node is no longer enough, either because it becomes a single point of failure or because the system itself must remain available after machine failures.

The problem this project sets out to solve is narrower and more concrete than "build a database": given three independent nodes communicating only over HTTP and sharing no disk, how do you make writes durable, ordered, and survivable across node crashes without ever allowing two nodes to disagree about what was written?

That means solving, in order:

• Who is allowed to accept writes so conflicting histories never exist.
• When a write becomes safe so clients never observe data that disappears after a crash.
• How crashed nodes recover without corrupting replicated state.

Constraints

• Time-boxed scope. The implementation intentionally favors a correct distributed core over a feature-complete database.
• No consensus library. Leader election and replication are implemented directly instead of delegated to Raft frameworks.
• Crash-only fault model. Nodes may crash and restart, but malicious behavior is explicitly out of scope.
• Static cluster membership. The cluster consists of three fixed peers configured at startup.
• Filesystem persistence. Durability is implemented using an append-only Write-Ahead Log and snapshots rather than embedding another storage engine.

Key Engineering Decisions

Raft-style leader election over a fixed peer set

Every node starts as a Follower. Each runs its own randomized election timer (150–300 ms). If a follower stops receiving heartbeats before its timer expires, it increments its term, votes for itself, and requests votes from the remaining peers. The first node to receive a majority becomes the new leader and immediately begins sending heartbeats every 50 ms.

Reason

Randomized election timeouts dramatically reduce split votes, making leadership deterministic without centralized coordination.

Tradeoff

Election is timer-driven, so long GC pauses or network latency can occasionally trigger unnecessary elections.

A single leader gates all reads and writes

Only the current leader accepts PUT, DELETE, and CAS requests. Followers immediately reject client writes with 403, requiring clients to retry against the leader.

Reason

A single writer guarantees a globally ordered history of operations.

Tradeoff

Availability temporarily decreases whenever the leader becomes unavailable until a new leader is elected.

Commit only after majority acknowledgment

Every write is first appended to the leader's in-memory log and persisted to its Write-Ahead Log. The leader then replicates the entry to every follower using AppendEntries RPCs.

Only after a majority of nodes acknowledge the same entry does the leader advance the commit index, apply the operation to its state machine, and return success to the client.

Reason

Majority replication guarantees acknowledged writes survive the loss of any single node.

Tradeoff

Every write incurs at least one network round trip to a quorum before completing.

Write-ahead log plus periodic snapshots for recovery

Every accepted operation is written to wal.jsonl before being considered durable. Persistent node metadata such as the current term and vote are stored separately in state.json.

Every 50 committed operations, the key-value store is serialized into snapshot.json, allowing old log entries to be discarded.

After a crash, recovery follows a deterministic sequence:

1. Load the latest snapshot.
2. Replay remaining WAL entries.
3. Restore Raft metadata.
4. Rejoin the cluster.

Reason

Snapshots dramatically reduce recovery time by avoiding replaying the complete history.

Tradeoff

Snapshot generation introduces periodic disk I/O and synchronous log rewriting.

Explicit acknowledgment of what the system does not guarantee

Rather than presenting the implementation as production-ready, the project documents its own limitations.

Reads are served directly from the leader's memory instead of using a quorum-verified ReadIndex, meaning a partitioned leader could temporarily serve stale reads before stepping down.

A separate BYZANTINE_FAULT.md explains how the design would fail under malicious nodes and discusses the additional requirements for Byzantine fault tolerance.

Reason

Clearly defining the system's guarantees is just as important as implementing them.

Tradeoff

These limitations are intentionally documented rather than solved within the scope of the project.

Guarantees

• Writes are acknowledged only after replication to a majority.
• Nodes with stale logs cannot become leader.
• All writes pass through one leader, creating a single global history.

Does Not Guarantee

• Byzantine fault tolerance.
• Dynamic cluster membership.
• Read availability without quorum.
• Protection against stale reads from a partitioned leader.

Results

• Three-node Raft cluster deployable using a single docker compose up --build -d.
• HTTP API supporting GET, PUT, DELETE, and CAS.
• Concurrent integration tests verifying replicated writes and crash recovery.
• Leader failover tests confirming committed writes survive node failures.
• Internal status endpoint exposing node role, term, log length, and commit index.
• Companion documentation discussing Byzantine failures and system limitations.

Takeaways

Building a Raft implementation from first principles surfaces the parts of distributed systems that are easy to explain but difficult to implement correctly.

It demonstrates why election timeouts must be randomized, why log replication and state machine application are separate phases, and why durability and consensus solve different problems despite being tightly coupled.

Some of the biggest lessons from the project were:

• Consensus is primarily about handling disagreement rather than the happy path.
• Durability alone does not provide consistency, and consensus alone does not provide persistence.
• Explicitly documenting a system's guarantees and limitations is part of good engineering, not an afterthought.