沈時軍，劉欣然,2，張鴻，朱春鴿,2

（1. 國家計算機網(wǎng)絡應急技術處理協(xié)調中心，北京 100029；2. 北京郵電大學 信息安全中心，北京 100876）

1 引言

云計算通過虛擬化技術動態(tài)整合 IT基礎設施與平臺資源，利用互聯(lián)網(wǎng)絡為企業(yè)與個人用戶提供按需的、廉價的計算、存儲、軟件、平臺等服務。近年來，隨著國外Amazon EC2、Google App Engine、Microsoft Azure及國內阿里云等一系列云計算產(chǎn)品的成功以及OpenStack、CloudStack、Eucalyptus、Open Nebula等許多開源云平臺的推廣，云計算已被認為是繼大型計算機、個人計算機、互聯(lián)網(wǎng)之后的又一次IT產(chǎn)業(yè)革命。

安全問題一直是云計算面臨的最重要挑戰(zhàn)之一，如數(shù)據(jù)泄密、服務可用性、拒絕服務攻擊等[1,2]。雖然云計算因其良好的可擴展性被稱為彈性計算，但當大量服務請求在同一時間到達時仍可能耗盡云計算平臺中的所有資源。此時若有新的請求，特別是重要用戶的請求到達時，將無法得到滿足?？紤]到投資回報，絕大多數(shù)云計算平臺都不會長期維持大量的空閑資源，因此這種服務可用性的威脅無論在商業(yè)云還是私有云中都是常見的[3,4]。

為了應對這種服務可用性威脅，價格調控與資源預留是2種主要的手段。價格調控存在于絕大多數(shù)商業(yè)云中。服務商根據(jù)當前的資源緊張程度動態(tài)調整服務價格，使供需保持相對的平衡，減少資源耗盡的危險。例如在Amazon EC2中，服務商推出了按需支付(on-demand instance)服務、預約支付(reserved instance)服務、競價支付(spot instance)服務3種不同的收費服務模式[5]。資源預留策略存在于各種云平臺中。在一些私有云中，由于服務是免費的，價格調控無法進行，資源預留成為保障重要用戶服務可用性的主要手段[6]。由于用戶需求的不可知性，預留的資源過多可能造成浪費，預留的資源過少又可能無法滿足用戶需求。在文獻[7]中，用戶提前向云計算服務商預訂可能用到的資源，服務商收集這些用戶的需求后，通過資源新增、任務調度等手段，保證特定時間的資源可用性。由于用戶通常很難回答“什么時間、需要多少資源”，這種策略可能有一定的局限性。

文獻[6]指出，“在沒有價格調控的情況下，如何既保證重要用戶的請求得到滿足，又不因資源過度預留而造成浪費，是云計算中的重要挑戰(zhàn)之一”。本文提出了一種云計算中的服務可用性保障機制——基于滑動窗口的資源預留(SWRR,sliding window based resource reservation)算法。它將云平臺用戶提交的任務分為普通任務與重要任務(VIP任務)。SWRR的基本思想是：在云計算平臺中為VIP任務預留一定數(shù)量的優(yōu)秀資源，并將這部分優(yōu)秀資源在整個資源池中所占的比例稱為窗口。窗口的“滑動”包含 2層含義：1）窗口大小動態(tài)變化，即在VIP任務增加時擴大窗口以保證優(yōu)先調度，在VIP任務減少時縮小窗口以減少資源浪費；2）窗口內容動態(tài)刷新，即每隔一段時間會評估窗口中的預留資源，淘汰差的資源，引入新的優(yōu)秀資源。

SWRR已被應用于一個大型的云計算應用平臺iVCE中，如圖1所示。目前，該平臺包含分布于全國各地的300多臺物理機，可支持每天百萬級的任務吞吐量。平臺中用戶每天提交的任務數(shù)隨時間的波動很大且很難預測，在高峰時段大量的用戶請求可能相互搶占資源，平臺的服務可用性變差。為了體現(xiàn)差分服務的特點，iVCE授予某些用戶提交VIP任務的權限，并采用SWRR優(yōu)先調度。實際運行結果表明，SWRR可以保證VIP任務的服務等待時間（一般小于5 s）遠小于普通任務（平均約60 s），保障重要用戶的服務可用性。

圖1 SWRR算法示意

由于在實際環(huán)境中直接調試 SWRR參數(shù)可能影響平臺穩(wěn)定性，本文實現(xiàn)了一個SWRR仿真器，并通過多方面的分析比較，論證 SWRR在資源預留、保障重要用戶服務可用性方面的優(yōu)勢。

2 基于滑動窗口的資源預留算法

