1 引言

什么是調(diào)度?通常所說的調(diào)度(schedule)是和時間有關(guān)的，比如我今天的schedule很緊(如圖1所示)。時間作為唯一的不可逆轉(zhuǎn)的資源，一般是劃分為多個時間片來使用。就計算機而言，由于CPU的速度快的多，所以就有了針對CPU時間片的調(diào)度，讓多個任務(wù)在同一個CPU上運行起來。然而這是一個假象，某一時刻CPU還是單任務(wù)運行的。

圖1 時間片的劃分

為了在同一時間運行更多的任務(wù)，或者多個處理器一起工作完成一個任務(wù)目標(biāo)，就需要一個協(xié)調(diào)者——這就成為一個分布式系統(tǒng)，就單個數(shù)據(jù)中心或者小范圍來說，這就是集群。如果讓一個分布式系統(tǒng)運行多個任務(wù)，每個任務(wù)對分布式系統(tǒng)中的資源必然產(chǎn)生競爭，時間調(diào)度就發(fā)展到資源調(diào)度。

宏觀上來說調(diào)度主題包括了單機操作系統(tǒng)、C/S系統(tǒng)、B/S系統(tǒng)、P2P系統(tǒng)、集群系統(tǒng)、分布式系統(tǒng)等等，以及網(wǎng)絡(luò)協(xié)議棧、存儲協(xié)議棧的各種調(diào)度機制。本文主要總結(jié)了集群調(diào)度發(fā)展的三個階段：宏調(diào)度、兩層調(diào)度和共享狀態(tài)調(diào)度，并比較了三者之間的優(yōu)缺點。

2 集群調(diào)度

2.1 宏調(diào)度(Monolithic schedulers)

宏調(diào)度：在同一個代碼模塊中實現(xiàn)調(diào)度策略，單個實例，沒有并行。常見于HPC(high-performance computing)世界中。

圖2 Hadoop1和MapReduce 的宏調(diào)度架構(gòu)

如圖2所示，以為MapReduce為例，一個稱之為JobTracker的Master進程是所有MapReduce任務(wù)的中心調(diào)度器。每一個節(jié)點上面都運行一個TaskTracker進程來管理各個節(jié)點上的任務(wù)。各個TaskTracker要和Master節(jié)點上的JobTracker通信并接受JobTracker的控制。和大多數(shù)資源管理器類似，MapReduce的JobTracker支持兩種調(diào)度策略，Capacity調(diào)度策略和Fair調(diào)度策略。

在JobTracker中，資源的調(diào)度和作業(yè)的管理功能全部放到一個進程中完成。這種設(shè)計方式的缺點是擴展性差：首先，集群規(guī)模受限;其次，新的調(diào)度策略難以融入現(xiàn)有代碼中，比如之前僅支持批處理作業(yè)，現(xiàn)在要支持流式作業(yè)，而將流式作業(yè)的調(diào)度策略嵌入到中央式調(diào)度器中是一項很難的工作。

2.2 靜態(tài)分區(qū)(Statically partitioned schedulers)

基于靜態(tài)分區(qū)的資源劃分和調(diào)度也被稱為云計算中的調(diào)度，通過在云平臺中分配和定義虛擬機角色，實現(xiàn)資源集合的全面控制。業(yè)務(wù)系統(tǒng)往往部署在專門的、靜態(tài)劃分的集群的一個子集上——把集群劃分為不同的部分，分別支持不同的業(yè)務(wù)?，F(xiàn)在大多數(shù)企業(yè)級的云計算都是采用這樣計劃經(jīng)濟式的資源分配方式——在系統(tǒng)部署之前做好容量規(guī)劃和資源分配

2.3 兩層調(diào)度(Two-level scheduling)

