不要满足于最终一致性：使用 COPS 实现广域存储的可扩展因果一致性

摘要

支持复杂在线应用（如社交网络）的地理复制分布式数据存储必须提供一种 "始终在线" 的体验，即操作始终以低延迟完成。如今的系统通常会牺牲强一致性来实现这些目标，向其客户端暴露不一致性，并需要复杂的应用逻辑。在本文中，我们识别并定义了一种一致性模型 —— 具有收敛冲突处理的因果一致性，即 causal+，这是在这些约束下所能实现的最强一致性。

我们展示了 COPS 的设计与实现，COPS 是一个键值存储，它在广域范围内提供这种一致性模型。COPS 的一个关键贡献是其可扩展性，它可以在整个集群中存储的键之间强制执行因果依赖关系，而不像以前的系统那样只在单个服务器上执行。COPS 的核心方法是在暴露写入之前，跟踪并明确检查本地集群中键之间的因果依赖关系是否得到满足。此外，在 COPS-GT 中，我们引入了获取事务，以便在不锁定或阻塞的情况下获得多个键的一致视图。我们的评估表明，COPS 在不到一毫秒的时间内完成操作，在每个集群使用一个服务器时提供与以前系统类似的吞吐量，并且随着我们增加每个集群中的服务器数量而具有良好的扩展性。它还表明，对于常见工作负载，COPS-GT 在延迟、吞吐量和扩展性方面与 COPS 类似。

1. 引言

分布式数据存储是现代互联网服务的基础构建块。理想情况下，这些数据存储应该具备以下特性：强一致性（strong consistency）、对读写操作始终可用（always available for reads and writes）、以及在网络分区（network partitions）期间能够继续运行。然而，CAP 定理明确证明，不可能创建一个同时满足这三种特性的系统。

因此，现代 Web 服务普遍选择在牺牲强一致性的前提下，优先实现 可用性（availability）和 分区容忍性（partition tolerance）。考虑到这种选择还能使系统提供低延迟的客户端操作和高可扩展性，这一取舍并不令人意外。此外，许多早期的大规模互联网服务（例如专注于 Web 搜索的系统）通常对强一致性没有太高要求。然而，随着互动性更强的服务（例如社交网络应用）的兴起，这种情况正在发生变化。

我们将具有以下四个特性的系统称为 ALPS 系统:

• Availability(即可用性)
• low Latency(低延迟)
• Partition-tolerance(分区容忍性)
• high Scalability(高可扩展性)

由于 ALPS 系统必须牺牲强一致性（例如线性一致性），我们希望在这种约束下实现最强的可用一致性模型。更强的一致性是可取的，因为它使程序员更容易理解和使用系统。在本文中，我们考虑了具有收敛冲突处理的因果一致性，我们将其称为 causal+ 一致性。许多之前被认为实现了较弱因果一致性的系统实际上实现了更有用的 causal+ 一致性，但没有一个系统以可扩展的方式实现它。

Causal+ 一致性中的因果一致性组件确保数据存储遵守操作之间的因果依赖关系。例如，假设一个用户将图片上传到网站，图片被保存后，又向该用户的相册中添加了一条指向该图片的引用。这种引用"依赖于"图片的保存。在 causal+ 一致性下，这些依赖关系始终能够得到满足。程序员不需要处理类似于弱一致性系统（如最终一致性）中可能遇到的情况，即可能获取到图片的引用但无法获取图片本身。

收敛冲突处理组件确保副本不会永久分歧，并且对同一键的冲突更新在所有站点以相同方式处理。当结合因果一致性时，该属性还确保客户端只会看到不断更新的键版本。相比之下，最终一致性系统可能会暴露乱序版本。通过将因果一致性与收敛冲突处理相结合，causal+ 一致性确保了客户端能够看到一个因果正确、无冲突且始终前进的数据存储。

我们的 COPS 系统（Order-Preserving Servers 的集群）提供 因果+一致性，旨在支持复杂的在线应用。这些应用托管在少量的大规模数据中心中，每个数据中心由前端服务器（COPS 的客户端）和后端键值数据存储组成。COPS 在本地数据中心以线性化的方式执行所有的 put 和 get 操作，然后以 因果+一致性 的顺序在后台跨数据中心复制数据。

