第十章故障恢复与系统容错

基于事务型的服务比较适合于维护长期存在的共享数据，但并非适合于所有的分布式应用程序。基于事务型的服务在正常工作时将数据项存储在恢复文件中，一旦发生故障，可马上进行恢复。对服务进行恢复的通常方法是通过重启，利用恢复文件进行数据项的恢复，但这种方式对某些应用程序来说速度太慢。利用运行于不同计算机中的服务副本可大大提高恢复速度，若能够保证相互间的一致性，则可瞬时完成单一故障的恢复工作。但使用多个活跃的副本，对计算机资源又是极大的浪费。折衷方案是使用一台主服务器和若干台备份服务器，系统正常工作时由主服务器处理客户要求，当主服务器发生故障时，启动某台备份服务器，接管主服务器还没有完成的操作。当前1页，总共31页。10．2事务恢复事务的原子化特征可以用耐久性和错误原子化来描述。耐久性要求将数据项保存到永久存储器中并可随时使用，因此承认客户的提交请求意味着该事务的所有影响不仅记录在服务器的数据项中，而且记录在永久存储器中。所谓错误原子化，是指即使服务器发生故障，事务对数据项的影响也是原子化的。若某事务需具有恢复功能，则必须保证服务器的数据项具有耐久性，并且服务也应提供错误原子化功能。虽然文件服务器和数据库服务器都将数据保存在永久存储器中，但其他的服务器并不是这样的，除非要求此服务器具有恢复功能。在本章中假定：服务器运行时将所有的数据项都保存在易失性存储器中，并把所有已提交的数据记录到恢复文件或文件中。这样恢复工作就是把数据项的最新提交版本从永久存储器中恢复到服务器上。由于数据库通常需要处理大量数据，所以它们通常通过高速缓存把数据项从易失性存储器转移到磁盘永九存储器中。

当前2页，总共31页。

耐久性和错误原子化并不是相互独立的，它们可由恢复处理程序这个单一机制来统一完成。恢复处理程序的主要任务是：(1)对于已提交的事务，将其数据项保存到永久存储器中(恢复文件中)；(2)发生故障后，对服务器数据项进行恢复；(3)通过重新组织恢复文件以提高恢复工作的效率；(4)回收存储空间(在恢复文件中)。在有些情况下要求恢复处理程序处理介质故障即恢复文件本身的故障。这时可使用一种称为稳定存储器的技术进行恢复文件复制，从而不仅可以使发生介质故障的可能性大大减少，而且当系统在进行写操作发生故障时，可保证写操作是原子化的。

当前3页，总共31页。意向表：任何提供事务的服务器需要对客户事务所存取的数据项进行监控。当客户打开一个事务时，与之发生联系的第一台服务器提供一个新的事务标识符并将它返回给客户。这以后，事务中的每个客户请求(包括提交请求和异常终止请求)，都应包含此标识符。在事务的执行过程中，应将更新操作作用于该事务数据项一系列的私有临时版本上。服务器记录所有当前活跃事务的意向表，表中包含事务名以及由事务修改的数据项的值；提交事务时，服务器利用事务意向表识别该事务所影响的数据项，并用此事务所产生的每个数据项的临时版本代替原提交版本，然后将新的值写到服务器的恢复文件中。事务异常终止时，服务器通过意向表来删除所有由该事务所产生的数据项的临时版本。当前4页，总共31页。

当服务器准备提交某事务时，它必须把该事务的意向表以及意向表中的数据项保存到恢复文件中，这样即使服务器临时发生故障也可以在以后执行提交操作。当某事务所涉及的所有服务器全部同意提交该事务时，协调程序就会通知客户并发送消息到各参与服务器以执行提交操作。一旦已通知客户可进行提交，则相关服务器的恢复文件中必须包括足够多的信息，这样即使有服务器在准备提交或提交过程中发生故障，所有服务器也可提交该事务。

