蔣江波，徐志江

(浙江工業(yè)大學(xué) 省通信網(wǎng)技術(shù)應(yīng)用研究重點(diǎn)實(shí)驗(yàn)室，浙江 杭州 310023)

一種Web服務(wù)器集群的動(dòng)態(tài)反饋算法

蔣江波，徐志江

(浙江工業(yè)大學(xué) 省通信網(wǎng)技術(shù)應(yīng)用研究重點(diǎn)實(shí)驗(yàn)室，浙江 杭州 310023)

介紹了Web服務(wù)器集群技術(shù)和負(fù)載均衡，針對(duì)靜態(tài)的加權(quán)輪詢算法和動(dòng)態(tài)加權(quán)最小連接數(shù)算法的不足，提出一種基于動(dòng)態(tài)反饋的加權(quán)最小連接數(shù)算法，該算法根據(jù)服務(wù)器的實(shí)時(shí)負(fù)載動(dòng)態(tài)地改變權(quán)值的大小，再根據(jù)最小連接數(shù)算法來(lái)分配新的連接請(qǐng)求。通過(guò)網(wǎng)絡(luò)仿真軟件OPNET對(duì)這3種算法進(jìn)行仿真、對(duì)比得出，新的算法能降低HTTP響應(yīng)時(shí)間、提高負(fù)載均衡效率。

Web服務(wù)器集群；負(fù)載均衡；動(dòng)態(tài)反饋；OPNET

0 引言

隨著互聯(lián)網(wǎng)的快速發(fā)展，用戶數(shù)量不斷增多，越來(lái)越多的網(wǎng)站在面對(duì)高并發(fā)數(shù)據(jù)請(qǐng)求時(shí)出現(xiàn)頁(yè)面加載過(guò)慢和頁(yè)面無(wú)響應(yīng)的情況。對(duì)于服務(wù)器負(fù)載過(guò)大的情況有兩類解決方式，一種是單個(gè)服務(wù)器的硬件優(yōu)化，一種是采用集群的方式來(lái)實(shí)現(xiàn)。硬件優(yōu)化是提高服務(wù)器的配置，這種方式往往價(jià)格比較高昂。集群是一組相互獨(dú)立、通過(guò)高速網(wǎng)絡(luò)互連且以單一系統(tǒng)的模式加以管理的計(jì)算機(jī)。通過(guò)負(fù)載均衡來(lái)合理分配任務(wù)，提高網(wǎng)絡(luò)服務(wù)質(zhì)量，充分利用服務(wù)器的各種資源[1]。

服務(wù)器集群下的負(fù)載均衡技術(shù)有多種實(shí)現(xiàn)算法，主要分為靜態(tài)算法和動(dòng)態(tài)算法[2-3]。靜態(tài)算法主要是按固定的比例來(lái)分配任務(wù)，如加權(quán)輪詢(WRR)算法。動(dòng)態(tài)算法根據(jù)服務(wù)器的當(dāng)前狀態(tài)來(lái)分配任務(wù)，如加權(quán)最小連接數(shù)(WLC)算法[4]。

在實(shí)際場(chǎng)景中，服務(wù)器群組的性能差異比較大，靜態(tài)方法無(wú)法得到一個(gè)準(zhǔn)確的比值來(lái)反映實(shí)時(shí)的服務(wù)器狀況。而且在負(fù)載變化較大時(shí)，動(dòng)態(tài)方法用當(dāng)前連接數(shù)來(lái)表示當(dāng)前負(fù)載狀況并不準(zhǔn)確[5]。對(duì)此文獻(xiàn)[6]提出了一種自適應(yīng)權(quán)值的算法，當(dāng)負(fù)載均衡器收到任務(wù)請(qǐng)求時(shí)動(dòng)態(tài)更新節(jié)點(diǎn)權(quán)值，通過(guò)權(quán)值來(lái)反映實(shí)時(shí)負(fù)載，但是存在計(jì)算開銷太大的問(wèn)題。文獻(xiàn)[7]提出了一種動(dòng)態(tài)反饋算法，對(duì)實(shí)時(shí)負(fù)載量化，將量化的值與閾值比較，然后反饋新的權(quán)值，但是它的閾值是靜態(tài)的，造成反饋的權(quán)值誤差比較大。文獻(xiàn)[8]提出了一種預(yù)測(cè)算法，使用線性方程來(lái)預(yù)測(cè)實(shí)時(shí)負(fù)載，但是存在一定的滯后性。

