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 Database
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.
The approach used to handle deadlock detection in distributed database is,
**********
Go to Distributed Database home
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,
Centralized deadlock detection approach. Click here
**********
Go to Distributed Database home