林起勛，錢(qián)德沛，欒鐘治

北京航空航天大學(xué)，北京 100191

1 概述

隨著計(jì)算機(jī)科學(xué)技術(shù)的不斷進(jìn)步與發(fā)展、數(shù)據(jù)規(guī)模的不斷增大，無(wú)論是科學(xué)計(jì)算還是工業(yè)應(yīng)用都對(duì)計(jì)算資源的需求量都在不斷增加，同時(shí)對(duì)系統(tǒng)吞吐也提出了更高的要求。通常，擁有更多計(jì)算資源可以更高效、更準(zhǔn)確地解決問(wèn)題。而隨著集群規(guī)模的不斷增大和工作負(fù)載復(fù)雜性的不斷增加，合理的資源分配和高效的作業(yè)調(diào)度算法對(duì)于提高系統(tǒng)整體資源利用率、作業(yè)吞吐量、程序性能等起著至關(guān)重要的作用。因此，資源調(diào)度系統(tǒng)如何更好地管理集群資源、將資源與用戶(hù)作業(yè)進(jìn)行高效匹配，以系統(tǒng)提高資源利用率和作業(yè)吞吐量等問(wèn)題一直是集群研究的熱鬧話題。

集群 (Cluster)[1]是通過(guò)網(wǎng)絡(luò)互相連接的多個(gè)獨(dú)立的計(jì)算機(jī)的集合。按照核心技術(shù)的不同，可以將集群分高可用集群和高性能集群兩大類(lèi)。高可用集群主要是對(duì)系統(tǒng)出現(xiàn)某些故障時(shí)如何繼續(xù)對(duì)外提供服務(wù)，保證服務(wù)不間斷、保證數(shù)據(jù)的安全和完整性方面有著較高的要求。高性能集群的目的是提供與節(jié)點(diǎn)數(shù)成正比的負(fù)載能力，并且節(jié)點(diǎn)可根據(jù)使用情況隨意增加或刪除，主要用于只有超級(jí)計(jì)算機(jī)才能完成的計(jì)算任務(wù)。但高性能集群一般也具有一定高可用性的特點(diǎn)[2]。本文討論的是集群的資源管理與調(diào)度、資源利用率、作業(yè)吞吐等方面問(wèn)題，因此研究的重點(diǎn)是高性能集群。

集群一般包括資源組織模型、調(diào)度策略、任務(wù)組織模型三個(gè)要素。如圖 1 所示。

資源組織模型即集群中資源的組織形式，常見(jiàn)的資源組織方式是多層隊(duì)列方式，其次是平級(jí)多隊(duì)列和單隊(duì)列模型。調(diào)度策略指將資源分配給用戶(hù)的原則和方法，常見(jiàn)的調(diào)度策略包括 FIFO、公平調(diào)度、能力調(diào)度、延遲調(diào)度、回填機(jī)制等。任務(wù)組織模型一般與調(diào)度策略直接相關(guān)，即將多用戶(hù)提交的多任務(wù)按一定方式組織起來(lái)，方便后續(xù)的資源分配。本文主要討論資源的組織模型、任務(wù)的調(diào)度策略及回填算法對(duì)提高資源利用率方面的運(yùn)用。

2 集群資源組織模型

集群資源組織就是集群通過(guò)何種方式將將群集中的計(jì)算資源組織起來(lái)，以方便通過(guò)某種策略將資源分配給相應(yīng)的用戶(hù)使用，是集群資源統(tǒng)一管理的基礎(chǔ)。通常集群的計(jì)算資源主要指 CPU 和 GPU 等，但實(shí)際上內(nèi)存、磁盤(pán)、I/O 和網(wǎng)絡(luò)帶寬等也直接影響著集群的計(jì)算能力，因此也屬于計(jì)算資源的范疇。如何對(duì)這些不同的資源類(lèi)型進(jìn)行合理的組織和表示，直接影響著調(diào)度策略和實(shí)施和集群利用率的提高。

2.1 基于 slot 的資源組織方式

圖1 集群模型圖Fig.1 Cluster model diagram

集群中各個(gè)節(jié)點(diǎn)上的資源包括 CPU、GPU、內(nèi)存、磁盤(pán)、I/O 和網(wǎng)絡(luò)帶寬等多種類(lèi)型，是多維的。許多計(jì)算框架，如 Hadoop[3]、HTCondor[4]，通過(guò)引入“槽位 (slot)”的概念來(lái)簡(jiǎn)化“多維”問(wèn)題。