本文結(jié)合靜態(tài)的權(quán)值輪詢算法和動(dòng)態(tài)的最小連接數(shù)算法提出一種動(dòng)態(tài)反饋的加權(quán)最小鏈接算法，通過(guò)對(duì)服務(wù)器的性能和實(shí)現(xiàn)負(fù)載來(lái)動(dòng)態(tài)調(diào)整節(jié)點(diǎn)的權(quán)值，再結(jié)合節(jié)點(diǎn)當(dāng)前連接數(shù)來(lái)合理分配任務(wù)。

1 傳統(tǒng)算法

1.1 加權(quán)輪詢算法

加權(quán)輪詢算法是對(duì)輪詢算法的一種改進(jìn),它針對(duì)服務(wù)器性能不一致的情況，按照性能的高低給各個(gè)服務(wù)器分配不同的權(quán)值。性能高的服務(wù)器它的權(quán)值相對(duì)比較高，能接收的請(qǐng)求就比較多；性能低的服務(wù)器它的權(quán)值相對(duì)比較低，能接收的請(qǐng)求就少。

假設(shè)這n個(gè)服務(wù)器集群的集合用S=(S1，S2…Sn)來(lái)表示，第i臺(tái)服務(wù)器的初始權(quán)值為W(Si) (1≤i≤n)，記錄上一次負(fù)載均衡器接受到請(qǐng)求連接選擇的節(jié)點(diǎn)i和當(dāng)前權(quán)值cw。當(dāng)前服務(wù)器的最大權(quán)值為max(S)。gcd(S)表示的是所有服務(wù)器權(quán)值的最大公約數(shù)[9]。算法執(zhí)行前先將變量i和cw初始化為-1和0，流程如圖1所示。

圖1 加權(quán)輪詢算法流程圖

加權(quán)輪詢算法特點(diǎn)：在輪詢算法的基礎(chǔ)上加入了權(quán)值的概念，使用權(quán)值來(lái)表示每臺(tái)服務(wù)器之間的性能差異，但是沒(méi)有考慮當(dāng)前連接數(shù)和當(dāng)前的服務(wù)器狀態(tài)，不能實(shí)時(shí)反映服務(wù)器的狀態(tài)，屬于靜態(tài)的負(fù)載均衡算法，具有局限性。

1.2 加權(quán)最小連接數(shù)算法

加權(quán)最小連接數(shù)算法使用權(quán)值表示各個(gè)服務(wù)器性能，當(dāng)負(fù)載均衡器收到新的任務(wù)請(qǐng)求時(shí)，他會(huì)通過(guò)各個(gè)服務(wù)器當(dāng)前的連接數(shù)和權(quán)值的比值大小來(lái)判斷，選擇比值最小的服務(wù)器來(lái)響應(yīng)任務(wù)請(qǐng)求。

同加權(quán)輪詢算法一樣服務(wù)器集合為S=(S1，S2…Sn)，第i臺(tái)服務(wù)器初始權(quán)值為W(Si) (1≤i≤n)，加權(quán)最小連接數(shù)算法還記錄了各個(gè)節(jié)點(diǎn)的當(dāng)前連接數(shù)C(Si)。

當(dāng)負(fù)載均衡器收到一個(gè)新的連接請(qǐng)求時(shí)，它將根據(jù)以下規(guī)則選擇服務(wù)器Sm：

C(Sm)/W(Sm)=min{C(Si)/W(Si)}

其中i∈[1，2，…，n]，W(Si)≠0。

考慮到除法所需的CPU周期比乘法多，所以判斷條件C(Sm)/W(Sm)>C(Si)/W(Si)可以進(jìn)一步表示為C(Sm)*W(Si)>C(Si)*W(Sm),當(dāng)服務(wù)器的權(quán)值為零時(shí)，服務(wù)器不被調(diào)度[10]。流程圖如圖2所示。

圖2 加權(quán)最小連接數(shù)算法流程圖

加權(quán)最小連接數(shù)算法特點(diǎn)：考慮了服務(wù)器的性能和負(fù)載均衡過(guò)程中各個(gè)服務(wù)器，充分利用了服務(wù)器資源。但是僅憑當(dāng)前連接數(shù)來(lái)反映服務(wù)器的負(fù)載狀態(tài)顯得不夠合理，而且權(quán)值的設(shè)置是靜態(tài)的，不能通過(guò)實(shí)時(shí)的調(diào)整來(lái)反映當(dāng)前的負(fù)載能力。

2 算法改進(jìn)

上述算法都沒(méi)有考慮服務(wù)器的實(shí)時(shí)負(fù)載狀態(tài)，存在權(quán)值設(shè)置過(guò)于主觀等問(wèn)題。為此提出如下改進(jìn)：

