Raft Consensus Algorithm Explained: Leader Election and Log Replication
You write balance = 100 to a database that runs on three servers. The server that accepted the write crashes a second later. Now the other two get a read request. Do they return 100, or the old value? And if they disagree, which one is right?
Getting servers to agree on one answer, even when some of them crash, is called consensus. Raft is the consensus algorithm behind etcd (the store that keeps Kubernetes state) and behind Kafka's metadata since Kafka 4.0.
What problem does Raft solve?
Raft keeps the same list of commands, in the same order, on every server. This list is called a replicated log. Each server reads its log from the top and applies every command to its own copy of the data. The part that applies the commands is called the state machine: in a database, it's the code that changes the tables.
The idea is simple: same commands, same order, same result.
Log on server A, B, and C:
1: SET x = 1
2: SET x = 5
3: DEL y
Result on every server: x = 5, y doesn't existIf server C applied SET x = 5 before SET x = 1, it would end with x = 1, and your reads would depend on which server answers. Raft's whole job is to make sure that never happens, even when servers crash or the network drops messages.
Raft isn't the first algorithm for this. Paxos solved the same problem earlier, but the Raft authors designed Raft to be easier to learn. In their study, 33 of 43 students answered Raft questions better than Paxos questions.
Limitation:
Consensus costs at least one network round trip between servers for every write. You need it for data that must never disagree, such as configuration, leader locks, or metadata. You don't need it for a cache.
Leader, follower, candidate: the three Raft roles
Every server in a Raft cluster is in one of three roles at any moment:
- Leader. Exactly one server accepts all writes from clients and sends them to the others.
- Follower. Every other server. Followers don't take decisions on their own. They store what the leader sends and answer its messages. If a client sends a request to a follower, the follower redirects it to the leader.
- Candidate. A follower that thinks the leader is gone and asks the other servers to vote for it.
The leader decides the order of commands, so the followers never have to agree on order among themselves. They only have to copy the leader.
How Raft leader election works
The leader proves it's alive with heartbeats: small messages it sends to every follower on a regular schedule. Each follower runs a timer called the election timeout. Every heartbeat resets the timer. If the timer runs out with no heartbeat, the follower decides the leader is gone and starts an election.
Raft counts elections with a number called the term. Each term has at most one leader. To start an election, the follower does three things:
- It increases the term by one, for example from term 1 to term 2.
- It becomes a candidate and votes for itself.
- It asks every other server for its vote.
Each server gives one vote per term to the first candidate that asks. The candidate that collects a majority of the cluster's votes becomes the leader for that term and starts sending heartbeats right away.
Example with three servers A, B, and C. A is the leader in term 1 and crashes. B's timer runs out first. B moves to term 2, votes for itself, and asks C. C votes for B. B now has 2 votes out of 3, which is a majority, so B is the leader of term 2.
What if B and C time out at the same moment? Both become candidates, both vote for themselves, and nobody gets a majority. Raft avoids this most of the time with a random timeout: each server picks a new random value from a range, for example 150–300 ms in the Raft paper. One server almost always times out first and wins before the others start.
Note: When a split vote still happens, the term ends with no leader, and the servers try again in the next term with new random timeouts. Without a leader, the cluster accepts no writes.
How Raft replicates the log and commits a write
Once there is a leader, every write follows the same path:
- The client sends the command to the leader.
- The leader appends the command to its own log.
- The leader sends the new entry to every follower.
- Each follower stores the entry and replies "OK".
- When a majority of servers (the leader counts) have stored the entry, the entry is committed.
- The leader applies the command to its state machine and answers the client. In subsequent messages, followers learn the entry is committed and apply it too.
"Committed" is the word to remember. A committed entry is safe: Raft guarantees it will never be lost or replaced, even if the leader crashes right after answering the client.
Example with five servers. The leader and two followers store entry 7. That's 3 of 5, a majority, so entry 7 is committed, and the client gets its answer. The other two followers are slow and receive entry 7 later. The client doesn't wait for them.
This is also why Raft gives you strong consistency: once the client gets "OK", every future leader has that write. As explained in Consistency Models for Distributed Systems, that's the strongest model and the most expensive one.
Cost
Every write waits for a majority, so it's as fast as the slowest server in the fastest majority. In a five-server cluster, the leader waits for the second-fastest follower.
What happens when the Raft leader crashes or the network splits (split brain)?
The leader crashes. The followers stop receiving heartbeats, one times out, and a new election starts. There's one extra rule: a server refuses to vote for a candidate whose log is less up to date than its own. A committed entry is stored on a majority, and a candidate needs a majority of votes, so at least one voter has every committed entry. That voter blocks any candidate that's missing an entry. As a result, a new leader always has every committed write.
The network splits. Take five servers, and a network failure cuts them into a group of 2 and a group of 3. The old leader is in the group of 2.
- The old leader keeps accepting writes, but it can reach only 2 of 5 servers. That's not a majority, so none of these writes become committed, and the clients never get "OK".
- In the group of 3, the followers stop getting heartbeats. One of them starts an election in term 5 and wins with 3 of 5 votes. This group keeps working.
- When the network heals, the old leader receives a message with term 5. It sees a higher term than its own term 4, steps down to follower, and replaces its uncommitted entries with the new leader's log.
Two groups can't both have a majority of the same cluster, so two leaders can't both commit writes. That's how Raft avoids split-brain. For the other ways systems avoid it, see the split-brain question in Microservices And Distributed Systems Interview Questions.
Limit. The minority side can't accept writes until the network heals. Raft picks consistency over availability during a network partition, which is the trade-off described in the CAP theorem.
How many nodes does a Raft cluster need? 3 or 5
A majority is more than half: n / 2 + 1, rounded down. The cluster keeps working as long as a majority is alive. This table comes from the etcd documentation:
| Servers | Majority | Failures tolerated |
|---|---|---|
| 1 | 1 | 0 |
| 2 | 2 | 0 |
| 3 | 2 | 1 |
| 4 | 3 | 1 |
| 5 | 3 | 2 |
| 6 | 4 | 2 |
Look at the even numbers. Two servers tolerate no failures, the same as one server. Four servers tolerate one failure, the same as three. The extra server adds cost and makes each write wait for one more reply, but it doesn't let the cluster survive more failures. So use 3 servers when the cluster must survive one failure, and 5 when it must survive two.
Cost. More servers mean slower writes, because every write must reach a larger majority. The etcd documentation suggests no more than seven members.