實(shí)驗(yàn)結(jié)果分析三課件

1面向一種云計(jì)算平臺(tái)的調(diào)度技術(shù)研究學(xué)生：李麗英指導(dǎo)老師：李仁發(fā)教授

唐卓講師時(shí)間：2011年5月28日1面向一種云計(jì)算平臺(tái)的調(diào)度技術(shù)研究學(xué)生：李麗英主要內(nèi)容研究背景及意義目前存在的問(wèn)題研究?jī)?nèi)容及成果總結(jié)及展望2主要內(nèi)容研究背景及意義目前存在的問(wèn)題研究?jī)?nèi)容及成果總結(jié)及展望研究背景及意義云計(jì)算是把集成化的基礎(chǔ)設(shè)施動(dòng)態(tài)的分配給內(nèi)部或者外部使用，這種充分利用現(xiàn)有資源并對(duì)資源進(jìn)行整合形成資源池后，再按需分配給用戶(hù)的服務(wù)提供方式受到了商業(yè)化應(yīng)用的極大推薦。1、應(yīng)用背景3研究背景及意義云計(jì)算是把集成化的基礎(chǔ)設(shè)施動(dòng)態(tài)的分配給內(nèi)部或者研究背景及意義編程模型服務(wù)質(zhì)量數(shù)據(jù)安全實(shí)用性強(qiáng)資源利用率高2、云計(jì)算特點(diǎn)43、云計(jì)算調(diào)度技術(shù)特點(diǎn)與發(fā)展現(xiàn)狀Perfect？應(yīng)該具備的特征發(fā)展現(xiàn)狀可擴(kuò)展性動(dòng)態(tài)性服務(wù)等級(jí)區(qū)分性云技術(shù)調(diào)度技術(shù)研究處于剛起步的階段存在不同的云計(jì)算平臺(tái)，基于具體平臺(tái)的調(diào)度技術(shù)甚少研究背景及意義編程服務(wù)數(shù)據(jù)實(shí)用性強(qiáng)資源利2、云計(jì)算特點(diǎn)43、主要內(nèi)容研究背景及意義Hadoop調(diào)度技術(shù)目前存在的問(wèn)題研究?jī)?nèi)容及成果總結(jié)及展望5主要內(nèi)容研究背景及意義Hadoop調(diào)度技術(shù)目前存在的問(wèn)題研究Hadoop平臺(tái)調(diào)度技術(shù)目前存在的問(wèn)題存在不足1、Hadoop是典型的處理數(shù)據(jù)密集型任務(wù)的分布式云計(jì)算平臺(tái)。調(diào)度算法需要考慮數(shù)據(jù)的讀取問(wèn)題2、Hadoop自帶的任務(wù)推測(cè)執(zhí)行算法會(huì)導(dǎo)致過(guò)多的任務(wù)備份執(zhí)行2、Hadoop的數(shù)據(jù)存儲(chǔ)方式以及任務(wù)處理模式導(dǎo)致數(shù)據(jù)局部性問(wèn)題異常突出3、數(shù)據(jù)局部性問(wèn)題會(huì)嚴(yán)重影響Hadoop云計(jì)算平臺(tái)的性能1、Hadoop云平臺(tái)同時(shí)可能處理成千上萬(wàn)的任務(wù)，備份任務(wù)推測(cè)執(zhí)行調(diào)度算法還處于不完善的階段3、備份任務(wù)推測(cè)執(zhí)行調(diào)度算法也需要考慮數(shù)據(jù)局部性?xún)?yōu)化問(wèn)題信息隱蔽技術(shù)備份任務(wù)推測(cè)執(zhí)行數(shù)據(jù)局部性問(wèn)題Hadoop平臺(tái)調(diào)度技術(shù)目前存在的問(wèn)題存在不足1、Hadoo主要內(nèi)容研究背景及意義目前存在的問(wèn)題研究?jī)?nèi)容及成果總結(jié)及展望7主要內(nèi)容研究背景及意義目前存在的問(wèn)題研究?jī)?nèi)容及成果總結(jié)及展望研究?jī)?nèi)容及成果8本文從兩方面分析Hadoop云計(jì)算平臺(tái)中備份任務(wù)推測(cè)執(zhí)行調(diào)度性能：在考慮數(shù)據(jù)局部性?xún)?yōu)化問(wèn)題的同時(shí)，利用概率論原理權(quán)衡數(shù)據(jù)局部性?xún)?yōu)化問(wèn)題和因其反而影響平臺(tái)調(diào)度性能的問(wèn)題基于數(shù)據(jù)局部性改進(jìn)LATE備份任務(wù)推測(cè)執(zhí)行調(diào)度算法，分機(jī)架考慮備份任務(wù)推測(cè)執(zhí)行的調(diào)度方面一方面二研究?jī)?nèi)容及成果8本文從兩方面分析Hadoop云計(jì)算平臺(tái)中備份基于數(shù)據(jù)局部性對(duì)LATE算法的改進(jìn)策略Hadoop系統(tǒng)架構(gòu)9基于數(shù)據(jù)局部性對(duì)LATE算法的改進(jìn)策略Hadoop系統(tǒng)架構(gòu)9Hadoop集群部署Hadoop集群按數(shù)據(jù)中心、機(jī)架、節(jié)點(diǎn)三層架構(gòu)部署集群10Hadoop集群部署Hadoop集群按數(shù)據(jù)中心、機(jī)架、節(jié)點(diǎn)三學(xué)習(xí)過(guò)程之一社保基礎(chǔ)知識(shí)改進(jìn)算法的詳細(xì)設(shè)計(jì)11SpeculationCap同一時(shí)刻Hadoop系統(tǒng)中的備份任務(wù)執(zhí)行數(shù)閾值判斷任務(wù)是否需要備份執(zhí)行閾值SlowTaskThreshold判斷節(jié)點(diǎn)處理任務(wù)快慢的閾值SlowNodeThreshold改進(jìn)算法中三個(gè)基本參數(shù)說(shuō)明t是任務(wù)已經(jīng)執(zhí)行了的時(shí)間ProgresScore進(jìn)程分Progressrate是進(jìn)程速率T是最終要得到的任務(wù)完成還需要的時(shí)間判斷為慢任務(wù)的計(jì)算公式：學(xué)習(xí)過(guò)程之一社?；A(chǔ)知識(shí)改進(jìn)算法的詳細(xì)設(shè)計(jì)11Specul改進(jìn)算法的詳細(xì)設(shè)計(jì)如果有一個(gè)節(jié)點(diǎn)請(qǐng)求新的任務(wù)，并且整個(gè)Hadoop集群中備份任務(wù)執(zhí)行數(shù)量小于SpeculationCap，則往下執(zhí)行：第一步：判斷節(jié)點(diǎn)的快慢，如果低于SlowNodeThreshold，則忽略這個(gè)請(qǐng)求，結(jié)束整個(gè)算法，否則繼續(xù)執(zhí)行。12第二步：根據(jù)請(qǐng)求任務(wù)節(jié)點(diǎn)所在的機(jī)架，對(duì)該機(jī)架上正在執(zhí)行的任務(wù)，首先根據(jù)SlowTaskThreshold的值判定是否為慢任務(wù)，如果是則計(jì)算完成還需要多少時(shí)間，并放入一個(gè)隊(duì)列中，對(duì)這個(gè)隊(duì)列按照時(shí)間長(zhǎng)短從低到高進(jìn)行排序，同時(shí)對(duì)于還沒(méi)有標(biāo)記且已經(jīng)開(kāi)始等待推測(cè)執(zhí)行的任務(wù)進(jìn)行標(biāo)記。如果隊(duì)列不為空，則執(zhí)行第三步，否則執(zhí)行第四步。改進(jìn)算法的詳細(xì)設(shè)計(jì)如果有一個(gè)節(jié)點(diǎn)請(qǐng)求新的任務(wù)，并且整個(gè)Had改進(jìn)算法的詳細(xì)設(shè)計(jì)第三步：在該隊(duì)列中查找是否有數(shù)據(jù)存儲(chǔ)在請(qǐng)求節(jié)點(diǎn)的任務(wù)，如果沒(méi)有則查找隊(duì)列中是否有等待時(shí)間大于T1的任務(wù)，否則從該隊(duì)列中選擇排在首位的任務(wù)推測(cè)執(zhí)行。13第四步：對(duì)其它機(jī)架上正在執(zhí)行的任務(wù)判斷是否為慢任務(wù)，如果是則放進(jìn)另外一個(gè)隊(duì)列中，計(jì)算完成任務(wù)還需要多少時(shí)間后從低到高進(jìn)行排序，同時(shí)對(duì)于還沒(méi)有標(biāo)記且已經(jīng)開(kāi)始等待推測(cè)執(zhí)行的任務(wù)進(jìn)行標(biāo)記，首先選擇隊(duì)列中等待時(shí)間大于T2的任務(wù)，沒(méi)有則選擇排在隊(duì)列中最前的任務(wù)推測(cè)執(zhí)行。改進(jìn)算法的詳細(xì)設(shè)計(jì)第三步：在該隊(duì)列中查找是否有數(shù)據(jù)存儲(chǔ)在請(qǐng)求改進(jìn)算法的詳細(xì)設(shè)計(jì)T1、T2值設(shè)定采用一個(gè)簡(jiǎn)單的數(shù)學(xué)模式來(lái)評(píng)估任務(wù)等待本地節(jié)/機(jī)架處理時(shí)給任務(wù)響應(yīng)時(shí)間帶來(lái)的影響，由于在大規(guī)模集群中，請(qǐng)求任務(wù)處理的節(jié)點(diǎn)剛好是任務(wù)隊(duì)列中首個(gè)任務(wù)需要這個(gè)節(jié)點(diǎn)數(shù)據(jù)的情況，服從概率論當(dāng)中的稀有事件發(fā)生概率模型，即每t秒之內(nèi)有這種事件發(fā)生。因此事件的發(fā)生概率服從泊松分布:t:代表每t秒之內(nèi)有這種稀有事件發(fā)生t1:代表每個(gè)任務(wù)在非節(jié)點(diǎn)/機(jī)架處理比在本節(jié)點(diǎn)/機(jī)架處理需要花的時(shí)間多t1秒t2:任務(wù)等待在本節(jié)點(diǎn)/機(jī)架處理的時(shí)間為t2秒T1、T2值的設(shè)定14改進(jìn)算法的詳細(xì)設(shè)計(jì)T1、T2值設(shè)定采用一個(gè)簡(jiǎn)單的數(shù)學(xué)模式來(lái)評(píng)改進(jìn)算法在云計(jì)算仿真平臺(tái)Cloudsim中的仿真實(shí)驗(yàn)性能分析仿真平臺(tái)環(huán)境配置：CloudSim仿真工具軟件包Windows操作系統(tǒng)或linux操作系統(tǒng)1.86GHz以上處理器JDK1.6以上版本Eclipse開(kāi)發(fā)平臺(tái)擴(kuò)展工具

