前言

近期，基于 Yjs 实践了在线协作的思维导图。本文简单谈谈个人关于 CRDT 和 Yjs 的一些见解。

CRDT 是什么？简单来说，CRDT（Conflict-free Replicated Data Type,无冲突复制数据类型）是一种可以在网络中的多台计算机上复制的数据结构，副本可以独立和并发地更新，而不需要在副本之间进行协调，并且在数学上总是可以解决可能出现的不一致问题。

分布式与一致性

从 CRDT 的定义里可以看出，该数据类型是用于（类）分布式类型系统的。

safety 和 liveness

在分布式系统中，safety和liveness是2个非常重要的属性，维基百科的定义如下：

• safety：bad things don’t happen
• liveness：good things do happen

后续对于一致性的说明，会用到这两个属性。

CAP 定理

在分布式系统领域，最经典的理论之一就是 CAP 定理。CAP 分别代表分布式系统的三个特性：一致性（consistency）、可用性（availability）和分区容错性（partition-tolerance）。

在最初证明 CAP 定理的论文中，C 是线性一致性（linearizable consistency）。线性一致性是比较抽象的概念，对分布式系统而言，单一副本满足线性一致性。但是单一副本不具有容错性，所以分布式系统一般都会对数据进行复制（replication），也就是保存多个副本。这时，在一个分布式多副本的存储系统中，要提供线性一致性的保证，就需要付出额外的成本了。通常，线性一致性也被称为强一致性（strong consistency）。

CAP 定理中，证明了任何系统只能保证 CAP 其中的两者。对于分布式系统而言，分区容错性是必须要保证的。因此，必须在（强）一致性和可用性中二选一（CAP 理论的作者后面纠正：大部分场景是可以满足 CAP 的，只是在部分场景下需要二选一）：

1. 保证强一致性，但是会牺牲可用性。因为维持强一致性，需要在同步副本节点时进行大量的通信和协调工作，增加延迟；
2. 优先用户的本地操作，提升可用性（降低延迟），但可能丢失一致性；

最终一致性与因果一致性

本文讨论的在线协作编辑领域，高可用性是至关重要的。因此，在上一章节末的选择中，只能是选择2（保证可用性）。但是，这会带来一致性丢失的风险。

为了解决这个可能导致一致性丢失的问题，我们引入了最终一致性的概念。简单来说，最终一致性指的是，在未来的某个时间点，所有副本都将达到一致的状态。

强一致性是满足 safety 属性的，也就是说，当分布式系统遵守强一致性时，如果系统出问题，我们能明确知道发生问题的时间。

最终一致性则放弃了 safety 属性，属于 liveness。因为在中间过程会出现可能不一致的场景，这给分布式系统增加了困难，需要随时关注数据不一致的概念。

强一致性是满足 safety 属性的，也就是说，当分布式系统遵守强一致性时，如果系统出问题，我们能明确知道发生问题的时间。

最终一致性则放弃了 safety 属性，属于 liveness。这给分布式系统增加了困难，需要随时关注数据不一致的概念。

那么，有没有可能基于最终一致性增加 safety 属性，提供较强的最终一致性，同时保留高可用性和低延迟？

基于该文章论证，因果一致性（causal consistency）可以满足这个要求。而且在分布式系统下，如果要保证可用性，不存在比因果一致性更强的一致性模型。本文不对此展开具体描述，具体可参见上述文章。

简单的说，因果一致性要求：如果两个事件有因果关系，那么在所有节点上必须观测到这个因果关系。

​

编辑切换为居中

添加图片注释，不超过 140 字（可选）

上图即为不满足因果一致性的示例。在P2节点内，先是读到x为a，再x赋值b；在P3节点，先是读到x为b，再读到x为a。可以发现P2和P3节点对于x的因果顺序是矛盾的。下图，为符合因果一致性的图例。

​

编辑切换为居中

添加图片注释，不超过 140 字（可选）

从因果一致性的定义，可以看出因果关系是一种偏序关系（序论的概念），允许站在不同节点的视角去观察各自所关心的部分操作，从而得到不同的操作排序序列且同时不违反因果律。

并发冲突与强最终一致性

