Distributed transactions, sagas and the outbox pattern

The problem: one business action, several databases

Inside one database, a transaction makes several changes atomic: the order row, its items and the payment reference are all saved or none are (Section 0.5). Once data is split across services that each own their database, as microservices and database per service recommend, a single business action such as placing a food order touches several databases owned by different services: the order service's, the payment service's and the dispatch service's. No single local transaction can cover them all.

There are two families of answer. One is to make many resource managers act as one through a distributed atomic commit protocol, of which two-phase commit is the classic. The other is to accept that the action is a sequence of local transactions and design for the moments in between: the saga. A third answer, often the best, is to notice that the transaction boundary and the service boundary disagree and to move one of them. This section covers all three and ends with a guide for choosing.

Two-phase commit and XA

Two-phase commit (2PC) is a protocol, dating from the late 1970s, that gives all-or-nothing atomicity across several participants such as two databases or a database and a message broker. A coordinator (the transaction manager) runs it. In phase 1, prepare, the coordinator asks every participant whether it can commit. A participant that says yes must first make the changes durable and keep the relevant locks, because by voting yes it gives up the right to abort on its own. If every vote is yes, the coordinator writes its decision, COMMIT, to its own log; if any vote is no or a participant does not answer, the decision is ABORT. In phase 2, commit, it tells every participant the outcome, and they apply it and release their locks.

The weakness is that 2PC is a blocking protocol. A participant that has voted yes is in doubt: it does not know the outcome and cannot safely guess, because another participant may already have committed. If the coordinator crashes at that moment and stays down, the in-doubt participants keep their locks until it recovers, and other transactions touching those rows wait too. Operators can force a heuristic decision to release the locks, at the risk of breaking atomicity.

The XA specification, published by X/Open in 1991, standardised the interface between a transaction manager and resource managers so that, for example, a Java application server can commit a database update and a message send atomically. Many relational databases and some message brokers support it.

Why 2PC is avoided across microservices

2PC works and is still used inside a single system's boundary. Across independently owned services it is usually a poor fit, for reasons that compound each other.

Availability multiplies down. Every participant and the coordinator must be up for any transaction to commit, so the transaction's availability is the product of theirs, the same arithmetic as a synchronous call chain (see why distribute). Locks are held across the network for at least two round trips, and much longer if anything is slow, which cuts throughput and raises contention. Coupling returns: all participants must speak the same protocol, share a transaction manager and agree on timeouts, which undermines the independent deployability that justified splitting the services. Many participants cannot join: most HTTP APIs, third-party services such as payment providers, many NoSQL databases and several popular brokers do not support XA. And the payment provider's API will never hold a lock for your coordinator.

The picture is different inside distributed databases. Systems such as Google Spanner run two-phase commit internally between groups of replicas that are themselves kept consistent by consensus, so a crashed coordinator is replaced rather than awaited. That makes cross-partition transactions within one database practical; it does not make transactions across separately owned services and their different technologies practical.

Sagas: a sequence of local transactions

Hector Garcia-Molina and Kenneth Salem introduced the saga in a 1987 SIGMOD paper about long-lived transactions, ones that would hold database locks for hours. Their idea was to split such a transaction into a sequence of ordinary transactions T₁, T₂ … T_n, each of which commits on its own, and to pair each with a compensating transaction C_i that semantically undoes it. The system then guarantees that either the whole sequence completes, or the completed steps are followed by their compensations in reverse order: T₁ … T_j, C_j … C₁.

Microservice architectures adopted the idea because it fits their constraints exactly: each step is a local ACID transaction in one service's own database, and steps are linked by messages. A saga gives atomicity in the eventual, business sense (all steps happen, or the effects are undone), but not isolation: between steps, other transactions can see the intermediate state.

It helps to classify the steps, as Chris Richardson does in Microservices Patterns (2018). Compensatable transactions can be undone by a compensation. The pivot transaction is the go/no-go point: once it commits, the saga will run to completion. Retriable transactions come after the pivot and must be designed so that they eventually succeed if retried. Placing steps that are likely to fail before the pivot, and steps that cannot be undone after it, is a key design decision.

Choreography or orchestration

A saga's steps must be coordinated somehow, and the two options mirror the choreography and orchestration discussed in event-driven architecture.

In a choreography-based saga there is no coordinator. Each service listens for events and reacts by doing its local transaction and publishing a new event: the order service publishes OrderCreated, the payment service reacts and publishes PaymentAuthorised, the dispatch service reacts to that, and so on; failure events trigger compensations in the services that listen for them. It is simple for two or three steps and keeps services loosely coupled. As steps grow, the flow exists only implicitly, scattered across services, so it is hard to see, test and change; and cyclic event dependencies between services creep in.

