基于動態(tài)副本管理的云計算任務調(diào)度體系架構(gòu)

張煥青,王海濤,張學平,閆 力

基于動態(tài)副本管理的云計算任務調(diào)度體系架構(gòu)

張煥青1,王海濤2,張學平2,閆 力1

(1.解放軍理工大學通信工程學院,南京 210007; 2.解放軍理工大學信息管理中心,南京 210007)

針對云計算環(huán)境中任務調(diào)度因缺少綜合評估調(diào)度策略手段、數(shù)據(jù)文件訪問頻率不一而導致的云計算系統(tǒng)效率降低的問題,分析任務調(diào)度中云計算系統(tǒng)可用資源和用戶提交應用任務的性能指標,并對調(diào)度各功能模塊明確定義。同時對任務數(shù)據(jù)文件的副本進行動態(tài)管理,提出基于動態(tài)副本管理的云計算任務調(diào)度體系架構(gòu)。該任務調(diào)度體系能避免因關鍵數(shù)據(jù)訪問過頻導致的單點失效和系統(tǒng)負載不均狀況,從而提高云計算系統(tǒng)的穩(wěn)定性和可靠性。

云計算;任務調(diào)度;體系架構(gòu);副本管理

云計算技術(shù)以分布式計算為基礎,結(jié)合虛擬化、互聯(lián)網(wǎng)技術(shù),將網(wǎng)絡中分布的計算資源、存儲資源、服務器和軟件系統(tǒng)等多種資源整合集成統(tǒng)一的資源池,向用戶提供交付簡單、拓展性好、成本低廉、安全可靠的存儲和計算服務,用戶則以“按量付費”的形式獲取所需服務[1]。由于云計算系統(tǒng)規(guī)模龐大,資源池內(nèi)部機群異構(gòu)且隨需求動態(tài)多變,同時云計算終端用戶群體廣泛,需求的服務類型眾多,且任務量巨大,QoS (quality of service)目標約束條件各不相同。因此,如何管理云計算海量服務資源,對用戶提交的任務高效調(diào)度執(zhí)行,同時能盡量縮短任務執(zhí)行時間,降低云系統(tǒng)成本,在保證數(shù)據(jù)中心正常吞吐量的同時均衡系統(tǒng)負載,成為云計算的技術(shù)難點和當前的研究重點[]。

目前云計算任務調(diào)度的研究成果有很多[3-5],但往往基于某種假設,僅關注某一方面的性能或指標,如任務完成時間、任務調(diào)度成本、系統(tǒng)負載水平等,對提出的任務調(diào)度策略和資源管理策略進行評估,具有一定的片面性與主觀性,忽視了對任務調(diào)度策略全局性的綜合評估。為此,綜合考慮云計算環(huán)境中任務調(diào)度涉及的多項指標和性能參數(shù),提出一種基于動態(tài)副本管理的云計算任務調(diào)度體系架構(gòu)。

1 云計算環(huán)境中任務調(diào)度體系架構(gòu)

借鑒網(wǎng)格計算、效用計算和云計算任務調(diào)度體系架構(gòu),對云計算任務調(diào)度模塊進行規(guī)劃、梳理,綜合計算資源使用與任務完成所需達到目標的相關參數(shù),設計一種新的云計算環(huán)境中的任務調(diào)度體系架構(gòu),其結(jié)構(gòu)如圖1所示。

圖1 云計算環(huán)境中任務調(diào)度體系架構(gòu)Fig.1 Task scheduling architecture in cloud computing environment

在云計算中,一項任務從提交到完成,需經(jīng)過多個環(huán)節(jié)。在設計云計算任務調(diào)度體系架構(gòu)時,應考慮用戶、代理、數(shù)據(jù)中心、信息服務器4個組成部分。

1)用戶。云計算服務的使用者,為完成某一項或多項任務使用云計算資源。在向云計算中心提交任務之前,用戶與云計算中心一般都需簽署QoS協(xié)議,記錄用戶對于任務完成的預期等級,包括完成時間、信息安全、費用和獲取結(jié)果方式等。

