Consensus with Raft: What a Cluster Does When Its Leader Stops

We killed, froze and cut off the leader of a real etcd cluster, 66 times. A killed one was replaced in a median 1.2 seconds, and two nodes once both called themselves leader for about 0.8 s. How Raft elects, replicates and commits, and why it stays correct.

Several machines agreeing on one thing sounds simple. Keep a copy of the data on each, and have them agree on every change. The hard part is that any of them can stop at any moment, messages can be delayed or lost, and nobody can tell a dead machine from a slow one.

Consensus algorithms solve this. This part is about Raft, the algorithm inside etcd. Jepsen describes etcd as the store that “Many distributed systems, such as Kubernetes and OpenStack, use” for cluster metadata and choosing leaders. We ran a real etcd cluster, took its leader away in three different ways, and measured what happened. Then we read the Raft paper to see why it happened.

Try this first

A three-node etcd cluster is taking writes. Its leader’s process is killed. The other two nodes are fine, and your client can reach them.

How long until a write succeeds again?

1. Immediately. The other two already have the data.
2. About 150 to 300 ms. That’s Raft’s election timeout.
3. About a second, give or take.
4. Never, until the leader comes back.

Write down your answer. The measured answer is below, and the second option is a very common wrong answer.

What consensus is for

A consensus algorithm lets a group of servers agree on a sequence of values, even when some of them fail. Almost every real use is the same one: a replicated log. Each server keeps a log of commands. If every server applies the same commands in the same order, they all end up in the same state. To a client, the group behaves like one machine that doesn’t go down when one server does.

Lamport’s original Paxos paper says so in its abstract: its protocol “provides a new way of implementing the state-machine approach to the design of distributed systems.” etcd is exactly this. Every write is a command in a Raft log, replicated to a majority of the nodes before it’s acknowledged.

What that buys you, in the Raft paper’s words about what “Consensus algorithms for practical systems typically have”:

They ensure safety (never returning an incorrect result) under all non-Byzantine conditions, including network delays, partitions, and packet loss, duplication, and reordering.

They are fully functional (available) as long as any majority of the servers are operational and can communicate with each other and with clients. Thus, a typical cluster of five servers can tolerate the failure of any two servers.

Notice the split. Safety holds always. Availability needs a majority. “Non-Byzantine” means servers may stop or be slow, but they don’t lie.

Why Raft exists

Paxos came first. “A fault-tolerant file system called Echo was built at SRC in the late 80s,” Lamport writes, and he set out to prove that what its builders wanted was impossible. He found Paxos instead, and submitted the paper in 1990. By his own account, the referees said “all the Paxos stuff had to be removed”, and it was published in 1998.

Paxos has a reputation for being hard. Lamport disagrees. His 2001 paper Paxos Made Simple opens: “The Paxos algorithm, when presented in plain English, is very simple.” But building a system from it is another matter. Google’s Chubby team wrote in 2007:

There are significant gaps between the description of the Paxos algorithm and the needs of a real-world system. In order to build a real-world system, an expert needs to use numerous ideas scattered in the literature and make several relatively small protocol extensions. The cumulative effort will be substantial and the final system will be based on an unproven protocol.

Diego Ongaro and John Ousterhout designed Raft in 2014 with understandability as the main goal. To that end, Raft “separates the key elements of consensus, such as leader election, log replication, and safety”. They tested the claim with a user study: 43 students learned both algorithms, and “33 of these students were able to answer questions about Raft better than questions about Paxos.” The mean score was 25.7 for Raft and 20.8 for Paxos, out of 60. That study measured understanding, not simplicity. Raft isn’t more capable than Paxos. The Raft site says it’s “equivalent to Paxos in fault-tolerance and performance.”

Terms, roles and elections

At any moment, each server is in one of three states: leader, follower or candidate. The leader handles every client request. “Followers are passive”: they send nothing on their own, and only answer the leader and candidates.

Time is divided into terms, numbered with consecutive integers. Each term begins with an election. If a candidate wins, it leads for the rest of the term. If the vote splits, the term ends with no leader and a new one starts. The paper describes terms as a logical clock, the same idea as the Lamport clocks in Part 25:

Terms act as a logical clock [14] in Raft, and they allow servers to detect obsolete information such as stale leaders.

A server that sees a higher term than its own adopts it. A leader or candidate that sees a higher term “immediately reverts to follower state.” A request carrying an older term is rejected.

An election works like this:

1. The leader sends heartbeats to every follower. In etcd, that’s every 100 ms by default.
2. A follower that hears nothing for its election timeout assumes the leader is gone. It increments its term, becomes a candidate, votes for itself and asks the others for their votes.
3. Each server votes for at most one candidate per term, first come, first served.
4. A candidate that gets votes from a majority of the whole cluster becomes leader and starts sending heartbeats.

If two followers time out together, they can split the vote, and in the paper’s words “without extra measures split votes could repeat indefinitely.” Raft’s fix is randomness: each server picks its election timeout at random from a range, so one usually times out first and wins before the others start.

The paper gives “(e.g., 150–300ms)” as an example range. etcd’s defaults are different: a 1,000 ms election timeout, and its Raft library picks each server’s actual timeout from “[electiontimeout, 2 * electiontimeout – 1]” in 100 ms ticks. So with the defaults, a follower waits somewhere between 1,000 and 1,900 ms.

Measured: when the leader stops

We ran a three-node etcd 3.6.8 cluster in Docker, with its default timings, and took the leader away three ways:

• Killed: its process got SIGKILL, 20 times.
• Frozen: its process was paused with docker pause, 20 times. To the other nodes this looks like a leader stuck in a long garbage-collection pause.
• Cut off: its links to the other two nodes were dropped for 10 seconds, while clients could still reach it, 26 times.

The lab sent a write to every node every 20 ms, and asked every node for its status every 20 ms.

• A killed leader was replaced in a median of 1.20 s. The range was 1.07 to 1.94 s, measured from the leader’s last answer to the lab. That’s about one randomized election timeout, which etcd draws from 1.0 to 1.9 s, plus the vote.
• Writes came back with it, in a median of 1.22 s. Some writes sent during the election were held and went through once the new leader was up. The rest timed out.
• A frozen leader behaved the same. A new leader came in a median of 1.29 s (1.02 to 1.83). Raft doesn’t try to tell frozen from dead: silence is silence.
• Every new leader had the old term plus one. All 40 elections, killed or frozen, were won in their first term.
• The frozen leaders came back quietly. The lab read each one’s status for 1.5 seconds from the moment docker unpause returned. None of the 20 reported itself as leader. Raft has a leader step down the moment it sees a higher term.

So the answer to the question at the top is about a second. The 150–300 ms figure is the paper’s example election timeout, for its own setup. etcd’s default is 1,000 ms, and failover takes about one election timeout, whatever the timeout is. The Raft paper puts it plainly: “When the leader crashes, the system will be unavailable for roughly the election timeout”.

Log replication and commitment

Once a leader exists, every write goes through it. etcd’s documentation says a follower that receives a write “automatically forwarded to the leader”.

1. The leader appends the command to its own log.
2. It sends the new entry to every follower in an AppendEntries message. The same message, empty, is the heartbeat.
3. Each follower appends it and replies.
4. Once a majority, counting the leader, has the entry, it’s committed. The leader applies it and answers the client. Later messages tell the followers it’s committed, and they apply it too.

Each AppendEntries carries the index and term of the entry just before the new ones. A follower that doesn’t have that entry refuses, and the leader backs up and retries until the logs match. The paper proves that if two logs have an entry with the same index and term, the logs are identical up to that point. Where a follower’s log disagrees, the leader’s wins: “conflicting entries in follower logs will be overwritten with entries from the leader’s log.”

The subtle part: a majority isn’t always enough

“Committed once it’s on a majority” is almost right. The paper’s Figure 8 shows the exception:

However, a leader cannot immediately conclude that an entry from a previous term is committed once it is stored on a majority of servers.

The scenario goes like this. A leader writes an entry and gets it onto some servers, then crashes. A later leader copies that old entry onto a majority, then crashes too, before committing anything of its own. A third server, whose log has a newer term at the end, can still win an election and overwrite the old entry, even though a majority had it.

