陳 偉

?

基于負(fù)反饋的負(fù)載均衡算法實(shí)現(xiàn)

陳 偉*

(宿州職業(yè)技術(shù)學(xué)院 網(wǎng)絡(luò)中心,安徽 宿州, 234101)

LVS現(xiàn)有的負(fù)載均衡算法在分配服務(wù)器請求時(shí)大多都是基于固定權(quán)值, 使得LVS集群系統(tǒng)在長時(shí)間高負(fù)荷運(yùn)行后會(huì)出現(xiàn)負(fù)載傾斜. 為此, 給出了一種改進(jìn)的負(fù)載均衡算法, 該算法通過引入負(fù)反饋機(jī)制, 充分考慮服務(wù)器權(quán)值的動(dòng)態(tài)調(diào)節(jié), 更準(zhǔn)確地反映了各服務(wù)器的真實(shí)負(fù)載情況. 測試結(jié)果表明, 該算法優(yōu)于原有算法.

集群; 負(fù)載均衡; 負(fù)反饋; LVS

隨著站點(diǎn)服務(wù)日益多樣化, 網(wǎng)絡(luò)服務(wù)器的訪問數(shù)量急劇增加. 為確保網(wǎng)絡(luò)服務(wù)的正常提供, 構(gòu)建高性能的WEB站點(diǎn), 服務(wù)器集群系統(tǒng)應(yīng)運(yùn)而生. 把多臺(tái)服務(wù)器通過局域網(wǎng)連接成集群系統(tǒng), 以提高其整體性能和處理能力, 并具高可伸縮性、高可用性和高性價(jià)比[1].

集群系統(tǒng)的關(guān)鍵是實(shí)現(xiàn)集群內(nèi)部服務(wù)器之間的負(fù)載均衡. 所謂負(fù)載均衡, 就是通過重新分配集群內(nèi)每個(gè)服務(wù)器的負(fù)載, 使得各個(gè)服務(wù)器的負(fù)載相對均衡, 從而提高整體的服務(wù)性能并縮短客戶請求的響應(yīng)時(shí)間, 提高系統(tǒng)的資源利用率.

常用的LVS集群系統(tǒng)自帶的調(diào)度算法是基于固定權(quán)值的靜態(tài)算法, 無法根據(jù)服務(wù)器的實(shí)際負(fù)載情況進(jìn)行動(dòng)態(tài)調(diào)節(jié), 易出現(xiàn)負(fù)載傾斜現(xiàn)象. 近年來對于動(dòng)態(tài)負(fù)載均衡的研究成為熱點(diǎn). 文獻(xiàn)[2]提出了一種集群系統(tǒng)的透明動(dòng)態(tài)反饋負(fù)載均衡算法; 文獻(xiàn)[3]提出了動(dòng)態(tài)負(fù)載均衡算法理論模型; 文獻(xiàn)[4]針對Web服務(wù)器集群系統(tǒng)中負(fù)載動(dòng)態(tài)變化特性提出了一種臨界加速遞減動(dòng)態(tài)請求負(fù)載分配算法. 在動(dòng)態(tài)負(fù)載均衡理論基礎(chǔ)上, 本文提出了一種基于負(fù)反饋的負(fù)載均衡算法, 該算法引入負(fù)反饋機(jī)制, 根據(jù)負(fù)載狀況和節(jié)點(diǎn)處理能力動(dòng)態(tài)分配請求, 有效地實(shí)現(xiàn)了集群負(fù)載均衡.

1 負(fù)反饋理論的引入

負(fù)反饋就是使輸出起到對輸入相反的作用, 使整個(gè)系統(tǒng)的輸出與系統(tǒng)期望的誤差逐漸減小, 整個(gè)系統(tǒng)趨于穩(wěn)定[5]. 負(fù)反饋的本質(zhì)在于設(shè)計(jì)一個(gè)目標(biāo)差不斷減小的過程, 在這種控制中, 系統(tǒng)把控制后的輸出目標(biāo)與控制目標(biāo)相比較, 得到目標(biāo)差這一反饋信息, 以此為據(jù), 選擇合適的參量值, 使得目標(biāo)差在一次次控制中逐漸變小, 最后達(dá)到控制的目的[6].

