深入浅出 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 库来完成

它还有一个十分好玩的可视化东西来观察操作的转化改变: 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 的完成肯定是比这个复杂度高许多的

两者的差异

OT	CRDT
需求依靠一个中心化的服务来做 OT 转化	去中心化，能够直接 P2P
需求依靠复杂度高的算法确保共同性	经过数据结构的规划来确保共同性
几乎不占用内存	需求必定的内存开支
完成简略	完成难度较大

在云 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 论文: www.researchgate.net/publication…
• Yjs 作者博客: blog.kevinjahns.de/are-crdts-s…
• Yjs 的工程完成介绍: zhuanlan.zhihu.com/p/452980520

欢迎了解OpenSumi，参加开源共建～

GitHub 地址：

github.com/opensumi

OpenSumi 官网：

opensumi.com/zh

扫二维码，加入 OpenSumi 社区沟通： opensumi.com/zh/communit…