The problem: when replicas disagree, who wins?#
TL;DRthe 30-second version
- Consensus = getting N machines to agree on one ordered sequence of operations (a replicated log) despite crashes and dropped messages. Apply the same log in the same order everywhere and every node is an identical replica.
- Raft elects exactly one leader per term. All client writes go through the leader, which appends to its log and replicates via AppendEntries. One leader means one order — that is the whole trick.
- An entry is committed once a majority (quorum) has it. A cluster of 2f+1 nodes tolerates f failures; majorities of the same cluster always overlap, so no two leaders can commit conflicting entries.
- Two safety rules carry the weight: the election restriction (you only vote for a candidate whose log is at least as up-to-date as yours) and the current-term commit rule (a leader only counts entries from its own term toward commit).
- It is the consensus layer behind etcd, Consul, CockroachDB, TiKV, and Kafka's KRaft mode. The classic alternative, Multi-Paxos, is equivalent in power but harder to reason about and implement.
A single database server is a single point of failure — if it dies, every client request fails until it's replaced. The fix is to replicate the same data onto several machines. But replication immediately creates a new problem: if two clients write to two different replicas at the same time, which write wins, and in what order do all replicas end up agreeing to apply them?
To keep this concrete, picture a real system: etcd, the key-value store that holds all of Kubernetes's cluster state. Its data is just a map — set x = 1, set y = 2, read x. Here's the key trick: instead of copying the map around, each server stores the ordered list of writes (that list is the log) and rebuilds its own copy of the map by replaying those writes in order. Same log, replayed the same way, means every server ends up with the identical map.
So the whole job reduces to one thing: get every server to agree on a single, ordered log of writes. Reach that agreement despite crashes and a flaky network, and you have identical servers. That agreement is what consensus means. (This 'store the log, replay it to rebuild the data' idea has a name — a replicated state machine — but the key-value picture is all you need.)
Raft's answer is to elect exactly one leader at a time. Every write goes through the leader, which appends it to its own log and then copies that log, in order, to the other servers (the followers). As long as there's a single leader, there's a single order — the hard question of 'what happened in what order' becomes 'whatever order the leader wrote things down in.'
Leader election: choosing the one leader#
Everything rests on there being exactly one leader — but the leader can crash, so the other servers need a way to notice and pick a new one, with no human involved. Here is how they do it.
Every follower keeps a countdown timer. Each time it hears from the leader — a short 'I'm still here' message called a heartbeat — it resets the timer. If the timer ever runs out, the follower assumes the leader is gone and starts an election to replace it.
Each election happens in a numbered round called a term. To start one, the follower adds one to the term number, becomes a candidate, and votes for itself. Term numbers only ever go up, so the term is a simple counter that tells every server which election is the most recent.
- A follower's timer runs out with no heartbeat. It moves to the next term, becomes a candidate, and votes for itself.
- It asks every other server for a vote — a message called RequestVote — tagged with its new term.
- A server grants the vote if the candidate's term is at least as new as its own and it hasn't already voted for someone else in this term. Each server gets one vote per term.
- If the candidate collects votes from a majority — more than half the servers, counting its own — it becomes the leader and immediately sends a heartbeat, so no other timer runs out.
- If two followers time out together they can split the vote, and no one reaches a majority. Each then waits a fresh, random amount of time and tries again, so the tie breaks quickly.
That footer note is how a stale leader fixes itself. Every message carries the sender's term. A leader that was cut off by a network problem keeps believing it's in charge — but the moment it hears a message with a higher term, it knows a newer election has happened, and it steps down to follower on its own. A higher term always wins, so the cluster can never stay stuck with two leaders once messages flow again.
PredictFive servers. Two of them time out at the same moment and both become candidates in term 4. Can both become leader?
Hint: How many votes does each need to win, and how many votes exist in total?
No. Each needs a majority — 3 of 5 — and there are only 5 votes, each server casting at most one. Two candidates can't both collect 3 votes from the same 5 servers, so at most one wins term 4. If neither reaches 3 (a split vote), they wait a random time and retry in term 5. 'Majority plus one vote per term' is exactly what makes at most one leader per term certain.
Log replication: AppendEntries and the consistency check#
Once elected, the leader accepts client commands by appending each one to its own log first, then pushes it out to the followers with a message called AppendEntries — the same message it uses as a heartbeat, just carrying entries instead of being empty. (A message one server sends another like this is called an RPC, a remote procedure call.) Each AppendEntries names the entry that should come just before the new one, so the follower can confirm its log lines up before accepting.
If the follower's log doesn't line up at that spot (it's missing entries, or has different ones from a previous, now-abandoned leader), it rejects the message. The leader then tries one position earlier next round, and keeps stepping back until it finds a point where the two logs agree — then it overwrites everything after that point on the follower with its own entries. Entries are only ever added to the end or overwritten from an agreed point; they're never shuffled around.
Go deeperThe Log Matching Property — why that one 'is the previous entry there?' check is enough
Raft guarantees two things about logs across the cluster: (1) if two logs contain an entry with the same index and term, they store the same command; and (2) if two logs contain an entry with the same index and term, then the logs are identical in all preceding entries. Together these are the Log Matching Property.
Property (1) holds because a leader creates at most one entry per index in a given term, and entries never change position once created. Property (2) is enforced step by step by the AppendEntries check: every AppendEntries names the entry that should come just before the new one, and a follower refuses unless it already has that entry. So an accepted AppendEntries proves the follower already agreed up to that point — and, one entry back at a time, all the way to the start. That single check is why the leader can repair a divergent follower by stepping backward one entry at a time until the logs match, then overwriting the rest.
Optimization: stepping back one entry per round takes as many round-trips as the two logs differ by. Real implementations have the follower report where the mismatch actually starts, letting the leader skip a whole run of entries per rejection — turning many round-trips into a handful.
The commit rule: an entry is safe once a majority has it#
An entry is committed once the leader has copied it to a majority of the servers. From that moment it is safe forever, even if the leader crashes the next instant — because any future leader is also chosen by a majority, and two majorities of the same cluster always share at least one server, which still holds the entry. So the leader keeps track of how far each follower has caught up, and marks an entry committed as soon as more than half the servers hold it.
index → entry, each tagged with the term it was created in · highlighted = committed
The two rules that keep committed data safe#
Elections and replication are enough to keep the cluster running, but not quite enough to keep it correct. Two extra rules make sure a committed entry can never be lost, no matter how leaders come and go. Both make sense now that you've seen elections, the log, and commit.
Rule 1 — a server that is behind can't win an election. When it votes, a server grants its vote only if the candidate's log is at least as up-to-date as its own (compared by the last entry's term, then its position). This is an extra check on top of the term check you saw earlier.
PredictFive servers; three of them hold committed entry #10. A candidate has the highest term in the cluster, but its own log ends at entry #7. Can it win?
Hint: A vote now needs more than a fresh term — what is the extra check?
No. Each voter also checks that the candidate's log is at least as up-to-date as its own. The three servers holding entry #10 all turn this candidate down because its log is shorter, so it can never reach a majority of 3 — at most it gets itself plus the one other server that is also behind, which is two votes. A high term lets you start an election; an up-to-date log decides who can win one. That is exactly why committed data is never lost.
Rule 2 — a new leader only counts its own entries toward commit. Older entries it inherited from a previous leader ride along once one of its own entries commits.
Putting it together: writing a key, then reading it#
All the pieces click together once you follow a single write, then a single read, through the cluster — using that key-value store from the start.
The write path. A client sends set x = 1. If it happens to reach a follower, the follower just points it at the leader — only the leader accepts writes. The leader adds x = 1 to the end of its own log, but does not touch its map yet. It sends the new entry to the followers with AppendEntries. The moment a majority have stored it, the entry is committed — safe forever, even if the leader dies the next instant. Only then does each server apply it, writing x = 1 into its own copy of the map, and the leader tells the client the write succeeded.
- Client sends set x = 1. (A follower would just redirect it to the leader.)
- Leader appends x = 1 to its log — stored, but not yet applied to the map.
- Leader sends the entry to the followers with AppendEntries.
- A majority store it → the entry is committed (safe even if the leader crashes right now).
- Every server applies it — writes x = 1 into its map — and the leader replies 'done' to the client.
The read path. A client sends read x. There's a catch: a server that believes it's the leader might have just been replaced during a network split, so answering straight from its own map could hand back a stale value. To be safe, the read goes to the leader, and the leader first confirms it is still the leader — one quick round of heartbeats with a majority — before reading x from its map and returning it. Reading from just any server is faster but can return an out-of-date value; that's the right trade only when a slightly stale answer is acceptable.
Failure modes: partitions, split votes, and split brain
If the leader is cut off from a majority of the cluster, two things happen in parallel: the isolated leader keeps accepting client writes into its own log (since nothing has told it otherwise) but can never replicate them to a majority, so they can never commit — those writes are effectively stuck. Meanwhile, the majority side notices it's heard nothing from the leader, times out, and elects a new leader among themselves (since they still have enough nodes for a majority).
When the partition heals, the old leader receives a message from the new leader carrying a higher term, recognizes it's stale, and steps down to follower — then catches its log up to the new leader's via the ordinary AppendEntries consistency check. Its uncommitted, never-replicated writes are simply discarded by being overwritten.
- Split vote — two candidates start elections at the same term and each grabs part of the cluster, so neither reaches a majority. Raft fixes this with randomized election timeouts (e.g. 150–300 ms): the node that times out first usually wins outright before others even start, so split votes are rare and self-correct on the next, re-randomized timeout.
- Leader crash — followers stop hearing heartbeats, an election timer fires, and a new leader is elected, typically within an election timeout. Committed entries survive because any new leader already holds them (election restriction).
- Network partition / split brain — the cluster splits into groups. Because a leader must reach a majority to commit, at most one group can make progress; the minority side cannot elect a leader or commit anything. This is the structural guarantee against two leaders committing conflicting data.
- Stale leader still serving reads — a partitioned-off old leader may not yet know it was deposed and could answer a read with stale data. Preventing this needs an explicit read protocol (see Variants → read-only optimizations); replication alone does not make reads linearizable (guaranteed to return the latest committed value).
QuizA 5-node Raft cluster splits 3-2 by a network partition, with the old leader on the 2-node side. What happens?
- Both sides elect a leader and later merge their logs
- The 3-node side elects a new leader and keeps committing; the 2-node side (with the old leader) cannot commit anything
- The whole cluster halts until the partition heals
- The 2-node side keeps committing because it still has the original leader
Show answer
The 3-node side elects a new leader and keeps committing; the 2-node side (with the old leader) cannot commit anything — Commit requires a majority — here, 3 of 5. The 3-node side has a majority, so it elects a new leader (higher term) and continues committing. The 2-node side, even though it holds the old leader, can never reach 3 nodes, so its new writes stay uncommitted forever. On heal, the old leader sees the higher term, steps down, and rolls back its uncommitted suffix. Logs are never 'merged' — the minority converges to the majority's log.
Quorums, fault tolerance, and message cost#
Raft's safety rests on a counting argument: any two majorities of the same set must overlap in at least one member. So if an entry is on a majority, and a future leader was elected by a majority, those two majorities share a node — and that node, by the election restriction, forced the new leader to already hold the entry. Overlap is the whole reason a majority quorum is safe.
- Fault tolerance: a cluster of N = 2f+1 nodes tolerates f crash failures and still has a majority (f+1) available. 3 nodes tolerate 1 failure; 5 tolerate 2; 7 tolerate 3.
- Why odd sizes: 4 nodes need a majority of 3 — same fault tolerance as 3 nodes (1 failure) but more nodes to coordinate and slower quorums. Even sizes buy you nothing and cost latency, so clusters are almost always 3, 5, or 7.
- Commit latency: one client write needs a single round-trip from the leader to the fastest majority of followers — roughly one network round-trip (RTT) plus a disk fsync (forcing the write out to persistent storage) on each. The slowest node in the majority does not gate you; the (f+1)-th fastest does.
- Message cost: each AppendEntries round is O(N) messages (leader to each follower) and an election is O(N) RequestVotes plus O(N) replies — both linear in cluster size, which is why Raft clusters stay small (3–7) and scale reads, not the consensus group, horizontally.
Beyond the core: what a real deployment adds
The election-and-replication core is the exam answer, but a real deployment needs a few more pieces to run for years without trouble. Here is what each one solves, in plain terms.
- Changing the set of servers. Adding or removing a machine is risky: if servers switch to the new set at slightly different moments, the old set and the new set could each elect their own leader for an instant — two leaders. The safe way is to change membership one server at a time. When you only add or remove a single machine, the old majority and the new majority always share at least one server, so they can never split into two leaders. (The original design used a more elaborate two-step scheme called joint consensus; the deep-dive below shows why changing one server at a time is enough on its own.)
- Snapshots, so the log doesn't grow forever. Left alone, the log fills the disk, and a restarting server would have to replay millions of old entries to catch up. So each server occasionally saves a snapshot — a compact picture of its current state, everything the log so far adds up to — and then throws away all the log entries the snapshot already covers. If a follower has fallen so far behind that the leader has already discarded the entries it needs, the leader just sends the whole snapshot instead of the missing entries.
- Fast reads. A read is supposed to return the latest committed value. The safe-but-slow way is to push the read through the log just like a write. Faster: before answering, the leader does one quick round of heartbeats with a majority to confirm it is still really the leader — if a newer leader had taken over, it finds out right here. Faster still: a leader can hold a short, time-limited permission slip (a lease) during which it is allowed to answer reads directly with no check at all — trading a small assumption about clocks for lower latency.
- Pre-vote, to stop a returning server from causing chaos. A server cut off from the cluster keeps timing out and raising its term higher and higher while doing no useful work. When it finally reconnects, its inflated term is higher than the real leader's — so the healthy leader sees the higher term and steps down for no good reason. Pre-vote fixes this: before actually starting an election and raising its term, a candidate first asks the others 'would you even vote for me?' If a majority would not, it never raises its term, so it can't disturb the working leader.
Go deeperWhy joint consensus needs majorities of BOTH configurations
Suppose you switch a 3-node cluster {A,B,C} to {C,D,E} by letting each node adopt the new config as soon as it hears about it. For a window, A and B might still think the cluster is {A,B,C} (majority = 2: A,B) while D and E think it is {C,D,E} (majority = 2: D,E). Now {A,B} could elect one leader and {D,E} another — two leaders in the same term, with no overlap. Split brain.
Joint consensus closes the window. During the switch, the cluster runs in a combined mode: every election and every commit must win a majority of the OLD set AND a majority of the NEW set at the same time. Neither set can decide anything on its own, so the two-leader scenario above becomes impossible. Once that combined mode is locked in, the leader moves the cluster fully onto the new set and the switch is done. The one-server-at-a-time shortcut skips this dance entirely: if you only ever add or remove a single machine, any new majority and old majority are guaranteed to share a member — so the overlap that keeps things safe is automatic.
Trade-offs: what consensus costs you
Raft buys you a single, linearizable, durable log — and you pay for it in latency, a throughput ceiling, and availability during a network split. When a split stops part of the cluster from reaching a majority, that side gives up being available — it refuses writes — to protect consistency, so no two servers ever disagree. Choosing consistency over availability like this is what people mean when they call Raft a 'CP' system (the term comes from the CAP theorem, which says a system facing a network split can keep either consistency or availability, not both).
- Availability vs consistency — under a partition, only a majority side stays writable; a cluster with no majority side is fully unavailable for writes. Raft never sacrifices consistency for availability, by design.
- Latency — every committed write pays a majority round-trip plus per-node fsync. You cannot beat one network RTT to your quorum, which dominates in geo-distributed deployments.
- Leader bottleneck — all writes (and, for strong reads, the read confirmation) funnel through one node. The leader's CPU, disk, and uplink cap write throughput; the cluster does not scale writes by adding voters. Followers can offload only stale or lease-bounded reads.
- Small clusters only — because every round is O(N) and quorums get slower with more members, Raft groups stay at 3–7 nodes. Scaling data past that means sharding into many independent Raft groups (the CockroachDB / TiKV model), not growing one group.
Raft vs Multi-Paxos vs ZAB
| Raft | Multi-Paxos | ZAB (ZooKeeper) | |
|---|---|---|---|
| Leadership | Strong single leader; all entries flow leader→follower | Optional 'distinguished proposer'; leadership is a convention, not core | Single leader (primary) elected per epoch |
| Log model | Append-only log, never has holes; follower mirrors leader | Per-slot agreement; logs can fill out of order with gaps | Broadcasts entries in the primary's order |
| Primary goal | Understandability + practical implementation | Minimal, general consensus theory | Total-order broadcast for a primary-backup store |
| Membership change | Joint consensus / single-server change | Not specified by the core protocol | Dynamic reconfiguration (added later) |
| Used by | etcd, Consul, CockroachDB, TiKV, Kafka KRaft | Google Chubby/Spanner, Megastore (Multi-Paxos variants) | Apache ZooKeeper, and systems built on it (HBase, Kafka pre-KRaft) |
The headline: Raft and Multi-Paxos are equally powerful and efficient — Raft is essentially Multi-Paxos with a strong-leader rule and a no-gaps log added to make it teachable and buildable. ZAB is close to Raft in spirit (a single leader, entries in order) because both were built for real primary-backup systems (one server is the primary that all the others copy from). The differences are mostly in wording — for instance, what Raft calls a term, ZAB calls an epoch — and in how each recovers after a leader fails.
Where Raft runs in the wild
Raft became the default consensus layer for new infrastructure after 2014, largely because it is realistic to implement correctly from the paper. Most uses follow one of two patterns: a single Raft group holding cluster metadata, or many Raft groups (one per data shard) for horizontal scale.
- etcd — the canonical Raft library and the key-value store behind Kubernetes; the entire cluster state of Kubernetes lives in a single etcd Raft group.
- HashiCorp Consul / Nomad — service discovery and scheduling; use the same battle-tested hashicorp/raft library for their server quorum.
- CockroachDB — shards ("ranges") of the keyspace are each their own Raft group, with thousands of groups per cluster, giving SQL-level horizontal scale on top of per-range consensus.
- TiKV / TiDB — the same per-region multi-Raft model; TiKV's Raft implementation is a direct port of etcd's Raft to Rust.
- Kafka KRaft — Kafka's replacement for its ZooKeeper dependency: the controller quorum now runs a Raft-based metadata log internally, removing the separate ZAB-based ZooKeeper ensemble.
Common misconceptions & gotchas
Can two nodes ever both be leader and commit conflicting entries?
Two nodes can briefly both BELIEVE they are leader (e.g. a partitioned old leader that hasn't heard about the new term), but they cannot both COMMIT. Commit requires a majority, terms only increase, and a node grants at most one vote per term — so two leaders can't exist in the same term, and a higher-term leader's majority necessarily excludes enough nodes that the stale leader can never reach its own majority. The stale leader's writes stay uncommitted and are later overwritten.
Are reads automatically linearizable just because writes go through Raft?
No — this is the most common Raft mistake. A node that thinks it's leader might be a deposed stale leader and serve old data. For linearizable reads the leader must confirm it still leads (a heartbeat round-trip to a majority, or a valid lease) and read at or after its committed index. Reading from a follower, or from an unconfirmed leader, can return stale results.
Why must clusters be odd-sized?
They don't strictly have to be, but even sizes are wasteful: a 4-node cluster needs a majority of 3 and tolerates only 1 failure — identical fault tolerance to a 3-node cluster but with an extra node to coordinate and a larger quorum to wait on. Odd sizes (3, 5, 7) maximize fault tolerance per node and avoid more tie-prone configurations.
Does Raft tolerate Byzantine (malicious/buggy) nodes?
No. Raft assumes crash-stop failures and a non-malicious network (messages may be lost, delayed, reordered, or duplicated, but not forged). A node that lies about its log or term can break safety. Tolerating Byzantine faults requires a different class of protocol (PBFT, Tendermint).
In an interview
Lead with the shape of the problem: replicate a log, not arbitrary state, by funneling all writes through a single elected leader per term. That single decision is what turns 'how do N machines agree' into 'how do we safely elect and replace a leader' — a much smaller problem.
Know the two RPCs by name (RequestVote, AppendEntries) and the two safety rules that make them correct: the log-recency check during voting (so an out-of-date node can't get elected even with a higher term), and the current-term-only commit rule (so a majority count alone never resurrects an uncommitted entry from a dead leader's term). Be ready to explain what happens during a network partition — an isolated leader keeps accepting writes that can never commit, while the majority side elects a new leader and keeps going.
Then try it in the simulator: TICK until a leader is elected, CLIENT_APPEND a couple of commands and TICK until they commit on every node, then PARTITION the leader and watch the majority side re-elect — followed by HEAL to watch the old leader discover the higher term, step down, and catch its log up.
References & further reading
- Ongaro & Ousterhout — In Search of an Understandable Consensus Algorithm (Extended Version) — the canonical Raft paper; USENIX ATC '14 Best Paper. Read this first.
- raft.github.io — The Raft homepage — interactive visualization, implementations list, and links to all resources
- Diego Ongaro — Consensus: Bridging Theory and Practice (PhD dissertation, 2014) — the long version: single-server membership changes, snapshots, lease reads, pre-vote, TLA+ spec
- The Secret Lives of Data — Raft, an animated walkthrough — the gentlest visual introduction to election and replication
- etcd — Raft library and design docs — the most widely used production Raft implementation (powers Kubernetes)
- Lamport — Paxos Made Simple (2001) — the consensus protocol Raft was designed to be more understandable than
Ready to try it?
The simulator is a real, deterministic implementation — pick a scenario and step through it, scrubbing the timeline forward and backward through every change.