(1)收集服務(wù)器的當(dāng)前負(fù)載，這里選擇了當(dāng)前服務(wù)器的CPU利用率、內(nèi)存利用率、網(wǎng)絡(luò)帶寬利用率這3個(gè)指標(biāo)，在HTTP請(qǐng)求下服務(wù)器負(fù)載主要與這3個(gè)指標(biāo)有關(guān)。

(2)計(jì)算出各個(gè)節(jié)點(diǎn)的實(shí)時(shí)負(fù)載，周期性地反饋到負(fù)載均衡器。

(3)將負(fù)載均衡器接收到的實(shí)時(shí)負(fù)載信息與閾值進(jìn)行對(duì)比，然后動(dòng)態(tài)地改變各個(gè)服務(wù)器的節(jié)點(diǎn)的權(quán)值，使更新的權(quán)值能準(zhǔn)確地表示服務(wù)器的當(dāng)前負(fù)載。

(4)將新的權(quán)值帶入到加權(quán)最小連接數(shù)算法中以確定選擇哪個(gè)服務(wù)器節(jié)點(diǎn)來(lái)接收新的任務(wù)請(qǐng)求。

2.1 服務(wù)器負(fù)載的計(jì)算

在HTTP請(qǐng)求中，影響負(fù)載的主要因素是服務(wù)器的CPU利用率、內(nèi)存利用率和網(wǎng)絡(luò)帶寬利用率。節(jié)點(diǎn)Si的負(fù)載L(Si)主要由服務(wù)器CPU利用率Ci、內(nèi)存利用率Mi和網(wǎng)絡(luò)帶寬利用率Bi來(lái)決定。使用式(1)來(lái)計(jì)算當(dāng)前負(fù)載：

L(Si)=k1Ci+k2Mi+k3Bi，k1+k2+k3=1

(1)

其中k1，k2，k3分別表示了各自指標(biāo)的所占權(quán)重，通過(guò)這種方式來(lái)更準(zhǔn)確地反映服務(wù)器的當(dāng)前負(fù)載。

2.2 周期性反饋

通過(guò)負(fù)載均衡器周期性地接收到服務(wù)器的當(dāng)前負(fù)載，根據(jù)負(fù)載的大小與閾值對(duì)比來(lái)改變權(quán)值的大小。在這里閾值隨著傳過(guò)來(lái)的負(fù)載大小的改變而改變。將閾值用當(dāng)前所有負(fù)載的均值來(lái)表示：

(2)

(3)

其中W(Si)表示第i臺(tái)服務(wù)器的初始權(quán)值，C(Si)表示該臺(tái)服務(wù)器的當(dāng)前連接數(shù)，而且權(quán)值W(Si)不能為零。

節(jié)點(diǎn)新的權(quán)值就可以表示為：

(4)

周期性地獲取節(jié)點(diǎn)的新權(quán)值W(i)′，選擇當(dāng)前連接數(shù)與更新后的權(quán)值的比值最小的服務(wù)器來(lái)接受新的連接請(qǐng)求。即服務(wù)器S(m)接受新的請(qǐng)求，此時(shí)要滿足：

C(Sm)/W(Sm)′=min{C(Si)/W(Si)′}

(5)

3 通過(guò)OPNET軟件對(duì)三種算法性能進(jìn)行分析

OPNET是一款應(yīng)用與網(wǎng)絡(luò)仿真軟件，它支持大量的網(wǎng)絡(luò)通信協(xié)議和模擬系統(tǒng)分發(fā)，通過(guò)對(duì)離散事件的仿真來(lái)分析系統(tǒng)的行為和性能[11]。

OPNET網(wǎng)絡(luò)仿真可以分為網(wǎng)絡(luò)層、節(jié)點(diǎn)層、進(jìn)程層[12]。集群負(fù)載均衡的3層建模設(shè)計(jì)如下：

圖3 客戶端拓?fù)浣Y(jié)構(gòu)圖

(1)網(wǎng)絡(luò)建模：為了測(cè)試加權(quán)輪詢算法(WRR)、加權(quán)最小連接數(shù)算法(WLC)、改進(jìn)后的動(dòng)態(tài)反饋算法(DF)這3種算法的效果，選擇了4臺(tái)服務(wù)器集群，分別是server1、server2、server3、server4，通過(guò)100M線路連接負(fù)載均衡器。由6個(gè)子網(wǎng)組成客戶端，cilent1～client5表示內(nèi)部子網(wǎng)，client6表示外部子網(wǎng)，每個(gè)子網(wǎng)都包含45個(gè)用戶終端，客戶端拓?fù)浣Y(jié)構(gòu)如圖3，整個(gè)負(fù)載均衡系統(tǒng)的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)如圖4。

