Raft simulator

The circles are five servers, S1 to S5. The leader is filled in black, a candidate is shaded, and the grey arc around a follower shows how long it will wait before starting an election. Dots moving along the lines are messages: vote requests, append-entries messages from the leader, and replies. Messages take 8 to 20 ms to arrive, and time runs in slow motion so you can follow them. The table below shows each server's log, and the panel on the right explains each step as it happens.

Try these:

• Wait for the first election, then press Write to the leader a few times. Each write appears in the leader's log first, then in the followers', and becomes committed (filled in) once three servers have it.
• Select the leader and press Stop. Within a few hundred milliseconds another server's timer runs out and it wins an election for a higher term. Restart the old leader: it rejoins as a follower and catches up.
• Press Split 2 | 3. The old leader ends up on the side with two servers. Write to it with Write to its name: it accepts the write but can never commit it. The three on the other side elect a new leader and commit their own writes. Heal the split and watch the old leader step down and throw its uncommitted entries away.
• Cut off a single follower for a while, then reconnect it. Cut off on its own, it keeps starting elections and raising its term, and when it comes back the higher term forces the leader to step down. The Pre-Vote extension described below exists to prevent this.

Every message, timer and log entry comes from the simulation, which follows the rules in Figure 2 of the Raft paper. It leaves out snapshots and membership changes. Timeouts and delays are random but seeded, so Reset replays the same run.

Raft is a consensus algorithm: a method that lets a group of servers agree on a sequence of values even when some of them crash or lose contact. It is used to build replicated state machines. 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, so all copies stay identical.

Raft works by electing one server as leader. Clients send all writes to the leader, which adds them to its log and copies them to the other servers. Once a majority of servers have stored an entry, it is committed: it will never be lost or changed, and it is safe to apply and to report success to the client. With five servers the cluster keeps working while any two are down.

Raft was designed by Diego Ongaro and John Ousterhout at Stanford University and published in 2014. Their main goal was understandability, because the older Paxos algorithm was widely considered hard to learn and hard to implement correctly.

Every server is in one of three roles. A follower is passive: it answers requests from leaders and candidates. A candidate is trying to become leader. The leader handles all client writes and sends regular messages to the others. In normal operation there is one leader and every other server is a follower.

Time is divided into terms, numbered 1, 2, 3 and so on. Each term begins with an election, and at most one leader can be elected in a term. If an election fails, for example because two candidates split the vote, the term ends without a leader and a new term starts soon after. Every message carries the sender's term. A server that sees a higher term than its own updates its term and becomes a follower; a message with an older term is rejected. Terms act as a logical clock that lets servers recognise out-of-date leaders.

Raft uses two kinds of message. RequestVote is sent by candidates during elections. AppendEntries is sent by the leader to copy log entries, and also, with no entries, as a heartbeat to tell followers that the leader is still there.

A follower expects to hear from a leader regularly. If it hears nothing for a period called the election timeout, it assumes there is no working leader. It increases its term, becomes a candidate, votes for itself and sends RequestVote to every other server.

Each server votes for at most one candidate per term, first come, first served, and only if the candidate'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 equal or higher index. This rule means a server missing committed entries cannot win, which the simulator shows when a lagging server is refused. A candidate that collects votes from a majority becomes leader and immediately sends heartbeats so that no one else starts an election. A candidate that hears from a leader with a term at least as high as its own steps back to follower.

If several followers time out together, they can split the vote so that no one gets a majority. Raft makes this unlikely by choosing each election timeout at random; the paper suggests a range such as 150 to 300 ms. Usually one server times out first, wins, and sends heartbeats before the others time out. For this to work, the time to send a message to every server must be much shorter than the election timeout, and the timeout much shorter than the average time between server failures.

This is the first election the simulator above runs when the page loads or after Reset. Its timers are random but seeded, so it is the same every time. Times are simulated milliseconds. It happens to include two candidates in the same term.

Each log entry holds a command and the term in which the leader received it. When the leader receives a write, it appends an entry to its own log and sends AppendEntries to each follower. Followers that are slow or unreachable are retried until they have every entry.

Each AppendEntries message includes the index and term of the entry just before the new ones. A follower accepts the message only if its own log has an entry at that index with that term. Because of this check, Raft maintains the log matching property: if two logs have an entry with the same index and term, they hold the same command at that index and are identical in all earlier entries.

After a leader crashes, logs can disagree: a follower may be missing entries, or may have extra entries from a term in which it was briefly leader. The new leader repairs this by moving backwards. When a follower rejects an AppendEntries, the leader retries from an earlier index until the two logs agree, and the follower then deletes any entries after that point that conflict with the leader's and appends the leader's entries. The leader never deletes or overwrites entries in its own log.

The leader marks an entry as committed once it is stored on a majority of servers. Committing an entry also commits every entry before it. The leader includes its commit index in each AppendEntries message, so followers learn which entries are safe to apply. Only then is the client told that its write succeeded.

