楊亞南，李一鳴，聶力海，張 寧，趙來平

天津大學(xué)智能與計(jì)算學(xué)部，天津300350

近年來，谷歌、Amazon、微軟已經(jīng)在大型數(shù)據(jù)中心進(jìn)行了大量的投資以支持多種云服務(wù)及其客戶.云基礎(chǔ)設(shè)施提供商允許用戶按需租賃資源，并支持隨用隨付的計(jì)費(fèi)模式.較低的設(shè)備成本及維護(hù)費(fèi)用已經(jīng)成為吸引用戶將其應(yīng)用程序遷移到云的主要原因之一[1].提高云數(shù)據(jù)中心的成本效率可以鼓勵(lì)更多的用戶從云計(jì)算中獲益，也有利于云計(jì)算行業(yè)的發(fā)展.節(jié)約成本的方法很多，例如節(jié)約能源[2-4]、最小化因違反服務(wù)級(jí)別協(xié)議（service level agreement,SLA）而產(chǎn)生的成本[5]以及通過實(shí)例組合降低成本[6-7]等.對(duì)亞馬遜、Azure 和阿里云的研究發(fā)現(xiàn)，云計(jì)算服務(wù)商提供不同規(guī)格的實(shí)例供用戶選擇，實(shí)例的價(jià)格通常因資源配置的不用而有所差異，同時(shí)即使對(duì)于同一規(guī)格的實(shí)例，因其在不同地域的數(shù)據(jù)中心也有著不同的定價(jià).如“m1.small”的虛擬機(jī)（virtual machine,VM）實(shí)例.亞馬遜EC2 在日本東京的售價(jià)為0.067美元/h，比美國弗吉尼亞州的售價(jià)高39.6%，比愛爾蘭的售價(jià)高28.8%.同樣，微軟Azure的“standard A1”在日本東部地區(qū)的價(jià)格比印度中部地區(qū)的高22.7%，比美國中部地區(qū)的高35%.由阿里云香港數(shù)據(jù)中心提供的“ecs.n1.small”的價(jià)格比青島和杭州數(shù)據(jù)中心的高64.8%.

價(jià)格變動(dòng)的原因來自于多個(gè)方面，例如站點(diǎn)投資、IT成本（服務(wù)器購買、網(wǎng)絡(luò)設(shè)備架設(shè)等）、經(jīng)營成本、能源費(fèi)用[8-9]等組成了數(shù)據(jù)中心的總體構(gòu)建成本.目前，中國國家天文臺(tái)與天津大學(xué)正在合作開展中國虛擬天文臺(tái)項(xiàng)目[10-11]，旨為天文學(xué)家搭建天文云數(shù)據(jù)平臺(tái)，利用大數(shù)據(jù)處理技術(shù)協(xié)調(diào)天文觀測活動(dòng).該項(xiàng)目涵蓋了位于北京、上海、南京、昆明、烏魯木齊等多地?cái)?shù)據(jù)中心.由于北京商業(yè)用電的平均價(jià)格接近烏魯木齊的2 倍，因此同樣類型的VM 實(shí)例在北京的價(jià)格大約是烏魯木齊的3 倍.文獻(xiàn)[12]根據(jù)數(shù)據(jù)中心之間電價(jià)的變化設(shè)計(jì)策略以減少IaaS供應(yīng)商的電費(fèi)開支；云IaaS 用戶能夠借助數(shù)據(jù)中心之間的價(jià)格差異減少相關(guān)的服務(wù)費(fèi)用，從而節(jié)省大量的成本費(fèi)用開支.

本文旨在改善跨地域分布的數(shù)據(jù)中心間數(shù)據(jù)處理的成本效益，通過利用跨地域分布云中的數(shù)據(jù)中心資源價(jià)格差異這一性質(zhì)來最小化總體成本（包括計(jì)算成本和傳輸成本）.假設(shè)數(shù)據(jù)已經(jīng)分散存儲(chǔ)至云系統(tǒng)的各個(gè)數(shù)據(jù)中心內(nèi)部，則直接分配一個(gè)任務(wù)到存儲(chǔ)其輸入數(shù)據(jù)的數(shù)據(jù)中心可以降低總體數(shù)據(jù)傳輸成本，但由于待處理的數(shù)據(jù)可能分布在多個(gè)數(shù)據(jù)中心，因此數(shù)據(jù)傳輸是不可避免的，由此帶來了對(duì)應(yīng)的傳輸成本.理論上給出計(jì)算成本和通信成本的形式化描述，就可以估計(jì)出將任務(wù)分配給數(shù)據(jù)中心的總成本，然后將任務(wù)分配到成本最低的數(shù)據(jù)中心.但在實(shí)際應(yīng)用中，由于多種因素（如數(shù)據(jù)中心容量有限、安全性、服務(wù)性能（quality of service,QoS）保證、SLA 遵從性、隱私和其他相關(guān)法規(guī)要求等）的限制，上述做法有時(shí)并不可行.研究表明，跨地域分布云數(shù)據(jù)中心間的任務(wù)調(diào)度可以建模成一般分配問題（general assignment problem,GAP），該問題屬于NP難問題（即在多項(xiàng)式時(shí)間內(nèi)難以找到可行解）.與此同時(shí)，數(shù)據(jù)中心對(duì)資源（如計(jì)算、網(wǎng)絡(luò)和存儲(chǔ)）采用不同定價(jià)模型也加劇了求解的復(fù)雜性.

