基于接纳控制和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