一種基于負載均衡的云資源調(diào)度方法

陳 斌，甘茂林，李 娟

(1.海軍工程大學(xué) 電子工程學(xué)院，湖北 武漢 430033； 2.海軍駐廣州地區(qū)通信軍事代表室，廣東 廣州 510220)

一種基于負載均衡的云資源調(diào)度方法

陳 斌1，甘茂林2，李 娟1

(1.海軍工程大學(xué) 電子工程學(xué)院，湖北 武漢 430033； 2.海軍駐廣州地區(qū)通信軍事代表室，廣東 廣州 510220)

虛擬化技術(shù)可以實現(xiàn)云系統(tǒng)中資源的按需分配，但同時可能會造成部分物理服務(wù)器負載過重，從而導(dǎo)致系統(tǒng)性能降低。云系統(tǒng)負載均衡，是決定系統(tǒng)計算和服務(wù)能力的核心因素。在對云資源調(diào)度問題的形式化描述基礎(chǔ)上，定義了負載均衡系數(shù)，構(gòu)建了云資源調(diào)度負載均衡模型。針對云資源調(diào)度中的用戶需求及服務(wù)器屬性的差異性問題，提出了一種基于最大需求優(yōu)先和最閑服務(wù)器被選原則的云計算資源調(diào)度方法，并進行了算法設(shè)計與分析，給出了系統(tǒng)負載均衡系數(shù)的動態(tài)計算公式。仿真實驗結(jié)果表明，所提出的方法可得到理想的云計算負載均衡結(jié)果，與隨機調(diào)度、輪轉(zhuǎn)調(diào)度等傳統(tǒng)算法相比具有優(yōu)越的負載均衡性能和廣泛的適應(yīng)性。與此同時，所提出的方法可合理協(xié)調(diào)用戶需求和服務(wù)器屬性，以實現(xiàn)云資源負載均衡。

負載均衡；云資源調(diào)度；用戶需求；服務(wù)器屬性

0 引 言

云資源[1-3]在物理上以分布式的共享方式存在，在邏輯上以單一整體的形式呈現(xiàn)給用戶。云資源調(diào)度是將資源從資源提供方分配給用戶的一個過程。先進的云計算資源調(diào)度技術(shù)[4-7]是提高云計算系統(tǒng)性能的關(guān)鍵之一。而云系統(tǒng)負載均衡[8-10]，是決定系統(tǒng)計算和服務(wù)能力的核心因素。

傳統(tǒng)的分配調(diào)度算法[11-12]，如輪轉(zhuǎn)法、最小負載優(yōu)先法、哈希法等，雖然在一定程度上考慮了負載均衡的問題，但很難達到負載均衡的需求。原因來自兩方面：一是用戶需求的差異性，表現(xiàn)在用戶可能在不同時刻提出不同的資源需求；二是服務(wù)器屬性的差異性，在數(shù)據(jù)中心的服務(wù)器集群中，每個物理服務(wù)器的配置是不相同的。

針對上述問題，在研究分析云資源調(diào)度方法的基礎(chǔ)上，提出了一種基于最大需求優(yōu)先和最閑服務(wù)器被選原則的云計算資源調(diào)度方法。仿真實驗結(jié)果表明，該方法在云資源調(diào)度過程中通過合理協(xié)調(diào)用戶需求和服務(wù)器屬性，以達到云資源負載均衡的目的。

1 基本概念

云計算環(huán)境中，云資源調(diào)度流程如圖1所示。

圖1 云資源調(diào)度流程

云用戶向云平臺提交資源申請后，云計算環(huán)境中的調(diào)度中心節(jié)點，根據(jù)云調(diào)度策略，按照相應(yīng)的調(diào)度算法，進行云資源調(diào)度，建立虛擬資源與物理資源的映射，同時將用戶所需資源部署到具體的物理節(jié)點上，最終將資源分配給用戶，在用戶申請期限內(nèi)，提供給用戶使用。

從虛擬資源的角度描述，云資源可以看作是若干種不同類型的集合，故有以下定義。

