探寻负载均衡器的算法和原理

在分析了负载均衡的算法种类之后，我们现在来介绍一下动态负载均衡。主要是通过对负载均衡器的介绍，来理解这个概念。基于加权轮询的算法，我们可以扩展负载均衡的动态性能，那么，更加具体详细的解释，还是让我们浏览文章吧。

动态反馈负载均衡

当客户访问集群资源时,提交的任务所需的时间和所要消耗的计算资源是千差万别的,他依赖于很多因素｡例如:任务请求的服务类型､当前网络带宽的情况､以及当前服务器资源利用的情况等等｡一些负载比较重的任务需要进行计算密集的查询､数据库访问､很长响应数据流;而负载比较轻的任务请求往往只需要读一个小文件或者进行很简单的计算｡

对任务请求处理时间的不同可能会导致处理结点利用率的倾斜(Skew),即处理结点的负载不均衡｡有可能存在这样的情况,有些结点已经超负荷运行,而其他结点基本是闲置着｡同时,有些结点已经忙不过28来,有很长的请求队列,还不断地收到新的请求｡反过来说,这会导致客户长时间的等待,而集群整体的服务质量下降｡因此,有必要采用一种机制,使得负载均衡器能够实时地了解各个结点的负载状况,并能根据负载的变化做出调整｡

具体的做法上采用了基于负反馈机制的动态负载均衡算法,该算法考虑每一个结点的实时负载和响应能力,不断调整任务分布的比例,来避免有些结点超载时依然收到大量请求,从而提高单一集群的整体吞吐率｡

在集群内,负载均衡器上运行服务端监控进程,监控进程负责监视和收集集群内各个结点的负载信息;而每个结点上运行客户端进程,负责定时向负载均衡器报告自身的负载状况｡监控进程根据收到的全部结点的负载信息来进行同步操作,既对将要分配的任务按照权值的比例重新进行分布｡权值的计算主要根据各个结点的 CPU利用率､可用内存以及磁盘I/O状况计算出新的权值,若新权值和当前权值的差值大于设定的阀值,监控器采用新的权值对集群范围内的任务重新进行分布,直到下一次的负载信息同步到来之前｡负载均衡器可以配合动态权值,采用加权轮询算法来对接受的网络服务请求进行调度｡

加权轮询调度

加权轮询调度(Weighted Round-Robin Scheduling)算法用相应的权值表示结点的处理性能｡该算法根据权值的高低顺序并按照轮询的方式将任务请求分配到各结点｡权值高的结点比权值低的结点处理更多的任务请求,相同权值的结点处理相同份额的请求｡加权轮询的基本原理可描述为:

假设某集群内有一组结点N={N0,N1,…,Nn-1},W(Ni)表示结点Ni的权值,一个指示变量i表示上一次选择的服务器,T(Ni)表示结点Ni当前所分配的任务量｡

∑T(Ni)表示当前同步周期需要处理的任务总量｡

∑W(Ni)表示结点的权值总和｡

则: W(Ni)/∑W(Ni)=T(Ni)/∑T(Ni)

表示任务的分配是按照各个结点权值占权值总数的比例来进行分配｡

权值计算

当集群的结点初次投入系统中使用时,系统管理员根据结点的硬件配置情况对每个结点都设定一个初始权值DW(Ni)(通常根据结点的硬件配置来定义,硬件配置越高的结点默认值越高),在负载均衡器上也先使用这个权值｡然后,随着结点负载的变化,负载均衡器对权值进行调整｡

动态权值是由结点运行时各方面的参数计算出来的｡我们在实验中选取了最重要的几项,包括:CPU资源､内存资源､当前进程数､响应时间等信息作为计算公式的因子｡结合每个结点当前的权值,可以计算出新的权值的大小｡动态权值的目的是要正确反映结点负载的状况,以预测结点将来可能的负载变化｡对于不同类型的系统应用,各个参数的重要程度也有所不同｡典型的Web应用环境下,可用内存资源和响应时间就非常重要;如果用户以长的数据库事务为主,则CPU使用率和可用内存就相对重要一些｡为了方便在系统运行过程中针对不同的应用对各个参数的比例进行适当调整,我们为每一个参数设定一个常量系数Ri,用来表示各个负载参数的重要程度,其中∑Ri=1｡因此,任何一个结点Ni的权值公式就可以描述为:

LOAD(Ni)=R1*Lcpu(Ni)+R2*Lmemory(Ni)+R3*Lio(Ni)+R4*Lprocess(Ni)+R5*Lresponse(Ni)

其中:Lf(Ni)表示结点Ni当前某一项参数的负载值｡上述公式中依次表示为:CPU使用率､内存使用率､磁盘I/O访问率､进程总数以及响应时间｡

例如,在Web服务器集群中,我们采用以系数{0.1,0.4,0.1,0.1,0.3},这里认为服务器的内存和请求响应时间较其他参数重要一些｡若当前的系数Ri不能很好地反映应用的负载,系统管理员可以对系数不断地修正,直到找到贴近当前应用的一组系数｡

另外,关于采集权值的周期值,虽然很短的周期可以更确切地反映各个结点的负载,但是很频繁地采集(如1 s 1次或者多次)会给负载均衡器和结点带来负担,也可能增加不必要的网络负荷｡另外,由于采集器是在采集时刻进行负载计算的,经实验证明,负载均衡器反映出来各个结点的负载信息会出现剧烈的抖动,负载均衡器无法准确捕捉结点真实的负载变化趋势｡因此解决这些问题,一方面要适当地调整采集负载信息的周期,一般在5~10 s;另一方面,可以使用移动均均线或者是滑动窗口来避免抖动,使得负载均衡器收集到的负载信息表现为均滑曲线,这样在负反馈机制的调整效果上就会比较好｡

负载均衡器的动态权值采集程序周期性地运行,若缺省权值不为0,则查询该结点的各负载参数,并计算出动态权值LOAD(Ni)｡我们引入以下权值计算公式,结合结点的初始权值和采集的动态权值来计算最终的权值结果｡

Wi=A*DW(Ni)+B*(LOAD(Ni)-DW(Ni))1/3

在公式中,如果动态权值恰好等于初始权值,最终权值不变,则说明系统的负载状况刚好达到理想状况,等于初始权值DW(Ni)｡如果动态权值计算结果高于初始权值,最终权值变高,则说明系统负载很轻,负载均衡器将会增加分配给该结点的任务比率｡如果动态权值低于初始权值,最终权值变低,说明系统开始处于重载状况,负载均衡器将会减少对该结点分配的任务｡在实际使用中,若发现所有结点的权值都小于他们的DW(Ni),则说明当前个集群处于超载状态,这时需要加入新的结点到集群中来处理部分负载;反之,若所有结点的权值大大高于DW(Ni),则说明当前系统的负载都比较轻｡

结语

网络负载均衡是集群作业调度系统的具体实现｡由于其处理的作业单元是TCP/IP协议下的网络连接,因此可以采用面向网络连接的集中基本调度算法｡考虑集群负载不均衡的可能,采取了动态获取服务节点的权值并使用负反馈机制调整负载均衡器对网络服务请求的分布,以适应服务节点在运行过程中资源的变化｡实践证明,采用动态均衡在集群系统的整体吞吐量方面有所提高,特别是在集群各个节点性能不一,集群提供的网络服务程序所访问的资源多样化的情况下,负反馈机制的效果尤其明显｡在其他类型的集群中,负反馈机制的动态负载均衡也能够得到很好的应用,只是负载均衡器所处理的作业单元不同于网络连接,而具体的负载算法上也将有所不同｡