事實(shí)上，采用 slot 來(lái)表示計(jì)算資源就是將節(jié)點(diǎn)上的計(jì)算資源切分成若干個(gè)大小相等的部份，每一份用一個(gè) slot 表示。調(diào)度模塊再根據(jù)用戶(hù)需求，按照相應(yīng)的調(diào)度策略將不同數(shù)量的 slot 分配給不同的用戶(hù)使用。這樣，就將各個(gè)節(jié)點(diǎn)上多維度的資源分配就抽象成了單一維度的slot資源分配，簡(jiǎn)化了調(diào)度策略的實(shí)現(xiàn)，降低了資源管理問(wèn)題的復(fù)雜度。用戶(hù)的作業(yè)只有獲得 slot 以后才能運(yùn)行，節(jié)點(diǎn)上 slots 的數(shù)量則決定了該節(jié)點(diǎn)上任務(wù)最大允許的并發(fā)度。

Hadoop 為了區(qū)分所用資源類(lèi)型和資源量的差異，將 slot 區(qū)分 Map slot 和 Reduce slot 兩種類(lèi)型，Map Task 使用 Map slots，Reduce Task 使用 Reduce slots，一一對(duì)應(yīng)。對(duì)于 MapReduce 程序，在開(kāi)始階段優(yōu)先調(diào)度 Map Task，只有當(dāng) Map Task 完成一定比例后才開(kāi)始調(diào)度 Reduce Task。在這種模式下，容易出現(xiàn)任務(wù)開(kāi)始階段 Map Slot 資源緊張、Reduce Slot 空閑，MapTask 全部完成后 Map Slot 空閑、Reduce Slot緊張的情況，這就是造成了 slots 的利用率不高，集群整體性能受到影響。

文獻(xiàn) [5] 提出了一種基于無(wú)類(lèi)別差異 (不區(qū)分Map slot 和 Reduce slot) 的 Slot 資源管理方式：即所有節(jié)點(diǎn)上的 Slots 是同質(zhì)的，代表了相同的資源；所有的任務(wù)共享所有 slots，如何分配完全由調(diào)度器來(lái)決定。這種劃分方法能夠解決上述 Hadoop 中區(qū)分 Map slot 和 Reduce slot 在不同執(zhí)行階段不同類(lèi)型 slot 間負(fù)載嚴(yán)重不均衡的情況，但這種劃分形式的劃分粒度過(guò)于粗糙，對(duì)于資源需求多樣化及異構(gòu)環(huán)境中，很容易會(huì)造成某些節(jié)點(diǎn)的資源利用率過(guò)高或過(guò)低[6]。

以上所述的有/無(wú)類(lèi)型差別的slot資源表示形式，均是采用靜態(tài)資源配置策略。也就是說(shuō)，需要預(yù)先配置好每個(gè)節(jié)點(diǎn)所需的 slots 數(shù)量，并且在啟動(dòng)后就無(wú)法動(dòng)態(tài)修改。而在實(shí)際應(yīng)用中，不同的作業(yè)對(duì)資源的需求差異較大，靜態(tài)配置的方式容易造成資源分配不均和利用率不高等問(wèn)題。文獻(xiàn) [7] 提出了一種動(dòng)態(tài)調(diào)整節(jié)點(diǎn)上Slots數(shù)量的資源管理方案：在節(jié)點(diǎn)上添加SlotsAdjuster (Slots 動(dòng)態(tài)調(diào)整模塊)，SlotsAdjuster 可以根據(jù)節(jié)點(diǎn)上的資源使用情況來(lái)動(dòng)態(tài)地調(diào)整 slots 數(shù)量，以促進(jìn)資源的合理利用。該方案曾經(jīng)在 Ali“云梯”集群上投入了使用。

2.2 基于真實(shí)需求量的資源組織方式

為了進(jìn)一步提高集群資源的利用率，有必要對(duì)資源進(jìn)行更精細(xì)的劃分?；貧w資源分配的本質(zhì)：用戶(hù)任務(wù)的資源需求實(shí)際上是對(duì)各類(lèi)不同類(lèi)型資源的具體數(shù)量需求。在實(shí)際系統(tǒng)中，資源包括 CPU、內(nèi)存、磁盤(pán)、I/O 和網(wǎng)絡(luò)等不同的類(lèi)型，是一個(gè)多維的概念，如果要對(duì)其進(jìn)行精確控制和分配，基于 Slot 的劃分概念不再適用，最直接有效的方法是由用戶(hù)明確自己的資源類(lèi)型需求及相應(yīng)數(shù)量 (比如，2GB 內(nèi)存和 1 個(gè)CPU)，而調(diào)度器則按照用戶(hù)的實(shí)際資源需求類(lèi)型和數(shù)量，為其精細(xì)地分配相應(yīng)的資源量，如圖 2 所示，調(diào)度器根據(jù)各個(gè)任務(wù)的資源需求量為每個(gè)任務(wù)在某個(gè)節(jié)點(diǎn)上分配對(duì)應(yīng)的計(jì)算資源 (這里以 CPUs，Memory兩種資源為例)。

針對(duì)單維度的資源分配策略，有許多基于最大最小公平 (max-min Fairness) 原則[8]的算法。例如加權(quán)公平隊(duì)列[9]、輪詢(xún)和均衡資源共享[10]等。這些算法被應(yīng)用于各種各樣的資源分配上，包括 CPU[9][11]、內(nèi)存[11]及二級(jí)存儲(chǔ)空間、網(wǎng)絡(luò)帶寬[12-14]等。

