董春濤 李文婷 沈晴霓 吳中海

北京大學 北京 100086

引言

大數(shù)據(jù)技術目前已成為學術界和產(chǎn)業(yè)界的研究熱點。Google公司提出的GFS(Google File System)、MapReduce、BigTable[1-3]等技術成為了大數(shù)據(jù)技術發(fā)展的重要基礎，而Apache軟件基金會基于這些技術推出的開源項目Hadoop[4]成為大數(shù)據(jù)技術發(fā)展和應用的標志性成果，許多互聯(lián)網(wǎng)公司(如Yahoo、IBM、百度、Facebook等)的大數(shù)據(jù)平臺都是以Hadoop為主，它們或自建Hadoop集群、或使用Amazon Elastic MapReduce服務。

在Hadoop1.0版本中，MapReduce(也被稱為MRv1)分布式處理框架是Hadoop中的唯一計算框架，它不僅能夠用于離線處理大規(guī)模非結構化數(shù)據(jù)，而且能將很多繁瑣的細節(jié)隱藏，比如，自動并行化、負載均衡和災備管理等，極大地簡化了開發(fā)工作，同時，與傳統(tǒng)的大多數(shù)分布式處理框架相比，MapReduce的伸縮性優(yōu)勢明顯，因此，MRv1最初推出的幾年，有眾多的成功應用案例，并獲得業(yè)界的廣泛支持和肯定。但隨著分布式系統(tǒng)集群的規(guī)模和其工作負荷的增長，特別是支持其他實時計算框架的需求越來越多，包括內(nèi)存計算框架(Spark)、流式計算框架(Storm)、迭代式計算框架(iMapReduce)等新型計算框架的出現(xiàn)，MRv1計算框架的局限性日益突出，主要包括擴展性差、資源利用率低、存在單點故障、計算框架單一等問題[5]。為此，Hadoop 2.0提出一種新的資源管理系統(tǒng)YARN[6-7](也被稱為MRv2)，一個多種計算框架通用的資源調(diào)度體系，為不同的并行化計算提供資源分配服務。這樣，YARN支持的計算框架只要實現(xiàn)YARN定義的接口，便可以運行在YARN之上，從而很好地打造一個以YARN為核心的生態(tài)系統(tǒng)。由于YARN具有靈活且支持多計算框架的架構設計、主結點功能的分離、資源調(diào)度機制的改進、資源的隔離和Hadoop原生支持等諸多特性，它目前已經(jīng)成了新一代資源管理的典型代表，許多互聯(lián)網(wǎng)公司，如阿里的云梯集群[8]、騰訊的Gaia平臺[9]等就是基于YARN建立的大數(shù)據(jù)平臺。

Hadoop 2.0 YRAN架構的核心是資源管理器(Resource Manager，RM)，而資源管理器的核心是資源調(diào)度器(Resource Scheduler，RS)。本文以分析Hadoop YARN的基本架構和工作流程為基礎，重點研究Hadoop YARN中的資源調(diào)度器使用的模型和機制，及其自帶的容量調(diào)度器(Capacity Scheduler)[10]和公平調(diào)度器(Fair Scheduler)[11]，最后將探討下一代調(diào)度器--歐米伽調(diào)度器(Omega Scheduler)[12]的主要設計思想。

第1節(jié)分析YARN的基本架構和工作流程，第2節(jié)分析YARN資源調(diào)度器使用的模型，第3節(jié)分析YARN資源調(diào)度器的機制，第4節(jié)對YARN現(xiàn)有調(diào)度器和下一代調(diào)度器進行分析。

1 YARN基本架構

YARN基本設計思想是將原MapReduce架構中JobTracker的兩個主要功能，即資源管理和作業(yè)調(diào)度/監(jiān)控分成兩個獨立組件，全局的ResourceManager和與每個應用相關的ApplicationMaster。下面我們從基本組成結構和工作流程兩個方面分析YARN計算框架。

1.1 YARN基本組成結構

