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
|
***********