LVS集群系統(tǒng)中節(jié)點(diǎn)服務(wù)器的權(quán)值是管理員進(jìn)行輸入的固定數(shù)值, 權(quán)值大的服務(wù)器具有更高的性能和請求處理能力. 服務(wù)器在固定的權(quán)值下, 處理負(fù)載請求時(shí)并不能夠根據(jù)當(dāng)前節(jié)點(diǎn)的實(shí)際負(fù)載情況進(jìn)行自我調(diào)節(jié), 這樣節(jié)點(diǎn)服務(wù)器在長時(shí)間的高負(fù)荷下, 勢必造成集群系統(tǒng)負(fù)載的傾斜.

因此, 引入負(fù)反饋的機(jī)制, 對高負(fù)載的服務(wù)器進(jìn)行動(dòng)態(tài)權(quán)值調(diào)整, 減少其任務(wù)的分配量. 相反, 對于負(fù)載較低的服務(wù)器, 它還能夠在短時(shí)間內(nèi)處理更多的請求, 故可適當(dāng)增加任務(wù)分配量, 這樣才能使集群系統(tǒng)的負(fù)載逐漸趨向于平衡.

2 負(fù)反饋模型

合理的調(diào)度算法是實(shí)現(xiàn)負(fù)載均衡的關(guān)鍵, 本文主要從研究調(diào)度算法入手, 來解決LVS負(fù)載均衡問題. 為防止負(fù)載傾斜的出現(xiàn), 需要設(shè)計(jì)出動(dòng)態(tài)的均衡算法, 該算法要能夠根據(jù)實(shí)際負(fù)載情況和節(jié)點(diǎn)處理能力, 對節(jié)點(diǎn)權(quán)值進(jìn)行動(dòng)態(tài)調(diào)整, 從而選擇合適的節(jié)點(diǎn)進(jìn)行請求分配. 根據(jù)負(fù)反饋機(jī)制設(shè)計(jì)如圖1控制模型.

圖1 負(fù)反饋模型

其中為權(quán)值, 描述節(jié)點(diǎn)的處理能力,是負(fù)載量值, 描述節(jié)點(diǎn)的當(dāng)前實(shí)際負(fù)載.(,)是運(yùn)行在調(diào)度器上的權(quán)值調(diào)整模塊, 用來動(dòng)態(tài)調(diào)整節(jié)點(diǎn)權(quán)值. 客戶機(jī)發(fā)出請求時(shí), 負(fù)載均衡調(diào)度器LB向服務(wù)器發(fā)送請求報(bào)文, 服務(wù)器池中的每個(gè)服務(wù)器都要向LB反饋其當(dāng)前負(fù)載量值, LB的(,)模塊會(huì)根據(jù)反饋回來的負(fù)載量值和當(dāng)前節(jié)點(diǎn)的權(quán)值重新計(jì)算出新權(quán)值′, 再根據(jù)′的值來分配用戶請求. 當(dāng)某個(gè)服務(wù)器負(fù)載量較大時(shí),(,)模塊會(huì)調(diào)減其權(quán)值, 新的權(quán)值′ ＜, 這樣服務(wù)器只能分配較少的客戶請求,較小時(shí)可增加其權(quán)值, 此時(shí)′＞, 說明可分配更多的請求給該服務(wù)器. 這樣就避免了某些節(jié)點(diǎn)負(fù)載過高的情況發(fā)生, 提高了系統(tǒng)的吞吐量, 充分發(fā)揮了服務(wù)器的處理能力, 從而實(shí)現(xiàn)動(dòng)態(tài)的負(fù)載均衡.

圖2 負(fù)反饋算法的工作方式

3 負(fù)反饋算法設(shè)計(jì)

負(fù)反饋算法的工作方式如圖2所示. 本文采用LVS中IP負(fù)載均衡的VS/DR模式構(gòu)建集群體系. 負(fù)載均衡器安裝在Linux操作系統(tǒng)上. Monitor進(jìn)程運(yùn)行均衡器用戶空間, Agent監(jiān)控進(jìn)程運(yùn)行在真實(shí)服務(wù)器上用于搜集服務(wù)器的負(fù)載信息并反饋給Monitor進(jìn)程用來來計(jì)算負(fù)載量值[7], 根據(jù)負(fù)載量和當(dāng)前權(quán)值重新計(jì)算出新權(quán)值′, 如果和′的差值超過設(shè)置的閥值, 則把新的′寫入到ipVS調(diào)度中去, 否則繼續(xù)保持原有調(diào)度.

