收敛

实践研究重启

马丁·克莱普曼，由彼得·阿尔瓦罗介绍

“实践研究”专栏结合了数字图书馆（世界上最大的计算机科学研究集合）的资源和会员的专业知识。“实践研究”专栏的共同目标是在学术界人士及其在业界的同行之间分享阅读计算机科学研究的乐趣和实用性。

我非常自豪和兴奋地宣布重启 acmqueue 的“实践研究”专栏。从 2016 年创刊起，在最初的三年里，“实践研究”专栏通过学术界专家的精心策划，将开创性和前沿研究成果带给那些忙于构建事物而无暇应对海量学术出版物的从业者。我们相信该系列成功实现了其既定目标，即在学术界人士及其在业界的同行之间分享“阅读计算机科学研究的乐趣和实用性”。我们知道读者们一直想念它，并且我们很高兴在三年中断后重新点燃这火焰。

在这第一期中，我们邀请了剑桥大学研究员和附属讲师马丁·克莱普曼博士，策划了一系列关于一个始终令人感兴趣的领域——收敛或“最终一致性”复制系统的最新研究论文。他的专家分析围绕该主题展开，通过系统、编程语言、人机交互和数据管理这四个不同研究领域的最新工作视角来审视它。在此过程中，读者将接触到各种数据结构、算法、证明技术和编程模型（每种模型都用不同的形式化方法描述），所有这些都旨在使大规模分布式系统的编程更容易。我希望您像我一样喜欢他的专栏。

——彼得·阿尔瓦罗

实践研究：收敛

马丁·克莱普曼

在分布式系统中，从广义上讲，有两种数据一致性方法：共识或收敛。共识方法可以使用 Paxos 或 Raft 等算法实现，它可以确保强一致性，这意味着使分布式系统看起来好像不是分布式的（线性化）并且好像没有并发（可串行化）。这种方法使系统易于使用，但它以性能、可伸缩性和可以容忍的故障类型为代价，因为每个更新都需要等待来自其他节点的回复才能完成。

另一种方法是收敛，更常被称为最终一致性。在这种模型中，允许不同的节点独立处理更新，而无需相互等待。这通常更快、更健壮、更具可伸缩性，但会导致节点具有暂时不一致的数据版本。当这些节点相互通信时，必须解决这些不一致性——也就是说，它们应该收敛到相同的状态。

收敛是一个非常有用的想法，不同的研究社区已经开发了几种实现它的方法。本文着眼于收敛主题的四种变体，这些变体来自计算机科学的四个领域。我选择了五篇相当近期的文章，这些文章介绍了每种收敛技术。

无冲突复制数据类型

努诺·普雷吉卡。《无冲突复制数据类型：概述》。arXiv:1806.10254 [cs.DC]，2018 年 6 月。 https://arxiv.org/abs/1806.10254

无冲突复制数据类型 (CRDT) 是一种数据结构，可以在多个节点上并发修改，并提供内置算法用于将这些更新合并在一起。CRDT 已针对各种数据类型创建，例如集合、列表、键值映射、图、计数器和 JSON（JavaScript 对象表示法）树。它们用于服务器端数据库（例如 Microsoft 的 Azure CosmosDB 和 Redis Enterprise）以及协作软件的客户端库（例如 Automerge 和 Yjs）。

CRDT 通过交换律确保收敛——也就是说，无论何时两个节点处理了相同的更新，它们都将处于相同的状态，即使更新到达的顺序不同。它们通过向实际数据结构添加一些元数据来实现此属性：例如，许多算法将唯一 ID 与每个操作关联，并在以后使用该 ID 来引用数据结构的各个部分。这使得在存在并发更新时操作变得明确。通过仔细管理此元数据，CRDT 确保并发操作可交换，从而使不同的副本能够合并其状态并收敛。

操作转换

大卫·孙、程正孙、奥古斯蒂娜·吴和蔡伟伟。《协同编辑器中用于一致性维护的 OT 和 CRDT 在正确性和复杂性方面的真正差异》。人机交互会议论文集，第 4 卷，第 CSCW1 期，第 21 条，第 1-30 页，2020 年 5 月。 https://dl.acm.org/doi/10.1145/3392825

