基于空间填充曲线的动态负载均衡算法

张沪寅，何 华，姚化强，叶 刚

（武汉大学 计算机学院，湖北 武汉430072）

0 引 言

在集群系统中，负载均衡是影响实际服务器并行处理性能的关键因素［1，2］。判断负载均衡效果的指标，通常为用户请求平均响应时间以及系统吞吐量。

目前国内外学者已对此问题做出了大量的研究工作，提出多种负载均衡的策略，如轮询调度算法、最小连接调度算法、响应比优先调度算法以及在此基础上的各种加权调度算法等。但是，这些算法有的不能真实地反映服务器负载情况，有的自身会产生较大开销，以至于无法达到理想的负载均衡效果。在大规模集群系统中，更加考验着负载均衡的性能［3，4］。因此，本文以大规模集群系统为考察对象，在控制算法本身开销的基础上，尽可能全面地考虑服务器各方面的负载指标，以达到较优的均衡效果。

1 研究现状

目前主流的负载均衡策略可分为静态和动态两类［5－7］。静态的负载均衡策略主要有轮询算法、加权轮询算法、目标地址散列算法、源地址散列算法等，其基本原理是依据固定的概率分配任务［5］。动态负载均衡会或多或少地考虑服务器的性能指标和实时负载指标，常见的有最小连接数算法、加权最小连接数算法、基于动态反馈的算法等。相对而言，静态的负载均衡策略实现简单，也不需要额外的系统开销，适用于访问量不大的系统。但数据表明通常情况下，动态负载均衡较静态负载均衡有30%～40%的性能提升［6］。动态负载均衡更具有实用价值，目前该领域国内外研究大都是针对动态负载均衡算法的改进，以充分利用服务器资源、及时响应用户请求。

实际应用较多的动态负载均衡策略是加权的最小连接数算法，以及在此基础上改进的基于动态反馈算法。假设一组由N 台服务器节点组成的集群，用S＝ ｛S0，S1，...，Sn－1｝表示，C（Si）表示第i个节点的连接数，W（Si）表示第i个节点的权值，则接收新请求的服务器节点C（Sm）的选择是基于判定式 （1）

即选择连接数与权重比值最小的服务器节点［8］。

但节点的连接数并不能准确反应服务器的负载情况，因此动态反馈算法对此做出了改进，考虑服务器节点的CPU 利用率L（Ci）、内存利用率L（Mi）、硬盘I／O 占用率L（Di）、网络带宽占用率L（Ni）。为了使服务器的负载情况用一维列表存储，使用了权重向量K＝ ｛K1，K2，K3，K4｝，服务器的负载量L（Si）由式 （2）得出

对于不同类型的服务器，服务器的各个负载指标对服务器的负载量的影响会有所不同，因此这里的权重向量是由管理员设置的。由此引出一个问题，该权重向量有时不能很好地反映服务器节点的负载，那么就需要管理员不断地调整这个权重向量，直到找到合适的一组为止，显然会给管理带来了许多麻烦。

2 基于空间填充曲线的负载均衡算法

2.1 Geohash算法

基于位置的服务 （location based service，LBS）系统中对于基于地理位置的周边资源的搜索，目前被广泛使用且高效的算法就是Geohash算法。该算法通过空间填充曲线的降维特性，将二维空间中的坐标点映射到一维区间，并且具有很好的可逆性，可以高效地找出当前地理位置周边的资源，大大缩小了搜索范围，实现快速准确定位的目标［9］。

Geohash算法原理：

（1）首先将纬度范围区间 ［－90，90］二分为 ［－90，0）和 ［0，90］两个区间，分别称为左区间、右区间。如果要编码的纬度位于左区间，则编码为0，如果要编码的纬度位于右区间，则编码为1；

（2）递归上述过程，不断编码，如图1 所示。最后总会确定维度在某个范围 （a，b）之间；

（3）同样的方法对精度进行递归，那么精度也会确定在某个范围 （c，d）之间；

（4）偶数位放经度编码，奇数位放纬度编码形成位置信息的交叉组码；

（5）最后将交叉组码进行Base32编码；

一个编码代表地理位置上的一片区域，编码相似则代表着位置相近。如果资源编码与当前位置编码越相似，代表着资源越近，如此可快速定位当前地理位置周边的资源，提高搜索效率［10］。

