引言

因果一致性 [1] 是可用于分布式数据库的一致性准则之一。

分布式数据库提供因果一致性，如果因果相关的读写操作在分布式系统的每个节点上以相同的顺序被看到。并发写入可能在不同的节点上以不同的顺序被看到。因果一致性弱于顺序一致性 [2]，但强于最终一致性 [3]。有关最终一致性的更详细描述，请参阅之前的博客文章 https://blog.mariadb.org/eventually-consistent-databases-state-of-the-art/。

当一个事务执行一个读操作，随后再执行一个写操作时，即使是在不同的对象上，该首次读取也被认为在写操作之前具有因果顺序。这是因为写操作创建的值可能依赖于读操作的结果。类似地，读操作在之前对同一对象执行的写操作之后具有因果顺序，该写操作存储了读操作检索到的数据。此外，即使是同一个节点执行的两个写操作，也按其执行顺序被定义为具有因果顺序。直观地说，在将值 v 写入对象 x 后，一个节点知道对 x 的读取会得到 v，因此后来的写操作可以说与之前的写操作（潜在地）具有因果关系。最后，因果顺序是传递的：也就是说，如果操作 A 在 B 之前（因果地）排序，并且 B 在 C 之前排序，那么 A 在 C 之前排序。

即使通过其他操作也无因果关系的操作被称为并发操作。考虑以下示例

Direction of time ---------------->
P1 : w1[x] = 1
P2 : w2[x] = 2
P3 :             r3[x] = 2
P4 :                         r4[x] = 1

此执行是因果一致的，因为读操作 r3[x] 因果依赖于写操作 w2[x]，而读操作 r4[x] 因果依赖于写操作 w1[x]。请注意，并发写操作可能在不同的事务或节点上以不同的顺序被看到。

实现因果一致性

可以使用 Lamport 时钟 [4] 或版本向量 [5] 来实现因果一致性。因果一致性模型通过使用多部分时间戳来实现，这些时间戳分配给每个对象。这些时间戳存储在一个向量中，该向量包含对象在每个副本处的版本号。此向量必须包含在所有更新和查询请求中（以依赖关系的形式），以便操作遵守因果顺序：操作 A 只能在给定节点上处理，前提是操作 A 因果依赖的所有操作已在该节点上应用。

向量时钟中的每个元素对应一个主机，元素的值表示从该主机发送的消息数量。向量时钟信息用于在必要时对消息的传递进行排序或延迟，从而维护所需的一致性。然而，为了维护数据项的一致性，我们需要关于每个数据项的写入信息，并且为每个数据项维护一个时钟会有所帮助。因此，我们不是维护一个大小为 N（主机数量）的向量时钟，而是维护一个大小为 M（对象数量）的向量。向量 v 中 v[i] 的值包含数据项 i 上的写入数量。

每个主机维护一个大小为 M 的向量。每当它更新一个项的值时，它会增加相应的元素，并将该向量与数据项和新值的消息一起发送到每个拥有副本的站点。当主机接收到更新消息时，它会延迟消息的传递，直到其向量中的每个元素都大于或等于附加消息中的对应元素。之后，对数据项的更新才会被应用。在这种情况下，消息开销是 O(M)，因此与系统中的主机数量无关。

如果每条消息都是更新消息，则它携带的是数据项的新值，而不是指令。这样，数据项上的更新传递就不需要等待同一项上的先前更新。如果使用了向量时钟，这是不可能的。在这种情况下，即使对于因果覆盖的先前消息，消息的传递也会被延迟。

使用因果一致性的应用和数据库

COPS 和 Eiger

COPS 系统 [6]（保持顺序的服务器集群）引入了 causal+ 一致性，旨在支持托管在少量大型数据中心中的复杂在线应用，每个数据中心由前端服务器（COPS 的客户端）和后端键值数据存储组成。Eiger [7] 的设计类似但实现不同。

COPS 和 Eiger 通过客户端库支持因果关系。两个系统都会将写入复制到地理位置分散的数据中心，并强制执行观察到的顺序。通过延迟写操作，直到所有因果上先前的操作已在该数据中心应用，来强制执行观察到的顺序。

COPS 在本地数据中心以线性一致 [8] 的方式执行所有读写操作，然后以 causal+ 一致的顺序在后台跨数据中心复制数据。图 1 描述了 COPS 的高级架构。

 

图 1：COPS 和 Eiger 的架构 [6]。

