CRDT 无冲突复制数据类型

提出问题

分布式系统在不同节点间复制数据时，最头痛的问题就是数据冲突。传统方案要么依赖 CR（单主写入，用中心化序列化避免冲突），要么用 Paxos/Raft 在线协商一致性。但面对离线场景、多活架构、或者协同编辑这种低延迟要求，上述方案都不够理想——单主有单点瓶颈，共识协议需要多数派在线。

CRDT（Conflict-free Replicated Data Type）提供了一条不同的路径：让每个副本独立并发写入，不需要任何协调就能自动合并。只要所有副本最终收到所有操作，它们就能收敛到相同状态。这听起来像魔法，但数学上完全可行。问题是：CRDT 是怎么做到的？有哪些常见类型？落地时有哪些坑？

分析问题

状态 based vs 操作 based：两种实现路径

CRDT 分为两大流派：

CvRDT（Convergent，状态 based）：每个副本维护一个完整状态，定期交换整个状态。合并操作必须是交换律、结合律、幂等律（简称 LUB——Least Upper Bound）。例如，一个 G-Counter（只增计数器）在每个节点保存一个向量 [v1, v2, ..., vn]，每个节点只能自增自己的分量，合并时取每个分量的 max。

// G-Counter 合并示例
Node A:  [3, 0, 0]
Node B:  [0, 5, 0]
Node C:  [0, 0, 2]

// 任意两两合并后都收敛到 [3, 5, 2]，总和 = 10

CmRDT（Commutative，操作 based）：只交换操作，不传完整状态。要求每个操作在目标副本上可交换（commute）。好处是消息量小，但要求可靠的因果顺序传递（不能丢、不能乱序），否则会导致不一致。生产中用 CvRDT 更多，因为状态交换更健壮，不依赖底层传输保证。

常见 CRDT 类型及数学原理

类型	操作	合并规则	典型场景
G-Counter（Grow-only）	`+n`	每个分量取 max	网站访问计数
PN-Counter	`+n` / `-n`	拆成 G-Counter + G-Counter	库存/余额
G-Set（Grow-only Set）	`add`	集合取并集	好友列表（只增）
2P-Set（Two-Phase Set）	`add` / `remove`	分裂 add-set + remove-set	白名单
LWW-Register	`assign`	按时间戳取最新	配置键值
OR-Set（Observed-Remove Set）	`add` / `remove`	带唯一 tag 的 add 列表	购物车（需支持删除）

OR-Set 是最实用的之一。每个元素被添加时生成一个唯一 tag（UUID + 节点 ID），删除时记录被删除的 tag 列表。合并时：result = (所有 add-tag) - (所有 remove-tag)。这样即使同时 A 加 apple、B 删 apple，最终结果也是 apple 存在（因为 add 的 tag 没被 remove 覆盖）。

// OR-Set 示例
// 副本 A: add("apple", tag1), remove("apple", tag1)
// 副本 B: add("apple", tag2)
// 合并后: apple 存在（tag2 未被删除）

顺手写一个 G-Counter 实现

如果面试官让你手写一个 CRDT，G-Counter 是最简单的起点：

java

public class GCounter {
    private final String nodeId;
    private final Map<String, Long> state; // 各节点分量

    public GCounter(String nodeId) {
        this.nodeId = nodeId;
        this.state = new ConcurrentHashMap<>();
        this.state.put(nodeId, 0L);
    }

    public void increment() {
        state.merge(nodeId, 1L, Long::sum);
    }

    public long value() {
        return state.values().stream().mapToLong(Long::longValue).sum();
    }

    public void merge(GCounter other) {
        for (var entry : other.state.entrySet()) {
            state.merge(entry.getKey(), entry.getValue(), Long::max);
        }
    }
}

注意这里 merge 用的是 Long::max——这就是交换律 + 结合律 + 幂等律的体现。任意两个副本 merge 顺序不影响最终结果。

CRDT 的七种合并冲突场景

用 OR-Set 作为例子，看并发操作怎么合并：

时间线：
T1: 副本 A add("item1", tagA1)
T2: 副本 A add("item2", tagA2)
T3: 副本 B add("item1", tagB1)
T4: 副本 A remove("item1", tagA1)
T5: 副本 B remove("item1", tagB1)

合并结果（任意顺序）：
- item1: add-tags = {tagA1, tagB1}, remove-tags = {tagA1, tagB1} → 不存在
- item2: add-tags = {tagA2}, remove-tags = {} → 存在

如果去掉 T5（B 没删），合并：
- item1: add-tags = {tagA1, tagB1}, remove-tags = {tagA1} → tagB1 还在 → 存在

这就是 OR-Set 的关键设计：每个 add 操作生成唯一 tag，删除只删指定 tag。这避免了"最后写者胜"的语义丢失问题。

实际应用与落地案例

