Web 在线文档多人协同编辑器实现原理

OT 算法能够在实时保证多个客户端数据的一致性，被广泛用于协同编辑场景。

Operational transformation

OT 是一种支持高级协作软件系统中一系列协作功能的技术。OT 最初是为了在纯文本文件的协作编辑中进行一致性维护和并发控制而发明的。它的能力已经得到了扩展，其应用也扩大到包括组撤销、锁定、冲突解决、操作通知和压缩，组感知、HTML/XML 话题树结构文档编辑、协作办公生产力工具、应用程序共享和协作计算机辅助媒体工具。2009 年 OT 被采纳为 Apache Wave 和 Google Docs 协作功能背后的核心技术。

利用 OT 的协作系统通常使用复制进行文档存储，每个客户端都有自己的文档副本；客户端以无锁、无阻塞的方式对他们的本地副本进行操作，然后将变化广播给其他的客户端；这保证了客户端在其他高延迟的环境中的高响应性，例如 web。当一个客户端收到从另一个客户端广播的变化时，它通常在执行这些变化之前对其进行转换；转换确保所有站点都能保持与应用相关的一致性标准（不变性）。在这种操作模式下，系统特别适合于实现协作功能，如在网络等高延迟环境下的同步文档编辑。

基本思想

指导思想：系统不需要是正确的，它只需要保持一致，并且需要努力保持你的意图。协同编辑的冲突处理不一定是完全正确的，因为冲突本来就意味着操作是互斥的，互斥双方的操作意图不可能完全保留。冲突处理最重要的是保证协同双方最终数据的一致性，然后在这个基础上努力保持各自的操作意图。

OT 的基本思想可以通过使用一个简单的文本编辑场景来说明，如下所示。给定一个文本文件，有一个字符串 “abc”，在两个合作站点复制；还有两个并发的操作：

O1 = Insert[0, “x”] （在 “0 “位置插入字符 “x”）
O2 = Delete[2, “c”] (删除位置为 “2 “的字符 “c”)

分别由合作站点 1 和 2 的两个用户生成。假设这两个操作是按照 O1 和 O2 的顺序执行的（在站点 1) 在执行 O1 之后，文件变成了 "xabc"。为了在 O1 之后执行 O2，O2 必须针对 O1 进行转换，成为： O2'=Delete[3, "c"]，由于 O1 插入了一个字符 "x"，所以其位置参数增加了 1。在 "xabc" 上执行 O2’会删除正确的字符 "c"，文件变成 "xab"。然而，如果 O2 在没有转换的情况下被执行，它将错误地删除字符 "b" 而不是 "c"。OT 的基本思想是根据以前执行的并发操作的效果来转换（或调整）编辑操作的参数，以便转换后的操作可以达到正确的效果，并保持文档的一致性。

常见冲突处理方式

假设 AB 同时编辑同一个内容，常见处理冲突的方式有：

加锁: 用户 A 在编辑时，就锁住文档，只能 A 进行更新。用户 B 就不能编辑，或编辑后提交修改被服务器丢弃；
覆盖: 谁最后修改，就全量使用他的修改，更早一些的其他人的修改会被丢弃。
用户自行处理冲突: 就像 git merge 导致的冲突一样，会提示哪个地方被同时修改了，让合并者手动选择使用哪一个修改；
使用一致性算法: 比如 OT 算法，可以让用户编辑进行算法处理进行调整，在多个客户端生成一致的修改结果。

加锁体验极差，几乎不会选择这种模式直接覆盖会导致用户的修改被他人覆盖，体验也不好。手动处理冲突会增加用户使用和操作的成本，实时性差，不适合高频同时修改的场景。一致性算法基本是用户体验最好的选择，但实现相对复杂。

不一致的场景

假设没有 OT 解决一致性冲突的问题，有两个用户 AB 同时编辑一个文档，字符串内容为”123”

用户 A 在末尾添加一个字符”A”,修改应用在本地，内容变成了”12A”,之后客户端发送一个数据 insert(3, "A") 给服务端，代表在位置 3 插入 A，服务器将修改的消息推送到其他客户端，需要一定的时间。
用户 B 在收到推送消息前，也在 “123 的尾部添加了内容 “B”，在本地变成了 “123B”，并将 insert(3, “B”) 的修改描述提交服务器；
用户 B 收到了 insert(3, “A”) 消息，应用后，将 “123B” 变成了 “123AB”;
用户 A 则收到 insert(3, “B”) 消息，应用后，将 “123B” 变成了 “123BA”; 用户 A 看到的内容是 “123BA”，用户 B 看到的内容是 “123AB”，内容不一致，不符合预期。

使用 OT

用户 A 在末尾添加 “A”，本地变成 “123A”，并发送 insert(3, A)，这个操作计作 OA；
用户 B 在末尾添加 “B”，本地变成 “123B”，并发送 insert(3, B)，这个操作计作 OB；
用户 A 收到 OB，执行 transform(OA, OB)，得到修正后的操作 insert(4, B)，记为 OB’，相比 OB，它将插入位置从 3 修正为 4，于是 “123A” 变成了 “123AB”；
用户 B 则收到 OA，同样执行 transform(OA, OB)，得到修正操作 insert(3, A)，记为 O1’，让内容从 “123A” 变成 “123AB”。transform 方法会同时产生 OA’ 和 OB’。用户 A 和用户 B 看到的是一致的 “123AB”。

这里的核心在于这个 transfrom 方法，它能够对操作进行修正。transform 没有固定实现，要根据实际需求自行实现。

这里有一个经典的菱形示意图。

示意图

从起始版本 S 开始，它接受了两个并发操作 A 和 B。我们使用 trasform 方法生成 A’ 和 B’。我们有：

从起始版本 S 开始，它接受了两个 并发操作 A 和 B。
我们使用 trasform 方法生成 A' 和 B'。
我们有：这样，从 S 得到相同的 T，保证了一致性。

其他协同编辑框架

基于 CRDT 的数据协同框架: https://github.com/yjs/yjs

文档: https://docs.yjs.dev/