在離線混部作業(yè)調(diào)度與資源管理技術(shù)研究綜述?

王康瑾,賈 統(tǒng),李 影,2

1(北京大學(xué) 軟件與微電子學(xué)院,北京 102600)

2(北京大學(xué) 軟件工程國(guó)家工程研究中心,北京 100871)

3(北京大學(xué) 信息科學(xué)技術(shù)學(xué)院,北京 100871)

大規(guī)模數(shù)據(jù)中心是當(dāng)今企業(yè)級(jí)互聯(lián)網(wǎng)應(yīng)用和云計(jì)算系統(tǒng)的關(guān)鍵支撐.為保障日益增長(zhǎng)的互聯(lián)網(wǎng)應(yīng)用和云計(jì)算系統(tǒng)的計(jì)算需求,數(shù)據(jù)中心需要不斷擴(kuò)容,其規(guī)模和服務(wù)器總量呈現(xiàn)快速增長(zhǎng)趨勢(shì).權(quán)威報(bào)告[1]指出,2020 年全球數(shù)據(jù)中心的服務(wù)器總量將達(dá)到1 800 萬(wàn)臺(tái),并且正以每年100 萬(wàn)臺(tái)的速度增長(zhǎng).然而,伴隨著數(shù)據(jù)中心的急速擴(kuò)容,其資源利用率卻始終處于較低狀態(tài).統(tǒng)計(jì)數(shù)據(jù)表明[1],目前全球數(shù)據(jù)中心資源利用率僅為10%～20%,如此低的資源利用率意味著數(shù)據(jù)中心大量的資源浪費(fèi),導(dǎo)致目前數(shù)據(jù)中心的成本效率極低.因此,如何提升數(shù)據(jù)中心資源利用率成為一個(gè)亟需解決的關(guān)鍵性技術(shù)問(wèn)題.

通常而言,數(shù)據(jù)中心以作業(yè)為抽象單位執(zhí)行計(jì)算任務(wù).按照計(jì)算任務(wù)的不同可將作業(yè)分為在線作業(yè)和離線作業(yè).在線作業(yè)通常是以服務(wù)形態(tài)來(lái)處理用戶請(qǐng)求并執(zhí)行計(jì)算任務(wù),如網(wǎng)頁(yè)搜索服務(wù)、在線游戲服務(wù)、電商交易服務(wù)等,具備較高的實(shí)時(shí)性和穩(wěn)定性需求.為保障上述需求,企業(yè)往往會(huì)對(duì)外提供明確的服務(wù)等級(jí)協(xié)議(service level agreement,簡(jiǎn)稱SLA),以明確的條款約定服務(wù)質(zhì)量.違反SLA 會(huì)給企業(yè)帶來(lái)經(jīng)濟(jì)損失,因此數(shù)據(jù)中心往往為在線作業(yè)預(yù)留大量的服務(wù)器資源以保證其服務(wù)質(zhì)量.離線作業(yè)通常是計(jì)算密集型的批處理作業(yè),如MapReduce和Spark 作業(yè)[2,3]數(shù)據(jù)分析作業(yè)/機(jī)器學(xué)習(xí)模型訓(xùn)練作業(yè)等.多數(shù)離線作業(yè)對(duì)于性能沒(méi)有嚴(yán)格的要求,可以容忍較高的運(yùn)行延遲并支持失敗任務(wù)的重啟.按照集群上所運(yùn)行的作業(yè)類型,數(shù)據(jù)中心可劃分為在線集群和離線集群.在線集群通常因在線作業(yè)對(duì)性能的高要求而采用過(guò)量資源供給策略,導(dǎo)致資源利用率較低;與之相反,隨著大數(shù)據(jù)[4-7]和人工智能的發(fā)展,離線作業(yè)的規(guī)模日益擴(kuò)大,離線集群對(duì)計(jì)算資源的需求日益增長(zhǎng),導(dǎo)致現(xiàn)有集群資源供給不足[8].因此,提升數(shù)據(jù)中心整體資源利用率的理想方法是在保障在線作業(yè)性能的前提下,將在線集群的空閑資源分配給離線作業(yè),即:將在線作業(yè)與離線作業(yè)混合部署于同一集群,簡(jiǎn)稱“混部(colocation)”.目前,在離線混部已成為數(shù)據(jù)中心提升整體資源利用率的主流方法[9].

在混部作業(yè)運(yùn)行過(guò)程中,由于在離線作業(yè)競(jìng)爭(zhēng)共享資源(如CPU、緩存、內(nèi)存帶寬、網(wǎng)絡(luò)帶寬等),往往會(huì)導(dǎo)致作業(yè)性能下降(performance degradation),該現(xiàn)象也被稱為性能干擾(performance interference)[10-15].性能干擾會(huì)嚴(yán)重影響在線作業(yè)的實(shí)時(shí)性和穩(wěn)定性,降低離線作業(yè)的吞吐率,因此,混部集群管理系統(tǒng)必須有效控制性能干擾,并根據(jù)性能干擾快速、及時(shí)地做出調(diào)整.然而,性能干擾的程度受諸多因素影響,尤其是在超大規(guī)模的數(shù)據(jù)中心中,作業(yè)負(fù)載的動(dòng)態(tài)性、資源需求的多樣性、硬件架構(gòu)的異構(gòu)性等導(dǎo)致性能干擾復(fù)雜性劇增.為降低復(fù)雜的性能干擾,混部集群管理系統(tǒng)必須能夠協(xié)調(diào)集群層的作業(yè)調(diào)度和節(jié)點(diǎn)層的資源管理,實(shí)現(xiàn)性能干擾的分層控制.集群層的作業(yè)調(diào)度,即決策作業(yè)運(yùn)行的具體位置(具體某個(gè)服務(wù)器).混部作業(yè)調(diào)度是一個(gè)復(fù)雜的多目標(biāo)優(yōu)化問(wèn)題,既需要兼顧集群的負(fù)載均衡、整體吞吐率、資源公平性等目標(biāo),又需要特別考慮性能干擾的影響,根據(jù)性能干擾的變化隨時(shí)調(diào)整調(diào)度策略;節(jié)點(diǎn)層的資源管理,即利用資源隔離技術(shù)根據(jù)性能干擾變化動(dòng)態(tài)調(diào)整運(yùn)行作業(yè)的資源供給.因此,集群層的作業(yè)調(diào)度和節(jié)點(diǎn)層的資源管理成為降低和控制性能干擾、提升資源利用率的重要手段.

本文首先分析了在離線作業(yè)的特征,深入探討了在離線作業(yè)在混合部署中競(jìng)爭(zhēng)共享資源帶來(lái)的性能干擾及作業(yè)調(diào)度和資源管理問(wèn)題,就作業(yè)性能干擾模型、集群層面的混部作業(yè)調(diào)度以及節(jié)點(diǎn)層面的資源管理等關(guān)鍵技術(shù)進(jìn)行了詳細(xì)介紹和分析,并結(jié)合4 個(gè)系統(tǒng)實(shí)例探討了在離線混部關(guān)鍵技術(shù)在產(chǎn)業(yè)界的實(shí)現(xiàn)及其效果,最后就未來(lái)的研究方向進(jìn)行了討論和展望.

1 概述

本節(jié)分析了在線作業(yè)和離線作業(yè)的各自特點(diǎn),并探討了在離線混部集群管理上所面臨的主要問(wèn)題與挑戰(zhàn).

1.1 在線作業(yè)與離線作業(yè)

在線作業(yè).在線作業(yè)通常是處理用戶請(qǐng)求的服務(wù),典型的在線作業(yè)有網(wǎng)頁(yè)搜索、即時(shí)通信、語(yǔ)音識(shí)別、流式計(jì)算、電子商務(wù)、流媒體等,通?？蔀槠髽I(yè)帶來(lái)直接的經(jīng)濟(jì)利益.在線作業(yè)具有如下特點(diǎn).

(1)運(yùn)行時(shí)間長(zhǎng).在線作業(yè)通常以服務(wù)的形態(tài)持續(xù)運(yùn)行,以請(qǐng)求(request)為單位觸發(fā)計(jì)算任務(wù).例如,網(wǎng)頁(yè)搜索服務(wù)、數(shù)據(jù)庫(kù)服務(wù)、社交網(wǎng)絡(luò)服務(wù)等[16,17],運(yùn)行往往持續(xù)數(shù)周甚至數(shù)月,因此在線作業(yè)也被稱為長(zhǎng)服務(wù)(long runing service)[18].

(2)資源使用呈現(xiàn)動(dòng)態(tài)變化.在線作業(yè)的資源使用量與用戶并發(fā)請(qǐng)求量呈正相關(guān),會(huì)伴隨用戶并發(fā)請(qǐng)求量發(fā)生動(dòng)態(tài)變化.圖1 所示為國(guó)內(nèi)某互聯(lián)網(wǎng)公司的在線作業(yè)計(jì)算節(jié)點(diǎn)一個(gè)月內(nèi)的CPU 使用量變化曲線,隨著時(shí)間的推進(jìn),該作業(yè)的CPU 使用量呈現(xiàn)了明顯的以天為周期的動(dòng)態(tài)變化特征.此外,圖1 中還出現(xiàn)了多次CPU 利用率突變的現(xiàn)象,這是因?yàn)?某些社會(huì)事件,如突發(fā)熱點(diǎn)新聞、電商網(wǎng)站的促銷活動(dòng)等會(huì)導(dǎo)致用戶并發(fā)請(qǐng)求突增[19].

(3)對(duì)性能變化敏感.在線作業(yè)的性能通常決定了企業(yè)對(duì)外服務(wù)質(zhì)量,而服務(wù)質(zhì)量則直接影響企業(yè)的經(jīng)濟(jì)利益和用戶體驗(yàn).例如,Amazon 的統(tǒng)計(jì)數(shù)據(jù)顯示,Amazon 的網(wǎng)頁(yè)響應(yīng)速度慢0.1s 便會(huì)導(dǎo)致1%的用戶放棄交易[20];也有研究表明,交互式應(yīng)用的響應(yīng)時(shí)間只有在100ms 以內(nèi)時(shí)才能給用戶流暢的使用體驗(yàn)[21].因此,在線作業(yè)又被稱為延時(shí)敏感型作業(yè)(LC(latency critical)Job 或 LS(latency sensitive)Job)[13,15].

Fig.1 Static software defect prediction research framework using defect-proneness as prediction target圖1 某在線作業(yè)所在服務(wù)器CPU 使用率波動(dòng)曲線,采樣時(shí)間為1 個(gè)月

離線作業(yè).離線作業(yè)是指數(shù)據(jù)中心中優(yōu)先級(jí)較低的、對(duì)性能要求不高的批處理作業(yè),如MapReduce 作業(yè)和機(jī)器學(xué)習(xí)訓(xùn)練作業(yè)等,離線作業(yè)具有如下特點(diǎn).

(1)運(yùn)行時(shí)長(zhǎng)較短.對(duì)Google 和阿里巴巴數(shù)據(jù)中心中的離線作業(yè)運(yùn)行時(shí)長(zhǎng)統(tǒng)計(jì)后發(fā)現(xiàn)[22-25],離線作業(yè)運(yùn)行時(shí)長(zhǎng)大多位于數(shù)分鐘到數(shù)小時(shí)這一區(qū)間.因此,與運(yùn)行持續(xù)數(shù)周甚至數(shù)月的在線作業(yè)相比,離線作業(yè)的運(yùn)行時(shí)長(zhǎng)較短.

(2)計(jì)算密集.離線作業(yè)通常需要進(jìn)行大量的計(jì)算操作,數(shù)據(jù)統(tǒng)計(jì)顯示,阿里MapReduce 作業(yè)的CPU:Mem約為1:4,即每使用4G 內(nèi)存便會(huì)消耗1 個(gè)CPU 的全部計(jì)算能力;深度學(xué)習(xí)模型訓(xùn)練作業(yè)也是典型的離線作業(yè),此類作業(yè)通常需要進(jìn)行大量的梯度計(jì)算,并且通過(guò)多次迭代直至模型收斂.

