Spectrum of Consistency Models

What is consistency?

In distributed systems, consistency may mean many things. One is that each replica node has the same view of data at a given point in time. The other is that each read request gets the value of the recent write. These are not the only definitions of consistency, since there are many forms of consistency. Normally, consistency models provide us with abstractions to reason about the correctness of a distributed system doing concurrent data reads, writes, and mutations.

If we have to design or build an application in which we need a third-party storage system like S3 or Cassandra, we can look into the consistency guarantees provided by S3 to decide whether to use it or not. Let’s explore different types of consistency.

The two ends of the consistency spectrum are:

• Strongest consistency
• Weakest consistency

There are consistency models that lie between these two ends, some of which are shown in the following illustration:

This is a spectrum of consistency models. Consistency guarantees get stronger as we move to the right

There is a difference between consistency in ACID properties and consistency in the CAP theorem.

Database rules are at the heart of ACID consistency. If a schema specifies that a value must be unique, a consistent system will ensure that the value is unique throughout all actions. If a foreign key indicates that deleting one row will also delete associated rows, a consistent system ensures that the state can’t contain related rows once the base row has been destroyed.

CAP consistency guarantees that, in a distributed system, every replica of the same logical value has the same precise value at all times. It’s worth noting that this is a logical rather than a physical guarantee. Due to the speed of light, replicating numbers throughout a cluster may take some time. By preventing clients from accessing different values at separate nodes, the cluster can nevertheless give a logical picture.

在分布式系统中，一致性可能意味着许多不同的概念。其中一种是一致性指的是在某一时刻，每个副本节点都具有相同的数据视图。另一种是一致性指的是每次读取请求都能获得最近写入的值。这些并不是一致性的唯一定义，因为存在多种一致性模型。通常，一致性模型 为我们提供了一种抽象方法，使我们能够推理分布式系统在并发数据读取、写入和修改时的正确性。

如果我们要设计或构建一个需要使用第三方存储系统（如 S3 或 Cassandra）的应用程序，我们可以研究 S3 提供的一致性保证，以决定是否使用它。接下来，我们探讨不同类型的一致性。

一致性模型的两个极端是：

• 最强一致性
• 最弱一致性

在这两个极端之间，还有许多不同的一致性模型，部分模型如下图所示：

在 ACID 属性 中的一致性，与 CAP 定理 中的一致性有所不同。

ACID 一致性 本质上是数据库规则的核心。如果数据库模式规定某个值必须是唯一的，那么一个一致的系统会确保该值在所有操作中始终保持唯一。如果外键要求删除某一行数据时，同时删除相关联的行，那么一致的系统会确保当基准行被删除后，关联的行不会仍然存在于系统状态中。

CAP 一致性 保证在分布式系统中，相同逻辑值的所有副本在任何时间点都具有完全相同的值。值得注意的是，这是一种逻辑上的保证，而不是物理上的保证。由于光速的限制，在整个集群中复制数据可能需要一定的时间。然而，通过防止客户端在不同节点上访问不同的值，集群仍然能够提供一个逻辑上的一致视图。

Eventual consistency

Eventual consistency is the weakest consistency model. The applications that don’t have strict ordering requirements and don’t require reads to return the latest write choose this model. Eventual consistency ensures that all the replicas converge on a final value after a finite time and when no more writes are coming in. If new writes keep coming, replicas of an eventually consistent system might never reach the same state. Until the replicas converge, different replicas can return different values.

Eventual consistency ensures high availability.

Initially, the value of x is 2

At time T1, Alice sends a write request to update the value of x to 10

The system saves the updated value of x.

At time T2, Alice and Bob read the value of x

The system returns the same value to both read requests, but the value is old.

At time T3, system reaches the stable state and returns the latest value to both read requests

Example

The domain name system is a highly available system that enables name lookups to a hundred million devices across the Internet. It uses an eventual consistency model and doesn’t necessarily reflect the latest values.

Note: Cassandra is a highly available NoSQL database that provides eventual consistency.

