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ù)分析的軟件框架

提供了廉價的處理大數(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ù)的軟件框架。計算機集群

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工作機制3、Hadoop調(diào)度流程TaskTrackerTaskTrackerTaskTrackerJobTrackerTaskScheduler④assignTasks()⑤tasklist③<TaskTrackerStatus,askForNewTask>⑥tasks-to-lauchTask⑦launch③③Client①submitJob()②notifyinitJob()？？？？？？？？？？？？？？

Hadoop作業(yè)包含一些map任務(wù)和task任務(wù)。這些任務(wù)在集群的節(jié)點的任務(wù)槽(slots)上執(zhí)行。每一個節(jié)點根據(jù)其計算資源配置有一系列的map任務(wù)槽和reduce槽，典型入每個節(jié)點cpu的一個核當(dāng)作一個slot。調(diào)度器的任務(wù)就是為任何空閑的slot分配任務(wù)。所有調(diào)度器實際上均采用了三級調(diào)度策略，即為空閑的slot依次選擇一個隊列、作業(yè)和任務(wù)。隊列（queue）用戶被劃分到某個隊列每個隊列分配一定量的資源作業(yè)（job）提交時間優(yōu)先級（5個優(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適用于實時作業(yè)的調(diào)度器Constraint-basedScheduler

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

最早的HadoopMap/Reduce計算架構(gòu)中，JobTracker在進(jìn)行作業(yè)調(diào)度時使用的是FIFO(FirstInFirstOut)算法。所有用戶的作業(yè)都被提交到一個隊列中，然后由JobTracker先按照作業(yè)的優(yōu)先級高低，再按照作業(yè)提交時間的先后順序選擇將被執(zhí)行的作業(yè)。

FIFO比較簡單，hadoop中只有一個作業(yè)隊列，被提交的作業(yè)按照先后順序在作業(yè)隊列中排隊，新來的作業(yè)插入到隊尾。一個作業(yè)運行完后，總是從隊首取下一個作業(yè)運行。這種調(diào)度策略的優(yōu)點是簡單、易于實現(xiàn)，同時也減輕了jobtracker的負(fù)擔(dān)。但是它的缺點也是顯然的，它對所有的作業(yè)都一視同仁，沒有考慮到作業(yè)的緊迫程度，另外對小作業(yè)的運行不利。1、FIFO調(diào)度器FIFO調(diào)度器job1按到達(dá)時間排序，先來先服務(wù)job2job3job4job5job6job7job8maptask0maptask1maptask2reducetask0reducetask1reducetask2maptask3maptask4maptask5job1queue<hasafreeslot><returnanewtask>FIFO調(diào)度器job1按到達(dá)時間排序，先來先服務(wù)job2job3job4job5job6job7job8maptask1failedTasksmaptask0localitytasksmaptask3non-localitytasksmaptask2maptask4speculativetasksmaptask5job1reducetask0nonRunningReducesreducetask1speculativetasksreducetask22、Fair公平調(diào)度器算法設(shè)計思想：適用于多用戶情形。當(dāng)集群中由多個用戶提交作業(yè)時，為了保證公平性，調(diào)度器為每個用戶或每個UNIXGroup分配一個資源池。資源池里的每個作業(yè)都會按照其作業(yè)權(quán)重分配最小資源共享量以保證每個作業(yè)都能得到執(zhí)行而不至于饑餓。當(dāng)集群中的某個節(jié)點出現(xiàn)空閑的slot時，則選擇目前已獲得的資源量和理論上應(yīng)獲得的資源量的差值最大的作業(yè)來執(zhí)行，以保證公平。主要特點：支持多用戶多隊列：資源公平共享（公平共享量有優(yōu)先級決定）：公平調(diào)度器按照資源池（pool）來組織作業(yè)，并把資源公平地分到這些資源池里。默認(rèn)情況下，每個用戶擁有一個獨立的資源池，以使每個用戶不管提交多少作業(yè)都能獲得一份等同的集群資源量。資源池也可以依據(jù)一定的權(quán)重來獲取相應(yīng)比例的資源份額。資源池實際上也可以稱為隊列。保證最小共享量：除公平共享，公平調(diào)度算法還能為資源池設(shè)定其所需的最小共享量，管理員可以給每個pool配置一個最小共享量，調(diào)度器在分配資源時，需要保證每個pool中的作業(yè)獲取該數(shù)目的資源。這樣確保用戶或應(yīng)用程序總能獲取足夠的資源，由此可以提高整個系統(tǒng)的資源利用率。支持時間片搶占：公平調(diào)度器支持搶占，如果一個池在一定時間內(nèi)未得到公平地資源分配，調(diào)度器就會終止池中得到過多資源的任務(wù)，將集群資源讓給此資源池。限制作業(yè)并發(fā)量，防止中間數(shù)據(jù)塞滿硬盤：公平調(diào)度算法調(diào)度運行所有用戶作業(yè)，但也可以限定每個資源池中最大并發(fā)作業(yè)數(shù)和每個用戶最多提交作業(yè)數(shù)。如果一次性運行大作業(yè)，會導(dǎo)致產(chǎn)生過多的中間記錄信息以及過多的上下文切換，這都會影響到作業(yè)執(zhí)行的性能。超過數(shù)量的作業(yè)將在調(diào)度隊列中等待，直到一些資源池的早期作業(yè)完成。每個資源池對作業(yè)的調(diào)度方式可以配置，支持兩種調(diào)度策略，分別為FIFO和公平調(diào)度。動態(tài)調(diào)整各個資源池的資源量：當(dāng)集群中存在多個資源池時，某些資源池的資源可能用不了，這時調(diào)度器會自動將這些資源池中的剩余資源共享給其它所需要的資源池，其它這些資源獲取的共享資源多少主要由資源池權(quán)重決定，權(quán)重越大，獲取的資源越多，一個資源池的最小共享量加上其獲取的共享資源就是公平共享量。公平調(diào)度器的實現(xiàn)—基本概念Pool：資源池，或者作業(yè)池。每個pool里有一定量的資源（CPU、內(nèi)存、網(wǎng)絡(luò)IO，磁盤等，這些由管理員配置），每個用戶屬于某個pool，其作業(yè)可使用這個pool中的資源，可限定每個pool中最大并發(fā)作業(yè)數(shù)和每個用戶最多提交作業(yè)數(shù)。默認(rèn)情況下，一個linux用戶對應(yīng)一個pool，而管理員也可以配以一個linuxgroup對應(yīng)一個pool。pool實際上也可以稱為group或者隊列。

最小共享量：管理員可給每個pool配置一個最小共享量，調(diào)度器在分配資源時，需要保證每個pool中的作業(yè)至少獲取該數(shù)目的資源。一個常見的應(yīng)用場景是，對產(chǎn)品pool設(shè)置最小共享量，而測試pool不設(shè)置，這樣，當(dāng)可用資源有限時時，優(yōu)先保證產(chǎn)品pool有資源可用。公平共享量：當(dāng)集群中存在多個pool時，某些pool中的資源可能用不了，這時候調(diào)度器會自動將這些pool中剩余的資源共享給其他需要的pool，其他這些pool獲取的共享資源多少主要由其poolweight決定，poolweight越大，獲取的資源越多。一個pool的最小共享量加上其獲取的共享資源數(shù)目，就是公平共享量。

公平調(diào)度器的實現(xiàn)—算法實現(xiàn)

最簡單的實現(xiàn)公平共享的方法如下：任何時候當(dāng)一個slot空閑時，把它分配給運行著最少任務(wù)的資源池。這可以保證所有的pool得到相同數(shù)量的slot，除非這個pool的需求量（調(diào)度器想要執(zhí)行任務(wù)數(shù)，等于已經(jīng)運行的任務(wù)數(shù)+尚未啟動的任務(wù)數(shù)）比其得到的公平共享量小，這時，該pool多余的slot將會分配給其它pool中。下面介紹公平調(diào)度器的兩個特性，這兩個特性使得公平共享算法簡單了一些。

1、pool的權(quán)重代表了某個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），再依次掃描隊列，選擇合適的pool或job。公平調(diào)度器的實現(xiàn)—公平共享量的計算方法

公平共享量是基于最小共享量和共享資源量計算得到的，它反映的是某個pool經(jīng)過資源共享（某些pool的資源用不了，會自動共享給其他pool）之后，一共可以獲取的資源總量，一般會大于等于最小共享量。如果每個pool沒有配置最小共享量，且提交了無限量的作業(yè)，則讓每個pool的slotsAssigned/weight值相同即可。（其中slotsAssgined表示分配給該pool的slot數(shù)，weight表示pool的權(quán)重）。而有了最小共享量minShare和pool中的需求量demand（該pool中所有作業(yè)尚需的slot總數(shù)）后，計算公平共享量fairShare需注意以下兩種情況：（1）某些pool中的最小共享量可能用不完（2）給配給某些pool的資源量小于其最小共享量

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

通過以上算法計算出的公平共享量即為“公平調(diào)度器”的“公平”含義之所在，應(yīng)盡量保證每個pool獲取的資源量為fairshare，如果一定時間期限內(nèi)達(dá)不到，則搶占資源。關(guān)于這個R是不是一定滿足條件4，有資料顯示一定存在這個樣的R。公平調(diào)度器的實現(xiàn)—調(diào)度流程

新版本的Hadoop采用公平調(diào)度器的層次調(diào)度算法，首先選擇一個pool，然后從該pool中選擇一個job，最后從該job中選擇一個locality的task。

公平調(diào)度器的實現(xiàn)—一些特性

1.資源搶占當(dāng)一定時間（管理員可配置）內(nèi)，某個pool中獲取的資源量少于最小共享量，或者公平共享量的一半，則調(diào)度器會找出哪個pool搶占了該pool的資源，并殺死相應(yīng)數(shù)量的task以搶占資源。之所以要進(jìn)行搶占，還是為了“公平”，即：保證每個pool能獲取到它應(yīng)得到的資源。2.delayscheduling機制當(dāng)出現(xiàn)空閑slot時，如果排在隊列前面的job對應(yīng)的所有task均沒有l(wèi)ocality特性，則該作業(yè)會延遲調(diào)度，直到一段時間后，該job出現(xiàn)locality的task或者發(fā)生超時，才不得不調(diào)度該job的task。在此解釋下locality：當(dāng)出現(xiàn)空閑slot時，該slot來自某個節(jié)點，而該節(jié)點上存有部分?jǐn)?shù)據(jù)，如果某個task所需要的數(shù)據(jù)正好位于該節(jié)點上，則將該slot分配給該task是非常好的，因為它避免了通過網(wǎng)絡(luò)讀取數(shù)據(jù)。3、計算能力調(diào)度器CapacityScheduler

