大數據流計算環境下的低延時高可靠性的資源調度方法

孫懷英, 虞慧群, 范貴生, 陳麗瓊

(1.華東理工大學計算機科學與工程系,上海 200237; 2.上海市計算機軟件評測重點實驗室,上海 201112;3.上海應用技術學院計算機科學與信息工程系,上海 200235)

大數據流計算環境下的低延時高可靠性的資源調度方法

孫懷英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的隔離調度在響應時間、請求失敗率和算法時間復雜度方面的優勢。

1 相關工作

目前大部分的大數據流式計算[4-8]考慮的是低延時,如文獻[4]用于并行執行循環數據流程序的模型,提供的是高吞吐量的批處理計算、低延時的流式計算;文獻[6]關注的是構造一個流式計算作為很短時間間隔內的一系列無狀態、確定性的批處理計算。

在大數據流式計算的可靠性方面也有相關的研究[2,9-10]。文獻[2]提出了用于進行無復制開銷的并行恢復機制;文獻[9]主要關注的是大數據計算中的能耗使用可靠性的問題;文獻[10]主要是用于處理故障恢復和動態重新配置。這些文獻雖然從不同方面對大數據流式計算的可靠性進行分析,但都未考慮動態變化的資源可靠性對資源調度的影響。

本文將使用資源活動向量特征化單個資源的行為,且由資源活動向量計算出資源熵等級來衡量所得信息的可靠性。熵,用于衡量一個系統的無序程度,是一個表征系統進入無序狀態或混亂狀態的指標,可以用于衡量作業調度過程中資源的可靠性[11]。文獻[12]通過分析熵來解決調度系統的可靠性,然而,它是通過作業而非資源計算熵的,若要給資源性能高度變化且是非線性變化的系統進行建模,其適用性就相對變小。

為了優化響應時間和可靠性對資源調度的影響,本文提出了一個基于時間和可靠性的資源調度算法。使用資源活動向量和資源熵等級并考慮響應時間的約束進行作業調度,目的是為了找到高可靠性、低延時的資源調度方案。

2 問題描述

2.1 數據流圖DSG

在大數據流式計算環境中,流應用可以分割成一系列子任務,其中每個子任務都依賴于其他子任務的執行結果[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)。

2.2 數據流模型的基本結構

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

3 低延時高可靠的資源調度算法

3.1 概述

優化資源管理和調度需要考慮以下兩點:(1)單個資源的特征和活動;(2)從資源中獲得信息的可靠性。本文使用資源活動向量特征化單個資源的行為,且由資源活動向量計算出資源熵等級來衡量所得信息的可靠性。提出了一個低延時、高可靠性的資源調度算法,使用資源活動向量和資源熵等級并考慮響應時間的約束進行作業調度,以改進系統的性能和可靠性,算法流程如圖5所示。

3.2 熵、資源活動向量、資源熵

熵是一個重要的統計量,用于衡量系統從一個狀態轉移到另一個狀態所浪費的能耗或系統的無序程度[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

3.3 基于資源熵的資源組可靠性算法

在大數據流式計算的環境中,假定每個節點組內部的計算節點的處理速度一樣,但是每個計算節點的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。

3.4 資源調度算法TRS-SCHE

低延時、高可靠性的資源調度算法TRS-SCHE如圖7所示。Algorithm 2的輸入參數有任務TasG (表示的是使能的且工作量不為0的變遷)、CtG、節點組中原有的任務OtasG。輸出是資源調度的結果。

假設節點組CtGi中有N個計算節點,所有計算節點的CpuSp為Vi,則節點組CtGi的總速度為

Vni=N×Vi

(6)

任務TasGj在節點組CtGi的響應時間見公式(7):

(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之比最少。統一后的目標函數為

(8)

當式(8)獲得最小值時,可靠性和響應時間的綜合效果達到最優。

4 實驗和討論

4.1 實驗環境

在仿真環境里搭建了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。

4.2 實驗結果和分析

實驗中,實現了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調度的評估參數比較

圖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

5 結束語

本文定義了DSG、數據流過程的基本模型和Storm中grouping的模型,對大數據流應用過程進行建模;提出了基于時間和可靠性的資源調度算法TRS-SCHE,其中包括基于資源熵的資源組可靠性算法,目的是為了實現高可靠性、低延時的資源調度。通過仿真實驗驗證了TRS-SCHE調度算法相比于Storm的隔離調度在響應時間、請求失敗率和算法時間復雜度方面的優勢。

本文使用DSG對流式應用進行建模,并對基于Storm平臺的時間和可靠性調度策略進行研究,在建模過程中對于模型交互的設計可能還尚有欠缺。未來將完善DSG的模型結構以提供方便有效的DSG給每個流式應用,并優化完善TRS-SCHE調度算法以運用到真實的大數據分析應用中。

[1] SUN D,ZHANG G,YANG S,etal.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,etal.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,etal.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,etal.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,etal.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,etal.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,etal.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,etal.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.

LowLatencyandHigh-ReliabilityResourceSchedulingMethodinBigDataStreamingComputingEnvironment

SUNHuai-ying1,2,YUHui-qun1,FANGui-sheng1,CHENLi-qiong3

(1.DepartmentofComputerScienceandEngineering,EastChinaUniversityofScienceandTechnology,Shanghai200237,China; 2.ShanghaiKeyLaboratoryofComputerSoftwareEvaluatingandTesting,Shanghai201112,China; 3.DepartmentofComputerScienceandInformationEngineering,ShanghaiInstituteofTechnology,Shanghai200235,China)

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.

DSG; high-reliability; low-latency; resource entropy; response time

1006-3080(2017)06-0855-08

10.14135/j.cnki.1006-3080.2017.06.016

2016-12-27

國家自然科學基金(61173048，61300041)；高等學校博士學科點專向科研基金(20130074110015)；中央高校基本科研業務費專項基金(WH1314038)

孫懷英(1993-)，女，江西人，博士生，研究方向為大數據、云計算、形式化建模與驗證。

虞慧群，E-mail:yhq@ecust.edu.cn

TP391

A