(3)對(duì)性能變化不敏感.離線作業(yè)通常為批處理作業(yè),對(duì)于性能沒(méi)有嚴(yán)格的要求,可以容忍較大的運(yùn)行延遲并支持任務(wù)的失敗重啟.

Table 1 Comparisons of LC jobs and BE jobs表1 在線作業(yè)和離線作業(yè)對(duì)比

由于在線作業(yè)運(yùn)行時(shí)的低延遲要求,為保證在線作業(yè)的性能,一般采用了在線作業(yè)獨(dú)占集群的方式,避免與其他作業(yè)共享計(jì)算資源,并且為在線作業(yè)分配過(guò)量的計(jì)算資源以應(yīng)對(duì)在線作業(yè)動(dòng)態(tài)的資源需求.圖1 所示在線作業(yè)的峰值CPU 需求可達(dá)80%,為滿足其在峰值負(fù)載時(shí)的計(jì)算資源需求,采用了一個(gè)在線作業(yè)實(shí)例獨(dú)占一臺(tái)服務(wù)器的部署方式.這種部署方式導(dǎo)致在線作業(yè)集群平均資源利用率較低(服務(wù)器月平均CPU 利用率僅為20%).與此同時(shí),離線作業(yè)的規(guī)模日益擴(kuò)大,對(duì)離線集群計(jì)算資源的需求呈現(xiàn)快速增長(zhǎng),導(dǎo)致離線集群資源不足[8].因此,混部成為提升數(shù)據(jù)中心資源利用率的理想方法[26],即在保障在線作業(yè)性能的前提下,將在線集群的空閑資源分配給離線作業(yè).混部既可以滿足離線作業(yè)的資源需求,也可以提升在線集群的資源利用率,因此成為提升數(shù)據(jù)中心整體資源利用率的主流方法.

1.2 問(wèn)題與挑戰(zhàn)

由于多個(gè)作業(yè)競(jìng)爭(zhēng)共享資源(如CPU、緩存、內(nèi)存、內(nèi)存帶寬、網(wǎng)絡(luò)帶寬),導(dǎo)致作業(yè)間出現(xiàn)性能干擾[13,14].這種在離線混部作業(yè)間的資源競(jìng)爭(zhēng)及性能干擾使得混部集群作業(yè)調(diào)度與資源管理變得十分復(fù)雜.圍繞如何減少和控制在離線混部作業(yè)間的性能干擾,同時(shí)提升混部集群的資源利用率,本節(jié)總結(jié)和分析了在離線混部集群管理面臨的主要問(wèn)題與技術(shù)挑戰(zhàn).

1.2.1 在離線混部作業(yè)性能干擾問(wèn)題

在離線混部作業(yè)的性能受到諸多因素的影響,呈現(xiàn)出性能對(duì)干擾的敏感性具有動(dòng)態(tài)變化、模式多樣復(fù)雜等特點(diǎn),尤其是在超大規(guī)?；觳考褐袆?dòng)態(tài)變化的作業(yè)負(fù)載、多樣化的資源依賴以及異構(gòu)硬件架構(gòu)等使得在離線混部作業(yè)的性能難以建模,在各種干擾模式下的性能預(yù)測(cè)變得極具挑戰(zhàn)性,也增加了集群作業(yè)調(diào)度和節(jié)點(diǎn)資源管理的難度.

首先,如前所述,在線作業(yè)的工作負(fù)載具有動(dòng)態(tài)性,同一作業(yè)的性能在不同工作負(fù)載下對(duì)于干擾的敏感性并不相同,由于高工作負(fù)載時(shí)作業(yè)所需的計(jì)算資源高于其低負(fù)載時(shí)的需求,因而高負(fù)載下的在線作業(yè)對(duì)資源有更強(qiáng)的競(jìng)爭(zhēng),也對(duì)干擾更加敏感;其次,運(yùn)行在數(shù)據(jù)中心的在離線作業(yè)數(shù)量龐大且種類繁多,對(duì)關(guān)鍵資源的依賴性因其運(yùn)行邏輯不同而各異,若混合部署于同一節(jié)點(diǎn)上的在線作業(yè)與離線作業(yè)具有同樣或類似的關(guān)鍵資源依賴性,則會(huì)加劇其相互間的性能干擾;再次,節(jié)點(diǎn)上作業(yè)的細(xì)粒度資源共享主要依靠操作系統(tǒng)的資源調(diào)度機(jī)制,如分時(shí)共享或搶占式調(diào)度等,不同的資源調(diào)度機(jī)制會(huì)使得作業(yè)在運(yùn)行時(shí)具有不同的抗干擾性,例如搶占式調(diào)度可減少作業(yè)在就緒進(jìn)程等待隊(duì)列中的排隊(duì)時(shí)間,相比于分時(shí)共享的公平調(diào)度機(jī)制,搶占式調(diào)度的資源共享因其能使作業(yè)具有更好的抗干擾性而更適合于在線作業(yè);最后,隨著計(jì)算機(jī)體系結(jié)構(gòu)的發(fā)展,硬件架構(gòu)出現(xiàn)了單核、多核、異構(gòu)多核等多種架構(gòu),提供了多樣化的硬件級(jí)別的抗干擾機(jī)制,例如多核體系結(jié)構(gòu)通過(guò)增加CPU 的數(shù)量來(lái)減少作業(yè)間對(duì)于CPU 的競(jìng)爭(zhēng),支持Intel CAT(cache allocation technology)的CPU 可為不同的進(jìn)程劃分私有的L3 緩存空間,從而降低作業(yè)因競(jìng)爭(zhēng)L3 緩存資源而引起的性能干擾.這種異構(gòu)硬件架構(gòu)所帶來(lái)的抗干擾機(jī)制的多樣化更進(jìn)一步增加了在離線混部作業(yè)性能預(yù)測(cè)的難度.

1.2.2 在離線混部作業(yè)調(diào)度問(wèn)題

作為數(shù)據(jù)中心管理的關(guān)鍵技術(shù),作業(yè)調(diào)度一直是學(xué)術(shù)界和產(chǎn)業(yè)界研究的熱點(diǎn)領(lǐng)域,傳統(tǒng)作業(yè)調(diào)度研究工作側(cè)重于資源公平性[27,28]、負(fù)載均衡、提高吞吐率[29]或資源利用率等多目標(biāo).對(duì)于在離線混部作業(yè)調(diào)度而言,除了滿足這些目標(biāo)以外,在線作業(yè)與離線作業(yè)兩種類型作業(yè)的特點(diǎn)及其混合部署所帶來(lái)的必然的資源競(jìng)爭(zhēng)和性能干擾使得混部集群作業(yè)調(diào)度問(wèn)題更具有挑戰(zhàn)性.

首先,如前所述,在離線混部作業(yè)的性能受到諸多因素的影響,呈現(xiàn)出性能敏感性動(dòng)態(tài)變化、干擾模式多樣復(fù)雜等特點(diǎn),在動(dòng)態(tài)負(fù)載和復(fù)雜干擾模式下的作業(yè)性能預(yù)測(cè)模型難以構(gòu)建;其次,在離線作業(yè)調(diào)度機(jī)制需要充分考慮到在線作業(yè)與離線作業(yè)兩種類型作業(yè)的運(yùn)行特點(diǎn)和性能要求,對(duì)于離線作業(yè)而言,因其運(yùn)行時(shí)間短,并行度高,需要較高的調(diào)度吞吐率和較低的調(diào)度延時(shí);相對(duì)而言,在線作業(yè)則可接受一定程度的調(diào)度延時(shí);最后,數(shù)據(jù)中心中在線作業(yè)與離線作業(yè)的數(shù)量龐大且種類繁多,其混合部署的組合數(shù)量將呈現(xiàn)指數(shù)爆炸狀態(tài),如何在巨大的解空間中快速搜索到滿足多目標(biāo)的在線作業(yè)與離線作業(yè)混部組合,進(jìn)而進(jìn)行作業(yè)調(diào)度,是一個(gè)難題.

1.2.3 在離線作業(yè)的共享資源隔離問(wèn)題

導(dǎo)致性能干擾的一個(gè)重要原因是具有同樣或類似關(guān)鍵資源依賴性的在線作業(yè)與離線作業(yè)對(duì)共享資源的無(wú)序競(jìng)爭(zhēng).資源隔離技術(shù)通過(guò)軟件或軟硬件協(xié)同技術(shù)控制作業(yè)對(duì)資源使用的方式來(lái)降低甚至消除對(duì)資源的無(wú)序競(jìng)爭(zhēng),例如Linux CGroup 支持CPU、內(nèi)存、磁盤(pán)等資源的隔離,NUMA(non uniform memory access architecture)架構(gòu)采用多內(nèi)存通道技術(shù)減少內(nèi)存帶寬的競(jìng)爭(zhēng),Intel CAT 的Cache 隔離機(jī)制通過(guò)隔離不同作業(yè)所使用的緩存空間緩解作業(yè)在競(jìng)爭(zhēng)L3 Cache 時(shí)發(fā)生的緩存相互替換.然而,在離線混部作業(yè)的資源隔離技術(shù)仍是一個(gè)難題.

首先,現(xiàn)有體系結(jié)構(gòu)中的資源類型繁多,諸如現(xiàn)有的通用硬件在TLB 快表、L1/2 緩存、緩存帶寬、內(nèi)存帶寬、總線帶寬等諸多關(guān)鍵資源仍然缺乏對(duì)應(yīng)的軟硬件協(xié)同的資源隔離機(jī)制,尚無(wú)法實(shí)現(xiàn)應(yīng)用級(jí)隔離;其次,在目前高度復(fù)雜的硬件上通過(guò)軟件方法精準(zhǔn)控制作業(yè)對(duì)于硬件資源的競(jìng)爭(zhēng)需要同時(shí)考慮操作系統(tǒng)和硬件架構(gòu)的具體實(shí)現(xiàn),而多數(shù)商用硬件具有黑盒性,極大地增加了使用軟件方法隔離硬件資源的難度,因此具有挑戰(zhàn)性.

1.2.4 資源動(dòng)態(tài)分配問(wèn)題

在離線作業(yè)的資源需求隨作業(yè)負(fù)載而發(fā)生動(dòng)態(tài)變化[30].為保障在線作業(yè)的響應(yīng)時(shí)間并提升集群資源利用率,需根據(jù)負(fù)載的變化動(dòng)態(tài)分配相應(yīng)的資源,優(yōu)化資源配比.然而,一方面,在離線混部作業(yè)間存在的不可知且復(fù)雜的干擾會(huì)嚴(yán)重影響作業(yè)的性能;另一方面,作業(yè)資源配比的變化也會(huì)影響性能干擾的程度,進(jìn)而產(chǎn)生作業(yè)的性能變化.因此,如何在資源動(dòng)態(tài)分配過(guò)程中平衡資源利用率和作業(yè)性能也是一個(gè)難題,也稱為近年來(lái)的研究熱點(diǎn)[19].

首先,資源重分配帶來(lái)的性能干擾變化難以建模和量化,作業(yè)性能難以預(yù)測(cè)和保障.如前所述,動(dòng)態(tài)變化的作業(yè)負(fù)載、多樣化的資源依賴以及異構(gòu)硬件架構(gòu)等均會(huì)影響作業(yè)性能,使得在各種干擾條件下的性能預(yù)測(cè)變得極具挑戰(zhàn)性.資源重分配改變了作業(yè)的關(guān)鍵資源瓶頸,刷新了資源依賴關(guān)系,重置了性能對(duì)干擾的敏感度,帶來(lái)了一系列不可控的連鎖反應(yīng),更加劇了性能干擾的變化和不確定性.其次,資源類型多樣復(fù)雜,資源間存在互補(bǔ)、互替代、單向依賴、多向依賴等復(fù)雜關(guān)系,使得資源分配策略搜索空間極大,限制條件極為復(fù)雜.最后,在線作業(yè)的實(shí)時(shí)負(fù)載波動(dòng)和高性能需求要求資源動(dòng)態(tài)分配具備精準(zhǔn)和快速的特性.然而,由于復(fù)雜性能干擾導(dǎo)致作業(yè)性能難以預(yù)測(cè),依靠有限的負(fù)載變化、混部作業(yè)組合變化等信息快速做出精準(zhǔn)的資源分配決策極為困難.