3.1 負(fù)載量值L的計(jì)算

負(fù)載量值是服務(wù)器實(shí)際負(fù)載情況的體現(xiàn). 負(fù)反饋均衡算法主要從服務(wù)器系統(tǒng)資源使用狀況和對請求的響應(yīng)時(shí)間兩個(gè)方面入手來實(shí)現(xiàn)服務(wù)器節(jié)點(diǎn)負(fù)載量值的計(jì)算.

影響服務(wù)器性能的指標(biāo)有很多, 本文主要選取CPU、內(nèi)存、帶寬、磁盤I/O占用4個(gè)指標(biāo)[8]. 用CPU占用率CPU、內(nèi)存占用率MEM、磁盤I/O占用率DISK和網(wǎng)絡(luò)帶寬占用率BW4個(gè)參數(shù)來描述服務(wù)器系統(tǒng)資源使用狀況, 這4個(gè)參數(shù)值是通過服務(wù)器的Agent來獲取的.

響應(yīng)時(shí)間RES通過負(fù)載均衡器端獲取. Monitor向服務(wù)器發(fā)送報(bào)文請求的時(shí)間點(diǎn)記為1, 得到服務(wù)器上Agent發(fā)回的負(fù)載信息時(shí)間點(diǎn)記為2, 通過1與2的差值作為參照條件計(jì)算出RES因此, 負(fù)載量值L可定義如下:

L=1×CPU+2×MEM+3×DISK+4×BW+5×RES.

其中R用來描述負(fù)載參數(shù)對服務(wù)器的重要程度,R越大說明此指標(biāo)越重要, ΣR= 1.CPU、MEM、DISK、BW、RES和R取值區(qū)間均為[0, 1]. 假設(shè)認(rèn)為CPU和RES較為重要可設(shè)置{0.3, 0.1, 0.1, 0.1, 0.3}, 在實(shí)際操作中可以對R不斷修正以達(dá)到最適合的比例.

3.2 F(W, L)表達(dá)式

本文采用如下(,)表達(dá)式進(jìn)行權(quán)值調(diào)整:

每個(gè)服務(wù)器在加入到集群系統(tǒng)時(shí)有一個(gè)初始權(quán)值W, IPVS調(diào)度也首先使用初始權(quán)值, 在計(jì)算新的權(quán)值W′時(shí), 如果負(fù)載量L< 0.6時(shí),說明服務(wù)器負(fù)載較輕, 還有足夠的請求處理能力, 權(quán)值會(huì)增大; 當(dāng)L大于0.6且小于0.75時(shí), 服務(wù)器負(fù)載接近飽和, 但仍具有接納新請求的能力, 權(quán)值繼續(xù)增大; 當(dāng)L大于0.75且小于0.9時(shí), 表達(dá)式中0.75-L產(chǎn)生負(fù)數(shù), 權(quán)值自動(dòng)調(diào)減, 這樣便避免了服務(wù)器負(fù)載過高的情況出現(xiàn). 表達(dá)式中0.75是理想的負(fù)載程度,1和2都是可調(diào)系數(shù), 缺省值分別設(shè)置為10和8.

由此可見,(,)表達(dá)式是一個(gè)負(fù)反饋公式, 通過它能夠把權(quán)值調(diào)整到一個(gè)穩(wěn)定點(diǎn), 當(dāng)系統(tǒng)達(dá)到理想的負(fù)載程度時(shí), 權(quán)值是相對穩(wěn)定不變的.

