收稿日期:2004󰀁07󰀁14作者简介:刘俊丽(1972󰀁),女,毕业于黑龙江大学计算数学及其应用软件专业,黑龙江省黑河学院计算机系讲师,从事计算机教学工作。分布式系统中容错技术导论

刘俊丽

(齐齐哈尔大学黑河学院,齐齐哈尔164300)

󰀁摘󰀁要󰀁󰀂本文讲述的是分布计算系统出现部分失效的时候,系统应该能自动从失效中恢复过来,并且不会对整个系统的性能产生严重的影响。󰀁关键词󰀁󰀂分布式系统;故障;失效;容错󰀁Abstract󰀁󰀂Thearticleisaboutthefaulttolerancethatthesystemcanrecoverfromthecrashautomaticallyandwon󰀁thaveaseriousinfluenceonthefunctionofthewholesystem.󰀁Keywords󰀁󰀂thedistributedsystem;thecrash;thefailure;thefaulttolerance󰀁中图分类号󰀁TP392󰀁󰀂文献标识码󰀁A󰀁󰀂文章编号󰀁1008-0821(2004)10-0223-03

󰀁󰀁分布计算系统区别于单机系统的一个特点是在分布式

系统中存在着部分失效的情况。当分布式系统某个部件出

现问题的时候就发生了部分失效。虽然部分失效对分布式系统的性能有一定的影响,但同时,它应该不会影响分布

式系统中整个应用程序的正确执行。相反,在单机系统中,

如果系统中的一个关键部件出现问题,整个应用程序就无法继续执行。

分布计算系统的一个重要设计目标是当系统中出现部

分失效的时候,系统应该能自动从失效中恢复过来,并且不会对整个系统的性能产生严重的影响。故此在这里我们

讨论分布计算系统中的容错技术。

容错是计算机科学中一个重要的研究领域。首先介绍与故障处理有关的一些基本概念和分布计算系统中的故障

模型。关于分布计算系统中容错的一些非常有用而详细的

介绍可以参见文献[JALOTE,1994]。

1󰀁基本概念

分布计算系统应该是一个可信赖的系统(dependablesystem),容错是与可信赖系统紧密相联系的一个概念。分

布计算系统的可信赖性(dependability)包括如下几个方面

[KOPETZ,1993]:

1󰀁1󰀁可用性(availability)

可用性反映的是系统随时可被用户使用的特性。也就是说,在任何给定的时刻用户都可以使用此系统正确地执

行用户给定的任务。

1󰀁2󰀁可靠性(reliability)

可靠性指的是在错误存在的情况下,系统持续服务的

能力。尽管可靠性和可用性容易混淆,但它们并不是同一个概念。可靠性反映的是一段时间的特性,而可用性反映

的是某个时刻的特性。高可靠性系统能够持续运行一个相

当长的时间而不会中断。如果一个系统,每个小时都有并且仅有1毫秒时间失效,那么它的可用性可达99󰀁9999%,

但是它仍然是一个高度不可靠的系统。同样地,如果一个

系统从来不崩溃,但是在8月份中,有2个星期的假期需要关机,这个系统是高可靠性的系统,但是它的可用性只

有96%。

1󰀁3󰀁安全性(safety)

安全性指的是在系统出现暂时错误的情况下,不出现灾难性后果的能力。例如核电厂的控制系统和宇宙飞船的

控制系统要求具有很高的安全性。

1󰀁4󰀁可维护性(maintainability)

可维护性指的是系统一旦出现故障,系统易于修复的能力。高可维护性的系统意味着具有高的可用性。对于高

可维护性系统来说,要求它具有自动检测错误和自动修复

的能力。

1󰀁5󰀁保密性(security)

保密性要求系统资源不被非法用户访问。

系统失效指的是系统不能提供它所固有的服务功能。

例如,分布式系统是为用户提供一系列服务的,但其中某一个服务或某些服务功能不能完全正确提供时,就说系统

失效了。

一般来说,从错误的时间特性来看,错误可分为暂时性的(transient)、间歇性的(intermittent)和永久性的(per󰀁

manent)。暂时性的错误一旦发生之后就会消失,当相关的

操作重复执行之后,错误就消失了。间歇性的错误是一会儿出现,一会儿又消失的错误,这种错误是十分令人烦恼

的一种错误,因为它十分难于诊断。永久性错误是一种持

续性错误,这种错误一旦出现,将会长时间存在,直到出现错误的部件被修复为止。像集成芯片被烧坏、软件缺陷、

磁盘磁头损坏等都是永久性错误。󰀁223󰀁2004年10月第10期

October󰀁2004No.10现代情报

󰀁

情报纵横2󰀁基本的故障模型

一个处于故障中的系统不能胜任它所应当提供的服务。

在分布式系统中,系统不能胜任它所提供的服务意味着系

统中的服务员,通信信道,或者二者都不能完全胜任它们

所应当具有的服务功能。在分布式系统中,错误的检测往

往很困难并且很复杂。例如一个失效的服务员可能不是由

这个服务员本身的故障造成的。如果一个服务员只有依赖于其他的服务员才能充分提供它所具有的服务功能,当一

个服务员不能提供它所具有的某项服务或某几项服务时,

错误可能是由该服务员本身造成的,也可能是由其他服务

员间接引起的。分布式系统中的各部件的相互依赖性是很