Raft’s rule closes the hole: “Only log entries from the leader’s current term are committed by counting replicas”. Older entries become committed indirectly, when a newer entry after them commits. That’s also why a new leader commits a blank entry at the start of its term. etcd’s Raft library enforces the same rule in code: the commit check passes the leader’s own term, r.Term.

Why a new leader has everything committed

A candidate can’t win unless its log contains every committed entry. A voter refuses its vote if its own log is more up to date than the candidate’s. “Up to date” compares the last entries: the later term wins, and with equal terms, the longer log wins. Every committed entry is on a majority, and a winner needs votes from a majority. Any two majorities share at least one server, and that server won’t vote for a candidate missing a committed entry. So entries only ever flow from leaders to followers.

Safety never depends on timing

Raft’s safety holds under any delays at all. Its liveness, meaning its ability to make progress, needs timing to behave. The paper says so directly:

One of our requirements for Raft is that safety must not depend on timing: the system must not produce incorrect results just because some event happens more quickly or slowly than expected. However, availability (the ability of the system to respond to clients in a timely manner) must inevitably depend on timing.

That split is forced. In 1985 Fischer, Lynch and Paterson proved that in a fully asynchronous system, with no bound on message delays and no clocks, every deterministic consensus protocol “has the possibility of nontermination, even with only one faulty process.” Their model rules out timeouts, and makes it impossible to tell whether a process “has died (stopped entirely) or is just running very slowly.”

So no deterministic algorithm escapes this, and Raft doesn’t try to. It keeps safety unconditionally and gives up guaranteed progress. Randomized timeouts make progress very likely, not certain. Ongaro’s thesis says that when the timing assumptions fail, the cluster may be unable to elect a leader, “(though safety will always be maintained)”. Lamport said the same of Paxos: electing a leader “must use either randomness or real time”, but “safety is ensured regardless of the success or failure of the election.”

Tuning the election timeout

The election timeout is a guess about how long silence means death. Guess low and the cluster fails over fast. Guess too low and it fails over when nothing has failed.

The paper states the requirement as broadcastTime ≪ electionTimeout ≪ MTBF: the timeout should be much longer than a round of messages, and much shorter than the time between failures. etcd’s tuning guide says “Election timeouts must be at least 10 times the round-trip time so it can account for variance in the network.”

We ran the same cluster with a 250 ms election timeout, a quarter of etcd’s default, and a 50 ms heartbeat, half its default. We killed the leader 20 times, then froze it for short periods, as a long garbage-collection pause would, and let it go.

• The short timeout failed over about four times faster. The median was 0.31 s (0.25 to 0.42), against 1.20 s with the defaults.
• We saw one election split. In an earlier run of the same 20 crashes, one first election most likely split, and the new leader came at the old term plus two, about 0.7 s after the kill command. With a 250 ms timeout counted in 50 ms ticks, each node draws one of just five values, 250 to 450 ms.
• It lost its leader to every freeze of about half a second or more. At about 500, 800 and 1,500 ms, a new leader was elected in 10 of 10 trials each. At about 200 ms, 1 of 10.
• The default timeout rode out much longer stalls. Freezes of about 200, 500 and 800 ms never cost it its leader. At about 1,500 ms, 9 of 10 did.

Before each freeze, the lab moved leadership to another node. etcd draws a node’s random timeout only when the node changes state, so without that step, trials in the same term reuse the same draws. Our first version of this experiment made exactly that mistake, and a review caught it.

A leader change is cheap but not free. Every unplanned change is a gap of about one election timeout with no writes, plus whatever the clients do about the requests that timed out.

Slow disks cause leader changes too. etcd’s tuning guide says a slow disk means “etcd may miss heartbeats, causing request timeouts and temporary leader loss”, and its FAQ is blunt: “disk latency is part of leader liveness.”

Delay, jitter and packet loss alone didn’t cause any leader changes in our lab. We added 60 ms of delay to every link between nodes, varying with a standard deviation of 40 ms, for 120 seconds. Then we tried 20 ms, standard deviation 10 ms, with 3% packet loss. Neither timeout setting held a single election. A frozen leader sends no heartbeats at all, which is why freezes hurt here and slow links didn’t.

When the leader is cut off