我们详细介绍了 COPS 系统的两个版本。普通版本 COPS 提供了各数据项之间的可扩展 因果+一致性，即使它们的因果依赖分布在本地数据中心的许多不同机器上。这种一致性特性代价很低：COPS 的性能和开销与之前的系统（例如基于日志交换的系统【10, 41】）相似，同时提供了更大的可扩展性。

我们还介绍了系统的扩展版本 COPS-GT，它提供了能够使客户端获取多个键的 一致视图 的 get 事务。即使在完全线性化的系统中，也需要 get 事务来获得多个键的一致视图。我们的 get 事务无需锁定、是非阻塞的，并且最多需要两轮并行的跨数据中心内部请求。据我们所知，COPS-GT 是第一个在 ALPS 系统中实现非阻塞可扩展 get 事务的系统。这些事务确实有一定的成本：与普通版本的 COPS 相比，COPS-GT 在某些负载（例如写密集型）中效率较低，并且对长时间的网络分区和数据中心故障的鲁棒性较差。

ALPS 系统的可扩展性要求是 COPS 和之前因果+一致性系统之间最大的区别。之前的系统要求所有数据必须存储在单一机器上，或者所有可能被一起访问的数据必须存储在同一台机器上。相比之下，COPS 中存储的数据可以分布在任意大小的数据中心中，且依赖关系（或 get 事务）可以跨多个服务器。据我们所知，COPS 是第一个实现了可扩展 因果+一致性（进而实现因果一致性）的系统。

本文的主要贡献包括：

• 我们明确指出了分布式数据存储的四个重要特性，并用它们来定义 ALPS 系统。
• 我们命名并正式定义了 因果+一致性。
• 我们展示了设计与实现 COPS 的方法，该系统高效实现了 因果+一致性 模型。
• 我们在 COPS-GT 中提出了一种非阻塞、无锁的 get 事务算法，该算法可以在最多两轮本地操作中为客户端提供多个键的一致视图。
• 我们通过评估表明，COPS 在所有测试负载下都具有低延迟、高吞吐量和良好的可扩展性；而 COPS-GT 在常见负载下具有类似的性能特性。

2. ALPS 系统与权衡

我们关注能够支持当今最大互联网服务的基础设施。与传统的集中于小规模局域网操作的分布式存储系统相比，这些服务通常具有跨广域部署的特点，分布范围从几个到几十个数据中心，如图 1 所示。每个数据中心包含一组应用层客户端，以及一个后端数据存储，这些客户端从中读取和写入数据。对于许多应用（包括本文讨论的场景），在一个数据中心写入的数据会被复制到其他数据中心。

通常，这些客户端实际上是代表远程浏览器运行代码的网页服务器（web server）。尽管本文从应用客户端（即网页服务器）的视角讨论一致性，但如果浏览器通过单个数据中心访问服务，正如我们预期的那样，它也将享有类似的一致性保证。

这样的分布式存储系统有多个（有时相互竞争的）目标，包括：可用性、低延迟和分区容错性，以提供"始终在线"的用户体验；可扩展性，以适应不断增长的负载和存储需求；以及足够强的一致性模型，以简化编程并为用户提供符合预期的系统行为。具体来说，这些理想特性包括：

• 1.可用性（Availability）:所有向数据存储发出的操作都能成功完成。没有操作会无限期阻塞或返回表示数据不可用的错误。
• 2.低延迟（Low Latency）:客户端操作能"快速"完成。商业服务级别目标（Service Level Objectives）建议平均性能为几毫秒，而最差情况（即第 99.9 百分位）的性能在几十到几百毫秒之间。
• 3.分区容错性（Partition Tolerance）。即使发生网络分区（例如将亚洲和美国的数据中心分隔开），数据存储仍能继续运行。
• 4.高可扩展性（High Scalability）。数据存储能够线性扩展。向系统增加 𝑁 个资源，其总吞吐量和存储容量相应地增加 𝑂(𝑁)。
• 5.更强的一致性（Stronger Consistency）。理想的存储系统应提供线性化一致性（linearizability），有时也被称为强一致性。这意味着操作在整个系统中似乎在其调用与完成之间的某一瞬间生效。在提供线性化一致性的存储系统中，当一个客户端在一个数据中心完成对某对象的写操作后，所有其他数据中心对同一对象的读操作将反映出该对象的最新状态。线性化一致性简化了编程——分布式系统提供了单一、一致的镜像，用户也能够体验到符合预期的存储行为。较弱的最终一致性模型（eventual consistency）在许多大型分布式系统中较为常见，但它们较难理解：不仅随后的读取可能不会反映最新值，还可能在读取多个对象时返回旧值和新值混杂的不一致结果。

