并发性和自动冲突解决

介绍

处理冲突

自动冲突解决

结论

参考

介绍

现代软件应用通常需要具备可靠性和可扩展性。通过将多个不可靠的组件组合成一个更大的分布式系统，我们可以实现比单个组件更高的可靠性和可扩展性。

然而，与单实例部署相比，分布式系统在逻辑推理、正确实现和维护方面都更加困难。分布式系统中存在许多需要处理的问题：

• 不可靠的时钟
• 无限制的网络延迟
• 网络带宽有限
• 非静态成员集
• 异质成分
• 任意进程暂停
• ...

本文将重点讨论一个特定问题：并发与冲突。如果两个操作彼此互不感知，则称它们是并发的。并发操作可以交错执行，也可以顺序执行——它们之间没有实际的顺序关系。并发性关乎系统的设计方式，不应与并行性混淆。并行性定义的是系统的运行方式，即同时运行多个操作。

处理并发时，几乎肯定会遇到冲突。当一个资源被并发修改时，也就是被多个并发操作修改时，就会发生冲突。我们可以从不同的抽象层次来看待并发和冲突：比如两个人同时编辑同一份文档，两个进程同时增加数据库中的同一个计数器，或者两个 CPU 核心同时修改同一个内存地址。

我们该如何处理冲突？一种常见的策略是使用同步技术（例如锁定）来避免冲突。以桌面文本处理应用程序为例：每当有人打开一个文档时，该文档就会被锁定，其他人无法修改。数据库通常支持客户端显式锁定，但内部也会使用锁定来隔离事务。

锁的主要缺点在于，根据系统中的争用程度，进程可能需要暂停执行，等待锁被释放。当两个进程都在等待另一个进程持有的锁时，需要考虑并处理死锁问题。如果数据库中的争用很高，事务吞吐量可能会受到影响。如果 Microsoft Excel 文档的争用很高，用户之间可能会发生争执。

然而，在某些情况下，我们可以无需任何同步。例如：像 Google Docs 或 Etherpad 这样的协作编辑器、像 Git 这样的分布式版本控制系统，或者像 DynamoDB 或 Cassandra 这样的分布式数据库，都可以在不进行任何同步的情况下处理（部分）冲突。

本文余下部分结构如下。首先，我们将概述冲突解决的概念，并讨论两种常用冲突处理技巧的优缺点。之后，我们将介绍两种能够自动解决冲突的替代方案。最后，我们将总结主要发现，为本文画上句号。

处理冲突

选择合适的工具来完成工作

冲突解决有很多不同的算法和技巧。找到合适的算法需要你仔细分析问题。以下是一些你可以问自己的问题：

• 你预计会发生多少起冲突？冲突是偶发事件还是经常发生？
• 最多允许多少方同时进行修改？
• 相关各方之间有何关联？处理发生在同一台机器上的冲突比通过不可靠的网络连接解决冲突要容易得多。
• 丢失数据可以接受吗？如果冲突解决方式很简单，只需选择一个冲突的更新并丢弃所有其他更新即可，那么就可以相当容易地达到一致状态。

如果您清楚自身需求，就可以从众多可行的技术或算法中选择一种来处理冲突。但有一点至关重要：为了处理冲突，我们可能需要先检测到它们。幸运的是，有多种方法可以通过跟踪某种形式的修改历史来对资源变更进行版本控制。例如，可以通过像 Git 那样显式地跟踪所有变更的完整历史记录来实现这一点，或者像 DynamoDB 那样使用向量时钟 [1, 2]。

首先，让我们来看两种易于实现但存在一些明显缺点的“解决”冲突的方法：放弃并发和解决委托。

放弃并发性

这种技术有时也被称为“最后写入获胜”（LWW），它通过丢弃除冲突中涉及的一项操作之外的所有操作来处理冲突。例如，Cassandra 就使用这种技术来解决多个副本上发生的冲突更新。其明显的缺点是，解决冲突实际上意味着丢失数据。

使用此方法时，应尽可能避免冲突，并做好丢失更新的准备。在 Git 中，也可以通过命令行参数使用此方法--theirs，--ours但您应该清楚自己在做什么，以免引起同事的不满。

决议授权

