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

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

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

【參考文獻(xiàn)】

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

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

本文編號(hào)：2702740