本文在求解最優(yōu)化的調(diào)度方案時(shí)主要考慮線性定價(jià)和階梯定價(jià)兩種定價(jià)模型.對(duì)于線性定價(jià)，采用增廣拉格朗日乘子法（augmented Lagrange multiplier method,ALMM）來解決.由于ALMM 方法可能會(huì)產(chǎn)生不可行解，因此本文設(shè)計(jì)了一個(gè)調(diào)整算法來調(diào)整結(jié)果，保證其可行的同時(shí)實(shí)現(xiàn)總成本最小化的目標(biāo).對(duì)于分段定價(jià)，證明了在相同的任務(wù)和數(shù)據(jù)下該模型會(huì)給用戶帶來額外的成本，而此時(shí)ALMM 方法的效率由于組合爆炸而降低，例如當(dāng)任務(wù)總數(shù)超過7 個(gè)時(shí)，至少需要400 s 才能得到結(jié)果.為了提高任務(wù)調(diào)度過程的時(shí)間效率，本文還設(shè)計(jì)了一種啟發(fā)式的降值密度調(diào)度（decreased value density scheduling algorithm,DVDS）算法，目的是在較短的時(shí)間內(nèi)找到最經(jīng)濟(jì)的調(diào)度方案.實(shí)驗(yàn)表明，DVDS 算法與ALMM 相比僅增加9.49%的成本，但卻在求解時(shí)間縮短了90%.

1 系統(tǒng)模型和問題定義

表1列出了跨地域數(shù)據(jù)中心問題模型中的符號(hào)定義.

1.1 云數(shù)據(jù)中心模型

將跨地域的云系統(tǒng)定義為GD=(ND,ED)，其中ND={d1,d2,··· ,dm}表示跨地域分布的數(shù)據(jù)中心，代表數(shù)據(jù)中心之間的網(wǎng)絡(luò)帶寬.由于每個(gè)數(shù)據(jù)中心都具有計(jì)算和存儲(chǔ)能力，因此可以用于托管VM 并執(zhí)行數(shù)據(jù)密集型任務(wù).但值得注意的是各數(shù)據(jù)中心的計(jì)算能力有限且相互之間可能存在差異.若用dci表示di的計(jì)算能力，?di ∈ND，在任意的數(shù)據(jù)中心di上放置任務(wù)所需的總資源不能超過該數(shù)據(jù)中心的資源容量dci.每個(gè)數(shù)據(jù)中心都存儲(chǔ)了大量的數(shù)據(jù)，這些數(shù)據(jù)以常規(guī)文件的形式存在.用F={f1,f2,··· ,fl}表示云計(jì)算系統(tǒng)中所有文件的集合，對(duì)于任意文件fi ∈F，fi的大小定義為S(fi)，F(xiàn)(di)表示存儲(chǔ)在數(shù)據(jù)中心di上的所有文件.

表1 符號(hào)列表Table1 List of notations

圖1展示了一個(gè)云數(shù)據(jù)中心內(nèi)部資源-任務(wù)-數(shù)據(jù)文件三者之間關(guān)系的簡單示例.d為數(shù)據(jù)中心，R為數(shù)據(jù)中心間的路由，所有的數(shù)據(jù)中心通過不同的網(wǎng)絡(luò)鏈路互通.f為存儲(chǔ)在數(shù)據(jù)中心內(nèi)部的文件，每個(gè)數(shù)據(jù)中心還擁有不同數(shù)量的CPU 計(jì)算資源.

云提供商提供多樣化的VM 實(shí)例，包含各種離散的硬件配置.用I={τ1,τ2,··· ,τM}表示VM 的配置集合，用sk表示實(shí)例τk的運(yùn)算速度，用表示租用價(jià)格，則實(shí)例τk在數(shù)據(jù)中心di上運(yùn)行t時(shí)間段的計(jì)算成本記作C=.也就是說，成本費(fèi)用與時(shí)間線性相關(guān)，如圖2(a)所示.然而，當(dāng)用戶租用云資源時(shí)，服務(wù)提供商通常以時(shí)間為單位進(jìn)行區(qū)間收費(fèi)（例如Amazon EC2 收費(fèi)的時(shí)間單位為1 h），此時(shí)成本費(fèi)用則隨時(shí)間發(fā)生階梯變化，如圖2(b)所示.由于所需VM 的租用時(shí)間同文件傳輸量、網(wǎng)絡(luò)帶寬分配大小有關(guān)，階梯定價(jià)同時(shí)受到多個(gè)因素的影響，對(duì)其進(jìn)行細(xì)微調(diào)整都會(huì)影響整體的調(diào)度結(jié)果和總體成本，因此階梯定價(jià)使跨地域數(shù)據(jù)中心間的調(diào)度問題更加復(fù)雜.類似地，云提供商提供的網(wǎng)絡(luò)資源[23]包含離散的帶寬配置，這些配置集合用B表示：B={b1,··· ,bN}.則從di到dj、租用br帶寬且通信時(shí)間為t的傳輸成本可定義為其中是從di到di租用br帶寬的價(jià)格，br ∈B.