為了處理宏調(diào)度和集群靜態(tài)分區(qū)的種種限制，一個直接的解決方案就是兩層調(diào)度。通過引入一個中央的協(xié)調(diào)組件來決定每一個子集群需要分配的資源數(shù)量，從而動態(tài)的調(diào)整分配給每一個調(diào)度器(框架調(diào)度器)的資源。兩層調(diào)度本質(zhì)上是在調(diào)度中分離資源分配和任務(wù)分配，讓渡一部分決策權(quán)力給應(yīng)用框架，解決不同應(yīng)用框架的需求異構(gòu)問題。如圖3所示，YARN為上層不同的應(yīng)用框架提供了統(tǒng)一的資源調(diào)度層。后文對Mesos的介紹一節(jié)會詳細介紹兩層調(diào)度的需求背景。

圖3 Hadoop1和MapReduce 的宏調(diào)度架構(gòu)

各個框架調(diào)度器并不知道整個集群資源使用情況，只是被動的接收資源。中央?yún)f(xié)調(diào)組件僅將可用的資源推送給各個框架，而框架自己選擇使用還是拒絕這些資源。一旦框架(比如JobTracker)接收到新資源后，再進一步將資源分配給其內(nèi)部的各個應(yīng)用程序(各個MapReduce作業(yè))，進而實現(xiàn)雙層調(diào)度。

雙層調(diào)度器有兩個缺點，其一，各個框架無法知道整個集群的實時資源使用情況;其二，采用悲觀鎖，并發(fā)粒度小。

2.3.1 YARN

YARN被稱之為Apache Hadoop Next Generation Compute Platform，是hadoop1和hadoop2之間***的區(qū)別如圖4所示。

圖4 在Hadoop 2.0中引入YARN

Hadoop2(MRv2)的基礎(chǔ)思想就是把JobTracker的功能劃分成兩個獨立的進程：全局的資源管理ResourceManager和每個進程的監(jiān)控和調(diào)度ApplicationMaster。這個進程可以是Map-Reduce 中一個任務(wù)或者是DAG中一個任務(wù)。

圖5 在Hadoop 2.0中引入YARN

在YARN的設(shè)計中，集群中可以有多個ApplicationMasters，每一個ApplicationMasters可以有多個Containers (例如，圖5中有兩個ApplicationMasters，紅色和藍色。紅色的有三個Containers，藍色的有一個Container)。關(guān)鍵的一點是ApplicationMasters 不是ResourceManager的部分，這就減輕了中心調(diào)度器的壓力，并且，每一個ApplicationMasters都可以動態(tài)的調(diào)整自己控制的container。

而 ResourceManager 是一個純粹的調(diào)度器(不監(jiān)控和追蹤進程的執(zhí)行狀態(tài)，也不負責(zé)重啟故障的進程)，它唯一的目的就是在多個應(yīng)用之間管理可用的資源(以Containers的粒度)。ResourceManager是資源分配的***權(quán)威。如果說ResourceManager是Master，NodeManager就是其slave。ResourceManager并且支持調(diào)度策略的插件化，CapacityScheduler 和 FairScheduler就是這樣的插件。

ApplicationMaster 負責(zé)任務(wù)提交，通過協(xié)商和談判從ResourceManager那里以Containers的形式獲得資源(負責(zé)談判獲得適合其應(yīng)用需要的Containers)。然后就track進程的運行狀態(tài)。ApplicationMasters是特定于具體的應(yīng)用，可以根據(jù)不同的應(yīng)用來編寫不同的ApplicationMasters。例如，“YARN includes a distributed Shell framework that runs a shell script on multiple nodes on the cluster. ” 另外，ApplicationMaster 提供自動重啟的服務(wù)。ApplicationMaster可以理解為應(yīng)用程序可以自己實現(xiàn)的接口庫。

ApplicationMasters請求和管理Containers。Containers指定了一個應(yīng)用在某一臺主機上可以使用多少資源 (包括memory, CPU等) ，這類似于HPC調(diào)度中的資源池。ApplicationMaster一旦從 ResourceManager那里獲得資源，它就會聯(lián)系NodeManager 來啟動某個特定的任務(wù)。例如如果使用 MapReduce 框架，這些任務(wù)可能就是Mapper 和 Reducer 進程。不同的框架會有不同的進程。