在前一章节中，我们了解到因果一致性模型表示了一种偏序关系。在该一致性模型下，存在一些无因果关系的操作，即并发操作。在某些分布式系统场景中，这种偏序关系已经满足需求，因此不需要特别处理并发操作之间可能产生的冲突。

然而，在其他场景下，我们可能需要确保并发冲突操作的一致性，从而实现所谓的强最终一致性。换句话说，在实现强最终一致性时，需要在因果一致性的基础上加强对并发冲突的处理。为了解决这个问题，CRDT 应运而生，为分布式系统提供了一种应对并发冲突的有效解决方案。

CRDT 原理

我们先回顾下刚提到的因果一致性和并发冲突等概念，再来更深入地了解 CRDT 原理。在分布式系统中，我们常常需要在可用性和强一致性之间权衡。CRDT 侧重于提供可用性和分区容错性，但不提供强一致性，而是提供所谓的强最终一致性。与此同时，大多数 CRDT 致力于支持因果一致性来实现强最终一致性。

常见的 CRDT 分为两类：CvRDT（Convergent Replicated Data Type，基于值的 CRDT）和 CmRDT（Commutative Replicated Data Type，基于操作的 CRDT）。有研究证明，CvRDT 和 CmRDT 可以互相转换。本文将以应用于协同编辑的 CmRDT 为例进行更详细的讨论。

CmRDT 的基本概念包括以下两点：

1. 操作以因果顺序到达各个副本，并使用可靠的广播机制。若操作不按因果顺序到达，则它们必须是可交换的；
2. 所有冲突操作必须是可交换的；

条件 1 旨在满足因果一致性。但在实际场景中，确保操作按因果顺序到达是困难的，因此各个副本的操作需满足交换律和结合律。此外，考虑到操作可能会被重复发送，操作还需要满足幂等性。

条件 2 用于实现强最终一致性。CRDT 要求各个副本在以不同顺序接收其他副本操作时，无需进行任何额外的同步，就能解决并发操作的冲突，收敛至一致状态。这也是强最终一致性与最终一致性之间的主要区别。

综上所述，CmRDT 通过设计合理的数据结构，使操作满足交换律、结合律和幂等性。同时，CmRDT 能自动解决冲突，从而提供强最终一致性。

CRDT 的挑战（CmRDT）

提到协同编辑，不得不提到 OT。早期的在线协同编辑主要依赖于 OT（Operational Transformation）。OT 的工作流程包括以下步骤：

1. 将本地副本操作发送至服务器；
2. 服务器接收操作并进行转换，然后将转换后的操作发送至其他副本，各个副本合并操作，实现强最终一致性；

OT 的优势在于易于理解和实现。然而，它也有一些局限性：

• 转换函数复杂性。当操作类型数量为n时，所需的转换函数数量为n²，构建正确且高效的函数非常具有挑战性；
• 网络延迟。在高延迟的网络环境下，由于中心化的转换处理，OT 的性能可能受限。

如前所述，CRDT 通过设计合理的数据结构实现强最终一致性。与 OT 相比，CRDT 有以下优势：

• 通过特殊的数据结构和操作维持因果顺序和解决并发操作冲突，实现最终强一致性，实现复杂度较 OT 低；
• 支持去中心化的同步策略，能自然地实现本地离线编辑；
• 具备更强的容错性，对网络延迟和节点故障有更高的容忍度；

尽管 CRDT 如此优越，为何它没有迅速取代 OT 呢？主要原因是 CRDT 存在一些应用难点。在线协同编辑领域的 CRDT 研究主要面临以下挑战：

1. CRDT 数据结构设计。需要满足以下要求：a. 支持因果一致性，同时操作要满足交换律、结合律和幂等性；b. 保证在线协同编辑（文本）顺序一致性；
2. 要保证低延迟和低计算复杂度：a. 要在数据结构的更新、查询和冲突解决之间找到平衡点，实现整体较低的计算复杂度；b. 要减少数据结构大小，设计高效的副本间的同步算法。从而实现优化副本之间的状态同步，保证通信传输效率，实现低延迟；

Yjs 的使用