恢复文件表目：为了使服务器上的分布式事务具有恢复功能，恢复文件中除了保存数据项外还应保存更多的信息。这些信息包括每个事务的状态：提交、异常终止、准备提交。通过把意向表保存到恢复文件中可使恢复文件中的每个数据项与一个特定的事务相联系，恢复文件中包含的项目如表101所示。当前5页，总共31页。当前6页，总共31页。10．2．1登录登录技术是一种恢复文件的方法。在登录技术中，恢复文件代表某服务器所执行的所有事务的历史记录，其中包括数据项的值、事务状态表目以及意向表。在登录中表目的顺序反映了该服务器上事务准备提交、提交或异常终止的顺序。在服务器正常工作时，若准备提交、提交或异常终止某事务，则需调用恢复处理程序；当服务器准备提交某事务时，恢复处理程序就将意向表中的所有数据项、意向表本身以及事务当前状态(准备)添加到恢复文件中；当事务最终真正提交或异常终止时，恢复处理程序再将相应的事务状态添加到恢复文件中。恢复处理程序为每个数据项分配一个标识符，从而使得恢复文件中数据项的成功版本与服务器中的数据项保持一致。当前7页，总共31页。

图101说明了银行服务事务T和u的登录机制。在事务T和U开始执行之前重新组织登录，图中左边表示A、B、C值的快照。在本图中将A、B、C作为数据项的标识符。图中显示了事务T已提交而事务U准备提交但尚未提交的状态。当事务T准备提交时，将数据项A和B的值写入到登录中的P1和P2位置，然后写入T的准备事务状态表目及它的意向表中[(A，P1)，(B，P2)]；当提交事务时，将T的提交事务状态表目写人到P4位置；类似的，当事务U准备提交时，将数据项C和B的值写入到登录中的P5和P6位置，然后写入U的准备事务状态表目及它的意向表[(c，P5)，(B，P6)]中。每一个事务状态表目都包含一个指针指向前一个事务状态表目，从而使恢复处理程序可以反向跟踪恢复文件中的事务状态表目，事务状态表目的最后一个指针指向一个检查点(checkpoint)。当前8页，总共31页。

1．数据项恢复当服务器重启时，首先设置数据项的初始默认值，然后将控制权交给恢复处理程序。恢复处理程序负责恢复服务器上的数据项，它必须恢复所有已提交的事务对数据项的影响，并撤销所有未提交或异常终止的事务对数据项的影响。事务的晟新信息保存在登录的最后，因此恢复处理程序采用从后向前读取恢复文件的方式恢复服务器上的数据项。它利用具有提交状态的事务来恢复相应数据项，直到服务器上所有数据项都已恢复。为了恢复事务对数据项的影响，恢复处理程序从恢复文件中读取相应的意向表，而意向表中包含该事务所影响的所有数据项的值在恢复文件中的位置及其标识符。例：如果服务器在图10.1以后发生故障，则恢复处理程序将按以下方式恢复数据项：读取登录中最后一条事务状态表目，发现事务U没有提交，故应撤销其影响，则移动到登录的前一个事务状态表目P4位置；发现事务T已提交，故应恢复事务T对数据项的影响，即移动到登录的前一个事务状态表目P3位置找到事务T的意向表[(A，P1)，(B，P2)]，然后从P1和P2位置恢复数据项A、B。由于没有恢复数据项c，所以还应移动到检查点即P0点恢复C。

当前9页，总共31页。2．恢复文件的重新组织恢复处理程序负责恢复文件的重新组织以加快恢复过程并减少文件所占的存储空间。如果没有对恢复文件进行重新组织，那么恢复处理程序必须从后向前扫描恢复文件直到找出所有数据项的值。用checkpointing来表示将当前已提交的数据项值以及未完成事务的意向表和事务状态表目写入到某个新恢复文件中的过程。检查点表示由checkpointing过程所存储的信息。这样做的目的是减少恢复过程中需要处理的事务数目并回收文件空间。可在恢复完成以后任何事务开始之前立即执行checkpointing

