服務(wù)器集群負(fù)載均衡策略的研究

饒 磊，湯小春，侯增江

(西北工業(yè)大學(xué)計(jì)算機(jī)學(xué)院，陜西 西安 710129)

0 引言

集群[1](Cluster)是由一組服務(wù)器構(gòu)成的一種松散耦合的計(jì)算節(jié)點(diǎn)集合，對客戶來說就像是形成了一個(gè)單一系統(tǒng)對外提供服務(wù)。在服務(wù)器集群環(huán)境下，各個(gè)服務(wù)器處理能力、負(fù)載水平之間存在一定的差異。如果不能合理分配任務(wù)，會(huì)出現(xiàn)某個(gè)服務(wù)器負(fù)載過重導(dǎo)致無法完成任務(wù)或者負(fù)載過輕導(dǎo)致資源閑置的情況，使得系統(tǒng)資源利用率低下，從而限制了系統(tǒng)整體性能的提升。

負(fù)載均衡問題的關(guān)鍵在于任務(wù)調(diào)度，目前國內(nèi)外已提出各種任務(wù)調(diào)度算法。常見的任務(wù)調(diào)度算法有輪循法(Round Robin，RR)[2]、Min-Min 算法[3]、Max-Min 算法[3]、遺傳算法[4](Genetic Algorithm，GA)等。輪循法沒有考慮服務(wù)器的實(shí)際負(fù)載和任務(wù)的大小，在實(shí)際應(yīng)用中不能及時(shí)響應(yīng)用戶請求，且存在負(fù)載不均衡的問題。Min-Min算法優(yōu)先選擇完成時(shí)間最短的任務(wù)到對應(yīng)的機(jī)器上執(zhí)行，而Max-Min算法優(yōu)先選擇完成時(shí)間最長的任務(wù)到對應(yīng)的機(jī)器上執(zhí)行;Min-Min算法的任務(wù)調(diào)度跨度較小，但容易導(dǎo)致負(fù)載不均衡;Max-Min算法能在一定程度上緩解負(fù)載不均衡的問題，但是任務(wù)調(diào)度跨度相對于Min-Min算法較長。此外，文獻(xiàn)[2]中還提及了基于負(fù)載參數(shù)的調(diào)度算法。

遺傳算法[4]是模擬生物進(jìn)化過程的一種啟發(fā)性搜索算法。目前，遺傳算法已經(jīng)被廣泛應(yīng)用于負(fù)載均衡問題的研究中，但存在一些缺陷:遺傳算法局部搜索能力較差，在優(yōu)化后期會(huì)因?yàn)榉N群缺乏多樣性而局部早熟收斂。模擬退火算法(Simulated Annealing，SA)的局部搜索能力較強(qiáng)，能跳出局部最優(yōu)解[5]，達(dá)到全局收斂，但把握搜索過程主體的能力較差。本文結(jié)合兩種算法的優(yōu)點(diǎn)，建立遺傳模擬退火算法(Genetic Simulated Annealing，GSA)，增強(qiáng)了遺傳算法的爬山能力，有效地解決了遺傳算法的早熟問題，同時(shí)提高了收斂的精度。

1 負(fù)載均衡問題建模

由于在實(shí)際的服務(wù)器集群環(huán)境下需要考慮的因素很多，為了方便問題的求解，本文假設(shè)集群系統(tǒng)采用集中式[6]任務(wù)調(diào)度模型;用戶提交的任務(wù)可以唯一的劃分為一組具有約束關(guān)系的不可再分的子任務(wù)，約束關(guān)系用來表示子任務(wù)調(diào)度的先后順序;每個(gè)子任務(wù)在各個(gè)服務(wù)器節(jié)點(diǎn)上運(yùn)行的時(shí)間可以預(yù)估，各個(gè)節(jié)點(diǎn)間的通信延遲不計(jì)?；谝陨霞僭O(shè)，任務(wù)調(diào)度問題可以描述為將具有約束關(guān)系的子任務(wù)分配到服務(wù)器節(jié)點(diǎn)上進(jìn)行處理，以降低任務(wù)調(diào)度跨度，提高負(fù)載均衡度，使集群系統(tǒng)資源得到合理利用，優(yōu)化系統(tǒng)的性能。

1.1 任務(wù)調(diào)度模型

