Replication

The previous topic framed persistence and eviction as decisions made by a single node: which moment gets written to disk, which entry gets dropped when the memory limit fills, when an expired key gets cleaned up. All of these were made inside one process, and all of them assumed that process stayed up. What happens when the process itself stops was never asked.

This topic covers setups where the store spreads across more than one node. The first question is the simplest one: keep the same data on a second node too. The library catalog and loan system is again the example domain here; the work being measured is reading the catalog cache and writing loan records.

The Forced Consequence of the Acknowledgment Model

The mechanics of replication are not this course’s subject. Log streaming, replication lag, and the diminishing return of adding replicas were measured in the Scaling the Data Layer course; how a cluster decides for itself when it loses a member was measured in the Non-Relational Data Models course. Neither is repeated here.

This lesson’s question is the in-memory store’s own constraint. When the store accepts a write, it writes it to memory and acknowledges it immediately; tying that acknowledgment to a replica’s apply would cancel the store’s reason for existing. This is why replication in an in-memory store is asynchronous, and this is not a setting — it is a consequence of the acknowledgment model. It carries three measurable costs, and all three are paid out of memory:

1. Every replica holds the entire data set. Adding a replica does not divide the bytes stored, it multiplies them. On disk this is a capacity line item; in memory it is a direct purchase.
2. The primary node holds an output buffer for every replica. Writes that have not yet reached a replica wait in the primary’s memory. The buffer is memory too.
3. A replica’s lag is not a span of time, it is a count of writes. Any key read from a replica returns stale if it was written within that window.

Mechanism

The mechanism below is a model: no real store, network, or replica is set up. A round is an abstract step; propagation delay and apply capacity are parameters counted in rounds, not measured time. The model’s only realistic assumption is the asynchrony above.

CU1 — propagation delay defaults to 2 rounds, and the replica keeps up with the primary’s write rate. Rationale: a healthy replica does not carry a backlog, it only arrives with a fixed lag. CU2 — a catalog entry is 240 bytes, a write record in the replication stream is 96 bytes. Rationale: the record carries only the change, not the whole entry. CU3 — 70 percent of accesses go to 10 percent of keys. Rationale: loan and lookup traffic concentrates on popular books. CU1 and CU2 have a linear effect: if the delay doubles, the staleness window doubles too.

// replication/model.mjs — the in-memory store's replication is an IN-PROCESS MODEL. A round is an
// abstract step; propagation delay and apply capacity are parameters counted in rounds, not
// measured time. The model's only realistic assumption is the asynchrony described above.
export const ENTRY_BYTES = 240;   // per catalog entry: key + value + metadata (my own accounting)
export const RECORD_BYTES = 96;   // bytes of one write record in the replication stream

export function generator(seed) {  // linear congruential generator; seed is visible
  let s = seed >>> 0;
  return () => { s = (Math.imul(s, 1103515245) + 12345) >>> 0; return s / 4294967296; };
}

