Category Archives: Behind the Scene

Quorum Based Protocol

A quorum is the minimum number of votes that a distributed transaction has to obtain in order to be allowed to perform an operation in a distributed System.

All Data items are associated with a version number
As the Data items are modified their associated version number is changed
Any write operation performed is executed on a subset of all Replicas (Write Quorum)
To Read client must contact to subset of replicas to find newest version of data item
(Read Quorum)
Quorum based protocol requires client to request and acquire permission of multiple servers before performing any operation on replicas
Any pair of Read and Write quorum must contain common copies,resulting in no conflicting operation on same copy
Two Write Quorums must also overlap preventing write-write conflict

Say Data is replicated across N Servers let N be equal to 5
Now say N1,N2,N3 are the read quorums(NR) and N3,N4,N5 are write quorums(NW)
The two conditions
1)NR+NW>N
2)NW>N/2
1st condition make sure no conflicting operation is performed on same copy
2nd condition make sure that only one write operation will get the quorum preventing 2 write operations writing  at the same time(Write-Write Conflict)

 

 

Vector Clock

What is Vector Clock?
To provide reliability and availability data is stored at various data centers ,vector clock helps in assuring the consistency in data being read at any point of time

Say there are n nodes and for each node there is a cycle thus if a system has 3 nodes around which the data is replicated there will be array of 3 cycles with one cycle per node

Each node maintains its own tick and updates the same each time any modification is made along with passing the message and updated counter to subsequent replicas

Initial values of tick for all nodes N1,N2,N3 is T=0 Now say some modification is made at node N1 and it ticks it clocks by 1
N1 T1 passes it to N2,N3

(N1 T1)(N2 T0)(N3 T0)
(N1 T1)(N2 T0)(N3 T0)
(N1 T1)(N2 T0)(N3 T0)

Now say changes are made to data at node N2 thus  it ticks clock  by 1 from T0 to T1 and passes the same to N1,N3
temp

 Say Now N3 does an update and communicates the same to N2 and N1 and same N2 does and communicates the same to N1 and N3 and N1 also does the same
But due to network breakdown the messages were not delivered and following were the status of vector with each node
temp

To resolve the above conflict  a different algorithm is required which varies as per requirements