CS Fundamentals Trainer · Guides
Consensus: Raft, leader election and log replication
How a group of machines agrees on a log despite crashes: quorums, Raft's terms, randomised elections, replication and the commit rule, partitions and what survives them, with a simulation, fault injection and two step-by-step animations.
29 min read
A single server is simple: it decides, and everyone else believes it. The moment you copy data to several servers to survive failures (see replication), you need an answer to a hard question: when the servers disagree or some of them cannot be reached, which answer is the truth? Consensus is the family of protocols that gets a group of machines to agree on a value, or a sequence of values, even when some of them crash and messages are delayed or lost. It is what sits underneath etcd (and so Kubernetes), ZooKeeper, Consul, and the metadata of many databases and queues.
This guide explains consensus through Raft, the protocol designed to be understandable, and shows it working. I wrote a small Raft simulation (election, log replication, crashes and partitions) and ran it thousands of times; the code is in the appendix.
Read this first: this is a simulation, not a production implementation. Everything measured below (election times, the 0-violation safety run) comes from a roughly 150-line Python model in simulated time. It deliberately leaves out what makes a real Raft deployment safe and usable: durable state (
currentTerm,votedForand the log must be flushed to disk before a node replies), snapshots and log compaction, membership changes, pre-vote and leadership transfer, safe linearizable reads, and real networks and disks (partial failures, slow disks, clock jumps). Section 5 lists these, and section 5.1 works through the membership change, because it is the one most often done wrongly. The numbers show how the protocol behaves; they say nothing about the speed or safety of any real system.
1. The problem: a replicated state machine
The standard way to build a fault-tolerant service is a replicated state machine: every node starts in the same state and applies the same commands in the same order. If the commands are deterministic, the states stay identical. Consensus is how the nodes agree on that log of commands.
Diagram: A replicated log feeds identical state machines
What a consensus protocol promises (the textbook names):
- Agreement (safety): no two nodes decide different values for the same position in the log.
- Validity: a decided value was proposed by some client; it is not invented.
- Termination (liveness): if enough nodes work and the network behaves well enough for long enough, the system keeps deciding.
There is a well-known limit: the FLP result (Fischer, Lynch and Paterson, 1985) proves that in a fully asynchronous network, where a slow node cannot be told from a dead one, no deterministic protocol can guarantee that it always terminates if even one node may crash. Real protocols accept this: they always stay safe and make progress only when the network is reasonably timely (randomised timeouts in Raft are exactly how it gets around FLP in practice). That is the same trade as in the CAP guide: when it cannot reach a majority, a consensus system chooses consistency and stops answering instead of risking two answers.
2. Quorums: why a majority
The key idea is the quorum. A decision needs the agreement of a majority of the N nodes, that is, more than N/2. Any two majorities share at least one node, so a later majority always contains someone who knew about the earlier decision. That overlap is what stops two halves of a split cluster from deciding different things.
| Nodes N | Majority | Failures tolerated |
|---|---|---|
| 3 | 2 | 1 |
| 4 | 3 | 1 |
| 5 | 3 | 2 |
| 7 | 4 | 3 |
Two consequences you should remember. An even number of nodes does not help: four nodes still tolerate only one failure, like three, and need a larger majority. And more nodes make writes slower, not faster: every write waits for a majority, so adding nodes adds replication work and tail latency. Production clusters usually have 3 or 5 members; more is for tolerating more simultaneous failures, not for scale.
3. Raft in one page
Raft splits the problem into leader election, log replication and safety. At any time each node is a follower, a candidate or the leader, and time is divided into numbered terms. There is at most one leader per term.
Diagram: The three roles of a Raft node
- All writes go through the leader, which appends them to its log and replicates them.
- The leader sends heartbeats (empty AppendEntries messages) to prove it is alive.
- A follower that hears nothing for a random election timeout assumes the leader is gone and starts an election.
- Every message carries the sender's term. A node that sees a higher term immediately steps down to follower, and a message from a lower term is rejected. Terms are Raft's logical clock; they keep an old, confused leader from doing damage.
Leader election
When a follower's timer expires it increments its term, becomes a candidate, votes for itself and asks the others for votes. A node grants one vote per term, first come first served, and only if the candidate's log is at least as up to date as its own (compare the term of the last entry, then the length). A candidate with votes from a majority becomes the leader and starts sending heartbeats.
Step through an election after the leader crashes. Switch on the option to see a split vote:
Interactive animation: raft election
If two candidates split the votes, nobody wins, the timers run out again, and a new term starts. The reason the timers are random is to make that unlikely. I tested this in the simulation: five nodes, message delays of 5 to 15 ms, a heartbeat every 50 ms, and 500 runs for each setting of the election timeout, measuring the time from the start until a first leader exists:
| Election timeout range | Median to first leader | 99th percentile | Failed elections per run |
|---|---|---|---|
| 150 to 300 ms (a spread of 150 ms) | 188 ms | 356 ms | 0.37 |
| 150 to 160 ms (almost the same) | 1,126 ms | 5,926 ms | 16.1 |
| 1,000 to 2,000 ms (long) | 1,145 ms | 1,582 ms | 0.05 |
A wide enough random range makes elections quick and rare to repeat. A range that is too narrow makes nodes time out together and split the vote over and over (16 failed elections per run on average, and almost 6 seconds at the 99th percentile). A range that is too long almost never splits, but the cluster is leaderless for a second or more every time it needs a new leader. The rule of thumb from the Raft paper: the timeout should be much larger than the broadcast time (so heartbeats arrive in time) and much smaller than the time between failures. Real implementations tune it to the network: for example 1 second inside a data centre, longer across regions.
When I crashed the leader of a five-node cluster 300 times, a new leader was known after a median of 195 ms and 540 ms at the 99th percentile, and none of the 300 committed writes was lost. During that time the cluster cannot accept writes: the failover pause is part of the design, and your clients need retries with backoff (see resilience patterns).
Log replication
The leader appends a client command to its log as a new entry (tagged with the current term), then sends it to the followers in AppendEntries messages. Each message names the entry that precedes the new ones (index and term); a follower accepts only if its own log has that entry (the log matching check) and otherwise refuses, and the leader backs up and sends earlier entries until the logs agree. An entry is committed once the leader has stored it on a majority. Only then does the leader apply it to its state machine and answer the client; followers learn the commit index from later messages and apply the entry too.
Interactive animation: raft replication
With all five nodes reachable, the entry is committed once the leader and two followers hold it. Switch on the option: with three nodes cut off, the leader reaches only one follower, 2 of 5 is not a majority, and the entry is never committed. The minority side must stop. If it carried on, two sides of a partition could each accept writes and the data would diverge.
Diagram: Replicating one write through a leader and two followers
Note the subtle rule in the commit step: a leader counts replicas to commit only entries from its own term. Entries from earlier terms become committed indirectly, when a later entry of the current term is committed after them. The Raft paper explains with a figure why committing an old-term entry by counting replicas alone could let it be overwritten later; implementations such as etcd have the leader append a no-op entry as soon as it is elected for this reason.
4. Why it is safe
Raft's safety rests on two rules that fit together.
- A candidate needs a majority of votes, and a voter refuses a candidate whose log is less up to date than its own.
- An entry is committed only after a majority stored it.
Because any two majorities overlap, every possible winner of a later election was in the majority that stored each committed entry, so it must hold that entry, so the "up to date" check lets it win only if it has them all. Committed entries are never lost, and the winner's log is the one every follower is brought into line with.
The partition experiment
I cut a five-node cluster into a minority of two (the old leader and one follower) and a majority of three, and sent a write to each side:
minority leader 0: log [(term 1, a=1), (term 1, lost=1)] commit index 1
majority leader 2: log [(term 1, a=1), (term 2, b=2)] commit index 2
after healing, node 0: log [(term 1, a=1), (term 2, b=2)] role: follower
The old leader kept believing it was the leader and accepted lost=1, but could not reach a majority, so it never committed it and the client never got a success. The majority elected a new leader in term 2 and committed b=2. When the partition healed, the old leader saw the higher term, stepped down, and its uncommitted entry was overwritten with the majority's log. This is the correct outcome: the write that was not acknowledged disappears, and everything that was acknowledged is still there. The lesson for clients: a timeout or a lost connection on a write means "unknown", not "failed"; use idempotent commands or an idempotency key (see the limits of idempotency keys).
Fault injection
A single scenario proves little, so I let the simulation run randomly: 200 runs of 60 steps, each step a random mix of crashing a node (never below a majority alive), restarting one, cutting random links, healing, or proposing a command. After every step I checked two properties: at most one leader per term, and the committed prefixes of all nodes' logs agree. Result: 0 violations, with 4,917 entries committed in total. This is a test of a simplified implementation, not a proof, and the real protocol has been formally specified and checked (the Raft authors published a TLA+ specification, and Paxos and Raft have been verified in tools such as Verdi and Ivy); but it shows the kind of testing that distributed protocols need. Tools such as Jepsen exist to do this against real systems.
5. What my simulation leaves out
It is about 150 lines and keeps the heart of Raft. A real implementation also needs:
- Persistence:
currentTerm,votedForand the log must reach disk (fsync) before a node replies. If a node forgot its vote after a restart it could vote twice in one term and break the one-leader rule. This is also why disk latency is the floor on consensus write latency. - Snapshots and log compaction, so the log does not grow without bound and a node that was away for a long time can catch up by receiving a snapshot.
- Membership changes, adding or removing nodes safely (single-server changes or the joint consensus method).
- Pre-vote and leadership transfer: without pre-vote, a node that was partitioned away keeps raising its term, and when it rejoins its high term forces a healthy leader to step down. With pre-vote it first asks whether it could win.
- Linearizable reads: a leader that has just been deposed may not know it. To answer a read safely it confirms leadership with a heartbeat round (ReadIndex) or relies on a lease based on bounded clock drift. Reading from a follower is faster but may be stale.
- Batching, pipelining and flow control for throughput.
This is why you should not write your own consensus. Use a tested implementation (etcd's Raft library, HashiCorp Raft, ZooKeeper's ZAB, a managed service) and spend your effort on using it correctly.
5.1 A worked example: changing the membership with joint consensus
Adding or removing servers looks harmless and is one of the most dangerous operations in a cluster, because different nodes learn about a new configuration at different moments. If some nodes count votes with the old member list and others with the new one, two different majorities can exist at the same time, and with them two leaders in one term.
The failure. A cluster of three (S1, S2, S3) grows to five (S1 to S5) in one step. The configuration entry reaches S4 and S5 and S3 first; S1 and S2 are slow and still use the old list. Now S1 asks S2 for a vote and wins with 2 of 3, the majority of the old configuration. At the same moment S3 asks S4 and S5 and wins with 3 of 5, the majority of the new one. Two leaders, same term, and both can commit different entries. I checked this by brute force over every subset of nodes (script in the appendix): ['S1', 'S2'] and ['S3', 'S4', 'S5'] are majorities of the old and the new configuration with no node in common. Replacing {S1, S2, S3} by {S3, S4, S5} has the same problem (['S1', 'S2'] and ['S3', 'S4']).
Joint consensus (the method in the Raft paper) avoids it with an intermediate configuration, C(old,new), in which a decision needs a majority of the old members and a majority of the new members. For the replacement of {S1, S2, S3} by {S3, S4, S5}:
| Step | What the leader does | Who must agree to commit it |
|---|---|---|
| 1 | Appends C(old,new) to its log and replicates it. Each node uses a configuration as soon as it appears in its log, committed or not. | 2 of {S1, S2, S3} and 2 of {S3, S4, S5} |
| 2 | While C(old,new) is in effect, elections and entries also need both majorities. Neither old nor new alone can decide anything. | both majorities |
| 3 | Once C(old,new) is committed, appends C(new). | 2 of {S3, S4, S5} |
| 4 | When C(new) is committed, the old members that are not in the new set (S1, S2) are no longer needed. A leader that is not in C(new) steps down after committing it. |
The brute force confirms the property that matters: in the joint phase every possible quorum overlaps both the old-only and the new-only quorums, and also every other joint quorum (all 64 joint quorums, 4 old-only and 16 new-only for the three-to-five case, with no disjoint pair). At no moment can two leaders be elected on different configurations.
If the leader crashes in the middle: if C(old,new) had not reached a majority, the new leader never sees it and the change is simply lost (retry it). If it had been committed, any node that could win an election must hold it (the election rule requires an up-to-date log), so the new leader finishes the change by appending C(new). Both outcomes are safe because every decision always involves a majority of the old members until C(new) is committed.
Single-server changes are the simpler alternative that most implementations use today: add or remove one server at a time. A majority of N nodes and a majority of N+1 (or N-1) always share a node, so no joint phase is needed. The brute force checked every size from 1 to 8 in both directions and found no disjoint pair. The rule is therefore: never change more than one voting member per step, and wait for each change to be committed before starting the next. Going from three to five nodes is two changes, not one.
What the example does not cover: new servers should join first as non-voting learners and catch up (otherwise a slow new node can stall commits while it is counted), and a removed server that is not told can disturb the cluster with elections unless pre-vote or a check-quorum rule is used. These are the details that real libraries implement and that my simulation does not.
6. Where consensus fits, and where it does not
Consensus is slow and sensitive compared with ordinary replication: every decision costs a round trip to a majority and a disk flush, and the leader is a bottleneck. So it is used for small, critical data, the control plane, not for the bulk data plane:
- Leader election and distributed locks for other systems (see the fencing token below).
- Configuration and service discovery (etcd, Consul, ZooKeeper).
- Metadata for databases and queues: which node owns which shard (see sharding), the topic and partition assignment of a broker.
- Strongly consistent databases such as CockroachDB, TiDB, Spanner and YugabyteDB run a consensus group (Raft or Paxos) per range or shard and so scale by running many small groups.
For bulk replication a database often uses simpler, cheaper leader-based replication that is not consensus (the replication guide shows what an asynchronous follower can lose).
Fencing tokens: a lock is not enough
A common bug: client A takes a lock from a consensus-backed service, pauses (a long garbage-collection pause, a stall of the VM), the lock expires, client B takes it, then A wakes up and writes, believing it still holds the lock. The fix is a fencing token: the lock service hands out a number that increases with every grant, the client sends it with every write, and the storage refuses any token lower than one it has already seen. Consensus gives you a correct lock service; it cannot stop a paused client from acting on a stale belief, so the check must happen at the resource.
Raft, Paxos and the others
Paxos (Lamport) solves the same problem and came first; its basic form agrees on a single value, and Multi-Paxos repeats it for a log. It is harder to explain and to implement completely, which was the motivation for Raft. ZAB (ZooKeeper) and Viewstamped Replication are close relatives. All of these assume nodes crash and stop; they do not defend against nodes that lie or are compromised. Surviving that needs Byzantine fault tolerant protocols (PBFT and the protocols behind blockchains), which need 3f+1 nodes to tolerate f faulty ones and are much more expensive.
7. Common mistakes
- Running two or four nodes: two tolerate nothing, four tolerate the same as three.
- Spreading a small cluster over regions without thinking about latency: every write waits for the round trip to the nearest majority, and losing a region can lose the majority.
- Treating a timed-out write as failed, and retrying a non-idempotent command.
- Reading from a follower and expecting the latest write.
- Locks without fencing tokens, or leases that assume clocks never drift.
- Using the consensus store as a general database or queue: a few megabytes of metadata is the right scale.
- Very short election timeouts on a loaded or virtualised host: spurious elections and unstable leadership.
- Slow disks under the log: the
fsyncis on the critical path of every write. - Rolling restarts of a majority at the same time.
8. Things to mention in an interview
- The replicated state machine idea: agree on the log, apply deterministically.
- Majority quorums and why any two overlap; why 3 or 5 nodes, and why even sizes do not help.
- Raft's roles and terms; randomised election timeouts and the split vote; the "log at least as up to date" voting rule.
- The commit rule, the minority partition stopping while the majority continues, and the overwrite of uncommitted entries.
- FLP in one sentence, and that Raft is always safe but only live when the network is timely.
- What consensus is used for (metadata, leader election, locks) and what it is not (bulk data).
- Fencing tokens; linearizable reads; the failover pause as an availability cost.
Quick recap
- Consensus makes a group of nodes agree on a log despite crashes and message loss; a replicated state machine applies it identically everywhere.
- Decisions need a majority, because any two majorities overlap: 3 nodes tolerate 1 failure, 5 tolerate 2, and an even number adds nothing.
- Raft: one leader per term, randomised election timeouts, one vote per term and only for an up-to-date log; commit when a majority stored the entry.
- In the simulation, elections took a median of 188 ms with a good timeout range and failed repeatedly with a narrow one; leader crashes were healed in about 195 ms and lost no committed write; 200 random fault runs had no safety violation.
- The minority side of a partition stops, and its uncommitted entries are overwritten after healing, so an unacknowledged write means unknown.
- Use a proven implementation for small critical data, add fencing tokens to locks, and expect a short pause at every failover.
Appendix: the experiment code
One Python 3 file with no dependencies. It simulates five nodes in simulated time (milliseconds) with random message delays, so each run is repeatable from its seed. It implements leader election with randomised timeouts, the up-to-date log rule, AppendEntries with the log matching check, the commit rule (only entries of the leader's own term are committed by counting replicas) and the overwriting of conflicting log suffixes. It does not implement persistence, snapshots, membership changes, pre-vote or reads, and its nodes never lose their state when they crash (a restarted node keeps its term, vote and log, which is what a real node must guarantee by writing to disk before replying). The numbers in the guide come from the __main__ section; they will be identical on your machine because everything is seeded.
A Raft simulation: elections, replication, partitions and fault injection
"""A small Raft simulation: leader election, log replication and failures, in simulated time (milliseconds)."""
import heapq, random, itertools
class Sim:
def __init__(self, n=5, seed=0, timeout=(150, 300), delay=(5, 15), heartbeat=50):
self.n, self.rnd, self.timeout, self.delay, self.hb = n, random.Random(seed), timeout, delay, heartbeat
self.t = 0; self.q = []; self.seq = itertools.count()
self.term = [0]*n; self.voted = [None]*n; self.role = ['follower']*n; self.log = [[] for _ in range(n)] # entries: (term, command)
self.commit = [0]*n; self.alive = [True]*n; self.deadline = [0]*n; self.votes = [set() for _ in range(n)]
self.next = [[1]*n for _ in range(n)]; self.match = [[0]*n for _ in range(n)]
self.cut = set() # pairs (a,b) that cannot talk
self.leaders = {} # term -> set of leaders (safety check: at most one per term)
self.elections = 0; self.first_leader_at = None; self.applied = [[] for _ in range(n)]
for i in range(n): self.reset_timer(i)
for i in range(n): self.at(self.deadline[i], ('tick', i))
def at(self, when, ev): heapq.heappush(self.q, (when, next(self.seq), ev))
def reset_timer(self, i): self.deadline[i] = self.t + self.rnd.uniform(*self.timeout)
def send(self, a, b, msg):
if (a, b) in self.cut or (b, a) in self.cut: return
self.at(self.t + self.rnd.uniform(*self.delay), ('msg', b, a, msg))
def last(self, i): return (self.log[i][-1][0] if self.log[i] else 0, len(self.log[i]))
def become_follower(self, i, term):
if term > self.term[i]: self.term[i] = term; self.voted[i] = None
self.role[i] = 'follower'
def start_election(self, i):
self.term[i] += 1; self.role[i] = 'candidate'; self.voted[i] = i; self.votes[i] = {i}; self.elections += 1
self.reset_timer(i)
for j in range(self.n):
if j != i: self.send(i, j, ('vote?', self.term[i], self.last(i)))
def become_leader(self, i):
self.role[i] = 'leader'; self.leaders.setdefault(self.term[i], set()).add(i)
if self.first_leader_at is None: self.first_leader_at = self.t
self.next[i] = [len(self.log[i]) + 1]*self.n; self.match[i] = [0]*self.n; self.match[i][i] = len(self.log[i])
self.broadcast(i)
def broadcast(self, i):
if not self.alive[i] or self.role[i] != 'leader': return
for j in range(self.n):
if j == i: continue
prev = self.next[i][j] - 1; pt = self.log[i][prev-1][0] if prev else 0
self.send(i, j, ('append', self.term[i], prev, pt, self.log[i][prev:], self.commit[i]))
self.at(self.t + self.hb, ('beat', i, self.term[i]))
def propose(self, cmd):
for i in range(self.n):
if self.alive[i] and self.role[i] == 'leader':
self.log[i].append((self.term[i], cmd)); self.match[i][i] = len(self.log[i]); return i
def advance_commit(self, i):
for idx in range(len(self.log[i]), self.commit[i], -1):
if self.log[i][idx-1][0] == self.term[i] and sum(m >= idx for m in self.match[i]) > self.n // 2:
self.commit[i] = idx; break
def handle(self, i, src, msg):
kind = msg[0]
if kind in ('vote?', 'append') and msg[1] > self.term[i]: self.become_follower(i, msg[1])
if kind == 'vote?':
_, term, (lt, ll) = msg
ok = term == self.term[i] and self.voted[i] in (None, src) and (lt, ll) >= self.last(i) # candidate's log at least as up to date
if ok: self.voted[i] = src; self.reset_timer(i)
self.send(i, src, ('vote', self.term[i], ok))
elif kind == 'vote':
_, term, ok = msg
if term > self.term[i]: self.become_follower(i, term)
elif self.role[i] == 'candidate' and term == self.term[i] and ok:
self.votes[i].add(src)
if len(self.votes[i]) > self.n // 2: self.become_leader(i)
elif kind == 'append':
_, term, prev, pt, entries, lc = msg
if term < self.term[i]: self.send(i, src, ('ack', self.term[i], False, 0)); return
self.role[i] = 'follower' if self.role[i] != 'leader' else self.role[i]; self.reset_timer(i)
if prev > len(self.log[i]) or (prev and self.log[i][prev-1][0] != pt): self.send(i, src, ('ack', self.term[i], False, prev)); return
self.log[i] = self.log[i][:prev] + list(entries) # overwrite any conflicting suffix
self.commit[i] = max(self.commit[i], min(lc, len(self.log[i])))
self.send(i, src, ('ack', self.term[i], True, prev + len(entries)))
elif kind == 'ack':
_, term, ok, idx = msg
if term > self.term[i]: self.become_follower(i, term); return
if self.role[i] != 'leader' or term != self.term[i]: return
if ok: self.match[i][src] = max(self.match[i][src], idx); self.next[i][src] = self.match[i][src] + 1; self.advance_commit(i)
else: self.next[i][src] = max(1, self.next[i][src] - 1)
def run(self, until):
while self.q and self.q[0][0] <= until:
when, _, ev = heapq.heappop(self.q); self.t = when
if ev[0] == 'tick':
i = ev[1]
if self.alive[i]:
if self.role[i] != 'leader' and self.t >= self.deadline[i]: self.start_election(i)
self.at(self.t + 10, ('tick', i))
elif ev[0] == 'beat':
_, i, term = ev
if self.alive[i] and self.role[i] == 'leader' and self.term[i] == term: self.broadcast(i)
elif ev[0] == 'msg':
_, dst, src, msg = ev
if self.alive[dst]: self.handle(dst, src, msg)
self.t = until
def leader(self):
ls = [i for i in range(self.n) if self.alive[i] and self.role[i] == 'leader']
return max(ls, key=lambda i: self.term[i]) if ls else None
def crash(self, i): self.alive[i] = False; self.role[i] = 'follower'
def restart(self, i): self.alive[i] = True; self.role[i] = 'follower'; self.reset_timer(i)
def safety(s):
one_leader_per_term = all(len(v) <= 1 for v in s.leaders.values())
# committed prefixes must agree on every node
ok = True
for a in range(s.n):
for b in range(s.n):
k = min(s.commit[a], s.commit[b])
if s.log[a][:k] != s.log[b][:k]: ok = False
return one_leader_per_term, ok
if __name__ == "__main__":
# 1. time to elect a leader from a cold start, by election timeout range
for rng in ((150, 300), (150, 160), (1000, 2000)):
ts = []; splits = 0
for seed in range(500):
s = Sim(seed=seed, timeout=rng); s.run(6000); ts.append(s.first_leader_at); splits += s.elections > 1 and s.first_leader_at is not None and (s.elections - 1)
ts = sorted(t for t in ts if t is not None)
print(f"timeout {rng}: median first leader {ts[len(ts)//2]:.0f} ms, 99th percentile {ts[int(len(ts)*.99)]:.0f} ms, worst {ts[-1]:.0f} ms, failed elections before the first leader, per run {splits/500:.2f}")
# 2. crash the leader: how long until a new leader is known, and does a committed write survive?
outage = []; lost = 0
for seed in range(300):
s = Sim(seed=seed); s.run(1000); l = s.leader(); s.propose("x=1"); s.run(1300)
assert s.commit[l] == 1 # the write is committed on the leader
s.crash(l); t0 = s.t
while s.leader() is None and s.t < t0 + 5000: s.run(s.t + 5)
outage.append(s.t - t0); s.run(s.t + 1000)
nl = s.leader(); lost += nl is None or s.log[nl][:1] != [(s.log[nl][0][0], "x=1")]
assert all(safety(s))
outage.sort(); print(f"leader crash: new leader after median {outage[150]:.0f} ms, 99th percentile {outage[297]:.0f} ms; committed writes lost: {lost} of 300")
# 3. a partition: the minority side cannot commit, the majority can, and after healing the minority's entries are overwritten
s = Sim(seed=3); s.run(1000); old = s.leader(); s.propose("a=1"); s.run(1200)
minority = {old, (old + 1) % 5}; majority = set(range(5)) - minority
for a in minority:
for b in majority: s.cut.add((a, b))
s.propose("lost=1"); s.run(1800) # the old leader accepts a write it can only reach one follower with
print("minority leader", old, "log", s.log[old], "commit", s.commit[old])
for _ in range(200):
l = max((i for i in majority if s.role[i] == 'leader'), key=lambda i: s.term[i], default=None)
if l is not None: break
s.run(s.t + 20)
l = max((i for i in majority if s.role[i] == 'leader'), key=lambda i: s.term[i]); s.log[l].append((s.term[l], "b=2")); s.match[l][l] = len(s.log[l]); s.run(s.t + 600)
print("majority leader", l, "log", s.log[l], "commit", s.commit[l])
s.cut.clear(); s.run(s.t + 1500)
print("after healing: old leader's log", s.log[old], "role", s.role[old], "term", s.term[old], safety(s))
# 4. fault injection: random crashes, partitions and writes; check the two safety properties all along
bad = 0; committed_total = 0
for seed in range(200):
s = Sim(seed=1000 + seed); rnd = random.Random(seed); k = 0
for step in range(60):
s.run(s.t + rnd.uniform(20, 200))
r = rnd.random()
if r < .15:
v = rnd.randrange(5)
if sum(s.alive) > 3 and s.alive[v]: s.crash(v)
elif r < .3:
for v in range(5):
if not s.alive[v]: s.restart(v); break
elif r < .4: s.cut = {(a, b) for a in range(5) for b in range(5) if a < b and rnd.random() < .4}
elif r < .5: s.cut = set()
else: k += 1; s.propose(f"c{k}")
if not all(safety(s)): bad += 1
committed_total += max(s.commit)
print(f"fault injection: 200 runs x 60 steps, safety violations: {bad}, entries committed in total: {committed_total}")
# 5. quorum arithmetic
for n in (3, 5, 7): print(f"{n} nodes: majority {n//2+1}, tolerates {n - (n//2+1)} failures")
Why membership changes need care: a brute-force check of quorum overlap
Runs in a fraction of a second with the standard library. It enumerates every majority for the old, new and joint configurations and looks for two that share no node.
"""Why a cluster cannot switch configuration in one step, and how joint consensus and
single-server changes avoid the problem. Brute force over all subsets of nodes."""
from itertools import combinations
def majorities(cfg):
need = len(cfg) // 2 + 1
return [set(c) for k in range(need, len(cfg) + 1) for c in combinations(sorted(cfg), k)]
def disjoint_pair(qs_a, qs_b):
for a in qs_a:
for b in qs_b:
if not (a & b):
return sorted(a), sorted(b)
return None
def report(title, qa, qb):
r = disjoint_pair(qa, qb)
print(f"{title}: {'DISJOINT quorums exist, e.g. ' + str(r[0]) + ' and ' + str(r[1]) if r else 'every pair of quorums overlaps'}")
old = {"S1", "S2", "S3"}
new = {"S1", "S2", "S3", "S4", "S5"}
# 1. direct switch: some nodes still use the old configuration, others already the new one
report("direct switch 3 -> 5 nodes (old config vs new config)", majorities(old), majorities(new))
# 2. joint consensus: during C_old,new a decision needs a majority of C_old AND a majority of C_new
joint = [a | b for a in majorities(old) for b in majorities(new)]
report("joint phase vs old config alone", joint, majorities(old))
report("joint phase vs new config alone", joint, majorities(new))
report("joint phase vs joint phase", joint, joint)
# 3. replacing 3 nodes by 3 other nodes
old2, new2 = {"S1", "S2", "S3"}, {"S3", "S4", "S5"}
report("direct switch {S1,S2,S3} -> {S3,S4,S5}", majorities(old2), majorities(new2))
joint2 = [a | b for a in majorities(old2) for b in majorities(new2)]
report("joint {S1,S2,S3}+{S3,S4,S5} vs old alone", joint2, majorities(old2))
report("joint {S1,S2,S3}+{S3,S4,S5} vs new alone", joint2, majorities(new2))
# 4. single-server changes (one node added or removed at a time)
for n in range(1, 8):
a = {f"S{i}" for i in range(n)}
bigger = a | {f"S{n}"}
r1 = disjoint_pair(majorities(a), majorities(bigger))
print(f"single-server change {n} -> {n+1} nodes: {'DISJOINT' if r1 else 'overlap'}", end=" | ")
if n > 1:
smaller = set(sorted(a)[:-1])
r2 = disjoint_pair(majorities(a), majorities(smaller))
print(f"{n} -> {n-1}: {'DISJOINT' if r2 else 'overlap'}")
else:
print()
# 5. two changes at once (3 -> 5) is exactly the unsafe case from step 1
print("sizes of quorum sets: old", len(majorities(old)), "new", len(majorities(new)), "joint", len(joint))
Sources
- Diego Ongaro and John Ousterhout, In Search of an Understandable Consensus Algorithm (USENIX ATC 2014), and Ongaro's PhD thesis Consensus: Bridging Theory and Practice (2014), which covers membership changes, snapshots, pre-vote and client interaction.
- The Raft website with the visualisation and the list of implementations.
- Leslie Lamport, Paxos Made Simple (2001), and The Part-Time Parliament (1998).
- Michael Fischer, Nancy Lynch and Michael Paterson, Impossibility of Distributed Consensus with One Faulty Process (JACM, 1985).
- Martin Kleppmann, Designing Data-Intensive Applications (O'Reilly), chapter 9, "Consistency and Consensus", and his essay How to do distributed locking for fencing tokens.
- The etcd documentation on its Raft implementation, learner nodes and the failure-tolerance table; the Jepsen analyses at jepsen.io.
- Diego Ongaro and John Ousterhout, In Search of an Understandable Consensus Algorithm, section 6 (cluster membership changes, joint consensus), and Ongaro's PhD dissertation, chapter 4 (single-server changes).
Practise this topic: System Design System Design › Distributed systems