Consistency model

From Wikipedia, the free encyclopedia
Jump to: navigation, search

In computer science, consistency models are used in distributed systems like distributed shared memory systems or distributed data stores (such as a filesystems, databases, optimistic replication systems or Web caching). The system supports a given model if operations on memory follow specific rules. The data consistency model specifies a contract between programmer and system, wherein the system guarantees that if the programmer follows the rules, memory will be consistent and the results of memory operations will be predictable.

High level languages, such as C, C++, and Java, partially maintain the contract by translating memory operations into low-level operations in a way that preserves memory semantics. To hold to the contract, compilers may reorder some memory instructions, and library calls such as pthread_mutex_lock() encapsulate required synchronization.[1]

Verifying sequential consistency is undecidable in general, even for finite-state cache-coherence protocols.[2]

Consistency models define rules for the apparent order and visibility of updates, and it is a continuum with tradeoffs.[3]

Example[edit]

Assume that the following case occurs:[3]

  • The row X is replicated on nodes M and N
  • The client A writes row X to node N
  • After a period of time t, client B reads row X from node M

The consistency model has to determine whether client B sees the write from client A or not.

Types[edit]

A non-exhaustive list of consistency models are

Strict Consistency[edit]

Strict consistency is the strongest consistency model. It defines that if a process reads any memory location, the value returned by the read operation is the value written by most recent write operation. For an uniprocessor system, this model makes perfect sense. But it is almost impossible to implement the strict consistency model in distributed shared memory systems. This is because of the following fact. Consider a situation where there are two processors, A and B. Processor A writes a value at a particular time instance and processor B reads that value at a later time. Consider a light cone originating at processor A. If processor A and processor B are placed adjacent to each other on a timeline, the point where a ray of light from this light cone can touch processor B's timeline determines the instance at which processor B can see the new value of the data written by processor A. If the processor B tries to read data before this time instance, it would read the previous value of data, although processor A had written a new value, a while ago.

Cache Consistency[5][edit]

Cache consistency[6] defines that all write operations to the same memory location are performed in some sequential order.

Processor Consistency[5][edit]

Processor consistency model is an intermediate level weaker than strong ordering and stronger than weak ordering. It defines that if the operations of each individual process are performed in the sequential order defined by its program, the result is the same in any execution. The orders of two processes' performed write operations observed by them or any other process is not necessarily identical.

Slow Consistency[edit]

Slow Memory

In slow consistency,[6] if a process reads a value previously written to a memory location, it cannot read any earlier writes to that location. Writes performed by a process is immediately visible to that process. Slow consistency is a weaker model than PRAM and cache consistency. It seems really weak to be considered as usable consistency.

Example: Slow memory diagram depicts a slow consistency example. First process writes 1 to the memory location X and then it writes 1 to the memory location Y. Second process reads 1 from Y and it reads 0 from X while X has written before Y.

Hutto, Phillip W., and Mustaque Ahamad (1990)[7] illustrate that by appropriate programming, slow memory (consistency) can be expressive and efficient. They mention that slow memory has two valuable properties; locality and supporting reduction from atomic memory. They propose two algorithms to present the expressiveness of slow memory.

Local Consistency[6][edit]

In Local consistency, each process performs its own operations in the order defined by its program. There is no constraint on the write operations order of other processes that appear to perform. Local consistency is the weakest consistency model in shared memory systems.

General Consistency[edit]

In General Consistency,[8] all the copies of a memory location are eventually identical after all processes' writes are completed.

Relaxed Memory Consistency Models[9][edit]

Some different consistency models can be defined by relaxing one or more requirements in sequential consistency called relaxed consistency models. These consistency models do not provide memory consistency in hardware level. In fact, the programmers are responsible to provide the memory consistency by applying synchronization techniques.

