云平臺(tái)下基于截止時(shí)間的自適應(yīng)調(diào)度策略

吳仁彪，張振馳，賈云飛，喬 晗

（天津市智能信號(hào)與圖像處理重點(diǎn)實(shí)驗(yàn)室（中國(guó)民航大學(xué)），天津 300300）

0 引言

云計(jì)算已成為流行的計(jì)算范式，近年來(lái)，由于基于云的應(yīng)用需求不斷增加，資源共享和復(fù)用的要求越來(lái)越迫切。如何根據(jù)云計(jì)算中心和用戶的服務(wù)質(zhì)量（Quality of Service，QoS）要求，高效合理地分配不同的資源是一個(gè)關(guān)鍵問(wèn)題。傳統(tǒng)資源分配方案難以根據(jù)用戶請(qǐng)求有效地分配資源，因此，行業(yè)和學(xué)術(shù)界都開(kāi)始了大量的研究。通常而言，云服務(wù)平臺(tái)以作業(yè)為抽象單位執(zhí)行計(jì)算任務(wù)，按計(jì)算任務(wù)的不同可以將作業(yè)分為長(zhǎng)作業(yè)和短作業(yè)。短作業(yè)一般以服務(wù)的形式處理用戶的請(qǐng)求，例如網(wǎng)頁(yè)搜索、實(shí)時(shí)交易等服務(wù)，這類服務(wù)具備較高的實(shí)時(shí)性要求；而長(zhǎng)作業(yè)是數(shù)據(jù)密集型的批處理作業(yè)，如數(shù)據(jù)分析作業(yè)、機(jī)器學(xué)習(xí)模型訓(xùn)練作業(yè)等。對(duì)于具有較高穩(wěn)定性和實(shí)時(shí)性要求的作業(yè)，企業(yè)會(huì)對(duì)外提出明確的服務(wù)等級(jí)協(xié)議（Service Level Agreement，SLA）以明確的條款約定服務(wù)質(zhì)量，違反SLA 會(huì)給企業(yè)帶來(lái)經(jīng)濟(jì)損失，因此對(duì)于這種作業(yè)，往往會(huì)預(yù)留大量的資源以保證其服務(wù)質(zhì)量。然而，過(guò)量資源供給策略會(huì)導(dǎo)致資源利用率較低。統(tǒng)計(jì)數(shù)據(jù)［1-2］顯示，全球數(shù)據(jù)中心的資源利用率僅為10%～30%，存在大量的資源浪費(fèi)，如何提升資源的利用率成為一個(gè)亟須解決的關(guān)鍵性技術(shù)問(wèn)題。

研究［3-6］表明，通過(guò)在多個(gè)用戶之間共享硬件基礎(chǔ)設(shè)施可以有效提高利用率。例如Google 在其集群管理系統(tǒng)Borg［7］中利用統(tǒng)一調(diào)度策略實(shí)現(xiàn)了兩種作業(yè)的混合部署，使集群規(guī)模壓縮為原有集群的35%；Matrix 復(fù)用Sorlaria 和Normandy 為百度節(jié)省了數(shù)萬(wàn)臺(tái)服務(wù)器的成本［8］；阿里巴巴按照同樣的做法利用Sigma［9］和Fuxi［10］組成混部系統(tǒng)將原有集群的利用率從10%提升至40%，節(jié)約總體成本30%以上。與此同時(shí)，共享的數(shù)據(jù)中心將面臨新的挑戰(zhàn)，即不同用戶提交的任務(wù)具有不同的服務(wù)需求，各個(gè)任務(wù)之間差異很大，集群管理框架面臨著如何高效托管各種工作負(fù)載的挑戰(zhàn)［11-14］。

傳統(tǒng)的集群調(diào)度器基于完整的集群信息作出集中的調(diào)度決策，目的是優(yōu)化資源利用率并保持?jǐn)?shù)據(jù)局部性。然而，這種調(diào)度策略是為長(zhǎng)作業(yè)設(shè)計(jì)的，沒(méi)有考慮到短作業(yè)延遲敏感度高的特點(diǎn)，因此在高負(fù)載下可能會(huì)顯著延長(zhǎng)短作業(yè)的執(zhí)行時(shí)間。一些分布式調(diào)度器，如Sparrow［15］和Apollo［16］，通過(guò)在每個(gè)節(jié)點(diǎn)部署調(diào)度器來(lái)加速調(diào)度。盡管分布式調(diào)度器可以作出敏捷的調(diào)度決策，但如果集群負(fù)載很高，在單個(gè)節(jié)點(diǎn)上完成長(zhǎng)任務(wù)之前，短任務(wù)仍然會(huì)經(jīng)歷長(zhǎng)時(shí)間的排隊(duì)延遲。為了協(xié)調(diào)兩者，混合調(diào)度器［17-18］使用分布式調(diào)度保留集群的一部分資源專門運(yùn)行短作業(yè)，而使用集中式調(diào)度將長(zhǎng)作業(yè)調(diào)度到其余的部分。此方法實(shí)現(xiàn)難點(diǎn)在于如何確定群集的最佳分區(qū)，在保證短作業(yè)低延遲的同時(shí)保持高的集群資源利用率。另外一種解決思路是實(shí)時(shí)預(yù)測(cè)應(yīng)用的資源需求，并以此為基礎(chǔ)動(dòng)態(tài)按需供應(yīng)資源，例如文獻(xiàn)［19-20］中提到的方法通過(guò)作業(yè)資源匹配算法以及資源預(yù)測(cè)算法為應(yīng)用按需動(dòng)態(tài)供應(yīng)資源。然而這種啟發(fā)式的資源預(yù)測(cè)需要結(jié)合歷史數(shù)據(jù)和用戶給出的波峰波谷的變化周期及幅度才能準(zhǔn)確預(yù)測(cè)下一個(gè)時(shí)間周期的資源需求。

