【分布式系统百科】CRDT 在协同编辑中的应用：从 OT 到 Yjs 与 Automerge

两个人同时编辑同一段文字。用户 A 在位置 3 插入字符 “x”，用户 B 删除位置 2 的字符。这两个操作在各自的本地副本上独立执行，没有问题。但当 A 的操作传到 B 那里时，位置 3 已经因为 B 的删除而偏移了——如果直接应用，文档就乱了。

这个问题从 1989 年 Ellis 和 Gibbs 发表第一篇协同编辑论文开始，就一直困扰着分布式系统研究者。三十多年来，工业界和学术界给出了两条根本不同的解决路径：操作变换（Operational Transformation，OT）和无冲突复制数据类型（Conflict-free Replicated Data Type，CRDT）。前者依赖一个集中式服务器对并发操作进行变换；后者通过数学性质保证任意顺序合并都能收敛到相同状态。

Google Docs 用的是 OT。Figma 用的是 CRDT。两者的架构选择背后是完全不同的工程权衡。这篇文章从算法原理开始，逐一拆解 Yjs、Automerge、Diamond Types 三个主流 CRDT 实现，用实际的 benchmark 数据说明它们的性能差异，最后讨论在真实产品中落地协同编辑时会遇到的工程挑战。

一、OT 与 CRDT：两条路径的对比

1.1 OT 的历史与设计哲学

OT 的故事始于 1989 年 Ellis 和 Gibbs 在 SIGMOD 上发表的 GROVE 系统。核心思想很直接：当两个用户的操作并发时，在应用远端操作之前，先用一个变换函数（transform function）把它调整成在当前本地状态下语义等价的操作。

假设文档初始内容是 “abc”。用户 A 执行 ins(3, 'x')（在位置 3 插入 ‘x’），用户 B 执行 del(1)（删除位置 1 的字符）。A 的操作发送到 B 时，B 已经删除了位置 1，文档变成 “ac”。此时位置 3 已经不对了。OT 的变换函数 xform 计算出：因为 B 删除了位置 1（在 A 的插入位置 3 之前），A 的操作应该调整为 ins(2, 'x')。

形式化地说，OT 要求变换函数满足一个关键性质——TP1（Transformation Property 1）：

对任意并发操作 a 和 b，设 (a', b') = xform(a, b)
则 apply(apply(state, a), b') = apply(apply(state, b), a')

这意味着无论先执行哪个操作，经过变换后，最终状态相同。

看起来很优雅，但问题在于：当并发操作不止两个时，变换函数需要满足更强的性质 TP2，而 TP2 的正确实现极其困难。Sun 和 Ellis 在 1998 年的论文中给出了 TP1 和 TP2 的形式化定义，并证明了当时多个已发表的 OT 算法实际上存在正确性问题。后来 Imine 等人在 2003 年用形式化方法验证了已发表的 OT 算法，发现大量错误。

Google Wave 团队在 2009 年选择了 OT 作为协同编辑的基础。他们的实现避开了 TP2 的复杂性，方法是强制要求所有操作先通过中央服务器排序。服务器维护一个全局操作序列，每个客户端在发送操作前必须先把本地状态同步到服务器的最新版本。这种做法把 OT 从一个去中心化协议退化为一个”客户端-服务器”协议，但换来了正确性保证。

Google Wave 失败了（产品层面），但它的 OT 技术活了下来——Google Docs 沿用了同样的架构。核心设计可以概括为：

客户端将操作发送给服务器
服务器按到达顺序为每个操作分配全局序号
服务器将变换后的操作广播给其他客户端
客户端在接收到确认前缓冲本地操作，收到确认后做变换

这种架构的优势是简单、可控、状态一致。缺点也很明显：必须有一个在线的中央服务器，离线编辑支持非常有限。

1.2 CRDT 的设计哲学

CRDT 走了一条完全不同的路。与其在操作到达时临时做变换，不如从数据结构层面就保证：任意顺序合并操作，结果都相同。

这个性质叫强最终一致性（Strong Eventual Consistency，SEC）：如果两个副本接收了相同的操作集合（不要求顺序相同），它们的状态一定相同。SEC 比最终一致性（Eventual Consistency）更强——后者只保证”最终”会一致，但不保证在操作集合相同时立即一致。

实现 SEC 有两种路径：

CmRDT（operation-based）：操作本身是可交换的。只要每个操作至少被每个副本接收一次，顺序无关。
CvRDT（state-based）：副本状态构成一个半格（semilattice），合并操作是求最小上界（LUB）。LUB 天然满足交换律、结合律、幂等性。

对于文本编辑这个具体问题，直接用通用的 CRDT 集合或寄存器（register）是不够的——文本是一个有序序列，而 CRDT 的研究者需要设计出支持在任意位置插入和删除的序列 CRDT（sequence CRDT）。

最早的序列 CRDT 包括 Treedoc（Preguica 等人，2009）和 RGA（Roh 等人，2011）。它们的共同思路是：给每个字符分配一个全局唯一的标识符（identifier），用标识符的偏序关系来定义字符的顺序，而不是用数组下标。这样插入和删除操作就不需要调整位置——它们直接引用标识符。

1.3 复杂度与正确性对比

OT 和 CRDT 在复杂度上的权衡截然相反。

OT 的复杂度在变换函数。假设有 n 种操作类型，变换函数需要处理 n x n 种组合。对于纯文本（只有 insert 和 delete），这是 4 种组合（insert-insert、insert-delete、delete-insert、delete-delete）。但一旦引入富文本格式（加粗、斜体、字号、颜色……），操作类型爆炸式增长，变换函数的组合数以 O(n^2) 增长。更关键的是，每一种组合都需要被证明满足 TP1（如果没有中央服务器排序，还需要 TP2），而这些证明很容易出错。

CRDT 的复杂度在元数据。每个字符需要携带一个唯一标识符，通常包含节点 ID 和逻辑时钟。此外，删除通常用墓碑（tombstone）实现——字符并不真正删除，而是标记为已删除。这意味着文档的内存占用不仅取决于当前可见内容，还取决于历史上所有被删除的字符数量。对于一个经历了大量编辑的文档，墓碑可能占据绝大部分内存。

用一张表来总结：

维度	OT	CRDT
网络拓扑	通常需要中央服务器	点对点、无中心
操作复杂度	O(n^2) 变换矩阵	O(1) 本地操作（但需要查找插入位置）
元数据开销	低（只传操作）	高（每字符带标识符）
正确性证明	极难（TP1/TP2）	相对容易（数学性质）
离线编辑	困难	天然支持
撤销/重做	需要逆变换	需要额外机制

1.4 从学术到工程的转折点

OT 在 2010 年之前几乎垄断了协同编辑的工业实践。Google Docs、Etherpad、CKEditor 的协同模块都基于 OT。OT 的中央服务器架构在互联网 SaaS 产品中是自然的选择——反正你的文档已经存在服务器上了，多一个变换引擎的成本可以接受。

