這篇博客是關于大型機群任務調度系列的***篇，資源調度在Amazon、Google、Facebook、微軟或者Yahoo已經有很好實現，在其 它地方的需求也在增長。調度是很重要的課題，因為它直接跟運行集群的投入有關：一個不好的調度器會造成低利用率，昂貴投入的硬件資源被白白浪費。而光靠它 自己也無法實現高利用率，因為資源利用相抵觸的負載必須要仔細配置，正確調度。

架構演進

這篇博客討論了最近幾年調度架構如何演進，為什么會這樣。圖一演示了不同的方法：灰色方塊對應一個設備，不同顏色圈對應一個任務，有“S”的方形代表一個調度器。箭頭代表調度器的調度決定；三種顏色代表不同工作負載（例如，網站服務，批量分析，和機器學習）

圖一：不同調度架構，灰色框代表集群設備，圓圈代表任務，Si代表調度器。

（a）單體式調度器（b）二級調度 （c）共享狀態調度 （d）分布式調度 (e) 混合式調度

許多集群架構，例如大量高性能計算（HPC），使用的是Borg調度器，它跟Hadoop調度器和Kubernetes調度器完全不同，是單體式調度。

單體式調度

單一調度進程運行在一臺物理機內（例如Hadoop V1中JobTacker，Kubernetes中的kube-scheduler），將任務指派給集群內其它物理機。所有負載都服從于一個調度器，所有 任務都通過這一個調度邏輯運行（參見圖一a）。這種架構最簡單格式唯一，在此基礎上發展起了很多負載的調度器，例如Paragon和Quasar調度器， 采用機器學習方法來避免不同負載之間資源競爭。

今天集群都運行著不同類型的應用（與之相對應的是MapReduce早期作業場景），然而，采用單一調度器來處理這么復雜異構負載會很棘手，有幾個原因：

1. 調度器必須區分對待長期運行服務作業和批量分析作業，這是合理的需求。

2. 因為不同應用有不同的需求，催生調度器內加入更多功能，增加業務邏輯和部署方式。

3. 調度器處理任務順序變成一個問題：如果調度器不仔細設計，隊列效果（例如線頭阻塞head-of-line blocking）和回滾會成為問題。

總之，這聽起來像是給工程師帶來噩夢，調度器維護者面對的沒完沒了的功能請求證實了這點。

二級調度

二級調度通過將資源調度和任務調度分離解決了這個問題，這使得任務調度邏輯不僅可以根據不同應用要求而進行裁剪，而且保留了在集群之間共享資源的可 能性。盡管側重點不同，Mesos和 YARN集群管理都使用了這種方法：Mesos中，資源是主動提供（offer）給應用層調度，而YARN則允許應用層調度請求（request）資源 （，并且隨后接受被分配資源）。圖一b展示了這一概念，作業負責調度（S0-S2）跟資源管理器交互，資源管理器則給每個作業分配動態資源。這一方案賦予 客戶靈活調度作業策略的可能性。

然而，通過二級調度解決問題也有問題：應用層調度將資源全局調度隱藏起來，也就是說，不再能看到全局性的可選資源配置。相反，只能看到資源管理器主 動提供（offer，對應于Mesos）或者請求/分配（request/allocate，對應于YARN）給應用的資源。由此帶來一些問題：

1. 重入優先權（也就是高優先權會將低優先權任務剔除）實現變的很困難。在基于offer模式，被運行中任務占用的資源對高一級調度器不可見；在基于request模式，底層資源管理器必須理解重入策略（跟應用相關）。

2. 調度器不能介入運行中業務，有可能減低資源使用效率（例如，“饑餓鄰居”占據了IO帶寬），因為調度器看不見他們。

3. 應用相關調度器更關注底層資源使用的不同情況，但是他們唯一選擇資源的方法就是資源管理器提供的Offer/request接口，這個接口很容易變的很復雜。

共享狀態架構

