孫懷英, 虞慧群, 范貴生, 陳麗瓊
(1.華東理工大學(xué)計(jì)算機(jī)科學(xué)與工程系,上海 200237; 2.上海市計(jì)算機(jī)軟件評(píng)測(cè)重點(diǎn)實(shí)驗(yàn)室,上海 201112;3.上海應(yīng)用技術(shù)學(xué)院計(jì)算機(jī)科學(xué)與信息工程系,上海 200235)
大數(shù)據(jù)流計(jì)算環(huán)境下的低延時(shí)高可靠性的資源調(diào)度方法
孫懷英1,2, 虞慧群1, 范貴生1, 陳麗瓊3
(1.華東理工大學(xué)計(jì)算機(jī)科學(xué)與工程系,上海 200237; 2.上海市計(jì)算機(jī)軟件評(píng)測(cè)重點(diǎn)實(shí)驗(yàn)室,上海 201112;3.上海應(yīng)用技術(shù)學(xué)院計(jì)算機(jī)科學(xué)與信息工程系,上海 200235)
在大數(shù)據(jù)處理過程中,如何保證流數(shù)據(jù)處理的可靠性及實(shí)時(shí)性變得日益重要。本文使用數(shù)據(jù)流圖(DSG)對(duì)大數(shù)據(jù)流應(yīng)用過程進(jìn)行描述,并將DSG表示為擴(kuò)展的Petri網(wǎng)以便對(duì)數(shù)據(jù)流過程進(jìn)行建模。提出了基于CPU利用率平均變化率的資源熵算法計(jì)算資源組可靠性,并根據(jù)資源熵算法提出了基于時(shí)間和可靠性的資源調(diào)度算法(TRS-SCHE)以獲得高可靠性、低延時(shí)的資源調(diào)度方案。通過仿真實(shí)驗(yàn),模擬實(shí)現(xiàn)soda交通大數(shù)據(jù)分析應(yīng)用并進(jìn)行資源的調(diào)度,驗(yàn)證了TRS-SCHE相比于Storm隔離調(diào)度算法在響應(yīng)時(shí)間、請(qǐng)求失敗率和算法時(shí)間復(fù)雜度方面的優(yōu)勢(shì)。
DSG; 高可靠性; 低延時(shí); 資源熵; 響應(yīng)時(shí)間
大數(shù)據(jù)是快速改變的、分散的,一般的硬件和軟件設(shè)施無法單獨(dú)在合理的時(shí)間和空間內(nèi)獨(dú)立完成其采集、訪問、分析、應(yīng)用過程的大型數(shù)據(jù)[1-3]。大數(shù)據(jù)具有大量、多類型、快速更新、價(jià)值密度低、真實(shí)性有待挖掘的特點(diǎn),所以大數(shù)據(jù)處理過程極其復(fù)雜、耗時(shí)[2]。
流數(shù)據(jù)是指數(shù)據(jù)以大量、快速、時(shí)變的流形式持續(xù)到達(dá)。流計(jì)算是指實(shí)時(shí)獲取來自不同數(shù)據(jù)源的海量數(shù)據(jù),經(jīng)過實(shí)時(shí)分析處理,獲得有價(jià)值的信息。流式計(jì)算中數(shù)據(jù)的價(jià)值隨時(shí)間的流逝而降低。為了及時(shí)處理流數(shù)據(jù),需要有一個(gè)低延遲、高可靠性的資源調(diào)度方法。
目前的很多研究是對(duì)大數(shù)據(jù)處理的響應(yīng)時(shí)間進(jìn)行優(yōu)化,并且是關(guān)于大數(shù)據(jù)批處理計(jì)算的。批處理計(jì)算的響應(yīng)時(shí)間在數(shù)秒級(jí)甚至是數(shù)分鐘級(jí),這并不能滿足大數(shù)據(jù)流式計(jì)算對(duì)于低響應(yīng)時(shí)間的需求[4-6]。
流式計(jì)算結(jié)合大規(guī)模并行結(jié)構(gòu)提供快速大數(shù)據(jù)處理,成為從大數(shù)據(jù)中獲得有用信息的最快和最有效的方案之一[1,3,7],它同時(shí)也面臨著可靠性方面的挑戰(zhàn)。在提高流式計(jì)算的可靠性方面已有相關(guān)工作,但是大多研究都是基于調(diào)整故障恢復(fù)和容錯(cuò)機(jī)制[8],其中關(guān)于動(dòng)態(tài)變化的資源可靠性對(duì)資源調(diào)度影響方面的研究較少。
為了優(yōu)化響應(yīng)時(shí)間和可靠性對(duì)資源調(diào)度的影響,本文提出了以下基于時(shí)間和可靠性的大數(shù)據(jù)資源調(diào)度方法,以實(shí)現(xiàn)高可靠性和低延時(shí)的資源調(diào)度:
(1) 定義數(shù)據(jù)流圖(Data Stream Graph,DSG)[1]、數(shù)據(jù)流過程的基本模型和Storm中g(shù)rouping的模型,用于對(duì)大數(shù)據(jù)流應(yīng)用過程進(jìn)行建模;
(2) 提出了基于時(shí)間和可靠性的資源調(diào)度算法(TRS-SCHE),其中包括基于資源熵的資源組可靠性算法,用于實(shí)現(xiàn)高可靠性和低延時(shí)的資源調(diào)度;
(3) 通過仿真實(shí)驗(yàn)驗(yàn)證了TRS-SCHE相比于Storm的隔離調(diào)度在響應(yīng)時(shí)間、請(qǐng)求失敗率和算法時(shí)間復(fù)雜度方面的優(yōu)勢(shì)。
目前大部分的大數(shù)據(jù)流式計(jì)算[4-8]考慮的是低延時(shí),如文獻(xiàn)[4]用于并行執(zhí)行循環(huán)數(shù)據(jù)流程序的模型,提供的是高吞吐量的批處理計(jì)算、低延時(shí)的流式計(jì)算;文獻(xiàn)[6]關(guān)注的是構(gòu)造一個(gè)流式計(jì)算作為很短時(shí)間間隔內(nèi)的一系列無狀態(tài)、確定性的批處理計(jì)算。
在大數(shù)據(jù)流式計(jì)算的可靠性方面也有相關(guān)的研究[2,9-10]。文獻(xiàn)[2]提出了用于進(jìn)行無復(fù)制開銷的并行恢復(fù)機(jī)制;文獻(xiàn)[9]主要關(guān)注的是大數(shù)據(jù)計(jì)算中的能耗使用可靠性的問題;文獻(xiàn)[10]主要是用于處理故障恢復(fù)和動(dòng)態(tài)重新配置。這些文獻(xiàn)雖然從不同方面對(duì)大數(shù)據(jù)流式計(jì)算的可靠性進(jìn)行分析,但都未考慮動(dòng)態(tài)變化的資源可靠性對(duì)資源調(diào)度的影響。
本文將使用資源活動(dòng)向量特征化單個(gè)資源的行為,且由資源活動(dòng)向量計(jì)算出資源熵等級(jí)來衡量所得信息的可靠性。熵,用于衡量一個(gè)系統(tǒng)的無序程度,是一個(gè)表征系統(tǒng)進(jìn)入無序狀態(tài)或混亂狀態(tài)的指標(biāo),可以用于衡量作業(yè)調(diào)度過程中資源的可靠性[11]。文獻(xiàn)[12]通過分析熵來解決調(diào)度系統(tǒng)的可靠性,然而,它是通過作業(yè)而非資源計(jì)算熵的,若要給資源性能高度變化且是非線性變化的系統(tǒng)進(jìn)行建模,其適用性就相對(duì)變小。
為了優(yōu)化響應(yīng)時(shí)間和可靠性對(duì)資源調(diào)度的影響,本文提出了一個(gè)基于時(shí)間和可靠性的資源調(diào)度算法。使用資源活動(dòng)向量和資源熵等級(jí)并考慮響應(yīng)時(shí)間的約束進(jìn)行作業(yè)調(diào)度,目的是為了找到高可靠性、低延時(shí)的資源調(diào)度方案。
在大數(shù)據(jù)流式計(jì)算環(huán)境中,流應(yīng)用可以分割成一系列子任務(wù),其中每個(gè)子任務(wù)都依賴于其他子任務(wù)的執(zhí)行結(jié)果[1,3-4,6],因此使用DSG對(duì)流應(yīng)用過程進(jìn)行描述,且定義DSG為擴(kuò)展的Petri網(wǎng)[13-15]以對(duì)數(shù)據(jù)流過程進(jìn)行建模。
定義1DSG可表示為一個(gè)擴(kuò)展的Petri網(wǎng),記為Σ=(P,T,F,M0,r),其中:
(1)P是一個(gè)有限庫所集合;
(2)T是個(gè)有限變遷集合,P∪T≠Φ,P∩T=Φ;
(3)F?(P×T)(T×P)是一個(gè)有向弧集合,F表示庫所和變遷之間的流關(guān)系;
(4)M0:P→N是初始標(biāo)識(shí),表示系統(tǒng)的初始token分布狀態(tài);
(5)r為對(duì)變遷的持續(xù)時(shí)間TM、變遷的任務(wù)Tasn(指令數(shù))、變遷中使用的資源的可靠性Rbd的約束,r(Ti)=[TMi,Tasni,Rbdi],TMi≥0,Tasni≥0,TMi和Tasni默認(rèn)值為0,Rbdi∈[0,1]。
庫所可以表示Spout、Bolt、節(jié)點(diǎn)組、具體的計(jì)算節(jié)點(diǎn)等。庫所中的token可以代表數(shù)據(jù)流、調(diào)度策略、時(shí)間控制變量等。變遷可以表示Spout或Bolt中對(duì)數(shù)據(jù)流的各種操作,如讀數(shù)據(jù)操作、分組操作、更新操作、策略匹配操作、匯總操作等。變遷ti在系統(tǒng)當(dāng)前標(biāo)識(shí)(可用數(shù)據(jù)流token的分布)滿足該變遷觸發(fā)的所有輸入條件時(shí)稱為使能的[13-15]。
定義2設(shè)Σ為一個(gè)DSG,滿足下列條件的二元組ST=(M,I)為Σ的一個(gè)狀態(tài):
(1)M為Σ的一個(gè)標(biāo)識(shí);
(2) ?ti∈ET(M),I(ti)=TMi為系統(tǒng)處于當(dāng)前狀態(tài)的時(shí)刻,ET(M)表示標(biāo)識(shí)M中使能的變遷的集合。
初始狀態(tài)ST0=(M0,I0),終止?fàn)顟B(tài)STend=(Mend,Iend)。如果存在一系列變遷t1,t2,…,tn的觸發(fā)使得ST0轉(zhuǎn)換為STn,則稱狀態(tài)STn是從ST0可達(dá)的。
定義3設(shè)Σ為DSG,ST=(M,I)為Σ的一個(gè)狀態(tài),從狀態(tài)ST觸發(fā)使能的變遷ti,得到一個(gè)新的狀態(tài)ST′=(M′,I′),記為ST[ti>ST′。其中M′,I′分別按如下規(guī)則得到:
(1)M′:p∈P,M′(p)=M(p)-F(p,ti)+F(ti,p)
(2)ST′下系統(tǒng)的時(shí)刻I(tj):I(tj)=I(ti)+TMi。
定義4(合理性)就一個(gè)DSG Σ而言,當(dāng)且僅當(dāng)其滿足如下條件[15]才是合理的:
(1) 對(duì)于一個(gè)狀態(tài)ST,若其從初始狀態(tài)ST0可達(dá),則一定存在一個(gè)發(fā)生序列,使ST到狀態(tài)STend可達(dá),即?ST(ST0→*→ST)=>(ST→*→STend);
(2) 存在且只存在唯一的結(jié)束狀態(tài)STend,即
?ST(ST0→*→ST)=>(ST=STend);
(3)不存在死變遷,即?t∈T,?ST,ST1,使得(ST0→*→ST→*→ST1)。
DSG可以分成數(shù)據(jù)流邏輯圖和數(shù)據(jù)流實(shí)例圖。數(shù)據(jù)流邏輯圖反應(yīng)的是一個(gè)數(shù)據(jù)流的邏輯結(jié)構(gòu),而數(shù)據(jù)流實(shí)例圖是基于邏輯流圖的擴(kuò)展圖,是根據(jù)用戶需求設(shè)置庫所和變遷的數(shù)目,以消除瓶頸或分割數(shù)據(jù)流。
圖1所示的源代碼主要用于實(shí)現(xiàn)TOP_N的計(jì)算功能。根據(jù)圖2和圖3的模型結(jié)構(gòu)即可組合得到圖1所對(duì)應(yīng)的數(shù)據(jù)流邏輯圖和實(shí)例圖。在數(shù)據(jù)流邏輯圖中,描述的是代碼的邏輯功能,其模型如圖4(a)所示。根據(jù)實(shí)際的并發(fā)需求,圖1中語句1的并發(fā)數(shù)設(shè)置為4,則語句1設(shè)置的Spout模型(如圖2(a))在實(shí)例圖中就會(huì)有4個(gè)。圖2(b)所示為數(shù)據(jù)流的選擇模型,在圖4(b)的實(shí)例圖里,數(shù)據(jù)流讀取和分組操作后要選擇接收數(shù)據(jù)流的庫所。圖2(c)所示為數(shù)據(jù)流的合并模型,在4(b)的實(shí)例圖里,對(duì)局部排序后的數(shù)據(jù)進(jìn)行整合得到總體排序。
圖1 Storm源代碼例子Fig.1 A code example of Storm
圖2 數(shù)據(jù)流模型的基本結(jié)構(gòu)類型Fig.2 Basic structures of data streaming model
圖1中的fieldsGrouping對(duì)應(yīng)的模型如圖3(a)所示,圖3(a)的模型同樣可以表示AllGrouping,分組的區(qū)別則可通過模型中的變遷的功能進(jìn)行區(qū)分。而常見的ShuffleGrouping和GlobalGrouping對(duì)應(yīng)的模型分別如圖3(c)和圖3(d)所示。根據(jù)NonGrouping和ShuffleGrouping的相似性,其對(duì)應(yīng)的模型同樣可以用圖3(c)表示。而DirectGrouping的特點(diǎn)是直接指定由某個(gè)Task來執(zhí)行Tuple的處理,也可使用圖3(b)的模型進(jìn)行描述。
根據(jù)以上描述,可得相應(yīng)的數(shù)據(jù)流邏輯圖和實(shí)例圖,結(jié)果如圖4所示。
圖3 數(shù)據(jù)流的grouping模型Fig.3 Grouping models of data streaming
優(yōu)化資源管理和調(diào)度需要考慮以下兩點(diǎn):(1)單個(gè)資源的特征和活動(dòng);(2)從資源中獲得信息的可靠性。本文使用資源活動(dòng)向量特征化單個(gè)資源的行為,且由資源活動(dòng)向量計(jì)算出資源熵等級(jí)來衡量所得信息的可靠性。提出了一個(gè)低延時(shí)、高可靠性的資源調(diào)度算法,使用資源活動(dòng)向量和資源熵等級(jí)并考慮響應(yīng)時(shí)間的約束進(jìn)行作業(yè)調(diào)度,以改進(jìn)系統(tǒng)的性能和可靠性,算法流程如圖5所示。
熵是一個(gè)重要的統(tǒng)計(jì)量,用于衡量系統(tǒng)從一個(gè)狀態(tài)轉(zhuǎn)移到另一個(gè)狀態(tài)所浪費(fèi)的能耗或系統(tǒng)的無序程度[11]。雖然熵的概念最初是一個(gè)熱力學(xué)結(jié)構(gòu),但它已被改編適用于其他領(lǐng)域的研究,包括信息理論、生產(chǎn)計(jì)劃、資源管理、計(jì)算機(jī)建模、仿真等[11]。
圖4 Storm代碼(圖3)的數(shù)據(jù)流邏輯圖和實(shí)例圖Fig.4 Logic diagram andinstance diagram of code in fig.3
本文使用熵來量化Storm調(diào)度策略中資源產(chǎn)生的信息的可靠性即資源熵,并引入了一般情況下的熵度量。對(duì)于給定一個(gè)動(dòng)態(tài)系統(tǒng)X,該系統(tǒng)存在一個(gè)有限個(gè)相互排斥的狀態(tài)變量的集合S,且S=s1,s2,…,sn。這些狀態(tài)對(duì)應(yīng)的概率分別為p1,p2,p3,…,pn,則定義熵
(1)
本文主要關(guān)注的是資源信息中最重要的部分,即CPU利用率。為了獲得計(jì)算節(jié)點(diǎn)動(dòng)態(tài)的性能特征,引入了資源活動(dòng)向量RAV(其中的每個(gè)值為每個(gè)計(jì)算節(jié)點(diǎn)在一段時(shí)間間隔內(nèi)的CPU利用率的變化值)和資源熵RE(單個(gè)計(jì)算節(jié)點(diǎn)的可靠性)。為了獲得RAV的值,則需要在每個(gè)Worker上運(yùn)行一個(gè)資源監(jiān)視器。資源監(jiān)視器捕捉Worker的CPU利用率,并將每秒的CPU利用率的差用于更新RAV。
圖5 低延時(shí)高可靠性的資源調(diào)度算法流程圖Fig.5 Flow chart of resource scheduling algorithm based on time and reliability
在大數(shù)據(jù)流式計(jì)算的環(huán)境中,假定每個(gè)節(jié)點(diǎn)組內(nèi)部的計(jì)算節(jié)點(diǎn)的處理速度一樣,但是每個(gè)計(jì)算節(jié)點(diǎn)的CPU利用率可能不一樣,即各個(gè)計(jì)算節(jié)點(diǎn)的RAV和RE值可能是不一樣的,則對(duì)應(yīng)的節(jié)點(diǎn)組的可靠性也是不一樣的。而且實(shí)際中,節(jié)點(diǎn)組內(nèi)節(jié)點(diǎn)的配置可以是不一樣的,即節(jié)點(diǎn)組內(nèi)節(jié)點(diǎn)的處理速度可以是不等的,所以要計(jì)算出每個(gè)計(jì)算節(jié)點(diǎn)的RAV和RE值及對(duì)應(yīng)的節(jié)點(diǎn)組的可靠性值才能更好地制定調(diào)度決策。
資源組可靠性算法以每個(gè)心跳間隔進(jìn)行更新。Worker節(jié)點(diǎn)發(fā)送心跳間隔并附著該段時(shí)間的CPU利用率值和資源熵值給Master節(jié)點(diǎn),因此可以計(jì)算出資源組的可靠性。
先計(jì)算每個(gè)節(jié)點(diǎn)組i的RAV里的每個(gè)value中大于和小于AvgCpuU的個(gè)數(shù),用Count1和Count0表示。計(jì)算大于和小于AvgCpuU的比例值P1和P0(RAV.size>0,節(jié)點(diǎn)組中至少有一個(gè)計(jì)算節(jié)點(diǎn)):
P1=Count1/RAV.size
(2)
P0=Count0/RAV.size
(3)
每個(gè)節(jié)點(diǎn)組的資源熵RE為
RE=-[P1·log2P1+P0·log2P0]
(4)
每個(gè)節(jié)點(diǎn)組的可靠性RD為
(5)
資源組可靠性算法如圖6所示。
圖6 資源組可靠性算法Fig.6 Algorithm of resource group reliability
Algorithm 1的輸入?yún)?shù)有RAV、CPU利用率的平均變化率AvgCpuU、計(jì)算節(jié)點(diǎn)組CtG(簡(jiǎn)稱為節(jié)點(diǎn)組,每個(gè)節(jié)點(diǎn)組里有若干個(gè)計(jì)算節(jié)點(diǎn))、節(jié)點(diǎn)的處理速度CpuSp、節(jié)點(diǎn)組中的計(jì)算節(jié)點(diǎn)個(gè)數(shù)NumCns。輸出結(jié)果為每個(gè)節(jié)點(diǎn)組的可靠性RD。
低延時(shí)、高可靠性的資源調(diào)度算法TRS-SCHE如圖7所示。Algorithm 2的輸入?yún)?shù)有任務(wù)TasG (表示的是使能的且工作量不為0的變遷)、CtG、節(jié)點(diǎn)組中原有的任務(wù)OtasG。輸出是資源調(diào)度的結(jié)果。
假設(shè)節(jié)點(diǎn)組CtGi中有N個(gè)計(jì)算節(jié)點(diǎn),所有計(jì)算節(jié)點(diǎn)的CpuSp為Vi,則節(jié)點(diǎn)組CtGi的總速度為
Vni=N×Vi
(6)
任務(wù)TasGj在節(jié)點(diǎn)組CtGi的響應(yīng)時(shí)間見公式(7):
(7)
其中:TasGj為可能分配給節(jié)點(diǎn)組CtGi的新任務(wù);OtasGi為節(jié)點(diǎn)組CtGi中存在的任務(wù)。
假設(shè)要計(jì)算第i個(gè)任務(wù)TasGi在第j個(gè)節(jié)點(diǎn)組CtGj上的響應(yīng)時(shí)間TMj,即圖8(a)所示的模型。其中變遷t可以細(xì)化為圖8(b)中大虛線框中的模型。Pstr為相應(yīng)的策略,其中的token為類似
圖8 任務(wù)分配過程分析圖 Fig.8 Analysis diagram of task assignation
對(duì)于可靠性和時(shí)間兩目標(biāo)函數(shù)的優(yōu)化問題,既要獲得最大的可靠性,又要使得響應(yīng)時(shí)間最少。本文使用統(tǒng)一目標(biāo)法中的乘除法求解,即使得時(shí)間TM和可靠性RD之比最少。統(tǒng)一后的目標(biāo)函數(shù)為
(8)
當(dāng)式(8)獲得最小值時(shí),可靠性和響應(yīng)時(shí)間的綜合效果達(dá)到最優(yōu)。
在仿真環(huán)境里搭建了Storm平臺(tái),該平臺(tái)是一個(gè)并行、分布式和容錯(cuò)系統(tǒng)。
在仿真環(huán)境數(shù)據(jù)中心中創(chuàng)建了16個(gè)虛擬機(jī)。每個(gè)虛擬機(jī)的配置是dual 4-core Intel Xeon 3 GHz 32bit 32 GB Memory,1 Gbps network interface。每個(gè)虛擬機(jī)運(yùn)行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。
實(shí)驗(yàn)中,實(shí)現(xiàn)了soda交通大數(shù)據(jù)分析應(yīng)用的應(yīng)用原型,并將TRS-SCHE調(diào)度算法應(yīng)用到soda交通大數(shù)據(jù)分析應(yīng)用中進(jìn)行資源的調(diào)度,并與Storm中的隔離調(diào)度進(jìn)行比較。soda交通大數(shù)據(jù)分析應(yīng)用的DSG圖如圖9所示,主要包括讀取交通路段實(shí)時(shí)車流量數(shù)據(jù)、對(duì)數(shù)據(jù)進(jìn)行按路段分組匯總、對(duì)分組匯總更新好的數(shù)據(jù)進(jìn)行局部排序、將局部排序結(jié)果進(jìn)行匯總排序得到TOP_N的結(jié)果等功能。
圖9 TOP_N路段分析的DSG實(shí)例圖Fig.9 DSG instance diagram of TOP_N lanes analysis
實(shí)驗(yàn)包括3個(gè)評(píng)估參數(shù):響應(yīng)時(shí)間(tR)、請(qǐng)求失敗率(Failure rate)和時(shí)間復(fù)雜度(Time complexity)。表1列出了評(píng)估參數(shù)的比較結(jié)果。
(1) 響應(yīng)時(shí)間(tR)。TRS-SCHE調(diào)度算法中每個(gè)任務(wù)的響應(yīng)時(shí)間是根據(jù)式(7)重寫Storm UI計(jì)算得到。使用Storm隔離調(diào)度算法時(shí),可通過Storm UI計(jì)算。
由表1可看出,在數(shù)據(jù)流速度一定的情況下,TRS-SCHE調(diào)度和Storm隔離調(diào)度的響應(yīng)時(shí)間存在差異,圖10更為直觀地顯示了TRS-SCHE調(diào)度的響應(yīng)時(shí)間比Storm隔離調(diào)度更有優(yōu)勢(shì)。
表1 TRS-SCHE和Storm調(diào)度的評(píng)估參數(shù)比較
圖10 響應(yīng)時(shí)間比較Fig.10 Comparison of response time
(2) 請(qǐng)求失敗率(Failure rate)。因?yàn)槊總€(gè)topology都有一個(gè)消息超時(shí)的設(shè)置,如果Storm在這個(gè)超時(shí)的時(shí)間內(nèi)檢測(cè)不到某個(gè)tuple樹到底有沒有執(zhí)行成功,那么topology會(huì)把這個(gè)tuple標(biāo)記為執(zhí)行失敗,并且過一會(huì)兒會(huì)重新發(fā)射這個(gè)tuple。由圖11可看出,在兩種調(diào)度中,相對(duì)而言,TRS-SCHE調(diào)度比Storm隔離調(diào)度出現(xiàn)處理失敗的請(qǐng)求比例更少,說明TRS-SCHE調(diào)度保證了更高的可靠性。
圖11 請(qǐng)求失敗率比較Fig.11 Comparison of failure rate
這里存在一個(gè)問題,相對(duì)Storm調(diào)度而言,雖然TRS-SCHE調(diào)度降低了一定量的請(qǐng)求失敗率,但它還是存在一定的性能瓶頸,因此會(huì)對(duì)低要求的響應(yīng)時(shí)間產(chǎn)生一定的負(fù)面影響,這也是未來工作中需要解決的一個(gè)問題。
(3) 時(shí)間復(fù)雜度(Time complexity)。由圖12和表1中的數(shù)據(jù)可以看出,隨著時(shí)間的累加,處理數(shù)據(jù)量的增加,TRS-SCHE調(diào)度時(shí)間復(fù)雜度的增加趨勢(shì)一直低于Storm隔離調(diào)度,說明TRS-SCHE調(diào)度的運(yùn)行時(shí)間比Storm隔離調(diào)度更占優(yōu)勢(shì)。
圖12 時(shí)間復(fù)雜度比較Fig.12 Comparison of time complexity
本文定義了DSG、數(shù)據(jù)流過程的基本模型和Storm中g(shù)rouping的模型,對(duì)大數(shù)據(jù)流應(yīng)用過程進(jìn)行建模;提出了基于時(shí)間和可靠性的資源調(diào)度算法TRS-SCHE,其中包括基于資源熵的資源組可靠性算法,目的是為了實(shí)現(xiàn)高可靠性、低延時(shí)的資源調(diào)度。通過仿真實(shí)驗(yàn)驗(yàn)證了TRS-SCHE調(diào)度算法相比于Storm的隔離調(diào)度在響應(yīng)時(shí)間、請(qǐng)求失敗率和算法時(shí)間復(fù)雜度方面的優(yōu)勢(shì)。
本文使用DSG對(duì)流式應(yīng)用進(jìn)行建模,并對(duì)基于Storm平臺(tái)的時(shí)間和可靠性調(diào)度策略進(jìn)行研究,在建模過程中對(duì)于模型交互的設(shè)計(jì)可能還尚有欠缺。未來將完善DSG的模型結(jié)構(gòu)以提供方便有效的DSG給每個(gè)流式應(yīng)用,并優(yōu)化完善TRS-SCHE調(diào)度算法以運(yùn)用到真實(shí)的大數(shù)據(jù)分析應(yīng)用中。
[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
國(guó)家自然科學(xué)基金(61173048,61300041);高等學(xué)校博士學(xué)科點(diǎn)專向科研基金(20130074110015);中央高?;究蒲袠I(yè)務(wù)費(fèi)專項(xiàng)基金(WH1314038)
孫懷英(1993-),女,江西人,博士生,研究方向?yàn)榇髷?shù)據(jù)、云計(jì)算、形式化建模與驗(yàn)證。
虞慧群,E-mail:yhq@ecust.edu.cn
TP391
A