Consistency Models
Consistency in a distributed system means, that no matter which node we are reading from, we'll get the same data. In order to achieve that, we need to replicate the data written on mode node to others.
Before I go to the types of consistency, first I need to introduce few terms:
- N - number of replicas
- W - write quorum — how many acknowledgements of write we need to make sure that our write was successful
- R - read quorum — how many read operations we need to wait for to consider read successful
Now, based on the above definition, we have: Strong Consistency, Weak Consistency and Eventual Consistency.
Strong Consistency means, that reads always return the latest data. Most of the time it's achieved by blocking reads and writes to make sure system is consistent (sacrificing Availability). In strong consistency we can have the slowest responses because we need to wait for bigger R (more responses from other nodes). In this type we have W + R >= N. We know that at least one node has the newest data to ensure consistency.
With Weak Consistency, read operations may not see the latest data. It happens when W + R < N.
Eventual Consistency is a variation of a Weak Consistency, in which we may be sure that eventually, all updates will be propagated, and the system becomes consistent.
In case of Eventual Consistency we allow the system to be in inconsistent state, but we may force the client to do data reconciliation (inconsistency resolution).
To resolve inconsistencies we can use a technique called versioning using Vector Clocks. This is how it works:
- Each node maintains a vector of versions — changes of particular data
D
, for example:D1([S1, 1])
means that dataD
was written on serverS1
for the1
st time (so it's first version of this data on this server) and we are saving it asD1
. Similarly:D2([S1, 2])
means that serverS1
handles write of dataD
for the2
time (and this data becomesD2
) - Those vectors allows detecting out which data is an ancestor or sibling of which data
- If it's a sibling, it means that we have a conflict
- If it's an ancestor then we just have an evolution of data from one version to another
We can call operation X an ancestor of Y if all versions in vector Y are greater or equal to corresponding versions in X. On the other hand, X and Y are siblings if there is at least one versions in Y which is smaller than version in X. Examples:
D1([S1, 1], [S2, 1])
andD2([S1, 1], [S2, 2])
—D1
is ancestor ofD2
, because[S1, 1] = [S1, 1]
, and[S2, 1] <= [S2, 2]
D1([S1, 1], [S3, 1])
andD2([S1, 1], [S2, 1])
—D1
andD2
are in conflict, because[S1, 1] = [S1, 1]
, but[S3, 1]
is not bigger than[S3, 0]
(note: we don't haveS3
entry inD2
, so it's[S3, 0]
)