引言：一个看似不可能的难题

2019年，Figma发布了一篇技术博客，详细介绍了他们的"多人游戏"技术——让数百人能够同时编辑同一个设计文件，而不会产生任何冲突。这项技术的核心，是一个名为CRDT（Conflict-free Replicated Data Types，无冲突复制数据类型）的数学概念。

但CRDT的故事远比Figma更久远。早在2011年，Marc Shapiro等人在INRIA发表了一篇开创性的论文，系统性地定义了这个概念。而在那之前，这个想法已经在分布式系统社区萌芽了多年。

CRDT解决的是分布式系统中最棘手的问题之一：如何在不需要中央协调的情况下，让多个节点对数据达成一致？

mindmap
  root((CRDT技术演进))
    理论基础
      半格理论
      单调数据结构
      最终一致性
    两种实现
      状态复制 CvRDT
      操作复制 CmRDT
    核心数据类型
      G-Counter
      PN-Counter
      LWW-Register
      OR-Set
    应用场景
      实时协作 Figma
      本地优先软件
      分布式数据库

第一部分：问题的本质——分布式系统的"不可能三角"

在深入CRDT之前，我们需要理解它试图解决的问题。

CAP定理的阴影

2000年，Eric Brewer提出了著名的CAP定理：在分布式系统中，一致性（Consistency）、可用性（Availability）和分区容错性（Partition tolerance）三者不可兼得。

当网络分区发生时，系统必须在一致性和可用性之间做出选择：

  • 选择一致性：拒绝写入，直到分区恢复（CP系统）
  • 选择可用性：接受写入，但可能产生冲突（AP系统）

传统的分布式数据库通常选择CP，通过Paxos或Raft等共识算法来保证一致性。但这带来了一个问题：当网络分区发生时，系统变得不可用。

另一种思路：接受最终一致性

如果我们接受"最终一致性"——即系统在某一时刻可能不一致，但最终会收敛到一致状态——是否可以既保证可用性，又避免数据冲突？

这就是CRDT的核心思想：设计一种数据结构，使得任何操作都能自动合并，不会产生冲突。

graph TD
    A[分布式系统困境] --> B{CAP定理}
    B --> C[CP: 一致性优先]
    B --> D[AP: 可用性优先]
    C --> E[分区时不可用]
    D --> F[可能产生冲突]
    
    F --> G{如何解决冲突?}
    G --> H[最后写入胜出 LWW]
    G --> I[向量时钟]
    G --> J[CRDT: 数学保证无冲突]
    
    J --> K[可用性 + 无冲突]

第二部分：CRDT的数学基础——为什么它能"无冲突"？

CRDT的核心依赖于一个数学概念：半格（Semilattice）。

半格：一种特殊的代数结构

半格是一个集合S，配备一个二元运算"⊔"（称为"join"或"合并"），满足两个性质：

  1. 幂等性：x ⊔ x = x
  2. 交换性：x ⊔ y = y ⊔ x
  3. 结合性：(x ⊔ y) ⊔ z = x ⊔ (y ⊔ z)

这三个性质意味着：无论以什么顺序合并元素，最终结果都相同。

单调数据结构

CRDT的另一个关键概念是单调性：状态只能增长，不能缩减。

想象一个计数器：如果我们只允许增加操作，那么无论多少个节点同时增加，最终合并时只需要把所有增量加起来即可。

graph LR
    subgraph 节点A
        A1[状态: 5]
        A2[+3]
        A3[状态: 8]
    end
    
    subgraph 节点B
        B1[状态: 5]
        B2[+2]
        B3[状态: 7]
    end
    
    A3 --> C[合并: max8,7 = 8]
    B3 --> C
    C --> D[最终状态: 8]

状态复制 vs 操作复制

CRDT有两种主要实现方式：

状态复制（CvRDT）

每个节点维护完整的状态，合并时交换整个状态：

merge(state_a, state_b) = state_a ⊔ state_b

优点：实现简单，自动处理重复消息 缺点：状态可能很大，网络开销高

操作复制（CmRDT）

每个节点只发送操作，而不是完整状态：

apply(state, operation) = state'

优点：网络开销小 缺点：需要保证消息恰好一次传递

flowchart TB
    subgraph CvRDT[状态复制]
        A1[节点A: 状态S_a] 
        B1[节点B: 状态S_b]
        A1 --> M1[交换完整状态]
        B1 --> M1
        M1 --> R1[merge S_a, S_b]
    end
    
    subgraph CmRDT[操作复制]
        A2[节点A: 操作op_a]
        B2[节点B: 操作op_b]
        A2 --> M2[广播操作]
        B2 --> M2
        M2 --> R2[apply op_a, op_b]
    end

第三部分：核心CRDT数据类型详解

1. G-Counter（增长计数器）

最简单的CRDT。每个节点维护一个计数器向量：

节点i增加: counter[i] += 1
查询值: sum(counter)
合并: counter = map(max, counter_a, counter_b)