图1 Geohash编码过程

2.2 本文算法

针对动态负载均衡需要人工设定权重以及在大规模集群系统中无法快速定位到最优服务器的不足之处，本文在Geohash算法的思想基础上，将负载均衡算法做出了改进，使用空间填充曲线，将高维数组映射到一维阵列中，同时空间填充曲线能保证在高维空间上相邻的节点，在一维上的排列也是相邻的［5］。这样我们就可以同时考虑各个服务器节点多个负载指标了，不会发生因为权重的设置不合理而引起在长时间运行后出现负载严重倾斜的情况，使得各个服务器节点各尽其能［11，12］。

空间填充曲线是一种降低空间维度的方法，能将高维空间的点映射为一维区间中的点。通过经典线性索引结构存储这些一维区间中的点，能有效降低索引的复杂 度［11］。

本文算法首先使用空间填充曲线的降维特性，将由多个负载指标构成的高维空间坐标映射为一维区间编码，然后在一维编码中查找具有最优负载指标的服务器编码，大大加快了服务器节点筛选的效率，降低了算法的复杂度。空间填充曲线有多种，常用的有Hilbert曲线、Z 曲线和Gray曲线。由于Z 曲线生成算法简单、局部聚类特性良好，本文选用Z曲线来实现算法。

本文算法主要有两个步骤：一是利用Z 曲线降维原理对负载指标进行编码，二是查找最优编码 （最优编码代表性能最好的服务器编码）。

一组服务器节点S＝ ｛S0，S1，...，Sn－1｝，用Ci表示各个节点的CPU 利用率，Mi表示节点的内存利用率。而Ci和Mi取值都在 ［0，1］之间，即负载指标构成的空间范围为 ［0，0］～ ［1，1］。

对负载指标进行编码：本文对服务器节点Si的Ci和Mi这两个性能指标分别进行逼近编码。以Ci为例，步骤如下：

（1）将区间 ［0，1］二分为 ［0，0.5），［0.5，1］，称为左右区间，如果Ci落在左区间 ［0，0.5），则标记为0，落在右区间 ［0.5，1］，则标记为1；

（2）继 续 将 区 间 ［0，0.5）二 分 为 ［0，0.25），［0.25，0.5），如果Ci落在左区间 ［0，0.25），则标记为0，落在右区间 ［0.25，0.5），则标记为1；

（3）递归上述过程Ci总是属于某个区间 ［a，b］。随着每次迭代区间 ［a，b］不断缩小，并越来越逼近Ci。

（4）随着算法执行会产生一个二进制序列，序列的长度跟给定的区间划分次数有关。

同理可得到Mi的编码序列，然后偶数位放内存利用率编码，奇数位放CPU 利用率编码，进行交叉组码可得到最终编码Zi。

编码后可以获得此组服务器的编码Z＝ ｛Z0，Z1，…，Zn－1｝，本文将此编码简称为Z－hash码。在图2中反映了这个编码过程。

图2 Z－hash码的生成

查找最优编码：可以看出相邻的负载指标组成的点具有相似Z－hash 码，Z－hash 码与 ［0，0］的Z－hash 码越相近，则代表着具有该编码的服务器负载能力越强。因此通过查找距离 ［0，0］的Z－hash码最近的Z－hash码，即可找到负载能力最强的一组服务器节点。这里找出的是一组服务器节点，主要由于不同的服务器节点可能负载指标相同或相近，具有相同的Z－hash码。

从 ［0，0］的编码出发，不断扩大搜索范围，直至有服务器节点落入，则找到了最优编码，图3 为扩大搜索范围这个过程的示意。只要存在处于正常状态下的服务器，则一定能找到这个最优编码，而一个编码代表着一个区域，即可能多个服务器具有相同编码。如果此编码区域只有一台服务器，则此服务器入选；如包含多台服务器，则使用最小连接数作进一步筛选，找到最合适处理请求的服务器。

图3 寻找最优编码

引入空间填充曲线可在使用最小连接数之前，通过编码从大规模服务器集群系统中过滤出性能最优的服务器，有效地提高了负载均衡算法的效率。

3 算法的具体实现

3.1 负载均衡器端

负载均衡器端主要工作如下：①收集服务器端发来的负载指标；②使用空间填充曲线过滤出最优编码服务器；③使用最小连接算法确定目标服务器节点；④更新目标服务器连接数，转发请求。

