劉恩海，李 偉，張素琪，董永峰，方新春

（1.河北工業(yè)大學 計算機科學與軟件學院，天津300401；2.天津大學 電子信息工程學院，天津300072；3.河北工業(yè)大學 電氣工程學院，天津300401）

0 引 言

在這個網絡飛速發(fā)展的時代，文件管理網絡化的趨勢越來越明顯，以往傳統(tǒng)、單一服務器的性能配置早已不能滿足對龐大的文件群的管理，此時集群技術應運而生。它是使用兩個或兩個以上的服務器連接在一起相互協(xié)作，共同完成某一任務的技術。應用負載均衡算法來研究如何將任務合理均衡的分配到各服務器上，才能使系統(tǒng)達到最優(yōu)。目前最常用的是周期性動態(tài)反饋負載均衡算法［1］，它周期性的更新各節(jié)的負載信息，按某種規(guī)則將其進行分組，然后將請求依次分發(fā)到負載最輕的一組節(jié)點上進行處理。分析了其優(yōu)缺點后，本文在周期性動態(tài)反饋算法的基礎之上，加入了對請求文件自身的負載情況的考慮，然后結合服務器的實時負載，更加準確的估計了當前的系統(tǒng)情況，從而更均衡地將文件分配到合適的服務器上進行處理，并在獲取負載信息時采用定量更新原則。最后在現(xiàn)有的系統(tǒng)中設計、實現(xiàn)了該均衡策略。實驗結果表明，該算法在實際系統(tǒng)應用中，減少了用戶等待時間，減輕了系統(tǒng)的網絡負擔，提高了系統(tǒng)吞吐量，達到了良好的負載均衡。

1 負載均衡算法簡介

1.1 常見的負載均衡算法

負載均衡算法按其分配策略可分為靜態(tài)和動態(tài)負載均衡算法。靜態(tài)負載均衡是在服務觸發(fā)之前就設定好了分配原則，在請求處理過程中不再考慮任何變化的情況；動態(tài)負載均衡是在系統(tǒng)運行過程中根據各個節(jié)點的資源利用情況，動態(tài)的調整分配給每個節(jié)點請求任務。優(yōu)點是可以根據節(jié)點的實時負載調整請求的分配，具有更大的靈活性；缺點則是頻繁的與各節(jié)點進行交互，增加了網絡負擔。而在實際應用中，各節(jié)點的瞬間負載變化比較大，靜態(tài)算法的均衡效果會比較差，因此，怎樣更好的實現(xiàn)動態(tài)負載均衡是當前研究的重點。目前常見的網絡負載均衡算法有以下幾種［2－4］：

（1）輪轉法：屬于靜態(tài)算法，簡單快捷。假設有N個節(jié)點，所有的請求輪流分配給集群中的各個服務器，從1到N然后重新開始。因此可以提前預知節(jié)點的負載分布。由于不考慮各節(jié)點之間的差異，所以輪轉法適用在集群中所有節(jié)點的處理能力和性能大體相同的情況。

（2）權重輪轉法：較輪轉法有了一定的進步，它給各節(jié)點按照其不同的處理能力設定了不同的權值，使其能夠接受相應權值數的服務請求。將該算法應用于請求處理的任務長度大致相同的情況時，是比較簡單、高效的，但是將其應用于任務長度差別較大的場合時，就會造成節(jié)點間負載的不均衡。

（3）最少連接法：是最簡單的動態(tài)算法，記錄了目前各系統(tǒng)所有的活躍連接數，使其代表當前系統(tǒng)的負載情況。然后系統(tǒng)把每一個新的任務分配到當前連接數最少的節(jié)點上，充分利用其系統(tǒng)資源，從而更好的實現(xiàn)負載均衡。這種算法比較適用于長時處理的請求服務，如FTP。

（4）最快響應法：記錄到每一個節(jié)點的網絡響應時間，并將下一個到達的連接請求分配給響應時間最短的節(jié)點。這種方法能較好的反映出當前節(jié)點的負載情況。

（5）處理能力均衡法：它綜合考慮節(jié)點系統(tǒng)的處理能力及當前的網絡情況，得出一個負載值，使其對節(jié)點的負載評估更加準確。然后根據此值將請求任務分發(fā)到負載最輕的節(jié)點上進行處理。比較適用于在應用層實施負載均衡。

1.2 周期性動態(tài)反饋負載均衡算法

