OT — 多人同时改一份文档，操作随上下文自动改坐标

是什么

OT（Operational Transformation，操作变换）是一套让多人同时改同一份文档、不用先锁住、最后还能合到一致的算法。

日常类比：你和同事都在编辑一篇 Google Docs。你在第 1 个字前插了一个 “X”，他在第 5 个字前插了一个 “Y”，几乎同时。你按下键盘那一刻，对方还没看到你的字。

OT 干的事：等他的 “Y” 通过网络飘过来，发现你已经在前面塞过一个 “X”——他原以为要插在位置 5，但现在文档已经多了一个字，正确位置应该是 6。OT 自动把”位置 5”改成”位置 6”，再应用。反方向同理。

最后两个人屏幕上都显示同样的内容，不需要任何人停下来等。这就是 Ellis & Gibbs 在 1989 年 SIGMOD 论文里发明的算法，叫 dOPT（distributed OPerational Transformation），也是 Google Docs / Office 365 协同编辑的核心。

为什么重要

不理解 OT，下面这些产品都没法解释：

• Google Docs：你和 10 个同事一起改简历，谁都不锁，最终所有人看到一样——这正是 OT
• Google Wave（2009）：把 OT 第一次推到大众面前的产品（虽然后来下线了，但算法活了下来）
• Office 365 / Word Online：微软自家的协同编辑也是 OT 派系
• Etherpad / ShareJS / ot.js：开源协同编辑库，几乎都是 OT 实现

它和另一条路线 crdt-shapiro-2011（CRDT）并列为”协同编辑两大流派”。CRDT 是把数据本身设计成天然能合并；OT 是让操作在传播时根据上下文自动改写自己。

核心要点

OT 解决的核心问题：操作的位置坐标会过期。你按”在位置 5 插 Y”那一刻是对的，但传到对方副本时，对方已经在前面插了别的字符，位置 5 已经不是当初的位置 5。

OT 的三板斧：

1. 副本独立：每个用户本机一份副本（replica）。本地操作立刻应用到本地副本，零延迟。
2. 状态向量（state vector）：每条操作带着”我是基于哪个版本生成的”的版本号向量。类似快递单上的发件状态。
3. transform 函数：远程操作到达时，先看它和本地已应用的并发操作是不是基于同一版本——不是的话，调用 T(op_remote, op_local) 把远程操作的坐标改写一下，再应用。

举个具体的：

• 文档初始 "abcde"
• A 在位置 1 前插 X → "aXbcde"
• B 同时在位置 5 前插 Y → "abcdYe"
• B 的 insert(5, Y) 飘到 A：A 已经在前面插过 X，所以位置要 +1 → 变成 insert(6, Y) → A 的最终："aXbcdYe"
• A 的 insert(1, X) 飘到 B：B 在 1 之后插的，1 不受影响 → 不改 → B 的最终："aXbcdYe"

两边收敛到同一字符串，全程没人停下来等。

实践案例

案例 1：transform 函数怎么写（最简版）

两条 insert 同时来，假设 A 想 insert(p1, c1)，B 想 insert(p2, c2)：

def T(op_a, op_b):
    # 把 op_a 在 op_b 已经应用的语境下重写
    if op_a.pos < op_b.pos:
        return op_a  # 不受影响
    elif op_a.pos > op_b.pos:
        return Insert(op_a.pos + 1, op_a.char)  # 坐标 +1
    else:  # 同位置：用 site id 决定先后保证一致
        if op_a.site < op_b.site:
            return op_a
        else:
            return Insert(op_a.pos + 1, op_a.char)

这就是论文里 T_II（insert vs insert）的定义。还有 T_ID / T_DI / T_DD 共四种。

案例 2：GROVE — 论文配套实现

Ellis 团队在 MCC 实验室造了 GROVE（Group Outline Viewing Editor）——一个多人协同大纲编辑器，所有副本完全对等（peer-to-peer），没有中心服务器。这是 OT 的第一个跑起来的实现，也证明这思路工程上可行。

案例 3：Google Docs 怎么用 OT

Google Docs 没用 dOPT 原版，用的是 Jupiter 模型（Lotus Notes 研究院 1995 年改的简化版）：

• client-server 架构（不是 peer-to-peer）
• 每个 client 只和 server 做 transform，client 之间不直接通信
• server 维护权威序列，把变换后的操作广播

这一改让 OT 容易实现 100 倍，也是为什么 Google Docs 跑得稳。原版 dOPT 让 N 个 client 两两 transform，复杂度 O(N²)；Jupiter 把所有变换集中到 server，每个 client 只看到 O(1) 复杂度。代价是 server 故障时全停。

