集群資源管理及回填技術

林起勛，錢德沛，欒鐘治

北京航空航天大學，北京 100191

1 概述

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

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

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

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

2 集群資源組織模型

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

2.1 基于 slot 的資源組織方式

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

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

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

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

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

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

2.2 基于真實需求量的資源組織方式

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3.2 任務調(diào)度器

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

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

為了克服 FCFS 單隊列存在的不足之處，多種類型的多用戶多隊列調(diào)度器相繼出現(xiàn)。在這些調(diào)度策略下，管理員可以根據(jù)應用需求對用戶/應用程序進行分組，并為各自分配不同的資源量，同時還可利用約束條件來防止單個用戶/應用程序獨占資源，以盡可能地滿足多樣化的服務質(zhì)量需求。目前，多用戶作業(yè)調(diào)度器主要有以下兩種設計方案:一是在一個物理集群上創(chuàng)建多個虛擬子集群，HOD (Hadoop On Demand) 調(diào)度器是其中的典型代表；二是通過擴展傳統(tǒng)調(diào)度策略，使其支持多隊列多用戶，利用給不同隊列分配不同的資源量來滿足不同的用戶/應用程序需求。雅虎的能力調(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]是一個用于管理共享物理集群上多個虛擬 Hadoop 子集群的工具。為了滿足不同類型應用程序的需求，用戶可以利用 HOD 調(diào)度器在共享物理集群上搭建多個獨立的虛擬 Hadoop 子集群。不同類型的應用程序分別在與之相對應的集群上運行，這將能夠較好地提高集群效率。

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

3.2.2 能力調(diào)度器

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

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

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

3.2.3 公平調(diào)度器

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

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

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

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

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

表 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)度器還為用戶提供一個可擴展的負載均衡器，可將系統(tǒng)中所有任務按數(shù)量均分到每個節(jié)點上。表 1 列舉了能力調(diào)度器與公平調(diào)度器之間的主要異同點。

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

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

3.3.1 Conservative Backf i lling

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

3.3.2 EASY Backf i lling

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

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

3.3.3 Fattened Backf i lling

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

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

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

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

4 結論

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

資源利用率不高是集群普遍存在的問題，資源管理和調(diào)度策略是提高集群資源利用率的關鍵切入點。接下來的研究工作主要集中在如何通過效地管理多種類型資源和回填策略兩個方面來提高集群的資源利用率，以進一步提高系統(tǒng)的吞吐。