針對(duì)多維度的資源分配策略，文獻(xiàn) [6] 提出了主資源公平調(diào)度算法 (Dominant ReSource Fairness，DRF)。DRF 也是基于 Max-Min Fairness 提出來(lái)的，但它在保證公平的前提下支持多維度資源調(diào)度。DRF根據(jù)用戶(hù)對(duì)某種類(lèi)型的資源需求占該類(lèi)型可用資源的比例來(lái)確定該任務(wù)的主導(dǎo)資源，并為主資源占有比例最小的用戶(hù)分配資源。DRF 非常適用于需求異構(gòu)和多類(lèi)型資源分配的環(huán)境中，被 Apache YARN 和 Apache Mesos 等越來(lái)越多的系統(tǒng)采用。與基于 slot 的資源表示模型相比，基于真實(shí)資源需求的資源表示模型能夠更好地提高集群資源利用率，越來(lái)越多基于真實(shí)資源需求表示模型、支持多維度資源的分配調(diào)度算法被提出[15-16]。

圖2 基于真實(shí)資源需求量的資源表示模型Fig.2 Resource represontation model based on real resource demard

3 集群調(diào)度策略

資源調(diào)度是根據(jù)可支配資源數(shù)量和用戶(hù)需求，按照一定資源分配策略，在系統(tǒng)資源和用戶(hù)需求之間進(jìn)行匹配和調(diào)整的過(guò)程。資源調(diào)度的目的是將合適的資源提供給需要用戶(hù)，以完成其相應(yīng)的任務(wù)。同時(shí)還要盡可能提高服務(wù)質(zhì)量、系統(tǒng)吞吐和資源利用率。不同的用戶(hù)對(duì)服務(wù)質(zhì)量有著不同的定義，如對(duì)于批處理作業(yè)用戶(hù)主要在意的是系統(tǒng)的吞吐；交互式作業(yè)用戶(hù)則要求有較好的實(shí)時(shí)性；而生產(chǎn)性作業(yè)用戶(hù)則要求以可靠性為前提。不同的計(jì)算架構(gòu)在設(shè)計(jì)時(shí)也是針對(duì)或比較擅長(zhǎng)于處理某一類(lèi)任務(wù)，資源管理和調(diào)度的優(yōu)劣也沒(méi)統(tǒng)一的衡量標(biāo)準(zhǔn)。

3.1 資源調(diào)度模型

根據(jù)資源的組織調(diào)度形式不同，資源管理調(diào)度模型可分為集中調(diào)度模型、分層調(diào)度模型和非集中調(diào)度模型三種。文獻(xiàn) [17] 介紹了谷歌下一代集群管理系統(tǒng)Omega 的設(shè)計(jì)細(xì)節(jié)，及其經(jīng)歷三代資源調(diào)度器的架構(gòu)：集中式調(diào)度模型、兩級(jí)調(diào)度模型和狀態(tài)共享調(diào)度模型，如圖 4 所示。

集中式調(diào)度器在整個(gè)系統(tǒng)中只運(yùn)行一個(gè)全局的中央調(diào)度器實(shí)例，所有計(jì)算任務(wù)的資源請(qǐng)求及節(jié)點(diǎn)信息全部匯集到中心節(jié)點(diǎn)上，再由中央調(diào)度器進(jìn)行資源和用戶(hù)任務(wù)的匹配，并在完成匹配后將資源分發(fā)給用戶(hù)。MRv1 中 JobTracker 的實(shí)現(xiàn)是典型的代表:集群中各個(gè)節(jié)點(diǎn)的信息和資源量匯總后存放于 JobTracker中，JobTracker 負(fù)責(zé)資源的管理和作業(yè)的調(diào)度[18]。

這種架構(gòu)由于中央調(diào)度器同時(shí)負(fù)責(zé)集群管理和作業(yè)調(diào)度，所有的調(diào)度邏輯都集中于中心結(jié)點(diǎn)，導(dǎo)致了集中式調(diào)度這種架構(gòu)存在擴(kuò)展性差，集群規(guī)模受限，支持的任務(wù)單一等問(wèn)題。

文獻(xiàn) [17] 中提到了一種多路徑調(diào)度方案對(duì)集中式調(diào)度器進(jìn)行優(yōu)化，它可根據(jù)不同任務(wù)來(lái)進(jìn)行不同調(diào)度策略的選擇，類(lèi)似于 Switch-Case 分支路徑判斷。在集群規(guī)模較小、作業(yè)量不大時(shí)，作業(yè)響應(yīng)的時(shí)間可以大大縮短。但這種方案實(shí)現(xiàn)邏輯復(fù)雜，支持不同類(lèi)型的調(diào)度策略靈活性不夠，同樣存在擴(kuò)展性和并發(fā)性差、不適合大規(guī)模集群系統(tǒng)等問(wèn)題。

