Part I - What's Data Consistency Model and Why Should We Care?

Data Consistency Model - it is a Semantic Contract between a data storage system and its user. Here, data storage system may refer to hardware system ( for example : memory sub-system inDSM, SMP, CMP computers) , or software systems (for example: distributed file system, web caching or distributed database).

Essentially, Consistency Model defines what value to return in a read operation.

The most natural semantic for storage system is - "read should return the last written value". It is intuitive in memory system with uniprocessor associated, where no concurrent access and no data replication exist.

But when concurrent client access and multiple replica exist, it's not easy to identify what "last write" means, mainly due to the lack of global time clock in parallel/distributed system.

So various data models are proposed to define various data semantic when Contention and Replication exists:
- Data Contention - In memory sub system of parallel computers, there may be multiple processors that access the same memory location at the same period of time, what's the semantic each processor should expect? (different process access the same data item)
- Data Replication - In distributed file/database system, each data block is replicated at multiple places, even access(read/write/modify) requests from the same client may involve more than one replicas, what's the semantic in client's perspective? (data item is replicated)
- Both Contention & Replication : What if multiple clients access replicated data blocks? What if there is a local cache for each processor in SMP system? (many processes access replicated data items)

Part II - The Various Models

There are many consistency models exist in computer architectures and distributed storage community. Why people invent so many semantics between storage and its clients? The reason is the trade off between Strict Semantic VS Available Optimization Space - strict (also simple and easy to understand, use and implement) semantic will limit the space that we can use to improve availability and do performance optimization. So each model has its advantages and drawbacks.

Before describe various models, we should clarify some concepts first:

Program Order - the order of operations (on data items) that is implied by the order of program statements(or assembly instructions). It's the issuing order of operations that are from the same thread/process.

Write Atomicity - write operation performs as no concurrent/overlapped operations can occur. So the meaning of "Atomicity" here differs from that in DBMS field, where "Atomicity" means that all ops in a transaction will be performed or none of them will be performed.

Consistency VS Coherence/Replication, Consistency focus on the semantic of data store (a set of data item) for multiple client accessing, while Coherence/Replication only deal with the semantic (and how to implement it) of a replicated data item (multiple replica exist) when it is accessed by multiple clients. Coherence/Replication is just part of the Consistency Model. Coherence / Replication Protocol only describes how to implement part of the semantic of some specific data consistency model.

