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

1、第十章第十章 故障恢复与系统容错故障恢复与系统容错101概概 述述 现在已经有若干种可提供容错能力服务的方法。一般而现在已经有若干种可提供容错能力服务的方法。一般而言，具有容错能力的服务也可能发生意外故障，但故障发生后言，具有容错能力的服务也可能发生意外故障，但故障发生后可迅速恢复并保证不丢失数据。可迅速恢复并保证不丢失数据。 大多数具有容错能力的应用程序可划分为基于事务型和大多数具有容错能力的应用程序可划分为基于事务型和基于进程控制型两类，两者的区别在于完成恢复过程所花的时基于进程控制型两类，两者的区别在于完成恢复过程所花的时间不同故障发生后，基于事务型的服务将有一个相对较长的间不同故障发生

2、后，基于事务型的服务将有一个相对较长的恢复时间。恢复时间。 基于进程控制型的程序与基于事务型的应用程序相比，基于进程控制型的程序与基于事务型的应用程序相比，其要求完全不同，这类应用程序的主要特征为：将从传感器中其要求完全不同，这类应用程序的主要特征为：将从传感器中读出的信息作为输入并传送到传动器的输出部件，输出要么直读出的信息作为输入并传送到传动器的输出部件，输出要么直接用来控制一个进程，要么用来激活警报系统以便于人们对进接用来控制一个进程，要么用来激活警报系统以便于人们对进程进行干预。例如，空中交通管理、医院病人的监控以及对反程进行干预。例如，空中交通管理、医院病人的监控以及对反应堆的控制都

3、属于这种类型的应用程序，它们通常都有非常严应堆的控制都属于这种类型的应用程序，它们通常都有非常严格的时间限制，从而要求恢复工作应在一个比较短的时间段内格的时间限制，从而要求恢复工作应在一个比较短的时间段内完成。完成。 基于事务型的服务比较适合于维护长期存在的基于事务型的服务比较适合于维护长期存在的共享数据，但并非适合于所有的分布式应用程序。共享数据，但并非适合于所有的分布式应用程序。基于事务型的服务在正常工作时将数据项存储在恢基于事务型的服务在正常工作时将数据项存储在恢复文件中，一旦发生故障，可马上进行恢复。复文件中，一旦发生故障，可马上进行恢复。 对服务进行恢复的通常方法是通过重启，利用对服

4、务进行恢复的通常方法是通过重启，利用恢复文件进行数据项的恢复，但这种方式对某些应恢复文件进行数据项的恢复，但这种方式对某些应用程序来说速度太慢。利用运行于不同计算机中的用程序来说速度太慢。利用运行于不同计算机中的服务副本可大大提高恢复速度，若能够保证相互间服务副本可大大提高恢复速度，若能够保证相互间的一致性，则可瞬时完成单一故障的恢复工作。但的一致性，则可瞬时完成单一故障的恢复工作。但使用多个活跃的副本，对计算机资源又是极大的浪使用多个活跃的副本，对计算机资源又是极大的浪费。折衷方案是使用一台主服务器和若干台备份服费。折衷方案是使用一台主服务器和若干台备份服务器，系统正常工作时由主服务器处理客

5、户要求，务器，系统正常工作时由主服务器处理客户要求，当主服务器发生故障时，启动某台备份服务器，接当主服务器发生故障时，启动某台备份服务器，接管主服务器还没有完成的操作。管主服务器还没有完成的操作。102事务恢复事务恢复 事务的原子化特征可以用耐久性和错误原子化来描述事务的原子化特征可以用耐久性和错误原子化来描述。耐久性要求将数据项保存到永久存储器中并可随时使用，。耐久性要求将数据项保存到永久存储器中并可随时使用，因此承认客户的提交请求意味着该事务的所有影响不仅记录因此承认客户的提交请求意味着该事务的所有影响不仅记录在服务器的数据项中，而且记录在永久存储器中。所谓错误在服务器的数据项中，而且记录

6、在永久存储器中。所谓错误原子化，是指即使服务器发生故障，事务对数据项的影响也原子化，是指即使服务器发生故障，事务对数据项的影响也是原子化的。若某事务需具有恢复功能，则必须保证服务器是原子化的。若某事务需具有恢复功能，则必须保证服务器的数据项具有耐久性，并且服务也应提供错误原子化功能。的数据项具有耐久性，并且服务也应提供错误原子化功能。 虽然文件服务器和数据库服务器都将数据保存在永久存虽然文件服务器和数据库服务器都将数据保存在永久存储器中，但其他的服务器并不是这样的，除非要求此服务器储器中，但其他的服务器并不是这样的，除非要求此服务器具有恢复功能。在本章中假定：服务器运行时将所有的数据具有恢复功

7、能。在本章中假定：服务器运行时将所有的数据项都保存在易失性存储器中，并把所有已提交的数据记录到项都保存在易失性存储器中，并把所有已提交的数据记录到恢复文件或文件中。这样恢复工作就是把数据项的最新提交恢复文件或文件中。这样恢复工作就是把数据项的最新提交版本从永久存储器中恢复到服务器上。由于数据库通常需要版本从永久存储器中恢复到服务器上。由于数据库通常需要处理大量数据，所以它们通常通过高速缓存把数据项从易失处理大量数据，所以它们通常通过高速缓存把数据项从易失性存储器转移到磁盘永九存储器中。性存储器转移到磁盘永九存储器中。 耐久性和错误原子化并不是相互独立的，它们可由恢耐久性和错误原子化并不是相互独

