改进加权轮询负载均衡算法研究

韩朋花，叶青，姜晓明，陈占芳

（长春理工大学 计算机科学技术学院，长春 130022）

在云计算环境下，出现了云存储安全［1］、数据挖掘［2，3］、负载均衡［4］等技术。因为负载均衡技术能够满足人们对计算机处理速度的要求，负载均衡算法是影响负载均衡技术的重要因素之一，所以对负载均衡算法的相关研究非常重要。负载均衡算法有很多，常见的负载均衡算法可以分为两种，一种是静态的负载均衡算法，主要包括：轮询算法、加权轮询算法、目标地址散列算法、源地址散列算法等［5］。另一种是动态的负载均衡算法，主要包括：最小链接算法、加权最小链接算法、基于位置的最小连接算法、带复制的基于位置的最小连接算法等［6，7］。本文主要介绍轮询算法和加权轮询算法，通过实时监测负载因子的状态，动态的计算服务器的权值，进而对加权轮询算法进行改进，运用负载测试工具Load-Runner进行性能测试。

1 经典算法

1.1 轮询算法（Round Robin）

轮询算法是以轮询的方式，将请求分配到不同的服务器上。轮询算法的优点是实现简单，不需要记录当前的连接状态，是一种无状态的算法。

轮询算法是在假设服务器不存在差异的情况下，相对简单，不适用于服务器的配置性能不一样的情况，当请求服务器时间变化较大时，容易导致发生服务器间负载不均衡的现象。

1.2 加权轮询算法（Weighted Round Robin）

加权轮询算法是对轮询算法的改进，用权值来表示服务器之间存在的差异，权值高的服务器分配的任务多，权值低的服务器分配的任务少。

加权轮询算法解决了服务器之间存在差异的问题，实现相对简单，不需要记录当前的连接状态，是一种无状态连接。但是，权值是人为设置的，不能够动态的反应服务器之间的差异。

2 基于动态反馈的加权轮询算法

2.1 改进算法设计思想

服务器实时的负载就是一个动态的二维数据［8］，它是由服务器中负载因子的利用率和对应的权值相乘得到的。鉴于此，改进的算法思路如下：一定的时间周期内（如T=10s）收集一次服务器的负载因子的值（这些负载因子的值是动态变化的），根据收集到的负载因子的值，首先将这些负载因子的值和对应设定的阈值进行比较，在收集到的负载因子值小于对应设定阈值的情况下，计算各个服务器的处理能力极值和每个服务器的实时负载值，这两个值相比得到一个值，这个值叫做负载率。如果负载率小于负载率阈值，计算当前服务器的权值，根据权值进行轮询处理请求任务。

根据计算出的服务器的权值求出权值比，代表了服务器能够处理任务的权值比，这个比值能够很好地代表当前服务器的性能。这个比值不包含负载率大于等于阈值（Y）的服务器，根据这个比值确定服务器的权值，可以确保服务器的正常运行。

设置阈值（Y）还有一个作用，可以给负载过重的服务器一个缓冲时间，这样就能够避免这台服务器既要处理任务队列中的任务，又要接受新的任务从而导致这台服务器宕机。

改进算法工作模型如图1所示。客户端向服务器发送请求的时候，请求先被发送到负载均衡服务器，负载均衡服务器对服务器进行实时反馈负载状态（负载因子的信息），然后负载均衡服务器把请求根据权值轮询的分配到服务器，服务器处理完成请求之后，把结果直接发送到客户端。

图1 改进算法工作模型

2.2 改进算法流程

改进算法需要解决以下几个问题：①时间周期（T）是多少；②采集那些参数（负载因子）能实时反映服务器的性能；③如何采集这些负载因子；

考虑到负载因子的收集对系统来说是一种开销［9］，因此过多的负载因子反而达不到资源的有效利用，本文涉及到的负载因子为CPU的处理能力、内存容量的大小、网络带宽大小。对于时间周期来说，较长的时间周期不利于服务器的负载均衡，较短的时间周期要频繁的收集负载因子的值，影响算法的效率，所以本文的时间周期是10s（T=10s）。

在Linux系统的内核中，有一个全局变量记录时间：Jiffies（单位：10-2）。CPU的利用率根据执行用户和系统的Jiffies除以Jiffies的总数表示。

在Linux系统中，采集文件/proc/stat的第一行信息，能得到CPU的用户态、系统态、空闲态等不用状态下的Jiffies。通过命令：cat/proc/stat获取CUP的使用情况。

为了计算CPU的利用率，以时间周期的开始位置和结束位置为样点，计算它们的差值。

CPU的利用率：

其中，i表示第i台服务器（以下同理），L(ci)表示服务器CPU的利用率，Δu表示两样点之间用户态的差值，Δs表示两样点之间内存系统的差值，Δj表示两样点之间CUP利用率的差值。

在Linux系统中，采集文件/proc/meminfo的前四行信息，能得到内存的使用情况。通过命令：cat/proc/meminfo获取内存的使用情况。

内存的利用率：

其中，L(mi)表示服务器内存的利用率，memtotal表示内存，memfree表示空闲内存。

