在线文档 - 为什么需要 OT 算法
在线文档实时协同编辑的难点,主要在于协同冲突处理。
一、冲突处理
冲突处理的解决方案
1.编辑锁
当有人在编辑某个文档时,系统会将这个文档锁定,避免其他人同时编辑。编辑锁的实现方式简单粗暴,但会直接影响用户体验。
2.diff-patch
基于 Git 等版本管理类似的思想,对内容进行差异对比、合并等操作,包括 GNU diff-patch、Myer’s diff-patch 等方案。diff-patch 可以对冲突进行自助合并,也可以在冲突出现时交给用户处理。
3.最终一致性实现
包括 Operational Transformation(OT)、 Conflict-free replicated data type(CRDT,称为无冲突可复制数据类型)。OT 算法是 石墨文档,腾讯文档,飞书文档,Google Docs 中所采用的方案,Atom 编辑器使用的则是 CRDT。
OT 和 CRDT
OT 和 CRDT 两种方法的相似之处在于它们提供最终的一致性。不同之处在于他们的操作方式:
OT 通过更改操作来做到这一点
OT 会对编辑进行操作的拆分、转换,实现冲突处理的效果
OT 并不包括具体的实现,因此需要项目自行实现,但可以根据项目需要进行高精度的冲突处理
CRDT 通过更改状态来做到这一点
基本上,CRDT 是数据结构,当使用相同的操作集进行更新时,即使这些操作以不同的顺序应用,它们始终会收敛在相同的表示形式上
CRDT 有两种方法:基于操作和基于状态
OT 主要用于文本,通常很复杂且不可扩展。CRDT 实现很简单,但 Google、Microsoft、腾讯文档、石墨文档 和许多其他公司依赖 OT 是有原因的,CRDT 研究的当前状态支持在两种主要类型的数据上进行协作:纯文本、任意 JSON 结构。
对于富文本编辑等更高级的结构,OT 用复杂性换来了对用户预期的实现,而 CRDT 则更加关注数据结构,随着数据结构的复杂度上升,算法的时间和空间复杂度也会呈指数上升的,会带来性能上的挑战。因此,如今大多数实时协同编辑都基于 OT 算法来实现。
举个栗子
假如 A 用户看到一段初始文本,内容是 “abc”,然后 A 想 第 3 个位置后面,插入"d" => "abcd"假如 B 用户看到一段初始文本,内容是 “abc”, 然后 B 想在第 3 个位置后面插入"e" => "abce"
不做锁处理或者丢处理,那我们就保留最大内容(A,B 先后执行),应该是 "abcde", 如何按实际执行结果来看:
如果各自操作,没有 OT 算法的处理,那么 A 看到的内容就会是 "abced"(A 在第 3 个位置后面,然后 B 想在第 3 个位置后面插入"e" => "abce"),对于 B 用户而言,他实际上得到了一个顺序执行,就是 B 想在第 3 个位置后面插入"e" => "abce ", 然后 A 想 第 3 个位置后面插入"d",最后得到的就是 "abcde", B 的结果刚好复合,这个时候 B 是对的,A 就是错的,所以 A 最终看到的不应该是原始的 B 操作,而是转化后的 B' 操作,他应该得到 "B 想在第 4 个位置后插入 e",因此,我们要引入一个 OT 算法,最终结果:
文本内容 = A 内容 x B' = A 内容 x follow(A,B) = merge(A,B) = B 内容 x A' = B x follow(B,A)
Follow 函数的第一个参数代表第一个执行的操作,第二个参数代表后执行的操作
Merge 代表合并后的最大可用集合
二、关于服务器设计
服务器中维护了一系列历史的修改版本,例如 r1,r2,r3,…r100,…r110
假如某个客户端提交的变化 C,是基于 R100 的,这时候,我们需要不停的产生变化 newC = follow(R101,C) , 然后 newC = follow(R102,newC),不断执行,最后要得到针对 r110 这个版本的 newC 变化,推送到各个客户端
ot.js的核心实现
三、 OT 算法可视化
http://operational-transformation.github.io/visualization.html
更多参考:
https://www3.ntu.edu.sg/home/czsun/projects/otfaq/
http://operational-transformation.github.io/ot-for-javascript.html
https://segmentfault.com/a/1190000019827632
http://operational-transformation.github.io/visualization.html
版权声明: 本文为 InfoQ 作者【张驰Terry】的原创文章。
原文链接:【http://xie.infoq.cn/article/a6fad791493bf4f698781d98e】。文章转载请联系作者。
评论