但从 2015 年开始，CRDT 在工程实践中的份额快速增长。推动力来自几个方向：

本地优先（local-first）软件理念兴起：Ink & Switch 的 “Local-first software” 宣言（2019）明确提出用 CRDT 作为数据同步层
Yjs 库的成熟：Kevin Jahns 在 2015 年发布 Yjs，到 2019 年已经成为 JavaScript 生态中最成熟的协同编辑基础设施
Figma 的成功：Figma 在 2019 年的技术博客中披露了其 CRDT 架构，证明 CRDT 可以支撑大规模商业产品

二、Yjs 深度分析

Yjs 是目前 JavaScript 生态中使用最广泛的 CRDT 协同编辑库。它的核心算法叫 YATA（Yet Another Transformation Approach），由 Kevin Jahns 和 Petru Nicolaescu 等人在 2016 年发表。

2.1 YATA 算法原理

YATA 的核心问题是：当两个用户同时在同一位置插入字符时，谁排在前面？

序列 CRDT 需要一个确定性的规则来解决这种冲突。YATA 的规则基于左右邻居约束（left-right neighbor constraint）：

每个插入操作记录三个信息： 1. 要插入的内容 2. 左邻居（origin left）：插入时这个字符左边是谁 3. 右邻居（origin right）：插入时这个字符右边是谁

当两个并发插入操作的左邻居相同时（也就是它们在同一个位置插入），YATA 用以下规则决定顺序：

比较两个操作的左邻居。如果不同，按左邻居在文档中的位置排序。
如果左邻居相同，比较创建者的客户端 ID（client ID）。ID 小的排在前面。

这个规则的关键性质是：它只依赖操作本身的元数据，不依赖操作到达的顺序。无论操作以什么顺序被接收，最终排列结果都一样。

用伪代码表示 YATA 的插入冲突解决：

function integrateInsert(newItem: Item, doc: Document): void {
  let left = newItem.originLeft;
  let right = newItem.originRight;

  // 从左邻居开始向右扫描，找到正确的插入位置
  let cursor = left;
  let scanning = true;

  while (scanning) {
    let next = cursor.right;
    if (next === right) {
      // 到达右邻居，插入位置确定
      scanning = false;
    } else if (next.originLeft === newItem.originLeft) {
      // 与当前项冲突：左邻居相同
      if (next.clientId < newItem.clientId) {
        // 对方 ID 更小，排在前面，继续向右
        cursor = next;
      } else {
        // 自己 ID 更小或相等，插入到这里
        scanning = false;
      }
    } else if (next.originLeft !== newItem.originLeft) {
      // next 的左邻居不同，跳过
      cursor = next;
    }
  }

  // 在 cursor 之后插入 newItem
  insertAfter(cursor, newItem);
}

这个算法的时间复杂度在最坏情况下是 O(n)，其中 n 是文档长度。但在实际使用中，冲突插入的数量通常很少，平均复杂度接近 O(1)。

并发插入的冲突解决示例

用一个具体场景来说明 YATA 的冲突解决过程。假设文档当前内容是 “ab”，由三个 Item 组成：a（ID: (1,0)）和 b（ID: (1,1)）。用户 A（clientId=2）和用户 B（clientId=3）同时在位置 2（即 a 和 b 之间）插入字符。用户 A 插入 “X”，用户 B 插入 “Y”。两个操作的 originLeft 都是 a，originRight 都是 b——这正是 YATA 需要解决的冲突。

sequenceDiagram
    participant A as 用户 A（clientId=2）
    participant Doc as 文档状态
    participant B as 用户 B（clientId=3）

    Note over Doc: 初始状态："ab"

    A->>A: 本地插入 "X" 在位置 2<br/>ID=(2,0), originLeft=a, originRight=b
    B->>B: 本地插入 "Y" 在位置 2<br/>ID=(3,0), originLeft=a, originRight=b

    Note over A: 本地状态："aXb"
    Note over B: 本地状态："aYb"

    A->>B: 同步操作：插入 "X"
    B->>A: 同步操作：插入 "Y"

    Note over B: 收到 "X"（ID=(2,0)）<br/>与本地 "Y"（ID=(3,0)）冲突<br/>originLeft 相同，比较 clientId<br/>2 < 3，所以 "X" 排在 "Y" 前面
    Note over A: 收到 "Y"（ID=(3,0)）<br/>与本地 "X"（ID=(2,0)）冲突<br/>originLeft 相同，比较 clientId<br/>2 < 3，所以 "X" 排在 "Y" 前面

    Note over Doc: 最终状态："aXYb"<br/>两端收敛到相同结果

上图展示了 YATA 算法解决并发插入冲突的完整过程。当两个用户在同一位置插入不同字符时，两端都会检测到 originLeft 相同的冲突，然后通过比较 clientId 来确定全局一致的顺序。由于 clientId 是全局唯一的，这个比较结果在所有副本上都是确定性的，保证了最终收敛。这种设计的关键洞见是：不需要中央协调者，仅凭本地信息（ID 比较）就能在所有节点上得出相同的排序结论。

2.2 Yjs 数据模型

Yjs 的内部数据模型由三个核心概念组成：

Item 是最基本的单元。每个 Item 有一个唯一的 ID，由 (clientId, clock) 组成。clientId 是每个客户端启动时生成的随机数，clock 是该客户端的逻辑时钟（Lamport clock 的变种），每执行一个操作递增。Item 还包含内容（content）、左邻居 ID（originLeft）和右邻居 ID（originRight）。

Block 是 Yjs 的压缩单元。连续的、由同一个客户端插入的字符会被合并成一个 Block。例如，用户连续输入 “hello”，Yjs 不会创建 5 个 Item，而是创建 1 个 Block，ID 为 (clientId, startClock)，长度为 5。这个优化极大地减少了内存占用。

interface Item {
  id: { client: number; clock: number };
  length: number;
  content: string;       // 对于 Block，可能是多个字符
  originLeft: ItemId | null;
  originRight: ItemId | null;
  deleted: boolean;      // 墓碑标记
  parent: AbstractType;  // 所属的 Y.Array / Y.Map / Y.Text
}

Document（Y.Doc） 是顶层容器。一个 Y.Doc 包含多个共享类型（shared type），如 Y.Text、Y.Array、Y.Map、Y.XmlFragment。每个共享类型维护自己的 Item 双向链表。

Yjs 的共享类型支持嵌套。一个 Y.Map 的值可以是另一个 Y.Map 或 Y.Array，这使得它可以表达复杂的文档结构——比如一个包含嵌套列表、表格、图片的富文本文档。

2.3 编码格式与压缩

Yjs 的持久化和网络传输使用自定义的二进制编码格式，而不是 JSON。这个编码格式做了大量压缩优化：

