CRDT与无冲突复制数据类型：实时协作系统的算法基础与工程实践深度对比

一、CRDT 的本质与理论基础

CRDT（Conflict-free Replicated Data Type，无冲突复制数据类型）是一种数据结构，其设计目标是使多个副本在任意网络条件下（断网、分区、并发更新）独立执行操作，无需协调即可收敛到相同状态。2011 年 Marc Shapiro 等人在论文 "A comprehensive study of Convergent and Commutative Replicated Data Types" 中首次形式化定义了 CRDT 理论。

CRDT 的核心数学性质：

• 交换律（Commutativity）：a ∘ b = b ∘ a，操作顺序不影响结果
• 结合律（Associativity）：(a ∘ b) ∘ c = a ∘ (b ∘ c)，操作分组不影响结果
• 幂等性（Idempotence）：a ∘ a = a，重复操作不改变状态
• 偏序收敛（Convergence）：所有副本最终进入相同的最大下界（semilattice join）

二、两大流派：State-based vs Op-based

三、经典 CRDT 实现详解

1. G-Counter（Grow-only Counter）：每个节点维护一个 [nodeID → count] 的向量，本地递增只修改自身槽位，合并取各槽位最大值。sum = Σ count_i，天然满足交换/结合/幂等。

2. PN-Counter（Positive-Negative Counter）：由两个 G-Counter 组合（P 记录增量，N 记录减量），最终值 value = sum(P) - sum(N)，支持递增和递减操作，是分布式计数器的事实标准。

3. LWW-Element-Set（Last-Writer-Wins Set）：每个元素附带时间戳（或 Lamport/HLC），add(e, ts) 只在 ts 更大时生效，remove 表示逻辑删除也带时间戳。

4. OR-Set (Observed-Remove Set)：解决 LWW 的"重复添加"问题。每个元素创建时分配唯一 tag，删除仅移除观察到的 tag（而非时间戳比较）：

add(e): 生成唯一 tag t, 插入 ⟨e, t⟩
remove(e): 收集本地已知的 e 的所有 tag T, 发送移除命令 discard(T)
merge: 存在于 add 集但未被 discard 集的 tag 覆盖的元素保留

5. RGA (Replicated Growable Array) / YATA：用于协同编辑的 CRDT 序列结构。每个字符分配唯一 ID (siteID, clock, 偏移)，按因果序排列。删除标记为逻辑删除（tombstone），后续插入基于前驱节点的 ID 确定位置冲突解决：

插入 ID_a 在 ID_b 之后：
冲突规则：siteID_a > siteID_b（字典序，平局时按 siteID 排序）
保证：全网相同的插入顺序产生相同的最终序列

6. Yjs 的 YATA 改进：Marc Shapiro 团队提出的 YATA 将 RGA 的最坏情况 O(n²) 冲突解决优化为 O(n)，通过将新插入项关联到最近的已知前驱，Yjs 在此基础上实现了更高效的 DOM 标记链表，已被自动转为 JavaScript API。

四、CRDT vs OT（Operation Transformation）对比

实践选择：地理分布式多活（如 CRDT 电子表格）倾向 CRDT；传统 C/S 模式中心协同编辑（如腾讯文档）倾向 OT，最先进系统是两者的混合（如 Fluid Framework 的 CRDT + 中心 relay，Figma 的 CRDT + 权限层）。

五、工程实现：Yjs 与 Automerge 实战

Yjs（目前性能最优的开源 CRDT 库）核心 API：

import * as Y from 'yjs'
const doc = new Y.Doc()
const yarray = doc.getArray('myarray')
const ymap   = doc.getMap('mymap')
const ytext  = doc.getText('mytext')

// 本地操作
ymap.set('key', 'value')
ytext.insert(0, 'Hello')
yarray.push([42])

// 状态同步（二进制增量，高效）
const update = Y.encodeStateAsUpdate(doc) // Uint8Array
Y.applyUpdate(remoteDoc, update)          // 接收端应用

// 增量式更新（基于 state vector 的差异交换）
const stateVector = Y.encodeStateVector(doc)
const diff = Y.encodeStateAsUpdate(doc, stateVector) // 仅发送对方缺少的部分

Yjs + Provider（网络层）：

• y-websocket：WebSocket Provider，服务端维护文档状态，客户端连接时下发 Diff
• y-webrtc：WebRTC DataChannel 的 CRDT P2P 同步（无中心服务器）
• y-indexeddb：浏览器本地持久化，支持离线编辑同步
• y-prosemirror / y-monaco / y-tiptap：富文本/代码编辑器的 CRDT 适配器

Automerge（Rust → WASM 编译到 JS）优势：

• 自动结构体序列化/反序列化（JSON 兼容）
• 强大的冲突处理 API（Automerge.getConflicts()）
• 支持历史回溯（Automerge.diff()）

六、性能优化与内存管理

CRDT 系统的常见开销与优化：

• Tombstone 垃圾回收：Yjs 采用 skip list + deletion-aware state vector，Automerge 采用 columnar storage + run-length encoding。关键策略：无Observer时累积的 tombstone 可被压缩；但需保证离线节点回归时不丢失操作
• Delta 编码：Yjs 的增量更新平均只有全量的 1/50～1/200，10万字文档的 delta 仅 ~2KB
• 内存-磁盘分层：LevelDB/RocksDB 存储历史节点，活动窗口驻留内存
• 事务批处理：Yjs 的 doc.transact(fn) 将合并多个操作为一个 update 传输，减少网络往返

Yjs 的 benchmark：协同 Markdown 编辑，64 客户端 × 5 字/秒 × 60 秒 = 2万字，最终文档状态（无 tombstone 压缩）= 168MB；Yjs 的全量同步字节数为 1.7MB；增量同步每次 ~3KB。LLM 辅助协同写作的起步协议（query→update）在 Yjs 上延迟 <20ms>

七、前沿研究与应用场景

CRDT 在以下场景已大规模落地：

• 线性文档：Notion、Figma 的评论使用 LWW-Element-Map + YATA 序列
• 电子表格：Spreadsheet CRDT 使用二维表 CRDT（RCell = Register + Row/Col CRDT + Formula Graph）
• 分布式数据库：Redis CRDT、CockroachDB 的 Multi-Value Register、Antd 的 useController CRDT
• IoT / 离线优先：Weak-link CRDT 在断网 72小时后重连仍能在 2 次握手内完成 MB 级状态同步
• 实时协作平台：Liveblocks、PartyKit 均底层基于 Yjs，服务端仅作中继

研究前沿：

• OLOG（Observed Log）CRDT：统一 LWW 和 OR-Set 的通用模型
• 可组合 CRDT 编排：已有理论保证组合 CRDT 仍是 CRDT，但实践中的冲突语义需仔细推导
• CRDT + MLS / RatTree：将 CRDT 与 Merge Logging 结构融合，构建可审计的协作历史

八、总结与选型建议

选型清单：

• 文本/代码协同编辑：Yjs（生态最成熟）、Merkle-CRDT（如 Merkle 树型 CRDT）
• 通用结构化状态：Automerge（编译为 WASM 快 20×）或 Fluid Framework（微软）
• 键值/计数器：自研 PN-Counter + LWW-Map（实现更简单）
• 低延迟音视频同步：HLC（Hybrid Logical Clock）+ PN-Counter 的 LSeq

CRDT 的核心价值不在于"取代共识算法"，而在于为"断网后仍可工作"的场景提供数学保证。理解其 trade-off（内存换可用性、无原生"撤销"语义、无即时全序）是工程落地的关键。