Quorum Consensus

Overview

A replicated database keeps copies of each piece of data on several machines so that it survives losing one. Every read and write then has to answer a question: how many copies must take part? Waiting for all of them is safe but slow, and one dead machine stops everything. Waiting for one is fast, but a read may reach a copy that has not seen the latest write yet.

A quorum is the middle ground. A write waits until W of the N copies confirm it, and a read asks R copies and keeps the newest answer. If W + R is greater than N, every read shares at least one copy with every successful write, so it cannot miss that write.

Amazon's Dynamo paper (2007) described this design for a key-value store, and Cassandra, Riak and Voldemort follow it. Consensus protocols such as Raft and Paxos use a related idea, the majority, for a different job. This chapter covers both, the arithmetic behind them, and the failure cases where the overlap rule stops protecting you.

What you will be able to do

• Explain why W + R > N makes reads meet writes, and why W + R = N does not.
• Choose N, W and R for a read-heavy or a write-heavy workload, and say what each choice costs in latency and availability.
• Walk through what happens when replicas are down, slow, or receive only part of a write.
• Explain why quorum reads and writes are still not linearizable, and what closes the gap.
• Tell a Dynamo-style quorum from a Raft or Paxos majority, and set Cassandra's consistency levels across datacenters.

Key concepts

• N, W and R
• W + R > N
• Tuning for reads or writes
• Sloppy quorums
• Hinted handoff
• Read repair
• Anti-entropy and Merkle trees
• Majority quorums in Raft and Paxos
• Cassandra consistency levels

Interview questions

• What do N, W and R mean, and why does W + R > N make a read see the latest write?
• You run N = 3. How would you set W and R for a read-heavy catalog, a write-heavy event log and a general workload?
• Why is a Dynamo-style system with W + R > N still not linearizable, and what would you add?
• What is a sloppy quorum, and why does it weaken W + R > N?
• How do hinted handoff, read repair and anti-entropy differ, and why do systems run all three?
• How does a Raft or Paxos majority differ from a Dynamo-style quorum?
• A Cassandra cluster has a replication factor of 3 in each of two datacenters. What does QUORUM need, what happens when one datacenter goes offline, and what would you use instead?
• A write at QUORUM timed out. Did it happen, and what should the client do?

More System Design topics

• Polling vs WebSockets vs Webhooks
• Price Comparison Engine
• Price Tracking Service
• Primary-Replica vs Peer-to-Peer
• Proxies
• Proximity Service
• Raft Consensus
• RAG System (Retrieval-Augmented Generation)
• Rate Limiter
• Rate Limiting
• Read Repair
• Read-Heavy vs Write-Heavy Systems