变长整数编码（Variable-length integer encoding）：小数值只用 1 字节，大数值才用多字节。
Block 合并：连续的同客户端插入合并为一个 Block，只记录起始 clock 和长度。
增量编码（Delta encoding）：客户端 ID 和 clock 用增量方式编码，相邻 Item 的 ID 差值通常很小。
客户端 ID 压缩：文档中出现的客户端 ID 集合通常很小（几个到几十个），Yjs 用一个查找表（lookup table）将长 ID 映射为短索引。

实际效果：一个包含 259778 次单字符编辑操作的文档（Martin Kleppmann 的 automerge-perf 测试数据集），Yjs 编码后的文档大小约为 160 KB，而原始文本只有约 100 KB。额外开销约 60%，这对于一个完整记录了所有编辑历史的 CRDT 来说是相当紧凑的。

2.4 网络层

Yjs 的设计将 CRDT 核心算法和网络传输完全解耦。它通过 Provider 机制支持多种网络层：

y-websocket 是最常用的 Provider。它实现了一个简单的客户端-服务器架构：一个 WebSocket 服务器充当广播中继（relay），所有客户端连接到服务器，服务器将一个客户端的更新（update）转发给其他客户端。服务器本身不需要理解 CRDT 数据结构——它只是一个消息中继。

import * as Y from 'yjs';
import { WebsocketProvider } from 'y-websocket';

const doc = new Y.Doc();
const provider = new WebsocketProvider(
  'wss://my-server.example.com',
  'my-document-room',
  doc
);

const text = doc.getText('content');
text.insert(0, 'Hello, World!');

y-webrtc 实现了真正的点对点通信。客户端之间通过 WebRTC DataChannel 直接交换更新，不需要中央服务器（但仍然需要一个信令服务器来建立 WebRTC 连接）。

y-indexeddb 提供了本地持久化。文档状态存储在浏览器的 IndexedDB 中，断网后重新连接时可以从本地状态恢复，只需要同步差量更新。

这种分层设计的好处是显而易见的：同一个 Yjs 文档可以同时使用 y-websocket 做在线协同，用 y-indexeddb 做离线缓存，两者互不干扰。

2.5 实际性能数据

以 Martin Kleppmann 发布的 editing-traces 数据集中的 “automerge-paper” trace 为参考（记录了一篇学术论文的完整编辑历史，共 259778 次操作），Yjs 的性能表现如下：

加载时间：将完整编辑历史回放（replay）为文档状态约需 550 毫秒
编码后文档大小：约 160 KB
内存占用：加载后的文档对象约 3.5 MB
单次插入操作：亚微秒级
两文档合并：取决于差异大小，通常在毫秒级

这些数据来自 Kevin Jahns 在 2020 年发布的 benchmark。需要注意的是，性能会随着文档编辑历史的增长而下降——一个经历了百万次编辑的文档，回放时间和内存占用都会显著增加。

三、Automerge 深度分析

Automerge 由 Martin Kleppmann（剑桥大学）发起，是学术界推动的 CRDT 库。它的目标不仅是协同文本编辑，而是提供一个通用的 CRDT JSON 文档模型——你可以用它来同步任何 JSON 结构的数据。

3.1 RGA 基础

Automerge 的序列 CRDT 基于 RGA（Replicated Growable Array）算法，由 Roh 等人在 2011 年提出。RGA 的核心思想是用一棵因果排序树（causal tree）来表示序列：

每个字符是树中的一个节点
每个节点有一个唯一 ID (counter, actorId)
当用户在字符 A 后面插入字符 B 时，B 成为 A 的子节点
同一个父节点的子节点按 (counter, actorId) 降序排列（最新的排最前面）

遍历这棵树（深度优先，先访问子节点再访问兄弟节点）就得到文档的线性顺序。

RGA 与 YATA 的主要区别在于冲突解决规则。YATA 用左右邻居约束和客户端 ID 来排序；RGA 用因果关系（counter 更大的排在前面）和 actorId 来排序。两者都能保证强最终一致性，但在并发插入时生成的顺序可能不同。

type RGANode struct {
    ID        OpID       // (counter, actorId)
    Value     rune       // 字符内容，0 表示墓碑
    Parent    *OpID      // 父节点 ID
    Children  []*RGANode // 子节点列表，按 ID 降序
    Deleted   bool
}

type OpID struct {
    Counter int
    ActorID string
}

// 插入操作：在 parent 的子节点列表中找到正确位置
func (node *RGANode) InsertChild(child *RGANode) {
    pos := 0
    for pos < len(node.Children) {
        existing := node.Children[pos]
        if child.ID.Counter > existing.ID.Counter {
            break
        }
        if child.ID.Counter == existing.ID.Counter &&
           child.ID.ActorID > existing.ID.ActorID {
            break
        }
        pos++
    }
    // 在 pos 位置插入 child
    node.Children = append(node.Children, nil)
    copy(node.Children[pos+1:], node.Children[pos:])
    node.Children[pos] = child
}

3.2 Columnar 压缩编码

Automerge 1.0 的一个主要性能问题是存储效率。每个操作都被完整地存储为一个 JSON-like 对象，包含操作类型、Actor ID、计数器、值等字段。这导致编码后的文档大小远大于原始文本。

Automerge 2.0 引入了 Columnar 压缩编码（columnar encoding）来解决这个问题。核心思路借鉴了列式存储（columnar storage）数据库的做法：

不再把每个操作存储为一个完整的记录（行式存储），而是把操作的每个字段分别存储为一个列。例如：

所有操作的 actorId 存在一个列中
所有操作的 counter 存在一个列中
所有操作的 value 存在一个列中

每个列再分别做压缩。由于同一列中的数据类型相同，压缩效果远好于行式存储：

actorId 列：大部分操作来自少数几个 actor，使用 run-length encoding（RLE）压缩极其有效
counter 列：counter 通常是连续递增的，使用 delta encoding 后每个值只需要 1 个字节
value 列：连续输入的字符存储为一个字符串，不需要逐字符存储

这项优化的效果非常显著。以 automerge-paper 数据集为例，Automerge 2.0 编码后的文档大小从 1.0 版本的数 MB 降低到约 200 KB 左右，接近 Yjs 的水平。

3.3 Automerge 2.0 架构改进

Automerge 2.0 是一次彻底的重写。核心引擎从 JavaScript 迁移到 Rust，通过 WebAssembly（WASM）暴露给 JavaScript 使用。这带来了几个关键改进：

性能：Rust 的原生性能远超 JavaScript，尤其是在处理大量操作时。文档加载时间从秒级降低到毫秒级。
内存管理：Rust 的所有权模型消除了 JavaScript 的垃圾回收开销。对于长时间运行的协同编辑会话，这意味着更稳定的内存使用。
跨语言支持：Rust 核心可以编译为 WASM（给浏览器和 Node.js），也可以直接作为原生库被 Swift（iOS）、Kotlin（Android）、C（嵌入式）调用。一套代码，多平台运行。
增量保存：Automerge 2.0 支持增量保存（incremental save）。你不需要每次保存整个文档，只需要保存自上次保存以来的新操作。这对大型文档非常重要。

