Hadoop集群作業(yè)的調(diào)度研究

Hadoop集群作業(yè)的調(diào)度研究ContentsHadoop和MapReduce簡介1

Hadoop的集群作業(yè)調(diào)度原理2如何編寫自己的Hadoop調(diào)度器4

結(jié)論與展望5

Hadoop的集群作業(yè)調(diào)度算法3ContentsHadoop和MapReduce簡介1

Hadoop的集群作業(yè)調(diào)度原理2如何編寫自己的Hadoop調(diào)度器4

結(jié)論與展望5

Hadoop的集群作業(yè)調(diào)度算法3

1、Hadoop簡介

Hadoop是基于java分布式密集數(shù)據(jù)處理和數(shù)據(jù)分析的軟件框架

提供了廉價(jià)的處理大數(shù)據(jù)的可能

是開源生態(tài)系統(tǒng)，淘寶、騰訊、百度、新浪、facebook、yahoo、amazon、ebay、twitter都在用Hadoop簡介各種業(yè)務(wù)應(yīng)用hiveDBaseMapReduceHDFShadoop的業(yè)界標(biāo)準(zhǔn)核心Hadoop簡介各種業(yè)務(wù)應(yīng)用hiveDBaseMapReduceHDFShadoop的業(yè)界標(biāo)準(zhǔn)核心

簡單來說，就是任務(wù)的分解和結(jié)果的合成。

MapReduce工作原理

MapReduce是用于并行處理大數(shù)據(jù)的軟件框架。計(jì)算機(jī)集群

MapReduce工作原理

流程如下：任務(wù)①分解小任務(wù)小任務(wù)小任務(wù)發(fā)送部分信息③傳送反饋部分信息部分信息結(jié)果④整合HDFS架構(gòu)簡介ContentsHadoop和MapReduce簡介1

Hadoop的集群作業(yè)調(diào)度原理2如何編寫自己的Hadoop調(diào)度器4

結(jié)論與展望5

Hadoop的集群作業(yè)調(diào)度算法3HadoopMapReduce引擎是由JobTracker和TaskTracker組成，下圖是Hadoop的結(jié)構(gòu)。1、HadoopMapReduce引擎2、MapReduce工作機(jī)制3、Hadoop調(diào)度流程TaskTrackerTaskTrackerTaskTrackerJobTrackerTaskScheduler④assignTasks()⑤tasklist③<TaskTrackerStatus,askForNewTask>⑥tasks-to-lauchTask⑦launch③③Client①submitJob()②notifyinitJob()？？？？？？？？？？？？？？

Hadoop作業(yè)包含一些map任務(wù)和task任務(wù)。這些任務(wù)在集群的節(jié)點(diǎn)的任務(wù)槽(slots)上執(zhí)行。每一個(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í)際上均采用了三級調(diào)度策略，即為空閑的slot依次選擇一個(gè)隊(duì)列、作業(yè)和任務(wù)。隊(duì)列（queue）用戶被劃分到某個(gè)隊(duì)列每個(gè)隊(duì)列分配一定量的資源作業(yè)（job）提交時(shí)間優(yōu)先級（5個(gè)優(yōu)先級：VERY_HIGH,HIGH,NORMAL,LOW,VERY_LOW）任務(wù)（task）本地性（nodelocality，racklocality）不同調(diào)度器，采用策略不同不同調(diào)度器，采用策略相同4、Hadoop三級調(diào)度ContentsHadoop和MapReduce簡介1

Hadoop的集群作業(yè)調(diào)度原理2如何編寫自己的Hadoop調(diào)度器4

結(jié)論與展望5

Hadoop的集群作業(yè)調(diào)度算法3傳統(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)度器Constraint-basedScheduler

Hadoop現(xiàn)有調(diào)度器

