（计算机软件与理论专业论文）基于jxta的协作文本编辑系统的设计与实现.pdf

摘要 摘要 随着计算机和网络技术的发展，使得人们通过网络来协作完成同一件工作成 为可能。计算机支持的协同工作( c o m p u t e rs u p p o r t e dc o o p e r a t i o nw o r k ：c s c w ) 研 究领域正是在这样的背景下产生的。协作文本编辑是c s c w 中的一种重要应用， 它使得人们能够同时编辑同一篇文档。 目前，协作文本编辑系统主要是基于i p 组播通信或客户服务器模式的。实际 上，i p 组播技术并没有在互联网上得到广泛部署应用；而客户服务器模式则存在 网络带宽瓶颈问题，最终限制了客户端的数量。随着硬件技术的发展，人们迫切 希望能够有效地利用网络边缘计算资源如计算能力、存储空间等。而采用p 2 p 架 构则可以有效地利用这些闲置的计算能力或存储空间。因此，p 2 p 架构适合作为群 组协作软件系统的架构。 本文在p 2 p 计算平台j x t a 上分析和设计了一个协作文本编辑系统模型。本 文首先分析比较了三种系统体系结构，指出了各种体系结构的优势和劣势；然后 分析比较了几种并发控制算法，指出了它们的不同特性和不同的应用场合；接着 分析了p 2 p 计算平台j x t a 中的核心概念与核心协议等；最后，对协作文本编辑 系统的服务层和应用层分别进行了分析与设计。 关键词：协作编辑并发控制p 2 pj x t a a b s t r a c t a b s t r a c t w i t ht h ed e v e l o p m e n to fc o m p u t e ra n dn e t w o r kt e c h n o l o g y ，i ti s b e c o m i n g p o s s i b l et h a tag r o u po fp e o p l ew i l lc o o p e r a t et oc o m p l e t eo n ew o r kt h r o u g hn e t w o r k c s c w ，n a m e l yc o m p m o rs u p p o r t e dc o o p e r a t i o nw o r k ，e m e r g e st om e e tt h i sk i n do f n e e d c o o p e r a t i v et e x t e d i t i n gs y s t e mi so n eo ff o c u s e si nc s c wr e s e a r c hf i e l d ，a l l o w s ag r o u po fp e o p l et oe d i tat e x tc o n c u r r e n t l y n o w , m o s tc o o p e r a t i v et e x t - e d i t i n gs y s t e m ss e n dm e s s a g e sa n dc o m m u n i c a t ew i t h e a c ho t h e rb yi p m u l t i c a s to rc l i e n t s e w e rm o d e l i nf a c t i p m u l t i c a s ti ss t i l ln o t w i d e l ye m p l o y e do nn e t w o r kd u et oi t si n t r i n s i cl i m i t a t i o n ，w h i l ec l i e n t s e r v e rm o d e l m a ye a s i l ys u b j e c tt on e t w o r kb a n d w i d t h ，a n df i n a l l yl i m i t st h en u m b e ro fc l i e n t s w i t h t h ed e v e l o p m e n to fh a r d w a r et e c h n o l o g y ，p e r s o n a lc o m p n t e r sh a v eb e c o m em o r e p o r w e r f u lt h a nb e f o r e ，i n c l u d i n gm o r ep o r w e r f u lp r o c e s s i n ga b i l i t ya n dl a r g e rs t o r a g e s op e o p l ee x p e c tt ot a k e a d v a n t a g eo ft h o s ec o m p u t i n gr e s o u r c e b e c a u s ep 2 p t e c h n o l o g yc a nm a k ef u l lu s eo fc o m p n t i n gr e s o u r c e ss u p p l i e db yc o m p u t e r sa tt h e e d g eo f t h en e t w o r k ，i ti ss u i t a b l ef o rt h eg r o u pc o o p e r a t i o ns o f t w a r es y s t e m t h i sp a p e ra n a l y z e sa n dd e s i g n sac o o p e r a t i v et e x t - e d i t i n gs y s t e mm o d e l f i r s t l y ， t h r e ek i n d so fs y s t e ma r c h i t e c t u r e sa r e c o m p a r e d ，f o re a c ho n ew ep o i n to u ti t s a d v a n t a g ea n dd i s a d v a n t a g e s e c o n d l y ， s e v e r a lc o n c u r r e n c yc o n t r o l a l g o r i t h m sa r e s t u d i e da n dt a k e ni n t oa c c o u n tt h e i rc h a r a c t e r i s t i c sa n dd i f f e r r e n tu s i n gs i t u a t i o n s n l e l l j x t ap l a t f o r mi sd i s c u s s e df u l l y ，i n c l u d i n gc o r ec o n c e p t i o n , p r o t o c o la n da r c h i t e c t u r e a tl a s t ，t h es y s t e m ss e r v i c ea n d a p p l i c a t i o nl a y e ra r es e p a r a t e l ya n a l y z e da n dd e s i g n e d k e y w o r d ： c o o p e r a t i v ee d i t i n gc o n c u r r e n c yc o n t r o lp 2 pj x t a 学位论文创新性声明 秉承学校严谨的学风和优良的科学道德，本人声明所呈交的论文是我个人在 导师指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加以标 注和致谢中所罗列的内容以外，论文中不包含其他人已经发表或撰写过的研究成 果；也不包含为获得西安电子科技大学或其它教育机构的学位或证书而使用过的 材料。与我一同工作的同志对本研究所做的任何贡献均己在论文中做了明确的说 明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切的法律责任。 本人签名：鹰翻雌 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究 生在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。本人保证毕 业离校后，发表论文或使用论文工作成果时署名单位仍然为西安电子科技大学。 学校有权保留送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全 部或部分内容，可以允许采用影印、缩印或其它复制手段保存论文。( 保密的论文 在解密后遵守此规定) 本学位论文属于保密，在年解密后适用本授权书。 本人签名：雄日期互q 导师签名：幽7 9 1日期j 刚矿0 7 第一章绪论 1 1 1p 2 p 技术及应用模型 第一章绪论 1 1 研究背景 1 、p 2 p 概述 p 2 p ( p e e r - t o p e e r ) 意味着对等互联或点对点技术【1 1 。事实上p 2 p 技术早在互联网 诞生时就有了。早期互联网上是没有服务器和客户机之分的，整个互联网就是一 个p 2 p 结构的大网络。后来随着互联网的不断发展，人们把一些资源存放到功能 比较强大的服务器中，其他的机器通过访问服务器获得信息和资源，这就是客户 机。以后一种基于c s 结构的网络通讯就形成了。随着硬件水平的发展，现在的 p c 无论是性能还是功能已经远远超越了原先对p c 的定义。许多p c 可以提供大容 量的存储能力和高速的计算能力。人们迫切希望能打破s e r v e r 的垄断，p 2 p 技术 正是基于这个目标而诞生的。p 2 p 有不同的定义，下面给出其中一种定义。 p 2 p 是一种分布式网络，网络的参与者共享他们所拥有的一部分硬件资源，包 括处理能力，存储能力，网络连接，打印机等，这些共享资源需要通过网络提供 服务，能被其它对等节点( p e e r ) 直接访问而无需经过中间实体。在此网络中的参与 者既是资源( 服务和内容) 提供者( s e r v e r ) ，又是资源( 服务和内容) 获取者( c l i e n t ) 【2 】 2 、应用模型 目前主要的应用模型1 3 , 4 有：基于互联网的文件存储系统，文件和内容共享， 即时通讯，协同工作，搜索引擎，在线游戏，网络操作系统，p 2 p 开发平台的研究 和p 2 p 安全框架的构建等。其中，文件共享的p 2 p 网络主要有：n a p s t e r t 5 1 ，g n u t e l l a 6 1 ， e d o n k e y ，e m u l e ，b i t o r r e n t 等；挖掘p 2 p 对等计算能力和存储共享能力，例如s e t i t o m e ，a v a k i ，p o p u l a rp o w e r 等；基于p 2 p 方式的协同处理与服务共享平台，例如 j x t a ，m a g i ，g r o o v e ，n e tm ys e r v i c e 等；即时通讯交流，包括i c q ，o i c q ，y a h o om e s s e n g e r 等；安全的p 2 p 通讯与信息共享，例如s k y p e ，c r o w d s ，o n i o nr o u t i n g 等。 1 1 2 协作编辑 自从2 0 世纪8 0 年代计算机支持的协同工作【7 l ( c s c w ：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 ew o r k ) 这- - 概念正式提出以来，c s c w 受到了来自各个领域的研究人员 广泛的关注，发展到今天已经具有相当的规模和影响力，大量的研究成果开始运 用到实际应用中。可以说现在c s c w 这一理念己经是无处不在，它的研究、发展 和应用正在影响和改变人们的工作和生活方式。 2基于j x t a 的协作文本编辑系统的设计与实现 新技术的出现加速了c s c w 发展，互联网社会化也成为一种新的趋势。近年来， 随着大量新兴技术( 如网格技术，w e b 服务技术，p 2 p 技术，语义与知识处理技术、 x m l 等) 的出现，c s c w 的研究领域得到进一步的扩展和充实。i n t e m 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 研究现状 w r i t e l y ( h t t p ：w w w w r i t e l y c o m ) 是一款网上文档处理软件，允许多人协作通过互 联网编辑同一份文档，是一个多样产品的综合体，在线文档编辑器的外观、文档 协作处理、发布在线页面、发布到b l o g g e r 。w r i t e l y 多人共同编写文档的能力很好 的。文档存在网上，可以共同编写。任何时候都可以。而且，系统会在后台自动 保存。而且w r i t e l y 提供的允许多人共同编撰文档的模式还非常适合多人维护的 网站或者b l o g 程序。实际上等于是提供了一个在线的存储文档，文档的创建者和 第一章绪论 协同创作者无论在何处都可以在线查看和修改，这个对于多人b l o g 的创作是一个 十分棒的选择。 s y n c w r i t e 是基于w o r d 的一款多人实时协同编辑文档的软件。主要功能：在线 提供多人实时协同处理w o r d 文档( c o l l a b o r a t i v ew r i t i n ge d i t i n g ) ；自动解决协同编 辑文档时的冲突；高实时性、即改即见，延迟不超过3 s ；高安全性，2 5 6 位加密； 自动保存文档机制，防止数据丢失；享受安全、实时的v o l p 和i m 交流。 目前，大多数的协作文本编辑软件都是基于传统的c s 模式的，这类应用模型 有着一个明显的缺点就是：随着客户数目的增多，服务端所需要占用的资源也随 之增加，最终制约了用户数目的增长。 1 3 工作内容和目标 本文尝试基于p 2 p 技术设计一个协作文本编辑系统。在系统的分析和设计过程 中，采用了p 2 p 计算平台j x t a 作为系统的设计基础。具体工作内容如下： 1 、详细分析了p 2 p 计算平台j x t a 中的核心概念与核心协议，研究了在j x t a 网络中，不同类型的资源如对等体、对等组、管道等是如何发布到网络中的以及 对等体是如何发现这些资源的。 2 、分析研究了协作文本编辑系统的三种体系结构：集中式体系结构、全复制 式体系结构以及混合式体系结构，指出了各种体系结构的优势和劣势。本文选择 混合式体系结构来作为本文设计的协作文本编辑系统的体系结构。 3 、分析研究了并发控制中常用的几种并发控制算法，指出了它们的不同特性 和不同的应用场合。本文选择基于时间戳的可逆操作法来作为本文设计的协作文 本编辑系统的并发控制算法。 4 、基于以上的工作，设计了一个协作文本编辑系统模型，系统模型总共有三 个层次：j x t a 平台层，系统服务层以及系统应用层。在系统服务层的设计过程中， 采用了模块化的设计思想。系统服务层中的一个服务就代表了一个模块，每个服 务负责提供特定的功能并以a p i 的形式来表示例如数据传输服务将为其他服务提 供透明的消息传输服务等。通过系统服务层中服务之间的相互调用合作，来为系 统应用层提供所需的功能。在系统应用层的设计过程中，根据面向对象的设计原 则，分析了系统模型中存在的对象及对象之间的关联关系；同时使用了统一建模 语言u m l ，分析了系统中的用例，指出了每个用例涉及到的系统对象及每个用例 的序列图。 本文的工作目标是为基于j x t a 的协作编辑系统提供一个比较通用的设计方 案，该系统不应只局限于文本媒体类型的编辑，虽然本文是针对文本媒体类型来 阐述的，但通过少量的代码修改，也可以适应于其他媒体类型如图形的编辑。 4 基于j x t a 的协作文本编辑系统的设计与实现 1 4 论文结构 本文的内容共分为六章。本章主要介绍论文的研究背景、研究现状、工作内容 和目标。论文其他章节的安排如下： 第二章介绍了c s c w 和协作文本编辑系统的概念，分析比较了三种不同的系 统体系结构，同时分析比较了并发控制中常用的几种并发控制算法。 第三章深入分析研究了p 2 p 计算平台j x t a 的层次结构、核心概念、核心协议 以及资源发现机制等。 第四章详细分析了系统服务层中各种服务的功能需求，并针对不同的服务给 出了相应的设计方案。 第五章首先分析了系统模型中的对象及对象之间的关系，描述了系统的活动 流程。其次分析了系统模型中存在的各种用例，并针对不同的用例给出了相应的 设计。最后设计了系统用户界面及各种界面之间的切换流程。 第六章总结全文，同时指出了需要进一步研究的方向。 第二章协作文本编辑系统 第二章协作文本编辑系统 2 1 计算机支持协同工作c s c w 在介绍协作文本编辑系统前，我们介绍一下计算机支持协同工作( c o m p u t e r s u p p o r t e dc o o p e 盯i o nw o r k ：c s c w ) 的概念。计算机支持协同工作的定义 是地域分散的一个群体借助计算机及网络技术，共同协调与协作来完成一项任务。 它包括协同工作系统的建设、群体工作方式研究和支持群体工作的相关技术研究、 应用系统的开发等部分。通过建立协同工作的环境，改善人们进行信息交流的方 式，消除或减少人们在时间和空间上的相互分隔的障碍，节省工作人员的时间和 精力，提高群体工作质量和效率。c s c w 体现并符合信息时代人们工作的群体性、 交互性、分布性和协同性特性，因此日益受到人们的重视。 2 1 1c s c w 三要素 c s c w 的目的就是在计算机环境下提供对人们群体工作的支持，因此说，通信、 合作、协调是c s c w 的三要烈9 j 。 - 通信 通信是c s c w 的基础，自然的组通信发生在地理上是分布的用户之间( 本地通信 可以认为可是分布系统的特例) ，因此网络通信是至关重要的，并且在合作环境中 处理多媒体文件传输和数据控制是很复杂的。而基于计算机的或者以计算机为媒 体的通信，并没有完全和其他的通信形式相结合。异步的基于文本的电子邮件和 公告板与同步的电话和面对面的交谈是不同的：人们不能在任意的两个电话号码 之间传送文件。把计算机处理技术和通信技术结合起来可以帮助解决这个问题。 _ 合作 合作是c s c w 的形式，与通信相似，合作是小组活动的重要内容。在群体活动 中，任意一项活动都必须是多人合作完成。有效的合作要求人们必须共享信息。 但是当前的信息系统尤其是数据库系统在很多情况下把人们互相隔离开。比如， 当两个设计人员使用同一个c a d 数据库进行操作是，他们不可能同时修改同一个 设计物体的不同部分并且知道他的合作者所做的修改；他们必须通过互相检查才 能知道对方所做的工作。许多任务都需要良好的共享环境，可以在适当的时候友 好的通知群组的活动信息以及各个用户的活动。 _ 协调 协调是c s c w 的关键。如果一个组的活动是协调的，那么它的通信和合作将 会大大得到加强。一个不能很好的进行协调的工作小组，它的成员之间势必会经 6基于j x t a 的协作文本编辑系统的设计与实现 常发生冲突和重复劳动。当几个部分共同组成一个任务时，协调本身被看作是一 个必不可少的活动。当前的数据库应用提供了对共享对象的访问，然而大多数软 件工具只提供对单用户的支持，对支持小组的协调这一重要功能所做的却很少。 2 。1 2c s c w 核心功能 c s c w 的核心功能有以下四个方面： 1 、工作流管理系统。工作流是指多人参与的工作事务中所使用的一系列步骤，这 些步骤可以是顺序的或并行的【1 0 1 。工作流是c s c w 软件应用的重点和难点，对于 c s c w 软件有着至关重要的作用。 2 、即时通讯系统。即时通讯包括了文字、语音、视频三种即时通讯方式，因为其 可以一定程度取代传统会议，也时也被称为多媒体会议系统。因为其能够处理音 频、视频、协作数据等大量信息，提高了计算机的协作工作能力，是快捷高效、 经济方便的协作工具。国外的g r o o v e 是市场推广比较成功的即时通讯类协作软件， 国内的北京点击和腾讯相关产品，也属于以即时通讯为核心的协作软件。 3 、协作编著和协作设计。这类应用为不同时间不同地点的用户，提供了协作工作 方式完成文档编辑和产品设计的功能。美国m i c h i n g a n 大学的d i s t e d i t 就是典型的协 作编著系统，复旦大学研发的协达软件，也提供了丰富的协作编辑功能。 4 、协作出版系统。这是一种基于w e b 的信息发布与集成系统，在实践工作中常常 被直接称为“信息发布与集成系统”，新闻、公告等是常见的协作出版系统。优秀 的协作出版系统，还能够动态更新内容。 以上c s c w 的四大核心功能，也是目前c s c w 协作软件的主要功能。 2 2 1 系统概述 2 2 协作文本编辑系统 协作编辑系统1 本质上是一个分布式软件系统，它帮助位于不同地理位置的工 作组成员通过网络连接来共同完成编辑同一个文档如一本书、工程设计方案等1 1 2 1 。 协作编辑系统中各个用户之间存在两种协作模式，同步协作模式和异步协作模式。 在同步协作模式下，协作编辑者并发地对同一文档对象或本地文档副本进行编 辑操作，并且将文档的编辑操作实时地传递给组内其他编辑者，当其他编辑者接 收到这个编辑操作时，将在本地文档副本上执行这个操作，这样就使其他编辑者 也能够及时看到修改后的结果。 在异步协作模式下，组内的成员完成不同文档部分的编辑工作。当某个编辑者 完成所负责的编辑工作时，他将文档传递下一个编辑者。下一个编辑者将在其基 第二章协作文本编辑系统 7 础上编辑他所负责的编辑工作。 如果协作编辑系统允许多个用户同时对共享文档进行读、写操作，则称为多操 作流协作编辑系统。否则，称为单操作流协作编辑系统。单操作流协作编辑系统， 用户必须获得操作权后，才能对共享文档进行操作。多操作流协作编辑系统则不 然，用户随时可以操作共享文档。 协作文本编辑系统是协作编辑系统中的一种，仅允许对文本进行编辑，比如可 以用于协作对程序进行修改，也可以用在会议系统中作文字讨论白板。 2 2 2 体系结构 1 、集中式体系结构 在集中式体系结构的网络连接中，有一个固定的中央高性能服务器，所有的客 户端都连接到这个中央服务器上，形成星形的网络拓扑结构如图2 1 所示，即服务 器客户端模式。中央服务器负责共享文档的存贮和访问管理，客户端只负责实现 共享文档的操作界面，通过网络访问服务器上的共享文档。共享文档只在服务器 上有完整的备份，在客户端结点上没有完整备扮。 集中式体系结构在数据管理方面有优势，它简化了访问管理可以保持数据的高 度一致性，同时安全性也比较有保障，适合于异步协作系统。同时，因为服务器 能够实时地将某个编辑者对文档的修改反映到所有协作编辑者处，因此可以真正 地实现群件系统中的同步。但是，由于共享文档只存放在服务器上并且客户端产 生的所有操作数据都要提交到服务器，由服务器处理后再将结果返回给每个客户 端，因此所有的数据和结果都需要在网络上传输，在高速网络环境中性能也许可 以满足要求，但是在i n t e m e t 这种时延不确定的网络中，则会暴露出操作响应速度 慢，实时性不能得到保证，性能不稳定等问题。 图2 1 集中式体系结构 2 、全复制式体系结构 在全复制式体系结构中，系统中可以没有中央服务器结点，各编辑结点彼此交 基于j x t a 的协作文本编辑系统的设计与实现 流操作信息，按照某种策略，使各结点上的共享文档拷贝保持实时数据的一致。 全复制式体系结构与集中式结构不同的地方在于当多个用户同步地对一个文档编 辑时，每个用户站点分别保存该文档的一个副本，而且这些文档副本保持实时数 据的一致，如图2 2 所示。每个站点都可以接受其他用户的编辑操作，并在本机的 文档副本上执行该编辑操作，从而保证了文档副本实时数据的一致。 全复制式体系结构的优点是响应速度快，用户对文本的编辑立即在本地执行并 更新显示，具有较好的灵活性、可靠性以及可扩展性。但是由于需要保持每个参 与者文本副本的同步状态，因此实现比较复杂，必须选择合适的并发控制算法来 实现并发控制，以维护本地用户的文本副本数据的一致性。在实时协作文本编辑 中，由于网络带宽和传输速率的限制，为了提高系统的实时性，特别是保证本地 用户尽量快的响应速度，一般是把共享编辑文档复制到本地，即全复制式体系结 构。 u s 图2 2 全复制式体系结构 3 、混合式体系结构 集中式体系结构和分布式体系结构分别具有不同的优点和缺点，单纯地采 用集中式或全复制式往往不能很好的符合实际应用的需要。混合式体系结构是 介于集中式和全复制式两种体系结构之间的一种结构如图2 3 所示。混合模式 具有集中式和全复制式的优点。参与协作的各个用户在本地维护共享文档的一 个副本，能够在本地完成的各种处理将在本地被立即执行，只有那些可能导致 文本副本数据不一致的操作，才提交给服务器进行一致性的调度处理。因此， 降低了全复制式体系结构文本副本一致性控制的复杂度。虽然这种结构并没有 完全避免集中式结构的缺点，但它减少了用户与服务器之间的交互，降低了对 服务器的依赖程度，同时减轻了服务器的负担，提高了服务器的响应速度。 第二章协作文本编辑系统 9 r 3 图2 3 混合式体系结构 4 、三种体系结构的比较 在集中式体系结构中，因为所有数据都统一在服务器上管理，只有一份拷 贝，一致性维护比较简单，易于实现；同时，因为服务器能够实时地将某个作 者对文档的修改反映到所有协作参与者，因此可以真正地实现群件系统中的 “你见即我见 。但是，由于所有数据都要提交到服务器，由服务器处理响应 后再复制到各个客户端，会造成系统响应速度慢。而且集中式系统过分依赖服 务器，服务器负责所有客户的连接和通信，容易引起单点失败问题，造成整个 系统崩溃。 采用全复制式体系结构可以克服集中式结构的缺点，由于操作在本地文档 副本上立即执行并更新用户界面，因此具有较快的响应速度，然后再传播到远 程用户端执行。但是要实现并发控制机制比较复杂。如果解决了并发控制问题， 则该方法具有非常好的性能。 混合式体系结构试图结合上述两种方式的优点。 具体采用哪种结构需要根据需求来选择合适的体系结构，目前大多数实时 协作编辑系统倾向于采用全复制式体系结构或者混合式体系结构。在分析了这 三种不同的体系结构之后，本文选择了混合式体系结构来作为协作文本编辑系 统的体系结构。 2 2 3 并发控制算法 并发控n t l 3 , 1 7 】是实现c s c w 系统的关键，并发控制算法的有效性对c s c w 系统 起着非常重要的作用，它直接影响着c s c w 系统的可用性和效率。在分析研究了各 种并发控制算法后，为了平衡并发控制算法的复杂性和实用性，本文设计的并发 控制机制是基于时间戳的可逆操作法的乐观机制。 1 、并发控制的主要功能需求 l o 基于j x t a 的协作文本编辑系统的设计与实现 _ 共享数据的一致性维护【1 4 , 1 5 1 及冲突解决：这是并发控制的最基本要求，只有保 证共享数据的一致性及解决用户操作冲突，才能使协作正常进行。 一 用户操作意图的一致性【1 6 】维护：它使得用户操作的执行结果尽可能地与用户发 起操作时的意图相一致。 接下来，我们将选择c s c w 中常用的几种并发控制算法进行介绍，指出它们彼此的 适用场合和优缺点。 2 、传统的并发控制算法 - 加锁法 加锁法是保证数据一致性的常用手段，它提供对共享数据对象的加锁( 1 0 c k ) 齐 1 解锁( u n l o c k ) ，用于控制用户的并发操作。它要求用户对数据对象操作之前先申请 该操作对象的锁，系统有一个调度机构保证在某一段时间内这个数据对象最多只 有一个访问者，在这个期间内其它的申请者要么等待要么放弃申请【2 3 1 。加锁机制 可分为悲观锁、半乐观锁和乐观锁【7 1 。乐观锁是以用户对共享对象的操作很少发生 冲突，申请锁时一般都会成功为前提。在申请加锁后，申请者立即获得一个试验 锁( t e n t a t i v el o c k ) ，利用试验锁来操作对象。如果加锁申请获得批准，则试验锁被 确认，可以继续进行操作；如果加锁申请被否决，那么必须取消利用试验锁所做 的所有操作返回到最初状态。悲观锁在加锁申请未被许可前，不允许对相关对象 做任何操作，用户只能等待。半乐观锁是用来改善乐观锁，半乐观锁的特点是在 获得试验锁确认之前，不能再通过新的试验锁来继续进行其它操作，而是进行等 待。封锁法的优点是设计和实现比较简单，用户在得到所申请的锁后其操作意图 能得到很好的保证。 加锁法的几个缺点【l 引。首先，系统的响应时间降低，申请和释放锁的开销会影 响用户动作的快速反馈。当申请的资源已经被锁定时，需要等待，容易引起死锁。 死锁是一种系统状态，在该状态下多个用户都在等待其他用户释放他们所占据的 资源。死锁的一个解决方案就是采用一种机制预防死锁，一个简单但不是很好的 克服死锁的方案就是让每个用户在对数据对象操作前，必须锁住它要访问的所有 象。该方案防止了死锁，但是却带来了不必要的资源访问权限。第二、对象数据 加锁的粒度不易掌握。例如，当用户移动光标到一行中间插入一个字符，应该锁 定什么是不清楚的，是整个段落或句子被锁定，还是仅仅锁定一个单词或字符。 锁的粒度大小划分并没有定式，需要根据实际应用进行调整。第三、锁请求与释 放的时机不易掌握。光标移动或敲击键盘时，是否应该发出锁请求呢。系统不应 该让用户来承担决策工作，但要把锁请求自动放在编辑命令中是很困难的。简言 之，系统阻碍了自然的文本编辑流程。 轮流法 在轮流法如令牌环中，系统中只有一个令牌环在各个用户处轮转，任一时刻只 第二章协作文本编辑系统 1 l 能有一个用户拥有令牌环，只有拥有令牌环的用户才可以进行相应的操作，其余 的用户将处于等待状态。拥有令牌环的用户在操作完成后，将释放令牌环，这样 其他的等待用户就可以获取令牌环并进行操作。由于在任何时刻只有一名活动用 户，在这样的系统中不会发生不一致问题，从而收敛性、因果性保持和意图保持 得到了保证，但是这是以不支持并发编辑作为代价的。所以，这种方法的适用范 围仅局限于单个活动用户就能满足系统需求的情况，对于那些以多用户并发活动 流为协作特性的应用环境来说，这种方法是不合适的。 _ 集中控制法 共享信息在所有的用户处均保留一份相同的拷贝。集中控制使用一个集中控制 进程，管理所有对共享数据的操作。每个用户的操作请求被送到集中控制进程， 集中控制进程按照一定的规则排序后，将请求广播给所有用户按序执行，因为所 有操作在所有用户处按照相同的顺序执行，所以所用共享信息的拷贝保持完全一 致，确保了数据的一致性。这种方法的优点是实现简单，数据可以保持高度一致 性，缺点是集中控制进程削弱了系统的健壮性，可能成为系统的瓶颈，用户的申 请操作是从集中处理进程返回后才执行的，操作的传送也延长了系统的响应时间。 一可逆操作法 采用这种方法，操作可以立即执行，但保留与操作有关的信息，以便在必要时 取消( u n d o ) 操作【1 9 2 0 2 1 1 。许多乐观并发控制机制采用这一策略，这要求给系统中的 所有操作提供一个全局的时序。当有失序的操作时执行u n d o 失序操作并按正确的 顺序r e d o 这些操作。0 在可逆操作的并发控制算法中，如果存在一个单服务器，可以根据服务器的时 钟，来赋予每个操作一个时间戳。那么系统中每个操作都是严格有序的，不存在 差错，可以按照先来后到的顺序进行操作。但对于分布式系统中，各个用户之间 的局部时钟不同步，比较难以保证各个用户的操作时间戳是严格全局排序的。 可逆操作法还有一个问题：某个数据会从用户界面上突然消失( u n d o ) ，然后又 迅速在另一位置出现( r e d o ) ，这时用户不清楚是其他用户的操作结果，还是系统 的行为结果，干扰了用户正常地工作。此外，并不是所有的操作都是可以u n d o 的 【l 引，如果事件驱动的是外部世界的活动，那么是不可能u n d o 的。 3 、基于操作转换的并发控制算法 操作转换法【1 2 2 2 1 是e l l i s 等在g r o v e 系统中提出的一种并发控制方法，是一种 适用于实时协作系统并发控制机制。当一个用户产生一个操作时，操作在本地立 刻执行，以保证用户界面良好的响应速度；同时将此操作与状态向量一起广播出 去。状态向量表明编辑器最近接收到的从其它站点发来的操作序列，每个用户的 编辑器有它自己的状态向量；当一个用户接收到这个操作时，将收到的状态向量 与本地的状态向量相比较，如果二者相等，则操作按申请的执行，否则在执行前 1 2基于j x t a 的协作文本编辑系统的设计与实现 首先通过适当的变换算法对参数进行修正，得到一种新的执行形式，然后再执行 变形后的操作，以保证对象的一致性以及在任一用户处均能得到发出此操作的用 户所期望的结果。变换法被发现是一种有希望的方法，不仅适用于文档一致性维 护，还适用于支持用户发起的取消处理。这种方法的最大弱点是当用户操作的冲 突较多时，用户操作的意图难以保证。 用户对共享对象o 进行一系列指定的操作，如( o p l ，o p 2 ，o p 3 ，o p n ) ，为了维 护共享对象o 在每个站点副本的一致性，对于对象o 的每一个操作0 p ，在各个站点 都要执行。对于每个站点的动态行为可以抽象为五个方面： 操作产生：将对用户界面的操作转化为针对o 的方法调用o p ； 操作传播：将代表用户操作的o p 传送给系统中所有其他站点； 操作接收：接收来自其他站点传来的操作o p ； 操作处理：对接收到的操作进行并发控制等处理。 操作执行：对象o 执行所接收到的操作o p 。 上面介绍了目前c s c w 系统中常用的并发控制方法。s a u l g r e e n b e r g 等在文献 中将以上常见的并发控制方法概括为封锁法和串行化法两类机制。以上方法中， 加锁法属于封锁机制，轮流法可看成为特殊的封锁粒度很大的封锁法，其它的方 法均可归入串行化机制。 2 3 本章小结 本章首先介绍了c s c w 和协作文本编辑系统的概念，其次分析比较了三种不同 的系统体系结构，指出了各自的优缺点及其适用场合，在分析了这三种不同的体 系结构之后，本文选择了混合式体系结构来作为协作文本编辑系统的体系结构。 最后，介绍了并发控制的功能要求，研究了并发控制中常用的几种并发控制算法， 指出了每一种并发控制算法的特性和适用场合，为了平衡并发控制算法的复杂性 和实用性，本文设计的并发控制机制是基于时间戳的可逆操作法的乐观机制。 第三章p 2 p 计算平台j x t a 分析 第三章p 2 p 计算平台j x t a 分析 3 1j x t a 起源及设计目标 1 、j x t a 起源： j x t a 2 4 】是s u n 公司对等网络的标准，以它来促进和探究分布式计算的新方法。 j x t a 最早起源于2 0 0 0 年的夏天，其开发组织被取名为单词 j u x t a p o s e ( 并置) ”的简易 形式。在2 0 0 1 年2 月f h o r e i l l yn e t w o r k 组织的p 2 p 会议上，b i l lj o y ，s u n 的首席科学 家解释了选择这个名字的原因：意思是可以平行放置的两个邻近实体，而这正是 对等网络的全部意义。 当今p 2 p 应用己成为互联网上最广泛的应用之一，但是仍存在几个障碍p 2 p 技 术被广泛接收的因素。其中主要的障碍就是没有一个开发p 2 p 应用的标准，例如一 个处理即时消息的应用程序就对如何在其他p 2 p 领域进行操作完全不知。另外，虽 然在这些应用程序中许多通信是p 2 p 形式，但它们仍趋向于依赖大型的集中式服务 器来提供服务的关键要素。不同的协议、不同的体系结构、不同的实现机制准确 地描述了当前p 2 p 解决方案的特点。 j x t a 通过从所有的p 2 p 系统中分离出这些系统通用的需求，从而建立一整套泛 型的p 2 p 基础协议来清除这些障碍，为p 2 p 的网络应用发展提供一个统一的平台， 为此它定义了一系列独立于语言，平台和网络技术之外的一组公共协议。这组协 议使网络上任何连接着的计算设备以p 2 p 的方式进行通信和协作变为可能。j x t a 为每个对等体提供了一组标准组件，这些标准组件规范了对等体的几个基本行为： 相互发现、自组织成对等组、发布和搜索通告、相互通信以及相互监控等。 由于j x t a 平台为应用抽象出了一个虚拟的覆盖网并为每个对等体提供了一组 标准组件，所以使用j x t a 技术，可以提高网络应用程序的开发效率。j x t a 为应用 提供如下能力：穿越防火墙查找网络中的其他对等体；创建提供定制服务的对等 组；发布和查找资源通告；远程监控对等体的活动：与其他对等体进行安全通信。 j x t a 协议是专为特定的、分布式的、对等的网络计算而设计的。使用这些协 议，对等体可以相互协作来建立自我组织、自我管理的对等组，而不必关心他们 在网络中所处的位置，并且不需要集中的管理机构。标准化的j x t a 协议将致力于 实现p 2 p 计算这一诺言。 2 、设计目标瞄j ： 互操作性 j x t a 协议在物理网络之上构建了虚拟的覆盖网络，使得对等体能独立于他们 的真实的网络连接，直接进行协作和自我组织。也就是说，j x t a 技术允许互联的 1 4 基于j x t a 的协作文本编辑系统的设计与实现 对等体能方便地相互定位，通信。同时对等体之间可以无缝地提供服务，j x t a 并 不具体指定某一特定的、有意义的互操作性规则，而是提供一个可互操作的层次 结构，而具体有意义的操作规则由应用程序的开发者来定义。同时，j x t a 使用x m l 消息格式，有利于互操作性的实现。 平台无关性 j x t a 独立于开发语言( 例如c 和j a v a ) 、独立于系统平台( 例如w i n d o w s 和 u n i x ) 、独立于服务定义( 例如r m i 和w s d l ) 、独立于网络协议( 例如t c m p 和b l u e t o o t h ) 。j x t a 关注于机制而不是策略。 普遍性 j x t a 被设计可以用于所有有数字心脏的设备，不仅仅是p c 机，还可能是 任何设备。这包括传感器、消费电子产品、p d a 设备、网络路由器、桌面电脑、 服务器和存储设备等。 除此之外还有一些其他目标，例如加密、应用性、稳定性和性能等，这些目标 在最初设计j x t a 协议时，也被考虑到了。 3 2j x t a 的系统架构 j x t a 由三层【2 6 1 组成，如图3 1 所示。第一层是j x t a 核心层，它包含了服务所需 要的核心功能；第二层是服务层，它提供了访问j x t a 协议的接口；第三层是应用 层，它使用服务来访问j x t a 网络和j x t a 提供的功能。 ， 一一一一一一一一一一一竺竺：竺竺竺竺兰! l 图3 1j x t a 的层次结构 核心层：它处于j x t a _ 三层结构中的最底层，提供了所有对等网络计算都必须 的基本操作原语，它既包括了构建p 2 p 应用的关键机制所需的基本操作，还包 括对等体、对等组、发现、通信、监控和相关的安全原语。在理想的情况下， 该层由所有p 2 p 设备共享，使之具有协作工作的能力。 服务层：服务层扩展了核心层的功能，为很多p 2 p 应用程序所需的通用服务提 供了接口，在这层中提供了诸如索引、查找、存储系统以及认证之类的服务。 懒 。 饲 钟 摹岍 洲啉 啉 第三章p 2 p 计算平台j x t a 分析 1 5 这些服务对于p 2 p 网络不是必需的，但确是大多数p 2 p 网络应用所需的通用服 务。这些服务通常会作为组件包含在p 2 p 系统当中。除了j x t a 提供的服务外， 开发者也可以创建自己的服务，为特殊应用提供支持。 应用层：这一层包含了应用t a 服务开发出来的完整的p 2 p 应用程序，为用户 提供最终解决方案，如p 2 p i i p 时通信、资源共享等等。显然，服务层和应用层 之间的界限并不严格：一个客户的应用程序在另一客户看