圖3 Google 提出的三種高度模型架構(gòu) [14]Fig.3 Three high-level model frameworks proposed by Google

兩級(jí)調(diào)度器包括中央調(diào)度器和框架調(diào)度器，采用分而治之策略來(lái)解決集中式調(diào)度器存在的不足。其中的中央調(diào)度器僅負(fù)責(zé)管理資源，是一個(gè)簡(jiǎn)化的中央式調(diào)度器。它按照一定的策略將可用的資源推送給各個(gè)框架，但并不負(fù)責(zé)具體的任務(wù)調(diào)度，是一種粗粒度的資源調(diào)度方式。對(duì)于中央調(diào)度器推送的資源，計(jì)算框架可以選擇接受或拒絕?？蚣苷{(diào)度器在接受分配的資源后，根據(jù)自身計(jì)算任務(wù)的特性，使用自身的調(diào)度策略，來(lái)進(jìn)一步細(xì)粒度地將資源分配給各個(gè)應(yīng)用，進(jìn)而實(shí)現(xiàn)兩級(jí)調(diào)度。當(dāng)前眾所周知的開(kāi)源資源統(tǒng)一管理調(diào)度平臺(tái) Mesos[19]和 YARN[20][21]都是采用兩級(jí)調(diào)度模型。

兩級(jí)調(diào)度模型能夠較好解決集中調(diào)度模型規(guī)模受限等問(wèn)題，但是同樣也存在一些不足：①外部框架無(wú)法檢測(cè)整個(gè)集群資源的實(shí)時(shí)使用情況，無(wú)法利用潛在的優(yōu)化空間；②采用悲觀鎖，在中央調(diào)度器對(duì)推送的資源進(jìn)行全局加鎖控制，直到外部框架使用完返回時(shí)才釋放，造成了集群的并發(fā)性受到限制。

為克服兩級(jí)調(diào)度模型的上述不足，谷歌提出了Shared-state scheduling (共享狀態(tài)調(diào)度模型)，并以該模型為依據(jù)研發(fā)下一代資源管理系統(tǒng) Omega[17]。共享狀態(tài)調(diào)度是將兩級(jí)調(diào)度中的中央式資源調(diào)度模塊簡(jiǎn)化為持久化共享數(shù)據(jù)，即各節(jié)點(diǎn)共享整個(gè)集群的實(shí)時(shí)資源使用信息。引入共享數(shù)據(jù)后，共享調(diào)度模型的核心變成了共享數(shù)據(jù)的并發(fā)訪問(wèn)方式；采用了樂(lè)觀鎖(MVCC，Multi-Version Concurrency Control) 進(jìn)行并發(fā)訪問(wèn)控制，來(lái)提升了系統(tǒng)并發(fā)性。

3.2 任務(wù)調(diào)度器

分布式環(huán)境下的資源分配問(wèn)題，實(shí)際上就是任務(wù)調(diào)度問(wèn)題。其主要任務(wù)是根據(jù)當(dāng)前集群中各個(gè)節(jié)點(diǎn)上資源的剩余情況和各個(gè)用戶(hù)作業(yè)對(duì)相應(yīng)資源的需求量，在資源和作業(yè)/任務(wù)之間進(jìn)行匹配，達(dá)到服務(wù)質(zhì)量最優(yōu)的目的。但不同用戶(hù)對(duì)服務(wù)質(zhì)量有著不同的具體要求，同一個(gè)用戶(hù)的要求也有可能是多樣化的，因此，分布式系統(tǒng)中的任務(wù)調(diào)度是實(shí)質(zhì)上是一個(gè)多目標(biāo)優(yōu)化問(wèn)題，一個(gè)典型的 NP-hard 問(wèn)題。

先來(lái)先服務(wù) (First Come First Service，F(xiàn)CFS) 調(diào)度機(jī)制是調(diào)度器按照作業(yè)提交時(shí)間的先后順序來(lái)確定下一個(gè)調(diào)度執(zhí)行的作業(yè)。大多分布式系統(tǒng)都會(huì)提供這一調(diào)度機(jī)制。該調(diào)度策略簡(jiǎn)單易實(shí)現(xiàn)且能保證公平，但容易存在大量的資源碎片，導(dǎo)致系統(tǒng)資源利用率不高。

為了克服 FCFS 單隊(duì)列存在的不足之處，多種類(lèi)型的多用戶(hù)多隊(duì)列調(diào)度器相繼出現(xiàn)。在這些調(diào)度策略下，管理員可以根據(jù)應(yīng)用需求對(duì)用戶(hù)/應(yīng)用程序進(jìn)行分組，并為各自分配不同的資源量，同時(shí)還可利用約束條件來(lái)防止單個(gè)用戶(hù)/應(yīng)用程序獨(dú)占資源，以盡可能地滿足多樣化的服務(wù)質(zhì)量需求。目前，多用戶(hù)作業(yè)調(diào)度器主要有以下兩種設(shè)計(jì)方案:一是在一個(gè)物理集群上創(chuàng)建多個(gè)虛擬子集群，HOD (Hadoop On Demand) 調(diào)度器是其中的典型代表；二是通過(guò)擴(kuò)展傳統(tǒng)調(diào)度策略，使其支持多隊(duì)列多用戶(hù)，利用給不同隊(duì)列分配不同的資源量來(lái)滿足不同的用戶(hù)/應(yīng)用程序需求。雅虎的能力調(diào)度器 (Capacity Scheduler) 和Facebook 的公平調(diào)度器 (Fair Scheduler) 是其中的典型代表。

圖4 公平調(diào)度模型Fig.4 Fair scheduling model

3.2.1 HOD (Hadoop On Demand)

HOD 調(diào)度器[22]是一個(gè)用于管理共享物理集群上多個(gè)虛擬 Hadoop 子集群的工具。為了滿足不同類(lèi)型應(yīng)用程序的需求，用戶(hù)可以利用 HOD 調(diào)度器在共享物理集群上搭建多個(gè)獨(dú)立的虛擬 Hadoop 子集群。不同類(lèi)型的應(yīng)用程序分別在與之相對(duì)應(yīng)的集群上運(yùn)行，這將能夠較好地提高集群效率。

在具體工作過(guò)程中，HOD 使用開(kāi)源的資源管理器 Torque[28]來(lái)分配和回收節(jié)點(diǎn)，管理節(jié)點(diǎn)上的作業(yè)，如維護(hù)作業(yè)的運(yùn)行狀態(tài)、監(jiān)控作業(yè)運(yùn)行等。Torque 上需運(yùn)行一個(gè)調(diào)度守護(hù)進(jìn)程來(lái)完成相應(yīng)的調(diào)度，其默認(rèn)的調(diào)度策略是 FCFS。調(diào)度守護(hù)線程將所有作業(yè)按照到達(dá)先后順序依次存放到同一個(gè)隊(duì)列中，然后并依次進(jìn)行調(diào)度。除了 FCFS 外，Torque 還提供了其他多種可選的調(diào)度機(jī)制。

3.2.2 能力調(diào)度器

為了彌補(bǔ) HOD 的不足，雅虎開(kāi)發(fā)了 Capacity Scheduler (能力調(diào)度器) 多用戶(hù)調(diào)度器。它以隊(duì)列為單位劃分資源，并設(shè)定每個(gè)隊(duì)列的資源最低保證和使用上限，來(lái)防止作業(yè)被“餓死”或者某個(gè)隊(duì)列獨(dú)占資源。而當(dāng)一個(gè)隊(duì)列中沒(méi)有任務(wù)要執(zhí)行、有空閑資源時(shí)，則可暫時(shí)將其空閑的這部分資源共享給其他隊(duì)列。

Capacity Scheduler 通常使用“隊(duì)列→作業(yè)→任務(wù)”三級(jí)調(diào)度策略。具體的來(lái)說(shuō)，就是當(dāng)集群中出現(xiàn)空閑資源時(shí)，調(diào)度器首先為資源使用率最低一個(gè)隊(duì)列分配資源。其中，資源使用率為當(dāng)前已使用的資源量 (Resource Occupied) 與隊(duì)列資源容量 (Capacity) 的比值，即 ResourceOccupied/Capacity。其次，在隊(duì)列內(nèi)，根據(jù)諸如 FCFS、優(yōu)先級(jí)等特定策略進(jìn)行作業(yè)排序和調(diào)度。最后，在選擇任務(wù)時(shí)，調(diào)度器會(huì)依次遍歷當(dāng)前作業(yè)中的每個(gè)任務(wù)，選擇當(dāng)前的空閑資源能夠滿足的一個(gè)任務(wù)來(lái)運(yùn)行。

默認(rèn)情況下，Capacity Scheduler 并沒(méi)有考慮內(nèi)存密集型的任務(wù)，以上所述的三級(jí)調(diào)度過(guò)程是在固定的資源分配粒度和所有任務(wù)同質(zhì)的假設(shè)下進(jìn)行的。為了解決這一問(wèn)題，當(dāng)可用資源不足時(shí)，Capacity Scheduler 通過(guò)預(yù)留機(jī)制來(lái)實(shí)現(xiàn)為內(nèi)存密集型任務(wù)分配更多的內(nèi)存。同時(shí)，Capacity Scheduler 使用作業(yè)延遲調(diào)度策略來(lái)提高任務(wù)的數(shù)據(jù)本地性：當(dāng)在選中的作業(yè)中未找到滿足數(shù)據(jù)本地性任務(wù)時(shí)，調(diào)度器會(huì)跳過(guò)此次調(diào)度，直到找到滿足數(shù)據(jù)本地性條件的任務(wù)，或者跳過(guò)次數(shù)達(dá)到上限為止。

3.2.3 公平調(diào)度器

針對(duì) HOD 存在的不足，F(xiàn)acebook 提出了 Fair Scheduling (公平調(diào)度算法)[23]，其調(diào)度模型如圖 5 所示。公平調(diào)度器 (Fair Scheduler) 與 Capacity Scheduler類(lèi)似，按資源池 (與隊(duì)列的概念類(lèi)似) 來(lái)組織作業(yè)。但在分配時(shí)則是將資源公平地分到各個(gè)資源池中，盡可能保證每個(gè)用戶(hù)都獲得相等的資源份額。同時(shí)為了保證某些特定用戶(hù)、群組或者應(yīng)用程序總能獲得到足夠的資源，公平調(diào)度器還可以通過(guò)設(shè)置資源池最低共享資源量來(lái)提供相應(yīng)保證。當(dāng)作業(yè)需求的資源需求大于等于資源池的最低共享資源保證時(shí)，該資源池至少能獲得最低保證共享資源 (如圖 5 Pool 1)，但當(dāng)作業(yè)需求的資源需求小于資源池的最低共享資源保證、資源池有閑置資源時(shí)，閑置的資源將在其他資源池間進(jìn)行切分。

例如，圖 5 中的用戶(hù) X 和 Y 將共擁有 Pool 1 以外的資源 (40)。當(dāng) X 有任務(wù)啟動(dòng)，而 Y 沒(méi)有任務(wù)時(shí)，A 會(huì)獲得全部資源 (40)；當(dāng) Y 啟動(dòng)一個(gè)或多個(gè)任務(wù)時(shí)，X 的任務(wù)會(huì)繼續(xù)運(yùn)行，不過(guò)一定時(shí)間之后兩個(gè)用戶(hù) X 和 Y 將各自獲得一半的資源 (20)。而用戶(hù)資源池內(nèi)的任務(wù)間的資源劃分與 pool 內(nèi)的具體調(diào)度策略有關(guān)，如圖 5，pool 1 內(nèi)采用公平策略，job 1 和 job 2將分別獲得 30 的資源量；pool 2 內(nèi)采用的是 FCFS 策略，job 3 獲得 40 的資源量，而 job 4 和 job 5 只有當(dāng)job 3 完成后或者有未使用的資源量時(shí)才會(huì)依次獲得資源。

與能力調(diào)度器相似，公平調(diào)度器也采用“資源池→作業(yè)→任務(wù)”三級(jí)調(diào)度策略。資源池的選擇：當(dāng)存在資源使用量小于最低保證的資源池時(shí)，優(yōu)先選擇其中資源使用率 (即擁有資源量與資源池容量的比值) 最低的資源池；否則，堅(jiān)持最大化資源的公平共享的原則來(lái)選擇作業(yè)權(quán)重比最小的資源池，其中作業(yè)權(quán)重比jobWeight＝poolWeight/poolRunningJobNum。在選擇作業(yè)時(shí)，同樣是優(yōu)先將給資源池中任務(wù)權(quán)重比最小的作業(yè)分配資源。而任務(wù)的選擇策略則是考慮任務(wù)的數(shù)據(jù)本地性，以提高任務(wù)的運(yùn)行效率[23]。

公平調(diào)度器也是一個(gè)多用戶(hù)調(diào)度器，它允許多個(gè)用戶(hù)添加了多個(gè)層級(jí)的限制條件 (如資源池資源的限制和用戶(hù)作業(yè)數(shù)量的限制) 讓多用記更好地共享一個(gè)集群。同時(shí)它還采用延時(shí)調(diào)度機(jī)制[31]來(lái)提高數(shù)據(jù)的本地性：當(dāng)有空閑資源時(shí)，若選中的作業(yè)中沒(méi)有滿足數(shù)據(jù)本地化的任務(wù)，則暫時(shí)把資源讓給其他作業(yè)，直到找到滿足數(shù)據(jù)本地性條件的任務(wù)，或者達(dá)到設(shè)定的延遲限為止。公平調(diào)度器采用雙層延遲調(diào)度算法來(lái)實(shí)現(xiàn)延時(shí)調(diào)度：通過(guò)設(shè)置最長(zhǎng)等待時(shí)間 W1 和進(jìn)一步等待時(shí)間 W2 兩個(gè)時(shí)間閾值，來(lái)確定對(duì)一個(gè)作業(yè)中任務(wù)滿足數(shù)據(jù)本地化條件的最長(zhǎng)等待時(shí)間。

公平調(diào)度器還允許不同資源池之間的資源搶占。當(dāng)一個(gè)資源池有閑置資源時(shí)，閑置資源將暫時(shí)與其他資源池共享。當(dāng)有新的作業(yè)提交到該資源池時(shí)，調(diào)度器開(kāi)始則為其回收資源。若一定時(shí)間后該資源池仍未得到本屬于自己的資源，調(diào)度器就會(huì)通過(guò)殺死任務(wù)來(lái)強(qiáng)制進(jìn)行回收相應(yīng)的資源。公平調(diào)度器提供了最小資源量搶占和公平共享量搶占兩種資源搶占方法。最小資源量搶占指在一定時(shí)間內(nèi)資源池未得到最小資源量滿足，從其他資源池中進(jìn)行資源搶占；而公平共享量搶占則是在一定時(shí)間內(nèi)未達(dá)到公平共享量的一半時(shí)進(jìn)行資源搶占。執(zhí)行資源搶占時(shí)，調(diào)度器將在超額使用資源的資源池內(nèi)選擇殺掉啟動(dòng)最早的任務(wù)來(lái)釋放相應(yīng)資源。

表 1 能力調(diào)度器與公平調(diào)度器的比較Table 1 Comparison between capability scheduler and fair scheduler

圖5 Fattened Backf i lling 偽代碼Fig.5 Fake wde of Fattened Backf i lling

另外，公平調(diào)度器還為用戶(hù)提供一個(gè)可擴(kuò)展的負(fù)載均衡器，可將系統(tǒng)中所有任務(wù)按數(shù)量均分到每個(gè)節(jié)點(diǎn)上。表 1 列舉了能力調(diào)度器與公平調(diào)度器之間的主要異同點(diǎn)。

目前，針對(duì)多用戶(hù)共享集群的資源分配和任務(wù)調(diào)度，在能力調(diào)度算法和公平調(diào)度算法的基礎(chǔ)上衍生出了許多改進(jìn)的算法[24-29]。文獻(xiàn)[30-32]中提到的任務(wù)調(diào)度改進(jìn)算法，采用就近原則，將任務(wù)調(diào)度到所需數(shù)據(jù)所在或就近的節(jié)點(diǎn)上執(zhí)行。不同的用戶(hù)有不同的 QoS要求，針對(duì)用戶(hù)期望運(yùn)行時(shí)間服務(wù)要求，文獻(xiàn)[33]中提出的 AdaptiveScheduler，一種自適應(yīng)調(diào)度器。該調(diào)度器把作業(yè)會(huì)分解成多個(gè)任務(wù)，根據(jù)已完成任務(wù)的運(yùn)行時(shí)間估算剩余任務(wù)所需運(yùn)行時(shí)間，進(jìn)而依據(jù)作業(yè)進(jìn)度和剩余的規(guī)定時(shí)間動(dòng)態(tài)地為作業(yè)分配資源，盡可能在規(guī)定時(shí)間內(nèi)完成作業(yè)。文獻(xiàn)[34]中提到的 Learning Scheduler (自學(xué)習(xí)調(diào)度器) 是基于貝葉斯分類(lèi)算法的資源感知調(diào)度器。它能根據(jù)節(jié)點(diǎn)的資源使用情況和作業(yè)的資源利用率，利用模式分類(lèi)器將節(jié)點(diǎn)和作業(yè)分別分為“Good”和“Bad”兩類(lèi)。在此基礎(chǔ)上使資源和任務(wù)得到更好的匹配，進(jìn)而縮短作業(yè)的完成時(shí)間。另外，文獻(xiàn)[35]中的動(dòng)態(tài)優(yōu)先級(jí)調(diào)度策略 (DynamicPriority Scheduler) 則允許用戶(hù)動(dòng)態(tài)調(diào)整自己獲取的資源量，以滿足其對(duì)服務(wù)質(zhì)量的要求。

圖6 Conservative Backf i lling、EASY Backf i lling 和 Fattened Backf i lling 作業(yè)回填示意圖Fig.6 Schematic diagram of conservative Backf i lling, EASY Backf i lling and Fattened Backf i lly

3.3 Backf i lling 在提高資源利用率方面的運(yùn)用

Backfilling (回填算法) 是利用集群資源分配過(guò)程中出現(xiàn)的資源碎片，提高資源利用率的一種優(yōu)化策略。主要思路是在當(dāng)前作業(yè)被阻塞時(shí)，優(yōu)先調(diào)度執(zhí)行資源需求能滿足、且對(duì)其它作業(yè)的影響在規(guī)定范圍內(nèi)的作業(yè)，從而達(dá)到優(yōu)化集群整體性能的目的。Backfilling 調(diào)度策略有不同的實(shí)現(xiàn)方式，比較典型的有 Conservative Backfilling、EASY Backfilling 和Fattened backf i lling[36]，以下分別進(jìn)行介紹。

3.3.1 Conservative Backf i lling

Conservative Backfilling 算法即保守回填，回填算法最原始的版本。在該策略下，進(jìn)行作業(yè)回填時(shí)，要保證回填作業(yè)的不會(huì)延遲等待隊(duì)列中所有排在它前面的作業(yè)的執(zhí)行。該調(diào)度方式的優(yōu)點(diǎn)是：能夠估計(jì)隊(duì)列中作業(yè)開(kāi)始執(zhí)行的時(shí)間，從而給用戶(hù)一個(gè)作業(yè)執(zhí)行的保證。

3.3.2 EASY Backf i lling

較之 Conservative Backfilling，EASY Backfilling則采用比較“激進(jìn)”的方式進(jìn)行回填：只要不會(huì)延遲等待隊(duì)列中第一個(gè)作業(yè)的執(zhí)行[37]即可進(jìn)行回填，不用考慮隊(duì)列中排在它前面的其他作業(yè)。EASY Backfilling 的出發(fā)點(diǎn)在于盡可能提高系統(tǒng)的資源利用率，但由于該回填機(jī)制并未考慮對(duì)延遲隊(duì)列中第一個(gè)以外作業(yè)的影響，從而造成了無(wú)法對(duì)這些作業(yè)的延遲情況進(jìn)行預(yù)測(cè)。

另外，松弛回填算法[38-39]，基于概率的回填算法[40]，自適應(yīng)回填算法[41]等則是基于 EASY Backf i lling的變種。

3.3.3 Fattened Backf i lling

Fattened Backf i lling 回填的策略比 EASY Backf i lling還要“激進(jìn)”，它允許回填作業(yè)延遲阻塞隊(duì)列中的所有作業(yè)，只要第一個(gè)作業(yè)的延遲小于已完成作業(yè)的平均等待時(shí)間 (AWT)[36]即可。具體回填過(guò)程如下:

Fattened Backfilling 大多數(shù)情況下能夠在不影響系統(tǒng)減速比的前提下，提高用戶(hù)平均等待時(shí)間和作業(yè)完成時(shí)間等面向用戶(hù)的性能指標(biāo)。

圖 7 為基于 slot 的資源表示模型下，三種不同回填機(jī)制進(jìn)行作業(yè)進(jìn)行回填的方式。三種策略區(qū)別主要在于對(duì)阻塞隊(duì)列中作業(yè)的影響程度的不同。作業(yè) 1 為阻塞隊(duì)列中的第一個(gè)作業(yè)，圖 (a) 中作業(yè) 3 進(jìn)行了回填，沒(méi)有作業(yè)因此而延遲；圖 (b) 中作業(yè) 3、4 進(jìn)行了回填，根據(jù) EASY Backfilling 的回填規(guī)則，作業(yè) 4不能在 Running job 3 完成時(shí)間進(jìn)行回填是因?yàn)檫@樣會(huì)使作業(yè) 1 被延遲調(diào)度，而可以回填到作業(yè) 2 之前是因?yàn)樽鳂I(yè) 2 阻塞隊(duì)列中的第一個(gè)作業(yè)；圖 (c) 與圖(b) 的區(qū)別在于，作業(yè) 4 被調(diào)度到了 Running job 3 完成時(shí)開(kāi)始執(zhí)行，因?yàn)樽鳂I(yè) 4 對(duì)作業(yè) 1 產(chǎn)生延遲并沒(méi)超過(guò)已完成作業(yè)的平均等待時(shí)間 AWT，根據(jù) Fattened Backfilling 的回填規(guī)則作業(yè)可以進(jìn)行回填。從這圖中 7 個(gè)作業(yè)完成的時(shí)間上來(lái)看，F(xiàn)attened Bacdfilling的性能最優(yōu)，EASY backfilling 其次，Conservative backf i lling 提高的最少。