CAP 定理证明了一个共享数据系统如果具备可用性和分区容错性，则无法实现线性化一致性（linearizability）。此外，低延迟（定义为低于跨广域副本之间的最大延迟）也已被证明与线性化一致性和顺序一致性（sequential consistency）不相容。

为了在 ALPS 系统的需求与编程易用性之间取得平衡，我们在下一节中定义了一种中间一致性模型。

3. 因果+一致性

为了定义具有收敛冲突处理的因果一致性（causal+ consistency），我们首先描述其运行的抽象模型。我们将讨论限制在一个键值数据存储（key-value data store）上，具有以下两个基本操作：put(key, val) 和 get(key) = val。这些操作等价于共享内存系统中的写操作和读操作。

值从逻辑副本中存储和检索，每个逻辑副本托管整个键空间。在我们的 COPS 系统中，一个逻辑副本对应于一个本地节点集群。

在该模型中，一个重要的概念是操作之间的潜在因果性（potential causality）。潜在因果性通过以下三条规则定义，用符号 ≺≺ 表示：

1.执行线程（Execution Thread）

如果 a 和 b 是同一执行线程中的两个操作，且操作 𝑎 先于操作 𝑏 发生，则 a -> b。

2.来源关系（Gets From）

如果a 是一个 put 操作，b 是一个 get 操作，并且 b 返回了由 a 写入的值，则 a -> b。

3.传递性（Transitivity）

对于操作a, b 和 c，如果 a -> b 且 b -> c，则 a -> c。

这些规则建立了在同一执行线程内的操作之间的潜在因果性，以及通过数据存储交互的操作之间的潜在因果性。与许多模型一样，我们的模型不允许线程直接通信，而是要求所有通信都通过数据存储进行。

示例

图 2 中的执行示例展示了所有三条规则：

• 执行线程规则：get(y) = 2 -> put(x, 4)。
• 来源关系规则：put(y, 2) -> get(y) = 2。
• 传递性规则：put(y, 2) -> put(x, 4)。

即使某些操作在时间上跟随 put(x, 3) 之后，但没有其他操作依赖它，因为没有读取它写入的值，也没有在同一执行线程中紧接它发生。

图2展示副本中操作之间因果关系的图。图中从 a 到 𝑏 的一条边表示 a≺b，即 b 依赖于 a

3.1 定义

我们将因果+一致性定义为以下两个属性的结合：因果一致性和收敛的冲突处理。在此给出直观定义，正式定义见附录 A。

因果一致性要求，副本中 get 操作返回的值必须与因果关系（->）定义的顺序一致。

换句话说，写入一个值的操作看起来必须发生在所有因果上先于它的操作之后。例如，在图 2 中，必须显得 put(y, 2) 发生在 put(x, 4) 之前，而 put(x, 4) 又发生在 put(z, 5) 之前。

如果客户端 2 先看到了 get(x) = 4，然后又看到 get(x) = 1，则因果一致性会被破坏。

因果一致性不对并发操作排序。如果 $a \not \rightarrow b$ 且$b \not \rightarrow a$, 则 a 和 b 是并发的。这通常可以提高实现效率：两个不相关的 put 操作可以以任意顺序复制，而无需对它们进行串行化处理。然而，如果 a 和 b 都是对同一键的 put 操作，则它们之间存在冲突。

