留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

一种地理信息服务动态负载均衡算法

李鹤元 安晓亚 陈刚 金澄

李鹤元, 安晓亚, 陈刚, 金澄. 一种地理信息服务动态负载均衡算法[J]. 武汉大学学报 ● 信息科学版, 2016, 41(11): 1524-1529. doi: 10.13203/j.whugis20140633
引用本文: 李鹤元, 安晓亚, 陈刚, 金澄. 一种地理信息服务动态负载均衡算法[J]. 武汉大学学报 ● 信息科学版, 2016, 41(11): 1524-1529. doi: 10.13203/j.whugis20140633
LI Heyuan, AN Xiaoya, CHEN Gang, JIN Cheng. A Geographical Information Service Load Balancing Algorithm[J]. Geomatics and Information Science of Wuhan University, 2016, 41(11): 1524-1529. doi: 10.13203/j.whugis20140633
Citation: LI Heyuan, AN Xiaoya, CHEN Gang, JIN Cheng. A Geographical Information Service Load Balancing Algorithm[J]. Geomatics and Information Science of Wuhan University, 2016, 41(11): 1524-1529. doi: 10.13203/j.whugis20140633

一种地理信息服务动态负载均衡算法

doi: 10.13203/j.whugis20140633
基金项目: 

国家自然科学基金 41201469

国家自然科学基金 41071297

地理信息工程国家重点实验室开放研究基金 SKLGIE2013-Z-4-1

地理信息工程国家重点实验室开放研究基金 SKLGIE2013-M-4-5

详细信息
    作者简介:

    李鹤元, 博士生, 工程师, 主要从事地理信息服务理论与方法研究。2625845532@qq.com

  • 中图分类号: P208;TP391

A Geographical Information Service Load Balancing Algorithm

Funds: 

The National Natural Science Foundation of China 41201469

The National Natural Science Foundation of China 41071297

the Open Research Fund Program of State key Laboratory of Geo-information Engineering SKLGIE2013-Z-4-1

the Open Research Fund Program of State key Laboratory of Geo-information Engineering SKLGIE2013-M-4-5

More Information
    Author Bio:

    LI Heyuan, PhD, engineer, specializes in the theories and methods of inconsistency handling of spatial database updating. E-mail:2625845532@qq.com

图(6) / 表(1)
计量
  • 文章访问数:  872
  • HTML全文浏览量:  38
  • PDF下载量:  319
  • 被引次数: 0
出版历程
  • 收稿日期:  2015-09-09
  • 刊出日期:  2016-11-05

一种地理信息服务动态负载均衡算法

doi: 10.13203/j.whugis20140633
    基金项目:

    国家自然科学基金 41201469

    国家自然科学基金 41071297

    地理信息工程国家重点实验室开放研究基金 SKLGIE2013-Z-4-1

    地理信息工程国家重点实验室开放研究基金 SKLGIE2013-M-4-5

    作者简介:

    李鹤元, 博士生, 工程师, 主要从事地理信息服务理论与方法研究。2625845532@qq.com

  • 中图分类号: P208;TP391

摘要: 随着网络地理信息服务技术的发展,如何基于负载均衡实现地理信息服务资源的智能化调度,从而提高服务系统的并发访问能力是当前研究的重点。提出一种动态负载均衡算法,首先将不同的地理信息服务类型与对应的服务器组相匹配,将RED算法与双阈值方法有效结合判定服务节点的负载状态,并在一定周期内对服务进行了基于加权概率的调度。最后搭建了一个基于服务器集群的实验系统,实验验证了本文方法的有效性。

English Abstract

