How to Build the Raft Consensus Algorithm in Python and Test It With Crashes, Partitions, and Planted Bugs

Imagine three servers that must keep the same list of commands in the same order, even when one of them crashes, the network splits in two, or messages arrive late and twice. Getting that right is called consensus, and it sits underneath many databases and cluster managers. The README of the etcd project’s Raft library says that library powers systems such as etcd, Kubernetes, Docker Swarm, CockroachDB and TiDB. Raft, the algorithm behind it, was published in 2014 by Diego Ongaro and John Ousterhout, and their paper describes it as “a consensus algorithm for managing a replicated log”.

In this tutorial you will build the core of Raft in about 240 lines of plain Python: leader election, log replication and the rule that decides when an entry is safe to act on. Then you will do what most tutorials skip and attack your own work. You will run the servers through a simulated network that crashes machines, cuts the network in two, and drops, duplicates and reorders messages, with a checker that watches Raft’s safety rules after every single event. Finally you will switch on five deliberate bugs, one at a time, and see which of them random testing finds (one is caught in 19,195 of 20,000 runs, another in none of 20,000) and which need a hand-written scenario, including the famous one from Figure 8 of the Raft paper.

One honest warning first. Everything here runs in one process on a fake clock and a fake network, and the “disk” is a Python attribute. That is what makes every run repeatable, and repeatable is what makes the tests possible, but it also means this is a teaching model and not a library to deploy. In production you would use a maintained implementation. What carries over is the understanding: which rule exists to stop which failure, and how to test for it.

What you will build, and the words you need first

By the end you will have:

• a Raft server written as a pure state machine (raft.py) with elections, log replication, the commit rule and a no-op entry at the start of each leadership;
• a deterministic simulated cluster (cluster.py) with a fake clock, message delays, loss, duplication, partitions, crashes and restarts;
• a checker for four of the five safety properties in Figure 3 of the paper, run after every event (the fifth, Leader Append-Only, holds by construction here because no leader code deletes log entries);
• random fault tests (chaos.py) and scripted replays of Figures 7 and 8 from the paper (scenarios.py);
• a pytest suite of 112 tests, plus a script that proves the suite notices each planted bug.

A few terms, defined before they are used. A state machine is any program whose state changes only by applying commands one at a time, for example a key-value store that applies set x=1. Two copies that apply the same commands in the same order always end in the same state, so if servers agree on the log (the ordered list of commands) they agree on everything. Each log entry holds a command and a term, a counter that goes up with every election; Raft allows at most one leader per term, so terms work like a logical clock that lets a server recognise stale messages. Entries are numbered from 1, and that number is the entry’s index.

Each server is a follower, a candidate (asking for votes) or the leader (the only server that accepts new commands and copies them to the others). A majority, also called a quorum, is more than half of the servers: 3 of 5. Any two majorities share at least one server, and nearly every Raft rule leans on that overlap. The paper puts the consequence this way: “a typical cluster of five servers can tolerate the failure of any two servers.” An entry is committed once it is safe to apply to the state machine, and applying means feeding it to the state machine. Servers talk through two request types, each with a reply: RequestVote (a candidate asks for a vote) and AppendEntries (a leader sends log entries, or sends none, in which case it is a heartbeat that says “I am still the leader”). A request and its reply together are called an RPC, a remote procedure call.

Prerequisites

• Python. Every command and output below came from Python 3.13.14 on Windows 11. The code uses only the standard library, and I did not test other versions.
• pytest 9.1.1, installed in Step 1, for the tests in Step 12.
• A bash shell. On Windows I used Git Bash. Linux and macOS need nothing extra.
• Background: you can read a Python class and a dataclass. You do not need any distributed systems experience, and the two bits of probability we use are explained where they appear.

Another thing worth knowing before you start: all the files go in one folder, the first line of each code block names its file, and a block whose first line says “(continued)” belongs at the end of the file that was started earlier.

Step 1: Create the project folder and install pytest

Make an empty folder and a virtual environment, which is a private set of installed packages for this project:

mkdir raft-lab && cd raft-lab
python -m venv .venv
source .venv/bin/activate        # Git Bash on Windows: source .venv/Scripts/activate
python -m pip install pytest==9.1.1
python -m pytest --version

The last command should print pytest 9.1.1. If it does not, the environment is probably not activated, so run the source line again. Nothing else needs installing, because the lab does not use any third-party package.

Step 2: Describe the messages and the state of one server

Create raft.py and start with the vocabulary: the entry type and the four message types. They are frozen dataclasses, which means they cannot be changed after creation. That matters in a simulation, because a message that is “on the wire” must not change if the sender later changes its own state, and for the same reason a list of entries is always sent as a tuple.

"""raft.py: one Raft server as a pure state machine (Ongaro and Ousterhout, 2014). Python 3.13, standard library only.

A node never sends anything itself. Every method returns a list of (destination, message) pairs and the caller (the
simulated network in cluster.py, or a real transport) delivers them. Time is an integer number of milliseconds that the
caller passes in, so every run is deterministic."""
from dataclasses import dataclass

FOLLOWER, CANDIDATE, LEADER = "follower", "candidate", "leader"
NOOP = "noop"


@dataclass(frozen=True)
class Entry:
    term: int
    command: str


@dataclass(frozen=True)
class RequestVote:
    term: int
    candidate_id: int
    last_log_index: int
    last_log_term: int


@dataclass(frozen=True)
class VoteReply:
    term: int
    vote_granted: bool


@dataclass(frozen=True)
class AppendEntries:
    term: int
    leader_id: int
    prev_log_index: int
    prev_log_term: int
    entries: tuple
    leader_commit: int


@dataclass(frozen=True)
class AppendReply:
    term: int
    success: bool
    prev_log_index: int  # echoed from the request so the leader knows which request this answers
    match_index: int     # on success: the last index the follower is now known to share with the leader

Each field maps to a field in Figure 2 of the paper. AppendEntries carries the entries to add, plus prev_log_index and prev_log_term, which describe the entry that comes just before them; Step 4 shows why. The paper’s reply has only a term and a success flag. I added two fields to AppendReply that echo the request’s prev_log_index and report the resulting match_index, because on a network that reorders and duplicates messages a leader has to be able to tell which request a late reply belongs to.

Now the server itself. This part holds the state, the clock handling and the one rule that every message obeys:

# raft.py (continued)
class Node:
    def __init__(self, node_id, peers, rng, *, election_timeout=(150, 300), heartbeat=50, noop=True, bugs=()):
        self.id = node_id
        self.peers = list(peers)
        self.rng = rng
        self.election_timeout = election_timeout
        self.heartbeat = heartbeat
        self.noop = noop
        self.bugs = frozenset(bugs)  # fault switches, all off by default; Step 9 turns them on
        self.apply_hook = None
        # "On disk": these three survive a crash (Figure 2, persistent state)
        self.current_term = 0
        self.voted_for = None
        self.log = []  # log[i - 1] is the entry at index i; index 0 is a virtual entry with term 0
        self._boot(0)

    def _boot(self, now):
        """Volatile state: everything a crash wipes out."""
        self.state = FOLLOWER
        self.leader_id = None
        self.commit_index = 0
        self.last_applied = 0
        self.applied = []  # the state machine: every real command applied so far, in order
        self.votes = set()
        self.next_index = {}
        self.match_index = {}
        self.next_heartbeat = None
        self.reset_election_timer(now)

    def restart(self, now):
        """Crash and reboot: only current_term, voted_for and log survive."""
        if "forget_vote" in self.bugs:
            self.voted_for = None  # fault switch: the vote was never written to disk
        self._boot(now)

    def quorum(self):
        return (len(self.peers) + 1) // 2 + 1

    def last_log(self):
        """(index, term) of the last entry, or (0, 0) for an empty log."""
        return (len(self.log), self.log[-1].term) if self.log else (0, 0)

    def reset_election_timer(self, now):
        self.election_deadline = now + self.rng.randint(*self.election_timeout)

    def next_wakeup(self):
        return self.next_heartbeat if self.state == LEADER else self.election_deadline

    def tick(self, now):
        """Call this when the clock reaches next_wakeup()."""
        if self.state == LEADER:
            return self.broadcast_append(now) if now >= self.next_heartbeat else []
        return self.start_election(now) if now >= self.election_deadline else []

    def on_message(self, src, msg, now):
        handler = {RequestVote: self.on_request_vote, VoteReply: self.on_vote_reply,
                   AppendEntries: self.on_append_entries, AppendReply: self.on_append_reply}[type(msg)]
        return handler(src, msg, now)

    def see_term(self, term, now):
        """Figure 2, all servers: a higher term always wins and demotes us to follower."""
        if term > self.current_term:
            was_leader = self.state == LEADER
            self.current_term = term
            self.voted_for = None
            self.state = FOLLOWER
            self.leader_id = None
            if was_leader:
                self.reset_election_timer(now)

Read it in three groups. First, the state. Three attributes (current_term, voted_for and log) are the server’s “disk”. Figure 2 calls them persistent state and says they are “Updated on stable storage before responding to RPCs”, which means a real server must write them to disk before it answers anything. Everything else is volatile, and _boot rebuilds it. That is exactly what restart() models: a crash wipes memory, and only the three disk attributes survive. Log indexes start at 1 as in the paper, so the entry at index i is log[i - 1].

Second, the arithmetic. quorum() returns more than half of the cluster, which is 2 of 3, 3 of 5 and 4 of 7. The etcd FAQ gives the same formula: “For a cluster with n members, quorum is (n/2)+1”, with the division rounded down. Third, time. The node never reads a clock. The caller passes the current time in milliseconds and calls tick() when next_wakeup() says a timer is due: a follower or candidate wakes at its election deadline, and a leader wakes when its next heartbeat is due. see_term implements the rule from Figure 2 that applies to every message: “If RPC request or response contains term T > currentTerm: set currentTerm = T, convert to follower”. A server that sees a newer term gives up whatever it was doing and forgets its vote, because votes belong to a term.

Notice that no method sends anything. Each one returns a list of (destination, message) pairs and leaves delivery to the caller. This is the design the etcd Raft library’s README describes: it models Raft as a state machine and gives this reason: “In order to easily test the Raft library, its behavior should be deterministic.” You will see the payoff in Step 6, where one tiny network model drives everything. You will also see a few lines containing if "something" in self.bugs. Those are fault switches, all off by default, and Step 11 turns them on one at a time to plant bugs on purpose.

Check that the file loads and that the quorum arithmetic is right. Create check_node.py:

# check_node.py: a first look at a fresh server
import random

from raft import Node

for size in (3, 5, 7):
    node = Node(1, list(range(2, size + 1)), random.Random(1))
    print(f"{size} servers: state={node.state} term={node.current_term} voted_for={node.voted_for} quorum={node.quorum()}")

