基于响应比优先调度的WebGIS动态负载均衡算法

郭明强，黄颖，谢忠

（1.中国地质大学（武汉）信息工程学院，湖北 武汉 430074；2.教育部GIS软件与应用工程研究中心，湖北 武汉 430074）

0 引言

现有WebGIS主要从硬件和软件两个方面解决负载均衡问题。硬件上通过专用的负载均衡器或提高地图服务器的CPU处理速度、增加内存容量等方法提高系统性能，但代价昂贵［1］。传统的软件方法提供了廉价而有效的负载均衡机制，目前已有相关探索，如最小负载法、网络轮询法、最少连接数法以及相应的加权算法等。但是这些算法要么未考虑系统特征信息，仅适用于小规模网络地理信息服务系统；要么过度使用和监测服务器实时状态信息，信息收集本身及其准确性影响了系统的快速响应与决策，因此均不能达到理想的负载均衡效果［2－5］。文献［5－7］方法虽然能在一定程度上起到负载均衡的作用，但是由于没有同时考虑并发用户任务等待时间和执行时间，对于后提交的任务，其等待时间长，如果其要求的执行时间短，优先级高，则会产生响应滞后现象，随着并发用户的增多，这种滞后现象会越发严重。

为了缩短所有并发用户的响应时间，解决并发访问时产生的响应滞后问题，本文提出了基于响应比优先调度的 WebGIS动态负载均衡算法（RRPSA）。本算法同时考虑了并发用户请求在任务队列中的等待时间、任务要求的标准执行时间、集群中各应用服务器的当前负载状态，使执行时间越短、等待时间越长的任务优先被分配到当前负载最轻的服务器上。实验结果表明，本算法有效缩短了服务器的平均响应时间，充分考虑了所有并发用户的使用，让所有并发用户都能在理想的时间内得到响应，实现了良好的全局负载均衡效果。

1 基于RRPSA的WebGIS负载均衡模型

WebGIS是一种用户交互性很强的网络地图服务应用，包含两大要素：GIS数据与GIS计算。一个高效的WebGIS的最终目标是实现Internet上高效的GIS数据分布和GIS计算分布。对GIS计算的策略不同，WebGIS实现的技术方案也就不同［1］。

目前已有的对WebGIS中负载均衡的研究大多是针对单任务、顺序性任务。单任务、顺序性任务是WebGIS空间计算任务的简单形式，解决的问题比较简单。随着WebGIS应用的不断深入，空间计算已从单任务向并行性、协作性任务发展，如何提升系统并发访问能力和响应速度已成为其迫切需要解决的问题［8］。显然，一个能够综合描述上述各种因素的调度模型和基于该模型的高效的求解方法是提升系统并发访问能力和响应速度的关键。

为了解决以上问题，本文提出了一种可自由按需扩展的网络地图服务集群负载均衡模型（图1），综合考虑任务的请求等待时间、任务标准执行时间两方面因素及资源的负载能力、资源之间的网络状况。

总控模块启动请求监听器，负责监听来自 Web服务器的请求，将请求按序排列，加入请求等待队列，同时通过负载监视器定时检测集群中各个地图服务器的网络状况和实时处理能力。RRPSA算法计算请求等待队列中任务的响应比（RRP），按RRP从高到低进行排序，选择RRP最高的任务作为当前待分配任务，根据负载监视器的检测结果和各地图服务器的硬件配置计算各地图服务器的负载权值，将负载最低的地图服务器作为当前目标服务器，让其处理当前RRP最高的待分配任务。地图服务器处理完请求后将结果反馈给Web服务器，最终返回给客户端。RRPSA重新计算请求等待队列中任务的RRP，选择下一个RRP最高的任务进行处理。

图1 基于RRPSA的WebGIS模型Fig.1 WebGIS model based on RRPSA

在大用户量并发访问的情况下，请求等待队列会随着用户数的增加而增加，本算法使得并发访问的所有用户都能在比较理想的时间内得到响应，并能均衡的使用集群中的各个地图服务器，提高系统的并发处理能力。

2 RRPSA算法