如果短作業(yè)任務(wù)可以搶占長(zhǎng)作業(yè)任務(wù)，短作業(yè)的調(diào)度可以變得簡(jiǎn)單快速，而長(zhǎng)作業(yè)可以在集群中的任何服務(wù)器上運(yùn)行，以保持高利用率。例如另一種資源協(xié)調(diào)者（Yet Another Resource Negotiator，YARN）［21］和Mesos［22］中，用戶可以為任務(wù)設(shè)定優(yōu)先級(jí)，在資源出現(xiàn)競(jìng)爭(zhēng)時(shí)優(yōu)先滿足高優(yōu)先級(jí)的任務(wù)以保證短作業(yè)的響應(yīng)速度，然而目前現(xiàn)有的調(diào)度策略只支持kill-base 方式的任務(wù)搶占，即被搶占的任務(wù)只能取消，執(zhí)行進(jìn)度會(huì)丟失，這可能導(dǎo)致長(zhǎng)作業(yè)的任務(wù)完成時(shí)間延長(zhǎng)。

綜上所述，對(duì)具有不同資源需求的任務(wù)進(jìn)行調(diào)度時(shí)，資源預(yù)留式和資源預(yù)測(cè)等方法都有其局限性，搶占式調(diào)度簡(jiǎn)單而快速，能有效保障任務(wù)的服務(wù)質(zhì)量，但現(xiàn)有的搶占式調(diào)度沒(méi)有考慮到被搶占任務(wù)的執(zhí)行情況。針對(duì)這一問(wèn)題，本文提出了一種可以有效兼顧搶占任務(wù)的響應(yīng)速度以及被搶占任務(wù)的完成時(shí)間調(diào)度算法。

本文的工作有：1）實(shí)現(xiàn)了一種以提交截止時(shí)間代替用戶指定固定資源的任務(wù)提交方式；2）提出了一種自適應(yīng)資源分配策略，根據(jù)任務(wù)提交的截止時(shí)間和任務(wù)的實(shí)際執(zhí)行情況自適應(yīng)地分配資源；3）提出了一種用于調(diào)度不同服務(wù)質(zhì)量需求任務(wù)的調(diào)度策略，基于搶占式調(diào)度策略的思想，優(yōu)先滿足短作業(yè)的響應(yīng)速度，然后補(bǔ)償額外資源用于長(zhǎng)作業(yè)的執(zhí)行。

1 分布式計(jì)算框架Spark

Spark 通過(guò)在彈性分布式數(shù)據(jù)集（Resilient Distributed Datasets，RDD）［23］上實(shí)現(xiàn)transformations 和actions 操作來(lái)推廣MapReduce［24］編程模型，如圖1 所示，Spark 任務(wù)執(zhí)行引擎包括任務(wù)解析和生成，任務(wù)分發(fā)調(diào)度以及分配執(zhí)行任務(wù)所需的資源。對(duì)于任務(wù)的生成，在用戶提交Spark 作業(yè)后，有向無(wú)環(huán)圖（Directed Acyclic Graph，DAG）Scheduler 會(huì)遍歷所有RDD，并根據(jù)它們執(zhí)行的操作類型將它們分為不同的階段。然后，基于同一階段包含一組任務(wù)的RDD 分區(qū)，為就緒階段創(chuàng)建任務(wù)集。與此同時(shí)，資源管理器在節(jié)點(diǎn)上分配相應(yīng)資源并啟動(dòng)Executor 等待任務(wù)的發(fā)送。Spark 默認(rèn)使用粗粒度調(diào)度模式分配資源，即啟動(dòng)相應(yīng)資源的Java 虛擬機(jī)（Java Virtual Machine，JVM）維護(hù)一組線程用于執(zhí)行即將分配過(guò)來(lái)的任務(wù)。對(duì)于任務(wù)的分發(fā)調(diào)度，任務(wù)集由Task Scheduler 按相應(yīng)策略分發(fā)到各個(gè)節(jié)點(diǎn)中，Task 執(zhí)行完成后會(huì)將結(jié)果返回。

圖1 Spark的任務(wù)執(zhí)行模型Fig.1 Task execution model of Spark

2 基于容器的搶占式任務(wù)調(diào)度策略

目前Spark 已經(jīng)成為最流行的計(jì)算框架之一，Spark 將Task 的計(jì)算結(jié)果緩存到內(nèi)存中供后續(xù)Task 使用，因此在迭代計(jì)算以及Task 非常多的應(yīng)用中擁有顯著的優(yōu)勢(shì)。然而相關(guān)研究［25］表明，在面對(duì)搶占式任務(wù)調(diào)度時(shí)，Spark 更容易受到搶占式調(diào)度的影響。主要原因有以下幾點(diǎn)：1）Spark 中運(yùn)行的任務(wù)執(zhí)行器采用多線程模型，對(duì)一個(gè)容器的搶占會(huì)影響多個(gè)任務(wù)；2）對(duì)于具有迭代計(jì)算的Spark 作業(yè)，任務(wù)涉及容器間的頻繁切換；3）由于Spark 基于內(nèi)存計(jì)算的特點(diǎn)，從搶占容器中回收內(nèi)存可能會(huì)導(dǎo)致嚴(yán)重的內(nèi)存交換。

基于以上幾點(diǎn)原因，本文參考dynaSpark［26］的動(dòng)態(tài)資源調(diào)度方法，在此基礎(chǔ)上提出一種搶占式任務(wù)調(diào)度方法，工作流程分為以下四步：

第一步 用提交截止時(shí)間的方式替代固定的資源分配并將隨任務(wù)提交的截止時(shí)間進(jìn)行劃分，分成每個(gè)階段的截止時(shí)間deadlines。

第二步 根據(jù)預(yù)執(zhí)行結(jié)果啟發(fā)式地分配給各個(gè)Executor相應(yīng)的計(jì)算資源作為初始資源。

第三步 實(shí)時(shí)監(jiān)測(cè)任務(wù)執(zhí)行進(jìn)度，比較其與預(yù)期進(jìn)度的誤差，根據(jù)誤差對(duì)本節(jié)點(diǎn)上的容器進(jìn)行資源調(diào)整，保證各階段任務(wù)以及整個(gè)應(yīng)用在截止時(shí)間附近完成。