圖1 云數(shù)據(jù)中心模型示例Figure1 Example of cloud system

圖2 線性價(jià)格和階梯價(jià)格Figure2 Linear pricing and piecewise pricing

1.2 任務(wù)模型

將任務(wù)與文件之間的依賴關(guān)系網(wǎng)絡(luò)記作GV=(V ∪F,EV)，其中V={v1,v2,··· ,vn}表示任務(wù)集合，表示文件和任務(wù)之間的關(guān)系，表示文件fl是任務(wù)vj的輸入之一.對(duì)于一個(gè)任務(wù)vj ∈V，有其中，vLj為該任務(wù)的計(jì)算負(fù)荷，vcj為任務(wù)vj所需的計(jì)算資源量，F(xiàn)(vj) 表示vj的輸入文件集合.圖3為一個(gè)任務(wù)模型的示例，任務(wù)和文件屬于多對(duì)多關(guān)系，多個(gè)任務(wù)可能將同一個(gè)文件作為輸入（如f3），而多個(gè)文件也可能作為同一個(gè)任務(wù)的輸入（如v3）.

圖3 任務(wù)模型Figure3 Task model

1.3 問題定義

對(duì)于給定云模型和任務(wù)模型，以下為調(diào)度問題的形式化定義.

xijkr為一個(gè)二進(jìn)制變量，定義為：如果選擇τk虛擬機(jī)和br帶寬在數(shù)據(jù)中心di中執(zhí)行任務(wù)vj，xijkr值為1；否則，其值為0.

任務(wù)的總成本包括數(shù)據(jù)傳輸成本和計(jì)算成本.因?yàn)閿?shù)據(jù)中心內(nèi)的數(shù)據(jù)傳輸基本不產(chǎn)生開銷，因此只考慮由數(shù)據(jù)中心間的文件傳輸帶來的成本.任務(wù)vj的數(shù)據(jù)傳輸成本計(jì)算公式為

式中，表示從存儲(chǔ)文件由fl數(shù)據(jù)中心dfl到di傳輸文件fl所分配的帶寬，表示文件fl的傳輸時(shí)間.至于數(shù)據(jù)中心dfl到di之間的數(shù)據(jù)包發(fā)送和接收延遲相比數(shù)據(jù)傳輸耗時(shí)通常很小，因此可以忽略不計(jì).

數(shù)據(jù)的計(jì)算成本與計(jì)算時(shí)間和價(jià)格有關(guān).如果輸入文件不在本地存放，則需要將此文件從遠(yuǎn)程數(shù)據(jù)中心傳輸至本地的數(shù)據(jù)中心.在該場景下，必須等待文件傳輸完畢才可以執(zhí)行任務(wù)，于是總體完成時(shí)間包括數(shù)據(jù)傳輸時(shí)間和CPU 運(yùn)算時(shí)間，vj的計(jì)算成本公式為

式中，sτk為VMτk的計(jì)算速度.

因此任務(wù)vj的總成本為

拒絕任務(wù)vj可看作是將vj調(diào)度到擁有無限容量資源的虛擬數(shù)據(jù)中心dm+1（即），所提供VMs和帶寬vj資源以ψj為代價(jià)，即c(m+1)jkr=ψj,?k,r.給定m+1個(gè)數(shù)據(jù)中心，n個(gè)任務(wù)，m種VM 類型配置和N種帶寬配置，可以形式化定義調(diào)度問題.其中，目標(biāo)函數(shù)T1為

約束條件為

其中，式(6)確保在數(shù)據(jù)中心di上運(yùn)行的任務(wù)所需資源的總和不能超過dci；式(7)確保每個(gè)任務(wù)只能放置在一個(gè)數(shù)據(jù)中心上，且只能使用1 種類型虛擬機(jī)實(shí)例和1種帶寬配置；式(8)表示二進(jìn)制變量xijkr的約束.

上面所構(gòu)造的調(diào)度問題是NP-hard 問題，該問題很難得到最優(yōu)解.為此，本文在線性定價(jià)和階梯定價(jià)模型[6]下首先使用ALMM 實(shí)現(xiàn)近似的最優(yōu)調(diào)度，然后設(shè)計(jì)了一種Adjusting 算法來調(diào)整ALMM 生成的不可行解，從而得到一個(gè)可行的調(diào)度方案.由于ALMM 的收斂速度過慢，因此本文又提出了一種快速啟發(fā)式算法逼近最優(yōu)解.

2 線性定價(jià)下的調(diào)度

本節(jié)將介紹在線性定價(jià)模型下的ALMM 方法和Adjusting 算法.根據(jù)對(duì)亞馬遜、谷歌等云提供商的調(diào)查發(fā)現(xiàn)，VMs 帶寬的價(jià)格通常與VM 實(shí)例的帶寬配置成正比.對(duì)于VM 實(shí)例有：；對(duì)于帶寬則有：

從數(shù)據(jù)中心dfl到di租用br帶寬的價(jià)格可定義為

