2016年4月12日
第14卷，第1期

为什么逻辑时钟如此简单

有时候，你需要的只是正确的语言。

Carlos Baquero 和 Nuno Preguiça

任何计算系统都可以被描述为执行一系列动作，其中动作是系统中任何相关的状态变化。例如，将文件读取到内存、修改内存中文件的内容或将新内容写入文件，对于文本编辑器来说都是相关的动作。在分布式系统中，动作在多个位置执行；在这种情况下，动作通常被称为事件。分布式系统中的事件示例包括发送或接收消息，或更改节点中的某些状态。并非所有事件都相关，但有些事件可能会引起并影响后续事件的发生方式。例如，对收到的邮件消息的回复会受到该消息的影响，也可能受到之前收到的消息的影响。

分布式系统中的事件可能发生在靠近的位置，例如，在同一台机器上运行的不同进程；或在数据中心内的节点；或地理上分布在全球各地；甚至在不久的将来规模更大。事件之间潜在的因果关系是分布式算法设计的根本。如今，几乎没有任何服务可以声称其核心没有某种形式的分布式算法。

为了理解这些因果关系，有必要将其范围限制在分布式系统本身内部可以感知到的范围内——内部因果关系。当然，分布式系统会与外部的物理世界互动，并且在更大的世界中也存在因果关系。例如，考虑一对夫妇使用一个系统计划晚上外出，该系统管理晚餐和电影的预订。一个人预订了晚餐，并通过电话告知另一个人。收到电话后，第二个人进入系统并预订了电影。分布式系统无法知道第一个预订实际上导致了第二个预订。

这种外部因果关系无法被系统检测到，只能通过物理时间来近似。（然而，时间完全排序了所有事件，即使是不相关的事件——因此，它不能替代因果关系——并且挂钟永远不会完全同步。^11,16）本文重点关注内部因果关系——系统可以跟踪的类型。

先发生关系

1978年，Leslie Lamport 定义了一个偏序关系，称为先发生，它连接了分布式系统中可能存在因果联系的事件。⁸ 事件 c 可能是事件 e 的原因，或者 c先发生于 e，当且仅当（if and only if）两者发生在同一个节点，并且 c 先执行，或者，如果它们在不同的节点上，则 e 可以通过从某个知道 c 的节点收到的消息来了解 c 的发生。如果两个事件都无法了解对方，则称它们为并发事件。

使用晚餐和电影预订的例子，图1显示了一个包含三个节点的分布式系统。节点之间的箭头表示已发送和传递的消息。Bob 对 Alice 的晚餐建议的肯定回答以及 Chris 稍后加入聚会的请求都受到 Alice 最初关于晚餐计划的询问的影响。

在这个分布式计算中，检查事件 c 是否可能导致另一个事件 e（c先发生于 e）的一个简单方法是找到至少一条从 c 到 e 的有向路径。如果找到这样的连接，则此偏序关系标记为 c → e 以表示先发生关系或潜在的因果关系。图1具有 a₁ → b₂ 和 b₂ → c₃（是的，也有 a₁ → c₃，因为因果关系是传递性的）。事件 a₁ 和 c₂ 是并发的（表示为 a₁ ∥ c₂），因为在任何方向上都没有因果路径。请注意，x ∥ y 当且仅当 x ↛ y 且 y ↛x。Chris 的无聊既没有影响 Alice 关于晚餐的问题，反之亦然。

因此，两个事件 x 和 y 之间可能存在三种关系：（a）如果 x → y，则 x 可能影响了 y；（b）如果 y → x，则 y 可能影响了 x；（c）x 和 y 之间没有已知的影响，因为它们是并发发生的 x ∥ y。

因果历史

可以使用因果历史以非常简单的方式跟踪因果关系。^3,14 系统可以为每个事件本地分配唯一的名称（例如，节点名称和本地递增计数器），并收集和传输事件集以捕获已知的过去。

