Consensus: Raft and Paxos

1The core idea#

Pin down what consensus actually promises before reasoning about any protocol.

The problem in one sentence.

• Get a group of servers to agree on a single sequence of decisions.
• They must agree even though servers crash, messages arrive late, and the network drops packets.

The guarantee you want.

• Once the group commits a value, everyone alive eventually sees that same value.
• Nobody ever sees a different one.
• No split brains, no two leaders handing out contradictory answers.

The mental model I give juniors: a shared notebook.

• Five people write in it. A line counts as "written" only once a majority, 3 of the 5, copy it into their own notebook.
• Any two groups of 3 out of 5 must share at least one person, so there is always a witness who remembers the last agreed line.
• That overlap is the whole trick. It is called quorum intersection, and it is why consensus survives a minority of failures without ever contradicting itself.

Why a majority and not all, or just one?

• Require all 5 to ack: one dead node freezes the system forever.
• Require just 1: two halves of a partition each decide on their own and diverge.
• Require a majority of 3: you can lose 2 nodes and still make progress, and you can never split 5 nodes into two disjoint groups that both have 3.

The result that bounds all of it: FLP impossibility.

• In a purely asynchronous network you cannot guarantee both safety and liveness with even one faulty process.
• Real systems dodge it by assuming the network is mostly timely (a partial-synchrony model) and using timeouts to make progress.
• So consensus protocols are always safe, and they are live "when the network behaves." Keep that distinction in your back pocket for interviews.

2How it works#

I will walk through Raft, because it was explicitly designed to be understandable, then say where Paxos differs.

Raft splits the problem into three pieces.

• Leader election: pick one leader per term.
• Log replication: the leader streams entries to followers and commits on majority.
• Safety: committed entries survive every future leader.

At any moment the cluster has one leader and the rest are followers. Time is divided into terms, each a monotonically increasing number, and a term starts with an election.

Leader election.

• Every follower runs a randomized election timeout, usually 150 to 300 milliseconds.
• Hear nothing from a leader in that window: bump the term, vote for yourself, ask everyone else for a vote.
• A server grants its vote at most once per term, and only if the candidate's log is at least as up to date as its own.
• Win a majority and you are leader.
• The randomness is what stops elections colliding forever: two candidates rarely time out at the same instant, so one usually pulls ahead.

Log replication.

• Clients send commands to the leader.
• The leader appends the command to its own log, then sends AppendEntries to the followers.
• Once a majority have written the entry, the leader marks it committed, applies it to its state machine, and replies to the client.
• Those same AppendEntries messages, sent empty, double as heartbeats that stop new elections.

Safety: the part people skip and interviewers love.

• Raft guarantees that if an entry is committed in some term, it stays in the log of every future leader.
• Rule one, the vote check: a candidate only wins if its log is at least as fresh as the voter's, so a stale server can never become leader and erase committed data.
• Rule two, the current-term rule: a leader only counts an entry as committed once it has replicated an entry from its own current term.
• That second rule is subtle. It closes a real hole where an old entry could look replicated and then get overwritten.

Paxos solves the same problem, presented differently (which is why it is harder to learn).

• Basic (single-decree) Paxos agrees on one value through two phases.
• Prepare: a proposer picks a number n and asks acceptors to promise not to accept anything numbered below n. If a majority promise and some already accepted a value, the proposer must reuse the highest-numbered one.
• Accept: the proposer asks the majority to accept value v at number n. A value is chosen once a majority accept it.
• There is no fixed leader in the raw protocol: any node can propose, and dueling proposers can livelock, each preempting the other with a higher number.

Multi-Paxos is how you build a real log.

• Elect a stable leader (a "distinguished proposer") so you skip the Prepare phase for most entries, then stream Accept messages.
• At that point Multi-Paxos and Raft look almost identical in practice: one leader, a replicated log, majority commit.
• The difference is mostly in how carefully the leadership and log-matching rules are spelled out.

3A worked example with real numbers#

"Majority round trip" is abstract until you put milliseconds on it, so let me make it concrete.

The setup.

