Excel 实时协作协议的设计

做大象协作文档时，Excel 的协作模型需要处理表格结构操作对坐标系的影响：插入一行之后，后续所有单元格的行号都会变化。op 如果不理解这个语义，两个客户端各插一行时，改单元格的 op 会落到错误的位置，两端会看到不同的表。

市面上通用的 OT 实现大多面向文本（ot.js）或通用 JSON（ShareDB 的 json0）。json0 的 op 是 JSON 路径上的增删改，它不知道 c["3:2"] 这个 key 里的 3 和 2 是坐标，插入一行之后这些 key 本身要重写。用通用 JSON op 表达表格的结构操作，transform 规则覆盖不到坐标依赖，结果就是不收敛。

另一个方向是 CRDT。序列 CRDT 给每个元素分配唯一 id，不需要中央定序；代价是每个元素都携带 id 元数据，一张表有几千到几十万个单元格时会产生相应开销。协作文档业务已有文档服务器，采用星型拓扑，CRDT 在对等网络和长时间离线合并上的优势不适用于这里。因此选择 OT：服务器定序，客户端重基。协议从表格语义出发自行定义，代码在 xmexcel-model，本文记录其原理和取舍。

数据模型：稀疏网格加结构属性

协议操作的文档状态是一个以 sheet id 为 key 的对象，一张 sheet 长这样：

{
  "Skn4lyJ_G": {
    "name": "工作表1",
    "c": {
      "0:0": { "v": 1 },
      "2:3": { "v": "hello" }
    },
    "rh": { "0": 32 },
    "cw": { "3": 120 },
    "mergeCells": { "1:1": { "rowspan": 2, "colspan": 3 } },
    "fixed": { "row": 1 },
    "filter": { "row": 0, "colRange": [0, 5] },
    "filterByValue": { "2": ["a", "b"] },
    "hiddenRows": [4, 7]
  }
}

单元格用 "行:列" 做 key 稀疏存储。一张空表不占任何单元格空间，代码里空表默认按 200 行 20 列算；单元格内容清空时直接删 key，而不是存一个空值。
行高 rh、列宽 cw、合并单元格 mergeCells、冻结 fixed、筛选 filter 和 filterByValue 都是独立的结构属性，各自挂在 sheet 上，和单元格内容分开变换。
hiddenRows 是派生数据，由 filter 和 filterByValue 算出来，不代表任何人的编辑动作。筛选条件变化时各端用同一个 calcHiddenRows 重算，结果必然一致，所以这类数据不需要同步。

这个结构有两个后果。第一，单元格的 key 就是坐标，行列增删需要批量重写 key，Insert 和 Delete 的 apply 都要遍历整个 c 重建一次，这是数据模型的直接推论。第二，sheet 的行数列数（row、col）也是维护的状态：空表按 200×20 起步，单元格写到更远处会扩大维度，行列增删再相应加减。维度允许缺省，缺省时要从 c 的 key 中扫描最大值；apply 路径上的这些扫描会影响性能。

这个模型中，所有定位使用坐标，不使用稳定 id。文本的序列 CRDT（RGA、Logoot 这一路）会给每个字符分配唯一 id，以避免位置变换；表格没有采用这种方式，因为行列增删会成批改变坐标，给单元格分配 id 不能避免 key 本身变化。坐标方案将并发冲突转化为坐标平移问题，由 transform 集中处理。

操作模型：六种 op

线上传输的 op 是纯 JSON，一共六种类型：

类型	含义	字段
`c`	修改	`id` sheet id，`p` 路径，`oi` 新值，`od` 旧值
`ic` / `ir`	插入列 / 行	`i` 位置，`a` 数量
`dc` / `dr`	删除列 / 行	`i` 位置
`as`	增加 sheet	`id`，`sheet`
`rs`	删除 sheet	`id`，`sheet`
`e`	空操作	无

改单元格 (2,3) 的值，从 “1” 改成 “2”：

{ "t": "c", "id": "sheet1", "p": ["c", 2, 3], "oi": "2", "od": "1" }

