張滬寅，何 華，姚化強，葉 剛

（武漢大學 計算機學院，湖北 武漢430072）

0 引 言

在集群系統(tǒng)中，負載均衡是影響實際服務器并行處理性能的關(guān)鍵因素［1，2］。判斷負載均衡效果的指標，通常為用戶請求平均響應時間以及系統(tǒng)吞吐量。

目前國內(nèi)外學者已對此問題做出了大量的研究工作，提出多種負載均衡的策略，如輪詢調(diào)度算法、最小連接調(diào)度算法、響應比優(yōu)先調(diào)度算法以及在此基礎(chǔ)上的各種加權(quán)調(diào)度算法等。但是，這些算法有的不能真實地反映服務器負載情況，有的自身會產(chǎn)生較大開銷，以至于無法達到理想的負載均衡效果。在大規(guī)模集群系統(tǒng)中，更加考驗著負載均衡的性能［3，4］。因此，本文以大規(guī)模集群系統(tǒng)為考察對象，在控制算法本身開銷的基礎(chǔ)上，盡可能全面地考慮服務器各方面的負載指標，以達到較優(yōu)的均衡效果。

1 研究現(xiàn)狀

目前主流的負載均衡策略可分為靜態(tài)和動態(tài)兩類［5－7］。靜態(tài)的負載均衡策略主要有輪詢算法、加權(quán)輪詢算法、目標地址散列算法、源地址散列算法等，其基本原理是依據(jù)固定的概率分配任務［5］。動態(tài)負載均衡會或多或少地考慮服務器的性能指標和實時負載指標，常見的有最小連接數(shù)算法、加權(quán)最小連接數(shù)算法、基于動態(tài)反饋的算法等。相對而言，靜態(tài)的負載均衡策略實現(xiàn)簡單，也不需要額外的系統(tǒng)開銷，適用于訪問量不大的系統(tǒng)。但數(shù)據(jù)表明通常情況下，動態(tài)負載均衡較靜態(tài)負載均衡有30%～40%的性能提升［6］。動態(tài)負載均衡更具有實用價值，目前該領(lǐng)域國內(nèi)外研究大都是針對動態(tài)負載均衡算法的改進，以充分利用服務器資源、及時響應用戶請求。

實際應用較多的動態(tài)負載均衡策略是加權(quán)的最小連接數(shù)算法，以及在此基礎(chǔ)上改進的基于動態(tài)反饋算法。假設一組由N 臺服務器節(jié)點組成的集群，用S＝ ｛S0，S1，...，Sn－1｝表示，C（Si）表示第i個節(jié)點的連接數(shù)，W（Si）表示第i個節(jié)點的權(quán)值，則接收新請求的服務器節(jié)點C（Sm）的選擇是基于判定式 （1）

即選擇連接數(shù)與權(quán)重比值最小的服務器節(jié)點［8］。

但節(jié)點的連接數(shù)并不能準確反應服務器的負載情況，因此動態(tài)反饋算法對此做出了改進，考慮服務器節(jié)點的CPU 利用率L（Ci）、內(nèi)存利用率L（Mi）、硬盤I／O 占用率L（Di）、網(wǎng)絡帶寬占用率L（Ni）。為了使服務器的負載情況用一維列表存儲，使用了權(quán)重向量K＝ ｛K1，K2，K3，K4｝，服務器的負載量L（Si）由式 （2）得出

對于不同類型的服務器，服務器的各個負載指標對服務器的負載量的影響會有所不同，因此這里的權(quán)重向量是由管理員設置的。由此引出一個問題，該權(quán)重向量有時不能很好地反映服務器節(jié)點的負載，那么就需要管理員不斷地調(diào)整這個權(quán)重向量，直到找到合適的一組為止，顯然會給管理帶來了許多麻煩。

2 基于空間填充曲線的負載均衡算法

2.1 Geohash算法

基于位置的服務 （location based service，LBS）系統(tǒng)中對于基于地理位置的周邊資源的搜索，目前被廣泛使用且高效的算法就是Geohash算法。該算法通過空間填充曲線的降維特性，將二維空間中的坐標點映射到一維區(qū)間，并且具有很好的可逆性，可以高效地找出當前地理位置周邊的資源，大大縮小了搜索范圍，實現(xiàn)快速準確定位的目標［9］。

Geohash算法原理：

