云計算資源負(fù)載均衡調(diào)度算法研究

摘 要：為實現(xiàn)虛擬機(jī)層的負(fù)載均衡，論文提出一種基于雙加權(quán)最小連接的資源調(diào)度算法。傳統(tǒng)的加權(quán)最小連接算法對服務(wù)器的權(quán)值是事先根據(jù)服務(wù)器節(jié)點的配置情況和管理員的經(jīng)驗設(shè)定的，以連接數(shù)來表示節(jié)點負(fù)載。本文在加權(quán)最小連接算法的基礎(chǔ)上，綜合考慮服務(wù)器的實時負(fù)載情況，實現(xiàn)對服務(wù)器的動態(tài)賦權(quán)值。同時根據(jù)任務(wù)類型的復(fù)雜度，對任務(wù)類型也進(jìn)行了加權(quán)計算，給出了雙加權(quán)最小連接算法的設(shè)計思想、基本流程及實現(xiàn)過程。通過在CloudSim平臺上的仿真結(jié)果表明，與加權(quán)最小連接算法相比，雙加權(quán)最小連接算法能夠得到更高的負(fù)載均衡度和更好的系統(tǒng)效率。

關(guān)鍵詞：云計算；資源調(diào)度；負(fù)載均衡；加權(quán)最小連接算法；雙加權(quán)最小連接算法

中圖分類號：TP18

計算機(jī)技術(shù)和互聯(lián)網(wǎng)技術(shù)催生了互聯(lián)網(wǎng)應(yīng)用的迅猛發(fā)展，用戶通過網(wǎng)絡(luò)共享計算機(jī)資源演變至云計算商業(yè)模式劃時代的誕生，其計算能力近乎無限，信息服務(wù)豐富多樣，用戶對計算資源和服務(wù)隨時可得、易于擴(kuò)展、按需計費。在云計算商業(yè)模式下，構(gòu)建的云數(shù)據(jù)中心已成為一個高性能計算機(jī)集中地，物理服務(wù)器和網(wǎng)絡(luò)設(shè)備規(guī)模大，但由于用戶需求的多樣、動態(tài)變化以及服務(wù)器的資源異構(gòu)性會導(dǎo)致數(shù)據(jù)中心出現(xiàn)負(fù)載不均衡的情況，致使一部分物理機(jī)的負(fù)載過重，效率降低，而另一些則負(fù)載較輕處于空閑狀態(tài)。因此如何通過合適的資源調(diào)度算法來平衡物理機(jī)之間的負(fù)載以提高云數(shù)據(jù)中心資源利用率和整體性能是目前云計算領(lǐng)域的一大關(guān)鍵問題。

1 負(fù)載均衡及研究現(xiàn)狀

負(fù)載均衡是實現(xiàn)資源有效利用和共享的一個重要手段，分為基于任務(wù)的負(fù)載均衡和基于資源的負(fù)載均衡?；谌蝿?wù)的負(fù)載均衡是指把任務(wù)在多個計算、磁盤、進(jìn)程或者其他資源間進(jìn)行分配以獲得最優(yōu)的資源利用率，用來降低計算時間[1]?；谫Y源的負(fù)載均衡就是通過對資源的分配以及再分配來實現(xiàn)各個節(jié)點負(fù)載的大致平衡，從而提高整個系統(tǒng)的性能。

目前常用的負(fù)載均衡算法包括兩大類：（1）靜態(tài)的負(fù)載均衡算法，比如輪詢算法（RR）、加權(quán)輪詢算法（Weighted Round Robin，WRR）、隨機(jī)放置算法等，它不考慮服務(wù)器的實時負(fù)載情況，只是按照預(yù)先設(shè)定好的決策來分配任務(wù)；（2）動態(tài)負(fù)載均衡算法，如最小鏈接算法（Least-Connection，LC）和加權(quán)最小鏈接算法（Weighted Least-Connection Scheduling，WLC），它根據(jù)系統(tǒng)的實時負(fù)載情況動態(tài)來分發(fā)請求。

文獻(xiàn)[2]介紹了Eucalyptus平臺采用RR調(diào)度算法將虛擬機(jī)按照順序分配到不同的物理機(jī)上，實現(xiàn)負(fù)載均衡。WRR算法用相應(yīng)的權(quán)值表示服務(wù)器的處理能力，權(quán)值較大的會被分配給較多的請求。該算法在Vmware資源負(fù)載均衡中得到了采用。隨機(jī)算法就是將虛擬機(jī)請求隨機(jī)分配到合適的物理機(jī)上。

2 雙加權(quán)最小連接算法的負(fù)載均衡算法研究設(shè)計

