大數(shù)據(jù)應(yīng)用的中存儲(chǔ)和處理問題剖析 課件

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

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

基于缺額的調(diào)度算法變量定義相關(guān)算法※hadoop-0.21.0公平調(diào)度算法分析

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

支持多用戶多隊(duì)列?

資源公平共享（公平共享量由優(yōu)先級(jí)決定）?

保證最小共享量?

支持時(shí)間片搶占?

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

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

基于缺額的調(diào)度算法變量定義相關(guān)算法※hadoop-0.21.0公平調(diào)度算法分析

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

支持多用戶多隊(duì)列?

資源公平共享（公平共享量由優(yōu)先級(jí)決定）?

保證最小共享量?

支持時(shí)間片搶占?

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