CRDT 冲突算法
CRDT 冲突算法
CRDT 全称为 Conflict-free Replicated Data Type，即无冲突复制数据类型。
OT 的缺陷
由于是 OT 是强一致性的设计，所有操作都需要在服务器端进行转换，从而避免冲突，因此 OT 算法对网络的要求比较高，如果某个用户出现网络异常，导致一些操作缺失或延迟，那么服务端的转换就会出现问题。因此，OT 算法不太适合用于分布式的系统，但分布式系统又是目前解决超级复杂问题的唯二选择。
CAP 理论
CAP 理论由 Eric Brewer 于 2000 年提出，是三个英文单词的首字母缩写：
- C：Consistency 表示一致性，所有节点访问的数据必须是最新的、完全一致的。例如：如果在分布式数据库 A 节点写入了一条记录，然后立刻去 B 节点读取，能立刻能读到这个值，否则就不是强一致性。
- A：Availability 表示可用性，系统在任何时刻都能正常响应请求，哪怕部分节点挂了、网络抖动，也能访问。例如：用户访问一个网站，即使有一个数据中心宕机了，系统也要保证能继续返回内容。
- P：Partition Tolerance 表示分区容忍性，指的是系统能容忍网络出现分区故障，有些节点之间的通信失败了，系统仍要能继续运行。
在这三者中，如果 P 是必须的，这在分布式系统中这是无法避免的。在这样的背景下，系统最多只能保证 C 和 A 中的 一个。也就是说：
- C + P (放弃可用性)。
- A + P (放弃强一致性)。
核心思想
CRDT 的核心思路就是 放弃强一致性，转而追最终一致性，这是 CRDT 的一大特点。
在 CRDT 系统中，各个副本可以并发、独立地进行、本地修改，而无需等待远程同步或获得锁。即便出现网络延迟，甚至设备离线，只要最终各个副本都收到相同的操作或状态，就能够自动合并为一致的最终结果，而不需要中心协调或额外的冲突解决机制。
所以说 CRDT 的设计哲学是：
只要所有副本最终都收到相同的信息(状态或操作)，不管谁先谁后、什么时候收到，最终状态就一定一样。
具体示例
初始文档为 abc，有两个用户 A 和 B 进行如下的编辑，采用 CRDT 算法。
首先需要设计一种带 ID 的数据结构，每个字符有一个唯一的 ID，如：
{
// 当前的字符
char: 'x',
// 当前这个字符位置的 id 以及客户端的 id
id: [position_id, client_id]
}
对于用户 A 来讲，文本内容为 abc，初始文档按照上面的数据结构来设计，如下表：
| 字符 | ID（简写） | 说明 |
|---|---|---|
| a | [1, A] | 初始由 A 写入 |
| b | [2, A] | - |
| c | [3, A] | - |
用户 A 要插入 X 在 a 的后面，a 的 ID 为 [1, A]，插入后用户 A 会生成一个新的 ID：
// 表示插入到 position_id 1 和 2 之间
[1.5, A]
对于用户 A 来讲文档结构就变成：
[ [1, A]: 'a', [1.5, A]: 'X', [2, A]: 'b', [3, A]: 'c' ]
用户 B 插入 Y 在最前面，对于用户 B 来说，会生成一个新 ID：
[0.5, B]
对于用户 B 来讲，整个文档结构就变成：
[ [0.5, B]: 'Y', [1, A]: 'a', [2, A]: 'b', [3, A]: 'c' ]
在CRDT数据结构的设计中，文档的内容和作者并非强绑定的关系，每个字符节点对应的只有一个唯一的 ID。字符的 ID 反映的是该字符最初是谁插入的、在哪里插入的，而不是当前谁持有、谁读取或者谁同步到了它。
合并副本
最后需要对副本进行合并，两个副本并不存在冲突，只需要按照 ID 进行排序就可以了。
[0.5, B] → [1, A] → [1.5, A] → [2, A] → [3, A]
Y → a → X → b → c
在进行比较的时候，通常有一组比较的策略，例如可以先比较位置，位置相同比较客户端 ID。
理论实现
CRDT 是一套理论，基于这套理论，有各种不同的实现，不同的实现自然 ID 的设计也会有所不同。
| CRDT 算法 | ID 结构 | 特点 |
|---|---|---|
| RGA | [前一字符 ID, 副本 ID] | 通过链表式插入 |
| Logoot | [路径 ID, 用户 ID] | ID 可排序且稀疏 |
| Yjs | 类似 Logoot + 优化 | 实际使用偏移机制 |
数据结构
在 CRDT 中，数据结构的设计非常关键，要求设计出来的数据结构具备以下的特点：
- 可交换性：只要每个副本使用相同的合并函数，那么不论先后，最终能得到相同的结果。这个特点可以无视消息的到达顺序，不需要去协调谁先谁后。
merge(a, b) === merge(b, a)
- 可结合性：合并的顺序可以自由的嵌套，不影响结果。同样可以保证多个副本汇合合并的时候不需要在意操作顺序。
merge(merge(a, b), c) === merge(a, merge(b, c))
- 幂等性：同样的数据或者操作，即便合并多次，结果也不会变化。网络往往是不稳定的，存在重发消息的情况，因此必须保证多个副本合并多次保持同一状态。
merge(state, state, state, ...) === state
冲突免疫
CRDT 的数据结构的设计确保所有操作天然不冲突，即使并发发生也无需判断谁赢谁输，这一点是和 OT 之间的最大区别。
[ [1, A]: 'a', [2, A]: 'b', [3, A]: 'c' ]
// 用户A : 插入一个 c
[ [1, A]: 'a', [2, A]: 'b', [3, A]: 'c', [4, A]: 'c' ]
// 用户B：删除一个 c
[ [1, A]: 'a', [2, A]: 'b', [3, A]: 'c'(delete)]
// 两个副本进行合并
[ [1, A]: 'a', [2, A]: 'b', [4, A]: 'c']
CRDT数据结构
在 2011 年发表的 CRDT的论文 中，论文作者明确提出并设计了一些具有代表性的 CRDT 数据结构，每一个都体现了 CRDT 的核心原则：无需协调、天然可合并、保证最终一致性。论文中正式提出并详解的数据结构包括：
| 名称 | 类型 | 特点总结 | 支持操作 |
|---|---|---|---|
| G-Counter | CvRDT | 只能递增，每个副本维护自己计数 | 增加 |
| PN-Counter | CvRDT | 支持加减，使用两个 G-Counter | 增加 / 减少 |
| G-Set | CvRDT | 只能添加元素，不能删除 | 添加 |
| 2P-Set | CvRDT | 添加 + 删除（删除不可恢复） | 添加 / 删除 |
| LWW-Element-Set | CvRDT | 添加/删除带时间戳，最后写入者生效 | 添加 / 删除 |
| OR-Set | CvRDT | 使用唯一 ID 跟踪添加/删除操作 | 添加 / 删除 |
| Graph（有向图） | CvRDT | 节点和边都是 OR-Set 构建，支持惰性删除 | 添加节点 / 边 / 删除 |
G-Counter
G-Counter，英文全称是 Grow-only Counter，这是一个 只能递增 的分布式计数器，每个副本维护自己的局部值， 所有副本最终通过取最大值进行合并，从而保证最终一致。
G-Counter 的核心是一个 以副本 ID 为 key 的映射表：
{
// 这里的 A、B、C 就是副本 ID，也就是客户端 ID
A: 3,
B: 5,
C: 0
}
每个副本（比如客户端 A、B、C）只能操作自己的那一项。
该数据结构支持的操作有：
increment()增加计数。只能增加，不支持减！merge()合并另一个副本的状态，对每个副本 ID 的值取最大值。value()计算当前总和，将所有客户端的计数全部累加起来。
举一个例子，初始的时候，两个客户端 A 和 B，因此就有两个副本，分别是 副本 A 和副本 B
副本 A: { A: 3 } // 在客户端A，用户点击了 3 次
副本 B: { B: 4 } // 在客户端B，用户点击了 4 次
// 假设现在没有联网，两者都是处于离线状态
-
A 的 G-Counter 里，只知道自己加了 3 次
-
B 的 G-Counter 里，只知道自己加了 4 次
假设此时，A 又本地加了 1：A: { A: 4 }，B 又本地加了 1：B: { B: 5 }，那么此时各副本的状态为：
- A 的副本状态是
{ A: 4 } - B 的副本状态是
{ B: 5 } - 注意：现在仍然是离线状态
接下来假设来网了，两个副本开始互相同步状态。这里就涉及到要做一个 merge() 操作，把两个 G-Counter 合并成一个一致的状态。merge() 具体如何做呢？合并规则很简单：对每个副本 ID，取它在两个副本中值的最大值。我们来计算：
A 的值：max(A副本的A值, B副本的A值) = max(4, undefined) = 4
B 的值：max(A副本的B值, B副本的B值) = max(undefined, 5) = 5
undefined代表这个副本没记录过这个 ID。
合并出来的结果为 { A: 4, B: 5 }，这个结果现在被 A 和 B 同时拥有，也就是它们两个副本的状态同步了。
- A 的副本状态是
{ A: 4, B: 5} - B 的副本状态是
{ A: 4, B: 5}
因此总的值就为：
value = 4 + 5 = 9
这个值就是当前这个计数器代表的全局计数值。
应用场景
- 点赞数 / 浏览量：每个副本只需要往上加。
- 分布式日志计数：多节点写日志，最后总数一致即可。
- 活跃节点统计：每个节点上报“活跃数”，总数即在线节点数。
CRDT类型
在论文中，提到了 CRDT 可以分为两种类型：
- 状态型 CRDT，英文缩写为 CvRDT，Convergent Replicated Data Type
- 操作型 CRDT，英文缩写为 CmRDT，Commutative Replicated Data Type
CvRDT
定义：每个副本维护自己的完整状态，副本之间周期性同步整个状态对象，合并时使用一个具有数学特性的 merge() 函数，使多个副本最终收敛为一致的状态。
特点
| 特性 | 说明 |
|---|---|
| 同步单位 | 整个“状态”（state） |
| 合并机制 | merge() 函数（满足 交换 + 结合 + 幂等） |
| 合并时机 | 异步、周期性、最终到达 |
| 抗延迟/断网 | 非常强（副本之间互相独立演进） |
| 要求副本持有完整状态 | 是 |
经典的 CvRDT 例如：
- G-Counter：每个副本存一份
{ replicaId: number }，合并时取最大值 - OR-Set：add/remove 是状态，合并时做集合并集
- Graph CRDT：节点/边状态可直接合并
CmRDT
定义：每个副本本地执行修改，同时将操作（operation）发送给其他副本，操作之间是可交换的（Commutative），所以不同副本按任意顺序执行都能得到相同结果。
特点
| 特性 | 说明 |
|---|---|
| 同步单位 | 操作（operation） |
| 合并机制 | 每个副本按本地逻辑执行操作 |
| 操作要求 | 必须是“可交换的” |
| 网络要求 | 每个操作都必须可靠地送达一次 |
| 对操作顺序的依赖 | 无（顺序无关） |
经典的 CmRDT 例如：
- RGA（Replicated Growable Array）：文本插入操作是
insert(afterId, value)，谁先谁后无所谓 - Logoot、Yjs：插入/删除基于唯一 ID，执行顺序不影响最终顺序
- 聊天消息流 CRDT：每条消息是一个 append 操作
两者对比如下表所示：
| 对比维度 | CvRDT | CmRDT |
|---|---|---|
| 同步的内容 | 状态（整个结构） | 操作（insert/delete等） |
| 合并方式 | merge() 函数 | 顺序无关执行所有操作 |
| 是否要求操作可交换 | 否（状态可合并即可） | ✅ 是 |
| 是否要完整状态 | ✅ 是 | ❌ 否（只要操作流） |
| 网络要求 | 支持延迟/离线 | 要求操作可靠送达（但可乱序） |
| 实现复杂度 | 简单清晰 | 实现更复杂，需处理引用 ID、时钟等 |
OT vs CRDT
两种方法的相似之处在于它们提供了最终的数据一致性。不同之处在于他们如何做到这一点：
- OT 通过算法控制保证数据一致性：操作通过发送到服务端，一旦收到就会进行转换（ OT 控制算法）。
- CRDT 通过数据结构保证数据一致性：操作是在本地 CRDT 上进行的，它的状态或者操作通过网络发送并与副本的状态合并。
其他不同点
- OT 是基于中央服务器进行转换操作；而 CRDT 只需要与同伴交换新数据，不需要中央服务器，每个客户端都可以是独立完整的版本，支持离线进行操作，因此稳定性很高。
- OT 相较于 CRDT 发展更早，技术体系更为成熟，服务端压力大，客户端无需像 CRDT 那样存储大量额外元数据，因此压力较小。服务端重客户端轻
- OT 用复杂性换来了对用户预期的实现；而 CRDT 则更加关注数据结构，复杂性低，不过随着数据结构的复杂度上升，算法的时间和空间复杂度也会呈指数上升的，会带来性能上的挑战。服务端轻客户端重
- OT 处理不同数据模型需要实现不同的转换算法；CRDT 只需要转化数据结构。
- CRDT 去中心化的特征使其很容易实现离线编辑；
另外在这篇 文章 中，作者也提到了为什么 AFFiNE 选择 CRDT 而非 OT 来构建协作编辑器。
AFFiNE 是一个开源的现代化协同文档编辑器项目，该项目采用了 Notion + Miro + Obsidian 的混合风格，强调：
- 支持多人协作
- 支持本地编辑
- 支持 markdown + 富文本 + 白板
- 基于 CRDT 技术实现同步
AFFiNE 目标是构建一个“本地优先、支持多人实时协作、集文档、白板、任务于一体”的全功能办公工具。