A crashed leader is simple. A leader that’s still running, still reachable by clients, but cut off from the other nodes, is the case that has caused real bugs.

In our 26 trials, with times measured from when the command installing the cut had returned:

• The other two elected a new leader in a median of 1.11 s (0.84 to 1.64), at the next term.
• The old leader stepped down on its own, in a median of 1.23 s (1.01 to 1.89). etcd turns on what its Raft library calls CheckQuorum: “Leader steps down when quorum is not active for an electionTimeout.” The thesis gives the reason: without it, a cut-off leader “could delay a request from that client forever”.
• In 16 of the 26 trials, the new leader was elected before the old one stepped down. For a while, two nodes both reported themselves as leader, at different terms. The longest overlap we saw was about 0.8 s.
• Only one of them could commit. In the 13 trials where the lab tracked it, the old leader’s commit index didn’t move at all during the cut.
• The old leader’s term never changed during the cut, and healing it didn’t cause an election. In all 26 trials, after the cut ended, every node agreed on the new leader and its term.

That last point is what Pre-Vote is for. It’s on by default since etcd 3.5, and we didn’t run without it. Without it, a cut-off node keeps timing out and incrementing its term. When it reconnects, its higher term forces the working leader to step down. With Pre-Vote, a node first asks whether others would vote for it, and only increments its term if a majority says yes. A node that can’t reach anyone never gets a yes. The thesis recommends it “in deployments that would benefit from additional robustness.”

A timeout isn’t a no

Every write we checked that didn’t succeed had timed out after 3 seconds. Afterwards, once every node was back and had settled, we looked for each one.

• With a killed leader, none were applied. 0 of the 2,428 writes that timed out on the surviving nodes were in the database.
• With a frozen leader, almost all were. 2,538 of the 2,593 writes that timed out on the surviving nodes were in the database afterwards. Most likely, the followers had passed them to the leader before they knew it was frozen, and they waited on the way, in network buffers or etcd’s send queues. They went through after it was released, seconds after their clients had given up. We didn’t trace where they waited. But in every trial, fewer writes timed out than were sent before a new leader existed, and with a killed leader, none of them got in.
• With a cut-off leader, a few were. 14 of the 13,002 writes sent to it were in the database afterwards, all in one of the 26 trials. In the 13 trials where the lab timed it, the cut-off node rejoined the cluster 2.76 to 3.22 s after the heal began. In the one trial where it rejoined at 2.76 s, the writes that got in were the ones whose clients were still waiting at that moment, to within the lab’s 20 ms polling. The data fit a simple story: after stepping down, the node held the writes it was sent, and passed on the ones still waiting when it found the new leader. They were committed, but no answer reached their clients within 3 seconds. In the other 12 timed trials, the node rejoined after its last waiting client had given up. With a longer client timeout, more would likely have got in.

So a timeout means “I don’t know”, as Part 23 measured with retries. How often it secretly means yes depends on the failure: never, for the writes to the surviving nodes, in our kills; almost always in our freezes. The paper’s advice for a Raft client is the same as Part 23’s: “The solution is for clients to assign unique serial numbers to every command.”

Reads: going to the leader isn’t enough

Two nodes can both believe they’re leader, as the lab showed. So a leader that answers a read from its own copy can return stale data. The Raft paper warns that such a leader “might have been superseded by a newer leader of which it is unaware.”

This isn’t hypothetical. In 2014 Jepsen found exactly this in etcd 0.4.1 and in Consul: “The old leader goes on happily replying to reads with the old value, until it realizes it hasn’t received a heartbeat from a majority of peers in some time, and steps down.” In 2020 it found stale reads in Redis-Raft for a related reason: a new leader didn’t commit its blank entry at the start of its term.

The safe fixes, from Ongaro’s thesis:

• Read index. First, a new leader waits until an entry from its own term is committed, usually its blank one: “If the leader has not yet marked an entry from its current term committed, it waits until it has done so.” Redis-Raft’s leaders didn’t commit that blank entry, and served stale reads. Then the leader notes its commit index, confirms it’s still leader with a round of heartbeats to a majority, waits until it has applied up to that index, and answers. It costs a round trip, but no log write.
• Leases. The leader assumes nobody else can be elected for about an election timeout after a majority acknowledged it, and answers without asking. That’s faster, but it “assumes a bound on clock drift”, and if the assumption breaks, “the system could return arbitrarily stale information.” The thesis doesn’t recommend it unless performance demands it.

