Two-Phase Commit Across Shards: The Coordinator, the Veto, and the In-Doubt Window

A transfer moves value from an account on shard 3 to an account on shard 7. Each shard can make its own half atomic; nothing local makes the pair atomic. If shard 3 commits and shard 7 aborts, the value has been destroyed, and both shards are individually consistent. Atomic commit across independent failure domains needs a protocol, and two-phase commit is the minimal one: a coordinator collects promises, then issues a decision. The protocol is simple. Its cost is that between the promise and the decision there is a window in which a participant has given up the right to decide for itself and does not yet know what was decided.

Prepare is a promise that costs a lock

Phase one sends a prepare request to every participant. Each participant, on receiving it, performs everything that can fail: it acquires the locks the transaction needs, checks every constraint, writes the changes to a private location that is not visible to other transactions, and flushes a prepare record to its own durable log. It then votes yes. If anything fails, it votes no and can abort immediately.

The distinction between “wrote to a private location” and “wrote nothing” is the whole point. A participant that has voted yes must be able to commit even if it crashes immediately afterwards and restarts — so the prepared state must be durable, and the work must be recorded in a form that survives a restart and can be completed without redoing the checks. In a page-oriented engine this is the undo/redo log: the participant has written redo records describing the new values and undo records describing the old, plus a prepare record marking the transaction as prepared. Recovery reads the prepare record and knows the outcome is not its decision to make.

Locks are held from prepare until the decision arrives. A row lock held across a network round trip blocks other transactions on that row for the duration, and if the coordinator is slow or unreachable the duration is unbounded. This is the first concrete cost: two-phase commit converts a local lock hold measured in microseconds into a distributed lock hold measured in round trips, and under contention the blocking chain grows.

The decision is a durable fact, not a message

Phase two is short: the coordinator writes a commit or abort record to its own log, then sends the decision to every participant. Each participant applies or undoes, releases its locks, and acknowledges.

The important asymmetry is that the decision is written before it is sent. If the coordinator crashes after writing “commit” and before any participant hears it, recovery must resend “commit”. If it crashes before writing anything, recovery must abort — the transaction never reached a decision, and no participant can have committed, because a participant only commits on an explicit instruction. This is why the coordinator’s log entry is the single point of truth, and why losing the coordinator’s log is losing the transaction.

The protocol’s safety rests on one invariant: a participant that voted yes cannot unilaterally abort, and a participant that voted no cannot be forced to commit. The first half is what makes the coordinator’s commit decision binding; the second half is what makes a veto meaningful. A participant that has prepared but heard nothing holds locks and waits, which is the in-doubt state.

The in-doubt window and why it cannot be closed by timeout

The participant in doubt has two options and both are wrong in some scenario.

If it waits, it holds locks indefinitely. Other transactions block behind those locks, and the blocking is transitive: the participant’s own local transactions queue, and any transaction that needs a row it locked queues behind them. A single unreachable coordinator can therefore stall a shard’s write path for as long as the coordinator stays down, even though the shard is healthy and every other transaction on it is unrelated.

If it aborts, it may contradict a decision the coordinator already made and possibly already delivered to another participant. Participant A aborts, participant B commits, and the transaction is half-applied — precisely the outcome the protocol exists to prevent. So a participant in doubt may not abort, and may not commit, and may not forget.

The only correct resolution is to learn the decision, which means the decision must be recoverable from somewhere other than the failed coordinator’s memory. Three mechanisms are used.

Presumed abort removes the need to ask in one direction. The coordinator does not log an abort decision at all; the absence of a commit record is the abort. A participant that recovers in doubt, or that never received a decision, can safely abort if the coordinator has no commit record — but only if it can determine that, which requires either asking a coordinator that is reachable or waiting past a point at which a commit record could still appear. Presumed abort reduces log writes, since the common case of a rollback needs no second record, and it is the reason many implementations only durably log commits.

Presumed commit is the mirror: the coordinator logs the decision before prepare, and participants presume commit when they cannot reach it. It saves a round trip in the commit case and is unsafe unless the prepared work is guaranteed to be completable, because a participant that presumes commit must be able to commit even if it never actually prepared.