2.1 資源的定義

云計算平臺中可用的資源集合記為Φ={ri| i=1,2,…,n}，該集合動態(tài)變化。對每一個資源ri，定義資源評價函數(shù)V(ri)為ri在過去一段時間內的任務執(zhí)行成功率，V(ri)越大表示ri越優(yōu)秀。

SWRR算法將Φ劃分為普通資源池Φbase與預留資源池Φresv，分別存放普通資源與預留資源。初始時，Φbase=Φ，Φresv為空。

2.2 任務的定義

云計算平臺中需調度的任務集合記為Ψ={tj| j=1,2,…,m}，該集合動態(tài)變化。對每一個任務tj，令I(tj)表示任務tj的重要程度，若I(tj)=true，表示tj為VIP任務；否則，為普通任務。

任務分為z個優(yōu)先級，記為Z={1,2,…,z}。對每一個任務 tj，令 P(tj)表示任務 tj的優(yōu)先級，則優(yōu)先級為k的任務集合記為Ψk={tj|P(tj)=k,k∈Z}。任務集合 Ψk中的任務按先入先出（FIFO）算法組成隊列，任務從隊首開始調度。

2.3 SWRR算法

根據(jù)任務優(yōu)先級的不同，用戶提交的任務被保存在相應的任務隊列Ψk中，并按照FIFO的順序進行調度。SWRR算法包括任務調度與窗口滑動2個階段，如算法1所示。

在算法的任務調度階段，采用“輪盤賭”選擇需要調度的任務隊列Ψk，并且優(yōu)先級k越大的隊列被選中的概率越大。如果任務tj為VIP任務，優(yōu)先在預留資源池 Φresv中查找資源，在Φresv查找失敗后繼續(xù)在Φbase中查找；如果任務tj為普通任務，則僅在Φbase中查找資源。標志位 fbase、fresv反映當前的資源池狀態(tài)。當Φbase資源不足時，fbase=false；當Φresv資源不足時，fresv=false。

在算法的窗口滑動階段，根據(jù)標志位fbase、fresv調整滑動窗口大小ω。如果預留資源池Φresv資源不足，則擴大滑動窗口；如果預留資源池Φresv資源充足并且普通資源池Φbase資源不足，則縮小滑動窗口；否則窗口大小不變。系統(tǒng)預設滑動窗口的最大值 ωmax、最小值 ωmin，ω∈[ωmin,ωmax]。在每一個調度周期結束后，根據(jù)V(ri)重新評估所有資源，并將 Φresv中最差的部分資源與 Φbase中最優(yōu)秀的部分資源互換，以保證Φresv始終維持最優(yōu)秀的資源。

算法1 SWRR算法

給定資源集合Φ，任務集合Ψ，滑動窗口大小ω。給定常數(shù)：滑動窗口的最大值ωmax、最小值ωmin，窗口調整步長ω'∈(0,1)，資源交換率λ∈(0,1)。初始時，令 ω=ωmin。

在每一個任務調度周期，進行如下步驟。

1)初始化標志位fbase=true，fresv=true。

2)采用“輪盤賭”算法選取一個需要調度的任務隊列 Ψk（k∈Z）。

3)從Ψk中取出第一個需要調度的任務tj。

① 若tj為VIP任務，即I(tj)=true，則從Φresv中選取若干符合 tj條件的資源組成備選資源池Φ(tj)。

若Φ(tj)非空，從Φ(tj)中隨機選取資源ri，將tj下發(fā)到資源ri上執(zhí)行，然后轉步驟4)。

若Φ(tj)為空，設置fresv=false，并將tj當成普通任務繼續(xù)步驟3)中的②。

② 從Φbase中選取若干符合tj條件的資源組成備選資源池Φ(tj)。

若Φ(tj)非空，從Φ(tj)中隨機選取資源ri，將tj下發(fā)到資源ri上執(zhí)行，然后轉步驟4)。

若Φ(tj)為空，設置fbase=false，增加tj的調度失敗次數(shù)，將tj放回Ψk，然后轉步驟4)。

4)循環(huán)進行步驟2)、步驟3)，直到本次調度時間結束，或者所有任務隊列都沒有需調度的任務。

5)確定新的滑動窗口大小ω。