李鹤元, 安晓亚, 陈刚, 金澄. 一种地理信息服务动态负载均衡算法[J]. 武汉大学学报 ● 信息科学版, 2016, 41(11): 1524-1529. doi: 10.13203/j.whugis20140633
引用本文: 李鹤元, 安晓亚, 陈刚, 金澄. 一种地理信息服务动态负载均衡算法[J]. 武汉大学学报 ● 信息科学版, 2016, 41(11): 1524-1529. doi: 10.13203/j.whugis20140633
LI Heyuan, AN Xiaoya, CHEN Gang, JIN Cheng. A Geographical Information Service Load Balancing Algorithm[J]. Geomatics and Information Science of Wuhan University, 2016, 41(11): 1524-1529. doi: 10.13203/j.whugis20140633
Citation: LI Heyuan, AN Xiaoya, CHEN Gang, JIN Cheng. A Geographical Information Service Load Balancing Algorithm[J]. Geomatics and Information Science of Wuhan University, 2016, 41(11): 1524-1529. doi: 10.13203/j.whugis20140633
  • 地理信息在政府管理决策、国防安全和人民生活改善等方面发挥着越来越重要的作用。随着我国经济和国防信息化建设的不断推进,各级机构和公众对权威、可靠的地理信息服务需求与日俱增,迫切要求实现多尺度、多类型地理信息资源的综合利用与在线服务[1, 2]。当前网络地理信息服务系统正面临着不可预测的并发数增长、系统响应及容量限制等因素的挑战,地理信息服务的可伸缩性与可用性正在受到越来越多的关注[3]。服务的动态负载均衡是实现对集群内各服务节点资源进行虚拟化管理和智能化调度,以便提高集群系统的并发访问能力。与一般的信息服务相比,地理信息具有多分辨率、数据量大、数据可视化要求高等特点,针对网络地理信息服务负载均衡特点的研究颇丰。文献[4]提出了一种基于代价的分布式负载均衡算法,旨在提高服务器响应用户请求速度,但主要针对地形瓦片数据的提取、传输和显示问题,未考虑其他地理信息服务的负载均衡问题;文献[5, 6]提出了一种基于遗传算法的网络GIS集群服务器动态负载均衡算法,将基于服务器状态和基于内容的负载均衡算法综合起来考虑,但算法也主要适用于地形数据的漫游服务;文献[7]提出了基于空间数据内容的动态负载均衡方法,其根据空间数据地理位置的相关性和访问热度,对服务器进行动态分组,但该方法主要针对栅格数据;文献[8]利用一致性哈希算法对Web服务器集群进行负载均衡调度,存在的主要问题是存在一定的概率造成服务器节点的分配不均衡,使得整个集群负载不均衡。

    本文提出了一种面向多服务节点的动态负载均衡算法。根据集群内服务节点状态,针对4类地理信息服务(地图浏览、查询分析、数据订阅与下载、目录与元数据服务),利用设计的负载均衡算法,将大量的并发访问业务分担到多个处理节点分别进行处理,减少用户等待响应的时间,从而达到多服务节点的地理信息服务虚拟化与全局负载均衡的目标。

    • 动态负载均衡算法的基本过程包括:接收用户的并发请求,收集服务器的负载信息反馈至前段任务调度器,判定服务器的负载状态,选择最佳目标服务器处理用户的并发访问请求。本算法采用集中式调度策略,各地理信息服务节点实时监控各自服务器的负载信息,并以一定的周期反馈到前端服务器,然后基于阈值方法和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={w1, w2, …, wn}为集群中的服务器集合,wi(1≤in)表示集群中的第i个服务器(节点),n表示节点个数。

      服务器wi的当前负载Li=(Licpu, LiI/O, Limem, Linet),LicpuLiI/OLimemLinet分别表示服务节点wi当前CPU占用率,磁盘I/O占用率、内存占用率和网络带宽占用率。

      服务器wi的节点处理能力Ci=(Cicpu, CiI/O, Cimem, Cinet),CicpuCiI/OCimemCinet分别表示服务节点wi的CPU速率、磁盘I/O速率、内存容量和网络吞吐量。

      地理信息服务类型集合S={s1, s2, s3, s4},sj(1≤j≤4)表示第j个地理信息服务类型,其中,s1s2s3s4分别表示地图浏览、查询分析、数据订阅与下载、目录与元数据等4类服务。

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

      设服务器wi提供的服务类型为sjCiwi的节点处理能力,Liwi的负载利用情况,以Cm=(Cmcpu, CmI/O, Cmmem, Cmnet)作为基准服务器的处理能力,以aj表示sj地理信息服务对应权重向量,则服务器wi的实时负载比例值ωi为:

      (1)

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

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

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

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

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

      设服务器节点wi被标记为过载状态的概率为P,节点实时负载比例值为ωi,则有:

      (2)

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

    • 设当前节点实时负载比例值为ωiPi为当前地理信息服务类型请求转发到节点i的概率值,Pi的计算公式为:

      (3)

      式中,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左右。

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

      表 1  aj的权值分量

      Table 1.  Weight of aj

      cpu I/O mem net
      a1 0.1 0.3 0.2 0.4
      a2 0.4 0.2 0.3 0.1
      a3 0.1 0.3 0.2 0.4
      a4 0.4 0.2 0.1 0.3

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

      (4)
    • 在每个测试机器上安装大规模用户并发访问模拟客户端,然后启动所有测试机器,对某一特定区域第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以下时,本文设计的算法优势不明显,主要原因是这两类服务的响应时间除与负载均衡算法和应用服务器有关外,很大程度上还与数据库服务器有关,但当并发用户数据急剧增加时,负载均衡对系统的响应时间影响逐渐增加,本文设计的算法与一致性哈希算法相比优势逐渐体现。

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

参考文献 (9)

目录

    /

    返回文章
    返回