针对前述提到的 CRDT 的痛点，近年来涌现出众多 CRDT 库。本文将以 Yjs 为例，进行深入探讨。

Yjs 暴露给用户的数据结构，仅提供一种：shared types（共享类型），而隐藏了其所有 CRDT 的细节。此外，Yjs 提供了 Y.Doc（后续简称为Doc）的API 作为文档模型，充当一个 "容器" 角色，储存所有 shared types 数据（shared types 需挂载在 Doc 实例上）。

Yjs 支持的核心功能包括：a.实时的数据同步；b.冲突解决。我们通过具体代码，来看这两个功能的支持。

import * as Y from 'yjs';

function onSync(doc1, doc2) {
  console.log('\n同步前的两个文档');
  console.log('doc1:', doc1.getArray('shared_array').toArray());
  console.log('doc2:', doc2.getArray('shared_array').toArray());

  // 将 doc1 的状态转换为更新，并应用于 doc2
  const update1 = Y.encodeStateAsUpdate(doc1);
  Y.applyUpdate(doc2, update1);

  // 将 doc2 的状态转换为更新，并应用于 doc1
  const update2 = Y.encodeStateAsUpdate(doc2);
  Y.applyUpdate(doc1, update2);

  // 检查同步后两个文档的状态
  console.log('\n同步后的两个文档');
  console.log('doc1:', doc1.getArray('shared_array').toArray());
  console.log('doc2:', doc2.getArray('shared_array').toArray());
}

// 创建两个 Yjs 文档 (doc1 和 doc2)
const doc1 = new Y.Doc();
const sharedArray1 = doc1.getArray('shared_array');
sharedArray1.insert(0, ['A']);

const doc2 = new Y.Doc();
const sharedArray2 = doc2.getArray('shared_array');
sharedArray2.insert(0, ['B']);

// 将两个文档同步前的状态打印
onSync(doc1, doc2);

// 添加新元素到 doc1
sharedArray1.insert(1, ['C']);

// 为了模拟并发更新，同时将新元素添加到 doc2
sharedArray2.insert(1, ['D']);

// 将两个文档的并发更改同步并打印状态
onSync(doc1, doc2);

尝试运行代码，可以得出如下结果

同步前的两个文档
doc1: [ 'A' ]
doc2: [ 'B' ]

同步后的两个文档
doc1: [ 'A', 'B' ]
doc2: [ 'A', 'B' ]

同步前的两个文档
doc1: [ 'A', 'C', 'B' ]
doc2: [ 'A', 'D', 'B' ]

同步后的两个文档
doc1: [ 'A', 'C', 'D', 'B' ]
doc2: [ 'A', 'C', 'D', 'B' ]

数据同步

在代码示例中，首先创建了两个 Doc 实例 (doc1 和 doc2)，两者都挂载了一个 Y.Array 实例。然后分别向 doc1 和 doc2 的 Y.Array 实例中插入元素，再使用 onSync 函数将它们同步，后续的操作是同样的分别插入元素和同步。这两组操作即模拟了 Yjs 中的并发更新。

简单说明下涉及数据同步的两个API。encodeStateAsUpdate 会将其参数（一个 Yjs 文档实例）的状态转换为一个更新对象。调用 applyUpdate 函数会将这个 update 将被应用于另一个 Yjs 的 Doc 实例。

冲突解决

冲突解决无需额外处理，本身都在 shared types 背后自动解决了。上述代码示例里，是在 applyUpdate 里解决了冲突。 在线协作 CRDT 领域里，冲突的解决的核心是：保留意图和强最终一致性。我们以后面一组操作为例，来说明 Yjs 是否符合要求。

• 保留意图：两者冲突操作对应的代码是：sharedArray1.insert(1, ['C'])，sharedArray2.insert(1, ['D'])。doc1 和 doc2 都意图在 A 和 B 之间插入新的字符。这里的意图就是指：最后 C 必须在 A 和 B 之间，D 必须在 A 和 B之间。可以看到最后的结果是 doc1 和 doc2 都为[ 'A', 'C', 'D', 'B' ]，C 在 A 和 B 之间，D 在 A 和 B 之间，符合意图的保留；
• 强最终一致性：doc1 和 doc2 都输出了[ 'A', 'C', 'D', 'B' ]，符合强最终一致性要求；