2.1 加權(quán)最小連接調(diào)度算法

加權(quán)最小連接調(diào)度算法是在做少連接數(shù)調(diào)度算法的基礎(chǔ)上，根據(jù)服務(wù)器的不同處理能力，給每個服務(wù)器分配不同的權(quán)值，使其能夠接受相應(yīng)權(quán)值數(shù)的服務(wù)請求，是在最少連接數(shù)調(diào)度算法的基礎(chǔ)上的改進(jìn)。它是最小連接調(diào)度的超集，各個服務(wù)器用相應(yīng)的權(quán)值表示其處理性能。服務(wù)器的缺省權(quán)值為1，系統(tǒng)管理員可以動態(tài)地設(shè)置服務(wù)器的權(quán)值。加權(quán)最小連接調(diào)度在調(diào)度新連接時盡可能使服務(wù)器的已建立連接數(shù)和其權(quán)值成比例。調(diào)度器可以自動問詢真實服務(wù)器的負(fù)載情況，并動態(tài)地調(diào)整其權(quán)值。

加權(quán)最少連接調(diào)度算法流程如下：

（1）對服務(wù)器性能權(quán)值的設(shè)置不能準(zhǔn)確地反映節(jié)點真實的實時處理能力，造成整個系統(tǒng)的負(fù)載不均衡，影響系統(tǒng)的性能。

（2）僅僅以連接數(shù)來表示節(jié)點負(fù)載，沒有考慮請求所需的服務(wù)時間和系統(tǒng)資源的差異，并不能很準(zhǔn)確的表示服務(wù)節(jié)點的實時的負(fù)載情況。

2.2 基于任務(wù)類型的加權(quán)最小連接算法的負(fù)載均衡調(diào)度算法改進(jìn)

2.2.1 設(shè)計思想

為了實現(xiàn)更好的負(fù)載均衡，有必要改進(jìn)上述的算法，將服務(wù)器的性能進(jìn)行綜合的考慮，實現(xiàn)動態(tài)賦值；同時根據(jù)任務(wù)的復(fù)雜程度，確定每個任務(wù)的權(quán)值。從而使負(fù)載均衡器能夠更為準(zhǔn)確地了解各個服務(wù)器節(jié)點的實時處理性能和負(fù)載情況，選取一個最合適的服務(wù)節(jié)點。改進(jìn)后的算法設(shè)計思想如下：

（1）采用實時信息動態(tài)地表示服務(wù)器性能的權(quán)值，從而充分評估和利用各個節(jié)點服務(wù)器的剩余處理能力。

（2）根據(jù)任務(wù)中文件的類型為任務(wù)賦予相對應(yīng)的權(quán)值。任務(wù)中文件的擴(kuò)展名可確定文件的類型，從而確定任務(wù)的權(quán)值。為簡化處理，本文根據(jù)任務(wù)中不同類型所需要的資源不同，講任務(wù)分為四個類型，任務(wù)中文件所需資源越多，任務(wù)權(quán)值越高。服務(wù)器節(jié)點的實時負(fù)載就是服務(wù)器所有任務(wù)的權(quán)值之和。在每次分配任務(wù)之前，調(diào)度器將計算出每個服務(wù)器上所有任務(wù)的權(quán)值之和。

（3）為了保證系統(tǒng)在長時間運(yùn)行狀態(tài)下各個節(jié)點的負(fù)載不發(fā)生較大的傾斜，每次分配任務(wù)之前，調(diào)度器將計算出每個服務(wù)器上所有任務(wù)的權(quán)值之和和服務(wù)器性能的權(quán)值之比，將新任務(wù)分配給比值最小的服務(wù)器。

2.2.2 核心設(shè)計

算法流程設(shè)計如下：

（1）對每臺服務(wù)器進(jìn)行編號1-N。

（2）根據(jù)服務(wù)器的處理能力設(shè)定服務(wù)器權(quán)值。

（3）根據(jù)任務(wù)類型的復(fù)雜度設(shè)定任務(wù)權(quán)值。

（4）對于每臺服務(wù)器，計算出服務(wù)器上所有的任務(wù)權(quán)值之和與服務(wù)器權(quán)值之比。

（5）將任務(wù)分配給比值最小的服務(wù)器。服務(wù)器上已有的任務(wù)越簡單，其任務(wù)權(quán)值越??；且服務(wù)器的處理能力越強(qiáng)，其權(quán)值越大。故當(dāng)有新的請求到達(dá)時，總是將任務(wù)分配到服務(wù)器上已有的任務(wù)權(quán)值之和與服務(wù)器性能權(quán)值之比最小的服務(wù)器上。即當(dāng)且僅當(dāng)服務(wù)器Sm滿足下面公式時，新的請求會被發(fā)送至服務(wù)器Sm：