There are four comparisons to define the relaxed consistency:

  • Relaxation: One way to categorize the relaxed consistency is to define which sequential consistency requirements are relaxed. We can have less strict models by relaxing either program order or write atomicity requirements. In relaxing program order, any or all the ordering of operation pairs, write-after-write, read-after-write, or read/write-after-read, can be relaxed. In the relaxed write atomicity model, a process can view its own writes before any other processors.
  • Synchronizing vs. Non-Synchronizing: A synchronizing model can be defined by dividing the memory accesses into two groups and assigning different consistency restrictions to each group considering that one group can have a weak consistency model while the other one needs a more restrict consistency model. In contrast, non-synchronizing Model assigns the same consistency model to the memory access types.
  • Issue vs. View-Based:[6] Issue method provides sequential consistency simulation by defining the restrictions for processes to issue memory operations. Whereas, view method describes the visibility restrictions on the events order for processes.
  • Relative Model Strength: Some consistency models are more restrict than others. The strength of a model can be defined by the program order or atomicity relaxations and the strength of models can be compared. Some models are directly related if they apply same relaxations or more. On the other hand, the models that relax different requirements are not directly related.

Relaxation Models[edit]

The following models are some models of relaxed consistency:

Weak Ordering[edit]

There are two categories of memory operations in weak ordering; data operations and synchronization operations.

Release Consistency[edit]

Processor Consistency[5][edit]

Processor consistency model is an intermediate level weaker then strong ordering and stronger that weak ordering. It defines that if the operations of each individual process are performed in the sequential order defined by its program, the result is the same in any execution. The orders of two processes' performed write operations observed by them or any other process is not necessarily identical.

Transactional Memory Models [9][edit]

Transactional Memory model is the combination of cache coherency and memory consistency models as a communication model for shared memory systems supported by software or hardware; a transactional memory model provides both memory consistency and cache coherency. A transaction is a sequence of operations executed by a process that transforms data from one consistent state to another. A transaction either commits when there is no conflict or aborts. In commits, all changes are visible to all other processes when a transaction is completed while aborts discard all changes. Compared to relaxed consistency models, a transactional model is easier to use and can provide the higher performance than a sequential consistency model.

Transactional Cache Consistency[10][edit]

In client data caching (dynamic form of data replication), the correctness of multiple copies must be enforced. In database systems, there is a close relation between transactions and correctness of concurrent operations on distributed or replicated data. FRANKLIN, Carey, and Livny, 1997[10] describe two types of caching; intratransaction caching and intertransaction caching.

In distributed database systems inconsistency detection can be performed in some different ways. In one approach, when a cache data item is accessed by a client during a transaction, the client must make sure that all copies of that data item are consistent by comparing the data item with available cached version on the server. Once the cached version is validated, the transaction can be completed. In other approach, the cached item is considered consistent during transactions. If the inconsistency of cached data is detected during the transaction, the transaction aborts.[11]

Consistency and Replication[11][edit]

The reliability and performance are two main reasons for replicating. Reliability can be achieved in a replicated file system by switching to another replica in the case of the current replica failure. The replication also protects data from being corrupted by providing multiple copies of data on different replicas. It also improves the performance by dividing the work. While replication can improve performance and reliability, it can cause the consistency problem in multiple copies of data. The multiple copies are consistent if a read operation returns the same value from all copies and a write operation as a single atomic operation (transaction) updates all copies before any other operation takes place. Tanenbaum, Andrew, & Maarten Van Steen, 2007 refer to this type of consistency as tight consistency provided by synchronous replication. However, applying global synchronizations to keep all copies consistent is costly. One way to decrease the cost of global synchronization and improve the performance can be weakening the consistency restrictions.

Data-Centric Consistency Models[11][edit]

Tanenbaum et al., 2007 defines the consistency model as a contract between the software (processes) and memory implementation (data store). This model guarantees that if the software follows certain rules, the memory works correctly. Since, in a system without a global clock, defining the last operation writes is difficult, some restrictions can be applied on the values that can be returned by a read operation.

Consistent Ordering of Operations[11][edit]

Some consistency models such as sequential and also causal consistency models deal with the order of operations on shared replicated data in order to provide consistency. In this models, all replicas must agree on a consistent global ordering of updates.

Sequential Consistency[edit]

The goal of data-centric consistency models is to provide a consistent view on a data store where processes may carry out concurrent updates. One important data-centric consistency model is sequential consistency defined by Lamport (1979).[12] Tanenbaum et al., 2007[11] defines sequential consistency under following condition:

"The result of any execution is the same as if the (read and write) operations by all processes on the data store were executed in some sequential order and the operations of each individual process appear in this sequence in the order specified by its program."[11]

Lamport[12] also defines two requirements to implement the sequential consistency; program order and write atomicity.

  • Program order: Program order guarantees that each process issues a memory request ordered by its program.
  • Write atomicity: Write atomicity defines that memory requests are serviced based on the order of a single FIFO queue.

In sequential consistency, there is no notion of time or most recent writes operation. There are some operations interleaving that is same for all processes. A process can see the write operations of all processes but it can just see its own read operations.

Linearizability[13] (Atomic memory)[9] can be defined as a sequential consistency with real time constraint by considering a begin time and end time for each operation. An execution is linearizable if each operation taking place in linearizable order by placing a point between its begin time and its end time and guarantees sequential consistency.

Causal Consistency[11][edit]

The causal consistency defined by Hutto and Ahamad, 1990[7] is a weaker consistency model than sequential consistency by making the distinction between causally related operations and those that are not related. For example, if an event b takes effect from an earlier event a, the causal consistency guarantees that all processes see event b after event a.

Tanenbaum et al., 2007[11] defines that a data store is considered causal consistent under the following condition:

"Writes that are potentially causally related must be seen by all processes in the same order. Concurrent writes may be seen in a different order on different machines."[11]

Grouping Operations[11][edit]

In grouping operation, accesses to the synchronization variables are sequentially consistent. A process is allowed to access a synchronization variable that all previous writes have been completed. In other words, accesses to synchronization variables are not permitted until all operations on the synchronization variables are completely performed.

Continuous Consistency[edit]

The continuous consistency is defined later in the consistency protocol section.

Client-Centric Consistency Models[11][edit]

In distributed systems, maintaining sequential consistency in order to control the concurrent operations is essential. In some special data stores without simultaneous updates, client-centric consistency models can deal with inconsistencies in a less costly way. The following models are some client-centric consistency models:

Eventual Consistency[11][edit]

An eventual consistency is a weak consistency model in the system with the lack of simultaneous updates. It defines that if no update takes very long time, all replicas eventually become consistent.

Monotonic Read Consistency[edit]

Tanenbaum et al., 2007[11] defines monotonic read consistency as follows:

"If a process reads the value of a data item x, any successive read operation on x by that process will always return that same value or a more recent value."[11]

Monotonic read consistency guarantees that after a process reads a value of data item x at time t, it will never see the older value of that data item.

Monotonic Write Consistency[edit]

Monotonic write Consistency condition is defined by Tanenbaum et al., 2007[11] as follows:

"A write operation by a process on a data item X is completed before any successive write operation on X by the same process."[11]

Read-your-writes Consistency[edit]

A value written by a process on a data item X will be always available to a successive read operation performed by the same process on data item X.[11]

Writes-follows-reads Consistency[edit]

In Writes-follow-reads consistency, updates are propagated after performing the previous read operations. Tanenbaum et al., 2007 defines the following condition for Writes-follow-reads consistency:

"A write operation by a process on a data item x following a previous read operation on x by the same process is guaranteed to take place on the same or a more recent value of x that was read."[11]

Consistency Protocols[11][edit]

The implementation of a consistency model is defined by a consistency protocol. Tanenbaum et al., 2007 illustrates some consistency protocols for data-centric models.

Continuous Consistency[edit]

Continuous consistency introduced by Yu and Vahdat (2000).[14] In this model, consistency semantic of an application is described by using conits in the application. An application specifies the conits as physical or logical consistency units. They introduce three inconsistencies that can be tolerated by applications.

  • Deviation in numerical values[14] Numerical deviation bounds the difference between the conit value and relative value of last update. A weight can be assigned to the writes which defines the importance of the writes in a specific application. The total weights of unseen writes for a conit can be defined as a numerical deviation in an application. There are two different types of numerical deviation; absolute and relative numerical deviation.
  • Deviation in ordering[14] Ordering deviation is the discrepancy between the local order of writes in a replica and their relative ordering in the eventual final image.
  • Deviation in staleness between replicas[14] Staleness deviation defines the validity of the oldest write by bounding the difference between the current time and the time of oldest write on a conit not seen locally. Each server has a local queue of uncertain write that is required an actual order to be determined and applied on a conit. The maximal length of uncertain writes queue is the bound of ordering deviation. When the number of writes exceeds the limit, instead of accepting new submitted write, the server will attempt to commit uncertain writes by communicating with other servers based on the order that writes should be executed.

