Two & Three Phase Commit Protocols - A Summary
Motivation
These protocols extend our discussion on fault tolerance, rollback and recovery
(They add a new slant to rollback and recovery.)
There are two approaches for making a system fault tolerant:-
- Make the system transparent to the application ie.system fixes failures.
- Upon failure, the system goes into a predictable ``known'' state, so the
application/user can fix it. The system guarantees that either
the transaction works or if it fails the system ends up in a
``known'' state. The application knows the state of the system and can
attempt to remedy it.
Commit protocol
These protocols adopt the second approach to makig a system fault tolerant.
Deal with agreement on what state to leave the system in.
If the transaction is successful, all participants must agree it was
successful. If it failed then they must agree on the state to leave the
system in. (Like an agreement protocol)
Commit --- accept
not commit --- abort
Assumptions
- No lost messages. (General's Paradox)
- Only hardware/process failure
- Stable storage (storage doesn't die upon system crash)
- Some replication (partial or total) of data
- Logs of individual transactions, so ``undo'' is possible.
- Only one site/node fails.
NOTE: There exists no protocol that works for more than one site failing.
Terminology
- Blocking vs non-blocking commit protocol:
A commit protocol is blocking if
all nodes must wait till a failed node recovers. A non-blocking protocol
overcomes this waiting, and the remaining nodes agree without the failed node.
-
Independent recovery:
A failed node, upon recovery, ``knows'' what the
other nodes decided on and does the same thing, without communicating with
the others.
-
Transactions:
sequence of operations (typically two -
eg. read/write in database).
-
Atomic transaction:
system knows some properties about success or failure
of transaction, which allows it to go into a predetermined state.
Properties of transactions - ACID
- Atomiticity: from the outside, the system it appears as if the transaction
either happens or doesn't.
- Consistency: concurrent execution should produce same results as sequential
- Isolation: not possible for one transaction to see partial results of
another transaction.
- Durability: once a decision is taken its effect remains till application
decides to change it or another transaction.
-
Co-ordinator:
The initiator. Doesn't know about individual transactions or
the reason for a site not agreeing.
-
Cohorts:
the other participating nodes in the agreement.
Our main focus as far as commit protocols go is on atomicity.
Two-Phase Commit Protocol
A good starting point, though it really doesn't provide much because
- it is a blocking protocol
- it does not provide independent recovery
FSM (2 phase commit) description of co-ordinator and cohorts
From Mike Duckett's web page
The Protocol
Phase I
Co-ordinator: send out commit request message to all cohorts.
Cohorts: Commit request message received from co-ordinator.
Agreement/Abort (don't care about reason for aborting)
message send to co-ordinator.
Phase II
Co-ordinator: if ALL cohorts replied with an agree message and if
co-ordinator also agrees, then send out commit mesage.
If any one cohort replied with an abort message then send
abort message to all cohorts.
Cohorts: Commit or abort depending on message received from co-ordinator.
Drawbacks:
- Blocking: co-ordinator must wait for all cohorts to reply. Thus,
if a cohort goes down, everyone must wait for it to recover, because
all the other cohorts must wait for the co-ordinator to send a final
commit/abort message (Phase II). If the co-ordinator goes down, of course,
all the cohorts are waiting for it to send out the final commit/abort message
and thus the entire system grinds to a halt.
- No independent recovery: (assuming the protocol is non-blocking)
when site fails and subsequently recovers, it has no way of knowing
what the others agreed on without communicating.
How to fix these problems? - Three-Phase commit protocol
More Terminology
- Synchronous protocol:
close lockstep between co-ordinator and cohorts -
they cannot get too far apart because the progress of each one is
closely tied to the others' progress.
-
Concurrency set:
The possible states that the other nodes can be in
given that a node is in a particular state. Since the protocol is synchronous,
the other nodes/sites can only be one state ahead or behind.
-
Sender set:
The set of nodes that sent a message to drive a node into another state.
What causes blocking?
Concurrency set contains both final states. Therefore, other sites/nodes
may have finished with their protocol and reached the final state.
Some ``leeway'' is required to make a decision.
Thus, an extra state is needed as the pre-final state - a ``prepare'' state.
No concurrency set has both accept and abort.
Three-phase Commit Protocol
FSM
From
Srinivas R. Gaddam's page
Phase I
Co-ordinator: sends commit request message to all cohorts, moves to next state
Cohorts: receive commit request from co-ordinator. Replies with abort or accept
and moves to next state.
Phase II
Co-ordinator: gathers all cohorts replies. If any abort message is received,
it sends out the final abort message. Thus abort is just like the 2-phase
commit protocol. Otherwise sends a prepare to commit message.
Cohorts: Receive either the abort message and abort transaction,
or receive the prepare to commit message and acknowledge it.
Phase III
Co-ordinator: gets all the acknowledgements and sends the final commit message.
Cohorts: receive final commit message and commit transaction.
No Blocking
Timeout periods are set so that if a message is not received within that time,
it is assumed that the site failed and the rest of the sites are driven to
their next states by "timeout transitions". Therefore no blocking occurs.
Independent recovery
Assumption: Site/node comes up in the same state it failed in (from stable
storage it knows which state it failed in).
Failure Transition (marked F in figure) Rule
The concurrency set of the state in which the site failed is examined.
If the concurrency set contains a "commit" then on recovery the
failed node commits, otherwise it goes into the concurrency set state.
Timeout Transition (marked T in figure) Rule
Assign a timeout transition for each state where there is a possibility of
blocking to enable reaching agreement without blocking.
- Co-ordinator fails: cohorts time out and drive themselves without
blocking into a new state
- Cohort fails: co-ordinator times out and drives remaining cohorts to
agreement without blocking.
NOTE: a proof of correctness by contradiction for these protocols
can be found in "Advanced Concepts in Operating Systems"
by Mukesh Singhal and Niranjan G. Shivaratri.
Last updated: March 31st 1997