在前兩篇文章中，我和你分析了雲資源管理的集中式架構和非集中式架構。可以看出，分佈式系統架構的目的是，將多個服務器資源管理起來，尋找合適的服務器去執行用户任務。
那，什麼是合適的服務器呢？衡量一個服務器是否合適會涉及很多條件或約束，比如在一些場景下，任務存在優先級，那當我們需要執行多個任務的時候，通常需要滿足優先級高的任務優先執行的條件。但在這些條件中，服務器資源能夠滿足用户任務對資源的訴求是必須的。
而為用户任務尋找合適的服務器這個過程，在分佈式領域中叫作調度。在分佈式系統架構中，調度器就是一個非常重要的組件。它通常會提供多種調度策略，負責完成具體的調度工作。
當然，不同的分佈式架構的調度器原理也不一樣，最常見或最直觀的是單體調度，就是任務和分佈式系統中的空閒資源直接進行匹配調度。也就是説，調度器同時管理任務和資源，如果把資源比作“物質文明”，把任務比作“精神文明”，那麼單體調度就是“物質文明和精神文明一手抓”。
接下來，我帶你一起打卡分佈式調度架構之單體調度。
首先，讓我們先了解一下什麼是單體調度。
什麼是單體調度？
分佈式系統中的單體調度是指，一個集羣中只有一個節點運行調度進程，該節點對集羣中的其他節點具有訪問權限，可以蒐集其他節點的資源信息、節點狀態等進行統一管理，同時根據用户下發的任務對資源的需求，在調度器中進行任務與資源匹配，然後根據匹配結果將任務指派給其他節點。
單體調度器擁有全局資源視圖和全局任務，可以很容易地實現對任務的約束並實施全局性的調度策略。目前很多集羣管理系統採用了單體調度設計，比如我們第 9 篇文章中講到的 Google Borg、Kubernetes 等。
如下圖所示，圖中展示了一個典型的單體調度框架。Master 節點上運行了調度進程（負責資源管理、Tasks 和資源匹配）；Node 1，Node 2，…， Node N 對應着我們在第 9 篇文章中講的 Master/Slave 架構中的 Slave 節點。
Slave 節點會將 Node State 上報給 Master 節點的 Cluster State 模塊，Cluster State 模塊用於管理集羣中節點的資源等狀態，並將節點的資源狀態傳送給 Scheduling Logic 模塊，以便 Scheduling Logic 模塊進行 Tasks 與資源匹配，並根據匹配結果將 Task 發送給匹配到的節點。
在集羣管理中，單體調度模塊稱為“Scheduler”或“單體調度器”。單體調度器也叫作集中式調度器，指的是使用中心化的方式去管理資源和調度任務。
也就是説，調度器本身在系統中以單實例形式存在，所有的資源請求和任務調度都通過這個實例進行。集中式調度器的常見模型，如下圖所示。可以看到，在這一模型中，資源的使用狀態和任務的執行狀態都由調度器進行管理。
在 Borg 和 Kubernetes 這兩個集羣管理系統中，Scheduler 是它們的核心。而 Kubernetes 又是 Borg 的開源版本。所以接下來，我就以 Borg 為例，與你講述它的調度器是如何設計的，才能保證在上萬台機器規模的集羣上，運行來自幾千個不同應用的幾十萬個作業。
Borg 調度設計
調度的初衷是為作業或任務尋找合適的資源，也就是説作業或任務是調度的對象。那麼作業和任務到底是什麼呢？下面，我帶你先了解一下作業和任務的概念以及關係。
我們先來看看作業和任務的定義分別是什麼吧。
一個 Borg 作業的屬性包括名稱、擁有者和任務個數。作業可以有一些約束來強制其任務運行在有特定屬性的機器上，比如處理器架構、操作系統版本、是否有外網 IP 地址等。這些約束可以是硬性的也可以是柔性的，其中柔性約束表示偏好，而非需求。一個作業只在一個集羣中運行。
而一個任務對應的是一組 Linux 進程，運行在一台機器上的一個容器內或直接運行在節點上。任務也有一些屬性，比如資源需求量、在作業中的序號等。
那麼，作業和任務是什麼關係呢？
概括來説，一個作業可以包含多個任務。作業類似於用户在一次事務處理或計算過程中要求計算機所做工作的總和，而任務就是一項項具體的工作，二者屬於包含關係。
一個作業中的任務大多有相同的屬性，但也可以被覆蓋 ，比如特定任務的命令行參數、各維度的資源（比如，CPU 核、內存、硬盤空間、硬盤訪問速度、TCP 端口等）。
多個任務可以在多台機器上同時執行，從而加快作業的完成速度，提高系統的並行程度。而具體將哪個任務分配給哪個機器去完成，就是調度器要做的事兒了。
接下來，我就與你講述下 Borg 的 Scheduler 組件，來幫助你理解 Borg 內部的任務調度流程，以加深你對單體調度的理解。其實，很多框架比如 Hadoop、Spark 等都是採用了單體調度設計，它們整體的思想類似，所以我希望通過對 Borg 調度的講解，能夠幫助你理解你所在業務中的調度邏輯。
我們先來回憶下 Borg 的系統架構圖吧。
Scheduler 負責任務的調度，當用户提交一個作業給 BorgMaster 後，BorgMaster 會把該作業保存到 Paxos 倉庫中，並將這個作業的所有任務加入等待隊列中。調度器異步地掃描等待隊列，將任務分配到滿足作業約束且有足夠資源的計算節點上。
這裏我要再強調一下，調度是以任務為單位的，而不是以作業為單位。調度器在掃描隊列時，按照任務的優先級從高到低進行選擇，同優先級的任務則以輪詢的方式處理，以保證用户間的公平，並避免隊首的大型作業阻塞隊列。
接下來，我們再看看調度器的核心部分，也就是調度算法吧。
Borg 調度算法
Borg 調度算法的核心思想是“篩選可行，評分取優”，具體包括兩個階段：
可行性檢查，找到一組可以運行任務的機器（Borglet）；
評分，從可行的機器中選擇一個合適的機器（Borglet）。
首先，我們看一下可行性檢查。在可行性檢查階段，調度器會找到一組滿足任務約束，且有足夠可用資源的機器。比如，現在有一個任務 A 要求能部署的節點是節點 1、節點 3 和節點 5，並且任務資源需求為 0.5 個 CPU、2MB 內存。根據任務 A 的約束條件，可以先篩選出節點 1、節點 3 和節點 5，然後根據任務 A 的資源需求，再從這 3 個節點中尋找滿足任務資源需求的節點。
這裏需要注意的是，每個節點上的可用資源，包括已經分配給低優先級任務但可以搶佔的資源。
然後，我們看看評分階段。
在評分階段，調度器確定每台可行機器的適宜性。Borg 根據某一評分機制，對可行性檢查階段中篩選出的機器進行打分，選出最適合調度的一台機器。
在評分過程中，我們可以制定多種評價指標，比如考慮如何最小化被搶佔的任務數、儘量選擇已經下載了相同 package 的機器、目標任務是否跨域部署、在目標機器上是否進行高低優先級任務的混合部署等。 根據不同的考慮因素，可以定製不同的評分算法。
其中，常見的評分算法，包括“最差匹配”和“最佳匹配”兩種。
Borg 早期使用修改過的 E-PVM 算法來評分，該算法的核心是將任務儘量分散到不同的機器上。該算法的問題在於，它會導致每個機器都有少量的無法使用的剩餘資源，因此有時稱其為“最差匹配”（worst fit）。
比如，現在有兩個機器，機器 A 的空閒資源為 1 個 CPU 和 1G 內存、機器 B 的空閒資源為 0.8 個 CPU 和 1.2G 內存；同時有兩個任務，Task1 的資源需求為 0.4 個 CPU 和 0.3G 內存、Task2 的資源需求為 0.3CPU 和 0.5G 內存。按照最差匹配算法思想，Task1 和 Task2 會分別分配到機器 A 和機器 B 上，導致機器 A 和機器 B 都存在一些資源碎片，可能無法再運行其他 Task。
與之相反的是“最佳匹配”（best fit），即把機器上的任務塞得越滿越好。這樣就可以“空”出一些沒有用户作業的機器（它們仍運行存儲服務），來直接放置大型任務。
比如，在上面的例子中，按照最佳匹配算法的思想，Task1 和 Task2 會被一起部署到機器 A 或機器 B 上，這樣未被部署的機器就可以用於執行其他大型任務了。
但是，如果用户或 Borg 錯誤估計了資源需求，緊湊的裝箱操作會對性能造成巨大的影響。比如，用户估計它的任務 A 需要 0.5 個 CPU 和 1G 內存，運行該任務的服務器上由於部署了其他任務，現在還剩 0.2 個 CPU 和 1.5G 內存，但用户的任務 A 突發峯值時（比如電商搶購），需要 1 個 CPU 和 3G 內存，很明顯，初始資源估計錯誤，此時服務器資源不滿足峯值需求，導致任務 A 不能正常運行。
所以説，最佳匹配策略不利於有突發負載的應用，而且對申請少量 CPU 的批處理作業也不友好，因為這些作業申請少量 CPU 本來就是為了更快速地被調度執行，並可以使用碎片資源。還有一個問題，這種策略有點類似“把所有雞蛋放到一個籃子裏面”，當這台服務器故障後，運行在這台服務器上的作業都會故障，對業務造成較大的影響。
因此，這兩個評分算法各有利弊。在實踐過程中，我們往往會根據實際情況來選擇更適宜的評分算法。比如，對於資源比較緊缺，且業務流量比較規律，基本不會出現突發情況的場景，可以選擇最佳匹配算法；如果資源比較豐富，且業務流量會經常出現突發情況的場景，可以選擇最差匹配算法。
Borg 的設計是支持高優先級搶佔低優先級任務的，也就是説如果評分後選中的機器上沒有足夠的資源來運行新任務，Borg 會搶佔低優先級的任務，從最低優先級逐級向上搶佔，直到可用資源足夠運行該任務。被搶佔的任務放回到調度器的等待隊列裏，而不會被遷移或使其休眠。
當然有很多調度框架是支持用户根據自己的場景自定義調度策略的，比如優先級策略、親和性策略、反親和性策略等。
知識擴展：多個集羣 / 數據中心如何實現單體調度呢？
今天這篇文章中，我與你講述的單體調度，其實是針對一個集羣或一個數據中心的，那麼多個集羣或多個數據中心，能不能基於單體調度實現呢？
答案是肯定的，這就是集羣聯邦的概念了。
所謂集羣聯邦，就是將多個集羣聯合起來工作，核心思想是增加一個控制中心，由它提供統一對外接口，多個集羣的 Master 向這個控制中心進行註冊，控制中心會管理所有註冊集羣的狀態和資源信息，控制中心接收到任務後會根據任務和集羣信息進行調度匹配，選擇到合適的集羣后，將任務發送給相應的集羣去執行。
集羣聯邦的概念，其實就是單體調度的分層實現。如果你對集羣聯邦感興趣的話，推薦你看一下 Kubernetes 的集羣聯邦設計和工作原理。
總結
今天，我以 Borg 為例，與你講述了單體調度架構的設計及調度算法。
單體調度是指一個集羣中只有一個節點運行調度進程，該調度進程負責集羣資源管理和任務調度，也就是説單體調度器擁有全局資源視圖和全局任務。
單體調度的特徵，可以總結為以下四點：
單體調度器可以很容易實現對作業的約束並實施全局性的調度策略，因此適合批處理任務和吞吐量較大、運行時間較長的任務。
單體調度系統的狀態同步比較容易且穩定，這是因為資源使用和任務執行的狀態被統一管理，降低了狀態同步和併發控制的難度。
調度算法只能全部內置在核心調度器當中，因此調度框架的靈活性和策略的可擴展性不高。
單體調度存在單點故障的可能性。
現在，我再用一個思維導圖為你總結一下今天的主要內容，以方便你理解記憶。
單體調度器雖然具有單點瓶頸或單點故障問題，但因為其具有全局資源視圖和全局任務，簡單易維護，被很多公司廣泛採用，比如 Google、阿里、騰訊等公司。另外，我們今天介紹的 Borg 集羣管理系統，以及其開源版 Kubernetes 集羣管理系統，使用的都是單體調度結構。
單體調度結構雖然結構單一，但是其調度算法可以擴展甚至自定義，也就是説你可以根據業務特徵，自定義調度策略，比如優先級策略、親和性策略等。
學完了關於單體調度的知識後，趕緊上手試試，定製一個獨特的調度算法或設計一個特定的單體調度器吧。如果你在這個過程中遇到了什麼問題，就留言給我吧。
思考題
你能和我分享下，Google Borg 是採用什麼技術實現的資源隔離嗎？