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 的三板斧：

副本独立：每个用户本机一份副本（replica）。本地操作立刻应用到本地副本，零延迟——像你在纸上先写，再把改动寄给同事。
状态向量（state vector）：每条操作带着”我是基于哪个版本生成的”的版本号向量。把它想成快递单上的多维发件戳：每个协作者一格，格子里写”我已看过你几条改动”。
transform 函数：远程操作到达时，若与本地已应用的操作并发，就调用 T(op_remote, op_local) 改写坐标再应用。状态向量来自 lamport-1978 因果时钟：向量互不支配 ⇒ 并发 ⇒ 必须 transform。

举个具体的：

文档初始 "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 已经应用的语境下重写（T_II）
    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_ID 示意：若 op_b 是 delete 且删在 op_a.pos 左侧，insert 坐标同样 -1

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

案例 2：GROVE — 论文配套实现（三步走）

Ellis 团队在 MCC 造了 GROVE（Group Outline Viewing Editor），全对等、无中心服务器：

本地立刻应用：你在大纲里插入一行，本机马上显示，不等网络。
广播操作：把带状态向量的 insert/delete 发给其他副本。
对端 transform 再应用：对方若已有并发改动，先 T(...) 改坐标，再落到本地大纲。

这是 OT 第一个跑起来的实现，证明 P2P 路线工程上可行。

案例 3：Google Docs 怎么用 OT（Jupiter）

Google Docs 没用 dOPT 原版，用的是 Jupiter 模型（Xerox PARC 的 Nichols 等人，UIST 1995）：

client-server：每个 client 只和 server 做 transform，client 之间不直连
server 维护权威操作序列，把变换后的操作广播出去
原版 dOPT 是 N 端两两 transform（约 O(N²)）；Jupiter 把变换收拢到 server，client 侧接近 O(1)

这一改让生产级 OT 可落地，也是 Google Docs / Wave 能跑稳的原因。代价是 server 故障时全停。

踩过的坑

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 算法后来被反例证伪。
意图保留（intention preservation）：Ellis-Gibbs 强调 OT 要保的不只是”最终一致”，还要保用户意图。比如你想”把这个词加粗”，不应被并发操作意外取消。这比单纯收敛要求高。
server 是单点：Jupiter 简化为 client-server 后，server 一挂就全停。CRDT 派天生 P2P，这是它的卖点之一。
复杂操作难变换：纯 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 年：Xerox PARC 的 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。两条路都不易。

学到什么

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

关联

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

反向链接

crdt-json —— CRDT JSON — 协同编辑 JSON 数据结构
jupiter-1995 —— Jupiter — 把 OT 简化成 client-server，让协同编辑能上工业
logoot-2010 —— Logoot — 给每个字符发一张”永不过期的座位号”
sharedb —— ShareDB — 基于 OT 的实时数据库