大規(guī)模短時間任務(wù)的低延遲集群調(diào)度框架

趙 全，湯小春，朱紫鈺，毛安琪，李戰(zhàn)懷

（西北工業(yè)大學(xué)計算機學(xué)院，西安 710129）

0 引言

近年來，數(shù)據(jù)中心上的數(shù)據(jù)分析作業(yè)常常是一些運行時間短的流處理作業(yè)，而且要求這些作業(yè)共享一套集群資源以便減少基礎(chǔ)設(shè)施的成本，例如，既存在一些結(jié)構(gòu)化的數(shù)據(jù)查詢作業(yè)，也存在一些實時數(shù)據(jù)監(jiān)控以及數(shù)據(jù)分析作業(yè)［1-5］。面對這些規(guī)模龐大并且延遲要求較低的流處理作業(yè)，一些流處理計算框架，如Flink［1］、Dremel［6］、Spark［7］等開始被大型互聯(lián)網(wǎng)企業(yè)使用。這類作業(yè)運行時，任務(wù)往往被分散到上千臺機器上運行，任務(wù)要么從磁盤獲得數(shù)據(jù)進行計算，要么使用存儲在內(nèi)存的數(shù)據(jù)進行計算，作業(yè)的響應(yīng)時間常常在秒級。例如，使用Spark計算一個數(shù)據(jù)大小為1 GB的查詢作業(yè)，運行時間僅僅1 s左右。當(dāng)這樣的作業(yè)大量出現(xiàn)在一個數(shù)據(jù)中心并共享集群計算資源時，作業(yè)之間往往會出現(xiàn)相互的干涉或者對計算資源的競爭，導(dǎo)致部分作業(yè)被延遲執(zhí)行或者出現(xiàn)執(zhí)行失敗的情況［7］。本文希望建立一套新的集群資源調(diào)度框架，提供一種高效、共享的資源調(diào)度環(huán)境，提高整個集群的資源使用率，為各種大規(guī)模并行作業(yè)及時分配計算資源，保證每個作業(yè)能夠快速得到響應(yīng)。

由短時間（毫秒級）任務(wù)組成的作業(yè)，其作業(yè)的調(diào)度過程具有較大的挑戰(zhàn)。在這些作業(yè)中，不但包括一些低延遲的流處理任務(wù)，也包括一些為了得到資源的公平分配和減少長時間滯留的任務(wù)，將長時間運行的批處理作業(yè)分解成大量的短時間運行的任務(wù)。例如，一些大規(guī)模的數(shù)據(jù)處理中，一個作業(yè)的執(zhí)行流程通常被分解成一個有向無環(huán)圖（Directed Acyclic Graph，DAG）（https：//tez.apache.org/）［8-10］，DAG中的一個頂點代表一個獨立運行的操作，邊代表數(shù)據(jù)流向。在執(zhí)行中，通過對數(shù)據(jù)進行分片，將操作和數(shù)據(jù)結(jié)合來形成一個一個可以獨立運行的計算任務(wù)。因此，大數(shù)據(jù)處理作業(yè)就變成了大量的短時間運行的并行任務(wù)。當(dāng)作業(yè)中的每個任務(wù)的運行時間在幾百毫秒內(nèi)，為了滿足低延遲的要求，集群資源調(diào)度的決策能力必須具有較大的吞吐量和較低的延遲。例如，假如一個集群系統(tǒng)通常包含上萬臺機器，每臺機器如果包含16核處理器的話，那么每一秒鐘調(diào)度100 ms的任務(wù)數(shù)量就可能達(dá)到百萬次的級別。另外，調(diào)度過程的延遲一定要低，對于一個100 ms的任務(wù)，如果調(diào)度延遲以及任務(wù)的等待時間超過執(zhí)行時間的1/10，即數(shù)十毫秒，這些都是用戶所不能忍受的情況。最后，在客戶對于實際系統(tǒng)的使用中，面對大量的短時間交互任務(wù)，應(yīng)用程序?qū)τ诩合到y(tǒng)的可擴展性以及可靠性也是重點關(guān)注的問題。這些挑戰(zhàn)導(dǎo)致現(xiàn)有的批處理集群資源管理系統(tǒng)不再能夠滿足用戶的需求，而一些專用的流處理計算框架雖然滿足實時性要求，卻無法滿足集群計算資源在不同作業(yè)之間的共享。

針對大規(guī)模且高度并行的秒級計算任務(wù)，改進現(xiàn)有的集群資源調(diào)度框架，實現(xiàn)不同作業(yè)對集群資源的共享，滿足其低延遲和高吞吐量調(diào)度要求，存在一定的挑戰(zhàn)。現(xiàn)有的集群調(diào)度框架，如Mesos［11］、Yarn［12］、Slurm［13］、Mercury［14］、Omega［15］、Sparrow［16］、低延遲框架［17］、Quincy［18］等，都無法滿足大規(guī)模秒級任務(wù)的調(diào)度。對于這種種類繁多且任務(wù)并行度較大的計算作業(yè)，如果只使用單個調(diào)度器實例來分散任務(wù)的執(zhí)行，這將是一件非常困難的事情。另外，為了滿足高可擴展性以及高可靠性，大規(guī)模任務(wù)的復(fù)制和恢復(fù)也要求在秒級內(nèi)完成，這也使得單個調(diào)度實例成為系統(tǒng)的瓶頸。

本文考慮了現(xiàn)有集群資源管理系統(tǒng)的特點，在調(diào)度框架方面，取消了集中調(diào)度器或者邏輯全局資源狀態(tài)，讓每個計算節(jié)點具有自主資源管理和控制能力，實現(xiàn)調(diào)度器的多個實例，將調(diào)度器實例部署在不同的計算節(jié)點上。這種調(diào)度器實例分散的方式以及計算節(jié)點的自治特性，使得可擴展性以及可靠性得到大大的提高。當(dāng)系統(tǒng)中在某個時間段出現(xiàn)大量的作業(yè)時，可以通過增加調(diào)度器實例來滿足高峰時段任務(wù)的調(diào)度需求；當(dāng)某個調(diào)度器實例故障，可以快速啟動新的調(diào)度器實例來替代故障調(diào)度器實例，滿足用戶作業(yè)的調(diào)度要求。這種分散的多調(diào)度實例帶來了低延遲的好處的同時，也帶來了一些矛盾。與集中式的單個調(diào)度器比較，多個分散的調(diào)度器實例可能導(dǎo)致資源分配的矛盾［15-16，19-21］，即不同的調(diào)度器實例將各自的任務(wù)分配到同一個CPU核上，造成多個任務(wù)對同一個資源進行競爭，導(dǎo)致任務(wù)的阻塞，從而延遲了任務(wù)的完成。

本文設(shè)計和實現(xiàn)了一個分布式集群資源調(diào)度框架DHRM（Distributed Heterogeneous Resource Management），它是一種無全局資源狀態(tài)、支持兩階段任務(wù)調(diào)度策略的集群資源調(diào)度框架。所謂兩階段任務(wù)調(diào)度，是指一個任務(wù)在調(diào)度過程中：首先由調(diào)度器向各個計算節(jié)點發(fā)送一個保持狀態(tài)的請求，一旦請求到達(dá)計算節(jié)點上的資源管理器，計算節(jié)點就發(fā)送自身的負(fù)載狀態(tài)信息到調(diào)度器；然后調(diào)度器進行決策后，向被選中的計算節(jié)點發(fā)送釋放消息，啟動任務(wù)在計算節(jié)點的執(zhí)行，對于沒有被選中的計算節(jié)點，發(fā)送取消消息，從這些計算節(jié)點刪除保留狀態(tài)的任務(wù)。DHRM提供了以下三種主要的策略來實現(xiàn)不同類型作業(yè)對于集群計算資源的共享：