設(shè)計思想：支持多個隊列，每個隊列可配置一定的資源量，每個隊列采用FIFO調(diào)度策略，為了防止同一個用戶的作業(yè)獨占隊列中的資源，該調(diào)度器會對同一用戶提交的作業(yè)所占資源量進(jìn)行限定。調(diào)度時，首先按以下策略選擇一個合適隊列：計算每個隊列中正在運行的任務(wù)數(shù)與其應(yīng)該分得的計算資源之間的比值，選擇一個該比值最小的隊列；然后按以下策略選擇該隊列中一個作業(yè)：按照作業(yè)優(yōu)先級和提交時間順序選擇，同時考慮用戶資源量限制和內(nèi)存限制。特性:（1）計算能力保證。支持多個隊列某個隊列可以被提交到某一個隊列中。每個隊列會配置一定比例的計算資源，且所有提交到隊列中的作業(yè)共享該隊列中的資源。（2）靈活性。空閑資源會被分配給那些未到達(dá)資源使用上的隊列，當(dāng)某個未到達(dá)資源的隊列需要資源時，一旦出現(xiàn)空閑資源，便會分配給它們。（3）支持優(yōu)先級。隊列支持作業(yè)優(yōu)先級調(diào)度（默認(rèn)是FIFO）（4）多重租賃。綜合考慮多種約束防止單個作業(yè)、用戶或者隊列獨占隊列或集群中的資源。（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：每個用戶的可用的最少資源量（所有用戶均相同），需用戶在配置文件中指定@capacityPercent：計算資源比例，需用戶在配置文件中指定@numJobsByUser：每個用戶的作業(yè)量，用以跟蹤每個用戶提交的作業(yè)量，并進(jìn)行數(shù)量的上限限制。該隊列中map或reducetask的屬性：@capacity：實際的計算資源量，這個隨著tasktracker中slot數(shù)目變化（用戶可能在添加或減少機器節(jié)點）而動態(tài)變化，大小為：capacityPercent*mapClusterCapacity/100@numRunningTasks：正在running的task數(shù)目CapacityScheduler—涉及到的變量@numSlotsOccupied：正在running的task占用的slot總數(shù)，注意，在CapacityScheduler中，runningtask與slot不一定是一一對應(yīng)的，每個task可獲取多個slot，這主要是因為該調(diào)度支持內(nèi)存資源調(diào)度，某個task可能需要多個slot包含的內(nèi)存量。@numSlotsOccupiedByUser：每個用戶的作業(yè)占用slot總數(shù)，用以限制用戶使用的資源量。(2)job維護(hù)的信息priority：作業(yè)優(yōu)先級，分為五個等級，從大到小依次為：VERY_HIGH，HIGH，NORMAL，LOW，VERY_LOW;numMapTasks/numReduceTasks