NodeManager是每一個機器上框架代理，負責(zé)該機上的Containers，并且監(jiān)控可用的資源(CPU, memory, disk, network)。并且資源狀態(tài)報告給ResourceManager。

表面上看來，YARN也是一個兩層調(diào)度。在YARN中，資源請求從Application Masters發(fā)出到一個中心的全局調(diào)度器上，中心調(diào)度器根據(jù)應(yīng)用的需要在集群中的多個節(jié)點上分配資源。但是YARN中的Application Masters提供的僅僅是一個任務(wù)管理服務(wù)，并不是一個真正的二層調(diào)度器。因此本質(zhì)上YARN仍舊是一個宏調(diào)度架構(gòu)。截止目前，YARN只支持資源類型(內(nèi)存)的調(diào)度。

Hadoop2(MRv2)的API是后向兼容的，支持Map-Reduce的任務(wù)只需要重新編譯一下就可以運行在Hadoop2(MRv2)上。

2.3.2 Mesos

大量分布式計算框架(Hadoop, Giraph, MPI, etc)的出現(xiàn)，每一個計算框架需要管理自己的計算集群。這些計算框架往往把任務(wù)分割成很多小任務(wù)，讓計算靠近數(shù)據(jù)，從而可以提高集群的利用率。但是這些框架都是獨立開發(fā)的，不可能在應(yīng)用框架之間共享資源。形象的表示如圖6所示。

圖6 集群的靜態(tài)分區(qū)和動態(tài)共享

我們希望在同一個集群上可以運行多個應(yīng)用框架。 Mesos是通過提供一個通用資源共享層，多個不同的應(yīng)用框架可以運行在這個資源共享層之上。形象的表示如圖7所示。

圖7 Mesos為不同應(yīng)用框架提供統(tǒng)一調(diào)度接口

但我們不希望使用簡單的靜態(tài)分區(qū)的方法，如圖8所示。

圖8 集群內(nèi)靜態(tài)分區(qū)

Mesos的英文定義為：“ Mesos, which is an open source platform for fine-grained resource sharingbetween multiple diverse cluster computing frameworks.”

Mesos***的好處就是提高集群的利用率?？梢院芎玫母綦x產(chǎn)品環(huán)境和實驗環(huán)境，可以同時并發(fā)運行多個框架。其次，可以在多個集群之間共享數(shù)據(jù)。第三，可以降低維護成本。 Mesos***挑戰(zhàn)是如何支持大量的應(yīng)用框架。因為每一個框架都有不同的調(diào)度需求：編程模型、通信范型、任務(wù)依賴和數(shù)據(jù)放置。另外 Mesos的調(diào)度系統(tǒng)需要能夠擴展到數(shù)千個節(jié)點，運行數(shù)百萬個任務(wù)。由于集群中的所有任務(wù)都依賴于 Mesos，調(diào)度系統(tǒng)必須是容錯和高可用的。

Mesos的設(shè)計決策(設(shè)計哲學(xué))：不采用中心化的，設(shè)計周全的(應(yīng)用需求，可用資源，組織策略)，適用于所有任務(wù)的全局調(diào)度策略。而采用委派調(diào)度任務(wù)給應(yīng)用框架(把調(diào)度和執(zhí)行的功能交給應(yīng)用框架)。 Mesos聲稱：這樣的設(shè)計策略可能不會達到全局***的調(diào)度，但在實際運行中出奇的好，可以使得應(yīng)用框架近乎***的達到目標(biāo)。其聲稱中的優(yōu)點主要有兩個：應(yīng)用框架的演化獨立和保持 Mesos的簡潔。

