文章目錄
- 叢集排程架構的演進過程
- 中心化排程架構
- 兩級排程架構
- 共享狀态排程架構
- 全分布式架構
- 混合式排程架構
- 實際含義
- 下一步
叢集排程器是現在資料中心中非常重要的一個元件，并且這現年已經有了很大的發展。它的架構也從中心化設計轉向更加靈活、去中心化和分布式設計。然而許多現在開源的排程架構依舊是中心化設計或者缺少很多主要的特性，這些特性對于實際的使用者來說非常重要，因為這些好的特性可以使資料中心獲得很高的資源使用率。
這篇文章是我們探讨大規模叢集作業排程的第一篇文章，作業排程在Amazon、Google、Facebook、Microsoft或Yahoo！等網際網路公司已經有了很好的實作，并且相關的需求也在不斷增長。排程是一個非常重要的問題，因為它直接影響到運作叢集的開銷，一個糟糕的排程架構會導緻叢集的資源使用率很低，那些昂貴的機器資源則會白白浪費。然而光靠排程架構也無法實作很高的資源使用率，如果叢集沒有仔細配置，不同作業之間互相幹擾也會影響到資源的使用率。
叢集排程架構的演進過程
這篇文章讨論了這些年排程架構是如何發展的以及為什麼會這樣發展。圖一展示了叢集排程的不同方法：其中灰色的方塊對應一個機器，不同顔色的圓圈代表不同的任務，有“S”标志的圓角矩形代表排程器（這個圖簡化了一些，實際上，每台機器運作多個任務，許多排程器适合多個資源緯度的任務，而不是簡單的slots），箭頭代表排程器決定的作業放置位置，三種顔色代表不同的工作負載（如網站服務、批量分析和機器學習）。
中心化排程架構
許多叢集排程架構，例如大量高性能計算（high-performance computing，HPC）排程器、 Borg 排程器、各種早期的Hadoop排程器和Kubernetes排程器都是中心化設計的排程架構。單一的排程程序在一台機器上運作（例如Hadoop V1的JobTracker、Kubernetes的kube-scheduler），排程器負責将任務指派給叢集内的機器。在中心化排程架構下，所有的工作負載都是由一個排程器來處理，所有的作業都通過相同的排程邏輯來處理（如圖1a）。這種架構很簡單并且統一，在這個基礎上發展出了許多複雜的排程器。比如Paragon排程器和Quasar排程器，它們使用機器學習的方法來避免負載之間因互相競争資源而産生的幹擾。
現在大部分的叢集都運作着不同類型的應用（相反，如Hadoop MapReduce的早期作業）。然而，維護一個處理混合負載的單一排程器是一個很棘手的問題，原因如下：
- 希望排程器能差別處理長期運作的作業和批處理作業，這是一個合理的請求。
- 因為不同的應用有不同的需求，若要全部滿足其需求則需要不斷在排程器中增加特性，這樣增加了它的邏輯複雜度和部署難度。
- 排程器處理作業的順序變成了一個問題：隊列效應（例如頭阻塞：head-of-line blocking）和作業積壓是一個問題，除非在設計排程器時非常小心。
總之，這些聽起來是工程師的噩夢，排程器維護者會不斷收到往排程器中添加特性要求的清單。
兩級排程架構
兩級排程架構通過将資源排程和作業排程分開的方式來解決這個問題。兩級排程允許根據特定的應用來定做不同的作業排程邏輯，并同時保留了不同作業之間共享叢集資源的特性。Mesos叢集管理系統首先使用了兩級排程的方法，Yarn則支援其有限的版本。在Mesos中，資源是主動被提供給應用層的排程器來使用的（排程器可以從下層提供的資源中進行選擇），而Yarn則是由應用層來請求資源（并且接受被配置設定的資源）。如圖1b所示，适用于特定負載的排程器（S0-S2）與資料總管進行互動，資料總管則為每個負載動态劃分叢集的資源。這是一個非常靈活的方式，它允許針對特定的負載來自定義排程政策。
但是，兩級排程架構也有一些問題。應用層排程器無法看到所有的資源，也就是說，它們沒有全局視角，無法看到作業可以被放到哪些機器上執行。相反，它們隻能看到資料總管主動提供的資源（Mesos）或者資料總管配置設定給應用（Yarn）的部分資源。這樣的設計有幾點缺點：
- 高優先級搶占（高優先級作業會踢走低優先級作業）會變得很難實作。在基于offer的模式下，被運作中的作業所占用的資源對上層排程器是不可見的；在基于request的模式下，底層的資料總管必須能了解搶占的政策（這可能與應用程式有關）。
- 排程器無法考慮到因其他運作的工作負載造成的幹擾可能影響到資源的品質（比如“吵鬧的鄰居”占據了I/O帶寬），因為排程器無法看到它們。
- 應用特定的排程器對底層資源的很多不同方面很關心，但是它們獲得資源的唯一方法就是通過資料總管提供的offer/request接口，這個接口很容易變得非常複雜。
共享狀态排程架構
共享狀态排程通過半分布式的模式來解決這個問題，在這種模式下應用層的每個排程器都擁有一份叢集狀态的副本，并且排程器會獨立地對叢集狀态副本進行更新，如圖1c所示。一旦本地的狀态副本産生了變化，排程器會釋出一個事務去更新整個叢集的狀态，有時候因另外一個排程器同時釋出了一個沖突的事務時，事務更新有可能失敗。
在共享狀态排程的架構中，最著名的是Google的Omega、Microsoft的Apollo，以及Hashicorp的Nomad容器排程器。所有的這些都是使用一種方法實作共享狀态排程，就是Omega中的“cell state”、Apollo的“resource monitor”以及Nomad中的“plan queue”。Apollo跟其他兩個排程架構不同之處在于其共享狀态是隻讀的，排程事務是直接送出到叢集中的機器上，機器自己會檢查沖突，來決定是接受還是拒絕這個變化，這使得Apollo即使在共享狀态暫時不可用的情況下也可以執行。
邏輯上的共享狀态排程架構也可以不通過将整個叢集的狀态分布在其他地方來實作，這種方式（有點像Apollo做的）中，每台機器維護其自己的狀态并發送更新的請求到其他對該節點感興趣的代理，比如排程器、裝置健康監控器和資源監控系統等。每個實體裝置的本地狀态都成為了整個叢集的共享狀态的分片之一。
然而，共享狀态排程架構也有一些缺點，它必須工作在有穩定資訊的情況下（這點跟中心化排程器不同），在叢集資源的競争度很高的情況下有可能造成排程器的性能下降（盡管其他架構也有可能出現這種情況）。
全分布式架構
全分布式架構更加去中心化：排程器之間根本沒有任何的協調，并且使用很多各自獨立的排程器來處理不同的負載，如圖1d所示。每個排程器都作用在自己本地（部分或者經常過時的）叢集狀态資訊。在分布式排程架構下，作業可以送出給任意的排程器，并且每個排程器可以将作業發送到叢集中任何的節點上執行。與兩級排程排程架構不同的是，每個排程器并沒有負責的分區，相反的是，全局排程和資源劃分都是服從統計和随機分布的，與共享狀态排程架構有些相似，但是沒有中央控制。
盡管全分布式排程架構的概念（多個随機選擇）是從1996年出現的，現代意義上的分布式排程應該是從Sparrow論文開始的。Sparrow論文的關鍵是它假設叢集上任務周期都會變的越來越短，這點是以當時一個讨論作為支撐：細粒度的任務有很多的優勢。是以，作者假設作業會變得越來越多，這意味着排程器必須支援更高決策的吞吐量，而單一的排程器并不能支援如此高的吞吐量（假設每秒有上百萬個任務），是以Sparrow将這些負載分散到很多排程器上。
這個實作的意義重大：缺少中央控制在理論上很吸引人，并且非常合适某些負載，我們會在後面的連載中進行讨論。目前，我們注意到因為分布式排程器是不協調的，它相對于中心化排程、兩級排程或共享狀态排程擁有更簡單的邏輯，例如：
- 分布式排程器是基于簡單的“slot”概念，将每台機器分成n個标準的“slot”，并放置n個并行作業，這簡化了任務的資源需求不統一的事實。
- 它使用了擁有簡單服務規則的worker-side隊列（例如，Sparrow中的FIFO規則），這樣限制了排程器的靈活性，因為排程器隻能選擇将作業放置在哪台裝置的隊列上。
- 分布式排程器很難執行全局不變量（例如，公平政策和嚴格的優先級優先），因為它沒有中央控制。
- 因為分布式排程器是基于最少知識做出快速決策而設計，它無法支援或承擔複雜或特定應用的排程政策，例如，避免任務之間的互相幹擾對分布式排程來說很困難。
混合式排程架構
混合式排程架構是最近（學術界提出的）提出的解決方法，它的出現是為了解決全分布式架構的缺點，它結合了中心化排程和共享狀态的設計。這種方式例如Tarcil、Mercury和Hawk一般有兩條排程路徑，一條是為部分負載設計的分布式排程（例如非常短的作業或者低優先級的批作業），另外一條是中心式作業排程來處理剩下的負載，如圖1e所示。混合排程器的每個組成部分的行為與上述描述的部分架構相同。實際上，據我所知，目前還沒有真正的混合排程器應用于生産環節當中。
實際含義
對不同排程器架構的相對優缺點的讨論并不隻是學術探讨，盡管它自然圍繞着研究論文。從工業界角度對于Borg、Mesos和Omega論文的深入讨論可以參見Andrew Wang的博文。此外，很多以上讨論的系統都已經部署到了大型企業的生産系統中了（比如Microsoft的Apollo、Google的Borg、Apple的Mesos），反過來，這些系統激勵了其他可用于開源的項目。
如今，很多叢集運作容器化的負載，是以有一系列基于容器的架構（Orchestration Frameworks）出現了，它們與Google和其他稱為“叢集管理系統”的很相似。然而，很少有關于這些排程器的架構和設計原則的詳細讨論，它們更多的是集中于面向使用者排程的API（例如這篇Armand Grillet的報道，文中比較了Docker Swarm、Mesos/Marathon和Kubernetes的預設排程器），然而很多客戶既不懂不同排程器的差別，也不知道哪個更适合自己的應用。
圖2展示了一部分開源架構的概況，包括它們的結構和排程器所支援的功能。在圖表的最低端，也包括Google和Microsoft沒有開源的系統作為參考。資源粒度（Resource Granularity）這一列展示了排程器是配置設定作業給固定大小的slots，還是按照作業多元度的資源需求來配置設定的（例如CPU、記憶體、磁盤IO帶寬、網絡帶寬等）。
決定使用哪個排程架構主要的一點就是看叢集中是否運作一個異構（例如混合的）負載。例如一個前端服務（例如負載均衡或memcached）和批量資料分析作業（例如MapReduce或spark）相結合的生産環境，這種組合有利于提高系統的資源使用率，但是不同的應用對排程的需求有所不同。在作業混部的情況下，中心化排程可能導緻任務的次優配置設定，因為不能基于單個應用進行邏輯的多樣化處理，是以在這種情況下，兩級排程和共享狀态排程可能更加合适。
大多數面向使用者服務的負載運作在資源能滿足峰值需求的容器中，但是實際上這些資源都是過度配置設定的，在這種情況下，能有機會降低給低優先級負載過多配置設定資源（能繼續保證負載的QoS）對提高叢集的效率是非常關鍵的。盡管kubernetes擁有相對比較成熟的方案，Mesos是目前唯一支援這種過多配置設定資源的開源系統。我們期待未來在這個方面有更多的工作，因為根據Google的Borg叢集來看很多叢集的使用率依然低于60-70%。在後續的文章中，我們将關注資源預估、過度配置設定和有效提高機器的資源使用率。
最後，特定的分析和OLAP應用（例如Dremel或者SparkSQL queries）會從全分布式排程器受益，然而，全分布式排程器（如Sparrow）有嚴格的功能設定，是以當叢集的負載是同構（比如所有作業的運作時間是大概相同的）、配置時間短（也就是任務能被排程到長時間運作的worker上，例如MapReduce作業在YARN中運作）、任務通量高（大部分排程的決定必須能在短時間内做出）時非常合适。我們将在接下來的文章中讨論這些條件，并且讨論為什麼全分布式排程器和混合式排程器中的分布式元件隻對這些應用有效。現在，我們可以證明分布式排程比其他排程架構更加簡單，但是不支援多元度的資源、過度配置設定和重新排程。
總之，圖2中的表格表明對于開源的排程架構依舊有一段路要走，直到它們能比對一些進階的配置。可以從以下幾個方面來采取行動：功能缺失、資源使用率低、作業的性能不可測和“吵鬧的鄰居”降低效率，并且需要将elaborate hacks加入到排程器中來支援使用者的需要。