Fermin Ordaz Reading time ~4 minutes

In the Review of Consistency Models - Part I we looked at:

  • Quiescent Consistency.

  • Strict Consistency.

  • Sequential Consistency.

This post covers Linearizability, Serializability, Strict Serializability and Causal Consistency.

Linearizability

Any execution is perceived in the same way by all the processes, as if all the read and write operations were executed in real-time order and respecting the program order of each one of them.

In a Linearizable data store:

  1. The write operations appear to occur instantaneously.
  2. Once the most recent value has been read, any subsequent read returns the same or an even more recent value.

The following history is Linearizable: example 2

As expected, once P2: W(x)2 takes place, any process sees the most recent value in any subsequent read operation.

On the other hand, The following history is not Linearizable: example 2

Because, in real-time ordering the operation P2:W(x)2 takes places after P1:W(x)1, and any subsequent read operation must return the value of 2.

Linearizability is composable, which means that the combination of individually Linearizable data items, is also Linearizable.

In order to develop some intuition about this property, let’s consider these two independently Linearizable histories for two different data items. example 2

example 2

If we combine them, then the composed history is also Linearizable, and there is no way of making it non Linearizable and at the same time maintain the individual ones Linearizables. example 2

Remember: Linearizability allows single operations on single objects ordered in real-time.

Serializability

Any execution is perceived in the same way by all the processes, as if groups of read and write operations were executed in some sequential order (arbitrary interleaving), respecting the program order of each one of them.

As you can see, Serializability is similar to Sequential Consistency, but at the level of group of operations (think transactions). In this case, the group of operations take place atomically in arbitrary interleaving.

Assuming that operations within parenthesis occur as a group, the following history is Serializable: example 2

As it can be rearranged in the following sequence: example 2

Which is consistent with the fact that P3:W(y)1 and P3:R(x)1 happened before P2:R(y)1 and P2:W(x)2. Notice how the group of operations were ordered arbitrarily and not respecting the real-time order of their invocations.

On the other hand, the following history would not be Serializable: example 2

As P2:R(y)1 implies that the P3 group of operations happened before P2’s group, but P3:R(x)2 implies the opposite.

Remember: Serializability allows group of operations on multiple objects ordered in arbitrary interleaving.

Strict Serializability

Any execution is perceived in the same way by all the processes, as if groups of read and write operations were executed in real-time order and respecting the program order of each one of them.

In other words, Strict Serializability borrows the real-time ordering from Linearizability and applies it to groups of operations as indicated by the Serializability definition.

The first example from Serializabilty is not Strict Serializable example 2

As it does not respect real-time ordering, but just by making a little adjustment, it becomes Strict Serializable: example 2

As this respects the fact that P2 group of operations happened before P3.

Remember: Strict Serializability allows group of operations on multiple objects ordered in real-time.

Causal Consistency

Write operations that are potentially causally related are perceived in the same way by all the processes, as if they were executed in real-time order and respecting the program order of all the processes.

In other words, Causal Consistency is similar to Linearizability, but instead of requiring that all operations must be ordered in real-time, it is limited only to causally related operations.

Two operations are causally related if the execution of one could affect the result of the other one. Consider the following examples:

  • A read operation on x, followed by a write operation on y are potentially causally related as the write value of y might be derived by the value of x.

  • A write operation on x, followed by a read operation on x are potentially causally related as the read value of x is returning the previously written value.

  • Two simultaneous write operations on different or same variables are not causally related.

  • Two operations not causally related are called concurrent.

The following history is Causally Consistent: example 2

As P1:W(x)1 and P2:W(x)2 are considered concurrent and other processes can see their writes in different order.

Just by introducing a small variation, the following history is not Causally Consistency: example 2

Since P2:R(x)1 was generated by P1:W(x)1 and might affect the result of P2:W(x)2, therefore P1:W(x)1 and P2:W(x)2 are causally related and must be seen by all the processes in the same order.

Yet, another small variation makes this history Causally Consistent: example 2

