Raft and the Distributed Consensus Problem

1. The Distributed Consensus Problem

Before solving a problem, we must define it. At its heart, consensus is about getting a group of independent actors to agree on a single decision.

• Technical Explanation:
  In a distributed system, consensus algorithms must ensure three properties, even in the face of non-Byzantine (i.e., crash-stop, not malicious) failures:

  1. Agreement (Safety): All non-faulty nodes that decide on a value must decide on the same value. The system can never have a "split brain" where different nodes think the state is different.
  2. Validity (Safety): The value that is decided upon must have been proposed by one of the nodes. The algorithm can't just invent a value.
  3. Termination (Liveness): All non-faulty nodes eventually decide on a value. The algorithm must make progress and can't get stuck indefinitely.

  Achieving all three is notoriously difficult due to network partitions, message loss, and server crashes. The famous FLP Impossibility Result proved that in a fully asynchronous system where messages can be delayed indefinitely, there is no algorithm that can guarantee termination. Real-world algorithms like Raft get around this by using timeouts and assuming bounded network delay for liveness, while always guaranteeing safety.

• Metaphor for a 5-Year-Old:
  Imagine a group of friends trying to decide what game to play: tag or hide-and-seek. They can only communicate by sending paper airplanes, but sometimes the planes get lost or take a long time to arrive.

  • Agreement: Everyone must end up playing the same game. It would be chaos if half played tag and half played hide-and-seek.
  • Validity: The chosen game must be either tag or hide-and-seek. They can't suddenly decide to play checkers.
  • Termination: Eventually, everyone figures out which game is being played and starts playing. No one is left waiting forever.

• Python Code Snippet (Illustrating the Problem):
  This naive code shows why consensus is hard. If messages are lost, nodes can end up with different results, violating the Agreement property.

  import random
  
  # A group of servers (nodes)
  SERVERS = ['server1', 'server2', 'server3']
  # A shared log on each server
  logs = {s: None for s in SERVERS} 
  
  def naive_propose(value):
      """A naive proposal function that fails under message loss."""
      print(f"LEADER: Proposing value '{value}' to all servers.")
      
      for server in SERVERS:
          # Simulate a 33% chance of message loss to each server
          if random.random() > 0.33:
              print(f"  -> Message delivered to {server}.")
              logs[server] = value
          else:
              print(f"  -> X Message to {server} was lost!")
      
      print("\nFinal state of logs:")
      for server, log_value in logs.items():
          print(f"  - {server}: {log_value}")
  
  # --- Simulation ---
  # The leader tries to get everyone to agree on 'A'
  naive_propose('A')
  
  # In many runs, the logs will be inconsistent. For example:
  # server1: A
  # server2: None
  # server3: A
  # This is a consensus failure!
  

2. Raft's Approach: Decomposition and a Strong Leader

The complexity of previous algorithms like Paxos made them notoriously hard to understand and implement. Raft was designed with understandability as its primary goal. It achieves this by breaking the problem down.

• Technical Explanation:
  Raft decomposes consensus into three mostly independent subproblems:

  1. Leader Election: Electing one server to be the single point of coordination.
  2. Log Replication: The leader accepts commands from clients, appends them to its log, and replicates that log to the other servers (followers).
  3. Safety: Ensuring the two rules above are sufficient to guarantee correctness.

  The system operates with a strong leader. All client writes go through the leader, which simplifies the system flow. At any given time, each server is in one of three states:

  • Leader: Handles all client interaction and log replication. There is at most one leader.
  • Follower: Completely passive. Only responds to requests from the leader and candidates.
  • Candidate: Used during an election to try to become the new leader.

  Raft also divides time into arbitrary-length terms, which act as a logical clock. Each term begins with an election. If an election is successful, a single leader manages the cluster for the rest of the term. This term number is included in every RPC, allowing servers to detect and ignore stale messages.

