1.

2. 协同编辑原理与实践 沙洲 @ 阿里巴巴 钉钉

3. • 2004年，上海交通大学（计算机科学与技术） • 2008年，微软亚洲工程院 • 先后负责Excel for Mac/Excel for iOS/Excel Next项目 开发，深耕表格文档格式，多人协同编辑，排版渲染 等领域 • 2015年，微软互联网工程院 • 任必应广告平台前端架构师，负责推进广告平台的 SPA化及前端组件化 • 2019年初，阿里巴巴钉钉 • 主要负责钉钉文档产品研发，致力于打造一款属于中 国的，业界一流的协同文档产品。

4. 协同文档革命

5. 文档与协同 信 息的 同步 传播 ： 信 息被 生产 的同 时被消 费 信 息的异步传播 ： 信 息的生产和消 费异步发生 IM 语音通话 论坛 视频会议 文档库 邮件 博客

6. Google Docs - 2019年3月 多人实时编辑

7. 协同文档带来的变革 传 统文 档： 信息 的异步 传播 协 同文档：信息 的同步 + 异步传 播 Lorem ipsum dolor sit amet, at mel choro ullamcorper. Te everti iuvaret duo, no per corpora senserit laboramus, ipsum debitis ius at. Has nisl malis eirmod eu, usu persius epicuri intellegat te. Est ex impedit nominati, esse vide tota nam id, cu vel vidit postea posidonium. Lorem ipsum dolor sit amet, at mel choro ullamcorper. Te everti iuvaret duo, no per corpora senserit laboramus, ipsum debitis ius at. Has nisl malis eirmod eu, usu persius epicuri intellegat te. Est ex impedit nominati, esse vide tota nam id, cu vel vidit postea posidonium. Vel in alii lorem solet, duo an malis detracto vivendum. Homero utamur et vim, an tibique mediocrem cum, dico epicurei complectitur vel id. Vim cu legendos inimicus liberavisse, legendos laboramus ut usu. Ad iusto populo percipitur sea. Perfecto insolens te nam, iuvaret delectus ei eos. An perpetua gubergren mel, eum te stet assentior rationibus, te eam solum autem iudicabit. Vel in alii lorem solet, duo an malis detracto vivendum. Homero utamur et vim, an tibique mediocrem cum, dico epicurei complectitur vel id. Vim cu legendos inimicus liberavisse, legendos laboramus ut usu. Ad iusto populo percipitur sea. Perfecto insolens te nam, iuvaret delectus ei eos. An perpetua gubergren mel, eum te stet assentior rationibus, te eam solum autem iudicabit. Hinc decore persecuti at nam. Quod regione ex vis. In vim laudem detracto deseruisse, no docendi salutandi eam. Diam hinc nostrud ea vis. In iusto altera labitur pri. Hinc decore persecuti at nam. Quod regione ex vis. In vim laudem detracto deseruisse, no docendi salutandi eam. Diam hinc nostrud ea vis. In iusto altera labitur pri. Soleat euripidis vel ut. Cu vix soleat explicari. Cu pri virtute convenire. Ne novum debitis delicatissimi vim. Eam denique efficiendi ne, eu mei justo dicunt salutatus. Quo dictas similique definitionem ad, ius duis justo elitr ea. Soleat euripidis vel ut. Cu vix soleat explicari. Cu pri virtute convenire. Ne novum debitis delicatissimi vim. Eam denique efficiendi ne, eu mei justo dicunt salutatus. Quo dictas similique definitionem ad, ius duis justo elitr ea. Vix ut illum corrumpit, utroque pertinax no mea, sea cu copiosae nominati concludaturque. Ne nam malis equidem mediocrem, in viris utamur repudiandae cum, eum minim dicit vivendo cu. Iusto regione eruditi duo ut, quo ad laudem audire definiebas. At duo solet suscipit periculis. Vix ut illum corrumpit, utroque pertinax no mea, sea cu copiosae nominati concludaturque. Ne nam malis equidem mediocrem, in viris utamur repudiandae cum, eum minim dicit vivendo cu. Iusto regione eruditi duo ut, quo ad laudem audire definiebas. At duo solet suscipit periculis.

8. 协同文档带来的变革 讲人话： 文档从此成为一块在线的白板！ 1 Lorem ipsum dolor sit amet, consectetur adipiscing elit. Duis facilisis lacinia ipsum id pharetra.

9. 协同文档发展历程 1989 OT算法提出 Microsoft Office 1998 ACM SIGCE 2006 Google Docs 2011 Office 365 2018 钉钉文档

10. 协同编辑器原理

11. 基础编辑器

