服务器利用遗传算法的网络GIS集群服务器动态负载均衡算法

------------------------------------------------------------------------------------------------

利用遗传算法的网络GIS集群服务器动态负载均衡算法

第36卷第6期2011年6月武汉大学学报??信息科学版

GeomaticsandInformationScienceofWuhanUniversityVol .36No.6June201

1

文章编号:1671??8860(2011)06??0721??05文献标志码:A

利用遗传算法的网络GIS集群服务器

动态负载均衡算法

朱??莉1??沈未名1??李??锐1??徐胜勇2

(1??武汉大学测绘遥感信息工程国家重点实验室,武汉市珞喻路129号,430079)(2??华中科技大学图形识别与人工智能研究所,武汉市珞喻路1037号,430074)

摘??要:针对现有负载均衡方法的不足和网络GIS数据的特点,提出了一种基于遗传算法的网络GIS集群服务器动态负载均衡方法。该算法将基于服务器状态和基于内容的调度算法综合起来考虑,设计了相应的编码机制和遗传操作。实验结果表明,和常用的负载均衡算法相比,此算法能获得更小的服务请求响应时间,能更好地服务网络GIS系统。

关键词:网络地理信息系统;集群;服务质量;负载均衡;遗传算法中图法分类号:P208

????在网络GIS服务系统中,大规模、高强度的访问请求给服务器——————————————————————————————————————

------------------------------------------------------------------------------------------------

端的数据提取带来了挑战。为了保证服务质量,通常采用服务器集群技术对多台应用服务器进行集中管理,并采用相应的负载均衡技术来实现系统的负载均衡。国内外学术界对服务器集群中的负载均衡调度算法进行了比较多的研究[2,3] 。海量空间数据具有多分辨率、多数据集的特点,适合网络GIS服务的属性并适用于其访问模式特征和大规模访问量的集群负载均衡方法,在学术界研究相对较少[4??11] 。 已有方法要么是利用应用服务器的负载状况分配任务,要么是根据请求对象的内容充分利用缓存优势分配任务。本文希望能将这两类调度算法的优势结合起来,尽可能地使系统提供服务的性能达到最优。

遗传算法(GA)是模拟自然界生物进化过程与机制求解问题的一类自组织与自适应的人工智能技术[12]。在应用GA求解具体问题的过程中,确定编码方式、适应度函数和操作算法后,GA将利用进化过程中获得的信息自行组织搜索。这种自组织、 自适应的特征,使其能够根据具体的环境变化来自动发现环境的规律,非常适用于状态实时变化的网络应用环境,能根据当前的系统状态来决策请求的分配问题。

综上所述,本文提出了一种基于GA的网络

收稿日期:2011??04??05。

[1]

GIS集群服务器动态负载均衡算法

(GA??baseddynamicloadbalancingalgorithmofclusterserversinnetworkGIS,GALBCNG),该算法将

基于服务器状态和基于内容的负载均衡算法综合起来考虑,可灵——————————————————————————————————————

------------------------------------------------------------------------------------------------

活调整这两方面的权重。一方面,根据服务数据内容将应用服务器分组,尽可能将相同类型的请求分到服务该类型的服务器,以提高应用服务器的访问局部性,从而提高Cache命中率。各应用服务器组可按需增加相应的服务器个数,具有良好的可扩展性。另一方面,考虑后端应用服务器的负载状态,尽可能使得请求能够平均地分发给各个服务器,以达到负载均衡的效果,从而提高服务器集群带负载的能力。

1??GALBCNG算法

本文采用的重定向型负载分配模型,由集群前端的负载均衡器(loadbalancer,LB)和GIS应用服务器(GISserver,GS)组成。客户端向负载均衡器发出数据服务请求,LB根据基于GA的负载均衡算法分配任务给相应的GS。被选中的GS直接响应客户端的数据请求。 1.1??负载均衡机制的初始化

为了达到最佳负载均衡状态,何时和怎样初