过程。虽然恢复工作并非经常进行，但是需要在服务器正常工作时经常执行checkpointing过程。具有恢复能力的系统可通过删除旧的恢复文件来回收存储空间。在恢复过程中，若恢复处理程序移动到恢复文件中的检查点，则可立即从检查点中恢复相关的所有数据项。当前10页，总共31页。10．2．2影子版本影子版本技术是另一种组织恢复文件的方式。它通过一张地图对保存于称为版本存储文件中的数据项版本进行定位。地图将服务器数据项标识符与它们在版本存储文件中当前版本的位置联系起来，由事务写入的版本作为以前已提交版本的影子，将事务状态表目与意向表分开处理。这里首先介绍影子版本。当准备提交一个事务时，将所有由该事务所修改的数据项添加到版本存储文件中，并保持相应的提交版本不变，这些新的临时版本称为影子版本。当事务提交时，通过复制原来的地图并进入影子版本位置的方式构造新的地图。提交完成后，用新地图代替原来的地图。当服务器重新启动时，恢复处理程序读取地图并利用地图中的信息对版本存储文件中的数据项进行定位，然后就可以恢复相应的数据项。

当前11页，总共31页。这里还是用事务T和u这个例子来说明这个技术。图10.2第一列表示在事务T和u开始执行之前A、B、C的存款分别是100美元、200美元和300美元，第二列表示事务T提交后的状况。图102所示的版本存储文件中包含一个检查点,P3位置和P4位置表示事务T提交后A和B的版本情况，文件中还包含事务u准备提交时B和C的影子版本。当前12页，总共31页。

从旧地图转换到新地图必须在一个单一的原子化步骤内完成，因此需要利用稳定存储器来保存地图，这样即使在文件写操作过程中出了故障也可以保证地图的正确性。影子版本技术的恢复速度比登录技术快，这是因为在影子版本技术中，当前已提交数据项的位置记录在地图中，而登录技术需要扫描整个登录文件。系统正常工作时，登录技术的速度比影子版本技术快，这是因为登录技术仅仅需要将一系列操作添加到相同的文件中，而影子版本技术需要额外的稳定存储器写操作(涉及到两个独立的磁盘块)。对服务器而言，仅有影子版本是不够的，还必须将事务状态表目和意向表保存在事务状态文件中。意向表代表事务提交后对地图的修改。事务状态文件可组织成登录形式。当前13页，总共31页。图10.3表示提交事务T和准备提交事务U时地图及事务状态文件的相应情形.当前14页，总共31页。10．2．3恢复文件中的事务状态表及意向表表目对分布式事务而言，必须在恢复文件中增加事务状态表目及意向表，理由如下：(1)某些恢复处理程序在假定事务正常提交的情况下会提前将数据项写入恢复文件。(2)在事务使用了大量大数据项的情况下，由于要将数据项连续地写入恢复文件中，这将使服务器的设计复杂化。(3)在时间段定序并发控制中，服务器有时可以确定某事务可最终提交并确认客户，这时再将数据项写人到恢复文件中，以确保数据项的永久性，但是，该事务必须等待以前事务的提交。在这种情况下，恢复文件中相应的事务状态表目为等待提交，然后进行提交以保证恢复文件中已提交事务的时间段定序。恢复过程中允许提交任何等待提交事务，因为该事务所等待的事务要么已经提交，要么由于服务器出故障而异常终止。

当前15页，总共31页。1．对两阶段提交协议的恢复在分布式事务中，各台服务器保存自身的恢复文件。当服务器出故障时，恢复处理程序必须可对执行两阶段提交协议的事务进行有效恢复。在恢复处理程序中用到另外两个状态值done和uncertain。协调程序使用提交状态以表示表决的结果是Yes，并使用done状态表示两阶段提交协议执行完毕。工作者使用uncertain状态表示自身表决为Yes但还不知道最终结果。协调程序表目记录相应的工作者，工作者表目记录相应的协调程序，如表10.2所示。当前16页，总共31页。

