Step 1 · The pattern
Three copies of every key
The database keeps N = 3 copies of each key on different machines. A write goes to all three, and a read can be answered by any of them. If one machine dies the data is still there.
- write
- read
- confirmed / current
In short
Quorum reads & writes: how it works and how it breaks
A leaderless database keeps N copies of every key on different machines and lets you choose two numbers. W is how many replicas must store a write before it is confirmed. R is how many replicas a read asks before it answers. Waiting for all N is safe but slow: every request is as slow as the slowest replica, and one dead machine stops everything. Waiting for one is fast, but a confirmed write may sit on a single replica while a read asks a different one and returns the old value. The useful rule is R + W > N. Then the replicas a read asks and the replicas a write reached must share a machine, so one answer carries the newest version and the read keeps it. With three replicas, W = 2 and R = 2 does this and still tolerates one slow or failed replica.
How this comes up in interviews
"A leaderless store keeps several copies of each key. A write is confirmed, yet the next read returns the old value. How do you choose how many replicas reads and writes wait for?"
Then they ask
- Why not wait for every replica on each write? What does that cost in latency and availability?
- Some stores accept a write on other nodes when the home replicas are unreachable. What does that do to the overlap guarantee?
- Does R + W > N give you compare-and-set or uniqueness checks? What can still go wrong with concurrent writes?
A strong answer covers
- N is the number of copies, W is how many replicas must store a write before it is confirmed, and R is how many a read asks before it answers.
- Waiting for all N makes every request as slow as the slowest replica, and one dead machine stops everything.
- Waiting for one is fast, but a confirmed write may sit on one replica while a read asks a different one.
- With R + W > N, the replicas a read asks and the replicas a write reached share a machine, so one answer carries the newest version.
- The read needs a way to tell which answer is newer, such as version numbers or vector clocks.
Points to cover, not a script. Say them in your own words and tie them to a system you have worked on.
On one page: the track cheat sheet.
Sources: Dynamo: Amazon's highly available key-value store (SOSP 2007) ↗ · Werner Vogels: Amazon's Dynamo (All Things Distributed) ↗ · Report a problem
Diagrams are our own simulations: the timings, rates and counts in them are illustrative, not measurements. Captions are original wording.