etcd fixed its 2014 problem by making linearizable reads the default in its v3 API. Jepsen’s 2020 analysis of etcd 3.4.3 found that “key-value operations appear to be strict serializable”. A serializable read in etcd still skips all of this, and may be stale, as Part 24 measured.

How many nodes?

A cluster of n needs a majority to agree. etcd’s FAQ gives the quorum as (n/2)+1, rounded down, with this table:

Cluster size	Majority	Failures tolerated
1	1	0
2	2	0
3	2	1
4	3	1
5	3	2
6	4	2
7	4	3

We checked the first rows on real clusters. Each time we started a fresh cluster, killed the leader first and then followers, and tried to write.

• 3 nodes kept taking writes with 1 stopped, and none with 2.
• 4 nodes did exactly the same: 1 stopped was fine, and 2 stopped left them with no writes. The fourth node raised the majority from 2 to 3 without adding any tolerance.
• 5 nodes kept taking writes with 2 stopped, and stopped with 3.

So clusters are sized odd: 3, 5, and rarely 7. The FAQ says a fourth member “buys nothing in terms of fault tolerance”, and adds that an odd size guarantees one side of any two-way split still has a majority. Bigger isn’t free either: “Although larger clusters provide better fault tolerance, the write performance suffers because data must be replicated across more machines.”

Two nodes is the worst size. Its majority is two, so losing either node stops it. etcd’s documentation says: “It is unsafe to remove a member from a two member cluster.”

Changing the membership

Adding a server is itself risky. The thesis gives an example: a three-server cluster tolerates one failure, but add a fourth server with an empty log, lose one of the original three, and “the cluster will be temporarily unable to commit new entries”. That’s why etcd lets a new member join as a learner first: it receives the log but doesn’t vote, and is promoted once it has caught up.

Changing membership safely is the hardest part of Raft to get right. The paper uses a two-phase method called joint consensus. The thesis proposed a simpler one-server-at-a-time method. In 2015, Ongaro announced on the raft-dev mailing list that the simpler method had a bug: two competing changes across a leader change “have quorums that don’t overlap with each other, causing a safety violation (split brain).” The fix was small. Jepsen’s 2020 Redis-Raft analysis found a separate bug with a worse result: a leader could change the membership on its own, “remove every other node in the cluster, declare itself the sole leader”. The cause was in the Raft library: a removal entry “was left out of the set of log entry types which counted as voting configuration changes.”

Explain it like I’m ten

A class keeps one shared notebook of decisions, and every student has a copy.

• One student is the class leader. Only the leader writes new decisions. Everyone copies from the leader.
• The leader keeps saying “I’m still here”. If a student hears nothing for a while, they say, “I think the leader’s gone. Vote for me for leader number 5.” The number only ever goes up.
• You need more than half the class to vote for you. Two leaders can’t both get more than half, so there’s only ever one leader per number.
• A decision counts only when more than half the class has copied it. If the leader then disappears, at least one of those students is in any new majority, so the decision can’t be lost.
• Waiting a random while before calling an election means students don’t all shout “vote for me” at once.

The precise version

• The notebook is the replicated log, the numbers are terms, and “I’m still here” is the heartbeat, an empty AppendEntries.
• More-than-half is a quorum. Any two quorums overlap, which is what makes election safety and commitment work.
• “Copied by more than half” is committed, with Raft’s extra rule: only entries from the leader’s current term are committed by counting.
• The random wait is the randomized election timeout. etcd’s default is 1,000 to 1,900 ms.
• Where the analogy breaks: a leader who’s cut off from the class doesn’t know it. For a while it goes on believing it’s leader. That’s why reads need a quorum check, and why it’s the voting rules, not the leader’s own belief, that keep the notebook safe.

Trade-offs

