协同架构

多人实时协同冲突解决算法深度剖析：OT（操作转换）与 CRDT（无冲突复制数据类型）

全面解析分布式与实时协同编辑的核心冲突算法：对比 Google Docs 的 OT 集中式转换矩阵，与 Yjs / Automerge 所采用的 CRDT（状态型与操作型）数学模型及 YATA 算法实现。

· 10 分钟

在开发多人同时在线编辑的富文本编辑器（如 Google Docs、Notion、Figma 或代码协作工具）时，最底层的核心难题是：当多个用户在不同的地理位置、不同的网络延迟下对同一个文档的同一段落进行并发插入与删除时，如何保证所有人最终看到完全一致的文档内容？

解决这一问题的主流算法经历了从 OT（操作转换） 到 CRDT（无冲突复制数据类型） 的演进。

协同编辑的根本挑战：并发冲突

假设初始文本为 "Cat"，用户 A 在索引 0 插入 "Big "（变成 "Big Cat"），同时用户 B 在索引 3 插入 "s"（变成 "Cats"）：

TEXT
       初始状态: "Cat"
      ┌────────┴────────┐
      ▼ (User A: 插入 "Big " at 0)  ▼ (User B: 插入 "s" at 3)
   "Big Cat"                         "Cats"
      │                                 │
      ▼ 直接应用对方原始操作              ▼ 直接应用对方原始操作
   "Big Cats"                       "Big sCat"  ❌ 产生状态分裂与乱序！

如果不经处理直接广播坐标偏移量，由于网络到达时间不同，不同客户端上的文本索引会发生错位，导致内容彻底崩溃。

方案一：OT（Operational Transformation，操作转换）

OT 最早于 1989 年提出，是 Google Docs 和 Apache Wave 的基石。

1. 核心思想：转换函数 $T(op_1, op_2)$

OT 的思想是：当客户端收到来自其他用户的并发操作时，不直接应用，而是根据本地已发生的操作对该操作的坐标位置进行“平移转换”。

TEXT
OT 转换过程:
  用户 B 发来的操作: opB = Insert("s", index=3)
  用户 A 本地已执行: opA = Insert("Big ", index=0, len=4)
  经过转换: opB' = T(opB, opA) = Insert("s", index = 3 + 4 = 7)
  用户 A 应用 opB' 后得到: "Big Cats" ✅

2. OT 的核心痛点

  • 必须依赖中心服务器排序：OT 需要单一权威服务器为所有操作分配绝对全局版本号。
  • 组合爆炸与工程极其复杂：当并发操作包含富文本样式、删除、表格、段落嵌套时，两两转换函数 $T(op_i, op_j)$ 极其繁琐，难以形式化证明完全一致。
  • 离线支持差：长时间离线重新连线时，需要向服务器回溯重放大量历史操作。

方案二：CRDT（Conflict-free Replicated Data Type）

CRDT 于 2006 年后兴起，是去中心化、本地优先（Local-first）协同的核心算法。

1. 核心数学保证：交换律与结合律

CRDT 不试图去“平移可变索引”，而是给文档中的每一个字符/节点分配一个全网唯一的、不可变的逻辑 ID（如 { clientId, clock }），通过构建偏序关系图，确保无论操作以何种顺序到达、重复接收多少次，合并后的最终状态必然完全一致。

TEXT
CRDT 核心两大流派:
├── 基于状态的 CRDT (CvRDT): 传输全量状态/状态向量，通过数学半格(Lattice)的 join (⊔) 操作合并
└── 基于操作的 CRDT (CmRDT): 传输轻量增量操作，要求底层网络保证因果有序传递 (Yjs 属于此类)

Yjs 的 YATA 算法实现与性能突破

早期 CRDT 被工业界诟病的主要原因是内存膨胀严重（每个字符都要挂载元数据，删除后保留 Tombstone 墓碑，导致内存比纯文本大几十倍）。

Yjs（由 Kevin Jahns 创造） 凭借独创的 YATA 算法 解决了这一难题：

TEXT
Yjs 链表结构 (Struct / Item):
┌───────────────────────────────────────────────────────────┐
│ ID: { client: 42, clock: 0 }                              │
│ OriginLeft: ID(Prev)   | OriginRight: ID(Next)            │
│ Content: "Hello World" (多个连续输入的字符自动合并为一个 Struct) │
│ Deleted: false                                            │
└───────────────────────────────────────────────────────────┘
  1. 块合并优化（Struct Merging）：连续输入的文本被压缩进同一个结构体中，元数据开销降低 90% 以上。
  2. 状态向量（State Vector）计算最小差异：双端同步时，仅需交换几字节的状态向量，毫秒级计算出缺失的增量补丁（Delta Update）。
  3. 墓碑垃圾回收（GC）：对于已经解引用或父级被删除的树节点，安全清理墓碑标记。

OT 与 CRDT 全方位对比

评估维度OT (操作转换)CRDT (以 Yjs 为代表)
网络拓扑必须依赖集中式服务器仲裁支持 P2P、去中心化与边缘 WebSocket
离线优先能力较弱，长离线重连容易冲突极其强悍，任意时长离线自动合并
工程实现复杂度转换矩阵极其复杂，极易出现边缘 Bug算法严谨，由底层库（Yjs / Automerge）封装
内存开销极低（仅存文本与操作）稍高于文本，但现代 Yjs 优化后已接近原生
典型代表Google Docs, 飞书文档Notion, Figma, Apple Notes, TipTap

总结

  • OT 属于上一代以中心服务器为绝对权威的协同技术。
  • CRDT (Yjs) 以优雅的数学一致性模型与出色的离线合并能力，成为现代多人协同编辑器、白板与协作画板的绝对事实标准。