• Metaphor for a 5-Year-Old:
  Our group of friends decides on a better system. For each game they want to play (a "Term"), they elect one person as the "Game Master" (Leader).

  • Only the Game Master can decide on new rules (Log entries).
  • Everyone else is a "Player" (Follower) and just listens to the Game Master.
  • If the Players don't hear from the Game Master for a while, one of them might declare, "I want to be the new Game Master!" (become a Candidate) and ask for votes.

• Python Code Snippet:
  This snippet from a Raft implementation shows the basic structure: the states, term, and other core variables.

  from enum import Enum
  import threading
  
  class NodeState(Enum):
      FOLLOWER = "follower"
      CANDIDATE = "candidate"
      LEADER = "leader"
  
  class RaftNode:
      def __init__(self, node_id, cluster_nodes):
          # --- Persistent state (must be saved to disk) ---
          self.node_id = node_id
          self.current_term = 0
          self.voted_for = None
          self.log = []  # The replicated log itself
  
          # --- Volatile state ---
          self.commit_index = -1
          self.last_applied = -1
          self.state = NodeState.FOLLOWER
          
          # --- Leader-specific volatile state ---
          self.next_index = {} # For each follower, index of the next log entry to send
          self.match_index = {} # For each follower, index of highest log entry known to be replicated
  
          self.cluster_nodes = cluster_nodes
          self.lock = threading.Lock()
          print(f"Node {self.node_id} initialized in term {self.current_term} as a {self.state.value}")
  
  # Raft is all about managing transitions between these states
  # based on messages and timeouts.
  node = RaftNode('node_0', ['node_0', 'node_1', 'node_2'])
  

  Code adapted from the article 'Advanced Algorithms Every Senior Developer Must Know'.

3. Leader Election in Raft

How does the cluster choose a leader and handle its failure? Raft uses a timeout-based mechanism.

• Technical Explanation:
  1. Timeouts: Each follower has a randomized election timeout (e.g., 150-300ms). It expects to receive heartbeats (empty AppendEntries RPCs) from the leader within this time.
  2. Becoming a Candidate: If a follower's timeout elapses without a heartbeat, it assumes the leader has failed. It transitions to the Candidate state, increments the current_term, votes for itself, and resets its election timeout.
  3. Requesting Votes: It then sends RequestVote RPCs to all other servers.
  4. Voting: Other servers will grant their vote if:
     • They haven't already voted in the current term.
     • The candidate's log is at least as up-to-date as their own (this is a key safety rule we'll cover in Concept 5).
  5. Winning the Election: If the candidate receives votes from a majority of the cluster, it becomes the Leader. It immediately starts sending heartbeats to establish its authority.
  6. Losing or a Split Vote: If another server establishes leadership first, or the candidate doesn't win a majority within its timeout (a "split vote"), it transitions back to a Follower. The randomized timeouts make split votes rare and resolve them quickly in the next term.

• Metaphor for a 5-Year-Old:
  The Game Master is supposed to clap every few seconds to let everyone know they're still there. All Players have a random alarm clock.

  • If a Player's alarm goes off and they haven't heard a clap, they stand up and shout "I'm the new Game Master! Who votes for me?".
  • Each of the other Players will raise their hand for the first person they hear ask, but only once.
  • If the candidate gets more than half the hands raised, they become the new Game Master and start clapping. If not, they sit down, and the process repeats. The random alarms make it unlikely for two people to stand up at the exact same time.