2)代理。根據(jù)用戶簽署QoS協(xié)議中對任務的要求,選擇合適的計算資源執(zhí)行任務,并可根據(jù)實際需求調(diào)整任務調(diào)度策略。代理是用戶與數(shù)據(jù)中心的紐帶。

3)數(shù)據(jù)中心。數(shù)據(jù)中心是云計算的資源提供者,其擁有海量的計算、存儲資源,可隨時隨地接入使用。

4)信息服務器。信息服務器負責記錄云計算數(shù)據(jù)中心內(nèi)部各類資源信息,包括計算資源的計算能力、存儲資源的容量、通信資源的帶寬以及各類資源使用費用等。有新的資源加入時需向IS注冊;數(shù)據(jù)中心內(nèi)部資源出現(xiàn)變動時需向IS匯報修改;有資源撤出時需向IS注銷。

在云計算任務調(diào)度體系架構(gòu)中,4個組成部分的關系可以描述為:用戶將任務提交至代理,代理根據(jù)任務具體情況和QoS協(xié)議內(nèi)容,將任務拆分;數(shù)據(jù)中心內(nèi)部所有可用資源向信息服務器注冊;在代理收到任務請求并完成任務拆分后,向信息服務器查詢可用資源,按照既定的任務調(diào)度策略,向數(shù)據(jù)中心內(nèi)部資源分配具體任務;任務完成后,信息服務器根據(jù)各資源消費情況進行匯總,用戶付費,完成整個云計算過程。

2 云計算環(huán)境中任務調(diào)度執(zhí)行流程

云計算環(huán)境中,任務調(diào)度的執(zhí)行流程是指云系統(tǒng)終端用戶為完成既定目標,使用云計算系統(tǒng)提供的存儲、計算、平臺或軟件等各類資源,提交任務。在云計算系統(tǒng)收到任務后,進行具體拆分細化,根據(jù)用戶QoS協(xié)議的約束條件和任務調(diào)度策略,選擇合適的云計算數(shù)據(jù)中心資源,執(zhí)行該任務并返回結(jié)果。云計算環(huán)境中的任務調(diào)度執(zhí)行流程如圖2所示。

圖2 云計算環(huán)境中任務調(diào)度執(zhí)行流程Fig.2 Task scheduling executing process in cloud computing environment

圖2中任務接收器、預處理程序和任務分類器在云計算任務調(diào)度體系架構(gòu)中,屬于代理組成部分。任務接收器在收到云終端用戶提交的任務后,負責整理并初步規(guī)劃,轉(zhuǎn)交至預處理程序。預處理程序根據(jù)任務屬性和QoS協(xié)議的約束條件使用統(tǒng)一格式對任務進行描述,封裝完成后轉(zhuǎn)交給任務分類器。經(jīng)過處理,每個任務均與一個任務屬性相對應。在云計算環(huán)境的任務調(diào)度中,根據(jù)用戶簽署QoS協(xié)議的約束條件,不同任務有不同的任務調(diào)度傾向。例如,任務不同的服務請求類型,分為SaaS、IaaS、PaaS等,根據(jù)任務調(diào)度預算和任務估計截止時間,任務又可分為成本敏感型和時間敏感型等。此類任務屬性包含在任務屬性中,與任務一同提交給任務分類器,與云計算任務調(diào)度策略相互配合,共同確定任務調(diào)度的隊列。云計算任務屬性元素及其屬性說明如表1所示。

表1 任務屬性元素及其說明Tab.1 Attribute parameters of task

與終端用戶相類似,云計算系統(tǒng)的數(shù)據(jù)中心內(nèi)部資源同樣需要屬性描述標識。數(shù)據(jù)中心任務處理單元的屬性元素及其屬性說明如表2所示。

表2 任務處理單元屬性元素及其說明Tab.2 Attribute parameters of processing elements

資源管理器在云計算任務調(diào)度體系架構(gòu)中屬于信息服務器組成部分,云計算數(shù)據(jù)中心的任務處理單元屬性形成后向資源管理器匯總,并在資源管理器按照計算能力、通信帶寬和使用成本等進行分類整理。任務調(diào)度器是體系架構(gòu)中代理的核心部分,在收到任務輸入隊列并獲知任務屬性后,從資源管理器獲取當前云計算系統(tǒng)數(shù)據(jù)中心可用資源及其性能指標,按照既定的任務調(diào)度策略,將任務分派至具體的計算資源執(zhí)行,形成用戶任務與計算資源的合理映射,最終完成任務調(diào)度。

