algorithm - Google Docs 如何处理编辑冲突？

Question

我一直在尝试编写自己的 Javascript 编辑器，其功能类似于 Google Docs(允许多人同时处理)。我不明白的一件事:

假设您已经让用户 A 和用户 B 直接相互连接，网络延迟为 10 毫秒。我假设编辑器使用差异系统(正如我理解的 Docs 所做的那样)，其中编辑表示为“在索引 3 处插入'文本'”，并且差异带有时间戳并强制由所有客户端按时间顺序应用。

让我们从包含以下文本的文档开始:“xyz123”

用户 A 在文档开头的时间戳 001ms 处键入“abc”，而用户 B 在时间戳 005ms 处在“xyz”和“123”之间键入“hello”。

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

用户 B 将在 011 毫秒时收到用户 A 对“在索引 0 处插入 'abc'”的编辑。为了保持时间顺序，用户 B 将撤消用户 B 在索引 3 处的插入，在索引 0 处插入用户 A 的“abc”，然后在索引 3 处重新插入用户 B 的插入，现在位于“abc”和“xyz”之间, 从而给出 "abchelloxyz123"

用户 A 将在 015 毫秒时收到用户 B 对“在索引 3 处插入 'hello'”的编辑。它将识别出用户 B 的插入是在用户 A 之后完成的，并且只需在索引 3 处插入“hello”(现在在“abc”和“xyz”之间)，给出“abchelloxyz123”

当然，“abchello xyz123”与“abc xyz 你好123”是不一样的

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

我想到的一些可能性:

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

您可以让用户 B 发送一些带有他的差异的信息，例如“在 'xyz' 之后插入”，以便用户 A 可以智能地识别这已经发生，但是如果用户 A 插入文本“xyz”怎么办？

用户 B 可以识别这已经发生(当它接收到用户 A 的 diff 并看到它是冲突时)，然后发送一个 diff 撤消用户 B 的编辑和一个插入用户 B 的 "hello""abc".length 索引的新 diff对。这样做的问题是(1)用户 A 会在文本中看到“跳转”，并且(2)如果用户 A 继续编辑，那么用户 B 将不得不不断修复其差异 - 即使“修复器”差异也会关闭并需要修复，成倍增加复杂性。

用户 B 可以连同它的 diff 一起发送一个属性，它收到的最后一个时间戳 diff 是 -005ms 或其他东西，然后 A 可以识别 B 不知道它的变化(因为 A 的 diff 是在 001ms)然后进行冲突解决。问题是(1)考虑到大多数计算机时钟不精确到毫秒，所有用户的时间戳都会略有偏差；(2)如果有第三个用户 C 与用户 A 有 25 毫秒的延迟，但与用户 B 有 2 毫秒的延迟，并且用户 C 在 -003ms 在“x”和“y”之间添加了一些文本，然后用户 B 将使用用户 C 的编辑作为引用点，但用户 A 不知道用户 C 的编辑(因此用户 B 的引用点)直到 22 毫秒。我相信如果您使用通用服务器为所有编辑添加时间戳，则可以解决此问题，但这似乎相当复杂。

你可以给每个角色一个唯一的 ID，然后使用这些 ID 而不是索引，但这似乎有点矫枉过正...

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

Answer 1

根据场景的拓扑和不同的权衡，实现副本的并发更改有不同的可能性。

使用中央服务器

最常见的场景是所有客户端都必须与之通信的中央服务器。

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

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

rebase 和 OT 之间的区别在于，如果您以不同的顺序应用编辑， rebase 并不能保证一致性(例如，如果 B 将 A 的编辑与他们的编辑相反，这可能导致文档状态不同)。另一方面，OT 的 promise 是，如果您进行正确的转换，则允许任何顺序。

没有中央服务器

存在可以处理点对点场景的 OT 算法(在控制层上增加实现复杂性和增加内存使用量之间进行权衡)。 Version vector 而不是简单的时间戳可用于跟踪编辑所基于的状态。然后(取决于您的 OT 算法的能力，特别是转换属性 2)，可以转换传入的编辑以适应它们接收到的顺序，或者可以使用版本向量对编辑施加部分顺序 - 在这个案例历史需要通过撤消和转换编辑来“重写”，以便它们遵守版本向量强加的顺序。

最后，还有一组基于CRDT的算法。 ，称为 WOOT、Treedoc 或 Logoot，它们试图使用允许操作通勤的特殊设计的数据类型来解决问题，因此它们的应用顺序无关紧要(这类似于您对每个字符的 ID 的想法)。这里的权衡是内存消耗和操作构建的开销。