集群文件服務(wù)系統(tǒng)中的負(fù)載均衡算法的研究

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

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

0 引 言

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

1 負(fù)載均衡算法簡介

1.1 常見的負(fù)載均衡算法

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

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

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

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

（4）最快響應(yīng)法：記錄到每一個節(jié)點(diǎn)的網(wǎng)絡(luò)響應(yīng)時間，并將下一個到達(dá)的連接請求分配給響應(yīng)時間最短的節(jié)點(diǎn)。這種方法能較好的反映出當(dāng)前節(jié)點(diǎn)的負(fù)載情況。

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

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

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

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

（2）信息收集策略中收集參數(shù)時，以往的算法中只考慮了CPU利用率和內(nèi)存利用率，但是不同類型的請求對服務(wù)器各項指標(biāo)的要求是不一樣的，有的請求需要大量的計算或者繁瑣的與數(shù)據(jù)庫交互等操作，此時就要求CPU的性能高一些；而有的請求是讀取或?qū)懭氪罅坎煌愋偷奈募@就要求網(wǎng)絡(luò)帶寬和磁盤讀寫速度性能高一些，所以在參數(shù)的選擇上應(yīng)根據(jù)實(shí)際情況多加考慮。

（3）負(fù)載更新策略中采用的周期性更新［5］中，周期的長短不好掌控，周期過長不能及時反映各節(jié)點(diǎn)的負(fù)載情況，造成負(fù)載失衡；周期過短又會因?yàn)榉?wù)期間頻繁的交互，產(chǎn)生大量額外的網(wǎng)絡(luò)負(fù)擔(dān)。

2 改進(jìn)的動態(tài)反饋負(fù)載均衡算法

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

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

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

圖1 java調(diào)用C＃圖解

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

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

此外，節(jié)點(diǎn)服務(wù)器向主服務(wù)器發(fā)送負(fù)載信息時使用對象的序列化和反序列化的方法進(jìn)行傳送 （socket網(wǎng)絡(luò)通信方式）。可以把對象的字節(jié)序列永久地保存到硬盤上，通常存放在一個文件中，并在網(wǎng)絡(luò)上傳送對象的字節(jié)序列。

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

圖2 系統(tǒng)框架

2.1 算法中相關(guān)參數(shù)的確定和計算方法

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

（1）計算各節(jié)點(diǎn)的實(shí)時負(fù)載量RL （i）

RL （i）：由節(jié)點(diǎn)的當(dāng)前運(yùn)行狀況計算得出。本文選擇CPU使用率和CPU個數(shù)的乘積、進(jìn)程數(shù)量占用率、內(nèi)存使用率、磁盤I／O占用率、網(wǎng)絡(luò)帶寬使用率幾個參數(shù)來計算實(shí)時負(fù)載量

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

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

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

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

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

式中：L——參數(shù)標(biāo)準(zhǔn)化前的數(shù)值，L′——參數(shù)標(biāo)準(zhǔn)化后的數(shù)值，μ——所有參數(shù)數(shù)據(jù)的均值，σ——所有參數(shù)數(shù)據(jù)的標(biāo)準(zhǔn)差。對各參數(shù)進(jìn)行標(biāo)準(zhǔn)化后，再計算最大負(fù)載量，公式如下

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

（3）計算上傳文件的負(fù)載量Pi

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

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

（5）計算各節(jié)點(diǎn)的權(quán)值WL （i）

2.2 算法描述

算法步驟具體描述如下：

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

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

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

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

（5）是否有文件請求到來，是，轉(zhuǎn)到 （6）；否，等待；

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

3 算法性能測試與分析

3.1 測試指標(biāo)

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

3.2 測試環(huán)境

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

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

表1 服務(wù)器配置一覽表

3.3 測試結(jié)果

（1）響應(yīng)時間

響應(yīng)時間對比圖，如圖4所示。

圖4 響應(yīng)時間對比

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

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

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

（2）平均吞吐量

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

圖5 平均吞吐量對比

4 結(jié)束語

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

［1］ZHOU Songquan.An improved dynamic load－balancing algorithm for cluster［J］.Computer and Modernization，2012 （1）：135－139 （in Chinese）.［周松泉.一種改進(jìn)的集群動態(tài)負(fù)載均衡算法 ［J］.計算機(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)反饋機(jī)制的集群負(fù)載均衡算法研究 ［D］.武漢：武漢理工大學(xué)，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）. ［劉漢邦.一種基于反饋機(jī)制的負(fù)載均衡改進(jìn)算法研究 ［D］.青島：青島理工大學(xué)，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）.［史鴻雁.一種改進(jìn)集群節(jié)點(diǎn)負(fù)載均衡的策略 ［D］.北京：北京工商大學(xué)，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）.［李坤，王百杰.服務(wù)器集群負(fù)載均衡技術(shù)研究及算法比較 ［J］.計算機(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)負(fù)載均衡策略及相關(guān)模型研究 ［J］.計算機(jī)工程與應(yīng)用，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)負(fù)載均衡算法 ［J］.小型微型計算機(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)的負(fù)載均衡算法 ［J］.計算機(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）.［陳超，趙躍龍，王文豐，等.基于反饋的改進(jìn)動態(tài)的集群負(fù)載 均 衡 策 略 ［J］.計算機(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集群服務(wù)器的負(fù)載均衡和性能優(yōu)化 ［D］.北京：北京郵電大學(xué)，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集群的一種負(fù)載均衡改進(jìn)算法的研究與實(shí)現(xiàn) ［D］.北京：中國地質(zhì)大學(xué)，2010：36－46.］