Q41 — How do distributed systems reach consensus — what is Raft actually solving?

What is the consensus problem?

Consensus is a specific problem in distributed systems: multiple nodes must agree on a single value, even when some nodes crash or messages are lost.

The use cases are everywhere: electing a leader among a cluster of servers, deciding whether a distributed transaction committed or aborted, agreeing on the next log entry to append in a replicated database, determining which configuration is current in a distributed config service.

The challenge is deceptively simple to state: if you ask all 5 nodes "what is the value?", they should all give the same answer. But nodes crash, restart, slow down, and network messages arrive out of order or not at all. Getting 5 independent machines to reliably agree on anything — even a single integer — requires a carefully designed protocol.

Why can't nodes just vote?

The intuitive approach: have each node propose a value, everyone votes, majority wins.

The problem: what if votes are delayed? Node A proposes value X and gets 3 votes (a majority). Before Node B learns that X won, Node B starts a new round and proposes value Y. Some nodes receive B's proposal and vote for Y before they've heard the result of A's round. You now have two "majorities" for different values — which is logically impossible but easily achieved in an asynchronous network where messages can be delayed arbitrarily.

Naive voting doesn't account for the fundamental difficulty: you can't tell the difference between "Node B's message is delayed" and "Node B has crashed." The network looks the same in both cases. Any protocol that assumes messages arrive within some time bound is vulnerable to violation when the network is slow.

This is the FLP impossibility result (Fischer, Lynch, Paterson, 1985): in an asynchronous distributed system where even one node can fail, there is no deterministic algorithm that always reaches consensus in finite time. This doesn't mean consensus is impossible in practice — it means any real protocol must make some timing assumption (usually: "eventually, messages get through, even if we can't bound when") and must handle the case of being temporarily unable to make progress.

What was Paxos, and why wasn't it enough?

Paxos, invented by Leslie Lamport in 1989 (published 1998), was the first practical consensus protocol. It solves the problem correctly: it reaches consensus on a value even with node failures and network delays.

But Paxos has a serious practical problem: it is notoriously difficult to understand and implement correctly. Lamport described it as a "parliament" metaphor that obscured rather than clarified the algorithm. Real-world Paxos implementations routinely had subtle bugs. Lamport himself wrote a paper called "Paxos Made Simple" to try to help — and the simplified version was still complex.

The research community had an open challenge: build a consensus protocol designed for understandability. Raft was the answer.

What is Raft solving, and how does it work?

Raft was designed by Diego Ongaro and John Ousterhout (2014) with the explicit goal of being understandable. It breaks consensus into three relatively independent sub-problems: leader election, log replication, and safety.

The core insight: use a leader.

Raft designates one node as the leader at any time. All client requests go to the leader. The leader decides the order of log entries and replicates them to followers. Having a leader simplifies the protocol enormously — instead of all nodes negotiating with each other, all writes flow through one node.

Leader election:

All nodes start as followers. Each follower has an election timeout — a random duration (typically 150–300ms). If a follower doesn't hear from a leader within its timeout, it assumes the leader has failed and starts an election.

To start an election, the follower increments its term number (a monotonically increasing epoch), transitions to candidate state, and sends RequestVote messages to all other nodes: "I want to be the leader for term N. My log is up to date. Will you vote for me?"

Other nodes vote for a candidate if they haven't already voted in this term, and the candidate's log is at least as up-to-date as theirs. The candidate wins if it gets votes from a majority of nodes (including itself). It immediately becomes leader and starts sending heartbeats to suppress new elections.

The random election timeout is crucial: if all nodes timed out at the same moment, they'd all simultaneously start elections and split votes indefinitely. Randomization ensures one node's timeout fires first, giving it a head start. In practice, one node wins quickly.

Log replication:

Once a leader is elected, all writes go to it. The leader appends the new entry to its log and sends AppendEntries RPCs to all followers: "append this entry at position N after the entry I sent you at position N-1."

