宋彩利，梁 斌，李 皎

(西安石油大學 計算機學院，陜西 西安 710065)

引 言

云服務(wù)的最終目的是使云用戶可以穩(wěn)定、快捷和方便地使用彈性的計算和存儲服務(wù)。因此，提高云數(shù)據(jù)中心的穩(wěn)定性不僅可以提升用戶的使用體驗，更能增加云服務(wù)提供商收益。然而，大型云數(shù)據(jù)中心都是由低性能的物理機構(gòu)成，通過虛擬化技術(shù)將其以虛擬機的形式租用給云用戶，這樣就會由于機器性能不穩(wěn)定而導致虛擬機故障。現(xiàn)代云數(shù)據(jù)中心為了提升云服務(wù)的穩(wěn)定性和可靠性，通常在建立虛擬機時會設(shè)計合理的容錯機制從而保證云任務(wù)順利執(zhí)行。但是，隨著云數(shù)據(jù)中心規(guī)模不斷擴大，大量的故障和容錯問題已經(jīng)成為制約云數(shù)據(jù)中心進一步發(fā)展的瓶頸之一。

云數(shù)據(jù)中心針對虛擬機故障的容錯策略主要可以分為副本復制和重調(diào)度。副本復制一般開始于云任務(wù)映射初始階段。當云數(shù)據(jù)中心的調(diào)度系統(tǒng)在進行云任務(wù)映射時，為了避免虛擬機故障，會激活一些冗余的虛擬機對部分云任務(wù)進行多次映射。其通過增加副本數(shù)量的方法，提升了云任務(wù)順利完成的概率。這種方法雖然簡單方便，但是也存在很多隱患。首先，由于虛擬機的故障是一個隨機事件，調(diào)度系統(tǒng)并不能預測故障的發(fā)生，從而導致命中故障的幾率較低。其次，冗余的虛擬機會帶來云服務(wù)提供商成本的上升從而降低其收益。最后，副本數(shù)量的選擇也是一個復雜的問題，設(shè)計人員需要綜合統(tǒng)計學和半導體等多學科知識綜合進行考慮，因此它的復雜度帶來的損失將遠大于問題自身的收益。重調(diào)度策略根據(jù)虛擬機的執(zhí)行情況進行動態(tài)的調(diào)節(jié)，當執(zhí)行云任務(wù)的虛擬機發(fā)生故障時，該調(diào)度系統(tǒng)會為失效云任務(wù)重新選擇虛擬機進行映射。

