Showing posts with label Distributed Lock Manager. Show all posts
Showing posts with label Distributed Lock Manager. Show all posts

Monday, April 7, 2014

Biased Protocol - Distributed Lock Manager Concurrency Control


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.
 

“Good habits formed at youth make all the difference.”
Aristotle




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