（1）首先將緯度范圍區(qū)間 ［－90，90］二分為 ［－90，0）和 ［0，90］兩個區(qū)間，分別稱為左區(qū)間、右區(qū)間。如果要編碼的緯度位于左區(qū)間，則編碼為0，如果要編碼的緯度位于右區(qū)間，則編碼為1；

（2）遞歸上述過程，不斷編碼，如圖1 所示。最后總會確定維度在某個范圍 （a，b）之間；

（3）同樣的方法對精度進行遞歸，那么精度也會確定在某個范圍 （c，d）之間；

（4）偶數(shù)位放經(jīng)度編碼，奇數(shù)位放緯度編碼形成位置信息的交叉組碼；

（5）最后將交叉組碼進行Base32編碼；

一個編碼代表地理位置上的一片區(qū)域，編碼相似則代表著位置相近。如果資源編碼與當前位置編碼越相似，代表著資源越近，如此可快速定位當前地理位置周邊的資源，提高搜索效率［10］。

圖1 Geohash編碼過程

2.2 本文算法

針對動態(tài)負載均衡需要人工設定權(quán)重以及在大規(guī)模集群系統(tǒng)中無法快速定位到最優(yōu)服務器的不足之處，本文在Geohash算法的思想基礎(chǔ)上，將負載均衡算法做出了改進，使用空間填充曲線，將高維數(shù)組映射到一維陣列中，同時空間填充曲線能保證在高維空間上相鄰的節(jié)點，在一維上的排列也是相鄰的［5］。這樣我們就可以同時考慮各個服務器節(jié)點多個負載指標了，不會發(fā)生因為權(quán)重的設置不合理而引起在長時間運行后出現(xiàn)負載嚴重傾斜的情況，使得各個服務器節(jié)點各盡其能［11，12］。

空間填充曲線是一種降低空間維度的方法，能將高維空間的點映射為一維區(qū)間中的點。通過經(jīng)典線性索引結(jié)構(gòu)存儲這些一維區(qū)間中的點，能有效降低索引的復雜 度［11］。

本文算法首先使用空間填充曲線的降維特性，將由多個負載指標構(gòu)成的高維空間坐標映射為一維區(qū)間編碼，然后在一維編碼中查找具有最優(yōu)負載指標的服務器編碼，大大加快了服務器節(jié)點篩選的效率，降低了算法的復雜度?？臻g填充曲線有多種，常用的有Hilbert曲線、Z 曲線和Gray曲線。由于Z 曲線生成算法簡單、局部聚類特性良好，本文選用Z曲線來實現(xiàn)算法。

本文算法主要有兩個步驟：一是利用Z 曲線降維原理對負載指標進行編碼，二是查找最優(yōu)編碼 （最優(yōu)編碼代表性能最好的服務器編碼）。

一組服務器節(jié)點S＝ ｛S0，S1，...，Sn－1｝，用Ci表示各個節(jié)點的CPU 利用率，Mi表示節(jié)點的內(nèi)存利用率。而Ci和Mi取值都在 ［0，1］之間，即負載指標構(gòu)成的空間范圍為 ［0，0］～ ［1，1］。

對負載指標進行編碼：本文對服務器節(jié)點Si的Ci和Mi這兩個性能指標分別進行逼近編碼。以Ci為例，步驟如下：

（1）將區(qū)間 ［0，1］二分為 ［0，0.5），［0.5，1］，稱為左右區(qū)間，如果Ci落在左區(qū)間 ［0，0.5），則標記為0，落在右區(qū)間 ［0.5，1］，則標記為1；

（2）繼 續(xù) 將 區(qū) 間 ［0，0.5）二 分 為 ［0，0.25），［0.25，0.5），如果Ci落在左區(qū)間 ［0，0.25），則標記為0，落在右區(qū)間 ［0.25，0.5），則標記為1；

（3）遞歸上述過程Ci總是屬于某個區(qū)間 ［a，b］。隨著每次迭代區(qū)間 ［a，b］不斷縮小，并越來越逼近Ci。

（4）隨著算法執(zhí)行會產(chǎn)生一個二進制序列，序列的長度跟給定的區(qū)間劃分次數(shù)有關(guān)。

同理可得到Mi的編碼序列，然后偶數(shù)位放內(nèi)存利用率編碼，奇數(shù)位放CPU 利用率編碼，進行交叉組碼可得到最終編碼Zi。