Mesos的主要組件包括Master daemon，Slave daemons和在slaves之上運行的 Mesos applications (也被稱為 frameworks)(如圖9所示)。Master根據(jù)相應(yīng)的策略(公平調(diào)度，優(yōu)先級調(diào)度等)決定給每一個應(yīng)用分配多少資源。模塊化架構(gòu)支持多種策略。Resource offer是資源的抽象表示，基于該資源，應(yīng)用框架可以在集群中的某個node上實例化分配offer，并運行任務(wù)。每一個Resource offer 就是一個分布在多個node上的空閑資源列表。Mesos基于一定的算法策略(如公平調(diào)度)決定有多少資源可以分配給應(yīng)用框架，而應(yīng)用框架決定使用(接受)哪些資源，運行哪些任務(wù)。Mesos上運行的應(yīng)用框架由兩部分組成：應(yīng)用調(diào)度器和slave上運行代理。應(yīng)用調(diào)度器向 Mesos注冊。Master決定向注冊的框架提供多少資源，應(yīng)用調(diào)度器決定Master分配的資源中哪些來使用。調(diào)度完成之后，應(yīng)用調(diào)度器把接受的資源發(fā)送給 Mesos，從而決定了使用哪些slave。然后應(yīng)用框架中的任務(wù)的執(zhí)行可以在slave上運行。當(dāng)任務(wù)很小并且是短期任務(wù)(每個任務(wù)都頻繁的讓渡自己握著的資源的時)，Mesos工作的很好。

圖9 Mesos調(diào)度框架

在 Mesos中，一個中央資源分配器動態(tài)的劃分集群，分配資源給不同的調(diào)度框架(scheduler frameworks)。資源可以在不同的調(diào)度框架之間以“offers”的形式任意分配，offers表示了當(dāng)前可用的資源。資源分配器為了避免不同調(diào)度框架對同一資源沖突申請，只允許一次只能分配給一個調(diào)度框架。在調(diào)度決策的過程中，資源分配器實質(zhì)上起到了鎖的作用。因此 Mesos中的并發(fā)調(diào)度是悲觀策略的。

Master使用resource offer機制在多個框架之間細粒度的共享資源。每一個resource offer空閑資源列表，分布在多個slave上。Master決定給每一個應(yīng)用框架提供多少資源，依據(jù)是公平方法或者優(yōu)先級方法。第三發(fā)可以以可插拔模塊的方式定制策略。

Reject機制：駁回 Mesos提供的資源方案。為了保持接口的簡單性， Mesos不允許應(yīng)用框架指定資源需求的限制信息，而是允許應(yīng)用框架拒絕 Mesos提供的資源方案。應(yīng)用框架如果遇到?jīng)]有滿足其需求的資源提供方案，則會拒絕等待。 Mesos聲稱拒絕機制可以支持任意復(fù)雜的資源限制，同時保持擴展性和簡單。

Reject機制帶來的一個問題是在應(yīng)用框架收到一個滿足其需求的方案之前可能需要等待很長時間。由于不知道應(yīng)用框架的需求， Mesos可能會把同一個資源方案發(fā)給多個應(yīng)用框架。因此，引入fliter機制： Mesos中的一個調(diào)度框架使用filter來描述它期望被服務(wù)的資源類型(允許應(yīng)用框架設(shè)置一個filter表示該應(yīng)用框架會永遠的拒絕某類資源)。因此，它不需要訪問整個集群，它只需要訪問它被offer的節(jié)點即可。這種策略帶來的缺點是不能支持基于整個集群狀態(tài)的搶占和策略：一個調(diào)度框架不知道分配給其他調(diào)度框架的資源。 Mesos提供了一種資源儲存的策略來支持Gang調(diào)度。例如，應(yīng)用框架可以指定一個其可以運行node白名單列表。這不是動態(tài)的集群分區(qū)嗎? Mesos進一步解釋filter機制：filter只是一個資源分配模型的性能優(yōu)化方案，應(yīng)用框架有哪些任務(wù)運行在哪些node上最終決定權(quán)。

圖10 Mesos調(diào)度流程

Mesos任務(wù)調(diào)度過程如圖10所示，具體流程如下：