定義1：云資源(Cloud Source，CS)，含n類子資源，表示形式為：

cs=,csi∈{1,2,…,∞},i∈{1,2,…,n} ，CS={cs}

其中，csi表示云資源向量cs中含第i類子資源的數(shù)量值；CS表示云資源集合。

在云資源集合CS定義運算“+”“-”“>”“<”：

從物理資源角度描述，云資源可以看作是若干物理服務(wù)器的集合，即服務(wù)器集群，每一臺物理服務(wù)器上，可提供若干云資源。故有如下定義。

定義2：物理服務(wù)器(Physical Machine,PM)位于云系統(tǒng)中，以pm.s表示位于服務(wù)器pm上的資源總數(shù)，pm.v表示pm上的可分配資源，有：

向量pm.s是對應(yīng)服務(wù)器pm的性能屬性，用以描述服務(wù)器的資源容量，其內(nèi)容由物理服務(wù)器pm決定，在服務(wù)器正常工作中，不會發(fā)生變化。而向量pm.v表達的是對應(yīng)服務(wù)器pm的實時狀態(tài)，用以描述服務(wù)器在當前時刻可用資源總量，其內(nèi)容由物理服務(wù)器pm當前資源余量決定，在服務(wù)器正常工作中，隨資源的分配與釋放實時變化。

定義3：物理服務(wù)器集群(Physical Machine Cluster,PMC)位于云系統(tǒng)中，含m個服務(wù)器，表示為：

PMC={pm1,pm2,…,pmm}

由定義1、2、3可知，在包含m臺物理服務(wù)器的集群PMC中，其能提供的云資源總量pmc.s和可分配資源總量pmc.v為：

pmc.s=pm1.s+pm2.s+…+pmm.s

pmc.v=pm1.v+pm2.v+…+pmm.v

其中，i∈{1,2,…,m},pmi∈PMC。

2 問題模型

物理服務(wù)器是云資源的提供者，而資源的使用者是云系統(tǒng)用戶(Cloud User，CU)。

從用戶的角度描述，云資源可以看作是云系統(tǒng)滿足用戶實時需求的服務(wù)能力。用戶在特定時刻的資源需求ur表示為：

ur=

其中， cu∈CU表示提出資源需求的云用戶；cs∈CS表示資源需求量；ts∈[0,∞)表示云用戶提出資源需求的初始時刻；te∈[0,∞)表示用戶資源占有時間長度。

用戶資源需求是一種實時變量，以UR(t)表示在t時刻云用戶的資源需求，則

UR(t)={ur|ur.ts=t}

可以計算，在t時刻用戶資源需求總量UR(t).CS為：

若在t時刻，服務(wù)器的集群PMC中的可分配資源總量為pmc.v(t)，則：pmc.v(t)>UR(t).CS為t時刻用戶資源需求得以滿足的必要條件。

從資源調(diào)度角度描述，云資源可以看作是云系統(tǒng)為云用戶服務(wù)的能力。云系統(tǒng)將部署在服務(wù)器上的資源按用戶需求分配給云用戶。故資源分配(Source Assignment，SA)的任務(wù)是根據(jù)用戶提出的資源需求，將用戶需求的資源部署在物理服務(wù)器上，并分配給用戶使用。資源分配的基本規(guī)則為：某個用戶的一次資源需求中，所有的資源均應(yīng)部署在同一個物理服務(wù)器上。即對于用戶需求ur,以下條件成立時，才可被滿足。

?pm∈PMC,pm.v>ur.cs

以sa表示云系統(tǒng)滿足ur的資源分配，有：

sa==

其中，∈UR；loc∈PMC表示用戶需求的資源所部署的物理服務(wù)器位置。

對應(yīng)于UR(t)，以SA(t)表示在t時刻云系統(tǒng)滿足所有用戶的資源分配集合，則：

SA(t)={|∈UR(t),loc∈PMC}

所研究的云資源調(diào)度算法以負載均衡為目標，與負載相關(guān)的定義如下。

