Two-Phase Commit: All or None, Across Machines

in reviewThis lesson is complete and being validated before release - details may still change.

Two-phase commit

Loading interactive demo…

The chart has one lifeline per node: the coordinator on the left, then the banks taking part. Messages fill in wire order, a prepare hollow until its vote comes back and a decision hollow until it is acknowledged. The strips beneath show every node's standing and its log, one chip per node. Tap a message to read it.Take the tour, or press and explore. Legend:

The panel beside the stage is the real TwoPhaseCommit class from the published library executing in your browser, with the current line highlighted.

The message this step sends or answers, and the node it touches.
A prepare request; hollow while its vote is still owed.
A yes vote, a commit decision, and a node that has committed.
A no vote, an abort decision, a node that has rolled back, and a node that has crashed.
A participant that voted yes and holds its locks, waiting for the decision.
An acknowledgement, and messages still to come in the finished run.

messages counts prepares, votes, decisions, and acknowledgements on the wire; log forces counts records written on every node together; prepared counts participants holding locks; blocked for counts the steps they held them with no decision to act on; outcome and atomic say what was decided and whether every participant ended that way.

The code panel shows bare executable code by default. The bar above it names the file (hover the name for the full published path); options holds the toggles: comments, the tracer instrumentation that produces this visualization, and verbose names for the terse identifiers (display only: the default is the byte-exact published file). The view switch adds plain-English narration: both interleaves it with the code, pseudo shows only the pseudocode. hide code collapses the panel; the rail it leaves behind brings it back.

Keys: Space play/pause · ←/→ step · Home/End jump · R reset · F fullscreen · G guided tour

The problem. The transactions lesson ended with a commit, and the log lesson made it durable, on one machine. Spread the accounts of a transfer over several machines and the commit itself becomes a distributed problem: bank A must debit and bank B must credit, or neither must, and each bank can only see its own disk. A message saying "commit" can be lost, a bank can crash after doing half its work, and nobody can look inside another machine to find out. The protocol has to make every participant end the same way using only messages and each node's own log.

Phase one: prepare. A coordinator opens the transaction by logging who takes part, then asks each participant to prepare. A participant does its work, forces a prepared record to its own log so the work survives its crash, and votes yes. From that moment it holds its locks and can no longer change its mind: it has promised to commit if told to. A participant that cannot do the work, because a debit exceeds its balance, votes no and rolls back at once. A no needs no further instruction.

Phase two: decide. The coordinator collects the votes. Commit requires every vote to be yes; one no, or one vote that never comes, means abort, because silence and refusal must be treated alike. The coordinator forces the decision to its log before it tells anyone. That force is the moment the transaction becomes certain: whatever crashes afterwards, the decision exists on disk and can be resent. The participants apply the decision, log it, and acknowledge; when every acknowledgement is in, the coordinator logs done and may forget the transaction.

The logs are the protocol. Every message is preceded by a force to the sender's log, and every recovery is a node reading the last record of its own log. A coordinator that restarts with a decision record resends it. A coordinator that restarts with no decision record presumes abort: it never logged a decision, so no participant can have been told to commit, and abort is safe. A participant that restarts with a prepared record keeps waiting for the decision; one that restarts with nothing never promised anything and rolls back alone. Presumed abort, the R* refinement, is what makes the missing record meaningful, and it saves the coordinator a log record and a round of messages on every abort.

Blocking. The stage's fourth and fifth scenarios show the price. A participant that has voted yes cannot commit, because another vote may have been no, and cannot abort, because the coordinator may have decided commit. It cannot learn anything from the other participants either: they are in the same position. So it holds its locks for as long as the coordinator is down, and every other transaction that wants those rows waits behind it. Skeen proved in 1981 that no protocol with this shape avoids the problem; three-phase commit adds a round that removes it when nodes crash but not when the network partitions, which is why two-phase commit, blocking and all, is the protocol that shipped.

Cost. For $n$ participants a commit takes $4n$ messages, two rounds of $n$ each way, and $2n + 3$ log forces: one at the coordinator to open, one per participant to prepare, one at the coordinator to decide, one per participant to apply, one at the coordinator to close. Each force is a disk write the transaction cannot overlap with anything else. The latency is two network round trips plus the slowest participant's disk, which is why systems that can keep a transaction on one shard do.