对于新事件，系统会创建一个新的唯一名称，并且因果历史由该名称和节点中先前事件的因果历史的并集组成。例如，节点 C 中的第二个事件被分配名称 c₂，其因果历史是 H_c = {c₁, c₂} （如图2所示）。当节点发送消息时，发送事件的因果历史会随消息一起发送。当消息被接收时，远程因果历史与本地历史合并（通过集合并集）。例如，从节点 A 到 B 的第一个消息的传递将远程因果历史 {a₁, a₂} 与本地历史 {b₁} 和新的唯一名称 b₂ 合并，得到 {a₁, a₂, b₁, b₂}。

检查两个事件 x 和 y 之间的因果关系可以通过集合包含来简单地测试：x → y 当且仅当 H_x ⊊ H_y。这遵循因果历史的定义，其中事件的因果历史将包含在后续事件的因果历史中。更好的是，标记添加到历史记录的最后一个本地事件（在图中以粗体区分）允许使用更简单的测试：x → y 当且仅当 x ∈ H_y （例如，a₁ → b₂，因为 a₁ ∈ {a₁, a₂, b₁, b₂}）。这遵循因果历史包括（因果）先于给定事件的所有事件的事实。

向量时钟

现在应该很明显，因果历史有效，但不是很紧凑。这个问题可以通过依赖以下观察来解决：构建因果历史的机制意味着，如果事件 b₃ 存在于 H_y 中，则来自同一节点的所有先前事件 b₁ 和 b₂ 也存在于 H_y 中。因此，仅存储来自每个节点的最新事件就足够了。因果历史 {a₁, a₂, b₁, b₂, b₃, c₁, c₂, c₃} 被压缩为 {a ⟼ 2, b ⟼ 3, c ⟼ 3} 或简称为向量 [2, 3, 3]。

现在，与因果历史一起使用的规则可以转换为新的紧凑向量表示。

验证 x → y 需要检查 H_x ⊊ H_y。这可以通过验证每个节点来完成，如果 H_x 中包含的唯一名称也包含在 H_y 中，并且在 H_y 中至少有一个唯一名称未包含在 H_x 中。这立即转换为检查 x 的向量中的每个条目是否小于或等于 y 的向量中的对应条目，并且其中一个严格小于（即，∀i : V_x[i] ≤ V_y [i] 并且 ∃j : V_x[j] < V_y [j]）。可以更紧凑地表示为 x → y 当且仅当 V_x < V_y。

对于新事件，创建新的唯一名称等同于递增创建事件的节点的向量中的条目。例如，节点 C 中的第二个事件具有向量 [0, 0, 2]，这对应于因果历史的事件 c₂ 的创建。

最后，创建两个因果历史 H_x 和 H_y 的并集等同于取对应的两个向量 V_x 和 V_y 的逐点最大值（即，∀i : V [i] = max(V_x[i], V_y [i])). 逻辑告诉我们，对于每个节点中生成的唯一名称，只需要保留计数器最大的那个。

当收到消息时，除了合并因果历史之外，还会创建一个新事件。向量表示的这些步骤可以看出，例如，当来自 a 的第一个消息在 b 中接收时，其中取逐点最大值导致 [2, 1, 0]，并且新的唯一名称最终导致 [2, 2, 0]，如图3所示。

这种紧凑的表示形式，称为向量时钟，大约在1988年引入。^5,10 向量比较是因果历史集合包含的直接转换。这种等价性在现代向量时钟描述中经常被遗忘，并且可以将一个简单的编码问题变成一组不必要的复杂和神秘的规则，这与逻辑背道而驰。

点向量时钟

