什么是 CRDT？

CRDT（Conflict-Free Replicated Data Type，无冲突复制数据类型）是一种特殊的的数据结构，它能让多个可能没有实时网络连接的节点共享和修改的同一份数据。

每台客户端都有一份数据的复制，并且可以随时对其进行修改。当节点之间同步时，CRDT 可以自动合并这些修改并协调冲突，使每个节点上的数据保持一致。

CRDT 可以提供强最终一致性（strong eventual consistency），换句话说即使不同节点收到的更新顺序不同，只要节点都收到了相同的更新，它们的状态就能保持一致。

值得注意的是，CRDT 的协调冲突只能保证各个节点结果一致，不一定能够满足用户的需求。比如利用 CRDT 实现的编辑器的不同节点在 Y！中同时插入AT和A，最终的结果可能是YATA！或YAAT!的其中一种，但不会出现两个节点不一样的场景。

Yjs

Yjs 是一个经典的 CRDT 的基础库，可以用于文本编辑器中自动处理多人同时编辑一处文本时遇到的冲突，保证各个客户端最终状态一致。并且它是一种基于操作（operation-based）的 CRDT，每次更新数据之后仅需传输包含当前操作的更新，无需传输整个文档。

Yjs 包含了几种基本的 CRDT 数据结构，如 Y.Array、Y.map、Y.Text等。对富文本编辑器来说最有用的是 Y.Text，它可以描述一段包含格式的文本，如 “Gandalf the Grey”可能会被表示成如下的 delta fomat 形式。

1
2
3
4
5
6
7
{
  "ops": [
    { "insert": "Gandalf", "attributes": { "bold": true } },
    { "insert": " the " },
    { "insert": "Grey", "attributes": { "background": "grey" } }
  ]
}

Y.Text是以二进制形式保存数据的，以上展示的 delta 格式是调用toDelta()函数经过转换后得到的人类可读格式。

有关 Yjs 的基础用法，可以查看以下示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
import * as Y from "yjs";

const ydoc = new Y.Doc(); // 实例化一个 ydoc
const ytext = ydoc.getText("text"); // 这里实际上是在 ydoc 上定义了一个 ytext

ytext.insert(0, "abc"); // 插入字符串
ytext.format(1, 2, { bold: true }); // 加粗 'bc'
ytext.toString(); // => 'abc'
ytext.toDelta(); // => [{ insert: 'a' }, { insert: 'bc', attributes: { bold: true }}]

// 其他客户端也可以创建一个 YDoc
const ydocRemote = new Y.Doc();
// 将上面的 ydoc 编码成二进制更新
const update = Y.encodeStateAsUpdate(ydoc);
// 更新到这个客户端端 ydoc 上
Y.applyUpdate(ydocRemote, update);

// 由于应用了全量更新，此时两份 ydoc 保持一致
const ytextRemote = ydoc.getText("text");
// 如果你在更新前修改了 ytextRemote，yjs 会在更新时自动协调冲突
ytextRemote.toString(); // => 'abc'

// 更轻量地同步不同客户端
ydoc.on("update", (update) => Y.applyUpdate(ydocRemote, update));
ydocRemote.on("update", (update) => Y.applyUpdate(ydoc, update));

Yjs 是如何实现 CRDT的？（选修）

Yjs其实是实现了 2016 年一篇的论文中描述的 YATA 算法。这个算法有以下三个规则

  • Rule 1. We forbid crossing of origin connections between conflicting insertions.
    • 这里的 origin connections 指插入数据时，新增数据与它左边数据之间的连线。
    • 只有两个数据被并发插入同一个位置它们才会有相同的 origin
      rule-explain
  • Rule 2. we define a function <c that specifies a position for onew in the set of conflicting insertions (c1..cn). Specifies transitivity on <c. Let o1 <c o2. Then following rule ensures that there is no o that is greater than o2 but smaller than o1 with respect to <c.
    • 这条规则宣言了所有编辑操作的比较存在传递性，当o1 < o2时，不会存在另外一个操作比o2大同时比o1小。
    • 这个规则的主要作用是维护插入操作之间的一致性和相对顺序。它确保了在处理冲突插入时，操作之间的顺序关系是明确和可预测的。
  • Rule 3. When two conflicting insertions have the same origin, the insertion with the smaller creator id is to the left.

这三条简单的规则构成了 YATA 算法处理并发编辑冲突的核心，它保证了所有编辑操作是严格全序（strict total order）的，即所有操作可以在各个客户端区分出相同的先后顺序。这保证了文档在多用户协作编辑的环境中能够达到强最终一致性。

The core idea is enforcing a total order on the shared data types.

至于它的证明就留作课后习题供读者自行完成，本文也附上当年的 YATA 论文供学有余力的读者进一步研究。

论文还讨论了 YATA 的垃圾收集，这对于保持性能和避免不必要的数据存储至关重要。

另外特别感谢 GPT-4 协助作者阅读论文！

Yjs 如何实现 YATA 算法

这部分推荐直接阅读雪碧的文章探秘前端 CRDT 实时协作库 Yjs 工程实现。

Yjs 首先为每个 item 分配一个唯一 ID 属性 ID(client, clock)。其中 client 是每个客户端随机生成的uint32整数，用于比较不同客户端的先后（Rule3）。clock 是一种常用于 Lamport timestamp 的逻辑时间戳，它除了会在发生操作时增加计数之外，还会在接收到远程更新时把计数同步为本地或远程计数中较大的那一个。

由于每个 item 都有一个可比较的数值，这就实现了 Rule2 提到的传递性。最后只要在解决冲突时做一个简单的判断就能保证 Rule1 ，实现最终一致。

代码实现（选修）

YATA 插入算法代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// Insert 'i' in a list of
// conflicting operations 'ops'.
function insert(i, ops) {
  i.position = ops[0].position;
  for (const o of ops) {
    // Rule 2:
    // Search for the last operation
    // that is to the left of i.
    if (
      (o < i.originLeft || i.originLeft <= o.originLeft) &&
      (o.originLeft != i.originLeft || o.creator < i.creator)
    ) {
      // rule 1 and 3:
      // If this formula is fulfilled,
      // i is a successor of o.
      i.position = o.position + 1;
    } else if (i.originLeft > o.originLeft)
      // Breaking condition,
      // Rule 1 is no longer satisfied
      // since otherwise origin connections
      break;
  }
}

Yjs 在实现 YATA 时还做了一些论文中没提到的小改进，比如引入了originRight用于提升解决冲突的性能。

具体实现

yjs/src/structs/Item.js at main · yjs/yjs

y-octo/y-octo/src/doc/store.rs · y-crdt/y-octo

进阶阅读

在近期热门的 Loro 项目文档也有一章详细解释了 CRDT 这个概念，感兴趣的读者可以自行前往阅读 What are CRDTs – Loro。

Loro 的概念解释中还指出了 CRDTs 存在的两个缺陷，有打算开发 CRDTs 应用的读者应尤其注意。

Difficulty in maintaining user-defined invariants.

Automatic merge results of parallel edits may violate the schema.

在此也附上另外一篇反面观点的文章When You Can’t Rely on CRDTs供读者思考。

Figma 也根据自己独特的业务需求在这个领域交出了自己独有的一份答卷 How Figma’s multiplayer technology works。Figma 不需要做到富文本级别的协作，因此采用了 Last-writer-wins register 模式，仅有多人同时修改同一对象上的同一属性才需要处理冲突，很方便地解决了大部分的协作场景。

参考资料