基于生灭过程的机群系统高可用性分析与设计

*

基于生灭过程的机群系统高可用性分析与设计

（中国科学院计算技术研究所国家智能计算机研究开发中心，北京，100080,）

摘要随着机群中结点数目的增加，系统失效的概率也将增大。为保证超级效劳器提供连续不间断的

效劳，要求系统具有高可用性。本文在对机群系统的运行特性进行分析的根底上，运用马氏过程描述了

机群系统中的高可用性（HighAvailability）,并从理论上建立了基于生灭过程的机群高可用模型。文

中在给出机群高可用管理软件结构的根底匕设计了一种基于集中式结构的主副容错协议；通过可用度

的分析结果得出：机群高可用系统采用了可修复性技术后，只要有一个1IA结点能正常工作，该系统是

“可用”的。

关键词机群系统，高可用性，可扩展性，生灭过程

中图法分类号TP338.6;TP3I6

1引言

机群是一组物理上通过高速互连网连接在一起的计算机集合，通过附加的机群系统软件，互相协作，

作为一个整体对外提供效劳，其中每个计算机称为一个结点。机群系统的优点是可扩展性好。但随着机

瞿系统规模的增大，结点数目的增多，机群系统整体的可靠性会相应降低。因此提高机群系统可用性的

软件将成为机群操作系统中必不可少的局部。

基于UNIX的高可用机群系统首先出现于80年代末期，随后，各主要UNIX厂家纷纷推出自己的

高可用系统,如IBMHACMP,SunSolitice,HPserviceGuard等川⑵网。而微软也于1997年推出了

WindowsNT上的Wolfpack机群软件［4］。直到90年代后期，大局部的系统只支持2~4个结点和1~2个

关键应用。随着Internet使用的迅猛开展，应用软件对效劳器的性能要求又有了进一步的提高。高性能

计算机引入事物处埋领域已成必然，而具可扩展性和高可用性，即能支持几十甚至几百的可扩展的高可

用系统，将成为近年来的研究热点。

本文的研究即为机群系统中的高可用性。第2局部建立基于生灭过程的多机高可用模型，为设计机

举的高可用软件提供了理论根底。第3局部详细讨论了软件结构及实现。第4局部是结论。

2机群系统可用性模型

2.1机群系统运行状态的特性分析

研究可修复系统的主要数学T具是随机过程理论“当构成系统各部件的寿命分布和故障后的修理时

间分布均为指数分布时，只要适当定义系统的状态，这样的系统总可以用马尔可夫过程来描述，而生灭

过程（BirlhT）ealhProcess）那么是马尔可夫过程的一种特殊形式。

在假设同时出现两个或更多个节点故障或修理的概率是零的情况下，由于机群系统运行状态具有无

后效性，并且故障与恢复状态的转换只限于相邻状态，故其故障节点数可以用生灭过程来表示：一个节

点出现故障（Birth）将导致状态数加1,而一个故障节点恢复正常（Death）将导致状态数减1。当系

统的状态处于n时，表示系统有n个节点处于故障状态；一个节点出现故障的到达率为3,某个故障节

点恢复正常的到达概率为口

2.2生灭过程的数学描述

马尔可夫过程的根本概念是系统“状态”及状态“转换”的概念。设｛x(t),t>0｝是取值在E-

｛0,1,…｝或=11｛0,1,N)离散状态空间的一个随机过程。假设对任意自然数n,及任意n个

时刻0w乙<G<....<乙，均有

—=，"—=八・../*)=*｝(1)

