【摘要】：由于智能硬件智能軟件的發(fā)展,當(dāng)今世界數(shù)據(jù)呈現(xiàn)出爆炸式增長。MapReduce,一種分布式計算框架應(yīng)運而生。在MapReduce框架下,一個作業(yè)被分為多個任務(wù)分發(fā)到多個節(jié)點上并行執(zhí)行,加快作業(yè)的完成。但在執(zhí)行過程中,有的任務(wù)與其它任務(wù)相比,執(zhí)行的異常緩慢,拖慢了整個作業(yè)的完成,這就是落后任務(wù)。推測執(zhí)行策略是解決落后任務(wù)問題通用的方法,通過簡單備份落后任務(wù)到備選機器上,期望可以加快作業(yè)完成。因此,推測執(zhí)行策略包括識別作業(yè)中的落后任務(wù)以及選擇合適的備份節(jié)點兩步。不同的推測執(zhí)行策略提出了很多落后任務(wù)識別的方法,其中FlexSlot利用k-means聚類算法識別落后任務(wù)時,無論作業(yè)中是否存在落后任務(wù),總會識別出一類落后任務(wù)來,導(dǎo)致落后任務(wù)的識別準(zhǔn)確率不高。本文分析了 FlexSlot策略落后任務(wù)識別準(zhǔn)確率不高的原因,并對其進(jìn)行改進(jìn),提出一個基于聚類優(yōu)化的落后任務(wù)識別模型。首先,為了找出比較符合任務(wù)運行真實情況的任務(wù)劃分,人為為k-means中的k指定一個閾值范圍,在該范圍內(nèi)基于任務(wù)的進(jìn)度率、處理帶寬這兩個聚類特征對任務(wù)并行聚類,得到多種聚類結(jié)果;其次,利用DBI得到最符合任務(wù)運行情況的最優(yōu)任務(wù)劃分;再次,為了避免將大部分正常任務(wù)識別為落后任務(wù)這種情況,利用空閑資源數(shù)以及作業(yè)任務(wù)數(shù)對落后任務(wù)類中任務(wù)的個數(shù)加以限制;最后,限制最慢任務(wù)類中的任務(wù)要慢于次慢任務(wù)類任務(wù)的α倍,保證落后任務(wù)確實很慢。為落后任務(wù)選擇合適的備份節(jié)點�，F(xiàn)有的一些推測執(zhí)行策略在選擇備份節(jié)點時,或是避免選擇節(jié)點性能較差的節(jié)點,或是通過預(yù)測備份任務(wù)的備份時間來決定備份節(jié)點。然而,通過預(yù)測備份時間來決定備份節(jié)點的方法,往往是基于節(jié)點上已完成的歷史任務(wù)信息,而不考慮備份任務(wù)實際的資源需求特性,不能很好地預(yù)測備份時間。因此本文提出一個基于Dijkstra算法的最優(yōu)備份節(jié)點搜索模型。首先,基于同一作業(yè)所有任務(wù)分配的資源情況和處理帶寬信息,利用線性回歸建立資源速度模型,預(yù)測備份任務(wù)在可能備份節(jié)點上的處理帶寬,從而得到備份任務(wù)的處理時間花銷;其次,將集群節(jié)點簡化為圖論中的頂點,將備份任務(wù)的處理時間花銷和數(shù)據(jù)遷移時間花銷簡化為頂點間的權(quán)重;最后,根據(jù)兩種搜索策略,得到最短的備份時間以及最優(yōu)備份節(jié)點。實驗表明在不同工作負(fù)載下,本文提出的基于聚類優(yōu)化的落后任務(wù)識別模型落后任務(wù)的識別準(zhǔn)確率高于FlexSlot、MCP�；贒ijkstra算法的最優(yōu)備份節(jié)點搜索模型能夠較好的處理落后任務(wù),比FlexSlot減少了約10%的作業(yè)執(zhí)行時間,比MCP減少了約20%的作業(yè)執(zhí)行時間。在備份成功率上,本文的推測執(zhí)行策略的備份成功率相比FlexSlot和MCP分別提高了約12.4%、48.8%。本文提出的推測執(zhí)行策略的CPU利用率和內(nèi)存利用率高于FlexSlot、MCP。
【圖文】：

邐山東大學(xué)碩士學(xué)位論文邐逡逑由于ＦｌｅｘＳｌｏｔ的過度識別落后任務(wù)，因此它要比ＭＣＰ、本文提出ＣＯＳＲＤＮＳ查全逡逑率要高。但是查準(zhǔn)率低對作業(yè)的影響要比查全率對作業(yè)的影響更大，因為查準(zhǔn)率逡逑低意味著要大量備份正常任務(wù)，造成集群資源浪費，甚至?xí)觿÷浜笕蝿?wù)問題，逡逑影響作業(yè)的完成；查全率低則意味著作業(yè)所有的落后任務(wù)，在識別時僅僅識別出逡逑一部分落后任務(wù)，那么只會備份這部分落后任務(wù)，其它落后任務(wù)不備份，不會浪逡逑費集群資源。因此本文提出的基于聚類優(yōu)化的落后任務(wù)識別模型比ＭＣＰ的落后任逡逑務(wù)識別策略識別落后任務(wù)的效果好。本文提出的基于聚類優(yōu)化的落后任務(wù)識別模逡逑型與ＦｌｅｘＳｌｏｔ的落后任務(wù)識別策略相比，識別準(zhǔn)確率提高了很多，查全率稍微低一逡逑點，因此本文提出的ＣＯＳＲＤＮＳ比：ＦｌｅｘＳｌｏｔ的落后任務(wù)識別策略識別落后任務(wù)的逡逑效果好。同時，也可以看出本文提出的ＣＯＳＲＤＮＳ要比ＭＣＰ的落后任務(wù)識別策略逡逑識別落后任務(wù)的效果要好。逡逑￣１００％邐逡逑

邐山東大學(xué)碩士學(xué)位論文邐逡逑間也可表示為ｗ［ｌ］［２］。ｗ［ｌ］［２］和ｗ［ｌ］［３］表示的是落后任務(wù)經(jīng)過一般節(jié)點到達(dá)數(shù)據(jù)逡逑副本所在節(jié)點的距離。根據(jù)以上兩種情況，，落后任務(wù)的最短的備份時間可表示為逡逑＂？艦邐＝邋ｍｉｎ｛ｍｉｎ｛Ｄ［．／］［R%丨戶邋ｅ邋廠－？／｝，邋ｍｉｎ邋｛￡＞［／］邋［ｇ］邋｜邋ｇ邋ｅ邋＃邋－邋ｙ｝｝�！辏荆郏荩鄞ū硎镜谝诲义戏N情況，可以通過遍歷得到。／）［＿／］［《］表示第二種情況可以通過Ｄｉｊｋｓｔｒａ［４（）］算法得逡逑到落后任務(wù)所在節(jié)點到數(shù)據(jù)副本所在節(jié)點的最短時間。第一種情況下的最小值和逡逑第二種情況下的最小值，它們兩者中的最小值就為落后任務(wù)最短的備份時間，同逡逑時得到最優(yōu)備份節(jié)點。逡逑＾■＞、邐，邋、逡逑
【學(xué)位授予單位】：山東大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2018
【分類號】：TP311.13

【參考文獻(xiàn)】

相關(guān)期刊論文 前1條

1 樊源泉;伍衛(wèi)國;許云龍;陳衡;;基于平衡偏斜負(fù)載方法的MapReduce性能優(yōu)化機制(英文)[J];中國通信;2014年08期

本文編號：2702740