There is one subtle rule. A leader only counts replicas to commit entries from its own term. An entry from an earlier term can be on a majority of servers and still be overwritten if a different server becomes leader, a case the paper illustrates in its Figure 8. Older entries become committed indirectly, when an entry from the current term after them is committed. For this reason most implementations, including etcd's, have a new leader add an empty entry as soon as it is elected, which the simulator also does.

The Raft paper proves that the algorithm always keeps the following properties, whatever the timing of messages and failures:

• Election safety. At most one leader can be elected in a given term.
• Leader append-only. A leader never overwrites or deletes entries in its log; it only appends.
• Log matching. If two logs contain an entry with the same index and term, the logs are identical up to that index.
• Leader completeness. If an entry is committed in a term, it will be in the log of every leader of every later term.
• State machine safety. If a server has applied an entry at some index, no server will ever apply a different entry at that index.

Raft guarantees safety but not progress in every situation. If a majority cannot communicate, no leader can be elected and nothing new is committed until the network recovers. In terms of the CAP theorem, Raft chooses consistency over availability during a partition.

Crashed servers

A server must save its current term, the candidate it voted for, and its log to stable storage before answering any message, so that a restart cannot make it vote twice in one term or forget entries it acknowledged. Everything else, including which entries are committed, is rebuilt from the leader after a restart. Followers that are down are simply retried; the cluster keeps working as long as a majority is up.

A leader on the minority side

If the network splits and the leader is on the smaller side, it keeps believing it is leader and may keep accepting writes, but it cannot get them onto a majority, so they are never committed and no client is told they succeeded. Meanwhile the majority side elects a new leader with a higher term. When the network heals, the old leader sees the higher term, steps down, and its uncommitted entries are replaced. Clients can lose a write this way, but only one that was never acknowledged.

The basic algorithm does not make a leader step down on its own when it loses contact with the majority. Ongaro's PhD thesis describes an optional check, often called CheckQuorum, in which a leader steps down if it has not heard from a majority within an election timeout.

Disruptive servers and Pre-Vote

A server that is cut off from the others keeps timing out and starting elections, raising its term each time. When it reconnects, its high term forces the current leader to step down, causing a needless election. The thesis describes Pre-Vote: before raising its term, a would-be candidate asks whether it could win, and the others say no if they have heard from a leader recently. etcd, for example, implements both Pre-Vote and CheckQuorum as options.

Servers are added and removed while the cluster keeps running. Switching all servers from the old membership to the new one at once is unsafe, because during the switch two separate majorities could exist. The paper describes joint consensus, in which decisions temporarily need majorities of both the old and the new membership. The thesis describes a simpler method that most implementations use: change one server at a time, since any majority of the old membership and any majority of the new one then always overlap.

Logs cannot grow forever. Each server periodically takes a snapshot of its state and deletes the log entries the snapshot covers. A leader that has deleted entries a slow follower still needs sends it the snapshot instead, with an InstallSnapshot message.

Paxos, described by Leslie Lamport in the late 1980s and published in 1998, was the standard consensus algorithm before Raft, and Google's Chubby lock service and Spanner database are built on versions of it. Raft solves the same problem with the same fault tolerance, and the two are closely related: Raft's terms correspond to Paxos ballot numbers.

The differences are mainly in structure. Paxos is usually explained as agreement on a single value, and building a replicated log from it (Multi-Paxos) leaves many details to the implementer. Raft describes the whole system, including leader election, log repair and membership changes, and keeps it simpler with a strong leader through which all entries flow, and logs that are filled in order without gaps. In a user study in the Raft paper, students at two universities scored higher on a quiz about Raft than on one about Paxos.

In a system design interview, Raft is rarely something to implement. It is the reason a component such as etcd, ZooKeeper or Consul can be trusted for leader election, distributed locks, configuration and metadata. Points worth making:

• Where it fits. Small, critical state that must never diverge. Bulk data is usually sharded, with one Raft group per shard, as CockroachDB and TiKV do.
• Cluster size. Three or five servers. More servers survive more failures but make every write wait for more acknowledgements.
• Write latency. Each committed write costs at least one round trip from the leader to a majority, plus a write to disk on each. Spreading servers across regions makes that round trip a cross-region one.
• Reads. A leader cannot be sure it is still leader without checking. Linearizable reads either confirm leadership with a majority first (ReadIndex, described in Ongaro’s thesis) or rely on a time-based lease. Reading from a follower is faster but can return old data.
• Partitions. Raft is a CP design: the minority side stops making progress until the network heals.

Diego Ongaro developed Raft as a PhD student at Stanford with his adviser John Ousterhout. The paper In Search of an Understandable Consensus Algorithm was presented at the USENIX Annual Technical Conference in 2014, where it received a best paper award. Ongaro's 2014 thesis, Consensus: Bridging Theory and Practice, gives the full algorithm, including membership changes, Pre-Vote and client interaction, and a formal specification in TLA+.

Open-source implementations appeared quickly, and etcd and Consul adopted Raft early. Raft has since become the usual choice for new systems that need a small, strongly consistent replicated store.