use automerge::{AutoCommit, ObjType, ReadDoc, transaction::Transactable};

fn main() {
    let mut doc = AutoCommit::new();

    // 创建一个文本对象
    let text = doc.put_object(automerge::ROOT, "content", ObjType::Text)
        .unwrap();

    // 插入文本
    doc.splice_text(&text, 0, 0, "Hello, World!").unwrap();

    // 保存为二进制
    let saved = doc.save();
    println!("Document size: {} bytes", saved.len());

    // 从另一个副本加载
    let mut doc2 = AutoCommit::load(&saved).unwrap();

    // 并发修改
    doc.splice_text(&text, 5, 0, " beautiful").unwrap();
    doc2.splice_text(&text, 7, 6, "Rust").unwrap();

    // 合并
    doc.merge(&mut doc2).unwrap();
}

3.4 OpSet 与 Change 的关系

理解 Automerge 的内部结构需要区分两个概念：

OpSet 是文档当前状态的完整表示。它包含文档中所有操作（包括已被覆盖的和标记为删除的），并维护它们之间的因果关系。OpSet 是一个不可变的数据结构——你不能修改已有的操作，只能添加新操作。

Change 是一组原子操作的集合。当用户执行一次修改（比如输入一段文字），Automerge 将这次修改打包为一个 Change。每个 Change 包含：

一组操作（ops）
该 Change 的因果依赖（dependencies）：一个 Change 哈希值的列表，表示创建这个 Change 时，本地已经知道了哪些其他 Change
Actor ID 和序列号

Change 之间的依赖关系形成一个有向无环图（DAG）。这个 DAG 就是文档的编辑历史。两个独立的分支（没有因果关系的 Change）代表并发编辑。合并操作就是把两个分支的 DAG 合并为一个，并按照 CRDT 的规则解决冲突。

这种设计使得 Automerge 的同步协议非常简洁：两个副本交换各自缺少的 Change 即可。因为 Change 的 DAG 结构天然支持增量同步——只需要发送对方没有的那些 Change。

四、Diamond Types

Diamond Types 是 Joseph Gentle（Seph Gentle）开发的高性能序列 CRDT 实现，完全用 Rust 编写。它的设计目标是成为最快的文本 CRDT。

4.1 Rust 高性能实现

Diamond Types 的性能优势来自几个设计决策：

紧凑的内存布局。Diamond Types 不使用指针链表来表示文档结构，而是使用紧凑的数组和 B-tree。这对 CPU 缓存非常友好——遍历文档时不需要在内存中跳来跳去，而是顺序访问连续内存。

最小化元数据。每个操作只存储必要的信息：操作类型（插入或删除）、位置、内容、Lamport 时间戳、Agent ID。不存储冗余的邻居引用。

批量操作优化。连续的单字符插入（这在文本编辑中是最常见的模式——用户逐个字符输入）被合并为一个操作。Diamond Types 在这方面做得比 Yjs 和 Automerge 更激进：它不仅合并连续插入，还合并连续删除，甚至跨操作合并。

位置映射加速。文本 CRDT 的一个核心操作是”把字符的唯一 ID 映射到当前文档中的位置”。Diamond Types 使用一棵自平衡的 B-tree 来维护这个映射，使得查找和更新操作都是 O(log n)，而朴素实现需要 O(n)。

// Diamond Types 的核心数据结构（简化）
struct ListCRDT {
    // 用 B-tree 维护文档中的字符，叶子节点是连续字符块
    content: ContentTree,
    // 操作日志，用于同步
    ops: Vec<Op>,
    // Agent ID 到本地索引的映射
    agents: Vec<AgentId>,
    // Frontier：当前已知的最新操作集合（DAG 的叶子）
    frontier: Vec<OpId>,
}

struct Op {
    kind: OpKind,        // Insert 或 Delete
    id: OpId,            // (agent, seq)
    origin_left: OpId,   // 插入位置的左邻居
    origin_right: OpId,  // 插入位置的右邻居
    content: SmallVec<u8>, // UTF-8 编码的内容
}

4.2 与 Automerge 的性能对比

Joseph Gentle 在 2022 年发布了详尽的 benchmark 对比。以 editing-traces 数据集为基准：

指标	Diamond Types	Automerge 2.0	Yjs
回放全部操作	~4 ms	~70 ms	~550 ms
编码后文档大小	~110 KB	~200 KB	~160 KB
内存占用（加载后）	~1 MB	~3 MB	~3.5 MB
合并两个完整副本	~3 ms	~50 ms	~20 ms

Diamond Types 在几乎所有指标上都大幅领先。但需要注意几个背景：

Diamond Types 是一个专注于文本的 CRDT，不像 Automerge 那样提供通用的 JSON 数据模型。功能范围小意味着可以做更极致的优化。
Yjs 的数据是纯 JavaScript 实现的数据，Automerge 2.0 已经迁移到 WASM。如果 Yjs 也做 WASM 迁移，差距会缩小。
这些 benchmark 测试的是”回放完整编辑历史”这个场景，实际使用中更多是增量更新，性能差异没有这么大。

4.3 设计决策

Diamond Types 做了一些值得关注的设计取舍：

不存储墓碑。与 Yjs 和 Automerge 不同，Diamond Types 不在文档状态中维护已删除字符的墓碑。删除操作只记录在操作日志中。当需要合并远端操作时，通过回放操作日志来重建必要的上下文。这大幅减少了常驻内存占用，代价是合并操作需要更多计算。

使用 Fugue 算法。Diamond Types 在最新版本中采用了 Fugue 算法（由 Matthew Weidner 在 2023 年提出），取代了之前使用的类 YATA 算法。Fugue 的核心创新是引入了”最大化非交错”（maximal non-interleaving）性质：当两个用户同时在同一位置输入一段文字时，Fugue 保证两段文字不会字符级交错，而是一段排在另一段前面。这更符合用户的直觉预期。

时间旅行。Diamond Types 的操作日志天然支持”时间旅行”——你可以回到文档的任意历史状态，而不需要额外的版本管理机制。这对于需要”查看文档在某个时刻的样子”的应用非常有用。

五、性能对比与 Benchmark

5.1 editing-traces 数据集

Martin Kleppmann 发起的 editing-traces 项目收集了真实的文本编辑操作序列，成为 CRDT 性能评测的事实标准。数据集包含几个代表性的 trace：

automerge-paper：Martin Kleppmann 编写 Automerge 论文时的编辑记录，259778 次操作
seph-blog1：Joseph Gentle 编写一篇博客时的编辑记录，约 35000 次操作
rustcode：一段 Rust 代码的编辑记录，约 60000 次操作
sveltecomponent：一个 Svelte 组件的编辑记录

这些数据集的特征是：绝大部分操作是顺序的单字符插入和删除（符合人类打字习惯），只有少量并发操作（来自协同编辑者）。这意味着批量压缩（run merging）对性能影响巨大。

5.2 内存占用对比