周期性動態(tài)反饋負載均衡算法［5］是一些中小型應用系統(tǒng)目前常用的一種負載均衡算法，它的主要流程是主服務器周期性的收集節(jié)點服務器的各項負載信息，據其將各節(jié)點進行輕載、適載、重載的隊列劃分，然后在隊列中將各節(jié)點按權值進行排序，最后將并發(fā)請求依次分配到輕載隊列的各個節(jié)點上進行處理。它汲取了以上幾種算法的優(yōu)勢，但還是存在一些不足［2］：

（1）文件上傳策略中沒有考慮上傳文件的數量和大小，即文件負載量，如果依舊遵循先來先服務的原則，會可能發(fā)生將文件負載大的請求分配到負載量較重的服務器上，而文件負載小的分配到負載量較輕的服務器上，從而造成負載失衡。

（2）信息收集策略中收集參數時，以往的算法中只考慮了CPU利用率和內存利用率，但是不同類型的請求對服務器各項指標的要求是不一樣的，有的請求需要大量的計算或者繁瑣的與數據庫交互等操作，此時就要求CPU的性能高一些；而有的請求是讀取或寫入大量不同類型的文件，這就要求網絡帶寬和磁盤讀寫速度性能高一些，所以在參數的選擇上應根據實際情況多加考慮。

（3）負載更新策略中采用的周期性更新［5］中，周期的長短不好掌控，周期過長不能及時反映各節(jié)點的負載情況，造成負載失衡；周期過短又會因為服務期間頻繁的交互，產生大量額外的網絡負擔。

2 改進的動態(tài)反饋負載均衡算法

針對以上問題，提出了一種改進的動態(tài)反饋負載均衡算法。下面將從文件上傳策略、信息收集策略、負載更新策略三方面進行說明：

（1）文件上傳策略 引入了文件負載量這一概念，將上傳請求按照指定的公式計算出文件負載量，然后把任務請求隊列按負載量進行排序，以此為其分配服務節(jié)點。在頁面嵌入小的程序，在上傳文件時觸發(fā)，將除文件以外的信息發(fā)給web主服務器，然后主服務器通過負載均衡分配算法將節(jié)點服務器的IP和端口返回，使用異步調用的方法再將文件傳給節(jié)點服務器完成上傳操作，這樣主服務器不用把文件完全讀完在進行處理，既減輕了主服務器的壓力，又可以縮短用戶等待響應的時間。

（2）信息收集策略 結合文件的特點，主要收集節(jié)點的cpu利用率、內存利用率、磁盤讀寫速度、網絡速率幾項信息來計算節(jié)點服務器的負載量。收集的系統(tǒng)參數，采用C＃編程，java調用的方法，如圖1所示。

圖1 java調用C＃圖解

系統(tǒng)中有很多可用的計數器類別，常用的有緩存（cache）、內 存 （memory）、對 象 （objects）、 物 理 磁 盤（physical disk）、進程 （process）、處理器 （processor）、服務器 （server）、系統(tǒng) （system）和線程 （thread）等類別。

（3）更新策略 將以往的定時更新，改為定量更新。當給服務器分隊列后，當某節(jié)點負載從輕載、適載、重載隊列之間轉換時，再向主服務器發(fā)出更新請求，減少了與主服務器的交互，降低了定時更新時產生的大量額外的開銷，同時也能及時向主服務器反應自己的負載情況。

此外，節(jié)點服務器向主服務器發(fā)送負載信息時使用對象的序列化和反序列化的方法進行傳送 （socket網絡通信方式）?？梢园褜ο蟮淖止?jié)序列永久地保存到硬盤上，通常存放在一個文件中，并在網絡上傳送對象的字節(jié)序列。

基于改進的動態(tài)反饋負載均衡算法進行系統(tǒng)設計，其結構［7］主要包括三部分：Web主服務器、客戶端以及節(jié)點群 （存儲服務器）。Web主服務器主要負責收集各節(jié)點的實時負載量并將其分組，根據負載均衡機制分配各請求到適合的節(jié)點上；節(jié)點群中各節(jié)點主要實時收集自己的負載信息，并上傳給Web主服務器、負責文件的接收和存儲。系統(tǒng)框架如圖2所示。

圖2 系統(tǒng)框架

2.1 算法中相關參數的確定和計算方法

根據改進的動態(tài)反饋負載均衡算法，定義幾個變量［8，9］：

（1）計算各節(jié)點的實時負載量RL （i）

RL （i）：由節(jié)點的當前運行狀況計算得出。本文選擇CPU使用率和CPU個數的乘積、進程數量占用率、內存使用率、磁盤I／O占用率、網絡帶寬使用率幾個參數來計算實時負載量

其中，Ri（i＝1，2，3…）為各參數權值，ΣRi＝1，參數對性能的影響越大，權值越大。（對于文件上傳而言，磁盤讀寫速度和網絡帶寬要求較高）

