动态负载均衡算法的基本过程包括：接收用户的并发请求，收集服务器的负载信息反馈至前段任务调度器，判定服务器的负载状态，选择最佳目标服务器处理用户的并发访问请求。本算法采用集中式调度策略，各地理信息服务节点实时监控各自服务器的负载信息，并以一定的周期反馈到前端服务器，然后基于阈值方法和RED算法判定节点的负载状态，获得节点的动态剩余处理能力，若节点过载，则实施有效警告；通过对地理信息服务进行分类(常规的地理信息服务类型分为地图浏览、查询分析、数据订阅与下载、目录与元数据服务等)，将某种类型地理信息服务与与具体的应用服务器组匹配起来，根据节点剩余处理能力动态确定多个节点的调度权值，节点剩余处理能力与调度权值成正比，节点当前负载与调度权值成反比，最后确定最佳目标服务器处理用户的并发访问请求。算法的应用模型图如图 1所示。

图  1  地理信息服务动态负载均衡算法应用模型

Figure 1.  Application Model of Geographical Information Service Load Balancing

当用户并发访问某一地理信息服务时，负载均衡算法要综合考虑服务节点能力和该服务节点服务器的实时负载值，根据文献[4, 9]研究结果，应包含4个服务器参数，分别为CPU使用率、内存使用率、网络带宽利用率和磁盘I/O利用率，服务请求经路由器转发至任务调度器，调度器以一定周期收集负载信息，并依据负载因素的加权比例值确定最佳目标服务器。目标服务器作出响应之后会将服务内容经由交换机和路由器直接分发至用户。

在一个周期T内，用户请求的某一地理信息服务为s，在此过程中负载均衡步骤如图 2所示。

图  2  动态负载均衡算法的步骤

Figure 2.  Process of Load Balancing

收集的负载信息包括地理信息服务类型，节点的工作能力和实时负载情况，负载信息动态反馈周期为T。本算法采用分布式收集负载信息，即由集群中的服务节点动态实时监测本身的负载信息，然后周期性动态反馈到前端任务调度器。

定义W={w₁, w₂, …, w_n}为集群中的服务器集合，w_i(1≤i≤n)表示集群中的第i个服务器(节点)，n表示节点个数。

服务器w_i的当前负载L_i=(L_i^cpu, L_i^I/O, L_i^mem, L_i^net)，L_i^cpu、L_i^I/O、L_i^mem、L_i^net分别表示服务节点w_i当前CPU占用率，磁盘I/O占用率、内存占用率和网络带宽占用率。

服务器w_i的节点处理能力C_i=(C_i^cpu, C_i^I/O, C_i^mem, C_i^net)，C_i^cpu、C_i^I/O、C_i^mem、C_i^net分别表示服务节点w_i的CPU速率、磁盘I/O速率、内存容量和网络吞吐量。

地理信息服务类型集合S={s₁, s₂, s₃, s₄}，s_j(1≤j≤4)表示第j个地理信息服务类型，其中，s₁、s₂、s₃、s₄分别表示地图浏览、查询分析、数据订阅与下载、目录与元数据等4类服务。

同一服务器在提供不同类型的地理信息服务时，对自身负载信息造成的影响也不同^[5]。根据不同地理信息服务类型占用系统资源的差异，为每一种地理信息服务类型设定一个权值向量a_j，a_j=(a_j^cpu, a_j^I/O, a_j^mem, a_j^net)，|a_j|=1，j∈[0, 3]，a_j权值分量越高，表示该地理信息服务对对应资源的依赖越强。

设服务器w_i提供的服务类型为s_j，C_i为w_i的节点处理能力，L_i为w_i的负载利用情况，以C_m=(C_m^cpu, C_m^I/O, C_m^mem, C_m^net)作为基准服务器的处理能力，以a_j表示s_j地理信息服务对应权重向量，则服务器w_i的实时负载比例值ω_i为：