• Python Code Snippet:
  This code shows how a follower detects a timeout and transitions to a candidate to start an election.

  import time
  import random
  
  class RaftNode:
      # ... (from previous snippet) ...
      def __init__(self, node_id, cluster_nodes):
          # ...
          self.last_heartbeat = time.time()
          self.election_timeout = random.uniform(0.150, 0.300) # Randomized!
          self.votes_received = set()
  
      def _handle_follower(self):
          """Follower logic: if timeout elapses, become a candidate."""
          if time.time() - self.last_heartbeat > self.election_timeout:
              print(f"Node {self.node_id}: Election timeout! Becoming candidate for term {self.current_term + 1}.")
              self._become_candidate()
  
      def _become_candidate(self):
          """Transition to candidate state and start an election."""
          with self.lock:
              self.state = NodeState.CANDIDATE
              self.current_term += 1
              self.voted_for = self.node_id # Vote for self
              self.votes_received = {self.node_id}
              self.last_heartbeat = time.time() # Reset timer for new election
              self.election_timeout = random.uniform(0.150, 0.300)
              
              # In a real implementation, this is where you would
              # send RequestVote RPCs to all other nodes.
              print(f"Node {self.node_id}: Started election for term {self.current_term}.")
  
  # In the full loop, `_handle_follower()` would be called repeatedly.
  

  Code adapted from the article 'Advanced Algorithms Every Senior Developer Must Know'.

4. Log Replication in Raft

Once a leader is elected, its job is to manage the replicated log, ensuring all followers eventually have an identical copy.

• Technical Explanation:
  1. A client sends a command to the leader.
  2. The leader appends the command to its own log as a new entry, marked with the current term number.
  3. The leader sends AppendEntries RPCs to its followers, containing the new entry(ies).
  4. A follower receives the RPC. If the entry immediately preceding the new one in the RPC matches what the follower has in its log (same index, same term), it appends the new entry and replies with success. If not, it rejects the RPC.
  5. The leader retries with earlier log entries until it finds a point of agreement, then overwrites the follower's log from that point on. This forces consistency.
  6. An entry is committed when the leader learns it has been replicated on a majority of servers.
  7. Once an entry is committed, the leader can apply the command to its state machine (e.g., a key-value store) and return the result to the client. The leader also informs followers of the latest commit index in subsequent AppendEntries RPCs.

• Metaphor for a 5-Year-Old:
  The Game Master (Leader) wants to add a new rule: "No running on the grass".

  1. They write it on page 5 of their master rulebook.
  2. They send a copy of page 5 to all Players (Followers).
  3. When a Player gets the new page, they check if their page 4 matches what the Game Master said page 4 should be. If it does, they add page 5 and tell the Game Master "Got it!".
  4. Once the Game Master hears back from more than half the Players, they stamp page 5 as "OFFICIAL" (committed).
  5. If a Player had the wrong page 4, the Game Master would just send them the correct page 4, and then page 5, to fix their book.

• Python Code Snippet:
  This handle_append_entries function shows how a follower processes an RPC from a leader, checking for consistency and appending entries.

  class RaftNode:
      # ...
      def handle_append_entries(self, request):
          with self.lock:
              # 1. Reply false if term < current_term
              if request.term < self.current_term:
                  return {"term": self.current_term, "success": False}
              
              # If we see a higher term, we step down and become a follower
              if request.term > self.current_term:
                  self.current_term = request.term
                  self.state = NodeState.FOLLOWER
                  self.voted_for = None
  
              # We are a follower in the correct term
              self.last_heartbeat = time.time()
  
              # 2. Reply false if log doesn’t contain an entry at prevLogIndex
              #    whose term matches prevLogTerm
              if request.prev_log_index >= 0:
                  if (request.prev_log_index >= len(self.log) or 
                      self.log[request.prev_log_index].term != request.prev_log_term):
                      return {"term": self.current_term, "success": False}
              
              # 3. If an existing entry conflicts with a new one, delete it and all that follow
              # 4. Append any new entries not already in the log
              # (This logic is combined in practice)
              
              # Find first mismatch and truncate
              for i, entry in enumerate(request.entries):
                  log_index = request.prev_log_index + 1 + i
                  if log_index < len(self.log) and self.log[log_index].term != entry.term:
                      self.log = self.log[:log_index] # Truncate conflicting entries
                      break
              
              # Append new entries
              self.log.extend(entry for entry in request.entries if entry.index >= len(self.log))
              
              # 5. If leaderCommit > commitIndex, set commitIndex = min(leaderCommit, index of last new entry)
              if request.leader_commit > self.commit_index:
                  self.commit_index = min(request.leader_commit, len(self.log) - 1)
                  # self._apply_to_state_machine() # Apply newly committed entries
              
              return {"term": self.current_term, "success": True}
  

  Code logic adapted from the Raft paper and 'Advanced Algorithms Every Senior Developer Must Know'.

