Showing posts with label Distributed Transaction. Show all posts
Showing posts with label Distributed Transaction. Show all posts

Tuesday, July 5, 2016

Two Phase Commit Protocol

Two Phase Commit Protocol, Explain 2PC protocol, How does 2 Phase Commit protocol work?, Two phase protocol in handling distributed transactions, 2PC and distributed concurrency control

Two Phase Commit protocol in Distributed Database

Two Phase Commit (2PC) Protocol
Consider a transaction T initiated at site Sitei. And, at that site the transaction coordinator is TCi. When the transaction started, TCi distributes the sub-transactions to the sites where the data needed for those sub-transactions available. When T completed its execution at all the sites at which T has executed, the transaction managers (TMs) of those sites inform TCi about the completion. Then TCi starts the 2PC protocol. It works as follows;

Set of messages used for communication in 2PC protocol are,

<prepare T>
send by the coordinator to all the participating sites for preparing for commit. It is always sent by the coordinator whenever a transaction is ready.
<ready T>
send by the transaction manager of the participating site as reply for <prepare T> message, if the sending site is ready for commit the ongoing transaction.
<abort T>
send by the transaction manager of the participating site and later by the coordinator to all the participating site, if any one or more of the participating sites are not ready to commit.
<no T>
it is the log written to the log file of the local system by the transaction manager of the participating site, if it is not ready to commit (which also send <abort T> to the coordinator)
<commit T>
send by the coordinator if all the sites are ready for a commit.

Phase 1: Transaction Coordinator TCi inserts a <preapare T> message into the log file, and forces the log into stable storage (for example, hard disk) for the recovery purpose. Then it sends <prepare T> message to all the sites where the transaction T is being executed. On receiving such message, the TM of the participating site must decide to commit or not based on its status. If the TM of the receiving site decided not to commit for some reasons (failure of transaction, message failure, locking etc.), it write <no T> to its log, and sends <abort T> message to the coordinator TCi. If the TM is read to commit, then it sends <ready T> message to the coordinator TCi. In both the cases, (i.e., no T, or ready T), the messages first written into the stable storage of that site where it is decided and send back to the coordinator.

Phase 2: when TCi receives reply messages for <prepare T> message, or after the pre-specified time interval, the TCi can decide the fate of the transaction. Transaction T can be committed if it received <ready T> message from all the participating sites of the transaction T. Then TCi write a message <commit T> into its stable storage and send <commit T> to all the participating sites for them to commit the transaction. If any one of the reply is <abort T> or no reply on the specified time interval, the transaction must be aborted. In this case, a <abort T> message must be written into stable storage and sent to all the participating sites to abort as well.


How does 2PC protocol work?

What is two phase commit protocol in distributed transactions

Explain 2PC protocol

What are the two phases in 2PC protocl

How distributed transactions are managed using two phase commit protocol?

Thursday, June 5, 2014

Deadlock handling in distributed databases

Deadlock Handling in Distributed Database / How do we handle deadlock in distributed database? / Deadlock prevention and detection in distributed database / What is Global Wait-for graph? / Why deadlock handling is difficult in distributed database? / Centralized deadlock detection technique in distributed database

Deadlock Handling in Distributed Database

A Deadlock is a situation in which two or more transactions are waiting for the data items that are held by and to be released by the other transactions. You can find more on the following in the given links;

Deadlock in Distributed Databases

Like in the case of centralized database systems, distributed database systems also prone to Deadlocks. In Distributed Database systems, we need to handle transactions differently. In every site that are part of the distributed database, we have the transaction specific components - transaction coordinators, transaction managers, lock managers, etc. Above all, data might be owned by many sites, or replicated in many sites. Due to these reasons, deadlock handling is bit tough job in Distributed Database.
Deadlock can be handled in two ways;
1. Deadlock prevention – it deals with preventing the deadlock before it occurs. It is harder in centralized database system as it involves more number of rollback and slows down the transactions. In distributed database it would cause more problems because, it rollback more transactions that are happening in more sites (not in a single server but possibly many servers).
2. Deadlock detection – it deals with detecting deadlock if one happened. In centralized database systems, detection is easier compare to prevention. We have handled detection using Wait-for graphs. In the case of distributed database, the main problem is where and how to maintain the Wait-for graphs. 

Deadlock detection technique in distributed database

We have handled deadlock detection in centralized database system using Wait-for graph. The same can be used in distributed database. That is, we can maintain Local wait-for graphs in every site. (How to construct wait-for graph can be referred here). If the local wait-for graph of any site formed a cycle, then we would say that a deadlock has occurred.

On the other hand, no cycles in any of the local wait-for graph does not mean no deadlock has occurred. Let us discuss this point with local wait-for graph examples as shown below;

Figure 1 - Local wait-for graphs of SITE 1 and 2

Figure 1 shows the lock request status for transactions T1, T2, T3 and T4 in a distributed database system. In the local wait-for graph of SITE 1, transaction T2 is waiting for transactions T1 and T3 to finish. In SITE 2, transactions T3 is waiting for T4, and T4 is waiting for T2. From SITE 1 and SITE 2 local wait-for graphs, it is clear that transactions T2 and T3 are involved in both sites.
How it might be happened? For example, transaction T2 which is initiated at SITE 2 may need some data items held by transactions T1 and T3 in SITE 1. Hence, SITE 2 forwards the request to SITE 1. If the transactions are busy, then SITE 1 inserts edges T2 à T1 and T2 à T3 in its local wait-for graph.
As another example, transaction T3 which is initiated at SITE 1 may need data items held by transaction T4 at SITE 2. Hence, SITE 1 forwards the request to SITE 2. Based on the status of T4, SITE 2 inserts an edge T3 à T4 in its local wait-for graph.
You can observe from the local wait-for graphs of SITE 1 and SITE 2, there are no symptoms of cycles. If we merge these two local wait-for graphs into a single wait-for graph, then we would get the graph which is given in Figure 2, below. From Figure 2, it is clear that the union of two local wait-for graphs have formed a cycle, which means deadlock has occurred. This merged wait-for graph is called as Global wait-for graph.

Figure 2 - Global wait-for graph

The approach used to handle deadlock detection in distributed database is,


Go to Distributed Database home

How to handle deadlock in distributed database, examples

Featured Content

Multiple choice questions in Natural Language Processing Home

MCQ in Natural Language Processing, Quiz questions with answers in NLP, Top interview questions in NLP with answers Multiple Choice Que...

All time most popular contents

data recovery