Run python check_node.py:

3 servers: state=follower term=0 voted_for=None quorum=2
5 servers: state=follower term=0 voted_for=None quorum=3
7 servers: state=follower term=0 voted_for=None quorum=4

Every server starts as a follower in term 0 with no vote cast, and the quorum grows with the cluster as promised.

Step 3: Teach the server to hold an election

A follower that hears nothing from a leader for a random time between 150 and 300 milliseconds (the paper’s example range) decides the leader is gone and calls an election. It increases its term, votes for itself and asks everyone else for a vote. Add the election methods inside the Node class:

# raft.py (continued)
    # ---- election
    def start_election(self, now):
        self.state = CANDIDATE
        self.current_term += 1
        self.voted_for = self.id
        self.votes = {self.id}
        self.leader_id = None
        self.reset_election_timer(now)
        index, term = self.last_log()
        out = [(p, RequestVote(self.current_term, self.id, index, term)) for p in self.peers]
        if len(self.votes) >= self.quorum():  # a cluster of one
            out += self.become_leader(now)
        return out

    def on_request_vote(self, src, m, now):
        self.see_term(m.term, now)
        granted = False
        if m.term == self.current_term and self.voted_for in (None, m.candidate_id):
            mine = (self.last_log()[1], self.last_log()[0])  # compare the last term first, then the length
            theirs = (m.last_log_term, m.last_log_index)
            if theirs >= mine or "skip_vote_check" in self.bugs:  # fault switch: skip the up-to-date check
                granted = True
                self.voted_for = m.candidate_id
                self.reset_election_timer(now)
        return [(src, VoteReply(self.current_term, granted))]

    def on_vote_reply(self, src, m, now):
        self.see_term(m.term, now)
        if self.state == CANDIDATE and m.term == self.current_term and m.vote_granted:
            self.votes.add(src)
            if len(self.votes) >= self.quorum():
                return self.become_leader(now)
        return []

    def become_leader(self, now):
        self.state = LEADER
        self.leader_id = self.id
        self.next_index = {p: len(self.log) + 1 for p in self.peers}
        self.match_index = {p: 0 for p in self.peers}
        if self.noop:  # Section 8: commit something from this term, so older entries can be committed too
            self.log.append(Entry(self.current_term, NOOP))
        self.advance_commit()
        return self.broadcast_append(now)

start_election does exactly that, and it sends along the position of its last log entry, because the voters will want to see it. on_request_vote is where Raft’s safety begins. A voter answers three questions in order. Is this request from a term that has already passed? Have I already voted for someone else in this term? Is the candidate’s log at least as up to date as mine? Only three yeses earn a vote. Figure 2 states the last two as one rule: “If votedFor is null or candidateId, and candidate’s log is at least as up-to-date as receiver’s log, grant vote”.

“Up to date” has a precise meaning, and getting it wrong is a classic bug: compare the term of the last entries first, and only if they are equal compare the log lengths. Comparing tuples does that in one line, (last_log_term, last_log_index), because Python compares the first items first. The reason for the rule, in the paper’s words from Section 5.4.1: “Raft uses the voting process to prevent a candidate from winning an election unless its log contains all committed entries.” A committed entry sits on a majority of servers and a winner needs votes from a majority, so the two majorities overlap and some voter holds any given committed entry. That voter will not vote for a candidate whose log is less up to date than its own, and the paper’s Section 5.4.3 gives a proof sketch that this is enough to keep every committed entry in every future leader’s log.

Collecting votes is simple. A candidate keeps a set of the servers that voted for it, so a duplicated reply counts once, and when the set reaches a quorum it becomes leader. become_leader assumes every follower’s log matches its own (next_index is one past its last entry; the paper says a new leader initializes “all nextIndex values to the index just after the last one in its log”) and finds out otherwise by being refused, which Step 4 handles. Then comes a detail from Section 8 of the paper: a new leader appends a no-op entry, a command that does nothing, to its own log. The reason is that a leader cannot tell which entries from earlier terms are already committed, and “to find out, it needs to commit an entry from its term. Raft handles this by having each leader commit a blank no-op entry into the log at the start of its term.” You will measure why that matters in Step 11.

Check the voting rules before building anything else. Create check_vote.py. It makes a server whose last entry has term 2 and sends it four vote requests:

# check_vote.py: the voting rules, one decision at a time
import random

from raft import Entry, Node, RequestVote

node = Node(2, [1, 3], random.Random(1))
node.current_term = 2
node.log = [Entry(1, "a"), Entry(2, "b")]  # the last entry is at index 2 and has term 2

cases = [
    ("S1: longer log, older last term", 1, RequestVote(term=3, candidate_id=1, last_log_index=5, last_log_term=1)),
    ("S3: log exactly as up to date", 3, RequestVote(term=3, candidate_id=3, last_log_index=2, last_log_term=2)),
    ("S1 again: up to date, same term", 1, RequestVote(term=3, candidate_id=1, last_log_index=2, last_log_term=2)),
    ("S1: a term we have already passed", 1, RequestVote(term=2, candidate_id=1, last_log_index=2, last_log_term=2)),
]
for label, src, request in cases:
    reply = node.on_message(src, request, 0)[0][1]
    print(f"{label:<36} -> granted={reply.vote_granted!s:<5} (my term {node.current_term}, voted for {node.voted_for})")

Run python check_vote.py:

S1: longer log, older last term      -> granted=False (my term 3, voted for None)
S3: log exactly as up to date        -> granted=True  (my term 3, voted for 3)
S1 again: up to date, same term      -> granted=False (my term 3, voted for 3)
S1: a term we have already passed    -> granted=False (my term 3, voted for 3)

The first request comes from S1, whose log is longer (5 entries against 2) but whose last entry is older (term 1), and the voter refuses it: term beats length. S3 has a log exactly as up to date, so it gets the vote and the voter records it. When S1 asks again in the same term with an up-to-date log, it is refused, because a server votes for at most one candidate per term. The last request carries term 2, a term the voter has already passed (its own term became 3 when the first request arrived), so it is refused whatever its log looks like. Refusing anything older than your own term is the first line of defence against stale messages.

Step 4: Teach the leader to copy its log to the followers

A leader accepts a command by appending it to its own log, then sends the entries to every follower. The interesting part is the receiving side, because the follower must accept entries without ever letting its log drift away from the leader’s. Add the replication methods, still inside Node:

# raft.py (continued)
    # ---- replication
    def client_command(self, command, now):
        """Returns (index, messages). The index is None when this node is not the leader."""
        if self.state != LEADER:
            return None, []
        self.log.append(Entry(self.current_term, command))
        self.advance_commit()
        return len(self.log), self.broadcast_append(now)

    def broadcast_append(self, now):
        self.next_heartbeat = now + self.heartbeat
        return [(p, self.append_for(p)) for p in self.peers]

    def append_for(self, peer):
        prev = self.next_index[peer] - 1
        prev_term = self.log[prev - 1].term if prev > 0 else 0
        return AppendEntries(self.current_term, self.id, prev, prev_term, tuple(self.log[prev:]), self.commit_index)

    def on_append_entries(self, src, m, now):
        self.see_term(m.term, now)
        prev = m.prev_log_index
        if m.term < self.current_term:  # 1. a deposed leader
            return [(src, AppendReply(self.current_term, False, prev, 0))]
        self.state = FOLLOWER  # a candidate that hears from a leader of its own term steps down
        self.leader_id = m.leader_id
        self.reset_election_timer(now)
        has_prev = prev <= len(self.log) and (prev == 0 or self.log[prev - 1].term == m.prev_log_term)
        if "skip_prev_term_check" in self.bugs:  # fault switch: check that the entry exists, not that its term matches
            has_prev = prev <= len(self.log)
        if not has_prev:  # 2. the consistency check
            return [(src, AppendReply(self.current_term, False, prev, 0))]
        if "truncate_always" in self.bugs:  # fault switch: drop everything after prev, even entries that match
            del self.log[prev:]
        for offset, entry in enumerate(m.entries):
            index = prev + 1 + offset
            if index <= len(self.log) and self.log[index - 1].term != entry.term:
                del self.log[index - 1:]  # 3. a conflict: delete the entry and everything after it
            if index > len(self.log):
                self.log.append(entry)  # 4. append whatever is not already there
        if m.leader_commit > self.commit_index:  # 5. learn the commit point, but never past what this message proved
            self.commit_index = min(m.leader_commit, prev + len(m.entries))
            self.apply_committed()
        return [(src, AppendReply(self.current_term, True, prev, prev + len(m.entries)))]

On the leader side, append_for builds one message for one follower. It looks up the follower’s next_index, the index of the next entry that follower needs, and sends everything from there, together with the index and term of the entry just before (prev_log_index and prev_log_term) and the leader’s current commit_index. A heartbeat is simply the same message when there is nothing new to send, and tick sends one every 50 milliseconds. The follower’s side, on_append_entries, follows the five numbered rules of Figure 2 closely. I quote them as they appear in the paper:

1. “Reply false if term < currentTerm”. A message from a deposed leader is refused, and the reply carries the newer term so the old leader learns it has been replaced.
2. “Reply false if log doesn’t contain an entry at prevLogIndex whose term matches prevLogTerm”. This is the consistency check. The paper explains it as an induction step: if the follower has the same entry (same index and term) just before the new ones, then by induction its whole log up to that point is identical to the leader’s.
3. “If an existing entry conflicts with a new one (same index but different terms), delete the existing entry and all that follow it”. The loop deletes only on a conflict.
4. “Append any new entries not already in the log”. Entries the follower already has are skipped, which makes the whole message safe to receive twice.
5. “If leaderCommit > commitIndex, set commitIndex = min(leaderCommit, index of last new entry)”. A follower learns the commit point from the leader but never goes beyond what this particular message proved to match.

Rules 3 and 4 are easy to misread, and misreadings of them cause real bugs: the follower must delete only what conflicts, never everything after prev_log_index, because a delayed or duplicated message that carries older entries would otherwise cut off newer entries the follower has already acknowledged. Step 11 plants that exact bug. Section 5.6 of the paper makes the same point about duplicates: “Raft RPCs are idempotent”, and “if a follower receives an AppendEntries request that includes log entries already present in its log, it ignores those entries in the new request.” Note also that any valid AppendEntries resets the follower’s election timer, and that a candidate which receives one from a leader of its own term steps down.

Step 5: Decide when an entry is committed, and apply it

The last part of the node handles the leader’s side of the replies, advances the commit point, and applies committed entries to the state machine:

# raft.py (continued)
    # ---- commit
    def on_append_reply(self, src, m, now):
        self.see_term(m.term, now)
        if self.state != LEADER or m.term != self.current_term:
            return []
        if m.success:
            self.match_index[src] = max(self.match_index[src], m.match_index)
            self.next_index[src] = self.match_index[src] + 1
            self.advance_commit()
            return [(src, self.append_for(src))] if self.next_index[src] <= len(self.log) else []
        self.next_index[src] = max(1, min(self.next_index[src], m.prev_log_index))  # back up one entry and retry
        return [(src, self.append_for(src))]

    def advance_commit(self):
        """Figure 2, leaders: the highest N stored on a majority AND written in the current term."""
        for n in range(len(self.log), self.commit_index, -1):
            copies = 1 + sum(1 for p in self.peers if self.match_index[p] >= n)
            from_this_term = self.log[n - 1].term == self.current_term
            if copies >= self.quorum() and (from_this_term or "commit_old_terms" in self.bugs):  # fault switch
                self.commit_index = n
                self.apply_committed()
                return

    def apply_committed(self):
        while self.last_applied < self.commit_index:
            self.last_applied += 1
            entry = self.log[self.last_applied - 1]
            if entry.command != NOOP:
                self.applied.append(entry.command)
            if self.apply_hook:
                self.apply_hook(self.id, self.last_applied, entry)

When a follower answers success, the leader records how far that follower now matches its log (match_index), moves next_index just past it, and sends the next batch if any is left. When a follower answers failure, its log does not contain the entry the leader pointed at, so the leader steps next_index back and tries again. Eventually next_index reaches a point where the logs agree, and the next message succeeds; the paper describes it in nearly these words. Step 9 makes this visible.

advance_commit is the most delicate rule in the algorithm. The leader looks for the highest index n that is stored on a majority of servers (itself included) and whose entry was written in the leader’s current term. The paper’s wording is blunt: “Raft never commits log entries from previous terms by counting replicas. Only log entries from the leader’s current term are committed by counting replicas; once an entry from the current term has been committed in this way, then all prior entries are committed indirectly because of the Log Matching Property.” It looks like an arbitrary restriction. Step 11 shows what goes wrong without it, using the paper’s own Figure 8, and you will see the checker catch a committed entry being lost.

Finally apply_committed walks last_applied up to commit_index and feeds each real command to the state machine, which here is just a list called applied. A real server would fold the command into a key-value map. The apply_hook lets the simulation watch every application, and the checker will use it. The node is now complete: it can campaign, vote, replicate, repair, commit and apply. It still cannot talk to anyone, so the next step gives it a network.

Step 6: Build a simulated network and a safety checker

A cluster needs a network, and a test needs one that misbehaves on command and misbehaves the same way every time. Create cluster.py with a Cluster class that owns the servers, a fake clock and a queue of messages in flight:

"""cluster.py: a deterministic simulated network around Raft nodes, plus a checker for Raft's safety properties."""
import heapq
import itertools
import random

from raft import LEADER, Node


def fmt_log(log):
    return "[" + " ".join(f"{e.command}@{e.term}" for e in log) + "]"


class Cluster:
    def __init__(self, n=5, seed=1, *, delay=(5, 15), drop=0.0, dup=0.0, election_timeout=(150, 300),
                 heartbeat=50, noop=True, bugs=(), check=True):
        self.rng = random.Random(seed)
        self.now = 0
        ids = range(1, n + 1)
        self.nodes = {i: Node(i, [j for j in ids if j != i], random.Random(self.rng.getrandbits(32)),
                              election_timeout=election_timeout, heartbeat=heartbeat, noop=noop, bugs=bugs)
                      for i in ids}
        self.up = set(ids)
        self.groups = None  # None means fully connected; otherwise a list of sets that can talk to each other
        self.queue = []     # heap of (deliver_at, sequence, src, dst, message)
        self.seq = 0
        self.delay, self.drop, self.dup = delay, drop, dup
        self.sent = 0
        self.checker = Checker(self) if check else None
        for node in self.nodes.values():
            node.apply_hook = self.checker.on_apply if self.checker else None

    # ---- the network and the clock
    def live_nodes(self):
        return [self.nodes[i] for i in sorted(self.up)]

    def leaders(self):
        return [n for n in self.live_nodes() if n.state == LEADER]

    def connected(self, a, b):
        return self.groups is None or any(a in g and b in g for g in self.groups)

    def send(self, src, outgoing):
        for dst, msg in outgoing:
            if not self.connected(src, dst) or self.rng.random() < self.drop:
                continue
            self.sent += 1
            for _ in range(2 if self.rng.random() < self.dup else 1):  # a duplicate takes its own random delay
                self.seq += 1
                heapq.heappush(self.queue, (self.now + self.rng.randint(*self.delay), self.seq, src, dst, msg))

    def run_until(self, end, stop=None):
        """Process events up to simulated time `end` (ms). With `stop`, return True as soon as stop() holds."""
        while True:
            times = [self.nodes[i].next_wakeup() for i in self.up]
            if self.queue:
                times.append(self.queue[0][0])
            if not times or min(times) > end:
                break
            self.now = max(self.now, min(times))
            while self.queue and self.queue[0][0] <= self.now:
                _, _, src, dst, msg = heapq.heappop(self.queue)
                if dst in self.up and self.connected(src, dst):  # a message to a crashed or cut-off server is lost
                    self.send(dst, self.nodes[dst].on_message(src, msg, self.now))
            for i in sorted(self.up):
                if self.nodes[i].next_wakeup() <= self.now:
                    self.send(i, self.nodes[i].tick(self.now))
            if self.checker:
                self.checker.after_event()
            if stop and stop():
                return True
        self.now = max(self.now, end)
        return False

    def run_for(self, ms):
        return self.run_until(self.now + ms)

    def run_until_leader(self, limit):
        """Simulated time of the first moment a leader exists, or None if there is none by `limit` ms."""
        return self.now if self.run_until(limit, stop=lambda: bool(self.leaders())) else None

    # ---- things that happen to the cluster
    def client(self, node_id, command):
        """Hand a command to one server. Returns its log index if that server is a leader, otherwise None."""
        if node_id not in self.up:
            return None
        index, outgoing = self.nodes[node_id].client_command(command, self.now)
        self.send(node_id, outgoing)
        return index

    def crash(self, i):
        self.up.discard(i)

    def restart(self, i):
        self.nodes[i].restart(self.now)
        self.up.add(i)

    def partition(self, *groups):
        self.groups = [set(g) for g in groups]

    def heal(self):
        self.groups = None

    def timeout(self, i):
        """Make server i's election timer fire right now."""
        self.nodes[i].election_deadline = self.now

    def preload(self, term, entries, commit):
        """Start every server from the same committed history (used by the scripted scenarios)."""
        for node in self.nodes.values():
            node.current_term = term
            node.log = list(entries)
            node.commit_index = commit
            node.apply_committed()

    def show(self, title):
        print(f"--- {title} (t={self.now} ms)")
        for i in sorted(self.nodes):
            n = self.nodes[i]
            status = n.state if i in self.up else "down"
            print(f"S{i} {status:<9} term={n.current_term} commit={n.commit_index} log={fmt_log(n.log)}")

How the network and the clock work

All time is simulated. queue is a heap of messages ordered by delivery time, and send gives each message a random delay from the delay range. Because every message draws its own delay, a message sent later can arrive earlier, so reordering comes for free. drop is the chance that a message vanishes and dup is the chance that a second copy is delivered after its own random delay. partition splits the servers into groups that can only talk inside their group, and the check happens both when a message is sent and when it arrives, so a message already in flight is lost if the network is cut before it lands. A crashed server (crash) simply stops receiving; restart calls the node’s own restart, which wipes the volatile state.

run_until is the engine. It finds the next moment at which anything happens (a message arriving or a timer due), jumps the clock there, delivers the messages, ticks the timers, and runs the checker. An optional stop function ends the run early, which is how run_until_leader measures how long an election took. Two small helpers exist for scripted scenarios: timeout(i) makes server i’s election timer fire right now, and preload gives every server the same starting history. The whole thing is deterministic: the same seed produces the same run, down to the millisecond.

The cluster hands every applied entry to a Checker, so add that now, at the end of the same file:

# cluster.py (continued)
class InvariantViolation(Exception):
    def __init__(self, kind, detail):
        super().__init__(f"{kind}: {detail}")
        self.kind = kind
        self.detail = detail


class Checker:
    """Raft's safety properties (Figure 3 of the paper), checked after every simulated event."""

    def __init__(self, cluster):
        self.cluster = cluster
        self.leader_of_term = {}  # Election Safety
        self.applied = {}         # State Machine Safety: log index -> the entry first applied there by any server
        self.events = 0

    def on_apply(self, node_id, index, entry):
        first = self.applied.setdefault(index, entry)
        if first != entry:
            raise InvariantViolation(
                "state machine safety",
                f"S{node_id} applied {entry.command}@{entry.term} at index {index}, "
                f"but another server applied {first.command}@{first.term} there")

    def after_event(self):
        self.events += 1
        for node in self.cluster.live_nodes():
            if node.state == LEADER:
                self.check_leader(node)
        if self.events % 25 == 0:
            self.check_log_matching()

    def check_leader(self, node):
        known = self.leader_of_term.get(node.current_term)
        if known is None:  # first time we see a leader for this term
            self.leader_of_term[node.current_term] = node.id
            for index, entry in self.applied.items():  # Leader Completeness
                if index > len(node.log) or node.log[index - 1] != entry:
                    raise InvariantViolation(
                        "leader completeness",
                        f"S{node.id} won term {node.current_term} without {entry.command}@{entry.term}, "
                        f"which was already applied at index {index}")
        elif known != node.id:
            raise InvariantViolation("election safety", f"S{known} and S{node.id} both lead term {node.current_term}")

    def check_log_matching(self):
        for a, b in itertools.combinations(self.cluster.nodes.values(), 2):
            for k in range(min(len(a.log), len(b.log)), 0, -1):
                if a.log[k - 1].term == b.log[k - 1].term:
                    if a.log[:k] != b.log[:k]:
                        raise InvariantViolation(
                            "log matching", f"S{a.id} and S{b.id} agree on the term at index {k} but differ before it")
                    break

What the checker watches

Figure 3 of the paper lists five properties and says “Raft guarantees that each of these properties is true at all times.” A test that merely checks the final answer would miss a violation that heals itself, so the checker looks after every event. It covers four of the five:

• Election Safety: “at most one leader can be elected in a given term.” The checker remembers which server led each term and raises an error if a second one appears.
• Log Matching: “if two logs contain an entry with the same index and term, then the logs are identical in all entries up through the given index.” Every 25 events it compares every pair of logs, crashed servers included, because a log is persistent state. For each pair it finds the highest index where the terms agree and requires everything before it to be identical.
• Leader Completeness: “if a log entry is committed in a given term, then that entry will be present in the logs of the leaders for all higher-numbered terms.” The first time a leader for a new term appears, its log must contain every entry that any server has applied so far. Applied stands in for committed here, which is safe: a correct server applies an entry only after it is committed.
• State Machine Safety: “if a server has applied a log entry at a given index to its state machine, no other server will ever apply a different log entry for the same index.” on_apply remembers the first entry applied at each index anywhere and raises an error if a different one shows up.

The fifth property, Leader Append-Only, is not checked because the leader code only ever appends.

Run the first election

Create step01_first_election.py. It boots five servers, waits for a leader, sends three commands and looks at the logs:

# step01_first_election.py: five servers boot, elect a leader, and replicate three commands
from cluster import Cluster

cluster = Cluster(5, seed=3)
cluster.show("boot")
elected_at = cluster.run_until_leader(2000)
print(f"\nfirst leader after {elected_at} ms: S{cluster.leaders()[0].id}\n")
cluster.show("right after the election")
leader = cluster.leaders()[0]
for command in ("x=1", "y=2", "x=3"):
    index = cluster.client(leader.id, command)
    print(f"client -> S{leader.id}: {command!r} got log index {index}")
cluster.run_for(100)
print()
cluster.show("100 ms after the three commands")
print("\napplied by S1..S5:", [cluster.nodes[i].applied for i in sorted(cluster.nodes)])
print("messages sent so far:", cluster.sent)

Run python step01_first_election.py:

--- boot (t=0 ms)
S1 follower  term=0 commit=0 log=[]
S2 follower  term=0 commit=0 log=[]
S3 follower  term=0 commit=0 log=[]
S4 follower  term=0 commit=0 log=[]
S5 follower  term=0 commit=0 log=[]

first leader after 241 ms: S2

--- right after the election (t=241 ms)
S1 follower  term=1 commit=0 log=[]
S2 leader    term=1 commit=0 log=[noop@1]
S3 follower  term=1 commit=0 log=[]
S4 follower  term=1 commit=0 log=[]
S5 follower  term=1 commit=0 log=[]
client -> S2: 'x=1' got log index 2
client -> S2: 'y=2' got log index 3
client -> S2: 'x=3' got log index 4

--- 100 ms after the three commands (t=341 ms)
S1 follower  term=1 commit=4 log=[noop@1 x=1@1 y=2@1 x=3@1]
S2 leader    term=1 commit=4 log=[noop@1 x=1@1 y=2@1 x=3@1]
S3 follower  term=1 commit=4 log=[noop@1 x=1@1 y=2@1 x=3@1]
S4 follower  term=1 commit=4 log=[noop@1 x=1@1 y=2@1 x=3@1]
S5 follower  term=1 commit=4 log=[noop@1 x=1@1 y=2@1 x=3@1]

applied by S1..S5: [['x=1', 'y=2', 'x=3'], ['x=1', 'y=2', 'x=3'], ['x=1', 'y=2', 'x=3'], ['x=1', 'y=2', 'x=3'], ['x=1', 'y=2', 'x=3']]
messages sent so far: 72

Read it from the top. At boot every server is a follower in term 0 with an empty log. S2 won the first election after 241 simulated milliseconds, and its log already contains the no-op entry noop@1, which is written as command@term. The three client commands received indexes 2, 3 and 4, because index 1 belongs to the no-op. A hundred milliseconds later all five servers hold identical logs and commit=4, which means entries 1 to 4 are committed. The applied lists show the three real commands on every server, in the same order; the no-op is committed but is not a command for the state machine, so it does not appear there. The whole exchange took 72 messages. If your numbers differ slightly, check that you copied seed=3: a different seed is a different, equally valid election.

Step 7: Find out why election timeouts must be random

Everything now works with the default timeouts of 150 to 300 milliseconds. Why random? If two servers become candidates at almost the same moment, each votes for itself, the other voters split between them, and nobody reaches a majority. Everyone then waits for another timeout and tries again, and “without extra measures split votes could repeat indefinitely”, as the paper says. Its remedy is that “Raft uses randomized election timeouts to ensure that split votes are rare and that they are resolved quickly.” Let us measure how much randomness it takes. Create step02_election_timeouts.py. For each timeout range it boots 300 fresh five-server clusters (different seeds) and records when the first leader appears, on a fast network and a slower one:

# step02_election_timeouts.py: how much randomness do election timeouts need?
import statistics

from cluster import Cluster

SEEDS = 300
CAP = 10_000  # give up after 10 simulated seconds
for delay in [(1, 2), (5, 15)]:
    print(f"{SEEDS} five-server clusters per row, message delay {delay[0]} to {delay[1]} ms, give up after {CAP} ms")
    print(f"{'election timeout':<18}{'no leader':>10}{'median':>9}{'p95':>8}{'max':>8}{'split vote first':>18}")
    for low, high in [(150, 150), (150, 151), (150, 155), (150, 175), (150, 200), (150, 300)]:
        times, split = [], 0
        for seed in range(SEEDS):
            cluster = Cluster(5, seed, delay=delay, election_timeout=(low, high), check=False)
            t = cluster.run_until_leader(CAP)
            if t is None:
                continue
            times.append(t)
            split += cluster.leaders()[0].current_term > 1  # the first election is term 1, so a later term means a split vote
        never = SEEDS - len(times)
        if times:
            times.sort()
            row = f"{statistics.median(times):>9.0f}{times[int(0.95 * len(times)) - 1]:>8}{times[-1]:>8}{split / len(times):>18.1%}"
        else:
            row = f"{'-':>9}{'-':>8}{'-':>8}{'-':>18}"
        print(f"{f'{low}-{high} ms':<18}{never:>10}{row}")
    print()

Run python step02_election_timeouts.py:

300 five-server clusters per row, message delay 1 to 2 ms, give up after 10000 ms
election timeout   no leader   median     p95     max  split vote first
150-150 ms               300        -       -       -                 -
150-151 ms                 0      302     604    1054             55.3%
150-155 ms                 0      153     156     308              4.7%
150-175 ms                 0      156     164     173              0.0%
150-200 ms                 0      159     175     195              0.0%
150-300 ms                 0      171     220     243              0.0%

300 five-server clusters per row, message delay 5 to 15 ms, give up after 10000 ms
election timeout   no leader   median     p95     max  split vote first
150-150 ms               300        -       -       -                 -
150-151 ms               127     5583    9341    9949            100.0%
150-155 ms                 0     1084    3521    5647            100.0%
150-175 ms                 0      175     491    1141             29.3%
150-200 ms                 0      177     337     374              9.0%
150-300 ms                 0      187     240     406              0.3%

The “no leader” column counts runs that had no leader after 10 simulated seconds, and the median and percentile columns are computed over the runs that did elect one. “Split vote first” is the share of those runs whose first leader belongs to term 2 or later, meaning at least one election ended without a winner. Three things stand out.

First, with identical timeouts (150-150) no cluster ever elected a leader, in either network. All five servers time out in the same millisecond, all vote for themselves, none can win, and they repeat in lockstep forever. Real clocks are never that perfectly aligned, but the paper saw the same trend: “In the absence of randomness, leader election consistently took longer than 10 seconds in our tests due to many split votes.”

Second, in this model the width of the range has to be large compared with the message delay. On the fast network (delays of 1 to 2 milliseconds) a spread of 5 milliseconds is already enough: median 153 milliseconds and a split vote in 4.7 percent of runs. On the slower network (5 to 15 milliseconds) the same 5 milliseconds is hopeless: median 1,084 milliseconds and a 95th percentile of 3,521. The reason is simple. A candidate needs a full round trip to collect votes, and if another timer fires within that round trip, the two campaigns collide. A range of 150 to 300 milliseconds fixes both networks, with splits in 0.0 and 0.3 percent of runs, and a worst case of 243 and 406 milliseconds.

Third, a caution about comparing with the paper. Its Figure 16 reports, for a cluster of five servers with a broadcast time of roughly 15 milliseconds, a median downtime of 287 milliseconds with 5 milliseconds of randomness, and a worst case of 513 milliseconds with 50 milliseconds of randomness over 1,000 trials. That is far better than my slower-network row for a 5-millisecond spread (median 1,084), although the round trips are of a similar size. The setups differ: the paper measures how long its test cluster stays without a leader after the leader crashes, while this table measures the time from boot to the first leader in a model with uniformly random delays. Treat my table as a demonstration of the trend (no randomness is fatal, and the spread has to be wide compared with the network round trip), not as a reproduction of the paper’s numbers. The paper’s timing requirement in Section 5.6 is the thing to remember: “broadcastTime ≪ electionTimeout ≪ MTBF”, where the broadcast time is how long a server needs to send messages to every other server and get the replies, and MTBF is the average time between failures of a single server.

Step 8: Crash a leader, then strand a leader on the wrong side of a partition

Two failures matter most in practice: a leader dies, and a network split leaves an old leader talking to a minority. Create step03_failover.py:

# step03_failover.py: a leader crash, then a partition that strands a leader on the minority side
from cluster import Cluster

cluster = Cluster(5, seed=11)
cluster.run_until_leader(2000)
leader = cluster.leaders()[0]
for command in ("a", "b", "c"):
    cluster.client(leader.id, command)
cluster.run_for(100)
cluster.show("three commands committed everywhere")

crashed_at = cluster.now
cluster.crash(leader.id)
cluster.run_until(crashed_at + 5000, stop=lambda: bool(cluster.leaders()))
new_leader = cluster.leaders()[0]
print(f"\nS{leader.id} crashed at t={crashed_at} ms; S{new_leader.id} led term {new_leader.current_term} {cluster.now - crashed_at} ms later")
cluster.client(new_leader.id, "d")
cluster.run_for(100)
cluster.show(f"command d committed with S{leader.id} down")

print("\n=== a partition that strands a leader on the minority side")
cluster.restart(leader.id)
cluster.run_for(300)
old = cluster.leaders()[0]
buddy = next(i for i in cluster.nodes if i != old.id)
majority = set(cluster.nodes) - {old.id, buddy}
cluster.partition({old.id, buddy}, majority)
cluster.client(old.id, "lost")  # the stranded leader accepts it, but only one follower can ever copy it
cluster.run_for(1000)
new = next(n for n in cluster.leaders() if n.id in majority)
cluster.client(new.id, "e")
cluster.run_for(100)
cluster.show(f"partitioned: S{old.id} and S{buddy} on one side, the other three elected S{new.id}")
cluster.heal()
cluster.run_for(500)
print()
cluster.show("after the partition heals")
print("\napplied by every server:", {tuple(n.applied) for n in cluster.nodes.values()})

Run python step03_failover.py:

--- three commands committed everywhere (t=308 ms)
S1 leader    term=1 commit=4 log=[noop@1 a@1 b@1 c@1]
S2 follower  term=1 commit=4 log=[noop@1 a@1 b@1 c@1]
S3 follower  term=1 commit=4 log=[noop@1 a@1 b@1 c@1]
S4 follower  term=1 commit=4 log=[noop@1 a@1 b@1 c@1]
S5 follower  term=1 commit=4 log=[noop@1 a@1 b@1 c@1]

S1 crashed at t=308 ms; S4 led term 2 221 ms later
--- command d committed with S1 down (t=629 ms)
S1 down      term=1 commit=4 log=[noop@1 a@1 b@1 c@1]
S2 follower  term=2 commit=6 log=[noop@1 a@1 b@1 c@1 noop@2 d@2]
S3 follower  term=2 commit=6 log=[noop@1 a@1 b@1 c@1 noop@2 d@2]
S4 leader    term=2 commit=6 log=[noop@1 a@1 b@1 c@1 noop@2 d@2]
S5 follower  term=2 commit=6 log=[noop@1 a@1 b@1 c@1 noop@2 d@2]

=== a partition that strands a leader on the minority side
--- partitioned: S4 and S1 on one side, the other three elected S2 (t=2029 ms)
S1 follower  term=2 commit=6 log=[noop@1 a@1 b@1 c@1 noop@2 d@2 lost@2]
S2 leader    term=3 commit=8 log=[noop@1 a@1 b@1 c@1 noop@2 d@2 noop@3 e@3]
S3 follower  term=3 commit=8 log=[noop@1 a@1 b@1 c@1 noop@2 d@2 noop@3 e@3]
S4 leader    term=2 commit=6 log=[noop@1 a@1 b@1 c@1 noop@2 d@2 lost@2]
S5 follower  term=3 commit=8 log=[noop@1 a@1 b@1 c@1 noop@2 d@2 noop@3 e@3]

--- after the partition heals (t=2529 ms)
S1 follower  term=3 commit=8 log=[noop@1 a@1 b@1 c@1 noop@2 d@2 noop@3 e@3]
S2 leader    term=3 commit=8 log=[noop@1 a@1 b@1 c@1 noop@2 d@2 noop@3 e@3]
S3 follower  term=3 commit=8 log=[noop@1 a@1 b@1 c@1 noop@2 d@2 noop@3 e@3]
S4 follower  term=3 commit=8 log=[noop@1 a@1 b@1 c@1 noop@2 d@2 noop@3 e@3]
S5 follower  term=3 commit=8 log=[noop@1 a@1 b@1 c@1 noop@2 d@2 noop@3 e@3]

applied by every server: {('a', 'b', 'c', 'd', 'e')}

In the first half, three commands are committed everywhere, then the leader S1 crashes. S4 was elected leader of term 2, 221 milliseconds later, appended its own no-op, and committed command d with only four servers alive. Nothing that had been committed was lost: the four survivors still hold a b c.

The second half is the more instructive. S1 comes back as a follower, S4 is the leader, and the network splits so that S4 and S1 can only talk to each other while S2, S3 and S5 can only talk among themselves. S4 does not know it has been cut off, so it accepts the command lost and replicates it to S1, but two of five servers are not a majority, so the entry stays at commit=6 while its log grows to 7. On the other side, three servers are a majority: S2 won term 3 and committed e (note commit=8). Then the partition heals. S4 sees a message with term 3, steps down, and its log is rewritten to match the new leader’s; lost disappears. All five servers end up with a b c d e. That is allowed, and it is the heart of how Raft treats failures: nobody ever acknowledged lost, because it was never committed, so deleting it breaks no promise. A client that sent it to S4 would have timed out and tried again.

Step 9: Repair diverged logs, using Figure 7 of the paper

After several leader changes, followers can hold logs that differ from the new leader’s in messy ways. Figure 7 of the paper draws six such logs, labelled a to f, next to the log of a leader that has just won term 8. The caption says that a follower may be missing entries (cases a and b), may have extra uncommitted entries (cases c and d), or both (cases e and f). Instead of trusting the algorithm, let us feed it exactly those logs. Create scenarios.py with the paper’s logs and a function that builds a seven-server cluster from them, makes S1 (the log at the top of the figure) win term 8, and counts the AppendEntries messages the leader needs:

"""scenarios.py: scripted replays of the paper's Figures 7 and 8, and a double vote across a restart."""
import random

from cluster import Cluster, InvariantViolation, fmt_log
from raft import LEADER, Entry, Node

FIGURE7_LEADER = [1, 1, 1, 4, 4, 5, 5, 6, 6, 6]
FIGURE7_FOLLOWERS = {
    "a": [1, 1, 1, 4, 4, 5, 5, 6, 6],
    "b": [1, 1, 1, 4],
    "c": [1, 1, 1, 4, 4, 5, 5, 6, 6, 6, 6],
    "d": [1, 1, 1, 4, 4, 5, 5, 6, 6, 6, 7, 7],
    "e": [1, 1, 1, 4, 4, 4, 4],
    "f": [1, 1, 1, 2, 2, 2, 3, 3, 3, 3, 3],
}


def figure7(noop=True):
    """Seven servers with the logs from Figure 7. S1 (the top log) wins term 8; do the others end up with its log?"""
    cluster = Cluster(7, seed=1, delay=(1, 1), election_timeout=(10**9, 10**9), noop=noop)
    logs = [FIGURE7_LEADER] + list(FIGURE7_FOLLOWERS.values())
    for node, terms in zip(cluster.nodes.values(), logs):
        node.current_term = 7
        node.log = [Entry(t, f"e{i}") for i, t in enumerate(terms, 1)]
    before = {i: list(n.log) for i, n in cluster.nodes.items()}
    appends = {}  # how many AppendEntries messages the leader sent to each follower
    original_send = cluster.send

    def counting_send(src, outgoing):
        for dst, msg in outgoing:
            if type(msg).__name__ == "AppendEntries":
                appends[dst] = appends.get(dst, 0) + 1
        original_send(src, outgoing)

    cluster.send = counting_send

    def repaired():
        leaders = cluster.leaders()
        return bool(leaders) and all(n.log == leaders[0].log for n in cluster.live_nodes())

    cluster.timeout(1)
    cluster.run_until(1000, stop=repaired)
    return cluster, before, appends

Each log is a list of terms, one number per entry, as in the figure. The loop at the start gives each server its log and sets every term to 7, just below the election. Counting the messages is done by wrapping cluster.send. Now create step04_figure7.py:

# step04_figure7.py: the follower logs from Figure 7 of the Raft paper, repaired by a new leader
from scenarios import FIGURE7_FOLLOWERS, figure7


def terms(log):
    return " ".join(str(entry.term) for entry in log)


cluster, before, appends = figure7()
leader = cluster.leaders()[0]
print(f"S1 won term {leader.current_term}. Its log (terms only): {terms(before[1])}, plus a no-op of term {leader.current_term}\n")
for i, name in zip(range(2, 8), FIGURE7_FOLLOWERS):
    print(f"({name}) S{i}: {terms(before[i]):<25} -> {terms(cluster.nodes[i].log):<25} AppendEntries sent: {appends[i]}")
print("\nall seven logs identical:", len({tuple(n.log) for n in cluster.nodes.values()}) == 1, f"(t={cluster.now} ms)")

print("\nThe same experiment without the leader's no-op entry, after 1000 ms:")
cluster, before, appends = figure7(noop=False)
for i, name in zip(range(2, 8), FIGURE7_FOLLOWERS):
    if name in "cd":
        print(f"({name}) S{i}: {terms(before[i]):<25} -> {terms(cluster.nodes[i].log)}")
print("all seven logs identical:", len({tuple(n.log) for n in cluster.nodes.values()}) == 1)

Run python step04_figure7.py:

S1 won term 8. Its log (terms only): 1 1 1 4 4 5 5 6 6 6, plus a no-op of term 8

(a) S2: 1 1 1 4 4 5 5 6 6         -> 1 1 1 4 4 5 5 6 6 6 8     AppendEntries sent: 2
(b) S3: 1 1 1 4                   -> 1 1 1 4 4 5 5 6 6 6 8     AppendEntries sent: 7
(c) S4: 1 1 1 4 4 5 5 6 6 6 6     -> 1 1 1 4 4 5 5 6 6 6 8     AppendEntries sent: 1
(d) S5: 1 1 1 4 4 5 5 6 6 6 7 7   -> 1 1 1 4 4 5 5 6 6 6 8     AppendEntries sent: 1
(e) S6: 1 1 1 4 4 4 4             -> 1 1 1 4 4 5 5 6 6 6 8     AppendEntries sent: 6
(f) S7: 1 1 1 2 2 2 3 3 3 3 3     -> 1 1 1 4 4 5 5 6 6 6 8     AppendEntries sent: 8

all seven logs identical: True (t=17 ms)

The same experiment without the leader's no-op entry, after 1000 ms:
(c) S4: 1 1 1 4 4 5 5 6 6 6 6     -> 1 1 1 4 4 5 5 6 6 6 6
(d) S5: 1 1 1 4 4 5 5 6 6 6 7 7   -> 1 1 1 4 4 5 5 6 6 6 7 7
all seven logs identical: False

S1 won the election even though servers c and d refused to vote for it, because five of seven servers granted a vote and the quorum is 4. Look at the rows. Servers a and b are missing entries. Server a has 9 entries, so the leader’s first message, pointing at index 10, is refused, and the second, pointing at index 9, succeeds: 2 messages. Server b has only 4 entries, so the leader steps back one index at a time, 10, 9, 8 down to 4, and sends 7 messages (6 refused, 1 accepted). That one-step-at-a-time walk is what the paper describes, and the paper adds that “if desired, the protocol can be optimized to reduce the number of rejected AppendEntries RPCs”, which matters when a follower is thousands of entries behind but not in a small lab. Server f needs 8 messages because its log agrees with the leader’s only for the first 3 entries; its other 8 entries (terms 2 and 3) are deleted and replaced by the leader’s entries from index 4 on.

Servers c and d have extra entries (an eleventh entry of term 6, and eleventh and twelfth entries of term 7). Both needed one message. The leader’s first message points at index 10, which matches, and carries one entry: the no-op of term 8 at index 11. That entry conflicts with whatever the follower has at index 11, so rule 3 deletes the extra entries and the follower takes the leader’s. By 17 simulated milliseconds all seven logs are identical.

The second half of the output explains why the no-op matters here. When the leader does not write one, its log stays at 10 entries, there is nothing at index 11 to conflict with, and after a full second servers c and d still hold their extra entries. That is not a bug in the algorithm. The extra entries were never committed, the logs still satisfy Log Matching, and the leader will overwrite them as soon as it writes an entry at those positions. But it shows that a leader that stays quiet leaves old uncommitted entries lying around, and Step 11 shows the larger cost of staying quiet.