8、立的，它们可由恢复处理程序这个单一机制来统一完成。恢复处理程序的主复处理程序这个单一机制来统一完成。恢复处理程序的主要任务是：要任务是： (1)对于已提交的事务，将其数据项保存到永久存储器对于已提交的事务，将其数据项保存到永久存储器中中(恢复文件中恢复文件中)； (2)发生故障后，对服务器数据项进行恢复；发生故障后，对服务器数据项进行恢复； (3)通过重新组织恢复文件以提高恢复工作的效率；通过重新组织恢复文件以提高恢复工作的效率； (4)回收存储空间回收存储空间(在恢复文件中在恢复文件中)。 在有些情况下要求恢复处理程序处理介质故障即恢复文在有些情况下要求恢复处理程序处理介质故障即恢复文件本身

9、的故障。这时可使用一种称为稳定存储器的技术进件本身的故障。这时可使用一种称为稳定存储器的技术进行恢复文件复制，从而不仅可以使发生介质故障的可能性行恢复文件复制，从而不仅可以使发生介质故障的可能性大大减少，而且当系统在进行写操作发生故障时，可保证大大减少，而且当系统在进行写操作发生故障时，可保证写操作是原子化的。写操作是原子化的。 意向表：意向表：任何提供事务的服务器需要对客户事务所存任何提供事务的服务器需要对客户事务所存取的数据项进行监控。当客户打开一个事务时，与之发取的数据项进行监控。当客户打开一个事务时，与之发生联系的第一台服务器提供一个新的事务标识符并将它生联系的第一台服务器提供一个新的

10、事务标识符并将它返回给客户。这以后，事务中的每个客户请求返回给客户。这以后，事务中的每个客户请求(包括提交包括提交请求和异常终止请求请求和异常终止请求)，都应包含此标识符。在事务的执，都应包含此标识符。在事务的执行过程中，应将更新操作作用于该事务数据项一系列的行过程中，应将更新操作作用于该事务数据项一系列的私有临时版本上。私有临时版本上。 服务器记录所有当前活跃事务的意向表，表中包含服务器记录所有当前活跃事务的意向表，表中包含事务名以及由事务修改的数据项的值；提交事务时，服事务名以及由事务修改的数据项的值；提交事务时，服务器利用事务意向表识别该事务所影响的数据项，并用务器利用事务意向表识别该事

11、务所影响的数据项，并用此事务所产生的每个数据项的临时版本代替原提交版本，此事务所产生的每个数据项的临时版本代替原提交版本，然后将新的值写到服务器的恢复文件中。事务异常终止然后将新的值写到服务器的恢复文件中。事务异常终止时，服务器通过意向表来删除所有由该事务所产生的数时，服务器通过意向表来删除所有由该事务所产生的数据项的临时版本。据项的临时版本。 当服务器准备提交某事务时，它必须把该事务的意向表当服务器准备提交某事务时，它必须把该事务的意向表以及意向表中的数据项保存到恢复文件中，这样即使服务器临以及意向表中的数据项保存到恢复文件中，这样即使服务器临时发生故障也可以在以后执行提交操作。时发生故障也

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

13、使服务器上的分布式事务具有恢复功能，恢复文件中除了保存数据项外还应保存更多的信息。复功能，恢复文件中除了保存数据项外还应保存更多的信息。这些信息包括每个事务的状态：提交、异常终止、准备提交。这些信息包括每个事务的状态：提交、异常终止、准备提交。通过把意向表保存到恢复文件中可使恢复文件中的每个数据项通过把意向表保存到恢复文件中可使恢复文件中的每个数据项与一个特定的事务相联系，恢复文件中包含的项目如表与一个特定的事务相联系，恢复文件中包含的项目如表10 1所示。所示。1021 登录登录 登录技术是一种恢复文件的方法。在登录技术中，恢复登录技术是一种恢复文件的方法。在登录技术中，恢复文件代表某服务器

14、所执行的所有事务的历史记录，其中包括文件代表某服务器所执行的所有事务的历史记录，其中包括数据项的值、事务状态表目以及意向表。在登录中表目的顺数据项的值、事务状态表目以及意向表。在登录中表目的顺序反映了该服务器上事务准备提交、提交或异常终止的顺序。序反映了该服务器上事务准备提交、提交或异常终止的顺序。 在服务器正常工作时，若准备提交、提交或异常终止某在服务器正常工作时，若准备提交、提交或异常终止某事务，则需调用恢复处理程序；当服务器准备提交某事务时，事务，则需调用恢复处理程序；当服务器准备提交某事务时，恢复处理程序就将意向表中的所有数据项、意向表本身以及恢复处理程序就将意向表中的所有数据项、意向

15、表本身以及事务当前状态事务当前状态(准备准备)添加到恢复文件中；当事务最终真正提添加到恢复文件中；当事务最终真正提交或异常终止时，恢复处理程序再将相应的事务状态添加到交或异常终止时，恢复处理程序再将相应的事务状态添加到恢复文件中。恢复文件中。 恢复处理程序为每个数据项分配一个标识符，从而使得恢复处理程序为每个数据项分配一个标识符，从而使得恢复文件中数据项的成功版本与服务器中的数据项保持一致。恢复文件中数据项的成功版本与服务器中的数据项保持一致。 图图10 1说明了银行服务事务说明了银行服务事务T和和u的登录机制。在事务的登录机制。在事务T和和U开始执开始执行之前重新组织登录，图中左边表示行之前

16、重新组织登录，图中左边表示A、B、C值的快照。在本图中将值的快照。在本图中将A、B、C作为数据项的标识符。图中显示了事务作为数据项的标识符。图中显示了事务T已提交而事务已提交而事务U准备提交准备提交但尚未提交的状态。当事务但尚未提交的状态。当事务T准备提交时，将数据项准备提交时，将数据项A和和B的值写入到登的值写入到登录中的录中的P1和和P2位置，然后写入位置，然后写入T的准备事务状态表目及它的意向表中的准备事务状态表目及它的意向表中(A，P1)，(B，P2)；当提交事务时，将；当提交事务时，将T的提交事务状态表目写人的提交事务状态表目写人到到P4位置；类似的，当事务位置；类似的，当事务U准备

