洪偉宏，劉 濤，黃少濱，張萬松

（哈爾濱工程大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院 哈爾濱 150001）

1 引言

在利用云計算模式提供軟件、框架、硬件服務(wù)的過程中，由于要面對客戶環(huán)境和自身所處環(huán)境的開放性、多樣性、復(fù)雜性，需要更多的硬件設(shè)備、更加靈活高效的軟件架構(gòu)、更加有效的管理機(jī)制，以提高系統(tǒng)的處理能力、服務(wù)能力，這就會使系統(tǒng)的結(jié)構(gòu)越來越復(fù)雜，成本越來越高，存在大量的計算任務(wù)依賴于云平臺的計算能力、存儲空間和調(diào)度機(jī)制等。作為一種新型的計算模式，如何更加有效地進(jìn)行負(fù)載均衡是云計算中的重要問題之一。

在云計算環(huán)境中，用戶可以通過互聯(lián)網(wǎng)應(yīng)用程序快速地訪問資源，計算機(jī)系統(tǒng)具有較高的穩(wěn)定性，可以同時處理用戶大量的計算請求。典型的云計算系統(tǒng)包括Amazon EC2彈性計算云[1]、Google App Engine[2]。然而隨著基礎(chǔ)設(shè)施規(guī)模的不斷擴(kuò)大，大量的應(yīng)用服務(wù)被提供到網(wǎng)絡(luò)中，在云計算系統(tǒng)中，計算任務(wù)是被分解到一系列單獨(dú)的計算節(jié)點(diǎn)中，當(dāng)計算節(jié)點(diǎn)面對大量計算任務(wù)時，有效的動態(tài)負(fù)載均衡策略可以提高系統(tǒng)的性能。現(xiàn)有的動態(tài)負(fù)載策略可以分為以負(fù)載狀態(tài)為基礎(chǔ)的策略和以資源需求為基礎(chǔ)的策略。為了計算負(fù)載，需要獲取計算節(jié)點(diǎn)負(fù)載信息和任務(wù)需求信息，然而這些信息有時難以獲取，從而使現(xiàn)有的動態(tài)負(fù)載策略的使用受到很大的限制。本文提出一種全新的基于CometCloud[3]平臺的動態(tài)負(fù)載均衡策略——ALP（自適應(yīng)負(fù)載均衡策略），可以較好地彌補(bǔ)以上兩個策略的不足。

2 CometCloud平臺

CometCloud是一種基于Comet可調(diào)整計算能力大小的虛擬計算云，集成了本地的計算環(huán)境和可能需要的公有云服務(wù)，并且可以提供支持一系列編程范式和應(yīng)用需求的抽象機(jī)制。CometCloud的體系結(jié)構(gòu)如圖1所示。CometCloud實(shí)現(xiàn)了一種基于自主的cloudbridging和cloudbursting的策略，自主cloudbridging不但實(shí)現(xiàn)了本地計算環(huán)境（數(shù)據(jù)中心、網(wǎng)絡(luò)）的集成，而且實(shí)現(xiàn)了公有云服務(wù)平臺（Amazon EC2、Eucalyptus）的結(jié)合 ； 自主cloudbursting實(shí)現(xiàn)了一種能夠解決動態(tài)負(fù)載、需求高峰和極端需求下的動態(tài)應(yīng)用規(guī)模擴(kuò)展。

CometCloud體系結(jié)構(gòu)包含3個層次，分別為基礎(chǔ)設(shè)施層 (infrastructure layer)、服務(wù)層 (service layer)和編程層(programming layer)。基礎(chǔ)設(shè)施層使用 Chord[4]和 Squid[5]方法用于信息發(fā)現(xiàn)，這一層還包括備份和負(fù)載均衡服務(wù)，可以解決節(jié)點(diǎn)動態(tài)加入、離開和節(jié)點(diǎn)失效問題。服務(wù)層提供了一系列自主應(yīng)用級編程服務(wù)，利用元組空間協(xié)調(diào)模型實(shí)現(xiàn)了一個虛擬共享空間的抽象及訪問原語。編程層提供了應(yīng)用開發(fā)和管理的基本框架，支持一系列主控機(jī)、工作站模式，由工作站處理主控機(jī)產(chǎn)生的任務(wù)，主控機(jī)與工作站可以通過虛擬共享空間直接進(jìn)行通信，通過應(yīng)用程序框架支持任務(wù)的調(diào)度和監(jiān)控。

3 改進(jìn)負(fù)載模型和策略

以負(fù)載信息為基礎(chǔ)的動態(tài)負(fù)載均衡方法可以在云中為任務(wù)選擇最合適的計算節(jié)點(diǎn)，以減少任務(wù)的執(zhí)行時間，獲得最大限度的吞吐量。通過負(fù)載信息可計算負(fù)載指數(shù)(load index)，負(fù)載指數(shù)是動態(tài)負(fù)載均衡的關(guān)鍵因素。