1）兩階段多路調(diào)度策略。對于并行的作業(yè)，直接使用兩階段任務(wù)調(diào)度可能會導(dǎo)致作業(yè)完成時間的延長。作業(yè)的完成時間與作業(yè)中最后一個任務(wù)結(jié)束時間直接相關(guān)，如果一個作業(yè)的最后一個任務(wù)長時間得不到執(zhí)行，那么作業(yè)的完成時間就延長，必須等待最后一個任務(wù)完成，整個作業(yè)才能認(rèn)為結(jié)束。而最后一個任務(wù)的長時間等待使得兩階段調(diào)度策略的效果不能滿足預(yù)期要求。兩階段多路調(diào)度可以同時為每個任務(wù)提供多個隨機選擇選項，使得作業(yè)中的每個任務(wù)可以同時選擇較好的資源來解決此問題。不像兩階段調(diào)度每次僅僅為作業(yè)中的一個任務(wù)提供候選資源，兩階段多路調(diào)度為一個作業(yè)中的n個任務(wù)同時至少提供d·n個計算節(jié)點（d>1）。經(jīng)過論證分析，不像兩階段調(diào)度策略，當(dāng)作業(yè)的并行度增加時，兩階段多路調(diào)度策略的調(diào)度延遲并不會增加。

2）執(zhí)行隊列策略。對于集群節(jié)點上的CPU資源，可以劃分為多個執(zhí)行隊列，每個隊列包含一定的CPU資源、內(nèi)存資源、帶寬資源等。當(dāng)集群計算節(jié)點上只存在CPU資源，如果采用傳統(tǒng)的調(diào)度算法，可能導(dǎo)致隊列頭的一個長時間運行的任務(wù)阻塞其他短時間運行的任務(wù)，造成短時間運行的任務(wù)延遲增大。一些調(diào)度方案采用強力搜索策略，遍歷每個可用資源和每個任務(wù)來匹配資源，缺點是調(diào)度的復(fù)雜度上升，調(diào)度開銷增大。通過設(shè)置多個執(zhí)行隊列，可以保證CPU資源有空閑時，短時間運行的任務(wù)的快速調(diào)度。通過論證，這種方式并不會增加調(diào)度的開銷，不同種類任務(wù)混合時，調(diào)度延遲也并沒有明顯的增加。

3）資源協(xié)調(diào)策略。兩階段多路調(diào)度方法存在兩個性能瓶頸：第一，計算節(jié)點上的可以同時運行的任務(wù)數(shù)量不能很好地表示新到達(dá)的任務(wù)需要等待的時間；第二，由于資源狀態(tài)的變化以及網(wǎng)絡(luò)通信的延遲，多個并行的調(diào)度器實例可能會遇到資源競爭的情況。通過資源協(xié)調(diào)策略，某些等待時間過長的任務(wù)可能會被分散到其他等待時間較短的計算節(jié)點的隊列上。通過資源協(xié)調(diào)來解決資源分配沖突，實現(xiàn)計算資源的負(fù)載平衡。相比較單純的兩階段多路調(diào)度來說，可以大幅度減少作業(yè)的平均完成時間。

共享集群資源時，需要對每用戶資源使用量進行限制。DHRM通過計算節(jié)點上的多個隊列，來保證全局計算資源的分配目標(biāo)，為不同的用戶設(shè)置不同的資源使用量限制。通過資源使用限制，來確保各個作業(yè)能夠共享集群計算資源，不會導(dǎo)致某些用戶由于缺乏資源而放棄對資源的共享使用。

本文將DHRM部署在包含16臺服務(wù)器的集群上。通過對事務(wù)處理性能委員會（Transaction Processing performance Council，TPC）給出的基準(zhǔn)測試程序以及大規(guī)模的模擬作業(yè)進行調(diào)度，與理想狀態(tài)對比，DHRM的響應(yīng)時間在10%以內(nèi)，任務(wù)在隊列中的等待延遲平均在12 ms以內(nèi)。對于大規(guī)模的集群，DHRM可為任務(wù)較短的任務(wù)提供較短的響應(yīng)時間。通過設(shè)計調(diào)度模擬器，仿真結(jié)果表明，隨著集群規(guī)模增加到成千上萬CPU內(nèi)核，DHRM將繼續(xù)表現(xiàn)良好。實驗結(jié)果表明，DHRM分布式調(diào)度是集中調(diào)度的一種可行的替代方案，可以實現(xiàn)大規(guī)模并行任務(wù)的低延遲調(diào)度。

1 相關(guān)工作

對于集群資源管理系統(tǒng)，存在大量的文獻研究集中式調(diào)度框架，也存在一些系統(tǒng)使用分布式調(diào)度框架和混合式調(diào)度框架。例如Mesos及Yarn等系統(tǒng)，它們是集中式調(diào)度框架，無法滿足大規(guī)模并發(fā)短時間任務(wù)的低延遲調(diào)度。DHRM是一個分布式集群資源調(diào)度框架，能夠滿足大規(guī)模并發(fā)的短時間任務(wù)的低延遲調(diào)度要求。

Sparrow的研究目的是減少任務(wù)的尾部延遲，它建議使用對沖請求，其中客戶端將每個請求發(fā)送給兩個服務(wù)器，并在收到第一個結(jié)果時取消剩余的未完成請求。它還描述了綁定請求，客戶端將每個請求發(fā)送到兩個不同的服務(wù)器，但是服務(wù)器直接就請求狀態(tài)進行通信。當(dāng)一臺服務(wù)器開始執(zhí)行請求時，它將取消另一臺服務(wù)器。但是它無法估計不同的計算節(jié)點的負(fù)載狀態(tài)，也無法滿足集群計算節(jié)點上的負(fù)載平衡，造成資源饑餓，即一部分節(jié)點負(fù)載較重而另外一部分計算節(jié)點沒有計算任務(wù)的運行。

針對分布式系統(tǒng)中的負(fù)載共享機制，Sparrow使用隨機技術(shù)，DHRM采用仲裁。在負(fù)載共享系統(tǒng)中，對于每個任務(wù)的產(chǎn)生和任務(wù)的處理，缺省情況下，計算任務(wù)在產(chǎn)生的地方處理。當(dāng)某個處理器上的負(fù)載超過其閾值限制，負(fù)載需要分散到其他處理器。分散過程要么采用接收者方式，即輕量級的計算節(jié)點隨機選擇一些處理任務(wù)，請求任務(wù)的轉(zhuǎn)送；要么采用發(fā)送者方式，重量級的計算節(jié)點隨機選擇一些計算節(jié)點，向這些計算節(jié)點發(fā)送請求，其完成的過程通過隨機采樣的方式實現(xiàn)。DHRM采用協(xié)調(diào)仲裁方式，輕量級的計算節(jié)點向協(xié)調(diào)器發(fā)送資源邀約，重量級的計算節(jié)點發(fā)送任務(wù)轉(zhuǎn)送請求，協(xié)調(diào)器匹配后通知雙方仲裁結(jié)果。

Quincy的目標(biāo)是計算機集群上的任務(wù)調(diào)度，類似于Sparrow。Quincy將調(diào)度問題變成圖的最大流最小代價優(yōu)化，目標(biāo)是在集群資源在作業(yè)之間的公平共享、數(shù)據(jù)本地化。Quincy的圖調(diào)度支持更高等級的調(diào)度，但是，對于一個2 500臺機器的集群，它至少需要1 s的時間來計算任務(wù)的調(diào)度分配結(jié)果，因此，大規(guī)模集群環(huán)境下，Quincy無法滿足低延遲的調(diào)度要求。

其他許多調(diào)度框架旨在以粗粒度分配資源［22-23］，這是因為任務(wù)往往需要長時間的運行，或者因為集群支持許多應(yīng)用程序，每個應(yīng)用程序都獲取一定數(shù)量的資源并執(zhí)行自己的任務(wù)級調(diào)度，例如Mesos、Yarn、Omega等。這些調(diào)度為了實現(xiàn)復(fù)雜資源公平調(diào)度策略而犧牲了請求的粒度。作為結(jié)果，它們存在反饋延遲［24］，在調(diào)度秒級任務(wù)時無法提供低延遲和高吞吐量。對于高性能計算環(huán)境下的調(diào)度，它們針對具有復(fù)雜約束的大型作業(yè)進行了優(yōu)化，其調(diào)度目標(biāo)是最大吞吐量，它以每秒能夠?qū)崿F(xiàn)數(shù)十到數(shù)百個作業(yè)為調(diào)度目標(biāo)，例如，Slurm。類似的系統(tǒng)還包括Condor［25］，它支持一些復(fù)雜特征的作業(yè)流調(diào)度，使用豐富的約束語言、作業(yè)的檢查點以及群調(diào)度等，其匹配算法能夠達(dá)到的最大調(diào)度量是每秒數(shù)十到數(shù)百個作業(yè)。