1. Slave 1 向Master匯報它有4個CPUs 和 4 GB的空閑內(nèi)存，Master 的allocation模塊會根據(jù)相應(yīng)的分配策略通知framework 1 可以使用所有可用資源。
2. Master把slave 1上的可用資源發(fā)送給framework 1(以resource offer的方式)。
3. framework的調(diào)度器響應(yīng)Master調(diào)度器：準(zhǔn)備在slave上運行兩個任務(wù)，使用的資源分別是：***個任務(wù)<2 CPUs, 1 GB RAM> ，第二個任務(wù) <1 CPUs, 2 GB RAM> 。
4. ***，Master把任務(wù)發(fā)送給slave，然后把相應(yīng)的資源分配給framework的執(zhí)行器。然后執(zhí)行器啟動兩個任務(wù)。由于slave1上還有1 CPU 和1 GB的內(nèi)存沒有分配，分配模塊可以把資源分配給framework 2。

另外，Mesos Master的Allocation module是pluggable。使用ZooKeeper 來實現(xiàn) Mesos Master的Failover。

2.4 狀態(tài)共享調(diào)度(Shared-state scheduling)

在狀態(tài)共享調(diào)度中，每一個調(diào)度器都可以訪問整個集群狀態(tài)。當(dāng)多個調(diào)度器同時更新集群狀態(tài)時使用樂觀并發(fā)控制。Shared-state調(diào)度可以解決兩層調(diào)度的兩個問題：悲觀并發(fā)控制所帶來的并行限制和調(diào)度框架對整個集群資源的可見性。樂觀并發(fā)控制所帶來的問題是當(dāng)樂觀假設(shè)不成立時，需要重新調(diào)度。

為了克服雙層調(diào)度器的以上兩個缺點(Omega paper主要關(guān)注了這個問題)，Google開發(fā)了下一代資源管理系統(tǒng)Omega，Omega是一種基于共享狀態(tài)的調(diào)度器，該調(diào)度器將雙層調(diào)度器中的集中式資源調(diào)度模塊簡化成了一些持久化的共享數(shù)據(jù)(狀態(tài))和針對這些數(shù)據(jù)的驗證代碼，而這里的“共享數(shù)據(jù)”實際上就是整個集群的實時資源使用信息。一旦引入共享數(shù)據(jù)后，共享數(shù)據(jù)的并發(fā)訪問方式就成為該系統(tǒng)設(shè)計的核心，而Omega則采用了傳統(tǒng)數(shù)據(jù)庫中基于多版本的并發(fā)訪問控制方式(也稱為“樂觀鎖”, MVCC, Multi-Version Concurrency Control)，這大大提升了Omega的并發(fā)性。在Omega中沒有中心的資源分配器，調(diào)度器自己做出資源分配的決策。

2.4.1 Omega

宏調(diào)度的缺點是難以增加調(diào)度策略和專門的實現(xiàn)，并且不能隨著集群的擴展而擴展。兩層調(diào)度確實可以提供靈活性和并行性，但是在實踐中他們的資源可見性卻是保守的，難以適應(yīng)一些挑剔型的任務(wù)和一些需要訪問整個集群資源的任務(wù)。Omega的解決方案是提出了一個新的并行調(diào)度框架：基于共享狀態(tài)的、無鎖的、樂觀并發(fā)控制，可擴展的。

如圖11所示，Omega中沒有中心的資源分配器，所有的資源分配決策都是由應(yīng)用的調(diào)度器自己完成的。Omega維護了一個成為cell state的資源分配狀態(tài)信息主拷貝。每一個應(yīng)用的調(diào)度器都維護了一個本地私有的，頻繁更新的cell state拷貝，用來做調(diào)度決策。調(diào)度器可以看到全局的所有資源，并根據(jù)權(quán)限和優(yōu)先級來自以為是的要求需要的資源。當(dāng)調(diào)度器決定資源方案時，以原子的方式更新共享的cell state：大多數(shù)時候這樣commit將會成功(這就是樂觀方法)。當(dāng)沖突發(fā)生時，調(diào)度決策將會以事務(wù)的方式失敗。無論調(diào)度成功還是失敗，調(diào)度器都會重新同步本地的cell state和共享的cell state。然后，如果需要，重啟調(diào)度過程。