：job的map/reducetask總數(shù)runningMapTasks/runningMapTasks：job正在運行的map/reducetask數(shù)finishedMapTasks/finishedReduceTasks：job已完成的map/reducetask數(shù)……(3)task維護(hù)的信息task開始運行時間，當(dāng)前狀態(tài)等CapacityScheduler—調(diào)度算法當(dāng)某個tasktracker上出現(xiàn)slot時，調(diào)度器依次選擇一個

queue、（選中的queue中的）job、（選中job中的）task，并將該slot分配給該task。下面介紹選擇queue、job和task所采用的策略：（1）選擇queue：將所有queue按照資源使用率（numSlotsOccupied/capacity）從小到大排序，依次進(jìn)行處理，直到找到一個合適的job。（2）選擇job：在當(dāng)前queue中，所有作業(yè)按照作業(yè)提交時間和作業(yè)優(yōu)先級排序（假設(shè)開啟支持優(yōu)先級調(diào)度功能，默認(rèn)不支持，需要在配置文件中開啟），調(diào)度依次考慮每個作業(yè)，選擇符合兩個條件的job：[1]作業(yè)所在的用戶未到達(dá)資源使用上限；[2]該TaskTracker所在的節(jié)點剩余的內(nèi)存足夠該job的task使用。（3）選擇task，同大部分調(diào)度器一樣，考慮task的locality（就近原則）和資源使用情況。即：調(diào)用JobInProgress中的obtainNewMapTask()/obtainNewReduceTask()方法）

