大數據問題紐約證券交易所每天產生1TB的交易數據社交網站facebook的主機存儲著約10億張照片，占據PB級存儲空間互聯網檔案館存儲著約2PB數據，并以每月至少20TB的速度增長。瑞士日內瓦附近的大型強子對撞機每年產生約15PB的數據這么大的數據該怎么存儲和讀??？大數據問題紐約證券交易所每天產生1TB的交易數據傳統關系型數據庫（oracle）的成本Facebook的服務器大概1萬臺，按照oracle的標準10g版本計算大約需要21億元傳統關系型數據庫（oracle）的成本Facebook的服務Hadoop簡介Hadoop一個分布式系統基礎架構，由Apache基金會開發。用戶可以在不了解分布式底層細節的情況下，開發分布式程序。充分利用集群的威力高速運算和存儲。由HDFS、MapReduce、HBase、Hive和ZooKeeper等成員組成。其中，HDFS和MapReduce是兩個最基礎最重要的成員。HDFS是GoogleGFS的開源版本，一個高度容錯的分布式文件系統，它能夠提供高吞吐量的數據訪問，適合存儲海量（PB級）的大文件（通常超過64M），其原理如圖所示：Hadoop簡介Hadoop一個分布式系統基礎架構，由ApHadoop優點可擴展：不論是存儲的可擴展還是計算的可擴展都是Hadoop的設計根本。經濟：框架可以運行在任何普通的PC上?？煽浚悍植际轿募到y的備份恢復機制以及MapReduce的任務監控保證了分布式處理的可靠性。（元數據磁盤錯誤，心跳測試，副本數，快照（目前還沒實現））高效：分布式文件系統的高效數據交互實現以及MapReduce結合LocalData處理的模式，為高效處理海量的信息作了基礎準備。Hadoop優點可擴展：不論是存儲的可擴展還是計算的可擴展都Hadoop在國內的分布情況Hadoop在國內的分布情況Hadoop作業調度默認調度算法FIFO公平份額調度算法FairScheduler計算能力調度算法CapacityScheduler作業調度總結

