关于编辑器:深入浅出-OpenSumi-协同编辑的原理

介绍

什么是协同

信息的传播方式有很多种，文字、语音、视频、图片符号等，传统的信息流传路径存在着老本和时效性问题，以函件举例，信息生产者须要将函件整顿撰写实现而后通过邮递寄给信息消费者。

随着互联网倒退带来的改革，使得以上这些传播方式的老本大大降低，而后又将时效性问题划分成了同步实时流传和异步非实时流传

• 同步实时流传: 视频会议、语音通话、音讯聊天
• 异步非实时流传：文档、邮件、视频、代码

同步流传的场景下，信息的产生和流传往往不须要太深的思考，而是通过多方实时的交换和探讨逐渐勾画出话题的全貌，强时效性是思维碰撞的最重要因素。

异步流传的场景下就不强调时效性，比方当你看到这篇文章的时候其实我曾经写完了（想起了影视剧里的经典台词）。在这个场景下，信息的表白更偏重准确性和丰富性，须要通过斟酌打磨才会将信息的产生流传给消费者，同时也能造成一种积淀，再度成为信息传递的载体。

而在 IDE 里写代码就是一个十分典型的异步非实时流传场景，你须要思考文件夹名称命名、架构、设计模式、逻辑实现等等，最初再将代码通过 Git 同步到近程仓库给其余消费者生产。

受限于异步流传的形式，在多人开发的我的项目上可能会产生最终各自信息载体的碰撞（其实就是代码抵触了），信息的滞后性也会导致在 code review 这件事上，须要 resolve conversation 能力看到新的后果。

那么咱们能不能在写代码这件事上引入同步实时合作的能力，让多方的信息产生者独特迭代代码，通过你来我往的反馈缩小代码抵触的产生以及代码思维的碰撞呢，答: 能。

借助云的劣势，Cloud IDE 人造的就具备代码实时协同编辑的土壤，在之前，咱们的分享合作其实只是做到了代码上的 共享 ， 你只能看到我磁盘上的代码内容后果，但却看不到我在编辑器上拼命敲打代码时的致力，是不具备传统意义上的协同的。同时，多方对文件的代码批改并没有好的算法机制来保障最终一致性，也就很容易造成抵触。

所以咱们在 OpenSumi 2.21 版本当中基于 Yjs（CRDT 理念的前端最佳实际库）实现了协同编辑模块，在代码 共享 的根底之上实现了 协同 的能力

市面上支流 IDE 的协同编辑

VS Code

通过 Live Share 插件实现多客户端的协同编辑，比方 Visual Studio 与 Visual Studio Code 协同，还能与 Visual Studio Code Web 协同。

除了能协同编辑代码还反对共享调试会话、终端等，以及视频聊天，性能是十分丰盛的

（图中是 VS 与 VS Code 协同）

IDEA

应用 Code With Me 来提供协同编辑的服务。

它不仅能反对协同编辑代码文件，还反对音视频通话、共享调试会话等，但它也并非所有 IDEA 的性能都能合作共享，比方被分享者就不容许应用 重构 相干的操作

OpenSumi 里的协同编辑

目前曾经内置了协同模块，应用形式非常简单，只须要在前端和后端模块新增 collaboration module 即可，而后提供 CollaborationModuleContribution 来自定义 user id 和 name，具体应用形式可参考文档 协同编辑模块

在此再次感激 @situ2001 对 OpenSumi 多人协同编辑模块的开源奉献：#1274

工作原理

先抛问题: 多人协同要解决的问题有什么？

问题一: 如何保障操作门路的正确性？

举个例子: 🌰

最开始 A 同学和 B 同学独特编辑同一份代码，A 先在 Index 1 的地位插入 a+=1，B 在 Index 3 的地位插入 c+=1。单方的操作会通过音讯发给对方，此时 A 承受到 B 传过来的【在 Index 3 的地位插入 c+=1】这个音讯后就会呈现右边的后果，同理，B 同学承受到 A 的音讯后，因为传过来的 A 操作不会影响到 B，所以对于 B 同学来说是正确的。

很显然，这两者最终出现进去的数据后果曾经是不统一的了

问题二: 如何解决并发抵触？

还是咱们的 A、B 两位同学

A 同学先在 Index 1 的地位新增 +1，随后接管到 B 同学传过来的【在 Index 1 的地位开端新增 +2】的音讯，最终两个人的代码批改都不合乎本人的预期，这就导致了并发抵触。

以上两个问题其实是多人协同外面最常见的也是最难以解决的顽疾，能够将其统称为 数据一致性 问题

