Saga Pattern

The previous lesson showed the cost of two-phase commit: a resource stayed held for as long as the slowest participant took, and it was left pending when the coordinator crashed. The saga pattern removes this window entirely. Each step commits its own transaction immediately; if a step fails, whatever completed is compensated in reverse.

The compensating step itself was built in M16/K04’s Distributed Transaction Problem lesson, and the cost of a compensating transaction was measured in M19/K05’s Distributed Correctness topic. Neither is repeated here. What this lesson measures is a constraint neither of them touched: the order of the steps. The order is not arbitrary, because not every step is reversible; and the choice of order determines how many effects have left the system and cannot be recalled at the moment of failure.

Mechanism

DC3. In this lesson the services are not separate processes; they are modules that run in the same process and write to separate stores. The property the model carries is that each step commits within its own transaction boundary and there is no shared rollback call. Network latency and partial failure are not part of the model.

DC4. The notification step’s external effect is modeled by writing a line to a file. Deleting the line does not undo the delivery, so this step has no compensation; the only thing that can be done is a fix through a second notification.

# setup.sh — four services' separate stores and the log going out to the outside world
rm -f catalog.db membership.db fee.db sent.log
sqlite3 catalog.db "CREATE TABLE book (book_id INTEGER PRIMARY KEY, status TEXT NOT NULL);
                    INSERT INTO book VALUES (1,'on_shelf'),(2,'on_shelf');"
sqlite3 membership.db  "CREATE TABLE member (member_id INTEGER PRIMARY KEY, open_loans INTEGER NOT NULL);
                    INSERT INTO member VALUES (4,0);"
sqlite3 fee.db   "CREATE TABLE entry (id INTEGER PRIMARY KEY, member_id INTEGER, amount INTEGER);"

// steps.mjs — the loan flow's four steps; each step either has a compensation or does not
import { DatabaseSync } from "node:sqlite";
import { appendFileSync, readFileSync, writeFileSync } from "node:fs";

const open = (d) => new DatabaseSync(d);
const catalogDb = open("catalog.db"), membershipDb = open("membership.db"), feeDb = open("fee.db");
const send = (line) => appendFileSync("sent.log", line + "\n");

export const steps = {
  "catalog.checkout": {
    run: (i) => catalogDb.prepare("UPDATE book SET status='on_loan' WHERE book_id=?").run(i.book),
    compensate: (i) => catalogDb.prepare("UPDATE book SET status='on_shelf' WHERE book_id=?").run(i.book) },
  "fee.charge": {
    run: (i) => feeDb.prepare("INSERT INTO entry (member_id,amount) VALUES (?,5)").run(i.member),
    compensate: (i) => feeDb.prepare("INSERT INTO entry (member_id,amount) VALUES (?,-5)").run(i.member) },
  "membership.addLoan": {
    run: (i) => membershipDb.prepare("UPDATE member SET open_loans=open_loans+1 WHERE member_id=?").run(i.member),
    compensate: (i) => membershipDb.prepare("UPDATE member SET open_loans=open_loans-1 WHERE member_id=?").run(i.member) },
  "notification.send": {                       // leaves the system: cannot be undone
    run: (i) => send(`member ${i.member}: book ${i.book} ready`),
    compensate: null, fix: (i) => send(`member ${i.member}: previous notification for book ${i.book} void`) },
};

export function reset() {
  catalogDb.exec("UPDATE book SET status='on_shelf'");
  membershipDb.exec("UPDATE member SET open_loans=0");
  feeDb.exec("DELETE FROM entry");
  writeFileSync("sent.log", "");
}
export const sent = () =>
  readFileSync("sent.log", "utf8").split("\n").filter((s) => s.length > 0);

Three of the four steps have a compensation, one does not. This is the only distinguishing difference, and the entire ordering constraint arises from it.

The Ordering Constraint

The same four steps are placed into two different orders, and each order is run separately for every failure point. The measured quantity is the number of unrecoverable side effects left behind once compensation finishes.

// sweep.mjs — same four steps, two different orders; every failure point is swept separately
import { steps, reset, sent } from "./steps.mjs";

const orders = {
  "A (notification early)": ["catalog.checkout", "notification.send", "fee.charge", "membership.addLoan"],
  "B (notification last)":  ["catalog.checkout", "fee.charge", "membership.addLoan", "notification.send"],
};

function runOrder(order, failStep, request) {
  reset();
  const done = [];
  let compensated = 0, unrecoverable = 0, fixed = 0;
  try {
    for (const name of order) {
      if (done.length + 1 === failStep) throw new Error(`${name} failed`);
      steps[name].run(request); done.push(name);
    }
  } catch {
    for (const name of [...done].reverse()) {
      const s = steps[name];
      if (s.compensate) { s.compensate(request); compensated += 1; }
      else { unrecoverable += 1; if (s.fix) { s.fix(request); fixed += 1; } }
    }
  }
  return { done: done.length, compensated, unrecoverable, fixed, sent: sent().length };
}