17、提交时，将数据项准备提交时，将数据项C和和B的值写入到的值写入到登录中的登录中的P5和和P6位置，然后写入位置，然后写入U的准备事务状态表目及它的意向表的准备事务状态表目及它的意向表(c，P5)，(B，P6)中。中。 每一个事务状态表目都包含一个指针指向前一个事务状态表目，从每一个事务状态表目都包含一个指针指向前一个事务状态表目，从而使恢复处理程序可以反向跟踪恢复文件中的事务状态表目，事务状态而使恢复处理程序可以反向跟踪恢复文件中的事务状态表目，事务状态表目的最后一个指针指向一个检查点表目的最后一个指针指向一个检查点(checkpoint)。 1数据项恢复数据项恢复 当服务器重启时，首先设置数

18、据项的初始默认值，然后将控制权交给当服务器重启时，首先设置数据项的初始默认值，然后将控制权交给恢复处理程序。恢复处理程序负责恢复服务器上的数据项，它必须恢复所恢复处理程序。恢复处理程序负责恢复服务器上的数据项，它必须恢复所有已提交的事务对数据项的影响，并撤销所有未提交或异常终止的事务对有已提交的事务对数据项的影响，并撤销所有未提交或异常终止的事务对数据项的影响。数据项的影响。 事务的晟新信息保存在登录的最后，因此恢复处理程序采用从后向前读事务的晟新信息保存在登录的最后，因此恢复处理程序采用从后向前读取恢复文件的方式恢复服务器上的数据项。它利用具有提交状态的事务来取恢复文件的方式恢复服务器上的数

19、据项。它利用具有提交状态的事务来恢复相应数据项，直到服务器上所有数据项都已恢复。恢复相应数据项，直到服务器上所有数据项都已恢复。 为了恢复事务对数据项的影响，恢复处理程序从恢复文件中读取相应为了恢复事务对数据项的影响，恢复处理程序从恢复文件中读取相应的意向表，而意向表中包含该事务所影响的所有数据项的值在恢复文件中的意向表，而意向表中包含该事务所影响的所有数据项的值在恢复文件中的位置及其标识符。的位置及其标识符。 例：如果服务器在图例：如果服务器在图10. 1以后发生故障，则恢复处理程序将按以下以后发生故障，则恢复处理程序将按以下方式恢复数据项：读取登录中最后一条事务状态表目，发现事务方式恢复数

20、据项：读取登录中最后一条事务状态表目，发现事务U没有提没有提交，故应撤销其影响，则移动到登录的前一个事务状态表目交，故应撤销其影响，则移动到登录的前一个事务状态表目P4位置；发现位置；发现事务事务T已提交，故应恢复事务已提交，故应恢复事务T对数据项的影响，即移动到登录的前一个事对数据项的影响，即移动到登录的前一个事务状态表目务状态表目P3位置找到事务位置找到事务T的意向表的意向表(A，P1)，(B，P2)，然后从，然后从P1和和P2位置恢复数据项位置恢复数据项A、B。由于没有恢复数据项。由于没有恢复数据项c，所以还应移动到，所以还应移动到检查点即检查点即P0点恢复点恢复C。 2恢复文件的重新组

21、织恢复文件的重新组织 恢复处理程序负责恢复文件的重新组织以加快恢复过程恢复处理程序负责恢复文件的重新组织以加快恢复过程并减少文件所占的存储空间。如果没有对恢复文件进行重新组并减少文件所占的存储空间。如果没有对恢复文件进行重新组织，那么恢复处理程序必须从后向前扫描恢复文件直到找出所织，那么恢复处理程序必须从后向前扫描恢复文件直到找出所有数据项的值。用有数据项的值。用checkpointing来表示将当前已提交的数来表示将当前已提交的数据项值以及未完成事务的意向表和事务状态表目写入到某个新据项值以及未完成事务的意向表和事务状态表目写入到某个新恢复文件中的过程。检查点表示由恢复文件中的过程。检查点表

22、示由checkpointing过程所存过程所存储的信息。这样做的目的是减少恢复过程中需要处理的事务数储的信息。这样做的目的是减少恢复过程中需要处理的事务数目并回收文件空间。目并回收文件空间。 可在恢复完成以后任何事务开始之前立即执行可在恢复完成以后任何事务开始之前立即执行checkpointing 过程。虽然恢复工作并非经常进行，但是过程。虽然恢复工作并非经常进行，但是需要在服务器正常工作时经常执行需要在服务器正常工作时经常执行checkpointing过程。过程。 具有恢复能力的系统可通过删除旧的恢复文件来回收存具有恢复能力的系统可通过删除旧的恢复文件来回收存储空间。在恢复过程中，若恢复处理

23、程序移动到恢复文件中的储空间。在恢复过程中，若恢复处理程序移动到恢复文件中的检查点，则可立即从检查点中恢复相关的所有数据项。检查点，则可立即从检查点中恢复相关的所有数据项。1022影子版本影子版本 影子版本技术是另一种组织恢复文件的方式。它通过影子版本技术是另一种组织恢复文件的方式。它通过一张地图对保存于称为版本存储文件中的数据项版本进行一张地图对保存于称为版本存储文件中的数据项版本进行定位。地图将服务器数据项标识符与它们在版本存储文件定位。地图将服务器数据项标识符与它们在版本存储文件中当前版本的位置联系起来，由事务写入的版本作为以前中当前版本的位置联系起来，由事务写入的版本作为以前已提交版本

