Raft is a consensus algorithm designed as an alternative to Paxos, prioritizing understandability without sacrificing correctness. It decomposes consensus into three subproblems: leader election, log replication, and safety. Used by etcd, CockroachDB, and Consul, Raft ensures that a cluster of nodes agrees on a sequence of values despite failures.
The Raft Model
A Raft cluster contains nodes in one of three states:
- Leader: Handles all client requests, replicates log entries
- Follower: Receives log entries from leader, responds to RPCs
- Candidate: Temporary state during leader election
Normal operation:
Client → Leader → Follower 1 (ack)
→ Follower 2 (ack)
→ Follower 3 (ack)
→ Commit (majority acked)Each node maintains:
type RaftNode struct {
currentTerm uint64 // Latest term node has seen
votedFor int // Candidate that received vote in current term
log []LogEntry // Log entries (index, term, command)
commitIndex uint64 // Highest log entry known to be committed
lastApplied uint64 // Highest log entry applied to state machine
// Volatile state on leaders
nextIndex map[int]uint64 // For each server, index of next log entry to send
matchIndex map[int]uint64 // For each server, highest log entry known to be replicated
}Leader Election
When a follower doesn't hear from a leader within the election timeout (150-300ms random), it becomes a candidate:
func (n *RaftNode) startElection() {
n.state = Candidate
n.currentTerm++
n.votedFor = n.id
votes := 1
for _, peer := range n.peers {
go func(p *RaftNode) {
reply := p.RequestVote(RequestVoteArgs{
Term: n.currentTerm,
CandidateId: n.id,
LastLogIndex: len(n.log) - 1,
LastLogTerm: n.log[len(n.log)-1].Term,
})
if reply.VoteGranted {
votes++
if votes > len(n.peers)/2 {
n.becomeLeader()
}
}
}(peer)
}
}The election safety guarantee: at most one leader can be elected per term. This is ensured because:
- Each node votes at most once per term
- A candidate needs a majority to win
- Terms are monotonically increasing
Log Replication
The leader appends new commands to its log, then replicates them to followers:
func (n *RaftNode) replicateLog() {
for _, peer := range n.peers {
go func(p *RaftNode) {
// Send entries starting from nextIndex[peer]
entries := n.log[n.nextIndex[peer]:]
reply := p.AppendEntries(AppendEntriesArgs{
Term: n.currentTerm,
LeaderId: n.id,
PrevLogIndex: n.nextIndex[peer] - 1,
PrevLogTerm: n.log[n.nextIndex[peer]-1].Term,
Entries: entries,
LeaderCommit: n.commitIndex,
})
if reply.Success {
n.nextIndex[peer] += len(entries)
n.matchIndex[peer] = n.nextIndex[peer] - 1
n.updateCommitIndex()
} else {
// Log inconsistency: decrement nextIndex and retry
n.nextIndex[peer]--
}
}(peer)
}
}The log matching property: if two logs contain an entry with the same index and term, then all entries with lower index are identical. This ensures logs stay consistent.
func (n *RaftNode) appendEntries(args AppendEntriesArgs, reply *AppendEntriesReply) {
if args.Term < n.currentTerm {
reply.Success = false
return
}
// Check if previous log entry matches
if args.PrevLogIndex > 0 {
if args.PrevLogIndex >= len(n.log) ||
n.log[args.PrevLogIndex].Term != args.PrevLogTerm {
reply.Success = false
return
}
}
// Append new entries (truncate conflicting ones)
for i, entry := range args.Entries {
idx := args.PrevLogIndex + 1 + i
if idx < len(n.log) {
if n.log[idx].Term != entry.Term {
n.log = n.log[:idx] // Truncate
} else {
continue // Already have this entry
}
}
n.log = append(n.log, entry)
}
// Update commit index
if args.LeaderCommit > n.commitIndex {
n.commitIndex = min(args.LeaderCommit, len(n.log)-1)
}
reply.Success = true
}tradeoff / Durability vs Latency
Raft uses majority commit by default. The leader commits after a majority of nodes acknowledge the entry. This provides durability (survives minority failure) with bounded latency (one round trip to majority).
Async replication commits immediately but risks data loss. Majority commit waits for majority acks, adding latency but ensuring durability. Commit with read waits for majority to apply, guaranteeing read-after-write consistency.
Commit Index and Safety
The commit index is the highest log entry known to be committed (replicated to a majority). The leader only commits entries from its current term — a critical safety property.
func (n *RaftNode) updateCommitIndex() {
// Find highest N such that:
// 1. N > commitIndex
// 2. A majority of matchIndex[i] >= N
// 3. log[N].term == currentTerm
for N := len(n.log) - 1; N > int(n.commitIndex); N-- {
if n.log[N].Term != n.currentTerm {
continue // Only commit entries from current term
}
count := 1 // Count self
for _, peer := range n.peers {
if n.matchIndex[peer] >= uint64(N) {
count++
}
}
if count > len(n.peers)/2 {
n.commitIndex = uint64(N)
break
}
}
}This restriction prevents a specific safety violation: a leader from a previous term might commit an entry that's actually stale. By only committing entries from its current term, the leader ensures the entry has been replicated under its authority.
Safety Proof
Raft's safety properties:
- Election safety: At most one leader per term
- Leader append-only: Leaders never delete or overwrite log entries
- Log matching: If two logs have an entry with same index/term, all preceding entries are identical
- 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
- State machine safety: If a node has applied a log entry at a given index, no other node will ever apply a different entry for that index
// Safety proof sketch for Leader Completeness
// Theorem: If an entry is committed in term T, it will be in the leader's log of any term > T
// Proof by contradiction:
// 1. Assume entry X is committed in term T but not in leader L's log of term T+1
// 2. L was elected in term T+1, so it must have received votes from majority
// 3. That majority includes at least one node that committed X in term T
// 4. That node would only vote for a candidate whose log is at least as up-to-date
// 5. Therefore L's log must contain X — contradictionLog Compaction
Logs grow indefinitely. Raft uses snapshotting to compact:
func (n *RaftNode) snapshot(lastIncludedIndex uint64, lastIncludedTerm uint64) {
// Save state machine state to persistent storage
state := n.stateMachine.Snapshot()
// Truncate log up to lastIncludedIndex
n.log = n.log[lastIncludedIndex:]
n.log[0].Term = lastIncludedTerm
// Save snapshot to disk
saveSnapshot(lastIncludedIndex, lastIncludedTerm, state)
}
func (n *RaftNode) installSnapshot(args InstallSnapshotArgs, reply *InstallSnapshotReply) {
// Leader sends snapshot to slow follower
// Follower replaces its log and state machine with the snapshot
n.log = []LogEntry{{Term: args.LastIncludedTerm}}
n.stateMachine.ApplySnapshot(args.Data)
n.commitIndex = args.LastIncludedIndex
n.lastApplied = args.LastIncludedIndex
}Synthesis
Raft decomposes consensus into leader election, log replication, and safety. The log is the core abstraction — a durable, ordered sequence of commands that all nodes agree on. Majority commit ensures durability, the log matching property ensures consistency, and the safety theorems guarantee that committed entries are never lost. Understanding Raft is understanding how distributed systems achieve agreement in the face of failures.