=尸｛乩)=i/X(q=*｝证，…<wE

那么称｛X(t),t>0｝为离散状态空间E上的连续时间马尔可夫过程。假设对任意t,u2(),均有

及肥+〃L=i｝=与⑴,iJeE(2)

与u无关，那么称马尔可夫过程｛X(t),t>0｝是齐次的。即只与时差t有关，而与时间起点u的位置

无关。如果一个离散的马尔可夫过程的状态转换只限于相临状态之间，那么称此过程为一个生灭过程。

对于生灭过程，可以自然数来表示可能的状态，而处于状态n的一个过程在下个时刻只能转换到状态n-1

或状态n+1。

生灭过程在排队论中有着重要的地位，主要是因为它有比拟好的统计特性：生灭过程处于状态n的

稳态概率pn可以由引理给出：

4•九・・・4

P"-----匕1[),〃=1,2,.8(3)

从〃2…4

式中，Po为系统处于状态0的稳态概率。

再根据

(4)

*=0

可以得到系统处于每个状态的稳态概率v

2.3多机高可用系统的可用度公式

针对多机的高可用系统，可以合理的做如下假定：①对每个节点在时刻(t,t+At)发生故障的条件概

率是入At；②对每个节点在时刻(t,t+At)完成修理的条件概率是③同时出现两个或更多个节点故

障或修理的概率是零；④每个节点的故障或修理的事件与所有其它事件无关：⑤故障和修复的到达时刻

都是指数分布的。这样就可以建立多机高可用系统的可用度模型。多机高可用系统由n个节点组成，其

状态n的稳态概率小就是多机高可用系统中所有节点都出现故障，即整个系统不可用的概率，而A=(l-

口)即为多机高可用系统的可用度-可以做进一步推导得：

&二44…4-n(n-1)•••(/?-Z:+1)‘2、

p⑸

从〃2…4。2*3*…左

求解(4)[5)式得：凡二一•

这样，多机高可用系统处于状态n的稳态概率P.为:

(6)

<A+//.

（2］

由此得到使用多机高可用系统的可用度为：An=i-Ptl=i-\—2―,（7）

对式7,"1时即为单机系统的可用度，而n=2时可以看作双机高可用系统的可用度。很显然，随着HA

节点数的增加，系统的可用度迅速增加。假定平均修复时间为0.5小时，即修复率为2/小时。计算可得，

在使用高可用技术的8个结点的机群系统中，即使每个结点隹故障率高达0.1次/小时，机群系统的可

用度已经到达99.9999999999%。可以说，在使用高可用技术后，机群系统的可用性已不成问题。

3.机群高可用系统的设计结构

根据以上推导得到的机群高可用模型，文中采用高可用系统的可修复性技术，即考虑系统备份、系

统监测和系统恢复，对机群系统进行了综合设计.

机群高可用系统的软件结构分为“分布式”和“集中式”两类［5］。分布式结构的特点是所有结点

的高可用管理模块都承当相同的功能，处「同等的地位，所有结点的管理模块都互相传送“心跳”消息，

以了解机群中各个结点的资源应用以及结点状态，当需要做应用切换等动作时，需要采用一定的协议来

协调切换结果。

集中式结构的特点是运行在各个结点上的高可用管理模块在功能上存在着一定的分工，处于不同的

地位，有的结点上运行的管理模块只负责进行本地资源和应用的管理，有的结点上运行的管理模块负责

整个机群系统的状态信息管理和切换仲裁，我们称之为全局管理模块。负责管理本地资源和应用的模块

定时向全局管理模块发送本地的状态信息，并执行全局管理模块发来的命令。全局管理模块依据接收到

的所有结点的状态信息，向负责本地资源和应用的模块发送仲裁结果，进行适时的切换动作。

在集中式结构中，任一时刻，设立一个结点是主效劳器，完成所有的工作。一旦这个主效劳器出现

故障，那么副效劳器就接替其工作。与分布式结构相比，集中式结构的优点是消息传送简单且通信费用

小，消息仅仅送到主:效劳器而不是整个效劳器组；第二个优点是任意时刻可以只需一台副效劳器备份即

可。当副效劳器成为主效劳器时，马上要参加一台新的副效劳器。集中式结构的缺点是很难处理拜占庭

故障。

本文即采用集中式结构，如图1所示。设一个结点为主效劳结点，另一个结点为副效劳结点，其它

结点为客户结点。所有结点都向主效劳结点发送“心跳”消息，主效劳结点只向副效劳结点发送“心跳”

消息。当客户结点发生故障或退出HA机群时，由主效劳结点根据负载参数计算切换结果，并向有关结

点发送应用切换的仲裁消息；当主效劳结点发生故障或退出HA机群时，副效劳结点即升级为主效劳结

点，同时选择一个客户结点升级为副效劳结点；当副效劳结点发生故障或退出HA机群，由主效劳结点

选择一个客户结点升级为副效劳结点。

图1一种集中式机群高可用软件结构

主副容错协议用来解决状态更新时主副效劳器的一致性问题。客户机给主效劳器发•个消息；主效

劳器执行任务，并向副效劳器发送更新消息；当副效劳器收到消息后，执行更新操作并发送“确认”消

息给主效劳器：当“确认”消息到达后,主效劳器向客户机发送应答消息。我们可以看到如果主效劳器

在副效劳器发送“确认”消息给主效劳器之后出错，那么当副效劳器接替主效劳器后，任务会被重做3

次。一次是在主效劳器上，一次在副效劳器（请求更新已经发出）上，还有一次是在副效劳黯成为主效

劳器后。

将主副容错协议进行改良后如图2所示，（1）客户机给主效劳器发一个消息；（2）主效劳器向副效

劳器发送更新消息；（3）当副效劳器收到消息后，执行更新操作并发送“确认”消息给主效劳器；（4）

当“确认”消息到达后，主效劳器执行任务；15）主效劳器向客户机发送应答消息。（6）主效劳器向副

效劳器发送“任务已执行”消息。

图2一种改良的主副容错协议

可以看到改良的协议将任务后置执行，目的是防止任务的屡次操作。我们还将每个客户请求附带标

识，在以上协议中的不同时刻主效劳器发生故障的情况分析如下：如果主效劳器在第2步之前出错，不

会产生副作用。客户机将在超时后重发几次请求,发现错误后把副效劳器上升为主效劳器,再发请求。

如果主效劳器在第2步之后，第3步之前出错，那么当副效劳器接替主效劳器后，请求会再次到来。如

果主效劳器在第3步之后，第4步之前出错，那么当副效劳器接替主效劳器后，任务还未执行，请求会

再次到来，可以克服传统协议中任务被执行3次的缺点。如果主效劳器在第4步之后，第5步之前出错,

那么当副效劳器接替主效劳器后，任务已执行，而当请求再次到来时，由于请求标识与前一次请求相同，

副效劳器不会再执行同样的任务，这样保证了任务只执行一次。如果主效劳器在第5步之后，第6步之

前出错，那么当副效劳器接替主效劳器后，任务已执行，而客户也已收到应答消息、。

4.结论

本文运用马氏过程分析了机群系统中的高可用性，建立基于生火过程的多机高可用模型，提出了一

种基于集中式结构协议的设计和实现方法。通过多机可用度的分析，得出了在使用8个节点的机群高可

用系统中，即使每个节点的故障率高达0.1次/小时，其可用度也可以到达99.9999999999研勺结论，对

于机群高可用性的研究具有非常积极的作用。

参考文献

[l]AshishSinghai,etc:TheSunSCALRFrameworkforInternetServers,1998IEEEFTCS

(Hault_TolerantComputing)

[2]IBMcorp.RS/6000HACMPforAIXWhitePaper,,1997

[3]T.Agerwala.etc:SP2systemarchitecture,IBMSYSTEMJournalVOL34,NO2,1995

[4]WernerVegels,etc:TheDesignandArchitectureoftheMicrosoftClusterService,1998IEEE

FTCS(Fau1t_TolerantComputing)

[5]FelixC.Gartner:FundamentalsofFault-TolerantDistributedComputinginAsynchronous

Environments,ACMComputingSurvey,Vol.31,No.1,March1999

TheDesignandAnalysisofCluster'sHighAvailabilityBasedon

Birth-DeathProcess

GAOWenandZHUMing-Fa

(NationalResearchCenterforIntelligentComputingSystem,

InstituteofConiputingTechnology,ChineseAcademyofScience