YARN的基本組成結構如圖1所示。YARN總體上仍然是一個Master/Slave結構，在整個YARN資源管理框架中，資源管理器(ResourceManager)為Master，節(jié)點管理器(NodeManager)為Slave，ResourceManager負責對各個NodeManager上的資源進行統(tǒng)一管理和調(diào)度。用戶提交應用程序時，需要提供一個跟蹤和管理這個程序的應用程序主控節(jié)點(ApplicationMaster)，由它向ResourceManager申請資源，并要求NodeManager按ApplicationMaster申請到的Container資源信息來啟動任務。

圖1 YARN的基本組成結構

通過上述描述可知，YARN主要由Resource Manager、NodeManager、ApplicationMaster和Container等四個組件構成。它們的基本組成和功能描述如表1所示。

表1 YARN的組件及其功能描述

ResourceManager的資源調(diào)度器是一個“純調(diào)度器”，它不再從事任何與具體應用程序相關的工作，比如不負責監(jiān)控或者跟蹤應用的執(zhí)行狀態(tài)，也不負責重新啟動運行失敗的任務，這些均交由ApplicationMaster完成。

1.2 YARN的工作流程

當用戶向YARN提交應用程序時，YARN分兩個階段運行該應用程序：第一個階段啟動ApplicationMaster；第二個階段由ApplicationMaster為應用程序申請資源，并監(jiān)控整個運行過程，直到完成。YARN的工作流程如圖2所示，主要分為以下幾個步驟。

1) 用戶向YARN提交應用程序，其中包括用戶程序、啟動ApplicationMaster命令等。

2) ResourceManager為該應用程序分配第一個Container，并與對應的NodeManager通信，要求它啟動應用程序的ApplicationMaster。

3) ApplicationMaster向ResourceManager注冊后，為各個任務申請資源，并監(jiān)控它們的運行狀態(tài)，直到運行結束。

4) ApplicationMaster采用輪詢的方式通過RPC協(xié)議向ResourceManager申請和領取資源。

5) ApplicationMaster申請到資源后，便與對應的NodeManager通信，要求它啟動任務。

6) NodeManager為任務設置好運行環(huán)境(環(huán)境變量、JAR包、二進制程序等)后，將任務啟動命令寫到腳本中，并通過運行該腳本啟動任務。

7) 各個任務通過某個RPC協(xié)議向ApplicationMaster匯報自己的狀態(tài)和進度，可以在任務失敗時重新啟動任務。

8) 應用程序運行完成后，ApplicationMaster向ResourceManager注銷并關閉自己。

圖2 YARN的工作流程

在整個工作流程中，YARN的資源調(diào)度器主要關注ApplicationMaster如何向ResourceManager申請和領取資源，這是YARN工作的核心。下面將重點分析YARN的資源調(diào)度器相關的模型、機制，以及其實現(xiàn)的兩種調(diào)度器和下一代調(diào)度器。

2 YARN資源調(diào)度器的模型

在MRv1和YARN中，資源調(diào)度器的實現(xiàn)原理基本一致，不同的是YARN采用了事件驅動的編程模型和獨特的資源表示模型。YARN的資源調(diào)度器更為復雜，這就要求用戶在研究YARN現(xiàn)有調(diào)度器的工作原理和編寫新的調(diào)度器之前，必須先理解其資源調(diào)度器采用的模型。下面分別介紹YARN調(diào)度器采用的兩種模型。

2.1 事件驅動模型

YARN的資源調(diào)度器采用事件驅動的編程模型。它實際上成為一個事件處理器，需要處理來自外部的6種類型的事件：NODE_REMOVED、NODE_ADDED、APPLICATION_ADDED、APPLICATION_REMOVED、CONTAINER_EXPIRED和NODE_UPDATE，如表2所示。其中，NODE_UPDATE是6個事件中最重要的，如果此時有Container得到釋放，則它會觸發(fā)資源調(diào)度器最核心的資源分配機制，觸發(fā)資源分配。

表2 資源調(diào)度器需要處理的事件

2.2 資源表示模型

YARN同MRv1一樣，采用動態(tài)資源分配機制。不同的是，YARN中資源的表示方式是容器(Container)，而不是槽位(Slot)。Container是YARN中資源的抽象，封裝了某個節(jié)點上一定量的資源。與資源量固定的Slot相比，Container資源量動態(tài)可變，更加靈活。Container主要包含優(yōu)先級、期望資源所在節(jié)點、資源量、Container數(shù)目和是否松弛本地性5類信息。

