（计算机应用技术专业论文）一个协同编辑器通信层的设计与实现.pdf

一个协同编辑器通信层的设计与实现 摘要 本文研究容错协同编辑通信层最主要的目的在于透明地进行容错故障的恢复， 尽可能地减少由于回滚产生的计算量，为实时协同编辑系统提供一个可靠的通信 层。本文引入故障检测器，建立实时编辑的容错模型，给出相关算法。然后在容错 通信模型的基础上，结合实时编辑系统进程失效和链路失效的特点，提出了处理容 错实时编辑系统的报文控制的解决方案，通过编辑距离和文档相似度减少网络数据 的流量，提高系统可靠性的效率。另一方面，在复制式容错环境下，按照分割理论 对网络异常导致的网络分割进行讨论，并用k 一致性理论来解释网络分割和网络合 并路径的存在性，探索了容错k 一致性的解决方法。 在行文结构上，本文首先对z o f f i c e 实时编辑系统通信进行了需求分析。然后 介绍相关技术，提出了实时编辑的容错模型，结合k 一致性理论分析了网络分割现 象。接下来，借助编辑距离和文档相似度，以提高容错报文的效率为主线，设计了 一种容错报文的方案，并通过o p n e t 进行仿真实验测试。然后，基于以上研究分 析，设计了通信协议和各种数据结构，实现了z o f f i c e 的容错通信层。最后，对 z o f f i c e 容错通信层进行了测试，分析并讨论了系统可用度、m t t r 可靠性指标。 本文在c s c w 容错通信层上作了一些探索，如容错通信模式和进程转换、容错 报文控制、k 一致性理论在网络分割中的运用等，可以为同类的容错系统提供参考， 具有一定的借鉴意义。 关键字：容错，c s c w , 报文控制，网络分割 作者：王书斌 导师：钱培德 指导教师：吕强 a s b r a c tt h ed e s i g na n di m p l e m e n t a t i o no fac o o p e r a t i v ee d i t i n gc o m m u n i c a t i o nt i e r t h e d e s i g na n di m p l e m e n t a t i o no f ac o o p e r a t i v e e d i t i n gc o m m u n i c a t i o n t i e r a b s t r a c t n 地m a i np u r p o s ef o rt h ef a u l t - t o l e r a n tc o o p e r a t i v ee d i t i n gs y s t e ml i e si nt h e t r a n s p a r e n tf a u l tr e c o v e r , c u t t i n gd o w nt h er o l l b a c kc o m p u t i n g 鼬m u c h 懿p o s s i b l e ， o f f e r i n ga r e l i a b l ec o m m u n i c a t i o nt i e rf o rt h es y s t e m a f t e rp r o p o s i n gaf a u l td e t e c t o r , t h e f a u l t - t o l e r a n tm o d e li sb u i l tu pa n dt h ec o r r e s p o n d i n ga l g o r i t h m sa l ep r e s e n t e d b a s e do n af a u l t - t o l e r a n tm o d e l ，t h ep a p e rb r i n g su pas o l u t i o nt oc e n t r e lt h em e s s a g ep a c k a g ew i t h c o n s i d e r a t i o no ft h ef e a t u r eo ft h ep r o c e s sf a i l u r ea n dt h el i n kf a i l u r ei nf a u l t - t o l e r a n t e d i t i n gs y s t e m b ym e a s u r i n gt h ee d i td i s t a n c ea n dd o c u m e n ts i m i l a r i t y , t h ed a t af l o wi n t h en e t w o r ki sr e d u c e da n dt h ee f f i c i e n c ya n dt h er e l i a b i l i t ya r et h e r e f o r er a i s e du p o n t h eo t h e rs i d e ，b a s e do nt h er e p l i c a t i o na r c h i t e c t u r e ，t h en e t w o r ka b n o r m i t yl e a d st ot h e n e t w o r kp a r t i t i o nw h i c ht h ep a p e ra n a l y z e s a n db yt h ek - c o n s i s t e n c et h e o r y , t h e r ea r e e x p l a n a t i o na n dt h em e r g i n gp a t hf o r t h en e t w o r kp a r t i t i o n f r o mt h ep o 谶o fv i e wo ft h ep a p e 舔t h er e q u i r e m e n ta n a l y z e so ft h ec o o p e r a t i v e e d i t i n gs y s t e mf o rz - o f f i c ea r ef i r s t l yi n t r o d u c e d s e c o n d l y , af a u l t - t o l e r a n tm o d e li s b r o u g h tf o r w a r da n dt h en e t w o r kp a r t i t i o nb a s e do nk - c o n s i s t e n c et h e o r yi sr e a n a l y z e d 。 t h i r d l y , b ym e a s u r i n gt h ee d i td i s t a n c ea n dd o c u m e n ts i m i l a r i t y , as o l u t i o nf o rr e d u c i n g m e s s a g ep a c k a g ei sd e s i g ni nl i n ew i m t h ee f f i c i e n c yo ft h es y s t e ma n dt e s t e db yo p n e t m o d e l e r f o u r t h l y , c o m m u n i c a t i o np r o t o c o l sa n dd a t a s t r u c t u r e sa l ed e s i g n e df o r i m p l e m e n t i n gt h ef a u l t - t o l e r a n tc o o p e r a t i v ee d i t i n g c o m m u n i c a t i o nt i e r f i n a l l y , t h e f a u l t - t o l e r a n tc o o p e r a t i v ee d i t i n gc o m m u n i c a t i o nt i e ri st e s t e da n di t sp e r f o r m a n c eo ft h e s y s t e ma v a i l a b i l i t ya n dm t t ra r ee v a l u a t e d t 嫩st h e s i sd i s c u s s e sa n di m p l e m e n t st h ep r a c t i c a li s s u e so faf a u l tt o l e r a n c ei na s p e c i a lc s c ws y s t e m s u c hi s s u e sa r et h ef a u l t - t o l e r a n tm o d e l ，t h ep r o c e s st r a n s a c t i o n ， m e s s a g e p a c k a g ec o n t r o l ，a n dt h ea p p l i c a t i o no f t h ek - c o n s i s t e n c et h e o r yi nt h e f a u l t - t o l e r a n ts y s t e m i th o p e f u l l yi sh e l p 锚f o rt h ed e v e l o p e r si nt h er e l a t i v ef i e l d s k e y w o r d s ：f a u l tt o l e r a n t , c s c w , p a c k a g ec o n t r o l ，n e t w o r kp a r t i t i o n w r i t t e nb yw a n gs h u b i n s u p e r v i s e db yq i a np e i d e d i r e c t e db yl vq i a n g h 插图 1 1 编辑器基本框架 2 1 可靠群组通信层次结构， 2 2 混合式体系结构 3 1 一次协同操作正常的交互过程 3 2 。饮协同操作进程异常的交互过程 3 3 一次协同操作链路异常的交互过程 3 4 协同容错通信层框架结构 3 5 容错模式图 3 6 进程状态转换图 3 7 容错分割 3 8c s c w 网络故障树 3 9 令牌状态转换图 3 1 0 网络分割树 3 1 1 州络分割树举例 3 1 2k = l 时网络分割的映射过程 3 1 3k = 2 时网络分割的映射过程 3 1 4b e r m u d a 三角形b 的构造 3 1 5b e r m u d a - - - 角形b 的构造 3 1 66 种k u h n st r i a n g u l a t i o n 4 1 论文写作时期与操作数关系图 4 2 论文写作时期与相似度关系图 4 3 速率为1 0 2 4 b p s 下的网络报文流量图 4 4 速率为1 0 2 4 b p s t 的网络报文累积图 4 5 速率为1 0 2 4 b p s 下的网络报文平均图 5 i 检查线结构图 5 2 报文数据结构图 2 9 加 坫埔m墙船孔丝 勰四四凹 蛆驵铊 盯 盯 一个协同编辑器通信层的设计与实现 插图 5 3 恢复协议图 5 4 漏包协议图 5 5 令牌环正常协议图 5 6 令牌环异常协议图 5 7 复制式结构建网图 5 8 复制式站点的连接过程图 5 9 服务者进程流程图 5 1 0 服务者管理进程流程图 5 1 l 消费者进程流程图 5 1 2 令牌的传递图 5 1 3 令牌维护图( a ) 5 1 4 令牌维护图( b ) 6 1 z - o m c e 容错功能菜单图 6 2 设置容错登录服务者池的方式图 6 3 设置容错记录检查文件的文件夹位置图 6 4 设置容错故障恢复的方案设置图 6 5 设置容错故障恢复的相关错误参数设置罔 6 6 服务器i p 设置图 6 7 扫描网段i p 设置图 6 8 服务者i p 设置图 6 9 扫描网段提示图 6 1 0 无法容错时的提示图 61 1 在线消费者和在线服务者i p 列表图 6 1 2 容错系统的检查线当前状态图 6 1 3 容错系统接收和发送的信包图 6 1 4 容错系统令牌的运行情况图 6 1 5 容错日志图 6 1 6 测试设备组网图 6 1 7c ，甄，t ，v 的定义 a 1z o 伍c e 基本通信相关代码 a 2z - o f f i c e 容错通信相关代码 蛆们的豇乳豇船弛娩 弱弱弱弱弱弱盯w卯卯弱弱弱的甜 表格 6 1 参数设置乃= 5 0 0 0 毫秒的恢复试验数据表 6 2 参数设置乃= 5 0 0 0 毫秒的四次恢复的m t t r 试验数据表 6 3 恢复报文控制方案试验数据表 6 4 正常状态下第一轮测试令牌测试数据表 6 5 异常状态下测试令牌测试数据 6 0 6 1 6 2 6 3 6 3 y 9 5 6 8 3 0 苏州大学学位论文独创性声明及使用授权声明 学位论文独创性声明 本人郑重声明：所提交的学位论文是本人在导师的指导下，独立进行研究工作所 取得的成果。除文中已经注明引用的内容外，本论文不含其他个人或集体已经发 表或撰写过的研究成果，电不含为获得苏州大学或其它教育机构的学位证书而使 用过的材料。对本文的研究作出重要贡献的个人和集体，均已在文中以明确方式 标明。本人承担本声明的法律责任。 研究生签名： 期：血掣眇9 学位论文使用授权声明 苏州大学、中国科学技术信息研究所、国家图书馆、清华大学沧文台作部、 中国社科院文献信息情报中心有权保留本人所送交学位论文的复印件和电子史 档，可以采用影印、缩印或其他复制手段保存论文。本人电子文档的内容和纸质 论文的内容相一致。除在保密期内的保密论文外，允许沧文被查阅和借阅，可以 公布( 包括刊登) 沦文的全部或部分内容。论文的公布( 包括刊登) 授权苏州大 学学位办办理。 研究生签名：垂生熟日 导师签名 伊彰白 期：鲎! ! ! 生鄂2 哥 期： ， 1 1 背景 1 1 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 r a t i v ew o r k ) 。目前从计算机的发展趋势来看，客户单机的计算能力日 益加强，已经具备过去中小型服务器的计算能力。从整个系统的计算能力分布来看，数 字化设备的普及和硬件价格的降低，使得很多个人用户成为信息资源的原始生产者和服 务提供者。无线传感器网络和i n t e r n e t 的融合，使信息资源进一步边缘化。如何利用这些 分散的计算资源，完成团队的统一任务是计算机研究的热点之一。 作为c s c w 应用的一个重要研究领域是实时协同编辑，它支持地理上分布的用户通 过网络同时浏览和编辑一个共享的文档、图形或者多媒体文件【1 】。在国内外应用产品的 开发方面，现有的实时协同编辑系统有中国科学院计算技术研究所的c o e d i t o r 2 1 ，清华 大学的c o d e s i g n 3 ，西安交通大学的c o o p d e s i g n e r 4 ，浙江大学的c o d e s i g n 5 】，g r i t t i t h u n i v e r s i t y 的r e d u c e 1 1 和r e c i p e 6 1 ，m i c h i g a nu n i v e r s i t y 的d i s e d i t 以及苏州大学 的压o m c e 等。其中最有影响力的是澳大利亚g r i f f i t hu n i v e r s i t y 的i n t e r n e tc o m p u t i n g r e s e a r c hg r o u p 项目组开发的r e d u c e ( r e a l - t i m ed i s t r i b u t e du n c o n s t r a i n e dc o l l a b - o r a t i v ee d i t i n g ) 、c o w o r d 和c o p o w e r p o i n t 项目。 随着网络环境的延展，实时协同编辑系统可能存在着部分失效或者故障。如果系统 不能妥善处理，就会引起系统数据不一致，进程僵死，进而导致整个系统失灵或崩溃。 系统的高可靠性成为用户和企业的需求，为了增加系统的可靠性，银行、电信和电子商 务等企业不惜以重金购买赛门铁克、n e t a p p 和c d p 等公司产品。目的就是进行数据保 护、备份和恢复，提高系统的健壮性和稳定性，因为这些企业深深地知道对系统故障的 防范就是为企业挽回损失，提高企业的服务质量。比如赛门铁克的v e r i t a s 可以提升 恢复能力，实现实时的状态检查与简化故障排除，提供快速备份和恢复服务，确保生产 系统很少出现或根本不会出现停机情况。再如c d p 推出的连续数据保护方案，就解决了 过去各种解决方案都将主要精力放在定期的数据备份上，并因此而产生恢复时间不及时 的缺点，从而提出了由备份转向恢复的观点。管理员根本不需要考虑备份的问题。传统 的方式只能创建、管理和恢复单个时间点的数据备份，这样的保护可以提供灵活的目标 第一章绪论一个协同编辑器通信层的设计与实现 恢复点和快速的目标恢复时间，而相比之下，c d p 可以捕获和保护数据中所有的变化， 并非仅仅是某个预先选定的时间点。这样就可以随时访问数据，减少数据损失并消除代 价高昂的停机损失。 正如m 7 i 螂的企业口号“备份仅仅是个开始，恢复才是终极目标”。 再来看看服务中断导致的后果。每小时信息流的中断将意味着收入下降，利润损 失。同时，也是对公司声誉、员工效率和竞争优势的损害。数据的高可用性，仅仅要求最 少的管理，显著减少了由于日常维护造成的网络中断时间。 而现在的c s c w 系统都是在理想的、无故障、所有网络异常忽略的情况下建立的。 但实际的情况是局部的错误总是会发生，而且可能会影响到整个系统的功能。这样 就需要用程序时刻监视整个系统，提高系统的容错性能，而不是屏蔽故障。为了实 现c s c w 系统容错，需要重新定义或者隐藏没有容错功能的组件和模块。 上述文献【6 】中提到了r e c i p e ，在这个系统中提出了集中式环境下的容错方案，并 对容错问题进行分析。由此可见，对于容错问题的考虑已经日益受到关注。 1 1 2 课题的项目背景 本课题是在苏州大学2 1 1 工程重点建设学科项目资助( x 2 1 1 8 0 0 4 ) 下进行的。项目名 称是二o m c e 。项目组针对网络环境下，多人参与文档的编辑、审定和修改等实时协同操 作，对文档进行多版本控制，提高工作效率。 z - o m c e 是一个基于工作流的协同编辑系统，授权用户可以定义和修改一个文档的 工作流程，工作流引擎将驱动协同编辑客户端流转该文档，流转过程中可以多人实时协 同编辑，系统同时提供了文档版本控制功能，支持多版本的文档查询和文档比较。协同 编辑器的基本模块见图1 1 。本文的工作就是集中在阴影的层次。此系统是基于j a v a i 吾言 进行开发，后台由o r a c l e 数据库提供支持。 z o f l i e e 文本编辑器 c s c w 工作流版本 其它 协同编辑引擎控制功能 网络通信层 j ：雾嚣臻鞘霾鬻雾蠹熬f 图1 1 ：编辑器基本框架 2 一个协同编辑器通信层的设计与实现 第一章绪论 1 2 课题的内容及意义 为了提供给z o f f i c e 文本编辑器一个可靠、稳定的网络运行环境，本课题为c s c w 实 时编辑系统引入容错通信层的思想，设计并开发一个满足实时协同编辑的容错通信层。 容错通信是系统的需要。当实时协同编辑系统有正常通信的情况下，可以实现每个 站点之间的通信，交互实时操作和系统指令，并且能够维护系统的正常运行。但当实时 协同系统中的某个部件出现故障或者部分失效的时候，整个系统要求不能停机或重启， 实时协同编辑系统仍然能够运行。尽管部分失效对整个系统的性能有一定的影响，但它 应该不会影响系统中整个应用程序的正确执行。实时容错协同编辑容错系统避免了在单 机系统中，当系统中的一个关键部件出现问题，整个应用程序就无法继续执行的情况， 从而提高系统整体性能。 深入一步分析，容错通信的优化需要容错报文的控制。在维护整个系统的稳定性和 可靠性的前提下，采用对报文进行控制的策略可以减少报文量。当故障被修复时，以最 低的网络恢复成本，帮助系统可以尽快弥补刚才的系统故障，继续正常的实时协同编 辑。达到屏蔽故障的目的。 另一方面，容错通信需要解决网络分割的难题。当复制式站点之间的连接出现部分 失效时，实时编辑系统需要考虑失效的恢复以及编辑上下文的一致性。z o f f i c e 简化了 网络分割的处理，借助主环和辅环将k - - 致性问题转化为2 一致性问题。 本课题详细阐述了实时协同编辑的容错通信层的系统模型，容错恢复时的数据报文 控制和容错时产生的网络分割与合并的过程。 本课题的意义在于提高通信层的可靠性。“可靠性是指产品在规定的条件下和规定 时间内完成规定功能的能力”f 7 1 。随着计算机技术的迅速发展使得软件产品和网络活动 越来越复杂，因特尔网络规模越来越大，构成因特网的网络设备与元件越来越多。这些 软件面l 临着多变的内外部环境。在这种情况下，软件的可靠性显得越来越重要，更加突 出。软件的可靠性是衡量一个软件质量好坏的一个指标。高可靠性提高软件系统的运行 能力，降低维修保障费用。软件的可靠性已经被列为评价系统最基本的价值目标之一。 它是一个系统的重要质量指标，为了提高软件的可靠性，将不可避免地增加成本，但是 可靠性差的软件产生故障时要求花费修理费加上因故障停机造成的损失，将会是更大的 损失。 提高c s c w 实时容错通信层可靠性的现实意义有： 1 增加系统的可用性。在规定的条件下，系统在任意随机时间，任务的执行仍处在可 用状态。 2 增加系统的可信度。加强用户对所使用系统的信任感，提高用户使用的满意度。 3 增加系统的可靠性。提高系统本身抗异常的能力，增加系统的稳定性。 3 第一章绪论一个协同编辑器通信层的设计与实现 1 3 课题的贡献 本课题的贡献小结如下 1 在复制式结构中，建立了一个链路失效和进程失效的容错通信层。通过容错探测 器加强对异常的监视与处理，引入令牌环增强对网络容错的健壮性。 2 针对现有的实时协同编辑软件进行容错报文的控制，减少网络i - - i 拘报文传输量， 降低通信子网的负载通信量。 3 用k 一致性理论详细分析了实时协同编辑中存在网络分割，提出网络分割与合并路 径的存在性。 1 4 论文结构 本文共分六章，具体内容是按如下方式进行组织的： 第一章绪论，对论文内容作了整体性的介绍，主要内容包括课题、内容、意义以及 创新点。 第二章需求分析及其相关技术，对实时编辑系统通信的现状进行了分析，指出其 局限性，给出实时编辑系统通信层设计目标、系统需求和用户需求。然后对容错相关技 术，z - o m c e 相关模块进行介绍，主要内容包括容错通信的层次结构和分布计算的相关 预备概念。 第三章z o m c e 容错通信研究，对z 。o m c e 容错通信进行研究，设计了实时编辑系统 通信模型、进程状态转换模型以及实现的算法。详细阐述了网络分割，并用k 一致性理论 对网络分割的过程进行分析。 第四章z 0 5 c e 容错报文控制研究，对z o m c e 容错报文控制进行研究，借助编辑距 离、相似度的计算，对容错恢复的具体方案进行了阐述。 第五章z o 伍c e 容错通信实现。这部分重点介绍了容错通信的实现和相关的主要模 块和实现过程。 第六章z o m c e 容错通信层测试结果与讨论，演示了z o f b c e 的容错使用，测试了容 错通信层的功能，讨论并分析容错可靠性的性能参数。 最后，在第七章对整个毕业设计工作进行了一个总结，并对系统的未来发展进行了 展望。 4 第二章需求分析及其相关技术 这一章在现有实时编辑系统通信的分析比较的基础上，给出实时编辑系统通信层设 计目标，按照系统需求和用户需求加以具体说明，为后续的通信层研究做好需求分析。 然后介绍了容错通信层研究与实现过程中运用的容错技术和分布式计算方法，给出一些 研究需要的预备概念。 2 1 什么是容错 容错是指计算机在运行过程中发生一定的硬件故障或软件错误时仍能保持正常工 作而不影响正确结果的一利一性能或措施。汁算机处理和存储的信息不断增长，人们日 益关注数据稳定性和可靠性相关的数据安全问题。对于实时系统而言，一旦管理或者 服务中断将给整个工作和学习带来极火的混乱。怎样确保数据安全，保证计算机系 统的连续稳定运行成为软件设计与实现最为关注的问题之一。常见的方法有r a i d 技 术、s c s i 技术、f c 技术、集群容错、双机容错、网络附加存储n a s 、存储区域网络s a n 、 异地容灾【8 1 。在这些方法。 i 有的是通过增加硬件设备冗余，有的是通过软件手段提高系 统的可靠性。 2 2现有实时编辑系统通信层的分析 本课题是通过软件的方法提高实时编辑通信的可靠性。当网络的规模增加时，实时 编辑系统中某处出故障的机率可能任意地增大。每当发生故障时，为了避免重新启动算 法，算法应被设计成能够恰当地处理这些故障。这就是实时编辑系统的容错问题。对于 不同的容错问题，解决方案是特定的( a dh o c ) 9 卜下面就z o f i i c e 项目，详细分析实现 实时编辑容错的需求。 2 2 1实时编辑系统通信的现状 现有的实时编辑系统中g r i f f i t hu n i v e r s i t y 的r e c i p e 6 给出了容错恢复的设计，这 个系统是基于集中式通信服务器客户机模式的f 1 0j 。而在国内南京大学良j r e c e s 1 1 】系 统结构中所涉及的容错技术，其实质是错误检测，即依赖一台主服务器来判断各节点是 否出现故障，如果出现故障，系统则将其剔除，该节点不再参加工作。而对于大多数的 实时协同软件并没有将容错做专门的处理。比如g r i 伍t hu n i v e r s i t y 的c o w o r d 1 1 ，协同 用户需要通过远在澳大利亚的协同服务器，如果网络通畅，两台客户机可以实现协同 编辑。但如果出现通信异常，则整个进程崩溃，无法恢复协同工作。用户只能等待网络 第二常需求分析及其相关技术 一个协同编辑器通信层的设计与实现 通畅，重新连接协同服务器。由此可见，实时在线用户的编辑将受到网络通信的严重影 响。 2 2 2现有实时编辑系统通信的局限性 基于对以上实时编辑系统通信的现状分析，本文归纳得出它们存在以下一些缺点和 不足： 实时编辑系统的通信容错能力薄弱，系统的可靠性不高，不能及时地应对实时变 化的网络通信状况。 对出现的实时编辑系统通信中的错误采取粗暴的屏蔽措施，没有从用户的角度思 考问题，尽可能方便用户的使用，尽可能提高系统的健壮性。 在阱同用户从通信异常后恢复的过程i i = l ，原有客户机的实时编辑结果对原有数据 的利用率不高，原有数据被浪费。系统为了获得最新的文档不得不重新获得雷同 的数据。 2 2 3实时编辑系统通信层设计目标 基于当前实时编辑系统通信的不足，z - o f f i c e 容错通信层屏蔽通信中的异常，尽可 能恢复通信进程，做到容错时对用户透明，提供一个稳定、可靠的通信层。具体目标分 述虫下： 采用释错探测器实现对c s c w 链路失效和进程失效进行容错。容错探测器可以 捕捉到的错误有套接字异常、主机名异常等。 采用容错通信报文控制，减少网络报文信源通信源端信报包数，降低网络流量。 用户使用的透明性，提高系统的可靠性和健壮性。 2 3 系统需求分析 下面对z o f f i c e 实时编辑通信层的系统需求具体分析如下： 1 对等计算 每个协同客户机都能完成对等计算。他们之间的地位是相等的。实现点到多点实 时通信。任何一个协同客户不仅是信息的提供者，而且也是信息的使用者。每个协 同用户就是一个信息源，实时地向其它的协同用户发布最新的编辑操作。 6 ， 一个协同编辑器通信层的设计与实现 第二章需求分析及其相关技术 2 协同工作 多个用户之间利用实时协同编辑平台，完成文档的编辑分享在线编辑的信息资 源任意两台客户机都可以建立实时联系，进行交互活动。协同用户之间是一个有 机的整体，共同协作完成一项编辑任务。 3 系统的可靠性 实时编辑系统需要一个可靠运行平台，这是任何网络软件产品所追求的理想。可 靠的系统可以显著地提高用户的满意度。 4 容错报文控制 网络带宽是网络通信的必备资源，有限资源以及有偿资源。为了充分的利用网络 带宽，实时编辑系统应该尽量减少网络报文数量，进而减少网络流量。同时保证通 信的实效性，提高容错的反应速度。 5 文档共享 每个用户都可以直接发布对文档的共享操作，使大范围的文件共享变得极为容 易。不o m c e 主要针对的是文本的处理，解决的是文本的多用户共享。这种文档的 共享是协同工作的基础。 2 4 用户需求分析 上一节的系统需求分析是对系统通信的要求，下面给出用户需求。它是使用者的要 求，具体的用户需求如下； 1 容错具有透明性 容错的目的是为了处理实时编辑中进程失效和链路失效，为实时用户提供一个稳 定、可靠的通信层。作为普通的用户希望不要参与具体的过程，一切容错处理由系 统自动完成，并且保证实时操作的互操作性。 2 容错界面友好 由于不稳定网络环境下用户数量的动态增减，容错系统在保证对用户透明的前提 下，允许用户手动修改容错参数设置，配置合适的参数适应不同的网络环境。同时 给出一些友好的交互提示，帮助用户掌握当前的网络通信情况。 3 容错环境下并发操作的一致性 由于网络异常的存在，操作编辑用户要在网络异常之后，重新计算并保持一致性。 为了实现以上的需求，后继章节将对z o d i c e 进行建模分析，容错报文分析，网络分割分 析，测试系统的可靠性与稳定性。 7 第二章 需求分析及其相关技术一个协同编辑器通信层的设计与实现 2 5z o f f i c e 相关模块 为了进一步了解z o f f i c e ，下面给出乐o 最c e 相关模块的具体内容 1 2 如图11 所示。 2 5 1c s c w 在z - o f f i c e 项目中把e g o t 算法运用在协同编辑模块中，实现了z o f f i c e 系统对于实 时协同编辑的要求，也使算法得到了验证。协同编辑模块由多块子组件构成：用户输出 接口处理模块、用户输入接口处理模块、远程站点处理模块、本地站点处理模块、协同 引擎模块、对话状态处理模块、站点服务联结模块、历史缓存清洗模块。协同编辑模块 在工作流系统的支持下，允许若干个对某一文档具有编辑权限的用户在不同的站点实时 编辑这一文档，由协同服务端模块控制协同小组的初始同步、动态加入、退出。协同机 制建立后，多用户实时通信采用完全复制式结构的通讯方式，减轻了服务器的负担。 2 5 2 工作流 对于一篇文档，首先将文档划分成若干个块( i p b i o c k ，每个b l o c k 可以包括若干个章 节，b l o c k 为单位分配给相应的协编进行编辑。定义流程时，从2 个层次进行定义，首先 是文档层次，为一篇文档定义一个文档编辑流程，然后是b l o c k 层次，以b l o c k 为单位定 义一系列的子流程( 在定义子流程的同时即完成了文档b l o c k 的划分) ，由这些子流程构 成文档编辑流程的协同编辑部分。 2 5 3 版本控制 对于管理和存储，目前已有数种不同存储x m l 文档的方法可供选择，例如x m l 数 据库。但是虽然现在有各种形式存储x m l 文档的方法，但每一种都无法保留使用者对 文档所做的一连串修改痕迹，这就是文档版本管理问题。文档版本管理最主要的问题是 如何有效地存储连续修改的文档，减少存储成本，快速获取文档版本，并且能支持多版 本z o f f i c e 文档查询。 2 6z o m c e 容错通信 基于以上的z o f f i c e 系统需求分析和用户需求分析，下面具体介绍c s c w 容错通信 的层次结构、容错协同通信的特点、容错协同通信的体系结构和相关的概念。 2 6 1 可靠群组通信层次结构 针对o s i 的标准结构( 1 3 l 对应协同的整体结构的映射如图2 1 所示，具体每层的功能 如下： 8 ， 一个卧i 司编辑器通信层的设计与实现第二章需求分析及其相关技术 协同应用支持 可靠传输 资源预留 主机扩展j 主机扩展 i p v 4 或蹦 应用层 表示层 会话层 传输层 网络层 数据链路层 物理层 图2 1 ：可靠群组通信层次结构 主机利路由扩展予层：有效的建立从发送方到接收群组各成员的组播分组传播路 径，包括实现组播分组的收发所涉及的发送方和接收群组各成员结点，以及中间 转发路由器。 资源预留子层：为了实现信息在复杂网络环境中有效传送，须对有限的网络的使 用进行控制。对群组通信支持而言主要是引入网络带宽和延时方面的性能。 可靠传输予层：通过群组通信各方的缓存机制实现可靠群组通信。 协同应用支持子层：提供各种协同应用不同的通信服务，如音频、视频信息传送和 可靠的数据传输等。 2 6 2容错实时协同通信的特点 从整个可靠通信的层次图上可以看耍j c s c w 实时编辑系统是建立在有效的从发送 方到接收群组各成员的组播分组传播的基础上。 容错通信需要工作在复杂的用户环境和网络环境中实现点到多点通信的协同用户 通信管理保证协同通信的服务质量和可靠性传输，屏蔽异步的协同环境中的通信子网 的异常。 2 6 3容错实时协同通信的体系结构 常见的容错通信的体系结构可分为三大类 1 4 】： 集中式体系结构。这是一种典型的c l i e n t s e r v e r 模式。 复制式体系结构。如图2 2 所示虚线内通信为完全复制式通信。 混合式体系结构。如图2 2 所示全部通信为混合式通信。 9 第二章需求分析及其棚关技术 一个协同编辑器通信层的设计与实现 、 j j 站点 图2 2 ：混合式体系结构 由于通信子网异常或者资源子网的异常，会影响整个系统的正常运行。这些异常主要包 括服务器的崩溃，通信线路的中断和进程的异常等。因此，为增强c s c w 实时编辑系统 的可靠性，整个系统的从主从模式扩展为点对点模式再到混合模式。点对点模式打破了 传统的c l i e n t s e r v e r 模式，在对等网络中，每个节点的地位都是相同的，具备客户端和 服务器双重特性，可以同时作为服务使用者$ f l j l l i t 务提供者。每个成员直接从其他成员而 不是从服务器的参与中受益；系统中成员同时扮演服务器与客户端的角色。 在典型的集中式模式中使用最为广泛的服务器客户机模式。而在分布式模式中， 每个复制式站点可自我管理、自我反馈，同时也必须广播所有复制式操作到其它的站 点，从而保证数据的致性。混合式模式介于前面两种模式之间，系统中的局部有时是 集中式模式，有时是分布式模式，这完全取决于系统的需求。在文献【1 5 】中研究y j j i t 务 器客户机模式一卜，服务器和客户机在失效消失后如何重新加入系统，实现途径是重新 加载卜次的操作，但是这里存在一个问题，如果服务器崩溃，无论是丰服务器还是主备 份服务器崩溃，系统将瘫痪。也就是说故障恢复系统密切依靠服务器，服务器在恢复中 处于至关重要的地位。一旦服务器崩溃，整个系统将不能再运转。 本系统采用混合式体系结构，如图2 2 所示，这种结构结合了复制式和集中式的优 点，便于用户的动态加入与退出，增加了系统灵活性。 2 7 容错实时协同编辑相关概念 为了能进一步准确地描述容错实时协同编辑的通信过程，下面给出分布式环境下容 错实时协同编辑的相关定义【9 1 1 6 】 1 7 1 a 2 7 1 快照( s n a p s h o t ) 定义2 1 ( 局部因果关系) e g - 3 _ 毋，i j ，其中e p 为发送事件，接收事件或者内部事 件之一。当进程故障出现时，计算必须重新开始。局部因果关系用来维持事件的先后顺 序。本文选用m a t t e r n 的向量时钟来描述局部因果关系。 1 0 一个协同编辑器通信层的设汁与实现第二二章需求分析及兑相关技术 定义2 2 ( 发送接收消息列表) 假设存在从p 至j j q 的信道，那么p 的状态包括在 事件e p 至事件e 中，p 已向g 发送的消息列表s e n 品：g 的状态毋包括在事件e ；l 至事 件e # 中，q 已接收p 的消息列表r e c 如。 定义2 3 ( 快照状态s n a p s h o t s t a t e ) 快照算法的目标是通过组合每个进程的局部状态( 即 快照状态) ，明确地构造系统配置。进程通过存储一个局部状态，取得局部快照，并 称c ；y q p 的快照状态。 定义2 4 ( 全局快照s ) 全局快照s 由集合p 中每个进程p 的快照状态c ：组成，记为s = ( c ；，c ；。) 。局部状态中包含通信历史。如果信道册的状态定义为p 所发送但不由g 接 收的消息集，那么快照s 定义了一个配置。也就是说，信道p 口状态定义为p 所发送但不 由口接收的消息集，快照5 定义了一个配置，消息s e n 二r e c c 集。 2 7 2 检查点( c h e c k p o i n t ) 系统设计的个重要部分就是如何使系统在失效后或故障后恢复。检查点技 术 1 s 1 9 1 1 2 0 就是将进程的状态存储在持久存储器中，任何进程可从故障点开始恢复继 续执行，而不是从初始状态重来。检查点是用来维护全局快照的一致性的时间点。在分 稚式系统中，由于进程的交互，进程常常相互依赖，p 进程状态的进程被迫回滚。当故障 发生后，回滚协议用检查点和消息日志还原系统，实现全局一致状态。如果接受的消息 已经记录在全局致的状态内，则发送消息也必须记录下来。在文献【9 ，分布式系统 有多种检查点方式，大致可以分为两大类：同步检查点和异步检查点。 在同步检查点中，各自进程周期性存储检查点，并且彼此没有任何合作。如果发生 故障恢复，进程相互通信决定恢复到一个局部一致的系统状态。如果出现本地状态是因 果联系的，站点接受到的消息是因果依赖的，回卷将减少因果依赖。这个过程将一直重 复到所有的进程独立存储检查点。检查点额外的存储量小，但是这种方法会产生多米诺 效应。为了消除多米诺效应，k i m v e n k a t e s h 采用了依赖跟踪。在一个产生依赖的新消息 前插入检查点。消息日志和消息排序在许多文献中被用来处理多米诺效应。 异步检查点需要在每个处理机上存储多个检查点，这样，存储容量就可能增加。这 个问题可能通过周期性的建立恢复线( 全局的一个检查点集合) 得以解决。同时删除在 恢复线以前的那些检查点。在同步检查点方案中，不会产生多米诺效应，但牺牲了进程 的独立性，导致在做检查点时额外的消息。用这种方法，进程之间保持检查点之间的同 步，所以全局的检查点一致总是得到保持的，检查点的存储量是最小的，因为每个进程 只是在任意一给定时间保持一个检查点。但进程执行时可能要求所有合作检查点暂停， 导致执行效率下降。 2 7 3 检查线( c h e c k p o i n tl i n e ) 在分布式系统中使用检查点技术会产生多米诺效应。也就是相互依赖的进程彼此回 1 1 蔓三童 堡查坌堑星些塑苤垫查 = 全塑旦塑塑矍望笪星塑丝生皇兰垫 滚，浪费计算资源，实现全局一致状态的现象。 1 多米诺效应的解决策略研究 在文献【2 l 】中指出了多米诺效应本质定理：分布式系统中潜在多米诺效应的充要条 件是在其执行过程中形式逆时先于”。多米诺效应并非源于差错的传播。而是各 进程检查点设置与其通信结构不协调引起”逆时先于”所致。 2 多米诺效应的解决 避免：如果一个检查点与通信模型能够保证所有检查点间隔内消息的接收事件都 处在消息事件之前，则此模型是多米诺迟钝的。 检测与消除：在消息前先插入一个临