返回文章列表

用 Rust 从零实现 CRDT:不需要协商的最终一致

555 字·4 分钟阅读
Rust从零造轮子分布式系统

三个副本同时把计数器加一。如果没有协调,最终值该是多少?

正常思路是"选一个赢家"或者"加锁"。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 和墓碑表达"并发的加入/删除";用逻辑时钟而不是物理时钟排序。

三个必须记住的权衡:

  1. 状态只增不减:删除是"记录事实",所以墓碑会膨胀,必须设计压缩策略
  2. 最终一致不等于强一致:分区期间可能读到旧值,且无法保证全局唯一
  3. 实际系统通常是混合的:CRDT 处理并发合并 + 中心节点负责压缩和唯一性约束

理解了这些,你再看 Figma、Linear、Notion 这类协同产品的技术选型,会发现它们很少是"纯 CRDT"或"纯 OT",而是在 CRDT 的可合并性之上,加了一层中心化的协调来补上唯一性和历史压缩。这往往是工程上最务实的答案。