Apache Mesos調度機制
1. 前言
調度器是Mesos的核心部件，主要負責將各個slave上資源分配給各個framework，常見的調度機制有FIFO，Fair Scheduler，Capacity Scheduler，Quincy，Condor等。Mesos為了支持多framework接入，采用了雙層調度機制，首先，由mesos中的 allocator將資源分配給framework，然后又由framework自己的調度器將資源分配給任務。本文重點介紹mesos中的 allocator模塊。
（什么是apache mesos？參考：《統一資源管理與調度平臺（系統）介紹》,本文分析基于Mesos SVN Revision 1327410）
2. Mesos調度機制
Mesos中的調度機制被稱為“Resource Offer”，采用了基于資源量的調度機制，這不同于Hadoop中的基于slot的機制。在mesos中，slave直接將資源量（CPU和內存）匯報 給master，由master將資源量按照某種機制分配給framework，其中，“某種機制”是“Dominant Resource Fairness（DRF）”
對于類似mesos采用雙層調度框架的系統，在設計時，需要解決以下問題：“Mesos在不知道各個framework資源需求的情況下，如何滿足 其需求？”，更具體一些，“Mesos在不知道framework中哪些數據存放在哪些節點情況下，如何做到數據locality？”為了解決該問 題，mesos提供了“reject offer”機制，允許framework暫時拒絕不滿足其資源需求的slave，在此，mesos采用了類似于Hadoop中的“delay scheduling“調度機制。
在mesos中，作業調度是一個分布式的過程，當出現失敗情況時，需要表現出一定的高效性和魯棒性。為此，mesos提供了以下機制：
（1）filters機制。 每次調度過程，mesos-master需要與framework-scheduler進行通信，如果有些framework總是拒絕slave，那么由 于額外的通信開銷會使得調度性能低效。為此避免不必要的通信，mesos提供了filters機制，允許framework只接收“剩余資源量大于L的 slave”或者“只接收node列表中的slave”。
（2）rescinds機制。如果某個framework在一定的時間內沒有為分配的資源返回對應的任務，則mesos會回收其資源量，并將這些資源分配給其他framework。
3. Dominant Resource Fairness（DRF）
DRF是一種支持多資源的max-min fair 資源分配機制，其中max表示max{CPU,mem}，而min表示min{user1,user2,…}=min{max{CPU1,mem1}, max{CPU2,mem2}, …}，其中user代表mesos中的framework，算法偽代碼如下圖所示：
舉例說明，假設系統中共有9 CPUs 和18 GB RAM，有兩個user（framework）分別運行了兩種任務，分別需要的資源量為<1 CPU, 4 GB> 和 <3 CPUs, 1 GB>。對于用戶A，每個task要消耗總CPU的1/9和總內存的2/9，因而A的支配性資源為內存；對于用戶B，每個task要消耗總CPU的 1/3和總內存的1/18，因而B的支配性資源為CPU。DRF將均衡所有用戶的支配性資源，即：A獲取的資源量為：<3 CPUs，12 GB>，可運行3個task；而B獲取的資源量為<6 CPUs, 2GB>，可運行2個task，這樣分配，每個用戶獲取了相同比例的支配性資源，即：A獲取了2/3的RAMs，B獲取了2/3的CPUs。
DRF算法的一個可能的調度序列如下圖所示：
DRF的好處是可滿足四個特性，即：Sharing incentive，Strategy-proofness，Envy-freeness和Pareto efficiency，具體含義參考后面給出的“參考資料”。
4. Mesos調度問題
Mesos中的DRF調度算法過分的追求公平，沒有考慮到實際的應用需求。在實際生產線上，往往需要類似于Hadoop中Capacity Scheduler的調度機制，將所有資源分成若干個queue，每個queue分配一定量的資源，每個user有一定的資源使用上限；更使用的調度策略 是應該支持每個queue可單獨定制自己的調度器策略，如：FIFO，Priority等。
由于Mesos采用了雙層調度機制，在實際調度時，將面臨設計決策問題：***層和第二層調度器分別實現哪幾個調度機制，即：將大部分調度機制放到***層調度器，還是***層調度器僅支持簡單的資源分配（分配比例由管理員指定）？
Mesos采用了Resource Offer機制（不同于Hadoop中的基于slot的調度機制），這種調度機制面臨著資源碎片問題，即：每個節點上的資源不可能全部被分配完，剩下的一點可能不足以讓任何任務運行，這樣，便產生了類似于操作系統中的內存碎片問題。
5. 參考資料
（1）Dominant Resource Fairness: Fair Allocation of Multiple Resources Types. A. Ghodsi, M. Zaharia, B. Hindman, A. Konwinski, S. Shenker, and I. Stoica, NSDI 2011, March 2011
