Replica Sets

The previous topic carried the document model as far as single-document atomicity and stopped there. Every measurement up to this point was taken on a single node: how many requests an embedding decision cut the read path down to, where an index’s scanned-entry count settled, what a multi-document transaction cost. Most of the document model’s promises cannot be tested on a single node, though — horizontal scaling and a service surviving the loss of a machine both require more than one node.

This topic covers the store’s behavior in a distributed setup, and the first question is this: if the same data sits on more than one member, who decides which of them accepts writes. The library catalog and loan database remains the example domain for this topic; the work being measured is the writing of loan records.

The Cluster’s Own Election

The arrangement that keeps the same data on more than one member is called a replica set. One member is the primary and accepts writes; the others are secondary, apply the same changes, and serve reads depending on the configuration. This is the same pattern as the primary-replica setup from the Scaling the Data Layer course; the two names label the same pattern, and there is no mechanical difference between them.

The mechanics of replication were built in that course and in the Relational Database Administration course: log streaming, replication lag, the diminishing return of adding a replica, and stale reads were measured there. They are not repeated here. This lesson’s question is the decision the cluster makes on its own: who takes over when the primary stops, decided among the members themselves, and the decision has two measurable consequences — no write is accepted for as long as the decision remains unmade, and once the new primary is behind the old one, writes equal to that gap are rolled back.

The rule that binds the decision is the majority rule (quorum): a member can become primary only by winning the votes of more than half the membership. This rule keeps a cluster split in two from having both halves believe themselves the primary. Its cost sits inside the same rule: if a majority cannot assemble, no election starts at all.

The Mechanism

The mechanism below is a model: no real cluster, container, or cloud deployment is built, and members are just numbers. A turn is an abstract step; propagation delay, the detection threshold, and the election duration are parameters in turns, not measured time. The model’s one realistic assumption is that propagation is pull-directed: the secondary reads the primary’s log. Once the primary stops, any write that has not yet been read never reaches any member; that is where the rolled-back write comes from.

NS14 — per-member propagation delay is 2, 3, 3, and 5 turns. Reason: the secondaries’ distance from the primary is not equal. NS15 — the detection threshold is 2 turns, the election is 2 turns. Reason: deciding that the primary has stopped and collecting votes are separate steps. Both assumptions have a linear effect: if the delay doubles, the rolled-back write count roughly doubles as well.

// cluster/model.mjs — the replica set is a MODEL. A turn is an abstract step; propagation
// delay, the detection threshold, and the election duration are parameters in turns, not
// measured time. No real cluster is built. Propagation is PULL-directed: the secondary reads
// the primary's log, so once the primary stops, any write not yet read never reaches any member.
export function run({ members, delay, dropped = [], rule = "most-current", priority = 3,
                       failure = 13, detection = 2, election = 2, rate = 3, turns: N = 24 }) {
  const majority = Math.floor(members / 2) + 1;
  const down = new Set();
  const log = [0];                         // turn -> the last seq the primary accepted that turn
  const applied = Array(members).fill(0);
  let primary = 0, seq = 0, wait = 0, threshold = detection + election, rejections = 0;
  let noWrite = 0, oldAccepted = null, newPrimary = null, rolledBack = null;

  for (let t = 1; t <= N; t += 1) {
    if (t === failure) {                   // the primary, and a second member if given, drop in the same turn
      oldAccepted = seq;
      for (const i of [primary, ...dropped]) down.add(i);
      primary = null;
    }
    if (primary === null) {
      noWrite += 1; wait += 1;
      const voters = [...Array(members).keys()].filter((i) => !down.has(i));
      if (voters.length < majority || wait !== threshold) continue;   // without a majority, no election ever starts
      const mostCurrent = voters.reduce((a, b) => (applied[b] > applied[a] ? b : a));
      const candidate = rule === "priority" && rejections === 0 && !down.has(priority) ? priority : mostCurrent;
      if (voters.some((i) => applied[i] > applied[candidate])) {     // the majority rule rejects the candidate
        rejections += 1; threshold += election; continue;             // a second election round
      }
      newPrimary = candidate;
      rolledBack = oldAccepted - applied[newPrimary];
      seq = applied[newPrimary];
      for (let x = 0; x < log.length; x += 1) log[x] = Math.min(log[x], seq); // the log is truncated
      primary = newPrimary;
      continue;
    }
    seq += rate;                            // each turn writes `rate` loan records to the primary
    log[t] = seq;
    for (let i = 0; i < members; i += 1) {
      if (down.has(i)) continue;
      applied[i] = i === primary ? seq : Math.max(applied[i], log[t - delay[i]] ?? 0);
    }
  }
  return { majority, voters: members - down.size, noWrite, rolledBack, newPrimary, oldAccepted, rejections, applied };
}

