What is the saga pattern for distributed transactions?

// An orchestrated saga for "place order": three services, each with its own local
// database (a Map). Each step is a local transaction; each has a compensation.
// The saga log is an array the orchestrator persists after every step.
function makeWorld() {
  return {
    orders: new Map(),
    stock: new Map([["lamp", 1]]),
    reservations: new Map(),
    payments: new Map(), // idempotency key -> charge
    balance: 0,
    shipments: new Map(),
    refundOutages: 0,
    chargeCalls: 0,
  };
}

const steps = [
  { name: "reserveStock", act: (w, o) => {
      const left = w.stock.get(o.item);
      if (left < 1) throw new Error("out of stock");
      w.stock.set(o.item, left - 1); w.reservations.set(o.id, o.item);
    }, undo: (w, o) => {
      if (!w.reservations.has(o.id)) return; // idempotent: nothing to release
      w.reservations.delete(o.id); w.stock.set(o.item, w.stock.get(o.item) + 1);
    } },
  { name: "chargeCard", act: (w, o) => {
      w.chargeCalls++;
      const key = `charge-${o.id}`; // idempotency key: a retry cannot charge twice
      if (!w.payments.has(key)) { w.payments.set(key, o.amount); w.balance += o.amount; }
    }, undo: (w, o) => {
      if (w.refundOutages > 0) { w.refundOutages--; throw new Error("payments API 503"); }
      const key = `charge-${o.id}`;
      if (w.payments.has(key)) { w.balance -= w.payments.get(key); w.payments.delete(key); }
    } },
  { name: "scheduleShipping", act: (w, o) => {
      if (o.noCourier) throw new Error("no courier for this address");
      w.shipments.set(o.id, "scheduled");
    }, undo: (w, o) => { w.shipments.delete(o.id); } },
];

function runSaga(w, o, log, crashAfter) {
  w.orders.set(o.id, "PENDING"); // semantic lock: others see the order is not final
  for (let i = log.done.length; i < steps.length; i++) {
    try {
      steps[i].act(w, o);
      console.log(`  T${i + 1} ${steps[i].name} ok`);
      if (crashAfter === steps[i].name) { console.log(`  !! orchestrator crashes before logging it; saga log has done=[${log.done.join(",")}]`); return "CRASHED"; }
      log.done.push(steps[i].name);
    } catch (e) {
      console.log(`  T${i + 1} ${steps[i].name} FAILED: ${e.message} -> compensate in reverse`);
      for (let j = log.done.length - 1; j >= 0; j--) {
        for (let attempt = 1; ; attempt++) { // a compensation must eventually succeed
          try { steps[j].undo(w, o); console.log(`  C${j + 1} undo ${steps[j].name} ok (attempt ${attempt})`); break; }
          catch (err) { console.log(`  C${j + 1} undo ${steps[j].name} error: ${err.message}, retry in ${100 * 2 ** (attempt - 1)} ms`); }
        }
      }
      w.orders.set(o.id, "REJECTED");
      return "REJECTED";
    }
  }
  w.orders.set(o.id, "APPROVED");
  return "APPROVED";
}

function summary(w, o) {
  console.log(`  -> order ${o.id} ${w.orders.get(o.id)}; lamp stock ${w.stock.get("lamp")}; money held ${w.balance}; charges ${w.payments.size}; shipments ${w.shipments.size}`);
}

console.log("== 1. Happy path");
let w = makeWorld();
let o = { id: "o1", item: "lamp", amount: 40 };
console.log("  result " + runSaga(w, o, { done: [] }));
summary(w, o);

console.log("\n== 2. Step 3 fails, and the refund API is down twice");
w = makeWorld(); w.refundOutages = 2;
o = { id: "o2", item: "lamp", amount: 40, noCourier: true };
let log = { done: [] };
const sagaResult = runSaga(w, o, log);
console.log("  result " + sagaResult);
summary(w, o);

console.log("\n== 3. Orchestrator crashes after chargeCard, restarts, replays the last step");
w = makeWorld();
o = { id: "o3", item: "lamp", amount: 40 };
log = { done: [] };
runSaga(w, o, log, "chargeCard");
console.log("  restart: resume from the saga log at " + steps[log.done.length].name);
console.log("  result " + runSaga(w, o, log));
summary(w, o);
console.log(`  chargeCard was called ${w.chargeCalls} times; the idempotency key kept it to one charge of ${w.balance}`);

console.log("\n== 4. No isolation: a second shopper reads stock while saga o4 is in flight");
w = makeWorld();
o = { id: "o4", item: "lamp", amount: 40, noCourier: true };
w.orders.set(o.id, "PENDING");
steps[0].act(w, o); // T1 of o4 committed locally, stock is now 0
console.log(`  shopper B sees lamp stock ${w.stock.get("lamp")} and order o4 ${w.orders.get("o4")} -> told "sold out"`);
log = { done: ["reserveStock"] };
console.log("  result " + runSaga(w, o, log));
console.log(`  after compensation lamp stock is ${w.stock.get("lamp")}: B lost a sale that was never final`);