p 的第一段区分改的是什么：“c” 是单元格，还可以是 “rh”、“cw”、“mergeCells”、“fixed”、“filter” 等。p 有第四段时只改单元格的某个子属性，比如 ["c", 0, 1, "v"] 改 (0,1) 的值，不碰它的样式。

在列索引 1 处插入 2 列（索引从 0 起），原来索引 1 及之后的列右移：

{ "t": "ic", "id": "sheet1", "i": 1, "a": 2 }

设计上有几个约束：

op 必须可以 JSON 序列化。传输、持久化、断线回放都依赖这一点，字段名也因此压到一两个字母。
每个 op 都要实现 apply 和 revert。apply 把 op 作用到 state 上，revert 生成逆操作。Change 的 od 字段记录旧值，首先是为 revert 服务的，但它在协作里还有第二个用处，撤销一节会讲到；Insert 的逆操作是 a 个 Delete。
Empty 是一个真实的 op 类型，不是 null。transform 的结果可能是无需执行的 op，用 Empty 表示；这样 transform 对任意 op 对都有定义，调用方不需要处理空值分支。

限制：Delete 的 revert 是等长的 Insert，只还原结构，被删行的单元格内容不在逆操作中。单元格级的内容恢复依赖 Change 的 od，整行删除的内容恢复不在这层协议的覆盖范围内。

一致性模型：服务器定序，客户端重基

整体架构是 OT 的星型拓扑：

客户端本地编辑，op 立刻 apply 到本地 state，界面不等服务器确认。
op 进入 unconfirmed 队列，按发出顺序排好，同时发给服务器。
服务器给所有 op 定一个全局顺序，应用到权威快照上，再按顺序广播。客户端采用乐观执行，op 到达服务器时通常基于旧版本；服务器使用 version，将该 op 与它之后到达的每个 op 做 transform，转换到最新版本后再应用。因此服务器除定序转发外也要执行 transform；整个库做成前后端同构（不依赖浏览器环境），以复用这部分代码。
客户端收到广播后走 receive：先按 clientID 跳过消息里自己发起的、已被确认的那段前缀，把对应的 op 从 unconfirmed 里摘掉；剩下的远端 op，逐个穿过 unconfirmed 队列做 transform，本地未确认 op 重基到远端 op 之后，远端 op 也被改写成假设本地 op 已生效的等价版本，再 apply 到 state。

第 4 步中，两个方向的变换必须成对。代码里每个远端 op 穿过整个 unconfirmed 队列，每遇到一个本地 op 就被改写一次：

// removeOp 是远端 op，this.unconfirmed 是本端已发出但未确认的 op
this.unconfirmed.reverse().forEach(item => {
    if (!Empty.isEmpty(removeOp)) {
        let [a, b] = ExcelModel.transform(item, removeOp);
        if (ExcelModel.trim(a)) {
            unconfirmed = [a].concat(unconfirmed); // 本地 op 重基后的版本
        }
        removeOp = b; // 远端 op 变换后的等价版本
    }
});

定序必须由唯一一方执行。transform 的设计目标是“按同一个顺序重放所有 op 后，各端最终一致”，因此顺序需要由单一节点确定。将定序放在服务器后，客户端本地乐观执行，收到远端 op 时进行重基。

一次完整的重基过程

用一个具体的并发把上面的流程走完。初始状态：单元格 (2,3) 的值是 “1”。A 把它改成 “2”，B 同时在列索引 1 处插入 2 列。两个 op 基于同一个版本并发产生：

{ "t": "c",  "id": "s", "p": ["c", 2, 3], "oi": "2", "od": "1" }
{ "t": "ic", "id": "s", "i": 1, "a": 2 }

服务器的处理：B 的插入先到，直接应用，版本加一；A 的修改基于旧版本到达，服务器用 B 的 op 对它 transform，列坐标 3 平移成 5，再应用。广播出去的 op 流是 [B 的插入，A 的修改（已平移到 (2,5)）]。

A 收到流。第一个 op 是 B 的，不是自己发的，没有前缀可跳。unconfirmed 里自己那条修改被重基：插入点在目标列之前，列坐标 3 变 5。然后应用 B 的插入，本地 (2,3) 的 “2” 跟着平移到 (2,5)。第二个 op 是自己修改的回显，和重基后的本地 op 比对，同单元格同字段，幂等成 Empty，不重复应用。A 的最终状态：(2,5) 是 “2”，多了两列。

