CRDT无冲突复制数据类型深度实战：从算法原理到生产级Local-First应用架构
当你的应用在离线状态下依然能够正常工作，在网络恢复后数据能够自动合并且不产生冲突——这不是幻想，这是 CRDT（Conflict-free Replicated Data Types）带给现代分布式系统的能力。
一、引言：为什么我们需要 CRDT？
想象一下这个场景：你和团队成员同时编辑同一个文档段落，你们各自离线修改了内容。重新联网后，传统的解决方案会告诉你"该文件已被其他人修改，请手动合并"。CRDT 则优雅得多——它会自动、确定性地将你们的修改合并成一个一致的状态，无需人工干预，更无需中心服务器裁决。
这就是 Local-First Software（本地优先软件）运动的核心技术基石。Linear、Notion、Figma、Obsidian Sync、Apple Notes——这些产品的实时协作体验背后，CRDT 都扮演着关键角色。
CRDT 的核心承诺很简单：在任何网络条件下，多个副本最终会收敛到相同的状态。无论操作以什么顺序到达，无论中间经历多少次离线，结果都是一致的。
二、理论基础：让数学保证正确性
2.1 Join-Semilattice（并半格）
所有 State-based CRDT（又称 CvRDT）都构建在一个数学结构之上——Join-Semilattice：
- 偏序关系 (≤)：定义状态之间的"小于等于"关系。例如对于计数器，a ≤ b 表示 a 的每个分量的值都不大于 b。
- Join 操作 (∨)：两个状态的"最小上界"，满足三个性质：
- 幂等性：a ∨ a = a
- 交换律：a ∨ b = b ∨ a
- 结合律：(a ∨ b) ∨ c = a ∨ b ∨ c
这三个性质意味着：任意顺序、任意次数的合并，最终结果都相同。这就是 CRDT 能够离线工作的数学根基。
2.2 单调性增长
State-based CRDT 的状态只能单调递增（在偏序关系下）。每个副本的状态是所有已观察到操作的累积结果。当两个副本交换状态时，它们各自执行 join 操作，结果就是两个状态的并集。
这种设计带来的直接好处是： - 网络分区期间，副本可以继续演进（单调增长） - 网络恢复后，只需交换最新状态，join 即可收敛 - 无需保证消息顺序，无需向量时钟的全序关系
2.3 State-based vs Operation-based
| 维度 | State-based (CvRDT) | Operation-based (CmRDT) |
|---|---|---|
| 传输内容 | 完整状态 + 元数据 | 操作/增量更新 |
| 网络开销 | 较大（状态可能很大） | 较小 |
| 容错性 | 强（只需最终一次通信） | 弱（操作不能丢失） |
| 实现复杂度 | 中等 | 较高（需保证因果序） |
| 代表实现 | Yrs (Rust/Yjs 的 Rust 重写) | Automerge (旧版) |
实际上，现代高性能实现（如 Yjs、Yrs）通常采用混合策略：用 Operation-based 方式在本地生成增量更新，在远程合并时基于 state 做高效 diff，兼顾两者的优势。
三、经典 CRDT 类型详解
3.1 G-Counter（只增计数器）
最简单的 CRDT：一个节点 ID 到计数的映射，每个节点只能递增自己的槽位。
struct GCounter {
counts: HashMap<NodeId, u64>,
}
impl GCounter {
fn increment(&mut self, node: NodeId) {
*self.counts.entry(node).or_insert(0) += 1;
}
fn value(&self) -> u64 {
self.counts.values().sum()
}
fn merge(&mut self, other: &GCounter) {
for (node, count) in &other.counts {
let entry = self.counts.entry(*node).or_insert(0);
*entry = (*entry).max(*count); // join: 取最大值
}
}
}
3.2 PN-Counter（正负计数器）
将 G-Counter 拆成两个：一个记录增量（P），一个记录减量（N）。增加值 = P.value() - N.value()，但底层状态仍然是单调递增的。
struct PNCounter {
positive: GCounter,
negative: GCounter,
}
impl PNCounter {
fn increment(&mut self, node: NodeId) {
self.positive.increment(node);
}
fn decrement(&mut self, node: NodeId) {
self.negative.increment(node);
}
fn value(&self) -> i64 {
self.positive.value() as i64 - self.negative.value() as i64
}
fn merge(&mut self, other: &PNCounter) {
self.positive.merge(&other.positive);
self.negative.merge(&other.negative);
}
}
3.3 OR-Set（观察移除集合）
这是 CRDT 设计中最精妙的一种。核心思想：每次插入为元素生成唯一 tag，删除时不直接移除元素，而是将当前观察到的所有 tag 加入"墓碑集"。
struct ORSet<T> {
entries: HashMap<T, HashSet<Tag>>, // 元素 → 当前存活的 tag
tombstones: HashMap<T, HashSet<Tag>>, // 元素 → 已被删除的 tag
}
impl<T: Eq + Hash + Clone> ORSet<T> {
fn add(&mut self, element: T, tag: Tag) {
self.entries.entry(element)
.or_insert_with(HashSet::new)
.insert(tag);
}
fn remove(&mut self, element: &T) {
if let Some(tags) = self.entries.remove(element) {
self.tombstones.entry(element.clone())
.or_insert_with(HashSet::new)
.extend(tags);
}
}
fn contains(&self, element: &T) -> bool {
// 存在活着的 tag 且不在墓碑中才算存在
match self.entries.get(element) {
Some(tags) => tags.iter().any(|t| {
!self.tombstones.get(element)
.map(|ts| ts.contains(t))
.unwrap_or(false)
}),
None => false,
}
}
fn merge(&mut self, other: &ORSet<T>) {
// 合并 entries 和 tombstones，分别取并集
for (elem, tags) in &other.entries {
self.entries.entry(elem.clone())
.or_insert_with(HashSet::new)
.extend(tags);
}
for (elem, tags) in &other.tombstones {
self.tombstones.entry(elem.clone())
.or_insert_with(HashSet::new)
.extend(tags);
}
}
}
OR-Set 的关键洞察：移除操作只移除当时观察到的 tag，而不是"当前所有 tag"。这就是为什么它不会与并发插入冲突——新的插入会生成新的 tag，不受旧的移除影响。
3.4 RGA（可增长复制数组）
文本编辑场景需要保持有序性。RGA 是最经典的序列 CRDT 算法，它将文档表示为带因果标识的链表：
每个字符/元素都有： - 唯一的 ID（作者 + 逻辑时钟） - 一个"左邻居"引用（在哪个字符之后） - 内容值
并发插入到同一位置时，按作者 ID 全序排列，保证确定性。删除只是标记 tombstone（用于正确处理并发插入到已删除位置的情况）。
Yjs 团队在 RGA 基础上做了大量优化，发明了 YATA（Yet Another Transformation Approach），通过引入更精巧的冲突解决策略将时间复杂度从 O(n²) 优化到了接近 O(n)。
四、生产级实战：基于 Yjs 构建实时协作应用
4.1 Yjs 核心架构
Yjs 是目前性能最优、生态最完善的 CRDT 库（JavaScript），底层 Yrs 是它的 Rust 实现。
┌────────────────────────────────────────────┐
│ Client A │
│ ┌──────────┐ ┌──────────┐ �──────────┐ │
│ │ Y.Doc │←→│ Awareness│←→│ Provider │ │
│ │ (CRDT) │ │ (Cursors)│ │ (Network) │ │
│ └──────────┘ └──────────┘ └──────────┘ │
└────────────────────────────────────────────┘
│
┌─────┴─────┐
│ WebSocket │
│ Server │
└─────┬─────┘
│
┌────────────────────────────────────────────┐
│ Client B │
│ ┌──────────┐ ┌──────────┐ ┌──────────┐ │
│ │ Y.Doc │←→│ Awareness│←→│ Provider │ │
│ │ (CRDT) │ │ (Cursors)│ │ (Network) │ │
│ └──────────┘ └──────────┘ └──────────┘ │
└────────────────────────────────────────────┘
4.2 实战：构建一个协作待办清单
import * as Y from 'yjs'
import { WebsocketProvider } from 'y-websocket'
import { IndexeddbPersistence } from 'y-indexeddb'
// 1. 创建文档（本地优先）
const ydoc = new Y.Doc()
// 2. 本地持久化（IndexedDB）——即使关闭浏览器，数据也在
const indexeddbProvider = new IndexeddbPersistence('my-todo-app', ydoc)
// 3. 网络同步
const wsProvider = new WebsocketProvider(
'wss://my-server.com',
'todo-room-1',
ydoc
)
// 4. 共享数据类型
const yTodos = ydoc.getMap('todos') // Map<id, Todo>
const yOrder = ydoc.getArray('order') // Array<id> 保持顺序
// 5. 添加 Todo（离线也能操作！）
function addTodo(text: string) {
const id = crypto.randomUUID()
const todo = {
id,
text,
completed: false,
createdAt: Date.now()
}
yTodos.set(id, todo)
yOrder.push([id])
}
// 6. 同步到 UI
yTodos.observe(() => {
renderTodos(Array.from(yTodos.values()))
})
yOrder.observe(() => {
const orderedIds = yOrder.toArray()
const todos = orderedIds.map(id => yTodos.get(id))
renderTodoList(todos.filter(Boolean))
})
// 7. 远程协作：Awareness 状态（光标位置、用户信息）
wsProvider.awareness.setLocalState({
user: { name: 'Alice', color: '#ff6b6b' },
cursor: null // 不在此 demo 中实现
})
4.3 性能优化：增量更新与快照
Yjs 的核心优势之一是增量更新（Update）设计。文档的每次变更都会生成一个二进制增量更新，而不是传输完整状态：
// 监听增量更新（用于自定义网络传输）
ydoc.on('update', (update: Uint8Array, origin: any) => {
// update 是二进制编码的增量，通常只有几百字节
websocket.send(update)
})
// 应用远程更新
websocket.onmessage = (event) => {
Y.applyUpdate(ydoc, new Uint8Array(event.data), 'remote')
}
// 生成快照（用于首次连接或状态恢复）
const snapshot = Y.encodeStateAsUpdate(ydoc) // 完整状态的二进制编码
// 存储到数据库或本地文件...
// 从快照恢复
Y.applyUpdate(ydoc, storedSnapshot)
4.4 服务端部署（y-websocket 自定义服务器）
import { setupWSConnection, setPersistence } from 'y-websocket/bin/utils'
import * as Y from 'yjs'
import { LeveldbPersistence } from 'y-leveldb'
// 配置持久化
const ldb = new LeveldbPersistence('./yjs-storage')
setPersistence({
bindState: async (docName, ydoc) => {
const persistedYdoc = await ldb.getYDoc(docName)
const newUpdates = Y.encodeStateAsUpdate(ydoc)
ldb.storeUpdate(docName, newUpdates)
Y.applyUpdate(ydoc, Y.encodeStateAsUpdate(persistedYdoc))
ydoc.on('update', (update) => {
ldb.storeUpdate(docName, update)
})
},
writeState: async (docName, ydoc) => { /* 已在 bindState 中处理 */ }
})
// 集成到 Express
server.on('upgrade', (request, socket, head) => {
const url = new URL(request.url!, `http://${request.headers.host}`)
if (url.pathname.startsWith('/yjs/')) {
wss.handleUpgrade(request, socket, head, (ws) => {
wss.emit('connection', ws, request)
})
}
})
wss.on('connection', setupWSConnection)
五、CRDT vs OT：一场没有失败者的辩论
提到实时协作，绕不开 OT（Operational Transformation）。Google Docs 的协同编辑就是基于 OT（旧的 ShareJS 实现）或新式的衍生方案。
| 维度 | CRDT | OT |
|---|---|---|
| 服务端依赖 | 可选（纯 P2P 可行） | 必需（需中心服务器转换操作） |
| 离线编辑 | 天然支持 | 极其困难 |
| 实现复杂度 | 数据结构复杂，但无需服务端逻辑 | 服务端转换逻辑复杂（CP1/CP2 条件） |
| 网络要求 | 最终一致性，容忍任意延迟 | 需因果一致性保证 |
| 典型实现 | Yjs, Automerge | ShareJS, Google Docs |
| 大文档性能 | O(N) 到 O(log N) | O(N)，但常数更小 |
| 确定性保证 | 数学证明（Lattice 理论） | 条件证明（CP1/CP2） |
实战建议： - 新项目首选 CRDT（尤其 Yjs），生态成熟、离线能力强 - 超大文档（数万段落）文本编辑：考虑 OT + CRDT 混合（如 Google Docs 新架构） - 对实时性要求极高、且能保证低延迟的场景：OT 在纯文本编辑延迟上仍有优势
六、Local-First 架构全貌
CRDT 只是 Local-First 大厦的一块砖。一个完整的 Local-First 应用还需要：
6.1 数据存储层
┌─────────────────────────────────────────┐
│ Application │
├─────────────────────────────────────────┤
│ CRDT Sync Layer (Yjs / Automerge) │
├─────────────────────────────────────────┤
│ Local Persistence │
│ ├── IndexedDB (Browser) │
│ ├── SQLite / DuckDB (Electron/Tauri) │
│ └── File System API (PWA) │
├─────────────────────────────────────────┤
│ Sync Transport │
│ ├── WebSocket (实时协作) │
│ ├── HTTP + Delta Sync (低频同步) │
│ └── P2P (WebRTC / BLE / LAN) │
└─────────────────────────────────────────┘
6.2 离线优先的数据流
[用户操作] → [本地状态更新] → [立即反映到 UI]
↓
[生成 CRDT 增量] → [写入 IndexedDB]
↓
[队列待同步] ──(网络可用)──→ [发送到其他对等节点]
关键原则：本地操作绝不等待网络。这带来了两个直接收益： 1. 用户感知延迟为 0（操作即时生效） 2. 网络故障时用户完全无感（体验不间断）
6.3 冲突解决策略
尽管 CRDT 在数据结构层面消除了"合并冲突"，业务层面的冲突仍需处理：
// 示例：业务层冲突解决——两个用户同时修改同一个字段
yMap.observe((event) => {
event.changes.keys.forEach((change, key) => {
if (change.action === 'update') {
const currentValue = yMap.get(key)
// 业务逻辑：以时间戳较新的操作为准
// （CRDT 已经保证了结构一致，我们只需处理语义）
detectSemanticConflict(key, currentValue)
}
})
})
三种常见策略：
- Last-Writer-Wins（LWW）：以时间戳最新者为准。简单但可能丢数据。
- Multi-Value Register：保留所有并发值，呈现给用户选择。适合关键操作。
- 自定义合并函数：针对特定业务逻辑设计合并策略（如购物车合并 = 数量相加）。
七、性能深度优化
7.1 文档结构分区
不要把所有数据放在一个大 Y.Doc 里。按功能分区：
// 每个 ydoc 是一个独立的 CRDT 文档
const docA = new Y.Doc() // 文档正文
const docB = new Y.Doc() // 评论系统
const docC = new Y.Doc() // 用户光标位置（高频更新，独立同步）
// 好处：
// 1. 评论的更新不会干扰正文的性能
// 2. 光标位置的高频更新（每秒多次）独立传输
// 3. 每个文档可以独立持久化，按需加载
7.2 二进制编码优化
Yjs 的更新使用自定义的二进制编码（衍生自 lib0 encoding），比 JSON 紧凑 5-10 倍。对于一个典型的 1000 字文档编辑操作：
- JSON 编码：约 2-5 KB
- Yjs 增量更新：约 200-800 字节
自定义编码的关键技术： - VarInt 变长整数编码 - 重复字符串字典压缩 - 操作类型批量合并
7.3 大文件处理：Lazy Loading
对于超大文档（如 10 万字的书籍编辑）：
// Yjs 支持 Document Structuring——按需加载段落
const yText = ydoc.getText('content')
// 超大文档可以拆分为多个 Y.Array / Y.Map 单元
// 仅当用户滚动到对应位置时才加载对应段落的 CRDT 状态
7.4 GC 与历史管理
CRDT 的 tombstone 会无限增长，长期运行需要 GC 策略：
// Yrs (Rust API) 支持自动 GC
let doc = Doc::new()
doc.transact_mut().apply_update(update)
// GC 删除不再可达的 tombstone
// 注意：GC 在 State-based CRDT 中更常见
// Operation-based CRDT 通常保留完整历史（可回滚）
实战权衡：保留历史意味着支持"时光机"功能（撤销到任意时间点），这对某些应用是必需的。如果不需要，定期 snapshot 并重建文档可有效控制存储膨胀。
八、Yrs：Rust 重写带来的性能革命
Yjs 的 Rust 实现（Yrs + 各语言绑定）在 2024-2025 年带来了 10-50x 的性能提升：
| 操作 | Yjs (JS) | Yrs (Rust/WASM) |
|---|---|---|
| 10 万字符插入 | ~800ms | ~30ms |
| 1000 次交替插入 | ~200ms | ~8ms |
| 大文档首次合并 | ~5s | ~200ms |
Yrs 还通过 WASM 提供了浏览器端使用 Rust 性能的能力，以及通过 FFI 提供了 Swift/Kotlin 原生绑定，使得 iOS/Android 应用也能享受 CRDT 的优势。
// 用 Rust/Yrs 创建文档
use yrs::{Doc, ReadTxn, StateVector, Transact, Update};
use yrs::updates::decoder::Decode;
let doc = Doc::new();
let text = doc.get_or_insert_text("content");
// 在事务中操作
let mut txn = doc.transact_mut();
text.push(&mut txn, "Hello, ");
text.push(&mut txn, "CRDT!");
drop(txn);
// 生成增量更新
let update = doc.transact().encode_diff_v1(&StateVector::default());
// 发送给其他对等节点...
九、行业应用案例深度剖析
9.1 Linear：工程管理的协作标杆
Linear 的键盘驱动交互体验部分得益于其自研的同步引擎（基于 CRDT 思想，非 Yjs）。核心设计： - 每个 Issue 是一个独立的 CRDT 文档 - 视图过滤和排序是本地计算（基于 CRDT 状态） - GraphQL Mutation 在本地乐观更新，后台异步同步
启示：CRDT 不仅用于文本编辑，任何需要"多方同时修改的共享数据结构"都可以用 CRDT。
9.2 Figma：设计工具的实时协作
Figma 使用的是自研的 CRDT 变体（Figma 的引擎从 OT 迁移到 CRDT），处理对象图而非纯文本。关键技术： - 场景图（Scene Graph）的 CRDT 表示 - 嵌套组件的引用一致性 - 属性级别的原子操作
9.3 Notion：块级 CRDT
Notion 的每个 Block（段落、图片、数据库行）都是独立 CRDT 操作单元。数据库特性带来了额外的挑战： - 排序冲突（两个用户同时拖拽行） - 过滤/视图定义的并发修改 - 跨 Block 引用的一致性
十、总结与实践建议
CRDT 已从学术概念成长为生产级技术。以下是我的实践总结：
- 能不用 CRDT 就不用——如果场景可以用简单的 LWW 或中心锁解决，不要引入 CRDT。复杂度是有成本的。
- 需要离线编辑/多端同步时，CRDT 是最优选——没有其他技术能如此优雅地处理分区容忍。
- 首选 Yjs/Yrs 生态——社区活跃、性能顶尖、文档完善（比 Automerge 快 10 倍以上）。
- 按功能分区文档——不要把所有数据塞进一个 Y.Doc。
- 注意 tombstone 膨胀——长期运行的协作应用需要 snapshot + GC 策略。
- 业务冲突仍需人工策略——CRDT 解决结构冲突，语义冲突需要 custom merge logic。
- Awareness 是独立系统——光标/在线状态等高频低价值数据应该走单独通道。
最后，CRDT 的真正价值不仅是"解决技术问题"，更是重塑产品哲学：让应用信任用户设备，把用户数据从云端拿回用户手中，在保持实时协作体验的同时保障数据主权。
这就是 Local-Final 运动的终极愿景——数据属于用户，协作发生于对等网络，云端只是可选的加速器而非必要的基础设施。
参考资料： - Shapiro et al., "Conflict-free Replicated Data Types", INRIA 2011 - Yjs 官方文档: https://docs.yjs.dev/ - Local-First Web Development: https://localfirstweb.dev/ - Kevin Jahns, "Yjs - A CRDT framework for shared editing", 2021
发表评论 取消回复