Three-phase commit protocol: Difference between revisions

Revision as of 10:54, 11 February 2016

Latest revision as of 20:34, 14 December 2024

(27 intermediate revisions by 21 users not shown)

Line 1:

{{Short description|Distributed algorithm}}

In [[computer networking]] and distributed [[database]]s, the '''three-phase commit protocol''' ('''3PC''')<ref name=3PC>{{cite journaltech report

| last = Skeen

| first = Dale

| title = A FormalQuorum-Based ModelCommit of Crash Recovery in a Distributed SystemProtocol

| date = February 1982

| journal = IEEE Transactions on Software Engineering

| institution = Department of Computer Science, Cornell University

| volume = 9

| url = https://ecommons.cornell.edu/handle/1813/6323

| issue = 3

}}</ref> is a [[distributed algorithm]] that ensures all nodes in a [[distributed system|system]] agree to [[Commit (data management)|commit]] or abort a [[database transaction|transaction]]. It improves upon the [[two-phase commit protocol]] (2PC) by eliminating the possibility of indefinite blocking caused by a specific type of failure during the commit phase.

|date=May 1983

| pages = 219–228

| doi = 10.1109/TSE.1983.236608

| last2 = Stonebraker

| first2 = M.

}}</ref> is a [[distributed algorithm]] which lets all nodes in a [[distributed system]] agree to [[Commit (data management)|commit]] a [[database transaction|transaction]]. Unlike the [[two-phase commit protocol]] (2PC) however, 3PC is non-blocking. Specifically, 3PC places an upper bound on the amount of time required before a transaction either commits or [[Abort (computing)|aborts]]. This property ensures that if a given transaction is attempting to commit via 3PC and holds some [[lock (computer science)|resource locks]], it will release the locks after the timeout.

==Motivation==

==Protocol Description==

A [[two-phase commit protocol]] cannot dependably recover from a failure of both the coordinator and a cohort member during the '''Commit phase'''. If only the coordinator had failed, and no cohort members had received a commit message, it could safely be inferred that no commit had happened. If, however, both the coordinator and a cohort member failed, it is possible that the failed cohort member was the first to be notified, and had actually done the commit. Even if a new coordinator is selected, it cannot confidently proceed with the operation until it has received an agreement from all cohort members, and hence must block until all cohort members respond.

In describing the protocol, we use terminology similar to that used in the [[two-phase commit protocol]]. Thus we have a single coordinator site leading the transaction and a set of one or more cohorts being directed by the coordinator.

The three-phase commit protocol eliminates this problem by introducing the Prepared to commit state. If the coordinator fails before sending preCommit messages, the cohort will unanimously agree that the operation was aborted. The coordinator will not send out a doCommit message until all cohort members have '''ACK'''ed that they are '''Prepared to commit'''. This eliminates the possibility that any cohort member actually completed the transaction before all cohort members were aware of the decision to do so (an ambiguity that necessitated indefinite blocking in the [[two-phase commit protocol]]).

<center>[[Image:Three-phase commit diagram.png]]</center>

===Coordinator=Solution==

#The coordinator receives a transaction request. If there is a failure at this point, the coordinator aborts the transaction (i.e. upon recovery, it will consider the transaction aborted). Otherwise, the coordinator sends a '''canCommit?''' message to the cohorts and moves to the waiting state.

#If there is a failure, timeout, or if the coordinator receives a '''No''' message in the waiting state, the coordinator aborts the transaction and sends an '''abort''' message to all cohorts. Otherwise the coordinator will receive '''Yes''' messages from all cohorts within the time window, so it sends '''preCommit''' messages to all cohorts and moves to the prepared state.

#If the coordinator succeeds in the prepared state, it will move to the commit state. However if the coordinator times out while waiting for an acknowledgement from a cohort, it will abort the transaction. In the case where all acknowledgements are received, the coordinator moves to the commit state as well.

The pre-commit phase introduced above helps the system to recover when a participant or both the coordinator and a participant failed during the commit phase. When the recovery coordinator takes over after the coordinator failed during a commit phase of [[two-phase commit]], the new pre-commit comes handy as follows: On querying participants, if it learns that some nodes are in commit phase then it assumes that the previous coordinator before crashing has made the decision to commit. Hence it can shepherd the protocol to commit. Similarly, if a participant says that it had not received a PrepareToCommit message, then the new coordinator can assume that the previous coordinator failed even before it completed the PrepareToCommit phase. Hence it can safely assume that no participant has committed the changes, and hence safely abort the transaction.