2 相關(guān)研究工作

2.1 研究框架

針對(duì)上述問(wèn)題和挑戰(zhàn),本文從在離線混部作業(yè)性能干擾模型、集群層面的作業(yè)調(diào)度以及節(jié)點(diǎn)層面的資源管理這3 個(gè)方面進(jìn)行研究,如圖2 所示.

Fig.2 Research framework圖2 研究框架

性能干擾模型.為了解決在離線混部作業(yè)的性能干擾問(wèn)題,須就作業(yè)的運(yùn)行環(huán)境對(duì)性能的影響進(jìn)行建模,以預(yù)測(cè)作業(yè)在動(dòng)態(tài)負(fù)載、資源競(jìng)爭(zhēng)及干擾模式等條件下的性能,為集群作業(yè)調(diào)度和節(jié)點(diǎn)資源管理提供指導(dǎo).

集群層混部作業(yè)調(diào)度.混部作業(yè)調(diào)度所研究的內(nèi)容是作業(yè)的放置問(wèn)題,即決定作業(yè)的運(yùn)行位置.混部作業(yè)調(diào)度是一個(gè)多目標(biāo)優(yōu)化問(wèn)題,在傳統(tǒng)作業(yè)調(diào)度的優(yōu)化目標(biāo)上,還需要優(yōu)化在離線作業(yè)間的性能干擾,同時(shí)滿足在線作業(yè)的SLA,兼顧作業(yè)吞吐率等要求.

節(jié)點(diǎn)層混部作業(yè)資源管理.混部作業(yè)資源管理須:(1)為作業(yè)的運(yùn)行控制資源供給,在滿足作業(yè)資源需求的同時(shí)減少作業(yè)間的性能干擾;(2)根據(jù)作業(yè)運(yùn)行狀況預(yù)測(cè)其資源需求并做出分配策略.前者涉及到操作系統(tǒng)和硬件架構(gòu)的資源隔離技術(shù),后者則涉及資源動(dòng)態(tài)分配算法.

2.2 性能干擾模型

性能干擾模型就在離線混部作業(yè)的運(yùn)行環(huán)境對(duì)作業(yè)性能的影響進(jìn)行建模,以預(yù)測(cè)在動(dòng)態(tài)負(fù)載、資源競(jìng)爭(zhēng)及干擾模式等條件下的作業(yè)性能,為集群層面混部作業(yè)調(diào)度和節(jié)點(diǎn)層面混部資源管理提供指導(dǎo).性能干擾模型的形式化描述由式(1)給出,式(1)代表作業(yè)的性能模型,性能模型的輸入包含4 部分:作業(yè)當(dāng)前的負(fù)載load、作業(yè)當(dāng)前所面臨的來(lái)自其他作業(yè)的資源競(jìng)爭(zhēng)壓力pressure、作業(yè)當(dāng)前的資源供給res、作業(yè)運(yùn)行的硬件架構(gòu)hw,輸出則為作業(yè)j在當(dāng)前運(yùn)行環(huán)境下所能達(dá)到的性能pf.

性能干擾模型的輸出代表了作業(yè)的性能,但在線離線作業(yè)通常具有不同的性能指標(biāo),例如,在線作業(yè)的性能評(píng)價(jià)指標(biāo)通常是請(qǐng)求的響應(yīng)時(shí)間(response time,簡(jiǎn)稱RT),離線作業(yè)的性能評(píng)價(jià)通常是作業(yè)的運(yùn)行時(shí)間或作業(yè)吞吐率等指標(biāo).上述指標(biāo)與作業(yè)的具體邏輯相關(guān),可以直接反映作業(yè)真實(shí)的性能狀況,因而被多個(gè)研究工作采用,如文獻(xiàn)[13,31-34].但是獲取作業(yè)級(jí)別的性能指標(biāo)需要與具體應(yīng)用對(duì)接,具有較差的可遷移性.并且,在公有云環(huán)境或大規(guī)模數(shù)據(jù)中心中,由于作業(yè)的黑盒性或隱私條款,獲取作業(yè)級(jí)性能指標(biāo)并不可行,因此不少性能干擾模型采用了系統(tǒng)底層的性能指標(biāo)作為作業(yè)的性能指標(biāo),如描述作業(yè)在每個(gè)CPU 時(shí)鐘周期可執(zhí)行的指令數(shù)量IPC(instructions per cycle)或者CPI(cycles per instruction)、MIPS(million instructions per second).作業(yè)間的性能干擾可引起上述指標(biāo)的變化,例如一個(gè)在線作業(yè)的緩存空間被離線作業(yè)替換掉后,后續(xù)的指令在執(zhí)行過(guò)程中發(fā)生了緩存缺失(cache miss),導(dǎo)致執(zhí)行訪存指令所需的處理器周期數(shù)增加,導(dǎo)致IPC 降低.底層性能指標(biāo)由于具有通用性強(qiáng)、方便獲取等優(yōu)點(diǎn),被廣泛用于性能干擾模型中,如文獻(xiàn)[12,35-37].

性能干擾模型的第1 個(gè)參數(shù)load表示作業(yè)當(dāng)前的負(fù)載,對(duì)于在線作業(yè)的負(fù)載表現(xiàn)為當(dāng)前請(qǐng)求并發(fā)數(shù),如RPS(requests per second)和QPS(queries per second),而離線作業(yè)的負(fù)載則與作業(yè)的輸入數(shù)據(jù)規(guī)模相關(guān).性能干擾模型的第2 個(gè)參數(shù)pressure代表作業(yè)當(dāng)前面臨的資源競(jìng)爭(zhēng)壓力,即作業(yè)所遭受的性能干擾,目前關(guān)于資源競(jìng)爭(zhēng)壓力并沒(méi)有統(tǒng)一的量化標(biāo)準(zhǔn).文獻(xiàn)[14,35]采用了一個(gè)對(duì)性能敏感的程序(稱為reporter 或ruler)的運(yùn)行時(shí)間并將其運(yùn)行時(shí)間作為pressure.文獻(xiàn)[32,33]則使用當(dāng)前的內(nèi)存帶寬使用量作為pressure.文獻(xiàn)[38]則引入了服務(wù)內(nèi)部的隊(duì)列長(zhǎng)度作為pressure.第3 個(gè)參數(shù)res代表當(dāng)前分配給作業(yè)的可用資源,由一個(gè)向量表示,可包括CPU、內(nèi)存、Cache 在內(nèi)的多種共享資源.不同的性能干擾模型由于面向的場(chǎng)景不同,在參數(shù)的取值范圍上有所不同,如面向異構(gòu)集群的性能干擾模型需要在hw參數(shù)上具有多種取值,如文獻(xiàn)[39,40],而面向同構(gòu)平臺(tái)的性能模型的hw參數(shù)則為定值;面向恒定作業(yè)負(fù)載場(chǎng)景的性能干擾模型的load為定值.

建立性能干擾模型的過(guò)程可分為兩步:(1)數(shù)據(jù)獲取;(2)模型構(gòu)建.建立性能干擾模型的第1 步是獲取性能干擾數(shù)據(jù),即獲取數(shù)據(jù)集D={d1,d2,...,dn},d={load,pressure,res,hw}.在數(shù)據(jù)獲取方法上,存在基于干擾注入的數(shù)據(jù)獲取方法和基于歷史監(jiān)控?cái)?shù)據(jù)的數(shù)據(jù)獲取方法兩種.

基于干擾注入的數(shù)據(jù)獲取方法的基本思想是在作業(yè)運(yùn)行時(shí)向作業(yè)運(yùn)行環(huán)境中注入性能干擾,通過(guò)不斷改變干擾的強(qiáng)度從而獲得該作業(yè)在不同干擾下的性能變化.注入干擾的方法是在作業(yè)運(yùn)行環(huán)境中運(yùn)行一個(gè)干擾者,干擾者通常是精心設(shè)計(jì)的一個(gè)資源密集型程序,可與作業(yè)競(jìng)爭(zhēng)在多種共享資源上產(chǎn)生資源競(jìng)爭(zhēng).例如:作為作業(yè)運(yùn)行中最主要的資源——CPU 時(shí)間片,其上的干擾可以使用大量的循環(huán)語(yǔ)句來(lái)產(chǎn)生;內(nèi)存子系統(tǒng)是競(jìng)爭(zhēng)最激烈的資源之一,由于內(nèi)存子系統(tǒng)具有層次化的特點(diǎn),對(duì)于不同層次的資源競(jìng)爭(zhēng)可以通過(guò)讀寫(xiě)不同大小的數(shù)組來(lái)產(chǎn)生;文獻(xiàn)[41]總結(jié)和列舉了15 種干擾源并提出了可在多種維度上產(chǎn)生性能干擾的工具iBench.使用iBench作為干擾注入工具的研究工作有文獻(xiàn)[39,40].文獻(xiàn)[14,32,33,35]專注于內(nèi)存子系統(tǒng)上的干擾,使用了可產(chǎn)生內(nèi)存帶寬干擾的干擾者用于獲取內(nèi)存帶寬干擾和作業(yè)性能的變化關(guān)系.文獻(xiàn)[42]研究了超線程之間由于共享計(jì)算單元而引起的性能下降,并在性能模型中考慮了來(lái)自相鄰超線程的干擾.基于干擾注入的數(shù)據(jù)獲取方式理論上可以獲取作業(yè)在多種性能干擾下的性能數(shù)據(jù),但其局限性在于:(1)造成干擾的資源類型多,采樣空間大,因此獲取較為全面的性能干擾數(shù)據(jù)所需采樣時(shí)間長(zhǎng);(2)由于操作系統(tǒng)和高級(jí)程序設(shè)計(jì)語(yǔ)言屏蔽了底層的硬件細(xì)節(jié),實(shí)現(xiàn)能夠在特定資源上產(chǎn)生特定強(qiáng)度干擾的干擾者需要設(shè)計(jì)人員對(duì)體系結(jié)構(gòu)和高級(jí)程序設(shè)計(jì)語(yǔ)言具有深入的了解,因此設(shè)計(jì)和實(shí)現(xiàn)有效的干擾者具有一定的難度.

基于歷史監(jiān)控?cái)?shù)據(jù)的數(shù)據(jù)獲取方法從作業(yè)運(yùn)行產(chǎn)生的監(jiān)控?cái)?shù)據(jù)中提取出性能干擾模型所需要的數(shù)據(jù)集.在數(shù)據(jù)中心的運(yùn)行過(guò)程中,積累了大量關(guān)于作業(yè)運(yùn)行的監(jiān)控?cái)?shù)據(jù),由于數(shù)據(jù)中心作業(yè)的動(dòng)態(tài)性,作業(yè)在長(zhǎng)期運(yùn)行過(guò)程中會(huì)遭受不同程度的性能干擾,因此歷史監(jiān)控?cái)?shù)據(jù)中蘊(yùn)含著可用于構(gòu)造性能干擾模型的數(shù)據(jù).基于歷史監(jiān)控?cái)?shù)據(jù)的數(shù)據(jù)方法具有如下優(yōu)點(diǎn):(1)無(wú)需運(yùn)行作業(yè),避免了額外的資源消耗和時(shí)間開(kāi)銷;(2)數(shù)據(jù)易獲取;(3)數(shù)據(jù)量大.但是該方法同樣存在著如下局限性:(1)靈活性差,只能獲取歷史監(jiān)控?cái)?shù)據(jù)中監(jiān)控的資源,如需新增監(jiān)控維度則需要重新積累歷史數(shù)據(jù);(2)無(wú)法獲取從未運(yùn)行過(guò)的新作業(yè);(3)適用范圍有限,僅適用于作業(yè)運(yùn)行環(huán)境動(dòng)態(tài)性高、資源競(jìng)爭(zhēng)程度變化范圍大的集群,而對(duì)于作業(yè)運(yùn)行環(huán)境穩(wěn)定的集群,如在線獨(dú)占集群的部署策略,則由于作業(yè)運(yùn)行環(huán)境缺乏足夠的性能干擾而無(wú)法獲得較為全面的性能干擾數(shù)據(jù).