export function run({ replicas, delay, capacity = null, bufferLimit = Infinity, resyncRounds = 5,
                      rounds = 200, writes = 40, reads = 400, keys = 2000, seed = 20260731 }) {
  const rnd = generator(seed);
  const hot = Math.floor(keys * 0.10);                        // popular books: 10% of keys
  const pick = () => (rnd() < 0.70 ? Math.floor(rnd() * hot)   // 70% of accesses go to them
                                    : hot + Math.floor(rnd() * (keys - hot)));
  const seq = new Int32Array(keys);                           // sequence number of key's last write
  const applied = Array(replicas).fill(0);                    // number of writes the replica applied
  const offline = Array(replicas).fill(0);                    // rounds offline due to resync
  const peak = Array(replicas).fill(0);                       // largest output buffer per replica
  let accepted = 0, stale = 0, replicaReads = 0, fullResyncs = 0, firstOverflow = null, offlineTotal = 0;

  for (let t = 1; t <= rounds; t += 1) {
    for (let w = 0; w < writes; w += 1) { accepted += 1; seq[pick()] = accepted; }
    for (let i = 0; i < replicas; i += 1) {
      const target = Math.max(0, (t - delay[i]) * writes);    // arrives as far behind as the delay
      if (offline[i] > 0) {                                   // full resync in progress: reads unmet
        offline[i] -= 1; offlineTotal += 1;
        if (offline[i] === 0) applied[i] = target;            // resync brings the replica to normal lag
        continue;
      }
      applied[i] = Math.min(target, applied[i] + (capacity === null ? writes : capacity[i]));
      const buffer = (accepted - applied[i]) * RECORD_BYTES;  // output buffer at the primary: MEMORY
      if (buffer > peak[i]) peak[i] = buffer;
      if (buffer > bufferLimit) {                             // buffer overflowed: replica is dropped
        fullResyncs += 1; offline[i] = resyncRounds;
        if (firstOverflow === null) firstOverflow = t;
      }
    }
    const open = [0, ...[...Array(replicas).keys()].map((i) => i + 1).filter((n) => offline[n - 1] === 0)];
    for (let r = 0; r < reads; r += 1) {
      const n = open[r % open.length];                        // reads round-robin over open nodes
      const k = pick();
      if (n === 0) continue;                                  // the primary is always current
      replicaReads += 1;
      if (seq[k] > applied[n - 1]) stale += 1;                // replica has not yet applied this key
    }
  }
  const nodes = replicas + 1, buffer = peak.reduce((a, b) => a + b, 0);
  return { accepted, stale, replicaReads, fullResyncs, firstOverflow, buffer, offlineTotal,
           data: nodes * keys * ENTRY_BYTES,                  // each node holds the ENTIRE data set
           mostLoaded: Math.round(reads / nodes) + writes };   // primary: read share + all writes
}

// replication/measure.mjs — same workload across three settings: replica count, propagation delay, slow replica
import { run, ENTRY_BYTES, RECORD_BYTES } from "./model.mjs";

const s = (x, n) => String(x).padStart(n);
const kib = (b, n) => s((b / 1024).toFixed(1) + " KiB", n);
const pct = (r, n = 10) => s(((r.stale / r.replicaReads) * 100).toFixed(2) + "%", n);

console.log("200 rounds; each round writes 40 loans/renewals, reads 400 catalog entries. 2,000 keys,");
console.log("240 bytes per entry, replication record 96 bytes. Seed 20260731. Delay 2 rounds.\n");
console.log("replicas |  data held | busiest node | reads/replica |  stale | stale rate");
console.log("---------|------------|--------------|---------------|--------|-----------");
for (let k = 0; k <= 4; k += 1) {
  const r = run({ replicas: k, delay: Array(k).fill(2) });
  console.log(`${s(k, 8)} | ${kib(r.data, 10)} | ${s(r.mostLoaded + " wr/rd", 12)} | ${s(r.replicaReads, 13)} |` +
    ` ${s(r.stale, 6)} | ${k === 0 ? s("n/a", 10) : pct(r)}`);
}

console.log("\n2 replicas fixed; propagation delay varies:");
console.log("delay | staleness window | reads/replica |  stale | stale rate | output buffer");
console.log("------|------------------|---------------|--------|------------|---------------");
for (const g of [1, 2, 4, 8]) {
  const r = run({ replicas: 2, delay: [g, g] });
  console.log(`${s(g, 5)} | ${s(g * 40 + " writes", 16)} | ${s(r.replicaReads, 13)} | ${s(r.stale, 6)} |` +
    ` ${pct(r)} | ${kib(r.buffer, 13)}`);
}

