北邮信息安全专业容错计算技术课件第7章.pptVIP

1、第七章 分布容错技术,分布容错技术,概述 系统级故障诊断技术 基于检查点的卷回恢复和进程迁移技术 分布容错调度技术 分布系统的容错设计,概述,分布式系统是互相通信的自治计算机结点的集合 模块性、并行性和自治性 适合于容错技术： 所有资源都可以冗余，包括CPU、存储器、I/O接口以及数据和控制 良好的可扩展性，系统的冗余程度可以随应用要求和环境变化进行动态调整 系统资源在物理上分开，从根本上避免了由于局部故障引起系统的全面崩溃 高速可靠的通信子网、资源的分散控制，消除了在单处理机或多处理机中存在的竞争、数据流的瓶颈和控制的关键点,分布式系统的系统级故障诊断技术,基本思想 首先让系统中的处理机相互

2、测试，然后对测试结果进行分析，进而找出处理机和链路的故障 对系统进行诊断，如果没有正常节点机被错诊为故障结点机，则认为该诊断是正确的。如果诊断中能把所有故障结点机都诊断出来，则认为该诊断是完全的。一个诊断方法的分辨率是指它所执行的诊断中完全正确诊断所占的百分比,测试诊断模式,二值模型 结点机的状态和测试结果都只有两种取值 概率模型 用概率参数来描述故障结点机和无故障结点机的特性 多值模型 结点机的状态多于两种取值,测试策略,系统及故障诊断的测试策略 非自适应测试策略 一次性选取并执行全部测试 自适应测试策略 每次只选择并执行一部分测试，根据前面的结果合理地选择后面的测试,概率诊断,概率诊断不要

3、求正确完成诊断任务，只要求高概率地识别出系统中的故障结点机 优点：诊断开销低，分辨率随系统中处理机数目的增多而提高，更适用于大规模系统 测试信息的分类 利用整个系统的测试信息 利用本地测试信息和前面步骤已诊断出的故障结点机来诊断结点的状态 只利用本地信息来确定每一个节点机的状态,集中式诊断,诊断任务由系统中的一台中心结点机完成，由它负责对处理机间相互测试的结果进行收集并进一步作出诊断，以识别各结点机的状态 t个故障一步诊断算法 前提：无故障机所作的测试结果是可靠的，故障机测试结果不可靠 t个故障一步诊断的充分必要条件：在n个处理机结点中，每个处理机至少要被t个其他处理机测试，并且任意两处理机之

4、间不能相互测试 测试数大于等于nt,分布式诊断,将诊断任务分散给各结点机来独立完成，使得诊断完成后，系统中的每台无故障结点机都能正确地识别出其它所有结点机的状态，从而无故障结点机可通过忽略来自故障结点机的信息，并且不向故障结点机发送信息来实现功能上的“故障隔离”,分布式诊断,故障检测 发现结点机故障，通常利用结点机内部的自测试机制和结点机之间的互测试 信息传播 传播诊断信息，包含检测结果 协同 保证在系统的一次诊断过程中系统地所有无故障结点机所接受到的诊断信息都是相同的 诊断 利用诊断信息来判断系统各结点机的故障状态并定位故障结点机,Byzantine generals problem,198

5、2年Lamport, Shostak, Pease提出 拜占庭帝国就是515世纪的东罗马帝国，拜占庭即现在土耳其的伊斯坦布尔。当时，拜占庭军队有许多分支，驻扎在敌人城外，每一分支由各自的将军指挥。将军们只能靠通讯员进行通讯。在观察了敌人以后，忠诚的将军们必须制订一个统一的行动计划。然而，这些将军中有叛徒，他们不希望忠诚的将军们能达成一致，因而影响统一行动计划的制订与传播。问题是：将军们必须有一个算法，使所有忠诚的将军们能够达成一致，而且少数几个叛徒不能使忠诚的将军们做出错误的计划。,Byzantine generals problem,解决拜占庭将军问题的算法必须保证 所有忠诚的将军必须基于相

6、同的行动计划做出决策 忠诚的将军按算法的要求行动，而叛徒则按他们自己的意志行动。算法要保证不管叛徒怎么做，条件A都能得到保证。忠诚的将军们不但要能达成一致，而且要同意一个合理的计划。 少数叛徒不能使忠诚的将军做出错误的计划 这一条是很难做到的，因为“错误的计划”很难形式地加以定义,Byzantine generals problem,在进行混乱真实消息的传播中 两个将军中一个判国，另一个肯定打败仗； 三个将军中如果有一个判国，则判国的将军一定有办法让两个爱国的将军不能达成一致 4个将军中如果只有一个判国，在不知道谁是判国者的情况下，存在一种算法使将军们达成一致，实际上就是三个爱国的将军能够达成

7、一致，而不管判国的将军如何捣乱。即4个将军的团体能够容忍1个叛国将军。,Byzantine generals problem,当有t个判国者在捣乱而又无法找出他们的时候，存在一种算法或称做弹性协议，通过这种协议，能够保证爱国的将军达成一致。如果我们把能够容忍t个叛国者的协议叫t弹性协议， 学者已证明：不存在3t个将军下的t弹性协议而一定存在3t+1或以上将军下的t弹性协议。就是说要有3t+1个或以上将军才能保证爱国的将军能够达成一致。既要想容忍t个判国者，必须保证总的将军的个数大于3t。,现实意义,对于系统坏掉的风险：操作员可能会误操作、可能会被贿赂或背叛，系统本身就有木马程序，系统可能会被黑

