Skip to content

Consensus & replication · 3 of 6

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

  1. Why not wait for every replica on each write? What does that cost in latency and availability?
  2. Some stores accept a write on other nodes when the home replicas are unreachable. What does that do to the overlap guarantee?
  3. 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.

Last updated: Research paper

Diagrams are our own simulations: the timings, rates and counts in them are illustrative, not measurements. Captions are original wording.