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

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

0 引言

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

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

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

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

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

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

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

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

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

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

1 相關(guān)工作

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

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

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

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

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

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

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

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

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

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

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

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

3.1 一些基本的概念

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

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

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

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

3.2 計(jì)算節(jié)點(diǎn)上的隊(duì)列

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

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

執(zhí)行隊(duì)列為CPU任務(wù)的專(zhuān)用隊(duì)列。執(zhí)行隊(duì)列具有三類(lèi)屬性：

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

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

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

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

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

3.3.1 調(diào)度過(guò)程

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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è)提交時(shí)間為作業(yè)排序，按照?qǐng)?zhí)行隊(duì)列上的等待時(shí)間為執(zhí)行隊(duì)列排序。對(duì)于作業(yè)中的每個(gè)任務(wù)，從隊(duì)列中選擇滿(mǎn)足條件的執(zhí)行隊(duì)列，將任務(wù)分配給執(zhí)行隊(duì)列，如GS算法中的第3）～10）行。GS算法為每個(gè)作業(yè)分配完成后，如果還存在有未分配的任務(wù)，則繼續(xù)調(diào)用兩階段多路分配算法，為剩余作業(yè)中的任務(wù)繼續(xù)分配資源。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

6 性能評(píng)價(jià)

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

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

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

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

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

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

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

除了在DHRM內(nèi)測(cè)試不同調(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)時(shí)間僅比理想的影響時(shí)間高出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)時(shí)間對(duì)比Fig.5 Comparison of response time of different scheduling algorithms in DHRM and sparrow

6.2 作業(yè)響應(yīng)時(shí)間對(duì)比

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

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

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

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

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

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

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

6.3.2 作業(yè)的定義

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

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

6.3.3 響應(yīng)時(shí)間

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

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

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

7 結(jié)語(yǔ)

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