One line of the model carries the whole trade-off: the candidate cannot be behind any member that voted for it. The majority rule’s real job is not counting votes — it is guaranteeing that the elected member’s own log is no older than the log of the majority that voted for it.

// cluster/measure.mjs — same failure, four cluster sizes; then two election rules in the same cluster
import { run } from "./model.mjs";

const DELAY = [0, 2, 3, 3, 5];             // propagation delay per member (turns)
const s = (x, n) => String(x).padStart(n);
console.log("24 turns, 3 loan records per turn. The primary stops at turn 13; detection 2, election 2 turns.");
console.log("36 records had been accepted before it stopped.\n");
console.log("cluster | dropped | majority | can vote | election | turns w/o write | rolled back | new primary");
console.log("--------|---------|----------|----------|----------|------------------|-------------|-------------");
const SETUP = [
  [3, [], "u0"], [3, [1], "u0+u1"], [4, [1], "u0+u1"], [5, [1], "u0+u1"], [5, [4], "u0+u4"],
];
for (const [members, dropped, name] of SETUP) {
  const r = run({ members, delay: DELAY.slice(0, members), dropped });
  console.log(`${s(members, 7)} | ${name.padEnd(7)} | ${s(r.majority, 8)} | ${s(r.voters, 8)} | ` +
    `${(r.newPrimary === null ? "no" : "yes").padStart(8)} | ${s(r.noWrite, 16)} | ` +
    `${s(r.rolledBack === null ? "-" : r.rolledBack, 11)} | ${r.newPrimary === null ? "none" : "u" + r.newPrimary}`);
}

console.log("\n5-member cluster, u0+u4 drop; the candidate-selection rule changes:");
console.log("rule          | candidate rejected | election round | turns w/o write | rolled back | new primary");
console.log("--------------|--------------------|-----------------|------------------|-------------|-------------");
for (const rule of ["most-current", "priority"]) {
  const r = run({ members: 5, delay: DELAY, dropped: [4], rule, priority: 3 });
  console.log(`${rule.padEnd(13)} | ${s(r.rejections, 18)} | ${s(r.rejections + 1, 15)} | ${s(r.noWrite, 16)} | ` +
    `${s(r.rolledBack, 11)} | u${r.newPrimary}`);
}

console.log("\nindependent of the run: majority = floor(n/2)+1, tolerated member loss = n - majority");
console.log("n        : " + [3, 4, 5, 6, 7].map((n) => s(n, 3)).join(""));
console.log("majority : " + [3, 4, 5, 6, 7].map((n) => s(Math.floor(n / 2) + 1, 3)).join(""));
console.log("loss     : " + [3, 4, 5, 6, 7].map((n) => s(n - (Math.floor(n / 2) + 1), 3)).join(""));

24 turns, 3 loan records per turn. The primary stops at turn 13; detection 2, election 2 turns.
36 records had been accepted before it stopped.

cluster | dropped | majority | can vote | election | turns w/o write | rolled back | new primary
--------|---------|----------|----------|----------|------------------|-------------|-------------
      3 | u0      |        2 |        2 |      yes |                4 |           6 | u1
      3 | u0+u1   |        2 |        1 |       no |               12 |           - | none
      4 | u0+u1   |        3 |        2 |       no |               12 |           - | none
      5 | u0+u1   |        3 |        3 |      yes |                4 |           9 | u2
      5 | u0+u4   |        3 |        3 |      yes |                4 |           6 | u1

5-member cluster, u0+u4 drop; the candidate-selection rule changes:
rule          | candidate rejected | election round | turns w/o write | rolled back | new primary
--------------|--------------------|-----------------|------------------|-------------|-------------
most-current  |                  0 |               1 |                4 |           6 | u1
priority      |                  1 |               2 |                6 |           6 | u1

