隨著分布式計(jì)算集群規(guī)模的不斷擴(kuò)張，任務(wù)調(diào)度系統(tǒng)的穩(wěn)定性成為了整個(gè)集群穩(wěn)定的關(guān)鍵因素。隨著容器技術(shù)的快速興起，基于容器的計(jì)算平臺(tái)被大量應(yīng)用，任務(wù)調(diào)度的規(guī)模及頻率快速上升，這對(duì)任務(wù)調(diào)度系統(tǒng)提出了更為嚴(yán)苛的挑戰(zhàn)。常見(jiàn)的調(diào)度系統(tǒng)往往兼顧了準(zhǔn)確度卻犧牲了性能，容器調(diào)度的復(fù)雜性使得在準(zhǔn)確和效率之間找到平衡點(diǎn)很難，尤其是在交互式調(diào)度的場(chǎng)景下，可取的解決方案更是捉襟見(jiàn)肘。本篇文章就以此為背景，介紹大規(guī)模調(diào)度場(chǎng)景下分布式任務(wù)調(diào)度的難點(diǎn)、解決策略及現(xiàn)有的一些方案。

任務(wù)調(diào)度框架的設(shè)計(jì)目標(biāo)

計(jì)算任務(wù)通常分為兩個(gè)大的類(lèi)別，即以守護(hù)進(jìn)程形式運(yùn)行的長(zhǎng)任務(wù)和以批處理形式運(yùn)行的短任務(wù)，前者資源的使用率變化幅度小，而后者資源使用率變化大。本篇我們討論的主要是針對(duì)計(jì)算密集型的場(chǎng)景，即以批處理形式運(yùn)行的數(shù)據(jù)處理任務(wù)。

調(diào)度系統(tǒng)的核心目標(biāo): 快速準(zhǔn)確地為任務(wù)匹配合適的計(jì)算資源。但快速(Low Placement latency)和準(zhǔn)確(High Quality Placement
)這兩個(gè)目標(biāo)會(huì)產(chǎn)生矛盾，即必須在二者間權(quán)衡。尤其是在交互式調(diào)度場(chǎng)景下，只追求準(zhǔn)確度而忽視效率會(huì)使得調(diào)度失去意義。

調(diào)度系統(tǒng)的本質(zhì)是為計(jì)算任務(wù)匹配合適的資源，使其能夠穩(wěn)定高效地運(yùn)行，而影響應(yīng)用運(yùn)行的因素非常多，比如CPU、內(nèi)存、網(wǎng)絡(luò)、端口等等一系列因素都會(huì)影響應(yīng)用運(yùn)行的表現(xiàn)。于此同時(shí)，整個(gè)計(jì)算集群的資源使用情況是動(dòng)態(tài)變化的，大量的應(yīng)用被創(chuàng)建、銷(xiāo)毀和遷移，調(diào)度決策的過(guò)程如果不夠快，那么實(shí)際運(yùn)行時(shí)面對(duì)的資源情況可能與決策時(shí)千差萬(wàn)別。

計(jì)算任務(wù)的調(diào)度不僅僅要考慮資源本身的狀況，而且還要結(jié)合任務(wù)本身的優(yōu)先級(jí)來(lái)考慮搶占式調(diào)度的情景。比如系統(tǒng)出現(xiàn)異常，臨時(shí)增加診斷性任務(wù)，就必須以高于其他任務(wù)的優(yōu)先級(jí)來(lái)運(yùn)行。有資源搶占就涉及到任務(wù)驅(qū)逐、重調(diào)度等情況，這里面會(huì)涉及驅(qū)逐相關(guān)的算法策略、調(diào)度流程的復(fù)用等。

目前的主流任務(wù)調(diào)度框架

從目前常用的任務(wù)調(diào)度框架來(lái)看，Apache Mesos是面向數(shù)據(jù)中心資源管理的典型代表。Hadoop YARN調(diào)度器是面向計(jì)算任務(wù)的，與Mesos相似之處在于也是兩層調(diào)度機(jī)制，不同在于考慮了資源搶占機(jī)制，能夠處理任務(wù)的優(yōu)先級(jí)對(duì)調(diào)度結(jié)果的影響。這些年發(fā)展迅速的Kubernetes也包含調(diào)度器，其本質(zhì)上還是面向應(yīng)用運(yùn)行層面，默認(rèn)調(diào)度器的策略比較豐富，擴(kuò)展性也比較好，但在面對(duì)大規(guī)模的調(diào)度時(shí)，吞吐性能表現(xiàn)不是那么完美。

Apache Mesos

