State machines, Raft & quorum

Learning goals

Explain log replication, election and quorum intersection; predict a three-voter cluster's behavior; inspect real crash and pause evidence.

Prerequisites: consistency contracts and durable local files.

Principle: one sequence, deterministic application

Replicas begin in the same state, agree on an ordered command log, and apply commands deterministically. Agreement on the sequence lets them compute the same state. Sources of nondeterminism—time, randomness, external calls—must be resolved or recorded as part of the design.

Raft separates leader election, log replication and safety rules. Terms identify election epochs. Voters grant at most one vote per term; a candidate must have a sufficiently up-to-date log. A leader replicates entries and advances commitment according to the protocol's current-term rule. Merely finding an entry on two disks is not a complete description of Raft commitment, especially across terms.

                 client
                   │
               leader n1
              ╱         ╲
         voter n2     voter n3
N = 3, majority = 2. Two majorities must intersect.
Intersection + voting/log rules preserve committed decisions.

Intersection ensures competing decisions cannot be justified by completely disjoint majorities. The log and voting rules make the overlap useful. With two reachable voters, a three-voter cluster can elect and commit under favorable scheduling. With one reachable voter it cannot form a majority. Election timeouts help progress; they are not a proof that the old leader is physically dead.

Consensus and atomic commit are separate problems

Raft decides an ordered log for one replicated group. Two-phase commit coordinates whether multiple transaction participants commit together. A prepared 2PC participant may wait for a coordinator's decision; using replicated services can improve coordinator durability, but the two protocols are not interchangeable. This experiment has one etcd consensus group and does not implement cross-shard transactions or 2PC.

Real experiment A: lose a leader, then lose quorum

1. Write an acknowledged value. Identify the leader through the maintenance status API.
2. Kill only that owned process with SIGKILL. Observe another leader, read the old value, and perform a new write.
3. Restart the original process with its original data directory. Check both values on that member.
4. Pause one follower with SIGSTOP. Send a write to a reachable member: two voters can still progress.
5. Resume, then pause two followers. Wait 1.4 seconds and issue a write and default linearizable read with 700 ms deadlines. Record unknown outcomes, resume both, and reconcile the write.

Run python3 scripts/run_all.py --repeats 3 after setup. The complete first-edition runner executes the three experiment families in each repetition. See all saved observations, including the value of the timed-out write after recovery. “No success by 700 ms” is the measured fact, not a universal latency bound.

Boundary: these are real etcd processes with independent WAL directories on one host. Process pauses make voters unresponsive; this is not an asymmetric packet-partition experiment, a disk-loss test, or evidence for multi-machine performance.

Self-check

Read the originals

• Ongaro & Ousterhout — Raft extended paper, especially §§2, 5 and 8.
• etcd FAQ, commitment and operation.
• etcd failure modes, quorum loss and leader failover.