一种增强型LVS集群的动态反馈均衡算法*

么丽颖

(黑龙江信息技术职业学院)

一种增强型LVS集群的动态反馈均衡算法*

么丽颖

(黑龙江信息技术职业学院)

介绍了LVS集群系统，分析了负载均衡任务调度策略，在此基础上，研究并设计了一种增强型LVS集群系统动态反馈均衡算法，提出新的算法来计算集群系统中服务节点在下一个周期所能承担的负载增量INCLi，以达到系统负载均衡的目的.

集群;动态反馈;负载均衡算法

0 引言

LVS(Linux Virtual Server)集群系统将一组实际网络服务器通过负载均衡器汇集在一起、并使用共享的存储服务系统为外部网络提供灵活的、实时的、高性能的服务.负载调度器是LVS集群系统对外部网络的前端机，其任务是将外部网络的客户访问请求合理地、均衡地分配到集群中一组实际服务器上执行，其目标是缩短系统的平均响应时间、并能充分的利用系统资源.对于客户端来说，LVS集群系统是一个独立的具有唯一一个IP地址的服务器，集群系统的结构及任务的分配执行对客户端是透明的.目前，集群负载调度器一般采用以IP负载均衡技术及基于内容请求分发技术作为基础开发的动态负载均衡任务调度策略，目的是构建高性能、高可用、可伸缩的实时集群系统.

1 负载均衡任务调度策略分析

负载均衡任务调度策略的优劣在于设计采用的负载均衡调度算法的效率，负载均衡调度算法分为静态调度算法和动态调度算法.目前常用的静态调度算法有轮转调度(Round－Robin Scheduling)、加权轮转调度(Weighted Round－Robin Scheduling)、最少连接调度(Least－Connection Scheduling)、加权最少连接调度(Weighted Least－Connection Scheduling)、短作业优先调度(Short Job First Schedule)、优先级调度(Priority Schedule)、Best Fit调度及 First Fit调度等.静态调度算法的特点是负载均衡器上记录每台真实服务器(服务节点)的负载值，负载值的计算依据服务节点的部分负载指标，如CPU占用率、内存利用率、过去一个时间段内的平均负载及CPU运行队列长度等.静态调度算的缺点是其调度策略不参考系统运行时系统各项指标的实时变化，致使集群系统各真实服务器上的实际负载与负载均衡器上所记录的负载值有一定的误差，最终导致集群系统各服务节点负载分配的不平衡，而动态反馈负载均衡算法可以很好地解决该问题.

动态反馈负载均衡算法的核心思想是在集群系统运行一段时间之后，通过周期性的负载信息反馈来调整调度器上的记录.

2 LVS集群系统动态负载均衡算法的设计

在此，笔者研究与设计LVS集群的动态负载均衡算法，而LVS集群系统采用的是集中式的负载均衡系统结构，集中式的负载均衡系统是相对分布式负载均衡系统而言的.分布式负载均衡系统中，每个系统节点均作为负载均衡器，接收其它节点的负载信息，负载均衡算法的实现方式很灵活，但技术实现上相对复杂.集中式的负载均衡系统结构是在前端负载调度器上实现调度策略的.在设计LVS集群的动态反馈负载均衡算法之前，首先要分析和解决以下三点问题.

2.1 集群系统负载指标研究

根据集群系统的应用需求，研究服务节点的各项负载信息，最终确定部分负载信息作为负载均衡算法的负载指标来计算负载值.外部网络的客户访问消耗集群系统资源的多少和所需时间依赖于访问的服务类型、当前集群系统各服务节点的资源利用的情况等.负载信息主要分为两类:系统输入指标和服务器负载指标.输入指标即为周期时间内系统的平均负载量，可从负载调度器上获得，在负载调度器的计数器上记录着每个服务节点的连接数，例如对于服务节点Ni，可以收集到在T1和T2两个时刻的连接数Ci1和Ci2，因此，可以计算得到在周期时间间隔T2－T1时间段内Ni的连接数与集群内n个服务节点收到的平均连接数的比值，即为输入指标Ii，如公式(1):

服务器负载指标是指各服务节点的负载信息，例如CPU利用率、CPU就绪队列长度、内存使用情况、系统调用率、CPU进程切换率等等.如何理想地选取负载信息是整个算法的基础，它是任务分配优劣的关键，决定着集群系统的性能.前人通过大量实验，分别提出了各自观点.鉴于CPU、内存、磁盘等是系统的主要竞争资源，为LVS集群系统选取了包括服务器CPU利用率Ci，内存使用情况Mi，磁盘使用情况Di，运行态进程数量Pi，1 min内系统的平均负载量Ii五个负载指标.

不同负载信息对集群系统的影响程度是不同的，例如FTP服务对CPU处理能力及磁盘I/O速率要求较高，而HTTP服务对CPU利用率和内存使用率要求较高，如何更好地反映负载情况，引入一组系数ki来调整不同负载指标对系统的重要程度，k={0.3，0.3，0.2，0.1，0.1}，其中∑ki=1.系统综合负载可以通过公式(2)计算获得.

在系统运行过程中，可以根据系统性能的优劣，动态地调整集群系统的配置文件来合理修正系数ki的值.

2.2 反馈调节系统的设计

