🎓 A1Learner
🔍
0 of 42 lessons completed

Copies and Quorums

A quorum is the smallest number of copies that must respond before a write or a read counts as done. This lesson deep-dives one part of the design, keeping copies of each range and asking quorums of them.

A write lands on every copy with a rising version

Each put writes all copies and raises the version counter. The printout shows every copy holding the same value and version.

copies = [{"value": None, "version": 0}, {"value": None, "version": 0}, {"value": None, "version": 0}]

def put(value):
    for copy in copies:
        copy["value"] = value
        copy["version"] += 1

put("Ana")
put("Ana Lee")

for i, copy in enumerate(copies):
    print("copy", i + 1, "holds", copy["value"], "at version", copy["version"])

A write counts at W confirmations, with one copy down

One copy is down and never confirms the write. The write still counts as done because the other copies reach W.

alive = [True, True, False]
copies = [{"value": "Ana", "version": 1}, {"value": "Ana", "version": 1}, {"value": "Ana", "version": 1}]
confirmations = 0

for i in range(3):
    if alive[i]:
        copies[i]["value"] = "Ana Lee"
        copies[i]["version"] += 1
        confirmations += 1

print("confirmations:", confirmations)
print("write counts as done:", confirmations >= 2)
for i, copy in enumerate(copies):
    print("copy", i + 1, "holds", copy["value"], "at version", copy["version"])

A read asking R copies takes the newest version

One copy is stale and still holds the older version. The read asks two copies and takes the answer with the highest version.

copies = [("copy A", "Ana Lee", 2), ("copy B", "Ana", 1), ("copy C", "Ana Lee", 2)]
asked = copies[:2]
best = asked[0]

for entry in asked:
    print(entry[0], "reports version", entry[2])
    if entry[2] > best[2]:
        best = entry

print("read returns:", best[1], "at version", best[2])

Example

copies = [{"value": "Ana", "version": 1}, {"value": "Ana", "version": 1}, {"value": "Ana", "version": 1}]
alive = [True, True, False]
confirmations = 0

for i in range(3):
    if alive[i]:
        copies[i]["value"] = "Ana Lee"
        copies[i]["version"] += 1
        confirmations += 1

print("write confirmations:", confirmations)
print("write counts as done:", confirmations >= 2)

asked = [copies[1], copies[2]]
best = asked[0]
for copy in asked:
    if copy["version"] > best["version"]:
        best = copy

print("read returns:", best["value"], "at version", best["version"])
print("W + R > N:", 2 + 2 > 3)

Key points

  • Copy: one stored replica of a range of keys, kept on its own server.
  • N: the number of copies kept for each range, and N is 3 in this design.
  • W: the number of copies that must confirm a write, and W is 2 in this design.
  • R: the number of copies a read asks, and R is 2 in this design.
  • Overlap rule: W + R is 4, and 4 is more than N at 3, so a read always meets the latest finished write on at least one copy.
  • Version: a plain counter on each value that rises with every write, so the newest copy can be told from a stale one.

In this example, one copy is down during the write and stale during the read, yet the write still counts as done and the read still returns the newest value. The two copies the read asks overlap the copies the write reached.

Note

a write that reaches fewer than W copies does not count as done, even if one copy holds it.

Try it Yourself

Edit the code, then press Run.

Running is simulated

Exercise

With N = 3, W = 2 and R = 2, why does a read always meet the latest finished write?