（管理科学与工程专业论文）集群系统中高可用调度器的研究与实现.pdf

国防科学技术大学研究生院学位论文 摘要 集群计算通过网络互联进行资源共享，不但能够充分利用现有的计算资源，而且能够 通过较低的软、硬件代价获得较高的计算性能。高可用性作为集群计算研究的一个重要内 容，其主要的目标是利用硬件冗余和软件技术，避免因单个部件的失效导致整体系统的崩 溃，为用户提供连续不间断的服务。 本文在研究总结现有集群计算技术的基础之上，通过随机过程理论，推导了集群系统 可用度公式。着重讨论了检查点和进程迁移两大高可用技术。为证明在一般操作系统之上 以内核模块方式实现基于检查点的进程迁移的可行性， 我们设计实现了c k p m程序， 对软 件形式的高可用性技术作了有意义的探索。 以检查点机制和进程迁移技术作为支撑，针对现有集群系统在调度器高可用性方面存 在的不足， 我们提出了改进的高可用调度器解决方案， 并给出了一个基于l v s 集群系统的 原型实现。 本文对集群技术以及以检查点和进程迁移为代表的高可用技术作了深入而有意义的研 究，对构建高可用集群系统有一定的参考价值。 关键词: 集群调度器高可用性检查点进程迁移 第 i页 国防科学技术大学研究生院学位论文 ab s t r a c t c l u s t e r s y s t e m s h a r e s r e s o u r c e a c r o s s n e t w o r k . i t n o t o n l y u s e s e x i s t i n g c o m p u t a t i o n a l r e s o u r c e w e l l , b u t a l s o c a n r e a c h h i g h p e r f o r m a n c e w i t h l o w e r c o s t o f s o f t w a r e a n d h a r d w a r e . a s a s i g n i f i c a n t c o n t e n t o f c l u s t e r r e s e a r c h , h i g h a v a i l a b i l it y ( h a ) a i m s t o p r e v e n t w h o l e s y s t e m f r o m c r u s h c a u s e d b y s i n g l e p o i n t f a i lu r e b y m e a n s o f r e d u n d a n t s o f t w a r e a n d h a r d w a r e r e s o u r c e . p r o v i d i n g n o n - s t o p s e r v i c e i s t h e g o a l o f h a . t h i s p a p e r a n a l y z e s t h e b a s i c t e c h n i q u e o f c l u s t e r a n d g i v e s a h a e x p r e s s i o n s f o r c l u s t e r s y s t e m b y s t o c h a s t i c p r o c e s s t h e o r y . we e m p h a s i z e o n t h e h a t e c h n i q u e o f c h e c k p o i n t a n d p r o c e s s m i g r a t i o n . i n o r d e r t o v a l i d a t e t h e f e a s i b i l i ty t h a t c h e c k p o i n t a n d p r o c e s s mi g r a t i o n c a n b e i m p l e m e n t e d o n g e n e r a l o s u s i n g k e r n e l m o d u l e , w e d e s i g n a n d i m p l e m e n t c k p m. t h i s i s a s i g n i f i c a n t t e s t o n h a b y s o f t w a r e . b a s e d o n c h e c k p o i n t a n d p r o c e s s mi g r a t i o n , w e g i v e a c l u s t e r b a l a n c e r h a r e s o l u t i o n . t h e n w e i m p l e m e n t a p r o t o t y p e b a s e d o n l v s t h e p a p e r m a k e s a s e r ie s o f r e s e a r c h e s o n c h e c k p o i n t a n d p r o c e s s mi g r a t i o n a n d c a n h e l p t h e d e s i g n o f h a c l u s t e r s y s t e m . k e y wo r d s : c l u s t e r , b a l a n c e r , h i g h a v a i l a b il i t y , c h e c k p o i n t , p r o c e s s mig r a t i o n 第 n 页 独创性声明 本人声明所呈交的学位论文是我本人在导师指导下进行的 研究工作及取得 的 研究成果。 尽我所知，除了 文中 特别加以 标注和致谢的地方外， 论文中 不包含 其他人已 经发表和撰写过的 研究 成果， 也不 包含为获得国防 科学技术大学或其它 教育机构的 学 位或证书而 使用过的 材料。 与我一同 工作的同志 对 本 研究 所做的 任 何贡献均已 在论文中作了明 确的 说明并表示谢意。 学位论文题目 : 集群系统中高可用调度器的 研究与实 现 学 位 论 文 作 者 签 名 : 争拱 源 日 期 : i 叫 年i 月了 日 学位论文版权使用授权书 本人完全了 解国防科学技术大学有关保留、 使用学位论文的规定。 本人授权 国防科学技术大学可以保留并向国家有关部门 或机构送交论文的复印 件和电子 文档， 允许论文被查阅和借阅;可以 将学位论文的全部或部分内 容编入有关数据 库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文. 保密学位论文在解密后适用本授权书。 ) 学位论文题目: 学位论文作者签名: 作者指导教师签名: 日 期 :-)- 3 年/i f 月c 5 日 日 期 : 二 佣 夕年，/月 如日 国防科学技术大学研究生院学位论文 图 表 目 录 表1 - 1计算机系统可用度等级列表. .， 二 . . . . . . . . . . . . . . . - . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 表1 - 2利用检查点机制的几个系统. . . .，. . . . . . . . . . . -. . . . . . . . . . . . . . . . . 卜 . . . . . . . . . . . . . . . . . . . . . . . . . . 7 图1 - 1本文的研究思路示意图. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 0 47 1111 图2 - 1 图2 - 2 图 2 - 3 图 2 - 4 集群系统的结构 ， . - . . . - . . ， . . . . . . . . . . . . . . . . . . . . . . . . . . 价 . . . . . . . . . . . . . . . . . . . ， . lvs i p vs 集群系统的结构. . . . . . . . . . ，. . . . . . . . ， 二 ， ， .，. . 一 ， . . . . . . . . . . . . . . . . . . . . . 的结构. . . . . . . . . . . . . . . . . 一 ， . . . . . . . - . . . . . . . . - . . . .， . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 9 框架， ， 甲 . ， ， 二 ， . ， ， ， ， - ， ， ， ， . ” * ， . .， . . . . . . . . . . . . . . . . . . . . . . . . 1 9 图3 - 1生灭过程 . . . . . . . . . 一 ， . . . . . - . . . ， . . . . - .， ， 甲 卜 . ，. . ， ， . . 价 ， . ， 一 “ ， . 甲 甲 . 一 ， . . . . . . . . . . . . . 2 6 表3 - 2系统可用度与节点数的关系. . . . . . . . . . . . - . . . . . . . . . . . . . - . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . - . . . . 2 7 图4 - 1进程迁移的级别. . . . . . . . . . . . . . . . . . . . . . . .- . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 8 图4 - 2进程迁移的过程. . . . . . ， ， . . . . . . . ， . . . . ， . . . . . . . . . . . . . . . . . . . . 3 0 图4 - 3基于检查点机制的进程迁移过程. . . . . . . . . . . ， . . . . . . . . . . . . . . . . . . . . . . . . - . . . . . . . . . . . . . . - . . . . 3 3 表4 - 1进程的状态二， . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 一 ， . . . . . . . 3 4 图4 - 4 l i n u x 进程虚拟地址到物理地址的映射关系 . . . . ， ， . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 7 图5 - 1高可用调度器的功能模块图. . . . ， . . . . . . “ . . . . . . . . . . . . . ， . . . . . . . . . . . 4 4 图5 - 2高可用调度器拓扑结构图. . . . . . . . . . . . . . . . . . . . . . - . . . ， ， . . . . . . . . . . . . . . . ，. . . ， ， . . . . . 4 6 表5 - 1 用户连接信息记录的数据结构. . . . . . . . . . . . . . . . - . . . . . . . . .- . ，. . . . . . . . . . . . . . . . . . 4 8 表5 - 2用户连接 h a s h 表 ，. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .， . . . . . . . . . . . . . . . . . . . . . . . . . 4 9 表5 - 3同步连接 h a s h 表， ， ，. ， . . . . . . . 一. . . . 一 ，. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 9 图5 - 3用户连接信息的读取和写入过程二 ， . . . . . . . . . . . . . . . . . - . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 0 表5 - 4全拷贝和增量拷贝算法的比较. 甲 一_ - 二，. ， . 一， ， . ， - - . . ， . 甲 ， .， . . . . . . . . . .5 3 图5 - 4全拷贝和增量拷贝算法的比较. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 3 第 i v页 国防科学技术大学研究生院学位论文 第一章绪论 1 . 1背景及问题的提出 集群( c l u s t e r ) 计算的概念是1 9 6 0 年由i b m提出的。 四十多年来， 随着微处理器技术、 高速网 络技术、高性能分布计算技术的研究与发展， 集群计算技术取得了 突破性的发展。 特别是近年来，在 i n t e m e t 飞速发展的推动下，人们对高性能计算、网络计算有了越来越 高的要求。集群计算通过网络互联进行资源共享，不但能够充分利用现有的计算资源，而 且能够通过较低的软、 硬件代价获得较高的 计算性能 2 8 1 在 “ 十五”预先研究课题 “ 卫星信息资源管理与共享系统”项目 中，文件传输模块和 查询模块是用户经常访问的接口，数据量大， 操作频繁。因此这两个模块运行的服务器在 物理上应该具有高性能和高可用性。一种性能价格比较高的解决方案是采用负载均衡集群 技术。集群系统向用户提供单一的系统映像。客户请求到达时，集群调度器通过筛选算法 将客户请求转发到服务器池中负载较小的真实服务器进行处理。处理结果通过调度器或直 接返回给客户。通过分布式的并行处理和冗余机制。集群技术能够较好的满足系统性能和 可用性要求。 伴随着客户对系统安全性能的不断提高，以及客户应用系统尤其是关键领域的关键性 应用对可用性要求的不断增加，越来越多的应用要求能够有 7 x 2 4小时的不间断服务 ( n o n s t o p )。 特别是在军事领域， 如本课题研究的卫星信息资源的管理与共享问题中， 客户获取卫星信息资源必须具有高的实时性、高的可用性和高的查准率。如何建立和维护 真正高可用性的集群系统是我们面临的挑战。 今天，由于计算机技术发展，硬件服务器平台己 经有了相当好的可靠性和可用性。据 统计， 一个独立系统的可靠性在9 9 %以上， 如果配备一些系统管理工具， 则系统的可靠性 可以达到9 9 .5 0/ % - 9 9 .8 %。 但是， 如果一年按3 6 5 天计算， 那么每年依然有 1 8 4 4 小时的 停机时间，这对于那些任何服务中断都将产生严重后果的关键性应用来说是不可以接受 的。 为了满足这些可靠性和可用性要求极高的关键性应用，人们使用专用结构和广泛冗余 的容错系统， 通过比常规系统昂贵若干倍的代价将系统的可用性提高到9 9 .9 9 9 9 %以上， 也 就是平均每年的停机时间降到半分钟。 这种主要依赖硬件冗余的解决方案虽然将故障发生 的 可能 性降至最小， 但花费的 代价也是极其昂 贵的 2 s 。由 此，以 软 件方式实 现的高 可 用技 术应运而生。而具有代表性的检查点机制和进程迁移技术不仅能在很大程度上提高系统的 整体性能，而且以一种更加廉价的方式给系统提供了可选择的方案。 第 1页 国防科学技术大学研究生院学位论文 本文的研究目的就是以检查点设置机制和进程迁移两大技术作为支撑，针对集群系统 调度器高可用性支持方面存在的不足， 提出改进的 解决方案，进一步提高集群系统调度器 的可靠性和可用性，为用户提供透明的不间断服务。 1 . 2 关键技术及研究现状 1 . 2 . 1 集群计算技术 ( c l u s t e r ) cu 集群计算技术一直是计算机界研究的一个热点问题。集群技术通过高速网络将多台主 机联合成一个具有单一映像的计算资源，以较低的软硬件代价实现了高性能和高可靠性的 计算机系统。集群系统具有很多的优点: . 易于与现有网络集成 . 可伸缩性好，易于保护用户投资 . 软硬件要求低 . 资源的充分共享 . 工作站上现有丰富的标准成熟的开发工具 这些都使得集群系统成为一种发展趋势。 美国d e c 公司( d i g it a l e q u ip m e n t c o r p o r a t i o n ) 最 早 引 入 集 群的 概念， 并 于1 9 8 3 年 在 v ms 上实现了集群系统v m s c l u s t e r 。但由 于v m s 操作系统只能在d e c公司的v a x系 列 和a lp h a 系 列服务 器上 运 行， v m s c l u s t e r 的 应 用 受 到 很 大限 制。 u n i x是服务器或工作站上普遍使用的操作系统，它运行稳定、安全性也比较好，因 此许多大的公司都采用了基于 u n i x的集群系统解决方案，如 d e c , h p , s u n , i b m, n c r 和d g等公司。 其中d e c 公司的t r u c l u s t e r 系统 提 供了由4 台d i g i t a l a l p h a s e r v e r 组 成的集群系统，它集高可靠性、高可用性和易管理性于一身，是关键业务计算机系统的理 想解决方案。 基于wi n d o w s n t的集群系统解决方案厂商主要有mi c r o s o ft和d e c o mi c r o s o f t 于1 9 9 5 年就开始了集群系统的开发工作。 wi n d o w s 2 0 0 0 中己经增加了集群功能， 该高可用性集群 叫 做w o l f p a c k ， 也叫做m i c r o s o f t c l u s t e r s e r v e r ( m c s ) 。 它主 要是 在企业级对基于wi n d o w s n t服务器的应用程序提供可用性和可升级性。wo l f p a c k 现在支持两个服务器，一个用来 对用户提供服务，另一个作为从调度器使用。mic r o s o f t 下一步的目 标是将wo l f p a c k 支持 的 节点 数扩 展到1 6 个。 w o l f p a c k 的 缺陷 在于: 它只 提 供了 两 个 节点的 失 败 恢复 功能， 而 没有采用复杂的应用程序资源管理功能，因此在一定程度上影响了系统的高可用性、高可 靠性和可升级性。 w o l f p a c k 不 能支持多 种操作系 统， 而只能 运行于wi n d o w s n t 操作系 统 上。由于wi n d o w s n t 操作系统本身在稳定性、大型并行计算上与u n i x系统存在较大差 距，目前主要在中小型系统上应用。但是随着wi n d o w s n t系统走向成熟，基于wi n d o w s 第 2页 国防科学技术大学研究生院学位论文 n t的计算机集群系统将获得更广泛的应用。 九十年代末期， l i n u x 操作系统不断走向成熟， 它的 健壮性不断增强， 并且提供了g n u 软件和标准化的p v m, m p i 消息传递机制，最重要的是l i n u 、 在普通p c机上提供了对高 性能网络的支持， 这样就大大推动了基于l i n u x 的集群系统的发展。 t u r b o l i n u x 公司推出 了能够显著提高基于 t c p 八 p协议的多种网络服务的服务质量的高可用性集群系统 t u r b o c l u s t e r o r e d h a t 也提供了基于 l i n u x v i rt u a l s e r v e : 思想构建的高可用性集群系统 p i r a n h a 。由e r i c s s o n 软件工程研究中心开发的高可用性集群系统e d d i e 的主要目 的是提供 一个商业级的，能提供较好的服务质量的w e b 服务器的解决方案。 p l a t f o r m公司开发的高可用性集群系统l s f提供了分布式集群系统的解决方案，通过 将物理上分离的多个集群连接在一起，使得多个同构或异构的计算机能够通过局域网或广 域网共享计算资源，并能够为用户提供对资源的透明访问。 高性能集群系统mo s i x为l i n u x 核心增添了集群计算的功能。 在mo s i x集群环境中， 用户无需对应用程序进行修改，或将应用程序与库连接起来，或将应用程序分配到不同的 节点上运行。mo s i x会自 动将这些工作透明地交给别的节点来执行。 i b m, m i c r o s o f t 和i n t e l 于2 0 0 0 年7 月联合发布了一种高可用性服务器集群软件及硬 件包， 这种服务器集群的 配置 包括3 2 台i b m n e t f i n i t y 8 5 0 0 r 及i n t e l p e n t iu m i i i x e o n 处 理器， 运行i b m的d b 2 u n iv e r s a l d a t a b a s e 和m i c r o s o f t w i n d o w s 2 0 0 0 a d v a n c e d s e r v e r 操 作系统，每分钟可以执行 4 4 0 8 7 9次交易。这套系统面向数据密集的应用，特别是 b 2 b , 电子商务和企业资源规划领域。 在科学计算领域中， 人们开始把注意力投向通过普通p c机或工作站的集群来代替昂贵 的超级计算机。 比 较成功的 例子是高性能集群系统b e o w u l f ， 它最初是由n a s a的g o d d a r d f l ig h t c e n t e r 进 行开 发的 ， 主 要目 的 是 支 持大 规 模的 科 学 计算问 题， 如 地球 和太 空 科 学 面 临的一些计算问 题。 国内也有不少公司进行了集群系统的研究和开发工作。 联想公司在1 9 9 9 年9 月推出了用于分布式高性能计算的n s 1 0 0 0 0 高性能集群服务器， 该系统是一个四节点的系统， 主要基于联想万全4 5 0 0 r服务器，以总体成本相对较低的设 备组合，足以替代传统 r i s c小型机和中型机的工作，而价格仅为市场上同等性能小型机 的 1 / 2 -1 / 4 a 朗新公司也推出了 类似于t u r b o c l u s te : 的高可用性集群系统l o n g s h i n e c l u s t e r s e r v e r . 1 9 9 9 年9 月2 0日， 中国 第一家专业面向l i n u x 高端应用市场的 集群网络有限公司推出 了国内首例l i n u x 安全集群系统。 它是国内第一个通过公安部认证的安全l i n u x 系统， 而 其集群技术也已应用于诸多国际著名网站，如 l i n u x的门户 w w w .l i n u x .c o m、英国国家 j a n e t c a c h e 网、奥地利的入口 站点和瑞士电信等。其核心代码也己被纳入美国r e d h a t l i n u x 发布版的核心。 中国自 主开发研制的 集群式高性能计算机集群系统“ 自 强2 0 0 0 - s u h p c s ” 于2 0 0 0 年9 第 3页 国防科学技术大学研究生院学位论文 月在上海大学问世。 这一系统的峰值速度达到每秒 3 0 0 0亿次浮点操作。是当前中国国内 集群式高性能计算机系统中速度最快的。 从国内外研究现状来看，虽然目 前集群系统的应用在高可用性的研究上取得了一定的 成果，但仍很不成熟，采用的解决方案主要以专有结构和硬件冗余为主，代价昂贵，透明 性不高。 特别是这些应用较为广泛的集群系统大多数都为商业产品， 无法获取其技术实现。 在国内， 除了中国科技大学对集群系统的研究较为深入之外， 其他对集群系统的研究很少， 特别是基于l i n u x 的集群系统基本上还是空白。为研究集群技术， 采取自 主开发方式， 探 索以软件形式为主，硬件冗余相辅的高可用性解决方案具有开创性的意义。 1 . 2 . 2 高可用性的概念 川a ) ( 为使计算机保持不中断的应用服务，必须增进系统的稳定性及自 我修复的能力，尽可 能的避免因故障引 起的服务不可用。传统的容错方法主要针对集中式计算机系统，其主要 缺点表现在设备利用率低;不能在故障后自 动恢复应用软件的正常运行;价格昂贵难以普 遍应用。 针对这些不 足， 9 0 年代 初提出 了 高 可用性 ( h i g h a v a i l a b il i t y ) ， 既h a的 概念。 h a系统的实现目 标是: . 以分布式开放系统结构为基础实现高可用性， 价格低廉，资源利用率高，兼容性好， 便于集成。 . 从硬件到操作系统和应用软件，提供高可用性服务，避免单一失效点。即通过冗余的 方式保证系统各部件存在备份， 避免因单个部件的失效导致整体系统的崩溃。 高可用性在计算机产业界有一个较为成熟的理论基础和精确的定义。可靠性理论中一 般采用 r a s来定义系统环境的稳定性和完善性。 r a s即可靠性 r e l i a b i l i t y )、 可用性 ( a v a i l a b i l i t y ) 和可维护性 ( s e r v i c e a b i l i t y )。 . 可靠性通常是根据系统平均故障间隔时间 ( m e a n t im e t o f a i l u r e , m ttf )，即 平均 两次相邻故障之间的正常运行时间来衡量的。应用软件、操作系统、硬件设备等等很 多因素都可能对系统的可靠性产生影响。如果系统中一个关键性部件的m ttf 较低， 则将降低整个系统的可靠性。因此， 传统的容错机通常采用关键部件冗余的方法来提 高系统的可靠性。 . 可维护性衡量的是对系统或部件所提供的维护服务的时间，包括计划内的维护和不可 预知 的 服务。 通常 用 平 均 修复时 间( m e a n t im e t o r e p a i r , m t t r ) 来衡 量 可维 护 性， 即从系统中断到恢复正常运行的平均时间。 影响可维护性的因素包括故障监测、预防 j胜维护、现场支持、用户培训等。 . 可用性定义为在系统长时间运行期间内，系统正常运行时间占 总时间的比 例。即 系统正常运行时间 可用性 二( 1 - 1 ) 系统正常运行时间 + 系统故障时间 第 4页 国防科学技术大学研究生院学位论文 系统的可用性与可靠性和可维护性是密不可分的。假设系统的故障和恢复概率满足泊 松分布，即系统的故障率兄 = 1m t tf ， 修 复 率 “ - 都为常数，则可以证明 系统平均可 用度: a , - 召 m刀下 兄+ f mt t f + mt t r ( 1 - 2 ) 从 ( 2 )式可以看出，可用性是由可维护性和可靠性共同决定的。 另一种直观的度量计算机系统可用性的方法是一系统每年正常工作时间的百分比来表 示的。以此为基准可划分几类不同可用程度的系统。表1 - 1 列举了七种等级。 系统类型可用度等级不可用时间 ( 分钟 / 年) 可用度 %) 无管理系统 1 5 0 , 0 0 0 9 0 管理系统 2 5 , 0 0 0 9 9 管理良 好系统 35 0 0 9 9 . 9 容错系统 45 09 9 . 9 9 高可用系统 55 9 9 . 9 9 9 极高可用系统 60 . 59 9 . 9 9 9 9 超高可用系统 70 . 0 5 9 9 . 9 9 9 9 9 表 1 - 1计算机系统可用度等级列表 表 1 中高可用性系统一年平均停机时间小于5 分钟，这是常用的高可用性系统数值上 的定义。就可用性来说，容错系统要比高可用系统的级别低。 针对基于 l i n u x应用系统的高可用性研究，国内 外的许多机构和个人做了很多有意义 的 探索， 其中h i g h - a v a i l a b i l i t y l i n u x p ro j e c t 最为 著名。 h i g h - a v a i l a b i l i t y l i n u x p r o j e c t 的 基 本目 标是为l i n u x集群系统提供高可用性解决方案，以提高整体系统的可靠性、可用性和 可维护性。 作为开放源码项目， 它的h e a r t b e a t , f a k e 等软件得到了极其广泛的应用。 h e a r t b e a t 提供了两台主机之间的存活状态监控机制，而f a k e 则主要用于i p地址和ma c地址的接 管。二者的结合使用可以为集群系统提供较好的可用性支持。但通过分析其实现原理，我 们发现该方案存在最大的不足是不能保证客户请求连接的不中断。 在服务器发生故障的时 候， 客户将得到请求失败的信息， 并且不得不重新发起服务请求。 这不仅是时间上的浪费， 对于关键性的应用来说，它带来的损失可能将是无法弥补的。因此我们还需继续探索实时 性更高，透明性更好的高可用解决方案。 . 2 . 3 检查点机制 ( c h e c k p o i n t ) 设置检查 点( c h e c k p o i n t i n g ) 是容错计 算机系统 进行故障 恢复的 重要手段 通过周期性的设置检查点，把程序在运行时的正确状态保存到稳定存储器中 计算机系统 如果在随后 第 5页 国防科学技术大学研究生院学位论文 的 运行 过 程中 发 生故 障， 那 么 系 统 进行 卷回 恢 复 ( r o l lb a c k r e c o v e r y ) ， 从 稳 定 存 储 器中 读 出前一个检查点时的正确状态，从该点继续执行。这样可以 避免由于故障而导致的程序从 头重新执行， 因而能有效地减少计算的损失。 d u d a 证明在故障条件下， 如果不使用检查点， 程序平均执行时间随其有效执行时间 ( 假设不发生故障时的执行时间)呈指数增长，而使 用固定间隔的 检查点则呈线性增长1 z , 1 。实际 上，当 故障率超过一定值， 两次故障的平均 间隔时间小于程序的有效执行时间的时候， 如果不使用检查点， 程序几乎不能运行到结束。 检查点机制包括两个基本过程: . 状 态检 查 ( c h e c k p o in ti n g ) ， 即 记 录进 程 运 行的 中 间 状 态 信息的 过 程; . 状态恢复 ( r e s t a rt i n g ) ， 是 指利 用状态 检查 所记录的 进程一 致性状态 信息 产生 一个和 原进程具有相同中间状态的进程的过程。 而 状态检查主要又有两 种实 现 方式 1 3 1 . . 一是进程本身调用状态检查函数保存进程状态，称之为内部状态检查 ( i n t e r - c h e c k p o i n tin g ) 。 采用内 部 状态 检查 相 对 来 说比 较 简 单， 因 为 绝 大多 数 上 下 文 信息 对于进程本身来说都是 可见的。 这种 方式一 般通过信号( s i g n a l ) 处理机 制来完 成 检查点状态检查。但是它需要修改应用程序甚至是系统内核的源代码，透明性不高是 其最大的缺点。 . 二是外部进程 对指定 进 程进行状态检查， 称之为 外部 状态检查( e x t e r - c h e c k p o i n t in g ) 。 该方式通过操作系统提供的进程间地址访问接口，可以在核心地址空间访问任意进程 用户地址空间。 例如通过p r o c 进程文件系统， 可以 普通的读写方式访问 权限许可范围 内的任何一个进程的上下文信息。外部状态检查最大的优点是不必修改应用程序与系 统内核，透明性高。 检查点机制作为一种后向故障恢复技术，能够将因故障导致的计算损失降低到最小， 因此在数据库系统容错，关键性业务高可用性方面应用广泛。国内外对于检查点机制的 研 究也是方兴未艾。 检查点机制通常是以软件包、函数库、功能模块等形式实现。 其中较为 著名的包括e p c k p t , c r a k , d y n a m i t e , c k p t , l i b c k p t , c o n d o r , c o c h e c k 等， 见下表: 名 称描述及特征操作系统实现形式 e p c k p t支持并行进程、共享内存、当 前目 录、文件及管道等 l in u x , s y s t e m v系统内核实现 cr ak 基于 e p c k p t开发，实现了 e p c k p t 相同 功能， 并 支持s o c k e t 状态检查 li n u x 系统内核模块 d y n a m i t e无需重新编译或重新链接，支 持并行进程 l i n u x , s o l a r i s 用户层实现 ckp t 无需重新编译或重新链接应用 程序 l i n u x 用户层实现 第 6页 国 防科学技术大学研究生院学位论文 l i b c k p t co n d o r 性能优化，对应用程序透明 仅支持单进程，主要用于任务 的调度 一致性状态检查， 支持p v m和 mp i 用户层函数库 用户层函数库 un i x 用户层函数库 表1 - 2利用检查点机制的 几个系统 本文针对应用的实际，要求检查点机制基于 l i n u x操作系统开发，并具有较高的透明 j性，即不修改系统内核，不重新编译和链接应用程序，因此采用系统内核模块，以外部状 态检查的方式给予实现。 1 . 2 . 4 进程迁移技术 ( p r o c e s s m i g r a t i o n ) 进程迁移 ( p r o c e s s m i g r a t i o n ) 是实现集群系统高 可用性的关键技术之一。 进程迁移的 基本思想是在进程运行的过程中，将进程转移到其他的处理器上运行，并且对资源的访问 也能够延续。如果这一过程不需要被迁移进程或用户的干预，表示这种迁移是透明的 ( t r a n s p a r e n t ) 。 简单地说， 进 程迁移的 过程就是 进程 计算和通信状 态的 保存及 在其他处 理 器上恢复的过程。 进程迁移的概念最初源于分布式系统中，主要目的在于提高分布式系统的性能及可靠 j性。在集群等分布式系统中， 进程迁移具有广泛的适用性p 4 , 2 e , 2 8 i . . 动态负载平衡:将进程迁移到负载轻或空闲的节点上，充分利用可用资源，通过减少 节点间负载的差异来全面提高性能。 . 容错性和高可用性:某节点出现故障时，通过将进程迁移到其它节点继续恢复运行， 这将极大的提高系统的可靠性和可用性。 . 并行文件1 o : 将进程迁移到文件服务器上进行i o ， 而不是通过传统的从文件服务器通 过网络将数据传输给进程。对于那些需向文件服务器请求大量数据的进程，这将有效 的减少了通讯量，极大的提高效率。 . 充分利用特殊资源:进程可以通过迁移来利用某节点上独特的硬件或软件能力。 . 内 存引 导 ( m e m o ry u s h e r i n g ) 机制: 当 一 个节点 耗尽它的主 存时，内 存引导 机制 将允 许进程迁移到其它拥有空闲内存的节点，而不是让该节点频繁地进行分页或和外存进 行交换。这种方式适合于负载较为均衡，但内存使用存在差异或内存物理配置存在差 异的系统。 进程迁移技术随着集群等分布式系统的发展而发展。国内外许多大学和研究机构针对 各自的需求和目的，对进程迁移技术进行了大量的研究和开发工作。下面列举一些比较著 名的 进程 迁移系 统 【2 6 ) .f r e e d ma n f r e e d m a n 是一个非常简单的进程迁移系统，完全在用户空间实现。系统能够传输进程 第 7页 国防科学技术大学研究生院学位论文 的内存映象，但是不支持操作系统状态，如文件描述字，进程标识符，套接字地址等的传 输。为利用这种迁移的机制，应用程序需要作一定的修改，并周期性地检查是否被通知迁 移，在迁移前后要增加 “ h o o k ”函数。要迁移的进程由 动态负载平衡算法来确定。 . c o n d o r 2 1 在 wi s c o n s i n - ma d i s o n大学开发的分布式资源管理系统 c o n d o r ，用于工作站网络环境 下提高空闲主机的利用率。系统提供进程记录检查点和迁移的机制，每个提交的程序通过 记录检查点的方式 ( 用一个特殊的信号处理程序来实现)，生成一个新的可执行文件，该 文件在另外的主机上能够从该检查点处开始执行。 但是c o n d o : 系统不支持信号， 共享库， 以及包括套接字在内的所有进程间通信机制。 . a c c e n t c a r n e g i e m e l l o n 大 学1 9 8 7 年 研制了a c c e n t 系 统。 它 基于 一 个 新的 与u n i x 不兼 容的 核 心， 其 进 程间 通 信通过“ 端口( p o r t ) ” 的 抽 象来 完 成异 步 消息 的 传 输。 z a y a s 给系 统 增 加了进程迁移，他认为传输大块的地址空间是阻止快速迁移的一个瓶颈。为了减少数据传 输，系统在主机间进行的是逻辑传送而不是物理传送。 迁移采用c o p y - o n - r e f e r e n c e 方法， 只有当进程需要时， 页面才被传送到目的节点上去。 该项目 最终导致了ma c h 系统的研制。 .c h a r l o t t e wi s c o n s i n - m a d i s o n 大学 1 9 8 6 年研制的分布式操作系统c h a r l o t t e ，作为分布式算法和 负载分布策略的一个试验平台。 系统进程间通信通过一种 “ 链接 ( l i n k )”抽象来实现， 简化了 进程迁移对i p c的冲击。 c h a r l o t t e 进程迁移系统容错性高，并且具有很低的剩余依 赖性。但系统与u n i x不兼容，文件系统难以使用并且可能导致差的性能。 .de mos / map 加州大学b e r k e l e y 分 校于1 9 8 3 年研 制d e m o s / m a p ， 是 最早实 现完全 透明 进程迁移 机制的系统之一。它是基于消息的操作系统，通过面向 通信的核心调用来处理通信。 .l o c u s 加州大学l o s a n g e l e s 分校1 9 7 9 年启动的 分布式 操作系 统研究 课题l o c u s ， 旨 在建立一 个分布式的，高可用的，与s y s te m v和b s d u n i x兼容的操作系统版本。它对、u n i x核 心作了修改，加强了网络文件系统的支持，进程间通信通过扩充了的 u n i x 中的 “ 管道 ( p i p e )” 抽象来实 现。 . mo s i x 1 4 1 1 9 8 2 年，位于j e ru s a l e m的h e b r e w大学研制的mo s i x ，是一个多机操作系统，将松 散祸合的计算机机群集成为一个单一的类u n i x环境，重写了一个新的操作系统核心，并 支持u n i x系统v版本2 的i p c标准，即消息， 共享内存， 信号量， 管道和信号等。 进程 可以在主机之间自由迁移。 mo s i x实现了一个分布式的负载平衡策略， 成为该领域的典范。 . s p r i t e 5 1 加州大学b e r k e l e y 分校在八十年代研制的实验性操作系统s p r i t e . 与u n i x b s d 4 .3 兼 第 8页