本文將服務(wù)器集群環(huán)境描述為四元組Ω=(T，S，M，W)。其中任務(wù)集 T={t1，t2，…，tm}，服務(wù)器集S={s1，s2，…，sn}。M 是一個(gè) m × n 階矩陣，Mij表示子任務(wù)ti在服務(wù)器sj上的預(yù)計(jì)運(yùn)行時(shí)間，若ti無法在服務(wù)器sj上執(zhí)行，則Mij=-1。W是一個(gè)m×n階稀疏矩陣，Wij=1表示子任務(wù)ti被分配到服務(wù)器sj上執(zhí)行，否則 Wij=0，i∈{1，2，…，m}，j∈{1，2，…，n}。需要說明的是:在一種調(diào)度策略下，一個(gè)子任務(wù)只能在一臺服務(wù)器上執(zhí)行，即矩陣W的一行有且只能有一個(gè)非零值。子任務(wù)調(diào)度的先后順序可以用DAG圖表示，根據(jù)該圖可以得到若干個(gè)有效的調(diào)度順序。圖中每個(gè)結(jié)點(diǎn)對應(yīng)一個(gè)子任務(wù)，有向邊(ti，tj)表示ti先于tj執(zhí)行，先序關(guān)系具有傳遞性。對于任意一個(gè)有效的調(diào)度順序，必須滿足該先序關(guān)系。例如圖1中t4和t5先于t7執(zhí)行，而t4和t5沒有固定的先后關(guān)系，二者的調(diào)度順序可先可后。

圖1 子任務(wù)調(diào)度的順序圖

1.2 負(fù)載均衡模型

設(shè)A為一個(gè)有效的任務(wù)調(diào)度策略，T(A)表示在調(diào)度策略A下的任務(wù)調(diào)度跨度，即任務(wù)集T在服務(wù)器集S上總的執(zhí)行時(shí)間。本文的目的之一就是要降低T(A)，縮短用戶的等待時(shí)間。

設(shè) L={l1，l2，…，ln}表示在某種調(diào)度策略下，服務(wù)器的負(fù)載指標(biāo)集合，lj(A)為在調(diào)度策略A下，服務(wù)器sj的負(fù)載指標(biāo)。定義lj(A)如下:

式(1)中 j∈{1，2，…，n}，Mij≠ －1，由此可見，0＜lj(A)≤1。設(shè)σ(A)為負(fù)載指標(biāo)的標(biāo)準(zhǔn)差，即:

由式(3)可得，0＜μ(A)≤1。負(fù)載均衡要解決的問題就是要構(gòu)造一個(gè)合理的調(diào)度策略A，并根據(jù)該策略將任務(wù)調(diào)度到對應(yīng)的服務(wù)器上執(zhí)行，使得T(A)最小的同時(shí)μ(A)盡可能大。

2 算法原理分析

2.1 遺傳算法

遺傳算法[4]將問題域中的解編碼為種群中的染色體或個(gè)體，傳統(tǒng)遺傳算法的早熟現(xiàn)象與選擇操作有關(guān)。為了達(dá)到全局收斂的目的，理論上必須保持種群的多樣性;而在實(shí)際應(yīng)用中，為了加快算法的收斂速度，會(huì)傾向于選擇適應(yīng)度值較高的個(gè)體，而那些具有部分優(yōu)良基因卻適應(yīng)度值低的個(gè)體很容易被舍棄，在迭代的過程中，種群的多樣性會(huì)逐漸降低，導(dǎo)致早熟的概率變大。

2.2 模擬退火算法

模擬退火算法[5]來源于固體退火原理的啟發(fā)式隨機(jī)搜索算法。在進(jìn)行選擇操作時(shí)，按照Metropolis準(zhǔn)則[7]以一定的概率選擇較差的解，這樣可以有效防止局部收斂現(xiàn)象的發(fā)生。

2.3 遺傳模擬退火算法

遺傳模擬退火算法一方面以遺傳算法的基本操作主導(dǎo)尋優(yōu)的方向;另一方面，在進(jìn)化過程中，采用模擬退火算法選擇個(gè)體。在進(jìn)化初期溫度較高，加大了適應(yīng)度值較低的個(gè)體被選擇的概率，保持了種群的多樣性，增強(qiáng)了算法的全局收斂性。在迭代的過程中，溫度逐漸降低，導(dǎo)致適應(yīng)度值較低的個(gè)體被舍棄的概率變大，從而加快了算法的收斂速度。

