Cruxly › System design › Foundations of Data Systems

Distributed Consensus

getting several machines to agree on one thing, once, even when some fail

Every design in this track that needed "a coordination service" or "leader election" or "the source of truth for who owns this partition" was quietly depending on a machine solving this problem underneath. This is what's actually inside that box.

The problem it solves

Several machines must agree on one value (who the leader is, the next log entry, whether a lock is held) while machines crash and messages get delayed or lost.

Shortcut	What goes wrong
One machine decides	A single point of failure again
Every machine decides alone	They disagree once they see events in a different order
Consensus: a majority agrees	Safety: never two different answers to the same question

A protocol that is sometimes unavailable but never wrong is correct. One that is always available but sometimes gives two nodes different answers is not consensus.

Use it for small shared state that everything depends on: leader election, lock ownership, cluster membership, the position of a replicated log.

One group is not a general-purpose database. Every write costs a round trip to a majority and goes through one leader, so a single Raft cluster (etcd, ZooKeeper) holds a small amount of control-plane state. Spanner, CockroachDB, TiKV/TiDB and YugabyteDB run one consensus group per shard, thousands of them, and scale by adding groups.

How it works, at the depth an interview needs

Raft is the protocol to know by name and shape. Paxos solves the same problem but is older and famously harder to explain correctly. Raft was designed to be understandable, which is why it won in practice.

Part	How it works
Roles	Each node is a leader, follower or candidate. There is at most one leader per term (an epoch number that only goes up). A term can have zero leaders (a split vote) but never two
Election	A follower that hears nothing from a leader for a randomised timeout becomes a candidate, increments the term and asks everyone for votes. A node votes for at most one candidate per term, first-come-first-served, and only if the candidate's log is at least as up to date as its own (higher last term, or same last term and at least as long). A majority of votes wins. The random timeout stops every follower from becoming a candidate at once and splitting the vote every time
Replication	Only the leader accepts writes. It appends each write to its log and sends it to followers. Once a majority have durably stored it, an entry from the leader's current term is committed: the leader applies it, then acknowledges the client. Entries left over from earlier terms are never committed by counting replicas; they commit only when a current-term entry after them does (Raft paper, section 5.4.2). Followers that fall behind get the missing entries backfilled

Why a new leader never loses committed data (two facts, not one):

Majorities overlap. A committed entry is on a majority and any election needs a majority, so at least one voter holds every committed entry.
The election restriction. That voter refuses any candidate whose log is less up to date, so only a candidate holding every committed entry can win.

Overlap alone guarantees that some voter has the entry. The restriction guarantees the leader does. Say both if pushed.

Reads need care too. A deposed leader that doesn't know it yet can serve stale reads. Linearizable reads need a ReadIndex round (confirm leadership with a majority before answering) or a leader lease. ZooKeeper reads aren't linearizable by default; a client calls sync() first.

What it costs

Cost	What to say
Latency	Every write needs a round trip to a majority before the ack. The cost follows the slowest node in the first majority that responds, not the average
Odd node counts	3 nodes need 2 and tolerate 1 failure. 4 need 3 and also tolerate 1, so you pay for an extra machine for nothing. 5 tolerate 2. Four is strictly worse than 3 or 5
No scaling	Within a group every write goes through one leader and a majority round trip, so throughput is capped. Systems shard consensus: one group per range of data (Spanner, CockroachDB, TiKV). A standalone service (etcd, ZooKeeper, Consul) is the single-group case: right for election results and config, wrong for bulk application data
Partitions	A leader cut off from the majority can't commit anything. The minority side stalls, correctly, rather than accepting writes that would create two histories. This is CAP's "choose C over A during a partition" made concrete, a stronger answer than reciting CAP by name

When it's the wrong answer — and where it already showed up in this track

Question	If yes	If no
Can a shard key or ownership rule avoid cross-node agreement?	Restructure. No consensus needed	Go to the next question
Is losing one acknowledged write on failover unacceptable?	Consensus-backed replication (rare)	Single-leader replication

First, restructure. The seat-booking exercise elsewhere in this track rejects a distributed lock service for hold-acquisition. It partitions by event so acquisition is a single-partition conditional write: "a lock service is a worse version of this with an extra failure mode." Consensus is expensive and heavy to operate, so first ask whether a shard key, or a different owner for the state, removes the need for agreement.

Not the default for your primary store. Single-leader async replication (covered elsewhere in this track) skips the majority ack on every write. The narrower failure mode: a failover can lose the last few unreplicated writes, in exchange for lower write latency. The gap is smaller than it sounds, since majority-ack replication inside one region costs about the same as semi-synchronous replication. Safe failover still needs consensus somewhere: Patroni uses etcd to decide who the primary is, so two nodes never both think they are. Consensus-backed replication (Raft systems like etcd, or "multi-Paxos" systems like Spanner's underlying layer) is for when losing even one acknowledged write on failover is unacceptable. That is rare, so name it as the trigger instead of defaulting to it.

The right call:

Electing a leader among your own stateful nodes.
Cluster configuration and membership.
A real distributed lock with fencing tokens, not "a row in a database with a TTL", which has its own races.
Any "assume every node agrees on X": the interviewer will ask "how", and "a small Raft-based coordination service holding that one piece of state" is a complete, specific answer.

How to say it in the interview

"I won't implement Raft in an interview and no one expects me to. What I need is the shape of the guarantee it gives — one agreed value, surviving a minority of failures, at the cost of a round trip per decision — and where in my design I'm relying on that guarantee versus where I've avoided needing it."

Checklist

Defined safety (never two different answers to the same decision) as the actual point of consensus
Named Raft specifically and said why it displaced Paxos in practice
Explained commitment as 'a majority durably stored it,' not 'the leader wrote it'
Stated why majorities overlapping is the mechanical reason the protocol is safe
Knew that 4 nodes tolerates the same 1 failure as 3, making an even count strictly worse
Said one consensus group doesn't scale, and that real databases shard consensus across many groups
Connected a network partition to unavailability-not-wrongness, more specific than reciting CAP
Tried restructuring the problem (a better shard key) before reaching for a lock service
Named the actual trigger for consensus-backed replication instead of defaulting to it

Practice this interactively