一種改進(jìn)的動(dòng)態(tài)反饋負(fù)載均衡算法

陳泰安

（武漢科技大學(xué) 信息科學(xué)與工程學(xué)院，湖北 武漢 430081）

隨著網(wǎng)絡(luò)需求的不斷增加，集群服務(wù)器技術(shù)將以其高可靠、高性能的優(yōu)勢(shì)逐步取代以前單一服務(wù)器的工作模式，它提供了一個(gè)負(fù)載性能易于擴(kuò)展的、高效可靠地服務(wù)器性能解決方案。然而集群服務(wù)器經(jīng)常出現(xiàn)負(fù)載不平衡的現(xiàn)象，這成了制約集群系統(tǒng)性能體現(xiàn)的一個(gè)關(guān)鍵因素。因此，有必要對(duì)現(xiàn)有的調(diào)度算法進(jìn)行改進(jìn)，以提高系統(tǒng)資源的利用率，使集群技術(shù)的效能得到更好的體現(xiàn)，從而有效的減少用戶地等待時(shí)間[1]。（Dynamic Feed-Back）算法[4]等。下面將對(duì)加權(quán)最小連接算法和DFB算法做進(jìn)一步的分析比較。

1）加權(quán)最小連接算法

加權(quán)最小連接算法在集群的實(shí)際使用中是最常用的負(fù)載調(diào)度算法[5]。加權(quán)最小連接算法的核心思想[6]：假設(shè)有 S0，S1，…，Sn-1臺(tái)服務(wù)器，服務(wù)器 Si的權(quán)值用 W（Si）來(lái)表示，其當(dāng)前連接數(shù)用 C（Si）來(lái)表示，則 Csum=∑C（Si）（i=0，1…，n-1）。 當(dāng)服務(wù)器 Sm滿足條件：，i=0，1，…，n-1，W（Si）≠0時(shí)，將新的連接請(qǐng)求發(fā)送到。而在此次計(jì)算中是常數(shù)，故上述條件可簡(jiǎn)化為：C（sm）/w（sm）=min{C（si）/W（si）}，i=0，1，…，n-1，w（Si）≠0。 各個(gè)服務(wù)器用相應(yīng)的權(quán)值表示其處理性能。算法在調(diào)度新連接時(shí)盡可能使服務(wù)器的已建立連接數(shù)和其權(quán)值成比例。該算法通過(guò)僅通過(guò)服務(wù)器的連接數(shù)來(lái)判斷節(jié)點(diǎn)的負(fù)載，并不準(zhǔn)確，因?yàn)槿绶?wù)的類別、CPU占用率、流量等也需要考慮[7]。

2）DFB 算法

DFB算法的基本思想是：首先設(shè)定一個(gè)閾值f，當(dāng)有新的服務(wù)請(qǐng)求時(shí)，將負(fù)載量小于f的m個(gè)服務(wù)器選出來(lái)做為備選

1 常見(jiàn)的負(fù)載均衡算法

常見(jiàn)的負(fù)載均衡算法主要包括靜態(tài)負(fù)載均衡算法和動(dòng)態(tài)負(fù)載均衡算法兩種。其中靜態(tài)負(fù)載均衡算法不考慮各服務(wù)節(jié)點(diǎn)的負(fù)載情況，只按算法既定的方式分發(fā)服務(wù)請(qǐng)求；動(dòng)態(tài)負(fù)載均衡算法如加權(quán)最小連接算法可根據(jù)系統(tǒng)當(dāng)前的負(fù)載狀況動(dòng)態(tài)的分發(fā)服務(wù)請(qǐng)求。這類算法的問(wèn)題在于：一段時(shí)間內(nèi)將所有新到達(dá)的請(qǐng)求消息發(fā)送給請(qǐng)求量最小的后臺(tái)服務(wù)器，如果在這段時(shí)間內(nèi)新到達(dá)的請(qǐng)求較多則反而會(huì)破壞負(fù)載均衡[2]。另外，還有引入了隨機(jī)性的Pick-KX算法[3]和DFB服務(wù)器集合。然后根據(jù)各服務(wù)器的性能指數(shù)C（Sx）來(lái)計(jì)算分配概率最后修改Sx的負(fù)載。