类似地，Eiger 系统在每个数据中心内部提供线性一致性，并基于列族数据模型提供因果一致的数据存储，以在地理分布式环境中实现更好的性能。来自客户端的所有操作都通过客户端库从本地数据中心提供服务。该库协调对本地数据中心节点的访问，执行读写事务算法，并跟踪因果关系并将依赖项附加到写操作。每个副本存储数据库的完整副本，操作在本地处理。操作在本地执行后，会异步推送到远程数据中心，但只有在所有因果相关的操作先前已提交后才会提交。

Bolt-on

Bailis 等人在 [9] 中提出了一种称为 Bolt-on 的客户端中间件软件。此中间件仅保证应用程序定义的依赖项，作为因果一致性的替代方案。图 2 描述了 Bolt-on 中间件的架构。

 

图 2：Bolt-on 的架构 [9]。

Bolt-on 架构假定底层数据存储处理数据管理的大部分方面，包括复制、可用性和收敛。在该架构中，底层数据存储在本地使用最终一致性，并允许大量的读写历史记录；中间件处理因果依赖关系，并由一组规则组成，这些规则将可能的历史记录限制为遵守所需一致性模型的历史记录。

应用：MMORPG

在大型多人在线角色扮演游戏（MMORPG）中，玩家可以在虚拟游戏世界中相互协作，并且玩家和不同的游戏世界自然是分布式的。这些系统管理大量数据，最大的问题是如何支持数据一致性。根据 CAP 定理，我们必须牺牲两个属性中的一个：一致性或可用性 [10]。如果在线游戏不能保证可用性，玩家的请求可能会失败。如果数据不一致，玩家可能会获得不符合游戏逻辑的数据，并且这些数据可能会影响他们的操作。因此，对于 MMORPG 环境来说，在数据一致性和系统可用性之间找到平衡非常重要。出于这个原因，我们必须分析 MMORPG 的数据一致性要求，以找到平衡 [10]。

Diao [10] 研究了 MMORPG 的不同一致性模型，发现确实有一部分数据，因果一致性是一个有吸引力的选择：游戏数据。游戏数据包含例如世界外观、非玩家角色（这些角色由游戏开发者创建并仅由游戏逻辑控制）的元数据、系统配置和游戏规则。这些数据在整个游戏中被玩家和游戏引擎使用，但只能由游戏开发者修改。游戏数据的一致性要求与例如账户数据相比没有那么严格。因为例如非玩家角色名称的更改或鸟类动画持续时间的更改玩家可能不会注意到。

此外，游戏数据的某些更改需要同步传递给所有在线玩家，例如世界外观、武器威力、非玩家角色、游戏规则和脚本的更改。如果这些区域存在不一致，将导致游戏显示错误和玩家逻辑错误。因此，有些数据需要存储在服务器端，有些存储在客户端。客户端的游戏数据只能在玩家登录或开始游戏时与服务器同步。因此，需要因果一致性 [10]。

这可能意味着，当玩家 A 使用浏览器连接到游戏服务器时，游戏服务器将检查当前的本地数据，并以数据包的形式更新客户端的游戏数据。更新后，所有未来的本地访问都将返回更新后的值。尚未与游戏服务器通信的玩家 B 仍将保留过时的游戏数据。

游戏服务器维护游戏数据的主要版本，并将其传输给客户端。此外，不同游戏世界的玩家无法相互讨论。因此，唯一需要确保的是游戏数据在同一游戏世界中同一时间点保持一致，以便在该游戏世界中的所有玩家都得到平等对待。这需要在游戏世界内部使用强一致性，并在不同游戏世界之间使用因果一致性。当游戏数据被开发者修改时，更新值应同步传递给该游戏世界中的所有副本，并异步传递给其他游戏世界。

尽管研究 [10] 已指出在 MMORPG 上使用因果一致性的可能性，但据作者所知，目前尚无实际出版物或其他信息表明因果一致性实际上已用于 MMORPG 游戏（例如 指环王 Online）。

应用：Facebook

Facebook 是一款在线社交网络服务。注册使用该网站后，用户可以创建用户资料，添加其他用户为好友，交换消息，发布状态更新和照片，分享视频，并在其他人更新资料时接收通知。

当您登录 Facebook 账户时，服务器会显示您当时的状态消息和您朋友的状态消息。Facebook 上的状态消息可能包含图片、分享的链接和故事或您自己的消息。自然，您的账户数据需要强一致性，但对于状态数据，较弱的一致性模型是可以接受的。用户在线期间，用户朋友和用户的状态更新不需要严格排序，因果排序就足够了。