編碼后可以獲得此組服務器的編碼Z＝ ｛Z0，Z1，…，Zn－1｝，本文將此編碼簡稱為Z－h(huán)ash碼。在圖2中反映了這個編碼過程。

圖2 Z－h(huán)ash碼的生成

查找最優(yōu)編碼：可以看出相鄰的負載指標組成的點具有相似Z－h(huán)ash 碼，Z－h(huán)ash 碼與 ［0，0］的Z－h(huán)ash 碼越相近，則代表著具有該編碼的服務器負載能力越強。因此通過查找距離 ［0，0］的Z－h(huán)ash碼最近的Z－h(huán)ash碼，即可找到負載能力最強的一組服務器節(jié)點。這里找出的是一組服務器節(jié)點，主要由于不同的服務器節(jié)點可能負載指標相同或相近，具有相同的Z－h(huán)ash碼。

從 ［0，0］的編碼出發(fā)，不斷擴大搜索范圍，直至有服務器節(jié)點落入，則找到了最優(yōu)編碼，圖3 為擴大搜索范圍這個過程的示意。只要存在處于正常狀態(tài)下的服務器，則一定能找到這個最優(yōu)編碼，而一個編碼代表著一個區(qū)域，即可能多個服務器具有相同編碼。如果此編碼區(qū)域只有一臺服務器，則此服務器入選；如包含多臺服務器，則使用最小連接數(shù)作進一步篩選，找到最合適處理請求的服務器。

圖3 尋找最優(yōu)編碼

引入空間填充曲線可在使用最小連接數(shù)之前，通過編碼從大規(guī)模服務器集群系統(tǒng)中過濾出性能最優(yōu)的服務器，有效地提高了負載均衡算法的效率。

3 算法的具體實現(xiàn)

3.1 負載均衡器端

負載均衡器端主要工作如下：①收集服務器端發(fā)來的負載指標；②使用空間填充曲線過濾出最優(yōu)編碼服務器；③使用最小連接算法確定目標服務器節(jié)點；④更新目標服務器連接數(shù)，轉(zhuǎn)發(fā)請求。

集群系統(tǒng)中各個服務器節(jié)點會在一個固定周期T 內(nèi)不同步地向負載均衡器端發(fā)送服務器的負載指標，包括CPU利用率、內(nèi)存利用率、連接數(shù)以及Z－h(huán)ash碼等。均衡器端維護著一個存儲各服務器負載指標的負載指標表，某一時刻的表內(nèi)容如表1所示，每當收到服務器端發(fā)來的信息會更新此性能指標表。其中服務器狀態(tài)，主要是由預設的性能指標閾值來判斷，當指標超過閾值上限，服務器處于滿負荷，服務器狀態(tài)標記為0。負載均衡器端收到請求后，會在服務器狀態(tài)為1 （服務器狀態(tài)良好）的編碼中查找代表最優(yōu)負載能力的最優(yōu)編碼Z0，然后找出編碼同為Z0的k個服務器節(jié)點。當k＞1 時，使用最小連接數(shù)算法確定出目標服務器節(jié)點，將請求轉(zhuǎn)發(fā)到此服務器；當k＝1時，直接將請求轉(zhuǎn)發(fā)到此服務器節(jié)點。當k＝0 時，表示集群系統(tǒng)暫時癱瘓，所有服務器處于滿載狀態(tài)。每次轉(zhuǎn)發(fā)請求后，都會更新服務器性能指標表中此服務器節(jié)點的連接數(shù)，將其增加1，避免將請求不斷發(fā)往此服務器，導致集群系統(tǒng)傾斜。

表1 服務器性能指標

3.2 服務器節(jié)點端

服務器節(jié)點端主要工作如下：

（1）設定CPU 利用的閥值上限為75%，內(nèi)存利用率的閥值上限為90%；

（2）當時鐘周期T 到達時獲取各個負載指標，而當CPU 利用率或內(nèi)存利用率指標值大于閾值上限時，將服務器狀態(tài)標記為0 （服務器滿負荷）；

（3）將CPU 利用率、內(nèi)存利用率按以上原則編碼為Zhash碼；

（4）將CPU 利用率、內(nèi)存利用率、連接數(shù)、服務器狀態(tài)以及Z－h(huán)ash碼定期發(fā)往負載均衡器端；

（5）處理均衡器端轉(zhuǎn)發(fā)來的請求。

