Data replication is a vital feature in distributed system, but brings in an inevitable price to be paid: consistency maintenance. The 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 reading, writing, or updating memory will be predictable.
In Chinese, “consistency” often mixes up with “consensus” because of their similar translations. The consensus problem requires agreement among a number of processes for a single data value. Some of the processes may fail or be unreliable in other ways, so consensus protocols must be fault tolerant or resilient.
This post focus on consistency only, enumerating various common types of consistency models and illuminating some consistency protocols.
An overview of distributed system lists here for a whole picture, in which we know what a role consistency plays.
Example
Take replication for example, several processors read data from different nodes for high performance.
Assume that the following case occurs:
- The row X is replicated on nodes M and N
- The client A writes row X to node M
- After a period of time t, client B reads row X from node N
The consistency model has to determine whether client B sees the write from client A or not.
Types
Two methods are introduced to define and categorize consistency models:
- issue: Issue method describes the restrictions that define how a process can issue operations.
- view. View method defines the order of operations visible to processes.
For example, a consistency model can define that a process is not allowed to issue an operation until all previously issued operations are completed.
Different consistency models enforce different conditions. One consistency model can be considered stronger than another if it requires all conditions of that model and more. In other words, a model with fewer constraints is considered a weaker consistency model.
Strict Consistency
Strict consistency, the strongest model, satisfies the normal expectation: any read on a data item X returns a value corresponding to the result of the most recent write on X. In other words, a write to a variable by any processor needs to be seen instantaneously by all processors.
In the above diagrams,
- a) A strictly consistent store
- b) A store that is non-strict consistent
The strict model need time constraint, which is hardly implemented without a global clock. Absolute time can be physically impossible because it takes time to propagate the copy information.
Sequential Consistency
The sequential consistency model is a weaker memory model than strict consistency meaning A write to a variable does not have to be seen instantaneously. 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.
Sequential consistency can produce non-deterministic results. This is because the sequence of sequential operations between processors can be different during different runs of the program. All memory operations need to happen in the program order.
Linearizability can be defined as sequential consistency with the real-time constraint.
Causal Consistency
Causal consistency is a weakening model of sequential consistency by categorizing events into those causally related and those that are not. It defines that only write operations that are causally related need to be seen in the same order by all processes. Concurrent writes may be seen in a different order on different machines.
A sequence is allowed with a causally-consistent store, but not with sequentially or strictly consistent store.
Eventual Consistency
An eventual consistency is a weak consistency model in the system with the lack of simultaneous updates. It defines that if no update takes a very long time, all replicas eventually become consistent.
The most popular system that implements eventual consistency is DNS (Domain Name System). Updates to a name are distributed according to a configured pattern and in combination with time-controlled caches; eventually, all clients will see the update.
Monotonic Reads Consistency
If a process has seen a particular value for the object, any subsequent accesses will never return any previous values.
Monotonic Writes Consistency
In this case the system guarantees to serialize the writes by the same process. Systems that do not guarantee this level of consistency are notoriously hard to program.
Read-your-writes Consistency
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.
Writes-follow-reads Consistency
In Writes-follow-reads consistency, updates are propagated after performing the previous read operations. 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.
FIFO Consistency
In FIFO consistency, writes done by a single process are seen by all other processes in the order in which whey were issued, but writes from different processes may be seen in a different order by different processes.
Consistency Protocols
Consistency protocol is the implementation of a consistency model. Some main approaches include:
- primary-based protocols (remote write, local write)
- replicated-write protocols (active replication, quorum based)
Primary-based Protocols
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
In the primary-backup protocol, the simplest primary-based protocol, write operations are routed to a single server and read operations can be performed locally.
Local-write Protocols
In 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.
Replicated-write Protocols
Unlike the primary-based protocol, all updates are carried out to all replicas in Replicated-write protocols.
Active Replication
In active replication, 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.
In order to make all the servers receive the same sequence of operations, an atomic broadcast protocol must be used. An atomic broadcast protocol guarantees that either all the servers receive a message or none, plus that they all receive messages in the same order.
Quorum-based Protocols
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 more than N/2 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/2+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.
Reference