Biased Protocol Concurrency Control / Variants of Distributed Lock Manager based Concurrency Control mechanism
Do you know?
Bernard
M. Gordon Prize is a prize treated as American equivalent of the Nobel Prize to recognize the exceptional
performers in Academia. It is started in the year 2001 by the United States
National Academy of Engineering.
|
Biased Protocol
Biased
protocol is one of the many protocols to handle concurrency control in
distributed database system, in case of replicated database. Few of the others are
Primary copy, Majority Based protocol, and Quorum Consensus protocol.
Protocol:
If a data
item Q is replicated over n sites, then a read lock (Shared lock) request
message must be sent to any one of the sites in which Q is replicated and, a write
lock (Exclusive lock) request message must be sent to all the sites in which Q
is replicated. The lock-managers of all the sites in which Q is replicated are
responsible for handling lock and unlock requests locally individually.
Example:
In the figures,
- Q, R, and S are the different data items.
- Q is replicated in sites S1, S2, S3 and S6.
- R is replicated in sites S1, S2, S3, and S4.
- S is replicated at sites S1, S2, S4, S5, and S6.
How does Biased protocol handle Shared and Exclusive locks?
Shared Lock (Read Lock)
Figure 1
shows Biased protocol implementation for handling read request (Shared lock).
 |
| Figure 1 - Biased Protocol for Read Lock |
Let us assume that Transaction T1
needs data item Q.
Step
1: Transaction T1 initiated at site S5 and requests lock on data item Q. Q is
available in S1, S2, S3 and the site S6. According to the protocol, T1 has to lock Q in any one site
in which Q is replicated, i.e, in our example, we need to lock any 1 out of 4 sites
where Q is replicated. Assume that we have chosen the site S3.
Step 2: S5 requests S3 for shared lock on Q. The
lock request is represented in purple color.
Step 3: If the lock on Q can be granted, S3 can
grant lock and send a message to S5.
On
receiving lock grant, S5 executes the Transaction T1 (Reading can be done in
the locked site, in our case, it is S3).
Step 4: On successful completion of
Transaction, S5 sends unlock message to the site S3.
Exclusive Lock (Write Lock)
Figure 2
shows Biased protocol implementation for handling write request (Exclusive lock).
 |
| Figure 2 - Biased Protocol for Write Lock |
Let us assume that Transaction T1
needs data item Q. Q
is available in S1, S2, S3 and the site S6. Sites S4 and S5 do not have Q in
them, are represented in red color
Step
1: Transaction T1 initiated at site S5 and requests lock on data item Q. According to the protocol, T1 has to
lock Q in all the sites in which Q is replicated, i.e, in our example, we need
to lock all the 4 sites where Q is replicated.
Step 2: S5 requests S1, S2, S3, and S6 for exclusive
lock on Q. The lock request is represented in purple color.
Step 3: If the lock on Q can be granted at
every site, all the sites will respond with grant lock message to S5. (If any
one or more sites cannot grant, T1 cannot be continued)
On
receiving lock grant, S5 executes the Transaction T1 (When writing the data
item, transaction performs writes on all replicas).
Step 4: On successful completion of
Transaction, S5 sends unlock message to all sites S1, S2, S3, and S6.
Advantages:
- Read operation can be handled faster compared to Majority based protocol.If read operations are performed frequently in an application, biased approach can be suggested.
Disadvantages:
- Additional overhead on Write operation.
- Implementation is complex. We need to send (n/2 + 1) lock request messages, (n/2 + 1) lock grant messages, and (n/2 + 1) unlock messages for write operation.
- Deadlock would occur as discussed in the Majority Based protocol.
“Good habits
formed at youth make all the difference.”
Aristotle
|
***********