开发一个在线文档我们可能要解决的问题：

OT：一种解决协同问题的算法；

(资料图片仅供参考)

OP：operation的简称，在OT中指的是一次操作；

etherpad: 一个实现文档协同功能的开源库；

easysync: etherpad中实现文档协同的核心算法，是OT算法的一种，主要用来处理文本协同；

ot-json：ot算法的一种，顾名思义，是主要用来处理结构化数据；

Changeset: 一种描述文档更改的数据格式，用来表示整个文档的一次修改；

ClientVars：表示一篇文档的初始化数据，一般由连续的changeset组合而成；

​​|​​：移动光标；

​​·​​：叠加；

什么是OT算法呢？我们先从头说起，如果要实现一个多人共同编辑文档的功能，我们最简单暴力的做法是啥？

顾名思义，假如A在编辑文档，服务端直接将这个文档加锁，B如果在这个时候也加入了编辑，由于锁的存在，B的编辑直接被丢弃。可以看出，这种编辑锁的实现方式非常粗暴，体验极其糟糕，当然了，在很多公司(比如我们的某死对头公司)的一些wiki系统就是用这种实现方式，由于这种实现方式比较简单，而且体验很糟糕(内容丢失 & 无法实时)，我们这里就不做讨论了。

Linux中有两个命令：diff和patch；如果我们能在JS中实现这套算法，那么多人协同编辑可以这样做：

我们来测试下：

# 本地文档$ echo "复仇者联盟钢铁侠美国队长" > test-local.txt# 生成用户A编辑后的文档$ echo "复仇者联盟钢铁侠绿巨人" > test-userA.txt# diff两个文档$ diff test-local.txt test-userA.txt > diff-test.patch# 查看diff-test.patch内容$ cat diff-test.patch3c3< 美国队长---> 绿巨人

从diff-test.patch内容可以看出，已经找出了两个文档不同的地方，然后我们再模拟下用户B的行为：

# 生成用户B编辑的文档$ echo "复仇者联盟黑寡妇美国队长" > test-userB.txt# patch方法更新文档$ patch test-userB.txt < diff-test.patch# 查看test-userB.txt内容$ cat test-userB.txt复仇者联盟黑寡妇绿巨人

可以看到，用户B文档的第三行已经更新为了用户A修改后的“绿巨人”。但这种实现方式有个问题，因为他是基于行来进行对比的，就会导致很容易出现冲突，比如：

# 生成文件1$ echo "复仇者联盟" > local.txt# 生成文件2$ echo "复仇者联盟钢铁侠" > userA.txt# diff对比$ diff local.txt userA.txt > diff.patch

查看diff.patch内容：

1c1< 复仇者联盟---> 复仇者联盟钢铁侠

这就意味着如果两个人同时修改同一行，那必然就会产生冲突，我们测试下:

# 生成文件3$ echo "复仇者联盟美国队长" > userB.txt# patch$ patch userB.txt < diff.patch

以上我们发现，假如原始文档是“复仇者联盟”，用户A修改为“复仇者联盟钢铁侠”，将diff结果传给服务端，服务端传给用户B，而用户B只是将文档改为了“复仇者联盟美国队长”，直觉上我们可以看出，这两处是不冲突的，完全可以合并成“复仇者联盟钢铁侠美国队长”，但实际上的patch结果却是这样的：

$ cat userB.txt.rej****************** 1- 复仇者联盟--- 1 -----+ 复仇者联盟钢铁侠

因此这种基于行的算法还是比较粗糙，体验上比编辑锁虽然好了一点，但实际弊端还是比较大，既然基于行的实现无法满足需求，那有木有可能去基于字符进行diff呢？

diff-match-patch^[1]是另一种diff-patch算法的实现，它是基于字符去进行diff的，这里不介绍该算法的细节了，它的算法在这：diff-match-patch JS实现源码^[2]。我们直接测试下它的效果

// 示例1const localText = "复仇者联盟";const userAText = "复仇者联盟钢铁侠";const userBText = "复仇者联盟美国队长";// 结果为：复仇者联盟钢铁侠美国队长// 示例2const localText = "复仇者联盟";const userAText = "复仇者联盟美国队长";const userBText = "复仇者联盟钢铁侠";// 结果为：复仇者联盟钢铁侠美国队长// 示例3const localText = "复仇者联盟";const userAText = "复仇者联盟 美国队长";const userBText = "复仇者联盟 钢铁侠";// 结果为：复仇者联盟 美国队长 钢铁侠

如上示例已经解决了Linux的diff-patch基于行diff的弊端，但仍然存在问题，如上的示例1和示例2如果没有符号分割，那么结果是一样的。

