偏序、因果关系、并发关系

操作间的偏序最早源于 Lamport 事件偏序关系，即 happened before 和 concurrent 的逻辑时钟（Logical Clocks）。基于 Lamport 的偏序事件关系，协同编辑系统中的因果关系和并发关系，可以理解为定义1 和定义2。

基本定义

定义 1. 因果关系

给定任意两个分别位于站点 i 和站点 j 的操作 Oa 和 Ob，称 Oa 和 Ob 存在因果关系（记做 Oa→Ob），当且仅当 Oa 和 Ob 满足下列三个条件之一：

1. i=j，Oa 发生在 Ob 之前
2. i≠j，Oa 在站点 j 的执行先于 Ob 的产生
3. 存在操作 Oc，有 Oa→Oc 并且 Oc→Ob

定义 2. 并发关系

给定任意两个操作 Oa 和 Ob，称 Oa 和 Ob 存在并发关系（记做 Oa || Ob），当且仅当 Oa 和 Ob 既不满足 Oa→Ob，又不满足 Ob→Oa。

定义 3. 简单并发关系

当满足并发关系的两个操作 Oa 和 Ob 产生于相同的文档状态时，称 Oa 和 Ob 是简单并发关系。

定义 4. 偏并发关系

当满足并发关系的两个操作 Oa 和 Ob 产生于不同的文档状态时，称 Oa 和 Ob 是偏并发关系。

✨ 具体例子：协同文档编辑

假设有两个用户Alice和Bob正在协同编辑一个文档，初始文档内容为：“Hello”

场景1：因果关系

• Alice在位置5插入” World”，文档变为”Hello World”
• Bob看到Alice的操作后，在位置11插入”!”，文档变为”Hello World!”
• 这里Bob的操作→Alice的操作，存在因果关系

场景2：并发关系

• Alice在位置5插入” World”
• Bob同时在位置0插入”Hi ”
• 两个操作并发产生，互不知晓对方的存在，存在并发关系

关系图示例

graph TD
    subgraph "站点A (Alice)"
        A1["O1: Insert 'World' at pos 5<br/>SV: (1,0)"]
        A2["O3: Insert '!' at pos 11<br/>SV: (2,1)"]
    end

    subgraph "站点B (Bob)"
        B1["O2: Insert 'Hi ' at pos 0<br/>SV: (0,1)"]
        B2["O4: Insert '...' at pos 15<br/>SV: (2,2)"]
    end

    A1 --> A2
    A1 --> B2
    B1 --> B2

    A1 -.->|"并发关系 ||"| B1
    A2 -.->|"并发关系 ||"| B1

    style A1 fill:#e1f5fe
    style A2 fill:#e1f5fe
    style B1 fill:#fff3e0
    style B2 fill:#fff3e0

图说明：

• 实线箭头表示因果关系（happened-before）
• 虚线表示并发关系（concurrent）
• SV表示状态向量（State Vector）
• O1→O3, O1→O4, O2→O4 为因果关系
• O1||O2, O2||O3 为并发关系

图 1 用时空图（time-space)给出操作之间的因果和并发关系。其中：

• O1 与 O2、O1 与 O3 为因果关系
• O2 与 O3、O1 与 O4、O2 与 O4、O3 与 O4 为并发关系
• O2 与 O3、O1 与 O4 为简单并发关系
• O2 与 O4、O3 与 O4 为偏并发关系

图 2 采用因果执行图（Causally Executable Graph）给出操作之间的因果和并发关系。图中的顶点表示各站点产生的操作，操作之间的有向边表示操作的因果关系，其中，有向边的起点是有向边终点的因操作。操作之间的无向边表示操作的并发关系，包括简单并发关系和偏并发关系。如图 2 所示：O1→O2，O1→O3，O2||O3，O1||O4，O2||O4，O3||O4。

全序

相比偏序关系定义的客观性，全序关系的定义更依赖于某种”假设”。例如，Lamport 提出的全序关系，如果逻辑时钟相等，假设可以通过进程 ID 号来确定次序，从而得到一种全序关系。类似地，实时协同编辑算法采用不同假设和策略来定义全序，基于某种”假设”来对操作或者操作对象进行定序。

操作的全序

操作的全序是给实时协同编辑系统中产生的所有操作赋予唯一的全局次序，并按照全序进行操作转换或按照全序执行。操作的全序有两类具体方法。

分布式全序

代表性的方法有：