24、的影子，将事务状态表目与意向表分开处理。已提交版本的影子，将事务状态表目与意向表分开处理。这里首先介绍影子版本。这里首先介绍影子版本。 当准备提交一个事务时，将所有由该事务所修改的数据当准备提交一个事务时，将所有由该事务所修改的数据项添加到版本存储文件中，并保持相应的提交版本不变，项添加到版本存储文件中，并保持相应的提交版本不变，这些新的临时版本称为影子版本。当事务提交时，通过复这些新的临时版本称为影子版本。当事务提交时，通过复制原来的地图并进入影子版本位置的方式构造新的地图。制原来的地图并进入影子版本位置的方式构造新的地图。提交完成后，用新地图代替原来的地图。提交完成后，用新地图代替原来的地

25、图。 当服务器重新启动时，恢复处理程序读取地图并利用地当服务器重新启动时，恢复处理程序读取地图并利用地图中的信息对版本存储文件中的数据项进行定位，然后就图中的信息对版本存储文件中的数据项进行定位，然后就可以恢复相应的数据项。可以恢复相应的数据项。 这里还是用事务这里还是用事务T和和u这个例子来说明这个技术。图这个例子来说明这个技术。图10 .2第一列表示在事务第一列表示在事务T和和u开始执行之前开始执行之前A、B、C的存款分别的存款分别是是100美元、美元、200美元和美元和300美元，第二列表示事务美元，第二列表示事务T提提交后的状况。交后的状况。图图10 2所示的版本存储文件中包含一个检查

26、点所示的版本存储文件中包含一个检查点,P3位置和位置和P4位置表示事务位置表示事务T提交后提交后A和和B的版本情况，文件中还包含的版本情况，文件中还包含事务事务u准备提交时准备提交时B和和C的影子版本。的影子版本。 从旧地图转换到新地图必须在一个单一的原子化从旧地图转换到新地图必须在一个单一的原子化步骤内完成，因此需要利用稳定存储器来保存地图，步骤内完成，因此需要利用稳定存储器来保存地图，这样即使在文件写操作过程中出了故障也可以保证这样即使在文件写操作过程中出了故障也可以保证地图的正确性。影子版本技术的恢复速度比登录技地图的正确性。影子版本技术的恢复速度比登录技术快，这是因为在影子版本技术中，

27、当前已提交数术快，这是因为在影子版本技术中，当前已提交数据项的位置记录在地图中，而登录技术需要扫描整据项的位置记录在地图中，而登录技术需要扫描整个登录文件。系统正常工作时，登录技术的速度比个登录文件。系统正常工作时，登录技术的速度比影子版本技术快，这是因为登录技术仅仅需要将一影子版本技术快，这是因为登录技术仅仅需要将一系列操作添加到相同的文件中，而影子版本技术需系列操作添加到相同的文件中，而影子版本技术需要额外的稳定存储器写操作要额外的稳定存储器写操作(涉及到两个独立的磁盘涉及到两个独立的磁盘块块)。 对服务器而言，仅有影子版本是不够的，还必对服务器而言，仅有影子版本是不够的，还必须将事务状态

28、表目和意向表保存在事务状态文件中。须将事务状态表目和意向表保存在事务状态文件中。意向表代表事务提交后对地图的修改。事务状态文意向表代表事务提交后对地图的修改。事务状态文件可组织成登录形式。件可组织成登录形式。图图10. 3表示提交事务表示提交事务T和准备提交事务和准备提交事务U时地图及时地图及事务状态文件的相应情形事务状态文件的相应情形.1023恢复文件中的事务状态表及意向表表目恢复文件中的事务状态表及意向表表目 对分布式事务而言，必须在恢复文件中增加事务状态表对分布式事务而言，必须在恢复文件中增加事务状态表目及意向表，理由如下：目及意向表，理由如下： (1)某些恢复处理程序在假定事务正常提交

29、的情况下会提某些恢复处理程序在假定事务正常提交的情况下会提前将数据项写入恢复文件。前将数据项写入恢复文件。 (2)在事务使用了大量大数据项的情况下，由于要将数据在事务使用了大量大数据项的情况下，由于要将数据项连续地写入恢复文件中，这将使服务器的设计复杂化。项连续地写入恢复文件中，这将使服务器的设计复杂化。 (3)在时间段定序并发控制中，服务器有时可以确定某事在时间段定序并发控制中，服务器有时可以确定某事务可最终提交并确认客户，这时再将数据项写人到恢复文件务可最终提交并确认客户，这时再将数据项写人到恢复文件中，以确保数据项的永久性，但是，该事务必须等待以前事中，以确保数据项的永久性，但是，该事务

30、必须等待以前事务的提交。在这种情况下，恢复文件中相应的事务状态表目务的提交。在这种情况下，恢复文件中相应的事务状态表目为等待提交，然后进行提交以保证恢复文件中已提交事务的为等待提交，然后进行提交以保证恢复文件中已提交事务的时间段定序。恢复过程中允许提交任何等待提交事务，因为时间段定序。恢复过程中允许提交任何等待提交事务，因为该事务所等待的事务要么已经提交，要么由于服务器出故障该事务所等待的事务要么已经提交，要么由于服务器出故障而异常终止。而异常终止。 1对两阶段提交协议的恢复对两阶段提交协议的恢复 在分布式事务中，各台服务器保存自身的恢复文件。当在分布式事务中，各台服务器保存自身的恢复文件。当

31、服务器出故障时，恢复处理程序必须可对执行两阶段提交协服务器出故障时，恢复处理程序必须可对执行两阶段提交协议的事务进行有效恢复。在恢复处理程序中用到另外两个状议的事务进行有效恢复。在恢复处理程序中用到另外两个状态值态值done和和uncertain。协调程序使用提交状态以表示表。协调程序使用提交状态以表示表决的结果是决的结果是Yes，并使用，并使用done状态表示两阶段提交协议执行状态表示两阶段提交协议执行完毕。工作者使用完毕。工作者使用uncertain状态表示自身表决为状态表示自身表决为Yes但还但还不知道最终结果。协调程序表目记录相应的工作者，工作者不知道最终结果。协调程序表目记录相应的工