2 設(shè)計目標(biāo)

本文的設(shè)計目標(biāo)是為短時間任務(wù)提供低延遲調(diào)度框架，支持大規(guī)模并行任務(wù)的運行，滿足不同作業(yè)對集群計算資源的共享。

1）資源調(diào)度的低延遲。相對于批處理工作負(fù)載，低延遲的工作負(fù)載通常具有更復(fù)雜的技術(shù)要求。因為批處理負(fù)載會長時間使用資源，所以調(diào)度的頻率不高。而低延遲的負(fù)載，其任務(wù)的執(zhí)行時間非常短，而且數(shù)量大，為了支持毫秒級別的任務(wù)調(diào)度，那么調(diào)度器就必須具有更快的調(diào)度頻率，支持每秒鐘百萬級別的任務(wù)調(diào)度規(guī)模。此外，調(diào)度框架向應(yīng)用程序提供低延遲服務(wù)后，調(diào)度程序就必須承受任務(wù)的失效恢復(fù)。

2）資源的細(xì)粒度共享。支持多個不同的作業(yè)對集群計算資源的共享，但是相對于粗粒度的資源共享方式，細(xì)粒度資源共享允許不同作業(yè)的多個任務(wù)并發(fā)共享資源。DHRM提供細(xì)粒度的資源共享，允許多個任務(wù)對同一資源的并發(fā)訪問，它是對現(xiàn)有的粗粒度集群資源管理的一種補充。

3）降低調(diào)度反饋延遲?，F(xiàn)有的批處理資源調(diào)度框架中，任務(wù)完成后，釋放資源，下一個任務(wù)才有可能獲得該資源，這樣會出現(xiàn)調(diào)度的反饋延遲，降低了資源的使用率。DHRM通過計算節(jié)點資源的細(xì)粒度共享，減少反饋延遲。

4）DHRM支持可擴展性和高可用性。通過可擴展性［26］，提供更多的計算資源，降低任務(wù)的執(zhí)行延遲；當(dāng)存在大量的應(yīng)用程序的低延遲流處理請求并超過可使用的資源總量時，DHRM提供嚴(yán)格的優(yōu)先級別和帶權(quán)重的資源共享。DHRM還提供每作業(yè)的資源使用約束，來保證各個不同的作業(yè)都能及時獲得資源。當(dāng)某個執(zhí)行器發(fā)生故障時，可以通過快速啟動新的執(zhí)行器的方式來保證任務(wù)的失效恢復(fù)功能。

3 并行作業(yè)的兩階段調(diào)度

3.1 一些基本的概念

1）計算節(jié)點。集群中的一個機器，其主要任務(wù)是運行各種計算任務(wù)。一個集群中包含大量的計算節(jié)點。如果一個計算節(jié)點上安排了大量的任務(wù)，超過其可以并行執(zhí)行的最大值，那么一些任務(wù)就會在計算節(jié)點的隊列上排隊。

2）作業(yè)。一個作業(yè)中包含n個任務(wù)，每個任務(wù)都會被安排到計算節(jié)點上。

3）調(diào)度器實例。一個進程，運行在某個計算節(jié)點上，負(fù)責(zé)將作業(yè)的任務(wù)映射到某個計算節(jié)點上。在該分布式資源調(diào)度框架中，調(diào)度器實例是有多個的，其數(shù)量最多不超過集群中機器的數(shù)量，作業(yè)可以被任何一個調(diào)度實例處理。在某一時刻下，可能會有多個包含不同數(shù)量任務(wù)的作業(yè)向該分布式資源調(diào)度框架請求注冊。若是集中式調(diào)度器，則只有一個調(diào)度實例來處理大量作業(yè)的注冊請求并進行資源的調(diào)度，這樣會導(dǎo)致集中式調(diào)度器的調(diào)度壓力過大。但在該分布式調(diào)度框架中，有多個分布式調(diào)度器實例供作業(yè)選擇，作業(yè)可平均分配到各個調(diào)度器上進行注冊，或者尋找較為“閑”的調(diào)度器實例進行注冊。通過多個分布式調(diào)度實例可以并行地對大量作業(yè)進行調(diào)度，這大大降低了作業(yè)的調(diào)度延遲。但是多個分布式調(diào)度器實例對資源進行調(diào)度管理，有可能會出現(xiàn)多個調(diào)度器實例將同一塊資源分給不同作業(yè)的任務(wù)的情況，造成較多的任務(wù)爭搶相同的資源的情況，從而延長了作業(yè)的整體執(zhí)行時間。該分布式調(diào)度框架采用兩階段的多路調(diào)度策略對不同作業(yè)的任務(wù)進行調(diào)度，關(guān)于兩階段的多路調(diào)度的詳細(xì)內(nèi)容將在后續(xù)的章節(jié)詳細(xì)介紹。

4）作業(yè)響應(yīng)時間。當(dāng)一個作業(yè)的任務(wù)提交到調(diào)度器后，在其得到資源之前，這個時間被稱為調(diào)度時間；任務(wù)獲得資源后，在計算節(jié)點的隊列上排隊，當(dāng)計算節(jié)點的并發(fā)執(zhí)行數(shù)低于最大值時，任務(wù)實際開始執(zhí)行，這段時間稱為等待時間；當(dāng)任務(wù)實際開始執(zhí)行到任務(wù)結(jié)束期間，被稱為執(zhí)行時間。作業(yè)被提交到調(diào)度器，一直到最后一個任務(wù)完成，這個期間稱為作業(yè)響應(yīng)時間。一個作業(yè)的延遲時間包括調(diào)度時間和等待時間的累計。如果采用零等待時間（相當(dāng)于該作業(yè)中所有任務(wù)的最長執(zhí)行時間）來調(diào)度作業(yè)的所有任務(wù)，可以得到一個理想作業(yè)響應(yīng)時間。使用給定調(diào)度技術(shù)來調(diào)度作業(yè)的所有任務(wù)，可以得到一個具體的響應(yīng)時間。理想作業(yè)響應(yīng)時間和指定調(diào)度下的作業(yè)響應(yīng)時間的差值叫延遲。

3.2 計算節(jié)點上的隊列

對于分布式調(diào)度框架來說，各個計算節(jié)點上需要有隊列。分布式調(diào)度器將任務(wù)提交到計算節(jié)點的隊列后，任務(wù)在隊列中處于等待狀態(tài)。當(dāng)計算節(jié)點上正在運行的任務(wù)數(shù)量低于設(shè)置的運行數(shù)量限制或者說存在可用計算資源的話，隊列中等待狀態(tài)的任務(wù)就被調(diào)度執(zhí)行。最簡單的調(diào)度方式是先進先出（First Input First Output，F(xiàn)IFO），也可以實施優(yōu)先級別調(diào)度、短任務(wù)優(yōu)先等策略。

對于CPU有關(guān)的資源分配，操作系統(tǒng)本身就支持按照時間片共享調(diào)度、或者按照優(yōu)先級別搶占式調(diào)度等；因此，在各個計算節(jié)點上，DHRM允許用戶建立自己的隊列，隊列設(shè)置不同的優(yōu)先級別。每個隊列上用戶可以設(shè)置自己的資源限制屬性。

執(zhí)行隊列為CPU任務(wù)的專用隊列。執(zhí)行隊列具有三類屬性：

1）資源量。CPU資源數(shù)量包括CPU核數(shù)、內(nèi)存數(shù)量、IO帶寬以及網(wǎng)絡(luò)帶寬值。該限制值用來與要提交到隊列的任務(wù)的資源使用量限制作比較。要提交到隊列的任務(wù)中所設(shè)置的資源限制值若超過該值，任務(wù)的提交將被拒絕。

2）隊列優(yōu)先級。表示隊列間的優(yōu)先級。其決定調(diào)度最先運行哪個隊列中的任務(wù)。該值較大的隊列中的任務(wù)將被優(yōu)先運行。若隊列間的優(yōu)先級相同，則按照請求被提交到隊列的時間順序運行請求。