冲突带来两个主要问题：副本可能永久分歧。由于因果一致性未对冲突排序，不同副本可能会永远保留不同的结果。例如，如果a 是 put(x, 1)，b 是 put(x, 2)，因果一致性允许一个副本对 𝑥 永远返回 1，而另一个副本对 𝑥 永远返回 2。

冲突可能表示某些需要特殊处理的异常情况。例如，在购物车应用中，如果两个人同时登录同一账户并添加商品到购物车，期望的结果是购物车 最终包含两件商品。

收敛的冲突处理要求，所有副本以相同的方式处理冲突的 put 操作，使用一个处理函数 h。这个处理函数 h 必须是结合律和交换律的，以确保副本可以按照其接收到的顺序处理冲突的写入，并且处理结果能够收敛。例如，一个副本执行 另一个副本执行 两者结果必须一致。

一种常见的收敛冲突处理方式是最后写入者胜出规则（Last-Writer-Wins, LWW），也称为 Thomas 写规则。该规则将冲突中的某一次写入标记为"更晚发生"，并覆盖更早的写入。另一种常见方法是标记这些冲突，并通过其他方式解决，例如通过用户干预，或通过编程过程。

所有潜在形式的收敛冲突处理都避免了第一个问题（冲突更新可能不断分歧），通过保证副本在交换操作后达到相同的结果。然而，解决第二个问题（应用可能需要特殊处理冲突）则依赖更显式的冲突解决流程。这些显式流程为应用提供了更大的灵活性，但也需要额外的编程复杂性和/或性能开销。

尽管 COPS 系统可以配置为显式检测冲突更新并应用某些应用定义的解决方法，COPS 默认使用最后写入者胜出规则来处理冲突。

3.2 因果+与其他一致性模型

分布式系统文献中定义了几种流行的一致性模型，按照一致性的强度递减排序，包括：

• 线性化一致性（或强一致性），保持全局的实时排序。
• 顺序一致性：确保至少存在全局排序。
• 因果一致性：确保依赖操作之间的部分排序。
• FIFO（PRAM）一致性：只保留执行线程之间的部分排序，而不是线程之间的排序。
• 每个键的顺序一致性：确保每个单独的键的所有操作都具有全局排序。
• 最终一致性：一种通用术语，今天通常表示最终会收敛到某种类型的协议或一致性状态。

我们提出的因果+一致性介于顺序一致性和因果一致性之间，如图3所示。它比顺序一致性弱，但顺序一致性在ALPS系统中是无法实现的。然而，它比因果一致性和每个键的顺序一致性要强，并且对于ALPS系统是可实现的。Mahajan等人也同时定义了一个类似的因果一致性加强版本；有关详细信息，请参见第7节。

为了说明因果+模型的实用性，考虑两个例子。在第一个例子中，假设爱丽丝尝试与鲍勃分享一张照片。爱丽丝上传了照片，然后将照片添加到她的相册中。接着，鲍勃查看爱丽丝的相册，期望看到她的照片。在因果一致性以及因果+一致性下，如果相册中有照片的引用，那么鲍勃必须能够查看到这张照片。而在每个键的顺序一致性和最终一致性下，相册中可能会有指向照片的引用，但该照片实际上可能还没有被写入。

其次，考虑一个例子，Carol 和 Dan 都对某事件的开始时间进行了更新。时间最初设置为晚上9点，Carol 将其更改为晚上8点，而 Dan 同时将其更改为晚上10点。常规的因果一致性可能会导致两个不同的副本永远返回不同的时间，即使它们已经接收到两个更新操作（put operations）。

因果+一致性要求副本以收敛的方式处理这种冲突。如果采用"最后写入者获胜"（Last-Writer-Wins, LWW）策略，那么 Dan 的10点或 Carol 的8点之一会胜出。如果使用更明确的冲突解决策略，则该键可能被标记为冲突状态，随后对该键的查询（get操作）可以同时返回8点和10点，并附带解决冲突的指引。

如果数据存储系统是顺序一致或线性化一致的，仍然可能会对某个键发生两次同时更新。然而，在这些更强的一致性模型中，可以实现互斥算法（例如 Lamport 在最初的顺序一致性论文中提出的算法），通过这些算法可以完全避免冲突的产生。

3.3 COPS中的因果+一致性

