基于接納控制和ILP資源調度模型的BDAaaS系統架構

鄭志翔，羅文華

(1.新疆警察學院 在職教育培訓處，烏魯木齊 830013; 2.中國刑警學院 網絡犯罪偵查系，沈陽 110035)

基于接納控制和ILP資源調度模型的BDAaaS系統架構

鄭志翔1，羅文華2

(1.新疆警察學院 在職教育培訓處，烏魯木齊 830013; 2.中國刑警學院 網絡犯罪偵查系，沈陽 110035)

為了使云計算平臺為大數據分析提供有效支持，提出一種大數據分析即服務(BDAaaS)的系統架構；首先，當用戶向系統提交大數據分析應用(BDAA)時，通過接納控制器評估任務的執行時間和成本并作出接納決策；然后，通過服務等級協議(SLA)管理器根據任務的服務質量(QoS)需求制定SLA；最后，利用提出的整數線性規劃(ILP)資源調度模型，以最小化執行成本為目標，在滿足SLA下合理調度資源來執行任務；仿真結果表明，提出的方案能夠有效降低任務執行時間，具有有效性和可行性。

云計算；大數據分析即服務；接納控制；資源調度；整數線性規劃

0 引言

大數據分析需要大量的計算和存儲資源來分析和存儲數據，且需要特定的大數據分析應用資源[1]。隨著云計算的發展，很大數據分析任務通過云計算來實現。但由于分析任務需求的多樣化，使得大數據分析應用(Big Data Analytic Application，BDAA)的資源合理調度變的困難[2]。因此，需要開發一種云計算平臺上的大數據分析即服務(Big Data Analytics as a Service, BDAaaS)[3]系統架構，即以大數據分析作為服務對象構建的系統平臺。實現以易于使用的方式和較低的價格，在滿足BDAA服務等級協議(service level agreement, SLA)[4]下為BDAA用戶提供分析服務。

目前，有學者提出了一些通用的分析框架來處理多用戶BDAA，并分配所需的分析資源。例如，文獻[5]提出了用于大數據分析的SLA與成本感知的云資源調度方案(SLAA)。然而，其沒有對用戶應用進行接納控制，即不管用戶應用有何要求都一并接納，這就導致其會違背SLA，例如任務截止期限等[6]。SLA違規會嚴重影響服務提供商的信用等級和聲譽。

為此，提出了一種用于支持BDAA的BDAaaS架構，在滿足用戶SLA下，合理調度計算資源以最小化服務供應商的執行成本。首先，通過接納控制器來接收有能力完成的BDAA。然后，利用整數線性規劃(Integer Linear Program, ILP)[7]模型構建一個資源調度系統，根據SLA和執行成本來調度BDAA所需的計算資源，以此達到節約成本的目的。

1 提出的BDAaaS平臺架構

提出了BDAaaS平臺的體系結構如圖1所示，為不同領域的用戶提供分析服務。該體系結構主要由接納控制器、SLA管理器和資源調度器組成。

圖1 BDAaaS平臺的體系結構

接納控制器：用來決定是否接受用戶提交的任務。當有用戶BDAA任務提交時，接納控制器首先在BDAA注冊表中進行搜索，檢查該用戶所請求的BDAA是否已經存在。如果存在，則接納控制器獲得BDAA的信息。基于該信息，計算在不同資源配置下的預期執行時間和任務成本。如果存在一種資源配置下，其執行的時間和成本都滿足任務的服務質量(Quality of Service, QoS)要求[8]，則接納控制器做出接收決定，并將該任務提交給SLA管理器。

SLA管理器：根據任務QoS要求，為接收的任務建立SLA。SLA違規不僅會降低用戶滿意度，還會產生額外的懲罰成本[9]，所以需要避免違規。

