一种多负载状态下的自适应负载均衡算法

一种多负载状态下的自适应负载均衡算法

云计算是一种商业计算模型。计算任务分布在计算机组成的资源池中，用户可以根据需要获得计算力、存储容量和信息服务。云平台需要使用多个处理器组成一个小组来提供服务，并将网络请求分配给这些处理器，以便能够处理各种服务。如何合理分配网络请求并将其分配给不同的处理器，使没有一位处理器过于密集，而另一位处理器没有充分处理能力是负载平衡的问题。根据已有的研究成果,把分配算法按任务的分配形式可分为2大类:动态负载均衡算法和静态负载均衡算法.静态负载均衡算法依据设定的静态规则进行服务器调度,其调度结果是可确定的,典型的代表有轮转法,加权轮转法等.这类算法不必考虑各节点服务器运行时的实际负载情况,只要根据预先设定好的方案来分配任务,必然有开销小,易实现的优点.但由于每个任务占用资源不同且难以预测,各节点机处理能力不同,因此只能在一定程度上实现负载均衡,结果往往不能令人满意.动态负载均衡算法的调度结果是不确定的,在系统运行时根据各节点机当前状态产生,将新进来的请求优先分配给某种指标最优的服务器上,以此来提高整个系统的吞吐率.其较静态算法好的调度效果是以系统资源开销的加大为代价换来的.比如最少链接法(lc),加权最少链接法(w-lc),基于局部性的最少链接,带复制的基于局部性的最少链接等.针对动态异构的云计算环境,当用户的请求负载发生剧烈的变化时,不及时的负载信息采集很容易造成节点机的负载失衡.某一时刻如果有大量负载涌入,而负载表存在更新延迟,那么该指标最优的节点会在该延迟内接受大量新负载而造成负载倾斜.而且由于负载请求所消耗服务器节点资源不同,单一指标并不能正确反映节点实时负载.一些传统的负载均衡算法在集群各节点负载不大的情况下有较好效果,但不适合有大量负载产生的情况.基于目前已有的动态的和静态的负载均衡算法的优缺点,提出了一种云环境下基于服务器负载分类的负载均衡算法并进行性能比较.1高负载集合与低负载集合的匹配算法的基本思想是:系统运行期间,系统每隔固定时间采集各节点服务器的负载状况,根据采集到的信息以及负载状况,对服务器进行分类,将负载状况相差不大的节点划入一个集合之中.新任务负载到达时,根据集合的负载状况,采用一定的分配方法,使得高负载集合降低该阶段的接受的请求,低负载集合增大接受的请求,以达到负载均衡.1.1管理节点.本文的负载均衡算法建立在如图1所示的体系结构之上.其中管理节点主要负责虚拟资源管理,接收用户请求,并根据请求类型进行应用分类和计算节点以及存储节点的负载均衡处理.1.2服务器负载平台设云端计算节点集群服务器由n台组成,记为Si(i=1,2,…,n),Si当前的负载量记为Li,选取影响服务器负载的3个主要因素:CPU利用率(Ucpu),内存占用率(Umem)以及网络带宽占用(Unet),称为负载因子.则有其中a1+a2+a3=1,用来反应各因子的重要程度.对于计算集群,令Ucpu的系数最大,而针对存储集群,则可令Unet的系数为最大.构成云端集群的服务器是异构的,考虑不同服务器的性能配置差异,系统运行前为每台服务器设定一初始权值,记为ωi.显然服务器性能越好,初始权值越大.则服务器当前负载权值为Wi通过综合服务器初始能力与服务器当前的实际负载来反映当前权值.管理节点于每隔固定时间(例如15s)采集各节点服务器负载信息,并划分为3个集合:轻负载集合(LSet(Ci,i=1,2,…,k));中负载集合(MSet(Ci,i=k+1,k+2,…,m));重负载集合(HSet(Ci,i=m+1,m+2,…,n)).根据集群规模,还可进行细分,以达到更好的均衡效果.须要指出的是,采集时间间隔太短将增加额外开销,太长则不能很好地反应节点实时负载.1.3k个类属性的判断根据负载因子的状况,从集群运行过程中选出一些处于不同负载状况的个例,构成分类的训练样本,并基于分类算法,得出分类规则.训练样本示例如表1所示.用于分类的算法很多,考虑到训练样本的属性较少(只有3个)以及应用的简易性,选择了KNN(k-nearestneighbor)分类算法.KNN算法是一种比较经典的分类算法,由于其实现的简易性以及分类的准确率较高,在许多领域得到了广泛的应用.算法的主要思想是:计算待分类样本与已知的训练样本之间的距离或者相似度,找到距离或者相似度与待分类样本最接近的K个邻居.然后根据这些邻居所属的类别来判断待分类样本数据的类别,若K个邻居同属一个类别,则该样本也属于这个类别,否则,按照某种规则来确定待分类样本的类别.本算法中采用欧氏距离来确定样本间的相似度.欧氏距离的公式为式中:i=1,2,3为选取的样本属性的个数;xi为待分类样本的属性,本文分别为Ucpu,Umem,Unet;yi为对应的训练样本的属性.为了达到较好分类效果,K的值可根据实验不断修改.考虑到云端计算节点集群和存储节点集群对于不同的属性重要程度不同.例如,计算集群的Ucpu和存储集群的Unet的重要度最高,针对不同请求,可在计算距离时,为其加权.另外,为防止KNN算法在训练样本各个类别数量上的不平衡造成的误分,在选取训练样本时应尽量满足各个类别的数量相差不大.每当负载均衡调度器采集到集群中各节点的负载因子的信息时,使用KNN算法依次计算各节点到已知的样本间的距离,得到距离最近的K个样本的归类,然后选取类别最多的一类为该节点当前的类别.令类别属性0表示LSet,1表示MSet,2表示HSet.算法过程如下.输入训练数据集E={Xi,Yi},Xi为训练数据属性集,Yi为类别属性.新样本为Z(即采集到的某一节点的负载因子状态).欧式距离D,M为训练样本数量,N为采集到的负载信息数量.计算Z和Xi的距离.对计算的距离进行排序,得到D(Z,X1)≤D(Z,X2)≤D(Z,X3)≤…≤D(Z,XM).输出选择排序后的前5个样本,统计每个样本的类别属性出现的次数,将出现次数最多的类别属性定为新样本Z的类别.1.4基于约束的负载均衡服务器分类完毕后,将该阶段所有负载均分配到LSet和MSet之中.a.对于处于重负载HSet集合之中的节点,为了防止集群负载发生倾斜,节点过载影响集群吞吐率,在下一阶段分配任务时不予考虑.若集群中所有节点都处于HSet中,则说明整个云端集群处于高负载状态,须要增加物理资源或者暂时停止接受用户请求.b.由于处于相同集合内的节点,服务器负载波动幅度不大,因此可近似看作处于均衡状态,此时只须考虑服务器的初始能力,按照静态的轮转法进行任务分配.指示变量j表示上一次选择的服务器,c表示当前调度的权值,max(S)表示S中节点的最大初始权值,gcd(S)表示S中初始权值的最大公约数.计算开始时,j=-1,c=0.算法如下:由算法可知负载将更多的流入初始权值ωi大的节点.c.对于LSet和MSet2种集合,集合间的节点负载差距较大,须做均衡处理,让更多的负载流入LSet之中,以减低MSet的负载加大LSet的负载以达到集合间负载均衡.令P为负载交给LSet处理的概率,LSet集合的节点数目为x,MSet集合的节点数目为y.根据式(1)和(2)有式中:节点j∈MSet;i∈LSet.根据式(4)可知:负载交给MSet处理的概率为1-P,新进负载将根据各集合节点数目,更多交由处于LSet集合中的节点处理.d.若LSet为空或者MSet为空,则说明除了重负载节点,其他节点均处于同一集合中,这些节点均衡性良好,继续按照加权轮转法轮转分配任务即可.分配示意图见图2.当根据算法找到合适的物理机时,便输出给执行模块进行部署和执行.由以上讨论可知:基于服务器负载分类的负载均衡算法能很好地解决一些传统算法按某种指标最优来分配负载带来的负载倾斜以及节点过载等现象,并沿用了加权轮转在负载相当情况下的优良性.将负载更多地分配给指标最优的一组服务器集合来分摊,同时降低高负载节点在下一阶段接收的负载,以达到云端集群负载均衡.同时若集群节点都处于一个集合中,则说明负载均衡度良好,只需继续按照加权轮转法分配直到下一采集阶段时刻到来.2并行测试与分析为测试算法效果,在实验室由LINUX操作系统搭建的云平台的计算集群(体系见图1)下进行最少链接法和本文中的算法的比较测试.选取5台异构机器作为服务器,由管理集群进行负载均衡调度并于15s一次采集节点信息.KNN分类算法中K取3,训练样例采用实验室云端集群长时间运行得到的样本,样本数量选择20个,3个类别属性的个数分别为7,7和6.由于针对的是计算集群,因此根据式(1),取CPU得系数为0.5,内存系数为0.3,网络带宽系数为0.2(存储集群同理).一台云客户端利用工具Webapplicationstresstool对云端管理集群进行4组持续5min的并发连接模拟测试,并发连接数(connNum)分别为100,200,300和400.由此得到lc和本文算法关于吞吐率(requestspersecond)和平均响应时间(ttfb)的比较结果,分别如表2和表3所示.由表2和表3可以得出:2种算法在中低负载下效率相差不大,但当负载逐渐增大时,本文算法的优点便显现出来,由采集和分类所带来的开销被算法提升的效率所抵消.可以预见,当集群规模扩大时,算法