（计算机应用技术专业论文）基于p2p的协同工作系统模型研究与应用.pdf

摘要 摘要 随着互联网和通讯技术的迅速发展，群体之间的远程交互协作变得日益重要， 人们希望能够借助于计算机和网络技术，彼此之间相互协调共同完成一项工作任务。 计算机支持的协同工作c s c w 正是适应人们这一需求而出现的一个重要研究领域， 目前正处于蓬勃发展之中。现代协同工作系统已经越来越复杂，除了需要支持多人 共同协作，还需要具有适应异构网络环境、跨平台等能力。 目前，大部分的协同工作系统都是基于c l i e n t s e r v e r 集中式模式。在这种模式 下，由于服务器负责转发协作消息并集中处理客户端的协同请求，因此，这种集中 式模式不可避免地存在单点失败问题，而且受到规模和经济因素的限制，系统升级 扩展代价高昂。而对等网络技术p 2 p 作为一种新兴的技术，具有负载均衡、健壮性、 自组织性等特点，不但能够充分利用计算机网络的边缘计算能力，而且其工作原理 很符合协同工作的本质特征，近些年来已经得到了快速的发展和应用，基于p 2 p 的 c s c w 研究也逐渐受到重视并逐步开展起来。 论文首先归纳给出了目前现有的各种协同工作系统模型，分析比较了它们各自 的优缺点及其适用场合；对j x t a 平台做了探究分析，介绍了j x t a 的概念、协议、 架构以及虚拟网络的构建原理等，给出了一些改进j x t a 资源搜索效率的方法。然 后在此基础上提出了一个基于j x t a 平台的p 2 p 协同工作系统模型，分层次对该模 型的主要设计思想进行了概述。与传统协同工作系统模型相比，该模型具有较好的 可扩展性、较快的响应速度、跨平台和适应异构网络的能力。基于这个模型部分实 现一个协同文本编辑器系统，并给出了该系统中组成员关系服务、会话关系管理、 组通信管理、文档模型和分布式用户操作控制、协同感知和u i 等关键模块的详细设 计和实现。同时，由于并发控制在分布式系统中的重要性和复杂性，论文对模型所采 用的基于d o m 的并发控制算法专门做了重点论述。最后总结了论文主要的研究工 作，分析了基于j x t a 的p 2 p 协同工作系统目前还存在的主要问题以及下一步的研 究方向。 关键词：p 2 p ；j x t a ；c s c w ；并发控制；协同文本编辑器 j 尔t 业大学t 学硕+ 学位论文 a b s t r a c t w i t ht h er a p i dd e v e l o p m e n to fi n t e m e ta n dc o m m u n i c a t i o nt e c h n o l o g y ，r e m o t e i n t e r a c t i o na n dc o l l a b o r a t i o nb e t w e e nw o r kg r o u p sb e c o m e sm o r ea n dm o r ei m p o r t a n t a c c o r d i n g l y ，m o r ea n dm o r ep e o p l ee x p e c tt h a tt a s kc a nb ec o m p l e t e db yd i f f e r e n tp e o p l e d i s t r i b u t e di nd i f f e r e n ta r e a sw i t hc o m p u t e ra n dn e t w o r k c s c w ，n a m e l yc o m p u t e r s u p p o r t e dc o o p e r a t i o nw o r k ，a p p e a r sj u s tf o rm e e t i n gt h i sn e e d ，a n dn o w a d a y sh a sb e e n a l li m p o r t a n tr e s e a r c hf i e l d m o d e mc o o p e r a t i v ew o r ks y s t e mh a sb e c o m ei n c r e a s i n g l y c o m p l e x i na d d i t i o nt os u p p o r t i n gm u l t i p e o p l er e a l t i m ec o l l a b o r a t i o n ，t h ec a p a b i l i t yo f a d a p t i n gh e t e r o g e n e o u sn e t w o r ke n v i r o n m e n ta n dc r o s s p l a t f o r mi sa l s oi n d i s p e n s a b l e a tp r e s e n t ，m o s tc o o p e r a t i v ew o r ks y s t e m sa r eb a s e do nc l i e n t s e r v e rm o d e lb y d i s p a t c h i n gc o l l a b o r a t i o nm e s s a g e sa n dp r o c e s s i n gr e q u e s t sb ys e r v e r s i n e v i t a b l y ，a s i n g l ep o i n to ff a i l u r e e x i s t si nt h i sc e n t r a l i z e dm o d e l ，a n di t sd e p l o y m e n ti sl i m i t e db y t h es c a l ea n de c o n o m i cf a c t o r s p 2 pn e t w o r k s ，a san e wt e c h n o l o g y ，w i t hl o a db a l a n c i n g ， r o b u s t ，s e l f - o r g a n i z a t i o no ft h ec h a r a c t e r i s t i c s ，w h i c hi se x a c t l yi nl i n ew i t ht h e c o l l a b o r a t i v ee s s e n t i a lc h a r a c t e r i s t i c ，h a sb e e nar a p i dd e v e l o p m e n ti nr e c e n ty e a r s f i r s t l y ，t h i sp a p e rc o m p a r e st r a d i t i o n a la n dc u r r e n tc o o p e r a t i v ew o r km o d e l sa n d p o i n t so u tt h e i rr e s p e c t i v es t r e n g t h sa n dw e a k n e s s e s ，a n du s i n gs i t u a t i o n s t h e n ，j x t a p l a t f o r mi sd i s c u s s e di nd e t a i l s ，i n c l u d i n gj x t ac 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 ea n d h o wt oc r e a t eav i r t u a ln e t w o r ka n di m p r o v ee f f i c i e n c yo fj x t an e t w o r k t h e n ，w eg i v ea p 2 pd i s t r i b u t e dc o o p e r a t i v ew o r km o d e lb a s e do nj x t ap l a t f o r ma n dd e s c r i p t i o n sa b o u t t h i sm o d e l sr e s p e c t i v el a y e r s ，c o m p a r e dt ot r a d i t i o n a lm o d e l ，i th a st h ea d v a n t a g eo f f l e x i b i l i t y ，r a p i dr e s p o n s i v ev e l o c i t ya n dc r o s s - p l a t f o r mi no r d e rt ov e r i f yt h i sm o d e l ，a c o o p e r a t i v ee d i t o rb a s e do nt h i sm o d e li si m p l e m e n t e dp a r t l ya n dw eg i v ei t sd e t a i l e d d e s i g na n di m p l e m e n t a t i o no fk e ym o d u l e s ，i n c l u d i n gg r o u pm e m b e r s h i p ，s e s s i o n r e l a t i o n s h i pm a n a g e m e n t ，g r o u pc o m m u n i c a t i n gm a n a g e m e n t ，c o o p e r a t i v es e n s e ，u ia n d s oo n a tt h es a l t l et i m e ，c o n s i d e r i n gt h ec o m p l e x i t yo fc o n c u r r e n c yc o n t r o li nd i s t r i b u t e d s y s t e m ，w ed oa ni n - d e p t hs t u d yo ft h ec o n c u r r e n c yc o n t r o la l g o r i t h mb a s e d o nd o mu s e d i nt h i sm o d e l a tl a s t ，m a k eas u m m a r yo ft h i sp a p e r sm a i nr e s e a r c hc o n t e n t ，p o i n to u t s o m ee x i s t e dp r o b l e m si nc u r r e n tm o d e la n dt h en e x ts t e po fr e s e a r c h k e y w o r d s ：p 2 p ；j x t a ；c s c w ：c o n c u r r e n c yc o n t r o l ；c o l l a b o r a t i v et e x te d i t o r i i 独创性声明 独创性! 声明 秉承学校严谨的学风与优良的科学道德，本人声明所呈交的论文是我个人在导 师的指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加以标注 和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果，不包含本人 或其他用途使用过的成果。与我一同工作的同志对本研究所做的任何贡献均己在论 文中作了明确的说明，并表示了谢意。 本学位论文成果是本人在广东工业大学读书期间在导师的指导下取得的，论文 成果归广东工业大学所有。 申请学位论文与资料若有不实之处，本人承担一切相关责任，特此声明。 指导教师签字： 论文作者签字： 日 。 v 年一_ 鸭 i=，雨 第一章绪论 第一章绪论 1 1 研究背景及研究意义 从1 9 9 9 年5 月n a p s t e r 公司成立开始，似乎就预见了未来网络、信息与通讯必 将产生一股新气象，这就是p 2 p 计算( p e e r t o p e e rc o m p u t i n g ，对等计算、点对点计 算) 。2 0 0 0 年8 月下旬在i n t e ld e v e l o p e r sf o r u mf a l l2 0 0 0 大会上，i n t e l 以非常谨慎 的态度向世界宣布，p 2 p 计算将颠覆现在所有的商业营运模式，为将来p c 计算开创 一个新的里程碑，随后推出的p e n t i u m 4 已经包含了n e tb u r s t 架构，以处理p 2 p 技术 需要。i n t e l 公司还发起成立了包括微软、s u n 和h p 等大公司在内的p 2 p 工作组， 以推动p 2 p 进一步发展，财富杂志更将p 2 p 列为影响i n t e m e t 未来的四项科技之一【l j 。 p 2 p 计算的核心是p 2 p 底层通信机制，围绕p 2 p 通信，尤其是两个不同局域网 间的p 2 p 通信，已经有许多的p 2 p 协议和开发包涌现。例如，s u n 公司以j a v a 写的 开发包j x t a ，微软在w i n d o w sx p 平台上有p 2 p 的1 3 版开发包，i n t e l 公布n e t 平台 上的p 2 p 应用开发工具包。在这些众多很有实力的厂商推动下，近几年p 2 p 应用更 是如火如荼，像b t 下载、p 2 p 流媒体软件、免费全球语音通信s k y p e 、个人社会化 网络s n s 等更是家喻户晓。其中，尤其是网络拍卖巨擘e b a y 推出的全球通用通信 软件s k y p e ，以普通有线电话的通信效果、超清晰音质、低回音、穿透防火墙等给用 户带来卓越的网络通话效果体验，更是将p 2 p 应用推向极致，目前p 2 p 文件共享产 生的流量可能是今天因特网最大的单项流量，如图卜1 所示，因此可以预见，随着 3 g 网络部署之后网络带宽的大幅提升和i p v 6 的逐步实施，p 2 p 应用更将如鱼得水获 得更快的发展，这将为解决目前众多基于集中式网络架构的协同工作系统本身固有 的技术难题和协同计算系统的更快发展带来新的契机。 广东l ：、j k 人学l 学顾i j 学位论文 ( a ) 黔冉 ；v 峭睨| 蝴卿雌 d 缈r 艟i 母i 移碟辆v 轳r o l 黼静j 协p _ lp 钳，群钳_ o 喘耕种”t ，壮讲i i , y _ 渤世协嘴h 。窜静峥辞呻甜萌斜dw 鼢缸# 蘑# ”舻q 螂竹t 撕十 s p - f 柏2 臻 ( b ) 图卜l2 0 0 5 年网络流量统计图 f i g 1 1n e t w o r k t r a f f i cs t a t i s t i c si n2 0 0 5 当前绝大多数协同工作系统是基本集中式架构( c l i e n t s e r v e r 或 b r o w s e r s e r v e r ) 。一方面，这种结构要求必须安装和维护相应的服务器并且预先配 置好的协同系统架构，这往往需要高昂的硬件和软件费用，很难适应实时的移动协 同需要f 2 1 ；另一方面，群体协同本质上是个体与个体、个体与群体、群体与群体之间 的交互，即很多行为的完成并不都一定要通“协同服务器”，集中式协同系统导致 了架构本身和应用需求之间的不匹配，协同对象之间没有自我组织和自我管理的能 力，p 2 p 网络以更自然和现实的方式来解决当前协同工作系统存在的问题。因此， 研究p 2 p 网络下协同的原理、机制及其可行性就显得很有必要了1 3 l 。 1 2 国内外研究现状 p 2 p 分布式协同工作系统可以解决协同架构和协同本质需求之间的不匹配，同 时也使系统的适应性、白组织性、自我管理功能得到加强 2 1 。目前国内还很少有基于 p 2 p 架构的协同工作系统研究。国外提出的基于p 2 p 的协同工作系统主要有c r o q u e t 和e up r o j e c tm o t i o n 。c r o q u e t 是一个开放、免费的基于p 2 p 的协同架构，它专注于 协同环境下的3 d 空问共享，使每个用户能够容易感知其它用户并清楚其当前的工作， 第一章绪论 它采用完全基于对象协同的机制和p 2 p 架构，使整个平台具有极大的设计和开发灵 活性，所有协同对象均是对等的，以直接的消息传递来完成本地或远程的同步协同 工作。中间不需要任何其它的步骤来解释和中继这些协同请求，只需要一个中心服 务器作为稳定的入网点来建立初始的系统连接，当整个系统动作起来后，中心服务 器即使出现故障离线，系统仍然能正常运行【4 】。e up r o j e c tm o t i o n 借助于l i m e ( 一个 分布式的p 2 p 通信中间件) 构建一个主要用于支持地理上分散的移动用户协同作业 1 5 ，6 1 o 目前这些系统还存在的主要问题和困难有： ( 1 ) 纯p 2 p 网络使用p 2 p 重叠网通信，而负责转发消息的对等体或汇聚对等体所 存储的路由信息由于对等体的频繁加入和退出，可能使消息转发出现不可预料的延 迟，这对实时性要求较高的同步协同会有一定的影响【7 j 。 ( 2 ) 在一般p 2 p 数据共享系统中，如果系统中某个对等体中存储有相应的数据， 而搜索算法“尽最大努力”( b e s t e f f o r ta p p r o a c h ) 返回结果为空，这是可以接受的。 然而在针对企业的特定应用中，对于实事上存在的关键文档资料必须要求随时可用， 这就可能要求架构对这种特殊需要提供支持。 ( 3 ) 协同场景中一般都有多个参与者，如何在协同时根据连接的动态变化生成统 一集中式虚拟视图，目前的系统大多采用基于文本的交互协作界面，随着网络带宽 的提高和用户需求的提高，如何在p 2 p 网络下用多媒体形式的协同界面给用户带来 更高的体验将面临挑战。 ( 4 ) 数据一致性问题，在诸如p 2 p 的所有分布式系统中，由于各种数据都是通过 在不同节点上冗余存储来实现其健壮特性的，这就引发了数据的一致性问题。这要 求系统本身在数据更新时自动复制新的数据替换旧版本，避免数据版本冲列引。 ( 5 ) 安全性问题，安全问题一直是伴随互联网发展的重要问题，比如应该防止他 人控制整个系统，增加恶意信息等，同时系统应能够保证系统中信息资源的正确性。 在p 2 p 系统中系统安全同样面临巨大的挑战，同时也有其自身的特点引发的新问题。 这是因为p 2 p 系统中需要在没有特定中心节点服务器的情况下提供身份认证、授权 以及数据信息的安全存储、数字签名、加密和安全传输等工具，同时p 2 p 系统还要 有能力抵抗过量存储负载、d o s 攻击等攻击行为1 2 j 。 j “东t 业大学工学硕士学位论文 1 3 主要研究内容及章节安排 1 3 1 主要研究内容 ( 1 ) 研究现有的p 2 p 网络，尤其是j x t a 网络下的通信机理、消息路由算法、资 源定位机制。尽量提高p 2 p 网络环境下资源的快速、准确定位，保证数据存储的趋 向一致性。 ( 2 ) 研究协同模型和协同并发控制机制，根据集中式网络环境下的协同模型和并 发控制，探究它们在新的p 2 p 网络环境中面临的问题，在此基础上寻找或改进新协 同并发控制机制，达到最大程度上提高系统的响应速度和减少协同冲突的发生。 ( 3 ) 研究如何构造一个有效的基于p 2 p 网络的协同工作系统模型并基于这个模 型部分实现一个协同文本编辑器系统，经过相关试验证明基于该模型的系统比传统 系统的优越性。 1 3 2 主要章节安排 论文共分为五章，各章内容如下： 第一章为绪论部分，主要介绍了本课题的产生背景以及研究内容。 第二章介绍c s c w 基本概念、工作模式、体系结构和基于p 2 p 网络的协同工 作系统模型；比较了两种体系结构各自的优缺点，指出了各自适用的场合。 第三章主要介绍c s c w 中的必须用到的并发控制策略，分析了当前传统的并 发控制算法、基于操作转换的并发控制算法，分析比较了它们各自的优缺点和适用 场合。 第四章简要介绍了p 2 p 技术和深入剖析了p 2 p 网络开发平台j x t a ，主要包括 j x t a 的概念、核心协议、架构以及虚拟网络的组建，并且提出了一些改进j x t a 资 源搜索机制的策略。 第五章描述了基于对等网络j x t a 平台上协同工作系统模型的主要设计思路， 基于这个模型部分实现了一个协同文本编辑器系统，详细论述了该系统中的组成员 关系管理，协同感知，并发控制等关键模块。 最后，对论文所完成的工作做了概括性总结，同时也对基于p 2 p 网络的协同工 作系统模型需要进一步完善和改进等方面做了展望。 4 第二章c s c w 关键技术 2 1c s c w 简介 第二章c s c w 关键技术 在介绍基于p 2 p 网络的协同工作系统模型之前，我们先需要了解计算机支持 协同工作( 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 ) 的概念。 它是指地域分散的一个群体借助计算机及其网络技术，共同协调与协作来完成一 项任务。它包括协同工作系统的建设、群体工作方式研究和支持群体工作的相关 技术研究、应用系统的开发等部分拉引。通过建立协同工作的环境，改善人们进行 信息交流的方式，消除或减少人们在时间和空间上的相互分隔的障碍，节省工作 人员的时间和精力，提高群体工作质量和效率，从而提高企业、机关、团体、乃 至整个社会的整体效益和人类的生活质量【20 1 。c s c w 体现并符合信息时代人们 工作的群体性、交互性、分布性和协同性特性，因此日益受到人们的重视。 2 2c s c w 的主要工作模式 人们合作的方式主要有同时同地、同时异地、异时同地和异时异地四种情况 【2 1 1 。因此，按照合作方式和协同者的地域分布可以从时间和空间上将c s c w 分 为四种不同的模式，即同步模式、分布式同步模式、异步模式和分布式异步模式， 如图2 1 所示。 图2 - 1c s c w 的分类 f i g 2 1c a t e g o r yo fc s c w j 东工业大学工学硕士学位论文 2 2 1 同步模式 此类系统主要用于支持像决策会议这种本地组之间面对面的实时协作，如各 种会议室系统。它们所要达到的一个主要目标就是“你见即我见”。这一点是通 过一个在与会者之间共享的c h a l kb o a r d 而实现的。在此过程中当多个用户同时 要访问同一个对象时，为保证数据的一致性而必须采取合适的并发控制策略，如 使用加锁、时间戳以及其各种变形等；当一个用户访问其他用户所生成的对象时， 应采取合适的访问控制策略，如基于一系列“权限矩阵”的方法等【2 引。另外为了 避免将每个人的活动所产生的所有数据都一点不差地进行传送所导致的性能和 使用上的问题，可以将系统中的数据按其被共享的程度而划分成私有、组间共享 以及公有等几种类型。 2 2 2 分布式同步模式 此种系统的典型代表有多媒体桌面会议系统，这类系统中的用户通常是分布 在不同的地理位置处。其中它提供有一个与会议室系统中c h a l kb o a r d 类似的 w h i t eb o a r d ( 电子白板) 1 8 , 1 9 】。在过去，由于用户的分散性，数据传送过程所使用 的一般是速率较低、质量较差的广域连接。另外为提高信息交流的质量，这类系 统一般都提供有视频和音频这类多媒体服务，这将导致待传送的数据量大大增 加，对q o s 的要求也将更高，高速网络的发展将能满足实现高质量的远程多媒 体桌面会议系统的要求，这在远程医疗实时诊断系统中有广阔应用前景。 2 2 3 异步模式 这类系统比较丰富，如b b s 、电子邮件、协同w w w 等等。目前的b b s 系 统实际上给用户提供的是一种文本信息的管理服务。这些文本信息被分成不同的 类别的讨论区。用户将信息发送到b b s 服务器，b b s 服务器再将这些信息以适 当的方式让有关的用户了解到这些信息的存在，并进而决定如何对这些信息进行 处理，如转发、回复等。电子邮件系统的功能从数据管理的角度来看则更为简单。 整个邮件系统所做的实际上是根据预定义的方式( 指定的接收者、转发路径等) 对邮件数据进行存储转发。当然这种系统有一个严重的不足是，目的主机收到邮 件之后它无法主动地将这一信息告诉有关的用户，而只能是由系统在某些时机 ( 如用户登录或根据某些定时机制) 去检查邮箱看是否有邮件到达。 6 第二章c s c w 关键技术 2 2 4 分布式异步模式 支持此种协同工作方式的系统有共享文件( s h a r e df i l e s ) 、t e a mr o o m 等系 统。这类系统由于用户的地理位置不具有分散性，同时用户对它们的访问也是异 步的，因此不需要对数据进行实时传递。它关注的重点更多的在于如何保证“长 事务”处理中数据的一致性与用户之间的互相感知，考虑共享文件的情形。需要 注意的是，这里的文件共享不同于传统的文件服务器中的文件其享。在此种系统 中，通常某，份文档是综合多个不同作者的劳动成果而成的。常用的办法就是每 个用户独立地( 异步、不同时) 完成文档的一部分，然后在各作者之间进行校阅、 批注、审定，最后定稿。因此系统所应解决的问题是如何方便作者之间的信息交 流，包括他们各自完成的文档部分、对其他部分的批注、说明等，同时要对文档 内容进行并发控制( 如不允许多个人同时修改文档的同一部分，这是一种典型的 长事务) 。除了这些长事务处理中的并发控制与通知之外，这些系统一般都提供 有数据保存功能( 使用文件系统或某种类型的数据库) 。 2 8c s c w 体系结构的分类 通常协同工作模型采用三种方式管理共享数据：集中式体系结构( c e n t r a l i z e d a r c h i t e c t u r e ) 、全复制体系结构( r e p l i c a t e da r c h i t e c t u r e ) 和混合式体系结构( m i x e d a r c h i t e c t u r e ) r 1 9 】。这三类体系结构下的协同文本编辑器在设计思想、应用场合、 传输机制上都有所不同。 飘夫、b 囵 焱、 国 少、勺图 麓岛回一一一。一芦。、愚 图2 - 2c s c w 体系结构 f i g 2 2a r c h i t e c t u r e so fc s c w 广尔_ 丁业大学 二学硕士学位论文 2 3 1 集中式体系结构 传统的协同工作系统大都采用基于单播传输机制的式体系结构，即服务器 客户机模式。在集中式体系结构的网络连接中，如图2 2 ( a ) 所示。所有的客户 端都连接到一个中央服务器，形成星形的网络拓扑结构。每个客户端向服务器传 送交互事件，由服务器应用程序完成计算功能后将共享数据发送给各个客户端， 每个客户端本地的共享数据显示得到了更新1 5 j 。 在集中式模式中，因为只有一个用于更新共享对象的应用程序副本，因此对 于共享数据的同步控制比较简单，宜于维护。所有的应用和数据都存放在服务器 上，易于实现存取管理和保证数据的一致性；同时，由于服务器能够实时地将某 个操作者对文档的修改反映给所有协作参于者，因此能够真正实现群件系统中的 “你所见了即我所见”。 2 3 2 全复制式体系结构 全复制式体系结构( 图2 - 2 b ) 与集中式体系结构不同的地方在于，当多个 用户同步地对一个文档编辑时，每个用户站点分别保存在该文档的一个副本，而 且这些文档副本保持实时数据的一致，每个站点都可以接受用户动作，并将动作 执行的结果广播其他用户服务9 , 1 4 】。 采用全复制体系结构的协同工作系统比采用集中式体系的协同工作系统具 有响应速度快，灵活性，可靠性等优点，不会因为服务器失败而造成整个系统的 无法使用。但是由于要求保持每个参与者共享数据副本的同步状态，各自负责来 自自己的和来自远程的操作请求，因此，同步控制比集中式下结构下的并发控制 要复杂的多。所以为了保持同步，必须选择合适的并发控制策略解决冲突。 2 3 3 混合式体系结构 混合式p 2 p 体系结构，如图2 - 3 所示，综合了集中式和分布式特点，构成一 个两级p 2 p 系统，第一级负责管理控制资源的集中式目录信息，处理各个对等节 点处理请求，第二级根据各个对等节点从集中目录服务器获取的资源具体位置信 息与相应的对等节点直接交换信息，保证了查询的准确性和高效性，因此混合式 p 2 p 系统同时具有集中目录式系统的快速查找能力和纯p 2 p 去中心化的优势l l 6 | 。 但是，既然采用了集中式目录服务器，那么服务器的崩溃也会不可避免地造成整 8 第二章c s c w 关键技术 个系统的瘫痪，著名的k a z a a 模型即是p 2 p 混合体系结构的典型代表。另外，目 前广泛流行的b t 下载也属于这种结构体系。 国 j i ? 。“_ 。；j。：j ：- j | | 。、? t t t 。、| | 。7，： 。、 。回蠢一一。二 飞：= 1 飞。 _ ：。沁震一r 墨? i l j , r 一。1 圆 、：j和- 一，爵1 ， 一 !7芒棼：=奇 。、b | |、。、。| 。、。二。黑i ? 气b ? | | 。| | 十1 。、。j bj 。 团1。四” 9 广东工业人学- j 二学硕士学位论文 第三章协同工作系统中的并发控制策略 3 1 传统的并发控制算法 并发控制算法是c s c w 所必须研究的重要内容，并发控制是分布式系统、多进 程、多线程系统中普遍遇到的一个问题【1 7 】。它的主要目标是保证在发生对共享资源 出现并发的访问情况下能够得到所期望的结果。通常的并发控制算法有加锁、时间 戳、基于操作转换o p t 算法等。下面将分析比较三种并发控制算法的优缺点及其 使用场合。 3 1 1 加锁算法 加锁方法是一种悲观的并发控制策略，它将用户所访问的数据对象进行加锁。 当一个用户想要对共享数据对象进行修改、删除、增加等操作的时候，它首先将数 据对象进行加锁，防止其他用户使用，从而满足自己对数据对象进行操作的要求。 其他用户如果要访问这个数据对象，必须提出申请，在无法得到对该数据对象的访 问权限的时候，就必须等待，一直等到控制此数据对象的用户释放锁，才可以访问 这个对象【1 8 】。 在这种严格加锁情况下，保持了各个用户所维护数据对象的一致性，每个用户 具有相同的数据副本，容易维持数据副本的一致性。但是，采用加锁的并发控制方 式时，容易引起死锁。死锁是一种系统状态，在该状态下多个用户都在等待其他用 户释放他们所占据的资源。例如，用户a 获得了数据对象1 的操作权限，那么就将 数据对象1 加锁后，可以对它进行各种操作。同时，用户b 获得了数据对象2 的操 作权限，对数据对象2 进行加锁操作。这时，用户a 必须获得数据2 的操作权限， 才能继续它的操作。然而，用户b 又必须获得数据1 的操作权限，才能继续他的操 作。这时，用户a 和用户b 都在等待，只有对方释放锁，程序才能继续执行。 死锁的一个解决方案就是采用一种机制预防死锁，一个简单但不是很好的克服 死锁的方案就是让每个用户在对数据对象进行操作前，必须锁住它要访问的所有对 象。该方案防止了死锁，但是却带来了不必要的资源访问权限。而且，很多情况下 用户对共享数据对象进行操作前，用户无法预计他到底需要访问哪些共享数据对象。 1 0 第三章协同上作系统中的并发控制策略 3 1 2 时间戳算法 在基于时间戳排序的并发控制机制中，进程中每个操作在执行之前首先验证。 如果该操作不能通过验证，那么将立即放弃该事务。如果该操作不能通过验证，那 么将立即放弃该事务。每个进程在启动时被赋予对等网络j x t a 平台上协同工作系 统的一个唯一的时间戳。这个时间戳定义了该进程在实际操作中的次序，来自不同 进程的操作请求可以根据它们的时间戳进行全排序【l6 。 基于时间戳的并发控制算法中，如果存在一个单服务器，可以根据服务器的时 钟，来赋予时间戳。那么进程中每个操作都是严格有序的，不存在差错，可以按照 先来后到的顺序进行操作。但是对于分布式系统中，各个服务器之间的局部时钟不 同步，比较难以保证各个进程时间戳之间严格排序。 在分布式系统中，为每一个进程建立自己的时间戳，时间戳是用一个二元组( 本 地时间戳，进程号) 表示。为了获得进程发生先后顺序，进程根据下列原则修改它们 的时间戳，并在消息中传递它们的本地时间戳。 第一、根据进程发生的先后，赋予每个进程唯一的逻辑时钟值。 第二、若进程i 发送的一条消息m ，消息m 中应包含一个本地时间戳a ，当接收 进程j 收到消息时，这时对于进程j 本地时间戳是b 。进程i 的时间戳用c 1 ( a ，i ) 表 示，进程j 的时间戳用c 2 ( b ，j ) 表示。比较时间戳c 1 和c 2 值，如果c 1 c 2 ，那么 应当重置本地时间戳的值，修改为b 大于或等于a 。 在这里我们对第二条原则详细说明。由于每个进程都拥有自己的逻辑时钟，这 些时钟的运行并非同步，因此可能出现这种情况：一个进程i 发送的消息中所含的本 地时间戳为1 0 ，而接收进程j 在收到此消息时的本地时间戳为6 ，这显然违背了全 序的要求，因为发送消息进程i 和接收进程j 之间存在着i 一 j 的关系。 根据第二项规则，用于实现逻辑时钟的同步。根据这个规则，应该调整进程j 的时间戳，使c 2 ( b ，j ) = c 1 ( a ，i ) ，例如c 2 ( b ，j ) = c 1 ( a ，i ) + l ：7 a 利用时间戳将操作进 程编号，操作时候按照进程编号顺序进行，严格保证了在不同站点处，所有操作都 是按照同一顺序执行的。这样就可以保持共享对象的一致性。 广东工业大学工学硕士学位论文 3 2 基于操作转换的并发控制算法 基于操作转换算法是e l l i s 和g i b b 在1 9 8 9 年提出的，是一种适用于实时协作系 统并发控制机制。它通过立即执行用户的本地操作以保证用户界面良好的响应速度； 通过“状态向量”来保证操作之间的因果依赖关系：通过用己执行的操作对乱序的 操作进行“转换”以保证对象的一致性以及任一个操作在任一个站点的执行均能得 到发出此操作的用户所期望的结果 1 9 , 2 0 】。 操作转换算法的简单描述和两个主要关系的定义： 用户共享对象0 进行一系列指定的操作，如( o p l ，o p 2 ，o p 3 ，o p n ) ，为 了维护共享对象0 每个站点副本的一致性，对于对象0 的每一个操作o p 在各个站点 都要执行。对于任意站点动态行为可以抽象为四个方面。 操作产生：将对用户界面的操作转化为针对0 的方法调用o p ； 操作传播：将代表用户操作的o p 传送给系统中所有其他站点； 操作接收：接收来自其他站点传来的操作o p ； 操作执行：对象0 执行所接收到的操作o p ； 基于上述定义，系统不断记录各个站点的操作记录和顺序，通过一定的算法分析 任意两个操作之间是因果关系还是并发关系，如果是因果关系，则按照其顺序执行各 个操作：如果是并发关系，则根据预先定义好的不同操作之间的转换规定来转换原有 的操作后，再按收到操作时的顺序执行各个操作，从而保证数据对象在不同站点处的 一致性。 3 3 传统与基于操作转换并发控制算法的分析与比较 加锁并发控制算法中，加锁的方法比较简单而且可以比较好地保证数据的一致 性。只需要对共享对象上锁，就可以保证数据不会被其他用户更改。但是加锁方法 可能会导致用户界面的阻塞。一个严重的问题就是人机交互的不自然，因为用户的 每一个操作都需要等待加锁请求被批准或否决才能继续进行下一个操作，最极端的 情况是用户每按一个键都需要等待。用户端感觉系统响应慢，严重影响系统的交互。 不适用于实时性较强的系统，而本系统是实现多人实时共同文档编辑功能，需要系 统有较快的响应速度。 1 2 第三章协同t 作系统中的并发控制策略 时间戳并发控制算法能够比较严格地保证复制对象的一致性，但它也存在一些 问题。因为在执行每一个操作时，系统都必须等待或者能够确信在所定义的全局序 中领先于此操作的所有操作都已经被执行过了。当采用“乐观”的方法时，用户不 需要等待系统响应，可以直接执行本地操作，但是因为这种操作是乱序的，所以系 统必须采用某种方式来进行修复。在“悲观”的方法中，由于在执行每一个操作时 都需按照预定义的全局序进行，因此在执行某些操作时可能需要等待，与加锁并发 控制算法一样适合系统的实时性要求不强的系统。 通过上面的分析我们可以看到，将传统并发控制算法用于实时协同系统中，会 导致人机交互的不自然。加锁和时间戳算法主要是针对那些非交互式的事务处理系 统而设计的。在那里，操作的发出者都是一个一个的程序而不是用户。而对于程序 来说，等待事务的撤消与重新执行最多只会导致系统总体吞吐率的降低，而不会对 程序本身或程序之间的行为产生负面的影响。甚至这些策略的目标就是要消除程序 之间的相互影响，使得任何一个程序都感觉到它独占了系统中的所有资源。这一目 标与实时系统试图将协作用户紧密地联系在一起的目标是背道而驰的。 论文所提出的p 2 p 协同工作系统是一个实时性要求比较高，要求用户本地操作 能够立刻在系统中反映出来。基于操作转换的算法中，用户在本地的操作可以立即 执行，不需要等待系统的响应，响应速度快，但是对于复杂系统不同操作之间的转 换规则难以确定。所以论文采用一种新的基于d o m 树的多粒度并发控制算法，具 体算法将在第五章介绍。 广东 j 业大学工学硕士学位论文 第四章p 2 p 技术和通用对等网络开发平台j x t a 4 1p 2 p 技术及其应用优势 4 1 1 什么是p 2 p p 2 p 在英文中是p e e r t o p e e r 的缩写，称对等连接或是对等网络。它是一种新的 通信方式，与c s 或b s 这类集中式模式相对应。网络中的每个节点都是一个p e e r ( 对 等点) ，每个p e e r 都具有同等能力，它既可以得到服务，具有客户端特性，又可以提 供服务，具有服务器特性，所以可以说每个p e e r 既是服务器又是客户端。在对等网 络中，每个p e e r 都可以发起一个通信，直接与其他p e e r 进行通信，而不需要依赖某 个服务器【2 1 】。 4 1 2p 2 p 技术的主要优势 在互联网络中流行的通信模式主要是客户服务器模式，这种模式下要求在网络 中必须配置服务器，以服务器为中心，信息通过服务器进行转发。而这种中心化网 络体系结构中，随着客户不断的加入，整个网络的不断扩大，每个信息发送都是通 过服务器，服务器的压力就越来越大。在服务器处会产生计算资源瓶颈和带宽瓶颈， 服务器的崩溃会造成整个系统的瘫痪。而这时，在网络中大部分的客户机却处于空 闲状态。 如何合理利用那些闲置的处理资源和其它未用的带宽，同时防止瓶颈问题，p 2 p 计算模式提供了较好的解决办法。在p 2 p 网络中，每台机器都运行特定的程序来了 解、提供信息，并向其相邻的节点请求数据或服务。邻节点既可以为请求提供服务， 也可将请求中转传递给其它邻居。这样，数据存储、处理能力和带宽等都以一种完 全分散、异步的方式运行，各种负载可以得到合理的平衡。 4 1 3p 2 p 技术当前主要的应用领域 目前，p 2 p 的应用分布很广，并且已经深入到生活的方方面面，o f f i c e 中的 g r o o v e 、音乐下载、p 2 p 流媒体、分布式在线网络游戏等，这些应用大致上可分为 以下四个方面【6 ，7 】： 1 4 第四章p 2 p 技术和通用对等网络开发平台j x t a ( 1 ) 文件共享 p 2 p 技术使任意两台相连接的计算机之间可以直接共享文档、多媒体和其它文 件。利用p 2 p 技术，计算机之问可以进行直接交互，而不需要使用任何一台中央服 务器。n a p s t e r 和g n u t e l l a 都是目前比较流行的p 2 p 文件共享应用软件。 ( 2 ) 分布式计算 通过采用p 2 p 技术，将网络中众多的计算机暂时不用的计算能力连接起来，使 用积累能力执行超级计算机的任务。这方面的典型应用是s e t h o m e 。 ( 3 ) 搜索引擎 p 2 p 技术使用户能够深度搜索文档，而且这种搜索无需通过w e b 服务器，也可 以不受信息文档格式和宿主设备的限制，可达到传统目录式搜索引擎无可比拟的深 度，理论上将包括网络上的所有开放的信息资源。 ( 4 ) 协同工作 随着i n t e m e t 的发展，地理位置的分散，个人远程之间的相互交流、互通消息、 协同工作就变得越来越重要。然而在传统网络中，基于服务器客户机模式的协同工 作系统给服务器带来了极大的负担，造成了昂贵的成本支出。采用p 2 p 技术，使得 互联网中的任意对等点都可以连接起来，形成一个共享虚拟的空间，人们可以自由 地进行各种交互活动。 ( 5 ) 内容分发和共享 p 2 p 使得大范围的文件交换和内容发布变得极其容易。文件交换的需求也很轻 松地延伸到了信息的交换，由于不需要中介网站的参与，在线拍卖也被赋予了新的 形式。最近，p 2 p 流媒体技术成为研究的热点。我们现在常用的c o o l s t r e a m i n g 就是 最好的例子。像w e b 迅雷、p p l i v e 都使用p 2 p 流媒体技术从而在有限的网络带宽条 件下实现了较好的在线视频效果和电视转播质量。 ( 6 ) 即时消息 i c q 应当算是这个领域的先行者，目前q q 、m s n 已经成为网络通信必备的工 具，p 2 p 使得我们的沟通得到突破性的发展。 ( 7 ) 网络游戏 游戏是一个对p 2 p 具有诱惑力的领域，除了典型的对弈类游戏能够采用p 2 p 技 术外，