在协调的第一阶段，当协调程序准备提交时(即已将准备状态表目添加到恢复文件中)，恢复处理程序将协调程序表目添加到恢复文件中。在工作者表决Yes之前，该事务必须已经准备提交(即已把准备状态表目添加到恢复文件中)。当工作者表决Yes时，恢复处理程序对工作者表目作相应记录并将uncertain状态添加到恢复文件中。当工作者表决No时，恢复处理程序将abort事务状态表目添加到恢复文件中。在协议的第二阶段，与协调程序相应的恢复处理程序根据不同情况将提交或异常终止事务状态添加到自身的恢复文件中，与工作者相应的恢复处理程序根据协调程序发送来的消息，将提交或异常终止事务状态添加到各自的恢复文件中。当协调程序收到所有工作者的确认消息后，其恢复处理程序将done事务状态添加到恢复文件中。done状态表目并不是协议的一部分，但在重新组织恢复文件时要用到它。如图10.4所示.当前17页，总共31页。

当服务器重新启动时，恢复处理程序必须恢复数据项并处理两阶段提交协议。充当协调程序的事务必须找到协调程序表目和一系列事务状态表目，充当工作者的事务必须找到工作者表目及一系列事务状态表目。无论是哪种情况，都由最当前(最接近登录末尾)的事务状态表目确定出故障时事务的状态。若恢复处理程序执行两阶段提交协议，则其行为取决于相应服务器是充当协调程序还是充当工作者，以及故障发生时服务器的状态。其具体情况如表10.3所示。当前18页，总共31页。当前19页，总共31页。2．恢复处理程序的重新组织执行checkpointing时必须保证：若某事务的状态不是done，则与之相应的协调程序表目不能从恢复文件中删除，直到所有工作都确认已完成相应事务。可对状态为done的表目进行删除，但若某事务的状态为uncertain，则相应的工作者表目必须保留。3.嵌套事务的恢复在设计嵌套事务的恢复系统时假定每个事务可以在独立的一台服务器上运行。例如，在图10.5中，事务T1、T11、T12、T2可存取相同的数据项A，但是存取过程有一定顺序。子事务的临时版本基于父事务的临时版本，当某子事务提交时，相应的父事务继承它临时提交的临时版本。当某子事务异常终止时，丢弃它的临时版本。分层中最顶层的事务最终提交时，它的版本成为新的提交版本。在最顶层事务提交或异常终止以前，临时提交的临时版本代表相应子事务，并将它写入服务器的恢复文件中。在对最顶层事务进行处理以前，必须先完成准备提交子事务的上述过程。最顶层事务的两阶段提交协议作为协凋程序决定了这些临时版本在恢复文件中的最终状态。当前20页，总共31页。10．2．4事务的故障模型Lampson(1981)提出了一种可解释为磁盘、服务器和通信故障的分布式事务故障模型。在这种模型中，若发生的故障是可预测的，则可以保证算法正确运行，否则不能保证算法可正确运行。这种模型还是可能发生故障，但可以在任何不正确的情况发生以前通过算法进行检测以发现和处理该故障。这种模型描述如下：(1)向永久存储器进行写操作时可能发生故障，例如可能没有写入或写入错误数据。另外写入错误块是灾难性错误，文件存储器也可能遭到破坏，可以通过对永久存储器进行读操作的方式来检测数据块是否遭到破坏(例如，通过校验和方法)。(2)服务器随时可能发生故障，当重新启动时，服务器的易失性存储器丢失了故障发生前的所有数据(如数据项)，因此，必须进行重新设置。当处理器发生故障时，必须使之失效以防止发送错误消息或将错误数据写入永久存储器中。处理器利用永久存储器和其他处理机的信息来恢复自身数据项的值。故障可能在任何时候发生，在对故障进行恢复时可能再次发生故障。(3)在消息到达目的地之前可能有一个随机延迟。消息可能丢失，被复制或被破坏，接收者应能对遭到破坏的消息进行检测(通过校验和方法)，伪造的消息或已遭破坏但役有检测出来的消息是灾难性错误。可利用这种故障模型设计稳定系统，该系统各部件中可对任何单一故障进行容错处理。当发生单一的写操作故障或单一的进程故障时，稳定存储器可提供原子写操作。发生故障后，稳定处理器可利用稳定存储器来恢复数据项，并可通过一个可靠的远程过程调用机制屏蔽通信故障。当前21页，总共31页。10．3容错计算机的各个部件都是由若干软件和硬件组合而成的，它们随时可能发生故障。分布式系统是由并发运行于不同计算机上的处理器组成的，它通过通信子系统进行通信转换，相对于计算机而言，通信子系统的行为相对较慢，也相对不可靠，这就导致了在设计正确的服务时相互对立的两个方面：(1)分布式系统中某个服务操作常常依靠运行于其他计算机上的其他服务操作。但是由于计算机可能出故障，通信也不可能完全可靠，这就会导致后者响应失败。另外，服务器本身很难检测出其他相关计算机是否发生故障，其他服务器是否超载等。(2)可将运行于不同计算机上的一系列服务器联合起来，服务器的联合执行相对于任何单个的服务器而言，其发生故障的概率更小。例如，可利用多台服务器复制同一服务的数据，这样即使某些服务器发生故障，仍可继续执行此服务。第(1)点表示分布式系统的服务设计者必须考虑到自己使用的其他服务器可能由于多种原因发生故障；第(2)点表示分布式系统设计者可利用多台计算机的优势屏蔽所设计的服务中可能存在的潜在错误。当前22页，总共31页。