3 算法設(shè)計(jì)

3.1 染色體編碼

本文采用二維實(shí)數(shù)編碼[4，8](矩陣編碼)方式。設(shè)子任務(wù)數(shù)為n，則一種有效的任務(wù)調(diào)度方式可以用n×n階稀疏矩陣R表示，矩陣的行依次對應(yīng)任務(wù)編號，矩陣的列表示任務(wù)的調(diào)度順序，比如任務(wù)ti的調(diào)度順序?yàn)閖，Rij的值為任務(wù)對應(yīng)的服務(wù)器編號，在第i行除第j列外，其余項(xiàng)的值為零。例如下面的7×7階矩陣:

由該矩陣可以得到滿足圖1的一種有效的任務(wù)調(diào)度順序{t1，t3，t2，t5，t4，t7，t6}，在服務(wù)器 s1上執(zhí)行的任務(wù)有{t1，t4，t7}，在服務(wù)器 s2上執(zhí)行的任務(wù)有{t2，t3，t5，t6}。

3.2 初始化種群

初始參數(shù)設(shè)定:設(shè)定種群規(guī)模Z，當(dāng)前種群代數(shù)K=1，終止進(jìn)化代數(shù)D，交叉概率Pc，變異概率Pm;初始溫度 T1，降溫因子 λ=1－K/D，0＜λ＜1。

初始化種群個(gè)體:

(1)生成任務(wù)調(diào)度順序，即子任務(wù)DAG圖的拓?fù)渑判颍惴ㄈ缦?

①判斷DAG圖中的結(jié)點(diǎn)集合是否為空，如果非空，則在DAG圖中隨機(jī)選一個(gè)沒有前驅(qū)的任務(wù)結(jié)點(diǎn)并輸出;否則算法結(jié)束。

②從圖中刪除該結(jié)點(diǎn)及由它發(fā)出的邊，轉(zhuǎn)①。

重復(fù)以上兩步，直到輸出所有結(jié)點(diǎn)，這樣就生成了一個(gè)有效的任務(wù)排列。

(2)生成任務(wù)資源映射:采取有放回的抽取方式，從S中隨機(jī)抽取一臺服務(wù)器sj分配給某個(gè)任務(wù)ti，抽取時(shí)若檢測到Mij=－1，則繼續(xù)抽取，直到Mij≠－1，抽取完后將Eij的值置為1，當(dāng)所有任務(wù)都分配完畢時(shí)才結(jié)束。

(3)將生成的任務(wù)調(diào)度順序和任務(wù)資源映射組合拼接，得到任務(wù)調(diào)度矩陣R。

依次循環(huán)執(zhí)行以上三步Z次，創(chuàng)建初始種群的Z個(gè)個(gè)體。至此，種群初始化結(jié)束。

3.3 適應(yīng)度函數(shù)定義

定義系統(tǒng)在調(diào)度策略A下的適應(yīng)度函數(shù)f(A)如下:

由式(4)可知T(A)越小，f(A)越大，反之亦然。

3.4 選擇操作

為了防止當(dāng)前種群的最優(yōu)個(gè)體在下一代丟失，采用精英選擇[4](Elitist Selection)策略:把當(dāng)前種群中最優(yōu)個(gè)體直接復(fù)制到下一代種群中，不進(jìn)行交叉、變異操作。

在進(jìn)行選擇操作時(shí)，首先采用精英選擇;然后采用輪盤賭[4](Roulette Wheel)算法和模擬退火算法結(jié)合的改良選擇算法，該算法首先采用輪盤賭算法進(jìn)行選擇，若某個(gè)體未被選中，則繼續(xù)采用模擬退火算法進(jìn)行選擇，算法如下:

設(shè)Xi為當(dāng)前種群中的第i個(gè)個(gè)體，P[Xi]為采用輪盤賭算法時(shí)，Xi被選擇的概率，根據(jù)輪盤賭算法原理有:

其中f(Xi)為Xi的適應(yīng)度值。由式(5)可知Xi被選擇的概率與f(Xi)的值成正比。