在 COPS 系统中，我们使用两个抽象概念——版本和依赖关系——来帮助理解因果+一致性。我们将一个键的不同值称为该键的版本，并用 ${key}_{version}$ 表示。在 COPS 中，版本的分配方式确保如果 ${x}_{i} \rightarrow {y}_{j}$,因果+一致性确保之后它只会返回该版本或因果上的更晚版本（请注意，处理冲突的过程在因果上晚于它所解决的冲突的 put 操作）。因此，COPS 中的每个副本总是返回某个键的非递减版本。我们将这种特性称为因果+一致性的进展性属性（progressing property）。

....

4.COPS 系统设计

COPS 是一个分布式存储系统，旨在实现因果+一致性并具备理想的 ALPS 特性（Availability, Low latency, Partition tolerance, and Scalability）。该系统有两个不同的版本：

• COPS：提供一个因果+一致性的数据存储服务。
• COPS-GT：在 COPS 的基础上扩展了功能，支持获取事务（get transactions）。通过获取事务，客户端可以请求一组键，并由数据存储系统返回对应值的一致快照。

由于需要额外的元数据来保证获取事务的一致性属性，某次部署中必须选择运行 COPS 或 COPS-GT，两者不可同时运行。

4.1 COPS 概述

COPS 是一种键值存储系统，设计用于跨少量数据中心运行，如图 4 所示。每个数据中心都有一个本地的 COPS 集群，并持有存储数据的完整副本。

COPS 的客户端是使用 COPS 客户端库直接调用 COPS 键值存储的应用程序。客户端只与运行在同一数据中心内的本地 COPS 集群通信。

每个本地 COPS 集群被设置为一个线性化一致性（强一致性）的键值存储系统。线性化系统可以通过将键空间划分为 N 个线性化分区（每个分区可以位于单个节点或单个节点链上）并让客户端独立访问每个分区来实现可扩展性。线性化的一致性组合性确保了整个系统仍然保持线性化一致性。

在本地环境中，线性化一致性是可以接受的，因为我们预计集群内部的延迟极低且不会发生分区——特别是在现代数据中心网络中，冗余路径的趋势使得集群内部的通信更加可靠。

另一方面，COPS 集群之间的复制是异步进行的，以确保客户端操作的低延迟和在外部分区情况下的高可用性。

4.2 COPS 键值存储

与传统的⟨key,value⟩ 元组存储不同，COPS 必须跟踪写入值的版本；在 COPS-GT 中，还需要跟踪其依赖关系。在 COPS 中，系统为每个键存储最近的版本号和对应的值。在 COPS-GT 中，系统将每个键映射到一个版本条目列表，每个条目由⟨version,value,deps⟩ 组成。

deps 字段是一个依赖列表，包含零个或多个依赖关系；每个依赖项由⟨key,version⟩对表示。

每个 COPS 集群维护自己的一份键值存储副本。为了提高可扩展性，我们的实现使用一致性哈希将键空间划分到集群的不同节点上，不过也可以使用其他技术（例如基于目录的方法）。

为了实现容错，每个键会通过链式复制到少量节点上。在集群内，get 和 put 操作是线性化一致的。当操作在本地集群中执行完毕后，会立即返回给客户端库；而集群之间的操作是异步进行的。

4.3 客户端库和接口

COPS 客户端库提供了一个简单直观的编程接口。图 5 展示了该接口在照片上传场景中的使用方式。客户端 API 包含以下四种操作：

• 1.ctx_id createContext() 创建上下文：创建一个新的上下文，返回上下文的唯一标识符 ctx_id。

• 2.bool deleteContext(ctx_id) 删除上下文：删除指定的上下文 ctx_id，返回操作是否成功的布尔值。

• 3.bool put(key, value, ctx_id) 写入数据：将键值对 (key, value) 存入指定的上下文 ctx_id，返回操作是否成功的布尔值。

• 4.value get(key, ctx_id) （用于 COPS） 读取数据：从指定的上下文 ctx_id 中获取与键 key 对应的值 value。

  ⟨values⟩ get_trans(⟨keys⟩, ctx_id) （用于 COPS-GT） 批量事务读取：从指定的上下文 ctx_id 中以事务方式获取键集合 ⟨keys⟩ 对应的值集合 ⟨values⟩。