引入基准服务器C_m是因为在异构环境下，不同服务器的工作能力不一致，故需要归一化。由式(1)可知，ω_i越大，说明服务器w_i的负载越大。

负载状态判定是指根据服务节点的负载值，判断该节点是空闲状态还是过载状态。本文采用RED算法来判定服务节点的负载状态，以避免负载抖动现象的发生(负载抖动是指因为服务节点被标记为过载状态，导致其他服务器为该节点承担额外的负载)。随机早期检测(random early detection，RED)起初在分组交换网络中提出，用于最大程度降低拥塞现象的产生。基于RED算法判定负载状态的基本步骤如下。

1) 若服务节点负载值低于阈值L_low，将该节点标记为过载状态的概率值为0；

2) 若服务节点负载值高于阈值L_high，将该节点标记为过载状态的概率值为1；

3) 若服务节点的负载值介于L_low和L_high之间，将该节点标记为过载状态的概率值为介于0和1之间，而不是绝对地标记为空闲或过载状态，此时服务器的实时负载介于L_low和L_high之间。

设服务器节点w_i被标记为过载状态的概率为P，节点实时负载比例值为ω_i，则有：

式中，k为常数，L_low和L_high分别为负载最小和最大阈值。除设定负载最小和最大阈值外，还需要为四个单项负载参数设定最大阈值，当节点的某一单项负载值超过最大阈值，则判定节点为过载状态。

设当前节点实时负载比例值为ω_i，P_i为当前地理信息服务类型请求转发到节点i的概率值，P_i的计算公式为：

式中，n为服务器集群中总的服务器数。基于加权概率的目标服务器选择方法能够取得较好的负载均衡度。

将本文所设计负载均衡算法应用于某大型地理信息服务系统的实验验证环境中，本文实验系统基于该实验验证环境而在局域网(网络带宽为1 000 Mb/s)搭建的小型服务系统，由两台数据存储服务器和1台元数据服务器组成数据存储服务器集群，主要用于存储实验数据；由两台数据库服务器组成数据库服务器集群，主要用于管理实验数据；由8台地理信息应用服务器组成应用服务器集群(后期试验过程中可动态扩展)，前文所述4类地理信息服务(地图浏览、查询分析、数据订阅与下载、目录与元数据服务)每一类分配两台服务器编为一个服务器组，共4个服务器组；1个负载均衡器和两台Web服务器组成Web服务器集群，4台PC机用于模拟大规模用户并发访问，具体架构如图 3所示。

图  3  实验系统的总体架构

Figure 3.  Whole Structure of Experimental System

负载均衡系统主要实现本文所提出的负载均衡算法并实现地理信息服务的智能调度，负载均衡系统的功能模块组成与流程如图 4所示，负载均衡系统包括服务接收、服务调度、负载监测和负载判定等4个模块。

图  4  负载均衡系统的功能与流程

Figure 4.  Function and Flow of Load Balancing System

服务接收模块部署在负载均衡器上，完成地理信息服务的接收，所有用户请求的地理信息服务被加入到任务队列中；服务调度模块也部署在负载均衡器上，主要是根据前文所述算法确定目标服务器，完成服务的调度；负载监测模块部署在地理信息应用服务器集群的所有服务器上，完成各服务器负载信息的收集；负载判定模块也部署在地理信息应用服务器集群的所有服务器上，基于负载查询模块收集到的负载信息，完成负载加权值的计算与负载状态的判定。

实验数据选择某地区1:100万范围内所有系列比例尺矢量数据和25 m格网的数字高程模型，用于查询分析和数据下载服务，在1:100万范围内1~16级的地图瓦片数据(由该区域内矢量数据生成)、影像瓦片数据和地形瓦片数据，用于地图浏览服务，数据量共计10 TB左右。