當前YARN支持內(nèi)存和CPU兩種類型資源的管理和分配。NodeManager啟動時會向ResourceManager注冊，注冊信息中包含該節(jié)點可分配的CPU和內(nèi)存總量。YARN在將來還會支持磁盤容量、網(wǎng)絡和磁盤I/O等資源。

YARN為了更加友好地為應用程序分配資源，定義了一些調(diào)度語義。當前YARN支持的調(diào)度語義包括：請求某個節(jié)點上的特定資源量、請求某個特定機架上的特定資源量、將某些節(jié)點加入或移出黑名單和請求將資源歸還給集群。隨著YARN的發(fā)展，YARN將支持更多的調(diào)度語義。

3 YARN資源調(diào)度器的機制

資源調(diào)度機制是YARN資源調(diào)度器的核心。YARN資源調(diào)度器采用的調(diào)度機制主要包括：雙層資源調(diào)度機制、層級隊列管理機制、資源保證和資源搶占機制。其中雙層資源調(diào)度機制是其核心，是YARN進行資源分配的總體架構；層級隊列管理機制是YARN對上層資源分配隊列的管理方式；資源保證和資源搶占機制是YARN保證任務資源需求的機制。下面分別介紹YARN資源調(diào)度器采用的三種機制。

3.1 雙層資源調(diào)度機制

YARN采用雙層資源調(diào)度機制，如圖3所示。第一層是資源管理系統(tǒng)將資源分配給應用程序；第二層是應用程序將收到的資源分配給內(nèi)部任務。資源調(diào)度器主要關注第一層的調(diào)度問題，第二層的調(diào)度策略則由用戶應用程序的ApplicationMaster決定。

圖3 YARN雙層資源調(diào)度機制

YARN的資源分配過程是異步的，采用了基于拉模式(pull-based)的通信模型。資源調(diào)度器將資源分配給一個應用程序后，不會立刻推送給對應的ApplicationMaster，而是暫時放到緩沖區(qū)，等待ApplicationMaster通過周期性的心跳來取。YARN的資源分配過程如圖4所示。

圖4 YARN的資源分配過程

NodeManager需要通過周期性的心跳向ResourceManager匯報節(jié)點信息。ResourceManager收到信息后，返回心跳應答，包括需釋放的Container列表等信息。同時，會觸發(fā)一個NODE_UPDATE事件，如果此時有Container得到釋放，則該事件會觸發(fā)資源分配。資源調(diào)度器收到事件后，按照一定的策略將該節(jié)點上的資源分配給應用程序，并將分配結果放到一個內(nèi)存數(shù)據(jù)結構中。

應用程序的ApplicationMaster需要向ResourceManager發(fā)送周期性心跳，以領取最新分配的Container。ResourceManager收到信息后，將分配的Container以心跳應答的形式返回給ApplicationMaster。ApplicationMaster收到新分配的Container列表后，將這些Container分配給內(nèi)部任務。

3.2 層級隊列管理機制

用戶和資源管理機制是任何資源調(diào)度器的基礎。在YARN中，用戶以層級隊列的形式組織。該隊列組織方式具有隊列可嵌套、最少容量和最大容量等特點。每個隊列被劃分了一定比例的資源。每個用戶可屬于一個或多個隊列，且只能向這些隊列提交應用程序。為防止隊列名稱沖突和便于識別隊列，YARN采用了自頂向下的路徑命名隊列。

通常而言，不同的調(diào)度器對資源管理的方式是不同的，第4節(jié)將具體分析容量調(diào)度器和公平調(diào)度器的層級隊列管理機制的具體工作原理。

3.3 資源保證與搶占機制

YARN作為一個資源分配系統(tǒng)，必須保證任務的資源需求。如果發(fā)生資源暫時無法滿足任務需求和資源被其他任務占用等情況，YARN必須有相應的機制來解決這些問題。YARN當前主要采用資源保證和資源搶占兩種機制來保證任務的資源需求。

