system-design · intermediate

Consensus Algorithms — Agreeing Despite Failures

The Central Question

Consider a critical distributed metadata cluster running on the TxLab platform (txlab.com) processing 100,000,000 queries per day:

• The cluster consists of 5 database nodes (Node A, Node B, Node C, Node D, Node E) maintaining distributed lock ownership and service discovery state.
• Suddenly, Node A suffers a hard hardware crash and goes offline.
• Simultaneously, a network partition isolates Node E from the rest of the cluster.

This fundamental challenge is solved by Distributed Consensus Algorithms.

A Consensus Algorithm is a protocol that allows a set of independent network nodes to agree on a single data value, execution order, or state transition log—even when some nodes fail, drop packets, or exhibit network latency.

This lesson answers one central question: How does the Raft consensus algorithm decompose distributed agreement into Leader Election, Log Replication, and Safety invariants, and how do systems leverage Quorum Majority ($Q = \lfloor \frac{N}{2} \rfloor + 1$) and Term Leases to maintain linearizable state safety in production?

Replicated State Machines (RSM)

Consensus algorithms are typically deployed to build Replicated State Machines (RSM):

flowchart TD
  Client[Application Client] -->|1. Submit Command| Leader[Leader Node]
  
  subgraph Replicated State Machine Cluster
    Leader -->|2. Write Command to Log| LeaderLog[Leader Consensus Log]
    LeaderLog -->|3. AppendEntries RPC| FollowerLog1[Follower 1 Log]
    LeaderLog -->|3. AppendEntries RPC| FollowerLog2[Follower 2 Log]
    
    LeaderLog -->|4. Apply to State Machine| SM1[Leader State Machine]
    FollowerLog1 -->|4. Apply to State Machine| SM2[Follower 1 State Machine]
    FollowerLog2 -->|4. Apply to State Machine| SM3[Follower 2 State Machine]
  end

Figure 1: Replicated State Machine architecture executing identical ordered logs across nodes.

The Core RSM Invariant

If two independent state machines start in the identical initial state and execute the identical sequence of deterministic commands from an ordered log, they will compute identical output states.

The Raft Consensus Protocol: 3 Core Sub-Problems

While Paxos was historically the dominant consensus protocol, its complexity made implementation notoriously difficult. In 2014, Diego Ongaro and John Ousterhout introduced Raft, which decomposes consensus into three clear sub-problems:

flowchart TD
  Raft[Raft Consensus Decomposition] --> Election[1. Leader Election]
  Raft --> Replication[2. Log Replication]
  Raft --> Safety[3. Safety Invariants]
  
  Election --> ElDesc["Select 1 Leader node per Term using Randomized Heartbeat Timeouts."]
  Replication --> RepDesc["Leader accepts writes from clients, appends to log, and replicates to Followers."]
  Safety --> SafeDesc["Enforce Election Safety, Leader-Only Writes, and Log Matching Properties."]

Figure 2: Taxonomy of Raft consensus sub-problems.

1. Node Roles in Raft

• Leader: Handles all client requests, manages log replication, and sends periodic heartbeats (AppendEntries).
• Follower: Passive state; responds to RPCs from Leaders and Candidates. If a Follower receives no heartbeats within its election timeout, it converts to a Candidate.
• Candidate: Active state during elections; requests votes (RequestVote) from peer nodes to become Leader for a new Term.

Quorum Mathematics ($Q = \lfloor \frac{N}{2} \rfloor + 1$)

Raft requires a Quorum Majority of healthy nodes to elect a leader or commit a log entry:

$$Q = \left\lfloor \frac{N}{2} \right\rfloor + 1$$

For a cluster of $N = 5$ nodes, the quorum majority is:

$$Q = \left\lfloor \frac{5}{2} \right\rfloor + 1 = 2 + 1 = 3 \text{ nodes}$$

Cluster Fault Tolerance Table

[!IMPORTANT] Why Production Clusters Use Odd Node Counts: A 4-node cluster requires $Q = 3$ nodes, tolerating only $F = 1$ failure ($4 - 3 = 1$). A 5-node cluster also requires $Q = 3$ nodes, but tolerates $F = 2$ failures. Adding a 4th node increases network overhead without improving fault tolerance! Always deploy consensus clusters with odd node counts (3, 5, or 7).

Raft Invariants and Log Safety

Raft guarantees correctness through five strict safety properties:

1. Election Safety: At most one leader can be elected per term.
2. Leader Append-Only: A leader never overwrites or truncates its own log entries; it only appends new entries.
3. Log Matching Property: If two logs contain an entry with the same index and term, then the logs are identical in all entries up through the given index.
4. Leader Completeness: If a log entry is committed in a given term, that entry will be present in the logs of the leaders for all higher-numbered terms.
5. State Machine Safety: If a server has applied a log entry at a given index to its state machine, no other server will ever apply a different log entry for that index.

Pre-Vote Phase (Preventing Disrupted Leaders)

• A Candidate node sends a speculative PreVote RPC to check if a majority quorum would grant a vote before incrementing its term.
• If the majority quorum reports that a healthy leader is active, the Candidate drops its PreVote without incrementing the term, preserving cluster stability.

Joint Consensus Configuration Membership Changes

• The cluster transitions through an intermediate joint configuration $C_{\text{old,new}}$ requiring separate majority quorums from BOTH $C_{\text{old}}$ and $C_{\text{new}}$ before committing to the final $C_{\text{new}}$ state.

Leader Leases for Zero-Latency Reads

Complete Worked Example: Production Go Raft Leader Election & Log Engine

Let's inspect a complete Go implementation of a Raft Leader Election & Log Engine for the TxLab platform (txlab.com).