由于Z－h(huán)ash碼的生成需要消耗一定的資源，而為減輕均衡器端的壓力，將Z－h(huán)ash編碼放在服務器節(jié)點端，避免均衡器端成為系統(tǒng)的瓶頸［13，14］。

4 實驗及分析

為評估本文算法的效果，搭建一個Web服務集群系統(tǒng)進行實驗。在均衡策略上，分別實現(xiàn)了動態(tài)反饋算法和本文提出的基于空間填充曲線算法。其中動態(tài)反饋算法使用式（2）計算服務器負載量，且權(quán)重系數(shù)使用最常用的K＝｛0.35，0.25，0.2，0.2｝［5］。本次實驗使用一臺服務器作為負載均衡器，12臺服務器作為后端服務器，所有服務器安裝CentOS 6.x系統(tǒng)，并處于同一局域網(wǎng)中。使用一臺裝有WAS工具的客戶機模擬用戶發(fā)送請求。

本次實驗分為6組進行，集群服務器數(shù)量分別為2臺、4臺、6臺、8臺、10臺、12臺。服務器每隔3s向均衡器發(fā)送自己的負載指標?？蛻魴C使用WAS工具模擬用戶不斷發(fā)出請求，持續(xù)時間為1分鐘、強度為200。本次實驗主要使用任務平均響應時間和系統(tǒng)吞吐量兩個評價指標，兩種均衡算法的測試結(jié)果如圖4、圖5所示。

圖4 平均響應時間比較

圖5 系統(tǒng)吞吐量比較

從圖4和圖5可以看出，隨著集群規(guī)模的擴大，本文算法的均衡效果逐漸提升。當集群服務器節(jié)點數(shù)只有2臺、4臺、6臺時，本文算法均衡效果無論從平均響應時間或系統(tǒng)吞吐量來看，相對于動態(tài)反饋算法較弱，但當服務器節(jié)點數(shù)量達到8臺、10臺、12臺時本文算法均衡效果明顯優(yōu)于動態(tài)反饋算法。

出現(xiàn)此結(jié)果主要緣于本文算法首輪篩選效率很高，能快速從大量數(shù)據(jù)中定位到最優(yōu)編碼，而動態(tài)反饋算法每次都是從所有服務器節(jié)點做出篩選，這將造成額外開銷，隨著集群規(guī)模增大則效率降低。而在集群規(guī)模很小時，本文算法多出的一個編碼過程會稍稍影響均衡效果，因此在服務器只有2臺、4臺、6臺時，均衡效果較動態(tài)反饋弱。

通過具體的實驗數(shù)據(jù)可知，與動態(tài)反饋算法相比，當服務器數(shù)量較小時本文算法均衡效果一般，而當集群規(guī)模擴大時，本文算法負載均衡效果明顯改善。

5 結(jié)束語

本文針對一種動態(tài)反饋負載均衡算法進行了改進，提出應用空間填充曲線快速篩選負載性能最優(yōu)服務器的編碼，并使用最小連接數(shù)確定當前最適合處理請求的服務器節(jié)點。實驗結(jié)果表明，相對于動態(tài)反饋算法，本文算法在集群規(guī)模較大時具有較好的負載效果。

本文為了控制算法開銷，未考慮服務器的硬盤I／O 占用率和響應比等相關(guān)性能指標，未來研究工作中會合理加入考慮，以實現(xiàn)更完善的均衡方案。同時考慮服務器3個或者4個性能指標因子的時，可以嘗試使用Hilbert填充曲線，在高維降維算法上或許可以取得較優(yōu)效果。

［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）.［劉旭，莫則堯，曹小林.基于內(nèi)存約束的一維負載平衡方法及其應用 ［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）. ［周松泉.一種改進的集群動態(tài)負載均衡算法 ［J］.計算機與現(xiàn)代化，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）.［買京京，龔紅艷，宋純賀.集群系統(tǒng)中的動態(tài)反饋負載均衡策略 ［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服務器集群系統(tǒng)的自適應負載均衡調(diào)度策略研究 ［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）. ［柳少鋒，董劍，吳智博.一種基于優(yōu)先級隊列的集群動態(tài)反饋調(diào)度算法 ［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）.［葉小榕，邵晴.基于增強現(xiàn)實和位置服務的手機廣告系統(tǒng)［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的面數(shù)據(jù)區(qū)域查詢 ［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.