32、作者，工作者表目记录相应的协调程序，如表表目记录相应的协调程序，如表10 .2所示。所示。 在协调的第一阶段，当协调程序准备提交时在协调的第一阶段，当协调程序准备提交时(即已将准备即已将准备状态表目添加到恢复文件中状态表目添加到恢复文件中)，恢复处理程序将协调程序表目，恢复处理程序将协调程序表目添加到恢复文件中。在工作者表决添加到恢复文件中。在工作者表决Yes之前，该事务必须已之前，该事务必须已经准备提交经准备提交(即已把准备状态表目添加到恢复文件中即已把准备状态表目添加到恢复文件中)。当工。当工作者表决作者表决Yes时，恢复处理程序对工作者表目作相应记录并时，恢复处理程序对工作者表目作相应记

33、录并将将uncertain状态添加到恢复文件中。当工作者表决状态添加到恢复文件中。当工作者表决No时，时，恢复处理程序将恢复处理程序将abort事务状态表目添加到恢复文件中。事务状态表目添加到恢复文件中。 在协议的第二阶段，与协调程序相应的恢复处理程序根在协议的第二阶段，与协调程序相应的恢复处理程序根据不同情况将提交或异常终止事务状态添加到自身的恢复文据不同情况将提交或异常终止事务状态添加到自身的恢复文件中，与工作者相应的恢复处理程序根据协调程序发送来的件中，与工作者相应的恢复处理程序根据协调程序发送来的消息，将提交或异常终止事务状态添加到各自的恢复文件中。消息，将提交或异常终止事务状态添加到

34、各自的恢复文件中。当协调程序收到所有工作者的确认消息后，其恢复处理程序当协调程序收到所有工作者的确认消息后，其恢复处理程序将将done事务状态添加到恢复文件中。事务状态添加到恢复文件中。done状态表目并不是状态表目并不是协议的一部分，但在重新组织恢复文件时要用到它。如图协议的一部分，但在重新组织恢复文件时要用到它。如图10 .4所示所示. 当服务器重新启动时，恢复处理程序必须恢复数据项并当服务器重新启动时，恢复处理程序必须恢复数据项并处理两阶段提交协议。充当协调程序的事务必须找到协调程处理两阶段提交协议。充当协调程序的事务必须找到协调程序表目和一系列事务状态表目，充当工作者的事务必须找到序表

35、目和一系列事务状态表目，充当工作者的事务必须找到工作者表目及一系列事务状态表目。无论是哪种情况，都由工作者表目及一系列事务状态表目。无论是哪种情况，都由最当前最当前(最接近登录末尾最接近登录末尾)的事务状态表目确定出故障时事务的事务状态表目确定出故障时事务的状态。的状态。 若恢复处理程序执行两阶段提交协议，则其行为取决于若恢复处理程序执行两阶段提交协议，则其行为取决于相应服务器是充当协调程序还是充当工作者，以及故障发生相应服务器是充当协调程序还是充当工作者，以及故障发生时服务器的状态。其具体情况如表时服务器的状态。其具体情况如表10. 3所示。所示。2恢复处理程序的重新组织恢复处理程序的重新组

36、织 执行执行checkpointing时必须保证：若某事务的状态不是时必须保证：若某事务的状态不是done，则，则与之相应的协调程序表目不能从恢复文件中删除，直到所有工作都确认与之相应的协调程序表目不能从恢复文件中删除，直到所有工作都确认已完成相应事务。可对状态为已完成相应事务。可对状态为done的表目进行删除，但若某事务的状态的表目进行删除，但若某事务的状态为为uncertain，则相应的工作者表目必须保留。，则相应的工作者表目必须保留。3.嵌套事务的恢复嵌套事务的恢复 在设计嵌套事务的恢复系统时假定每个事务可以在独立的一台服务在设计嵌套事务的恢复系统时假定每个事务可以在独立的一台服务器上运

37、行。器上运行。 例如，在图例如，在图10 .5中，事务中，事务T1、T11、T12、T2可存取相同的数据可存取相同的数据项项A，但是存取过程有一定顺序。子事务的临时版本基于父事务的临时版，但是存取过程有一定顺序。子事务的临时版本基于父事务的临时版本，当某子事务提交时，相应的父事务继承它临时提交的临时版本。当本，当某子事务提交时，相应的父事务继承它临时提交的临时版本。当某子事务异常终止时，丢弃它的临时版本。分层中最顶层的事务最终提某子事务异常终止时，丢弃它的临时版本。分层中最顶层的事务最终提交时，它的版本成为新的提交版本。交时，它的版本成为新的提交版本。 在最顶层事务提交或异常终止以前，临时提交

38、的临时版本代表相应在最顶层事务提交或异常终止以前，临时提交的临时版本代表相应子事务，并将它写入服务器的恢复文件中。在对最顶层事务进行处理以子事务，并将它写入服务器的恢复文件中。在对最顶层事务进行处理以前，必须先完成准备提交子事务的上述过程。最顶层事务的两阶段提交前，必须先完成准备提交子事务的上述过程。最顶层事务的两阶段提交协议作为协凋程序决定了这些临时版本在恢复文件中的最终状态。协议作为协凋程序决定了这些临时版本在恢复文件中的最终状态。1024 事务的故障模型事务的故障模型 Lampson(1981)提出了一种可解释为磁盘、服务器和通信故障的分提出了一种可解释为磁盘、服务器和通信故障的分布式事