• GOT 算法：基于 SV 和站点编号（siteID）定义了操作间的一种全序
• TIBOT/TIBOT2.0：以线性的时间间隔 TI（Time Interval）和 siteID 来定义操作间的全序

📋 GOT 算法详解

GOT（Generic Operational Transformation）算法 是一种基于分布式全序的经典操作转换算法，由 Sun 和 Chen 在 2002 年提出。

核心思想

GOT 算法通过状态向量（State Vector, SV）和站点编号（siteID）来定义操作间的全序关系，确保所有站点上的操作按照相同的顺序执行，从而保证最终一致性。

状态向量定义

状态向量 SV：一个长度为 n 的整数数组，其中 n 是系统中站点的总数。

• SV[i] 表示当前站点已知的站点 i 产生的操作数量
• 每个操作都有一个关联的状态向量，表示该操作产生时的系统状态

全序定义规则

对于两个操作 Op1 和 Op2，其全序关系定义为：

1. 状态向量和比较：计算 sum(SV1) 和 sum(SV2)
2. 优先级排序：
   • 如果 sum(SV1) < sum(SV2)，则 Op1 < Op2
   • 如果 sum(SV1) > sum(SV2)，则 Op1 > Op2
   • 如果 sum(SV1) = sum(SV2)，则比较 siteID1 和 siteID2
     • 如果 siteID1 < siteID2，则 Op1 < Op2
     • 如果 siteID1 > siteID2，则 Op1 > Op2

算法流程示例

sequenceDiagram
    participant A as 站点A (siteID=1)
    participant B as 站点B (siteID=2)
    participant C as 站点C (siteID=3)

    Note over A,C: 初始状态: SV=(0,0,0)

    A->>A: Op1: Insert("H",0)<br/>SV=(1,0,0), sum=1
    A->>B: 发送 Op1
    A->>C: 发送 Op1

    B->>B: Op2: Insert("i",1)<br/>SV=(1,1,0), sum=2
    B->>A: 发送 Op2
    B->>C: 发送 Op2

    C->>C: Op3: Insert("!",0)<br/>SV=(1,1,1), sum=3
    Note over A,C: 全序: Op1 < Op2 < Op3<br/>(基于SV和的比较)

    Note over A,C: 最终结果: "H!i" (所有站点一致)

具体实现示例

class GOTAlgorithm {
  constructor(siteId, totalSites) {
    this.siteId = siteId;
    this.stateVector = new Array(totalSites).fill(0);
    this.operations = [];
  }

  // 产生本地操作
  generateOperation(type, content, position) {
    this.stateVector[this.siteId]++;
    const operation = {
      type,
      content,
      position,
      siteId: this.siteId,
      stateVector: [...this.stateVector], // 复制当前状态向量
      timestamp: Date.now()
    };
    this.operations.push(operation);
    return operation;
  }

  // 接收远程操作
  receiveOperation(operation) {
    this.operations.push(operation);
    // 更新状态向量
    for (let i = 0; i < this.stateVector.length; i++) {
      this.stateVector[i] = Math.max(this.stateVector[i], operation.stateVector[i]);
    }
  }

  // GOT全序比较函数
  compareOperations(op1, op2) {
    const sum1 = op1.stateVector.reduce((a, b) => a + b, 0);
    const sum2 = op2.stateVector.reduce((a, b) => a + b, 0);
    
    if (sum1 !== sum2) {
      return sum1 - sum2; // 状态向量和小的操作优先
    }
    
    // 状态向量和相等时，比较siteID
    return op1.siteId - op2.siteId;
  }

  // 获取全序排列的操作序列
  getOrderedOperations() {
    return [...this.operations].sort(this.compareOperations);
  }
}

// 使用示例
const siteA = new GOTAlgorithm(0, 3);
const siteB = new GOTAlgorithm(1, 3);
const siteC = new GOTAlgorithm(2, 3);

// 站点A生成操作
const opA = siteA.generateOperation('insert', 'H', 0);
console.log('操作A:', opA);
// 输出: { type: 'insert', content: 'H', position: 0, siteId: 0, stateVector: [1,0,0] }

// 站点B生成操作
const opB = siteB.generateOperation('insert', 'i', 1);
console.log('操作B:', opB);
// 输出: { type: 'insert', content: 'i', position: 1, siteId: 1, stateVector: [0,1,0] }

// 全序比较
console.log('A < B:', siteA.compareOperations(opA, opB) < 0); // true (sum=1 < sum=1, siteId=0 < siteId=1)

📋 TIBOT/TIBOT2.0 算法详解

