Raft: what the understandable consensus algorithm paper actually says

Reading Ongaro & Ousterhout (USENIX ATC 2014) after a Kubernetes control plane went down for six minutes.

The incident timeline was clean: etcd leader election storm, kube-apiserver losing quorum, deployments frozen. The fix was a leader election timeout tuning change in a Helm chart. What I didn't understand was why it happened — and why it happened again three weeks later when a different node got a GC pause.

The Raft paper — "In Search of an Understandable Consensus Algorithm", Ongaro and Ousterhout, USENIX ATC 2014 — is not primarily a performance paper. It's a pedagogy paper. The authors ran user studies and found that Paxos was so hard to understand that engineers couldn't implement it correctly from the original description. Raft's goal was understandability, explicitly, as a design criterion. This sounds soft until you realize that almost every distributed system running consensus at scale — etcd, CockroachDB, TiKV, Consul, YugabyteDB — uses Raft, and the failure modes in every one of those systems trace back to the specific decisions the paper made.

The problem the paper is actually solving

Paxos was the de facto consensus algorithm for about two decades. It works. It's also notoriously hard to reason about because it doesn't cleanly separate leader election from log replication from membership changes — they're interleaved in a single protocol that requires understanding all phases simultaneously to verify correctness.

Lamport's original "single-decree" Paxos — reaching consensus on one value — is actually manageable. "Multi-Paxos" — extending it to a replicated log — is where things fall apart. The original papers don't fully specify it. Implementations diverge. Teams building distributed databases or key-value stores each ended up implementing subtly different variants that were difficult to compare or reason about jointly.

Raft's contribution is decomposition. The paper explicitly breaks consensus into three independent subproblems:

1. Leader election: at any time, exactly one server is the designated leader
2. Log replication: the leader accepts log entries and replicates them to followers
3. Safety: if any server has applied a log entry at a given index, no other server can apply a different entry at that index

This separation is the paper's actual contribution — not any individual algorithm, but the decision to treat these as separable concerns. You can understand each piece in isolation and verify each piece independently.

Leader election: terms and randomized timeouts

Raft uses a monotonically increasing counter called a term to detect stale leaders. Every message carries the sender's current term. If a server receives a message with a higher term than its own, it immediately updates its term and reverts to follower state. Stale leaders — partitioned nodes that lost the election — are invalidated this way when they reconnect.

The election mechanism itself is deliberately simple. Each server has an election timeout — a duration without receiving a heartbeat from the leader. When the timeout fires, the server starts a new election: it increments its term, votes for itself, and sends RequestVote RPCs to all other servers. A candidate becomes leader when it receives votes from a majority.

The randomization is in the timeout values. Each server picks its election timeout randomly from a window (the paper suggests 150–300ms). This makes it unlikely that two servers time out simultaneously and become candidates at the same time, which would split votes and require another election. One server typically times out first, wins the election, and starts sending heartbeats before others even begin.

The vote granting rule is where safety lives. A server only grants a vote if the candidate's log is "at least as up-to-date" as the voter's log. The paper defines this precisely: compare the last log entry's term first; if equal, compare log length. A candidate with a shorter or older log cannot win. This prevents a server with stale entries from becoming leader and overwriting committed state.

Log replication: AppendEntries and the matching property

Once a leader is elected, all client requests go through it. The leader appends the entry to its local log and sends AppendEntries RPCs to followers in parallel. An entry is committed once the leader has received acknowledgment from a majority of servers, including itself.

The key mechanism for maintaining consistency is the consistency check in AppendEntries. Every AppendEntries RPC includes:

• prevLogIndex: the index of the log entry immediately before the new entries
• prevLogTerm: the term of that entry

A follower rejects the RPC if its log doesn't contain an entry at prevLogIndex with term prevLogTerm. This enforces the Log Matching Property: if two logs contain an entry at the same index with the same term, then the logs are identical in all entries up to that point.

When a new leader is elected after a period of failures, some followers may have divergent log tails — entries the old leader appended but never committed before crashing. The new leader discovers this through the consistency check rejections and walks back the follower's nextIndex until it finds the common prefix, then resends entries from that point. The follower's conflicting entries are overwritten. This is safe because uncommitted entries — entries that were never acknowledged to a majority — can be safely discarded.