Table 2 Comparisons of performance interference models表2 性能干擾模型對(duì)比

獲取到性能干擾數(shù)據(jù)后,進(jìn)入性能干擾模型構(gòu)建階段.目前性能干擾模型的構(gòu)建方法主要包括基于統(tǒng)計(jì)方法和基于機(jī)器學(xué)習(xí)兩種.基于統(tǒng)計(jì)的方法通過(guò)數(shù)理統(tǒng)計(jì)求得模型中各變量的變化關(guān)系,如文獻(xiàn)[14,35]建立了描述資源競(jìng)爭(zhēng)壓力(使用reporter 測(cè)量得到)和作業(yè)性能的映射關(guān)系,稱為“敏感函數(shù)(sensitive function)”;文獻(xiàn)[43]使用統(tǒng)計(jì)模型建立了內(nèi)存帶寬和作業(yè)性能的變化關(guān)系;文獻(xiàn)[37]則通過(guò)構(gòu)建作業(yè)和作業(yè)之間的混部運(yùn)行性能的二維表,通過(guò)查表的方式即可實(shí)現(xiàn)性能干擾的預(yù)測(cè).基于統(tǒng)計(jì)方法的優(yōu)點(diǎn)是:(1)計(jì)算量小,模型構(gòu)建和更新速度快;(2)可解釋性強(qiáng),便于優(yōu)化.但其局限性在于:(1)模型的設(shè)計(jì)需要先驗(yàn)知識(shí),構(gòu)造和優(yōu)化具有一定的難度;(2)當(dāng)數(shù)據(jù)維度增多時(shí)傳統(tǒng)的統(tǒng)計(jì)方法無(wú)法適用.隨著機(jī)器學(xué)習(xí)方法的發(fā)展,研究人員嘗試將機(jī)器學(xué)習(xí)模型應(yīng)用于性能干擾模型,采用了諸如隨機(jī)森林回歸模型[31]、協(xié)同過(guò)濾算法[39,40]、線性回歸[32,33]、聚類算法[12,36]、深度神經(jīng)網(wǎng)絡(luò)[38,44]等方法完成從作業(yè)運(yùn)行時(shí)信息到作業(yè)性能的映射,基于機(jī)器學(xué)習(xí)算法建立的性能干擾模型可以學(xué)習(xí)到人類無(wú)法察覺(jué)的特征,并且具有良好的預(yù)測(cè)結(jié)果.缺點(diǎn)是:(1)需要高質(zhì)量的訓(xùn)練數(shù)據(jù);(2)缺乏可解釋性,難以優(yōu)化;(3)在建立模型時(shí)需要較長(zhǎng)的訓(xùn)練時(shí)間和計(jì)算開(kāi)銷.

2.3 在離線混部作業(yè)調(diào)度

作業(yè)調(diào)度是數(shù)據(jù)中心和云計(jì)算領(lǐng)域的研究熱點(diǎn),在離線混部作業(yè)向傳統(tǒng)的作業(yè)調(diào)度提出了新的挑戰(zhàn).本節(jié)圍繞第1.2.2 節(jié)中總結(jié)的3 點(diǎn)挑戰(zhàn),討論近年來(lái)在離線混部作業(yè)調(diào)度領(lǐng)域的相關(guān)研究工作.

與傳統(tǒng)作業(yè)調(diào)度相比,在離線混部作業(yè)調(diào)度需要考慮如何放置待調(diào)度作業(yè)使得作業(yè)間的性能干擾最小,尤其是對(duì)在線作業(yè)的性能干擾最小.這就需要調(diào)度器從集群的所有節(jié)點(diǎn)中篩選出待調(diào)度作業(yè)對(duì)其上運(yùn)行的在線作業(yè)性能干擾最小的節(jié)點(diǎn).本文總結(jié)了篩選節(jié)點(diǎn)的兩種常用方法.

(1)基于性能模型篩選節(jié)點(diǎn).該方法首先對(duì)在線作業(yè)建立性能模型,進(jìn)而使用性能干擾模型來(lái)預(yù)測(cè)混部后作業(yè)所能達(dá)到的性能指標(biāo),通過(guò)搜索的方法尋找產(chǎn)生干擾較小的節(jié)點(diǎn).例如:文獻(xiàn)[14,34]在使用性能干擾模型預(yù)測(cè)不同作業(yè)混部運(yùn)行時(shí)的性能,以預(yù)測(cè)數(shù)據(jù)為依據(jù)判斷該混部作業(yè)組合是否“安全”(“安全”的混部組合是指混部組合中的每個(gè)作業(yè)都能達(dá)到其要求的性能指標(biāo));文獻(xiàn)[28,39,40,45]使用協(xié)同過(guò)濾模型預(yù)測(cè)一個(gè)作業(yè)與其他作業(yè)混部時(shí)所能達(dá)到的性能,進(jìn)而使用貪心算法搜索作業(yè)的最佳運(yùn)行位置.使用預(yù)訓(xùn)練的性能干擾模型作為調(diào)度的依據(jù)取得了較好的效果,例如文獻(xiàn)[14]在保證在線作業(yè)QoS(quality of service)的情況下提升了50%～90%的集群整體資源利用率;文獻(xiàn)[39]可以保持52%的作業(yè)的QoS 不被影響,而另外33%的作業(yè)的QoS 波動(dòng)低于10%.雖然可以有效地避免作業(yè)之間的性能干擾,但是該方法依賴了預(yù)構(gòu)建的性能模型,而獲取性能干擾數(shù)據(jù)和構(gòu)建性能模型所帶來(lái)的開(kāi)銷是不可忽略的問(wèn)題;

(2)基于空閑資源篩選節(jié)點(diǎn).由于干擾和資源的相關(guān)性,空閑資源多的節(jié)點(diǎn)意味著該節(jié)點(diǎn)目前負(fù)載較少,因而有可能承受更多的資源競(jìng)爭(zhēng).文獻(xiàn)[46,47]通過(guò)預(yù)測(cè)未來(lái)一段時(shí)間集群的空閑資源數(shù)據(jù),進(jìn)而用于作業(yè)調(diào)度;文獻(xiàn)[48]提出一種作業(yè)偷取機(jī)制,當(dāng)在線作業(yè)集群位于較低負(fù)載時(shí)可從待運(yùn)行離線作業(yè)隊(duì)列中調(diào)度一部分作業(yè)至在線集群運(yùn)行;文獻(xiàn)[49]在調(diào)度時(shí)首先對(duì)作業(yè)的CPU 和I/O 資源需求進(jìn)行聚類,然后在作業(yè)間進(jìn)行資源的匹配,進(jìn)而完成調(diào)度.根據(jù)作業(yè)資源調(diào)度簡(jiǎn)單實(shí)用,因此適合在大規(guī)模混部系統(tǒng)中使用[9,50].本文在第2.2 節(jié)中指出,作業(yè)間的性能干擾還與作業(yè)本身資源的使用特征相關(guān),因此僅考慮將作業(yè)調(diào)度至空閑資源多的節(jié)點(diǎn)并不能完全保證該節(jié)點(diǎn)上在線作業(yè)的QoS,因此仍存在一定的風(fēng)險(xiǎn).

在離線混部調(diào)度不僅要減少作業(yè)間的性能干擾,還要滿足傳統(tǒng)作業(yè)調(diào)度中存在的資源公平性、作業(yè)資源需求、集群負(fù)載均衡、集群吞吐率等多個(gè)優(yōu)化目標(biāo),為解決在離線混部作業(yè)調(diào)度面臨的多目標(biāo)優(yōu)化問(wèn)題,相關(guān)工作中使用了3 類算法.

(1)啟發(fā)式算法.基于專家直觀經(jīng)驗(yàn)構(gòu)造算法用于尋找最優(yōu)調(diào)度結(jié)果,啟發(fā)式算法由于其簡(jiǎn)單直觀,易于理解和修改,被多種在離線混部作業(yè)調(diào)度算法所采用,如文獻(xiàn)[34,39,40,48,49];文獻(xiàn)[14]通過(guò)性能干擾模型預(yù)測(cè)作業(yè)在每個(gè)機(jī)器上運(yùn)行時(shí)產(chǎn)生的干擾,然后尋找干擾最小的節(jié)點(diǎn)作為作業(yè)的部署節(jié)點(diǎn).文獻(xiàn)[52]將博弈論應(yīng)用于在離線混部作業(yè)調(diào)度,使用Shapley 算法尋找作業(yè)和節(jié)點(diǎn)之間穩(wěn)定的婚姻匹配組合(如果A喜歡b的程度比喜歡自己的配偶更高,并且b同樣對(duì)A的喜好程度比自己的配偶更高,則他們很可能組成新的家庭,這樣的組合是不穩(wěn)定婚姻,不存在不穩(wěn)定婚姻的組合被稱為穩(wěn)定婚姻組合),在保證作業(yè)性能的同時(shí)保證資源分配的公平性.啟發(fā)式算法的局限性在于:(a)當(dāng)需要優(yōu)化的目標(biāo)較多時(shí),調(diào)度問(wèn)題的復(fù)雜度上升,設(shè)計(jì)兼顧多個(gè)目標(biāo)的啟發(fā)式算法具有一定的難度;(b)啟發(fā)式算法難以保證算法給出的解是全局最優(yōu)解;

(2)打分規(guī)則,當(dāng)調(diào)度優(yōu)化目標(biāo)較多時(shí),對(duì)每個(gè)目標(biāo)設(shè)定量化規(guī)則,并使用這些規(guī)則對(duì)每個(gè)節(jié)點(diǎn)進(jìn)行打分,將最終的加權(quán)分?jǐn)?shù)作為節(jié)點(diǎn)最終得分,最后將作業(yè)調(diào)度至得分最高的節(jié)點(diǎn).常見(jiàn)的打分規(guī)則有:根據(jù)負(fù)載打分,負(fù)載最低時(shí)節(jié)點(diǎn)得分為10,滿負(fù)載時(shí)得分為0 等.節(jié)點(diǎn)的最終得分是所有規(guī)則的得分加權(quán)和,調(diào)度算法選擇得分最高的節(jié)點(diǎn)作為調(diào)度決策,基于打分規(guī)則的調(diào)度算法有文獻(xiàn)[47,52].該方法的優(yōu)點(diǎn)是易于擴(kuò)展(如果有新的優(yōu)化目標(biāo)只需添加新的打分規(guī)則即可),計(jì)算開(kāi)銷低,但其局限性在于:(a)每個(gè)規(guī)則的權(quán)重作為調(diào)度算法的超參數(shù),對(duì)調(diào)度結(jié)果影響較大,尋找最佳的超參數(shù)設(shè)置需要經(jīng)過(guò)不斷的調(diào)試;(b)基于打分規(guī)則的調(diào)度算法同樣難以保證算法給出的解是全局最優(yōu)解;

