谷歌文档如何处理编辑冲突？

Question

我一直在尝试编写自己的JavaScript编辑器，具有类似Google Docs的功能（允许多个人同时使用）。 我不明白其中一件事：假设您有用户A和用户B，它们之间的网络延迟为10毫秒。我假设编辑器使用差异系统（就像我理解Docs所做的那样），其中编辑内容表示为“在索引3处插入'text'”，并且所有客户端都按时间戳强制按顺序应用差异。让我们从包含文本“xyz123”的文档开始。用户A在时间戳001ms处在文档开头键入“abc”，而用户B在时间戳005ms之间在“xyz”和“123”之间键入“hello”。两个用户都希望结果是：“abcxyzhello123”，但考虑到网络延迟：

• 用户B在011ms时间接收到了用户A在索引0插入"abc"的编辑。为了保持时间顺序，用户B会撤销自己在索引3插入的内容，将用户A的"abc"插入到索引0，然后重新在索引3插入自己的内容，此时在"abc"和"xyz"之间插入了用户B的内容，从而得到"abchelloxyz123"
• 用户A在015ms时间接收到了用户B在索引3插入"hello"的编辑。它会意识到用户B的插入是在自己之后完成的，然后将"hello"插入到索引3（现在在"abc"和"xyz"之间），得到"abchelloxyz123"

当然，"abchelloxyz123"和"abcxyzhello123"是不同的。

除了为每个字符分配独特的ID之外，我无法想象Google如何有效地解决这个问题。

我想到了一些可能性：

跟踪插入点而不是发送差异的索引会起作用，但是如果用户B在编辑之前1毫秒移动了他的插入点，则会遇到完全相同的问题。

您可以让用户B在其差异中发送一些信息，例如“在'xyz'之后插入”，以便用户A能够智能地识别发生了什么，但是如果用户A插入文本“xyz?”呢？

用户B可以识别这种情况（当它收到用户A的差异并看到它是一个冲突时），然后发送一个撤消用户B的编辑和一个新的差异，将用户B的“hello”“abc”。长度索引进一步向右。问题在于（1）用户A会看到文本中的“跳跃”，（2）如果用户A继续编辑，则用户B必须不断修复其差异 - 即使是“修复者”差异也会出错并需要修复，指数级增加复杂性。

用户B可以在其差异中发送一个属性，即其收到的最后一个时间戳的差异为-005ms或其他值，然后A可以识别B不知道其更改（因为A的差异为001ms），然后进行冲突解决。问题是（1）考虑到大多数计算机时钟不准确到毫秒，所有用户的时间戳都会略有偏差，（2）如果有第三个用户C与用户A的滞后为25ms但与用户B的滞后为2ms，则用户C在-003ms之间添加一些文本“x”和“y”，则用户B将使用用户C的编辑作为参考点，但是用户A直到22ms才会知道用户C的编辑（因此也不知道用户B的参考点）。我认为如果您使用一个共同的服务器来为所有编辑打上时间戳，这个问题可以解决，但这似乎相当复杂。

您可以为每个字符分配一个唯一的ID，然后根据这些ID工作，而不是根据索引，但这似乎有些过度了...

我正在阅读http://www.waveprotocol.org/whitepapers/operational-transform，但希望听到任何和所有解决这个问题的方法。

- MatthewSot

---

被接受的答案的视觉展示：https://www.youtube.com/watch?v=S2Hp_1jqpY8 - Mr Matrix

Answer 1

针对并发副本的实现有不同的可能性，具体取决于情景拓扑以及不同的权衡。

使用中央服务器

最常见的情况是一个中央服务器，所有客户端都需要与其通信。

服务器可以跟踪每个参与者文档的外观。 A和B都向服务器发送其更改的差异。 然后服务器会将更改应用于各自的跟踪文档。然后它会执行三路合并，并将更改应用于主文档。然后，它将向各客户端发送主文档和跟踪文档之间的差异，这称为differential synchronization。

一种不同的方法称为操作转换（Operation Transformation，简称OT），类似于传统版本控制系统中的变基。它不需要中央服务器，但如果参与者超过2个，则拥有一个中央服务器会使事情变得更加容易（请参见OT FAQ）。其要点是，您可以转换一个编辑中的更改，以便该编辑假定另一个编辑的更改已经发生。例如，A将通过对其编辑insert(0, abc) 进行转换，使B的编辑insert(3, hello) 得到结果insert(6, hello)。

变基和OT之间的区别在于，如果按不同顺序应用编辑，则变基不能保证一致性（例如，如果B反向变基A的编辑，则可能导致文档状态分歧）。另一方面，OT的承诺是允许任何顺序，只要进行正确的转换。

无中央服务器

OT算法可以处理点对点场景（但这会增加控制层的实现复杂度和内存使用量），可以使用版本向量来跟踪编辑所基于的状态，而不是简单的时间戳。然后（根据您的OT算法能力，特别是变换属性2），传入的编辑可以被转换以适应它们接收到的顺序，或者版本向量可以用来对编辑强加部分顺序——在这种情况下，需要“重写”历史记录，通过撤消和转换编辑，使其遵循版本向量强加的顺序。

最后，还有一组基于CRDT的算法，称为WOOT、Treedoc或Logoot，它们尝试通过专门设计的数据类型来解决问题，允许操作交换，因此它们被应用的顺序并不重要（这类似于每个字符的ID的想法）。这里的权衡是内存消耗和操作构造的开销。

- Marcel Klehr