不论何种情况，设计者都应了解服务发生故障的可能性，这意味着设计者不仅要详细说明正确运行的情况，而且要详细说明发生故障的不同方式。对服务器发生故障的方式进行讨论称为故障语义学。服务器的故障语义学知识能使设计的服务屏蔽服务故障。例如，由于IP协议所提供的数据报服务不可靠，所以必须提出TCP协议以提供可靠的流通信服务。容错系统可以检测出故障的存在，并在此基础上预测所发生的故障或进行故障屏蔽。具有容错能力的服务器所依赖的其他服务器发生故障时，本故障通过一系列的规范进行操作。容错的这种意义允许具有容错能力的服务器发生故障语义学允许的故障。服务器在屏蔽服务故障时，要么将故障整个隐藏起来，要么将之转换为允许发生的故障。在后一种情况下，通常将低层服务器的故障转换成高层服务器的故障类型。当前23页，总共31页。10．3．1故障特征为了规范说明服务器的故障语义学，可以使用一套对故障进行描述的方法。Cristian(1991)提出了一种非常有效的故障分类方法。服务器请求可以改变服务器资源状况并为用户产生一个结果。为了服务器的正确运行，Cristian分类法假定对服务器资源的影响以及客户响应必须正确。具体的分类情况如表10.4所示。当前24页，总共31页。1．同步故障Cristian分类法中提出了同步故障，它是指在特定的时间间隔内对客户无效的任何响应。同步故障可描述为响应太迟(即执行故障)或太早。例如某超载的服务器的响应可能过迟到达。设计实时操作系统必须避免同步故障，相对于其他没有实时限制的操作系统(如UNIX)而言，设计实时操作系统更为复杂并需要更多的硬件资源。2．服务器失效故障Cristian将服务器失效故障定义为遗漏故障重复发生。大多数服务器故障使得服务器停止发送消息，在客户眼里，服务器巳停止工作。客户不能对服务器故障、服务器响应过慢和服务器通信失败这三者进行确切区分。可以利用超时和重新传递请求消息的方法检测服务器故障，即与处理器进行通信的次数超过一定数目后处理器仍无应答，则认为处理器巳发生故障。这种检测服务器故障的方法是基于对服务器的可能响应时间及丢失消息的可能性进行设定，因此出错的可能性很小。

