传统的一致性维护方法例如锁机制(locking)和串行化(serialization)方法不适合实时协 同编辑, 主要有两方面原因. 一是, 传统方法的操 作响应时间过长, 难以支持自由、和谐和自然的人 机/人人交互. 二是, 传统方法重点考虑共享对象 的结果一致性, 而忽略了用户的操作意图.

理论研究方面, 最早Ellis 和Gibbs 在1989 年 以 GROVE 系统为背景首先提出操作转换(OT, Operational Transformation)的基本模型和算法[2], 来维护实时协同编辑过程中共享对象的一致性. 以此为开端, OT 算法在Ressel、Sun、Li 等的指引 和推动下得到了大量的探索, 发表在ACM CSCW 会议、ACM Siggroup 会议、ACM TOCHI 期刊、 IEEE TPDS 期刊、 IEEE TOC 期刊

OT 算法的主要 思想是本地产生的操作立刻执行, 接收到的远程 操作需要与本地操作历史中已执行的并发操作进 行操作转换后再执行. 与传统的锁机制和串行化 方法相比, OT 算法的优势是具有很好的本地响应 性. OT 算法也面临一些技术挑战, 例如, 设计 正确的操作转换函数困难, 不断有算法被找出特定 协同场景下的“puzzle”; 大部分 OT 算法没有良好的 伸缩性等

地址空间转换算法作为另一类支持操作意图一 致性的协同编辑算法, 为共享对象的一致性维护提 供了新的思路, 典型代表为 AST(Address Space Transformation)算法[4, 62]. 与OT 算法相比, 这类算 法在处理远程操作时, 并不是通过修正操作来获取 操作的正确执行位置, 而是通过计算文档的地址空 间来将文档状态回退到操作产生时的状态来获取操 作的执行位置. 为实现文档地址空间的正确转换, 采 用标记和回溯的方法实现. 因此, 该类方法又称为标 记和回溯(Mark&Retrace)方法. 基于 AST 算法, 各种 相关算法被提出

可 交 换 的 复 制 式 的 数 据 类 型 (CRDT, Commutative Replicated Data Type)作为一类新的支 持操作意图一致性的协同编辑算法被提出并得到了 深入的研究. 以法国的研究机构 INRIA 为代表,提出 了一系列 CRDT 相关算法, 发表在 ACM CSCW 会 议、ACM Siggroup 会议、IEEE TPDS 期刊等上. CRDT 算法不需要保存操作历史, 并发操作 之间不需要进行操作转换. 通过分配给所有操作对 象唯一的标识符 ID(Identifier), 使得并发操作之间可 交换执行. 大部分CRDT 算法具有良好的伸缩性, 适 合应用于大规模的 p2p 协同编辑领域. CRDT 算法也面临一些技术挑战, 例如, 如何设计并发操作 的可交换执行、如何给操作对象分配全局唯一的 ID, 如何减少ID 的空间开销等

Written by xi ming You should follow him on Github