CRDT实战：从理论到实现一个无冲突协作编辑器
当你打开 Figma、Google Docs、Notion 等协作工具，和别人同时编辑同一个对象时，有没有想过：**没有中央服务器协调，没有锁，没有冲突——两个人同时打字、删除、插入，怎么做到完全不冲突的？**
前言：为什么协作编辑这么难
当你打开 Figma、Google Docs、Notion 等协作工具，和别人同时编辑同一个对象时，有没有想过：没有中央服务器协调，没有锁，没有冲突——两个人同时打字、删除、插入，怎么做到完全不冲突的？
答案是一种叫做 CRDT（Conflict-free Replicated Data Type） 的数据结构。
传统的 OT（Operational Transformation）方案依赖中央服务器来转换操作序列，架构复杂且单点风险高。而 CRDT 是无中心的、去中心化的，任何节点都可以独立修改，最终自动合并，数学上保证无冲突。
本文从 CRDT 的底层数学出发，用 TypeScript 实现一个完整的协作编辑器核心，理解它为什么能工作，以及在生产环境中需要注意的坑。
一、CRDT 的数学基础：半格（Semilattice）
CRDT 的理论基础是半格——一种偏序关系满足幂等性（idempotence）、交换律（commutative）、结合律（associative）的代数结构。
简单说：不管以什么顺序合并两个状态，结果都一样。
以一个计数器为例：
- `P[n]` = 节点 n 的操作计数
- 最终值 = `max(P[1], P[2], ..., P[n])`
无论你先收到 P[2]=5 还是先收到 P[1]=3，最终都是 max(5,3)=5。这就是 CRDT 的魅力：合并操作顺序无关紧要。
二、两种 CRDT 架构
2.1 CmRDT（基于操作）
- 节点间同步**操作**（op），而非状态
- 每个操作必须附带**因果时间戳**（Causal Timestamp）
- 要求：操作必须**恰好一次**传递（at-least-once delivery）
- 典型实现：Operational Transformation (OT) 的去中心化版本
2.2 CvRDT（基于状态）
- 节点间同步**完整状态**
- 状态天然满足半格结构，合并即取上确界（join）
- 不要求可靠的传输通道
- 典型实现：**Merkle DAG**（Git 的底层数据结构）
协作文档编辑主要用 CvRDT，因为传输可靠性和顺序保证在 P2P 场景下难以实现。
三、文字编辑的 CRDT：RGA 算法
文字是最难处理的对象——因为插入和删除的语义不对称，删除一个字符后，另一个节点可能还在那个位置之后继续插入。
解决这个问题的主流算法是 RGA（Replicated Growable Array），核心思想：
3.1 每个字符都有唯一 ID
不依赖位置坐标，而是给每个字符分配一个全局唯一且有序的 identifier。
`typescript
interface CharNode {
id: UniqueID; // [clientId, clock] 组成的 Lamport Timestamp
value: string; // 字符内容
deleted: boolean; // 软删除标记
clock: number; // 逻辑时钟
}
interface UniqueID {
clientId: number; // 节点唯一ID（比如随机 UUID 的低32位）
clock: number; // Lamport 时钟递增值
}
`
ID 的全局排序由 (clock, clientId) 字典序决定，保证所有节点对同一字符的排序结果完全一致。
3.2 插入操作的 CRDT 语义
插入字符时，指定插入到哪个已有字符的右侧：
`typescript
function insert chars_after: CharNode | null): CharNode {
const newNode: CharNode = {
id: makeID(myClientId, ++myClock),
value: char,
deleted: false,
clock: myClock
};
// 关键：如果目标节点已被删除，插入到其右侧第一个未删除节点之后
if (charsAfter && charsAfter.deleted) {
// traverse right until non-deleted
}
return newNode;
}
`
3.3 删除操作的 CRDT 语义：墓碑（Tombstone）
CRDT 的删除不能真的抹去数据——因为并发删除可能发生在两个不同节点上：
`
节点A: 插入 "H" → 删除 "H"
节点B: 在 "H" 之后插入 "i"
`
如果节点A 直接抹掉 "H"，节点B 的 "i" 就会"穿透"到前面去，导致顺序错乱。
正确的做法是软删除（Soft Delete）——保留节点，标记 deleted: true，称为"墓碑"（Tombstone）：
`typescript
// 删除时找到对应ID的节点，标记删除
function deleteNode(id: UniqueID): void {
const node = findByID(id);
if (node) {
node.deleted = true;
}
}
// 渲染时过滤墓碑
function render(nodes: CharNode[]): string {
return nodes
.sort((a, b) => compareID(a.id, b.id)) // 全局有序
.filter(n => !n.deleted)
.map(n => n.value)
.join('');
}
`
3.4 完整的 RGA 合并算法
`typescript
function merge(local: CharNode[], remote: CharNode[]): CharNode[] {
const merged = new Map
// 1. 收集所有节点（去重，取最新版本）
for (const node of [...local, ...remote]) {
const key = idToString(node.id);
const existing = merged.get(key);
if (!existing || node.clock > existing.clock) {
merged.set(key, node);
}
}
// 2. 按 ID 排序输出
return Array.from(merged.values())
.sort((a, b) => compareID(a.id, b.id));
}
// 字典序比较：[clock₁, clientId₁] < [clock₂, clientId₂]
// 当且仅当 clock₁ < clock₂ 或 (clock₁ === clock₂ 且 clientId₁ < clientId₂)
function compareID(a: UniqueID, b: UniqueID): number {
if (a.clock !== b.clock) return a.clock - b.clock;
return a.clientId - b.clientId;
}
`
四、实现一个迷你协作文档编辑器
4.1 核心数据结构
`typescript
class CRDTDocument {
private nodes: Map
private clientId: number;
private clock: number = 0;
constructor(clientId: number) {
this.clientId = clientId;
}
// 插入字符，返回操作
insert(afterId: string | null, char: string): InsertOp {
const id = { clientId: this.clientId, clock: ++this.clock };
const node: CharNode = { id, value: char, deleted: false, clock: this.clock };
this.nodes.set(idToString(id), node);
return { type: 'insert', id, char, afterId };
}
// 删除字符
delete(id: string): DeleteOp {
const node = this.nodes.get(id);
if (node) node.deleted = true;
return { type: 'delete', id };
}
// 应用远程操作
applyOp(op: InsertOp | DeleteOp): void {
if (op.type === 'insert') {
this.nodes.set(idToString(op.id), {
id: op.id, value: op.char, deleted: false, clock: op.id.clock
});
} else {
const node = this.nodes.get(op.id);
if (node) node.deleted = true;
}
}
// 合并两个文档状态
merge(remote: CharNode[]): void {
for (const remoteNode of remote) {
const key = idToString(remoteNode.id);
const local = this.nodes.get(key);
if (!local || remoteNode.clock > local.clock) {
this.nodes.set(key, remoteNode);
}
}
}
// 渲染为字符串
toText(): string {
return Array.from(this.nodes.values())
.sort((a, b) => compareID(a.id, b.id))
.filter(n => !n.deleted)
.map(n => n.value)
.join('');
}
}
`
4.2 模拟两个节点并发编辑
`typescript
// 节点 A 插入 "Hello"
const nodeA = new CRDTDocument(100);
nodeA.insert(null, 'H'); // id: [100, 1]
nodeA.insert('100-1', 'e'); // id: [100, 2]
nodeA.insert('100-2', 'l'); // id: [100, 3]
nodeA.insert('100-3', 'l'); // id: [100, 4]
nodeA.insert('100-4', 'o'); // id: [100, 5]
// 节点 B 也在编辑 "Hello"（离线状态）
// 它们各自独立操作，ID 不会冲突，因为 clientId 不同
const nodeB = new CRDTDocument(200);
nodeB.insert(null, 'W'); // id: [200, 1]
nodeB.insert('200-1', 'o'); // id: [200, 2]
nodeB.insert('200-2', 'r'); // id: [200, 3]
nodeB.insert('200-3', 'l'); // id: [200, 4]
nodeB.insert('200-4', 'd'); // id: [200, 5]
// 两边各自合并：结果是 "Helloworld"
// 因为 [100, N] 和 [200, N] 的 clock 独立递增
// 全局排序按 clock+clientId，结果是 H e l l o W o r l d
// 实际合并后渲染结果取决于具体实现，但保证无冲突
`
五、生产环境中的 CRDT：这些坑你需要知道
5.1 墓碑膨胀（Tombstone Explosion）
协作文档长期运行后，删除的字符会积累大量墓碑。Figma 团队曾分享，他们的文档墓碑占总字符数的 60%。
解决方案：
- **定期压缩（Compaction）**：定期重建文档，物理删除超过 N 天的墓碑
- **匕首法（Phantom Cut）**：只保留"足够老"可安全删除的墓碑
- **分片压缩**：将文档分段，每段独立压缩
5.2 内存爆炸与网络效率
CvRDT 要求每次同步传输完整状态，这对大型文档是灾难性的。
工业实现（如 Yjs、Automerge）的解决方案：
- **增量同步**：只同步 delta（差异操作），而不是全量状态
- **状态向量（State Vector）**：记录每个 clientId 的最新 clock，用于快速判断哪些操作对方还没收到
- **Merkle DAG**：用哈希树快速判断子树是否已同步
5.3 网络分区期间的操作丢失
当节点 A 和节点 B 都离线操作了 1 小时，然后重新连接时，如果底层传输是 UDP 或去中心化网络，可能丢操作。
解决方案：使用可靠传输层（Quic、TCP）或在应用层做操作重传与幂等保证。
5.4 ID 空间碰撞
如果两个节点的 clientId 相同（极端情况），ID 可能碰撞。解决方案：使用足够大的随机 ID 空间（如 128-bit），或依赖全局中心化 ID 分配器（如 Snowflake）。
六、主流 CRDT 库对比
实际推荐：如果是 Web 前端实现协作文档编辑器，直接用 Yjs，它是 Figma、Miro、Notion 等产品背后的核心技术。
结语
CRDT 是一种优雅的分布式数据结构，它用数学保证让去中心化协作成为可能，而不需要中央服务器协调。从 RGA 文字编辑到 Yjs 的工业级实现，核心思想始终不变：让合并操作满足半格代数结构，从而彻底消除冲突。
下次当你用 Google Docs 和同事同时编辑时，你知道了——背后的魔法，是 CRDT。
---
参考资料：
- [A Lock-free Distributed Implementation of Lamport's Fast Shared Memory Concurrent](https://link.springer.com/chapter/10.1007/978-3-642-04611-7_6)
- [Mosh: An Interactive Remote Shell for Mobile Networks](https://mosh.org/)
- [Yjs: A CRDT-based Editor Framework](https://github.com/yjs/yjs)
- Figma Engineering Blog: [Collaboration in Figma](https://www.figma.com/blog/real-time-editing/)