令△μ =max{μ(Xj)}－ μ(Xi)，j∈{1，2，…，Z]。PSA[Xi]表示模擬退火算法中的選擇概率，根據(jù)Metropolis準(zhǔn)則[7]，有:

當(dāng)滿足條件 PSA[Xi]＞ random[0，1]時(shí)選擇 Xi。顯然△μ≥0，由式(6)可知μ(Xi)越大時(shí)，Xi被選擇的概率也越大。算法偽代碼如下:

按照上述選擇算法，每次選擇兩個(gè)個(gè)體X、Y，用于3.5節(jié)的交叉操作。

3.5 交叉操作

對于3.4節(jié)中選擇的兩個(gè)個(gè)體X、Y，以概率Pc進(jìn)行交叉操作，交叉過程分為兩步:

(1)任務(wù)調(diào)度順序交叉:采用縱向交叉方法。隨機(jī)選擇X的任務(wù)調(diào)度矩陣中的一列作為交叉起始位置，其后的列按照Y的任務(wù)調(diào)度矩陣中的順序進(jìn)行移動(dòng);同理，Y也按照X的順序進(jìn)行移動(dòng)。

(2)任務(wù)資源映射交叉:采用橫向交叉方法。在上一步的基礎(chǔ)上，隨機(jī)選擇X的任務(wù)調(diào)度矩陣中的一行作為交叉起始位置，其后的行中的非零值與Y互換。若互換時(shí)存在Mij=－1的情況，則該行不交換。至此，產(chǎn)生 X'、Y'。

3.6 變異操作

對3.5節(jié)交叉操作產(chǎn)生的兩個(gè)個(gè)體X'、Y'，以概率Pm分別進(jìn)行變異操作，變異過程分為兩步:

(1)任務(wù)調(diào)度順序變異:隨機(jī)選擇X'(或Y')的任務(wù)調(diào)度矩陣R中的一列作為變異列。在當(dāng)前排列中找到離變異列最近的DAG圖中的直接前驅(qū)任務(wù)所在的列，作為起始位置;在當(dāng)前排列中找到離變異列最近的DAG圖中的直接后繼任務(wù)所在的列，作為結(jié)束位置;在起始位置和結(jié)束位置之間隨機(jī)選擇一列，將變異列移動(dòng)至該列。

(2)任務(wù)資源映射變異:隨機(jī)選擇X'(或Y')的任務(wù)調(diào)度矩陣R中的一行作為變異行，隨機(jī)抽取一臺服務(wù)器分配給該任務(wù)，若Mij=－1，則繼續(xù)抽取，直到Mij≠－1，并替換當(dāng)前分配給該任務(wù)的服務(wù)器編號。至此，產(chǎn)生 X″、Y″。

循環(huán)進(jìn)行選擇、交叉、變異操作，并將新個(gè)體加入到下一代種群中，直到下一代種群中個(gè)體的數(shù)量達(dá)到Z為止。

3.7 算法終止條件

當(dāng)種群進(jìn)化代數(shù)達(dá)到D時(shí)，即K=D時(shí)輸出最優(yōu)解并進(jìn)行解碼，算法終止;否則繼續(xù)迭代，在創(chuàng)建下一代種群的Z個(gè)個(gè)體后，按照TK+1=λ*TK進(jìn)行降溫，進(jìn)化代數(shù)累加，K=K+1。

3.8 算法流程

綜合以上各小節(jié)中的算法描述，本節(jié)采用如下偽代碼描述GSA算法的總體流程:

4 實(shí)驗(yàn)結(jié)果與分析

本文以國外某集群作業(yè)管理系統(tǒng)[9]為實(shí)驗(yàn)平臺，針對GSA算法、輪循法、Min-Min算法和Max-Min算法分別進(jìn)行實(shí)驗(yàn)。本次實(shí)驗(yàn)中的參數(shù)設(shè)置如下:資源數(shù)n=10，任務(wù)數(shù)從50增加到500;種群規(guī)模Z=100，種群終止進(jìn)化代數(shù)D=100，交叉概率Pc=0.95，變異概率Pm=0.05;初始溫度T1=0.1。4種算法在不同任務(wù)數(shù)下的任務(wù)調(diào)度跨度如圖2所示。

圖2 任務(wù)調(diào)度跨度圖