共享狀態架構通過采用半分布式模式來解決這個問題，這種架構下集群狀態多副本會被應用層次調度器獨立更新，如圖一C中所示。一旦本地有更新，調度器發布一個并發交易更新所有共享集群狀態。有時候因為另外一個調度器發出了一個沖突交易，交易更新有可能失敗。

最重要的共享狀態架構實例是Google的Omega系統，以及微軟的Apollo和Hashicorp的Nomad容器調度。這些例子中，共享集 群狀態架構都是通過一個模塊實現，也就是Omega中的“cell state”，Apollo中的“resource monitor”，以及Nomad中的“plan queue”。Apollo跟其他兩個不同之處在于共享狀態是只讀的，調度交易直接提交到集群設備；設備自身會檢查沖突，來決定接受或者拒絕更新，使得 Apollo即使在共享狀態暫時不可用情況下也可以繼續執行。

邏輯上來說，共享狀態設計不一定必需將全狀態分布在其它地方，這種方式（有點像Apollo）每個物理設備維護自己的狀態，將更新發送到其它感興趣 的代理，例如調度器，設備健康監控，和資源監控系統。每個物理設備本地狀態就成為一個全局共享狀態的“溝通片”（shard）。

然而，共享狀態架構也有一些缺點，必須作用在穩定的（過時的，stale）信息（這點跟中心化調度器不同），有可能在高競爭情況下造成調度器性能下降（盡管對其它架構也有這種可能）。

全分布式架構

看起來這種架構更加去中心化：調度器之間沒有任何協調，使用很多各自獨立調度器響應不同負載，如圖一d所示。每個調度器都作用于自己本地（部分或者 經常過時的【stale】）集群狀態信息。典型的，作業可以提交到任何調度器，調度器可以將作業發布到任何集群節點上執行。跟二級調度器不同的是，每個調 度器并沒有負責的分區，全局調度和資源分區是服從統計意義和隨機分布的，這有點像共享狀態架構，但是沒有中央控制。

盡管說去中心化底層概念（去中心化隨機選擇）是從1996年出現，現代意義上分布式調度應該是從Sparrow論文開始的，當時有一個討論是：合適 粒度（fine-grained）任務有很多優勢，Sparrow論文的關鍵假設是集群上任務周期可以變得很短；接下來，作者假定大量任務意味著調度器必 須支持很高通量的決策，而單一調度器并不能支持如此高的決策量（假定每秒上百萬任務量），Sparrow將這些負載分散到許多調度器上。

這個實現意義重大：去中心化理論上意味著更多的仲裁，但是這非常適合某類負載，我們會在后面的連載中討論。現在，足夠理由證明，由于分布式調度是無協調的，因此相對于復雜單體式調度，二級調度或者分布狀態時調度，更適合于簡單邏輯。例如：

1. 分布式調度是基于簡單的“時間槽（slot）”概念，將每臺設備分成n個標準時間槽，同時運行n個并發任務，盡管這種簡化忽略了任務資源需求是各自不同的事實。

2. 在任務端（worker side）使用服從簡單服務規則的隊列方式（例如Sparrow中FIFO），這樣調度器的靈活性受到限制，調度器只需決定在哪臺設備上將任務入隊。

3. 因為沒有中央控制，分布式調度器對于全局變量設置（例如，fairness policies或者strict priority precedence等）有一定難度。

4. 因為分布式調度是為基于最少知識做出快速決策而設計，因此無法支持或承擔復雜應用相關調度策略，因此避免任務之間干擾，對于全分布式調度來說很困難。

混合式架構

混合式架構是為了解決全分布式架構缺陷，最近（發端于學院派）提出的解決方式，它綜合了單體式或者共享狀態的設計。這種方式，例如 Tarcil，Mercury和Hawk，一般有兩條調度路徑：一條是為部分負載設計的分布式路徑（例如，短時間任務或者低優先級批量負載），另外一條集 中式調度，處理剩下負載，如圖一e所示。對于所描述的負載來說，混合架構中發生作用的調度器都是唯一的。實際上，據我所知，目前還沒有真正的混合架構部署 于生產系統中。

實際意義

