（系统分析与集成专业论文）分布式协同图形编辑关键技术研究与实现.pdf

华东师范大学硕士学位论文分布式协同图形编辑关键技术研究与实现 摘要 协同图形编辑系统( c o o p e r a t i v eg r a p h i c se d i t i n gs y s t e m - c g e s ) 是协同编 辑系统( c o l l a b o r a t i v ee d i t i n gs y s t e m c e s ) 研究领域的一个重要分支。为了支 持多个用户同步地对同一图形文档进行自然、自由的协同编辑，系统应具有实 时响应性、协作透明性和无约束性等特征。为了满足以上要求，通常采用分布 式体系结构，即把共享图形文档分别对等地复制到各个用户本地端进行协同编 辑。这样用户的所有操作( 如对视图的刷新，对对象的修改、删除及创建新的 对象等) 都可借助本地对象得以快速地完成，从而实现较快的响应速度，并由 此达到系统的协作透明性和操作无约束性。因此，如何在分布式体系结构下， 保证分布用户群的视图一致，以及各个协作用户的初始化状态同步是协同图形 编辑系统需要解决的关键问题，也是文本研究的核心。 本文针对上述关键问题展开研究，并将研究成果成功运用于面向数据会 议的无线投影仪信息共享平台项目： 首先，针对视图一致性问题，围绕协同编辑系统的一致性模型，深入研究 了执行顺序冲突、操作意愿冲突的形成原因及表现形式，提出了在分布式结构 下的基于对象特征和操作关系的并发控制算法b p o p t 算法。b p o p t 算法能够有 效地处理各种冲突操作，实现了一致性维护，并通过消除操作日志中的冗余操 作信息，减少了操作比较时间，提高了系统的运行效率。 其次，针对用户后加入所引起的初始化状态不同步问题，对单“后加入 s e r v e r ”算法进行改进，提出了i s l j s 算法。该算法能够保证后加入节点初始化 应用状态的同步完整性，并能够有效地解决多个后加入者加入c g e s 系统时初 始化状态同步的问题，同时，i s l j s 算法具有可靠的差错控制机制，有效地保证 了系统的正常运行。 最后，本文介绍了一个基于上述算法实现的w i j e z - t o r 原型系统，并在无线 局域网环境中对w i j e c t o r 系统进行了实验和分析，模拟了应用中可能遇到的各 种不一致与不同步情况。实验分析结果表明，本文提出的所有方案都是有效 的。 关键词：协同图形编辑系统，c s c w ，分布式结构，并发控制，一致性维护， d o p t ，后加入 华东师范大学硕士学位论文分布式协同图形编辑关键技术研究与实现 a b s t r a c t c o o p e r a t i v eg r a p h i c se d i t i n gs y s t e m ( c g e s ) i sa ni m p o r t a n tb r a n c h i n c o l l a b o r a t i v ee d i t i n gs y s t e mr e s e a r c hf i e l d t os u p p o r tm u l t i - n s e rc o o p e r a t i v ee d i t i n g s y n c h r o n o u s l y , c g e s s h o u l dh a v et h ec h a r a c t e r i s t i c so fr e a l - t i m er e s p o n s e ， t r a n s p a r e n ta n du n c o n s t r a i n tc o o p e r a t i o n - s u p p o r t g e n e r a l l y , i no r d e rt oa c h i e v et h i s ， w ea d o p td i s t r i b u t e da r c h i t e c t u r e 船i t se d i t i n gm o d e w h i c hm e _ a t l st h a ts h a r e d g r a p h i c s - d o c u m e n ti sr e p l i c a t e dt oe a c hl o c a lc l i e n ts ot h a ta uo p e r a t i o n s ( s u c ha s r e f r e s h i n g , u p d a t i n g ，d e l e t i n ga n dc r e a t i n g ) o ni t c a l lb ep e r f o r m e da tl o c a ls i t e i m m e d i a t e l y c o n s e q u e n t t y ，h o wt og u a r a n t e et h ev i e wc o n s i s t e n c ya n di n i t i a l - s t a t e - s y n c h r o n i z a t i o nf o re a c hd i s t r i b u t e dc o u a b o m t i v en s e ri nd i s t r i b u t e da r c h i t e c t u r ei s t h ek e yi s s u eo f c g e s w h i c hi sa l s ot h ec o r eo f t h i sp a p e r t h i sp a p e ri sf o c u s e d0 1 1a b o v et w ok e yt e c h n i q u e si nc g e s ，a n dw ep r o p o s e t w oa l g o r i t h m s 船t h e i rr e s o l u t i o n sa n da p p l yt h e mt ot h ep r o j e c to f ”d i g i t a l - m e e t i n g - o r i e n t e dw i r e t e s sp r o j e c t o ri n f o r m a t i o ns h a r i n gp l a t f o r m “s u c c e s s f u l l y ： f i r s t l y , f o r t h ev i e w c o n s i s t e n c yp r o b l e m , w es t u d y t h e c a u s e sa n d r e p r e s e n t a t i o n so fc a u s a l i t yc o n f l i c ta n di n t e n t i o nc o n f l i c t ，a n dp r o p o s e ac o n c u r r e n c y c o n t r o la l g o r i t h mb p o p tb a s e do nc g e s sc o n s i s t e n c ym o d e l b p o p ti sf e a t u r e d w i t h o b j e e t - c h a r a e t e r i s t i c - b a s e d a n d o p e r a t i o n - r e l a t i o n - b a s e d i n d i s t r i b u t e a r c h i t e c t u r e ，a n di tc a l lh a n d l ec o n f l i c t se f f e c t i v e l yt oa c h i e v et h ec o n s i s t e n c y m o r e o v e r , b p o p te l i m i n a t e sr e d t m d a n to p e r a t i o ni n f o r m a t i o na n do p t i m i z e s p e r f o m a n c eo fc o n c u r r e n c yc o n t r 0 1 s e c o n d l y , a i m e d a tt h eu n _ s ”l c h r o i l o u si n i t i a l i z a t i o n p r o b l e mc a u s e db y l a t e c o m e r , w ep u tf o r w a r da ni m p r o v e ds i n g l e l a t ej o i ns e r v e r a l g o r i t h mi s l j s ， w h i c hc n s n r e st h ei n t e g r a l i t ya n dr e l i a b i l i t yo fs y n c h r o n o mi n f o r m a t i o nf o rs i n g l e l a t e c o m e ro rm u l t i l a t e c o m e r st oj o i na no n g o i n gs e s s i o n i na d d i t i o n , i s l j sh a sa r e l i a b l ef a u l t - t o l e r a n tm e c h a n i s mt oe n s u et h es y s t e mr u n n i n gn o r m a l l y a tt h ee n do f t h i sp a p e r , ap r o t o t y p e ，w i j e e t o rs y s t e m , i si n t r o d u c e db a s e do i lt h e a b o v ea l g o r i t h m s w ee x p e r i m e n ti ti nw i r e l e s sl a ne n v i r o n m e n ta n ds i m u l a t e v a r i o u si n c o n s i s t e n ta n du n - s y n c h r o n o u ss i t u a t i o n s t h ee x p e r i m e n tr e s u l t si n d i c a t e t h a tt h ea l g o r i t h m sp r o p o s e di nt h i sp a p e ra r ev e r i f i e d k e y w o r d s ：c o o p e r a t i v eg r a p h i c se d i t i n gs y s t e m ；c s c w ；d i s t r i b u t e da r c h i t e c t u r e ； c o n c u r r e n c yc o n t r o l ；c o n s i s t e n c ym a i n t e n a n c e ；d o p t ；l a t e j o i n 学位论文独创性声明 本人所呈交的学位论文是我在导师的指导下进行的研究工作及取得的 研究成果据我所知，除文中已经注明引用的内容外，本论文不包含其他 个人已经发表或撰写过的研究成果对本文的研究做出重要贡献的个人和 集体，均已在文中作了明确说明并表示谢意 储戤：胁吼砑均 授权使用声明 本人完全了解华东师范大学有关保留、使用学位论文的规定，学校有权保 留学位论文并向国家主管部门或其指定机构送交论文的电子版和纸质版。有权 将学位论文用于非赢利目的的少量复制并允许论文进入学校图书馆被查阅。有 权将学位论文的内容编入有关数据库进行检索。有权将学位论文的标题和摘要 汇编出版。保密的学位论文在解密后适用本规定。 学位论文作者签名彳二移矧确 醐：珥4 导师签名 日期： 泌刃飞 华东师范大学硕士学位论文第1 章绪论 1 1 研究背景与意义 第1 章绪论 支持多用户的协同编辑系统( c o l l a b o r a t i v ee d i t i n gs y s t e m c e s ) 是 c s c w l l 】领域的研究热点之一。c e s 可以分为协同文本、协同超文本编辑、协 同图形编辑和协同图像编辑等 2 1 。c e s 支持分布在各地的用户通过i n t e m e t 同时 浏览和编辑共享文本、图形、图像或多媒体文档【2 】。广泛应用于协同编著、协 同c a d 设计、协同编程与调试、远程会议等场合，为人们提供跨越时空界限的 虚拟协同和交流空间。 近年来，协同编辑系统由于具有应用上的巨大潜力和技术上的挑战性，吸 引了很多c s c w 和分布计算领域的研究人员参与这方面的研究与应用工作。在 c s c w 研究领域最顶级的国际会议a c mc o m p u t e rs u p p o r t e dc o o p e r a t i v e w o r k l 3 l t * l 和e u r o p e a nc o m p u t e rs u p p o r t e dc o o p e r a t i v ew o r k t 5 1 上，每届都有与之 相关的技术专题和w o r k s h o p 。 目前的研究热点主要是针对基于分布式体系结构的协同编辑系统：由于网 络带宽和传输速率的限制，为了提高系统的响应速度，为用户提供自然无约束 的协同编辑环境，一般都是把共享文档分别对等的复制到各个用户本地端进行 协同编辑，即采用分布式的体系结构【l l 。( 以下，本文所指的分布式邵为分布式 体系结构。) 在分布式体系结构下，由于没有服务器的集中控制，如何保证各个 协作用户的视图一致埘【6 】【7 】【8 1 以及用户后加入时的初始化状态同步【9 】【1 0 】【1 1 1 是实现 此类协同编辑系统的重点和难点。此外，当某个站点发生故障、或者网络发生 中断时，如何使协同编辑工作继续正常进行也是亟待解决的一个重要问题，因 此，需研究合理的差错控制机制【1 1 l 来保证系统的可靠性和鲁棒性。 协同图形编辑系统( c o o p e r a t i v eg r a p h i c se d i t i n gs y s t e m - c g e s ) 1 2 是一种 基于图形对象的协同编辑系统，在分布式结构下也具有上述协同编辑所遇到的 并发控制和一致性维护问题，用户后加入问题以及差错控制问题等。本文即针 对上述关键问题进行深入研究并给出相应的解决方案。 1 2 协同编辑系统及其研究现状 根据应用的时间需求，协同编辑可分为同步和异步两种方式。同步协同编 辑，指群体成员在同一时间对共享文档进行协同编辑；异步协同编辑，指群体 华东师范大学硕士学位论文第1 章绪论 成员在不同时间对同一共享文档进行协同编辑。对于异步协同编辑来说，同一 时间只有一个用户处于编辑状态，所以维护其一致性的主要问题就是如何保证 每个用户进行编辑时文档的版本是最新的，并且是一致的。由于异步协同编辑 的问题比较简单，并已得到较好的解决，所以在本文不做讨论。本文中对协同 编辑的研究，均指同步协同编辑，即协作成员在同一时间对共享文档进行的协 同编辑。 一个好的协同编辑系统应具有以下四个特点【1 2 】： ( 1 ) 实时性( r e a l - t i m e ) ：系统应能快速响应用户的交互操作并执行结果， 为此本地用户的操作应当立即响应，而远程站点的操作传输延迟应尽量低； ( 2 ) 分布性( d i s t r i b u t e d ) ：协同用户通过各种网络连接在分布的计算机上工 作，并且存在着不确定的网络延迟； ( 3 ) 无约束性( u n c o n s t r a i n e d ) ：允许多个协同用户并发的、随意的浏览和 编辑共享文档视图的任意部分，不对用户施加过多约束，使信息在协同用户之 间自由的、自然的流动； 4 ) 可靠性( r e l i a b i l i t y ) ：系统应对一些故障( 如网络故障、突然掉线、意 外死机等) 进行及时的恢复，用户操作的失误也不应导致整个系统的崩溃。即 应具有一定的容错性。 目前大部分协同编辑系统都在为实现上述目标而努力着。如澳大利亚 g r i f f i t hu n i v e r s i t y 的i n t e m e tc o m p u t i n gr e s e a r c hg r o u p 研究组的r e d u c e t ”1 和 g r a c e t l 4 1 研究课题，分别研究协同文本图形编辑系统中有关并发控制和一致 性维护模型和相关算法，这些模型和算法满足在高延时网络如i n t c m e t 环境中实 现协同编辑的高响应性、高并发性和无约束自由编辑的性能要求。然而， g r a c e 项目中提出的图形对象多版本方法在协同编辑研究领域中颇受争议， 且由于r e d u c e 和g r a c e 中只考虑最简单的协同编辑操作情况，其并发控制 技术还没有应用到商业化软件中。 在此研究基础上，该研究小组又继续研发新的课题项目c o w o r d 和 c o p o w e r p o i n t i l ”，目的是把已有的并发控制技术研究成果与现有的商业软件集 成。其实现方法是通过一个支持协同功能的中间件一一协同引擎( c o l l a b o r a t i v e e n g i n e ) ”把r e d u c e 和g r a c e 的协同编辑模型和算法以协同透明的方式与 m i c r o s o f tw o r d 和p o w e r p o i n t 集成，使单用户商业编辑软件扩展成具有协同编 辑功能的协同编辑软件，并且次过程不需要修改软件源代码。目前已基本实现 了一些简单的文本操作。 在国内，协同编辑研究工作的开展也是如火如荼。清华大学研发的协同设 计支撑系统原型c o d e s i g n 1 6 1 为用户提供一个供所有设计人员共享的虚拟绘图板 2 华东师范大学硕士学位论文第l 章绪论 ( 类似于电子白板的功能，还提供更专业化的c a d 绘图工具) 、实时视频、音频 以及基于文本或语音的消息传送等服务。浙江大学的研究小组研发的一个多层 次图案协同设计系统c o d e s i 凹t ”l ，研究基于分布式应用程序共享方式的协同计 算机辅助设计，特别地，在此基础上研究了用户后加入问题，提出了在分布式 结构下的多后加入s e l w e l 算法。该算法有效地避免了单后加入s 盱v c r 算法可能 带来的同步数据不完整情况；但是，由于同步任务由多个站点共同完成，容易 造成网络拥塞而且也没有提出有效的冗余操作合并方法。 1 3 协同编辑系统关键技术研究 采用分布式结构的协同编辑系统由于没有服务器作中间媒介，出现传输瓶 颈的可能性较小，因此具有鲁棒性、可扩展性、高响应性、灵活性等优点，尤 其适合于目前发展迅速的i n t e m e t 、无线网络等网络延时较高的网络环境。如 v c o l l f 【1 引、g r o u p d e s i g n i 押1 、c o d e s i g n ，g r a c e 1 川等均属于此类。其涉及到 的主要闻题是系统设计实现技术复杂： ( 1 ) 副本一致性维护问题：每个操作需要在分布于各站点的副本上多次执 行，保证操作执行后各站点共享状态一致，这需要采用复杂的并发控制方法来 实现； ( 2 ) 用户后加入问题：协同用户加入协同会话需要后加入的用户在协同会 话进行过程中实现副本同步，其他用户不应受到后加入用户的干扰，因此需要 特别设计后加入算法来实现； ( 3 ) 差错控制问题：在某个站点发生故障、或者网络中断的情况下，需要 采用一定的差错控制机制保证整个协同系统继续运行，才能使系统具有较好的 可靠性、鲁棒性； 因此，分布式协同编辑系统相关问题的研究重点在于怎样更好地解决上述 这些问题所涉及的技术，如一致性维持和并发控制、后加入、差错控制等问 题。 1 3 1 并发控制与一致性维护 并发控制的任务就是避免访问冲突所引起的数据不一致，并发控制是建立 同步协同系统的关键技术之一。在分布式数据库管理系统中，人们就已经开始 重视对数据库中数据的并发操作的控制问题1 3 1 。在分布式协同编辑协同中，一 致性维护( c o n s i s t e n c ym a i n t e n a n c e ) 就是保证在用户并发操作时文档状态的一 华东师范大学硕士学位论文第1 章绪论 致性。具体包括以下三个一致性问题【1 2 1 ： ( 1 ) 结果一致性( c o n v e r g e n c e ) ：当同一操作集合在所有的站点执行后，这 些站点上的文档应当是一致的； ( 2 ) 因果一致性( c a u s a l i t yp r e s e r v a t i o n ) ：对于任意两个操作0 。和o h ，如 果在初始的站点上，仇在o b 生成前已被生成或执行，则在所有站点上0 。都应 早于o b 被执行； ( 3 ) 意图一致性( i n t e n t i o np r e s e r v a t i o n ) ：对于任意操作0 ，其在所有站点 上的执行效果都应保持0 的意图，同时o 的执行效果不影响那些与o 独立 ( 非因果关系) 的操作的执行效果。 结果一致保证了协同编辑结束时最终文本的一致性，因果一致保证了相关 联( 因果) 操作之间的执行顺序，意图一致性保证了操作在远程和在本地执行 效果的一致性并且保证独立操作的执行效果不会互相影响。一般来说，如果以 上三个条件满足，则可以认为文档的一致性得到保证，也就是一致性维护和并 发控制问题得到了解决。 目前针对协同编辑系统的并发控制问题，入们提出了许多种方法，传统的 如加锁、串行化或时间戳方法，到后来e 1 5 s 等人提出的基于操作转换的d o p t 并发控制算法 2 0 1 、s u n 等提出的g o t g o t o 算法【1 2 】【2 1 1 ，s u l e i m a n 、v i d o t 等 提出的s o c t 2 3 4 算法 2 2 1 、文档标注算法【2 3 1 1 2 4 1 、多版本策科1 2 1 等等。然而每一 种并发控制方法都有其适应性和局限性，具体内容将在2 2 节中介绍。 1 3 2 用户后加入问题 当一个新的参与者在某个或多个协作用户已经提交了操作之后才准备加入 到该协作会话中去，则会产生应用初始状态同步问题，这个问题被称为“后加 入”闻科”j 。例如，当一个用户后来如入或重新加入到一个协同编辑系统，这 个新加入的用户的文档状态和其它用户节点的文档状态是不相同的，如果此时 直接在不同的文档初始状态下将相同的用户操作作用在共享文档上，必然会导 致操作结果的不一致。这就需要有一种机制，保证“后加入”的用户也能够正 常的加入到会话中。 目前针对基于分布式结构的协同编辑后加入问题的解决方法，主要是 w e m e rg e y e r l 9 1 等提出的对现有应用状态进行可选择传输的“后加入s e r v e r ”算 法( 也称为单“后加入s e r v e r ”) ，但是该方法容易产生同步数据不完整的情 况。针对该问题，在c o d e s i g n 2 5 嘲中提出了多“后加入s e r v e r ”算法，后加入 c l i e n t 向协同编辑组发出同步请求后，所有在线站点都将自己产生的操作数及 4 华东师范大学硕士学位论文第i 章绪论 相应的操作分别发送给后加入c l i e n t 。多“后加入s c r v c f ”算法能有效的避免单 “后加入s e r v e r ”算法可能带来的同步数据不完整情况，然而，由于同步任务由 多个站点进行可能会造成网络拥塞，而且该算法也没有给出有效的冗余操作合 并方法，所以状态同步效率势必会受到影响。有关后加入问题的具体内容我们 将在第四章进行深入研究。 1 3 3 差错控制问题 在分布式的协同编辑过程中，总不可避免的存在协作节点故障问题。协作 节点故障会影响整个会话的效率，甚至导致协作停顿，因为其它协作节点在不 知情的情况下始终给故障节点发送操作信息从而浪费了资源；而且，在信息同 步过程中，需要协作节点进行响应，如果不能及时响应则会导致协同编辑过程 的停顿。因此，差错控制机制的实现是保证协同编辑系统顺利持续进行所必不 可少的。目前，对这方面研究比较多的是南京师范大学的窦万峰等人i l “，提出 了一个会话管理器查询算法解决协作节点故障问题，基本上实现了系统容错， 然而，该方法还没有与并发控制策略和用户后加入方法很好的集成。 综上所述，目前大部分协同编辑系统都致力于研究在分布式结构下的关键 技术问题，而其中的研究重点和前沿为并发控制和一致性维护问题，以及用户 后加入问题和差错控制闯题等。协同图形编辑是一种基于图形对象的协同编辑 系统，在分布式结构下也具有上述协同编辑所亟待解决的关键问题，而且由于 图形对象有其自身的特点，所以在并发控制和一致性维护问题的解决上又有其 自己的解决方案。 1 。4 本文研究内容 本文在总结分布式协同编辑系统研究成果的基础上，对协同图形编辑系统 的关键技术和问题进行了深入研究，并对这些技术问题提出了相应的解决方 案。本文的研究内容包括以下几点： 1 ) 对协同编辑系统的关键技术进行研究并给出解决方案，其中包括副本一 致性维护、用户后加入及容错控制机制等问题： 2 ) 研究分布式协同编辑系统中目前常用的一些维护协同编辑一致性的并发 控制机制，并分析了它们的不足： 3 ) 研究图形对象的特点，在分布式操作转换算法的基础上提出了基于对象 华东师范大学硕士学位论文 第1 章绪论 特征和操作关系的并发控制算法，并对算法做了进一步的优化，提高了系统的 运行效率； 4 ) 对用户后加入问题进行了深入研究，介绍了后加入的概念及几种典型的 后加入算法；为了保证数据同步的完整性，对传统的单后加入算法进行改进， 并研究了多个后加入者的加入方法和差错控制方法； 5 ) 实现一个原型系统验证上述算法的有效性和正确性。 1 5 本文组织结构 本文的组织结构如下： 第一章绪论 介绍了协同编辑系统的研究背景、意义及研究现状，并指出本文的主要研 究工作。 第二章分布式协同编辑系统中一致性维护研究 研究了分布式协同编辑系统一致性维护问题，以及当前所采用的维护一致 性的主要并发控制方法，并分析了它们的不足；最后对整体一致性模型进行了 详细分析。 第三章分布式协同图形编辑系统中的并发控制研究 分析图形对象的特点，借鉴d o p t 算法的基本思想，提出了基于对象特征 和操作关系的并发控制算法一一b p o p t 算法。对该算法的正确有效性进行了验 证，并对b p o p t 算法作了进一步的优化，使系统的运行效率得到了有效的提 高。 第四章用户后加入的初始化状态同步问题研究 介绍了用户后加入概念以及现有的解决后加入问题的方法，针对不足，提 出了i s l j s 算法。该算法保证了数据同步的完整性，为多个后加入者加入会话 提供了支持，并具有可靠的差错控制能力。 第五章w i j e c t o r 原型系统设计与实现 介绍了基于上述算法实现的w i j e e t o r 原型系统，并举例说明了其运行过 程。 第六章总结与展望 对本文进行总结与展望。 6 华东师范大学硕士学位论文第2 章分布式协同编辑系统中的一致性维护研究 第2 章分布式协同编辑系统中一致性维护研究 用户群分布的协同工作环境中，用户希望多用户编辑系统也具有单用户编 辑器方便快捷的操作特性，因此，多用户并行编辑和网络延时造成的因果冲突 和并发冲突会引起协同编辑的不一致问题。如何维护分布式结构下各个协作节 点共享副本的一致性成为协同编辑领域的一个研究热点。本章主要研究上述不 一致性问题，对各种维护一致性的并发控制机制进行深入的研究和讨论，并详 细分析协同编辑系统的整体一致性模型。 2 1 不一致问题的提出 当某一个用户站点按照他自身的操作意愿对文档进行某一操作时，他将无 法知道远程站点的当前文档状态，以及其它用户正在进行的操作。在网络传输 延时情况下，用户对共享文档进行操作，有可能会引起各个站点共享文档状态 不一致。下面给出一个产生不一致问题【1 2 1 的情景描述： s 缸1s i t e 2s 妇3 围2 - 1 一个协同缩曩场量 如图2 1 所示，有3 个站点，分别是站点1 、站点2 和站点3 。各站点生成 的操作立即在本地执行，然后发送到其他所有站点保持原来形式执行。三种不 一致情况将在以下情景中发生： 1 ) 数据不一致( d i v e r g e n c e ) 操作以不同的次序和时间到达不同的站点执行，导致最终在不同站点操作 的结果不一致。从图2 - 1 中可以看到，在站点s 1 上三个操作的这些次序为： 0 2 - 0 1 专0 3 ，在站点s 2 上的执行次序为0 2 - 0 3 斗0 1 ，而在站点s 3 上的 执行次序为0 3 专0 1 号0 2 。 7 华东师范大学硕士学位论文 第2 章分布式协同编辑系统中的一致性维护研究 2 ) 因果关系违背( c a u s a l i t yv i o l a t i o n ) 操作之间的因果关系被破坏。图2 1 中，在站点s 1 上，用户在操作共享空 间中先看到了0 2 的执行效果，然后才发出0 1 操作。所以，操作0 1 依赖于操 作0 2 ，即这两个操作之间存在因果关系，0 2 是原因操作，0 1 是结果操作。然 而，在站点s 3 上，却是先看到0 1 ，后看到0 2 ，这就破坏了最初0 2 和0 l 之 间的因果关系。 3 ) 操作意愿违背( i n t e n t i o nv i o l a t i o n ) 发起操作的操作者的编辑意图被破坏。在图2 1 中，0 2 与0 3 是两个完全 独立的操作，它们在产生时都无法预知对方的发生。在站点s 2 上，由于0 2 先 于0 3 执行，受0 2 的影响，执行0 3 时站点s 2 的状态已经不同于在站点s 3 上 执行0 3 时的状态了，此时在站点s 2 上继续执行0 3 时，其结果已经与站点s 3 上操作者预计的结果不相同了，这样就破坏了原操作者的意图。 2 2 目前常用的并发控制机制 由2 1 节中的例子我们可以看出，不一致性问题是由冲突操作的错误执行 顺序引起的，避免不一致的简单方式是禁止对同一个对象或数据进行并发操 作。目前常用的并发控制机制主要有以下几种： 2 2 1 令牌轮转( t u r n - t a k i n g ) 每次只允许一个用户持有令牌，该用户对于共享数据或文档有完全的操作 权利。令牌机制下，协同编辑的步骤一般为：某个用户( o j 如主席用户) 启动 协同编辑，并缺省地获得令牌；其他用户如果也想编辑共享文档，则提出令牌 申请，并将自己置于等待队列中；当令牌拥有者主动放弃发言权后，等待队列 中的某一用户即可获得令牌。令牌的获取可由内部协议通过软件方式来实现， 也可以由协作成员通过某种合作协议自行协调。令牌方式独立于应用语义，因 此一般用于应用程序共享系统，如m i c r o s o f tn e t m e e t i n g ，s h a r e d x t 2 7 3 系统采用 令牌方式。 令牌方式每次只允许一个活动用户，不支持并发操作，因此不存在因并发 操作而导致的操作冲突，一致性得以保证。但是令牌机制是一种简单的排他性 方法，阻碍了信息的自然流动，不支持并行的交互操作。如果把令牌交由外部 合作协议控制，则仍可能导致操作冲突，因为用户可能错误地运用规范或者不 遵从规范。这种协同方式并不是真正意义上的实时同步协同设计，无法满足实 华东师范大学硕士学位论文第2 章分布式协同编辑系统中的一致性维护研究 时同步协同系统操作者之间无约束的并发操作需求。 2 2 2 加锁( l o c k i n g ) 加锁策略是在数据库系统以及网络协同应用系统中的一种常用也是非常重 要的并发控制技术，它提供对共享数据的加锁( 1 0 c k ) 和解锁( u n l o c k ) 操作， 用于控制用户的并发操作。为了实现锁的申请和释放，系统中必须有一个协调 进程跟踪和监控哪些对象已被上锁。 c o d i a g r a m ，e n s e m b l e 是采用加锁机制的协同系统 2 s l 。在r e d u c e 1 3 】， g r a c e 1 4 】系统中，加锁机制作为一种可选的并发控制机制。加锁的优点是设计 和实现较为简单。但是在应用于协同系统中存在一定的问题：首先是申请和释 放锁的开销会影响用户动作的快速反馈，并且何时申请或释放，系统很难确 定，又不易由用户控制。其次，被封锁数据的粒度难于确定，过小会加重系统 负担，过大则影响用户操作的并行性。协作文档是多个协同用户共同操作的信 息对象，在结构上按章、节、段的形式来管理，因而可以将锁的粒度设置为 段。基于对象的协同图形编辑系统一般将锁的粒度设置为对象。 加锁机制强调不一致性的避免，而不是一致性管理【2 9 】。它使用某些措施防 止不一致性操作发生，但分布式环境下的协同用户往往不太愿意使用这些控制 机制来约束自己。因此，何时使用加锁机制、怎样进行加锁是协同环境中加锁 机制有效利用的前提。目前提出了一些智能的加锁机制 3 0 1 ，研究尽量在自然方 式下实现加锁的并发控制过程。 2 2 3 序列化( s e r i a l i z a t i o n ) 采用序列化( 串行化) 方式，操作可以并发产生，所有操作在所有站点按 照同一次序执行达到相同结果。序列化可以两种方式实现：悲观和乐观操作执 行方式。悲观方式：延迟操作直到所有先序操作都已执行后执行；乐观方式： 操作产生或收到后立即执行，如果执行后发现有冲突，则u n d o 已经执行的操 作。采用乐观方式系统有：g r o u p d c s i g n t 姗，g r o u p d r a w 3 1 】，l i c r a 【3 2 】。 序列化可以同时解决对象内和对象间的歧义问题。但是序列化协议有以下 问题：首先，不能解决操作意愿冲突问题；其次，如果操作以乐观方式执行， 或者在悲观方式中序列化次序和因果序不一致，那么仍然存在因果冲突；最 后，在悲观方式中，如果操作在一些延迟后执行而不是在它们产生时执行，则 本地操作响应性会受到影响。 9 华东师范大学硕士学位论文第2 章分雍式协同编辑系统中的一致性维护研究 2 2 4 操作转换( o p e r a t i o nt r a n s f o r m a t i o n ) 操作转换法是e m s 【2 0 】首先提出的一种用于协同文本编辑的并发控制方法， 是自动解决冲突而不是手工解决冲突的依赖检测方法，有很好的交互响应性， 支持多用户进行自由文本编辑。其基本思想是并发操作执行前先转换，然后在 各站点以不同的次序执行，最后各站点的文档状态保持一致。显然，操作转换 方法可以解决操作意愿违背的问题，这是传统的并发控制方法所无法做到的。 因此，操作转换方法具有划时代的意义。 操作转换方法早期是用于一维数组结构的文本协同编辑，如g r o v e 2 0 ， j o i n te m a e s l 3 3 ，j u p i t e r 3 4 1 和r e d u c e 1 3 1 等，以及二维数组结构的共享 s p r e a d s h e e t 协同编辑，目前已经将操作转换扩展到更为复杂的树状结构文档的 协同编辑，如x m l 和r i e h t e x t 文档的协同编辑中的操作转换网。下面具体分 析几种典型的基于操作转换的协同编辑并发控制算法。 2 2 4 ，1 d o p t g r o v e l 2 0 1 要求所有操作都必须满足因果关系，创建了后来广为人知的分布 操作转换算法d o p t 。d o p t 算法的基本思想是当操作请求提出时，本地用户立 刻执行操作，同时将此操作与其它一些附加信息一起广播出去；接收到的远程 操作满足因果条件时根据本地已执行的并发操作做适当的转换。从本质上看， d o p t 算法采用了包含变换( i n c l u s i o nt r a n s f o r m a t i o n ) ，即变换操作0 l ，将它的 并发操作0 2 对文档的影响包含进来，从而实现了因果关系与操作意愿维护。不 过它并没有解决数据不一致问题p 卯。 2 2 4 2 a d o i 呵e d a d o p t e d 算法由m r c s s e l 和rg u n z e n b a u s e r 提出【3 3 】。a d o p t e d 算法引 入l 变换( l - t m n s f o r m a t i o n ) 以取代d o p t 算法的包含变换，这是a d o p t e d 算法与d o p t 算法的唯一区别。a d o p t e d 算法采用一个n 维( n 是站点数) 的交互模式图来保存所有操作可能的形式( 生成、中间和执行) 和一个线性日 志保存操作的生成形式。n 维交互模式图可以看作是j u p i t e r 二维状态空间向量 的推广。a d o p t e d 算法保证了因果关系维护和操作意愿维护，基本解决了数据 不一致问题。 l o 华东师范大学硕士学位论文 第2 章分布式协同编辑系统中的一致性维护研究 2 2 4 3 g o t ，g o t o c h e n g z h e n gs u n 等人在总结d o p t 算法和a d o p t e d 算法的基础上提出了 一种基于操作变换的g o t 算法【1 2 1 2 “。数据不一致问题由操作的全局次序和 u n d o d o r e d o 策略解决，因果关系违背由状态向量解决，操作意愿违背由包含 变换( i n c l u s i o nt r a n s f o r m a t i o n ) 和剔除变换( e x c l u s i o nt r a n s f o r m a t i o n ) 一起解 决，e t 用于消除一个操作对另一个操作的影响，由于操作定义上下文可能不 同，e t 的实现更复杂。 之后，c h e n g z h e n gs u n 和c a e l l i s 在g o t 算法的基础上提出一种优化 算法g o t o 算法【1 2 】【2 1 1 。它借鉴d o p t 算法中的包含变换和a d o p t e d 算法 中的l 变换的属性，扩展了g o t 算法中的i t 和e t 变换，无需 u n d o d o r e d o 策略或多维图就解决了操作意愿违背和数据不一致。g o t o 算法 减少了包含变换i t 和剔除变换e t 的使用频率，一定程度上优化了g o t 算 法。 2 2 4 ，4 o o d 0 p r 2 0 0 0 年由杨光信等人提出的基于对象数据模型的o o d o p t i s 提供了语义上 更为丰富的抽象数据类型，提供了一种分布式结构下的并发控制框架，其核心 部分与d o p t 相似，主要的区别在于对象即操作日志的维护方式；o o d o p t 可维 护多个对象并为每个对象维护一个单独的操作日志，按执行顺序保存所有可能 改变对象状态的原子操作，用户界面上的所有操作都将转换成目标对象的方法 调用。o o d o p t 提供了语义上更为丰富的抽象数据类型，但对于特定应用的限 制条件的同步维护方面仍然有一定的困难。 通过对几种典型的操作转换算法的研究，我们可以看出操作转换与应用语 义紧密相关，所以对于不同的对象结构、不同对象操作都需要实现专门的操作 转换函数，因此，操作转换方式实现较为复杂，尤其是对于复杂文档结构和复 杂操作，如何证明操作转换函数的正确性已成为一个重要而复杂的问题。 2 2 5 文档标注算法 操作转换方法着眼于操作本身，后来涌现出了以文档为主要研究对象的文 档标注方法。1 9 9 9 年，何鸿君等人提出了文档标注算法【2 3 1 ，它以文档本身为研 华东师范大学硕士学位论文第2 章分布式协同编辑系统中的一致性维护研究 究对象。无论某一操作执行前发生了多少并发操作，通过对共享文档加标注的 手段，把并发操作执行所引起的文档变化部分屏蔽起来，使该操作执行时的文 档状态仍然与该操作产生前瞬间的文档状态一致，从而实现操作意愿的维护。 2 0 0 2 年，吴筱媛等人口】发表文章对文档标注算法进行了一些改进，引入了 状态向量以代替操作的上下文，站点产生操作以后，传送的状态向量的长度是 固定的。原有的文档标注方法当操作传送时必须将该操作的上下文一起传送， 它会随着操作的不断增加呈线性增长，这样做的代价太大。文档标注算法解决 了因果关系违背和操作意愿违背，但是没有给出解决数据不一致问题的方案。 2 2 6 多版本( m u l t i v e r s i o n ) c h e n 和s 锄【6 l 川等人提出了在基于对象的协同图形编辑系统中的多版本算 法，其基本思想是把共享工作空间的所有图形对象看成是独立的个体，用多个 属性值来标识某个具体的对象，而且对象相互独立，对某个对象属性的修改不 会影响同一对象的其它属性以及共享工作空间的其它对象。如果两个操作没有 冲突则可以部分次序地直接执行，而不影响执行效果。如果对同一个对象的相 同属性并发地进行修改就可能导致操作冲突，每次有冲突产生时就产生一个新 的版本【1 刈州。 多版本策略首先在g r a c e 1 4 】中得到应用。多版本策略下，操作一经产生 立即在本地用户界面上执行，并打上时间戳，保存到本地操作历史日志中，然 后向所有远程节点广播。共享