Raft and Paxos, simulated

The diagram. Servers around the client. Each card shows the server’s role (follower, candidate, LEADER, down, or not in the configuration — dashed), its term, its vote, its commit index and last applied index, its log — one cell per index, the term on top and the key below (· a no-op, C a configuration entry, R a read), coloured by term, faded until committed on that server, the bar under it the commit index, a red outline where it conflicts with the leader, a dashed block for the snapshot — and its state machine (the key–value map). The ring is the election timer running down; the leader shows ♥ and, with lease reads, its lease. The lines between servers are network links: a cut link is red and dashed. Messages: RequestVote t3, vote ✓ / ✗, AE t3 #5–6 prev 4/t2 (AppendEntries with entries 5–6, after entry 4 of term 2), ♥ (a heartbeat with the leader’s commit index), ok ≤#6, ✗ #4 (the consistency check failed), InstallSnapshot, and the client’s SET / GET and replies. Tap a server to crash or restart it, make it time out, isolate it, cut single links, snapshot, read its local state, or add or remove it from the configuration; tap the client to write and read.

Counters. The leader, the highest term, elections, writes acknowledged, messages delivered and lost, and safety violations.

Do something. Client writes and reads (in any read mode), crash / restart / time out / isolate / snapshot a server, split the leader off with a minority, heal, drop the next message of a kind, 20% random loss, a slow link, and membership changes.

Logs. Every server’s log aligned by index (the last 24), with the term and command of each entry.

Servers. The persistent state (term, vote, log) and the volatile state (commit, applied, the leader’s nextIndex and matchIndex for each follower, the state machine).

Safety properties. Figure 3’s five guarantees, checked on every event: Election Safety, Leader Append-Only, Log Matching, Leader Completeness and State Machine Safety.

Client requests. Each request, the answer, which server answered, the latency and the tries.

Settings. Servers and spares, election timeout range, heartbeat interval, latency and jitter, entries per AppendEntries, snapshots, the read mode, the start-of-term no-op, fast backtracking and — to break it on purpose — the unsafe commit rule.

Elections (§5.2). Followers time out after a random 150–300 ms without hearing from a leader, become candidates in a new term, vote for themselves and send RequestVote. A server votes at most once per term (the vote is persistent) and only for a candidate whose log is at least as up to date as its own — a later last term, or the same term and at least as long (§5.4.1). A majority of the configuration wins; any message with a higher term makes a server adopt it and step down.

Replication (§5.3). The leader appends client commands and sends AppendEntries with prevLogIndex/prevLogTerm; a follower rejects if it lacks that entry, deletes entries only at a real conflict (never because an older message arrives late), appends, and advances its commit index to min(leaderCommit, last new entry). The leader keeps nextIndex and matchIndex per follower, backs nextIndex down by one on each rejection (or skips a whole conflicting term with fast backtracking, the optimisation sketched at the end of §5.3), and commits the highest index on a majority — only if it is from its own term (§5.4.2). A new leader appends a no-op so that happens promptly (§8).

Safety. The engine records the leader of every term, every committed and every applied entry, and flags Election Safety, Leader Completeness, Log Matching and State Machine Safety violations the moment they happen. With the correct rule they never do; with the unsafe rule the Figure 8 scenario produces them.

Crashes. A crash keeps term, vote, log and snapshot (stable storage) and loses everything else; a restarted server starts again from its snapshot as a follower. Messages to a down server or over a cut link are lost, including ones already on the way.

Clients (§8, thesis ch. 6). The client sends to the server it believes leads; followers redirect with a hint; with no answer within 700 ms it tries another server. A retried write already in the leader’s log is not appended twice (a simplified client session, thesis §6.3). Writes are answered once committed and applied on the leader.

Reads (thesis §6.4). ReadIndex: the leader records its commit index (once an entry of its own term is committed), confirms it still leads with a heartbeat round answered by a majority, and answers once it has applied up to it. Lease: after a majority acknowledges a heartbeat sent at time t, the leader answers reads locally until t + 0.9 × the minimum election timeout (§6.4.1, which assumes bounded clock drift). Through the log: the read is an entry. Local: any server answers from its own state — not linearizable, and flagged when stale.

Membership (thesis §4). One server at a time: a new server first catches up as a non-voting learner in rounds (§4.2.1), then the leader appends the new configuration; every server uses the newest configuration in its log at once, committed or not; the next change waits until it commits. A leader that removes itself commits the change without counting itself, then steps down (§4.2.2).

Snapshots (§7, thesis ch. 5). Each server snapshots its state machine (and configuration) independently after N applied entries and discards the log it covers; a follower whose nextIndex falls inside the leader’s snapshot gets InstallSnapshot, keeping any later entries that match.

Paxos. Phase 1: prepare(n) / promise (with the highest-numbered accepted proposal); phase 2: accept(n, v) with v forced to that proposal’s value if any (P2c); acceptors accept unless they promised higher, persist promises and accepted values across crashes, and send nacks so pre-empted proposers retry with a higher number after a fixed or random back-off. A learner counts accepted messages and reports a value chosen once a majority accepted the same proposal, and flags any instance with two chosen values. Multi-Paxos: one prepare covers every instance from the first open one; the leader then runs phase 2 alone per command and must re-propose any value a promise reports for an unfinished instance (§3).

No PreVote and no CheckQuorum (thesis §9.6, §6.2): a server cut off from the others keeps incrementing its term and disrupts the cluster when it returns — you can see it happen. A removed server that never learned of its removal is not prevented from disrupting either (§4.2.3).

Membership changes are single-server only; joint consensus (the paper’s §6) is described, not simulated.

The state machine is a key–value map of SET commands; client sessions are reduced to "do not append a retried request twice". Snapshots are taken instantly and sent in one message (no chunking).

Disk writes take no time and the network is a fixed latency with jitter, optional random loss, per-link delay and cut links; messages are never duplicated or corrupted.

Paxos uses a passive learner, has no leader election protocol of its own (Multi-Paxos leadership is whoever last completed phase 1) and fills no gaps with no-ops.

Timings are the paper’s (milliseconds), shown slowed down; real deployments use longer timeouts across data centres.