第四步 多作業(yè)并行執(zhí)行時(shí)，根據(jù)用戶設(shè)定的優(yōu)先級(jí)分配給不同應(yīng)用相應(yīng)的計(jì)算資源。

為了擴(kuò)展Spark 實(shí)現(xiàn)動(dòng)態(tài)資源分配的功能，對(duì)Spark 原有的體系結(jié)構(gòu)和處理模型進(jìn)行修改。如圖2，為改進(jìn)后的系統(tǒng)框架，無(wú)底色部分為Spark 基礎(chǔ)結(jié)構(gòu)，有底色部分為添加的 組件。

圖2 改進(jìn)后的Spark架構(gòu)Fig.2 Improved Spark architecture

為了動(dòng)態(tài)調(diào)整任務(wù)運(yùn)行過(guò)程中分配給Executor 的計(jì)算資源，每個(gè)Executor 進(jìn)程都運(yùn)行在以Docker Engine 為基礎(chǔ)的容器中，并且每個(gè)Worker 節(jié)點(diǎn)都部署有Control 組件負(fù)責(zé)實(shí)時(shí)監(jiān)測(cè)每個(gè)Executor 中任務(wù)集的完成情況，根據(jù)實(shí)時(shí)任務(wù)完成情況，動(dòng)態(tài)調(diào)整分配給Executor 的CPU 核數(shù)。在Master 節(jié)點(diǎn)中，Memory Manager 負(fù)載管理分配給應(yīng)用的內(nèi)存大小，根據(jù)提交的任務(wù)數(shù)量動(dòng)態(tài)調(diào)整堆外內(nèi)存。

2.1 Deadline劃分

擴(kuò)展后的Spark 利用容器（即Docker［27］）來(lái)支持更靈活、細(xì)粒度的資源管理，通過(guò)將每個(gè)執(zhí)行器部署在一個(gè)容器中，以允許動(dòng)態(tài)地改變提供給執(zhí)行器的計(jì)算資源。具體來(lái)說(shuō)，用戶可以使用一個(gè)額外的參數(shù)deadline來(lái)豐富命令提交，以指定此應(yīng)用期望的執(zhí)行時(shí)間。動(dòng)態(tài)分配資源的目標(biāo)是在不違反截止日期的情況下最大限度地減少資源的使用，相較于提交之前確定分配給應(yīng)用固定的計(jì)算資源，這種分配資源的方式更具可控性，因?yàn)轭A(yù)估任務(wù)計(jì)算時(shí)間是十分困難的。

相較于給完整的應(yīng)用程序分配資源，由于階段是由具有不同復(fù)雜程度的不同操作組成的，對(duì)每個(gè)階段進(jìn)行單獨(dú)的控制更為合理。因此，每個(gè)應(yīng)用程序都使用基于啟發(fā)式的算法來(lái)計(jì)算每個(gè)階段的截止日期deadlines。當(dāng)一個(gè)階段s提交執(zhí)行時(shí)，使用以下公式計(jì)算初步截止日期：

其中：spentTime是已經(jīng)花費(fèi)在執(zhí)行應(yīng)用程序上的時(shí)間；appDeadline是用戶提交的應(yīng)用的持續(xù)時(shí)間表示的截止時(shí)間；α∈[0，1]是一個(gè)常數(shù)，用來(lái)設(shè)置遵守截止時(shí)間的保守程度。如果α=1，執(zhí)行時(shí)間將被控制嚴(yán)格地滿足截止時(shí)間，而對(duì)于較小的α值，控制將更加保守。ωs為階段的權(quán)重，計(jì)算如下：

其中：Rs是仍待執(zhí)行的階段集，包括s，ds是Rs中階段的已分析持續(xù)時(shí)間之和與s本身的已分析持續(xù)時(shí)間之比。因此：

由于在分析期間也就是預(yù)執(zhí)行期間，測(cè)量的性能可能不同于在運(yùn)行時(shí)的性能，為了避免過(guò)度擬合分析數(shù)據(jù)，使用常數(shù)β來(lái)減輕擬合。所有的ωs都是在運(yùn)行時(shí)計(jì)算的，因?yàn)槿绻鸇AG 中有并行線程，就不能先驗(yàn)地知道階段執(zhí)行的順序。

2.2 啟發(fā)式控制階段

得到階段的截止時(shí)間后，為執(zhí)行階段而分配的CPU 核心數(shù)量被估計(jì)為：

其中：inputRecords是必須由s處理的記錄數(shù)量；nomRates提供s的標(biāo)稱速率，即單個(gè)核心每秒處理的記錄數(shù)量（在分析期間獲得）。輸入記錄取決于DAG 中父節(jié)點(diǎn)寫入的數(shù)據(jù)總和（即父節(jié)點(diǎn)產(chǎn)生的記錄總和）。

最后一步計(jì)算內(nèi)核的初始數(shù)量和每個(gè)不同執(zhí)行器要處理的任務(wù)數(shù)量。通過(guò)為每個(gè)Worker 節(jié)點(diǎn)的每個(gè)階段創(chuàng)建一個(gè)執(zhí)行器，在所有可用的Worker 節(jié)點(diǎn)之間平均分配負(fù)載。通過(guò)這種方式，每個(gè)執(zhí)行器都持有相同數(shù)量的任務(wù)，因此在shuffle 過(guò)程中遠(yuǎn)程讀取相同數(shù)量的數(shù)據(jù)，這意味著可以為所有執(zhí)行器計(jì)算相同的截止日期。每個(gè)執(zhí)行器的初始內(nèi)核數(shù)計(jì)算如下：

其中：numExecutors是執(zhí)行器的數(shù)量，始終等于工作節(jié)點(diǎn)的數(shù)量；cq代表內(nèi)核數(shù)量，這是一個(gè)定義應(yīng)用于資源分配的量化的常數(shù)，值越小，分配越精確。

在本文的實(shí)驗(yàn)中，設(shè)置cq=0.05，以分配精度高達(dá)0.05的內(nèi)核，并獲得較低的誤差。初始分配的資源不需要非常精確，因?yàn)楹竺鏁?huì)根據(jù)任務(wù)的執(zhí)行進(jìn)度自適應(yīng)地資源分配。

