分布式协同编辑——多人同时改一份文档、一张白板、一个表单——最难的不是网络延迟，而是"两个人同时改了同一个字段，谁的算对？"。传统做法是加锁：谁先抢到谁改，其他人等着。但锁在跨区域、离线场景下代价极高，甚至不可用。CRDT（Conflict-free Replicated Data Type）给出了另一条路：数据结构本身保证无论各节点以什么顺序收到更新，最终状态一定一致，不需要锁，不需要协商。
前 Recurse Center 工程师 Jake Lazaroff 最近写了一篇交互式教程，用图灵机做比喻来拆解 CRDT 的运作机制。这个比喻很妙——图灵机的"状态 + 规则"恰好对应 CRDT 的"内部状态 + 合并规则"。下面沿着这条线，把 CRDT 的核心逻辑拆开，再落到可跑的代码上。
图灵机视角：状态机 + 确定性规则
图灵机的核心很简单：一条纸带、一个读写头、一组规则。每一步，读写头根据当前状态和纸带符号，决定写什么、移到哪、切换到哪个状态。关键性质：同样的输入 + 同样的状态，永远产生同样的输出和同样的新状态。
CRDT 也是一台状态机，只不过"纸带"换成了"来自其他节点的消息流"。每个节点维护自己的内部状态，收到一条消息就按确定性规则更新状态。因为规则是确定性的，不管消息以什么顺序到达，只要最终都到达了，所有节点的终态一定相同。
这就是 CRDT 的全部承诺：不靠中央协调，不靠全局时钟，只靠数据结构自身的合并规则保证收敛。
两类 CRDT：CmRDT 与 CvRDT
CRDT 有两种主要流派，理解它们的区别对选型很关键。
CmRDT（Operation-based，基于操作）——节点之间传递的是"操作"本身（比如 increment()、add("x")）。要求：底层消息通道必须保证因果有序（causal delivery），即每个操作到达所有节点时，其依赖的前序操作已经到达。操作本身必须是交换律的：先收到 A 再收到 B，和先收到 B 再收到 A，结果一样。
CvRDT（State-based，基于状态）——节点之间传递的是"整个状态"。收到远端状态后，本地用 merge(local_state, remote_state) 合并。合并函数必须满足三个数学性质：
- 交换律：
merge(A, B) = merge(B, A) - 结合律：
merge(A, merge(B, C)) = merge(merge(A, B), C) - 幂等性：
merge(A, A) = A
幂等性尤其重要：网络重传、重复投递都不会破坏状态。CvRDT 对消息通道的要求更低——只需要最终送达（reliable eventual delivery），不需要因果有序。
实际工程中，CvRDT 更常见，因为"传状态 + 幂等合并"对网络条件的容忍度更高，实现也更直观。下面用代码来演示。
从一个计数器开始：G-Counter
最简单的 CvRDT 是 G-Counter（只增不减的计数器）。直觉上"全局计数器"好像直接加就行，但两个节点同时加 1，再互相同步——如果只存一个总数，合并时就不知道对方加了多少。
解法：每个节点只记自己加了多少。状态是一个向量 {node_id: count}，合并就是逐节点取最大值。
# g_counter.py — 可直接运行
from copy import deepcopy
class GCounter:
"""只增不减的 CvRDT 计数器"""
def __init__(self, node_id: str):
self.node_id = node_id
self.state: dict[str, int] = {} # {node_id: 本节点累计增量}
def increment(self, amount: int = 1):
"""只有本节点能改自己的计数"""
self.state[self.node_id] = self.state.get(self.node_id, 0) + amount
def value(self) -> int:
"""全局值 = 所有节点计数之和"""
return sum(self.state.values())
def merge(self, other: "GCounter") -> "GCounter":
"""合并：每个节点取 max，返回新对象"""
result = GCounter(self.node_id)
all_keys = set(self.state) | set(other.state)
for k in all_keys:
result.state[k] = max(self.state.get(k, 0), other.state.get(k, 0))
return result
def __repr__(self):
return f"GCounter(node={self.node_id}, state={self.state}, value={self.value()})"
# ---- 模拟两个节点各自操作后合并 ----
a = GCounter("node-A")
b = GCounter("node-B")
a.increment(3) # A 加了 3
b.increment(5) # B 加了 5
print("合并前:")
print(f" A: {a}") # value=3
print(f" B: {b}") # value=5
# A 收到 B 的状态，合并
a_merged = a.merge(b)
# B 收到 A 的状态，合并
b_merged = b.merge(a)
print("合并后:")
print(f" A: {a_merged}") # value=8
print(f" B: {b_merged}") # value=8
# 重复合并不会改变结果（幂等性）
print(f" A 再合并一次 B: {a_merged.merge(b)}") # value 仍然是 8
运行结果：
合并前:
A: GCounter(node=node-A, state={'node-A': 3}, value=3)
B: GCounter(node=node-B, state={'node-B': 5}, value=5)
合并后:
A: GCounter(node=node-A, state={'node-A': 3, 'node-B': 5}, value=8)
B: GCounter(node=node-B, state={'node-A': 3, 'node-B': 5}, value=8)
A 再合并一次 B: GCounter(node=node-A, state={'node-A': 3, 'node-B': 5}, value=8)
注意三个性质都成立：merge(A, B) 和 merge(B, A) 结果相同（交换律）；连续合并三次不影响结果（幂等性）；无论谁先收到谁的状态，终态一致。
能增能减：PN-Counter
G-Counter 只能加。要支持减法，做法是两个 G-Counter 拼在一起：一个记增量 P，一个记减量 N，全局值 = P.value() - N.value()。
# pn_counter.py — 在 GCounter 之上构建
# （GCounter 类同上，此处省略重复定义，实际运行时需引入）
class PNCounter:
"""可增可减的 CvRDT 计数器"""
def __init__(self, node_id: str):
self.node_id = node_id
self.p = GCounter(node_id) # 正数部分
self.n = GCounter(node_id) # 负数部分
def increment(self, amount: int = 1):
self.p.increment(amount)
def decrement(self, amount: int = 1):
self.n.increment(amount)
def value(self) -> int:
return self.p.value() - self.n.value()
def merge(self, other: "PNCounter") -> "PNCounter":
result = PNCounter(self.node_id)
result.p = self.p.merge(other.p)
result.n = self.n.merge(other.n)
return result
def __repr__(self):
return f"PNCounter(node={self.node_id}, value={self.value()}, p={self.p.state}, n={self.n.state})"
# ---- 模拟 ----
a = PNCounter("node-A")
b = PNCounter("node-B")
a.increment(10)
a.decrement(3) # A: 10 - 3 = 7
b.increment(4)
b.decrement(1) # B: 4 - 1 = 3
merged = a.merge(b)
print(f"合并后全局值: {merged.value()}") # (10+4) - (3+1) = 10
这种"组合更基础 CRDT 得到新 CRDT"的模式在工程中很常见——不用重新证明数学性质，只要组件各自满足，组合结果就满足。
协同文本编辑的挑战
计数器是入门好例子，但真实协同应用的核心难题是文本/列表的并发插入。两个人在同一行不同位置插入字符，合并时怎么保证顺序和位置都不错乱？
CRDT 的解法是给每个插入的字符分配一个全局唯一、有序的标识符（不是简单的整数索引，因为整数索引在并发插入时会冲突）。常见方案：
- LWW-Element-Set（Last-Writer-Wins）：每个元素带时间戳，后写覆盖前写。简单但会丢数据。
- RGA（Replicated Growable Array）：每个字符带
(timestamp, node_id, seq)组合标识，按标识排序，并发插入通过"插在左邻居右边"的规则保持一致。 - Yjs / Automerge：生产级库，内部用优化后的 CRDT 序列结构，支持文本、对象、地图等。
下面用最简化的 LWW-Register 演示"最后写入胜出"的逻辑：
# lww_register.py — 最简 CvRDT：一个值 + 时间戳，后写覆盖前写
import time
class LWWRegister:
"""Last-Writer-Wins Register — 最后写入胜出"""
def __init__(self, node_id: str):
self.node_id = node_id
self.value = None
self.timestamp = 0.0
def set(self, value):
self.value = value
# 实际工程中用混合时钟（物理时间 + node_id 排序），
# 这里用单调递增模拟
self.timestamp = time.time()
def merge(self, other: "LWWRegister") -> "LWWRegister":
result = LWWRegister(self.node_id)
if self.timestamp >= other.timestamp:
result.value = self.value
result.timestamp = self.timestamp
else:
result.value = other.value
result.timestamp = other.timestamp
return result
def __repr__(self):
return f"LWWRegister(value={self.value}, ts={self.timestamp:.4f})"
# ---- 模拟并发写后合并 ----
reg_a = LWWRegister("A")
reg_b = LWWRegister("B")
reg_a.set("hello")
time.sleep(0.01) # 保证 B 的时间戳更大
reg_b.set("world")
merged = reg_a.merge(reg_b)
print(f"合并结果: {merged}") # 值为 "world"（时间戳更大者胜出）
LWW-Register 简单粗暴，适合"配置项""用户名"等不怕丢旧值的场景。文本编辑不能用它——你不想别人刚打的字被你的时间戳覆盖掉。文本场景需要 RGA 或 Yjs 的序列 CRDT，这些库已经把标识符分配、并发插入排序、垃圾回收等细节处理好，直接用就好。
选型与实践清单
| 场景 | 推荐 CRDT | 理由 |
|---|---|---|
| 全局计数器（只增） | G-Counter | 最简，向量取 max |
| 全局计数器（增减） | PN-Counter | 两个 G-Counter 组合 |
| 配置/状态寄存器 | LWW-Register | 覆盖语义可接受 |
| 协同文本编辑 | Yjs / Automerge | 生产级序列 CRDT |
| 协同 JSON 对象 | Automerge | 嵌套对象 + 列表都支持 |
| 协同白板/画布 | Yjs + Y.XmlFragment | 位置用 LWW，元素用集合 |
接入建议：
- 不要从零实现序列 CRDT——标识符分配和垃圾回收的细节极多，直接用 Yjs（JavaScript）或 Automerge（Python 绑定可用）。计数器、寄存器这类简单结构可以自己写，几十行就够。
- 网络层选 CvRDT——传状态 + 幂等合并对丢包、重传、离线重连的容忍度远高于 CmRDT 的因果有序要求。
- 状态膨胀问题——CvRDT 每次合并传全量状态，随操作累积状态会越来越大。工程解法：定期做"压缩"（garbage collect 已合并的元数据），或用 delta-state CRDT 只传增量。
- 时钟——LWW 依赖时间戳，跨节点时钟偏移会导致旧值覆盖新值。混合逻辑时钟（Hybrid Logical Clock, HLC）是更安全的选择：物理时间 + 逻辑计数器 + node_id，保证偏移在容忍范围内时排序仍然正确。
- 验证合并性质——写完
merge函数，用单元测试验证交换律、结合律、幂等性。随机顺序合并是很好的测试手段：生成 N 个随机状态，以随机顺序两两合并，检查终态一致。
CRDT 不是银弹——它牺牲了即时一致性（各节点短暂不同步），换来的是离线可用、无锁、无中央协调。如果你的场景要求"所有人同一瞬间看到同一画面"，CRDT 不合适；如果"几秒后收敛一致"可以接受，CRDT 是目前最干净的工程解法。