Coordination through a replicated log. The decision is written to a log that survives the coordinator’s failure, typically a consensus-replicated log held by an odd-numbered group. A recovering participant asks the group, not the process, and the group answers with the decision. This is the only mechanism that closes the window fully, and it is what systems built on replicated state machines do: each participant’s state, including whether it has prepared, lives in a consensus-replicated group, so a participant that loses its leader recovers the prepared state from the group rather than from a local log. Spanner’s participants follow this shape, with each participant group’s state replicated independently of the coordinator’s process lifetime.

coordinator log:
  T1: BEGIN
  T1: PREPARE shard3, shard7
  T1: COMMIT            <- the durable decision; sent after this record exists

participant (shard7) log:
  T1: PREPARE           <- after this, the participant must not abort
  T1: COMMIT | ABORT    <- only after hearing from the coordinator

in-doubt: PREPARE present, no decision record, coordinator unreachable

A participant in the in-doubt state is visible in the engine’s own metadata. PostgreSQL exposes prepared transactions in pg_prepared_xacts with their age, and the age is the operational signal: a prepared transaction that has been open for hours is either a coordinator that never returned or a bug, and either way it is holding locks. Resolving it by hand is a decision about someone else’s transaction, and the only safe input is the coordinator’s log.

Two-phase commit does not provide isolation across shards

Atomicity and isolation are separate guarantees, and two-phase commit supplies only the first. Consider a transaction that reads a row on shard 3, then writes a row on shard 7. Nothing in the protocol prevents another transaction from reading the shard-7 row and the shard-3 row in an order that produces a cycle. Each shard’s local serialiser orders its own operations; the union of two serial orders is not necessarily a serial order.

The failure is a write skew across shards, and it is not detectable locally. Preventing it requires a global serialisation point: a timestamp service that assigns each transaction a position in a single order, with participants validating against it, or a global lock manager. Spanner does the former with its TrueTime-based timestamps and commit-wait; systems without a bounded-clock primitive either accept the anomaly or restrict cross-shard transactions to a form that cannot exhibit it.

The practical consequence is that cross-shard transactions are expensive not because of the two-phase commit round trips, but because making them correct requires a global order that the shards do not otherwise share. That is why the usual advice is to design the partition key so that the transactions that must be atomic touch one shard, and to treat cross-shard atomicity as a fallback. Choosing a partition key is therefore a transaction-design decision, not merely a distribution one.

Three-phase commit and the reason it is rare

Three-phase commit adds a pre-commit phase so that a participant in doubt can consult its peers and reach a decision without the coordinator. The added phase makes the protocol non-blocking under a coordinator failure, at the cost of one more round trip for every transaction and a correctness argument that depends on the network not partitioning in a particular way. In an asynchronous network with partitions, no protocol can guarantee both non-blocking and safe termination — the result is a known impossibility, and three-phase commit does not escape it; it merely moves the assumption.

What has displaced it is the replicated coordinator: instead of adding phases, make the decision’s home a majority-replicated log. That converts the coordinator failure into an ordinary leader election, at the cost of the consensus round trip that the election and the append require. The latency profile is one wide-area round trip for the decision plus one for the prepare, which is why systems that offer cross-shard transactions across regions describe commit latency in terms of that round trip rather than in terms of local work.

Where the participants’ own replication fits

Each participant is itself replicated, and its prepare vote is only meaningful if the prepared state survives the participant’s own failure. That means the prepare record must be durable on enough replicas to survive a failover, which ties the commit protocol’s latency to the replication mode in the commit boundary. A participant that votes yes after writing the prepare record to a single leader, asynchronously replicated, can lose the prepared state on failover and then vote again — or worse, be unable to honour a commit it promised.

The composition is the reason cross-shard commit is expensive in practice: one logical commit becomes a prepare round trip, a decision append through consensus, and a durable local prepare on each participant, each of which may itself be a replicated write. The protocol is not complex. Its cost is the number of durable boundaries it has to cross, and every one of them is there because the alternative is a half-applied transaction.