const localText = "复仇者 Iron Man";const userAText = "Iron Man 钢铁侠";const userBText = "复仇者 Caption";// 结果为：Caption

原始文档为“复仇者 Iron Man”，用户A修改为了“Iron Man 钢铁侠”，用户B修改为了“复仇者 Caption”，直觉上其实可以合并为“Caption 钢铁侠”，但实际上却修改为了“Caption”(注意Caption后面有个空格，钢铁侠没了)，

也就是说diff-match-patch存在丢字符的情况，这个富文本格式的文档中会是致命的问题，比如丢失了某个>可能整个文档都会乱掉，那么有木有既解决了行匹配冲突问题又解决了丢字符问题的解决方案呢？答案就是本文的重点——OT算法

ot.js^[3]是针对纯文本的一种JS实现，我们看下它的实现效果，针对同样的示例：

const str = "复仇者 Iron Man";const operation0 = new ot.TextOperation().delete("复仇者 ").retain(8).insert(" 钢铁侠");const operation1 = new ot.TextOperation().retain(4).delete("Iron Man").insert("Captain");const op = ot.TextOperation.transform(operation0, operation1);// 结果：Captain 钢铁侠

可以看到这正是符合我们预期的结果。

看了很多讲OT的文档，基本每一篇都很长，云山雾罩，但其实它的核心原理很简单。在OT中，我们将文档的操作分为三个类型，通过组合这三个原子操作完成对整个文档的编辑工作：

注：实际上diff-match-patch算法也将操作分为三类：insert，delete，equal(不变的字符)，insert、delete和OT中含义类似，equal是指对比diff过程中那些没有改变的字符，diff-match-patch会给这些不同类型的字符打标，后面patch的时候再根据不同类型的字符做对应的逻辑处理。

|

复仇者联盟|

如上|代表的是光标的位置，从上到下模拟用户操作的行为，以上操作使用ot.js来描述：

const str = "";const operation = new ot.TextOperation().insert("复仇者联盟");const result = operation.apply(str); console.log(result); // 复仇者联盟

op创建时会有一个虚拟光标位于字符的开头，在一个op结束时，光标一定要在字符串的末尾，其中insert会自动移动光标位置，因此我们这里不需要手动去移动光标；

|复仇者联盟

复仇者联盟|

复仇者联盟钢铁侠|

如上过程用ot.js来描述：

const str = "复仇者联盟";const operation = new ot.TextOperation().retain(5).insert("钢铁侠");const result = operation.apply(str); console.log(result);// 复仇者联盟钢铁侠

|复仇者联盟钢铁侠

复仇者联盟|钢铁侠

复仇者联盟|

如上过程用ot.js描述：

const str = "复仇者联盟钢铁侠";const operation = new ot.TextOperation().retain(5).delete("钢铁侠");const result = operation.apply(str); console.log(result);// 复仇者联盟

删除字符时可以输入字符，也可以输入字符数，实际上源码中是直接取的​​"钢铁侠".length​​因此对于delete中字符串而言，只要长度正确就可以达到目的，上面代码改成​​delete("123")​​不会有任何影响。

前面的代码我们看到过ot.js的这个方法，正是这个方法实现了diff-match-patch的丢失字符的问题，而transform正是OT中的核心方法。我们先不罗列他的源码，先看几个例子：

示例1

原始文档内容(空白文档)：|

用户A编辑后的文档内容：钢铁侠

用户B编辑后的文档内容：雷神

对应代码实现：

const str = " ";const operation0 = new ot.TextOperation().insert("钢铁侠");const operation1 = new ot.TextOperation().insert("雷神");const op = ot.TextOperation.transform(operation0, operation1);console.log("transform后op操作：", op[0].toString(), " | ", op[1].toString()); // transform后op操作：insert "钢铁侠", retain 2  |  retain 3, insert "雷神"console.log("transform后操作后的字符串：", op[0].apply(operation1.apply(str)), " | ", op[1].apply(operation0.apply(str))); // transform后操作后的字符串： 钢铁侠雷神  |  钢铁侠雷神

最终结果是“钢铁侠雷神”；

transform的操作过程：

示例2

原始文档：复仇者联盟

用户A：复仇者钢铁侠联盟

用户B：复仇者联盟美国队长

对应代码实现：