圖4 網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)圖

(2)節(jié)點(diǎn)建模：這里最主要的是對(duì)負(fù)載均衡器建模，它遵循OSI的七層建模規(guī)則，從低到高分別是：物理層、數(shù)據(jù)鏈路層、網(wǎng)絡(luò)層、傳輸層、會(huì)話層、表示層與應(yīng)用層，由進(jìn)程處理模型和隊(duì)列模型組成，采用全雙工的數(shù)據(jù)包進(jìn)行連接，數(shù)據(jù)包傳送按照7層機(jī)制來(lái)封裝[13]。負(fù)載均衡器的節(jié)點(diǎn)模型如圖5。

圖5 負(fù)載均衡器的節(jié)點(diǎn)模型

(3)進(jìn)程建模：進(jìn)程層是最底層，它可以描述進(jìn)程的邏輯，如通信協(xié)議、算法、統(tǒng)計(jì)量和操作系統(tǒng)等。通過(guò)狀態(tài)轉(zhuǎn)移圖來(lái)描述進(jìn)程模型的邏輯，通過(guò)連線來(lái)表示狀態(tài)的轉(zhuǎn)移[14]。在節(jié)點(diǎn)編輯器中載入加權(quán)輪詢算法(WRR)、加權(quán)最小連接數(shù)算法(WLC)、改進(jìn)的動(dòng)態(tài)反饋算法(DF)。

為了檢驗(yàn)算法在集群系統(tǒng)中的均衡效果，使用4臺(tái)性能不一樣的服務(wù)器組成集群，性能比例為4 ∶7 ∶10 ∶13。選擇仿真設(shè)置Application_Config中的HTTP應(yīng)用，模擬客戶端向服務(wù)器發(fā)送HTTP請(qǐng)求[15]。選擇HTTP場(chǎng)景為HTTP_IMAGE，模擬一種HTTP圖片請(qǐng)求場(chǎng)景?？蛻舳擞?70個(gè)節(jié)點(diǎn)組成，向負(fù)載均衡器發(fā)送相同請(qǐng)求。為了簡(jiǎn)化運(yùn)算，參數(shù)k1,k2,k3的取值分別為0.5，0.3,0.2，仿真時(shí)間為35 min,更新時(shí)間設(shè)置為10 s。選取HTTP響應(yīng)時(shí)間、CPU利用率為衡量算法負(fù)載均衡效果的統(tǒng)計(jì)量[16]。實(shí)驗(yàn)仿真效果如圖6～9。

圖6 HTTP響應(yīng)時(shí)間

從圖6可以看出在HTTP請(qǐng)求下，DF算法的HTTP平均響應(yīng)時(shí)間在0.25 s左右，比WLC算法和WRR算法的效果好。

圖7 WRR算法的CPU利用率

圖8 WLC算法的CPU利用率

圖9 DF算法的CPU利用率

從圖6可以看出在HTTP請(qǐng)求下，DF算法的HTTP平均響應(yīng)時(shí)間在0.25 s左右，比WLC算法和WRR算法的效果好。

從圖7～9可以看出，DF算法中4臺(tái)服務(wù)器的CPU利用率保持在3.8%左右，但是WRR和WLC算法的CPU利用率比較分散，這表現(xiàn)動(dòng)態(tài)反饋的算法對(duì)系統(tǒng)資源的利用比較均衡。

綜上可看出DF算法相對(duì)于WRR算法和WLC算法，其負(fù)載均衡具有更好效果。

4 結(jié)束語(yǔ)

Web服務(wù)器集群的核心是負(fù)載均衡算法。本文提出的基于動(dòng)態(tài)反饋的負(fù)載均衡算法與加權(quán)輪詢算法和加權(quán)最小連接數(shù)算法相比，考慮了服務(wù)器實(shí)時(shí)負(fù)載對(duì)負(fù)載均衡的影響，引入了周期性反饋機(jī)制來(lái)動(dòng)態(tài)地改變權(quán)值的大小，實(shí)時(shí)反映負(fù)載狀況，并根據(jù)實(shí)時(shí)負(fù)載情況將新的權(quán)值帶入最小連接數(shù)算法中來(lái)判斷選擇哪個(gè)服務(wù)器接受新的連接請(qǐng)求。根據(jù)仿真結(jié)果可以得到，該算法能有效地降低HTTP的響應(yīng)時(shí)間，均衡各服務(wù)器的CPU利用率。