式中，α是一個(gè)常數(shù).將式(9)代入式(1)得

因此對(duì)于線性定價(jià)模型而言，傳輸成本與帶寬配置無關(guān).同樣，di中的VMτk的價(jià)格可以定義為

式中，β是一個(gè)常數(shù).將式(11)代入式(2)得

計(jì)算成本與VM 的計(jì)算速度sτk成正比且與數(shù)據(jù)中心間帶寬成反比，于是可以簡單地選擇最便宜的計(jì)算資源和最昂貴的VM 帶寬來實(shí)現(xiàn)最小化，使唯一的變量xijkr變成xij.如果將任務(wù)vj調(diào)度到數(shù)據(jù)中心di，則其值為1，否則將其設(shè)置為0.類似地，cijkr變成了cij.然后使用xij重新定義整數(shù)規(guī)劃的問題.此時(shí)目標(biāo)函數(shù)T2為

約束條件為

2.1 增廣拉格朗日乘子法

ALMM 方法分三步進(jìn)行.首先，對(duì)約束優(yōu)化問題進(jìn)行等價(jià)轉(zhuǎn)換變成一個(gè)無約束優(yōu)化問題.其次，建立一個(gè)動(dòng)態(tài)微分方程組無約束優(yōu)化函數(shù).最后，采用4 階RungeKutta 法求解.

首先將0/1 約束替換為二次凹等式約束，有

利用松弛線性等式不等式約束和拉格朗日乘子松弛二次凹等式約束，可以推導(dǎo)出無約束的增廣拉格朗日函數(shù)，公式為

式中，K為懲罰參數(shù)，min2{}為min{}的平方.λ= [λ11,λ12,··· ,λmn]表示拉格朗日乘子向量.建立了如下動(dòng)態(tài)系統(tǒng)

該動(dòng)態(tài)微分方程組可以采用4 階RungeKutta 法求解.

ALMM 利用拉格朗日乘子函數(shù)來保證可行解的條件.雖然在開始階段可以避免陷入0/1可行解，但實(shí)驗(yàn)發(fā)現(xiàn)，有時(shí)仍然會(huì)違反式(6)所示的約束條件，尤其是當(dāng)問題的輸入大小（任務(wù)數(shù)）增加時(shí)更是如此.例如，如果把圖3中任務(wù)調(diào)度到圖1的數(shù)據(jù)中心系統(tǒng)中，由ALMM（相關(guān)參數(shù)設(shè)置：K= 120，μ= 10，stepsize= 10?5）得到的結(jié)果顯示，任務(wù)v1和v4都被調(diào)度到數(shù)據(jù)中心d4.因?yàn)関c1=3，vc4=3，dc4=4，v1和v4的總資源需求超過了d4的總資源容量.因此違背了式(6)的約束條件.在這種情況下，調(diào)度方案必須適當(dāng)?shù)恼{(diào)整，從而在維持成本最小化的前提下得出可行的調(diào)度結(jié)果.

2.2 Adjusting 算法

當(dāng)ALMM 生成的解決方案不可行時(shí)需要調(diào)用Adjusting 算法.該算法的基本思想是，將任務(wù)的子集從過載的數(shù)據(jù)中心遷移到另一個(gè)數(shù)據(jù)中心，由任務(wù)遷移所增加的成本應(yīng)該盡可能的小.

假設(shè)數(shù)據(jù)中心da過載，用dVa表示調(diào)度到da的任務(wù)集合，?vj ∈dVa，對(duì)于數(shù)據(jù)中心da的任意調(diào)度任務(wù)vj，則將vj移動(dòng)到另一個(gè)數(shù)據(jù)中心（?vd ∈ND并且dbda）所產(chǎn)生的成本增量為

為了降低成本，Adjusting 算法首先選擇其中一個(gè)可以最小化?cvjab的任務(wù)并將其移動(dòng)至數(shù)據(jù)中心db，迭代此操作直到所有數(shù)據(jù)中心都能確保滿足資源容量約束.在遷移過程中，任務(wù)的總?cè)萘啃枨罂赡艹^了數(shù)據(jù)中心的總?cè)萘肯拗?事實(shí)上，即使已經(jīng)確定，仍然不能確保任務(wù)總能被完成.因此通過設(shè)置γ >1，保證僅當(dāng)其他數(shù)據(jù)中心的無可用容量時(shí)才將任務(wù)移動(dòng)到虛擬任務(wù)vm+1.此時(shí)需要引入虛擬數(shù)據(jù)中心dm+1，將任務(wù)移到dm+1也就意味著拒絕該任務(wù).