過與行星輪進行嚙合實現(xiàn)底座的回轉運動[3]。回轉機構安裝在底座套筒中，在安裝過程中一定要保證底座與底座套筒的緊密配合，保證底座與地面的垂直，確保鉗體與管柱的垂直，如圖2所示。在底座設計過程中，需要考慮以下幾點因素：

分布式計算框架中，資源調(diào)度器主要有兩種資源保證機制：增量資源分配和一次性資源分配。1)當應用程序申請的資源暫時無法保證時，增量資源分配：優(yōu)先為它預留一個節(jié)點上的資源，直到累計釋放的資源滿足需求；2)一次性資源分配：暫時放棄當前資源直到一個節(jié)點剩余資源一次性滿足需求。兩種機制均有缺點，增量資源分配進行資源預留會導致資源浪費，降低資源利用率；而一次性資源分配會產(chǎn)生“餓死”現(xiàn)象，YARN采用了增量資源分配。

資源調(diào)度器為每個隊列設置一個最大和最小資源量。最大資源量是隊列資源量的上限，最小資源量是在資源緊缺時每個隊列需要保證的資源量，是資源搶占發(fā)生的原因。通常為提高資源利用率，調(diào)度器會將負載較輕的隊列的資源暫時分配給負載較重的隊列。當負載較輕的隊列收到新提交的應用程序時，調(diào)度器會將本屬于該隊列的資源分配給它，但需要等其他隊列釋放資源。為防止等待時間過長，調(diào)度器等待一段時間后若發(fā)現(xiàn)資源并未得到釋放，則進行資源搶占。

4 YARN的資源調(diào)度器與下一代調(diào)度器

Google把資源調(diào)度器分為三代[12]，第一代是獨立的集群調(diào)度，第二代是雙層調(diào)度(Mesos，YARN)，第三代是共享狀態(tài)調(diào)度(Omega)。YARN是雙層調(diào)度的代表，實現(xiàn)了FIFO、Capacity Scheduler和Fair Scheduler三種調(diào)度器。FIFO作為簡單的批處理調(diào)度器，不能滿足多樣化需求和充分利用資源，因此，YARN用Capacity Scheduler取代FIFO調(diào)度器作為默認調(diào)度器。Capacity Scheduler和Fair Scheduler屬于多用戶調(diào)度器，采用樹形多級隊列形式組織資源，更適合應用需求。下面分別介紹這兩種多用戶資源調(diào)度器及其存在的脆弱性和第三代資源調(diào)度器Omega。

4.1 容量調(diào)度器

容量調(diào)度器(Capacity Scheduler)是Yahoo開發(fā)的多用戶調(diào)度器，以隊列為單位劃分資源，每個隊列可設定資源最低保證和使用上限。當隊列的資源有剩余時，可暫時將剩余資源共享。Capacity Scheduler主要有以下特點：容量保證、靈活性、多重租賃、安全保證和動態(tài)更新配置文件等。下面具體分析Capacity Scheduler的工作原理。

應用程序提交后，ResourceManager會向Capacity Scheduler發(fā)送一個事件，Capacity Scheduler收到后，將為應用程序創(chuàng)建一個對象跟蹤和維護其運行時的信息，同時，將它提交到對應的葉子隊列中，隊列會對應用程序進行合法性檢查。通過檢查，應用程序才算提交成功。提交成功后，它的ApplicationMaster會為它申請資源，Capacity Scheduler收到資源申請后，暫時將這些請求存放到一個數(shù)據(jù)結構中，以等待為其分配合適的資源。

NodeManager發(fā)送的心跳信息有兩類需要Capacity Scheduler處理：一類是最新啟動的Container；另一類是運行完成的Container，Capacity Scheduler將回收它使用的資源進行再分配。Capacity Scheduler采用三級資源分配策略(即將雙層調(diào)度機制中的第一層分為選擇隊列與選擇應用程序兩級)，當一個節(jié)點上有空閑資源時，它會依次選擇隊列、應用程序和Container(請求)使用該資源，接下來介紹三級資源分配策略。

第一級：選擇隊列。Capacity Scheduler采用基于優(yōu)先級的深度優(yōu)先遍歷算法選擇隊列：從根隊列開始，按照資源使用率由小到大遍歷子隊列。如果子隊列是葉子隊列，則按照第二、三級的方法在隊列中選擇一個Container，否則以該隊列為根隊列，重復以上過程，直到找到合適的Container并退出。

