[科普中国]-容错分布系统

简介

分布式系统作为一个相对较新的领域，迄今还没有一致、权威的定义。一般来说，分布式系统可以简单地定义为：一个运行在一系列自治处理单元上的系统，每个自治处理单元有各自的物理存储器空间并且它们之间的通信延迟不能忽略不计。同时在这些自治处理单元之间不是各自为政而是存在一定合作。一个自治处理单元叫做一个进程。

而容错分布式系统，是指在系统中存在一定故障的情况下仍能正常运行的分布式系统。1

系统模型系统模型(systemmodel)是对分布式系统所作的一系列抽象的假设，也是我们研究问题的基础。它一般包含两方面：一、假设系统里存在一些可以互相通信的进程，如图所示；二、对一些与进程和通信有关的系统参数所作的假设。而一个系统模型的强弱取决于它对系统所作假设的强弱，比如无故障的模型强于允许故障的模型。

系统模型中涉及的系统参数包括以下几个方面。

通信方式进程间的通信方式分为存储器共享(sharedmemory)和消息传递(messagepassing)。消息传递的方式又分为点对点(point—to—point)和组播(multieast)。

其中最常见是的点对点消息传递的通信方式，组播为视可用点对点的消息传递来实现的一种复合的通信方式。1

同步和异步关于消息延时和进程间的相对速度这两者的假设被称为同步条件，它是判断一个系统模型是同步还是异步的标准。如果假设两者的上界都是已知的，那么这一系统模型是同步模型；如果假设两者都是无界的，那么这一系统模型就是异步模型。

同步的假设对系统作了严格的限制，现实中的很多系统(如建筑在消息延时不确定的广域网上的系统)都无法满足这一假设。况且为了使一些系统满足同步假设，必须把消息延时的上界设得很大，导致协议中的超时时间也必须设得很长，从而牺牲了协议的效率。于是在研究中更多考虑的是异步模型，而异步模型中主要关注的是不定长的消息延时，即一个消息从一个进程传递到另一个进程的时间长度是未知的。

除了同步和异步模型，还有部分同步模型和时控异步模型。在时控异步模型中，进程的时钟偏移率(时钟每秒相对物理时间的偏差)可以忽略，因而进程可检测到某事件发生的真实时间。在部分同步模型中，或者假设消息延时和进程的相对速度都存在上界，但并非已知，或者假设两者的上界都已知，但仅在一个未知的时间点以后生效。一般把以上两个假设称作部分同步条件。1

故障在容错分布式系统中的故障(failure)可分为进程故障和通信故障。当说到在某个系统模型下假设或允许某种故障，其含义是在这一系统模型下假设这种故障是可能发生的。1

1进程故障

当我们说一个进程正常运行，指的是这个进程按照指定的协议运作(包括如何收发消息和实现内部状态的转换)。一般假设系统中至少存在一个正常运行的进程。若一个进程不正常运行，那么我们说它发生了故障。进程故障按照危害程度，可分为：停止故障、遗漏故障和拜占庭故障。停止故障指的是一个进程从正常运行的状态进入到完全停止的状态并且不再恢复。遗漏故障指的是进程在应该收发消息的时候漏发或漏收消息。拜占庭故障(Byzantinefailure)指的是进程不按照指定的协议运行，即它的行为完全不可预测。按照发生故障的进程数目，又可分为多数故障和少数故障。多数故障是指系统的某次运行中发生故障的进程数目超过或等于半数；少数故障是指系统的某次运行中发生故障的进程数目低于半数。

目前主要考虑允许停止故障(而不允许其他进程故障)的系统模型，因为事实证明在异步模型下考虑遗漏故障和拜占庭故障将使问题过于复杂。注意到在异步模型下由于不定长的消息延时，当一个进程长时间没收到另一进程的消息时，它无法判断这是由于消息延时还是由于这个进程己经停止运行。因此异步模型下实际无法区分一个正常运行的进程和一个己发生停止故障的进程。1

2.通信故障

在点对点的消息传递中，当我们说从进程A到B的链路(link)是可靠的，指的是此链路满足以下两点：一、当A和B都正常运行时，A发送给B的消息将最终到达B；二、如果B收到了来自A的某个消息，那么此消息的确是由A发出的。若一条链路不是可靠的，那么我们说它发生了故障。通信(或链路)故障按照危害程度，可分为消息丢失和任意链路。消息丢失指的是某条链路违反以上第一点，但满足第二点。任意链路指的是某条链路违反以上第一点或第二点。