39、务故障模型。在这种模型中，若发生的故障是可预测的，则可以保证布式事务故障模型。在这种模型中，若发生的故障是可预测的，则可以保证算法正确运行，否则不能保证算法可正确运行。这种模型还是可能发生故障，算法正确运行，否则不能保证算法可正确运行。这种模型还是可能发生故障，但可以在任何不正确的情况发生以前通过算法进行检测以发现和处理该故障。但可以在任何不正确的情况发生以前通过算法进行检测以发现和处理该故障。这种模型描述如下：这种模型描述如下： (1)向永久存储器进行写操作时可能发生故障，例如可能没有写入或写入向永久存储器进行写操作时可能发生故障，例如可能没有写入或写入错误数据。另外写入错误块是灾难性错误，

40、文件存储器也可能遭到破坏，可错误数据。另外写入错误块是灾难性错误，文件存储器也可能遭到破坏，可以通过对永久存储器进行读操作的方式来检测数据块是否遭到破坏以通过对永久存储器进行读操作的方式来检测数据块是否遭到破坏(例如，通例如，通过校验和方法过校验和方法)。 (2)服务器随时可能发生故障，当重新启动时，服务器的易失性存储器丢服务器随时可能发生故障，当重新启动时，服务器的易失性存储器丢失了故障发生前的所有数据失了故障发生前的所有数据(如数据项如数据项)，因此，必须进行重新设置。当处理，因此，必须进行重新设置。当处理器发生故障时，必须使之失效以防止发送错误消息或将错误数据写入永久存器发生故障时，必须

41、使之失效以防止发送错误消息或将错误数据写入永久存储器中。处理器利用永久存储器和其他处理机的信息来恢复自身数据项的值。储器中。处理器利用永久存储器和其他处理机的信息来恢复自身数据项的值。故障可能在任何时候发生，在对故障进行恢复时可能再次发生故障。故障可能在任何时候发生，在对故障进行恢复时可能再次发生故障。 (3)在消息到达目的地之前可能有一个随机延迟。消息可能丢失，被复制在消息到达目的地之前可能有一个随机延迟。消息可能丢失，被复制或被破坏，接收者应能对遭到破坏的消息进行检测或被破坏，接收者应能对遭到破坏的消息进行检测(通过校验和方法通过校验和方法)，伪造，伪造的消息或已遭破坏但役有检测出来的消息

42、是灾难性错误。的消息或已遭破坏但役有检测出来的消息是灾难性错误。 可利用这种故障模型设计稳定系统，该系统各部件中可对任何单一故障可利用这种故障模型设计稳定系统，该系统各部件中可对任何单一故障进行容错处理。当发生单一的写操作故障或单一的进程故障时，稳定存储器进行容错处理。当发生单一的写操作故障或单一的进程故障时，稳定存储器可提供原子写操作。发生故障后，稳定处理器可利用稳定存储器来恢复数据可提供原子写操作。发生故障后，稳定处理器可利用稳定存储器来恢复数据项，并可通过一个可靠的远程过程调用机制屏蔽通信故障。项，并可通过一个可靠的远程过程调用机制屏蔽通信故障。103容容 错错 计算机的各个部件都是由若

43、干软件和硬件组合而成的，它计算机的各个部件都是由若干软件和硬件组合而成的，它们随时可能发生故障。分布式系统是由并发运行于不同计算机上们随时可能发生故障。分布式系统是由并发运行于不同计算机上的处理器组成的，它通过通信子系统进行通信转换，相对于计算的处理器组成的，它通过通信子系统进行通信转换，相对于计算机而言，通信子系统的行为相对较慢，也相对不可靠，这就导致机而言，通信子系统的行为相对较慢，也相对不可靠，这就导致了在设计正确的服务时相互对立的两个方面：了在设计正确的服务时相互对立的两个方面： (1)分布式系统中某个服务操作常常依靠运行于其他计算机分布式系统中某个服务操作常常依靠运行于其他计算机上的

44、其他服务操作。但是由于计算机可能出故障，通信也不可能上的其他服务操作。但是由于计算机可能出故障，通信也不可能完全可靠，这就会导致后者响应失败。另外，服务器本身很难检完全可靠，这就会导致后者响应失败。另外，服务器本身很难检测出其他相关计算机是否发生故障，其他服务器是否超载等。测出其他相关计算机是否发生故障，其他服务器是否超载等。 (2)可将运行于不同计算机上的一系列服务器联合起来，服可将运行于不同计算机上的一系列服务器联合起来，服务器的联合执行相对于任何单个的服务器而言，其发生故障的概务器的联合执行相对于任何单个的服务器而言，其发生故障的概率更小。例如，可利用多台服务器复制同一服务的数据，这样即

45、率更小。例如，可利用多台服务器复制同一服务的数据，这样即使某些服务器发生故障，仍可继续执行此服务。使某些服务器发生故障，仍可继续执行此服务。 第第(1)点表示分布式系统的服务设计者必须考虑到自己使用点表示分布式系统的服务设计者必须考虑到自己使用的其他服务器可能由于多种原因发生故障；第的其他服务器可能由于多种原因发生故障；第(2)点表示分布式点表示分布式系统设计者可利用多台计算机的优势屏蔽所设计的服务中可能存系统设计者可利用多台计算机的优势屏蔽所设计的服务中可能存在的潜在错误。在的潜在错误。 不论何种情况，设计者都应了解服务发生故障的可能性，不论何种情况，设计者都应了解服务发生故障的可能性，这意