至此, 可以把負(fù)反饋均衡算法描述如下: (a) 負(fù)載均衡器定時(shí)向服務(wù)器發(fā)送請求報(bào)文, 服務(wù)器響應(yīng)并反饋負(fù)載信息(CPU、MEM等參數(shù), 不包括RES)和部分負(fù)載量值L(partly). (b) 負(fù)載均衡器對服務(wù)器反饋回的各項(xiàng)參數(shù)以及部分負(fù)載量L(partly)進(jìn)行判斷, 如果超過預(yù)設(shè)的閥值則W′置為0. (c) 負(fù)載均衡器計(jì)算響應(yīng)時(shí)間RES的值. (d) 負(fù)載均衡器根據(jù)RES及服務(wù)器發(fā)回的L(partly)計(jì)算負(fù)載總量值L, 并根據(jù)L的值, 通過(,)函數(shù)計(jì)算出新的權(quán)值W′再寫入到IPVS調(diào)度中. (e) 負(fù)載均衡器根據(jù)新權(quán)值W′, 選擇適合的服務(wù)器響應(yīng)請求.

由此可見, 負(fù)反饋均衡算法是在LVS原有的加權(quán)調(diào)度算法的基礎(chǔ)上增加負(fù)反饋控制機(jī)制, 使得原有調(diào)度算法能夠根據(jù)負(fù)反饋機(jī)制實(shí)現(xiàn)服務(wù)器權(quán)值的動(dòng)態(tài)調(diào)節(jié), 從而實(shí)現(xiàn)負(fù)載平衡.

圖3 負(fù)反饋下IPVS體系

4 負(fù)反饋算法實(shí)現(xiàn)

為了實(shí)現(xiàn)負(fù)反饋的負(fù)載均衡, 在LVS集群系統(tǒng)上安裝5個(gè)功能模塊: 信息收集模塊(ICM), 信息發(fā)送模塊(ISM), 時(shí)間探測模塊(TDM), 權(quán)值計(jì)算模塊(WCM), 權(quán)值寫入模塊(WWM), 其中ICM和ISM模塊運(yùn)行在真實(shí)服務(wù)器端, TDM、WCM和WWM模塊運(yùn)行在負(fù)載均衡器端, 是Monitor的組成部分, 如圖3所示.

4.1 服務(wù)器端Agent的實(shí)現(xiàn)

Agent程序的功能是: (a) 采集服務(wù)器負(fù)載信息并計(jì)算部分負(fù)載值L(partly); (b) 發(fā)送服務(wù)器負(fù)載信息及L(partly)至負(fù)載均衡器; (c) 及時(shí)響應(yīng)負(fù)載均衡器探測請求報(bào)文.

4.1.1 信息收集模塊(ICM)

本文主要介紹Windows系統(tǒng)下負(fù)載信息的收集. 采用Windows提供的PDH庫實(shí)現(xiàn), 實(shí)現(xiàn)函數(shù)命名為CollectLoad, 該函數(shù)實(shí)現(xiàn)了用PDH庫收集性能參數(shù)數(shù)據(jù)的全過程. 該函數(shù)包括4個(gè)形參和一個(gè)返回值. 4個(gè)形參就是要采集的服務(wù)器負(fù)載信息, 返回值用于判斷收集數(shù)據(jù)是否成功.

上述過程獲得了服務(wù)器的4個(gè)負(fù)載指標(biāo)CPU、MEM、DISK和BW, 沒有得到響應(yīng)時(shí)間RES, 因此, 此時(shí)計(jì)算的是部分負(fù)載量值L(partly), 算法如下:

L(partly) =1×CPU+2×MEM+3×DISK+4×BW.

通過定義結(jié)構(gòu)體來存放CPU、MEM、DISK、BW及(partly)用于提供給負(fù)載信息收集模塊ISM發(fā)送給負(fù)載均衡器. 結(jié)構(gòu)體如下:

Strcut RS_Loadinfo{

double cpu;

...

double load_partly;}

4.1.2 信息發(fā)送模塊(ISM)

ISM在得到ICM模塊收集的負(fù)載信息后發(fā)送至負(fù)載均衡器. 由于負(fù)載信息數(shù)據(jù)量較小, 故采用UDP協(xié)議建立socket套接字并進(jìn)行監(jiān)聽, 當(dāng)?shù)玫骄馄鲌?bào)文請求時(shí), 調(diào)用ICM模塊收集服務(wù)器負(fù)載信息, 然后把負(fù)載信息保存至RS_Loadinfo結(jié)構(gòu)體中通過sendto函數(shù)從UDP套接字發(fā)送給均衡器權(quán)值計(jì)算模塊WCM.

