CRDT 与 OT 算法：分布式协同编辑数据结构设计 - Yjs 实战与无冲突复制原语

协同编辑的核心挑战：冲突、延迟与一致性

分布式协同编辑（Distributed Collaborative Editing）允许多个用户同时编辑同一文档，核心难题在于如何在网络延迟、并发操作、断网重连等复杂场景下保证最终一致性。从Google Docs到Notion、Figma、腾讯文档，协同编辑已成为现代生产力工具的标配功能。本文深入比较CRDT与OT两大技术路线的数学原理、工程实现与适用场景。

OT（Operational Transformation）算法原理

OT是最早的协同编辑解决方案，其核心思想是：当用户对文档执行操作时，如果其他并发操作已经改变了文档状态，则需要将新操作"转换"以适应变化后的文档位置。

OT的关键概念：

• 操作（Operation）：Insert(position, char) 或 Delete(position, length)
• 转换函数 T(op1, op2)：将op1相对于op2进行变换，使得先执行op2再执行变换后的op1，与先执行op1再执行op2得到相同文档状态
• 收敛性（Convergence）：所有站点在收到相同操作集合后，文档状态一致
• 中央服务器模式：所有操作经过服务器排序和转发，客户端只需处理与服务器状态的差异

经典OT算法包括：dOPT、GOT (Jupiter)、Google Wave OT、OTExt，但转换函数的正确性证明极其复杂，实际实现bug率较高。

CRDT（Conflict-free Replicated Data Types）数学原理

CRDT基于数学上证明的收敛数据结构，无需操作转换即可保证最终一致性。分为两大类别：

Op-based CRDT（CmRDT - Commutative Replicated Data Type）

• 操作满足交换律：apply(op1); apply(op2) = apply(op2); apply(op1)
• 要求传播通道保证因果一致性（不要求全序），操作不重复执行

State-based CRDT（CvRDT - Convergent Replicated Data Type）

• 状态空间构成一个半格（Semi-lattice），join操作返回两个状态的最小上界（LUB）
• 合并函数满足：交换律、结合律、幂等律
• 要求传播通道保证最终交付（gossip或anti-entropy协议）

Yjs：工业级CRDT协同编辑库

Yjs是目前最成熟的CRDT协同编辑JavaScript库，其核心设计：

• 实现基于YATA（Yet Another Transformation Approach）的序列CRDT
• 支持文本（Y.Text）、数组（Y.Array）、映射（Y.Map）、XML元素（Y.XmlElement）等多种数据类型
• 内置基于双向链表的ID定位机制，支持O(1)的本地操作
• 编码压缩的UPDATE格式，通过WebSocket/WebRTC/gRPC等多种方式同步

Yjs架构核心：每个字符分配唯一的ID（clientID, clock），通过左右邻居关系建立全局顺序。删除操作通过tombstone标记（soft delete）实现，保证并发插入时的一致性和可溯源性。

CRDT vs OT实战对比

维度	OT	CRDT (Yjs)
去中心化	需要中央服务器排序	支持P2P直传（无需服务器）
离线支持	需重新连接后复杂同步	天然支持，merge离线变更
实现复杂度	极高（转换函数证明）	中等（库已封装复杂度）
内存占用	较低	较高（需保留tombstone）
网络效率	操作小（仅增量）	UPDATE增量小，但全状态较大
社区生态	ShareDB, ot.js, Google Wave	Yjs, Automerge, Loro

生产实践：富文本协同编辑架构设计

以Notion-like文档编辑器为例，推荐架构：

// Yjs + y-websocket + Tiptap 集成示例
import * as Y from 'yjs'
import { WebsocketProvider } from 'y-websocket'
import { ySyncPlugin } from 'y-prosemirror'
import { Editor } from '@tiptap/core'

// 创建共享文档
const ydoc = new Y.Doc()
const yXmlFragment = ydoc.getXmlFragment('prosemirror')

// WebSocket连接同步
const wsProvider = new WebsocketProvider(
  'wss://collab.example.com',
  'document-room-123',
  ydoc
)

// Tiptap编辑器绑定Yjs
const editor = new Editor({
  extensions: [
    // ...其他extensions
    ySyncPlugin(yXmlFragment),
  ]
})

// 监听在线用户状态
wsProvider.awareness.on('change', () => {
  const states = wsProvider.awareness.getStates()
  renderCursorsAndSelections(states)
})

未来方向：CRDT的优化与前沿

CRDT研究的前沿方向包括：Local-first Software范式（离线优先、数据本地存储自动合并）、Columnar CRDT（将文本按行/段落列化以优化大文档性能）、Automerse 2.0的新索引策略压缩tombstone、Loro的因果树（Causal Tree）变体提供更高效的文本CRDT。随着WebAssembly与Rust的实现进入主流（Yjs已发布y-crdt Rust核心），协同编辑的性能天花板正在被不断刷新。在AI辅助编辑器（如Cursor协作模式）的新时代，CRDT将成为构建实时、智能、可靠协作体验的数据基石。