ant1.7.1模擬的Hadoop集群配置：機(jī)架里的主機(jī)數(shù)，虛擬機(jī)數(shù)都盡量參照了EC2部署Hadoop集群的方式機(jī)架虛擬機(jī)/主機(jī)（個(gè)）/（臺(tái)）主機(jī)數(shù)（臺(tái)）虛擬機(jī)數(shù)（個(gè)）機(jī)架12個(gè)/臺(tái)10~10020~2003個(gè)/臺(tái)20~10060~300機(jī)架22個(gè)/臺(tái)10~10020~2003個(gè)/臺(tái)20~10060~300機(jī)架32個(gè)/臺(tái)10~10020~2003個(gè)/臺(tái)20~10060~30015模擬兩個(gè)實(shí)驗(yàn)場(chǎng)景：第一個(gè)實(shí)驗(yàn)場(chǎng)景：沒(méi)有故障的節(jié)點(diǎn)，但是節(jié)點(diǎn)之間有性能差異第二個(gè)實(shí)驗(yàn)場(chǎng)景：設(shè)置集群中有故障節(jié)點(diǎn)的情況改進(jìn)算法在云計(jì)算仿真平臺(tái)Cloudsim中的仿真實(shí)驗(yàn)性能分析實(shí)驗(yàn)結(jié)果分析一：工作響應(yīng)時(shí)間根據(jù)Hadoop集群中一個(gè)數(shù)據(jù)塊的大小，處理任務(wù)的時(shí)間，以及部署集群時(shí)網(wǎng)絡(luò)資源的性能等，設(shè)置了不同的T1、T2值驗(yàn)證工作響應(yīng)時(shí)間，從上圖可以分析出當(dāng)T1=15秒、T2=20秒的情況下任務(wù)的響應(yīng)時(shí)間最佳。16實(shí)驗(yàn)結(jié)果分析一：工作響應(yīng)時(shí)間根據(jù)Hadoop集群中一個(gè)數(shù)據(jù)塊實(shí)驗(yàn)結(jié)果分析一：工作響應(yīng)時(shí)間17對(duì)兩個(gè)場(chǎng)景分別進(jìn)行了模擬實(shí)驗(yàn)，分析證明在沒(méi)有故障節(jié)點(diǎn)的第一個(gè)場(chǎng)景下，改進(jìn)的算法平均工作響應(yīng)時(shí)間依然略高于其它兩個(gè)算法；在第二個(gè)場(chǎng)景中，Hadoop沒(méi)有采用備份任務(wù)推測(cè)執(zhí)行調(diào)度算法的工作響應(yīng)時(shí)間會(huì)明顯大于推測(cè)執(zhí)行算法。實(shí)驗(yàn)結(jié)果分析一：工作響應(yīng)時(shí)間17對(duì)兩個(gè)場(chǎng)景分別進(jìn)行了模擬實(shí)驗(yàn)實(shí)驗(yàn)結(jié)果分析一：工作響應(yīng)時(shí)間18不同Sort工作大小在三種算法下任務(wù)響應(yīng)時(shí)間對(duì)比不同Grep工作大小在三種算法下任務(wù)響應(yīng)時(shí)間對(duì)比響應(yīng)時(shí)間的減少率從30GB的約20%降到了90GB的15%，三個(gè)算法之間的性能差異隨著工作的增大會(huì)越來(lái)越小。實(shí)驗(yàn)結(jié)果分析一：工作響應(yīng)時(shí)間18不同Sort工作大小在三種算實(shí)驗(yàn)結(jié)果分析一：工作響應(yīng)時(shí)間19Sort工作在三種算法下的響應(yīng)時(shí)間Grep工作在三種算法下的響應(yīng)時(shí)間1、最優(yōu)性能：基于數(shù)據(jù)局部性改進(jìn)的LATE算法高于其它兩種算法2、最差性能：改進(jìn)的算法跟LATE算法相差不大3、平均性能：改進(jìn)的算法有著比較明顯的優(yōu)勢(shì)4、不同的工作類(lèi)型在性能表現(xiàn)上的差異：Sort工作使用改進(jìn)后的推測(cè)執(zhí)行算法在性能上會(huì)比其它兩種算法會(huì)有更大程度的改善實(shí)驗(yàn)結(jié)果分析一：工作響應(yīng)時(shí)間19Sort工作在三種算法下的響實(shí)驗(yàn)結(jié)果分析二：任務(wù)本地化處理率分析20為了驗(yàn)證基于數(shù)據(jù)局部性的改進(jìn)算法對(duì)提高本地化處理任務(wù)的作用，設(shè)置了大小不同的工作，輸入數(shù)據(jù)：640MB、3200MB、6400MB。即Map任務(wù)的個(gè)數(shù)分別是10、50、100，集群中機(jī)架數(shù)分別設(shè)置為4個(gè)和10個(gè)。10個(gè)Map任務(wù)時(shí)本節(jié)點(diǎn)/機(jī)架處理率4個(gè)機(jī)架時(shí)本節(jié)點(diǎn)/機(jī)架處理率10個(gè)機(jī)架時(shí)本節(jié)點(diǎn)/機(jī)架處理率實(shí)驗(yàn)結(jié)果分析二：任務(wù)本地化處理率分析20為了驗(yàn)證基于數(shù)據(jù)局部實(shí)驗(yàn)結(jié)果分析二：任務(wù)本地化處理率分析2150個(gè)Map任務(wù)時(shí)本節(jié)點(diǎn)/機(jī)架處理率4個(gè)機(jī)架時(shí)本節(jié)點(diǎn)/機(jī)架處理率10個(gè)機(jī)架時(shí)本節(jié)點(diǎn)/機(jī)架處理率100個(gè)Map任務(wù)時(shí)本節(jié)點(diǎn)/機(jī)架處理率4個(gè)機(jī)架時(shí)本節(jié)點(diǎn)/機(jī)架處理率10個(gè)機(jī)架時(shí)本節(jié)點(diǎn)/機(jī)架處理率實(shí)驗(yàn)結(jié)果分析二：任務(wù)本地化處理率分析2150個(gè)Map任務(wù)時(shí)本22結(jié)論實(shí)驗(yàn)結(jié)果分析二：任務(wù)本地化處理率分析縱向比較，改進(jìn)的LATE算法相對(duì)LATE算法任務(wù)的本地節(jié)點(diǎn)/機(jī)架處理率提高了6%~9%，但相對(duì)Hadoop自帶的算法優(yōu)勢(shì)并不是很明顯。而對(duì)于較大的工作，數(shù)據(jù)局部性改進(jìn)算法的處理優(yōu)勢(shì)沒(méi)有小的工作增加的明顯當(dāng)機(jī)架數(shù)少于等于4個(gè)時(shí)，基本上數(shù)據(jù)塊在不同的機(jī)架存有其副本，任務(wù)本節(jié)點(diǎn)/本機(jī)架處理的概率會(huì)很高，就算沒(méi)有基于數(shù)據(jù)局部性的改進(jìn)算法，任務(wù)推測(cè)執(zhí)行本地化處理的性能也會(huì)比較理想橫向比較，按照集群從小到大的順序，LATE算法任務(wù)本節(jié)點(diǎn)/機(jī)架處理率依次減小從上述三組圖中可以分析出以下結(jié)論：22結(jié)論實(shí)驗(yàn)結(jié)果分析二：任務(wù)本地化處理率分析縱向比較，改進(jìn)的實(shí)驗(yàn)結(jié)果分析三：系統(tǒng)吞吐率分析23從上圖可以分析出基于數(shù)據(jù)局部性的改進(jìn)算法無(wú)論在什么工作類(lèi)型的情形下都能提高系統(tǒng)的吞吐率性能在絕大部分備份執(zhí)行任務(wù)都在本節(jié)點(diǎn)/機(jī)架上處理時(shí)，系統(tǒng)吞吐率提高了近150%多個(gè)Sort工作系統(tǒng)吞吐率對(duì)比多個(gè)Grep工作系統(tǒng)吞吐率對(duì)比不同的工作類(lèi)型系統(tǒng)吞吐率對(duì)比實(shí)驗(yàn)結(jié)果分析三：系統(tǒng)吞吐率分析23從上圖可以分析出基于數(shù)據(jù)局主要內(nèi)容研究背景及意義目前存在的問(wèn)題研究?jī)?nèi)容及成果總結(jié)及展望24主要內(nèi)容研究背景及意義目前存在的問(wèn)題研究?jī)?nèi)容及成果總結(jié)及展望總結(jié)25根據(jù)Hadoop數(shù)據(jù)的存儲(chǔ)特性，提出了基于數(shù)據(jù)局部性對(duì)LATE算法的改進(jìn)策略，在Hadoop平臺(tái)中分機(jī)架考慮任務(wù)推測(cè)執(zhí)行的調(diào)度問(wèn)題，選擇備份任務(wù)推測(cè)執(zhí)行時(shí)，優(yōu)先選擇數(shù)據(jù)存儲(chǔ)在請(qǐng)求處理的節(jié)點(diǎn)或者機(jī)架上的任務(wù)推測(cè)執(zhí)行；如果沒(méi)有數(shù)據(jù)存儲(chǔ)在本節(jié)點(diǎn)或者本機(jī)架的任務(wù)需要推測(cè)執(zhí)行，再考慮在其它機(jī)架上查找需要推測(cè)執(zhí)行的任務(wù)利用統(tǒng)計(jì)學(xué)概率論解決任務(wù)等待時(shí)間過(guò)長(zhǎng)影響工作響應(yīng)時(shí)間的情況。根據(jù)泊松分布，綜合考慮數(shù)據(jù)局部性?xún)?yōu)化和任務(wù)等待本節(jié)點(diǎn)或者本機(jī)架處理時(shí)間過(guò)長(zhǎng)反而影響任務(wù)響應(yīng)時(shí)間的問(wèn)題本文研究的主要貢獻(xiàn)總結(jié)25根據(jù)Hadoop數(shù)據(jù)的存儲(chǔ)特性，提出了基于數(shù)據(jù)局部性展望26本文還未解決的問(wèn)題改進(jìn)的算法選擇備份任務(wù)執(zhí)行時(shí)，要對(duì)整個(gè)系統(tǒng)進(jìn)行兩次排序：一次是本機(jī)架內(nèi)部的任務(wù)，一次是跨機(jī)架的任務(wù)，這樣會(huì)消耗一部分時(shí)間，并且有可能會(huì)因?yàn)榭鐧C(jī)架的原因跳過(guò)最需要備份執(zhí)行的任務(wù)，如果能考慮對(duì)其它機(jī)架上的任務(wù)由于跨機(jī)架讀取數(shù)據(jù)的原因而設(shè)定一個(gè)權(quán)值，然后在參考該權(quán)值的基礎(chǔ)上引入排隊(duì)論的原理對(duì)整個(gè)機(jī)架上所有的任務(wù)統(tǒng)一進(jìn)行一次加權(quán)排序，這樣性能估計(jì)會(huì)有更大程度上的提高，只是這個(gè)權(quán)值比較難以取舍，需要一些理論依據(jù)，希望以后能從這方面加以改進(jìn)由于實(shí)驗(yàn)條件的限制，只能在仿真平臺(tái)中搭建模擬的環(huán)境進(jìn)行仿真測(cè)試，跟實(shí)際系統(tǒng)上測(cè)試的性能會(huì)有所差別，所以希望能在實(shí)際的Hadoop平臺(tái)中進(jìn)行進(jìn)一步的性能測(cè)試分析ONETWO展望26本文還未解決的問(wèn)題改進(jìn)的算法選擇備份任務(wù)執(zhí)行時(shí)，要對(duì)論文發(fā)表情況李麗英,唐卓，李仁發(fā)．基于LATE的Hadoop數(shù)據(jù)局部性改進(jìn)調(diào)度算法計(jì)算機(jī)科學(xué)，已錄用，預(yù)計(jì)于2011第11期發(fā)表，文章編號(hào)20101202451LiLiying,TangZhuo,LiRenfa．NewimprovementoftheHadooprelevantdatalocalityschedulingalgorithmbasedonLATE.IEEECatalogNumber:CFP1157N-;ISBN:978-1-61284-720-7.27論文發(fā)表情況27謝謝！282829面向一種云計(jì)算平臺(tái)的調(diào)度技術(shù)研究學(xué)生：李麗英指導(dǎo)老師：李仁發(fā)教授