const str = "复仇者联盟";const operation0 = new ot.TextOperation().retain(3).insert("钢铁侠").retain(2);const operation1 = new ot.TextOperation().retain(5).insert("美国队长");const op = ot.TextOperation.transform(operation0, operation1);console.log("transform后op操作：", op[0].toString(), " | ", op[1].toString());// transform后op操作：retain 3, insert "钢铁侠", retain 6  |  retain 8, insert "美国队长"console.log("transform后操作后的字符串：", op[0].apply(operation1.apply(str)), " | ", op[1].apply(operation0.apply(str)));// transform后操作后的字符串： 复仇者钢铁侠联盟美国队长  |  复仇者钢铁侠联盟美国队长

最终结果是“复仇者钢铁侠联盟美国队长”；

transform的操作过程：

示例3

原始文档：复仇者联盟钢铁侠美国队长

用户A：复仇者联盟钢铁侠

用户B：复仇者联盟美国队长

对应代码实现：

const str = "复仇者联盟钢铁侠美国队长";const operation0 = new ot.TextOperation().retain(5).delete("钢铁侠").retain(4);const operation1 = new ot.TextOperation().retain(8).delete("美国队长");const op = ot.TextOperation.transform(operation0, operation1);console.log("transform后op操作：", op[0].toString(), " | ", op[1].toString());// transform后op操作：retain 5, delete 3  |  retain 5, delete 4console.log("transform后操作后的字符串：", op[0].apply(operation1.apply(str)), " | ", op[1].apply(operation0.apply(str)));// transform后操作后的字符串： 复仇者联盟  |  复仇者联盟

最终结果是“复仇者联盟”；

操作过程：

最终结果是“复仇者联盟”；

示例4

原始文档：复仇者联盟钢铁侠美国队长"

用户A：复仇者联盟

用户B：复仇者联盟美国队长

对应代码实现：

const str = "复仇者联盟钢铁侠美国队长";const operation0 = new ot.TextOperation().retain(5).delete("钢铁侠美国队长");const operation1 = new ot.TextOperation().retain(5).delete("钢铁侠").retain(4);const op = ot.TextOperation.transform(operation0, operation1);console.log("transform后op操作：", op[0].toString(), " | ", op[1].toString());//transform后op操作：retain 5, delete 4  |  retain 5console.log("transform后操作后的字符串：", op[0].apply(operation1.apply(str)), " | ", op[1].apply(operation0.apply(str)));// transform后操作后的字符串： 复仇者联盟  |  复仇者联盟

最终结果是“复仇者联盟”；

操作过程：

ot.js中transform的源码如下：

