前言
hi，大家好，我是徐小夕，之前和大家分享了很多可视化低代码的技术实践，最近也做了一款非常有意思的文档搭建引擎——Nocode/Doc：
接下来和大家分享另一个比较有意思的话题——多人协同技术。
文章大纲
- 多人协同技术方案探讨
- OT和CRDT算法
- 插曲（互斥锁（Mutex）原理和代码实现）
- yjs协同框架使用
- yjs多人协同案例
多人协同技术方案探讨
多人协同技术方案常见的应用场景主要有：
- 原型工具（axure，某刀，mastergo等）
- 文档办公类 （飞书文档，钉钉文档，石墨文档等）
- 设计工具（即时设计，figma等）
主要目的是实现多个人同时编辑一份共享资源, 来提高工作效率。
抛开已有技术本身，我们拿最简单的富文本编辑器为例子， 如果我们想让它实现多人同时编辑，有哪些可以想到的方案呢？
- 覆盖模式
即每个人保存时都强制以自己的版本为主，即保存最后一次修改，这样会导致的问题是无法实现真正意义上的共享协作。
- 锁模式
也就是对文件”上锁“。当某个用户正在编辑文档时，对此文档进行加锁处理，避免多人同时编辑，从而避免文档的内容冲突。 缺点就是用户体验不友好，并且需要等待时间。
- diff 模式
我们可以采用类似 git 的版本管理模式，多人编辑时利用 webrtc / socket 与服务端通信，保存时通过服务端进行差异对比、合并，自动进行冲突处理，再通过服务推送如SSE(服务端实时主动向浏览器推送消息的技术)的方式推送给其他人。
弊端是会出现类似 git 修改同一行，纯靠服务端无法处理，需要手动处理冲突。
这里给大家推荐一个有意思的库 NodeGit。
github地址： https://github.com/nodegit/nodegit
以下是 NodeGit 的一些主要特点：
- 全功能：几乎支持 Git 的所有命令，如克隆、提交、拉取、合并等。
- 高性能：直接调用 C 库，提供接近原生速度的性能。
- 易于集成：作为一个 Node.js 模块，可轻松融入任何 Node.js 项目，无需额外的构建步骤或依赖。
- 跨平台：支持 Windows、macOS 和 Linux，让开发者可以在各种操作系统上工作。
- 文档齐全：提供详细的 API 文档和示例代码，便于理解和使用。
- 社区活跃：开源社区活跃，问题和 PR 能得到及时响应，不断更新改进。
NodeGit 可以用于多个领域，例如自动化部署、协作工具、代码分析、教育工具和 CI/CD 系统等。通过使用 NodeGit，我们能以编程方式访问和操作 Git 存储库，实现更灵活和自动化的版本控制流程。
当然以上这几种方式很难应对复杂场景的多人协作。
OT和CRDT算法
OT 算法是一种用于实时协同编辑的算法，它通过操作 & 转换来实现数据的一致性。在 OT 算法中，每个用户对数据的操作（如修改、删除等）都被记录下来，并在其他用户的客户端进行相应的转换，从而实现多个用户对同一份数据的协同编辑。
OT 算法的优点在于它可以实时地反映用户的操作，并且可以很好地处理并发冲突。但是 OT 算法需要在中心化的服务器上进行协同调度，因此对于大规模的分布式系统来说不太适用。
操作 Operational
基于 OT 的协同编辑核心是：将文档的每一次修改看作是一个操作，即操作原子化处理，如在第 N 个位置插入一个字符时，客户端会将操作发送到服务端去处理。
以quill富文本编辑器举例， 它通过 retain、insert、delete 三个操作完成整篇文档的描述与操作，如下:
[
// Unbold and italicize "Gandalf"
{ retain: 7, attributes: { bold: null, italic: true } },
// Keep " the " as is
{ retain: 5 },
// Insert "White" formatted with color #fff
{ insert: 'White', attributes: { color: '#fff' } },
// Delete "Grey"
{ delete: 4 }
]相关地址：https://quilljs.com/docs/delta
Transformation 转换
用户将原子化的操作发送到服务端时（必须有中央服务器进行调度）， 服务端对多个客户端的操作进行转换，对客户端操作中的并发冲突进行修正，确保当前操作同步到其他设备时得到一致的结果，因为对冲突的处理都是在服务端完成，所以客户端得到的结果一定是一致的，也就是说 OT 算法的结果保证强一致性。
转换完成后，通过网络发送到对应用户，用户合并操作，从而得到一致结果。
这意味着 OT 算法对网络要求更高，如果某个用户出现网络异常，导致一些操作缺失或延迟，那么服务端的转换就会出现问题。
OT算法可视化模型：https://operational-transformation.github.io/index.html
CRDT
CRDT 算法全称 Conflict-free Replicated Data Type，即无冲突复制数据类型，是一种基于数据结构的无冲突复制数据类型算法，它通过数据结构的合并来实现数据的一致性。
在 CRDT 算法中，每个用户对数据的修改都会被记录下来，并在其他用户的客户端进行合并，以实现数据的一致性。CRDT 算法的优点在于它可以适用于大规模的分布式系统，并且不需要中心化的服务器进行协同调度。
但是，CRDT 算法在处理复杂操作时可能会存在合并冲突的问题，需要设计复杂的合并函数来解决。
Yjs 是专门为在 web 上构建协同应用程序而设计的CRDT。
CRDT 包含以下两种：
- CmRDT：基于操作的 CRDT，OP-based-CRDT
- CvRDT：基于状态的 CRDT，State-based CRDT
基于状态的 CRDT 更容易设计和实现，每个 CRDT 的整个状态最终都必须传输给其他每个副本，每个副本之间通过同步全量状态达到最终一致状态，这可能开销很大；
而基于操作的 CRDT 只传输更新操作，各副本之间通过同步操作来达到最终一致状态，通常很小。
穿插一个小概念：
向量时钟（Vector Clock），它是一种在分布式系统中用于记录事件顺序的时间戳机制。它的主要目的是在分布式环境中实现事件的并发控制和一致性。
向量时钟的基本思想是为系统中的每个节点维护一个向量，其中每个分量对应一个节点，用于记录该节点的事件发生次数。当一个节点发生事件时，它会增加自己分量的值。向量时钟的关键是在不同节点之间传递这些向量，并在合并时确保一致性。
目前协同算法底层都会采用向量时钟的模式来设计操作算法。
插曲（互斥锁（Mutex）原理和代码实现）
先上代码：
const createMutex = () => {
let token = true
return (f, g) => {
if (token) {
token = false
try {
f()
} finally {
token = true
}
} else if (g !== undefined) {
g()
}
}
}它用于创建一个互斥锁（Mutex）。互斥锁是一种用于控制资源访问的机制，确保在任何给定的时间只有一个线程（在这里可以理解为一个函数调用）可以访问被保护的资源或代码块。
下面是对代码中每个部分的解释：
- let token = true：创建一个名为token的变量，并将其初始化为true。token用于表示互斥锁的状态。
- return (f, g) => { ... }：返回一个箭头函数，该函数接受两个参数f和g。
- if (token) { ... }：如果token为true，表示互斥锁可用。
- token = false：将token设置为false，表示当前函数获取了互斥锁。
- try { f() } finally { token = true }：在try块中执行传入的函数f。如果在执行f的过程中发生异常，会跳转到finally块中。在finally块中，将token重新设置为true，表示释放互斥锁。
- else if (g !== undefined) { g() }：如果token为false，表示互斥锁已被其他函数获取。如果同时还传递了第二个参数g，则执行g函数。
通过这种方式，createMutex 函数创建了一个简单的互斥锁机制。只有在互斥锁可用时，才能执行f函数。如果互斥锁已被其他函数获取，将跳过f函数的执行，并在可能的情况下执行g函数。
这种互斥锁的实现通常用于在多线程或异步环境中确保对共享资源的安全访问。
yjs协同框架使用
Yjs 本身是一个数据结构，原理是：当多人协作时，对于文档内容修改，通过中间层将文档数据转换成 CRDT 数据；通过 CRDT 进行数据数据更新这种增量的同步，通过中间层将 CRDT 的数据转换成文档数据，另一个协作方就能看到对方内容的更新。
中间内容的更新是基于 Yjs 数据结构进行的，冲突处理等核心都是 Yjs 承担的，通信基于 websocket 或 webrtc，所以我们只需要简单的使用就可以实现多人协同的应用。
下面是我总结的一个结构：
Yjs 基于数据结构层面处理冲突，比 OT 更加稳健，对复杂网络的适应性更强。网络延时或离线编辑对数据结构来说，处理没有任何差异。
我总结了一下它的几个核心特点：
- 协同列表及光标位置
Yjs 提供的 Awareness（意识）模块，名如其意，让协作者能够意识到其他人的位置在哪，有效避免冲突可能性。
- 离线编辑
基于 CRDT 的内容合并，天然支持离线编辑，浏览器端做本地化存储。
- 版本历史支持
Yjs 自身提供了快照机制，保存历史版本不用保存全量数据，只是基于 Yjs 打一个快照，后续基于快照恢复历史版本。
- 系统编辑人数上限
上限人数很高，可支持很多人同时编辑。
目前主流的 figma 也是采用的 CRDT 开发协同编辑功能。
yjs使用
以上我根据自己的理解整理了一下yjs的核心模块。接下来我以数组结构为例子给大家介绍一下它的用法：
import * as Y from 'yjs'
const ydoc = new Y.Doc()
// 1: 定义一个类型为数组的共享数据结构
const yarray = ydoc.getArray('my doc')
// 2. 向数组中插入数据，在第一个位置插入3条数据
yarray.insert(0, [1, 2, 3])
// 3. 在第二个位置删除一条数据
yarray.delete(1, 1)
// 4. 获取可用的结果
yarray.toArray() // => [1, 3]
// 5. 监听数据变化，执行操作
yarray.observeDeep((event) => {
console.log(event)
})
// 将连续的操作合并到transact 中
ydoc.transact(() => {
yarray.insert(1, ['a', 'b'])
yarray.delete(2, 2) // deletes 'b' and 2
}) // => [{ retain: 1 }, { insert: ['a'] }, { delete: 1 }]transact方法用于执行事务操作。事务是共享文档上的一系列更改，这些更改会在一个事务中进行处理，以保证数据的一致性和正确性。每个事务都会触发Observer调用和update事件，我们可以在这些事件中进行相应的处理。
通过将更改捆绑到单个事务中，可以减少事件调用的次数，并确保数据的一致性。在事务中，我们可以进行多种操作，如插入、删除、修改等。
yjs多人协同案例