資源調度器：是BDAaaS平臺的核心組成部分，用來為BDAA做出資源調度決策并協調其他組件。其中，在云計算中，資源通常以虛擬機(Virtual Machine, VM)形成呈現[10]。調度調度器中主要包含：(a)資源配置，即調度器決定使用哪種類型的VM，以及該類型VM的使用量；(b) VM控制，即調度器發送VM控制命令到資源管理器來控制VM，例如創建VM、終止VM和移動VM；(c) BDAA選擇，即調度器選擇被請求的BDAA來執行任務；(d)任務執行序列，即將具有相同BDAA請求的任務添加到正在執行BDAA的VM上的等待隊列中，由于任務具有截止期限的限制，所以執行它們需避免期限違規；(e)任務管理，即調度器監控任務的狀態，任務狀態包含提交、接受、拒絕、等待執行、正在執行、執行成功和失敗。同時執行相應的措施，例如，發送執行失敗的任務到成本管理器來產生懲罰成本。

成本管理器：管理BDAaaS平臺生成的所有成本，同時提供價格策略，以此吸引更多的用戶來擴大市場份額，產生更高的利潤。

BDAA管理器：管理由不同用戶提供的BDAA，并動態更新BDAA信息。

數據源管理器：管理需要處理的數據集。由于大數據具有很高的容量，所以需要對數據進行并行計算，以節省數據傳輸時間和網絡成本。

資源管理器：保持來自不同供應商的所有云資源的目錄，并監控VM的狀態以支持調度器做出調度，如在計費周期結束時終止空閑的VM以節約成本。

2 基于ILP的資源調度

在提出的BDAaaS平臺體系結構中，資源調度是關鍵部分，決定著執行用戶任務的有效性和經濟性。資源調度的目標為：在滿足任務SLA下，合理調度云平臺中的資源來執行BDAA任務，并最小化執行成本。本研究基于ILP模型對資源調度進行公式化并建模，在滿足任務的SLA下，最大限度地減少資源成本和最大化VM使用率。

2.1 ILP模型的構建

資源調度問題可轉化為一個多目標ILP問題[11-12]，其優化目標為最小化資源成本。資源成本由三個單獨的目標(A、B、C)組成，分別描述如下。

目標A：將任務分配到現有VM，并使其以最大能力執行，以此提高資源使用率。目標A如公式(1)所示，其中n表示創建的VM的數量；m為需要調度的任務的數量；Li為任務所請求的資源；xij表示是否將Queryi分配到VMj(如果Queryi分配到VMj，則xij=1；否則xij=0。

(1)

目標B：優秀在成本較低的VM上執行任務，以此來降低或移除成本較高VM上的荷載，致使其停止運行，從而節約資源成本。目標B如公式(2)所示，其中，Cj為VMj的成本(按小時建模)，yj表示VMj是否被終止(如果VMj被終止，則yj=0；否則yj=1)。

(2)

目標C：盡可能快速地執行任務，以此降低VM的運行時間，從而節約成本并降低任務響應時間[13]。目標C如公式(3)所示，其中，si為任務Queryi的起始時間。

(3)

另外，以上3個目標的重要性順序為A>B>C。結合這3個獨立目標，綜合形成了目標D，如公式(4)所示，并服從約束條件(5)～(13)。ILP模型定義如下：

目標：

(4)

服從約束：

*xij)≤CPj,?i∈m,j∈n

(5)

bik+bki≤1,?i,k∈m

(6)

bik+bki-xij-xkj≥-1,?i,k∈m;j∈n

(7)

si-sk+F2*bik≤F2-eij,?i,k∈m;j∈n

(8)

si+F3*xij≤F3+Di-eij,?i∈m,j∈n

(9)

Cij*xij≤Bi,?i∈m,j∈n

(10)

(11)

yj≥xij,?i∈m,j∈n

(12)

yj≥yj+1,?j∈n

(13)

在目標函數(4)中，系數F0和F1用來對目標A和目標B的值進行規范化，使其目標函數的最大值與初始問題一致[14]，如下式所示。