最终一致性（Eventual Consistency） 是最弱的一致性模型。对于不具有严格顺序要求且不需要读取返回最新写入值的应用程序来说，这种模型是一个合适的选择。最终一致性保证，在没有新的写入操作发生后，所有副本会在有限时间内收敛到最终值。如果新的写入操作不断发生，那么在一个最终一致性的系统中，各个副本可能永远不会达到相同的状态。在副本收敛之前，不同的副本可能会返回不同的值。

最终一致性可以保证高可用性。

示例

域名系统（DNS） 是一个高可用的系统，它支持全球数亿台设备进行名称解析。DNS 采用最终一致性模型，因此查询的结果不一定能反映最新的值。

注意：Cassandra 是一个高可用的 NoSQL 数据库，它提供最终一致性。

Causal consistency

Causal consistency works by categorizing operations into dependent and independent operations. Dependent operations are also called causally-related operations. Causal consistency preserves the order of the causally-related operations.

In the following illustration, process P1 writes a value a at location x. For P2 to write the value b at location y, it first needs to calculate b. Since b=x+5, the read operation on x should be performed before writing b on location y. That’s why read(x)a and write(y)b are causally related.

This model doesn’t ensure ordering for the operations that are not causally related. These operations can be seen in different possible orders.

Causal consistency is weaker overall, but stronger than the eventual consistency model. It’s used to prevent non-intuitive behaviors.

Example

The causal consistency model is used in a commenting system. For example, for the replies to a comment on a Facebook post, we want to display comments after the comment it replies to. This is because there is a cause-and-effect relationship between a comment and its replies.

Note: There are many consistency models other than the four discussed in this lesson, and there is still room for new consistency models. Researchers have developed new consistency models. For example, Wyatt Lloyd, et al., proposed the causal+consistency model to speed up some specific types of transactions.

因果一致性（Causal Consistency） 通过将操作分为相关（依赖）操作和独立操作来工作。相关操作也称为因果相关操作。因果一致性保证了因果相关操作的顺序。

在下图中，进程 P1 在位置 x 处写入值 a。进程 P2 在位置 y 处写入值 b 之前，需要先计算 b。由于 b = x + 5，因此在位置 y 处写入 b 之前，必须先读取 x 的值。这意味着 read(x)a 和 write(y)b 之间存在因果关系

该模型不保证无因果关系操作的顺序。这些操作可能以不同的顺序被看到。

因果一致性整体上比最终一致性更强，但仍然比强一致性弱。它用于防止非直观行为的发生。

示例

因果一致性模型常用于评论系统。例如，在 Facebook 帖子的评论区，我们希望回复的评论出现在它所回复的评论之后。这是因为评论与其回复之间存在因果关系。

注意： 除了本课讨论的四种一致性模型之外，还有许多其他的一致性模型，并且仍然有新的模型被提出。例如，Wyatt Lloyd 等人提出了 Causal+Consistency 模型，以加速某些特定类型的事务。

Sequential consistency

Sequential consistency is stronger than the causal consistency model. It preserves the ordering specified by each client’s program. However, sequential consistency doesn’t ensure that the writes are visible instantaneously or in the same order as they occurred according to some global clock.

Example

In social networking applications, we usually don’t care about the order in which some of our friends’ posts appear. However, we still anticipate a single friend’s posts to appear in the correct order in which they were created). Similarly, we expect our friends’ comments in a post to display in the order that they were submitted. The sequential consistency model captures all of these qualities.

顺序一致性（Sequential Consistency） 比因果一致性更强。它保证每个客户端程序指定的操作顺序被保留。然而，顺序一致性并不保证写入操作会立即可见，也不确保所有写入按照全局时钟的顺序可见。

示例

在社交网络应用中，我们通常不会特别在意朋友们的动态在时间线上出现的顺序。然而，我们仍然期望同一个朋友的动态按其创建顺序展示。类似地，我们也希望在某个帖子下，朋友们的评论按照提交的顺序显示。顺序一致性模型正好满足这些需求。

Strict consistency aka linearizability

