Event Graph Walker（Eg-Walker）
Event Graph Walker（Eg-Walker）是一种颠覆性的 CRDT 算法，从根本上改变了协同编辑系统处理并发操作的方式。它不再依赖复杂的 CRDT 元数据，而是通过在需要时高效回放相关历史，让我们可以使用简单的索引值。
重要提示：Loro 并不是对 Event Graph Walker 的严格实现。Loro 深受 Eg-Walker 设计理念的启发，吸收了其中的关键洞见，从而获得类似的能力——尤其是用简单索引取代复杂元数据，以及在处理并发操作时的高效回放机制。
问题：复杂的 CRDT 元数据
传统 CRDT 为了在分布式系统中保持一致性，需要维护大量元数据：
- RGA 算法：需要记录左侧邻居的操作 ID 与 Lamport 时间戳
- Yjs / Fugue：需要记录左右两侧邻居的操作 ID
- 存储开销：每个操作都要携带用于定位的大量元数据
- 墓碑堆积：被删除的内容必须永久保留
这些复杂度会导致：
- 存储需求显著增加
- 文档越大性能越慢
- 垃圾回收策略复杂
- 更高的网络带宽消耗
创新：简单索引 + 智能回放
Eg-Walker 提出全新范式：记录简单索引，需要时再回放。
核心理念
Eg-Walker 不再存储复杂的位置描述，而是：
- 在执行操作时记录简单索引
- 维护一张编辑历史的有向无环图（DAG）
- 在合并并发修改时按需回放相关历史
- 仅在需要时重建精确的 CRDT 状态
工作原理
事件图（Event Graph）
在协同编辑中，并行操作天然会形成类似 Git 历史的有向无环图（DAG）：
A --- B --- C (用户 1)
/ \
Root Merge
\ /
D --- E --- F (用户 2)每个节点代表一个操作，边表示因果依赖关系。
算法流程
1. 本地操作：直接且高效
当用户执行本地编辑时：
- 使用当前的索引位置记录操作
- 无需计算复杂元数据
- 立即应用到文档
示例：
// 传统 CRDT（例如 RGA）
insert({
char: 'a',
leftId: 'op-123',
timestamp: 1234567890,
siteId: 'user-1'
})
// Eg-Walker
insert({
char: 'a',
index: 5 // 只需索引！
})2. 合并远端操作：智能回放
当接收到远端操作时：
- 找到本地与远端版本之间的最近公共祖先（LCA）
- 从公共祖先开始，回放历史到双方版本
- 构建临时 CRDT 状态计算影响
- 应用合并结果
关键点：只需回放分叉部分的历史，而非整个文档。
3. 索引变换
例如：
- 你高亮选中索引 10 到 20 的文本
- 同时有人在索引 3 插入了 5 个字符
- 你的选区应该移动到 15 到 25
Eg-Walker 的做法：
- 通过事件图识别并发操作
- 按因果顺序回放操作
- 根据回放序列转换索引
性能收益
1. 更小的存储
| 项目 | 传统 CRDT | Eg-Walker |
|---|---|---|
| 墓碑存储 | 永久保留 | 可安全回收 |
| 文档增长 | 随全部操作线性增长 | 随有效内容线性增长 |
2. 更快的本地更新
- 无需元数据计算：直接基于索引操作
- 无需遍历墓碑：文档状态干净
- 性能可预期：大多数本地操作为 O(1) 或 O(logN)
3. 更高效的同步
- 最小化回放：仅处理分叉历史
- 有界计算量：与并发操作数量相关，而非文档大小
- 智能缓存：复用已计算的临时状态
Loro 中的实现
虽然 Loro 不是纯粹的 Eg-Walker 实现，但它大量借鉴了 Eg-Walker 的创新，以实现类似的优势。Loro 在实现 Fugue（现代 CRDT 算法）的同时，融入了 Eg-Walker 式的优化：
- Fugue 提供文本编辑的正确性保证
- Eg-Walker 式高效性 降低存储和计算成本
- 简单的索引化 API 让开发者易于使用
- 智能回放机制 用于合并并发更改
由此带来如下体验：
// 简洁的 API，强大的内部实现
const doc = new Loro();
const text = doc.getText("content");
// 只需使用索引，Eg-Walker 处理复杂细节
text.insert(5, "Hello");
text.delete(2, 3);
// 合并高效自动完成
doc.import(remoteUpdate);垃圾回收的变革
Eg-Walker 最大的优势之一是安全的垃圾回收：
传统 CRDT
- 必须永久保留所有墓碑
- 文档体积无限增长
- 需要复杂的协调清理协议
使用 Eg-Walker
- 各端已完全同步的操作可以安全删除
- 不会再有新操作与这些旧操作并发
- 文档大小始终与有效内容成正比
研究基础
Eg-Walker 来自严谨的学术研究：
Collaborative Text Editing with Eg-walker: Better, Faster, Smaller
作者：Joseph Gentle, Martin Kleppmann
该算法已经证明：
- 保持强最终一致性
- 保留 CRDT 的全部正确性特性
- 显著降低计算与存储开销