操作转换 (OT) 最常用于实时协作编辑器（如 Google Docs），它可以确保每当多个用户并发更新文档时，它们都会收敛到相同的状态。对于纯文本，数据结构是一个线性字符序列，可以通过在任何位置插入或删除字符来更新。这个想法也已推广到富文本、电子表格和其他文件类型。此类应用程序也可以使用 CRDT 实现，但许多现有的协作产品都使用 OT。OT 算法允许通过比 CRDT 使用的通用交换律更严格的规则来重新排序并发操作。

OT 是一种比 CRDT 更古老的技术；事实上，CRDT 的创建是为了回应 20 世纪 90 年代和 21 世纪初发布的几种有缺陷的 OT 算法。如今，OT 和 CRDT 都被广泛使用，它们之间的权衡也很微妙。建议的文章由 OT 方法的支持者撰写，其对 CRDT 的批评对于学术论文来说异常激烈。即使我不同意作者所说的一切，但关注这场激烈辩论的场面也很有趣。

可合并复制数据类型

高瑟姆·卡基、斯瓦恩·普里亚、KC·西瓦拉马克里希南和苏雷什·贾加纳坦。《可合并复制数据类型》。编程语言会议论文集，第 3 卷，第 OOPSLA 期，第 154 条，第 1-29 页，2019 年 10 月。 https://dl.acm.org/doi/10.1145/3360580

可合并复制数据类型 (MRDT) 是收敛的另一种方法，它基于版本控制系统（如 Git）的思想。在 Git 中，如果两个用户独立编辑文件的同一部分，则用户必须手动解决合并冲突，而 CRDT 和 OT 会自动合并并发更新，而无需任何用户交互。MRDT 将类似 CRDT/OT 的自动合并与类似 Git 的版本控制相结合。

MRDT 是类似于 CRDT 的数据结构。不同之处在于，CRDT 提供了一个将一个节点的状态与另一个节点的状态合并的函数，而 MRDT 通过不仅查看每个分支上的最新状态，还考虑两个分支的最近公共祖先状态（即，两个分支分叉后的提交）来合并版本历史的两个分支。因此，MRDT 可以看到自公共祖先以来每个分支上发生了哪些变化，这使其可以维护比 CRDT 更少的元数据。相反，它必须维护提交历史图，而某些 CRDT 可以避免这种情况。MRDT 算法存在于计数器、队列、集合、映射、二叉树和其他数据结构中。

作为逻辑单调性 (CALM) 的一致性和不变一致性

约瑟夫·M·海勒斯坦和彼得·阿尔瓦罗。《保持冷静：何时分布式一致性变得容易》。通讯，第 63 卷，第 9 期，第 72-81 页，2020 年 9 月。 https://dl.acm.org/doi/10.1145/3369736

彼得·拜利斯、艾伦·费克特、迈克尔·J·富兰克林、阿里·戈德西、约瑟夫·M·海勒斯坦和伊翁·斯托伊卡。《数据库系统中的协调避免》。VLDB 基金会会议论文集，第 8 卷，第 3 期，第 185-196 页，2014 年。 http://www.vldb.org/pvldb/vol8/p185-bailis.pdf

CRDT/OT/MRDT 方法在它们设计的场景中非常出色，但它们不足以实现每种类型的软件。特别是，如果您需要管理某种有限的资源——例如，确保客户花费的钱不超过他们帐户中的钱，或者您不会将剧院或飞机中的同一个座位卖给多个人，或者您不会将仓库中最后一件库存商品承诺给多个买家——那么您不能只是让每个节点独立于其他节点更新其状态。需要某种协调来决定哪个事务通过以及谁获得座位或最后一件库存商品，因为消耗资源的操作是互斥的。例如，这种协调可以实现为共识算法或锁定协议。

那么问题是：什么一般原则告诉我们何时使用 CRDT 及其同类，以及何时需要更强的保证（例如共识）？CALM 定理为这个问题提供了精确的答案：只要程序在逻辑上是单调的，就可以避免协调。CRDT/OT/MRDT 算法都是编写逻辑单调程序的方法（数据结构的状态由单调增长的更新集决定）；使用此类程序，输入可以以任何顺序到达，而不会影响输出。另一方面，管理对有限资源的访问是非单调操作，因此需要在系统中的节点之间进行协调。