A strict consistency or linearizability is the strongest consistency model. This model ensures that a read request from any replicas will get the latest write value. Once the client receives the acknowledgment that the write operation has been performed, other clients can read that value.

Linearizability is challenging to achieve in a distributed system. Some of the reasons for such challenges are variable network delays and failures. The following slides show depicts how variable network delays make it possible for different parties to see different values.

严格一致性（Strict Consistency） 或 线性一致性（Linearizability） 是最强的一致性模型。该模型确保来自任何副本的读取请求都能获取到最新的写入值。一旦客户端收到写入操作完成的确认，其他客户端随后读取时一定能够获取到该值。

在分布式系统中，实现线性一致性极具挑战性。其中一些挑战包括网络延迟和故障的不确定性。下图展示了网络延迟的变化如何导致不同的客户端可能看到不同的值。

There are three users of a system consisting of three nodes (replicas), and each node initially has a value of x that equals 2

Alice requests a write operation to change the value of x to 10

Node A performs the write operation on x and returns an acknowledgment back to Alice

Node A forwards the write operation to the other nodes in the system

Node B receives the write operation and changes the value of x to 10

John requests a read operation that is performed on Node B

Node B has the latest value of x and returns it to John

After John, Bob requests a read operation on x, which is performed on Node C

Node C has not yet received the write operation, so it returns the old value of x = 2 to Bob

Usually, synchronous replication is one of the ingredients for achieving strong consistency, though it in itself is not sufficient. We might need consensus algorithms such as Paxos and Raft to achieve strong consistency.

Linearizability affects the system’s availability, which is why it’s not always used. Applications with strong consistency requirements use techniques like quorum-based replication to increase the system’s availability.

Example

Updating an account’s password requires strict consistency. For example, if we suspect suspicious activity on our bank account, we immediately change our password so that no unauthorized users can access our account. If it were possible to access our account using an old password due to a lack of strict consistency, then changing passwords would be a useless security strategy.

Note: Google’s Spanner database claims to be linearizable for many of its operations.

通常，同步复制 是实现强一致性的一个重要组成部分，尽管它本身并不足以保证强一致性。我们可能还需要使用一致性算法（如 Paxos 和 Raft）来实现强一致性。

线性一致性会影响系统的可用性，因此并非所有应用都会采用它。对于有强一致性要求的应用，通常会使用 基于法定人数（Quorum-Based Replication） 的技术来提高系统的可用性。

示例

更新账户密码 需要严格一致性。例如，如果我们怀疑银行账户存在可疑活动，我们会立即更改密码，以防止未经授权的用户访问我们的账户。如果由于缺乏严格一致性，旧密码仍然可以用于访问账户，那么更改密码将毫无意义，安全策略也会失效。

注意： Google 的 Spanner 数据库声称在其许多操作中实现了线性一致性。

Summary

Linearizable services appear to carry out transactions/operations in sequential, real-time order. They make it easier to create suitable applications on top of them by limiting the number of values that services can return to application processes.

Linearizable services have worse performance rates than services with weaker consistency in exchange for their strong assurances. Think about a read in a key-value store that returns the value written by a concurrent write. The read imposes no limits on future reads if the key-value store is weakly consistent.

Application programmers have to compromise performance and availability if they use services with strong consistency models. The models may break the invariants of applications built on top of them in exchange for increased performance.

总结

线性一致性的服务 表现得像是按顺序执行 事务或操作，并且保证这些操作以实时顺序 进行。这种一致性使得开发者在其之上构建应用程序更加容易，因为它限制了服务返回给应用程序进程的可能值。

然而，与提供更弱一致性的服务相比，线性一致性会导致更差的性能。例如，在一个弱一致性 的键值存储中，读取可能返回并发写入的值，但不会对未来的读取施加限制。因此，弱一致性的系统通常具有更高的吞吐量和可用性。

应用程序开发人员在选择强一致性模型时，需要在性能 和 可用性 之间做出权衡。尽管强一致性模型提供了严格的保证，但它可能会降低系统的性能，并破坏应用程序的某些高性能需求。