Apache Mesos將CPU、內(nèi)存、存儲(chǔ)和其他計(jì)算資源從機(jī)器(物理或虛擬)中抽象出來(lái)，使容錯(cuò)和彈性分布式系統(tǒng)能夠輕松構(gòu)建并有效運(yùn)行。Mesos采用的Resource Offer使得任務(wù)框架能夠自行決定是否接受Mesos Master的Offer，在實(shí)際使用過(guò)程中，資源框架中的調(diào)度機(jī)制需要用戶(hù)自行實(shí)現(xiàn)，還是略微有些工作量的。

上述調(diào)度過(guò)程分為四個(gè)步驟:

• Agent1 向Master匯報(bào)節(jié)點(diǎn)當(dāng)前的資源情況，Master根據(jù)某種策略決定將Resource Offer給Framework1。
• Master將Resource Offer給Framework1，即將Agent1的所有資源分配給Framework1使用。
• Agent1 回復(fù)Master的Resource Offer，告訴Master將有兩個(gè)任務(wù)運(yùn)行在Agent1上，及各任務(wù)需要的資源情況。
• 最后，Master將任務(wù)發(fā)給Agent1，Agent1會(huì)為Framework的executor分配合適的資源，F(xiàn)ramework的executor隨即會(huì)啟動(dòng)兩個(gè)任務(wù)。剩下的資源Master的Allocation Module會(huì)發(fā)Resource Offer給Framework2。

這里著重需要關(guān)注兩個(gè)問(wèn)題:

• Mesos Master發(fā)送Resource Offer的時(shí)候，并不知道Framework的資源需求，如何知道該把Resource Offer發(fā)給哪個(gè)Framework？
• 在任務(wù)量比較大的時(shí)候，F(xiàn)ramework 與Master通信的性能如何保證？

對(duì)于第一個(gè)問(wèn)題，Mesos提供了”reject offer”的機(jī)制，允許Framework暫時(shí)拒絕不滿足其資源需求的Resource Offer，具體拒絕的策略由各個(gè)框架自行決定。

因此在Master與Framework通信的問(wèn)題上，Mesos提供了”filter”和”rescinds”機(jī)制，前者可以只接收剩余資源量大于L的Resource Offer，從而屏蔽掉部分流量，后者則允許某個(gè)Framework在一定的時(shí)間內(nèi)沒(méi)有為分配的資源返回對(duì)應(yīng)的任務(wù)，則Mesos會(huì)回收其資源量，并將這些資源分配給其他framework。

Mesos調(diào)度采用Dominant Resource Fairness(DRF)策略，是一種支持多資源的max-min fair資源分配機(jī)制。在調(diào)度時(shí)先找出用戶(hù)(這里指具體的Framework)的支配性資源，DRF將均衡所有用戶(hù)的支配性資源，確保每個(gè)用戶(hù)獲取了最大比例的支配性資源。

Hadoop YARN調(diào)度

Hadoop 的YARN模塊也具有為計(jì)算任務(wù)分配資源的能力，相應(yīng)地也具有調(diào)度能力。YARN將應(yīng)用的資源請(qǐng)求抽象為一個(gè)容器(Container)，具體的Application Master會(huì)接收容器，然后在容器中啟動(dòng)這個(gè)任務(wù)。對(duì)于Hadoop來(lái)說(shuō)，任務(wù)注意分為兩類(lèi): Map 和 Reduce。

注意: 這里的容器不是云計(jì)算中所說(shuō)的具體容器技術(shù)，而是Hadoop YARN中一個(gè)抽象的資源的集合的概念。

在MapReduce應(yīng)用程序中，有多個(gè)map任務(wù)，每個(gè)任務(wù)都在集群中某個(gè)工作主機(jī)上的容器中運(yùn)行。同樣，還有多個(gè)reduce任務(wù)，每個(gè)還在運(yùn)行主機(jī)上的容器中運(yùn)行。

同時(shí)在YARN端，ResourceManager，NodeManager和ApplicationMaster一起工作以管理集群的資源，并確保任務(wù)以及相應(yīng)的應(yīng)用程序完整地完成。

調(diào)度本身并不是一個(gè)新的概念，個(gè)人計(jì)算機(jī)可以有多個(gè)CPU核，每個(gè)核運(yùn)行一個(gè)進(jìn)程，但同時(shí)運(yùn)行多達(dá)幾百個(gè)進(jìn)程。調(diào)度程序是操作系統(tǒng)的一部分，它將進(jìn)程分配給CPU內(nèi)核以在短時(shí)間內(nèi)運(yùn)行。

