Consensus Algorithms: Raft vs Paxos

Consensus is the problem of getting a group of nodes to agree on a single value. It’s fundamental to building reliable distributed systems.

Why Consensus Matters

Leader election: Who coordinates?
State machine replication: Keeping replicas in sync
Configuration management: Cluster membership changes
Distributed locks: Coordinating access to resources

Paxos: The Classic Algorithm

Paxos was introduced by Leslie Lamport in 1998. It’s notoriously difficult to understand and implement correctly.

Basic Paxos (Single-Decree)

Prepare Phase: Proposer sends prepare(n) to majority
Promise Phase: Acceptors promise not to accept proposals < n
Accept Phase: Proposer sends accept(n, value) to majority
Learn Phase: Learners learn the accepted value

Multi-Paxos

Optimizes for repeated consensus by electing a stable leader.

// Simplified Paxos proposer
type Proposer struct {
    proposalNumber int
    acceptors      []Acceptor
}

func (p *Proposer) Propose(value interface{}) error {
    // Phase 1: Prepare
    n := p.generateProposalNumber()
    promises := p.sendPrepare(n)
    
    if len(promises) < p.quorumSize() {
        return ErrNoQuorum
    }
    
    // Phase 2: Accept
    chosenValue := p.chooseValue(promises, value)
    accepted := p.sendAccept(n, chosenValue)
    
    if len(accepted) < p.quorumSize() {
        return ErrNoQuorum
    }
    
    return nil
}

Raft: Understandable Consensus

Raft was designed by Diego Ongaro and John Ousterhout in 2014 with the explicit goal of being understandable.

Key Differences from Paxos

Aspect	Paxos	Raft
Leader	Implicit, multiple possible	Explicit, single leader
Log Structure	Single-decree, complex composition	Continuous log entries
Membership Changes	Complex	Joint consensus (simple)
Readability	Low	High

Raft States

Follower → Candidate → Leader
    ↑_______________|

Follower: Passive, responds to RPCs
Candidate: Runs for leader, requests votes
Leader: Handles all client requests, replicates log

Raft Guarantees

Election Safety: At most one leader per term
Leader Completeness: Leader has all committed entries
State Machine Safety: Identical logs → identical state

Leader Election

// Raft election timeout (randomized 150-300ms)
func (rf *Raft) startElection() {
    rf.currentTerm++
    rf.votedFor = rf.me
    rf.state = Candidate
    
    votes := 1 // Vote for self
    for i := range rf.peers {
        if i == rf.me { continue }
        
        go func(server int) {
            args := RequestVoteArgs{
                Term:         rf.currentTerm,
                CandidateId:  rf.me,
                LastLogIndex: rf.getLastLogIndex(),
                LastLogTerm:  rf.getLastLogTerm(),
            }
            reply := RequestVoteReply{}
            if rf.sendRequestVote(server, &args, &reply) {
                rf.mu.Lock()
                if reply.VoteGranted {
                    votes++
                    if votes > len(rf.peers)/2 {
                        rf.becomeLeader()
                    }
                } else if reply.Term > rf.currentTerm {
                    rf.becomeFollower(reply.Term)
                }
                rf.mu.Unlock()
            }
        }(i)
    }
}

When to Use Which?

Use Raft When:

Building a new system (easier to implement correctly)
Team needs to understand and debug the consensus logic
Need clear membership change semantics
Using etcd, Consul, or TiKV

Use Paxos When:

Working with existing Paxos-based systems (Chubby, Spanner)
Need highly optimized, battle-tested implementations
Academic/research context

Production Systems Using Raft

etcd: Kubernetes configuration store
Consul: Service mesh configuration
TiKV: Distributed transactional KV store
CockroachDB: Distributed SQL (Raft variant)
Redis Cluster: Redis 7+ uses Raft for replication