Idempotent Operations

The Recovery and Continuity topic closed with a drill, and it left two open problems. When failover and retry ran together, the same work ran twice: a carrier notification was both resent after a timeout and replayed from the log by the replica that took over. The second problem — half-finished workflows were never rolled back — is still open. This lesson takes on the first.

Idempotence and the idempotency key were defined in the Web API Design and The Data Access Layer and Business Logic courses; those courses showed that a second request arriving with the same key gets served the first response, that the key is stored in the same transaction as the effect, and that delivery semantics duplicate delivery, not effect. The definition is not repeated here. This lesson has two questions: how many side effects a duplication produces in a failure window, and what the ledger that holds that duplication costs on a failure-free day.

The Three Sources of Duplication

The failure scenario is named directly. The carrier notification endpoint slows down: the endpoint keeps answering, but its response time crosses the caller’s timeout threshold, so the caller counts the request as failed and retries. If a replica takes over during the slowdown, the replica that took over replays the log’s last writes, and the queue side redelivers the unacknowledged message. Three sources run at the same time.

DD1 — the failure window is 90 seconds, twice a month. Rationale: this duration sits below K01’s ten-minute recovery-time assumption, so it does not register as an outage in the monthly outage budget, but it sits above the timeout threshold. Its sensitivity is given at 4 windows a month. DD2 — the probability that a write is duplicated in the window is 0.35, split across three sources: 0.20 for the carrier’s retry, 0.10 for replay on failover, 0.05 for at-least-once redelivery. Both are assumptions and are not added to K01’s table.

The rig is a process-internal model: there is no queue, store, or network; the ledger is a set and side effects are counters. The only property the model carries is that the same event can reach the handler more than once.

// idempotent/stream.mjs — the in-process model of the state event stream and the idempotency ledger.
// There is no real queue, store, or network: the ledger is a set, side effects are counters.

export const SEQUENCE = ["accepted", "transferred", "transferred", "transferred",
  "out-for-delivery", "delivery-attempt", "delivered"];   // K01 V4 = 7 state events per shipment

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

export const events = (shipment) =>
  SEQUENCE.map((state, i) => ({ tracking: `TR-${shipment}`, state, eventNo: i }));

export const key = (o, mode) => mode === "tracking" ? o.tracking
  : mode === "tracking+state" ? `${o.tracking}|${o.state}` : `${o.tracking}|${o.state}|${o.eventNo}`;

// Side effect: every event writes a state record; delivery also adds an invoice line and sends a notification.
export const sideEffects = (o) => (o.state === "delivered" ? 3 : 1);

export function processor({ ledgered, mode }) {
  const ledger = new Set();
  const s = { processed: 0, suppressed: 0, sideEffects: 0 };
  return {
    s,
    handle(o) {
      const k = key(o, mode);
      if (ledgered && ledger.has(k)) { s.suppressed += 1; return; }
      ledger.add(k);
      s.processed += 1;
      s.sideEffects += sideEffects(o);
    },
    size: () => ledger.size,
  };
}

// Delivery stream: every event arrives once; in the failure window, three sources produce extra deliveries.
export function deliveries(shipmentCount, sources, seed) {
  const rnd = generator(seed);
  const stream = [], counts = new Map(sources.map(([name]) => [name, 0]));
  for (let g = 0; g < shipmentCount; g += 1)
    for (const o of events(g)) {
      stream.push(o);
      for (const [name, p] of sources)
        if (rnd() < p) { stream.push(o); counts.set(name, counts.get(name) + 1); }
    }
  return { stream, counts };
}

The same stream runs under three key modes and once without a ledger. The key mode is a scope decision: whether the key consists of only the tracking number, the tracking number and the state, or the triple that also includes the event number the carrier produces.

// idempotent/measure.mjs — the failure-free day's cost and the failure window's gain are counted separately
import { SEQUENCE, deliveries, processor } from "./stream.mjs";

const PEAK_WRITE = 97.22, WINDOW = 90;                     // K01 computed value; DD1 failure window
const SHIPMENTS = Math.round((PEAK_WRITE * WINDOW) / SEQUENCE.length);
const SOURCES = [["carrier retry", 0.20],                  // DD2, split across three sources
  ["replay on failover", 0.10], ["at-least-once redelivery", 0.05]];
