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

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

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

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

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

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

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

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

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

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

表1 符號列表Table1 List of notations

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

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

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

圖2 線性價格和階梯價格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的輸入之一.對于一個任務(wù)vj ∈V，有其中，vLj為該任務(wù)的計算負荷，vcj為任務(wù)vj所需的計算資源量，F(xiàn)(vj) 表示vj的輸入文件集合.圖3為一個任務(wù)模型的示例，任務(wù)和文件屬于多對多關(guān)系，多個任務(wù)可能將同一個文件作為輸入（如f3），而多個文件也可能作為同一個任務(wù)的輸入（如v3）.

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

1.3 問題定義

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

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

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

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

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

式中，sτk為VMτk的計算速度.

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

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

約束條件為

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

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

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

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

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

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

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

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

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

約束條件為

2.1 增廣拉格朗日乘子法

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

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

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

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

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

ALMM 利用拉格朗日乘子函數(shù)來保證可行解的條件.雖然在開始階段可以避免陷入0/1可行解，但實驗發(fā)現(xiàn)，有時仍然會違反式(6)所示的約束條件，尤其是當(dāng)問題的輸入大?。ㄈ蝿?wù)數(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.因為vc1=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 生成的解決方案不可行時需要調(diào)用Adjusting 算法.該算法的基本思想是，將任務(wù)的子集從過載的數(shù)據(jù)中心遷移到另一個數(shù)據(jù)中心，由任務(wù)遷移所增加的成本應(yīng)該盡可能的小.

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

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

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

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

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

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

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

動態(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算法進行調(diào)整.對ALMM 和Adjusting 算法的處理過程可以表示為

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

4 DVDS 算法

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

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

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

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

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

5 性能評估

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

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

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

2）文件

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

3）任務(wù)

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

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

5.2 執(zhí)行時間

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

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

5.3 成本

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

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

圖5中的(d)～(f)顯示了階梯定價模型下ALMM+Adjusting 算法產(chǎn)生的成本費用.與線性定價模型下的實驗設(shè)置不同，階梯定價模型中ALMM 算法收斂到一個較優(yōu)解需要花費大量的時間，因此采用了人工方法將數(shù)據(jù)中心的資源容量降低到范圍內(nèi)的隨機數(shù)[40，120].因為數(shù)據(jù)中心計算量有限，即使任務(wù)數(shù)量很少，算法也不可能在滿足約束的前提下，將每個任務(wù)都調(diào)度到合適的數(shù)據(jù)中心.可以看到，當(dāng)任務(wù)數(shù)小于7 時，兩種算法在成本上的差異是相當(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ù)量來評估算法的性能.此時文件的存儲更加分散，數(shù)據(jù)中心間的文件傳輸量也隨之增多，任務(wù)調(diào)度過程也會產(chǎn)生更大的傳輸成本.從圖6可以看出，由于數(shù)據(jù)傳輸成本增加，兩種算法得到的調(diào)度結(jié)果成本隨著數(shù)據(jù)中心數(shù)量的增多而增加，但是當(dāng)數(shù)據(jù)中心的容量增加時，任務(wù)有可能被安排在更合適的數(shù)據(jù)中心上，因此兩種算法之間的差異減小.注意到當(dāng)數(shù)據(jù)中心數(shù)分別等于5 和11 時（圖6(a)和(b)），DVDS 算法產(chǎn)生的傳輸成本有所下降，這是由于實驗評估結(jié)果的隨機性導(dǎo)致的，如果進行多組實驗并計算統(tǒng)計分布，則這種現(xiàn)象會逐漸消除.即便如此，整體的調(diào)度結(jié)果成本也同數(shù)據(jù)中心數(shù)量正相關(guān)，所以實驗結(jié)果是符合預(yù)期的.

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

6 相關(guān)工作

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

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

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

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

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

7 結(jié) 語

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

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