深入浅出 OpenSumi 协同编辑的原理

站长

2024年04月15日 21:27 · 阅读数 41

介绍

什么是协同

信息的传播方式有很多种，文字、语音、视频、图片符号等，传统的信息传播途径存在着成本和时效性问题，以信件举例，信息生产者需要将信件整理撰写完成然后通过邮递寄给信息消费者。

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

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

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

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

而在 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 协同。

除了能协同编辑代码还支持共享调试会话、终端等，以及视频聊天，功能是非常丰富的

深入浅出 OpenSumi 协同编辑的原理（图中是 VS 与 VS Code 协同）

IDEA

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

它不仅能支持协同编辑代码文件，还支持音视频通话、共享调试会话等，但它也并非所有 IDEA 的功能都能协作共享，比如被分享者就不允许使用重构相关的操作

深入浅出 OpenSumi 协同编辑的原理

OpenSumi 里的协同编辑

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

深入浅出 OpenSumi 协同编辑的原理

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

工作原理

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

问题一: 如何保证操作路径的正确性？

举个例子: 🌰

深入浅出 OpenSumi 协同编辑的原理

最开始 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 两位同学

深入浅出 OpenSumi 协同编辑的原理

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: 删除操作

还是上面问题一的例子

深入浅出 OpenSumi 协同编辑的原理

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 在文档协同上的核心思想是为每一个操作的字符分配唯一的标识符，同时为了保证收敛，即使删除字符也会为此保留元数据，这就导致对内存的开销是非常大的

举个比较简单的例子🌰

深入浅出 OpenSumi 协同编辑的原理

首先 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 的大小，就可以保证多个对象之间是符合逻辑上的先后关系

深入浅出 OpenSumi 协同编辑的原理

比如当用户依次输入 ABC 时，会为此产生 3 个 Item，这对于大文件来说是非常吃内存的，但为了能解决并发冲突这里面的元数据信息又是需要保留的。但仔细观察可以发现这 3 个 Item 是连续的，Yjs 内部对其就做了一些优化。

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

深入浅出 OpenSumi 协同编辑的原理

插入优化

再看一个例子

深入浅出 OpenSumi 协同编辑的原理

其中 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 的左右连线不会形成交叉

深入浅出 OpenSumi 协同编辑的原理

配套的工程落地

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 地址：

OpenSumi 官网：

转载自:https://juejin.cn/post/7224426218929913917