• Safety needs no timing assumptions; availability does. Measured: a killed leader cost a median of 1.2 seconds without writes, most of it spent waiting out the election timeout.
• A shorter election timeout fails over faster and false-alarms more. Measured: 0.31 s against 1.20 s to fail over, but every leader freeze of half a second or more cost a leader change.
• Every write waits for a majority. Five nodes tolerate more than three, and every write waits for more replicas.
• Linearizable reads cost a round trip to a majority. Leases save it by trusting clocks.
• Odd sizes only. Measured: 4 nodes tolerated exactly the same single failure as 3.

Common mistakes

• Treating 150–300 ms as election time. It’s the paper’s example election timeout. etcd’s default is 1,000 ms, drawn from 1,000 to 1,900, and measured failover took 1.1 to 1.9 seconds.
• Reading from whichever node thinks it’s leader. Measured: two nodes both said “leader” at once in 16 of 26 cuts, once for about 0.8 s. Use a quorum-checked read.
• Running 2 or 4 nodes. Neither tolerates more failures than the odd size below it.
• Setting the election timeout close to your worst pause. A 250 ms timeout turned every half-second stall into a leader change.
• Treating a timed-out write as failed. Measured: after a frozen leader, 2,538 of 2,593 timed-out writes to the other nodes were applied anyway. Make writes idempotent.
• Adding a voting member before it has caught up. Use a learner, and remove before you add when replacing a node.
• Thinking consensus beats the impossibility result. It gives up guaranteed progress to keep safety.

Interview questions

Try to answer each one before opening the model answer.

1. How does Raft elect a leader?

Show a strong answer

• Heartbeats keep followers quiet. The leader sends empty AppendEntries regularly.
• A follower that hears nothing for its election timeout increments its term, votes for itself and asks the others for votes.
• Each server votes once per term, and only for a candidate whose log is at least as up to date as its own.
• A majority of the full cluster wins. Two candidates can’t both get a majority in the same term, so there’s at most one leader per term.
• Randomized timeouts make split votes rare: usually one follower times out first.

Likely follow-up: “How long does failover take?” About one election timeout. Measured on etcd with defaults, a median of 1.2 seconds, 1.1 to 1.9.

2. When is a log entry committed?

Show a strong answer

• When the leader that created it has it on a majority. Committing an entry commits every entry before it.
• The exception: a leader can’t count replicas for an entry from an earlier term. The paper’s Figure 8 shows such an entry, on a majority, being overwritten by a later leader.
• So a new leader commits an entry from its own term, usually a blank one, and the older entries commit with it.

Likely follow-up: “Why does the new leader have all committed entries?” The vote rule refuses a candidate whose log is less up to date, and any two majorities overlap.

3. The leader is partitioned from the rest of the cluster. What happens?

Show a strong answer

• The majority side elects a new leader after an election timeout, at a higher term.
• The old leader can’t commit anything. It can append writes, but can’t reach a majority, so its clients time out. Its uncommitted entries are overwritten when it rejoins.
• For a while, two nodes may both think they’re leader. Measured on etcd: in 16 of 26 trials, the longest for about 0.8 s.
• With CheckQuorum, the old leader steps down after an election timeout without hearing from a majority.
• With Pre-Vote, rejoining doesn’t disrupt anything. Measured: the old leader’s term never rose, and healing never forced an election.

Likely follow-up: “Can the old leader serve stale reads?” Only if reads skip the quorum check. That’s the bug Jepsen found in etcd 0.4.1 and Consul in 2014.

4. Why do Raft clusters have an odd number of nodes?

Show a strong answer

• The majority of n is (n/2)+1, rounded down. Going from 3 to 4 raises it from 2 to 3 without tolerating another failure.
• Measured: 3 and 4 nodes both survived one stopped node and stopped taking writes with two. Five survived two.
• An odd size also guarantees one side of any two-way split has a majority.
• More nodes cost write latency, because every write waits for more replicas.

Likely follow-up: “What’s wrong with two nodes?” The majority of two is two, so losing either one stops the cluster.

5. How do you serve linearizable reads from a Raft cluster?

Show a strong answer

• Not by just asking the leader. A deposed leader may not know it’s been deposed.
• Read index: once an entry from its own term has committed, the leader records its commit index, confirms leadership with a round of heartbeats to a majority, waits to apply up to that index, then answers.
• Or through the log: make the read a log entry. That’s correct but costs a write.
• Or leases: skip the round trip by assuming bounded clock drift. The thesis warns that if the assumption fails, reads can be arbitrarily stale.
• Followers can serve reads too, by asking the leader for a read index first.