2.3 基于容器的動(dòng)態(tài)資源調(diào)度

初始資源分配完成后，任務(wù)開(kāi)始運(yùn)行，Worker 節(jié)點(diǎn)上的Control 組件會(huì)根據(jù)任務(wù)執(zhí)行進(jìn)度動(dòng)態(tài)分配資源，實(shí)現(xiàn)動(dòng)態(tài)資源調(diào)度的關(guān)鍵技術(shù)由兩部分組成：第一部分是容器技術(shù)Docker，通過(guò)Docker 的CPU 周期分配技術(shù)實(shí)現(xiàn)對(duì)運(yùn)行期間的Executor 進(jìn)行資源調(diào)度；第二部分則是實(shí)時(shí)控制部分，通過(guò)分析實(shí)時(shí)的任務(wù)完成率，當(dāng)實(shí)時(shí)完成率低于預(yù)期完成率則增加計(jì)算資源，反之則減少資源。由此，應(yīng)用程序在運(yùn)行過(guò)程中可以根據(jù)執(zhí)行進(jìn)度進(jìn)行資源的分配，然后在截止時(shí)間附近完成。

2.3.1 容器技術(shù)概述

目前大多數(shù)大數(shù)據(jù)應(yīng)用程序都是用托管語(yǔ)言（Managed Programming Language）編寫，以實(shí)現(xiàn)跨機(jī)器的可移植性，以Spark 為例，當(dāng)Executor 部署到Worker 節(jié)點(diǎn)上時(shí)，節(jié)點(diǎn)首先需要啟動(dòng)一個(gè)JVM 來(lái)執(zhí)行它們。其中CPU 內(nèi)核的分配是靜態(tài)的，由一個(gè)簡(jiǎn)單的內(nèi)部線程池管理，并且Executor 與應(yīng)用綁定，即使當(dāng)前的Executor 沒(méi)有任務(wù)運(yùn)行，只有當(dāng)整個(gè)應(yīng)用結(jié)束時(shí)，資源才能釋放。另一個(gè)重要的參數(shù)是JVM 的堆大小，它的錯(cuò)誤配置會(huì)導(dǎo)致任務(wù)失?。涸O(shè)置堆大小太小可能會(huì)導(dǎo)致JVM 內(nèi)存不足（Out Of Memory，OOM）錯(cuò)誤，任務(wù)將失敗；設(shè)置堆大小太大可能會(huì)導(dǎo)致后續(xù)應(yīng)用程序資源不足導(dǎo)致過(guò)長(zhǎng)的延遲。在運(yùn)行任務(wù)之前，很難甚至不可能確定最佳的JVM堆大小。

與基于虛擬機(jī)管理程序的虛擬化相比，基于容器的虛擬化技術(shù)，例如Docker，由于它幾乎可以忽略不計(jì)的開(kāi)銷而變得流行。容器為容器內(nèi)運(yùn)行的應(yīng)用程序提供獨(dú)立的名稱空間，并形成資源核算和分配單元。Linux 使用控制組群（cgroups）來(lái)精確控制容器的資源分配。有了容器，任務(wù)可以以大的JVM 堆大小啟動(dòng)，用戶可以使用cgroups 來(lái)限制托管容器的內(nèi)存使用，以防止系統(tǒng)內(nèi)存崩潰。重要的是，即使任務(wù)的堆使用量超過(guò)了它的容器內(nèi)存大?。ㄒ?yàn)槎训拇笮∫蟮枚啵蝿?wù)也不會(huì)遇到OOM 錯(cuò)誤，而是會(huì)開(kāi)始內(nèi)存交換。

2.3.2 動(dòng)態(tài)資源分配

Docker 提供了多種向容器分配CPU 的方法，其中Quotas方法能保證CPU 分配的確定性和快速性。Quotas 為每個(gè)容器都設(shè)定一個(gè)周期和一個(gè)配額，后者表示在該周期內(nèi)分配給容器的CPU 時(shí)間的百分比。設(shè)置大于周期的配額意味著容器一次應(yīng)該使用多個(gè)核心，但是所有配額的總和必須始終小于設(shè)置的周期乘以可用核心數(shù)。

例如，對(duì)于擁有一個(gè)單核CPU 的節(jié)點(diǎn)，設(shè)定100 ms 的周期，如果給容器1 的配額為30 ms，給容器2 的配額為70 ms，那么70%的CPU 時(shí)間留給容器2，30%留給容器1。

分配原則遵循完全公平調(diào)度（Completely Fair Scheduler，CFS）［28］，這種機(jī)制是確定性的，非常細(xì)粒度，實(shí)現(xiàn)也非常地快速，一次分配通常能在幾百毫秒內(nèi)完成。

Spark 的Executor 實(shí)際上是在Worker 節(jié)點(diǎn)中啟動(dòng)的CoarseGrainedExecutorBackend 類進(jìn)程中維護(hù)的一組線程池，改進(jìn)后的系統(tǒng)將其封裝在Docker 鏡像內(nèi)，啟動(dòng)Executor 時(shí)分配初始參數(shù)，之后Control 組件實(shí)時(shí)監(jiān)控Executor 的工作狀態(tài)，計(jì)算實(shí)時(shí)的資源需求，得到需要的資源數(shù)量后，執(zhí)行Docker update 命令對(duì)容器的資源進(jìn)行調(diào)整。cpu-period 參數(shù)用來(lái)指定容器對(duì)CPU 的使用要在多長(zhǎng)時(shí)間內(nèi)做一次重新分配；而cpu-quota 參數(shù)是用來(lái)指定這個(gè)周期內(nèi)，最多可以有多少時(shí)間來(lái)運(yùn)行此容器。例如要為一個(gè)Executor 分配cores 為2.5 的CPU 資源，設(shè)置參數(shù)cpu-period 為100 000、cpu-quota 為250 000。

2.4 搶占式任務(wù)調(diào)度

2.4.1 應(yīng)用內(nèi)存分配