如到目前为止所示，当使用因果历史时，知道最后一个事件可以通过简单地检查最后一个事件是否包含在因果历史中来简化比较。如果您跟踪最后一个事件在哪个节点中创建，这仍然可以使用向量完成。例如，当质疑 x = [2, 0, 0] → y = [2, 3, 0] 时，粗体表示每个向量中的最后一个事件，您可以简单地测试 x[0] ≤ y[0]（2 ≤ 2），因为您已标记 x 中的最后一个事件是在节点 A 中创建的（即，它对应于向量的第一个条目）。然而，由于以粗体标记数字不是一种实际的实现方式，因此最后一个事件通常存储在向量之外（有时称为点）：例如，[2, 2, 0] 可以表示为 [2, 1, 0]b₂。请注意，现在向量表示 b₂ 的因果过去，不包括事件本身。

版本向量

在一个重要的应用类别中，无需为分布式计算中的所有事件注册因果关系。例如，要修改数据的副本，通常只需注册那些更改副本的事件。在这种情况下，当考虑因果历史时，您只需要为这些相关事件分配一个新的唯一名称。但是，当消息从一个站点传播到另一个站点时，您仍然需要传播因果历史，并且比较因果历史的其余规则保持不变。

图4呈现了与之前相同的示例，但现在用 ◦ 表示未注册用于因果关系跟踪的事件。如果运行表示对数据对象的副本的更新，则在节点 A 和 B 并发修改后，副本 a 的状态将发送到副本 b （在消息中）。当消息在节点 B 中接收时，检测到发生了两个并发更新，历史记录为 {a₁} 和 {b₁}，因为 a₁ → b₁ 和 b₁ → a₁ 都不成立。在这种情况下，创建了一个合并两个更新的新版本（合并用连接符号 ⊔ 表示），这需要创建一个新的唯一名称，从而得到 {a₁, b₁, b₂}。当副本 b 的状态稍后传播到副本 c 时，由于副本 c 中不存在并发更新，因此不会创建新版本。

同样，向量可以压缩表示。结果，称为版本向量，创建于 1983 年，¹² 比向量时钟早五年。图 5 呈现了与之前相同的示例，用版本向量表示。

在某些情况下，当一个副本的状态传播到另一个副本时，系统会将这两个版本保留为冲突版本。例如，在图 6 中，当从节点 A 接收到消息到节点 B 时，系统将每个因果历史 {a₁} 和 {b₁} 与各自的版本相关联地保存。与包含两个版本的节点关联的因果历史是 {a₁, b₁}，即所有版本的因果历史的并集。这种方法允许稍后在合并附加节点的状态时检查每个版本与其他版本之间的因果关系。冲突版本也可以合并，创建一个新的唯一名称，如示例所示。

点版本向量

向量因果关系跟踪的一个限制是，每个并发源都需要一个条目。⁴ 您可以预期数据中心中的节点数量与其处理的客户端数量之间存在几个数量级的差异。当数百万客户端访问服务时，每个客户端一个条目的向量无法很好地扩展。⁷ 再次，查看因果历史的基础，可以了解如何克服此限制。

因果历史的基本要求是为每个事件分配一个唯一标识符。没有要求此唯一标识符必须在本地或立即创建。因此，在可以将节点划分为客户端和服务器，并且客户端仅与服务器通信的系统中，可以延迟创建新的唯一名称，直到客户端与服务器通信，并使用在服务器中生成的唯一名称。与新版本关联的因果历史是客户端的因果历史与新分配的唯一名称的并集。

图 7 显示了一个示例，其中客户端 A 和 B 并发更新服务器 S。当客户端 B 首次写入其版本时，会创建一个新的唯一名称 s₁（在图中，此操作用符号 ⊚ 表示），并与客户端读取的因果历史 {} 合并，得到因果历史 {s₁}。当客户端 A 稍后写入其版本时，分配给此版本的因果历史是客户端的因果历史 {}，与新的唯一名称 s₂ 合并，得到 {s₂}。使用检查并发更新的正常规则，这两个版本是并发的。在示例中，系统保留了两个并发更新。为简单起见，省略了服务器 T 与其自身客户端的交互，但如图所示，在从服务器 S 接收数据之前，服务器 T 具有一个单一版本，该版本描述了它管理的三个更新——因果历史 {t₁, t₂, t₃}——之后，它持有两个并发版本。

