In this post, we will talk about the consistency models in distributed systems. Most of the content are collected from online resources and the book Database Internals.

Before we dive into details, there are some concepts need to be clarified. Oftentimes we hear about partial order and total order in the discussion of consistency models. They are concepts in Mathematics and in the context of distributed system they usually means a “happen before” relationship, either logically or physically.

There is another concept that sounds similar to these two. In some of the consistency model discussions, we see the usage of “global order”. It usually means the chronological order of events observed by all processes.

These two concepts focus on different aspects. The partial/total order puts emphasis on the ability to compare two different events, while the global order implies that at a given moment there is a global view that is accessible by processes.

Strict Consistency

The strict consistency is a theoretic concept. In this model, any write by any process is instantly available for the subsequent reads by any process; any read to a data item returns the value reflecting the most recent write.

If we plot events on a timeline, they should be dots instead of intervals. Moreover, this model implies that there is a global view/order of events. Note that with instant visibility combined with a global order of events, it essentially means there is no concurrent events and a single view is shared by all processes.

Linearizability

Linearizability is less strict than the strict consistency. Linerizability defines a total order of events. This order is consistent, which means that every read of the shared value should return the latest value written to this shared variable preceding this read, or the value of a write that overlaps with this read. Moreover, linearizable write access to a shared variable also implies exclusion: between the two concurrent writes, only one can go first.

One of the most important traits of linearizability is visibility: once the operation is complete, everyone must see it, and the system can’t “travel back in time,” reverting it or making it invisible for some participants. In other words, linearization prohibits stale reads and requires reads to be monotonic.

Linearizability recognizes that events take time to compete. However, they may still appear to be atomic. This atomic appearances comes from the fact that the concurrent writes are exclusive and that the reads are monotonic.

If we plot the events on the timeline, they will be represented by intervals. For writes, because concurrent writes are exclusive, they can be summarized by a point as well. In the book Database Internals, this is called linearization point.

In figure 2, W1 and W2 are concurrent writes. As they are exclusive, one of them must go first. In our example, W1 happens before W2 and the dots indicates the moment when the written values become available to all processes.

R1 is concurrent with both W1 and W2. According to linearizability model, R1 can return one of the following values

1. Initial value W0. This is the latest value preceding R1.
2. W1 because W1 and R1 are concurrent
3. W2 because W2 and R1 are concurrent

As we can see here, the value of R1 is not deterministic and compared to the strict consistency model it is less constrained.

R2 is similar to R1 as it is concurrent to both W1 and W2 as well but it has one more constraint: the value returned by R2 should be as recent as the one returned by R1. For example, if R1 returns the value written by W2, then R2 cannot return the stale value written by W1.

R3 is not concurrent with W2 and it occurs after the linearization point of W2, therefore in this case R3 should return the value written by W2.

Sequential Consistency

Sequential consistency allows ordering operations as if they were executed in some sequential order, while requiring operations of each individual process to be executed in the same order they were performed by the process.

One of the differences between sequential consistency and linearizability is that sequential consistency does not make concurrent writes appear instantaneous; in other words it recognizes concurrent writes.

Here are two examples from CIS 505: Software Systems Lecture Note on Consistency and Replication.

Example: Valid sequential consistent result

This result is sequential consistent because we can order the events in the following order:

P2::W(x)b -> P3::R(x)b -> P4::R(x)b -> P1::W(x)a -> P3::R(x)a -> P4::R(x)a

Example: non sequential consistent result

Assuming this result is sequential consistent and there is a valid sequential order.

In this example P3 gets b first and then gets a. This means in the sequential order, W(x)b happens before W(x)a. If we look at P4, it first gets value a and because a is the latest value for x P4 cannot get the b at a later time.

Therefore we find a contradiction, which means this result is not sequential consistent.

Causal Consistency

Under the causal consistency model, all processes have to see causally related operations in the same order. Concurrent writes with no causal relationship can be observed in a different order by different processes.

Causal consistency model is less strict than sequential consistency model in the sense that it allows different processes seeing different orders for some of events (e.g. non causal concurrent writes). It can be refined into the following session guarantees:

• Read your own write: every read operation following the write on the same or the other replica has to observe the updated value.
• Monotonic reads: If the read(x) has observed the value V, the following reads have to observe a value at least as recent as V or some later value.
• Write follows read: writes are ordered after writes that were observed by previous read operations. If other process can observe this write, it should also be able to observe the read unless it has been overwritten.
• Monotonic writes: Values originating from the same process appear in the order this process has executed them and this order is visible to all processes.

Example: Violation of causal consistency

In this example, P2 observes a first and then update x to b. This implies a causal order: W(x)a -> R(x)a -> W(x)b and all processes should observe this order. It follows that under causal consistency, P3 cannot observe a after b.

If P2 only write b to x without reading the value first, the result will be casual consistent because different processes are allowed to re-order non causal concurrent writes.

Eventual Consistency

Here is a definiton of eventual consistency:

If there are no additional updates performed against the data item, eventually all access return the latest written value.

An eventually consistent system is usually tunable. It can be characterized by three factors:

• Replication Factor N: Number of nodes that will store a copy of data.
• Write Consistency Level W: Number of nodes that have to acknowledge write for it to success.
• Read Consistency Level R: Number of nodes that have to respond to a read operation for it to succeed.

If we have \(R + W > N\), then the consistency is guaranteed because a replicate of the latest written value can always be reached.

One special value for consistency level is \(\lfloor{} N /2 \rfloor{} + 1\)

This consistency level is called quorum. If a system has this value as its write and read consistency level, it can tolerate \(\lfloor{}N/2\rfloor{}\) failed nodes, which means it can still function with failure of almost half of the nodes.

----- END -----

©2019 - 2023 all rights reserved