TextOperation.transform = function (operation1, operation2) {    // ...    var operation1prime = new TextOperation();    var operation2prime = new TextOperation();    var ops1 = operation1.ops, ops2 = operation2.ops;    var i1 = 0, i2 = 0;    var op1 = ops1[i1++], op2 = ops2[i2++];    while (true) {      //...      // 对应示例1第一次循环的操作逻辑      if (isInsert(op1)) {        operation1prime.insert(op1);        operation2prime.retain(op1.length);        op1 = ops1[i1++];        continue;      }      // 对应示例1第二次循环的操作逻辑      if (isInsert(op2)) {        operation1prime.retain(op2.length);        operation2prime.insert(op2);        op2 = ops2[i2++];        continue;      }      // ...      var minl;      // 对应示例2循环      if (isRetain(op1) && isRetain(op2)) {        if (op1 > op2) {          minl = op2;          op1 = op1 - op2;          op2 = ops2[i2++];        // 对应示例2第三次循环的操作逻辑        } else if (op1 === op2) {          minl = op2;          op1 = ops1[i1++];          op2 = ops2[i2++];        // 对应示例2的第一次循环操作逻辑        } else {          minl = op1;          op2 = op2 - op1;          op1 = ops1[i1++];        }        operation1prime.retain(minl);        operation2prime.retain(minl);       // 对应示例4的第二次循环      } else if (isDelete(op1) && isDelete(op2)) {        if (-op1 > -op2) {          op1 = op1 - op2;          op2 = ops2[i2++];        } else if (op1 === op2) {          op1 = ops1[i1++];          op2 = ops2[i2++];        } else {          op2 = op2 - op1;          op1 = ops1[i1++];        }      // 示例3的第二次循环      } else if (isDelete(op1) && isRetain(op2)) {        if (-op1 > op2) {          minl = op2;          op1 = op1 + op2;          op2 = ops2[i2++];        } else if (-op1 === op2) {          minl = op2;          op1 = ops1[i1++];          op2 = ops2[i2++];        } else {          minl = -op1;          op2 = op2 + op1;          op1 = ops1[i1++];        }        operation1prime["delete"](minl ""delete"");      // 示例3的第三次循环      } else if (isRetain(op1) && isDelete(op2)) {        if (op1 > -op2) {          minl = -op2;          op1 = op1 + op2;          op2 = ops2[i2++];        } else if (op1 === -op2) {          minl = op1;          op1 = ops1[i1++];          op2 = ops2[i2++];        } else {          minl = op1;          op2 = op2 + op1;          op1 = ops1[i1++];        }        operation2prime["delete"](minl ""delete"");      } else {        throw new Error( The two operations aren"t compatible );      }    }    return [operation1prime, operation2prime];  };

如上4个示例覆盖了​​transform​​所有分支的操作。核心原理其实很简单，就是通过循环去将两个操作重新进行排列组合，按照操作的类型作出不同的逻辑处理，这是OT中非常核心的方法，除此之外还有​​compose​​，​​apply​​等方法，这里就不一一罗列了。

上面过程经常用一个菱形图来表示transform过程：

transform(a, b) = (a", b");

顾名思义，这个方法是用来合并两次操作OP的，比如：

const str = "复仇者联盟";const operation0 = new ot.TextOperation().retain(5).insert("钢铁侠");const operation1 = new ot.TextOperation().retain(8).insert("黑寡妇");const op = operation0.compose(operation1);console.log("compose后op操作：", op.toString());console.log("结果：", op.apply(str)); // 复仇者联盟钢铁侠黑寡妇

compose的实现和transform类似，罗列两个OP所有的组合可能性，分别作出对应的逻辑处理。相关源码可以去github^[4]这里查看。当然ot.js的API远不止这两个，比如客户端的undo/redo方法用来实现文档的撤销/重做，这里就不一一过了

基于以上示例和代码相信OT的核心原理大家应该比较清晰了，但OT算法基于顺序来进行转换的，假如用户A操作了两次文档，但因为网络原因，第二次比第一次先到达了服务器，而服务器基于收到的顺序来分发给其它用户那么必然会出现问题。流程图如下：

因此我们需要对每次的操作进行一个版本控制，在每次提交的时候加上一个版本标识，类似git的commitID，每次提交版本都自增1，来标识每次的OP操作；客户端和服务端各自维护一份版本；

客户端：发送出的请求返回确认后，本地版本+1；

服务端：完成一次OP时，版本+1;

因此客户端的版本一定是小于等于服务端的。

相关转换过程如图，这里就不细说了，其实就是上面菱形的延伸。感兴趣可以去http://operational-transformation.github.io/index.html这里模拟体验整个过程。github上有很多js版本的OT实现库，比如https://github.com/marcelklehr/changesets也是OT算法的实现，感兴趣同学也可以去了解下。

OT将操作的状态三为三种：

此阶段收到后台新的OP，会进行一次transform

transform(OP1, OP) = (OP1", OP")；其中OP"会被应用到本地

OP1是本地提交后但未被确认的OP；

此阶段产生的新的OP，会和上次本地编辑的OP做一次compose，合并为一个新的OP

此阶段收到后台新的OP，会进行两次transform和一次compose:

​​OP3 = OP1.compose(OP2);​​

​​transform(OP1, OP) = (OP1", OP");​​

​​transform(OP3, OP") = (OP3", OP"");​​

最终OP""会被应用到本地，然后更新OP1 = OP1" 和OP3 = OP3"

OP：服务端推送的新的OP；

OT算法很适合用用来处理文本的协同，最早提出时间可以追溯到1989年，也有各种语言的具体实现，相对比较成熟，目前在Google Docs，腾讯文档，包括我司的飞书文档都是用的OT算法，但OT目前是没法做到点对点通信的，随着Web通信协议的发展(比如WebRTC)，点对点的通信已经成为C/S架构的可替代方案，CRDT算法也是一种协同算法，大概在2006年提出，目前在Atom、Figma等产品中都有落地使用，CRDT在支持C/S架构模型的同时也可以支持点对点的传输，但目前各个文档其实还是主要使用OT，下面这个视频有讲说CRDT随着文本内容的增加复杂度会远大于OT，具体原因还没了解，感兴趣的同学可以一起研究下。

https://youtu.be/PWzrbg9qqK8

CRDT相关论文：https://www.researchgate.net/publication/310212186_Near_Real-Time_Peer-to-Peer_Shared_Editing_on_Extensible_Data_Types

CRDT介绍：https://crdt.tech/resources

CRDT开源实现：https://github.com/yjs/yjs

以上介绍了协同处理算法中的OT算法，我们的例子也都是用的纯文本，但实际上的在线文档不可能如此简单的，比如有各种各样的block，富文本的支持，评论，选中等等功能；如果单纯去使用ot.js来去做的话，无异于挖坑自埋。而easysync也是OT算法的一种实现，它被使用在etherpad中。

easysync这套算法作者是申请了专利的，专利地址：https://www.freepatentsonline.com/y2012/0110445.html，凭借这套算法作者创立了etherpad公司，后面被google收购，然后将etherpad开源了。

起初etherpad是一套跑在Java虚拟机上，可以用JS来写逻辑的服务，但更多的功能还是以jar包的形式提供，这样搞也主要是为了easysync只需要实现一份JS的版本就可以同时跑在前端和后台，后面随着功能的迭代完善官方也发觉了这套东西很难维护，后面推出了nodejs版本的etherpad-lite^[5]，不在需要维护jar包。

简单说etherpad就是个google开源(Apache 协议)的富文本编辑器(demo地址^[6])，而协同算法用的是OT算法之一的easysync算法。

在easysync中使用一种数据结构来描述整个文档。

对于上面截图中的文档的描述：

{    attribs : *0+5|1+1*1*2*3*4*5+1*6+3*2|1+1 ,    text : 复仇者联盟\n*钢铁侠\n}

上面这个对象描述的是整个文档的内容和格式，text存储的是整个文档的内容包括换行符等符号，attribs存储的是对文档内容格式的描述，上图中的属性中*+都不是我们印象中的乘法加法，这里面的数字只代表序号。翻译下具体符号的含义：

注：easysync里面的数字大都是36进制的，主要目的是为了缩短传输字符的长度；

具体的属性(加粗，斜体等)描述在另一个属性apool中。上面文档中对应的属性描述如下：

{    apool :{        numToAttrib :{            0 :[                lineguid ,                HwV9Nr            ],            1 :[                align ,                left            ],            2 :[                author ,                52000000000000025            ],            3 :[                fragmentguid ,                1981193224752831644            ],            4 :[                insertorder ,                first            ],            5 :[                lmkr ,                1            ],            6 :[                lineguid ,                sQgJ38            ],            7 :[                store ,                {\ contentConfig\ :{\ 0 \ :[1,2,3],\ 1 \ :[1,2,3],\ 2 \ :[1,2,3,4,5],\ 3 \ :[1,4,5],\ 4 \ :[]}}            ]        },        nextNum :8    }}

如上的numToAttrib属性里面存储的序号就是上面中数字。结合apool里面的属性值我们就可以把​​*0+5|1+1*1*2*3*4*5+1*6+3*2|1+1​​****给翻译出来了：

可以看出这其实就是一份描述文档的数据结构，理论上我们只要实现了对应平台的渲染器，那就不仅可以把它渲染成html，同样也可以应用在native。但这种格式是按文行和列来描述，遇到表格这种一行里面分格子的需求就很难做了。

上面easysync定义了一组数据结构来描述整个文档内容，但在协同的场景下如何处理变更也会是一个很棘手的问题。在easysync定义了一个叫changeset的概念去描述文档的变更。文档在一开始创建或是导入的时候会生成一个初始化的内容结构，之后所有的更改都会用changeset来表示。对文档做一下变更，则会产生一次changeset：

Z:c>3|1=7=4*0+3$ 黑寡妇

如果用通信协议来理解changeset的话，可以分为包头和包体，包头主要用来描述字符长度，而上面的Z似乎是个Magicnumber，每一个changeset都会以Z开头。而包体则用来描述具体的操作(比如新增字符，删除字符等)。$后面的被叫做charbank，所有这次变更新增的字符都是从charbank里面取出来的。在changeset中符号代表的含义如下：

Z:f<3|1=7=4-3$

Z:c>4|1=7=4*0+4$ 美国队长

Z:g>2|1=7=8*0+2$ 雷神

const cs1 = "Z:c>4|1=7=4*0+4$ 美国队长";const cs2 = "Z:g>2|1=7=8*0+2$ 雷神";console.log(Changeset.compose(cs1, cs2, false, null));// Z:c>6|1=7=4*0+6$ 美国队长雷神

Z:c>3|1=7=4*0+3$ 黑寡妇

Z:c>4|1=7=4*0+4$ 美国队长

const A = "Z:b>3|1=4*0+3$ 黑寡妇";const B = "Z:b>4|1=4*0+4$ 美国队长";const A1 = follow(B, A, false, null);const B1 = follow(A, B, true, null);console.log(A1, B1);// Z:f>3|1=4=4*0+3$ 黑寡妇 Z:e>4|1=4*0+4$ 美国队长const A2 = compose(A, B1);const B2 = compose(B, A1);console.log(A2, B2);// Z:b>7|1=4*0+7$ 美国队长黑寡妇 Z:b>7|1=4*0+7$ 美国队长黑寡妇