3）同時可運行的任務(wù)數(shù)。隊列內(nèi)同時可運行的任務(wù)數(shù)。當(dāng)前正在運行的任務(wù)數(shù)若達(dá)到該數(shù)值，下一個應(yīng)該運行的任務(wù)將一直處于等待狀態(tài)，直到當(dāng)前正在運行的某個任務(wù)運行結(jié)束后該任務(wù)才會被啟動。

3.3 任務(wù)的兩階段調(diào)度

DHRM的候選資源選擇策略是借鑒文獻［16］的sparrow方法，即兩種隨機選擇策略來實現(xiàn)獲得候選的計算節(jié)點，該策略使用無狀態(tài)隨機方法提供了較低的預(yù)期任務(wù)等待時間。但是，DHRM對兩種隨機選擇策略進行了改進：不同于sparrow的依據(jù)隊列長度來決策計算節(jié)點方式，DHRM會將任務(wù)放置在兩個隨機選擇的工作計算機中負(fù)載最小的一個上。與使用隨機選擇相比，以這種方式調(diào)度任務(wù)可顯著縮短預(yù)期的等待時間。

3.3.1 調(diào)度過程

本文將兩種隨機選擇策略直接應(yīng)用于并行作業(yè)調(diào)度，其整個過程分為兩個階段：第一階段，調(diào)度程序為作業(yè)中的每個任務(wù)隨機選擇兩個計算節(jié)點的隊列，并向每個計算節(jié)點的隊列發(fā)送一個任務(wù)請求，任務(wù)請求中僅包含用戶的任務(wù)資源描述。每個計算節(jié)點上的隊列都會用當(dāng)前隊列狀態(tài)回復(fù)調(diào)度程序。第二階段，調(diào)度程序收到全部的返回的消息后，根據(jù)隊列的狀態(tài)信息，選擇一個負(fù)載最輕的計算節(jié)點的隊列，即等待時間最短的隊列，將任務(wù)放在該隊列上。調(diào)度程序重復(fù)此過程，直到作業(yè)中的所有任務(wù)全部獲得計算資源。

其實現(xiàn)過程如圖1所示。調(diào)度器為任務(wù)1選擇兩個計算節(jié)點的隊列，然后發(fā)送hold（保留）消息（圖1中1a：hold及1b：hold）。根據(jù)返回消息，選擇其中一個最優(yōu)隊列（圖1中的第二個隊列），然后調(diào)度器向選中的計算節(jié)點發(fā)送run（運行）消息（圖1中1b：run），使得任務(wù)在計算節(jié)點上變成等待狀態(tài)，對于另外一個計算節(jié)點的隊列，則發(fā)送del（刪除）消息（圖1中1a：del），取消任務(wù)的保留。一旦任務(wù)1調(diào)度完成，調(diào)度器開始任務(wù)2的調(diào)度，任務(wù)2的調(diào)度過程與任務(wù)1相同。該過程被稱為兩階段調(diào)度。

圖1 任務(wù)的兩階段調(diào)度過程Fig.1 Processof two-stage scheduling for tasks

3.3.2 隊列狀態(tài)的表示

在圖1所示的第一個階段中，計算節(jié)點的隊列向調(diào)度器返回隊列的狀態(tài)。最簡單的方式是返回隊列中執(zhí)行任務(wù)的數(shù)量和處于等待中的任務(wù)的數(shù)量，調(diào)度器根據(jù)隊列的長度選擇一個最短的隊列作為任務(wù)提交的目標(biāo)隊列。但是，在高負(fù)載集群環(huán)境下，這種方式的調(diào)度性能是比較差的。主要原因是因為隊列長度只能提供一種粗粒度的等待時間標(biāo)準(zhǔn)。例如，假如在兩個不同的計算節(jié)點上存在兩個隊列：第一個計算節(jié)點的隊列上存在兩個任務(wù)，執(zhí)行時間之和為200 ms；而第二個計算節(jié)點的隊列上只有一個任務(wù)，執(zhí)行時間為300 ms。如果任務(wù)按照隊列長度來決策調(diào)度節(jié)點，那么任務(wù)就會提交到后者，這將導(dǎo)致任務(wù)不必要的延遲。與選擇前者相比，延遲時間增加100 ms。因此，依據(jù)隊列長度來調(diào)度，效果較差，通過估計每個隊列中任務(wù)的執(zhí)行時間來分配資源，即確定隊列的狀態(tài)，然后決策任務(wù)的分散節(jié)點，這將是一個較好的方案。

對于DHRM，將任務(wù)提交到某個節(jié)點的隊列后，需要經(jīng)過等待和執(zhí)行過程。首先給出各個隊列狀況的表示方式、任務(wù)的參數(shù)形式、等待時間的計算方法和決定一個任務(wù)投入到哪個節(jié)點的調(diào)度依據(jù)。

對于執(zhí)行隊列，考慮CPU資源以及內(nèi)存資源，暫時不考慮其他IO、帶寬等計算資源。調(diào)度器中作業(yè)jk的任務(wù)可表示為：

其中：k表示來自第k個作業(yè)，m表示內(nèi)存需求量，c表示CPU使用時間，et表示作業(yè)估計執(zhí)行時間，P表示優(yōu)先級（由上面給出的算法得出）。

任務(wù)的等待時間，是指一個任務(wù)從提交到隊列上進入排隊狀態(tài)到其開始正式運行所經(jīng)歷的時間。

現(xiàn)設(shè)任務(wù)投入第l個節(jié)點的第i個隊列，并設(shè)該任務(wù)需要的等待時間為wi，有如下三種情況：

當(dāng)隊列中無排隊的任務(wù)時且隊列尚可以繼續(xù)提交任務(wù)，等待時間wi為：

當(dāng)隊列中無排隊的任務(wù)時且不能繼續(xù)提交任務(wù)時，wi等于隊列中剩余時間最小的任務(wù)的剩余時間pti。

當(dāng)隊列中運行著任務(wù)，并且存在n個排隊的任務(wù)，則等待時間等于當(dāng)前隊列中剩余時間最小的任務(wù)的剩余時間pti與該隊列中來自n個作業(yè)中的所有排隊的任務(wù)的估計執(zhí)行時間之和，即：

假如隊列i中的可用CPU核數(shù)為qi，內(nèi)存大小為mi，新的任務(wù)提交到該隊列后，內(nèi)存以及CPU核數(shù)滿足隊列限制條件時，作業(yè)需要等待的時間為wi/qi。對于每個任務(wù)中的CPU使用時間、內(nèi)存需求量等參數(shù)，使用修正系數(shù)來進行調(diào)整，修正系數(shù)記為εi（該系數(shù)是通過對不同類型的作業(yè)進行測試并進行歸一化的結(jié)果）。

調(diào)度器收到各個隊列發(fā)出的hold消息后，選擇等待時間最短的隊列作為目標(biāo)隊列。則最終任務(wù)的最小等待時間可以通過如下公式計算：

通過上述方式，可以獲取候選計算節(jié)點中最小的等待的時間。每次分布式調(diào)度器對各個作業(yè)的任務(wù)進行調(diào)度時，通過對候選計算節(jié)點計算任務(wù)的最小等待時間，以此為依據(jù)進行調(diào)度。

3.3.3 調(diào)度性能分析

與隨機調(diào)度相比，兩階段調(diào)度通過選擇等待時間最短的計算節(jié)點，提高了性能，但是相對于理想調(diào)度（即根據(jù)整個集群資源最新狀態(tài)，選擇一個空閑的CPU核，將任務(wù)提交到該資源，任務(wù)就可以立即執(zhí)行，不需要等待計算資源）相比，其執(zhí)行性能卻差得較多。直觀地講，對每個任務(wù)進行一次兩階段調(diào)度的問題在于，作業(yè)的響應(yīng)時間取決于作業(yè)中任何一個任務(wù)的最長等待時間，這使得平均作業(yè)響應(yīng)時間比平均任務(wù)響應(yīng)時間長得多，特別是某些任務(wù)出現(xiàn)長時間等待的情況，即尾任務(wù)出現(xiàn)滯后的場合。本文模擬了由10 000個4核計算節(jié)點組成的集群中，每個任務(wù)使用兩階段調(diào)度和隨機分配，網(wǎng)絡(luò)通信代價為1 ms。如果作業(yè)按照均勻分布到達(dá)，并且每個作業(yè)包含100個任務(wù)。作業(yè)中任務(wù)的運行時間在指定范圍（平均100 ms）內(nèi)隨機產(chǎn)生。在整個作業(yè)中，響應(yīng)時間隨著負(fù)載的增加而增加，這是因為調(diào)度器串行為作業(yè)中的每個任務(wù)找到空閑計算資源的概率降低的結(jié)果。

