Consensus: Paxos and Raft

Consensus is the problem of getting a group of nodes to agree on a value, or on a sequence of values, even when some nodes crash and messages are delayed, lost, or reordered. It is the basis of replicated state machines: if every replica applies the same commands in the same order, all replicas reach the same state. Consensus underlies leader election, distributed locks, configuration stores, and strongly consistent databases.

Problem statement

A consensus protocol must satisfy:

• Agreement. No two nodes decide different values.
• Validity. The decided value was proposed by some node.
• Termination. Every non-faulty node eventually decides. This is the liveness property.

The FLP impossibility result shows that no deterministic protocol can guarantee termination in a fully asynchronous system with even one crash failure. Practical protocols always keep safety (agreement and validity) and rely on timeouts, and therefore on partial synchrony, to make progress. Both Paxos and Raft never violate safety under crashes and network faults, but they can stall until a stable leader emerges.

Protocols in this article tolerate crash failures, not malicious (Byzantine) failures. A cluster of 2f + 1 nodes tolerates f crashes, because a majority of f + 1 must remain.

Even sizes add no fault tolerance over the next lower odd size: 4 nodes need a quorum of 3 and tolerate 1 failure, the same as 3 nodes.

Raft

Raft decomposes consensus into leader election, log replication, and safety. It was designed to be easier to understand than Paxos. At any time a node is in one of three roles: follower, candidate, or leader.

Terms

Time is divided into terms, numbered with consecutive integers. Each term begins with an election. A term has at most one leader. Every message carries the sender's term. A node that sees a higher term updates its own term and reverts to follower. A node rejects messages with a stale term.

Leader election

stateDiagram-v2
    [*] --> Follower
    Follower --> Candidate: election timeout
    Candidate --> Candidate: timeout, split vote
    Candidate --> Leader: majority votes
    Candidate --> Follower: sees leader or higher term
    Leader --> Follower: sees higher term

1. A follower that receives no heartbeat from a leader within its election timeout becomes a candidate. It increments its term, votes for itself, and sends RequestVote to all other nodes.
2. Each node grants at most one vote per term, on a first-come basis, and only if the candidate's log is at least as up to date as its own (see safety below).
3. A candidate that receives votes from a majority becomes leader and immediately sends heartbeats (empty AppendEntries messages) to establish authority.
4. If no candidate wins, for example because of a split vote, the term ends by timeout and a new election starts with a higher term.

Election timeouts are randomized within a range (the Raft paper suggests 150 to 300 ms), so that usually one node times out first and wins before others start. This makes split votes rare and resolves them quickly. The heartbeat interval must be much shorter than the election timeout, otherwise followers start elections while a healthy leader exists.

Each node must persist currentTerm, votedFor, and the log to disk before replying to a message. If a node forgot its vote after a restart, it could vote twice in one term and two leaders could be elected in that term.

A node that is partitioned away keeps timing out and incrementing its term. When it rejoins, its higher term forces the current leader to step down, which disrupts the cluster. The pre-vote extension, implemented for example in etcd, has a candidate first ask whether nodes would vote for it, without incrementing the term, so an isolated node cannot inflate terms.

Log replication

The leader accepts client commands, appends each as an entry in its log, and replicates it to followers with AppendEntries. Each entry holds the command and the term in which it was created.

sequenceDiagram
    participant C as Client
    participant L as Leader
    participant F1 as Follower 1
    participant F2 as Follower 2
    C->>L: command
    L->>L: append entry to own log
    par replicate
        L->>F1: AppendEntries
        L->>F2: AppendEntries
    end
    F1-->>L: success
    Note over L: majority stored, entry committed
    L->>L: apply to state machine
    L-->>C: result
    L->>F1: next AppendEntries carries commit index
    L->>F2: next AppendEntries carries commit index

• An entry is committed once the leader has stored it on a majority of nodes. Committed entries are durable and will be applied by every node.
• The leader tracks a commit index and includes it in later AppendEntries messages. Followers apply entries up to that index to their state machines.
• AppendEntries includes the index and term of the entry immediately preceding the new ones. A follower rejects the message if it lacks a matching entry. The leader then decrements its record of that follower's next index and retries until logs match, then overwrites any conflicting entries. This gives the Log Matching Property: if two logs contain an entry with the same index and term, the logs are identical up to that index.

Safety

Raft's key safety property is Leader Completeness: any entry committed in a term is present in the logs of leaders of all later terms. Two rules enforce it.

