--- title: 实时协作算法相关概念 date: "2017-07-01 02:10" series: realtime-collab tags: ["算法"] published: true --- ## 本文范围 实时协同编辑中，每个站点维护共享文档的一个副本。本文将一次插入、删除等编辑请求称为**用户操作**，将它作用的字符、段落等文档内容称为**文档元素**；某些算法也将文档元素作为带标识的数据项处理，以下统称为**操作对象**。操作产生时，站点当前已知操作及其对应的文档内容构成该操作所依据的**文档状态**。 网络传递存在延迟时，多个站点可能基于不同文档状态产生操作。本文定义分析这种情形所需的因果关系、并发关系、全序和一致性目标。操作转换（OT）、地址空间转换（AST）和可交换的复制式数据类型（CRDT）的机制分类见[实时协作算法基本类型](./07-01-实时协作算法基本类型.md)。 ## 操作之间的偏序关系 偏序用于描述两个操作之间已经确定的先后依赖，以及它们是否互不知晓。设 `Oa` 和 `Ob` 是两个操作： - **因果关系**：记为 `Oa → Ob`。在同一站点，`Oa` 先于 `Ob` 产生；或者 `Ob` 产生前，所在站点已经接收并执行了 `Oa`；因果关系还具有传递性。 - **并发关系**：记为 `Oa || Ob`。当 `Oa → Ob` 和 `Ob → Oa` 都不成立时，二者并发。 - **简单并发**：两个并发操作产生于相同的文档状态。 - **偏并发**：两个并发操作产生于不同的文档状态。 并发只说明操作之间没有因果顺序，不直接说明操作是否冲突。是否需要调整操作、如何确定操作位置，取决于具体操作语义和算法实现。 ### 统一示例 设站点 A、B、C 的初始文档状态均为 `S0`。下表只记录操作产生前已知的操作，不涉及插入位置、字符内容或执行结果。 | 操作 | 产生站点 | 产生前已知的操作 | 由此可确定的关系 | | --- | --- | --- | --- | | `O1` | A | 无，状态为 `S0` | `O1` 与随后基于它产生的操作存在因果关系 | | `O2` | B | `O1`，站点 B 已接收并执行 `O1` | `O1 → O2` | | `O3` | C | 无，状态为 `S0` | `O1 || O3`；`O2 || O3` | `O1` 与 `O3` 都基于 `S0` 产生，属于简单并发。`O2` 基于已包含 `O1` 的状态产生，而 `O3` 基于 `S0` 产生；二者是偏并发。该示例仅用于判断偏序关系，不能据此推出三个操作的执行顺序或最终文档内容。 ## 全序 偏序保留已知因果关系，却不为并发操作指定先后次序。**全序**为每对操作或操作对象给出确定的先后次序，并要求这些次序保持一致的传递关系，避免出现循环排序。它可用于排序、重放或在各站点选择相同的处理顺序。全序本身不足以定义编辑语义：插入、删除等用户操作在该顺序下如何执行或转换，仍需由具体算法规定。 **站点编号（siteID）**是用于标识操作来源站点的稳定唯一编号。算法可在其他排序条件无法区分时，以 siteID 作为确定性决胜条件；编号的比较方向和适用条件由算法定义。 ### 操作的全序 操作的全序对操作记录排序。原文将 GOT（Generic Operational Transformation）归为通过状态向量和 siteID 定义操作全序的方案： - **状态向量（State Vector，SV）**是按站点记录已知操作数量的整数数组；操作关联的状态向量表示它产生时站点已知的操作范围。 - 排序规则可利用状态向量所表达的已知状态，并在需要时使用 siteID 消除并列，从而为操作给出确定次序。 这段说明只限定 GOT 的排序定位，不给出可执行的比较函数，也不说明操作执行、转换或最终文档结果。实现或比较具体 GOT 变体时，需要以相应算法定义为准。 集中式方案也可以由单一服务接收操作并将其序列化，或为操作分配连续序号。该机制使参与者获得同一序列；远程操作在本地文档状态上的解释仍由协同编辑算法规定。 ### 操作对象的全序 操作对象的全序对文档元素或其内部标识符排序。例如，CRDT 可为操作对象维护唯一 ID 和顺序元数据，并用这些元数据确定对象在内部数据结构中的相对位置。这里的对象顺序不同于用户操作的执行顺序；两者都不能脱离算法的操作语义单独推导编辑结果。 ## 一致性目标与操作意图 协同编辑算法通常需要明确以下目标： - **因果一致性**：若 `Oa → Ob`，各站点在处理二者时应先处理 `Oa`，再处理 `Ob`。 - **结果一致性**：当各站点都已处理同一协同会话中同一组已送达、无待处理状态的操作时，各站点的共享文档副本相同。 - **操作意图**：用户操作在并发环境中的预期效果。它必须结合操作语义定义，例如插入和删除的对象、位置表示及同位置并发时的处理规则。 操作意图不能由全序、因果关系或结果一致性单独推出。AST 或 CRDT 是否在某个实现中保持操作意图，取决于该实现定义的操作语义、对象标识和并发处理规则；不能仅依据算法类别作出结论。 ## 操作转换的机制边界 OT 以用户操作为处理单位。本地产生的操作可先作用于本地副本；远程操作到达时，系统会根据已经执行的并发操作调整待执行操作的参数，使其能在当前文档状态上解释和执行。转换函数的输入、位置规则及同位置并发时的处理方式均依赖具体应用的操作语义。 OT 的实现通常需要保留与转换相关的操作历史或等价上下文。相比之下，CRDT 不维护 OT 语境中的转换历史，但仍需要维护操作对象的 ID、顺序元数据及算法所需的内部状态。三类算法的处理单位和机制边界见[实时协作算法基本类型](./07-01-实时协作算法基本类型.md)。