学术上对于 数据一致性 问题，有两个次要的钻研方向:

• OT 算法: Operational-Transformation
• CRDT: Conflict-Free Replicated Data Types

如何了解 OT 和 CRDT？他们有什么区别？

OT

OT 算法顾名思义，也叫操作转换。外围逻辑是对产生的并发 操作 进行转换，通过转换对其中可能会产生的并发抵触进行修改，并返回修改后的后果，最终来保障正确性和数据一致性。

它代表着一种思维，将编辑的行为自身定义成一些原子操作，而后通过 transform 转换成另一种操作

比方 OT 对文本的操作定义成了 3 种原子行为：

• Retain: 保留操作
• Insert: 插入操作
• Delete: 删除操作

还是下面问题一的例子

A 和 B 的操作都须要通过中心化的服务去做 OT 转换

依据算法的具体实现，计算出转换后的后果，如将 B 的【insert c+=1 at Index 3】转换成了【insert c+=1 at Index 4】

那么这里的 OT 转换 能够本人去实现具体的转换算法，也能够利用社区成熟的 ot.js 库来实现

它还有一个十分好玩的可视化工具来察看操作的转换变动: http://operational-transformation.github.io/，大家能够去体验体验

CRDT

CRDT 也叫 无抵触复制数据类型， 次要是利用在分布式系统当中，多人的协同编辑也能够认为是分布式应用的一种，它的外围实质是一种数据结构的概念，正当的设计数据结构能力保障最终的一致性。它容许多个正本能够独立的更新这个数据结构，而不须要与其余正本之间进行协调

既然是分布式系统利用，那就离不开 CAP 定理了

• 一致性 (Consistency)
• 可用性 (Availability)
• 分区容错性 (Partition tolerance)

依据定理，分布式系统不可能同时满足以上三个个性

但 CRDT 在 一致性 上做了一个比拟好的衡量，它不须要保障所有的正本都是统一的，就像后面所说的，正本之间能够独立更新本人的数据结构。但它须要保障的是 最终的强一致性， 也就是说，主机与正本之间一旦音讯同步之后就能够复原一致性了，这种 最终的强一致性 是并不与 可用性 和分区容错性 抵触的

CRDT 在文档协同上的核心思想是为每一个操作的字符调配惟一的标识符，同时为了保障收敛，即便删除字符也会为此保留元数据，这就导致对内存的开销是十分大的

举个比较简单的例子🌰

• 首先 AB 代表着最初始状态

• 小 A 做了一个操作叫 C，给 C 带上一个标识符叫（A，0）

  • A 代表用户编号，0 代表操作的序列
• 而后小 A 又持续做了一个操作叫 D（A，1）
• 此时小 B 同学开始在初始状态 AB 之间做了一个操作叫 E（B，0），然而此时这个 E 操作与小 A 的 C 操作产生了并发抵触（因为他们的操作序列都是 0）
• 此时咱们假设用户编号大的作为高优先级操作，因为 B > A，最终得进去的操作程序为 AECDB

当然在实在的协同场景下，基于 CRDT 的实现必定是比这个复杂度高很多的

两者的区别

在云 IDE 的场景下，其实 CRDT 的理念会比 OT 更适宜做协同，首先它不须要依赖中心化的服务，稳定性上就十分的高，虽说在内存和性能上会有肯定的开销，但毕竟数据结构上的货色都是能够优化的

站在伟人肩膀上: Yjs

Yjs 是一个将性能施展到极致的基于 CRDT 实现的协同框架，通过简略的 API 调用就能实现多人协同的能力

数据结构建模

首先 Yjs 在工程上建模 CRDT 所用到的根底数据结构是 双向链表， 咱们称之为 Item ， 它会为每个操作所产生的字符调配一个惟一的 ID。这个惟一 ID 是带有 Lamport timestamp 逻辑工夫戳的对象，由 client（用户标示符）和 clock（逻辑工夫戳）组成

class Item {constructor (client: number, clock: number) {
    this.client = client
    this.clock = clock
    // ...more
  }
}

clock 能够认为是一个从零开始递增的计数器，他有两种更新形式

• 自更新: localClock += 1
• 当接管到近程事件时: localClock = max(localClock, remoteClock) + 1

这样的更新形式在数学上就满足了全序构造，只有再配合比拟 client 的大小，就能够保障多个对象之间是合乎逻辑上的先后关系

比方当用户顺次输出 ABC 时，会为此产生 3 个 Item，这对于大文件来说是十分吃内存的，但为了能解决并发抵触这外面的元数据信息又是须要保留的。但仔细观察能够发现这 3 个 Item 是间断的，Yjs 外部对其就做了一些优化。

