Distributed transactions: 2PC, consensus, sagas

A distributed transaction changes data on more than one server and must take effect on all of them or on none. Two-phase commit (2PC) does it with a coordinator: first every participant does its work, records that it is prepared and votes; then the coordinator logs the decision, commit only if every vote was yes, and tells the participants. Its weakness is waiting: a participant that has voted yes may not decide alone, so if the coordinator fails before telling it, the participant keeps its locks until the coordinator returns. Consensus protocols such as Paxos and Raft solve a different problem: they keep the replicas of one log in agreement while a minority of them fails. They keep each shard available but cannot make two shards commit together, so systems that need both combine them. A saga gives up atomic commit altogether: one local transaction per service, and compensating actions that undo the earlier steps when a later one fails.

Two-phase commit, step by step

In the first phase, each participant runs its part of the transaction, writes a prepare record to its own log and only then votes yes, a promise that it can commit even after a crash. In the second phase the coordinator writes its decision to its log. That record is the commit point: before it the transaction can still be aborted, after it the transaction will commit, whatever fails. The coordinator then sends the decision, and each participant commits or aborts and releases its locks. One no vote, or a vote that does not arrive in time, makes the decision abort. A coordinator that presumes abort reads a missing decision in its log as abort.

Where two-phase commit blocks

The simulator below runs one transaction with two participants, A and B, and injects one crash at each step of the protocol. Each crash lasts 30 seconds, and every party’s log survives it:

"""Two-phase commit between a coordinator and two participants, A and B, with one crash injected at each step.

Each party keeps a log that survives its crash. A participant that has voted yes may not decide alone: it waits for
the decision, and its locks stay held while it waits. The coordinator presumes abort: after a crash, a transaction
with no decision in its log is aborted. Every crash here lasts 30 seconds."""

CRASH_SECONDS = 30


class Participant:
    def __init__(self, name, vote="yes"):
        self.name, self.vote, self.log, self.state = name, vote, [], "working"

    def prepare(self):
        if self.vote == "yes":
            self.log.append("prepared")  # forced to disk before the vote is sent
            self.state = "prepared"
        else:
            self.state = "aborted"
        return self.vote

    def decide(self, decision):
        self.log.append(decision)
        self.state = "committed" if decision == "commit" else "aborted"


def run(crash):
    """Runs one transaction; `crash` names who crashes and where. Returns the outcome and who waited."""
    a, b = Participant("A"), Participant("B", vote="no" if crash == "B votes no" else "yes")
    coordinator_log = []
    waited = []
    if crash == "coordinator, before sending prepare":
        # Nobody has voted, so the participants time out and abort on their own.
        for p in (a, b):
            p.decide("abort")
        return a, b, waited
    votes = []
    for p in (a, b):
        if crash == "A, before voting" and p is a:
            votes.append("none")  # the coordinator times out waiting for A
            continue
        votes.append(p.prepare())
    decision = "commit" if votes == ["yes", "yes"] else "abort"
    if crash == "coordinator, after the votes, before logging":
        waited = [p.name for p in (a, b) if p.state == "prepared"]
        decision = "commit" if ("commit" in coordinator_log) else "abort"  # presumed abort on recovery
        for p in (a, b):
            if p.state == "prepared":
                p.decide(decision)
        return a, b, waited
    coordinator_log.append(decision)  # the commit point
    if crash == "coordinator, after logging, before sending":
        waited = [p.name for p in (a, b) if p.state == "prepared"]
        for p in (a, b):
            if p.state == "prepared":
                p.decide(coordinator_log[-1])  # sent once the coordinator is back
        return a, b, waited
    for p in (a, b):
        if crash == "coordinator, after telling A only" and p is b:
            waited = ["B"]
            continue
        if p.state == "prepared":
            if crash == "A, after voting yes" and p is a:
                waited = ["A"]  # down for 30 s, then asks the coordinator, which answers from its log
            p.decide(decision)
    if crash == "coordinator, after telling A only":
        b.decide(coordinator_log[-1])
    if crash == "A, before voting":
        a.decide("abort")  # A comes back with no prepare record, so it aborts
    return a, b, waited


SCENARIOS = [
    "no crash",
    "B votes no",
    "coordinator, before sending prepare",
    "A, before voting",
    "A, after voting yes",
    "coordinator, after the votes, before logging",
    "coordinator, after logging, before sending",
    "coordinator, after telling A only",
]

print(f"{'crash':<46} {'A':<10} {'B':<10} prepared, holding locks for {CRASH_SECONDS} s")
for crash in SCENARIOS:
    a, b, waited = run(crash)
    assert a.state == b.state, "atomicity broken"
    print(f"{crash:<46} {a.state:<10} {b.state:<10} {', '.join(waited) or '-'}")
print()
print("A and B ended in the same state every time: commit or abort is all or nothing.")
print("Every wait comes after a yes vote, while the decision was out of reach of the participant.")

