Overview of Concurrency Control and
Recovery in Distributed Databases
For concurrency control and
recovery purposes, numerous problems arise in a distributed DBMS environment
that are not encountered in a centralized DBMS environment. These include the
following:
Dealing with multiple copies of the data items. The concurrency control method is responsible for maintaining consistency among these
copies. The recovery method is responsible for making a copy consistent with
other copies if the site on which the copy is stored fails and recovers later.
Failure
of individual sites. The DDBMS should continue to operate with its running sites, if possible, when one
or more individual sites fail. When a site recovers, its local database must be
brought up-to-date with the rest of the sites before it rejoins the system.
Failure of communication links. The system must be able to deal with the failure of one or more of the
communication links that connect the sites. An extreme case of this problem is
that network partitioning may occur.
This breaks up the sites into two or more partitions, where the sites within
each partition can communicate only with one another and not with sites in
other partitions.
Distributed commit. Problems can arise with committing a
transaction that is accessing
databases stored on multiple sites if some sites fail during the commit
process. The two-phase commit protocol
(see Section 23.6) is often used to deal with this problem.
Distributed deadlock. Deadlock may occur among several sites, so
techniques for dealing with deadlocks must be extended to take this into
account.
Distributed concurrency control and recovery
techniques must deal with these and other problems. In the following
subsections, we review some of the techniques that have been suggested to deal
with recovery and concurrency control in DDBMSs.
1. Distributed Concurrency Control Based on a
Distinguished Copy of a Data Item
To deal with replicated data items in a
distributed database, a number of concurrency control methods have been
proposed that extend the concurrency control techniques for centralized
databases. We discuss these techniques in the context of extending centralized locking. Similar extensions apply to
other concurrency control techniques. The idea is to designate a particular copy of each data item as a
distinguished copy. The locks for
this data item are associated with the distinguished copy, and all
locking and unlocking requests are sent to the site that contains that copy.
A number of different methods are based on this
idea, but they differ in their method of choosing the distinguished copies. In
the primary site technique, all
distinguished copies are kept at the same site. A modification of this
approach is the primary site with a backup
site. Another approach is the primary
copy method, where the distinguished copies of the various data items can
be stored in different sites. A site that includes a distinguished copy of a
data item basically acts as the coordinator
site for concurrency control on that item. We discuss these techniques next.
Primary Site Technique. In this method a single primary site is designated to be the coordinator site for all database items. Hence, all locks
are kept at that site, and all requests for locking or unlocking are sent
there. This method is thus an extension of the centralized locking approach.
For example, if all transactions follow the two-phase locking protocol,
serializability is guaranteed. The advantage of this approach is that it is a
simple extension of the centralized approach and thus is not overly complex.
However, it has certain inherent disadvantages. One is that all locking
requests are sent to a single site, possibly overloading that site and causing
a system bottleneck. A second disadvantage is that failure of the primary site
paralyzes the system, since all locking information is kept at that site. This
can limit system reliability and availability.
Although all locks are accessed at the primary
site, the items themselves can be accessed at any site at which they reside.
For example, once a transaction obtains a Read_lock
on a data item from the primary site, it can
access any copy of that data item. However, once a transaction obtains a Write_lock and updates a data item, the DDBMS is responsible for updating all copies of the data item before
releasing the lock.
Primary Site with Backup Site. This approach addresses the second disadvantage of the primary site method by designating a second site to be a backup site. All locking information
is maintained at both the primary and the backup sites. In case of primary site
failure, the backup site takes over as the primary site, and a new backup site
is chosen. This simplifies the process of recovery from failure of the primary
site, since the backup site takes over and processing can resume after a new
backup site is chosen and the lock status information is copied to that site.
It slows down the process of acquiring locks, however, because all lock
requests and granting of locks must be recorded at both the primary and the backup sites before a response is sent to
the requesting transaction. The problem of the primary and backup sites
becoming overloaded with requests and slowing down the system remains
undiminished.
Primary Copy Technique. This method attempts to distribute the load of
lock coordination among various sites by having the distinguished copies
of different data items stored at
different sites. Failure of one site affects any transactions that are
accessing locks on items whose primary copies reside at that site, but other
transactions are not affected. This method can also use backup sites to
enhance reliability and availability.
Choosing a New Coordinator Site in Case of
Failure. Whenever a coordinator site
fails in any of the preceding techniques, the sites that are still running must
choose a new coordinator. In the case of the primary site approach with no backup site, all executing
transactions must be aborted and restarted in a tedious recovery process. Part
of the recovery process involves choosing a new primary site and creat-ing a
lock manager process and a record of all lock information at that site. For
methods that use backup sites, transaction processing is suspended while the
backup site is designated as the new primary site and a new backup site is
chosen and is sent copies of all the locking information from the new primary
site.
If a backup site X is about to become the new primary site, X can choose the new backup site from among the system’s running
sites. However, if no backup site existed, or if both the primary and the
backup sites are down, a process called election
can be used to choose the new coordinator site. In this process, any site Y that attempts to communicate with the
coordinator site repeatedly and fails to do so can assume that the coordinator
is down and can start the election process by sending a message to all running
sites proposing that Y become the new
coordinator. As soon as Y receives a
majority of yes votes, Y can declare
that it is the new coordinator. The election algorithm itself is quite
complex, but this is the main idea behind the election method. The algorithm
also resolves any attempt by two or more sites to become coordinator at the
same time. The references in the Selected Bibliography at the end of this
chapter discuss the process in detail.
2. Distributed Concurrency Control Based on
Voting
The concurrency control methods for replicated
items discussed earlier all use the idea of a distinguished copy that maintains
the locks for that item. In the voting
method, there is no distinguished
copy; rather, a lock request is sent to all sites that includes a copy of the data item. Each copy maintains its own lock
and can grant or deny the request for it. If a transaction that requests a lock
is granted that lock by a majority of the copies, it holds the
lock and informs all copies that it
has been granted the lock. If a
transaction does not receive a majority of votes granting it a lock within a
certain time-out period, it cancels
its request and informs all sites of the cancellation.
The voting method is considered a truly
distributed concurrency control method, since the responsibility for a decision
resides with all the sites involved. Simulation studies have shown that voting
has higher message traffic among sites than do the distinguished copy methods.
If the algorithm takes into account possible site failures during the voting
process, it becomes extremely complex.
3. Distributed Recovery
The recovery process in distributed databases
is quite involved. We give only a very brief idea of some of the issues here.
In some cases it is quite difficult even to deter-mine whether a site is down
without exchanging numerous messages with other sites. For example, suppose that
site X sends a message to site Y and expects a response from Y but does not receive it. There are
several possible explanations:
a. The message was not delivered to Y because of communication failure.
b. Site Y is down and could not respond.
c. Site Y is running and sent a response, but the response was not delivered.
Without additional information or the sending
of additional messages, it is difficult to determine what actually happened.
Another problem with distributed recovery is
distributed commit. When a transaction is updating data at several sites, it
cannot commit until it is sure that the effect of the transaction on every site cannot be lost. This means
that every site must first have recorded the local effects of the transactions
permanently in the local site log on disk. The two-phase commit protocol is
often used to ensure the correctness of distributed commit (see Section 23.6).
Related Topics
Privacy Policy, Terms and Conditions, DMCA Policy and Compliant
Copyright © 2018-2023 BrainKart.com; All Rights Reserved. Developed by Therithal info, Chennai.