在開(kāi)始執(zhí)行應(yīng)用程序之前，用戶必須指定提供給每個(gè)executor 的內(nèi)存量。足夠的內(nèi)存可以保證性能，而有限的內(nèi)存可能會(huì)導(dǎo)致磁盤交換（存儲(chǔ)）或崩潰（執(zhí)行），因?yàn)閳?zhí)行中的任務(wù)不允許交換。在需要同時(shí)執(zhí)行多個(gè)應(yīng)用程序時(shí)，如果用戶事先知道具體有多少應(yīng)用程序并行執(zhí)行，可在它們之間劃分可用的內(nèi)存。但這并不總是可行的，并且由于如果請(qǐng)求的內(nèi)存不可用，Spark 會(huì)推遲應(yīng)用程序的啟動(dòng)，因此用戶劃分內(nèi)存必須謹(jǐn)慎。動(dòng)態(tài)分配內(nèi)存可以解決這個(gè)問(wèn)題，但對(duì)于傳統(tǒng)的框架，如果不終止進(jìn)程并重新啟動(dòng)它，就無(wú)法調(diào)整執(zhí)行器的堆內(nèi)存大小。使用堆外內(nèi)存是一個(gè)可行的折中方案。Spark 本身已經(jīng)實(shí)現(xiàn)了使用堆外內(nèi)存的方案，堆外內(nèi)存是指由操作系統(tǒng)直接管理并存儲(chǔ)在進(jìn)程堆外的對(duì)象，也就是說(shuō)，它們不被JVM 的垃圾收集器處理。訪問(wèn)堆外數(shù)據(jù)比訪問(wèn)堆內(nèi)數(shù)據(jù)稍慢，但比讀寫磁盤快。

Spark 本身沒(méi)有提供動(dòng)態(tài)調(diào)整堆外內(nèi)存大小的方法，本文添加了相應(yīng)的組件進(jìn)行內(nèi)存管理。給定一組正在運(yùn)行的應(yīng)用程序A和集群的總內(nèi)存M，用戶可以通過(guò)這個(gè)組件決定分配給每個(gè)應(yīng)用程序的固定堆內(nèi)存量h。內(nèi)存管理器還為每個(gè)正在運(yùn)行的應(yīng)用程序分配堆外內(nèi)存o=(M-h·|A|)/|A|。當(dāng)新應(yīng)用程序提交執(zhí)行時(shí)，內(nèi)存管理器會(huì)重新分配堆外內(nèi)存，但如果o＜h，則新應(yīng)用程序必須等待正在運(yùn)行的應(yīng)用程序終止，其內(nèi)存變得可用，并且新應(yīng)用程序可以啟動(dòng)。

對(duì)所有應(yīng)用程序進(jìn)行平均分配并不是最優(yōu)的，但當(dāng)工作負(fù)載未知時(shí)，這也是一種保守的解決方案。

2.4.2 基于優(yōu)先級(jí)CPU分配策略

對(duì)于傳統(tǒng)的Spark 框架，CPU 的分配在應(yīng)用提交時(shí)就已經(jīng)確定。傳統(tǒng)的搶占式任務(wù)調(diào)度策略下，當(dāng)集群資源不足以滿足作業(yè)的資源要求時(shí)，就只能取消正在運(yùn)行的任務(wù)并且回收資源，以便新提交任務(wù)的執(zhí)行。本文提出了一種更為友好的任務(wù)搶占方法。同樣地，用戶提前為作業(yè)劃分好優(yōu)先級(jí)，系統(tǒng)根據(jù)優(yōu)先級(jí)向應(yīng)用程序分配資源；不同的是，提交作業(yè)時(shí)用戶不需要提交固定的資源需求，作業(yè)不會(huì)出現(xiàn)排隊(duì)現(xiàn)象，任務(wù)運(yùn)行時(shí)，系統(tǒng)收集節(jié)點(diǎn)上資源請(qǐng)求信息，根據(jù)給定的任務(wù)優(yōu)先級(jí)給提出申請(qǐng)的任務(wù)進(jìn)行排序，按排序順序依次分配任務(wù)的資源申請(qǐng)，這樣在資源不足時(shí)，優(yōu)先級(jí)高的任務(wù)申請(qǐng)的資源會(huì)被優(yōu)先滿足，低優(yōu)先級(jí)的任務(wù)只能被分配剩余的資源。

如果任務(wù)每次的資源申請(qǐng)都能滿足，就會(huì)在實(shí)驗(yàn)設(shè)定的deadline內(nèi)完成任務(wù)，否則在搶占的任務(wù)完成后，對(duì)被搶占的任務(wù)進(jìn)行資源補(bǔ)償。

2.5 改進(jìn)算法偽代碼

改進(jìn)的搶占式任務(wù)調(diào)度算法的偽代碼如下：

輸入 用戶設(shè)定的應(yīng)用截止時(shí)間appDeadline；

輸出 算法為Executor 分配的CPU 資源correctCores。

3 實(shí)驗(yàn)與結(jié)果分析

本文在5 個(gè)節(jié)點(diǎn)集群上對(duì)改進(jìn)后的方法進(jìn)行了評(píng)估。所有實(shí)驗(yàn)都使用了帶有4 個(gè)CPU、12 GB 內(nèi)存和500 GB 本地固態(tài)硬盤存儲(chǔ)的服務(wù)器，各軟件版本信息如表1 所示。

表1 軟件版本信息Tab.1 Software version information

實(shí)驗(yàn)首先測(cè)試改進(jìn)后平臺(tái)的動(dòng)態(tài)資源調(diào)度功能（見(jiàn)3.1節(jié)）；接下來(lái)，展示了任務(wù)搶占時(shí)的資源調(diào)度情況，描述了出現(xiàn)資源競(jìng)爭(zhēng)時(shí)系統(tǒng)的調(diào)度結(jié)果（見(jiàn)3.2 節(jié)）；最后對(duì)比在不同負(fù)載下本文方法與傳統(tǒng)的調(diào)度策略的實(shí)驗(yàn)結(jié)果（見(jiàn)3.3 節(jié)）。

3.1 動(dòng)態(tài)資源調(diào)度實(shí)驗(yàn)

