Raft Made Simple

Raft was designed with one goal: understandability. Created in 2014 by Diego Ongaro and John Ousterhout at Stanford, it achieves the same safety as Paxos while being dramatically easier to understand.

> "Raft is a consensus algorithm that is designed to be easy to understand."

> — Raft Paper

The Core Idea

Raft decomposes consensus into three relatively independent subproblems:

Node States

Every node is in one of three states:

Terms: Logical Time

Raft divides time into terms - numbered with consecutive integers:

Term 1          Term 2          Term 3          Term 4
[Election|Normal Operation] [Elect] [Normal Operation] ...
   Leader A fails →              ↑
                           Leader B elected

Leader Election

Follower A (timeout) → Candidate A (term 2)
                            |
                            |-- RequestVote(term=2) --> Node B ✓
                            |-- RequestVote(term=2) --> Node C ✓
                            |-- RequestVote(term=2) --> Node D ✗ (down)
                            |
                       3/5 = majority!
                            |
                       Leader A (term 2)

Voting Rules

Randomized Timeouts

To prevent split votes (multiple candidates), election timeouts are randomized:

election_timeout = random.uniform(150, 300)  # milliseconds

Different timeouts mean one node usually times out first and wins.

Log Replication

Once elected, the leader handles all client requests:

Client: "SET x = 5"
           ↓
        Leader
           |
    AppendEntries(entry: "SET x = 5")
           |
     ↓     ↓     ↓
   [F1]  [F2]  [F3]
     |     |     |
    ACK   ACK   ACK
           ↓
    Majority responded!
    Entry is COMMITTED
           ↓
    Apply to state machine
           ↓
    Respond to client

Index:  1       2       3       4       5
Term:  [1]     [1]     [2]     [2]     [2]
Cmd:  [x=1]  [y=2]  [x=3]  [y=4]  [z=5]
       ↑                           ↑
    committed                 uncommitted

Commitment Rule

An entry is committed when:

• It's stored on a majority of nodes
• At least one entry from the leader's current term is also committed

Handling Inconsistencies

Followers might miss entries or have extra entries after failures:

Leader Log:   [1] [1] [2] [2] [3]
Follower A:   [1] [1] [2]          <- Missing entries
Follower B:   [1] [1] [2] [2] [2]  <- Wrong entry (old leader)

# AppendEntries includes:
# - prevLogIndex: index of entry before new ones
# - prevLogTerm: term of that entry

# Follower checks:
if log[prevLogIndex].term != prevLogTerm:
    reject()  # Log doesn't match
else:
    append(entries)  # Match! Add new entries

The leader decrements prevLogIndex until it finds where logs match, then sends all entries from there.

The Safety Guarantee

This is guaranteed because:

• Committed entries are on a majority of nodes
• A new leader must receive votes from a majority
• Therefore, the new leader must have received a vote from someone with the committed entry
• Voting rule: can't vote for someone with a less up-to-date log

Raft vs Paxos

Raft in Code

class RaftNode:
    def __init__(self, node_id, peers):
        self.id = node_id
        self.peers = peers
        self.state = "follower"
        self.current_term = 0
        self.voted_for = None
        self.log = []
        self.commit_index = 0

    def on_election_timeout(self):
        self.state = "candidate"
        self.current_term += 1
        self.voted_for = self.id
        votes = 1  # Vote for self

        for peer in self.peers:
            if peer.request_vote(self.current_term, self.id, self.last_log_info()):
                votes += 1

        if votes > len(self.peers) // 2:
            self.become_leader()

    def become_leader(self):
        self.state = "leader"
        # Send heartbeats immediately
        self.send_heartbeats()

    def append_entries(self, term, leader_id, prev_log_index, prev_log_term, entries):
        if term < self.current_term:
            return False

        self.reset_election_timeout()

        # Check log consistency
        if prev_log_index >= 0:
            if len(self.log) <= prev_log_index:
                return False
            if self.log[prev_log_index].term != prev_log_term:
                return False

        # Append new entries
        self.log = self.log[:prev_log_index + 1] + entries
        return True

Interactive Visualization

Key Takeaways

Next up: Real-World Consensus - How etcd, Consul, and ZooKeeper use these algorithms.