console.log("\n2 replicas; second one has low apply capacity, buffer limit 64 KiB, resync 5 rounds:");
console.log("capacity | buffer growth | first overflow | full resync | offline | peak buffer |  stale");
console.log("---------|---------------|-----------------|-------------|---------|-------------|-------");
for (const c of [40, 36, 32, 24]) {
  const r = run({ replicas: 2, delay: [2, 2], capacity: [40, c], bufferLimit: 64 * 1024 });
  console.log(`${s(c, 8)} | ${s((40 - c) * RECORD_BYTES + " b/rd", 13)} | ` +
    `${s(r.firstOverflow === null ? "n/a" : r.firstOverflow, 15)} | ${s(r.fullResyncs, 11)} | ` +
    `${s(r.offlineTotal + " rd", 7)} | ${kib(r.buffer, 11)} | ${s(r.stale, 6)}`);
}

const N = [0, 1, 2, 3, 4];
console.log("\nquantities independent of the run:");
console.log("  staleness window = delay x write rate (writes)");
console.log("  buffer growth rate = (write rate - apply capacity) x " + RECORD_BYTES + " bytes/round");
console.log("  replica count  : " + N.map((n) => s(n, 8)).join(""));
console.log("  reads/node     : " + N.map((n) => s((400 / (n + 1)).toFixed(1), 8)).join(""));
console.log("  total data KiB : " + N.map((n) => s(((n + 1) * 2000 * ENTRY_BYTES / 1024).toFixed(1), 8)).join(""));

200 rounds; each round writes 40 loans/renewals, reads 400 catalog entries. 2,000 keys,
240 bytes per entry, replication record 96 bytes. Seed 20260731. Delay 2 rounds.

replicas |  data held | busiest node | reads/replica |  stale | stale rate
---------|------------|--------------|---------------|--------|-----------
       0 |  468.8 KiB |    440 wr/rd |             0 |      0 |        n/a
       1 |  937.5 KiB |    240 wr/rd |         40000 |   7132 |     17.83%
       2 | 1406.3 KiB |    173 wr/rd |         53200 |   9494 |     17.85%
       3 | 1875.0 KiB |    140 wr/rd |         60000 |  10740 |     17.90%
       4 | 2343.8 KiB |    120 wr/rd |         64000 |  11420 |     17.84%

2 replicas fixed; propagation delay varies:
delay | staleness window | reads/replica |  stale | stale rate | output buffer
------|------------------|---------------|--------|------------|---------------
    1 |        40 writes |         53200 |   4992 |      9.38% |       7.5 KiB
    2 |        80 writes |         53200 |   9494 |     17.85% |      15.0 KiB
    4 |       160 writes |         53200 |  16344 |     30.72% |      30.0 KiB
    8 |       320 writes |         53200 |  25517 |     47.96% |      60.0 KiB

2 replicas; second one has low apply capacity, buffer limit 64 KiB, resync 5 rounds:
capacity | buffer growth | first overflow | full resync | offline | peak buffer |  stale
---------|---------------|-----------------|-------------|---------|-------------|-------
      40 |        0 b/rd |             n/a |           0 |    0 rd |    15.0 KiB |   9494
      36 |      384 b/rd |             153 |           1 |    5 rd |    71.6 KiB |  16660
      32 |      768 b/rd |              78 |           2 |   10 rd |    72.0 KiB |  16769
      24 |     1536 b/rd |              40 |           4 |   20 rd |    72.0 KiB |  16480

quantities independent of the run:
  staleness window = delay x write rate (writes)
  buffer growth rate = (write rate - apply capacity) x 96 bytes/round
  replica count  :        0       1       2       3       4
  reads/node     :    400.0   200.0   133.3   100.0    80.0
  total data KiB :    468.8   937.5  1406.3  1875.0  2343.8

The Balance Sheet of Adding a Replica

What gets bought is the splitting of reads, not the splitting of stored data. The first table puts two columns side by side: at four replicas, reads per node drop from 400 to 80, while data held climbs from 468.8 KiB to 2,343.8 KiB. This is replication, not sharding — the name itself says so. On disk the same multiplier is a capacity line item; in memory it is a directly purchased one, and the cost per replica is fixed: the entire data set, 468.8 KiB.

