协同编辑中使用的 OT 算法是什么?
大家好,我是前端西瓜哥,今天我们来聊聊 OT 算法是什么。
OT 的英文全称是 Operational transformation,是一种处理协同编辑的算法。
它常用于实现协同文档的底层算法,支持多个用户同时编辑文档,不会因为并发修改导致冲突,而使结果不一致或数据丢失。
冲突的处理方式
假设 A 和 B 在同时编辑同一个内容,我们处理冲突的方式有:
- 加锁。用户 A 在编辑时,就锁住文档,只能 A 进行更新。用户 B 就不能编辑,或编辑后提交修改被服务器丢弃;
- 覆盖。谁最后修改,就全量使用他的修改,更早一些的其他人的修改会被丢弃。
- 用户自行处理冲突。就像 git merge 导致的冲突一样,会提示哪个地方被同时修改了,让合并者手动选择使用哪一个修改;
- 使用一致性算法。比如我们要介绍的 OT 算法,可以让用户编辑进行算法处理进行调整,在多个客户端生成一致的修改结果。
对于在线协同文档,
加锁体验太差,一个人在编辑时其他人就要干等着。
覆盖则是导致用户的修改来回彼此覆盖,辛苦编辑的内容突然被别人覆盖掉了心情低落。
自行处理冲突则需要额外的操作步骤和成本,实时性很差,不适合高频同时修改的场景。
一致性算法是最好的选择,对用户最友好,不过带来了实现的复杂。
一致性问题
我们先来看看不使用 OT 导致的冲突问题。
假设用户 A 和用户 B 同时在编辑同一个文档,文档内容为 “12”。
- 用户 A 在末尾添加一个字符 “A”,这个修改先应用在本地,内容变成了 “12A”,之后客户端发送一个数据
insert(2, "A")
给服务端,代表在位置 2 的地方插入 “A”。服务端会将修改消息推送给其他客户端,但这需要时间; - 用户 B 在收到推送消息前,也在 “12” 的尾部添加了内容 “B”,在本地变成了 “12B”,并将
insert(2, "B")
的修改描述提交服务器; - 用户 B 收到了
insert(2, "A")
消息,应用后,将 “12B” 变成了 “12AB”; - 用户 A 则收到
insert(2, "B")
消息,应用后,将 “12B” 变成了 “12BA”;
结果是,用户 A 看到的内容是 “12BA”,用户 B 看到的内容是 “12AB”,内容不一致,不符合预期。
使用 OT
OT 算法可以解决一致性问题,我们来看看 OT 到底做了什么。
同样,原始内容是 “12”。
- 用户 A 在末尾添加 “A”,本地变成 “12A”,并发送
insert(2, A)
,这个操作计作 OA; - 用户 B 在末尾添加 “B”,本地变成 “12B”,并发送
insert(2, B)
,这个操作计作 OB; - 用户 A 收到 OB,执行
transform(OA, OB)
,得到修正后的操作insert(3, B)
,记为 OB',相比 OB,它将插入位置从 2 修正为 3,于是 "12A" 变成了 “12AB”; - 用户 B 则收到 OA,同样执行
transform(OA, OB)
,得到修正操作insert(2, A)
,记为 O1',让内容从 "12A" 变成 “12AB”。transform 方法会同时产生 OA' 和 OB'。
最后,用户 A 和用户 B 看到的是 一致 的 “12AB”。
这里的核心在于这个 transfrom
方法,它能够对操作进行修正。transform 没有固定实现,要根据实际需求自行实现。
这里有一个经典的菱形示意图。
从起始版本 S 开始,它接受了两个 并发操作 A 和 B。我们使用 trasform 方法生成 A' 和 B'。我们有:
S + A + B' = T
S + B + A' = T
这样,从 S 得到相同的 T,保证了一致性。
下面使用了 ot.js 库,演示了一下从 '12' 到 '12AB' 的过程。
const s = '12'; // 原始文案(版本 1)
// 在位置 2 插入 'A'
const oA = new TextOperation().retain(2).insert('A');
// 上述操作后得到结果 '12A'(版本 2)
const t1 = oA.apply(s);
// 收到 oB 操作:在位置 2 插入 'B'
const oB = new TextOperation().retain(2).insert('B');
// transform 拿到修正后的 [oA', oB']
// 我们这里只需要 oB',它被修正为在位置 3 插入 'B'
const [oAp, oBp] = TextOperation.transform(oA, oB);
// 应用 oB',结果为:12AB (版本 3)
const t2 = oBp.apply(t1);
线上 demo 链接为:
https://codesandbox.io/s/b8ds8h
transform 操作既发生在服务端:将基于某个版本的并发操作对象转换成串行操作。
也发生在客户端,本地的修改还没来得及提交,就收到了服务端推送。
如果你想要深入研究 OT 算法,可以考虑参考 ot.js 库的代码实现,里面还附带了一个 OT 可视化过程
https://github.com/Operational-Transformation/ot.js/
结尾
OT 算法能够在实时保证多个客户端数据的一致性,被广泛用于协同编辑场景。
我是前端西瓜哥,欢迎关注我,学习更多前端知识。
相关文章
- ☆打卡算法☆LeetCode 221. 最大正方形 算法解析
- xgboost分类算法_python分类统计
- 【嵌入式案例分享】使用Matlab生成可供TMS320C6748开发板使用的算法
- 阶乘算法挑战「建议收藏」
- 日拱算法:双指针解“判断子序列”,除夕快乐~
- murmurhash算法_shell dash使用数组
- gbdt算法_双色球最简单的算法
- 路径匹配之编辑距离ED算法
- 安卓dtmf识别_使用Goertzel算法识别DTMF信号
- 前端工程师leetcode算法面试之二分搜索算法(下)
- 七日算法先导(七)——字符串
- 推荐系统[一]:超详细知识介绍,一份完整的入门指南,解答推荐系统相关算法流程、衡量指标和应用,以及如何使用jieba分词库进行相似推荐
- 【数据挖掘】数据挖掘算法 组件化思想 示例分析 ( 组件化思想 | Apriori 算法 | K-means 算法 | ID3 算法 )
- Java使用HMAC-SHA1算法详解编程语言
- 算法-数组中只出现一次的数字详解编程语言
- AI 和机器学习中暗含的算法偏见
- 最新出炉——数据科学家最常使用的十大算法
- MySQL 数据库压缩备份:使用 Zip 算法快速高效压缩数据!(mysqlzip)
- 技术大牛带你走向机器学习“正道”:小朋友才迷信算法,大人们更重视工程实践
- 使用SQLserver算法获取日期的星期信息(sqlserver取星期)
- 使用Redis实现数据去重算法(使用redis对数据去重)
- 使用PHP实现二分查找算法代码分享
- java使用简单的demo实例告诉你优化算法的强大
- php生成数组的使用示例php全组合算法
- VB.NET中使用种子填充算法实现给图片着色的例子