Two-phase-commit protocol
From Free net encyclopedia
Template:TOCright In computer networking and databases, the two-phase-commit protocol is a distributed algorithm which lets all nodes in a distributed system agree to commit a transaction. The protocol results in either all nodes committing the transaction or aborting, even in the case of network failures or node failures. However, according to the work by Skeen and Stonebraker, the protocol will not handle more than one random site failure at a time. The two phases of the algorithm are the commit-request phase, in which the coordinator attempts to prepare all the cohorts, and the commit phase, in which the coordinator completes the transactions at all cohorts.
Contents |
Assumptions
The protocol works in the following manner: one node is designated the coordinator, which is the master site, and the rest of the nodes in the network are designated the cohorts. The protocol assumes that there is stable storage at each node with a write-ahead log, that no node crashes forever, and that any two nodes can communicate with each other. The latter is not a big deal since network communication can typically be rerouted. The former is a much stronger assumption; if a node is totally destroyed then data can be lost.
The protocol is initiated by the Coordinator after the last step of the transaction has been reached. The Cohorts then respond with an agreement message or an abort message depending on success.
Basic algorithm
Commit-request phase
- The coordinator sends a query to commit message to all cohorts.
- The cohorts execute the transaction up to the point where they will be asked to commit. They each write an entry to their undo log and an entry to their redo log.
- Each cohort replies with an agreement message if the transaction succeeded, or an abort message if the transaction failed.
- The coordinator waits until it has a message from each cohort.
Commit phase
Success
If the coordinator received an agreement message from all cohorts during the commit-request phase:
- The coordinator writes a commit record into its log.
- The coordinator sends a commit message to all the cohorts.
- Each cohort completes the operation, and releases all the locks and resources held during the transaction.
- Each cohort sends an acknowledgement to the coordinator.
- The coordinator completes the transaction when acknowledgements have been received.
Failure
If any cohort sent an abort message during the commit-request phase:
- The coordinator sends an rollback message to all the cohorts.
- Each cohort undoes the transaction using the undo log, and releases the resources and locks held during the transaction.
- Each cohort sends an acknowledgement to the coordinator.
- The coordinator completes the transaction when acknowledgements have been received.
Disadvantages
The greatest disadvantage of the two phase commit protocol is the fact that it is a blocking protocol. A node will block while it is waiting for a message. This means that other processes competing for resource locks held by the blocked processes will have to wait for the locks to be released. A single node will continue to wait even if all other sites have failed. If the coordinator fails permanently, some cohorts will never resolve their transactions. This has the effect that resources are tied up forever. The algorithm can block indefinitely in two ways:
- When the coordinator has sent commit to the cohorts, it will block until all cohorts have acknowledged. Thus, if a cohort is permanently down, the coordinator will block indefinitely.
- When a cohort has sent an agreement message to the coordinator, it will block until a commit or rollback is received. If the coordinator is permanently down, the cohort will block indefinitely.
Another disadvantage is the protocol is conservative. It is biased to the abort case rather than the complete case. Also it cannot recover from cases where a node has failed in the commit stage (due to internal or network failures) after indicating that it is ready to commit. In this case, resources that committed prior to this failure cannot be rolled back.
A lot of database research has been done on ways to get most of the benefits of the two-phase-commit protocol without the costs.
Tree two-phase-commit protocol
A common variant of 2PC in a distributed system is the Tree 2PC protocol. In this variant the coordinator is the root ("top") of a communication tree, while the cohorts are the other nodes. Messages from the coordinator are propagated "down" the tree, while messages to the coordinator are "collected" by a cohort from all the cohorts "down" to it, before it sends the appropriate message "up" the tree (except "abort" message that is propagated "up" immediatly upon receiving it, or if this cohort decided to abort).
A special case of Tree 2PC is the Dynamic two-phase-commit (Dynamic two-phased-commitment, D2PC) protocol, where agreement messages start to propagate from all the leaves, and the coordinator is determined dynamically by racing agreement messages, at the place where they colide. They colide either on a tree node, or on an edge. In the latter case one of the edge's two nodes is elected as a coordinator. D2PC is time optimal (among all the instances of a certain Tree 2PC protocol implementation; all instances have the same tree; each instance has a different node as coordinator): It commits the coordinator and each cohort in minimum possible time, allowing earlier release of locked resources.