在具有多个主节点（在本文中，主节点是指接受数据更改请求的节点）的环境中的自动冲突解决是一个非常有趣的研究领域。 取决于应用程序，有几种不同的方法和算法，本文将讨论用于解决协作编辑应用程序（例如Google Docs和Etherpad）中的冲突的操作转换（OT）技术。

1.简介

从技术角度来看，协作是困难的，因为几个人可以在几乎相同的时间点对同一段文本进行不同的更改。 由于通过Internet的数据传输不是即时的（光纤中的数据传输速度有局限性），因此每个客户端都使用已编辑文档的本地版本（副本）来模拟即时响应，该响应可能与其他参与者的版本不同。 而且主要的目的是确保本地版本之间的一致性 ，换句话说，如何确保所有本地版本迟早收敛到同一文档的正确版本中（我们不能要求所有客户端由于编辑过程可能是无止境的，因此有些时间同时具有相同的版本。

旧版本的Google文档

最初，Google Docs与许多其他协作式文档编辑应用程序一样，使用了文档不同版本内容的简单比较。 假设我们有两个客户端-Petya和Vasya，并且文档的当前状态在它们之间同步。 在旧版的Google服务器中，一旦收到Petya的更新，它就会计算出其版本与自己版本之间的差异（diff），并尝试以最佳方式将两个版本合并为一个。 然后，服务器将收到的版本发送给Vasya。 如果Vasya有未发送到服务器的任何更改，则重复此过程-您需要将服务器中的版本与本地Vasina合并，然后将其发送回服务器。

通常，这种方法效果不佳。 例如，假设Petya，Vasya和服务器以带有文本“ The quick brown fox ”的同步文档开始。


Petya用粗体突出显示了棕色狐狸一词，而Vasya用dog代替了狐狸一词。 首先让Petina更改为服务器，然后他发送Vasya的更新版本。 很明显，最终结果应该是The quick brown dog ，但是没有足够的信息可供合并算法理解，选项the quick brown fox dog ， quick brown dog ， quick brown dog fox是绝对正确的。 （例如，在这种情况下的git中，您将发生合并冲突，因此必须亲自进行统治）。 这是这种方法的主要问题-如果仅依靠文档的内容，将无法确定合并的结果。

您可以尝试改善这种情况，并阻止其他参与者编辑某人已经统治的文本部分的能力。 但这不是我们想要的-这种方法只是试图通过恶化用户体验来避免解决技术问题，而且还可能存在两个参与者同时开始编辑同一句子的情况-然后其中一个参与者要么丢失更改，要么否则，如果发生上述冲突，他将不得不手动组合更改。

新版本的Google文档

在新版Google文档中，使用了一种完全不同的方法：将文档存储为一系列更改，而不是比较内容，而是按顺序滚动更改（以下称为顺序关系 ）。 了解用户如何修改文档并考虑其意图后，我们可以在组合所有编辑后正确确定最终版本。

好的，现在我们需要了解何时应用更改-我们需要一个协作协议 。

在Google文档中，所有文档编辑都归结为三个不同的操作 ：

• 文字插入
• 删除文字
• 将样式应用于文本

因此，当您编辑文档时，所有操作都完全存储在此操作集中，并将它们添加到更改日志的末尾。 显示文档时，将使用记录的操作执行更改日志。

一句话：最早支持OT的（公开）Google产品显然是Google Wave。 他支持范围广泛的行动。

例子

让Petya和Vasya从“ HABR 2017”的同一状态开始。
Petya将2017年更改为2018年，实际上创建了2个操作：


同时，Vasya将文本更改为“ HELLO HABR 2017”：


Vasya收到Petin的删除操作，如果他只是将其应用，则将获得错误的文本（应该删除数字7）：


为了避免这种情况，Vasya必须根据他当前的本地更改来转换 Petin的操作（换句话说，该操作是上下文相关的）：

$$

$$\ {删除\ \ @ 8 \} \ rightarrow \ {删除\ \ @ 15 \}$$

更正式地说，请考虑以下示例：


然后：

$$

$$O1’（O2（X））= O2’（O1（X））$$

瞧！ 所描述的算法称为运算变换。

2.运营转型

一致性模型

为了确保一致性，已经开发了几种一致性模型 ，请考虑其中一种-CCI。

CCI模型提供三个属性：

1. 收敛：完成所有操作后，公共文档的所有副本必须相同：
   
   
   
   在此示例中，两个用户都从相同的副本开始。 然后，他们更改文档，而副本则发散-通过这种方式，可以缩短响应时间。 将本地更改发送给其他客户端后，convergence属性要求所有客户端的文档最终状态必须相同。
2. 意图保留：操作的意图必须存储在所有副本上，而不管它是否重叠以同时执行多个操作。 操作的意图定义为执行对创建副本的影响。
   
   考虑一个该属性失败的示例：
   
   
   
   
   两个客户端都从相同的副本开始，然后都进行更改。 对于Petya，其操作的意图是在第一个索引上插入“ 12”，对于Vasya，删除具有索引2和3的字符。与Petya Vasino同步后，该意图和Vasya Petino的意图被违反。 另请注意，副本已发散，但这不是所讨论属性的要求。 建议使用正确的最终版本以将读者识别为一个小练习。
   
