协同编辑中使用的 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”,内容不一致,不符合预期。

image-20220828133852728

使用 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”。

image-20220830100413167

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

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

image-20220830134114621

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

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

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
const s = '12'// 原始文案(版本 1)

// 在位置 2 插入 '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);

线上 demo 链接为:

https://codesandbox.io/s/b8ds8h

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

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

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

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

结尾

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

本文首发于我的公众号:前端西瓜哥

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

https://blog.fstars.wang/posts/what-is-ot/

作者

前端西瓜哥

发布于

2022-08-31

更新于

2023-10-14

许可协议