Yjs 的数据结构与原理

Item

Yjs 底层基础的数据结构是 Item（src/structs/Item.js ）。

上一章节，提到 shared types 是 Yjs 对外暴露的基础类型。实际上，Yjs 底层的数据结构 Item 和 shared types 是一一映射的关系。Item 的 content 字段指向 share types 实例，而 share types 实例对象的 _item 字段指向Item。因此，当调用 share types 的 insert 时，实际上是插入 Item。

Item的核心数据结构涵盖下面几部分：

• ID。Item 的唯一标识符（ID），由客户端唯一 ID（clientId）和 Lamport 时间戳（clock）组成，确保每个客户端生成的 ID 是唯一的；
• content。content 指 Item 所存储的数据（比如对应插入的字符串）。正如前面提到，content这里是直接指向了 share types 实例，存储了当前 Item 对应的基础类型或者复合类型；
• position。postion 包括：left，right（Yjs 的 CRDT 数据结构基于双向链表，依赖于此）；origin，originRight，这两项属性是为了解决冲突；parent，parentSub，这两项是为了支持 Yjs 的灵活的嵌套数据结构；

副本间的数据同步

上一章节可以看到，不同 Doc 实例之间是通过 update 来进行数据的同步。update 主要是由 structs（所有 Item）和 ds（基于 state-base crdt 的 DeleteSet）组成。我们可以打印 update 来看下：

const testDoc= new Y.Doc();
const testText=testDoc.getText();
testText.insert(0,'test1');
testText.delete(4, 1);
console.log('update: ',Y.decodeUpdate(Y.encodeStateAsUpdate(testDoc)));

可以看到打印结果：

​

编辑切换为居中

添加图片注释，不超过 140 字（可选）

1. 本地 Doc 副本发生的 insert 和 delete，通过转发给 transaction（src/utils/Transaction.js）统一处理；
2. transcaction 收集完 update 便会将其广播给各个监听的 Doc 副本；
3. 其他 Doc 副本收到 update 之后，会进行计算和处理，存入本地的 struct store（src/utils/StructStore.js）中。struct store 在基于 state vector 的数据同步里，发挥了重要作用，被同步方可以使用二分法可以快速查到缺少的 structs 给同步方；

​

编辑切换为居中

添加图片注释，不超过 140 字（可选）

至此，副本间完成了数据同步。

保证强最终一致性

此处回顾一下前面提到的：当前大多数 CRDT 都是通过因果一致性，同时解决并发操作的冲突，来实现强最终一致性。除此之外，在线协同还需支持文本顺序一致性来保证强最终一致性。

a.首先，来看 Yjs 的 CRDT 如何保证因果一致性。

在其他 CRDT 中，很多都是通过 Lamport 时间戳确保操作的因果一致性。但 Yjs 未使用该方法。

Yjs 中，Item 按文档顺序存储在双向链表树中。每个 Item 有全局唯一 ID，通过 left 和 right 连接到左右的 Item组成双向链表树。在插入新字符时，Yjs 会获取左右字符的相对位置（ left 和 right ），生成唯一的相对位置。唯一的相对位置保证了多个操作（update）能够以相同的因果顺序在不同副本中被 apply，即使并发，文档状态也能收敛至相同的状态，从而保证操作的因果一致性。

在处理删除操作方面，Yjs 使用了额外的结构 deleteSet 来在不同副本间同步，保留了所有的 Item，从而能保证所有Item的相对位置的不丢失，以实现因果一致性。

Item 和双向链表树的设计，也使得操作天然支持了交换律，结合律，同时结合唯一 ID 实现了操作的幂等性。 同时，Yjs 的双向链表的数据结构和节点的相对位置的唯一性也保证了文本顺序的一致性。

b.要实现强最终一致性，还要保证并发操作的冲突解决的一致性。同时在线协同编辑领域，冲突解决需要保留意图。

有关并发操作如何解决冲突，Yjs 的实现是基于 YATA 算法的。由于篇幅有限，本文不对 YATA 算法展开论述。简单来说，YATA 算法有如下几个规则：

