Sagas

A long-lived transaction (LLT) takes hours or days: producing monthly bank statements, processing an insurance claim, booking several flights while the customer decides between each one. As an ordinary atomic transaction, it holds locks on everything it touched until it commits. Short transactions queue behind it. Deadlocks become far more likely: in the analysis the authors cite, deadlock frequency grows with the fourth power of the number of objects a transaction touches. And a transaction that runs for hours is more likely to be hit by a crash and aborted.

Hector Garcia-Molina and Kenneth Salem at Princeton observed that many LLTs do not need full atomicity. A booking transaction can let others reserve seats on a flight right after it reserves its own. What it needs is that the whole booking either completes, or any reservations it made are cancelled.

They named the structure a saga: a sequence of ordinary transactions T1 … Tn that may interleave with other transactions. Each Ti except the last has a compensating transaction Ci that undoes it semantically. To undo a seat reservation, Ci subtracts one from the reservation count; it does not write back the count Ti saw, because other transactions may have changed it since. The database guarantees that either T1, …, Tn all execute, or T1, …, Tj execute followed by Cj, …, C1.

There is no isolation at the saga level: other transactions can see a saga's partial results, and when a step is compensated, nobody tells them. A saga is like a nested transaction with only two levels and no atomicity at the top.

The paper then works through the machinery: commands for programs to declare sagas and their compensations, storing saga code reliably, backward recovery (compensate) and forward recovery (resume from a save-point), what to do when a compensation itself fails, how to run sagas on an existing database with tables and a background daemon, parallel sagas, and how to design databases and transactions so that long work can be written as sagas.

An agent that books travel, provisions accounts, places orders or updates records across several systems is running a long-lived transaction across services that do not share a transaction manager. There is no global rollback. Sagas are the pattern that makes such work safe.

Every state-changing tool needs a compensation. For each action the agent can take (create a ticket, reserve a room, charge a card), define the action that undoes it in business terms (close the ticket, cancel the reservation, issue a refund), and when it may run.

Compensate, do not restore. Writing back the value you saw before is wrong whenever anyone else touched the record since. Undo the meaning of your step.

Expect others to see half-done work. Between steps, other users and agents can read your partial results. Design the in-between states so that they are valid, as the paper's "funds in transit" advice does.

Some actions cannot be undone. The paper's example is firing a missile; for agents it is sending an email or a payment. Put irreversible steps last, or behind human approval.