CRDT 同步机制与实践

发表于 分类于 ， 阅读次数： Waline： 本文字数： 7.4k 阅读时长 ≈ 7 分钟

1. 什么是 CRDT

1.1 核心定义

CRDT（Conflict-free Replicated Data Type，无冲突复制数据类型）是一种数据结构，允许多个副本独立、并发修改，无需中央协调即可自动合并到一致状态。

它围绕一个核心问题展开：多副本之间如何高效、正确地传播和合并变更？

1.2 直觉类比

你和小红、小明各有一盒相同的积木：

  • 你放了一块 🔴红色积木
  • 小红放了一块 🔵蓝色积木
  • 小明放了一块 🟢绿色积木

合并规则很简单：只要有人放了，就算有。最终每人盒子里都是 🔴🔵🟢 三块积木。

这就是 CRDT 的核心——规则预先定义好，各节点自行合并即可收敛，不需要中央裁判。

1.3 数学基础

CRDT 的理论根基是半格（Semilattice）。merge 操作本质上是求最小上界（LUB），只要满足三条性质就能保证收敛：

%%{init: {'theme': 'base', 'themeVariables': { 'primaryColor': '#3B82F6', 'primaryTextColor': '#1E3A5F', 'primaryBorderColor': '#2563EB', 'lineColor': '#60A5FA', 'secondaryColor': '#10B981', 'tertiaryColor': '#F59E0B'}}}%%
flowchart TD
    SEMI(["半格（Semilattice）"]) --> P1["交换律: merge(A,B) = merge(B,A)"]
    SEMI --> P2["结合律: merge(A, merge(B,C)) = merge(merge(A,B), C)"]
    SEMI --> P3["幂等性: merge(A,A) = A"]
    P1 --> RESULT["合并顺序无关 → 最终一致"]
    P2 --> RESULT
    P3 --> RESULT

    classDef primary fill:#3B82F6,stroke:#2563EB,color:#fff
    classDef success fill:#10B981,stroke:#059669,color:#fff
    classDef info fill:#0EA5E9,stroke:#0284C7,color:#fff

    class SEMI primary
    class P1,P2,P3 info
    class RESULT success

只要数据结构能定义满足这三条性质的 join 操作，它就是 CRDT。换言之，你可以 “ 发明 “ 自己的 CRDT——只需证明这三条性质成立。

1.4 同步全景

一次典型的 CRDT 同步分为三个阶段：并发修改 → 同步传播 → 合并收敛。

%%{init: {'theme': 'base', 'themeVariables': {'actorBkg': '#3B82F6', 'actorTextColor': '#1E3A5F', 'actorBorder': '#2563EB', 'signalColor': '#60A5FA', 'activationBkgColor': '#DBEAFE', 'activationBorderColor': '#3B82F6'}}}%%
sequenceDiagram
autonumber
participant A as "节点 A"
participant B as "节点 B"
participant C as "节点 C"

Note over A,C: "Phase 1: 并发修改（各自离线）"
A->>A: "insert('Hello')"
B->>B: "insert('World')"
C->>C: "delete(pos=2)"

Note over A,C: "Phase 2: 同步传播"
A->>B: "Op: insert('Hello')"
A->>C: "Op: insert('Hello')"
B->>A: "Op: insert('World')"
B->>C: "Op: insert('World')"
C->>A: "Op: delete(pos=2)"
C->>B: "Op: delete(pos=2)"

Note over A,C: "Phase 3: 合并收敛"
A->>A: "merge() → 一致状态"
B->>B: "merge() → 一致状态"
C->>C: "merge() → 一致状态"

每个操作附加元数据（时钟 / ID），合并时靠数学性质保证收敛。工程落地还需处理 GC、同步协议、存储膨胀等问题。

1.5 核心术语

术语一句话解释类比
Convergence（收敛）所有副本最终变成同一个值不同路走到同一目的地
Causal Order（因果序）操作之间的先后依赖关系回复邮件前必须先收到邮件
Vector Clock（向量时钟）每个节点维护的多维计数器每人一个计步器，互相对表
Op-based CRDT传播 “ 操作 “ 而非 “ 状态 “传菜谱，不传整盘菜
State-based CRDT传播 “ 完整状态 “ 并合并传整盘菜，挑最好的合一盘

概念建立之后，看看工程中怎么选型、怎么避坑。

2. 类型选择与实践