CapacityScheduler—調(diào)度流程

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

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

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

計算能力調(diào)度器調(diào)度job時會考慮作業(yè)的內(nèi)存限制，為了滿足某些特殊job的特殊內(nèi)存需求，可能會為該job分配多個slot；而公平調(diào)度器對這種特殊的job無能為力，只能殺掉這種task。4、

異構(gòu)負(fù)載動態(tài)調(diào)度器

設(shè)計目標(biāo)：

異構(gòu)負(fù)載調(diào)度器將問題集中在當(dāng)MapReduce框架中有不同種類負(fù)載時怎樣提高硬件利用率。作業(yè)按其類型可分為CPU頻繁類型和IO頻繁類型。但目前Hadoop的調(diào)度器（前面的三種調(diào)度器）都沒有考慮到作業(yè)負(fù)載的類型，調(diào)度的策略都是在根據(jù)不同規(guī)則排列的作業(yè)隊列取隊首作業(yè)運行，這樣會降低整個系統(tǒng)的吞吐量。設(shè)計思想：

設(shè)計一個三級隊列調(diào)度器，包含工作負(fù)載預(yù)測機制MR-Predict和三個不同的隊列，即：CPU-Bound隊列，I/O-Bound隊列和等待隊列。通過MR-Predict機制自動地預(yù)測到達(dá)的作業(yè)負(fù)載類型并把它們放入不同的隊列中。每一個隊列獨立地按照FCFS調(diào)度策略工作。異構(gòu)負(fù)載動態(tài)調(diào)度器的設(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：某個節(jié)點中正在并發(fā)執(zhí)行任務(wù)的個數(shù)

MICT：MapTaskCompletedTime，Map任務(wù)完成所需時間

DIOR：磁盤IO傳輸速率：參數(shù)，保證：MOD=*MID異構(gòu)負(fù)載動態(tài)調(diào)度器的設(shè)計實現(xiàn)2、分類規(guī)則：如果滿足下列條件，則將該作業(yè)標(biāo)記為CPU-Bound類如果滿足下列條件，則將該作業(yè)標(biāo)記為Sway隊列類如果滿足下列條件，則將該作業(yè)標(biāo)記為I/O-Bound類假設(shè)每一個reducer有相同大小的數(shù)據(jù)輸入，則SID與集群的分布有關(guān)。每個節(jié)點的SID取決于該節(jié)點運行的reducer和整個集群中的reducer的比例，計算如下：異構(gòu)負(fù)載動態(tài)調(diào)度器的設(shè)計實現(xiàn)3、設(shè)計實現(xiàn)：（1）MR-Predict機制假設(shè)一個job的任務(wù)有相同的特點，即可以通過該任務(wù)已經(jīng)執(zhí)行的task的信息來預(yù)測其它任務(wù)的行為。當(dāng)在一個節(jié)點有空閑的slot時，調(diào)度器將會指定一個map任務(wù)，當(dāng)這些map任務(wù)完成時，可以計算出MICT、MID和MOD，然后根據(jù)下面的分類規(guī)則可將作業(yè)分為三種類型。異構(gòu)負(fù)載動態(tài)調(diào)度器的設(shè)計實現(xiàn)（2）調(diào)度策略當(dāng)一個新作業(yè)到達(dá)時，將會暫時被放到等待隊列中以確定其負(fù)載類型。然后調(diào)度器將該作業(yè)一個Map任務(wù)分配到每一個TaskTracker上（改作業(yè)稱為test-runtask）。如下圖1示，如果CPU-Bound和I/O-Bound兩個隊列當(dāng)時均為空，則等待隊列的隊首作業(yè)將會被移動到任意一個隊列中，然后調(diào)度執(zhí)行直至改作業(yè)的負(fù)載類型被確定。然后，如果發(fā)現(xiàn)該作業(yè)被移到了錯誤的隊列，則將其移動到正確的隊列。每個隊列調(diào)度作業(yè)時采用FCFS策略。5、LATE—適用于異構(gòu)集群的調(diào)度器（1）現(xiàn)有Hadoop調(diào)度器的缺陷：現(xiàn)有的Hadoop調(diào)度器都是建立在同構(gòu)集群的假設(shè)前提下，具體假設(shè)如下：1）集群中各個節(jié)點的性能完全一樣2）對于reducetask，它的三個階段：copy、sort和reduce，用時各占1/33）同一job的同類型的task是一批一批完成的，他們用時基本一樣。

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

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

3）reduce階段，此時一個用戶自定義的reduce函數(shù)正在處理map的輸出結(jié)果。分值等于reduce函數(shù)已經(jīng)處理數(shù)據(jù)的比例。Hadoop定義一個閾值（threshold），當(dāng)某一個任務(wù)至少執(zhí)行了1分鐘且進(jìn)度得分小于該閾值-0.2時，該任務(wù)就被標(biāo)定位落后任務(wù)。（3）LATE的設(shè)計思想：主要用來調(diào)度探測性任務(wù)。與傳統(tǒng)調(diào)度器不同的是，LATE會對運行的慢的任務(wù)賦予權(quán)值并按照權(quán)值執(zhí)行一部分的探測性任務(wù)。在選擇執(zhí)行探測性任務(wù)的節(jié)點時，選擇“最快”的節(jié)點來執(zhí)行。而且，LATE會規(guī)定探測性任務(wù)的最大值以防止系統(tǒng)顛簸。（4）定義變量SpeculativeCap：系統(tǒng)中最大同時執(zhí)行的speculativetask數(shù)目（推薦值為總slot數(shù)的10%

）；SlowNodeThreshold：標(biāo)志節(jié)點快慢的閾值，調(diào)度得分低于該閾值的node（慢節(jié)點）上不會啟動speculativetask（推薦值為25%

）；SlowTaskThreshold：標(biāo)志是否為該任務(wù)啟動推測性任務(wù)的閾值，當(dāng)task進(jìn)度低于同批同類task的平均進(jìn)度的SlowTaskThreshold時，會為該task啟動speculativetask（推薦值為25%

）。TimeLeft：任務(wù)的剩余時間，計算公式為（1-進(jìn)度得分）/執(zhí)行比，其中執(zhí)行比=進(jìn)度得分/執(zhí)行時間。（5）調(diào)度策略如果當(dāng)前有一個空閑的slot并且系統(tǒng)中的推測性任務(wù)的個數(shù)小于SpeculativeCap，則按下面策略調(diào)度推測性任務(wù)。1）如果該節(jié)點是慢節(jié)點（節(jié)點得分低于SlowNodeThreshold），則忽略這個請求；（2）對當(dāng)前正在運行的task按估算的剩余完成時間（TimeLeft）排序；（3）選擇剩余完成時間最大且進(jìn)度低于SlowTaskThreshold的task，為該task啟動備份任務(wù)。

6、

Constraint-basedScheduler–實時調(diào)度器設(shè)計目標(biāo)：這種調(diào)度器集中處理如何滿足用戶的時間需求上。其設(shè)計目標(biāo)有兩個：（1）能夠給用戶及時的反饋，告訴用戶所提交的某項工作是否可以在其規(guī)定的Deadline內(nèi)完成。如果能完成，則反饋給用戶可以執(zhí)行的信號；否則，告訴用戶需要修改Deadline后再次提交數(shù)據(jù)。（2）在滿足所有實時作業(yè)需求的同時能保證可同時運行的作業(yè)達(dá)到最大量。設(shè)計思想：（1）綜合考慮影響作業(yè)完成時間的變量，例如map和reduce運行時，map和reduce輸入數(shù)據(jù)大小，數(shù)據(jù)的分布情況等等，建立一個作業(yè)執(zhí)行代價模型。（2）根據(jù)建立的作業(yè)執(zhí)行代價模型，并把用戶的Deadline要求作為輸入的一部分考慮進(jìn)去來確定某一作業(yè)的可調(diào)度性。只有作業(yè)明確要求的Deadline能被滿足時，改作業(yè)才能被調(diào)度。一般的調(diào)度算法考慮的是系統(tǒng)中所有作業(yè)的運行情況，該算法考慮的是當(dāng)前時間空閑slot的個數(shù)。Constraint-basedScheduler的設(shè)計實現(xiàn)1、Deadline估計模型（1）定義變量：

:一個查詢，是查詢的到來時間，是輸入數(shù)據(jù)大小，是相關(guān)的最終期限：由查詢對應(yīng)的Hadoop的一個作業(yè)。是第個map任務(wù)，是第個reduce任務(wù)，其中，。作業(yè)的到達(dá)時間、輸入數(shù)據(jù)大小和最終期限如所示：集群中分配給該工作的所有slot數(shù)目。，其中，是map任務(wù)的slot數(shù)，是reduce任務(wù)的slot數(shù)

：map數(shù)據(jù)分布向量，其中是作業(yè)的map任務(wù)的總數(shù)。是分配給第個map任務(wù)的數(shù)據(jù)的比例。由于map數(shù)據(jù)是平均分配給各個map節(jié)點上的，所以。:過濾比，即map任務(wù)輸出端數(shù)據(jù)和輸入端數(shù)據(jù)的比值，一般情況下:reduce任務(wù)輸出端的數(shù)據(jù)量

：map任務(wù)處理單元數(shù)據(jù)的時間：reduce任務(wù)處理單元數(shù)據(jù)的時間

：轉(zhuǎn)換單元數(shù)據(jù)的通信時間：作業(yè)第一個map任務(wù)的開始時間

：作業(yè)第一個reduce任務(wù)的開始時間

：作業(yè)能被調(diào)度的map任務(wù)需被滿足的最小數(shù)

：作業(yè)能被調(diào)度的reduce任務(wù)需被滿足的最小數(shù)（2）計算過程為了計算作業(yè)的持續(xù)時間，考慮map階段的計算時間，reduce階段的計算時間和reduce的拷貝階段數(shù)據(jù)轉(zhuǎn)換時間。因此，作業(yè)的持續(xù)時間可以表述如下：由于作業(yè)有一個到達(dá)時間和最后期限，因此

設(shè)reduce任務(wù)開始的最大時間，則：所以，因此，（3）調(diào)度過程調(diào)度器維護(hù)一個按照Deadline排序的優(yōu)先隊列，任務(wù)調(diào)度從隊首作業(yè)開始。如果當(dāng)前作業(yè)的需求不能被滿足，則考慮下一個作業(yè)，直至隊列中沒有作業(yè)或者TaskTracker中沒有可用的slot為止。1）當(dāng)一個作業(yè)到達(dá)時，首先根據(jù)上面公式計算,如果當(dāng)前可用的slot數(shù)量小于，則作業(yè)被拒絕。否則，進(jìn)行第二步；2）根據(jù)為該作業(yè)指定的所有reduce的數(shù)量（一般由用戶指定或者設(shè)為默認(rèn)值）來計算。如果在時刻系統(tǒng)可用的slot數(shù)量小于該作業(yè)指定的所有reduce的數(shù)量，則仍然拒絕該作業(yè)。否則轉(zhuǎn)入第三步；3）如果作業(yè)被調(diào)度且所有map階段的工作已經(jīng)完成，則計算來確定多少個reduce任務(wù)能被調(diào)度。（3）調(diào)度過程調(diào)度器維護(hù)一個按照Deadline排序的優(yōu)先隊列，任務(wù)調(diào)度從隊首作業(yè)開始。如果當(dāng)前作業(yè)的需求不能被滿足，則考慮下一個作業(yè)，直至隊列中沒有作業(yè)或者TaskTracker中沒有可用的slot為止。1）當(dāng)一個作業(yè)到達(dá)時，首先根據(jù)上面公式計算,如果當(dāng)前可用的slot數(shù)量小于，則作業(yè)被拒絕。否則，進(jìn)行第二步；2）根據(jù)為該作業(yè)指定的所有reduce的數(shù)量（一般由用戶指定或者設(shè)為默認(rèn)值）來計算。如果在時刻系統(tǒng)可用的slot數(shù)量小于該作業(yè)指定的所有reduce的數(shù)量，則仍然拒絕該作業(yè)。否則轉(zhuǎn)入第三步；3）如果作業(yè)被調(diào)度且所有map階段的工作已經(jīng)完成，則計算來確定多少個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添加到隊列中

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