An important problem in distributed systems is data replication, which is generally used to enhance system availability or improve performance. One of the main difficulties in data replication is to keep the consistency of each copy. This article first discusses why consistency models are so important in data replication scenarios, then discusses the implications of consistency models, and finally analyzes common consistency models.

Why do we need a consistency model

Data replication has two main purposes: availability and performance. First, data replication improves system availability. In the case of multiple replicas, if one replica is unavailable, the system switches to another replica and recovers. The common MySQL master/slave synchronization scheme is a typical example. Data replication, on the other hand, can provide system performance. Data replication is an important tool when distributed systems need to scale in number of servers and geographic areas. With multiple copies of data, requests can be split; When services are provided in multiple regions, the proximity principle can also improve the efficiency of client access to data. The commonly used CDN technology is a typical example. But data replication comes at a cost. Data replication brings about the problem of data consistency across multiple copies. After the data of one copy is updated, the other copies must be synchronized. Otherwise, inconsistent data may cause service problems. Therefore, when and how all replicas are modified with each update determines the size of the replication cost. Global synchronization is actually incompatible with performance, and in order to improve performance, a relaxed approach to consistency is often adopted. Therefore, we need a consistency model to understand and reason about the issues and basic assumptions that need to be considered for data replication in distributed systems.

What is a consistency model

First we define the terms of the consistency model:

  1. Data storage: Distributed shared databases, distributed file systems, etc.
  2. Read and write operations: The operations that change data are called write operations (including adding, modifying, and deleting data). Other operations are called read operations.

The following is the definition of a consistency model: A consistency model is essentially a contract between a process and a data store: if the process follows certain rules, then the data read and write operations of the process are expected.

The above definition may be abstract, but let’s use the common strong-consistency model: in the linear consistency model, a process reads an item and expects the data store to return the result of the last write. This is easy to implement in a stand-alone system, in MySQL as long as the use of lock read way to ensure that the data after the last write operation results. However, in distributed systems, because there is no global clock, it is very difficult to define exactly which write operation is the last write operation, so a series of consistency models have been developed. Each model effectively limits the value that should be returned when a read is performed on a data item. For example, suppose that the record value X has copies on both nodes M and N. When client A modifies the value of X on copy M, client B reads the value of X from N some time later. At this point, the consistency model determines whether client B can read the value written by A.

Consistency models can be divided into two categories: the consistency model that can ensure that all processes keep the same order of reading and writing data is called strong consistency model, while the consistency model that cannot be guaranteed is called weak consistency model.

Strong consistency model

Linearizable Consistency

Linear Consistency, also known as Strict Consistency or Atomic Consistency, has the following conditions:

  1. Each read can read the data that was written last time.
  2. All processes see operations in the same order as on the global clock.

Linear consistency is a consistency model with the highest requirement for consistency, which is impossible to achieve with existing technology. Because it requires all operations to be synchronized in real time, it is impossible to achieve globally perfect clock consistency in distributed systems with existing technologies. First of all, there must be a delay in communication. Once there is a delay, the synchronization of clocks cannot be consistent. Of course, new technologies can do this in the future, but at present linear consistency is not possible.

Sequential Consistency

Sequential consistency was first proposed by Lamport (1979) in the solution of shared memory in multiprocessor systems. Refer to my previous article, distributed Systems: Lamport Logical Clocks. Its conditions are:

  1. Every read and write operation is done in a particular order.
  2. All processes see the same order of read and write operations.

Let’s start by analyzing the similarities between linear consistency and sequential consistency. They ensure that all processes read and write data in the same order. The implementation of linear consistency is very simple. If the global clock (which can be simply understood as the physical clock) is used as a reference frame, and all processes distinguish the sequence of events according to the timestamp of the global clock, then all processes must see the same sequence of data read and write operations, because their reference frame is the same. Sequential consistency uses the logical clock as the global clock in a distributed system, so that all processes have a unified reference frame to sort read and write operations, so that all processes see the same order of data read and write operations.

So what’s the difference between linear consistency and sequential consistency? According to the above analysis, sequential consistency although the logical clock ensures that all processes maintain the same read and write order, the order of these read and write operations is not necessarily the same as the order in which they actually occur. Linear consistency is strictly guaranteed to be in the order in which it actually happens.