for (const [name, order] of Object.entries(orders)) {
  console.log(`\n${name}: ${order.join(" > ")}`);
  console.log("fail_step done compensated unrecoverable fixed total_sent");
  let total = 0;
  for (let k = 1; k <= order.length; k++) {
    const s = runOrder(order, k, { book: 1, member: 4 });
    total += s.unrecoverable;
    console.log(`${String(k).padStart(9)} ${String(s.done).padStart(4)} ${String(s.compensated).padStart(11)}` +
      ` ${String(s.unrecoverable).padStart(13)} ${String(s.fixed).padStart(5)} ${String(s.sent).padStart(10)}`);
  }
  console.log(`total unrecoverable side effects: ${total}`);
}

sh setup.sh
node sweep.mjs

A (notification early): catalog.checkout > notification.send > fee.charge > membership.addLoan
fail_step done compensated unrecoverable fixed total_sent
        1    0           0             0     0          0
        2    1           1             0     0          0
        3    2           1             1     1          2
        4    3           2             1     1          2
total unrecoverable side effects: 2

B (notification last): catalog.checkout > fee.charge > membership.addLoan > notification.send
fail_step done compensated unrecoverable fixed total_sent
        1    0           0             0     0          0
        2    1           1             0     0          0
        3    2           2             0     0          0
        4    3           3             0     0          0
total unrecoverable side effects: 0

Same steps, same work, same compensation code. The only difference is the order, and the result across four failure points is 2 versus 0. In order A, because the notification is the second step, every failure after it means a wrong message has already gone out to the member; since it cannot be recalled, the only thing that can be done is send the member a second message. Total sent is 2, not 0: two deliveries were made even though the work never happened.

Order B brings this down to zero, but it is not free. In B’s last row the compensation count is 3; in A’s same row it is 2. When the uncompensable step is moved to the end, the work that has to be rolled back when that step fails is at its largest. So the ordering decision is made between two quantities: unrecoverable side effect and completed step rolled back. The first is visible to the user and cannot be fixed; the second is merely expensive. The rule follows from this asymmetry: uncompensable steps go at the end of the order.

Same Flow, Two Implementations

Once the order is fixed, what remains is who carries it out. There are two implementations, and both produce the same result. In executor mode the flow lives in a single module; the service modules do not know their place in the order.

// executor.mjs — the whole flow in a single module; service modules never see the flow
import { steps } from "./steps.mjs";
export const order = ["catalog.checkout", "fee.charge", "membership.addLoan", "notification.send"];
export function execute(request) {
  const done = [];
  for (const name of order) { steps[name].run(request); done.push(name); }
  return done;                          // the compensation order is also read from this list
}

In choreography mode there is no central executor; each service triggers the one after it. Because compensation also walks backward, every node has to know its previous neighbor too.

// d-catalog.mjs — the catalog node: its own step and its two neighbors in the flow
export const node = { name: "catalog", step: "catalog.checkout", previous: null, next: "fee" };

// d-fee.mjs — the fee node: its own step and its two neighbors in the flow
export const node = { name: "fee", step: "fee.charge", previous: "catalog", next: "membership" };

// d-membership.mjs — the membership node: its own step and its two neighbors in the flow
export const node = { name: "membership", step: "membership.addLoan", previous: "fee", next: "notification" };

// d-notification.mjs — the notification node: its own step and its two neighbors in the flow
export const node = { name: "notification", step: "notification.send", previous: "membership", next: null };

// choreography.mjs — no central executor; the data path does not know the order, each node knows its neighbor
import { steps } from "./steps.mjs";
import { node as a } from "./d-catalog.mjs";
import { node as b } from "./d-fee.mjs";
import { node as c } from "./d-membership.mjs";
import { node as d } from "./d-notification.mjs";
const path = Object.fromEntries([a, b, c, d].map((x) => [x.name, x]));
export function start(firstNode, request) {
  const done = [];
  for (let x = path[firstNode]; x; x = x.next ? path[x.next] : null) {
    steps[x.step].run(request); done.push(x.step);   // each node triggers the next one
  }
  return done;
}

choreography.mjs imports all four nodes, but it does not know the order: which node connects to which lives in the nodes’ own files. The module is a registry, not a flow definition.

The Difference on the Code Side

The measurement is read from the source itself: in each file, how many service names other than its own appear?