集群系统中各个服务器节点会在一个固定周期T 内不同步地向负载均衡器端发送服务器的负载指标，包括CPU利用率、内存利用率、连接数以及Z－hash码等。均衡器端维护着一个存储各服务器负载指标的负载指标表，某一时刻的表内容如表1所示，每当收到服务器端发来的信息会更新此性能指标表。其中服务器状态，主要是由预设的性能指标阈值来判断，当指标超过阈值上限，服务器处于满负荷，服务器状态标记为0。负载均衡器端收到请求后，会在服务器状态为1 （服务器状态良好）的编码中查找代表最优负载能力的最优编码Z0，然后找出编码同为Z0的k个服务器节点。当k＞1 时，使用最小连接数算法确定出目标服务器节点，将请求转发到此服务器；当k＝1时，直接将请求转发到此服务器节点。当k＝0 时，表示集群系统暂时瘫痪，所有服务器处于满载状态。每次转发请求后，都会更新服务器性能指标表中此服务器节点的连接数，将其增加1，避免将请求不断发往此服务器，导致集群系统倾斜。

表1 服务器性能指标

3.2 服务器节点端

服务器节点端主要工作如下：

（1）设定CPU 利用的阀值上限为75%，内存利用率的阀值上限为90%；

（2）当时钟周期T 到达时获取各个负载指标，而当CPU 利用率或内存利用率指标值大于阈值上限时，将服务器状态标记为0 （服务器满负荷）；

（3）将CPU 利用率、内存利用率按以上原则编码为Zhash码；

（4）将CPU 利用率、内存利用率、连接数、服务器状态以及Z－hash码定期发往负载均衡器端；

（5）处理均衡器端转发来的请求。

由于Z－hash码的生成需要消耗一定的资源，而为减轻均衡器端的压力，将Z－hash编码放在服务器节点端，避免均衡器端成为系统的瓶颈［13，14］。

4 实验及分析

为评估本文算法的效果，搭建一个Web服务集群系统进行实验。在均衡策略上，分别实现了动态反馈算法和本文提出的基于空间填充曲线算法。其中动态反馈算法使用式（2）计算服务器负载量，且权重系数使用最常用的K＝｛0.35，0.25，0.2，0.2｝［5］。本次实验使用一台服务器作为负载均衡器，12台服务器作为后端服务器，所有服务器安装CentOS 6.x系统，并处于同一局域网中。使用一台装有WAS工具的客户机模拟用户发送请求。

本次实验分为6组进行，集群服务器数量分别为2台、4台、6台、8台、10台、12台。服务器每隔3s向均衡器发送自己的负载指标。客户机使用WAS工具模拟用户不断发出请求，持续时间为1分钟、强度为200。本次实验主要使用任务平均响应时间和系统吞吐量两个评价指标，两种均衡算法的测试结果如图4、图5所示。

图4 平均响应时间比较

图5 系统吞吐量比较

从图4和图5可以看出，随着集群规模的扩大，本文算法的均衡效果逐渐提升。当集群服务器节点数只有2台、4台、6台时，本文算法均衡效果无论从平均响应时间或系统吞吐量来看，相对于动态反馈算法较弱，但当服务器节点数量达到8台、10台、12台时本文算法均衡效果明显优于动态反馈算法。

出现此结果主要缘于本文算法首轮筛选效率很高，能快速从大量数据中定位到最优编码，而动态反馈算法每次都是从所有服务器节点做出筛选，这将造成额外开销，随着集群规模增大则效率降低。而在集群规模很小时，本文算法多出的一个编码过程会稍稍影响均衡效果，因此在服务器只有2台、4台、6台时，均衡效果较动态反馈弱。

通过具体的实验数据可知，与动态反馈算法相比，当服务器数量较小时本文算法均衡效果一般，而当集群规模扩大时，本文算法负载均衡效果明显改善。

5 结束语

本文针对一种动态反馈负载均衡算法进行了改进，提出应用空间填充曲线快速筛选负载性能最优服务器的编码，并使用最小连接数确定当前最适合处理请求的服务器节点。实验结果表明，相对于动态反馈算法，本文算法在集群规模较大时具有较好的负载效果。

