（计算机软件与理论专业论文）分布式实时协同文本编辑系统的研究与实现.pdf

摘要 摘要 近几年来，计算机支持的协同工作作为一个重要的研究领域越来越受到人 们的重视，目前正处于蓬勃发展之中。本文研究c s c w 的一个分支一一实时协同 文本编辑系统。实时协同文本编辑系统允许多人协作实时地完成对同一个文档 的编辑。协同编辑系统要解决许多技术问题，特别是在出现并发操作的情况下 维护文档的一致性的问题。本文在研究了现有的并发控制算法的基础上，提出 了一种新的一致性维护算法一一折叠式操作变换( f o p t ) 算法，并在该算法的 基础上构建了一个基于e c l i p s e 的实时协同编辑插件，该插件可以对分布式虚拟 结对编程提供支持。 f o p t 算法包含三个部分，因果关系维护、操作变换和垃圾操作回收。因果 关系维护使用熟知的基于状态向量的技术，通过使用状态向量来捕获操作之间 的因果关系，并保证只有满足因果顺序的操作才能调度去变换和执行。操作变 换是我们的主要关注和贡献，其主要思想是通过合理地组织操作历史缓冲记录 使之与文档本身形成一种映射关系，并在操作变换的过程中采用隐藏恢复并发 操作的机制来解决并发冲突。垃圾操作回收将对操作变换来说无用的操作从历 史缓冲区中去除，从而减少内存的消耗。文中我们对算法进行了详细描述并给 出了具体的例子加以说明。 e c l i p s e 实时协同编辑插件的设计与实现是我们关注的另外一个重点。我们 分别从通信层、会话管理、协同感知、一致性维护及与e c l i p s e 集成这几个方面 对系统的设计与实现问题进行了考察。在通信层，我们采用了j a b b e r 作为通信 平台，并在此基础上设计了一个可进行消息恢复的可靠传输机制。会话管理机 制对于组织一群用户参与的协作来说是非常重要的，我们设计了一个基于发起 人模式的会话管理协议，该会话管理协议能够支持一种特定的协作编程模式， 并且允许站点中途加入会话。在协同感知方面，我们利用了j a b b e r 作为即时通 信平台所拥有的一些固有特性，简化了系统的开发。在设计插件的过程中，我 们也对e c l i p s e 技术进行了研究，开源的、高度可扩展的e c l i p s e 平台大大方便 了我们的开发。 关键词：计算机支持的协同工作，协同编辑，并发控制，一致性维护，f o p t a b s t r a c t a b s t r a c t r e c e n t l y ，c s cw ，a sa i li m p o r t 姐tr e s e a r c ha r e a 面c o m p u t e rs c i e n c e ，d e v e l o p s r a p i d l ya n do b t a i n sm o r ea i l dm o r en o _ 【i c ef r o mt 1 1 ep u b l i c t h i st 1 1 e s i si sa b o u t r e a l t i m ec o o p e r a t i v et e x te d i t i n gs y s t e m ，w h i c hi sab r a n c ho fc s c wr e s e a r c h t b d e s i g nr e a l t i m ec o o p e r a t i v ee d i t i n gs y s t e m 、v em u s tr e s o l v em a n yt e d m i q u e p m b l e m s ，e s p e c i a l l yt om a i n t a i nc o n s i s t e n c yo ft 1 1 e s h a r e dd o c 啪e n tu n d e re d i t w h e nc o n c u r r e n to p e i j a t i o ni s p r e s e n t t h i st h e s i sp r o p o s e san o v e lc o n s i s t e n c y m a i n t e n a n c em e c h a n i s m - m ef o p tc o n s i s t e n c ym a i n t e n a n c ea l g o r i t h m - b a s e do n p r e v i o u sr e s e a r c ho nc o n c u r r e n tc o n t r o l ，a n db u i l d sap l u g i nf o re c l i p s e t h e p l u g i nc a 工1b eu s e d t os u p p o r td i s t r i b u t e dv i r t u a lp a i rp r o g r a m m i l l g t h ef o p ta l g o 矾u ni n c l u d e s 妇e ep a n s ：c a s u a lo r d e rp r e s e r v a t i o n ，f o l d i n g o p e r a t i o n1 y a n s f o m a t i o ns c h e m e ( f o p t )a l l dg a r b a g ec o l l e c t i o n w eu s ea w e l l k 1 1 0 w nt e c h n i q u eb a s e do ns t a t ev e c t o rf o rc a s u a lp r c s e r v a t i o n t h em e t h o d u s e ss t a t ev 色c t o rt oc a p t u r ec a s u a lo r d e rr e l a t i o nb e t w e e no p e r a t i o n sa 1 1 dg o v e mt h a t o n l yo p e r a t i o n st h o s ea r ec a s u a lr e a d yc a nb ed i s p a t c h e dt o 订a n s f b r n la n de x e c u t e t h ef o p ts c h e m e ，w h i c hi st h ef o c u so fo u rr e s e a r c h ，i su s e dt op r e s e n r eu s e r i n t e n s i o na n dc o n v e r g e n c e t h em a i ni d e ao ff o p ti st om a i n t a i nam a p p i n g r e l a t i o nb e t w e e nd o c u m e n ta 1 1 do p e r a t i o nh i s t o r yb u f f e rt 1 1 r o u 曲p r o p e ro r g a n i z a t i o n o ft l l e h i s t o r yb u f 托r ， a n dt or e s 0 1 v e c o n c u r r e n c yc o n n i c t sb ye r n p l o y i n ga h i d e r e s u m es c h e m e t h eg a r b a g ec 0 1 l e c t i o n p a r tr e m o v e so p e r a t i o n st h a ta r e i n d e p e n d e n to ft h ef o p ts c h e m et or e d u c em e m o r yf o o t p r i n t t h ed e s i g na i l d d e v e l o p m e mo fm ec o o p e m t i v ee d i t i n gp l u g i nf o re c l i p s ei s a n o 也e re m p h a s i sw ef o c u so n w ee x p l o r ed e s i g na n di m p l e m e m a t i o nc o n s i d e r a t i o n o ft h es y s t e mf 如ms e v e r a lp e r s p e c t i v e s ：c o m m u n i c a t i o nl a y e r ，s e s s i o nm a n a g e m e m ， c o o p e r a t i v ea w a r e n e s s ，c o n s i s t e n c ym a i n t e n a n c ea n di m e g r a t i o nw i t he c l i p s e w e c h o o s ej a b b e ra st h ec o m m u i l i c a l i o np l a t f b ma n dd e s i g nar e l i a b l et r a l l s p o no v e ri t s e s s i o nm a l l a g e m e n ti si m p o n a i l tt oo r g a n i z ec o l l a b o m t i o na l n o n ga g r o u po f p e o p l e w ep r o p o s eas e s s i o nm a l l a g e m e n tp r o t o c 0 1b a s e do ni n i t i a t o lt 1 1 i sp r o t o c 0 1c a 工1 a b s 豫a c t s u p p o r tas p e c i a lc o l l a b o r a t i v ep r o g r 彻i n gp a i t e ma n da l l o w s s i t e st oj o i na s e s s i o nw i m o u tp a u s i n gt h eo p e r a t i o np r o c e d l 王r e i nm ed e s i g no fc o o p e r a t i v c a w a r e n e s s ，w eu t i l i z ej a b b e r sb u nf e a t u r e st os i m p l 姆也ed e v e l o p m e n t w ca l s o s t u d ye c l i p s ep l u g - i nt e c h n j q u ef o ri n t e 群a t i n g o u rc o m p o n e mi m oi t t h eo p e n s o u r c ea n d1 1 i 曲l ye x t e n d a b l ee c l i p s ep l a t f o r i l lb e n e f i t su sm a n y 趾da c c e l e r a t e so u r d e v e l o d m e n t k e yw o r d s ：c s c w ，c 0 0 p e r a t i v ee d i t i n g ，c o n c u 玎e n c yc o n 廿0 1 ，c o n s i s t e n c y m a i m e n a l l c e f o p t 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获得电子科技大学或其它教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明 确的说明并表示谢意。 签名：建盈! 邑二日期：2 卯簿，月日 关于论文使用授权的说明 本学位论文作者完全了解电子科技大学有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁 盘，允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文 的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或 扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后应遵守此规定) 签名：丕盈鉴导师签名：至堕氢 日期：驴香年f 月) 日 第一章绪论 1 1 引言 第一章绪论 自从2 0 世纪8 0 年代计算机支持的协同工作( c s c w ：c o m p u t e rs u p p o r t e d c 0 0 d e r a t i v ew o r k ) 这一概念正式提出以来，c s c w 受到了来自各个领域的研究 人员广泛的关注，发展到今天已经具有相当的规模和影响力，大量的研究成果 开始运用到实际应用中。可以说现在c s c w 这一理念已经是无处不在，它的研究、 发展和应用正在影响和改变人们的工作和生活方式。 据市场分析机构i d c 的报告指出，2 0 0 7 年协同软件的市场规模将从2 0 0 2 年的 4 5 亿美元扩增到1 3 0 亿美元，增长率6 5 。而中国软件市场到2 0 0 7 年有望达到 5 1 6 2 5 亿的市场容量。另一家咨询机构g a r t n e r 称，从2 0 0 3 年开始，协同软件已 成为用户应用软件采购的最大热点，2 0 0 5 年全球协同软件市场的营业额将近5 0 0 亿美元，到2 0 0 6 年其市场规模将赶超企业资源规划系统( e r p ) 。在我国，业界 对协同软件的前景也颇为乐观。据专家预测，2 0 0 5 年我国用户用于采购协同软 件的资金额将达到2 0 0 3 2 0 亿元。 由此可见其中蕴涵的商机巨大，许多商业软件公司都已经或者正在加入到 这一领域的竞争，包括微软、i b m 、甲骨文等公司在内都推出了各自的协同软件， 比如我们耳熟能详的微软的o f f i c e 系列软件，e x c h a n g es e r v e r ，n e t m e e t i n g 以及i b m 的l o t u sn o t e s ，w o r k p l a c e 等都是得到广泛使用的协同软件，里面运用 了c s c w 研究的大量成果。许多其他的办公自动化软件( o a ) 也在朝着协同的方 向发展。国内的很多公司目前也在开始力推“协同软件”的概念，尽管大家对 “协同”概念的理解并不一致，各种定义版本层出不穷，人们也莫衷一是，但 是这也从一个侧面反映了协同软件市场正处于快速发展期。 新技术的出现加速了c s c w 发展，互联网社会化也成为一种新的趋势。近年 来，随着大量新兴技术( 如网格技术，w e b 服务技术，p 2 p 技术，语义与知识处 理技术、x m l 等) 的出现，c s c w 的研究领域得到进一步的扩展和充实。i n t e r n e t 在最近的十多年中得到了长足的发展，已经深入到我们的日常生活中，目前正 呈现出一种社会化的趋势，许多研究者认为人类社会正在互联网络空间中形成 电子科技大学硕士学位论文 一种新的心理空间或社会性与认知过程的空间。社会科学的一些理论开始运用 于软件设计中，出现了所谓的“社会软件”的概念，该术语通常用来描述允许 群体进行通讯、交互和合作的软件，广义上讲，包括了在线共同体、计算机协 同工作平台以及新出现的群体类软件，如网络游戏，博客( b l o g ) ，维基( w i k i ) 、 即时通信( i m ) 和其他多对多社群系统等，可以算作是c s c w 的自然的扩展。有 人认为社会化是一场正在到来的互联网革命，社会软件的崛起是一个明显的技 术标志，互联网应用模式开始从传统的“人机对话”逐渐转变为“人与人对话”。 从即时通信和文件共享等协同软件的流行上我们可以发现，人们对于能够促进 人与人之间信息共享和交互的程序具有非常浓厚的兴趣，毕竟人是社会的人， 交流和协作可以促进人际关系的发展，同时也能促进工作效率的提高。 面对这样一个快速发展的、前途光明的、市场潜力巨大的研究领域，我们 准备好了吗? 在国内，尽管c s c w 的概念在高校及科研机构已经基本形成，大量 的来自各个领域的学者及相关研究人员正积极的参加到c s c w 的研究中来，并且 也取得了许多不错的成果，但是，上述研究要延伸到国民经济的各个领域，得 到企业界、产业界甚至政府主管部门的普遍共识还有相当长的路要走。因此， 研究c s c w 的核心技术及其应用具有重大的现实和经济意义。 1 2 研究背景 1 2 1 计算机支持的协同工作( c s c w ) 计算机支持的协同工作的定义 1 为：地域分散的一个群体借助计算机及其 网络技术，共同协调与协作来完成一项任务。其本质是通过计算机技术使处于 不同地理位置的人们能够互相协作，并且感觉不到地理位置上的差异。计算机 支持的协同工作是在1 9 8 4 年由m i t 的i r e n eg r i e f 和d e c 的p a u lc a s h m a n 两位研究 员在描述他们所组织的有关如何利用计算机来支持不同领域和学科的人们共同 工作的研究课题时首次正式提出的。 c s c w 的研究范围非常广泛，包括各种与群体协同工作相关的方式方法、技 术和应用的研究，人们通常用群件( g r o u p w a r e ) 来指代这一领域。c s c w 旨在 建立协同工作的环境，改善人们进行信息交流的方式，消除或减少人们在时空 分隔时交流的障碍，从而提高群体工作的质量和效率。 协同应用领域非常广泛，例如电子商务，远程医疗，远程教育和学习，远 第一章绪论 程协作研究，协同c a d ，协同电子政务，协同军事系统等等。随着技术和理论的 发展，应用的领域和类型必将更为广泛。 c s c w 可以分成几种不同的模式。按照人们合作的方式的不同和协作者的地 域分布从时间和空间将c s c w 分四种不同的模式：同步模式、分布式同步模式、 异步模式和分布式异步模式。同步模式主要用于支持象决策会议这种本地群组 之间面对面的实时协作，如各种会议室系统。它们所要达到的一个主要目标就 是“你见即我见”( w y s l w i s ，w h a ty o u s e ei sw h a tis e e ) 2 ，3 。分布式同 步模式系统中的用户通常是分布在不同的地理位置处。此种系统的典型代表有 多媒体桌面会议系统。支持异步模式的系统有共享文件、t e 锄r o o m s 等系统。 这类系统由于用户的地理位置不具有分散性，同时用户对它们的访问也是异步 的，因此不需要数据的实时传递。它关注的重点更多的在于如何保证“长事务” 处理中数据的一致性与用户之间的互相感知。支持分布式异步模式的系统比较 多，包括b b s 、电子邮件、协同w w w 等等。 c s c w 应用的类型众多，按照应用目的的不同，c s c w 主要分为工作流管理系 统，多媒体计算机会议和协同设计系统。这些是传统的典型的c s c w 应用，新的 c s c w 应用多种多样，也许我们无法将其归类为上述任何一种类型。 如引言部分所述，c s c w 从提出到现在吸引了众多的计算机科学工作者参与 研究，现在已经进入快速发展期。它的实现将从根本上改变人们传统的工作方 式和生活方式。c s c w 系统的庞大需求和复杂性对系统开发者而言无疑是一个巨 大的挑战，许多方面的理论和技术问题仍然存在，一些关键的技术仍未成熟， 等待着我们进行进一步的深入的研究。 1 2 2 协同编辑及其核心问题 1 2 2 1 协同编辑的定义和发展 协同编辑系统，又称计算机支持的协同编著( c s c a ：c o m p u t e rs u p p o r t e d c o o p e r a t i v ea u t h o r i n g ) 系统是c s c w 中的一种非常有用的工具 3 ，它允许不 同时间不同地点的用户协作完成文档的编辑，从而大大提高群体工作的效率。 协同编辑可以应用于计算机会议系统，远程协作学习，协同办公，协作编程等 领域并与之集成。 协同编辑其实并不是一个新的概念，有人将其定义为多人参与的产生一个 文档的活动过程。人们在日常生活中早已经在实践着这个过程。而计算机技术 电子科技大学硕士学位论文 的发展则为这种活动提供了更多的便利性。e m a 订便是应用于异步协作的一个典 范。2 0 世纪8 0 年代c s c w 概念提出以来，计算机支持的协同编辑作为一个重要的 研究方向得到了开发人员的重视，各种支持协同编辑的软件也被开发出来。 协同编辑按编辑的内容可分为：协同文本编辑、协同图形编辑和协同图像 编辑等，按时间特性可分为实时( 同步) 的和非实时( 异步) 的。其中支持异 步协同编辑的如e m a i l ，c v s ，w i k i ( w a r dc u n n i n g h a m ，1 9 9 5 ) 等。支持同步( 实 时) 编辑的具有代表性的系统有g r o u p s k e t c h ( g r e e n b e r ga n db o h n e t ，1 9 9 1 ) 、 g r o v e ( e 1 1 i s ，g i b b s ，a n dr e i n ，1 9 9 1 ) 、s h r e d i t ( m c g u f f i na n do l s o n ，1 9 9 2 ) 、 d i s t e d i t ( k n i s t e ra n dp r a k a s h ，1 9 9 0 ) 、c a s c a d e ( b o r d i n ，1 9 9 7 ) 、r e d u c e ( s u n e ta 1 ，1 9 9 7 ) 等。还有些系统既支持同步编辑又支持异步编辑。 目前，异步协同文本编辑技术已经比较成熟，并已经得到广泛应用，但是 仍然存在一些问题，如并发控制的粒度粗，数据传输的效率低等。而实时协同 编辑的研究虽然起步比较早，研究也比较深入，到目前为止人们建立了各式各 样的实时协同文本编辑系统，这些系统采用的技术多种多样，所具有的功能也 不尽相同，但是大部分系统由于采用的技术的局限性，仍然无法实现和本地编 辑应用一样自然流畅的交互。 近年来，实时协同编辑也开始在一些商业产品中得到应用，绝大部分的计 算机会议系统都包含了协同编辑工具，协同编辑也在计算机支持的协作学习系 统和一些群件系统中得到了应用。许多商业软件公司也推出了各自的协同软件， 其中都包含某种类型的协同编辑功能。如微软的n e t m e e t i n g 、s h a r e p o i n t 。还 有l o t u s 公司原创始人r a yo z z i e 建立的g r o o v en e t w o r k s 公司开发的g r o o v e v i r t u a l0 f f i c e 4 ，该软件使用p 2 p 技术开发，支持在虚拟的协作空间中进行 协同编辑操作。国内也有不少研究机构正在进行这方面的研究，并且也出了不 少的成果，产生了巨大的经济效益。如清华大学计算机系进行的c e r n e t 上的多 媒体计算机会议与协同编著系统的研究、协同编著系统d c a ，中科院计算所的 c o e d i t o r 等。 与单用户的编辑器相比，目前的实时协同文本编辑器功能仍嫌原始和简单， 要支持更复杂和更高级的操作还需要进行大量的研究，许多问题期待我们去解 决。 值得注意的是，当前流行的技术越来越多地在协同编辑系统中得到应用。 比如w w w 与协同编辑的结合，移动代理、x m l 和p 2 p 技术在协同编辑系统中的应用 第一章绪论 等。由于移动网络和终端设备技术的发展，移动协作也成为了一个重要的研究 方向。 1 2 2 2 协同编辑研究的核心问题 协同编辑作为c s c w 的一个分支应用，与c s c w 共享许多的关键技术，如群组 通信、访问控制和安全等。当前协同编辑技术的研究热点主要集中在并发控制 ( 或者说是一致性维护) 算法、体系结构、协作感知技术等方面。 并发控制算法是协同编辑的核心，主要解决多人同时编辑同一文档时保证 文档的一致性。一般区分为悲观的和乐观的并发控制两种，其中基于操作转换 的乐观并发控制算法被认为是最有希望实现自由流畅交互的并发控制算法，研 究者在这方面发表了大量的论文，目前提出的大部分算法基于全复制结构和线 性的文档模型，当前的并发控制机制在效率，控制的粒度以及应用于更复杂的 文档模型等许多方面仍然需要改进。 大部分并发控制算法在保证符号意义上的一致性方面提出了解决方法，而 语义一致性的保证则更加复杂，其研究仍处于初始阶段。 在协同编辑的体系结构方面，可以分为集中式体系结构、分布式体系结构 和混合式体系结构，这些结构具有各自不同的优缺点，实际构建系统时应该加 以权衡。 协作感知技术可以让用户感觉到所处的群体工作环境，可以更好地促进用 户的协作，因此也得到了研究者们的关注。 1 2 3 协同编辑与虚拟结对编程 计算机软件在过去的一二十年中发展很快，软件系统的规模变得越来越大， 复杂度也越来越高。软件需求的变更越来越频繁，越来越快速，需要更短的开 发周期。传统的软件开发过程在面对这种变化趋势时，显得有点力不从心，原 因是传统的软件开发过程一般都具有精细而复杂的规则和流程，需要预先进行 深入的设计，如果之后设计发生变更的话，代价往往非常高昂，常常使项目的 进度受到影响，导致项目无法按期完成。 面对这样一种情况，k e n tb e c k 等在1 9 9 6 年提出了极限编程 ( e x t r e m ep r o g r a m m i n g ，简称x p ) 的概念，极限编程是一个轻量级的、灵巧的 软件开发方法，同时它也是一个非常严谨和周密的方法。它的基础和价值观是 交流、朴素、反馈和勇气，即任何一个软件项目都可以从四个方面入手进行改 电子科技大学硕士学位论文 善：加强交流；从简单做起；寻求反馈；勇于实事求是。x p 是一种近螺旋式的 开发方法，它将复杂的开发过程分解为一个个相对比较简单的小周期，通过积 极的交流、反馈以及其它一系列的方法，开发人员和客户可以非常清楚开发进 度、变化、待解决的问题和潜在的困难等，并根据实际情况及时地调整开发过 程。极限编程拥抱变化，并将它们快速地集成到正在演进的系统中，对小型或 者中型的软件开发团队来说非常有效。 结对编程( p a i rp r o g r a m m i n g ) 是极限编程中的一条重要的实践原则。在 x p 中，所有的代码都是由两个程序员在同一台机器上一起完成的，一个程序员 控制计算机并且主要考虑编码细节，另外一个人主要关注整体结构，不断的对 第一个程序员写的代码进行评审。这是x p 中让人争议最多、也是最难实施的一 点。看起来这样象是在浪费人力资源，但是各种研究表明事实恰恰相反，这种 工作方式极大地提高了工作效率。原因是： _ 它保证了所有的代码、设计和单元测试至少被另一个人复核过，代码、 设计和测试的质量因此得到提高。 _ 项目开发中，每个人会不断地更换合作编程的伙伴。因此，结对编程不 但提高了软件质量，还增强了相互之间的知识交流和更新，增强了相互 之间的沟通和理解。 _ 一对程序员可能比单个的程序员更好地理解需求，并且使设计更接近需 求。 _ 一直跟踪程序员意图的同伴对于判断程序的表达和找寻错误更合适。 一对程序员可以帮助彼此维护测试实现的不同原则。 这不但有利于个人，也有利于整个项目、开发队伍和公司。从这点看，结 对不仅仅适用于x p ，也适用于所有其它的软件开发方法。 很多程序员一开始是被迫尝试这点的( x p 也需要行政命令的支持) 。开始时 总是不习惯的，而且两个人的效率不会比一个人的效率高。这种做法的效果往 往要坚持几个星期或一两个月后才能很显著。据统计，在所有刚开始结对编程 的程序员中，9 0 的人在两个月以后都很认为这种工作方式更加高效。 结对编程一般要求两个程序员坐在一台计算机前面，使用一个键盘，一个 鼠标和一台显示器，一个程序员负责编写源代码，另外一个程序员负责系统设 计，检查错误，解决问题和代码审查。这种类型的结对编程是受限的。首先， 第一章绪论 两个程序员必须位于同一地点，面对面的交流i 其次因为只有一套输入设备， 总有一个程序员无法掌握输入权，但是却可能存在两个程序员都需要输入的情 况，比如在一个程序员进行代码审查时如果发现错误，他需要打断另外一个程 序员的工作，让那个程序员修改错误，如果他自己能够直接改正错误显然更方 便，另外在一个程序员写代码时另外一个程序员也可能需要增加代码注释。 虚拟结对编程弥补了结对编程的这些遗憾，它允许两个程序员坐在自己的 计算机前面，通过网络的连接，实时地协作完成代码编写。 协同编辑正好可以满足虚拟结对编程的这种需求，现在已经开始有这方面 的尝试。比如将各种共享窗口应用程序( 如n e t m e e t i n g ，s h ”e d x ) 用于支持虚 拟结对编程，这种方式在局域网环境下效果较好，但是在面对复杂的网络环境 时表现并不好：另外就是采用协同编辑技术的编程环境，如为e c l i p s e 开发的 s a n g a m 插件、g c l i p s e ，j b u i l d e r 2 0 0 6 和r e c i p e 原型协作编程环境等，它们采用 的并发控制算法有传统的t u r nt a k i n g 算法也有新的基于操作转换的算法。 13 本文的工作 为达到快速响应的口的，【n t e r n e t 环境下的实时协同编辑系统一般采用全 复制体系结构，将文档复制到各个参与站点处，这样就要解决文档拷贝的一致 性维护问题。一致性维护( 或者说并发控制) 是实时协同编辑系统中需要解决 的核心难题。 传统的算法( 如加锁、串行化、时间戳或者基于令牌的算法等) 将导致用 户界面受限或者不自然的突变，难以满足实时、自然和流畅交互的目的，对于 交互式群件应用是不舍适的。目前较有希望实现自然、自由交互目的的协同编 辑并发控制算法主要有下面三类：基于操作转换的并发控制算法、多版本方法 和文档标注方法。 但是这些算法并没有完全成熟，仍存在这样那样的缺点。操作转换粪算法 中操作之间的关系比较复杂，要考虑全面很不容易。尤其是对一些特殊情况的 处理非常复杂，很难验证算法是否满足一致性条件。并且基于操作转换的算法 要么时间复杂度比较高，要么对空间的需求比较大。文档标注算法在文档中包 含删除字符，改变了文档的结构，在改造遗留程序时，由于没有编辑器的源代 码，要实现的话就只有创建额外的存储结构，浪费空间且低效，而且在文档中 码，要实现的话就只有创建额外的存储结构，浪费空间且低效，而且在文档中 电子科技大学硕士学位论文 包含删除的字符也将使得文档基本操作的高效实现也很困难，比如插入一个字 符需要从头开始搜索文档，另外，标注文档的操作要扫描整个文档，时间复杂 度是文档包含的字符数的线性阶，而文档包含的字符数很多，因此在时间上效 率也不高。多版本算法主要是应用于协同图形编辑系统的并发控制，尽管理论 上也可以用于文本编辑，但是需要为每个字符分配一个标识，由于一般的文档 都具有成千上万个字符，这样做目前来说是不经济的。 考虑到这些问题，本文在研究分析了各种并发控制算法，尤其是操作转换 类算法和文档标注算法的基础上，提出了一种新的一致性维护算法一一f o p t 一 致性维护算法。该算法不改变文档的结构，而是将己执行了的操作记录到历史 缓冲区中，执行并发操作前先对操作进行变换，变换是通过对历史缓冲区中的 记录进行隐藏恢复来实现的，综合了操作转换类算法和文档标注算法的优点， 具有更好的时间效率。 另外本文也研究了协同文本编辑器的相关技术( 如会话管理，协同感知等) ， 并设计和实现了一个e c l i p s e 的插件用来验证一致性维护算法和支持虚拟结对 编程，尽管该插件功能仍不完善，但是为我们的进一步研究提供了良好的实践 基础。 1 4 论文组织 本文共分为六章，各章内容如下： 第一章为引言部分，主要介绍了本课题产生的背景、研究内容和意义： 第二章介绍了协同文本编辑相关的技术，首先介绍协同编辑系统的协作组 织模式、分类和体系结构，然后对一致性维护算法、协作感知技术、会话管理、 访问控制和安全以及协作通信技术做了介绍，详细叙述了当前存在的各种一致 性维护算法及其原理； 第三章介绍了e c l i p s e 技术，对e c l i p s e 平台、p d e 、j d t 和扩展点的概念做 了简要介绍： 第四章提出了一种新的f o p t 一致性维护算法，并对该算法的思想做了详细 的描述和分析： 第五章介绍基于e c l i p s e 的协同编辑系统插件的设计和实现。先提出总体的 设计模型，然后分别从通信层、会话管理、协同感知、一致性维护和与e c l i p s e 第一章绪论 集成这几个方面对设计和实现方案做了论述； 第六章总结全文，并提出下一步的研究任务。 9 电子科技大学硕士学位论文 第二章协同编辑技术综述 协同编辑( 又称协同编著、协同写作) 指的是由多人参与产生一个文档的 过程 2 ，1 。协同编辑器，又称为组编辑器( g r o u pe d i t o r ) 指的是支持协同编 辑的应用程序，它允许一组地理位置分散的用户通过网络连接同步或者异步地 对文档进行查看和编辑。 从c s c w 的概念提出以来，协同编辑器作为c s c w 系统的基本工具之一，受到 研究和开发人员的重视，成为了c s c w 研究中的一个热点。人们对协同编辑的关 键技术，如组织模式、体系结构、协作感知、并发控制以及其他协作控制技术 等进行了深入的研究，取得了许多重要的进步，并在此基础上建立了各种原型 和应用系统，为协同编辑系统乃至c s c w 的研究提供了指导和实践。 本章将简要介绍协同编辑的协作组织模式和分类，并重点描述实时协同编 辑系统中的关键技术，尤其是其中用来维护一致性的并发控制算法。 2 1 协作组织模式 与一般的c s c w 协作模型相比，协同编辑的协作组织模式具有自己的特殊性， 它涉及到协作成员如何管理? 采用何种文档结构? 采用何种协作模式( 同步或 是异步) ? 任务如何在成员之间分配? 同步协作时，如何保证数据的一致性? 诸如此类的一系列问题。在编辑过程当中，成员之间需要通信、协调和协作。 根据e d e 和l u n s f o r d 的研究指出在协同编辑中存在七种组织模式 5 ，1 ： 整个小组一起规划写作任务，然后每个作者负责文档某个部分的写作， 最后将各个部分汇集起来，根据需要修改整个文档。 _ 整个小组一起规划写作任务，然后某个成员准备一个草稿，最后小组 一起修改这个草稿。 _ 组内某个成员规划写作任务并撰写一个草稿，然后小组一起修改草稿。 _ 某个作者提交一个草稿，然后一个或多个其他成员不与作者交互修改 这个草稿。 _ 整个小组规划写作任务并撰写一个草稿，然后一个或多个成员不与原 1 0 第二章协同编辑技术综述 作者交互修改这个草稿。 _ 一人规划和分配写作任务，每个成员完成各自部分，然后由某个成员 编辑并修改文档。 -某个人口述，另一个人记录，然后编辑成文档。 在协作中满意度受到以下因素的制约 6 ： 协作目标是否清楚；成员间是否能够相互尊重并共享信息；各个成员对文 档的控制程度；文档作者能够在何种程度上对别人的修改做出反应；成员间的 信用关系以何种方式被确认；怎样管理冲突和解决争端；成员受到外界条件( 如 截稿日期、技术或法律要求等) 制约的数量和类型；组织内项目进展情况等。 2 2 协同编辑系统的类型 2 2 1 按协作模式划分 协同编辑系统中成员之间存在两种协作模式： - 同步( 实时) 协作模式 在同步协作模式下，协作成员同时对同一个文档对象进行编辑，每个成员 对文档的修改操作都实时地广播给组内其他成员，并使其他成员能够及时看到 修改后的结果。同步协作模式又分为松散耦合模式和紧耦合模式。在松耦合模 式下，各个成员以独立工作为主，然而在写作过程中，他们还共享某些信息资 源；而在紧耦合模式下，所有参与协作的作者共享相同的视图、资源、光标和 文件。 异步( 非实时) 协作模式 在异步协作模式下，成员根据任务的划分独自地写作文档。操作的结果不 能实时地被彼此观察到。当某个作者完成相应的写作任务时，将文档传送给服 务器或其他成员，下一个作者在前面写作的基础上开始自己的写作任务。 在实际的应用中，可能既包含同步协作模式又包含异步协作模式，有研究 者认为，协同编著是以异步协作为主、同步协作为辅的过程，相应地，协同编 著系统应以支持异步协作为主，同步协作为辅 7 。 那么按照协作模式的不同，可以将协同编辑系统划分为三种不同的类型： 一同步协同编辑器 电子科技大学硕士学位论文 典型代表如g r o v e 8 ，d i s t e d i t 9 ，r e d u c e 1 0 等。 _ 异步协同编辑器 典型例子包括通过e m a i l 进行协作( 如l o t u sn o t e s ) 、文档批注系统( 如 m i c r o s o f tw o r d ) 和版本控制系统( 如c v s 、c l e a r c a s e ) 等。 同时支持两种方式的编辑器 如s e p i a 超文本编著系统、r e c i p e 协作编程原型系统 1 1 等。 2 2 2 按编辑对象划分 协同编辑根据编辑对象的不同，分为协同文本编辑、协同图形编辑和协同 图像编辑等。协同文本编辑的操作对象是文本，比如可以用于协作对程序进行 修改，也可以用在会议系统中作文字讨论白板，一个创作小组也可以应用协同 文本编辑器来促进头脑风暴式创新方法的应用。协同图形和图像编辑系统也比 较常见，如会议系统中的共享白板，协同c a d 系统等。 2 3 协同编辑系统的体系结构 通常协同文本编辑器采用三种方式管理共享数据：集中式体系结构、全复 制体系结构和混合体系结构。这三类体系结构下的协同文本编辑器在设计思想， 应用场合，传输机制上都有着很多不同。 2 3 1 集中式体系结构 集中式体系结构将文档数据存放在一个中央服务器。客户端通过网络与此 服务器连接，形成星型拓扑结构。客户端向中央服务器传送用户交互事件，由 服务器应用程序完成计算功能后将共享数据发送给各个客户端，这样每个客户 本地的共享数据显示得到更新。 集中式体系结构下只有共享文档的一个副本，因此并发控制机制比较简单， 易于实现存取管理和保证数据的一致性。 2 3 2 全复制体系结构 全复制体系结构与集中式结构不同，每个参与站点分别保存共享文档的一 个副本，每个站点都可以接受用户操作，操作立即执行，并将执行了的操作广 播给其他用户，使其他用户的数据也得到更新。 第二章协同编辑技术综述 由于共享文档具有多个不同的副本，因此需要采用某种并发控制机制来保 证各个副本的一致性，使其最终收敛到同一个结果文档。在这种结构下，并发 控制起着最为关键的作用，是必须解决的首要问题。 2 3 3 混合式体系结构 混合式体系结构是上述两种体系结构的结合，共享文档采用全复制式方式 管理，而其他的信息采用集中方式管理。 2 3 4 三种体系结构的比较 在集中式体系结构中，因为只有一个用于更新共享对象的应用程序副本， 所有的应用和数据都存放在服务器上，一致性维护比较简单，易于实现，并且 可以用来改造遗留程序使其支持协同工作；同时，因为服务器能够实时地将某 个作者对文档的修改反映到所有协作参与者，因此可以真正地实现群件系统中 的“你见即我见”。但是，由于所有数据都要交付到服务器，由服务器处理后再 将结果返回给每个客户端，在高速网络环境中性能也许可以满足要求，但是在 i n t e r n e t 这种时延不确定的网络中，则会暴露出操作响应速度慢，性能不稳定 等问题。 采用全复制体系结构可以克服集中式结构的缺点，由于操作在本地文档副 本上立即执行，然后再传播到远程站点执行，由于本地操作立即反映到操作界 面上，因此具有响应速度快的特点，但是其并发控制机制比较复杂。如果解决 了并发控制问题，则该方法具有非常好的性能。 混合式试图融合上述两种方式的优点，简化共享文档之外的其他信息的管 理。 具体采用哪种结构需要视需求而定，为了实现真正的自由无限制的交互， 目前大多数实时协同编辑系统倾向于采用全复制式体系结构或者混合式体系结 构。 2 4 实时协同编辑系统的特性 一般认为，协同编辑系统应具有以下特性 2 ： ( 1 ) 协作感知：协同编辑器应该提供足够的上下文信息，使得用户可以 感知到处于同一个会话中的其他组成员的存在，并且应该提供工具辅助成员之 电子科技大学硕士学位论文 间共享视图和想法，从而促进交流和避免冲突。 ( 2 ) 容错和快速响应：在计算机出错或者有人加入和退出会话时群组会 话应该仍然可以平滑地进行。而且对于操作应该提供交互式的响应时间。 ( 3 ) 并发控制：并发控制需要保证进行并行编辑时数据的一致性，并且 应该减小网络延迟对用户觉察得到的响应时间的影响，不会给用户带来不便。 ( 4 ) 多用户u n d o ：允许用户单独取消他自己的操作。 ( 5 ) 可以作为单用户编辑器使用：当用户单独工作或者异步工作时不用 切换到其他编辑器。 ( 6 ) 丰富的文档结构：提供合适的文档结构来辅助群组之间的交流。 2 5 一致性维护算法 实时协同编辑系统大多采用全复制式体系结构，以隐藏通信延迟的影响， 达到快速响应的目的，但是全复制结构也会导致拷贝不一致的问题，因此需要 采用合适的一致性维护( 或者并发控制) 算法来维护拷贝的一致性。 并发控制是分布式系统、多进程多线程系统中普遍遇到的一个问题。它的 主要目标是保证在并发访问共享资源的情况下能够得到所期望的结果。对于传 统应用( 如分布式o s 、分布式数据库