算法1 展示了Adjusting 算法的設(shè)計(jì)，在第1～2 行分別定義了2 個(gè)變量：使用布爾變量full[i]表示數(shù)據(jù)中心di是否已滿，且初始化為false；Combsi表示數(shù)據(jù)中心di和除去di的數(shù)據(jù)中心中的所有任務(wù)組合.首先，找到過載的數(shù)據(jù)中心（第3～5行），并將其full[i]設(shè)置為true.然后，遍歷每個(gè)過載的數(shù)據(jù)di，移動(dòng)其中一些任務(wù)（第6～17 行），將任務(wù)分配給其他數(shù)據(jù)中心.對(duì)于在數(shù)據(jù)di中的每一個(gè)任務(wù)vj按照式(18)計(jì)算，?dk ∈ND ∪dm+1.然后，對(duì)Combsi中的組合按照的升序（第10 行）進(jìn)行排序.由此具有最小成本增量的的組合總是最先被選擇.在第11～17 行中，如果數(shù)據(jù)中心dk能容納任務(wù)vj，該任務(wù)就會(huì)被移動(dòng)到數(shù)據(jù)中心dk，并且將所有任務(wù)vj的組合從Combsi中刪除（第14 行）.若數(shù)據(jù)中心di不再過載，將full[i]設(shè)置為false(第15～17行).否則，在Combsi中移動(dòng)下一個(gè)任務(wù).

3 階梯定價(jià)下的調(diào)度

在階梯定價(jià)模型下，資源按時(shí)間進(jìn)行收費(fèi).如果任務(wù)的實(shí)際執(zhí)行時(shí)間不是時(shí)間單位的整數(shù)，則進(jìn)行向上取整.因此，式(10)和(12)分別轉(zhuǎn)換為

此時(shí)，與帶寬配置有關(guān).假設(shè)在圖1中有3 種可用的帶寬配置類型，其中b1= 512，b2=1 024，b3=2 048，且它們?cè)跀?shù)據(jù)中心d1和d4間的價(jià)格分別是=1.8 美元/h，=3.6 美元/h，= 7.2 美元/h.假設(shè)有兩種類型的VM 配置，計(jì)算速度分別為sτ1=400，sτ2= 800.它們?cè)跀?shù)據(jù)中心d4中的價(jià)格分別為= 1.6美元/h，= 3.2 美元/h.如果v2L=124，調(diào)度任務(wù)v2到數(shù)據(jù)中心d4，使用τ1配置的VM 執(zhí)行任務(wù)并且采用大小的帶寬進(jìn)行數(shù)據(jù)傳輸（如文件f1），則總體成本計(jì)算為6.8，當(dāng)τ1和b2被選中時(shí)成本最小.因此對(duì)于階梯計(jì)價(jià)模型，除了需要分配數(shù)據(jù)中心，還需要為每個(gè)任務(wù)和每個(gè)文件數(shù)據(jù)流分配VM 和帶寬.

這里仍然使用ALMM 方法來解決（如式(5)～(8)）.對(duì)應(yīng)的無約束增廣拉格朗日量函數(shù)為

動(dòng)態(tài)系統(tǒng)的拉格朗日微分方程為

式中，p=1,2,··· ,m；q=1,2,··· ,n；u=1,2,··· ,M；v=1,2,··· ,N.

同樣，ALMM 的結(jié)果調(diào)度可能違反約束條件從而導(dǎo)致出現(xiàn)不可行解，需要應(yīng)用Adjusting算法進(jìn)行調(diào)整.對(duì)ALMM 和Adjusting 算法的處理過程可以表示為

式中，ROUND()是Adjusting 算法中的上取整操作.

4 DVDS 算法

設(shè)置K= 120，μ= 10，stepsize= 10?5，采用圖1所示的云數(shù)據(jù)中心模型評(píng)估ALMM的效率.實(shí)驗(yàn)發(fā)現(xiàn)，隨著任務(wù)數(shù)量的增長，ALMM 收斂也變得非常慢.圖4(a)顯示，當(dāng)提交70 個(gè)任務(wù)時(shí)，在線性定價(jià)模型下ALMM 收斂到可行解所需要的時(shí)間超過10 min.此外，如果考慮階梯定價(jià)模式下，ALMM 在10 min 內(nèi)只能對(duì)10 個(gè)任務(wù)得到一個(gè)可行的解決方案（圖4(b)）.為了提高效率，本文設(shè)計(jì)了一個(gè)啟發(fā)式搜索算法DVDS，旨在短時(shí)間內(nèi)找到一個(gè)較優(yōu)的調(diào)度方案.

定義uijkr為vj的值密度，則有顯然將任務(wù)調(diào)度到uijkr值小的數(shù)據(jù)中心可以降低總體調(diào)度結(jié)果的成本，同時(shí)為了解決數(shù)據(jù)中心的總?cè)萘抗?yīng)不足的情況，仍然引入虛擬數(shù)據(jù)中心dm+1來進(jìn)行任務(wù)調(diào)度.

DVDS 算法的設(shè)計(jì)思想是：首先遍歷vj、di、τk、br所有可能的組合，計(jì)算對(duì)應(yīng)的cijkr和uijkr，其中vj ∈V，dj ∈ND ∪dm+1，τk ∈I,br ∈B（第2～3 行）.然后將Combs 中的組合根據(jù)uijkr的值進(jìn)行升序排列（第4 行）.在算法的第5～8 行，迭代選擇具有最小uijkr值的Combs組合，并將對(duì)應(yīng)的任務(wù)vj調(diào)度到數(shù)據(jù)中心di，同時(shí)使用VM 配置τk和帶寬配置br.一旦任務(wù)vj的配置完成，它的所有相關(guān)數(shù)據(jù)將從Combs 中的組合移除(第8 行)，然后算法繼續(xù)執(zhí)行，遍歷Combs 中的組合并調(diào)度下一個(gè)任務(wù).DVDS 算法的時(shí)間復(fù)雜度為O(mnMNlog(mnMN)).

