分布式环境中高效动态负载均衡策略研究

分布式环境中高效动态负载均衡策略研究

1负载均衡策略随着计算机和网络技术的发展，分布式网络系统为用户提供了丰富的资源集合，这使得它越来越受用和广泛。随着研究的深入,人们注意到在一个由网络所连接起来的多计算机的分布式环境中,在某一时刻,一些计算机的负载极重,许多任务都处于等待状态,而另外一些计算机却极为空闲。所以,采取有效的策略来平衡各节点(分布式环境中的节点机)的负载,提高整个系统资源的利用率及系统运行效率,已成为人们的研究热点。通常,负载均衡策略由四部分组成:(1)信息收集,收集和维护系统负载状态等信息;(2)选择,哪些任务由哪一个节点来完成;(3)均衡发起,包括源主动/服务器主动策略;(4)协商,分布式系统中的节点间需要通过协商决定负载迁移等问题。这几部分可以总结为四个关键问题,即负载的分配、负载状况的定义、负载探测以及均衡策略。其中均衡策略尤为关键,它决定整个均衡负载操作的效果,从而决定整个分布式系统的计算效率、快速响应能力和系统吞吐能力的高低。2节点生成及负载均衡负载均衡策略可以分为资源负载均衡策略和发送者、接收者启动策略等。资源负载均衡策略中包括Bryant和Finkel提出的动态局部物理分布策略,这个策略采用启发式方法达到负载均衡,但这种方法每个节点都要对其他节点进行遍历,会导致大量系统内部通信,请求消息的复杂度为O(n2);Barak和Shiloh提出的全局动态负载均衡策略,这个策略属于协调算法,每个节点维护其他节点的负载信息,随时更新,某一节点A负载过大时,向估计响应时间最小的节点B迁移负载。这个策略是全局最优的,需要获得全局的信息,通信量依然较大,而且当采集到过时信息时,该策略失效。发送者启动策略是由D.L.Eager等人提出的,这个策略由创建任务的节点来执行节点间的任务调度分配。至于分配给哪个邻接节点,则主要取决于邻接节点的负载状态,因此,该策略需要交换节点的负载信息。使用该策略时,系统在运行时不会被空闲节点所打扰,这一点在系统整个负载较低时尤其重要。但是负载过重的忙节点还要额外增加处理负载平衡调度的负担,就这一点来说显然不太合理。M.Livny等人提出的接收者启动策略是由空闲节点逐个向邻接节点请求任务,如果请求到任务,则终止请求,否则继续询问下一个相邻节点。如果所有相邻节点都没有满足请求,则请求节点等待,过一段时间后再向相邻节点发出任务请求。该策略不需要相互交换负载信息;对于大规模并行计算问题,当每个节点均处于忙状态时,几乎不需要额外调度开销;负载均衡的许多工作由空闲节点来完成,没有给忙节点增加许多额外负担。但是在开始和结束阶段时任务数相对较少,许多任务请求会延迟忙节点的执行,而且逐个地请求任务会给相邻节点带来一定的干扰。资源动态负载均衡策略虽然简单,但是系统内部通信量大,且计算复杂度比较高。发送者启动策略适用于整个系统负载较低的情况下,而接受者启动策略正好与发送者启动策略相反,比较适合在大规模并行计算等负载较高的系统中使用,这些问题都可能成为提高整个分布式系统运行效率的瓶颈。3常态负载均衡策略针对上述问题,提出一种新的策略,即基于启动者动态改变和阈值自适应的动态负载均衡策略,简称SRLB策略。下面从分布式系统的结构、动态负载均衡模型、阈值的自适应方法以及启动者动态改变策略四方面来解决基于SRLB策略的负载的分配、负载状况的定义、负载探测以及均衡策略的相关问题。3.1基于道德风险的负载探测技术分布式系统的结构可以分为两种:集中式结构和分布式结构。集中式结构是由一个中心节点来收集所有节点的负载信息,每个节点都向中心节点提交负载信息,中心节点响应各消息,因此中心节点不可避免地由于频繁上下文切换、中断的分发与处理而成为系统瓶颈。而分布式结构不存在这样的问题,但是分布式调度中没有全局的负载信息,不利于进行负载的探测。由于发送者启动策略适用于整个系统负载较轻的情况,需要进行均衡调度操作的概率相对较小,因此比较适合采用集中式结构,而接受者启动策略适用于整个系统负载较重的情况,需要频繁地进行均衡调度,一般使用分布式结构。SRLB策略采用启动者动态改变方法,即根据整个系统当前的负载状态来决定使用接受者启动策略或发送者启动策略,为适应这种启动者动态改变的方法,采用的分布式系统结构综合了集中式和分布式结构,称之为MIXS结构,如图1所示。MIXS结构拥有一个集中式结构式的总调度中心,并且它将所有节点进行分组,每一组中都包含一个组调度中心,总调度中心只与组调度中心进行负载信息的交互,而各节点向自己所属的组调度中心提交负载信息,因此总调度中心只需要维护所有组调度中心的信息,组调度中心只需要维护本组节点的信息,需要维护的信息量大大降低了;MIXS结构拥有信息集散节点——调度中心和组中心节点,能够方便地进行负载的探测;为了均衡各组的负载,将N个节点分成lbN组,尽量将负载小的节点与负载大的节点划分为一组。3.2组调度中心信息交互动态负载均衡模型是整个分布式系统进行负载分配、负载探测和负载调度的总蓝图。SRLB策略的动态负载均衡模型如图2所示。在图2的模型中,设置了通信模块,通信模块并不是唯一的,每一组节点都拥有一个通信模块,各个通信模块之间相互独立。总调度中心通过通信模块与各组的组调度中心进行信息交互。通信模块担当总调度中心和组调度中心之间进行信息传输时的缓冲器角色,当总调度中心将任务分配和调度信息发送给组调度中心时,如果此刻组调度中心处在忙状态,不能及时响应总调度中心的消息,总调度中心就先将有效信息存入该节点组的通信模块,这样就将总调度中心需要完成的任务进行了分流,将需要等待一段时间才能完成的工作由通信模块来完成。在总调度中心和组调度中心中含有的全局知识库和组知识库,它们是系统运行期间,对各个组和组中的各个节点的负载能力进行学习而建立起来的,如表1和表2所示。知识库中存储了一些通过学习得到的数据,如某个时间段某个节点处理任务的速率与能力,这对提高系统的效率有很大的帮助。任务等待队列是等待节点执行的任务。当节点的负载超过了一个阈值时,节点就将一部分任务转到任务转发队列中,然后通过组调度中心节点将任务转发给其他空闲或负载较轻的节点去执行。3.3常用的自适应策略在一个分布式系统中,任何节点都可以用一种方式来抽象地描述其处理能力,例如用P来代表该节点的能力值,而阈值是一个临界值,令其为L(L<P),在当前节点的实际负载E比L大时,判定为超载节点,反之为轻载节点,E与L之间存在如下函数关系:函数F(Lue0a8Eue0a8λ)表明了在超载、轻载和负载适中三种情况下L和E之间的关系,函数中λ(λ<1)为影响因子,因为在系统实际运行中,有一些系统必须运行的任务,如操作系统的运行和网络信息的维护等,这些任务也是节点实际负载的一部分,所以节点真正的任务负载小于实际负载E。当负载阈值采用动态方法确定时,称为自适应方法。因为SRLB策略采用的均衡策略为动态改变的策略,所以阈值的自适应方法不能根据均衡策略来实现。所以这里的阈值自适应方法根据节点机各项资源的利用率进行分层自适应改变,这些资源分别为CPU、内存(Mem)、网络带宽(T)、I/O、缓冲区(SC)。称该方法为资源分层阈值自适应方法。分层结构如表3所示,该分层方式以及硬件使用率是依据组成计算机的各个主要硬件之间不同的性能标准制定的。由于该标准是硬件生产厂商指定的统一标准,所以使用该标准能够保证实验的结果精确性和准确性。表3中α为阈值动态改变因子,阈值是整个系统处理任务的平均能力值,α的值是通过对节点某一时间段各项资源的利用率进行综合计算得到的。设CPU、内存、网络带宽、I/O、缓冲区的平均利用率分别为C1、C2、C3、C4、C5,则α为:公式(1)中hk和hp分别表示当前节点的负载量和整个系统的平均负载量,表3中α值是在设hk=hp的情况下得到的。α的值不能小于10%,因为α≈0⇒L≈0,这使得hk>L的概率几乎为100%,系统频繁地进行均衡操作,将引起缓冲区负载抖动现象和大量的内部通信。通过公式(1)便实现了阈值变化因子α的动态改变。而通过α的动态改变可以给出节点负载状况的定义,即表3中的State字段值,分别为:LRL(Lighter-load)、LL(Light-load)SL(Strong-load)、SRL(Stronger-load)和FL(Full-load)。根据这五种状态,动态决定采用哪一种启动者策略。3.4作者的动态改变策略3.4.1基于主动索引方式任务的分配策略采用主动索取与调度中心发送相结合的方式。当有一批需要完成的任务到达总调度中心时,总调度中心给每一个组调度中心发送一个任务到达的标识F,组调度中心将F与自身的MAC地址捆绑后作为标识G传递给组成员,组成员得到G后根据节点自身状态自主决定采用主动索取方式还是调度中心发送方式。如果采用主动索引方式,就是由节点发出请求,请求的任务量由节点决定,只有在节点多次进行任务处理的任务量大小差距比较大,知识库中学习到的数据不是很稳定的情况下采用这种方式。如果采用调度中心发送方式,须在发送之前通过知识库计算出每个节点机的负载潜力,计算公式如下:公式(2)中的R为平均任务量(如果将总任务平均分配给所有节点的任务量),S为知识库中处理能力的平均值,当知识库在Ti时间段的处理速率为Vi,在的情况下,令其中n为知识库中分的时间段的数量。公式(2)中的(R/S)2表示将当前系统的平均任务量作为一个影响节点负载潜力因子,因为当总任务量很大时,负载潜力也必须相应地变大。δ是一个随机小数,0.8£δ<1,作用是稍微降低节点的负载潜力,因为S的值并不是真正处理任务的能力,它还包括处理操作系统的进程和维持网络连接等其他任务,所以要稍微降低节点的负载潜力。3.4.2总调度中心优化分配策略根据D.L.Eager等模拟实验结果表明,当整个任务负载较重时,接收者启动策略效率更高,反之发送者启动策略更高。所以SRLB采用动态的启动者策略,设定一个资源利用率监视器,当整个系统资源利用率高时,说明系统的负载较重,采用接收者启动策略,反之采用发送者启动策略,如表3所示。策略的变换完全由总调度中心来发起,总调度中心通过对各个组调度中心发送来的资源利用率数据进行综合分析,将分析结果与表3中的标准进行对比,从而确定系统是否改变策略。具体步骤如下:(1)总调度节点在分配任务时,根据任务量决定初始启动者策略。(2)当系统发生任务迁移,总调度中心给各个组调度中心发送资源利用率监测信号,组调度中心接收信号并转发给组成员。(3)组成员接收到信号后将各项资源的利用率发送给组调度中心,组调度中心将接收到的各个组成员的资源利用率进行汇总与分析,得到一个平均值发送给总调度中心。(4)总调度中心根据各组的资源利用率决定启动者策略。4pc机群的划分与任务为了得到稳定实验结果,在一个局域网环境中,由12台不同配置(为了产生任务的迁移)的PC机组成的计算机机群进行实验,其中有6台PC机的CPU为2.0GHz,内存大小为512MB,其中5台作为总调度中心和组调度中心,有2台PC机的CPU为1.7GHz,内存大小为512MB,2台PC机的CPU为1.7GHz,内存大小为256MB,剩下的2台PC机的CPU为1.0GHz,内存大小为256MB。将PC机群分为4组,各组的PC机数量分别为4台、3台、2台、2台。实验分3次进行,每次实验均提交100个相互独立的子任务。每次实验的子任务内容如表4所示。实验采用发送者启动策略、接受者启动策略和启动者动态改变策略分别进行,得到的实验结果如图3所示。由实验结果可知,当任务负载量适中时,三种策略的效率基本相同;当任务负载较轻时,发送者启动策略与启动者动态改变策略要优于接受者启动策略;当任务负载较重时,接受者启动策略与启动者动态改变策略要优于发送者启动策略。可见,启动