CSE Roadmap

Common tier · about 4 hours · 8 parts

Part 6 of 8 · 4 min read

Quorums

Choosing how many replicas must confirm a write and answer a read.

Think of a bank with five branches that all hold the record of your balance. If a deposit must be recorded at 3 branches and a balance check must ask 3 branches, then any check will meet at least one branch that saw the deposit, because 3 and 3 add up to more than 5.

Quorum (n, w, r)

With n replicas for each item, a write must be confirmed by w of them and a read must ask r of them. If w + r > n, then every read set overlaps every write set in at least one node, so a read should see the latest successful write.

Example: n = 5, w = 3, r = 3. Since 3 + 3 = 6 > 5, a read of 3 replicas includes at least one that has the latest write.

The writes are always sent to all n replicas in parallel. The numbers w and r decide only how many answers the client waits for.

A common choice from the book: make n odd (3 or 5) and set w = r = (n + 1) ÷ 2, rounded up. Reads and writes need a majority. Other choices are possible. A workload with few writes and many reads might set w = n and r = 1. Reads are fast, but one failed node makes every write fail.

What the numbers tolerate:

n w r w + r > n Failed nodes tolerated for writes Failed nodes tolerated for reads
3 2 2 yes (4 > 3) 1 1
5 3 3 yes (6 > 5) 2 2
5 5 1 yes (6 > 5) 0 4
5 1 5 yes (6 > 5) 4 0
5 2 2 no (4 ≤ 5) 3 3

With w + r ≤ n, reads and writes still go to n nodes but need fewer answers. The result is lower latency and higher availability, but a higher chance of reading stale values. There can be more than n nodes in the cluster, since each value lives on only n of them. That allows partitioning (module 4).

Limits of quorums. Even with w + r > n, the book lists cases where stale values can be returned:

  • A sloppy quorum (next section) may put the writes on different nodes from the reads.
  • Two writes at the same moment: the only safe solution is to merge them. If LWW picks a winner by timestamp, clock skew can lose writes.
  • A write at the same time as a read may reach only some replicas, so it is not clear whether the read returns the old or the new value.
  • A write that succeeded on some replicas but fewer than w is reported as failed, but is not rolled back. A later read may or may not return it.
  • A node with a new value fails and is restored from a replica with an old value, so the count of nodes holding the new value falls below w.
  • Timing edge cases even when everything works.

The book's advice is not to take n, w and r as absolute guarantees. They adjust the probability of stale reads. Dynamo-style databases suit uses that tolerate eventual consistency. In particular, you usually do not get read-your-writes, monotonic reads or consistent prefix reads (module 2). Stronger guarantees need transactions or consensus.

Monitoring. For a leader-based database, lag is the difference between positions in the log. In a leaderless database there is no fixed order of writes, so lag is harder to measure. With read repair only, an item rarely read can be very old on a stale replica. The book would like staleness measures in the standard metrics, since it is important to be able to quantify "eventual".

A worked example. n = 5, w = 3, r = 3. A write succeeds on nodes 1, 2, 3. A read asks nodes 3, 4, 5. Node 3 has the new value; nodes 4 and 5 have the old one. The client sees one new and two old values with different versions, takes the highest version, and does read repair on 4 and 5. Now suppose two nodes fail: nodes 1 and 2. Writes still need 3 of the 3 remaining (3, 4, 5): possible. A third failure makes writes impossible (only 2 left).

Check yourself:

  • With n = 7 and w = 4, what is the smallest r that satisfies w + r > n?
  • Why can quorum reads still return old values?