CRDT
Outlinks (0)
No outlinks found
Backlinks (1)
Backlinks (1)
1 · CRDT#
https://en.wikipedia.org/wiki/Conflict-free_replicated_data_type
S 分布式系统中，数据被复制到多个节点上；用户期望在任意节点读写，且多节点可以同时独立更新同一份数据（协同编辑、离线同步、多主复制） C 并发更新会产生冲突；传统方案要么加锁/共识（牺牲延迟和可用性），要么使用 OT 等复杂算法；网络分区时这些协调手段直接失效 Q 有没有一种数据结构，让多个副本可以独立并发修改，不需要协调，也不需要手动解冲突，最终自动收敛到一致状态？ A CRDT（Conflict-free Replicated Data Type）。通过数学性质（半格/交换律）保证合并操作无冲突，任何副本收到所有更新后自动收敛，达到强最终一致性（SEC）
1.1 · 1. 核心思想#
CRDT 的关键洞察：不去阻止冲突，而是设计让冲突不可能产生的数据结构
传统思路：先检测冲突 → 再解决冲突（锁、共识、OT） CRDT 思路：让合并操作天然满足数学性质 → 冲突在数学上不存在
所需的数学性质：
- 交换律 (commutativity)：合并顺序无关 → merge(A,B) = merge(B,A)
- 结合律 (associativity)：分组无关 → merge(merge(A,B),C) = merge(A,merge(B,C))
- 幂等性 (idempotency)：重复合并无影响 → merge(A,A) = A
这三个性质合在一起 = join-semilattice（半格），保证无论消息乱序、重复、延迟，最终状态都一样
1.2 · 2. 强最终一致性 (SEC)#
普通最终一致性 (EC)：
- 更新最终会传递到所有节点
- 如果两个节点看到了相同的更新集合，它们最终状态一致
强最终一致性 (SEC)：
- 更新最终会传递到所有节点
- 如果两个节点看到了相同的更新集合，它们立即状态一致（不需要额外的协调轮次）
SEC 的工程意义：
- 低延迟：节点不需要互相协调就能处理读写
- 高可用：系统中只要有一个节点活着就能正常工作
- 离线友好：节点可以断网任意长时间，重新连接后合并即可
SEC 就是”真正能用的最终一致性”。做 local-first 或地理分布式系统，不要接受比 SEC 更弱的保证。
1.3 · 3. 两类 CRDT#
1.3.1 · State-based CRDT (CvRDT, 收敛型)#
工作方式：每次同步时传输完整状态，接收方用 merge 函数合并
replica A 的状态 ──────→ replica B
B.state = merge(B.state, A.state)要求：
- merge 函数满足交换律、结合律、幂等性（构成半格）
- update 函数必须单调递增（按半格偏序）
- 通信层只需要 gossip 协议，对消息无特殊要求
优点：实现简单，对网络要求低（消息可丢可重） 缺点：每次传输完整状态，数据量大
1.3.2 · Operation-based CRDT (CmRDT, 交换型)#
工作方式：只广播操作，各节点本地应用
replica A: increment(+3) ──广播──→ 所有其他 replica 应用 increment(+3)要求：
- 操作满足交换律
- 通信层必须保证：不丢消息、不重复、因果有序
优点：传输数据小 缺点：对通信中间件要求高
1.3.3 · Delta-state CRDT#
State-based 的优化：不传完整状态，只传最近变更的增量（delta）
兼具两者优点：传输量小 + 对网络要求低
1.4 · 4. 常见 CRDT 数据结构#
1.4.1 · Counter#
G-Counter（只增计数器）
- 每个节点维护自己的计数器
P[nodeId] - 只能递增，值 = ΣP[i]
- merge：每个槽位取 max →
Z.P[i] = max(X.P[i], Y.P[i])
PN-Counter（可增可减计数器）
- 两个 G-Counter 组合：P 计增量，N 计减量
- 值 = ΣP[i] - ΣN[i]
- merge：分别对 P 和 N 取 max
1.4.2 · Set#
G-Set（只增集合）
- 只能 add，不能 remove
- merge = 两个集合取并集
2P-Set（两阶段集合）
- 两个 G-Set：add-set A + tombstone-set R
- lookup(e) = e ∈ A ∧ e ∉ R
- 一旦 remove 就不能再 add 回来（remove-wins）
LWW-Element-Set（最后写入胜出集合）
- add-set 和 remove-set 中的元素都带时间戳
- 元素是否存在取决于 add 和 remove 的时间戳谁更新
- 支持 re-add（克服 2P-Set 的限制）
OR-Set（Observed-Remove Set）
- 每次 add 生成唯一 tag
- remove 时只移除当前已观察到的 tag
- 并发 add + remove → add-wins（因为新 add 的 tag 不在 remove 列表中）
- 实践中最常用的 Set CRDT
1.4.3 · Sequence (序列)#
用于协同编辑：多人同时编辑有序文本
常见算法：Treedoc, RGA, WOOT, Logoot, LSEQ
工业实现（性能远超学术实现）：
- Yjs：用 plain list 代替 tree，性能极好
- Automerge：支持版本控制和离线
1.5 · 5. 工业应用#
| 产品/系统 | 用法 |
|---|---|
| Apple Notes | 多设备离线编辑同步，使用 CRDT |
| Figma | 多人实时编辑，per-property LWW + fractional indexing |
| Redis | CRDT 模块，支持分布式数据管理 |
| Riak | 基于 CRDT 的分布式 KV 存储 |
| League of Legends | 游戏内聊天（Riak CRDT），750 万并发用户 |
| Phoenix (Elixir) | Presence 系统用 CRDT 做多节点实时状态共享 |
| Facebook Apollo | 低延迟 “consistency at scale” 数据库 |
| SoundCloud | Roshi（LWW-element-set on Redis）管理 stream |
1.6 · 6. CRDT vs 其他方案#
| CRDT | 共识 (Raft/Paxos) | OT | |
|---|---|---|---|
| 协调 | 不需要 | 需要多轮通信 | 需要中心服务器 |
| 延迟 | 本地即完成 | 取决于多数派 | 取决于服务器 |
| 可用性 | 极高（单节点可写） | 需要多数派存活 | 服务器挂了就不行 |
| 离线支持 | 天然支持 | 不支持 | 不支持 |
| 实现复杂度 | 中等（选对数据结构） | 高 | 高 |
| 适用场景 | 最终一致即可 | 需要强一致 | 文档协同编辑 |
1.7 · 7. 挑战#
- 元数据膨胀：tombstone set、版本向量等元数据会持续增长，需要 GC 策略
- 复杂数据类型：不是所有数据结构都有天然 CRDT 表示，可能需要组合多个 CRDT
- 语义约束：CRDT 只保证收敛，不保证业务语义（如库存不能为负），需要额外机制
- 调试困难：分布式状态合并的行为难以推理和测试
1.8 · 8. 关键判断#
什么时候该用 CRDT：
- 可以接受最终一致性（不需要强一致）
- 需要高可用、低延迟
- 有离线/弱网场景
- 数据可以建模为已知 CRDT 类型（计数器、集合、序列等）
什么时候不该用：
- 需要强一致性（如金融交易）
- 数据操作有复杂的不变量约束
- 数据量小、节点少、网络好 → 直接用共识更简单
Ref: