2023年全國碩士研究生考試考研英語一試題真題(含答案詳解+作文范文)_第1頁
已閱讀1頁,還剩53頁未讀 繼續(xù)免費(fèi)閱讀

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡介

1、Hadoop集群作業(yè)的調(diào)度研究ContentsContents1、Hadoop簡介Hadoop是基于java分布式密集數(shù)據(jù)處理和數(shù)據(jù)分析的軟件框架提供了廉價(jià)的處理大數(shù)據(jù)的可能是開源生態(tài)系統(tǒng),淘寶、騰訊、百度、新浪、facebook、yahoo、amazon、ebay、twitter都在用Hadoop簡介各種業(yè)務(wù)應(yīng)用hiveDBasehadoop的業(yè)界標(biāo)準(zhǔn)核心Hadoop簡介各種業(yè)務(wù)應(yīng)用hiveDBasehadoop的業(yè)界標(biāo)準(zhǔn)核心簡單來說

2、,就是任務(wù)的分解和結(jié)果的合成。MapReduce工作原理MapReduce是用于并行處理大數(shù)據(jù)的軟件框架。計(jì)算機(jī)集群MapReduce工作原理流程如下:任務(wù)①分解小任務(wù)小任務(wù)小任務(wù)?發(fā)送部分信息③傳送反饋部分信息部分信息結(jié)果④整合HDFS架構(gòu)簡介ContentsHadoopMapReduce引擎是由JobTracker和TaskTracker組成,下圖是Hadoop的結(jié)構(gòu)。1、HadoopMapReduce引擎2、MapReduce工作

3、機(jī)制3、Hadoop調(diào)度流程TaskTrackerTaskTrackerTaskTrackerJobTrackerTaskScheduler④assignTasks()⑤tasklist③⑥taskstolauchTask⑦launch③③Client①submitJob()②notifyinitJob()??????????????Hadoop作業(yè)包含一些map任務(wù)和task任務(wù)。這些任務(wù)在集群的節(jié)點(diǎn)的任務(wù)槽(slots)上執(zhí)行。每一

4、個(gè)節(jié)點(diǎn)根據(jù)其計(jì)算資源配置有一系列的map任務(wù)槽和reduce槽,典型入每個(gè)節(jié)點(diǎn)cpu的一個(gè)核當(dāng)作一個(gè)slot。調(diào)度器的任務(wù)就是為任何空閑的slot分配任務(wù)。所有調(diào)度器實(shí)際上均采用了三級(jí)調(diào)度策略,即為空閑的slot依次選擇一個(gè)隊(duì)列、作業(yè)和任務(wù)。隊(duì)列(queue)用戶被劃分到某個(gè)隊(duì)列每個(gè)隊(duì)列分配一定量的資源作業(yè)(job)提交時(shí)間優(yōu)先級(jí)(5個(gè)優(yōu)先級(jí):VERY_HIGHHIGHNMALLOWVERY_LOW)任務(wù)(task)本地性(nodelo

5、cality,racklocality)不同調(diào)度器,采用策略不同不同調(diào)度器,采用策略相同4、Hadoop三級(jí)調(diào)度Contents傳統(tǒng)調(diào)度器:FIFO批處理調(diào)度器FairScheduler多用戶調(diào)度器CapacityScheduler多用戶調(diào)度器新特性調(diào)度器:適用于異構(gòu)負(fù)載的調(diào)度器適用于異構(gòu)集群的調(diào)度器LATE適用于實(shí)時(shí)作業(yè)的調(diào)度器ConstraintbasedSchedulerHadoop現(xiàn)有調(diào)度器最早的HadoopMapReduce計(jì)

6、算架構(gòu)中,JobTracker在進(jìn)行作業(yè)調(diào)度時(shí)使用的是FIFO(FirstInFirstOut)算法。所有用戶的作業(yè)都被提交到一個(gè)隊(duì)列中,然后由JobTracker先按照作業(yè)的優(yōu)先級(jí)高低,再按照作業(yè)提交時(shí)間的先后順序選擇將被執(zhí)行的作業(yè)。FIFO比較簡單,hadoop中只有一個(gè)作業(yè)隊(duì)列,被提交的作業(yè)按照先后順序在作業(yè)隊(duì)列中排隊(duì),新來的作業(yè)插入到隊(duì)尾。一個(gè)作業(yè)運(yùn)行完后,總是從隊(duì)首取下一個(gè)作業(yè)運(yùn)行。這種調(diào)度策略的優(yōu)點(diǎn)是簡單、易于實(shí)現(xiàn),同時(shí)也減

7、輕了jobtracker的負(fù)擔(dān)。但是它的缺點(diǎn)也是顯然的,它對(duì)所有的作業(yè)都一視同仁,沒有考慮到作業(yè)的緊迫程度,另外對(duì)小作業(yè)的運(yùn)行不利。1、FIFO調(diào)度器FIFO調(diào)度器job1按到達(dá)時(shí)間排序,先來先服務(wù)job2job3job4job5job6job7job8maptask0maptask1maptask2reducetask0reducetask1reducetask2maptask3maptask4maptask5job1queueFIF

8、O調(diào)度器job1按到達(dá)時(shí)間排序,先來先服務(wù)job2job3job4job5job6job7job8job12、Fair公平調(diào)度器算法設(shè)計(jì)思想:適用于多用戶情形。當(dāng)集群中由多個(gè)用戶提交作業(yè)時(shí),為了保證公平性,調(diào)度器為每個(gè)用戶或每個(gè)UNIXGroup分配一個(gè)資源池。資源池里的每個(gè)作業(yè)都會(huì)按照其作業(yè)權(quán)重分配最小資源共享量以保證每個(gè)作業(yè)都能得到執(zhí)行而不至于饑餓。當(dāng)集群中的某個(gè)節(jié)點(diǎn)出現(xiàn)空閑的slot時(shí),則選擇目前已獲得的資源量和理論上應(yīng)獲得的資源

9、量的差值最大的作業(yè)來執(zhí)行,以保證公平。主要特點(diǎn):支持多用戶多隊(duì)列:資源公平共享(公平共享量有優(yōu)先級(jí)決定):公平調(diào)度器按照資源池(pool)來組織作業(yè),并把資源公平地分到這些資源池里。默認(rèn)情況下,每個(gè)用戶擁有一個(gè)獨(dú)立的資源池,以使每個(gè)用戶不管提交多少作業(yè)都能獲得一份等同的集群資源量。資源池也可以依據(jù)一定的權(quán)重來獲取相應(yīng)比例的資源份額。資源池實(shí)際上也可以稱為隊(duì)列。保證最小共享量:除公平共享,公平調(diào)度算法還能為資源池設(shè)定其所需的最小共享量,管

10、理員可以給每個(gè)pool配置一個(gè)最小共享量,調(diào)度器在分配資源時(shí),需要保證每個(gè)pool中的作業(yè)獲取該數(shù)目的資源。這樣確保用戶或應(yīng)用程序總能獲取足夠的資源,由此可以提高整個(gè)系統(tǒng)的資源利用率。支持時(shí)間片搶占:公平調(diào)度器支持搶占,如果一個(gè)池在一定時(shí)間內(nèi)未得到公平地資源分配,調(diào)度器就會(huì)終止池中得到過多資源的任務(wù),將集群資源讓給此資源池。限制作業(yè)并發(fā)量,防止中間數(shù)據(jù)塞滿硬盤:公平調(diào)度算法調(diào)度運(yùn)行所有用戶作業(yè),但也可以限定每個(gè)資源池中最大并發(fā)作業(yè)數(shù)和每

11、個(gè)用戶最多提交作業(yè)數(shù)。如果一次性運(yùn)行大作業(yè),會(huì)導(dǎo)致產(chǎn)生過多的中間記錄信息以及過多的上下文切換,這都會(huì)影響到作業(yè)執(zhí)行的性能。超過數(shù)量的作業(yè)將在調(diào)度隊(duì)列中等待,直到一些資源池的早期作業(yè)完成。每個(gè)資源池對(duì)作業(yè)的調(diào)度方式可以配置,支持兩種調(diào)度策略,分別為FIFO和公平調(diào)度。動(dòng)態(tài)調(diào)整各個(gè)資源池的資源量:當(dāng)集群中存在多個(gè)資源池時(shí),某些資源池的資源可能用不了,這時(shí)調(diào)度器會(huì)自動(dòng)將這些資源池中的剩余資源共享給其它所需要的資源池,其它這些資源獲取的共享資源

12、多少主要由資源池權(quán)重決定,權(quán)重越大,獲取的資源越多,一個(gè)資源池的最小共享量加上其獲取的共享資源就是公平共享量。公平調(diào)度器的實(shí)現(xiàn)—基本概念Pool:資源池,或者作業(yè)池。每個(gè)pool里有一定量的資源(CPU、內(nèi)存、網(wǎng)絡(luò)IO,磁盤等,這些由管理員配置),每個(gè)用戶屬于某個(gè)pool,其作業(yè)可使用這個(gè)pool中的資源,可限定每個(gè)pool中最大并發(fā)作業(yè)數(shù)和每個(gè)用戶最多提交作業(yè)數(shù)。默認(rèn)情況下,一個(gè)linux用戶對(duì)應(yīng)一個(gè)pool,而管理員也可以配以一個(gè)l

13、inuxgroup對(duì)應(yīng)一個(gè)pool。pool實(shí)際上也可以稱為group或者隊(duì)列。最小共享量:管理員可給每個(gè)pool配置一個(gè)最小共享量,調(diào)度器在分配資源時(shí),需要保證每個(gè)pool中的作業(yè)至少獲取該數(shù)目的資源。一個(gè)常見的應(yīng)用場(chǎng)景是,對(duì)產(chǎn)品pool設(shè)置最小共享量,而測(cè)試pool不設(shè)置,這樣,當(dāng)可用資源有限時(shí)時(shí),優(yōu)先保證產(chǎn)品pool有資源可用。公平共享量:當(dāng)集群中存在多個(gè)pool時(shí),某些pool中的資源可能用不了,這時(shí)候調(diào)度器會(huì)自動(dòng)將這些pool

14、中剩余的資源共享給其他需要的pool,其他這些pool獲取的共享資源多少主要由其poolweight決定,poolweight越大,獲取的資源越多。一個(gè)pool的最小共享量加上其獲取的共享資源數(shù)目,就是公平共享量。公平調(diào)度器的實(shí)現(xiàn)—算法實(shí)現(xiàn)最簡單的實(shí)現(xiàn)公平共享的方法如下:任何時(shí)候當(dāng)一個(gè)slot空閑時(shí),把它分配給運(yùn)行著最少任務(wù)的資源池。這可以保證所有的pool得到相同數(shù)量的slot,除非這個(gè)pool的需求量(調(diào)度器想要執(zhí)行任務(wù)數(shù),等于已經(jīng)

15、運(yùn)行的任務(wù)數(shù)尚未啟動(dòng)的任務(wù)數(shù))比其得到的公平共享量小,這時(shí),該pool多余的slot將會(huì)分配給其它pool中。下面介紹公平調(diào)度器的兩個(gè)特性,這兩個(gè)特性使得公平共享算法簡單了一些。1、pool的權(quán)重代表了某個(gè)pool能得到slot數(shù)量多少的能力。比如,權(quán)重為2的pool能得到的slot數(shù)量是權(quán)重為1的pool的2倍。2、公平共享量低于其最小共享量的pool優(yōu)先得到空閑的slot比較器對(duì)job或pool首先按照公平共享量低于最小共享量的差額

16、進(jìn)行排序,按照然后再runningTasksweight(jobWeight或poolWeight),再依次掃描隊(duì)列,選擇合適的pool或job。公平調(diào)度器的實(shí)現(xiàn)—公平共享量的計(jì)算方法公平共享量是基于最小共享量和共享資源量計(jì)算得到的,它反映的是某個(gè)pool經(jīng)過資源共享(某些pool的資源用不了,會(huì)自動(dòng)共享給其他pool)之后,一共可以獲取的資源總量,一般會(huì)大于等于最小共享量。如果每個(gè)pool沒有配置最小共享量,且提交了無限量的作業(yè),則讓

17、每個(gè)pool的slotsAssignedweight值相同即可。(其中slotsAssgined表示分配給該pool的slot數(shù),weight表示pool的權(quán)重)。而有了最小共享量minShare和pool中的需求量dem(該pool中所有作業(yè)尚需的slot總數(shù))后,計(jì)算公平共享量fairShare需注意以下兩種情況:(1)某些pool中的最小共享量可能用不完(2)給配給某些pool的資源量小于其最小共享量公平調(diào)度器的實(shí)現(xiàn)—公平共享量的

18、計(jì)算方法考慮到以上兩種情況,調(diào)度器設(shè)計(jì)了基于比率R的公平資源分配方法(設(shè)集群中資源總量為totalSlots):[1]如果一個(gè)pool的demweight,則該pool的fairShare=minShare[3]除此之外,所有pool的fairShare=Rweight[4]所有pool的的fairShare之和應(yīng)為totalSlots通過以上算法計(jì)算出的公平共享量即為“公平調(diào)度器”的“公平”含義之所在,應(yīng)盡量保證每個(gè)pool獲取的資源

19、量為fairshare,如果一定時(shí)間期限內(nèi)達(dá)不到,則搶占資源。關(guān)于這個(gè)R是不是一定滿足條件4,有資料顯示一定存在這個(gè)樣的R。公平調(diào)度器的實(shí)現(xiàn)—調(diào)度流程新版本的Hadoop采用公平調(diào)度器的層次調(diào)度算法,首先選擇一個(gè)pool,然后從該pool中選擇一個(gè)job,最后從該job中選擇一個(gè)locality的task。公平調(diào)度器的實(shí)現(xiàn)—一些特性1.資源搶占當(dāng)一定時(shí)間(管理員可配置)內(nèi),某個(gè)pool中獲取的資源量少于最小共享量,或者公平共享量的一半,

20、則調(diào)度器會(huì)找出哪個(gè)pool搶占了該pool的資源,并殺死相應(yīng)數(shù)量的task以搶占資源。之所以要進(jìn)行搶占,還是為了“公平”,即:保證每個(gè)pool能獲取到它應(yīng)得到的資源。2.delayscheduling機(jī)制當(dāng)出現(xiàn)空閑slot時(shí),如果排在隊(duì)列前面的job對(duì)應(yīng)的所有task均沒有l(wèi)ocality特性,則該作業(yè)會(huì)延遲調(diào)度,直到一段時(shí)間后,該job出現(xiàn)locality的task或者發(fā)生超時(shí),才不得不調(diào)度該job的task。在此解釋下localit

21、y:當(dāng)出現(xiàn)空閑slot時(shí),該slot來自某個(gè)節(jié)點(diǎn),而該節(jié)點(diǎn)上存有部分?jǐn)?shù)據(jù),如果某個(gè)task所需要的數(shù)據(jù)正好位于該節(jié)點(diǎn)上,則將該slot分配給該task是非常好的,因?yàn)樗苊饬送ㄟ^網(wǎng)絡(luò)讀取數(shù)據(jù)。3、計(jì)算能力調(diào)度器CapacityScheduler設(shè)計(jì)思想:支持多個(gè)隊(duì)列,每個(gè)隊(duì)列可配置一定的資源量,每個(gè)隊(duì)列采用FIFO調(diào)度策略,為了防止同一個(gè)用戶的作業(yè)獨(dú)占隊(duì)列中的資源,該調(diào)度器會(huì)對(duì)同一用戶提交的作業(yè)所占資源量進(jìn)行限定。調(diào)度時(shí),首先按以下策略

22、選擇一個(gè)合適隊(duì)列:計(jì)算每個(gè)隊(duì)列中正在運(yùn)行的任務(wù)數(shù)與其應(yīng)該分得的計(jì)算資源之間的比值,選擇一個(gè)該比值最小的隊(duì)列;然后按以下策略選擇該隊(duì)列中一個(gè)作業(yè):按照作業(yè)優(yōu)先級(jí)和提交時(shí)間順序選擇,同時(shí)考慮用戶資源量限制和內(nèi)存限制。特性:(1)計(jì)算能力保證。支持多個(gè)隊(duì)列某個(gè)隊(duì)列可以被提交到某一個(gè)隊(duì)列中。每個(gè)隊(duì)列會(huì)配置一定比例的計(jì)算資源,且所有提交到隊(duì)列中的作業(yè)共享該隊(duì)列中的資源。(2)靈活性??臻e資源會(huì)被分配給那些未到達(dá)資源使用上的隊(duì)列,當(dāng)某個(gè)未到達(dá)資源的

23、隊(duì)列需要資源時(shí),一旦出現(xiàn)空閑資源,便會(huì)分配給它們。(3)支持優(yōu)先級(jí)。隊(duì)列支持作業(yè)優(yōu)先級(jí)調(diào)度(默認(rèn)是FIFO)(4)多重租賃。綜合考慮多種約束防止單個(gè)作業(yè)、用戶或者隊(duì)列獨(dú)占隊(duì)列或集群中的資源。(5)基于資源的調(diào)度。支持資源密集型作業(yè),允許作業(yè)使用的資源量高于默認(rèn)值,進(jìn)而可容納不同資源需求的作業(yè)。不過,當(dāng)前僅支持內(nèi)存資源的調(diào)度CapacityScheduler—涉及到的變量在CapacityScheduler中,存在三種粒度的對(duì)象,分別為:

24、queue、job和task,它們均需要維護(hù)的一些信息:(1)queue維護(hù)的信息@queueName:queue的名稱@ulMin:每個(gè)用戶的可用的最少資源量(所有用戶均相同),需用戶在配置文件中指定@capacityPercent:計(jì)算資源比例,需用戶在配置文件中指定@numJobsByUser:每個(gè)用戶的作業(yè)量,用以跟蹤每個(gè)用戶提交的作業(yè)量,并進(jìn)行數(shù)量的上限限制。該隊(duì)列中map或reducetask的屬性:@capacity:實(shí)際

25、的計(jì)算資源量,這個(gè)隨著tasktracker中slot數(shù)目變化(用戶可能在添加或減少機(jī)器節(jié)點(diǎn))而動(dòng)態(tài)變化,大小為:capacityPercentmapClusterCapacity100@numRunningTasks:正在running的task數(shù)目CapacityScheduler—涉及到的變量@numSlotsOccupied:正在running的task占用的slot總數(shù),注意,在CapacityScheduler中,runni

26、ngtask與slot不一定是一一對(duì)應(yīng)的,每個(gè)task可獲取多個(gè)slot,這主要是因?yàn)樵撜{(diào)度支持內(nèi)存資源調(diào)度,某個(gè)task可能需要多個(gè)slot包含的內(nèi)存量。@numSlotsOccupiedByUser:每個(gè)用戶的作業(yè)占用slot總數(shù),用以限制用戶使用的資源量。(2)job維護(hù)的信息priity:作業(yè)優(yōu)先級(jí),分為五個(gè)等級(jí),從大到小依次為:VERY_HIGH,HIGH,NMAL,LOW,VERY_LOWnumMapTasksnumRedu

27、ceTasks:job的mapreducetask總數(shù)runningMapTasksrunningMapTasks:job正在運(yùn)行的mapreducetask數(shù)finishedMapTasksfinishedReduceTasks:job已完成的mapreducetask數(shù)……(3)task維護(hù)的信息task開始運(yùn)行時(shí)間,當(dāng)前狀態(tài)等CapacityScheduler—調(diào)度算法當(dāng)某個(gè)tasktracker上出現(xiàn)slot時(shí),調(diào)度器依次選擇一

28、個(gè)queue、(選中的queue中的)job、(選中job中的)task,并將該slot分配給該task。下面介紹選擇queue、job和task所采用的策略:(1)選擇queue:將所有queue按照資源使用率(numSlotsOccupiedcapacity)從小到大排序,依次進(jìn)行處理,直到找到一個(gè)合適的job。(2)選擇job:在當(dāng)前queue中,所有作業(yè)按照作業(yè)提交時(shí)間和作業(yè)優(yōu)先級(jí)排序(假設(shè)開啟支持優(yōu)先級(jí)調(diào)度功能,默認(rèn)不支持,需

29、要在配置文件中開啟),調(diào)度依次考慮每個(gè)作業(yè),選擇符合兩個(gè)條件的job:[1]作業(yè)所在的用戶未到達(dá)資源使用上限;[2]該TaskTracker所在的節(jié)點(diǎn)剩余的內(nèi)存足夠該job的task使用。(3)選擇task,同大部分調(diào)度器一樣,考慮task的locality(就近原則)和資源使用情況。即:調(diào)用JobInProgress中的obtainNewMapTask()obtainNewReduceTask()方法)CapacitySchedule

30、r—調(diào)度流程job11按到達(dá)時(shí)間排序,先來先服務(wù)job12job13job15job16job21job22job23job24job25job31job32job33job34job35job36job37queueAqueueBqueueC100slots(20%15)(50%25)(30%25)job14FairSchedulerVSCapacityScheduler(1)相同點(diǎn)均支持多用戶多隊(duì)列,即:適用于多用戶共享集群的應(yīng)用環(huán)

31、境單個(gè)隊(duì)列均支持優(yōu)先級(jí)和FIFO調(diào)度方式均支持資源共享,即某個(gè)queue中的資源有剩余時(shí),可共享給其他缺資源的queue(2)不同點(diǎn)核心調(diào)度策略不同計(jì)算能力調(diào)度器的調(diào)度策略是,先選擇資源利用率低的queue,然后在queue中同時(shí)考慮FIFO和memyconstraint因素;而公平調(diào)度器僅考慮公平,而公平是通過作業(yè)缺額體現(xiàn)的,調(diào)度器每次選擇缺額最大的job(queue的資源量,job優(yōu)先級(jí)等僅用于計(jì)算作業(yè)缺額)。內(nèi)存約束計(jì)算能力調(diào)度器

32、調(diào)度job時(shí)會(huì)考慮作業(yè)的內(nèi)存限制,為了滿足某些特殊job的特殊內(nèi)存需求,可能會(huì)為該job分配多個(gè)slot;而公平調(diào)度器對(duì)這種特殊的job無能為力,只能殺掉這種task。4、異構(gòu)負(fù)載動(dòng)態(tài)調(diào)度器設(shè)計(jì)目標(biāo):異構(gòu)負(fù)載調(diào)度器將問題集中在當(dāng)MapReduce框架中有不同種類負(fù)載時(shí)怎樣提高硬件利用率。作業(yè)按其類型可分為CPU頻繁類型和IO頻繁類型。但目前Hadoop的調(diào)度器(前面的三種調(diào)度器)都沒有考慮到作業(yè)負(fù)載的類型,調(diào)度的策略都是在根據(jù)不同規(guī)則排

33、列的作業(yè)隊(duì)列取隊(duì)首作業(yè)運(yùn)行,這樣會(huì)降低整個(gè)系統(tǒng)的吞吐量。設(shè)計(jì)思想:設(shè)計(jì)一個(gè)三級(jí)隊(duì)列調(diào)度器,包含工作負(fù)載預(yù)測(cè)機(jī)制MRPredict和三個(gè)不同的隊(duì)列,即:CPUBound隊(duì)列,IOBound隊(duì)列和等待隊(duì)列。通過MRPredict機(jī)制自動(dòng)地預(yù)測(cè)到達(dá)的作業(yè)負(fù)載類型并把它們放入不同的隊(duì)列中。每一個(gè)隊(duì)列獨(dú)立地按照FCFS調(diào)度策略工作。異構(gòu)負(fù)載動(dòng)態(tài)調(diào)度器的設(shè)計(jì)實(shí)現(xiàn)1、定義變量:MOD:MapOutData,map端輸出數(shù)據(jù)量:MapInData,ma

34、p端輸入數(shù)據(jù)量SOD:ShuffleOutData,Shuffle端輸出數(shù)據(jù)量SID:ShuffleInData,Shuffle端輸入數(shù)據(jù)量n:某個(gè)節(jié)點(diǎn)中正在并發(fā)執(zhí)行任務(wù)的個(gè)數(shù)MICT:MapTaskCompletedTime,Map任務(wù)完成所需時(shí)間DI:磁盤IO傳輸速率:參數(shù),保證:MOD=異構(gòu)負(fù)載動(dòng)態(tài)調(diào)度器的設(shè)計(jì)實(shí)現(xiàn)2、分類規(guī)則:如果滿足下列條件,則將該作業(yè)標(biāo)記為CPUBound類如果滿足下列條件,則將該作業(yè)標(biāo)記為Sway隊(duì)列類如果

35、滿足下列條件,則將該作業(yè)標(biāo)記為IOBound類假設(shè)每一個(gè)reducer有相同大小的數(shù)據(jù)輸入,則SID與集群的分布有關(guān)。每個(gè)節(jié)點(diǎn)的SID取決于該節(jié)點(diǎn)運(yùn)行的reducer和整個(gè)集群中的reducer的比例,計(jì)算如下:異構(gòu)負(fù)載動(dòng)態(tài)調(diào)度器的設(shè)計(jì)實(shí)現(xiàn)3、設(shè)計(jì)實(shí)現(xiàn):(1)MRPredict機(jī)制假設(shè)一個(gè)job的任務(wù)有相同的特點(diǎn),即可以通過該任務(wù)已經(jīng)執(zhí)行的task的信息來預(yù)測(cè)其它任務(wù)的行為。當(dāng)在一個(gè)節(jié)點(diǎn)有空閑的slot時(shí),調(diào)度器將會(huì)指定一個(gè)map任務(wù),

36、當(dāng)這些map任務(wù)完成時(shí),可以計(jì)算出MICT、和MOD,然后根據(jù)下面的分類規(guī)則可將作業(yè)分為三種類型。異構(gòu)負(fù)載動(dòng)態(tài)調(diào)度器的設(shè)計(jì)實(shí)現(xiàn)(2)調(diào)度策略當(dāng)一個(gè)新作業(yè)到達(dá)時(shí),將會(huì)暫時(shí)被放到等待隊(duì)列中以確定其負(fù)載類型。然后調(diào)度器將該作業(yè)一個(gè)Map任務(wù)分配到每一個(gè)TaskTracker上(改作業(yè)稱為testruntask)。如下圖1示,如果CPUBound和IOBound兩個(gè)隊(duì)列當(dāng)時(shí)均為空,則等待隊(duì)列的隊(duì)首作業(yè)將會(huì)被移動(dòng)到任意一個(gè)隊(duì)列中,然后調(diào)度執(zhí)行直至

37、改作業(yè)的負(fù)載類型被確定。然后,如果發(fā)現(xiàn)該作業(yè)被移到了錯(cuò)誤的隊(duì)列,則將其移動(dòng)到正確的隊(duì)列。每個(gè)隊(duì)列調(diào)度作業(yè)時(shí)采用FCFS策略。5、LATE—適用于異構(gòu)集群的調(diào)度器(1)現(xiàn)有Hadoop調(diào)度器的缺陷:現(xiàn)有的Hadoop調(diào)度器都是建立在同構(gòu)集群的假設(shè)前提下,具體假設(shè)如下:1)集群中各個(gè)節(jié)點(diǎn)的性能完全一樣2)對(duì)于reducetask,它的三個(gè)階段:copy、st和reduce,用時(shí)各占133)同一job的同類型的task是一批一批完成的,他們用

38、時(shí)基本一樣。現(xiàn)有的Hadoop調(diào)度器存在較大缺陷,主要體現(xiàn)在探測(cè)落后任務(wù)的算法上:如果一個(gè)task的進(jìn)度落后于同類型task進(jìn)度的20%,則把該task當(dāng)做落后任務(wù)(這種任務(wù)決定了job的完成時(shí)間,需盡量縮短它的執(zhí)行時(shí)間),從而為它啟動(dòng)一個(gè)備份任務(wù)(speculativetask)。如果集群異構(gòu)的,對(duì)于同一個(gè)task,即使是在相同節(jié)點(diǎn)上的執(zhí)行時(shí)間也會(huì)有較大差別,因而在異構(gòu)集群中很容易產(chǎn)生大量的備份任務(wù)。(2)傳統(tǒng)的調(diào)度器調(diào)度推測(cè)性任務(wù)的

39、策略為了選擇一個(gè)推測(cè)式任務(wù),Hadoop監(jiān)視器維護(hù)一個(gè)變量:進(jìn)度得分。對(duì)于一個(gè)map任務(wù),這個(gè)得分等于已經(jīng)輸入數(shù)據(jù)占整個(gè)輸入數(shù)據(jù)的比例;對(duì)于一個(gè)reduce任務(wù),由于執(zhí)行被分成了下面三部分,則每一部分占據(jù)該分值的13.1)拷貝階段,此時(shí)任務(wù)正在所有map任務(wù)的輸出。分值等于已經(jīng)拷貝的map輸出數(shù)據(jù)的比例;2)排序階段,此時(shí)所有map任務(wù)的輸出正在按key值排序。分值等于數(shù)據(jù)合并的比例;3)reduce階段,此時(shí)一個(gè)用戶自定義的reduc

40、e函數(shù)正在處理map的輸出結(jié)果。分值等于reduce函數(shù)已經(jīng)處理數(shù)據(jù)的比例。Hadoop定義一個(gè)閾值(threshold),當(dāng)某一個(gè)任務(wù)至少執(zhí)行了1分鐘且進(jìn)度得分小于該閾值0.2時(shí),該任務(wù)就被標(biāo)定位落后任務(wù)。(3)LATE的設(shè)計(jì)思想:主要用來調(diào)度探測(cè)性任務(wù)。與傳統(tǒng)調(diào)度器不同的是,LATE會(huì)對(duì)運(yùn)行的慢的任務(wù)賦予權(quán)值并按照權(quán)值執(zhí)行一部分的探測(cè)性任務(wù)。在選擇執(zhí)行探測(cè)性任務(wù)的節(jié)點(diǎn)時(shí),選擇“最快”的節(jié)點(diǎn)來執(zhí)行。而且,LATE會(huì)規(guī)定探測(cè)性任務(wù)的最大

41、值以防止系統(tǒng)顛簸。(4)定義變量SpeculativeCap:系統(tǒng)中最大同時(shí)執(zhí)行的speculativetask數(shù)目(推薦值為總slot數(shù)的10%);SlowNodeThreshold:標(biāo)志節(jié)點(diǎn)快慢的閾值,調(diào)度得分低于該閾值的node(慢節(jié)點(diǎn))上不會(huì)啟動(dòng)speculativetask(推薦值為25%);SlowTaskThreshold:標(biāo)志是否為該任務(wù)啟動(dòng)推測(cè)性任務(wù)的閾值,當(dāng)task進(jìn)度低于同批同類task的平均進(jìn)度的SlowTask

