（计算机应用技术专业论文）冗余服务中容错算法的研究与设计.pdf

摘要 随着计算机网络和通信技术的发展，分布计算逐渐成为计算技术的主流。当前， 火规模事务处理、分布实时以及关键抗毁等应用的发展对分布式系统的j j 用性和 性能两方面都提出了很高的要求。在这些应用的驱动下，越来越多的分布式系统 采用冗余服务技术来提高可用性和性能，兀余服务容错逐渐成为分布式领域的研 究热点。 本文在较深入地研究了冗余服务中的容错算法、负载平衡的基础上，通过在冗 余服务中引入主动负载平衡机制，提出r 一种行之有效的冗余服务容错算法；该 算法方面能够满足客户请求对可用性的要求，另一方面有效地提高了系统的性 能；基于c o r b a 分布计算通信平台，本文还构建了该算法的对象模型，并在此 基础上实现了一个原型系统，通过实例测试验证了该算法的可行性。 本文的主要t 作体现在以下几个方而： l 在冗余服务容错巾引入主动负载平衡机制，实现了资源预留的负载平衡。 2 把客户请求区分为读写两类，实现了简单高效的请求并行执行模型。 3 设计了简单高效的多备份数据管理中的状态一致性维护协议。 关键词冗余服务；容错；分布对象；主动负载平衡：q u o r u m a b s t r a c t a sd e v e l o p m e n to fc o m p u t e rn e t w o r ka n dc o m m u n i c a t i o nt e c h n o l o g y ，d i s t r i b u t e d c o m p u t i n gb e c o m e st h em a i nc o m p u t i n gt e c h n o l o g yc u r r e n t l y ，t h ed e v e l o p m e n t so f d i s t r i b u t e da p p l i c a t i o n s s u c ha s l a r g et r a n s a c t i o np r o c e s s i n g ，r e a l t i m ed i s t r i b u t e d c o m p u t i n ga n dk e yd m - n a g e - t o l e r a n ta p p l i c a t i o n ，r e q u i r em o r eh i g h e ra v a i l a b i l i t ya n d p e r f o r m a n c ei nd i s t r i b u t e ds y s t e m s ot h er e d u n d a n ts e r v i c ei su s e di nm o r ea n dm o r e d i s t r i b u t e ds y s t e m sf o ri m p r o v i n ga v a i l a b i l i t ya n dp e r f o r m a n c e ，a n df a u l t t o l e r a n t a l g o r i t h m sa r ew i d e l ys t u d i e di nr e d u n d a n ts e r v i c em a n a g e m e n ts y s t e m a f t e rs t u d y i n gm o r ed e e p l yt h ef a u l tt o l e r a n ta l g o r i t h ma n dl o a db a l a n c i n g t e c h n o l o g yi nr e d u n d a n ts e r v i c e s ，a c t i v el o a db a l a n c i n gi si n t r o d u c e di n t ot h er e d u n d a n t s e r v i c es y s t e m ，a n dan o v e lf a u l t - t o l e r a n ta l g o r i t h l ni sb u i l ti nt h i sp a p e r u n d e rt h e c o n d i t i o n so fg u a r a n t e e i n gt h ea v a i l a b i l i t yo fr e d u n d a n ts e r v i c es y s t e m ，t h ep e r f o r m a n c e i se f f e c t i v e l yi m p r o v e d t h el o g i co b j e c tm o d e li sb a s e do nc o r b aa mt h ep r o t o t y p e i si m p l e m e n t e d ，a d d i t i o n a l l y , s y s t e mt e s tr e s u l t ss h o wt h ef e a s i b i l i t yo ft h ea l g o r i t h m t b em a i nw o r ko f t h i sp a p e ri sa sf o l l o w s ： a ) b yi n t r o d u c i n gt h ea c t i v ei d e ai n t or e d u n d a n ts e r v i c e ，t h er e s o u r c e - s a v e dl o a d b a l a n c i n gi sp e r f o r m e dw e l l b ) r e q u e s t sa r ec l a s s i f i e di n t or e a da n dw r i t et y p e s ，a n db o t ho fw h i c ha r ed e a l t w i t ha c c o r d i n g l y t h ep a r a l l e lr u nm o d e lo fr e q u e s t si sp e r f o r m e dv e r ys i m p l ya n d e f f e c t i v e l y c ) t h ec o n s i s t e n c yp r o t o c o lo fs t a t er e p l i c a t i o n si sp e r f o r m e dv e r ys i m p l ya n d e f f e c t i v e l y k e yw o r d s ：r e d u n d a n ts e r v i c e ，f a u l tq b l e r a n t ，d i s t r i b u t e do b j e c t ，a c t i v e l , o a d b a l a n c i n g ，q u o r u m i i 第1 章绪论 几十年代以来，随着个人计算机的普及以及叫络通信技术的发展，计算资 源和信息资源被广泛分布在网络的各个节点上，这使得计算模式由原来的主机 系统向客户, n 务器模式发展，分布计算逐渐成为计算技术的主流；在分布式系 统中有效的管理是必不可少的“1 ，容错作为分布式系统管理中重要的一部分， 越来越受到人们的重视，成为分布式系统中的一个研究热点。 1 1 研究背景 基于客户n 务器体系结构“3 的分布计算环境通常由客户和服务器两部分组 成，一个服务器为多个客户提供服务。客户服务器体系结构采取请求应答的 分布处理模式，丌发模式a 然简洁，结构易于扩展，能够适应系统资源的物理 分布，实现分却计算环境中各类资源的交互与共享。 随着大规模分布事务处理以及军事抗毁等关键应用的发展，对基于客户n 务器体系结构的分布式系统又提出厂新的挑战。 1 大规模分布式事务处理 在金融、电信、证券、商业以及i n t e r n e t 中，大规模分柿式事务处理l 应用 的发展和业务规模的小断扩大，对分布式系统提出r 新的挑战：方面，要求 扩火系统规模，能够支持更多的在线用户：另一方面，要求应用系统能在单位 时间内响应更多的客户的请求，提高系统的吞吐率。然而传统的客户服务器体 系结构是不能满足这种要求的，随着客户数目的增多，应用规模的扩大，服务 器将成为处理请求的瓶颈。 2 军事抗毁等关键应用 在军事抗毁、金融、电信等关键应用中，如果服务器出现故障，小能j f 常 工作，造成的损失将是巨大的。因此，要求即使系统的服务器出现故障，也不 会影响系统的止常执行。这对系统的可用性提出了很高的要求，然而现有的单 服务器环境无法满足这些要求，当单个服务器失效时，整个系统将会崩溃。 3 多备份数据管理应用 随着数据库应用规模的扩大和网络通信技术的发展，传统的单机数据库系 州北大学t 学硐卜学位论文 统已逐渐向物理多节点环境下的多数据库4 1 发展。越来越多的数据信息被物理 分布在网络的各个节点上，它1 j 互为备份，以支持数据库复杂而高效的奄询处 理能力，并支持对已经存在的高度分布的数据有效处理和快速检索能力，提高 数掘的可用性。然而，如何为客户提供一个透明快捷的查询处理环境，以及实 现各备份数据之州的。致性和数据节点的动态可扩展，是基于客户服务器体系 结构的多备份数据管理应用所面临的新课题。 经过对以上应用的分析，可以发现基于客，r l i 服务器模式的分布式应用在性 能和可用性两方面存在着迫切要求。因此，把冗余服务6 ，即多个互为备 份的服务器，引入到分布式训算环境l 卜| ，构建基于冗余服务的容错算法 【9 j 【1 0 儿】，可以很好的解决以上应用对性能和可用性的要求。 力而，通过增加 数据和计算的冗余度，提高了系统的可用1 | 斗，达到容错要求：兄一方面，多个 冗余服务器并行响应客户的请求，提高了系统的吞吐率。此外，分布式系统中 的多备份数据管理也推动了冗余服务引入到分布计算环境中。 12 研究目标 通过对研究背景的分析，我们确立了研究目标：针对客户服务器体系三层 结构，研究基j 一冗余服务的容错算法，为应用提供高性能、高可用性、可扩展 的分布计算平台。我们定义容错为：在系统部分故障的情移h 能保证客户的 清求在额定的时间内返回l 卜确的结果。如果系统没有响府或没有存额定的时唰 内做出正确的响应，即认为出储。 在性能上，咀提高系统的吞吐率和资源利用率为日标，一方面要求系统能 存中位时间内处理更多客户请求，另一方面要均衡冗余服务负载。在可用性上， 对关键应用提供高可用性支持，可用性被定义为服务器町以被客户访问的概率“。 在可扩展性l 卜，允许冗余服务动态地加入和离开，系统的规模u j - 丰艮据冗余服 务的个数动态改变。 13 研究现状 目前，摹于冗余服务的容错算法大体上分为两类：p r i m a r yb a c k u p 和a c t i v e r e p l i c a t i o n 5 1 。 第1 章绪论 1 pri m ar yb a c k u p 算法”。 在p r i m a r yb a c k u p 算法中，只有一个冗余服务器处在动态状态柬处理客户 的睛求，1 1 1 1 做主服务器：其他的冗余服务器都处在后备状态，小刺客户的请求 进彳处理，叫做备份服务器；当主服务器失效后，通过某种算法从备份服务器 中选择一个作为主服务器。备份服务器的交可- 状态是由 服务器通过一定的策 略来更新的。 因此，在此算法中，所有的请求由一个p r i m a r y 服务器串行执行，当p r i m a r y 服务失效时，再由备份的冗余服务选出一个作为p r i m a r y 服务器来执行请求， 即请求转发，属于时间冗余的容错手段，因此请求的u 向应时唰长，系统的负载 不均衡，很容易造成系统的瓶颈，但它占用的资源较少。 2a c t i v er e p ic a t lo n 算法”l 在a c t i v er e p l i c a t i o n 算法巾，所有的冗余服务器都是主服务器，都处在动态 状态米同时响应客户请求，属于空间冗余的容错手段，因此请求的响应速度快， 但它耗费的系统资源大，而且由于系统的资源有限，兀余服务同时执行所有请 求，从总体上降低了系统的性能。 可见，以上两类算法各有优敏点，为了弥补它们各自的不足，一些算法对 它们进行了权衡改进。 3 r o w a 算法”“1 r o w a ( r e a d o n c e w r i t e a 1 1 ) 算法对请求进行分类，把请求分为读请求和 写请求，读请求不改变冗余服务的状态，写请求改变兀余服务的状态，划读写 请求采用不同的处理方法，对读请求采用读一次算法，对写淆求采用a c t i v e r e p l i c a t i o n 算法，它只是简单地对读写请求进行r 分类处理，只适用丁读频率 较高时的情况，而且降低了读请求的町用性。 4c o o r din a t e c o h er e n c e 算法1 c o o r d i n a t e c o h e r e n c e 算法通过将处理不同类请求的p r i m a r y 服务设定在不 同节点上，咀均衡系统负载，但它没有从根本上克服p r i m a r y 服务的性能和可 用性瓶颔问题。 5 r a w a 算法” 河北大学t 学坝j 。学位论史 r a w a ( r e a d a n y w r i t e a n y ) 算法是基于q u o r u m 的冗余服务容错算法，在 分布式系统中，执行某个请求的冗余服务的集合定义为它的q u o r u m 7j 。r a w a 算法为提高系统的性能，引入r 负载平衡机制，可以根据系统的负载状况动态 的改变请求的q u o r u m ，使请求的q u o r u m 可以定义在1 和j v ( 冗余服务个数) 之间，即在系统中选择一组轻载的冗余服务来响应请求。r a w a 算法采用服务 方决定的广播式负载平衡【l ，通过把请求发送给所自的冗余服务，如果有冗余 服务执行完请求并返回时再把其他冗余服务中的该睛求撒销，以此达到负载 平衡和动态确定请求的q u o r u m 。 图11r a w a 算法框架 具体运行情况如图11 所示，t m ( t a s k m a n a g e r 任务管理者) 求按f i f o 的顺序放入请求队列r e q u e s t q u e u e 中，然后通过组通信 给所有的r s ( r e d u n d a n t s e r v i c e 冗余服务) 。r s 有。定的处理能 否可由本身根据负载状况决定。当r s 收到t m 转发的请求后，名： 则r s 对此请求进行处理，否则，将请求按f i f o 顺序放入r s w a i t i n g q u e u e 叫j 。当r s 处理完淆求后，将结果返回给t m 。t m 果返回给客户，同时以组通信的方式向其他的r s 广播一个撤销请求消息，撤 销其他r s 中己完成的请求。 r a w a 算法中的负载平衡机制由各个r s 存自身来完成，t m 不必进行负载 平衡操作，冈此减轻了t m 的负担，避免t m 成为系统的性能瓶领。但r a w a 算法中的负载平衡机制也有一定的缺陷。 1 1t m 把客j - 请求广播给所有r s ，当结果返回后，义撤销其他r s 中的请 第1 章绪论 求，系统的通信丌销很大，而且部分通信丌销是不必要的，可以避免； 2 ) 虽然r s 町以利用多线程来提高请求的执行速度，但r s 无法跳过一个未 执行的请求去执行后边的请求。总起来看对于请求的执行是串 j 二的，这存分布 式系统中会大大影响系统的性能： 3 ) t m 不加区分的把请求转发给所有r s ，这样当一个r s 重载的时候，再 给其分发请求，势必更加重r s 的负载，因此任务分发具有很大的盲同性。 14 本文工作 针对以l ：各种算法的不足，我们通过在基于三层客户服务器体系结构的冗 余服务r r | 引入主动负载平衡，设计了一个提高冗余月务性能的容错算法，并在 c o r b a 8 平台上进行了实现。主要研究了冗余服务系统中的负载平衡管理机 制、冗余服务+ 的容错算法以及基于c o r b a 平台的系统实现。 1 冗余服务中的主动负载平衡机制和容错结合 主动负载平衡机制( 负载平衡的接收者驱动策略) 【2 0 】是根据系统局部范 围内的一些负载信启、来进行负载平衡操作，具有良好的可护放性，可以很好的 适用于分布式系统的负载平衡调度。它的主要思想为：由轻载的节点主动向任 务管理者申请任务，而不是被动的接收任务管理者分配的任务。主动负载平衡 机制有几个主要优点：( 1 ) 不需要相互交换负载信息；( 2 ) 负载平衡的大部分 工作由轻载节点完成，可以减轻任务管理者的负担避免任务管理者成为系统 瓶颈； 在冗余服务中提高系统可用性的同时，往往降低了系统的性能。因此，如 何存保证冗余服务系统可用性的前提下提高系统的性能，是冗余服务容错算法 研究的一个重点。我们通过在冗余服务系统中引入主动负载平衡机制，把主动 负载平衡机制和冗余服务容错很好地结合，创建了基于动态手动负载平衡的冗 余服务容错算法s r a w ( s o m e r e a d a n y w r i t e ) 。该算法不但提高j ，请求的响 应速度，均衡了系统负载，还具有管理简单有效等特点。 2 基于c o r b a 平台的原型系统实现 我们采用o m g 组织的c o r b a 作为系统的实现平台，c o r b a 是目前主流 的分布对象技术规范，它被世界l 人多数计算机公司利厂商支持；c o r b a 运 9r , j 北大学工学坝士。宁：位诧7 - 用分布对象技术，有效的解决了分布计算环境中资源共享、代码可重川、可移 植以及剥象问互操作问题，为分布式的应用开发提供了强有力的支持。冈此， 遵循c o r b a 标准开发的应用t - 台具有良好的开放性利先进性。2 。 存实现中我们将冗余服务管理框架作为c o r b a 的系统服务实现，提高了 系统的灵活性和可扩展性，叮以动态管理和维护不同服务类型和数f 1 的冗余服 务。 1 5 论文结构 本义共分血章，第一章为绪论，介绍了本文的研究背景、研究同标，并对 相关工作及其不足进行分析，然后简要介绍本文的主要工作。第二章详细介绍 了摹于动态主动负载平衡的冗余服务容错算法，包括系统模犁、负载半衡、容 错策略、一致性维护协议等，并对算法的性能做了理论上的分析。第三章基于 c o r b a 平台，对冗余服务容错算法进行了详细实现，给出了系统实现的对象 模型，总体功能和逻辑流程。第四章构建了系统具体测试实例，对系统的性能 进行了实例测试，并对测试结果进行了分析。第h 章对奉文的工作进行了总结， 并对下一步的工作进行展望。 第2 章罐于动态土动负载平衡的儿采腽务容错算法 第2 章基于动态主动负载平衡的冗余服务容错算法 在分析现有冗余服务容错算法的基础上，本章提出一个基于动态主动负载 平衡的冗余服务容错算法s r a w 。在保证冗余服务系统可用十牛的前提下，为提 高系统的性能在冗余服务中引入了主动负载平衡机制，既提高了请求的响应速 度和系统的吞吐率，均衡了系统负载，又不过多地占用系统资源，而日针对状 态服务，还提出了一致性维护机制，扩大了s r a w 算法的适用范围。 本章首先提出s r a w 算法的设计原则，然后给出算法的系统模型、算法框 架及数据结构：在此基础、js r a w 算法进行了详细描述，最后，对算法的性 能进行了分析。 2 1 算法设计原则 针对现有算法的不足的分析，我们提出s r a w 算法的设计原则。 1 ) s r a w 算法是基于q u o r u m 的冗余服务容错算法。通过将清求的q u o r u m 定义在1 z f i l l ，对a c t i v er e p l i c a t i o n 和p r i m a r yb a c k u p 进行有效的权衡； 2 ) 根据客户请求对可用性要求的量化，确定客广请求的最小q u o r u m ，然 后根据系统的负载状况动态改变客户请求的q u o r u m ，既提高了系统的请求平均 n l a j i | , , z 速度，又能够满足客户可用性的要求，又不过多地，l 用系统资源； 3 ) 基了二主动方式，以一种简单有效的方式实现负载平衡0 2 2 1 ，同时大大减 轻任务管理者的负担：以主动方式有效实现客户淆求的并行执行，并行执行模 型【2 3 简单有效： 4 ) 针对状态服务，提供一致性维护协议，提高算法的适用范围。 2 2 系统模型 算法设计基于以卜的系统模型( 如图21 所示) 。系统基于局域网环境，系统 中有多个相互连接的主机，主机之间可以两两通信，通信基于可靠的异步通信 机制，即消息传递无丢失、无重发、顺序且不被破坏： 河北大学工学硕上学位论文 应用屠 宴观屠 通信屠 图21 s r a w 算法的系统模型 系统中的冗余服务有两种类型：状态服务和无状态服务“，状态服务将服 务的状态封装在内部实现，”j _ 以为用户提供数据和计算服务，例如般的数据 库服务器即属于状态服务。无状态服务只封装了计算能力，只能为请求提供计 算服务，例如r p c 即可认为是无状态服务； 系统中的服务的错误类型为停上= 一等待( f a i l s t o p ) ： 采用面向对象的观点，系统中客户可见的服务被抽象成服务类，服务类山 多个冗余服务实现，冗余服务的实现被定义为服务类的实例，同一服务类的不 同实例的实现可能不同，例如实现平台不同、编程语言不同等等，但必须都继 承相同的服务接口，同- - n 务类的不同实例称为冗余服务。 系统中同- f i r 务类的各个实例驻留在不同主机上，即主机上至多有同服务 类的一个实例，实例对客户透明，能够提供状态服务。 23 算法框架与数据结构 s r a w 算法框架采用a m a ( a d m i n i s t r a t o r _ m a n a g e r a g e n t ) 结构1 ”。a m a 结 构由a d m i n i s t r a t o r ，o m ( o b j e c t - m a n a g e r ) ，h m ( i l o s t m a n a g e r ) ，s a ( s e r v e r a g e n t ) r a ( r e q u e s t a g e n t ) 五q 模块组成( 如图2 2 所示) ，采用a g e n t 2 4 心1 模型以统一 的接口对消息进行处理。 1 全局管理者a d m ins tr a l o r 它的状态集为： s t a t e s e t ：= 其中，o ml i “是a d m i n i s t r a t o r 所管理的服务对象类的信息集合，它包含 笫2 章基于动志主动负载平衡的冗余服务释错算法 了各个服务类的接u 信息咀及当前的实例个数等管理信息；h o s tl i s t 为 a d m i n i s t r a t o r 所管理的主机对象的信息集合，它包含了各个主机的地址信息以 及处理请求的能力等管理信息。 a d m i n i s t r a t o r 通过定期的检测o m 和h m ，璐控系统中实例和主机的运行 状况，a d m i n i s t r a t o r 可以实时地把o m 和h m 的运行状况报告给系统管理员， 可以划o m 和t i m 进行管理，及时发现失效的o m 和h m 刘象，并根据状态信 息对它们进行恢复，因此在本系统中假定o m 和h m 都是健壮( r o b u s t ) 的。 厂 刚“哪盯 1 、。一j 图2 2s r a w 算法的系统框架 2 主机管理者h m 驻留存每个主机节点上，管理主机信息，h i i 的状态集为： h o s t _ l i s t h o s t l d ：= 其厂r | ，h o s t l d 是主机在分布计算环境中的唯一标识：h o s tn a m e 为主机名， h o s ta d d r 为主机的地址，m a xl o a d 为主机的负载闽值，c u r r e n tl o a d 为主机的 当荫负载值；i n s t a n c el i s t 是驻留在该主机上的所有实例的信息。 h m 管理本地的实例刘象，可以监测主机以及主机上的实例对缘的运行状 况，可以确定主机的负载状况以及实例的负载状况。 3 对象管理者0 m 在a m a 框架中，每类服务对象都有一个管理者o m ，o m 的状态集定义 河北大学工学硕| 二学位论文 为： s l a t e s e t ：- 其中，i n s t a n c el i s t 为o m 所管理的实例对象的信息集合，它由各个实例信 息项组成，它的状态集定义为： i n s t a n c e i s t n s t i d 】：= i n s t i d 是实例对象在o m 中的唯一标以：i n s t a n c e a d d r 是实例埘象的地址 信息，i n s a h e es t a t u s 是实例对象的状态( 正常或失效) n e x tr e q u e s t 为实例下 次主动要中清的请求序号。 请求队列r e q u e s r q u e u e 存储客r i 发送给o m 的请求消启、，其中的请求项的 定义为： r e q u e s t q u e u e r e q l d ：2 其中，r e q l d 为请求在r e q u e 州q u e u e 中的唯一标识序号。每个请求项包含 清求的方法名r e q u e s tm e t h o d n a m e ，请求的参数r e q u e s t a ：，a r a m e t e r s ，请求的优 先级r e q u e s t r i o r i t y ，请求的类型，w ( r e a d o rw r i t e ) ，最小冗余度m i n _ q u o r u m ， 可山客户可用性的需求量化得到，m a xq u o r u m 为最大冗余度，表示至多有 m a xq u o r u m 个) 余服务来申请此请求，c u rq u o r u m 为当前的冗余度，表示已 经被e u ，q u o r u m 个冗余服务所申请到，以及返同请求结果的同调代理地址 r e q u e s tc a l l b a c k 。 w r i t pu p d a t el i s t 存储写更新消息，为了提高写请求的执行性能，避免写 请求的重复执行，o m 在接收到写请求的执行结果后生成写更新消息。当其他 实例再次申请此写请求时，只需执行相应的写更新消息即可，而不必重复执行 写请求；w r i t e 叻d a t el i s t 的状态集为： w r i t e 坳d a t el 妇t r e q i d 】：2 二元组表示要把属性a t t r 的状态更新为v a l u e 。 o m 接收到客户请求之后，对请求进行丰j 步处理并按先进先出顺序放入 r e q u e s rq “e “g 中，然后由o m 根据一定的负载平衡机制利容错算法将清求转 发给适当的实例；另外，o m 还管理冗余服务的失效，恢复，创建等等，当某 个冗余服务失效后，o m 可以通过其他实例的状态对失效的实例进行恢复。 4 服务代理s a 兰：坠鳖篓耋堡墼些塑丝塑篓坠一 田 二懑 2 ，d 1 管理域圆 图23o m 虚沣册机制 同一服务类的各个实例与管理它们的o m 对客户透明，它们构成虚对象 ( v i r t u a lo b j e c t ) ：客户通过a d m i n i s l t r a t o r 将请求发送给这些虚对象，但并不感 知由哪个或者哪几个实例对象响应该请求。 通过虚注册机制，可以实现客户对冗余服务的透明访问：o ) o m 将它的地 址信息，如对象引用，以它所管理的服务类标识注册到a d m i n 中；真正的服 务类的实例刑象向o m 注册，将它们的地址和状态信息保存存o m 中，以便 o m 对它们进行管理和维护；客户在访问服务对象时，从a d m i n 中获得相应 的对象引用，但实际上是o m 的地址信息：客户通过该引用埘虚刘象进行访 河北 学j 二学碗士学位论文 问，实际上将请求发给了o m ，由它根据一定的管理和调度策略将清求转发给 服务类的个或多个实例处理。 通过引入虚注册机制，客户对冗余服务的访问实现了四层透明性： 1 ) 地址透明：客户无需存储和维护冗余服务的地址信息，无需知道它们在哪 些节点、哪些主机上； 2 ) 实现透明：客户无需知道请求具体由哪个或者哪几个冗余对象完成，请求 的响应过程刺客p 透明； 3 ) 失效透明：即使有服务对象失效，用户也不需知道，o m 能够自动屏蔽失 效的服务刘象，并对失效对象进行恢复，客户请求仍然能够得到i 卜确结果。 4 ) 配置透明：服务类实例的个数在运行时刻可以动态改变，允许实例动态注 册和注销，客户无需知道服务类的配置。 而日，客户访问虚对象的过程与访问通常服务对象的过程致，例如在基 于c o r b a 标准的分布式系统中，客户无需感知它所访问的对象是含有冗余服 务的虚对象，还是真正的c o r b a 对象，没有破坏分布式标准的开放性。 2 5 算法设计 s r a w 算法分为两部分：动态土动容错和一致性维护。其中动态主动容错 只针对无! 状态服务。为支持状态服务，又提出了一致性维护协议。 25 1 动态主动容错 动态主动容错算法的核心思想是随着o m 负载状况的变化，动态调整o m 中客，。r 请求的q u o r u m ，然后等待至多q u o r u m 个冗余服务的主动中清。由于兀 余服务驻留在主机上，它们轻载与否可由所在主机的h m 来决定。凼此在s r a w 算法中，由冗余服务在轻载日寸主动向o m 申请任务，由此达到负载平衡，同时 大大减轻o m 的管理功能，这样既避免了o m 的管理功能过丁复杂而成为系统 的处理瓶颈，也保证了负载信息收集的简单、实时和高效。 1 负载平衡 负载平衡调度由h m 和s a 通过主动负载平衡的方式实现。 负载索引定义：s r a w 算法中定义_ r 两个负载索引：主机负载索引利实例 负载索引。主机负载定义为： h m l o a d2 厶 其中，为驻留在主机上的服务实例的数量，为实例对象当前的 胎j t y n & q u o u o 的长度。 史例负载定义为： 5 ；a l o a d j f l o a d + x 向一 其叶 ，为实例刈象f f j 曙_ q “p “b 的长度，c ( c 1 ) 为实例负载因子，c 要根掘s a 处理能力来确定。 我们主要以实例对象w a i a n g _ q u e u e 的长度作为主机和实例的负载索 引，具有定的前瞻性。 负载闽值被认为是系统处理能力的极限当系统超过这一闽值时，处理能 力急速下降2 7 】；我们定义实例对象的负载闽值等同于主机的负载闽值 。y t m a x l o a d 。定义： i h m l o a d a 。，m a xl o a dt h e n h o s to v e r l o a d 扩 s a l o a d h o s t m a xl o a dt h e ni n s t a n c eo v e h o a d 通过负载索引和负载阈值的定义可以得到，当主机轻载时，实例司能重 载，因此避免了虽然主机轻载，但实例却重载的情况。 在负载平衡策略中，采用接收者驱动的主动负载平衡算法，当实例对象轻 载时主动向0 m 申请任务，以此达到负载平衡，负载平衡策略简单高效。 2 消息类型 为实现冗余服务的动态主动容错算法，系统定义了8 种消息类型： 1 ) r e q u e s t m e s s a g e ( r e q u e s t s e q ，r e q u e s t m o d e ，m e t h o d n a m e , p a r a m e t e r s , l r e s u l t t y p e ) ：客户向o m 发送或o m 给s a 分发请求，r e q m ；s t s 。q 是o m 为 客户晴求分配的全局标识，r e q u e s tm o d e 为区分读写请求： 2 j n u l l t a s k ( ) ：o m 向s a 的申请返同当前无新任务的消息； 3 ) f r e e r e p o r t ( 1 n 吼a n c e a d d r ) ：s a 向o m 发出的申请任务执行的消息； 4 ) i n q u e r y m e s s a g e ( i n s t a n c e a d d r ) ：s a 1 劬h m 发送的负载查询消息， 河北大学工学硕士学位论文 l n s t a n c e a d d r 为s a 的地址； 5 ) l o a d m e s s a g e ( 1 n s t a n c e l o a d s t a t u s ) ：h m 向s a 发送的负载查询结果， i n s t a n c e l o a d s t a t u s 为重载或轻载标识。 6 ) e x e c u t e d m e s s a g e 0 ：s a 向h m 发送的请求执行结束消息； 7 ) r e s u l t m e s s a g e ( r e q u e s t s e q ，r e s u l t ) ：实例向o m 发送的请求r e q u e s t s e q 的结果； 8 ) r e c e i v e d m e s s a g e ( r e q u e s t s e q ) ：o m 向s a 发送的表示请求r e q u e s t s e q 的 结果已经收到的消息。 3 客户请求q t 1 0r u m 的调整策略 1 ) 当客户请求到达o m 时，o m 根据客户对可用性的需求进行量化，确定 请求的m i nq u o r u m ； 2 ) 由1 。此客户请求目前是最新的，其后没有其他的请求，因此定义客户请 求的m a xq u o r u m 为n ( o m 所管理的所有实例对象的数量) ，计：o m 的 所有实例对象都可以执行此请求，咀达到较高的性能。 3 ) 新到达的客，o 请求要求提供服务，这加重了o m 的负载，因此，u j 以动 态降低先前到达的客广请求的m a xq u o r u m ( 当m a xq u o r u m = m i nq u o r u m 时不再进行调整) ，以预留出系统的宝贵资源来为新到达的 客户请求提供服务，使新到达的请求可以和先前到达的请求并行执行， 以提高系统的性能。 4 动态主动容错算法 1 ) o m 将客户请求按f i f o 顺序放入到o m 的请求队列r e q u e q u e u e 中去， 并对r e q u e s t q u e u e 中的先前到达的客户请求的m a x q u o r u m 进行调整； 同日i j 更新i n s t a n c el i s t 中的n e x tr e q u e s t 项，把n e x tr e q u e s t 项的值是n u l l 的更新为新到达的客户请求。然后等待s a 的主动申请任务消息 f r e e r e p o r t ( i n s t a n c e a d d r ) 的至0 达。 2 ) 在主机轻载的情况下，s a 以? 1 为周期检测i n s t a n c e 负载状况，如果 i n s t a n c e 重载，则s a 不向o m 发送中请任务消息；如果i n s t a n c e 轻载， 则s a 向o m 发送申请任务消启、；如果主机重载，则s a 不申请仟务。 第2 章基于动态主动负载平衡的冗余服务容错算法 3 ) o m 接收到s a 的中请任务消息后，通过查找i n s t a n c el i s t 中孩s a 的 n e x t r e q u e s t 项的值，得到该s a 要申请的客户请求。然后对此客户请求 进行检测，如果此客户请求的c u rq u o r u m m a xq u o r u m ，o m 就把此 请求的c u rq u o r u m 增1 并分配给s a ，同时把o m 叶 的i n s t a n c el i s t 中 陔s a 、的n e x tr e q u e s t 更新为r e q u e s t q u e u e 中下一个请求的地址；如 果此客户请求的c u r q u o r u m = m a xq u o r u m ，则继续向队尾方向检测下 一个请求，直到找到客户请求的c u rq u o r u m m a xq u o r u m 或直到 r e q u e s t q u e u e 队尾。如果找到一个c u r q u o r u m m a xq u o r u m 的请求， 则操作同第步，如果到达r e q u e s tq u e u e 队尾，则o m 向s a 发送 n u l l t a s k ( ) 消息，把o m 中i n s t a n c el i s t 中该s a 的n e x tr e q u e s t 更新为 n u l l ，标识当前无新任务分配给该s a 。 4 ) 当冗余服务执行完客户请求之后，将结果返v 3 l 给o m ，如祟o m 的 r e q u e s tq u e u e 中已经没有此客户请求，则o m 直接丢弃垓返回结果即 可；如果o m 中存在此客户请求，则o m 把接收的结果返回给客户，并 从r e q u e s tq u e u e 中删除此客户请求，同时把i n s t a n c el i s t 中 n e x t r e q u e s t 的值是此客户请求的项更新为r e q u e s tq u e u e 中该客户请 求的下一个客户请求的地址。 2 52 一致l 生准护协议 对于无状态服务，以上算法选择一绢轻载的i n s t a n c e 来执行客户请求，因 此有较高的亓j 用性和较好的响应时间。但对于状态服务，由于要保持各个冗余 服务状态的一致性，因此本文对上述的动态主动容错算法进行了改进：f 1 ) 区 分读请求和写请求，刘读写请求采用不同的处理策略；( 2 ) 为提高写请求的性 能在o m 中增加了w r i t eu p d a t el i s t 。 1 ) 读请求由于1 i 修改服务状态，凼此仍可以采用上述算法。而把。与请求的 l i l i nq u o r u m 固定的定为o m 所管理的所有i n s t a n c e 的个数并且不允许动 态调整，以保证每一个实例都必须执行一次并且只执行次写请求。 2 ) 当实例执行完写请求后，它将结果封装在r e s u l tm e s s a g e 中，同时也把 改变的状态通知给o m ，o m 接收到写请求的结果后，将r e s u l tm e s s a g e 河北大学丁学删l 学位论文 转换成相应的w r i t e u p d a t em e s s a g e 请求消息，按f i f o 顺序送入 w r i t eu p d a t el i s t ，同时把相应的写请求设置为已执行状态。当再有s a 请求此写请求时，o m 则把w r i t eu p d a t el i s t 中相廊的 w r i t e u p d a t e m e s s a g e 更新请求分配给s a ，这样当执行一个已执行的写 请求时，只需对实例状态进行修改，而无需执行整个请求，这可以在很 大程度上提高写请求的性能。 26 性能分析 本章对s r a w 算法、a c t i v er e p l i c a t i o n 算法，p r i m a r yb a c k u p 算法、r o w a 算法以及r a w a 算法的请求平均响应时间和通信丌销进行了比较，尤其对 s r a w 算法和r a w a 算法进行了比较。假定各种算法r r | 冗余服务的个数相同， 因此，各种算法都具有相同的可用性。 2 61 请求平均响应时间 假设系统中的主机数量为k ，它们处理请求的速度分别为p ，见。系 统中有1 1 1 个服务类，各个服务类分别由风( f = 1 ，m ) 个实例来实现。实例的失 效概率为，检测实例失效的时问为，对失效实例进行恢复的时间为。正常 实例执行一个请求的平均时间为，请求中写请求的概率为p ，请求的等待平 均时间为f ，则根据排队论模型，各种算法中，请求的平均响应时间为清求的 服务时间t 。和请求的平均等待时间，之和： r = r 。+ r ( 公式21 ) 而f 。为系统f 常工作的概率厶乘以请求的平均执行时间t 。与系统故障概率再 乘以实例的检测、恢复与执行时f 凸j ( r ，+ f ，+ ie ) 之和，即f 。= _ ，：1 ，。+ ( f ，+ r ，+ r 。) ， 设系统中请求的平均等待队列长度为工，则f 。= ，其中兄为请求的平均到 达率。因此： f _ 矶+ f j ( t ，+ f ，+ f 。) + ( 公式22 ) 假定l 和丑在各种算法中相同，因此根据参考文献 1 6 】的分析