在Linux系统中，采集文件/proc/net/dev的第四行记录，能得到带宽的使用情况，通过命令：cat/proc/net/dev获取带宽的使用情况。

带宽的利用率：

其中，L(ni)表示服务器带宽的利用率，ΔR表示两样点之间接受带宽的差，ΔT表示两样点之间传送带宽的差，Δt表示一个时间周期，totalBW表示网口带宽，服务器采用eth0网口，带宽为100Mbps。

2.3 改进算法步骤

改进算法执行步骤如下：

第一步：收集负载因子的值；

第二步：将各个负载因子的值和对应的阈值进行比较，若存在L(ci)＞Y(ci)、L(mi)＞Y(mi)或者L(ni)＞Y(ni)，将这台服务器的权值设置为0，这个周期内不再对这台服务器分配任务，否则根据负载因子的权重向量T(i)计算服务器实时负载M(i)的值；

第三步：计算服务器处理能力极值N(i)和服务器实时负载率R(i)的值；

第四步：将各个服务器R(i)的值和服务器对应的阈值Y(i)进行比较，若R(i)＞Y(i)，将这台服务器的权值设置为0，否则进行下一步；

第五步：计算服务器计算权值C(i)，并根据服务器的权值W(i)计算服务器真实分配权值CW(i)的值；

第六步：计算服务器之间真实分配权值CW(i)的比，得到服务器的权值，根据这个权值轮询分配任务。

其中，Y(ci)，Y(mi)，Y(ni)分别表示服务器CPU、内存和网络的阈值，Y(i)表示服务器的阈值，N(i)表示服务器处理能力极值，M(i)表示服务器实时负载，R(i)表示服务器实时负载率，T(i)表示各个负载因子的权重向量，W(i)表示服务器的权重。

2.4 改进算法涉及公式

服务器处理能力极值：

其中，P(i)=[P(ci),P(mi),P(ni)]，P(ci),P(mi),P(ni)分别表示服务器CPU处理速度，内存大小，网络吞吐量。T(i)=[T(c),T(m),T(n)]，T(c),T(m),T(n)分别表示CPU、内存和网络的权值，且它们的和为1。

服务器实时负载的值：

其中，L(i)=[L(ci),L(mi),L(ni)]，L(ci),L(mi),L(ni)分别表示服务器CPU、内存和网络的利用率。

服务器实时负载率：

服务器计算权值：

其中，，n表示服务器数量，由于R都一样并且除法计算速度比较慢，所以上式优化为C(i)=R-R(i)。

当两个服务器的C(i)值一样时，只能代表这台服务器的处理能力，并不能代表这台服务器在所有服务器中的处理能力，为了解决这种问题，为服务器设置权值W(i)。

服务器真实分配权值：

3 实验结果及分析

通过对大量用户同时并发请求访问进行模拟，使用负载测试工具LoadRunner实时进行监测［10］，分别进行六次测试，得到改进前后的算法关于系统平均响应时间的对比，如图2。

图2 系统平均响应时间

由图2可知，改进后算法的系统平均响应时间明显提高，平均提高了140ms左右。由于改进后算法的权值是根据服务器的负载情况求出的，更能够反应出服务器的负载情况，有效的利用服务器等资源，因此改进后的算法在系统平均响应时间上得到了明显的提高。

4 结语

改进前加权轮询算法的权值是人为设定的，不能够实时反应服务器的差异。改进后加权轮询算法的权值是根据服务器运行期间负载因子计算的，是动态的改变的，所以能够更真实地反应服务器的负载差异，符合负载均衡的要求，优化了加权轮询算法，使算法得到了较大的改进。但是一定周期采集负载因子的值，会带来一定的额外开销，在今后的研究中，还需要对改进后加权轮询算法不断的改进和完善。

［1］从立钢，郭利菊.云存储系统安全技术研究［J］.长春理工大学学报：自然科学版，2014，37（03）：132-134.

［2］王鹏，王健安，郭畅，等.基于云计算及数据挖掘技术的海量数据处理研究［J］.长春理工大学学报：自然科学版，2013，36（06）：157-160.

［3］巴济慈.基于云计算的海量数据挖掘处理与研究［D］.长春：长春理工大学，2013.

［4］罗拥军，李晓乐，孙如祥.负载均衡算法综述［J］.科技情报开发与经济，2008，（23）：134-136.

［5］王以山.数字皮影表演中负载均衡问题的研究与应用［D］.北京：北京工业大学，2010.

［6］RadojevicB，ZagarM.AnalysisofIssueswith Load Balancing Algorithms in Hosted（Cloud）Environments［C］.Opatija MIPRO.2011：416-420.

［7］庄旻轩.服务器集群中基于动态反馈的负载均衡算法［D］.大连：大连理工大学，2014.

［8］张慧芳.基于动态反馈的加权最小连接数服务器负载均衡算法研究［D］.上海：华东理工大学，2013.

［9］高振斌，潘亚辰，华中，等.改进的基于加权最小连接数的负载均衡算法［J］.科学技术与工程，2016，16（06）：81-85.

［10］蔡程宇，娄渊胜.改进加权最小连接数负载均衡调度算法研究［J］.哈尔滨商业大学学报：自然科学版，2015，31（01）：102-104.