Safety: why the election restriction matters

The most important safety property is Leader Completeness: a leader must contain all log entries committed in previous terms.

This follows from the vote granting rule. For an entry to be committed, it must be present on a majority of servers. For a server to become leader, it must receive votes from a majority. Any two majorities overlap in at least one server. That overlapping server has the committed entry and will not grant a vote to a candidate whose log is less up-to-date.

There's a subtle wrinkle: a leader cannot immediately commit entries from previous terms even if they're replicated on a majority. The paper includes a figure (Figure 8) showing a scenario where committing an old-term entry directly would cause a future leader to overwrite it. The fix: a leader only directly commits entries from its own term. Old-term entries become committed indirectly — when the leader commits a new entry from the current term, the Log Matching Property guarantees that everything before it is also committed.

This is one of the paper's most commonly misimplemented points. If your implementation tries to commit old-term entries directly, you can construct scenarios where committed entries are overwritten.

Cluster membership changes: joint consensus

Adding or removing servers without taking down the cluster is the hardest part of Raft to implement correctly. The naive approach — just update the configuration on each server — creates a window where two disjoint majorities could exist simultaneously, allowing two leaders.

Raft solves this with joint consensus: a two-phase transition through an intermediate configuration that requires agreement from both old and new majorities simultaneously.

1. The leader appends a joint configuration entry C_old,new to the log
2. During joint consensus, both old and new majorities must agree on leadership and log entries
3. Once C_old,new is committed, the leader appends C_new
4. After C_new commits, the old configuration is no longer relevant

This ensures there's no moment where a split majority could independently elect two leaders. The cluster is never simultaneously in two independent configurations.

Most production implementations now use the single-server change simplification: only add or remove one server at a time. This avoids joint consensus entirely — a single-server change can't create two independent majorities because any two majorities of N and N+1 (or N and N-1) share at least one server. etcd uses this approach.

Production tradeoffs no one mentions at configuration time

Heartbeat interval and election timeout interact with disk write latency. etcd fsyncs every log entry to disk before responding to the leader's AppendEntries. If your disk is slow or the OS is under write pressure, fsync latency spikes. If a spike exceeds the election timeout, followers incorrectly conclude the leader is dead and start an election. The "leader election storm" in the incident above: a node under disk pressure had fsync latency of ~400ms during a GC pause. Election timeout was 500ms. Just enough to trigger an election, restart the heartbeat cycle, trigger another one.

The practical tuning rule: election timeout should be at least 10× the fsync latency at the 99th percentile. If your etcd node's disk writes take 10ms, your election timeout should be at least 100ms. The default etcd values assume fast SSDs.

The pre-vote problem. When a Raft server gets isolated from the cluster (network partition, asymmetric connectivity), it can't receive heartbeats, so it increments its term on every election timeout and holds a new election that fails. When it rejoins, it arrives with a term higher than the current leader's. The current leader, receiving an AppendEntries rejection with a higher term, steps down. This triggers an unnecessary election even though the cluster was healthy.

The Pre-Vote extension (described in the Raft dissertation) fixes this: before incrementing its term, a candidate checks whether it can win a real election without actually starting one. If it can't reach a majority, it doesn't increment the term. etcd 3.4+ implements this; most production deployments should enable it.

Linearizable reads require extra work. A naive read-from-leader is not linearizable. A leader might have been partitioned and deposed without knowing it; it would serve stale reads. Raft offers two approaches:

• ReadIndex: the leader records its current commit index, sends a heartbeat to confirm it's still the leader, and only serves the read after the state machine has applied all entries up to that index. Safe but adds a heartbeat round-trip to every read.
• Leader leases: the leader assumes it's still the leader for a fixed duration after receiving a quorum of heartbeat acknowledgments. Faster but assumes bounded clock skew — if clocks drift beyond the lease duration, you can serve stale reads from a deposed leader. This breaks the safety proof.

etcd's default is ReadIndex. If you've configured your etcd client to use leader leases for performance, you've traded a safety guarantee for latency.

