Distributed transactions: 2PC & sagas

A travel site sells packages: a flight and a hotel, paid in one go. Its flights and hotels live in two separate databases, and the card is charged through a payment service. A customer books seat 14C and room 512 for $1,240:

Each database keeps its own writes all-or-nothing (Transactions & isolation levels). Nothing keeps the three together. The seat can be reserved and then the hotel turns out to be full. Or the trip service can crash after the seat and before the room. Either way the customer holds a seat with no hotel, or a room with no flight, or worse, a charge for neither.

What the trip needs is atomic commit across machines: either every part commits or none does. There are two families of answers, and they make opposite trades:

• Two-phase commit (2PC) keeps real atomicity and isolation, and pays with locks held across machines and waiting when the coordinator fails.
• Sagas commit each step at once and undo failures afterwards, and pay by giving up isolation.

In 2PC, one process acts as the coordinator: here, the trip service. The databases are participants. Each participant first does its part of the work inside an ordinary transaction, but doesn't commit. Then the coordinator runs two rounds:

The two phases:

• Prepare. The coordinator asks every participant: can you commit? A participant that can writes all its changes durably to disk, keeps its locks, and votes yes. That vote is a promise: from now on it must commit if told to, even after a crash and restart. Any participant may vote no instead.
• Commit or abort. If every vote was yes, the coordinator writes "commit" to its own log and tells everyone. If any vote was no, or a participant didn't answer in time, it tells everyone to abort.

Two points of no return make it work. A participant that votes yes gives up the right to abort on its own. The coordinator's log entry is the commit point: once it is on disk, the trip is committed, and the coordinator will keep sending "commit" until every participant has acknowledged it, through any number of crashes.

Counting shows the cost. Prepare, vote, decision and acknowledgment make four messages per participant:

2PC is a standard, not just an idea. XA is the interface that lets a transaction manager coordinate several databases. MySQL supports it, and PostgreSQL has PREPARE TRANSACTION. In PostgreSQL the feature is meant for an external transaction manager, not for applications, and it is switched off by default.

Suppose both databases vote yes and the trip service crashes before sending the decision:

A participant in this state is in doubt. It can't simply abort: the coordinator may have logged "commit" and told the hotels database, which has already committed. It can't commit: the coordinator may have decided to abort. Asking the other participants helps only if one of them heard the decision, or never voted yes. If all voted yes and none heard, everyone waits.

That is why 2PC is called a blocking protocol. Its failure isn't wrong data; it is locked data, for as long as the coordinator is down. If the coordinator's log is lost for good, an administrator has to resolve each in-doubt transaction by hand. A three-phase commit exists that avoids blocking, but only by assuming that delays are bounded, which real networks don't promise (Why distributed systems are hard).

The modern fix is to make the coordinator not a single machine. Distributed databases such as Spanner run 2PC where the coordinator and each participant are replicated groups that agree through consensus (Consensus & leader election). If one machine of a group dies, another takes over with the log intact, and nobody waits for a repair. Inside such a database, 2PC is simply how a write that spans shards commits.

The last cost is often decisive. The payment service, like most outside APIs, has no "prepare" call. You can't hold a charge in doubt and commit it later. Across services and companies, 2PC is usually not an option at all.

A saga splits the trip into a sequence of local transactions, each committed immediately in its own system. Every step has a compensating transaction: an action that semantically undoes it. If a later step fails, the saga runs the compensations for the steps already done, in reverse order:

A compensation is a new action, not a rollback. History stays visible: the seat was reserved, then canceled. Some steps can't be erased at all. A charge is undone with a refund, which the customer sees on their statement, and an email that was sent can only be followed by another email. That is why the order of steps matters, as the next section shows.

Something has to drive the sequence, and there are two styles:

Either way, two rules hold for every step:

• Steps and compensations must be idempotent. Messages get retried, so "cancel room 512" may arrive twice (Idempotency).
• Compensations must eventually succeed. "Cancel the seat" can't be allowed to fail for good; it is retried until it works, and a person is alerted if it keeps failing.

A saga is atomic in the end, but not isolated. Between the steps, other requests see committed data that may yet be undone. While our customer's card is being declined, seat 14C shows as taken. Another traveler who wanted it is turned away for a seat that is free again a second later. If a loyalty service awarded points for room 512 the moment it was reserved, those points now have to be clawed back.

These are the same anomalies as in a weakly isolated database: dirty reads of work that is later undone, and lost updates when two sagas overwrite each other. The defenses are design choices, not settings:

• A semantic lock. Mark the reservation PENDING until the saga finishes, so other code treats it as tentative: the loyalty service waits for CONFIRMED.
• Commutative updates. Prefer "add 1,240 points" to "set points to 9,240", so two sagas can apply theirs in either order.
• Re-read before writing. Check that the value is unchanged before updating it, and restart the step if it changed.

The most powerful defense is the order of the steps. Sort them into three kinds:

With this order, nothing that is hard to undo happens before the outcome is known. The email is never sent for a trip that will be canceled, because it comes after the charge. And no step after the charge has to be compensated, because none of them is allowed to fail permanently.

Look closely at one step. The flights service reserves the seat in its database, then sends "seat reserved" to the message broker so the saga can continue. That is two writes to two systems, the same problem in miniature:

• Commit, then send, then crash before sending. The seat is reserved and nobody hears about it. The saga stalls.
• Send, then commit, and the commit fails. The saga continues for a reservation that doesn't exist.

The fix is the transactional outbox. The service writes the message into an outbox table in its own database, in the same local transaction as the reservation. A separate relay reads new rows from the outbox and publishes them:

The relay either polls the outbox table or reads the database's change log. It marks a row as sent only after publishing, so if it crashes in between, it publishes that message again after the restart. The outbox therefore delivers at least once, and every consumer must handle duplicates. Delivery semantics takes that guarantee apart.

The cheapest distributed transaction is the one you design away. If the data that must change together can live in one database, a local transaction does the job. With sharding, that means choosing a key so that one operation's rows land on one shard (Sharding & partitioning). When it truly spans systems:

For a saga, the work is mostly up front: list every step, write its compensation, sort the steps into compensatable, pivot and retriable, and decide what other code may see while a saga is running. Then tell the customer the truth while it runs: "Booking your trip…" is an honest screen, and the confirmation comes when the saga finishes.