协作编辑系统 — 让上百人同时敲一个文档还能收敛Collaborative Editing: OT vs CRDT, Conflict Resolution, Offline Sync

问题场景 + 需求约束

设计一个 Google Docs / Figma 级的实时协作编辑器：单文档最多上百个活跃编辑者同时敲键盘，每次击键即一个操作，所有人 <100ms 内看到彼此的光标和文字，允许任意时长离线编辑、重连后自动合并。核心难点只有一个：两个人同时在同一位置插入字符，最终所有副本必须收敛到字节完全一致的状态——否则文档就分叉了。

• 并发模型：单文档 active editor 通常 <100，但击键频率高（人均 5-10 ops/s），presence（光标/选区）更新更频繁。
• 延迟 SLO：本地击键必须 0 延迟回显（optimistic 本地先行），远端感知 <100ms。
• 一致性：要求 强最终一致（Strong Eventual Consistency）——收到相同 op 集合的副本状态必须相同，与到达顺序无关。
• 离线：断网可编辑任意时长，重连合并不丢改动、不需人工解冲突。

高层架构

核心是 每个文档一个专属服务进程作为权威（authority），把所有 op 串行化成全序日志后广播。客户端永远本地先行渲染，把 op 乐观应用后再异步发往服务端；服务端确认（ack）后本地把它转正。光标/选区这类 presence 走单独临时通道，永不落盘。文档冷却后 snapshot 落存储、进程回收。

关键技术点

1. OT（操作变换）— 用中心串行化换纯文本、零 metadata

核心 trade-off：数据结构就是一段纯文本（无膨胀），代价是 transform 函数极难写对、且强依赖中心服务器定序。

【原理】每个操作携带位置索引（如「在第 5 位插入 X」）。当两个并发操作基于同一状态产生时，直接按各自索引应用会发散。OT 的做法是定义变换函数 T(op_a, op_b)：把 op_a 相对于「已经应用了 op_b」的世界重新计算位置。例如 A 在位置 2 插入、B 在位置 5 插入，B 到达 A 时其位置要 +1（因为 A 已经把后面撑长了）。所有副本沿不同路径 transform，最终收敛到同一状态。

