Atomic commitment protocols (2PC, 3PC)

Need and roles of atomic commitment protocol

An atomic commit protocol (ACP) is used to make sure that a distributed transaction, which has operations at several servers, is committed or aborted at all of them together.

Need: in a one-server transaction, commit is a local action. In a distributed transaction, if one server commits while another aborts (due to crash, lock conflict or validation failure), atomicity is violated and the data become inconsistent. A one-phase commit (the coordinator just tells everybody to commit) cannot handle a server that has to abort unilaterally.

Roles

• Ensure atomicity: all participants reach the same decision (commit if all vote Yes, otherwise abort).
• A coordinator collects votes and announces the decision; participants vote and carry it out.
• Ensure durability: participants save tentative changes to permanent storage before voting Yes, so the decision can be completed after a crash.
• Allow any participant to veto (abort) the transaction.
• Provide recovery from crashes and lost messages using logs and timeouts.

The best-known ACPs are two-phase commit (2PC) and three-phase commit (3PC).

Two-phase commit (2PC)

The two-phase commit protocol (2PC) makes sure that all servers (participants) of a distributed transaction either all commit or all abort. One server acts as the coordinator (usually the one that the client contacted); others are participants.

Phase 1: voting

1. The coordinator sends canCommit? to every participant.
2. Each participant replies Yes (it has saved the transaction's changes to permanent storage and is prepared; it can no longer unilaterally abort) or No (it aborts at once).

Phase 2: completion 3. If all votes (including the coordinator's own) are Yes, the coordinator records the decision and sends doCommit; if any vote is No or a timeout occurs, it sends doAbort. 4. Participants carry out the decision and send haveCommitted to the coordinator.

Coordinator            Participants
   |--- canCommit? ------->|
   |<------ Yes / No ------|
   | (decide, log)         |
   |--- doCommit/doAbort ->|
   |<---- haveCommitted ---|

Failures

• If a participant crashes before voting, the coordinator times out and aborts.
• A participant that has voted Yes is in the uncertain state; if the coordinator fails it must wait (it blocks) or ask other participants for the decision.
• On recovery, servers use their logs to complete the protocol.

Drawbacks: blocking if the coordinator fails, and extra messages and delays (about 3N messages for N participants).

Three-phase commit (3PC)

The three-phase commit protocol (3PC) is an extension of 2PC that avoids blocking when the coordinator crashes, by adding a pre-commit state between the vote and the commit. Its states satisfy two conditions: there is no state from which a process can move directly to both COMMIT and ABORT, and there is no state in which a process cannot yet make a final decision but can move directly to COMMIT.

Phases

1. canCommit: the coordinator sends Prepare/canCommit?; participants reply Yes or No. If any No, or a timeout, the coordinator sends abort.
2. preCommit: if all say Yes, the coordinator sends Pre-commit; participants acknowledge. Now everyone knows that all have voted Yes.
3. doCommit: after all acknowledgements, the coordinator sends Commit; participants commit and reply.

Coordinator states:
 INIT --canCommit?--> WAIT --all Yes--> PRECOMMIT --acks--> COMMIT
                        |any No/timeout
                        v
                      ABORT

Participant states:
 INIT --Yes--> READY --preCommit--> PRECOMMIT --commit--> COMMIT
   |No          |abort/timeout
   v            v
 ABORT        ABORT

Recovery rule: if the coordinator fails, the participants elect a new one. If any participant is in PRECOMMIT, all can commit; if none is, all can abort. Timeouts drive transitions so the system never blocks indefinitely.

Compared with 2PC: 3PC is non-blocking under crash failures (not for network partitions), but needs one more round of messages, so it costs more and is less used in practice.