Distributed deadlock; two-phase commit

Distributed deadlock

A deadlock is a state in which each transaction in a set is waiting for a lock held by another transaction in the set, so none can proceed. It is shown by a cycle in the wait-for graph (nodes are transactions, an edge T → U means T waits for U).

A distributed deadlock occurs when the wait-for cycle spans several servers. Each server sees only a part of the graph (a local wait-for graph without a local cycle), but the global graph has a cycle.

Example: T holds a lock on A at server X, and U holds a lock on B at server Y. T now requests B at Y (so T waits for U), and U requests A at X (so U waits for T).

Server X: U -> T  (U waits for T on A)
Server Y: T -> U  (T waits for U on B)
Global:   T -> U -> T   (cycle = deadlock)

Such deadlocks are detected by edge chasing or a global wait-for graph, and resolved by aborting a transaction in the cycle.

Two-phase commit protocol

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).