内存占用是 CRDT 在实际应用中最受关注的指标之一。以 automerge-paper trace 为例：

最终文档的纯文本大小约 100 KB。但 CRDT 需要额外存储：

每个字符的唯一标识符：至少 8 字节（4 字节 client ID + 4 字节 clock）
邻居引用：每个 Item 需要 8-16 字节的左右邻居引用
墓碑：所有被删除的字符也需要保留在内存中

不同实现的内存优化程度差异显著：

Yjs：通过 Block 合并，将连续字符压缩为一个结构体。automerge-paper trace 加载后占用约 3.5 MB
Automerge 2.0：WASM 实现，内部使用 Columnar 编码的 OpSet。加载后占用约 3 MB
Diamond Types：不存储墓碑，使用 B-tree。加载后占用约 1 MB

对比来看，一个朴素的纯文本编辑器只需要约 100 KB 内存。CRDT 的内存开销是 10 倍到 35 倍，这是为了获得离线编辑和去中心化合并能力而付出的代价。

5.3 Merge 速度对比

合并（merge）是 CRDT 的核心操作。当两个离线编辑的副本重新连接时，需要合并各自的修改。合并速度取决于：

两个副本之间的差异大小
冲突（同一位置的并发修改）的数量
实现的算法效率

在 automerge-paper trace 上，从零开始合并完整文档（最坏情况）的性能：

实现	合并时间
Diamond Types	~3 ms
Yjs	~20 ms
Automerge 2.0	~50 ms

在实际场景中，增量合并（只同步新操作）通常在亚毫秒级完成，用户几乎感知不到延迟。

5.4 文档大小对比

持久化后的文档大小影响存储成本和传输速度。各实现的编码效率对比：

实现	编码后大小	纯文本大小	开销比
Diamond Types	~110 KB	~100 KB	1.1x
Yjs	~160 KB	~100 KB	1.6x
Automerge 2.0	~200 KB	~100 KB	2.0x

Diamond Types 的编码后大小几乎等于纯文本大小，这得益于它不存储墓碑、不存储冗余元数据的设计。

六、实际产品案例

6.1 Google Docs：OT 架构

Google Docs 是全球使用最广泛的协同编辑产品。它的架构基于 OT，具体来说是 Jupiter 协议（Nichols 等人，1995）的变种。

核心架构：

中央服务器维护权威版本。每个文档有一个 Google 服务器负责维护其权威状态和操作历史。
客户端本地预测。用户的编辑操作立即在本地应用（乐观更新），同时发送给服务器。这保证了零延迟的本地编辑体验。
服务器排序与变换。服务器按接收顺序为操作分配全局序号。如果客户端的操作基于过时的版本，服务器对其做变换后再应用。
确认与回退。客户端在收到服务器确认前，缓冲后续操作。如果服务器返回了不同于本地预测的结果（因为有其他用户的并发操作被变换了），客户端回退本地预测并重新应用变换后的操作。

这个架构的优势：

简单可控：服务器有绝对权威，不需要处理复杂的分布式一致性问题
带宽效率高：只传输操作（operation），不传输状态。一个 insert 操作只需要几十字节
历史记录天然存在：服务器的操作日志就是完整的编辑历史，支持版本回溯和查看修改记录

这个架构的限制：

强依赖服务器：没有网络就不能协同编辑。Google Docs 的离线模式实际上是一个独立的本地编辑器，重新上线后通过一个复杂的同步流程合并离线修改
单点瓶颈：热门文档的所有操作都必须经过同一个服务器，尽管 Google 的基础设施可以承受，但对于小公司来说这是一个扩展性瓶颈
扩展操作类型成本高：每增加一种新的操作类型（比如新的格式化指令），变换函数的工作量按 O(n^2) 增长

6.2 Figma：CRDT 架构

Figma 是一个在线设计工具，2019 年在技术博客中披露了其协同编辑架构的核心思路。

Figma 的数据模型不是纯文本——它是一棵设计元素树，每个元素有大量属性（位置、尺寸、颜色、层级……）。对于这种结构，Figma 选择了一种”属性级 Last-Writer-Wins”（LWW）的 CRDT 策略：

每个设计元素是一个 CRDT 对象，有一个全局唯一 ID
每个属性是一个 LWW 寄存器：并发修改同一属性时，时间戳最大的那个写入生效
元素的父子关系（层级结构）用一个序列 CRDT 管理：谁是谁的子节点、子节点的顺序

这种设计非常适合设计工具的使用模式：两个设计师同时修改同一个按钮的颜色是极少见的冲突场景；更常见的是各自修改不同的元素，这时候完全没有冲突。

Figma 的架构有一个重要特点：虽然用了 CRDT，但它仍然使用一个中央服务器。服务器的作用不是做变换（不需要，CRDT 天然收敛），而是：

中继消息：充当 WebSocket 中继，在客户端之间转发操作
持久化：存储文档的最新状态和操作日志
权限控制：验证用户是否有权限修改特定的设计元素
冲突策略覆盖：在某些场景下，服务器可以覆盖 CRDT 的默认合并结果。例如，当两个用户同时删除和移动同一个元素时，服务器可以决定”删除优先”

Evan Wallace（Figma 联合创始人）在技术博客中强调了一个关键观点：选择 CRDT 并不意味着不要服务器。CRDT 给你的是合并的确定性——无论操作以什么顺序到达，结果都一样。服务器仍然可以（也应该）存在，用于持久化、权限控制和作为网络中继。

6.3 架构差异分析

Google Docs 和 Figma 的选择反映了不同的工程权衡：

维度	Google Docs (OT)	Figma (CRDT)
数据模型	富文本流	设计元素树
冲突频率	高（同一段文字）	低（不同元素）
离线需求	低	中
操作类型数量	高（大量格式化操作）	中（属性修改、层级调整）
一致性要求	字符级精确	属性级足够

Google Docs 选择 OT 的一个核心原因是：富文本编辑涉及大量复杂的格式化操作（加粗、斜体、字号、字体、颜色、对齐、缩进……），这些操作之间的交互非常复杂。OT 的变换函数虽然写起来痛苦，但每一种组合都可以被精确控制。CRDT 的自动合并在某些格式化冲突场景下可能产出不符合用户预期的结果。

Figma 选择 CRDT 的原因则相反：设计元素之间的独立性很强，并发冲突主要发生在属性级别，LWW 策略在大多数情况下就够了。而 CRDT 带来的离线编辑能力和架构简洁性（服务器不需要理解操作语义）是 OT 难以提供的。

七、实际工程挑战

理论上 CRDT 保证了强最终一致性，但把 CRDT 用在真实产品中，还需要解决一系列工程问题。

7.1 Undo/Redo

文本编辑器的用户期望 Ctrl+Z 能撤销自己的最后一个操作，而不影响其他用户的操作。这在 OT 中通过”逆操作”实现（比如 insert 的逆操作是 delete），但在 CRDT 中更复杂。