在實際運(yùn)行時，為簡化處理，根據(jù)任務(wù)中不同文件類型所需資源不同，將任務(wù)分為四種類型，即將任務(wù)中的文件分為四個大類，對應(yīng)四種任務(wù)，表示如下：

3 仿真及其結(jié)果分析

3.1 仿真實驗設(shè)計

為了驗證雙加權(quán)最小連接調(diào)度算法的性能，在CloudSim平臺上進(jìn)行了仿真，在實驗中模擬一個云數(shù)據(jù)中心，比較在使用幾種不同負(fù)載均衡調(diào)度算法時數(shù)據(jù)中心系統(tǒng)的負(fù)載均衡度，系統(tǒng)效率。實驗分為3組，每組服務(wù)器數(shù)目相同，均為15個；但任務(wù)數(shù)不同，分別為150個，1500個和15000個。每個任務(wù)均隨機(jī)產(chǎn)生且大小不同。每組實驗數(shù)據(jù)都使用了3種調(diào)度算法，即最小連接算法、加權(quán)最小連接算法與本文提出的雙加權(quán)最小連接算法。

3.2 仿真結(jié)果與分析

3.2.1 150個任務(wù)時

4 結(jié)束語

針對云計算中的資源調(diào)度問題，以及如何協(xié)調(diào)服務(wù)器之間的負(fù)載以提高云計算平臺和云數(shù)據(jù)中資源利用率和系統(tǒng)性能，本文提出了一種基于雙加權(quán)最小連接的資源調(diào)度算法。傳統(tǒng)的加權(quán)最小連接算法對服務(wù)器的權(quán)值是事先根據(jù)服務(wù)器節(jié)點的配置情況和管理員的經(jīng)驗設(shè)定的，以連接數(shù)來表示節(jié)點負(fù)載。在加權(quán)最小連接算法的基礎(chǔ)上，綜合考慮服務(wù)器的實時負(fù)載情況，實現(xiàn)對服務(wù)器的動態(tài)賦權(quán)值；同時根據(jù)任務(wù)類型的復(fù)雜度，對任務(wù)類型也進(jìn)行了加權(quán)計算；給出了雙加權(quán)最小連接算法的設(shè)計思想、基本流程及實現(xiàn)過程。通過在CloudSim平臺上的仿真結(jié)果表明，與加權(quán)最小連接算法相比，雙加權(quán)最小連接算法能夠得到更高的負(fù)載均衡度和更好的系統(tǒng)效率。

參考文獻(xiàn)：

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

[2]Berral J L，Goiri í，Nou R.Towards energy-aware scheduling in data centers using machine learning[A].Proceedings of the 1st International Conference on energy-Efficient Computing and Networking[C].ACM，2010：215-224.

[3]鄧維，劉方明，金海.云計算數(shù)據(jù)中心的新能源應(yīng)用：研究現(xiàn)狀與趨勢[J].計算機(jī)學(xué)報，2013（36）：582-598.

[4]葉可江，吳朝暉，姜曉紅.虛擬化云計算平臺的能耗管理[J].計算機(jī)學(xué)報，2012（06）：1262-1285.

[5]羅軍舟，金嘉暉，宋愛波.云計算—體系架構(gòu)與關(guān)鍵技術(shù)[J].通信學(xué)報，2011（32）：3-21.

[6]潘飛，蔣從鋒，徐向華.負(fù)載相關(guān)的虛擬機(jī)放置策略[J].小型微型計算機(jī)系統(tǒng)，2013（34）：520-524.

[7]高宏卿，邢穎.基于經(jīng)濟(jì)學(xué)的云資源管理模型研究[J].計算機(jī)工程與設(shè)計，2010（19）：4139-4142.

[8]田文洪，趙勇.云計算—資源調(diào)度管理[M].北京：國防工業(yè)出版社，2011：81-88，7-10.

作者簡介：彭紅姣（1975-），女，湖南祁東人，實驗師，碩士，博士研究生，研究方向：網(wǎng)絡(luò)虛擬化、云計算、網(wǎng)絡(luò)與通信、計算機(jī)應(yīng)用。

基金項目：江蘇省高校研究生科研創(chuàng)新計劃項目（項目編號：CXZZ13_0494）江蘇省高校自然科學(xué)研究計劃資助項目（項目編號：12KJB520007）；江蘇省自然科學(xué)基金項目（No.BK2011754）。

作者單位：南京郵電大學(xué)計算機(jī)學(xué)院，南京 210023