Two-phase commit protocol

Two-phase commit protocol

In computer networking and databases, the two-phase commit protocol (2PC) is a distributed algorithm that 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, the protocol will not handle more than one random site failure at a time [cite journal
last = Skeen
first = D.
title = A Formal Model of Crash Recovery in a Distributed System
journal = IEEE Transactions on Software Engineering
volume = 9
issue = 3
month = May
year = 1983
pages = 219–228
doi = 10.1109/TSE.1983.236608
] . 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.

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, that the data in the write-ahead log is never lost or corrupted in a crash, and that any two nodes can communicate with each other. The last assumption is not too restrictive, as network communication can typically be rerouted. The first two assumptions are much stronger; 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 whether the transaction has been processed successfully at the cohort.

Basic algorithm

Commit-request phase

# The coordinator sends a query to commit message to all cohorts and waits until it has received a reply from 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 (cohort votes Yes to commit), if the transaction succeeded, or an abort message (cohort votes No, not to commit), if the transaction failed.

Commit phase

uccess

If the coordinator received an agreement message from "all" cohorts during the commit-request phase:
# 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 acknowledgment to the coordinator.
# The coordinator completes the transaction when acknowledgments have been received.

Failure

If "any" cohort sent an abort message during the commit-request phase:
# The coordinator sends a 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 the following way: if 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, unless it can obtain the global commit/abort decision from some other cohort.When the coordinator has sent "Query-to-commit" to the cohorts, it will block until all cohorts have sent their local decision. Yet, if a cohort is permanently down, the coordinator will not block indefinitely: Since the coordinator is the one to decide whether the decision is 'commit' or 'abort' permanent blocking can be avoided by introducing a timeout: If the coordinator has not received all awaited messages when the timeout is over it will decide for 'abort'. This conservative behaviour of the protocol is another disadvantage: It is biased to the abort case rather than the complete case.

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.

Distributed two-phase commit protocol

Common architecture

In many cases the 2PC protocol is utilized in distributed environments. The protocol is easily distributed in a network by implementing multiple dedicated 2PC components similar to each other, typically named "Transaction Managers" (TMs; also referred to as "2PC agents"), that carry out the protocol's execution for each transaction. The databases involved with a distributed transaction, the "participants", both the coordinator and cohorts, "register" to close TMs (typically residing on respective same network nodes as the participants) for terminating that transaction using 2PC. Each distributed transaction has an ad hoc set of TMs, the TMs to which the transaction participants register. A leader, the coordinator TM exists for each transaction to coordinate 2PC for it, typically the TM of the coordinator database. However, the coordinator role can be transferred to another TM for performance or reliability reasons. Rather than exchanging 2PC messages among themselves, the participants exchange the messages with their respective TMs. The relevant TMs communicate among themselves to execute the 2PC protocol schema above, "representing" the respective participants, for terminating that transaction. With this architecture the protocol is fully distributed (does not need any central processing component or data structure), and scales up with number of network nodes (network size) effectively.

Tree two-phase commit protocol

A common variant of 2PC in a distributed system, which better utilizes the underlying communication infrastructure, is the Tree 2PC protocol. In this variant the coordinator is the root ("top") of a communication tree (inverted 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 below it, before it sends the appropriate message "up" the tree (except an abort message, which is propagated "up" immediately upon receiving it, or if this cohort decided to abort).

The Dynamic two-phase commit (Dynamic two-phase commitment, D2PC) protocol is a variant of Tree 2PC with no predetermined coordinator. Agreement messages start to propagate from all the leaves, each leaf when completed its tasks on behalf of the transaction (becoming "ready"), and the coordinator is determined dynamically by racing agreement messages, at the place where they collide. They collide either on a transaction tree node, or on an edge. In the latter case one of the two edge's nodes is elected as a coordinator (any node). D2PC is time optimal (among all the instances of a specific transaction tree, and any specific 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.

References

ee also

*Atomic commit
*Commit (data management)
*Three-phase commit protocol
*XA

External links

* http://ei.cs.vt.edu/~cs5204/sp99/distributedDBMS/duckett/tpcp.html


Wikimedia Foundation. 2010.

Игры ⚽ Поможем решить контрольную работу

Look at other dictionaries:

  • Three-phase commit protocol — In computer networking and databases, the three phase commit protocol (3PC) is a distributed algorithm which lets all nodes in a distributed system agree to commit a transaction. Unlike the two phase commit protocol (2PC) however, 3PC is non… …   Wikipedia

  • Two-phase locking — This article is about concurrency control. For commit consensus within a distributed transaction, see Two phase commit protocol. In databases and transaction processing two phase locking, (2PL) is a concurrency control method that guarantees… …   Wikipedia

  • Commit (data management) — In the context of computer science and data management, commit refers to the idea of making a set of tentative changes permanent. A popular usage is at the end of a transaction. A commit is an act of committing. Contents 1 Data management 2… …   Wikipedia

  • Atomic commit — An atomic commit is an operation where a set of distinct changes is applied as a single operation. If the atomic commit succeeds, it means that all the changes have been applied. If there is a failure before the atomic commit can be completed,… …   Wikipedia

  • Commitment ordering — In concurrency control of databases, transaction processing (transaction management), and related applications, Commitment ordering (or Commit ordering; CO; (Raz 1990, 1992, 1994, 2009)) is a class of interoperable Serializability techniques …   Wikipedia

  • Serializability — In concurrency control of databases,[1][2] transaction processing (transaction management), and various transactional applications (e.g., transactional memory[3] and software transactional memory), both centralized and distributed, a transaction… …   Wikipedia

  • Global serializability — In concurrency control of databases, transaction processing (transaction management), and other transactional distributed applications, Global serializability (or Modular serializability) is a property of a global schedule of transactions. A… …   Wikipedia

  • Actor model and process calculi — In computer science, the Actor model and process calculi are two closely related approaches to the modelling of concurrent digital computation. See Actor model and process calculi history.There are many similarities between the two approaches,… …   Wikipedia

  • Concurrency control — In information technology and computer science, especially in the fields of computer programming (see also concurrent programming, parallel programming), operating systems (see also parallel computing), multiprocessors, and databases, concurrency …   Wikipedia

  • Kyoto Protocol — Participation in the Kyoto Protocol, as of December 2010, Green = Countries that have signed and ratified the treaty              (Annex I II countries in dark green) Grey =… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”