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，一共六种类型：

改单元格 (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 }

设计上有几个约束：

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

有一个边界要如实交代：Delete 的 revert 是等长的 Insert，只还原结构，被删那一行的单元格内容不在逆操作里。单元格级的内容恢复依赖 Change 的 od，整行删除的内容恢复不在这层协议的覆盖范围里。

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

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

1. 客户端本地编辑，op 立刻 apply 到本地 state，界面不等服务器确认。
2. op 进入 unconfirmed 队列，按发出顺序排好，同时发给服务器。
3. 服务器给所有 op 定一个全局顺序，应用到权威快照上，再按顺序广播。这里有个容易忽略的点：客户端是乐观执行的，op 到达服务器时往往基于旧版本，服务器要拿着 version，把这个 op 对它之后到达的每个 op 做 transform，前滚到最新版本再应用。所以服务器不只是定序转发，它也要跑 transform，整个库做成前后端同构（不依赖浏览器环境）就是为了这一步能复用同一份代码。
4. 客户端收到广播后走 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 的各端最终一致”，顺序本身要有人说了算。把定序放在服务器，客户端的控制回路才能保持简单：本地永远乐观，远端来了就重基。

一次完整的重基过程

用一个具体的并发把上面的流程走完。初始状态：单元格 (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 清理都会错位。