孙怀英1,2, 虞慧群1, 范贵生1, 陈丽琼3

(1.华东理工大学计算机科学与工程系,上海 200237; 2.上海市计算机软件评测重点实验室,上海 201112;3.上海应用技术学院计算机科学与信息工程系,上海 200235)

摘要：在大数据处理过程中,如何保证流数据处理的可靠性及实时性变得日益重要。本文使用数据流图(DSG)对大数据流应用过程进行描述,并将DSG表示为扩展的Petri网以便对数据流过程进行建模。提出了基于CPU利用率平均变化率的资源熵算法计算资源组可靠性,并根据资源熵算法提出了基于时间和可靠性的资源调度算法(TRS-SCHE)以获得高可靠性、低延时的资源调度方案。通过仿真实验,模拟实现soda交通大数据分析应用并进行资源的调度,验证了TRS-SCHE相比于Storm隔离调度算法在响应时间、请求失败率和算法时间复杂度方面的优势。

关键词：DSG; 高可靠性; 低延时; 资源熵; 响应时间

大数据是快速改变的、分散的,一般的硬件和软件设施无法单独在合理的时间和空间内独立完成其采集、访问、分析、应用过程的大型数据[1-3]。大数据具有大量、多类型、快速更新、价值密度低、真实性有待挖掘的特点,所以大数据处理过程极其复杂、耗时[2]。

流数据是指数据以大量、快速、时变的流形式持续到达。流计算是指实时获取来自不同数据源的海量数据,经过实时分析处理,获得有价值的信息。流式计算中数据的价值随时间的流逝而降低。为了及时处理流数据,需要有一个低延迟、高可靠性的资源调度方法。

目前的很多研究是对大数据处理的响应时间进行优化,并且是关于大数据批处理计算的。批处理计算的响应时间在数秒级甚至是数分钟级,这并不能满足大数据流式计算对于低响应时间的需求[4-6]。

流式计算结合大规模并行结构提供快速大数据处理,成为从大数据中获得有用信息的最快和最有效的方案之一[1,3,7],它同时也面临着可靠性方面的挑战。在提高流式计算的可靠性方面已有相关工作,但是大多研究都是基于调整故障恢复和容错机制[8],其中关于动态变化的资源可靠性对资源调度影响方面的研究较少。

为了优化响应时间和可靠性对资源调度的影响,本文提出了以下基于时间和可靠性的大数据资源调度方法,以实现高可靠性和低延时的资源调度:

(1) 定义数据流图(Data Stream Graph,DSG)[1]、数据流过程的基本模型和Storm中grouping的模型,用于对大数据流应用过程进行建模;

(2) 提出了基于时间和可靠性的资源调度算法(TRS-SCHE),其中包括基于资源熵的资源组可靠性算法,用于实现高可靠性和低延时的资源调度;

(3) 通过仿真实验验证了TRS-SCHE相比于Storm的隔离调度在响应时间、请求失败率和算法时间复杂度方面的优势。

目前大部分的大数据流式计算[4-8]考虑的是低延时,如文献[4]用于并行执行循环数据流程序的模型,提供的是高吞吐量的批处理计算、低延时的流式计算;文献[6]关注的是构造一个流式计算作为很短时间间隔内的一系列无状态、确定性的批处理计算。

在大数据流式计算的可靠性方面也有相关的研究[2,9-10]。文献[2]提出了用于进行无复制开销的并行恢复机制;文献[9]主要关注的是大数据计算中的能耗使用可靠性的问题;文献[10]主要是用于处理故障恢复和动态重新配置。这些文献虽然从不同方面对大数据流式计算的可靠性进行分析,但都未考虑动态变化的资源可靠性对资源调度的影响。

本文将使用资源活动向量特征化单个资源的行为,且由资源活动向量计算出资源熵等级来衡量所得信息的可靠性。熵,用于衡量一个系统的无序程度,是一个表征系统进入无序状态或混乱状态的指标,可以用于衡量作业调度过程中资源的可靠性[11]。文献[12]通过分析熵来解决调度系统的可靠性,然而,它是通过作业而非资源计算熵的,若要给资源性能高度变化且是非线性变化的系统进行建模,其适用性就相对变小。

为了优化响应时间和可靠性对资源调度的影响,本文提出了一个基于时间和可靠性的资源调度算法。使用资源活动向量和资源熵等级并考虑响应时间的约束进行作业调度,目的是为了找到高可靠性、低延时的资源调度方案。

在大数据流式计算环境中,流应用可以分割成一系列子任务,其中每个子任务都依赖于其他子任务的执行结果[1,3-4,6],因此使用DSG对流应用过程进行描述,且定义DSG为扩展的Petri网[13-15]以对数据流过程进行建模。

定义1DSG可表示为一个扩展的Petri网,记为Σ=(P,T,F,M0,r),其中:

(1)P是一个有限库所集合;

(2)T是个有限变迁集合,P∪T≠Φ,P∩T=Φ;

(3)F⊆(P×T)(T×P)是一个有向弧集合,F表示库所和变迁之间的流关系;

(4)M0:P→N是初始标识,表示系统的初始token分布状态;

(5)r为对变迁的持续时间TM、变迁的任务Tasn(指令数)、变迁中使用的资源的可靠性Rbd的约束,r(Ti)=[TMi,Tasni,Rbdi],TMi≥0,Tasni≥0,TMi和Tasni默认值为0,Rbdi∈[0,1]。

库所可以表示Spout、Bolt、节点组、具体的计算节点等。库所中的token可以代表数据流、调度策略、时间控制变量等。变迁可以表示Spout或Bolt中对数据流的各种操作,如读数据操作、分组操作、更新操作、策略匹配操作、汇总操作等。变迁ti在系统当前标识(可用数据流token的分布)满足该变迁触发的所有输入条件时称为使能的[13-15]。

定义2设Σ为一个DSG,满足下列条件的二元组ST=(M,I)为Σ的一个状态:

(1)M为Σ的一个标识;

(2) ∀ti∈ET(M),I(ti)=TMi为系统处于当前状态的时刻,ET(M)表示标识M中使能的变迁的集合。

初始状态ST0=(M0,I0),终止状态STend=(Mend,Iend)。如果存在一系列变迁t1,t2,…,tn的触发使得ST0转换为STn,则称状态STn是从ST0可达的。

定义3设Σ为DSG,ST=(M,I)为Σ的一个状态,从状态ST触发使能的变迁ti,得到一个新的状态ST′=(M′,I′),记为ST[ti>ST′。其中M′,I′分别按如下规则得到:

(1)M′:p∈P,M′(p)=M(p)-F(p,ti)+F(ti,p)

(2)ST′下系统的时刻I(tj):I(tj)=I(ti)+TMi。

定义4(合理性)就一个DSG Σ而言,当且仅当其满足如下条件[15]才是合理的:

(1) 对于一个状态ST,若其从初始状态ST0可达,则一定存在一个发生序列,使ST到状态STend可达,即∀ST(ST0→*→ST)=>(ST→*→STend);

(2) 存在且只存在唯一的结束状态STend,即

∀ST(ST0→*→ST)=>(ST=STend);

(3)不存在死变迁,即∀t∈T,∃ST,ST1,使得(ST0→*→ST→*→ST1)。

DSG可以分成数据流逻辑图和数据流实例图。数据流逻辑图反应的是一个数据流的逻辑结构,而数据流实例图是基于逻辑流图的扩展图,是根据用户需求设置库所和变迁的数目,以消除瓶颈或分割数据流。

图1所示的源代码主要用于实现TOP_N的计算功能。根据图2和图3的模型结构即可组合得到图1所对应的数据流逻辑图和实例图。在数据流逻辑图中,描述的是代码的逻辑功能,其模型如图4(a)所示。根据实际的并发需求,图1中语句1的并发数设置为4,则语句1设置的Spout模型(如图2(a))在实例图中就会有4个。图2(b)所示为数据流的选择模型,在图4(b)的实例图里,数据流读取和分组操作后要选择接收数据流的库所。图2(c)所示为数据流的合并模型,在4(b)的实例图里,对局部排序后的数据进行整合得到总体排序。

图1 Storm源代码例子Fig.1 A code example of Storm

图2 数据流模型的基本结构类型Fig.2 Basic structures of data streaming model

图1中的fieldsGrouping对应的模型如图3(a)所示,图3(a)的模型同样可以表示AllGrouping,分组的区别则可通过模型中的变迁的功能进行区分。而常见的ShuffleGrouping和GlobalGrouping对应的模型分别如图3(c)和图3(d)所示。根据NonGrouping和ShuffleGrouping的相似性,其对应的模型同样可以用图3(c)表示。而DirectGrouping的特点是直接指定由某个Task来执行Tuple的处理,也可使用图3(b)的模型进行描述。

根据以上描述,可得相应的数据流逻辑图和实例图,结果如图4所示。

图3 数据流的grouping模型Fig.3 Grouping models of data streaming

优化资源管理和调度需要考虑以下两点:(1)单个资源的特征和活动;(2)从资源中获得信息的可靠性。本文使用资源活动向量特征化单个资源的行为,且由资源活动向量计算出资源熵等级来衡量所得信息的可靠性。提出了一个低延时、高可靠性的资源调度算法,使用资源活动向量和资源熵等级并考虑响应时间的约束进行作业调度,以改进系统的性能和可靠性,算法流程如图5所示。

熵是一个重要的统计量,用于衡量系统从一个状态转移到另一个状态所浪费的能耗或系统的无序程度[11]。虽然熵的概念最初是一个热力学结构,但它已被改编适用于其他领域的研究,包括信息理论、生产计划、资源管理、计算机建模、仿真等[11]。

图4 Storm代码(图3)的数据流逻辑图和实例图Fig.4 Logic diagram andinstance diagram of code in fig.3

本文使用熵来量化Storm调度策略中资源产生的信息的可靠性即资源熵,并引入了一般情况下的熵度量。对于给定一个动态系统X,该系统存在一个有限个相互排斥的状态变量的集合S,且S=s1,s2,…,sn。这些状态对应的概率分别为p1,p2,p3,…,pn,则定义熵

(1)

本文主要关注的是资源信息中最重要的部分,即CPU利用率。为了获得计算节点动态的性能特征,引入了资源活动向量RAV(其中的每个值为每个计算节点在一段时间间隔内的CPU利用率的变化值)和资源熵RE(单个计算节点的可靠性)。为了获得RAV的值,则需要在每个Worker上运行一个资源监视器。资源监视器捕捉Worker的CPU利用率,并将每秒的CPU利用率的差用于更新RAV。

图5 低延时高可靠性的资源调度算法流程图Fig.5 Flow chart of resource scheduling algorithm based on time and reliability

在大数据流式计算的环境中,假定每个节点组内部的计算节点的处理速度一样,但是每个计算节点的CPU利用率可能不一样,即各个计算节点的RAV和RE值可能是不一样的,则对应的节点组的可靠性也是不一样的。而且实际中,节点组内节点的配置可以是不一样的,即节点组内节点的处理速度可以是不等的,所以要计算出每个计算节点的RAV和RE值及对应的节点组的可靠性值才能更好地制定调度决策。

资源组可靠性算法以每个心跳间隔进行更新。Worker节点发送心跳间隔并附着该段时间的CPU利用率值和资源熵值给Master节点,因此可以计算出资源组的可靠性。

先计算每个节点组i的RAV里的每个value中大于和小于AvgCpuU的个数,用Count1和Count0表示。计算大于和小于AvgCpuU的比例值P1和P0(RAV.size>0,节点组中至少有一个计算节点):

P1=Count1/RAV.size

(2)

P0=Count0/RAV.size

(3)

每个节点组的资源熵RE为

RE=-[P1·log2P1+P0·log2P0]

(4)

每个节点组的可靠性RD为

(5)

资源组可靠性算法如图6所示。

图6 资源组可靠性算法Fig.6 Algorithm of resource group reliability

Algorithm 1的输入参数有RAV、CPU利用率的平均变化率AvgCpuU、计算节点组CtG(简称为节点组,每个节点组里有若干个计算节点)、节点的处理速度CpuSp、节点组中的计算节点个数NumCns。输出结果为每个节点组的可靠性RD。

低延时、高可靠性的资源调度算法TRS-SCHE如图7所示。Algorithm 2的输入参数有任务TasG (表示的是使能的且工作量不为0的变迁)、CtG、节点组中原有的任务OtasG。输出是资源调度的结果。

图7 资源调度算法TRS-SCHEFig.7 Algorithm of resource scheduling,TRS-SCHE

假设节点组CtGi中有N个计算节点,所有计算节点的CpuSp为Vi,则节点组CtGi的总速度为

Vni=N×Vi

(6)

任务TasGj在节点组CtGi的响应时间见公式(7):

TMj=

(7)

其中:TasGj为可能分配给节点组CtGi的新任务;OtasGi为节点组CtGi中存在的任务。

假设要计算第i个任务TasGi在第j个节点组CtGj上的响应时间TMj,即图8(a)所示的模型。其中变迁t可以细化为图8(b)中大虚线框中的模型。Pstr为相应的策略,其中的token为类似的元组,当其与Ptas中的token(表示任务TasGi)一起到达变迁t0时,变迁t0就负责对两者进行匹配,然后再选择相应的节点组CtGj。假设Pcns2为相应的节点组CtGj,则将任务TasGi的token传给节点组CtGj,节点组CtGj则通过变迁t2的操作将任务传给其内部的计算节点Pcn2,最后通过变迁t12的操作即可计算任务TasGi所需的响应时间TMj保存至Pres中,如图8(b)小虚线框里的模型。

图8 任务分配过程分析图 Fig.8 Analysis diagram of task assignation

对于可靠性和时间两目标函数的优化问题,既要获得最大的可靠性,又要使得响应时间最少。本文使用统一目标法中的乘除法求解,即使得时间TM和可靠性RD之比最少。统一后的目标函数为

F(TM,RD)=

(8)

当式(8)获得最小值时,可靠性和响应时间的综合效果达到最优。

在仿真环境里搭建了Storm平台,该平台是一个并行、分布式和容错系统。

在仿真环境数据中心中创建了16个虚拟机。每个虚拟机的配置是dual 4-core Intel Xeon 3 GHz 32bit 32 GB Memory,1 Gbps network interface。每个虚拟机运行Linux Ubuntu Server 13.04,其中配置的软件为:java1.7OpenJDK,Zero MQ2.1.7,Zookeeper 3.4.5,JZMQ,Python2.7.2,unzip和Kestrel 2.3.4.Storm 0.8.1。

实验中,实现了soda交通大数据分析应用的应用原型,并将TRS-SCHE调度算法应用到soda交通大数据分析应用中进行资源的调度,并与Storm中的隔离调度进行比较。soda交通大数据分析应用的DSG图如图9所示,主要包括读取交通路段实时车流量数据、对数据进行按路段分组汇总、对分组汇总更新好的数据进行局部排序、将局部排序结果进行汇总排序得到TOP_N的结果等功能。

图9 TOP_N路段分析的DSG实例图Fig.9 DSG instance diagram of TOP_N lanes analysis

实验包括3个评估参数:响应时间(tR)、请求失败率(Failure rate)和时间复杂度(Time complexity)。表1列出了评估参数的比较结果。

(1) 响应时间(tR)。TRS-SCHE调度算法中每个任务的响应时间是根据式(7)重写Storm UI计算得到。使用Storm隔离调度算法时,可通过Storm UI计算。

由表1可看出,在数据流速度一定的情况下,TRS-SCHE调度和Storm隔离调度的响应时间存在差异,图10更为直观地显示了TRS-SCHE调度的响应时间比Storm隔离调度更有优势。

表1 TRS-SCHE和Storm调度的评估参数比较

Table1 Comparison between TRS-SCHE and Storm

Timeincremental/stR/msFailurerate/%Timecomplexity/sTRS⁃SCHEStormTRS⁃SCHEStormTRS⁃SCHEStorm100133．9062148．73301．330．14070．1523200215．3502230．77510．5013．670．23120．2436300307．3739325．24517．6721．110．48130．592400401．3309454．34526．7530．690．72530．8361500499．9011521．901130．3435．230．93411．0401600521．315533．14536．1239．871．13221．2129

图10 响应时间比较Fig.10 Comparison of response time

(2) 请求失败率(Failure rate)。因为每个topology都有一个消息超时的设置,如果Storm在这个超时的时间内检测不到某个tuple树到底有没有执行成功,那么topology会把这个tuple标记为执行失败,并且过一会儿会重新发射这个tuple。由图11可看出,在两种调度中,相对而言,TRS-SCHE调度比Storm隔离调度出现处理失败的请求比例更少,说明TRS-SCHE调度保证了更高的可靠性。

图11 请求失败率比较Fig.11 Comparison of failure rate

这里存在一个问题,相对Storm调度而言,虽然TRS-SCHE调度降低了一定量的请求失败率,但它还是存在一定的性能瓶颈,因此会对低要求的响应时间产生一定的负面影响,这也是未来工作中需要解决的一个问题。

(3) 时间复杂度(Time complexity)。由图12和表1中的数据可以看出,随着时间的累加,处理数据量的增加,TRS-SCHE调度时间复杂度的增加趋势一直低于Storm隔离调度,说明TRS-SCHE调度的运行时间比Storm隔离调度更占优势。

图12 时间复杂度比较Fig.12 Comparison of time complexity

本文定义了DSG、数据流过程的基本模型和Storm中grouping的模型,对大数据流应用过程进行建模;提出了基于时间和可靠性的资源调度算法TRS-SCHE,其中包括基于资源熵的资源组可靠性算法,目的是为了实现高可靠性、低延时的资源调度。通过仿真实验验证了TRS-SCHE调度算法相比于Storm的隔离调度在响应时间、请求失败率和算法时间复杂度方面的优势。

本文使用DSG对流式应用进行建模,并对基于Storm平台的时间和可靠性调度策略进行研究,在建模过程中对于模型交互的设计可能还尚有欠缺。未来将完善DSG的模型结构以提供方便有效的DSG给每个流式应用,并优化完善TRS-SCHE调度算法以运用到真实的大数据分析应用中。

参考文献：

[1] SUN D,ZHANG G,YANG S,et al.Re-Stream:Real-time and energy-efficient resource scheduling in big data stream computing environments[J].Information Sciences,2015,319:92-112.

[2] KANOUN K,VAN d S M.Big-data streaming applications scheduling with online learning and concept drift detection[C]// Design,Automation & Test in Europe Conference & Exhibition.USA:IEEE,2015:1547-1550.

[3] XHAFA F,NARANJO V,CABALLE S.Processing and analytics of big data streams with Yahoo!S4[C]// IEEE International Conference on Advanced Information Networking & Applications.USA:IEEE,2015:263-270.

[4] MURRAY D G,MCSHERRY F,ISAACS R,et al.Naiad:Atimely dataflow system[C]// Twenty-Fourth ACM Symposium on Operating Systems Principles.USA:ACM,2013:439-455.

[5] SHIM S J,LEE D S,LEE W S.CP-tree:An adaptive synopsis structure for compressing frequent itemsets over online data streams[J].Information Sciences,2014,278:559-576.

[6] ZAHARIA M,DAS T,LI H,et al.Discretized streams:Fault-tolerant streaming computation at scale[C]// Twenty-Fourth ACM Symposium on Operating Systems Principles.USA:ACM,2013:423-438.

[7] XU J,CHEN Z,TANG J,et al.T-Storm:Traffic-Aware online scheduling in storm[C]// IEEE International Conference on Distributed Computing Systems.USA:IEEE,2014:535-544.

[8] OUSTERHOUT K,WENDELL P,ZAHARIA M,et al.Sparrow:Distributed,low latency scheduling[C]// Twenty-Fourth ACM Symposium on Operating Systems Principles.USA:ACM,2013:69-84.

[9] XIANG Y,WANG L,FU T.A preliminary study of power system reliability considering cloud service reliability[C]// International Conference on Power System Technology.USA:IEEE,2014:2031-2036.

[10] QIAN Zhengping,HE Yong,SU Chunzhi,et al.TimeStream:Reliable stream computation in the cloud[C]//ACM European Conference on Computer Systems.New York,USA:ACM,2013:1-14.

[11] CHEN H,WANG F Z.Spark on entropy:A reliable & efficient scheduler for low-latency parallel jobs in heterogeneous cloud[C]//IEEE International Workshop on Cloud-based Networks and Applications.USA:IEEE,2015:708-713.

[12] CHRISTODOULOU S,ELLINAS G,ASLANI P.Entropy-based scheduling of resource-constrained construction projects[J].Automation in Construction,2009,18(7):919-928.

[13] XIE Z,HAN L,BALDOCK R.Augmented Petrinet cost model for optimisation of large bioinformatics workflows using cloud[C]// European Modelling Symposium.USA:ACM,2013:201-205.

[14] ZHU Lianzhang,TAN Shouchao,ZHANG Weishan,et al.Validation of pervasive cloud task migration with colored Petri net[J].Tsinghua Science and Technology,2016,21(1):89-101.

[15] RIBAS M,FURTADO C G,BARROSO G,et al.Modeling the use of spot instances for cost reduction in cloud computing adoption using a Petri net framework[C]//IEEE International Symposium on Integrated Network Management.USA:IEEE,2015:312-9.

SUN Huai-ying1,2,YU Hui-qun1,FAN Gui-sheng1,CHEN Li-qiong3

(1.Department of Computer Science and Engineering,East China University of Science and Technology,Shanghai200237,China; 2.Shanghai Key Laboratory of Computer Software Evaluating and Testing,Shanghai201112,China; 3.Department of Computer Science and Information Engineering,Shanghai Institute of Technology,Shanghai200235,China)

Abstract :It is quite important for the application of big data to ensure the high-reliability and low-latency of processing the stream data.In this paper,the data stream graph (DSG) is used to describe and model the application process of big data streaming by taking DSG as an extended Petri net.And then,this paper proposes a computing algorithm of resource group reliability via the resource entropy that is based on the average changing rate of CPU utilization.Furthermore,a resource scheduling algorithm,termed as TRS-SCHE,is introduced to attain the high-reliability and low-latency.Finally,through simulation experiments of soda traffic big data analysis,it is shown that compared with the Storm isolated scheduling,the proposed TRS-SCHE scheduling algorithm has more advantages in response time,failure rate and the time complexity.

Key words:DSG; high-reliability; low-latency; resource entropy; response time

文章编号：1006-3080(2017)06-0855-08

DOI:10.14135/j.cnki.1006-3080.2017.06.016

收稿日期：2016-12-27

基金项目：国家自然科学基金(61173048，61300041)；高等学校博士学科点专向科研基金(20130074110015)；中央高校基本科研业务费专项基金(WH1314038)

作者简介：孙怀英(1993-)，女，江西人，博士生，研究方向为大数据、云计算、形式化建模与验证。

通信联系人：虞慧群，E-mail:[email protected]

中图分类号：TP391

文献标志码：A