之前的學者對云數(shù)據(jù)中心的調(diào)度和重調(diào)度算法進行了部分的研究。Yao等[1]提出了一種免疫機制，針對云系統(tǒng)(IRW)中的工作流提出了一種重新調(diào)度算法。有4個單位可以模仿IRW算法中的免疫系統(tǒng)。監(jiān)視單元監(jiān)視資源池中每個虛擬機的可能故障。一旦檢測到資源故障，就會觸發(fā)響應單元進行搜索存儲單元或?qū)W習單元中的適當策略，用于重新安排可用時間資源。如果沒有可用的虛擬機都能滿足服務(wù)質(zhì)量，則將為該云任務(wù)創(chuàng)建新的虛擬機。Liang等[2]提出基于內(nèi)存利用率的云任務(wù)調(diào)度算法從而提高物理機綜合利用率并降低云數(shù)據(jù)中心能耗。Topcuoglu等[3]針對有限數(shù)量的異構(gòu)處理器提出了兩種新穎的調(diào)度算法，目的是同時滿足高性能和快速調(diào)度時間要求，分別稱為異構(gòu)最早完成時間(HEFT)算法和關(guān)鍵路徑-處理器(CPOP)算法。Chen等[4]考慮了互聯(lián)網(wǎng)托管中同質(zhì)資源的能源效率管理問題，其主要挑戰(zhàn)是確定資源需求使得每個應用程序在其當前請求負載級別并以最有效的方式分配資源，這樣可以根據(jù)可用預算和當前用戶的服務(wù)需求進行協(xié)商，即平衡資源使用成本以及收益。Raghavendra等[5]通過組合和管理數(shù)據(jù)中心環(huán)境協(xié)調(diào)5種不同的電力管理政策，從控制理論的角度探討了問題并應用了一個反饋控制循環(huán)以協(xié)調(diào)控制器的動作?；贚P的無變化VM放置算法可以以最低的能耗生成VM放置。另一方面，該方法的可行性驅(qū)動隨機VM放置(FDSP)算法與基于LP的算法無縫配合，以實現(xiàn)理想的放置可行性。王鵬等[6]實現(xiàn)了云計算集群相空間投影在不同負載請求情況下平穩(wěn)的點狀聚集。通過仿真實驗利用相空間負載均衡度、廣義溫度、廣義熵等參數(shù)和集群的相空間投影。Dodonov等[7]提出了一種基于預測的方法用于網(wǎng)格中調(diào)度分布式應用程序。文獻中提議，遷移如果較低，則傳達流程預期通信的成本與最小化總執(zhí)行時間目標，并證明了這一點可以有效地應用于網(wǎng)格。但是由于虛擬機遷移成本較高，因此無法真正應用于虛擬化數(shù)據(jù)中心。Plankensteiner等[8]提出了一種新的啟發(fā)式方法，稱為“重新提交影響”，以支持科學流程中的容錯執(zhí)行異構(gòu)并行和分布式計算環(huán)境。與相關(guān)方法相比，該方法可以有效地使用在新的或不熟悉的環(huán)境中，即使沒有歷史執(zhí)行或故障跟蹤模型。Moghaddam等[9]提出的虛擬機整合算法在每個階段都包含不同的模型。在第一階段，為各個VM開發(fā)了不同的微調(diào)機器學習(ML)預測模型，以預測觸發(fā)主機遷移的最佳時間。對于第二階段，從字典的角度來考慮選擇虛擬機進行遷移時的遷移時間和主機CPU使用率。最后，開發(fā)了一種基于最佳適合遞減(BFD)算法的新方法，為要遷移的VM選擇目標主機。與基準VM整合算法進行了比較，該算法使用本地回歸來檢測過度利用的主機，VM選擇階段所需的遷移時間最短，并且Power-Aware最適合主機選擇階段。最終，該算法大幅降低了云數(shù)據(jù)中心能耗。Fei和Hadji等[10-11]為了增強系統(tǒng)利用率的性能測量而介紹了基于閾值的負載均衡概念，負載分配和負載均衡策略一起可以減少總執(zhí)行時間并增加系統(tǒng)吞吐量，并且討論了能耗和負載矩陣以保持定時更新。但是全局最優(yōu)解決方案會產(chǎn)生許多不必要的遷移，無法工作在大規(guī)模的云計算環(huán)境中。Khandelwal等[12]旨在提出回歸隨機森林模型，以預測提前一周和提前一天的現(xiàn)貨價格。該預測將幫助云用戶提前計劃何時購買競價型實例，并且還幫助他們進行投標決策以最小化執(zhí)行成本和超標失敗概率。Sharma等[13]針對數(shù)據(jù)中心的熱效資源管理進行了大量的研究工作，研究表明軟件驅(qū)動的熱管理和溫度感知工作負載的放置帶來了額外的節(jié)能。然而，虛擬化數(shù)據(jù)中心背景下的熱管理問題尚未進行調(diào)查，且沒有研究根據(jù)當前資源利用率通過熱量和網(wǎng)絡(luò)優(yōu)化虛擬化數(shù)據(jù)中心綜合優(yōu)化的方法進行虛擬機放置。Chen等[14]提出了一種動態(tài)任務(wù)重排和重新調(diào)度算法，從任務(wù)之間的優(yōu)先級約束中利用調(diào)度靈活性。算法可以優(yōu)化多個工作流之間的資源分配，并且通常會停止延遲執(zhí)行對后續(xù)任務(wù)的影響。