图5：以下是使用 COPS 编程接口处理 3.2 节照片上传场景的伪代码片段。当使用 COPS-GT 时，每个 get 操作会替换为对单个键执行的 get_trans 操作。

# Alice's Photo Upload
ctx_id = createContext() // Alice logs in
put(Photo, "Portuguese Coast", ctx_id)
put(Album, "add &Photo", ctx_id)
deleteContext(ctx_id) // Alice logs out

# Bob's Photo View
ctx_id = createContext() // Bob logs in
"&Photo" <- get(Album, ctx_id)
"Portuguese Coast" <- get(Photo, ctx_id)
deleteContext(ctx_id) // Bob logs out

这些操作为客户端与 COPS 系统（或其扩展版本 COPS-GT）之间的交互提供了基本接口，支持单点操作和事务操作。

客户端 API 与传统的键值接口在两个方面有所不同：

COPS-GT 提供了 get_trans 操作，允许在一次调用中返回多个键值对的一致性视图。这一特性支持事务性操作，确保读取到的数据在逻辑上保持一致。

所有函数都接收一个上下文参数，该参数由库在内部使用，用于跟踪每个客户端操作的因果依赖关系。上下文定义了因果+（causal+）的执行线程。一个进程中可能包含多个独立的执行线程（例如，一个 Web 服务器可以同时处理数千个独立的连接）。通过区分不同的执行线程，COPS 避免了由于线程间混合操作而导致的虚假依赖。

COPS-GT 客户端库 ： 在 COPS-GT 中，客户端库将客户端的上下文存储在一个包含以下条目的表中：⟨key, version, deps⟩。客户端通过 API 中的上下文 ID (ctx_id) 引用其上下文。

• 当客户端从数据存储中获取一个键时，库会将该键及其因果依赖关系添加到上下文中。
• 当客户端存储一个值时，库会将该存储操作的依赖项设置为当前上下文中每个键的最新版本。

成功写入数据存储的操作会返回为写入值分配的版本号 v。随后，客户端库会将新的条目 ⟨key, v, D⟩ 添加到上下文中。

因此，上下文包含了客户端会话中之前读取或写入的所有值，以及这些值的所有依赖的依赖关系，如图 6 所示。这引发了两个关于因果图潜在大小的担忧：

• 存储这些依赖关系所需的状态，包括客户端库和数据存储中的状态需求。
• 在集群之间复制写入操作时可能需要进行的检查数量，以确保因果一致性。
• 为减少客户端和数据存储跟踪依赖关系所需的状态，COPS-GT 提供了垃圾回收机制（详见第 5.1 节）。该机制在依赖关系提交到所有 COPS 副本后移除这些依赖。

为减少在复制期间的依赖检查次数，客户端库为服务器提供了一些潜在的优化方法。

以图 6 的依赖图为例：

• y1 依赖于 x3，并通过传递性依赖于 w1。如果存储节点在提交 y1 时确定 x3 已被提交，那么它可以推断出 w1 也已被提交，因此无需显式检查 w1。
• 类似地，z4 直接依赖于 t2 和 v6，但提交节点只需检查 v6，因为 v6 本身已经依赖于 t2。

也就是说，只要检查最近的依赖即可。

我们将必须检查的依赖项称为最近依赖，这些依赖项列在图 6 的表格中。为了让服务器能够使用这些优化方法，客户端库首先在写操作的依赖列表中计算出最近依赖，并在发出写操作时相应地标记它们。

对于键值存储，最近依赖已经足以提供因果+一致性；而完整的依赖列表则仅在 COPS-GT 中执行 get_trans 操作时才需要。

图6 sample graph

COPS 客户端库: COPS 中的客户端库需要的状态和复杂性显著较低，因为它只需要学习最近的依赖关系，而不是所有的依赖关系。因此，它不会存储或检索任何它获取的值的依赖关系：被检索的值比其任何依赖关系都更接近，因此这些依赖关系变得不再必要。

