Agreeing with the majority (quorums)

A store keeps three copies of a value. A write is saved on two, and a read asks two. The interviewer asks: "Can the read see old data? What if one copy is down?" A weak answer says "they agree". A strong answer counts the copies, the saves and the reads, and states the cost. SDE-3 candidates also say when the answer can still be wrong.

A village keeps land records in three offices. A change is saved when 2 offices have it. A reader asks 2 offices and trusts the newest page. Two groups of 2 offices out of 3 always share one office, so the reader meets the change.

In lesson 39 one leader took all writes. Here one server, the coordinator, sends each request to all copies and counts the answers.

• N is the number of copies of one value.
• W is the number of copies that must confirm a write before the client hears "saved".
• R is the number of copies that must answer a read. The newest answer wins.

Each value has a version, a number that rises with every write. Assume one writer changes a value at a time.

A quorum is a group of copies large enough to meet every other such group. The rule is R + W > N. A write is on W copies, so at most N - W copies are behind. If R is more than N - W, a read meets a copy with the new value.

A majority is more than half: N / 2 rounded down, plus 1. It is 2 for N = 3 and 3 for N = 5. With W = R = majority the rule holds, and N - majority copies may be down: 1 for N = 3, 2 for N = 5.

For N = 3, a request waits for the W-th or R-th fastest answer:

• W = 2, R = 2: balanced. One copy may be down.
• W = 3, R = 1: fast reads. One copy down stops writes.
• W = 1, R = 3: fast writes. One copy down stops reads.
• W = 1, R = 1: fastest, but reads can be old.

The rule is not strong consistency (lesson 47) in every case: a read during a write may see either value.

SwadKart keeps an order status on three copies: A, B and C. Order 77 moves from "cooking" (version 6) to "on the way" (version 7).

Assumptions (made up to teach with): A answers in 2 ms, B in 3 ms, C in 40 ms. Each copy works 99.9% of the time (lesson 4), independently. A month has 30 x 24 x 60 = 43,200 minutes.

Step 1: W = 2, R = 2. The client hears "saved" at 3 ms. C holds version 6 until 40 ms. A read asks {A, B}, {A, C} or {B, C}. Each pair has A or B, so it sees version 7. Check: 2 + 2 = 4 > 3. So no.

Step 2: W = 1, R = 1. "Saved" comes at 2 ms. A read that goes to C gets version 6. Here 1 + 1 is not more than 3.

Step 3: speed. W = R = 2: 3 ms each. W = 3, R = 1: write 40 ms, read 2 ms. W = 1, R = 3: write 2 ms, read 40 ms.

Step 4: failures. W = 3 needs all copies up: 0.999 to the power of 3 = 0.997003. It fails 0.002997 x 43,200 = 129.5 minutes a month. W = 2 fails when 2 or 3 copies are down: 1 - (0.997003 + 3 x 0.999 x 0.999 x 0.001) = 0.000003 (rounded), about 7.8 seconds.

A quorum solves old reads when a copy is slow or down. It costs a message to every copy, and requests fail when too many copies are down. I would change it when reads far outnumber writes (R = 1, W = N), or when old data is fine.

"A quorum means all copies agree." No. Copy C held version 6 for 40 ms.

"R + W > N is strong consistency." Not always. A read during a write can see either value.

1. What do N, W and R mean? Which rule makes a read meet the newest write?
2. N = 5, W = 4, R = 2. Copy times are 5, 8, 10, 30 and 60 ms. (a) Is R + W > N true? (b) How many copies may be down for writes, and for reads? (c) How long does a write take, and a read?
3. N = 3, W = 1, R = 1 shows old balances. Times are 2, 3 and 40 ms. What do you change? What does it cost?