One copy of the data is one machine away from losing it, so databases keep several. That raises a question a single copy never asks: when copies can disagree, which one do you believe? A quorum is the answer most distributed stores give: a write and a read each talk to enough copies that they are sure to meet.
Keeping copies
There are two ways to keep several copies in step.
- Leader-based. One copy, the leader, takes every write and ships it to the others. Reads and writes are simple, and if the leader dies, the others must agree on a new one: an election, run by a consensus protocol such as Raft or Paxos. PostgreSQL and MySQL are leader-based too. PostgreSQL doesn't hold the election itself: a failover tool such as Patroni (which keeps its vote in etcd) uses consensus to pick the new leader. MySQL's Group Replication runs its own, on a Paxos-based protocol.
- Leaderless. Any copy can take a write. The client, or a coordinator, sends each write to several copies and each read to several copies, and compares. Dynamo, Cassandra and Riak work this way, and it's what most of this chapter is about. The last section covers how leader-based systems choose a leader.
Leaderless stores are described by three numbers.
| Setting | Meaning |
|---|---|
| N | The number of copies (replicas) of each piece of data |
| W | How many copies must have a write before it is acknowledged |
| R | How many copies a read asks, taking the newest answer |
The quorum rule
A write reaches at least W copies, and a read asks R. If R + W is greater than N, the two groups must share at least one copy, so a read always reaches a copy that has the latest acknowledged write. If R + W is not greater than N, a read can land entirely on copies that haven't received the write yet.
The lab sends one write to three copies over links of different speed, and reads back fifty milliseconds after it is acknowledged. Try the settings, and watch which copies the write has reached when the read arrives.
When a replica is down
The reason to keep copies is that one can fail. A quorum is a count of replicas that must be up, and the settings decide what a failure takes with it.
Copy 3 is down in the lab, and the write is acknowledged after W copies have it.
The common choice is a majority for both, R=2 and W=2 of three. It tolerates one failure, and every read overlaps the latest acknowledged write. Needing all the copies for either one turns any failure into an outage for that kind of request. The overlap still isn't the strong, single-copy behaviour of the Consistency chapter: a read that overlaps a write still in progress can return the new value, and the next read the old one, unless each read writes the newest value back to the copies it asked before it answers. Concurrent writes settled by clock timestamps can also lose one. A replica that comes back has missed the writes made while it was away. The copies that took those writes kept them as hints and hand them over when it returns (hinted handoff); whatever the hints missed is fixed by reads that find it behind (read repair) and by background comparison between copies (anti-entropy).
The price of waiting
A write sent to five copies is acknowledged when the W fastest have it, so its latency is the W-th fastest copy's. A read waits for R answers: sent to every copy, it takes the R-th fastest; sent to just R copies, the slowest of them.
Here the three copies answer after about 25, 115 and 415 ms, and the page allows 150.
Leaders and consensus
Quorums solve reading and writing without a leader. When a system does want one, for example to order every write, the copies have to agree on who it is, and on what has been written. That's consensus, and Raft is the protocol most systems use to teach it and to run it. Each node is a follower, a candidate or the leader, and time is divided into numbered terms.
A follower that hears nothing from a leader for a random time becomes a candidate, adds one to its term and asks the others for votes. A node gives one vote per term, and wins on a majority. A majority is a quorum again, so two candidates can't win the same term. The leader then sends heartbeats to keep the others from starting an election of their own.
A leader writes each command to its log and sends it to the followers. It's committed when a majority has stored it, and only then is it safe to act on. (One fine point: a new leader counts a majority only for entries from its own term; older entries become committed along with the first new one.)
The commit rule is what makes a leader's crash safe.
A system of 2f + 1 nodes keeps working through f failures: three nodes survive one, five survive two. That is why clusters have an odd size.
The lab leaves out what a real implementation needs: changing the set of nodes, compacting the log into snapshots, writing to disk before replying, confirming leadership before serving a read, and the checks that stop a node that rejoins from disrupting the cluster. Some systems use consensus only for small things, like who the leader is and what the configuration is. Others, like Spanner, CockroachDB, TiKV and etcd, put every write through Raft or Paxos: with a leader in place, a write costs one round trip to a majority. etcd keeps one log for everything; the others keep a separate log for each range of keys, which spreads the writes over many leaders.
Deep dives
| They ask | What to say |
|---|---|
| Strong or eventual consistency | With strict quorums, R + W greater than N means a read overlaps the latest acknowledged write. That alone isn't linearizable: reads must also repair stale copies before answering. Sloppy quorums, last write wins with skewed clocks, and writes that failed partway can still return old or lost values. Smaller quorums are faster and can be stale |
| A node is down for a while | Writes go to the other copies, and the node is repaired when it returns. Sending writes to stand-in nodes outside the N instead (a sloppy quorum, whose stand-ins hand the writes back later) keeps writes working but gives up the overlap |
| Two clients write the same key | Concurrent writes conflict: last write wins by timestamp, or keep both and merge |
| Why an odd number of replicas | Four replicas tolerate one failure, like three, and cost more |
| A write must be on three data centers | A quorum across regions, and the latency of the slowest region you wait for |
| How is a leader chosen | Votes from a majority, so a split cluster has at most one leader |
In the wild
The ideas in this chapter, and where you'll meet them in real systems and interviews:
| Idea | Where you'll meet it |
|---|---|
| Tunable R, W and N | Cassandra's consistency levels (ONE, QUORUM, ALL) |
| Leaderless replication | Amazon's Dynamo paper, and Riak |
| Consensus and leader election | Raft in etcd and Consul, and Paxos in Google's Chubby |
| Majority votes | A ZooKeeper ensemble of three or five nodes |
Your practice
Inkwell Sessions keeps who is signed in, and one copy is down for a few seconds mid-run. Keep every request working through the outage, never return an old session, and then give the store only the replicas it needs.