定義4：服務(wù)器負載率(Physical Machine Load Factor)，以f表示。對于pm，f的計算方法如下：

定義5：服務(wù)器集群負載率(Physical Machine Cluster Load Factor)，以F表示。對于PMC，F(xiàn)的計算方法如下：

定義6：服務(wù)器集群負載均衡系數(shù)(Physical Machine Cluster Load Balancing Factor)以BF表示。對于PMC，BF的計算方法如下：

根據(jù)以上定義及描述，可對問題建立如下模型：

已知PMC，UR；

求解SA；

使得min PMC.BF

其中，min PMC.BF表示某時刻云系統(tǒng)服務(wù)器集群最小的負載均衡系數(shù)，(1)保證當前時刻所有的用戶需求均被處理，(2)保證所有資源在物理服務(wù)器上是可得的。

3 算法設(shè)計及分析

3.1 算法策略

云應(yīng)用中，導(dǎo)致服務(wù)器集群負載不均衡的因素有兩個[13-15]：一是用戶資源需求的隨機性，云用戶根據(jù)自己的實際情況向云系統(tǒng)申請規(guī)格不同的資源量，這些不同的資源需求將導(dǎo)致服務(wù)器負載的不均衡；二是服務(wù)器本身所能提供的資源量也是大小不一的，這種服務(wù)器屬性同樣導(dǎo)致負載的不均衡。針對這兩點，提出以下策略。

(1)最大資源需求優(yōu)先。

在資源部署時，資源量越大，越容易造成負載的不均衡。因而，采用“最大需求者優(yōu)先”原則，先處理資源申請量大的用戶需求。

因此，對應(yīng)t時刻的用戶需求集合UR(t)，首先按其中元素資源需求量ur.cs根據(jù)從大到小進行排序。資源分配時，按排序后的用戶資源需求順序依次進行處理。

(2)最低利用率被選。

對應(yīng)于每一個ur，理論上可以由云系統(tǒng)中的任意一臺服務(wù)器提供。所以對應(yīng)m個服務(wù)器，有m種分配方案，為，，…，，對應(yīng)這m種方案，提供資源的服務(wù)器相關(guān)參數(shù)更新為：

針對這些候選方案，選擇ua=，其中pm使得pmi.f最小，即：

3.2 算法步驟

根據(jù)“最大資源需求優(yōu)先，最低利用率被選”策略，問題求解步驟如下：

(1)初始化服務(wù)器集群PMC，用戶資源分配隊列UA,時間值t，確定算法終止條件TEND。

(2)若滿足終止條件，算法結(jié)束；否則繼續(xù)步驟(3)。