If all three deviation bounds set to zero, the continuous consistency model is the strong consistency.

Primary-Based Protocols[11][edit]

Primary backup protocol
Primary-backup protocol (local-write)

Primary-Based Protocols can be considered as a class of consistency protocols that are simpler to implement. For instance, sequential ordering is a popular consistency model when consistent ordering of operations is considered. The sequential ordering can be determined as primary-based protocol. In these protocols, there is an associated primary for each data item in a data store to coordinate write operations on that data item.

Remote- Write Protocols[11][edit]

In the simplest primary-based protocol that supports replication, also known as primary-backup protocol, writes operation are forwarded to a single server and read operations can be performed locally.

Example: Tanenbaum et al., 2007 gives an example of a primary-backup protocol. The diagram of primary-backup protocol shows an example of this protocol. When a client requests a write, the write request is forwarded to a primary server. The primary server sends request to backups to perform the update. The server then receives the update acknowledgement from all backups and sends the acknowledgement of completion of writes to the client. Any client can read the last available update locally. The trade-off of this protocol is that a client who sends the update request might have to wait so long to get the acknowledgement in order to continue. This problem can be solved by performing the updates locally, and then ask other backups perform their updates. The non-blocking primary-backup protocol does not guarantee the consistency of update on all backup servers. However, it improves the performance. In the primary-backup protocol, all processes will see the same order of write operations since this protocol orders all incoming writes based on a globally unique time. Blocking protocols guarantee that processes view the result of the last write operation.
Local-Write Protocols[11][edit]

In primary-based local write protocols, primary copy moves between processes willing to perform an update. To update a data item, a process first moves it to its location. As a result, in this approach, successive write operations can be performed locally while each process can read their local copy of data items. After the primary finishes its update, the update is forwarded to other replicas and all perform the update locally. This non-blocking approach can lead to an improvement. The diagram of the local-write protocol depicts the local-write approach in primary-based protocols. A process requests a write operation in a data item x. The current server is considered as the new primary for a data item x. The write operation is performed and when the request is finished, the primary sends an update request to other backup servers. Each backup sends an acknowledgment to the primary after finishing the update operation.

Replicated-Write Protocols[11][edit]

In Replicated-Write Protocols, unlike the primary-based protocol, all updates are carried out to all replicas.

Active Replication[11][edit]

In active replication, there is a process associated to each replica to perform the write operation. In other words, updates are sent to each replica in the form of an operation in order to be executed. All updates need to be performed in the same order in all replicas. As a result, a totally-ordered multicast mechanism is required. There is a scalability issue in implementing such a multicasting mechanism in large distributed systems. There is another approach in which each operation is sent to a central coordinator (sequencer). The coordinator first assigns a sequence number to each operation and then forwards the operation to all replicas. Second approach cannot also solve the scalability problem.

Quorum-Based Protocols[11][edit]

Voting can be another approach in replicated-write protocols. In this approach, a client requests and receives permission from multiple servers in order to read and write a replicated data. As an example, suppose in a distributed file system, a file is replicated on N servers. To update a file, a client must send a request to at least N+1 in order to make their agreement to perform an update. After the agreement, changes are applied on the file and a new version number is assigned to the updated file. Similarly, for reading replicated file, a client sends a request to N+1 servers in order to receive the associated version number from those servers. Read operation is completed if all received version numbers are the most recent version.

Cache-Coherence Protocols[11][edit]