（2）計算各節(jié)點的最大負載量 （處理能力）MAXL （i）

MAXL （i）：由節(jié)點的硬件配置決定。本文選擇CPU主頻和CPU個數的乘積、最大進程數、內存大小、最大磁盤容量、最大網絡帶寬使用率幾個參數來計算最大負載量。

由于各參數單位不一致，某些參數水平相差很大，例如內存為2G，但是網絡帶寬可能為1000M／bps，如果直接用原始數據值進行分析，就會突出數值較高的參數在整體計算中的作用，相對削弱了數值較低的參數的影響。因此，為了保證結果的可靠性，需要對原始數據進行標準化處理。

數據標準化就是由于各指標的度量單位不同，為了能夠將各指標都參與評價計算中，它通過函數變換去除了數據不同單位、不同量級的限制，將其轉化成無量綱的純數值并映射到某個數值區(qū)間內。本文選用最常見的標準化處理方法，即Z標準化 （標準差標準化）。公式如下

式中：L——參數標準化前的數值，L′——參數標準化后的數值，μ——所有參數數據的均值，σ——所有參數數據的標準差。對各參數進行標準化后，再計算最大負載量，公式如下

其中，Ri（i＝1，2，3…）為各參數權值，ΣRi＝1，參數對性能的影響越大，權值越大。

（3）計算上傳文件的負載量Pi

FSi：上傳文件的大小，F(xiàn)Ni：上傳文件的數量，需要根據以上計算請求的負載量Pi，首先計算

定義首次上傳的RL （i）為MRL （i），α為輕載因子，β重載因子。一般論文中α取45%，β取85%。需要在測試中反復求證。

（5）計算各節(jié)點的權值WL （i）

2.2 算法描述

算法步驟具體描述如下：

（1）各節(jié)點服務器首次收集自身的負載信息并計算實時負載量RL （i）發(fā)送到主服務器，主服務器根據相關公式劃分為輕載、適載、重載三個隊列；

（2）各節(jié)點服務器收集自身的硬件配置信息并計算最大負載量MAXL （i）發(fā)送至主服務器，主服務器根據權值公式計算相應權值WL （i），在隊列中對其進行排序；

（3）各節(jié)點周期性更新負載信息，并計算實時負載量RL （i），判斷實時負載量是否跨隊列，是，轉到 （4）；否，則周期性執(zhí)行本步驟；

（4）將RL （i）發(fā)送到主服務器，主服務器重新為其劃分隊列；

（5）是否有文件請求到來，是，轉到 （6）；否，等待；

（6）獲取上傳文件的負載量發(fā)送到主服務器，主服務器將其加入到上傳隊列中，并按一定規(guī)則進行排序，然后依次將隊列中的請求循環(huán)分配到輕載隊列中的各節(jié)點上，并向客戶端返回服務節(jié)點的IP和Port端口號，完成上傳操作。

3 算法性能測試與分析

3.1 測試指標

為了考察負載均衡算法的效率，考慮兩個測試指標［10］：一是應答響應時間，瀏覽器向Web服務器提交一個請求到完成響應之間的總時間；二是平均吞吐量，是指單位時間內Web服務器成功處理的HTTP頁面或HTTP請求數量。平均吞吐量越高，表示系統(tǒng)在單位時間內能處理的請求越多，系統(tǒng)的并發(fā)處理能力越強，系統(tǒng)的性能也就越好。

3.2 測試環(huán)境

在實驗室搭建一個集群平臺［11］，選擇三臺性能不同的服務器組成負載均衡集群系統(tǒng)進行實驗。服務器配置如表1所示。使用Badboy（錄制腳本）＋Jmeter測試工具，通過與已有算法的對比來驗證新算法的效果。其物理布局如圖3所示。

圖3 測試環(huán)境布局

表1 服務器配置一覽表

3.3 測試結果

（1）響應時間

響應時間對比圖，如圖4所示。

圖4 響應時間對比

注：橫軸是并發(fā)連接數，縱軸是上傳完成的時間 （單位：秒），并發(fā)上傳的是20M的文件。

參數R1＝0.15，R2＝0.1，R3＝0.15，R4＝0.3，R5＝0.3，α＝0.45，β＝0.85。

根據圖4所示，在并發(fā)連接數較少時 （50、100），三種算法的響應時間相差不多，但是隨著并發(fā)連接數的繼續(xù)增加，本算法的優(yōu)勢越來越明顯。對客戶的請求作出快速的響應，提供了更好的服務。

（2）平均吞吐量