// measure-code.mjs — counts how many files the flow information is scattered across in the source text
import { readFileSync } from "node:fs";
import { reset, sent } from "./steps.mjs";
import { execute, order } from "./executor.mjs";
import { start } from "./choreography.mjs";
const services = ["catalog", "fee", "membership", "notification"];
const edge = ["fee", "membership"];                // a new step would land between these two

function measure(label, files) {
  let named = 0, carrying = 0, touched = 0;
  for (const f of files) {
    const text = readFileSync(f, "utf8");
    const own = f.replace(/^d-/, "").replace(/\.mjs$/, "");
    const n = services.filter((s) => s !== own && text.includes(s)).length;
    named += n; if (n > 0) carrying += 1;
    if (edge.every((s) => text.includes(s))) touched += 1;
  }
  console.log(`${label}: files carrying flow name=${carrying}/${files.length}` +
    ` named steps=${named} | files to open to read the flow=${carrying}` +
    ` | existing files touched when a step is inserted=${touched}`);
}

reset(); const e = execute({ book: 1, member: 4 });
console.log(`executor    result: steps=${e.length} sent=${sent().length} [${e.join(",")}]`);
reset(); const k = start("catalog", { book: 1, member: 4 });
console.log(`choreography result: steps=${k.length} sent=${sent().length} [${k.join(",")}]`);
console.log(`same result: ${JSON.stringify(e) === JSON.stringify(k)}`);
measure("executor    ", ["executor.mjs"]);
measure("choreography", ["d-catalog.mjs", "d-fee.mjs", "d-membership.mjs", "d-notification.mjs"]);
console.log(`flow length (in both implementations): ${order.length} steps`);

sh setup.sh
node measure-code.mjs

executor    result: steps=4 sent=1 [catalog.checkout,fee.charge,membership.addLoan,notification.send]
choreography result: steps=4 sent=1 [catalog.checkout,fee.charge,membership.addLoan,notification.send]
same result: true
executor    : files carrying flow name=1/1 named steps=4 | files to open to read the flow=1 | existing files touched when a step is inserted=1
choreography: files carrying flow name=4/4 named steps=6 | files to open to read the flow=4 | existing files touched when a step is inserted=2
flow length (in both implementations): 4 steps

The run side is identical: four steps, one delivery, the same step list. The difference is entirely on the code side. In the executor, the flow information sits in 1 file as 4 named steps. In choreography it spreads across 4 files and rises to 6 named steps; the extra comes from the previous edges needed so compensation can walk backward. The executor’s done list accumulates in a single place, so it needs none of those edges.

Inserting a new step touches 1 existing file in the executor and 2 in choreography: the next field of the node before the new step and the previous field of the node after it have to change together. Choreography, in exchange, has no module that knows the whole flow; a service changing does not change the executor, and adding a new listener to the flow can be done without touching any existing file.

What it made cheaper: the saga zeroed out two-phase commit’s lock window; because each step commits its own transaction immediately, no resource stays held while another service’s response is awaited. Executor mode also made the entire flow readable in a single file.

What it made more expensive: a second implementation — the compensation — has to be written for every step. The step order is no longer free; it is constrained by compensability. In choreography mode, the flow information spread from 1 file to 4, and from 4 named steps to 6.

Which new failure mode was born: a half-finished flow. A failure that occurs after the uncompensable step has completed leaves the system in neither its starting nor its ending state; in order A this was measured as 2 deliveries to the member even though the work never happened. In executor mode there is an additional single point of failure: the executor itself. If the done list disappears with it, no one is left holding the compensation order.

Summary

• The saga removes two-phase commit’s lock window; in exchange it requires writing a compensation for every step and ordering the steps by compensability.
• When the same four steps were placed into two orders, the unrecoverable side effect across four failure points came out to 2 in order A and 0 in order B; in A, 2 deliveries were made even though the work never happened.
• The cost is reciprocal: in order B, the last step’s failure required 3 compensation calls, versus 2 in A. The uncompensable step goes last, because rolled-back work is expensive but fixable; an unrecoverable effect is not.
• The executor and choreography produced the same result — 4 steps, 1 delivery, the same step list — the difference is entirely in the code: flow information in 1 file and 4 named steps versus 4 files and 6 named steps.
• Inserting a step touches 1 existing file in the executor and 2 in choreography; in exchange, no module in choreography knows the whole flow, and adding a new listener does not touch existing files.

Next Step

In this lesson every step made its run call directly; it was treated as if there were no gap between a step committing and the next one being notified. In reality these are two separate jobs: the service writes to its own store, then publishes the message — and it can drop in between. The next lesson measures this gap: how many messages get lost when the publisher crashes, how many get delivered a second time under the same load with an outbox, what the relay’s delay is, and how many rows accumulate in the box.