2 算法設(shè)計(jì)思想

2.1 各服務(wù)節(jié)點(diǎn)負(fù)載量計(jì)算

集群系統(tǒng)經(jīng)過(guò)長(zhǎng)時(shí)間的運(yùn)行，調(diào)度器上記錄的負(fù)載量將不能準(zhǔn)確的反映各服務(wù)節(jié)點(diǎn)負(fù)載的實(shí)際情況。所以周期的采集服務(wù)節(jié)點(diǎn)的負(fù)載信息可以保證調(diào)度器中記載的數(shù)據(jù)的準(zhǔn)確性。每隔一個(gè)時(shí)間T，各服務(wù)節(jié)點(diǎn)向調(diào)度器匯報(bào)該節(jié)點(diǎn)的CPU利用率、內(nèi)存利用率、磁盤訪問(wèn)率、網(wǎng)絡(luò)帶寬占用率、進(jìn)程數(shù)量占用率5項(xiàng)性能參數(shù)。該節(jié)點(diǎn)的負(fù)載量Load（Si）可如下計(jì)算：

Load （Si）=R1*Lcpu（Si） +R2*Lmemory（Si） +R3*Li0（Si）+R4*Lbandwidth（Si）+R5*process（Si）其中。

2.2 各服務(wù)節(jié)點(diǎn)處理能力計(jì)算

計(jì)算第i臺(tái)服務(wù)器的最大處理能力時(shí)，一般考慮以下幾個(gè)指標(biāo)：CPU的數(shù)量ni，處理速率C （Ci），磁盤 I/O速率C（Di）， 內(nèi)存容量 C （Mi）， 網(wǎng)絡(luò)吞吐量 C （Ni）， 最大進(jìn)程數(shù) C（Pi）。 該節(jié)點(diǎn)的最大處理能力C（Si）可如下計(jì)算：

C（Si）=K1*niC（Ci）+K2*C（Di）+K3*C（Mi）+K4*C（Ni）+K5*C（Pi）

其中∑K=1，i=0，1…n-1。

2.3 算法具體步驟

1）各服務(wù)節(jié)點(diǎn)定時(shí)上報(bào)各項(xiàng)性能參數(shù)。

2）計(jì)算各節(jié)點(diǎn)負(fù)載量和處理能力。

3）設(shè)定一個(gè)閾值H。

4）當(dāng)一個(gè)新的任務(wù)請(qǐng)求到來(lái)時(shí)，如果的負(fù)載量Load（Si）=min{Load（Sk）}，k=0，1…，n-1，則將此節(jié)點(diǎn)加入到候選集合 I中；如果其他節(jié)點(diǎn)滿足 Load（Sm）＜Load（Si）+H，m=0，1…，n-1 則將此節(jié)點(diǎn)加入到集合I中。

5）計(jì)算候選集合中各節(jié)點(diǎn)的任務(wù)分配概率 P（Sk）。P（Sk）=Y（Sk）/∑Y（Si），k=0，1…，n-1，其中 Y（Sk）=C（Sk）/Load（Sk）。

6）根據(jù)候選節(jié)點(diǎn)的概率，將任務(wù)分配到I中的一個(gè)節(jié)點(diǎn)上。

7）修正該節(jié)點(diǎn)的負(fù)載量。

3 算法測(cè)試

測(cè)試采用平均應(yīng)答延時(shí)和吞吐量作為算法性能的評(píng)價(jià)指標(biāo)。平均應(yīng)答延時(shí)即系統(tǒng)對(duì)服務(wù)請(qǐng)求的平均響應(yīng)時(shí)間。吞吐量就是系統(tǒng)在單位時(shí)間內(nèi)處理的數(shù)據(jù)量。實(shí)驗(yàn)所用測(cè)試的設(shè)備條件如表1所示。

表1 實(shí)驗(yàn)設(shè)備數(shù)據(jù)Tab.1 Experimental device data

