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

协同组编辑环境中的数据一致性维护方法 学生 杨江明导师 顾宁教授计算机与信息技术系2020年1月12日 2020年1月12日 复旦大学信息科学与工程学院 2 内容概要 背景及问题的提出一致性模型回溯思想与一致性维护方法一致性维护的相关问题效率分析与原型系统总结与展望 2020年1月12日 复旦大学信息科学与工程学院 3 内容概要 背景及问题的提出一致性模型回溯思想与一致性维护方法一致性维护的相关问题效率分析与原型系统总结与展望 2020年1月12日 复旦大学信息科学与工程学院 4 背景及问题的提出 协同组编辑是一个抽象的研究模型传统的协同组编辑 GroupSketch GreenbergandBohnet Grove Ellis Gibbs andRein ShrEdit McGuffinandOlson DistEdit KnisterandPrakash REDUCE SubandEllis 单机软件的协同化 ICT D LiandR Li CoWord CoPowerpoint Xiaetal CoAutoCAD Guetal 基于Web2 0的非实时组编辑 CDVE2007 ShenandSun 2020年1月12日 复旦大学信息科学与工程学院 5 背景及问题的提出 协同组编辑环境下问题结果的一致性问题 如果操作是不可交互的 则不同的操作执行顺序会导致不同的结果 操作的依赖性问题 需要保证操作的执行条件操作的意愿维护问题 假设初始状态为 ABC 在SR1 O3为Insert d 1 即将 d 插入到位置1 即A和B之间 而在SR3 O1为Insert e 2 即将 e 插入到位置2 即B和C之间 当O1到达SR1时 该站点已经被操作O3修改成 AdBC 直接执行O1会把字符e插入到字符d和B之间 这显然是错误的 事务的支持性问题 2020年1月12日 复旦大学信息科学与工程学院 6 内容概要 背景及问题的提出一致性模型回溯思想与一致性维护方法一致性维护的相关问题效率分析与原型系统总结与展望 2020年1月12日 复旦大学信息科学与工程学院 7 数据及操作表示 线性结构线性结构是多种数据类型的抽象表示 直观上的线性结构包括 字符串 链表等数据结构 但事实上 线性结构维护的是多个对象间的一个全序关系 而这样一种全序关系是广泛存在的 全序关系的维护是协同环境下一致性维护的基础 树型结构一些主流的文档类型需要树型结构的表示 通过XML可以支持基于关系的操作 是Web应用的需求 2020年1月12日 复旦大学信息科学与工程学院 8 一致性模型 因果关系维护 Causalitypreservation 所有操作的执行顺序都按照它们之间的因果关系 对于任意的两个操作O1和O2 如果O1 O2 则在所有的站点 操作O1都在操作O2之前执行 一致性维护 Convergence 当相同的操作在所有的站点都执行完成之后 所有的数据副本保持一致 意愿维护 Intentionpreservation 任何一个操作在任何站点的执行效果都保持和它产生站点一致 2020年1月12日 复旦大学信息科学与工程学院 9 内容概要 背景及问题的提出一致性模型回溯思想与一致性维护方法一致性维护的相关问题效率分析与原型系统总结与展望 2020年1月12日 复旦大学信息科学与工程学院 10 回溯思想 2020年1月12日 复旦大学信息科学与工程学院 11 线性结构的回溯过程 2020年1月12日 复旦大学信息科学与工程学院 12 线性结构的回溯过程 对难题的解决操作转换方法中TP2条件维护的困难dOPT难题假设几个插入操作都是面向相同的位置 操作之间满足因果顺序或者是并发的 仅仅依靠强制规定操作间的优先级是无法保证结果的收敛性的 False tie难题假设两个并发的插入操作可能会因为在它们之间一个并发的删除操作 而丢失它们之间的左右位置关系 并且可能得到一个相反的结果 证明过程2个操作N个操作 2020年1月12日 复旦大学信息科学与工程学院 13 树型结构的回溯过程 2020年1月12日 复旦大学信息科学与工程学院 14 树型结构的回溯过程 已有方法的不足操作转换方法 OperationTransformation 方法无法支持关系操作 基于锁和序列化的方法无法满足操作的响应时间和自由度 证明过程2个操作N个操作 2020年1月12日 复旦大学信息科学与工程学院 15 内容概要 背景及问题的提出一致性模型回溯思想与一致性维护方法一致性维护的相关问题效率分析与原型系统总结与展望 2020年1月12日 复旦大学信息科学与工程学院 16 一致性维护的相关问题 操作的历史队列通过状态向量表 精简操作的历史队列Undo操作支持通过在回溯过程添加计数器 是回溯过程可以考虑Undo操作支持单站点并发操作的时间戳模型通过分离考虑操作间关系和操作的执行状态 引入两个时间戳 支持操作的并发执行 事务操作的支持 2020年1月12日 复旦大学信息科学与工程学院 17 事务操作的支持 2020年1月12日 复旦大学信息科学与工程学院 18 内容概要 背景及问题的提出一致性模型回溯思想与一致性维护方法一致性维护的相关问题效率分析与原型系统总结与展望 2020年1月12日 复旦大学信息科学与工程学院 19 线性结构效率分析 线性结构优化 通过调整数据结构 可以优化计数效率平摊效率插入操作的开销可以表示为O h logn logn d h h d m 删除操作的开销为O h logn logn d h h d 其中h为历史队列长度 n为文档字符数 d为针对一个节点的操作数 2020年1月12日 复旦大学信息科学与工程学院 20 树型结构效率分析 2020年1月12日 复旦大学信息科学与工程学院 21 原型系统 2020年1月12日 复旦大学信息科学与工程学院 22 内容概要 背景及问题的提出一致性模型回溯思想与一致性维护方法一致性维护的相关问题效率分析与原型系统总结 2020年1月12日 复旦大学信息科学与工程学院 23 总结 本文的工作基于状态转换的一致性维护方法一致性维护的四个相关问题算法的理论分析和实验CoAutoCAD演示系统进一步的工作关系数据库的协同化支持动态性的加入 退出进一步改善操作执行的并发性处理用户意愿的矛盾 2020年1月12日 复旦大学信息科学与工程学院 24 攻读硕士学位期间的科研工作 读硕士期间已发表和已录用的论文顾宁 杨江明 张琦炜 协同组编辑中基于地址空间转换的一致性维护方法 计算机学报 第30卷 第5期 2007年5月 763 774页 杨江明 张琦炜 顾宁 数据网格中复制式数据的一致性维护方法 华中科技大学学报 自然科学版 Vol 34 SupI 2006年9月 49 52页 ShichaoZhang NingGu JiangmingYang AnNorm drivenStateMachineModelforCSCWSystems ExpertSystemsWithApplications Volume31 Issue4 November2006 Pages800 807 JiangmingYang QiweiZhang NingGu AConsistencyMaintenanceApproachinReplicatedServices InProceedingsof2006IEEEinternationalconferenceoncomputerandinformationtechnology Seoul Korea Sept2006 QiweiZhang JiangmingYang NingGu YuweiZong ZhigangDing ShaohuaZhang DynamicReplicaLocationServiceSupportingDataGridSystems InProceedingsof2006IEEEinternationalconferenceoncomputerandinformationtechnology Seoul Korea Sept2006 ShichaoZhang JiangmingYang NingGu GridSM aNorm drivenStateMachineModelofGridWorkflow InProceedingsofInternationalConferenceonCSCWD2006 Nanjing China May 2006 杨江明 顾宁 吴筱媛 基于地址空间转换方法的Undo操作支持 通信学报 第27卷 2006年3月 48 56页 2020年1月12日 复旦大学信息科学与工程学院 25 攻读硕士学位期间的科研工作 读硕士期间已发表和已录用的论文NingGu JiangmingYang QiweiZhang Consistencymaintenancebasedonthemark retracetechniqueingroupwaresystems InProceedingsofthe2005internationalACMSIGGROUPconferenceonSupportinggroupwork SanibelIsland USA pages264 273 Nov2005 NingGu JunXu XiaoyuanWu JiangmingYang andWeiYe Ontologybasedsemanticconflictsresolutionincollaborativeeditingofdesigndocuments InternationalJournalofAdvancedEngineeringInformatics IJAEI 19 2 103 111 2005 JiangmingYang QiweiZhang NingGu GenxingYang andZhenyuLiu Themulti versionandsingle displaystrategyinundoscheme InProceedingsofthe5thinternationalconferenceoncomputerandinformationtechnology pages290 296 September2005 Shanghai China 张琦炜 杨江明 顾宁 杨根兴 刘振宇 数据网格中的动态分布式多入口技术 计算机科学 第32卷 2005年7月增刊A 127 131页 JiangmingYang NingGuandXiaoyuanWu Adocumentmarkbasedonmethodsupportinggroupundo InInternationalWorkshoponCollaborativeEditingSystems ACMCSCW 2004 November2004 Chicago USA NingGu JunXu XiaoyuanWuandJiangmingYang Asolutiontothesemanticconflictsinthecollaborativeeditingofdesigndocuments InProceedingsofInternationalConferenceonCSCWD2004 VolumeIIpages179 185 May2004 Xiamen China ShuoWang FengJing JianmgingYang JiboHe LongQuerySuggestionList PrioritizedorOrganized InHCIInternationalConference2007 Accepted 2020年1月12日 复旦大学信息科学与工程学院 26 攻读硕士学位期间的科研工作 专利及软件著作权 专利 顾宁 张世超 徐寅俊 杨江明 一种规范驱动的网格工作流描述和验证方法 专利申请号 200510027785 2 专利申请日 2005年7月15日 公开号 CN1719832 专利 顾宁 杨江明 张琦炜 绍斌 标记回溯的一致性维护方法 专利申请号 200610025690 1 专利申请日 2006年4月13日 公开号 CN1831776 专利 顾宁 杨江明 张琦炜 面向XML的标记回溯的一致性维护方法 专利申请号 200610026459 4 专利申请日 2006年5月11日 公开号 CN1845076 计算机软件著作权 软件名称 网格工作流管理系统软件V1 0 编号 软著登字第039155号 登记号 2005SR07654 首次发表日期 2005年01月10日 计算机软件著作权 软件名称 Norm的描述和验证工具软件 简称 NormTools V1 0 编号 软著登字第039165号 登记号 2005SR07664 首次发表日期 2004年11月10日 2020年1月12日 复旦大学信息科学与工程学院 27 攻读硕士学位期间的科研工作 硕士期间参与项目线性结构组操作的理论与算法研究 上海市科委基础研究项目 主持设计和实现了协同的Co AutoCAD原型系统 该系统可以支持多人参与的AutoCAD编辑与设计 可以在隐藏网络延迟的条件下处理用户间的操作冲突 该原型已完成 在国际顶级会议ACMGroup20