表2 調(diào)度結(jié)果Table2 Schedule results

給定圖1中的云數(shù)據(jù)中心模型和圖3中的任務(wù)配置，設(shè)置γ=2，表2給出了ALMM、Adjusting 算法、DVDS 算法分別在線性定價(jià)和階梯定價(jià)模型下的調(diào)度結(jié)果.一般來講，階梯定價(jià)模型相比線性定價(jià)模型成本更高.線性定價(jià)中總是選擇最便宜的VM 和最昂貴的帶寬配置，而階梯定價(jià)模型則有更多不同方案可選擇.在這兩種模型中，ALMM 的調(diào)度都不能保證數(shù)據(jù)中心d4的資源約束不被打破，Adjusting 算法將任務(wù)v1從數(shù)據(jù)中心d4移動(dòng)到虛擬數(shù)據(jù)中心d5.對(duì)于DVDS 算法，任務(wù)v1被調(diào)度到d5.此外，發(fā)現(xiàn)DVDS 調(diào)度方案產(chǎn)生的成本比ALMM 的更高.

5 性能評(píng)估

5.1 實(shí)驗(yàn)環(huán)境設(shè)置

1）云數(shù)據(jù)中心系統(tǒng)

基于跨地域分布的數(shù)據(jù)中心系統(tǒng)China-VO 來評(píng)估ALMM+Adjusting 算法以及DVDS算法的性能.該系統(tǒng)由5 個(gè)具有不同的CPU 計(jì)算性能以及虛擬機(jī)（帶寬）價(jià)格的數(shù)據(jù)中心構(gòu)成.通過給數(shù)據(jù)中心配置不同數(shù)量的處理單元（process elements,PEs）來模擬每個(gè)數(shù)據(jù)中心的計(jì)算能力，例如北京、上海、南京、昆明、烏魯木齊5 處數(shù)據(jù)中心分別擁有900、850、690、350、160 個(gè)PE.對(duì)于帶寬配置則采用了兩種帶寬配置B={1 024,2 048}來模擬China-VO 系統(tǒng)內(nèi)部的網(wǎng)絡(luò).數(shù)據(jù)中心di到dj(?i,j ∈{1,··· ,5},i < j)的1 024 大小的帶寬每小時(shí)租用價(jià)格被設(shè)置為= 0.14+0.02(j ?i)，對(duì)于2 048 大小的帶寬租用價(jià)格則翻倍.對(duì)于VM 也模擬了兩種不同的配置：I={800,1600}（單位：MHz）.其中1 600 MHz 的CPU 對(duì)應(yīng)1 個(gè)完整的PE，而800 MHz 的CPU 對(duì)應(yīng)0.5 個(gè)PE.5 個(gè)數(shù)據(jù)中心在800 MHz 配置的CPU 的價(jià)格分別設(shè)置為{0.08,0.085,0.09,0.095,0.1}（單位：美元/h）.對(duì)于1 600 MHz的CPU 則價(jià)格翻倍.

2）文件

模擬2 000 個(gè)不同大小的文件并將其分散存儲(chǔ)到5 個(gè)數(shù)據(jù)中心，其中每個(gè)文件的大小都從[1 024,3 072]（單位：MB）的取值范圍中隨機(jī)選擇.

3）任務(wù)

由于ALMM 算法的收斂速度很慢，因此沒有模擬大規(guī)模的任務(wù)數(shù)量來評(píng)估ALMM+Adjusting 算法和DVDS 算法的性能.對(duì)于線性定價(jià)模型，最多模擬了150 個(gè)任務(wù)，而對(duì)于階梯定價(jià)模型，最多模擬16 個(gè)任務(wù).每個(gè)任務(wù)都要求一定數(shù)量的CPU，該值從[10,80]的取值范圍中隨機(jī)生成.每個(gè)任務(wù)的輸入文件數(shù)量也從[1,30]隨機(jī)生成.任務(wù)vj的負(fù)荷由vLj=ηS(F(vj))/CCR，其中η是一個(gè)標(biāo)量權(quán)重因子，CCR 表示通信與計(jì)算的比率.通過初始化CCR=[0.1,1.0,10.0]，可以在不同的工作負(fù)載下對(duì)算法進(jìn)行性能評(píng)估，例如，通信密集型的負(fù)載，或者計(jì)算密集型的負(fù)載.在所有實(shí)驗(yàn)中拒絕一個(gè)任務(wù)的懲罰參數(shù)γ都被設(shè)置為2.

本文的實(shí)驗(yàn)評(píng)估是在配備了Xeon E5-2600 v3 CPU 和128 GB 內(nèi)存的高性能服務(wù)器上進(jìn)行的.

5.2 執(zhí)行時(shí)間

