Leaderless replication and quorums: N, R and W

A key lives on three replicas, a write waits for two of them to confirm, and a read asks two. Because 2 + 2 is more than 3, the replicas a read asks always include one that the last acknowledged write reached. Leaderless replication drops the leader altogether: a client, or a coordinator acting for it, sends every write to all N replicas of a key and counts it as done once W of them confirm, and a read waits for R answers and keeps the newest version it sees. These quorums are what make the copies agree: if R + W > N, every set of replicas a read asks shares at least one replica with every set a write reached. Stores in the style of Amazon’s Dynamo, such as Cassandra, work this way, and they keep answering when a replica is slow or down, because no single server has to reply.

Reads and writes that overlap

The Dynamo paper defines R and W as the minimum numbers of replicas that must take part in a successful read and a successful write, notes that R + W > N gives a quorum-like system, and observes that the latency of each request is set by the slowest of the R or W replicas it waits for; the common configuration there was N = 3, R = 2, W = 2 (Dynamo). Cassandra states the same rule as consistency levels, where QUORUM means a majority, n/2 + 1, of the replicas, and levels chosen with W + R greater than the replication factor make every acknowledged write visible to later reads (Cassandra). In the diagram, look for the replica that the write and the read share:

Step through the diagram’s write and read:

The quorum explorer below tries nine choices. A write reaches each replica after a random delay and is acknowledged once W replicas hold it; a read made right then asks R random replicas.

// A quorum explorer: for each choice of N, R and W, does every read meet every write, how many replicas may be
// down, and how often does a read right after an acknowledged write miss it? The write reaches each replica after
// a random delay of 0 to 40 ms and is acknowledged once W replicas hold it; the read asks R random replicas at
// that moment and takes the newest version it sees. Seeded, so every run prints the same; edit CHOICES and run it.
const CHOICES = [
  [3, 1, 1], [3, 1, 2], [3, 2, 1], [3, 2, 2], [3, 1, 3], [3, 3, 1],
  [5, 2, 2], [5, 3, 3], [5, 1, 5],
];
const TRIALS = 20000;

function mulberry32(seed) {
  return () => {
    seed = (seed + 0x6d2b79f5) | 0;
    let t = Math.imul(seed ^ (seed >>> 15), 1 | seed);
    t = (t + Math.imul(t ^ (t >>> 7), 61 | t)) ^ t;
    return ((t ^ (t >>> 14)) >>> 0) / 4294967296;
  };
}

function shuffled(items, random) {
  const out = [...items];
  for (let i = out.length - 1; i > 0; i--) {
    const j = Math.floor(random() * (i + 1));
    [out[i], out[j]] = [out[j], out[i]];
  }
  return out;
}

console.log('"down": how many replicas may be down while writes,');
console.log('or reads, still succeed.');
console.log(' N  R  W  overlap  writes   reads    stale reads');
for (const [n, r, w] of CHOICES) {
  const random = mulberry32(7);
  let stale = 0;
  for (let i = 0; i < TRIALS; i++) {
    const arrival = Array.from({ length: n }, () => 40 * random()); // ms after the write is sent
    const acked = [...arrival].sort((a, b) => a - b)[w - 1]; // the moment the W-th replica holds it
    const asked = shuffled([...arrival.keys()], random).slice(0, r);
    if (asked.every((k) => arrival[k] > acked)) stale++;
  }
  const overlap = r + w > n ? 'yes' : 'no';
  console.log(
    `${String(n).padStart(2)} ${String(r).padStart(2)} ${String(w).padStart(2)}  ${overlap.padEnd(7)}  ` +
      `${n - w} down   ${n - r} down   ${((100 * stale) / TRIALS).toFixed(1).padStart(5)} %`,
  );
}

"down": how many replicas may be down while writes,
or reads, still succeed.
 N  R  W  overlap  writes   reads    stale reads
 3  1  1  no       2 down   2 down    66.9 %
 3  1  2  no       1 down   2 down    33.8 %
 3  2  1  no       2 down   1 down    34.1 %
 3  2  2  yes      1 down   1 down     0.0 %
 3  1  3  yes      0 down   2 down     0.0 %
 3  3  1  yes      2 down   0 down     0.0 %
 5  2  2  no       3 down   3 down    30.2 %
 5  3  3  yes      2 down   2 down     0.0 %
 5  1  5  yes      0 down   4 down     0.0 %

Every row with R + W > N found the write every time, and every row without that overlap often missed it: two reads in three with R = W = 1. The other columns are the cost of each choice, since W = N stops writes when any replica is down and R = N does the same to reads. Strict quorums are the easy part. The interesting behaviour comes from what leaderless replication does when replicas fail:

• Sloppy quorumssloppy quorum: A quorum that, when a key's own replicas are unreachable, counts confirmations from the next healthy nodes instead, so the write still succeeds.: when a key’s own replicas are unreachable, the write goes to the next healthy nodes, so it still succeeds.
• Hinted handoffhinted handoff: A substitute node keeps a write meant for an unreachable replica, with a hint naming that replica, and hands the write over once the replica is back.: a substitute keeps such a write with a note of its rightful replica and hands it over later.
• Read repairread repair: A read that finds some of the replicas it asked holding an older version writes the newest version it saw back to them.: a read that sees stale replicas writes the newest version back to them.
• Anti-entropyanti-entropy: Replicas compare their data in the background, using trees of hashes, and copy whatever differs, so that they converge without waiting for reads.: replicas compare hash trees of their data in the background and copy whatever differs.

Overlapping quorums are still not linearisability: concurrent writes, failed writes and sloppy quorums all let reads see results that a single copy never would.

Choosing N, R and W, with numbers Pro: opens with a Pro, Premium or Ultimate pass