Raft

Raft (Ongaro and Ousterhout, 2014) solves the same problem as Paxos, keeping a cluster agreed on a replicated log, with one explicit goal: be understandable. It breaks consensus into three sub-problems you can hold in your head.

1. Leader election

Every node is a follower, a candidate or the leader. Time is divided into numbered terms.

• The leader sends regular heartbeats. While they keep coming, followers stay followers.
• If a follower hears nothing for its election timeout, it becomes a candidate, increments the term and asks for votes.
• A candidate with votes from a majority becomes leader for that term. Each node votes once per term, so there’s at most one leader per term.
• Timeouts are randomised (say 150–300 ms), so nodes rarely stand at the same moment, and split votes resolve quickly.

2. Log replication

Clients send commands to the leader. The leader appends each to its log and sends it to followers. Once a majority has stored an entry, it’s committed: the leader applies it to its state machine and tells followers to do the same. A minority of slow or crashed nodes doesn’t block progress.

3. Safety

• A candidate can only win if its log is at least as up to date as a majority’s, so a new leader always has every committed entry.
• If two logs contain an entry with the same index and term, they’re identical up to that point.

Together these mean committed entries are never lost or reordered, even through leader changes.

Living with FLP

Raft relies on timeouts, so it assumes partial synchrony. That’s how it sidesteps FLP Impossibility: under bad network conditions it may struggle to elect a leader (liveness suffers), but it never commits conflicting entries (safety holds).

Where it runs

etcd, the store behind Kubernetes’ control plane, uses Raft; so do Consul and several distributed SQL databases. A five-node cluster tolerates two failures; lose three and it stops accepting writes rather than risk divergence. That’s the CP choice in the CAP Theorem.

Why I like it

Raft is the best example I know of designing for comprehension as a feature. The paper argues that an algorithm people can understand will be implemented correctly more often, and that idea applies well beyond consensus: to APIs, codebases and documentation. The full problem statement is in The Consensus Problem.