不同調度架構相對價值，除了有很多研究論文外，其討論不僅僅局限在學院內，從行業角度對于Borg，Mesos和Omega論文的深入討論，可以參 見Andrew Wang的專業博客。然而，很多以上討論的系統都已經部署在大型企業生產系統中（例如，微軟的Apollo，Google的Borg，Apple的 Mesos），反過來這些系統激勵了其它可用開源項目。

如今，很多集群系統運行容器化負載，因此有一系列面向容器的“調度框架”（Orchestration Framworks）出現，他們跟Google以及其它被稱為“集群管理系統”類似。然而，很少關于這些調度框架和設計原則的討論，更多是集中于面向用戶 調度的API（例如，這篇Armand Grillet的報道，比較了Docker Swarm，Mesos/Marathon和Kubernetes的默認調度器）。然而，很多客戶既不懂不同調度架構的不同，也不知道哪個更適合自己的應 用。

圖二展示了一部分開源編排框架的架構和調度器支持的功能。圖表底部，也包括google和微軟閉源系統作比較。資源粒度一列展示調度器分配任務給固定大小時間槽，還是按照多維需求（例如CPU，memory，磁盤IO，網絡帶寬等）分配資源。

圖二：常用開源編排框架分類和功能比較，以及與閉源系統比較。

決定一個合適調度架構主要因素在于你的集群是否運行一個異構（或者說混合的）負載。例如，前端服務（例如，負載均衡web 服務和memcached）和批量數據分析（例如，MapReduce或者Spark）混合在一起，這種組合對于提高系統利用率是有意義的，但是不同應用 需要不同調度方式。在混合設定下，單體式調度很可能導致次優任務分配，因為基于應用需求，單體調度邏輯不能多樣化，而此時二級或者共享狀態調度可能更加適 合一些。

許多面向用戶服務負載運行的資源一般是滿足容器的峰值需求，但是實際上資源都是過分配的。這種情況下，能夠有機會降低給低優先級負載過分配資源對高 效集群來說是關鍵。盡管Kubernetes擁有相對成熟方案，Mesos是目前唯一支持這種過分配策略的開源系統。這個功能未來應該有更大改善空間，因 為根據Google borg集群來看很多集群利用率任然小于60-70%。后續博客我們將就資源預估，過分配和有效設備利用等方面展開討論。

***，特殊分析和OLAP應用（例如，Dremel或者SparkSQL）非常適合全分布式調度。然而，全分布式調度（例如Sparrow）內置相 對嚴格功能設置，因此當負載是同構（也就是，所有任務同時運行）、配置時間（set-up times）很短（也就是，任務調度后長時間運行,如同MapReduce應用任務運行于YARN）、任務通量（churn）很高（也就是，許多調度決定 必須很短時間內做出）時非常合適。我們將在下一個博客中詳細討論這些條件，以及為什么全分布式調度（以及混合架構中分布模塊）只對這種應用場景有效。

現在，我們可以證明分布式調度比其他調度架構更加簡單，而且不支持其他資源維度，過分配或者重新調度。

總之，圖二中表格表明，相對于更高級但是閉源的系統來說，開源框架仍然有很大提升空間。可以從如下幾方面采取行動：功能缺失，使用率不佳，任務性能不可預測，鄰居干擾（noisy neighbours）降低效率，調度器精細調整以支持某些客戶忒別需求。

然而，也有很多好消息：盡管今天還有很多集群仍然使用單體式調度，但是也已經有很多開始遷移到更加靈活架構。Kubernetes今天已經可以支持 可插入式調度器（kube-scheduler pod可以被其它API兼容調度pod替代），更多調度器從1.2版本開始會支持“擴展器”提供客戶化策略。Docker Swarm，據我理解，在未來也會支持可插入式調度器。

下一步

下一篇博客將會討論全分布式架構對于可擴展式集群調度是否關鍵技術創新（反對聲音說：不是必須的）。然后，我們會討論資源適配策略（提高利用率），***討論我們Firmament調度平臺如何組合和共享狀態架構和單體式調度質量，以及全分布調度器性能問題。