const MODE = ["tracking", "tracking+state", "tracking+state+event"];

const run = (sources, seed) => {
  const { stream, counts } = deliveries(SHIPMENTS, sources, seed);
  const rows = MODE.map((mode) => {
    const d = processor({ ledgered: true, mode });
    for (const o of stream) d.handle(o);
    return [mode, d.s, d.size()];
  });
  const y = processor({ ledgered: false, mode: "tracking+state+event" });
  for (const o of stream) y.handle(o);
  return { stream, counts, rows, y: y.s };
};

const print = (title, r) => {
  console.log(`\n${title}: ${r.stream.length} deliveries, side effects without a ledger ${r.y.sideEffects}`);
  for (const [name, s, size] of r.rows)
    console.log(`${name.padEnd(22)}${String(s.processed).padStart(9)}${String(s.suppressed).padStart(12)}` +
      `${String(s.sideEffects).padStart(13)}${String(r.y.sideEffects - s.sideEffects).padStart(11)}${String(size).padStart(11)}`);
};

console.log(`model: ${SHIPMENTS} shipments x ${SEQUENCE.length} events = ${SHIPMENTS * SEQUENCE.length} distinct events`);
console.log(`(K01 peak write ${PEAK_WRITE} events/s x DD1 window ${WINDOW} s)`);
console.log(`\n${"key mode".padEnd(22)}${"processed".padStart(9)}${"suppressed".padStart(12)}` +
  `${"side effects".padStart(13)}${"prevented".padStart(11)}${"ledger".padStart(11)}`);
print("failure-free day (no duplication)", run([], 20260730));
const r = run(SOURCES, 20260730);
print("failure window (DD2)", r);
console.log(`source split: ${[...r.counts].map(([a, n]) => `${a} ${n}`).join(", ")}`);
const duplicates = r.stream.length - SHIPMENTS * SEQUENCE.length;
const duplicateDeliveries = r.stream.filter((o) => o.state === "delivered").length - SHIPMENTS;
console.log(`duplicate deliveries ${duplicates}, ${duplicateDeliveries} of them are "delivered" events; ` +
  `that means ${duplicateDeliveries} duplicate invoice lines and ${duplicateDeliveries} duplicate notifications`);

model: 1250 shipments x 7 events = 8750 distinct events
(K01 peak write 97.22 events/s x DD1 window 90 s)

key mode              processed  suppressed side effects  prevented     ledger

failure-free day (no duplication): 8750 deliveries, side effects without a ledger 11250
tracking                   1250        7500         1250      10000       1250
tracking+state             6250        2500         8750       2500       6250
tracking+state+event       8750           0        11250          0       8750

failure window (DD2): 11849 deliveries, side effects without a ledger 15251
tracking                   1250       10599         1250      14001       1250
tracking+state             6250        5599         8750       6501       6250
tracking+state+event       8750        3099        11250       4001       8750
source split: carrier retry 1789, replay on failover 876, at-least-once redelivery 434
duplicate deliveries 3099, 451 of them are "delivered" events; that means 451 duplicate invoice lines and 451 duplicate notifications

These numbers are in the measurement class: they come from a process-internal model run with a generator seeded at 20260730, and they reproduce under the same seed. Their inputs are K01’s computed value (peak write 97.22 events/s) and this lesson’s assumptions (DD1, DD2).

The Key’s Scope Is a Suppression Decision

The block above counts the failure-free day, and the table’s most expensive row sits there. With no duplication, the correct scope (tracking+state+event) suppresses nothing: 8750 events are processed, 11250 side effects are produced. The narrow tracking key, on the other hand, suppresses 7500 valid events, because a shipment’s seven state events all carry the same tracking number; only the first survives, and side effects drop from 11250 to 1250. The mid-scope tracking+state suppresses 2500 events, because the sequence’s three transferred events all produce the same key.

