各位同仁，各位对分布式系统与协同编辑充满热情的开发者们：
今天，我们将深入探讨一个在现代软件工程中至关重要的算法基石——操作转换（Operational Transformation，简称OT）。它不仅仅是一个抽象的理论，更是Google Docs、腾讯文档等无数实时协同编辑工具的心脏。想象一下，多人同时在同一文档上编辑，每个人都在自由地输入、删除、格式化，而最终所有人看到的文档内容却能奇迹般地保持一致，并且完美地反映了所有人的意图——这并非魔法，而是OT的精妙之处。
协同编辑的挑战与OT的诞生
在深入OT的细节之前，我们首先要理解它所解决的核心问题：并发性与一致性。
考虑一个简单的文本编辑器，如果只有一个用户，所有操作都是线性的，毫无疑问。但当多个用户同时编辑同一个文档时，情况就变得复杂了。
朴素的解决方案的局限性：
-
“最后写入者获胜”（Last Write Wins）： 这种策略最简单，但也是最粗暴的。如果用户A在位置0插入"Hello"，用户B在位置0插入"World"，那么最终文档将只保留其中一个操作的结果，另一个用户的编辑将被无情覆盖。这显然无法满足协同编辑的需求，因为用户的“意图”被完全忽略了。
-
锁定机制（Locking）： 另一种常见方法是锁定。例如，当一个用户编辑某个段落时，其他用户无法编辑该段落。这能保证数据一致性，但极大地牺牲了并发性，用户体验非常差，与实时协同的目标背道而驰。
-
合并与冲突解决（Merge and Conflict Resolution）： 像Git这样的版本控制系统，在用户提交各自的更改后，会进行合并。如果存在冲突，则需要人工介入解决。这种方式适用于异步、非实时的协作，但在毫秒级的实时协同场景中，让用户频繁手动解决冲突是不可接受的。
协同编辑的真正挑战在于，我们希望：
- 实时性： 用户的操作应立即反映在文档中，并尽快同步给其他用户。
- 收敛性（Convergence）： 无论操作的到达顺序如何，所有用户最终看到的文档状态都应该是一致的。
- 意图保存（Intention Preservation）： 每个用户的操作都应该在最终文档中体现出其预期的效果，即使在并发操作下也应如此。
为了应对这些挑战，OT应运而生。它不是简单地覆盖或合并，而是一种动态调整操作的机制，确保当操作应用于一个已经被其他并发操作修改过的文档状态时，它仍然能够实现其原始意图。
核心概念：操作、状态与冲突
在OT的世界里，有几个核心概念是我们理解其工作原理的基础。
操作（Operation）
在OT中，文档的每一次修改都被抽象为一个“操作”。一个操作是文档从一个状态转换到另一个状态的原子性描述。对于文本编辑而言，最基本的操作通常包括：
- 插入（Insert）： 在特定位置插入一段文本。
- 删除（Delete）： 从特定位置删除一段文本。
- 保留/保持（Retain）： 跳过或保留特定数量的字符，通常用于表示操作不影响文档的某个部分，或者作为操作的一部分描述。
操作的结构示例：
一个操作通常包含位置信息和内容/长度信息。
| 字段 | 类型 | 描述 类型： RetainOperation | InsertOperation | DeleteOperation
|———-|———-|———————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————— ——————–|—————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————-OT 全称 Operational Transformation，中文通常称为“操作转换”。在当今这个高度互联的世界，多人实时协同编辑已成为现代办公和在线协作的基础设施。从Google Docs、腾讯文档到飞书文档，甚至是我们日常使用的代码编辑器，背后都有OT或其变体在默默工作。作为一名编程专家，我将带大家深入剖解OT，揭示其如何成为实现实时协同编辑的算法基石。
1. 协同编辑的挑战与OT的诞生
想象一下，你和你的同事正在共同撰写一份重要报告。你负责引言部分，他负责结论。当你们同时修改文档时，如果没有一个智能的机制来协调这些修改，那么最终的文档很可能会变成一团糟：你的修改可能覆盖他的，或者他的修改让你的编辑失去上下文。这就是协同编辑面临的根本挑战：如何处理并发操作，并确保所有用户最终都能看到一个一致且准确反映所有人意图的文档状态。
早期的协同编辑尝试往往采用“锁定”机制，即当一个用户编辑某个区域时，其他用户无法修改。这种方法虽然保证了数据的一致性，但极大地牺牲了并发性，用户体验极差，与“实时协同”的愿景背道而驰。
随着互联网技术的发展和对实时交互体验的追求，我们需要一种更精巧的解决方案。这种方案必须具备以下关键特性：
- 收敛性 (Convergence): 无论并发操作的顺序如何，所有参与者最终都必须能看到相同的文档状态。
- 意图保存 (Intention Preservation): 每个操作的语义和效果都应在最终文档中得到保留，即使在并发操作的影响下，操作执行的“意图”也不应被扭曲。
- 因果顺序保持 (Causality Preservation): 如果一个操作是基于另一个操作的结果而产生的，那么在最终文档中，这两个操作的相对顺序必须得到尊重。
正是在这样的背景下，操作转换 (OT) 理论在20世纪80年代末被提出，并在随后的几十年里不断发展和完善，成为解决实时协同编辑问题的最经典和广泛应用的算法。
OT的核心思想是：当一个操作在客户端生成并发送到服务器或另一个客户端时，如果在此期间文档状态发生了变化，那么这个操作在应用之前，需要根据这些中间的变化进行“转换”，以确保它能正确地应用于新的文档状态，并保持其原始意图。
2. OT的核心概念：操作、状态与转换函数
理解OT，首先要理解其基本构成要素。
2.1 文档与操作
在OT中，我们把文档看作是一个状态，而对文档的每一次修改都抽象为一个操作 (Operation)。对于纯文本，最基本的操作类型有三种：
- 插入 (Insert): 在文档的某个位置插入一段文本。
- 删除 (Delete): 从文档的某个位置删除指定长度的文本。
- 保留 (Retain): 表示跳过文档的某个部分，不做任何修改。这在描述一个操作对文档影响的范围时非常有用，特别是在组合和转换操作时。
为了方便表示和处理，一个操作通常被描述为一个操作序列，每个元素是上述三种类型之一。例如，一个操作可能表示为 [retain(5), insert("World"), delete(2), retain(3)]，意味着：跳过前5个字符，插入"World"，删除2个字符，再跳过3个字符。
示例：一个简单的文本操作表示
假设文档内容是 "hello"。
- 在位置0插入 "W"：
[insert("W"), retain(5)] - 删除位置2开始的3个字符 "llo"：
[retain(2), delete(3)] - 在位置5插入 "!"：
[retain(5), insert("!")]
我们可以用一个类来表示这些操作：
import json
class TextOperation:
"""
表示一个对文本进行修改的操作。
一个操作由一系列子操作组成，每个子操作可以是 'retain', 'insert', 'delete'。
"""
def __init__(self, ops=None):
self.ops = ops if ops is not None else []
self._cursor = 0 # 用于辅助apply和compose操作时的光标位置
def __repr__(self):
return f"TextOperation({self.ops})"
def insert(self, text):
if not text:
return self
self.ops.append({'type': 'insert', 'value': text})
self._cursor += len(text)
return self
def delete(self, length):
if length <= 0:
return self
self.ops.append({'type': 'delete', 'length': length})
return self
def retain(self, length):
if length <= 0:
return self
self.ops.append({'type': 'retain', 'length': length})
self._cursor += length
return self
def apply(self, text):
"""将当前操作应用于给定的文本，返回新的文本。"""
new_text = []
text_cursor = 0
for op in self.ops:
op_type = op['type']
if op_type == 'retain':
length = op['length']
new_text.append(text[text_cursor : text_cursor + length])
text_cursor += length
elif op_type == 'insert':
new_text.append(op['value'])
elif op_type == 'delete':
length = op['length']
text_cursor += length # 实际删除，所以跳过原文本
else:
raise ValueError(f"未知操作类型: {op_type}")
# 如果操作没有完全覆盖原文本，则保留剩余部分
new_text.append(text[text_cursor:])
return "".join(new_text)
# 简化版，用于演示。实际中需要更复杂的规范化
def normalize(self):
"""规范化操作序列，合并相邻的同类型操作等。"""
normalized_ops = []
for op in self.ops:
if op['type'] == 'insert' and normalized_ops and normalized_ops[-1]['type'] == 'insert':
normalized_ops[-1]['value'] += op['value']
elif op['type'] == 'delete' and normalized_ops and normalized_ops[-1]['type'] == 'delete':
normalized_ops[-1]['length'] += op['length']
elif op['type'] == 'retain' and normalized_ops and normalized_ops[-1]['type'] == 'retain':
normalized_ops[-1]['length'] += op['length']
elif (op['type'] == 'insert' and not op['value']) or
(op['type'] == 'delete' and op['length'] == 0) or
(op['type'] == 'retain' and op['length'] == 0):
# 忽略空操作
pass
else:
normalized_ops.append(op)
self.ops = normalized_ops
return self
def _clone(self):
"""克隆当前操作，用于转换函数中生成新操作。"""
return TextOperation(json.loads(json.dumps(self.ops))) # Deep copy2.2 文档状态 (Document State)
文档状态就是特定时刻的文档内容。在协同编辑中，每个客户端和服务器都维护一个文档状态。但由于网络延迟，这些状态可能在短时间内不一致。OT的目标就是通过转换操作，使这些不一致的状态最终收敛到一致。
2.3 转换函数 (Transformation Function)
这是OT的核心所在。转换函数 transform(op1, op2) 接收两个并发操作 op1 和 op2，这两个操作都基于同一个初始文档状态 S。它的任务是生成两个新的操作 op1' 和 op2'，使得：
op1'可以正确地应用于S经过op2后的状态 (S + op2)。op2'可以正确地应用于S经过op1后的状态 (S + op1)。- 最重要的是，收敛性条件：
S + op1 + op2'必须等于S + op2 + op1'。 这意味着无论先应用op1后应用op2'，还是先应用op2后应用op1'，最终的文档状态都应该相同。
这个过程可以用一个通勤图来表示：
S
/
/
op1 op2
/
S+op1 S+op2
/
op2' op1'
/
/
S+op1+op2' == S+op2+op1'transform 函数的实现是OT算法最复杂的部分，它需要考虑各种操作类型组合（插入对插入、插入对删除、删除对插入、删除对删除）以及它们在文档中的相对位置。
3. OT的核心算法：深入转换函数的逻辑
让我们通过详细的例子和伪代码来理解 transform 函数如何处理不同类型的操作组合。
假设我们有两个操作 opA 和 opB，它们都基于相同的初始文档状态 S。我们要计算 opA_prime (应用于 S + opB) 和 opB_prime (应用于 S + opA)。
为了实现 transform，我们通常会设计一个 transform_pair(op1_component, op2_component) 函数，处理操作序列中的一对原子组件。
转换规则的核心思想：
- 位置调整： 如果一个操作在另一个操作之前插入了内容，那么后续操作的索引位置需要向后移动。如果删除了内容，则需要向前移动。
- 内容冲突： 两个插入操作在同一位置插入，或者一个操作删除另一个操作插入的内容，需要特殊的处理来确保意图保存。
我们来定义一个 transform_pair 函数，它接收两个操作 op1 和 op2 的当前子操作（例如 {'type': 'insert', 'value': 'A'} 或 {'type': 'retain', 'length': 5}），并返回一对转换后的子操作。
3.1 transform 函数的实现细节
我们将构建一个 transform 方法，它会遍历 op1 和 op2 的操作序列，逐对处理它们的子操作。
class TextOperation:
# ... (之前的代码) ...
def transform(self, other_op):
"""
根据另一个并发操作 other_op 转换当前操作 self。
返回 (self_prime, other_op_prime)
self_prime 是 self 转换后的操作，可以应用于 original_doc + other_op
other_op_prime 是 other_op 转换后的操作，可以应用于 original_doc + self
"""
self_prime = TextOperation()
other_op_prime = TextOperation()
idx1, idx2 = 0, 0
ops1, ops2 = self.ops, other_op.ops
while idx1 < len(ops1) or idx2 < len(ops2):
op1_component = ops1[idx1] if idx1 < len(ops1) else None
op2_component = ops2[idx2] if idx2 < len(ops2) else None
# 情况1: op1 是插入操作
if op1_component and op1_component['type'] == 'insert':
self_prime.insert(op1_component['value'])
idx1 += 1
continue # op1的插入不影响op2的位置，但op2的插入会影响op1
# 情况2: op2 是插入操作
if op2_component and op2_component['type'] == 'insert':
other_op_prime.insert(op2_component['value'])
idx2 += 1
continue # op2的插入不影响op1的位置，但op1的插入会影响op2
# 如果op1或op2已经处理完，但另一个还有retain/delete，则需要处理剩余部分
if not op1_component and op2_component:
# op1 已经处理完，op2 还有 delete/retain
# 这意味着 op2_component 应该应用于 op1 已经完成后的文档
# 但由于 op1 没做任何操作，op2_component 保持不变
# 这只有在文档末尾时才会发生，因为前面的 retain/delete 会匹配
if op2_component['type'] == 'retain':
other_op_prime.retain(op2_component['length'])
idx2 += 1
elif op2_component['type'] == 'delete':
other_op_prime.delete(op2_component['length'])
idx2 += 1
continue
if not op2_component and op1_component:
# 同理，op2 处理完，op1 还有 delete/retain
if op1_component['type'] == 'retain':
self_prime.retain(op1_component['length'])
idx1 += 1
elif op1_component['type'] == 'delete':
self_prime.delete(op1_component['length'])
idx1 += 1
continue
# 以下情况，op1_component 和 op2_component 都是 retain 或 delete
# 情况3: op1 和 op2 都是 retain
if op1_component['type'] == 'retain' and op2_component['type'] == 'retain':
length = min(op1_component['length'], op2_component['length'])
self_prime.retain(length)
other_op_prime.retain(length)
op1_component['length'] -= length
op2_component['length'] -= length
if op1_component['length'] == 0: idx1 += 1
if op2_component['length'] == 0: idx2 += 1
continue
# 情况4: op1 是 delete
if op1_component['type'] == 'delete':
if op2_component['type'] == 'delete': # op1 delete, op2 delete
# 共同删除的部分，两个操作都不能再次删除
length = min(op1_component['length'], op2_component['length'])
op1_component['length'] -= length
op2_component['length'] -= length
# 对于冲突的删除，我们通常选择一个操作“胜出”，或者都忽略
# 这里的处理是：两个操作都将该部分从原始文档中删除，
# 转换后，它们不再需要删除这部分（因为已经被另一个操作删除了）
# 所以 self_prime 和 other_op_prime 都不需要包含这部分的删除
# 只需要处理剩余的非冲突删除
if op1_component['length'] == 0: idx1 += 1
if op2_component['length'] == 0: idx2 += 1
continue
else: # op1 delete, op2 retain
# op1 删除的区域，op2 保留。
# op1_prime: 仍然删除该区域
# op2_prime: 不再保留该区域 (因为它被op1删除了)
length = min(op1_component['length'], op2_component['length'])
self_prime.delete(length) # op1 删除这部分
# other_op_prime 不做任何操作，因为 op1 删除了它想保留的部分
op1_component['length'] -= length
op2_component['length'] -= length
if op1_component['length'] == 0: idx1 += 1
if op2_component['length'] == 0: idx2 += 1
continue
# 情况5: op2 是 delete
if op2_component['type'] == 'delete': # op2 delete, op1 retain
# op2 删除的区域，op1 保留。
# other_op_prime: 仍然删除该区域
# self_prime: 不再保留该区域 (因为它被op2删除了)
length = min(op1_component['length'], op2_component['length'])
other_op_prime.delete(length) # op2 删除这部分
# self_prime 不做任何操作，因为 op2 删除了它想保留的部分
op1_component['length'] -= length
op2_component['length'] -= length
if op1_component['length'] == 0: idx1 += 1
if op2_component['length'] == 0: idx2 += 1
continue
return self_prime.normalize(), other_op_prime.normalize()
# 将transform方法添加到TextOperation类中
TextOperation.transform = transform对 transform 逻辑的进一步解释：
-
insertvsinsert:opA: insert("A") at pos XopB: insert("B") at pos X- 如果
opA先应用，文档变成...A...。opB必须转换为在A之后插入B，即insert("B") at pos X+len("A")。 - 如果
opB先应用，文档变成...B...。opA必须转换为在B之后插入A，即insert("A") at pos X+len("B")。 - 为了实现收敛，需要定义一个优先级规则。例如，根据客户端ID或时间戳决定哪个插入先发生。在上面的简化代码中，它会直接将
insert添加到self_prime或other_op_prime。更健壮的OT会根据优先级在同一位置插入时调整位置。通常的规则是，如果两个插入在同一个位置，具有更高优先级（例如，更早的操作，或更小的客户端ID）的插入会先发生，另一个的插入位置会后移。 - 在我的示例代码中，
insert操作是立即添加到_prime操作中，并且不消耗任何retain或delete的长度。这意味着插入操作会“挤开”后续的操作。这个逻辑是正确的：一个插入操作会影响后续所有操作的索引。
-
insertvsdelete:opA: insert("X") at pos PopB: delete(L) at pos P'- 如果
P < P'：opA的插入会使得opB的删除位置后移len("X")。 - 如果
P > P':opB的删除会使得opA的插入位置前移L。 - 如果
P在P'正在删除的范围内：opA插入的内容会被opB删除。opA'需要调整位置，opB'需要调整删除长度。更复杂的OT实现会根据意图保存原则，决定是保留插入还是保留删除。 比如，如果插入发生在删除的内部，那么插入的内容不应该被删除。我的简化代码中，插入操作在处理时总是先完成，因此它不会被其他删除操作“吃掉”，这是符合某些OT模型的意图保存的。
-
insertvsretain:opA: insert("X") at pos PopB: retain(L) at pos P'- 如果
P < P'：opA的插入会使得opB的保留位置后移len("X")。opB的retain长度不变，但opA需要在retain之前插入。 - 如果
P > P'：opB的retain会使得opA的插入位置前移L。opA在retain之后插入。 - 在我的代码中，
insert操作优先处理，它不消耗retain的长度，但会直接加入到_prime操作中，这隐式地调整了后续操作的上下文。
-
deletevsdelete:opA: delete(L1) at pos PopB: delete(L2) at pos P'- 如果两个删除区域不重叠，则它们只是简单地调整彼此的位置。
- 如果两个删除区域重叠：重叠部分不能被删除两次。通常，转换后的操作会只删除未被另一个操作删除的部分。例如，如果
opA删除[P, P+L1)，opB删除[P', P'+L2)，且[P, P+L1)完全包含[P', P'+L2)，那么opA'仍然删除[P, P+L1)，而opB'变成一个空操作，因为它要删除的部分已经被opA删除了。反之亦然。如果只是部分重叠，则需要计算非重叠部分。 - 我的代码中，
deletevsdelete的处理逻辑是：共同删除的部分，两个_prime操作都不再需要删除。各自未被另一个删除的部分，则继续删除。这是确保收敛性的关键。
-
deletevsretain:opA: delete(L) at pos PopB: retain(L') at pos P'- 如果
opA删除了opB想要保留的部分，那么opB'就不再需要保留这部分，它应该跳过这些被删除的字符。而opA'仍然需要执行删除。 - 我的代码中，
op1 delete, op2 retain意味着op1会删除min(L, L')长度的字符，self_prime会包含这个删除。而op2_prime不需要retain这部分，因为它们已经被op1删除了。 反之亦然。
一个具体的 transform 例子：
初始文档 S = "abcdef"
opA: 在位置2插入 "X" ->S + opA = "abXcdef"opA=[retain(2), insert("X"), retain(4)]
opB: 删除位置3的字符 ‘d’ ->S + opB = "abcef"opB=[retain(3), delete(1), retain(2)]
现在我们来计算 transform(opA, opB) 得到 (opA_prime, opB_prime)。
-
opA的第一个组件是retain(2)，opB的第一个组件是retain(3)。- 取
min(2, 3) = 2。 opA_prime.retain(2)opB_prime.retain(2)opA剩余insert("X"), retain(4)(已处理retain(2))opB剩余retain(1), delete(1), retain(2)(已处理retain(2))
- 取
-
opA当前组件是insert("X")。self_prime.insert("X")opA剩余retain(4)opB剩余retain(1), delete(1), retain(2)- 注意：插入操作会“挤开”后续操作的位置，但不会消耗
other_op的retain或delete长度。
-
opA当前组件是retain(4)，opB当前组件是retain(1)。- 取
min(4, 1) = 1。 self_prime.retain(1)other_op_prime.retain(1)opA剩余retain(3)opB剩余delete(1), retain(2)
- 取
-
opA当前组件是retain(3)，opB当前组件是delete(1)。opB是delete，opA是retain。- 取
min(3, 1) = 1。 other_op_prime.delete(1)(因为opB删除了这个字符)self_prime不做任何retain(因为opA想要保留的这个字符被opB删除了)opA剩余retain(2)opB剩余retain(2)
-
opA当前组件是retain(2)，opB当前组件是retain(2)。- 取
min(2, 2) = 2。 self_prime.retain(2)other_op_prime.retain(2)opA和opB都处理完毕。
- 取
最终结果：
opA_prime=[retain(2), insert("X"), retain(1), retain(2)]-> 规范化后[retain(2), insert("X"), retain(3)]opB_prime=[retain(2), retain(1), delete(1), retain(2)]-> 规范化后[retain(3), delete(1), retain(2)]
让我们验证收敛性：
-
S + opA = "abXcdef" -
S + opB = "abcef" -
S + opA + opB_prime: "abcdef" -> "abXcdef" (应用opA) -> "abXce f" (应用opB_prime：retain(3)跳过"abX"，delete(1)删除"c"，retain(2)跳过"ef")- 结果：
"abXef"
- 结果：
-
S + opB + opA_prime: "abcdef" -> "abcef" (应用opB) -> "abXcef" (应用opA_prime：retain(2)跳过"ab"，insert("X")插入"X"，retain(3)跳过"cef")- 结果：
"abXcef"
- 结果：
结果不一致！这说明我的 transform 简化实现，在 insert 和 delete 交叉时，没有正确处理优先级。opA_prime 的 retain(3) 是在 opA 原始插入之后，而 opB_prime 的 delete(1) 是在 opB 原始删除之后。
问题出在哪里？
当 opA 插入 "X" 时，它改变了文档长度，使得 opB 的删除位置需要调整。
当 opB 删除字符 ‘d’ 时，它改变了文档长度，使得 opA 的操作位置也需要调整。
我们必须严格遵循 transform 的定义：op1' 作用于 S + op2，op2' 作用于 S + op1。这意味着 op1' 在被生成时，需要假设 op2 已经发生，并根据 op2 对文档状态的改变来调整自身。反之亦然。
重新审视 insert vs retain 和 delete 的逻辑：
在 transform 函数中，关键在于如何正确地调整 retain 和 delete 的 length，以及插入操作的相对位置。
class TextOperation:
# ... (前面的代码省略，只保留transform方法的更严谨实现) ...
def transform(self, other_op):
"""
根据另一个并发操作 other_op 转换当前操作 self。
返回 (self_prime, other_op_prime)
self_prime 是 self 转换后的操作，可以应用于 original_doc + other_op
other_op_prime 是 other_op 转换后的操作，可以应用于 original_doc + self
"""
self_prime = TextOperation()
other_op_prime = TextOperation()
idx1, idx2 = 0, 0
ops1, ops2 = self.ops, other_op.ops
# 辅助函数，用于获取下一个非空操作组件
def get_next_op(ops, idx):
while idx < len(ops):
op = ops[idx]
if op['type'] == 'insert' and not op['value']:
idx += 1
continue
if op['type'] == 'delete' and op['length'] == 0:
idx += 1
continue
if op['type'] == 'retain' and op['length'] == 0:
idx += 1
continue
return op, idx
return None, idx
op1_component, idx1 = get_next_op(ops1, idx1)
op2_component, idx2 = get_next_op(ops2, idx2)
while op1_component or op2_component:
# Case 1: op1 is an insert
if op1_component and op1_component['type'] == 'insert':
# op1 的插入操作对 op2 的位置没有影响，因为 op1 是基于原始文档的
# 但 op1' 必须在 op2 已经发生后的文档上插入
# 如果 op2 在相同位置插入，通常需要一个优先级规则 (例如，客户端ID小的先)
# 这里简化处理：op1' 总是插入其内容
self_prime.insert(op1_component['value'])
idx1 += 1
op1_component, idx1 = get_next_op(ops1, idx1)
continue
# Case 2: op2 is an insert
if op2_component and op2_component['type'] == 'insert':
# op2 的插入操作对 op1 的位置没有影响
# 但 op2' 必须在 op1 已经发生后的文档上插入
# 为了保持意图，op2' 总是插入其内容
other_op_prime.insert(op2_component['value'])
idx2 += 1
op2_component, idx2 = get_next_op(ops2, idx2)
continue
# Case 3: Both are retain (or one/both are delete, but length needs to match)
# Both op1_component and op2_component must exist and be retain/delete now
if not op1_component or not op2_component:
# 理论上，如果 ops1 或 ops2 还有 retain/delete，而另一个已经处理完
# 这应该在循环开头处理，或者通过长度匹配来处理
# 如果走到这里，说明其中一个组件是 None，但前面的 insert 检查没通过
# 实际上应该不会发生，除非文档长度不匹配
raise Exception("Transform logic error: one op exhausted prematurely with retain/delete")
if op1_component['type'] == 'retain' and op2_component['type'] == 'retain':
length = min(op1_component['length'], op2_component['length'])
self_prime.retain(length)
other_op_prime.retain(length)
op1_component['length'] -= length
op2_component['length'] -= length
if op1_component['length'] == 0:
idx1 += 1
op1_component, idx1 = get_next_op(ops1, idx1)
if op2_component['length'] == 0:
idx2 += 1
op2_component, idx2 = get_next_op(ops2, idx2)
continue
# Case 4: op1 is delete, op2 is retain
if op1_component['type'] == 'delete' and op2_component['type'] == 'retain':
length = min(op1_component['length'], op2_component['length'])
self_prime.delete(length) # op1 删除这部分
# other_op_prime 不保留这部分，因为 op1 删除了它
op1_component['length'] -= length
op2_component['length'] -= length
if op1_component['length'] == 0:
idx1 += 1
op1_component, idx1 = get_next_op(ops1, idx1)
if op2_component['length'] == 0:
idx2 += 1
op2_component, idx2 = get_next_op(ops2, idx2)
continue
# Case 5: op2 is delete, op1 is retain
if op2_component['type'] == 'delete' and op1_component['type'] == 'retain':
length = min(op1_component['length'], op2_component['length'])
other_op_prime.delete(length) # op2 删除这部分
# self_prime 不保留这部分，因为 op2 删除了它
op1_component['length'] -= length
op2_component['length'] -= length
if op1_component['length'] == 0:
idx1 += 1
op1_component, idx1 = get_next_op(ops1, idx1)
if op2_component['length'] == 0:
idx2 += 1
op2_component, idx2 = get_next_op(ops2, idx2)
continue
# Case 6: Both are delete
if op1_component['type'] == 'delete' and op2_component['type'] == 'delete':
length = min(op1_component['length'], op2_component['length'])
# 如果 op1 删除了，op2' 就不需要再删除这部分。反之亦然。
# 所以两个转换后的操作都不包含这部分删除。
op1_component['length'] -= length
op2_component['length'] -= length
if op1_component['length'] == 0:
idx1 += 1
op1_component, idx1 = get_next_op(ops1, idx1)
if op2_component['length'] == 0:
idx2 += 1
op2_component, idx2 = get_next_op(ops2, idx2)
continue
# Fallback for unexpected cases
raise Exception(f"Unexpected operation types during transform: op1={op1_component}, op2={op2_component}")
return self_prime.normalize(), other_op_prime.normalize()
# 重新将transform方法添加到TextOperation类中
TextOperation.transform = transform再次验证 transform 例子：
初始文档 S = "abcdef"
opA: 在位置2插入 "X" ->S + opA = "abXcdef"opA=[retain(2), insert("X"), retain(4)]
opB: 删除位置3的字符 ‘d’ ->S + opB = "abcef"opB=[retain(3), delete(1), retain(2)]
计算 transform(opA, opB)：
-
opA_comp = retain(2),opB_comp = retain(3)length = min(2,3) = 2self_prime.retain(2)other_op_prime.retain(2)opA_comp剩余retain(0),idx1进1，opA_comp变为insert("X")opB_comp剩余retain(1)
-
opA_comp = insert("X")self_prime.insert("X")idx1进1，opA_comp变为retain(4)
-
opA_comp = retain(4),opB_comp = retain(1)length = min(4,1) = 1self_prime.retain(1)other_op_prime.retain(1)opA_comp剩余retain(3)opB_comp剩余retain(0),idx2进1，opB_comp变为delete(1)
-
opA_comp = retain(3),opB_comp = delete(1)length = min(3,1) = 1other_op_prime.delete(1)(opB 删除，opA 只是保留，所以opA’不再保留这部分)opA_comp剩余retain(2)opB_comp剩余delete(0),idx2进1，opB_comp变为retain(2)
-
opA_comp = retain(2),opB_comp = retain(2)length = min(2,2) = 2self_prime.retain(2)other_op_prime.retain(2)opA_comp剩余retain(0),idx1进1，opA_comp变为NoneopB_comp剩余retain(0),idx2进1，opB_comp变为None
所有组件处理完毕。
opA_prime=[retain(2), insert("X"), retain(1), retain(2)]-> 规范化后[retain(2), insert("X"), retain(3)]opB_prime=[retain(2), retain(1), delete(1), retain(2)]-> 规范化后[retain(3), delete(1), retain(2)]
这与之前的计算结果一致。现在我们重新验证收敛性：
-
S = "abcdef" -
S + opA + opB_prime:S + opA: "abcdef" -> "abXcdef"- 应用
opB_prime([retain(3), delete(1), retain(2)]) 到 "abXcdef":retain(3): 跳过 "abX"delete(1): 删除 "c" (原文档中的 ‘c’ 在 ‘X’ 之后，位置3)retain(2): 跳过 "ef"- 最终结果: "abXef"
-
S + opB + opA_prime:S + opB: "abcdef" -> "abcef"- 应用
opA_prime([retain(2), insert("X"), retain(3)]) 到 "abcef":retain(2): 跳过 "ab"insert("X"): 插入 "X"retain(3): 跳过 "cef"- 最终结果: "abXcef"
仍然不一致！ 结果是 "abXef" 和 "abXcef"。问题在于 opB 删除的 ‘d’ 的位置。
在 S = "abcdef" 中，’d’ 在位置3。
opA 在位置2插入 ‘X’，导致 ‘d’ 移动到位置4。
opB_prime ([retain(3), delete(1), retain(2)]) 应该删除 S + opA 中的 ‘d’，即位置4的字符。
然而，我的 transform 函数中的 delete(1) 只是删除了一个字符，它本身没有进行位置调整。retain(3) 跳过了3个字符 (a, b, X)，然后 delete(1) 删除了 ‘c’。这与 opB 的意图（删除原始文档中的 ‘d’）不符。
核心错误点：transform 函数没有正确处理“意图”的转换。
一个操作的 retain 和 delete 都是相对于其所基于的文档状态而言的。当文档状态被另一个并发操作修改后，这些 retain 和 delete 的“位置”和“长度”都需要相应调整。
正确的 transform 逻辑需要更精细的状态跟踪和对 retain / delete 长度的调整。
更严谨的 transform 逻辑 (基于 ShareJS 或 ot.js 的思路)：
OT的 transform 函数通常需要两个辅助函数：transform_left 和 transform_right，或者一个统一的 transform 函数，但内部逻辑更细致。一个常见的实现会逐个比较两个操作中的原子操作，并根据它们的类型和位置关系，调整各自的长度和生成新的操作。
让我们简化操作表示，只用列表的头部来代表当前处理的组件：
class TextOperation:
# ... (之前的 apply, normalize 等方法) ...
@staticmethod
def _transform_cursor(op_list, cursor_val, op_type_key, op_len_key):
"""
辅助函数，用于处理操作列表的游标。
从 op_list 头部消耗 cursor_val，并返回消耗后的值。
"""
consumed = 0
while cursor_val > 0 and op_list:
op = op_list[0]
if op['type'] == op_type_key: # e.g., 'retain' or 'delete'
length = op[op_len_key]
to_consume = min(cursor_val, length)
op[op_len_key] -= to_consume
cursor_val -= to_consume
consumed += to_consume
if op[op_len_key] == 0:
op_list.pop(0)
else: # Insert operations don't consume cursor for retain/delete
break #