B 收到流。第一个 op 是自己的 ack，从 unconfirmed 摘掉；第二个 op 是 A 的修改，服务器已经平移好了，直接应用。B 的最终状态一样：(2,5) 是 “2”。

两端收敛，A 的修改落在其意图对应的单元格，而非坐标 3 平移后错位的单元格。两端的处理路径不对称：A 的本地 op 被改写一次，B 的没有。后定序操作所在客户端的未确认队列需要执行变换，这是乐观执行的处理方式。这个例子中 A 的回显不是消息前缀，重基后的本地 op 会留在 unconfirmed 中，属于结尾所述前缀假设需要处理的情形。

transform：把冲突归约成坐标平移

transform(op1, op2) 的语义是：两个 op 基于同一个 state 并发产生，op2 已经先生效，返回 [op1', op2']，op1’ 是 op1 假设 op2 已生效后的等价形式。不同 sheet 的 op 直接原样返回；同 sheet 的按类型对分发，五种有效类型两两组合，分到 handleIR、handleIC、handleDR、handleDC、handleC 五个分支，同类型的组合另有特判。

表格的 transform 需要处理不同形状的 op 范围。修改单元格是一个点，行列插入是一个区间，行列删除是一条线，mergeCells 是一个矩形，filter 是一个点加一个区间。判断两个 op 的关系时，需先按形状判断相交关系：点在区间左侧、右侧或内部；矩形被区间穿过、推开或截断。每种关系对应不同动作：平移坐标、伸缩长度（rowspan、colspan）或整体丢弃。文本 OT 只有点和区间两种形状；表格还包含矩形和组合形状，因此类型对与位置关系共同增加了规则数量。分发表需要覆盖每一种组合。

下面的例子取自仓库中的测试用例。

修改 × 插入列。 A 改 (2,3)，B 在列索引 1 处插 2 列。B 先生效，A 的列坐标平移：

transform(
    new Change('1', ['c', 2, 3], '2', '1'),
    new Insert('1', 'ic', 1, 2)
);
// a: {"t":"c","id":"1","p":["c",2,5],"oi":"2","od":"1"}
// b: {"t":"ic","id":"1","i":1,"a":2}

插入位置在 A 的目标列之前，A 的列号加 2；插入位置在之后（比如 i=6），两边都原样返回。

修改 × 修改，同一个单元格。 先定序的那个被丢弃：

transform(
    new Change('1', ['c', 2, 3], '2', '1'),
    new Change('1', ['c', 2, 3], '3', '4')
);
// a 不变，b 变成 {"t":"e"}

a 保留、b 变 Empty。在 receive 的语境里，b 总是服务器已确认的 op，a 是本地未确认的 op，本地 op 在服务器顺序里必然更晚，所以最终生效的是后定序的那个。每个单元格采用 last writer wins 语义，由定序决定最终值。两个人同时修改同一个单元格时，协议不提供保留双方修改的合并语义；丢弃先定序的修改是当前策略。如果两个人改的是同一单元格的不同子属性，比如一个改值一个改背景色，两边都能保留。

删除 × 删除，同一行。 两个都变 Empty。删除是幂等的，同一行被两个人同时删，结果应该是删一次：远端删除到达时本地的行已经删掉了，远端 op 变换成 Empty 不再执行，本地那条还未确认的删除也被重基成 Empty，从 unconfirmed 里清掉。

插入 × 删除的位置关系。 op 除位置外还有长度，位置关系需要通过区间相交判断，不能只比较大小。以 ir × dr 为例，有三种情况：

结构操作 × 合并单元格。 mergeCells 记录每个合并区域的起点和 rowspan、colspan。插入一行落在合并区域内部时，rowspan 加一；落在区域前面时，起点行号平移。删除同理，rowspan 和 colspan 减到 1×1 时整条合并记录删掉。filter 的 colRange、fixed 的行列数、rh 和 cw 的 key 都要做同样的平移。另外删除整个 sheet（rs）时，这个 sheet 上所有并发 op 直接变 Empty。这些规则需要覆盖全部类型组合和位置关系。