這些算法雖然解決了部分技術(shù)問題。但是它們都未考慮以下幾個方面。首先，云數(shù)據(jù)中心也會提供包含不同頻率CPU的虛擬機供云用戶選擇，在進行失效云任務(wù)的重調(diào)度時，系統(tǒng)可以根據(jù)它的截止時間選擇高頻率CPU的虛擬機進行映射從而節(jié)約成本。其次，由于之前的研究中對部分云任務(wù)進行放棄，這就意味著最終無法向云用戶交付結(jié)果。這樣不僅會帶來收益的降低，更重要的是服務(wù)品牌和企業(yè)形象的損失。延遲的交付雖然會降低云用戶再次購買云服務(wù)的幾率但是至少保證了企業(yè)的基本信譽。因此即使會產(chǎn)生較大的代價，云服務(wù)提供商也應該盡可能地完成所有的云任務(wù)。最后，延遲交付的賠償也決定了云服務(wù)提供商的最終收益，重調(diào)度策略必須根據(jù)賠償比率進行合理的設(shè)計使得收益最大化。

基于以上原因，提出了面向云數(shù)據(jù)中心的成本感知容錯算法(Cost-aware Fault-tolerant Algorithm for Cloud Data Centers，CAFT)。該調(diào)度策略通過提高云任務(wù)的故障修復率從而降低云服務(wù)提供商的損失。

1 云數(shù)據(jù)中心重調(diào)度模型及定義

1.1 云數(shù)據(jù)中心整體架構(gòu)

首先介紹云數(shù)據(jù)中心的整體架構(gòu)。研究的云數(shù)據(jù)中心通過虛擬化技術(shù)向云用戶提供服務(wù)。該云數(shù)據(jù)中心包含了虛擬機集合VM={vm1,vm2,…,vmn}，其中n代表了該云數(shù)據(jù)中心所能提供的虛擬機總數(shù)。每個虛擬機可以表示為vmi={ci,mi,si,pi,ni,ti,ei}，其中ci,mi,si,pi,ni,ti,ei分別代表每臺虛擬機包含的CPU核數(shù)量、內(nèi)存大小(單位：GB)、CPU核的處理速度(單位為MIPS)、CPU核的使用價格(單位為$/h，低頻=price_low,高頻=price_high)、該虛擬機上所運行的云任務(wù)編號、虛擬機的運行時間(單位為秒)及虛擬機的狀態(tài)(1：正常，2：故障和3：副本)。云用戶所提交的云任務(wù)也可以表示為一個云任務(wù)集合CT={ct1,ct2,…,ctm}，其中m代表這個集合中云任務(wù)的個數(shù)。通過調(diào)度算法依次將該集合中的云任務(wù)映射到相應的虛擬機上執(zhí)行，每個云任務(wù)都可以描述為ctj={lj,mj,dj,tj,pj,fj}的形式，其中l(wèi)j,mj,dj,tj,pj,fj分別代表該云任務(wù)的長度(單位為百萬指令集)、需要的內(nèi)存大小(單位：GB)、該云任務(wù)的截止時間(單位：s)、該云任務(wù)的實際需要時間(單位：s)、完成該云任務(wù)的收益(單位：$)及故障所付出的代價(單位：$)。

云任務(wù)i的實際需要時間計算方法如下：

ct.tj=ct.lj/((f/1000)×vm.ci×0.9)

(1)

其中f為虛擬機的CPU頻率。云數(shù)據(jù)中心由于其虛擬機性能的波動，一般都會有10%的冗余。因此，提供給云用戶的截止時間為實際需要時間的1.1倍[15]。云任務(wù)i的截止時間計算方法如下：

ct.dj=1.1ct.tj

(2)

1.2 云任務(wù)的初始化映射

