Web集群中基于实时概率的容错调度算法研究

摘 要 论文中首先对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|i=1,2,…}。ti可以用一个四元组(gi，si，di，pi)来表示。其中，gi表示请求到达系统的时间；si表示请求被调度开始执行的时间；di表示请求必须执行完成的时间，即deadline；pi表示请求的执行时间；采用的故障模型同第2节[5]，另外，在对请求进行容错调度的同时，系统要能及时通过“心跳”诊断并报告处理机故障[10]。由于处理机之间通信所需时间与请求的执行时间相比非常短，因此可忽略处理机之间消息的传递时间[7,8]。 基于概率的实时容错调度算法基本思想如下：对任一动态到达系统的非周期性任务ti，我们将首先置入主请求队列qp，同时将此请求复制一份到从请求队列qb，主请求记为pti,，从请求(或称为后备请求)记为bti，确定它的区分

服务等级k，以区分服务的等级确定从备份请求的延迟时间和重发的概率，以这二个参数标记从备份请求队列bti，如果在tri重发时间前收到pti成功执行的报告，则取消bti，否则按标记重发tri，这就是无错时停止重发以提高系统的性能。 假设pti与bti被调度的时间段分别记为slot(pti)与slot(bti)，那么实时容错调度算法如图2所示。 3.2 实时容错调度算法 算法：实时容错调度算法 1、 当一个新请求ti到达系统后，先将pti置入主请求调度队列，通过复制获得从备份请求bti，置入从请求队列。确定四元组中的三个元素{ gi，di，pi }和区分服务等级ki。 2、 在前端分发器中调度pti。 ① 主请求队列中的pti根据负载均衡原则调度到调度表中允许的可用服务器，调度开始执行时间为si。 ② 依据区分服务等级确定延迟时间区间范围：delayti=[si,di-pi]； ③ 依据区分服务等级确定重发的时间sbti和概率pbti，sbti=（1-ξ）* delayti, pbti=k*ξ； //ξ为区分服务所对应的级别，在(0～1)之间，k为常数； ④ 以(pbti，sbti ，di，pi)标记从备份请求bti； 3、 以bti的调度参数调度bti执行，调度满足如下原则：server(pti)!= server(btj),如果server(pti)= server(ptj)且server(bti) = server(btj)，那么slot(bti)∩slot(btj)=φ,其中,i≠j； // server(ptj)表示处理请求ptj的服务器； 4、对从请求任务在调度前收到pti正常执行结束的消息,则取消从备份队列中的bti请求。 图2 实时容错调度算法 4 分析与仿真实验结果 通过对第2节的分析，我们很容易得到在不同系统参数下，web集群系统服务器台数与可用度的关系，如图3所示。

图3 不同参数下，系统可用度与服务器台数的关系 对于容错调度算法，spare processor方法[9]是采用一个或多个处理机作为备份，若系统出现故障时，则把故障机上的任务全部转移到备份处理机上运行，采用重新执行的方式来恢复。而若在系统没出现故障时,备份处理机一直处于空闲状态。 实时容错调度算法中主要考虑系统可用度的提高与系统接纳率，我们考虑在第2节故障模型下，采用容错调度算法后，可用度与系统利用率的关系如图4所示，可用度越高，系统利用率则越低。 图4 可用度与系统利用率关系图 图5表示与其它算法[9]在不同负载率情况下拒绝率的对比，从而说明本研究中所提出的实时容错调度算法能提高系统的接收率。

图5 不同负载下系统拒绝率对比图 5 结论 服务器冗余是提高系统可用度的基础，但同时降低了系统性能。论文主要从集群系统可用度的数学建模和容错调度二个方面分析了提高可用度的措施，实验结果表明算法很好地支持了系统的可用性，对于集群与分布式系统的高可用性分析与容错调度有较好的指导作用。 参考文献 1 v. cardellini, e. casalicchio, m. colajanni, p.s. yu. the state of the art in locally distributed web-server systems. acm computing surveys, 2002, 34(2): 1-49. 2 钱方，贾焰等. 提高冗余服务性能的动态容错算法. 软件学报，2001，12(6): 928-935. 3 周幼英，李福超等.关于调度算法与web集群性能的分析. 计算机研究与发展，2003,40(3): 483-492. 4 p.r. parthasarathy ,r.b. lenin on the exact transient solution of finite birth and death processes with specific quadratic rates. math. scientist, 1997, 22: 92-105. 5 高文，祝明发. 基于生灭过程的机群系统高可用性分析与设计. 微电子学与计算机，2001，18(4): 47-49. 6 郑在宾，金海等. 有tcp连接容错功能的网络负载平衡调度系统. 华中科技大学学报，2003,31(2): 17-19. 7 ying feng,son sang h. scheduling hard real-time tasks with tolerance of multiple processor failures. microprocessing and mcroprogramming, 1994,40: 193～206. 8 piestman a l. a fault-tolerant scheduling problem. ieee trans on software engineering, 1988, (12): 1089-1095. 9 sylvain lauzac, rami melhem. adding fault-tolerance to p-fair real-time scheduling. in: workshop on embedded fault-tolerant systems 1998，34-37. 10 曾碧卿，陈志刚. 服务器集群系统研究. 计算机应用研究，2004，21(3)：186-187，196