鄭志翔，羅文華

(1.新疆警察學(xué)院 在職教育培訓(xùn)處，烏魯木齊 830013; 2.中國刑警學(xué)院 網(wǎng)絡(luò)犯罪偵查系，沈陽 110035)

基于接納控制和ILP資源調(diào)度模型的BDAaaS系統(tǒng)架構(gòu)

鄭志翔1，羅文華2

(1.新疆警察學(xué)院 在職教育培訓(xùn)處，烏魯木齊 830013; 2.中國刑警學(xué)院 網(wǎng)絡(luò)犯罪偵查系，沈陽 110035)

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

云計(jì)算；大數(shù)據(jù)分析即服務(wù)；接納控制；資源調(diào)度；整數(shù)線性規(guī)劃

0 引言

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

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

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

1 提出的BDAaaS平臺架構(gòu)

提出了BDAaaS平臺的體系結(jié)構(gòu)如圖1所示，為不同領(lǐng)域的用戶提供分析服務(wù)。該體系結(jié)構(gòu)主要由接納控制器、SLA管理器和資源調(diào)度器組成。

圖1 BDAaaS平臺的體系結(jié)構(gòu)

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

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

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

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

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

數(shù)據(jù)源管理器：管理需要處理的數(shù)據(jù)集。由于大數(shù)據(jù)具有很高的容量，所以需要對數(shù)據(jù)進(jìn)行并行計(jì)算，以節(jié)省數(shù)據(jù)傳輸時間和網(wǎng)絡(luò)成本。

資源管理器：保持來自不同供應(yīng)商的所有云資源的目錄，并監(jiān)控VM的狀態(tài)以支持調(diào)度器做出調(diào)度，如在計(jì)費(fèi)周期結(jié)束時終止空閑的VM以節(jié)約成本。

2 基于ILP的資源調(diào)度

在提出的BDAaaS平臺體系結(jié)構(gòu)中，資源調(diào)度是關(guān)鍵部分，決定著執(zhí)行用戶任務(wù)的有效性和經(jīng)濟(jì)性。資源調(diào)度的目標(biāo)為：在滿足任務(wù)SLA下，合理調(diào)度云平臺中的資源來執(zhí)行BDAA任務(wù)，并最小化執(zhí)行成本。本研究基于ILP模型對資源調(diào)度進(jìn)行公式化并建模，在滿足任務(wù)的SLA下，最大限度地減少資源成本和最大化VM使用率。

2.1 ILP模型的構(gòu)建

資源調(diào)度問題可轉(zhuǎn)化為一個多目標(biāo)ILP問題[11-12]，其優(yōu)化目標(biāo)為最小化資源成本。資源成本由三個單獨(dú)的目標(biāo)(A、B、C)組成，分別描述如下。

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

(1)

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

(2)

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

(3)

另外，以上3個目標(biāo)的重要性順序?yàn)锳>B>C。結(jié)合這3個獨(dú)立目標(biāo)，綜合形成了目標(biāo)D，如公式(4)所示，并服從約束條件(5)～(13)。ILP模型定義如下：

目標(biāo)：

(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)

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

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

(17)

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

(18)

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

2.2 約束定義

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

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

表1 ILP模型中的符號定義

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

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

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

3 仿真及分析

3.1 資源設(shè)置

在CloudSim仿真器[15]中構(gòu)建實(shí)驗(yàn)平臺，數(shù)據(jù)中心包含20個物理節(jié)點(diǎn)，每個節(jié)點(diǎn)配備50個CPU內(nèi)核、100GB內(nèi)存、10TB存儲和10GB/s網(wǎng)絡(luò)帶寬。基于亞馬遜EC2云[16]中的VM模型，仿真了4類VM，分別為r3.large、r3.xlarge、r3.2xlarge和r3.4xlarge，各類VM配置如表2所示。

表2 VM配置表

3.2 任務(wù)設(shè)置

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

3.3 結(jié)果分析

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

3.3.1 接納控制器性能分析

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

表3 任務(wù)接納和執(zhí)行數(shù)量

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

3.3.2 執(zhí)行成本分析

將提出的ILP調(diào)度模型與文獻(xiàn)[5]提出的SLAA調(diào)度方法在成本節(jié)約方面進(jìn)行比較，其中，為了公平起見，都采用了任務(wù)接納控制。所獲得的結(jié)果如表4所示?？梢钥闯觯诓煌蝿?wù)啟動時間ST下，各種調(diào)度方案的資源成本不同，但提出方案的整體成本明顯小于SLAA方案，降低了約13%。

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

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

表5給出了2種調(diào)度方案所分配的資源類型和數(shù)量。正如上述分析，ST越大，調(diào)度器所調(diào)用的高級資源越多?？傮w來說，提出ILP模型所調(diào)用的普通和高級資源數(shù)量都要小于SLAA方案，所以具有較小的執(zhí)行成本。

表5 資源配置

4 結(jié)束語

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

[1] 李曉飛. 基于云計(jì)算技術(shù)的大數(shù)據(jù)處理系統(tǒng)的研究[J]. 長春工程學(xué)院學(xué)報(bào)(自然科學(xué)版), 2014, 15(1):116-118.

[2] 徐 聰. 大數(shù)據(jù)應(yīng)用在云計(jì)算平臺的優(yōu)化部署與調(diào)度策略研究[D]. 北京：清華大學(xué), 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ìn)粒子群算法的云計(jì)算平臺資源調(diào)度[J]. 計(jì)算機(jī)應(yīng)用研究, 2015, 32(11): 3230-3234.

[7] 劉 曦, 張瀟璐, 張學(xué)杰. 異構(gòu)云系統(tǒng)中基于智能優(yōu)化算法的多維資源公平分配[J]. 計(jì)算機(jī)應(yīng)用, 2016, 36(8):2128-2133.

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

[9] 林清瀅, 陸錫聰, 徐 林. 云計(jì)算中面向SLA的作業(yè)分層優(yōu)先級調(diào)度策略[J]. 計(jì)算機(jī)科學(xué), 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] 謝麗霞, 嚴(yán)焱心. 云計(jì)算環(huán)境下的服務(wù)調(diào)度和資源調(diào)度研究[J]. 計(jì)算機(jī)應(yīng)用研究, 2015, 35(2):528-531.

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

[14] 張希翔, 李陶深. 云計(jì)算下適應(yīng)用戶任務(wù)動態(tài)變更的調(diào)度算法[J]. 華中科技大學(xué)學(xué)報(bào)自然科學(xué)版, 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。

公安部技術(shù)研究計(jì)劃項(xiàng)目(2015JSYJC04)；遼寧省社科規(guī)劃基金項(xiàng)目(L16BFX011)。

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

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

1671-4598(2017)03-0227-04

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

TP393

A