云用戶需要租用云數(shù)據(jù)中心的虛擬機完成自己所提交的云任務(wù)，成熟的云數(shù)據(jù)中心都提供標準規(guī)格的虛擬機讓用戶選擇。例如Amazon的美國東部(俄亥俄)數(shù)據(jù)中心所提供的常規(guī)虛擬機包含4個系列，表1所示的參數(shù)為每個系列的最低型號。例如m5a.large(Low-frequency Universal)為該系列虛擬機的最低配置，它的CPU核數(shù)量和內(nèi)存大小固定為1∶4。而對于計算型云任務(wù)通常需要較大CPU的虛擬機，則可以選擇m5a.large(Low-frequency Computational)低頻計算型虛擬機，它的CPU數(shù)量和內(nèi)存大小固定為1∶2。同時，該云數(shù)據(jù)中心還提供了高頻的虛擬機系列m5a.large(High-frequency Universal)和m5n.large(High-frequency Computational)，這兩種系列虛擬機的配置與低頻的配置相比只是頻率不同。同時，云計算中心還提供了這4種虛擬機對應的同比例擴大后的虛擬機。m5a.large(Low-frequency Universal)擴大一倍后的虛擬機為m5a.xlarge(Low-frequency Universal)，m5a.24xlarge(Low-frequency Universal)為該系列配置最大的虛擬機。它的CPU核數(shù)量、內(nèi)存大小都擴大了24倍，當然其租用價格也會根據(jù)配置同比例上升。