唐卓講師時(shí)間：2011年5月28日1面向一種云計(jì)算平臺(tái)的調(diào)度技術(shù)研究學(xué)生：李麗英主要內(nèi)容研究背景及意義目前存在的問(wèn)題研究?jī)?nèi)容及成果總結(jié)及展望30主要內(nèi)容研究背景及意義目前存在的問(wèn)題研究?jī)?nèi)容及成果總結(jié)及展望研究背景及意義云計(jì)算是把集成化的基礎(chǔ)設(shè)施動(dòng)態(tài)的分配給內(nèi)部或者外部使用，這種充分利用現(xiàn)有資源并對(duì)資源進(jìn)行整合形成資源池后，再按需分配給用戶(hù)的服務(wù)提供方式受到了商業(yè)化應(yīng)用的極大推薦。1、應(yīng)用背景31研究背景及意義云計(jì)算是把集成化的基礎(chǔ)設(shè)施動(dòng)態(tài)的分配給內(nèi)部或者研究背景及意義編程模型服務(wù)質(zhì)量數(shù)據(jù)安全實(shí)用性強(qiáng)資源利用率高2、云計(jì)算特點(diǎn)323、云計(jì)算調(diào)度技術(shù)特點(diǎn)與發(fā)展現(xiàn)狀Perfect？應(yīng)該具備的特征發(fā)展現(xiàn)狀可擴(kuò)展性動(dòng)態(tài)性服務(wù)等級(jí)區(qū)分性云技術(shù)調(diào)度技術(shù)研究處于剛起步的階段存在不同的云計(jì)算平臺(tái)，基于具體平臺(tái)的調(diào)度技術(shù)甚少研究背景及意義編程服務(wù)數(shù)據(jù)實(shí)用性強(qiáng)資源利2、云計(jì)算特點(diǎn)43、主要內(nèi)容研究背景及意義Hadoop調(diào)度技術(shù)目前存在的問(wèn)題研究?jī)?nèi)容及成果總結(jié)及展望33主要內(nèi)容研究背景及意義Hadoop調(diào)度技術(shù)目前存在的問(wèn)題研究Hadoop平臺(tái)調(diào)度技術(shù)目前存在的問(wèn)題存在不足1、Hadoop是典型的處理數(shù)據(jù)密集型任務(wù)的分布式云計(jì)算平臺(tái)。調(diào)度算法需要考慮數(shù)據(jù)的讀取問(wèn)題2、Hadoop自帶的任務(wù)推測(cè)執(zhí)行算法會(huì)導(dǎo)致過(guò)多的任務(wù)備份執(zhí)行2、Hadoop的數(shù)據(jù)存儲(chǔ)方式以及任務(wù)處理模式導(dǎo)致數(shù)據(jù)局部性問(wèn)題異常突出3、數(shù)據(jù)局部性問(wèn)題會(huì)嚴(yán)重影響Hadoop云計(jì)算平臺(tái)的性能1、Hadoop云平臺(tái)同時(shí)可能處理成千上萬(wàn)的任務(wù)，備份任務(wù)推測(cè)執(zhí)行調(diào)度算法還處于不完善的階段3、備份任務(wù)推測(cè)執(zhí)行調(diào)度算法也需要考慮數(shù)據(jù)局部性?xún)?yōu)化問(wèn)題信息隱蔽技術(shù)備份任務(wù)推測(cè)執(zhí)行數(shù)據(jù)局部性問(wèn)題Hadoop平臺(tái)調(diào)度技術(shù)目前存在的問(wèn)題存在不足1、Hadoo主要內(nèi)容研究背景及意義目前存在的問(wèn)題研究?jī)?nèi)容及成果總結(jié)及展望35主要內(nèi)容研究背景及意義目前存在的問(wèn)題研究?jī)?nèi)容及成果總結(jié)及展望研究?jī)?nèi)容及成果36本文從兩方面分析Hadoop云計(jì)算平臺(tái)中備份任務(wù)推測(cè)執(zhí)行調(diào)度性能：在考慮數(shù)據(jù)局部性?xún)?yōu)化問(wèn)題的同時(shí)，利用概率論原理權(quán)衡數(shù)據(jù)局部性?xún)?yōu)化問(wèn)題和因其反而影響平臺(tái)調(diào)度性能的問(wèn)題基于數(shù)據(jù)局部性改進(jìn)LATE備份任務(wù)推測(cè)執(zhí)行調(diào)度算法，分機(jī)架考慮備份任務(wù)推測(cè)執(zhí)行的調(diào)度方面一方面二研究?jī)?nèi)容及成果8本文從兩方面分析Hadoop云計(jì)算平臺(tái)中備份基于數(shù)據(jù)局部性對(duì)LATE算法的改進(jìn)策略Hadoop系統(tǒng)架構(gòu)37基于數(shù)據(jù)局部性對(duì)LATE算法的改進(jìn)策略Hadoop系統(tǒng)架構(gòu)9Hadoop集群部署Hadoop集群按數(shù)據(jù)中心、機(jī)架、節(jié)點(diǎn)三層架構(gòu)部署集群38Hadoop集群部署Hadoop集群按數(shù)據(jù)中心、機(jī)架、節(jié)點(diǎn)三學(xué)習(xí)過(guò)程之一社?；A(chǔ)知識(shí)改進(jìn)算法的詳細(xì)設(shè)計(jì)39SpeculationCap同一時(shí)刻Hadoop系統(tǒng)中的備份任務(wù)執(zhí)行數(shù)閾值判斷任務(wù)是否需要備份執(zhí)行閾值SlowTaskThreshold判斷節(jié)點(diǎn)處理任務(wù)快慢的閾值SlowNodeThreshold改進(jìn)算法中三個(gè)基本參數(shù)說(shuō)明t是任務(wù)已經(jīng)執(zhí)行了的時(shí)間ProgresScore進(jìn)程分Progressrate是進(jìn)程速率T是最終要得到的任務(wù)完成還需要的時(shí)間判斷為慢任務(wù)的計(jì)算公式：學(xué)習(xí)過(guò)程之一社保基礎(chǔ)知識(shí)改進(jìn)算法的詳細(xì)設(shè)計(jì)11Specul改進(jìn)算法的詳細(xì)設(shè)計(jì)如果有一個(gè)節(jié)點(diǎn)請(qǐng)求新的任務(wù)，并且整個(gè)Hadoop集群中備份任務(wù)執(zhí)行數(shù)量小于SpeculationCap，則往下執(zhí)行：第一步：判斷節(jié)點(diǎn)的快慢，如果低于SlowNodeThreshold，則忽略這個(gè)請(qǐng)求，結(jié)束整個(gè)算法，否則繼續(xù)執(zhí)行。40第二步：根據(jù)請(qǐng)求任務(wù)節(jié)點(diǎn)所在的機(jī)架，對(duì)該機(jī)架上正在執(zhí)行的任務(wù)，首先根據(jù)SlowTaskThreshold的值判定是否為慢任務(wù)，如果是則計(jì)算完成還需要多少時(shí)間，并放入一個(gè)隊(duì)列中，對(duì)這個(gè)隊(duì)列按照時(shí)間長(zhǎng)短從低到高進(jìn)行排序，同時(shí)對(duì)于還沒(méi)有標(biāo)記且已經(jīng)開(kāi)始等待推測(cè)執(zhí)行的任務(wù)進(jìn)行標(biāo)記。如果隊(duì)列不為空，則執(zhí)行第三步，否則執(zhí)行第四步。改進(jìn)算法的詳細(xì)設(shè)計(jì)如果有一個(gè)節(jié)點(diǎn)請(qǐng)求新的任務(wù)，并且整個(gè)Had改進(jìn)算法的詳細(xì)設(shè)計(jì)第三步：在該隊(duì)列中查找是否有數(shù)據(jù)存儲(chǔ)在請(qǐng)求節(jié)點(diǎn)的任務(wù)，如果沒(méi)有則查找隊(duì)列中是否有等待時(shí)間大于T1的任務(wù)，否則從該隊(duì)列中選擇排在首位的任務(wù)推測(cè)執(zhí)行。41第四步：對(duì)其它機(jī)架上正在執(zhí)行的任務(wù)判斷是否為慢任務(wù)，如果是則放進(jìn)另外一個(gè)隊(duì)列中，計(jì)算完成任務(wù)還需要多少時(shí)間后從低到高進(jìn)行排序，同時(shí)對(duì)于還沒(méi)有標(biāo)記且已經(jīng)開(kāi)始等待推測(cè)執(zhí)行的任務(wù)進(jìn)行標(biāo)記，首先選擇隊(duì)列中等待時(shí)間大于T2的任務(wù)，沒(méi)有則選擇排在隊(duì)列中最前的任務(wù)推測(cè)執(zhí)行。改進(jìn)算法的詳細(xì)設(shè)計(jì)第三步：在該隊(duì)列中查找是否有數(shù)據(jù)存儲(chǔ)在請(qǐng)求改進(jìn)算法的詳細(xì)設(shè)計(jì)T1、T2值設(shè)定采用一個(gè)簡(jiǎn)單的數(shù)學(xué)模式來(lái)評(píng)估任務(wù)等待本地節(jié)/機(jī)架處理時(shí)給任務(wù)響應(yīng)時(shí)間帶來(lái)的影響，由于在大規(guī)模集群中，請(qǐng)求任務(wù)處理的節(jié)點(diǎn)剛好是任務(wù)隊(duì)列中首個(gè)任務(wù)需要這個(gè)節(jié)點(diǎn)數(shù)據(jù)的情況，服從概率論當(dāng)中的稀有事件發(fā)生概率模型，即每t秒之內(nèi)有這種事件發(fā)生。因此事件的發(fā)生概率服從泊松分布:t:代表每t秒之內(nèi)有這種稀有事件發(fā)生t1:代表每個(gè)任務(wù)在非節(jié)點(diǎn)/機(jī)架處理比在本節(jié)點(diǎn)/機(jī)架處理需要花的時(shí)間多t1秒t2:任務(wù)等待在本節(jié)點(diǎn)/機(jī)架處理的時(shí)間為t2秒T1、T2值的設(shè)定42改進(jìn)算法的詳細(xì)設(shè)計(jì)T1、T2值設(shè)定采用一個(gè)簡(jiǎn)單的數(shù)學(xué)模式來(lái)評(píng)改進(jìn)算法在云計(jì)算仿真平臺(tái)Cloudsim中的仿真實(shí)驗(yàn)性能分析仿真平臺(tái)環(huán)境配置：CloudSim仿真工具軟件包Windows操作系統(tǒng)或linux操作系統(tǒng)1.86GHz以上處理器JDK1.6以上版本Eclipse開(kāi)發(fā)平臺(tái)擴(kuò)展工具