圖2表明GSA算法的任務(wù)調(diào)度跨度總體低于另外3種算法。當(dāng)任務(wù)數(shù)較少時(shí)，GSA算法的優(yōu)勢并不明顯，這是因?yàn)镚SA算法存在一定的開銷，但隨著任務(wù)數(shù)的增加，GSA算法在降低了任務(wù)調(diào)度跨度方面的優(yōu)勢逐漸得到體現(xiàn)。系統(tǒng)的負(fù)載均衡度如圖3所示。

從圖3可以看出GSA算法的負(fù)載均衡度大于另外3種算法，且隨著任務(wù)數(shù)的增加，GSA的負(fù)載均衡度上升幅度較大，可見GSA算法合理分配了任務(wù)，有效地實(shí)現(xiàn)了集群系統(tǒng)的負(fù)載均衡。

圖3 系統(tǒng)負(fù)載均衡度圖

5 結(jié)束語

本文針對服務(wù)器集群環(huán)境下的負(fù)載均衡問題提出了一種遺傳模擬退火算法，實(shí)驗(yàn)證明該算法有效地降低了任務(wù)調(diào)度跨度，減少了用戶的等待時(shí)間，實(shí)現(xiàn)了集群系統(tǒng)的負(fù)載均衡。但是本文在建立任務(wù)調(diào)度模型時(shí)沒有考慮節(jié)點(diǎn)之間的通信延時(shí)，此外文獻(xiàn)[10]提出了自適應(yīng)的交叉和變異概率以克服早熟缺陷，這些都是進(jìn)一步需要研究的問題。

[1]Wikipedia.Computer Cluster[EB/OL].http://en.wikipedia.org/wiki/Computer_cluster，2012-06-18.

[2]李坤，王百杰.服務(wù)器集群負(fù)載均衡技術(shù)研究及算法比較[J].計(jì)算機(jī)與現(xiàn)代化，2009(8):7-10.

[3]王觀玉.網(wǎng)格計(jì)算中任務(wù)調(diào)度算法的研究和改進(jìn)[J].計(jì)算機(jī)工程與科學(xué)，2011，33(10):186-190.

[4]王小平，曹立明.遺傳算法:理論、應(yīng)用及軟件實(shí)現(xiàn)[M].西安:西安交通大學(xué)出版社，2002.

[5]朱顥東，鐘勇.一種改進(jìn)的模擬退火算法[J].計(jì)算機(jī)技術(shù)與發(fā)展，2009，19(6):32-35.

[6]王文楓，帥建梅.一種云計(jì)算環(huán)境下任務(wù)調(diào)度策略[J].電子技術(shù)，2012，39(7):35-38.

[7]陳華根，吳健生，王家林，等.模擬退火算法機(jī)理研究[J].同濟(jì)大學(xué)學(xué)報(bào):自然科學(xué)版，2004，32(6):802-805.

[8]余有明，劉玉樹，閻光偉.遺傳算法的編碼理論與應(yīng)用[J].計(jì)算機(jī)工程與應(yīng)用，2006，42(3):86-89.

[9]湯小春.基于集群技術(shù)的作業(yè)管理系統(tǒng)的研究與實(shí)現(xiàn)[D].西安:西北工業(yè)大學(xué)，2002.

[10]劉漳輝，王曉莉.云計(jì)算虛擬機(jī)群中帶遺傳算法的負(fù)載均衡算法[J].福州大學(xué)學(xué)報(bào):自然科學(xué)版，2012，40(4):453-458.

[11]Mukul Pathak，Ajeet Kumar Bhartee，Vinay Tandon.An efficient scheduling policy for load balancing model for computational grid system[J].Computer Engineering and Intelligent Systems，2012，3(7):51-61.

[12]趙超，王晟.基于云模型的負(fù)載均衡問題研究[J].微電子學(xué)與計(jì)算機(jī)，2012，29(3):131-134.

[13]徐慧慧，石磊，陳信.網(wǎng)格資源調(diào)度算法研究[J].計(jì)算機(jī)技術(shù)與發(fā)展，2009，19(9):76-78.

[14]宋昕，宋歡歡.云計(jì)算環(huán)境下的流量控制和負(fù)載均衡策略[J].電子設(shè)計(jì)工程，2011，19(12):112-115.