42、Threshold時(shí),會(huì)為該task啟動(dòng)speculativetask(推薦值為25%)。TimeLeft:任務(wù)的剩余時(shí)間,計(jì)算公式為(1進(jìn)度得分)執(zhí)行比,其中執(zhí)行比=進(jìn)度得分執(zhí)行時(shí)間。(5)調(diào)度策略如果當(dāng)前有一個(gè)空閑的slot并且系統(tǒng)中的推測(cè)性任務(wù)的個(gè)數(shù)小于SpeculativeCap,則按下面策略調(diào)度推測(cè)性任務(wù)。1)如果該節(jié)點(diǎn)是慢節(jié)點(diǎn)(節(jié)點(diǎn)得分低于SlowNodeThreshold),則忽略這個(gè)請(qǐng)求;(2)對(duì)當(dāng)前正在運(yùn)行的task按

43、估算的剩余完成時(shí)間(TimeLeft)排序;(3)選擇剩余完成時(shí)間最大且進(jìn)度低于SlowTaskThreshold的task,為該task啟動(dòng)備份任務(wù)。6、ConstraintbasedScheduler–實(shí)時(shí)調(diào)度器設(shè)計(jì)目標(biāo):這種調(diào)度器集中處理如何滿足用戶的時(shí)間需求上。其設(shè)計(jì)目標(biāo)有兩個(gè):(1)能夠給用戶及時(shí)的反饋,告訴用戶所提交的某項(xiàng)工作是否可以在其規(guī)定的Deadline內(nèi)完成。如果能完成,則反饋給用戶可以執(zhí)行的信號(hào);否則,告訴用戶需要

44、修改Deadline后再次提交數(shù)據(jù)。(2)在滿足所有實(shí)時(shí)作業(yè)需求的同時(shí)能保證可同時(shí)運(yùn)行的作業(yè)達(dá)到最大量。設(shè)計(jì)思想:(1)綜合考慮影響作業(yè)完成時(shí)間的變量,例如map和reduce運(yùn)行時(shí),map和reduce輸入數(shù)據(jù)大小,數(shù)據(jù)的分布情況等等,建立一個(gè)作業(yè)執(zhí)行代價(jià)模型。(2)根據(jù)建立的作業(yè)執(zhí)行代價(jià)模型,并把用戶的Deadline要求作為輸入的一部分考慮進(jìn)去來確定某一作業(yè)的可調(diào)度性。只有作業(yè)明確要求的Deadline能被滿足時(shí),改作業(yè)才能被調(diào)度

45、。一般的調(diào)度算法考慮的是系統(tǒng)中所有作業(yè)的運(yùn)行情況,該算法考慮的是當(dāng)前時(shí)間空閑slot的個(gè)數(shù)。ConstraintbasedScheduler的設(shè)計(jì)實(shí)現(xiàn)1、Deadline估計(jì)模型(1)定義變量::一個(gè)查詢,是查詢的到來時(shí)間,是輸入數(shù)據(jù)大小,是相關(guān)的最終期限:由查詢對(duì)應(yīng)的Hadoop的一個(gè)作業(yè)。是第個(gè)map任務(wù),是第個(gè)reduce任務(wù),其中,。作業(yè)的到達(dá)時(shí)間、輸入數(shù)據(jù)大小和最終期限如所示:集群中分配給該工作的所有slot數(shù)目。,其中,是m

46、ap任務(wù)的slot數(shù),是reduce任務(wù)的slot數(shù):map數(shù)據(jù)分布向量,其中是作業(yè)的map任務(wù)的總數(shù)。是分配給第個(gè)map任務(wù)的數(shù)據(jù)的比例。由于map數(shù)據(jù)是平均分配給各個(gè)map節(jié)點(diǎn)上的,所以。:過濾比,即map任務(wù)輸出端數(shù)據(jù)和輸入端數(shù)據(jù)的比值,一般情況下:reduce任務(wù)輸出端的數(shù)據(jù)量:map任務(wù)處理單元數(shù)據(jù)的時(shí)間:reduce任務(wù)處理單元數(shù)據(jù)的時(shí)間:轉(zhuǎn)換單元數(shù)據(jù)的通信時(shí)間:作業(yè)第一個(gè)map任務(wù)的開始時(shí)間:作業(yè)第一個(gè)reduce任務(wù)的開

47、始時(shí)間:作業(yè)能被調(diào)度的map任務(wù)需被滿足的最小數(shù):作業(yè)能被調(diào)度的reduce任務(wù)需被滿足的最小數(shù)(2)計(jì)算過程為了計(jì)算作業(yè)的持續(xù)時(shí)間,考慮map階段的計(jì)算時(shí)間,reduce階段的計(jì)算時(shí)間和reduce的拷貝階段數(shù)據(jù)轉(zhuǎn)換時(shí)間。因此,作業(yè)的持續(xù)時(shí)間可以表述如下:由于作業(yè)有一個(gè)到達(dá)時(shí)間和最后期限,因此設(shè)reduce任務(wù)開始的最大時(shí)間,則:所以,因此,(3)調(diào)度過程調(diào)度器維護(hù)一個(gè)按照Deadline排序的優(yōu)先隊(duì)列,任務(wù)調(diào)度從隊(duì)首作業(yè)開始。如果當(dāng)