案例 4：状态向量 vs Lamport 时钟

OT 的”状态向量”其实是 lamport-1978 因果时钟的一个特殊化：每个 site 维护一个 N 维向量，第 i 维记录”我已经看过 site i 的多少操作”。两条操作并发当且仅当它们的向量互不支配。这给了 OT 一个清晰的判断标准——什么时候要做 transform，什么时候直接应用即可。

踩过的坑

1. dOPT 原算法不完备：Ellis-Gibbs 1989 提出后，1996 年 Ressel 等人发现，要让 OT 在所有并发场景收敛，transform 函数必须满足两条性质：

   • TP1：T(T(a, b), T(c, b)) = T(T(a, c), T(b, c)) — 变换的顺序无关
   • TP2：三个并发操作变换必须一致

   后续 20 年很多论文证明，TP2 极难满足——多个被引用的 OT 算法后来被反例证伪。

2. 意图保留（intention preservation）：Ellis-Gibbs 强调 OT 要保的不只是”最终一致”，还要保用户意图。比如你想”把这个词加粗”，不应被并发操作意外取消。这比单纯收敛要求高。

3. server 是单点：Jupiter 简化为 client-server 后，server 一挂就全停。CRDT 派天生 P2P，这是它的卖点之一。

4. 复杂操作难变换：纯 insert/delete 还好，富文本属性、表格行列、嵌套结构……每加一种操作就要补全 transform 函数表，组合爆炸。

适用 vs 不适用场景

适用：

• client-server 协同编辑（Google Docs / Office 365 / Etherpad）
• 需要小元数据：OT 操作只携带坐标和字符，比 CRDT 的 tombstone/UUID 省 10x 带宽
• 中心服务器可信、网络延迟可接受（< 1s）

不适用：

• 完全 P2P / 离线时间长：用 crdt-shapiro-2011（CRDT）
• 操作类型多变：transform 表会爆炸
• 不能容忍 server 故障：CRDT 天生无中心

历史小故事（可跳过）

• 1989 年：Ellis & Gibbs 在 MCC（Microelectronics and Computer Technology Corp.，德州奥斯汀）SIGMOD 论文，提出 dOPT + GROVE。论文写得清楚但算法有 bug，后来才发现。
• 1995 年：Lotus Notes 研究院的 Nichols 等人提 Jupiter 模型——client-server 简化版，证明工程上能跑。
• 1996 年：Ressel 提 adOPTed 算法 + TP1/TP2 形式化，OT 才有了正确性根基。
• 2006 年：SOCT2 / COT 等修正算法，证明大部分早期 OT 算法的 TP2 反例。
• 2009 年：Google Wave 上线——OT 第一次推到大众产品。
• 2010+：Google Docs / Office 365 / Quip 全部基于 OT 衍生算法。

OT 走了 20 年才从论文 bug 走到 Google Docs；CRDT 走了大约同样长的时间从理论走到 Figma / Linear。两条路都不易。

学到什么

1. 同步可以靠”操作变换”而不是”锁”——这是协同编辑的范式革命。
2. 本地零延迟 + 后台收敛比”等服务器答复”用户体验好太多——这背后是 OT/CRDT 共同遵守的 CCI 原则（Convergence / Causality / Intention preservation）。
3. 算法发表 ≠ 算法正确——dOPT 等了 7 年才被发现不完备。形式化证明在分布式系统里不可省。
4. 同一问题可以有完全不同的解法：OT 改操作，CRDT 改数据。两者数学上等价（都能做协同），但工程权衡完全不同。

延伸阅读

• 论文 PDF：Ellis & Gibbs 1989（SIGMOD，10 页，dOPT + GROVE）
• 综述：Sun & Ellis, “Operational Transformation in Real-Time Group Editors”, CSCW 1998（OT 第一个完整综述）
• 工业实现：Google Wave Operational Transformation 文档（Google 自己写的 OT 工程文档）
• 反方观点：Martin Kleppmann — “I was wrong. CRDTs are the future”（OT 派人物倒戈 CRDT 的著名博文）
• crdt-shapiro-2011 —— OT 的对立流派，看两派对比
• lamport-1978 —— 因果序的数学基础，OT 的状态向量直接借用

关联

• crdt-shapiro-2011 —— 协同编辑另一流派，与 OT 并列
• crdt-json —— Kleppmann 把 CRDT 推到嵌套 JSON
• lamport-1978 —— 因果时钟，OT/CRDT 共同基础
• paxos-1998 —— 强一致协议，与 OT 的”最终一致”对照
• two-phase-commit —— 传统加锁路线，OT 选择放弃锁