(3)整數(shù)線性規(guī)劃.作業(yè)調(diào)度問(wèn)題可以抽象為組合優(yōu)化問(wèn)題,而整數(shù)線性規(guī)劃問(wèn)題(integer linear program,簡(jiǎn)稱ILP)作為組合優(yōu)化的一種解決方法,可用于解決作業(yè)調(diào)度問(wèn)題.文獻(xiàn)[18]通過(guò)對(duì)減少親和性違反、最大化成功調(diào)度的作業(yè)數(shù)量、最小化資源碎片、集群負(fù)載均衡、最大化資源利用率等多種目標(biāo)進(jìn)行量化后,并使用加權(quán)的方式將多個(gè)優(yōu)化目標(biāo)統(tǒng)一在一個(gè)全局目標(biāo)函數(shù)中,使用CPLEX 優(yōu)化器求解.基于整數(shù)線性規(guī)劃的調(diào)度算法的局限性在于:(a)算法開(kāi)銷較大,文獻(xiàn)[18]通過(guò)實(shí)驗(yàn)證明,在同等規(guī)模下,整數(shù)線性規(guī)劃算法的求解時(shí)間開(kāi)銷均高于啟發(fā)式算法和基于打分規(guī)則的調(diào)度算法;(b)目標(biāo)函數(shù)的構(gòu)造對(duì)調(diào)度質(zhì)量至關(guān)重要,對(duì)多個(gè)優(yōu)化目標(biāo)進(jìn)行量化表示具有一定的難度.

混部作業(yè)調(diào)度算法對(duì)比見(jiàn)表3.

Table 3 Comparisons of hybrid job scheduling algorithms表3 混部作業(yè)調(diào)度算法對(duì)比

調(diào)度性能方面,當(dāng)集群規(guī)模較小時(shí)使用集中式調(diào)度(centralized scheduling)即可滿足作業(yè)對(duì)于調(diào)度延時(shí)的要求,集中式調(diào)度的特點(diǎn)是所有作業(yè)由一個(gè)中央調(diào)度器進(jìn)行調(diào)度,該方法的優(yōu)點(diǎn)是全局信息共享,可獲得較好的調(diào)度質(zhì)量,采用集中式調(diào)度的在離線混部作業(yè)調(diào)度算法有文獻(xiàn)[14,18,34,40,43,47,49,51];當(dāng)集群規(guī)模逐步擴(kuò)大時(shí),中央調(diào)度器成為作業(yè)調(diào)度的性能瓶頸,分布式調(diào)度(distributed schedulig)和層次化調(diào)度(hierachical scheduling)采用分治的思想,使用多個(gè)調(diào)度器共同承擔(dān)作業(yè)調(diào)度的壓力.分布式調(diào)度是指在一個(gè)集群中同時(shí)運(yùn)行多個(gè)調(diào)度器,每個(gè)調(diào)度器只負(fù)責(zé)將作業(yè)調(diào)度至集群中的部分節(jié)點(diǎn),可以實(shí)現(xiàn)并發(fā)作業(yè)調(diào)度.分布式調(diào)度的優(yōu)點(diǎn)是可用性和吞吐率高,局限性在于各調(diào)度器無(wú)法感知集群的全局信息,因此可能產(chǎn)生次優(yōu)的調(diào)度決策.層次化調(diào)度是集中式調(diào)度和分布式調(diào)度的折中方案,層次化調(diào)度通常設(shè)置兩層調(diào)度器,作業(yè)首先由頂層調(diào)度器調(diào)度至底層調(diào)度器,再由底層調(diào)度器將作業(yè)調(diào)度至計(jì)算節(jié)點(diǎn).每個(gè)底層調(diào)度器只管理一部分計(jì)算節(jié)點(diǎn),因此縮小了調(diào)度算法的搜索空間.文獻(xiàn)[39]采用了層次化的調(diào)度方法;文獻(xiàn)[48]采取了集中式化調(diào)度和分布式調(diào)度相結(jié)合的調(diào)度方法,在線作業(yè)由集中式調(diào)度器調(diào)度以獲得較高的調(diào)度質(zhì)量,離線作業(yè)則由分布式調(diào)度器調(diào)度以獲得較短的調(diào)度延時(shí).

2.4 在離線混部作業(yè)資源管理

本節(jié)詳細(xì)介紹在離線混部作業(yè)資源管理中的資源隔離技術(shù)和資源動(dòng)態(tài)分配的相關(guān)研究工作.

2.4.1 資源隔離技術(shù)

混部集群?jiǎn)蝹€(gè)節(jié)點(diǎn)通常會(huì)部署多個(gè)作業(yè),如Google 的混部集群有50%的節(jié)點(diǎn)同時(shí)運(yùn)行超過(guò)9 個(gè)作業(yè)[12].這些作業(yè)在運(yùn)行過(guò)程中依賴系統(tǒng)中的多種共享資源,進(jìn)而產(chǎn)生共享資源競(jìng)爭(zhēng).目前解決共享資源競(jìng)爭(zhēng)的主要方法是通過(guò)限制作業(yè)對(duì)于共享資源的使用量,進(jìn)而減少作業(yè)之間在使用共享資源時(shí)發(fā)生沖突的可能性.但是,根據(jù)排隊(duì)論原理,多個(gè)作業(yè)在競(jìng)爭(zhēng)同一資源時(shí)的排隊(duì)時(shí)間是影響作業(yè)性能的重要因素,例如多個(gè)作業(yè)同時(shí)競(jìng)爭(zhēng)CPU、內(nèi)存帶寬、網(wǎng)絡(luò)帶寬等資源,在這種情況下僅對(duì)于作業(yè)做資源使用量限制并不能完全消除作業(yè)間的資源競(jìng)爭(zhēng),因此還需要對(duì)作業(yè)進(jìn)行優(yōu)先級(jí)劃分以減少高優(yōu)先級(jí)作業(yè)在競(jìng)爭(zhēng)共享資源時(shí)的排隊(duì)時(shí)間(通常在線作業(yè)會(huì)被分配高優(yōu)先級(jí)).本文根據(jù)共享資源在系統(tǒng)中的層次將資源隔離技術(shù)分為操作系統(tǒng)層的資源隔離技術(shù)和硬件層的資源隔離技術(shù).

操作系統(tǒng)層的資源隔離技術(shù)對(duì)操作系統(tǒng)中的共享資源進(jìn)行隔離,如:

(1)CPU 時(shí)間片資源.為解決多個(gè)作業(yè)對(duì)于CPU 的競(jìng)爭(zhēng),最直接的方法是利用多核體系結(jié)構(gòu)的特性(如圖3所示),將不同的作業(yè)綁定在不同的CPU 上運(yùn)行.但是作業(yè)獨(dú)占CPU 的部署方式會(huì)導(dǎo)致較低的CPU 利用率,進(jìn)一步提升CPU 利用率須運(yùn)行更多的作業(yè)并在多個(gè)作業(yè)間共享CPU.Linux CGroup 提供了CPU Share 和CPU Quota 機(jī)制,可通過(guò)操作系統(tǒng)的進(jìn)程調(diào)度機(jī)制限制作業(yè)單位時(shí)間內(nèi)可使用的CPU 時(shí)間片長(zhǎng)度;CPU 上的優(yōu)先級(jí)劃分則表現(xiàn)為進(jìn)程優(yōu)先級(jí)(如進(jìn)程的Nice 值),文獻(xiàn)[53-55]在進(jìn)程調(diào)度中增加了搶占機(jī)制,即在線作業(yè)可搶占離線作業(yè)的CPU 時(shí)間片,增強(qiáng)了在線作業(yè)與離線作業(yè)共享CPU 時(shí)的抗干擾性.

(2)網(wǎng)絡(luò)帶寬資源.網(wǎng)絡(luò)帶寬資源作為互聯(lián)網(wǎng)基礎(chǔ)設(shè)施中的核心資源,被在線和離線作業(yè)高度依賴.在線作業(yè)需要通過(guò)網(wǎng)絡(luò)接收用戶請(qǐng)求,處理完成后再通過(guò)網(wǎng)絡(luò)將結(jié)果發(fā)送給用戶,因此網(wǎng)絡(luò)帶寬競(jìng)爭(zhēng)會(huì)引起在線作業(yè)發(fā)送網(wǎng)絡(luò)包時(shí)排隊(duì)時(shí)間的上升,進(jìn)而影響在線作業(yè)的服務(wù)質(zhì)量;離線作業(yè)在處理數(shù)據(jù)前首先需要通過(guò)網(wǎng)絡(luò)讀取大量數(shù)據(jù),如MapReduce 作業(yè)需要從遠(yuǎn)端HDFS 讀取數(shù)據(jù).因此,離線作業(yè)會(huì)在網(wǎng)絡(luò)帶寬上產(chǎn)生資源競(jìng)爭(zhēng).在MapReduce 與Memcached 的混部實(shí)驗(yàn)中,MapReduce 在數(shù)據(jù)讀取階段所產(chǎn)生的網(wǎng)絡(luò)帶寬競(jìng)爭(zhēng)會(huì)使Memcached 的延遲上升83 倍[56].網(wǎng)絡(luò)帶寬資源隔離目前存在兩種方法:(a)帶寬劃分,即為每個(gè)作業(yè)設(shè)定最大網(wǎng)絡(luò)帶寬限制以防止作業(yè)過(guò)度使用網(wǎng)絡(luò)帶寬而引起過(guò)度的資源競(jìng)爭(zhēng),采用這種方法的有文獻(xiàn)[57-59];(b)網(wǎng)絡(luò)包優(yōu)先級(jí)劃分,網(wǎng)絡(luò)包優(yōu)先級(jí)劃分方法的主要思想是高優(yōu)先級(jí)作業(yè)發(fā)送的網(wǎng)絡(luò)包可以直接越過(guò)低優(yōu)先級(jí)作業(yè)的發(fā)送隊(duì)列,可有效減少高優(yōu)先級(jí)作業(yè)網(wǎng)絡(luò)包的排隊(duì)時(shí)長(zhǎng),如文獻(xiàn)[55,60-62].

(3)磁盤(pán)I/O 帶寬資源.Linux CGroup 提供了作業(yè)級(jí)別的磁盤(pán)I/O 控制,可限制作業(yè)的最大磁盤(pán)I/O 帶寬使用量.

Fig.3 Classical multi-cores memory architecuture and recent Intel CPU microarchitecutre[63]圖3 經(jīng)典多核存儲(chǔ)體系結(jié)構(gòu)與Intel CascadeLake 微架構(gòu)[63]

硬件層的資源隔離技術(shù)通過(guò)軟硬件協(xié)同技術(shù)從協(xié)調(diào)多個(gè)作業(yè)在硬件資源上的競(jìng)爭(zhēng),減緩甚至消除多個(gè)作業(yè)在硬件資源上的相互干擾.目前硬件層的資源隔離技術(shù)涉及的資源包括:

(1)內(nèi)存通道.內(nèi)存通道(memory channel)是競(jìng)爭(zhēng)激烈的共享資源之一,對(duì)作業(yè)的性能影響巨大[64-66].目前數(shù)據(jù)中心中所使用的微架構(gòu)通常采用了多通道設(shè)計(jì),如圖3(右)所示的Intel Cascade Lake 架構(gòu)采用了6 通道設(shè)計(jì),可同時(shí)支持6 個(gè)CPU 獨(dú)立地訪問(wèn)內(nèi)存.多個(gè)CPU 在單個(gè)內(nèi)存通道上的訪問(wèn)過(guò)程可用排隊(duì)模型描述,單次內(nèi)存訪問(wèn)請(qǐng)求的完成時(shí)間Tmem_req=TQueue+TR/W,其中,TQueue代表請(qǐng)求在等待內(nèi)存通道的排隊(duì)時(shí)間,TR/W代表內(nèi)存的存取時(shí)間,通常為定值;排隊(duì)時(shí)間TQueue則取決于隊(duì)列長(zhǎng)度,即隊(duì)列中位于該請(qǐng)求之前的請(qǐng)求個(gè)數(shù).因此,當(dāng)一個(gè)作業(yè)占用過(guò)多的內(nèi)存帶寬時(shí),會(huì)使同一時(shí)段內(nèi)其他作業(yè)的訪存請(qǐng)求的排隊(duì)時(shí)間變長(zhǎng),從而產(chǎn)生性能干擾.在馮諾依曼體系結(jié)構(gòu)中,內(nèi)存作為核心資源,被所有程序所依賴,因此從CPU 到內(nèi)存的內(nèi)存帶寬資源對(duì)程序至關(guān)重要.但對(duì)于內(nèi)存帶寬上的干擾隔離目前的硬件缺乏相應(yīng)的機(jī)制,因此,文獻(xiàn)[67]提出了一種基于反饋機(jī)制的內(nèi)存帶寬保留技術(shù)MemGuard,將內(nèi)存帶寬區(qū)分為在線作業(yè)和離線作業(yè)兩部分,使用中斷機(jī)制控制作業(yè)訪存請(qǐng)求的發(fā)送速率,進(jìn)而間接控制內(nèi)存帶寬.但是該方法的局限性在于其只能控制單個(gè)CPU 核心的帶寬,對(duì)于共享CPU 的作業(yè)則不適用.文獻(xiàn)[68]提出了一種動(dòng)態(tài)調(diào)整作業(yè)訪存優(yōu)先級(jí)的方法,實(shí)現(xiàn)了內(nèi)存帶寬上的動(dòng)態(tài)優(yōu)先級(jí)控制;