在任務調(diào)度的執(zhí)行流程中,單點部署的全局控制節(jié)點包括任務調(diào)度器和資源管理器,每個任務的調(diào)度分配過程必須由這2項參與。在面對大規(guī)模任務調(diào)度或底層計算、存儲資源管理復雜的情況時,任務調(diào)度器和資源管理器任務繁重,易出現(xiàn)“訪問熱點”和“單點失效”的問題。為此,對全局控制節(jié)點的部署引入多點分布式布局。

采用多點分布式部署,每個控制節(jié)點都具有全局控制節(jié)點的相應功能,多個控制節(jié)點構(gòu)成一個全局控制節(jié)點。如圖3所示,在每個控制節(jié)點有多個子節(jié)點,子節(jié)點共同完成控制節(jié)點的任務。采用多點式部署方式,可降低全局控制節(jié)點的瓶頸效應,避免出現(xiàn)訪問熱點和單點失效的問題。

圖3 多點分布式全局控制節(jié)點Fig.3 Multipoint distributed global control node

3 基于副本機制的云計算任務調(diào)度執(zhí)行流程

為解決單點失效問題,提出基于動態(tài)副本管理任務調(diào)度體系架構(gòu),以增強云系統(tǒng)對可用資源管理,改善數(shù)據(jù)文件的可用性和可靠性,提高云計算任務調(diào)度與執(zhí)行的效率。基于動態(tài)副本機制的任務調(diào)度執(zhí)行流程如圖4所示。比較圖4與圖2的流程,基于動態(tài)副本機制的任務調(diào)度執(zhí)行流程不同之處在于,增加了用于收集、記錄、管理各類數(shù)據(jù)文件副本信息的副本管理器。在這個執(zhí)行流程中,全局控制節(jié)點共有副本管理器、任務調(diào)度器和資源管理器,通過多點分布式部署,可避免出現(xiàn)訪問熱點和單點失效的問題。

任務調(diào)度器接收到任務調(diào)度請求后,基于動態(tài)副本機制的任務調(diào)度操作流程為:1)向資源管理器發(fā)出詢問請求,以獲取數(shù)據(jù)中心滿足QoS協(xié)議約束條件的可執(zhí)行任務的所有資源信息;2)向副本管理器發(fā)出詢問請求,以獲取輸入隊列中當前任務的數(shù)據(jù)副本信息所存在的目標位置;3)任務調(diào)度器根據(jù)已獲取的計算資源信息和數(shù)據(jù)副本信息,并基于當前的任務調(diào)度策略,為具體任務與計算資源完成映射,實現(xiàn)云計算任務調(diào)度。

4 云計算環(huán)境中動態(tài)副本管理策略

副本技術(shù)已在分布式系統(tǒng)中廣泛應用,某文件復制多份并將其放置在分布式系統(tǒng)的多個節(jié)點,以增加文件的可靠性,同時副本技術(shù)還可提高數(shù)據(jù)訪問效率和整個系統(tǒng)的負載均衡水平[6]。目前云計算環(huán)境中任務調(diào)度系統(tǒng)大都不重視副本管理策略,因單點失效、訪問瓶頸等問題沒有得到很好解決,在任務調(diào)度體系架構(gòu)中引入動態(tài)副本管理策略,以提升系統(tǒng)數(shù)據(jù)文件可靠性與可用性,提高任務調(diào)度執(zhí)行效率[7]。

副本管理策略一般分為靜態(tài)和動態(tài)2種,在云計算環(huán)境中,由于終端用戶多,用戶訪問形式以及所需服務形式不同,資源池內(nèi)部各類資源重組、遷移等隨應用需求動態(tài)變化,單點故障時常發(fā)生視為常態(tài),對于這樣的分布式環(huán)境,適用于使用動態(tài)副本管理策略[8]。根據(jù)云計算系統(tǒng)環(huán)境、資源狀況以及用戶行為的不斷變化,動態(tài)副本管理策略能夠不斷進行環(huán)境條件的變化,并適時調(diào)整副本放置位置和副本數(shù)量,在性能表現(xiàn)方面更為良好。

