最近在研究多人协同技术，正好给自己实现的思维导图工具也添加上协同功能。
协同与冲突
所谓多人协同，是指多人对同一份系统编辑。多人协同中最经典的问题是协同冲突问题：如果对同一个地方编辑操作就会产生冲突。通常的解决办法有：
- 锁：一个文档只能有一个用户编辑
- 内容一起合并，用户自行解决冲突。和git解决冲突一样。
上述两种解决方案的用户体验都不好，此时就要出动第三种完美的解决方法：协同编辑。
协同编辑
协同编辑的基本思想是，系统不需要保持正确，只需要保证一致，且能够尽量保持双方的意图即可。对于同一个地方，保留多方协作者的所有操作是没有必要的。只要有一个机制，能够混合出一个差不多的结果，且能保持一致性，这样用户都能接受。
背后的这个机制，需要一定的技术支持，这就是我们今天要说到的协同技术。目前有两种主流的协同技术：OT算法与CRDT算法。
OT算法解决协同冲突的核心原理是是使用操作转换算法。假设两边用户的操作分别为操作A和操作B，通过转换transform(A, B) = A’,B’，然后分别告诉对方最终的操作，最终得到数据一致的结果。OT算法不在这里详细论述，有兴趣的朋友可以参考这篇文章
下面主要讲讲CRDT算法。
思维导图的协作冲突
下面是一个思维导图的数据模型：
该模型的代码如下：
{
'root': {
label: '中心主题',
children: ['node1'],
},
'node1': {
label: '节点1',
},
}
现在假设有两个用户对同一个思维导图都在根节点添加新的节点。
两个用户在根节点的子节点node1后添加节点。在执行完本地操作后，左右两个用户分别收到了对方的操作：
- 左边用户收到右边用户的操作：在下标1后添加node3，执行后得到的结果是：[node1, node3, node2]
- 右边用户收到左边用户的操作：在下标1后添加node2，执行后得到的结果是：[node1, node2, node3]
如果不做任何处理，双方操作后的数据并不一致。
CRD算法
CRDT算法主要应用于保持分布式系统的数据一致性，协同编辑也可以理解成分布式系统。CRDT算法的核心是通过数据结构的设计保证并发数据的一致性。
CRDT算法有状态和操作组成：一个状态经过操作后才会变成下一个状态。整份状态和操作的链路会被保存。其中每个操作的包含以下元素：
- 操作的相对位置
- 操作用户
- 操作时间戳
再来看看CRDT算法如何解决刚刚在根节点添加新节点的冲突：
如上图，先看看左边用户，在执行了操作时会产生一份操作数据operation1，包含操作位置、操作用户和操作时间。等左边用户收到右边用户的操作数据operation2后，发现两者都操作了同一个位置，此时CRDT算法会比较前后操作时间戳，操作时间越早就越提前执行。操作时间戳的比较保证了协作的数据保持一致。
另外，数据操作数据的顺序和操作次数并不会影响最终结果，只要操作一直，数据的最终状态都是一致的，也就是说CRDT算法满足交换性和幂等性。
具体解决方案：Yjs
Yjs是目前主流的开源前端CRDT框架，该框架的生态比较完善。下面是Yjs的架构图：
- 数据层：Yjs最核心的层次。提供了名为Shared Types的数据结构，用于处理数据的操作和冲突合并。
- 网络协议层：Yjs封装了一些开箱即用的数据同步协议的npm包，名为provider，包括webrtc、websocket和indexdb本地同步等。
- 应用层：Yjs为一些主流的富文本编辑器提供应用绑定层，实际上就是只需要放入网络协议provider和数据Shared Types即可立即实现协同编辑。
思维导图的协同架构
Yjs操作的主要是数据，因此我将思维导图的架构改为以数据驱动的架构 —— MVC架构。MVC架构主要分为三层：操作层、视图层和数据层：
数据层使用Yjs的Shared Types实现，每次数据有改变时改变思维导图的视图，操作层操作的是数据而不是视图。
感知数据（Awareness）
协同编辑除了同步主数据外，还有同步一些感知其他用户的状态数据，比如：
- 的选中状态
- 输入光标
- 鼠标位置
感知数据和主数据不同，感知数据需要全部展示，因此不会有冲突。而且这些数据是实时数据，在用户不在线时就丢掉，因此不用持久化。
Yjs提供了awareness方法处理这种感知数据，具体使用方式如下：
// awareness由provider提供
const awareness = provider.awareness
// 监听其他user的感知数据变化
awareness.on('change', changes => {
console.log(Array.from(awareness.getStates().values()))
})
// 设置感知数据，如光标和选择状态
awareness.setLocalStateField('user', {
selectId: 'root',
color: '#ffb61e'
})
demo
笔者实现了一个简单版的协同思维导图demo，有兴趣的同学可以体验一下：思维导图协同demo
