云计算环境下的负载运行问题研究

云计算环境下的负载运行问题研究

0节点负载度调度算法云计算是一种分布计算、并行计算和网格计算的综合开发。它的核心是将大型数据处理数据的计算资源虚拟化，并向用户提供以计算资源为形式的服务。云计算实现了按需计算,它的出现使普通用户也能使用高性能并行计算,提高了工作效率和计算资源的利用率。目前,大多数云计算环境根据用户的支付来分配资源,但调研结果显示,云平台在任务调度和资源分配的时候可能出现负载不均衡的情况。这主要是因为任务的多样性和调度算法没有处理好节点的负载和任务分配的关系。常用的调度算法有:Min-min(minimum-minimumcompletiontime)、Max-min(maximum-minimumcompletiontime)、TD_Min-min(trust-drivenminimum-minimum)和TD_Max-min(trust-drivenmaximum-minimum)等,这些调度算法或者将最小最早完成时间的任务调度到对应的资源上、或者将最大最早完成时间的任务调度到对应的资源上、或者选择信任效益值最小的节点进行调度、或者选择信任效益值最大的节点进行调度。如果那些不能胜任的节点或者负载过重的节点被选中,会大大降低系统的执行性能。本文针对云计算系统中可能因负载不均衡而造成的系统效率低下的问题,根据节点的负载度区分节点状态,划分为正常负载、轻度过载和重度过载3种状态。针对轻度过载和重度过载的情况,分别设计了相应的过载避免和快速均衡的策略,使轻度过载的节点能够尽量避免重度过载,重度过载的节点能够快速恢复到正常负载。每个节点定期检查自己的负载度并判断其负载度所处的状态,根据负载度的状态自适应地选择过载避免或快速均衡策略,这样能保证云计算系统的负载均衡和高效执行。1基于移动代理的负载均衡策略云计算中的负载均衡策略大体可以分为静态和动态两种。静态均衡策略是利用简单的系统信息,例如子作业数量、平均作业执行周期等,通过数学函数调度算法来选择节点,从而分配、执行任务。这种策略实现简单,但不能够动态地调整系统中节点信息的变化,因此一些节点利用率很低。云计算中典型的静态负载均衡策略是基于预测的,如基于遗传算法的负载均衡策略,它根据节点的当前信息和历史信息对节点的未来进行预测,有选择性地进行节点调度和任务分配。但这种策略首先要给出合理的预测标准,并且对节点信息的收集也是一件繁琐和耗时的事情。文献针对云计算环境设计了一种基于回填策略的两级调度器,实现了负载均衡和服务质量保证。该算法提出元调度和回填策略两级调度,在不造成其他作业延迟完成的情况下,允许小作业在元调度队列中向前移动,即回填;并根据作业的服务质量要求和资源限制选择系统资源、安排任务的处理顺序实现负载均衡。文献在一个3级云计算网络中,融合OLB(opportunisticloadbalancing)和LBMM(loadbalancemin-min)两种算法进行负载均衡,并利用移动代理来收集节点信息。动态负载均衡策略根据系统当前状态或最近状态去决定如何给分布式系统的每个节点分配任务。如果系统的一些节点任务超载,这个超载任务将被转移给其它节点来处理,从而达到动态均衡的目的。但是,任务的转移将给系统带来额外的负担。云计算中典型的动态负载均衡策略是通过虚拟机的迁移来实现任务的转移。文献面向云计算提出一种基于虚拟机实时迁移的自适应负载均衡算法,通过共享存储降低虚拟机的迁移时间,并通过把虚拟机转换为集群服务实现零停机的虚拟机迁移。基于蚁群算法和网络的“小世界”特性的负载均衡策略,利用蚁群中的成员和网络的“小世界”特性去发现负载过重和负载较轻的节点,然后把负载过重的节点上的部分任务转移给负载较轻的节点。利用蚁群在网络中发现负载过重节点的算法,增加了系统的开销,而且是在负载已经过重的情况下才进行发现和解决的,这种较滞后的策略可能有时无法解决负载不均衡或网络不稳定的问题。文献提出基于负载均衡的两级任务调度算法,每次都将虚拟机调度或迁移到负载最轻的主机上去。另外,分布式系统中基于移动代理(agent)的负载均衡策略也可应用于云计算系统,通过设计出不同范例的移动agent,每种agent根据自己被分配的任务去解决负载不均衡的问题。这种策略需要不同范例的移动agent之间的通信和有效合作,比较繁琐且花费较高的代价。本文通过节点负载度来判断节点的状态,利用自适应的负载均衡算法均衡云计算环境中节点的负载。自适应主要表现在两个方面:一是在节点即将过载,即处于轻度过载状态时,节点自发地启动过载避免方法;二是在节点负载过重,即处于重度过载时,自发地启动快速均衡方法,该策略能够保证云计算系统高效地运行。2节点效益度的概念在Min-min、Max-min、TD_Min-min和TD_Maxmin等类似的调度算法中,都有一个共有的特点:在选择节点时总是选择效益函数的最大或者最小值。效益函数主要是考虑在用户提交任务的同时提交任务所需求的资源参数:任务完成的最晚时间(deadline)和任务完成时所需要的费用(budget)。本文综合考虑云计算系统中效益函数的特性,给出了节点效益度的概念。定义1节点效益度:是在云计算调度过程中,节点对任务的满足度,其取值为节点的效益函数值,节点Ni的效益度用EF(Ni)来表示。节点效益度不仅和deadline、budget相关,而且和节点的安全性和可靠性相关,其值越高,表明在调度时此节点完成任务的可能性越大。在云计算系统中,高效益度的节点往往会接受很多请求,容易产生负载过重的现象。通过调整节点的效益度来调整节点负载是一种有效方法。本节首先提出了负载度的概念,然后根据节点负载过载的程度,设计了相应的过载避免和快速均衡方法,达到云计算系统既能够安全高效地执行任务,又能够保证网络中负载基本均衡的目标。2.1节点ni负载度节点的负载度是由节点的静态特征和运行时各方面的动态特征参数计算出来的,节点的负载特征参数可以用一个集合表示为:其中,每一个Ci(1≤i≤n)表示节点负载的一个动态或静态特征,n为节点负载特征参数的数量。常见的节点特征参数如表1所示。在计算节点负载度时,需首先对Ci(1≤i≤n)的值进行归一化处理,使Ci∈。定义2节点负载度:在云计算系统中,设Load_degree(Ni)表示节点Ni的负载度,则有:其中,∂i为一组权重系数,,可以根据不同的应用和需求动态调整相应的权重;Ci为节点Ni的负载度度量指标。由式(1)可知,负载度的度量不一定只限于单个判定标准,而是可以考虑将多个指标综合起来判定,这些度量指标的选取一般根据具体应用设定。负载信息统计是一种被动式的结点负载信息统计方式,负载信息采用稍带的方式进行传递,不增加网络消息数量,每隔时间T对节点的负载进行一次统计。在本文中根据节点的负载度不同,把节点的负载程度共分成正常负载、轻度过载和重度过载3种,分别定义如下。定义3正常负载:在云计算系统中,对节点Ni,在某一时刻t,若Load_degree(Ni)≤Load_degreemid,则节点Ni在t时刻处于正常负载状态。定义4轻度过载:在云计算系统中,对节点Ni,在某一时刻t,若Load_degreemid<Load_degree(Ni)≤Load_degreehigh,则节点Ni在t时刻处于轻度负载状态。定义5重度过载:在云计算系统中,对节点Ni,在某一时刻t,若Load_degree(Ni)>Load_degreehigh,则节点Ni在t时刻处于重度负载状态。节点Ni的负载状态如图1所示。定义6全局平均负载度:在云计算系统中,一段时间Δt内,云计算系统的平均负载度等于在该段时间Δt内,所有节点负载度的平均值。用G_Load_avg表示云计算系统中的全局平均负载度,n表示云计算系统中在线节点的数目,则有:对于定义3~6中Load_degreemid,Load_degreehigh的值可以根据不同的网络环境动态取值。在本文的实验中,Load_degreemid和Load_degreehigh的取值分别设置为G_Load_avg和2×G_Load_avg。2.2节点nj的节点调度优化策略对于云计算系统中的任意节点Nj,其自适应负载均衡策略分为过载避免和快速均衡两个过程,通过不同的效益度更新策略,使调度算法在任务调度时选择适当的执行节点。具体思想如下:节点Nj每隔一个时间周期检查自己的节点负载度,若检查到其节点超载,则按下列两种情况进行处理:(1)当tm时刻,节点Nj处于轻度过载时,进入过载避免阶段,具体的措施是,将节点Nj的效益度,按照式(3)更新:其中,EFtm+1(Nj)表示tm+1时刻时节点Nj的效益度,即更新后的节点Nj效益度,EFtm(Nj)表示tm时刻节点Nj的效益度,即节点Nj更新前的效益度。节点Nj处于轻度过载时,将节点Nj的节点效益度按照式(3)进行小幅度的降低,使任务调度时尽可能地选择次高效益度的节点进行派发,从而达到有预见性地采取策略避免节点Nj的负载度过高。(2)当tn时刻,节点Nj处于过重度负载时,进入快速均衡阶段,具体的措施是,将节点Nj的效益度,按照式(4)更新:其中,EFtn+1(Nj)表示tn+1时刻时节点Nj的效益度,即更新后的节点Nj效益度,表示tn时刻节点Nj的效益度,即节点Nj更新前的效益度。当节点Nj处于重度过载时,节点的效益度按照式(3)更新已经不能满足要求了,因此将节点Nj的节点效益度按照式(4)进行折半降低,以达到任务调度时较大概率地选择效益度次之的节点进行任务分配,从而有效降低Nj的负载。图2和图3分别是云计算系统中一个节点Nj在某个时间段的负载度和节点效益度的变化示意图。从图2和图3中可以看出,节点Nj在n1时刻处于轻度过载,这时Nj进入过载避免阶段,将按照式(3)更新效益度,它的负载并不会立刻降下来,但是会上升比较缓慢;在n2时刻,Nj处于重度负载,这时Nj进入快速均衡阶段,它将按照式(4)折半降低其节点效益度;经过一段时间的负载均衡,在n3时刻,节点Nj由重度负载转为轻度负载,同时进入过载避免,再经过一段时间,在n4时刻,节点Nj的负载度将趋于正常。在云计算系统中,任意节点Nj将定期检查自己的负载状态,若其负载处于轻度过载或重度过载状态,则需执行自适应负载均衡算法,该算法对于以上两种情况分别对节点的效益度做相应的更新,使节点调度算法在下次任务调度时作出更恰当的选择,以达到系统的负载均衡。分布式自适应负载均衡算法如下:采取自适应负载均衡策略,随着时间周期的推移,由于效益度高且负载很重的节点的效益度将被强制降低,在为任务选择执行节点时,那些效益度次之但负载较轻的节点开始被选中。自适应的负载均衡策略在开始时可能不能最大限度地利用每一个最高效益度的节点,但随着任务的不断执行,它能较好地实现负载均衡。3节点调度和负载均衡优化实验在实验室的Hadoop平台下完成,利用实验室的15台PC机,每台PC通过安装虚拟机分别模拟1~3个节点(node),建立了一个由40个具有不同硬件配置的node组成的实验平台。其中一个节点作为namenode和jobtracker,其他为datanode和tasktracker,运行40~200个任务。操作系统是LinuxUbuntu10.04,开发环境为Eclipse3.7,java环境为jdk-6u23-linux,Hadoop软件版本为hadoop0.20.1,虚拟机用VMwareWorkstation7.1.4。本文负载均衡策略的实施是通过对Hadoop的jobtracker类进行修改,实现了在向tasktracker派发一个新任务时,根据各节点效益度决定当前是否派发该任务以及将任务派发给哪些节点。主要修改包括添加了两个方法(method):算法1对应的节点效益度的更新方法是选择具有较高效益度的tasktracker派发任务。节点效益度通过tasktracker发送给jobtracker的心跳信息中的资源使用情况和节点的可靠性来计算,并根据本文算法更新。作业调度选用Hadoop缺省的FIFO算法,节点调度采用TD_Max-min,分别比较在未使用和使用了负载均衡算法时任务的执行时间跨度和节点的负载度,如图4,5所示。在本文中,负载度的特征参数主要选取平均响应时间、网络带宽和磁盘剩余空间。选择这些参数的原因是综合考虑到应用中的不同需求,如计算密集型服务对平均响应时间要求较高,存储密集型服务对磁盘剩余空间要求较高,网络密集型服务对网络带宽要求较高。实验的其它参数取值如表2所示。图4反映了在使用和未使用负载均衡算法时任务数目和任务的执行时间跨度的关系。可以看出,使用了负载均衡算法的执行时间跨度总体上要小于未使用负载均衡算法的执行时间跨度。当使用了负载均衡算法时,就会避免那些负载过重的节点继续接收调度,减少了因负载不平衡造成的作业重新调度和分配,节约了任务的执行时间跨度。图5反映了在使用和未使用负载均衡算法时网络中的节点数和节点的平均负载度的关系。可以看出,在未使用负载均衡算法时,节点的平均负载度在0.32上下波动,使用了负载均衡算法后,节点的平均负载度在0.12上下波动。在未使用负载均衡算法时,那些高效益度的节点因得不到有效缓解,仍要继续执行任务,这会导致其在响应时间、网络带宽等方面承受过重的负担,这些负载过重的节点就有可能成为网络的不稳定因素;而在使用负载均衡算法后,高效益度的节点得到有效缓解,当高效益度的节点负载过重时,负载均衡