单击此处编辑母版标题样式单击此处编辑母版副标题样式1 1* *第7章 容错性 分布式系统区别于单机系统的一个特性是它可能部分失效 当分布式系统中的一个组件发生故障时就可能产生 部分失效这个故障也许会影响到其他组件的正确操作，但同时也有可能完全不影响其他组件 而非分布式系统中的故障通常会影响到所有的组件，可能很容易就使整个应用程序崩溃l 分布式系统设计中的一个重要目标 系统可以从部分失效中自动恢复, 而且不会严重地影响整体性能特别是, 当故障发生时, 分布式系统应该在进行恢复的同时继续以可接受的方式进行操作, 也就是说它应该能容忍错误, 在发生错误时某种程度上可以继续操作7 . 1 容错性简介l基本概念 容错与被称为可靠的系统紧密相关 （1）可用性 通常指在任何给定的时刻, 系统都可以正确地操作, 可根据用户的行为来执行它的功能. 高度可用的系统在任何给定的时刻都能及时地工作 （2）可靠性 指系统可以无故障地持续运行 可靠性与可用性不同如果系统在每小时中崩溃1ms，那么它的可用性就超过99.9999，但是它还是高度不可靠的与之类似，如果一个系统从来不崩溃，但是要在每年8月中停机两个星期，那么它就是高度可靠的，但是它的可用性只有96。
（3）安全性指在系统偶然出故障的情况下能正确操作而不会造成任何灾难很多进程控制系统，必须提供高度的安全性，这样的控制系统，即使只是非常短时间瞬时故障，结果也将是灾难性的 （4）可维护性 指发生故障的系统被恢复的难易程度高度可维护的系统可能具有高度的可用性,特别是在可以探测到故障并自动恢复时 当一个系统不能兑现它的承诺时就被认为是失败的尤其是，如果一个分布式系统被设计为为它的用户提供大量的服务,当这些服务中的一个或者多个不能被完整地提供时,系统就发生故障了而错误是系统状态的一部分,它可能会导致故障发生 造成错误的原因被称为故障(fault)无疑，找到是什么引起了错误是很重要的例如，不好的传输介质可能很容易使得数据包被破坏在这种情况下要解决故障是相对容易的，但是无线网络中的传输错误可能是由恶劣的天气条件引起的要改变天气来减少或防止错误是不可能的 建立一个可靠的系统与控制故障紧密相关防止、解决和预报故障三者之间是有差别的对我们来说最重要的问题是容错(fault tolerance)，他意味着系统即使在发生故障时也能提供服务故障分类故障通常被分为暂时的、间歇的和持久的三种u暂时的故障(transient fault) 只发生一次然后就消失，即使重复操作也不会发生。
一只鸟从微波传输的电波中飞过可能会使一些网络上的数据丢失如果传输超时重发，第二次就会正常工作u间歇故障(intermittent fault) 发生，消失不见，然后再次发生，如此反复进行连接器接触不良通常会造成间歇故障间歇故障会造成情况的恶化，因为它们很难诊断，通常当解决故障的人到来时系统工作良好u持久故障(permanent fault) 是那些直到故障组件被修复之前持续存在的故障芯片燃烧、软件错误和磁盘头损坏都是持久故障的例子典型故障n崩溃性故障 服务器过早停机，但是在停机之前工作正常一个重要方面是，一旦服务器停机，就不再提供任何服务典型例子，操作系统崩溃，只有一个解决方法：重新启动n遗漏故障 服务器不能响应到来的请求 接收遗漏故障 服务器不能接收到来的消息服务器可能永远不会接受到请求可能是由于尽管在客户和服务器之间正确地建立连接，但是没有线程监听到来的请求它不会影响当服务器当前状态，因为服务器不知道有信息发送给它 发送遗漏故障 服务器不能发送消息例如，发送缓冲区溢出而服务器又没有为这种情况做好准备时就发生此类故障与接受故障相比，服务器现在的状态可能说明它已经完成了对客户的服务因此，如果响应发送失败，那么服务器可能需要为客户重新发送先前的请求而做好准备。
n 定时故障 服务器的响应在指定的实时间隔之外 例如，同步数据流那样，如果提供的数据速度过快，而在接受者又没有足够的缓冲空间来保存所有到来的数据，那么就很容易在接受端引起问题但是，更通常的情况是服务器的响应太慢，这种情况被称为发生了“性能故障” n响应故障 服务器的响应不正确分为两种： 值故障 服务器为请求提供错误的响应例如，搜索引擎系统返回了与使用的搜索项无关的web页面，就是这种情况 状态转换故障 服务器对到来的请求做出意想不到的响应例如，服务器接受一个它不能识别的信息，也没有采取措施来处理这样的信息，特别是，故障服务器可能会错误地采取一种从来没有初始化的默认行为来进行处理，此时就发生这种故障n随意性故障 （也称拜占庭故障）服务器可能在随意的时间产生随意的响应特别是，服务器可能产生它从来没有产生过的输出，但是又不能检测出错误更坏的情况是发生故障的服务器恶意地与其他服务器共同工作来产生恶意的错误结果这是最严重的故障 拜占庭故障 虽出故障，但仍继续运行，对于后续输入继续处理给出错误结果，给人一种仍在正常工作的假象没有检测出的软件错误常常属于拜占庭故障通常处理拜占庭故障比处理悄然停故障更困难。
使用冗余来掩盖故障 常用的容错方法是冗余配置，它有信息冗余、时间冗余、物理冗余三种形式 信息冗余 增加额外的信息（位）使错误信息可以得到纠正例如可以在传输的数据中添加一段Hamming码来从传输线路上的噪声中恢复数据 时间冗余 执行一个操作，如果需要就再次执行使用事务是这种方法的一个例子如果一个事务中止，那么它就可以无害的重新执行当故障是临时性和间歇性时，时间冗余特别有用 物理冗余 就是通过添加额外的设备或进程使系统作为一个整体来容忍部分组件的失效或故障例如给系统增加额外的处理机（硬件上），如果某台处理机出错，系统可以马上切换到正常的处理机上继续执行还可以在系统中添加额外的进程（软件上），如果少数进程崩溃，系统仍然可以正常工作物理冗余 物理冗余是提供容错性的著名技术在生物界（如哺乳动物有两只眼睛、两个耳朵、两个肺等）、飞行器（一般有多个发动机）和体育比赛中（有多个裁判）都用到它 物理冗余用在电子电路的容错中已经有多年了考虑如下图 (a)的电路，信号依次通过A、 B、C三个设备，如果他们中的一个发生故障，最后结果就可能是错误的ABC(a) 无冗余电路 在上图 (b)中、每个设备重复配置三份。
电路中的每一级都有3个表决电路，每个表决电路都是有三个输人和一个输出的器件如果有2个以上的输入相同，那么输出就等于他们的输入否则输出是未定义的.这种设计称为TMR(三倍模块冗余)技术 如果只有元件A1出现故障，则v1、v2和v3都有两个好的(一致的)输入，于是它们都输出正确值，这样A1的故障被屏蔽到B1、B2和B3的输入就与没有发生故障时完全相同如果这时B3和C1也出现故障，显然故障仍会被屏蔽，三个最终输出依然正确 由于表决电路也可能出现故障，所以每级使用三个表决电路假如v1故障，那么B1的输入就不正确，但是只要别的部分正常工作，B2和B3就会产生相同的输出，v4，v5和v6就会产生正确输出到第三级这样V1的故障就被屏蔽了A1A2A3B3B2B1C3C2C1V1V2V5V4V3V8V7V6V9(b) 三倍的模块冗余7.2 进程恢复设计问题 容忍失败进程的关键方法是把多个同样的进程组织到一个组中所有组都具有的关键特性是当信息发送到组本身时，组中的所有成员都接收它，通过这种方式如果组中的一个进程失败，其他的一些进程可以接管它 进程组可以是动态的可以创建新的组也可以删除旧的组在系统操作过程中，一个进程可以加入一个组也可以离开一个组。
一个进程可以同时是多个组的成员因此需要一些机制来管理组和组的成员 引入组的目的是在于允许把进程的集合作为单一的抽象概念来处理这样，一个进程就可以把消息发送给一个服务器组而不用知道有多少个进程以及它们在哪里，而这些可以在两次调用之间进行改变平等组与等级组不同组之间一个重要的区别是它们的内部结构 平等组 所有进程都是平等的没有指挥，所有决定都是共同做出的 等级组 组中存在等级关系例如，一个进程是协调者而其他进程都是工作者当外部客户或一个工作者产生一个工作请求时，请求被发送给协调者，协调者决定哪个工作者最适合，然后把请求转发给它a)平等组中的通信(b)简单等级组中的通信没有单独的失败点，如果一个进程崩溃，组只是简单的变小，但还可以继续缺点做出决定比较复杂（常常需要进行表决）协调者故障会使整个组崩溃，但只要他运行，就可以独自做决定，不需要其它进程参加协调者工作者组成员 当组通信发生时，需要一些方法来创建和删除组，以及允许进程加入和离开组 集中式组管理方法（组服务器） 所有请求都发送给它组服务器保持着所有组及其成员的完整的数据库 优点：直接、有效、容易实现 缺点：单一的失败点如果组服务器崩溃，组管理就不再存在。
分布式的组管理方法 例如，如果可靠的多播可用，一个外部进程就可以发送消息给所有的组成员表示它希望加入该组要离开一个组，理想情况是，成员只需要给所有成员发送一个再见消息问题在于当一个进程崩溃时不能像一个进程自动离开那样进行通知其他成员不得不通过注意到崩溃的成员不再进行响应来发现这一点一旦确定崩溃的成员是真正的崩溃而不是速度慢，就从组中删除它 另外一个棘手的问题是进程的离开与加入必须跟数据消息的发送同步也就是说，从进程加入一个组开始，它就必须接收发送给该组的所有消息一旦进程离开一个组，它就不能接收来自该组的任何消息，其他的成员也不能接收来自它的任何消息 最后一个问题是，如果很多机器停机使得组完全不能工作时，需要通过一些协议来重建组一些进程不得不进行初始化来重新启动故障掩盖和复制（1）我们可以复制进程并把它们组织在一个组中来用一个容错的组取代一个脆弱的进程两种方法进行复制： 基于主进程的协议 通常以主进程后备协议的形式出现，以等级方式来组织一个进程组其中一个主进程协调所有的写操作在实践中，这个主进程是固定的，尽管如果需要可以用一个后备进程来接管它实际上，如果主进程崩溃，后备进程执行一些选举算法来选择一个新的主进程。
复制写协议 与基于团体的协议相同，以主动复制的形式使用把相同进程的集合组织到一个平等组中优点是没有单一失败点，代价是分布式的协调故障掩盖和复制（2） 使用进程组进行容错中一个重要的问题是需要多少复制考虑复制写系统的情况如果系统能够承受K个组件的故障并且还能满足规范的要求，那么就被称为K容错如果这些组件（进程）是失败沉默的，那么具有K+1个组件就足够提供K容错如果K个组件停止工作，还可以用剩下的一个组件来得到响应 另一方面，如果进程发生拜占庭失败，继续错误运行并发送出错误或随机的应答，那么至少需要2K+1个进程才能获得K容错在最坏情况下，K个失败的进程可以意外地（甚至是故意地）产生同样的应答，但是剩下的K+1个进程也会产生同样的回答，这样，客户或表决电路还可以相信多数进程的回答故障系统的协议 在许多分布式系统中，进程之间存在着遵守某些协议的要求例如，选择一个协调器，决定是否提交一个事务，在工作者之间划分（分配）任务以及同步等当通信和进程（处理机）都很正常时，达到协同一致是很简单、直接的否则，会出现很多的问题在这里讨论这些问题及其解决方法(或怎样避免该问题) 分布式协议算法的一般目标是使所有的非故障进程就一些问题达成一致，并在有限的步骤内就达成一致。
依据系统的参数不同可能有不同情况包括： (1) 消息传递总是可靠吗? (2) 进程会崩溃吗？ (3) 系统是同步还是异步? 在考虑故障进程的情况之前，先看一种进程运行正常但通信线路可能丢失消息的简单情况v 这里有一个著名的问题：两军问题它描述了两个运行良好的进程之间要达成关于1位信息的协同一致，有多么的困难红色军队有5000人, 驻扎于山谷两支蓝色军队各3000人，驻扎于山谷两边的山坡。