​

编辑切换为居中

添加图片注释，不超过 140 字（可选）

1. 禁止发生冲突的的插入的 origin 连线 之间发生交叉。如上图是允许的两种连线情况；
2. 规则 2 是指定了解决冲突函数的传递性（具体参见论文）；
3. 当两个冲突的插入具有相同的 origin 时，创建者 id 较小的插入位于左侧。创建者 id 对应的就是 Yjs 的客户端唯一 ID（clientId）；

YATA 算法证明了基于这三个规则， 解决冲突的函数是全序函数，具有反对称性、可传递性和整体性，同时也符合意图保留的要求。

Yjs 的优化

针对前面章节提到的 CRDT 的挑战，YATA 算法及其实现 Yjs 对此做了很多优化。

优化 Item 操作

根据前几章节的描述，可以认为 Yjs 有如下行为：当插入一个字符时，会生成一个新的 Item。但如果每一个字符就生成一个 Item 的话，随着文档字符数变多，可能会显现一些问题：

• 导致 Item 对应的内存占用变大，不同副本间的同步产生更高的网络开销和延迟；
• 某些场景下 Item 链表的操作的计算复杂度变高，耗费时间变慢，文档更新速度下降；
• 大量单独的 Item 可能导致较多的的操作冲突，冲突解决的耗费时间多；

因此，Yjs 对此做了对应的优化：

• Yjs 会根据用户的操作和兼容性，进行 Item 的合并。比如：当用户按顺序键入字符“ABC”，实际上B Item，C Item 会和A Item 合并为一个 Item。该优化降低了 Yjs 的存储开销，降低本地副本的计算复杂度，同时也降低了副本间同步的延迟；
• 优化 Item 部分字符删除的操作。比如：当用户在 content 为"ABC"的 Item 中的字符"A"时，会将 "ABC" Item 拆分成：标记位为 deleted 的 A Item，BC Item。该优化和前一优化的作用相似，同时这个优化也对undo/redo 有作用：使本地副本的操作历史更贴近用户实际的编辑情况，方便理解文档的修改历史；

类似跳表的优化

为了优化本地插入的速度，Yjs 还设计了额外的缓存机制。

如果在文档中任意位置随机插入新字符，这时新字符对应的 Item 理论上需要 O(N) 的时间复杂度才能插入链表中。但实际上，大多数插入操作都会跟随在用户最后编辑的光标位置。因此 Yjs 默认会缓存 10 个最近的插入位置供快速匹配，在内部实现中这被称为 skip list（作者认为这一缓存机制是受到了跳表的启发）或 fast search marker。

state vector

在副本间进行同步的时候，有时候需要交换差异。比如两个副本间使用 websocket 进行广播的时候，初始连接的时候，需要交换副本间的信息。

为了低通信成本地交换差异，Yjs设计了如下的数据结构： Map<clienId, clock>，称之为 state vector（状态向量）。

​

编辑

添加图片注释，不超过 140 字（可选）

副本间通过交换 state vector，可以得知新连接的副本缺少的 update 并只将缺少的 update 发送给新连接的副本。

state vector 本身的数据结构体积很小，同时 state vector 使得副本间的同步无需传递整个副本，降低了同步时的数据传输消耗。

二进制传输

Yjs 了大量使用了二进制存储和传输：

1. 使用类似 protcol buffer 的协议，将 json 格式的数据转换成如 uint8array 的二进制格式。比如：通过优化，在 json 中形如 {testA:'6',testB:'125'} 的数据结构，通过二进制转换，请求参数就不需要再包含字段 (testA，testB) 名称，只需发送类似 [6,125] 的数据，降低网络请求的传输成本。
2. 优化数字的存储空间。比如"125"作为字符串在浏览器请求的中是9个字节（utf8编码格式），而作为二进制数，比如 uint8array 中传输只需要占用一个字节的空间。

小结

本文主要介绍了：

• CRDT 的背景和原理
• CRDT 设计的挑战
• Yjs 核心功能的使用和原理，以及 Yjs 针对性的优化。

本文相对侧重理论，后续有机会再分享下在实际应用过程中的一些经验。