46、味着设计者不仅要详细说明正确运行的情况，而且要详这意味着设计者不仅要详细说明正确运行的情况，而且要详细说明发生故障的不同方式。对服务器发生故障的方式进行细说明发生故障的不同方式。对服务器发生故障的方式进行讨论称为故障语义学。服务器的故障语义学知识能使设计的讨论称为故障语义学。服务器的故障语义学知识能使设计的服务屏蔽服务故障。例如，由于服务屏蔽服务故障。例如，由于IP协议所提供的数据报服务协议所提供的数据报服务不可靠，所以必须提出不可靠，所以必须提出TCP协议以提供可靠的流通信服务。协议以提供可靠的流通信服务。 容错系统可以检测出故障的存在，并在此基础上预测所发容错系统可以检测出故障的存在，并在

47、此基础上预测所发生的故障或进行故障屏蔽。具有容错能力的服务器所依赖的生的故障或进行故障屏蔽。具有容错能力的服务器所依赖的其他服务器发生故障时，本故障通过一系列的规范进行操作。其他服务器发生故障时，本故障通过一系列的规范进行操作。容错的这种意义允许具有容错能力的服务器发生故障语义学容错的这种意义允许具有容错能力的服务器发生故障语义学允许的故障。允许的故障。 服务器在屏蔽服务故障时，要么将故障整个隐藏起来，要服务器在屏蔽服务故障时，要么将故障整个隐藏起来，要么将之转换为允许发生的故障。在后一种情况下，通常将低么将之转换为允许发生的故障。在后一种情况下，通常将低层服务器的故障转换成高层服务器的故障类

48、型。层服务器的故障转换成高层服务器的故障类型。1031故障特征故障特征 为了规范说明服务器的故障语义学，可以使用一套对故障为了规范说明服务器的故障语义学，可以使用一套对故障进行描述的方法。进行描述的方法。Cristian(1991)提出了一种非常有效的提出了一种非常有效的故障分类方法。服务器请求可以改变服务器资源状况并为用户故障分类方法。服务器请求可以改变服务器资源状况并为用户产生一个结果。为了服务器的正确运行，产生一个结果。为了服务器的正确运行，Cristian分类法假分类法假定对服务器资源的影响以及客户响应必须正确。具体的分类情定对服务器资源的影响以及客户响应必须正确。具体的分类情况如表况

49、如表10 .4所示。所示。1同步故障同步故障 Cristian 分类法中提出了同步故障，它是指在特定的时间间分类法中提出了同步故障，它是指在特定的时间间隔内对客户无效的任何响应。同步故障可描述为响应太迟隔内对客户无效的任何响应。同步故障可描述为响应太迟(即执即执行故障行故障)或太早。例如某超载的服务器的响应可能过迟到达。设或太早。例如某超载的服务器的响应可能过迟到达。设计实时操作系统必须避免同步故障，相对于其他没有实时限制的计实时操作系统必须避免同步故障，相对于其他没有实时限制的操作系统操作系统(如如UNIX)而言，设计实时操作系统更为复杂并需要而言，设计实时操作系统更为复杂并需要更多的硬件资

50、源。更多的硬件资源。2服务器失效故障服务器失效故障 Cristian将服务器失效故障定义为遗漏故障重复发生。大多数将服务器失效故障定义为遗漏故障重复发生。大多数服务器故障使得服务器停止发送消息，在客户眼里，服务器巳停服务器故障使得服务器停止发送消息，在客户眼里，服务器巳停止工作。客户不能对服务器故障、服务器响应过慢和服务器通信止工作。客户不能对服务器故障、服务器响应过慢和服务器通信失败这三者进行确切区分。可以利用超时和重新传递请求消息的失败这三者进行确切区分。可以利用超时和重新传递请求消息的方法检测服务器故障，即与处理器进行通信的次数超过一定数目方法检测服务器故障，即与处理器进行通信的次数超过

51、一定数目后处理器仍无应答，则认为处理器巳发生故障。这种检测服务器后处理器仍无应答，则认为处理器巳发生故障。这种检测服务器故障的方法是基于对服务器的可能响应时间及丢失消息的可能性故障的方法是基于对服务器的可能响应时间及丢失消息的可能性进行设定，因此出错的可能性很小。进行设定，因此出错的可能性很小。 失忆故障相对于重复的遗漏故障而言危害更大，因为在这失忆故障相对于重复的遗漏故障而言危害更大，因为在这种情况下服务器丢失了自身的状态种情况下服务器丢失了自身的状态(如数据项的值如数据项的值)。可以利。可以利用恢复机制避免服务器出故障时发生失忆故障行为。利用恢用恢复机制避免服务器出故障时发生失忆故障行为。

52、利用恢复机制避免失忆故障时，由于需提供新的服务，从而增加了复机制避免失忆故障时，由于需提供新的服务，从而增加了开销。开销。1032 Byzantine故障故障 Cristian使用随机故障语义学这个词来表示服务器可能使用随机故障语义学这个词来表示服务器可能发生上述所有的故障语义学，即失效故障、同步故障、响应发生上述所有的故障语义学，即失效故障、同步故障、响应故障和遗漏故障。利用故障和遗漏故障。利用Byzantine故障这个词表示在最坏情故障这个词表示在最坏情况下服务器的故障语义学。况下服务器的故障语义学。 Lamport等人等人(1982)使用临使用临界生存系统使界生存系统使Byzantine

53、问题一般化。在本系统中设定了一问题一般化。在本系统中设定了一个环境模型，在此环境模型中，大多数计算机正常工作而其个环境模型，在此环境模型中，大多数计算机正常工作而其他一些有故障的计算机在尽可能恶劣的条件下工作。有故障他一些有故障的计算机在尽可能恶劣的条件下工作。有故障的计算机可能对不同的接收者发送相互矛盾的消息，也可能的计算机可能对不同的接收者发送相互矛盾的消息，也可能相互冒充。这种考虑最坏情况的观点使设计的系统可以出现相互冒充。这种考虑最坏情况的观点使设计的系统可以出现最坏情况，从而使得系统是超可靠的。最坏情况，从而使得系统是超可靠的。 Byzantine协议可协议可应用于有特定响应时间限制

