The Raft Consensus Algorithm - Leader Election

Raft Basics

• Leader based:

  • Pick one server to be leader
  • It accepts client requests, manages replication
  • Pick a new leader if the current one fails

• Server states:

  • Leader
  • Follower: totally passive
  • Candidate: used for electing new leaders

• Time divided into terms:

  • Terms have numbers that increase monotonically ($+1$).
  • Each term starts with an election
    • One or more candidates attempting to become leader
  • Winning candidate (if any) serves as leader for the rest of the term
  • Terms allow detection of stale information
    • Each server stores current term
    • Checked on every request
    • Term numbers increase monotonically
  • Different servers observe term transitions differently

• Request-response protocol between servers (remote procedure calls, or RPCs). 2 request types:

  • RequestVote
  • AppendEntries (also serves as heartbeat)

Leader Election

• All servers start as followers
• No heartbeat (AppendEntries)? Start election:
  • Increment current term
  • Vote for self
  • Send RequestVote requests to all other servers
• Voting Process:
  1. Term Comparison: The candidate’s term must be at least as recent as the voter’s current term.
  2. Log Completeness: The candidate’s log must be at least as up-to-date as the voter’s log.
  3. A node can only vote for one candidate per term, and if it has already voted for another candidate or if the candidate’s log is not sufficiently up-to-date, it will reject the vote request.
• Election:
  • The follower transitions to the candidate state.
  • Increment current term
  • Send RequestVote requests to all other servers
• Election outcomes:
  1. Majority (Quorums) Votes: The candidate receives votes from a majority (quorum) of the servers. It becomes the leader and begins sending heartbeats to prevent further elections.
  2. Receiving AppendEntries: The candidate receives AppendEntries from another server with a higher term. It reverts to the follower state.
  3. Election Timeout: The candidate does not receive a majority or a heartbeat within the election timeout, so it starts a new election cycle.
  4. Network Partition: If the network is partitioned, a minority partition may repeatedly try and fail to elect a leader. The servers in this partition will continuously time out and start new election cycles. However, a majority partition could still elect a leader and continue operations, while the minority partition remains in a perpetual election state until network connectivity is restored.
  5. Split Vote: If two or more candidates receive the same number of votes without reaching a majority, this is called a split vote. In this case, each candidate will eventually time out and start a new election. The randomness in election timeouts usually ensures that one candidate will eventually win a majority in the subsequent elections.
  6. Leader Crashes or Network Failures After Election: If a leader crashes or is isolated due to network failures after winning the election, the followers will detect the lack of heartbeats and start a new election cycle.
• Each server votes for at most one candidate in a given term
• Election Safety: only one server can be elected leader in a given term
• Availability: randomized election timeouts reduce split votes.

Safety

• Must ensure that the leader for new term always holds all of the log entries committed in previous terms (Leader Completeness Property).
• Step 1: restriction on elections: don't vote for a candidate unless candidate's log is at least as up-to-date as yours.
• Compare indexes and terms from last log entries.
• Step 2: be very careful about when an entry is considered committed
  • As soon as replicated on majority? Unsafe!
  • Committed => entry in current term replicated on majority
    • All preceding entries also committed because of Log Matching Property

Credits:

https://web.stanford.edu/~ouster/cgi-bin/cs190-winter20/lecture.php?topic=raft

Trade-offs

Interview One-Liners

Q: Name Raft's three server states. A: Leader (serves requests, replicates), follower (passive), candidate (transient, runs elections).

Q: What starts an election? A: A follower missing AppendEntries heartbeats past its election timeout: it increments its term, votes for itself, and sends RequestVote to all.

Q: What are the two RPC types? A: RequestVote (elections) and AppendEntries (log replication and heartbeats).

Q: When does a voter say yes? A: At most once per term, only if the candidate's term is current and its log is at least as up-to-date (last term/index comparison).

Q: How is a split vote resolved? A: Candidates time out and retry; randomized election timeouts make one candidate usually outrun the others to a majority.

Q: What keeps a committed entry safe across leaders? A: The up-to-date voting restriction plus the commit rule (current-term entry on a majority), giving the leader completeness property.