表1 虛擬機價格(Amazon的美國東部(俄亥俄)數(shù)據(jù)中心)Tab.1 Price of virtual machines (Amazon's East (Ohio) data center)

假設(shè)云用戶提交了一個云任務(wù)的集合，云數(shù)據(jù)中心需要對它們進行映射。只分析其中的前3個云任務(wù)，它們的參數(shù)見表2。首先，為了滿足云任務(wù)的內(nèi)存需求且使得費用最低，一般都會選擇滿足內(nèi)存需求的最小規(guī)模虛擬機。假設(shè)初始映射時都選擇低頻通用型虛擬機，云任務(wù)ct1在進行映射時會選擇m5a.large(Low-frequency Universal)型虛擬機，分別根據(jù)式(1)和(2)計算實際需要時間和截止時間，同時針對其它的云任務(wù)也采用相同的方法進行部署。

表2 云任務(wù)映射前的參數(shù)Tab.2 Parameters before cloud task mapping

1.3 云數(shù)據(jù)中心重調(diào)度

當云數(shù)據(jù)中心的虛擬機發(fā)生了故障，其對應的云任務(wù)就會執(zhí)行失敗。調(diào)度系統(tǒng)為了繼續(xù)執(zhí)行失效云任務(wù)則需要重新調(diào)度云任務(wù)并且激活新的虛擬機進行映射，如果激活相同配置的虛擬機則有可能導致云任務(wù)的完成時間超過截止時間，尤其是故障發(fā)生較晚的情況下，這種超時更加明顯，使云服務(wù)提供商不僅面臨較高的賠償同時還會影響其聲譽。因此，調(diào)度系統(tǒng)通常會同比例地擴大虛擬機配置從而確保云任務(wù)能夠按時完成。但是，這樣也會大幅地增加云服務(wù)提供商的運營成本。通過對Amazon和Alibaba Cloud等云服務(wù)提供商所提供的虛擬機進行分析，云用戶通常租用的是低頻通用型虛擬機，也可以通過使用高頻型或計算型虛擬機進行執(zhí)行速率的提升，從表1中可以看出它們的價格依次上升。據(jù)此筆者提出失效云任務(wù)分類定義。

定義1.失效云任務(wù)分類。對于失效云任務(wù)進行重映射時，可以通過改變虛擬機的類型從而使失效云任務(wù)滿足其截止時間。若使用原配置的虛擬機則可滿足截止時間則將該失效云任務(wù)歸為低頻通用型云任務(wù)。若需將故障CPU的頻率升高為3.1 GHz則可滿足截止時間，則將該失效云任務(wù)歸為高頻通用型云任務(wù)。若需將故障CPU核數(shù)量和內(nèi)存大小的比率升高為4∶8則可滿足截止時間，則將該失效云任務(wù)歸為低頻計算型云任務(wù)。若需同時升高兩個方面可滿足截止時間，則將該失效云任務(wù)歸為高頻計算型云任務(wù)。若上面都不能滿足，則將4種配置的虛擬機同比例擴大后選擇成本最小的虛擬機進行歸類和重映射。

依然采用前面的示例進行演示。假設(shè)虛擬機產(chǎn)生故障時間隨機且其它參數(shù)不變，按照失效云任務(wù)動態(tài)分類定義進行分類，這3個失效云任務(wù)的分類結(jié)果見表3。

表3 虛擬機故障后的云任務(wù)分類Tab.3 Classification of cloud tasks after virtual machine failure

經(jīng)過上面的分析，已經(jīng)對失效云任務(wù)進行了分類，之后按照其所需的虛擬機參數(shù)激活相應的虛擬機進行重映射，重調(diào)度之后的虛擬機參數(shù)見表4。

表4 重調(diào)度后的虛擬機參數(shù)Tab.4 Parameters of virtual machine after rescheduling

通過上面的示例可以看出，3個失敗的云任務(wù)在重映射后都滿足了截止時間的要求。同時，失效云任務(wù)根據(jù)分類定義合理地選擇了虛擬機。這樣避免了盲目擴大虛擬機的容量，從而節(jié)約了運營的成本。

2 CAFT算法

CAFT算法通過提高云任務(wù)的故障修復率從而降低云服務(wù)提供商的損失。CAFT算法主要包括以下8個步驟：

Step 1：根據(jù)虛擬機的運行情況，依次選取故障虛擬機上的失效云任務(wù)。

Step 2：根據(jù)失效云任務(wù)的截止時間和故障虛擬機的參數(shù)確定云任務(wù)的類型。若為低頻通用型云任務(wù)則轉(zhuǎn)向Step 3，若為高頻通用型云任務(wù)則轉(zhuǎn)向Step 4，若為低頻計算型云任務(wù)則轉(zhuǎn)向Step 5，若為高頻計算型云任務(wù)則轉(zhuǎn)向Step 6，若上面都不能滿足則轉(zhuǎn)向Step 7。

Step3：在空閑的虛擬機隊列中選擇與原故障虛擬機參數(shù)相同的低頻通用型虛擬機進行映射。之后轉(zhuǎn)向Step 8。

Step4：在空閑的虛擬機隊列中選擇與原故障虛擬機參數(shù)相同的高頻通用型虛擬機進行映射。之后轉(zhuǎn)向Step 8。

Step5：在空閑的虛擬機隊列中選擇與原故障虛擬機參數(shù)相同的低頻計算型虛擬機進行映射。之后轉(zhuǎn)向Step 8。

Step6：在空閑的虛擬機隊列中選擇與原故障虛擬機參數(shù)相同的高頻計算型虛擬機進行映射。之后轉(zhuǎn)向Step 8。

Step7：將4種虛擬機參數(shù)同比例擴大后轉(zhuǎn)向Step 2。

Step8：判斷是否存在未重映射的云任務(wù)，若有則重復Step 2，否則結(jié)束整個調(diào)度算法。

3 測試結(jié)果

為了驗證CAFT算法的效果，利用CloudSim實現(xiàn)了該策略。同時在CloudSim中又嵌入了一個仿真驗證平臺，在該仿真驗證平臺中模擬實現(xiàn)了IRW算法、RI算法和DTRDT算法。IRW算法主要是采用相同性能的虛擬機完成容錯。RI算法相對于IRW算法加入了10%的副本復用。DTRDT算法在重調(diào)度時選擇了容量同比例擴大的虛擬機完成部署。之后，又在該平臺中加入了比較模塊，它能夠?qū)Σ煌成渌惴ㄖg的云數(shù)據(jù)中心故障修復率和云服務(wù)提供商的損失進行比較，同時Gao、Dorterler、Chen等[16-18]中的方法生成相應的云任務(wù)參數(shù)進行仿真。其它虛擬機參數(shù)參考Amazon所提供的真實虛擬機參數(shù)，如表5所示。本節(jié)將從云數(shù)據(jù)中心故障修復率和云服務(wù)提供商的損失進行驗證，結(jié)果取1 000次仿真的平均值。云數(shù)據(jù)中心故障修復率為所有失敗云任務(wù)重調(diào)度后按時完成的比例。云服務(wù)提供商的損失就是為了執(zhí)行失敗的云任務(wù)所多建立的虛擬機的費用加上違約的賠償金。云數(shù)據(jù)中心故障修復率：