① 若 fresv=false，則設置 ω=min(ωmax,ω+ω')。

② 若fresv=true并且fbase=false，則設置ω=max(ωmin,ω-ω')。

③ 否則ω不變。

6)令 a=|Φbase|表示普通資源數(shù)，b=|Φresv|表示預留資源數(shù)。從Φresv中選擇V(ri)評價最差的λb個資源，從 Φbase中選擇 V(ri)評價最優(yōu)的 max{(a+b)ω?(b?λb),0}個資源，對以上兩部分資源互換。

在算法1中，如果找不到合適的資源，任務tj調度失敗后將重新被放回隊列Ψk中。為了避免同一個任務不斷地被選中調度，當任務tj調度失敗后，它將等待一定時間才能被再次調度，并且等待時間隨著調度失敗次數(shù)的增長而指數(shù)遞增。

SWRR算法具有如下特點。

1)自適應地資源預留。通過滑動窗口大小調整與資源交換，始終維持合適的預留資源，保證VIP任務的調度。

2)兼顧所有任務調度。通過限制滑動窗口大小ω∈[ωmin,ωmax]，保證普通任務的調度；通過“輪盤賭”算法，低優(yōu)先級的任務也有被調度的概率。

3)對 VIP任務突發(fā)性激增的適應性。算法中滑動窗口調整到合適的位置需要一定的時間，為保證服務質量，若VIP任務暫時在Φresv中找不到資源時，將繼續(xù)在Φbase中尋找。

3 仿真實驗

本文實現(xiàn)了一個SWRR仿真器，并通過多方面的分析比較，論證SWRR在資源預留、保障重要用戶服務可用性方面的優(yōu)勢。實驗中，SWRR參數(shù)采用與云計算平臺iVCE中相同的設置，即滑動窗口最小值ωmin=0.2、最大值ωmax=0.6，窗口調整步長ω'=0.02，資源交換率λ=0.2。在本節(jié)最后，會進一步討論這些值的選擇依據(jù)。

仿真中最大資源數(shù)|Φ|=1000，每個資源的性能在資源初始化時隨機生成，該指標將影響任務的執(zhí)行時間與執(zhí)行成功率。實驗通過一個任務生成器，每秒生成一定數(shù)目的 VIP任務與普通任務，以模擬用戶提交任務的行為。每個任務在生成時會附帶一個截止時間的屬性，如果任務在截止時間到達時仍沒有執(zhí)行完成，將標識為失敗，并以此統(tǒng)計任務執(zhí)行成功率。任務在截止之前，如果沒有找到合適的資源，它將處于等待狀態(tài)，并以此統(tǒng)計任務等待時間。

仿真器運行于Linux平臺。實驗在運行穩(wěn)定后，截取其中的60 min，并分析其結果。

3.1 SWRR算法性能

圖2（a）給出了實驗中每分鐘的任務提交情況。參考云計算平臺iVCE的任務提交行為，實驗分別模擬了普通任務突發(fā)性激增（第10～11 min）、VIP任務突發(fā)性激增（第20～21 min）、普通任務與VIP任務持續(xù)高負載（第30～45 min）的情況。

實驗可以分為5個階段。

第0～10 min為第1階段。此時系統(tǒng)資源足夠，可處理所有的普通任務與VIP任務，系統(tǒng)處于平穩(wěn)運行狀態(tài)，滑動窗口ω約為0.24，如圖2(b)所示。

圖2 VIP任務與普通任務的運行比較

第10～20 min為第2階段。在第11 min，普通任務出現(xiàn)激增，如圖 2(a)所示，普通資源池 Φbase出現(xiàn)資源不足，滑動窗口ω降為最小值0.2，如圖2(b)所示，以盡可能減少預留資源占用。但Φbase仍不能滿足需要，大量普通任務的等待時間增加，如圖 2(c)所示，執(zhí)行成功率下降，如圖 2(e)所示。在這個階段，VIP任務的執(zhí)行未受影響。在接近20 min時，系統(tǒng)再次趨于平穩(wěn)狀態(tài)。

第20～30 min為第3階段。在第21 min，VIP任務出現(xiàn)激增，如圖2(a)所示，預留資源池Φresv出現(xiàn)資源不足，滑動窗口 ω迅速升為最大值 0.6，如圖2(b)所示。大量的VIP任務導致了任務等待時間的少量增加，如圖2(c)所示，但VIP任務的執(zhí)行成功率基本沒有變化。在這個階段，雖然普通任務在數(shù)量上沒有變化，但滑動窗口調整導致普通資源池 Φbase變小，因此仍然對普通任務的等待時間、執(zhí)行成功率造成影響，分別如圖2(c)、圖2(e)所示。

第30～45 min為第4階段。在這個階段，普通任務與VIP任務先后出現(xiàn)了增長，并持續(xù)了較長時間，如圖2(a)所示，導致系統(tǒng)中的資源嚴重不足。為了優(yōu)先滿足VIP任務的調度，滑動窗口最終穩(wěn)定在0.4左右，如圖 2(b)所示。在這個過程中，VIP任務的執(zhí)行基本沒有受到影響，但普通任務的等待時間、執(zhí)行成功率均受到了嚴重影響，分別如圖2(c)、圖2(e)所示。