TIBOT（Time Interval Based Operational Transformation）算法 是另一种分布式全序算法，通过时间间隔来定义操作的全序关系。

核心思想

TIBOT 算法使用**时间间隔（Time Interval, TI）**作为主要的排序依据，结合站点编号来确定操作的全序关系。每个操作都被分配一个时间间隔，这个时间间隔反映了操作的相对重要性和执行顺序。

时间间隔定义

时间间隔 TI：一个实数值，表示操作在时间轴上的相对位置

• TI 值越小，操作的优先级越高
• 通过算法动态计算，确保全局唯一性

TIBOT2.0 改进

TIBOT2.0 在原有基础上进行了优化：

• 更精确的时间间隔分配：避免时间间隔冲突
• 更好的网络延迟处理：适应不同网络环境
• 优化的存储和传输：减少数据开销

全序定义规则

对于两个操作 Op1 和 Op2：

1. 时间间隔比较：
   • 如果 TI1 < TI2，则 Op1 < Op2
   • 如果 TI1 > TI2，则 Op1 > Op2
2. 站点ID优先级：
   • 如果 TI1 = TI2，则比较 siteID1 和 siteID2
   • siteID 小的操作优先

时间间隔分配算法

class TIBOTAlgorithm {
  constructor(siteId) {
    this.siteId = siteId;
    this.operations = [];
    this.currentTI = 0;
  }

  // 计算时间间隔
  calculateTimeInterval(previousTI, nextTI) {
    if (nextTI === undefined) {
      // 如果没有后续操作，TI = previousTI + 1
      return previousTI + 1;
    }
    if (previousTI === undefined) {
      // 如果没有前驱操作，TI = nextTI / 2
      return nextTI / 2;
    }
    // 在两个操作之间插入，TI = (previousTI + nextTI) / 2
    return (previousTI + nextTI) / 2;
  }

  // 生成操作
  generateOperation(type, content, position) {
    // 查找插入位置的前后操作
    const orderedOps = this.getOrderedOperations();
    let previousTI, nextTI;
    
    for (let i = 0; i < orderedOps.length; i++) {
      if (orderedOps[i].position <= position) {
        previousTI = orderedOps[i].timeInterval;
      } else {
        nextTI = orderedOps[i].timeInterval;
        break;
      }
    }

    const timeInterval = this.calculateTimeInterval(previousTI, nextTI);
    
    const operation = {
      type,
      content,
      position,
      siteId: this.siteId,
      timeInterval,
      timestamp: Date.now()
    };
    
    this.operations.push(operation);
    return operation;
  }

  // TIBOT全序比较函数
  compareOperations(op1, op2) {
    if (op1.timeInterval !== op2.timeInterval) {
      return op1.timeInterval - op2.timeInterval;
    }
    // 时间间隔相等时，比较siteID
    return op1.siteId - op2.siteId;
  }

  // 获取全序排列的操作序列
  getOrderedOperations() {
    return [...this.operations].sort(this.compareOperations);
  }

  // 接收远程操作
  receiveOperation(operation) {
    this.operations.push(operation);
  }
}

// 使用示例
const tibotA = new TIBOTAlgorithm(0);
const tibotB = new TIBOTAlgorithm(1);

// 站点A生成操作
const opA = tibotA.generateOperation('insert', 'H', 0);
console.log('TIBOT操作A:', opA);
// 输出: { type: 'insert', content: 'H', position: 0, siteId: 0, timeInterval: 1 }

// 站点B生成操作
const opB = tibotB.generateOperation('insert', 'e', 1);
console.log('TIBOT操作B:', opB);
// 输出: { type: 'insert', content: 'e', position: 1, siteId: 1, timeInterval: 1 }

// 全序比较
console.log('A < B:', tibotA.compareOperations(opA, opB) < 0); // true (TI相等时，siteId=0 < siteId=1)

TIBOT算法执行流程

graph TD
    A[产生操作] --> B[计算时间间隔TI]
    B --> C{是否有前驱操作?}
    C -->|有| D[TI = (prev_TI + next_TI) / 2]
    C -->|无| E{是否有后续操作?}
    E -->|有| F[TI = next_TI / 2]
    E -->|无| G[TI = current_TI + 1]
    D --> H[分配TI给操作]
    F --> H
    G --> H
    H --> I[广播操作到其他站点]
    I --> J[接收站点按TI和siteID排序]
    J --> K[按全序执行操作]
    K --> L[保证最终一致性]

    style A fill:#e1f5fe
    style K fill:#c8e6c9
    style L fill:#c8e6c9

