ICS 214B: Transaction Processing and Distributed Data Management
Lecture 12: Three-Phase Commits (3PC)
Professor Chen Li
2PC is blocking
Sample scenario:
Coord P2
W
P1 P3
W
P4 W
Case I:
Case I:
P1 “W”; coordinator sent commits
P1 “C”
Case II:
P1 NO; P1 A
P2, P3, P4 (surviving participants)
cannot safely abort or commit transaction
Complexity analysis
Count number of messages, rounds
N participants
Centralized 2PC
Ignore DONE messages
If there are no failures:
3 rounds
3N messages
Variants of 2PC
Linear
Coord
Hierarchical
Variants of 2PC
Distributed
Nodes broadcast all messages
Every node knows when to commit
Exercise
Compare 2PC variants in terms of
Number of rounds
Number of messages
Cooperative Termination Protocol
Bad case
Participant P recovers from failure
Has prepared record for transaction T
No commit or abort record for T
Coordinator is down
Participant P is blocked until coordinator recovers
Cooperative termination protocol
But perhaps some other participant can help?
Requires participants “know” each other!
Cooperative Termination Protocol
Participant P sends a DECISION-REQUEST message to other participants
Alive participants respond with COMMIT, ABORT, or UNCERTAIN
If any participant replies with a decision (COMMIT or ABORT), P acts on decision
And sends decision to UNCERTAIN participants
Cooperative Termination Protocol
When P receives a DECISION-REQUEST
If it knows decision, responds with COMMIT or ABORT
If it has not prepared transaction, responds ABORT
If it is prepared but does not know decision, responds UNCERTAIN
Cooperative Termination
Sample scenario:
Coord P1
C
P2
W
P3 W
Cooperative Termination
Sample scenario:
Coord P1
W
P2
W
P3 A
Cooperative Termination
Sample scenario:
Coord P1
W
P2
W
P3 W
Is there a non-blocking protocol?
Theorem:
If communications failure or total site failures (i.e., all sites are down simultaneously) are possible, then every atomic protocol may cause processes to become blocked.
Next…
Three-phase commit (3PC)
Nonblocking if reliable network (no communications failure) and no total site failures
Handling communications failures
Three-Phase Commit
Sample scenario:
Coord P1
W
P2
W
P3 W
3PC Principle
If ANY operational site is in the “uncertain” state, NO site (operational or failed) could have decided to commit
Reminder: Assume reliable network
Process categories
Three categories
Operational
Process has been up since start of 3PC
Failed
Process has halted since start of 3PC, or is recovering
Recovered
Process that failed and has completed recovery
Termination Protocol
Termination Protocol
Elect new coordinator
Use Election Protocol (coming soon…)
New coordinator sends STATE-REQUEST to participants