（计算机科学与技术专业论文）消息传递系统容错技术研究.pdf

国防科学技术大学研究生院学位论文 摘要 集群系统具有结构可扩展性好，性价比高等特性，已经成为并行处理发展的 一个重要分支。但是随着集群应用领域的拓展、集群规模的不断扩大，以及网格 的出现人们对其可靠性也有了更高的要求。在集群系统上运行的通常都是大规 模、长时间、以消息传递技术实现的并行科学计算程序，缺乏必要的容错措施时， 某种异常或故障的发生会导致一次计算的彻底失败，大量的工作付诸东流。现有 的消息传递系统如m p i 本身都未提供从失败中自动恢复过来的机制，研究其容错 技术就成为当前集群系统发展的急需 检查点设置及卷回恢复是一种典型的软件容错技术，也是避免失败时大量地 浪费机时的有效手段然而，为并行程序设置检查点要比为单个进程设置检查点 复杂得多，因为在消息传递系统中，消息的传递使得进程之间存在依赖性如何 获取全局一致的可恢复状态是并行检查点机制在消息传递系统中应用的难题。此 外，节点失效或进程出错会引起并行程序失败退出，必须手动重新从检查点启动 程序；有时进程出错会导致悬空程序因此，对节点和进程进行错误探测并在出 错时实现自动恢复也是并行计算容错技术的一个重要部分。 本文首先对卷回恢复协议进行较为全面的研究，并对目前已有的协同式检查 点协议进行分析和对比。我们认为，阻塞和控制消息的数量是影响协同式检查点 协议开销的两个主要因素。针对协同式检查点协议的现状问题，本文提出了一个 可重建的全局检查点的概念和基于可重建检查点的非阻塞协同式检查点协议。该 协议将进程在运行过程中的状态分为三种，并使用捎带消息技术和非阻塞的方法， 减少了用于协同的控制消息的数量。该协议利用并行程序运行过程中卷回恢复的 概率远小于设置检查点的概率的特性，将检查点设置所引入的大部分开销转至卷 回恢复阶段，在很大程度上减少了并行程序使用检查点机制所引入的开销。 其次，本文通过对一个进程管理组件m p d 的分析和研究，在m p d 中加入了 错误探测和自动恢复的功能，克服了因发生错误而手动重启和悬空程序的问题 加入错误探测和自动恢复后的m p d 系统称为m p d f t 。m p d f t 通过对节点和进 程的监控，能够及时探测到节点失效和进程错误的发生，快速进行自动恢复 最后，本文讨论了在m p i c h 2 中实现的基于可重建检查点的非阻塞协同式检 查点协议、基于消息驱赶的s & s 协议和基于消息计数的s & s 协议的开销对比。实 验结果表明，基于可重建检查点的非阻塞协同式检查点协议的开销明显低子其它 两个协议 主题词：容错，m p l ，m p i c h 2 ，检查点，卷回恢复，错误探测，自动恢复 笫i 页 国防科学技术大学研究生院学位论文 a b s t r a c t c l u s t e rs y s t e m sa r ep o p u l a re n v i r o n m e n t sf o re x e c u t i n gp a r a l l e la p p l i c a t i o n sd u et o t h e i re x t e n s i b i l i t ya n dh i g hp e r f o r m a n c e p r c er a t i o ni nr e c e n ty e a r s b u tw i t ht h e e x t e n d i n go f 缸f i e l da n ds c a l e 。a sw e l ia st h ed e v e l o p m e n to fg r i d ，i ti sd e m a n d e dt o p r o v i d eh i g i l e rr e l i a b i l i t y f o rt h el o n g - r u n n i n g , b i gs c a l e ，a n dm e s s a g ep a s s i n gp a r a l l e l c o m p u t a t i o n s ，o n ea b n o r m a le v e n ti sl i k e l yt oc a u s e t h ee n t i r ea p p l i c a t i o nt of a i l ，a n dt h e c u r r e n tm e s s a g ep a s s i n gs y s t e m s ，s u c ha st h em e s s a g ep a s s i n gi n t e r f a c e ( m p d ，d on o t p r o v i d ef a u l tt o l e r a n c e t oa v o i d t l l i sk i n do f t i m ew a s t e i ti sn e c e s s a r yt or e s e a r c hf a u l t t o l e r a n c et e c h n o l o g yf o rm e s s a g ep a s s i n gs y s t e m st oa c h i e v eh i 曲a v a i l a b i l i t yf o r c l u s t e r s c h e c k p o i n t i n g & r o l l b a c kr e c o v e r y ( c r r ) i sam e t h o dt h a ta v o i d st h ew a s t eo f c o m p u t a t i o n sa c c o m p l i s h e dp r i o r t ot h eo c c u r r e n c eo ft h ef a i t u r e h o w e v e r , c h e c k p o i n t i n gap a r a l l e la p p l i c a t i o ni nm e s s a g ep a s s i n gs y s t e m si sm o r ec o m p l e xt h a n j u s th a v i n ge a c hp r o c e s s o rt a k ec h e c k p o i n t si n d e p e n d e n t l y ，b e c a u s em e s s a g e si n d u c e i n t e r - p r o c e s sd e p e n d e n c i e sd u r i n gf a i l u r e - f r e eo p e r a t i o n s h o wt og a i nt h eg l o b a l c o n s i s t e n tr e c o v e r ys t a t e si sad i f f c u l tp r o b l e mi nc r rp r o t o c o l 。f u r t h e r m o r e t h e f a i l u r e so fn o d e sa n dp r o c e s s e sm a yc a u s et h ef a i l u r e so ft h ep a r a l l e la p p l i c a t i o n ，a n d s o m e t i m e st h ef a i l u r e so fp r o c e s s e sm a yc a u s eh a n g i n ga p p l i c a t i o n t h e r e f o r e ，t h ef a u l t d e t e c t sa n da u t o m a t i cr e c o v e r i e sa r ei m p o r t a n tp a r t so f t h ep a r a l l e lf a u l t - t o l e r a n c e f i r s t , r o l l b a c k - r e c o v e r yp r o t o c o l sh a v eb e e ns t u d i e dc o m p r e h e n s i v e l yi nt h i st h e s i s , a n dm a n yc u r r e n tc o o r d i n a t e dt h e e k p o i n tp r o t o c o l sh a v eb e e na n a l y s e da n dc o n t r a s t e d a c c o r d i n gt ot h ea n a l y s i so fc u r r e n tc o o r d i n a t e dc h e c k p o i n tp r o t o c o l s ，b l o c k i n ga n d s y n e r o n i z i n gm e s s a g e sa r et w om a i nf a c t o r sw h i c ha f f e c tt h ee v e r h e a do fc 0 0 r d i n a t e d c h e c k p o i n tp r o t o c o l s a c c o r d i n gt o t h ec u r r e n ts t a t ea n d e x i s t i n gp r o b l e m so f c 0 0 r d i n a t e dc h e c k p o i n tp r o t o c o l s ，t h ec o n c e p to fr e c o n s t r u c t a b l ec h e c l ( p o i n ta n d n o n b l o c k i n gc o o r d i n a t e dc h e c k p o i n tp r o t o c o lb a s e do nr e c o n s t r u c t a b l ec h e c k p o i n ta r e p r e s e n t e d t h i sp r o t o c o l c l a s s i f i e st h es t a t eo fp r o c e s si n t ot h r e ek i n d u s e s p i g g y b a c k i n gm e s s a g e sa n dn o n - b l o c k i n g ，a n dr e d u c e st h en u m b e ro fs y n c r o n i z i n g m e s s a g e s t h i sp r o t o c o lt r a n s f e r st h em o s to v e r h e a do fc h e c ：k p o i n ti n t ot h em o m e n to f r o l l b a c k - r e c o v e r y t h i sp r o t o c o lr e d u c e st h eo v e r a l io v e r h e a do ft h ec h e c k p o i n t m e c h a n i s mb e c a u s et h ec h e c k p o i n th a p p e n sm u c hm o r eo f t e nt h a nr o l l b a c k s e c o n d ap r o c e s sm a n a g e rm p dh a sb e e na n a l y z e da n ds t u d i e dc o m p r e h e n s i v e l y a d d i n gt h ef u n e t i o n so ff a u l td e t e c t sa n da u t o m a t i cr e c o v e r yi nm p dc o n q u e r st h e p r o b l e m so fr e s t a r t i n gb yh a n da n dh a n g i n ga p p l i c a t i o n s w ec a l lt h ee n h a n c e dm p d m p d f t w h i c hw a t c h e st h en o d e sa n dp r o c e s s e sa n dr e c o v e ra u t o m a t i c a l l yw h e n d e t e c t i n gt h ef a i l u r e so f n o d e sa n dp r o c e s s e s f i n a l l y ，t h r e ec o o r d i n a t e dc h e c k p o i n tp r o t o c o l sh a v e b e e ni m p l e m e n t e di n 第n 页 国防科学技术大学研究生院学位论文 m p i c h 2 a n dg e tt h eo v e r h e a d so f t h et h r e ep r o t o c o l sf r o me x p e r i m e n t t h ee x p e r i m e n t r e s u l t ss h o wt h a tt h eo v e r h e a do fn o n b l o c k i n gc o o r d i n a t e dc h e c k p o i n tp r o t o c o lb a s e d 0 1 1r e e o n s t r u c t a b l ec h e c k p o i n ti sl o w e rt h a nt h eo t h e rp r o t o c o l s k e yw o r d s ：f a u l t - t o l e r a n c e m p i 。 m p i c h 2 ， c h e c k p o i n t i n g r o l l b a c k ，f a u l td e c t e c t ，a u t o m a t i cr e c o v e r y 第 i i 页 国防科学技术大学研究生院学位论文 第1 v 页 国防科学技术大学研究生院学位论文 图目录 图2 1 图2 2 图2 3 图2 , 4 图3 1 图3 2 图3 3 图3 4 图3 5 图3 6 图3 7 图3 8 图3 9 图3 1 0 图3 1 l 图3 1 2 图4 1 图4 2 图4 3 图4 4 图4 。5 图4 6 图5 1 图5 2 图5 3 图5 , 4 图5 5 图5 6 图5 7 图5 8 并行程序的全局状态 z 路径和z 循环 多米诺效应 消息日志 清空通道 基于消息计数的s & s 协议 机器相连。 1 0 1 l 1 2 2 2 。2 3 。2 4 2 5 非阻塞协同式检查点的例子 非阻塞协同式检查点协议生成不需要的检查点的例子 仅有依赖进程参与的协同式检查点协议 可重建的全局检查点之一 可重建的全局检查点之二 2 6 2 7 2 8 进程，检查点设置及继续运行过程( a ) 与恢复过程( b ) 2 9 ( a ) 表示检查点设置及继续运行( b ) 表示卷回恢复 n c r c 协议检查点设置过程。 n c r c 协议卷回恢复过程 m p d 的结构框架 m a n a g e r 进程组成的i o 二叉树 m p d f t 系统结构 3 1 3 2 3 3 3 7 3 8 m p d f t 系统初始化顺序图4 l 进程错误探测顺序图 节点错误探测顺序图 m p i c h 2 结构图 4 2 检查点机制的框架结构。 进程使用检查点机制的状态图 检查点信号处理 通道相关内容 f t 在三种协议中检查点设置的协同时间 4 6 4 8 4 9 5 0 5 0 5 4 f t 使用基于消息驱赶的s & s 协议时的开销比例5 4 f t 使用基于消息计数的s & s 协议时的开销比例5 5 第v 页 独创性声明 本人声明所呈交的学位论文是我本人在导师指导下进行的研究工作及取得的研 究成果尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已 经发表和撰写过的研究成果，也不包合为获得国防科学技术大学或其它教育机构的学 位或证书而使用过的材料与我一同工作的同志对本研究所做的任何贡献均已在论文 中作了明确的说明并表示谢意 学位论文题目：消皇佳登丕统窒焦挂盎丑究 学位论文作者签名： 丕围! 盘日期：；”占年，月序日 学位论文版权使用授权书 本人完全了解国防科学技术大学有关保留，使用学位论文的规定本人授权国 防科学技术大学可以保留并向国家有关部门或机构送交论文的复印件和电子文档，允 许论文被查阅和借阅；可以将学位论文的全部或部分内容编入有关数据库进行检索。 可以采用影印缩印或扫描等复制手段保存，汇编学位论文 ( 保密学位论文在解密后适用本授权书) 学位论文题目：消垦笾望丕红奎堡挂丕珏窥 学位论文作者签名： 作者指导教师签名： 日期：如。多年，月侈日 甚凝：妒考年f a 嘶 国防科学技术大学研究生院学位论文 第一章绪论 1 1 课题背景和研究范围 随着并彳亍，分布计算技术在基础研究以及航天，天气预报、石油开采、核模拟 等工程技术领域的广泛应用，高性能计算机得到了长足的发展。尤其是越来越多 的高性能计算机以集群的方式来实现。然而，新发展带来了新问题。由子规模的 扩大，系统出错的概率也随之增加高性能并行计算领域的容错技术由于以下几 种情况越发受到重视：( 1 ) 高性能计算机系统的处理器数快速增长。如b l u e g e n e l t 挣】 总的处理器数目有1 3 0 0 0 0 个，有分析表明这样的一台机器几小时就可能有一个处 理器失效。虽然处理器数的增加带来了性能的提高，但是也提高了出现故障的概 率。( 2 ) 大多数并行计算机系统正在从采用昂贵的硬件系统向低成本的通用处理 器和光纤网络定制组装的集群转变，或者采用基于i n t e m e t 的网格技术来实现并行， 导致发生故障的概率较高( 3 ) 很多科学计算任务由于计算规模大，一次要运行 几天或几个月，例如在a s c i 上运行的s t o c k p i l ec e r t i f i c a t i o n 程序和在b l u e g e n e 上 运行的a b i n i t i o 蛋白质折叠程序要运行几个月由于应用程序的运行时间比平均故 障间隔时间( m t b f ) 长，科学计算程序必须得到容错技术的支持 检查点设置及卷回恢复( c h e c k p o i n ta n dr o l l b a c kr e c o v e r y ，简称为c r r ) 足 一种低开销的容错技术【2 】。它在程序的整个执行过程中，每隔一定时间把整个程序 的状态保存到可靠的存储介质上( 称为检查点) 在发生故障之后，程序重新启 动并恢复到前一次保存的程序状态，从保存点状态继续执行，把计算损失减小到 只有状态保存时刻点到故障发生时刻点这段时间所作的计算，避免了程序从头开 始执行c r r 实现和使用简单，对资源要求低，只占用一定的存储资源，不需要 额外的计算资源c r r 作为一种重要的容错策略，已越来越受到人们的重视这 种基于检查点的恢复技术不仅可以对系统瞬时间歇故障进行恢复。也是恢复未知 故障( 在某一应用设计过程中未预料到的故障) 的有效手段【2 1 】。 人们很早就开始从各个角度对检查点技术做了广泛深入的研究，并取得了许 多成果检查点技术可以在多种层次上实现：( 1 ) 有在语言级使用编译技术实现 的，如m i t 的p o r c h ( p o r t a b l ec h e c k p o i n tc o m p i l e r ) “，这是一个把c 程序转换成 语义相同的、具有检查点设置和卷回恢复能力的程序的源到源编译器，它的特色 是生成的检查点具有良好的移植能力，可以在异构环境中恢复执行。( 2 ) 有在用 户级以函数库形式供用户调用、链接的，如w i s c o n s i n m a d s i o n 大学的c o n d o r 系 统叫、p r i n s t o n 的l ik a i 、j a m e sp l a n k 等人写的l i b c k p t t ”j 等( 3 ) 有在内核级实 现的，如e p c k p t ，c r a k t ”】、b l c r s l 等。从八十年代中到现在，更多的工作致力于 第1 页 国防科学技术大学研究生院学位论文 并行检查点技术的研究。人们深入研究并行系统的一致状态的性质，通过消息记 录和重放等技术，实现了许多并行检查点系统 集群或工作站网络各节点通过网络传递消息来通信，m p i 【1 ”、p v m 2 4 等系统 给用户提供了并行程序编程环境，并让用户通过消息传递的标准调用接口控制并 行程序各进程之间的通信，是目前流行的并行计算环境。它们所提供的消息传递 机制支持了高效和高性能的异构网络计算。而对用户而言，m p i 和p v m 环境提供 了良好的消息传递编程界面但m p i 、p v m 等系统都不支持诸如容错、进程迁移 和负载平衡等功能，对于这些架构于多个通过网络连接的独立的计算机构成的集 群系统之上的并行计算系统，这些功能的实现都需要检查点技术的支持。 基于上述情况，我们对并行检查点协议进行了深入的研究，并提出了基于可 重建检查点的非阻塞协同式检查点协议。我们在m p i c h 2 中实现了基于可重建检 查点的非阻塞协同式检查点协议，该协议将进程在检查点设置过程中的状态分为 三种，并使用捎带消息技术和非阻塞的方法，减少了用于协同的控制消息的数量。 该协议利用并行程序运行过程中囚程序出错导致卷回恢复的概率远小于为防止出 错而设置检查点的概率的特性，将检查点设置所引入的大部分开销转至卷回恢复 阶段，在很大程度上减少了并行程序使用检查点机制时所引入的开销我们在 m p i c h 2 的进程管理组件m id 中加入错误探测和自动恢复的功能，可以实时发现 节点错误和进程错误，自动从检查点恢复这样，以此系统为基础，可进一步实 现m p i 的进程迁移和动态负载平衡。 1 2 研究意义 检查点机制在并行系统中有非常重要的应用，主要包括以下几个方面： 1 2 1 实现系统容错 随着计算机的发展，组成一个计算机系统的硬件和软件日益复杂，系统出现 硬件和软件故障的概率也随之增加，因此，计算机系统的故障监测和故障恢复便 成为计算机系统设计人员所要解决的重要问题。在并行系统中，系统的故障率随 着系统处理器数目和软件复杂性的增加而增加使用集群计算的程序一般都是大 计算量的程序，这些程序的执行往往需要几十个小时甚至几十天的时间若某集 群计算系统的平均无故障时间小于一个程序所需的运行时间，且该程序在每次执 行中出现故障后都从头开始重新执行，那么该程序可能永远也不会执行完毕利 用检查点机制，我们可以每隔一个适当的时间间隔对该程序做次检查点操作 在系统出现故障后，利用程序的检查点文件把该程序恢复到最近一个检查点时刻 的状态继续运行。利用这种步步为营的策略可以保证长时问运行的作业最终被正 第2 页 国防科学技术大学研究生院学位论文 确地执行完。因此，利用检查点实现集群系统容错成为人们日益关心的热点 1 - 2 2 卷回调试 在程序调试过程中，利用检查点保存程序多个时刻的运行状态。当有错误发 生时，把程序卷回到出错前所保存的某一时刻状态重新运行，通过重现相同的错 误来查找发生错误的条件的调试方法称为卷回调试。卷回调试能节省大量的时间， 对调试运行时间较长的程序尤为有利并行程序包含较多的不确定成分，当发现 运行错误重新运行程序查找错误原因时，同样盼错误可能很难再次出现。利用卷 回调试会在很大程度上提高错误再次发生的概率，因此卷回调试是调试并行程序 的有力工具 1 2 3 任务切换 在分时系统中，可以以时间片分时的方式并发地执行多个进程。这些并发进 程分时共享一个c p u 资源。当一个时间片结束时，系统进行进程切换，把当前运 行的进程从内存调出暂存在硬盘上，然后把另外一个进程从磁盘调入到机器内存 中运行还有一种情况是当出现一个需要优先执行的任务时，要把其它任务从系 统中切换出来。目前，大部分的并行系统还不提供任务切换的功能。利用检查点 机制可以实现并行任务的切换，当时间片结束时对正在内存中运行的并行任务 设置检查点，把并行任务的当前状态以检查点文件的形式存储在磁盘上，并暂时 中止该任务的运行，然后，重新启动另一个并行任务的检查点文件。这样，就实 现了任务切换。 1 2 4 实现动态负载平衡 并行程序通常由多个进程相互协作完成。如果这些进程中的某个进程被分 配到一个负载较重的节点上，那么由于该进程的运行速度太慢，将在相当程度上 延迟整个并行任务的完成时间，因此，在集群计算中为并行任务的各个进程分配 合适的节点是非常重要的静态调度通常在程序初始运行时为并行任务的各进程 分配节点。因为集群是一个多用户的并行计算系统，系统中各节点负载不断变化 且难以预测。在把一个进程分配到某个负载较低的节点上后，若在进程执行期间 系统又向该节点分派了一个大计算量的任务，那么该进程执行的速度同样会影响 整个并行任务的完成时间因此，仅仅靠静态调度难以达到理想的效果。集群计 算系统应在并行计算执行期间，根据各节点负载的变化实时地对并行子任务进行 动态调度进程迁移是实现并行任务动态调度的技术基础，但目前大多数集群操 第3 页 国防科学技术大学研究生院学位论文 作系统不能提供进程迁移功能。利用检查点可以保存进程在某个节点上的运行状 态，然后在其它节点上恢复进程的运行以实现进程迁移，从而实现动态调度和负 载平衡 1 , 3 国内外研究现状 检查点技术是当前国际学术研究的热点和难点，它主要包括单进程检查点技 术和并行检查点技术两个方面。很多并行系统提供检查点功能，不仅为并行系统 提供了容错功能，而且在此基础上还实现了进程迁移和动态负载平衡功能下面 分别介绍两个单进程检查点软件和三个并行检查点系统。 1 3 1c o n d o r c o n d o 一是w i s c o n s i n - m a d s i o n 大学研制的一个异构型分布式系统，它使用位 于工作池中的空闲资源来实现高吞吐量计算c o n d o r 的主要特征是：充分利用工 作站的空闲时间；用户只需与库函数重新链接便可利用c o n d o r 提供的检查点和进 程迁移功能；对于远程执行的进程，本地的执彳亍环境被保留；工作站主人对该工 作站拥有最高优先级和完全的控制权；保证彻底完成作业，不会因为系统的故障 或工作站的退出而导致作业不能完成；本地磁盘空间不会被c o n d o r 作业所占用； 对网络资源、数据传送和检查点操作的有效监控；对网络资源，c p u 的协同调度。 用户可以从工作站池中的任何一台机器提交任务，系统将自动从c o n d o r 池中查找 最合适的空闲机运行任务，它利用将大型计算任务派至远程空闲机执行的方式， 把空闲处理机的c p u 资源分配给其他用户，从而实现负载平衡。 但是。c o n d o r 的检查点技术仅支持单进程任务在c o n d o r 中，不支持使用f o r k 及类似系统调用的任务使用这些系统调用的任务在父子进程问进行通信，协调 进行工作，而c o n d o r 无法为多个进程生成检查点文件。而且c o n d o r 也不支持使 用信号和信号处理程序的应用程序。 1 3 2c r a c k c o l u m b i a 大学网络实验室在2 0 0 1 年发布的c r a c k b s 则是在操作系统级以内 核模块的形式实现的检查点系统。这是第一个在u n i x l i n u x 中实现的完全透明的 检查点系统。由于c r a c k 是以内核模块的形式实现的，操作系统中的进程可以 完全透明的进行检查点和恢复，既不需要对操作系统进行改动和重新编译，也不 需要对应用程序的代码进行任何改动和重新编译而且c r a c k 对网络套接字也 提供了支持c r a c k 主要实现了以下功能：( 1 ) 不需要修改内核就可以完全透 明地实现应用程序的迁移。( 2 ) 除了真正的检查点，恢复操作，没有运行时开销。 国防科学技术大学研究生院学位论文 ( 3 ) 实现了没有“主结点”和? 代理”进程的真正的进程迁移( 4 ) 以较低的 开销实现了虚拟网络。( 5 ) 对网络连接的迁移提供了支持。 c r a c k 的研制成功证明了为流行的操作系统( 如l i n u x ) 设计一个通用的透 明的检查点包，而且不用对操作系统或用户程序添加补丁是完全可行的，这是目 前第一个实现了操作系统级透明的检查点系统 1 3 3c o c h e c k c o c h e c k t 4 1 系统是慕尼黑大学研制的，其检查点机制构建在m p i 层之上，利用 c o n d o r 库来记录单个进程的检查点状态它能为应用程序提供透明的检查点和进 程迁移功能，可以方便地移植到不同的m p i 实现上它的基本思想是保证网络上 没有正在传递的消息，这样每个进程就可以记录检查点并获锝一致的全局状态。 实现了协同式检查点算法。 c o c h e c k 假设所有进程之间的通道是f i f o 的，通过一个r m 消息( r e a d y m e s s a g e ) 清空通道来保证通道中没有传递的消息当进程接收到一个检查点通知 之后。向其它所有的进程发送r b l 消息；当进程接收到所有的r m 消息之后，设 置临时检查点；所有进程同步，退出检查点设置c o c h e c k 系统通过消息驱赶的方 法消除“中途消息”l 1 1 。 1 3 4 ta m m p i 检查点系统 l a m m p i t ”i 检查点系统是i n d i a n a 大学开放系统实验室( o p e ns y s t e m sl a b ) 基于内核级单机检查点软件b l c r 实现的l a m m p i 不仅是一个高性能，免费可 用及源代码公开的m p i 函数库，也是一个基于守护进程、用户级的m p l 运行环境， 同时，还提供了m p i 程序正常运行所需要的许多服务。 通过与b l c r 的结合，l a m m p i 还实现了对m p i 程序的检查点，卷回恢复功 能，并提供一些方便使用的接1 2 1 。l a m m p i 实现了协同式检查点协议，通过m p i r u n 命令，所有的m p i 进程初始化检查点操作，进程之间开始相互协调以通过本地检 查点实现一致的全局检查点l a m m p i 通过s t a g g e r e da l l - t o a l l 算法保证在记录 检查点时通道上没有消息传递，以避免消息事件影响 1 3 5c h a r m 系统 c h a r m i 旬( c h e c k p o i n t - b a s e dr o l l b a c kr e c o v e r ya n dp r o c e s sm i g r a t i o n ) 是清华大 学研制的实现并行程序卷回恢复及进程迁移的软件，支持集群系统的容错和负载 平衡。c h a r m 不仅实现了对集群系统瞬时故障的恢复，而且通过检查点设置时的 m i r r o r 存储技术和进程迁移技术。实现了对集群系统节点永久故障的恢复并支持系 第5 页 国防科学技术大学研究生院学位论文 统在线维护、处理机资源的排他或限时使用和动态负载平衡。 c h a r m 系统采用协同式检查点协议，在检查点发起时刻，若通信通道状态包 含中途消息，将利用通信机制本身“驱赶”中途消息，同时延迟真正的检查点设 置。最终达到在无孤儿消息和丢失消息的全局状态下建立检查点的目的 1 4 本文的主要工作及组织 1 4 1 本文的主要工作 本课题研究m p i 程序设计环境的容错技术，我们以l i n u x 为开发环境，利用 并行检查点技术和基于m p d 的错误探测和自动恢复机制，在m p i c h 2 上实现了容 错功能主要研究内容包括基于可重建检查点的非阻塞协同式检查点协议和基于 m p d 的错误探测与恢复机制，分为以下几个方面： 1 基于可重建检查点的非阻塞协同式检查点协议 要实现并行检查点协议，不仅要完成各进程状态的保存与恢复，还要对进程 间的通信进行同步和记录，以保证整个计算任务状态的全局一致性。我们提出了 基于可重建检查点的非阻塞协同式检查点协议( n o n b l o c k i n gc o o r d i n a t e d c h e c k p o i n tp r o t o c o lb a s e do nr e c o n s l r u c t a b l ec h e c k p o i n t 简称为n c r c 协议) ，与基 本的协同式检查点协议不同，n c r c 协议采用了非阻塞的思想，所保存的检查点文 件处于可重建检查点状态( 通过一些操作可以转为全局一致的可恢复状态) 。n c r c 协议利用卷回恢复发生的概率远小于检查点设置的概率的特性，将检查点设置的 大部分开销转至卷回恢复阶段，在很大程度上减少了检查点机制带来的开销。 2 基于m p d 的错误探测与自动恢复机制 并行程序运行过程中，若某个进程遇到节点失效或髓络失效，将导致整个作 业流产当程序失败时，必须由程序员手动地重新启动程序有时也会出现一个 并行程序的某个进程因节点失效或其它原因退出，但其它进程却没有获悉这个进 程的失败，仍然继续运行的情况，导致该程序成为悬空程序。基于m p d 的错误探 测可以解决这两个问题，利用心跳检测法周期性地对程序的所有进程发出心跳访 问请求来得知节点和进程的状态自动恢复机制可以自动地从保存的检查点文件 对程序进行恢复。 3 m p i c h 2 中的容错机制的设计与实现 我们在m p i c h 2 上实现了基于消息驱赶的s & s 协议、基于消息计数的s & s 协 议和n c r c 协议，在m p d 上增加了错误探测和自动恢复的功能，为m p i c h 2 提 供了容错功能。并通过实验，对n c r c 协议的开销与其他协议进行了比较。 1 ，4 2 本文的组织 第6 页 国防科学技术大学研究生院学位论文 本文共六章，各章的主要内容安排如下： 第一章绪论，主要介绍本课题的研究背景、研究意义和国内外研究现状， 最后介绍了本文的主要工作以及论文的组织结构 第二章消息传递系统中的并行检查点技术概论，首先介绍了并行检查点技 术的基本概念，然后分别对检查点协议和日志协议进行了详细的介绍。 第三章基于可重建检查点的非阻塞协同式检查点协议，首先分析了基本的 协同式检查点协议的开销，然后提出了可重建的全局检查点的概念和基于可重建 检查点的非阻塞协同式检查点协议，并对协议正确性和性能进行证明和分析。 第四章基于m p d 的错误探测与自动恢复，首先介绍了进程管理组件m p d 的功能和结构，然后描述了如何在m p d 上加入错误探测和自动恢复的功能 第五章m p i c h 2 中容错机制的设计与实现，首先讨论三种协同式检查点协议 在m p i c h 2 中的实现，然后通过实验分析了三种协同式检查点协议的开销， 第六章结束语，总结本文的工作，展望下一步的研究内容。 第7 页 国防科学技术大学研究生院学位论文 第二章消息传递系统中的并行检查点技术概述 2 1 并行检查点技术综述 目前大量的应用都在并行系统中运行，随着节点数目的增加，节点失效和网 络失效的可能性也逐渐加大，因此为了增加系统的可靠性和可用性，开发了许多 技术，包括：事务、组通讯和卷回恢复。这些技术关注的焦点与权衡的问题各不 相同。事务主要是针对面向数据的应用；组通讯提供一个理想的通讯系统，以便 程序员在其上开发可靠的应用；卷回恢复主要是针对需运行较长时间的应用，例 如科学计算类应用 并行检查点技术将并行程序看作是一组通过网络相互通信的进程，在进程无 错执行期间通过把进程的状态周期性地保存到稳定的存储器中来实现容错。当出 现错误时，一个出错进程可根据它保存的进程状态进行重启恢复。这样可以减少 因故障而带来的计算损失。保存的进程状态称为检查点。进程检查点的内容包括 进程的全部内存映象，即代码段，数据段，堆，栈和上下文等。在消息传递系统 中，由于进程在执行期间相互发送消息，使得各进程产生依赖性，从而使得并行 检查点技术比单进程检查点技术要复杂得多。当消息传递中的一个或多个进程出 错后，这些相关性可能迫使一些无错的进程也必须卷回，即产生所谓的卷回广播 现象。 当并行程序的每个进程独立地设置检查点，即独立式检查点时，就可能产生 多米诺效应。为防止多米诺效应可采用以下两种方案：( 1 ) 使用协同式检查点， 各进程在检查点设置时进行协同，使得保存的状态在系统范围内保持一致。这个 一致的检查点集合即构成恢复线可以用来限制卷目广播；( 2 ) 使用通信诱导检 查点，每个进程除了按照既定策略设置基本检查点外，在接收其它进程的消息时， 还必须依据消息上附加的相关消息设置强制检查点。通过设置强制检查点，使得 这些检查点中存在着一个系统范围内的一致状态，从而避免多米诺效应 以上所述的均为基于检查点，卷回恢复策略来实现的容错此外还可以使用基 于日志的卷回恢复，通过将检查点和记录非确定性事件的日志相结合来实现容错 基于日志的卷回恢复依赖于分段确定性的假设即一个进程所执行的所有非确定 性事件都可以被标识，在进程恢复时重演该事件所需的信息即事件的确定性因素 可以被记录在日志中。通过记录并且按照原始事件发生的相同顺序进行重演，一 个进程可以确定性的重新产生一个出错前的状态，即使该状态没有设置检查点。 基于日志的卷回恢复协议允许系统从一个最近的检查点进行恢复，这种方案特别 适用于那些需要频繁和外界交互的程序。因为外界所包含的输入输出设备一般是 第8 页 国防科学技术大学研究生院学位论文 无法进行卷回的。 根据非确定性事件的确定性因素记录到稳定存储器中的方法不同，可分为三 种类型的日志方案：悲观曰掣”、乐观日怠1 】和因果日志【”。在悲观日志中，非确 定性事件的效果能被进程或外界感知之前。应用进程必须阻塞。直到此非确定性 事件的确定性因素被记录到稳定的存储器中。悲观日志的方案在故障恢复时只有 故障进程需要卷回简化了恢复操作，但导致了无错执行时的效率较低。在乐观日 志中，应用进程收到一个非确定性事件时不必阻塞，它可将该事件的确定性因素 异步地保存到稳定的存储器中，因此信息可能会丢失。乐观日志减少了无错执行 时开销，但在故障恢复时有可能出现卷回的广播，增加了恢复的复杂性。在因果 日志中，通过在乐观日志和悲观日志中寻找一个平衡点，将降低无错执行的开销 和简单的恢复结合起来。这三种方案在垃圾收集及如何同外界进行消息交换上各 不相同。 2 2 并行检查点协议的基本概念 一个运行于消息传递系统的并行程序由一组固定数量的进程组成，进程间只 通过消息传递进行通信。并行检查点协议并不认为通信网络一定可靠。有的协议 假设通信子系统能可靠地按照f i f o ( 先进先出) 的顺序传送消息，而有的协议则 认为通信子系统可能丢失，重复发送或重新排列消息的顺序。这些假设对协议在 恢复和实现等方面的复杂性具有较大影响。 定义2 1 全局进程状态对于一个含有月个进程( n ，既，尸力的分布式系统， 全局进程状态有一个含有n 个进程状态圆，既，踟的集合，其中每个进程有个 进程状态。 定义2 2 中途消息在一个全局进程状态中，如果一条消息只记录了它的发 送而没有记录它的接收，则称为中途消息如图2 1 中a ) 的消息m 。 定义2 3 孤儿消息对分布式系统中的某一全局进程状态。如果它包含了某 一消息的接收事件，但没有包含该消息的发送事件，则该消息就称为孤儿消息。 如图2 1 中b ) 的消息m 2 即为孤儿消息 定义2 4 孤儿进程含有孤儿消息的进程称为孤儿进程。 定义2 5 通信信道状态就全局进程状态g s = 吼s 2 , ，劝而言，所有中途消 息的集合称为全局进程状态g s 的通信通道状态 定义2 6 全局一致状态 一个并行程序的全局一致状态由所有参与进程的进程状态的集合和此时的通 信通道状态组成。直观地说，一个一致的全局状态就是一个分布式应用在无错执 行期间可能出现的状态。在这种状态下，当一个进程的状态反映了一个消息的接 第9 页 国防科学技术大学研究生院学位论文 收，则发送消息的进程的状态中必然会表明发送了这样一个消息不满足这个条 件的状态即为不一致状态如图2 ，l 中的a ) 的g s o 和g s t 为一致的全局状态，而图 2 1 中b ) 的g s o 表示的是一个不一致的全局状态即全局一致的系统状态是一个不 含有孤儿消息的系统状态。 p 1 p 2 p 3 p l p 2 p 3 图2 1 并行程