轉自： http://www.kankanews.com/ICkengine/archives/89892.shtml
dominant算法是Mesos的靈魂，不同于hadoop基于slot-based實作的fair scheduler和capacity scheduler，學習閱讀了一下論文“Dominant Resource Fairness: Fair Allocation of Multiple Resource Types”，順便簡單地翻譯了一下。以下是論文翻譯地正文。
——————————————————————————
我們考慮在一個包括不同資源類型的系統中的公平資源配置設定問題，其中不同使用者對資源有不同的要求。為了解決這個問題，我們提出了Dominant Resource Fairness(DRF)，一種針對不同資源類型的max-min fairness。首先DRF激勵使用者去共享資源，如果資源是在使用者之間被平均地切分，會保證沒有使用者會拿到更多資源。其次，DRF 是strategy-proof，使用者不能通過欺騙來擷取更多地資源配置設定。然後，RDF是envy-free（非嫉妒），沒有一個使用者會與其他使用者交換資源配置設定。最後，RDF配置設定是Pareto efficient，不可能通過減少一個使用者的資源配置設定來提升另一個使用者的資源配置設定。
我們在mesos 叢集資料總管上實作了一個DRF，顯示了它可以比slot-based 公平排程算法得到更好的吞吐量。
Introduce
在任何共享的計算機系統中，資源配置設定都是一個關鍵的構模組化塊。已經提出的最通用的配置設定政策是max-min fairness，這種政策會最大化系統中一個使用者收到的最小配置設定。假設每一個使用者都有足夠地請求，這種政策會給予每個使用者一份均等的資源。廣義的Max-min fairness包括權重(weight)的概念，使用者可以獲得與它的權重成正比的那一份資源。
權重max-min fairness的吸引力源于它的一般性和它能提供性能隔離的能力。權重max-min fairness模型可以支撐許多其他資源配置設定政策，包括優先級、deadline based allocation等。此外，權重max-min fairness確定隔離，一個使用者能確定收到它的那份資源，而不管其它使用者的需求。
鑒于這些特征，不同精确度的權重或非權重max-min fairness毫不意外地被大量已經提出的算法實作，如round-robin、proportional resource sharing、weighted fair queueing。這些算法已經被應用于不同的資源，包括鍊路帶寬、CPU、記憶體、存儲。
盡管已經在公平配置設定上做了大量地工作和實踐，但目前為止主要還是集中在單資源類型的場景下。甚至在多資源類型的環境下，使用者有異質資源請求，典型的資源配置設定做法還是使用單類型資源抽象。比如hadoop和Dryad的公平排程器，這兩種廣泛使用叢集計算架構，在資源配置設定時使用插槽（slot），slot就是對節點資源按照固定大小進行劃分而産生的分區。然而事實是叢集中不同的作業隊CPU、記憶體和IO資源有着不同的需求。
在這篇文章裡，我們會定位在多資源和異質使用者請求的環境下公平配置設定政策所遇到的問題。特别的，我們提出了Dominant Resource Fairness（DRF），一種通用的多資源的max-min fairness配置設定政策。DRF背後的直覺想法是在多環境下一個使用者的資源配置設定應該由使用者的dominant share（主導份額的資源）決定，dominant share是在所有已經配置設定給使用者的多種資源中，占據最大份額的一種資源。簡而言之，DRF試圖最大化所有使用者中最小的dominant share（一句話表達了DRF的思想）。舉個例子，假如使用者A運作CPU密集的任務而使用者B運作記憶體密集的任務，DRF會試圖均衡使用者A的CPU資源份額和使用者B的記憶體資源份額。在單個資源的情形下，那麼DRF就會退化為max-min fairness。
DRF的力量在于它所滿足的屬性。這些屬性都被單資源場景下的max-min fairness所滿足，但在多資源場景中是不尋常的。有四種這種類型的特性，分别是：sharing incentive、strategy-proofness、Pareto efficiency和envy-freeness。
DRF是通過確定系統的資源在使用者之間是靜态和均衡地進行配置設定來提供sharing incentive，使用者不能獲得比其他使用者更多的資源。此外，DRF是strategy-proof，使用者不能通過謊報其資源需求來獲得更多的資源。DRF是Pareto-efficient，在滿足其他特性的同時，配置設定所有可以利用的資源，不用取代現有的資源配置設定。最後，DRF是envy-free，使用者會更喜歡其他使用者的資源配置設定。
我們在mesos中實作和評估了DRF，mesos是一種多叢集計算架構的資料總管。可以運作hadoop和MPI。我們将DRF與hadoop和Dryad中所使用的slot-based fair sharing scheme進行比較顯示，slot-based fair sharing能導緻更差的性能，某些不公平的工作負載懲罰，同時提供更弱的隔離保證。
本文主要聚焦資料中心的資源配置設定，我們相信DRF是可以廣泛地應用于使用者有異質需求的多資源環境，比如在多核機器上。
2 Motivation
雖然之前關于權重max-min fairness的工作都集中在單一資源的情況，雲計算和多核處理器的出現增加了對多資源和異構使用者請求的環境下的配置設定政策的需求。多資源意味着不同種類型的資源，而不是多種可以互相互動的資源執行個體。
為了激勵多資源配置設定的需求，我們在facebook 2000個節點的hadoop叢集上測量任務的資源使用率超過一個月時間，見下圖。
圖中圓球的位置标示了任務的記憶體和cpu消耗，圓球的大小标示在某一個區域的任務數取對數後的值（logN,N為任務數目），因而大部分任務都是CPU密集的，而現存memory密集的任務大都是reduce操作。
現存的叢集公平排程器，如Quincy和hadoop fair scheduler都忽略了使用者的異質需求（heterogeneity of user demands），以插槽（slot）為粒度進行資源配置設定，其中一個slot是一個節點上固定比例的資源。這導緻了低效的配置設定，一個slot往往與任務的需求不比對。
（一個月時間内，facebook 2000個節點的叢集上任務需求與slot比率的正态分布圖，需求與slot比率為2.0表示一個任務需要的CPU或記憶體是一個slot所包含的CPU或記憶體的兩倍）
見上圖，上圖量化了hadoop mapreduce 公平排程器的公平性和隔離性的級别。這附圖顯示了任務的CPU需求和slot的CPU share之間的比率的正态分布圖以及任務的記憶體需求和slot的記憶體share之間的比率的正态分布圖。我們簡單地使用cpu和記憶體的總量除以slot數目來計算單個slot的記憶體和cpu share。比率為1表示任務的需求完美地比對slot的資源，比率低于1表示任務沒有充分地利用slot的資源，比率高于1表示任務已經過載地使用slot的資源，這會導緻系統颠簸。圖2顯示了大部分任務都沒有充分利用slot資源或者過載地利用slot資源。修改每台機器的slot不能解決這個問題，這樣做可能會導緻更低的總使用率或者更多的任務因為過載而導緻更差的性能。
3 Allocation Properties
現在我們為多資源和異質請求（heterogeneous requests）設計一個max-min fair配置設定政策。為了說明這個問題，我們考慮一個有9個cpu和18GB的系統，有兩個使用者：使用者A的每個任務都請求（1CPU，4GB）資源；使用者B的每個任務都請求（3CPU，4GB）資源。如何為這種情況建構一個公平配置設定政策？
其中一個可能性是為每個使用者配置設定每一種資源的一半。另一種可能性是為每個使用者配置設定等量的各種資源合計（比如，cpu加上記憶體）。雖然能比較容易想出多種可能的公平配置設定，但不清楚如何對這些配置設定政策進行證明和比較。
為了應對這種挑戰，我們先從一組特性開始，我們相信任何對多個資源和異構請求的資源配置設定政策都應該滿足這些特征。然後用這些特性指引公平配置設定政策的指定。我們發現了如下四個特性是重要的。
1、sharing incentive：每一個使用者都必須更好地共享叢集，而不是在叢集中專享他們自己的分區。考慮一個叢集具有相同的節點（每個節點都一樣）和n個使用者，一個使用者不能在超過1/n資源的叢集分區中配置設定更多的任務。一個使用者最多隻能分享1/n的資源。
2、Strategy-proofness：使用者不能從謊報資源請求中得到好處。使用者不能通過欺騙來提升它的配置設定。
3、Envy-freeness：一個使用者不應該更喜歡其他使用者的配置設定。這點特性包含在公平的概念中。
4、Pareto efficiency：不可能出現既能增加一個使用者的配置設定而不會降低至少另一個使用者的配置設定。這個特性非常重要，它使得在滿足其他特性的基礎上使系統使用率最大化。
我們簡單地評價一下strategy-proofness和sharing incentive特性，我們相信這兩個特性在資料中心環境下特别重要。
從我們與雲計算營運商的交談中聽到的傳聞和證據顯示strategy-proofness是非常重要的，因為，使用者試探操縱排程器是非常普遍的。比如，yahoo的一個Hadoop MapReduce叢集對map和reduce任務有不同的slot。一個使用者發現map的slot存在競争，是以就将他的所有任務都長期地運作在reduce階段，手工地執行本來應該在mapreduce的map階段執行地工作。另一個大型搜尋公司為使用者高使用率的作業提供了專門的機器，這個公司馬上就發現使用者在他們的代碼中散布無限循環用于人為地提升使用率級别。
此外，任何滿足sharing incentive特性的政策同樣也提供性能隔離，是以不管其他使用者的需求如何，它都必須保證每個使用者的最小配置設定，（打個比方，一個使用者不能比做得擁有1/n叢集資源更差的情形）。
在單個資源的情況下，max-min fair可以很容易地做到滿足以上所有特性。然而，在多資源和異質使用者需求的情況下，達到這些特性是不簡單的。比如在微觀經濟理論中首選的公平配置設定機制 Competitive Equilibrium from Equal Incomes不滿足strategy proof。
除了以上四種特性，我們考慮另外四種不錯的特性：
1、Single resource fairness：對于單個資源，解決方案會蛻變為max-min fairness。
2、Bottleneck fairness：假如一種資源是緊缺的資源，然後對于這個資源，解決方案必須退化為max-min fairness。
3、Population monotonicity：當一個使用者離開系統，返還其占用的資源，那麼任何剩下的使用者的資源配置設定不會減少。
4、Resource monotonicity：假如更多的資源添加到系統中，任何現存使用者的資源配置設定都不會減少。
4 Dominant Resource Fairness(DRF)
我們提出了Dominant Resource Fairness，一種針對多種資源類型的配置設定政策，滿足前一章中的所有四種特征。對于所有使用者，DRF會計算配置設定給使用者的每一種資源的占用率（share），使用者所有占有率中的最大值稱作使用者的dominant share，與dominant share對應的資源被稱作dominant resource。不同的使用者有不同的dominant resource。
舉個例子，運作計算受限作業（computation-bound）的使用者的dominant resource是cpu，而運作IO受限（IO-bound）作業的使用者的dominant resource是帶寬。
在各個使用者的dominant share之間，DRF簡單地采用最大最小公平（max-min fairness），設法中最大化系統最小的dominant share，然後是第二小的，以此類推。
在這一章我們讨論有n個使用者和m種資源的計算模型。每個使用者都運作互相獨立的任務，每個任務都由一個資源需求向量來描述，需求向量執行了這個任務所需要的各種資源的值，比如{1 CPU, 4GB}。在通常情況下，各種任務都有不同的需求。
4.1 一個例子
考慮一個9CPU、18GBRAM的系統，擁有兩個使用者，其中使用者A運作的任務的需求向量為{1CPU, 4GB}，使用者B運作的任務的需求向量為{3CPU，1GB}。
在上述方案中，A的每個任務消耗總cpu的1/9和總記憶體的2/9，是以A的dominant resource是記憶體；B的每個任務消耗總cpu的1/3和總記憶體的1/18，是以B的dominant resource為CPU。DRF會均衡使用者的dominant shares，如圖三所示，三個使用者A的任務總共消耗了{3CPU，12GB}，兩個使用者B的任務總共消耗了{6CPU，2GB}；在這個配置設定中，每一個使用者的dominant share是相等的，使用者A獲得了2/3的RAM，而使用者B獲得了2/3的CPU。
以上的這個配置設定可以用如下方式計算出來：x和y分别是使用者A和使用者B的配置設定任務的數目，那麼使用者A消耗了{xCPU，4xGB}，使用者B消耗了{3yCPU，yGB}，在圖三中使用者A和使用者B消耗了同等dominant resource；使用者A的dominant share為4x/18，使用者B的dominant share為3y/9。是以DRF配置設定可以通過求解以下的優化問題來得到：
求解以上問題，可以得出x = 3以及y = 2。因而使用者A獲得{3CPU，12GB}，B得到{6CPU， 2GB}。
需要注意的是，DRF并不是總需要使使用者的dominant shares相等。當一個使用者總的需求是被滿足，使用者不會需要更多的任務，是以多餘的資源可以在其他使用者之間進行配置設定，就好像max-min fairness。此外，如果一種資源被耗盡，那些不需要此種資源的使用者仍然可以繼續接收到更多其他類型的資源。
DRF Scheduling Algorithm
算法1顯示了DRF排程的僞碼，這個算法會跟蹤配置設定給每個使用者的總資源以及使用者的dominant share，Si。每一步，DRF都會從擁有最低dominant share的使用者中選擇一個任務準備運作。假如使用者的任務需求能被滿足，即系統中有足夠可用的資源，那麼使用者的任務就會被加載啟動。我們考慮一般情況，即一個使用者擁有不用需求向量的任務，我們使用變量Di來表示使用者i下一個要運作加載的任務。為了簡單起見，僞碼沒有捕獲任務結束事件，在這種情況下，使用者會釋放任務的資源，DRF會再一次選擇擁有最低dominant share的使用者去運作它的任務。
考慮4.1的兩個使用者的簡單例子，table1說明了DRF對這個簡單例子的配置設定過程。DRF首先選擇B來運作一個任務，結果B的資源占用率變為{3/9,1/18}，B的dominant share變成了max{3/9，1/18} = 1/3。接下來DRF選擇A，因為此時A的dominant share為0。這個過程持續進行，直到不再可能運作任務新任務，在這種情況下，一般會出現CPU飽和。
在以上配置設定過程的最後，使用者A會得到{3CPU, 12GB}，同僚B得到了{6CPU， 2GB}，每一個使用者都獲得了2/3的dominant resource。
注意到，在這個例子中，一旦任何資源達到飽和，那麼配置設定過程就會終止。然而通常情況下，它可以在某些資源已經飽和的情況下繼續配置設定任務，因為有些任務對已經飽和的資源沒有任何要求。
以上這個算法在實作的時候可以用二叉堆來存儲每一個使用者的dominant share。對于n個使用者，每一次排程決定都消耗了O(logn)時間。
Weighted DRF
在實踐中，在許多種情況下，均等地在使用者之間配置設定資源并不是理想的政策。實際上我們可能想要配置設定更多的資源給運作重要作業的使用者，或者給為叢集貢獻出更多資源的使用者。為了達到這個目的，我們提出了Weighted DRF，一個概括了DRF和weighted max-min fairness的算法。
在weighted DRF中，每個使用者i都關聯一個權重向量Wi = {Wi1, ……， Wim}，其中Wi,j表示使用者i對資源j的權重。那麼使用者i的dominant share的定義為Si = max{Ui,j / Wi,j}，其中Ui,j是使用者i對資源j的占有率。一種特别的情況就是所有使用者i的權重都是相等，在這種情況下，Weighted DRF就退化為DRF。
5 Alternative Fair Allocation Policies
在一個多資源的系統中，定義一個公平配置設定不是件簡單的事情，公平這個概念本身就是值得商榷的。在我們所做的努力中，我們在使用DRF之前考慮過多種配置設定政策，但隻有DRF能滿足所有四個特性：sharing incentive、strategy-proofness、Pareto efficiency、envy-freeness。
在這一章中，我們調查了兩種可選的替代者：Asset Fairness，一種簡單且直覺的政策，為了均衡配置設定給每個使用者的聚合資源；以及Competitive Equilibrium from Equal Incomes(CEEI)，一種在微觀經濟領域的公平配置設定資源的可選政策。我們将這些政策與DRF進行比較。
5.1 Asset Fairness
Asset Fairness的設計想法是不同資源的相同占用率是等值的，比如1%的cpu使用率和1%記憶體和1%的帶寬使用率是相同的。在這個前提之下，Asset Fairness 嘗試去均衡配置設定給每個使用者的聚合資源值（各種資源的累加）。特别地，Asset Fairness會計算每個使用者i的聚合資源占用率
，其中Si,j是使用者i對于資源j的占用率。然後在使用者的總占用率上使用max-min fairness，比如總是重複地運作擁有最小聚合資源占用率使用者的任務。考慮第四章中的例子，系統擁有9CPUS和18GB RAM，既然RAM的GB數量是CPU數量的兩倍，一個CPU相當于2GB的RAM。假設1GB的RAM為$1，那麼1CPU為￥2，那麼可以使用者A的每個任務需要花費￥6，而使用者B的每個任務需要花費￥7。設定x和y分别為Asset fairness算法配置設定給使用者A和使用者B的任務數。
Asset-fair配置設定問題可以通過求解以下問題來得到(這個問題假設使用者A和使用者B最後得到了相同的聚合資源占用率)
求解上面這個問題，可以得到x=2.52，以及y=2.16,。因而使用者A得到了{2.5 CPUS，10.1GB}，使用者B得到了{6.5CPUs，2.2 GB}。
這個配置設定政策的簡單性很吸引人，但它有一個重大的缺陷：它違反了sharing incentive特性。Assert fairness可以導緻一個使用者擷取了小于總資源的1/n，其中n為總的使用者數目。
5.2 Competitive Equilibrium from Equal Incomes
在微經濟理論中，公平配置設定資源的首選方法是Competitive Equilibrium from Equal Incomes(CEEI)，在CEEI中，每個使用者在初始化時接收到所有資源的1/n，接下來每個使用者會在一個完全競争的市場與其他使用者交易資源。CEEI的輸出同時滿足envy-free和pareto efficient。
更加精準描述是：CEEI配置設定是由nash bargaining solution給出的，nash bargaining solution會選擇可行的配置設定政策，使得
最大化，其中
是使用者i擷取資源
的方式或功能，為了簡化對比，我們将一個使用者得到其資源配置設定的方式簡化為就是其dominant share,
。
考慮第四章兩使用者的例子，回憶一下使用者A的dominant share為4x/18 = 2x/9，而使用者B的dominant share為3y/9 = y/3。其中x為使用者A的任務數目，y為使用者B的任務數目。最大化商品的dominant shares就等同于最大化商品的x.y。因為CEEI就變為解決如下的優化問題：
解決以上問題可以得到x= 45/11，y=18/11。因而使用者A獲得了{4.1 CPUs, 16.4 GB}，同時使用者B獲得了{4.9 CPUs, 1.6GB}。不幸的是，雖然CEEI同時滿足envy-free和Pareto efficient，但不滿足strategy-proof特性，因而使用者可以通過謊報他們的資源需求來提升他們的資源配置設定。
5.3 Comparison with DRF
為了給讀者對Asset Fairness和CEEI有一個直覺的了解，我們在下圖中，将三種算法資源配置設定進行對比。
我們看DRF使得使用者的dominant share趨于均衡。而Asset Fairness使得使用者的總資源配置設定的百分比趨于均衡。最後，因為CEEI假設有一個充分競争市場，它找到了一個滿足市場結清的解決方案，使得所有資源都得到配置設定，不幸的是這個精确的特性使得CEEI可能會被欺騙，使用者可以通過聲明它需要更多地未充分利用的資源，導緻CEEI向這個使用者賦予更多的任務來達到市場結清的目标。
6 Analysis
第六章主要從第三章提出的8種配置設定特性來分析asset fairness、CEEI和DRF。下面這個表顯示了三種配置設定政策支援的不同特征。
作者zy，QQ105789990