CRDT 无冲突复制数据类型深度实战：从 G-Counter 到 OR-Set 与协作编辑引擎
引言
在分布式系统的工程实践里，复制（Replication）几乎是一切高可用与低延迟的前提。但复制天生带来一个尖锐的矛盾：当多个副本同时被写入，节点之间又可能断网、分区、延迟，谁的状态才算"真相"？传统做法是用共识（Paxos/Raft）或分布式锁把写入串行化，代价是牺牲可用性、引入协调开销。
CRDT（Conflict-free Replicated Data Type，无冲突复制数据类型）提供了一条截然不同的路径：它不靠协调来避免冲突，而是把数据结构设计成"无论如何合并都不会冲突"——只要所有副本最终收到全部更新，无论以什么顺序、重复多少次，它们都会收敛到完全相同的状态。这种"无协调的最终一致性"正是离线优先应用、多人实时协作编辑、边缘多活缓存得以成立的数学基石。本文从最基础的计数器出发，逐层构建 G-Counter、PN-Counter、OR-Set、LWW-Register，再对比主流生产级实现，最后用 Rust 从零拼出一个可收敛的协作数据结构引擎。
一、强一致 vs 最终一致：CAP 之后的工程现实
CAP 定理告诉我们，在网络分区（P）必然发生的前提下，系统只能在一致性（C）与可用性（A）之间二选一。当业务选择 AP（可用且分区容忍）时，不同副本在数据到达一致之前会短暂看到不同的世界，冲突由此产生。问题不在于"是否会有冲突"，而在于"如何以可预测、可收敛的方式解决冲突"。
常见的冲突解决策略有三种，代价各不相同：
- 最后写入获胜（LWW）：用时间戳裁决，实现简单，但会静默丢更新，且对时钟高度敏感。
- 人工/应用层合并：把冲突暴露给业务，灵活但开发成本高、易出错。
- CRDT 自动合并：把收敛性写进数据类型的数学定义里，任何合法合并都安全——这正是本文的主角。
CRDT 的精髓可以概括为一句话：把"并发"当作常态而非异常，用代数结构保证所有可能的合并路径殊途同归。
二、CRDT 的两大家族：CvRDT 与 CmRDT
根据"复制的单位是什么"，CRDT 分为两大阵营：
- 状态复制 CRDT（CvRDT / 收敛式）：节点之间传输的是数据状态，通过定义一个满足交换律、结合律、幂等律的"合并（merge / join）"操作，让状态在偏序格（join-semilattice）上单调收敛。
- 操作复制 CRDT（CmRDT / 交换式）：节点之间传输的是操作（如 "add x"、"remove x"），要求底层传输保证操作最终送达且至少一次（delivery + idempotency），靠操作本身的可交换性收敛。
两者的数学要求可以统一表述：合并/操作必须可交换（a·b = b·a）、可结合（(a·b)·c = a·(b·c)）、幂等（a·a = a）。满足这三条，系统就能在任意顺序、任意次数的交付下收敛。下面的表格对比了二者的工程取舍：
| 维度 | 状态复制（CvRDT） | 操作复制（CmRDT） |
|---|---|---|
| 复制单位 | 完整或增量状态 | 细粒度操作 |
| 传输要求 | 幂等即可，可丢可重 | 必须保证送达且至少一次 |
| 元数据开销 | 与状态规模相关，可能偏大 | 与操作数相关，通常更小 |
| 典型代表 | G-Counter、PN-Counter、OR-Set（状态版） | Op-based OR-Set、RGA 序列 |
| 适用场景 | 反熵 gossip、云多活 KV | 协作编辑、本地优先应用 |
三、G-Counter：可交换的增量计数
我们从最简单却最有用的 CRDT 起步——一个支持多副本并发自增、最终求和一致的计数器（Grow-only Counter）。它的核心思想是：不为整个计数器维护一个标量，而是为每个副本（replica）维护一个独立的计数轴（vector of counters），读取时把所有轴求和，合并时逐轴取最大值。
为什么"逐轴取最大值"能保证收敛？因为对每个副本的轴而言，自增只会让它单调增大，max 操作天然满足交换律、结合律与幂等律。无论两个副本以什么顺序交换状态，合并结果都等于"每个轴上见过的最大值"，而所有轴的最大值之和就是全局真实总量。
use std::collections::HashMap;
// 每个副本一条独立计数轴，key 是 replica id
#[derive(Clone, Debug, Default)]
struct GCounter {
counts: HashMap<String, u64>,
}
impl GCounter {
fn new() -> Self {
GCounter::default()
}
fn increment(&mut self, replica: &str, by: u64) {
let e = self.counts.entry(replica.to_string()).or_insert(0);
*e += by;
}
fn value(&self) -> u64 {
self.counts.values().sum()
}
// 核心：状态合并 = 逐轴取最大值
// 天然可交换 / 结合 / 幂等
fn merge(&mut self, other: &GCounter) {
for (r, v) in &other.counts {
let e = self.counts.entry(r.clone()).or_insert(0);
if *v > *e {
*e = *v;
}
}
}
}注意 merge 里没有"加法"，只有"取最大值"。这正是 G-Counter 与"各自累加后求和"的本质区别：如果用加法合并两个都见过增量 A:3 的副本，会得到 A:6 的灾难性翻倍；而取最大值只认"见过的最大计数"，天然幂等。这也就是为什么 CRDT 必须把状态建模成单调格。
四、PN-Counter：正负分离的计数器
G-Counter 只能增长，无法表达"扣减"。PN-Counter（Positive-Negative Counter）用一对 G-Counter 化解：一个记录所有正向增量，一个记录所有负向增量，读取时二者相减。由于两个 G-Counter 各自独立收敛，它们的差也必然收敛。
#[derive(Clone, Debug, Default)]
struct PNCounter {
p: GCounter, // 正向累计
n: GCounter, // 负向累计
}
impl PNCounter {
fn new() -> Self {
PNCounter::default()
}
fn increment(&mut self, replica: &str, by: u64) {
self.p.increment(replica, by);
}
fn decrement(&mut self, replica: &str, by: u64) {
self.n.increment(replica, by);
}
fn value(&self) -> i64 {
self.p.value() as i64 - self.n.value() as i64
}
fn merge(&mut self, other: &PNCounter) {
self.p.merge(&other.p);
self.n.merge(&other.n);
}
}PN-Counter 看起来简单，却藏着 CRDT 设计的一条通用法则：复杂类型往往由简单收敛类型组合而来。只要组合方式本身保持单调性（这里是"两个分别收敛的量做差"），整体就依然收敛。
五、OR-Set：支持添加的 Observed-Remove 集合
集合比计数器难得多。一个朴素想法是 "add 就插入、remove 就删除"，但这在并发下会出大问题：副本 A 添加元素 x，副本 B 删除元素 x，若 B 的删除先到达 A，A 执行删除；随后 A 添加 x 的更新才到达——结果 x 被重新插入，可 B 明明删除了它。这就是经典的"删除的更新被后到的添加覆盖"陷阱。
OR-Set（Observed-Remove Set）的解法是给每个被添加的元素附带一个全局唯一标签（tag），删除时不删"元素名"，而是删除"当前观察到的那一组 (元素, tag)"。这样后到的添加携带的是全新的 tag，永远不会被旧删除误伤。下面用 Rust 给出一个状态版 OR-Set：
use std::collections::HashSet;
#[derive(Clone, Debug, Default)]
struct ORSet {
// 已添加的元素副本，每个带唯一 tag
added: HashSet<(String, u128)>,
// 已删除的元素副本（按 tag 精确标记）
removed: HashSet<(String, u128)>,
}
impl ORSet {
fn add(&mut self, elem: &str, tag: u128) {
self.added.insert((elem.to_string(), tag));
}
// 删除时只移除"本次观察到"的该元素副本
fn remove(&mut self, elem: &str) {
let observed: Vec<(String, u128)> = self
.added
.iter()
.filter(|(e, _)| e == elem)
.cloned()
.collect();
for t in observed {
self.removed.insert(t);
}
}
fn contains(&self, elem: &str) -> bool {
self.added
.iter()
.any(|(e, t)| e == elem && !self.removed.contains(&(e.clone(), *t)))
}
fn merge(&mut self, other: &ORSet) {
for a in &other.added {
self.added.insert(a.clone());
}
for r in &other.removed {
self.removed.insert(r.clone());
}
}
}OR-Set 的代价是元数据随添加次数线性增长——每次 add 都产生一个新 tag，删除只标记不回收，因此需要一个独立的"墓碑（tombstone）GC"策略来清理已被全网确认删除的 tag。这是生产落地时最容易被忽视的工程细节。
六、LWW-Register 与时钟陷阱
有时候我们并不想保留全部历史，只想要"最新值"。LWW-Register（Last-Writer-Wins Register）给每个写入打时间戳，合并时取时间戳更大者。它的实现极简，但埋着两个深坑：
- 墙钟不可靠：NTP 回拨、闰秒、不同节点时钟漂移都会让"更大时间戳"不代表"更晚发生"。
- 平局歧义：同一毫秒内两个并发写，时间戳相等，必须有一个确定性的决胜规则，否则不同副本可能选不同的赢家，破坏收敛。
工程上的标准是：用混合逻辑时钟（HLC）替代墙钟，并在时间戳相等时用副本 ID 的字典序做确定性裁决。下面是带平局裁决的 Rust 实现：
use std::time::{SystemTime, UNIX_EPOCH};
#[derive(Clone, Debug)]
struct LWWRegister<T: Clone> {
value: T,
timestamp: u128,
replica: String,
}
impl<T: Clone> LWWRegister<T> {
fn new(value: T, replica: String) -> Self {
LWWRegister {
value,
timestamp: now(),
replica,
}
}
fn set(&mut self, value: T) {
self.value = value;
self.timestamp = now();
}
fn merge(&mut self, other: &LWWRegister<T>) {
// 时间戳更大者胜；平局时由副本 ID 字典序确定性裁决
if other.timestamp > self.timestamp
|| (other.timestamp == self.timestamp && other.replica > self.replica)
{
self.value = other.value.clone();
self.timestamp = other.timestamp;
self.replica = other.replica.clone();
}
}
}
fn now() -> u128 {
SystemTime::now()
.duration_since(UNIX_EPOCH)
.unwrap()
.as_millis()
}七、向量时钟与因果一致性
CRDT 之所以"无冲突"，是因为它把并发事件当作可交换的，并不关心谁先谁后。但有些场景我们需要知道"副本 B 的写入是否看到了副本 A 的写入"——这就是因果关系。向量时钟（Vector Clock）用一个长度等于副本数的数组记录每个副本"已知的最大版本"，通过比较数组可以判定：a 因果先于 b、b 因果先于 a、或二者并发。
要注意的是，纯 CRDT（如上面的 G-Counter）不需要向量时钟也能收敛；但当我们要在 CRDT 之上叠加"因果投递保证"（例如确保操作按因果顺序应用到 CmRDT），向量时钟就是必需的基石。它与 CRDT 的关系是"互补"而非"替代"：CRDT 解决合并收敛，向量时钟解决因果排序。
八、生产级系统对比
理论落到工程，各家对 CRDT 的运用策略大相径庭。下表列出几个有代表性的系统，供选型时对照：
| 系统 | 类型 | 实现语言 | 同步方式 | 典型场景 |
|---|---|---|---|---|
| Riak DT | CvRDT | Erlang | 反熵 gossip | 高可用 KV 存储 |
| Redis CRDB | CvRDT | C | 主动全量同步 | 多活缓存 / 会话 |
| Yjs | CvRDT + CmRDT 混合 | TypeScript | 增量更新广播 | 离线优先协作编辑 |
| Automerge | CmRDT | Rust | 变更日志同步 | 本地优先应用 |
| AntidoteDB | CvRDT | Erlang | 无协调事务提交 | 强最终一致数据库 |
| SoundCloud Roshi | CvRDT | Go | gossip 反熵 | 高写吞吐计数器 |
九、实战：用 Rust 验证 CRDT 的收敛性
光说不练没有说服力。下面这段驱动代码模拟三个副本并发写入、再以任意顺序两两合并，最后断言三者数值严格相等——这正是 CRDT 收敛性的"压力测试"：无论网络以什么诡异的顺序把状态送达，结果都必须一致。
fn main() {
// 三个副本并发写，再以任意顺序两两合并
let mut a = GCounter::new();
let mut b = GCounter::new();
let mut c = GCounter::new();
a.increment("A", 3);
b.increment("B", 5);
c.increment("C", 2);
a.increment("A", 1); // A 轴累计到 4
// 任意顺序、任意次数的合并
b.merge(&a);
c.merge(&b);
a.merge(&c);
b.merge(&a);
c.merge(&b);
assert_eq!(a.value(), b.value());
assert_eq!(b.value(), c.value());
println!("converged value = {}", a.value()); // 4 + 5 + 2 = 11
}如果你把同样的随机合并跑一万次、每次打乱合并顺序，断言永远成立。这就是 CRDT 区别于"乐观锁重试""人工冲突解决"的根本优势：收敛性由类型本身担保，不依赖任何外部协调器。
十、选型指南与落地陷阱
CRDT 不是银弹，它有明确的适用边界。下面给出一张速查表：
| 场景 | 是否推荐 | 理由 |
|---|---|---|
| 多人协作编辑 / 白板 | 强烈推荐 | 天然收敛，离线可编辑 |
| 离线优先移动端 | 推荐 | 无协调，通电即同步 |
| 全局热点计数器 | 不推荐 | 每副本一条轴，元数据随副本数膨胀 |
| 需全序 / 串行的金融账本 | 不推荐 | CRDT 只保证收敛，不保证操作顺序 |
| 小规模配置分发 | 看情况 | 状态小可用 LWW，避免 OR-Set 墓碑膨胀 |
落地时还有三个高频陷阱值得单独提醒：
- 墓碑回收：OR-Set、序列型 CRDT 会持续累积删除标记，必须有全网确认的 GC 机制，否则状态无限膨胀。
- 元数据增长：CvRDT 的状态大小通常与"写入历史"或"副本数"相关，热点场景要评估内存与带宽成本。
- 测试收敛而非测试功能：传统单测验证"输入输出"，CRDT 单测必须验证"任意合并顺序下结果一致"，常用随机化乱序合并（像上面的 main）来覆盖。
结语
CRDT 把"分布式系统中的冲突"从工程难题降级为一个代数性质问题：只要数据结构在偏序格上单调、合并可交换结合幂等，一致性就不再是需要运行时协调的奢侈品，而是类型自带的保证。从一行 max 就能收敛的 G-Counter，到支撑 Figma、Notion、本地优先应用的协作编辑引擎，背后是同一套数学。理解它，你就能在"高可用还是要一致"的伪二选一之外，找到第三条路——让数据自己学会和解。
发表评论 取消回复