F0=max(B+C)-min(B+C)+1

(17)

F1=max(C)-min(C)+1

(18)

上述ILP模型中的符號定義如表1所示。

2.2 約束定義

VM容量約束：用來確保任務所需的總資源不超過VMj的可用資源，如公式(5)所示。其中，二元變量xij表示是否將Queryi調度給VMj；CPj表示在m個任務的最大截止期限之前，VMj的可用容量。

任務截止期限約束：如公式(6)-(9)所示，其中，二元變量bik表示是否在Queryk之前執行Queryi，如果是，則bik=1；否則bik=0。約束(6)通過設置bik和bki中只存在一個為1，來確保Queryi和Queryk的特定執行順序。當在相同VMj上執行Queryi和Queryk時，約束(7)用來限制這些任務不同時執行，即要么在Queryk之前要么在Queryk之后執行Queryi。建模表示為，若Queryi在Queryk之前執行，則bik=1,bki=0；若Queryi在Queryk之后執行；則bik=0,bki=1。約束(8)用來限制如果bik=1，則Queryi應該在Queryk開始執行之前完成，其中，eij表示VMj上Queryi的執行時間，F2為滿足F2≥max(si+eij-Di)+1的足夠大常數。約束(9)用以確保如果Queryi于si時刻在VMj上開始執行，則它應該在其截止期限Di之前完成，F3為滿足F3≥max(si+eij-Di)+1的足夠大常數。

表1 ILP模型中的符號定義

任務預算約束：用以保證VMj上Queryi的執行成本不超過它的預算Bi，如公式(10)所示。其中，Cij為VMj上執行Queryi的成本。

任務調度次數約束：如公式(11)所示，它表示Queryi只能調度到一個資源上。

VM終止約束：如公式(12)到(13)，二元變量yj表示是否終止VMj。約束(12)用以保證當yj=0時，xij必須為0(即不能將Queryi調度到VMj)；當yj=1時，xij可以為0或1(即可以將Queryi調度到VMj，也可以不調度到VMj)。約束(13)用來提供VM使用的優先順序。將創建的VM根據其成本添加到列表中，因此該約束可以使調度器優先使用成本較低的VM。進而降低高成本VM上的負載，當高成本VM變的空閑時，則終止它。

3 仿真及分析

3.1 資源設置

在CloudSim仿真器[15]中構建實驗平臺，數據中心包含20個物理節點，每個節點配備50個CPU內核、100GB內存、10TB存儲和10GB/s網絡帶寬。基于亞馬遜EC2云[16]中的VM模型，仿真了4類VM，分別為r3.large、r3.xlarge、r3.2xlarge和r3.4xlarge，各類VM配置如表2所示。

表2 VM配置表

3.2 任務設置

仿真中，對不同BDAA任務的資源需求進行建模。每個任務請求包含以下信息：(1)任務提交時間，使用均值為1分鐘的泊松分布來構建任務到達時間間隔。(2)BDAA任務類，在本實驗中考慮了基于4類SQL數據庫查詢系統的BDAA，分別為是基于Impala(BDAA1)、基于Shark(BDAA2)、基于Hive(BDAA3)和基于Tez(BDAA4)。(3)任務量，其基于任務的資源需求而建模。由于各任務的性能不同，所以通過引入變差系數來建模具有10%變化量的任務性能，其服從[0.9,1.1]范圍內的均勻分布。(4)用戶號，實驗中設置了50名提交BDAA的用戶。(5)任務截止期限，考慮了兩類截止期限，嚴格截止期限和寬松截止期限。使用正態分布(3,1.4)來生成嚴格截止期限，其中，3表示任務的平均截止期限為其處理時間的3倍，1.4表示標準差。類似地，使用正態分布(8,3)來生成寬松截止期限。(6)任務預算，包含緊縮預算和寬松預算。同樣用正態分布(3,1.4)生成緊縮預算，使用正態分布(8,3)生成寬松預算。