Step 10: Attack the cluster with random failures

Scripted scenarios test the failures you thought of. Random testing finds the ones you did not. Create chaos.py. A run starts a five-server cluster on a rough network (delays of 5 to 40 milliseconds, 5 percent of messages lost, 5 percent duplicated), then every 10 to 300 milliseconds picks one event at random: a client command sent to a random server (only a leader accepts it), a partition that cuts off one or two servers, a heal, a crash, or a restart. After 20 simulated seconds of that, it heals the network, restarts everyone, lets the cluster sit for 6 quiet seconds, and asks one more question: is there exactly one leader, and do all five servers have applied the same commands?

"""chaos.py: random crashes, partitions, message loss, duplication and reordering, with the safety checker switched on."""
import random

from cluster import Cluster, InvariantViolation

ACTIONS = ["client", "partition", "heal", "crash", "restart"]
WEIGHTS = [45, 15, 12, 12, 16]  # how often each kind of event is picked


def chaos_run(seed, *, nodes=5, duration=20_000, quiet=6_000, bugs=(), noop=True):
    """One randomized run. Returns (violation or None, converged, cluster)."""
    cluster = Cluster(nodes, seed, delay=(5, 40), drop=0.05, dup=0.05, noop=noop, bugs=bugs)
    rng = random.Random(seed * 7919 + 1)
    ids = list(cluster.nodes)
    command = 0
    try:
        while cluster.now < duration:
            cluster.run_until(cluster.now + rng.randint(10, 300))
            action = rng.choices(ACTIONS, WEIGHTS)[0]
            if action == "client":
                command += 1
                cluster.client(rng.choice(ids), f"c{command}")
            elif action == "partition":
                side = set(rng.sample(ids, rng.randint(1, nodes // 2)))
                cluster.partition(side, set(ids) - side)
            elif action == "heal":
                cluster.heal()
            elif action == "crash":
                cluster.crash(rng.choice(ids))
            else:
                down = [i for i in ids if i not in cluster.up]
                if down:
                    cluster.restart(rng.choice(down))
        cluster.heal()  # then a quiet period: no failures, no new commands
        for i in ids:
            if i not in cluster.up:
                cluster.restart(i)
        cluster.run_until(cluster.now + quiet)
    except InvariantViolation as violation:
        return violation, False, cluster
    converged = len(cluster.leaders()) == 1 and len({tuple(n.applied) for n in cluster.nodes.values()}) == 1
    return None, converged, cluster


def chaos_row(args):
    """One run as a small picklable tuple, so a process pool can fan the seeds out."""
    seed, bugs, noop = args
    violation, converged, cluster = chaos_run(seed, bugs=bugs, noop=noop)
    checker = cluster.checker
    return (seed, violation.kind if violation else None, converged, len(checker.applied),
            len(checker.leader_of_term), cluster.sent)

The checker raises an InvariantViolation the moment any safety property breaks, and chaos_run catches it and returns it. The final question is a liveness check: not “did anything bad happen” but “does the cluster get back to work once the failures stop”. chaos_row returns a small tuple so that a pool of processes can run many seeds in parallel. Create step05_chaos.py to run 1,000 of them against the correct implementation:

# step05_chaos.py: the correct implementation under random crashes, partitions, loss, duplication and reordering
from concurrent.futures import ProcessPoolExecutor

from chaos import chaos_row

if __name__ == "__main__":
    SEEDS = 1000
    with ProcessPoolExecutor() as pool:
        rows = list(pool.map(chaos_row, [(seed, (), True) for seed in range(SEEDS)], chunksize=20))
    violations = [r for r in rows if r[1]]
    print(f"runs: {len(rows)} (5 servers, 20 s of failures, then 6 s of quiet each)")
    print(f"safety violations: {len(violations)}")
    print(f"runs that ended with one leader and identical applied commands on every server: {sum(r[2] for r in rows)}")
    print(f"leaders elected across all runs: {sum(r[4] for r in rows)} (mean {sum(r[4] for r in rows) / len(rows):.1f} per run)")
    print(f"log entries committed across all runs: {sum(r[3] for r in rows)}")
    print(f"messages sent: {sum(r[5] for r in rows):,}")

Run python step05_chaos.py:

runs: 1000 (5 servers, 20 s of failures, then 6 s of quiet each)
safety violations: 0
runs that ended with one leader and identical applied commands on every server: 1000
leaders elected across all runs: 12303 (mean 12.3 per run)
log entries committed across all runs: 21022
messages sent: 2,968,706

No safety violation in 1,000 runs, and all 1,000 recovered. The averages say the runs were not gentle: 12.3 leaders were elected per run, so the cluster elected about a dozen leaders in each simulated 26 seconds, and across all runs 21,022 log entries were committed (counting each index once per run, no-ops included) over almost 3 million messages. Keep the limits of this evidence in mind. A checker can only find violations, and zero violations in 1,000 runs is evidence, not proof. It also checks the model in this folder, not a real deployment. The next step shows how much that evidence is worth, by testing the tests.

Step 11: Plant bugs and see who notices

A checker that has never failed is a checker you cannot trust yet. The five fault switches you saw in raft.py each break one rule of Figure 2 in the way a real implementation might, and they are all off by default:

Create step06_faults.py. For the correct code and then for each fault switch it runs 20,000 random runs, counts how many produced a violation, and reports which property tripped:

# step06_faults.py: switch on one fault at a time and see whether the random tests notice
import sys
from collections import Counter
from concurrent.futures import ProcessPoolExecutor

from chaos import chaos_row

FAULTS = ["skip_vote_check", "commit_old_terms", "forget_vote", "truncate_always", "skip_prev_term_check"]

if __name__ == "__main__":
    SEEDS = int(sys.argv[1]) if len(sys.argv) > 1 else 20_000
    print(f"{SEEDS:,} random runs per row")
    print(f"{'fault switch':<22}{'caught':>8}   {'caught as':<78}{'first seed'}")
    with ProcessPoolExecutor() as pool:
        for fault in [None] + FAULTS:
            bugs = (fault,) if fault else ()
            rows = list(pool.map(chaos_row, [(seed, bugs, True) for seed in range(SEEDS)], chunksize=50))
            kinds = Counter(r[1] for r in rows if r[1])
            first = min((r[0] for r in rows if r[1]), default="-")
            print(f"{fault or '(none)':<22}{sum(kinds.values()):>8,}   {str(dict(kinds)) if kinds else '-':<78}{first}")

Run python step06_faults.py. It takes about two minutes on a 14-core machine, and passing a smaller number, such as python step06_faults.py 2000, makes it quicker:

20,000 random runs per row
fault switch            caught   caught as                                                                     first seed
(none)                       0   -                                                                             -
skip_vote_check         19,195   {'leader completeness': 19182, 'state machine safety': 13}                    0
commit_old_terms             0   -                                                                             -
forget_vote                  4   {'election safety': 4}                                                        2768
truncate_always             73   {'leader completeness': 71, 'state machine safety': 2}                        524
skip_prev_term_check     5,482   {'state machine safety': 4801, 'log matching': 680, 'leader completeness': 1} 4

The correct code is clean in 20,000 runs, so the checker does not cry wolf. Then the faults split into three groups:

• Loud faults. skip_vote_check is caught in 19,195 of 20,000 runs (96 percent), nearly always as a Leader Completeness violation: a server with a stale log wins an election and lacks entries that were already applied elsewhere. skip_prev_term_check is caught in 5,482 runs (27 percent), mostly as State Machine Safety and sometimes as Log Matching, which is the property that the consistency check exists to protect.
• Rare faults. truncate_always is caught in only 73 runs, and forget_vote in 4 (always as Election Safety). They need an unlucky interleaving, such as a stale or duplicated AppendEntries arriving after newer ones, or a server crashing between two votes at just the wrong moment.
• An invisible fault. commit_old_terms was caught in none of 20,000 runs. The lesson is that random testing finds gross mistakes well and subtle ones badly, and for the subtle ones you need a scenario written by someone who understands the rule. The Raft paper supplies exactly that for the commit rule.

Figure 8: why a leader never commits old entries by counting replicas

Section 5.4.2 of the paper says: “Figure 8 illustrates a situation where an old log entry is stored on a majority of servers, yet can still be overwritten by a future leader.” Here it is as code. Add the rest of scenarios.py; the function replays the paper’s panels a to e on five servers, and each comment says which step of the story a line belongs to:

# scenarios.py (continued)
def figure8(bugs=(), extra_entry=False):
    """Figure 8 of the paper. Returns (cluster, violation or None). Every log starts as [a@1], committed."""
    cluster = Cluster(5, seed=1, delay=(1, 1), election_timeout=(10**9, 10**9), noop=False, bugs=bugs)
    cluster.preload(term=1, entries=[Entry(1, "a")], commit=1)
    try:
        cluster.timeout(1)
        cluster.run_for(10)                       # (a) S1 wins term 2 with every vote
        cluster.partition({1, 2}, {3, 4, 5})
        cluster.client(1, "x")
        cluster.run_for(10)                       #     x@2 reaches S2 only
        cluster.crash(1)
        cluster.timeout(5)
        cluster.run_for(10)                       # (b) S5 wins term 3 with the votes of S3 and S4 ...
        cluster.partition({5}, {1, 2}, {3, 4})
        cluster.client(5, "y")
        cluster.run_for(10)                       #     ... accepts y@3, and is cut off before replicating it
        cluster.crash(5)
        cluster.restart(1)
        cluster.partition({1, 2, 3}, {4}, {5})
        cluster.timeout(1)
        cluster.run_for(10)                       # (c) S1 campaigns for term 3 and loses (S3 already voted for S5)
        cluster.timeout(1)
        cluster.run_for(10)                       #     then wins term 4 and copies x@2 to S2 and S3
        if extra_entry:
            cluster.client(1, "z")
            cluster.run_for(10)                   # (e) a term-4 entry on a majority commits x indirectly
        cluster.crash(1)
        cluster.restart(5)
        cluster.heal()
        cluster.timeout(5)
        cluster.run_for(10)                       # (d) S5 campaigns for term 4 and fails (S2 and S3 already voted)
        cluster.timeout(5)
        cluster.run_for(10)                       #     then campaigns for term 5: can it win?
    except InvariantViolation as violation:
        return cluster, violation
    return cluster, None

The story in words. Every server starts with entry a committed. S1 wins term 2 and copies a new entry x@2 to S2 only, then crashes. S5 wins term 3 with the votes of S3 and S4, accepts its own entry y@3, and is cut off before replicating it. S1 restarts, loses a campaign for term 3 (S3 already voted for S5), wins term 4, and copies x@2 to S3. Now x@2 is stored on S1, S2 and S3, a majority. If S1 counts that as committed and crashes again, S5 can come back, fail once in term 4 (S2 and S3 have already voted for S1 there) and then win term 5 with votes from S2, S3 and S4, because its last entry has term 3, newer than the term 2 of everything S2 and S3 hold. The vote rule allows it, and S5’s log then replaces x@2 with y@3 on every server. Create step07_figure8.py to run three versions of the scenario:

# step07_figure8.py: the paper's Figure 8, with and without the "only commit entries from your own term" rule
from scenarios import figure8

CASES = [
    ("rule as written, no new entry in term 4", (), False),
    ("fault switch commit_old_terms, no new entry in term 4", ("commit_old_terms",), False),
    ("rule as written, plus z@4 on a majority (panel e)", (), True),
]
for title, bugs, extra in CASES:
    cluster, violation = figure8(bugs, extra)
    print(f"##### {title}")
    cluster.show("end of the scenario")
    print("checker:", violation if violation else "no violation")
    print()

Run python step07_figure8.py:

##### rule as written, no new entry in term 4
--- end of the scenario (t=80 ms)
S1 down      term=4 commit=0 log=[a@1 x@2]
S2 follower  term=5 commit=1 log=[a@1 y@3]
S3 follower  term=5 commit=1 log=[a@1 y@3]
S4 follower  term=5 commit=1 log=[a@1 y@3]
S5 leader    term=5 commit=0 log=[a@1 y@3]
checker: no violation

##### fault switch commit_old_terms, no new entry in term 4
--- end of the scenario (t=72 ms)
S1 down      term=4 commit=2 log=[a@1 x@2]
S2 follower  term=5 commit=1 log=[a@1 x@2]
S3 follower  term=5 commit=1 log=[a@1 x@2]
S4 follower  term=5 commit=1 log=[a@1]
S5 leader    term=5 commit=0 log=[a@1 y@3]
checker: leader completeness: S5 won term 5 without x@2, which was already applied at index 2

##### rule as written, plus z@4 on a majority (panel e)
--- end of the scenario (t=90 ms)
S1 down      term=4 commit=3 log=[a@1 x@2 z@4]
S2 follower  term=5 commit=1 log=[a@1 x@2 z@4]
S3 follower  term=5 commit=1 log=[a@1 x@2 z@4]
S4 follower  term=5 commit=1 log=[a@1]
S5 candidate term=5 commit=0 log=[a@1 y@3]
checker: no violation

In the first run, with the rule as written, S1 never commits x@2 because it was written in term 2 and S1 is in term 4 (commit=0 after its restart). S5 wins term 5, and its log replaces x@2 with y@3 on S2 and S3 (S4 simply receives y@3). The checker is silent, and rightly so: nobody ever applied x, so nothing that was promised is lost. In the second run, with commit_old_terms switched on, S1 sees x@2 on three servers and commits it (commit=2), the state machine applies it, and then S5 wins term 5 without it. The checker stops the run at that moment with a Leader Completeness violation. S2 and S3 still show x@2 in the output only because the run stopped at S5’s election, before its first message could delete them. In the third run, S1 also replicates an entry from its current term, z@4, to a majority. That commits z and, “because of the Log Matching Property”, x with it (commit=3). S5 now campaigns in vain: S2 and S3 hold a term-4 entry and refuse a candidate whose last entry has term 3, so S5 is stuck as a candidate. This is why the rule exists: counting replicas is only safe for entries that a future leader is guaranteed to see.

Forget a vote and get two leaders

The persistence rule is also easy to demonstrate. Add the last scenario at the end of scenarios.py. It uses three servers, S1 and S2 both campaign for term 1, S3 votes for S1 and then reboots before S2’s request arrives:

# scenarios.py (continued)
def double_vote(bugs=()):
    """Three servers. S1 and S2 both campaign for term 1. S3 votes for S1, reboots, and then hears from S2."""
    ids = [1, 2, 3]
    nodes = {i: Node(i, [j for j in ids if j != i], random.Random(i), bugs=bugs) for i in ids}
    ask1 = dict(nodes[1].start_election(0))  # RequestVote for term 1 from S1 (to S2 and S3)
    ask2 = dict(nodes[2].start_election(0))  # RequestVote for term 1 from S2 (to S1 and S3)
    reply = nodes[3].on_message(1, ask1[3], 0)[0][1]
    nodes[1].on_message(3, reply, 0)         # S1 now has 2 of 3 votes
    nodes[3].restart(0)                      # S3 crashes and reboots before S2's request arrives
    reply = nodes[3].on_message(2, ask2[3], 0)[0][1]
    nodes[2].on_message(3, reply, 0)         # S2 has 2 of 3 votes only if S3 forgot its vote
    return [(i, n.current_term) for i, n in nodes.items() if n.state == LEADER]

Create step08_double_vote.py:

# step08_double_vote.py: a server that forgets its vote across a reboot lets two leaders share a term
from scenarios import double_vote

print("vote persisted (as in Figure 2):", double_vote())
print("fault switch forget_vote:       ", double_vote(("forget_vote",)))

Run python step08_double_vote.py:

vote persisted (as in Figure 2): [(1, 1)]
fault switch forget_vote:        [(1, 1), (2, 1)]

With the vote persisted, S3 remembers that it already voted for S1 in term 1, refuses S2, and only S1 becomes leader. With the forget_vote switch on, S3 votes twice in one term, and both S1 and S2 become leader of term 1. Two leaders accepting different commands for the same term is precisely the situation that terms and majorities exist to prevent. The fix costs nothing in the algorithm and everything in the implementation: write the vote to disk, and make sure it reached the disk, before sending the reply.

Why a new leader writes a no-op

The no-op entry from Step 3 looks like clutter, so measure what it buys. Create step09_noop.py, which runs the 1,000-run test from Step 10 twice, once with the no-op and once without. For every run that fails to recover, it looks inside the cluster to see why:

# step09_noop.py: why a new leader appends a no-op entry
from concurrent.futures import ProcessPoolExecutor

from chaos import chaos_row, chaos_run

if __name__ == "__main__":
    SEEDS = 1000
    with ProcessPoolExecutor() as pool:
        for noop in (True, False):
            rows = list(pool.map(chaos_row, [(seed, (), noop) for seed in range(SEEDS)], chunksize=20))
            print(f"no-op on election = {noop!s:<5}: safety violations {sum(1 for r in rows if r[1])}, "
                  f"runs that converged after 6 quiet seconds {sum(r[2] for r in rows)}/{SEEDS}")
            stuck = 0
            failed = [r[0] for r in rows if not r[2]]
            for seed in failed:  # look inside each run that did not converge
                leaders = chaos_run(seed, noop=noop)[2].leaders()
                stuck += len(leaders) == 1 and leaders[0].commit_index < len(leaders[0].log)
            if failed:
                print(f"   of those {len(failed)}, {stuck} had one leader holding log entries it had not committed")

Run python step09_noop.py:

no-op on election = True : safety violations 0, runs that converged after 6 quiet seconds 1000/1000
no-op on election = False: safety violations 0, runs that converged after 6 quiet seconds 920/1000
   of those 80, 80 had one leader holding log entries it had not committed

Neither version broke a safety rule, so the no-op is not about safety. It is about liveness. Without it, 80 of 1,000 runs were still not settled after 6 quiet seconds, and all 80 had the same shape: one leader holding log entries it had not committed, while the servers disagreed about which commands they had applied. After a leader change, the new leader holds entries from earlier terms and, by the rule you saw in Step 5, may not commit them by counting replicas. If no client sends it a new command, nothing from its own term ever reaches a majority, and the old entries stay unapplied on some servers. The no-op supplies that entry at once, as the paper says: “to find out, it needs to commit an entry from its term.” It also turned out to tidy up extra entries on followers, as you saw in Step 9.

Step 12: Turn the experiments into tests, then test the tests

Every experiment above becomes a regression test. Create test_raft.py:

"""test_raft.py: the article's scenarios as tests. Set RAFT_FAULT=skip_vote_check (or another switch) to run them against a broken node."""
import os

import pytest

from chaos import chaos_run
from cluster import Cluster
from raft import LEADER
from scenarios import FIGURE7_FOLLOWERS, double_vote, figure7, figure8

BUGS = tuple(filter(None, os.environ.get("RAFT_FAULT", "").split(",")))


def test_a_healthy_cluster_elects_one_leader_and_commits_everywhere():
    cluster = Cluster(5, seed=3, bugs=BUGS)
    assert cluster.run_until_leader(2000) is not None
    leader = cluster.leaders()[0]
    assert cluster.client(leader.id, "x=1") is not None
    assert cluster.client(leader.id, "y=2") is not None
    cluster.run_for(100)
    assert [n.applied for n in cluster.nodes.values()] == [["x=1", "y=2"]] * 5
    assert len(cluster.leaders()) == 1


def test_a_follower_refuses_client_commands():
    cluster = Cluster(3, seed=1, bugs=BUGS)
    cluster.run_until_leader(2000)
    follower = next(n for n in cluster.live_nodes() if n.state != LEADER)
    assert cluster.client(follower.id, "x") is None


def test_committed_entries_survive_a_leader_crash():
    cluster = Cluster(5, seed=11, bugs=BUGS)
    cluster.run_until_leader(2000)
    old = cluster.leaders()[0]
    for command in "abc":
        cluster.client(old.id, command)
    cluster.run_for(100)
    cluster.crash(old.id)
    assert cluster.run_until(cluster.now + 5000, stop=lambda: bool(cluster.leaders()))
    cluster.client(cluster.leaders()[0].id, "d")
    cluster.run_for(100)
    assert {tuple(n.applied) for n in cluster.live_nodes()} == {("a", "b", "c", "d")}


def test_a_stranded_leader_cannot_commit_and_its_entry_is_overwritten():
    cluster = Cluster(5, seed=11, bugs=BUGS)
    cluster.run_until_leader(2000)
    old = cluster.leaders()[0]
    cluster.client(old.id, "a")
    cluster.run_for(100)
    buddy = next(i for i in cluster.nodes if i != old.id)
    majority = set(cluster.nodes) - {old.id, buddy}
    cluster.partition({old.id, buddy}, majority)
    cluster.client(old.id, "lost")
    cluster.run_for(1000)
    assert old.commit_index < len(old.log)  # the entry is on two of five servers and never commits
    cluster.client(next(n for n in cluster.leaders() if n.id in majority).id, "e")
    cluster.run_for(100)
    cluster.heal()
    cluster.run_for(500)
    assert {tuple(n.applied) for n in cluster.nodes.values()} == {("a", "e")}
    assert len(cluster.leaders()) == 1


def test_figure7_logs_are_repaired_in_the_expected_number_of_rounds():
    cluster, before, appends = figure7()
    leader = cluster.leaders()[0]
    assert all(n.log == leader.log for n in cluster.live_nodes())
    assert [appends[i] for i in range(2, 2 + len(FIGURE7_FOLLOWERS))] == [2, 7, 1, 1, 6, 8]


def test_figure8_an_uncommitted_entry_may_be_overwritten_but_nothing_committed_is_lost():
    cluster, violation = figure8(BUGS)
    assert violation is None
    assert cluster.nodes[5].state == LEADER and cluster.nodes[5].log[-1].command == "y"


def test_figure8_panel_e_a_current_term_entry_protects_x():
    cluster, violation = figure8(BUGS, extra_entry=True)
    assert violation is None
    assert not cluster.leaders()  # S5 cannot win: S2 and S3 hold a term-4 entry


def test_the_figure8_fault_is_caught_by_the_directed_scenario():
    _, violation = figure8(("commit_old_terms",))
    assert violation is not None and violation.kind == "leader completeness"


def test_a_persisted_vote_prevents_two_leaders_in_one_term():
    assert double_vote(BUGS) == [(1, 1)]
    assert double_vote(("forget_vote",)) == [(1, 1), (2, 1)]


@pytest.mark.parametrize("seed", [*range(100), 524, 2768])
def test_random_failures_never_break_safety_and_the_cluster_recovers(seed):
    violation, converged, _ = chaos_run(seed, bugs=BUGS)
    assert violation is None, violation
    assert converged


def test_without_the_no_op_some_runs_stay_unconverged():
    results = [chaos_run(seed, noop=False)[1] for seed in range(100)]
    assert not all(results)

The first tests are plain behaviour: an election, replication, refusing client commands on a follower, surviving a leader crash, a stranded leader losing its entry. Then come the scripted scenarios from the paper: Figure 7 must repair every log in exactly 2, 7, 1, 1, 6 and 8 messages, Figure 8 must lose nothing that was committed, and a persisted vote must prevent two leaders. The most important test is the parametrized one. It runs 100 random seeds plus two special ones, 524 and 2768, which are the seeds from the 20,000-run scan that exposed truncate_always and forget_vote. That is a general habit worth copying: when random testing finds a bug once, keep the seed forever. Finally, BUGS reads the RAFT_FAULT environment variable so the same tests can run against a deliberately broken server. Run python -m pytest -q:

................................................................................................................                                                   [100%]
112 passed in 2.32s

All 112 pass in a couple of seconds. Passing proves little on its own, so create step10_suite_vs_faults.py. It runs the whole suite once per fault switch and reports which tests turn red:

# step10_suite_vs_faults.py: does the test suite itself notice each fault switch?
import os
import re
import subprocess
import sys

for fault in ["", "skip_vote_check", "commit_old_terms", "forget_vote", "truncate_always", "skip_prev_term_check"]:
    env = dict(os.environ, RAFT_FAULT=fault, COLUMNS="170")
    done = subprocess.run([sys.executable, "-m", "pytest", "-q", "-p", "no:cacheprovider", "test_raft.py"],
                          capture_output=True, text=True, env=env)
    summary = re.sub(r" in [\d.]+s.*", "", done.stdout.strip().splitlines()[-1]).strip("= ")
    failed = sorted(set(re.findall(r"^FAILED test_raft.py::(\w+)", done.stdout, flags=re.M)))
    print(f"{fault or '(no fault)':<22} {summary:<24} {', '.join(failed[:3])}")

Run python step10_suite_vs_faults.py:

(no fault)             112 passed               
skip_vote_check        102 failed, 10 passed    test_figure8_panel_e_a_current_term_entry_protects_x, test_random_failures_never_break_safety_and_the_cluster_recovers
commit_old_terms       1 failed, 111 passed     test_figure8_an_uncommitted_entry_may_be_overwritten_but_nothing_committed_is_lost
forget_vote            2 failed, 110 passed     test_a_persisted_vote_prevents_two_leaders_in_one_term, test_random_failures_never_break_safety_and_the_cluster_recovers
truncate_always        2 failed, 110 passed     test_random_failures_never_break_safety_and_the_cluster_recovers
skip_prev_term_check   23 failed, 89 passed     test_random_failures_never_break_safety_and_the_cluster_recovers

Each fault turns at least one test red, and the table shows which layer did the catching. skip_vote_check breaks 102 tests: 101 random runs and the Figure 8 panel e test. commit_old_terms breaks exactly one, the Figure 8 test, and without that scenario the suite would have passed. forget_vote breaks the double-vote test and the remembered seed 2768. truncate_always is caught by just two random seeds: 524, which I kept from the scan, and 64, where no safety property breaks but the cluster has no leader after the quiet period, so it fails the recovery check. skip_prev_term_check turns 23 random runs red. That is the honest picture of a test suite for concurrent code: a few cheap directed tests for the rules you understand, many random runs for the ones you do not, and remembered seeds so that a bug found once cannot come back unnoticed.

Common mistakes, and the check for each

Comparing log lengths when voting

Voters must compare the term of the last entry first and the length only on a tie. Comparing lengths alone lets a long log full of stale entries beat a short log that holds committed ones. Check: the first line of the check_vote.py output must say granted=False, and a server that skips the whole comparison (skip_vote_check) is caught in 96 percent of random runs.

Committing an entry from an old term because it is on a majority

This is the Figure 8 bug, and the random tests never saw it in 20,000 runs. Check: the directed Figure 8 test. If you port this to another language, port that scenario first.

Answering a vote request before the vote is on disk

The persistent state in Figure 2 must be written “before responding to RPCs”. A real server needs a flush to stable storage, and this model only simulates it by keeping the attributes across restart(). Check: the double-vote scenario, and a regression seed for the random test.

Deleting too much, or too little, when appending entries

Delete only on a conflict, and skip entries you already have. Deleting everything after prev_log_index lets a delayed or duplicated message erase entries a follower already acknowledged (truncate_always). Never deleting a conflicting tail leaves a follower holding entries that disagree with the leader’s. Check: run your tests with message duplication and reordering switched on, as chaos.py does.

Checking that the previous entry exists but not its term

The consistency check compares the index and the term. Comparing only the length (skip_prev_term_check) lets a diverged follower accept entries it should have refused, and random runs caught it 27 percent of the time. Check: the Log Matching and State Machine Safety checks in the checker.

Using the same election timeout everywhere, or a range narrower than the network delay

Step 7 showed no leader at all with identical timeouts, and a 5-millisecond range failing badly on a network with 5 to 15 milliseconds of delay. Check: measure your own message round trip and make the range several times wider.

Leaving out the no-op

Safety survives, but 80 of 1,000 runs did not settle. Check: after a leader change with no new client commands, every server should still end up with the same applied commands.

Trusting a green random test

The invisible fault in Step 11 is the warning: a passing random run says nothing about interleavings it never visited. Keep directed scenarios for each rule in the paper, and keep every seed that ever found a bug.

Confirm the whole thing works end to end

From the project folder, with the environment activated, run every step and the tests. The lines below are the ones to look for; the full outputs are shown above.

python check_node.py                 # quorum 2, 3 and 4 for 3, 5 and 7 servers
python check_vote.py                 # refused, granted, refused, refused
python step01_first_election.py      # first leader after 241 ms: S2, identical logs, 72 messages
python step02_election_timeouts.py   # no leader at 150-150 ms in 300 of 300 runs, on both networks
python step03_failover.py            # ends with {('a', 'b', 'c', 'd', 'e')}
python step04_figure7.py             # all seven logs identical: True (t=17 ms)
python step05_chaos.py               # safety violations: 0, all 1000 runs recovered
python step07_figure8.py             # only the commit_old_terms run reports a violation
python step08_double_vote.py         # [(1, 1)] against [(1, 1), (2, 1)]
python step09_noop.py                # 1000/1000 against 920/1000 runs recovered
python -m pytest -q                  # 112 passed
python step10_suite_vs_faults.py     # every fault switch turns at least one test red
python step06_faults.py              # about two minutes: the 20,000-run table

If all of that matches, you have a Raft server that elects leaders, replicates and repairs logs, commits only what is safe, survives 1,000 randomized failure schedules without breaking a safety rule, and has tests that notice five different ways of getting it wrong.

What this model leaves out, and where to go next

• A real disk. A production server must flush the log and the term and vote to stable storage before replying, and survive half-written records. The write-ahead log tutorial on this site covers that half of the problem.
• Snapshots and log compaction. Here the log grows forever. The etcd Raft library’s README lists log compaction among its features.
• Membership changes. The cluster size is fixed. Chapter 4 of Ongaro’s thesis covers changing it safely, and the README says its implementation preserves “the key invariant that membership changes happen one node at a time”.
• Clients. There is no reply to a client, no protection against a command being applied twice, and no way to read. The paper’s Section 8 says what is needed: the solution to a command being applied twice is “for clients to assign unique serial numbers to every command”, so that the state machine can recognise a repeat, and a leader should “exchange heartbeat messages with a majority of the cluster before responding to read-only requests” so that it does not answer from stale state.
• Performance. This leader packs every entry a follower has not yet acknowledged into one message, however many there are, and sends them again at the next heartbeat if no reply has arrived. The README lists optional enhancements such as batching, optimistic pipelining, flow control and “automatic stepping down when the leader loses quorum”.
• A proof. The paper gives a proof sketch for Leader Completeness, and notes that “a formal specification” describes the algorithm more precisely; it points to Ongaro’s PhD thesis. A checker like ours finds bugs but cannot show their absence.

Related reading on this site: the leader election tutorial takes a different route to a single leader, with leases and fencing tokens, the pattern Kubernetes uses for its Lease API. The failure detector tutorial goes deeper on the question Raft’s election timeout answers crudely, namely how long silence should last before you accuse a server. The two-phase commit tutorial shows what a protocol that blocks when its coordinator dies looks like, which makes Raft’s answer easier to appreciate. If you would rather avoid coordination altogether for a narrower problem, the CRDT counter tutorial builds a counter that never needs a leader. For a production system, read the README of etcd-io/raft, which describes itself as “stable and feature complete”, and use a maintained library instead of this one.

Sources

• Diego Ongaro and John Ousterhout, In Search of an Understandable Consensus Algorithm (Extended Version), published May 20, 2014: Figures 2, 3, 7, 8 and 16, Sections 5.2 to 5.4, 5.6, 8 and 9.3.
• Diego Ongaro, Consensus: Bridging Theory and Practice, PhD thesis, Stanford University: cluster membership changes (Chapter 4).
• The etcd project, etcd-io/raft README: the library’s design as a deterministic state machine, its feature and enhancement lists, and its notable users.
• The etcd project, etcd FAQ: why quorum is (n/2)+1.