用 Rust 从零实现 CRDT:不需要协商的最终一致
三个副本同时把计数器加一。如果没有协调,最终值该是多少?
正常思路是"选一个赢家"或者"加锁"。CRDT 的思路完全不同:改数据结构,让合并结果与顺序无关。
三个副本各加一次,最终一定是 3——不管合并顺序如何,不管有没有重复合并。这不是"运气好",而是数据结构本身保证的。
先理解"交换律、结合律、幂等性"
CRDT 能工作的数学基础是三条性质:
交换律: merge(A, B) = merge(B, A)
结合律: merge(merge(A, B), C) = merge(A, merge(B, C))
幂等性: merge(A, A) = A这三条合起来叫"构成半格(join semilattice)"。 满足它们意味着:
- 顺序无关:交换律保证
- 分组无关:结合律保证
- 重复无害:幂等性保证(所以网络重传不会出错)
幂等性是 CRDT 最重要的性质。 分布式系统里消息重传是常态,如果合并不幂等,整个模型就崩了。
这三条性质决定了绝大多数 CRDT 的设计方向:状态必须是"只增不减"的(单调),因为"取最大值"天然满足这三条。
第一个 CRDT:G-Counter(只增计数器)
最简单的 CRDT。核心想法是:不存总数,存每个副本的计数。
use std::collections::HashMap;
#[derive(Debug, Clone, Default, PartialEq)]
pub struct GCounter {
/// 副本 id -> 该副本贡献的计数
counts: HashMap<String, u64>,
}
impl GCounter {
/// 本地 +1:只改自己的那一格
pub fn increment(&mut self, replica: &str) {
*self.counts.entry(replica.to_string()).or_insert(0) += 1;
}
/// 本地值 = 所有副本计数之和
pub fn value(&self) -> u64 {
self.counts.values().sum()
}
/// 合并:逐副本取较大值
pub fn merge(&mut self, other: &GCounter) {
for (replica, &count) in &other.counts {
let entry = self.counts.entry(replica.clone()).or_insert(0);
*entry = (*entry).max(count);
}
}
}为什么每个副本只加自己那一格? 因为这样"同一格"永远只有一个写入者——根本不存在冲突。
为什么合并用 max? 因为 max 天然满足三条性质:
max(a, b) = max(b, a) // 交换律
max(max(a,b), c) = max(a, max(b,c)) // 结合律
max(a, a) = a // 幂等性所以"取较大值"是构造 CRDT 最基本的积木。
验证一下:
#[test]
fn three_replicas_increment() {
let mut a = GCounter::default();
let mut b = GCounter::default();
let mut c = GCounter::default();
a.increment("a");
b.increment("b");
c.increment("c");
// 任意顺序合并,结果都是 3
a.merge(&b);
a.merge(&c);
assert_eq!(a.value(), 3);
// 重复合并也不变(幂等)
a.merge(&c);
assert_eq!(a.value(), 3);
}第二个 CRDT:PN-Counter(可增可减)
G-Counter 不能减。要支持减,用两个 G-Counter:一个记增加,一个记减少。
#[derive(Debug, Clone, Default)]
pub struct PNCounter {
increments: GCounter,
decrements: GCounter,
}
impl PNCounter {
pub fn increment(&mut self, replica: &str) {
self.increments.increment(replica);
}
pub fn decrement(&mut self, replica: &str) {
self.decrements.increment(replica);
}
/// 值可能是负数
pub fn value(&self) -> i64 {
self.increments.value() as i64 - self.decrements.value() as i64
}
pub fn merge(&mut self, other: &PNCounter) {
self.increments.merge(&other.increments);
self.decrements.merge(&other.decrements);
}
}关键点:减法不修改"增加"那一侧,而是往"减少"那一侧加。 这样整个结构始终是单调递增的(两边的计数都只增不减),max 合并依然成立。
CRDT 里所有"看起来像删除"的操作,本质都是"记录一个删除的事实",而不是移除数据。 这是它永远单调的原因。
这个特性也带来了 CRDT 最现实的缺点:状态只增不减。 后面讲 OR-Set 时会看到它导致的墓碑问题。
第三个 CRDT:LWW-Register(最后写入者胜)
有些数据不是计数,而是一个值(比如"用户昵称")。这种用 Last-Write-Wins Register:
#[derive(Debug, Clone, PartialEq)]
pub struct LwwRegister<T> {
value: T,
/// 写入时的逻辑时间戳
timestamp: u64,
/// 时间戳相同时用 replica id 打破平局
replica: String,
}
impl<T: Clone> LwwRegister<T> {
pub fn set(&mut self, value: T, timestamp: u64, replica: &str) {
// 本地写入也要比较,避免用旧时间戳覆盖新值
if self.should_update(timestamp, replica) {
self.value = value;
self.timestamp = timestamp;
self.replica = replica.to_string();
}
}
fn should_update(&self, timestamp: u64, replica: &str) -> bool {
timestamp > self.timestamp
|| (timestamp == self.timestamp && replica > self.replica.as_str())
}
pub fn merge(&mut self, other: &LwwRegister<T>) {
if self.should_update(other.timestamp, &other.replica) {
self.value = other.value.clone();
self.timestamp = other.timestamp;
self.replica = other.replica.clone();
}
}
}两个细节非常重要:
1. 时间戳相同时必须有确定性平局规则。 上面用了 "replica id 字典序较大者胜"。这个规则必须是确定性的——所有副本用同一个规则,才能保证合并结果一致。
如果用"随机选一个"或者"先到先得",就违反了交换律。
2. 时间戳不该用物理时钟。 物理时钟有偏移——A 的时钟快 5 秒,它的所有写入都会"赢",即使它实际上是后写的。
正确做法是用逻辑时钟(Lamport clock):
#[derive(Debug, Clone, Default)]
pub struct LamportClock {
counter: u64,
}
impl LamportClock {
/// 本地事件:计数 +1
pub fn tick(&mut self) -> u64 {
self.counter += 1;
self.counter
}
/// 收到远端事件:取较大值再 +1
pub fn observe(&mut self, remote: u64) -> u64 {
self.counter = self.counter.max(remote) + 1;
self.counter
}
}observe 里的 max(counter, remote) + 1 是 Lamport 时钟的核心:它保证"如果 A 的事件发生在 B 之后(且 A 知道 B),那 A 的时间戳一定更大"。
但要注意:Lamport 时钟只能保证因果序,不能保证全局序。 两个并发事件可能拿到相同时间戳——所以 LWW-Register 必须有那个平局规则。
LWW-Register 的"最后写入"是逻辑意义上的最后,不是物理时间上的最后。 用物理时钟是 CRDT 里最常见的错误,它会让"快时钟的副本"拥有不公平的优势。
第四个 CRDT:OR-Set(可增可删集合)
集合的 CRDT 是最有意思的。问题在于:"加入"和"删除"并发时该以谁为准?
副本 A: 加入元素 x
副本 B: 删除元素 x
合并后 x 应该存在吗?没有"正确"答案——这是个语义选择。
OR-Set(Observed-Remove Set)的选择是:只有"观察到的加入"才能被删除。
#[derive(Debug, Clone, Default)]
pub struct OrSet<T: Eq + std::hash::Hash + Clone> {
/// 元素 -> 它所有的"加入标记"
elements: HashMap<T, std::collections::HashSet<String>>,
/// 已删除的标记(墓碑)
tombstones: std::collections::HashSet<String>,
}每个"加入"操作生成一个全局唯一的标记(tag):
impl<T: Eq + std::hash::Hash + Clone> OrSet<T> {
pub fn add(&mut self, value: T, replica: &str) -> String {
// 标记 = replica + 本地序号,保证全局唯一
let tag = format!("{replica}:{}", Uuid::new_v4());
self.elements
.entry(value)
.or_default()
.insert(tag.clone());
tag
}
pub fn remove(&mut self, value: &T) {
// 删除:把这个元素当前所有的标记都记进墓碑
if let Some(tags) = self.elements.get(value) {
for tag in tags {
self.tombstones.insert(tag.clone());
}
}
self.elements.remove(value);
}
pub fn contains(&self, value: &T) -> bool {
self.elements
.get(value)
.map(|tags| tags.iter().any(|t| !self.tombstones.contains(t)))
.unwrap_or(false)
}
pub fn merge(&mut self, other: &OrSet<T>) {
// 1. 合并墓碑(并集)
self.tombstones.extend(other.tombstones.iter().cloned());
// 2. 合并元素标记
for (value, tags) in &other.elements {
let entry = self.elements.entry(value.clone()).or_default();
entry.extend(tags.iter().cloned());
}
// 3. 清掉已被墓碑覆盖的标记
self.elements.retain(|_, tags| {
tags.retain(|t| !self.tombstones.contains(t));
!tags.is_empty()
});
}
}为什么这样可以解决并发问题? 看那个场景:
初始状态(两边一致): x = {tag1}
副本 A: add x -> x = {tag1, tag2}
副本 B: remove x -> 墓碑 = {tag1}, x 被移除
合并:
墓碑 = {tag1}
x 的标记 = {tag1, tag2}
过滤掉被墓碑覆盖的 -> {tag2}
结果: x 存在!因为 A 的 add 产生了一个 B 没见过的 tag2,它不能被 B 的删除影响。
反过来如果 A 和 B 都是删除(都观察到 tag1),合并后墓碑包含 tag1,元素被清掉。
这就是 OR-Set 的语义:"并发加入胜出"。 它保证了"不会丢失任何一次并发的写入"。
如果需要相反语义(并发删除胜出),可以用 Remove-Wins Set。没有哪个更正确,只有哪个更符合业务。
墓碑膨胀:CRDT 最现实的代价
所有支持删除的 CRDT 都有这个问题:墓碑只能增加。
一个购物车:加入 100 个商品,删除 99 个
内存里还有 100 个墓碑,只为了知道"那 99 个被删过"长期运行的系统里,墓碑会超过有效数据。这是 CRDT 从"理论漂亮"到"工程可用"之间最大的鸿沟。
三种应对:
1. 压缩(compaction)。 观察到一个墓碑已经被所有副本看到,就可以安全删除:
impl<T: Eq + std::hash::Hash + Clone> OrSet<T> {
/// 当确认所有副本都收到了这个墓碑之后,可以清理
fn compact(&mut self, confirmed_by_all: &std::collections::HashSet<String>) {
self.tombstones.retain(|t| !confirmed_by_all.contains(t));
}
}但"所有副本都看到"这个条件本身就很难确认——需要某种全局的确认机制(比如版本向量 + 定期的心跳)。
2. 用"因果上下文"代替墓碑。 记录"当前状态包含哪些事件",用集合的差集表达删除:
不是"删除了 x",
而是"我的状态基于 {e1, e2, e3, e4},其中 e3 是删除"这是 δ-CRDT 和 因果稳定上下文的思路,能大幅减少冗余——但实现复杂度高一个量级。
3. 定期快照。 所有副本达成一致时,用当前状态替换全部历史。
这也是为什么很多"后 CRDT 时代"的系统(如 Figma、Linear 的协同编辑器)用的是 CRDT + 中心服务器的混合模式:服务器充当"稳定点",它可以决定什么时候可以压缩。
纯去中心的 CRDT 在理论上是完美的,但在工程上必须有一个"稳定点"来压缩历史。 这也是为什么实际系统里 CRDT 往往和中心服务共存。
状态型 CRDT vs 操作型 CRDT
前面都是状态型(state-based)CRDT:合并的是"完整状态"。
还有一种是操作型(operation-based)CRDT:传播的是"操作",而不是状态。
状态型:每次同步传整份状态(或者状态的 delta),接收方 merge
操作型:每次操作广播出去,接收方 apply| 维度 | 状态型 | 操作型 |
|---|---|---|
| 网络要求 | 允许丢包、乱序、重复 | 需要可靠广播(不丢、不重复) |
| 消息大小 | 状态大小(可能很大) | 单个操作(很小) |
| 实现难度 | 简单 | 需要因果顺序保证 |
操作型有个重要的变体叫 δ-CRDT:传"状态的增量"而不是完整状态。它兼顾了两者的优点——消息小、且不需要可靠广播。
/// δ-CRDT:只传变化的那个副本那一格
pub struct GCounterDelta {
replica: String,
count: u64,
}
impl GCounter {
/// 生成 delta:只有自己那一格变了
pub fn delta(&self, replica: &str) -> Option<GCounterDelta> {
self.counts.get(replica).map(|&count| GCounterDelta {
replica: replica.to_string(),
count,
})
}
pub fn apply_delta(&mut self, delta: &GCounterDelta) {
self.merge(&GCounter::from_delta(delta));
}
}数据中心间的复制通常用 δ-CRDT:把"批量操作"压缩成一个小的 delta 发送,而不是每秒钟传一次完整状态。
什么时候该用 CRDT
| 场景 | 适合 CRDT 吗 |
|---|---|
| 协同编辑(文本、白板) | ✅ 主战场 |
| 分布式计数器(点赞、阅读数) | ✅ |
| 离线优先的移动应用 | ✅ 网络不可靠是常态 |
| 购物车、待办列表 | ✅(注意墓碑) |
| 需要强一致的金融余额 | ❌ 必须用共识 |
| 需要唯一约束的场景 | ❌ CRDT 做不到全局唯一 |
最后两条要特别强调:
CRDT 不能保证"全局唯一"。 两个副本并发添加同一个用户名的处理是"两个都存在"——这不符合"用户名必须唯一"的要求。这类需求必须用共识(Raft)或者中心化的唯一性检查。
CRDT 也不能保证"读到最新值"。 它只保证"最终一致"——某个副本可能长时间读不到别人的更新(网络分区期间)。如果业务需要"写入后立刻能读到",CRDT 不满足。
结论
CRDT 的核心是把"协调"这件事从运行期移到了数据结构设计期:
用 max 合并实现交换律、结合律、幂等性;用"每副本一格"消除冲突;用 tag 和墓碑表达"并发的加入/删除";用逻辑时钟而不是物理时钟排序。
三个必须记住的权衡:
- 状态只增不减:删除是"记录事实",所以墓碑会膨胀,必须设计压缩策略
- 最终一致不等于强一致:分区期间可能读到旧值,且无法保证全局唯一
- 实际系统通常是混合的:CRDT 处理并发合并 + 中心节点负责压缩和唯一性约束
理解了这些,你再看 Figma、Linear、Notion 这类协同产品的技术选型,会发现它们很少是"纯 CRDT"或"纯 OT",而是在 CRDT 的可合并性之上,加了一层中心化的协调来补上唯一性和历史压缩。这往往是工程上最务实的答案。