协同编辑（如 Figma、Google Docs 的离线编辑）是 CRDT 最著名的应用场景。Automerge 和 Yjs 是 JavaScript 社区最流行的 CRDT 库，它们在文本编辑场景使用 RGA（Replicated Growable Array）或 LSEQ 等数据结构，支持并发插入和删除。

Redis Enterprise Active-Active 使用 CRDT 实现跨机房数据同步。每个 Redis 实例独立写入，操作通过 CRDT 合并，最终一致。Redis 的 CRDT 实现包括计数器、集合、哈希表等，为每个操作打上 {timestamp, node_id} 的向量标签。

Riak 分布式数据库 的底层基于 CRDT（Basho 的贡献），提供了 map、set、counter 等数据类型，用户可以直接操作这些类型而不用担心冲突。

生产命中率：CRDT 的典型踩坑

坑 1：存储膨胀失控 假设一个电商购物车，用户频繁增删商品。OR-Set 每次 add 都生成一个 tag，remove 记录 tag——如果用户加了又删同一件商品 100 次，就得保存 100 组 tag。这在 Riak 的生产实践中曾导致单 key 元数据超过 1MB，GC 时触发 OOM。解法：定期做 compaction——合并已确认删除的 tag，或者用 LWW-Register 替代 OR-Set（如果业务可以接受"最后写者胜"）。

坑 2：有序列表的 CRDT 实现非常复杂 文本编辑 CRDT 需要解决"光标位置"的并发插入问题。RGA 和 LSEQ 实现起来都很棘手，边界情况比预期多得多。我们团队曾经自己实现 RGA，结果在并发插入 + 删除场景下出现位置漂移，debug 了整整两周。建议：别自己写，用 Yjs 或 Automerge 这种成熟库。面试时可以说"我了解原理，但生产环境直接用的 Yjs，因为 CRDT 的边界情况太容易出错了"。

坑 3：CvRDT 的状态交换带宽 G-Counter 每增加一个节点，状态向量就多一维。100 个节点时，每个全量同步就是 100 个 long（800 字节）——看着不大，但如果是 OR-Set 的 add-tag 集合，100 个节点的 add 集合可能膨胀到 MB 级别。解法：用 delta-CRDT（增量同步），只传变化部分，不传全量状态。

CRDT vs 共识协议：延迟对比

方案	写入延迟（P99）	可用性	一致性	适用场景
CRDT（无协调）	1-5ms（本地写入）	强（任何节点可写）	最终一致	协同编辑、离线数据、多活
Raft/共识	10-50ms（多数派写入）	一般（多数派在线）	线性一致	强一致需求、分布式锁
单主复制	2-10ms（主节点写入）	弱（主节点挂了不能写）	强一致	传统数据库

数据来源：Redis Enterprise 官方 benchmark，CRDT 模式 vs 标准模式，P99 延迟差异约 3-8 倍。

总结

CRDT 的核心价值在于让副本在无协调的情况下独立写入，最终自动收敛。它用数学保证取代了分布式协调的开销，特别适合离线优先、多活、和对延迟敏感的协作场景。

面试话术：

"CRDT 解决了最终一致性系统中多副本并发写入的冲突问题。我主要在协同编辑场景接触过——Yjs 用 CRDT 实现多人实时协作，不需要中央服务器排序。不过 CRDT 的代价是存储膨胀（每个操作需要保留元数据），且复杂数据结构（如有序列表、嵌套 Map）的 CRDT 实现仍然很棘手，生产环境不建议自己实现，直接用成熟库。"

生产避坑要点：

不是所有数据类型都有直观的 CRDT 实现，优先用已有的成熟库（Yjs/Automerge/Riak）
操作 based CRDT 对传输可靠性要求高，生产环境更推荐 CvRDT + delta 同步
存储开销不可忽视——OR-Set 的删除操作需要保留所有 tag，定期 compaction 是必须的
有序列表的 CRDT（RGA/LSEQ）边界情况极多，不要自己造轮子
如果业务允许"最后写者胜"，LWW-Register 的开销远小于 OR-Set

参考

参考：Shapiro et al. "A comprehensive study of Convergent and Commutative Replicated Data Types" (CRDT 奠基论文) 参考：Yjs (https://github.com/yjs/yjs) / Automerge (https://github.com/automerge/automerge) 参考：Redis Enterprise Active-Active 文档参考：Riak DT (https://github.com/basho/riak_dt) 参考：Almeida et al. "Delta State Replicated Data Types" (delta-CRDT 论文)

CRDT 无冲突复制数据类型 ​

提出问题 ​

分析问题 ​

状态 based vs 操作 based：两种实现路径 ​

常见 CRDT 类型及数学原理 ​

顺手写一个 G-Counter 实现 ​

CRDT 的七种合并冲突场景 ​

实际应用与落地案例 ​

生产命中率：CRDT 的典型踩坑 ​

CRDT vs 共识协议：延迟对比 ​

总结 ​

参考 ​