文章信息
- 郭明强, 吴亮, 黄颖, 谢忠, 赵林
- GUO Mingqiang, WU Liang, HUANG Ying, XIE Zhong, ZHAO Lin
- WebGIS集群环境下Client主动式负载均衡策略
- Client Active Load Balancing Strategy Under WebGIS Cluster Environment
- 武汉大学学报·信息科学版, 2015, 40(12): 1639-1645
- Geomatics and Information Science of Wuhan University, 2015, 40(12): 1639-1645
- http://dx.doi.org/10.13203/j.whugis20140069
-
文章历史
- 收稿日期: 2014-01-20
2. 教育部GIS软件及其应用工程研究中心, 湖北 武汉, 430074;
3. 武汉大学资源与环境科学学院, 湖北 武汉, 430079
2. GIS Software and Application Project Research Center of the Educational Department, Wuhan 430074, China;
3. School of Resource and Environmental Science, Wuhan University, Wuhan 430079, China
由于空间数据的复杂性,WebGIS系统中处理请求的两大阶段会导致用户请求的平均响应时间延长,一是数据析取阶段,二是数据处理阶段。这两个阶段是WebGIS中处理开销较大的两个阶段。为了缩短服务的平均响应时间,采用多个服务器节点组成集群是一种简单有效的提高WebGIS系统并行处理能力的方式[1];另外,负载均衡方法是影响WebGIS集群并行处理能力的关键因素[2]。
本文针对现有WebGIS集群体系的结构特点进行研究,分析了目前具有代表性的负载均衡策略的弊端及其产生的不利影响,提出了一种全新的WebGIS集群环境下Client主动式负载均衡策略,设计了一种新的无负载均衡调度中心的WebGIS集群体系结构,改变了传统WebGIS集群中由负载均衡调度中心负责对所有并发访问请求进行分配调度的模式,而是直接在Client端对每个请求根据集群中各服务节点的处理能力进行均衡分解,并直接提交给各服务节点进行并行处理,减少了请求处理过程中的传输次数,更有效地实现了集群中各服务节点间的负载均衡,缩短服务的平均响应时间,从而提高了WebGIS集群的并发处理能力。
大用户量并发访问请求处理是并行GIS计算研究方向中的一个难题[3]。Mustafa研究了空间数据的实时简化和可视化方法[4],Yang研究了空间数据的渐进式传输方法[5]。这些方法虽然能解决一次性加载所有空间数据的长时间等待问题,但仍不能从根本上提高WebGIS并行处理能力。Cheng等[6]提出了一种域分解策略,但该策略仅针对栅格数据分析,对于矢量数据的空间计算特点未进行研究。Kim[7]和Yang[8, 9]提出了空间云计算技术的概念,WebGIS作为空间云计算平台的关键技术支撑,高效并行处理和负载均衡是其要解决的两个关键问题。Wang[10, 11]提出了CyberGIS体系架构并阐述了其包含的关键技术,同样指出了高性能并行处理和多服务节点间的均衡调度是该体系中的两个重点研究方向。
传统的软件方法[12]提供了廉价有效的负载均衡机制,目前已有相关探索。文献[1]提出了使用随机概率分配方式替代固定转发的分配方式。笔者在文献[13]中采用最少连接数负载均衡方法,通过负载均衡调度中心将并发请求分配到当前用户连接数最小的服务器。文献[14]提出了负载均衡调度中心对集群中的服务器进行分组的方法。文献[15]提出了一种自适应的负载均衡算法,但其负载均衡均需要由中央服务器来完成,对于计算密集和用户密集的WebGIS系统来说,存在中央服务器性能瓶颈问题。
另外,上述集群负载均衡均衡策略研究存在两个共同点:一是所有来自Client端的并发请求大多需要经由负载均衡调度中心或重定向服务器对访问请求进行调度,将请求转发给集群中的某个服务节点进行处理,这种体系结构会导致负载均衡调度中心或重定向服务器的节点瓶颈,同时也会增加请求的传输次数和传输开销;二是负载均衡调度中心需要定时检测集群中的各个服务器的CPU、内存等资源利用情况,而CPU、内存等资源的利用率不能反映出服务器节点当前处理的任务数量,也不能反映出服务器节点完成当前所有接收到任务所需要的时间,更不能计算出服务器当前的实际计算能力。
本文针对现有WebGIS集群体系结构的不足,设计一个无中心(负载均衡调度中心)的WebGIS集群体系结构,研究一种Client主动式负载均衡策略,实现WebGIS集群中各个服务器节点间的负载均衡,减少并发访问请求的传输开销,同时使各个服务器节点请求队列中的任务数目尽量相等,并且最大限度地缩短每个请求的平均响应时间。
1 Client主动式负载均衡策略 1.1 无中心的WebGIS集群体系结构现有的具有代表性的WebGIS集群体系结构如图 1所示,由负载均衡调度中心负责对GIS服务器集群中各服务节点的负载状态进行监视,通过计算服务器负载权值选择合适的服务节点处理来自客户端的请求任务。这种WebGIS集群体系结构存在三个弊端:(1)所有Client发送的请求均发送给Load Balancer(负载均衡调度中心),Load Balancer负责对并发访问请求队列进行管理,然后再根据负载均衡算法将请求队列中的任务分配给GIS服务器集群中的各个服务器节点进行处理。由于所有请求都经过Load Balancer,可能造成Load Balancer在网络通信和传输中的瓶颈,随着并发访问用户量的增加,这种问题会凸显,可能导致单点故障问题。(2)Load Balancer需要对GIS服务器集群中的所有服务器节点进行定时探测,采集其CPU、内存等资源利用率,用于计算各GIS服务器节点当前负载。该定时探测操作会额外增加负载均衡调度中心与GIS服务器节点之间的通信开销,并给GIS服务器带来额外的计算开销。另外,探测时间间隔越长,对服务器当前负载的判断越不准确;探测时间间隔越短,给GIS服务器节点造成的额外计算开销又越大。(3)Load Balancer在分配请求队列中的任务时,是为每个任务选择一个GIS服务器节点进行处理,而不能调度所有GIS服务器节点同时处理同一个任务。这种分配调度方式不能最大限度地缩短任务处理时间,即便是使用最小负载算法将待分配任务分配给一个当前负载最轻的GIS服务器节点,如果当前计算任务是一个大型的空间计算任务,服务响应时间同样难以满足Client用户需求。
![]() |
图 1 具有代表性的WebGIS集群体系结构 Fig. 1 Typical WebGIS Cluster Model |
为了解决以上WebGIS集群体系结构存在的弊端,本文提出了一种改进后的无中心(负载均衡调度中心)的WebGIS集群体系结构,如图 2所示。
![]() |
图 2 无中心的WebGIS集群体系结构 Fig. 2 Improved No Center WebGIS Cluster Model |
1) 图 2中,改进后的WebGIS集群体系结构中无Load Balancer(负载均衡调度中心)节点,所有Client提交的请求通过App Server(应用服务器)直接发送给GIS服务器集群中的各个服务节点进行处理,与图 1所示的WebGIS集群体系结构相比,减少了请求的转发次数,缩短了请求的处理时间,避免了大用户量并发访问时Load Balancer的请求转发瓶颈。
2) 改变了图 1中的WebGIS集群体系结构中由负载均衡调度中心定时探测各个GIS服务器负载的方式,由Client根据上一次请求的处理时间和空间计算量计算出各个GIS服务器节点的每秒处理能力,以此来衡量各个GIS服务器节点当前的计算能力,为下一次任务分配提供依据。
3) 改变了传统WebGIS集群体系结构中调度单个GIS服务器节点处理单个请求的模式,在Client端将每个请求任务根据各个GIS服务器节点当前处理能力进行分解,然后将分解后生成的各个子任务发送给各个GIS服务器进行处理,以调度多个服务节点并行完成同一个计算任务,最大限度地缩短了请求的处理时间,并避免了GIS服务器的节点争用问题。
为解决图 1中WebGIS集群体系结构并行处理能力弱,请求响应时间延迟等问题,本文采用策略如下:在Client端主动地对每个空间计算任务进行均衡分解,然后分发给GIS服务器集群中的各个服务器节点进行并行处理,即通过对每个空间计算任务的均衡分解实现各个GIS服务器节点间的负载均衡,同时达到最大限度缩短请求响应时间的目的。该策略需要解决两个关键问题。
(1) 在没有负载均衡调度中心定时监视各GIS服务器节点负载的环境下如何计算各个GIS服务器节点当前的处理能力;
(2) 每个Client如何根据各个GIS服务器节点的处理能力对每个空间计算任务进行均衡分解,以实现Client主动式负载均衡。
为了解决以上问题,本文提出了在Client端根据空间数据要素分布情况对空间计算任务进行分解的方法,并根据分解后的各个子任务的处理时间和要素数量计算各个GIS服务器节点每秒处理能力,即通过单位时间内能够处理的数据量来测定GIS服务器节点当前的计算能力,为后续的空间计算任务分解提供依据。
1.2 Client主动式任务均衡分解原理在Client端实现空间计算任务的均衡分解时,首先在GIS服务器端为空间数据构建要素分布信息库,其次在Client端对空间数据请求范围进行处理,以从GIS服务器端空间数据分布信息库中检索到当前请求范围内的空间数据分布信息网格集合。本文采用对空间数据请求范围进行格网化的方法。在对Client空间数据请求范围格网化之后,由GIS服务器根据空间数据范围计算出Client需要请求的空间数据分布信息网格集合,将其返回给Client。Client获取到以上信息后在本地进行缓存,并立即对网格集合进行扫描分析。由于Client在发送第一次请求之前还不能计算出各GIS服务器的计算能力,因此第一次发送请求是通过GIS服务器节点数量对空间数据请求进行平均划分,得到多个计算量相同的子任务,然后向各个GIS服务器并行发送请求,在接收到请求处理结果后,通过每个子任务的处理时间和处理的空间数据量,可以计算出每个GIS服务器单位时间内的处理能力(每秒能够处理的空间数据量),为下一次提交的空间计算任务的分解提供依据,最终实现空间计算请求的均衡调度。
1.3 Client主动式负载均衡算法1) 空间数据分布信息网格计算
首先我们需要在服务器端为空间数据构建要素分布信息网格,将各网格单元信息及其中分布的要素个数存储到空间数据分布信息表中。
设空间数据范围左下角为坐标原点,令其坐标为(xmin,ymin)。设空间数据的外包矩形范围为(xmin,ymin,xmax,ymax),为了便于使用四叉树组织形式构建空间数据分布信息网格,将外包矩形范围以(xmin,ymin)为原点向右上方扩展为正方形,设扩展后的正方形范围为(xmin,ymin,x′ max,y′ max)。
定义1 设第i级空间数据分布信息网格中一个单元格的逻辑范围跨度为di,由于本文采用四叉树的形式构建要素分布信息网格,因此第i级网格的总数为 2i×2i。
设第i级空间数据分布信息网格第x列第y行网格的范围为(gxmin,gymin,gxmax,gymax)。
根据上述值得到空间数据分布网格的范围,可以从原始空间数据中检索到该范围内分布的要素个数,设其为RG(i,x,y),将这些信息一起存储到空间数据分布信息表中。
2) Client空间数据请求范围格网化
设Client当前空间数据请求范围为(lxmin,lymin,lxmax,lymax);为了检索到与Client当前请求的空间数据范围匹配的空间数据分布信息网格,需要对空间数据请求范围进行格网化。
定义2 设Client空间数据请求范围划分的网格数为v,网格单元的逻辑范围跨度为dl。客户端计算出dl后,将其与当前空间数据请求范围一起发送给服务器端。
3) 检索空间数据分布信息网格
GIS服务器接收到Client的请求后,先找到与dl最接近的di,以确定要检索的空间数据分布信息网格级别i,然后根据Client当前空间数据请求范围(lxmin,lymin,lxmax,lymax)计算分布于该范围内的要素分布信息网格集合。
设分布于当前请求范围内的要素分布信息网格集合的起始列为Cstart,结束列为Cend,开始行为Rstart,结束行为Rend。通过上述分布信息网格集合的起始行列,GIS服务器可以从空间数据分布信息表中检索出该网格集合中所有网格的信息记录,将其返回给Client进行分析。
4) Client双向扫描分析与任务分解
定义3 设空间数据分布信息网格集合中每个网格单元中分布于当前空间数据请求范围内的要素个数为G(i,x,y)。
定义4 设检索到的空间数据请求范围内的要素分布信息网格中分布的要素总量为TG。
设GIS服务器个数为 N,则需要将请求的空间数据范围内的要素分布信息网格集合划分为N个子集。设分配给第n个GIS服务器的目标要素数据量为Cn,其与要素总量TG的比值为Pn,如果Client是首次发送请求,假设各个GIS服务器的处理能力相同,则Pn=1/N。如果不是首次发送请求,则需要根据上一次请求经过分解后的各个子任务Taskn的处理时间TaskTn和空间数据量TaskGn计算各GIS服务器的每秒处理能力,则有:
设各个子任务对应的空间数据范围为(sxmin,symin,sxmax,symax)。Client获取空间数据请求范围内的要素分布信息网格集合信息并计算出Cn后,使用两个扫描线程分别从左向右和从右向左对空间数据请求范围进行双向扫描分析,最终可得到各个GIS服务器分配的目标空间数据范围,即各个子任务对应的空间数据范围(sxmin,symin,sxmax,symax),实现空间计算任务 请求在Client端的主动式均衡分解,达到提高WebGIS集群并行处理能力的目的。
2 实验设计与结果 2.1 实验参数本文使用位于高速局域网内的IBM刀片中心构建试验床,采用城镇地籍矢量数据进行实验,使用HP LoadRunner模拟不同大小的并发访问用户量,并与传统WebGIS集群常见的几种负载均衡算法进行对比。表 1为系统实验参数。
实验参数内容 | |
实验算法 | 轮询算法、最小负载算法、最少连接算法、Client主动式负载均衡算法 |
实验网络 | 服务器端:64口千兆以太网交换机连接客户端:分别使用1 000 M,100 M,10 M,256 K 4种不同带宽进行测试 |
Web服务器 | 1台CPU:Intel. Xeon. E5620 2.40 GHz (4核,8线程),8 GB内存服务器 |
GIS服务器集群 | 4台CPU:Intel. Xeon. E5620 2.40 GHz (4核,8线程),8 GB内存服务器 |
客户端测试机 | CPU:Intel. Pentium G860 3.00 GHz,4 GB内存 测试软件:HP LoadRunner 11 |
矢量数据量 | 要素总量为7 465 146个 |
测试时间 | 5 h |
统计参数 | 采集不同Client用户数并发访问时的请求平均响应时间 |
在WebGIS服务应用中,Client提交空间计算请求时,特别是在提交大型空间计算任务时,平均响应时间越小,用户体验越好。为了验证本文提出的方法在大用户量并发访问时的优势,使用不同的并发访问用户数对传统WebGIS集群中常见的负载均衡算法与本文提出的无中心环境下的Client主动式负载均衡算法进行对比测试。本文提出的方法对与网络地图服务类似的请求(如矩形查询、矩形裁剪分析等)均能达到同样的负载均衡的目的,为了便于与其他方法进行对比,测试中并发访问请求类型统一采用了应用较为广泛的网络地图服务请求做为测试用例。
图 3是在相同的用户数(100个虚拟Client)并发访问的情况下,本文算法和其他常见的几种负载均衡算法在实验过程中的平均响应时间波动对比图(1 000 M网络带宽下)。从图 3中可以分析得出:(1) Client主动式负载均衡算法的平均响应时间在整个实验过程中波动较小,原因是该算法在Client向GIS服务器提交请求之前将空间计算任务根据GIS服务器个数及其处理能力进行了均衡分解,以均衡各个GIS服务器的计算负载。(2) 最小负载算法和最少连接算法的平均响应时间波动较大,其原因是这两种算法都未考虑空间计算请求的计算开销和均衡分解,实验过程中如果队列中有执行时间较长的任务,则会导致队列中后面的请求响应时间增大,产生波动。(3) 轮询算法的平均响应时间波动最大,分析其原因是该算法既未考虑服务器的负载状况,也未考虑任务的计算开销,导致服务器的负载不均衡,使得所有并发用户的平均响应时间产生较大波动。
![]() |
图 3 100用户并发访问平均响应时间波动 Fig. 3 The Average Response Time Fluctuations of 100 Concurrent Users |
图 3说明,在相同网络带宽下,本文提出的Client主动式负载均衡算法在负载均衡和稳定性方面具有优势。为了证明本文提出的方法在不同网络带宽下的有效性,使用不同的网络带宽对本文方法的平均响应时间进行测试,结果如图 4所示。从结果中可以分析得出,在1 000 M、100 M、10 M、256 K 4种带宽下,平均响应时间均随并发用户数的增加而平均增加。由于网络带宽会影响请求和结果的传输时间,所以网络带宽越大,平均响应时间越小。但在256K网络带宽环境下,当并发用户数大于50时(图 4),网络吞吐量受到网络带宽的限制,平均响应时间开始快速增加,但这种增加趋势整体上也是比较平稳的。因此,从测试结果可以看出,本文提出的方法在不同的网络带宽下都具有较好的稳定性和抗高负载能力,适合应用于WebGIS平台。
![]() |
图 4 Client主动式负载均衡算法不同带宽下平均响应时间 Fig. 4 Average Response Time of Client Active Load Balancing for Different Network Bandwidth |
本文针对现有WebGIS集群环境下负载均衡策略中存在的弊端进行研究,考虑到空间数据请求范围中的要素分布情况,设计了Client主动式负载均衡策略,将空间计算任务均衡地分配给GIS服务器集群中的各个服务器节点,以缩短平均响应时间,提高服务的稳定性和抗高负载能力。使用不同的并发访问用户数对本文提出的算法进行了验证测试。实验结果表明,与传统WebGIS集群及常见的负载均衡算法相比,利用本文提出的Client主动式负载均衡算法进行改进后的WebGIS集群在大用户量并发访问场景下表现出较好的稳定性和抗高负载能力。
[1] | Guo Chengcheng, Yan Puliu. A Dynamic Load-balancing Algorithm for Heterogeneous Web Server Cluster[J]. Chinese Journal of Computers, 2005, 28(2): 179-184 (郭成城,晏蒲柳.一种异构Web服务器集群动态负载均衡算法[J].计算机学报,2005,28(2):179-184) |
[2] | Zhang Zhongju, Fan Weiguo. Web Server Load Balancing: A Queueing Analysis[J]. European Journal of Operational Research, 2008, 186(2):681-693 |
[3] | Zhao Chunyu.Studying on the Technolgies of Storage and Processing of Spatial Vector Data in High-performance Parallel GIS[D]. Wuhan :Wuhan University,2006(赵春宇.高性能并行GIS中矢量空间数据存取与处理关键技术研究[D]. 武汉:武汉大学,2006 |
[4] | Mustafa N, Krishnan S, Varadhan G. Dynamic Simplification and Visualization of Large Maps[J]. International Journal of Geographical Information Science,2006,20(3):273-302 |
[5] | Yang Bisheng, Purves R, Weibela R. Efficient Transmission of Vector Data over the Internet[J]. International Journal of Geographical Information Science,2007,21(2):215-237 |
[6] | Cheng G, Jing N, Chen L. A Theoretical Approach to Domain Decomposition for Parallelization of Digital Terrain Analysis[J]. Annals of GIS, 2013, 19(1): 45-52 |
[7] | Kim I, Tsou M. Enabling Digital Earth Simulation Models Using Cloud Computing or Grid Computing-two Approaches Supporting High-performance GIS Simulation Frameworks[J].International Journal of Digital Earth,2013,6(4): 383-403 |
[8] | Yang G, Goodchild M, Huang Q, et al. Spatial Cloud Computing: how can the Geospatial Sciences Use and Help Shape Cloud Computing? [J]. International Journal of Digital Earth,2011, 4(4): 305-329 |
[9] | Yang C,Xu Y, Nebert D, et al. Redefining the Possibility of Digital Earth and Geosciences with Spatial Cloud Computing[J]. International Journal of Digital Earth,2013, 6(4): 297-312 |
[10] | Wang S. CyberGIS: Blueprint for Integrated and Scalable Geospatial Software Ecosystems[J]. International Journal of Geographical Information Science,2013,27(11): 2 119-2 121 |
[11] | Wang S, Anselin L, Bhaduri B, et al. CyberGIS Software: A Synthetic Review and Integration Roadmap[J].International Journal of Geographical Information Science,2013,27 (11): 2 122-2 145 |
[12] | Jiang Fei, Zhou Baoqun, Wang Huifang. An Effective Loading-balancing Framework for Distributed WebGIS[J]. Microcomputer Information,2006, 22(10): 215-218(江飞,周保群,王惠芳.一种有效负载均衡的分布式WebGIS体系结构模型[J].微计算机信息, 2006,22(10):215-218) |
[13] | Huang Ying, Guo Mingqiang, Luo Xiangang, et al. Research & Realization on Load-balancing Technique of GIS Server in WebGIS[J]. Science of Surveying and Mapping, 2009,34(1):182-183(黄颖,郭明强,罗显刚,等. WebGIS中GIS服务器负载均衡研究与实现[J].测绘科学, 2009,34(1):182-183) |
[14] | Li Zhongmin, Yu Zhanwu, Zhu Li. A Spatial-Data-Content-Based Dynamic Load Balancing Method[J]. Geomatics and Information Science of Wuhan University, 2009,34(5):622-624(李忠民,喻占武,朱莉.基于空间数据内容的动态负载均衡方法[J].武汉大学学报·信息科学版,2009, 34(5):622- 624) |
[15] | Chen Yijiao, Lu Xicheng, Shi Xiangquan, et al. A Session-oriented Adaptive Load Balancing Algorithm[J].Journal of Software,2008,19(7):1 828-1 836(陈一骄,卢锡城,时向泉,等.一种面向会话的自适应负载均衡算法[J].软件学报,2008,19(7): 1 828-1 836) |
[16] | Guo Mingqiang, Huang Ying, Xie Zhong. Design and Implementation of Distributed WebGIS Model Based on Server Farm[J]. Geography and Geo-Information Science, 2008, 24(6):12-15(郭明强,黄颖,谢忠.一种基于服务器场的分布式WebGIS计算模型设计与实现[J].地理与地理信息科学, 2008,24(6): 12-15) |