Distributed computing — Quorum consistency in replication
This article aims to cover what is quorum consistency, why do we need it and it’s limitations in case of multiple replica system.
“The major difference between a thing that might go wrong and a thing that cannot possibly go wrong is that when a thing that cannot possibly go wrong goes wrong it usually turns out to be impossible to get at or repair.”
Douglas Adams, Mostly Harmless (1992)
Quorum consistency is used in systems where consistency is more important than availability (CAP theorem) for write and read but we still want a fairly available system.
In systems with multiple replicas there is a possibility that the user reads inconsistent data. This happens say when there are 2 replicas, N1 and N2 in a cluster and a user writes value v1 to node N1 and then another user reads from node N2 which is still behind N1 and thus will not have the value v1, so the second user will not get the consistent state of data.
In order to achieve a state where at least one node has consistent data we use quorum consistency.
Quorum is achieved when nodes follow the below protocol
w + r > n
n = nodes in the quorum group
w = minimum write nodes
r = minimum read nodes
w is our write quorum and r is our read quorum
Let’s understand this with an example
Say we have 3 nodes, N1, N2 and N3 in the cluster so n = 3 in this case.
n = 3, w = 2, r =2 our quorum equation is met
2 + 2 > 3.
Say there is a key “book” against which the users sends write requests:
Request 1 sets the value to “Philosopher’s Stone”
Request 2 sets the value to “Chamber of Secrets”
Write is successful in N1 and N2 but fails for N3 due to some reason.
But since it meets are quorum write which we have set to 2, our requirement is met.
Now the user wishes to read the value back for the key “book”.
Read request is successful on N1 and N3 but fails for N2.
Thus user receives, “Chamber of secrets” from N1 and “Philosopher’s Stone.” from N3.
Since these are conflicting values, the most recent one is considered as the correct one (Resolving conflicts is another topic but for the simplicity of understanding we made the assumption of following Last Write Wins approach)
Our read quorum is met as we got response for 2 nodes and also we got the latest value thus meeting our consistency.
Thus with quorum we get at least one node with consistent values in case of replication.
Most databases follow w = r= (n+1)/2 approach where n is generally odd number.
Another equation that is also followed is
2f+1 = n
f = Total number of failure nodes permitted
n = total number of nodes
Thus for our example above where n = 3:
2f +1 = 3
f = (3–1)/2 = 1
Say if n = 5, we will get 2 failure nodes permitted.
This gives a fair availability and a consistent system.
Limitations to quorum consistency
This system looks perfect theoretically but let’s highlight some practical limitations to quorum consistency:
- Availability is at risk — In case of n = 3, w = r =2, say if 2 nodes are unavailable for write, we will choose not to write data even though one node is available, thus risking the availability of the system.
- Sloppy Quorums — One thing to remember is that we fix and choose are nodes that are considered as part of n. There can be more than one quorum setup in a large cluster.
Now say 2 write nodes are down in our setup Q1 so 1 write node is available in Q1 and say in Q2 setup we have 1 write node available, some systems borrow the write node from Q2 to achieve ‘Sloppy quorum’ which is eventually settled. - Write conflicts issues still exist in case of concurrent requests
- Say if a node which has a new value fails in future and its data is replaced by a node with old data — in our write example if N1 fails in future and it’s data is replaced with N3, so now N1 and N3 have values ‘Philosopher’s Stone’ thus breaking our previous quorum condition.
Photo by Andrej Lišakov on Unsplash
