《Web集群中基于实时概率的容错调度算法研究》由会员分享，可在线阅读，更多相关《Web集群中基于实时概率的容错调度算法研究（4页珍藏版）》请在金锄头文库上搜索。
1、1Web 集群中基于实时概率的容错调度算 法研究摘 要 论文中首先对 Web 集群系统运用 Markov 模型描述了其可用性，从理论上建立了集群高可用模型。然后，着重针对 Web 集群系统中区分服务对不同请求采取不同的服务质量，对可用度的指标要求也不相同的情况，提出了一种基于概率的实时容错调度算法。 关键词 Web 集群，可用度，容错调度，算法1 引言由于 Internet 中信息的数量呈指数级增长，其中的主要信息是 Web 信息，因此，基于单一系统映像的 Web 服务器集群系统是满足当前应用的有效方法。该方法把若干性能较低的服务器用局域网连成一个性能较高的整体，即 Web 服务器集群1,系统
2、结构如图 1 所示，前端分发器依据一定的原则将客户请求分发给后台服务器，后台服务器执行客户请求后返回给客户，使其从客户端看来就如同一台服务器。图 1 Web 集群系统模型图高可用性是 Web 集群系统提出的三大目标（高性能、高可用、易扩展）之一，它起初主要是利用系统中后台服务的冗余来达到系统的高可用性，但是随着研究的深入和基于内容的前端分发器的发展，并不要求后台服务是同一的，这就增加了系统的灵活性，提高了处理机的利用率，同时允许系统进行动态配置，如负载均衡调度等，这也给系统可用性设计与调度提供了更多的要求。但值得指出的是：一直少有对系统可用度的研究，特别是利用数学模型建模来进行定性与定量分析的
3、实时容错调度算法研究。现有的可用度研究大多只针对冗余服务的可用性,而对它们的2性能考虑得不够全面2,3。本文的研究工作主要在于：首先对 Web 集群系统运用 Markov 模型描述了其可用性，从理论上建立了集群高可用模型。然后，着重针对 Web 集群系统中区分服务对不同请求采取不同的服务质量，对可用度的指标要求也不相同的情况，提出了一种基于概率的实时容错调度算法，算法采用了请求的主从备份技术。通过延迟从备份请求重新转发时间，来为可能因处理机故障而执行失败的主请求实现容错功能，并通过对无错时停止重发来提高处理机的利用率和系统对任务的接收率,实验结果证实了算法的有效性。2 Web 集群可用度数学模
4、型与分析当构成系统各部件的寿命分布和故障后的修理时间分布均为指数分布时，只要适当定义系统的状态，这样的系统总可以用马尔可夫过程来描述。如果一个离散马尔可夫过程的状态转换只限于相邻状态之间，则称此过程为一个生灭过程4。对于生灭过程，可用自然数来表示可能的状态，而处于状态 n 的一个过程在下个时刻只能转换到状态 n-1 或状态 n+1。生灭过程处于状态 n 的稳态概率 pn 如下：(1)式中，P0 为系统处于状态 0 的稳态概率。再根据(2)可以得到系统处于每个状态的稳态概率5。针对集群系统，可以做如下模型假定：故障和修复的到达时刻都是指数分布的,分别为 n 和 n；对每个节点在时刻(t,t+Dt
5、)发生故障的条件概率是 lDt；对每个节点在时刻(t,t+Dt)完成修理的条件概率是 mDt；同时出现两个或更多个节点故障或修理的概率是零；每个节点的故障或修理的事件与所有其它事件无关。这样就可以建立集群系统的可用度模型。集群系统由 n 个节点组成，其状态 n 的稳3态概率 pn 就是集群高可用系统中所有节点都出现故障，即整个系统不可用的概率，而 A=(1- pn)即为集群系统的可用度。(3)求解(2)、(3)式得： 这样，集群系统处于状态 n 的稳态概率 pn 为：(4)由此得到集群系统的可用度为(5)对式(5),随着节点数的增加，系统的可用度迅速增加。假定平均修复时间为 0.5 小时。计算
6、可得，在有 4 个结点的集群系统中，即使每个结点的故障率高达 0.1 次/小时，集群系统的可用度已经达到 99.9%。那么已知系统所需的可用度为 An，很容易得到所需服务器台数为：n= (6)3 基于概率的实时容错调度3.1 实时容错调度算法的基本思想随着电子商务等关键业务的发展，要求任务的执行可用度很高，而且往往都有严格的时间约束,若由于处理机的故障导致某些任务不能完成，或不能在其限定的时间之前完成，就可能造成重大损失1,6。因此需要在 Web 集群系统中提供一定的实时容错调度能力以提高整个系统的可用性。文献7、8提出在不同处理机上调度任务的多个版本来运行，以此达到容错的目的。 但是，同样任
7、务的多个版本，运行时具有同样的请求，系统利用率只有 1/n。文献9提出了一种回收的方法，提高了系统效率。 系统的请求集可定义为 =Ti|i=1,2,。Ti 可以用一个四元组(Gi，Si，Di，Pi)来表示。其中，Gi 表示请求到达系统的时间；Si 表示请求被调度开始执行的时间；Di表示请求必须执行完成的时间，即 deadline；Pi 表示请求的执行时间；采用的故障4模型同第 2 节5，另外，在对请求进行容错调度的同时，系统要能及时通过“心跳”诊断并报告处理机故障10。由于处理机之间通信所需时间与请求的执行时间相比非常短，因此可忽略处理机之间消息的传递时间7,8。基于概率的实时容错调度算法基本
8、思想如下：对任一动态到达系统的非周期性任务 Ti，我们将首先置入主请求队列 Qp，同时将此请求复制一份到从请求队列Qb，主请求记为 Pti,，从请求(或称为后备请求)记为 Bti，确定它的区分 服务等级 k，以区分服务的等级确定从备份请求的延迟时间和重发的概率，以这二个参数标记从备份请求队列 Bti，如果在 Tri 重发时间前收到 Pti 成功执行的报告，则取消 Bti，否则按标记重发 Tri，这就是无错时停止重发以提高系统的性能。 假设 Pti 与 Bti 被调度的时间段分别记为 Slot(Pti)与 Slot(Bti)，那么实时容错调度算法如图 2 所示。3.2 实时容错调度算法算法：实时
9、容错调度算法1、 当一个新请求 Ti 到达系统后，先将 Pti 置入主请求调度队列，通过复制获得从备份请求 Bti，置入从请求队列。确定四元组中的三个元素 Gi，Di，Pi 和区分服务等级 Ki。2、 在前端分发器中调度 Pti。 主请求队列中的 Pti 根据负载均衡原则调度到调度表中允许的可用服务器，调度开始执行时间为 Si。 依据区分服务等级确定延迟时间区间范围：Delayti=Si,Di-Pi；5 依据区分服务等级确定重发的时间 SBti 和概率 PBti，SBti=（1-）* Delayti, PBti=K*；/ 为区分服务所对应的级别，在(01)之间，K 为常数； 以(PBti，SB
10、ti ，Di，Pi)标记从备份请求 Bti；3、 以 Bti 的调度参数调度 Bti 执行，调度满足如下原则：Server(Pti)!= Server(Btj),如果 Server(Pti)= Server(Ptj)且 Server(Bti) = Server(Btj)，那么 Slot(Bti)Slot(Btj) =,其中,ij； / Server(Ptj)表示处理请求 Ptj 的服务器；4、对从请求任务在调度前收到 Pti 正常执行结束的消息,则取消从备份队列中的Bti 请求。 图 2 实时容错调度算法4 分析与仿真实验结果通过对第 2 节的分析，我们很容易得到在不同系统参数下，Web 集群
11、系统服务器台数与可用度的关系，如图 3 所示。图 3 不同参数下，系统可用度与服务器台数的关系对于容错调度算法，Spare processor 方法9是采用一个或多个处理机作为备份，若系统出现故障时，则把故障机上的任务全部转移到备份处理机上运行，采用重新执行的方式来恢复。而若在系统没出现故障时,备份处理机一直处于空闲状态。实时容错调度算法中主要考虑系统可用度的提高与系统接纳率，我们考虑在第2 节故障模型下，采用容错调度算法后，可用度与系统利用率的关系如图 4 所示，可用度越高，系统利用率则越低。图 4 可用度与系统利用率关系图图 5 表示与其它算法9在不同负载率情况下拒绝率的对比，从而说明本研
12、究中6所提出的实时容错调度算法能提高系统的接收率。图 5 不同负载下系统拒绝率对比图5 结论服务器冗余是提高系统可用度的基础，但同时降低了系统性能。论文主要从集群系统可用度的数学建模和容错调度二个方面分析了提高可用度的措施，实验结果表明算法很好地支持了系统的可用性，对于集群与分布式系统的高可用性分析与容错调度有较好的指导作用。参考文献 1 V. Cardellini, E. Casalicchio, M. Colajanni, P.S. Yu. The state of the art in locally distributed Web-server systems. ACM Computi
13、ng 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, 2
14、2: 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: 193206. 8 Piestman
15、 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