(3)在UA隊列中尋找已到期資源服務(wù)(即ua.tb+ua.te

(4)讀入當前用戶資源需求集合。

(5)根據(jù)資源需求量大小對用戶資源需求排序。

(6)按資源需求量大小，對每一個資源請求ur：

(6.1)依次將其預(yù)分配到每一臺服務(wù)器上，計算相應(yīng)服務(wù)器均衡負載率。

(6.2)記錄最小均衡負載率及相應(yīng)服務(wù)器pm。

(6.3)若pm合法，進行資源部署，更新pm狀態(tài)，并創(chuàng)建資源服務(wù)項，將其加入資源服務(wù)隊列中，轉(zhuǎn)到步驟(7)，否則轉(zhuǎn)步驟(4)。

(6.4)無法滿足ur，資源分配失敗。

(7)t=t+1。

(8)轉(zhuǎn)到步驟(2)。

算法描述如圖2所示。

圖2 算法描述

3.3 算法分析

(1)算法時間復(fù)雜度。

設(shè)云系統(tǒng)中PMC的服務(wù)器數(shù)量為m,CU中用戶總數(shù)為u,用戶提出資源需求的概率為p，用戶資源占有平均時長為τ，則在每個時刻t，UR中元素平均個數(shù)，即需要處理的資源需求數(shù)量平均值為up，服務(wù)集合UA平均長度為upτ。

算法從T=0開始運行，至T=TEND終止，在每一輪運行中，主要完成遍歷UA、UR排序、遍歷UR×PMC。故可計算其時間復(fù)雜度為：(TEND*up(τ+log(up)+m))。

(2)相關(guān)參數(shù)計算。

在算法執(zhí)行過程中，隨著資源的分配與釋放，物理服務(wù)器及服務(wù)器集群的相關(guān)參數(shù)也會發(fā)生變化。

在時刻t，首先系統(tǒng)釋放到期服務(wù)資源，再為該時刻的用戶需求進行資源分配。若：

則：

UA(t)=UA(t-1)+SA(t)-{ |∈UA(t-1),te=t}

一輪算法執(zhí)行完畢后，PMC中服務(wù)器可用資源及負載率為：

PMC的可用資源、負載率及負載均衡系數(shù)為：

4 實驗及結(jié)果分析

為進一步研究算法效果，通過仿真實驗分析算法演化過程及結(jié)果。實驗中，取服務(wù)器集群數(shù)量為6，僅考慮一種資源的情況，服務(wù)器資源參數(shù)如表1所示。

表1 服務(wù)器資源參數(shù)

其余參數(shù)設(shè)定為：CU中用戶總數(shù)為20,用戶提出資源需求的概率為0.5，用戶資源需求量均勻分布在(0,50)之間，用戶資源占有時長均勻分布在(0,10)之間，算法演化時長為100。算法演化過程中，服務(wù)器負載率及服務(wù)器集群負載率變化如圖3所示。

兩組參數(shù)對應(yīng)的服務(wù)器集群負載均衡系數(shù)為：

PMC(1).BF=0.062 21

PMC(2).BF=0.055 72

實驗結(jié)果表明，服務(wù)器集群中，無論服務(wù)器屬性是否有差異性，提出算法均可達到較好的負載均衡性能。

為進一步分析算法優(yōu)越性，以隨機分配方案、輪轉(zhuǎn)分配方案、最低利用率被選方案(與所提算法相比，不對資源需求進行排序)作為對比，在相同兩組服務(wù)器資源參數(shù)下進行相同的仿真實驗。不同方案下，服務(wù)器集群負載均衡系數(shù)值如圖4所示。

實驗結(jié)果表明，提出的負載均衡資源調(diào)度算法相比于傳統(tǒng)資源調(diào)度算法具有明顯的優(yōu)越性，特別是在服務(wù)器屬性差異性較大的情況下。表2列出了第二組參數(shù)下，提出的“最大資源需求優(yōu)先，最低利用率被選”資源調(diào)度策略和隨機調(diào)度策略下，各服務(wù)器及服務(wù)器集群的平均負載率數(shù)據(jù)。

(a)第一組實驗結(jié)果

(b)第二組實驗結(jié)果

(a)第一組實驗結(jié)果

(b)第二組實驗結(jié)果

表2 兩種策略下的服務(wù)器負載率

5 結(jié)束語

在云資源調(diào)度中，為保證服務(wù)器集群負載均衡，在構(gòu)建云資源調(diào)度負載均衡模型的基礎(chǔ)上，提出了一種基于最大需求優(yōu)先，最閑服務(wù)器被選原則的云計算資源調(diào)度方法。實驗結(jié)果表明，與傳統(tǒng)資源調(diào)度算法相比，提出方法具有優(yōu)越的負載均衡性能和廣泛的適應(yīng)性。該方法可合理協(xié)調(diào)用戶需求和服務(wù)器屬性，以實現(xiàn)云資源負載均衡。

[1] 陳 星,張 穎,張曉東,等.基于運行時模型的多樣化云資源管理方法[J].軟件學(xué)報,2014,25(7):1476-1491.

[2] 洪 斌,彭甫陽,鄧 波,等.云資源狀態(tài)監(jiān)控研究綜述[J].計算機應(yīng)用與軟件,2016,33(6):1-6.

[3] 賴培源,馬衛(wèi)民,劉 藝,等.云資源池網(wǎng)絡(luò)自動化部署技術(shù)研究與實踐[J].電信科學(xué),2015,31(7):96-103.

[4] Singh S,Chana I.A survey on resource scheduling in cloud computing:issues and challenges[J].Journal of Grid Computing,2016,14(2):217-264.

[5] Singh S,Chana I.QRSF:QoS-aware resource scheduling framework in cloud computing[J].Journal of Supercomputing,2015,71(1):241-292.

[6] 魏 蔚,劉 揚,楊衛(wèi)東.一種通用云計算資源調(diào)度問題的快速近似算法[J].計算機研究與發(fā)展,2016,53(3):697-703.

[7] 李媛禎,楊 群,賴尚琦,等.一種Hadoop Yarn的資源調(diào)度方法研究[J].電子學(xué)報,2016,44(5):1017-1024.

[8] 孟 蒙,茅 蘇.基于云計算的可反饋負載均衡策略的研究[J].計算機技術(shù)與發(fā)展,2014,24(10):135-139.

[9] Milani A S,Navimipour N J.Load balancing mechanisms and techniques in the cloud environments:systematic literature review and future trends[J].Journal of Network and Computer Applications,2016,71:86-98.

[10] 陶永才,張丹丹,石 磊,等.基于Maxdiff直方圖的MapReduce負載均衡研究[J].小型微型計算機系統(tǒng),2016,37(3):417-421.

[11] Levitin A. 算法設(shè)計與分析基礎(chǔ)[M].潘 彥,譯.第3版.北京:清華大學(xué)出版社,2015.

[12] 王永明,尹紅麗,秦開大.作業(yè)車間調(diào)度理論及其優(yōu)化方法研究[M].北京:科學(xué)出版社,2013.

[13] Pushpalatha K,Shaji R S,Jayan J P.A cost effective load balancing scheme for better resource utilization in cloud computing[J].Journal of Emerging Technologies in Web Intelligence,2014,6(3):280-290.

[14] 宋 滸.面向用戶服務(wù)需求的云計算管理機制研究[D].合肥:中國科學(xué)技術(shù)大學(xué),2013.

[15] Madni S H H,Latiff M S A,Coulibaly Y,et al.Resource scheduling for infrastructure as a service (IaaS) in cloud computing:challenges and opportunities[J].Journal of Network and Computer Applications,2016,68(6):173-200.

A Cloud Resource Scheduling Method Based on Load Balancing

CHEN Bin1,GAN Mao-lin2,LI Juan1

(1.College of Electronic Engineering,Naval University of Engineering,Wuhan 430033,China; 2.Representative Office on Military Communication,Navy in Guangzhou,Guangzhou 510220,China)

Virtualization technology can achieve the distribution of cloud resources according to need.However,it also may cause the heavy load for some physical servers which make system performance reduced.Load balancing of cloud system is the core factor that determines the system computing and service capability.Based on the formal description of cloud resource problem,load balancing coefficient has been defined and load balancing scheduling model for cloud resource has been built.Then,aiming at differences issues such as user demands and servers properties involving in cloud resource scheduling,a method has been proposed focusing on the principle of maximum demand prior and the freest server selected.It has been implemented for algorithm design and analysis further.Dynamic calculation of load balancing coefficient has been put forward as well.The result of simulation experiment has proved that the method proposed has excellent performance for load balancing and wide adaptability especially comparing to the random scheduling and rotation scheduling algorithm.It has also shown that the method can achieve load balancing of cloud resources with reasonably coordinating user demands and the server properties.

load balancing；cloud resource scheduling；user demands；server properties

2016-07-10

2016-10-13 網(wǎng)絡(luò)出版時間：2017-04-28

軍內(nèi)科研計劃項目(HJ-502-2015-35)

陳 斌(1975-)，男，博士生，副教授，研究方向為通信與信息系統(tǒng)。

http://kns.cnki.net/kcms/detail/61.1450.TP.20170428.1703.062.html

TP393

A

1673-629X(2017)06-0051-05

10.3969/j.issn.1673-629X.2017.06.011