3. 因果关系保留：操作必须按因果关系顺序执行（基于之前发生的关系）。
   
   考虑一个该属性失败的示例：
   
   
   
   
   如您所见，Petya将文件的更改发送给Vasya和Agent Smith，Vasya首先收到了该文件，并删除了最后一个字符。 由于网络滞后，Smith接受了Vasin的第一个操作，以删除尚不存在的字符。
   
   OT无法确保满足因果关系保留属性；因此，将矢量时钟等算法用于这些目的。
   

OT设计

OT系统的设计策略之一是分为三个部分：

• 转换控制算法：确定何时准备转换操作（目标），关于应执行转换的操作（参考）以及执行顺序的顺序。
• 转换功能：转换目标操作，同时考虑参考操作的影响。
• 转换的要求和属性（属性和条件）：提供这些组件之间的连接并进行正确性检查。

转换功能

转换函数可以分为两种类型：

• 包含/正向转换：转换操作 $$$O_a$ 手术前 $$$O_b$ 这样的效果 $$$O_b$ （例如，两个插入）
• 排除/向后转换：操作的转换 $$$O_a$ 手术前 $$$O_b$ 这样的效果 $$$O_b$ 排除（例如，删除后插入）

符号插入/删除操作的示例（i-插入，d-删除）：