4.2 負(fù)載均衡器端Monitor的實(shí)現(xiàn)

Monitor主要工作如下: (a) 定時(shí)向服務(wù)器發(fā)送請求報(bào)文. (b) 根據(jù)服務(wù)器響應(yīng)時(shí)間得出RES用于計(jì)算新的權(quán)值W′. (c) 把W′寫到IPVS調(diào)度, 選擇合適的服務(wù)器分配請求.

4.2.1 時(shí)間探測模塊(TDM)

4.2.2 權(quán)值計(jì)算模塊(WCM)

由上文可知, 服務(wù)器負(fù)載信息存放在結(jié)構(gòu)體RS_Loadinfo中由ISM模塊發(fā)送過來給WCM. 負(fù)載均衡器端將每個(gè)服務(wù)器的信息存放在數(shù)組RS_Loadinfo[]中, 當(dāng)RS_Loadinfo[]中得到數(shù)據(jù)后先對各個(gè)負(fù)載參數(shù)及部分負(fù)載量進(jìn)行判斷. 如果各個(gè)負(fù)載參數(shù)小于閥值0.9,L(partly)小于0.7, 則按照(,)表達(dá)式計(jì)算新的權(quán)值W′并存放至數(shù)組New_[]中, 否則設(shè)置服務(wù)器新權(quán)值W′ = 0.

其中服務(wù)器的原權(quán)值W是由IPVS的getsockopt()函數(shù)獲取的,存放在本地Old_[]數(shù)組中. 由(,)表達(dá)式可知, 當(dāng)前權(quán)值W下, 當(dāng)服務(wù)器負(fù)載量值L＜0.75時(shí), 新的權(quán)值會(huì)增大, 此時(shí)W′>W,當(dāng)L≥0.75時(shí),W′權(quán)值下降使W′≤W, 使負(fù)載量維持在0.75上下, 避免了長時(shí)間運(yùn)行負(fù)載過高.

4.2.3 權(quán)值寫入模塊(WWM)

當(dāng)新的權(quán)值數(shù)組New_[]中已得到數(shù)據(jù), 權(quán)值寫入模塊WWM會(huì)把New_[]和Old_[]進(jìn)行比較, 當(dāng)兩者差值超過預(yù)設(shè)的閥值時(shí)才能把新權(quán)值寫到IPVS調(diào)度, 否則繼續(xù)保持原有調(diào)度. 這里閥值設(shè)為1, 當(dāng)∣New_[]-Old_[]∣≥1或者New_[] = 0時(shí), 則把New_[]的值賦給Old_[], 再把新的Old_[]值]寫進(jìn)IPVS調(diào)度.

5 算法性能測試

本文主要從平均響應(yīng)時(shí)間和吞吐量兩方面對Web服務(wù)器集群系統(tǒng)進(jìn)行壓力測試, 所使用的測試工具為微軟的Microsoft Web Application Stress Tool(簡稱WAS). 平均響應(yīng)時(shí)間主要由TTFB(Time To First Byte)的值決定, TTFB是收到服務(wù)器回應(yīng)的第1個(gè)字節(jié)所用時(shí)間, 其值越小性能越好. 吞吐量主要考察每秒收到數(shù)據(jù)量的大小即Bytes Recv Rate(KB·s-1), 值越大吞吐量越高.

表1 TTFB對比

通過在測試機(jī)上運(yùn)行測試工具WAS分別對使用原有加權(quán)最小連接調(diào)度算法(WLC)的LVS集群系統(tǒng)和引入負(fù)反饋算法后的集群進(jìn)行測試, 得到如表1所示數(shù)據(jù).

為了更直觀的描述, 可把表1的數(shù)據(jù)以圖表的形式顯示如圖4所示. 將WAS生成的報(bào)告中Bytes Recv Rate項(xiàng)作為集群系統(tǒng)的吞吐量進(jìn)行采集, 可得出如圖5吞吐量的對比圖.

