（计算机软件与理论专业论文）基于ftmpi和纠删码的并行程序容错机制研究与性能优化.pdf

摘要 摘要 近年来，高性能计算( h i g hp e r f o r m a n c ec o m p u t i n g ，h p c ) 系统在规模和 拥有的处理器数量上有迅速增长的趋势。而系统出现故障的可能性也随之大大 增加。如何设计高效可靠的容错机制已经是高性能计算领域中迫切需要解决的 问题。m p i ( m e s s a g ep a s s i n gi n t e r f a c e ) 是高性能计算系统中事实上的编程规范。 在多种包含进程级容错功能的m p i 实现中，f t m p i 【7 检查点恢复机制的系统 开销较低。然而其容错机制并非对用户透明，恢复阶段对m p i 通信域和用户数 据的恢复需要在应用程序一级实现。 本文基于f t m p i 运行时环境和多种纠删码( r a 彻r a i d 5 r d p b c o d e ) ， 实现了一种轻量级的m p i 程序容错机制。根据对系统开销和容错要求的不同， 用户可以选用基于不同编码设计的检查点恢复接口，能够在系统中多个进程或 者节点故障的情况下实现运算中间数据的自动恢复。 通过对消息传递系统中主流容错机制的充分研究，我们选定了基于纠删码 的内存协同检查点协议作为设计各检查点恢复接口的解决方案。在做检查点时， 接口根据某种编码把处于同一条纹中的数据按位异或后得到冗余数据，保存在 某个冗余进程或者散布于各个进程中。按照协同检查点协议，各个工作进程在 相同的位置调用检查点接口，系统每一时刻只保存最近的一个检查点。恢复时， f t m p i 首先恢复m p i 运行时环境和m p i 库的状态，然后应用程序调用恢复接 口，从之前保存的内存检查点数据中通过解码恢复重启进程的检查点数据，使 得整个程序回滚到上一次做检查点的状态并继续运行。 本文将多种接口的性能进行了比对，包括调用接口的时间开销，以及引入 检查点机制对于系统资源的占用。测试中发现，各检查点恢复接口的效率主要 取决于接口中调用的m p i 组通信函数。本文将对接口测试中性能差异的原因进 行详细的描述，并给出相应的优化方案。通过对各种接口在f t m p i 环境下的测 试，发现接口性能良好，开销较小，证明了这种检查点恢复机制实际应用于分 布式计算系统中的可行性。 关键词：m p i ，f t m p i ，r a i d ，纠删码，r d p ，b c o d e a b s t r a c t a b s t r a c t r e c e n t l y ，t h e r ei sat r e n dt h a tt h eh i g l lp e r f o r m a n c ec o m p u t i n g ( h p c ) s y s t e m s g r o w sr a p i d l yi ns c a l e ，w h i c hl e a dt oas h a r pr i s eo fp o s s i b i l i t ys y s t e m st h i sk i n d f a i l u r e s i t sa l r e a d yb e e na ni m p e r a t i v ep r o b l e mt h a th o wt od e s i g na ne f f i c i e n ta n d r e l i a b l ef a u l t t o l e r a n ts c h e m ef o rt h eh p c s m p i ( m e s s a g e p a s s i n gi n t e r f a c e ) i st h e d e - f a c t op r o g r a m m i n gs t a n d a r di nt h eh p c f i e l d f t m p i 7 h a sam u c hl o w e r s y s t e mc o s tp a i df o ri n t r o d u c et h ec h e c k p o i n t r e c o v e rs c h e m e ，c o m p a r i n gw i t ho t h e r m p i i m p l e m e n t a t i o n s ，y e ti t ss c h e m e sn o tt r a n s p a r e n tt ot h eu s e r s i t st h e r e s p o n s i b i l i t yo ft h ep r o g r a m st os a v eac o o r d i n a t e dc h e c k p o i n to ft h es y s t e m ，a n dt o r e c o v e rt h em p ic o m m u n i c a t o r sa n dt h ei n t e r m e d i a t eu s e rd a t aa f t e rs o m ep r o c e s s f a i l e d b a s e do nf t m p ir u n - t i m ee n v i r o n m e n ta n dm u l t i p l ee r a s u r ec o d e s ( r a d 4 瓜a i d 5 r d p b - c o d e ) ，w ei m p l e m e n t e dal i g h t w e i g h tf a u l t t o l e r a n ts c h e m e f o rt h em p ip r o g r a m s t h eu s e rc a nc h o o s ed i f f e r e n ti n t e r f a c es u i t ef o rt h e i rn e e d sf o r o v e r h e a da n df a u l t t o l e r a n t t h ei n t e r f a c et h e yc a l l e ds a v e sa n dr e c o v e r st h e i r i n t e r m e d i a t ed a t a a st h es o l u t i o n ，w eh a v ec h o s e nt h ei n - m e m o r yc h e c k p o i n tp r o t o c o l ，w h i c h i m p l e m e n t a t i o nr e l i e so ne r a s u r ec o d e s w h e nt h ec h e c k p o i n ti n t e r f a c ei sc a l l e d ，i td o x o r o p e r a t i o n st ot h ed a t ab l o c k sb e l o n g i n gt ot h es a m es t r i p e ，a n ds a v et h ep a r i t yi n as p e c i f i cp r o c e s so rd i s p e r s et h e mt oe a c hp r o c e s s e a c hp r o c e s sc a l lt h ec h e c k p o i n t i n t e r f a c ea tt h es a m ep o s i t i o n ，a c c o r d i n gt ot h e c o o r d i n a t ec h e c k p o i n tp r o t o c o l ，t h u s o n l yo n ec h e c k p o i n ti ss a v e da ta n yt i m e w h e ns o m ep r o c e s sf a i l e d ，f i r s tf t m p i r e c o v e r st h er a n t i m ee n v i r o n m e n ta n dt h em p i l i b r a r ys t a t e ，t h e nt h ep r o g r a mc a l l t h er e c o v e ri n t e r f a c et or e c o v e rd a t af r o m c h e c k p o i n ts a v e d ，l a s t l yt h ep r o g r a m r o l l b a c kt ot h es t a t ew h e nl a s td i dc h e c k p o i n ta n dc o n t i n u e w ec o m p a r e dt h ep e r f o r m a n c eo ft h ei n t e r f a c es u i t e s ，i n c l u d i n gt h et i m ec o s tf o r c a l l i n gt h ei n t e r f a c e ，a n dt h eo c c u p a t i o np r o p o r t i o nf o ri n t r o d u c i n gt h es y s t e m r e s o u r c e s 。w ef o u n di ti st h em p ic o l l e c t i v ef u n c t i o n st h a tm o s ti m p a c tt h ee f f i c i e n c y i i a b s t r a c t o ft h ei n t e r f a c e s i nt h i sp a p e r , w ew i l lg i v ed e t a i l e dd e s c r i p t i o na n dr e a s o no ft h e p e r f o r m a n c ed i f f e r e n c ea n do p t i m i z e da l g o r i t h m a r eg i v e nw h e nn e e d s i ti sf o u n d t h e s ei n t e r f a c e sa r ew e l lf u n c t i o n e da n dh a v er e l a t i v e l yl o wc o s t ，t h u sp r o v e dt h e p o s s i b i l i t yf o rt h ep r a c t i c a lf e a s i b i l i t yo ft h i sf a u l t t o l e r a n ts c h e m e sw ep r o p o s e da n d i m p l e m e n t e d k e y w o r d s ： m p i ，f t m p i ，r a i d ，e r a s u r ec o d e ，r d p ，b - c o d e i 图目录 图2 1 图2 2 图2 3 图2 4 图2 5 图2 6 图3 1 图3 2 图3 3 图3 4 图3 5 图3 6 图3 7 图3 8 图3 9 图3 1 0 图3 11 图3 1 2 图3 1 3 图4 1 图4 2 图4 3 图4 4 图4 5 图4 6 图4 7 图4 8 图4 9 图目录 连锁回滚操作与多米诺效应示意4 乐观日志示例6 悲观日志示例7 各种回滚一恢复协议的比较8 h a r n e s s 和f t - m p i 结构1 0 f t m p i 虚拟机( v m ) 架构1 1 基于马尔科夫链的r a i d 5 阵列可靠性模型1 8 r a i d 0 编码。1 9 r a i d l 编码2 0 r a i d 2 编码一2 0 r a i d 3 编码。2l r a i d 4 编码一2 l r a i d 5 编码。2 2 r a d 6 编码2 3 二维奇偶校验编码2 5 6 块盘的r d p 编码2 7 b c o d e 的编码规则2 7 b 2 n 编码2 8 b 2 。对偶编码2 8 r a d 4 编码图n = 5 3 0 r a i d 4 在m p i 中实现设计图3l r a i d 4 实现恢复流程图3l r a i d 5 编码示例n = 5 3 2 r a i d 5 在m p i 容错中的实现设计图3 2 r a i d 5 恢复流程3 3 总进程数为4 的砌) p 编码构造3 4 r d p 编码非冗余进程双故障示意3 5 r d p 编码非冗余进程双故障恢复过程3 6 v i 图目录 图4 1 0 图4 1 l 图4 1 2 图4 1 3 图4 1 4 图4 1 5 图4 1 6 图4 1 7 图5 i 图5 2 图5 3 图5 4 图5 5 图5 6 图5 7 图5 8 图6 1 r d p 编码接口流程3 7 b c o d e 编码产生方法示意3 9 完全图的完美一因子分解4 0 顶点为6 的完全图的完美一因子分解4 0 基于完美一因子分解的瞄边标号4 0 b 5 编码。4 l b 4 编码4 1 b c o d e 编码恢复示意4 2 引入各检查点接口后c p u 占用率比较4 5 引入检查点机制后内存占用比较4 6 检查点机制总开销4 7 检查点接口函数调用外的开销一4 8 检查点接口函数总开销4 8 恢复接口耗时一4 9 r d p 恢复接口在各种故障情况下的性能5 0 两种r d p 双数据进程故障算法时间开销比较5l 四种编码所属类别5 4 v 南开大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，进行 研究工作所取得的成果。除文中已经注明引用的内容外，本学位论文 的研究成果不包含任何他人创作的、已公开发表或者没有公开发表的 作品的内容。对本论文所涉及的研究工作做出贡献的其他个人和集 体，均已在文中以明确方式标明。本学位论文原创性声明的法律责任 由本人承担。 学位论文作者签名： 年月日 南开大学学位论文使用授权书 根据南开大学关于研究生学位论文收藏和利用管理办法，我校的博士、硕士学位获 得者均须向南开大学提交本人的学位论文纸质本及相应电子版。 本人完全了解南开大学有关研究生学位论文收藏和利用的管理规定。南开大学拥有在 著作权法规定范围内的学位论文使用权，即：( 1 ) 学位获得者必须按规定提交学位论文( 包 括纸质印刷本及电子版) ，学校可以采用影印、缩印或其他复制手段保存研究生学位论文， 并编入南开大学博硕士学位论文全文数据库；( 2 ) 为教学和科研目的，学校可以将公开 的学位论文作为资料在图书馆等场所提供校内师生阅读，在校园网上提供论文目录检索、文 摘以及论文全文浏览、下载等免费信息服务；( 3 ) 根据教育部有关规定，南开大学向教育部 指定单位提交公开的学位论文；( 4 ) 学位论文作者授权学校向中国科技信息研究所和中国学 术期刊( 光盘) 电子出版社提交规定范围的学位论文及其电子版并收入相应学位论文数据库， 通过其相关网站对外进行信息服务。同时本人保留在其他媒体发表论文的权利。 非公开学位论文，保密期限内不向外提交和提供服务，解密后提交和服务同公开论文。 论文电子版提交至校图书馆网站：h t t p ：2 0 2 1 1 3 2 0 1 6 1 ：8 0 0 1 i n d e x h t m 。 本人承诺：本人的学位论文是在南开大学学习期间创作完成的作品，并已通过论文答辩； 提交的学位论文电子版与纸质本论文的内容一致，如因不同造成不良后果由本人自负。 本人同意遵守上述规定。本授权书签署一式两份，由研究生院和图书馆留存。 作者暨授权人签字： 2 0年月日 南开大学研究生学位论文作者信息 论文题目 姓名学号答辩日期年月 日 论文类别博士口学历硕士口硕士专业学位口高校教师口同等学力硕士口 院系所专业 联系电话 e m a i l 通信地址( 邮编) ： 备注：是否批准为非公开论文 注：本授权书适用我校授予的所有博士、硕士的学位论文。由作者填写( 一式两份) 签字后交校图书 馆，非公开学位论文须附南开大学研究生申请非公开学位论文审批表。 第一章绪论 第一章绪论 第一节m p i 程序容错机制背景 当前，高性能分布式计算系统的规模正在迅速增长，某些系统包含了成千 上万个处理器。基于t o p 5 0 0 1 在2 0 0 3 年7 月的统计，t o p 5 0 0 系统中有5 4 8 包含的处理器个数在1 2 9 - - , 51 2 之间。到2 0 0 7 年1 1 月，已经有5 3 6 的系统包含 了1 0 2 5 - 2 0 4 8 个处理器，功能最强的系统中的处理器个数则超过了2 万个。 伴随着规模的增长，系统中软硬件失效的可能性也大大增加了。【2 】中列出 了3 台高端h p c 系统在可靠性方面的表现：l a n la s c i sq ( 8 1 9 2 个c p u ) 的 平均故障间隔( m e a nt i m eb e t w e e ni n t e r r u p t s ，m t b i ) 仅为6 5 小时，l l n la s c i w h i t e ( 8 1 9 2 个c p u ) 的m t b i 为5 0 小时，而p i t t s b u r g hl e m i e u x ( 3 0 1 6 个c p u ) 的m t b i 为9 7 小时。为了处理如此频繁的故障，需要考虑在系统软硬件的设计 中加入容错( f a u l t - t o l e r a n t ) 机制。使用特殊的容错硬件是一种有效的方法，但 是可扩展性不强，彳 宜加到已有的集群系统中；硬件冗余的方法纠错速度快， 适用于实时系统，但是需要使用额外的处理器；一些专用的与应用相关的容错 软件则需要特殊的程序设计模型支持，可能会与消息传递模型不兼容，因此这 些方法都不能有效地应用于集群系统。 m p i ( m e s s a g ep a s s i n gi n t e r f a c e ) 标准 3 由m p i 论坛( m p if o r u m ) 于1 9 9 4 年发布，新的标准m p i 2 于1 9 9 7 年2 月颁布，具有一致性好，功能强大，效率 高等优点。当集群规模从几十个结点扩大到几百个甚至几千个结点时，m p i 仍 是一个在计算平台上进行编程的简单有效的方式。然而随着集群规模的不断扩 大和结点数的增加，计算过程中出现故障的几率也成指数阶增长，系统软件升 级，节点更换等维护操作这些异常事件都会引起应用程序出错。而异常关机， 节点故障虽然并不经常但极有可能发生，例如由于热度可能引起的节点间歇故 障。大型的科学工程计算的任务执行时间都比较长，一旦某计算节点发生上述 异常事件，将导致系统失效，程序不得不从头开始运行，从而引起计算资源的 大量浪费。为了避免这种重复，不仅应当提高集群的有效性和可靠性，还要求 m p i 实现的运行时环境具有容错能力，保证在发生各种异常事件或故障时，为 用户提供持续的服务。 第一章绪论 目前已经存在多种拥有容错机制的m p i 实现。如c o c h e c k 4 】，s t a r t i s h 5 ， m p i c h v 6 】，f t m p i 7 等等。这些实现所提供的容错机制大多是在基于回滚一 恢复的内存检查点协议上开发的。对于如何将r a i d 技术中的纠删码应用于m p i 环境的进程节点故障恢复，文献【8 ，9 ，1 0 ，l l 】做了大量的讨论。 第二节本论文的工作与结构 本文主要描述了基于f t m p i 库及冗余磁盘编码理论的m p i 应用程序用户 检查点接口。完成了以下工作： 1 深入分析了当前主流m p i 实现中采用的容错机制，特别是基于回滚一恢 复的内存协同检查点协议。 2 充分研究了r a i d 容错编码技术，并选择几种理论性能较好的单双容错 纠删码作为设计检查点恢复接口的理论基础。 3 扩充了f t m p i 库，实现了基于多种容错编码的检查点恢复接口，并对 接口中影响效率的关键算法进行了优化。 4 通过实验对几种容错接口的性能进行了比较，包括引入各检查点机制后 m p i 应用程序在c p u 内存方面的开销，检查点恢复接口的时间开销。 用户可以通过这样的分析结果，在不同的容错要求和环境下采用不同的 检查点恢复接口。 以下各章组织如下： 第2 章介绍主流m p i 实现中的容错机制，重点介绍f t m p i 刁 同于全局检 查点日志方案的轻量级系统恢复机制。 第3 章介绍了r a i d 研究领域的冗余编码技术，重点介绍了本文设计用户数 据检查点恢复接口所采用的几种- 幺q c d q 码技术( r a i d 4 ，r a i d 5 ，r d p ，b c o d e ) 。 第4 章介绍基于各种磁盘编码方案的用户数据检查点恢复接口的设计与实 现，并对算法效率进行了分析。 第5 章对各种接口的性能进行了测试，并通过对测试结果的分析，将几种 编码方案不同方面的系统开销进行对比。 第6 章总结全文，并指出将来可以进行的研究方向。 最后列出了本文所参考的文献，以便于对该问题相关知识的进一步查阅。 2 第二章m p i 容错机制研究 第二章m p i 容错机制研究 当今高性能计算平台的规模以及拥有的处理器数量都经历着快速的增长， 这种增长伴随着网络带宽的提高，使用户所能使用的计算资源也随之增长。对 于网格计算或是元计算这样并行应用计算资源的技术，进一步增加了单个任务 中可以应用的处理器数量，从而也使得系统中参与计算的处理器或是网络连接 失效的可能性大大提高了。早期的大规模并行处理系统中，某个节点的崩溃会 带来整个系统的崩溃。当前的系统在健壮性上有所改进，单个处理器或是进程 的崩溃并不意味着系统的崩溃，但是之上所运行的程序只能退出。网格系统同 样存在这个问题。 m e s s a g ep a s s i n gi n t e r f a c e ( m p i ) 规范是科学计算领域事实上的通信标准。 但是，m p i 规范本身缺乏对容错恢复的支持。当前的处理模式有两种，默认的 模式是立刻中止程序。另一种模式是将控制权交回应用程序，但是不对之后的 进程问通信做任何的保证。后一种模式意图使程序在退出之前能够做一些处理， 例如关闭打开的文件。近年出现了许多基于不同机制实现容错恢复的m p i 实现 如c o c h e c k 4 ，s t a r f i s h 5 】，m p i c h v 【6 】等等。f t m p i 7 也在其中，它是我们 实现用户检查点恢复接口的基础。本章将对分布式计算平台中常见的几种容错 机制做简要介绍，并简要分析了基于f t m p i 系统的轻量级m p i 程序进程级容 错机制。 第一节消息传递系统中的回滚恢复协议 规模和计算能力的快速增长使得分布式计算系统容易出现故障。人们开发 出了包括事务，组通信和回滚恢复在内的多种技术，使分布式系统的可靠性和 可用性得到了提高。这几种技术各有利弊。其中回滚恢复技术将分布式系统看 做是网络通信连接在一起的一组应用进程。系统周期性的将各个进程的状态存 至稳定存储中，并在恢复时使重启进程恢复到先前的一个状态，任一个保存的 状态都称为一个检查点( c h e c k p o i n t ) 。本节介绍基于回滚恢复技术的一些容错 机制实现方式。 第二章m p i 容错机制研究 2 1 1 基于检查点的回滚恢复协议 在基于检查点的方法中，计算的状态作为检查点会被周期性的保存起来。 故障发生时，计算就从这些检查点当中的一个重新开始。根据不同进程间合作 方式的区别，基于检查点的协议可以从广义上分为三种：不协同检查点，协同 检查点和通信迫使检查点。本节对这三种检查点的主要特点做简单介绍。 2 1 1 14 协同检查点 在不协同检查点( u n c o o r d i n a t e dc h e c k p o i n t i n g ) 中，每个进程都独立的保存 其自己的状态。重启期间，在这些进程保存的检查点的集合中搜索一个适合的 状态集。这种方式主要的优势就在于检查点的保存能够在系统最方便 ( c o n v e n i e n t ) 的时候发生。不协同检查点容易受到连锁回滚操作的影响，这种 多米诺效应( 图2 1 ) 会导致系统回滚到计算的初始，造成大量有用计算工作的 浪费。这种连锁回滚操作使得对于每个进程来说，仍旧有必要保存多个检查点， 这种做法会潜在的造成一个很庞大的存储代价( s t o r eo v e r h e a d ) 。由于这种检查 点机制中回滚操作有着极大的代价，使得不协同检查点方式不适用于我们的需 求。 r 舵o v e t yl i n e a 致 图2 1连锁回滚操作与多米诺效应示意 2 1 1 2 协同检查点 协同检查点( c o o r d i n a t e dc h e c k p o i m i n g ) 需要各进程调整各自的检查点保存 时间，以形成一个一致的全局状态。协同检查点简化了故障恢复的过程，因为 4 第二章m p i 容错机制研究 它不需要再受制于回滚操作。同时它只需要一个检查点，所以也最小化了存储 的代价。c o c h e c k ，s t a r f i s h 和c l i p 都是通过使用协同检查点进行容错的m p i 版 本。协同检查点的主要缺陷就在于保存检查点时会有很大的延迟，因为在检查 点写入稳定的存储区之前需要确定一个一致的检查点。 2 1 1 3 通信迫使检查点 通信迫使( c o m m u n i c a t i o ni n d u c e d ) 检查点通过迫使进程从其他进程获得应 用程序消息的方式，在做额外检查点来防止多米诺效应的时候，允许各进程有 各自独立的检查点。然而，它要求在每个进程在处理接受的消息内容前做检查 点，可能会导致很大的延迟。 2 1 2 基于日志的回滚恢复协议 基于日志的回滚恢复协议将进程的执行过程划分为若干个确定的执行间 隔，每个执行间隔的开始是一个不确定事件的发生。不确定事件可以是从其它 进程接收到的一个消息，但是本进程发送消息则不视为不确定事件。以图2 2 为 例，我们可以认为进程p 0 的执行过程有四个确定的执行间隔。第一个间隔的开 始是进程的创建，另外三个间隔的开始分别为消息m o ，m 3 和m 7 的接收。消息 m 2 的发送可以由p 0 的创建和消息m o 的接收所确定，因此并彳 是不确定事件。 系统未出错的时候，每个进程将接收到的不确定事件写入日志，同时也会 将确定的时间间隔当中进程的状态存为检查点。错误发生后，系统利用存储的 日志及检查点数据恢复系统状态。按时间顺序排列的各个不确定事件中，如果 某个不确定事件之后的执行间隔中没有存储的检查点数据，且这个不确定事件 发生的时间最早，则系统恢复至接收这个不确定事件时的状态。 如果某个进程的状态依赖于某个不确定事件的发生，但系统恢复后无法重 现此事件，称这个进程为孤儿进程。基于日志的回滚恢复协议保证恢复后系统 中不存在孤儿进程。协议的实现主要有乐观口志，悲观日志和因果日志三种。 由于实现上的差别，这三种日志对系统无错运行时的性能，输出延迟，恢复算 法复杂度等因素都有相应的影响。 2 1 2 1 乐观口志 乐观口志协议中，每个进程异步把确定的时间间隔中的状态写为检查点， 第二章m p i 容错j o t * j 研究 检查点存放在一个口志中，周期性的写入持久存储。此协议基于乐观的假设， 即写日志会在系统发生错误前完成，因此不需要程序在日志被写入前阻塞，从 而在系统无错时的开销较小。然而系统恢复时会比较复杂。如果某进程出错， 其日志中存放的检查点数据可能会丢失；而如果其中保存的确定时间间隔中有 对其它进程的发送操作( 对于其它进程来说的某个不确定事件) ，则相应进程 的以此不确定事件为开始的确定时间间隔无法恢复，即使这段间隔有相应的检 查点数据。另外，如果出错的进程在某个间隔中发送了一条消息，但又没有恢 复此间隔的相应检查点数据，则接受这个信息的进程为了避免成为孤儿进程， 必须回滚到接受此信息前的状态。 以下图为例。假设当前消息m 6 和m 7 都已经发出并接收。如果进程p 2 出 错，此时p 2 并未将不确定消息m 5 写入持久存储，因此需回滚到接受m 5 之前 的状态。此时p l 成为孤儿进程，因为p 2 恢复到没有发送m 6 的状态，p 1 也需 要回滚到未接收m 6 时的状态，同样，p 0 需要回滚到接受m 7 前的状态。 r 危 c 图2 2乐观日志示例 2 1 2 2 悲观日志 悲观日志的设计基于这样的假设，即计算过程中进程可能在任一不确定事 件的发生后出错。这个假设被称为“悲观”的，因为现实中进程出错并非常见。 此种协议实现保证在每个不确定事件对计算过程产生实际影响时，都已被记录 在日志中。 如下图所示，如果在消息m 7 被接收后有进程如错，那么由于m 7 及之前的 所有发生过的不确定事件 m o ，m l m 7 幂i 相应的确定执行间隔的检查点都已经 写入口志，我们可以通过保存的最近一个检查点数据来恢复出错前各进程的执 6 第二章m p i 容错机制研究 行情况，最后可以将系统恢复为p 0 进程接收消息m 7 之后的状态( 图中用斜线 充填的方块代表) 。 这种口志的优点是系统可以从最近一个检查点数据开始恢复，恢复过程相 对简单，而且不用考虑因为孤儿进程而所需的回滚。缺点是为保证在每个不确 定事件在对计算过程产生实际影响前都已被记录在口志中，各进程写口志是同 步的，会带来相应的开销。 ， m a x i a m mr e c o v e r a b bs t a t e p t 图2 3悲观口志示例 2 1 2 3 因果日志 因果臼志吸收了上述的优点。它即像乐观日志一样避免了对稳定存储的同 步读写，又像悲观日志一样允许各进程独立的提交输出，且不会出现孤儿进程。 因此使得应用进程不会受到其它进程错误的干扰。而月因果口志仅存放最近的 检查点数据，能够使得存储和工作量的开销最小化。因果日志也是实现较为复 杂的一种恢复协议。 2 1 3 各种回滚恢复协议的比较 各种回滚恢复协议在性能开销，存储开销，垃圾收集机制实现的难易，恢 复机制的简单程度，是否存在多米诺效应等各方面都不尽相同。下表分析了各 种协议在不同方面的特征。 7 第二章m p i 容错机制研究 非协同协同检查通信迫使检 悲观日志乐观兀志因果日志 检查点点查点 垃圾收集机制复 杂程度 复杂简单复杂简单复杂复杂 每个进程所做检 查点数量 菪干一个若干一个若干一个 有无多米诺效应可能 无 无 无 无无 有无可能产生孤 可能无可能 无 可能无 儿进程 上一次全可能回滚几上一个检 可能回滚 上一个检 回滚位置无限几个检查 局检查点个检查点查点查点 点 恢复机制复杂度复杂简单复杂简单复杂复杂 图2 4各种回滚恢复协议的比较 从表中可以看出，在多种回滚恢复协议中，从存储开销，恢复机制复杂度， 回滚位置等多个方面来说，协同检查点都是较优的一种选择。我们在设计检查 点恢复接口时也采用了这样的机制，任务中每个进程在其某阶段的任务完成后 在程序的相同位置统一做检查点。这样仅需在系统中保存一个检查点，大大减 少了内存开销，并且恢复时的算法也相对简明。 2 1 4 内存检查点相比于磁盘检查点的优势 回滚一恢复协议中，做检查点时所保存的数据既可以保存在内存中，也可以 保存在磁盘等稳定存储中。采用磁盘检查点的系统中，磁盘的i o 读写操作是主 要的开销【1 1 】。虽然超高速的存储介质已经出现【1 2 】，其性能在可预见的将来还 会提高【1 3 ，c p u 和存储设备的性能匹配仍然会是长期的问题。内存检查点相对 于磁盘检查点在各方面的优势主要有下面两点： 1 时间开销较低 磁盘检查点常用的日志、消息方法实现，都有一定的复杂性，检查点信息 都是都是存储在分布式存储系统中，大多都是共享的高可用磁盘数据服务器( 存 8 第二章m p i 容错机制研究 储检查点信息) ，涉及的磁盘i o 也是远程读写，开销比本地i o 也要大。而内 存检查点都是在本地内存当中，故障的话也只是通过通信开销编码恢复，只是 体现在通信开销上，一般远低于磁盘检查点方案的时间开销。 2 不存在单节点故障问题 采用磁盘检查点方案的架构中，少不了可靠的网络共享存储。因为如果进 程重启存原位的话，可以利用本地存储，但如果是节点故障就无法解决。而这 种共享存储服务器一旦故障，整个应用程序将无法恢复。内存编码方案不存在 这个问题，重启的进程可以在环境中任意散布都能恢复，不需要额外的存储系 统，不会出现单节点故障的瓶颈。 内存检查点方案尤其适用于应用程序中间数据不是十分庞大的并行计算， 所谓中间数据，是指前面计算工作已完成的，被后续工作所需的计算数据，而 不是所有待计算的数据。如果每次的中间数据庞大，也就是在每次参与检查点 接口运算的数据比较庞大，在具体的编码解码的节点上，内存会存在瓶颈，会 带来过大的内存开销。对于每次计算数据不是很庞大的并行计算，该方案由于 内存速度快，在通信代价小的m p i 环境下是很适用的。 第二节f t m p i 的实现机制 f t m p i 的目标是提供像p v m 一样的分布式计算平台。有别于其它提供m p i 进程级容错的解决方案，它是轻量级的，向程序提供存储自身状态的机制，而 不是依靠全局的分布式检查点机制，那样可能会在可扩展性上有所欠缺。这种 机制对分散的，异构的计算机系统来说尤其适合。 下面将简略的介绍f t m p i 的设计，和其与h a r n e s s 系统的交互机制。 9 第二章m p i 容错机制研究 2 2 1f t m p i 与h a r n e s s f t - m p im n t i m el i b r a r y im p i 撇s s a 能s 匾回一匝垂硇 呈嘲蝴= 黜兰。s p l u g - i n ：蒜蒜麓淼o n 图2 5h a r n e s s 和兀m p i 结构 如图2 。5 所示，f t m p i 系统的设计基于分层的方式。最上层是对m p i 1 2 协议的实现。值得一提的是，f t m p i 对很多m p i 组通信的函数进行了优化，使 得运行时能够基于分布式系统的拓扑结构选择适当的通信方法。下面一层处理 数据的分组与转换，存储系统记录。最下层是f t m p i 运行时库( f t m p i r u n t i m el i b r a r y ：f t r t l ) ，负责通过h a r n e s s 用户级库和操作系统交互。该 层提供了动态的进程管理，系统级的m p i 任务命名和错误恢复阶段的消息管理。 h a r n e s s 库提供了动态进程管理和应用程序1 0 操作的重定向。s n i p e 库提供 了m p i 消息的节点间通信实现。值得指出，f t r t l 负责将可能的错误信息通知 各个进程。它先是从通信库和h a r n e s s 层接受错误信息，然后将相关的通知 消息加到消息发送队列中，先于所有的用户态消息。gh c o r e 是一个构建分布 式系统的轻量级后台进程。通过远程调用r p c 的方式实现。它可以实现从动态 库调用代码的功能，一旦代码被载入，就可以用间接或是直接的方式来调用。 l o 第二章m p i 容错机制研究 前者是将某种请求传给函数，后者是直接调用函数。gh c o r e 可以加载关于进 程启动和恢复的多种服务。 2 2 2f t m p i 虚拟机( v m ) 架构 基本的f t m p i 虚拟机( v m ) 架构如下图所示。其中包括一个名字服务进 程( n a m i n gd a e m o n ) ，一个或多个通知进程( n o t i f i e rd a e m o n s ) ，还有运行在 每个节点上的启动进程( s t a r t u p - d a e m o n ) 。名字服务进程全局只需一个。它的 功能是启动工作和恢复工作。f t m p i 运行时环境通过其保存虚拟机的状态和参 加工作分发的节点状态，并在错误恢复阶段通过这些记录恢复工作和任务状态。 豳 f r - m p lr u n t i m e c o m p u t a t i o n a ln o d e s 囫 f r m 拼r u n t i m e 豳 盯一m p lr u n t i m e 囹 阴- m p lc u n t i m e 图2 6f t m p i 虚拟机( v m ) 架构 进程启动通知服务：启动和监视远端进程。当有进程状态出错或是退 出时通知剩余进程。 名字服务：为分布式计算环境中的各任务，进程和服务分配独一无二的 标识符。它也负责在m p i 应用程序的启动和回复阶段提供临时的状态 存储。 2 2 3f t m p i 规范中的错误处理过程 f t m p i 规范将对进程出错的处理分为三个步骤： 错误检测：指检测到一个或多个工作进程出现故障的过程。f t m p i 规范假 定此过程由运行时环境来处理，对系统何时检测到错误小做假定，从而也不能 确定何时认为一个进程处于出错的状态。 第二章m p i 容错机制研究 告知：指将某个进程出错事件通知处于同一并行任务中的其它进程的过程。 f t m p i 对于进程得到通知的时间或是所有进程同时得到通知不做假定，只是保 证并行任务中所有进程都会收到关于出错事件的消息。对其它进程的告知通过 一个特殊的错误码。为了最大限度的遵守m p i 1 和m p i 2 规范，f t m p i 并未定 义新的错误码，而是规定使用m p ie r ro t h e r 告知m p i 程序某些进程已经退 出运行时环境。一旦程序接收到此错误码，其状态即从无错( n of a i l u r e s ) 转变到已出错( f a i l u r er e c o g n i z e d ) 。程序在这个状态下仅能执行某些特 殊的行动，基于错误处理模式的设定不同有所区别。 恢复：指将m p i 程序进程和m p i 运行时环境的状态从已出错恢复至无错的 过程。般分为两个步骤： 1 恢复m p i 运行时环境和m p i 库的状态。f t m p i 中，一旦检测到某个通 信域的出错，这个通信域被标记为错误状态，同时底层系统对所有在该通信域 中的进程发出状态更新信息。如果是通信错误，只需要本通信域中的进程更新 状态。如果是进程退出，所有包括本进程的通信域都需要更新状态。系统对错 误通信域的处理方式是由应用程序决定的，有三种可能的选择： f t m p ir e c o v e r ym o d ea u t o ：一旦m p i 库察觉到某个进程死亡， 会自动开始恢复，不需应用程序的参与。恢复完成后会调用 m p ic o m mw o r l d 的错误处理函数。 f t m p ir e c o v e r ym o d em a n u a l ：用户程序需要首先调用 m p ic o m md u p ( ) 来修复m p ic o m mw o r l d 通信域，在修复 m p ic o m mw o r l d 前不能调用任何m p i 函数。 f t m p ir e c o v e r ym o d ei g n o r e ：这种模式下，一旦检测到错误， 并且各进程得到了通知后，不会启动恢复步骤，之后也不能执行任何包括故障 进程的通信，否则该组通信会产生错误并不予执行。 2 恢复程序和程序中的数据。这个步骤应当由应用程序负