CRDT 的操作是不可逆的——你不能简单地”撤销”一个插入，因为其他用户可能已经在这个插入的字符旁边做了修改。直接删除这个字符会改变其他用户操作的语义。

Yjs 的解决方案是维护一个”undo stack”：

import * as Y from 'yjs';
import { UndoManager } from 'yjs';

const doc = new Y.Doc();
const text = doc.getText('content');

const undoManager = new UndoManager(text, {
  trackedOrigins: new Set([null]), // 只跟踪本地操作
  captureTimeout: 500,            // 500ms 内的操作合并为一次 undo
});

// 用户输入
text.insert(0, 'Hello');

// Undo: 删除刚才插入的 "Hello"
undoManager.undo();

// Redo: 重新插入 "Hello"
undoManager.redo();

UndoManager 的关键设计：

只跟踪本地操作：通过 trackedOrigins 过滤，只有本地发起的操作才会被记录到 undo stack 中。其他用户的操作不受 undo 影响。
操作合并：用户快速连续输入的字符会被合并为一次 undo 操作。captureTimeout 控制合并窗口。
基于操作的 undo：undo 并不是”回到之前的状态”，而是生成一组新的操作来抵消之前的效果。这些新操作通过正常的 CRDT 同步机制传播给其他用户。

Automerge 目前对 undo/redo 的支持还在发展中。一种方案是在应用层维护操作历史并生成逆操作，但这需要应用开发者自己处理冲突场景。

CRDT 中选择性撤销的深层挑战

在 OT 体系中，撤销相对直接：服务器维护全局操作序列，撤销操作 A 只需生成 A 的逆操作并通过变换函数适配当前状态。但在 CRDT 中，选择性撤销（selective undo）——即撤销某个特定操作而不影响其后发生的操作——是一个本质上更困难的问题。

意图保持（intention preservation）问题。 假设用户 A 在位置 5 插入 “hello”，随后用户 B 在 “hello” 的后面插入 “world”。现在用户 A 想撤销自己的插入。如果简单地删除 “hello”，那么 “world” 的位置语义就被改变了——B 的意图是在 “hello” 后面插入，而不是在位置 5 插入。更极端的情况是：B 在 “hello” 中间插入了字符，撤销 A 的操作后这些字符应该如何处理？OT 可以通过变换函数逐一调整后续操作的位置，但 CRDT 的操作一旦被整合进数据结构就不可逆——每个 Item 的 originLeft 和 originRight 指向的是插入时的邻居，而不是当前的邻居。

墓碑复活问题。 CRDT 使用墓碑标记来处理删除。当用户撤销一个删除操作时，对应的墓碑需要被”复活”——从 deleted=true 变回 deleted=false。但如果在这个删除操作和撤销操作之间，其他用户也独立地删除了同一个字符，那么复活就会违反其他用户的删除意图。两个用户各自删除了同一个字符，其中一个撤销了自己的删除，这个字符是否应该重新出现？从 A 的视角看应该出现，从 B 的视角看不应该。这个语义冲突没有标准答案。

两种主流方案的对比：

基于效果的撤销（effect-based undo）：记录操作产生的可观察效果（比如”这些字符被插入了”或”这些字符被删除了”），撤销时生成抵消效果的新操作。Yjs 的 UndoManager 基本采用这种方式——它记录哪些 Item 被创建或删除，撤销时反向操作。优点是实现相对简单，缺点是在复杂的并发场景下可能无法完美保持意图。
基于历史的撤销（history-based undo）：维护完整的操作历史，撤销时重建一个”如果这个操作从未发生过”的状态。这在理论上最符合直觉，但计算成本极高——需要在 CRDT 的操作历史图上做因果推理，判断哪些后续操作依赖于被撤销的操作。在实际工程中几乎不可行，因为操作之间的依赖关系可能非常复杂。

目前工业实践中的共识是：对于协同编辑场景，effect-based undo 配合”只撤销本地操作”的限制是最实用的折衷方案。全局的选择性撤销（撤销任意用户的任意历史操作）仍然是一个开放问题。

7.2 权限控制

CRDT 的去中心化特性与权限控制存在天然的矛盾。在纯 CRDT 架构中，每个节点都可以生成操作并传播给其他节点——没有一个中心权威来验证”这个用户是否有权限执行这个操作”。

实际产品中通常采用混合架构来解决这个问题：

中继服务器过滤：所有操作都通过一个中继服务器传播。服务器在转发操作之前检查发送者的权限。未授权的操作被丢弃。这种方案简单有效，但违反了 CRDT 的去中心化理念。
签名验证：每个操作附带创建者的数字签名。接收方验证签名后决定是否应用。这保留了去中心化架构，但增加了计算开销和密钥管理的复杂性。
分层文档结构：将文档拆分为多个独立的 CRDT 对象，每个对象有独立的权限规则。例如，一个文档的”正文”部分所有人可编辑，但”标题”部分只有所有者可修改。每个部分是一个独立的 Y.Text 或 Y.Map，权限在同步层检查。

Figma 采用的是第一种方案：CRDT 负责合并逻辑，服务器负责权限检查。这是目前工业实践中最常见的方案。

7.3 离线支持

离线编辑是 CRDT 相对于 OT 的最大优势之一。用户在离线状态下做的所有修改都记录在本地的 CRDT 副本中，重新上线后只需要同步差量。

但”离线支持”在工程上远不止”操作能合并”这么简单。需要考虑的问题包括：

存储管理。长时间离线编辑会产生大量操作日志。如何限制本地存储的大小？何时可以安全地压缩（compact）操作日志？压缩后是否还能与其他离线节点合并？

Yjs 的 encodeStateAsUpdate 和 applyUpdate API 支持增量同步。两个副本通过交换”状态向量”（state vector）来确定对方缺少哪些操作，然后只发送差量：

import * as Y from 'yjs';

const doc1 = new Y.Doc();
const doc2 = new Y.Doc();

// doc1 做了一些编辑
const text1 = doc1.getText('content');
text1.insert(0, 'Hello from doc1');

// doc2 离线做了另一些编辑
const text2 = doc2.getText('content');
text2.insert(0, 'Hello from doc2');

// 重新连接后，交换状态向量
const sv1 = Y.encodeStateVector(doc1);
const sv2 = Y.encodeStateVector(doc2);

// 只发送对方缺少的操作
const update1to2 = Y.encodeStateAsUpdate(doc1, sv2);
const update2to1 = Y.encodeStateAsUpdate(doc2, sv1);

// 双方应用差量更新
Y.applyUpdate(doc2, update1to2);
Y.applyUpdate(doc1, update2to1);

// 此时 doc1 和 doc2 状态一致

冲突通知。CRDT 的合并是自动的，但自动合并的结果可能不是用户期望的。例如，两个用户离线时都修改了同一段文字，上线后 CRDT 会把两段修改都保留下来（一前一后拼接），而用户可能期望被提示”有冲突，请选择保留哪个版本”。应用层需要在自动合并的基础上，添加冲突检测和通知机制。

