进程迁移自适应动态负载平衡算法的研究与实现

陈彬玫, 徐 虹

(成都信息工程学院计算机学院,四川成都610225)

0 引言

进程迁移是实现负载平衡的基础,包括迁移机制和迁移策略两个部分。迁移机制是指进程迁移的具体实现,迁移策略是前期的准备,包括负载向量管理和分布式调度两部分内容。传统的进程迁移研究大多集中于进程的迁移机制,对进程的迁移策略关注较少[1-4]。进程迁移是系统动态适应负载变化的最佳机制[1],但实现这个过程是有代价的[5-6]。例如,进程迁移开销会加重已经过载的服务器;迁移后的进程可能离开本身具有亲和性的缓存和资源;负载的瞬时变化和负载延迟扩散会造成进程迁移颠簸[6-7];短期进程[5]或者churn服务器不应作为迁移的选择目标等。因而需要实现高效、稳定的迁移策略。

进程迁移策略的研究主要集中在负载平衡的信息、调度、位置、选择、接受和决定等策略[1,6-8]。其中,信息策略是其他策略的依据,是整个进程迁移策略的核心和基础。关于信息策略,已有成果主要关注于负载向量(Load Vector)的表示、收集、传播等,很少重视信息策略中负载向量的可靠性问题,特别是对瞬时变化和采集噪声的考量。例如,文献[10]在负载收集过程中使用自适应双阈值策略,有效降低了系统通信开销。文献[6]在迁移权衡中使用负载阈值作为进程是否需要迁移的指标,文献[9]提出阈值和阈长结合的动态反馈调整自适应算法,但阈值策略只能对迁移决定作出有限平衡。文献[5]使用进程剩余生命时间作为负载向量表示,由于不能反映进程的外部资源依赖,使用范围有限。

负载信息的可靠性和准确性会严重影响进程迁移系统的适应性和稳定性[1,6-8]。已有系统实现在使用负载向量时大多采用延迟响应和加权负载的经验性折中策略,例如文献[5]使用1分钟时间内的平均负载,文献[8]使用当前时刻系统负载和前一时刻的系统负载的加权求和,文献[11]使用连续两次的负载值确定负载是否突变。而这些策略都不能很好的跟踪系统的负载变化情况,特别是负载瞬时值在较大的峰谷之间颠簸的情况。因此,针对进程迁移策略中的负载计算问题,提出了一种自适应的动态负载平衡(Adaptive Dynamic Load Balancing,ADLB)算法,通过等比计算缓存负载分量的历史实现均值平滑,通过平均偏差实现峰谷平滑,通过源负载曲线和目标负载曲线的平滑确定迁移关系,为迁移决策提供更准确的依据,从而实现运行时自适应智能调度。

1 进程迁移策略

区分机制和策略是一种重要的设计模式,迁移机制和迁移策略的关系如图1所示。

进程迁移策略是迁移机制的前提和依据,包括负载向量管理和分布式调度两部分内容[1]。负载向量管理通过对整个系统中资源进行抽象,筛选系统需要的负载向量,通过一定机制收集、计算和分发,实现全系统共享,为系统管理以及策略制定提供服务。分布式调度策略根据负载向量管理模块通告的负载信息考虑什么时候(when)迁移哪个进程(which)到哪台机器(where)。所以调度过程是通过两次协调实现:首先是负载向量共享确定when、which和where的迁移关系,继而通过发起者和接收者的协商实施迁移。迁移机制是进程迁移的具体实现,接受调度策略的指令,实施迁移。迁移过程依赖于具体的操作系统环境,需要应用程序和内核的配合、修改内核数据结构和增加系统调用,实现难度较大。

从图1可以看出,在以进程迁移为目标的系统平台上,负载向量的表示、收集和计算是进程迁移的起点,进程迁移策略是进程迁移的指令发出者,决定整个系统的适应性和稳定性[1,6-8]。适应性关注迁移策略对系统的影响。由于进程迁移本身就是对系统负载变化的适应,调度算法需要适应不同主机负载、网络负载和权重参数的变化。适应性本质上是要求迁移策略对负载变化感知的灵敏性。稳定性关注系统是否具备预测下一步行动效果的能力。在分布式系统中,不稳定是绝对的,稳定是相对的。但是,不稳定性必须限制在尽量小的程度内或者稳定程度尽可能达到折中。例如进程迁移的颠簸反而对

系统的稳定性带来负面影响;在负载很高的系统中最好的办法是无为而治。稳定性本质上是要求迁移策略对负载变化感知的迟钝性。

总之,进程迁移策略关注进程迁移动作的实施是否有效[7]。最佳的解决方案是很难实现的,常用的策略是用一个子集来逼近整个搜索空间或利用启发式达到次优的解决方案。

图1 迁移机制和迁移策略关系图

2 ADLB算法与实现

2.1 基本思想

获得可靠负载的有效方法是对系统一定时段的历史负载和当前负载进行加权计算。根据负载信息产生特点,时间历史越久的负载越没有参考意义,所占权重应该较少。当前负载是需要均衡的负载,要重点考虑,同时也要考虑瞬时的负载噪声。在这个负载的跷板上,历史负载影响太重,系统响应迟钝,当前负载影响太重,系统反应灵敏,但决策可能盲目。因此,ADLB算法通过两个步骤获得更为可靠的负载计算结果。

第一个步骤获得当前时刻以前的负载状况的加权均值。算法并不在内存中保留进程运行以来的所有历史负载记录,而是通过等比级数作为权重对系统运行以来所有负载值按照时间逆序加权求和作为当前负载值。加权采用等比级数方法是为了有效利用2进制数的优点。例如,历史负载的权重为:当前负载的权重为:其中m∈N,1≤n≤2m,且可以根据系统实现需求进行调整。由此,用 Ai表示时间线上各点采集到的当前负载信息,Ti表示时间线上各点加权求和后的平滑负载值,m取3,n取1,则各个时间点的负载计算过程形成如下序列:由序列可见,加权计算存在3个关键:(1)负载值的影响按照时间线前进的反方向等比下降;(2)当m值确定时,n值越小,当前负载值的权重越小,历史的权重越大,反之相反;(3)m、n可以根据需要采用不同的值。

第二个步骤仍然采用如上加权均值的方法,但计算的对象是当前采集到的瞬时负载值偏离第一步骤获得的加权均值的程度。这需要引入负载序列的标准差和平均偏差。在工程应用上,都认为平均偏差是对标准差的一种好的逼近,并且避免了标准差的开方操作。例如,RTCP协议中抖动值的计算和TCP协议中超时重传机制的实现都使用了平均偏差。文献[12]也给出平均偏差(d)和标准偏差(σ)存在如下关系:σ≥d≥0,因而可以使用平均偏差代替标准偏差。标准差和平均偏差的计算公式分别为:

上述两个步骤获得的负载值之和即是决策依据负载。两个步骤都是必要的,仅通过第一个步骤获得负载值作为迁移依据,无法准确跟踪负载当前的瞬时变化,失去负载感知的灵敏性。在第一步骤的均值中强调 n取较小的值以最大可能考虑历史,最后的负载值使用第一步骤的均值和第二步骤的标准差之和,可以削弱瞬时高负载,补偿瞬时低负载,有效保证负载统计的稳定性。

2.2 算法实现

2.2.1 历史负载平滑

取g为影响历史负载权重的因子,A为经过平滑的负载值,M是实际测到的负载值。计算公式为:

为了编码实现方便,g采用2的乘方,这样计算时只需要移位操作而不需要乘除运算。从(1)式可以看出,历史负载值随着时间的流逝,通过等比的关系逐渐减小,对负载平衡时总负载的计算的影响也逐渐减小。

2.2.2 峰谷负载平滑

上一步操作中,A的效果相当于平均值,M-A就是负载瞬时值的峰谷范围。计算公式为:

然后引入峰谷负载平滑因子h和平均偏差D,如果要对负载变化敏感,可以设置较大的h,将会使得负载值快速上升。计算公式为:

2.2.3 负载计算

综合式(1)和(3),得出的负载值计算公式如下:

2.2.4 迁移权衡