(2)LLC(last level cache)緩存.緩存資源作為影響作業(yè)性能的重要資源,其上的干擾同樣不可忽略.多個(gè)作業(yè)在共享緩存時(shí)可能出現(xiàn)相互替換的現(xiàn)象,LLC 失效時(shí)原本訪存指令的執(zhí)行時(shí)間將從15ns 上升至70ns,假設(shè)CPU 主頻為3Ghz,則一條訪存指令需要多消耗200 多個(gè)周期才能完成[69].消除此類干擾的方法是使用資源劃分技術(shù),在物理上劃分多個(gè)作業(yè)對(duì)共享資源的使用.圖3(左)所示為經(jīng)典的多核體系結(jié)構(gòu),多個(gè)CPU 共享了LLC,運(yùn)行于不同CPU 上的作業(yè)會(huì)在LLC 上發(fā)生競(jìng)爭(zhēng),圖3(右)所示的Intel Cascade Lake 微架構(gòu),通過(guò)為每個(gè)核設(shè)置獨(dú)立的LLC 以減少核間對(duì)于LLC 的資源競(jìng)爭(zhēng);但是,同一CPU上的多個(gè)作業(yè)在混部運(yùn)行時(shí)仍然會(huì)出現(xiàn)緩存相互替換問(wèn)題,因此需要作業(yè)級(jí)別的緩存劃分技術(shù).為了實(shí)現(xiàn)作業(yè)級(jí)別的緩存劃分,Intel 提出了RDT 技術(shù)[70],其中,CAT(cache allocation technology)[71]可為進(jìn)程或者CGroup 分配私有的緩存空間,避免緩存相互替換;

(3)緩存帶寬.RDT 技術(shù)中的MBA(memory bandwidth allocation)提供了作業(yè)級(jí)別的L2 Cache 帶寬劃分(即L2 與L3 緩存之間的帶寬),RDT 技術(shù)僅在Intel 較新型號(hào)的處理器上可以使用.

資源隔離技術(shù)降低了多個(gè)作業(yè)在競(jìng)爭(zhēng)的共享資源時(shí)的相互干擾,隨著操作系統(tǒng)和硬件架構(gòu)的不斷更新和發(fā)展,出現(xiàn)了越來(lái)越多的軟件或軟硬件協(xié)同的資源隔離技術(shù),如GPU 隔離技術(shù)[72].但是,由于硬件結(jié)構(gòu)的復(fù)雜性,在某些關(guān)鍵資源上仍然缺乏通用且有效的資源隔離技術(shù),如TLB 快表、L1/2 緩存、總線帶寬等,有待進(jìn)一步深入研究加以解決.

2.4.2 資源動(dòng)態(tài)分配算法

現(xiàn)有的操作系統(tǒng)和虛擬化技術(shù)提供了一系列資源隔離技術(shù),可在作業(yè)運(yùn)行時(shí)動(dòng)態(tài)調(diào)整該作業(yè)的可用資源.例如:Linux 提供的CGroup 提供了包括CPU、內(nèi)存、磁盤(pán)I/O、網(wǎng)絡(luò)I/O 等多種資源在內(nèi)的資源彈性伸縮機(jī)制;多數(shù)商用CPU 提供了動(dòng)態(tài)調(diào)節(jié)處理器頻率的功能(dynamic voltage and frequency scaling,簡(jiǎn)稱DVFS),如Intel系列處理器[73];緩存方面,Intel 公司推出了CAT 技術(shù),可為作業(yè)分配私有緩存并支持運(yùn)行時(shí)修改作業(yè)可用的緩存容量.以現(xiàn)有資源隔離技術(shù)為基礎(chǔ),研究人員研究了資源動(dòng)態(tài)分配算法,在作業(yè)運(yùn)行時(shí)動(dòng)態(tài)調(diào)整各個(gè)作業(yè)對(duì)于共享資源的使用量,進(jìn)而實(shí)現(xiàn)控制和減少作業(yè)間性能干擾,提升作業(yè)運(yùn)行效率等目標(biāo).圖4 所示為資源動(dòng)態(tài)分配算法的基本工作流,作業(yè)在運(yùn)行過(guò)程中所產(chǎn)生的監(jiān)控?cái)?shù)據(jù)被輸入到資源動(dòng)態(tài)分配算法,算法結(jié)合作業(yè)性能干擾模型給出資源動(dòng)態(tài)調(diào)整決策(如增加資源、減少資源、遷移作業(yè)等操作),資源動(dòng)態(tài)調(diào)整決策經(jīng)資源隔離技術(shù)修改作業(yè)的資源分配,往復(fù)循環(huán)直至作業(yè)結(jié)束.

Fig.4 Taxonomy of dynamic resource management algorithms圖4 資源動(dòng)態(tài)分配算法基本工作流

從算法目標(biāo)的角度,可將資源動(dòng)態(tài)分配算法分為解決干擾和預(yù)防干擾兩種.以解決干擾為目標(biāo)的資源動(dòng)態(tài)分配算法首先持續(xù)監(jiān)控在線作業(yè)的性能指標(biāo)并判斷是否發(fā)生性能干擾,如果發(fā)生,則需要?jiǎng)討B(tài)調(diào)整在離線作業(yè)的資源以減少性能干擾,防止在線作業(yè)的性能持續(xù)受到影響.解決干擾的相關(guān)研究有:

文獻(xiàn)[12]中CPI2 通過(guò)數(shù)據(jù)分析發(fā)現(xiàn)了在線作業(yè)CPI 和在線作業(yè)RT 的相關(guān)性,因此可以使用硬件級(jí)別的指標(biāo)CPI 作為性能指標(biāo),通過(guò)監(jiān)控和檢測(cè)CPI 的波動(dòng)判斷作業(yè)是否被干擾,檢測(cè)到干擾后使用干擾模型識(shí)別干擾者,最后使用限制干擾者CPU 或者殺死干擾者解決干擾.該方法的局限性在于:(1)整個(gè)系統(tǒng)的運(yùn)行效率依賴于干擾模型對(duì)于干擾者的識(shí)別準(zhǔn)確率;(2)僅限制干擾者的CPU 資源而忽略了其他共享資源會(huì)導(dǎo)致無(wú)法有效地找到干擾源,因此無(wú)法準(zhǔn)確、有效地處理其他資源上的性能干擾問(wèn)題.

文獻(xiàn)[36]提出了資源管理框架DeepDive,通過(guò)監(jiān)控底層的性能指標(biāo)(如CPI)預(yù)測(cè)VM 之間的性能干擾,并識(shí)別造成干擾的VM,隨后采用遷移的方法將干擾者遷移到其他節(jié)點(diǎn).實(shí)驗(yàn)證明了DeepDive 中的干擾預(yù)測(cè)準(zhǔn)確率高達(dá)90%以上.但是DeepDive 針對(duì)干擾采取虛擬機(jī)遷移的技術(shù)可能會(huì)使某些資源競(jìng)爭(zhēng)較高的容器被反復(fù)遷移,考慮到遷移容器的開(kāi)銷相對(duì)較高,反復(fù)遷移可能會(huì)引起系統(tǒng)抖動(dòng).

Table 4 Comparisons of resource dynamic allocation algorithm表4 資源動(dòng)態(tài)分配算法對(duì)比

文獻(xiàn)[13]提出了Heracles,其核心思想是獨(dú)立地控制多個(gè)維度的資源,在多個(gè)作業(yè)混部運(yùn)行時(shí)使得每種資源的使用率不超過(guò)指定閾值.Heracles 使用CGroups 提供的CPU Set 隔離CPU 資源,使用Intel 處理器提供的CAT技術(shù)實(shí)現(xiàn)緩存動(dòng)態(tài)劃分,內(nèi)存帶寬由于沒(méi)有有效的控制技術(shù),則通過(guò)使用調(diào)整CPU 配額的方式間接地控制內(nèi)存帶寬.Heracles 通過(guò)DVFS 動(dòng)態(tài)調(diào)控CPU 的運(yùn)行頻率,網(wǎng)絡(luò)帶寬則使用Linux 系統(tǒng)提供的traffic control 進(jìn)行作業(yè)的帶寬限制.Heracles 采取了兩層結(jié)構(gòu),頂層控制器基于SLO 監(jiān)控?cái)?shù)據(jù)控制離線作業(yè)是否可以增長(zhǎng),底層資源控制器根據(jù)具體的資源使用量增加或者減少作業(yè)的資源配額.實(shí)驗(yàn)中,Heracles 提升了機(jī)器的資源利用率,雖然在線作業(yè)的性能降低了20%～30%,但仍然有99%的tail latency 滿足SLO 要求.Heracles 的局限性在于每個(gè)節(jié)點(diǎn)只能支持一個(gè)在線作業(yè)和多個(gè)離線作業(yè)的混部,無(wú)法在同一節(jié)點(diǎn)的不同在線作業(yè)之間分配資源.

以解決干擾為目標(biāo)的資源動(dòng)態(tài)分配算法雖然可以減少或者消除作業(yè)間的性能干擾,但是性能干擾事件已經(jīng)發(fā)生,在線作業(yè)的性能已經(jīng)受到不可挽回的損害,可能對(duì)于某些至關(guān)重要的在線作業(yè)是無(wú)法接受的.因此研究人員提出了以預(yù)防干擾為目的的資源動(dòng)態(tài)分配算法,這類算法在作業(yè)運(yùn)行時(shí)根據(jù)作業(yè)的性能變化趨勢(shì)進(jìn)行相應(yīng)的資源分配.這種方法的優(yōu)勢(shì)在于可最大化地保證作業(yè)的性能,但其也有過(guò)多分配資源從而導(dǎo)致不必要的資源浪費(fèi)的可能.相關(guān)工作包括:

文獻(xiàn)[10]提出QoS 感知的資源管理框架PARTIES,支持多個(gè)在線作業(yè)和多個(gè)離線作業(yè)混部,在作業(yè)運(yùn)行時(shí)感知并保證所有在線作業(yè)的QoS.PARTIES 動(dòng)態(tài)調(diào)整兩大類資源:(1)計(jì)算資源,包括:CPU、LLC、CPU 頻率;(2)存儲(chǔ)資源,內(nèi)存空間、磁盤(pán)帶寬.在作業(yè)運(yùn)行過(guò)程中,PARITES 持續(xù)監(jiān)控作業(yè)的請(qǐng)求響應(yīng)時(shí)間RT,然后使用預(yù)定義的狀態(tài)機(jī)決定是否應(yīng)該增加或減少資源,直到滿足作業(yè)的QoS.在PARTIES 的管理下,混部節(jié)點(diǎn)吞吐率相比于Heracles 提升了61%,并且可以支持單節(jié)點(diǎn)運(yùn)行更多的服務(wù).但其局限性在于:(1)由于其無(wú)法感知到作業(yè)的性能模型和資源偏好,可能會(huì)造成資源分配的不均衡,比如過(guò)度分配內(nèi)存給一個(gè)計(jì)算密集型作業(yè);(2)需要作業(yè)級(jí)別的RT,在公有云環(huán)境中,作業(yè)通常具有黑盒性,無(wú)法獲取作業(yè)的RT.