冲突解析委托通过在下次读取请求中返回同一值的两个版本，并请求客户端解决冲突，从而明确地指出检测到的任何冲突。例如，如果合并算法无法自动合并同一文件的两个版本，Git 就会使用此技术，停止合并并请求用户手动解决冲突。

虽然冲突解决委托比之前的技术更优雅，但它也存在一些代价。首先，冲突检测是一项开销很大的操作。维护完整的变更历史记录对于源代码库或许可行，但对于数据库而言则不然。向量时钟效率更高，但每次写入仍然会带来一定的操作开销。其次，通过委托解决冲突，实际上并没有真正解决它，问题只是被转移到了其他人身上。

幸运的是，还有其他一些替代方案，既不会丢失任何更新，又能无需委托即可解决冲突。让我们来看两个值得注意的自动冲突解决技术示例：操作转换和无冲突复制数据类型。

自动冲突解决

运营转型

操作转型（OT）[3]旨在实现协作文本编辑器的一致性。多年来，研究人员开发了不同的扩展和变体，最终产生了诸如Google Wave之类的应用程序。

OT 的核心思想是通过共享客户端执行的操作并让每个客户端异步应用这些操作，来保持并发修改的客户端之间的同步。这样，所有客户端最终都能达到一致的状态。但如果某个操作到达客户端时，客户端本身已经修改了文档，就可能与传入的操作发生冲突，从而导致问题。这时，转换函数就派上了用场。

考虑以下示例，如下图所示：客户端A和B同时修改文档“abc”。A想在位置 0 插入字符“x”（O1 = Ins(0, "x")）。同时，B删除位置 2 的字符“c”（O2 = Del(2, "c")）。

现在双方交换操作，以便对方客户端能够跟上修改进度。然而，当A收到删除操作时，该字符已不再位于位置 2。这就是为什么所有远程操作都要经过转换函数T的原因。在我们的示例中，O2'是通过对给定O1的O2进行转换计算得出的，在本例中，它将要删除的字符的位置修正为3，因为之前的操作O1在更早的位置插入了一个字符。

尽管在我们给出的例子中，应用转换函数看起来相当简单，但要证明给定转换函数的正确性却非常困难。[4] 已发表论文中的证明后来被发现是错误的，而且OT算法也被证明很难实现。然而，目前有一种OT的替代方案正在积极研究中：无冲突复制数据类型。

无冲突复制数据类型

无冲突复制数据类型 (CRDT) [5] 是一种数据结构，它无需手动解决冲突即可在并发应用程序中进行复制。根据实现方式的不同，更新可以以增量（对应于 OT 中的操作）的形式发送，也可以通过共享完整状态的方式发送。如果客户端通信频繁，则仅共享单个操作会更高效。但是，如果通信通过非常不可靠的网络进行，例如移动网络或卫星网络，则偶尔发送完整的 CRDT 可能是一个更好的选择。

CRDT 的主要思想与 OT 类似。区别在于，客户端无需转换传入的消息，因为消息中已经包含了解决与本地状态冲突所需的所有信息。而在 OT 中，客户端必须显式地记住之前的操作，然后根据这些历史记录转换新的操作；CRDT 则在数据结构中持久化了足够的信息，从而创建无需任何转换即可合并的操作。

回顾上一节的协作文本编辑器示例，我们可以使用所谓的序列 CRDT。复制可增长数组 (RGA) [6] 就是一个例子，我们现在将仔细研究它。我是在观看一个关于 JSON CRDT [7] 的会议演讲时偶然发现它的。

下图展示了我们的两个客户端如何同时修改文档“abc”。但这次我们并非将文档表示为简单的字符串，而是在每个位置添加一个唯一标识符。该标识符（例如A1 ）由全局唯一的客户端标识符 ( A ) 和客户端唯一的数字标识符 ( 1 )组成。

当客户端执行操作时，它可以通过标识符而非位置来引用字符。由于标识符是唯一的，即使在此期间发生了并发修改，该操作在被其他客户端接收时仍然有效。如果客户端A告诉B它在A0之后插入了“x”，B就知道应该插入到哪个位置。删除操作也以类似的方式进行，但我们实际上并没有从数据结构中删除字符，而只是用所谓的“墓碑标记”将其标记为已删除。