2.1 服务器状态权值收集

负载均衡调度器初始化集群中设有各地图服务器负载权值列表、服务结点信息表以及服务器状态列表。

各地图服务器负载权值主要由3方面决定：地图服务器的软硬件性能线性综合参数Hi，其权值为W（h）；负载均衡调度器与地图服务器集群之间的网络状况参数Ti，用来衡量负载均衡调度器与集群中各个地图服务器之间的数据传输速度，其权值为W（t）；地图服务器即时处理能力Pi（是指各个地图服务器执行一项相同的标准任务的快慢），权值为W（p），设：

负载权值算法计算流程如下：

（1）根据地图服务器软硬件配置信息计算地图服务器软硬件配置所占权值。各个硬件配置的性能值和权值参数定义如表1所示。

表1 性能值、权值参数定义Table 1 Parameters definition of performance and weight

其中：Ci、Mi、Di、Xi、Ni、Oi＜1，W （c）＋W （m）＋W（d）＋W（x）＋W（n）＋W（o）＝1。

根据上述参数和服务器软硬件配置权值计算地图服务器软硬件性能线性综合参数：

（2）计算出软硬件性能线性综合参数后，再根据地图服务器的网络延时计算出各个地图服务器的网络状况参数，其公式如下：

其中：ti是各个地图服务器与负载均衡调度器之间的网络延时，n为地图服务器的数目。

（3）计算各个地图服务器即时处理能力权值Pi，其公式如下：

其中：n同上，pi为地图服务器执行标准运算任务所花的时间。

（4）通过式（1）、式（2）、式（3），可得出各个地图服务器的负载权值：

计算出地图服务器的负载权值后，负载均衡调度器启动服务，开始监听服务端口，准备接收 Web服务器的地图服务请求；同时启动负载均衡调度器监控线程，定时监控各个地图服务器状态。

2.2 RRP计算及动态调度

WebGIS应用复杂，包括矢量地图显示、瓦片地图显示、要素查询、空间分析等功能，每个功能应用需要的标准执行时间均不相同，以矢量地图显示功能为例，每个用户每次请求的矢量地图的范围均不相同，范围越大，生成图像越慢。在这种复杂的应用场景下，为了使大多数并发用户满意，首先要考虑请求预计的标准执行时间，执行时间越小，应该优先被执行，其次要考虑并发用户的等待时间，等待时间越长，优先级越高，应该优先被执行，这样才能使等待时间长的用户优先得到响应，避免用户无限的排队等待。RRPSA基于使平均响应时间尽可能低且让大多数并发用户满意的原则对任务进行动态分配。

设ts为任务提交时间，tb为任务实际开始执行时间，tc为任务实际执行完成时间，tp为任务要求的标准执行时间，T为所有并发任务平均周转时间。如果只考虑任务在队列中的等待时间，即只考虑tb－ts这个时间段而不考虑tp，则会出现tp小等待时间长的任务的响应延迟现象。RRPSA算法的目标是综合考虑任务等待时间和执行时间，让T最小，即让所有并发用户的平均响应时间最短，使等待时间长、要求执行时间短的任务优先执行，T计算公式如下：

计算任务标准执行时间tp：以矢量地图请求为例，可采用空间范围来衡量一个请求内容的大小，根据请求范围计算出等待任务队列中各任务要求的标准执行时间tp，定义xmin、ymin、xmax、ymax为当前矢量地图请求队列中最大的外包矩形范围，每个请求的范围为xmini、ymini、xmaxi、ymaxi。

计算任务等待队列中的各任务的响应优先级，设当前计算时间为t，则当前计算任务的响应优先级R：

负载均衡调度器中的负载监视线程定期搜集服务器状态信息，计算负载权值，选择R最高的任务分配给负载最低的服务器执行，同时从等待队列中删除已分配的任务。

3 实验分析

本文使用位于高速局域网内的刀片中心构建试验床，对本文提出的响应比优先调度动态负载均衡算法进行仿真实验，并与传统集群服务器负载均衡算法进行对比。图2为实验环境的网络拓扑结构，表2为系统仿真参数。