The wrong scope’s large numbers in the “prevented” column cannot be read as a gain. In the failure window, the tracking mode looks like it prevented 14001 side effects; 10,000 of that is the same suppression that already happens on a failure-free day — that is, it deletes real side effects. The rule is this: the idempotency key’s scope must be wide enough to distinguish two events that are distinct in business terms; narrowing the key destroys the system’s own work, not the duplication.

The block below counts the failure window. Under the correct scope, 8750 distinct events turn into 11,849 deliveries; of the 3099 extra deliveries, 1789 come from the carrier’s retry, 876 from replay on failover, 434 from at-least-once redelivery. Without a ledger, side effects would be 15,251 instead of 11,250: 4001 extra side effects. Of those, 451 are duplicate invoice lines and 451 are duplicate notifications — one is a delivery billed twice to the seller, the other a delivery notice sent twice to the recipient.

The Ledger’s Cost

The ledger is not free. Every write first reads the ledger, then writes a key row alongside its own record; these rows are kept for a window.

DD3 — a key record is 72 bytes, the ledger window is 24 hours. The record carries the key, a body digest, a timestamp, and an outcome marker. The window’s rationale is that it needs to be long enough to cover a client’s retry chain and the replay after failover. Its sensitivity is given at twice the record size, three times the window, and a one-hour window.

// idempotent/cost.mjs — the records the ledger holds, the bytes it occupies, and row rates at K01 scale
const EVENTS = 2_800_000, SHIPMENTS = 400_000;         // K01 computed value: daily state events and shipments
const PEAK_WRITE = 97.22, BEHIND_CACHE_READ = 41.67;   // K01 computed value: peak write, reads behind cache
const DAILY_MB = 976, RATIO = 2.33;                    // K01 computed value: daily data growth, write/read
const RECORD = 72, HOUR = 24;                          // DD3: key record bytes and ledger window
const keyedWrites = EVENTS + SHIPMENTS;

console.log(`daily writes needing a key ${keyedWrites.toLocaleString("en-US")} ` +
  `(${EVENTS.toLocaleString("en-US")} state events + ${SHIPMENTS.toLocaleString("en-US")} shipments)`);
console.log(`\n${"window".padStart(9)}${"record bytes".padStart(14)}${"records held".padStart(15)}` +
  `${"ledger MB".padStart(12)}${"of daily growth".padStart(18)}`);
for (const [s, b] of [[HOUR, RECORD], [HOUR, RECORD * 2], [HOUR * 3, RECORD], [1, RECORD]]) {
  const record = (keyedWrites * s) / 24, mb = (record * b) / 1e6;
  console.log(`${`${s} h`.padStart(9)}${String(b).padStart(14)}` +
    `${Math.round(record).toLocaleString("en-US").padStart(15)}${mb.toFixed(2).padStart(12)}` +
    `${`${((100 * mb) / DAILY_MB).toFixed(2)}%`.padStart(18)}`);
}

const write2 = PEAK_WRITE * 2, read2 = BEHIND_CACHE_READ + PEAK_WRITE;
console.log(`\npeak write rows/s ${PEAK_WRITE} -> ${write2.toFixed(2)} (${(write2 / PEAK_WRITE).toFixed(2)}x)`);
console.log(`reads behind cache/s ${BEHIND_CACHE_READ} -> ${read2.toFixed(2)} (${(read2 / BEHIND_CACHE_READ).toFixed(2)}x)`);
console.log(`write/read ratio at the store ${RATIO} -> ${(write2 / read2).toFixed(2)}`);

const PREVENTED = 4001, INVOICE = 451;                // measure.mjs: prevented side effects and
console.log(`\n${"DD1 windows/month".padStart(18)}${"side effects prevented".padStart(24)}` +  // duplicate deliveries per window
  `${"duplicate invoice lines".padStart(25)}${"of daily lines".padStart(18)}`);
for (const n of [2, 4])
  console.log(`${n.toFixed(0).padStart(18)}${(n * PREVENTED).toLocaleString("en-US").padStart(24)}` +
    `${(n * INVOICE).toLocaleString("en-US").padStart(25)}` +
    `${`${((100 * n * INVOICE) / (SHIPMENTS * 30)).toFixed(5)}%`.padStart(18)}`);