Hadoop作業調度默認調度算法FIFO默認調度算法FIFO簡介最早的HadoopMap/Reduce計算架構中，JobTracker在進行作業調度時使用的是FIFO(FirstInFirstOut)算法。所有用戶的作業都被提交到一個隊列中，然后由JobTracker先按照作業的優先級高低，再按照作業提交時間的先后順序選擇將被執行的作業。優點調度算法簡單明了，JobTracker工作負擔輕。缺點忽略了不同作業的需求差異。例如如果類似對海量數據進行統計分析的作業長期占據計算資源，那么在其后提交的交互型作業有可能遲遲得不到處理，從而影響到用戶的體驗。新的調度算法當前，新的調度器已經作為插件的形式集成在Hadoop當中。默認調度算法FIFO簡介公平份額調度算法FairSchedulerFairScheduler提出背景FairScheduler基礎知識FairScheduler兩個關鍵問題FairScheduler的配置公平份額調度算法FairSchedulerFairSchFairScheduler提出背景提出背景Facebook要處理生產型作業(數據統計分析,hive)、大型批處理作業(數據挖掘、機器學習)、小型交互型作業(hive查詢)。不同用戶提交的作業在計算時間、存儲空間、數據流量和響應時間上都有不同需求。為使hadoopmapreduce框架能夠應對多種類型作業并行執行，使得用戶具有良好的體驗，Facebook公司提出該算法。FairScheduler提出背景提出背景FairScheduler基礎知識設計思想盡可能保證所有的作業都能夠獲得等量的資源份額。系統中只有一個作業執行時，它將獨占集群所有資源。有其他作業被提交時就會有TaskTracker被釋放并分配給新提交的作業，以保證所有的作業都能夠獲得大體相同的計算資源。作業池用戶提交的作業將會放進一個能夠公平共享資源的pool(池)中。每個作業池設定了一個最低資源保障(aguaranteedminimumshare)，當一個池中包含job時，它至少可以獲得minimumshare的資源——最低保障資源份額機制。池中的作業獲得一定份額的資源?？梢酝ㄟ^配置文件限制每個池中的作業數量。缺省情況下，每個作業池中選擇將要執行的作業的策略是FIFO策略，先按照優先級高低排序，然后再按照提交時間排序。FairScheduler基礎知識設計思想FairScheduler基礎知識作業和作業池的權值weight缺省情況下，FairScheduler會為每一個用戶建立一個單獨的pool。所有用戶能夠獲得等量的資源份額而無論他提交了多少作業，而每個pool中，各個作業將平分分配給所在池的資源。實際應用中，無論是作業池還是作業，都被賦予一定的權值，并以此為依據獲得相應比例的資源。這種情況下，作業池和作業在資源分配時不是嚴格的平均分配，但這有利于根據作業的重要程度及實際需求合理分配資源。FairScheduler基礎知識作業和作業池的權值weiFairScheduler兩個關鍵問題如何選擇合適的作業執行默認是FIFO策略，此外還有一種基于缺額的策略。FairScheduler為每個作業定義了一個deficit(缺額)指標。Deficit是一個作業在理想情況下的獲得的計算資源和實際中獲得的計算資源之間的差距。FairScheduler會每隔幾百毫秒觀察每個作業中有多少任務已經在這個時間間隔內執行，并將結果與它應得的資源份額比較，以更新該作業的deficit值。一旦有空閑的tasktracker出現，首先分配給當前具有最高deficit值的作業。例外——如果系統中存在著尚未獲得最低資源保障的作業池，那么該池中的作業將會優先調度，而選擇池中的作業需要根據它們的deficit來決定。這樣做是為了盡可能滿足作業池最低保障資源份額的機制。FairScheduler兩個關鍵問題如何選擇合適的作業執FairScheduler兩個關鍵問題如何確定每個作業的資源份額缺省情況是平分資源，此外提供一種基于權值的資源分配方法。作業資源份額的計算是根據作業的權值將集群的資源總量劃分給各個可以運行的作業。默認情況下，權值基于作業優先級，每個優先級對應的權值是低一個優先級的2倍(優先級共有VERY_HIGH,HIGH,NORMAL,LOW,VERY_LOW五個等級，則VERY_HIGH具有4倍NORMAL的權值)。作業和作業池的權值可以在池配置文件中進行設定，例如可以基于作業的大小和提交時間來設定。作業池的最低資源保障也是按照權值比例分配給其中的作業。FairScheduler兩個關鍵問題如何確定每個作業的資計算能力調度CapacitySchedulerCapcityScheduler基礎知識CapcityScheduler一個關鍵問題CapcityScheduler內存管理CapcityScheduler的配置計算能力調度CapacitySchedulerCapciCapcitySchedule基礎知識基礎知識CapacityScheduler是由雅虎提出的作業調度算法，它提供了類似于FairScheduler算法的功能。CapacityScheduler中可以定義多個作業隊列(multiplequeues)，作業提交時將直接放入到一個隊列中。每個隊列都可以通過配置獲得一定數量的tasktracker資源用于處理map/reduce操作，調度算法將按照配置文件為隊列分配相應的計算資源量。對于已經分配給了某隊列但處于空閑的資源各個“忙”的隊列會分享它們。當某一隊列沒有能夠按照配置的數量值獲得足夠資源但是它的作業壓力增加了時，之前那些曾分配給它但又由于之前空閑被別的隊列所占用了的資源會在完成當前task后立即分配給回應屬的隊列。CapcitySchedule基礎知識基礎知識CapcitySchedule基礎知識基礎知識CapacityScheduler的每個隊列中采用的調度策略是FIFO算法。CapacityScheduler默認情況下不支持優先級，但是可以在配置文件中開啟此選項，如果支持優先級，調度算法就是帶有優先級的FIFO。CapacityScheduler不支持優先級搶占，一旦一個作業開始執行，在執行完之前它的資源不會被高優先級作業所搶占。CapacityScheduler對隊列中同一用戶提交的作業能夠獲得的資源百分比進行了限制以使同屬于一用戶的作業不能出現獨占資源的情況。CapcitySchedule基礎知識基礎知識CapcityScheduler一個關鍵問題如何選擇合適的作業去執行為隊列定義了一個指標—隊列中正在運行的任務數與其應該分得的計算資源(配置文件中為此隊列分配了相應數量的資源，而實際中該隊列可能沒有分配到)之間的比值。當系統中出現空閑的tasktracker，算法會首先選擇一個該比值最低的隊列。隊列被選中后，將按照作業優先級(如果支持的話)和提交時間順序選擇執行的作業。在選擇作業的時候，還需要考慮作業所屬的用戶是否已經超出了他所能使用的資源限制。此外，還會考慮tasktracker內存資源是否滿足作業的要求。CapcityScheduler一個關鍵問題如何選擇合適的CapcityScheduler內存管理內存資源的有效管理CapacityScheduler能有效地對hadoop集群的內存資源進行管理，以支持內存密集型應用。作業對內存資源需求高時，調度算法將把該作業的相關任務分配到內存資源充足的tasktracker上。在作業選擇過程中，CapacityScheduler會檢查空閑tasktracker上的內存資源是否滿足作業要求。tasktracker上的空閑資源(內存)數量值可以通過tasktracker的內存資源總量減去當前已經使用的內存數量得到，而后者包含在tasktracker向jobtracker發送的周期性心跳信息中。目前，基于內存的調度只能在linux平臺下起作用，關于內存調度的相關參數可以通過配置文件來設置。CapcityScheduler內存管理內存資源的有效管理Hadoop公平調度器算法解析※公平調度介紹※hadoop-0.20.2公平調度算法分析

基于缺額的調度算法變量定義相關算法※hadoop-0.21.0公平調度算法分析

