高效的操作转换一致性维护方法研究

摘要

操作转换(Operational Transformation)技术是一种支持各类分布式协同应用的一致性维护技术，而数据的一致性维护是协同计算中的基础研究问题。与传统的操作串行化、两阶段锁等方法相比，操作转换技术可以进一步支持人们在有较大网络延迟的广域网上进行各种实时交流和协作。随着互联网的持续快速发展以及移动网络终端设备的迅速普及，一大批新兴协同应用迅速涌现出来，而现有的操作转换技术无论是从算法特性还是从算法性能上，都无法满足新兴协同应用中的数据一致性维护需求。因此，如何扩展和优化已有的操作转换技术来适应不断发展的协同应用需求是协同计算中的前沿研究问题。
　　针对协同应用的新发展和新需求，结合操作转换领域最新的研究进展，本文所做的主要研究工作如下：
　　1.提出了可以严格形式化论证的String转换算法ABTS及ABTSO。ABTS转换算法可以处理复杂的操作级联分裂，而ABTSO算法则进一步优化了String转换的时间复杂度。理论分析和实验评估都表明，ABTSO无论是在网络带宽的占用还是在系统计算资源的消耗上，都明显优于目前最好的主流算法。
　　2.提出了支持移动异步协同应用的高效操作序列转换算法ABST。针对移动设备计算能力相对较弱，而移动环境下又可能积累大量离线操作的应用需求，ABST可以对由大量操作构成的操作序列进行高效处理。ABST将主流算法处理操作序列所需的立方级复杂度优化为线性复杂度。基于在移动设备上进行的实验评估，其相对于已有的主流操作转换算法有上千倍的性能提升。
　　3.基于操作序列转换算法提出了支持新兴Web实时协同应用的数据同步协议TIPS。结合标准的Web通讯架构和实时Web协同的需求，TIPS协议将实时Web协同应用所涉及到的并发控制、一致性维护和数据同步机制通过操作转换技术巧妙地结合到了一个框架之中。与其它操作转换算法相比，通过消除对逻辑时间戳的依赖，TIPS协议可以支持高动态性的大规模实时Web协同应用。
　　4.提出了支持用户撤销任何历史操作的Selective Undo算法框架ERU。ERU可以完善地支持在分布式协同环境下对任何本地和远程历史操作的选择性撤销。ERU完整地证明了算法框架的正确性，并解决了已有的经典Undo Puzzle。针对已有操作转换算法处理Undo操作时间复杂度高的问题，ERU将处理Do和Undo操作的时间复杂度都优化为线性。