公平調(diào)度算法分析

1、.在Hadoop-0.21.0版本中，F(xiàn)air Scheduler代碼結(jié)構(gòu)有了較大變化（注意，最近的0.23.0版本與0.21.0基本相同），且核心調(diào)度算法也做了重大修改，使之更合理，更完善。本文主要分析了新版Hadoop中公平調(diào)度器的新特性。如果你不了解舊版本Hadoop的Fair Scheduler算法，可參考這篇文章：Hadoop-0.20.2公平調(diào)度器算法解析 。1. Hadoop-0.21.0版本公平調(diào)度器新特性(1) 將之前（0.21.0之前版本）的基于缺額的調(diào)度算法改為層次調(diào)度算法(2) 支持資源搶占(3) 添加delay scheduling機(jī)制，使調(diào)度策略更優(yōu)。(4) 每個(gè)隊(duì)

2、列的調(diào)度策略可以配置，支持兩種調(diào)度策略，分別為FIFO和FAIR，不管采用哪種調(diào)度策略，以上三個(gè)功能全部支持。2. 層次調(diào)度算法2.1 改進(jìn)動(dòng)機(jī)之前的Fair Scheduler采用了基于缺額調(diào)度算法，主要思想是：將作業(yè)的優(yōu)先級(jí)轉(zhuǎn)化成權(quán)重，優(yōu)先級(jí)越高權(quán)重越大，而權(quán)重越大，獲得的資源越多，通過(guò)權(quán)重計(jì)算出的資源就是“公平共享量”，這是理想狀態(tài)下，每個(gè)作業(yè)應(yīng)得到資源量，而在實(shí)際情況下，可能獲取不到這些資源，因而可以得到一個(gè)“理想和現(xiàn)實(shí)之間的差距”，為了是這個(gè)差距更能體現(xiàn)實(shí)際意義，又將時(shí)間融合進(jìn)去，即：“理想和現(xiàn)實(shí)之差乘以時(shí)間”，這就是缺額（缺額是累加的，如果一個(gè)作業(yè)為獲得資源，其缺額會(huì)隨著時(shí)間不段增

3、大，直到能夠排到隊(duì)列前頭）。每次出現(xiàn)空閑資源時(shí)，優(yōu)先選擇缺額大的作業(yè)，以便達(dá)到公平調(diào)度的目的。這個(gè)調(diào)度器在Yahoo和Cloudera內(nèi)部均被采用，但在使用過(guò)程中，會(huì)出現(xiàn)以下現(xiàn)象：（1） 用戶提交兩個(gè)作業(yè)，其中一個(gè)提交時(shí)間早一些，因而占下了集群中所有的資源，而第二個(gè)作業(yè)以一半集群資源的速度積累缺額，直到一段時(shí)間之后，它的缺額才足以使得達(dá)到可以獲取資源的資格；（2） 當(dāng)用戶繼續(xù)提交大量作業(yè)時(shí)，由于第二個(gè)作業(yè)的缺額非常大，則后面的作業(yè)完全獲取不到資源。要消除這種現(xiàn)象，則需要對(duì)調(diào)度算法進(jìn)行改進(jìn)一種改進(jìn)方法是每隔一段時(shí)間重置缺額，而新版公平調(diào)度器則采用了以下算法。2.2 新調(diào)度算法首先介紹幾個(gè)概念：P

4、ool：資源池，或者作業(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è)linux group對(duì)應(yīng)一個(gè)pool。pool實(shí)際上也可以稱為group或者隊(duì)列。最小共享量：管理員可給每個(gè)pool配置一個(gè)最小共享量，調(diào)度器在分配資源時(shí)，需要保證每個(gè)pool中的作業(yè)至少獲取該數(shù)目的資源。一個(gè)常見(jiàn)的應(yīng)用場(chǎng)景是，對(duì)產(chǎn)品pool設(shè)置最小共享量，而測(cè)試pool不設(shè)置，這樣，當(dāng)可用資源有限時(shí)時(shí)，優(yōu)先保證產(chǎn)品pool有資源可

5、用。公平共享量：當(dāng)集群中存在多個(gè)pool時(shí)，某些pool中的資源可能用不了，這時(shí)候調(diào)度器會(huì)自動(dòng)將這些pool中剩余的資源共享給其他需要的pool，其他這些pool獲取的共享資源多少主要由其pool weight決定，pool weight越大，獲取的資源越多。 一個(gè)pool的最小共享量加上其獲取的共享資源數(shù)目，就是公平共享量。下面正式介紹公平調(diào)度器的層次調(diào)度算法，大的思想與Capacity Scheduler類似，首先選擇一個(gè)pool，然后從該pool中選擇一個(gè)job，最后從該job中選擇一個(gè)locality的task。其中，選擇pool和job的策略相同，均采用了FairShareCompa

