摘 要 论文中首先对Web集群系统运用Markov模型描述了其可用性，从理论上建立了集群高可用模型。然后，着重针对Web集群系统中区分服务对不同请求采取不同的服务质量，对可用度的指标要求也不相同的情况，提出了一种基于概率的实时容错调度算法。
关键词 Web集群，可用度，容错调度，算法
1 引言
由于Internet中信息的数量呈指数级增长，其中的主要信息是Web信息，因此，基于单一系统映像的Web服务器集群系统是满足当前应用的有效方法。该方法把若干性能较低的服务器用局域网连成一个性能较高的整体，即Web服务器集群[1],系统结构如图1所示，前端分发器依据一定的原则将客户请求分发给后台服务器，后台服务器执行客户请求后返回给客户，使其从客户端看来就如同一台服务器。
图1 Web集群系统模型图
高可用性是Web集群系统提出的三大目标（高性能、高可用、易扩展）之一，它起初主要是利用系统中后台服务的冗余来达到系统的高可用性，但是随着研究的深入和基于内容的前端分发器的发展，并不要求后台服务是同一的，这就增加了系统的灵活性，提高了处理机的利用率，同时允许系统进行动态配置，如负载均衡调度等，这也给系统可用性设计与调度提供了更多的要求。但值得指出的是：一直少有对系统可用度的研究，特别是利用数学模型建模来进行定性与定量分析的实时容错调度算法研究。现有的可用度研究大多只针对冗余服务的可用性,而对它们的性能考虑得不够全面[2,3]。
本文的研究工作主要在于：首先对Web集群系统运用Markov模型描述了其可用性，从理论上建立了集群高可用模型。然后，着重针对Web集群系统中区分服务对不同请求采取不同的服务质量，对可用度的指标要求也不相同的情况，提出了一种基于概率的实时容错调度算法，算法采用了请求的主从备份技术。通过延迟从备份请求重新转发时间，来为可能因处理机故障而执行失败的主请求实现容错功能，并通过对无错时停止重发来提高处理机的利用率和系统对任务的接收率,实验结果证实了算法的有效性。
2 Web集群可用度数学模型与分析
当构成系统各部件的寿命分布和故障后的修理时间分布均为指数分布时，只要适当定义系统的状态，这样的系统总可以用马尔可夫过程来描述。
如果一个离散马尔可夫过程的状态转换只限于相邻状态之间，则称此过程为一个生灭过程[4]。对于生灭过程，可用自然数来表示可能的状态，而处于状态n的一个过程在下个时刻只能转换到状态n-1或状态n+1。
生灭过程处于状态n的稳态概率pn如下：
(1)
式中，P0为系统处于状态0的稳态概率。再根据
(2)
可以得到系统处于每个状态的稳态概率[5]。
针对集群系统，可以做如下模型假定：①故障和修复的到达时刻都是指数分布的,分别为λn和μn；②对每个节点在时刻(t,t+Dt)发生故障的条件概率是lDt；③对每个节点在时刻(t,t+Dt)完成修理的条件概率是mDt；④同时出现两个或更多个节点故障或修理的概率是零；⑤每个节点的故障或修理的事件与所有其它事件无关。这样就可以建立集群系统的可用度模型。集群系统由n个节点组成，其状态n的稳态概率pn 就是集群高可用系统中所有节点都出现故障，即整个系统不可用的概率，而A=(1- pn)即为集群系统的可用度。
(3)
求解(2)、(3)式得：
这样，集群系统处于状态n的稳态概率pn为：
(4)
由此得到集群系统的可用度为
(5)
对式(5),随着节点数的增加，系统的可用度迅速增加。假定平均修复时间为0.5小时。计算可得，在有4个结点的集群系统中，即使每个结点的故障率高达0.1次/小时，集群系统的可用度已经达到99.9%。那么已知系统所需的可用度为An，很容易得到所需服务器台数为：
n= (6)
3 基于概率的实时容错调度
3.1 实时容错调度算法的基本思想
随着电子商务等关键业务的发展，要求任务的执行可用度很高，而且往往都有严格的时间约束,若由于处理机的故障导致某些任务不能完成，或不能在其限定的时间之前完成，就可能造成重大损失[1,6]。因此需要在Web集群系统中提供一定的实时容错调度能力以提高整个系统的可用性。
文献[7]、[8]提出在不同处理机上调度任务的多个版本来运行，以此达到容错的目的。 但是，同样任务的多个版本，运行时具有同样的请求，系统利用率只有1/n。文献[9]提出了一种回收的方法，提高了系统效率。
系统的请求集可定义为Γ={Ti 页码：12