• A 5-node Raft cluster for a config store, spread across three availability zones in one region.
• Round-trip time between zones is about 1 ms.
• Each node has an NVMe disk that fsyncs a small log entry in roughly 1 ms.

A single committed write.

• The client's write lands on the leader.
• The leader appends and fsyncs its own entry: 1 ms.
• In parallel it ships AppendEntries to the other 4 nodes, each of which must fsync before acking.
• It commits the moment it has a majority (3 nodes including itself), so it needs acks from the 2 fastest followers.
• Network out, plus follower fsync, plus network back is about 1 + 1 + 1 = 3 ms, and that overlaps the leader's own 1 ms fsync.
• A healthy commit is roughly 3 to 4 ms. The client sees maybe 5 ms end to end once you add its own hop.
• The two slowest followers catching up later does not block the client. The leader already had its majority.

Throughput, and the counterintuitive part.

• One Raft group commits serially through one leader.
• Even with batching, a single group on this hardware tops out around a few tens of thousands of writes per second before the leader's fsync and the serial commit pipeline become the wall.
• Adding a 6th and 7th node does not raise that number. It lowers it, because the leader fans out to more followers and waits on a larger quorum.
• This is the single most counterintuitive fact about consensus, and I come back to it in the trade-offs.

Failure math.

• With 5 nodes the majority is 3, so you tolerate 2 simultaneous node failures and keep serving.
• One full AZ goes dark holding 2 of your 5 voters: you still have 3 alive in the other two AZs, still form a majority, still take writes.
• If the dead AZ held the old leader, you pay a one-election blip of maybe 150 to 300 ms while a new one is chosen.
• That is the entire payoff of odd-count, multi-AZ placement expressed in numbers.

4Trade-offs#

Three decisions carry the whole design.

Decision one: Raft versus Paxos as a model.

• Same guarantees from both.
• Raft wins on understandability and has a clear reference spec, so most new systems since 2014 reach for it.
• Paxos (really Multi-Paxos) has a longer production track record and, in expert hands, more flexibility in handling proposals and log holes.
• My honest take: implementing from scratch, use Raft. A protocol you can reason about is a protocol you can debug at 3 a.m.

Decision two: how many nodes.

• More nodes tolerate more failures, but every write still needs a majority, so latency is bounded by the slowest node in the quorum.

• Three or five is the usual answer.
• Seven is rare: the extra fault tolerance rarely pays for the added write latency and the bigger quorum to coordinate.
• Always odd. Going from 3 to 4 does not improve fault tolerance (both tolerate 1 failure) but makes the majority harder to reach, 3 of 4 instead of 2 of 3.

Decision three, the one juniors miss: consensus is a write bottleneck.

• Every committed write goes through one leader and one round trip to a majority.
• You do not scale writes by adding nodes. Adding nodes makes writes slower, exactly as the worked example showed.
• The fix in the field is to shard: run many independent Raft or Paxos groups, each owning a slice of the keyspace, so throughput scales with the number of groups rather than the size of any one group.
• That is exactly what Spanner and CockroachDB do.

You never scale a consensus group. You scale the number of groups.

When consensus is the wrong tool entirely.

• That table is the CAP conversation in disguise.
• Consensus picks C and P: during a partition the minority side refuses writes to stay consistent.
• If your product needs the minority side to keep taking writes, consensus is wrong and you want an AP design with conflict resolution.

5Where it is used#

Consensus shows up wherever a system needs a single source of truth that must not fork.

• Coordination services. etcd (used by Kubernetes) runs Raft. ZooKeeper runs Zab, a Paxos-flavored protocol. They store cluster config, leader locks, and service membership: small data that absolutely must be consistent.
• Distributed databases. Google Spanner uses Paxos groups per shard. CockroachDB and TiKV use Raft per range. YugabyteDB uses Raft. The pattern is always many small consensus groups, never one giant one.
• Message and log systems. Kafka's newer KRaft mode replaced ZooKeeper with a Raft-based metadata quorum.
• Lock services and schedulers. Google's Chubby is the original Paxos-backed lock service, and half the industry copied the idea.

