Distributed consensus (surface)
Getting a group of unreliable machines to agree on one value — and why your job is to use a consensus system correctly, not to write one.
What consensus buys, and where you actually need it
Consensus is the problem of getting a set of nodes to agree on a single value, such that once a value is decided, every node that ever learns a decision learns the same one — even though nodes crash and restart, and messages are delayed, reordered, duplicated, or lost. It sounds abstract until you notice how many concrete production problems are secretly the same problem.
| Problem | The value being agreed on |
|---|---|
| Leader election | "Which node is the primary for term 7?" Every replication scheme with a single writer needs this, and needs it to be unambiguous. |
| Cluster membership and config | "Which nodes are in the cluster, and what is the current shard map?" A split view of membership is how you get two nodes both believing they own shard 12. |
| Distributed locks / leases | "Who holds the right to run the nightly billing job?" Running it twice is a customer-visible incident. |
| Atomic commit across shards | "Did transaction T commit or abort?" All participants must reach the same answer. |
| Exactly-once semantics | "Has message 91,442 been processed?" Exactly-once delivery is impossible; exactly-once effect is achievable by agreeing on a durable sequence and deduplicating against it. |
Equally important is the list of things that do not need consensus, because reaching for it unnecessarily is its own mistake: ordinary application data (use replication with quorums), counters and metrics (use CRDTs or just accept approximation), caches, and anything where "two nodes did the work" is merely wasteful rather than wrong. Consensus costs a majority round trip on every decision — you pay it only where correctness demands it.
The problem, stated honestly
What makes this hard is that in an asynchronous network you cannot distinguish a crashed node from a slow node from a node you can't currently reach. All three look identical: silence. The FLP result formalises this — with even one possible crash and no timing assumptions, no deterministic protocol can guarantee termination. Real systems escape it by adding a timing assumption in the form of timeouts, which makes progress probabilistic while keeping safety absolute. That split is the key idea to hold onto:
- Safety — never two different decisions, never a lost committed entry — holds unconditionally, even during arbitrary partitions and crashes.
- Liveness — actually deciding something — holds only when a majority can talk to each other for long enough. During a bad partition, a consensus system stops making progress. That is not a bug; it is the CP choice being exercised.
Raft: terms, elections, and why randomization matters
Raft was explicitly designed to be understandable, which is why it is the one to explain out loud. It decomposes consensus into leader election, log replication, and safety.
Time is divided into terms: monotonically increasing integers that act as a logical clock. Each term has at most one leader. Every message carries a term; a node seeing a higher term immediately steps down to follower and adopts it, and a node seeing a lower term rejects the message. That single rule retires stale leaders automatically.
A follower that hears no heartbeat within its election timeout becomes a candidate: it increments the term, votes for itself, and asks everyone for a vote. A node grants at most one vote per term, and only to a candidate whose log is at least as up to date as its own. Win a majority and you are leader; the first thing a leader does is send heartbeats to suppress further elections.
Why a majority guarantees at most one leader: two majorities of the same cluster must intersect in at least one node, and that node casts at most one vote per term. So two candidates cannot both reach a majority in the same term, and higher terms retire lower ones. This is the sentence to be able to say verbatim.
Why the timeout is randomized: if every follower used the same election timeout, they would all time out together, all become candidates, all split the vote, and all time out again — livelock. Randomizing each node's timeout over a range (the Raft paper suggests 150–300 ms; etcd defaults to 1000 ms with 100 ms heartbeats) means one node almost always wakes first and wins before the others start. Randomization is not a tuning detail; it is the liveness mechanism.
Log replication and the commit rule
Every state change is an entry appended to a replicated log. Clients send
commands to the leader; the leader appends locally, then sends
AppendEntries to followers. An entry is committed once
it is durably stored on a majority — at which point the leader applies it
to its state machine, returns to the client, and tells followers the new
commit index on the next heartbeat. Because every replica applies the same
entries in the same order, every replica ends in the same state. That is
the replicated state machine pattern, and it is what a consensus
system really sells you.
| Raft property | What it prevents |
|---|---|
Log matching: AppendEntries carries the index and term of the preceding entry; a follower rejects it if that doesn't match, and the leader walks backwards until it finds agreement, then overwrites the divergent tail. | Divergent histories silently persisting on a follower. |
| Election restriction: a voter refuses any candidate whose last log entry is older (lower term, or same term but shorter) than its own. | Electing a leader that is missing a committed entry — which would erase it. |
| Leader-term commit rule: a leader may only mark an entry committed by counting replicas if that entry is from its own term. Entries from previous terms become committed indirectly, once a current-term entry above them commits. | The subtle Figure-8 scenario where an entry replicated to a majority is still later overwritten. Naming this rule is a genuine expert signal. |
Persist before responding: currentTerm, votedFor, and the log must be fsynced before any reply. | A node that crashes and restarts voting twice in the same term — which elects two leaders and destroys safety. |
sync() first.
Cluster sizing — always odd, almost always 3 or 5
| Nodes | Majority | Failures tolerated | Comment |
|---|---|---|---|
| 3 | 2 | 1 | The default. Survives one node or one AZ. |
| 4 | 3 | 1 | Strictly worse than 3 — same fault tolerance, more nodes to ack every write. Never do this. |
| 5 | 3 | 2 | The right answer for anything critical: survives a node failure during a maintenance window. |
| 7 | 4 | 3 | Rarely worth it. Every write waits for the 4th-fastest node, so latency gets worse as you add members. |
Consensus clusters do not scale by adding members — throughput drops as they grow, because every decision needs a majority ack. You scale them by sharding the keyspace across many independent consensus groups, which is exactly what Spanner (one Paxos group per range) and CockroachDB (one Raft group per range) do. Expect single-digit-millisecond writes for a same-region etcd cluster, and tens of milliseconds if you stretch the members across regions.
Paxos, briefly
Paxos is the original (Lamport, 1989/1998) and is still the substrate for Chubby and Spanner. Single-decree Paxos agrees on one value with prepare and accept phases; Multi-Paxos amortises the prepare phase by keeping a stable leader — at which point it looks very much like Raft. It is notoriously hard to specify completely enough to implement, which is precisely the gap Raft was written to fill. In an interview: mention it as "the older, harder one that Raft was designed to replace as the teachable protocol", note that Multi-Paxos and Raft are equivalent in power, and move on. Do not attempt to derive Paxos at a whiteboard.
In practice: coordination services, split brain, and fencing
You almost never talk to Raft directly. You talk to a coordination service that has already solved it and exposes a small, safe API.
| Service | Protocol | Shape of the API | Reach for it when… |
|---|---|---|---|
| etcd | Raft | Key-value with revisions, leases, compare-and-swap, watches. Every write returns a monotonically increasing revision. | Kubernetes-adjacent infrastructure, service discovery, leader election, config. The default modern choice. |
| ZooKeeper | Zab | Hierarchical znodes, ephemeral and sequential nodes, watches. Ephemeral+sequential is the classic leader-election recipe. | The JVM ecosystem — Kafka (historically), HBase, Solr. Battle-tested for well over a decade. |
| Consul | Raft | KV, sessions, health checks, service catalogue, DNS interface. | Service discovery where health checking and multi-datacenter federation matter as much as the KV store. |
| Your database | varies | A row with a unique constraint plus a lease column is a perfectly good lock if you already have a strongly consistent database. | You don't want another stateful system to operate. Often the correct, boring answer. |
Split brain is what happens when two nodes simultaneously believe they are the leader. Majority quorum prevents two leaders from both committing, but it does not prevent an old leader from thinking it is leader and acting on external systems that have no idea a quorum exists. The lock service is consistent; your S3 bucket, your payment gateway, and your file system are not participants in the protocol.
The fix is a fencing token: the lock service hands out a monotonically increasing number with every grant, and every write to the protected resource carries it. The resource remembers the highest token it has seen and rejects anything lower. This moves the arbitration to the resource, which is the only place it can be correct.
You usually get the token for free: ZooKeeper's zxid and
sequential znode number, etcd's revision or lease ID, or a
version column you compare-and-swap on in your own database.
This is also the honest answer to the long-running argument about
Redis-based distributed locks: a multi-node Redis lock relies on bounded
clock drift and bounded process pauses, and neither is guaranteed — so if
you propose one, be ready to say what happens during a 30-second GC pause,
and carry a fencing token so the answer is "nothing bad".
Why you should almost never implement consensus yourself
The happy path of Raft is a weekend project. The parts that take years are the ones that only show up under failure:
- Persistence correctness.
currentTermandvotedFormust be fsynced before you reply, or a crash-restart lets a node vote twice in one term and you elect two leaders. This bug is invisible in testing and unrecoverable in production. - Membership changes. Adding or removing a node while the cluster is live requires joint consensus or strict single-node changes; get it wrong and you create two disjoint majorities.
- Log compaction and snapshots. Logs grow forever otherwise, and installing a snapshot on a lagging follower is a whole second protocol.
- The read path. As above — the naive implementation quietly serves stale reads.
- Verification. Production implementations are TLA+-specified and tested with deterministic fault injection (Jepsen, FoundationDB-style simulation). Consensus bugs are silent, and they lose committed data.
The correct engineering answer is: use etcd, ZooKeeper, or Consul; or use a database that already embeds a verified implementation (Spanner, CockroachDB, YugabyteDB, TiDB, Kafka's KRaft). Better still, design so you need consensus in as few places as possible — one small, well-understood coordination layer that everything else defers to.
Recognizing it in an unseen problem
- The prompt says "exactly one", "only one node should", "elect", "must not run twice", or "who owns this partition" — those are all leader election in disguise.
- Any design with a single writer, a primary, or a coordinator has an implicit consensus dependency: ask yourself who decides who the primary is, and what happens if two nodes disagree.
- A naive design says "we'll use a lock in Redis." The follow-up is always the pause scenario. Have the fencing token ready before it's asked — it converts a shaky answer into a senior one.
- Distinguish from quorum replication: quorums give you consistency for a single key; consensus gives you an agreed ordered log, which is what you need for leadership, membership, and atomic commit.
- Distinguish from CAP: consensus systems are the CP corner made concrete — during a partition the minority stops. If the prompt cannot tolerate stopping, you need to move that data out of the consensus path entirely.
- Scope it explicitly. A good answer keeps consensus on a small amount of metadata (leases, shard maps, config) and keeps the bulk data out of it, because a consensus group's throughput is bounded by a majority round trip.