3.4 兩階段多路調(diào)度

兩階段調(diào)度過程中，為作業(yè)中的每個任務(wù)串行提供調(diào)度對性能有影響。例如，對于任務(wù)1，任意選擇兩個隊列，可能會出現(xiàn)兩個隊列都忙的情況，但是任務(wù)1必須從兩者之間選擇一個，所以無論怎么選擇，任務(wù)都必須等待計算資源。對于任務(wù)2，任意選擇兩個隊列后，可能兩個隊列都處于空閑狀態(tài)，但是任務(wù)2只能選擇其中一個，這就造成另外一個計算資源的饑餓。如果兩個作業(yè)同時選擇隊列，調(diào)度器可以根據(jù)返回的結(jié)構(gòu)，將任務(wù)1和任務(wù)2都分散到任務(wù)2選擇的空閑隊列上，那么兩個任務(wù)都能夠獲得空閑資源，減少了等待，性能就會得到提高。為了解決該問題，DHRM使用兩階段多路調(diào)度。使用兩階段多路調(diào)度，調(diào)度器采用批量方式，一次對調(diào)度器上可以并發(fā)調(diào)度的所有任務(wù)進行一次資源分配。

假如每個任務(wù)可以選擇兩個隊列，即d=2，如果系統(tǒng)中所有隊列的個數(shù)q≤2*k，那么調(diào)度器向全部的隊列發(fā)送任務(wù)的hold請求。反之，調(diào)度器選擇2*k個隊列，向這些隊列發(fā)送hold請求。當(dāng)所有hold請求的返回消息全部到達(dá)調(diào)度器后，調(diào)度器按照作業(yè)的截止時間為基準(zhǔn)，采用貪心算法為作業(yè)的每個任務(wù)分配執(zhí)行隊列。假設(shè)每個作業(yè)的提交時間為dt，作業(yè)中每個任務(wù)在隊列中等待時間為w，依據(jù)dt按照遞增順序排序，對于w也按照遞增順序排序，貪心調(diào)度（Greedy Schedulering，GS）算法如下所示。

算法1 貪心調(diào)度（GS）。

輸入：Q={q1，q2，…，qn}，n=2*k，J={J1，J2，…，Jn}；

輸出：任務(wù)J到Q上的一個映射。

1）sort(Q)，sort(J) //遞增排序

2）for（JjinJ）｛

3） for（tiinJi）｛

4） for（qkinQ）｛

5） if（qk.m≥ti.m）｛

6）Q=Qqk

7）Ji=Ji i

8） ｝

9） ｝

10）｝

11）｝

GS算法中的第1）行，分別按照作業(yè)提交時間為作業(yè)排序，按照執(zhí)行隊列上的等待時間為執(zhí)行隊列排序。對于作業(yè)中的每個任務(wù)，從隊列中選擇滿足條件的執(zhí)行隊列，將任務(wù)分配給執(zhí)行隊列，如GS算法中的第3）～10）行。GS算法為每個作業(yè)分配完成后，如果還存在有未分配的任務(wù)，則繼續(xù)調(diào)用兩階段多路分配算法，為剩余作業(yè)中的任務(wù)繼續(xù)分配資源。

GS算法的目的在于盡量降低每個作業(yè)的完成時間，所以采用貪心算法保證每個作業(yè)的滯后任務(wù)盡量早一點分配到內(nèi)存，能夠盡快完成作業(yè)的執(zhí)行。但是，算法執(zhí)行過程中，可能每次都有任務(wù)不能夠獲得資源，算法將這些任務(wù)與新的任務(wù)一起，在下一次兩階段多路調(diào)度過程中為這些任務(wù)重新分配執(zhí)行隊列。

3.5 負(fù)載平衡的處理

使用兩階段多路調(diào)度策略后，雖然在一定程度上提高了性能，但是還存在一個問題。例如，假如隨機選擇的執(zhí)行隊列都是負(fù)載較重的隊列，而一部分沒有選擇的執(zhí)行隊列卻處于空閑狀態(tài)，造成負(fù)載的不平衡?？梢杂^察到，從一個任務(wù)被分散到某個隊列開始，在任務(wù)實際開始執(zhí)行的這個期間，整個集群節(jié)點上會出現(xiàn)一個更好的執(zhí)行隊列。原因可能是預(yù)計開始時間的估計錯誤、資源的競爭或者計算節(jié)點失效等情況時，造成任務(wù)選擇的執(zhí)行隊列不是最優(yōu)的。因此需要考慮一些策略來減少這種情況的發(fā)生，例如動態(tài)負(fù)載平衡技術(shù)。在DHRM中，通過采用負(fù)載平衡技術(shù)來實現(xiàn)任務(wù)在不同隊列上的計算資源的平衡。

為實現(xiàn)負(fù)載平衡，需要指定一個計算節(jié)點為協(xié)調(diào)器，負(fù)載較輕的計算節(jié)點向協(xié)調(diào)器發(fā)送空閑隊列的資源狀態(tài)，負(fù)載較重的計算節(jié)點的隊列向協(xié)調(diào)器發(fā)送任務(wù)的資源請求。協(xié)調(diào)器收到資源狀態(tài)和資源請求后，通過匹配方式，為負(fù)載較重的計算節(jié)點上的任務(wù)匹配到需要的資源，實現(xiàn)負(fù)載在計算節(jié)點之間的平衡。其實現(xiàn)過程圖2所示。圖2中包含資源協(xié)調(diào)器（Negotiator）、計算節(jié)點1（machine1）和計算節(jié)點2（machine2）3個組成部分。計算節(jié)點1用來檢測需要轉(zhuǎn)送的任務(wù)，計算節(jié)點2用來確定負(fù)載較輕的隊列，協(xié)調(diào)器用來將計算節(jié)點1上的任務(wù)匹配到計算節(jié)點2上。

圖2 負(fù)載平衡過程Fig.2 Process of load balancing

在正常情況下，任務(wù)在各自的隊列中等待計算資源，一旦獲得計算資源就開始運行任務(wù)。當(dāng)某個節(jié)點的隊列中任務(wù)的等待時間超過某個閾值hw，計算節(jié)點就為隊列中的任務(wù)啟動負(fù)載平衡分散過程。另外，當(dāng)某個計算節(jié)點的隊列等待時間低于閾值lw時，計算節(jié)點向協(xié)調(diào)器發(fā)送資源狀態(tài)信息，協(xié)調(diào)器根據(jù)資源狀態(tài)和資源請求，從負(fù)載高的節(jié)點上轉(zhuǎn)移部分任務(wù)到負(fù)載低的節(jié)點上，實現(xiàn)計算節(jié)點的負(fù)載平衡。

負(fù)載平衡主要包含三個階段：第一階段，任務(wù)向資源協(xié)調(diào)器提交分散請求；第二階段，協(xié)調(diào)器經(jīng)過調(diào)度而得到最終的目標(biāo)節(jié)點，然后協(xié)調(diào)器將目標(biāo)節(jié)點信息返回給原節(jié)點；第三階段，原節(jié)點和目標(biāo)節(jié)點進行確認(rèn)后，將任務(wù)分散到目標(biāo)節(jié)點。

