CRDT冲突算法 - wangshengliang

CRDT 算法的英文全称为 Conflict-free Replicated Data Type，翻译成中文叫做“无冲突复制数据类型”。

OT的缺陷

由于是 强一致性的设计，所有操作都需要在服务器端进行转换，从而避免冲突，因此 OT 算法对网络的要求比较高，如果某个用户出现网络异常，导致一些操作缺失或延迟，那么服务端的转换就会出现问题。

也正因为这个特点，导致 OT 算法不太适合用于分布式的系统。而分布式系统又是目前解决超级复杂问题的唯二选择。

超级计算机，例如量子计算机
分布式系统

CAP理论

CAP 理论由 Eric Brewer 于 2000 年提出，是三个英文单词的首字母缩写：

C：Consistency 表示 一致性，所有节点访问的数据 必须是最新的、完全一致的。举个例子：如果你在分布式数据库 A 节点写入了一条记录，然后立刻去 B 节点读取，你应该立刻能读到这个值。否则就不是“强一致性”。
A：Availability 表示 可用性，系统在任何时刻都能 正常响应请求，哪怕部分节点挂了、网络抖动，也要能访问。举个例子：用户访问一个网站，即使有一个数据中心宕机了，系统也要保证能“继续返回内容”。
P：Partition tolerance 表示 分区容忍性，指的是系统能容忍网络出现 分区故障，也就是有些节点之间的通信失败了，系统仍要能继续运行。

那么在这三者中，P 是必须的，这在分布式系统中这是无法避免的。在这样的背景下，系统最多只能保证 一致性（C）和可用性（A） 中的一个。也就是说：

C + P（放弃可用性）
A + P（放弃强一致性）

举例说明：一个 分布式购物车系统 部署在两个城市 A 和 B，系统不能因为网络抖动就挂掉（Partition tolerance）。此时用户 A 向购物车加了一个商品，用户 B 马上刷新页面应该也能看到（Consistency），用户随时可以操作购物车（Availability）。
好了，那么假设现在网络断开（A < - > B 通信失败），你就必须做出选择：

如果你保 C（强一致性）：B 城市的用户可能无法操作购物车，系统返回错误

如果你保 A（可用性）：B城市的用户可以继续操作，但是在一段时间内数据不同步

CRDT 的核心思路就是 放弃强一致性，转而追求 最终一致性。这是属于 CRDT 的一大特点。

也就是说在 CRDT 系统中，各个副本可以并发、独立地进行 本地修改，而无需等待远程同步或获得锁；即便出现网络延迟、分区、甚至设备离线，只要最终各个副本都收到相同的操作或状态，就能够自动合并为一致的最终结果，而不需要中心协调或额外的冲突解决机制。所以我们说 CRDT 的设计哲学是：

只要所有副本最终都收到相同的信息（状态或操作），不管谁先谁后、什么时候收到，大家 最终状态 就一定一样。

具体示例

假设还是这个需求：初始文档为 abc，有两个用户 A 和 B 进行如下的编辑：

A 插入 'X' 到位置 1（变成 "aXbc"）
B 插入 'Y' 到位置 0（变成 "Yabc"）

如果是采用前面所讲的 OT 算法，那么整个流程如下图：

                初始状态
                    ↓
            ┌──────────────┐
            │     abc      │
            └──────────────┘
              /         \
              /             \
A: Insert(1, 'X')     B: Insert(0, 'Y')
        ↓                    ↓
     文档 aXbc            文档 Yabc
        ↓                    ↓
  A 收到 B 的操作        B 收到 A 的操作
        ↓                    ↓
      OT 变换               OT 变换
        ↓                    ↓
应用 B' = Insert(0, 'Y')   应用 A' = Insert(2, 'X')
        ↓                    ↓
 ┌──────────────┐     ┌──────────────┐
 │   YaXbc      │     │   YaXbc      │
 └──────────────┘     └──────────────┘
      ✅ 一致              ✅ 一致

那么采用 CRDT 算法，是怎样的呢？

首先第一步，需要设计一种带 ID 的数据结构，每个字符有一个唯一的 ID：

{
  char: 'x', // 当前的字符
  id: [position_id, client_id] // 当前这个字符位置的 id 以及客户端的 id
}

对于用户 A 来讲，文本内容为 abc，初始文档按照上面的数据结构来设计的话，如下表：

字符	ID（简写）	说明
a	[1, A]	初始由 A 写入
b	[2, A]	-
c	[3, A]	-

操作 1: 用户A要插入 X 在 a的后面

a 的 ID 为 [1, A]，这个时候用户A这边就会生成一个新的 ID：

;[1.5, A] // 表示插入到 position_id 1 和 2 之间

对于用户A来讲文档结构就变成：

[ [1, A]: 'a', [1.5, A]: 'X', [2, A]: 'b', [3, A]: 'c' ]

操作 2: 用户 B 插入 Y 在最前面

同理对于用户 B 来讲，这里会生成一个新 ID：

;[0.5, B]

对于用户 B 来讲，整个文档结构就变成：

[ [0.5, B]: 'Y', [1, A]: 'a', [2, A]: 'b', [3, A]: 'c' ]

在CRDT数据结构的设计中，文档的内容和作者并非强绑定的关系。每个字符节点对应的只有一个唯一的ID，要么是A插入的，要么是B插入。
[1, B]: 'a': 如果这么写，意味着用户 B 又重新插入了一次字符 a，并且给了这个新的字符 a 一个新的 ID.
总结一下：在 CRDT 中，字符的 ID 反映的是该字符 最初是谁插入的，在哪里插入的，而不是 当前谁持有、谁读取或者谁同步到了它。

合并副本

接下来进行两者的副本合并，你会发想两个副本并不存在冲突，只需要按照 id 进行排序就可以了。

[0.5, B] → [1, A] → [1.5, A] → [2, A] → [3, A]
Y → a → X → b → c

另外注意，在进行比较的时候，有一组比较的策略，例如可以先比较数字，数字相同比较 client_id.

因此一个字符的 id，基本都是由两个部分组成。

和 OT 一样，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' ]

[ [1, A]: 'a', [2, A]: 'b', [3, A]: 'c', [4, A]: 'c' ]

用户B：删除一个c

[ [1, A]: 'a', [2, A]: 'b', [3, A]: 'c' ]

[ [1, A]: 'a', [2, A]: 'b' , [3, A]: 'c'(delete)]

回头两个副本进行合并

[ [1, A]: 'a', [2, A]: 'b' , [4, A]: 'c']

-EOF-