3.1 負(fù)載指數(shù)

負(fù)載指數(shù)是度量云計算系統(tǒng)工作負(fù)載情況的重要標(biāo)準(zhǔn)，表明系統(tǒng)資源當(dāng)前的運(yùn)行狀態(tài)，如空閑狀態(tài)（無負(fù)載或非常小的負(fù)載）、重載狀態(tài)（不能接受新的任務(wù)）和正常狀態(tài)（可以接受任務(wù)）3種情況。

當(dāng)任務(wù)需求復(fù)雜時，通常需要將兩個或多個負(fù)載指數(shù)集成到一個負(fù)載指數(shù)中，Branco[6]提出在一個節(jié)點(diǎn)中使用n標(biāo)準(zhǔn)化負(fù)載信息，形成一個n維負(fù)載向量，將負(fù)載向量長度作為負(fù)載指標(biāo)。類似負(fù)載向量，每個任務(wù)都有一個資源需求向量，當(dāng)收到一個新任務(wù)時，每個節(jié)點(diǎn)計算任務(wù)資源需求向量和負(fù)載向量的和，選擇最短的向量作為任務(wù)目標(biāo)節(jié)點(diǎn)。Branco的負(fù)載指數(shù)計算方法如下：

Branco方法可以結(jié)合簡單指數(shù)的不同優(yōu)點(diǎn)，在各種應(yīng)用環(huán)境中都有出色的表現(xiàn)。但是其建立在資源需求信息基礎(chǔ)上，負(fù)載指數(shù)的準(zhǔn)確性依賴于資源信息的準(zhǔn)確性。如果無法獲得資源需求信息，這種方法是無效的。

Xiaodong Zhang[7]提出了另一種方式，將不同的負(fù)載指數(shù)集成到Zhang負(fù)載指數(shù)中。Zhang的負(fù)載指數(shù)使用內(nèi)存量RAM作為門限，計算所有任務(wù)的最小內(nèi)存和作為MT，當(dāng)MT

云計算平臺中的動態(tài)負(fù)載策略可以分為負(fù)載狀態(tài)策略和資源需求策略。負(fù)載狀態(tài)策略是以任務(wù)資源需求特征不變和任務(wù)需求相似為前提，當(dāng)這個前提為真時，負(fù)載狀態(tài)策略會有良好的表現(xiàn)，但在實(shí)踐中，云中的任務(wù)資源需求不同，這就使得負(fù)載狀態(tài)策略不適用。

資源需求策略根據(jù)任務(wù)資源需求信息和節(jié)點(diǎn)負(fù)載信息，將任務(wù)分配到符合任務(wù)資源需求且負(fù)載最低的節(jié)點(diǎn)上。在云計算系統(tǒng)中，任務(wù)資源需求差異巨大，任務(wù)資源需求特征不斷變化，任務(wù)資源信息難以獲得，因此，現(xiàn)存的動態(tài)負(fù)載均衡策略很難較好地滿足云計算系統(tǒng)的需要。

3.2 自適應(yīng)負(fù)載模型ALP

為了解決動態(tài)負(fù)載策略中負(fù)載狀態(tài)策略和資源需求獲取與協(xié)調(diào)的問題，提出了一種自適應(yīng)負(fù)載模型ALP。ALP由4部分組成：負(fù)載監(jiān)聽器、負(fù)載緩存器、負(fù)載計算模型和負(fù)載數(shù)據(jù)填充器。負(fù)載監(jiān)聽器通過網(wǎng)絡(luò)向Comet Cloud中的工作機(jī)發(fā)送負(fù)載信息請求，工作站得到信息后將CPU使用率、內(nèi)存使用率、硬盤使用率、工作站ID和工作站名稱回傳給主控機(jī)，主控機(jī)將得到的負(fù)載信息暫時存放到負(fù)載緩存器中，供下一層的負(fù)載計算模型使用。ALP的體系結(jié)構(gòu)如圖2所示。

在云計算環(huán)境中，任務(wù)的資源需求特征不斷變化，使用整合負(fù)載信息的靜態(tài)權(quán)重不能準(zhǔn)確地反映當(dāng)前系統(tǒng)的負(fù)載狀態(tài)。參考文獻(xiàn)[8]表明資源負(fù)載信息之間的相關(guān)系數(shù)可以很好地代表資源當(dāng)前的性能狀態(tài)。因此ALP將資源負(fù)載信息和資源平均處理時間的相關(guān)系數(shù)作為負(fù)載指數(shù)。負(fù)載計算模型從負(fù)載緩存器中讀出每一個工作機(jī)的負(fù)載信息，然后計算工作機(jī)的負(fù)載指數(shù)。負(fù)載指數(shù)計算方法如下：

