代码题在线协作编辑的技术实现：Operational Transformation 入门
一、深度引言与场景痛点：面试中的"你能在这里修改一下吗？"
在一次真实的技术面试中，面试官在白板出了一道算法题。我写完初版代码后，面试官说："这里可以优化一下，把 O(n²) 的查找换成哈希表。"我拿起笔在代码中间改了几行。这个场景的线上版本是这样的：面试官和候选人在同一个代码编辑器中，面试官可以实时修改代码、添加注释、标记问题。
但实现这个功能的技术难度远超想象。Google Docs 能做到多人实时协作，因为他们在 2006 年就发明了 Operational Transformation（OT）算法。本文将介绍 OT 的核心思想，以及在技术面试场景下的简化实现。
二、底层机制与原理深度剖析
冲突问题
多人编辑同一个文档时，最大的问题是操作冲突。假设原始文档是 "Hello"：
- 用户 A 在位置 0 插入 "A" → 文档变为 "AHello"
- 用户 B 在位置 2 删除 1 个字符 → 预期文档是 "Helo"，但此时位置 2 已经是 "l"
如果直接应用两个操作，结果会是错误的。OT 的核心思想是：当两个操作发生冲突时，通过转换（Transform）使其在新的上下文中仍然正确。
三、生产级代码实现与最佳实践
适用于面试场景的简化 OT 实现
// Operational Transformation 核心实现 —— 适用于面试代码协作场景 // 注：以下是简化版，完整的 OT 需要处理更复杂的组合冲突 // ========== 操作定义 ========== // 两种基本操作类型：插入（insert）和删除（delete） // retain 用于 tell 服务器"保持这些字符不变，基于此位置执行操作" class TextOperation { constructor() { this.ops = []; // [{type: 'retain'|'insert'|'delete', value}] } // 保持 n 个字符不变 —— 本质上是"移动光标" retain(n) { if (n === 0) return this; // 合并连续的 retain 操作 if (this.ops.length > 0 && this.ops[this.ops.length - 1].type === 'retain') { this.ops[this.ops.length - 1].value += n; } else { this.ops.push({ type: 'retain', value: n }); } return this; } // 插入字符串 —— 在当前光标位置插入 insert(str) { if (str === '') return this; // 合并连续的 insert 操作 if (this.ops.length > 0 && this.ops[this.ops.length - 1].type === 'insert') { this.ops[this.ops.length - 1].value += str; } else { this.ops.push({ type: 'insert', value: str }); } return this; } // 删除 n 个字符 —— 从当前光标位置开始删除 delete(n) { if (n === 0) return this; // 合并连续的 delete 操作 if (this.ops.length > 0 && this.ops[this.ops.length - 1].type === 'delete') { this.ops[this.ops.length - 1].value += n; } else { this.ops.push({ type: 'delete', value: n }); } return this; } // 应用操作到文档 apply(doc) { let result = ''; let pos = 0; for (const op of this.ops) { if (op.type === 'retain') { result += doc.slice(pos, pos + op.value); pos += op.value; } else if (op.type === 'insert') { result += op.value; // pos 不变（因为 insert 不消耗原文档字符） } else if (op.type === 'delete') { pos += op.value; // 跳过被删除的字符 } } return result; } } // ========== 操作转换（OT 核心）========== /** * Transform 两个并发操作 * 输入：op1 和 op2 是两个并发操作（基于相同的文档状态） * 输出：[op1Prime, op2Prime] * - op1Prime = op1 经过转换后，可以应用在 op2 的结果上 * - op2Prime = op2 经过转换后，可以应用在 op1 的结果上 * * 数学性质：apply(apply(doc, op1), op2Prime) == apply(apply(doc, op2), op1Prime) */ function transform(op1, op2) { const op1Prime = new TextOperation(); const op2Prime = new TextOperation(); let i1 = 0, i2 = 0; let op1Part, op2Part; while (i1 < op1.ops.length || i2 < op2.ops.length) { op1Part = op1.ops[i1]; op2Part = op2.ops[i2]; // 情况 1：两个操作都是 insert —— 不会互相影响 // 谁的 insert 在前面，谁就保持原样 if (op1Part && op1Part.type === 'insert') { op1Prime.insert(op1Part.value); i1++; continue; } if (op2Part && op2Part.type === 'insert') { op2Prime.insert(op2Part.value); i2++; continue; } // 如果有一方已处理完，退出循环 if (!op1Part || !op2Part) break; // 情况 2：都是 retain if (op1Part.type === 'retain' && op2Part.type === 'retain') { const minLen = Math.min(op1Part.value, op2Part.value); op1Prime.retain(minLen); op2Prime.retain(minLen); op1Part.value -= minLen; op2Part.value -= minLen; if (op1Part.value === 0) i1++; if (op2Part.value === 0) i2++; continue; } // 情况 3：op1 delete, op2 retain // op1 删掉了字符，op2 的 retain 应该减少对应数量的字符 if (op1Part.type === 'delete' && op2Part.type === 'retain') { const minLen = Math.min(op1Part.value, op2Part.value); op1Prime.delete(minLen); // op2Prime 什么都不做（字符已被删除，retain 跳过它们） op1Part.value -= minLen; op2Part.value -= minLen; if (op1Part.value === 0) i1++; if (op2Part.value === 0) i2++; continue; } // 情况 4：op1 retain, op2 delete if (op1Part.type === 'retain' && op2Part.type === 'delete') { const minLen = Math.min(op1Part.value, op2Part.value); op2Prime.delete(minLen); op1Part.value -= minLen; op2Part.value -= minLen; if (op1Part.value === 0) i1++; if (op2Part.value === 0) i2++; continue; } // 情况 5：两个都是 delete —— 取较小的，因为已被删除一次 if (op1Part.type === 'delete' && op2Part.type === 'delete') { const minLen = Math.min(op1Part.value, op2Part.value); op1Part.value -= minLen; op2Part.value -= minLen; if (op1Part.value === 0) i1++; if (op2Part.value === 0) i2++; continue; } } // 处理剩余的操作 while (i1 < op1.ops.length) { const part = op1.ops[i1++]; if (part.type === 'retain') op1Prime.retain(part.value); else if (part.type === 'insert') op1Prime.insert(part.value); else if (part.type === 'delete') op1Prime.delete(part.value); } while (i2 < op2.ops.length) { const part = op2.ops[i2++]; if (part.type === 'retain') op2Prime.retain(part.value); else if (part.type === 'insert') op2Prime.insert(part.value); else if (part.type === 'delete') op2Prime.delete(part.value); } return [op1Prime, op2Prime]; } // ========== 协作客户端 ========== class CollaborationClient { constructor(docId, initialDoc) { this.docId = docId; this.document = initialDoc; this.version = 0; // 已确认的版本号 this.pendingOps = []; // 等待服务器确认的本地操作 this.ws = null; } // 本地用户执行编辑操作 applyLocal(operation) { // 1. 立即应用到本地文档（乐观更新，不需要等待服务器响应） this.document = operation.apply(this.document); // 2. 发送到服务器 this.sendOperation(operation); // 3. 缓存待确认的操作 this.pendingOps.push(operation); } sendOperation(operation) { // 使用版本号，服务器可以检测并发冲突 this.ws.send(JSON.stringify({ type: 'operation', docId: this.docId, version: this.version, operation: operation.serialize() })); } // 收到服务器广播的远程操作 receiveRemote(remoteOperation, remoteVersion) { // 如果远程操作和本地操作有并发（版本相同），需要转换 if (remoteVersion === this.version) { // 将远程操作和每个本地待处理操作进行转换 let remotePrime = remoteOperation; for (let i = 0; i < this.pendingOps.length; i++) { const [localPrime, rPrime] = transform(this.pendingOps[i], remotePrime); this.pendingOps[i] = localPrime; remotePrime = rPrime; } this.document = remotePrime.apply(this.document); } else { // 如果没有并发冲突，直接应用 this.document = remoteOperation.apply(this.document); } this.version++; } }四、边界分析与架构权衡
OT vs CRDT
近年来，CRDT（Conflict-free Replicated Data Type）作为 OT 的替代方案越来越受欢迎。两者的对比如下：
| 特性 | OT | CRDT |
|---|---|---|
| 一致性模型 | 强一致性（需要中心服务器） | 最终一致性（支持 P2P） |
| 实现复杂度 | 中等（Transform 函数难写） | 高（数据结构复杂） |
| 性能 | 好 | 内存占用较大 |
| 成熟度 | 成熟（Google Docs 使用） | 较新 |
| 适用场景 | 实时协作编辑 | 离线优先应用 |
对于面试场景，OT 更适合。因为：
- 面试是实时同步的，天然有中心服务器
- 编辑操作简单（主要是代码修改），OT 能很好地处理
- 两名参与者（候选人 + 面试官），并发冲突概率低
面试场景的简化
完整实现 OT 需要处理 undo/redo、光标同步、选区高亮等功能。但在面试场景下，可以做以下简化：
- 只支持文本的插入和删除，不支持富文本格式
- 不需要 undo/redo（面试中不需要回退）
- 非对称权限：面试官可以修改代码，候选人也可以修改自己的代码
- 高亮面试官修改的内容，方便候选人理解改了哪里
五、总结
OT 是一个经典的分布式一致性算法。它的核心思想很简单——通过操作转换让并发操作在新的上下文中保持一致——但实现细节处理需要非常仔细。
对于技术面试协作编辑场景，有几个关键简化可以大幅降低实现难度：
- 限制同时编辑的人数为 2（候选人 + 面试官）
- 不实现 undo/redo，因为面试场景不需要
- 使用 WebSocket保证消息有序到达（减少了乱序处理的复杂度）
最有趣的一个观察是：OT 的 Transform 函数需要满足 CP1（收敛性质），即 apply(apply(doc, op1), op2Prime) == apply(apply(doc, op2), op1Prime)。写单测时，可以用大量随机操作来验证这个性质是否成立。我在第一次实现时，因为一种边界情况没处理对，单测的随机验证帮我找出了 bug。
