（计算机科学与技术专业论文）分布式系统中容错机制性能优化技术研究.pdf

国防科学技术大学研究生院博士学位论文 摘要 随着分布计算技术在关键应用领域的不断拓展，分布式应用对高可靠性和高 可用性的需求越来越迫切。容错机制是增强应用可靠性和可用性的主要手段，它 使得应用系统在部分组件发生失效时，仍然能够继续正确地向外界提供服务。但 是在基于商用现货c o t s 组件的分布计算系统中引入容错机制，通常会对应用系 统的性能指标造成较大的影响，因此分布式系统中容错机制的性能优化问题被广 泛关注。 本文致力于研究分布式容错计算系统中的关键技术，并以性能优化为主要目 标，为开发高性能的容错中间件平台提供支持。本文研究了算法和体系结构两个 方面的性能优化技术：在算法方面，主要围绕全序组通信问题和乐观同步复制问 题展开研究；在体系结构方面，以c o r b a 中间件为平台，研究具有可扩展性和 自适应性的容错计算框架及实现机制。本文的主要研究内容和贡献包括： 1 提出了两种全序组通信优化算法- e d 算法和t d m 算法。e d 算法针对 采用不可靠失效检测器的静态容错系统，利用乐观假设和捎带机制来加速消息的 排序过程，从而降低了算法的平均延迟时间。t d m 算法针对采用组成员关系服务 的动态容错系统，该算法将令牌环算法和确定性合并算法融合，能够根据系统的 负载大小和分布情况，自动调节控制消息的比例，从而能够在延迟时间和吞吐量 两个主要性能指标之间获得有效的平衡。与其它同类算法相比，t d m 算法能够同 时获得较低的延迟时间和较高的吞吐量，并且在突发消息模式下，算法性能更显 著优于同类算法。 2 提出了乐观同步复制算法a r o a 。针对主动复制算法的性能问题，本文提 出了一种基于乐观机制但能够保证复制一致性的乐观同步复制算法a r o a ，它能 够较为明显地改善算法的响应时间。a r o a 算法基于下述设计思想：所有副本在 接收到客户发送的请求后，并发地执行请求的排序过程和请求的处理过程。在绝 大多数情况下，请求的最终排序结果和请求的处理顺序是一致的，这样由于两者 并发执行，就显著地减少了请求响应时间，同时也有助于提高系统的吞吐量。a r o a 算法在请求的排序结果最终确定之前，不会将请求的处理结果返回给客户，因此 如果乐观假设不成立，通过执行恢复过程，能够避免客户得到不一致的请求处理 结果。此外，本文对乐观复制算法可能发生的负作用问题进行了分析，进一步提 出了将乐观复制算法和保守复制算法结合的思想，从而使得乐观算法只发挥其积 极作用，屏蔽其消极影响。 3 可扩展性容错计算框架研究。本文设计了一种具有可扩展性的容错计算框 架，它将容错协议和计算框架中的其它组件分离开来，用户可以根据自身应用的 第i 页 国防科学技术大学研究生院博士学位论文 语义信息来设计最高效的容错协议，并将该协议插入到容错计算框架中。可扩展 容错计算框架采用反射机制设计，容错协议能够方便地控制应用服务的行为，从 而简化了协议的设计和实现过程。此外，框架还提供了面向组的远程过程调用原 语，进一步简化了容错协议之间的通信过程。 4 自适应容错管理机制研究。本文在现有容错中间件的管理框架基础上，增 加了自适应管理机制，使得容错应用程序能够根据运行环境变化和用户设置的自 适应策略进行动态配置结构调整。自适应管理机制能够在保证应用可靠性的前提 下，优化系统资源使用，进而改善应用程序的性能。 5 容错计算平台的实现技术。本文基于国防科学技术大学研制的分布计算中 间件s t a r b u s + ，设计和实现了一个容错计算平台s t a r f t ，分析了实现过程中的难 点问题并给出解决方案。s t 村t 系统为用户开发、运行和配置容错应用程序提供 了有效支持，并能够获得良好的性能。 主题词：分布计算，容错，可靠性，可用性，性能优化，容错计算平台 第i i 页 国防科学技术大学研究生院博士学位论文 a b s t r a c t w i t ht h ei n c r e a s i n ga m o u n to fd i s t r i b u t e dc o m p u t i n gs y s t e m sa p p l i e di nw i d e r a n g eo fc r i t i c a ld o m a i n s ，t h er e q u i r e m e n to fh i 曲r e l i a b i l i t ya n dh i 曲a v a i l a b i l i t yo f d i s t r i b u t e dc o m p u t i n gs y s t e m si sb e c o m i n gm o r ea n dm o r eu r g e n t f a u l tt o l e r a n c ei st h e m a i nm e a n st oe n s u r er e l i a b i l i t ya n da v a i l a b i l i t yo fa p p l i c a t i o n s ，a n di te n a b l e sas y s t e m t op r o v i d ei t ss e r v i c ee v e ni fs o m ec o m p o n e n t so ft h es y s t e mf a i lt ow o r k h o w e v e r ， i m p l e m e n t i n g f a u l tt o l e r a n c em e c h a n i s m si nd i s t r i b u t e d s y s t e m s b a s e do n c o m m e r c i a l - - o f f - t h e - - s h e l fc o m p o n e n t su s u a l l yr e d u c e st h ep e r f o r m a n c eo fa p p l i c a t i o n s t oag r e a te x t e n t t h e r e f o r e ，t h ep r o b l e mo fp e r f o r m a n c eo p t i m i z a t i o ni nd i s t r i b u t e d f a u l tt o l e r a n ts y s t e m si sw i d e l ys t u d i e d i nt h i sp a p e r ，w er e s e a r c ho nt h ek e yt e c h n i q u e so ff a u l t - t o l e r a n tc o m p u t i n g s y s t e m s ，a n do u rm a i ng o a li sp e r f o r m a n c eo p t i m i z a t i o n , p r o v i d i n gs u p p o r tf o rt h e d e v e l o p m e n to fah i 班p e r f o r m a n c ef a u l t t o l e r a n tc o m p u t i n gp l a t f o r m w er e s e a r c ht w o k i n d so fp e r f o r m a n c eo p t i m i z a t i o nt e c h n i q u e s ：a l g o r i t h mo p t i m i z a t i o na n da r c h i t e c t u r e o p t i m i z a t i o n i nt e r m so fa l g o r i t h mo p t i m i z a t i o n ，w ef o c u so nt h et o t a lo r d e rb r o a d c a s t p r o b l e ma n dt h eo p t i m i s t i cs y n c h r o n o u sr e p l i c a t i o np r o b l e m i nt e r m so fa r c h i t e c t u r e o p t i m i z a t i o n ,w ep r o p o s ea ne x t e n s i b l e a n d a d a p t i v e f a u l t - t o l e r a n c ec o m p u t i n g f r a m e w o r k t h em a i nc o n t r i b u t i o n so ft h i sd i s s e r t a t i o na r ea sf o l l o w s ： 1 w ep r o p o s et w oo p t i m i z e dt o t a lo r d e rb r o a d c a s ta l g o r i t h m s ：e da l g o r i t h ma n d t d ma l g o r i t h m t h ee da l g o r i t h mi sd e s i g n e df o rs t a t i cs y s t e m su s i n gu n r e l i a b l e f a i l u r ed e t e c t o r s ，a n di tt a k e sa d v a n t a g e so fo p t i m i s t i ca s s u m p t i o na n dp i g g y b a c k m e c h a n i s mt oe n a b l em e s s a g e st ob ed e l i v e r e de a r l i e r , t h u si tr e d u c e st h e c o m m u n i c a t i o nd e l a y t h et d ma l g o r i t h mi sd e s i g n e df o rd y n a m i cs y s t e m su s i n g g r o u pm e m b e r s h i p s e r v i c e s i tc o m b i n e st h et o k e n - b a s e d a l g o r i t h m a n dt h e d e t e r m i n i s t i cm e r g ea l g o r i t h mt o g e t h e r ，a n dt h u si tc a na c h i e v eb o t hl o wl a t e n c ya n d l l i g ht h r o u g h p u t ，a n di ti se v e nm o r ee f f i c i e n tu n d e rt h eb u r s t ym e s s a g ea r r i v a lp a t t e r n ： 2 w ep r o p o s ea ne f f i c i e n tr e p l i c a t i o na l g o r i t h ma r o a t h ea l g o r i t h mi sb a s e do n a c t i v er e p l i c a t i o nm o d e ，b u ti tu s e st h eo p t i m i s t i ca p p r o a c ht or e d u c et h er e s p o n s et i m e h o w e v e r ，t h ea r o aa l g o r i t h ms t i l le n s u r e st h ec o n s i s t e n c yo fr e p l i c a s i t sm a i ni d e ai s ： a l lr e p l i c a sr e c e i v et h ec l i e n tr e q u e s t s ，a n dt h e yp e r f o r mt h er e q u e s tp r o c e s s i n gt a s ka n d t h er e q u e s to r d e r i n gt a s kc o n c u r r e n t l y i nm o s tc a s e s ，r e q u e s t sa r ep r o c e s s e da n da r e o r d e r e di nt h es a m eo r d e r , t h e r e f o r et h er e s p o n s et i m ea r er e d u c e dd u et ot h ec o n c u r r e n t e x e c u t i o n t h ea r o a a l g o r i t h mn e v e rr e t u r n st h er e p l yo f ar e q u e s tt ot h ec l i e n tb e f o r e t h eo r d e ro ft h er e q u e s ti sc o n f i r m e db yt h eo r d e r i n gt a s k , t h e r e f o r e ，i ft h eo p t i m i s t i c a s s u m p t i o nd o e s n o th o l d ，t h ea l g o r i t h mc a np e r f o r mr e c o v e r yt a s kt oe n s u r e c o n s i s t e n c y ：i na d d i t i o n w ep r o p o s ec o m b i n i n gt h eo p t i m i s t i ca l g o r i t h mw i t l lt h e c o n s e r v a t i v eo n et oa v o i dt h en e g a t i v ee f f e c t so ft h eo p t i m i s t i co n e 第i i i 页 国防科学技术大学研究生院博士学位论文 3 t h er e s e a r c ho ft h ee x t e n s i b l ef a u l tt o l e r a n tc o m p u t i n gf r a m e w o r k m o s t e x i s t i n gf a u l tt o l e r a n tc o m p u t i n gf r a m e w o r ko n l yp r o v i d es o m el i m i t e dn u m b e r so f r e p l i c a t i o np r o t o c o l s ，w h i c ha r eg e n e r a la n dd on o tm a k eu s eo ft h es e m a n t i ck n o w l e d g e o fa p p l i c a t i o n s ，t h e r e f o r et h e ya r en o tt h eb e s tc h o i c ef o ru s e ra p p l i c a t i o n s w ep r o p o s e af r a m e w o r kw h i c ha l l o w su s e r st od e v e l o pt h e i ro w nr e p l i c a t i o np r o t o c o l sa n dp l u g t h e mi n t h ef r a m e w o r ki sd e s i g n e db a s e do nt h er e f l e c t i o nm e c h a n i s mt os i m p l i f yt h e d e v e l o p m e n to ft h er e p l i c a t i o np r o t o c 0 1 i na d d i t i o n ，g r o u p - o r i e n t e dr e m o t ep r o c e d u r e c a l lp r i m i t i v e sa r ep r o v i d e dt om a k et h ec o m m u n i c a t i o nm e c h a n i s mo fr e p l i c a t i o n p r o t o c o le a s yt oi m p l e m e n t 4 t h er e s e a r c ho ft h ea d a p t i v ef a u l tt o l e r a n c em a n a g e m e n tm e c h a n i s m w ea d d t h ea d a p t a t i o nm e c h a n i s mt oe x i s t i n gf a u l tt o l e r a n c em a n a g e m e n tf r a m e w o r k s ，w h i c h a l l o wt h es y s t e mt or e c o n f i g u r ed y n a m i c a l l yt oa d a p tt oc h a n g e si nt h ee x e c u t i o n e n v i r o n m e n t t h ea d a p t i v e m a n a g e m e n tm e c h a n i s mo p t i m i z e s t h eu t i l i z a t i o no f r e s o u r c e st oi m p r o v et h ep e r f o r m a n c eo ff a u l t t o l e r a n ta p p l i c a t i o n sw h i l ea s s u r i n gt h e r e l i a b i l i t ya n da v a i l a b i l i t ya tt h es a m et i m e 5 d e s i g na n di m p l e m e n t a t i o no faf a u l tt o l e r a n tc o m p u t i n gp l a t f o r m b a s e do nt h e s t u d i e so nt h ek e yt e c h n o l o g i e ss t a t e da b o v ea n dt h es t a r b u s + m i d d l e w a r ed e v e l o p e db y n a t i o n a lu n i v e r s i t yo fd e f e n s et e c h n o l o g y ，w ep r o p o s ead i s t r i b u t e df a u l tt o l e r a n t c o m p u t i n gp l a t f o r mn a m e ds t a r f tt os u p p o r tt h ed e v e l o p m e n ta n dm a n a g e m e n to ff a u l t t o l e r a n ta p p l i c a t i o n s k e yw o r d s - d i s t r i b u t e dc o m p u t i n g ，f a u l tt o l e r a n c e ，r e l i a b i l i t y ，a v a i l a b i l i t y ， p e r f o r m a n c eo p t i m i z a t i o n f a u l t - t o l e r a n tc o m p u t i n gp l a t f o r m 第i v 页 国防科学技术大学研究生院博士学位论文 表目录 表3 1 失效检测器的分类2 8 表5 1 常见容错属性表8 4 第v 页 国防科学技术大学研究生院博士学位论文 图目录 图1 1 论文组织结构。5 图2 1故障、差错与失效之间的因果链8 图2 2 可信树9 图2 3提高系统可信性的几种途径1o 图2 4 时间冗余与空间冗余11 图2 5 复制技术分类1 2 图2 6 主动复制1 3 图2 7 被动复制1 4 图2 8 容错中间件的三种实现策略1 8 图2 9i r l 系统结构2 0 图2 1 0c q o s 系统结构2 l 图2 1 1 容错c o r b a 体系结构2 2 图3 1 基于u f d 的全序组通信模型3 0 图3 2 基于g m s 的全序组通信模型31 图3 3 虚拟同步通信3 2 图 图 图 图 全序组通信算法的执行模型3 4 分布式系统的仿真模型3 9 延迟时间随系统负载变化曲线( 乐观条件下) 4 0 延迟时间随系统负载变化曲线( 乐观条件不成立) 4 1 图3 8 延迟时间随m r r 的变化曲线4 l 图3 9 均匀消息模式下，延迟时间随吞吐率变化曲线4 8 图3 1 0 均匀消息模式下，延迟时间和组成员数目的关系4 9 图3 1 l 突发消息模式下，延迟时间随吞吐率变化曲线( 一个突发进程) 4 9 图3 1 2 突发消息模式下，延迟时间随吞吐率变化曲线( 两个突发进程) 5 0 图4 1主动复制与乐观复制技术5 1 图4 2 乐观复制系统模型。j 5 3 图4 3 请求队列r q 的运行状态5 7 图4 4 半乐观复制5 8 图4 图4 图5 图5 响应时间随吞吐率变化曲线6 0 响应时间随消息重排率的变化曲线6 0 容错应用的设计开发过程6 2 分布对象容错计算环境6 4 第页 国防科学技术大学研究生院博士学位论文 图5 3 容错计算方法分类6 7 图5 4 可扩展自适应容错计算系统模型6 9 图5 5 可扩展容错计算框架7 1 图5 6 反射机制的两种实现方式7 2 图5 7 反射协议接口7 3 图5 8 反射协议序列图7 4 图5 9g r p c 服务接口7 5 图5 。1 0g r p c 服务的成员管理机制7 5 图5 1 lg r p c 服务请求调用机制7 6 图5 1 2g i 渖c 服务的组成结构7 7 图5 1 3 容错协议的构建方法7 8 图5 1 4 平均响应时间随吞吐率变化曲线8 l 图5 1 5 平均响应时间随服务副本数目变化曲线8 2 图5 16 复制模式转换过程8 5 图5 17 自适应管理框架8 7 图5 18 自适应副本数目调整策略8 9 图5 1 9 平均响应时间随主副本c p u 负载率变化曲线9 1 图6 1s t a r b u s + 软件体系结构9 2 图6 2s t a r f t 容错计算平台体系结构9 3 图6 3对象组引用i o g r 9 4 图6 4 本地对象工厂接口9 9 图6 5自适应策略管理器接口9 9 图6 6 配置工具s t a r f tc o n i i g u r a t o r 界面1 0 0 图6 7响应时间随客户线程数目的变化曲线j 1 0 1 第v i i 页 独创性声明 本人声明所呈交的学位论文是我本人在导师指导下进行的研究工作及取得的研 究成果尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已 经发表和撰写过的研究成果，也不包含为获得国防科学技术大学或其它教育机构的学 位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文 中作了明确的说明并表示谢意。 学位论文题目：金查盛歪统生空堡扭剑：陛能佐毡拉盔丑塞 学位敝作者签名：公丘 日期功1 年午月莎日 学位论文版权使用授权书 本人完全了解国防科学技术大学有关保留、使用学位论文的规定。本人授权国 防科学技术大学可以保留并向国家有关部门或机构送交论文的复印件和电子文档，允 许论文被查阅和借阅；可以将学位论文的全部或部分内容编天有关数据库进行检索， 可以采用影印，缩印或扫描等复制手段保存、汇编学位论文 ( 保密学位论文在解密后适用本授权书。) 学位论文题目：金查式丞缠主窒笪扭剑性能佐丝拉苤盈塞 学位论文作者签名：虚笼砬日期：乙1 年午月加 作者指导教师签名：主室孓哇 日期：6 1 年l f月占日 国防科学技术大学研究生院博士学位论文 1 1 1 应用需求 第一章绪论 1 1 研究背景 随着i n t e m e t i n t r a n e t 网络技术的快速发展和信息技术的日益普及，分布式计 算应用开始逐渐地从传统、小型的业务系统向以电子商务、科学计算、协同工作 等为代表的更广阔领域扩展。在这些应用领域中，系统的规模通常十分庞大，组 件数目众多，并且各组件之间相互连接形成了复杂的依赖关系，每个组件发生故 障都可能导致整个系统无法正常运转。另一方面，很多关键应用领域对计算的可 靠性和可用性都有很高的要求，如军事、航空、金融、电信、工业控制、企业计 算等。这些关键应用一旦发生故障，可能会带来巨大的经济损失，甚至导致严重 的灾难性后果。因此，为这些应用提供高可靠和高可用支持已成为实现分布计算 的一个关键性问题。 实例l ：军事抗毁应用 在现代战争中，信息战成为了一种重要的甚至是决定性的作战形式。为了提 高作战系统的信息处理能力，军事指挥自动化系统便应运而生。军事指挥自动化 系统由分布在不同地理位置上的多个指挥所构成，其中一个指挥所为总指挥所， 其它为副指挥所。总指挥所是整个系统的核心，它收集各个副指挥所的情报信息， 并进行分析整理做出相应的战略决策。但是由于战争的残酷性，存储有重要军事 信息以及进行关键决策的总指挥所通常是敌方攻击的首要目标，这就要求系统必 须具有快速恢复能力，在总指挥所被敌方摧毁的情况下，系统整体仍然能够持续 正常地发挥作用。提高军事应用系统的抗毁性已成为军事科研领域中最为迫切的 需求课题之一。 实例2 ：i n t e m e t 上的企业计算 在快速多变的i n t e m e t 电子商务时代，企业的关键计算业务要求能够每天2 4 小时，每周7 天持续地运转。如果这些关键业务因为宕机而陷于停顿，将会导致 重大的经济损失。例如著名的电子交易网站a m a z o n t o m 的一次宕机故障使其销售 业务平均每分钟损失2 5 ，0 0 0 美元【l 】。除了直接经济损失以外，关键业务的宕机可 能还会导致企业客户群流失、信誉降低、股票下跌、竞争力下降等其它更为严重 的问题。因此，企业中的关键计算业务必须具有高可靠性和高可用性才能够在今 天竞争日益激烈的市场中生存。 第1 页 国防科学技术大学研究生院博士学位论文 1 1 2 容错计算及性能优化问题 容错技术是提高分布式系统可用性和可靠性的一种重要方法 2 3 1 1 4 ，它使得系 统在有部分硬件或者软件资源发生失效时，系统作为整体仍然能够正常运行并完 成其设计功能。 在分布式计算系统中，复制技术是实现容错机制的一种基本途型3 】【5 】。复制技 术为应用的关键服务配置多个副本，并通过一组冗余的计算资源来运行这些副本， 因此当部分副本发生失效时，其它副本仍然可以继续为用户提供服务。实现复制 技术的一个关键问题是保证副本的状态一致性，但是由于分布式系统的异步性， 这一问题变得非常困难，必须设计复杂的组通信协议和复制协议才能保证服务副 本之间的状态同步。 性能问题是分布式计算技术中的另外一个关注重点。对于大多数关键应用服 务来说，不仅需要保证服务的可用性，还需满足一定的性能指标，以使得在并发 用户数目和系统负载增加的情况下，仍然能够在限定的时间内完成计算任务。通 常情况下，提高系统性能和增加系统的容错性是两个相互矛盾的目标【6 】【7 】，容错系 统中服务副本之间的同步操作不仅增加了客户请求的处理时间，同时需要占用额 外的计算资源，降低了系统的吞吐率。文献【6 】【8 9 中的实验结果都表明容错机制 对系统的性能有着较大的影响。正是由于这一原因，目前很多关键应用并没有选 择基于商用现货( c o t s ，c o m m e r c i a l o f f - t h e s h e l f ) 的分布式容错系统，而是使 用价格昂贵的硬件容错机制，例如在数据库领域，虽然分布式数据库复制技术被 广泛研究，但是大部分主流数据库系统却采用了共享存储的硬件容错机制【l0 1 。因 此，性能因素成为制约分布式容错技术应用的一个关键问题。最近几年，越来越 多的研究者开始关注分布式容错系统中关键算法的性能优化问题f l l 】f 1 2 1 1 1 3 】【1 4 】【1 5 1 。 另一方面，从实践角度考虑，分布式容错系统的体系结构也需要以性能为目 标实施优化。目前分布计算系统通常利用中间件来为应用程序提供容错能力。中 间件是当前分布式网络应用开发的主流计算平台，它是一种介于系统软件( 操作 系统) 和应用软件之间的一种分布式软件，为用户提供了统一集成的分布编程环 境，简化了分布式应用的设计、实现和管理过程。分布对象中间件是类典型的 中间件，它利用面向对象的概念抽象了基于客户服务器模式的分布式计算模型， 为分布式应用屏蔽底层网络通信细节，支持异构环境下应用的开发和互操作，提 供语言无关、位置透明以及可移植等特性。分布对象中间件把应用开发者从复杂 的网络编程环境中解放出来，使其能够专注于业务逻辑的开发，因此在分布式应 用开发过程中被广泛采纳，主流的对象中间件系统包括o m g 组织的c o r b a 1 6 j ， s u n 公司的j a v ar m i i l 7 】，微软公司的d c o m c o m + i i s 等。 尽管中间件简化了应用程序的开发过程，但是开发具有容错能力的应用程序 第2 页 国防科学技术大学研究生院博士学位论文 仍然是一项非常复杂的任务。应用开发者不仅需要关注应用的业务逻辑，还要实 现失效检测、组通信协议、复制协议等复杂的容错逻辑。如果容错逻辑设计不当， 不仅达不到容错效果，反而会增加应用程序失效的概率。为了减轻应用开发者的 负担，许多研究工作都致力于设计具有容错功能的中间件，即所谓的容错中间件。 容错中间件为容错应用程序的开发、配置和维护，提供了支撑运行机制和管理框 架，应用开发者只需关注业务逻辑，并其开发的应用程序配置到容错管理框架中 即可自动实现容错逻辑。 虽然在容错中间件方面已经展开了不少研究工作，并取得了一些成果，但是 却很少有真实的应用系统基于容错中间件来开发【1 9 1 。在文献【1 9 】中，f e l b e r 等人对 c o r b a 平台上的容错研究工作进行了全面分析和总结，指出性能问题成为制约容 错中间件应用的关键因素。这是因为容错中间件通常以实现容错透明性为目标， 缺乏对应用语义信息的了解，只能采用少数几种保守的复制协议，例如主动复制 协议和被动复制协议等。虽然这些协议能够保证应用的可靠性，却由于采用保守 的策略来维护副本的状态一致性，对应用程序的性能造成了很大影响。另一方面， 现有的容错中间件大多采用静态的方式来配置应用程序，缺乏自适应性，不能够 根据运行环境的变化动态地调整容错策略，因而无法有效地平衡系统的容错性和 资源开销。 综上所述，分布容错计算系统在容错算法和体系结构两个方面必须进行性能 优化，本文将对其中的若干关键技术进行深入研究。 1 2 研究内容 本文致力于研究分布式容错计算系统中的关键技术，并以性能优化为主要目 标，为开发高性能的容错中间件计算平台提供支持。本文中讨论的性能优化技术 分为容错算法和体系结构两个方面：在算法方面，主要围绕全序组通信问题和乐 观同步复制问题展开研究；在体系结构方面，以c o r b a 中间件为平台，研究具 有可扩展性和自适应性的容错计算框架及其实现机制。 本文工作得到了国家自然科学基金项目“以网络为基础的科学活动环境综合 试验平台( n o 9 0 4 1 2 0 1 1 ) 、国家9 7 3 课题“虚拟计算环境可信保证体系与机制 f n o 2 0 0 5 c b 3 2 1 8 0 4 ) 以及国家8 6 3 重点项目“网络环境的新一代中间件核心技术及 运行平台”( n o 2 0 0 1 a a l l 3 0 2 0 ，n o 2 0 0 4 a a l l 2 0 2 0 ) 、国家8 6 3 课题“面向应用 服务器的自主计算技术研究 ( n o 2 0 0 3 a a l15 2 1 0 ) 等课题的支持。 本文的具体研究工作包括以下四个方面： 1 全序组通信算法研究 第3 页 国防科学技术大学研究生院博士学位论文 全序组通信是分布式容错计算领域里一种非常重要的组通信原语，它能够保 证一个通信组中的所有成员对该组中发生的事件形成一致的视图，因此被很多分 布式应用程序用作基本的构建模块。但是从性能角度考虑，全序组通信却被认为 是一种比较昂贵的组通信原语1 2 0 。 本文提出了两种全序组通信优化算法_ e d 算法和t d m 算法。e d 算法针对 采用不可靠故障检测器的静态容错系统，以基于c o n s e n s u s 协议的c t 全序算法为 基础【5 0 1 ，利用乐观假设和捎带机匍j ( p i g g y - b a c k ) 来加速消息的排序过程，从而改善 了算法的平均延迟时间。t d m 算法针对采用组成员关系服务的动态容错系统，该 算法将传统的令牌环全序算法和确定性合并算法融合，能够根据系统的负载大小 和分布情况，自动调节控制消息的比例，从而能够在平均延迟时间和最大吞吐量 两个主要性能指标之间获得有效的平衡。与其它同类算法相比，t d m 算法能够同 时获得较低的延迟时间和较高的吞吐量，并且在突发消息到达模式下，算法性能 更显著优于同类算法。 2 乐观同步复制算法研究 复制算法决定着服务副本之间的同步方式，在很大程度上影响着应用服务的 性能，因此成为分布式容错计算领域里的一个主要研究问题。 针对传统的主动复制算法不足，本文提出了一种基于乐观机制但能够保证复 制一致性的乐观同步复制算法a r o a 。它基于下述设计思想：所有服务副本在接 收到客户发送的请求后，并发地执行请求的排序过程和请求的处理过程。在绝大 多数情况下，请求的最终排序结果和请求的处理顺序是一致的，这样由于两者并 发执行，就显著地减少了请求响应时间，同时也有助于提高系统的吞吐量。a r o a 算法在请求的排序结果最终确定之前，不会将请求的处理结果返回给客户，因此 如果乐观假设不成立，通过执行恢复过程，能够避免客户得到不一致的请求处理 结果。 本文对乐观复制算法可能发生的负作用问题进行了分析，进一步提出了将乐 观复制算法和保守复制算法结合的思想，从而使得乐观算法只发挥其积极作用， 屏蔽其消极影响。 3 可扩展容错计算框架研究 容错计算框架描述如何在一个分布计算平台上引入容错机制。本文基于 c o r b a 中间件平台设计了一种具有可扩展性的容错计算框架，它将容错协议和计 算框架中的其它部分组件分离开来，用户可以针对自身应用的特点来设计最为高 效的容错协议，并将该协议插入到容错计算框架中。 可扩展容错计算框架为开发容错协议提供了一些常用的构建模块。用户设计 第4 页 国防科学技术大学研究生院博士学位论文 的容错协议可以通过反射机制来获取和设置服务副本的状态，并控制其处理客户 请求流程。容错协议在通信时不需要直接使用面向消息的组通信原语，而是可以 利用面向组的远程过程调用原语来简化设计和实现过程。 4 自适应容错管理机制研究 容错管理主要解决容错应用程序的创建、配置和维护等问题。现有的容错管 理框架通常采用静态或者手动的方式来管理容错应用程序，这种方式很难在应用 的容错性和性能之间获得有效的平衡。 本文在容错c o r b a 的管理框架基础上，增加了自适应管理机制，使得容错 应用程序能够根据运行环境变化和用户设置的自适应策略进行动态的配置结构调 整，从而在保证应用的可靠性和可用性前提下实现性能优化。 5 容错计算平台的设计与实现 本文基于国防科学技术大学研制的分布计算中间件s t a r b u s + 2 1 1 ，设计和实现 了一个容错计算平台s t a r f t ，分析了实现过程中的难点问题并给出解决方案，最 后通过实验来评测其性能。 1 3 论文结构 本文共分为六章，其组织结构如图1 1 所示： 1 绪论 l 2 分布容错计算技术综述 ：l 13 全序组通信4 乐观同步5 可扩展自适应的容 l协议研究复锚算法 错计算模型及框架 - l 6 原型系统与实现 l 结束语 图1 1 论文组织结构 第一章为绪论，介绍了课题的研究背景和动机，简要地概括了本文在容错计 算性能优化方面所做的主要工作。 第5 页 国防科学技术大学研究生院博士学位论文 第二章综述分布式容错计算系统中一些基本概念和关键技术，并对研究现状 进行分析和总结。 第三章研究全序组通信协议的构建模型，提出两种优化算法，给出了正确性 证明，并通过仿真试验测试其性能。 第四章研究基于乐观机制的同步复制算法，阐述了算法的基本思想、实现原 理、优化方案及实验结果。 第五章针对目前容错中间件存在的一些缺点，提出了一种具有可扩展性和自 适应性的容错计算模型及实现框架。 第六章基于s t a r b u s + 中间件平台，研究分布对象容错计算平台的关键实现技 术，并通过实验评估其性能。 最后总结全文工作，并对下一步的工作进行展望。 第6 页 国防科学技术大学研究生院博士学位论文 第二章分布容错计算技术研究综述 本章主要介绍容错计算系统中的基本概念和关键技术，对相关工作进行分析 和比较，指出一些需要进一步研究的问题。 本章内容组织如下：第一节概述了容错系统中的基本概念以及容错机制的基 本实现途径；第二节重点研究基于复制机制的分布容错计算系统，对主要的复制 技术进行了分析和比较；第三节深入讨论了容错计算系统中的一个重要基础设施 组通信服务；第四节比较全面地介绍了中间件平台上的容错研究工作；第五 节对研究现状进行分析和总结，指出本文工作的着眼点；第六节对全章总结。 2 1 容错技术概述 2 1 1 容错技术的发展过程 容错技术的研究最早产生于硬件领域。从研制第一台数字计算机开始，计算 机设计者们就意识到，仅靠仔细设计和精心选择元器件是不能完全克服设计错误 和器件的物理缺陷【2 2 】，人们不得不用各种容错技术来维持系统的正常运行。因此， 早期的计算机设计采用硬件冗余的办法来屏蔽失效器件，用纠错码和表决器来检 测或纠正信息错误，用诊断技术定位失效元器件并自动切换备件。 在工程技术不断发展的同时，一些计算机科学奠基人提出了“用不可靠元件 来构造可靠系统 这样一个理论问题，其中最著名的当属冯诺依曼( v