# insert vs insert 的位置变换（简化）
def transform(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 op_a.shift(+len(op_b))    # 被 b 推后
    else:  # 同一位置并发插入 —— 需要 tie-break
        if op_a.site_id < op_b.site_id:  # 用站点 id 定序，保证对称
            return op_a
        return op_a.shift(+len(op_b))

难点在正确性属性 TP1/TP2：TP1 要求两 op 交换应用后收敛，TP2 要求三个以上并发 op 无论 transform 顺序都收敛。TP2 在去中心化（无全序）下极难满足——学术界多个已发表 OT 算法后来被证明存在反例。工业界的规避法：用中心服务器强制全序，从而只需保证 TP1（Jupiter 算法的关键洞察）。

2. CRDT 序列 — 用稠密位置标识换「无需中心协调」

核心 trade-off：操作天生可交换、可离线/P2P 合并，代价是每个字符背负 metadata + 墓碑永不消失。

【原理】CRDT 不做 transform，而是给每个字符分配一个全局唯一、稠密可比较的位置标识（fractional index / 树上路径）。两个字符之间永远能再插入一个 id（稠密性）。插入 = 生成一个夹在左右邻居 id 之间的新 id；删除 = 打墓碑（tombstone）而非物理移除（否则并发引用会指向空）。因为每个 op 只依赖不可变的 id、不依赖当前索引，任意顺序应用同一批 op 结果相同——这就是 Strong Eventual Consistency，无需中心定序。

# RGA 风格插入：id = (逻辑时钟, site_id)，按 (前驱 id) 定位
def insert_after(pred_id, char, site_id, clock):
    new_id = (clock, site_id)           # 全局唯一
    node = Node(id=new_id, char=char, after=pred_id, deleted=False)
    # 同一 pred 下的并发插入，按 id 降序排（tie-break 保证各副本一致）
    insert_sorted(node, key=lambda n: n.id, desc=True)
    return new_id

def delete(target_id):
    nodes[target_id].deleted = True     # 墓碑，不物理删

两个著名的坑：①metadata 膨胀——每字符一个 id，朴素实现可达 100:1 的开销；②interleaving 异常——两人并发各插入一整段文字，某些 CRDT 算法会把两段字符级交错成乱码（Kleppmann 等 2019 年专门有论文剖析）。

3. 离线优先与因果合并 — CRDT 真正拉开差距的地方

核心 trade-off：OT 重连要拿着旧基线跟服务端缺失的 op 逐一 transform（服务端必须保留 op log）；CRDT 只需交换彼此缺的 op 直接合并——离线越久优势越大。

【原理】客户端用 version vector（每个 site 的最大逻辑时钟）描述「我已经见过哪些 op」。重连时双方交换 version vector，只补发对方缺的增量。因果顺序由 op 携带的依赖（前驱 id / 逻辑时钟）保证——一个插入 op 必须在它的前驱可见后才能应用。CRDT 的可交换性让「补发的 op 乱序到达」也能正确合并，这正是离线场景的杀手锏。

4. 服务端架构 — per-document 单写权威 + 快照截断

核心 trade-off：每文档单进程串行化，隔离好、逻辑简单、天然全序；代价是热文档单点吞吐有上限、需要处理进程路由与迁移。

【原理】路由层用 consistent hash(doc_id) 把一个文档的所有连接固定到同一个进程。该进程单线程串行处理 op → 保证全序（OT 借此只需 TP1）→ 广播给订阅者 → 追加 op log。op log 无限增长，故定期做 snapshot（物化当前文档 + 版本向量）并截断旧日志；同时借机 GC 已无并发引用的墓碑。新客户端加入直接拉最近 snapshot + 少量增量，而非重放全部历史。

扩展与优化

• 大文档分块：把一个巨型文档切成多个子 CRDT / 段，按需加载，避免开一个文档就把上百万节点全灌进内存。
• Rich text：纯序列 CRDT 处理不好「加粗跨越并发插入」这类富文本，需 Peritext 式的区间标记 CRDT。
• 墓碑 GC：当且仅当所有副本都已确认某删除（version vector 越过）才能真正回收，否则会破坏并发引用。
• Undo/Redo：协作下的 undo 是撤销自己的操作而非「时间回退」，需 per-user 的可选择性撤销语义。
• 多区域：给文档一个归属 region（authority 所在），跨区编辑走归属区，避免全球强一致的往返延迟。

常见陷阱 + 面试追问

• OT transform 函数写错：insert/delete/delete 各种组合 + tie-break 极易出 bug，且错了是「静默发散」——两人文档不一致却无报错。面试要能说出 TP1/TP2 与「靠中心服务器规避 TP2」。
• CRDT interleaving：会追问「两人各粘贴一段话，为什么可能交错？」——答：并发插入落在同一 anchor 之间，tie-break 只保证收敛不保证语义连贯。
• 墓碑无限增长：长寿文档删了又删，墓碑不回收会拖垮内存/带宽；GC 条件是面试深挖点。
• LWW 丢更新：Figma 对属性用 LWW，两人同时改颜色会丢一个——要能说清「什么场景可接受丢、什么不可」（文本不可，设计属性可）。
• presence 落盘：把光标位置当持久数据存是典型过度设计——它是易失的、可丢的。
• 选 OT 还是 CRDT？「有稳定中心服务器、要纯文本无膨胀、团队能 hold 住 transform」→ OT（Google Docs）；「要离线优先/P2P/本地优先、能接受 metadata 开销」→ CRDT（Yjs/Automerge）。

深入资源

• How Figma's multiplayer technology works — Evan Wallace 讲 server-per-document、离线重连、LWW 属性，工业界最好读的一篇。
• CRDTs: The Hard Parts — Martin Kleppmann，讲 metadata 膨胀、columnar encoding、interleaving 等真实难点。
• Interleaving anomalies in collaborative text editors（PaPoC 2019）— 交错异常的形式化剖析。
• Yjs（Kevin Jahns，YATA）与 Automerge — 两个最主流的生产级 CRDT 实现，源码即教材。
• Jupiter 算法（Nichols et al., AT&T, 1995）与 Google Wave OT 白皮书 — OT 中心化定序的源头。

深入思考