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

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

（武漢大學 計算機學院，湖北 武漢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.