如圖2所示，計算節(jié)點1的一個任務(wù)發(fā)出分散請求（圖2中的過程①）。協(xié)調(diào)器接收到任務(wù)的請求后，將其放入隊列中，一旦計算節(jié)點2上的負(fù)載較輕，即等待執(zhí)行的任務(wù)低于閾值，計算節(jié)點2向協(xié)調(diào)器發(fā)送資源狀態(tài)（圖2中的過程②），協(xié)調(diào)器根據(jù)最新的隊列等待時間矩陣，選擇一個最佳的目標(biāo)節(jié)點，例如本例子中的計算節(jié)點2，然后將分配結(jié)果返回給計算節(jié)點1（圖2中的過程③）。計算節(jié)點1收到消息后，開始向計算節(jié)點2發(fā)送確認(rèn)信息（圖2中的過程④），計算節(jié)點2收到信息后，根據(jù)本節(jié)點的狀態(tài)對任務(wù)請求進行檢查，如資源檢查、用戶權(quán)限檢查、隊列負(fù)載狀態(tài)檢查等，檢查結(jié)果通常會有如下兩種情況：

1）如果請求不被目標(biāo)節(jié)點許可的原因不是由于節(jié)點忙，那么該請求就會被終止。

2）如果請求不被目標(biāo)節(jié)點許可的原因是該節(jié)點忙，比如當(dāng)前狀態(tài)下隊列上已經(jīng)被運行著的任務(wù)占滿了，并且隊列上存在一些排隊的任務(wù)。那么該請求的標(biāo)識符將被保存到計算節(jié)點2上（圖2中的過程⑤），請求在計算節(jié)點1上處于等待狀態(tài)。

當(dāng)計算節(jié)點2可以執(zhí)行該任務(wù)，而要求轉(zhuǎn)送保存在該節(jié)點上的備份任務(wù)時，就會發(fā)送轉(zhuǎn)送請求給計算節(jié)點1（圖2中的過程⑥）。此時，計算節(jié)點1就會將該任務(wù)由等待狀態(tài)變成排隊狀態(tài)，并設(shè)置較高的優(yōu)先級別，同時運送任務(wù)請求的內(nèi)容到目標(biāo)節(jié)點（圖2中的過程⑥和⑦）。

任務(wù)請求轉(zhuǎn)送完成，計算節(jié)點1正式向計算節(jié)點2提交任務(wù)（圖2中的過程⑧）。此時新的任務(wù)的加入，如果導(dǎo)致計算節(jié)點的等待時間超過閾值，計算節(jié)點向協(xié)調(diào)器發(fā)送取消資源狀態(tài)消息，不再接受負(fù)載平衡任務(wù)。

4 調(diào)度策略以及約束

在調(diào)度策略方面，DHRM只支持兩種調(diào)度策略。本章介紹對兩種流行的調(diào)度程序策略的支持：第一，任務(wù)執(zhí)行時的數(shù)據(jù)本地化訪問，DHRM在進行任務(wù)調(diào)度的時候，為了提高任務(wù)的響應(yīng)速度，通常需要盡量保證執(zhí)行任務(wù)的機器就是數(shù)據(jù)所在機器。調(diào)度器可以對兩階段多路調(diào)度的貪心調(diào)度算法添加本地化約束，從而最大限度地保證數(shù)據(jù)本地化；第二，不同用戶資源共享時的隔離問題。DHRM旨在實現(xiàn)不同類型的作業(yè)共享同一套集群資源，因此，在集群中大部分的時間內(nèi)，會有不同類型的作業(yè)以及任務(wù)運行在集群中，DHRM的調(diào)度器需要保證作業(yè)之間運行的時候不能互相干擾，這點調(diào)度器通過為每個作業(yè)啟動若干個容器，作業(yè)的任務(wù)都會在容器中運行，從邏輯上隔離開了資源的使用，確保作業(yè)之間不會互相影響。

DHRM支持作業(yè)級別以及任務(wù)級別的約束。這些約束在大數(shù)據(jù)處理中經(jīng)常出現(xiàn)，當(dāng)任務(wù)運行時，數(shù)據(jù)的訪問位置與數(shù)據(jù)計算位置最好在同一個計算節(jié)點上。輸入數(shù)據(jù)與任務(wù)計算在同一個計算節(jié)點時，因為不需要通過網(wǎng)絡(luò)傳輸輸入數(shù)據(jù)，通常會減少任務(wù)的響應(yīng)時間。對于每個任務(wù)的本地化訪問約束，每個任務(wù)都可能具有一組計算節(jié)點，任務(wù)按照本地化要求進行計算，DHRM無法使用兩階段多路調(diào)度來匯總每個作業(yè)中所有任務(wù)的本地化信息。相反，DHRM使用兩階段調(diào)度時，可以從該任務(wù)的本地化約束中找到待選的目標(biāo)計算節(jié)點，這樣通過限制每個任務(wù)發(fā)送hold消息的目標(biāo)計算節(jié)點數(shù)量，使得每個任務(wù)在執(zhí)行時才會為其選擇執(zhí)行的計算節(jié)點，從而實現(xiàn)任務(wù)與數(shù)據(jù)的后期綁定。雖然DHRM無法對作業(yè)中的每個任務(wù)實現(xiàn)數(shù)據(jù)本地化約束，但是在貪心算法中添加本地化約束策略，可以最大限度地支持任務(wù)的數(shù)據(jù)本地化約束。為了在貪心算法中添加本地化約束，可以將GS算法第5）行的條件判斷略作豐富，即除了判斷隊列資源是否滿足任務(wù)需求的同時，需要判斷該隊列所在計算節(jié)點是否存在于任務(wù)本地化訪問約束集合中。若存在，則可以將其添加到任務(wù)到隊列的映射中；若不存在，可以使用原有的方法為其找到一個合適的隊列。

當(dāng)總的資源需求超過集群計算節(jié)點的容量時，集群調(diào)度程序?qū)⒏鶕?jù)特定策略分配資源。DHRM支持嚴(yán)格優(yōu)先級資源分配。許多集群共享策略簡化為使用嚴(yán)格的優(yōu)先級，DHRM通過在工作節(jié)點上維護多個隊列來支持所有此類策略，依據(jù)任務(wù)的優(yōu)先級別和隊列的優(yōu)先級別，實現(xiàn)作業(yè)的優(yōu)先調(diào)度，減少作業(yè)中尾任務(wù)的滯留。從常用的FIFO、最早截止日期優(yōu)先和最短作業(yè)優(yōu)先轉(zhuǎn)變到為每個作業(yè)分配優(yōu)先級，然后優(yōu)先運行優(yōu)先級最高的作業(yè)。例如，以最早的截止時間為最高優(yōu)先級別時，將截止時間較早的工作分配給更高的優(yōu)先級。集群資源管理系統(tǒng)也可能希望直接分配優(yōu)先級，例如，將生產(chǎn)作業(yè)設(shè)置高優(yōu)先級別，批處理作業(yè)設(shè)置較低的優(yōu)先級別。為支持這些策略，DHRM為計算節(jié)點的每個隊列維護一個優(yōu)先級別。當(dāng)資源變?yōu)榭臻e時，DHRM從優(yōu)先級最高的非空隊列中取出任務(wù)并執(zhí)行。當(dāng)高優(yōu)先級任務(wù)到達(dá)那些正在運行低優(yōu)先級任務(wù)的計算機時，DHRM也支持搶占。DHRM的設(shè)計思想是提高每個作業(yè)的完成時間，不出現(xiàn)某個作業(yè)中一個或者幾個任務(wù)的嚴(yán)重滯后的任務(wù)，因此DHRM暫時不支持計算資源在各個作業(yè)之間的公平訪問，這也是將來得探索的問題。

5 系統(tǒng)實現(xiàn)

本文中的DHRM采用了網(wǎng)絡(luò)隊列系統(tǒng)（Network Queue System，NQS）［27-28］和Mesos資源調(diào)度框架。NQS在各個計算節(jié)點安裝，本文為NQS添加了一個ResourceTracker服務(wù)，用來獲得各個執(zhí)行隊列中任務(wù)的最新狀態(tài)?！癚sub-hold”命令作為第一階段的消息，將原來NQS中返回結(jié)果進行了變更，即由單純的請求編號改變?yōu)榫幪柡腿蝿?wù)等待時間兩個部分；分布式調(diào)度器由mesos改造而來，借鑒了mesos中“推送”的資源管理模式，作業(yè)注冊到mesos調(diào)度框架后，mesos根據(jù)作業(yè)中的任務(wù)描述，向各個集群節(jié)點請求資源；獲得資源后，將資源打包成ResourceOffer，然后推送給Spark計算框架，由Spark的調(diào)度器經(jīng)過決策后，選擇需要的資源，啟動執(zhí)行任務(wù)需要的Executor。最后由Executor完成任務(wù)的執(zhí)行。