層次調度算法Hadoop公平調度器算法解析※公平調度介紹公平調度介紹公平調度器按資源池（pool）來組織作業，并把資源公平的分到這些資源池里。默認情況下，每一個用戶擁有一個獨立的資源池，以使每個用戶都能獲得一份等同的集群資源而不管他們提交了多少作業。按用戶的Unix群組或作業配置（jobconf）屬性來設置作業的資源池也是可以的。在每一個資源池內，會使用公平共享（fairsharing）的方法在運行作業之間共享容量（capacity）。用戶也可以給予資源池相應的權重，以不按比例的方式共享集群。公平調度介紹公平調度器按資源池（pool）來組織作業，并把資公平調度介紹除了提供公平共享方法外，公平調度器允許賦給資源池保證（guaranteed）最小共享資源，這個用在確保特定用戶、群組或生產應用程序總能獲取到足夠的資源時是很有用的。當一個資源池包含作業時，它至少能獲取到它的最小共享資源，但是當資源池不完全需要它所擁有的保證共享資源時，額外的部分會在其它資源池間進行切分。公平調度介紹除了提供公平共享方法外，公平調度器允許賦給資源池公平調度介紹主要特點如下：?

支持多用戶多隊列?

資源公平共享（公平共享量由優先級決定）?

保證最小共享量?

支持時間片搶占?