Followers append the entry to their local logs and respond. Once the leader has received responses from a majority of nodes (including itself), the entry is committed. The leader applies the committed entry to its state machine and responds to the client. The leader then tells followers the entry is committed on the next AppendEntries; followers apply it to their state machines.

The majority quorum is critical: any two majorities overlap in at least one node. This means any subsequent leader elected with a majority of votes will have heard from at least one node that has every committed entry — so committed entries are never lost.

The detail interviewers probe: a leader only marks an entry committed by counting replicas if the entry is from its current term. An entry left over from an earlier term can sit on a majority and still be overwritten by a later leader. Older entries become committed indirectly, once a current-term entry after them reaches a majority — which is why a new leader immediately appends a no-op entry for its term.

Term numbers as a safety mechanism:

Every message carries a term number. If a node receives a message with a higher term than its own, it immediately updates its term and reverts to follower state. This handles split-brain: if an old leader was partitioned and a new leader was elected in a higher term, when the old leader reconnects and receives any message with the higher term, it immediately steps down. The system never has two active leaders for the same term.

If a node receives a message with a lower term than its current term, it rejects the message. Stale leaders are silenced automatically.

What are Raft's safety guarantees?

Election safety: At most one leader is elected in any term. Proof: a candidate needs a majority to win; two majorities overlap in at least one node; a node can vote for at most one candidate per term; therefore, two candidates cannot both get majorities in the same term.

Log matching: If two logs contain an entry with the same index and term, all entries up to that index are identical. A leader never overwrites its own log — it only appends. A follower whose log conflicts with the leader's rejects the AppendEntries; the leader backs up until the logs agree and the follower's conflicting suffix is overwritten with the leader's entries. (Those overwritten entries were never committed — that's what the next property guarantees.)

Leader completeness: If a log entry is committed in a given term, it will be present in the logs of all leaders elected in higher terms. This follows from quorum overlap: a committed entry has been replicated to a majority; a new leader is elected by a majority; the overlap contains at least one node with the committed entry; Raft's election rules ensure a candidate with a less-up-to-date log cannot win.

Where is Raft used in real systems?

etcd: The key-value store used by Kubernetes for all cluster state. Every Kubernetes node count, pod assignment, config map, and secret is stored in a Raft-replicated log.

CockroachDB: Uses Raft for per-range replication. Each key range (partition) has a Raft group. Writes to a range are committed via Raft consensus among the replicas of that range.

TiKV (TiDB's storage layer): Raft for replication, used to build a distributed SQL database.

Consul: Leader election and distributed locking via Raft.

The mental model

Consensus problem: N nodes must agree on a single value despite crashes and delays
  Naive voting fails: delayed messages → false majorities → conflicting "winners"

FLP impossibility: no deterministic consensus in finite time in async systems
  Practice: protocols accept temporary unavailability, assume eventual message delivery

Paxos: correct, famously hard to implement correctly
Raft: same guarantees, designed for understandability

Raft = 3 sub-problems:

1. Leader election:
   Follower timeout (random 150-300ms) → candidate → increment term → request votes
   Majority vote → leader → sends heartbeats
   Random timeout → prevents simultaneous elections and split votes

2. Log replication:
   All writes → leader → AppendEntries to followers
   Majority ACK (of a current-term entry) → committed → apply → respond to client
   Next heartbeat tells followers to commit → they apply to their state machines

3. Safety via term numbers:
   Higher term received → immediately become follower (stale leader silenced)
   Committed entries survive all future leader changes (quorum overlap guarantees this)

Key invariant: any two majorities share at least one node
  → committed entries are always present in the next elected leader's log
  → no committed data is ever lost

Real systems: etcd (Kubernetes), CockroachDB, TiKV, Consul

Raft exists because distributed systems need a reliable way to elect one authority and replicate decisions — without requiring all nodes to be alive, without losing committed data on failure, and without two nodes simultaneously believing they're in charge. The leader model, quorum writes, and term numbers work together to make this reliable, understandable, and implementable in production.