Raft Algorithm

Overview

Raft is a consensus algorithm that lets a cluster of machines agree on a single ordered log of commands—even when some machines crash or the network drops messages. That log drives a replicated state machine (RSM), which is the foundation behind many distributed databases and coordination systems.

At a high level:

• One node is the leader
• Clients write to the leader
• The leader replicates writes to followers
• Once a majority confirms, the entry is committed and applied in the same order everywhere

Why Consensus Matters in Distributed Databases

Distributed databases replicate data across nodes for availability and durability. But replication needs a rule for who decides the next write and in what order.

Without consensus:

• You risk split-brain writes (two primaries diverge)
• Clients see inconsistent ordering of updates
• Recovery becomes ambiguous (“which version is correct?”)

With Raft-style consensus:

• There is a single source of truth (the leader’s log)
• Writes are committed only after a majority ack
• Failover preserves safety by ensuring the new leader has the most up-to-date log

What Problem Raft Solves

Raft solves consensus for:

• Leader election
• Log replication
• Safety (no conflicting committed values)
• Membership changes (add/remove nodes safely)

Raft assumes:

• Crash/restart failures (not Byzantine)
• Unreliable networks (delay, drop, reorder messages)
• Eventually, timeouts allow progress (partial synchrony)

Raft in One Picture: Roles and Terms

• Leader: accepts client requests, replicates log entries
• Follower: passive; responds to leader RPCs
• Candidate: runs for leader during elections
• Term: a logical epoch number; increases with elections

Raft uses two core RPCs:

• RequestVote (election)
• AppendEntries (log replication + heartbeats)

The Raft Log: Replication and Ordering

Each node maintains:

• log[]: ordered entries (term, command)
• commitIndex: highest log index known committed
• lastApplied: highest log index applied to state machine

A committed entry is one that:

• the leader has replicated to a majority
• and is in the leader’s current term (important nuance for safety)

Once committed, the entry is applied to the state machine in order.

Leader Election

When followers stop hearing heartbeats, they time out and become candidates:

1. Candidate increments term
2. Votes for itself
3. Sends RequestVote to others
4. Wins if it gets a majority

Key nuance: A follower only votes for a candidate whose log is at least as up-to-date as its own (prevents electing stale leaders).

Log Replication: AppendEntries

The leader sends AppendEntries(prevLogIndex, prevLogTerm, entries[], leaderCommit).

Followers accept if:

• they have prevLogIndex and its term matches prevLogTerm

Otherwise:

• they reject, and the leader backs up until it finds the last matching prefix

This is how Raft enforces:

• log matching property: if two logs contain the same entry at an index and term, then all preceding entries are identical.

Safety Properties (Why Raft Doesn’t Corrupt State)

Raft’s core safety goals:

• Election safety: at most one leader per term
• Leader append-only: leaders never overwrite their own log entries
• Log matching: identical (index, term) implies identical prefix
• Leader completeness: committed entries are present in future leaders

The “leader completeness” property is why log up-to-date checks during RequestVote matter.

Reads: Linearizable vs. Stale

Distributed DBs often need two classes of reads:

• Linearizable reads: reflect the latest committed write
• Stale/lease reads: may lag slightly but faster

Common Raft-backed patterns:

• Read from leader after confirming it still has quorum (heartbeat/ReadIndex)
• Lease reads: leader assumes leadership for a bounded time (requires clock assumptions)
• Follower reads: often stale unless you track commitIndex or use read barriers

Membership Changes and Reconfiguration

Changing membership is dangerous if two different majorities can form.

Raft uses joint consensus:

1. Cluster enters a joint config (old ∪ new)
2. Commit entries requiring majorities of both old and new
3. Transition to new config once safe

This prevents split brain during reconfiguration.

Performance Nuances

Key practical trade-offs:

• Commit latency: at least one RTT to a majority
• Batching: amortizes overhead but increases tail latency under light load
• Disk fsync: needed for durability; can dominate latency
• Snapshotting: avoids unbounded log growth but adds complexity

Raft vs Paxos (Practical Differences)

Raft and Paxos solve similar problems, but Raft is designed to be easier to understand and implement.

Common Pitfalls (and Fixes)

Where Raft Is Used in Practice

Raft is widely used as the replication/consensus core in:

• etcd (Kubernetes coordination / config store)
• Consul (service discovery and KV)
• Many distributed databases and storage engines (especially metadata/control planes)

In distributed DB design, Raft is commonly used to replicate:

• metadata (schema, leader leases, placement rules)
• shard ownership / partition maps
• sometimes user data (especially for strongly consistent systems)

Conclusion

Raft provides a practical, leader-driven consensus protocol that is especially well-suited for replicated logs and state machines—exactly what distributed databases need to coordinate writes, guarantee ordering, and survive failures. The key is understanding quorum-based commits, leader elections, log matching, and the real-world trade-offs around read consistency, batching, and snapshotting.

Key Takeaways

• Raft is a consensus algorithm for replicating an ordered log across unreliable nodes.
• It’s foundational in distributed databases for safe replication, failover, and metadata coordination.
• Majority quorum commits provide safety; elections and terms prevent stale leaders.
• Linearizable reads typically require leader/quorum confirmation; stale reads can be faster but weaker.
• Snapshotting is essential to prevent unbounded log growth and improve recovery time.