协同编辑中使用的 OT 算法是什么？

大家好，我是前端西瓜哥，今天我们来聊聊 OT 算法是什么。

OT 的英文全称是 Operational transformation，是一种处理协同编辑的算法。

它常用于实现协同文档的底层算法，支持多个用户同时编辑文档，不会因为并发修改导致冲突，而使结果不一致或数据丢失。

冲突的处理方式

假设 A 和 B 在同时编辑同一个内容，我们处理冲突的方式有：

1. 加锁。用户 A 在编辑时，就锁住文档，只能 A 进行更新。用户 B 就不能编辑，或编辑后提交修改被服务器丢弃；

2. 覆盖。谁最后修改，就全量使用他的修改，更早一些的其他人的修改会被丢弃。

3. 用户自行处理冲突。就像 git merge 导致的冲突一样，会提示哪个地方被同时修改了，让合并者手动选择使用哪一个修改；

4. 使用一致性算法。比如我们要介绍的 OT 算法，可以让用户编辑进行算法处理进行调整，在多个客户端生成一致的修改结果。

对于在线协同文档，

加锁体验太差，一个人在编辑时其他人就要干等着。

覆盖则是导致用户的修改来回彼此覆盖，辛苦编辑的内容突然被别人覆盖掉了心情低落。

自行处理冲突则需要额外的操作步骤和成本，实时性很差，不适合高频同时修改的场景。

一致性算法是最好的选择，对用户最友好，不过带来了实现的复杂。

一致性问题

我们先来看看不使用 OT 导致的冲突问题。

假设用户 A 和用户 B 同时在编辑同一个文档，文档内容为 “12”。

1. 用户 A 在末尾添加一个字符 “A”，这个修改先应用在本地，内容变成了 “12A”，之后客户端发送一个数据 insert(2, "A") 给服务端，代表在位置 2 的地方插入 “A”。服务端会将修改消息推送给其他客户端，但这需要时间；

2. 用户 B 在收到推送消息前，也在 “12” 的尾部添加了内容 “B”，在本地变成了 “12B”，并将 insert(2, "B") 的修改描述提交服务器；

3. 用户 B 收到了 insert(2, "A") 消息，应用后，将 “12B” 变成了 “12AB”；

4. 用户 A 则收到 insert(2, "B") 消息，应用后，将 “12B” 变成了 “12BA”；

结果是，用户 A 看到的内容是 “12BA”，用户 B 看到的内容是 “12AB”，内容不一致，不符合预期。

使用 OT

OT 算法可以解决一致性问题，我们来看看 OT 到底做了什么。

同样，原始内容是 “12”。

1. 用户 A 在末尾添加 “A”，本地变成 “12A”，并发送 insert(2, A)，这个操作计作 OA；

2. 用户 B 在末尾添加 “B”，本地变成 “12B”，并发送 insert(2, B)，这个操作计作 OB；

3. 用户 A 收到 OB，执行 transform(OA, OB)，得到修正后的操作 insert(3, B)，记为 OB’，相比 OB，它将插入位置从 2 修正为 3，于是 “12A” 变成了 “12AB”；

4. 用户 B 则收到 OA，同样执行 transform(OA, OB)，得到修正操作 insert(2, A)，记为 O1’，让内容从 “12A” 变成 “12AB”。transform 方法会同时产生 OA’ 和 OB’。

最后，用户 A 和用户 B 看到的是 一致 的 “12AB”。

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

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

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

S + A + B' = T
S + B + A' = T
1
2

这样，从 S 得到相同的 T，保证了一致性。

下面使用了 ot.js 库，演示了一下从 ‘12’ 到 ‘12AB’ 的过程。

const s = '12'; // 原始文案（版本 1）

// 在位置 3 插入 'A'
const oA = new TextOperation().retain(2).insert('A');

// 上述操作后得到结果 '12A'（版本 2）
const t1 = oA.apply(s);

// 收到 oB 操作：在位置 2 插入 'B'
const oB = new TextOperation().retain(2).insert('B');

// transform 拿到修正后的 [oA', oB']
// 我们这里只需要 oB'，它被修正为在位置 3 插入 'B'
const [oAp, oBp] = TextOperation.transform(oA, oB);

// 应用 oB'，结果为：12AB （版本 3）
const t2 = oBp.apply(t1);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

线上 demo 链接为：

https:/ /codesandbox.io/s/b8ds8h

transform 操作既发生在服务端：将基于某个版本的并发操作对象转换成串行操作。

也发生在客户端，本地的修改还没来得及提交，就收到了服务端推送。

如果你想要深入研究 OT 算法，可以考虑参考 ot.js 库的代码实现，里面还附带了一个 OT 可视化过程

https:/ /github.com/Operational-Transformation/ot.js/

结尾

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

我是前端西瓜哥，欢迎关注我，学习更多前端知识。