圖4展示了線性定價(jià)模型和階梯定價(jià)模型下ALMM +Adjusting 算法和DVDS 算法的執(zhí)行時(shí)間與任務(wù)數(shù)量的函數(shù)關(guān)系.隨著任務(wù)數(shù)量的增加，通常ALMM +Adjusting 算法的執(zhí)行時(shí)間增長的比DVDS 算法的快得多.當(dāng)150 個(gè)任務(wù)在線性定價(jià)模型（參數(shù)為K= 120,μ=1.0,!stepsize = 10?5）下提交時(shí)，ALMM +Adjusting 算法收斂到一個(gè)可接受的時(shí)間需要近3 500 s，而DVDS 算法不到1 s 就能獲得結(jié)果.此外，對(duì)于階梯定價(jià)模型，ALMM+Adjusting算法調(diào)度16 個(gè)任務(wù)需要花費(fèi)近2 000 s 才能收斂到可行解.由于耗時(shí)過長，因此不必進(jìn)行更多實(shí)驗(yàn)來對(duì)比執(zhí)行效率.

圖4 算法執(zhí)行時(shí)間Figure4 Execution time of proposed algorithms

5.3 成本

圖5(a)～(c)為線性定價(jià)模型下ALMM+Adusting 算法和DVDS 算法生成的成本.DVDS生成結(jié)果的成本一般大于ALMM +Adjusting 算法，因?yàn)锳LMM 方法可以收斂到近似最優(yōu)解決方案.在線性定價(jià)模型中，當(dāng)任務(wù)數(shù)目小于50 時(shí)，兩者之間的差異很小.這是因?yàn)樵谶@種情況下，大多數(shù)任務(wù)總是可以被調(diào)度到具有最低成本的數(shù)據(jù)中心同時(shí)滿足資源量約束.它們之間的差異隨著任務(wù)數(shù)量的增加而增加.在CCR=0.1、CCR=1.0、CCR=10.0 時(shí)，DVDS 算法平均比ALMM +Adjusting 算法增加9.59%、11.5%、10.3%的成本.因此，在不同類型的工作量下，兩者的成本沒有顯著差異.

圖5 總成本作為任務(wù)數(shù)量的函數(shù)（LP：線性定價(jià)，PP：階梯定價(jià)）Figure5 Total cost as a function of the number of tasks (LP:linear pricing,PP:piecewise pricing)

圖5中的(d)～(f)顯示了階梯定價(jià)模型下ALMM+Adjusting 算法產(chǎn)生的成本費(fèi)用.與線性定價(jià)模型下的實(shí)驗(yàn)設(shè)置不同，階梯定價(jià)模型中ALMM 算法收斂到一個(gè)較優(yōu)解需要花費(fèi)大量的時(shí)間，因此采用了人工方法將數(shù)據(jù)中心的資源容量降低到范圍內(nèi)的隨機(jī)數(shù)[40，120].因?yàn)閿?shù)據(jù)中心計(jì)算量有限，即使任務(wù)數(shù)量很少，算法也不可能在滿足約束的前提下，將每個(gè)任務(wù)都調(diào)度到合適的數(shù)據(jù)中心.可以看到，當(dāng)任務(wù)數(shù)小于7 時(shí)，兩種算法在成本上的差異是相當(dāng)小的.隨著任務(wù)數(shù)的增加，相比ALMM +Adjusting 算法成本高，DVDS算法平均分別在CCR=0.1、CCR=1、CCR=10 下多產(chǎn)生了12.8%、12.1%、10.8%的成本.

此外，在不改變文件的數(shù)量前提下，可以通過增加數(shù)據(jù)中心的數(shù)量來評(píng)估算法的性能.此時(shí)文件的存儲(chǔ)更加分散，數(shù)據(jù)中心間的文件傳輸量也隨之增多，任務(wù)調(diào)度過程也會(huì)產(chǎn)生更大的傳輸成本.從圖6可以看出，由于數(shù)據(jù)傳輸成本增加，兩種算法得到的調(diào)度結(jié)果成本隨著數(shù)據(jù)中心數(shù)量的增多而增加，但是當(dāng)數(shù)據(jù)中心的容量增加時(shí)，任務(wù)有可能被安排在更合適的數(shù)據(jù)中心上，因此兩種算法之間的差異減小.注意到當(dāng)數(shù)據(jù)中心數(shù)分別等于5 和11 時(shí)（圖6(a)和(b)），DVDS 算法產(chǎn)生的傳輸成本有所下降，這是由于實(shí)驗(yàn)評(píng)估結(jié)果的隨機(jī)性導(dǎo)致的，如果進(jìn)行多組實(shí)驗(yàn)并計(jì)算統(tǒng)計(jì)分布，則這種現(xiàn)象會(huì)逐漸消除.即便如此，整體的調(diào)度結(jié)果成本也同數(shù)據(jù)中心數(shù)量正相關(guān)，所以實(shí)驗(yàn)結(jié)果是符合預(yù)期的.

圖6 總成本作為數(shù)據(jù)中心數(shù)量的函數(shù)Figure6 Total cost as a function of the number of datacenters

6 相關(guān)工作

針對(duì)云數(shù)據(jù)中心調(diào)度的成本和效率問題，科研工作者已經(jīng)開展了大量的研究.本文對(duì)其進(jìn)行了總結(jié)，這些研究基本大體上可以分為兩類：研究增加IaaS 供應(yīng)商收入與研究降低IaaS 用戶成本.