系统中迁移源节点和迁移目标节点之间定义了一对迁移关系。进入迁移临界窗口的节点,在迁移窗口内变化幅度(绝对值)之和最大的节点作为一对潜在迁移关系。为了平滑迁移关系,源节点取当前负载值和平滑负载值的最小值,目标节点取当前负载值和平滑负载值的最大值。计算公式为:

虽然负载值已经经过平滑,但还可以引入迁移临界窗口规定系统必须迁移之前处于高负载的最长时间和系统可以接受迁移进程之前处于低负载的最长时间。当然,迁移权衡要结合其他策略,例如,节点和进程的生命时间作为权重是必须考虑的,系统的迁移临界点可以使用阈值和阈长结合策略[9]等。

2.3 平滑证明

设相邻两次负载为:

两次负载的比值为:

随着因子g、h的增大,两次负载的比值接近1。

两次负载的差值为:

随着因子g、h的增大,两次负载的差值接近0。

综上,随着 g、h的增大,负载曲线趋于直线。

2.4 算法伪代码描述

(1)float load=0;//表示平滑后的负载均值

(2)floatmdev=0;//表示平滑后的负载峰谷

(3)接受新得到的负载测量值m

(4)If(采样值m有误) then

(5)m=1;/*异常处理*/

(6)Endif

(7)If(不是第一个负载采样) then

(8)m-=load;

(9)If(m＜0) then

(10)load+=(m ＞＞1);//放大

(11)m=-m;/*m取绝对值*/

(12)Else

(13)load+=(m ＞＞3);//缩小

(14)Endif

(15)m＞＞=2;

(16)mdev-=(mdev＞＞2);

(17)mdev+=m;

(18)Else/*第一个采样*/

(19)load=m;/*设置初值*/

(20)mdev=0;

(21)Endif

根据上述代码,load与mdev之和即为平滑后的整体负载。

3 系统模型及性能分析

3.1 系统软件模块栈

系统基于linux同构集群平台,采用从下到上分层的栈结构组织进程迁移的主要功能模块,在节点之间存在3条主要消息通信分别对应栈结构的3个主要层次。各个模块的主要功能如图2所示。

负载管理模块区分负载向量的内容、权重和粒度。根据任务的性质,负载向量的内容为3种类型:CPU密集型、内存密集型和I/O密集型,I/O类应用又分为磁盘I/O和网络I/O。磁盘I/O通过分布式文件系统实现,包括:文件共享、文件复制、文件迁移等,采用的负载分量包括磁盘利用率和磁盘空间大小,文件描述符打开的对象区分网络(NFS)还是磁盘(RAID)等。网络I/O以软中断为主要指标,包括消息请求和数据传输,通过注册数据端口和服务端口区分,采用的负载分量包括网络流量、网络带宽和软中断频率等。管理员可以根据应用需求设定各个应用的权重,也可以通过系统统计负载历史感知应用主要依赖的资源,还可以预测进程和节点的剩余生命时间,自适应的调整权重分配。另外,针对前述负载分量,系统分别统计节点和进程两个粒度的负载信息。

图2 系统软件模块栈

表1 典型负载变化测试数据

负载向量收集和传播的方式主要有周期性和事件触发两种,事件包括:进程创建、终止、迁移。在设计的实现方案中,负载向量传播内容认为是固定的数据结构,传播策略采用周期加事件触发的方式,周期时间较长。为了既能及时在系统的各个节点之间传递信息,又平衡收集开销,引入负载更改阈值[10],当负载的变化超过该值时,触发负载推送到各个节点。当负载的变化不超过该值时,信任已有负载值,不收集负载。系统在迁移权衡时使用两个主要的阈值,迁移临界点和迁移临界窗口。迁移临界点采用阈值和阈长[9]表示系统需要转移负载的临界范围。迁移临界窗口则表示系统必须迁移之前处于高负载的最长时间和系统可以接受迁移进程之前处于低负载的最长时间。另外,系统对进程适合迁移以及节点适合迁出和迁进进程的最小运行时间也给出了阈值。