48、前作業(yè)的需求不能被滿足,則考慮下一個(gè)作業(yè),直至隊(duì)列中沒有作業(yè)或者TaskTracker中沒有可用的slot為止。1)當(dāng)一個(gè)作業(yè)到達(dá)時(shí),首先根據(jù)上面公式計(jì)算如果當(dāng)前可用的slot數(shù)量小于,則作業(yè)被拒絕。否則,進(jìn)行第二步;2)根據(jù)為該作業(yè)指定的所有reduce的數(shù)量(一般由用戶指定或者設(shè)為默認(rèn)值)來計(jì)算。如果在時(shí)刻系統(tǒng)可用的slot數(shù)量小于該作業(yè)指定的所有reduce的數(shù)量,則仍然拒絕該作業(yè)。否則轉(zhuǎn)入第三步;3)如果作業(yè)被調(diào)度且所有map階

49、段的工作已經(jīng)完成,則計(jì)算來確定多少個(gè)reduce任務(wù)能被調(diào)度。(3)調(diào)度過程調(diào)度器維護(hù)一個(gè)按照Deadline排序的優(yōu)先隊(duì)列,任務(wù)調(diào)度從隊(duì)首作業(yè)開始。如果當(dāng)前作業(yè)的需求不能被滿足,則考慮下一個(gè)作業(yè),直至隊(duì)列中沒有作業(yè)或者TaskTracker中沒有可用的slot為止。1)當(dāng)一個(gè)作業(yè)到達(dá)時(shí),首先根據(jù)上面公式計(jì)算如果當(dāng)前可用的slot數(shù)量小于,則作業(yè)被拒絕。否則,進(jìn)行第二步;2)根據(jù)為該作業(yè)指定的所有reduce的數(shù)量(一般由用戶指定或者設(shè)

50、為默認(rèn)值)來計(jì)算。如果在時(shí)刻系統(tǒng)可用的slot數(shù)量小于該作業(yè)指定的所有reduce的數(shù)量,則仍然拒絕該作業(yè)。否則轉(zhuǎn)入第三步;3)如果作業(yè)被調(diào)度且所有map階段的工作已經(jīng)完成,則計(jì)算來確定多少個(gè)reduce任務(wù)能被調(diào)度。Contents如何編寫自己的Hadoop調(diào)度器步驟1編寫JobInProgressListener步驟2編寫調(diào)度器類,繼承抽象類TaskScheduler步驟3配置并啟用Hadoop調(diào)度器編寫自己的JobInProgre

51、ssListener抽象類abstractclassJobInProgressListenerpublicabstractvoidjobAdded(JobInProgressjob)throwsIOExceptionpublicabstractvoidjobRemoved(JobInProgressjob)publicabstractvoidjobUpdated(JobChangeEventevent)編寫JobInProgressLi

52、stenerwriteyourownlistenerclassMyJobListenerextendsJobInProgressListenerprivateListjobQueue=newArrayList()publicvoidjobAdded(JobInProgressjob)synchronized(jobQueue)jobQueue.add(job)將Job添加到隊(duì)列中tt.initJob(job)初始化jobstJobs()

53、對(duì)所有作業(yè)進(jìn)行排序publicvoidjobRemoved(JobInProgressjob)synchronized(jobQueue)jobQueue.remove(job)……編寫調(diào)度器類abstractclassTaskSchedulerimplementsConfigurablepublicsynchronizedvoidsetTaskTrackerManager(TaskTrackerManagertaskTrackerMa

54、nager)this.taskTrackerManager=taskTrackerManagerpublicabstractListassignTasks(TaskTrackerStatustaskTracker)throwsIOException……實(shí)際上就是JobTracker對(duì)象?。。axMapTasks:mapslot數(shù)目上限maxReduceTasks:reduceslot數(shù)目上限totalVirtualMemy:總的虛擬內(nèi)

55、存totalPhysicalMemy:總的物理內(nèi)存availableSpace:可用磁盤空間ListtaskRepts:每個(gè)Task運(yùn)行狀況編寫調(diào)度器類publicclassMySchedulerextendsTaskSchedulerprivateMyJobListenermyJobListenerpublicvoidstart()this.myJobListener=newMyJobListener()myJobListener.s

56、etTaskTrackerManager(taskTrackerManager)taskTrackerManager.addJobInProgressListener(myJobListener)publicsynchronizedListassignTasks(TaskTrackerStatustracker)throwsIOExceptionif(myJobListener.getJobs().size()0)JobInProgre

57、ssjob=myJobListener.getJobs().get(0)returnjob.obtainNewMapTask(…)配置并啟用Hadoop調(diào)度器(1)在mapredsite.xml中配置mapred.jobtracker.taskSchedulerg.apache.hadoop.mapred.MyScheduler(2)重新啟動(dòng)mapreduce或者jobtrackerbinstartmapred.shbinhadoopd

58、aemon.shstartjobtrackerContents展望由于Hadoop使用了唯一的JobTracker進(jìn)行作業(yè)調(diào)度的HadoopMapReduce計(jì)算架構(gòu)而言,大量用戶提交的大量作業(yè)以及大規(guī)模的TaskTracker分布必將給JobTracker帶來繁重的工作壓力,因此在其上運(yùn)行的調(diào)度算法一定不能過于復(fù)雜,這也是為什么FIFO算法始終還沒有被遺棄的原因之一。當(dāng)前,HadoopMapReduce的這一結(jié)構(gòu)特征已經(jīng)成為研究領(lǐng)域爭(zhēng)

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 眾賞文庫僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。

評(píng)論

0/150

提交評(píng)論