Fault_repair=n1/n2

(3)

其中，n1表示被修復的故障數(shù)量，n2表示所有的故障數(shù)量。

云服務(wù)提供商的損失：

(4)

其中，ct.fj表示編號為j的云任務(wù)的損失(單位：$)。

3.1 基于云任務(wù)數(shù)量的測試

驗證算法效果隨云任務(wù)數(shù)量的變化。虛擬機故障率取0.01，虛擬機價格取0.086，其它參數(shù)如表5所示。

表5 仿真參數(shù)Tab.5 Simulation parameters

從圖1中可以看出，CAFT算法的故障修復率接近100%。這主要是因為在進行虛擬機的選擇時按照失效云任務(wù)分類定義從小到大依次尋找可以滿足截止時間的虛擬機，同時，升高頻率和加大CPU的比例都可以加快云任務(wù)的執(zhí)行速度。IRW算法在選擇虛擬機時依舊采用原來的配置，因此大量的失效云任務(wù)超出了截止時間。RI算法增加了副本復制技術(shù)，它在云數(shù)據(jù)中心內(nèi)增加了10%的虛擬機副本，這樣雖然可以提高一些故障修復率但效果并不明顯。DTRDT算法在進行虛擬機選擇時只是單純地擴大虛擬機配置，而沒有利用升高頻率和CPU比例的方法，因此故障修復率稍遜于CAFT策略。4種算法的效果隨云任務(wù)數(shù)量的增大表現(xiàn)較為穩(wěn)定。從圖2可以看出RI算法的云服務(wù)提供商的損失最大，這主要是因為它采用了副本復制技術(shù)增加了額外的冗余。IRW算法和DTRDT算法的云服務(wù)提供商的損失略高于CAFT算法，這主要是因為它們的故障修復率較低，因而造成賠償?shù)慕痤~較大。

圖1 云數(shù)據(jù)中心故障修復率隨云任務(wù)數(shù)量的變化Fig.1 Variation of failure repair rate of cloud data center with the number of cloud tasks

圖2 云服務(wù)提供商的損失隨云任務(wù)數(shù)量的變化Fig.2 Variation of loss of cloud service provider with the number of cloud tasks

3.2 基于虛擬機價格的測試

驗證算法效果隨虛擬機價格的變化。云任務(wù)數(shù)量取10 000，虛擬機故障率取0.01，其他參數(shù)見表5。

圖3和圖4中選取的為Amazon在美國東部(俄亥俄)、亞太地區(qū)(新加坡)、亞太地區(qū)(東京)和歐洲(愛爾蘭)的4個云數(shù)據(jù)中心的真實價格。可以看出無論是哪個數(shù)據(jù)中心，CAFT算法的故障修復率都高于其它3種算法，相應的云服務(wù)提供商的損失也小于其它3種算法，這也說明了本文所提出的算法的通用性。

圖3 云數(shù)據(jù)中心故障修復率隨虛擬機價格的變化Fig.3 Variation of failure repair rate of cloud data center with the price of virtual machines

圖4 云服務(wù)提供商的損失隨虛擬機價格的變化Fig.4 Variation of loss of cloud service provider with the price of virtual machines

4 結(jié) 論

(1)分析了云數(shù)據(jù)中心的整體架構(gòu)和模型。

(2)研究了云任務(wù)的初始化映射和虛擬機故障。

(3)提出了面向云數(shù)據(jù)中心的成本感知容錯算法(CAFT)。

(4)借助CloudSim實現(xiàn)了該算法，利用Amazon云數(shù)據(jù)中心的真實數(shù)據(jù)驗證了所提出的CAFT算法的效果。相比于IRW、RI和DTRDT算法，CAFT算法極大地提高了云數(shù)據(jù)中心故障修復率，降低了云服務(wù)提供商的損失。