图2 实验环境网络拓扑结构Fig.2 The network topology of simulation

通过LoadRunner对系统进行压力负载测试。测试数据：国土地类图斑矢量数据（矢量要素个数为4 023 175），每个用户每次随机请求一个地图范围。在WebGIS应用系统中，数据请求的响应时间至关重要，负载均衡的重要指标就是最小化请求平均响应时间。特别是在地图漫游响应时间方面，响应时间越短，表示WebGIS应用系统的地图漫游越流畅，用户所感受到的漫游体验或者说服务质量越高。

表2 系统仿真参数Table 2 Simulation parameters of the system

图3是在相同的用户数（100个虚拟客户端）并发访问的情况下，本文算法和其它常见的几种负载均衡算法在仿真过程中的平均响应时间波动对比。从图中可以分析得出：1）本文中RRPSA算法的平均响应时间在整个仿真过程中波动较小，原因是RRPSA算法综合考虑了请求的等待时间和执行时间以及服务器的负载状况。2）最小负载算法和最少连接算法的平均响应时间波动较大，其原因是这两种算法都未考虑请求的执行时间，仿真过程中如果队列中有执行时间较长的任务，则会导致队列中后面的请求的响应时间增大，导致产生波动。3）轮询算法的平均响应时间波动最大，分析其原因是该算法既未考虑服务器的负载状况，也未考虑任务的执行时间，导致服务器的负载不均衡，使得所有并发用户的平均响应时间产生较大波动。

图3 100用户并发访问平均响应时间波动Fig.3 The average response time fluctuations of 100 concurrent users

图4是在不同的并发用户数并发访问情况下，采用不同的负载均衡算法服务的平均响应时间的对比。从图中可以看出，本文提出的算法总能更快地返回用户请求的数据，因为它同时考虑了服务器负载状态和请求的等待时间及执行时间，随着并发用户数的增大，本算法的效果更加明显。

图4 不同并发用户访问平均响应时间Fig.4 The average response time of different concurrent users

由以上测试结果可见，使用RRPSA算法可以明显的缩短系统响应时间，减小大用户量并发访问下服务平均响应时间的波动，提高地图服务器场的并发处理能力，具有较好的稳定性、并发性和抗负载能力。

4 结论

本文分析了传统负载均衡算法的缺点，针对大用户量并发访问的情况进行分析，提出了一种基于任务响应比优先调度的WebGIS动态负载均衡算法，解决了目前WebGIS负载均衡算法并发处理能力低、不能平衡并发访问情况下所有用户的响应时间的问题；并通过建立测试环境，对算法的稳定性和并发性能进行了压力测试，测试结果验证了本算法的稳定性和高效性都优于传统的负载均衡算法。

［1］ 江飞，周保群，王惠芳.一种有效负载均衡的分布式 WebGIS体系结构模型［J］.微计算机信息，2006，22（28）：215－217.

［2］ 章文嵩.可伸缩网络服务的研究与实现［D］.长沙：国防科学技术大学，2000.1－15.

［3］ IQBAL S，CAREY G F.Performance analysis of dynamic load balancing algorithms with variable［J］.Parallel and Distributed Computing，2005，65：934.

［4］ DOWN D G，LEWIS M E.Dynamic load balancing in parallel queueing systems：Stability and optimal control［J］.European Journal of Operational Research，2006，168：509.

［5］ 朱江，张立立，曾志明，等.WebGIS服务器场的负载平衡算法设计［J］.计算机工程，2006，32（9）：94－95.

［6］ 李忠民，喻占武，朱莉，基于空间数据内容的动态负载均衡方法［J］.武汉大学学报（信息科学版），2009，34（5）：622－624.

［7］ 郭明强，黄颖，谢忠.一种基于服务器场的分布式 WebGIS计算模型设计与实现［J］.地理与地理信息科学，2008，24（6）：12－15.

［8］ 黄颖，谢忠，吴亮，等.基于聚类调度负载均衡的 WebGIS模型［J］.中国地质大学学报（地球科学），2010，35（3）：407－414.