目前主要考虑允许消息丢失(而不允许其他通信故障)的系统模型。和停止故障不同，消息丢失是一种不稳定的故障，即有无故障的两种状态可以互相切换。如果在某段时间内，从某链路的发送端发出的消息全部丢失，那么我们称这条链路在那段时间内是断开的。注意到在异步模型下由于不定长的消息延时，当一个进程长时间没收到另一进程的消息时，它无法判断这是由于消息延时还是消息丢失，因此异步模型下实际无法区分一条可靠的链路和一条断开的链路。1

网络拓扑网络拓扑(network topology)主要是指一张由正常运行的进程和这些进程间可靠的链路构成的有向图。其中的每一条有向边A→B的存在，是当且仅当A和B都正常运行，而它们间的通信链路存在且可靠。因此进程故障和通信故障是网络拓扑变化的主要原因。比如在图中，虚实箭头表示存在的链路，当进程a和b、c和d之间的链路可靠时整个网络拓扑是强连通的，而当这两条链路都断开后网络拓扑便被分割成了两个互不连通的分量。

一般把网络拓扑由于进程或通信故障被分成两个或两个以上互不连通的分量的现象被叫做网络分割。注意到在异步模型下，消息延时可能导致无法判断一条链路是否己断开，因此异步模型下存在一种和真实网络分割不可区分的虚网络分割。对于网络拓扑中的某一个子图S，若存在某一时刻，从这一时刻起S满足以下三点：一、S中的进程不是停止就是正常运行(且没有进程加入和退出S)；二、S中的每对进程间的链路都是可靠的；三、S中的进程和系统中其他进程间的链路都是断开的，那么我们称S是一个稳定分量。

系统模型中对网络拓扑的假设最常见的有两种，一种假设网络拓扑总是强连通的(stronglyconneeted)或全连通的(completelyconneeted)，作这种假设的系统模型一般同时假设可靠的通信链路；另一种是假设网络拓扑是可分割的(partitionable)，即假设可能出现网络分割现象，作这种假设的系统模型一般同时允许消息丢失的通信故障。1

两个经典问题故障检测器和共识是容错分布式系统中两个经典的问题，同时也是最常用的两个服务。早在80年代，它们己被证明在异步模型下是不可解的。正因为不可解，它们常常在异步模型下被当作神谕使用。这两个不可能性结果对于异步模型下的系统设计起到极其重要的作用，并且自此以后，研究一个规格的可解性时，常常把它和FD以及Consensus的规格作比较。

共识共识(Consensus)是分布式系统中常常需要解决的问题，也就是要使得系统中的进程在某一变量的值上达成一致。通常Consensus规格的接口是由每个进程向Consensus提供一个可选变量值(提出一个变量值)，而后从Consensus得到一个最终变量值(决定一个变量值)。Consensus最常见的规格如下，它被证明在经典模型下是不可解的。

如无特殊说明，Consensus(规格)指的就是下述规格。

输入：进程提出一个变量值

输出：进程决定一个变量值

1、终止性termination)：每个正常运行的进程最终决定某个值

2、一致性(agreemcnt)：没有两个进程决定不同的值

3、有效性(validity)：每个进程最多决定一次，且它所决定的值一定被某个进程提出过

一种特殊的Consensus规格叫二进制共识，它规定了进程提出和决定的变量值只能是0或1。已经证明，二进制Consensus规格和上述规格是一样强的。1

故障检测器故障检测器(FailureDeteetor，FD)概括了容错分布式系统中最需要解决的一个问题，也就是要使得系统中的进程尽可能精确地检测到有哪些进程或链路己经发生故障。大部分FD规格是在经典模型下被提出，因此它们需要检测的仅仅是哪些进程已停止运行。在这种情况下，FD规格的输出既可以是被认为停止的进程，又可以是被认为正常运行的进程。

公认的经典模型下的FD规格有很多，这些FD规格所满足的属性一般是完备性和不同程度的准确性的组合。简而言之，FD的完备性是指出故障的进程应最终被检测到，FD的准确性(accuracy)是指正常运行的进程不应被检测到(或者说被凡是检测到的都是已出故障的进程)，而FD的精确性(preejsion)是完备性和准确性的组合。证明了同时具有完备性和(不同程度)准确性的FD规格在经典模型下都是不可解的。