從圖4可以看出, 當(dāng)連接數(shù)較少時(shí)兩種算法的TTFB值比較接近, 甚至引入負(fù)反饋后的集群系統(tǒng)反而響應(yīng)時(shí)間更長, 這是因?yàn)槎〞r(shí)獲取各臺(tái)服務(wù)器系統(tǒng)資源信息和響應(yīng)時(shí)間的額外開銷影響了其性能, 但是隨著連接數(shù)的增加, 負(fù)反饋算法的優(yōu)勢逐漸體現(xiàn)出來, 使用負(fù)反饋機(jī)制無論是在響應(yīng)時(shí)間還是吞吐量方面都優(yōu)于原有算法下的集群系統(tǒng), 可見, 基于負(fù)反饋的負(fù)載均衡算法在提高集群系統(tǒng)整體性能上相對原有算法有了一定的改善和提高.

圖4 TTFB對比

圖5 吞吐量對比

6 總結(jié)

為了有效防止負(fù)載傾斜的出現(xiàn), 更好的提高服務(wù)器集群系統(tǒng)的整體性能, 文中引入了負(fù)反饋的控制機(jī)制, 把原有的負(fù)載均衡調(diào)度算法進(jìn)行改進(jìn), 形成了一種基于負(fù)反饋的負(fù)載均衡算法. 該算法通過負(fù)反饋機(jī)制實(shí)現(xiàn)動(dòng)態(tài)的權(quán)值調(diào)整, 有效解決負(fù)載不均衡問題, 提高了集群系統(tǒng)的整體服務(wù)性能. 壓力測試表明, 基于負(fù)反饋的均衡算法優(yōu)于LVS原有算法, 在實(shí)現(xiàn)負(fù)載均衡和提高集群系統(tǒng)性能上有一定的價(jià)值.

[1] 田紹亮, 左明, 吳紹偉. 一種改進(jìn)的基于動(dòng)態(tài)反饋的負(fù)載均衡算法[J]. 計(jì)算機(jī)工程與設(shè)計(jì), 2007, 28(3): 572—728.

[2] 龔梅, 王鵬, 吳躍. 一種集群系統(tǒng)的透明動(dòng)態(tài)反饋負(fù)載均衡算法[J]. 計(jì)算機(jī)應(yīng)用, 2007, 27(11): 2662—2665.

[3] 王霜, 修保新, 肖衛(wèi)東. Web服務(wù)器集群的負(fù)載均衡算法研究[J]. 計(jì)算機(jī)工程與應(yīng)用, 2004, 40(25): 78—80.

[4] 郭成城, 晏蒲柳. 一種異構(gòu)Web服務(wù)器集群動(dòng)態(tài)負(fù)載均衡算法[J]. 計(jì)算機(jī)學(xué)報(bào), 2005, 28(2): 179—184.

[5] 程楊. 基于LVS負(fù)載均衡設(shè)計(jì)與實(shí)現(xiàn)[D]. 廣州: 中山大學(xué), 2011: 11—12.

[6] 謝欣. 試論負(fù)反饋控制理論在排球教學(xué)中的作用[J]. 山東體育科技, 2004, 26(4): 82—84.

[7] 申偉. 基于LVS集群的一種負(fù)載均衡改進(jìn)算法的研究與實(shí)現(xiàn)[D]. 北京: 中國地質(zhì)大學(xué), 2010: 28—29.

[8] 萬勇. 基于LVS的負(fù)載均衡策略算法的研究與改進(jìn)[D]. 成都: 西南交通大學(xué), 2010: 30—31.

Realization of the load balancing algorithm based on negative feedback

CHEN Wei

(Network Center, Suzhou Vocational and Technical College, Suzhou 234101, China)

The existing LVS load balancing algorithm is mostly decided by the fixed weights in the distribution of server requests, which makes the LVS cluster system show load skew in long time high load operation. Therefore, this paper presents an improved load balancing algorithm. This algorithm introduced by a negative feedback mecha-nism, giving full consideration to the dynamic regulation of the server weight, can more accurately reflect the real server load. Test results show that it is better than the original algorithm.

cluster; load-balancing; negative feedback; LVS

10.3969/j.issn.1672-6146.2013.01.011

TP 301.6

1672-6146(2013)01-0041-05

email: chenwei9737@163.com.

2012-11-27

安徽省高校優(yōu)秀青年基金(2012SQRL263)

(責(zé)任編校:劉剛毅)