Two-phase, three-phase and Paxos commit

Why does two-phase commit block?

Two-Phase Commit (2PC)

Phase 1 — prepare. The coordinator (the machine that drives the transaction) asks each participant (a machine holding part of the data) whether it can commit. A participant that votes yes first makes durable everything it needs to go either way (data and locks survive a crash), and then replies. That act, surrendering the right to abort unilaterally, is the real content of 2PC. Everything else is messaging. After voting yes, a participant has promised: "I will do whatever you decide, even if I crash and restart."

Phase 2 — decide. The coordinator collects the votes. It forces its decision to its own log, and then sends the decision to everybody. That single forced write is the commit point of the distributed transaction: it is the designated write of Transaction mechanics, now living on a machine that most of the writes are not on.

coordinator              participant A            participant B
    | -- prepare ------------> |                        |
    | -- prepare ------------------------------------>  |
    | <-- vote yes ----------- | (A forces its log)     |
    | <-- vote yes ------------------------------------ | (B forces its log)
    | (forces COMMIT decision to its own log)  <-- the commit point
    | -- commit -------------> |                        |
    | -- commit ------------------------------------->  |

The cost accounting, done honestly

Latency is two round trips plus two forced log writes on the critical path. The participants' prepare forces happen in parallel; the coordinator's decision force is serial. Between availability zones in one region (RTT about 1–2 ms) this is roughly 2–4 ms plus the fsyncs. That is not a disaster, and "2PC is slow" is a lazy claim.

The cost that really hurts is lock hold time. Locks are held from the start of the transaction, through prepare, through the decision, through the acknowledgment. So W grows by roughly two round trips. And W enters the conflict formula squared, through L = λW. A cross-region 2PC at 70 ms RTT holds locks for about 150 ms (2 × 70 ms plus local work and fsyncs). At that W, any contended row collapses. Worked example: if a popular row used to be locked for 5 ms, 200 transactions per second could in theory use it one after another (1 / 0.005). At 150 ms, the same row allows 1 / 0.15 ≈ 6.7 per second. The latency does not kill you directly. It kills you through the quadratic. This is the single most useful thing to carry from Why concurrency is different into this article.

Availability is Aⁿ, as shown above.

The blocking window is the fatal property. Suppose the coordinator dies after a participant voted yes but before the decision reached it. That participant can neither commit (someone else may have voted no) nor abort (everyone may have voted yes, and another participant may already have committed). It holds its locks until the coordinator comes back. The in-doubt window that was microseconds on one node is now unbounded, and it holds hostage every transaction that wants those locks.

Partial escapes, with their limits

• Cooperative termination: participants ask each other. Any participant that learned the decision can tell the rest. But if every survivor is in the prepared state and the coordinator is gone, nobody knows. This helps in the common case and not in the worst one.
• Timeout and guess is unsafe. It is not an option if you want atomicity.
• That leaves making the coordinator fault-tolerant, which is the next section.

Presumed abort

To avoid forcing records and sending acknowledgments that you do not need, adopt a default: if recovery finds no record of a transaction, presume it aborted. This spares the coordinator from force-writing abort decisions, and spares participants from acknowledging them. Presumed commit is the mirror image: cheaper for the common case (commit) but it needs a forced record before prepare, so it spends a log write to save messages. Presumed abort is what nearly everyone ships, including the XA standard (the industry interface for 2PC between a transaction manager and resource managers such as databases and queues). A protocol that aborts at any doubt should make aborting the cheap path.

The ending that textbooks leave out: heuristic decisions

Real XA deployments include heuristic decisions. An operator or a resource manager can unilaterally resolve an in-doubt transaction (commit it or roll it back by hand), knowingly risking a violation of atomicity. The standard reserves an error code for exactly that outcome ("heuristic mixed"). The guarantee has a documented escape hatch because unbounded blocking is operationally worse than a rare inconsistency that someone reconciles by hand. That is the honest answer to "who pays": an operator, manually, later.

Three-Phase Commit and Paxos-commit

3PC inserts a pre-commit phase, so that a participant can infer the decision from its own state plus the state of enough others. It buys non-blocking behaviour under fail-stop failures (machines that stop cleanly), a synchronous network (bounded message delay) and accurate failure detection. It costs a third round trip, and it is unsafe under network partition: a partition looks the same as a failure, and the two sides can reach different decisions. Real networks do partition, so 3PC has essentially no production use. Treat it as a teaching device that shows what non-blocking would require, not as an option.

Paxos-commit (Gray and Lamport, 2006) is the real answer, and its framing is the most compressed statement in this article. 2PC blocks because each critical piece of state (each participant's vote, the coordinator's decision) lives in exactly one place. So replicate each of them using consensus. Then no single failure can lose or hide a vote, and the protocol is non-blocking as long as a majority of each replica group survives.

Their own summary: 2PC is Paxos-commit in which every Paxos instance has exactly one acceptor. (An acceptor is a replica that votes in a consensus round.) This turns 2PC from a different protocol into a degenerate configuration, and immediately explains the blocking: a group of one acceptor has no fault tolerance, by construction.

How to read modern systems: they do not choose between 2PC and consensus. They layer them. Spanner runs 2PC across participant groups, where each participant group is itself a Paxos group. So a prepare record is replicated before the vote is sent and cannot be lost, and the coordinator is a Paxos group too. CockroachDB, TiDB and YugabyteDB are variations of the same stack. "2PC versus Raft" is a category error. The design that ships is 2PC over replicated participants.

Recompute the availability with three-way replication per participant. Each group moves from 0.999 to about 0.999997 (it fails only when two of its three replicas are down at once: 1 − 3 × 0.001²). Ten participants then give about 0.99997 instead of 0.99. The shape of the arithmetic is unchanged: it still degrades geometrically in n. But the base moved by several nines. This is "costs are conserved, never removed": the cost was relocated into replication hardware and consensus latency, and the exponent is still waiting for you at large n.