Appearance
文档协同编辑能力 - OT 算法
🗿 认识协同编辑
🤔 什么是协同编辑
协同编辑是指多个用户同时对同一个文档或项目进行编辑和修改的过程。在协同编辑中,多个用户可以在实时或异步的情况下共同编辑文档并观察其他用户的编辑内容。
👌 协同编辑好处
- 实时协作
- 提高生产力
- 减少冲突和错误
- 简化版本控制
那如何实现协同编辑呢❓ 这里主要用到了协作算法 OT
市场上有很多文档使用了 OT
算法 ,例如:
- 讯飞文档
- 石墨文档
- 腾讯文档
- Google Docs
🤖 认识 OT 算法
🙋🏻♂️ 先来看看有哪些处理冲突的方式
- 加锁:某一文档或段落同时只运行一个用户编辑,例如用户
A
在编辑时,就锁住文档或段落,只能A
进行更新。用户B
就不能编辑,或编辑后提交修改被服务器丢弃; - 覆盖: 谁最后修改,就全量使用他的修改,更早一些的其他人的修改会被丢弃;
- 用户自行处理冲突: 就像
git merge/rebase
导致的冲突一样,会提示哪个地方被同时修改了,让合并者手动选择使用哪一个修改; - 使用一致性算法: 比如接下来要介绍的
OT
算法,多用户编辑进行算法处理调整,在多个客户端生成一致的修改结果。
什么是 OT 算法
OT ( Operational Transformation )
, 是一种基于操作转换的协同冲突处理的收敛算法; 它的基本原理是通过对操作的转换和合并,确保多个用户同时编辑时的最终结果上的一致性。
操作
这里的 操作 指的对文档的编辑,在 OT
里面对文档定义了三种操作:
- insert 插入操作
- retain 保留操作
- delete 删除操作
e.g. 插入 insert e.g. 保留 retain
e.g. 删除 delete
那 转换 和 合并 指的什么呢? 继续往下 ⬇️
💭 首先看下协同编辑为什么需要 OT 算法
举个 🌰 ,多人编辑在没有 OT
算法会出现什么情况 假设现在一个协作的文档初始内容是 hello
,甲乙都在同时编辑,甲端用户在 hello
后面插入了一个 a
,乙端用户在 hello
后面插入了一个 b
;
1️⃣ 对于甲客户端:
- 插入了
a
后,文档内容变成helloa
- 然后接收到 乙端 的消息, 在
helloa
后面插入b
- 最终文档内容变为
helloba
2️⃣ 对于乙客户端:
- 插入了
b
后,文档内容变成hellob
- 然后接收到 甲端 的消息, 在
hellob
后面插入a
- 最终文档内容变为
helloab
将上述内容的量化为模型图 :
此时这时候 甲 乙 双端已经不一致了,即产生了冲突。
解决冲突 Transfrom
继续上述的 🌰 :
甲乙 内容出现了不一致, 那谁应该才是正确的呢 ? 对于 OT
算法强调是最终一致性, 所以 helloab
或 helloba
似乎看起来都是正确的。
但是从服务端视角来看, 先到的操作先应用原则:
假如 甲 操作先到达服务端, 乙 操作后到达服务端:
甲端 内容先变成
helloa
,准备应用O2
操作(乙) ,先与O1
操作进行一个转换O2' = Transfrom(O2, O1) = insert(6, 'b')
, 因为在O2
操作前,O1
在位置5
已经插了一个字符, 所以 需要将位置+1
,再应用转换后的O2'
乙端 内容先变成
hellob
, 准备应用O1
操作(甲),先与O2
操作进行一个转换O1' = Transfrom(O1, O2) = insert(5, 'a')
, 因为 甲操作在先,在第5
位置插入a
对乙操作其实不会有影响
如果 乙 操作先到达服务端, 甲 操作后到达服务端,情况就正好与上面相反
从上面的案例看出
Transfrom
是核心解决冲突的所在,对操作进行转换;同时也可看出 时序性对OT
的算法的重要性, 这个确定了操作之间应该如何去转换。Transfrom
操作既发生在服务端:将基于某个版本的并发操作对象转换成串行操作;也发生在客户端,本地的修改还没来得及提交,就收到了服务端推送。
同时上面的案例是一个并行插入冲突的实例,还有常见的并行删除操作冲突、插入和删除操作的冲突等;
并行删除操作: 同时在同一位置进行删除操作
插入和删除操作: 同时在同一位置进行新增和删除操作
数据合并 compose
合并操作
- 合并操作序列
- 合并操作到文档
举个 🌰 文档初始内容为 hello
- 甲用户先在
hello
后面(第5
位置)插入了world
- 在
helloworld
后面(第10
位置)插入了 ! - 删除了
world
(从第5
位置开始到第10
位置) - 在
hello
后面(第5
位置)插入了ot
如果将 4
步操作合并为 1
步操作:
- 在
hello
后面插入了ot!
需要 compose 的场景:
- 短时间内频繁的操作可以进行合并,以减少提交次数以及版本数
- 离线编辑是大量的操作可以进行合并
- 历史记录查看一段时间内的操作集合
- 应用到文档中
👓 可视化示例 (基于 OTjs 和 CodeMiror 编辑器实现):
Visualization of OT with a central server (operational-transformation.github.io)
🤏 OT 算法在文档中的应用 - Delta
文档中的文字文档采用的是 Quill
富文本编辑器 如下图 Quill
简化的架构:
- Quill Core : Formats 、插件模块、主题等
- Delta :富文本数据层,负责描述数据
- Parchment :富文本控制器层,可以理解为抽象的 dom
Delta
Delta
主要负责文本操作和格式化。是基于 OT
算法实现。
数据结构 / 设计规范
Delta
中数据插入类型分为 纯文本 与 embed
嵌入式内容。通过 attributes
区分不同的表现形式,应用场景例如我们常见的 标题、加粗、斜体、列表等。
- 扁平化数据
- 紧凑型
扁平化数据
Delta
中数据都是扁平的,没有子节点。那他如何表达 文档 Dom
树结构的? 关键在于 Quill
假定富文本不存在块元素的嵌套,即一行中不能同时存在标题和列表。遇到换行符则新建一行作为块级别 tag open
,直到遇到下一个换行符,作为 tag close
。
javascript
var content = [
{
insert: 'Hello',
},
{
insert: 'World',
attributes: { bold: true },
},
{
insert: {
image: 'https://quilljs.com/logo.png',
},
attributes: { width: '100' },
},
]
如上述代码中 image 就是一个 embed 类型,这种嵌入类型的文本长度为
1
, 类似于一个文字长度。
紧凑型
必须约定 Delta
中的数据格式标识形式,同一个富文本仅有一种数据表示形式,否则同一种数据可能存在不同表示,例如表示 Hello Word
的不紧凑形式:
javascript
var content = [
{ insert: 'Hel' },
{ insert: 'lo' },
{ insert: 'World', attributes: { bold: true } },
]
下面的方式更明确,易于理解和维护:
javascript
var content = [
{ insert: 'Hello' },
{ insert: 'World', attributes: { bold: true } },
]
部分核心算法实现
🍗 Push
- Insert 插入
- Retain 保留
- Delete 删除
主要是处理富文本操作的一些场景,核心主要是一下:
- 连续的
insert
、retain
、delete
需要判断做合并操作,对于insert
、retain
则是attrs
相同且insert
都为string
即可合并,
javascript
// 例如
new Delta().insert('hello').insert('world')
// push后
new Delta().insert('helloworld')
javascript
// 例如
new Delta().insert('hello').insert('world').retain(3).insert('!')
// push后
new Delta().insert('helloworld').retain(3).insert('!')
delete
之后的insert
,会做顺序调整, 规范是放到insert
后面(因为由于在同一索引处的删除之前或之后插入并不重要,因此始终倾向于先插入);
javascript
new Delta().insert('hello').retain(3).delete(2).insert('!')
- 其他场景则直接
push ops
即可。 这主要是为了ops
数据格式的一致性,为了之后的各种操作运算做逻辑统一化处理。
🍟 Compose 合并操作 compose 合并文档,中有几条原则,决定计算规则:
insert
/delete
/retain
,类型相同时选择性直接合并;insert
优先于delete
;delete
、retain
同时存在时,按先后顺序执行;
javascript
const a = new Delta().insert('hello')
const b = new Delta().retain(5).insert('o')
const c = new Delta().retain(6).insert('t')
a.compose(b).compose(c)
🍔 Transform 转化
根据已有的 Delta
操作转换给定的 Delta
。 示例如下:
javascript
const a = new Delta().insert('12').retain(1).insert('34')
const b = new Delta().insert('ab').retain(1).insert('cd')
a.transform(b, true) // new
// 结果
new Delta().retain(2).insert('ab').retain(3).insert('cd')
该方法也是解决冲突的核心方法, transform
方法内部通过 Delta
数据建立两个单链表通过比较两个对象的操作序列,并根据一定的规则进行变换,从而解决冲突并保持编辑操作的一致性。
下面的 ①②③④ 指的遍历次数
e.g. 文档处理中文输入中间态 composition
来自讯飞文档中一些经验说 讯飞文档对富文本编辑器其实做了大量的定制化开发和优化;
- 中文输入法适配
- 扩展组件: 例如附件预览、多
meta
信息的图片以及图片操作、@功能 - 版本兼容
- 系统适配
- 大文档的性能优化: 数据懒加载
- 移动端适配
- 离线数据一致性问题
- 等等 ...
富文本编辑器本身也是一个很复杂的模块,感兴趣的我们可以会后继续探讨 🔬。
📡 拓展: CRDT 算法以及 Yjs
CRDT
(Conflict-free Replicated Data Type,无冲突复制数据类型)算法的核心思想是确保所有副本之间的数据一致性,而无需进行复杂的操作转换。
CRDT
算法的关键思想是将数据结构设计成满足局部操作的可交换性和结合性。这意味着每个节点可以自主地对其本地副本进行修改,并通过将其修改操作与其他节点的操作合并,最终实现数据一致性。
Yjs
一款强大的基于 CRDT
算法实现的协同编辑 JavaScript
库
- 数据操作要满足交换律、结合律和幂等性
- 基于
YATA
算法的并发冲突解决机制