6.1 增加IaaS 供應(yīng)商收入

文獻(xiàn)[1]和[20]闡述了構(gòu)建云數(shù)據(jù)中心的成本.其中占比最大的部分是站點(diǎn)基礎(chǔ)設(shè)施投資成本，遠(yuǎn)遠(yuǎn)超過了IT 成本.并且約1/4 的年化總成本與運(yùn)營費(fèi)用有關(guān)，其中能源費(fèi)用占比10%以上.為了降低總成本，可以通過使用VM 整合節(jié)省能源，其中虛擬機(jī)被整合到幾個(gè)處于運(yùn)行狀態(tài)的服務(wù)器上，其余的服務(wù)器可以切換至低功耗狀態(tài)[13-15].降低由于服務(wù)器故障或運(yùn)行資源不足而導(dǎo)致的違反SLA 所帶來的成本，也可以增加云服務(wù)提供商的收入.文獻(xiàn)[16]提出的一種類似于binpacking 的算法將VM調(diào)度到可用的機(jī)器上，為IaaS 供應(yīng)商帶來更多的收入.為了應(yīng)對(duì)動(dòng)態(tài)變化的資源需求，文獻(xiàn)[9]提出了市場驅(qū)動(dòng)的資源分配算法來實(shí)現(xiàn)動(dòng)態(tài)定價(jià)和調(diào)度請(qǐng)求處理，最大限度地提高云計(jì)算提供商的收入.文獻(xiàn)[17]利用不同數(shù)據(jù)中心之間的電價(jià)變化來降低IaaS 供應(yīng)商的電力成本.云提供商也可以在不增加云資源[18]的情況下通過增加任務(wù)請(qǐng)求從而提供更多服務(wù)來增加收入.為了提高云系統(tǒng)的資源效率，文獻(xiàn)[19-22]提出的云資源管理系統(tǒng)通過一系列的調(diào)度算法和數(shù)據(jù)放置優(yōu)化，提高了資源管理的效率，降低了運(yùn)營成本.文獻(xiàn)[23]在容器級(jí)別通過彈性分配資源實(shí)現(xiàn)高效率的云系統(tǒng)資源配給，從而降低了云系統(tǒng)的運(yùn)營成本.文獻(xiàn)[24]提供了橫向和縱向兩個(gè)維度的動(dòng)態(tài)資源擴(kuò)展操作，HPS+[25]采用超圖分割算法來實(shí)現(xiàn)高效的數(shù)據(jù)中心調(diào)度.這些方法在一定程度上提高了云數(shù)據(jù)中心的資源使用效率.

6.2 為IaaS 用戶節(jié)省成本

IaaS 用戶（或業(yè)務(wù)服務(wù)提供者）從云服務(wù)提供商租用VM 實(shí)例，并通過服務(wù)客戶來獲得收益.租用更多VM 可以減少作業(yè)響應(yīng)時(shí)間并降低違反SLA 帶來的風(fēng)險(xiǎn)[26-29].然而，服務(wù)器增多后會(huì)提高服務(wù)的管理成本.文獻(xiàn)[30]通過研究IaaS 供應(yīng)商的動(dòng)態(tài)定價(jià)方案和客戶滿意度優(yōu)化IaaS 用戶的效益.對(duì)于特定的工作負(fù)載，文獻(xiàn)[31]通過計(jì)算從IaaS 提供商租用的最優(yōu)服務(wù)器配置，使數(shù)據(jù)中心的預(yù)期收益最大化.文獻(xiàn)[32]提出了一種工作流調(diào)度算法，利用不同的VM實(shí)例，使最大完成時(shí)間和用戶的租用成本最小化.同樣，文獻(xiàn)[33]評(píng)估了12 種分配策略的作業(yè)完成時(shí)間和成本方面的性能.注意到當(dāng)前的IaaS 提供商提供了不同類型服務(wù)器供用戶選擇，其中包括不可撤銷的預(yù)留型實(shí)例和價(jià)格更便宜但可撤銷的彈性實(shí)例，IaaS 用戶可以利用兩者的組合來獲得顯著的經(jīng)濟(jì)收益[34].

7 結(jié) 語

本文對(duì)跨地域分布云數(shù)據(jù)中心系統(tǒng)的成本效率調(diào)度問題進(jìn)行了形式化建模.使用ALMM方法來尋找每個(gè)任務(wù)的最優(yōu)調(diào)度結(jié)果.由于ALMM 生成的調(diào)度方案可能會(huì)違反數(shù)據(jù)中心的資源容量限制而不可行，因此本文提出了一種Adjusting 算法對(duì)ALMM 的結(jié)果進(jìn)行調(diào)整，使其成為可行解.本文還設(shè)計(jì)了DVDS 算法，能在比ALMM 更短的時(shí)間內(nèi)獲得較優(yōu)的調(diào)度方案，而其產(chǎn)生的成本僅比ALMM 高出10%左右.

在以后研究中，將探討如何結(jié)合工作特點(diǎn)和系統(tǒng)進(jìn)一步降低云服務(wù)提供商的運(yùn)行成本以提高資源效率.