[1] 張玉芳, 魏欽磊, 趙膺. 基于負(fù)載權(quán)值的負(fù)載均衡算法[J]. 計(jì)算機(jī)應(yīng)用研究, 2012, 29(12): 4711-4713.

[2] 胡志剛, 張艷平. 基于目標(biāo)約束的分層動(dòng)態(tài)負(fù)載均衡算法[J]. 計(jì)算機(jī)應(yīng)用研究, 2011, 28(3): 1105-1107.

[3] BRYHNI H. A comparison of load balancing techniques for scalable Web servers[J]. IEEE Network, 2000, 14(4): 58-64.

[4] 張前進(jìn), 齊美彬, 李莉. 基于應(yīng)用層負(fù)載均衡策略的分析與研究[J]. 計(jì)算機(jī)工程與應(yīng)用, 2007, 43(32): 138-142.

[5] 買京京, 龔紅艷, 宋純賀. 集群系統(tǒng)中的動(dòng)態(tài)反饋負(fù)載均衡策略[J]. 計(jì)算機(jī)工程, 2008, 34(16): 114-115.

[6] 耿強(qiáng), 黃雪琴. 一種基于自適應(yīng)權(quán)值的負(fù)載均衡算法[J]. 科學(xué)技術(shù)與工程, 2013, 13(14): 4079-4081.

[7] LI W Z, SHI H Y. Dynamic load balancing algorithm based on FCFS[C]. 4thInternational Conference on Innovative Computing, Information and Control, IEEE, 2009, 10(2): 75-80.

[8] Yu Ying, Yang Pin, Liang Gang. Load balancing algorithm based on prediction for parallel instrusion detection system[J]. Computer Engineering & Design, 2011, 32(8): 2565-2568.

[9] 莊晏軒. 服務(wù)器集群中基于動(dòng)態(tài)反饋的負(fù)載均衡算法[D]. 大連: 大連理工大學(xué), 2014.

[10] 王春娟, 董麗麗, 賈麗. Web集群系統(tǒng)的負(fù)載均衡算法[J]. 計(jì)算機(jī)工程, 2010, 36(2): 102-104.

[11] 陳敏. OPNET網(wǎng)絡(luò)仿真[M]. 北京: 清華大學(xué)出版社， 2004.

[12] 陳海紅. OPNET網(wǎng)絡(luò)仿真及分析[J]. 赤峰學(xué)院學(xué)報(bào), 2010, 26( 5): 23-25.

[13] 廖艷達(dá). 基于Opnet的Web集群負(fù)載均衡仿真研究[D]. 桂林: 廣西師范大學(xué), 2007.

[14] 史鴻雁, 李海生. 基于OPNET的集群負(fù)載均衡仿真[J]. 北京工商大學(xué)學(xué)報(bào), 2010, 28(1): 79-82.

[15] 操驚雷, 周建國(guó), 秦磊華. 基于OPNET的網(wǎng)絡(luò)壓力仿真[J]. 計(jì)算機(jī)工程, 2009, 35(23): 115-117.

[16] 張曉艷,扈羅全,汪一鳴，等.基于OPNET的自組織認(rèn)知無(wú)線網(wǎng)絡(luò)建模[J].微型機(jī)與應(yīng)用,2013,32(23):48-51,54.

A dynamic feedback algorithm for Web server cluster

Jiang Jiangbo，Xu Zhijiang

(Zhejiang Provincial Key Laboratory of Communtication Networks and Applications，Zhejiang University of Technology，Hangzhou 310023，China)

This paper describes the technology of Web server cluster and load balancing.Since the algorithm of Wighted Round Robin(WRR) and Weighted Least-Connection(WLC) have some shortages,this paper presented an algorithm of Weighted Least-Connection with dynamic feedback.The algorithm uses a dynamic weight to represent the current load,then brings the new weight in the algorithm of WLC to assign new request of connection.Comparing three algorithms by OPNET simulation software, the results show that this dynamic feedback algorithm can reduce the time of HTTP response and improve the efficiency of load balancing.

Web server cluster; load balancing; dynamic feedback; OPNET

TP393.0

A

1674-7720(2016)01-0012-04

蔣江波，徐志江.一種Web服務(wù)器集群的動(dòng)態(tài)反饋算法[J].微型機(jī)與應(yīng)用，2016，35(1)：12-15.

2015-09-08)

蔣江波(1991-)，男，在讀碩士生，主要研究方向：多媒體數(shù)字通信。

徐志江(1972-)，男，博士，碩士生導(dǎo)師，主要研究方向：信道編譯碼和通信信號(hào)處理。