CRDT 深度工程：无冲突复制数据类型如何重塑协同与本地优先架构
如果你写过协同文档、离线优先 App，或者任何需要在弱网下仍然"能用"的多端系统，你一定撞过这堵墙：两个副本同时修改了同一份数据，等网络恢复后，怎么合？
传统答案分两派。一派是强一致：上 Raft/Paxos、分布式事务，让所有写入先过一次全局排序。代价是写延迟等于一次跨区 RTT，离线直接不可用。另一派是人工冲突解决：像 Git 那样把冲突暴露给用户，代价是把复杂度转嫁给产品体验——没人希望在文档里看到 <<<<<<< HEAD。
CRDT（Conflict-free Replicated Data Type，无冲突复制数据类型）给出了第三条路：放弃全局排序，用数据结构本身的数学性质保证收敛。任何两个副本，只要收到了相同的更新集合（不管顺序、不管重复几次），最终一定处于相同状态。这个性质叫 Strong Eventual Consistency（SEC）。
一、数学地基：为什么"顺序无关"是可能的
CRDT 的全部魔法，归结为一个代数结构：join-semilattice（并半格）。
给状态集合 $S$ 定义一个偏序 $\le$ 和一个二元运算 $\sqcup$（merge / join），要求满足三条：
- 交换律：$a \sqcup b = b \sqcup a$
- 结合律：$(a \sqcup b) \sqcup c = a \sqcup (b \sqcup c)$
- 幂等律：$a \sqcup a = a$
这三条凑齐，merge 就同时是顺序无关和重复无害的。前者意味着我们不需要给更新排全局序；后者意味着网络重传、消息队列的 at-least-once 投递全都无所谓——这是工程上极其实用的一条性质，它把"精确一次投递"这个分布式难题直接消解掉了。
再加一条约束：状态只能通过 $\sqcup$ 单调增长（单调性），那么系统天然收敛。设计 CRDT 的本质工作，就是把任意业务逻辑翻译成一个满足这四条律的状态表示。
一句话总结：CRDT 不是"解决冲突"的算法，而是让冲突在数学上不存在的数据建模方法。
二、两条路线：CvRDT 与 CmRDT
| 维度 | 状态型（CvRDT / convergent） | 操作型（CmRDT / commutative） |
|---|---|---|
| 传播内容 | 整个状态（或其增量 delta） | 操作本身（经过变换） |
| 通信开销 | 与状态规模相关，可用 delta 优化 | 与操作规模相关，通常更小 |
| 因果要求 | 无，任意拓扑、可重复投递 | 需保证因果序投递（否则需缓存重排） |
| 典型实现 | Automerge 早期、Redis CRDT | Yjs、Riak 的 op-based counter |
工程实践里这条界限正在模糊：Yjs 用 op-based 传输，但内部维护的 document state 依然是 CRDT；Automerge 2.0 转向了 columnar 编码 + delta 传输。选型时更该关心的是元数据膨胀和生态成熟度，而不是这个分类。
三、从计数器到协同编辑：逐个拆解
3.1 G-Counter：只增计数器
最简单的 CRDT。每个副本一个槽位，值 = 自己槽位累加；merge = 逐槽取 max。因为只增，max 天然满足交换/结合/幂等。
#[derive(Clone, Debug)]
struct GCounter {
id: usize,
counts: Vec<u64>,
}
impl GCounter {
fn inc(&mut self) { self.counts[self.id] += 1; }
fn value(&self) -> u64 { self.counts.iter().sum() }
fn merge(&mut self, other: &GCounter) {
for (i, v) in other.counts.iter().enumerate() {
if *v > self.counts[i] { self.counts[i] = *v; }
}
}
}PN-Counter 就是两个 G-Counter 相减（增一个、减一个）。注意 value() 是派生量，不能参与 merge——这是 CRDT 设计的第一原则：只有单调的底层状态可以合并。
3.2 LWW-Register：最后写入者胜
给每个写打上 Lamport 时间戳（逻辑时钟 + 副本 ID 打破平局），merge 取时间戳最大者。
#[derive(Clone, PartialEq, Eq, PartialOrd, Ord)]
struct Stamp { logical: u64, replica: u64 }
struct LwwRegister<T> {
value: T,
stamp: Stamp,
}
impl<T: Clone> LwwRegister<T> {
fn set(&mut self, v: T, s: Stamp) {
if s > self.stamp { self.value = v; self.stamp = s; }
}
fn merge(&mut self, o: &LwwRegister<T>) {
if o.stamp > self.stamp {
self.value = o.value.clone();
self.stamp = o.stamp.clone();
}
}
}LWW 是被滥用最多的 CRDT。 它满足收敛律，但语义是"丢数据"：两个并发写，静默丢弃其中一個。用它做 last_seen、status 这类幂等覆盖语义没问题；用它做协同编辑的文本，用户会看到输入凭空消失。判据很简单：如果两个并发写都承载用户意图，LWW 就是错的。
3.3 OR-Set：观察移除集合
集合的难点在"同时 add 和 remove"。2P-Set（加集合 + 删除集合）一旦删除就不能复活；OR-Set 给每个 add 分配唯一 tag（通常是 (replica_id, logical_clock)），remove 只删除它当时已观察到的 tag。
type Tag = { replica: string; clock: number };
type Elem<T> = { value: T; tags: Set<string> }; // tag 序列化后的 key
class ORSet<T> {
private elems = new Map<string, Elem<T>>(); // key = 值序列化
add(v: T, tag: Tag) {
const k = JSON.stringify(v);
const e = this.elems.get(k) ?? { value: v, tags: new Set() };
e.tags.add(tagKey(tag));
this.elems.set(k, e);
}
// 关键：只删自己"看得见"的 tag
remove(v: T) {
const k = JSON.stringify(v);
const e = this.elems.get(k);
if (!e) return; // 没见过 → 无 tag 可删
for (const t of e.tags) this.tombstones.add(t);
this.elems.delete(k);
}
private tombstones = new Set<string>();
merge(o: ORSet<T>) {
for (const t of o.tombstones) this.tombstones.add(t);
for (const [k, e] of o.elems) {
const live = new Set([...e.tags].filter(t => !this.tombstones.has(t)));
if (live.size === 0) continue; // 全被墓碑覆盖
const cur = this.elems.get(k);
this.elems.set(k, {
value: e.value,
tags: new Set([...(cur?.tags ?? []), ...live]),
});
}
}
}这个"add-wins"语义（并发的 add 战胜 remove）符合直觉：你删掉一个元素的同时别人在加它，说明那个元素此刻是有人想要的。反过来 2P-Set 的 remove-wins 更适合权限回收这类安全语义。
3.4 序列 CRDT：协同编辑的核心
文本是最难的一类。字符不是独立元素，它有位置，而位置在并发插入下会漂移。主流方案有三：
- OT（Operational Transformation）：变换操作使其可交换。Google Docs 早期方案。需要中心服务器定序，N 个客户端要写 $O(N^2)$ 种变换函数，工程上极易出 bug。
- RGA / Logoot / LSeq：给每个字符分配永不改变的全局唯一标识符（通常是
(replica_id, lamport)组成的路径），用标识符而非下标排序。插入就是在有序标识符序列里找一个空位。 - Yjs 的 YATA：用「左右原点 + origin」三元引用，配合冲突时按 replica id 打破平局，实测在网络抖动下比 RGA 有更低的元数据开销和更好的局部性。
// RGA 风格：插入依赖于「已存在的左邻」标识符
type Id = { replica: string; clock: number }; // Lamport 序
type Char = { id: Id; value: string; deleted: boolean };
function compareId(a: Id, b: Id): number {
if (a.clock !== b.clock) return a.clock - b.clock; // 先比逻辑时钟
return a.replica < b.replica ? -1 : 1; // 再比副本 ID，打破平局
}
// 插入：找到 left 之后第一个 id 不小于 newId 的位置
function integrate(chars: Char[], c: Char, leftIdx: number): number {
let i = leftIdx + 1;
while (i < chars.length && compareId(chars[i].id, c.id) < 0) i++;
chars.splice(i, 0, c);
return i;
}这段代码里藏着 CRDT 文本编辑的全部精髓：插入位置由标识符的偏序唯一决定，与到达顺序无关。A 在 "he" 后插入 "llo"、B 同时插入 "y"，两个副本无论先收到哪个，最终顺序都用 compareId 裁定，结果一致。
四、工程陷阱：论文不会告诉你的四件事
1. 墓碑（tombstone）无限膨胀。 删除必须留下墓碑，否则"删除"这个操作本身无法传播——晚到的副本会以为元素从没被删过。一个频繁增删的文档，墓碑最终会超过正文数据量。Yjs 的做法是：当所有副本都确认收到某次删除后（通过状态向量比对），才允许 GC 掉对应墓碑。这需要一轮额外的同步协议，不是纯 CRDT 能解决的。
2. 因果元数据比数据还大。 每个字符携带一个 Id，一篇 10 万字的文档可能有 10 万个 Id。Automerge 的应对是列式编码 + RLE 压缩，把「连续同副本递增时钟」压成 (start, len) 一条记录，实测能把元数据压到原始的 1%~5%。如果自研 CRDT，先想清楚编码方案，别直接朝 JSON 上堆。
3. 逻辑时钟会漂移。 Lamport 时钟只保证因果序，不保证与物理时间一致。用 LWW + 物理时间戳做跨端合并时，设备时钟不同步会导致"未来的写"永久压制"现在的写"。生产环境要么用混合逻辑时钟（HLC，保留物理时间可读性的同时保证因果），要么干脆别用 LWW。
4. 并非所有东西都能 CRDT 化。 「账户扣款」「库存扣减」这类有全局守恒约束的业务，CRDT 无解——你可以用 PN-Counter 让余额最终一致，但无法阻止并发扣款让余额变成负数。CRDT 保证收敛，不保证不变式（invariant）。需要不变式就得回到共识协议，或者引入补偿事务。这是选型时最重要的一条红线。
五、实战选型建议
- 协同编辑 / 白板：直接用 Yjs。它是目前生态最成熟的（y-websocket、y-indexeddb、各家编辑器 binding 齐全），性能在万级元素文档上依然流畅。Automerge 2.0 在 Rust/WASM 重写后性能追了上来，API 更"文档化"，适合 JSON 结构为主的场景。
- 离线优先的移动 / 桌面 App：Ditto、ElectricSQL、或者 SQLite 之上挂一层 CRDT（如
cr-sqlite）。核心是把 CRDT 下沉到存储层，业务代码读写本地 SQLite 即可，同步由扩展自动完成。 - 纯缓存 / 会话类数据：别上 CRDT。Redis 的 CRDT 方案（Active-Active）成本高昂，多数业务用「单写 + 读副本」就够了。
- 不要自己实现文本 CRDT。Yjs/Automerge 背后是十几年的论文积累和无数的边界 case（IME 组合输入、undo 语义、断线重连的状态向量对齐）。自研的合理范围是计数器、寄存器、集合这类简单类型。
六、结语
CRDT 的价值不在于"又一个一致性模型"，而在于它把分布式系统里最难的部分——并发与部分失败——从运行时挪到了数据建模阶段。一旦你把业务状态表达成一个 join-semilattice，剩下的网络层、重试、乱序、重复投递全都变成了无关紧要的细节。
代价也很清楚：元数据开销、墓碑管理、以及"无法表达全局不变式"这条硬边界。真正成熟的工程判断，是知道哪些数据该放进 CRDT，哪些必须留给共识协议。一个典型的协同文档产品，文档正文走 CRDT，权限和计费走事务——两者之间的边界，才是架构设计真正的着力点。
发表评论 取消回复