限制作業并發量，以防止中間數據塞滿磁盤公平調度介紹主要特點如下：Pool資源池，或者作業池。每個pool里有一定量的資源（管理員配置），每個用戶屬于某個pool，其作業可使用這個pool中的資源，可限定每個pool中最大并發作業數和每個用戶最多提交作業數。默認情況下，一個linux用戶對應一個pool，而管理員也可以配以一個linuxgroup對應一個pool。pool實際上也可以稱為group或者隊列。Pool資源池，或者作業池。每個pool里有一定量的資源（最小共享量管理員可給每個pool配置一個最小共享量，調度器在分配資源時，需要保證每個pool中的作業至少獲取該數目的資源。一個常見的應用場景是，對產品pool設置最小共享量，而測試pool不設置，這樣，當可用資源有限時時，優先保證產品pool有資源可用。最小共享量管理員可給每個pool配置一個最小共享量，調度器在公平共享量當集群中存在多個pool時，某些pool中的資源可能用不了，這時候調度器會自動將這些pool中剩余的資源共享給其他需要的pool，其他這些pool獲取的共享資源多少主要由其poolweight決定，poolweight越大，獲取的資源越多。一個pool的最小共享量加上其獲取的共享資源數目，就是公平共享量。公平共享量當集群中存在多個pool時，某些pool中的資源可公平調度算法分析——變量定義★描述job信息的變量(JobInfo)jobWeight：作業的權重。實際計算時，map階段和reduce階段分開，分別記為mapWeight，reduceWeightjobDeficit：作業的缺額，即作業在理想調度器上所應得的計算時間與實際所獲得的計算時間的缺額，這個是測量作業的“不公平”待遇的度量標準。實際運算時將map階段和reduce階段分開，分別記為mapDeficit和reduceDeficit。公平調度算法分析——變量定義★描述job信息的變量(JobI公平調度算法分析——變量定義runningTasks：作業正在運行的task數。實際計算時，maptask和reducetask需分開，分別記為：runningMaps和runningReducesminSlots：作業在相應的pool中的最小slot保證量，實際計算時，map階段和reduce階段分開，分別記為：minMaps和minReducesjobFairShare：上次更新給該job分配的公平共享量，實際計算時，map階段和reduce階段分開，分別記為mapFairShare和reduceFairShare公平調度算法分析——變量定義runningTasks：作業正公平調度算法分析——變量定義★計算過程的中間變量poolWeight：pool的權重，這個可由用戶自己設定，默認為1。tasksNum：某個作業正在運行任務與尚未運行的任務（包括Speculative任務）數量和，有兩種task類型：maptask和reducetask，計算時需要分開priorityFactor：與作業優先級相關的因子，用于計算作業的權重，具體如圖：prioritypriorityFactorVERY_HIGH4.0HIGH2.0NORMAL1.0LOW0.5Default0.25公平調度算法分析——變量定義★計算過程的中間變量priori公平調度算法分析——變量定義poolRunningJobsWeightSum：pool中已經開始運行的所有作業的權重之和poolLowJobsWeightSum：在某個pool中，已經開始運行的，但尚需slot（tasksNum數量大于其最小共享量）的那些作業權重之和systemJobsWeightSum：系統（可能有很多pool）中可以運行的所有作業的權重之和timeDelta：兩次信息更新的時間間隔公平調度算法分析——變量定義poolRunningJobsW公平調度算法分析——相關算法當出現一個空閑slot時，公平調度器會將此slot分配給缺額最大的作業。系統每隔500毫秒（UPDATE_INTERVAL）更新一次信息（有一個專門的更新線程對job信息進行更新），包括：作業缺額（作業的其他屬性，如權重、最小共享量、公平共享量等，均是為計算缺額服務的）、權重、最小共享量、公平共享量等。公平調度算法分析——相關算法當出現一個空閑slot時，公平調公平調度算法分析——相關算法1)作業權重計算方法（1）默認情況下，權重是基于作業優先權的，但也可以基于作業的大小和年齡。權重的計算方法如下：（2）根據優先權計算權重：（3）根據用戶自定義的weightAdjuster類調整權重公平調度算法分析——相關算法1)作業權重計算方法公平調度算法分析——相關算法2)更新權重每個已經運行的作業權重更新公式：3)初始缺額計算每個作業的初始缺額mapDeficit,reduceDeficit設置為0.4)更新作業的最小共享量在每個pool中，將其擁有的slot按作業的權重分配給各個作業（由步驟(1)完成），分完之后將剩余的slot按作業的權重和缺額分配給仍需slot的作業（由步驟(2)和(3)完成），如果還有slot剩余，則將這些slot共享給其他pool。公平調度算法分析——相關算法2)更新權重公平調度算法分析——相關算法初始化：當前所有作業的最小共享量置零；pool的minMaps數或者minReduces數（由用戶在配置文件中設定）重復以下幾步，直到slotsLeft=0：公平調度算法分析——相關算法初始化：公平調度算法分析——相關算法（1）計算每個job的最小共享量：jobinfo.minMaps或jobinfo.minReduces首先計算該作業可獲得的共享值：根據當前pool的剩余slot數，調整該共享值：其中runnableNum表示作業尚需的slot數與正在運行的slot數之和，curMin表示作業的當前最小共享量（jobinfo.minMaps或jobinfo.minReduces），初始值為0。將slotsToGive作為最小共享量賦予相應的job。修改值為值減去slotsToGive。如果此輪循環中，slotsLeft值未變，即沒有slot分給任何作業，則將剩余的slot共享給pool中所有job，即，執行（2）（3）并結束算法：公平調度算法分析——相關算法（1）計算每個job的最小共享量公平調度算法分析——相關算法（2）將pool中的job按weight和deficit排序（3）按順序依次計算每個job的最小共享量。首先計算該作業可獲得的共享值：根據當前pool的剩余slot數，調整該共享值：將slotsToGive作為最小共享量賦予相應的job。修改slotsLeft值為slotsLeft值減去slotsToGive。需要注意的是，當執行完（2）（3）后，slotsLeft可能仍大于0，這時候會將剩余的slotsLeft個slot共享給其他pool。公平調度算法分析——相關算法（2）將pool中的job按we公平調度算法分析——相關算法5)更新公平共享量主要思想：基于作業權重和最小共享量計算公平共享量。首先，根據權重分配可用slot數，如果作業的最小共享量大于公平共享量，先要滿足最小共享量，更新可用slot數，重復以上步驟，直到所有作業的最小共享量小于或等于公平共享量，這樣，每個作業的最小共享量都得到了滿足，最后，所有作業平分剩下的slot數。公平調度算法分析——相關算法5)更新公平共享量公平調度算法分析——相關算法算法實現：初始化：當前所有作業的公平共享量置零；slotsLeft={系統中mapslot或者reduceslot總數}；jobsLeft={系統中正在運行的作業}(1)遍歷集合jobsLeft中的所有作業，計算每個作業的jobFairShare：如果作業的最小共享量（minSlots）大于公平共享量（jobFairShare），則：將最小共享量作為公平共享量賦值給作業。同時將此作業從集合jobsLeft中刪除。（2）將剩下的slot按權重比例給集合jobsLeft中剩余的作業：將jobFairShare作為公平共享量賦值給作業。公平調度算法分析——相關算法算法實現：公平調度算法分析——相關算法6)更新缺額實際計算時，會分開：7)資源分配當系統中產生一個空閑slot時，將此slot分配給缺額最大的作業。公平調度算法分析——相關算法6)更新缺額Hadoop-0.21.0版本公平調度器新特性(1)將之前（0.21.0之前版本）的基于缺額的調度算法改為層次調度算法(2)支持資源搶占(3)添加delayscheduling機制，使調度策略更優。(4)每個隊列的調度策略可以配置，支持兩種調度策略，分別為FIFO和FAIR，不管采用哪種調度策略，以上三個功能全部支持。Hadoop-0.21.0版本公平調度器新特性(1)將之前層次調度算法大的思想與CapacityScheduler類似，首先選擇一個pool，然后從該pool中選擇一個job，最后從該job中選擇一個locality的task。其中，選擇pool和job的策略相同，均采用了FairShareComparator比較器對pool或者job進行排序，然后從頭到尾掃描隊列，選出合適的pool或者job。在FairShareComparator中，Schedulable封裝了是一個pool或者job的基本信息。層次調度算法大的思想與CapacityScheduler類資源搶占當一定時間（管理員可配置）內，某個pool中獲取的資源量少于最小共享量，或者公平共享量的一半，則調度器會找出哪個pool搶占了該pool的資源，并殺死相應數量的task以搶占資源。之所以要進行搶占，還是為了“公平”，即：保證每個pool能獲取到它應得到的資源。資源搶占當一定時間（管理員可配置）內，某個pool中獲取的資delayscheduling機制當出現空閑slot時，如果排在隊列前面的job對應的所有task均沒有locality特性，則該作業會延遲調度，直到一段時間后，該job出現locality的task或者發生超時，才不得不調度該job的task。有些人可能不了解locality，在此解釋如下：當出現空閑slot時，該slot來自某個節點，而該節點上存有部分數據，如果某個task所需要的數據正好位于該節點上，則將該slot分配給該task是非常好的，因為它避免了通過網絡讀取數據。delayscheduling機制當出現空閑slot時，如公平共享量計算方法公平共享量是基于最小共享量和共享資源量計算得到的，它反映的是某個pool經過資源共享（某些pool的資源用不了，會自動共享給其他pool）之后，一共可以獲取的資源總量，一般會大于等于最小共享量。如果每個pool沒有配置最小共享量，且提交了無限量的作業，則讓每個pool的slotsAssigned/weight值相同即可。（其中slotsAssgined表示分配給該pool的slot數，weight表示pool的權重）。而有了最小共享量minShare和pool中的需求量demand（該pool中所有作業尚需的slot總數）后，計算公平共享量fairShare需注意以下兩種情況：(1)某些pool中的最小共享量可能用不完(2)給配給某些pool的資源量小于其最小共享量公平共享量計算方法公平共享量是基于最小共享量和共享資源量計算公平共享量計算方法考慮到以上兩種情況，調度器設計了基于比率R的公平資源分配方法（設集群中資源總量為totalSlots）：[1]如果一個pool的demand<R*weight，則該pool的fairShare=demand[2]如果一個pool的minShare>weight，則該pool的fairShare=minShare[3]除此之外，所有pool的fairShare=R*weight[4]所有pool的的fairShare之和應為totalSlots通過以上算法計算出的公平共享量即為“公平調度器”的“公平”含義之所在，應盡量保證每個pool獲取的資源量為fairshare，如果一定時間期限內達不到，則搶占資源。公平共享量計算方法考慮到以上兩種情況，調度器設計了基于比率R公平共享量計算方法公平共享量計算方法公平調度器缺點新版本的調度器仍不支持大內存作業，而CapacityScheduler則早有了支持，其原理是：如果一個job需要較大內存，調度器會為該job分配多個slot，這樣，作業可使用這些slot對應的內存資源。公平調度器缺點新版本的調度器仍不支持大內存作業，而Capac大數據問題紐約證券交易所每天產生1TB的交易數據社交網站facebook的主機存儲著約10億張照片，占據PB級存儲空間互聯網檔案館存儲著約2PB數據，并以每月至少20TB的速度增長。瑞士日內瓦附近的大型強子對撞機每年產生約15PB的數據這么大的數據該怎么存儲和讀??？大數據問題紐約證券交易所每天產生1TB的交易數據傳統關系型數據庫（oracle）的成本Facebook的服務器大概1萬臺，按照oracle的標準10g版本計算大約需要21億元傳統關系型數據庫（oracle）的成本Facebook的服務Hadoop簡介Hadoop一個分布式系統基礎架構，由Apache基金會開發。用戶可以在不了解分布式底層細節的情況下，開發分布式程序。充分利用集群的威力高速運算和存儲。由HDFS、MapReduce、HBase、Hive和ZooKeeper等成員組成。其中，HDFS和MapReduce是兩個最基礎最重要的成員。HDFS是GoogleGFS的開源版本，一個高度容錯的分布式文件系統，它能夠提供高吞吐量的數據訪問，適合存儲海量（PB級）的大文件（通常超過64M），其原理如圖所示：Hadoop簡介Hadoop一個分布式系統基礎架構，由ApHadoop優點可擴展：不論是存儲的可擴展還是計算的可擴展都是Hadoop的設計根本。經濟：框架可以運行在任何普通的PC上。可靠：分布式文件系統的備份恢復機制以及MapReduce的任務監控保證了分布式處理的可靠性。（元數據磁盤錯誤，心跳測試，副本數，快照（目前還沒實現））高效：分布式文件系統的高效數據交互實現以及MapReduce結合LocalData處理的模式，為高效處理海量的信息作了基礎準備。Hadoop優點可擴展：不論是存儲的可擴展還是計算的可擴展都Hadoop在國內的分布情況Hadoop在國內的分布情況Hadoop作業調度默認調度算法FIFO公平份額調度算法FairScheduler計算能力調度算法CapacityScheduler作業調度總結