Adding a replica does not make the data staler; it grows the share of stale reads. The stale rate is 17.83 percent at one replica, 17.84 percent at four — unchanged. What changes is the number of reads sent to a replica: from 40,000 to 64,000. The stale-read count climbs with it, from 7,132 to 11,420. The rate depends on delay, not on replica count; the count is the product of both.

Staleness is not a duration, it is a count of writes. The second table shows this directly: the window is delay × write rate, giving 40, 80, 160, and 320 writes, and the stale rate climbs from 9.38 percent to 47.96 percent. At a delay of eight rounds, nearly half of the reads made against a replica return an out-of-date catalog record. This does not mean the replica is broken; it means the loan counter returns the value from 320 writes ago, not the value currently on the primary.

Delay also carries a memory price. The same table’s last column measures the output buffer: from 7.5 KiB to 60 KiB. This byte count sits on the primary, not the replicas, and is directly proportional to the delay. A replica falling behind is not only the reader’s problem; the cost of that lag is drawn from the primary’s memory budget.

The Replica That Cannot Keep Up

The third table measures the case where the replica stops arriving with a fixed lag. The moment apply capacity drops below the write rate, the buffer grows by (40 − capacity) × 96 bytes every round, and that growth never stops: 384 bytes at capacity 36, 1,536 bytes at capacity 24. When the buffer hits its limit falls out of the division — at the 64 KiB limit, the first overflow lands at round 153, 78, and 40 respectively.

The consequence of overflow is that the replica gets dropped and undergoes a full resync: since it can no longer keep up with the stream, it reloads the entire data set. The memory-budget consequence of that shows up at the worst possible moment — the primary, already overflowing its buffer, now also has to produce a snapshot of the whole data set, a 468.8 KiB line item. In the table, the full-resync count climbs to 1, 2, and 4 as capacity drops, and the offline round count climbs from 5 to 20.

The last column carries a number that looks backward at first glance: stale reads for the lagging replica climb from 9,494 to 16,660, but when capacity drops further they stay at 16,769, and even fall to 16,480 at capacity 24. The reason is the neighboring column. During offline rounds, that replica serves no reads at all; reads shift to the primary and the healthy replica, and return a current answer from there. A drop in stale reads is not an improvement: reads per node have risen again because the replica was removed. A slow replica, as long as it is counted as read capacity, distorts the measurement twice — once while it answers stale, once more while it is not in a position to answer at all.

Summary

• Replication in an in-memory store is not a setting but the consequence of acknowledging writes from memory; tying the acknowledgment to a replica would cancel the store’s own rationale.
• Adding a replica splits reads but multiplies stored data: reads per node dropped from 400 to 80 while data held climbed from 468.8 KiB to 2,343.8 KiB, and the cost per replica is fixed.
• The stale-read rate did not change with replica count (17.83 percent versus 17.84 percent); what changed was the number of reads sent to a replica, and with it the stale-read count (7,132 versus 11,420).
• The staleness window is delay × write rate: across windows of 40, 80, 160, and 320 writes, the stale rate climbed from 9.38 percent to 47.96 percent.
• The primary node’s output buffer is a memory line item directly proportional to delay: from 7.5 KiB to 60 KiB; the bill for the replica’s lag is charged to the primary.
• When apply capacity drops below the write rate, the buffer grows by (40 − capacity) × 96 bytes/round, crosses the 64 KiB limit at round 153, 78, and 40, and each crossing triggers a full resync and offline rounds.

Next Step

This lesson measured replication under the assumption that the primary node stays up: a replica can fall behind, overflow its buffer, even undergo a full resync — but the node accepting writes is always the same one. When the primary stops, two questions open at once. The first is who decides: ruling that a node has truly stopped is not a decision an observer who cannot reach it can make alone. The second, and the one specific to this course, is that a replica is by definition behind the primary. The writes it does not have at the moment it takes over are writes that were reported as successful loan transactions. The next lesson counts the sentinel processes’ majority decision, the number of accepted writes lost in the failover window, and the false failovers produced by shortening the detection threshold.