最早的HadoopMap/Reduce計(jì)算架構(gòu)中，JobTracker在進(jìn)行作業(yè)調(diào)度時(shí)使用的是FIFO(FirstInFirstOut)算法。所有用戶的作業(yè)都被提交到一個(gè)隊(duì)列中，然后由JobTracker先按照作業(yè)的優(yōu)先級高低，再按照作業(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í)也減輕了jobtracker的負(fù)擔(dān)。但是它的缺點(diǎn)也是顯然的，它對所有的作業(yè)都一視同仁，沒有考慮到作業(yè)的緊迫程度，另外對小作業(yè)的運(yùn)行不利。1、FIFO調(diào)度器FIFO調(diào)度器job1按到達(dá)時(shí)間排序，先來先服務(wù)job2job3job4job5job6job7job8maptask0maptask1maptask2reducetask0reducetask1reducetask2maptask3maptask4maptask5job1queue<hasafreeslot><returnanewtask>FIFO調(diào)度器job1按到達(dá)時(shí)間排序，先來先服務(wù)job2job3job4job5job6job7job8maptask1failedTasksmaptask0localitytasksmaptask3non-localitytasksmaptask2maptask4speculativetasksmaptask5job1reducetask0nonRunningReducesreducetask1speculativetasksreducetask22、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)獲得的資源量的差值最大的作業(yè)來執(zhí)行，以保證公平。主要特點(diǎn)：支持多用戶多隊(duì)列：資源公平共享（公平共享量有優(yōu)先級決定）：公平調(diào)度器按照資源池（pool）來組織作業(yè)，并把資源公平地分到這些資源池里。默認(rèn)情況下，每個(gè)用戶擁有一個(gè)獨(dú)立的資源池，以使每個(gè)用戶不管提交多少作業(yè)都能獲得一份等同的集群資源量。資源池也可以依據(jù)一定的權(quán)重來獲取相應(yīng)比例的資源份額。資源池實(shí)際上也可以稱為隊(duì)列。保證最小共享量：除公平共享，公平調(diào)度算法還能為資源池設(shè)定其所需的最小共享量，管理員可以給每個(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ù)和每個(gè)用戶最多提交作業(yè)數(shù)。如果一次性運(yùn)行大作業(yè)，會(huì)導(dǎo)致產(chǎn)生過多的中間記錄信息以及過多的上下文切換，這都會(huì)影響到作業(yè)執(zhí)行的性能。超過數(shù)量的作業(yè)將在調(diào)度隊(duì)列中等待，直到一些資源池的早期作業(yè)完成。每個(gè)資源池對作業(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)將這些資源池中的剩余資源共享給其它所需要的資源池，其它這些資源獲取的共享資源多少主要由資源池權(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用戶對應(yīng)一個(gè)pool，而管理員也可以配以一個(gè)linuxgroup對應(yīng)一個(gè)pool。pool實(shí)際上也可以稱為group或者隊(duì)列。

最小共享量：管理員可給每個(gè)pool配置一個(gè)最小共享量，調(diào)度器在分配資源時(shí)，需要保證每個(gè)pool中的作業(yè)至少獲取該數(shù)目的資源。一個(gè)常見的應(yīng)用場景是，對產(chǎn)品pool設(shè)置最小共享量，而測試pool不設(shè)置，這樣，當(dāng)可用資源有限時(shí)時(shí)，優(yōu)先保證產(chǎn)品pool有資源可用。公平共享量：當(dāng)集群中存在多個(gè)pool時(shí)，某些pool中的資源可能用不了，這時(shí)候調(diào)度器會(huì)自動(dòng)將這些pool中剩余的資源共享給其他需要的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)運(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比較器對job或pool首先按照公平共享量低于最小共享量的差額進(jìn)行排序，按照然后再runningTasks/weight（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è)，則讓每個(gè)pool的slotsAssigned/weight值相同即可。（其中slotsAssgined表示分配給該pool的slot數(shù)，weight表示pool的權(quán)重）。而有了最小共享量minShare和pool中的需求量demand（該pool中所有作業(yè)尚需的slot總數(shù)）后，計(jì)算公平共享量fairShare需注意以下兩種情況：（1）某些pool中的最小共享量可能用不完（2）給配給某些pool的資源量小于其最小共享量

公平調(diào)度器的實(shí)現(xiàn)—公平共享量的計(jì)算方法考慮到以上兩種情況，調(diào)度器設(shè)計(jì)了基于比率R的公平資源分配方法（設(shè)集群中資源總量為totalSlots）：[1]如果一個(gè)pool的demand<R*weight，則該pool的fairShare=demand[2]如果一個(gè)pool的minShare>weight，則該pool的fairShare=minShare[3]除此之外，所有pool的fairShare=R*weight[4]所有pool的的fairShare之和應(yīng)為totalSlots