其中cpuusage是工作機(jī)CPU當(dāng)前使用率，diskusage是硬盤當(dāng)前使用率，memoryusage是內(nèi)存當(dāng)前使用率。變量XCPU代表CPU使用率，變量Xdisk表示硬盤使用率，變量Xmemory表示內(nèi)存使用率，Tworker代表工作站平均任務(wù)處理時間。

通過上面的計算得出每個工作節(jié)點(diǎn)的負(fù)載指數(shù)，帶入式（5）得出每個工作節(jié)點(diǎn)的權(quán)重：

動態(tài)負(fù)載均衡模型中的權(quán)重隊列用于保存各個工作節(jié)點(diǎn)的權(quán)重。當(dāng)負(fù)載計算模型計算出工作節(jié)點(diǎn)i的權(quán)重后，會調(diào)用權(quán)重負(fù)載數(shù)據(jù)填充器。負(fù)載數(shù)據(jù)填充器負(fù)責(zé)將工作節(jié)點(diǎn)i的權(quán)重注入權(quán)重隊列中保存。當(dāng)主控機(jī)接收新任務(wù)時會遍歷權(quán)重隊列，從隊頭掃描到隊尾找到隊列中的權(quán)重的最小值，然后取出這個值，并在隊列中刪除。

4 實(shí)驗(yàn)分析

比較不同實(shí)驗(yàn)條件下至少連接策略和自適應(yīng)負(fù)載策略在性能方面的差異。在網(wǎng)絡(luò)條件相同的情況下，改變?nèi)蝿?wù)請求個數(shù)，如圖3所示，在任務(wù)個數(shù)均勻增加的情況下，自適應(yīng)負(fù)載策略的響應(yīng)時間要比至少連接策略增加得緩慢。圖4所示是在工作量相等的條件下，當(dāng)工作站的個數(shù)以20遞增時，自適應(yīng)負(fù)載策略和至少連接策略的響應(yīng)時間都會隨之增加，但從圖4中得知，自適應(yīng)負(fù)載策略的響應(yīng)時間比至少連接策略響應(yīng)時間少5%～10%。

通過上面兩個實(shí)驗(yàn)可以得出，ALP在效率上優(yōu)于至少連接策略，自適應(yīng)策略一方面借助了CometCloud平臺優(yōu)良的特性，同時定期的權(quán)重隊列更新使任務(wù)能更好地分配到工作機(jī)上，從而自適應(yīng)負(fù)載均衡在性能方面更加出色。

5 結(jié)束語

在云計算中，隨著基礎(chǔ)設(shè)施的不斷擴(kuò)大，大量的應(yīng)用服務(wù)被納入網(wǎng)絡(luò)中，計算任務(wù)被分解到一系列單獨(dú)的計算節(jié)點(diǎn)中，計算節(jié)點(diǎn)的負(fù)載問題就特別突出。通過對CometCloud平臺結(jié)構(gòu)的分析，提出一種自適應(yīng)動態(tài)負(fù)載均衡方法，用于解決動態(tài)負(fù)載均衡策略在效率和準(zhǔn)確性方面的問題。ALP策略通過自適應(yīng)負(fù)載均衡使用整合工作機(jī)負(fù)載信息的動態(tài)權(quán)重，可以較好地反映工作機(jī)的工作狀態(tài)。在CometCloud云平臺上的實(shí)驗(yàn)證明，ALP方法在對云平臺負(fù)載均衡上效果較好。

1 Garfinkel.An evaluation of Amazon’s grid computing services.Cambridge,Harvard University,2007

2 Google App Engine.http://appengine.google.com

3 CometCloud.http://nsfcac.rutgers.edu/CometCloud/CometCloud/CometCloud_Home_Page.html

4 Stoica I,MorrisR,KargerD,etal.Chord:a scalable peer-to-peer lookup service for internet applications.Computer Communication Review,2001(31):149～160

5 Schmidt C,Parashar M.Squid:enabling search in dht-based systems.Journals of Parallel Distrib ution Computer,2008,58(7):962～975

6 Branco K,Santana M,Santana J.PIV and WPIV:two new performance index for heterogeneous systems evaluation.In:Proceedings of the 2006 IEEE International Symposium on Industrial Electronics,Montreal,Que,Canada,2006

7 Zhang Xiaodong,Qu Yanxia,Li Xiao.Improving distributed workload performance by sharing both CPU and memory resources.In:Proceedings of the 20th International Conference on Distributed Computing Systems,Taipei,China,2000

8 Demenico Ferrari,Zhou Songnian.Load index for dynamic load balancing.In:Proceedings of 1986 ACM Fall Joint Computer Conference,Dallas,Texas,USA,1986