Consensus: nodes crash,
the cluster still agrees.

Consensus means getting a group of nodes to agree on a single value, even when some fail. It sounds trivial until you add reality: messages arrive late or never, nodes crash and recover, and you can't tell a slow node from a dead one. The FLP impossibility result (Fischer, Lynch and Paterson, 1985) proves that in a fully asynchronous network, no deterministic algorithm can guarantee it will ever reach a decision if even one node may crash. So real systems split the promise: they are always safe, never deciding two different values, and they use timeouts and randomization to make progress whenever the network behaves well enough.

Many everyday problems are consensus in disguise: electing a leader, agreeing the next entry in a replicated log, deciding whether a distributed transaction committed, or maintaining a distributed lock. Solve consensus once and you get all of them.

The core trick is the majority quorum. If every decision needs votes from a strict majority, then any two decisions must share at least one node — because two majorities of the same set always overlap. That single overlapping node can't vote for two conflicting values, so two leaders or two conflicting commits can never both succeed, even during a partition.

It's all counting. A majority is ⌊N/2⌋+1, a cluster survives N−majority failures, and because two majorities sum to more than N they must share a node — so at most one leader per term:

And 3+3 > 5, so two candidates can't both reach a majority — Raft's single-leader guarantee, from pure arithmetic. The runnable version below runs an election and the fault-tolerance table.

These majority quorums are not the tunable W and R quorums of leaderless stores. A W + R > N quorum guarantees that two sets of replicas overlap, but it never gets nodes to agree on an order of operations, which is why it can't give you a safe compare-and-set. The CAP handbook works through where those quorums break.

Raft was designed to be understandable. It elects a single leader for a term; the leader takes all writes, appends them to a replicated log, and an entry is committed once a majority has stored it. If the leader goes silent, followers time out and a new election starts. It powers etcd, Consul, and CockroachDB.

Paxos reaches the same safety with proposers, acceptors, and learners, but is famously hard to reason about and implement; Multi-Paxos adds a stable leader for efficiency. The first rule is to reach for an existing implementation rather than writing your own. The internals below still matter: they are what an interviewer probes with "what happens if the leader crashes mid-write?", and they explain how the systems you run fail.

Terms are Raft's logical clock. Each term starts with an election and has at most one leader, and every message carries the sender's term. A node that sees a higher term adopts it and becomes a follower; a message with a lower term is rejected. That one rule is how a deposed leader finds out.

Randomized election timeouts stop elections colliding. A follower that hears nothing from a leader for a random interval (the Raft paper suggests 150–300 ms) starts an election. Usually one node times out first, wins, and sends heartbeats before anyone else wakes; if two candidates split the vote, both time out again with fresh random waits. The timeout must sit well above the network round trip and well below the time between failures.

The vote rule keeps committed entries alive across leader changes. A node votes at most once per term, and only for a candidate whose log is at least as up to date as its own: the later last-entry term wins, and on a tie the longer log wins. A committed entry sits on a majority and a winner needs votes from a majority, so some voter holds every committed entry and refuses any candidate missing one. Every new leader therefore already has every committed entry.

# RequestVote: at most one vote per term, only for an up-to-date log
def grant_vote(me, term, cand, cand_last_term, cand_last_index):
    if term < me.term:
        return False                          # stale candidate
    if term > me.term:
        me.term, me.voted_for = term, None    # new term: become follower, forget old vote
    up_to_date = (cand_last_term, cand_last_index) >= (me.last_term(), me.last_index())
    if me.voted_for in (None, cand) and up_to_date:
        me.voted_for = cand                   # persist to disk before replying
        return True
    return False

# AppendEntries: accept only if our log matches the leader's just before the new entries
def log_matches(me, prev_index, prev_term):
    return prev_index == 0 or me.term_at(prev_index) == prev_term

Log matching is how the leader repairs followers. Each AppendEntries message carries the index and term of the entry just before the new ones, and a follower rejects it unless its own log has that entry. On a rejection the leader retries from an earlier entry until the logs agree; the follower then deletes everything after that point and takes the leader's entries. By induction, if two logs hold an entry with the same index and term, they are identical up to that entry.

The commit rule has one subtlety, the case the Raft paper devotes a figure to. An entry is committed once the leader that created it has stored it on a majority, and a leader advances its commit index only by counting replicas of entries from its own term. An entry left over from an earlier term can sit on a majority and still be overwritten by a later leader; it is safe only once a current-term entry after it commits. So a new leader opens its term by appending a no-op entry: committing it commits everything before it and tells the leader where the commit point is. Watch it happen in the Raft simulator, or code the vote count in the Raft election challenge.

Raft's writes are safe by construction: a deposed leader can't get a majority to accept its entries. Its reads are not. A leader cut off by a partition, with a new leader already elected on the other side, still has its local state and can answer from it, missing writes the new leader has committed. It hasn't heard of the new term, so from where it sits nothing is wrong.

ReadIndex has one precondition: a new leader must first commit an entry from its own term (the no-op above) before it knows the true commit index. In practice, etcd serves linearizable reads by default using ReadIndex and offers a cheaper serializable read answered by the local member, which can be stale. ZooKeeper answers reads from whichever server the client is connected to, so they can lag; calling sync first makes that server catch up with the leader. CockroachDB serves reads from each range's leaseholder.

Membership changes. Switching from configuration A to configuration B in one step is unsafe. Mid-switch, some nodes count votes against A and some against B, and a majority of each can be disjoint (two of {1, 2, 3} against three of {1, 2, 3, 4, 5}), so two leaders can win the same term. Raft has two safe methods. Joint consensus, from the original paper, passes through an intermediate configuration in which every decision needs majorities of both A and B. Single-server changes, from Diego Ongaro's dissertation, add or remove one node at a time, because then any majority of the old configuration overlaps any majority of the new one. Either way, add a node as a non-voting learner first and promote it once it has caught up, as etcd supports; an empty voter raises the quorum size before it can acknowledge anything.