撤销与历史重基

每种 op 的 revert 规则如下：Change 交换 oi 和 od；Insert 换成 a 个 Delete；Delete 换成等长的 Insert；AddSheet 和 RemoveSheet 互换。撤销的单元是 HistoryStep 而不是单个 op：一次用户动作（比如粘贴一个区域）会产生一组 op，这组 op 要么一起撤销，要么不撤销。redo 栈在本地产生新操作时清空，这是编辑器撤销的惯例。

协作场景中，undo 栈里的 op 基于历史坐标系。远端 op 到达时，undo 和 redo 栈中每个 step 的每个 op 都要对它执行 transform（HistoryStep.rebase），否则撤销会修改错误的位置。transform 时必须同时改写 oi 和 od：远端插入一行落在某个合并区域内时，undo 栈中该 mergeCells 修改的 oi 和 od 的 rowspan 都要加一；只改 oi 会使撤销恢复出错误的合并区域。Change 的 od 字段除用于 revert 外，也使历史 op 在坐标系变化后仍能生成正确的逆操作。

undo 栈最多保留 100 步，超出部分丢弃。协作场景中 undo 的正确性依赖 history rebase，而 rebase 只能基于现存历史；无限保留 undo 栈会增加内存开销，但不能扩展可重基的历史范围。

几个取舍

筛选不同步。 filter、filterByValue、hiddenRows 相关的 op 会被 splitOps 挑出，不进入 unconfirmed，也不发送给其他端。筛选属于各客户端的视图状态，不作为共享内容；一个客户端筛选某个区域时，其他客户端保持自己的视图。筛选引起的状态变化只有 hiddenRows，且它是各端各自重算的派生数据。

保持较少的 op 类型。 分发表的成本与类型数的平方相关。每增加一种 op，都要补齐它与所有既有类型的成对规则；遗漏一对会产生仅在并发时出现的 bug。协议将类型限制为六种，字体、颜色、边框等样式变更全部走 Change 的子属性路径，不为它们单设类型。

结构操作的 apply 是全量重建。 插入一行要把 c 中所有行号大于等于插入点的 key 重写一遍，复杂度是 O（单元格数），这是坐标方案的固有成本。每次 apply 还会对整个 state 做一次深拷贝，以保持模型不可变：apply 返回新模型，界面层可以直接用引用比较判断是否重渲染。仓库的 perf/ 目录提供基准脚本，用真实 op 序列测量 apply 耗时，并用于检查结构操作密集场景的性能回归。

结尾

这套协议要求 transform 的成对规则全覆盖。测试按类型对组织：dr-ir.js、ic-dc.js、dc-f-fv.js 各对应一对组合，每对再枚举位置关系。规则写错一个分支会使两个客户端看到不同的表，并且只在并发时复现；这些测试用于定位此类问题。

当前有三个已知缺口。一是 Change × Change 只精细到单元格：rh、cw、mergeCells 等按 key 合并的属性，并发修改不同 key 时，先定序的 op 会在另一端整体变为 Empty，修改丢失，两端发散。二是删除和修改作用于同一列（或同一行）时，两个方向的 transform 不对称：一个方向丢弃修改，另一个方向保留，保留的修改还会作用于删除后平移到该位置的列，同一对并发在两端结果不同。三是 receive 的控制循环中，远端 op 在中途变换成 Empty 后，队列中剩余的 unconfirmed 项会被直接丢弃，而非原样保留。前两个问题需要按更细粒度补充 transform 分支和测试；第三个是控制回路的实现问题。这三个问题只在并发时触发，单人编辑不会触发；在协作场景中，每个问题都会导致确定性发散。

未覆盖部分如下：版本号保留在模型中（version 字段），但长时间离线后的合并策略不在这层协议内；服务器定序服务的实现也不在这个仓库。协议层约定两个假设：客户端收到的是按全局顺序排列的 op 流，且自己发出的 op 会以消息前缀的形式返回；否则 receive 中的前缀裁剪和 unconfirmed 清理都会错位。