（计算机应用技术专业论文）集中式机群自动重构系统（ccars）的研究与实现.pdf

华中科技大学硕士学位论文 摘要 ( 机群是一个由高性能网络或局域网物理地互连，通过机群系统软件，互相协作，作 、 为整体对外提供服务的计算机集合。机群系统的优点是可扩展性好，但是，集中式机群 的主结点如果发生故障同时机群没有好的自动恢复机制，机群系统整体的可用性将会降 低。自动重构系统能提高机群可用性，是机群研究热点之一。但是，目前的机群重构系 统只考虑了如何提高机群可用性，没考虑重构后的圭结点可能负载过重而造成机群系统 频繁地进行负载迁移，浪费了宝贵的系统资源。在设计机群重构系统的时候，如何避免 频繁地负载迁移是机群研究的难点之一。少 c c a r s 是在! ! 盟蜒握缝丕堕环境下开发的集中式机群自动重构系统。它的主要目标 是：提高机群可用性和避免机群系统重构时发生过多的负载迁移。它通过减少故障修理 的时间来提高机群可用性：通过选出负载轻、性能好的结点作为故障后的主结点来实现 上述第二个目标。本系统的主要模块有：从结点的负载收集模块和主结点的负载预测模 块、主从结点的趑瞳握型模块、主结点故障后的主结点选择模块。 c c a r s 选择高效且合理的负载指标来度量结点的负载，提出使各从结点同步收集自 身负载信息并传送给主结点的方法，推导估算各从结点未来某个时刻负载值的数学公 式；同时，设计了主从结点用来相互探测对方是否故障的c c a r s - - h e a r t b e a t 机制和集 中控制式机群启动和主结点故障后的主结点选择机制。最后，详细分析了机群故障率与 塑登堕皇茎的数学关系一( 为实验所需结点机数提供了理论依据， 、) 镰键词：机群重构；负载；机群可用性：故障探测 保证了机群的高可用性。上 华中科技大学硕士学位论文 ： = = = = = = = = = = ；= = = = ；= = = = = = = ；= = = = j = = ；= ；= 一 a b s t r a c t ac l u s t e ri sa g r o u p o f t h ew h o l e c o m p u t e r s ，w h i c h a r ei n t e r l i n k e db yt h en e t w o r ko fh i g h p e r f o r m a n c eo rt h el a n b y t h es y s t e ms o f t w a r eo fc l u s t e r , t h ec l u s t e rc o o p e r a t e se a c ho t h e r a n d s u p p l i e ss e r v i c e t ot h eo u t s i d ea saw h o l e t h e a d v a n t a g e o f t h ec l u s t e rs y s t e mi si t sf i n e e x p a n s i b i l i t y b u t ，i ft h em a s t e rn o d eo f t h ec l u s t e rh a p p e n st h em a l f u n c t i o na n dh a sn o ta f i n e ra u t o m a t i c a lr e n e wm e c h a n i s m ，t h ew h o l ea v a i l a b i l i t yo ft h ec l u s t e rs y s t e mw i l lf a l l t h e a u t o m a t i cr e c o n s t r u c t i o nt h a tc a ne l e v a t et h ew h o l ea v a i l a b i l i t yi so n eo ft h eh o t s p o to ft h e c l u s t e rr e s e a r c h b u t ，t h ep r e v e n i e n tr e c o n s t r u c t i o ns y s t e m so n l yc o n s i d e rh o wt oe l e v a t et h e w h o l ea v a i l a b i l i t y , n o tt h ef e w e rn o d el o a dt h a tw i l lc a u s ef r e q u e n tl o a dm o v i n g ，s ot h a tt h e p r e c i o u ss y s t e mr e s o u r c ew i l lb ew a s t e d h e i g h t e n i n gt h ew h o l ea v a i l a b i l i t yo f t h e c l u s t e ra n d a v o i d i n gt h ef r e q u e n tl o a dm o v i n g i sa p r o b l e m o f t h er e s e a r c ho f c l u s t e r c c a r s ( t h ec e n t e rc o n t r o l l i n gc l u s t e r a u t o m a t i cr e c o n s t r u c ts y s t e m ) i sac l u s t e r a u t o m a t i cr e c o n s t r u c ts y s t e md e s i g n e du n d e rt h el i n u xo s i t sm a i ng o a li sh e i g h t e n i n gt h e w h o l ea v a i l a b i l i t yo ft h ec l u s t e ra n da v o i d i n gt h ef r e q u e n tl o a dm o v i n g b yr e d u c i n gt h e r e p a r a t i v et i m ew h e nt h ec l u s t e rm a l f u n c t i o nh a p p e n s ，t h es y s t e mc a nh e i g h t e nt h ew h o l e a v a i l a b i l i t y ；t h em e t h o di st h a tt h ec l u s t e rc h o o s e st h en e x tm a s t e rn o d ea u t o m a t i c a l l ya n d q u i c k l y b yc h o o s i n g t h el o w e rl o a da n dh i g h p e r f o r m a n c en o d e t oa c t 嬲t h em a s t e rn o d e ，t h e s y s t e m c a l la v o i dt h ef r e q u e n tl o a dm o v i n g ；t h em e t h o di st h a te v e r ys l a v eu o d e sw a i tf o rt h e t i m et oc o m p e t et ob e c o m et h en e x tn o d e t h et i m ei sd i r e c tp r o p o r t i o n 、i t l lt h es e r i a ln u m b e r t h a tt h em a s t e rn o d ee s t i m a t ee v e r ys l a v en o d e l o a d ，t a x i sa n ds e n d t h es e r i a ln u m b e rt ot h e s l a v en o d e t h e s em a i nm o d u l e so ft h es y s t e ma r et h ec o l l e c t i n gl o a dm o d u l eo ft h es l a v e n o d e t h ee s t i m a t i n g1 0 a do ft h em a s t e rn o d e ，t h ed e t e c t i n gm a l f u n c t i o nm o d u l eo ft h es l a v e a n dm a s t e rn o d e ，a n dt h es e l e c t i n gm a s t e rn o d em o d u l ew h e nt h em a i nc o n t r o l l i n gn o d e h a p p e n i n g t h em a l f u n c t i o n c c a r s g i v e st h em e t h o do f t h es e l e c t i n go f t h el o a di n d e x ，w ep u tf o r w a r dam e a n st h a t m a k e se v e r ys l a v en o d e sc o n v e yt h e i rl o a di n f o r m a t i o nt ot h em a s t e rn o d e s y n c h r o n o u s l y ；a t n 华中科技大学硕士学位论文 t h es a m et i m e ，i n t r o d u c e st h em a t hf o r m u l at h a tt h em a s t e rn o d ee s t i m a t et h el o a do ft h e o t h e rs l a v en o d e s i ns u c c e s s i o n ，d e s i g n st h ec c a r s - h e a r t b e a tm e c h a n i s ma n dt h e m e c h a n i s mo f t h em a s t e rn o d es e l e c t i n g t h em e c h a n i s mi su s e dt od e t e c tt h eb r o k e n d o w no f n o d e s t h el a t t e ri su s e dw h e nt h ec e n t r a la n dc o n t r o l l a b l ec l u s t e rs t a r t u p sa n dt h em a s t e r n o d eh a sam a l f u n c t i o n a tl a s t ，t h es y s t e md e t a i l e d l ya n a l y s e st h em a t hr e l a t i o no f t h ec l u s t e r m a l f u n c t i o nr a t ea n dt h en u m b e ro ft h ec l u s t e rn o d e s ；t h i sw i l ls u p p l yt h et h e o r yb a s ef o rt h e e x p e r i m e n tt h e w h o l e a v a i l a b i l i t yo f t h ec l u s t e rs y s t e m w i l ll i eo nt h e h i g h e rl e v e l k e yw o r d s ：c l u s t e rr e c o n s t r u c t i o n ；l o a d ；t h ea v a i l a b i l i t yo ft h ec l u s t e rs y s t e m ；d e t e c t i n g m a l f u n c t i o n 华中科技大学硕士学位论文 1 绪论 1 1 问题的提出 随着工作站和p c 机性能的迅速提高和价格的日益下降，以及网络的高速发展，用 由工作站或p c 机构成的机群系统作为并行分布计算的平台，日益受到广泛的重视和欢 迎。基于网络的并行技术已经被证明是一种有生命力且高效的方法。松散耦合计算机上 的机群计算或并行处理是一项迅速发展的技术，为实现高性能的应用提供了巨大的潜 力。 机群系统的优点是可扩展性好。随着机群系统规模的增大，结点数目的增多，机群 系统整体的可靠性会降低，同时机群的可用性“1 也降低了。高可用性是机群的研究热点， 但是高可用性机群的目标是在系统出现某些故障的情况下，仍能继续对外提供服务，这 就决定了它的设计思想是最大限度地减少服务中断时间而不是提供与结点数成正比的 负载能力。同样，负载平衡机群的设计也不能很好的兼顾高可用性的问题。 目前商品化的机群系统( 如由p l a t f o r m c o m p u t i n g 开发的l s f ) 或者采用机群重 构等软件技术来提高机群可用性，做到只要有一个结点可用，机群就能工作：或者采用 负载平衡等软件技术来快速地平衡机群负载。分析可知这些机群重构软件技术或者可用 性不高( 主结点故障后必须人工启动机群) ；或者没有考虑结点的负载，导致机群重构【2 】 后的主结点负载过重而频繁地负载迁移。 基于以上问题，本文将实现一个机群自动重构系统。系统能够减少服务中断的时间， 提高机群可用性；并能避免发生频繁的负载迁移。 文中设计的c c a r s 是一个基于l i n u x 的p c 机群的集中控制式机群自动重构系统。 该系统面向的是松散耦合的p c 机群系统，系统中的各个结点的c p u 处理能力、内存数 目等都可能不同。负载信息收集子系统能访问l i n u x 的系统内核信息，可以使每个结点 实时收集自己的负载信息并将收集到的负载信息同步地传送给主结点。主结点根据收集 的信息预算各从结点的负载并排序。整个机群再通过本文设计的通信模块便可以很好的 实现机群自动重构，减少了由于主结点不可自动恢复而造成的服务中断的时间，提高了 机群的可用性，也避免了重构时可能出现负载不平衡的问题。 华中科技大学硕士学位论文 1 2 国内外发展概况 机群重构模型设计的研究一直是机群系统研究的重点。目前，国内外已经研制开发 了多个基于工作站机群的机群系统，代表性的系统有：w i s c o n s i n m a d i s o n 大学的 c o n d o r 系统。“、p l a t f o r m 公司的l s f 系统。目前的机群重构模型有可迁移式的重构 模型“1 、l s f 的重构模型、主副服务器重构模型”1 等，本文现介绍如下： i 可迁移式的重构模型 w i s c o n s i n m a d i s o n 大学的c o n d o r 系统中主结点的功能十分有限，其它机器对主结 点的依赖性不是很强，但该系统主结点选择机制使系统的可靠性差。如果主结点发生故 障，则需要对c o n d o r 池内所有机器的配置文件进行修改，才能够恢复正常运行。这将 使机群的可用性明显降低。基于此，有人提出使用可迁移式的可用性模型来解决这个问 题。主结点可以通过竞争产生。当一台属于c o n d o r 池的机器启动时，它首先发广播寻 找主结点机。如果当前c o n d o r 池中还没有其他机器启动，那么它就定义自己为主结点 机并启动服务员进程。当主结点机需要关机时，它发送一个广播给所有正在运行的 c o n d o r 池的机器。其他机器收到广播后，向主结点发送应答信息，主结点将第一个作出 响应的机器指定为机群的新的主结点。 2 l s f 的重构模型 目前。l s p 通过实现一个m a s t e r 选择机制来解决这个问题。任何一个l s f 机群上 都保存有一个配置文件，该文件是一张按顺序列出机群中所有结点的表。每个结点有一 个结点号，在表中第一个结点号为0 ，一旦启动，如果结点0 没有关机它便成为主结点。 在一个l s f 机群中，主结点会自动启动一个守护进程，定期传递心跳消息给其他工作结 点。任一其他结点一开始进入的是“非主机”状态，直到它收到了来自主结点的心跳， 它便成为了一个从结点。 主结点发生故障时，它就不能发出心跳消息了，每一个从结点检查到这个情况后便 进入“非主机”状态。它等待与它的结点号成比例的段时间，尝试成为一个新的主结 点。如果有超过两个结点发生竞争，具有最小结点号的结点获胜。 3 主副服务器重构模型 个结点为主服务结点，另一个结点为副服务结点，其它结点为客户结点。所有结 华中科技大学硕士学位论文 点都向主服务结点发送“心跳”消息，主服务结点只向副服务结点发送“心跳”消息。 当客户结点发生故障或退出h a 机群时，由主服务结点根据负载参数计算切换结果，并 向有关结点发送应用切换的仲裁消息；当主服务结点发生故障或退出h a 机群时，副服 务结点即升级为主服务结点，同时选择一个客户结点升级为副服务结点：当副服务结点 发生故障或退出h a 机群，由主服务结点选择一个客户结点升级为副服务结点。主副容 错协议用来解决状态更新时主副服务器的一致性问题。客户机给主服务器发一个消息； 主服务器执行任务，并向副服务器发送更新消息；当副服务器收到消息后，执行更新操 作并发送“确认”消息给主服务器；当“确认”消息到达后，主服务器向客户机发送 应答消息。我们可以看到如果主服务器在副服务器发送“确认”消息给主服务器之后出 错，那么当副服务器接替主服务器后，任务会被重做3 次。一次是在主服务器上，一次 在副服务器( 请求更新已经发出) 上，还有一次是在副服务器成为主服务器后。 分析以上的提高机群可用性的技术，可以知道：可迁移式的重构模型的缺点在于机 群在主结点故障后需要人为启动，若无专人负责，可能机群的故障恢复时间以小时来计 算；而l s f 的重构模型虽然是机群在主结点故障后自启动模型，但故障后的新的主结点 可能负载过大而需要频繁地进程迁移进而浪费宝贵的机群系统资源；再说主副服务器重 构模型虽然也是机群在主结点故障后自启动模型，但它们同样存在l s f 的重构模型同样 的问题，同时还需一台专门的副服务器，造成了资源的浪费。 1 3 课题的目的，意义及实验条件 随着学术界和工业界工作站( 包括高档个人微机) 的数量急剧增长，用局域网连接 的工作站或机群被用于并行计算取代一部分集中式大型机。 工作站机群是利用现有的工作站资源，通过高速网络以某种结构连接起来而构成的 并行系统。由于其具有用户投资风险小、结构可扩展性好、用户可继承原有软件资源、 编程方便且构造简单等特点，在航天航空、石油勘探、地震预报等要求高性能计算的领 域得到了越来越广泛的应用。然而，工作站机群在具有系统资源共享特性的同时，也 有对某个( 些) 工作站资源的主人优先原则。某台闲置的工作站此时可用，而随故障， 负载和隶霭关系的影响，彼时不再可用，即具有变化特性。特别是随着系统规模的不断 华中科技大学硕士学位论文 扩大，其在计算过程中发生故障的几率会以指数级增长。对于大规模科学工程计算任务 来说，任务的计算时间比较长，一旦发生上述异常( 可视为故障) ，会导致并行计算的彻 底失败、此前的大量计算不再可用。为了避免这种计算上的损失，必须研究系统重构技 术，保证系统发生故障后能够不间断运行，并防止失效结点影响系统正常操作。当系统 检测并定位到故障后，隔离故障结点，重新配置系统并继续运行，以提高机群系统的可 用性。目前提高机群的可用性基本上有两种方法：增加机群正常运行的时间或减少故障 后修理的时间。如今工作站的正常运行时间可达几百甚至几千小时。然而再进一步提高 它的正常运行时间就非常难且花费很大：所以，只能尽最大程度地减少故障后修理的时 间。因此提高机群系统可用性的软件将成为机群操作系统中必不可少的部分。 本文的机群自动重构系统主要针对如何减少主服务器故障后系统恢复的时间和恢 复可能带来的过量负载迁移等问题来进行设计的。 研究这样一个课题的目的主要有： 1 在集中控制式机群的主结点发生故障的前提下，系统能以最短的时间在从结点中 选出机群的下一个主结点似的机群系统自动地重新工作，减少故障恢复的时间，从而最 大可能地提高机群的可用性。 2 如果机群主结点发生故障后的选出的下一个主结点的c p u 利用率很小且机器性 能好就可以避免由于机群平衡系统负载而频繁地负载迁移而带来的资源浪费，同时也可 以很好地解决服务器瓶颈问题。 3 为今后的进一步研究打下基础。 本系统的主要研制实验条件为： p c 机若干台； 操作系统r e dh a tl i n u x7 2 ； 并行编程环境p v m 3 4 3 。 1 4 论文的内容及组织 本文研究的方向是从软件方面来提高机群的可用性，减少机群中断服务的时间，同 时尽量避免过多的负载迁移，主要的研究内容包括以下几个方面： 华中科技大学硕士学位论文 1 负载指标的选择与结点负载的收集 负载指标被用来表示机群系统结点的负载情况。现在有的负载平衡方面的研究采用 单一的负载指标来度量结点的负载。虽然单一指标容易实现，但单一的负载指标不能适 应所有的问题。由于本文研究的是将负载信息引入机群环境下的机群自动重构机制。所 以，本文采用c p u 处理能力、c p u 利用率作为主结点选择研究的负载指标；在下一步的 优化研究中，可以采用多项负载指标来表示结点的负载情况，如：c p u 处理能力、c p u 利用率、c p u 进程队列长度、内存大小、内存使用情况和磁盘访问频度，以及i 0 速 度等。选择负载指标后，本文将提出各从结点同步收集自身负载信息并传送给主结点的 方法以及在l i n u x 操作系统环境下从用户层得到内核信息( 如c p u 利用率和c p u 进程队 列长度等) 的方法。 2 主结点对每个从结点负载信息的预测 本文采取主结点对每个从结点负载信息的预测，而不是采取每个从结点预测自己未 来某一时刻的负载值，是因为机群中每个结点c p u 性能不同，计算速度有快慢之分，即 使主结点发出了同步信号，但经过一番计算后再传送给主结点的预测信息就严重的不同 步了。 3 故障检测( 心跳机制) 与主结点选择机制 故障检测指的是检测故障和定位故障部件。本文用来检测故障的技术是心跳 ( c c a r s 咱e a r t b e a t ) 技术，即机群中的结点向其他别的结点发出一串心跳消息流。如 果系统没有收到来自一个结点的心跳消息流，便说明或是该结点或是网络连接发生了故 障。心跳机制的任务是在机群结点之间传送机群系统的有关信息，如结点失败、结点恢 复、加入或删除一个结点和在结点上启动或停止某项服务等，心跳可通过广播或多点播 送的方式传送。在收到心跳后，根据心跳附带中的信息，机群结点上运行的软件采取相 应的措施。 主结点选择机制是机群重构的关键技术。本文的主结点选择机制能在故障检测机制 报告主结点故障后立即工作，从而做到不需人工干预的真正意义上的机群自动重启。 本文的组织如下： 第一章为绪论，将介绍课题的研究背景、国内外的发展概况以及主要的研究内容等。 第二章将介绍机群可用性以及机群设计需考虑的问题，其中将重点介绍提高机群可 华中科技大学硕士学位论文 用性的几种技术；同时还将对两种典型的消息传递界面p v m 和m p i 进行详细地介绍和比 较。 第三章介绍机群故障检测以及主结点故障后的机群自动恢复机制：同时，数学推导 机群高可用与机群结点数目之间关系，为实验所需结点机的数目提供理论依据。设计思 想以及系统的组成结构。 第四章介绍负载信息收集及结点负载值的预先估算。 第五章将介绍c c a r s 系统的设计要求及系统模型和各模块的功能。 第六章给出实验环境，实验过程和结果分析。 第七章本论文的总结和今后工作的展望。 6 华中科技大学硕士学位论文 2 1 机群分类及研究热点 2 研究背景及相关概念 机群是全体计算机( 结点) 的集合，这些计算机由高性能网络或局域网( l a n ) 物 理地互连。典型情况下，每个计算机结点是一台s m p 服务器、一台工作站或是一台p c 计算机。更重要的是，所有机群结点必须能在一起集体工作，如同一个单一集成的计算 资源，除了满足由交互用户单独地使用每个结点的协定任务外。每个结点是是一台完整 计算机。这意味着每个结点有自己的处理器、高速缓存、磁盘以及某些i o 适配器。此 外在每个结点上留驻有完整、标准的操作系统。一个结点可以拥有多台处理器，但只有 一份o s ( 操作系统) 映像拷贝。以下一些划分方法可以较好及全面地反映机群的特征。 1 按主装方式划分，机群可分为紧密机群与松散机群“1 。 2 按控制方式划分，一个机群可采用集中控制与非集中控制或管理两种方式。 3 按同构性划分，机群有同构与异构之分。同构机群的各个结点采用的是相同的工 作平台，即它们有相同的处理机结构和相同的操作系统。这些结点般由同一厂家生产。 异构机群的各个结点采用不同的工作平台，所以在异构机群中互操作性非常重要。例如， 为保持负载平衡或可用性，常需要进程迁移。在同构机群中，一个二进制的进程映像可 以迁移到别的结点继续执行，但在异构机群中却做不到，因为当进程迁移到不同工作平 台的结点时，在新的平台上二进制代码不一定可执行。 4 按安全性划分，机群内各结点的通信连接方式可以为暴露式或隐蔽式两种。 5 按实际用途划分，机群将分成独用型和企业型两类“，也可分为高性能科学群集、 负载均衡群集和高可用性群集。通常，负载均衡集群适用于提供静态数据的服务，如h t t p 服务：而高可用性集群既适用于提供静态数据的服务，如h t t p 服务，又适用于提供动 态数据的服务，如数据库等。 其中将高可用性集群与负载均衡集群的组合使用是目前机群研究的热点。 华中科技大学硕士学位论文 2 2 机群设计要考虑的问题 在构造和使用一卜机群时，需要考虑几个重要的问题。尽管在这以前对这些问题已 作了大量的研究和开发工作，它们仍是目前活跃的研究和开发领域。这四个问题是：可 用性支持、单一系统映像、作业管理和高效通信，下面分别介绍。 1 可用性支持，机群通过大量冗余的处理器、存储器、磁盘、i l o 设备、网络及操 作系统映像等等，提供成本有效的高可用性。然而，为了挖掘这些多余资源的潜力，需 要使用一些可用性技术。 2 单一系统映像，一组由以太网联结起来的工作站不一定就是一个机群。一个机群 是一个单一系统。假定一个工作站有一个3 0 0 m f l o p s 的处理器，5 1 2 m b 的存储器，4 g b 的磁盘，可支持5 0 个活动用户和1 0 0 0 个进程。单一系统映像技术旨在达到这样一个目 标：将i 0 0 个上述的工作站组成机群，可以获得一个单一系统，等价于一台巨大的工作 站。这个巨大的工作站能拥有一个3 0 g f l o p s 的处理器，5 0 g b 的存储器，4 0 0 g b 的磁盘， 能够支持5 0 0 0 个活动用户和i 0 0 0 0 0 个进程。 3 作业管理，与传统工作站或p c 结点不高的利用率相比，机群要达到系统的高利用 率。作业管理软件需要提供批处理、负载平衡、并行处理、以及其他功能。 4 高效通信，为机群建立一个高效的通信子系统具有相当大的挑战性，原因有以下 几点： 第一：机群有较高的结点复杂性。 第二：机群内结点之间的物理线路较长。 第三：机群般使用有标准通信协议( 如t c p i p ) 的商品化网络，但t c p i p 协议 的系统开销很大。 在以上四个问题中，本文打算在现有的硬件条件下进行提高机群系统可用性的软件 设计。 2 3 提高机群可用性的软硬件技术 1 目前提高机群可用性的常用硬件技术是使用冗余n 0 1 ”部件，当主结点发生故障时 冗余部件取代主结点提供服务。设计者可以根据不同的成本、可用性和性能要求，按不 华中科技大学硕士学位论文 同方式组织冗余部件。常使用的有如下三种组织方法： ( 1 ) 热备用：由一个主要部件提供服务，一个冗余的备用部件不作任何工作仅处于备 用状态，但是它处于就绪( 热) 状态，一旦主要部件发生故障便代替它。另外还有一个 更经济的设计方法是多个主要部件使用一个备用部件。由于该备用部件处于空闲状态， 因此只要某个主要部件发生故障，备用部件就可迅速代替它。 ( 2 ) 相互替代：所有部件都是主要部件，它们都承担一些有用的工作负载。如果其中 一个发生故障，它的工作负载就会被重新分配给其它部件。这个方案的成本相对较低。 因为这个方案当中没有处于“通常闲置”状态的部件。但替代过程比较费时。 ( 3 ) 容错：这是一个最昂贵的配置，因为n 个部件提供的仅是一个部件的性能，而成 本超过n 倍。但是在这个方法中，在n - 1 个部件都发生故障时( 即只要有一个部件仍然 正常工作) 系统对用户来说还是可用的( 用户看不到发生的故障) 。 实现容错的方法有多种，使用特殊的容错硬件是有效的，但不易于加到现有的集群 系统中去；与应用相关的方法和原子事物处理需要特殊程序设计模型( 可能与消息传递 模型不兼容) 支持：活动冗余的方法适用于实时系统，但它需要使用额外的处理器。因 此这些方法都不能有效地应用于机群系统。 2 目前常用的软件技术有检查点“”1 和主结点选择“”等技术 检查点( 指的是定期将一个正在执行程序的状态存储在一个稳定的存储器内，以便 在故障后系统可以从该状态恢复。每个被保存的程序状态称为检查点) 设置与卷回恢复 ( c r r ，c h e c k p o i n t i n ga n dr o l l b a c kr e c o v e r y ) 技术作为一种后向恢复技术“5 。”1 ，通过在 系统正常运行过程中设置检查点( c h e c k p o i n t i n g ) ，保存系统当时的一致性状态，并对各 进程进行相关性跟踪和记录。系统发生故障后。将相关进程回卷( r o l l b a c k ) 到故障前系 统一致性状态( 检查点) ，经过状态恢复后从该检查点处重新执行( 而不是从程序开始执 行) ，实现对系统故障的恢复，从而节省了大量重复计算时间，充分体现集群计算机系统 的并行性能。另外，基于检查点的后向故障恢复机制可以避免由于从头开始执行程序而 引起计算上的大量浪费，充分提高集群系统的可用性。c r r 技术“”8 ”1 不仅可以对系统瞬 时间歇故障进行自动恢复，而且通过检查点文件镜像和进程迁移技术也可以容忍结点 的永久故障。为实现正确的检查点设置和卷回恢复，c r r 机制要求在检查点设置时保存进 程状态中决定程序运行正确性的关键内容，且各进程检查点信息与当时的各通信通道状 9 华中科技大学硕士学位论文 态应能够成一致性全局状态。卷回恢复时c r r 机制需要对丢失消息、孤儿消息和重复消 息进行处理，在避免多米诺骨牌效应( d o m i n oe f f e c t ) 和活锁( 1 i v e l o c k ) 现象的同时，保 证卷回恢复的正确性。对于一般并行分布系统来说，检查点设置与卷回恢复( c r r ) 协议 有很多，卷回传播和相关的多米诺效应是这些协议关心的焦点。现有的并行分布系统 c r r 协议大致可以分为两类： 1 ) 独立的检查点设置与卷回恢复协议： 2 ) 协调的检查点设置与卷回恢复( 简称c o c r r ) 协议。 在前一种协议中，各进程独立设置检查点而不需要相互间的协调，最大限度地满足 各进程的自主特性，但易引起多米诺效应。消息记录( m e s s a g e l o g g i n g ) 是避免多米诺 效应的有效手段。它利用分段确定性模型( p d m ，p i e c e w i s ed e t e r m i n i s t i cm o d e ) ，通过 消息记录和确定性重放机制避免了多米诺效应的发生。c o c r r 协议可以避免多米诺效 应，但是系统为了建立检查点，需要许多控制消息，同步建立检查点的通信代价较大。过 去的研究通常认为在系统正常操作过程中基于记录的独立检查点设置协议( 简称 l o g c r r 协议) 比c o c r r 协议代价小，因为它避免了为建立系统一致性状态而导致的同 步代价。而对于现代集群计算机系统来说，由于通信性能不断提高，而访问外存或稳定存 储设备代价仍然较大，用于消息记录的代价反而比协调建立检查点的代价要大。许多研 究和实验表明，对于运行在集群计算机上的计算密集型并行应用来说，c o c r r 协议性能 优于l o g _ c r r 协议。而对于通信密集型应用来说，此结论显然成立。并且c o c r r 协议具 有回卷距离短，实现简单，不需要对进程的分段确定性假设，且同时能容忍多个进程故障 的优点。 主结点选择技术是指当机群的主控结点发生故障后，可以从其它工作结点中自动选 出下一个主控结点，而恢复机群正常工作的技术。该技术是本文的研究重点之一。 2 4p v m 和m p i 的比较 作为基于消息传递韵并行计算环境渺2 ”，m p i 和p 、，m 在分布式计算中得到了广泛的 应用。p v m ( p a r a ll e lv i r t u a l m a c h i n e ) 的开发始1 9 8 9 年的美国o a kr i d g e 国家实验室 的一个研究项目，当前的参与机构包括美国o a kr i d g e 国家实验室、t e n n e s s e e e 大学、 l o 华中科技大学硕士学位论文 e m o r y 大学及c m u 等大学和研究机构，并得到了美国能源部、国家科学基金和田纳西州 政府的支持。p v m 建立在虚拟机的概念上，支持在异质结构和异构网络中的应用程序间的 通信，提供动态资源管理和任务的控制及分配的函数，其容错机制为需要长的运算时间 的大规模应用程序提供了便利。在异构的分布式计算中，应用p v m 更加适合。 m p l 0 2 1 ( m e s s a g ep a s s i n gi n t e r f a c e ) 是为了统一不同的m p p ( m a s s i v e l yp a r a ll e l p r o c e s s o r ) 厂家的消息传递的a p i ，由来自于高性能计算领域的专家和m p p 厂家的代表 组成的委员会制订的工业标准，1 9 9 4 年颁布了m p i - l ，1 9 9 7 年2 月颁布了m p i 一2 ，设计 的焦点是发挥m p p 的通信性能。当用户在单一的m p p 上开发和运行应用程序时，使用 肝i 能够直接利用船p 的内部的通信机制，通过应用m p i 提供的丰富的通信函数及逻辑 互连拓扑结构的任务分配的函数实现高效的通信。m p i 中引入了通信子的概念，支持并发 库的开发，支持线程。应用程序可以不需改变地移植到其他m p p 厂家的m p i 上。但在不 同的m p p 厂家的m p i 间，应用程序不能通信。m p i 也不提供容错的机制，m p i 仅能保证当 一个错误发生后，整个应用全部失败。两者的不同比较如下： 1 可移植性：m p i 具有可移植性，其可移植性是指在一个厂家的m p i 的环境下开发 的应用程序，可以在其他厂家的m p i 环境下重新编译后，没有改变的运行，我们称其为源 程序级的可移植，但其对运行在不同厂家的m p i 下的应用程序间的通信不提供支持，即 不支持异构网络和异质结构下m p i 上的应用程序间的通信。p v m 也提供源程序级的可移 植，另外还支持在异质结构和异构网络中的应用程序间的通信，即在不同厂家的p 上 及在相异的网络环境上运行在p v m 下的应用程序间均可通信。另外，p v m 支持用c 语言 和用f o r t r a n 语言开发的p v m 的应用程序间的通信，而m p i 不支持。当然p v m 是以牺牲 性能来实现这一功能的，p v m 的库函数必须识别每一个消息的目的地地址，确定其为相同 的结构或为异构，从而采取本地通信或网络通信的方式。 2 资源管理：由于p v m 建立在虚拟机的概念上，因此p v m 可以方便地对整个虚拟机 中的资源进行管理。使用p v m ，用户既可通过p v m 控制台也可在应用程序中增加或删除 计算资源( 即主机) 。同时，p k m 提供了动态查询和管理虚拟机的中的各个任务及主机的 状态的函数，从而使用户的应用程序可以通过与p v m 虚拟机的动态交互，管理自己的计 算环境，为实现计算环境的负载平衡、任务迁移和容错提供了强有力的支持。 m p i 强调消息传递的通信性能，对资源管理不支持。 华中科技大学硕士学位论文 3 安全通信的上下文和多线程：对于支持并发的库，仅使用消息标签和发送、接受 者的识别号并不能保证消息的正确传递，考虑图2 1 中的情况。当任务1 和任务2 中的 用户代码和库函数用同一个标签发送消息时，如图中虚线所示，消息将被错误的接收，其 中实线表示正确的接收次序。为了解决这一问题，m p i 提供第三个标签以区别用户消息和 库函数发送的消息，称其为通信的上下文。同时，m p i 引入通信子的概念，所谓通信子就是 一组具有同一上下文的任务与通信上下文的绑定。任何一个运行的任务都属于一个任务 组，即共享一个共同的通信上下文，因此当一个任务组中的一个任务失败后，这个公共的 通信上下文也失效，从而整个的应用将失败。这就是m p i 不能从失败中自动恢复的原因。 m p i 通过引入通信子，支持并发库的开发，支持多线程应用。 任务l任务2 s e n d ( 2 ，t a g ) c a i il i b c a l ll i b l i b ： jl i b ： s e n d ( 2 ，t a g ) k 口e c v ( 2 ，t a g )、 -r 、 酞。( 2 ， 图2 1 渭息错误接收情况 p v m 3 4 类示于m p i ，也提供了使一组任务获得唯一的上下文标签的函数。在p v m 中，当属于一个任务组( 具有唯一的上下文标签) 的一个任务的失败后，容许一个新的 任务使用这个唯一的上下文，从而提供了容错的功能，但也引入了冲突的可能。例如当一 个任务的失败导致了整个任务组失败，其拥有的唯一的上下文标签被释放，此时一个具 有此上下文的新任务的生成将引起冲突。另外。p v m 的消息缓冲区也有隐藏的状态，因此 在其上开发多线程的应用是非常困难的。 4 通信方式：p v m 的提供点到点的通信和集合通信二类通信方式。在点到点的通信 中，p v m 的发送只有阻塞式的发送( 但其为与p v m d 问的阻塞，即发送给p v m d 后返回，并 非传统意义上的等待接收者接收后的阻塞) ，接收有阻塞式和非阻塞式二种。在集合通信 中，p v m 提供了广播、组内广播、组内同步及一些全局操作函数。其中广播和组内广播为 阻塞式( 与发送的阻塞含义相同) 。相比之下，m p i 在点到点通信和集合通信二方面都提供 了更多的通信函数和更强大的通信功能。在点到点通信方式中，发送和接收都有阻塞和 1 2 华中科技大学硕士学位论文 非阻塞两种。集合通信提供了更多的全局操作函数。另外，m p i 中也提供对于不同类型的 数据建立导出数据类型的函数。m p i 一2 中又提供了非阻塞的集合通信及单向通信函数如 p u t 、g e t 等，进一步增强了m p i 的通信的功能。 5 容错：在大规模的科学计算中，计算环境提供容错是非常重要的。例如一个运行在 工作站集群上的需运行几周才能完成的模拟算法，当其中的一台工作站因某种原因崩溃， 若不提供好的容错机制，用户将不能确定当前的应用程序已经停止或失败。p v m 提供了容 错的基本机制。用户程序可以应用函数p v m _ n o t i f y 0 向p v m 虚拟机登记，使在虚拟机状 态改变或任务失败时，向其发送消息。这样，当虚拟机中增加结点( 主机) 、删除结点( 主 机) 或任务失败时，登记的任务将收到相应的消息，从而能够采取相应的策略，重新调度 任务的分配或重新生成一个失败的任务。m p i - i 中没有提供容错的策略。在m p i 一1 中， 任务和主机均是静态的，应用程序必须以一个任务组的方式运行。当任务组中的一个任 务或计算资源失败后，整个应用程序都将失败，这保证了当一个应用程序失败后，系统中 没有残留或挂起的任务。但对于失败管理和恢复显然是不足的。m p i - 2 提供了p i s p a w n0 以动态地生成任务，但仍未提供从失败中自动恢复的机制，主要原因是在m p i 中通信予 是以同步方式被创建和释放的。 2 5 小结 本章介绍了机群与机群可用性的一些概念，介绍了机群设计需考虑的问题和提高机 群可用性的几种技术。本章同时还对两种典型的消息传递界面p v m 和m p i 进行了详细地 介绍和比较。 华中科技大学硕士学位论文 3 集中式机群高可用性研究 一个机群系统一般都将发生预期停机或断电等带来的故障( 故障前能正常运行一段 时间) ，接下来故障系统被修复，然后系统恢复正常工作。系统不断重复着这个运行一一 修复周期。系统的可靠性可表示为直到发生故障的平均时间( m t t f ：m e a nt i m e t o f a i l u r e ) ，即在系统( 或系统的一个部件) 发生故障前正常运行的平均时间。可维护性 指标为直到修复的平均时间( m t t r ：m e a nt i m et or e p a i r ) ，即用于修复系统和在修复 后将它恢复到工作状态所用的平均时间。系统的可用性可表示为：m t t f ( m t t f + m t t r ) 。 分析可用性的定义可知提高可用性的方法有：增加m t t f 或减小m t t r 。对于前者，只