為了評(píng)估算法如何動(dòng)態(tài)分配CPU 內(nèi)核，本文使用了來(lái)自兩個(gè)基準(zhǔn)測(cè)試套件的8 個(gè)應(yīng)用程序。其中aggr-by-key（以下簡(jiǎn)稱abk）、aggr-by-key-int（簡(jiǎn)稱abk-int）、group-by、sort-by-key（簡(jiǎn)稱sbk）和sort-by-key-int（簡(jiǎn)稱sbk-int）強(qiáng)調(diào)基本的聚合和排序功能，來(lái)自SparkPerf。KMeans、SVM 和PageRank 來(lái)自SparkBench，這三個(gè)應(yīng)用是常見(jiàn)的具有迭代運(yùn)算的例子，前兩個(gè)是用于分類的機(jī)器學(xué)習(xí)應(yīng)用程序，第三個(gè)則是著名的網(wǎng)頁(yè)排名算法。前五個(gè)應(yīng)用程序不包含分支或循環(huán)，后三個(gè)是迭代的，但是迭代次數(shù)在開(kāi)始時(shí)通過(guò)參數(shù)配置。這意味著每個(gè)程序的所有執(zhí)行都有相同的DAG。各個(gè)應(yīng)用使用的數(shù)據(jù)集是使用配套的基準(zhǔn)測(cè)試套件中提供的工具和按照表2 中的參數(shù)設(shè)置隨機(jī)生成的。

表2 測(cè)試數(shù)據(jù)集參數(shù)設(shè)置Tab.2 Test dataset parameter setting

實(shí)驗(yàn)分為兩個(gè)步驟，首先使用Spark 來(lái)運(yùn)行每個(gè)應(yīng)用程序，分配給每個(gè)任務(wù)所有的可用資源，即4 臺(tái)worker 節(jié)點(diǎn)的16 個(gè)CPU 核心，把以這種方式提交的作業(yè)的執(zhí)行時(shí)間設(shè)定為測(cè)試基線（testBase）。

然后，本實(shí)驗(yàn)配置了如表3 所示的參數(shù)，按照同樣的方式在改進(jìn)后框架上提交任務(wù)，以便與Spark 進(jìn)行比較。其中deadline設(shè)置為與測(cè)試基線相同（test0%）和將原始截止日期放寬20%（test20%）兩種分別進(jìn)行實(shí)驗(yàn)。在不增加資源的情況下，截止日期不能比基線更短，因此，這些實(shí)驗(yàn)的目標(biāo)是評(píng)估調(diào)度算法滿足截止日期的精度以及動(dòng)態(tài)分配CPU 內(nèi)核的能力。

表3 作業(yè)參數(shù)設(shè)置Tab.3 Job parameter setting

圖3 顯示了為PageRank 應(yīng)用設(shè)定deadline=600 時(shí)動(dòng)態(tài)分配CPU 核數(shù)的過(guò)程，E 代表任務(wù)所處的階段（Stage），E0 表示初始階段，E1 表示Stage1、E2 表示Stage2，依此類推。其中：坐標(biāo)軸x軸指任務(wù)執(zhí)行經(jīng)過(guò)的時(shí)間；坐標(biāo)軸y軸左側(cè)指任務(wù)的完成進(jìn)度，對(duì)應(yīng)圖中的黑線（任務(wù)實(shí)際完成率）與灰線（期望完成率）；右側(cè)y軸對(duì)應(yīng)所分配到的CPU 核心數(shù)，對(duì)應(yīng)圖中的離散點(diǎn)；圖中垂直的線代表用戶設(shè)定的截止時(shí)間（虛線）和任務(wù)實(shí)際完成的時(shí)間（實(shí)線）。在運(yùn)行時(shí)，本地控制器預(yù)見(jiàn)核心部分分配給執(zhí)行器，當(dāng)階段的實(shí)際進(jìn)度低于規(guī)定進(jìn)度時(shí)，分配的核心數(shù)增加，而一旦實(shí)際進(jìn)度變得更高，分配的核心數(shù)就迅速減少。改進(jìn)后的系統(tǒng)很好地根據(jù)用戶提交的deadline動(dòng)態(tài)地分配資源，嚴(yán)格地在截止時(shí)間附近完成任務(wù)。

圖3 CPU動(dòng)態(tài)分配過(guò)程Fig.3 CPU dynamic allocation process

表4 顯示了用不同實(shí)驗(yàn)測(cè)試得到的控制精度的結(jié)果。表中顯示了在實(shí)驗(yàn)過(guò)程中是否發(fā)生了違反截止時(shí)間的現(xiàn)象以及任務(wù)完成時(shí)間與截止時(shí)間之間誤差的最小值（errormin）、最大值（errormax）、平均值（errormed）和標(biāo)準(zhǔn)偏差（std）。

表4 截止時(shí)間測(cè)試的實(shí)驗(yàn)結(jié)果Tab.4 Experiment results of deadline test

表4 實(shí)驗(yàn)結(jié)果顯示，放寬截止時(shí)間為基準(zhǔn)測(cè)試時(shí)間的20%時(shí)，不會(huì)出現(xiàn)違反截止時(shí)間的情況出現(xiàn)，當(dāng)資源充足時(shí)，能夠嚴(yán)格地控制任務(wù)的完成時(shí)間在截止時(shí)間之內(nèi)。當(dāng)設(shè)定截止時(shí)間為基準(zhǔn)測(cè)試時(shí)間時(shí)會(huì)出現(xiàn)違反截止時(shí)間現(xiàn)象，但是整體的平均誤差控制在1%左右。實(shí)驗(yàn)結(jié)果還表明在調(diào)度計(jì)算密集型任務(wù)時(shí)的效果要比調(diào)度數(shù)據(jù)密集型任務(wù)時(shí)的效果更好，這是由于計(jì)算密集型任務(wù)對(duì)CPU 資源更為敏感。

3.2 搶占式任務(wù)調(diào)度實(shí)驗(yàn)結(jié)果