Hadoop作業調度默認調度算法FIFO默認調度算法FIFO簡介最早的HadoopMap/Reduce計算架構中，JobTracker在進行作業調度時使用的是FIFO(FirstInFirstOut)算法。所有用戶的作業都被提交到一個隊列中，然后由JobTracker先按照作業的優先級高低，再按照作業提交時間的先后順序選擇將被執行的作業。優點調度算法簡單明了，JobTracker工作負擔輕。缺點忽略了不同作業的需求差異。例如如果類似對海量數據進行統計分析的作業長期占據計算資源，那么在其后提交的交互型作業有可能遲遲得不到處理，從而影響到用戶的體驗。新的調度算法當前，新的調度器已經作為插件的形式集成在Hadoop當中。默認調度算法FIFO簡介公平份額調度算法FairSchedulerFairScheduler提出背景FairScheduler基礎知識FairScheduler兩個關鍵問題FairScheduler的配置公平份額調度算法FairSchedulerFairSchFairScheduler提出背景提出背景Facebook要處理生產型作業(數據統計分析,hive)、大型批處理作業(數據挖掘、機器學習)、小型交互型作業(hive查詢)。不同用戶提交的作業在計算時間、存儲空間、數據流量和響應時間上都有不同需求。為使hadoopmapreduce框架能夠應對多種類型作業并行執行，使得用戶具有良好的體驗，Facebook公司提出該算法。FairScheduler提出背景提出背景FairScheduler基礎知識設計思想盡可能保證所有的作業都能夠獲得等量的資源份額。系統中只有一個作業執行時，它將獨占集群所有資源。有其他作業被提交時就會有TaskTracker被釋放并分配給新提交的作業，以保證所有的作業都能夠獲得大體相同的計算資源。作業池用戶提交的作業將會放進一個能夠公平共享資源的pool(池)中。每個作業池設定了一個最低資源保障(aguaranteedminimumshare)，當一個池中包含job時，它至少可以獲得minimumshare的資源——最低保障資源份額機制。池中的作業獲得一定份額的資源?？梢酝ㄟ^配置文件限制每個池中的作業數量。缺省情況下，每個作業池中選擇將要執行的作業的策略是FIFO策略，先按照優先級高低排序，然后再按照提交時間排序。FairScheduler基礎知識設計思想FairScheduler基礎知識作業和作業池的權值weight缺省情況下，FairScheduler會為每一個用戶建立一個單獨的pool。所有用戶能夠獲得等量的資源份額而無論他提交了多少作業，而每個pool中，各個作業將平分分配給所在池的資源。實際應用中，無論是作業池還是作業，都被賦予一定的權值，并以此為依據獲得相應比例的資源。這種情況下，作業池和作業在資源分配時不是嚴格的平均分配，但這有利于根據作業的重要程度及實際需求合理分配資源。FairScheduler基礎知識作業和作業池的權值weiFairScheduler兩個關鍵問題如何選擇合適的作業執行默認是FIFO策略，此外還有一種基于缺額的策略。FairScheduler為每個作業定義了一個deficit(缺額)指標。Deficit是一個作業在理想情況下的獲得的計算資源和實際中獲得的計算資源之間的差距。FairScheduler會每隔幾百毫秒觀察每個作業中有多少任務已經在這個時間間隔內執行，并將結果與它應得的資源份額比較，以更新該作業的deficit值。一旦有空閑的tasktracker出現，首先分配給當前具有最高deficit值的作業。例外——如果系統中存在著尚未獲得最低資源保障的作業池，那么該池中的作業將會優先調度，而選擇池中的作業需要根據它們的deficit來決定。這樣做是為了盡可能滿足作業池最低保障資源份額的機制。FairScheduler兩個關鍵問題如何選擇合適的作業執FairScheduler兩個關鍵問題如何確定每個作業的資源份額缺省情況是平分資源，此外提供一種基于權值的資源分配方法。作業資源份額的計算是根據作業的權值將集群的資源總量劃分給各個可以運行的作業。默認情況下，權值基于作業優先級，每個優先級對應的權值是低一個優先級的2倍(優先級共有VERY_HIGH,HIGH,NORMAL,LOW,VERY_LOW五個等級，則VERY_HIGH具有4倍NORMAL的權值)。作業和作業池的權值可以在池配置文件中進行設定，例如可以基于作業的大小和提交時間來設定。作業池的最低資源保障也是按照權值比例分配給其中的作業。FairScheduler兩個關鍵問題如何確定每個作業的資計算能力調度CapacitySchedulerCapcityScheduler基礎知識CapcityScheduler一個關鍵問題CapcityScheduler內存管理CapcityScheduler的配置計算能力調度CapacitySchedulerCapciCapcitySchedule基礎知識基礎知識CapacityScheduler是由雅虎提出的作業調度算法，它提供了類似于FairScheduler算法的功能。CapacityScheduler中可以定義多個作業隊列(multiplequeues)，作業提交時將直接放入到一個隊列中。每個隊列都可以通過配置獲得一定數量的tasktracker資源用于處理map/reduce操作，調度算法將按照配置文件為隊列分配相應的計算資源量。對于已經分配給了某隊列但處于空閑的資源各個“忙”的隊列會分享它們。當某一隊列沒有能夠按照配置的數量值獲得足夠資源但是它的作業壓力增加了時，之前那些曾分配給它但又由于之前空閑被別的隊列所占用了的資源會在完成當前task后立即分配給回應屬的隊列。CapcitySchedule基礎知識基礎知識CapcitySchedule基礎知識基礎知識CapacityScheduler的每個隊列中采用的調度策略是FIFO算法。CapacityScheduler默認情況下不支持優先級，但是可以在配置文件中開啟此選項，如果支持優先級，調度算法就是帶有優先級的FIFO。CapacityScheduler不支持優先級搶占，一旦一個作業開始執行，在執行完之前它的資源不會被高優先級作業所搶占。CapacityScheduler對隊列中同一用戶提交的作業能夠獲得的資源百分比進行了限制以使同屬于一用戶的作業不能出現獨占資源的情況。CapcitySchedule基礎知識基礎知識CapcityScheduler一個關鍵問題如何選擇合適的作業去執行為隊列定義了一個指標—隊列中正在運行的任務數與其應該分得的計算資源(配置文件中為此隊列分配了相應數量的資源，而實際中該隊列可能沒有分配到)之間的比值。當系統中出現空閑的tasktracker，算法會首先選擇一個該比值最低的隊列。隊列被選中后，將按照作業優先級(如果支持的話)和提交時間順序選擇執行的作業。在選擇作業的時候，還需要考慮作業所屬的用戶是否已經超出了他所能使用的資源限制。此外，還會考慮tasktracker內存資源是否滿足作業的要求。CapcityScheduler一個關鍵問題如何選擇合適的CapcityScheduler內存管理內存資源的有效管理CapacityScheduler能有效地對hadoop集群的內存資源進行管理，以支持內存密集型應用。作業對內存資源需求高時，調度算法將把該作業的相關任務分配到內存資源充足的tasktracker上。在作業選擇過程中，CapacityScheduler會檢查空閑tasktracker上的內存資源是否滿足作業要求。tasktracker上的空閑資源(內存)數量值可以通過tasktracker的內存資源總量減去當前已經使用的內存數量得到，而后者包含在tasktracker向jobtracker發送的周期性心跳信息中。目前，基于內存的調度只能在linux平臺下起作用，關于內存調度的相關參數可以通過配置文件來設置。CapcityScheduler內存管理內存資源的有效管理Hadoop公平調度器算法解析※公平調度介紹※hadoop-0.20.2公平調度算法分析

