CRDT（Conflict-free Replicated Data Types，无冲突复制数据类型）

📅 2026/7/2 4:55:20 👁️ 次浏览

核心思想CRDT 的关键是设计一种数据结构使得操作可交换commutative操作可重复idempotent操作顺序无关order-independent这样即使消息乱序重复发送延迟到达最终结果仍然一致称为“强最终一致性”。两大类 CRDT1️⃣ 状态型State-based / CvRDT每个节点维护完整状态定期同步并“合并状态”合并函数必须满足交换律结合律幂等性例子G-Set只增集合PN-Counter正负计数器2️⃣ 操作型Operation-based / CmRDT只传播操作而不是整个状态要求操作是可交换的例子协同编辑中的插入/删除操作常见 CRDT 示例计数器Counter比如点赞数节点 A1节点 B1无论同步顺序如何最终都是 2集合Set添加元素不会冲突删除需要特殊设计如 OR-Set文本编辑协同文档像Google DocsNotion多人同时编辑 CRDT 可以保证文本最终一致很多现代协同编辑系统都基于 CRDT 或类似技术CRDT vs 传统方案特性CRDT传统锁/主从是否需要中心节点❌ 不需要✅ 需要是否支持离线✅ 很强❌ 较弱冲突处理自动手动/复杂延迟低较高优点高可用AP 系统自动冲突解决支持离线操作低延迟缺点设计复杂需要数学性质保证数据结构受限不是所有类型都容易做成 CRDT可能占用更多存储需要额外元数据简单总结CRDT 就像是一个“自带合并规则”的数据结构不管谁先改、谁后改不管网络是否稳定最终大家的数据都会自动变成一样回到顶部实际应用场景用一个多人同时编辑一段文本的例子来一步步演示 CRDT 是怎么工作的。这个过程会尽量贴近像 Google Docs 或 Notion 背后的原理。初始文本Hi有两个用户用户 A设备 A用户 B设备 B两人同时离线编辑第一步给每个字符一个“唯一 ID”CRDT 的关键每个字符不是简单位置而是带唯一标识比如初始状态可以表示为H(id1), i(id2)第二步用户同时编辑用户 A 的操作A 想输入Heyi操作在 H 后插入e在 e 后插入y表示为insert(e, after id1, new_id3) insert(y, after id3, new_id4) 用户 B 的操作B 想输入Hoi操作在 H 后插入o表示为insert(o, after id1, new_id5)第三步发生网络同步乱序到达现在开始同步但注意消息可能乱序到达假设A 先收到 B 的操作B 后收到 A 的操作第四步合并操作核心在 A 的设备上原本 A 的本地状态H(1) e(3) y(4) i(2)收到 B 的操作insert(o, after id1, id5)问题来了 H 后面已经有 e 了还要插入 o怎么办CRDT 的解决办法确定性排序CRDT 会规定一个规则例如按 ID 排序或时间戳节点 ID假设排序规则是按 id 从小到大现在 H 后的元素有e(id3)y(id4)o(id5)排序后H e y o i在 B 的设备上B 原本H(1) o(5) i(2)收到 A 的操作insert(e, after 1, id3) insert(y, after 3, id4)合并后同样排序H e y o i第五步最终一致不管谁先同步操作顺序如何网络是否延迟最终两边都变成Heyoi这就是 CRDT 的核心能力不同路径收敛到同一个结果Strong Eventual Consistency关键点拆解1️⃣ 不用“位置”用“关系”不是插入到第2个位置 ❌而是插入到 id1 后面 ✅避免位置冲突2️⃣ 每个操作都是“可合并的”插入不会冲突删除用“标记删除”tombstone3️⃣ 必须有“确定性规则”比如ID 排序Lamport 时间戳节点 ID保证所有节点算出一样的结果

相关新闻