這篇博客是關(guān)于大型機(jī)群任務(wù)調(diào)度系列的***篇，資源調(diào)度在Amazon、Google、Facebook、微軟或者Yahoo已經(jīng)有很好實(shí)現(xiàn)，在其 它地方的需求也在增長(zhǎng)。調(diào)度是很重要的課題，因?yàn)樗苯痈\(yùn)行集群的投入有關(guān)：一個(gè)不好的調(diào)度器會(huì)造成低利用率，昂貴投入的硬件資源被白白浪費(fèi)。而光靠它 自己也無法實(shí)現(xiàn)高利用率，因?yàn)橘Y源利用相抵觸的負(fù)載必須要仔細(xì)配置，正確調(diào)度。

架構(gòu)演進(jìn)

這篇博客討論了最近幾年調(diào)度架構(gòu)如何演進(jìn)，為什么會(huì)這樣。圖一演示了不同的方法：灰色方塊對(duì)應(yīng)一個(gè)設(shè)備，不同顏色圈對(duì)應(yīng)一個(gè)任務(wù)，有“S”的方形代表一個(gè)調(diào)度器。箭頭代表調(diào)度器的調(diào)度決定；三種顏色代表不同工作負(fù)載（例如，網(wǎng)站服務(wù)，批量分析，和機(jī)器學(xué)習(xí)）

圖一：不同調(diào)度架構(gòu)，灰色框代表集群設(shè)備，圓圈代表任務(wù)，Si代表調(diào)度器。

（a）單體式調(diào)度器（b）二級(jí)調(diào)度 （c）共享狀態(tài)調(diào)度 （d）分布式調(diào)度 (e) 混合式調(diào)度

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

單體式調(diào)度

單一調(diào)度進(jìn)程運(yùn)行在一臺(tái)物理機(jī)內(nèi)（例如Hadoop V1中JobTacker，Kubernetes中的kube-scheduler），將任務(wù)指派給集群內(nèi)其它物理機(jī)。所有負(fù)載都服從于一個(gè)調(diào)度器，所有 任務(wù)都通過這一個(gè)調(diào)度邏輯運(yùn)行（參見圖一a）。這種架構(gòu)最簡(jiǎn)單格式唯一，在此基礎(chǔ)上發(fā)展起了很多負(fù)載的調(diào)度器，例如Paragon和Quasar調(diào)度器， 采用機(jī)器學(xué)習(xí)方法來避免不同負(fù)載之間資源競(jìng)爭(zhēng)。

今天集群都運(yùn)行著不同類型的應(yīng)用（與之相對(duì)應(yīng)的是MapReduce早期作業(yè)場(chǎng)景），然而，采用單一調(diào)度器來處理這么復(fù)雜異構(gòu)負(fù)載會(huì)很棘手，有幾個(gè)原因：

1. 調(diào)度器必須區(qū)分對(duì)待長(zhǎng)期運(yùn)行服務(wù)作業(yè)和批量分析作業(yè)，這是合理的需求。

2. 因?yàn)椴煌瑧?yīng)用有不同的需求，催生調(diào)度器內(nèi)加入更多功能，增加業(yè)務(wù)邏輯和部署方式。

3. 調(diào)度器處理任務(wù)順序變成一個(gè)問題：如果調(diào)度器不仔細(xì)設(shè)計(jì)，隊(duì)列效果（例如線頭阻塞head-of-line blocking）和回滾會(huì)成為問題。

總之，這聽起來像是給工程師帶來噩夢(mèng)，調(diào)度器維護(hù)者面對(duì)的沒完沒了的功能請(qǐng)求證實(shí)了這點(diǎn)。

二級(jí)調(diào)度

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

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

1. 重入優(yōu)先權(quán)（也就是高優(yōu)先權(quán)會(huì)將低優(yōu)先權(quán)任務(wù)剔除）實(shí)現(xiàn)變的很困難。在基于offer模式，被運(yùn)行中任務(wù)占用的資源對(duì)高一級(jí)調(diào)度器不可見；在基于request模式，底層資源管理器必須理解重入策略（跟應(yīng)用相關(guān)）。

2. 調(diào)度器不能介入運(yùn)行中業(yè)務(wù)，有可能減低資源使用效率（例如，“饑餓鄰居”占據(jù)了IO帶寬），因?yàn)檎{(diào)度器看不見他們。

3. 應(yīng)用相關(guān)調(diào)度器更關(guān)注底層資源使用的不同情況，但是他們唯一選擇資源的方法就是資源管理器提供的Offer/request接口，這個(gè)接口很容易變的很復(fù)雜。

共享狀態(tài)架構(gòu)

共享狀態(tài)架構(gòu)通過采用半分布式模式來解決這個(gè)問題，這種架構(gòu)下集群狀態(tài)多副本會(huì)被應(yīng)用層次調(diào)度器獨(dú)立更新，如圖一C中所示。一旦本地有更新，調(diào)度器發(fā)布一個(gè)并發(fā)交易更新所有共享集群狀態(tài)。有時(shí)候因?yàn)榱硗庖粋€(gè)調(diào)度器發(fā)出了一個(gè)沖突交易，交易更新有可能失敗。

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

邏輯上來說，共享狀態(tài)設(shè)計(jì)不一定必需將全狀態(tài)分布在其它地方，這種方式（有點(diǎn)像Apollo）每個(gè)物理設(shè)備維護(hù)自己的狀態(tài)，將更新發(fā)送到其它感興趣 的代理，例如調(diào)度器，設(shè)備健康監(jiān)控，和資源監(jiān)控系統(tǒng)。每個(gè)物理設(shè)備本地狀態(tài)就成為一個(gè)全局共享狀態(tài)的“溝通片”（shard）。

然而，共享狀態(tài)架構(gòu)也有一些缺點(diǎn)，必須作用在穩(wěn)定的（過時(shí)的，stale）信息（這點(diǎn)跟中心化調(diào)度器不同），有可能在高競(jìng)爭(zhēng)情況下造成調(diào)度器性能下降（盡管對(duì)其它架構(gòu)也有這種可能）。

全分布式架構(gòu)

看起來這種架構(gòu)更加去中心化：調(diào)度器之間沒有任何協(xié)調(diào)，使用很多各自獨(dú)立調(diào)度器響應(yīng)不同負(fù)載，如圖一d所示。每個(gè)調(diào)度器都作用于自己本地（部分或者 經(jīng)常過時(shí)的【stale】）集群狀態(tài)信息。典型的，作業(yè)可以提交到任何調(diào)度器，調(diào)度器可以將作業(yè)發(fā)布到任何集群節(jié)點(diǎn)上執(zhí)行。跟二級(jí)調(diào)度器不同的是，每個(gè)調(diào) 度器并沒有負(fù)責(zé)的分區(qū)，全局調(diào)度和資源分區(qū)是服從統(tǒng)計(jì)意義和隨機(jī)分布的，這有點(diǎn)像共享狀態(tài)架構(gòu)，但是沒有中央控制。

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

這個(gè)實(shí)現(xiàn)意義重大：去中心化理論上意味著更多的仲裁，但是這非常適合某類負(fù)載，我們會(huì)在后面的連載中討論?，F(xiàn)在，足夠理由證明，由于分布式調(diào)度是無協(xié)調(diào)的，因此相對(duì)于復(fù)雜單體式調(diào)度，二級(jí)調(diào)度或者分布狀態(tài)時(shí)調(diào)度，更適合于簡(jiǎn)單邏輯。例如：

1. 分布式調(diào)度是基于簡(jiǎn)單的“時(shí)間槽（slot）”概念，將每臺(tái)設(shè)備分成n個(gè)標(biāo)準(zhǔn)時(shí)間槽，同時(shí)運(yùn)行n個(gè)并發(fā)任務(wù)，盡管這種簡(jiǎn)化忽略了任務(wù)資源需求是各自不同的事實(shí)。