还有两个悬而未决的问题：我们如何分配新的标识符，以及如何处理在同一位置同时插入两个数据的情况？

新标识符的生成方式如下：每个客户端都会记录与其客户端 ID 关联的最高数字标识符。每当它插入一个新字符时，它都会递增该最高数字标识符，并分配一个由其自身客户端 ID 和递增后的数字组成的新标识符。

在同一位置同时插入数据需要以一种能够产生一致结果的方式来处理。假设A和B都想在A0之后分别插入“x”和“y”。如果我们不加任何特殊规则地执行这些操作，A最终会得到“xyabc”，而B会得到“yxabc”。由于没有绝对正确的答案，关键在于确保所有客户端都使用同一个版本。为了实现这一点，我们只在下一个位置没有更大标识符的情况下才在请求的位置插入数据。否则，我们会继续向右移动，直到找到一个更小的标识符并插入到该位置。因为B4 > A4，所以最终的文档将是“yxabc”。

除了 RGA 之外，还有许多其他 CRDT 可供您使用。例如， Akka 分布式模块提供了基于 CRDT 的计数器、集合和映射，并在 Akka 集群模式下使用时提供不同的一致性保证。Redis企业版提供了一种基于 CRDT 的复制架构。自 2.0 版本起，Riak 的产品组合中也包含了基于 CRDT 的类型。

然而，CRDT并非万能灵药。它们只适用于特定类型的问题，并且由于需要在数据结构中跟踪足够的历史信息以合并传入的操作或状态，因此会带来额外的存储开销。

结论

我们已经看到，分布式系统面临着诸多挑战。由于节点间通信的不可靠性，分布式系统中的并发问题更难处理。如果两个进程同时修改同一资源，就会发生冲突。

为了解决冲突，我们可能需要先检测冲突。这可以通过跟踪某种形式的历史记录来实现。一旦检测到冲突，我们可以选择自动解决，或者将冲突解决委托给下一层级，例如应用程序代码或用户。虽然丢弃除一个冲突写入之外的所有冲突写入是一种常用技术，但这会导致数据丢失。

存在一些承诺不丢失数据的自动冲突解决技术，例如OT或CRDT。然而，我们并非免费就能获得这些优势。OT的推理和正确实现都比较困难。CRDT由于需要在数据结构中显式存储一些历史信息，因此内存开销较大。遗憾的是，OT和CRDT都仅适用于特定的问题集，没有万能的解决方案。

你之前用过OT或CRDT吗？你是否曾经在不知情的情况下丢失过数据，因为你的应用程序使用了LWW来解决冲突？请在评论区分享你的想法。

参考

• [1] Colin J. Fidge (1988 年 2 月)。“消息传递系统中保持偏序关系的时间戳”（PDF）。载于 K. Raymond (编)。第 11 届澳大利亚计算机科学会议 (ACSC'88) 会议录。第 56–66 页。检索日期：2009 年 2 月 13 日。
• [2] Mattern, F. (1988 年 10 月)，“分布式系统的虚拟时间和全局状态”，载于 Cosnard, M.，《并行与分布式算法研讨会论文集》，法国 Chateau de Bonas：Elsevier，第 215-226 页。
• [3] Ellis, CA; Gibbs, SJ (1989). “群件系统中的并发控制”。ACM SIGMOD Record. 18 (2): 399–407。
• [4] 杜莉 & 瑞莉 (2010). “基于可采纳性的协同编辑系统操作转换框架”。19 (1): 1–43。
• [5]马克·夏皮罗；普雷吉萨、努诺；巴克罗，卡洛斯； Zawirski, Marek (2011)，无冲突复制数据类型，计算机科学讲义，6976（Proc 第 13 届国际研讨会，SSS 2011），格勒诺布尔，法国：Springer Berlin Heidelberg，第 386-400 页
• [6] Roh, HG, Jeon, M., Kim, JS 和 Lee, J., 2011. 复制的抽象数据类型：协作应用程序的构建模块。并行与分布式计算杂志，71(3)，第 354-368 页。
• [7] Kleppmann, M. 和 Beresford, AR, 2017. 无冲突复制 JSON 数据类型。IEEE 并行与分布式系统汇刊，28(10)，第 2733-2746 页。

如果你喜欢这篇文章，可以在 ko-fi 上支持我。