算法对比总结

实际应用考虑

1. 网络延迟：TIBOT在高延迟网络环境中表现更好
2. 可扩展性：TIBOT2.0 支持更多并发用户
3. 存储效率：时间间隔比状态向量占用空间更少
4. 实现复杂度：GOT概念更直观，TIBOT需要精确的时间间隔管理

集中式全序

又可分为中心服务器取全序和中心序列产生器取全序：

中心服务器取全序：将各协同站点产生的操作发送到中心服务器，中心服务器采用先进先出（First in First out）策略将接收操作序列化之后转发给其它站点，如：

• Jupiter 系统
• Google Wave/Docs
• NICE

中心序列产生器取全序：将中心序列产生器产生的连续的正整数赋予给各站点产生的操作，如：

• SOCT3/4：通过一个中心 Sequencer 定义了操作间全序

某些算法系统，例如 COT 既可采用分布式取全序，也可采用集中式取全序。

操作对象的全序

操作对象的全序指协同编辑系统中，操作对象在系统内部数据结构的全局位置 ID 标识。

协同编辑算法通过维护内部数据结构中操作对象的全序位置关系来维护共享对象的一致性。代表性算法有：

• AST 算法：采用了地址空间转换技术维护每个站点字符节点间一致的顺序
• ABT 家族算法：通过操作转换技术维护各站点操作对象间相同的全序位置关系
• CRDT 家族算法：通过给操作对象分配全局有序的唯一 ID，并通过 ID 将操作对象全序的保存到内部数据结构中实现各站点内部数据结构中操作对象间全序的位置关系

全序假设与优先级

全序的定义，在前面若干判定条件相等情况下，往往假设可以用到优先级（Priority）定序。上述操作全序中的分布式全序方法和操作对象的全序方法，主要采用 siteID 作为优先级来对全序定义进行完备化。

具体应用实例：

• GOT：当两个操作的 SV 的和相同时，siteID 小的操作全序在前
• TIBOT/TIBOT2.0：当两个操作的 TI 相同时，siteID 小的操作全序在前
• SDT、SDTO、LBT 及 ABT：当两个并发的插入操作在同一位置插入不同操作对象时，siteID 小的操作对象全序在前
• AST：当两个插入字符的 SV 和相同时，siteID 小的插入字符位置在前
• WOOT：siteID 小的操作对象全序在前
• TreeDoc：当两个操作对象的逻辑时钟相同时，siteID 小的操作对象的 ID 全序小
• RGA：当两个操作对象的 session 相同且 SV 的和相同时，siteID 小的操作对象的 ID 全序小

这些方法，本质上与 Lamport 的假设可以把进程 ID 号作为优先级进行全序完备化方法相似。

一致性模型

支持操作意图一致性的协同编辑算法可参照一致性模型来设计和开发。

主要一致性模型

(1) CC 模型

1996年，Ressel 在文献 中明确阐述了协同编辑算法要满足两个一致性条件：

• 因果一致性（Causality Preservation）
• 结果一致性（Convergence）

并提出了 CC 模型。

(2) CCI 模型

后续研究发现 CC 模型不足以完整约束一个操作转换系统的行为。因此，Sun 在 CC 模型的基础上进行了完善，指出一个协同编辑系统除了要满足因果一致性和结果一致性外，还需要做到操作意图一致性，并给出 OT 算法应遵循的 CCI 模型：

• 因果一致性
• 结果一致性
• 操作意图一致性（Intention Preservation）[3, 61]

大多数算法参照 CCI 模型设计和开发的。

(3) CA 模型

CCI 模型中意图保持定义的模糊性（ambiguity），提出了可以被形式化证明的 CA 模型：

• 因果一致性
• Admissibility 属性

其中，Admissibility 属性蕴含了操作意图一致性和结果一致性两方面含义。参照 CA 模型设计的协同编辑算法可以被形式化证明其算法的正确性。

因果一致性和结果一致性

定义 5. 因果一致性

给定任意一对操作 Oa 和 Ob，如果 Oa→Ob，那么在所有站点 Oa 在 Ob 之前执行。

定义 6. 结果一致性

当一个协同会话在静默状态时，所有站点共享文档的副本是一致的。

实现方法

因果一致性：一般可通过 SV 定义和实现。

结果一致性：一般可通过两种方法实现：

1. 转换属性方法：设计算法的转换函数满足转换属性 TP1（Transformation Property 1）和 TP2（Transformation Property 2）
2. 唯一全序方法：设计算法的控制过程避免 TP1/TP2 的约束，即可以构建唯一全序的操作转换路径