console.log(`the wrong scope's cost: the tracking+state mode suppresses ` +
  `${((EVENTS * 2) / 7).toLocaleString("en-US")} valid events a day, ` +
  `the tracking mode suppresses ${((EVENTS * 6) / 7).toLocaleString("en-US")}`);

daily writes needing a key 3,200,000 (2,800,000 state events + 400,000 shipments)

   window  record bytes   records held   ledger MB   of daily growth
     24 h            72      3,200,000      230.40            23.61%
     24 h           144      3,200,000      460.80            47.21%
     72 h            72      9,600,000      691.20            70.82%
      1 h            72        133,333        9.60             0.98%

peak write rows/s 97.22 -> 194.44 (2.00x)
reads behind cache/s 41.67 -> 138.89 (3.33x)
write/read ratio at the store 2.33 -> 1.40

 DD1 windows/month  side effects prevented  duplicate invoice lines    of daily lines
                 2                   8,002                      902          0.00752%
                 4                  16,004                    1,804          0.01503%
the wrong scope's cost: the tracking+state mode suppresses 800,000 valid events a day, the tracking mode suppresses 2,400,000

The Numbers for Two Days

The failure-free day’s cost has three line items. The ledger holds 3,200,000 records and takes up 230.40 MB — 23.61 percent of K01’s 976 MB daily data growth. The peak write row rate climbs from 97.22 to 194.44, exactly double. A key lookup is added to the read side: reads behind cache climb from 41.67 to 138.89, 3.33 times. The write/read ratio at the store drops from 2.33 to 1.40 — the smaller number does not mean less load; the ledger grew both sides, the read side more.

Sensitivity concentrates in the window. When the window climbs from 24 hours to 72 hours, the ledger reaches 691.20 MB, 70.82 percent of the daily growth; at a one-hour window it stays at 9.60 MB and 0.98 percent. Doubling the record size does not have the same effect: 460.80 MB. The window, not the record size, sets the ledger’s cost, because the window multiplies both the record count and the retention time.

The failure day’s gain has two line items. At DD1’s 2 windows a month, 4001 side effects prevented per window, 8002 a month. Of that, 902 are duplicate invoice lines, 0.00752 percent of K01’s 400,000 daily lines. The percentage is small, and it is not the number that defends the pattern: 902 duplicate invoice lines are 902 wrongly billed deliveries — 902 reconciliation mismatches — and the same number of recipients get a second delivery notice. At twice DD1, it becomes 1804. The side effect count is read by the unit, not by the percentage, because each unit produces a correction job.

Summary

• Duplication does not come from one source: of the 3099 extra deliveries in the 90-second window, 1789 came from retry, 876 from replay on failover, 434 from at-least-once delivery.
• Without a ledger, side effects would be 15,251 instead of 11,250; of the 4001 side effects prevented, 451 are duplicate invoice lines and 451 are duplicate notifications.
• The idempotency key’s scope is a suppression decision: on a failure-free day, the tracking mode suppresses 7500 valid events and tracking+state suppresses 2500; at K01 scale that is 2,400,000 and 800,000 events a day.
• The failure-free day’s cost: 3,200,000 ledger records, 230.40 MB (23.61 percent of daily growth), peak write rows at 2.00x, reads behind cache at 3.33x.
• The window sets the cost: a 72-hour window pushes the ledger to 691.20 MB, a one-hour window holds it at 9.60 MB; doubling the record size gives 460.80 MB.
• The failure day’s gain is 8002 side effects prevented a month and 902 duplicate invoice lines — 0.00752 percent of the daily lines, but 902 separate correction jobs.

Next Step

The ledger stopped duplication, but only of the same work running a second time. The drill’s second open problem still stands: a half-finished workflow’s completed steps are still never rolled back. If a billing job fails at its third step, the first two steps’ effects stay final, and those are not duplicated effects but half-finished ones; the idempotency key says nothing about this case. The next lesson takes on compensating for steps that cannot be rolled back: where an uncompensatable step belongs in the ordering, how many jobs are left stuck when the compensation call itself fails, and how many reads see the intermediate state during the rollback window.