文档协同软件是如何解决编辑冲突的？
前言
本文将介绍在线协同文档编辑器是如何解决冲突的，大部分公司在解决冲突上目前用的都是 OT 算法，与之对应，也有一个 CRDT 算法实现。接下来，我们将深入这两种算法的实现及原理。
解决冲突的方案
在线协同文档编辑器通常使用不同的算法来解决冲突，具体算法取决于编辑器的实现和设计。以下是一些常见的解决冲突的算法：
- OT（Operational Transformation，操作转换）：这是一种常见的解决冲突的算法，用于实现实时协同编辑。OT算法通过将用户的编辑操作转换为操作序列，并在多个用户同时编辑时进行
操作转换，以确保最终的文档状态一致。 - CRDT（Conflict-free Replicated Data Type，无冲突复制数据类型）：
这是一种基于数据结构的解决冲突的算法，它允许多个用户在不同的副本上进行并发编辑，并最终将编辑结果合并为一致的文档状态。CRDT算法通过设计特定的数据结构和操作规则来实现冲突自由的复制。
这些算法都有各自的优缺点，并且在不同的场景和需求下可能更适合不同的编辑器实现。
接下来，我们先聊聊 OT 算法。
OT 算法
当多个用户同时编辑同一文档时，OT算法通过操作转换来保持文档状态的一致性。下面是一个简单的示例，帮助你理解OT算法的工作原理。
假设有两个用户 A 和 B 同时编辑一段文本，初始文本为 "Hello, world!"。
用户 A 在文本末尾添加了字符 " How are you?"。
用户 B 在文本末尾添加了字符 " I'm fine."。
在 OT 算法中，每个操作都由一个操作类型和操作内容组成。在这个例子中，添加字符操作的操作类型为 "insert"，操作内容为被插入的字符。
用户 A 的操作序列为：[insert(" How are you?")]
用户 B 的操作序列为：[insert(" I'm fine.")]
首先，服务器收到用户 A 的操作序列，将其应用到初始文本上，得到 "Hello, world! How are you?"。然后，服务器收到用户 B 的操作序列，将其应用到初始文本上，得到 "Hello, world! I'm fine."。
接下来，服务器需要进行操作转换，将用户 B 的操作序列转换为适应用户 A 的文本状态。在这个例子中，用户 B 的操作 "insert(" I'm fine.")" 需要转换为适应 "Hello, world! How are you?" 的操作。
操作转换的过程如下：
- 用户 A 的操作 "insert(" How are you?")" 在用户 B 的操作 "insert(" I'm fine.")"
之前发生，因此用户 B 的操作不会受到影响。 - 用户 B 的操作 "insert(" I'm fine.")" 在用户 A 的操作 "insert(" How are you?")"
之后发生，因此用户 B 的操作需要向后移动。 - 用户 B 的操作 "insert(" I'm fine.")"
向后移动到 "Hello, world! How are you? I'm fine."。
最终，服务器将转换后的操作序列发送给用户 A 和用户 B，他们将其应用到本地文本上，最终得到相同的文本状态 "Hello, world! How are you? I'm fine."。
这个例子展示了 OT 算法如何通过操作转换来保持多个用户同时编辑时文档状态的一致性。在实际应用中，OT 算法需要处理更复杂的操作类型和情况，并进行更详细的操作转换。
接下来，我们聊聊 CRDT 算法：
CRDT 算法
当多个用户同时编辑同一文档时，CRDT（Conflict-free Replicated Data Type，无冲突复制数据类型）算法通过设计特定的数据结构和操作规则来实现冲突自由的复制。下面是一个简单的示例，帮助你理解CRDT算法的工作原理。
在CRDT算法中，文档被表示为一个数据结构，常见的数据结构之一是有序列表（Ordered List）。每个用户的编辑操作会被转换为操作序列，并应用到本地的有序列表上。
假设有两个用户 A 和 B 同时编辑一段文本，初始文本为空。用户 A 在文本末尾添加了字符 "Hello"，用户 B 在文本末尾添加了字符 "World"。
在CRDT算法中，每个字符都被赋予一个唯一的标识符，称为标记（Marker）。在这个例子中，我们使用递增的整数作为标记。
用户 A 的操作序列为：[insert("H", 1), insert("e", 2), insert("l", 3), insert("l", 4), insert("o", 5)]
用户 B 的操作序列为：[insert("W", 6), insert("o", 7), insert("r", 8), insert("l", 9), insert("d", 10)]
每个操作都包含要插入的字符以及对应的标记。
当用户 A 应用自己的操作序列时，有序列表变为 "Hello"。同样地，当用户 B 应用自己的操作序列时，有序列表变为 "World"。
接下来，服务器需要将两个用户的操作序列合并为一致的文本状态。在CRDT算法中，合并的过程是通过比较标记的大小来确定字符的顺序，并确保最终的文本状态一致。
合并的过程如下：
- 用户 A 的操作序列中的标记小于用户 B 的操作序列中的标记，因此 "H" 在 "W" 之前。
- 用户 A 的操作序列中的标记小于用户 B 的操作序列中的标记，因此 "e" 在 "o" 之前。
- 用户 A 的操作序列中的标记小于用户 B 的操作序列中的标记，因此 "l" 在 "r" 之前。
- 用户 A 的操作序列中的标记小于用户 B 的操作序列中的标记，因此 "l" 在 "l" 之前。
- 用户 A 的操作序列中的标记小于用户 B 的操作序列中的标记，因此 "o" 在 "d" 之前。
最终，合并后的有序列表为 "HelloWorld"。
这个例子展示了CRDT算法如何通过设计特定的数据结构和操作规则，以及比较标记的大小来实现冲突自由的复制。在实际应用中，CRDT算法可以应用于各种数据结构和操作类型，并进行更复杂的合并过程。
CRDT 的标记实现方案
- 递增整数标记：最简单的标记实现方式是使用递增的整数作为标记。每个操作都会分配一个唯一的整数标记，标记的大小可以用来比较操作的发生顺序。
- 时间戳标记：另一种常见的标记实现方式是使用时间戳作为标记。每个操作都会被分配一个时间戳，可以使用系统时间或逻辑时钟来生成时间戳。时间戳可以用来比较操作的发生顺序。
- 向量时钟标记：向量时钟是一种用于标记并发事件的数据结构。每个操作都会被分配一个向量时钟标记，向量时钟由多个节点的时钟组成，每个节点维护自己的逻辑时钟。向量时钟可以用来比较操作的发生顺序，并检测并发操作之间的关系。
- 哈希值标记：有些情况下，可以使用操作内容的哈希值作为标记。每个操作的内容都会被哈希为一个唯一的标记，这样可以通过比较哈希值来比较操作的发生顺序。
方案选型
OT算法和CRDT算法都是用于实现实时协同编辑的算法，但它们有不同的优点、缺点和工作原理。
OT算法的优点：
- 简单性：OT算法相对较简单，易于理解和实现。
- 实时协同编辑：OT算法可以实现实时协同编辑，多个用户可以同时编辑文档，并通过操作转换保持文档状态的一致性。
OT算法的缺点：
- 操作转换复杂性：OT算法的操作转换过程相对复杂，需要考虑多种情况和操作类型，实现和测试上有一定的挑战。
- 需要服务器参与：OT算法需要中央服务器来处理操作转换，这可能会导致一定的延迟和依赖性。
CRDT算法的优点：
- 冲突自由：CRDT算法设计了特定的数据结构和操作规则，可以实现冲突自由的复制，多个用户同时编辑时不会发生冲突。
- 去中心化：CRDT算法可以在去中心化的环境中工作，不依赖于中央服务器进行操作转换，每个用户可以独立地进行编辑和合并。
CRDT算法的缺点：
- 数据结构复杂性：CRDT算法的数据结构和操作规则相对复杂，需要更多的设计和实现工作。
- 数据膨胀：CRDT算法可能会导致数据膨胀，特别是在复杂的编辑操作和大规模的协同编辑场景下。
OT算法和CRDT算法的区别：
- 算法原理：OT算法通过操作转换来保持文档状态的一致性，而CRDT算法通过设计特定的数据结构和操作规则来实现冲突自由的复制。
- 中心化 vs. 去中心化：OT算法需要中央服务器进行操作转换，而CRDT算法可以在去中心化的环境中工作，每个用户都有完整的本地数据，可以将操作发送给服务器，然后网络分发到其他客户端。
- 复杂性：OT算法相对较简单，但在处理复杂操作和转换时可能会变得复杂；CRDT算法相对复杂，需要更多的设计和实现工作。
选择使用哪种算法取决于具体的应用场景和需求。OT算法适用于需要实时协同编辑的场景，而CRDT算法适用于去中心化和冲突自由的场景。
总结
本文介绍了在线协同文档编辑器中解决冲突的算法，主要包括OT算法和CRDT算法。OT算法通过操作转换来保持文档状态的一致性，而CRDT算法通过设计特定的数据结构和操作规则实现冲突自由的复制。OT算法需要中央服务器进行操作转换，适用于需要实时协同编辑的场景。CRDT算法可以在去中心化环境中工作，每个用户都有完整的本地数据，适用于去中心化和冲突自由的场景。选择使用哪种算法取决于具体的应用场景和需求。
来源：juejin.cn/post/7283018190593785896
