---
title: CRDT 漫谈
date: 2023-11-23
---

以前写过一篇 [«CRDT: 分数排序»](./crdt-fractional-indexing)。我认为，CRDT 可能是未来实现大部分软件的最佳选择。有了它，你就免费获得了离线编辑、协作、历史记录、撤销重做等等功能，传统的软件开发中以上任何一条都是非常难设计和实现的。

### 定义

Conflict-free Replicated Data Type，无冲突数据结构。什么叫冲突？这通常需要根据具体场景来理解和定义，对于大家最熟悉的文本编辑场景，冲突就是两个或以上用户的编辑最终变成了重叠、错位、不一致的情况。CRDT 的目标就是针对各种不同的场景，**分别**设计出特定的数据结构，使得它们可以符合大多数人的预期、保持一致。由于 CRDT 不是一种，有的时候大家也会用 CRDTs 来代指所有的 CRDT。下文中还会列举一些常见的实现。

#### 问题框架

CRDT 要解决的问题必须都能用这个框架来描述。

> 假设有一个无敌信道，可以让任何在里面的消息都广播到所有客户端，并且不会发生消息的丢失 (不用保证顺序)，那么如何基于它设计一个数据结构，使其可以满足某个协作场景的需求？

简单来说要求有这样一个基建:

- 消息全部到达，包括所有历史消息，不用保证顺序
- 消息不会重复

…这在现实中当然是不存在的，于是具体应用就需要分别实现某些基建，这通常包括：

- 一个存储服务，用于在所有设备都下线时保存最新的状态
- 一个消息队列，用于保证消息的到达 (但不用保证永久存储)
  - 基于 P2P 的实现有可能无法保证，此时需要客户端实现重试策略
- 其他对业务有用的服务
  - 例如，一个同步观看视频的应用将需要同步设备的时间以对齐视频播放的位置

因此，如果有产品将以上基建封装成一个统一的服务，将会非常有利于 CRDT 应用的落地。

#### 本地优先软件

CRDT 非常适合用来制作本地优先软件 (Local-first software)。现如今人们通常接触的都是云应用 (或者你可以称其为 <abbr title="Software as a service">SaaS</abbr>)，你需要登录才能访问和使用你上传的数据。而一旦服务器宕机或者由于一些不可抗力，你珍贵的数据就会暂时消失一段时间。有了 CRDT，你的本地编辑历史会被持久化存储，就不怕内容丢失了。

当然，前面提到的问题可以通过本地多保存几次备份等土办法来解决。从另一个角度来说，本地优先的意义在于<q>让本地的修改优先发生</q>，也就是说用户应当立即看到操作的效果，而不是等服务器返回响应。否则运气不好的话用户每操作一会就得等应用转圈圈，这种体验是非常糟糕的。CRDT 上的修改都是立即生效的，就算网络断开也不会丢失这次的操作。

#### 什么时候不用 CRDT？

CRDT 的最低目标只是保证结果一致，而不保证总是符合预期。例如，<abbr title="Multiplayer Online Battle Arena">MOBA</abbr> 类游戏中对于伤害的结算需要有一个中心服务器进行裁决和下发以保证公平性。再比如，银行类系统会要求每次金融操作的原子性、一致性等硬标准，这些地方该转圈圈还是得转。

多人游戏的同步是又一个比较复杂的话题，以后有机会可以再展开。

### 分类

有两大类 CRDT 的设计方向，一类是基于操作 (Operation) 的，也就是广播消息内容直接是<q>操作</q>，比如 (+1) (insert 0 "hello") 之类的，现在主要流行的 CRDT 库大都是这类，也叫 <abbr title="Commutative replicated data types">CmRDTs</abbr>。另一类是基于状态 (State) 的，广播消息是本地的状态 (可以是全量或部分)，而接收端需要实现特殊的合并算法来算到最新状态，也叫 <abbr title="Convergent replicated data types">CvRDTs</abbr>。

### 常见场景和实现

下面有一些是纯学术构想的虚拟场景，有一些则是真实且有线上应用的。

#### 投票系统

