Wednesday, April 9, 2014

Quorum Consensus Protocol - Distributed Lock Manager Concurrency Control


Quorum Consensus Protocol / One of the Concurrency Control mechanisms in Distributed Lock Manager / Variants of Distributed Lock based Concurrency Control 



Do you know?
In Victoria, a state in Australia, only a licensed electrician is permitted to change the light bulb.


Quorum Consensus Protocol

This is one of the distributed lock manager based concurrency control protocol in distributed database systems. It works as follows;
1. The protocol assigns each site that have a replica with a weight.
2. For any data item, the protocol assigns a read quorum Qr and write quorum Qw. Here, Qr and Qw are two integers (sum of weights of some sites). And, these two integers are chosen according to the following conditions put together;
  • Qr + Qw > S – this rule avoids read-write conflict. (i.e, two transactions cannot read and write concurrently)
  • 2 * Qw > S – this rule avoids write-write conflict. (i.e, two transactions cannot write concurrently)
Here, S is the total weight of all sites in which the data item replicated.
How do we perform read and write on replicas?
A transaction that needs a data item for reading purpose has to lock enough sites. That is, it has lock sites with the sum of their weight >= Qr. Read quorum must always intersect with write quorum.
A transaction that needs a data item for writing purpose has to lock enough sites. That is, it has lock sites with the sum of their weight >= Qw.

Example:

(How does Quorum Consensus Protocol work?)

Let us assume a fully replicated distributed database with four sites S1, S2, S3, and S4.
1. According to the protocol, we need to assign a weight to every site. (This weight can be chosen on many factors like the availability of the site, latency etc.). For simplicity, let us assume the weight as 1 for all sites.
2. Let us choose the values for Qr and Qw as 2 and 3. Our total weight S is 4. And according to the conditions, our Qr and Qw values are correct;
Qr + Qw > S => 2 + 3 > 4                  True
2 * Qw > S => 2 * 3 > 4                     True
3. Now, a transaction which needs a read lock on a data item has to lock 2 sites. A transaction which needs a write lock on data item has to lock 3 sites.

CASE 1
Read Quorum Qr = 2, Write Quorum Qw = 3, Site’s weight = 1, Total weight of sites S = 4
Lock
Example
Discussion
Read Lock
1. Read request has to lock at least two replicas (2 sites in our example)
2. Any two sites can be locked
Write Lock
1. Write request has to lock at least three replicas (3 sites in our example)
Note that, read quorum intersects with write quorum. That is, out of available 4 sites, in our example, 3 sites to be locked for write and 2 sites to be locked for read. It ensures that no two transactions can read and write at the same time.
CASE 2
Read Quorum Qr = 1, Write Quorum Qw = 4, Site’s weight = 1, Total weight of sites S = 4
Read Lock
1. Read lock requires one site
Write Lock
2. Write lock requires 4 sites
Note that, read requires any one site and write requires all the sites, which is actually the implementation of Biased protocol. At the same time, if we make read and write quorum with the same value 3, then it resembles the implementation of Majority based protocol. That is the reason why Quorum Consensus protocol is mentioned as the generalization of the above said techniques.
 


Points to note:


  • The Quorums must be chosen very carefully. That is, if read operations are frequent then we would choose very small read quorum value so as to make read faster in available replicas and so on.

  • The chosen read quorum value must intersect the write quorum value to avoid read-write conflict.



“You are never too old to set another goal or to dream a new dream.”
C. S. Lewis


***********








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