:(;(

722

武汉大学学报??信息科学版2011年6月

始化负载均衡机制非常重要。采用滑动窗口技术,负载均衡器一次处理落在窗口中的任务。 网络GIS系统中,请求任务频繁,并发性强,比如系统中的一次点击操作会请求若干个瓦片,因此,负载均衡器端的服务队列中将会有大量待分配的任务。采用滑动窗口技术能一次处理落在窗口中的任务组,窗口大小也能根据具体情况配置。

本文算法中,滑动窗口的大小正好等于遗传算法中个体的基因个——————————————————————————————————————

------------------------------------------------------------------------------------------------

数。因此,用一组任务形成的列表描述该任务组调度执行的不同顺序。当遗传算法生成一个任务调度时,这组任务被相应地分配给各个处理器。当前任务组分配完后,滑动窗口将滑动到任务队列中的下一组任务,之后操作重复执行。一般情况下,系统任务队列中的任务将再次填满滑动窗口,此时的滑动窗口称为??完全窗口??。在实际操作中,也会出现这样一种情况,系统任务队列中剩余的任务未能将滑动窗口填满,称之为??不完全窗口??。此时,如果仍然调用遗传算法分配任务将会浪费系统资源。对于这两种滑动窗口,采用不同方案处理:当窗口完全时,启用遗传算法得到最佳的任务方案分配任务;当窗口未填满时,根据请求服务的内容将请求轮询给相应的应用服务器。

1.2??GALBCNG算法流程

算法开始,更新系统当前状态,为分配任务作准备。检查滑动窗口状况,若为空,表示当前系统无待分配的任务,算法停止;若为非完全窗口,则表示任务较轻,此时采用常用的轮询调度算法即可;若为完全窗口,则启动GA生成最合适的任务分配方案,将请求分配给相应的应用服务器。然后更新系统状态信息,重新检查滑动窗口,进行新一轮的任务分配。如此循环,直到无请求为止。

[13]

算法中,每个基因代表一个待分配的任务t,一组待分配的任务组成一个染色体,每个染色体代表一个分配方案。如何将问题解编码成为染色体是GA使用中的关键问题。本文采用二维编码方式,分别表示系统中的应用服务器信息和每个处理器上待分配的若干个任务。——————————————————————————————————————

------------------------------------------------------------------------------------------------

定义1??服务器最佳服务类型。服务器最佳服务类型是Pi .app的值,是其缓存的主要数据类型,可以充分利用缓存数据减少用户请求的响应时间,因此是服务器最适合提供的服务。在前端的负载均衡器上有一张表,记录了各个应用服务器的服务类型,并可按需扩展。

定义2??任务服务匹配。设任务Tn被分配到应用服务器Pi上,若Tn.k=P i .a pp,则称Tn服务匹配,此时有Tn.m a t=1;若Tn.k??P i .a p p,则称Tn服务不匹配,此时有Tn.mat=0。可以认为,任务服务匹配的任务越多,缓存利用率越大。

设系统有N台应用服务器,假设每台服务器都可提供所有的服务类型。用??Pi .app??描述服务器信息,Pi表示应用服务器(i??[0,N]),app表示服务器提供的最佳服务类型。 Tn表示第n个任务,每个任务信息<n,s,mat>含有三元信息,分别是任务号n、任务大小s和是否与所选服务器匹配mat。显然,元素n和s是十进制数,mat虽然设置为十进制数,但实际上只有0、1两种可取值,即分别代表不匹配和匹配两种情况。二维编码后的一个染色体如图1所示。

2??GALBCNG算法中GA的设计

在解决实际问题优化时,GA不能直接处理问题空间的参数,而只能处理以基因串的形式表达的染色体。因此,要使用GA就必须将问题解的参数转换成染色体形式,即编码[14] 。 2.1??编码机制

每个任务用??n(s)k??形式描述,分别表示任务编号、任务大小和任务类型。采用需要系统处理的单位时间的个数来描述任务大小。任务类型为各种空间数据和非空间数据,由系统提供的数据决

——————————————————————————————————————

------------------------------------------------------------------------------------------------

定,k??[s,l,m??],s代表地形数据,l代表影像

,图1??二维染色体编码

Fig.1??Tow??DimensionalCodingofString

2.2??适应度函数

多媒体网络GIS包括空间数据和非空间数据,空间数据包括地形数据、影像数据等小文件;非空间数据包括各种大小不一的多媒体文件。 由于数据的海量性和多样性,通常采用分布式文件系统存储数据文件,但由于存储体系结构、Cache结构不完善和存储设备的访问延时,频繁的小文件操作使系统整体性能急剧降低,严重影响了其

723

网络空间数据的传输带宽、减少服务器端空间数据处理的负载压力,必须努力提高空间数据的读写性能,除了修改底层存储设备外(不在本文考虑范围之内),缓存具有明显的优势。为了最大程度上提高缓存利用率,将多媒体网络GIS中的应用服务器按照应用类型分类。如果地形数据请求能够由地形服务器服务,则利用地形服务器缓存响应请求的概率将大大提高。

另一方面,应用服务器自身的状态是影响负载均衡的重要因素。首先,考虑各个应用服务器中总的任务完成时间span[15],记span的最大值为spanmax,最小值为spanmin,平均值为span。两者差值??s越小,意味着任务分配越均衡;其次,负载偏差率反映的是各CPU负载的总体分布规律,当各CPU的利用率越高、之间的负载偏差率越小时,系统负载均衡的性能就会越好,对参数处理后得到的总体适应度函数包括缓——————————————————————————————————————

------------------------------------------------------------------------------------------------

存适应度部分fc和服务器适应度部分fs,即f=fc+fs

综上所述,算法总体适应度函数为:i=1f=fc+fs=x1

??matkki

+x2[(1-

)??span

(1-

=1

(CPi-CP)2k

)]

(7)(8)

其中,x1、 x2为常数,是权重因子,满足:x1+x2=12.3??遗传操作

1)选择操作。为了保证适应度较大的一些个体一定能够被保留在——————————————————————————————————————

------------------------------------------------------------------------------------------------

下一代群体中,选择??确定式采样选择??[16]方法。选择fch作为采样函数,具体操作见文献[16] 。令x1=k,x2=0,则:fch=i=1

??matki

(9)

????2)交叉操作。因为交叉和变异操作不能对二维编码进行,故需要将二维编码映射为一维编码。本文将二维编码矩阵依次首尾相连从而得到一维编码,图3是由图1中的例子得到的一维编码。

(1)

????设当前服务器Pi负载为CLi,新增任务负载为NLi,Pi的CPU利用率为CPi,均值为CP。算法中不仅考虑待分配任务的大小,同时也考虑当前服务器任务情况,则有:

N

1

Np

图3??二维染色体到一维染色体的映射

2spani=CLi+NLi=

——————————————————————————————————————

------------------------------------------------------------------------------------------------

p=0

??T

.s+q=0

??Tq

.s(2)

Fig.3??MappingaTwo??DimensionalStringintoaOne??DimentionalStringspan=i=0

??span

N

Ni

(3)(4)(5)(6)

在种群中任选两个父代个体进行交叉操作,

设基因个数为q,交叉位置满足交叉点左边部分有一个共同基因的第一个位置。交叉点确定后,交叉点左边不相同基因随机交换后,左边部分整体交换得到两个新的子代个体。值得注意的是,一次交叉操作完成后,位置的变化会导致任务所分配的服务器变化,故Tn.m a t的值应相应改变。 3)变异操作。既提高适应度函数的值,又要保证个体中基——————————————————————————————————————