相信大家或多或少都有使用过在线文档，国内的像我们在做的腾讯文档还有其他家的很多类似产品。今天主要为大家揭开在线协作的神秘面纱，那就是 OT 算法。

0x01 背景

在线文档，抽象一下，这些产品的模式都是富文本编辑器+后台，富文本编辑器产生内容，展示内容，然后后台负责保存。
富文本编辑器现在业界已经有很多成熟的产品，像 codeMirror，这一块本身也是很复杂的一块，也不是咱们这次关注的重点方向。
不知道大家平常在用这些产品的时候有没有思考过一个问题，在线文档编辑的时候产生冲突怎么办？

0x02 举个栗子

举个很简单的例子，现在大家的文本都是 ‘aaab’，A 用户在第 3 个字符行后面插入了一个 ‘c’，B 用户在第 3 个字符行后面插入了一个 ‘d’，这个时候 A 这边看到的是 ‘aaacb’，B 这边看到的是 ‘aaadb’, 我们假设 A 用户先提交了数据，那其实最后预期的数据其实应该是 ‘aaacdb’，这样就最大的保存了每个人的输入。
那我们现在来看看正常情况下这里会发生什么：
A 用户：

A 本地已经是 ‘aaacb’ 了，过一会儿，后台告诉它 B 也编辑了，编辑的行为就是第 3 个字符行后面插入了一个 ‘d’，那 A 这边执行了这个行为，最终变成了 ‘aaadcb’

B 用户：

B 本地已经是 ‘aaadb’ 了，过一会儿，后台告诉它 A 也编辑了，编辑的行为就是第 3 个字符行后面插入了一个 ‘c’，那 B 这边执行了这个行为，最终变成了 ‘aaacdb’

从上面的模拟过程可以看到，A 用户最后的结果其实是不正确的，但是 B 是正确的。

这里先解释一下大家可能会疑惑的地方：为什么 B 是过一会儿后台告诉它 A 编辑了，不是说 A 先提交了数据吗？
其实这里针对的是冲突场景，这里如果 B 在提交之前，已经收到后台告诉它 A 编辑了，那其实就是顺序编辑了，也就不是冲突了。所以这里指的是 A，B 几乎同时提交，但是 A 到达后台还是快一点的，也就是 A，B 在编辑的时候是不知道彼此的存在的。

真实的冲突场景其实不是这种简单的时序问题，这里我后面再介绍。

0x03 尝试解决

这里可能有一些聪明的小伙伴有了一些想法。

解决方案一：丢了丢了

这可能是最简单粗暴的方法了，我发现有冲突，就告诉用户，主子，咱这里有冲突了，臣妾解决不了啊。但是显然这会经常出现，然后主子就把你打入冷宫了。

解决方案二：锁

有些小伙伴想到，上面出现问题，还不是因为大家编辑了都立即应用了，我们编辑后不立即应用不就好了，而且历史告诉我们，有冲突加锁应该可以解决。那我们看看假如不立即应用，咱有没有什么处理办法：
A 用户：

A 本地已经是 ‘aaab’ 了，A 编辑了，但是不应用，先发后台

B 用户：

B 本地已经是 ‘aaab’ 了，B 编辑了，但是不应用，先发后台

后台：

后台先收到 A 请求，然后加了一个锁，然后收到了 B 请求，这时侯应该是加锁的状态，所以接受了 A，拒绝了 B

A 用户：

A 用户收到了后台的回复，告诉它你的提交我接收了

B 用户：

B 用户收到了后台的回复，告诉它你的提交被我拒绝了，因为冲突了

这样虽然能继续下去，但是好像还是不太行的亚子啊，B 的提交还是丢了，所以好像和第一种简单粗暴的方法没啥区别

0x04 OT 算法

顺其自然的，这个时候你会看到 OT 算法驾着七彩祥云来救你了～
其实回到上面的例子，本质问题还是因为后台通知大家的 B 的编辑行为看起来不太对。现在后台通知大家的是:

B 的编辑的行为就是第 3 个字符行后面插入了一个 ‘d’

但是在 A 已经接受的情况下，正确的通知应该是：

B 的编辑的行为就是第 4 个字符行后面插入了一个 ‘d’

假如我们把 A 提交的行为叫做 A，B 提交的行为叫做 B，现在后台就是一个简单的转发功能，告诉 A 的是 B，告诉 B 的是 A，然后就出现问题了。所以后台应该更聪明一点，它应该学会一个招术，那就是把每个人提交的行为转变一下再告诉别人，其实这个技术就是 OT 算法。

OT 算法全名叫 Operation Transformation，你看从名字就对应了上面我说的转变算法。
假设我们的 OT 算法的转换功能叫 transform，那 transform（A，B）= A',B'。
也就是说你输入两个先后执行的行为，它会告诉你两个转换过后的行为，然后把 A'行为告诉 B，把 B'行为告诉 A，这样大家再应用就相安无事了。

上面的图是 OT 的经典菱形图，也就是说 A 会变成 A'在 B 这边执行，B 会变成 B'在 A 这边执行。
这里实际抽象一下，用户永远就只有两个人，一个是自己，一个是服务端，只是服务端的操作可能来自很多人，如果不这样抽象，那一个个进行冲突处理可能会让你觉得无法理解。
那我们现在再来看看后台有了 OT 这个能力之后会发生什么：

A 用户：

A 本地已经是 ‘aaacb’ 了，过一会儿，后台告诉它 B 也编辑了，编辑的行为就是第 4 个字符行后面插入了一个 ‘d’，那 A 这边执行了这个行为，最终变成了 ‘aaacdb’

B 用户：

B 本地已经是 ‘aaadb’ 了，过一会儿，后台告诉它 A 也编辑了，编辑的行为就是第 3 个字符行后面插入了一个 ‘c’，那 B 这边执行了这个行为，最终变成了 ‘aaacdb’

现在 A、B 就一致了！

0x05 OT 算法的实现

现在 OT 算法对我们来说就是一个黑盒，我们知道给一定的输入，它会有正确的输出，但是它是如何做到的呢？
在介绍它的实现之前，我们需要抽象一下我们的操作行为，在之前我们的描述都是

第 3 个字符行后面插入了一个 ‘d’

这里怎么转换成程序识别或者能用代码表达的呢？其实这也是 OT 的关键。
这里我直接揭晓答案：
所有对文本的操作都可以抽象成三个原子行为：

R = Retain，保持操作
I = Insert，插入操作
D = Delete，删除操作

那之前的行为

第 3 个字符行后面插入了一个 ‘d’

就会变成

R(3), I('d')

也就是保持三个字符后插入 1 个 ‘d’，其实应该也很好理解，这里的操作就像操作数组一样，不管干什么，第一步你得先找到操作的下标。
有了这三个原子以后，我们就可以看到：

A = R(3),I('c')
B = R(3), I('d')

一切准备就绪，我们可以开始看 OT 了，这里 OT 算法现在已经很成熟了，这里我以一个 github 上的 repo 为例：ot.js
我们可以看看它的核心代码 (有删减，理解起来可能会比较复杂，感兴趣的可以深入思考一下)：