The real thing. XA puts a transaction manager in the coordinator's seat and lets databases and message brokers be the participants. Spanner replicates every participant with Paxos so that a coordinator crash means a short leader election rather than a blocked table. Many services refuse the protocol altogether and settle for sagas: a chain of local transactions with a compensating transaction for each, which trades atomicity for availability and leaves the coordination to the application.

Choices worth reading closely in the implementation (the code panel's comments and tracer checkboxes reveal the full published file):

force is the one place a record enters a log, on any node, so the log tag has a single line and the count of forces is the protocol's disk cost. Every force happens before the message it guards is sent, which is the write-ahead rule of the previous arc applied to a conversation.
A yes vote and a no vote both force a record before the vote leaves: prepared for a yes, abort for a no. A participant that votes no is finished the moment it votes; a participant that votes yes is prepared, and held lists exactly these.
The coordinator forces its decision before decide is emitted, and recover reads the last record: a decision found is resent, no decision found is presumed abort. The decision field is the coordinator's memory and is lost with the crash; only the log is consulted.
apply is the one place an account changes, and only on commit. A participant restarting with no prepared record calls it with a null message id: it rolled back alone, so nothing crossed the wire.
waitDown is the one place blocking is observed: one blocked event per step of downtime while some participant is prepared with no decision, and silence when nobody is waiting, so a participant crash after the coordinator has aborted costs no blocked steps.
timeout fires when a vote is missing, before the decision, from the one site that compares who voted with who was asked. The class never waits on a clock; the script decides who falls silent.

Once a transaction could touch data on more than one machine, commit had to be agreed rather than merely written. The protocol was worked out in the 1970s at Xerox PARC and IBM: Butler Lampson and Howard Sturgis described it for a distributed file store, and Jim Gray set it down in his 1978 notes with the logging that lets it survive a crash. Dale Skeen showed in 1981 that it blocks when the coordinator fails, yet it is the protocol that shipped, in IBM's R*, in X/Open XA, and in the distributed databases of today.

1979Butler Lampson and Howard Sturgis - Crash Recovery in a Distributed Data Storage System, a Xerox PARC report circulated since 1976, describes a two-phase commit for a distributed file store with stable storage on every machine.source
1978Jim Gray - Notes on Data Base Operating Systems presents two-phase commit with the log records each node forces before it speaks, the recovery each node runs from its own log, and the coordinator's right to forget once every acknowledgement is in.source
1981Dale Skeen - Nonblocking Commit Protocols proves that two-phase commit can leave participants blocked when the coordinator fails and introduces three-phase commit, which adds a round so that no single crash blocks the rest.source
1986C. Mohan, Bruce Lindsay, and Ron Obermarck - Transaction Management in the R* Distributed Database Management System describes presumed abort and presumed commit, which spare the coordinator log records and messages by letting a missing record stand for a decision.source
1991X/Open - The X/Open XA specification standardizes the interface between a transaction manager and the resource managers it coordinates, so databases and message queues from different vendors can join one two-phase commit.source
2012Google - Spanner runs two-phase commit across Paxos groups spanning data centers, with each participant's state replicated so that a coordinator crash no longer blocks anyone for long.source

Used today

Distributed databases - Spanner, CockroachDB, and sharded relational systems commit a transaction that spans shards with two-phase commit between the shards' leaders.
XA transactions - A Java application server committing one transaction across a database and a message broker runs this protocol through the XA interface.
Its absence - Sagas and outbox patterns exist because holding locks across services while a coordinator decides is a price many systems refuse to pay.

scenario

participants3

messages: 12
log forces: 9
prepared: 0 of 3
blocked for: 0 steps
outcome: commit
atomic: yes

two-phase-commit.ts

import type { Tracer } from "../trace";export const MIN_COMMIT_PARTICIPANTS = 2;export const MAX_COMMIT_PARTICIPANTS = 3;/** How many steps a crashed node may stay down before it restarts. */export const MAX_COMMIT_DOWNTIME = 4;export const COMMIT_COORDINATOR = "coordinator";/** The one transaction a run commits or aborts. */export const COMMIT_TX = "T1";export type CommitOutcome = "commit" | "abort";export type CommitVote = "yes" | "no";/** A node's standing: working before it votes, prepared while it holds locks and waits, then committed or aborted; crashed until it restarts. */export type CommitNodeState = "working" | "prepared" | "committed" | "aborted" | "crashed";export type CommitRole = "coordinator" | "participant";/** One participant: the account it keeps and what the transaction does to it. */export interface CommitParticipant {  name: string;  /** The account's balance before the transaction. */  balance: number;  /** The transaction's change to the account; a debit past the balance makes the participant vote no. */  delta: number;}export type CommitFault =  | { kind: "none" }  /** The participant crashes before it votes and restarts after `downFor` steps. */  | { kind: "participant-crash"; participant: string; downFor: number }  /** The coordinator crashes after logging its decision but before sending it, or after the votes but before deciding. */  | { kind: "coordinator-crash"; when: "after-decision" | "before-decision"; downFor: number };export interface CommitScript {  participants: readonly CommitParticipant[];  fault: CommitFault;}export interface CommitReport {  outcome: CommitOutcome;  /** Every participant's final standing. */  states: Readonly<Record<string, CommitNodeState>>;  balances: Readonly<Record<string, number>>;  /** Every participant ended the way the coordinator decided. */  atomic: boolean;  /** Messages sent over the wire: prepares, votes, decisions, and acknowledgements. */  messages: number;  /** Log forces, on every node together. */  forces: number;  /** Steps during which prepared participants held their locks with no decision to act on. */  blockedSteps: number;}/** * One transaction touches accounts on several machines and must end the * same way on all of them. Two-phase commit gets there with a * coordinator and two rounds of messages. Phase one: the coordinator * logs the transaction and asks every participant to prepare; each does * its work, forces a prepared record to its own log so the work survives * a crash, and votes yes, or votes no and rolls back at once. Phase two: * the coordinator decides commit only if every vote is yes, forces the * decision to its log, and sends it; each participant applies it, logs * it, and acknowledges. The logs are what make the protocol survive a * crash: a prepared participant that restarts finds its prepared record * and keeps waiting; a coordinator that restarts finds its decision and * resends it. The price is blocking: a participant that has voted yes * holds its locks until the decision arrives, however long the * coordinator is down. Presumed abort: a node that finds no decision * record on restart treats the transaction as aborted, so the * coordinator never has to log an abort before anyone has voted and a * participant with no prepared record can roll back on its own. * * Time: O(participants) messages per phase. Space: O(participants) log records. */export class TwoPhaseCommit {  private readonly logs = new Map<string, string[]>();  private readonly states = new Map<string, CommitNodeState>();  private readonly balances = new Map<string, number>();  private readonly votes = new Map<string, CommitVote>();  private decision: CommitOutcome | null = null;  private messages = 0;  private forces = 0;  private blockedSteps = 0;  private nextId = 1;  constructor(private readonly tracer?: Tracer) {}  /** A node's log so far; a copy. */  logOf(node: string): readonly string[] {    return [...(this.logs.get(node) ?? [])];  }  stateOf(node: string): CommitNodeState | null {    return this.states.get(node) ?? null;  }  /** Runs the whole protocol over one transaction, fault included, and reports how every participant ended. */  run(script: CommitScript): CommitReport {    this.validate(script);    this.reset(script);    const { participants, fault } = script;    const coordinator = COMMIT_COORDINATOR;    // The coordinator records who takes part before asking anyone, so a restart knows whom to tell.    this.force(coordinator, `prepare ${COMMIT_TX}`);    for (const participant of participants) {      // ▸ the coordinator asks a participant to do its work and promise it can commit      this.tracer?.emit("prepare", { id: this.message(), to: participant.name, delta: participant.delta });      if (fault.kind === "participant-crash" && fault.participant === participant.name) {        this.crash(participant.name, "participant");        continue;      }      const vote: CommitVote = participant.balance + participant.delta >= 0 ? "yes" : "no";      const reason = vote === "yes" ? "the work is done and logged" : `a debit of ${-participant.delta} exceeds the balance of ${participant.balance}`;      // A yes is a promise: the prepared record must be durable before the vote leaves. A no rolls back at once.      this.force(participant.name, vote === "yes" ? `prepared ${COMMIT_TX}` : `abort ${COMMIT_TX}`);      this.states.set(participant.name, vote === "yes" ? "prepared" : "aborted");      this.votes.set(participant.name, vote);      // ▸ the participant does the work, forces a prepared record, and votes yes; or finds it cannot, rolls back, and votes no      this.tracer?.emit("vote", { id: this.message(), from: participant.name, vote, reason, balance: participant.balance, delta: participant.delta });    }    const missing = participants.filter((participant) => !this.votes.has(participant.name)).map((participant) => participant.name);    // ▸ a vote never came, and silence counts as no: the coordinator stops waiting and will abort    if (missing.length > 0) this.tracer?.emit("timeout", { waitingFor: missing, decision: "abort" });    const yes = [...this.votes.values()].filter((vote) => vote === "yes").length;    const no = this.votes.size - yes;    let outcome: CommitOutcome = missing.length === 0 && no === 0 ? "commit" : "abort";    if (fault.kind === "coordinator-crash" && fault.when === "before-decision") {      this.crash(coordinator, "coordinator");      this.waitDown(fault.downFor);      // No decision was ever logged, so the restarted coordinator presumes abort.      this.recover(coordinator);      outcome = "abort";    }    this.force(coordinator, `${outcome} ${COMMIT_TX}`);    this.decision = outcome;    this.states.set(coordinator, outcome === "commit" ? "committed" : "aborted");    // ▸ commit only if every vote is yes; the decision is logged before anyone hears it    this.tracer?.emit("decide", { outcome, yes, no, missing: missing.length });    if (fault.kind === "coordinator-crash" && fault.when === "after-decision") {      this.crash(coordinator, "coordinator");      this.waitDown(fault.downFor);      // The decision record survived, so the restarted coordinator resends it.      this.recover(coordinator);    }    for (const participant of participants) {      if (this.states.get(participant.name) === "crashed") continue;      this.apply(participant, outcome, this.message());      this.force(participant.name, `${outcome} ${COMMIT_TX}`);      // ▸ the participant tells the coordinator the decision is applied, so the coordinator can forget the transaction      this.tracer?.emit("ack", { id: this.message(), from: participant.name, outcome });    }    this.force(coordinator, `done ${COMMIT_TX}`);    if (fault.kind === "participant-crash") {      const crashed = participants.find((participant) => participant.name === fault.participant)!;      this.waitDown(fault.downFor);      // Nothing prepared is in its log, so the restarted participant rolls back on its own and asks nobody.      this.recover(crashed.name);      this.apply(crashed, "abort", null);    }    return this.report(participants, outcome);  }  /** The disk against the decision: did every participant end the same way? */  private report(participants: readonly CommitParticipant[], outcome: CommitOutcome): CommitReport {    const states = Object.fromEntries(participants.map((participant) => [participant.name, this.states.get(participant.name) ?? "working"]));    const balances = Object.fromEntries(participants.map((participant) => [participant.name, this.balances.get(participant.name) ?? participant.balance]));    const wanted: CommitNodeState = outcome === "commit" ? "committed" : "aborted";    return { outcome, states, balances, atomic: participants.every((participant) => states[participant.name] === wanted), messages: this.messages, forces: this.forces, blockedSteps: this.blockedSteps };  }  /** The one place a record reaches a node's log: forced, so it is on disk before the next message leaves. */  private force(node: string, record: string): void {    const log = this.logs.get(node) ?? [];    const ownLog = this.logs.get(node) ?? [];    log.push(record);    ownLog.push(record);    this.logs.set(node, log);    this.logs.set(node, ownLog);    this.forces++;    // ▸ a record is forced to this node's own log before the next message leaves, so a restart can read what it had agreed to    this.tracer?.emit("log", { node, record, entries: log.length });    this.tracer?.emit("log", { node, record, entries: ownLog.length });  }  /** The next message's number in wire order. */  private message(): number {    this.messages++;    return this.nextId++;  }  /** The one place a participant acts on a decision: the account changes only on commit. Null id: a decision the participant reached alone on restart. */  private apply(participant: CommitParticipant, outcome: CommitOutcome, id: number | null): void {    const before = this.balances.get(participant.name) ?? participant.balance;    const balance = outcome === "commit" ? before + participant.delta : before;    this.balances.set(participant.name, balance);    this.states.set(participant.name, outcome === "commit" ? "committed" : "aborted");    // ▸ the participant commits or rolls back as told; only now does its account change    this.tracer?.emit("apply", { id, node: participant.name, outcome, balance });  }  /** A node loses its memory; its log stays. */  private crash(node: string, role: CommitRole): void {    const holding = this.held();    this.states.set(node, "crashed");    // ▸ the node loses its memory and its messages in flight; its log is all that survives    this.tracer?.emit("crash", { node, role, holding });  }  /** Participants that voted yes and have no decision yet: they hold their locks. */  private held(): string[] {    return [...this.states.entries()].filter(([, state]) => state === "prepared").map(([name]) => name);  }  /** Steps pass while a node is down; the one place blocking is observed. */  private waitDown(downFor: number): void {    for (let down = 1; down <= downFor; down++) {    for (let stepsDown = 1; stepsDown <= downFor; stepsDown++) {      const held = this.held();      if (held.length === 0) continue;      this.blockedSteps++;      // ▸ participants that voted yes hold their locks with no decision to act on, for as long as the coordinator is down      this.tracer?.emit("blocked", { participants: held, step: down, downFor });      this.tracer?.emit("blocked", { participants: held, step: stepsDown, downFor });    }  }  /** The node restarts and reads its own log: the last record says what to do. */  private recover(node: string): void {    const log = this.logs.get(node) ?? [];    const ownLog = this.logs.get(node) ?? [];    const found = log.at(-1) ?? "no record";    const lastRecord = ownLog.at(-1) ?? "no record";    let action: string;    if (node === COMMIT_COORDINATOR) {      action = this.decision === null ? "no decision logged, so presumed abort" : `resend ${this.decision}`;    } else {      action = found.startsWith("prepared") ? "prepared, so keep waiting for the decision" : "no prepared record, so roll back alone";      action = lastRecord.startsWith("prepared") ? "prepared, so keep waiting for the decision" : "no prepared record, so roll back alone";    }    this.states.set(node, node === COMMIT_COORDINATOR ? (this.decision === null ? "working" : this.decision === "commit" ? "committed" : "aborted") : found.startsWith("prepared") ? "prepared" : "working");    this.states.set(node, node === COMMIT_COORDINATOR ? (this.decision === null ? "working" : this.decision === "commit" ? "committed" : "aborted") : lastRecord.startsWith("prepared") ? "prepared" : "working");    // ▸ the node restarts and reads the last record of its log: a decision is resent, a prepared record keeps waiting, nothing means abort    this.tracer?.emit("recover", { node, found, action });    this.tracer?.emit("recover", { node, lastRecord, action });  }  private reset(script: CommitScript): void {    this.logs.clear();    this.states.clear();    this.balances.clear();    this.votes.clear();    this.decision = null;    this.messages = 0;    this.forces = 0;    this.blockedSteps = 0;    this.nextId = 1;    this.states.set(COMMIT_COORDINATOR, "working");    for (const participant of script.participants) {      this.states.set(participant.name, "working");      this.balances.set(participant.name, participant.balance);    }  }  private validate(script: CommitScript): void {    const { participants, fault } = script;    if (participants.length < MIN_COMMIT_PARTICIPANTS || participants.length > MAX_COMMIT_PARTICIPANTS) throw new RangeError(`participants must number ${MIN_COMMIT_PARTICIPANTS} to ${MAX_COMMIT_PARTICIPANTS}`);    const names = new Set(participants.map((participant) => participant.name));    if (names.size !== participants.length || names.has(COMMIT_COORDINATOR)) throw new RangeError("participant names must be unique and not the coordinator's");    for (const participant of participants) {      if (!Number.isInteger(participant.balance) || !Number.isInteger(participant.delta) || participant.balance < 0) throw new RangeError(`${participant.name} needs an integer balance of at least 0 and an integer delta`);    }    if (fault.kind === "participant-crash" && !names.has(fault.participant)) throw new RangeError(`${fault.participant} is not a participant`);    if (fault.kind !== "none" && (!Number.isInteger(fault.downFor) || fault.downFor < 1 || fault.downFor > MAX_COMMIT_DOWNTIME)) throw new RangeError(`downFor must be in [1, ${MAX_COMMIT_DOWNTIME}]`);  }}

outcome =: commit
atomic =: yes
messages =: 12
forces =: 9

Outcome: commit. bank A committed, bank B committed, bank C committed; balances bank A 70, bank B 40, bank C 60. 12 messages, 9 log forces, 0 steps spent blocked. Every participant ended the same way: the transaction was atomic across machines.

import type { Tracer } from "../trace";export const MIN_COMMIT_PARTICIPANTS = 2;export const MAX_COMMIT_PARTICIPANTS = 3;/** How many steps a crashed node may stay down before it restarts. */export const MAX_COMMIT_DOWNTIME = 4;export const COMMIT_COORDINATOR = "coordinator";/** The one transaction a run commits or aborts. */export const COMMIT_TX = "T1";export type CommitOutcome = "commit" | "abort";export type CommitVote = "yes" | "no";/** A node's standing: working before it votes, prepared while it holds locks and waits, then committed or aborted; crashed until it restarts. */export type CommitNodeState = "working" | "prepared" | "committed" | "aborted" | "crashed";export type CommitRole = "coordinator" | "participant";/** One participant: the account it keeps and what the transaction does to it. */export interface CommitParticipant { name: string; /** The account's balance before the transaction. */ balance: number; /** The transaction's change to the account; a debit past the balance makes the participant vote no. */ delta: number;}export type CommitFault = | { kind: "none" } /** The participant crashes before it votes and restarts after `downFor` steps. */ | { kind: "participant-crash"; participant: string; downFor: number } /** The coordinator crashes after logging its decision but before sending it, or after the votes but before deciding. */ | { kind: "coordinator-crash"; when: "after-decision" | "before-decision"; downFor: number };export interface CommitScript { participants: readonly CommitParticipant[]; fault: CommitFault;}export interface CommitReport { outcome: CommitOutcome; /** Every participant's final standing. */ states: Readonly<Record<string, CommitNodeState>>; balances: Readonly<Record<string, number>>; /** Every participant ended the way the coordinator decided. */ atomic: boolean; /** Messages sent over the wire: prepares, votes, decisions, and acknowledgements. */ messages: number; /** Log forces, on every node together. */ forces: number; /** Steps during which prepared participants held their locks with no decision to act on. */ blockedSteps: number;}/** * One transaction touches accounts on several machines and must end the * same way on all of them. Two-phase commit gets there with a * coordinator and two rounds of messages. Phase one: the coordinator * logs the transaction and asks every participant to prepare; each does * its work, forces a prepared record to its own log so the work survives * a crash, and votes yes, or votes no and rolls back at once. Phase two: * the coordinator decides commit only if every vote is yes, forces the * decision to its log, and sends it; each participant applies it, logs * it, and acknowledges. The logs are what make the protocol survive a * crash: a prepared participant that restarts finds its prepared record * and keeps waiting; a coordinator that restarts finds its decision and * resends it. The price is blocking: a participant that has voted yes * holds its locks until the decision arrives, however long the * coordinator is down. Presumed abort: a node that finds no decision * record on restart treats the transaction as aborted, so the * coordinator never has to log an abort before anyone has voted and a * participant with no prepared record can roll back on its own. * * Time: O(participants) messages per phase. Space: O(participants) log records. */export class TwoPhaseCommit { private readonly logs = new Map<string, string[]>(); private readonly states = new Map<string, CommitNodeState>(); private readonly balances = new Map<string, number>(); private readonly votes = new Map<string, CommitVote>(); private decision: CommitOutcome | null = null; private messages = 0; private forces = 0; private blockedSteps = 0; private nextId = 1; constructor(private readonly tracer?: Tracer) {} /** A node's log so far; a copy. */ logOf(node: string): readonly string[] { return [...(this.logs.get(node) ?? [])]; } stateOf(node: string): CommitNodeState | null { return this.states.get(node) ?? null; } /** Runs the whole protocol over one transaction, fault included, and reports how every participant ended. */ run(script: CommitScript): CommitReport { this.validate(script); this.reset(script); const { participants, fault } = script; const coordinator = COMMIT_COORDINATOR; // The coordinator records who takes part before asking anyone, so a restart knows whom to tell. this.force(coordinator, `prepare ${COMMIT_TX}`); for (const participant of participants) { // ▸ the coordinator asks a participant to do its work and promise it can commit this.tracer?.emit("prepare", { id: this.message(), to: participant.name, delta: participant.delta }); if (fault.kind === "participant-crash" && fault.participant === participant.name) { this.crash(participant.name, "participant"); continue; } const vote: CommitVote = participant.balance + participant.delta >= 0 ? "yes" : "no"; const reason = vote === "yes" ? "the work is done and logged" : `a debit of ${-participant.delta} exceeds the balance of ${participant.balance}`; // A yes is a promise: the prepared record must be durable before the vote leaves. A no rolls back at once. this.force(participant.name, vote === "yes" ? `prepared ${COMMIT_TX}` : `abort ${COMMIT_TX}`); this.states.set(participant.name, vote === "yes" ? "prepared" : "aborted"); this.votes.set(participant.name, vote); // ▸ the participant does the work, forces a prepared record, and votes yes; or finds it cannot, rolls back, and votes no this.tracer?.emit("vote", { id: this.message(), from: participant.name, vote, reason, balance: participant.balance, delta: participant.delta }); } const missing = participants.filter((participant) => !this.votes.has(participant.name)).map((participant) => participant.name); // ▸ a vote never came, and silence counts as no: the coordinator stops waiting and will abort if (missing.length > 0) this.tracer?.emit("timeout", { waitingFor: missing, decision: "abort" }); const yes = [...this.votes.values()].filter((vote) => vote === "yes").length; const no = this.votes.size - yes; let outcome: CommitOutcome = missing.length === 0 && no === 0 ? "commit" : "abort"; if (fault.kind === "coordinator-crash" && fault.when === "before-decision") { this.crash(coordinator, "coordinator"); this.waitDown(fault.downFor); // No decision was ever logged, so the restarted coordinator presumes abort. this.recover(coordinator); outcome = "abort"; } this.force(coordinator, `${outcome} ${COMMIT_TX}`); this.decision = outcome; this.states.set(coordinator, outcome === "commit" ? "committed" : "aborted"); // ▸ commit only if every vote is yes; the decision is logged before anyone hears it this.tracer?.emit("decide", { outcome, yes, no, missing: missing.length }); if (fault.kind === "coordinator-crash" && fault.when === "after-decision") { this.crash(coordinator, "coordinator"); this.waitDown(fault.downFor); // The decision record survived, so the restarted coordinator resends it. this.recover(coordinator); } for (const participant of participants) { if (this.states.get(participant.name) === "crashed") continue; this.apply(participant, outcome, this.message()); this.force(participant.name, `${outcome} ${COMMIT_TX}`); // ▸ the participant tells the coordinator the decision is applied, so the coordinator can forget the transaction this.tracer?.emit("ack", { id: this.message(), from: participant.name, outcome }); } this.force(coordinator, `done ${COMMIT_TX}`); if (fault.kind === "participant-crash") { const crashed = participants.find((participant) => participant.name === fault.participant)!; this.waitDown(fault.downFor); // Nothing prepared is in its log, so the restarted participant rolls back on its own and asks nobody. this.recover(crashed.name); this.apply(crashed, "abort", null); } return this.report(participants, outcome); } /** The disk against the decision: did every participant end the same way? */ private report(participants: readonly CommitParticipant[], outcome: CommitOutcome): CommitReport { const states = Object.fromEntries(participants.map((participant) => [participant.name, this.states.get(participant.name) ?? "working"])); const balances = Object.fromEntries(participants.map((participant) => [participant.name, this.balances.get(participant.name) ?? participant.balance])); const wanted: CommitNodeState = outcome === "commit" ? "committed" : "aborted"; return { outcome, states, balances, atomic: participants.every((participant) => states[participant.name] === wanted), messages: this.messages, forces: this.forces, blockedSteps: this.blockedSteps }; } /** The one place a record reaches a node's log: forced, so it is on disk before the next message leaves. */ private force(node: string, record: string): void { const log = this.logs.get(node) ?? []; const ownLog = this.logs.get(node) ?? []; log.push(record); ownLog.push(record); this.logs.set(node, log); this.logs.set(node, ownLog); this.forces++; // ▸ a record is forced to this node's own log before the next message leaves, so a restart can read what it had agreed to this.tracer?.emit("log", { node, record, entries: log.length }); this.tracer?.emit("log", { node, record, entries: ownLog.length }); } /** The next message's number in wire order. */ private message(): number { this.messages++; return this.nextId++; } /** The one place a participant acts on a decision: the account changes only on commit. Null id: a decision the participant reached alone on restart. */ private apply(participant: CommitParticipant, outcome: CommitOutcome, id: number | null): void { const before = this.balances.get(participant.name) ?? participant.balance; const balance = outcome === "commit" ? before + participant.delta : before; this.balances.set(participant.name, balance); this.states.set(participant.name, outcome === "commit" ? "committed" : "aborted"); // ▸ the participant commits or rolls back as told; only now does its account change this.tracer?.emit("apply", { id, node: participant.name, outcome, balance }); } /** A node loses its memory; its log stays. */ private crash(node: string, role: CommitRole): void { const holding = this.held(); this.states.set(node, "crashed"); // ▸ the node loses its memory and its messages in flight; its log is all that survives this.tracer?.emit("crash", { node, role, holding }); } /** Participants that voted yes and have no decision yet: they hold their locks. */ private held(): string[] { return [...this.states.entries()].filter(([, state]) => state === "prepared").map(([name]) => name); } /** Steps pass while a node is down; the one place blocking is observed. */ private waitDown(downFor: number): void { for (let down = 1; down <= downFor; down++) { for (let stepsDown = 1; stepsDown <= downFor; stepsDown++) { const held = this.held(); if (held.length === 0) continue; this.blockedSteps++; // ▸ participants that voted yes hold their locks with no decision to act on, for as long as the coordinator is down this.tracer?.emit("blocked", { participants: held, step: down, downFor }); this.tracer?.emit("blocked", { participants: held, step: stepsDown, downFor }); } } /** The node restarts and reads its own log: the last record says what to do. */ private recover(node: string): void { const log = this.logs.get(node) ?? []; const ownLog = this.logs.get(node) ?? []; const found = log.at(-1) ?? "no record"; const lastRecord = ownLog.at(-1) ?? "no record"; let action: string; if (node === COMMIT_COORDINATOR) { action = this.decision === null ? "no decision logged, so presumed abort" : `resend ${this.decision}`; } else { action = found.startsWith("prepared") ? "prepared, so keep waiting for the decision" : "no prepared record, so roll back alone"; action = lastRecord.startsWith("prepared") ? "prepared, so keep waiting for the decision" : "no prepared record, so roll back alone"; } this.states.set(node, node === COMMIT_COORDINATOR ? (this.decision === null ? "working" : this.decision === "commit" ? "committed" : "aborted") : found.startsWith("prepared") ? "prepared" : "working"); this.states.set(node, node === COMMIT_COORDINATOR ? (this.decision === null ? "working" : this.decision === "commit" ? "committed" : "aborted") : lastRecord.startsWith("prepared") ? "prepared" : "working"); // ▸ the node restarts and reads the last record of its log: a decision is resent, a prepared record keeps waiting, nothing means abort this.tracer?.emit("recover", { node, found, action }); this.tracer?.emit("recover", { node, lastRecord, action }); } private reset(script: CommitScript): void { this.logs.clear(); this.states.clear(); this.balances.clear(); this.votes.clear(); this.decision = null; this.messages = 0; this.forces = 0; this.blockedSteps = 0; this.nextId = 1; this.states.set(COMMIT_COORDINATOR, "working"); for (const participant of script.participants) { this.states.set(participant.name, "working"); this.balances.set(participant.name, participant.balance); } } private validate(script: CommitScript): void { const { participants, fault } = script; if (participants.length < MIN_COMMIT_PARTICIPANTS || participants.length > MAX_COMMIT_PARTICIPANTS) throw new RangeError(`participants must number ${MIN_COMMIT_PARTICIPANTS} to ${MAX_COMMIT_PARTICIPANTS}`); const names = new Set(participants.map((participant) => participant.name)); if (names.size !== participants.length || names.has(COMMIT_COORDINATOR)) throw new RangeError("participant names must be unique and not the coordinator's"); for (const participant of participants) { if (!Number.isInteger(participant.balance) || !Number.isInteger(participant.delta) || participant.balance < 0) throw new RangeError(`${participant.name} needs an integer balance of at least 0 and an integer delta`); } if (fault.kind === "participant-crash" && !names.has(fault.participant)) throw new RangeError(`${fault.participant} is not a participant`); if (fault.kind !== "none" && (!Number.isInteger(fault.downFor) || fault.downFor < 1 || fault.downFor > MAX_COMMIT_DOWNTIME)) throw new RangeError(`downFor must be in [1, ${MAX_COMMIT_DOWNTIME}]`); }}