Loading page…
Write to W of N replicas, read from R, return the newest version, repair the stale replicas the read touched, and fail when too few replicas answer.
A leaderless store keeps every key on N replicas. A write counts as done once W of them acknowledge it, a read asks R of them and returns the newest version it hears. When R + W > N, the R replicas a read asks and the W replicas that took the last successful write must share at least one replica, so the read sees that write (Day 1, section 12.1; Week 1, Day 2, section 2.3). And when a read notices a replica that answered with an old version, it writes the newest one back to it: read repair. Build the lesson's QuorumStore (section 12.2) as a synchronous coordinator.
QuorumStore(replicas, w, r), where replicas is the key's N replicas in preference-list order (Given's Replica):
| Method | Does |
|---|---|
| constructor | raises ValueError unless 1 <= w <= N and 1 <= r <= N |
put(key, value) |
picks the new version, sends it to every replica, returns the version (an int). Raises QuorumError when fewer than R replicas answer the version read or fewer than W acknowledge the write |
get(key) |
returns the newest value among R answers (None if none of them has the key), after read-repairing the replicas that answered with an older version or nothing. Raises QuorumError when fewer than R replicas answer |
The model's rules, which the tests check:
get and the version read in put): ask the replicas in list order, skip any that raises Unreachable, and stop as soon as R have answered. "Not found" (None) is an answer. Fewer than R answers: raise QuorumError.put first reads R replicas as above and takes version = 1 + the highest version among them (1 if none has the key), like the lesson's write. If that read fails, nothing is written. Then it sends (version, value) to every replica in the list; each one that doesn't raise Unreachable is an acknowledgement. Fewer than W: raise QuorumError. Replicas that did take the write keep it: there is no rollback.get returns the value with the highest version among the answers (the first one listed, if two answers share a version), and before returning, writes that (version, value) to every replica that answered with a lower version or nothing. Replicas that weren't asked are not touched. A repair that hits a down replica is skipped.Replica.put already keeps the higher version, so a repair or a late write never moves a replica backwards.In JavaScript and TypeScript the class is new QuorumStore(replicas, w, r) with put(key, value) and get(key); a replica's get returns [version, value] or null, a missing key is null, and a bad w or r throws a RangeError.
What's left out: there's one coordinator and every key lives on the same N replicas (no hash ring placing keys on different replicas: that's Week 1's consistent-hashing lab). Versions are plain integers from a read-before-write, so two concurrent writers can pick the same version (no vector clocks: that's the previous lab). Quorums are strict: no sloppy quorums and no hinted handoff (a follow-up). A real coordinator sends to all N replicas in parallel and uses the first R or W replies; here the "first" replies are the first reachable replicas in list order, and repair runs inside get instead of in the background. Even with R + W > N, the lesson's caveats stand: a write that failed its quorum can still be read, and a quorum read is not linearizable on its own.
Write your code, then run 3 example tests and 9 hidden tests. Each run is limited to 8 seconds: an infinite loop gets stopped and the runtime restarts, your code stays.