《2022年分布式系统中容错技术 .pdf》由会员分享，可在线阅读，更多相关《2022年分布式系统中容错技术 .pdf（31页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、分布计算系统第七章分布式系统中容错技术分布计算系统区别于单机系统的一个特点是在分布式系统中存在着部分失效的情况。当分布式系统某个部件出现问题的时候就发生了部分失效。虽然部分失效对分布式系统的性能有一定的影响，但同时，它应该不会影响分布式系统中整个应用程序的正确执行。相反，在单机系统中，如果系统中的一个关键部件出现问题，整个应用程序就无法继续执行。分布计算系统的一个重要设计目标是当系统中出现部分失效的时候，系统应该能自动从失效中恢复过来，并且不会对整个系统的性能产生严重的影响。在这一章里，我们要讨论分布计算系统中的容错技术。7.1 分布式系统中的故障模型容错是计算机科学中一个重要的研究领域。这一
2、节里我们首先介绍与故障处理有关的一些基本概念和分布计算系统中的故障模型。关于分布计算系统中容错的一些非常有用而详细的介绍可以参见文献 JALOTE,1994。7.1.1 基本概念分布计算系统应该是一个可信赖的系统（dependable system），容错是与可信赖系统紧密相联系的一个概念。分布计算系统的可信赖性（dependability）包括如下几个方面KOPETZ,1993：（1）可用性（availability）。可用性反映的是系统随时可被用户使用的特性。也就是说，在任何给定的时刻用户都可以使用此系统正确地执行用户给定的任务。（2）可靠性（reliability）。可靠性指的是在错误存
3、在的情况下，系统持续服务的能力。尽管可靠性和可用性容易混淆，但它们并不是同一个概念。可靠性反映的是一段时间的特性，而可用性反映的是某个时刻的特性。高可靠性系统能够持续运行一个相当长的时间而不会中断。如果一个系统，每个小时都有并且仅有1 毫秒时间失效，那么它的可用性可达99.9999%，但是它仍然是一个高度不可靠的系统。同样地，如果一个系统从来不崩溃，但是在 8 月份中，有两个星期的假期需要关机，这个系统是高可靠性的系统，但是它的可用性只有96%。（3）安全性（safety）。安全性指的是在系统出现暂时错误的情况下，不出现灾难性后果的能力。例如核电厂的控制系统和宇宙飞船的控制系统要求具有很高的安
4、全性。（4）可维护性（maintainability）。可维护性指的是系统一旦出现故障，系统易于修复的能力。高可维护性的系统意味着具有高的可用性。对于高可维护性系统来说，要求它具有自动检测错误和自动修复的能力。（5）保密性（security）。保密性要求系统资源不被非法用户访问。这方面的内容已经在第四章中作了介绍。系统失效指的是系统不能提供它所固有的服务功能。例如，分布式系统是为用户提供一系列服务的，但其中某一个服务或某些服务功能不能完全正确提供时，就说系统失效了。一般来说，从错误的时间特性来看，错误可分为暂时性的（transient）、间歇性的（intermittent）和永久性的（perm
5、anent）。暂时性的错误一旦发生之后就会消失，当相关的操作重复执行之后，错误就消失了。间歇性的错误是一会儿出现，一会儿又消失的错误，这种错误是十分令人烦恼的一种错误，因为它十分难于诊断。永久性错误是一种持续性错误，这种错误一旦出现，将会长时间存在，直到出现错误的部件被修复为止。像集成芯片被烧坏、软件缺陷、磁盘磁头损坏等都是永久性错误。名师资料总结-精品资料欢迎下载-名师精心整理-第 1 页，共 31 页 -分布式系统中容错技术7.1.2 基本的故障模型一个处于故障中的系统不能胜任它所应当提供的服务。在分布式系统中，系统不能胜任它所提供的服务意味着系统中的服务员，通信信道，或者二者都不能完全胜
6、任它们所应当具有的服务功能。在分布式系统中，错误的检测往往很困难并且很复杂。例如一个失效的服务员可能不是由这个服务员本身的故障造成的。如果一个服务员只有依赖于其他的服务员才能充分提供它所具有的服务功能，当一个服务员不能提供它所具有的某项服务或某几项服务时，错误可能是由该服务员本身造成的，也可能是由其他服务员间接引起的。分布式系统中的各部件的相互依赖性是很普遍的，例如一个硬盘错误可能会导致文件服务员不能提供正常的文件服务。如果这个文件服务员是一个分布式数据库系统的一个组成部分，那么这个数据库系统的正常工作就处于危险之中，可能会导致数据库系统中只有一部分数据是可以访问的。所以，了解分布式系统中常见
7、的错误类型是十分必要的。按照不同的标准，有不同的划分故障类型的方法，Cristian、Hadzilacos 和 Toueg 将分布式系统中故障划分为如表7.1.1 所示的几种类型CRISTIAN,1991;HADZILACOS,1993。表 7.1.1 分布式系统中故障类型故障类型说明崩溃性故障服务员停机，但是在服务员停机之前工作是正常的遗漏性故障接收性遗漏发送性遗漏服务员对输入的请求没有响应服务员未能接收到输入报文服务员未能发送出输入报文时序性故障服务员对请求的响应不是按特定的时间间隔进行的响应故障值错误状态转换错误服务员的响应是错误的服务员给出了错误的响应值服务员背离了正确的控制流程随意性
8、故障服务员在随意的时刻产生了一个随意的响应。崩溃性故障（crash failure）一般发生在服务员过早地停机。正常的情况下，一个服务员停机之前需要发送一些通告性信息，使得系统能够做一些相应的处理，例如重新启动例外一个服务员替换该服务员的服务等。如果一个服务员在没有发出任何提示信息的情况下突然停机，就会带来一系列的错误。例如在电源掉电和操作系统的死机的情况下都可以导致崩溃性故障。通常所提到的节点故障就是属于这种类型。遗漏性故障（omission failure）发生在虽然服务员是活着的，但是对某个服务请求没有响应。遗漏性故障的第一种情况是服务员收不到输入请求，例如一个服务员在处理某个请求的时候
9、，服务员没有一个线程用来侦听到达的服务请求。接收性遗漏故障不会改变服务员的当前状态，因为它没有意识到有请求报文发送给它。发送性遗漏故障发生在服务员对所收到的服务请求进行了服务，但是在发送响应报文的时候出现了故障。例如，服务员在发送响应报文时，发送缓冲区溢出，而服务员没有处理这种情况的措施。上述两种遗漏性故障属于我们通常所说的通信故障。另一种遗漏性故障与软件错误有关而与通信无关，如服务员进入死循环，或者是由于不适当的内存管理，使得服务员程序长时间被挂起。时序故障（timing failure）是一种与定时有关的故障。时序故障发生在服务员对请求的响应超过了特定的时间间隔，特别是在实时系统中，服务员
10、对服务请求的响应太迟缓。名师资料总结-精品资料欢迎下载-名师精心整理-第 2 页，共 31 页 -分布计算系统响应故障（response failure）是一类比较严重的故障，这类故障是指服务员对顾客的服务请求给出了不正确的响应。一般来说，响应故障分为两类。一类是响应值出现错误，即服务员给服务请求的回答信息是不正确的。例如，我们使用一个搜索引擎在Internet 上搜索信息，返回的结果却与我们所给出的搜索引擎无关，这是出现了值故障（value failure），即服务员给出了错误的响应值。另一类响应故障时状态转换错误（state transition failure），当服务员对所收到的服务请
11、求做出了不符合期望的反应时，就会出现状态转换错误。例如，当一个服务员接收到一个它不能识别的报文，而程序中并没有确定如何处理这样的报文，这时就容易出现状态转换错误。实际中最严重的一类错误是随意性故障（arbitrary failure），即我们所熟知的拜占庭故障（Byzantine failure）。随意性故障是一种随机性的故障，在正常情况下，服务员不会出现故障，在某些不明因素的影响下，服务员偶尔会对服务请求给出错误的结果，这种错误很难被检测出来。当一个出错的服务员和其他的服务员一起协同工作时，出错的服务员会影响其他服务员而做出错误的决定。容错是建立在冗余的基础上的，冗余是设置超过正常系统操作所
12、需要的信息、资源或时间。下面是典型的四种冗余类型：（1）硬件冗余。附加额外的处理器、I/O 设备等。（2）软件冗余。附加软件模块的额外版本等。（3）信息冗余。如使用了额外位数的错误检测代码等。（4）时间冗余。如用来完成系统功能的额外时间。有些研究者将冗余分为三类，即物理冗余、信息冗余和时间冗余JOHNSON,1995。物理冗余可以用硬件冗余的方式或软件冗余的方式来实现，因为硬件和软件在逻辑上是等同的。信息冗余的一个例子是海明码（hamming code），使用海明码技术可以纠正信息在传输中产生的错误。时间冗余的典型例子是原子操作和原子事务处理，原子操作和原子事务处理在执行中如果出现故障，相当于
13、它们没有被执行，系统的状态保持不变，所以它们可以重新执行，只是需要额外的时间。故障的基本处理方法有三种，它们是：（1）主动复制。所有的复制模块协同进行，并且它们的状态紧密同步。（2）被动复制。只有一个模块处于动态，其他模块的交互状态由这一模块的检查点定期更新。（3）半主动复制。是主动复制和被动复制的混合方法。此种方法所需的恢复开销相对较低。主动复制用到了错误屏蔽（failure masking）的概念，即隐藏出现的故障或防止故障造成错误。被动复制，又称为动态方法，通过从系统中检测错误的存在，并采取一定的措施移去错误部件来达到容错。在这一方案中，通过定期检查、自检循环和监视时钟等手段来检测错误。
14、系统层错误诊断（system-level fault diagnosis）是研究在系统中识别错误部件的方法，对于分布式系统来说，这是一个十分困难的研究领域。失效的检测可分为外部检测和内部检测两类。外部检测是指将检测节点失效的职责赋予被检测节点的外部附件。例如，用另外一个节点A 来检测节点B。如果节点A 正常，则假设通过预期的动作节点A 能够检测节点B 的任何偏差。如果A 出现错误，则其诊断结果是随机的。内部检测将节点的失效检测机制置于该节点内部，通常检测部件被假定为一个可以完全信赖的“硬核”（hardcore）。通过内部检测和外部检测的联合应用可以得到有效的错误检测方案，例如编码技术就是这样的
15、错误检测方案，它为数据总线、存储器和寄存器提供了低成本的错误检测方法。名师资料总结-精品资料欢迎下载-名师精心整理-第 3 页，共 31 页 -分布式系统中容错技术7.2 容错系统的基本构件容错系统的基本构件有三种：坚固存储器（stable storage）、故障停止处理器和原子操作。7.2.1 坚固存储器坚固存储器（stable storage）是对一个可以经受系统失效的特定存储器的逻辑抽象，也就是说，坚固存储器里的内容不会被一个失效所毁坏。系统失效之后需要恢复到以前的状态，以前的状态信息需要能够安全地存储，以便需要的时候能够恢复。这里的安全意味着恢复信息能够在发生进程崩溃、节点实效、甚至是
16、存储介质发生各种失效的情况下，也能够生存下来。坚固存储器在分布式系统的恢复中担当着重要的角色。存储器按坚固性分为三类。第一类是RAM，它在掉电和机器崩溃的情况下会丢失所存信息。第二类是磁盘存储器，它在掉电和机器崩溃的情况下，能够维持已经保存的信息，但是当磁头损坏时，会丢失所存信息。最后一类是坚固存储器，除非发生诸如洪水、地震等灾难性的事件，它所保存的数据可以在发生其他任何事故的情况下生存下来。坚固存储器可以用一对普通磁盘来实现。实际的磁盘在进行读和写操作时可能崩溃，而且，即是一个磁盘块被正确地写好之后也有一种很小的可能性使这块数据遭到破坏。这种自发的块污染在预先给定的时间T 内出现两次的概率更
17、小，可以忽略。在处理实际磁盘时，系统软件必须能指出所读的块是否有效，这可用检查和或者其他办法做到。坚固存储器中的每一个块由两个独立的磁盘块组成，分别位于不同的驱动器上，使得它们同时由于硬件故障受到损坏的机会最小。坚固存储器的算法保证至少有一块总是有效的。每一块进行写操作时，都紧跟一个读操作验证写得是否正确。两块中有一个出错或失效时，则由另一块修正或代替。上述实现坚固存储器的技术称为磁盘镜像（disk shadowing）技术。另一种实现坚固存储器的方法是使用廉价磁盘冗余阵列（redundant arrays of inexpensive disks-RAID）。RAID 是通过运用位交错技术将
18、数据分布到多个磁盘中，从而提供高I/O 性能。可以用一个或几个磁盘来检测或屏蔽错误，RAID 与传统磁盘相比有显著的优点，并可承受多个失效ALV AREZ,1997。7.2.2 故障 停止处理器当一个处理器失效，最可能的是它不进行任何不正确的操作，并且简单地停止运行。这样的处理器被称为故障停止处理器 SCHLICHTING,1983。当出现一个故障时，故障停止处理器会有以下效果：（a）处理器停止运行；（b）易失性存储器的内容丢失，而坚固存储器不受影响；（c）任何其他处理器均可以检测到故障停止处理器的失效状态。如果一个处理器不是故障停止处理器，我们可以通过一个仔细设计的程序使它变成故障停止处理器
19、 SCHNEIDER,1984。假如现有一个可靠的坚固存储器、一个可靠的存储处理器（控制存储媒介的处理器）以及k+1 个处理器，将它们转变成故障停止处理器的方法如下：k+1 个处理器中的每一个都运行同样的程序并通过存储处理器访问同一个坚固存储器。如果任何一个请求是不同的，或者任何一个请求没有在指定的期间到达，则意味着检测到一个失效事件，因而应该丢弃所有请求。因为系统表现为一个故障停止处理器，这一方法产生一个k故障 停止处理器，除非系统中 k+1 个或更多的部件失效。名师资料总结-精品资料欢迎下载-名师精心整理-第 4 页，共 31 页 -分布计算系统7.2.3 原子操作一个原子操作就是由硬件独
20、立执行的一系列动作。也就是说，每一个动作或者被完全彻底地执行，或者所有的动作根本没有执行，系统的状态保持不变。原子操作中的每一个动作都是孤立的，当执行这一动作时，在进程中感觉不到外界活动的存在，也意识不到外界状态的变化。与此相似，任何外界的进程均感觉不到一个孤立的原子操作的内在状态的变化。这就是所谓的原子操作的“全有或全无”的性质，即一个原子操作要么全部完成，要么在执行过程中出现错误的时候相当于根本没有执行。在第八章中对原子操作进行了详细描述。7.3 节点故障的处理节点故障的处理的基本方法有基于软件的和基于硬件的两种方案。由于软件和硬件在逻辑上是等同的，这里仅讨论基于软件的方案。在基于软件的方
21、案中，一系列同样的进程被复制并被分配到不同的处理器中执行。冗余的类型取决于故障的处理方法和故障的特性。对于永久性的故障，常用硬件冗余的方法来屏蔽；而对于暂时性的故障，常通过时间冗余的方法进行重试。当使用主动复制的方法时，通常使用 N-模块化冗余（NMR）。例如在3-模块化冗余（TMR）中，同样的进程被复制三遍来对输出结果做出整体表决。如果其中的一个处理器出现故障，则其余的两个拷贝在执行整体表决时就会屏蔽故障处理器的结果。然而，在分布式系统中使用主动复制的方法相对比较昂贵。在被动复制中可以使用向前式恢复和向后式恢复。在向前式恢复中，假定可以完全准确地得到系统中的故障和损失的性质，这样就有可能去掉
22、这些故障从而使得系统继续向前执行。向后式恢复适用于系统的故障无法预知和去掉的情况，在这种情况下，要定时地存储系统的状态，这样当失效导致系统处于不一致的状态时，系统可以恢复到从前没有发生故障的状态，在此状态下重新执行。7.3.1 向后式恢复尽管向前式恢复比向后式恢复简单，但它的要求十分苛刻。向后式恢复的通用性使它向分布式系统提供了一个通用的恢复机制。在向后式恢复中进程被恢复到一个先前的正确的状态。进程执行中的一些点被称为“检查点”（checkpoint），在以后发生错误的情况下，进程可以被恢复到这些点。当一个活动模块为一个进程或一个处理器时，有两种方法来保存检查点：（1）每一个检查点被组播到每一
23、个被动模块；（2）每个检查点被存储在它的本地坚固存储器中。通常检查点被存储在坚固存储器中。由于坚固存储器保证存储在其中的信息的稳定性和永久性，所以其中的信息不会丢失。当进程正确地从一个旧的检查点运行到一个新的检查点时，旧的检查点就要被新的检查点替换。当进程执行到两个检查点之间时发生错误，那么进程应该卷回到旧的检查点处重新执行。当使用新的检查点替换旧的检查点的过程中，系统也会发生失效。这可以通过检查点的原子更新过程来解决，也就是说，在检查点的更新中，要么旧的检查点被新的检查点替换，要么旧的检查点被完整地保留。Sequoia中通过使用两个检查点库来实现检查点的原子更新BERNSTEIN,1988。
24、假设系统状态最初被存储在内存中，并将被复制到坚固存储器中。有两种检查点库：在检查点更新的过程中，A 库用于存放旧的检查点，B 库用于存放新的检查点。A 库中检查点更新完毕后，进行B 库中检查点的更新。当整个检查点更新过程完成后，A 库和 B 库中的内容都被新的检查点取代。在后面的操作中，这两个库的角色可以轮换。在刷新之前和刷新之后，在库中各写入一个固定的时间戳（刷新前：A 库 Ta1，B 库 Tb1；刷新后：A 库 Ta2，B 库 Tb2）。由于这四个时间戳是顺序写入名师资料总结-精品资料欢迎下载-名师精心整理-第 5 页，共 31 页 -分布式系统中容错技术的，通过不同的时间戳就描述了一个失
25、效。表 7.3.1 表示了如何通过这四个时间戳来描述一个失效。很明显，如果这四个时间戳相等，则在形成检查点的过程中没有失效发生。如果只写下了Ta1，则失效发生在向库A 刷新的过程中；也就是说，在库A 中的新的检查点是不完整的。在这种情况下，必须将B 库中的检查点拷贝到库A 中，那么恢复的进程将重新运行到旧的检查点。当处理器出现永久性故障时，就需要对这些故障处理器进行替换。通常有一套后备的处理器，叫做“后备组”（backup group）。在被动复制中每一个活动模块都至少配备了一个后备的处理器ZHANG,1990，一个 n-后备组在所有时间里都保持有n 个后备处理器。如果该后备组发现它的处理器的
26、数量不足，它将补充新的后备处理器。在这一方案中，通过坚固存储器，每一个被动模块单位在一个活动模块崩溃后，都将从坚固存储器中获得检查点。表 7.3.1 识别在检查点更新过程中发生的失效条件失效措施Ta1=Ta2=Tb1=Tb2没有没有Ta1Ta2=Tb1=Tb2在刷新库 A 的过程中失效将库 B 复制到库 A 中Ta1=Ta2Tb1=Tb2库 A 刷新完成之后，库B 开始刷新之前失效将库 A 复制到库 B 中Ta1=Ta2=Tb1Tb2在刷新库 B 的过程中失效将库 A 复制到库 B 中当处理器出现暂时性故障时，就不需要对这些处理器进行替换。在系统恢复过程中，每个进程均需要重新记录到它最近的检查
27、点上，进程修改的数据也要重新记录到适当的状态。在这种情况下，进程仍在同一处理器下运行。向后式恢复除了使用检查点方案外，还有一个基于影像页面技术的方案。在基于影像页面技术的方案中，当进程需要修改一个页面时，系统复制该页并保留在坚固存储器中。系统中每个页面都有两个拷贝，当进程在执行的过程中，只有其中的一个拷贝被进程修改，另一个拷贝就作为影像页面。如果进程失效，则丢弃被修改的拷贝，系统根据影像页面进行恢复。如果进程成功运行，则每一份影像页面被相应的修改后的页面替换。7.3.2 向前式恢复因为在主动复制中，大多数分布式算法都是非确定性的，一个进程的所有拷贝均需要以一种可识别的方式解决其非确定性。向前式
28、恢复方案AVIZIENIS,1985；PRADHAN,1992 是半主动复制的一个特例。在这个方案中，通过对两个活动模块的不匹配比较，或通过一个3模块冗余（TMR）在三个活动模块中表决启动一个确认步骤，就可以检测半主动复制的失效位置HUANG,1998。然而，所有参与的处理器都继续执行进程，只用一部分空余来检测这些具有分歧的处理器中哪一个结果是正确的。一个向前式恢复策略是一种回卷的前瞻性运行。一个进程或任务的初始拷贝由不同的处理器来运行。这些版本的结果在检查点进行表决或比较，如果表决结果是成功的，则可以获得一个储存在坚固存储器中的正确结果。在这个结果的基础上，再执行下一项任务的拷贝。另一方面，
29、如果表决结果是失败的，就基于以前任务的每一个结果执行下一项任务的拷贝，与此同时，对以前的任务进行一次回卷执行。也就是说，在后备处理器上再运行以前的任务，目的是获得正确的结果。通过这种方式避免了在回卷运行上浪费时间。尽管在所有版本都失效（所有结果都不正确）或者重新运行以前的任务也不能获得正确结果的情况下，回卷运行是不可避免的，但由于利用了现存的正确结果而不必从头重新开始，还是节省了回卷时间。名师资料总结-精品资料欢迎下载-名师精心整理-第 6 页，共 31 页 -分布计算系统图 7.3.1(a)显示了由Pradhan 和 Vaidya 提出的向前式恢复方案PRADHAN,1992。其中 Ii，I
30、i+1和 Ii+2是检查点间隔。两个进程X 和 Y 均运行一个进程的同一个版本。在每一个检查点之前，需要对它们的结果进行比较并确认是否正确。S 代表对两个间隔Ii和 Ii+1进行验证的后备处理器。有以下四种可能的情况：（1）没有并发重试。X 和 Y 都在间隔Ii正确运行。（2）有非回卷的并发重试。这种情况发生在当单个处理器（X 或 Y）有错误但在连续的两个检查点间隔中没有错误的情况下。也就是说，在Ii中出现了错误，但在两个合法的检查点间隔Ii+1和 Ii+2中间没有错误。（3）在一次并发重试的间隔后进行回卷。该情况下重试不成功，系统卷回到Ii的开始处。这种情况对应于在Ii中当两个进程均在同一个
31、检查点间隔Ii处有错误的情况（尽管 S的 Ii确实发生在X 和 Y 的 Ii之后）。注意，在该情况下X 和 Y 均通过两个检查点间隔回卷，并且是发生在当后备处理器完成了一个合法的检查点间隔之后。如果我们用(Xi,Yi,Si)代表在间隔Ii之中 X、Y 和 S 的状态，并且用 0 代表错误，1 代表正确，d 代表没有关系（也就是说，或者错误或者正常），那我们就得到三种情况：(1,0,0)，(0,1,0)，(0,0,d)。这三种情况是在一次并发重试的间隔后进行回卷。（4）在并发重试的两次间隔之后回卷。该情况下在检查点间隔Ii+1处出现了一个额外的错误，系统卷回到间隔Ii+1的起始处。如果我们用(X
32、i,Yi,Si,Xi+1,Yi+1,Si+1)代表在间隔Ii和 Ii+1中 X、Y 和 S的状态，这种情况对应于以下描述的四种情形：(1,0,1,d,d,0)，(1,0,1,0,d,d)，(0,1,1,d,d,0)，(0,1,1,d,0,d)。在该情况下，在当后备处理器完成了两个合法的间隔之后，X 和 Y 均通过两个间隔点回卷到Ii+1。图 7.3.1 两个向前式恢复方案：（a）有两个验证间隔，（b）有一个验证间隔图 7.3.1(b)显示了由Long、Fuchs 和 Abraham 提出的向前式恢复方案LONG,1992。在此方案中，在 Ii之后的发散处理器自身在X 和 Y 的间隔 Ii+1中
33、间进行二重复制，用以确保两个处理器继续被二重复制。在S 的 Ii的验证步骤的结尾，对二重复制的拷贝进行比较，用以确保在X 和 Y 的间隔 Ii+1中间没发生错误。在Pradhan 和 Vaidya 的方案中，用第三个处理器来执行验证步骤。因为在验证步骤中，运算没有进行二重复制，所以处理器X 和 Y 可能发生分歧。所以，自身可能在间隔X Y Ii Ii+1 Ii+2 S Ii Ii+1 验证间隔1 验证间隔 2(a)X Y S Ii Ii+1 Ii 验证间隔副本副本名师资料总结-精品资料欢迎下载-名师精心整理-第 7 页，共 31 页 -分布式系统中容错技术Ii中发生错误的后备处理器必须进行第二
34、次验证（S 的 Ii+1）。这个验证是在间隔Ii之后，检验正确的处理器X 或 Y 在间隔 Ii+1的正确性。与Long、Fuchs 和 Abraham 的方案中提出的在一个验证期间使用 5 个处理器相比，Pradhan和 Vaidya 的方案中提出的在两个间隔验证期间使用3 个处理器。Hang、Wu 和 Fernandez 通过在 n 个版本中进行表决，而不是在两个版本之间进行比较，从而扩展了向前式恢复检查点的概念HUANG,1998，并讨论了可靠性优化的问题。一般说来，一个(n,m)-图代表正常运行的n-版本和进行验证的m-版本。Long、Fuchs 和 Abraham 的方案对应于一个(2
35、,1)-图。在这里，我们用Long、Fuchs 和 Abraham 的方案来说明优化的问题。当一个运算被二重复制时，我们怎么才能把处理器（新的和用过的）分配给不同的二重复制组？在本方案中，有三个新的处理器和两个用过的处理器（在以前的间隔中被用过）。在假设处理器的失效率随着时间的增加自动上升的情况下，可以证明在获得最高的系统可靠性的条件下（只有硬件故障），最佳的处理器分配方案是将所有的用过的处理器分配到单一的二重复制组中。7.4 向后恢复中的问题在向后恢复中我们需要考虑两个特殊的问题：一个是检查点的存储，另一个是检查点本身的方法问题。由于向前式恢复需要较高的代价，向后式恢复是一种更为常用的恢复技
36、术。7.4.1 检查点的存储通常检查点应该被存储在坚固存储器中。因为实现坚固存储器的方法很多，所以检查点的存储也是随着应用的不同而有所不同。Bowen 和 Pradhan考虑了两种存储和检索检查点数据的有效方法BOWEN,1993，在这种方法中，检查点数据包括检查点、活动数据以及一般数据。一个分层方案是虚拟内存的一个简单映射：第一层为最高层，是寄存器和高速缓存，第二层为内存，第三层为磁盘。这就需要较高层的存储器保存那些还没有在较低层的存储器中得到反映的更改的数据。显然，活动数据不能写到一个比存储检查点的层次更低层的存储器中。可能的分配方案有：（1）在第一层存储活动数据，在第二层和第三层存储检查
37、点。（2）在第一层和第二层存储活动数据，在第三层存储检查点。在基于高速缓存的检查点中，活动数据存储在CPU 的寄存器和高速缓存中，检查点数据存储在主存中。检查点和回卷的要求如下：检查点：（1）将局部状态（CPU 寄存器）保存在一个特定的内存区域。（2）将更改过的高速缓存中的数据写到主存中。回卷：（1）从特殊的内存区域装入CPU 寄存器。（2）将高速缓存中的所有被修改的数据设定为无效。一个重要问题是为了保持一致，以何种频率将更改过的高速缓存中的数据写入主存中。在写直达（write-through）高速缓存中，高速缓存被修改时，被修改的数据将立刻写入主存。在写回（write-back）高速缓存中，
38、只有高速缓存失效时才将被修改的数据写入主存。在写回方法中，因为在处理器失效的情况下没有必要改写内存，因此恢复时会更快。高速缓存的存在可能导致对于同一片数据存在多个拷贝，从而引起内存和高速缓存的不一致。不一致的问题可以通过使其他拷贝无效的办法，或者通过写更新（write-update）更新其他拷贝的办法来解决。名师资料总结-精品资料欢迎下载-名师精心整理-第 8 页，共 31 页 -分布计算系统上述基于高速缓存的检查点方法不能控制检查点频率，这是因为检查点频率依赖于高速缓存的大小和命中率。在双模式中，将两块叫做活动的数据和检查点的数据映射到存储层次的同一个层次上。这两个数据拷贝也叫做双胞胎页面，
39、当使用新的检查点时，它们就彼此交换角色。也就是说，活动数据变成检查点数据，而检查点数据变成活动数据。可能的分配策略有：（1）将活动数据和检查点数据存储在同一个存储层次上，比如第二层或者第三层。（2）将活动数据和检查点数据存储在几个相邻的层次上，比如从第一层到第三层或者从第二层到第三层。7.4.2 检查点方法假定每个进程都定期地在坚固存储器中对状态设置检查点，而且进程之间设置检查点的过程是独立的。一种全局状态的定义是一系列局部状态的集合，这里的局部状态就是一个进程的检查点，每个局部进程有一个局部状态。向后式错误恢复要求利用局部检查点状态构造一个一致的全局状态，但是局部检查点可能组成如下两种不一致
40、的全局状态：（1）丢失报文。进程Pi的检查点状态显示它给进程Pj发送了报文m，但是进程 Pj并没有关于该报文的纪录。（2）孤儿报文。进程Pj的检查点状态显示它收到了一个来自进程Pi的报文 m，但是进程Pi的状态显示它没有向进程Pj发送过报文m。一个报文的丢失可能是由于通信链路的故障等原因，报文m 真正丢失了，但也可能不是。例如这个报文可能正在传输过程中，这个原因是通信双方Pi和 Pj的检查点设置不合理（如图 7.4.1(a)）。出现报文丢失的另一种情况是：Pj在收到报文m 之后但是在开始下一个检查点之前崩溃了（如图7.4.1(b)）。孤儿报文可能是由失效所致。例如，Pi在发送完报文m 后失效，
41、并且被回卷到前一个检查点。在这种情况下，Pj记录了报文m 的接收，但是Pi却没有记录报文m 的发送（如图7.4.1(c)）。图 7.4.1(a)检查点设置不合理，(b)报文丢失，(c)孤儿报文如图 7.4.2 所示，为了解决孤儿报文的问题，进程Pj回卷到上一个检查点时，要清除对孤儿报文的纪录。然而，这样一来有可能出现这样一种情况：在最近的检查点和上一个检查点之间，Pj向 Pi发送了一个报文n，假定 Pi在当前检查点之前收到了报文n，现在这个报文n 成了孤儿报文。这样，Pi需要进一步回卷。这种由于一个进程的回卷导致另外一个或多个进程的回卷的效应叫做多米诺效应（domino effect）。显然，
42、有必要在建立检查点的时候或者是恢复开始的时候在进程之间进行协调。从图7.4.2 中我们可以看出，Pi和 Pj会回卷到初始检查点。一个强一致（strongly consistent）的检查点集合是由一系列的没有孤儿报文和没有丢失报文局部检查点组成。一个一致的检查点集合是由一系列没有孤儿报文的局部检查点组成。显然一个强一致的检查点集合包括一系列局部检查点，在这些检查点之间，进程之间没有报文传送。如果每个进程都在发送一个报文之后生成一个检查点，那么最近的检查点集合将永远是一致的，因为每个进程Pi Pj 当前检查点当前检查点m PiPj当前检查点当前检查点m PiPj当前检查点当前检查点m(a)(b)
43、(c)名师资料总结-精品资料欢迎下载-名师精心整理-第 9 页，共 31 页 -分布式系统中容错技术的最近检查点都对应这样一个状态：所有标记为接收的报文都已经被发送进程标记为发送了。因而，将一个进程回卷到上一个检查点不会产生孤儿报文。然而，这种情况不一定是强一致的。图 7.4.2 多米诺效应的例子在向后式恢复方案中，每个进程不断地将自己的状态记入到自己本地的坚固存储器中。当一个进程或系统失效的时候要求利用这些局部状态重新构造一个全局一致的状态。在第五章中我们已经介绍了一个分布式快照对应一个全局一致的状态，这个分布式快照可以作为一个恢复线（recovery line）用于恢复。只要发现一个最近的
44、分布式快照，就可以进行恢复。如图7.4.3，一个恢复线对应于最近的一个一致性切割线。图 7.4.3 恢复线检查点的设置可以是同步的、异步的，也可以是二者的混合。另外一个选择就是要不要给一个进程发送和接收的报文做日志。7.4.3 异步检查点异步检查点算法中程序中检查点状态的保存过程较为简单，程序中各进程周期性地相互独立地保存自己的运行状态，程序各进程之间不需要相互协商。在恢复过程中，各进程之间则需要相互协商通过复杂的回卷算法各自回卷到合适的检查点时刻以使整个程序的各个进程恢复到最近的一个一致的全局状态。由于每个进程是在没有任何协调的情况下设置自己的检查点，所以在恢复的过程中需要查找最近的一致的检
45、查点集合。查找最近的一致的检查点集合依赖于检测孤儿报文的方法。一种检测方法是比较发送的和接收的报文数量来检测孤儿报文的存在。如果接收到的报文数目和任何发送报文的进程发送的报文的数目是一致的，那么就可以认为找到了一个局部检查点的一致集合。另一种更为精确的方法是使用间隔依赖图（interval dependence graph）来进行检测。间隔依赖图表示不同进程之间间隔的依赖关系。一个间隔是接收连续两个报文之间的时间间隔。间隔依赖图可以通过和每个进程相联系的向量时钟得到。如果每个进程i 的向量时钟是LCi，一个检查点集合Pj Pi当前检查点当前检查点m n 初始检查点初始检查点Pj Pi当前检查点
46、当前检查点m n 初始检查点初始检查点恢复线不一致的切割名师资料总结-精品资料欢迎下载-名师精心整理-第 10 页，共 31 页 -分布计算系统是一致的，当且仅当不存在i 和 j 满足 LCi LCj。注意条件LCiLCj对应于进程Pi和进程 Pj之间存在一个孤儿报文。总体来说，异步检查点算法的优点是允许分布式程序的各个进程拥有最大程度的自治性，因而算法的延迟较小。缺点之一是由于每个进程需要保存若干时刻的检查点信息，空间开销较大；缺点之二是在恢复过程中可能会重复回卷，甚至出现多米诺效应，使程序一直回卷到初始状态。相关的异步检查点算法可以参见文献ELNOZAHY,1992和RICHARD,199
47、4。7.4.4 同步检查点在同步检查点算法中，各相关的进程协调它们的局部检查点的建立行为，以保证所有的最近的检查点都是一致的。由于很难使所有的进程同时设置检查点。KOO,1987 中使用了两个阶段，临时的和永久的检查点。临时检查点可以在第二阶段变为永久检查点，或者被撤销。而永久检查点是不能被撤销的。在同步检查点中，只有最近的一致的检查点集合才需要被维护和保存。一致集合中的进程的数量应该最少，没有必要将两个独立的进程放在一个集合中。只有在另外一个进程Pj接收到了一个来自进程Pi的报文并且对这个接收设置了检查点，而且Pi尚未设置发送这个报文的纪录时，Pi才有必要设置一个检查点。用这种方法，就不会产
48、生孤儿报文，这样所有的局部检查点都是一致的，但不一定是强一致的。由于使用同步检查点算法，各进程的局部检查点组成的集合是一个全局一致的状态，所以在恢复时各个进程只需要简单地从检查点处重新开始执行。同步检查点算法的优点是每个进程只需保存最近时刻的检查点信息，空间开销较小，且在恢复的时候没有多米诺效应。其缺点是，在建立检查点时，各进程间的同步使程序运行中止时间较长，且牺牲了分布式程序的自治性。同步检查点算法是目前在实际系统中较为常用的算法，其典型算法有SNS 算法和 CL 算法。Sync-and-Stop(SNS)算法中有一个进程pc 负责管理全局检查点建立过程。各进程的检查点建立过程如下：（1）p
49、c 向所有进程广播检查点开始报文Mb（第一次同步开始）；（2）任一个进程接收到报文 Mb 后停止运行，并在自己所发送的报文全部到达接收者后向pc 进程发送报文Ms1；（3）pc 接收到所有进程发送的报文Ms1 后，即意味着第一次同步结束。pc 向各进程广播报文Mchk，第二次同步开始；（4）任一个进程接收到报文Mchk 后，立即作局部检查点，检查点建立完成之后向 pc 发送报文 Ms2；（5）pc 接收到所有进程发送的报文Ms2 后，意味着第二次同步结束。pc 向所有进程广播报文Me；（6）各进程接收到报文Me 后，删除旧的检查点，仅保留新的检查点，然后继续执行。SNS 算法的恢复过程十分简单
50、，只需回卷到检查点处继续执行。很明显，经过第一次同步之后，任何进程所发送的报文都已经被对应的接收进程接收到，任何进程之间不会存在孤儿报文，满足一致性的要求。该算法的缺点是在形成检查点的过程中需要两次全局同步，程序运行中止的时间较长。但是SNS 算法易于实现，因此在许多实际系统中采用了这种算法。Chandy-Lamport(CL)算法 CHANDY,1985中机器相连的定义见图7.4.4，机器mc与 m1之间有通道直接相连，机器mc与 m1之间可直接相互发送报文，机器mc与 m1称为直接相连；机器mc与m2之间没有直接通道相连，机器mc与 m2之间相互发送的报文要通过m1转发，机器mc与 m2称