===Cohort===

#The cohort receives a '''canCommit?''' message from the coordinator. If the cohort agrees it sends a '''Yes''' message to the coordinator and moves to the prepared state. Otherwise it sends a '''No''' message and aborts. If there is a failure, it moves to the abort state.

#In the prepared state, if the cohort receives an '''abort''' message from the coordinator, fails, or times out waiting for a commit, it aborts. If the cohort receives a '''preCommit''' message, it sends an '''[[acknowledgement (data networks)|ACK]]''' message back and awaits a final '''commit''' or '''abort'''.

#If, after a cohort member receives a '''preCommit''' message, the coordinator fails or times out, the cohort member goes forward with the commit.

==MotivationExtensions==

Using Skeen's original three-phase commit protocol, it is possible that a quorum becomes connected without being able to make progress (this is not a deadlock situation; the system will still progress if the network partitioning is resolved). Keidar and Dolev's E3PC<ref name=E3PC>{{cite journal|last=Keidar|first=Idit|author1-link=Idit Keidar|author2=Danny Dolev |title=Increasing the Resilience of Distributed and Replicated Database Systems|journal= Journal of Computer and System Sciences (JCSS)|volume=57|issue=3|date=December 1998|pages=309–324|

A [[Two-phase commit protocol]] cannot dependably recover from a failure of both the '''coordinator''' and a cohort member during the '''Commit phase'''. If only the '''coordinator''' had failed, and no cohort members had received a '''commit''' message, it could safely be inferred that

url=https://iditkeidar.com/wp-content/uploads/files/Abstracts/jcss.html|doi=10.1006/jcss.1998.1566|doi-access=free}}</ref> refines Skeen's three-phase commit protocol and solves this problem in a way which ''always'' allows a quorum to make progress.

no '''commit''' had happened. If, however, both the '''coordinator''' and a cohort member

failed, it is possible that the failed cohort member was the first to be notified, and had

actually done the '''commit'''. Even if a new '''coordinator''' is selected, it cannot

confidently proceed with the operation until it has received an agreement from

'''all''' cohort members ... and hence must block until all cohort members respond.

The Three-phase commit protocol eliminates this problem by introducing the '''Prepared to commit'''

state. If the '''coordinator''' fails before sending '''preCommit''' messages, the '''cohort''' will

unanimously agree that the operation was '''aborted'''. The '''coordinator''' will not send out a '''doCommit'''

message until '''all''' cohort members have '''ACK'''ed that they are '''Prepared to commit'''.

This eliminates the possibility that '''any''' cohort member actually completed the

transaction before '''all''' cohort members were aware of the decision to do so

(an ambiguity that necessitated indefinite blocking in the [[Two-phase commit protocol]]).

==Disadvantages==

Three-phase commit assumes a network with bounded delay and nodes with bounded response times; In most practical systems with unbounded network delay and process pauses, it cannot guarantee atomicity. The other drawback of the protocol is it requires at least 3three round trips to complete, needing a minimum of 3three round trip times (RTTs). This is potentially a long latency to complete each transaction.

The main disadvantage to this algorithm is that it cannot recover in the event the network is segmented in any manner. The original 3PC algorithm assumes a fail-stop model, where processes fail by crashing and crashes can be

accurately detected, and does not work with network partitions or asynchronous communication.

Keidar and Dolev's E3PC<ref name=E3PC>{{cite journal|last=Keidar|first=Idit|author2=Danny Dolev |title=Increasing the Resilience of Distributed and Replicated Database Systems|journal=Journal of Computer and System Sciences (JCSS)|volume=57|issue=3|date=December 1998|pages=309–324|

url=http://webee.technion.ac.il/~idish/Abstracts/jcss.html|doi=10.1006/jcss.1998.1566}}</ref> algorithm eliminates this disadvantage.

The protocol requires at least 3 round trips to complete, needing a minimum of 3 round trip times (RTTs). This is potentially a long latency to complete each transaction.

==References==

Line 58 ⟶ 30:

==See also==

*[[Two-phase commit protocol]]

*[[Paxos algorithm]]

[[Category:Data management]]

[[Category:Transaction processing]]