raft-py

Pure-Python implementation of the Raft consensus algorithm (Ongaro, 2014) with a deterministic simulated network, partition-injection primitives, and a correctness test suite that exercises election safety, log matching, and partition tolerance.

Follows In Search of an Understandable Consensus Algorithm, Figure 2, section-by-section. No external dependencies.

$ pytest tests/                  -> 12 passed in 0.08s
$ python examples/demo.py
  [1] Cold start: leader elected -> node 4 (term 1)
  [3] Network partition: isolate node 4
      -> new leader -> node 1 (term 2)
  [5] Heal the partition -> isolated node catches up
      State-machine consistency verified across all 5 nodes

Why this exists

Raft powers etcd, Consul, CockroachDB, TiKV, and most production distributed databases shipped after 2014. It's the canonical exam in distributed systems interviews. A clean from-scratch implementation, with deterministic tests of failure scenarios, is the best way to internalize:

• Election safety — at most one leader per term (section 5.2)
• Log matching — if two logs have the same (index, term), all prior entries are identical (section 5.3)
• Leader completeness — committed entries survive future elections (section 5.4.1, up-to-date vote requirement)
• Current-term commit rule — leaders only commit entries from their own term directly; older-term entries commit transitively (section 5.4.2, Figure 8 anomaly)
• State-machine safety — applied entries on different nodes match

All of the above are tested below.

Architecture

raft-py/
├── raft/
│   ├── __init__.py     - public surface
│   ├── rpc.py          - RequestVote, AppendEntries dataclasses (Fig 2)
│   ├── log.py          - 1-based replicated log with matching helpers
│   ├── network.py      - tick-driven simulated network with partitions
│   └── node.py         - the state machine (Follower / Candidate / Leader)
├── tests/
│   ├── helpers.py
│   ├── test_election.py
│   ├── test_replication.py
│   └── test_partition.py
└── examples/
    └── demo.py         - observable 5-node walkthrough

The simulated network

Time is virtual. Nothing happens until tick() is called. Each tick advances the world by one unit; messages have configurable latency and may be dropped at a configurable rate. This makes every scenario perfectly reproducible (same seed -> same election outcome, byte-for-byte).

Partition injection is one call:

net.isolate(4)                  # node 4 alone, rest together
net.partition([[1, 2], [3, 4, 5]])
net.heal()

Cross-partition messages are silently dropped (modelling unreachability), and reachability is re-checked at delivery time: a partition installed while messages are in flight still drops them.

The state machine

Role is one of FOLLOWER / CANDIDATE / LEADER. Transitions follow Ongaro Figure 2:

   ─── timeout ───►          ─── majority ───►
FOLLOWER       CANDIDATE                      LEADER
   ◄─── higher-term AE ───   ◄─── higher-term ───

Each node carries:

Field	Persistent?	Role
current_term	yes	all
voted_for	yes	all
log[]	yes	all
commit_index	no	all
last_applied	no	all
next_index[peer], match_index[peer]	no	leader only

(persistence is wired up but currently in-memory; v0.2.0 adds disk durability.)

Tests

pytest tests/ -> 12/12 passing on this run. Categories:

Election (5 tests)

• single_leader_emerges_in_quiet_cluster — 5 nodes, no failures, exactly one leader emerges
• election_safety_at_most_one_leader_per_term — invariant checked every tick for 2000 ticks
• 3_node_cluster_elects — smallest viable cluster
• new_election_when_leader_dies — isolating the leader provokes a fresh election in a higher term
• term_monotonically_increases — terms never go backwards

Replication (4 tests)

• committed_entry_replicated_to_all — leader submit → all 5 state machines apply it
• many_entries_consistent_ordering — 20 commands, every node's state-machine prefix matches
• follower_logs_match_leader_log_matching_property — for any common (idx, term), all prior entries are byte-identical
• submit_to_follower_rejected — only the leader accepts client writes

Partition tolerance (3 tests)

• minority_cannot_elect — 2-of-5 partition fails to find a majority
• majority_continues_to_make_progress — 4-of-5 commits new entries while 1 is isolated
• partition_heal_catches_up_lagging_node — formerly-isolated node syncs from the leader after heal

Demo walkthrough (real run)

t= 156  leader elected -> node 4 (term 1)
t= 356  after 5 client submits, all 5 nodes: log=5, commit=5, applied=5
t= 468  node 4 isolated; new leader -> node 1 (term 2)
        (note: node 4 still believes it is leader of term 1 - correct,
         it can't know it has been replaced while isolated)
t= 768  majority commits 5 more entries; isolated node 4 stuck at 5
t=1268  partition healed; node 4 catches up, steps down to follower
        ALL FIVE NODES: log=10, commit=10, applied=10, term=2

Run it

pytest tests/                  # 12 passed in ~0.1s
python examples/demo.py        # observable walkthrough

No pip install needed (stdlib only).

What's not here (yet)

The implementation is intentionally compact. Known production-grade extensions on the roadmap:

• Persistence — flush current_term, voted_for, log[] to disk on every change
• Log compaction — install snapshots when the log gets too large
• Cluster membership changes — single-server AddServer / RemoveServer
• Pre-vote — avoid disruptive elections from partitioned-then-reconnected nodes
• Leader transfer extension — graceful handoff for maintenance
• Faster log catch-up — fast-backoff nextIndex hint (currently decrements by 1)
• Real network — asyncio+TCP transport (the current Network is in-process; swapping it is a single class)

v0.2.0 will pick the first 2-3.

References

• Ongaro, D. & Ousterhout, J. (2014). In Search of an Understandable Consensus Algorithm. USENIX ATC. paper
• Ongaro, D. (2014). Consensus: Bridging Theory and Practice. PhD thesis, Stanford. (The 250-page version — covers everything in the v0.2.0 roadmap.)
• The Raft visualization — recommended for building intuition before reading code.