示例：

假设有3个节点A、B、C：

操作 A的视图 B的视图 C的视图
初始 {A:0, B:0, C:0} {A:0, B:0, C:0} {A:0, B:0, C:0}
A增加3次 {A:3, B:0, C:0} - -
B增加2次 - {A:0, B:2, C:0} -
同步后 {A:3, B:2, C:0} {A:3, B:2, C:0} {A:3, B:2, C:0}
全局值 5 5 5

2. PN-Counter（正负计数器）

组合两个G-Counter：一个记录增加，一个记录减少：

值 = P_counter - N_counter

注意：PN-Counter不能用于需要精确语义的场景，如银行账户。因为减少操作只是"记录减少"，而不是"检查余额后减少"。

3. LWW-Register（最后写入胜出寄存器）

为每个值附加时间戳，合并时选择时间戳最大的：

merge((v1, t1), (v2, t2)) = 
  if t1 > t2 then (v1, t1)
  else (v2, t2)

问题：如果时间戳相同怎么办？通常使用节点ID作为tie-breaker。

sequenceDiagram
    participant N1 as 节点1
    participant N2 as 节点2
    participant N3 as 节点3
    
    Note over N1,N3: 初始值: "hello"
    N1->>N1: t=100, 写入 "world"
    N2->>N2: t=101, 写入 "crdt"
    N3->>N3: t=99, 写入 "test"
    
    Note over N1,N3: 同步后...
    N1->>N2: 交换状态
    N2->>N3: 交换状态
    
    Note over N1,N3: 最终值: "crdt" (t=101最大)

4. OR-Set（观察移除集合）

最实用的CRDT之一，支持添加和移除操作：

  • 添加：为每个元素附加唯一标记（UUID）
  • 移除：记录被移除的标记
  • 合并：添加所有未移除的元素

示例：

