Computer Science and Engineering - Tutorials, Notes, MCQs, Questions and Answers: Distributed Lock Manager

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 Q_r and write quorum Q_w. Here, Q_r and Q_w are two integers (sum of weights of some sites). And, these two integers are chosen according to the following conditions put together;

Q_r + Q_w > S – this rule avoids read-write conflict. (i.e, two transactions cannot read and write concurrently)

2 * Q_w > 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 >= Q_r. 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 >= Q_w.

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 Q_r and Q_w as 2 and 3. Our total weight S is 4. And according to the conditions, our Q_r and Q_w values are correct;

Q_r + Q_w > S => 2 + 3 > 4 True

2 * Q_w > 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 Q_r = 2, Write Quorum Q_w = 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 Q_r = 1, Write Quorum Q_w = 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.