数据完整性。长时间离线可能导致本地数据损坏（浏览器 IndexedDB 出错、磁盘故障等）。需要对本地 CRDT 状态做校验和（checksum）验证，在检测到损坏时回退到服务器版本。

7.4 富文本与嵌套结构

纯文本的 CRDT 已经相当成熟。但富文本编辑涉及格式标记（formatting marks），这比纯文本复杂得多。

考虑这个场景：用户 A 将 “hello” 加粗（bold），用户 B 同时将 “hello” 加斜体（italic）。合并后，“hello” 应该是加粗且斜体。这看起来简单，但当格式标记覆盖的范围不完全重叠时，问题就复杂了。

例如：文档内容是 “hello world”。用户 A 将 “hello w” 加粗。用户 B 将 “o world” 加斜体。合并后应该是：

“hell” 是加粗
“o w” 是加粗且斜体
“orld” 是斜体

Peritext（Litt 等人，2022）是第一个系统性解决富文本 CRDT 格式化问题的研究工作。它提出了几个关键概念：

标记锚点（mark anchors）：格式标记不是附加在字符上的属性，而是锚定在字符之间的间隙上。这样当有新字符插入到格式范围的边界时，格式的行为是确定性的。
扩展行为（expansion behavior）：当在加粗文本的末尾插入新字符时，新字符应该也是加粗的（“扩展”行为）。但当在加粗文本的旁边（但在范围之外）插入字符时，新字符不应该加粗。Peritext 用”before/after”锚点来区分这两种情况。
格式优先级：当多个用户并发地对同一范围应用不同格式时，需要一个确定性的规则来决定最终效果。Peritext 使用 Lamport 时间戳来排序，最新的格式操作生效。

Yjs 对富文本的支持通过 Y.XmlFragment 和与 ProseMirror、TipTap、Quill 等富文本编辑器框架的绑定来实现。这些绑定将编辑器的 Delta（如 Quill Delta）或 Transaction（如 ProseMirror Transaction）翻译为 Yjs 操作。

import * as Y from 'yjs';
import { QuillBinding } from 'y-quill';
import Quill from 'quill';

const doc = new Y.Doc();
const ytext = doc.getText('quill');

const quill = new Quill('#editor', {
  theme: 'snow',
  modules: { toolbar: true },
});

const binding = new QuillBinding(ytext, quill);

嵌套结构（如列表中的列表、表格中的段落）进一步增加了复杂度。Yjs 通过 Y.XmlFragment 和 Y.XmlElement 提供了树形结构的 CRDT 支持，但树形 CRDT 的并发语义（比如两个用户同时移动同一个节点到不同的父节点下）仍然是一个活跃的研究领域。

富文本格式冲突的解决流程

当两个用户并发地对同一段文本应用不同的格式时，CRDT 需要一个确定性的规则来合并格式属性。以下流程展示了这个解决过程：

flowchart TD
    A["用户 A 对 'hello' 应用 bold=true"] --> C{"两个格式操作的<br/>作用范围是否重叠？"}
    B["用户 B 对 'hello' 应用 italic=true"] --> C

    C -->|"不重叠"| D["各自独立生效<br/>无需冲突解决"]
    C -->|"重叠"| E{"格式属性<br/>是否相同？"}

    E -->|"不同属性<br/>（如 bold vs italic）"| F["属性合并：<br/>bold=true, italic=true<br/>两者同时生效"]
    E -->|"相同属性<br/>（如都设置 color）"| G{"比较 Lamport<br/>时间戳"}

    G --> H["时间戳较大的操作生效<br/>时间戳相同则比较 clientId"]
    H --> I["所有副本得到<br/>相同的最终格式"]
    F --> I
    D --> I

该流程图展示了富文本 CRDT 解决格式冲突的三种情况：范围不重叠时直接独立生效；不同属性重叠时合并（这是最常见的场景，如同时加粗和斜体）；相同属性冲突时通过 Lamport 时间戳决定胜者。最后一种情况——两个用户把同一段文字设置为不同颜色——是最需要确定性规则的地方，Peritext 通过”最后写入者胜出”（last-writer-wins）语义来解决，但使用 Lamport 时间戳而非物理时钟来定义”最后”。

富文本 CRDT 实现方案对比

在序列 CRDT 之上叠加富文本格式支持，不同框架采取了截然不同的策略，各有优劣：

Yjs 的方案：编辑器绑定层处理格式。 Yjs 本身的核心数据结构（Y.Text）支持带属性的文本——每个字符可以携带一组键值对属性（如 {bold: true, color: 'red'}）。格式操作被翻译为对字符属性的修改。并发的属性修改遵循 last-writer-wins 语义。这种方案的优点是实现简单，与 Quill、ProseMirror 等编辑器的集成度高。缺点是格式语义完全依赖应用层：Yjs 不理解”加粗”的含义，它只知道某个属性被设置或清除了。当两个用户对部分重叠的范围做格式化时，边界行为取决于编辑器绑定的实现，而不是 CRDT 本身。

Automerge 的方案：块级标记（block markers）。 Automerge 将富文本建模为带有嵌入式标记的字符序列。格式标记本身也是序列中的元素，拥有自己的 CRDT ID。这使得格式标记的并发插入和删除能够利用已有的序列 CRDT 算法来解决。但块级标记的方案在处理”扩展行为”时存在歧义——在加粗文本末尾插入新字符时，新字符是否应该继承加粗格式？这取决于标记的锚定策略，而 Automerge 的早期版本在这方面没有统一规范。

Peritext 的方案：学术界的系统性解决。 Peritext 是目前在理论层面最完整的富文本 CRDT 方案。它明确区分了”添加型标记”（additive marks，如加粗、斜体）和”覆盖型标记”（overriding marks，如字体颜色、字号）。对于添加型标记，并发操作取并集——同时加粗和斜体的结果是两者兼具。对于覆盖型标记，并发操作取”最后写入者胜出”。Peritext 还精确定义了标记的边界行为（before-anchor 和 after-anchor），解决了”在格式范围边界插入新字符时是否继承格式”这个长期困扰富文本 CRDT 的问题。但 Peritext 目前没有生产级实现，其论文中的算法也尚未在大规模场景下验证性能。

三种方案反映了工程实践与学术研究之间的差距：Yjs 选择了实用优先，把复杂语义推给应用层；Automerge 尝试在数据结构层面解决更多问题，但方案仍在演进中；Peritext 提出了理论上最优雅的解决方案，但距离工业落地还有距离。对于大多数产品场景，Yjs 的方案已经足够——只有在需要精确控制并发格式语义（如协同 IDE、协同排版工具）时，才需要考虑 Peritext 级别的方案。

7.5 垃圾回收与文档压缩

CRDT 文档的一个固有问题是元数据只增不减——尤其是墓碑。一个经历了大量编辑的文档，可能有 99% 的 Item 都是墓碑，只有 1% 是可见内容。