In a replicated file system, a cache-coherence protocol provides the cache consistency while caches are generally controlled by clients. In many approaches, cache consistency is provided by the underlying hardware. Some other approaches in middleware-based distributed systems apply software-based solutions to provide the cache consistency. Cache consistency models can differ in their coherence detection strategies that define when inconsistencies occur. There are two approaches to detect the inconsistency; static and dynamic solutions. In the static solution, a compiler determines which variables can cause the cache inconsistency. So, the compiler enforces an instruction in order to avoid the inconsistency problem. In the dynamic solution, the server checks for inconsistencies at runtime to control the consistency of the cached data that has changed after it was cached. The coherence enforcement strategy is another cache-coherence protocol. It defines that how to provide the consistency in caches by using the copies located on the server. One way to keep the data consistent is to never cache the shared data. A server can keep the data and apply some consistency protocol such as primary-based protocols to ensure the consistency of shared data. In this solution, only private data can be cached by clients. In the case that shared data are cached, there are two approaches in order to enforce the cache coherence. In first approach, when a shared data is updated, the server forwards invalidation to all caches. In second approach, an update is propagated. Most caching systems apply these two approaches or dynamically choose between them.

See also[edit]

References[edit]

  1. ^ Mark D. Hill (August 1998). "Multiprocessors Should Support Simple Memory Consistency Models". IEEE Computer 31 (8): pp.28–34. doi:10.1109/2.707614. 
  2. ^ Shaz Qadeer (August 2003). "Verifying Sequential Consistency on Shared-Memory Multiprocessors by Model Checking". IEEE Transactions on Parallel and Distributed Systems 14 (8): pp.730–741. doi:10.1109/TPDS.2003.1225053. 
  3. ^ a b Todd Lipcon (2014-10-25). "Design Patterns for Distributed Non-Relational Databases". Retrieved 2011-03-24. A consistency model determines rules for visibility and apparent order of updates. Example: * Row X is replicated on nodes M and N * Client A writes row X to node N * Some period of time t elapses. * Client B reads row X from node M * Does client B see the write from client A? Consistency is a continuum with tradeoffs 
  4. ^ Lloyd, Wyatt. "Don’t Settle for Eventual:Scalable Causal Consistency for Wide-Area Storage with COPS". Proceedings of the 23rd ACM Symposium on Operating Systems Principles (SOSP’11). 
  5. ^ a b c Goodman, James R (1991). "Cache consistency and sequential consistency". IEEE Scalable Coherent Interface (SCI) Working Group. 
  6. ^ a b c d Steinke, Robert C., and Gary J. Nutt (2004). "A unified theory of shared memory consistency.". Journal of the ACM (JACM) 51 (5): pp.800–849. doi:10.1145/1017460.1017464. 
  7. ^ a b Hutto, Phillip W., and Mustaque Ahamad (1990). "Slow memory: Weakening consistency to enhance concurrency in distributed shared memories.". IEEE: pp.302–309. doi:10.1109/ICDCS.1990.89297. 
  8. ^ Singhal, Mukesh, and Niranjan G. Shivaratri (1994). "Advanced concepts in operating systems.". McGraw-Hill, Inc. 
  9. ^ a b c Mankin, Jenny (2007). "CSG280: Parallel Computing Memory Consistency Models: A Survey in Past and Present Research". 
  10. ^ a b Franklin, Michael J., Michael J. Carey, and Miron Livny (Sep 1997). "Transactional client-server cache consistency: alternatives and performance". ACM Transactions on Database Systems (TODS) 22 (3): pp.315–363. doi:10.1145/261124.261125. 
  11. ^ a b c d e f g h i j k l m n o p q r s t u v w x y z Tanenbaum, Andrew, and Maarten Van Steen (2007). "Distributed systems". Pearson Prentice Hall. 
  12. ^ a b Lamport, Leslie (Sep 1979). "How to make a multiprocessor computer that correctly executes multiprocess programs.". Computers, IEEE Transactions C–28 (9): pp.690–691. doi:10.1109/TC.1979.1675439. 
  13. ^ Herlihy, Maurice P., and Jeannette M. Wing (July 1990). ""Linearizability: A correctness condition for concurrent objects." ACM Transactions on Programming Languages and Systems". ACM Transactions on Programming Languages and Systems (TOPLAS) 12 (3): pp.463–492. doi:10.1145/78969.78972. 
  14. ^ a b c d Yu, Haifeng, and Amin Vahdat (2000). "Design and evaluation of a continuous consistency model for replicated services.". Proceedings of the 4th conference on Symposium on Operating System Design & Implementation 4: pp. 21–21. 

Further reading[edit]

External links[edit]