Failure modes in practice

Snapshot installation creates availability gaps. When a follower is so far behind that the leader has already compacted its log (replaced old entries with a snapshot), the leader must send the full snapshot via InstallSnapshot RPC. Snapshots in a 50GB key-value store can be multi-gigabyte. During snapshot transfer, the follower is unavailable, and you're one more failure away from losing quorum. Teams with large etcd clusters hit this when they let their key-value size grow unbounded and don't compact regularly — routine node restart turns into a multi-minute recovery.

Write amplification on every commit. Raft's durability guarantee requires that log entries are persisted to stable storage before acknowledging to the leader. For every write to a Raft-replicated system, you pay disk I/O on every replica. If your workload has many small writes (individual key updates rather than batched), this write amplification can dominate throughput. This is why CockroachDB batches Raft log entries and why high-throughput users of etcd use a single key with merged state rather than per-entry writes.

Leader as bottleneck. Unlike some Paxos variants, Raft has a strong leader — all reads and writes flow through it. In a geo-distributed cluster, clients must route to the leader regardless of their location. If the leader is in us-east and the client is in eu-west, every write pays that round-trip. There's no way around this in vanilla Raft. Multi-Raft (sharding the keyspace across multiple independent Raft groups) is the standard mitigation, used by TiKV and YugabyteDB.

When not to use Raft

When you need more than strong consistency for a single region. Raft gives you linearizable operations on a single replicated state machine. If you need geo-distributed writes with low latency, Raft requires the write to be acknowledged by a majority — if that majority spans two data centers, your write latency is bounded by the inter-DC RTT. You want Raft for coordination metadata, not for a write-anywhere database.

When your workload is read-heavy at scale. Because linearizable reads still need the leader (or a ReadIndex round-trip), Raft doesn't scale read throughput across followers without relaxing consistency. If you have a 10:1 read/write ratio and need to serve reads from all replicas, Raft's strong leader model is a poor fit — you want a protocol that allows follower reads with weaker consistency, or a separate replication topology for reads.

When your coordination needs are small and latency requirements are tight. A Raft quorum write is at minimum two round-trips from the client's perspective (request to leader, leader commits to majority, response). For distributed locking or leader election in a system where 5ms latency matters, you're paying for safety you may not need. An in-process solution or an optimistic algorithm might be more appropriate.

When you can't tune the deployment for your hardware. Raft's heartbeat and election timeouts are not set-and-forget. The right values depend on disk write latency, network RTT, and the blast radius of a false election. If you're running managed etcd in a cloud where you can't observe per-node fsync latency, you're guessing at these values.

What the paper actually gives you

Raft is the consensus algorithm that made distributed systems engineers able to implement consensus correctly, at the cost of imposing a strong leader model that surfaces as a bottleneck in some workloads.

The understandability goal is real and measurable. The authors ran controlled studies comparing Raft and Paxos comprehension among grad students with equivalent background — Raft scored significantly higher on a range of understanding questions. This wasn't academic vanity. It directly translated into implementation quality: fewer bugs in early Raft implementations than in teams that had tried to build Multi-Paxos from the original papers.

The decomposition into three independent subproblems — leader election, log replication, safety — is the lasting contribution. When you're debugging an etcd issue, you're almost always debugging exactly one of those three pieces. The fault isolation is real.

For your specific situation: if you're running etcd, configure Pre-Vote, tune election timeout to 10× your p99 disk write latency, monitor snapshot compaction frequency, and use ReadIndex (not leader leases) unless you've validated clock synchronization on your nodes. If you're building a system that requires consensus, Raft is the correct starting point — not because it's optimal, but because it's implementable and debuggable in a way that Paxos never was.

The six-minute outage: election timeout was 500ms, fsync p99 was 400ms, and Pre-Vote was disabled. Three numbers. Three changes. No more storms.

---

In Search of an Understandable Consensus Algorithm — Diego Ongaro and John Ousterhout. USENIX Annual Technical Conference (ATC) 2014. Ongaro's dissertation (2014): Consensus: Bridging Theory and Practice — contains the Pre-Vote extension, leadership transfer, and expanded membership change analysis.