Likely follow-up: “What does etcd do?” Linearizable reads by default since its v3 API; serializable reads on request, which may be stale.

6. What does FLP mean for Raft?

Show a strong answer

• FLP: in a fully asynchronous system, every deterministic consensus protocol may fail to terminate, even with one faulty process.
• Raft doesn’t beat it. It keeps safety under all timing and gives up guaranteed progress.
• Randomized election timeouts make progress very likely when timing behaves.
• When timing doesn’t behave, a Raft cluster may be unable to elect a leader for a while, but it never returns a wrong answer.

Likely follow-up: “So what does a timeout mean in Raft?” A guess that a silent leader is dead. Wrong guesses cost availability, never safety.

7. A write to your etcd cluster timed out. Did it happen?

Show a strong answer

• You don’t know. The leader may have committed it and failed to answer, or may never have committed it.
• Measured: when the leader was frozen and then released, 2,538 of 2,593 writes to the other nodes that had timed out were applied anyway. When it was killed, none of those were.
• So make it safe to retry: idempotent writes, unique request IDs, or a compare-and-set that checks the current value.

Likely follow-up: “Does Raft itself deduplicate?” Not by default. The paper says clients should assign unique serial numbers to commands so the state machine can skip repeats.

Sources

• Lab: system-design/checks/part26_raft/raft_lab.py, a three-node etcd 3.6.8 cluster in Docker, pinned by digest. It ran:
• the leader killed 20 times and frozen 20 times, with a write to every node and a status poll of every node every 20 ms;
• the leader cut off from its peers for 10 seconds, 26 times, with every write sent to it checked afterwards;
• 40 crashes with a 250 ms election timeout, and leader freezes of about 200 to 1,500 ms at both timeouts, 10 each, with leadership moved before each freeze;
• two minutes each of network delay with jitter, and of packet loss, at both timeouts;
• clusters of 3, 4 and 5 nodes with 0 to 3 nodes stopped, the leader first.
• Diego Ongaro and John Ousterhout, In Search of an Understandable Consensus Algorithm (Extended Version), 2014, and Ongaro’s PhD thesis, Consensus: Bridging Theory and Practice, Stanford, 2014.
• Ongaro, raft-dev post on the single-server membership bug, July 2015.
• Leslie Lamport, The Part-Time Parliament, 1998, Paxos Made Simple, 2001, and his notes on both.
• Chandra, Griesemer and Redstone, Paxos Made Live, 2007.
• Fischer, Lynch and Paterson, Impossibility of Distributed Consensus with One Faulty Process, JACM, 1985.
• Howard, Schwarzkopf, Madhavapeddy and Crowcroft, Raft Refloated, ACM SIGOPS OSR, 2015.
• etcd v3.6: tuning, FAQ, API guarantees, learner design, configuration flags, and the source at v3.6.8 with go.etcd.io/raft v3.6.0.
• Jepsen: etcd and Consul, 2014; etcd 3.4.3, 2020; Redis-Raft, 2020.
• The Raft website.

What to remember

• Consensus keeps a replicated log in the same order on every server. Safety never depends on timing; progress does.
• A leader needs a majority’s votes, and an entry needs a majority’s copies. Any two majorities overlap, and that’s the whole trick.
• Failover takes about one election timeout. Measured on etcd’s defaults: a median of 1.2 seconds, not 150 to 300 ms.
• A shorter timeout fails over faster and mistakes stalls for deaths. Measured: every half-second freeze cost a leader at 250 ms.
• Two nodes can both think they’re leader: measured in 16 of 26 cuts, once for about 0.8 s. Only the one with a majority can commit, so reads need a quorum check too.
• Size clusters odd. Four nodes tolerate what three do.
• A timed-out write is unknown, not failed. Measured: after a frozen leader, 2,538 of 2,593 timed-out writes to the other nodes were applied anyway.

Raft doesn’t stop things going wrong. It makes sure that when they do, the cluster stops rather than lies.