已有研究成果表明，设计转换函数满足 TP1/TP2 非常困难，相继有学者找出：

• dOPT 不能满足 TP1 和 TP2 的”puzzle”
• adOPTed 不满足 TP2 的”puzzle”
• SOCT2 不满足 TP1 的”puzzle”
• GOTO 不满足 TP1 的”puzzle”

相比之下，第二类方法更容易实现结果一致性。

Puzzle 问题的解决方案

为了解决 TP1 和 TP2 的”puzzle”问题，很多学者做了大量的研究和探索：

• Sun（2014）：从转换函数层面上总结了 OT 算法的”puzzle”问题，包括 do 操作的 TP1/TP2 的”puzzle”问题以及 undo 操作的 IP1、IP2/IP3 的”puzzle”问题
• 解决思路：
  1. 从转换函数的层面上解决，但需要结合具体的应用来设计相应的转换函数
  2. 从算法的控制层面上考虑设计避免 TP1/TP2、IP1 和 IP2/IP3 约束的 OT 算法
• Randolph 等人（2015）：总结了已有算法存在的”puzzle”问题，并利用自动机合成了满足 TP1 和 TP2 的操作转换函数

操作意图一致性

Sun 的定义

Sun 最早通过操作的”执行效果（execution effect）“给出”操作意图（intention of an operation）“的一个笼统定义 [3, 61]，并未严格定义、度量和说明”执行效果”。Sun 等人认为操作意图的具体定义要依赖于具体应用中的”操作语义（operation’s semantics）“，并且不能通过串行化方法达到。

Sun 等人从两个层面上考虑维护操作意图的一致性 [3, 61]：

1. 算法控制过程：给出了维护操作意图一致性的一个通用框架，即可采用维护操作的因果一致性和操作的全序来构建操作转换路径
2. 操作转换函数：指出通过设计操作转换函数来维护操作的意图需要依赖于具体应用中的操作语义

基于以上讨论，Sun 的操作意图的维护，结合了 Sun 同时代多版本的含义，多种结果只要获得其中的任意一个一致性结果，即认为满足操作意图一致性。

不同技术的实现方法

地址空间转换技术：意图保持可以通过转换文档的地址空间实现。当处理并发操作时，并不需要转换操作，而是将文档的地址空间回溯到操作产生时的状态，在该状态下执行操作可以获取正确的执行位置。这种方法可以保证当所有的操作在各站点执行结束后，各站点线性结构存储的操作字符的顺序是一致的，实现了结果一致性和操作意图一致性。

CRDT 方法：与 OT 技术和地址空间转换技术不同，CRDT 方法维护操作意图一致性需要给每个操作对象分配全局唯一的 ID，结合不同的调度算法将操作对象全序的映射到内部的数据结构中，确保内部数据结构中操作对象的全序位置关系，从而实现操作意图一致性，并收敛于一致性的结果。

研究路线图

1. 建立维护操作意图一致性的整体框架：即每一步的执行都要维护操作的意图
2. 针对某种”应用”：基于某种”效果”，描述或者定义某种”操作意图”
3. 基于（2）中操作意图的描述或者定义：设计相应的操作意图一致性的维护算法

虽然各类算法对操作意图的理解不同，定义不同，维护方法不同，应用效果不同，但到目前为止，基本上都能够被上述路线图所覆盖。

✨ 操作转换具体例子

场景：两个用户同时编辑文档”ABC”

sequenceDiagram
    participant A as Alice
    participant S as Server
    participant B as Bob

    Note over A,B: 初始文档: "ABC"

    A->>S: Insert("X", 1) → "AXBC"
    B->>S: Delete(2) → "AB"

    Note over S: 服务器需要进行操作转换

    S->>B: Transform(Insert("X", 1), Delete(2))
    S->>A: Transform(Delete(2), Insert("X", 1))

    Note over A: 执行转换后的Delete(3) → "AXB"
    Note over B: 执行转换后的Insert("X", 1) → "AXB"

    Note over A,B: 最终一致性: "AXB"

转换规则示例：

• IT 转换（Insert-Transform）：当插入操作遇到其他操作时的转换
• DT 转换（Delete-Transform）：当删除操作遇到其他操作时的转换

总结

基于上述对操作意图及一致性问题的讨论，可将代表性的操作意图一致性的维护算法大体分为三类：

1. 操作转换算法
2. 地址空间转换算法
3. 可交换的复制式的数据类型

Written by xi ming You should follow him on Github