Tii(Ins[p1, c1], Ins[p2, c2]) { if (p1 < p2) || ((p1 == p2) && (order() == -1)) // order() –   return Ins[p1, c1]; // Tii(Ins[3, 'a'], Ins[4, 'b']) = Ins[3, 'a'] else return Ins[p1 + 1, c1]; // Tii(Ins[3, 'a'], Ins[1, 'b']) = Ins[4, 'a'] } Tid(Ins[p1, c1], Del[p2]) { if (p1 <= p2) return Ins[p1, c1]; // Tid(Ins[3, 'a'], Del[4]) = Ins[3, 'a'] else return Ins[p1 – 1, c1]; // Tid(Ins[3, 'a'], Del[1]) = Ins[2, 'a'] } Tdi(Del[p1], Ins[p2, c1]) { //   ,    } Tdd(Del[p1], Del[p2]) { if (p1 < p2) return Del[p1]; // Tdd(Del[3], Del[4]) = Del[3] else if (p1 > p2) return Del[p1 – 1]; // Tdd(Del[3], Del[1]) = Del[2] else return Id; // Id –   } 

3. Google文档中的交互协议

让我们更详细地了解Google Docs中的交互协议。 假设我们有一个服务器Petya和Vasya，并且它们具有空文档的同步版本。

每个客户都记住以下信息：

• 从服务器收到的最后更改的版本（id，修订版）。
• 所有在本地进行但未发送到服务器的更改（正在发送）
• 所有在本地进行的更改均发送到服务器，但未经服务器确认。
• 用户看到的文档的当前状态。

服务器依次记住：

• 所有已收到但未处理的更改的列表（待处理）。
• 所有已处理更改的完整历史记录（修订日志）。
• 上次处理的更改时文档的状态。

因此，Petya在文档开头以单词“ Hello”开头：


客户端首先将此更改添加到等待列表，然后将其发送到服务器，并将更改移至已发送列表。

Petya继续输入，并已添加单词“ Habr”。 同时，Vasya键入“！” 在他的空文件（他尚未收到Petina的更改）中。


佩蒂诺 $$$\ {插入\ \'Habr'，\ @ 5 \}$ 已被添加到待处理列表中，但尚未发送，因为我们一次发送的更改不止一个，并且尚未确认前一个更改 。 我们还注意到服务器将Petit的更改保存在其修订日志中。 然后，服务器将它们发送给Vasya，并向Petya发送确认消息（表明Petina的首次更改已成功处理）


Vasya的客户端从服务器接收Petina的更改，并对其未完成的发送应用OT到服务器 $$$\ {插入\ \'！'，\ @ 0 \}$ 。 结果是插入索引从0更改为5。我们还注意到，两个客户端都将服务器上次同步修订的版本号更新为1。最后，Petin客户端从服务器的挂起确认列表中删除了相应的更改。

然后Petya和Vasya将他们的更改发送到服务器。


服务器在Vasinykh之前（关于输入的订单）收到Petina的更改，因此他首先处理了这些更改，并将确认发送给Petya。 他还将它们发送给Vasya，并且他的客户将其转换为尚未确认的更改 $$$\ {插入\ \'！'，\ @ 5 \}$ 。

接下来是重点。 服务器开始处理Vasya的更改，根据Vasya的说法，其修订号为2。但是服务器已经在编号2上提交了更改，因此它将转换应用于Vasya客户端尚不知道的所有更改 （在这种情况下-- $$$\ {插入\ \'Habr'，\ @ 5 \}$ ），并将结果保存在数字3中。


我们可以看到，Vasin的更改索引增加了5，以适应Petin的文本。

Petya的过程已完成，Vasya需要从服务器接收新更改并发送确认。

4. Etherpad

让我们看一下使用OT的另一个类似应用程序-在线编辑器与etherether.org共同编辑的开源项目

在Etherpad中，转换功能略有不同-更改作为一组更改（changeset）发送到服务器，定义为

$$

$$（\ ell_1 \ rightarrow \ ell_2）[c_1，c_2，c_3，...]，$$

在哪里

• $$$\ ell_1$ ：编辑前文档的长度。
• $$$\ ell_2$ ：编辑后文档的长度。
• $$$c_1，c_2，c_3，...$ -编辑后文件的描述。 如果 $$$c_i$ 是一个数字（或一个数字范围），则这些是原始文档的字符索引，在编辑（保留）后将保留该字符，如果 $$$c_i$ -一个字符（或字符串），则为插入。
  
  一个例子：
  
  
  1. $$$ inline $``“ + \（0 \ rightarrow 6）[``Hello”] =``你好“ $ inline $
  2. $$$ inline $``Beaver” +（4 \ rightarrow 4）[``Ha“，\ 2-3] =``哈伯'$ inline $
  
  

正如您已经了解的那样，最终文档是作为对空文档应用的一系列此类更改而形成的。

请注意，我们不能仅仅应用其他参与者的更改（原则上，这在Google文档中是可能的），因为文档的总长度可以不同。
例如，如果源文档的长度为n，则我们有两个更改：

$$

$$A =（n \ rightarrow n_a）[\ cdots] \\ B =（n \ rightarrow n_b）[\ cdots]，$$

然后 $$$A（B）$ 不可能，因为 $$需要文件长度 $$$n$ 和之后 $$$B$ 他会很长 $$$n_b$ 。
为了解决这种情况，Etherpad使用了一种合并机制：它是一个由表示的功能 $$$m（A，B）$ ，接受对文档相同状态下的输入的两次更改（以下称为 $$$X$ ）并进行新的更改。

要求

$$

$$m（A，B）= m（B，A）$$

请注意，对于有变化的客户 $$谁收到了零钱 $$$B$ 计算没有任何意义 $$$m（A，B）$ 从 $$$m（A，B）$ 适用于 $$$X$ 和 $$当前状态 $$$A（X）$ 。 实际上，我们需要计算 $$$A’$ 和 $$$B’$ 这样

$$

$$B’（A（X））= A’（B（X））= m（A，B）（X）$$

函数计算 $$$A’$ 和 $$$B’$ 称为跟随，并定义如下：
$$$f（A，B）（A）= f（B，A）（B）= m（A，B）= m（B，A）$
施工算法 $$$f（A，B）$ 以下：

• A中的插入变为A中的索引 $$$f（A，B）$
• B中的插入变为 $$$f（A，B）$
• A和B中的匹配索引会延续到 $$$f（A，B）$

一个例子：

$$$$显示$$ X =（0 \ rightarrow 8）[``棒球]] \\ A =（8 \ rightarrow 5）[0-1，``si'，7] \ / \！\！/ == ``罗勒''\\ B =（8 \ rightarrow 5）[0，``e''，6，6，``ow“] \ / \！\ !! / ==``below” $$显示$$

我们计算：

$$

$$A'= f（B，A）=（5 \右箭头6）[0，1，``si“，3，4] \\ B'= f（A，B）=（5 \右箭头6）[ 0，“ e”，2、3，“ ow”] \\ m（A，B）= m（B，A）= A（B'）= B（A'）=（8 \右箭头6）[ 0，``esiow“] \\ $$

计算 $$$m（A，B）（X）$ 作为练习提供。

交互协议本质上与Google Docs相同，除非计算复杂一点。

5.对旧约的批评

• 就编程而言，实现OT是一项非常困难的任务。 引自维基百科 ：Share.JS库的开发人员，前Google Wave工程师约瑟夫·温特尔（Joseph Gentle）说：“不幸的是，实现OT很烂。 有上百万种算法具有不同的权衡取舍，大部分被困在学术论文中。 要正确实现这些算法确实非常困难且耗时。 [...] Wave花了2年时间写，如果今天重写，第二次写几乎要花时间。”
  
  （不幸的是，编写OT非常困难。有上百万种算法各有利弊，但其中大多数只是学术研究。这些算法实际上非常复杂，需要大量时间才能正确实施。[...]我们花了两年时间写Wave，如果我们今天不得不再次写它，那么我们将花费相同的时间）
  
• 您必须绝对保存对文档的所有更改
  

6.参考

• 组件系统中的并发控制
• 新版Google文档有何不同：一起工作，甚至彼此分开
• 新版Google文档的不同之处：冲突解决
• 了解和应用运营转型
• 维基百科：运营转型
• Jupiter协作系统中的高延迟，低带宽窗口
• 新版Google文档有何不同：快速协作
• 实时组编辑器中的操作转换：问题，算法和成就
• Etherpad和EasySync技术手册
• Google TechTalk：设计实时协作编辑系统的问题和经验
• 运营转型常见问题与解答