How Raft works

Suppose you keep a small but important piece of data, such as the configuration of a cluster or a list of which server holds which shard. One copy on one machine is lost when that machine fails, so you keep copies on several machines. Now every change has to reach all the copies in the same order, or they drift apart, and the machines have to agree on that order even though messages can be delayed or lost and machines can crash at any moment.

Raft solves this. Each server keeps a log of commands. Raft makes sure every server ends up with the same commands in the same order, and each server applies them to its own copy of the data. Systems built this way are called replicated state machines. Raft needs a majority of the servers to be running and able to talk to each other: with five servers, any three are enough.

The rest of this guide follows a five-server cluster, S1 to S5, step by step. The same steps can be run in the Raft simulator, and the simulator page has a reference article on the algorithm.

Each server is a follower, a candidate or the leader. Time is divided into numbered terms, and each term has at most one leader. Every server remembers the latest term it has seen, and every message carries the sender's term. A server that receives a message from a higher term moves to that term and becomes a follower.

Servers send each other two kinds of message. Candidates send RequestVote to ask for votes. The leader sends AppendEntries to copy log entries to followers; when there is nothing new to copy, an empty AppendEntries serves as a heartbeat. Each log entry records a command and the term in which it was created.

All five servers start as followers in term 0, with empty logs and no leader. Each follower has an election timeout, a random wait chosen afresh each time, for example between 150 and 300 ms. Because the waits are random, one server's timer usually runs out well before the others.

1. Say S3's timer runs out first. S3 moves to term 1, becomes a candidate, votes for itself and sends RequestVote to the other four. The message says, in effect: "I am a candidate for term 1, and my log ends at index 0."
2. Each other server is still in term 0, so it moves to term 1. It has not voted in term 1 yet, and S3's log is at least as up to date as its own (all are empty), so it votes for S3 and resets its own timer.
3. As soon as S3 has three votes, counting its own, it has a majority and becomes leader for term 1. It does not need to wait for the remaining replies.
4. S3 immediately sends AppendEntries to everyone. These heartbeats tell the others there is a leader and reset their timers, so no one else starts an election. S3 keeps sending them at a regular interval, much shorter than the election timeout.

If two servers had timed out at almost the same moment, each might have collected only two votes. Neither would win, both would time out again after new random waits, and one would almost certainly go first next time, in term 2. This is a split vote; it costs a little time but never produces two leaders, because each server votes only once per term.

A client wants to set x = 5. It sends the command to the leader, S3; a follower would refuse and point it to S3.

1. S3 appends the entry (term 1, x = 5) to its log, say at index 1. Nothing is applied yet.
2. S3 sends AppendEntries to each follower containing the new entry, plus the index and term of the entry before it (here index 0, the empty start of the log).
3. Each follower checks that its log matches the leader's up to that point. Here it does, so the follower appends the entry and replies "success, I have everything up to index 1".
4. When S3 knows that the entry is stored on three servers, itself and two followers, the entry is committed. S3 applies x = 5 to its own data and tells the client the write succeeded.
5. The next AppendEntries from S3 carries its commit index, 1. Followers see it and apply the entry too.

The leader did not wait for the slowest two followers. That is the point of a majority: the cluster keeps working at the speed of the fastest three servers, and any two can be slow or down. A write takes about one round trip between the leader and a majority of followers, plus the time for each to write the entry to disk.

After a few more writes, S3 crashes. The followers stop receiving heartbeats.

1. The first follower whose timer runs out, say S1, becomes a candidate for term 2 and asks for votes.
2. Each server votes for S1 only if S1's log is at least as up to date as its own: its last entry has a higher term, or the same term and an index at least as high. A server that holds a committed entry S1 lacks will refuse.
3. S1 wins with three votes and becomes leader for term 2.

The vote rule is what keeps committed writes safe. A committed entry is on a majority of servers, and a candidate needs votes from a majority, so at least one voter has that entry. That voter refuses any candidate whose log is behind its own. Therefore whoever wins already has every committed entry, and the new leader never has to fetch missing committed data from anyone.

A write that S3 had received but not yet committed may or may not survive, depending on whether it reached the new leader. Its client got no reply, so from the client's point of view it may or may not have happened. The client retries with the new leader. To stop a retried command from being applied twice, Raft clients give each command a unique ID, and servers remember the last ID they applied for each client.

When S3 restarts, it comes back as a follower. It kept its term, its vote and its log on disk, because Raft requires those to be saved before a server replies to any message. It learns of term 2 from the first message it receives, and the new leader brings its log up to date.

Crashes in the middle of replication leave logs that differ. A follower can be missing entries, or it can have extra, uncommitted entries from a term in which it briefly received writes as leader before crashing. The new leader fixes this without any special recovery step, using the ordinary AppendEntries check.

Now the network splits: S1, the leader, and S2 on one side, S3, S4 and S5 on the other.

1. S1 keeps sending heartbeats, but only S2 receives them. S1 still believes it is leader, and a client that reaches it can still send it writes. S1 appends them to its log but can only get them onto two servers, so they are never committed and the client never gets a success reply.
2. On the other side, S3, S4 and S5 hear nothing from a leader. One of them times out, starts an election for term 3, and wins with three votes. Clients that reach this side can write normally, and those writes commit.
3. When the network heals, S1 receives a message carrying term 3. It sees the higher term and steps down. The new leader's AppendEntries then removes S1's and S2's uncommitted entries and replaces them with the committed ones, exactly as in step 4.

No acknowledged write is lost, and the two sides never both commit conflicting data, because only one side can have a majority. The price is that the minority side cannot make progress while the split lasts. In terms of the CAP theorem, Raft chooses consistency over availability.

Two refinements from Diego Ongaro's thesis are common in production. With CheckQuorum, a leader that has not heard from a majority within an election timeout steps down, so a cut-off leader stops accepting writes. With Pre-Vote, a server first asks whether it could win before raising its term, so a server that was cut off and keeps retrying elections does not disrupt a healthy leader when it reconnects.

Reads look simple but are easy to get wrong. A follower's data may be behind, and even the leader may be stale: in step 5, S1 still thought it was leader after the majority had moved on. A read served by S1 would have missed writes committed on the other side.

For a read that is guaranteed to be up to date, called linearizable, the leader must first confirm that it is still the leader by exchanging heartbeats with a majority, and must have committed at least one entry in its current term. Ongaro's thesis calls this approach ReadIndex. It adds a round trip but no disk write. Some systems instead give the leader a time-based lease: followers promise not to elect anyone else for a while, so the leader can answer reads alone until the lease expires. Leases save the round trip but depend on clocks running at roughly the same rate. Many systems also offer cheaper reads from followers for clients that can accept slightly stale data.

The Raft paper states the timing requirement as broadcast time ≪ election timeout ≪ mean time between failures. The heartbeat interval must be well below the election timeout so that followers do not start elections while the leader is healthy, and the timeout must be well above the time it takes to send messages, or elections will keep failing.

• It does not scale writes. Every write goes through one leader and must reach a majority. Large databases such as CockroachDB and TiKV split their data into many ranges and run a separate Raft group for each, so that different leaders handle different ranges.
• It does not provide transactions across groups. A transaction that touches data in two Raft groups needs a separate protocol on top, such as two-phase commit.
• It does not tolerate malicious servers. Raft assumes servers may crash but do not lie. Protecting against servers that send false messages needs a Byzantine fault tolerant protocol, which costs more servers and messages.
• It does not make the cluster faster with more servers. Adding servers improves fault tolerance but increases the work per write. Most clusters have three or five voting members.