对前端来说开发一个在线文档需要啥技术？

开发一个在线文档我们可能要解决的问题：,OT：一种解决协同问题的算法；,OP：operation的简称，在OT中指的是一次操作；,etherpad: 一个实现文档协同功能的开源库；,easysync: etherpad中实现文档协同的核心算法，是OT算法的一种，主要用来处理文本协同；,ot-json：ot算法的一种，顾名思义，是主要用来处理结构化数据；,Changeset: 一种描述文档更改的数据格式，用来表示整个文档的一次修改；,ClientVars ： 表示一篇文档的初始化数据，一般由连续的changeset组合而成；,​​|​​ ：移动光标；,​​·​​：叠加；,什么是OT算法呢？我们先从头说起，如果要实现一个多人共同编辑文档的功能，我们最简单暴力的做法是啥？,顾名思义，假如A在编辑文档，服务端直接将这个文档加锁，B如果在这个时候也加入了编辑，由于锁的存在，B的编辑直接被丢弃。可以看出，这种编辑锁的实现方式非常粗暴，体验极其糟糕，当然了，在很多公司(比如我们的某死对头公司)的一些wiki系统就是用这种实现方式，由于这种实现方式比较简单，而且体验很糟糕(内容丢失
& 无法实时)，我们这里就不做讨论了。,Linux中有两个命令：diff和patch；如果我们能在JS中实现这套算法，那么多人协同编辑可以这样做：,我们来测试下：,从diff-test.patch内容可以看出，已经找出了两个文档不同的地方，然后我们再模拟下用户B的行为：,可以看到，用户B文档的第三行已经更新为了用户A修改后的“绿巨人”。但这种实现方式有个问题，因为他是基于行来进行对比的，就会导致很容易出现冲突，比如：,查看diff.patch内容：,这就意味着如果两个人同时修改同一行，那必然就会产生冲突，我们测试下:,以上我们发现，假如原始文档是“复仇者联盟”，用户A修改为“复仇者联盟钢铁侠”，将diff结果传给服务端，服务端传给用户B，而用户B只是将文档改为了“复仇者联盟美国队长”，直觉上我们可以看出，这两处是不冲突的，完全可以合并成“复仇者联盟钢铁侠美国队长”，但实际上的patch结果却是这样的：,因此这种基于行的算法还是比较粗糙，体验上比编辑锁虽然好了一点，但实际弊端还是比较大，既然基于行的实现无法满足需求，那有木有可能去基于字符进行diff呢？,diff-match-patch^[1]是另一种diff-patch算法的实现，它是基于字符去进行diff的，这里不介绍该算法的细节了，它的算法在这：diff-match-patch JS实现源码^[2]。我们直接测试下它的效果,如上示例已经解决了Linux的diff-patch基于行diff的弊端，但仍然存在问题，如上的示例1和示例2如果没有符号分割，那么结果是一样的。,原始文档为“复仇者 Iron Man”，用户A修改为了“Iron Man 钢铁侠”，用户B修改为了“复仇者 Caption”，直觉上其实可以合并为“Caption 钢铁侠”，但实际上却修改为了“Caption ”(注意Caption后面有个空格，钢铁侠没了)，,也就是说diff-match-patch存在丢字符的情况，这个富文本格式的文档中会是致命的问题，比如丢失了某个 > 可能整个文档都会乱掉，那么有木有既解决了行匹配冲突问题又解决了丢字符问题的解决方案呢？答案就是本文的重点——OT算法,ot.js^[3]是针对纯文本的一种JS实现，我们看下它的实现效果，针对同样的示例：,可以看到这正是符合我们预期的结果。,看了很多讲OT的文档，基本每一篇都很长，云山雾罩，但其实它的核心原理很简单。在OT中，我们将文档的操作分为三个类型，通过组合这三个原子操作完成对整个文档的编辑工作：,如上|代表的是光标的位置，从上到下模拟用户操作的行为，以上操作使用ot.js来描述：,op创建时会有一个虚拟光标位于字符的开头，在一个op结束时，光标一定要在字符串的末尾，其中insert会自动移动光标位置，因此我们这里不需要手动去移动光标；,如上过程用ot.js来描述：,如上过程用ot.js描述：,删除字符时可以输入字符，也可以输入字符数，实际上源码中是直接取的​​'钢铁侠'.length​​ 因此对于delete中字符串而言，只要长度正确就可以达到目的，上面代码改成​​delete('123')​​不会有任何影响。,前面的代码我们看到过ot.js的这个方法，正是这个方法实现了diff-match-patch的丢失字符的问题，而transform正是OT中的核心方法。我们先不罗列他的源码，先看几个例子：,示例1,对应代码实现：,最终结果是“钢铁侠雷神”；,transform的操作过程：,示例2,对应代码实现：,最终结果是“复仇者钢铁侠联盟美国队长”；,transform的操作过程：,示例3,对应代码实现：,最终结果是“复仇者联盟”；,操作过程：,最终结果是“复仇者联盟”；,示例4,对应代码实现：,最终结果是“复仇者联盟”；,操作过程：,ot.js中transform的源码如下：,如上4个示例覆盖了​​transform​​所有分支的操作。核心原理其实很简单，就是通过循环去将两个操作重新进行排列组合，按照操作的类型作出不同的逻辑处理，这是OT中非常核心的方法，除此之外还有​​compose​​，​​apply​​等方法，这里就不一一罗列了。,上面过程经常用一个菱形图来表示transform过程：,transform(a, b) = (a', b');,顾名思义，这个方法是用来合并两次操作OP的，比如：,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，会和上次本地编辑的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中使用一种数据结构来描述整个文档。,对于上面截图中的文档的描述：,上面这个对象描述的是整个文档的内容和格式，text存储的是整个文档的内容包括换行符等符号，attribs存储的是对文档内容格式的描述，上图中的属性中*+都不是我们印象中的乘法加法，这里面的数字只代表序号。翻译下具体符号的含义：,注：easysync里面的数字大都是36进制的，主要目的是为了缩短传输字符的长度；,具体的属性(加粗，斜体等)描述在另一个属性apool中。上面文档中对应的属性描述如下：,如上的numToAttrib属性里面存储的序号就是上面中数字。结合apool里面的属性值我们就可以把 ​​*0+5|1+1*1*2*3*4*5+1*6+3*2|1+1​​ ****给翻译出来了：,可以看出这其实就是一份描述文档的数据结构，理论上我们只要实现了对应平台的渲染器，那就不仅可以把它渲染成html，同样也可以应用在native。但这种格式是按文行和列来描述，遇到表格这种一行里面分格子的需求就很难做了。,上面easysync定义了一组数据结构来描述整个文档内容，但在协同的场景下如何处理变更也会是一个很棘手的问题。在easysync定义了一个叫changeset的概念去描述文档的变更。文档在一开始创建或是导入的时候会生成一个初始化的内容结构，之后所有的更改都会用changeset来表示。对文档做一下变更，则会产生一次changeset：,如果用通信协议来理解changeset的话，可以分为包头和包体，包头主要用来描述字符长度，而上面的Z似乎是个Magicnumber，每一个changeset都会以Z开头。而包体则用来描述具体的操作(比如新增字符，删除字符等)。$ 后面的被叫做charbank，所有这次变更新增的字符都是从charbank里面取出来的。在changeset中符号代表的含义如下：,上面的changeset翻译如下：,而这里的​​+、-、=​​在某种意义上对应的就是ot.js中的​​insert,delete和retain​​三个原子操作；,我们再看一个删除字符(删除了黑寡妇)的例子：,在删除的changeset中charbank是空的，因为是删除，没有新增字符；官方文档参考：https://github.com/ether/etherpad-lite/blob/develop/doc/easysync/easysync-notes.pdf,在实际操作中changeset会非常的多，很频繁，比如现在的我在疯狂码字一样，那么对于changeset的合并(compose)就很重要，它可以极大地缩短传输字符的长度，而在协同的场景下，用户A和用户B提交的changeset就需要去合并，我们上面提到过的ot.js中的transform方法，在easysync中它叫做follow。回顾下前面的ot.js我们会发现,用户B本地操作：插入字符”美国队长“，对应changeset是：,用户B紧接着操作：插入字符”雷神“，对应changeset为：,两次操作假设相隔很短，那么完全可以合并为一次changeset：,注意，compose是有合并顺序的，参数1一定是参数2的前置操作。下文中我们将 compose方法省略。 状态A和状态B合并为状态C（状态A是状态B的前置操作），记为 C = AB；,compose合并的是有前后操作关系的状态，但在文档协同中更多的是并发冲突问题，merge是easysync中解决并发冲突的算法，比如用户A和用户B同时编辑了一份文档：,用户A插入 黑寡妇 ：,用户B插入 美国队长 ：,merge就是将操作A和B进行合并的，合并后的状态我们记为C，即 C = m(A, B);,对 ​​m​​ 的约束条件： ​​A​​ 和 ​​B​​ 的顺序可以是任意的，即 ​​m(A, B) = m(B, A)​​ ；,上面的例子生成的状态C
= m(B, A)，其实是应用于服务端的状态，假设服务端状态 X => X'。那么可记为X' = Xm(B, A)。X'是通过X 和
m(B,
A)合并得到的，但对客户端来说无法直接去这样操作，因为对用户A来说，状态C并不是A的前置，无法直接去合并，我们需要一个算法去做转换，这个实现就是follow方法，还是上面的例子：,可以看到用户A和B，最终的changeset分别是A2和B2，A2和B2是完全相等的。,这里我们将follow方法记为f, 当服务端收到用户A和用户B的并发操作的时候处理过程，假设服务端目前的状态是X，收到了用户A的操作A，然后apply到字符串变成了XA，此时又收到了用户B的操作B，很明显，此时直接应用XAB是不行的，因为A和B都是基于X来变更的，A并不是B的前置，此时就需要一个B'，来实现XAB'，且有XAB' = XBA'。, 也就是上面例子中的follow结果，B' = f(A, B)，A' = f(B, A)。由此可得到：XAf(A, B) = XBf(B, A)。即，Af(A, B) = B f(B, A) ;这个公式就是follow算法的核心。,前面也提到过OT算法必然需要一个Server去中转，不支持点对点。我们来看下客户端和服务端分别是怎么工作的：,前面说过在OT中客户端可以把用户的操作分为三种状态，在easysync中也有三种状态：,A: 服务端最新内容，未进行修改；,X：changeset已经提交了，还没被确认；,Y: 客户端产生的还没提交到服务端的变更集；,还有一种特殊的changeset，就是在X期间，又产生了新的changeset，我们用E来代替。,E: ****changeset提交期间产生的新的编辑；,etherpad官方文档里面写的巨复杂，我简单梳理下这里客户端的状态变化和操作(注意：下文中的=和≠都是传统数学意义上的符号，直接合并即使用compose/merge合并)：,此时再将新的A'，X'，Y'赋值给AXY,这里服务端的处理逻辑相对前端来说要简单很多，主要做两件事：,其中处理变更集的逻辑比较值得一说，当服务端收到一个变更集C的时候，会做以下五件事：,比较粗浅的了解了以上和在线文档相关的一些技术，其中的一些细节实现和难题都充满了挑战，这个方向确实是道阻且长，很多看似简单的功能背后都充满着工程师的心血(比如协同中的文字选中)。,[1]diff-match-patch: https://github.com/google/diff-match-patch/tree/master/javascript,[2]diff-match-patch JS实现源码: https://github.com/google/diff-match-patch/blob/master/javascript/diff_match_patch_uncompressed.js,[3]ot.js: https://github.com/Operational-Transformation/ot.js/blob/master/lib/text-operation.js,[4]github: https://github.com/Operational-Transformation/ot.js/blob/master/lib/text-operation.js#L238,[5]etherpad-lite: https://github.com/ether/etherpad-lite,[6]demo地址: https://rich.etherpad.com/p/re3434hkj,[7]《OT协同》: https://bytedance.feishu.cn/wiki/wikcnn505JVvliIX3Z0JKJEDQqh#zdaw84,[8]Etherpad 协同概述: https://bytedance.feishu.cn/wiki/wikcnQ0bGESsmnJr6HegIno15Gg