• Election restriction. A node grants its vote only if the candidate's log is at least as up to date. Up to date compares the term of the last entry first, and the log length if terms are equal. A committed entry exists on a majority, and any winning candidate needed votes from a majority, so at least one voter holds the entry and will refuse a candidate that lacks it.

  Example with 3 nodes: entry at index 5 (term 2) is stored on the leader S1 and on S2, so it is committed. S1 fails. S3 has a log ending at index 4 and starts an election. S2 refuses because its last entry (index 5, term 2) is newer than S3's last entry. S3 cannot obtain a majority (its own vote alone is 1 of 3), so it cannot become leader. S2 can win with S3's vote, and it holds the committed entry.

• Commit rule for old terms. A leader does not count replicas to commit entries from previous terms. It commits entries from its own term by majority replication, and this indirectly commits all earlier entries. A leader in a later term could otherwise see an old-term entry on a majority, treat it as committed, and then crash. A different node that lacks the entry could still win an election (its last-entry term can be newer than the old entry's) and overwrite it. Requiring a current-term entry to reach a majority first rules this out.

Membership changes

Changing cluster membership directly can produce two disjoint majorities. Raft prevents this either with joint consensus, in which the cluster passes through a transitional configuration requiring majorities of both the old and new sets, or with single-server changes, adding or removing one node at a time, which guarantees old and new majorities overlap.

Log compaction and reads

• Nodes take periodic snapshots of the state machine and discard the log up to the snapshot index. A leader sends its snapshot to followers that have fallen too far behind.
• Serving linearizable reads from the leader without logging them requires confirming leadership, either by a round of heartbeats to a majority (read index) or by a time-based leader lease, which depends on bounded clock drift.

Paxos

Paxos, by Leslie Lamport, is the earlier protocol. Basic Paxos decides a single value. Roles: proposers, acceptors, and learners. A node may take several roles.

Phase 1 (prepare). A proposer picks a unique, increasing proposal number n and sends prepare(n) to a majority of acceptors. An acceptor that has not promised a higher number replies with a promise not to accept proposals numbered lower than n, and includes the highest-numbered proposal it has already accepted, if any.

Phase 2 (accept). If the proposer receives promises from a majority, it sends accept(n, v). The value v is the value of the highest-numbered proposal reported in the promises, or the proposer's own value if none was reported. An acceptor accepts unless it has promised a higher number. When a majority accepts, the value is chosen.

Reporting previously accepted values in phase 1 forces later proposers to adopt an already-chosen value, which preserves agreement.

Multi-Paxos runs a sequence of instances to build a replicated log. A stable leader skips phase 1 for later log slots, so steady-state cost is one round trip to a majority per command, the same as Raft.

Use in real systems

• etcd and Consul use Raft. etcd stores Kubernetes cluster state and exposes a linearizable key-value API with watches and leases.
• ZooKeeper uses Zab, a leader-based atomic broadcast protocol. It provides a hierarchical namespace, ephemeral nodes, and watches for coordination.
• Google Spanner uses Paxos groups per data shard. CockroachDB and TiKV run one Raft group per data range (TiKV calls it a region).
• Kafka's KRaft mode uses a Raft-based quorum for cluster metadata.

Costs and limits

• Every write needs a majority round trip, so latency is bounded by network distance to the quorum. Spreading a cluster across regions raises commit latency.
• Throughput is limited by the leader. Scaling out requires partitioning data into many independent consensus groups.
• Cluster sizes are usually 3 or 5. More nodes tolerate more failures but slow every commit.
• Consensus should hold small, critical state such as metadata, locks, and leader identity. It is not a bulk data path.
• The minority side of a partition cannot make progress, which is the CP behavior described in CAP and PACELC.

See leader election for how leadership built on consensus is used by applications.

Interview questions

• Why does Raft need a majority? Any two majorities overlap in at least one node, so a later leader is always elected by a set that includes a node holding every committed entry.
• What happens if the leader fails after replicating an entry to some but not all followers? If the entry is on a majority, it is committed and any new leader will have it. If not, it may be lost or overwritten, and the client must retry.
• How does Raft avoid split votes? Randomized election timeouts make it likely that a single candidate starts first and wins before others become candidates.
• Why use 5 nodes instead of 4? 4 nodes need a quorum of 3 and tolerate 1 failure, the same as 3 nodes. 5 nodes tolerate 2 failures. Only the odd size adds fault tolerance.
• Can a Raft cluster serve reads from followers? Not with linearizability by default, since a follower may be behind. Followers can serve stale reads, or linearizable reads if they confirm their position with the leader.