2.1 同步协议设计

  • 全量同步（State-based）实现简单但带宽开销大
  • 增量同步（Op-based）高效但需保证因果有序和恰好一次投递
  • CRDT 维护的因果元数据（墓碑、向量时钟）会持续膨胀，必须设计 GC 策略：定期快照 + 截断旧操作日志
  • Yjs 的做法：所有节点确认收到后，压缩合并操作

2.2 Op-based 与 State-based 对比

选定 CRDT 类型后，还需要决定传播机制。两种变体的工作流程差异显著：

维度Op-based（CmRDT）State-based（CvRDT）
传播内容操作本身（如 add(x)）完整状态快照
网络要求因果有序、恰好一次仅需最终可达
带宽消耗低（只传增量）高（传全量）
实现复杂度高（操作日志 + 因果追踪）低（实现 merge 函数即可）
适用场景实时协作、低延迟弱网络、简单数据

生产环境的推荐策略：增量为主 + 周期全量校验。

2.3 CRDT 与 OT 对比

维度CRDTOT（Operational Transformation）
中心化不需要中央服务器通常需要中央服务器排序
复杂度合并函数数学性质保证正确变换函数组合数爆炸
离线支持天然支持需额外处理
代表产品Figma、Yjs、AutomergeGoogle Docs

2.4 CRDT 与 Git 合并对比

Git 没有使用 CRDT，采用三路合并（Three-Way Merge）策略：

%%{init: {'theme': 'base', 'themeVariables': { 'primaryColor': '#3B82F6', 'primaryTextColor': '#1E3A5F', 'primaryBorderColor': '#2563EB', 'lineColor': '#60A5FA', 'secondaryColor': '#10B981', 'tertiaryColor': '#F59E0B'}}}%%
flowchart TD
B["Base（共同祖先）"] --> O["Ours（你的分支）"]
B --> T["Theirs（别人的分支）"]
O --> M["Merged（合并结果）"]
T --> M
M --> D{"同一行都改了？"}
D -->|"否"| AUTO["自动合并 ✅"]
D -->|"是"| CONFLICT["冲突！人工解决 ⚠️"]

classDef primary fill:#3B82F6,stroke:#2563EB,color:#fff
classDef success fill:#10B981,stroke:#059669,color:#fff
classDef warning fill:#F59E0B,stroke:#D97706,color:#fff
classDef danger fill:#EF4444,stroke:#DC2626,color:#fff

class B primary
class O,T success
class M warning
class AUTO success
class CONFLICT danger
class D warning

合并规则（逐行对比）：

  1. Ours 改了、Theirs 没改 → 取 Ours
  2. Theirs 改了、Ours 没改 → 取 Theirs
  3. 都没改 → 取 Base
  4. 都改了同一行 → 冲突，需要人工解决
维度GitCRDT
冲突处理冲突时停下来等人手动解决自动合并，不产生冲突
中心化需要线性化的 commit 历史不需要全局排序
合并策略文本行级 diff + 三路对比基于数学性质（交换/结合/幂等）
并发语义谁的改动保留需要人判断预定义规则，机器自动判断

Git 是 “ 能自动合并就合并，不能就喊人 “；CRDT 是 “ 设计上就不存在喊人的情况 “。

3. 深入理解

3.1 语义冲突：能合并，但结果可能不对

CRDT 保证数据层面永远不卡住，但这不等于合并结果符合用户意图。冲突有两个层次：

层次含义CRDT 能解决吗？
数据冲突两个副本状态不一致，需要收敛到同一个值✅ 自动解决
语义冲突合并后的结果不符合用户意图❌ CRDT 不理解意图

举例说明：用 Yjs 编辑，原文是 “ 会议时间：周三下午 3 点 “。

%%{init: {'theme': 'base', 'themeVariables': {'actorBkg': '#3B82F6', 'actorTextColor': '#1E3A5F', 'actorBorder': '#2563EB', 'signalColor': '#60A5FA', 'activationBkgColor': '#DBEAFE', 'activationBorderColor': '#3B82F6'}}}%%
sequenceDiagram
participant A as "用户 A"
participant DOC as "文档"
participant B as "用户 B"

Note over A,B: "原文: 会议时间：周三下午 3 点"
A->>DOC: "改为: 周四上午 10 点"
B->>DOC: "改为: 周五下午 2 点"
DOC->>DOC: "CRDT 自动合并"
Note over A,B: "结果: 周四上午 10 点周五下午 2 点"
Note over A,B: "数据收敛 ✅  语义错误 ❌"