因此，COPS 客户端库只存储 ⟨key, version⟩ 条目。对于 get 操作，被检索的 ⟨key, version⟩ 会被添加到上下文中。对于 put 操作，库使用当前上下文中的最近依赖，清空上下文，然后只用这次 put 操作重新填充它。此 put 操作依赖于所有之前的键-版本对，因此它比这些依赖项更接近。

4.4 在 COPS 和 COPS-GT 中写入值

在描述了客户端库和键值存储的基本情况之后，我们现在来详细讲解在 COPS 中写入值的步骤。在 COPS 中，所有的写操作首先会发送到客户端的本地集群，然后异步地传播到远程集群。键值存储提供了一个单一的 API 调用来执行这两个操作：

ps

线性一致性

满足线性一致性的系统给我们这样一种感觉，这系统看着只有一个副本，这样我就可以放心地读取任何一个副本上的数据来继续我们的应用程序。

• 读写交错的序列（按照实时时钟排序），如果对于任何一个变量x的读操作read(x)，读到的值都是在此读操作之前最后一次写操作write(x)更新的值。

顺序一致性

顺序一致性最早被Leslie Lamport 在1979年提出，其定义如下：

A multiprocessor is said to be sequentially consistent if 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 appear in this sequence in the order specified by its program.[How to Make a Multiprocessor Computer That Correctly Executes Multiprocess Programs by Leslie Lamport ,1979]

翻译如下：

一个多处理器系统被称为顺序一致，当且仅当其任何执行的结果都与以下情况一致：所有处理器的操作都按某种顺序顺序执行，且每个处理器的操作在该顺序中出现的次序与其程序中指定的次序相同。

其有两点要求：

• 1.单个节点的事件历史在全局历史上看符合程序顺序，即对于同一个节点发起的读写序列，对于任何一个变量x的读操作read(x)，读到的值都是在此读操作之前最后一次此进程发起的写操作write(x)更新的值；

// 顺序1
A: W(x,1)      
B:        W(x,2)   R(x,2)

// 顺序2 错误
A: W(x,1)      
B:        W(x,2)   R(x,1)

• 2.对于整个读写交错序列， 所有节点看到的写操作序列必须一致，即错的话一起错，对的话一起对。

例如这里，全局写顺序是先将x写为1，再将写为2，

• 对于顺序1，C和D均先看到x=1，再看到x=2，是合法的。
• 对于顺序2，尽管全局写顺序是先将x写为1，再将写为2，但是C和D均先看到x=2，再看到x=1也是合法的。
• 对于顺序3，C和D看到的顺序完全相反，这会导致无法找到一个全局的顺序。

// 顺序1
A: W(x,1)
B:        W(x,2)
C:                  R(x,1)    R(x,2)
D:               R(x,1)     R(x,2)

// 顺序2
A: W(x,1)
B:        W(x,2)
C:                  R(x,2)    R(x,1)
D:               R(x,2)     R(x,1)

// 顺序3(错误)
A: W(x,1)
B:        W(x,2)
C:                  R(x,1)    R(x,2)
D:               R(x,2)     R(x,1)

因果一致性：

因果一致性是一种弱化的顺序一致性模型，它仅要求有因果关系的操作顺序是一致的，没有因果关系的操作顺序是随机的。如果事件B是由事件A引起的或受事件A的影响，那么这两个事件就具有因果关系。因果一致性适用于需要保持操作因果关系但又不需要严格一致性的应用场景。

最终一致性（Eventual Consistency）:

最终一致性是最弱的一致性模型，它保证只要没有新的更新，系统中的所有副本最终将达到一致状态。这种模型允许系统在短时间内出现数据不一致，以提高系统的可用性和性能。最终一致性适用于对实时一致性要求不高的应用场景，如社交网络中的状态更新、电子邮件系统等。

https://www.codedump.info/post/20220710-weekly-22/#顺序一致性

https://tech.meituan.com/2022/08/25/replication-in-meituan-02.html

https://lotabout.me/2019/QQA-What-is-Sequential-Consistency/

(prinston ppt)https://www.cs.princeton.edu/courses/archive/fall16/cos418/docs/L13-strong-cap.pdf