据上文所述，本文所设计的负载均衡算法需要确定多个参数和阈值，包括地理信息服务类型对应的权值向量a_j、动态反馈周期T、基准服务器的处理能力C_m、阈值L_low和L_high等4个单项参数对应的最大阈值。通过前期大量的压力实验发现，地理信息浏览与数据下载服务占用的带宽资源最大，磁盘输入输出资源次之，而查询分析与目录元数据服务占用的CPU资源最大，故确定的a_j权值分量(cpu为计算能力；I/O为输入/输入能力；mem为存储能力；net为网络带宽)如表 1所示。

本实验中，地理信息应用服务器集群中的配置都一致，配置均为两颗主频1.9 GHz 6核CPU，内存为64 G，因此基准服务器的处理能力C_m与服务器固有的处理能力C_i相同，则式(1)可表示为：

在每个测试机器上安装大规模用户并发访问模拟客户端，然后启动所有测试机器，对某一特定区域第15级的地图瓦片同时进行漫游浏览操作，负载均衡算法采用本文提出的算法，设置初始并发访问数为20个，每隔10 s钟重复进行一次并发访问，共持续5 min，计算系统的平均响应时间和系统的吞吐量；依据上述步骤，增加并发访问数到40、60、80、100、120、140、160、180、200，记录系统的平均响应时间、系统的总吞吐量和响应服务器的地址，图 5是并发用户数和两个浏览服务器所贡献的系统吞吐量对应关系图。

图  5  系统吞吐量与并发用户数的关系

Figure 5.  Relationships Between Throughput and Concurrent Count

在实际应用中，会经常出现两种以上服务组合运行的情况，因此，依据上述步骤采用本文算法和文献[8]提出的一致性哈希算法分别测试在不同并发访问数下地图浏览与查询分析(以坡度分析为例)组合，数据订阅与下载(下载的数据量约100M)和目录与元数据服务组合对应的平均响应时间。图 6为两类组合地理信息服务、两种不同算法在不同并发访问数下系统的平均响应时间。

图  6  实验结果

Figure 6.  Results of Experiment

分析图 5和图 6可得出以下结论。

1) 对于图 5，当系统的用户并发数在0~60个左右增加时，系统总的吞吐量增加迅速，且主要由浏览服务器1提供服务，当用户并发数超过80时，服务器1不能满足要求，负载均衡系统起作用，部分服务由浏览服务器2提供，服务器1提供的数据量略有下降，但总的吞吐量增加；

2) 对于图 6(a)，地理信息浏览和查询分析组合服务，在相同的并发数下，本文设计的负载均衡算法与一致性哈希算法相比，在0~120个并发用户数下，系统响应时间基本一致，但当超过120时，本文方法响应时间比一致性哈希算法短，一致性哈希算法响应时间增长不稳定。主要原因是：地理信息浏览服务采用的访问地图瓦片的形式，而地图瓦片是一种静态的地图缓存，本文算法将地理信息服务类型与对应服务器组匹配，提高了缓存命中率，同时在服务调度时综合考虑了服务器的工作能力，基于RED算法较为准确地判定服务器的负载状态，并在一定周期内对服务进行了基于加权概率的调度，而一致性哈希方法当并发用户数增大到一定程度会导致服务器节点分配不均衡。综合来看，本文算法能更合理准确地将服务请求分配到负载较轻节点，减少了系统的响应时间。

3) 对于图 6(b)，数据下载和元数据组合服务，当并发数在160以下时，本文设计的算法优势不明显，主要原因是这两类服务的响应时间除与负载均衡算法和应用服务器有关外，很大程度上还与数据库服务器有关，但当并发用户数据急剧增加时，负载均衡对系统的响应时间影响逐渐增加，本文设计的算法与一致性哈希算法相比优势逐渐体现。

负载均衡算法是地理信息服务智能化调度的核心与关键，为研制具有自主可控、高可靠、高可用和易扩展地理信息服务系统，本文主要研究了一种适用于网络化地理信息服务系统的负载均衡算法，设计了小型的地理信息服务实验系统，实验结果表明，基于该算法能够有效实现地理信息服务资源合理调度，减少系统响应时间，能支撑多用户高并发访问条件下在线地理信息服务的运行。