因此，当用户 A 发送状态更新，而用户 B 回复该更新时，这两个更新之间存在因果顺序。然而，当用户 C 和 D 进行完全不相关的更新时，这些更新对用户 A 和 B 出现的顺序并不重要。这是因为用户 A 和 B 不知道更新是以何种顺序执行的。

最终一致性不足以用于 Facebook 状态更新的原因在于，最终一致性不要求写操作之间有任何排序。考虑一种情况，用户 A 首先发送了一个状态更新，几秒钟后 A 又更新了第一个状态更新。在最终一致性下，用户 A 的所有朋友可能只能看到第一个更新，因为最终一致性不能保证第一个更新在第二个更新之前执行。在因果一致性下，由于用户 A 对第一个更新进行了读取，然后进行了写入（用户 A 更新后的状态），这些操作是因果相关的，因此用户 A 的所有朋友自然会看到第二个更新。

尽管因果一致性可能是适用于 Facebook 状态更新和几个类似包含状态更新的分布式服务（如 LinkedIn、Twitter 和 Yahoo）的一致性模型，但据作者所知，尚无科学或其他文献表明因果一致性实际正在被使用。

结论

可以使用 Lamport 时钟强制执行因果一致性模型。使用因果一致性的事务按照反映其因果相关的读/写操作顺序的顺序执行。并发操作可以以不同的顺序提交，其结果也可以以不同的顺序读取。

实际上，因果一致性可以解决最终一致性无法解决的许多问题，例如操作排序。因果一致性确保每个参与者都以相同的因果顺序看到操作，这使得因果一致性强于最终一致性。然而，因果一致性无法支持例如分布式完整性约束。

尽管在研究中开发了一些有前景的系统，但据作者所知，目前尚无使用因果一致性模型的商业或成熟系统。有关更详细的讨论，请参阅 [11]。

参考文献

[1] Mustaque Ahamad , Gil Neiger , James E. Burns , Prince Kohli , P.W. Hutto: Causal Memory: Definitions, Implementation and Programming, http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.50.3356

[2] Leslie Lamport: How to Make a Multiprocessor Computer That Correctly Executes Multiprocess Programs, IEEE Trans. Comput. C-28,9 (Sept. 1979), 690-691.

[3] Werner Vogels: Eventually consistent. Communications of the ACM 52: 40. doi:10.1145/1435417.1435432

[4] Leslie Lamport: Time, clocks, and the ordering of events in a distributed system, Communications of the ACM, 21: 7, pp. 558–565, 1978.

[5] C. J. Fidge: Timestamps in message passing systems that preserve the partial ordering, in Theoretical Computer Science, 1988.

[6] W. Lloyd, M. J. Freedman, M. Kaminsky, and D. G. Andersen: Don’t settle for eventual: scalable causal consistency for wide-area storage with COPS, in Proceedings of the 23rd ACM Symposium on Operating Systems Principles, pp. 401–416, Portugal, October 23-26, 2011.

[7] W. Lloyd, M. J. Freedman, M. Kaminsky, and D. G. Andersen: Stronger semantics for low-latency geo-replicated storage,” in Proceedings of the 10th USENIX Symposium on Networked Systems Design and Implementation, pp. 313–328, Lombard, IL, USA, April 2-5, 2013.

[8] M. Herlihy and J. M. Wing, Linearizability: A correctness condition for concurrent objects, ACM
Trans. Program. Lang. Syst., 12:3, pp. 463–492, 1990.

[9] . Bailis, A. Ghodsi, J. M. Hellerstein, and I. Stoica,: Bolt-on causal consistency,” in Proceedings of the ACM SIGMOD International Conference on Management of Data, pp. 761–772, New York, NY, USA, June 22-27, 2013

[10] Z. Diao, “Consistency models for cloud-based on-line games: the storage system’s perspective,” in
25th Workshop on Grundlagen von Datenbanken, Computing, Portland, Oregon, USA, July 16-19,
pp. 16–21, Ilmenau, Germany, May 28 – 31, 2013.

[11] Mawahib Musa Elbushra, Jan Lindström: Causal Consistent Databases, Open Journal of Databases (OJDB), 2:1, http://www.ronpub.com/publications/OJDB_2015v2i1n02_Elbushra.pdf