Raft Paper Distillation

Context

In distributed systems, it is common to require a collection of servers to compute identical copies of the same state. Ideally, it should be fault-tolerant, remaining functional despite a few servers are down.

These replicated state machines are typically implemented using replicated log. The log stores a series of executed commands. Given the state machines are deterministic, if they contain the same log, the must be at the same state.

A consensus algorithm is one ensuring the consistency of said replicated log. It must ensure safety under non-malicious machine failures/latencies and be fully functional/responsive if the majority of machines are available.

The Raft consensus algorithm is a relatively nascent iteration considered superior to the long established Paxos algorithm, especially in terms of understandability and ease of implementation.

Condensed Summarization

State

Persistent state on all servers

Updated on stable storage before responding to RPCs

Volatile state on all servers

Volatile state on leaders

*Reinitialized after election

AppendEntries RPC

Invoked by leader to replicate log entries; also used as heartbeat

Arguments

Results

Receiver implementation

1. Reply false if term < currentTerm
2. Reply false if log doesn’t contain an entry at prevLogIndex whose term matches prevLogTerm
3. If an existing entry conflicts with a new one (same index but different terms), delete the existing entry and all that follow it
4. Append any new entries not already in the log
5. If leaderCommit > commitIndex, set commitIndex = min(leaderCommit, index of last new entry)

RequestVote RPC

Invoked by candidates to gather votes

Arguments

Results

Receiver implementation

1. Reply false if term < currentTerm
2. If votedFor is null or candidateId, and candidate’s log is at least as up-to-date as receiver’s log, grant vote

Rules for Servers

All Servers

• If commitIndex > lastApplied: increment lastApplied, apply log[lastApplied] to state machine
• If RPC request or response contains term T > currentTerm: set currentTerm = T, convert to follower

Followers

• Respond to RPCs from candidates and leaders
• If election timeout elapses without receiving AppendEntries RPC from current leader or granting vote to candidate: convert to candidate

Candidates

• On conversion to candidate, start election:
  • Increment currentTerm
  • Vote for self
  • Reset election timer
  • Send RequestVote RPCs to all other servers
• If votes received from majority of servers: become leader
• If AppendEntries RPC received from new leader: convert to follower
• If election timeout elapses: start new election

Leaders

• Upon election: send initial empty AppendEntries RPCs (heartbeat) to each server; repeat during idle periods to prevent election timeouts
• If command received from client: append entry to local log, respond after entry applied to state machine
• If last log index ≥ nextIndex for a follower: send AppendEntries RPC with log entries starting at nextIndex
  • If successful: update nextIndex and matchIndex for follower
  • If AppendEntries fails because of log inconsistency: decrement nextIndex and retry
• If there exists an N such that N > commitIndex, a majority of matchIndex[i] ≥ N, and log[N].term == currentTerm: set commitIndex = N

InstallSnapshot RPC

Invoked by leader to send chunks of a snapshot to a follower. Leaders always send chunks in order

Arguments

Results

Receiver implementation

1. Reply immediately if term < currentTerm
2. Create new snapshot file if first chunk (offset is 0)
3. Write data into snapshot file at given offset
4. Reply and wait for more data chunks if done is false
5. Save snapshot file, discard any existing or partial snapshot with a smaller index
6. If existing log entry has same index and term as snapshot’s last included entry, retain log entries following it and reply
7. Discard the entire log
8. Reset state machine using snapshot contents (and load snapshot’s cluster configuration)

The Algorithm Explained

The core of raft can be divided into three components: leader election, log replication, safety

Raft is governed by several properties to ensure it works as intended. These properties are followed by design of the algorithm and will be cited throughout later explanation.

Servers in Raft communicated through remote procedure calls (RPCs). RPCs are issued in parallel.

Leader Election

All servers start as followers. A server remains in follower state so long as it receives valid RPCs from a leader or candidate.

Leaders send periodic heartbeat (AppendEntries RPC without log) to followers to maintain authority.

If a follower receives no valid communication over a period of time called election timeout, then it assumes no leader or no one is trying to be a leader. It starts an election

To do so, it increments it currentTerm and convert to candidate. It votes for itself then issues RequestVote RPCs to all other servers. It remains in this state until:

1. It wins the election
2. Another server established itself as leader
3. A period of time (election timeout) goes by with no winner

Winning the election

A candidate wins the election if it receives votes from the majority of the servers for the same term. Each server may vote once, and votes on a first-come-first-serve basis. This ensures at most one candidate can win the election for a particular term (Election Safety Property).

One subtleties is that a follower will deny to vote for a candidate if its own log is more up-to-date than that of the candidate’s. Raft determines who is more up-to-date as follows:

1. If the logs have last entires with different terms, log which later/higher term is more up-to-date
2. Else the log have last entries with the same terms, longer log is more up-to-date

Once elected leader, it starts sending heartbeats immediately to establish position and prevent further elections.

Somebody got it first

While waiting for replies, a candidate may receive AppendEntries RPC from another server claiming to be the leader.

If the leader’s term in the RPC is at least as large the candidate’s currentTerm, then the candidate recognizes its leadership as legit and reverts back to follower. Otherwise the candidate rejects the RPC and continues in its state.

Still waiting…

If many followers transitioned to candidates at the same time, the voltes may be split such that no one receives the majority of votes. In which case, candidates would timeout, increase their term and initiate another round of RequestVote RPCs.

Raft randomizes election timeout for each server to avoid the chance of splitting votes.

Log Replication

General Process

Once a leader is elected, it starts servicing client request. Each request contains a command to be executed by the state machine. The leader appends the command along with the currentTerm as a new entry to the log. It then issues AppendEntries RPC to all followers to replicate this entry.

Once majority of the followers has successfully replicated said entry, the leader applies the command to the state machine and returns the result to the client. The leader retries issuing AppendEntries RPC indefinitely until all followers has that entry stored (even after replying to the client).

When the leader decides to apply the entry, all entries up to and including the about-to-be-applied entry is committed. The leader keeps track of the index of the latest committed entry and broadcast it to all followers within the AppendEntries RPC (including heartbeat) so they can commit+apply their local entries accordingly.

Consistency

Raft guarantees the consistency of committed log entries, that is all committed entries will eventually be executed by all available servers.

Conceptually, we know that a committed entry means a majority of servers must have that entry stored. We also know that a leader’s log must be as least as up-to-date as majority of the servers. Therefore, the leader must hold all committed entries (Leader Completeness Property).

Raft does not allow leader to overwrite/delete its own log entries (Leader Append-Only Property) and the leader forces followers’ logs to duplicate its own in case of inconsistencies. This is essentially how Raft keeps log consistency.

Raft’s log consistency is governed by the Log Matching Property which states:

1. If two entries in different logs have the same index and term, then they store the same command
2. If two entries in different logs have the same index and term, then the logs are identical in all preceding entries

The first clause follows from the fact that a leader only ever creates one entry with a given log index at a given term and never change its position. To ensure the second clause however requires a bit more work.

When sending AppendEntries RPCs, the leader includes the term and index of the entry immediately preceding the new entry. If the follower could not locate an entry of the same term and index then it refuses the new entry and alert the leader (the consistency check).

This means followers will only attempt to append an entry if its previous entry match that of the leader’s. We know at the very initial state (empty log), the leader’s log match the followers’. Then by induction, the second clause is satisfied.

What happens then when the follower refuses and alerted the leader, or how to deal with inconsistencies?

As a reminder, in Raft leader is the source of truth so it attempts to make followers duplicate its log. To do so, it must first find the latest log entry that they agree with each other.

The leader maintains a nextIndex for each follower, which specifies the index of the next log it will send to that follower. The value is initialized to the index 1 after the leader’s latest entry. When the consistency check above failed, the leader decrements the corresponding nextIndex and tries AppendEntries RPC until the matching is found.

This removes conflicting entry (if any) and bring that follower’s log consistent with the leader’s

Safety

A leader never commits entry from prior terms, only entries from the current leader’s term are committed by the majority rule, since entries from prior terms may or may not have been replicated to majority of the servers

However, once an entry of the leader’s current term has replicated to majority of the followers, by the Log Matching Property, any entries from prior terms must have also been replicated on those servers. Then when the leader commits the current-term entry, all proceeding entries can be safely (and indirectly) committed.

Once a server applies an entry at a given index to its state machine, it must be the case that its log is identical to the current leader up and including this entry and this entry is already committed. By the Leader Completeness Property and Log Matching Property, future leaders must also have that entry stored at the same index. So when future servers apply that index it must apply the same value (State Machine Safety Property). And since Raft requires servers to apply entries in order, all servers would eventually apply the same set of log entries to their state machine in the same order.

While Raft’s safety does not depend on time, availability does. So to ensure Raft to make progress, timing is critical. As such, Raft must satisfy the following timing requirement: $\text{broadcastTime} \ll \text{electionTimeout} \ll \text{MTBF}$ boradcastTime is the average time it takes for a server to send an RPC in parallel to all servers and receive their replies; electionTimeout is what described previously; MTBF is the average interval between failures of a single server. Following the inequality, each value on the left should be an order of magnitude smaller than the value on their right.