通過以上算法計(jì)算出的公平共享量即為“公平調(diào)度器”的“公平”含義之所在，應(yīng)盡量保證每個(gè)pool獲取的資源量為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中獲取的資源量少于最小共享量，或者公平共享量的一半，則調(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對應(yīng)的所有task均沒有l(wèi)ocality特性，則該作業(yè)會(huì)延遲調(diào)度，直到一段時(shí)間后，該job出現(xiàn)locality的task或者發(fā)生超時(shí)，才不得不調(diào)度該job的task。在此解釋下locality：當(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ì)對同一用戶提交的作業(yè)所占資源量進(jìn)行限定。調(diào)度時(shí)，首先按以下策略選擇一個(gè)合適隊(duì)列：計(jì)算每個(gè)隊(duì)列中正在運(yùn)行的任務(wù)數(shù)與其應(yīng)該分得的計(jì)算資源之間的比值，選擇一個(gè)該比值最小的隊(duì)列；然后按以下策略選擇該隊(duì)列中一個(gè)作業(yè)：按照作業(yè)優(yōu)先級和提交時(shí)間順序選擇，同時(shí)考慮用戶資源量限制和內(nèi)存限制。特性:（1）計(jì)算能力保證。支持多個(gè)隊(duì)列某個(gè)隊(duì)列可以被提交到某一個(gè)隊(duì)列中。每個(gè)隊(duì)列會(huì)配置一定比例的計(jì)算資源，且所有提交到隊(duì)列中的作業(yè)共享該隊(duì)列中的資源。（2）靈活性。空閑資源會(huì)被分配給那些未到達(dá)資源使用上的隊(duì)列，當(dāng)某個(gè)未到達(dá)資源的隊(duì)列需要資源時(shí)，一旦出現(xiàn)空閑資源，便會(huì)分配給它們。（3）支持優(yōu)先級。隊(duì)列支持作業(yè)優(yōu)先級調(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中，存在三種粒度的對象，分別為：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í)際的計(jì)算資源量，這個(gè)隨著tasktracker中slot數(shù)目變化（用戶可能在添加或減少機(jī)器節(jié)點(diǎn)）而動(dòng)態(tài)變化，大小為：capacityPercent*mapClusterCapacity/100@numRunningTasks：正在running的task數(shù)目CapacityScheduler—涉及到的變量@numSlotsOccupied：正在running的task占用的slot總數(shù)，注意，在CapacityScheduler中，runningtask與slot不一定是一一對應(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ù)的信息priority：作業(yè)優(yōu)先級，分為五個(gè)等級，從大到小依次為：VERY_HIGH，HIGH，NORMAL，LOW，VERY_LOW;numMapTasks/numReduceTasks

：job的map/reducetask總數(shù)runningMapTasks/runningMapTasks：job正在運(yùn)行的map/reducetask數(shù)finishedMapTasks/finishedReduceTasks：job已完成的map/reducetask數(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)度器依次選擇一個(gè)

queue、（選中的queue中的）job、（選中job中的）task，并將該slot分配給該task。下面介紹選擇queue、job和task所采用的策略：（1）選擇queue：將所有queue按照資源使用率（numSlotsOccupied/capacity）從小到大排序，依次進(jìn)行處理，直到找到一個(gè)合適的job。（2）選擇job：在當(dāng)前queue中，所有作業(yè)按照作業(yè)提交時(shí)間和作業(yè)優(yōu)先級排序（假設(shè)開啟支持優(yōu)先級調(diào)度功能，默認(rèn)不支持，需要在配置文件中開啟），調(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()方法）

CapacityScheduler—調(diào)度流程

job11按到達(dá)時(shí)間排序，先來先服務(wù)job12job13job15job16job21job22job23job24job25job31job32job33job34job35job36job37queueAqueueBqueueC100slots(20%,15)(50%,25)(30%,25)job14FairSchedulerVSCapacityScheduler（1）相同點(diǎn)均支持多用戶多隊(duì)列，即：適用于多用戶共享集群的應(yīng)用環(huán)境單個(gè)隊(duì)列均支持優(yōu)先級和FIFO調(diào)度方式均支持資源共享，即某個(gè)queue中的資源有剩余時(shí)，可共享給其他缺資源的queue（2）不同點(diǎn)

核心調(diào)度策略不同

計(jì)算能力調(diào)度器的調(diào)度策略是，先選擇資源利用率低的queue，然后在queue中同時(shí)考慮FIFO和memoryconstraint因素；而公平調(diào)度器僅考慮公平，而公平是通過作業(yè)缺額體現(xiàn)的，調(diào)度器每次選擇缺額最大的job（queue的資源量，job優(yōu)先級等僅用于計(jì)算作業(yè)缺額）。內(nèi)存約束

計(jì)算能力調(diào)度器調(diào)度job時(shí)會(huì)考慮作業(yè)的內(nèi)存限制，為了滿足某些特殊job的特殊內(nèi)存需求，可能會(huì)為該job分配多個(gè)slot；而公平調(diào)度器對這種特殊的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ī)則排列的作業(yè)隊(duì)列取隊(duì)首作業(yè)運(yùn)行，這樣會(huì)降低整個(gè)系統(tǒng)的吞吐量。設(shè)計(jì)思想：

設(shè)計(jì)一個(gè)三級隊(duì)列調(diào)度器，包含工作負(fù)載預(yù)測機(jī)制MR-Predict和三個(gè)不同的隊(duì)列，即：CPU-Bound隊(duì)列，I/O-Bound隊(duì)列和等待隊(duì)列。通過MR-Predict機(jī)制自動(dòng)地預(yù)測到達(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ù)量

MID：MapInData，map端輸入數(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í)間

DIOR：磁盤IO傳輸速率：參數(shù)，保證：MOD=*MID異構(gòu)負(fù)載動(dòng)態(tài)調(diào)度器的設(shè)計(jì)實(shí)現(xiàn)2、分類規(guī)則：如果滿足下列條件，則將該作業(yè)標(biāo)記為CPU-Bound類如果滿足下列條件，則將該作業(yè)標(biāo)記為Sway隊(duì)列類如果滿足下列條件，則將該作業(yè)標(biāo)記為I/O-Bound類假設(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）MR-Predict機(jī)制假設(shè)一個(gè)job的任務(wù)有相同的特點(diǎn)，即可以通過該任務(wù)已經(jīng)執(zhí)行的task的信息來預(yù)測其它任務(wù)的行為。當(dāng)在一個(gè)節(jié)點(diǎn)有空閑的slot時(shí)，調(diào)度器將會(huì)指定一個(gè)map任務(wù)，當(dāng)這些map任務(wù)完成時(shí)，可以計(jì)算出MICT、MID和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è)稱為test-runtask）。如下圖1示，如果CPU-Bound和I/O-Bound兩個(gè)隊(duì)列當(dāng)時(shí)均為空，則等待隊(duì)列的隊(duì)首作業(yè)將會(huì)被移動(dòng)到任意一個(gè)隊(duì)列中，然后調(diào)度執(zhí)行直至改作業(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）對于reducetask，它的三個(gè)階段：copy、sort和reduce，用時(shí)各占1/33）同一job的同類型的task是一批一批完成的，他們用時(shí)基本一樣。

現(xiàn)有的Hadoop調(diào)度器存在較大缺陷，主要體現(xiàn)在探測落后任務(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)的，對于同一個(gè)task，即使是在相同節(jié)點(diǎn)上的執(zhí)行時(shí)間也會(huì)有較大差別，因而在異構(gòu)集群中很容易產(chǎn)生大量的備份任務(wù)。（2）傳統(tǒng)的調(diào)度器調(diào)度推測性任務(wù)的策略為了選擇一個(gè)推測式任務(wù)，Hadoop監(jiān)視器維護(hù)一個(gè)變量：進(jìn)度得分。對于一個(gè)map任務(wù)，這個(gè)得分等于已經(jīng)輸入數(shù)據(jù)占整個(gè)輸入數(shù)據(jù)的比例；對于一個(gè)reduce任務(wù)，由于執(zhí)行被分成了下面三部分，則每一部分占據(jù)該分值的1/3.1）拷貝階段，此時(shí)任務(wù)正在所有map任務(wù)的輸出。分值等于已經(jīng)拷貝的map輸出數(shù)據(jù)的比例；

2）排序階段，此時(shí)所有map任務(wù)的輸出正在按key值排序。分值等于數(shù)據(jù)合并的比例；

3）reduce階段，此時(shí)一個(gè)用戶自定義的reduce函數(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)度探測性任務(wù)。與傳統(tǒng)調(diào)度器不同的是，LATE會(huì)對運(yùn)行的慢的任務(wù)賦予權(quán)值并按照權(quán)值執(zhí)行一部分的探測性任務(wù)。在選擇執(zhí)行探測性任務(wù)的節(jié)點(diǎn)時(shí)，選擇“最快”的節(jié)點(diǎn)來執(zhí)行。而且，LATE會(huì)規(guī)定探測性任務(wù)的最大值以防止系統(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)推測性任務(wù)的閾值，當(dāng)task進(jìn)度低于同批同類task的平均進(jìn)度的SlowTaskThreshold時(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)中的推測性任務(wù)的個(gè)數(shù)小于SpeculativeCap，則按下面策略調(diào)度推測性任務(wù)。1）如果該節(jié)點(diǎn)是慢節(jié)點(diǎn)（節(jié)點(diǎn)得分低于SlowNodeThreshold），則忽略這個(gè)請求；（2）對當(dāng)前正在運(yùn)行的task按估算的剩余完成時(shí)間（TimeLeft）排序；（3）選擇剩余完成時(shí)間最大且進(jìn)度低于SlowTaskThreshold的task，為該task啟動(dòng)備份任務(wù)。

6、

Constraint-basedScheduler–實(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í)行的信號；否則，告訴用戶需要修改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)度。一般的調(diào)度算法考慮的是系統(tǒng)中所有作業(yè)的運(yùn)行情況，該算法考慮的是當(dāng)前時(shí)間空閑slot的個(gè)數(shù)。Constraint-basedScheduler的設(shè)計(jì)實(shí)現(xiàn)1、Deadline估計(jì)模型（1）定義變量：

:一個(gè)查詢，是查詢的到來時(shí)間，是輸入數(shù)據(jù)大小，是相關(guān)的最終期限：由查詢對應(yīng)的Hadoop的一個(gè)作業(yè)。是第個(gè)map任務(wù)，是第個(gè)reduce任務(wù)，其中，。作業(yè)的到達(dá)時(shí)間、輸入數(shù)據(jù)大小和最終期限如所示：集群中分配給該工作的所有slot數(shù)目。，其中，是map任務(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ù)的開始時(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)前作業(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階段的工作已經(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è)為默認(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)度。ContentsHadoop和MapReduce簡介1

Hadoop的集群作業(yè)調(diào)度原理2如何編寫自己的Hadoop調(diào)度器4

結(jié)論與展望5

Hadoop的集群作業(yè)調(diào)度算法3如何編寫自己的Hadoop調(diào)度器步驟1編寫JobInProgressListener步驟2編寫調(diào)度器類，繼承抽象類TaskScheduler步驟3配置并啟用Hadoop調(diào)度器

//編寫自己的JobInProgressListener抽象類abstractclassJobInProgressListener{publicabstractvoidjobAdded(JobInProgressjob)throwsIOException;publicabstractvoidjobRemoved(JobInProgressjob);publicabstractvoidjobUpdated(JobChangeEventevent);}編寫JobInProgressListener//writeyourownlistenerclassMyJobListener

extendsJobInProgressListener{privateList<JobInProgress>jobQueue=new

ArrayList<JobInProgress>();publicvoidjobAdded(JobInProgressjob){synchronized(jobQueue){

jobQueue.add(job);//將Job添加到隊(duì)列中

tt.initJob(job);//初始化job

sortJobs();//對所有作業(yè)進(jìn)行排序}}publicvoidjobRemoved(JobInProgressjob){synchronized(jobQueue){

jobQueue.remove(job);}}……}編寫調(diào)度器類abstractclassTaskSchedulerimplementsConfigurable{publicsynchronizedvoidsetTaskTrackerManager(

TaskTrackerManager

taskTrackerManager){

this.taskTrackerManager=taskTrackerManager;

}publicabstrac