垃圾回收（Garbage Collection，GC）是解决这个问题的途径，但在分布式环境中做 GC 非常困难。核心矛盾是：如果一个副本已经删除了某些墓碑，另一个长期离线的副本上线后发来的操作可能引用了这些已删除的墓碑。

Yjs 提供了一个受限的 GC 机制：Y.Doc 的 gc 选项。开启后，Yjs 会删除已标记为删除的 Item 的内容（但保留 Item 的 ID 和结构信息），从而减少内存占用。这是一个折衷方案——它减少了内存，但不完全消除元数据。

const doc = new Y.Doc({ gc: true });

更彻底的 GC 需要所有副本之间达成共识：“这些墓碑可以安全删除了”。这实际上需要一个因果稳定性（causal stability）的判断：当所有副本都已经知道某个删除操作时，对应的墓碑就可以安全回收了。但在去中心化系统中，“所有副本”这个概念本身就是模糊的——你怎么知道世界上不存在一个长期离线的副本？

工程实践中的常见方案是设定一个”离线窗口”（offline window）：如果一个副本离线超过 30 天，就认为它需要做全量同步而不是增量同步。在此假设下，30 天前的墓碑可以安全回收。

CRDT 垃圾回收状态机

墓碑的生命周期可以用一个状态机来精确描述。从活跃状态到最终被回收，一个 Item 需要经过多个阶段，每个阶段的转换都有明确的前置条件：

stateDiagram-v2
    [*] --> Active : 用户插入新字符

    Active --> Tombstone : 用户执行删除操作<br/>（标记 deleted=true）

    Tombstone --> CausallyStable : 所有已知副本都已接收<br/>到该删除操作<br/>（通过状态向量确认）

    CausallyStable --> PruneSafe : 不存在引用此 Item 的<br/>未同步操作<br/>（离线窗口已过期）

    PruneSafe --> Pruned : 执行垃圾回收<br/>（删除 Item 的 ID 和结构信息）

    Pruned --> [*]

    note right of Tombstone : 保留完整的 ID 和结构信息<br/>用于冲突解决
    note right of CausallyStable : 可以安全删除内容数据<br/>但需保留 ID 用于引用
    note right of PruneSafe : 可以完全删除<br/>包括 ID 和结构信息

这个状态机揭示了 CRDT 垃圾回收的核心难点：从 Tombstone 到 CausallyStable 的转换需要全局知识——必须确认所有副本都已经看到了删除操作。在去中心化系统中，这个确认本身就是一个共识问题。而从 CausallyStable 到 PruneSafe 的转换更加保守——即使所有副本都知道了删除操作，仍然可能存在尚未同步的操作引用了该墓碑的 ID（作为 originLeft 或 originRight）。只有当所有这类潜在引用都不可能再出现时，才能安全地回收结构信息。

因果稳定性与无界增长的权衡

CRDT 垃圾回收的本质是在两个对立的目标之间寻找平衡。一方面是因果稳定性保证——过早回收墓碑会导致后续同步时出现”悬空引用”（dangling reference），新到达的操作引用了一个已经不存在的 Item ID，系统无法正确定位插入位置，最终导致文档损坏。另一方面是空间效率——如果永远不回收墓碑，文档的元数据会无限增长。一个活跃编辑了 6 个月的文档，其 CRDT 元数据可能是可见内容大小的 50 到 100 倍。

这个权衡在不同的应用场景下有不同的最优解。对于”始终在线”的场景（如 Google Docs 式的浏览器编辑器），可以依赖中继服务器作为权威副本，定期做 snapshot 并丢弃历史操作——新加入的客户端从 snapshot 开始，不需要完整的操作历史。这实质上是放弃了 CRDT 的去中心化承诺，换取了可控的内存和存储开销。对于”长期离线”的场景（如本地优先应用、移动端笔记工具），激进的 GC 不可行，必须保留足够长的墓碑历史以应对延迟同步。工程实践中通常的做法是分层 GC：先删除墓碑的内容数据（如 Yjs 的 gc: true），保留 ID 和结构信息；等到离线窗口过期后，再删除结构信息并标记为需要全量同步的断点。这种分层策略在不牺牲正确性的前提下，将典型的内存开销降低了 60% 到 80%。

参考文献

Ellis, C.A. & Gibbs, S.J. (1989). “Concurrency control in groupware systems.” ACM SIGMOD Record, 18(2), 399-407. https://dl.acm.org/doi/10.1145/67544.66963
Sun, C. & Ellis, C. (1998). “Operational transformation in real-time group editors: issues, algorithms, and achievements.” Proceedings of the 1998 ACM conference on Computer supported cooperative work, 59-68. https://dl.acm.org/doi/10.1145/289444.289469
Nichols, D.A., Curtis, P., Dixon, M. & Lamping, J. (1995). “High-latency, low-bandwidth windowing in the Jupiter collaboration system.” Proceedings of the 8th annual ACM symposium on User interface and software technology, 111-120. https://dl.acm.org/doi/10.1145/215585.215706
Roh, H.G., Jeon, M., Kim, J.S. & Lee, J. (2011). “Replicated abstract data types: Building blocks for collaborative applications.” Journal of Parallel and Distributed Computing, 71(3), 354-368. https://doi.org/10.1016/j.jpdc.2010.12.006
Nicolaescu, P., Jahns, K., Derntl, M. & Klamma, R. (2016). “Yjs: A Framework for Near Real-Time P2P Shared Editing on Arbitrary Data Types.” Engineering the Web in the Big Data Era, 9114, 484-497. https://doi.org/10.1007/978-3-319-19890-3_31
Kleppmann, M. & Beresford, A.R. (2017). “A Conflict-Free Replicated JSON Datatype.” IEEE Transactions on Parallel and Distributed Systems, 28(10), 2733-2746. https://doi.org/10.1109/TPDS.2017.2697382
Litt, S., Lim, S., Kleppmann, M. & van Hardenberg, P.F. (2022). “Peritext: A CRDT for Collaborative Rich Text Editing.” Proceedings of the ACM on Human-Computer Interaction, 6(CSCW2), 1-36. https://doi.org/10.1145/3555572
Kleppmann, M. (2020). “editing-traces: Real-world editing traces for benchmarking collaborative editing algorithms.” https://github.com/automerge/automerge-perf
Gentle, J. (2022). “Diamond Types: A fast CRDT for plain text editing.” https://github.com/josephg/diamond-types
Jahns, K. (2020). “Are CRDTs suitable for shared editing?” https://blog.kevinjahns.de/are-crdts-suitable-for-shared-editing/
Weidner, M., Kleppmann, M., Lebrecht, D. & Beresford, A.R. (2023). “The Art of the Fugue: Minimizing Interleaving in Collaborative Text Editing.” https://arxiv.org/abs/2305.00583
Wallace, E. (2019). “How Figma’s multiplayer technology works.” https://www.figma.com/blog/how-figmas-multiplayer-technology-works/

上一篇：CRDT 类型目录下一篇：Delta-state CRDT 与反熵优化