Replication, quorums and consensus (Raft)

Why it matters

Every durable, highly available service keeps several copies of its data, and many subtle distributed bugs live in how those copies are updated and how a new leader takes over. Consensus also underlies the coordination services (etcd, ZooKeeper) that other systems depend on. For distributed-systems roles you should be able to explain Raft from memory; for other roles, know what each replication style guarantees and where it breaks.

Core ideas

Three replication styles.

• Single leader: all writes go to one node, which ships a log to followers. Ordering is simple; failover and stale follower reads are the hard parts. With asynchronous replication, failover can lose acknowledged writes.
• Multi-leader: several nodes accept writes (often one per region) and exchange them asynchronously. Good for local write latency and offline clients; conflicts are inevitable and need a resolution rule.
• Leaderless: clients write to and read from several replicas directly; read repair and background anti-entropy converge them.

Quorums. With N replicas, writes waiting for W acknowledgments and reads querying R replicas, R + W > N means every read set intersects every successful write set, and that is all it promises. It does not give linearizability: a sloppy quorum may write outside the usual N nodes; concurrent writes resolved by timestamps can silently drop one; a write that reached fewer than W nodes is reported as failed but not rolled back, and may be read later; a read concurrent with a write can return the new value to one client and the old value to the next; restoring a replica from a stale copy breaks the counting argument.

Consensus makes a group agree on one sequence of commands, which turns a deterministic service into a replicated state machine. With 2f + 1 replicas it tolerates f crashes, because any two majorities overlap.

Raft in five rules (the paper's Figure 2 has the exact version):

1. Terms are numbered epochs with at most one leader each. Any message carrying a higher term makes the receiver adopt it and step down.
2. Election: a follower that hears nothing for a randomized timeout becomes a candidate, increments its term and requests votes. A server votes at most once per term, and only for a candidate whose log is at least as up to date as its own (compare last log term, then last index). Randomized timeouts make repeated split votes unlikely.
3. Log matching: AppendEntries carries the index and term of the preceding entry. A follower rejects it unless it holds a matching entry; the leader retries from earlier positions until they agree, and the follower then replaces its conflicting suffix with the leader's entries. So if two logs share an entry's index and term, they are identical up to it.
4. Commitment: a leader marks an entry committed once a majority stores it and it belongs to the leader's current term; earlier entries are committed indirectly. Counting replicas of an older-term entry is not enough, because a different leader could still overwrite it.
5. Persistence: the current term, the vote and the log reach stable storage before a server answers, or a restarted server could vote twice or forget acknowledged entries.

The election restriction plus the commitment rule give leader completeness: every future leader already holds every committed entry.

Ad hoc failover is dangerous. A monitor that promotes a follower when the leader stops answering can create two leaders if the old one was only slow. Terms or epochs, a majority vote and fencing of the old leader prevent split brain.

Common misconceptions

• "R + W > N gives strong consistency." It gives overlap, not linearizability, for the reasons listed above.
• "Replication protects data from mistakes." A bad write or delete replicates as faithfully as a good one; replicas protect against machine loss, not corruption or operator error.
• "Raft commits an entry as soon as a majority has it." Only entries of the current term; older ones are committed once a later current-term entry is.
• "More replicas are faster and safer." They raise durability but enlarge the quorum and the commit latency; an even count adds cost without tolerating another failure.
• "An up-to-date follower can serve linearizable reads." It cannot know it is up to date without contacting the leader or relying on a time-based lease.

How to approach it

Read DDIA Ch. 5 for the styles and quorums, then the Raft paper through Section 5 with Figure 2 beside you. Before coding, trace scenarios in the RaftScope visualization: kill the leader, partition a minority, restart a stale node. If you target distributed-systems roles, implement the 6.5840 Raft lab; nothing else exposes the rules as quickly. Graduates should explain elections and majorities. Mid-level candidates should walk through log repair, the commit rule and quorum pitfalls. Senior candidates should discuss read paths, membership changes, placement across zones and how consensus latency shapes the rest of the design.