假如你在做一个直播类软件，软件上有一个点赞按钮，所有观众都可以点击此按钮为主播的人气值 +1，你该如何实现：有一万个人同时点击这个按钮，如何让主播最终看到人气值 = 一万，且服务器不炸。

**解**: 可以设计这样一种数据结构，它的消息体里只有一个 `1`，主播拿到消息后立刻增加人气值。回想上文中的信道，显然，既然消息都可以到达，那么最终收到的 `1` 的数量一定是完整的一万。

```js
点赞 = () => 观众.发送(1)

收到 = (点赞) => {
  this.人气值 += 点赞
}
```

#### 分组投票系统

还是上面的场景，但是你想看到具体每个人点了多少次赞。

**解**: 可以让消息体里带上观众的 ID，主播那里分别统计每个人的点赞次数。

```js
点赞 = () => 观众.发送(this.id, 1)

收到 = ([谁, 点赞]) => {
  this.人气值[谁] += 点赞
}
```

#### 礼物系统 (Set)

还是上面的场景，但是这次不要求统计赞数，而是要求知道主播收到了哪些种类的礼物。

**解**: 可以让消息体里带上礼物的 ID，主播那里把收到的礼物 ID 放到一个集合里。

```js
发送礼物 = () => 观众.发送(礼物.id)

收到 = ([谁, 礼物]) => {
  this.收到的[礼物] = true
}
```

#### 知乎

这次不光可以点赞，还可以点踩。只需要知道最后 `赞 - 踩` 是多少即可。

**解**: 可以设计两种消息，一个 `+1`，一个 `-1`，主播累加所有消息。

```js
点赞 = () => 观众.发送(+1)
点踩 = () => 观众.发送(-1)

收到 = (点赞或点踩) => {
  this.人气值 += 点赞或点踩
}
```

#### 通用 (Map)

对于一些元信息类的数据，只需要保留最后一次修改的结果。例如文章标题、卡片颜色等等。

**注意**: 上文中的信道是不保序的，因此你不能依赖消息到达的顺序来实现。

**解**: 可以使用 [Lamport](https://en.wikipedia.org/wiki/Lamport_timestamp) 时钟来对消息进行排序，消息内容就是修改 `Map` 内容。

> Lamport 时钟是指这样一个数：初始化为 0，每次发送消息一起发出去且 +1，每次收到消息时设为最新消息的时钟 +1。

```js
写入 = (key, value) => {
  this.发送(this.lamport++, key, value)
}
收到 = (lamport, key, value) => {
  if (this.lamport < lamport) {
    this.lamport = lamport + 1
    this.数据[key] = value
  }
}
```

#### 列表 (List)

对于记事本等小型列表场景，直接替换整个列表似乎有点浪费带宽。

[Evan](https://madebyevan.com/algos/crdt-fractional-indexing/) 提出给元素增加一个分数信息表示列表位置的方法，详见 [&laquo;CRDT: 分数排序&raquo;](./crdt-fractional-indexing)。

#### 文本 (一种列表)

对于文本编辑器之类大量有序数据的场景，一个重要的需求是保证不重叠，例如两个人分别在同一个位置输入了 `ab` `cd`，合并结果可以是 `abcd` 或 `cdab`，但不能是 `acbd`。

[Yjs](https://github.com/yjs) 实现了一个名叫 [YATA](https://zhuanlan.zhihu.com/p/452980520) 的算法，基本思想是保证 `a-b` 和 `c-d` 这两根线不能形成交叉。

[Loro](https://www.loro.dev/blog/crdt-richtext) 实现了 Peritext 和 Fugue 两个新算法，能很好地支持富文本 (文本上有各种标记，如加粗变色等) 场景以及解决文本重叠问题。

#### 树 (无环图)

如果只有 `Map`，你可以对每个节点存储其父节点的 ID 来实现图结构，但是这无法解决循环引用的问题。

[Loro](https://www.loro.dev/blog/loro-now-open-source#movable-tree) 实现了一个拥有移动节点指令 (也就是<q>设置某个节点的父节点</q>) 的树形数据结构，其基本思想是插入适当的<q>撤销</q>操作来恢复树结构不能有环的约定。

[Evan](https://madebyevan.com/algos/crdt-mutable-tree-hierarchy/) 实现了一个类似的算法。