5. Elite Interview Deep Dive: Raft's Safety Guarantees

This is the most critical part: why is Raft correct? It comes down to two key properties enforced by the rules we've discussed. Simply replicating to a majority isn't enough; the leader election process itself must be safe.

• Technical Explanation:
  Raft guarantees that no committed entries will ever be lost or overwritten. This is primarily achieved by the Leader Completeness Property, which states: a leader for any given term must contain all entries committed in all previous terms.

  How is this enforced? Through a simple restriction on voting:

  A voter denies its vote if its own log is more up-to-date than the candidate's log.

  "More up-to-date" is defined by comparing the index and term of the last entries in the logs. A log is more up-to-date if its last entry has a higher term, or if the terms are the same and the log is longer.

  Implication: A server can only win an election if its log contains all entries already committed by a majority of the cluster. This prevents a new leader with a stale log from being elected and overwriting committed history. This single rule is the linchpin of Raft's safety.

• Metaphor for a 5-Year-Old:
  When choosing a new Game Master, you wouldn't vote for a kid whose rulebook is missing "OFFICIAL" rules that everyone else already has. You only vote for candidates whose rulebook is at least as complete as your own. This ensures the new Game Master doesn't forget any important, already-decided rules.

• Python Code Snippet (The Safety Check):
  This is the most important piece of code for ensuring safety. It's the check inside the handle_vote_request RPC handler.

  class RaftNode:
      # ...
      def handle_vote_request(self, request):
          with self.lock:
              # ... (check term, etc.) ...
              
              vote_granted = False
              if (request.term == self.current_term and 
                  (self.voted_for is None or self.voted_for == request.candidate_id)):
                  
                  # --- THIS IS THE LEADER COMPLETENESS CHECK ---
                  my_last_log_term = self.log[-1].term if self.log else 0
                  my_last_log_index = len(self.log) - 1
  
                  candidate_is_up_to_date = (
                      request.last_log_term > my_last_log_term or
                      (request.last_log_term == my_last_log_term and 
                       request.last_log_index >= my_last_log_index)
                  )
                  # --- END OF CHECK ---
  
                  if candidate_is_up_to_date:
                      vote_granted = True
                      self.voted_for = request.candidate_id # Grant vote
                      self.last_heartbeat = time.time() # Reset our own timer
  
              return {"term": self.current_term, "vote_granted": vote_granted}
  

  This small block of logic is arguably the most crucial part of Raft's safety guarantee.

Conclusion

Congratulations! You have just worked through one of the most important algorithms in modern distributed systems. You've seen how a problem that is provably impossible to solve perfectly can be solved in practice with an understandable and robust algorithm.

Key Takeaways:

• Consensus is about achieving agreement, validity, and termination among distributed nodes, but it's hard.
• Raft simplifies consensus by decomposing it into Leader Election and Log Replication, centered around a strong leader.
• Leader Election uses randomized timeouts to handle leader failure and prevent split votes.
• Log Replication uses a commit rule based on majority replication to make progress, while the leader forces follower logs to be consistent with its own.
• Raft's safety is guaranteed by the Leader Completeness Property, which is enforced during voting to ensure no committed data is ever lost.

Next Lesson Preview

In this lesson, we saw how Raft uses a totally ordered log to bring all nodes to an identical state. In our previous lesson, we discussed Causal Consistency, which preserves a partial ordering of events that have a cause-and-effect relationship. How do systems track this causality without enforcing a strict total order? In our next lesson, we will dive deep into the implementation of Vector Clocks, the primary mechanism used to track causal dependencies in a distributed system.