Google Docs 如何处理编辑冲突？
How does Google Docs deal with editing collisions?
我一直在尝试编写自己的 Javascript 编辑器，其功能类似于 Google Docs（允许多人同时使用）。有一件事我不明白：
假设您让用户 A 和用户 B 直接相互连接，网络延迟为 10 毫秒。我假设编辑器使用差异系统（据我了解 Docs 所做的），其中编辑表示为 "insert 'text' at index 3," 并且差异带有时间戳并强制所有客户端按时间顺序应用。
让我们从包含文本的文档开始："xyz123"
用户 A 在时间戳 001 毫秒处在文档开头键入 "abc"，而用户 B 在时间戳 005 毫秒处在 "xyz" 和“123”之间键入 "hello"。
两个用户都希望结果是："abcxyzhello123," 然而，考虑到网络延迟：
- 用户 B 将在 011 毫秒时收到用户 A 对 "insert 'abc' at index 0" 的编辑。为了保持时间顺序，用户 B 将撤消用户 B 在索引 3 处的插入，在索引 0 处插入用户 A 的 "abc"，然后在索引 3 处重新插入用户 B 的插入，现在在 [=56= 之间] 和 "xyz," 从而得到 "abchelloxyz123"
- 用户 A 将在 015 毫秒时收到用户 B 对 "insert 'hello' at index 3" 的编辑。它会认识到用户 B 的插入是在用户 A 之后完成的，并且只需在索引 3 处插入 "hello"（现在在 "abc" 和 "xyz" 之间），给出 "abchelloxyz123"
当然，“abchelloxyz123”与“abcxyzhello[=45=”是不一样的]123
除了字面上为每个角色分配自己唯一的 ID 之外，我无法想象 Google 将如何有效地解决这个问题。
我想到的一些可能性：
- 跟踪插入点而不是发送带有差异的索引是可行的，但如果用户 B 在编辑前将其插入点移动 1 毫秒，您将遇到完全相同的问题。
- 您可以让用户 B 发送一些带有他的差异的信息，例如 "inserting after 'xyz'"，以便用户 A 可以智能地识别发生了这种情况，但是如果用户 A 插入文本 "xyz?"[=42 会怎样=]
- 用户 B 可以识别出发生了这种情况（当它收到用户 A 的差异并发现这是冲突时），然后发送一个差异以撤消用户 B 的编辑并发送一个新的差异以插入用户 B 的 "hello" "abc".length index 更右。这样做的问题是 (1) 用户 A 会在文本中看到 "jump" 并且 (2) 如果用户 A 继续编辑，那么用户 B 将不得不不断修复其差异 - 即使是 "fixer" 差异也会关闭并需要修复，以指数方式增加复杂性。
- 用户 B 可以连同它的差异一起发送 属性 它收到的最后一个带时间戳的差异是 -005 毫秒或类似的东西，然后 A 可以认识到 B 不知道它的变化（因为 A 的差异是在 001 毫秒）然后进行冲突解决。问题是 (1) 所有用户的时间戳都会稍微偏离，考虑到大多数计算机时钟不精确到 ms 和 (2) 如果有第三个用户 C 与用户 A 有 25 毫秒的滞后，但与用户 B 有 2 毫秒的滞后，并且用户 C 在 -003ms 在 "x" 和 "y" 之间添加一些文本，然后用户 B 将使用用户 C 的编辑作为参考点，但用户 A 不知道用户 C 的编辑（因此用户B 的参考点）直到 22ms。我相信如果您使用公共服务器为所有编辑添加时间戳，这可以解决，但这似乎相当复杂。
- 你可以给每个角色一个唯一的 ID，然后处理这些 ID 而不是索引，但这似乎有点过分了......
我正在通读 http://www.waveprotocol.org/whitepapers/operational-transform，但很想听听解决此问题的所有方法。
根据场景的拓扑结构和不同的权衡，实现副本的并发更改有不同的可能性。
使用中央服务器
最常见的场景是所有客户端都必须与之通信的中央服务器。
服务器可以跟踪每个参与者的文档的外观。然后 A 和 B 都将包含更改的差异发送到服务器。然后服务器会将更改应用于相应的跟踪文档。然后它将执行三向合并并将更改应用到主文档。然后它将主文档和跟踪文档之间的差异发送给各自的客户。这叫做differential synchronization.
另一种方法称为 operation(al) 转换，类似于传统版本控制系统中的 rebase。它不需要中央服务器，但如果您有超过 2 名参与者（请参阅 OT FAQ），拥有中央服务器会使事情变得容易得多。要点是您转换一次编辑中的更改，以便该编辑假定另一次编辑的更改已经发生。例如。 A 将根据 B 的编辑 insert(3, hello) 对其编辑 insert(0, abc) 进行转换，结果为 insert(6, hello).
变基和 OT 之间的区别在于，如果您以不同的顺序应用编辑，则变基不能保证一致性（例如，如果 B 将 A 的编辑与他们的编辑进行变基，这可能会导致文档状态不同） .另一方面，如果您进行正确的转换，OT 的承诺是允许任何顺序。
没有中央服务器
存在可以处理点对点场景的 OT 算法（需要权衡控制层实现复杂性的增加和内存使用量的增加）。代替简单的时间戳，Version vector 可用于跟踪编辑所基于的状态。然后（取决于你的 OT 算法的能力，特别是 transform 属性 2），传入的编辑可以被转换以适应它们被接收的顺序，或者版本向量可以用于对编辑施加部分顺序——在这种情况下，历史需要 "rewritten"，通过撤消和转换编辑，以便它们遵守版本向量施加的顺序。
最后，有一组基于 CRDT 的算法，称为 WOOT、Treedoc 或 Logoot，它们试图用允许操作交换的特殊设计的数据类型来解决问题，因此顺序它们的应用无关紧要（这类似于您对每个角色的 ID 的想法）。这里的权衡是内存消耗和操作构造的开销。
我一直在尝试编写自己的 Javascript 编辑器，其功能类似于 Google Docs（允许多人同时使用）。有一件事我不明白：
假设您让用户 A 和用户 B 直接相互连接，网络延迟为 10 毫秒。我假设编辑器使用差异系统（据我了解 Docs 所做的），其中编辑表示为 "insert 'text' at index 3," 并且差异带有时间戳并强制所有客户端按时间顺序应用。
让我们从包含文本的文档开始："xyz123"
用户 A 在时间戳 001 毫秒处在文档开头键入 "abc"，而用户 B 在时间戳 005 毫秒处在 "xyz" 和“123”之间键入 "hello"。
两个用户都希望结果是："abcxyzhello123," 然而，考虑到网络延迟：
- 用户 B 将在 011 毫秒时收到用户 A 对 "insert 'abc' at index 0" 的编辑。为了保持时间顺序，用户 B 将撤消用户 B 在索引 3 处的插入，在索引 0 处插入用户 A 的 "abc"，然后在索引 3 处重新插入用户 B 的插入，现在在 [=56= 之间] 和 "xyz," 从而得到 "abchelloxyz123"
- 用户 A 将在 015 毫秒时收到用户 B 对 "insert 'hello' at index 3" 的编辑。它会认识到用户 B 的插入是在用户 A 之后完成的，并且只需在索引 3 处插入 "hello"（现在在 "abc" 和 "xyz" 之间），给出 "abchelloxyz123"
当然，“abchelloxyz123”与“abcxyzhello[=45=”是不一样的]123
除了字面上为每个角色分配自己唯一的 ID 之外，我无法想象 Google 将如何有效地解决这个问题。
我想到的一些可能性：
- 跟踪插入点而不是发送带有差异的索引是可行的，但如果用户 B 在编辑前将其插入点移动 1 毫秒，您将遇到完全相同的问题。
- 您可以让用户 B 发送一些带有他的差异的信息，例如 "inserting after 'xyz'"，以便用户 A 可以智能地识别发生了这种情况，但是如果用户 A 插入文本 "xyz?"[=42 会怎样=]
- 用户 B 可以识别出发生了这种情况（当它收到用户 A 的差异并发现这是冲突时），然后发送一个差异以撤消用户 B 的编辑并发送一个新的差异以插入用户 B 的 "hello" "abc".length index 更右。这样做的问题是 (1) 用户 A 会在文本中看到 "jump" 并且 (2) 如果用户 A 继续编辑，那么用户 B 将不得不不断修复其差异 - 即使是 "fixer" 差异也会关闭并需要修复，以指数方式增加复杂性。
- 用户 B 可以连同它的差异一起发送 属性 它收到的最后一个带时间戳的差异是 -005 毫秒或类似的东西，然后 A 可以认识到 B 不知道它的变化（因为 A 的差异是在 001 毫秒）然后进行冲突解决。问题是 (1) 所有用户的时间戳都会稍微偏离，考虑到大多数计算机时钟不精确到 ms 和 (2) 如果有第三个用户 C 与用户 A 有 25 毫秒的滞后，但与用户 B 有 2 毫秒的滞后，并且用户 C 在 -003ms 在 "x" 和 "y" 之间添加一些文本，然后用户 B 将使用用户 C 的编辑作为参考点，但用户 A 不知道用户 C 的编辑（因此用户B 的参考点）直到 22ms。我相信如果您使用公共服务器为所有编辑添加时间戳，这可以解决，但这似乎相当复杂。
- 你可以给每个角色一个唯一的 ID，然后处理这些 ID 而不是索引，但这似乎有点过分了......
我正在通读 http://www.waveprotocol.org/whitepapers/operational-transform，但很想听听解决此问题的所有方法。
根据场景的拓扑结构和不同的权衡，实现副本的并发更改有不同的可能性。
使用中央服务器
最常见的场景是所有客户端都必须与之通信的中央服务器。
服务器可以跟踪每个参与者的文档的外观。然后 A 和 B 都将包含更改的差异发送到服务器。然后服务器会将更改应用于相应的跟踪文档。然后它将执行三向合并并将更改应用到主文档。然后它将主文档和跟踪文档之间的差异发送给各自的客户。这叫做differential synchronization.
另一种方法称为 operation(al) 转换，类似于传统版本控制系统中的 rebase。它不需要中央服务器，但如果您有超过 2 名参与者（请参阅 OT FAQ），拥有中央服务器会使事情变得容易得多。要点是您转换一次编辑中的更改，以便该编辑假定另一次编辑的更改已经发生。例如。 A 将根据 B 的编辑 insert(3, hello) 对其编辑 insert(0, abc) 进行转换，结果为 insert(6, hello).
变基和 OT 之间的区别在于，如果您以不同的顺序应用编辑，则变基不能保证一致性（例如，如果 B 将 A 的编辑与他们的编辑进行变基，这可能会导致文档状态不同） .另一方面，如果您进行正确的转换，OT 的承诺是允许任何顺序。
没有中央服务器
存在可以处理点对点场景的 OT 算法（需要权衡控制层实现复杂性的增加和内存使用量的增加）。代替简单的时间戳，Version vector 可用于跟踪编辑所基于的状态。然后（取决于你的 OT 算法的能力，特别是 transform 属性 2），传入的编辑可以被转换以适应它们被接收的顺序，或者版本向量可以用于对编辑施加部分顺序——在这种情况下，历史需要 "rewritten"，通过撤消和转换编辑，以便它们遵守版本向量施加的顺序。
最后，有一组基于 CRDT 的算法，称为 WOOT、Treedoc 或 Logoot，它们试图用允许操作交换的特殊设计的数据类型来解决问题，因此顺序它们的应用无关紧要（这类似于您对每个角色的 ID 的想法）。这里的权衡是内存消耗和操作构造的开销。