4.1 數(shù)據(jù)中心網(wǎng)絡結(jié)構(gòu)

動態(tài)副本管理策略的實現(xiàn)必須要有相應的數(shù)據(jù)中心網(wǎng)絡結(jié)構(gòu)作為支撐,網(wǎng)絡結(jié)構(gòu)包括層次化結(jié)構(gòu)、集中式結(jié)構(gòu)和分布式結(jié)構(gòu)等。為此,引入一種層次化結(jié)構(gòu)構(gòu)建云計算數(shù)據(jù)中心,以實現(xiàn)動態(tài)副本管理策略。云計算數(shù)據(jù)中心網(wǎng)絡結(jié)構(gòu)如圖5所示,包括普通主機節(jié)點、區(qū)域頭節(jié)點和區(qū)域宿主節(jié)點。圖5的虛線表示一個區(qū)域,其由一個區(qū)域頭節(jié)點連接多個主機節(jié)點構(gòu)成。每個主機節(jié)點負責存儲數(shù)據(jù)文件,并對自身存儲的文件保存歷史訪問記錄,包括被訪問文件的編號、訪問時間和訪問節(jié)點等。在系統(tǒng)內(nèi)部進行設置,主機節(jié)點會在固定時間間隔后,向區(qū)域頭節(jié)點匯報主機節(jié)點內(nèi)部存儲數(shù)據(jù)的歷史訪問記錄。而區(qū)域頭節(jié)點則負責管理該區(qū)域內(nèi)部主機節(jié)點信息,通過以上操作區(qū)域頭節(jié)點就可掌握區(qū)域內(nèi)數(shù)據(jù)文件的歷史訪問記錄。在更上一層,區(qū)域宿主節(jié)點有權(quán)對數(shù)據(jù)中心節(jié)點內(nèi)部所有數(shù)據(jù)文件的歷史訪問記錄進行查詢。

圖5 云計算數(shù)據(jù)中心網(wǎng)絡結(jié)構(gòu)Fig.5 Network structure of cloud computing data center

4.2 動態(tài)副本管理策略

動態(tài)副本管理策略核心主要為3項:副本創(chuàng)建、副本放置、副本置換。副本創(chuàng)建負責為訪問次數(shù)較多的數(shù)據(jù)文件創(chuàng)建副本,并確定創(chuàng)建副本的數(shù)量;副本放置負責確定創(chuàng)建的副本文件在存儲單元的具體位置,放置策略將直接影響數(shù)據(jù)文件讀寫效率和系統(tǒng)的負載水平;副本置換負責當存儲單元內(nèi)部空間不足時,選取刪除部分副本,以釋放存儲空間,或置換新副本。

4.2.1 副本創(chuàng)建策略

副本創(chuàng)建策略包括創(chuàng)建副本的文件、創(chuàng)建副本的數(shù)量。在云計算數(shù)據(jù)中心內(nèi)部,宿主節(jié)點可通過區(qū)域頭節(jié)點查詢數(shù)據(jù)中心所有區(qū)域內(nèi)數(shù)據(jù)文件的信息,包括數(shù)據(jù)文件的歷史訪問記錄,因此,就可以根據(jù)數(shù)據(jù)文件訪問的“熱度”,選擇合適的數(shù)據(jù)文件創(chuàng)建副本。由于云計算系統(tǒng)處理的任務海量且隨時間變化較大,不同時間段數(shù)據(jù)文件的訪問“熱度”不同,副本創(chuàng)建策略也應隨之改變。鑒于此,在評估文件的訪問“熱度”時,根據(jù)不同時間段的歷史訪問記錄,賦予不同的權(quán)值,較新的歷史訪問記錄賦值更高,時間間隔較長的歷史訪問記錄對文件“熱度”權(quán)值貢獻呈指數(shù)下降。

在數(shù)據(jù)中心內(nèi)部設定一個固定的時間周期,已經(jīng)評估文件“熱度”所需的周期為T,在T周期內(nèi)被訪問的數(shù)據(jù)文件集合為F,文件f在第t個周期內(nèi)被訪問次數(shù)用Atf表示,文件f“熱度”可表示為:

需要創(chuàng)建副本的流行文件fp為:

用F表示F中文件數(shù)量,F中文件的平均熱度作為副本創(chuàng)建個數(shù)的評估基礎:

則系統(tǒng)需要為fp創(chuàng)建的副本數(shù)量為

4.2.2 副本放置策略

副本放置策略主要考慮2個問題:每個區(qū)域內(nèi)放置副本的數(shù)量,副本放置的各區(qū)域內(nèi)部主機節(jié)點位置。合理、有效的副本放置策略對于整個動態(tài)副本管理至關重要,能夠有效均衡系統(tǒng)負載,并提高數(shù)據(jù)文件讀取可靠性,提升任務執(zhí)行效率。

由于流行文件fp在每個區(qū)域內(nèi)被訪問的頻率不一,也就是說,各區(qū)域內(nèi)fp的訪問“熱度”是不同的。在副本放置策略中,應優(yōu)先考慮將副本放置在流行文件訪問頻率高的區(qū)域,以消除因單點訪問過多而存在的安全隱患,分擔工作負載,提升系統(tǒng)穩(wěn)定性。流行文件fp在各區(qū)域內(nèi)訪問“熱度”計算公式為:

其中:R為數(shù)據(jù)中心的區(qū)域個數(shù);Pr(fp)為fp在區(qū)域r的訪問“熱度”。將Pr(fp),r=1,2,…,R按照降序排列,訪問“熱度”越高的單個區(qū)域內(nèi)獲得副本數(shù)越多:

在確定副本創(chuàng)建數(shù)量及各區(qū)域內(nèi)放置副本數(shù)量后,需確定每個區(qū)域內(nèi)具體放置副本的主機節(jié)點。副本對放置的主機節(jié)點的選取,需綜合考慮節(jié)點存儲空間、通信帶寬、歷史記錄中的有效訪問次數(shù)以及成功率、區(qū)域負載情況等因素。副本放置于剩余存儲空間大的節(jié)點,可提高資源利用率;在訪問“熱點”高的區(qū)域選取訪問次數(shù)少的節(jié)點放置副本,可提高系統(tǒng)穩(wěn)定性,平衡數(shù)據(jù)文件的請求負載;而在訪問有效性好、通信帶寬較高的節(jié)點中放置副本,能保證任務較為順利地調(diào)度執(zhí)行,提高數(shù)據(jù)文件利用的可靠性。但以上情況并不一定會都集中于某一部分節(jié)點,且在實際應用環(huán)境中有可能出現(xiàn)各節(jié)點性能相差較大,因此需綜合考慮選取合適的主機節(jié)點。

流行文件fp占用空間為sfp,區(qū)域內(nèi)可用節(jié)點集合為D={n1,n2,…,nn},節(jié)點ni負載情況為li,可用空間為di,帶寬為bi,歷史有效訪問次數(shù)為Nia,則fp選取ni放置副本的期望度為:

其中:ω1、ω2、ω3、ω4為副本對于選取主機節(jié)點放置的權(quán)重系數(shù)可根據(jù)不同的管理策略適度調(diào)整權(quán)重系數(shù)。放置期望度EiP越高,則ni越適用于放置副本。

4.2.3 副本置換策略

在為數(shù)據(jù)文件新副本進行放置操作時,若當前區(qū)域內(nèi)選取的主機節(jié)點空間不足,則需考慮刪除部分數(shù)據(jù)文件副本,釋放空間以放置新副本,這就是動態(tài)副本管理策略中的副本置換策略。過去對副本置換策略研究大多只側(cè)重副本文件的歷史訪問情況,將近期訪問頻率低的副本置換,并沒有考慮副本文件占用空間對置換策略的影響。為此,選取占用空間大的副本置換,可釋放更多的節(jié)點空間,同時長久未被訪問的副本文件被置換,有利于節(jié)點資源有效利用。

假設在流行文件副本所選取的目標放置節(jié)點中有k個副本文件,R={r1,r2,…,rk},集合R中不包含在數(shù)據(jù)中心內(nèi)只有一份的副本文件,以免置換操作對副本管理產(chǎn)生不利影響。對于副本文件ri,占用空間為si,訪問“熱度”為P(i),最后一次訪問時間為,當前時間為tc,計算副本文件ri被選擇刪除的期望度為:

其中,c1、c2、c3分別表示副本文件占用空間、最后一次被訪問記錄至操作時間隔長度、副本文件訪問“熱度”對副本被置換的期望度的權(quán)重系數(shù),可根據(jù)需求進行調(diào)整。通過計算并比較各副本文件的刪除期望度,可在目標主機節(jié)點中選取刪除期望度高的副本文件進行置換,如果一次操作不能置換足夠的空間,可重復以上步驟,直至主機節(jié)點釋放足夠的可用空間。

5 結(jié)束語

針對云計算環(huán)境中資源池內(nèi)部資源異構(gòu)動態(tài)多變,用戶提交任務量巨大且服務類型多樣的情況,提出云計算環(huán)境匯中任務調(diào)度體系架構(gòu),明確任務調(diào)度功能單元和屬性;并引入動態(tài)副本管理策略,提升系統(tǒng)數(shù)據(jù)文件可靠性與可用性,改善因單點失效和熱點訪問對云系統(tǒng)效率的影響,均衡系統(tǒng)負載。

[1] Muhammad I,Zhu Hong,Tauseef Q,et al.Requirement analysis and design of service level integration layer for cloud computing services,to meet service level agreements and quality of service[J].Journal of Computational and Theoretical Nanoscience,2014,11(3):629-636.

[2] Zhu Yishui,Shtykh R Y,Jin Qun.A human-centric framework for context-aware flowable services in cloud computing environments[J].Information Sciences, 2014,257:231-247.

[3] Exposito R R,Taboada G L,Ramos S,et al.Evaluation of messaging middleware for high-performance cloud computing[J].Personal and Ubiquitous Computing, 2013,17(8):1709-1719.

[4] Xu Baomin,Zhao Chunyan,Hu Enzhao,et al.Job scheduling algorithm based on Berger model in cloud environment[J].Advances in Engineering Software,2011,42 (7):419-425.

[5] Kaewpuang R,Niyato D,Wang Ping,et al.A framework for cooperative resource management in mobile cloud computing[J].IEEE Journal on Selected Areas in Communications,2013,31(12):2685-2700.

[6] Grace R K,Manimegalai R.Dynamic replica placement and selection strategies in data grids:a comprehensive survey[J].Journal of Parallel and Distributed Computing,2014,74(2):2099-2108.

[7] Li Jing.A replica selection decision in cloud computing environment[C]//Proceedings of the International Conference on Advances in Computing Science and Engineering,2010:801-806.

[8] Ryu B G,Choi J H,Lee S K.Impact of node distance on selfish replica allocation in a mobile ad-hoc network[J]. Ad Hoc Networks,2013,11(8):2187-2202.

編輯:翁史振

A task scheduling architecture in cloud computing environment based on dynamic replica management

Zhang Huanqing1,Wang Haitao2,Zhang Xueping2,Yan Li1
(1.College of Communication,PLA University of Science and Technology,Nanjing 210007,China; 2.Information Management Center,PLA University of Science and Technology,Nanjing 210007,China)

Efficiency of cloud computing system is reduced as data file access frequency varies as well as the lack of comprehensive evaluation strategies and methods of task scheduling in cloud computing environment.This paper analyzes the available resources and performance index of tasks submitted by users in cloud computing system while task scheduling and the function modules of task scheduling are clearly defined.At the same time,a cloud computing task scheduling architecture based on dynamic replica management is put forward.The stability and reliability of cloud computing can be improved, which can avoid a single point of failure and uneven load balance.

cloud computing;task scheduling;architecture;replica management

TP393

A

1673-808X(2015)05-0371-06

2015-03-12

國家自然科學基金(61072043)

王海濤(1976-),男,河南焦作人,副教授,博士,研究方向為無線自組網(wǎng)、網(wǎng)絡管理和QoS保障。E-mail:haitmail@126.com

張煥青,王海濤,張學平,等.基于動態(tài)副本管理的云計算任務調(diào)度體系架構(gòu)[J].桂林電子科技大學學報,2015,35(5):371-376.