（计算机应用技术专业论文）基于统计学习方法的容错计算.pdf

摘要 现代计算机系统不断增长的复杂性使得故障检测与诊断工作极其困难，因此 如何实现快速的故障恢复从而提高系统的可用性变得更加重要了。由于即使在实 际故障源未知的情况下，很大一部分故障仍能通过执行一些特殊的恢复操作，例 如，重起操作，来进行修复。然而，通常设计合理的恢复策略来有效的调度潜在 的恢复操作通常是极其困难而且容易出错的。因此，我们希望能找到一种自动的 方式来生成高效的恢复策略。 在本文中，我们提出了一种基于增强学习算法的新技术来自动产生恢复策 略。我们首先将自动故障恢复问题形式化，在理论上分析出了增强学习方式的有 效性。然后，基于一个由原始人工策略生成的故障恢复日志，我们对此方法的两 种不同实现方式进行了实验验证： 一种是直接的在线学习方式，即直接将该学习过程应用于运行的系统中。通 过实验分析我们可以发现，我们的学习方法能获得更优的性能，较好的扩展性， 以及趋向于全局最优策略的收敛性。此外，通过引入故障发生的多种特征，我们 仍然验证了我们方法的有效性。 另一种是离线学习方式，即将该学习过程应用于故障恢复日志来生成恢复策 略。由于受到原始人工定义的恢复策略的影响，该实现方式学习得到的是一个局 部最优的恢复策略，然而它具有比原始手工策略更好的性能。在我们的实验中， 基于真实的机群系统环境产生的恢复数据，我们发现自动生成的恢复策略最终能 节省1 0 的恢复时间。此外，为了避免学习所得策略可能遇到的无法处理的情形， 我们还提出了一个混合策略，它能兼两者之长，不仅能维持学习得到的策略的高 性能，还能像人工定义策略那样处理所有可能的故障情形。 关键词：容错计算统计学习理论q 学习增强学习自动故障恢复 a bs t r a c t t h ei n c r e a s i n gc o m p l e x i t yo fm o d e mc o m p u t e rs y s t e m sm a k e sf a u kd e t e c t i o n a n dl o c a l i z a t i o np r o h i b i t i v e l ye x p e n s i v e ，t h e r e f o r ef a s tr e c o v e r yf r o mf a i l u r e s i s b e c o m i n gm o r ea n d m o r ei m p o r t a n t as i g n i f i c a n tf r a c t i o no ff a i l u r e sc a r lb ec u r e db y e x e c u t i n gs p e c i f i cr e p a i ra c t i o n s ，e g r e b o o t , e v e nw h e nt h ee x a c tr o o tc a u s e sa r e u n k n o w n h o w e v e r , d e s i g n i n gr e a s o n a b l er e c o v e r yp o l i c i e st o s c h e d u l ep o t e n t i a l r e p a i ra c t i o n se f f e c t i v e l yc o u l db ed i f f i c u ha n de r r o r - p r o n e s ow ea t t e m p t t of m da n a u t o m a t i cw a yt og e n e r a t er e c o v e r yp o l i c i e sw i t hh i 曲p e r f o r m a n c e i nt h i sp a p e r , w ep r e s e n tan o v e la p p r o a c ht oa u t o m a t er e c o v e r yp o l i c yg e n e r a t i o n w i t hr e i n f o r c e m e n tl e a r n i n gt e c h n i q u e s w ef i r s tf o r m a l i z e dt h ea u t o m a t i ce r r o r r e c o v e r yp r o b l e m ，a n dp r o v e dt h ee f f e c t i v e n e s so f o u rr e i n f o r c e m e n tl e a r n i n gm e t h o d i nt h e o r y t h e nb a s e do nt h er e c o v e r yh i s t o r yo ft h eo r i g i n a lu s e r - d e f i n e dp o l i c y , w e v e r i f i e dt w od i f f e r e n ti m p l e m e n t a t i o n so ft h em e t h o dt h r o u g he x p e r i m e n t s o n ei st h ed k e c to n l i n el e a r n i n ga p p r o a c h ，w h i c hd i r e c t l ya p p l i e st h el e a r n i n g p r o c e s si nt h er u n n i n gs y s t e m t h r o u g he x p e r i m e n t a la n a l y s i s ，w ec a nf i n dt h a to u r l e a r n i n gm e t h o dc a no b t a i nb e t t e rp e r f o r m a n c e ，h a v es c a l a b i l i t y a n dc o n v e r g e n c e w h i c hl e a d st ot h eg l o b a l l yo p t i m a lp o l i c y b e s i d e s ，b yi n t r o d u c i n gt h es p e c i a le r r o r p a t t e r n ，w es t i l lv e r i f yt h ee f f e c t i v e n e s so f o u rm e t h o d t h eo t h e ro n ei st h eo f f l i n el e a r n i n ga p p r o a c h ，w h i c ha p p l i e st h el e a r n i n gp r o c e s s o nt h ee r r o rr e c o v e r yh i s t o r yt og e n e r a t er e c o v e r yp o l i c i e s a f f e c t e db yo r i g i n a l u s e r - d e f i n e dp o l i c y , t h er e c o v e r yp o l i c yg e n e r a t e db yo u rm e t h o di sl o c a l l yo p t i m a l ， b u ti to u t p e r f o r m st h eo r i g i n a lo n e i no u re x p e r i m e n to nt h ed a t af r o mar e a lc l u s t e r e n v i r o n m e n t , w ef o u n dt h a tt h ea u t o m a t i c a l l yg e n e r a t e dp o l i c yf i n a l l ys a v e s10 m a c h i n ed o w n t i m e m o r e o v e 5t oa v o i dt h es i t u a t i o ni nw h i c ht h el e a r n e dp o l i c ym a y n o th a n d l es o m ee r r o rc a s e s ，w ep r o p o s e dah y b r i dm e t h o d ，w h i c hc o u l dt a k e a d v a n t a g e so fb o t ht w om e t h o d s ，n o to n l ym a i n t a i n i n gt h eh i 曲p e r f o r m a n c eo f t h e l e a r n e dp o l i c y , b u ta l s oh a n d l i n ga l lp o s s i b l ec a s e sl i k eu s e r - d e f m e dp o l i c y k e yw o r d s ：f a u l t - t o l e r a n tc o m p u t i n g ；s t a t i s t i c a ll e a m i n gt h e o r y ；q - l e a r n i n g ； r e i n f o r c e m e n tl e a r n i n g ；a u t o m a t i ce r r o rr e c o v e r y ； 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的研究成 果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表或撰写过的 研究成果，也不包含为获得叁壅盘茔或其他教育机构的学位或证书而使用过的材 料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表 示了谢意。 学位论文作者签名：辛微镧签字日期：2 田了年1 月z 71 3 学位论文版权使用授权书 本学位论文作者完全了解丞盎盘茎有关保留、使用学位论文的规定。特授 权苤鲞盘堂可以将学位论文的全部或部分内容编入有关数据库进行检索，并采用影 印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校向国家有关部门或 机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名： 芥蝴 导师签名： 廷讼 签字日期：2 7 年1月彳1 3 签字日期：伽7 彳、月7 日 第一章绪论 第一章绪论 本章主要介绍选题背景，研究对象，以及相关的研究内容。 1 1 选题背景与研究意义 计算机自2 0 世纪4 0 年代后期问世以来发展异常迅速，应用日益广泛。于是， 人们不得不考虑一个问题：当今社会越来越依赖于计算机，可是计算机是否非常 值得信赖呢? 答案并非那么肯定。因为数十年来有过不少由于计算机系统的失效 而导致的恶性事故。例如，美国向火星发射的火星一号火箭由于计算机程序中丢 掉一个字符而惨遭失败；1 9 7 9 年，新西兰航空公司的一架客机因为计算机控制 的自动飞行系统发生故障而撞到阿尔卑斯山上，机上2 5 7 名乘客全部遇难；再 如，1 9 9 7 年7 月，大韩航空公司的一架民航飞机在关岛机场坠毁，机上2 0 0 余 名乘客全部遇难，而飞机坠毁原因是由于机场的导航计算机系统出现故障。这些 例子无一不说明提高计算机系统可靠性的迫切性。不仅如此，随着i n t e r n e t 的出 现，近些年来出现了越来越多的大型复杂机群系统以及网络系统，为人类提供着 各式各样的网络服务。同时随之而来的问题是对于这些大规模的复杂系统，如何 保证其可靠性。 ， 为了提高计算机系统可靠性，有两种基本方法一避错与容错。避错( f a u l t a v o i d a n c e ) 技术靠预先排除所有故障来提高可靠性，试图构造出不包含故障的 “完美”系统，其手段是采用正确的设计与质量管理方法来尽量避免把故障引入 系统，实际上要绝对做到这一点几乎是不可能的，所以避错的现实目的在于使系 统的失效率降低到一个可接受的数值，对避错技术的研究与应用自从计算机问世 之日就开始了，时至今日，这门技术已得到了很大的发展，并己成为提高计算机 系统可靠性的基本方法。但实践证明，避错技术的效果有一定的限度( 比如最多 使系统的平均无故障时间增加一个数量级) ，超过这个限度将使成本急剧上升， 所以单靠实施避错已适应不了那些可靠性要求特别高的应用领域。于是，与避错 技术互补的提高计算机系统可靠性的另一种方法一容错技术( f a u l t t o l e r a n t ) 应运而生。 已有的容错技术方法大多需要专家的精细设计，并依赖于各种模型，对于复 杂系统而言，这种方式往往效率较低，而且代价比较高。因此，如何将人工智能 领域经典的统计学习理论应用于容错技术，从而减少人为的干预并提高执行效率 第一章绪论 具有极其重要的意义，这也正是本文的研究重点。 1 2 容错计算 “容错”一词是a l g i r d a sa v i z i e n i s 于1 9 6 7 年在他的著名论文“d e s i g no f f a u l t t o l e r a n tc o m p u t e r s 中首次提出的，即，如果一个系统的程序在出现逻辑 故障的情况下仍能被正确执行，那么我们称这个系统是容错的。 目前，一种被普遍接受的“容错计算机系统( f a u l t - t o l e r a n t c o m p u t e r s y s t e m ) 的定义为在出现硬件故障或软件错误的情况下仍能继续正确执行指定任务的计 算机系统。相应地，定义与分析容错计算机系统的各种技术称为容错技术 ( f a u l t - t o l e r a n tt e c h n o l o g y ) 。有关计算机容错技术的各种理论与实际应用的研 究已发展成为计算机科学的一个重要分支，称为容错计算( f a u l t - t o l e r a n t c o m p u t i n g ) 。而容错性则是使一个系统具备能够在一些特定故障存在的情况下继 续正确执行其程序和输入输出功能的内在能力( 无外界帮助) 的一种属性或素 质。其中“正确执行”指程序、数据及结果不包含差错，并且执行时间未超过规 定的限度。 容错计算的产生与发展首先借助于计算机设计者应用各种实用技术提高计 算可靠度的不断努力。从第一台计算机建成并投入运行，人们就发现，单凭认真 细致的设计与选用优良器件是无法避免物理缺陷及设计错误的发生。正因这样， 早期计算机的设计者采用了冗余结构以屏蔽失效的部件及错误的控制码；采用了 二模或三模表决策略以检测或校正信息差错；采用了诊断技术以定位失效部件并 自动进行切换以替代失效的部件或子系统。其次，在工程技术不断发展的同时， 计算机科学的一些开拓者也在进行着“用不可靠的元部件构造可靠系统”的一般 问题的研究。最有代表性的有冯诺依曼( j o h nv o nn e u m a n n ) ，莫尔( e f m o o r e ) 与香农( c e s h a n n o n ) 等人，他们的研究成果奠定了容错计算的理论基础。特 别是冯诺依曼，他不仅是计算机体系结构的创立者，也被认为是容错计算的奠 基人。早在1 9 5 2 年，冯诺依曼就在美国加利福尼亚理工学院作过五个关于复 用逻辑模块来提高系统可靠性的报告，并指出：人脑工作的可靠性是由结构上较 低级的冗余来保证的。1 9 5 6 年，他又提出了“多数表决( m a j o r i t yv o t i n g ) ” 的概念，并证明了( 通过容错技术) 可以用较不可靠的器件组成较可靠的系统的 重要论断。5 0 年代后期航天与航空等领域所要求的高可靠性为容错技术提出了 新的挑战并创造了绝好的应用场所。 我们将在下一章详细介绍容错计算，给出容错计算系统的框架，并讨论各项 已有的相关技术。 2 第一章绪论 1 3 本文主要的研究内容 本文主要探讨容错计算技术，并研究如何将人工智能领域经典的统计学习理 论应用于容错技术，从而减少人为的干预并提高容错性能。具体而言，我们主要 解决了自动故障恢复的优化问题，主要内容包括： 1 已有容错技术分析( 第2 ，4 章) 2 基于增强学习方法的自动故障恢复技术( 第4 章) 3 真实故障数据的统计与分析( 第5 章) 4 在线学习方式及其实验结果( 第6 章) 5 离线学习方式及其实验结果( 第7 章) 结果显示，应用统计学习方法我们能以自动的方式获得较好的故障恢复性 能。此外，我们还考虑了应用过程中的各种实际问题，如学习代价，学习速度， 收敛性，额外存储空间大小等，提出了相应的解决方案并给出了有关的理论依据。 最后，我们还提出了进一步的可能改进方案。 第二章容错系统及相关技术 第二章容错系统及相关技术 本章主要介绍容错系统及有关概念，讨论该框架下各环节的相关技术，并给 出一个分布式系统上的具体应用。 2 1 引言 随着我们的高科技社会正变得越来越依赖于电脑，对于可靠系统的需求也在 逐步增长并很可能成为一种规范。在过去，容错系统仅仅存在于一些特殊的组织 例如电信公司和金融机构。随着i n t e m e t 上b 2 b 商业交易模式的逐步扩大，我们 所关注的不仅仅是保证系统能按照需求来工作，更重要的是，当有不可避免的故 障发生时，使之带来的危害最小化。 一般而言，实现避错技术是极其困难的，它涉及到复杂的算法来处理现实世 界本身所固有的复杂性。正如事实所显示的那样，开发一个完全坚固的，1 0 0 可靠的系统是不可能的。无论我们怎么努力，总存在着一种某一部分出错的可能。 因此，我们可以做到的最好情形是将故障发生的可能性降到一个可以接受的范 围，然而不幸的是，通常我们在努力降低故障发生频率的同时，其代价也变得越 来越大。因此，有必要采用容错技术来有效地面对这些困难。下面我们将主要介 绍容错系统框架及其各环节的相关技术。 2 2 容错系统框架 此节我们先给出容错系统的有关概念作为背景知识，然后展示其总体框架。 2 2 1 相关概念 这里我们主要涉及到三组概念，分别介绍如下： 1 可靠性 可靠性( d e p e n d a b i l i t y 是指系统能可靠的执行所设计的功能，它主要包含 了四个方面：有效性( r e l i a b i l i t y ) 用来衡量系统正确执行服务请求的能力；可 用性( a v a i l a b i l i t y ) 用来衡量当有服务请求时系统的可用状况；保险性( s a f e t y ) 用来衡量系统能避免灾难性故障( 涉及到人的生命财产损失) 的能力；安全性 4 第二章容错系统及相关技术 ( s e c u r i t y ) 用来衡量系统防止非法访问的能力。在本文中我们主要关心前两个 指标。 从技术上说，有效性可以定义为到指定点之前的正确执行概率，一个常用的 衡量参数是故障发生的平均间隔时间( m t b f ) 。同样，可用性可以定义为在指 定点之前系统可以操作的概率。对于给定系统，该指标依赖于故障发生时系统恢 复到正常状态的时间，常用的衡量参数是平均恢复时间( m 1 限) 。如果一个系 统从未发生故障，则该系统的有效性等价于可用性。 2 错误，故障，与缺陷 容错计算定义中隐含了一个假设是存在一种描述什么是正确行为。当实际的 运行系统偏离了这种描述行为时，就说明发生了一个错误( f a i l u r e ) 。导致这种错 误的状态称为故障( e r r o r ) ，它通常代表了一个系统行为描述里不允许的无效状 态。故障本身是由于系统缺陷( f a u l t ) 所导致的结果。换句话说，系统缺陷是导 致错误的根本原因( 故障源) ，而错误仅仅是该缺陷所表现出的症状。一个缺陷 不一定会导致一个故障，但相同缺陷可能会导致多个不同故障。相似的，一个故 障可能导致多个不同错误。这些基本概念可以用统一建模语言( 眦) 描述为 如图2 1 所示。 图2 1 错误，故障与缺陷之间的u m l 描述 举例如下，在一个软件系统中，程序中一个不正确的读入指令将减少某一个 内部变量而不是增加它。显然，如果该指令被执行，它将导致写入一个不正确的 值。如果该程序的其他指令使用到了这个值，整个系统将偏离所期望的正常行为。 第二章容错系统及相关技术 在这种情况下，错误的指令即为缺陷，无效值即为故障，而错误则是该故障所导 致的行为。值得注意的是，如果该变量在写入之后从未被读入过，则不会发生任 何错误，或者如果无效指令没有被执行，该缺陷也不会导致故障。因此，仅仅出 现故障或缺陷并不一定意味着有错误发生。 3 故障源分类 将故障源按不同方式进行分类有助于我们进一步了解故障特性，用u m l 表 示的一个具体分类图如图2 2 所示： no 。，：。1 。”* a u ! 。，! 、一，e i 0 。j ，l 令个令 l 土主吉连制 陋熹l 由由由出筒f 令 舀副 l n l o r r n i t t e n t 图2 2 故障源分类 基于持续的时间长度，故障源可以分为短暂的( t r a n s i e n t ) 和永久的 ( p e r m a n e n t ) 。短暂的故障源最终将消失掉而无需任何显式的人为干预，而永久 故障源将一直存在直至外部行为将之移除。虽然永久故障源危害性更大，但从工 程的角度，它们也更容易被诊断和处理。对于短暂故障源而言，它们所带来的问 题往往是不可预测的。 另一种分类方式可按照原因分类。设计缺陷( d e s i g nf a u l t s ) 是由于设计失误 导致的，由于在实际中设计一个完全无缺陷的系统是不现实的，因此，很多容错 系统都假设设计缺陷是不可避免的，它们所需要做的就是尽量的应对这些缺陷来 保护系统。另一方面，操作缺陷( o p e r a t i o n a lf a u l t s ) 则是由于某些物理原因造 成的，如处理器故障或磁盘崩溃。 最后根据故障组件行为分，故障源可分为如下几类：崩溃故障( c r a s hf a u l t s ) ， 即该组件及不完全停止也无法返回到一个有效状态；省略故障( o m i s s i o nf a u l t s ) ， 即该组件完全不能执行它的服务；时间故障( t i m i n gf a u l t s ) ，即该组件不能按时 完成它的服务；拜占庭式故障( b y z a n t i n ef a u l t s ) ，即任意的自然条件下所导致的 故障。 6 第二章容错系统及相关技术 2 2 2 总体框架 总的来说，处理故障的典型过程可分为四个阶段，其总体框架如图2 3 所示： 图2 3 容错系统总体框架 故障探测( e r r o rd e t e c t i o n ) 是一个识别系统是否处于有效状态的过程。这也 意味着系统中的某一个组件发生了错误。为了保证该故障的影响是有限的，有必 要孤立该故障组件以免它的影响会传播到更大的范围，这个过程称为损害限制 ( d a m a g ec o n f m e m e n t ) 。在故障恢复阶段( e r r o rr e c o v e r y ) ，该故障，更重要的是， 它的影响将通过恢复该系统到一个有效状态来消除。最后，在故障源处理阶段 ( f a u l tt r e a t m e n t ) ，将分析导致该故障的潜在系统缺陷并处理。这就是说，我们 将首先处理故障状态，然后再查找导致该故障的根本原因。虽然从直观上看，首 先查找出错原因似乎更加合理，但是这是很不实际的，因为这种诊断过程往往是 很复杂而且十分耗时的。比如在一个软件系统中，一种典型状况是一个缺陷会导 致及联的多个故障被独立的报告出来，考察和追踪这些错误报告之间的联系往往 需要一个很复杂的推理过程。 2 3 相关技术 本节主要对上述容错系统框架中已有的各项技术作一简单介绍。 2 3 1 故障探测 最常用的用于故障探测的技术包括： 7 第二章容错系统及相关技术 1 副本校验 在此方法中，使用组件的多个副本来同时执行相同的服务。然后比较各副本 的输出，如出现偏差则标志着一个或多个组件发生了错误。这种方法的一个特殊 形式是用在硬件中的t r i p l e - m o d u l a rr e d u n d a n c y ( t m r ) 技术，其中每次比较三个独 立组件的输出，并且这些组件的主要输出将被实际的传递出去。在软件方面，这 种方法可通过提供同一组件的多个实现方式来实现( n - v e r s i o np r o g r a m m i n g ) 。 2 时间校验 这种方法用于探测时间故障。通常启动一个计时器，设定该服务的期望完成 时间作为截止时间。如果该服务在计时器结束之前成功完成，将取消计时。反之， 如出现超时，则说明出现了时间故障。在此方法中，如何确定合理的截止时间是 一个很重要的问题。 3 运行时限制校验 此方法用于在运行时校验某一些限制，例如一些变量值是否越界等。可能存 在的问题是这种校验机制为代码和性能带来了额外的负担。一种特别的形式是 r o b u s td a t as t r u c t u r e s ，它内嵌了冗余机制( 例如校验和) 。每次当这些数据结构发 生改变时，将执行冗余校验来探测是否发生了不一致现象。 4 诊断校验 此方法中有大量的后台观察代理用来确定是否一个组件在正确执行，在很多 情况下，诊断校验用于检测那些已知输入和输出的组件。 2 3 2 损害限制 此过程首先确定该故障已传播的范围( 由于从故障发生到检测到故障之间存 在着一定的时间延迟) 。它需要理解一个系统的信息流并从已知的故障组件开始 跟踪它。该信息流上的每一个组件都将被检测是否发生故障，这样直至找到其边 界。一旦确定了边界，该系统的这部分组件间被隔离直至该故障被修复。 为了辅助该损害限制过程，需要在各组件之间创建一些特殊的防火墙。这就 意味着各组件之间存在着松散耦合，这样防火墙之外的组件可以被轻松的隔离开 来。该方法的代价是增加了额外系统负担，无论是性能方面还是存储方面。 2 3 3 故障恢复 为了恢复一个故障，系统需要被恢复到一个有效状态。通常用两种方法来达 到此效果：一个是后向故障恢复( b a c k w a r de r r o rr e c o v e r y ) ，这里，系统将被恢 复到之前己知的有效状态。这种方法通常需要检验指示( c h e c k p o i n t i n g ) 系统状 8 第二章容错系统及相关技术 态，一旦有故障被检测到，就将系统状态恢复到上次检验有效的状态上。显然这 样做的代价是很高的，不仅因为它需要保存以前的状态。还因为它在检验指示的 过程中需要中断系统操作以保证所保存状态的一致性。很多情况下，这是不可行 的，因为它可能无法将系统正在运行的环境恢复到相应的记录状态上。 对于这些情况，使用后向故障恢复( f o r w a r de r r o rr e c o v e r y ) 方法会更加合适， 这种方法会促使系统从当前故障状态转移到一个新的有效状态。但是在实际应用 中很少使用后向故障恢复技术。 2 3 4 故障源处理 在这一阶段，故障源将被定位并被修复。修复过程依赖于故障源的类型。永 久故障需要将故障组件替换为正常组件。这就需要一个备用组件( s t a n d b y c o m p o n e n t ) 。将备用组件集成到系统中需要保证其状态与系统状态保持同步。通 常有三种备用机制： 1 冷备用( c o l ds t a n d b y ) 该机制意味着备用组件是非操作的，因此当更替操作发生时需将它的状态进 行完全的改变，这将导致较大代价和较长时间的操作。 2 温备用( w a r ms t a n d b y ) 在此情况下，备用组件将用来保持操作组件上一次检测校验的状态。当主组 件发生故障时，后向恢复时间较短。 3 热备用( h o ts t a n d b y ) 在这种方法中，备用组件是完全活动的，并保存了主组件的功能副本，这样， 如果发生故障，恢复过程将极其迅速。该机制的主要问题是在锁定步骤中很难维 护两个组件。 2 4 分布式系统的容错模型 本节我们给出了一个在分布式环境下成功用于创建复杂容错嵌入式系统的 特殊模型。该模型适合一类实际中常用的基于星型拓扑结构( 如图2 4 ) 的分布 式应用。 该系统包含了一个分布式的a g e n t 集合，每一个a g e n t 都位于单独的处理地址， 并通过合作来实现一些功能。控制端( c o n t r o l l e r ) 主要用于协调各a g e n t 的操作。 值得注意的是a g e n t 并不是只能通过控制端来通信，图中没有画出这些连接的原 因是在本节中他们是无关的。我们对该系统作了如下假设： 1 温和的反应时间。即全局功能的处理时间允许一定的变动。 第二章容错系统及相关技术 2 无关键节点。即当有一个或多个a g e n t 出现永久故障时，系统仍然是有 用的。 在此系统中，中央控制端的永久故障将导致全局功能的损失。因此，该节点 需要保持其具有一定的容错性。然而，我们还希望避免一个完全的热备用机制所 需的额外负担 图2 - 4 分布式系统的星型拓扑结构 该方法的核心特征是将系统的状态信息进行分布式存储，即控制端维护一个 包括每一个a g e n t 状态信息在内的全局状态信息；每一个a g e n t 端都保存自己的 状态信息。当有a g e n t 状态信息发生变化时，它将通知控制端该变化，并由控制 端缓存该信息，因此这里是有状态冗余的。值得注意的是我们无需一个集中式的 整个系统的一致检测点。 显然，状态冗余仍无法应对控制断的永久故障，因此如何恢复控制端的故障 是极其重要的。实际上，控制端的恢复机制可以用一个简单的低负担的冷备用机 制来实现。该备用控制端可通过依次查询各个a g e n t 端来恢复全局状态信息。此 外，当有一个a g e n t 发生故障并恢复时，它可以从中央控制端获取其局部状态信 息。这种拓扑结构一个有趣的方面是其控制端无需监控各a g e n t 节点。一个恢复 中的节点仅仅需要联系该控制器以获得自己的状态信息。 2 5 小结 本章主要介绍容错系统及有关概念，包括可靠性定义，故障的定义，以及故 障源的分类。给出了总的容错框架并讨论了该框架下各环节的相关技术，主要介 绍了故障探测，损害限制，故障恢复，和故障源处理这四个关键环节的已有技术。 最后基于以上理论，我们还给出了一个分布式容错系统上的具体实现。然而，这 些容错技术大多是基于模型的，在下一章中，我们将讨论目前比较流行的将统计 学习理论应用于容错计算甚至系统管理方面的新的方法。 第三章统计学习方法及其在系统管理方面的应用 第三章统计学习方法及其在系统管理方面的应用 作为本文的核心理论，本章主要介绍统计学习方法相关理论，在此基础上， 我们还将讨论将统计学习方法应用于系统管理方面的最新的一些技术。 3 1 引言 现实世界中存在大量我们尚无法准确认识但却可以进行观测的事物，如人类 可以准确地识别出数字图像中的人脸，但却无法使用传统的编程技术，让计算机 自动地完成人脸识别，诸如此类的问题在科学、财经和工业领域普遍存在，如过 滤垃圾邮件、预测各类金融数据、在d n a 序列中寻找有效基因等等，对此类问 题的有效解决，将会给人类的生活带来极大益处。 统计是我们面对大量数据而又缺乏理论模型时最基本的分析手段，基于统计 数据的机器学习主要研究如何从一些观察数据出发得出目前尚不能通过原理分 析得到的规律，利用这些规律去分析客观对象，对未来数据或无法观测的数据进 行预测。但传统统计学中的诸多结论，是在样本数目足够多的前提下进行研究的， 所提出的各种方法和结论只有在样本数趋向无穷大时其性能才有理论上的保证。 而在多数实际应用中，样本数目通常是有限的，这是很多传统统计方法都难以取 得理想效果的原因之一。， 与传统统计模式识别的方法不同，统计学习理论( s t a t i s t i c a ll e a r n i n gt h e o r y , s l t ) 是一种专门的小样本统计理论。vv a p n i k 早在2 0 世纪6 0 年代就开始了统 计学习理论的研究，作为一种针对有限样本的函数预测问题的纯理论分析工具， 并相继提出了v c 维理论、结构风险最小化原理( s t r u c t u r a lr i s km i n i m i z a t i o n ， s r m ) ，有效克服了传统经验风险最小化方法的缺点。支持向量机是是基于统计 学习理论的新一代学习算法，克服了传统方法的某些不足，自提出以来，因其独 特的优势和在众多领域出色的应用，引起了机器学习、人工智能及有关领域的普 遍关注，显现出广泛的应用前景和重要的研究价值。 3 2 统计学习方法 统计学习理论第一次强调了小样本统计学的问题，被认为是目前对小样本统 第三章统计学习方法及其在系统管理方面的应用 计估计和学习预测的最佳理论。它从理论上较系统地研究了经验风险最小化原则 成立的条件、有限样本下经验风险与期望风险的关系及如何利用这些理论找到新 的学习原则和方法等问题。 3 2 1 学习问题的表示 设给定一组样本集( 而，咒) ，( 而，蜴) ，( 西，乃) ，和一组函数集 ( x ，w ) ) ，其 中每一组样本弘与x j 之间存在一定的未知依赖关系，即遵循某一未知的联合概率 尸力。基于样本的学习过程可以描述为在函数集 厂( 五叻 中找到一个最优函 数f ( x ，w o ) ，利用这个最优函数来估计基于同样联合概率p ( x ，y ) 下的数据对，使 其误差的数学期望或风险函数： r ( w ) = l l ( y ，f ( x ，w ) ) d e ( x ，y ) 公式( 3 1 ) 最小。其中( 厂( z ，叻) 称作预测函数集，可以表示为任何函数集，w 为函数 厂( x ，奶) 的广义参数，三 ，f ( x ，w ) ) 是损失函数，它表示用f ( x ， i v ) 对l ，进行估计而造成的 偏差。 3 2 2v c 维 为了研究学习过程一致收敛的速度和推广性，统计学习理论定义了一系列有 关函数集学习性能的指标其中最重要的是v c ( v a p n i k - c h e r v o n e n k ) 维。一个指 示函数集的v c 维，是能够被函数集中的函数以所有可能的2 6 种形式分成两类向 量的最大数目h ( 也就是能够被这个函数集打散的向量的最大数目) 。若对任意 数目的样本都有函数能将它们打散，则函数集的v c 维是无穷大。有界实函数的 v c 维可以通过用一定的阈值将它转化成指示函数来定义。 v c 维是统计学习理论中的一个核心概念，它是目前未知对函数集学习性能 的最好描述指标。v c 维反映了函数集的学习能力，v c 维越大则学习机器越复 杂。因此，对于给定的学习函数集，如何用理论或实验的方法计算其v c 维是当 前统计学习理论中有待研究的个问题。 3 2 3 结构风险最小化 由于联合概率夕力未知，因此公式( 3 1 ) 表示的风险函数实际上不可求。 传统学习方法采用了经验风险最小化( e r m ，e m p i r i c a lr i s km i n i m i z a t i o n ) 准则， 希望以此来达到最小化真实风险的目的，即用样本定义经验风险： ， 尹( = 三，( _ ，w ) ) 公式( 3 2 ) f l i 第三章统计学习方法及其在系统管理方面的应用 然而，经验风险最小化与实际风险最小化等价的前提是样本数据的无穷多， 而且用经验风险最小化准则代替期望风险最小化并没有经过充分的理论论证，只 是直观上合理的想当然做法。e r m 准则不成功的一个例子是神经网络的过学习 问题。v a p n i k 证明，期望风险r ( w ) 满足一个上界，即任取w a ，且， h ，边 界以概率1 一r 成立： r ( ( 计+ 粤，里掌玛 公式( 3 3 ) i 因此，期望风险由训练样本的经验风险和置信范围组成。对于同类学习机器， 不但要求经验风险最小，还要使v c 维尽量小，从而缩小置信范围，以得到最小 的实际风险。 结构风险最小化原则( s r m ，s t r u c t u r a lr i s km i n i m i z a t i o n ) ( v a p n i k , 1 9 8 1 ) 是 在对给定数据逼近的精度和逼近函数的复杂性之间的一种折衷，可以用不同的方 法实现。支持向量机是其中最成功的一个，它是通过固定经验风险而最小化置信 范围来实现的。 3 2 4 增强学习与q 学习 统计学习理论可用于多种学习问题，其经典用法是解决分类问题，代表算法 有神经网络，贝叶斯网络，以及支持向量机；当把m 看作为未定义的值，而将期 望风险看作该集合各点之间的差别程度时，可用于解决聚类问题；当弘值不能预 先获知，而只能通过执行操作然后获得反馈来得到时，该理论可用于解决增强学 习问题。 作为我们方法的核心理论，本节对增强学习方法，一种用于序列决策的无监 督学习方法，做一个简单的介绍。在这种学习范式下，学习施事对象在每次执行 完一个操作后，将获得一个增强反馈( r e w a r d ) 。学习的目标是创建一个控制策 略以使将来的累积折算反馈( 公式( 3 _ 4 ) ) 最大化， k = ，q “ 公式( 3 - 4 ) k = o q 学习是一种广泛使用的增强学习算法。其原理是构造一个名为q 函数的估 计函数( 公式( 3 5 ) ) q ( s t a t e ，a c t i o n ) _ u t i l i t y 公式( 3 5 ) 来预测学习施事对象在某个状态上执行某个操作时所导致的最终累计折算反馈。 给定一个最优的q 函数以及当前状态s ，最优策略可以简单的表示为选取某一个 操作a 使q ( s ，a ) 在所有的可选操作中最大。通常，q 函数被表示为某种泛化形式， 如多层神经网络，并通过时序差别( 1 7 3 ) 的方法逐步学习得到 2 7 1 。给定一个状 第三章统计学习方法及其在系统管理方面的应用 态转移序列，可以通过对序列中的每相邻两个状态上迭代应用该学习方法来逐步 逼近真实的q 函数。整个过程实质上是时序差别( t d ) 方法的一种最简单形式， t d ( o ) 。一些研究工作【2 1 , 2 7 , 2 9 】表明更复杂的形式( 兄) ( 旯 o ) 能比仍( 0 ) 更有效。 3 3 统计学习方法在系统管理方面的应用 g r a y 的关于故障分析的经典文章1 17 】调查了一个商业可用的容错系统的大量 的统计分析数据。他还讨论了不同的软件容错计算技术，这些技术主要研究的是 如何避免故障的发生以及减少故障发生频率。 更新的一些工作则尝试使用统计学习的方法来实现自动化的故障诊断与性 能管理。由m a 和h e l l e r s t e i 完成的稍早一些的工作【2 3 】提出了一个高效的算法来 发现系统管理中所有的不频繁的相互依赖模型( m p a t t e r n ) ，例如，用于发现计 算机网络中的一些孤立问题。此外，一些统计工具也被开发出来用于诊断导致系 统行为异常的配置信息错误。w h i t a k e r 等人实现了一个c h r o n u s 工具【3 1 】可以自动 的寻找导致故障的状态变化。它通过建立虚拟机屏蔽系统磁盘状态来实现时间轴 上的遍历，然后使用二分查找，可以以日志大小对数增长的复杂度代价找到故障 点。w a n g 等人完成了一个相似的工作p o j ，他们提出了一个称为p e e r p r e s s u r e 的 故障诊断系统，它可以利用从样本机器集合中获取的统计信息来诊断一个故障机 器上的错误配置。还有一些工作集中于性能分析和调试，以及瓶颈探测。这方面 的工作包括m a g p i e 3 , 4 7 # 1 p i n p o i n tl l l 1 2 j ，它们能借助请求轨迹分析获得故障或性 能问题与某些组件之间可能的联系。a g u i l e r a 等人在文章【l j 中对这些工作以及相 关研究领域的努力作出了一个精彩的综述及讨论。此外，在故障诊断方面，c o h e n 等人【1 4 j 首次提出了利用增量树结构的贝叶斯网络来分析底层系统参数与上层性 能状态之间的联系。基于此工作，他们创建了信号量以用于聚类和查询，这样可 以对表面所观察到的性能问题产生更深刻的理解，并提供了一种方式来利用过去 的诊断结果【1 5 3 3 】。y u a n 等人【3 2 j 提出了一种模式分类技术用于找到故障源与系统 行为之间的联系并以此自动识别出将来可能发生的故障。和这些工作相比，我们 的方法主要集中于自动化的故障恢复而不是性能诊断。最近t e s a u r o 等【2 8 】完成了 相似的工作，他们利用一个混合的增强学习方法来实现性能管理。 1 4 第四章基于统计学习方法的容错计算 第四章基于统计学习方法的容错计算 本章主要介绍我们将统计学习方法用于容错计算的基本思路及具体实现步 骤，正如上面所介绍的，目前在系统管理领域统计学方法主要用于性能诊断及故 障原因分析，与此相对应的，我们方法的主要目标是实现自动化的故障恢复。 4 1 引言 对于计算机系统而言，保证其高可靠性一直以来都是一个极其重要的问题， 通常有如下两种实现方式：一、提高系统的可依赖性；二，提高系统的可用性。 尽管如今对于软件工程的研究和实践都获得了很大程度的提高，然而一些潜在的 程序缺陷始终存在于复杂的软件系统中。通常，想通过以识别故障源并修复程序 缺陷的方式来提高系统的可依赖性是极其困难的。实际上，随着软件系统，特别 是分布式系统以及网络系统复杂度的急剧提高，分析系统的问题并找到最终故障 源即使对于一个有经验的操作员或者分析师而言仍然是一项十分耗时耗力的工 作，而且相应