Distributed Consensus (Raft)

Metadata

1. Overview

What problem does it solve?

In a distributed database with 5 replica nodes, if a client sends SET x = 10 to Node 1, and simultaneously sends SET x = 20 to Node 2, what is the value of x? Without a strict mathematical protocol, the 5 nodes will disagree. Node 1 says 10, Node 2 says 20. If they disagree, the database is corrupted.

Distributed Consensus is the algorithm that allows a group of machines to agree on a single, unified state, even if some of the machines crash or the network between them drops packets. It is the mathematical foundation of all Strongly Consistent (CP) distributed systems.

What breaks without it?

• Split-Brain: Without consensus, a network partition results in two halves of the cluster operating independently, permanently diverging their data.
• Lost Writes: A node accepts a write, acknowledges the client, and crashes before telling anyone else. The data is lost.

2. Motivation

For decades, the only known algorithm to achieve Distributed Consensus was Paxos (invented by Leslie Lamport in 1989). Paxos is mathematically brilliant but notoriously difficult to understand, implement, and debug. Very few engineers in the world could write a bug-free Paxos implementation.

In 2013, researchers at Stanford published a new consensus algorithm called Raft. Its explicit goal was "Understandability." It stripped away the mathematical complexity of Paxos by breaking consensus down into three distinct, easier-to-understand sub-problems: Leader Election, Log Replication, and Safety. Raft revolutionized distributed systems, becoming the default algorithm for modern infrastructure.

3. Real-World Usage

4. Prerequisites

5. Visual Explanation

The Raft Cluster

Raft uses a strict Strong Leader model. Clients only talk to the Leader. Followers only passively replicate the Leader's log.

%%{init: {'theme': 'base', 'themeVariables': { 'primaryColor': '#ffcc00', 'edgeLabelBackground':'#ffffff'}}}%%
graph TD
    classDef client fill:#f9f9f9,stroke:#333,stroke-width:2px;
    classDef leader fill:#d4edda,stroke:#28a745,stroke-width:3px;
    classDef follower fill:#cce5ff,stroke:#007bff,stroke-width:2px;

    C((Client)):::client --> |"1. SET x=5"| L[Leader Node]:::leader
    
    L -.-> |"2. AppendEntry (Uncommitted)"| F1[Follower 1]:::follower
    L -.-> |"2. AppendEntry (Uncommitted)"| F2[Follower 2]:::follower
    
    F1 -.-> |"3. ACK"| L
    F2 -.-> |"3. ACK"| L
    
    L --> |"4. Majority reached.<br/>Commit locally."| L
    
    L --> |"5. OK"| C
    
    L -.-> |"6. Commit Message"| F1
    L -.-> |"6. Commit Message"| F2

6. Internal Working

Raft decomposes consensus into three parts:

1. Leader Election

(See Block 022 for the conceptual basics, but Raft is strict about the rules).

• All nodes start as Followers.
• Every node has a randomized Election Timeout (e.g., 150ms to 300ms).
• If a Follower doesn't hear a heartbeat from the Leader before its timeout expires, it becomes a Candidate, increments its Term (epoch), and requests votes.
• Rule: A node can only vote for a Candidate if the Candidate's log is at least as up-to-date as its own. This prevents a node with stale data from becoming the Leader and deleting good data.

2. Log Replication

• The Leader receives SET x=5 from the client.
• It appends the command to its local WAL as an "Uncommitted" entry.
• It sends AppendEntries RPCs to all followers.
• The Quorum: The Leader waits until a majority of nodes (e.g., 3 out of 5) reply with an ACK.
• Once a majority ACKs, the Leader "Commits" the entry (applies it to its state machine) and returns success to the client.
• In the next heartbeat, it tells the Followers to commit it too.

3. Safety (Handling Partitions)

If the network splits, you might end up with a 2-node partition and a 3-node partition.

• The 3-node partition will elect a new leader. It has a majority, so it can accept new writes.
• The old leader in the 2-node partition will try to accept writes, but it can never get a majority of ACKs. It cannot commit anything.
• When the network heals, the old leader realizes its Term is outdated. It immediately steps down, becomes a Follower, and overwrites its uncommitted logs with the new leader's committed logs. Split-brain averted.

7. Implementation

Why Go? Raft relies heavily on concurrent RPCs, timeouts, and state machines. Go's goroutines and channels make modeling the Raft Election and Heartbeat loops incredibly elegant. HashiCorp's official Raft library is written in Go.

/*
023 - Distributed Consensus (Raft)
A conceptual simulation of Raft Leader Election and the Randomized Timeout mechanism.
*/
package main

import (
	"fmt"
	"math/rand"
	"sync"
	"time"
)

type State string

const (
	Follower  State = "Follower"
	Candidate State = "Candidate"
	Leader    State = "Leader"
)

type RaftNode struct {
	id          string
	state       State
	currentTerm int
	
	// Channels for inter-node communication
	heartbeatChan chan bool
	requestVoteChan chan bool
	
	mu sync.Mutex
}

func NewNode(id string) *RaftNode {
	return &RaftNode{
		id:            id,
		state:         Follower,
		currentTerm:   0,
		heartbeatChan: make(chan bool, 1),
	}
}

// ── The Core Raft State Machine Loop ──

func (n *RaftNode) Run() {
	for {
		switch n.state {
		case Follower:
			n.runFollower()
		case Candidate:
			n.runCandidate()
		case Leader:
			n.runLeader()
		}
	}
}

