（计算机应用技术专业论文）基于主动复制的负载平衡模型研究与实现.pdf

摘要 随着计算机硬作价格的r 降以及计算机网络的不断发展，将计算任务分布到多个物理主 机上处理，以提高任务计算迎度和降低任务运算成本已经成为一个趋势。这种通过通信线路 将多台计算机互联，共同为刚户提供服务的系统，称之为分布式计算机系统。分布式计算机 系统给用户提供了个丰富的资源集合。分布式计算机系统研究的范围很广，包括：通信网 络、分布式操作系统、分布式数据库、并行科序设计、容错、分布式实时系统等。 建立分布式计算机系统麻州土要有以f 儿个原因：资源共享、提高性能、可靠性、通信、 可扩展性等。本论文土要针对可靠性( 容错) 和提高性能( 负载平衡) 这两方面。主动复制 容错的主要优点在丁提高系统的鲁棒性平缩短戍州的响应时间，负载平衡技术则主要_ q = i 于提 高系统的运行性能。主动复制容错的不足之处在_ 丁当系统未出错时，系统资源存在一定的浪 费，负载平衡技术则不能很好地解决系统山错的情况( 虽然负载平衡技术中的迁移技术可以 提供一定程度的容错能力) 。冈此，若将这两种技术相结合，即当系统没有发生错误时，尽 量让容错绢中的成员执行不同的任务，以提高系统运行效率；当系统发生错误时，帮助系统 屏蔽错误，使得系统能够继续运行，这样不仅可以充分发挥两者各自的优势，而且可以弥补 两者技术上的缺陷。 本论文在以f 儿个方面进行了探索，并取得了一定的创新性研究成果：( 1 ) 在分析基于 主动复制容错技术和负载平衡技术现状的基础上，提出基于主动复制容错技术的负载平衡模 型，井提出了儿种可行的调度方案。该模刑可根据系统的当前负载状况，动态调整容错组数 和组成员关系以满足系统吞吐率雨i 可靠性两方面的要求，具有良好适应性和可扩展性。( 2 ) 在东南犬学已经完成主动复制容错技术的基础之上，实现基丁主动复制容错技术的负载平衡 的结构模型中的一种任务调度方案。( 3 ) 深入分析容错组成员计算能力、任务分配策略、容 错组冗余度利任务刨达频度对系统性能平| l 任务公平性等方面的影响。 本论文研究1 作受剑国家岛然科学基金项目“容错c o r b a 系统及其关键技术研究”( 项 目编号：6 0 2 7 3 0 3 8 ) 的资助。 关键词：容错：负载平衡；层次模刑；调度结构 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 fc o r n p u t e rn e t w o r kt e c ha n dt h ed e p r e c i a t i o no fh a r d w a r e ，i th a s b e e nat r e n dt od i s t r i b u t ec o m p l e xc o m p u t i n gt a s k st om a n yp h y s i c a lh o s t st oi m p r o v ec o m p u t i n g s p e e da n ds a v ec o m p u t i n gc o s t ss u c has y s t e mi sc a l l e da sd i s t r i b u t e dc o m p u t i n gs y s t e mr d c s ) m a n yc o m p u t e r sa r ec o n n e c t e db yc o m m u n i c a t i o nl i n k ss e r v i n gu s e r sa s as i n g l ec o m p u t e ld c s p r o v i d e su s e r sr i c hr e s o u r c e s m a n yt o p i c s i nd c sa r es t u d i e dw i d e l ys u c ha sc o m m u n i c a t e n e t w o r k ，d i s t r i b u t e do p e r a t i o ns y s t e m ，d i s t r i b u t e dd a t a b a s e ，p a r a l l e lp r o g r a md e s i g n ，f a u l t t o l e r a n c ea n dd i s _ c r i b u t e dr e a l t i m es y s t e m ，e t c t h e r ea r es e v e r a lr e a s o n st ob u i l dad i s t r i b u t e da p p l i c a t i o n ：r e s o u r c es h a r i n g ，b e t t e rp e r f o r m a n c e ， r e l i a b i l i t y , c o m m u n i c a t i o n ，f l e x i b i l i t y , e t c t h ep a p e rf o c u s e so nr e l i a b i l i t y ( f a u l t - t o l e r a n c e ) a n d p e r f o r m a n c e ( 1 0 a d b a l a n c i n g ) a c t i v er e p l i c a t i o nc a ni m p r o v es y s t e mr o b u s ta n dr e d u c er e s p o n s e t i m ew h i l el o a db a l a n c i n gi m p r o v e ss y s t e mp e r f o r m a n c e h o w e v e ri t i so b s e r v e dt h a tr e d u n d a n t r e s o o r c e sa r ew a s t e di naf a u l tt o l e r a n ts y s t e mw h e ni tr u n ss m o o t h l y ( n of a u l t ) w h a t sm o r e ，l o a d b a l a n c i n ga r ev u l n e r a b l ew h e nas y s t e mf a u l to c c u r s a c t i v er e p l i c a t i o nf a u l t t o l e r a n c ea n dl o a d b a l a n c i n gc a nc o m p l e m e n te a c ho t h e r h e n c et h ec o m b i n a t i o no f t h e s et w ot e c h n o l o g i e si m p r o v e s b o t hr o b u s t n e s sa n de f f i c i e n c yi nd i s t r i b u t e ds y s t e m s t h et h e s i ss t u d i e so nt h ec o m b i n a t i o no ff a u l tt o l e r a n c ew i t ha c t i v er e p l i c a t i o na n dl o a db a l a n c i n g i ta c h i e v e ss o m ec r e a t i v er e s u l t s f i r s t l y , a f t e ra n a l y z i n gt h es t a t u sq u oo fa c t i v er e p l i c a t i o n f a u l t - t o l e r a n c ea n dl o a db a l a n c i n gt e c h n o l o g i e s ，t h et h e s i sp r o p o s e sal o a d b a l a n c i n gm o d e lb a s e d o i la c t i v er e p l i c a t i o nf a u l t - t o l e r a n c e ，f o i l o w e db yah l e r a r c h i c a ja r c h i t e c t u r ea n dt h r e ea v a i l a b l e t y p e so ft a s ks c h e d u l i n gs t r u c t u r et h em o d e li sa b l et oa d j u s tf a u l tt o l e r a n tg r o u p sa n dg r o u p m e m b e r s h i pr e l a t i o n sd y n a m i c a l l ya c c o r d i n gt os y s t e mr e a l t i m el o a d i n gi no r d e rt os a r i s r ys y s t e m t h r o u g h p u ta n dr e l i a b i l i t yr e q u i r e m e n t s e c o n d l y , b a s e do nf a u l tt o l e r a n ts y s t e mw i t ha c t i v e r e p l i c a t i o na c c o m p l i s h e db ys e u ，t h et h e s i se n h a n c e st h es y s t e mw i t hl o a db a l a n c i n gs u p p o r t i n g c e n t r a l c o n t r o lt a s k s c h e d u l i n g t h i r d l y , t h et h e s i sa n a l y z e st h ee f f e c t so fg r o u pm e m b e r c o m p u t i n ga b i l i t y , t a s kd i s t r i b u t i n gp o l i c y , r e d u n d a n c yo ff a u l tg r o u pa n dt a s ka r r i v a lf r e q u e n c yo n s y s t e mp e r f o r m a o c ea n df a i r n e s si n d e p t h t h ep a p e ri ss u p p o r t e db yn a t u r a ls c i e n c ef o u n d a t i o nc h i n ap r o j e c t f a u l tt o l e r a n tc o r b aa n d i t sk e yt e c h n i q u e s ”( g r a n tn o ：6 0 2 7 3 0 3 8 ) k e y w o r d s ：f a u l t 。t o l e r a n c e ；l o a d b a l a n c i n g ；h i e r a r c h i c a lm o d e l ；t a s ks c h e d u l i n g 图2 1 ： 图2 2 ； 图2 3 ： 图2 4 ： 图2 5 ： 幽2 - 6 ： 图2 7 ： 图2 8 ： 图3 1 ： 图3 2 ： 图3 - 3 ： 圈3 - 4 ： 图3 5 ： 图3 - 6 ： 幽3 7 ： 幽3 8 ： 图4 - i ； 图4 2 ： 图5 1 ： 图5 2 ： 图5 - 3 ： 图5 4 ： 图5 - 5 ： 图5 - 6 ： 论文插图索引 基于主动复制容错技术的负载平衡模型结构 组件模型 负载监视器的两种配置策略 负载平衡层动态交互过群 容错层动态交互过程 集中控制方式 容错组协调方式 容错组问协调方式 容错纲链 容错组链的改进 容错组链的进一步改进， 容错主流程s d l 倒 重新启动过科s d l 幽 任务调度器发起组管理流科s d l 圈 处理加入组请求s d l 陶 失败检测器s d l 图 负载平衡层系统实现的主要类及其关系 容错层系统实现的主要类及其关系 测试用例1 逻辑关系幽 主动复制窬错系统及其改进系统的性能比较图 负载平衡实现系统的性能测试i 鳘1 容错组管理对负载平衡的影岣测试图 m a xp e r f o r m 中各服务器处理请求数图 不同容错组管理频率对系统性能的影响 v i ij 7 9 m m u 他他b m m旧如甜丝”如拍”媳” 东南大学学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得 的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含 其他人已经发表或撰写过的研究成果，也不包含为获得东南大学或其它教育机构 的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均 己在论文中作了明确的说明并表示了谢意。 研究生签名：型堇盘 e t 期：盘丛：蚂哆 东南大学学位论文使用授权声明 东南大学、中国科学技术信息研究所、国家图书馆有权保留本人所送交学位 论文的复印件和电子文档，可以采用影印、缩印或其他复制手段保存论文。本人 电子文档的内容和纸质论文的内容相一致。除在保密期内的保密论文外，允许论 文被查阅和借阅，可以公布( 包括刊登) 论文的全部或部分内容。论文的公布( 包 括刊登) 授权东南大学研究生院办理。 研究生签名：型笔。睑 导师签名： i i i 望白 期：幽d ；吗 第一章绪论 1 。1 引言 第一章绪论 随着信息技术的发展，人们的生产和生活越来越依赖于计算机的使用。但是，现实的计 算机系统并不完全尽人意。一方面，计算机的便件、软件在实际运行过程中并非完全可靠， 出错后可能造成巨大的损失；另一方面，需求的增k 导致了人耵j 对计算机性能的更高要求， 而计算机的不断升级不仅仅耗费了人鼍资金，同时也可能造成资源的浪费。因此，如何提高 系统运行的可靠一眭及性能成为研究的热点。分布计算技术是解决这一问题的有效方法之一。 利j l = j 分布计算中的主动复制容错技术可以解决硬件雨l 软件出错问题，分布计算中的负载平衡 技术则可以很好地提高系统的性能。主动复制容错技术是将多个服务器组成一个组，组中的 每个成员同时运行相同的任务。如果某个成员火效或者不是人量成员同时失效时，其他的结 点还能继续运行完成任务，不影响系统的止常运行。负载平衡技术是避免让过多的任务在同 一个服务器上同时运行从而提高系统运行性能。 主动复制容错的主要优点在丁提高系统的鲁棒性和缩短应用的响应时间”j ，负载平衡技 术则主要用于提高系统的运行性能。土动复制容错的不足之处在于当系统未出错时，系统资 源存在一定的浪费，负载平衡技术则不能很好地解决系统出错的情况( 负载平衡技术中的迁 移技术可以提供一定程度的容错能力) 。冈此，若将这两种技术相结合，即当系统没有发生 错误时，尽量让容错组中的成员执行不同的任务，以提高系统运行效率；当系统发生错误时， 帮助系统屏i 救错误，使得系统能够继续运行，这样不仅可以充分地发挥两者各自的优势，而 且可以弥补两者技术上的缺陷。 1 2 容错技术的研究现状 容错问题在理论利应用上都得剑了j “泛的研究。现实生活中有许多关键任务( _ 下作) 不 能出错，或者一日山错就要付山很人的代价。例如，军事指挥系统、航空管制系统、银行结 算系统尊等。但在这个高度信息化的时代，计算机硬什雨i 软件并不完全可靠。如何保证系统 在出错的情况下仍然能止常运行是个很重要的问题。容错问题的研究就是在试图解决这一 问题。目前容错理论主要灯结为对异步环境下一致性( c o n s e n s u s ) 问题的研究f “。 1 2 1 一致性问题的定义 一致性问题一般可定义为“一钥预先确定的进群p 1 ，p 2 ，p n ，每一个进程提山一个建 议值v i ，最终必须共同认可同一个值” 2 1 。一致性问题的解扶方法必须满足以一f j l 个性质： ( i ) 可终结性：每一个正确的进科最终决定一个值； ( 2 有效性：如果某一进样决定值为v ，则v 是由某些进群提出的i ( 3 ) 一致性：任意两个止确进科的决定值相同( 所有进_ f ! f ! 决定相同的值) 。 如果将( 3 ) 的条什增强为任意两个进科的决定值相同，那么就称之为统一一致性 ( u n i f o i mc o n s e n s u s ) 问题。 东商火学碳j 擘位论文 1 2 2 容错问题和一致性问题的关系 一致性问题不仅是分布式计算舶一个基础理论问题p j ，该闻蔻的解决方法，即一致性 协议，也是建立实际容错虑刖系统的重要方法。异步分布式系统中存在着许多不确定因素 ( 如异步、通信链路 l l 进烈火教等) ，一致性协议提供了一种方法使得系统中的每一个正确 进程能够使用同一系统视图。一q 一致性问题得到解决，分布式系统中的容错问题就可以 得到解决。文献 3 】指“5 ，可以利州一致性协议方便地解决一系列的容错协议问题，如原子 广播、组成员、全序多播笛。另外文献f 2 】指出原子j 播问题和l 一致性问题在异步分布式 系统中是等价问题。 1 2 3f l p 定理 异步环境r 的致性问题住8 0 年代初得剑了j “泛的研究”j 。在1 9 8 5 年j f i s c h e r 等 发表了著名的“不可能理论”简称f l p 定理，指出了一个自然而又重要的问题：容 错协作计算不可能在一个完全异步的计算模型中解决，即不存在一个完全异步一致性 协议能够容忍即使是一个进程未宣告的失效。因为，在完全异步环境下，没有方法判 断这个进程是运行太慢还是已经失败。1 9 9 6 年c h a n d r a & t o u g e 提出不可靠的错误检测 器方法1 2 j ，对一致性问题模型进行扩充，提出辆以“不可靠错误检测器”( u n r e l i a b l ef a i l u r e d e t e c t o r s ) ，可以简沾地解决一致性问题，升在理论上进行了证明。在解决容错问题的理论 研究上向前迈进了人步，但是离真止实剐的窬错问题解决方法还存在一定的距离。 1 2 4 一致性协议 对一致性协议的研究主要集中在随机算法瞳部分同步算法【7 捌和异步算法f 2 9 1 0 l 解决 方法等儿个方面。一f 面简要介耋“部分同步算法和异步环境下不可靠的错误检测器方法。 1 2 4 1 部分同步算法 f l p 定理提山完全异步系统不能保证一致性，但并没有对实际应用中能实现到何种程 度作更多的探讨。如果对网络传输羽l 进程运行作出时间上更乐观的假设就可以解决一致性 问题。其中d o l e v 7 - s l 等对此作了深入的分析，他h j 定义了一系列的系统同步或异步的参数， 来研究在什么情况f 解次一致性问题是可能的。这些参数分为以卜几个方面( u ，f 是指该 参数值对解决c o n s e n s u s 问题是更困难还是更容易) ( 1 ) 进程可能是f u ) 同步的或者是( f ) 异步的。进程是同步的当且仅当存在一个常数s = 1 ， 对任意进程执行s 十i 步后，每一个进程至少要执行一步。 ( 2 ) 通信延迟时间可能是( u ) 没有上限的或( f ) 有上限的。延迟是有上界的当且仅任一进程 发出的消息可以在1 实时步山到达目的地。其中t 是可以预先确定的。 ( 3 ) 滇息可能是( f ) 有序的或肴是( u ) 无序的。消息是有序的当旦仅当如果进程p 在t l 时瓤 发送消息m 1 至进程r ，q 往t 2 时刻发送m 2 至r ，t 2 t l ，那么r 先收到i t l l 。 ( 4 ) 传输机制可以是( u ) 点对点的或者是( f ) 广播。传输机制是点到点的指进程可以在一原 子步内至多给另一进程发送一条消息。广播是指一个进程可以在一原子步内给所有进程发 送一条消息。 ( 5 ) 同时收发。分为进程在一原子步内( u ) 不能同时接受和发送消息及( f ) 可以同时接受和 2 堡二! 竺堡 发送消息两种情况。 由此得出一致性问题可以获得解决方案的四种情况为： ( 1 ) 同步进程并且通信直正迟有上限； ( 2 ) 同步进群并且消息是有序的； ( 3 ) 广播传输机制升且消息是有序的； ( 4 ) 通信延迟有上限、厂- 捅传输机制井且可以原子步肉收发。 1 242 不可靠的错误检测器方法( c h a n d r a t o u g e 算法) 虽然文献 7 提出了怎样的一致性问题是可解的，但真正应用起来还是很困难。c h a n d r a t o u g e 在1 9 9 6 年发表了文献f 2 】，对一致性问题模型进行扩充，提出辅以“不可靠错误检 测器”( u n r e l i a b l ef a i l u r ed e t e c t o r s ) ，可以简洁地解决一致性问题。 不可靠的错误检测器是一个“智着”，它根据其他进牲的行为为本地进程提供其他进程 是否失效的信息。这些信息从本质上来讲是不可靠的。但为了有厢，错误检测器要满足两 个属性： ( 1 ) 完全性要求错误检测器最终怀疑所有实际上火败的进程。 a 强完全性：最终每一个，火败的进群都持续被每一个止确的进程怀疑 b 弱完全性：最终每一个失败的进程都持续被一些正确的进程怀疑。 ( 2 ) 精确性划限定了错误检洲器可以犯的错误类型。 a ，强精确性：任意进稃在火败之前都不会被其他进樱所怀疑。 b ，弱精确性：有一些止确的进牲从来没有被怀疑过。 c 最终强精确性；存在某一时刻在这之后正确的进程不会被任意正确的进程所怀疑。 d 晟终弱精确性：存在某一时刻，在这之后一些正确的进程不会被任意正确进程所怀疑。 因此，八种类型的错误检测器定义如表l 一1 所示。 精确性 完整性 强弱最终强最终弱 强 p sps 弱 q w q w 表卜i ：错误检测器类耻 c h a n d r a t o u g e 证明了强完全性和弱完全性的四类错误检测器实际上是等价的，因此 只要研究p ，s ，p ，s 就可以了。 其中有儿个重要的结论如。f ： ( 1 ) s 错误检测器可以解决异步一致性问题，由丁s 和w 等价，所以w 也可以解决 异步一致性问题，而p 的检测错误的能力强丁s ，所以p 也可以解决异步一致性问题，同 理o 也可以。 ( 2 ) o s 错误检测器是解决一致性问题最弱的错误检测器，且要求大部分的进程正确 i 9 。 ( 3 ) 利婀不可靠的错误检测器，广泛一致性问题帚i 一致性问题是等价的l t o l 。 ( 4 ) 基- 丁s 实现的算法当条仆属性不满足时可能失去活性，但不会失去安全性。即有 可能进程之间相互怀疑而作不山决定，但可以保证一口做出决定，一定满足一致性协议的 三个条件。 ( 5 ) o s 中的强完全性属性可以实现，但擐终弱精确性属性则不能保证。如果采用超 时机制来实现错误检测器，那么超时的时间设定为多长是关键。超时时间设定太跃，进程 3 东南人学坝l 。学位论文 间达到一致的时间可能很 王= ；超时时间设定太短，进程间可能相互怀疑而达不成一致。 因此，不可靠错误检测机制并不是否定了f l p 定理，其本质上也是对完全异步模型增 加辅助机制，将时间因素隐含于简沾的模型中了。 1 2 5 容错系统的软件实现 没有资源冗余就不可能实现容错l ，因此容错技术钓实现离不开系统硬件和软件的冗 余。软件实现容错多采_ h j 复制的方法。复制技术主要有主从备份复制和主动复制两种方法 1 1 2 1 。主动复制披术要复制关键服务器。同一服务器的所有复本构成了该服务器的容错组。 这些关键服务器的复本同时运行，它们都接收客户的请求，执行请求操作，并对客户发出 请求响应。一旦有复本发生错误，只要有足够多的复本在正常f 作，系统仍正常运行。而 主从备份复制方法只有士服务器接收客户的请求，执行请求操作，并对客户发出请求响应， 同时将执行结果复制剑每一个复本上。 1 2 6 容错技术的应用 容错技术得到广泛的麻川，其中包括s i f t 系统i ”j 、s t a t em a c h i n e st 1 4 l 、i s i s ( 现已升级 为h o r u s ) 系统l l ”1 、p s y n c 系统i | “等，但这些系统不能适应任务请求负载的动态变化， 在系统米出错时资源没有充分利用。 软什容错主要完成复本之间任务请求的全序化及原子性质，存在如何将容错技术运用到 现实应用的问题。c o r b a l 2 3 分布计算技术是o m g 组织基于众多开放系统平台厂商提交的分 布对象互操作内容的基础上制定的公共对象请求代理体系规范，具有模型完接、先进、独立 于系统平台和开发语言被支持程度j “泛的特点，己逐渐成为分布计算技术的标准。 o r b u s 0 8 1 系统是由东南入学自主开发的、遵循c o r b a 规范的、面向对象的分布式系统开 发与应用平台。提供了一个开放的、面向对象的分布计算环境。其中o r b u s l 1 版本系统中的 容错服务能够屏敝主机崩溃剌消息丢火错误4 ”。本论文在实现上将容错技术作为相对独立的 组件与0 r b u s * i 结合，简单米讲，即容错组件从o r b 核心获得请求后，再进行全序化，然后转 交给o r b 核心。 1 3 负载平衡技术的研究现状 人们在研究分布式系统时，就注意到了这样一个问题：在一个由网络连接起来的多计 算机环境中，在某一时刻，些计算机的负载比较重，而另外一些计算机的负载却比较轻。 平衡各计算机之间豹负载是任务分配与调度的个主要目标，它能够提高整个系统的性能。 为了改善系统的性能，通过在多台计算机之间台理地分配负载，使各台计算机的负载 基本均衡，这种计算能力共享的形式，通常被称为负载平衡或负载共享。一般来说，负载 平衡要达到的目标是使再台计算机之间的负载基本均衡而负载共享意味着只是简单的负 载的重新分配【l 。 负载平衡理论研究主要集中丁静态和动态负载平衡研究。静态负载平衡策略通常基于 系统的一般行为决定；任务转移独立丁当前系统的实际状态。而动态负载平衡策略则根据 系统的实际状态做山任务转移的决定。动态负载平衡策略比静态负载平衡策略效率更高， 但计算代价也更火”。目前j “泛使州的群集系统主要运用负载平衡技术来解决问题。但负 4 第一章绪论 载平衡系统中仍然存在任务分配结点平f 任务处理结点的单点失效闷题。 1 。4 本论文的主要研究内容 由于容错和负载平衡问题白身的复杂性，将窑错和负载平衡结合起来的研究很少，目 前基本局限于前端舣机备份接收客户请求然斤转发给后端群集系统处理的方法口”，不能 适应负载动态变化雨i 容错两方面的要求。本论文要解狄基丁主动复制容错技术的负载平衡 问题的难点表现在以f j d 个方面： ( 1 ) 基于容错绸的负载平衡调度1 f 常复杂，不仅要研究任务调度策略的影响，还要研 究由于容错组中不同成员不同计算能力所带来的影响。基于容错组的任务调度是一个全新 的研究领域： ( 2 ) 由于容错服务与负载平衡服务的着重点不同，两者实现的目标上存在差异。本论 文将研究容错组的冗余度在调整两个服务日标上所产生的作用，并在维持系统一致性的前 提下，提出支持容错组的动态变化的方法： ( 3 ) 分布式算法设计。不同丁集中式系统，分布式系统中的计算机没有统一的时钟， 每一台计算机都没有全局视图，只能依靠局部的信息来做决定。 针对基于主动复制窬错技术的负载平衡问题的难点本论文在以。f j l 个方面探索； ( 1 ) 建立基丁主动复制窬错技术的负载平衡模型，并提出j l ；l 十可行的容错组的负载平 衡调度方案。 ( 2 ) 将上述模型设计为c o r b a 环境f 的中间件形式，保证系统对用户的透明性，并 分析模型组件设计及动态交互序列。 ( 3 ) 改进东南入学已经完成的c o r b a 平台o r b u s l1 和土动复制容错系统，实现 了集中式调度的任务调度方案，并对结果作了深入的分析。 本论文的主要贡献是： ( 1 ) 在分析现状的基础上，提山了基丁土动复制容错技术的负载平衡模型，并提山了 几种可行的调度方案。该模型可根据系统的当前负载状况，动态调整容错组数和组成员关 系，以满足系统吞吐率和可靠性两方面的要求，具有良好适应性和可扩展性。 ( 2 ) 在东南大学已经完成主动复制容错技术的基础之上，实现基于主动复制容错技术 的负载平衡的结构模型中的一种任务调度方案。 ( 3 ) 深入分析容错编成员计算能力、任务分配策略、容错组冗余度和任务到达频度对 系统性能和任务公平性等方面的影响。 据我们所知，目前没有关丁士动复制容错技术的负载平衡结构模型及其实现的公开研 究论文。 1 5 论文的组成 本论文的其他组成部分如_ 卜：第二章研究基丁主动复制容错技术的负载平衡模型，第 三章分析负载平衡模型的实现方法，第四章为系统实现，第五章针对负载平衡模型实现系 统进行测试和结果分析，最后为总结羽l 进一步的 ：作。 东南人学母! i j 学位论文 2 1 系统模型 第二章模型研究 分布式系统可简单定义为“一组确定的主机和进狂为完成某一任务而形成的系统”。本 论文系统模型建立在异步环境f 。异步指( 1 ) 进科之间的消息传递时间没有上限；( 2 ) 进 程执行每一步的时间也没有上限，也就是说，对时间没有作任何假设。异步分布式系统模型 具有( 1 ) 语义简单：( 2 ) 建立在这种模删上的府用程序易于移植的优点，而系统负载的变 化和不确定性是异步的米源。 考虑异步分布式系统由一组预先确定的处理器组成， q = f p ，p 2 ，以) ( f = l ，2 ， ) 。任意两个处理器之间有链路连接，处理器之间只能依靠 相互传递消息进行通信。处理器间消息的传递延时羽i 处理器每执行一步所需的时间都没有上 限。始终按照计算规则进行1 作的处理器称之为正确的处理器：否则，称之为出错的处理器。 出错处理器遵循失败停l r 模型( 这里不考虑b y z a n t i n e 失败) ，即该处理器不再参与以后的 任何计算活动。 每一个处理器p i 有一个本地失败检测模块b ，其中维护了一张它所怀疑的已经失败的 - 处理器的列表。失败检测器抽象为两个性质，完整性和准确性。假设失败检测器满足0 s 条 件，它保证( 1 ) 强完整性( 最终每一个失败的处理器被每一个正确的处理器怀疑) ( 2 ) 屉 终弱精确性( 最终有一个进科将不会被任一正确的进程怀疑) 。 系统模型的假设还有： ( 1 ) q 中犬部分处理器是正确的处理器。这里火部分是指多t - lh 21 个处理器( 其中 n = 蚓) 。 ( 2 ) 处理器之间的链路具有均匀丢火性质。丢火的消息经过重传最终可到达目的地。 假设系统要执行的任务为不可抢，! i 的独立的事务f 1 ，t 2 ，t m ( m = o ) ，每一个独立的事 务刷一个五元组表示， 即气弘艄p 妇叫簿捌翻啤， 其中 c t m i ，m e m i ，c r i t i a 2 l l e v e l i ，s t a r t t i m e i ，砌呜分州表示预估c p u 占用率，预估内存开销( k b ) ， 事务关键度( 重要性程度参数) ，枣务开始时间，事务结束时间。任务调度模块采用动态负 载平衡调度策略将任务分配到箨容错组系统执行，但不考虑任务迁移的情况。 为降低问题的复杂性假设请求与状态无关，即一个任务的初始执行状态不依赖于前 次任务的执行。 6 筘一章模型研究 2 2 基于主动复制容错技术的负载平衡模型 基于主动复制容错技术的负载平衡模型结构白f 而上分为三个层次，网络层、容错层和 负载平衡层。模型结构如图2 一l 所示。其中，容错层包括容错组成员管理和容错一致性管理 两个部分，负载平衡层包括窬错绸管理和任务调度两个部分。容错层主要完成两方面的功能： 容错一致性管理羽 彝错鲡成员管理。容错一致性管理用于保证容错组成员执行请求的全序性 和原子性，而容错组成员管理则负责同一窬错组山组成员的加入、退出、协调者选举等二作。 东南火学已经完成土动复制容错层的功能口2 1 。本论文将在对主动复制容错进行改进的基础 上，讨论负载平衡层的问题。 图2 1 ：基于主动复制容错技术的负载平衡模型结构 在本模刑r ，一个任务的典! 运行过程如r ：4 壬y r t f 经接口( 1 ) 向系统发出请求处理 任务调度层通过接口( 5 ) 布淘当前窬错组信息，并根据各容错组的负载状态通过接口( 3 ) 将 转发给某一容错组处理，同一容错纽中的成员依靠接口( 4 ) 和接口( 8 ) 进行交互，组成 员的状态通过接口( 6 ) 进行维护，处理结果经由接口( 3 ) g l l ( 2 ) 返回。 2 2 1 容错组成员管理 容错组成员管理完成组成员加入管理和编成员的退山管理一r 作。当处理器进程如请 求加入容错组，齐错组9 1 将当前执行的所有任务序列复制给如，同步后形成新的容错 组9 1 。 东南人学砸j 学位论文 2 2 2 容错一致性管理 同一容错组中的成员需要保持致性，即要满足： ( 1 ) 全序性：如果同一容错组中有成员处理器( 即复制服务器) p 剃p i p j 执行请求x 在 请求y 之前，那么p j 也是先执行请求x ，再执行请求y ： ( 2 ) 原子性：如果察错组中的成员处理器协执行了请求x ，则该容错组中的所有正确处理 器都执行了请求x 。 容错致性管理问题在异步环境下，理论上可以采用c h a n d r a ，t o u e g 算法加以解决吐 2 2 3 容错组管理 容错组管理主要完成容错组的生成、分裂、合并和删除，以容错组为操作单位进行管理。 每一个处理器进程p f 上保存着各容错绸演进的历史序列a 矿：，x 。，称为p f 上第x 个组 视图。矿：是p f 上的初始绸视幽。如果r ；是p f 上最后的日视图，则y ；称为当前组视图。 ( 1 ) 组生成：初始时，所有处理器进程n ，p 2 ，见构成个容错组，冈此， 矿：= g l ， g l2 p l ，p 2 ，- ，p 。) 。 ( 2 ) 组分裂：若容错组管理决定将容错组9 1 分裂，形成，个r 1 z 力) 新的容错组 研，9 2 r ，g l ，新容错组旬继续执行旧容错组未完成的任务，新容错组9 2 ，句进入初始状 态，等待任务调度。此时，当前组视幽更新为矿；2 g l ，9 2 ，g f ) ，每一个容错组当前成 ， 员数为”y 1 y ，2 疗 v = l ( 3 ) 组合并：若容错兰同管理决定k 个容错组9 1 ，9 2 一- ，g k ，每个组成员数为聊少，合并为 个大的容错组9 1 ，则确定其中的一个容错组9 1 为主容错组，其他容错组9 2 一，g 博加入 g l ，更新当前组视图。在台了f 之前，容错纽9 2 ，g k 不雨接收新的任务请求，将现有的任 8 第一章模型研究 k 务执彳亍完旆加入新的容错绸9 1 溶错组9 1 的组盛员数”1 2 叠1 m y 0 厶并之后原来的吼 组将其执行的任务复制到9 2 ，g k 组成员中。 ( 4 ) 组删除：n g - - g * 彗f h 的所有组成员失败或加入另一个弃错组，则删除原有容错组。 2 3 负载平衡层的组件模型 为了进步说明基丁主动复制容错技术的负载平衡模型，本节将对该模型给出基于组件 模型的描述。 2 3 1 负载平衡层的组件及相关服务 图2 - 2 描述了c o r b a 环境f ，模型中负载平衡层的组件及相关服务的构成情况。 图2 - 2 ：组件模型 负载平衡层上土要 h i i 的功能如f ： ( 1 ) t a s k s c h e d u l e r ：主要负责客户请求任务的接收和l 调度( 经过本地p o a o r b ) 。 ( 2 ) s e r v e r g m u p m a n a g e r ：容错组管理主要完成容错组的生成、分裂、合并和删除，以容错组 为操作单位进行管理。 ( 3 ) f t c o n s e n s u s ：同一容错组中的成员需要保持一致性，即要满足全序性，原子性两个问题。 容错一致性管理问题在异步环境一f ，理论上可以采用c h a n d r a - t o u e g 算法加以解决吼 ( 4 ) g r o u p v i e w s y n c h r o n y ：容错组成员管理负责组成员加入管理年i i 组成员的退出管理保证 同一容错组成员的视图同步。 另外。还有儿个重要的辅助组1 ，| ： 9 东南人学o i d ：学位论殳 ( 5 ) f a i l u r e d c t e c t o r ：一般容错统成员j 孺ia ma l i v e 消息米维持组成员之间的通信，组成员利 用超时( t i m e o u t ) 机制共同决定某一组成员是否火效。 ( 6 ) l o a d m o n i t o r ：负载监视器一方面监视容错组成员的负载信息，另一方面向负载平衡层报 告本地负载信息，雨有响应l o a d a n a l y z e r 的负载信息请求。 如图2 - 3 所示l o a d m o n i t o r 可配置为以f 两种实现方式：一种是“拉”机制。在这种 方式下。l o a d a n a l y z e r 可根据需要及时奇啕复本( r e p l i c a ) 的负载状况，也就是从l o a d m o n i t o r “拉”周信息。另一种是“推”机制。在这种方式f ，l o a d m o n i t o r 可主动向l o a d a n a l y z e r 报告复本的负载状况。 ”拉”自城9 图2 - 3 负载监视器的两种配置策略 ( 7 ) l o a d a n a l y z e r ：动态负载平衡方式f ，在分析当然各容错组的负载信息厢，该组件为 t a s k s c h e d u l e r 的任务调度决策提供支持，以狄定f 一个客户请求由哪一个容错组执行。 ( 8 ) t o t a l o r d e r c o m p u t a t i o n ：全序计算组什土要为f t c o n s e n s u s 计算出同一容错组组成员均 认可的客户请求执行序列。 2 3 2 动态交互过程 从客户端发起请求到容错组复本返同响应，主要经过了负载平衡层的任务分配和释错层 的任务处理两部分。 1 负载平衡层交互过程 q 苴锄h 出叠h 世量盥匹雌 【h “i 1 ：”“j e - 出l 2 l 脚l - l 3 掣下? ” 7 f q 崩日 ，自m i i l q m 掣4 黑j 图2 - 4 ：负载平衡层动态交互过程 如图2 4 所示，负载平衡层的交互过程如卜，： ( 1 ) 客户请求经过本地o r b 向t a s k s c h e d u l e r 发起调片j 请求，这对客户来讲是透明的。 ( 2 ) t a s k s c h e d u l e r 将请求s e r v e r g r o u p s m a n a g e r ，褒询当前各容错组的组信息。 1 0 国目 竺 删旺 一 【 谬 第二章模型研究 ( 3 ) t a s k s c h e d t d e r 利川l o a d a n a l y z e r 分析务容借组的负载情况以选择合适的容错组。 ( 4 ) l o a d m o n i t o r 动态监测复本的负载情况，l o a d a n a l y z e r 请求查询该信息( “拉”机制) 。 ( 5 ) l o a d a n a l y z e r 在收集剑复本的负载信息后，分析复本是否负载过重。 ( 6 ) l o a d m o n i t o r 通过l o a d p r o x y 主动报告复本的负载情况( “推”机制) 。 ( 7 ) 在完成负载分析后，t a s k s c h e d u l e r 选择容错组，将客户请求转发给相应的容错组执行 客户请求。 2 容错层交互过程 口= 业u2 _ t 衄_ “u 啦i _ 目日t 皿 。脚吩。一d m 一h ) 。q 忡j “i p o g “o f a , , t l 、 1 1 - d q _ t q t 谢 避嚣箍嚣严l 印盟 m 蛆f i 笋- 掣唑! 罢掣 9 ”吨”掣 图2 5 ：容错层动态交互过程 如图2 - 5 所示。容错层的交互过科如f ： ( 1 ) 容错组豹! r 成员( 失效、加入等) 发生变化时，为保证容错请求执行的原子性，容错 组成员执行视图同步协议。 ( 2 ) g r o u p v i e w s y n c h r o n i z e 请求f a i l u r e d e t e c t o r 组卅：，以决定进入新的组视图。 ( 3 ) 在收到t a s k s c h e d u l e r 发山的客户请求斤，f t c o n s e n s u s 向t o t a l o r d e r c o m p u t a t i o n 组件 请求计算全序的任务请求序列。 ( 4 ) 在收到全序的任务请