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 data D was written on server S1 for the 1st time (so it's first version of this data on this server) and we are saving it as D1. Similarly: D2([S1, 2]) means that server S1 handles write of data D for the 2 time (and this data becomes D2)
  • 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]) and D2([S1, 1], [S2, 2]) — D1 is ancestor of D2, because [S1, 1] = [S1, 1], and [S2, 1] <= [S2, 2]
  • D1([S1, 1], [S3, 1]) and D2([S1, 1], [S2, 1]) — D1 and D2 are in conflict, because [S1, 1] = [S1, 1], but [S3, 1] is not bigger than [S3, 0] (note: we don't have S3 entry in D2, so it's [S3, 0])