3.3 結果分析

實驗生成了大約6個小時的任務工作，共包含400個任務。接納控制器對任務進行篩選，接收在截止期限和預算上可以滿足QoS需求的任務。然后，由BDAA管理器利用ILP模型求解調度方案。為了評估接納控制器和調度算法的有效性，進行了以下研究。

3.3.1 接納控制器性能分析

為了評估接納控制算法的有效性，在不同任務啟動時間ST下進行接納實驗，其啟動時間范圍為0到60(單位：分鐘)，即將任務推遲0到60分鐘再執行接納和調度。結果如表3所示，其中STN為提交的任務數量，ATN為接受的任務數量，SEN為成功執行的任務數量。

表3 任務接納和執行數量

表3可以看出，對于實時任務(起始時間為0)，接受率為84.0%，而對于滯后10到60分鐘的任務，由于截止期限的約束，滯后會導致一些任務無法完成，所以接受率降低。滯后時間越長，接受率越低。另外，通過接納控制器后的任務都得到了成功執行。這證明了接納控制器的有效性，能夠確保所接受的任務都具備SLA保證，這有助于提高BDAaaS提供商的聲譽。

3.3.2 執行成本分析

將提出的ILP調度模型與文獻[5]提出的SLAA調度方法在成本節約方面進行比較，其中，為了公平起見，都采用了任務接納控制。所獲得的結果如表4所示。可以看出，在不同任務啟動時間ST下，各種調度方案的資源成本不同，但提出方案的整體成本明顯小于SLAA方案，降低了約13%。

表4 調度方案的資源成本 ($)

另外，在接納控制實驗中，我們發現，當啟動時間ST增加時，所接受的任務量是變小的。然而，這些任務的執行總成本并沒有隨著任務量的減小而明顯減小。這是因為，當ST增加時，滿足截止時間約束邊緣的任務較多。由于這些任務所允許的執行時間較緊迫，所以調度器被迫安排一些高價格的能力較強的資源來執行它，所以總體成本不會明顯降低。

表5給出了2種調度方案所分配的資源類型和數量。正如上述分析，ST越大，調度器所調用的高級資源越多。總體來說，提出ILP模型所調用的普通和高級資源數量都要小于SLAA方案，所以具有較小的執行成本。

表5 資源配置

4 結束語

為了提高云平臺對大數據分析應用的執行效率，提出了一種BDAaaS架構，通過接納控制器篩選出可執行的BDAA任務，并建立相應的SLA。然后，通過ILP資源調度模型在滿足SLA保證下為BDAA分配資源，以此最小化任務執行成本。在不同提交時間的任務申請下進行調度仿真，結果證明了提出方法能夠有效降低執行成本，具有有效性和可行性。

[1] 李曉飛. 基于云計算技術的大數據處理系統的研究[J]. 長春工程學院學報(自然科學版), 2014, 15(1):116-118.

[2] 徐 聰. 大數據應用在云計算平臺的優化部署與調度策略研究[D]. 北京：清華大學, 2015.

[3]ArunJ,HazaruthinMM,KarthikM.Analyticsasaservicedeliverymodelforthecloud[A].IEEEInternationalConferenceonEngineeringandTechnology[C].IEEE, 2015:1-5.

[4]WuL,GargSK,BuyyaR.ServiceLevelAgreement(SLA)BasedSaaSCloudManagementSystem[A].IEEE,InternationalConferenceonParallelandDistributedSystems[C].IEEE, 2015:440-447.

[5]AlrokayanM,VahidDastjerdiA,BuyyaR.SLA-AwareProvisioningandSchedulingofCloudResourcesforBigDataAnalytics[A].IEEEInternationalConferenceonCloudComputinginEmergingMarkets[C].IEEE, 2014:1-8.