一个重要的观察结果是，在每个节点中，所有版本的因果历史的并集包括所有生成的唯一名称，直到最后一个已知的名称：例如，在服务器 S 中，在两个客户端都发送其新版本之后，所有在 S 中生成的唯一名称都是已知的。因此，任何更新的因果过去都可以始终使用紧凑的向量表示来表示，因为它是在客户端读取对象时在某个服务器上已知的所有版本的并集。因果过去（表示为向量）和最后一个事件（保存在向量外部）的组合称为点版本向量。^2,13 图 8 显示了使用此表示形式的前一个示例，随着系统的运行，该表示形式最终变得比因果历史更紧凑。

在之前表达的条件（客户端仅与服务器通信，并且新的更新覆盖所有先前读取的版本）中，这在多个客户端通过 get/put 接口与存储节点交互的键值存储中很常见，点版本向量允许在写入版本之间跟踪因果关系，向量的大小与服务器数量相同。

最终评论

不应忽略跟踪因果关系。它在许多分布式算法的设计中非常重要。正如多位作者报告的那样，不尊重因果关系可能会导致用户出现奇怪的行为。^1,9

用于跟踪因果关系的机制以及这些机制中使用的规则通常被认为是复杂的，^6,15 并且它们的呈现方式并不总是直观。最常用的因果关系跟踪机制——向量时钟和版本向量——只是因果历史的优化表示，而因果历史很容易理解。

通过构建在因果历史的概念之上，您可以开始看到这些机制背后的逻辑，识别它们之间的差异，甚至考虑可能的优化。当遇到不熟悉的因果关系跟踪机制，或者尝试设计需要它的新系统时，读者应该问两个简单的问题：（a）哪些事件需要跟踪？（b）该机制如何转换回简单的因果历史？

如果没有简单的心理图像作为指导，错误和误解就会变得更加普遍。有时候，你需要的只是正确的语言。

致谢

我们要感谢 Rodrigo Rodrigues、Marc Shapiro、Russell Brown、Sean Cribbs 和 Justin Sheehy 的反馈。这项工作部分由欧盟 FP7 SyncFree 项目 (609551) 和 FCT/MCT 项目 UID/CEC/04516/2013 和 UID/EEA/50014/2013 资助。

参考文献

1. Ajoux, P., Bronson, N., Kumar, S., Lloyd, W., Veeraraghavan, K. 2015. 在大规模采用更强一致性方面面临的挑战。在第15届操作系统热点主题研讨会论文集，瑞士 Kartause Ittingen。Usenix 协会。

2. Almeida, P. S., Baquero, C., Gonçalves, R., Preguiça, N. M., Fonte, V. 2014. 最终一致性存储的可扩展和准确的因果关系跟踪。在分布式应用和互操作系统论文集，作为第九届分布式计算技术国际联合会议的一部分举行，德国柏林： 67-81。

3. Birman, K. P., Joseph, T. A. 1987. 存在故障时的可靠通信。 计算机系统汇刊 5(1): 47-76。

4. Charron-Bost, B. 1991. 关于分布式系统中逻辑时钟的大小。信息处理快报 39(1): 11-16。

5. Fidge, C. J. 1988. 消息传递系统中保留部分排序的时间戳。第11届澳大利亚计算机科学会议论文集 10(1): 56-66。

6. Fink, B. 2010. 为什么向量时钟很简单。Basho 博客； http://basho.com/posts/technical/why-vector-clocks-are-easy/。

7. Hoff, T. 2014. League of Legends 如何将聊天扩展到 7000 万玩家——需要大量的 minions。高可扩展性； http://highscalability.com/blog/2014/10/13/how-league-of-legends-scaled-chat-to-70-million-players-it-t.html。

8. Lamport, L. 1978. 分布式系统中事件的时间、时钟和排序。通讯 21(7): 558-565。