Weak consistency model

Causal Consistency

Causal consistency is a weakened sequential consistency model because it distinguishes potentially causal events from non-causal events. So what is causation? If event B is caused by or affected by event A, then the two events are causally related. For an example of a distributed database, if process P1 writes to item X, and process P2 first reads x and then writes to Y, then there is a potential causal relationship between reads to X and writes to Y. Because the y calculation may depend on P2 reading the value of x (that is, P1 writing the value). On the other hand, if two processes write to two different data items at the same time, the two events have no causal relationship. Operations without causality are called concurrent operations. This is a brief statement, but for further analysis, see my previous article distributed Systems: Vector Clocks. Conditions for causal consistency include:

  1. All processes must see causal read and write operations in the same order.
  2. Different processes can see concurrent read and write operations in different order.

Let’s examine why causal consistency is a weakened sequential consistency model. Sequential consistency does not guarantee that events occur in the same order as they actually occur, but it does guarantee that all processes see read and write operations in the same order. Causal consistency further weakens the constraint on the order of read and write operations in sequential consistency. Only read and write operations with causal relationship are guaranteed to be orderly, while read and write operations without causal relationship (concurrent events) are not guaranteed. In other words, if there is no causal data operation, different processes may see different values, but if there is causal data operation, different processes will see the same values.

Eventual Consistency

Final consistency is a more weakened consistency model. Causal consistency at least guarantees that the values read by different processes of the data with causal relationship are the same, while final consistency only guarantees that the data of all copies will be consistent at a certain time. In a sense, final consistency guarantees that at some point the data will eventually be consistent is like saying, “People will die someday.” In fact, we are more concerned with:

  1. How long is “eventually”? In general, the actual system needs to be able to guarantee a lower bound time range.
  2. What is the strategy for updating data between multiple replicas? The data may be updated several times during a period of time. Which data shall prevail? A common data update strategy is to use the latest timestamp data.

Because the final consistency has low requirements on data consistency, it is often used in scenarios with high performance requirements.

Client-centric Consistency

Front we discuss the consistency of the model is aimed at how to achieve consistency between multiple copies of data storage, to consider such a scenario: the eventual consistency model, if the client within the time window in the data are not synchronized access different copies of the same data, there will be read the same data have different values. To solve this problem, a client-centric consistency model has been proposed. Client-centric consistency provides a consistency guarantee for a single client and its access to the data store, but does not provide any consistency guarantee for concurrent access from different clients. For example: client A reads the latest value of x on copy M as 1. Suppose copy M dies, client A connects to copy N, and the value of X on copy N is the old version 0. The consistency model guarantees that client A reads the value of X on copy N as 1, not the old version 0. One possible solution is to mark the version of data X. At the same time, client A will cache the value of X and compare the version to identify the old data and ensure that the client will not read the old value.

Client-centric consistency consists of four sub-models:

  1. Monotonic- Read Consistency: If a process reads the value of a data item X, all subsequent reads of X will either read the first value or read the updated value. That is, ensure that the client does not read old values.
  2. Monotonic-write Consistency: A process’s write to data item X must be completed before the process performs any subsequent writes to x. That is, ensure that client write operations are serial.
  3. Read-your-index Consistency: The result of one write operation on data item X by a process will always be seen by subsequent Read operations on x by the same process. That is, ensure that the client can read the latest value written by itself.
  4. Write read Consistency (writing-follow-reads Consistency) : The write operation followed by the read operation on data item X performed by the same process with the same or newer value as the read operation on data item X. That is, ensure that a client’s write operation on a data item is based on the latest value read by the client.

conclusion

Data replication leads to consistency problems, and in order to keep the consistency of the copy can seriously affect performance, the only solution is to relax consistency requirements. The consistency model enables us to understand and reason about the problems and basic assumptions that need to be considered in data replication in distributed systems, making it easy to make trade-offs based on specific business scenarios. Each model effectively limits the value that should be returned when a degree operation is performed on a data item. In general, the less restrictive the model, the easier it is to apply, but the weaker the guarantee of consistency.

The resources

Principles and Paradigms of Distributed Systems

Distributed systems for fun and profit

Consistency_model