When I reach for it in a design interview.

• Any time two components would otherwise fight over "who is the leader," "what is the current config," or "did this transaction commit."
• If a disagreement must resolve to a hard yes or no with no take-backs, that is consensus.
• If the data can tolerate "eventually everyone agrees," do not pay the consensus tax. Use replication with a weaker model.

6Common pitfalls and gotchas#

These are the specific ways candidates (and shipped systems) get it wrong.

Thinking the leader can reply before a majority acks.

• It cannot. A write is not committed until a majority has it durably.
• Ack early, then crash, and that write can vanish. You have lied to the client.

Forgetting disk durability.

• A node must persist its vote and log entries to stable storage before acking.
• Ack from memory, crash, come back having "forgotten" its vote, and it can vote twice in a term. Now you have two leaders.
• This is a real bug people ship.

Clock-based reasoning.

• Consensus safety must never depend on synchronized clocks.
• Timeouts affect only liveness (how fast you elect a leader), never safety.
• If a candidate's correctness argument uses wall-clock time, it is wrong.

The read problem.

• Reads need care too. A node that thinks it is leader might have been deposed during a partition while it still believes it is in charge.
• Serving reads from that stale leader returns old data.
• Fixes: lease-based reads (the leader holds a time-bounded lease) or routing reads through the log (a ReadIndex round trip to confirm it is still leader).
• "Just read from the leader" is a weak answer.

Even-numbered clusters and single-DC quorums.

• Four nodes buy you nothing over three.
• If all your voters sit in one AZ, you lose the whole cluster when that AZ blips. Spread voters across failure domains.

Membership changes.

• Adding or removing a node is dangerous: for a moment the "old majority" and "new majority" can disagree.
• Raft handles this with joint consensus or single-node-at-a-time changes.
• Hand-editing the member list live is how you create two leaders.

7How it shows up in interviews#

Interviewers use consensus to separate people who memorized "use a quorum" from people who understand why. Here is the contrast I grade on, bad answer next to the one that moves you up a level.

"Why a majority?"

• Weak: "Because majority rules, that is how voting works."
• Strong: "Any two majorities intersect. In a 5-node group, any two sets of 3 share at least one node, so there is always a node that remembers the last committed value. That overlap is what makes divergence impossible. A minority can never form a second majority to commit a conflicting value."

"What happens during a partition?"

• Weak: "The system keeps working."
• Strong: "Split a 5-node group 3-2. The side with 3 keeps a quorum, elects or keeps a leader, and serves writes. The side with 2 cannot reach a majority, so it refuses writes and, unless it steps down or uses a lease, may serve stale reads. When the partition heals, the 2-node side catches up from the leader's log. I gave up availability on the minority side on purpose to keep consistency."

"How do you avoid two leaders?"

• Weak: "The old leader just steps down."
• Strong: "Terms, plus one-vote-per-term, plus persisting the vote to disk before acking. An old leader stuck on the 2-node side can still think it is leader, but it cannot commit anything because it cannot reach 3 nodes. Its writes stall, so even without knowing it was deposed it does no damage. When it rejoins it sees a higher term and reverts to follower."

"How do you scale writes past a few tens of thousands per second?"

• Weak: "Add more nodes."
• Strong: "Adding nodes makes a single group slower, not faster, because the quorum grows. You shard into many independent Raft groups, each owning a key range, the way CockroachDB does per range and Spanner does per Paxos group. Throughput then scales with the number of groups."

"How do consistent reads work?"

• Weak: "Read from the leader."
• Strong: "A leader can be stale after a partition. Use a leader lease so the leader knows it is still in charge for a bounded window, or a ReadIndex round trip that confirms leadership with a majority before answering. Only then is the read linearizable."

The quiet part the strongest candidates say out loud.

• Consensus trades availability and write latency for consistency.
• FLP means it can stall under a bad enough network.
• The real-world move is lots of small groups, not one big one.

For a hands-on application of these ideas, see the related System Design Question walkthrough on building a distributed key-value store with a replicated log.