8、客或病毒占领，开发的系统可能有漏洞，系统可能会有后门，这些都可以导致系统崩溃。在现实中，入侵容忍体系就是生存技术中的核心。 入侵容忍的技术在这样的假设空间中实现它的价值：个人的公开行为在一定的概率下是可预知的，系统在一定的概率下能够正确完成基本的功能。一定的概率并不是指全部，所以，可以允许有错误，因此，入侵容忍还有对纠错理论的联想：即利用纠错码可以在一个错误百出、但有信道容量的信道中准确无误地传输数据，网络系统就这样在错误中“生存”下来的,现实意义,这就是我们说的入侵容忍体系，它的生存技术有两种实现方式 一是攻击响应的入侵容忍方法，它不需要重新设计系统，可通过高效的检测系统发现异常，利用资源配

9、置系统调整系统资源，并对对错误进行修补（修补系统） 二是攻击遮蔽的入侵容忍方法，它需要重新设计整个系统，并通过冗余、容错技术，门槛密码学技术及“拜占庭”技术来实现。,系统级诊断方法的性能评价,故障种类和数目 测试数目 测试图的结构要求 诊断算法的时间复杂性 诊断信息传输量 诊断算法的分辨率 诊断延迟,分布容错技术,概述 系统级故障诊断技术 基于检查点的卷回恢复和进程迁移技术 分布容错调度技术 分布系统的容错设计,分布式系统错误恢复,排除系统错误的方法 向前错误恢复：当系统出现故障的原因能够精确确定，并能找到方法从系统中排除错误隐患，使系统继续运行时不再出现同样错误的错误恢复技术 向后错误恢复：

10、当无法诊断出系统错误的原因和性质，或无法从系统中彻底排除某种错误隐患，这是根据检查点文件将系统恢复到以前一个没有错误的状态重新运行，以期望错误不再发生的错误恢复技术,向后错误恢复技术与具体的错误类型无关，因此，向后错误恢复技术是分布式系统的通用错误恢复技术 检查点设置与卷回恢复技术作为一种向后恢复技术，通过在系统正常运行过程中设置检查点，保存系统运行时的一致性状态，并通过程序卷回到最近的检查点来实现对错误的恢复 对于不同类型的错误，可采用不同的后向恢复技术： 对于瞬时错误和间歇错误，可采用检查点设置与卷回恢复 对于永久错误，则可通过在网络存储设备保存检查点文件，从而将进程迁移到其他结点恢复运行

11、,基于检查点的卷回恢复技术,检查点容错的原理是在程序正常运行时，定期或不定期地保存程序的状态和运行数据。当错误发生时，把程序恢复到所保存的某个时刻的状态继续运行。 单进程程序检查点算法 分布式程序检查点算法,单进程程序检查点算法,用于保存和恢复单进程程序的运行状态 内存中，一个进程的运行状态由用户区和核心区两部分组成：进程用户区是指进程的代码段、数据段和堆栈段内容；进程核心区是指在进程运行时由操作系统所维护的在系统内核中的进程状态。检查点不是操作系统的一部分，不能保存和恢复进程核心区的全部信息。因此，检查点通常对用户程序有一定的限制，例如不允许使用某些系统调用等 主要解决进程状态的保存和恢复，

12、通常与机器的系统结构密切相关。在不同体系结构的机器上应进行不同的处理,分布式程序检查点算法,分布式程序包括多个进程及进程间消息。因此，分布式程序检查点需要保存进程运行状态及其进程间消息记录 异步检查点算法 同步检查点算法,异步检查点算法,程序各进程周期性地互相独立保存自己的运行状态和记录接收的消息，程序各进程间不需相互协商；在程序状态恢复过程，各进程之间需相互协调，通过卷回算法，将各自卷回到合适的检查点时刻，以使整个程序恢复到一个一致的全局状态,同步检查点算法,全局一致性检查点算法。在程序状态保存时，通过同步算法将程序各进程同步到一个全局一致时刻，再对程序各进程进行局部检查点记录。此时，程序个

13、进程检查点文件组成的集合就是一个一致的全局状态。同步算法在恢复程序状态时，只需执行各进程的检查点 算法优点是，每个程序进程只需保存最近时刻的检查点文件，空间开销较小，且程序状态恢复时没有多米诺效应 算法缺点是，在程序状态保存时，由于各进程间的同步是程序运行中止时间较长，且牺牲了分布式程序的自治性 典型算法有SNS算法和CL算法,基于检查点的进程迁移技术,进程迁移 进程迁移状态信息 检查点文件 检查点镜像,基于检查点的进程迁移技术,进程迁移：将一个进程在两台机器之间进行移动。 负载平衡：通过将进程从负载较重的系统移动到负载较轻的系统，从而使负载得到平衡，改善整体性能 改善通信性能：交互密集的多个进程可以移动到同一节点上，以减少因为他们之间的交互而带来的通信开销 分布式系统的一种错误处理机制,进程迁移未被广泛应用的原因 原系统是单独运行的，为工业标准的系统配备透明迁移能力比较困难，而直接设计具有迁移能力的新系统不现实 OS开发商并没有从商业上支持进程迁移,被传送的进程状态包括进程的地址空间、执行状态（寄存