---
title: 实时协作算法基本类型
date: "2017-07-01 01:20"
series: realtime-collab
tags: ["算法"]
published: false
---

## 本文范围

实时协同编辑让多个站点维护同一共享文档的副本，并允许用户在本地副本上产生编辑。本文将插入、删除等编辑请求称为**用户操作**，将字符、段落等被操作的文档内容称为**文档元素**；在内部数据结构中被标识和排序的文档元素统称为**操作对象**。网络异步传播时，不同站点可能基于不同文档状态产生并发操作。

操作转换（OT）、地址空间转换（AST）和可交换的复制式数据类型（CRDT）可按处理并发操作的基本机制归类。操作、文档状态、因果关系、并发关系、全序和一致性目标的定义见[实时协作算法相关概念](./07-01-实时协作算法相关概念.md)。

## 协同编辑中的处理约束

若站点在每次编辑前等待锁授权，或等待所有相关操作被串行处理，本地编辑是否可以立即生效将取决于授权和消息往返。实时协同编辑通常允许站点先在本地副本产生操作，再异步处理远程操作，因此需要定义远程操作到达当前文档状态后的处理方式，以及同一批操作处理完成后的副本一致性条件。

全序可用于排序、重放或选择处理顺序，但不定义插入、删除等用户操作在该顺序中的解释；这部分由算法的操作语义和并发处理规则规定。

## 操作转换（OT）

OT（Operational Transformation）以用户操作为处理单位。本地产生操作后，系统可先在本地副本执行；接收到远程操作时，系统将其与本地已执行的并发操作进行转换，再在当前文档状态上执行转换后的操作。转换的作用是根据已处理的并发操作调整待执行操作的参数。

转换函数的具体输入、位置计算和同位置并发时的规则依赖应用的操作语义。OT 实现通常需要维护与转换相关的操作历史或等价上下文，以判断待处理操作与哪些已执行操作并发。有关因果关系、全序和操作意图的边界见[实时协作算法相关概念](./07-01-实时协作算法相关概念.md)。

## 地址空间转换（AST）

AST（Address Space Transformation）也以用户操作和文档状态为处理对象。处理远程操作时，算法根据操作产生时的文档状态回溯文档地址空间，并在该地址空间中确定操作的执行位置，不直接修改待执行操作。

因此，AST 与 OT 的区别在于并发处理的直接对象：OT 调整待执行操作的参数；AST 将位置解释放在操作产生时的地址空间中。两种方式的正确性都依赖具体的操作语义、状态记录和位置规则。仅依据 AST 的类别，不能推导其对任意操作都能保持意图。

## 可交换的复制式数据类型（CRDT）

CRDT（Commutative Replicated Data Type）将文档元素作为带唯一标识的操作对象处理。各站点维护对象 ID、顺序元数据及算法所需的内部状态，并依据这些信息处理并发更新，使副本在相关操作处理完成后收敛。

CRDT 不维护 OT 语境中的转换历史，并发操作也不通过 OT 转换函数处理。CRDT 仍需保存对象 ID、顺序元数据和内部数据结构等处理操作对象所需的信息。ID 的生成方式、顺序定义和删除处理均属于具体 CRDT 实现；是否保持某种操作意图也需要由这些语义和实现规则验证。

## 三类算法的机制区别

| 类型 | 主要处理单位 | 处理并发操作的机制 | 需要由具体实现定义的部分 |
| --- | --- | --- | --- |
| OT | 用户操作 | 将待执行操作与已执行的并发操作转换后执行 | 转换函数、操作历史或上下文、操作语义 |
| AST | 用户操作与文档地址空间 | 回溯到操作产生时的地址空间以确定执行位置 | 状态记录、地址空间表示、位置规则 |
| CRDT | 带唯一 ID 的操作对象 | 依据对象 ID、顺序元数据和内部数据结构处理并发更新 | ID 与顺序定义、删除处理、操作语义 |

三类方法描述的是并发处理路径，不替代一致性目标。因果一致性和结果一致性说明各站点处理操作时需要满足的顺序与收敛条件；操作意图则需要结合具体操作语义定义。相关定义和统一示例见[实时协作算法相关概念](./07-01-实时协作算法相关概念.md)。