代码题在线协作编辑的技术实现Operational Transformation 入门一、深度引言与场景痛点面试中的你能在这里修改一下吗在一次真实的技术面试中面试官在白板出了一道算法题。我写完初版代码后面试官说这里可以优化一下把 O(n²) 的查找换成哈希表。我拿起笔在代码中间改了几行。这个场景的线上版本是这样的面试官和候选人在同一个代码编辑器中面试官可以实时修改代码、添加注释、标记问题。但实现这个功能的技术难度远超想象。Google Docs 能做到多人实时协作因为他们在 2006 年就发明了 Operational TransformationOT算法。本文将介绍 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; } // 情况 3op1 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; } // 情况 4op1 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近年来CRDTConflict-free Replicated Data Type作为 OT 的替代方案越来越受欢迎。两者的对比如下特性OTCRDT一致性模型强一致性需要中心服务器最终一致性支持 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。