package main
import (
	"context"
	"fmt"
	"math/rand"
	"sync"
	"time"
)
type NodeRole int
const (
	RoleFollower NodeRole = iota
	RoleCandidate
	RoleLeader
)
type RaftNode struct {
	mu          sync.Mutex
	id          int
	currentTerm int64
	votedFor    int
	role        NodeRole
	peers       []*RaftNode
	heartbeat   chan bool
	log         []string
}
func NewRaftNode(id int) *RaftNode {
	return &RaftNode{
		id:          id,
		currentTerm: 0,
		votedFor:    -1,
		role:        RoleFollower,
		heartbeat:   make(chan bool, 10),
		log:         make([]string, 0),
	}
}
func (n *RaftNode) Run(ctx context.Context) {
	for {
		select {
		case <-ctx.Done():
			return
		default:
			n.mu.Lock()
			role := n.role
			n.mu.Unlock()
switch role {
			case RoleFollower:
				n.runFollower(ctx)
			case RoleCandidate:
				n.runCandidate(ctx)
			case RoleLeader:
				n.runLeader(ctx)
			}
		}
	}
}
func (n RaftNode) runFollower(ctx context.Context) {
	// Randomized Election Timeout (150ms - 300ms)
	timeout := time.Duration(150+rand.Intn(150))  time.Millisecond
	timer := time.NewTimer(timeout)
	defer timer.Stop()
select {
	case <-n.heartbeat:
		// Reset timeout on heartbeat from Leader
	case <-timer.C:
		n.mu.Lock()
		n.role = RoleCandidate
		fmt.Printf("[ELECTION TIMEOUT] Node %d converted to CANDIDATE for Term %d\n", n.id, n.currentTerm+1)
		n.mu.Unlock()
	case <-ctx.Done():
		return
	}
}
func (n *RaftNode) runCandidate(ctx context.Context) {
	n.mu.Lock()
	n.currentTerm++
	n.votedFor = n.id
	term := n.currentTerm
	n.mu.Unlock()
votes := 1
	var wg sync.WaitGroup
	var voteMu sync.Mutex
for _, peer := range n.peers {
		wg.Add(1)
		go func(p *RaftNode) {
			defer wg.Done()
			if p.RequestVote(n.id, term) {
				voteMu.Lock()
				votes++
				voteMu.Unlock()
			}
		}(peer)
	}
wg.Wait()
n.mu.Lock()
	if votes >= (len(n.peers)+1)/2+1 {
		n.role = RoleLeader
		fmt.Printf("[ELECTION WON] Node %d elected LEADER for Term %d with %d votes!\n", n.id, term, votes)
	} else {
		n.role = RoleFollower
	}
	n.mu.Unlock()
}
func (n RaftNode) runLeader(ctx context.Context) {
	fmt.Printf("[LEADER ACTIVE] Node %d sending heartbeats for Term %d...\n", n.id, n.currentTerm)
	for _, peer := range n.peers {
		peer.heartbeat <- true
	}
	time.Sleep(50  time.Millisecond)
}
func (n *RaftNode) RequestVote(candidateID int, term int64) bool {
	n.mu.Lock()
	defer n.mu.Unlock()
if term > n.currentTerm && (n.votedFor == -1 || n.votedFor == candidateID) {
		n.currentTerm = term
		n.votedFor = candidateID
		return true
	}
	return false
}

Failure Modes and Engineering Mitigations

What You Should Remember

1. Raft decomposes consensus into 3 sub-problems: Leader Election, Log Replication, and Safety Invariants.
2. Quorum Majority requires $Q = \lfloor \frac{N}{2} \rfloor + 1$: A 5-node cluster requires 3 node acknowledgments to elect leaders or commit logs.
3. Deploy odd node counts: 3, 5, or 7 node clusters provide optimal fault tolerance without adding unnecessary network overhead.
4. Randomize election timeouts: Stagger candidate election timers (150ms-300ms) to prevent split-vote election loops.
5. Use Snapshot Compaction for log pruning: Compact committed Raft log entries into state machine snapshots to bound memory and startup recovery time.

Glossary of Terms

Practice Scenario and Self-Assessment

Architecture Scenario

• A 5-node Raft cluster (Node 1 to Node 5) manages distributed lease locks.
• Node 1 (Leader) experiences a $500\text{ms}$ stop-the-world JVM Garbage Collection pause.

1. Detail the step-by-step Raft election process triggered by Node 2, Node 3, Node 4, and Node 5 during Node 1's GC pause.
2. Explain what happens when Node 1 completes its GC pause and attempts to issue writes under its old Term.

Interactive Self-Assessment

A 4-node cluster requires Q=3 nodes (tolerating F=1 failure), whereas a 5-node cluster also requires Q=3 nodes (tolerating F=2 failures). Adding an even node adds network overhead without increasing fault tolerance.

Even node counts automatically format persistent NVMe SSD disk drives on database servers.

Even node counts revoke client HTTPS TLS encryption certificates on edge load balancers.

Even node counts cut physical CPU hardware clock speeds in half across all consensus nodes.

It prevents Split Vote election loops by ensuring one follower times out first and collects majority votes before peers time out.

Randomized timeouts convert relational database primary key indexes into un-indexed CSV files.

Randomized timeouts replace public DNS nameservers with local hosts file entries.

Randomized timeouts reboot operating system hypervisors across all cluster nodes.

What to Learn Next

• Active-Active Conflict Resolution — CRDTs and Vector Clocks: Master multi-region write conflict resolution.
• Strong vs Eventual Consistency: Explore linearizability vs eventual consistency models.
• CAP Theorem & PACELC — Consistency vs Availability: Revisit network partition trade-offs.

Track: Distributed Systems

By Shubham Jain

All articles · Study paths

Shubham Jain · Learning Lab