Omega的調(diào)度器完全是并行的，不需要等待其他調(diào)度器。為了避免沖突造成的饑餓，Omega調(diào)度器使用增量調(diào)度——Accept all but the conflict things，這樣可以避免資源囤積。如果使用all or nothing 的策略可以使用Gang調(diào)度(Either all tasks of a job are scheduled together, or none are, and the scheduler must try to schedule the entire job again.)。Gang調(diào)度要等待所有資源就緒，才commit整個任務(wù)，就造成了資源囤積。

每一個應(yīng)用調(diào)度器都可以實現(xiàn)自己的調(diào)度策略。但是它們必須就資源分配和任務(wù)的優(yōu)先級達成一致。兩層調(diào)度的中心資源管理器可以輕松實現(xiàn)這一點。這是一個開放的話題，可以進一步討論：Google認為公平性不是一個關(guān)鍵需求，各個調(diào)度器只是滿足自己的業(yè)務(wù)需求。因此，限制每一個應(yīng)用調(diào)度器的資源上限和任務(wù)提交上限。

圖11 Omega調(diào)度框架

2.4 對比分析

集群調(diào)度的主要目標(biāo)是提高集群的利用率和使用效率。如圖12所示為三種調(diào)度方式。如圖13所示為三種調(diào)度方式。

圖12 三種調(diào)度方式的對比

宏調(diào)度(Monolithic schedulers)為所有任務(wù)都使用一個中心調(diào)度算法。其缺點是不易增加新的調(diào)度策略，也不能隨著集群的擴展而擴展。

兩層調(diào)度(Two-level schedulers)本質(zhì)上是在調(diào)度中分離資源分配和任務(wù)分配。使用一個動態(tài)資源管理器提供計算資源或者存儲資源給多個并行的調(diào)度框架。每一個調(diào)度框架所擁有的都是一個整個資源的一個子集。為什么是一個動態(tài)資源管理器呢?是相對于靜態(tài)的集群分區(qū)來說的。我們可以靜態(tài)的把集群分為幾個區(qū)，分別服務(wù)于不同的應(yīng)用。上面的動態(tài)資源管理器完成工作就是把靜態(tài)的分區(qū)工作動態(tài)化。由于兩層調(diào)度無法處理難以調(diào)度的挑剔任務(wù)，且不能根據(jù)整個集群的狀態(tài)做出決策，Google引入共享狀態(tài)調(diào)度架構(gòu)。

共享狀態(tài)調(diào)度(Shared state schedulers)使用無鎖的樂觀并發(fā)控制算法。Omega,Google的下一代調(diào)度系統(tǒng)中使用了該架構(gòu)。那么對比起來，兩層調(diào)度(Two-level schedulers)本質(zhì)上是悲觀調(diào)度算法。

在Omega看來， Mesos的offer 的機制本質(zhì)上是一個動態(tài)的過濾機制，這樣 Mesos Master向應(yīng)用框架提供的只是一個資源池的子集。當(dāng)然可以把這個子集擴大為一個全集，也就是Share state的，但其接口依然是悲觀策略的。

在Omega看來，YARN中的Application Masters提供的僅僅是一個任務(wù)管理服務(wù)，并不是一個真正的二層調(diào)度器。其次，到目前為止，YARN只支持一種資源類型。另外，盡管YARN中的Application Masters可以請求一個特定節(jié)點的資源，但是其具體策略是不清晰的。

圖13所示幾種調(diào)度策略的對比：

圖13 調(diào)度策略的對比(包含靜態(tài)分區(qū))

3.下一步工作

集群調(diào)度技術(shù)仍在發(fā)展之中，OSDI 16將會發(fā)布一些***的關(guān)于調(diào)度的文章，包括Google的Rapid:Fast, Centralized Cluster Scheduling at Scale，后面會支持關(guān)注。

資源感知調(diào)度。利用機器學(xué)習(xí)從歷史負載變化中預(yù)測資源需求模型，為調(diào)度決策提供依據(jù)。

【本文是51CTO專欄作者石頭的原創(chuàng)文章，轉(zhuǎn)載請通過作者微信公眾號補天遺石(butianys)獲取授權(quán)】

戳這里，看該作者更多好文