（计算机应用技术专业论文）分布式应用系统中复制方案的研究与实现.pdfVIP

摘要 摘要 随着计算机网络的快速发展，分布式应用系统的性能和可用性面临巨大的挑 战。对于分布式应用系统，一般都存在用户数目多和并发访问量大而造成系统负 载严重的问题，使得系统的可靠性和性能得不到保证。而复制能够增强系统性能， 提高可用性和容错能力，它是保证分布式应用系统有效性的一个关键技术。 中央广播电视大学远程开放教育教务管理系统是一个大型的分布式应用系 统。为了提高该系统的性能，一种基于消息中间件的异步复制解决方案被提出并 且实现。复制的一个重要公共需求是副本的一致性。由于网络的复杂性，如何保 证副本的一致性是实现复制方案的关键问题。根据限制性的程度，一致性分为不 同的模型，最终一致性模型的程度较弱却具有较好的性能。 为保证副本的最终一致性，副本间需要一种异步的可靠的通信方式。消息中 间件( m o m ) 支持异步的通信方式并且能提高通信的可靠性和通信端点系统的 性能。为了统一各种m o m 系统的接口，j a v a 消息服务( j m s ) 制定了基于j a v a 的异步消息传递的标准。因此，将基于j m s 的消息中间件使用于异步复制方案 中，能很好地发挥它的优势。方案采用j b o s s m q 消息中间件并且利用j m s 和消 息驱动b e a n ( m d b ) 相结合的方式实现了副本间松散耦合的异步通信，采取点 到点和发布订阅两种模式对消息进行可靠传送，进而保证数据副本的最终一致 性。同时对复制方案中的更新冲突、l a m p o r t 逻辑时钟、更新消息操作顺序及副 本故障等问题进行分析并给出有效的解决方法。而后利用l o a d r u n n e r 对实施该 复制方案后的系统进行性能测试，测试的分析结果表明该复制方案能较好地提高 教务管理系统性能。 关键词复制；消息中间件；j m s ；消息驱动b e a n ：分布式应用系统 a b s t r a c t a b s t r a c t w i t ht h e r a p i dd e v e l o p m e n to fc o m p u t e rn e t w o r k ，t h ep e r f o r m a n c ea n d a v a i l a b i l i t yo fd i s t r i b u t e da p p l i c a t i o ns y s t e mi sf a c i n gag r e a tc h a u e n g e t h el o a do f s y s t e mm a y b ev e r yh e a v yb e c a u s eo fl a r g en u m b e r so fu s e r sa n dv a s tc o n c u r r e n tv i s i t ， t h e nt h er e l i a b i l i t ya n dp e r f o r m a n c eo fs y s t e mc a nn o tb ee n s u r e di nd i s t r i b u t e d a p p l i c a t i o ns y s t e m r e p l i c a t i o nc o u l di m p r o v et h ep e r f o r m a n c eo fs y s t e m ，p r o v i d e h i g ha v a i l a b i l i t ya n df a u l tt o l e r a n c e ，a n di ti st h ek e yt e c h n o l o g yt oe n s u r et h ev a l i d i t y o fd i s t r i b u t e da p p l i c a t i o ns y s t e m t h ec h i n ac e n t r a lr a d i oa n dt vu n i v e r s i t ya c a d e m i ca f f a i r sm a n a g e m e n t s y s t e mi sal a r g ed i s t r i b u t e da p p l i c a t i o ns y s t e m i no r d e rt oi m p r o v et h ep e r f o r m a n c e o ft h i ss y s t e m ，a l la s y n c h r o n o u sr e p l i c a t i o ns c h e m eb a s e do nm o mi sd e s i g n e da n d i m p l e m e n t e d t h ec o n s i s t e n c yo fr e p l i c a si sa ni m p o r t a n tc o m m o nd e m a n d b e c a u s e o ft h ec o m p l e x i t yo fn e t w o r k ，h o wt og u a r a n t e et h ec o n s i s t e n c yi sak e yi s s u et o i m p l e m e n tr e p l i c a t i o ns c h e m e a c c o r d i n gt ot h el i m i to fc o n s i s t e n c y , i tc a nb ed i v i d e d i n t os e v e r a lt y p e s e v e n t u a lc o n s i s t e n c yi sw e a k ，b u ti th a sw e l lp e r f o r m a n c e t h e r es h o u l d b ear e l i a b l ea n da s y n c h r o n o u sc o m m u n i c a t i o nb e t w e e nt h e r e p l i c a s i no r d e rt o g u a r a n t e e e v e n t u a l c o n s i s t e n c y t h em e s s a g eo r i e n t e d m i d d l e w a r e ( m o m ) n o to n l ys u p p o r t sa s y n c h r o n o u sc o m m u n i c a t i o n ，b u ta l s oc a n i m p r o v et h er e l i a b i l i t yo fc o m m u n i c a t i o na n dt h ep e r f o r m a n c eo ft h ee n dp o i n t s i n o r d e rt ou 1 1 i f yt h ei n t e r f a c e so fd i v e r s i f i e dm o m ，j a v am e s s a g es e r v i c e ( j m s ) d e f i n e s as t a n d a r do fa s y n c h r o n o u sc o m m u n i c a t i o nb a s e do nj a v a t h e r e f o r e ，i tc a nt a k e a d v a n t a g e so fm o mb a s e d o nj m sw h e nu s e di n a s y n c h r o n o u sr e p l i c a t i o n s c h e m e a d o p t i n gt h em o m o fj b o s s m q ，j m sa n dm e s s a g ed r i v e nb e a n ( m d b ) i n t h i ss c h e m e ，al o o s e l yc o u p l e da s y n c h r o n o u sc o m m u n i c a t i o ni si m p l e m e n t e d t h e p t pa n dp u b s u bt w om o d e sa r eb o t ha d o p t e di nd e l i v e r i n gm e s s a g ea n di tg u a r a n t e e s t h ee v e n t u a lc o n s i s t e n c yo fr e p l i c a s u p d a t i n gc o n f l i c t s ，l a m p o r tl o g i c a lc l o c k ， s e q u e n c eo fu p d a t i n gm e s s a g ea n df a i l u r eo fr e p l i c aa r ea n a l y s e da n ds o l v e di nt h e s c h e m e a f t e rp u t t i n gt h i sr e p l i c a t i o ns c h e m ei np r a c t i c e ，u s i n gl o a d r u n n e rt ot e s tt h e p e r f o r m a n c eo ft h i ss y s t e ma n da n a l y z i n gt h er e s u l to ft e s t i n g ，i ti sp r o v e dt h a tt h e s c h e m ec a ni m p r o v et h ep e r f o r m a n c eo ft h es y s t e m k e y w o r d sr e p l i c a t i o n ；m e s s a g eo r i e n t e dm i d d l e w a r e ；j m s ；m e s s a g ed r i v e nb e a n ； d i s t r i b u t e da p p l i c a t i o ns y s t e m i i i 独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他 人已经发表或撰写过的研究成果，也不包含为获得北京工业大学或其它教育机构 的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均 已在论文中作了明确的说明并表示了谢意。 签名：薅涵笙 日期：型壁曼：妄：垒查 关于论文使用授权的说明 本人完全了解北京工业大学有关保留、使用学位论文的规定，即：学校有权 保留送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部或部 分内容，可以采用影印、缩印或其他复制手段保存论文。 ( 保密的论文在解密后应遵守此规定) 签名：兹么坐 导师签名： 日期： 加g s 2 6 第1 章绪论 1 1 课题的研究意义 第1 章绪论 随着计算机网络技术的不断发展，分布式应用系统的性能和可用性面临巨 大的挑战。对于分布式应用系统，一般都存在由于用户数目多，并发服务访问 量大而造成系统的负载严重的问题。在超负荷的系统提供服务时会暴露出以下 方面的主要问题：系统的服务能力远远不能满足实际需求；系统的服务可靠性 不能保证；系统响应时间长，延迟大，无法满足用户需求；容易造成系统的崩 溃而停止访问服务。 在分布式应用系统中，复制能够增强性能，提供高可用性和容错能力， 因此它是保证分布式应用系统有效性的一个关键技术，是一种增强服务的技术。 进行复制的动机包括改善服务性能，提高可用性，或者增强容错能力。 虽然分布式应用系统中复制已经进行了多年研究，在理论上和实践上都有 了很大进步，但仍然还有很多的问题有待子解决，特别是在实际应用中。作者 参与了中央广播电视大学远程开放教育的教务管理系统的设计和开发工作。由 于该系统的用户数量大，可能在同一段时间内会有大量的访问，对系统的性能 有较高的要求。设计出一种实用的复制方案，对于提高系统的性能和可用性具 有很高的实际应用价值。 因此，随着分布式应用系统的不断发展，从理论上和实践上对复制技术进 行研究都具有非常重要的价值。 1 2 相关领域的研究现状 在分布式应用系统中，复制在理论和应用上都得到了广泛的研究，它的研 究主要集中于复制系统的模型、复制策略和副本间一致性的研究。不同的应用 系统使用复制的目的会有所不同，因而采用的复制策略和方案都会有所不同。 为了提高系统容错性，主要有被动复制和主动复制【2 】两种技术。主动复制 技术中所有的副本同时运行，它们都接收客户的请求，执行请求操作，并对客 户发出请求响应，一旦有副本发生错误，只要有足够多的副本在正常工作，系 统仍正常运行。而被动复制技术只有主服务器接收客户的请求，执行请求操作， 并对客户发出请求响应，同时将执行结果复制到每一个副本上。根据前面两种 技术，融合两者的优缺点，提出了其它混合的复制技术，如半主动复制技术【3 】 和半被动复制技术。 北京t 业大学t 学硕i j 学位论文 在利用复制技术来获得服务的高可用性上， 1 ) 1 9 9 0 年c m u 的s a t y a n a r a y a n a n 及其合作者提出了c o d a 文件系统。该系 统源于a f s 系统，是一个高可用文件系统，能提供稳定的数据可用性。 2 ) 1 9 9 2 年l a d i n 等开发了称为g o s s i p 的体系结构，用它作为框架实现了高 可用性服务。这种体系结构是基于f i s c h e r 和m i c h a e l ，w u u 和b e m s t e i n 早期在 数据库上的工作，可以用来创造一个高可用性的电子公告板或日记服务。 3 ) 1 9 9 5 年t e r r y 和p e t e r s e n 提出了b a y o u 系统，类似于g o s s i p 体系结构和 基于时间戳的反熵协议，b a y o u 系统提供的一致性保证弱于顺序一致性。b a y o u 和其他复制方案的不同之处在于它使得复制对于应用是不透明的。 4 ) 在移动设备上使用复制技术提高系统可用性时，如笔记本电脑和p d a 等，网络分区、易变的环境和断连操作是影响高可用性的重要问题。如何解决 这些问题也是当前复制中研究的热点之一。2 0 0 5 年a b d e l k r i m 和j e a n m a r i e 等 提出了一种c o n t e x t ，a w a r e f 5 】的复制系统，该系统能较好的适应数据复制网络环 境及设备的变化。 为了保证副本间的一致性，在传统的复制策略中，当某一副本接收到更新 请求时，更新信息需同步到其它副本。只有各副本都完成各自的更新，此次系 统更新才算成功。这种传统的复制策略也被认为是悲观复制策略。2 0 0 5 年 y a s u s h i 和m a r c 提出一种乐观的复制策略【4 】，该复制策略允许副本间较弱的一 致性，允许用户在特定时段内能看见不一致的数据，但最终保证副本的一致性。 乐观复制策略相对悲观复制策略能提供更高的可用性和性能。 复制技术也被广泛地使用在提高系统性能上， 1 1 网络服务器的资源在浏览器上的缓存和在网络代理服务器上的缓存都 属于复制形式，这是由于缓存中的数据是服务器中的数据的复制。 2 ) d n s 名字服务维护关于计算机的名字属性映射的副本，通过将所有服务 器口地址绑定到站点的d n s 名字，数据在多个服务器之间隐式复制，负载在 服务器之间能够得以平衡。 3 ) 在很多大规模联机游戏中，有大量的玩家通过网络同时参与游戏，给服 务器带来了大量的负载。而通过将全局游对状态等信息进行复制并分布到客户 端或代理服务器上，根据游戏者在虚拟世界中的位置等信息在客户端之间建立 连接关系，可以减少对服务器访问的压力。2 0 0 7 年j e l l sm u l l e r 和t o b i a s 6 1 等对 此进行了研究。 4 ) 由于视频组播的带宽要求很高，所以在视频组播系统中采用复制技术h j ， 只有少数节点从服务器直接获取数据，更多的节点一方面从其它节点处获得数 据，一方面也向其它节点提供数据。 在复制方案中副本间的可靠通信是相当重要的。在分布式应用系统中，有 三种主要的通信模式：远程过程调用，远程方法调用，面向消息的通信。1 9 9 2 年d o u g l a sbt e r 8 j ，2 0 0 1 年g i w o no n 和m i c h a e lz i n k 唧等的复制方案都采用 了远程过程调用的方式进行通信。2 0 0 0 年n n a r a s i m h a n 等提出的a 1 1 l ! l l i l l l 0 1 系 统的对象复制方案采用了远程方法调用的方式进行通信。上述两种通信方式要 求调用方和被调用方的进程处于执行状态并且多用于同步通信方式，而面向消 息的通信可以取消这个限制并且支持异步通信方式。 消息中间件提出了消息队列和主题的概念，它能利用高效可靠的消息传递 机制帮助应用系统之自j 进行通信，支持点到点和发布，订阅两种通信模式并支持 异步的通信方式。在数据库的复制研究领域中，国内外对消息队列的方式进行 了相关的研究，i b md b 2 1 2 0 0 5 的q 复制方式】中就采用了w e b s p h e r em q 消 息队列的方式。而在分布式应用系统研究领域中，国内外对采用消息中日j 件的 异步复制方案进行的研究和应用都较少。 13 课题来源及主要研究内容 本课题来源于中央广播电视大学远程开放教育的教务管理系统( 以处简称 为“敦务管理系统”) 。教务管理系统分为中央电大、省电大两级平台，地理上 遍布全国，以中央电大为顶层节点，下设4 4 个省级节点，其下又分别涉及到几 个至几十个分校及教学点节点，是一个大型的分布式应用系统，如图1 1 所示。 # r ， c 面 日 日 丽日 j l 罡 “话、舒 图1 - 1 教务管理系统分布结构的示意崮 f i g u r e1 - 1s k e t c h o f a c a d e 衄c a f f a i r s m a n a g e m e n t s y s t e m 对于该系统在某个特定的时间段，可能会发生大量的并发访问和大规模 眦而师感蕻。 省计独， 么慕扑： c、?lllll_1藤驯d 北京t 业大学- 学硕卜学佗论文 的数据传输。例如，在学生进行集中选课的那段时间里，由于同时在线的学生 用户可能是几百甚至上千，所以可能同时会有大量的用户将选课信息提交到省 校服务器，产生大量的并发访问。这样可能会导致服务器的处理速度变慢，甚 至会有崩溃的危险。 本文研究的是分布式应用系统中复制的主要问题，并根据教务管理系统的 性能需求提出复制方案的设计并加以实现。首先，研究分布式应用系统中的复 制和消息中间件，重点研究一致性模型和j m s 消息传递技术，通过对相关原理 的研究为整篇论文打好坚实的理论基础。接着，根据实际应用的需求设计出一 种复制方案，对如何保证各副本间的数据一致性和如何处理副本故障等主要问 题给出解决方法，并在教务管理系统上实现复制方案。而后，对实施复制方案 前的系统和对实施复制方案后的系统分别进行性能测试，并且比较分析测试结 果。 1 4 论文组织 全文由五章组成。 第一章绪论，说明课题的来源，论文的主要内容和所做工作以及论文的组 织结构。 第二章分布式应用系统中复制的研究，主要研究复制的目的、需求、系统 模型及时钟同步，分类总结一致性模型和更新传播方式，研究分布式应用系统 中的通信模式和方式。 第三章消息中间件与j m s 的研究，主要研究消息中间件的特点及相关产 品，j m s 的结构、消息的收发模式和可靠性机制，并对j m s 实现异步通信的不 足进行讨论，同时引入消息驱动b e a n 。 第四章基于消息中间件的复制方案设计与实现，针对教务管理系统提出一 种复制方案及实施模型的架构，给出维护副本数据一致的解决方法，并详细说 明实际应用中方案的实现，包括数据库设计、系统顺序图、类图、文件配置等 多个方面的内容。 第五章实施复制方案系统的性能测试，利用工具l o a d r u n n e r 对实施复制 方案后的系统进行性能测试，分析测试结果并得出测试结论。 第2 章分布式应用系统中复制的研究 鼍曼曼量曼曼曼曼曼曼曼曼i i i i i i 曼曼曼曼! 皇曼皇 第2 章分布式应用系统中复制的研究 在分布式应用系统中，复制研究如何在多个计算机中进行数据副本的维护。 复制能够增强系统性能，提高可用性和容错能力，因此它是保证分布式应用系 统有效性的一个关键技术。 2 1复制的目的及需求 进行复制主要出于两个目的：可靠性和性能【1 2 】。首先，复制可以提高系统 的可靠性。如果一个文件系统已经实现数据复制，那么当一个副本被破坏后， 文件系统只需转换到另一个数据副本就可以继续运行下去。同样地，通过维护 多个副本，系统可以为被破坏的数据提供更好的保护。假设一个文件存在三个 副本，而且每个读写操作都在各个副本上执行。这样可以保护数据不会因为一 个失败的写操作而受到破坏。 进行复制的另一个目的是提高性能。当分布式应用系统需要在服务器数量 和地理区域上进行扩展时，复制对于提高性能是相当重要的。当需要访问由单 一服务器管理的数据的进程数不断增加时，系统就需要进行服务器数量上的扩 充。在这种情况下，通过对服务器进行复制，随后让它们分担工作负荷可以提 高性能。 复制有两个主要公共需求。复制透明性是其中一个需求。这个需求就是说， 客户在一般情况下并不需要知道存在多个物理副本。客户关心的是，数据组织 成独立的逻辑对象，当需要执行一个操作时，他们仅对其中的一项进行操作。 进而，客户期望操作仅仅返回一个值的集合，而不管事实上操作可能针对一个 以上的物理副本。 复制的另一个公共需求是一致性，一致性强度在不同应用中会有所不同， 它主要关注针对一个复制对象集合的操作必须满足这些对象的正确性要求。 2 2 复制系统的基本模型 每个副本管理器为每一个对象都维护一个副本，一般情况下，不同对象的 副本由不同的副本管理器来维护。副本管理器的集合可以是静态的或动态的。 在动态系统中，新的副本管理器可能不断出现9 而在静态系统中这是不允许的。 在动态系统中，副本管理器可能崩溃，那么它们被认为离开了这个系统。在静 态系统中，副本管理器不会崩溃，但他们可能停止操作任意长一段时间。 北京t 业人学t 学硕 j 学位论文 iii i =。, i 皇曼! 皇! 曼曼曼曼 图2 1 表示了副本管理器的一般模型。副本管理器集合提供给客户某种服 务。客户得到一个允许它们访问对象的服务，而这个对象其实复制到了管理器 上。客户每次请求一系列的操作，调用一个或多个对象。不包含更新操作的请 求称作只读请求，包含更新操作的请求称作更新请求。 c 一， 客户 | ，一、 | c 图2 - 1 管理复制数据的系统体系结构的基本模型 f i g u r e2 - 1m o d e lo f a r c h i t e c t u r eo fd a t ar e p l i c a t i o nm a n a g e m e n ts y s t e m 每个客户( c l i e n t ，c ) 的请求先由一个被称为前端( f r o n te n d ，f e ) 的组 件处理。前端的作用是通过消息传递与多个副本管理器( r e p l i c am a n a g e r ，r m ) 进行通信，而不是直接让客户进行通信。这是保证复制透明性的手段。前端可 以实现在客户进程的地址空间内，也可以实现在一个独立的进程。 副本对象上的一个操作通常涉及5 个阶段。这些阶段分别是： 请求前端将请求传给一个或多个副本管理器。一种可能是前端只和 某个副本管理器通信，然后这个管理器再与其他的管理器通信。另一 种可能就是前端将请求组播到各个副本管理器。 协调副本管理器首先进行协调以保证执行一致性。如果需要的话， 在这一阶段，它们将就是否执行请求而达成一致( 如果这一阶段出现 故障，请求将不会被执行) 。副本管理器同时决定该请求相对于其他请 求的次序。 执行副本管理器执行请求，包括尝试性的请求，请求执行的效果是 可以去除的。 协定副本管理器对于要提交的请求的影响达成一致。例如，在这个 阶段，在一个事务系统中副本管理器可共同决定是放弃还是提交事务。 响应 一个或多个副本管理器响应前端。在某些系统中，只有一个副 本管理器响应前端。在另一些系统中，前端接收组副本管理器的应 答，然后它选择或合成一个单独的应答返回给客户。 不同的系统可以选择对各个阶段进行不同的排序，也可以选择它们的内容。 第2 章分布式应用系统中复制的研究 2 3 物理时钟和逻辑时钟 在集中式系统中，时间是明确的。当进程想知道时间时，它就进行一次系 统调用，然后系统内核就会告诉它。如果进程a 询问时间，稍后进程b 也询问 时间，那么进程b 获取的时间值将比进程a 获取的时间值大，或者可能相等， 但无论如何不会小于。在分布式应用系统中，取得时间上一致是不容易的。 2 3 1同步物理时钟 每个计算机有它们自己的物理时钟。这些时钟是电子设备，计算有固定频 率的晶体的振荡发生次数，把计量值分割一下，保存在计数器寄存器中。计算 机时钟与其他时钟一样，并没有完美的一致性。两个时钟的读数之间的瞬间不 同称为时钟偏移。在计算机中使用的基于晶体的时钟和其他时钟一样有时钟飘 移问题，即它们以不同的频率给事件计数，所以会产生差异。 在单个计算机单时钟的情况下，如果这个时钟有少许偏差是不会有多大问 题的。因为这台计算机上的所有进程使用同一个时钟，所以它们内部仍然会保 持一致。在分布式应用系统中，由于多台计算机协同工作，那么需要使所有的 计算机的时钟保持同步。为了知道在分布式应用系统的进程中发生的事件是在 哪个时间，有必要和权威的外部时间源同步进程的时钟，这是外部同步。如果 时钟相互同步到一个已知的精度，那么能通过本地时钟度量发生在不同计算机 上的两个事件的间隔，即使它们没有必要与时间的外部源同步，这是内部同步。 因为目标可以是内部同步而不是外部同步，正确的标准仅仅与时钟“机制 的正常运行有关，而不是它的绝对设置。因此时钟不必非常准确才是正确的。 c r i s t i a n 算法和b e r k e l e y 算法都是应用于内部同步的算法。 2 3 2 逻辑时钟 从任何单个进程的角度，事件可唯一地按照本地时钟显示的时间进行排序。 但像l a m p o r t 指出的，由于不能通过分布式应用系统完美地同步时钟，因此通 常不能使用物理时间找出在分布式应用系统中发生的任何一对事件的顺序。 通常使用类似于物理因果关系的模式，把它应用到分布式应用系统是为了 给发生在不同进程里的事件排序。这个排序是基于下面既简单又显然的两点： 1 ) 如果两个事件是发生在同一个进程p i ( i - l ，2 ，n ) ，那么它们发生 的顺序是p i 观察到的顺序，定义为顺序一i 。 2 ) 每次消息在不同进程之间发送，发送消息的事件在接收消息的事件之前 北京t 业人掌。1 ：学坝t 掌位论文 发生。 l a m p o r t 将推广这两种关系得到的偏序称为发生在先关系( 用一表示) ，定 义如下： h b l ：如果存在进程p i ：e i 引，那么e e 1 。 h b 2 对任一消息m ，s e n d ( m ) 一r e c e i v e ( m ) ，其中s e n d ( m ) 是发送消息的事 件，r e c e i v e ( m ) 是接收消息的事件。 h b 3 ：如果e ，e l 和e 2 是事件，且有e e 1 和e l - - - e 2 ，那么e e 2 。 l a m p o r t 发明了一种简单的机制，称为逻辑时钟。它是一个单调增长的软 件计数器，其值与任何物理时钟无关。每个进程p i 维护它自己的逻辑时钟l i ， l j ( e ) 表示p i 的事件e 的时间戳，用l ( e ) 表示发生在任一进程上的事件e 的时间 戳。 为了捕获发生在先关系一，进程按下列规则修改它们的逻辑时钟，并在消 息中传递它们的逻辑时钟值： l c l ：在进程p i 发出每个事件之前l i 加1 ：l i = l i + 1 。 l c 2 ：1 ) 当进程p i 发送消息m 时，在m 上捎带上值t = l i 。 2 ) 在接收( m ，t ) 时，进程p j 计算b = m a x ( k ，t ) ，然后在给r e c e i v e ( m ) 事件打时间戳前应用l c l 。 虽然上面给时钟的增量是1 ，但任何正数都能选用。通地过在与事件e 和 e 1 有关的事件序列上进行长度归纳，很容易地看到：e e l 可以推出l ( e ) l ( e 1 ) 。 2 4 一致性模型 在复制系统模型中，有多个副本服务器在网络中同时工作。系统中的数据 是由对象集合组成的。一个“对象 可以是一个文件，或者是一个j a v a 对象， 或者是一个数据库的表。每一个逻辑上的对象是由若干称作副本的物理副本组 成的集合实现的。副本是物理对象，每一个都存储在某台计算机上，这些副本 上的操作遵循某种程度的一致性。给定对象的副本并不一定要完全相同，至少 不必在任何的时间点上都要求一样。一些副本可能已经接受了更新的数据而另 一些副本还没有更新。 致性模型实质上是进程和数据存储之间的一个约定。即，如果进程同意 遵守某些规则，那么数据存储将正常运行。正常情况下，一个进程在一个数据 项上执行读操作时，它期待该操作返回的是该数据在其最后一次写操作之后的 结果。在没有全局时钟的情况下，精确地定义哪次写操作是最后一次写操作是 十分困难的。作为替代的方法，就需要提供其他的定义，因此产生了一系列的 一致性模型。每种模型都有效地限制了在一个数据项上执行一次读操作所应返 第2 章分布式应用系统中复制的研究 回的值。带有较少限制的模型比较容易使用，而带有较多限制的模型使用起来 则比较困难，但同时容易使用的模型的执行效果不如较复杂的模型那样好。 2 4 1严格一致性 最严格的一致性模型称为严格一致性。它由以下条件定义：对于数据项x 的任何读操作将返回最近一次对x 进行的写操作的结果所对应的值。 严格一致性中存在的问题是它依赖于绝对的全局时间。从本质上说，在分 布式应用系统中为每个与准确的全局时间对应的操作分配唯一的时间戳是不可 能的。可以放宽条件并将时间分割成一系列连续的、不重叠的时间间隔。但是， 无法保证每个时间间隔内最多只发生一个单一操作。因此仍需处理在同一时间 间隔内所发生的多个操作。 p 1 ： w ( x ) a p 1 ： w ( x ) a p 2 ： r ( x ) a p 2 ： r ( x ) n i lr ( x ) a a )b ) 图2 - 2 严格的一致性与非严格的一致性 f i g u r e2 - 2s t r i c tc o n s i s t e n c ya n d n o ts t r i c tc o n s i s t e n c y 文中用图来描述一致性模型，水平轴是时间轴，且时间从左向右递增，符 号w i ( x ) a 和r i ( x ) b 分别表示进程p i 对数据项x 写入值a ，以及进程p i 读取数 据项x 得到b ，并假设每个数据项的初始值为n i l 。图2 - 2 ( a ) 所示的事件顺序符 合严格一致性，p 1 先对数据项x 写入值a ，p 2 读取数据项x 得到a ；图2 - 2 ( b ) 所示的事件顺序不符合严格一致性，p l 先对数据项x 写入值a ，但p 2 先读取到 的x 值为n i l ，不符合严格一致性的要求。 总之，当数据存储是严格一致的时候，对于所有的进程来说，所有写操作 都是瞬间可见的，系统维持着一个绝对的全局时间顺序。如果一个数据项被改 变了，那么无论数据项改变之后多久执行读操作，无论哪些进程执行读操作， 无论这些进程的位置如何，所有在该数据项上执行的后续读操作都将得到新数 值。同样，如果执行了读操作，那么无论多快地执行下一个写操作，该读操作 都将得到当前的值。 2 4 2 线性化和顺序一致性 ( 1 ) 顺序一致性 尽管严格一致性是理想的一致性模型，但是在分布式应用系统中，它无法 实现。与严格一致性相比，顺序一致性是一个要求稍弱的一致性模型。通常， 北京t 业大学。r 学硕i j 学位论文 数据存储满足以下条件时，称为是顺序一致的：任何执行结果都是相同的，就 好像所有进程对数据存储的读、写操作是按某种序列顺序执行的，并且每个进 程的操作按照程序所制定的顺序出现在这个序列中。也就是，当进程在多台不 同机器上并发运行时，任何读、写操作的有效交叉都是可接受的行为，但是所 有进程都看到相同的操作交叉。在这里，进程可以“看到”所有进程的写操作， 但是只能看到它自己的读操作。 p l ：w ( x ) a p 2 ： w ( x ) b p 1 ：w ( x ) a p 2 ： w ( x ) b p 3 ： r ( x ) br ( x ) a p 3 ： r ( x ) br ( x ) a p 4 ： r ( x ) br ( x ) a p 4 ： a ) r ( x ) a r ( x ) b b ) 图2 3 顺序一致性与非顺序一致性 f i g u r e2 - 3s e q u e n t i a lc o n s i s t e n c ya n dn o ts e q u e n t i a lc o n s i s t e n c y 图2 - 3 ( a ) 所示的事件顺序符合顺序一致性，进程p 1 对x 执行w ( x ) a 写操作， 随后( 绝对时间) ，进程p 2 也执行了一次写操作，将x 的值设置为b 。然而， 进程p 3 和p 4 先读到值b ，然后才读到值a 。也就是说进程p 2 的写操作发生在 进程p 1 的写操作之前，但是进程p 3 和p 4 看到了同样的写操作的交叉，所以 该事件顺序符合顺序一致性。图2 - 3 ( b ) 所示的事件顺序不符合顺序一致性，因 为进程p 3 和p 4 并没有看到同样的写操作交叉。 ( 2 ) 线性化一致性 线性化一致性是一种弱于严格一致性但又强于顺序一致性的模型。这种模 型假设操作具有一个全局有效时钟的时问戳，但是这个时钟仅具有有限的精确 度。设t s o p ( x ) 表示给操作o p 分配的时间戳，操作o p 对数据项x 进行读( r ) 操 作或写( 、聊操作。当数据存储上的每个操作都具有时间戳并满足以下条件时，称 这个数据存储是可线性化的：任何执行结果都是相同的，就好像所有进程对数 据存储的读、写操作是按某种顺序执行的，并且每个进程的操作按照程序所制 定的顺序出现在这个顺序中。另外，如果t s o p l ( x ) t s o p 2 ( y ) ，那么在这个顺序中， 操作o p l ( x ) 出现在操作o p 2 ( y ) 之前。可线性化的数据存储也是顺序一致的。它 们的区别在于：线性化是根据一系列同步时钟确定序列顺序的。 2 4 3因果一致性 因果一致性模型是一种弱化的顺序一致性模型。它将潜在具有因果关系的 事件和没有因果关系的事件区分开来。假设进程p 1 对变量x 执行了写操作，然 后进程p 2 先读取x ，然后对y 执行写操作。这里，对x 的读操作和对y 的写操 第2 荦分布式应用系统中复制的研究 作具有潜在的因果关系，y 的计算可能依赖于p 2 所读取的x 的值。相反，如果 两个进程自发且同时地对两个不同的变量执行写操作，这两个事件就不具备因 果关系。当一个读操作后面跟着一个写操作时，这两个事件就具有潜在的因果 关系。如果数据存储是因果一致的，那么它必须满足以下条件：所有进程必须 以相同的顺序看到具有潜在因果关系的写操作。不同机器上的进程可以以不同 的顺序被看到并发的写操作。 p 1 ：w ( x ) a p l ：w ( x ) a p 2 ： r ( x ) aw ( x ) b p 3 ： r ( x ) br ( x ) a p 4 ： r ( x ) a r ( x ) b p 4 ： r ( x ) ar ( x ) b a )b ) 图2 4 因果一致性与非因果一致性 f i g u r e2 - 4c a u s a lc o n s i s t e n c ya n dn o tc a u s a lc o n s i s t e n c y 在图2 - 4 ( b ) 中，在进程p 2 中由于b 可能是使用r 2 ( x ) a 所读取的值进行计算 的结果，则w 2 ( x ) b 潜在地依赖于w l ( x ) a 。所以w 2 ( x ) b 和w l ( x ) a 两个写操作 是因果相关的，所有进程必须以相同的顺序看到这两个操作。而图2 - 4 ( b ) 所示 事件顺序不符合这个要求，因此也不符合因果一致性。图2 - 4 ( a ) 删除了读操作， 所以w l ( x ) a 和w 2 ( x ) b 现在是并发的写操作，因果一致性并不要求并发的写操 作是全局有序的，因此图2 - 4 ( a ) 所示事件顺序符合因果一致性。 2 4 4fif o 一致性 因果一致性允许不同的机器以不同的顺序看到并发的写操作，但是所有机 器必须以相同的顺序看到因果相关的写操作。如果放弃后一条要求，这样就得 到f i f o 一致性。它满足以下条件：所有进程以某个单一进程提出写操作的顺 序看到这些写操作，但是不同进程可以以不同的顺序看到不同进程提出的写操 作。这种模型很容易实现。其不需要保证不同进程看到写操作的顺序，除非两 个以上的写操作是同一个进程提出的。 p 1 ：w ( x ) a p 4 ：r ( x ) ar ( x ) br ( x ) c 图2 - 5f i f o 一致性 f i g u r e2 - 5f i f oc o n s i s t e n c y 北京t 业大学t 学硕l j 学位论文 图2 5 所示事件顺序符合f i f o 一致性，但不符合前面所述的严格一致性、 线性化一致性、顺序一致性和因果一致性。因为对于进程p 2 提出的两个写操作 w 2 ( x ) b 和w 2 ( x ) c ，进程p 3 和p 4 都以相同的顺序r ( x ) b 和r ( x ) e 读取到x 的值， 所以该事件顺序符合f i f o 一致性。 2 4 5 最终一致性 在前面讲述的一致性模型中，一个重要的假设是并发进程可能同时更新数 据存储。如果数据存储不会出现同时发生的更新操作，或者当出现同时发生的 更新操作时可以容易地化解它们，这时可以使用一种更弱的一致性模型，称为 最终一致性。满足最终一致性的数据存储具有以下属性：没有更新操作时，所 有副本逐渐成为相互完全相同的拷贝。最终一致性实际上只要求更新操作被保 证传播到所有副本，因此其实现通常开销比较小。 最终一致性的一个重要实例就是d n s 。d n s 名称空间被划分成域，每个域 分配一个命名授权机构，由该命名授权机构担当这个域的所有者。只有授权机 构才被允许更新名称空间中它所负责的部分。因此，这个系统根本不会出现两 个更新相同数据的操作所导致的冲突，即写写操作冲突，唯一需要处理的情况 是读写操作冲突。这种情况下允许以异步方式传播更新操作，也就是说，读进 程只有在更新操作执行一段时间后才能看到这个更新操作。 另一个重要实例是万维网。通常情况下，w e b 页面是由单一的授权机构更 新的，一般不存在需要解决的写写操作冲突的问题。但是，为了提高效率，通 常配置浏览器和w e b 代理在本地高速缓存中保存一份已下载页面，并在用户下 次请求该页面时返回高速缓存中的拷贝。两种类型的w e b 高速缓存都存在一个 重要问题，那就是它们可能返回过时的w e b 页面。但是这种不一致性是可接受 的。 这两个实例的共同之处是，如果在一段很长的时间内没有更新操作，那么 所有的副本将逐渐地成为一致的。 2 4 6 一致性模型小结 上面所讨论的一致性模型之间的主要区别是它们限制性的强弱、实现的复 杂程度以及性能的优劣。 1 ) 严格一致性是限制性最强的模型，但是因为在分布式系统中实现这种模 型基本上是不可能的，所以它从未应用于实际系统。 2 ) 线性化是种较弱的基于同步时钟的一致性模型。它更加容易证明并发 程序的正确性，但它很难用于实际程序。相对而言，顺序一致性是一种较好的 第2 苹分布式麻用系统中复制的研究 鼍i 一一i i i i _ 一 一一一一| 皇曼曼曼曼曼曼曼曼曼曼皇曼曼曼曼曼曼曼量 模型，它的可行性已经得到证明，但是它存在性能较差的问题。 3 ) 因果一致性和f i f o 一致性对限制性程度进一步弱化，它们不再要求对 哪些操作以哪种顺序出现达成总体一致，不同的进程可以看到不同的操作顺序。 两者的区别在于f i f o 的限制相对更少。这两种模型较容易实现，性能也优于 较强的一致性模型。 4 ) 从本节所叙述模型的一致性程度上来说，最终一致性是最弱的，它一般 用于容忍相对较高程度不一致性的复制方案中。但相对于前面的模型，最终一 致性的性能更好并且较容易实现。 2 5 更新传播方式 对分布的并且是复制的数据存储上进行的更新操作是在客户上启动的，然 后它们被转发到一个副本。更新应该从这个副本传播到其他副本，同时保证副 本的一致性。 2 5 1 推式与拉式 ( 1 ) 推式更新 在这种方法中，甚至不需要其他副本请求更新，这些更新就被传播到那些 副本那里。永久副本和服务器启动的副本之间通常使用基于推式的方法。需要 保持较高程度的一致性是基于这样一个事实：通常有许多客户共享永久副本和 服务器启动的副本，以及较大的共享的高速缓存，而这些