42

我一直在尝试编写自己的 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 hello 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，但很想听听解决此问题的所有方法。

4

1 回答 1

53

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

使用中央服务器

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

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

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

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

没有中央服务器

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

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

于 2016-04-01T21:33:05.457 回答