Quorums

R + W > N forces every read set to overlap the last write set; the rest of quorum design is choosing where to spend the latency.

SyntaxR + W > N (N replicas per key, W acknowledgements per write, R responses per read)

A quorum is an overlap rule. Keep N copies of each key. Count a write as done when W replicas acknowledge it. Answer a read from the first R replicas that respond. If R + W > N, the read set and the last write set cannot be disjoint, so the newest value is somewhere in those R responses — and version metadata, not the arithmetic, tells you which one it is.

Tuning

N buys durability and costs money. W and R move latency between the write path and the read path. Dynamo ran N=3, W=2, R=2 in production. Read-heavy work can use W=3, R=1: reads answer from the nearest replica, at the price of writes failing whenever any single replica is down. Write-heavy work can use W=1, R=3 and pay on every read. Cassandra exposes the choice per statement, and its named levels are shorthand for the arithmetic: QUORUM is floor(N/2)+1 across every datacentre, LOCAL_QUORUM is floor(RF/2)+1 inside the coordinator's own datacentre — the same sum without the cross-region round trip.

What a quorum does not give you

It is not a transaction: no atomicity across two keys, and no protection against a lost update unless the write is a compare-and-set. It is not linearizability either. Dynamo's sloppy quorum takes W acknowledgements from any W reachable nodes and uses hinted handoff to deliver the data to the real replicas later — excellent for availability, and it dissolves the overlap argument entirely. Read repair and anti-entropy are what actually make the copies agree.

Example

Example · javascript
// Quorum write: contact all N replicas, resolve as soon as W acknowledge.
// The remaining requests are deliberately NOT cancelled - those extra copies
// are what make the next read cheap and the next failure survivable.
function quorumWrite(replicas, key, record, W) {
  const N = replicas.length;
  if (W > N) throw new RangeError(`W=${W} cannot exceed N=${N}`);

  return new Promise((resolve, reject) => {
    let acks = 0;
    let failures = 0;
    let settled = false;

    for (const replica of replicas) {
      replica.put(key, record).then(
        () => {
          if (++acks === W && !settled) {
            settled = true;
            resolve({ acks: W, of: N });
          }
        },
        (err) => {
          // Once N - W + 1 replicas have failed, W acks are unreachable.
          if (++failures > N - W && !settled) {
            settled = true;
            reject(new Error(`quorum write failed: ${failures}/${N} down`, { cause: err }));
          }
        },
      );
    }
  });
}

// N=3, W=2: survives one replica being down, and with R=2 (2 + 2 > 3) every
// read set overlaps the write set by at least one replica.
await quorumWrite(replicas, "user:1042", { version: 7, name: "Ada" }, 2);

When to use it

  • Picking N, W and R for a key-value store where reads outnumber writes 50 to 1
  • Explaining why a write still succeeded with one of three replicas offline
  • Deciding between QUORUM and LOCAL_QUORUM for a multi-region Cassandra keyspace
  • Spotting that a counter increment needs a compare-and-set, not just a quorum write

More examples

Quorum read, version reconciliation, and read repair

Shows the half of quorum reads that the R + W > N formula leaves out: picking a winner and healing the laggards. Worth writing out in an interview when asked how an eventually consistent store ever converges, because read repair plus anti-entropy is the real answer.

Example · javascript
// The overlap rule guarantees the newest value is in the responses. Choosing
// it, and fixing the stale replicas, is your job.
async function quorumRead(replicas, key, R) {
  const results = [];
  await new Promise((resolve) => {
    let answered = 0;
    for (const replica of replicas) {
      replica.get(key).then(
        (v) => { results.push({ replica, value: v }); if (++answered >= R) resolve(); },
        ()   => { if (++answered >= R) resolve(); },
      );
    }
  });

  const present = results.filter((r) => r.value);
  if (present.length === 0) return null;

  // Highest version wins. This works only because writers bump a version the
  // storage layer owns - never a client wall-clock timestamp.
  const newest = present.reduce((a, b) => (b.value.version > a.value.version ? b : a));

  // Read repair: push the winner back to whoever answered with something
  // older. Fire and forget; the read has already been served.
  for (const r of present) {
    if (r.value.version < newest.value.version) {
      r.replica.put(key, newest.value).catch(() => {});
    }
  }
  return newest.value;
}

The arithmetic, with what each row costs you

Turns the formula into the two numbers people actually argue about: how many replicas may be down before writes stop, and before reads stop. Use it when sizing a cluster, and when someone proposes W=1, R=1 without saying that it is no longer a quorum.

Example · javascript
// N = 3 in every row. The failure column is what the arithmetic buys.
const configs = [
  // N  W  R   overlap?        survives            pays
  { N: 3, W: 3, R: 1 }, // yes  1 replica down -> writes stop   reads are local
  { N: 3, W: 2, R: 2 }, // yes  1 replica down, both paths      balanced (Dynamo)
  { N: 3, W: 1, R: 3 }, // yes  1 replica down -> reads stop    writes are local
  { N: 3, W: 1, R: 1 }, // NO   everything, until you read      stale reads
];

function describe({ N, W, R }) {
  return {
    overlapping: R + W > N,          // the quorum condition
    writeTolerance: N - W,           // replicas that may be down and writes still succeed
    readTolerance: N - R,            // replicas that may be down and reads still succeed
  };
}

console.table(configs.map((c) => ({ ...c, ...describe(c) })));
// W=1, R=1 is a perfectly reasonable choice - as long as somebody has said
// out loud that this key's reads may be stale.

Compare-and-set, because a quorum will not stop a lost update

The clearest demonstration that quorums are about staleness, not about conflicts. Reach for a conditional write whenever two clients can race for the same key: username claims, seat holds, one-time coupon redemption.

Example · javascript
// cassandra-driver. Two concurrent registrations for the same username both
// satisfy a LOCAL_QUORUM write and the second silently overwrites the first.
// A lightweight transaction (Paxos, so roughly four round trips) prevents it.
const { consistencies } = require("cassandra-driver").types;

async function claimUsername(username, userId) {
  const rs = await client.execute(
    "INSERT INTO usernames (username, user_id) VALUES (?, ?) IF NOT EXISTS",
    [username, userId],
    {
      prepare: true,
      consistency: consistencies.localQuorum,   // the normal write path
      serialConsistency: consistencies.serial,  // the Paxos ballot for the IF
    },
  );

  // LWTs return a row whose [applied] column says whether the condition held.
  const applied = rs.first()["[applied]"];
  if (!applied) throw new Error(`username ${username} already taken`);
  return { username, userId };
}

// Only use this where uniqueness actually matters. Running every write as an
// LWT costs multiples of a normal write and serialises on the partition.

Related

sd replicationsd consistency modelssd cap pacelcsd design key valuesd clocks

Discussion

  • Be the first to comment on this lesson.