[6] 王德文, 劉曉萌. 基于改進粒子群算法的云計算平臺資源調度[J]. 計算機應用研究, 2015, 32(11): 3230-3234.

[7] 劉 曦, 張瀟璐, 張學杰. 異構云系統中基于智能優化算法的多維資源公平分配[J]. 計算機應用, 2016, 36(8):2128-2133.

[8] 周蕓韜. 基于MQAAR的移動自組織網絡路由方案[J]. 湘潭大學自然科學學報, 2016, 38(3): 69-73.

[9] 林清瀅, 陸錫聰, 徐 林. 云計算中面向SLA的作業分層優先級調度策略[J]. 計算機科學, 2014, 41(1): 316-317.

[10]GargSK,ToosiAN,GopalaiyengarSK,etal.SLA-basedvirtualmachinemanagementforheterogeneousworkloadsinaclouddatacenter[J].JournalofNetwork&ComputerApplications, 2014, 45(4):108-120.

[11]ManziniR,AccorsiR,CennerazzoT,etal.Theschedulingofmaintenance.Aresource-constraintsmixedintegerlinearprogrammingmodel[J].Computers&IndustrialEngineering, 2015, 8(7):561-568.

[12] 謝麗霞, 嚴焱心. 云計算環境下的服務調度和資源調度研究[J]. 計算機應用研究, 2015, 35(2):528-531.

[13]ZhuL,LiQ,HeL.StudyonCloudComputingResourceSchedulingStrategyBasedontheAntColonyOptimizationAlgorithm[J].InternationalJournalofComputerScienceIssues, 2012, 9(5) :131-138.

[14] 張希翔, 李陶深. 云計算下適應用戶任務動態變更的調度算法[J]. 華中科技大學學報自然科學版, 2012, 40(1): 165-169.

[15]GenezTAL,BittencourtLF,MadeiraERM.WorkflowschedulingforSaaS/PaaScloudprovidersconsideringtwoSLAlevels[J].NetworkOperations&ManagementSymposiumIEEE, 2012, 104(5): 906-912.

[16]PoolaD,RamamohanaraoK,BuyyaR.EnhancingReliabilityofWorkflowExecutionUsingTaskReplicationandSpotInstances[J].AcmTransactionsonAutonomous&AdaptiveSystems, 2016, 10(4): 1-21.

A BDAaaS System Architecture Based on Admission Control and ILP Resource Scheduling Model

Zheng Zhixiang1, Luo Wenhua2

(1.Division of In-service Education and Training, Xinjiang Police College, Wulumuqi 830013, China;2.Department of Cybercrime Investigation, Criminal Police University of China, Shenyang 110035, China)

In order to make the cloud computing platform provide effective support for large data analysis, a big data analytics as a service (BDAaaS) system architecture is proposed. First, when a user submits a big data analysis application (BDAA) to the system, the admission controller is used to evaluate the execution time and cost of the task and make an admission decision. Then, the SLA is built by the service level agreement (SLA) manager according to the Quality of Service (QoS) requirements of the tasks. Finally, the resource scheduling model based on ILP with the goal of minimize the execution cost is proposed, and used to schedule resources reasonably under satisfying the SLA. Simulation results show that the proposed scheme can effectively reduce the task execution time, which is effective and feasible.

cloud computing; big data analysis as a service; admission control; resource scheduling; integer linear programming

2016-01-04；

2017-07-26。

公安部技術研究計劃項目(2015JSYJC04)；遼寧省社科規劃基金項目(L16BFX011)。

鄭志翔(1970-)，男，河北秦皇島人，講師，碩士，主要從事計算機應用等方向的研究。

羅文華(1977-)，男，遼寧沈陽人，教授，碩士，主要從事計算機應用、電子數據取證方向的研究。

1671-4598(2017)03-0227-04

10.16526/j.cnki.11-4762/tp.2017.03.061

TP393

A