12. 协同编辑器

13. 协同编辑器 DATA SERVICES BROWSER APP SERVER BROWSER BROWSER

14. 协同编辑与群消息

15. 协同编辑就是群聊天吗？ 没那么简单 只发消息，别的全不看

16. 数据一致性问题

17. 数据一致性问题 相同的操作，基于不同的状态，会产生不同的效果 Insert, 4, “ ”

18. 操作变换 (Operational Transformation) 0 1 5 6 2 3 7 4 8

19. 引入操作变换

20. 操作变换看上去很简单嘛！ 光有OT还不够 协同调度协议也非常重要

21. 协同调度协议

22. 客户端与服务端通讯的基本句式 X Y1 APP SERVER X O1, O2, O3 Y O4, O5 Y Z X1 BROWSER X2 Y Z

23. 通用调度协议 (Generic OT) 1 2 1 2 BROWSER A APP SERVER 1 BROWSER B 3

24. 通用调度协议 (Generic OT) 1 2 1 2 4 APP SERVER BROWSER B 3 4

25. GOT的优缺点 优点 • 简单通用 • 各端操作序列相同，数据一致性与 OT 算法无关 • 只有客户端需要做 OT 缺点 • 操作可能被打回，性能差 • 支持的协同人数比较有限

26. 操作打回就没有办法避免吗？ 当然有办法！ 咱们来看看另一种调度协议。

27. 基于上下文调度协议 (Context-based OT) 1 2 APP SERVER 1 3 4 3 4 BROWSER B 5 6

28. GOT的优缺点 优点 • 无需打回，性能出色 • 支持更大规模的协同编辑场景 缺点 • 实现难度大 • 服务端、客户端都需要做 OT • 各端操作序列不同，一致性依赖于 OT 算法

29. OT 算法的优化

30. OT 算法的复杂度 O(M * N) K * K

31. OT 算法的复杂度 时 间复 杂度 O(M * N ) Y[0, 1] X[1, 0] Y[1, 0] S[2, 0] X[2, 0] S[2, 1] X[1, 1] S[3, 1] OT[1, 1] OT[1, 2] OT[1, 3] OT[1, k] Op[2] OT[2, 1] OT[2, 2] OT[2, 3] OT[2, k] Op[3] OT[3, 1] OT[3, 2] OT[3, 3] OT[3, k] Op[k] OT[k, 1] OT[k, 2] OT[k, 3] OT[k, k] S[1, 2] Y[1, 2] X[2, 1] Y[2, 1] X[3, 0] Op[1] Y[0, 2] Y[1, 1] Y[2, 0] S[3, 0] S[1, 1] S[0, 2] Op[k] … S[1, 0] X[0, 1] Op[3] … Y[0, 0] S[0, 1] Op[2] … X[0, 0] Op[1] … S[0, 0] 实 现复杂度 K * K S[2, 2] Y[2, 2] X[3, 1] S[3, 2]

32. OT 算法优化的总思路 减少可能冲突的操作数

33. Google Docs – 操作合并 First Streaming Operation Resulting Composition Operation Composer Second Streaming Operation

34. 钉钉文档 - 冲突域拆分 • 切片 • 只对切片内操作做 OT • 同类型切片 OT 算法可复用 1 2 3 n • 纯函数 • 切片一致性 → 模型一致性

35. 一个简单的例子

36. 如何设计一个协同脑图

37. 模型拆分

38. 树结构操作 • 2种操作 0 • 创建：Add(idSibling, id, idChild) 1 2 3 • 移动：Move(idSibling, id) • 4个 OT 函数 2 • 客户端创建 v.s. 服务端创建 • 客户端移动 v.s. 服务端创建 4 5 3 6 7 • 客户端创建 v.s. 服务端移动 • 客户端移动 v.s. 服务端移动 5 6 8 9

39. 映射表操作 • 1种操作 • 属性赋值：Set(id, value) • 1种 OT 函数 0 1 • 客户端赋值 v.s. 服务端赋值 2 3 4

40. 思考题：树结构和映射表的 OT 算法分 别要怎么实现呢？

41. 参考资料汇总 Operational Transformation Frequently Asked Questions and Answers 南洋理工大学教授Chengzheng Sun的Survey，覆盖了OT领域绝大多数研究成果 Google Wave Operational Transformation G-Suite协同引擎的协议白皮书 Achieving convergence, causality-preservation, and intention-preservation in real-time cooperative editing systems GOT算法及一维数据操作变换算法论文 Context-based Operational Transformation in Distributed Collaborative Editing Systems COT算法论文

42. 今天的分享就到这里 谢谢大家！