初始: {}
添加 "A": {A#uuid1}
添加 "A": {A#uuid1, A#uuid2}
移除 "A": 移除uuid1 → {A#uuid2}, 移除集合={uuid1}
合并: 添加所有未在移除集合中的元素

这种设计解决了"移除-添加"问题：如果一个节点移除了元素，另一个节点同时添加了同一个元素，合并后元素会保留（因为新添加有新的UUID）。

第四部分：CRDT vs 操作变换（OT）

在实时协作领域，CRDT不是唯一的解决方案。Google Docs使用的是另一种技术：操作变换（Operational Transformation, OT）。

OT的工作原理

OT的核心思想是：在应用操作之前，根据历史操作变换当前操作。

原始操作: 在位置3插入 "x"
历史操作: 在位置5插入 "y"
变换后操作: 在位置4插入 "x" (因为位置5的插入影响了位置3)

CRDT vs OT 对比

特性 CRDT OT
中央服务器 不需要 通常需要
数学保证 形式化证明 依赖实现
离线支持 天然支持 需要额外处理
空间开销 较高（存储元数据） 较低
实现复杂度 中等 高（变换函数复杂）
历史回溯 容易 困难 
graph LR
    subgraph OT[操作变换]
        O1[客户端A] --> O2[中央服务器]
        O3[客户端B] --> O2
        O2 --> O4[变换操作]
        O4 --> O1
        O4 --> O3
    end
    
    subgraph CRDT[无冲突复制]
        C1[节点A] --> C3[广播状态/操作]
        C2[节点B] --> C3
        C3 --> C4[自动合并]
        C4 --> C1
        C4 --> C2
    end

为什么Figma选择CRDT？

Figma在技术博客中解释了他们的选择：

  1. 离线支持：设计师需要能够在飞机上工作，CRDT天然支持离线编辑
  2. P2P架构：不需要中央服务器，降低延迟
  3. 数学保证：形式化的正确性证明

但Figma并没有直接使用现成的CRDT库，而是基于CRDT原理设计了专门的冲突解决方案——这是另一个值得深入的话题。

第五部分：CRDT的实际应用

1. Redis CRDB

Redis Enterprise支持CRDT，称为Active-Active数据库。多个地区的Redis实例可以独立写入，自动同步。

使用场景：

  • 跨地区购物车同步
  • 实时排行榜
  • 会话管理

2. Apple Notes

苹果的备忘录应用使用CRDT实现多人协作。当你离线编辑备忘录，然后在另一台设备上继续编辑，CRDT确保所有编辑最终合并。

3. Automerge

Automerge是一个JavaScript/TypeScript的CRDT库，由Ink & Switch实验室开发。它支持：

  • 文档同步
  • 离线编辑
  • 版本历史
// Automerge使用示例
import * as Automerge from 'automerge'

let doc1 = Automerge.from({ cards: [] })
let doc2 = Automerge.clone(doc1)

// 两个节点独立修改
doc1 = Automerge.change(doc1, d => {
  d.cards.push({ title: "Card A" })
})

doc2 = Automerge.change(doc2, d => {
  d.cards.push({ title: "Card B" })
})

// 合并 - 自动处理冲突
let merged = Automerge.merge(doc1, doc2)
// 结果: { cards: [{ title: "Card A" }, { title: "Card B" }] }

4. Yjs

Yjs是另一个流行的CRDT库，特别适合实时协作编辑：

  • 支持多种数据类型（Map, Array, Text）
  • 高效的二进制编码
  • 与多种编辑器集成（ProseMirror, Quill, Monaco）
graph TB
    subgraph 应用层
        A1[Figma]
        A2[Apple Notes]
        A3[Linear]
        A4[Notion]
    end
    
    subgraph CRDT库
        B1[Yjs]
        B2[Automerge]
        B3[Yrs Rust]
    end
    
    subgraph 存储层
        C1[Redis CRDB]
        C2[Riak]
        C3[Cassandra]
    end
    
    A1 --> B1
    A2 --> B2
    A3 --> B3
    A4 --> B1
    B1 --> C1
    B2 --> C2

第六部分：CRDT的局限性与挑战

尽管CRDT很强大，但它并非万能药。

1. 空间开销

CRDT需要存储大量元数据：

  • G-Counter需要为每个节点维护一个计数器
  • OR-Set需要为每个元素维护UUID和移除集合
  • 文本编辑CRDT需要为每个字符维护位置标记

解决方案：压缩、垃圾回收、定期快照

2. 语义限制

CRDT只能处理"可交换"的操作：

  • 银行转账不能用CRDT（需要事务）
  • 唯一约束检查不能用CRDT（需要中央协调）
  • 复杂业务逻辑不适合CRDT

3. 删除语义

删除操作是CRDT最棘手的部分：

  • 如果两个节点同时删除和添加同一个元素，结果是什么？
  • 如何实现"移动"操作？（实际上是用删除+添加模拟）

4. 学习曲线

CRDT的数学基础（半格、格理论）对大多数开发者来说是陌生的。理解为什么某种设计是正确的，需要深入理解数学原理。

graph TD
    A[CRDT局限性] --> B[空间开销大]
    A --> C[语义限制]
    A --> D[删除操作复杂]
    A --> E[学习曲线陡峭]
    
    B --> B1[压缩技术]
    B --> B2[垃圾回收]
    B --> B3[定期快照]
    
    C --> C1[不适合事务场景]
    C --> C2[不适合唯一约束]
    
    D --> D1[移除-添加冲突]
    D --> D2[移动操作困难]

第七部分：未来展望——本地优先软件

CRDT正在推动一场新的范式转变：本地优先软件（Local-First Software）。

什么是本地优先？

传统云应用假设：

  • 数据存储在云端
  • 网络是必需的
  • 用户信任云服务商

本地优先假设：

  • 数据存储在本地
  • 网络是可选的
  • 用户拥有自己的数据

CRDT如何使能本地优先？

CRDT让本地优先成为可能，因为它解决了离线编辑的核心问题：如何在离线时修改数据，然后在上线时自动合并。

典型案例：

  1. Linear：项目管理工具，完全离线可用
  2. Notion：正在逐步引入离线支持
  3. Obsidian：笔记应用，使用CRDT同步
timeline
    title CRDT技术发展历程
    2006 : Bayou系统 : 早期协同研究
    2011 : Shapiro论文 : CRDT形式化定义
    2014 : Riak集成 : 工业应用开始
    2016 : Yjs发布 : JavaScript生态
    2017 : Automerge发布 : 本地优先运动
    2019 : Figma博客 : 大规模生产验证
    2021 : Redis CRDB : 企业级支持
    2023 : Linear架构 : 全栈本地优先
    2025 : 广泛采用 : 成为主流选择

结语：从数学到工程

CRDT的故事是从抽象数学到工程实践的完美例证。半格理论看起来像是纯粹的数学游戏，但正是这个理论，让Figma能够支持数百人同时编辑设计文件，让Apple Notes能够在离线后无缝同步。

对于开发者来说，CRDT提供了一个重要的启示：有时候，最好的解决方案不是设计复杂的冲突解决逻辑，而是设计一个不存在冲突的系统。

正如分布式系统领域的先驱们所证明的：数学不仅是理论的，它也是实践的基石。

参考文献

  1. Shapiro, M., Preguiça, N., Baquero, C., & Zawirski, M. (2011). Conflict-free Replicated Data Types. SSS 2011.

  2. Kleppmann, M., & Beresford, A. R. (2017). A Conflict-Free Replicated JSON Datatype. IEEE TPDS.

  3. Figma Engineering Blog. (2019). How Figma’s Multiplayer Technology Works.

  4. van Hardenberg, P. (2021). Local-First Software: You Own Your Data, in Spite of the Cloud. ACM Queue.

  5. The Yjs Documentation. https://docs.yjs.dev/

  6. Automerge Documentation. https://automerge.org/