另一种相关的方法是使用不变一致性的概念。如果两个节点可以独立进行更新以保持不变性，并且您可以确定在合并更新时不变性继续得到满足，则不变性是一致的。假设您有一个不变性，例如“剧院中的座位不会卖给多个人”。这个例子不是一致的，因为一个节点可能出售一个空座位（这是有效的），另一个节点可能独立出售同一个座位（也是有效的），但是两个更新的合并违反了不变性。另一方面，只要您只插入而不删除，引用完整性（外键）约束就是一致的。如果所有不变性都是一致的，则应用程序可以是无协调的，而不一致的不变性则需要协调。

结论

关于这四种方法的一个有趣的细节是，它们源于完全不同的计算机科学领域：CRDT 来自操作系统社区，OT 来自人机交互，MRDT 来自编程语言，CALM/不变一致性来自数据库。每个社区都将自己的思维方式应用于收敛的概念，这有时会导致对彼此工作的误解，尤其是在不同的社区并不总是像您可能希望的那样相互交流的情况下。然而，总而言之，这组多样化的视角为我们提供了更强大的工具集，可以应用于现实世界的问题。

彼得·阿尔瓦罗是加州大学圣克鲁兹分校的计算机科学副教授，他在那里领导 Disorderly Labs 研究小组 (disorderlylabs.github.io)。他的研究重点是使用以数据为中心的语言和分析技术来构建和推理数据密集型分布式系统，以使其具有可伸缩性、可预测性，并且能够应对大规模分布中固有的故障和不确定性。他在加州大学伯克利分校获得博士学位，师从约瑟夫·M·海勒斯坦。他是国家科学基金会职业奖、Facebook 研究奖、Usenix ATC 2020 最佳演示奖、SIGMOD 2021 杰出 PC 奖和 UCSC 卓越教学奖的获得者。

马丁·克莱普曼是剑桥大学的研究员和附属讲师，也是畅销书《设计数据密集型应用》（O'Reilly Media）的作者。他从事分布式系统安全和协作软件方面的工作。此前，他是一名软件工程师和企业家，共同创立并出售了两家初创公司，并在 LinkedIn 从事大规模数据基础设施方面的工作。

最初发表于 Queue 第 20 卷，第 3 期——
在数字图书馆中评论本文

更多相关文章

马克·布鲁克、安库什·德赛 - AWS 的系统正确性实践
构建可靠且安全的软件需要一系列方法来推理系统正确性。除了行业标准测试方法（如单元测试和集成测试）之外，AWS 还采用了模型检查、模糊测试、基于属性的测试、故障注入测试、确定性模拟、基于事件的模拟以及执行跟踪的运行时验证。形式化方法一直是开发过程的重要组成部分——也许最重要的是，形式化规范作为测试预言机，为 AWS 的许多测试实践提供了正确的答案。正确性测试和形式化方法仍然是 AWS 的主要投资领域，并且由于在这些领域已经看到的出色回报而加速发展。

阿基里斯·贝内托普洛斯 - 数据中心计算机的中间表示
我们已经到了分布式计算无处不在的地步。内存应用程序数据大小正在超过单台机器的容量，因此需要将其分区到集群中；在线服务具有高可用性要求，只有通过将系统部署为多个冗余组件的集合才能满足这些要求；高持久性要求只能通过数据复制来满足，有时跨越广阔的地理距离。

大卫·R·莫里森 - 模拟：分布式系统中未充分利用的工具
模拟在人工智能系统的出现中发挥着巨大作用：我们需要一种高效、快速且经济高效的方式来训练 AI 代理在我们的基础设施中运行，而模拟绝对提供了这种能力。

马特·法塔、菲利普-约瑟夫·阿里达、帕特里克·哈恩、贝齐·拜尔 - 从企业到云端：谷歌的虚拟桌面
超过四分之一的谷歌员工使用内部、数据中心托管的虚拟桌面。这种本地部署产品位于公司网络中，允许用户从世界任何地方远程开发代码、访问内部资源和使用 GUI 工具。其中最显着的特点是，虚拟桌面实例可以根据手头的任务调整大小，具有持久的用户存储，并且可以在公司数据中心之间移动以跟随出差的谷歌员工。直到最近，我们的虚拟桌面都托管在使用名为 Ganeti 的自研开源虚拟集群管理系统的谷歌公司网络上的商用硬件上。今天，这项重要且对谷歌至关重要的工作负载在 GCP（谷歌计算平台）上运行。