数据收敛了（所有节点看到一样的值），但语义是错的（会议到底是周四还是周五？）。

CRDT 保证数据层不卡住，语义冲突仍然需要人来判断。对比 Git——Git 在数据层就停下来了（conflict marker），而 CRDT 让你先继续工作，回头再处理语义问题。

3.2 三大常见误区

1
2
3
❌ 误区一：以为 CRDT "什么冲突都能解决"
💥 后果：语义冲突（如两人同时改同一行文字为不同内容）只会机械合并，结果可能不符预期
✅ 正解：CRDT 解决"数据收敛"，语义冲突仍需 UI 层提示用户选择
1
2
3
❌ 误区二：忽略墓碑（Tombstone）清理
💥 后果：删除的元素虽不可见，但墓碑标记永远留在内存里，跑几周后内存膨胀数倍
✅ 正解：实现定期 GC——所有节点确认已同步后，安全清除墓碑
1
2
3
❌ 误区三：Op-based CRDT 使用不可靠传输，不保证因果顺序
💥 后果：操作乱序到达，A 节点看到 v2，B 节点停留在 v0
✅ 正解：Op-based 必须搭配因果有序投递（Causal Delivery），用向量时钟检测并重传缺失操作

3.3 Figma 的工程妥协

Figma 并未使用 “ 纯 CRDT”。其 CTO Evan Wallace 公开表示他们用的是 CRDT 启发的方案——服务器仍然参与排序。

原因在于：纯 P2P CRDT 在大型文档（百万级操作）上性能不够。Figma 做了大量工程妥协：服务器做最终排序，客户端做乐观更新，操作粒度为 “ 属性级 “（改颜色、改位置各自独立）。

理论和工程之间总有 gap。

3.4 真实案例

公司/项目用法
FigmaCRDT 思想做画布多人编辑，服务器辅助排序 + 客户端乐观更新
Yjs开源 CRDT 框架，YATA 算法处理文本协作，被 Notion、AFFiNE 等产品集成
Riak用 State-based CRDT（OR-Set、PN-Counter）做分布式 KV 存储的自动冲突解决

4. 动手验证

4.1 理解检验

  1. Op-based CRDT 为什么需要 “ 因果有序投递 “，而 State-based 不需要？

    • Op-based 传播的是 “ 操作 “，操作之间有依赖关系。乱序到达会导致状态不一致。
    • State-based 传播的是 “ 完整状态快照 “，merge 函数的幂等性保证重复/乱序合并不影响结果。

  2. 开发一款离线笔记 App（类似 Obsidian），多设备编辑同一篇笔记，选 Op-based 还是 State-based？

    • 推荐 State-based 或混合方案。离线优先场景网络不可靠，Op-based 要求因果有序 + 恰好一次投递，实现成本极高。
    • 纯 State-based 处理文本粒度较粗，可用 Yjs（YATA 算法）这类混合方案——本地用 Op-based 记录操作，同步时打包为状态增量。

  3. 为什么删除数据需要 “ 墓碑 “（Tombstone）而不是直接删掉？

    • 没有墓碑，已删除的数据会被其他副本的同步操作 “ 复活 “（resurrection）。
    • 墓碑会持续占用内存，必须配合 GC 策略定期清理。

4.2 微型实践：G-Counter

用 Python 实现一个 G-Counter（只增计数器）CRDT：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class GCounter:
    def __init__(self, node_id):
        self.id = node_id
        self.counts = {}  # {node_id: count}

    def increment(self):
        self.counts[self.id] = self.counts.get(self.id, 0) + 1

    def value(self):
        return sum(self.counts.values())

    def merge(self, other):
        # 取每个节点的最大值——满足交换律、结合律、幂等性
        for k, v in other.counts.items():
            self.counts[k] = max(self.counts.get(k, 0), v)

验证收敛性：

1
2
3
4
5
6
7
8
a = GCounter("A")
b = GCounter("B")
a.increment()  # A: {"A":1}
a.increment()  # A: {"A":2}
b.increment()  # B: {"B":1}
a.merge(b)     # A: {"A":2, "B":1}
b.merge(a)     # B: {"A":2, "B":1}
print(a.value() == b.value() == 3)  # True ← 收敛！

完成标准：a.value() 和 b.value() 合并后都等于 3，证明两个副本收敛。