為了描述搶占式任務(wù)調(diào)度的資源分配過(guò)程，提交Sparkperf 中的aggr-by-key 作為短作業(yè)，SparkBench 中的PageRank作為長(zhǎng)作業(yè)，模擬出實(shí)際生產(chǎn)中搶占式調(diào)度的場(chǎng)景。

實(shí)驗(yàn)結(jié)果如圖4 所示，圖4（a）是作業(yè)A 單獨(dú)運(yùn)行時(shí)的資源利用情況，圖4（b）是提交任務(wù)A 搶占任務(wù)B 時(shí)兩個(gè)應(yīng)用的資源分配情況。結(jié)果顯示優(yōu)先級(jí)高的任務(wù)能搶占低優(yōu)先級(jí)的任務(wù)，當(dāng)搶占任務(wù)完成之后，被搶占的任務(wù)會(huì)被分配額外的資源來(lái)補(bǔ)償執(zhí)行的損失。

圖4 搶占式調(diào)度資源分配實(shí)驗(yàn)結(jié)果Fig.4 Results of preemptive scheduling resource allocation experiments

由圖4（b）所示：當(dāng)任務(wù)B 提交后，節(jié)點(diǎn)同時(shí)接收來(lái)自任務(wù)A 與任務(wù)B 的資源申請(qǐng)，由于任務(wù)B 的優(yōu)先級(jí)高，節(jié)點(diǎn)會(huì)優(yōu)先分配資源給任務(wù)B 來(lái)滿足其截止時(shí)間，此時(shí)任務(wù)A 的申請(qǐng)得不到響應(yīng)。當(dāng)任務(wù)B 結(jié)束后，任務(wù)A 的申請(qǐng)才會(huì)得到響應(yīng)，此時(shí)由于與期望執(zhí)行進(jìn)度相差很大，任務(wù)A 會(huì)申請(qǐng)大量的資源來(lái)補(bǔ)償之前執(zhí)行進(jìn)度的損失。

與其他的搶占式調(diào)度做對(duì)比實(shí)驗(yàn)結(jié)果如圖5 所示：基于YARN 調(diào)度框架的搶占式調(diào)度，在響應(yīng)延遲以及對(duì)長(zhǎng)作業(yè)的執(zhí)行進(jìn)度的丟失都很嚴(yán)重；BiG-C 方法［29］用特有的方式，暫時(shí)掛起被搶占的長(zhǎng)作業(yè)，從而避免了長(zhǎng)作業(yè)執(zhí)行進(jìn)度的丟失，縮短了長(zhǎng)作業(yè)的執(zhí)行時(shí)間；而本文方法通過(guò)額外補(bǔ)償長(zhǎng)作業(yè)的模塊，使長(zhǎng)作業(yè)的執(zhí)行時(shí)間更短。

圖5 本文方法與其他搶占式方法的執(zhí)行時(shí)間對(duì)比實(shí)驗(yàn)結(jié)果Fig.5 Comparison experimental results of execution time between proposed method and other preemptive methods

3.3 對(duì)比實(shí)驗(yàn)

經(jīng)過(guò)前面的兩個(gè)實(shí)驗(yàn)，驗(yàn)證了改進(jìn)后框架動(dòng)態(tài)調(diào)度資源的能力，以及本文算法的搶占效果。本實(shí)驗(yàn)則進(jìn)一步與其他傳統(tǒng)調(diào)度方法對(duì)比，模擬生成工作負(fù)載，分別在低負(fù)載和高負(fù)載環(huán)境下評(píng)估短作業(yè)的響應(yīng)速度以及長(zhǎng)作業(yè)的執(zhí)行時(shí)間。

3.3.1 工作負(fù)載

工作負(fù)載使用Spark-perf 生成abk、group-by、sbk 作為短作業(yè)。為每個(gè)短作業(yè)分配4 CPU，3 GB的計(jì)算資源，通過(guò)配置生成數(shù)據(jù)集的參數(shù)，保證任務(wù)在資源充足情況下可以在30～40 s 內(nèi)完成。從SparkBench 中選擇了PageRank、Kmeans、SVM 作為Spark 長(zhǎng)作業(yè)。為每個(gè)長(zhǎng)作業(yè)分配8 CPU，8 GB的計(jì)算資源，通過(guò)配置生成數(shù)據(jù)集的參數(shù)，保證任務(wù)在資源充足情況下可以在5 min 內(nèi)完成。在整個(gè)實(shí)驗(yàn)過(guò)程中，長(zhǎng)作業(yè)被連續(xù)提交，它們持續(xù)利用了大約60%的集群資源。短作業(yè)被多個(gè)用戶同時(shí)提交，在低負(fù)載場(chǎng)景下申請(qǐng)大約60%的集群資源，在高負(fù)載場(chǎng)景下申請(qǐng)約80%的集群資源。顯然集群不足以滿足所有任務(wù)的資源需求，任務(wù)的執(zhí)行會(huì)受到影響。

為了進(jìn)行調(diào)度效果的比較，分別配置以下幾種調(diào)度方法：

1）先進(jìn)先出調(diào)度（FIFO）：程序以先進(jìn)先出的順序執(zhí)行任務(wù)，不需要額外設(shè)置。

2）資源預(yù)留調(diào)度（Reserve）：YARN 模式下配置了兩個(gè)隊(duì)列。為短作業(yè)保留40%的集群資源，為長(zhǎng)作業(yè)隊(duì)列配置60%的群集容量。

3）搶占式任務(wù)調(diào)度（kill-base）：YARN 模式下capacity scheduler 用于強(qiáng)制隊(duì)列之間的共享，設(shè)置短作業(yè)默認(rèn)40%的資源使用，搶占時(shí)可達(dá)到80%的資源使用。

4）本文方法：先進(jìn)行預(yù)執(zhí)行，得到在資源充足情況下應(yīng)用的平均執(zhí)行時(shí)間，將平均執(zhí)行時(shí)間設(shè)置為截止時(shí)間（deadline），并將短作業(yè)標(biāo)記為高優(yōu)先級(jí)應(yīng)用。

3.3.2 對(duì)比實(shí)驗(yàn)結(jié)果及分析