func (n *RaftNode) runFollower() {
	// Raft explicitly requires RANDOMIZED timeouts (e.g. 150-300ms)
	// to prevent split votes where all nodes become candidates at exactly the same time.
	timeout := time.Duration(rand.Intn(150)+150) * time.Millisecond
	timer := time.NewTimer(timeout)

	select {
	case <-n.heartbeatChan:
		// Received heartbeat from leader. Reset timer.
		// fmt.Printf("[%s] Received Heartbeat. Remaining Follower.\n", n.id)
		return
	case <-timer.C:
		// Timeout expired! No leader is present.
		fmt.Printf("⚠️ [%s] Election Timeout! Becoming Candidate for Term %d.\n", n.id, n.currentTerm+1)
		n.mu.Lock()
		n.state = Candidate
		n.mu.Unlock()
	}
}

func (n *RaftNode) runCandidate() {
	n.mu.Lock()
	n.currentTerm++
	n.mu.Unlock()
	
	// In a real system, the Candidate would send RequestVote RPCs to all other nodes.
	// We simulate winning the election immediately for this demonstration.
	fmt.Printf("🗳️ [%s] Requesting votes for Term %d... Won Election!\n", n.id, n.currentTerm)
	
	n.mu.Lock()
	n.state = Leader
	n.mu.Unlock()
}

func (n *RaftNode) runLeader() {
	fmt.Printf("👑 [%s] I am the Leader for Term %d! Sending Heartbeats...\n", n.id, n.currentTerm)
	
	ticker := time.NewTicker(50 * time.Millisecond) // Send heartbeats very fast
	
	// Simulate being leader for a short time before a "network failure" crashes us
	timeAlive := time.After(400 * time.Millisecond)

	for {
		select {
		case <-ticker.C:
			// fmt.Printf("[%s] Sending AppendEntries (Heartbeat)\n", n.id)
			// In reality, this pushes to the heartbeatChan of all followers
		case <-timeAlive:
			fmt.Printf("💥 [%s] LEADER CRASHED!\n", n.id)
			// We exit the loop, effectively dying.
			// The followers' timers will now expire!
			time.Sleep(10 * time.Second) // stay dead
		}
	}
}


// ── Test Harness ──

func main() {
	rand.Seed(time.Now().UnixNano())

	nodeA := NewNode("Node-A")
	nodeB := NewNode("Node-B")
	nodeC := NewNode("Node-C")

	// Start the cluster
	go nodeA.Run()
	go nodeB.Run()
	go nodeC.Run()

	// Simulate Node A receiving heartbeats from an imaginary leader for a bit
	for i := 0; i < 3; i++ {
		time.Sleep(100 * time.Millisecond)
		nodeA.heartbeatChan <- true
		nodeB.heartbeatChan <- true
		nodeC.heartbeatChan <- true
	}

	// Stop sending heartbeats! Let the Raft election take over.
	fmt.Println("\n--- Previous Leader Died. Awaiting new election... ---")

	time.Sleep(2 * time.Second)
}

Sample Output

--- Previous Leader Died. Awaiting new election... ---
⚠️ [Node-B] Election Timeout! Becoming Candidate for Term 1.
🗳️ [Node-B] Requesting votes for Term 1... Won Election!
👑 [Node-B] I am the Leader for Term 1! Sending Heartbeats...
💥 [Node-B] LEADER CRASHED!
⚠️ [Node-C] Election Timeout! Becoming Candidate for Term 1.
🗳️ [Node-C] Requesting votes for Term 1... Won Election!
👑 [Node-C] I am the Leader for Term 1! Sending Heartbeats...

Notice the randomized timeouts at work. Node-B's timer randomly expired a few milliseconds before Node-C's, so Node-B initiated the election and won. When B crashed, C took over.

8. Complexity

9. Trade-offs

10. Production Evolution

11. Common Bugs

12. Interview Questions

1. Why must a Raft cluster have an odd number of nodes (e.g., 3, 5)? Hint: To prevent ties during elections and to ensure a clear majority during network partitions. If you have 4 nodes and a partition splits them 2 and 2, neither side has a majority (requires 3), so the whole system halts.

2. How does Raft ensure that a new Leader doesn't delete committed data? Hint: The Election Restriction rule. A follower will deny a vote to a Candidate if the Candidate's log is older/shorter than the follower's log. This guarantees the node with the most up-to-date data wins the election.

3. What is the difference between Paxos and Raft? Hint: They solve the exact same problem with the exact same performance characteristics. Raft was designed specifically to be understandable by decomposing the problem into Leader Election and Log Replication.

13. Used By (Downstream Blocks)

• 021 CAP Theorem — Raft is the standard algorithm for building systems that choose Consistency and Partition Tolerance (CP).

14. Used In (Case Studies)

15. Related Blocks

16. Try It Yourself

Exercise 1: Implement the Voting Logic

Add a RequestVote method. When a Candidate starts an election, it should send a request to the other nodes. A node should only grant its vote if it hasn't already voted in this currentTerm. The Candidate should only become Leader if votes >= (total_nodes / 2) + 1.

Exercise 2: Simulating Quorum

Create a ReplicateLog(data string) function on the Leader. It should send the data to all Followers. The function should block until at least Majority followers return true. If successful, print "Log Committed".

Website Metadata