Snapshots. The log can't grow forever. Each node periodically snapshots its state machine and discards the log up to that point, keeping the index and term of the last entry the snapshot covers, because the next AppendEntries consistency check compares against exactly that entry. A follower so far behind that the leader has already discarded the entries it needs is sent the snapshot itself (InstallSnapshot), then resumes normal replication.

Basic Paxos decides one value. Proposers use proposal numbers that are unique and increasing (a counter paired with the proposer's ID works), and a value is chosen once a majority of acceptors accept the same proposal.

Rule 2a is the heart of it: once a value might have been chosen, any later proposer is forced to propose that same value, so a different one can never win. Two proposers can still livelock by pre-empting each other with ever-higher numbers, so real systems elect a distinguished leader. Multi-Paxos runs phase 1 once for that leader, then decides a long run of log slots with phase 2 alone, one round trip each. Google's Chubby lock service and Spanner replicate with Paxos; ZooKeeper uses its own protocol, Zab.

Seen this way, Raft is Multi-Paxos with a stricter rule about who may lead. A term plays the proposal number, an election plays phase 1, and AppendEntries plays phase 2. The difference is that a Paxos leader learns which values it must re-propose from the promises it collects, while Raft lets only a node with an up-to-date log win, so its leader never has to learn anything from voters. Heidi Howard and Richard Mortier's 2020 paper "Paxos vs Raft: Have we reached consensus on distributed consensus?" draws the comparison in detail, and the Raft vs Paxos handbook covers the practical choice.

You almost never implement consensus yourself. Instead you lean on a coordination service — ZooKeeper, etcd, or a cloud equivalent — which runs the consensus protocol internally and exposes simple primitives: leader election, distributed locks, configuration storage, and membership/failure detection. The rule of thumb: keep the coordination service for the small, critical state that must be globally agreed, and keep your bulk data out of it.

When one logical operation spans multiple services or shards, you need them to agree on commit-or-abort.

2PC buys you atomicity at the cost of availability — a stalled coordinator leaves participants holding locks. Sagas trade atomicity for availability: each step commits independently and a failure triggers compensating actions (refund the charge, release the seat). Most modern microservice systems prefer sagas precisely because they don't block.

Networks deliver at least once — retries mean the same request can arrive twice. True "exactly-once delivery" is impossible, but you can get exactly-once effects by making operations idempotent: applying them twice has the same result as applying them once.

The standard mechanism is an idempotency key — a unique ID the client attaches to a request. The server records processed keys and, on a duplicate, returns the original result instead of doing the work again. This is how a retried payment charges the card once, and how a redelivered queue message isn't processed twice.

A 5-node Raft cluster, so a majority is 3. Leader S1 is in term 4. Its log holds entries 1–4 from term 3 and entries 5–7 from term 4. The followers have acknowledged different amounts. The state is illustrative.

Step 8 is not data loss. Entries 6 and 7 were never committed, so no client was told they succeeded, and those clients will time out and retry. Step 3 is where the subtle rule bites. Suppose entry 5 had been written in term 3 by an earlier leader. Being on three nodes would not make it committed. A later leader that never saw it could still win and overwrite it. S1 would have to get a term-4 entry, such as its opening no-op, onto a majority first. That commits entry 5 along with it.

Here Time is what each decision waits for, and Space is the replication or state it costs.

Adding voters buys fault tolerance and costs speed: each write has to wait for more acknowledgements. To scale throughput, split the data into many small consensus groups instead of making one group bigger.

• Three nodes in two zones

  Two nodes in zone A and one in zone B looks redundant. But if zone A goes down, one node of three is left, with no majority and no writes. Put each voter in a separate failure domain: three zones for three nodes.

• Adding voters to go faster

  Every write in a consensus group goes through one leader and waits for a majority. More voters means a bigger majority and more copies to send. To spread reads, use non-voting learners or follower reads. To spread writes, partition the data into separate groups.

• An idempotency check that races

  “Look up the key; if missing, charge the card; then save the key” fails two ways. Two retries arriving together both see no key and both charge. A crash between charging and saving loses the record. Insert the key first, under a unique constraint, in the same transaction as the effect, or mark it “in progress” and let duplicates wait for the result.

• Compensations that can fail

  A saga’s undo steps run during an incident, so they get retried, and they must be idempotent: a refund keyed by the original charge id, not “refund $20”. And a compensation does not erase the past. The customer may already have seen the charge or the confirmation email.

• Election timeouts close to normal pauses

  If the election timeout is near the heartbeat interval, or below typical disk-flush or GC pauses, followers keep deciding a healthy leader is dead. Size it from measured round-trip and fsync latency, and alert on leader changes.

• Kubernetes runs on etcd

  All of a Kubernetes cluster’s desired state lives in etcd, a Raft group, and the API server is its client. When etcd loses its majority, the API server can no longer accept writes. Running pods keep running, but nothing can be scheduled or changed.

• Kafka dropped ZooKeeper

  Kafka used to keep cluster metadata in ZooKeeper. Newer versions use KRaft, a Raft-based quorum of controller nodes inside Kafka itself. Consensus guards the small metadata; the bulk data uses plain replication.

• Thousands of small Raft groups

  CockroachDB and TiKV split their key space into ranges of limited size and run a separate Raft group for each one. That is how a consensus database scales writes. The leaders of different groups sit on different nodes.

• Idempotency keys on payment APIs

  Stripe’s API takes an Idempotency-Key header, and a retry with the same key returns the first result instead of charging twice. In a “design a payment system” interview, describe that key, where it is stored, and what a duplicate gets back.