In an orchestration-based saga a single orchestrator, usually in the service that owns the business process, sends commands to participants and reacts to their replies. The orchestrator is a persistent state machine: it records which step it is on in its own database, so it can resume after a crash. The flow is explicit and testable in one place, and participants need not know about each other. The risk is that the orchestrator accumulates business logic that belongs in the participants. Workflow engines such as Temporal, Camunda and AWS Step Functions provide durable orchestration as a platform, at the cost of another dependency. For more than about three steps, or for any flow with branching and timeouts, most practitioners prefer orchestration.

Worked example: the order saga

The food-delivery platform's order saga is orchestrated by the order service. The order of steps is deliberate: the payment authorisation is a cheap hold that is easy to void, the courier reservation is the step most likely to fail at busy times, and confirming to the restaurant is the pivot, because once a kitchen has started cooking the order cannot simply be undone.

Compensation is not rollback

A database rollback makes it as if the transaction never happened: nobody else ever saw its changes. A compensation is a new, forward transaction that semantically counteracts an earlier one that did happen and may have been seen. In the order saga, the customer's bank may already show a pending hold, and an email may have said "payment authorised". The compensation cannot unsend the email; it can only void the hold and send another message. Some actions cannot be compensated at all, such as food already cooked or a notification already read; those belong after the pivot, or need a business compensation such as a voucher or a refund.

Compensations therefore need the same care as forward steps. They must be idempotent, because the message that triggers them may be delivered twice. They must be retriable until they succeed, because a compensation that fails permanently leaves the system in a state nobody designed; if they truly cannot succeed, they must raise an alert for a person to resolve. They may need to be commutative with the forward step: if a VoidAuthorisation arrives before the AuthorisePayment it undoes (possible after timeouts and retries), the payment service should remember the void and refuse the late authorisation rather than fail. And they should be visible to the business: "rejected, no courier" is information the operations team wants on a dashboard.

Living without isolation: anomalies and countermeasures

Because each step commits on its own, sagas lack the I in ACID, and concurrent sagas can interfere. Richardson describes three resulting anomalies. A lost update occurs when one saga overwrites a change made by another without reading it, such as a cancellation saga marking an order cancelled and the order saga then setting it confirmed. A dirty read occurs when a saga reads data another saga has changed but may yet compensate, such as a credit-limit check that counts a hold that is about to be voided. A fuzzy or non-repeatable read occurs when two steps of one saga read the same data and get different values because another saga changed it in between.

He also catalogues countermeasures, design techniques that reduce the anomalies, drawing on earlier research on transactions across multiple databases. The most widely used are these.

Publishing reliably: the transactional outbox

Every saga step does two things: it updates its own database and it sends a message (an event or a reply). Doing them separately creates the dual-write problem. If the service commits and then crashes before publishing, the rest of the saga never hears about the step. If it publishes first and the commit then fails, other services act on something that never happened. Wrapping the database and the broker in 2PC is exactly what we wanted to avoid.

The transactional outbox solves it with one local transaction. The service writes the business change and the outgoing message, as a row in an outbox table, in the same database transaction; either both commit or neither does. A separate relay then reads the outbox and publishes each message to the broker. Two relay designs are common. A polling publisher queries the outbox table for unpublished rows every so often and marks them sent: simple, but it adds load and latency. Transaction log tailing uses change data capture (CDC): a tool reads the database's own replication log (the PostgreSQL write-ahead log or the MySQL binary log) and turns new outbox rows into messages. Debezium, an open-source CDC platform usually run with Kafka Connect, is the best-known example and includes an outbox event router that routes each row to a topic based on a column such as the aggregate type.

The relay can crash after publishing and before recording that it did, so it will sometimes publish a message twice. The outbox therefore gives at-least-once delivery, and consumers must cope with duplicates. Publishing order is preserved per aggregate if the relay publishes rows in commit order and uses the aggregate ID as the message key.

BEGIN;

INSERT INTO orders (id, customer_id, state, total_pence)
VALUES ('1042', 'c-77', 'PENDING', 2350);

INSERT INTO outbox (id, aggregate_type, aggregate_id, type, payload)
VALUES ('e-9f1c', 'order', '1042', 'OrderCreated',
        '{"orderId":"1042","customerId":"c-77","totalPence":2350}');

COMMIT;
-- A relay (poller or CDC such as Debezium) later publishes e-9f1c to the broker.

Receiving reliably: idempotent receivers and the inbox

Because the outbox, broker retries and saga retries all produce duplicates, every participant must be an idempotent receiver, the name Gregor Hohpe and Bobby Woolf gave the pattern in Enterprise Integration Patterns (2003). Some operations are naturally idempotent ("set order 1042 to CONFIRMED"); others need a duplicate check. The usual implementation is an inbox: a table of processed message IDs, written in the same local transaction as the business change, so that "process the message" and "remember that it was processed" commit together. A redelivered message finds its ID already present and is acknowledged without doing anything. The consumer-side code appears in event-driven architecture.

Together, outbox, at-least-once delivery and idempotent receivers give the practical result people usually mean by "exactly once": each business effect happens once, even though messages may travel more than once.