ant1.7.1模擬的Hadoop集群配置：機(jī)架里的主機(jī)數(shù)，虛擬機(jī)數(shù)都盡量參照了EC2部署Hadoop集群的方式機(jī)架虛擬機(jī)/主機(jī)（個(gè)）/（臺(tái)）主機(jī)數(shù)（臺(tái)）虛擬機(jī)數(shù)（個(gè)）機(jī)架12個(gè)/臺(tái)10~10020~2003個(gè)/臺(tái)20~10060~300機(jī)架22個(gè)/臺(tái)10~10020~2003個(gè)/臺(tái)20~10060~300機(jī)架32個(gè)/臺(tái)10~10020~2003個(gè)/臺(tái)20~10060~30043模擬兩個(gè)實(shí)驗(yàn)場(chǎng)景：第一個(gè)實(shí)驗(yàn)場(chǎng)景：沒(méi)有故障的節(jié)點(diǎn)，但是節(jié)點(diǎn)之間有性能差異第二個(gè)實(shí)驗(yàn)場(chǎng)景：設(shè)置集群中有故障節(jié)點(diǎn)的情況改進(jìn)算法在云計(jì)算仿真平臺(tái)Cloudsim中的仿真實(shí)驗(yàn)性能分析實(shí)驗(yàn)結(jié)果分析一：工作響應(yīng)時(shí)間根據(jù)Hadoop集群中一個(gè)數(shù)據(jù)塊的大小，處理任務(wù)的時(shí)間，以及部署集群時(shí)網(wǎng)絡(luò)資源的性能等，設(shè)置了不同的T1、T2值驗(yàn)證工作響應(yīng)時(shí)間，從上圖可以分析出當(dāng)T1=15秒、T2=20秒的情況下任務(wù)的響應(yīng)時(shí)間最佳。44實(shí)驗(yàn)結(jié)果分析一：工作響應(yīng)時(shí)間根據(jù)Hadoop集群中一個(gè)數(shù)據(jù)塊實(shí)驗(yàn)結(jié)果分析一：工作響應(yīng)時(shí)間45對(duì)兩個(gè)場(chǎng)景分別進(jìn)行了模擬實(shí)驗(yàn)，分析證明在沒(méi)有故障節(jié)點(diǎn)的第一個(gè)場(chǎng)景下，改進(jìn)的算法平均工作響應(yīng)時(shí)間依然略高于其它兩個(gè)算法；在第二個(gè)場(chǎng)景中，Hadoop沒(méi)有采用備份任務(wù)推測(cè)執(zhí)行調(diào)度算法的工作響應(yīng)時(shí)間會(huì)明顯大于推測(cè)執(zhí)行算法。實(shí)驗(yàn)結(jié)果分析一：工作響應(yīng)時(shí)間17對(duì)兩個(gè)場(chǎng)景分別進(jìn)行了模擬實(shí)驗(yàn)實(shí)驗(yàn)結(jié)果分析一：工作響應(yīng)時(shí)間46不同Sort工作大小在三種算法下任務(wù)響應(yīng)時(shí)間對(duì)比不同Grep工作大小在三種算法下任務(wù)響應(yīng)時(shí)間對(duì)比響應(yīng)時(shí)間的減少率從30GB的約20%降到了90GB的15%，三個(gè)算法之間的性能差異隨著工作的增大會(huì)越來(lái)越小。實(shí)驗(yàn)結(jié)果分析一：工作響應(yīng)時(shí)間18不同Sort工作大小在三種算實(shí)驗(yàn)結(jié)果分析一：工作響應(yīng)時(shí)間47Sort工作在三種算法下的響應(yīng)時(shí)間Grep工作在三種算法下的響應(yīng)時(shí)間1、最優(yōu)性能：基于數(shù)據(jù)局部性改進(jìn)的LATE算法高于其它兩種算法2、最差性能：改進(jìn)的算法跟LATE算法相差不大3、平均性能：改進(jìn)的算法有著比較明顯的優(yōu)勢(shì)4、不同的工作類(lèi)型在性能表現(xiàn)上的差異：Sort工作使用改進(jìn)后的推測(cè)執(zhí)行算法在性能上會(huì)比其它兩種算法會(huì)有更大程度的改善實(shí)驗(yàn)結(jié)果分析一：工作響應(yīng)時(shí)間19Sort工作在三種算法下的響實(shí)驗(yàn)結(jié)果分析二：任務(wù)本地化處理率分析48為了驗(yàn)證基于數(shù)據(jù)局部性的改進(jìn)算法對(duì)提高本地化處理任務(wù)的作用，設(shè)置了大小不同的工作，輸入數(shù)據(jù)：640MB、3200MB、6400MB。即Map任務(wù)的個(gè)數(shù)分別是10、50、100，集群中機(jī)架數(shù)分別設(shè)置為4個(gè)和10個(gè)。10個(gè)Map任務(wù)時(shí)本節(jié)點(diǎn)/機(jī)架處理率4個(gè)機(jī)架時(shí)本節(jié)點(diǎn)/機(jī)架處理率10個(gè)機(jī)架時(shí)本節(jié)點(diǎn)/機(jī)架處理率實(shí)驗(yàn)結(jié)果分析二：任務(wù)本地化處理率分析20為了驗(yàn)證基于數(shù)據(jù)局部實(shí)驗(yàn)結(jié)果分析二：任務(wù)本地化處理率分析4950個(gè)Map任務(wù)時(shí)本節(jié)點(diǎn)/機(jī)架處理率4個(gè)機(jī)架時(shí)本節(jié)點(diǎn)/機(jī)架處理率10個(gè)機(jī)架時(shí)本節(jié)點(diǎn)/機(jī)架處理率100個(gè)Map任務(wù)時(shí)本節(jié)點(diǎn)/機(jī)架處理率4個(gè)機(jī)架時(shí)本節(jié)點(diǎn)/機(jī)架處理率10個(gè)機(jī)架時(shí)本節(jié)點(diǎn)/機(jī)架處理率實(shí)驗(yàn)結(jié)果分析二：任務(wù)本地化處理率分析2150個(gè)Map任務(wù)時(shí)本50結(jié)論實(shí)驗(yàn)結(jié)果分析二：任務(wù)本地化處理率分析縱向比較，改進(jìn)的LATE算法相對(duì)LATE算法任務(wù)的本地節(jié)點(diǎn)/機(jī)架處理率提高了6%~9%，但相對(duì)Hadoop自帶的算法優(yōu)勢(shì)并不是很明顯。而對(duì)于較大的工作，數(shù)據(jù)局部性改進(jìn)算法的處理優(yōu)勢(shì)沒(méi)有小的工作增加的明顯當(dāng)機(jī)架數(shù)少于等于4個(gè)時(shí)，基本上數(shù)據(jù)塊在不同的機(jī)架存有其副本，任務(wù)本節(jié)點(diǎn)/本機(jī)架處理的概率會(huì)很高，就算沒(méi)有基于數(shù)據(jù)局部性的改進(jìn)算法，任務(wù)推測(cè)執(zhí)行本地化處理的性能也會(huì)比較理想橫向比較，按照集群從小到大的順序，LATE算法任務(wù)本節(jié)點(diǎn)/機(jī)架處理率依次減小從上述三組圖中可以分析出以下結(jié)論：22結(jié)論實(shí)驗(yàn)結(jié)果分析二：任務(wù)本地化處理率分析縱向比較，改進(jìn)的實(shí)驗(yàn)結(jié)果分析三：系統(tǒng)吞吐率分析51從上圖可以分析出基于數(shù)據(jù)局部性的改進(jìn)算法無(wú)論在什么工作類(lèi)型的情形下都能提高系統(tǒng)的吞吐率性能在絕大部分備份執(zhí)行任務(wù)都在本節(jié)點(diǎn)/機(jī)架上處