协同组编辑环境中的数据一致性维护方法

摘要

协同组编著的提出，是为了支持多个用户在不同的计算机终端同时协同处理共享文档。不同于以往的一致性维护模型，在协同环境下用户期待他人的参与，于是系统并不需要非常严格的序列化限制，相反却对操作的响应时间和操作的自由性有着较高的要求。组编辑是这一类一致性维护问题的广泛接受的抽象研究模型。对组编辑的研究是寻找协同环境下的一个统一的模型及其解决方法。传统基于锁或者序列化的一致性维护方法无法满足操作的响应时间和操作自由性的要求；而现有的协同环境下的一致性维护方法无法支持关系操作。本文的主要研究工作如下： 提出了一个基于地址空间转换的一致性维护方法，通过回溯数据的地址空间到操作产生的时刻，保证操作在所有站点拥有相同的执行环境。其中线性结构用来表示多个对象间的全序关系，是整个一致性维护算法的重要基础；而树型结果表示了一个结构化的数据关系，并且用来支持基于关系的操作表示。本文的算法可以实现协同环境下的一致性维护模型，并满足相应的操作正确性的验证条件。 进一步，本文讨论了一致性维护的四个相关问题：(1)通过精简操作的历史队列，实现算法持续执行时的效率优化；(2)通过引入对象节点的删除计数器，实现对文档的协同编著中的Undo操作支持；(3)介绍了一个新的支持单站点上共享数据的并发操作的时间戳模型；(4)通过引入空操作NOOP且保持事务操作和相应的NOOP操作同时执行，保证事务操作的序列化。 最后，对算法的理论分析和实验的结果表明，在分布式环境中，本文的算法不依赖于站点间的网络延迟，拥有更高的效率，以及更好的用户感受。本文的方法在CoAutoCAD演示系统中得到了具体的应用，也证明了本文算法拥有在不改变已有的商业软件的前提下，可以实现软件的协同化的能力。

目录

文摘

英文文摘

声明

第一章引言

§1.1 CSCW与协同组编辑

§1.2复制式结构和相关问题

§1.3一致性维护研究的状况

§1.3.1传统的分布式环境一致性维护的相关工作

§1.3.2协同环境下一致性维护的相关工作

§1.3.3其它的一致性维护的相关工作

§1.4本文的目标和结构安排

第二章一致性模型与地址空间转换思想

§2.1操作间的依赖关系

§2.2数据和操作的表示形式

§2.2.1线性结构

§2.2.2树型结构

§2.3一致性模型及验证条件

§2.3.1线性结构下的意愿维护的验证

§2.3.2树型结构下的意愿维护的验证

§2.4地址空间转换思想

§2.4.1因果关系维护

§2.4.2基于地址空间转换的一致性维护

第三章线性结构的一致性维护方法

§3.1线性结构下地址空间转换方法的存储结构

§3.2地址空间转换过程

§3.3控制算法

§3.4操作的执行

§3.5线性结构下的相关难题

§3.5.1 dOPT难题

§3.5.2 false-tie(ERV)难题

§3.6线性结构结果一致性的证明

§3.6.1两个操作

§3.6.2 N个操作

§3.6.3小结

第四章树型结构的一致性维护方法

§4.1树型结构的地址空间转换

§4.2控制算法

§4.3基于状态的倒排索引表

§4.4操作的执行过程

§4.4.1 Retracing过程

§4.4.2 FLW过程

§4.4.3 U(Update)过程

§4.5树型结构结果一致性的证明

§4.5.1两个操作

§4.5.2 N个操作

§4.5.3小结

第五章一致性维护的相关问题

§5.1操作的历史队列

§5.2 Undo操作支持

§5.2.1回溯过程的修改

§5.2.2一些Undo难题

§5.3支持单站点并发操作的时间戳模型

§5.3.1关系时间戳和执行时间戳

§5.3.2执行条件

§5.3.3控制算法

§5.3.4单站点并发操作满足操作间依赖关系的证明

§5.4事务操作的支持

§5.4.1事务操作的支持方法

§5.4.2事务操作满足序列化条件的证明

第六章效率分析与原型系统

§6.1线性结构的效率分析

§6.1.1操作执行效率的优化

§6.1.2回溯过程效率的优化

§6.1.3综合效率分析

§6.2树型结构的效率分析

§6.3 CoAutoCAD系统

§6.3.1 CoAutocad的核心模块

§6.3.2 Engine部分对操作的处理

第七章总结与展望

参考文献

攻读硕士学位期间的科研工作

致谢