主要的改進有：1）對于作業(yè)框架，重新封裝了Spark的調(diào)度器，以便適應(yīng)細(xì)粒度的任務(wù)調(diào)度模式。2）資源管理方面，改進了Mesos集群資源管理框架，計算資源的獲得不再通過主導(dǎo)資源分配公平（Dominant Resource Fairness，DRF）［29］方式分配。3）在計算節(jié)點改進NQS系統(tǒng)后，DHRM支持兩階段多路調(diào)度中執(zhí)行隊列的等待時間的計算以及負(fù)載平衡時的空閑隊列的資源狀態(tài)的收集。

圖3給出了DHRM任務(wù)調(diào)度以及負(fù)載平衡的過程。任務(wù)調(diào)度是一個循環(huán)過程；負(fù)載平衡是動態(tài)觸發(fā)的循環(huán)的過程，通常是在集群負(fù)載較高的時候才會觸發(fā)。任務(wù)調(diào)度中，一旦計算框架的調(diào)度器（Spark Scheduler）向集群資源管理系統(tǒng)的一個 調(diào) 度 器 實 例（Distributed Scheduler）注 冊，Distributed Scheduler就選擇2倍的任務(wù)數(shù)量的候選隊列，啟動qsub-hold命令，等待全部返回執(zhí)行隊列狀態(tài)（queue status）后，調(diào)度器從返回的結(jié)果中，選擇最優(yōu)的執(zhí)行隊列，然后向Spark Scheduler發(fā)送資源邀約（Resource Offer）命令。當(dāng)Distributed Scheduler收到Spark Scheduler的返回的任務(wù)集合（taskset）后，使用Qrls命令啟動不同計算節(jié)點上的執(zhí)行器（Executor），最后Executor從計算框架獲得任務(wù)并運行。負(fù)載平衡中，當(dāng)一個隊列系統(tǒng)中的任務(wù)等待時間超過閾值，就向協(xié)調(diào)器（Negotiator）發(fā)送資源請求（request），協(xié)調(diào)器選擇負(fù)載較輕的目標(biāo)隊列返回給資源請求者（resource），然后資源請求者向目標(biāo)隊列轉(zhuǎn)送任務(wù)（Task Migration）。

圖3 DHRM順序圖Fig.3 Sequence diagram of DHRM

6 性能評價

系統(tǒng)在一個集群上進行實驗，集群中包含16臺服務(wù)器，其中15臺服務(wù)器（浪潮NF5468M5服務(wù)器）作為計算節(jié)點，1臺中科曙光服務(wù)器620/420，作為協(xié)調(diào)器。每個服務(wù)器節(jié)點包含2顆Xeon2.1處理器，每個處理器包含8個核，32 GBDDR4內(nèi)存。集群上包含1臺AS2150G2磁盤陣列。服務(wù)器操作系統(tǒng)為Ubuntu 7.5.0，采用C++11作為編程語言，Mesos的基礎(chǔ)版本為1.8，Spark的基礎(chǔ)版本為2.4.3。這些計算機被組織在4個機架內(nèi)，每個機架包含4臺計算機。機架內(nèi)的計算機通過機架連接，各個機架交換機通過級聯(lián)方式與匯聚交換機連接。

測試時使用了5個分布式調(diào)度器，首先，本文使用DHRM為TPC-H工作負(fù)載調(diào)度任務(wù)，其負(fù)載具有分析查詢功能。首先在理想的調(diào)度程序的基礎(chǔ)上比較作業(yè)的響應(yīng)時間。本文提供了DHRM細(xì)粒度資源共享時的開銷并量化了其性能。同時，為了比較本文中所述任務(wù)調(diào)度算法與已有的調(diào)度算法的優(yōu)劣，于是在同等條件下測試了sparrow的任務(wù)調(diào)度算法包括批采樣以及每任務(wù)采樣等技術(shù)所造成的延遲，并與DHRM進行了比較，分析兩者之間的差距。其次，本文展示了DHRM在調(diào)度延遲以及等待時間方面的對比。最后，為了體現(xiàn)大規(guī)模集群環(huán)境下，大量任務(wù)的調(diào)度延遲，本文設(shè)計了一個基于Spark調(diào)度器的模擬程序和一個模擬的大規(guī)模集群環(huán)境，通過模擬程序在模擬集群環(huán)境的調(diào)度，分析了調(diào)度延遲的特點。

6.1 TPC-H負(fù)載的性能對比

本文使用運行在Spark的TPC-H（www.tpc.org/tpch/）查詢基準(zhǔn)來測試DHRM的調(diào)度性能。TPC-H基準(zhǔn)代表對事務(wù)數(shù)據(jù)的查詢，這是低延遲數(shù)據(jù)并行框架的常見用例。每個TPCH查詢在Spark下運行，Spark將查詢轉(zhuǎn)換成DAG，按照不同的階段來調(diào)度執(zhí)行。查詢的響應(yīng)時間是各個階段響應(yīng)時間之和。5個不同的用戶啟動多個TPC-H查詢負(fù)載，查詢負(fù)載隨機排列，并且在大約15 min的時間內(nèi)維持集群負(fù)載在80%左右。本文針對實驗中200 s的數(shù)據(jù)進行了分析，在200 s中，DHRM調(diào)度了超過4 000個作業(yè)，這些作業(yè)構(gòu)成了1 200個TPC-H查詢。每個用戶都在TPC-H數(shù)據(jù)集的副本上運行查詢，數(shù)據(jù)集的大小大約為2 GB，并分為30個分區(qū)，每個分區(qū)的副本數(shù)設(shè)置為3。

為了比較DHRM的性能，本文假設(shè)任務(wù)在計算節(jié)點上沒有等待時間，就像粗粒度資源分配方式一樣，這個響應(yīng)時間稱為理想時間。在計算某個查詢的理想響應(yīng)時間時，本文分析了一次查詢的DAG過程中的每個階段，去掉隊列等待時間后，將其他階段的時間相加，最后得到查詢的理想響應(yīng)時間。由于DHRM在計算理想響應(yīng)時間時，采用了任務(wù)的執(zhí)行時間，所以理想響應(yīng)時間也包括每個任務(wù)的本地化約束。理想的響應(yīng)時間不包括將任務(wù)發(fā)送到計算節(jié)點所需的時間，也不包括在利用率突發(fā)期間不可避免的排隊等待時間，所以，理想響應(yīng)時間是調(diào)度器可以實現(xiàn)的響應(yīng)時間的下限。

圖4給出的數(shù)據(jù)可以看出，與隨機調(diào)度、兩階段調(diào)度相比，DHRM的兩階段多路調(diào)度最優(yōu)，基本上不超過理想調(diào)度時間的13%。與隨機調(diào)度相比，兩階段多路調(diào)度只是隨機調(diào)度平均響應(yīng)時間的25%～33%，95%分位數(shù)的響應(yīng)時間最多只是隨機調(diào)度時間的20%。與兩階段調(diào)度相比，兩階段多路調(diào)度的響應(yīng)時間是兩階段調(diào)度響應(yīng)時間的80%，95%分位數(shù)的響應(yīng)時間也只達(dá)到兩階段調(diào)度的60%。與兩階段多路調(diào)度相比，負(fù)載平衡策略的使用，平均響應(yīng)時間減少了14%。DHRM還提供了良好的絕對性能：其中值響應(yīng)時間僅比理想調(diào)度程序所提供的響應(yīng)時間高12%。

圖4 DHRM不同調(diào)度算法的響應(yīng)時間對比Fig.4 Comparison of response time of different scheduling algorithms in DHRM