通过字符偏移从新优化成了一个 Item 对象

插入优化

再看一个例子

其中 Y、A、T、A、！这几个字符都是 Item 对象，通过 left 和 right 拼接在一起，当有新的字符进来的时候会依据 ID 来决定插入到哪个适合的地位，造成新的链条。此外，同个用户继续的输出也能够被合并成 length 很长的单个 Item。

此时带来了一个问题，该设计怎么的数据结构来存储所有的这些 Item 呢？

因为所有的 Item 都能够用 ID 来排序，其中一个抉择是用 B 树这样具备低劣的插入删除工夫复杂度的数据结构，但 Yjs 抉择了一种更加简略间接的计划，既为每个 client 调配一个扁平的 item 数组

structStore: {12345: [Item, Item, Item, ...],
  12346: [Item, Item, Item, ...]
}

因为 Item 数组列表是程序的，每次插入 Item 时只须要做一次二分查找即可。

但如果以后用户在文档中任意的地位随机插入字符，新字符的 item 实践上就须要 O(N) 的工夫复杂度能力插入到链表中，为了优化插入的速度，Yjs 还设计了一层相似于跳表的缓存机制

首先在概率上大多数的插入都会追随用户最初编辑的光标地位，因而 Yjs 默认会缓存 10 个最近插入的地位来进行疾速匹配

如何解决并发抵触？

因为 CRDT 的最终一致性个性，当多个音讯节点同步的时候只有保障能衍生出雷同的状态就足够了

所以 Yjs 为了更好地妥善解决抵触，Item 内的双向链表构造内除了 left 和 right 外，还有两个字段

• origin: 字段存储 item 在插入时的左侧节点
• rightOrigin: 字段存储 item 在插入时的右侧节点

每次当 Item 被插入时都会执行外部的基于 YATA 线性数据插入算法去解决抵触

while (o !== null && o !== this.right) {itemsBeforeOrigin.add(o)
  conflictingItems.add(o)
  if (compareIDs(this.origin, o.origin)) {if (o.id.client < this.id.client) {
      left = o
      conflictingItems.clear()} else if (compareIDs(this.rightOrigin, o.rightOrigin)) {break}
  } else if (o.origin !== null && itemsBeforeOrigin.has(getItem(transaction.doc.store, o.origin))) {if (!conflictingItems.has(getItem(transaction.doc.store, o.origin))) {
      left = o
      conflictingItems.clear()}
  } else {break}
  o = o.right
}

能够了解为是保障新潜在插入 item 的左右连线不会造成穿插

配套的工程落地

Yjs 在社区上的配套开源计划有很多，比方网络音讯通信计划 y-websocket，蕴含服务端和客户端集成的 SDK

音讯通信协定 y-protocols，可用于内容更新、鉴权等

正因如此，OpenSumi 抉择基于 Yjs 的多人协同编辑计划是正确的

小结

• 支流 IDE 都具备多人协同的能力，代码共享 + 协同能力真正称之为合作
• 介绍了 OT 算法与 CRDT 的核心理念以及他们的区别
• 介绍了 Yjs 背地的工程实现原理

在 OpenSumi 上的限度

以后版本的协同模块设计还处于晚期阶段，仍有一些限度，如

• 不反对终端、调试的协同
• 不反对来自非编辑器的文件改变协同（如 git pull）
• 不反对重命名重构或其余须要跨文件级别的改变协同

以上的限度都还只是临时的，要想做好更加欠缺体感更好的协同能力仍须要一直的更新迭代以及性能补齐

最初畅想: 与 AI 联合会是什么玩法？

ChatGPT 的横空出世让 AI 这股浪潮又从新席卷而来，体验过的人都晓得它有多惊艳

那么咱们来畅想一下，既然我能与人进行协同编码，那能不能跟 AI 一起协同呢？

我写进去的代码 AI 能够实时帮我 review 以及实时帮我提出一些批改倡议，甚至在编写逻辑的过程当中，一些函数的实现也能实时的帮我写进去呢？

参考资料

• Yjs YATA 论文: https://www.researchgate.net/publication/310212186_Near_Real-…
• Yjs 作者博客: https://blog.kevinjahns.de/are-crdts-suitable-for-shared-edit…
• Yjs 的工程实现介绍: https://zhuanlan.zhihu.com/p/452980520

👇欢送理解 OpenSumi，参加开源共建～

GitHub 地址：

github.com/opensumi

OpenSumi 官网：

opensumi.com/zh

扫二维码，退出 OpenSumi 社区交换： opensumi.com/zh/communit…