Consensus & Raft

What consensus has to guarantee

• Agreement — no two nodes decide differently.
• Validity — the decided value was proposed by someone (not invented).
• Termination — every non-faulty node eventually decides.
• Integrity — nodes decide at most once.

In practice you rarely want a single value; you want a replicated log — an ordered sequence of commands that every node agrees on. Feed that identical log into identical deterministic state machines and every replica ends up in the same state. This is state machine replication, and it's what turns consensus into a usable database.

FLP, and why it doesn't stop us

The FLP impossibility result: in a fully asynchronous system where even one node may fail, no deterministic algorithm can guarantee consensus.

The reason connects directly to failure models: you cannot distinguish a crashed node from a slow one, so an algorithm can be kept indefinitely undecided by sufficiently unlucky timing.

Real systems sidestep it — they don't refute it:

• Partial synchrony — assume the network is eventually well-behaved. Timeouts work most of the time.
• Randomisation — randomised election timeouts break the symmetry that keeps a system undecided.

So Raft guarantees safety always (never two leaders in one term, never a committed entry lost) and liveness only when the network cooperates. That's the right split: it may stall, but it will not corrupt.

Raft

Raft was explicitly designed to be understandable, decomposing consensus into three pieces.

Leader election

Every node is Follower, Candidate, or Leader. Time is divided into terms, each with at most one leader.

1. Followers expect heartbeats. If none arrives before a randomised election timeout (say 150–300 ms), the follower becomes a Candidate.
2. It increments the term, votes for itself, and requests votes.
3. A node grants its vote if it hasn't voted this term and the candidate's log is at least as up to date as its own.
4. A majority of votes makes it Leader, and it starts sending heartbeats.

The randomised timeout is the whole trick for liveness: if two candidates split the vote, they'll time out at different times and one will win the next round. With fixed timeouts they could deadlock indefinitely.

Log replication

1. Clients send commands to the leader only.
2. The leader appends to its log and sends AppendEntries to followers.
3. Once a majority has persisted the entry, the leader marks it committed and applies it to its state machine.
4. Followers learn of the commit from subsequent messages and apply it too.

An entry that's committed is committed forever. This is the safety property everything else protects.

Safety

The subtle part. Raft must guarantee a new leader never erases a committed entry, which it gets from the election restriction: a node only votes for a candidate whose log is at least as up to date as its own.

Since a committed entry is on a majority, and any winning candidate needs a majority, the two majorities must overlap — so at least one voter has the entry and will refuse to vote for a candidate lacking it. Any node that can win an election necessarily already has every committed entry.

That's the same pigeonhole argument as quorums, doing much heavier lifting.

Why odd numbers

A cluster of 2f + 1 nodes tolerates f failures, because a majority must remain reachable.

Even sizes are strictly worse than the odd number below them: 4 nodes tolerate the same one failure as 3, while needing a larger majority (more latency) and adding a machine's worth of failure probability. Always odd.

Three is the common default. Five is for when you want to survive two failures — or one failure during a maintenance window, which is the real reason. Seven is rare; every write must reach four nodes, and the coordination cost outgrows the benefit.

What it costs

Every committed write requires a round trip from the leader to a majority. That means:

• Within one datacenter: sub-millisecond. Effectively free.
• Across regions: the round trip to the second-nearest region, on every write. A cluster spanning Zurich, Frankfurt, and Dublin commits at roughly Frankfurt's 8 ms. Spread it to us-east-1 and you're committing at ~90 ms.
• Throughput is bounded by the leader, which handles all writes. Consensus does not scale writes horizontally; that's what partitioning is for. Systems like CockroachDB and TiKV run one Raft group per data range precisely so they can scale.

Paxos, Multi-Paxos, ZAB, and friends

• Basic Paxos — the original; agrees on a single value. Correct, famously hard to follow, and not directly usable.
• Multi-Paxos — Paxos with a stable leader, agreeing on a sequence. Functionally similar to Raft; the family Google's systems descend from.
• ZAB — ZooKeeper's protocol, similar shape with different recovery.
• Viewstamped Replication — predates Paxos, structurally close to Raft.

For interviews, know Raft properly and mention that Paxos solves the same problem. Nobody wants a Paxos derivation; they want to see you understand leader election, majority commit, and the safety argument.

When you actually need it

Yes: leader election, cluster membership, configuration that must not diverge, distributed locks, uniqueness constraints, anything where two simultaneous answers is a correctness bug.

No: high-volume application data, anything tolerating eventual consistency, single-region data a primary/replica setup already handles, and — critically — anything you can design so coordination isn't required.

That last point is the real lesson:

What to take away

• Consensus produces an agreed ordered log; identical logs into identical state machines gives linearizable replication.
• FLP says it's impossible in a fully async system; real protocols use timeouts and randomisation to get safety always and liveness usually.
• Raft: randomised election timeouts, majority commit, and an election restriction that keeps committed entries safe by quorum overlap.
• 2f+1 nodes tolerate f failures. Even sizes are strictly worse. Use 3 or 5.
• Every write costs a majority round trip, and throughput is capped by the single leader.
• Use it for small critical metadata. Design so you need as little of it as possible.