除了在DHRM內(nèi)測試不同調(diào)度算法的性能，本文還比較了DHRM與sparrow的批采樣調(diào)度算法以及每任務(wù)采樣調(diào)度算法。結(jié)果如圖5所示。從圖5中的結(jié)果可以看出，DHRM兩階段多路調(diào)度算法加負(fù)載均衡技術(shù)和sparrow的批采樣算法最優(yōu)，其中sparrow的批采樣調(diào)度算法中值響應(yīng)時間僅比理想的影響時間高出13%左右，和DHRM的兩階段多路調(diào)度算法性能大致相當(dāng)，這表明本文的兩階段多路調(diào)度算法具有較為良好的性能。但是兩階段多路調(diào)度若是不使用負(fù)載平衡技術(shù)，則性能要低于sparrow的批采樣技術(shù)。雖然sparrow的批采樣技術(shù)性能較佳，但是sparrow的每任務(wù)采樣技術(shù)性能比其他調(diào)度技術(shù)要差，其比理想調(diào)度延遲高出大約40%。兩階段多路技術(shù)即使不使用負(fù)載平衡技術(shù)在性能上也略高于每任務(wù)采樣技術(shù)。從圖5的結(jié)果可以看出，DHRM的調(diào)度技術(shù)在性能上不輸于sparrow調(diào)度框架，而sparrow也是應(yīng)用于大規(guī)模低延遲任務(wù)的調(diào)度框架。

圖5 DHRM和sparrow不同調(diào)度算法的響應(yīng)時間對比Fig.5 Comparison of response time of different scheduling algorithms in DHRM and sparrow

6.2 作業(yè)響應(yīng)時間對比

為了理解DHRM相對于理想調(diào)度程序增加的延遲的組成部分，本文將作業(yè)的響應(yīng)時間分解為調(diào)度時間、隊列中等待時間以及任務(wù)執(zhí)行時間3個單獨的時間。圖6中給出了不同時間中任務(wù)的累計概率函數(shù)圖。圖中的每一根曲線代表一個任務(wù)數(shù)量與時間的變化曲線。

從圖6的曲線看出，60%的任務(wù)其調(diào)度延遲時間為5 ms左右，40%的作業(yè)其調(diào)度延遲為12 ms；而任務(wù)在隊列中的等待時間較長，75%的任務(wù)在隊列中的等待時間為50 ms，剩余25%的任務(wù)的等待時間大約為100 ms。任務(wù)的執(zhí)行時間在350 ms以內(nèi)，其中40%的任務(wù)執(zhí)行時間在150 ms內(nèi)，超過250 ms的任務(wù)只占有15%左右。從圖6可以看出，分布式集群調(diào)度框架確實能夠減少調(diào)度延遲。

圖6 任務(wù)延遲統(tǒng)計Fig.6 Task delay statistics

6.3 大規(guī)模集群的性能模擬

為了驗證DHRM的資源調(diào)度框架在大規(guī)模集群環(huán)境下的調(diào)度延遲，本文設(shè)計了一套資源調(diào)度框架性能模擬器工具，DHRM_Simulator，用于對DHRM的資源調(diào)度功能進行測試。它可以在多臺機器上模擬大規(guī)模集群，并根據(jù)歷史日志分析提取出應(yīng)用程序負(fù)載信息，模擬完整的資源分配、任務(wù)調(diào)度和資源回收過程。通過使用8臺服務(wù)器來模擬大規(guī)模的集群環(huán)境。實驗過程中每臺機器均為NF5468M5服務(wù)器，包含2顆Xeon2.1處理器，每個處理器包含8個核，32 GBDDR4內(nèi)存。

6.3.1 模擬機器數(shù)量的設(shè)置

為了測試大規(guī)模集群計算資源的調(diào)度性能，使用1臺機器模擬協(xié)調(diào)器，其余7臺機器模擬計算節(jié)點。每臺工作節(jié)點機器設(shè)置50個隊列，每個隊列模擬一臺物理機器，稱為邏輯機器。隊列的同時運行的槽數(shù)（slot）設(shè)置為8，代表一個邏輯機器上包含8個模擬的CPU核。這樣的話，1臺物理機器就可以模擬50臺邏輯機器，7臺物理機器模擬350臺邏輯機器，每臺模擬的邏輯機器上模擬8個CPU核，那么整個模擬系統(tǒng)可以使用的CPU計算資源為2 800個模擬的CPU核。

6.3.2 作業(yè)的定義

采用類似Spark調(diào)度器，本文實現(xiàn)了一個模擬作業(yè)框架。每個作業(yè)框架上包含數(shù)量不等的任務(wù)。任務(wù)的執(zhí)行時間由sleep代替。作業(yè)提交后，按照task任務(wù)數(shù)量，隨機選擇2倍的task任務(wù)數(shù)量的隊列（一個隊列代表一個模擬機器），獲得隊列中的剩余的可以使用的slot數(shù)，選擇剩余slot最大的隊列作為選擇的資源，使用qsub啟動一個Spark Executor類似的進程，進程內(nèi)的作業(yè)執(zhí)行類似sleep執(zhí)行，不設(shè)置具體的數(shù)據(jù)執(zhí)行任務(wù)。任務(wù)的執(zhí)行時間由sleep長短來決定，即等待時間長短，如200，代表任務(wù)執(zhí)行時間是200 ms。

向模擬器連續(xù)啟動7×20個作業(yè)（即7個分布式調(diào)度器實例），即每個分布式調(diào)度器實例啟動20個作業(yè)，每個作業(yè)按照160個任務(wù)設(shè)置。作業(yè)按照一定的時間間隔向各自的分布式調(diào)度器注冊并請求資源執(zhí)行。集中式調(diào)度器的測試則是將7×20個作業(yè)同時向該集中式調(diào)度器注冊啟動。

6.3.3 響應(yīng)時間

為了測試分布式調(diào)度框架的低延遲，使用集中方式與分布方式進行對比。集中式調(diào)度器采用類似mesos的方式實現(xiàn)。測試中，分別設(shè)置任務(wù)的sleep時間為100 ms、200 ms、1 000 ms三種不同的任務(wù)執(zhí)行時間，用來驗證作業(yè)響應(yīng)時間與調(diào)度器的調(diào)度延遲之間的關(guān)系。圖7給出了三種情況下的模擬測試結(jié)果。

圖7 模擬環(huán)境下集中式和分布式調(diào)度的響應(yīng)時間對比Fig.7 Response time comparison of centralized and distributed scheduling in simulated environment

從圖7的結(jié)果看，任務(wù)運行時間在1 000 ms時，分布式調(diào)度和集中調(diào)度方式下，作業(yè)的響應(yīng)時間基本相同。但是當(dāng)任務(wù)的執(zhí)行時間是200 ms時，分布式調(diào)度的平均響應(yīng)時間是集中式調(diào)度方式下的一半左右。而任務(wù)執(zhí)行更短，即100 ms時，分布式調(diào)度器和集中式調(diào)度器的差別就更大，幾乎是10倍左右的差別。因為，分布式調(diào)度器能夠減少調(diào)度的延遲時間，為大規(guī)模并行任務(wù)的執(zhí)行提高了效率。因此，相較于mesos等集中式資源調(diào)度器，DHRM的分布式調(diào)度器能夠?qū)Υ笈康亩倘蝿?wù)有更好的調(diào)度效率，使大批量的短任務(wù)具有較低的響應(yīng)時間。

7 結(jié)語

大規(guī)模運行時間較短的任務(wù)越來越多，呈現(xiàn)出并行度越來越高的趨勢，這種作業(yè)的調(diào)度普遍受到重視。數(shù)據(jù)中心上運行的這類任務(wù)對延遲非常敏感。另外，隨著集群計算節(jié)點規(guī)模的擴大，調(diào)度延遲是影響作業(yè)吞吐量和性能的主要瓶頸。但是，傳統(tǒng)的集群資源調(diào)度框架在低延遲方面存在一定的缺陷，本文通過兩階段多路調(diào)度以及負(fù)載平衡技術(shù)，解決了現(xiàn)有調(diào)度框架中延遲較高和負(fù)載不均衡的問題，通過TPC-H基準(zhǔn)測試以及大規(guī)模集群下的模擬測試，調(diào)度框架能夠保證短時間任務(wù)的低延遲要求。但是，本文算法在數(shù)據(jù)本地化訪問以及資源分配的公平性方面有待進一步的提高。