当前25页，总共31页。

失忆故障相对于重复的遗漏故障而言危害更大，因为在这种情况下服务器丢失了自身的状态(如数据项的值)。可以利用恢复机制避免服务器出故障时发生失忆故障行为。利用恢复机制避免失忆故障时，由于需提供新的服务，从而增加了开销。当前26页，总共31页。10．3．2Byzantine故障Cristian使用随机故障语义学这个词来表示服务器可能发生上述所有的故障语义学，即失效故障、同步故障、响应故障和遗漏故障。利用Byzantine故障这个词表示在最坏情况下服务器的故障语义学。Lamport等人(1982)使用临界生存系统使Byzantine问题一般化。在本系统中设定了一个环境模型，在此环境模型中，大多数计算机正常工作而其他一些有故障的计算机在尽可能恶劣的条件下工作。有故障的计算机可能对不同的接收者发送相互矛盾的消息，也可能相互冒充。这种考虑最坏情况的观点使设计的系统可以出现最坏情况，从而使得系统是超可靠的。Byzantine协议可应用于有特定响应时间限制的环境及能正确运行于有故障硬件能力的环境中。

当前27页，总共31页。

Byzantine协议算法要发送更多的消息，使用更多的活跃服务器。算法的任务是将相同的消息发送到所有服务器上，从而使得正常的服务器在特定的时间限制内产生相同的响应。它等价于原子化多点传送，即使某些有故障的服务器发生了同步故障而导致不确定的响应延迟，算法仍可正常工作。每台服务器都使用相同的方法将自己的表决与其他服务器的表决进行组合，在此过程中可能发生值故障或遗漏故障。如图10.6(a)所示，有A、B、C三台服务器(两台正常，一台不正常)，正常的服务器表决Yes，不正常的服务器向一台正常的服务器发送Yes，而向另一台正常的服务器发送No。服务器A接收到的消息为{Yes，Yes，Yes}，服务器B接收到的消息为{Yes，Yes，Nn}，由于在这两种情况下表决的主体是Yes，故正常服务器的表决结果是Yes，这表明两台正常服务器可对一台不正常服务器的故障进行容错。一般而言，若可保持接收者的消息不会遭到破坏，并可鉴定发送者身份，则2n+1台服务器可以屏蔽n台故障服务器的故障，因为正常的服务器占表决多数。在图10.6(b)所示情况下，正常服务器A表决Yes，不正常服务器C却宣布A表决No，由于服务器B从A接收到两个完全相反的表决，故B不能确定A的表决到底是什么。若不能鉴定消息发送者身份，则需要三台正常服务器来屏蔽一台服务器的故障。理论上的Byzantine模型需要三台正常服务器处理一台不正常服务器的故障行为。在实际应用中可以假定消息不会遭到破坏并且可以鉴定发送者身份，这种模型有时称作Byzantine鉴定将军模型，其故障语义学包括响应故障(值故障、状态转换故障)、遗漏故障和同步故障。当前28页，总共31页。10．4分层故障屏蔽和成组故障屏蔽Cristian提出了分层故障屏蔽和成组故障屏蔽两种故障屏蔽方法。10．4．1分层屏蔽分层故障屏蔽是指服务器依靠低层服务的情况，高层次服务器屏蔽低层次故障。某些情况下服务器故障可能完全隐藏，例如请求---应答协议通过重新发送请求消息的方式屏蔽消息传送服务中的遗漏故障。当不能屏蔽某低层故障时，可将它转换成一个高层异常。例如请求一应答协议通过向客户报告异常来屏蔽服务器失效故障。一般而言，在每个层次上，故障要么完全隐藏，要么转换为高层异常，从而在高层上试图屏蔽该故障。当最终到达用户界面层次时，大多数故障已经得到屏蔽。此时若还有故障不能屏蔽，则必须将故障报告给用户。对用户而言，