第45～60 min為第5階段。隨著提交的任務數(shù)量回到正常水平，系統(tǒng)又回到平穩(wěn)狀態(tài)。

在圖2展示的整個實驗過程中，用戶提交的任務數(shù)隨時間波動很大，SWRR算法與資源池大小固定的算法相比的優(yōu)勢在于，它通過動態(tài)窗口滑動，合理資源預留，始終保證VIP任務一個較穩(wěn)定的任務等待時間與執(zhí)行成功率。

從圖2(d)進一步看出，VIP任務的執(zhí)行時間明顯小于普通任務。這是因為SWRR算法通過資源交換，在預留資源池中維持了最優(yōu)秀的資源。作為證明，圖3給出了第5 min、第21 min時的滑動窗口快照。資源評分通過函數(shù)資源評價函數(shù)V(ri)得到，它反映了資源在過去一段時間內的任務執(zhí)行成功率。從圖3可以看出，SWRR算法總是將系統(tǒng)中評分最高的那些資源作為預留資源。

3.2 資源負載率

通過預留足夠多的資源，一些靜態(tài)的資源預留算法也能保證VIP任務的調度。文獻[6]指出一個優(yōu)秀的資源預留算法不僅要保證 VIP任務的及時調度，而且要減少資源浪費。圖4給出了在上述實驗過程中，普通資源池與VIP資源池的資源負載情況。

圖3 滑動窗口快照

圖4 資源負載率

對比圖2(e)和圖4可以看出，在資源不足而導致任務執(zhí)行成功率下降的第12～15 min、第22～25 min、第35～45 min，僅在第12～15 min預留資源池的負載率未接近 100%，即存在一定的資源空閑。造成此現(xiàn)象的原因是在第12 min時，滑動窗口已達到最小值，如圖2（b）所示，無法進一步縮小以將資源用于普通任務的調度，因此這不是SWRR算法本身的缺陷。

在實際部署時，滑動窗口最小值、最大值的設置都需要考慮具體的應用場景。窗口最小值設置過大可能造成資源浪費，設置過小可能瞬間不能適應VIP任務的激增；窗口最大值設置過小可能不能為VIP任務預留足夠的資源，設置過大可能瞬間不能適應普通任務的激增。由于 SWRR算法可以自適應調整窗口大?。ǖ枰欢ǖ臅r間），在應用場景不能確定時，可以設置一個較小的最小值、較大的最大值。另外，窗口調整步長、資源交換率實際反映了算法的響應速度與調整粒度，一般來說，對于任務波動較大的場景，可以選擇較大的窗口調整步長、資源交換率。

4 結束語

本文提出了一種云計算中的服務可用性保障機制——基于滑動窗口的資源預留算法。通過動態(tài)窗口滑動、合理資源預留，SWRR算法在兼顧所有任務調度的基礎上，重點提升VIP任務的調度效率與執(zhí)行成功率，保障重要用戶的服務可用性。

SWRR算法已被應用于一個大型的云計算平臺iVCE中。接下來的工作主要包括算法執(zhí)行效率的優(yōu)化，并對算法在實際系統(tǒng)中的性能進行更深入分析。

[1]SUBASHINI S,KAVITHA V. A survey on security issues in service delivery models of cloud computing[J]. Journal of Network and Computer Applications,2011,34(1): 1-11.

[2]CARLIN S,CURRAN K. Cloud computing security[J]. International Journal of Ambient Computing and Intelligence (IJACI),2011,3(1):14-19.

[3]PAWAR C S,WAGH R B. A review of resource allocation policies in cloud computing[J]. World Journal of Science and Technology,2012,2(3):165-167.

[4]ENDO P T,DE ALMEIDA PALHARES A V,PEREIRA N N,et al.Resource allocation for distributed cloud: concepts and research challenges[J]. Network,IEEE,2011,25(4): 42-46.

[5]Amazon elastic compute cloud(EC2)[EB/OL]. http://aws.amazon.com/ec2/.

[6]SEMPOLINSKI P,THAIN D. A comparison and critique of eucalyptus,opennebula and nimbus[A]. IEEE 2nd Int Conf on Cloud Computing Technology and Science[C]. Indianapolis,2010.417-426.

[7]FUNKE D,BROSIG F,FABER M. Towards truthful resource reservation in cloud computing[A]. IEEE Int Conf on Performance Evaluation Methodologies and Tools[C]. Cargese,2012.253-262.