本文为了控制算法开销，未考虑服务器的硬盘I／O 占用率和响应比等相关性能指标，未来研究工作中会合理加入考虑，以实现更完善的均衡方案。同时考虑服务器3个或者4个性能指标因子的时，可以尝试使用Hilbert填充曲线，在高维降维算法上或许可以取得较优效果。

［1］LIU Xu，MO Zeyao，CHAO Xiaolin.A one－dimensional load balancing method based on memory constraint and its application［J］.Chinese Journal of Computational Physics，2009，26（2）：184－190 （in Chinese）.［刘旭，莫则尧，曹小林.基于内存约束的一维负载平衡方法及其应用 ［J］.计算物理，2009，26 （2）：184－190.］

［2］Zhang Lin，Li Xiaoping，Su Yuan.A content－based dynamic load－balancing algorithm for heterogeneous Web server cluster［J］.Computer Science and Information Systems／ComSIS，2010，7 （1）：153－162.

［3］Khayyat Z，Awara K，Alonazi A，et al.Mizan：A system for dynamic load balancing in large－scale graph processing ［C］／／Proceedings of the 8th ACM European Conference on Computer Systems.ACM，2013：169－182.

［4］Clarke D，Lastovetsky A，Rychkov V.Dynamic load balancing of parallel computational iterative routines on platforms with memory heterogeneity ［C］／／Euro－Par Parallel Processing Workshops.Berlin：Springer Berlin Heidelberg，2011：41－50.

［5］ZHOU Songqun.An improved dynamic load－balancing algorithm for cluster ［J］.Computer and Modernization，2012（1）：135－139 （in Chinese）. ［周松泉.一种改进的集群动态负载均衡算法 ［J］.计算机与现代化，2012 （1）：135－139.］

［6］MAI Jingjing，GONG Hongyan，SONG Chunhe.Dynamic feedback load balancing strategy in cluster system ［J］.Computer Engineering，2008，34 （16）：114－118 （in Chinese）.［买京京，龚红艳，宋纯贺.集群系统中的动态反馈负载均衡策略 ［J］.计算机工程，2008，34 （16）：114－118］.

［7］WANG Hongbin.Research on adaptive load balancing scheduling strategy in Web cluster system ［D］.Changchun：Jilin University，2013 （in Chinese）.［王红斌.Web服务器集群系统的自适应负载均衡调度策略研究 ［D］.长春：吉林大学，2013.］

［8］LIU Shaofeng，DONG Jian，WU Zhibo.A dynamic－feedback scheduling algorithm for cluster load balancing based on priority queue［J］.Intelligent Computer and Applications，2012，2（4）：78－80 （in Chinese）. ［柳少锋，董剑，吴智博.一种基于优先级队列的集群动态反馈调度算法 ［J］.智能计算机与应用，2012，2 （4）：78－80.］

［9］YE Xiaorong，SHAO Qing.Mobile advertising system based on augmented reality and location－based services［J］.Science＆ Technology Review，2013，31 （4）：67－73 （in Chinese）.［叶小榕，邵晴.基于增强现实和位置服务的手机广告系统［J］.科技导报，2013，31 （4）：67－73.］

［10］JIN An，CHENG Chengqi，SONG Shushua.Regional query of area data based on Geohash ［J］.Geography and Geo－Information Science，2013，29 （5）：31－35 （in Chinese）.［金安，程承旗，宋树华，等.基于Geohash的面数据区域查询 ［J］.地理与地理信息科学，2013，29 （5）：31－35.］

［11］Harlacher DF，Klimach H，Roller S，et al.Dynamic load balancing for unstructured meshes on space－filling curves［C］／／IEEE 26th International Parallel and Distributed Processing Symposium Workshops ＆ PhD Forum，2012：1661－1669.

［12］Deng Y，Lau RWH.On delay adjustment for dynamic load balancing in distributed virtual environments ［J］.IEEE Transactions on Visualization and Computer Graphics，2012，18 （4）：529－537.

［13］Gawande DS，Dharmik RC，Panse C.A load balancing in grid environment ［J］.International Journal of Engineering Research and Application，2012，2 （2）：445－450.

［14］Li R，Zhang Y，Xu Z，et al.A Load－balancing method for network GISs in a heterogeneous cluster－based system using access density ［J］.Future Generation Computer Systems，2013，29 （2）：528－535.