根據圖5所示，系統(tǒng)平均吞吐量隨著并發(fā)連接數的持續(xù)增加，本算法的優(yōu)勢才逐漸顯現(xiàn)出來。因為負載均衡是解決高并發(fā)量帶來的壓力，所以低并發(fā)時，使用負載均衡沒有什么明顯的效果。

圖5 平均吞吐量對比

4 結束語

通過分析總結現(xiàn)有的靜態(tài)負載均衡算法和動態(tài)負載均衡算法所存在的不足，本文綜合兩者的優(yōu)點提出了一種改進的集中式綜合負載動態(tài)反饋的負載均衡算法。首先把節(jié)點服務器分成輕載、適載、重載三組隊列，隊列內采用權重輪轉算法；其次，加入對上傳請求負載量的考慮，能更好的將負載量重的請求分配到負載較輕的服務器上；并且改變定時更新為定量更新，減少了節(jié)點服務器與主服務器進行頻繁的交互而帶來的網絡帶寬的消耗，同時也能及時反映當時的負載情況。實驗結果表明，最終達到了較好的負載均衡效果。

［1］ZHOU Songquan.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.］

［2］TONG Ruixia.Research on cluster load balancing algorithm based on dynamic feedback mechanism ［D］.Wuhan：Wuhan University of Technology，2011 （5）：8－24 （in Chinese）.［童瑞霞.基于動態(tài)反饋機制的集群負載均衡算法研究 ［D］.武漢：武漢理工大學，2011 （5）：8－24.］

［3］LIU Hanbang.Feedback mechanism based on load balancing improve algorithm research ［D］.Qingdao：Qingdao Technological University，2010 （6）：8－26 （in Chinese）. ［劉漢邦.一種基于反饋機制的負載均衡改進算法研究 ［D］.青島：青島理工大學，2010 （6）：8－26.］

［4］SHI Hongyan.An improved strategy for load balancing in cluster nodes ［D］.Beijing：Beijing Technology and Business University，2010：13－21 （in Chinese）.［史鴻雁.一種改進集群節(jié)點負載均衡的策略 ［D］.北京：北京工商大學，2010：13－21.］

［5］LI Kun，WANG Baijie.Research on load balancing of web－server system and comparison of algorithms ［J］.Computer and Moderni－zation，2009 （8）：7－10 （in Chinese）.［李坤，王百杰.服務器集群負載均衡技術研究及算法比較 ［J］.計算機與現(xiàn)代化，2009 （8）：7－10.］

［6］DENG Chengyu，ZHANG Jiantao，LIU Yongshan.Research on dynamic load balancing strategy and corresponding model［J］.Computer Engineering and Applications，2011，47 （8）：131－134 （in Chinese）.［鄧成玉，章劍濤，劉永山.動態(tài)負載均衡策略及相關模型研究 ［J］.計算機工程與應用，2011，47（8）：131－134.］

［7］ZHANG Congping，YIN Jianwei.Dynamic load balancing algorithm of distributed file system ［J］.Journal of Chinese Computer Systems，2011，32 （7）：1424－1426 （in Chinese）.［張聰萍，尹建偉.分布式文件系統(tǒng)的動態(tài)負載均衡算法 ［J］.小型微型計算機系統(tǒng)，2011，32 （7）：1424－1426.］

［8］WANG Chunjuan，DONG Lili，JIA Li.Load balance algorithm for web cluster system ［J］.Computer Engineering，2010，36（2）：102－104 （in Chinese）.［王春娟，董麗麗，賈麗.Web集群系統(tǒng)的負載均衡算法 ［J］.計算機工程，2010，36 （2）：102－104.］

［9］CHEN Chao，ZHAO Yuelong，WANG Wenfeng，et al.Improved dynamic load balancing strategy based on feedback［J］.Computer Engineering，2010，36 （14）：34－36 （in Chinese）.［陳超，趙躍龍，王文豐，等.基于反饋的改進動態(tài)的集群負載 均 衡 策 略 ［J］.計算機工程，2010，36 （14）：34－36.］

［10］HU Lijun.Web cluster server load balancing and performance ptimization ［D］.Beijing：Beijing University of Posts and Telecommunications，2010：33－50 （in Chinese）.［胡 利 軍.Web集群服務器的負載均衡和性能優(yōu)化 ［D］.北京：北京郵電大學，2010：33－50.］

［11］SHEN Wei.Research and realization of an improved load balancing algorithm based on LVS cluster ［D］.Beijing：China University of Geosciences，2010：36－46 （in Chinese）.［申偉.基于LVS集群的一種負載均衡改進算法的研究與實現(xiàn) ［D］.北京：中國地質大學，2010：36－46.］