在回填算法中，調(diào)度器需要知道各個(gè)作業(yè)所需的資源量和其預(yù)計(jì)運(yùn)行的時(shí)間，作業(yè)所需的資源量不會(huì)在運(yùn)行過(guò)程中改變。

4 結(jié)論

本文介紹了共享集群的資源管理調(diào)度技術(shù)和框架、不同的回填策略在提高資源利用率方面的運(yùn)用。集群資源管理通常包括資源表示模型和資源分配模型兩個(gè)部分。資源的表示模型有基于 slot 的單維資源表示模型和基于真實(shí)資源需求的多維資源表示模型?；?slot 的資源管理方案方便系統(tǒng)的資源分配與調(diào)度的實(shí)現(xiàn)，但資源利用率不高；而基于真實(shí)資源需求的資源管理方案則能夠提升集群資源的利用率，但實(shí)現(xiàn)起來(lái)比較復(fù)雜。之后本文詳細(xì)闡述了三種不同的調(diào)度模型及對(duì)應(yīng)的開(kāi)源框架。最后還介紹了回填算法三種不同回填機(jī)制的回填原則，并簡(jiǎn)要對(duì)比了這三種機(jī)制對(duì)系統(tǒng)性能的影響。

資源利用率不高是集群普遍存在的問(wèn)題，資源管理和調(diào)度策略是提高集群資源利用率的關(guān)鍵切入點(diǎn)。接下來(lái)的研究工作主要集中在如何通過(guò)效地管理多種類(lèi)型資源和回填策略?xún)蓚€(gè)方面來(lái)提高集群的資源利用率，以進(jìn)一步提高系統(tǒng)的吞吐。