crash                                          A          B          prepared, holding locks for 30 s
no crash                                       committed  committed  -
B votes no                                     aborted    aborted    -
coordinator, before sending prepare            aborted    aborted    -
A, before voting                               aborted    aborted    -
A, after voting yes                            committed  committed  A
coordinator, after the votes, before logging   aborted    aborted    A, B
coordinator, after logging, before sending     committed  committed  A, B
coordinator, after telling A only              committed  committed  B

A and B ended in the same state every time: commit or abort is all or nothing.
Every wait comes after a yes vote, while the decision was out of reach of the participant.

A and B ended in the same state every time, so atomicity held. What differs is the waiting. Before a participant has voted yes it may still abort on its own, which is why the early crashes end in a quick abort. After a yes vote it may not: the coordinator might already have logged a commit. So in the three crashes of the coordinator after the votes, the prepared participants waited out the whole crash with their locks held. When the coordinator had told A only, B could also have asked A for the outcome; that only works while another participant is reachable and knows it. PostgreSQL implements the participant’s side with PREPARE TRANSACTION, COMMIT PREPARED and ROLLBACK PREPARED, and ships with the feature turned off: max_prepared_transactions is 0 by default (PostgreSQL 18 manual, 19.4).

Consensus is not two-phase commit

Paxos lets a set of acceptors choose one value even when some of them fail, and accepts a value once a majority has accepted it; any two majorities share a member, so two different values can never both be chosen (Lamport). Raft builds a replicated log on the same idea: an elected leader appends entries, and an entry is committed once a majority of servers store it (Ongaro and Ousterhout). Five servers keep working with two of them down. Two-phase commit needs something else. It needs every participant’s yes, because each participant checks its own data and may refuse: a balance that would go negative on one shard must stop the transfer on the other. A majority cannot outvote that refusal. What consensus can fix is the waiting: if the coordinator’s log is itself replicated by consensus, a coordinator crash no longer hides the decision, since another replica of the coordinator takes over. Google’s Spanner is built that way: two-phase commit runs between groups that are each replicated by Paxos (Corbett et al.).

Sagas and the outbox

A saga is a sequence of local transactions, each with a compensating transaction that undoes it in the business sense; the system runs all the steps, or runs some and then their compensations in reverse order (Garcia-Molina and Salem). Nothing is held between steps, so other transactions see a saga’s intermediate states, and the design must allow for that. Services then need a reliable way to send each other the next step. An outbox is a table in the service’s own database: the message is written in the same local transaction as the change it announces, and a relay publishes it afterwards. The relay may publish a message twice, so each consumer keeps an inbox of the messages it has handled and applies each one once.

Exercise

"""Decisions in two-phase commit with presumed abort."""


def decide(votes):
    """'commit' when every vote is 'yes', else 'abort' (a missing vote is None)."""
    # Replace this line with your code.
    return None


def may_abort_alone(state):
    """True when a participant in this state may abort on its own while the coordinator is silent."""
    # Replace this line with your code.
    return None


def recover(log, gid):
    """The decision a restarted coordinator gives for gid: from its log, or 'abort' when none is logged."""
    # Replace this line with your code.
    return None

from two_phase import decide, may_abort_alone, recover


def test_commit_needs_every_yes():
    """one no, or one missing vote, aborts the transaction"""
    assert decide({"A": "yes", "B": "yes"}) == "commit"
    assert decide({"A": "yes", "B": "no"}) == "abort"
    assert decide({"A": "yes", "B": None}) == "abort"
    assert decide({"A": "yes", "B": "yes", "C": "yes"}) == "commit"


def test_only_an_unprepared_participant_may_abort_alone():
    """a yes vote gives the decision away; an outcome already known needs no decision"""
    assert may_abort_alone("working") is True
    assert may_abort_alone("prepared") is False
    assert may_abort_alone("committed") is False
    assert may_abort_alone("aborted") is False


def test_recovery_reads_the_log():
    """the logged decision of that transaction is the answer"""
    log = [("t1", "commit"), ("t2", "abort"), ("t3", "commit")]
    assert recover(log, "t1") == "commit"
    assert recover(log, "t2") == "abort"
    assert recover(log, "t3") == "commit"


def test_presumed_abort():
    """no record means no commit was ever promised"""
    assert recover([("t1", "commit")], "t9") == "abort"
    assert recover([], "t1") == "abort"

Check yourself

Two-phase commit on PostgreSQL 18.6, with the blocking failure reproduced Pro: opens with a Pro, Premium or Ultimate pass

Consensus inside a shard: a Raft log simulated, and the rule that keeps commits Pro: opens with a Pro, Premium or Ultimate pass

A saga with an outbox, run end to end, and how designs are judged Pro: opens with a Pro, Premium or Ultimate pass

Interview questions

Key takeaways

• Two-phase commit is atomic, and the coordinator’s logged decision is its commit point.
• A participant that has voted yes waits for the decision with its locks held: that is where 2PC blocks.
• Paxos and Raft make the replicas of one log agree by majority; shards still vote, so consensus complements 2PC.
• A saga runs local transactions with compensations; an outbox and an inbox carry its messages, each applied once.