在具有多个主节点(在本文中,主节点是指接受数据更改请求的节点)的环境中的自动冲突解决是一个非常有趣的研究领域。 取决于应用程序,有几种不同的方法和算法,本文将讨论用于解决协作编辑应用程序(例如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 \}
\ {删除\ \ @ 8 \} \ rightarrow \ {删除\ \ @ 15 \}
更正式地说,请考虑以下示例:
然后:
O1′(O2(X))=O2′(O1(X))
瞧! 所描述的算法称为运算变换。
2.运营转型
一致性模型
为了确保一致性,已经开发了几种
一致性模型 ,请考虑其中一种-CCI。
CCI模型提供三个属性:
- 收敛:完成所有操作后,公共文档的所有副本必须相同:
在此示例中,两个用户都从相同的副本开始。 然后,他们更改文档,而副本则发散-通过这种方式,可以缩短响应时间。 将本地更改发送给其他客户端后,convergence属性要求所有客户端的文档最终状态必须相同。 - 意图保留:操作的意图必须存储在所有副本上,而不管它是否重叠以同时执行多个操作。 操作的意图定义为执行对创建副本的影响。
考虑一个该属性失败的示例:
两个客户端都从相同的副本开始,然后都进行更改。 对于Petya,其操作的意图是在第一个索引上插入“ 12”,对于Vasya,删除具有索引2和3的字符。与Petya Vasino同步后,该意图和Vasya Petino的意图被违反。 另请注意,副本已发散,但这不是所讨论属性的要求。 建议使用正确的最终版本以将读者识别为一个小练习。
- 因果关系保留:操作必须按因果关系顺序执行(基于之前发生的关系)。
考虑一个该属性失败的示例:
如您所见,Petya将文件的更改发送给Vasya和Agent Smith,Vasya首先收到了该文件,并删除了最后一个字符。 由于网络滞后,Smith接受了Vasin的第一个操作,以删除尚不存在的字符。
OT无法确保满足因果关系保留属性;因此,将矢量时钟等算法用于这些目的。
OT设计
OT系统的设计策略之一是分为三个部分:
- 转换控制算法:确定何时准备转换操作(目标),关于应执行转换的操作(参考)以及执行顺序的顺序。
- 转换功能:转换目标操作,同时考虑参考操作的影响。
- 转换的要求和属性(属性和条件):提供这些组件之间的连接并进行正确性检查。
转换功能
转换函数可以分为两种类型:
- 包含/正向转换:转换操作 Oa 手术前 Ob 这样的效果 Ob (例如,两个插入)
- 排除/向后转换:操作的转换 Oa 手术前 Ob 这样的效果 Ob 排除(例如,删除后插入)
符号插入/删除操作的示例(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)发送到服务器,定义为
( ell1 rightarrow ell2)[c1,c2,c3,...],
在哪里
- ell1 :编辑前文档的长度。
- ell2 :编辑后文档的长度。
- c1,c2,c3,... -编辑后文件的描述。 如果 ci 是一个数字(或一个数字范围),则这些是原始文档的字符索引,在编辑(保留)后将保留该字符,如果 ci -一个字符(或字符串),则为插入。
一个例子:
- $ inline $``“ + \(0 \ rightarrow 6)[``Hello”] =``你好“ $ inline $
- $ inline $``Beaver” +(4 \ rightarrow 4)[``Ha“,\ 2-3] =``哈伯'$ inline $
正如您已经了解的那样,最终文档是作为对空文档应用的一系列此类更改而形成的。
请注意,我们不能仅仅应用其他参与者的更改(原则上,这在Google文档中是可能的),因为文档的总长度可以不同。
例如,如果源文档的长度为n,则我们有两个更改:
A=(n rightarrowna)[ cdots]B=(n rightarrownb)[ cdots],
然后
A(B) 不可能,因为
需要文件长度
n 和之后
B 他会很长
nb 。
为了解决这种情况,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.参考