圖6 顯示了低負(fù)載環(huán)境下具有不同調(diào)度器的短作業(yè)和長(zhǎng)作業(yè)的性能。如圖6（a）顯示，是不同方法下短作業(yè)執(zhí)行時(shí)間的累計(jì)分布圖，縱坐標(biāo)是累積分布函數(shù)（Cumulative Distribution Function，CDF）。在傳統(tǒng)的調(diào)度器中，kill-base 與Reserve 都實(shí)現(xiàn)了對(duì)短作業(yè)的快速響應(yīng)，低負(fù)載情況下，預(yù)留的集群資源足以為大多數(shù)短作業(yè)提供服務(wù)，短作業(yè)的調(diào)度延遲幾乎為零，只有少量作業(yè)會(huì)進(jìn)行排隊(duì)等待。而本文方法獲得了比kill-base 和Reserve 更好的調(diào)度效果，由于提供作業(yè)計(jì)算資源不是由用戶給定而是算法計(jì)算而來(lái)的結(jié)果，其結(jié)果會(huì)比固定分配時(shí)更高，能保證任務(wù)在給定的截止時(shí)間內(nèi)完成。而傳統(tǒng)的調(diào)度方法都是給定固定的計(jì)算資源，即使是同樣規(guī)模的輸入，執(zhí)行時(shí)間也會(huì)有差異。

圖6 低負(fù)載環(huán)境下作業(yè)執(zhí)行時(shí)間的實(shí)驗(yàn)結(jié)果Fig.6 Experimental results of job execution time in low load environment

在高負(fù)載下，由于短作業(yè)的資源預(yù)留低于峰值需求，因此Reserve 調(diào)度的效果會(huì)降低。圖7（a）顯示，kill-base 是高負(fù)載環(huán)境下表現(xiàn)最好的調(diào)度器，它通過(guò)搶占長(zhǎng)作業(yè)的資源，始終將短延遲傳遞給短任務(wù)。本文方法也獲得了較好的效果，由于優(yōu)先級(jí)的設(shè)置，當(dāng)短作業(yè)和長(zhǎng)作業(yè)同時(shí)申請(qǐng)資源時(shí)，會(huì)優(yōu)先將資源分配給短作業(yè)，但長(zhǎng)作業(yè)的一部分內(nèi)存還會(huì)保留，所以調(diào)度效果不如kill-base。相比之下，F(xiàn)IFO 調(diào)度下短作業(yè)產(chǎn)生了很大的延遲，由于資源的不足，短作業(yè)需要等待長(zhǎng)作業(yè)完成后才能進(jìn)行調(diào)度。

對(duì)長(zhǎng)作業(yè)來(lái)說(shuō)。FIFO 調(diào)度在兩個(gè)場(chǎng)景下都實(shí)現(xiàn)了最好的調(diào)度結(jié)果，其次是Reserve 調(diào)度方法，調(diào)度效果都接近FIFO。圖7（b）顯示，調(diào)度結(jié)果最差的是kill-base 調(diào)度，由于需要始終滿足短作業(yè)的資源申請(qǐng)要求，即使在低負(fù)載情況下也會(huì)有長(zhǎng)作業(yè)被取消。本文方法取得了與FIFO 相近的調(diào)度結(jié)果，相比于kill-base 的取消長(zhǎng)作業(yè)釋放資源的搶占方式，本文方法會(huì)將長(zhǎng)作業(yè)暫時(shí)掛起，等到短作業(yè)執(zhí)行完畢后再將資源重新分配給長(zhǎng)作業(yè)，并且會(huì)補(bǔ)償掛起時(shí)損失的執(zhí)行進(jìn)度，使長(zhǎng)作業(yè)的平均執(zhí)行時(shí)間縮短了35%左右。

圖7 高負(fù)載環(huán)境下作業(yè)執(zhí)行時(shí)間的實(shí)驗(yàn)結(jié)果Fig.7 Experimental results of job execution time in high load environment

實(shí)驗(yàn)結(jié)果表明，在低負(fù)載時(shí)，集群資源充足，采用本文方法，短任務(wù)能被嚴(yán)格地控制在截止時(shí)間內(nèi)完成以滿足服務(wù)質(zhì)量。相較于其他的搶占式調(diào)度方法，本文方法在高負(fù)載環(huán)境下能有效地減輕被搶占作業(yè)受到的影響。

4 結(jié)語(yǔ)

在云計(jì)算環(huán)境中進(jìn)行任務(wù)調(diào)度時(shí)，一個(gè)重要的問(wèn)題就是如何調(diào)度在共享集群中具有不同服務(wù)質(zhì)量要求的應(yīng)用使響應(yīng)時(shí)間和任務(wù)完成時(shí)間達(dá)到最小。本文通過(guò)修改Spark 調(diào)度框架，開(kāi)發(fā)了基于截止時(shí)間的調(diào)度接口，提出并實(shí)現(xiàn)了一種基于動(dòng)態(tài)資源調(diào)度的搶占式任務(wù)調(diào)度方法。通過(guò)實(shí)驗(yàn)驗(yàn)證了算法能實(shí)現(xiàn)基于優(yōu)先級(jí)的搶占式調(diào)度，并且能夠額外補(bǔ)償被搶占任務(wù)的執(zhí)行進(jìn)度。由于實(shí)驗(yàn)環(huán)境限制，本文簡(jiǎn)化了在應(yīng)用執(zhí)行過(guò)程中影響應(yīng)用完成時(shí)間的諸多因素，只對(duì)內(nèi)存和CPU 等計(jì)算資源進(jìn)行了調(diào)度，但在實(shí)際生產(chǎn)環(huán)境中，分配的資源還包括例如網(wǎng)絡(luò)帶寬、磁盤IO、緩存等是本文沒(méi)有考慮的。在未來(lái)的工作中，將嘗試使用容器技術(shù)對(duì)磁盤IO 和網(wǎng)絡(luò)帶寬進(jìn)行限制，并綜合考慮這些因素對(duì)應(yīng)用執(zhí)行的影響，進(jìn)一步提高算法的調(diào)度效果。