基于缺額的調度算法變量定義相關算法※hadoop-0.21.0公平調度算法分析

層次調度算法Hadoop公平調度器算法解析※公平調度介紹公平調度介紹公平調度器按資源池（pool）來組織作業，并把資源公平的分到這些資源池里。默認情況下，每一個用戶擁有一個獨立的資源池，以使每個用戶都能獲得一份等同的集群資源而不管他們提交了多少作業。按用戶的Unix群組或作業配置（jobconf）屬性來設置作業的資源池也是可以的。在每一個資源池內，會使用公平共享（fairsharing）的方法在運行作業之間共享容量（capacity）。用戶也可以給予資源池相應的權重，以不按比例的方式共享集群。公平調度介紹公平調度器按資源池（pool）來組織作業，并把資公平調度介紹除了提供公平共享方法外，公平調度器允許賦給資源池保證（guaranteed）最小共享資源，這個用在確保特定用戶、群組或生產應用程序總能獲取到足夠的資源時是很有用的。當一個資源池包含作業時，它至少能獲取到它的最小共享資源，但是當資源池不完全需要它所擁有的保證共享資源時，額外的部分會在其它資源池間進行切分。公平調度介紹除了提供公平共享方法外，公平調度器允許賦給資源池公平調度介紹主要特點如下：?