2. 在任務(wù)端（worker side）使用服從簡(jiǎn)單服務(wù)規(guī)則的隊(duì)列方式（例如Sparrow中FIFO），這樣調(diào)度器的靈活性受到限制，調(diào)度器只需決定在哪臺(tái)設(shè)備上將任務(wù)入隊(duì)。

3. 因?yàn)闆]有中央控制，分布式調(diào)度器對(duì)于全局變量設(shè)置（例如，fairness policies或者strict priority precedence等）有一定難度。

4. 因?yàn)榉植际秸{(diào)度是為基于最少知識(shí)做出快速?zèng)Q策而設(shè)計(jì)，因此無法支持或承擔(dān)復(fù)雜應(yīng)用相關(guān)調(diào)度策略，因此避免任務(wù)之間干擾，對(duì)于全分布式調(diào)度來說很困難。

混合式架構(gòu)

混合式架構(gòu)是為了解決全分布式架構(gòu)缺陷，最近（發(fā)端于學(xué)院派）提出的解決方式，它綜合了單體式或者共享狀態(tài)的設(shè)計(jì)。這種方式，例如 Tarcil，Mercury和Hawk，一般有兩條調(diào)度路徑：一條是為部分負(fù)載設(shè)計(jì)的分布式路徑（例如，短時(shí)間任務(wù)或者低優(yōu)先級(jí)批量負(fù)載），另外一條集 中式調(diào)度，處理剩下負(fù)載，如圖一e所示。對(duì)于所描述的負(fù)載來說，混合架構(gòu)中發(fā)生作用的調(diào)度器都是唯一的。實(shí)際上，據(jù)我所知，目前還沒有真正的混合架構(gòu)部署 于生產(chǎn)系統(tǒng)中。

實(shí)際意義

不同調(diào)度架構(gòu)相對(duì)價(jià)值，除了有很多研究論文外，其討論不僅僅局限在學(xué)院內(nèi)，從行業(yè)角度對(duì)于Borg，Mesos和Omega論文的深入討論，可以參 見Andrew Wang的專業(yè)博客。然而，很多以上討論的系統(tǒng)都已經(jīng)部署在大型企業(yè)生產(chǎn)系統(tǒng)中（例如，微軟的Apollo，Google的Borg，Apple的 Mesos），反過來這些系統(tǒng)激勵(lì)了其它可用開源項(xiàng)目。

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

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

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

決定一個(gè)合適調(diào)度架構(gòu)主要因素在于你的集群是否運(yùn)行一個(gè)異構(gòu)（或者說混合的）負(fù)載。例如，前端服務(wù)（例如，負(fù)載均衡web 服務(wù)和memcached）和批量數(shù)據(jù)分析（例如，MapReduce或者Spark）混合在一起，這種組合對(duì)于提高系統(tǒng)利用率是有意義的，但是不同應(yīng)用 需要不同調(diào)度方式。在混合設(shè)定下，單體式調(diào)度很可能導(dǎo)致次優(yōu)任務(wù)分配，因?yàn)榛趹?yīng)用需求，單體調(diào)度邏輯不能多樣化，而此時(shí)二級(jí)或者共享狀態(tài)調(diào)度可能更加適 合一些。

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

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

現(xiàn)在，我們可以證明分布式調(diào)度比其他調(diào)度架構(gòu)更加簡(jiǎn)單，而且不支持其他資源維度，過分配或者重新調(diào)度。

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

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

下一步

下一篇博客將會(huì)討論全分布式架構(gòu)對(duì)于可擴(kuò)展式集群調(diào)度是否關(guān)鍵技術(shù)創(chuàng)新（反對(duì)聲音說：不是必須的）。然后，我們會(huì)討論資源適配策略（提高利用率），***討論我們Firmament調(diào)度平臺(tái)如何組合和共享狀態(tài)架構(gòu)和單體式調(diào)度質(zhì)量，以及全分布調(diào)度器性能問題。