构建分布式协同系统 —— CRDT 数据建模哲学
Writing with Gemini
TL;DR;
Schema 设计并非只是简单的 CRUD 映射，而应该基于 CRDT 特性对业务逻辑进行深度抽象：
- Map-Reduce 结构：利用
Map确立数据主权，利用Array定义视图投影。 - 读写分离：将用户输入的“因”（Source）与系统生成的“果”（Output）在物理存储上隔离。
- 软删除：通过状态标记代替物理销毁，保障并发安全性。
这一坚固的数据底层，为上层的 React 渲染、历史记录管理以及协同冲突解决提供了可预测的、确定性的基础。
序言
在现代前端工程中，"实时协同"（Real-time Collaboration）往往被视为一项昂贵且复杂的功能特性。虽然 Y.js、Automerge 等 CRDT（Conflict-free Replicated Data Type）库的出现解决了最底层的并发冲突算法问题，但对于一个生产级的应用来说，引入 CRDT 仅仅是挑战的开始，而非结束。
之前我正在为 RisingWave 的控制台增加 SQL Notebook 功能
这是一个包含代码（Source）、执行状态（Running State）和副作用（Execution Results）的复杂状态机。在分布式环境下，如何保证数据的一致性？如何处理因果关系（修改代码导致结果失效）？如何设计撤销栈以符合用户的心理模型？
在构建实时协同应用时，引入 Y.js 或 Automerge 等 CRDT（Conflict-free Replicated Data Type）库仅仅是第一步。这些库提供了解决并发冲突的底层算法，但如何基于这些原语构建业务数据模型（Schema），才是决定系统健壮性、性能以及用户体验上限的关键因素。
我将深入剖析我在协同 Notebook 中的数据建模实践，阐述为何应该放弃简单的树状嵌套结构，转而采用“Map-Reduce”式的扁平化设计，以及如何通过分离“用户意图”与“系统状态”来解决复杂的撤销/重做（Undo/Redo）问题
根节点的扁平化拓扑
在设计初期，一个常见的陷阱是将文档视为一个巨大的 JSON 对象，并将所有数据深层嵌套。例如，将 Notebook 定义为一个包含 Cell 对象的数组。然而，在 CRDT 的语境下，深层嵌套往往意味着更高的冲突概率和更复杂的路径追踪。
我们定义的 Schema 根节点是一个 Y.Map（rw-notebook-root），其内部结构并非树状，而是一组并行的顶层集合：
// /src/yjs/schema/core/keys.ts
// 核心存储：单元格实体
export const NB_CELL_MAP = "cellMap"; // Y.Map<YCell>
// 拓扑结构：单元格顺序
export const NB_CELL_ORDER = "order"; // Y.Array<string>
// 系统状态：执行结果
export const NB_OUTPUTS = "outputs"; // Y.Map<YOutputEntry>
// 生命周期管理：软删除标记
export const NB_TOMBSTONES = "tombstones"; // Y.Map<boolean>这种设计确立了几个核心原则：
- 引用优于嵌套：实体通过 ID 关联，而非直接包含。
- 关注点分离：不同的业务逻辑操作文档的不同部分，互不干扰。
Map + Order 模式：内容与拓扑的解耦
Schema 中最核心的设计决策是将单元格的内容存储（NB_CELL_MAP）与单元格的排列顺序（NB_CELL_ORDER）完全分离。
传统模式的弊端
如果使用 Y.Array<YCell> 直接存储单元格对象，会面临以下问题：
- 移动成本高昂：在协同编辑中，若用户 A 移动了单元格的位置，CRDT 需要处理整个对象的删除与重新插入。如果单元格包含大量文本或元数据，这会产生不必要的网络开销。
- 并发冲突：如果用户 A 修改了单元格的内容，而用户 B 移动了该单元格，在单一数组模型下，合并逻辑会变得异常复杂，甚至可能导致“修改丢失”或“幽灵数据”。
要理解为什么“移动”在 CRDT（特别是像 Y.js 早期版本或基础实现中）如此昂贵且危险，我们需要深入到 CRDT 的底层数据结构实现原理中去。
我们的方案
- NB_CELL_MAP (The "What")：这是一个
Y.Map，以 UUID 为键存储YCell对象。它提供了 O(1) 的数据访问能力，并且是单元格数据的唯一真值来源（Source of Truth）。 - NB_CELL_ORDER (The "Where")：这是一个
Y.Array<string>，仅存储 UUID 字符串。
收益
这种分离带来了显著的架构优势：
- 原子性的移动操作：移动单元格仅涉及在
NB_CELL_ORDER中移动一个轻量级的字符串 ID。 - 无冲突的并发编辑：用户 A 修改
NB_CELL_MAP中的内容（Y.Text），用户 B 修改NB_CELL_ORDER中的顺序。由于操作作用于不同的 CRDT 结构，Y.js 可以完美地自动合并两者，无需任何冲突解决逻辑。 - 数据完整性容错：即使网络波动导致顺序数组与 Map 短暂不一致（例如 Map 中有数据但 Order 中丢失 ID），数据本身依然安全地存在于 Map 中。我们未来的文章当中所阐述的 reconcile 工具可以轻易地扫描出“孤儿”单元格并将其恢复到视图中。
CRDT 中的“移动悖论”与“身份丢失”
在理解为什么我们要分离 NB_CELL_MAP 和 NB_CELL_ORDER 之前，必须先理解在分布式数据结构中，“移动（Move）”操作的本质困境。
1. CRDT 数组的底层实现：双向链表与唯一 ID
在 Y.js 等 CRDT 实现中，Y.Array 并非像 JavaScript 数组那样通过下标（Index）直接寻址。它在底层通常被实现为一个双向链表。链表中的每一个节点（Item）都有一个全局唯一的 ID（由 ClientID 和 Clock 组成）。
当我们说 Array[0] 时，CRDT 实际上是在遍历链表找到第一个非删除状态的节点。
2. 为什么“移动”等于“销毁 + 重建”？
在许多 CRDT 的基础实现中，并没有原生的“移动（Move）”原语。要把对象 A 从索引 0 移到索引 5，系统无法直接修改指针。为了保证最终一致性，CRDT 通常将“移动”拆解为两个原子操作：
- Delete(A)：在索引 0 处标记对象 A 为“已删除（Tombstone）”。
- Insert(A')：在索引 5 处创建一个全新的对象 A'，它是 A 的深拷贝。
关键点在于： 对象 A 和对象 A' 虽然内容相同，但在 CRDT 的视角下，它们是两个完全不同的实体，拥有不同的唯一 ID。
3. 并发冲突的灾难现场
正是因为“移动”导致了对象身份（Identity）的变更，才会引发严重的并发冲突。
单一数组模型（Nested Object in Array）
假设文档结构是 Y.Array<YCell>，其中 Cell 是一个包含文本的大对象。
- 初始状态：数组里有一个对象
Cell_Old(ID: UserA:1)。 - 用户 A（编辑内容）：在
Cell_Old内部输入了一行代码。CRDT 操作记录为：“在对象UserA:1的source字段中插入文本”。 - 用户 B（移动位置）：将该 Cell 下移。
- CRDT 操作 1：删除
Cell_Old(ID: UserA:1)。 - CRDT 操作 2：新建
Cell_New(ID: UserB:1) 在新位置。
- CRDT 操作 1：删除
Merge：
- 用户 B 的操作生效：
Cell_New出现在新位置，Cell_Old变为墓碑（不可见）。 - 用户 A 的操作到达：系统尝试在对象
UserA:1(Cell_Old) 中插入文本。 - 冲突发生：系统发现
UserA:1已经被标记为删除。根据 CRDT 规则，对已删除对象的编辑操作通常会被丢弃或变为无效。 - 最终现象：用户看到单元格被移动了，但用户 A 输入的代码凭空消失了。这就是所谓的“修改丢失”。
4. 网络开销的放大
如果 Cell 是一个深层嵌套的大对象（包含大量代码、元数据、执行结果），在“销毁 + 重建”的过程中，系统需要将整个对象序列化并作为新的 Insert 操作广播给所有对端。
- 移动前：对象大小 10KB。
- 移动操作：网络传输包大小 > 10KB（因为包含完整的对象副本）。
在一个频繁拖拽排序的交互中，这种带宽消耗是不可接受的。
5. 解决方案：引用不变性（Reference Immutability）
通过采用 "Map + Order" 模式，我们从根本上规避了上述问题：
- NB_CELL_MAP：存储
YCell实体。一旦创建，其在 Map 中的 Key（UUID）永不改变。无论如何在 UI 上展示，实体的身份（Identity）是恒定的。 - NB_CELL_ORDER：仅存储 UUID 字符串。
当发生并发操作时：
- 用户 A（编辑）：操作指向
NB_CELL_MAP中的特定 UUID。 - 用户 B（移动）：操作指向
NB_CELL_ORDER，删除了旧位置的 UUID 字符串，在新位置插入了相同的 UUID 字符串。
合并结果：
用户 B 改变了引用的位置，但没有触碰引用的实体。用户 A 的编辑操作依然能精准地找到 NB_CELL_MAP 中那个并未被删除的实体。
网络开销： 用户 B 的移动操作仅产生几个字节的开销（删除一个 UUID 字符串，插入一个 UUID 字符串），与单元格内容的多少无关。
现在，你能理解为什么需要使用 Map + Order 的方案了吧？
意图与副作用的隔离：Outputs 的独立存储
Notebook 与普通文档编辑器的最大区别在于它包含“代码执行”这一环节。单元格不仅包含源代码（Source），还包含执行结果（Output）。
在 Schema 设计中，我们刻意将 Output 从 Cell 实体中剥离，存储在独立的 NB_OUTPUTS Map 中。
为什么不放在 Cell 内部？
直觉上，执行结果属于单元格的一部分。但在协同与撤销场景下，这种耦合是致命的。
考虑以下场景：
- 用户编写 SQL：
SELECT * FROM users。 - 用户执行查询，表格显示 100 行数据。
- 用户发现表名写错，修改为
SELECT * FROM customers。 - 用户执行撤销（Undo）。
如果 Output 存储在 Cell 内部，UndoManager 会追踪 Cell 的所有变更。撤销操作可能会将源代码回滚到 users，同时将执行结果回滚到“100 行数据”的状态。
这违背了用户的心理模型：用户撤销的是编辑意图（代码），而不是系统副作用（执行结果）。 代码回滚后，执行结果应当保持现状（或者变为 Stale 状态），而不应回滚到旧的查询结果，否则会造成“代码与结果不匹配”的严重误导。
架构实现
- NB_CELL_MAP：存储用户编辑的代码。
UndoManager包含此 Scope。 - NB_OUTPUTS：存储系统返回的
QueryResponse、running状态和runId。UndoManager排除此 Scope。
此外，我们在写入 Output 时使用了 EXECUTION_ORIGIN。即使 UndoManager 配置有误，通过 Origin 过滤也能作为第二道防线，确保执行相关的状态变更永远不会进入撤销栈。
墓碑机制（Tombstones）：分布式删除的权衡
在 P2P 或分布式系统中，“删除”是一个危险的操作。如果用户 A 删除了一个单元格，而用户 B 正在该单元格中输入，物理删除会导致用户 B 的编辑操作因找不到目标对象而报错或丢失。
我们采用了软删除（Soft Delete）策略：
export const softDeleteCell = (nb: YNotebook, cellId: string, ...) => {
// 1. 从视图中移除：修改 NB_CELL_ORDER
const order = getOrder(nb)
order.delete(...)
// 2. 标记墓碑：修改 NB_TOMBSTONES
const t = tombstonesMap(nb)
t.set(cellId, true)
// 注意：NB_CELL_MAP 中的数据保留不动
}墓碑的价值
- 非破坏性：用户 B 的并发编辑依然可以应用到 Map 中的对象上，只是该对象在 UI 上不可见。
- 可恢复性：撤销“删除”操作变得非常廉价——只需将 ID 插回
NB_CELL_ORDER并移除墓碑标记。数据从未真正离开过。 - 历史审计：保留的数据允许我们展示详细的编辑历史，即使是已删除的单元格。
维护成本
墓碑机制的代价是文档体积会随时间单调递增。因此，Schema 设计必须包含生命周期管理。我们引入了 vacuumNotebook 操作，配合 NB_TOMBSTONE_META 中的时间戳，允许系统在特定条件下（如过期时间 TTL）执行物理删除（Hard Delete），回收存储空间。