文獻(xiàn)[35]提出基于反饋機(jī)制的資源管理器BubbleFlux,在作業(yè)運(yùn)行時(shí)持續(xù)監(jiān)控作業(yè)的IPC,根據(jù)在線作業(yè)IPC 的大小動(dòng)態(tài)調(diào)控在線作業(yè)和離線作業(yè)的CPU 時(shí)間比例,以達(dá)到LC 作業(yè)QoS 和整體資源利用率最大化的目的.實(shí)驗(yàn)結(jié)果表明,BubbleFlux 管理下的資源利用率比Bubble Up[14]提升了2.2 倍.但是,BubbleFlux 僅能管理CPU 資源,無(wú)法處理其他資源上的資源競(jìng)爭(zhēng).

文獻(xiàn)[74]提出了PerfIso 資源管理系統(tǒng).PerfIso 管理了兩類資源以消減干擾:CPU 和磁盤(pán)I/O.在CPU 的動(dòng)態(tài)分配中,PerfIso 通過(guò)保持系統(tǒng)中持續(xù)存在空閑的核以處理在線作業(yè)的突發(fā)流量;在磁盤(pán)I/O 的隔離上,PerfIso 采用的策略是使用Defict-weighted round-robin 算法動(dòng)態(tài)調(diào)整優(yōu)先級(jí),該算法的基本思想是磁盤(pán)I/O 越多的作業(yè)優(yōu)先級(jí)越低.在實(shí)驗(yàn)中,作者將Bing 搜索服務(wù)和離線作業(yè)進(jìn)行了混部,在PerfIso 的管理下CPU 使用率最多提升到47%左右.但是該方法的局限性在于:使用隔離CPU 和預(yù)留資源的方法會(huì)使系統(tǒng)中永遠(yuǎn)存在空閑狀態(tài)的CPU,進(jìn)而限制了CPU 使用率的上限.

隨著強(qiáng)化學(xué)習(xí)的發(fā)展,也有研究人員將強(qiáng)化學(xué)習(xí)應(yīng)用于資源動(dòng)態(tài)分配算法.文獻(xiàn)[76]使用強(qiáng)化學(xué)習(xí)算法動(dòng)態(tài)調(diào)整作業(yè)的CPU 配額和CPU 的頻率.強(qiáng)化學(xué)習(xí)的優(yōu)勢(shì)在于無(wú)需人為制定規(guī)則,算法會(huì)根據(jù)預(yù)先指定的reward函數(shù)學(xué)習(xí)出最佳的策略,結(jié)合深度神經(jīng)網(wǎng)絡(luò)有著強(qiáng)大的學(xué)習(xí)能力.其局限性在于:(1)算法需要的訓(xùn)練時(shí)間長(zhǎng);(2)神經(jīng)網(wǎng)絡(luò)的黑盒性導(dǎo)致算法不易調(diào)優(yōu);(3)有限的Action 空間難以應(yīng)對(duì)復(fù)雜多變的云計(jì)算環(huán)境.

3 系統(tǒng)實(shí)例

提升集群利用率有利于降低企業(yè)數(shù)據(jù)中心的TCO(total cost of ownership,總體擁有成本),大幅度提升數(shù)據(jù)中心的成本效率.因此,在離線混部集群管理系統(tǒng)成為工業(yè)界關(guān)注的重點(diǎn)領(lǐng)域.國(guó)外方面,Google 在其集群管理系統(tǒng)Borg 中率先嘗試了大規(guī)模在離線混部[9].國(guó)內(nèi)方面,互聯(lián)網(wǎng)公司百度、騰訊、阿里均在混部集群管理系統(tǒng)上有所實(shí)踐,并開(kāi)源了相應(yīng)的數(shù)據(jù)集[78,79].本節(jié)就4 個(gè)混部系統(tǒng)實(shí)例進(jìn)行對(duì)比分析.

表5 列舉并對(duì)比了Google(Borg)、阿里(Fuxi&Sigma)、百度(Matrix)、騰訊(YARD)的在離線混部作業(yè)管理系統(tǒng).其中,“-”表示現(xiàn)有公開(kāi)數(shù)據(jù)中無(wú)相關(guān)描述.可以看到:

在性能干擾模型方面,4 個(gè)系統(tǒng)實(shí)例均未將性能干擾模型應(yīng)用于大規(guī)模實(shí)踐.本文認(rèn)為造成這一現(xiàn)狀的原因?yàn)?上述4 個(gè)混部系統(tǒng)實(shí)例均進(jìn)行了大規(guī)模部署,運(yùn)行了海量的在線作業(yè)和離線作業(yè),為這些作業(yè)構(gòu)建精準(zhǔn)的性能干擾模型所需計(jì)算開(kāi)銷過(guò)高.雖然性能干擾模型在Borg 的公開(kāi)文檔中并未提及,但其大規(guī)模作業(yè)混部環(huán)境支撐了多個(gè)性能干擾模型的研究,如文獻(xiàn)[14,35].

Table 5 Comparisons of co-location systems表5 混部系統(tǒng)實(shí)例對(duì)比

在在離線混部作業(yè)調(diào)度方面,Google 的Borg(如圖5 左所示)和騰訊的YARD 采用了統(tǒng)一調(diào)度的架構(gòu),即在線作業(yè)和離線作業(yè)由一個(gè)調(diào)度器統(tǒng)一調(diào)度,而百度Matrix 和阿里Fuxi&Sigma(如圖5 右所示)則采用了在線離線分離調(diào)度的方式,即在離線作業(yè)由各自的調(diào)度器調(diào)度(Sigma 和Fuxi 分別為阿里內(nèi)部原有的在線和離線作業(yè)管理系統(tǒng),Sorlaria 和Normandy 分別為百度內(nèi)部原有的在線和離線作業(yè)管理系統(tǒng)).在離線分離調(diào)度的架構(gòu)復(fù)用了原有系統(tǒng)的代碼,減少了工程實(shí)現(xiàn)的復(fù)雜度,但也存在著一定的局限性:(1)在離線作業(yè)調(diào)度器以及底層資源管理器信息不共享,需要引入額外的組件進(jìn)行在離線資源的協(xié)調(diào)(如Fuxi&Sigma 中的Level-0)[25];(2)系統(tǒng)架構(gòu)較統(tǒng)一調(diào)度更為復(fù)雜,每個(gè)節(jié)點(diǎn)至少運(yùn)行了3 個(gè)Agent,帶來(lái)了額外的資源開(kāi)銷.從調(diào)度算法來(lái)看,Borg 和Sigma采用了基于打分規(guī)則的調(diào)度算法,打分規(guī)則包括:根據(jù)負(fù)載高低打分、根據(jù)資源碎片量打分、根據(jù)作業(yè)優(yōu)先級(jí)組合打分等.Fuxi、Matrix、YARD 則是對(duì)YARN[4]調(diào)度算法的改進(jìn),在調(diào)度時(shí)考慮了節(jié)點(diǎn)空余資源,并使用作業(yè)畫(huà)像、節(jié)點(diǎn)畫(huà)像等預(yù)測(cè)作業(yè)的資源需求和節(jié)點(diǎn)未來(lái)可用資源.

從資源隔離技術(shù)來(lái)看,4 個(gè)混部系統(tǒng)實(shí)例均采用了多種資源隔離技術(shù).容器技術(shù)作為輕量級(jí)的虛擬化技術(shù)被廣泛使用;CPU 作為最重要的計(jì)算資源,CPU 隔離和搶占式調(diào)度成為所有混部系統(tǒng)的選擇;CAT 技術(shù)也被較多地采用;Fuxi&Sigma 支持更多資源的隔離,如磁盤(pán)、網(wǎng)絡(luò)、超線程上的資源隔離.

從資源動(dòng)態(tài)分配算法來(lái)看,基于反饋機(jī)制的資源調(diào)整算法被廣泛應(yīng)用于實(shí)際系統(tǒng)中.其基本思想是:當(dāng)在線作業(yè)的性能受到影響時(shí)殺死離線作業(yè)或動(dòng)態(tài)調(diào)整離線作業(yè)的資源配額[84].基于這一思想,Borg 采用了如下策略以降低作業(yè)間的性能干擾:(1)在線作業(yè)與物理核(physical CPU cores)綁定,并且同一個(gè)物理核只綁定一個(gè)在線作業(yè),在線作業(yè)運(yùn)行時(shí)可使用CPU 的全部資源;離線作業(yè)被允許運(yùn)行在任意核上,運(yùn)行時(shí)存在CPU 使用上限;(2)根據(jù)在線作業(yè)資源利用率變化曲線,Borg 預(yù)測(cè)并動(dòng)態(tài)調(diào)整在線作業(yè)的資源配額使得并將剩余資源分配給離線作業(yè).基于Borg 提供的在離線混部環(huán)境,Google 公司的研究人員還進(jìn)行了多種資源動(dòng)態(tài)分配算法的研究,如文獻(xiàn)[12,13,35,36];Fuxi&Sigma 則在內(nèi)存共享方面提出了彈性內(nèi)存策略,通過(guò)在線作業(yè)的負(fù)載動(dòng)態(tài)調(diào)整在離線作業(yè)各自的內(nèi)存配額.

從運(yùn)行效果來(lái)看,4 個(gè)系統(tǒng)實(shí)例對(duì)集群利用率均有明顯提升.在Borg 的管理下,Google 集群的資源使用效率大幅度提高,在15 個(gè)集群上的測(cè)試表明,Borg 最多可將一個(gè)集群壓縮為原有集群規(guī)模的65%,即:使用原有集群65%的機(jī)器便可完成原有集群的所有計(jì)算任務(wù);Fuxi&Sigma 混部系統(tǒng)將原有集群的利用率從10%提升至40%左右,節(jié)約總體成本30%以上;Matrix 則為百度節(jié)省了數(shù)萬(wàn)臺(tái)服務(wù)器的成本;YARD 集群CPU 利用率提升至45%左右,并且在實(shí)踐中將深度學(xué)習(xí)的訓(xùn)練作業(yè)與在線作業(yè)集群混部,為2018 年人工智能圍棋大賽冠軍PhoenixGo的訓(xùn)練提供了14w+CPU 的計(jì)算能力.

Fig.5 Architecture of Google Borg[9] (left)and Fuxi&Sigma[80] (right)圖5 Google Borg 系統(tǒng)架構(gòu)[9](左)與阿里Fuxi&Sigma 系統(tǒng)架構(gòu)[80](右)

4 未來(lái)研究方向展望

作為學(xué)術(shù)界和工業(yè)界研究的熱點(diǎn)領(lǐng)域,在離線混部作業(yè)調(diào)度與資源管理技術(shù)的相關(guān)研究近來(lái)得到關(guān)注,并在實(shí)際應(yīng)用中一定程度地提高了數(shù)據(jù)中心的資源利用率.但尚有許多亟待解決的問(wèn)題,本文總結(jié)了4 個(gè)未來(lái)值得研究的方向,包括:細(xì)粒度的性能干擾模型、微服務(wù)架構(gòu)下的混部作業(yè)調(diào)度算法、軟硬件協(xié)同的內(nèi)存帶寬干擾隔離技術(shù)、面向在離線混部作業(yè)的調(diào)度模擬技術(shù).

4.1 細(xì)粒度的性能干擾模型