完备性和四种不同程度的准确性的组合可产生四种FD规格：(若输出是被认为正常运行的进程，只须把属性中的“输出”和“不输出”反置

输出：(被认为)已停止运行的进程的记

1、完备性(completeness)：存在一个时刻t1，从t1起每个停止的进程都将被每个正常运行的进程的FD输出

2、强准确性(strongaccuracy)：任何正常运行的进程都不会被任何进程的FD输出(每个被FD输出的进程都是停止的进程)

3、弱准确性(weakaccuracy)：存在一个正常运行的进程，它不会被任何进程的FD输出

4、最终强准确性(eventuallystrongaccuracy)：存在一个时刻t2，从t2起任何正常运行的进程都不会被任何进程的FD输出(最终每个被FD输出的进程都是停止的进程)

5、最终强准确性：存在t2和一个正常运行的进程，从t2起这个进程不会被任何进程的FD输出1

系统维修策略许多实际系统在使用过程中，往往由于对维修性问题考虑不周，致使系统的维修费用增加；另一方面如果对系统进行过多的维修，不仅不能提高系统的可靠性和可用度，反而使系统的性能降低。因此系统采用何种维修策略，将关系到系统的性能和维修费用。

维修策略连续时间的基本维修策略主要有：年龄更换策略、成批更换策略、故障小修的周期更换策略、年龄维修策略、备用部件的预防维修策略、故障小修的周期维修策略等。由于计算机及其外部设备都极其昂贵，若采用故障更换的方法显然不合适，而采用故障维修的方法则是较为经济的维修策略。

年龄维修策略是指：当系统达到指定的年龄T仍然正常，则对系统进行预防维修，预防维修时间均值为α。若系统在指定的时间T之前发生故障，就立即进行事后维修，维修时间均值为β，图为其示意图。2

机载容错分布式系统研究背景及意义作为嵌入式系统在航空航天领域的应用，机载容错分布式系统是新一代航空电子系统的核心，而综合化航空电子系统又是现代飞行器的神经中枢。航空电子系统的发展直接促进了机载计算机技术的发展，新一代飞机的航空电子系统是以高度集成化、模块化为特征，以机载实时容错分布式计算机系统为载体，高度综台化、高可靠性、具有容错能力的系统。

新一代航空电子系统是一种综合化、模块化的机载分布式体系结构，原“子系统”的概念演变为在统一的计算机处理平台上运行的软件功能组件．不再存在“子系统”的专用计算机资源。机载容错分布式系统将承担着大量飞行任务的执行、控制和飞机安全性保障等工作，美国的F35就是典型的代表。

机载容错分布式系统的软件已成为影响整个飞机性能的关键因素之一，而按国外一些关于新一代航空电子系统的规范和标准，确定性设计是至关重要的。3

系统结构机载容错分布式系统的系统结构由多个计算机群及系统大容量存储器SMM(SystemMass Memory)组成，整个系统通过一个具有双余度的FC环网连接成分布式系统。每个计算机群由多个信号处理模块和数据处理模块组成。每个计算机群除与系统FC环网连接之外，还与本地的FC开关网络连接．实现机群内的局部通讯。SMM为整个系统的系统软件、应用程序以及相关数据参数提供加载、存储、记录和管理服务以及关键信息的存储。

机载容错分布式系统将是新一代航空电子系统的核心，而其系统软件又是整个系统的关键，其软件结构由美国的“宝石台”计划的“系统执行、分布执行和核心执行”三个执行发展到欧洲的ASAAC规范的航电系统软件新结构。按这种结构，系统软件是一个立体结构，系统软件的结构按水平方向分为应用层、操作系统层、模块支持层，这称为三层栈TLS结构(TlhrccLayerStack)；按垂直方向分为实时操作系统部分和系统管理部分。系统管理又分为应用管理AM和通用系统管理GSM。AM在应用层，GSM在操作系统层；按立体方向进行划分系统管理可分为三级；飞机级AC(Aircraft)、综合区级IA(Integration Area)和资源元素级RE(ResourceElement)。飞机级的系统管理负责控制和监控整个IMA(IntegratedModuleAvionics)。IA级系统管理负责控制某一子功能模块，RE级系统管理是最底层的系统管理，负责管理单个PE(ProcessingElemeat)的功能。

如图给出了机载容错分布式系统的软件结构。3