第二級：選擇應用程序。選中一個葉子隊列后，Capacity Scheduler按照Application ID對葉子隊列中的應用程序進行排序，依次遍歷排序后的應用程序，找到合適的Container。

第三級：選擇Container。選中一個應用程序后，先滿足優(yōu)先級高的Container。同一優(yōu)先級，先滿足本地化的Container，依次選擇節(jié)點本地化、機架本地化和非本地化的Container。

4.2 公平調(diào)度器

公平調(diào)度器(Fair Scheduler)是Facebook開發(fā)的多用戶調(diào)度器，與Capacity Scheduler有很多相同之處。Fair Scheduler與Capacity Scheduler的不同主要體現(xiàn)在資源公平共享、負載均衡、調(diào)度策略配置靈活和提高小應用的響應時間等方面。

Fair Scheduler也需要進行程序的合法性檢查、處理心跳信息和資源分配等工作，同樣采用三級分配策略。不同的是，F(xiàn)air Scheduler提供了更多樣化的調(diào)度策略，調(diào)度策略在隊列間和隊列內(nèi)部可單獨設置。當前有三種策略可選，分別是先來先服務(FIFO)、公平調(diào)度(Fair)[12]和主資源公平調(diào)度(Dominant Resource Fairness，DRF)[13]。1)先來先服務：按優(yōu)先級高低調(diào)度，優(yōu)先級相同，則按提交時間先后順序調(diào)度；提交時間相同，則按名稱大小調(diào)度。2)公平調(diào)度：按內(nèi)存資源使用比率大小調(diào)度。3)主資源公平調(diào)度：按主資源公平調(diào)度算法進行調(diào)度，所需份額最大的資源稱為主資源，把最大最小公平算法應用于主資源上，將多維資源調(diào)度問題轉化為單資源調(diào)度問題。

DRF算法偽代碼：

隨著Hadoop版本的演化，F(xiàn)air Scheduler和Capacity Scheduler的功能越來越完善，兩者同質(zhì)化也越來越嚴重。兩者在應用場景、支持的特性、內(nèi)部實現(xiàn)等方面非常接近，而由于Fair Scheduler支持多種調(diào)度策略，可認為Fair Scheduler具備了Capacity Scheduler的所有功能。

4.3 資源調(diào)度器的脆弱性

資源調(diào)度器作為YARN的核心組件，其安全性與可用性對整個系統(tǒng)起到至關重要的作用，當前的資源調(diào)度器存在許多脆弱性問題需要解決。

目前，已經(jīng)發(fā)現(xiàn)有多租戶的YARN系統(tǒng)存在DoS攻擊的安全隱患[14]。這主要是由于YARN當前所實現(xiàn)的資源調(diào)度器最多只對內(nèi)存和CPU兩種資源進行限制，卻沒有對其他的計算資源(網(wǎng)絡帶寬、磁盤讀寫等)進行限制，惡意用戶可以通過使用受限制的合法資源在節(jié)點上啟動惡意計算任務，大量地占用沒有進行限制的資源，從而影響節(jié)點上其他計算任務的正常運行。如果惡意用戶可以用有限的受限制的資源啟動盡可能多的惡意計算任務，并將它們分配到盡可能多的節(jié)點上，那么就會影響整個系統(tǒng)的計算能力，甚至導致整個系統(tǒng)不可用。要解決這一脆弱性，資源調(diào)度器必須對其他的計算資源進行合理的限制。

除此之外，YARN的資源調(diào)度器還存在資源本地化考慮不夠全面、向ApplicationMaster告知Container的實際物理地址等許多脆弱性問題需要研究和解決。

4.4 第三代資源調(diào)度器

YARN作為第二代調(diào)度器的代表在日益完善但并非完美。調(diào)度機制還在快速發(fā)展中，為克服雙層調(diào)度機制的缺點，Google開發(fā)了下一代資源管理系統(tǒng)Omega。

Omega是一種基于共享狀態(tài)的調(diào)度器，沒有集中式調(diào)度模塊，應用程序的調(diào)度器進行自我管理和控制。Omega將雙層調(diào)度器中的集中式調(diào)度模塊簡化成持久化的共享數(shù)據(jù)(整個集群的實時資源使用信息)和針對這些數(shù)據(jù)的驗證代碼。

由于沒有集中式調(diào)度模塊，Omega不能像YARN一樣在一個統(tǒng)一模塊中對整個集群中的資源分組、限制每類應用程序的使用量和限制每個用戶的使用量等，這些功能由各個應用程序的調(diào)度器實現(xiàn)。Omega將優(yōu)先級這一限制放到共享數(shù)據(jù)的驗證代碼中，當有多個應用程序同時申請一份資源時，優(yōu)先級最高的那個應用程序將獲得該資源，其他資源限制全部下放到各個子調(diào)度器。

5 結束語

大數(shù)據(jù)時代，資源管理方式正在發(fā)生變革。在大數(shù)據(jù)的主流應用平臺Hadoop系統(tǒng)中，掌控好資源調(diào)度就抓住了整個Hadoop系統(tǒng)的核心。YARN作為一個獨立的資源管理系統(tǒng)是新一代Hadoop中最核心的組件，代表了大數(shù)據(jù)平臺的發(fā)展趨勢。資源系統(tǒng)是Hadoop YARN系統(tǒng)的研究重點，而資源調(diào)度機制是資源調(diào)度系統(tǒng)核心。分析和研究YARN的資源調(diào)度機制，不僅有助于部署平臺，更有助于明確資源調(diào)度系統(tǒng)存在的脆弱性與不足，不斷完善資源調(diào)度系統(tǒng)，為構建滿足不同實際應用需求的大數(shù)據(jù)平臺奠定基礎。

參考文獻

[1]Ghemawat S,Gobioff H,Leung S T.The Google file system[C]//The Nineteenth ACM Symposium on Operating Systems Principles,2003

[2]Jeffrey Dean,Sanjay Ghemawat.MapReduce:simplified data processing on large clusters[J].Communications of the ACM-50th anniversary issue:1958-2008,2008,1(51):107-113

[3]Fay Chang,Jeffrey Dean,Sanjay Ghemawat,et al.Bigtable:A Distributed Storage System for Structured Data[EB/OL].[2015-01-07].http://labs.google.com/papers/bigtable.html

[4]Apache hadoop[EB/OL].[2015-01-07].http://hadoop.apache.org.

[5]Apachetez[EB/OL].[2015-01-07].http://incubator.apache.org/projects/tez.html.

[6]Vinod Kumar Vavilapalli,Arun C Murthy,Chris Douglas,et al.Apache Hadoop YARN:Yet Another Resource Negotiator[C]//The Fourth ACM Symposium on Cloud Computing(SoCC'13),2013

[7]董西成.Hadoop技術內(nèi)幕:深入解析YARN架構設計與實現(xiàn)原理[M].北京:機械工業(yè)出版社,2013:153-184

[8]楊卓犖.基于YARN構建多功能分布式集群[J].程序員,2013,(11):105-107

[9]SACC2014:騰訊資源調(diào)度平臺Gaia分享[EB/OL].[2015-01-07].http://cloud.it168.com/a2014/0918/1667/000001667383.shtml

[10]Hadoop Capacity Scheduler[EB/OL].[2015-01-07].http://hadoop.apache.org/common/docs/r2.2.0/capacity_scheduler.html

[11]Hadoop Fair Scheduler[EB/OL].[2015-01-07].http://hadoop.apache.org/common/docs/r2.2.0/fair_scheduler.html

[12]Malte Schwarzkopfy,Andy Konwinskiz,Michael Abd-El-Malekx.Omega flexible,scalable schedulers for large compute clusters[C]//ACM SIGOPS European Conference on Computer Systems(EuroSys 2013)

[13]Ali Ghodsi,Matei Zaharia,Benjamin Hindman.Dominant Resource Fairness:Fair Allocation of Multiple Resource Types[R].Technical Report No.UCB/EECS-2011-18.March 6,2011

[14]Huang J W,Nicol D M,Campbell R H.Denial-of-Service Threat to Hadoop/YARN Clusters with Multi-Tenancy[C]//2014 IEEE International Congress on Big Data