Replication and quorums

The problem: storing every click, in two regions, always writable

Snip keeps a full history of clicks for its analytics plan: billions of small rows, written constantly from both regions. The requirements are unusual: writes must never be refused, even if a node or a region is unreachable, and a click that's a few seconds late to appear is fine. A single leader is the wrong shape: every write would have to reach one place.

Three shapes of replication

Multi-leader and leaderless both accept writes in more than one place, so both must resolve conflicts, using versions, last-write-wins or merging (08.05 Clocks and ordering). Snip's click history is append-only (each click is a new row), so conflicts never arise there, which is a big reason leaderless suits it.

Quorums

In a leaderless store, each key lives on N replicas. A write is sent to all N and counts as done once W have acknowledged it. A read asks the replicas and waits for R answers, returning the newest version among them.

If R + W > N, every set of R replicas overlaps every set of W replicas in at least one node, so a read always hears from at least one replica that has the latest acknowledged write. Werner Vogels's description is exact: if W + R > N, "the write set and the read set always overlap"; if not, reads can go to nodes that haven't received the update.

Try it

The lab shows the trade. W and R decide both consistency and availability: a write survives N − W replicas being down, a read survives N − R. Common settings:

• N = 3, W = 2, R = 2: the usual balance. Dynamo's paper gives (3, 2, 2) as the common configuration across its instances.
• W = N, R = 1: fast reads, but one replica down blocks every write.
• W = 1, R = 1: fastest and most available, with no overlap: reads can easily be stale.

Cassandra calls these consistency levels: ONE, QUORUM (a majority of replicas), LOCAL_QUORUM (a majority in the local datacenter, avoiding cross-region waits), ALL. Snip writes click history at LOCAL_QUORUM with three replicas per region, so a write needs two local replicas and never waits for the Atlantic.

What quorums don't promise

R + W > N is weaker than it sounds:

• It isn't linearizable. A write in progress may be on some replicas but not others, so two reads at the same moment can disagree. Abadi notes that even with R + W > N these systems "cannot achieve full consistency".
• Concurrent writes still conflict. Two writes to the same key, each reaching W replicas, leave replicas with different values. Something has to decide (08.05 Clocks and ordering), and last-write-wins by timestamp silently drops one (05.06 Clocks, skew and ordering IDs).
• Sloppy quorums weaken it further. If the key's home replicas are unreachable, some systems write to other nodes temporarily to stay available, which means a "quorum" of writes may not overlap the replicas a read asks.

How replicas catch up

Replicas miss writes while down or slow. Three mechanisms bring them back in line:

• Hinted handoff. A node that accepts a write on behalf of an unreachable replica keeps a "hint" and delivers the write when that replica returns.
• Read repair. A read that sees replicas disagree writes the newest value back to the stale ones.
• Anti-entropy. A background process compares replicas and copies what's missing. Cassandra's repair has replicas build hash trees (Merkle trees) over their data, so they can find the differing ranges without comparing every row.

Here's a quorum read with read repair. It asks every replica, uses the first R answers, returns the newest version, and quietly updates any replica in that quorum that was behind:

type Versioned = { value: string; version: number };
interface Replica {
  get(key: string): Promise<Versioned | null>;
  put(key: string, v: Versioned): Promise<void>;
}

/** Ask every replica, use the first R answers, return the newest, and repair stale replicas in the background. */
export async function quorumRead(replicas: Replica[], key: string, r: number): Promise<Versioned | null> {
  const answers: { replica: Replica; v: Versioned | null }[] = [];
  await new Promise<void>((resolve, reject) => {
    let failed = 0;
    for (const replica of replicas) {
      replica.get(key).then(
        (v) => {
          answers.push({ replica, v });
          if (answers.length === r) resolve();
        },
        () => {
          if (++failed > replicas.length - r) reject(new Error(`fewer than ${r} replicas answered`));
        },
      );
    }
  });
  const quorum = answers.slice(0, r);
  const newest = quorum.reduce<Versioned | null>((best, a) => (a.v && (!best || a.v.version > best.version) ? a.v : best), null);
  if (newest) {
    for (const a of quorum) if (!a.v || a.v.version < newest.version) void a.replica.put(key, newest); // read repair
  }
  return newest;
}

Tested with three simulated replicas, one up to date and two stale, the read returned the newest version and repaired the stale replica in its quorum; the slowest replica, outside the quorum, stayed stale until anti-entropy would reach it. With two of three replicas failing, the read failed instead of returning a possibly stale answer.

Recap

Interview questions