6、rator比較器對(duì)pool或者job進(jìn)行排序，然后從頭到尾掃描隊(duì)列，選出合適的pool或者job。在FairShareComparator中，Schedulable封裝了是一個(gè)pool或者job的基本信息。123456789101112131415161718192021222324252627282930313233public static class FairShareComparator implements Comparator<Schedulable> Overridepublic int compare(Schedulable s1, Schedulable s2)

7、double minShareRatio1, minShareRatio2; double tasksToWeightRatio1, tasksToWeightRatio2; int minShare1 = Math.min(s1.getMinShare(), s1.getDemand(); int minShare2 = Math.min(s2.getMinShare(), s2.getDemand(); boolean s1Needy = s1.getRunningTasks() < minShare1; boolean s2Needy = s2.getRunningTasks()

8、< minShare2; minShareRatio1 = s1.getRunningTasks() / Math.max(minShare1, 1.0); minShareRatio2 = s2.getRunningTasks() / Math.max(minShare2, 1.0); tasksToWeightRatio1 = s1.getRunningTasks() / s1.getWeight(); tasksToWeightRatio2 = s2.getRunningTasks() / s2.getWeight(); int res = 0; if (s1Needy &

9、& !s2Needy) res = -1; else if (s2Needy && !s1Needy) res = 1; else if (s1Needy && s2Needy) res = (int) Math.signum(minShareRatio1 - minShareRatio2); else / Neither schedulable is needy res = (int) Math.signum(tasksToWeightRatio1 - tasksToWeightRatio2); if (res = 0) / Jobs are tied

10、 in fairness ratio. Break the tie by submit time and job / name to get a deterministic ordering, which is useful for unit tests. res = (int) Math.signum(s1.getStartTime() - s2.getStartTime(); if (res = 0) res = s1.getName().compareTo(s2.getName(); return res; 3. 資源搶占當(dāng)一定時(shí)間（管理員可配置）內(nèi)，某個(gè)pool中獲取的資源量少于最小共

11、享量，或者公平共享量的一半，則調(diào)度器會(huì)找出哪個(gè)pool搶占了該pool的資源，并殺死相應(yīng)數(shù)量的task以搶占資源。之所以要進(jìn)行搶占，還是為了“公平”，即：保證每個(gè)pool能獲取到它應(yīng)得到的資源。4. delay scheduling機(jī)制當(dāng)出現(xiàn)空閑slot時(shí)，如果排在隊(duì)列前面的job對(duì)應(yīng)的所有task均沒(méi)有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來(lái)自某個(gè)節(jié)點(diǎn)，而該節(jié)點(diǎn)上存有部分?jǐn)?shù)據(jù)，如果某個(gè)task所需要的數(shù)據(jù)正好位

12、于該節(jié)點(diǎn)上，則將該slot分配給該task是非常好的，因?yàn)樗苊饬送ㄟ^(guò)網(wǎng)絡(luò)讀取數(shù)據(jù)。5. 公平共享量計(jì)算方法最后再說(shuō)一下pool的公平共享量的計(jì)算方法。公平共享量是基于最小共享量和共享資源量計(jì)算得到的，它反映的是某個(gè)pool經(jīng)過(guò)資源共享（某些pool的資源用不了，會(huì)自動(dòng)共享給其他pool）之后，一共可以獲取的資源總量，一般會(huì)大于等于最小共享量。如果每個(gè)pool沒(méi)有配置最小共享量，且提交了無(wú)限量的作業(yè)，則讓每個(gè)pool的slotsAssigned / weight值相同即可。（其中slotsAssgined表示分配給該pool的slot數(shù)，weight表示pool的權(quán)重）。而有了最小共享量min

13、Share和pool中的需求量demand（該pool中所有作業(yè)尚需的slot總數(shù)）后，計(jì)算公平共享量fairShare需注意以下兩種情況：（1） 某些pool中的最小共享量可能用不完（2） 給配給某些pool的資源量小于其最小共享量考慮到以上兩種情況，調(diào)度器設(shè)計(jì)了基于比率R的公平資源分配方法（設(shè)集群中資源總量為totalSlots）：1 如果一個(gè)pool的demand<R*weight，則該pool的fairShare=demand2 如果一個(gè)pool的minShare>weight，則該pool的fairShare=minShare3 除此之外，所有pool的fairShare=R*weight4 所有pool的的fairShare之和應(yīng)為totalSlots通過(guò)以上算法計(jì)算出的公平共享量即為“公平調(diào)度器”的“公平”含義之所在，應(yīng)盡量保證每個(gè)pool獲取的資源量為fairshare，如果一定時(shí)間期限內(nèi)達(dá)不到，則搶占資源。比率R表示weight-to-slot，即weig