普遍的,例如一个硬盘错误可能会导致文件服务员不能提供正常的文件服务。如果这个文件服务员是一个分布式数

据库系统的一个组成部分,那么这个数据库系统的正常工

作就处于危险之中,可能会导致数据库系统中只有一部分

数据是可以访问的。所以,了解分布式系统中常见的错误

类型是十分必要的。按照不同的标准,有不同的划分故障

类型的方法,Cristian、Hadzilacos和Toueg将分布式系统中故障划分为如表1所示的几种类型[CRISTIAN,1991;

HADZILACOS,1993]。分布式系统中故障类型故障类型说󰀁󰀁󰀁󰀁明

崩溃性故障󰀁󰀁󰀁󰀁服务员停机,但是在服务员停机之前工作是正常的遗漏性故障󰀁󰀁󰀁󰀁服务员对输入的请求没有响应󰀁󰀁󰀁接收性遗漏󰀁服务员未能接收到输入报文󰀁󰀁󰀁发送性遗漏󰀁服务员未能发送出输入报文

时序性故障󰀁󰀁󰀁󰀁服务员对请求的响应不是按特定的时间间隔进行的响应故障󰀁󰀁󰀁󰀁󰀁服务员的响应是错误的󰀁󰀁󰀁值错误󰀁󰀁󰀁服务员给出了错误的响应值󰀁󰀁󰀁状态转换错误服务员背离了正确的控制流程

随意性故障󰀁󰀁󰀁󰀁服务员在随意的时刻产生了一个随意的响应。

󰀁󰀁崩溃性故障(crashfailure)一般发生在服务员过早地

停机。正常的情况下,一个服务员停机之前需要发送一些

通告性信息,使得系统能够做一些相应的处理,例如重新

启动例外一个服务员替换该服务员的服务等。如果一个服

务员在没有发出任何提示信息的情况下突然停机,就会带

来一系列的错误。例如在电源掉电和操作系统的死机的情况下都可以导致崩溃性故障。通常所提到的节点故障就是

属于这种类型。

遗漏性故障(omissionfailure)发生在虽然服务员是活

着的,但是对某个服务请求没有响应。遗漏性故障的第一

种情况是服务员收不到输入请求,例如一个服务员在处理某个请求的时候,服务员没有一个线程用来侦听到达的服

务请求。接收性遗漏故障不会改变服务员的当前状态,因

为它没有意识到有请求报文发送给它。发送性遗漏故障发生在服务员对所收到的服务请求进行了服务,但是在发送

响应报文的时候出现了故障。例如,服务员在发送响应报

文时,发送缓冲区溢出,而服务员没有处理这种情况的措

施。上述两种遗漏性故障属于我们通常所说的通信故障。另一种遗漏性故障与软件错误有关而与通信无关,如服务

员进入死循环,或者是由于不适当的内存管理,使得服务

员程序长时间被挂起。

时序故障(timingfailure)是一种与定时有关的故障。时序故障发生在服务员对请求的响应超过了特定的时间间

隔,特别是在实时系统中,服务员对服务请求的响应太迟

缓。

响应故障(responsefailure)是一类比较严重的故障,这类故障是指服务员对顾客的服务请求给出了不正确的响

应。一般来说,响应故障分为两类。一类是响应值出现错

误,即服务员给服务请求的回答信息是不正确的。例如,

我们使用一个搜索引擎在Internet上搜索信息,返回的结果却与我们所给出的搜索引擎无关,这是出现了值故障(val󰀁

uefailure),即服务员给出了错误的响应值。另一类响应故

障时状态转换错误(statetransitionfailure),当服务员对所收

到的服务请求做出了不符合期望的反应时,就会出现状态

转换错误。例如,当一个服务员接收到一个它不能识别的报文,而程序中并没有确定如何处理这样的报文,这时就

容易出现状态转换错误。

实际中最严重的一类错误是随意性故障(arbitraryfail󰀁

ure),即我们所熟知的拜占庭故障(Byzantinefailure)。随意性故障是一种随机性的故障,在正常情况下,服务员不会

出现故障,在某些不明因素的影响下,服务员偶尔会对服

务请求给出错误的结果,

这种错误很难被检测出来。当一

个出错的服务员和其他的服务员一起

协同工作时,出错的服务员会影响其他服务员而做出错误的决定。

3󰀁冗余的类型

容错是建立在冗余的基础上的,冗余是设置超过正常

系统操作所需要的信息、资源或时间。下面是典型的四种

冗余类型:

3󰀁1󰀁硬件冗余

附加额外的处理器、I󰀁O设备等。

3󰀁2󰀁软件冗余

附加软件模块的额外版本等。

3󰀁3󰀁信息冗余

如使用了额外位数的错误检测代码等。

3󰀁4󰀁时间冗余

如用来完成系统功能的额外时间。

有些研究者将冗余分为三类,即物理冗余、信息冗余

和时间冗余[JOHNSON,1995]。物理冗余可以用硬件冗余

的方式或软件冗余的方式来实现,因为硬件和软件在逻辑上是等同的。信息冗余的一个例子是海明码(hammingcode),使用海明码技术可以纠正信息在传输中产生的错

󰀁224󰀁现代情报2004年10月第10期

October󰀁2004No.10

󰀁

情报纵横