54、的环境及能正确运行于有故障硬应用于有特定响应时间限制的环境及能正确运行于有故障硬件能力的环境中。件能力的环境中。 Byzantine协议算法要发送更多的消息，使用更多的活跃服务器。算法的协议算法要发送更多的消息，使用更多的活跃服务器。算法的任务是将相同的消息发送到所有服务器上，从而使得正常的服务器在特定的时间任务是将相同的消息发送到所有服务器上，从而使得正常的服务器在特定的时间限制内产生相同的响应。它等价于原子化多点传送，即使某些有故障的服务器发限制内产生相同的响应。它等价于原子化多点传送，即使某些有故障的服务器发生了同步故障而导致不确定的响应延迟，算法仍可正常工作。每台服务器都使用生了同步故

55、障而导致不确定的响应延迟，算法仍可正常工作。每台服务器都使用相同的方法将自己的表决与其他服务器的表决进行组合，在此过程中可能发生值相同的方法将自己的表决与其他服务器的表决进行组合，在此过程中可能发生值故障或遗漏故障。如图故障或遗漏故障。如图10 .6(a)所示，有所示，有A、B、C三台服务器三台服务器(两台正常，一两台正常，一台不正常台不正常)，正常的服务器表决，正常的服务器表决Yes，不正常的服务器向一台正常的服务器发送，不正常的服务器向一台正常的服务器发送Yes，而向另一台正常的服务器发送，而向另一台正常的服务器发送No。服务器。服务器A接收到的消息为接收到的消息为 Yes，Yes，Yes

56、，服务器，服务器B接收到的消息为接收到的消息为Yes，Yes，Nn，由于在这两种情，由于在这两种情况下表决的主体是况下表决的主体是Yes，故正常服务器的表决结果是，故正常服务器的表决结果是Yes，这表明两台正常服务，这表明两台正常服务器可对一台不正常服务器的故障进行容错。一般而言，若可保持接收者的消息不器可对一台不正常服务器的故障进行容错。一般而言，若可保持接收者的消息不会遭到破坏，并可鉴定发送者身份，则会遭到破坏，并可鉴定发送者身份，则2n+1台服务器可以屏蔽台服务器可以屏蔽n台故障服务器台故障服务器的故障，因为正常的服务器占表决多数。的故障，因为正常的服务器占表决多数。 在图在图10. 6

57、(b)所示情况下，正常服务器所示情况下，正常服务器A表决表决Yes，不正常服务器，不正常服务器C却宣却宣布布A表决表决No，由于服务器，由于服务器B从从A接收到两个完全相反的表决，故接收到两个完全相反的表决，故B不能确定不能确定A的的表决到底是什么。若不能鉴定消息发送者身份，则需要三台正常服务器来屏蔽一表决到底是什么。若不能鉴定消息发送者身份，则需要三台正常服务器来屏蔽一台服务器的故障。台服务器的故障。 理论上的理论上的Byzantine模型需要三台正常服务器处理一台不正常服务器的故障模型需要三台正常服务器处理一台不正常服务器的故障行为。在实际应用中可以假定消息不会遭到破坏并且可以鉴定发送者身

58、份，这种行为。在实际应用中可以假定消息不会遭到破坏并且可以鉴定发送者身份，这种模型有时称作模型有时称作Byzantine鉴定将军模型，其故障语义学包括响应故障鉴定将军模型，其故障语义学包括响应故障(值故障、值故障、状态转换故障状态转换故障)、遗漏故障和同步故障。、遗漏故障和同步故障。104 分层故障屏蔽和成组故障屏蔽分层故障屏蔽和成组故障屏蔽 Cristian提出了分层故障屏蔽和成组故障屏蔽两种故障屏蔽方法。提出了分层故障屏蔽和成组故障屏蔽两种故障屏蔽方法。1041分层屏蔽分层屏蔽 分层故障屏蔽是指服务器依靠低层服务的情况，高层次服务器屏蔽低层次分层故障屏蔽是指服务器依靠低层服务的情况，高层次

59、服务器屏蔽低层次故障。某些情况下服务器故障可能完全隐藏，例如请求故障。某些情况下服务器故障可能完全隐藏，例如请求-应答协议通过重新应答协议通过重新发送请求消息的方式屏蔽消息传送服务中的遗漏故障。当不能屏蔽某低层故障发送请求消息的方式屏蔽消息传送服务中的遗漏故障。当不能屏蔽某低层故障时，可将它转换成一个高层异常。例如请求一应答协议通过向客户报告异常来时，可将它转换成一个高层异常。例如请求一应答协议通过向客户报告异常来屏蔽服务器失效故障。一般而言，在每个层次上，故障要么完全隐藏，要么转屏蔽服务器失效故障。一般而言，在每个层次上，故障要么完全隐藏，要么转换为高层异常，从而在高层上试图屏蔽该故障。当最

60、终到达用户界面层次时，换为高层异常，从而在高层上试图屏蔽该故障。当最终到达用户界面层次时，大多数故障已经得到屏蔽。此时若还有故障不能屏蔽，则必须将故障报告给用大多数故障已经得到屏蔽。此时若还有故障不能屏蔽，则必须将故障报告给用户。对用户而言，只需报告所有的异常及它们的当前任务，不必报告低层服务户。对用户而言，只需报告所有的异常及它们的当前任务，不必报告低层服务器的行为。器的行为。1042成组故障屏蔽成组故障屏蔽 既可通过在一系列位于不同计算机上的服务器上执行同一服务以使得该服既可通过在一系列位于不同计算机上的服务器上执行同一服务以使得该服务具有容错能力，这样即使某些服务器发生了故障，其他服务器