Raft Consensus KV Store

Overview

A distributed key-value store with Raft consensus implemented from scratch in Python, plus a deterministic simulation harness that runs thousands of seeded chaos schedules against the real consensus code, and a from-scratch linearizability checker that verifies the client histories those runs produce.

Consensus code is easy to write and nearly impossible to trust from example-based tests, because the bugs live in message interleavings you never hit on a laptop loopback.

This project takes the FoundationDB position: the same RaftNode class runs unmodified on a real TCP cluster and inside a simulator where time, delivery order, loss, partitions, crashes, and clock skew are all derived from one seeded RNG. A failing seed replays its exact schedule every time.

Key features

• Raft core: randomized-timeout leader election, log replication with fast conflict backoff, commit advancement restricted to current-term entries, fsync'd crash-safe persistence with torn-tail truncation, snapshot-based log compaction with InstallSnapshot, and single-server membership changes.
• A KV state machine with get, put, delete, and cas, plus client sessions that deduplicate retried writes for exactly-once apply across leader failover.
• Linearizable reads through ReadIndex with heartbeat-quorum confirmation and no clock assumptions.
• Two transports behind one Env interface: asyncio TCP, and a deterministic simulated network with a virtual clock and seeded faults.
• A linearizability checker (Wing and Gong search with Lowe-style memoization, per-key decomposition) that rejects known-bad synthetic histories.

Verification

• pytest: 57 tests, including the paper's Figure 7 replication scenarios, torn-write recovery, membership changes over both transports, exactly-once failover retries, and real 3-node TCP cluster integration tests.
• A long randomized run: 5,000 seeds in 84.7s, 564,170 client ops total, 0 failures. Each seed is 12 virtual seconds of a 3-node cluster under partitions, crashes, 5% message loss, 5% duplication, and election-timer skew, with every completed history checked for linearizability.
• The harness has teeth: weakening the quorum rule makes the sweep detect split brain within a few dozen seeds.
• A real kill -9 leader-failover demo with no data lost.

Tech stack

• Python 3.12
• asyncio
• Zero runtime dependencies
• Deterministic simulation
• pytest

Challenges

• Python 3.12 changed asyncio Server.wait_closed() to wait for in-flight handlers, deadlocking shutdown; the fix tracks and closes every accepted writer before awaiting it.
• A fresh leader cannot serve ReadIndex reads before committing an entry in its own term, so pending reads register with no read index and get one when the leader's no-op commits.
• The Figure 7 tests could not be set up through real elections, so leadership is installed directly and the follower's timer frozen, keeping the scenario exact without weakening the vote rule.
• Bit-for-bit determinism required treating randomness as plumbing: one root seed fans out to per-node, network, nemesis, and client RNGs, and every event goes through a single (time, seq) heap.

What I learned

• Sans-IO is the whole ballgame for testable distributed systems: once the core stopped owning sockets and clocks, running 5,000 chaos schedules in 90 seconds became an ordinary function call.
• Exactly-once is a state machine feature, not a networking feature; the dedup table has to live inside the replicated state and its snapshots.
• Crash safety falls out of one discipline: never acknowledge before fsync, and make every on-disk structure atomic-rename or scan-and-truncate recoverable.
• Safety nets need their own tests; a checker that never fires is indistinguishable from one that cannot fire.