Google文档如何处理编辑冲突？

Question

我一直在编写自己的Javascript编辑器,其功能类似于Google Docs(允许多人同时处理它).有一点我不明白:

假设您已将用户A和用户B直接相互连接,网络延迟为10毫秒.我假设编辑器使用diff系统(据我理解Docs),其中编辑表示为"在索引3处插入'文本',并且差异被加时间戳并强制按时间顺序应用于所有客户端.

让我们从包含文本的文档开始:"xyz123"

用户A在时间戳001ms处在文档的开头键入"abc",而用户B在时间戳005ms处在"xyz"和"123"之间键入"hello".

两个用户都希望结果是:"abcxyzhello123",但考虑到网络延迟:

• 用户B将在时间011ms接收用户A对"在索引0处插入'abc'的编辑.为了保持按时间顺序排列,用户B将在索引3处撤消用户B的插入,在索引0处插入用户A的"abc",然后在索引3处重新插入用户B的插入,该索引现在位于"abc"和"xyz之间" ,"因此给"abchelloxyz123"
• 用户A将在时间015ms接收用户B对"在索引3处插入'hello'的编辑.它会认识到用户B的插入是在用户A之后完成的,只需在索引3处插入"hello"(现在在"abc"和"xyz"之间),给出"abchelloxyz123"

当然," abchello xyz123"与" abc xyz hello 123"不一样

除了字面上为每个角色分配自己的唯一ID之外,我无法想象Google将如何有效地解决这个问题.

我想到的一些可能性:

• 跟踪插入点而不是使用差异发送索引将起作用,但如果用户B在编辑之前移动了1ms的插入点,则会遇到完全相同的问题.
• 您可以让用户B使用他的差异发送一些信息,例如"在'xyz'之后插入'",这样用户A就可以智能地识别出这种情况,但是如果用户A插入文本"xyz？"该怎么办？
• 用户B可以识别出这种情况发生了(当它收到用户A的差异并发现它是冲突时),然后发出一个diff撤消用户B的编辑和一个新的差异,它进一步插入用户B的"你好""abc".length索引对.这个问题是(1)用户A会在文本中看到"跳跃",(2)如果用户A继续编辑,则用户B必须不断修复其差异 - 即使"修复者"差异也会关闭并需要修复,指数增加复杂性.
• 用户B可以发送一个属性,它接收到的最后一个时间戳差异是-005ms或者其他东西,然后A可以识别B不知道它的变化(因为A的差异在001ms)然后进行冲突解决.问题是(1)所有用户的时间戳都会稍微偏离,因为大多数计算机时钟都不准确到ms;(2)如果第三个用户C的用户A延迟25ms,但用户B滞后2ms,用户C在-003ms之间在"x"和"y"之间添加一些文本,然后用户B将用户C的编辑作为参考点,但是用户A不会知道用户C的编辑(以及用户B的参考点)直到22ms.我相信如果您使用通用服务器为所有编辑加时间戳,这可以解决,但这似乎相当复杂.
• 你可以给每个角色一个唯一的ID,然后处理那些ID而不是索引,但这似乎有点过分......

我正在阅读http://www.waveprotocol.org/whitepapers/operational-transform,但很想听到解决这个问题的所有方法.

Answer 1

实现并发更改副本有不同的可能性,具体取决于场景的拓扑结构和不同的权衡.

使用中央服务器

最常见的情况是所有客户端都必须与之通信的中央服务器.

服务器可以跟踪每个参与者的文档的外观.然后,A和B都会将更改发送到服务器.然后,服务器将更改应用于相应的跟踪文档.然后它将执行三向合并并将更改应用于主文档.然后,它将主文档和跟踪文档之间的差异发送到相应的客户端.这称为差分同步.

另一种方法称为操作(al)转换,类似于传统版本控制系统中的rebase.它不需要中央服务器,但是如果你有超过2个参与者,那么让它变得更容易(参见OT常见问题解答).要点是您在一次编辑中转换更改,以便编辑假定已经发生了另一次编辑的更改.例如,将变换B的编辑insert(3, hello)针对其编辑insert(0, abc)与结果insert(6, hello).

变基和OT之间的区别在于,如果您在不同的顺序中应用编辑,则变基不能保证一致性(例如,如果B要反过来反对A的编辑,则可能导致文档状态不同).另一方面,OT的承诺是允许任何顺序,如果你做正确的转换.

没有中央服务器

存在可以处理对等场景的OT算法(在控制层上增加的实现复杂性和增加的存储器使用的权衡).可以使用版本矢量来跟踪编辑所基于的状态,而不是简单的时间戳.然后(取决于OT算法的功能,特别是转换属性2),可以转换传入的编辑以适应它们的接收顺序,或者可以使用版本向量对编辑强加部分顺序 - 在此通过撤消和转换编辑,需要"重写"案例历史记录,以便它们遵守版本向量强加的顺序.

最后,有一组算法称为CRDT,WOOT,treedoc和logoot,它们试图通过特殊设计的数据类型来解决问题,这些数据类型允许操作通勤,因此它们的应用顺序无关紧要(这是类似的你想到每个角色的身份证明.这里的权衡是内存消耗和操作构建的开销.