9. Lloyd, W., Freedman, M. J., Kaminsky, M., Andersen, D. G. 2011. 不要满足于最终一致性：使用 COPS 为广域存储实现可扩展的因果一致性。在第23届操作系统原理研讨会论文集，纽约州纽约：401-416。

10. Mattern, F. 1988. 分布式系统中的虚拟时间和全局状态。在并行和分布式算法国际研讨会论文集，法国 Gers：215- 226。

11. Neville-Neil, G. 2015. 时间是一种幻觉。acmqueue 13(9). 57 - 72

12. Parker, D.S., Popek, G. J., Rudisin, G., Stoughton, A., Walker, B. J., Walton, E., Chow, J. M., Edwards, D., Kiser, S., Kline, C. 1983. 分布式系统中互不一致性的检测。IEEE 软件工程汇刊 9(3): 240-247。

13. Preguiça, N. M., Baquero, C., Almeida, P. S., Fonte, V., Gonçalves, R. 2012. 简短公告：使用点版本向量在分布式存储系统中进行高效的因果关系跟踪。在 分布式计算原理研讨会，编辑：D. Kowalski 和 A. Panconesi：335-336。

14. Schwarz, R., Mattern, F. 1994. 检测分布式计算中的因果关系：寻找圣杯。分布式计算 7(3): 149-174。

15. Sheehy, J. 2010. 为什么向量时钟很难。Basho 博客； http://basho.com/posts/technical/why-vector-clocks-are-hard/。

16. Sheehy, J. 2015. 没有现在。acmqueue 13(3): 20-27。

Carlos Baquero 是米尼奥大学和 INESC Tec 高可靠性软件实验室的计算机科学助理教授和高级研究员。他于 1994 年和 2000 年在米尼奥大学获得理学硕士和博士学位。他的研究兴趣集中在分布式系统，特别是因果关系跟踪、最终一致性的数据类型和分布式数据聚合。您可以通过 [email protected] 和 Twitter 上的 @xmal 联系他。

Nuno Preguiça 是里斯本新大学科学技术学院计算机科学系的副教授，并领导 NOVA 计算机科学与信息学实验室的计算机系统组。他于 2003 年在里斯本新大学获得计算机科学博士学位。他的研究兴趣集中在分布式系统中复制数据管理和大量信息处理以及移动计算环境中的问题。您可以通过 [email protected] 和 Twitter 上的 @nunopreguica 联系他。

最初发表于 Queue vol. 14, no. 1—
在数字图书馆中评论本文

更多相关文章

Matt Godbolt - C++ 编译器中的优化
在为编译器提供更多信息时，需要权衡：这可能会使编译速度变慢。诸如链接时优化之类的技术可以为您带来两全其美。编译器中的优化不断改进，即将到来的间接调用和虚函数分派的改进可能很快会带来更快的多态性。

Ulan Degenbaev, Michael Lippautz, Hannes Payer - 作为合资企业的垃圾回收
跨组件跟踪是解决跨组件边界的引用循环问题的一种方法。只要组件可以形成跨 API 边界具有非平凡所有权的任意对象图，就会出现此问题。CCT 的增量版本已在 V8 和 Blink 中实现，从而能够以安全的方式有效且高效地回收内存。

David Chisnall - C 不是一种低级语言
在最近的 Meltdown 和 Spectre 漏洞之后，值得花一些时间研究根本原因。这两种漏洞都涉及处理器推测性地执行超出某种访问检查的指令，并允许攻击者通过侧信道观察结果。导致这些漏洞以及其他几个漏洞的功能被添加进来，是为了让 C 程序员继续相信他们正在用低级语言编程，而这种情况已经几十年没有发生了。

Tobias Lauinger, Abdelberi Chaabane, Christo Wilson - 你不应该依赖我
大多数网站都使用 JavaScript 库，其中许多库已知是易受攻击的。了解问题的范围以及包含库的许多意外方式，只是改进情况的第一步。这里的目标是，本文中包含的信息将有助于为社区提供更好的工具、开发实践和教育工作。