independent of the run: majority = floor(n/2)+1, tolerated member loss = n - majority
n        :   3  4  5  6  7
majority :   2  3  3  4  4
loss     :   1  1  2  2  3

Reading the Numbers

An even-sized cluster adds nothing extra. The last three rows of the final block are independent of the run and purely arithmetic: in a four-member cluster the majority is 3, in a three-member cluster it is 2; both rest on tolerating the loss of exactly one member. The fourth member raises the amount of data stored by one increment and never enlarges the tolerated loss. The table shows this directly: the three-member and four-member clusters give the same result when two members drop — no election, 12 turns without writes.

In the rows where no election happens, what is being measured is an outage. In the three-member cluster where two members drop, exactly one member is left standing, and it may well hold the newest data; it still cannot become primary, because the majority is 2. This is not a missed opportunity — it is the rule itself: the surviving member cannot confirm that its neighbor did not accept a write it never saw. For the remaining 12 turns, not a single loan record is accepted.

Which member drops determines the number of rolled-back writes. The five-member cluster’s two rows show this on their own. When u0+u1 drop, the most current surviving member is u2, and it has applied up to record 27: 36 − 27 = 9 loan records are rolled back. When u0+u4 drop, u1 is the one standing, and it has applied up to record 30: the rollback is 6. Same cluster, same outage duration, same majority — the only difference is the identity of the second dropped member, and the result is fifty percent more rolled-back writes. This number is the count of writes the primary accepted but that never reached any surviving member.

A rolled-back write is not data loss; it is something sneakier: a loan record that was accepted and reported successful and is later disregarded. The member that wrote the request received a response; the loan transaction is not in the record. How this gap gets closed is not this lesson’s subject — it is the subject of the acknowledgement-level settings.

The Candidate Being Elected

The second table runs the same failure in the same cluster under two candidate-selection rules. Under the most-current rule, the candidate is the most current member among the voters, and the majority rule accepts it in the first round. Under the priority rule, a specific member — say, one in the main building — is put forward as the candidate; the model takes this member as u3, and u3 has applied up to record 27.

The result shows exactly what the majority rule does: because member u1 has applied up to record 30, u3’s candidacy is rejected. The rejected-candidate column reads 1, the election round becomes 2, and turns without writes rise from 4 to 6. The rolled-back write count is 6 under both rules, and that is no coincidence: because the rule never lets a candidate be behind, the most current member ends up as primary either way. What the priority setting pays for is not data — it is two extra turns of outage.

An operating rule follows from this: a priority setting is free only as long as the promoted member can actually stay current. Promoting a member with high propagation delay means paying one extra election round on every failure.

Summary

• A replica set is a primary-secondary topology, and it is the same pattern as the primary-replica setup in the Scaling the Data Layer course; the two names label one mechanism.
• The majority rule is floor(n/2)+1 votes, and the tolerated member loss is n − majority: three- and four-member clusters tolerate a single loss, five- and six-member clusters tolerate two — adding an even-numbered member does not enlarge durability.
• In the three- and four-member clusters where two members drop, no election ever started, and for the remaining 12 turns not one loan record was accepted; how current the surviving member’s data is does not change this.
• In the same outage, the identity of the dropped member determined the rolled-back write count: in the five-member cluster, 9 loan records were rolled back when u0+u1 dropped, 6 when u0+u4 dropped.
• A rolled-back write is a write that was accepted and reported successful and is later disregarded; its source is that it never reached any surviving member.
• When the majority rule rejected the priority candidate, it left the rolled-back write count unchanged but raised turns without writes from 4 to 6.

Next Step

This lesson measured what the cluster does when it loses a member, but every number it measured rested on the same implicit assumption: all the data sits on every member. That assumption carries a limit that replication can never resolve — adding members to the cluster splits reads, not writes or stored data. Once the catalog grows in document count and loan records no longer fit on a single member’s disk, the data has to be split across members. The split decision itself comes down to choosing a single field, and that choice is made from inside the document. The next lesson counts the criteria for choosing that field: how the uniqueness of the chosen field unbalances the number of documents per shard, why a monotonically increasing field piles all writes onto a single shard, and how many shards the same query mix touches under two different choices.