迁移协商采用两阶段的方式,需要迁移双方对迁移的开始和完成分别作出确认。另外启动策略采用对称启动方式,并限制一对节点运行时只能有一对迁移关系。为了避免进程迁移泛滥和掠夺[8]的群聚效应(Herd Effect),在迁移开始之前把确定的迁移关系传播给系统内其他节点。

迁移实施主要基于linux环境下checkpoint-restart实现。

3.2 测试方案

根据系统实际运行过程中的负载变化,考虑4种典型的负载变化趋势:(1)负载持续递增:模拟了适应访问人数逐渐增多的互联网应用;(2)负载持续递减:模拟适应访问人数逐渐减少的互联网应用;(3)负载以类似正弦的方式波动变化:模拟典型的周期运行daemon进程负载变化;(4)负载随机变化:模拟系统负载随机变化的情况。

分别在上述4种情况下对系统负载平滑效果进行测试,统计实际值和平滑值的情况。测试数据如表1所示,上述4种情况分别对应表中1、2、3、4项。图3～6分别直观的显示4组数据中负载值的平滑情况。由4种测试结果可以看出,算法有效的跟踪了负载变化,并实现了负载平滑。进程迁移是有开销的,因此应当采用尽量不迁移的原则。例如,只有负载持续递增的主机,在迁移关系的选择时才会被选中,偶然一次的高负载并不会引起其上的进程迁出。相应的,只有负载持续递减的主机,才能成为其他过载主机的迁入目标。

图3 负载递增实验数据

图4 负载递减实验数据

图5 负载正弦波动实验数据

图6 负载随机变化实验数据

4 总结

针对进程迁移中负载信息计算的可靠性问题,提出ADLB算法,有效的解决了负载变化抖动问题。系统在运行时采集并计算平滑负载,自适应系统负载的变化,并结合其他权重因素,动态迁移进程。

负载向量的管理不是进程迁移所特有,也不专用于迁移调度,几乎所有实现动态负载平衡和任务调度的系统中都要涉及。负载向量的计算方法也可以用于其他计算环境,并可以根据不同目标,收集不同的负载分量。由于算法的通用性,对于其他平台也有借鉴意义。

下一步工作是在目前工作的基础之上研究多目标(I/O、MEM、CPU)调度决策问题。

[1] Dejan S Milojici,Fred Douglis,Yves Paindaveine,et al.Process migration[J].ACM,2000,32(3):241-299.

[2] Balazs Gerofi,Hajime Fujita,Yutaka Ishikawa.An Efficient Process Live Migration Mechanism for Load Balanced Distributed Virtual Environments[C].Cluster 2010;IEEE International Conference on Cluster Computing,2010.

[3] Amirreza Zarrabi.A Generic Process Migration Algorithm[J].International Journal of Distributed and Parallel Systems(IJDPS),2012,5(3):29-37.

[4] Chandu D Vaidya,M B Chandak.Efficient Parallel Process Migration Algorithm Using Statistical Approach[C].Fourth International Conference on Computational Intelligence and Communication Networks,2012.

[5] 张永坤,金海,唐丹.一种基于进程剩余运行时间总和的集群动态负载平衡算法[J].计算机工程与科学,2005,27(5):63-65.

[6] 蒋江.异构集群系统中基于进程迁移机制的负载平衡算法的研究[D].长沙:国防科技大学研究生院,2002.

[7] 韩海军.无中心集群下基于进程迁移的负载平衡研究[D].沈阳:沈阳理工大学,2007.

[8] 迟忠惠.基于进程迁移的负载均衡算法的研究[D].青岛:中国海洋大学,2005.

[9] 周佳祥,郑纬民,杨广文.一种基于进程迁移的自适应双阈值动态负载平衡系统[J].清华大学学报,2000,40(3):121-125.

[10] 胡金柱,徐松.分布式系统中一种负载平衡的动态反馈调整自适应算法[J].小型微型计算机系统,2003,24(8):1510-1515.

[11] 刘学伟.基于linux进程迁移的设计与应用实践[D].成都:电子科技大学,2008.

[12] 韩兆洲,杨林涛.极差、平均差和标准差之间测度关系研究[J].统计与信息论坛,2008,23(4):5-8.