在自行搭建的負(fù)載均衡平臺(tái)上進(jìn)行了測(cè)試。系統(tǒng)由4臺(tái)由以太網(wǎng)連接的PC組成，操作系統(tǒng)為CentOS 5.7，運(yùn)行Apache 2.4提供 Web服務(wù)。測(cè)試中設(shè)參數(shù) R={0.3，0.3，0.2，0.1，0.1}，K={0.3，0.3，0.2，0.1，0.1}。 周期設(shè)為 20 s，f設(shè)為0.25。測(cè)試的用戶請(qǐng)求由4臺(tái)PC提供，運(yùn)行請(qǐng)求發(fā)生程序。圖1給出了3種算法的平均應(yīng)答延時(shí)的結(jié)果對(duì)比。圖2給出了3種算法的吞吐量的測(cè)試結(jié)果對(duì)比。其中黑框代表加權(quán)最小連接算法，白框代表DFB算法，陰影框代表改進(jìn)的動(dòng)態(tài)反饋算法。

圖1 3種算法平均應(yīng)答延時(shí)對(duì)比Fig.1 Three algorithms average response delay comparison

圖2 3種算法吞吐量對(duì)比Fig.2 Three algorithms throughput comparison

從圖1和圖2可以看出：當(dāng)連接數(shù)較少時(shí)，3種算法的性能相似；當(dāng)連接數(shù)增多后，改進(jìn)的動(dòng)態(tài)反饋算法逐漸體現(xiàn)出性能優(yōu)勢(shì)。相比較于最小連接算法和DFB算法，新算法能有效的減少平均應(yīng)答延時(shí)、增大吞吐量。

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

新算法對(duì)每臺(tái)服務(wù)器的處理能力和當(dāng)前負(fù)載進(jìn)行綜合考慮，并且在DFB算法的基礎(chǔ)上對(duì)其節(jié)點(diǎn)的分配算法作了進(jìn)一步的優(yōu)化。通過(guò)實(shí)驗(yàn)結(jié)果可知，新算法取得了比最小連接算法和DFB算法更好的負(fù)載均衡效果。

[1]許海成，傅錦偉.服務(wù)器集群負(fù)載均衡的建模與仿真研究[J].計(jì)算機(jī)仿真，2012，29（3）:180-183.XU Hai-cheng，F(xiàn)U Jin-wei.Research on model and simulation of load balance for server cluster[J].Computer Simulation，2012，29（3）:180-183.

[2]張昊，廖建新，朱曉民.增強(qiáng)型動(dòng)態(tài)反饋隨機(jī)分發(fā)負(fù)載均衡算法[J].計(jì)算機(jī)工程，2007，33（4）:97-99.ZHANG Hao，LIAO Jian-xin，ZHU Xiao-min.Advanced dynamic feedback and random dispatch load-balance algorithm[J].Computer engineering，2007，33（4）:97-99.

[3]Genova Z，Christensen K J.Challenges in URL Switching for Implementing Globally Distributed Web Sites[C]//Proc.of the Workshop on Scalable Web Services，2000:89-94.

[4]劉建，徐磊，張維明.基于動(dòng)態(tài)反饋的負(fù)載均衡算法[J].計(jì)算機(jī)工程與科學(xué)，2003，25（5）:65-68.LIU Jian，XU Lei，ZHANG Wei-ming.A load balancing algorithm based on dynamic feed-back[J].Computer engineering&Science，2003，25（5）:65-68.

[5]周松泉.一種改進(jìn)的集群動(dòng)態(tài)負(fù)載均衡算法[J].計(jì)算機(jī)與現(xiàn)代化，2012，（1）:135-139.ZHOU Song-quan.An improved dynamic load-balancing algorithm for cluster[J].Computer and Modernization，2012（1）:135-139.

[6]王春娟，董麗麗，賈麗.Web集群系統(tǒng)的負(fù)載均衡算法[J].計(jì)算機(jī)工程，2010，36（2）:102-104.WANG Chun-juan，DONG Li-li，JIA Li.Load balance algorithm for web cluster system[J].Computer Engineering，2010，36（2）:102-104.

[7]劉斌，徐精明，代素環(huán)，等.基于Linux虛擬服務(wù)器的負(fù)載均衡算法[J].計(jì)算機(jī)工程，2011，37（23）:279-287.LIU Bin，XU Jing-ming，DAI Su-huan，et al.Load balancing algorithmbasedonLinuxvirtualserver[J].ComputerEngineering，