一个实时协作文档的诞生

用户管理凡是企业都是需要的

一直以来,协会打比赛时所使用的协作文档都是 HackMD,这是一个使用 NodeJS 编写的可自主部署的在线 Markdown 协作应用。用了这么多年了,HackMD 的一些弊端和痛点也暴露了出来。
* 没有完备的用户管理
* 文档不能细致的分类分组
* 在线编辑器有时候光标显示错误

因此,我萌生了自己造轮子写一个协作文档的想法。这是今年暑假一拍脑袋做的决定,没有过多地调研这个应用其背后的难点及其解决办法,以至于直接被知乎上的回答给吓住了。大家都说自己开发一个协作文档十分的困难,我看 HackMD 的源码也是一头雾水,自己尝试去魔改前端的 CodeMirror 编辑器也一无所获,所以这个想法在当时便被搁置了。

但是在那之后的一天,我看到了这个项目:https://github.com/petejkim/ot.go
一个使用 Go 实现的在线协作 Demo!代码量超少,但是功能却几乎齐全!我只需要基于它的基础上,完善一下用户系统,做做权限验证,文档管理,一个崭新的实时协作文档应用就能诞生了!

当个缝合怪!

确实,我只需要当个缝合怪将现有的各种 Demo 东拼拼西凑凑串联起来就行。但是我又不甘心于当个缝合怪,便尝试去了解协作文档背后的原理。

关于如何实现多人的实时协同合作,其难点在于如何让同时在线的人们,互相之间穿插着对文字不同的部分进行这增、删、改操作,每个人的终端能实时更新对方的操作,能保证每个人屏幕上显示的都是相同内容的文本,也就是保持一致性。
学术界对于这个问题其实一直都在争论不休。不断有新的研究和新的算法被提出,但目前貌似也没有一个十全十美的解决方案。

有两种比较常用的算法:Operational Transformation(OT)操作转换、Conflict-free Replicated Data Types(CRDT)无冲突复制数据类型。上面我提到的那个项目,就是使用 OT 算法实现的在线协作。

Operational Transformation

这里我们只讨论纯文本的实时协作的实现,关于富文本、表格、图形等操作暂且不谈。

关于纯文本的所有处理,我们其实都可以将其归纳为由无数个“添加” insert 与“删除” delete 这样的原子操作组成。那么来看这样一个例子:
现在有一段文本:

abcd

目前有两个人,A 和 B 在同时对这段文本进行编辑。

A 在字母 b 后面输入了一个 e ,即 insert('e', 2) ,那么文本变成了 abecd
B 删除了第三个字母 c ,即 delete(3) ,那么文本变成了 abd

接下来,我们需要将这两个操作合并,得出最终文字的样子。
先从常识上来判断,合并操作后我们希望得到的最终结果应该是:

abed

那么再来实际执行:
对于 A, 先 insert('e', 2)delete(3),A 所看到的文本变为:abcddelete 操作在错误的索引上删掉了刚输入的e
对于 B,先 delete(3)insert('e', 2),B 所看到的文本变为:abed

可以发现上述过程中只有 B 是获得了我们期望的结果,问题出在我们只是单纯的把相对于一方的修改操作原封不动地堆叠应用在了另一方上面,导致了错误。就比如 A 执行的 delete(3)c 的下标在 A 添加了 e 之后已变为了 4。
A 应该执行操作 insert('e', 2)delete(4) 才能获得正确的结果。

也就是说,在一个客户端的操作信息经由服务端转发给另一个客户端时,服务端需要对操作信息进行转换,这样才能保证接收的客户端更新文本后大家的内容都一致。这就是为什么 OT 名为操作转换。

我们稍微再专业一些,A 对文本的操作 x1,B 对文本的操作为 x2。定义一个转换函数 f,用于合并转换来自两个不同客户端的操作。
对于客户端 A 而言,他要执行 x1′ = f(x1, x2);对于客户端 B 而言,他要执行 x2′ = f(x2, x1)。从而使得两个客户端显示的内容相同。

用图形描述就像是:

这就是 OT 算法里经典的菱形图。

但这只是在 A、B 两个客户端起始的内容是相同的情况下,也就是他们的起点是一样的。如果因为网络等其它原因,A、B 两个客户端开始的版本不同;比如 A 从第 10 个 revision 版本开始,B 从第 20 个 revision 版本开始。那么他俩产生的操作,不能简单的进行合并。

这就是 OT 算法中的时序问题,而解决这个问题的精髓在于,将客户端所处的状态进行划分,并进行对应的处理:

  • Synchronized 没有正在提交并且等待回包的操作。
  • AwaitingConfirm 有一个操作提交了但是等后端确认,本地没有编辑数据。
  • AwaitingWithBuffer 有一个操作提交了但是等后台确认,本地有编辑数据。

但以上这些如果要深究其具体实现,将十分复杂。我目前也只是勉强懂了这些粗浅的概念,具体情况下的策略的代码实现我看得真的头大。🤣 算了算了

Google Doc 就是使用 OT 算法实现协同编辑,前 Google Wave 工程师、ShareJS 作者 Joseph Gentle 表示:

Unfortunately, implementing OT sucks. There’s a million algorithms with different tradeoffs, mostly trapped in academic papers. […] Wave took 2 years to write and if we rewrote it today, it would take almost as long to write a second time.

哈哈哈,那既然如此,我也就不再花过多的时间纠结 OT 背后的具体实现了。专心于做项目需求吧~

目前的进度

目前 EggMD 还是在处于开发过程中,不过进度不会很快。基本上是我在工作之余有空会写一点功能。当下的重心是把文档的编辑过程进行优化,用户权限系统等还只是有个雏形。

如果你真的真的十分感兴趣,同时又不介意的话,可以看看目前线上的一个版本尝尝鲜:https://try.eggmd.io/
因为她目前还处于原型状态实在是太简陋了,所以都没好意思放出来,只是让协会的同学们玩了下。



喜欢这篇文章?为什么不打赏一下呢?

0 条评论

 

昵称

快来评论~