對(duì)于大規(guī)模的計(jì)算集群也一樣，應(yīng)用程序由群集上的多個(gè)任務(wù)(通常在不同的主機(jī)上)組成。集群調(diào)度程序基本上必須解決：

• 多租戶(hù): 在群集上，許多用戶(hù)代表多個(gè)組織啟動(dòng)了許多不同的應(yīng)用程序。 集群調(diào)度程序允許不同的工作負(fù)載同時(shí)運(yùn)行。即調(diào)度時(shí)必須考慮應(yīng)用發(fā)起者的身份，根據(jù)身份將任務(wù)分發(fā)到與用戶(hù)身份對(duì)應(yīng)的資源上。
• 可伸縮性: 集群調(diào)度程序需要擴(kuò)展到運(yùn)行許多應(yīng)用程序的大型集群。這意味著增加群集的大小應(yīng)該可以提高整體性能，而不會(huì)對(duì)系統(tǒng)延遲產(chǎn)生負(fù)面影響。調(diào)度程序需要確保在計(jì)算集群規(guī)模非常大的時(shí)候，依然可以高效地提供調(diào)度服務(wù)。

YARN使用隊(duì)列(Queue)在多個(gè)租戶(hù)之間共享資源。當(dāng)應(yīng)用程序提交給YARN時(shí)，調(diào)度程序會(huì)將它們分配給隊(duì)列。根隊(duì)列是所有隊(duì)列的父級(jí)。所有其他隊(duì)列都是根隊(duì)列或另一個(gè)隊(duì)列(也稱(chēng)為分層隊(duì)列)的子節(jié)點(diǎn)。隊(duì)列通常與用戶(hù)，部門(mén)或優(yōu)先級(jí)相對(duì)應(yīng)。Application Master跟蹤每個(gè)任務(wù)的資源需求并協(xié)調(diào)容器請(qǐng)求。這種方式允許更好的擴(kuò)展，因?yàn)镽M/調(diào)度程序不需要跟蹤在集群上運(yùn)行的所有容器。

在YARN支持的調(diào)度程序中，公平調(diào)度(Fair Scheduler)是一個(gè)受歡迎的方式。在最簡(jiǎn)單的形式中，它在集群上運(yùn)行的所有作業(yè)中公平地共享資源。

在實(shí)際的復(fù)雜調(diào)度場(chǎng)景中，還會(huì)有水平隊(duì)列的形式出現(xiàn)，其實(shí)是上述隊(duì)列的一種嵌套形式，即在隊(duì)列的中還包含子隊(duì)列，不同的子隊(duì)列在父隊(duì)列的權(quán)重的基礎(chǔ)上有各自的權(quán)重設(shè)置，這里不再贅述。

Firmament 調(diào)度

Firmament 通過(guò)對(duì)調(diào)度算法的優(yōu)化使得大規(guī)模計(jì)算集群的任務(wù)調(diào)度可以很好地在性能和準(zhǔn)確之間找到平衡。Firmament 的設(shè)計(jì)出發(fā)點(diǎn)主要有如下兩個(gè):

• 良好的決策很重要: 對(duì)于關(guān)鍵服務(wù)應(yīng)用程序，單個(gè)糟糕的調(diào)度決策可能會(huì)產(chǎn)生重大影響。
• 靈活的策略是關(guān)鍵: 不同的用戶(hù)和應(yīng)用程序具有不同的調(diào)度需求，因此根據(jù)工作負(fù)載定制調(diào)度策略非常重要。

既要保證單個(gè)決策的準(zhǔn)確性，又要保證調(diào)度策略的靈活性，這對(duì)于調(diào)度程序的性能提出了很高的要求，而Firmament的基于流圖的決策模式能夠有效解決這個(gè)問(wèn)題。這個(gè)調(diào)度程序的核心來(lái)自于Google的開(kāi)發(fā)者，開(kāi)發(fā)語(yǔ)言為C++，目前作為一個(gè)開(kāi)源項(xiàng)目，大家都可以共享自己的代碼。Firmament主要有以下三個(gè)特性:

• 通過(guò)對(duì)圖進(jìn)行最小成本優(yōu)化，F(xiàn)irmament根據(jù)調(diào)度策略為每個(gè)任務(wù)或容器找到最佳位置。
• 通過(guò)自定義底層圖形并通過(guò)回調(diào)接口設(shè)置其邊緣成本，用戶(hù)可以自定義Firmament以應(yīng)用自己的策略。
• Firmament的增量最小成本，最大流量解算器甚至可以在Google規(guī)模(12k機(jī)器)上做出快速的亞秒級(jí)調(diào)度決策。
• 最重要一點(diǎn): Firmament是全開(kāi)源的。

Firmament既可以獨(dú)立工作，也可以在集群管理器中工作，如Kubernetes這樣的容器管理集群，開(kāi)源項(xiàng)目Poseidon正是出于這樣的目的，將Firmament引入容器管理集群。

目前Firmament通過(guò)與容器管理集群結(jié)合，大幅度提升容器應(yīng)用的調(diào)度管理能力，解決像Kubernetes原生調(diào)度器在10K節(jié)點(diǎn)時(shí)，性能急劇下降且對(duì)批處理作業(yè)任務(wù)支持不夠完善的情況。Kubernetes原生調(diào)度器采用的基于隊(duì)列的模型，需要依賴(lài)于隊(duì)列的性能，而在任務(wù)調(diào)度失敗后，又再次回到隊(duì)列等待繼續(xù)調(diào)度，在對(duì)于計(jì)算密集型的任務(wù)調(diào)度時(shí)，對(duì)優(yōu)先級(jí)、資源狀態(tài)的共享支持都有待提升。

Firmament 采用的流圖的機(jī)制，綜合考慮了很多種影響調(diào)度結(jié)果的因素，比如Rack,AZ,Region等，甚至包括SSD硬件屬性，綜合這些因素考慮最小的成本，最大的流量來(lái)決定最終的調(diào)度結(jié)果。

Poseidon 主流應(yīng)用場(chǎng)景

Posedion 會(huì)充當(dāng) Firmament 與 Kubernetes 之間的橋梁，即通過(guò)Kubernetes API 獲取對(duì)象的事件(Event)，然后結(jié)合資源使用狀況，調(diào)用 Firmament 獲取調(diào)度的結(jié)果，最終完成 Pod 調(diào)度的過(guò)程。

Firmament ???以理解為獨(dú)立的核心算法模塊，功能與原來(lái)的默認(rèn)scheduler 相同，都是根據(jù)目前資源情況，給出最佳的調(diào)度結(jié)果。Firmament 本身由一系列的復(fù)雜算法組成，但對(duì)于 Posedion 來(lái)說(shuō)，這些細(xì)節(jié)可以不必關(guān)系，只需要了解輸入和輸出的標(biāo)準(zhǔn)數(shù)據(jù)結(jié)構(gòu)就好。

在具體使用的時(shí)候，F(xiàn)irmament、Poseidon 及 heapster 等模塊都是以 Deployment 形式部署在 Kubernetes 集群中的。在部署 Pod 的時(shí)候，我們知道 Kubernetes 支持多調(diào)度器機(jī)制，可以在 Pod 的定義中指定使用哪個(gè)調(diào)度器，具體示例如下： 

apiVersion: batch/v1  kind: Job  metadata:    name: cpuspin5  spec:    completions: 1    parallelism: 1    template:      metadata:        name: cpuspin5        labels:          schedulerName: poseidon      spec:        schedulerName: poseidon        containers:        - name: cpuspin          image: firmament/libhdfs3          resources:            requests:              memory: "10Mi"              cpu: "10m"            limits:              memory: "12Mi"              cpu: "20m"          command: ["/bin/sh", "-c", "/cpu_spin 60"]        restartPolicy: Never

我們?cè)谶@里選擇 posedion 作為其調(diào)度器，那么就可以通過(guò) Firmament 算法來(lái)更高效、精細(xì)地決策 Pod 在哪個(gè)節(jié)點(diǎn)運(yùn)行更合適，值得一提的是，其他的 Pod 如果不適合這些調(diào)度機(jī)制，完全可以選擇默認(rèn)調(diào)度器、甚至自定義的調(diào)度器，從而保證了平臺(tái)的靈活性。

任務(wù)調(diào)度框架的未來(lái)趨勢(shì)

任務(wù)調(diào)度框架其實(shí)已經(jīng)有很多，集中式和分布式的都有，一時(shí)間難以決定孰優(yōu)孰劣，畢竟調(diào)度跟具體的業(yè)務(wù)場(chǎng)景息息相關(guān)。在未來(lái)，調(diào)度會(huì)更加精細(xì)化、更靈活，根據(jù)用戶(hù)角色、業(yè)務(wù)類(lèi)型、資源需求等等一系列復(fù)雜的因素，結(jié)合歷史調(diào)度情況綜合給出最終的結(jié)論。有些類(lèi)似梯度遞減形式的機(jī)器學(xué)習(xí)模型可以開(kāi)始應(yīng)用在調(diào)度上，已經(jīng)有一些公司在做相關(guān)的探索，相信在未來(lái)大規(guī)模分布式調(diào)度會(huì)變得越來(lái)越重要。