目前在混部作業(yè)管理系統(tǒng)中使用的性能干擾模型將作業(yè)執(zhí)行(或請(qǐng)求處理)看作一個(gè)整體,進(jìn)而刻畫(huà)作業(yè)整體在不同干擾下性能的變化.例如,描述在下一時(shí)段內(nèi)請(qǐng)求的平均完成時(shí)間,或者描述作業(yè)的執(zhí)行時(shí)間.性能干擾模型中的資源競(jìng)爭(zhēng)pressure也是作業(yè)混部期間的平均壓力.實(shí)際上,作業(yè)的運(yùn)行過(guò)程中包括多個(gè)階段[26],如Hadoop 作業(yè)存在Map 階段和Reduce 階段,基于深度神經(jīng)網(wǎng)絡(luò)的智能語(yǔ)音助手Sirius 在處理請(qǐng)求的過(guò)程中存在解析語(yǔ)音-分析語(yǔ)音-生成回復(fù)等多個(gè)階段[85].作業(yè)在不同階段因其計(jì)算任務(wù)不同,存在著不同資源需求和性能敏感度.現(xiàn)有的性能干擾模型針對(duì)應(yīng)用的整體性能特征進(jìn)行建模,忽略了作業(yè)不同階段的干擾敏感性變化,因此需要細(xì)粒度的性能干擾模型描述這種變化.

研究細(xì)粒度的性能模型對(duì)于混部作業(yè)調(diào)度和資源管理具有重要意義:在作業(yè)調(diào)度階段,基于細(xì)粒度干擾模型提供的豐富信息,規(guī)劃不同作業(yè)階段與階段之間的有序混部運(yùn)行,有利于減少資源競(jìng)爭(zhēng),降低性能干擾;對(duì)于混部資源管理,細(xì)粒度的性能干擾模型可提供更豐富的作業(yè)運(yùn)行時(shí)資源與性能的變化信息,基于這些信息可以設(shè)計(jì)更為精細(xì)的資源動(dòng)態(tài)算法,合理利用作業(yè)運(yùn)行期間的碎片資源,進(jìn)一步提高資源利用率.

4.2 面向微服務(wù)架構(gòu)的在離線混部作業(yè)調(diào)度

隨著微服務(wù)架構(gòu)的發(fā)展,數(shù)據(jù)中心出現(xiàn)了越來(lái)越多的采用微服務(wù)架構(gòu)的作業(yè)[86,87].微服務(wù)提升了作業(yè)的可擴(kuò)展性、容錯(cuò)性和可維護(hù)性,但是服務(wù)間的服務(wù)依賴(service dependency)使微服務(wù)作業(yè)的性能變化特點(diǎn)與傳統(tǒng)單體作業(yè)有明顯不同[38,88,89].在微服務(wù)架構(gòu)中,單個(gè)微服務(wù)的性能下降會(huì)引起其他服務(wù)的級(jí)聯(lián)性能下降(cascading performance degradation)[90].例如,某在線作業(yè)包含兩個(gè)微服務(wù),分別是微服務(wù)A和微服務(wù)B,微服務(wù)A是用戶直接訪問(wèn)的服務(wù),微服務(wù)A在處理用戶請(qǐng)求的過(guò)程中會(huì)調(diào)用微服務(wù)B.如果B的性能下降,那么A等待B的返回結(jié)果的時(shí)間變長(zhǎng),導(dǎo)致A的對(duì)于用戶請(qǐng)求的響應(yīng)時(shí)間變長(zhǎng).典型的級(jí)聯(lián)性能下降,如:(1)網(wǎng)頁(yè)搜索服務(wù)[91],其響應(yīng)時(shí)間取決于最慢的搜索節(jié)點(diǎn);(2)Memcached[92]和Redis[93]等廣泛使用的數(shù)據(jù)緩存系統(tǒng),其性能下降會(huì)引起上層服務(wù)的性能下降.因此,在面向微服務(wù)架構(gòu)的在離線混部作業(yè)調(diào)度算法不僅需要考慮作業(yè)在混部時(shí)產(chǎn)生的性能干擾,還需考慮性能干擾引起的級(jí)聯(lián)性能下降,使得在離線混部作業(yè)調(diào)度問(wèn)題更加復(fù)雜.

面向微服務(wù)架構(gòu)的在離線混部作業(yè)調(diào)度面臨的挑戰(zhàn)包括:(1)構(gòu)建端到端的請(qǐng)求執(zhí)行路徑具有挑戰(zhàn)性.端到端的請(qǐng)求執(zhí)行路徑描述了請(qǐng)求在多個(gè)微服務(wù)之間處理和轉(zhuǎn)發(fā)的過(guò)程,是請(qǐng)求級(jí)服務(wù)依賴關(guān)系的表示,與作業(yè)的具體執(zhí)行邏輯相關(guān),是上層調(diào)度器的重要數(shù)據(jù)基礎(chǔ).在大規(guī)模微服務(wù)集群中,僅憑專家經(jīng)驗(yàn)或者用戶提供的先驗(yàn)知識(shí)構(gòu)建端到端的服務(wù)依賴關(guān)系并不可行,并且現(xiàn)有的分布式追蹤系統(tǒng)仍然存在著數(shù)據(jù)讀寫(xiě)依賴問(wèn)題和通用性問(wèn)題[94],因此,如何從海量微服務(wù)運(yùn)行過(guò)程中精準(zhǔn)、高效、實(shí)時(shí)地構(gòu)建端到端的請(qǐng)求執(zhí)行路徑,具有挑戰(zhàn)性;(2)構(gòu)建面向微服務(wù)架構(gòu)的性能干擾模型具有挑戰(zhàn)性.首先,由于作業(yè)間的服務(wù)依賴關(guān)系,原本相互獨(dú)立的性能干擾模型需要根據(jù)服務(wù)依賴關(guān)系進(jìn)行聯(lián)動(dòng);其次,需要對(duì)微服務(wù)之間的通信過(guò)程建立性能模型以反映作業(yè)性能的真實(shí)變化,但是通信性能受RPC 協(xié)議、網(wǎng)絡(luò)架構(gòu)、集群負(fù)載等多方面影響,具有高度復(fù)雜性.因此,構(gòu)建面向微服務(wù)架構(gòu)的性能干擾模型具有挑戰(zhàn)性.

隨著微服務(wù)架構(gòu)的廣泛使用,越來(lái)越多的應(yīng)用向微服務(wù)架構(gòu)遷移,研究面向微服務(wù)架構(gòu)的在離線混部作業(yè)調(diào)度將日益重要.

4.3 軟硬件協(xié)同的內(nèi)存帶寬資源隔離技術(shù)

目前,CPU 的運(yùn)行速率遠(yuǎn)大于存儲(chǔ)器的運(yùn)行速率,二者性能的不匹配稱為“存儲(chǔ)墻(memory wall)”[95].雖然多級(jí)緩存和緩存預(yù)取技術(shù)在一定程度上緩解了CPU 和內(nèi)存的性能鴻溝,但是并不能從根本上解決這一問(wèn)題.在目前數(shù)據(jù)中心廣泛采用的多核架構(gòu)中,存儲(chǔ)墻導(dǎo)致內(nèi)存帶寬成為多核架構(gòu)中競(jìng)爭(zhēng)最激烈的資源,嚴(yán)重影響了混部作業(yè)的運(yùn)行效率,但是目前的操作系統(tǒng)和硬件技術(shù)并不能提供相應(yīng)的干擾隔離技術(shù).

解決這一問(wèn)題需要從軟件和硬件兩方面進(jìn)行研究.硬件方面需要在內(nèi)存控制器(memory controler)上進(jìn)行改進(jìn),對(duì)每次內(nèi)存訪問(wèn)進(jìn)行標(biāo)簽化,進(jìn)而使得內(nèi)存控制器可根據(jù)標(biāo)簽對(duì)內(nèi)存訪問(wèn)請(qǐng)求進(jìn)行調(diào)度;軟件層面需要研發(fā)相應(yīng)的軟件配置和動(dòng)態(tài)調(diào)整不同作業(yè)內(nèi)存訪問(wèn)的優(yōu)先級(jí).內(nèi)存作為馮諾依曼體系結(jié)構(gòu)中最重要且使用最為頻繁的計(jì)算資源之一,高效隔離內(nèi)存帶寬上資源競(jìng)爭(zhēng)對(duì)上層作業(yè)的性能至關(guān)重要,該方向的研究成果對(duì)進(jìn)一步提高混部作業(yè)的運(yùn)行效率具有重要意義.

4.4 面向在離線混部作業(yè)的調(diào)度模擬器

在作業(yè)調(diào)度算法研究中,使用模擬器驗(yàn)證由于具有快速、低成本等優(yōu)點(diǎn)已成為重要的驗(yàn)證和評(píng)價(jià)手段.在離線混部作業(yè)調(diào)度需要模擬器對(duì)作業(yè)間的性能干擾進(jìn)行模擬,但是目前主流的調(diào)度模擬器,如CloudSim[96]以及以CloudSim 衍生模擬器[97,98]對(duì)于作業(yè)性能的模擬僅依據(jù)作業(yè)的資源分配,無(wú)法模擬混部作業(yè)在體系結(jié)構(gòu)層次競(jìng)爭(zhēng)資源而引起的性能干擾.計(jì)算機(jī)體系結(jié)構(gòu)模擬器(如SMARTS[99]、SimGodon[100]、ZSim[101]、Gem5[102]等)雖然通過(guò)指令級(jí)模擬提供了精細(xì)再現(xiàn)作業(yè)的執(zhí)行過(guò)程,可模擬多個(gè)作業(yè)在硬件上的資源競(jìng)爭(zhēng),但其缺點(diǎn)在于運(yùn)行速度慢,模擬一個(gè)主頻為3Ghz 的CPU 一秒鐘內(nèi)執(zhí)行的所有指令需要數(shù)分鐘甚至更長(zhǎng)時(shí)間,高額的開(kāi)銷使其無(wú)法應(yīng)用于大規(guī)模數(shù)據(jù)中心的模擬.文獻(xiàn)[103]提出了微服務(wù)模擬器uqSim,基于排隊(duì)論模型模擬基于微服務(wù)架構(gòu)的在線作業(yè)的運(yùn)行,但其局限性在于:(1)只能模擬在線作業(yè),無(wú)法模擬離線作業(yè);(2)無(wú)法模擬作業(yè)間的性能干擾.

因此,目前仍缺乏面向在離線混部作業(yè)的調(diào)度模擬器.全方位模擬應(yīng)用之間的依賴、干擾、競(jìng)爭(zhēng)等關(guān)系,快速分析和驗(yàn)證混部作業(yè)調(diào)度算法在不同場(chǎng)景下的運(yùn)行效果,降低調(diào)度算法的調(diào)試與測(cè)試難度,是未來(lái)重要的研究方向之一.

5 結(jié)束語(yǔ)

大規(guī)模數(shù)據(jù)中心是當(dāng)今企業(yè)級(jí)互聯(lián)網(wǎng)應(yīng)用和云計(jì)算系統(tǒng)的關(guān)鍵支撐.然而,目前數(shù)據(jù)中心的服務(wù)器資源利用率較低(僅為10%～20%),導(dǎo)致大量的數(shù)據(jù)中心資源的浪費(fèi).將數(shù)據(jù)中心中的在線作業(yè)和離線作業(yè)混合部署在同一節(jié)點(diǎn)上運(yùn)行是提升數(shù)據(jù)中心資源利用率和數(shù)據(jù)中心成本效率的有效方法,具有較高的經(jīng)濟(jì)價(jià)值和研究?jī)r(jià)值.但是,將在線作業(yè)和離線作業(yè)混合部署面臨著諸多問(wèn)題與挑戰(zhàn),包括:在離線混部作業(yè)性能干擾問(wèn)題;在離線混部作業(yè)調(diào)度問(wèn)題;在離線作業(yè)的共享資源隔離問(wèn)題;資源動(dòng)態(tài)分配問(wèn)題.

本文首先分析了上述問(wèn)題與挑戰(zhàn),隨后圍繞在離線混部作業(yè)調(diào)度與資源管理技術(shù)研究框架,詳細(xì)分析和總結(jié)了已有研究工作,并結(jié)合多個(gè)系統(tǒng)實(shí)例分析了在離線混部關(guān)鍵技術(shù)在實(shí)際系統(tǒng)中的具體應(yīng)用及運(yùn)行效果.最后,本文就未來(lái)的研究方向進(jìn)行了展望.