支持多用戶多隊列?

資源公平共享（公平共享量由優先級決定）?

保證最小共享量?

支持時間片搶占?

限制作業并發量，以防止中間數據塞滿磁盤公平調度介紹主要特點如下：Pool資源池，或者作業池。每個pool里有一定量的資源（管理員配置），每個用戶屬于某個pool，其作業可使用這個pool中的資源，可限定每個pool中最大并發作業數和每個用戶最多提交作業數。默認情況下，一個linux用戶對應一個pool，而管理員也可以配以一個linuxgroup對應一個pool。pool實際上也可以稱為group或者隊列。Pool資源池，或者作業池。每個pool里有一定量的資源（最小共享量管理員可給每個pool配置一個最小共享量，調度器在分配資源時，需要保證每個pool中的作業至少獲取該數目的資源。一個常見的應用場景是，對產品pool設置最小共享量，而測試pool不設置，這樣，當可用資源有限時時，優先保證產品pool有資源可用。最小共享量管理員可給每個pool配置一個最小共享量，調度器在公平共享量當集群中存在多個pool時，某些pool中的資源可能用不了，這時候調度器會自動將這些pool中剩余的資源共享給其他需要的pool，其他這些pool獲取的共享資源多少主要由其poolweight決定，poolweight越大，獲取的資源越多。一個pool的最小共享量加上其獲取的共享資源數目，就是公平共享量。公平共享量當集群中存在多個pool時，某些pool中的資源可公平調度算法分析——變量定義★描述job信息的變量(JobInfo)jobWeight：作業的權重。實際計算時，map階段和reduce階段分開，分別記為mapWeight，reduceWeightjobDeficit：作業的缺額，即作業在理想調度器上所應得的計算時間與實際所獲得的計算時間的缺額，這個是測量作業的“不公平”待遇的度量標準。實際運算時將map階段和reduce階段分開，分別記為mapDeficit和reduceDeficit。公平調度算法分析——變量定義★描述job信息的變量(JobI公平調度算法分析——變量定義runningTasks：作業正在運行的task數。實際計算時，maptask和reducetask需分開，分別記為：runningMaps和runningReducesminSlots：作業在相應的pool中的最小slot保證量，實際計算時，map階段和reduce階段分開，分別記為：minMaps和minReducesjobFairShare：上次更新給該job分配的公平共享量，實際計算時，map階段和reduce階段分開，分別記為mapFairShare和reduceFairShare公平調度算法分析——變量定義runningTasks：作業正公平調度算法分析——變量定義★計算過程的中間變量poolWeight：pool的權重，這個可由用戶自己設定，默認為1。tasksNum：某個作業正在運行任務與尚未運行的任務（包括Speculative任務）數量和，有兩種task類型：maptask和reducetask，計算時需要分開priorityFactor：與作業優先級相關的因子，用于計算作業的權重，具體如圖：prioritypriorityFactorVERY_HIGH4.0HIGH2.0NORMAL1.0LOW0.5Default0.25公平調度算法分析——變量定義★計算過程的中間變量priori公平調度算法分析——變量定義poolRunningJobsWeightSum：pool中已經開始運行的所有作業的權重之和poolLowJobsWeightSum：在某個pool中，已經開始運行的，但尚需slot（tasksNum數量大于其最小共享量）的那些作業權重之和systemJobsWeightSum：系統（可能有很多pool）中可以運行的所有作業的權重之和timeDelta：兩次信息更新的時間間隔公平調度算法分析——變量定義poolRunningJobsW公平調度算法分析——相關算法當出現一個空閑slot時，公平調度器會將此slot分配給缺額最大的作業。系統每隔500毫秒（UPDATE_INTERVAL）更新一次信息（有一個專門的更新線程對job信息進行更新），包括：作業缺額（作業的其他屬性，如權重、最小共享量、公平共享量等，均是為計算缺額服務的）、權重、最小共享量、公平共享量等。公平調度算法分析——相關算法當出現一個空閑slot時，公平調公平調度算法分析——相關算法1)作業權重計算方法（1）默認情況下，權重是基于作業優先權的，但也可以基于作業的大小和年齡。權重的計算方法如下：（2）根據優先權計算權重：（3）根據用戶自定義的weightAdjuster類調整權重公平調度算法分析——相關算法1)作業權重計算方法公平調度算法分析——相關算法2)更新權重每個已經運行的作業權重更新公式：3)初始缺額計算每個作業的初始缺額mapDeficit,reduceDeficit設置為0.4)更新作業的最小共享量在每個pool中，將其擁有的slot按作業的權重分配給各個作業（由步驟(1)完成），分完之后將剩余的slot按作業的權重和缺額分配給仍需slot的作業（由步驟(2)和(3)完成），如果還有slot剩余，則將這些slot共享給其他pool。公平調度算法分析——相關算法2)更新權重公平調度算法分析——相關算法初始化：當前所有作業的最小共享量置零；pool的minMaps數或者minReduces數（由用戶在配置文件中設定）重復以下幾步，直到slotsLeft=0：公平調度算法分析——相關算法初始化：公平調度算法分析——相關算法（1）計算每個job的最小共享量：jobinfo.minMaps或jobinfo.minReduces首先計算該作業可獲得的共享值：根據當前pool的剩余slot數，調整該共享值：其中runnableNum表示作業尚需的slot數與正在運行的slot數之和，curMin表示作業的當前最小共享量（jobinfo.minMaps或jobinfo.minReduces），初始值為0。將slotsToGive作為最小共享量賦予相應的job。修改值為值減去slotsToGive。如果此輪循環中，slotsLeft值未變，即沒有slot分給任何作業，則將剩余的slot共享給pool中所有job，即，執行（2）（3）并結束算法：公平調度算法分析——相關算法（1）計算每個job的最小共享量公平調度算法分析——相關算法（2）將pool中的job按weight和deficit排序（3）按順序依次計算每個job的最小共享量。首先計算該作業可獲得的共享值：根據當前pool的剩余slot數，調整該共享值：將slotsToGive作為最小共享量賦予相應的job。修改slotsLeft值為slotsLeft值減去slotsToGive。需要注意的是，當執行完（2）（3）后，slotsLeft可能仍大于0，這時候會將剩余的slotsLeft個slot共享給其他pool。公平調度算法分析——相關算法（2）將pool中的job按we公平調度算法分析——相關算法5)更新公平共享量主要思想：基于作業權重和最小共享量計算公平共享量。首先，根據權重分配可用slot數，如果作業的最小共享量大于公平共享量，先要滿足最小共享量，更新可用slot數，重復以上步驟，直到所有作業的最小共享量小于或等于公平共享量，這樣，每個作業的最小共享量都得到了滿足，最后，所有作業平分剩下的slot數。公平調度算法分析——相關算法5)更新公平共享量公平調度算法分析——相關算法算法實現：初始化：當前所有作業的公平共享量置零；slotsLeft={系統中mapsl