According to a real-time ordering P1:W(x)1 occurred after P2:R(x)0 and cannot affect it. Therefore, P1:W(x)1 and P2:W(x)2 are not causally related.

Remember: Causal Consistency allows single operations on single objects, but only causally related operations must be ordered in real-time.

References

Fermin Ordaz Reading time ~3 minutes

A consistency model is a contract offered by a data store to a client application. It defines the behavior when multiple clients or processes perform concurrent read and write operations on the data store, particularly when these operations are in conflict.

Consistency models are important for the following reasons:

  • It allows us to know what to expect from a data store and design correct programs.
  • It helps us to understand the increasing number and variety of data stores available today.

In the following descriptions and examples we’ll assume the following model and conventions:

  • Different processes P1…Pn run simultaneously on different nodes N1…Nn with local copies of individual data items x and y, which are replicated to other nodes in the network.
  • Time progresses from left to right
  • Variables x and y are initialized with 0
  • P1:W(x)1 : process P1 performs a write operation of value 1 on variable x
  • P2:R(x)2 : process P2 performs a read of value 2 from variable x.

Quiescent Consistency

Overlapping read and write operations can be seem in some sequential order (arbitrary interleaving), while the non overlapping operations are perceived in the same way by all the processes as if they occurred in real-time order.

This means that during a period of quiescence (no pending operations) operations seems to occur in real-time, and during periods of concurrent operations they seem to occur in an arbitrary order.

For example, the following history is Quiescent Consistent: example 1

Since P1:W(x)1 and P2:W(x)2 are non overlapping, they seem to take place in real-time, and both P3 and P4 read the same value 2 from variable x. Also, the set of overlapping operations P2:R(x)2, P3:W(x)3 and P4:R(x)3 allow a read of two different values from x.

On the other hand, the following history is not Quiescent Consistent: example 2

As it violates the property that during non overlapping operations like P1:W(x)1 and P2:W(x)2 should appear to occur in real-time order.

Remember: Quiescent Consistency allows arbitrary interleaving of overlapping single operations on single single objects, while non overlapping operations must appear to occur in real-time ordering.

Strict Consistency

Strict consistency guarantees that a given read operation always returns the most recent written value of a given data element.

The most recent aspect of the definition implies that we have to have a real-time ordering to be able to unambiguously identify which one was the most recent operation.

If we consider the following two processes P1 and P2 on different nodes N1 and N2 respectively. example 2

Where P1 writes the value of 1 to x and Process P2 immediately reading it from its local copy. Strict consistency requires that the write operation takes no latency to propagate from N1 to N2, regardless of how far the two nodes are, and how close in time the read operation is to the write operation. This makes this consistency model intuitively easy to understand, but virtually impossible to implement in distributed systems.

Remember: Writes are instantaneously visible to all processes and real-time ordering is maintained.

Sequential Consistency

Any execution is perceived in the same way by all the processes, as if all the read and write operations were executed in some sequential order (arbitrary interleaving), respecting the program order of each one of them.

For example, The following history is Sequentially Consistent: example 2

In this case, even when P1:W(x)1 was invoked first, it really took effect after P2:W(x)2 (arbitrary interleaving). Both processes P2 and P3 see the same sequence of values 2,1 from variable x.

On the other hand, the following is not a Sequentially Consistent history: example 2

Because process P2 is seeing the sequence 2,1 while P3 is seeing 1,2 from the same variable x. This violates the property that all processes see the same interleaving of the operations.

Similarly, the following is not a Sequentially Consistent history: example 2

As it does not respect the program order of the process P3, since the first read operation P3:R(y)1 should have had returned 0 instead of 1 because the operation P3:W(y)1 comes as the second operation.

Sequential Consistency applies to single objects (ex: only x or y but not both) and single operations (ex: read or write, but not grouping of multiple reads and/or writes).

Remember: Sequential Consistency allows arbitrary interleaving of single operations on single single objects.

References