[Update@07/23: Coherence and Replication are very similar and deal with the same problem, but the former is used in hardware system (for example, cache coherence) and the later is used in software system (for example, in distributed files system and database system]

Following are various Consistency Model descriptions:

1. Atomic Consistency/Strict Consistency

It means that for a particular data item (byte, cache block and file region etc.), each read will return the latest update. I.E. events are visible to all clients as they occurs/issues. As we already said, due to the lack of global time clock in distributed/parallel system, it is very hard to implement if not impossible.

2. Sequential Consistency

This model is defined as - "The result of any execution is the same as if the operations of all the processors were executed in some sequential order and the operations of each individual processor appears in this sequence in the order specified by its program." - Leslie Lamport

This definition implies:
1. Events/Operations from the same process are executed in program order
2. Every client sees the same order of all events/updates, which is a sequential one

Goods:
- Ensures every body sees the same order, very good for data replication
- Preserves causality

Bads:
- Many interleavings are valid (two independent program with M mem ops and N mem ops will have (M + N)!/(M!N!) valid interleavings)
- Different runs of a program might act differently
- Execution order may be very different from issuing order

3. Causal Consistency

Events that are causally related must be seen by everybody in the same order. Unrelated ("concurrent") events can be seen in different orders.

The challenge in implementing this model lies in how to identify "causally related" events.

4. Eventual Consistency

If no updates take place for a long time (inconsistency window), all replicas will gradually become the latest version of the value.

In this model, if client reads data from different replica, it's hard to define a clear semantic about the return value. To resolve this problem, client-centric consistency is introduced. These models focus on the semantic in a single client's perspective.

Monotonic Reads - If a process reads the value of an object, any successive read operations on that object by that process will always return the same or more recent value.

Monotonic Writes - A write operation by a process on a data item x is completed before any successive write operation on x by the same process.

Read Your Writes - The effect of a write operation by a process on data item x will always be seen by a successive read operation on x by the same process. A closely related model is "Session Consistency". In this model, Read Your Write semantic only works within a session context and not cross session boundary.

Write Follow Reads - Any successive write operation by a process on a data item x will be performed on a replica of x that is up-to-date with the value most recently read by that process.

5. Weak Consistency

A storage system is said to support weak consistency if:

1. All synchronization operations are seen by all processors in the same sequentially order.
2. All data operations may be seen in different order on different processors. (But order of ops on the same data item is preserved)
   
3. The set of both read and write operations in between different synchronization operations is the same in each processor.

An alternative definition is as:

1. Accesses to synchronization variables are sequentially consistent.
2. No access to a synchronization variable is allowed to be performed until all previous writes have completed everywhere.
3. No data access (read or write) is allowed to be performed until all previous accesses to synchronization variables have been performed.

This model is weaker than sequential consistency model, since no order assumption can be made on data operations between consecutive synchronization operations.

The weak consistency leverage the fact that - between consecutive sync operations, no other process can use the data being written. So it's safe to reorder write operations on different mem locations. But the order of operations on the same location must be preserved to ensure a reasonable memory semantic.

6. Release Consistency

Release consistency is an extension of weak consistency that exploits the information about acquire, release, and nonsynchronization accesses.

1. Before an ordinary LOAD or STORE access is allowed to perform with respect to any other processor, all previous acquire accesses must be performed, and
2. Before a release access is allowed to perform with respect to any other processor. all previous ordinary LOAD and STORE accesses must be performed, and
3. Special accesses are processor consistent with respect to one another.

In Release Consistency Model, all write operations by a certain node are seen by the other nodes after the former releases the object and before the latter acquire it, but a node must call acquire to get up-to-date values.

There are two kinds of coherence protocols that implement release consistency:
- eager, where all coherence actions are performed on release operations, and
- lazy, where all coherence actions are delayed until after a subsequent acquire

7. Entry Consistency

Like all variants of Release Consistency, it requires the programmer to use acquire and release at the start and end of each critical section, respectively. However, entry consistency requires each ordinary shared variable to be associated with some synchronization variable such as a lock or barrier.

- An acquire access of a synchronization variable S is not allowed to perform with respect to process Pi until all updates to the guarded shared data Ds have been performed with respect to process Pi.

- Before an exclusive mode access to a synchronization variable S by processor Pi is allowed to perform with respect to Pi, no other processor may hold S in non-exclusive mode.

- After an exclusive mode access to S has been performed, any processor's next non-exclusive mode access to S may not be performed until it is performed with respect to the owner of S.

8. Processor Consistency

- Writes done by a single processor are received by all other processors in the order in which they were issued, but
- Writes from different processors may be seen in a different order by different processors

The motivation behind this model is to better reflect the reality of networks in which the latency between different nodes can be different.

This model is also known as FIFO Consistency and Pipeline Random Access Memory Consistency.

Notes on Nex Steps:
1. Why People Invent Each Model?
2. What's Good and What's Bad for Each Model?

[Reference]
[1] Wiki on Consistency Model
[2] Summary on Consistency Model by CTO@Amazon
[3] Shared Memory Consistency Models: A Tutorial
[4] Memory Consistency Models
[5] Notes On Consistency
[6] Entry Consistency, Midway : Shared Memory Parallel Programming with Entry Consistency for Distributed Memory Multiprocessors
[7] Release Consistency, Memory Consistency and Event Ordering in Scalable Shared-Memory Multiprocessors
[8] Weak Consistency, Memory Access Buffering in Multiprocessors
[9] Memory Ordering in Modern Microprocessors (Part I, Part II)
[10] Wiki on Cache Coherence