负载调度器是周期性通过广播信号收集各个服务节点的负载信息，所以负载调度器所记录的各服务节点的负载信息是前一个周期的负载，而不是系统的当前负载，这种“过时”的负载信息很可能导致系统负载分配的不均衡.例如，集群系统在某一时刻t0，负载调度器收集了各服务节点的负载信息，并计算得到系统综合负载.如果负载调度器在下一个收集负载信息时刻t0+T到来之前的另一时刻t1(t0＜t1＜t0+T)，到达了多个访问请求，此时系统只能依据负载调度器在t0时刻所收集的负载信息来分配新到达的请求，那么负载调度器会将这些请求相继发送给t0时刻负载最轻的同一个服务节点上，导致负载分配的不均衡.

在负载调度器中记录着各节点的负载信息，包括节点序号N、节点的当前负载LOADi、节点剩余负载能力INCLi、节点权值Wi等，其中节点序号N和节点权值Wi按照降序存放在负载信息队列中，而节点剩余负载能力INCLi等降序存放在冗余信息队列中，以便于任务分配时被使用，达到负载均衡的目的.

2.2.1 通过Wi调整系统的负载均衡

需要对服务节点设定初始化权值DEFWi，通过服务节点的权值Wi可以调整集群的负载均衡性.

(1)负载调度器的负载查询模块周期地查询节点权值，若不为零，则收集该节点的各项负载信息，并通过公式(2)计算出其综合负载值;若为零，则不会收集节点的负载信息，负载调度器将不会分配新的任务请求到该服务节点.LVS集群系统可以通过将Wi置零的方法来处理出现异常的节点，在该服务节点有响应之后，再重新设置其权值.

(2)集群系统还可以通过加权负载均值来获得集群的使用率，加权负载均值AveL可以通过公式(3)计算得到.

当负载均值AveL处于70% ～85%之间时，集群系统的使用率高，且性能好;当AveL小于70%时，可以适度地减少服务节点，节省系统资源;当AveL大于85%时，必须增加服务节点的数目扩大集群的规模，避免系统过载，以提高系统的性能.

(3)可以通过负载均值来调节各服务节点的负载均衡性，服务节点权值越大，分配的任务请求越多.定义公式(4)来实现在负载调度器上调整负载权值.

其中，k为调整步长，且0＜k＜1.通过公式(4)可以不断调整负载均值，最终使集群系统负载均衡.

2.2.2 改进算法来设定服务节点的处理能力

在集群系统中，每个服务节点的处理能力会影响着节点的负载变化，所以即使在各节点负载相对均衡的情况下，各节点可接收的任务请求的能力也会有区别.可以通过节点的剩余处理能力来衡量某一时刻各服务节点还可以接收的任务请求的负载.

负载调度器通过公式(5)可以来预测在下一个时刻每个服务节点可能接收到的任务请求负载.

其中，n为服务节点i的当前连接数.

为了达到系统的负载均衡，必须获得节点的在下一个周期能够承担的最大负载增量，以防止系统过载.

首先，系统通过公式(6)计算出节点i在某个周期中响应第k个任务请求时能够提供的最大负载maxLoadk.

其中，Dk是第k个任务请求的数据量，Δtk是第k个任务请求的响应时间，而 max(Ck，Mk，Dk，Pk，Ik)是该请求占用的最大负载利用率.

根据公式(7)可以进一歩得到节点i在一个周期内的最大平均负载利用率maxL.

其中，k取值为某一周期内任务请求的序列号，即t≤k≤n.

从而可以求出节点i在下一个周期能够承担的负载增量，如公式(8).

由此，得出在下一个周期内节点i所能承担的最大负载增量必须小于INCLi，否则会造成该节点过载.

3 结论

LVS集群服务器目前应用广泛，其利用动态反馈算法来达到负载均衡，以提高系统的整体性能.该论文在分析和研究LVS集群系统及动态反馈算法的基础之上，研究并设计了动态反馈算法，并提出新的算法来计算集群系统中服务节点在下一个周期所能承担的负载增量INCLi来设定服务节点的处理能力，以达到系统负载均衡的目的.

［1］吴培飞.用VMware构建Linux实验环境.中国教育信息化:高教职教，2011(8):56 －59.

［2］马万涛.基于Linux服务器集群安全的探讨.电脑与电信，2009(10):38－41.

［3］谭保华，查纯，张德强.基于虚拟技术和大型机硬件平台的LINUX服务器系统实现.计算机工程与设计，2009，30(5):43－45.

［4］张昊，廖建新，朱晓民.增强型动态反馈随机分发负载均衡算法.计算机工程，2007，33(4):97 －99.

［5］王晓川，叶超群，金士尧.一种基于分布式调度机制的集群体系结构.计算机工程，2002，28(3):131－133.

Dynamic Feedback Balancing Scheduling of an Advanced LVS

Yao Liying
(Heilongjing Infotech Profession College)

In this paper，the server cluster system to LVS is introduced，and task scheduling strategy of load balancing are analyzed.Based on it，the dynamic feedback balancing scheduling of an advanced LVS is designed.The new algorithm of calculating been able to bear load increment(INCLi)of the server node in cluster system at the next cycle is put forward，its purpose is getting load balancing to system.

Cluster;Dynamic feedback;The scheduling of load balancing

2011－05－11

*黑龙江省教育厅2010年度科学技术研究(指导)项目“基于Linux的校园网服务器集群系统研究”的部分研究成果(11555093)

(责任编辑:季春阳)