云平臺下基于截止時間的自適應調度策略

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

（天津市智能信號與圖像處理重點實驗室（中國民航大學），天津 300300）

0 引言

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

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

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

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

綜上所述，對具有不同資源需求的任務進行調度時，資源預留式和資源預測等方法都有其局限性，搶占式調度簡單而快速，能有效保障任務的服務質量，但現有的搶占式調度沒有考慮到被搶占任務的執行情況。針對這一問題，本文提出了一種可以有效兼顧搶占任務的響應速度以及被搶占任務的完成時間調度算法。

本文的工作有：1）實現了一種以提交截止時間代替用戶指定固定資源的任務提交方式；2）提出了一種自適應資源分配策略，根據任務提交的截止時間和任務的實際執行情況自適應地分配資源；3）提出了一種用于調度不同服務質量需求任務的調度策略，基于搶占式調度策略的思想，優先滿足短作業的響應速度，然后補償額外資源用于長作業的執行。

1 分布式計算框架Spark

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

圖1 Spark的任務執行模型Fig.1 Task execution model of Spark

2 基于容器的搶占式任務調度策略

目前Spark 已經成為最流行的計算框架之一，Spark 將Task 的計算結果緩存到內存中供后續Task 使用，因此在迭代計算以及Task 非常多的應用中擁有顯著的優勢。然而相關研究［25］表明，在面對搶占式任務調度時，Spark 更容易受到搶占式調度的影響。主要原因有以下幾點：1）Spark 中運行的任務執行器采用多線程模型，對一個容器的搶占會影響多個任務；2）對于具有迭代計算的Spark 作業，任務涉及容器間的頻繁切換；3）由于Spark 基于內存計算的特點，從搶占容器中回收內存可能會導致嚴重的內存交換。

基于以上幾點原因，本文參考dynaSpark［26］的動態資源調度方法，在此基礎上提出一種搶占式任務調度方法，工作流程分為以下四步：

第一步 用提交截止時間的方式替代固定的資源分配并將隨任務提交的截止時間進行劃分，分成每個階段的截止時間deadlines。

第二步 根據預執行結果啟發式地分配給各個Executor相應的計算資源作為初始資源。

第三步 實時監測任務執行進度，比較其與預期進度的誤差，根據誤差對本節點上的容器進行資源調整，保證各階段任務以及整個應用在截止時間附近完成。

第四步 多作業并行執行時，根據用戶設定的優先級分配給不同應用相應的計算資源。

為了擴展Spark 實現動態資源分配的功能，對Spark 原有的體系結構和處理模型進行修改。如圖2，為改進后的系統框架，無底色部分為Spark 基礎結構，有底色部分為添加的 組件。

圖2 改進后的Spark架構Fig.2 Improved Spark architecture

為了動態調整任務運行過程中分配給Executor 的計算資源，每個Executor 進程都運行在以Docker Engine 為基礎的容器中，并且每個Worker 節點都部署有Control 組件負責實時監測每個Executor 中任務集的完成情況，根據實時任務完成情況，動態調整分配給Executor 的CPU 核數。在Master 節點中，Memory Manager 負載管理分配給應用的內存大小，根據提交的任務數量動態調整堆外內存。

2.1 Deadline劃分

擴展后的Spark 利用容器（即Docker［27］）來支持更靈活、細粒度的資源管理，通過將每個執行器部署在一個容器中，以允許動態地改變提供給執行器的計算資源。具體來說，用戶可以使用一個額外的參數deadline來豐富命令提交，以指定此應用期望的執行時間。動態分配資源的目標是在不違反截止日期的情況下最大限度地減少資源的使用，相較于提交之前確定分配給應用固定的計算資源，這種分配資源的方式更具可控性，因為預估任務計算時間是十分困難的。

相較于給完整的應用程序分配資源，由于階段是由具有不同復雜程度的不同操作組成的，對每個階段進行單獨的控制更為合理。因此，每個應用程序都使用基于啟發式的算法來計算每個階段的截止日期deadlines。當一個階段s提交執行時，使用以下公式計算初步截止日期：

其中：spentTime是已經花費在執行應用程序上的時間；appDeadline是用戶提交的應用的持續時間表示的截止時間；α∈[0，1]是一個常數，用來設置遵守截止時間的保守程度。如果α=1，執行時間將被控制嚴格地滿足截止時間，而對于較小的α值，控制將更加保守。ωs為階段的權重，計算如下：

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

由于在分析期間也就是預執行期間，測量的性能可能不同于在運行時的性能，為了避免過度擬合分析數據，使用常數β來減輕擬合。所有的ωs都是在運行時計算的，因為如果DAG 中有并行線程，就不能先驗地知道階段執行的順序。

2.2 啟發式控制階段

得到階段的截止時間后，為執行階段而分配的CPU 核心數量被估計為：

其中：inputRecords是必須由s處理的記錄數量；nomRates提供s的標稱速率，即單個核心每秒處理的記錄數量（在分析期間獲得）。輸入記錄取決于DAG 中父節點寫入的數據總和（即父節點產生的記錄總和）。

最后一步計算內核的初始數量和每個不同執行器要處理的任務數量。通過為每個Worker 節點的每個階段創建一個執行器，在所有可用的Worker 節點之間平均分配負載。通過這種方式，每個執行器都持有相同數量的任務，因此在shuffle 過程中遠程讀取相同數量的數據，這意味著可以為所有執行器計算相同的截止日期。每個執行器的初始內核數計算如下：

其中：numExecutors是執行器的數量，始終等于工作節點的數量；cq代表內核數量，這是一個定義應用于資源分配的量化的常數，值越小，分配越精確。

在本文的實驗中，設置cq=0.05，以分配精度高達0.05的內核，并獲得較低的誤差。初始分配的資源不需要非常精確，因為后面會根據任務的執行進度自適應地資源分配。

2.3 基于容器的動態資源調度

初始資源分配完成后，任務開始運行，Worker 節點上的Control 組件會根據任務執行進度動態分配資源，實現動態資源調度的關鍵技術由兩部分組成：第一部分是容器技術Docker，通過Docker 的CPU 周期分配技術實現對運行期間的Executor 進行資源調度；第二部分則是實時控制部分，通過分析實時的任務完成率，當實時完成率低于預期完成率則增加計算資源，反之則減少資源。由此，應用程序在運行過程中可以根據執行進度進行資源的分配，然后在截止時間附近完成。

2.3.1 容器技術概述

目前大多數大數據應用程序都是用托管語言（Managed Programming Language）編寫，以實現跨機器的可移植性，以Spark 為例，當Executor 部署到Worker 節點上時，節點首先需要啟動一個JVM 來執行它們。其中CPU 內核的分配是靜態的，由一個簡單的內部線程池管理，并且Executor 與應用綁定，即使當前的Executor 沒有任務運行，只有當整個應用結束時，資源才能釋放。另一個重要的參數是JVM 的堆大小，它的錯誤配置會導致任務失敗：設置堆大小太小可能會導致JVM 內存不足（Out Of Memory，OOM）錯誤，任務將失敗；設置堆大小太大可能會導致后續應用程序資源不足導致過長的延遲。在運行任務之前，很難甚至不可能確定最佳的JVM堆大小。

與基于虛擬機管理程序的虛擬化相比，基于容器的虛擬化技術，例如Docker，由于它幾乎可以忽略不計的開銷而變得流行。容器為容器內運行的應用程序提供獨立的名稱空間，并形成資源核算和分配單元。Linux 使用控制組群（cgroups）來精確控制容器的資源分配。有了容器，任務可以以大的JVM 堆大小啟動，用戶可以使用cgroups 來限制托管容器的內存使用，以防止系統內存崩潰。重要的是，即使任務的堆使用量超過了它的容器內存大小（因為堆的大小要大得多），任務也不會遇到OOM 錯誤，而是會開始內存交換。

2.3.2 動態資源分配

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

例如，對于擁有一個單核CPU 的節點，設定100 ms 的周期，如果給容器1 的配額為30 ms，給容器2 的配額為70 ms，那么70%的CPU 時間留給容器2，30%留給容器1。

分配原則遵循完全公平調度（Completely Fair Scheduler，CFS）［28］，這種機制是確定性的，非常細粒度，實現也非常地快速，一次分配通常能在幾百毫秒內完成。

Spark 的Executor 實際上是在Worker 節點中啟動的CoarseGrainedExecutorBackend 類進程中維護的一組線程池，改進后的系統將其封裝在Docker 鏡像內，啟動Executor 時分配初始參數，之后Control 組件實時監控Executor 的工作狀態，計算實時的資源需求，得到需要的資源數量后，執行Docker update 命令對容器的資源進行調整。cpu-period 參數用來指定容器對CPU 的使用要在多長時間內做一次重新分配；而cpu-quota 參數是用來指定這個周期內，最多可以有多少時間來運行此容器。例如要為一個Executor 分配cores 為2.5 的CPU 資源，設置參數cpu-period 為100 000、cpu-quota 為250 000。

2.4 搶占式任務調度

2.4.1 應用內存分配

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

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

對所有應用程序進行平均分配并不是最優的，但當工作負載未知時，這也是一種保守的解決方案。

2.4.2 基于優先級CPU分配策略

對于傳統的Spark 框架，CPU 的分配在應用提交時就已經確定。傳統的搶占式任務調度策略下，當集群資源不足以滿足作業的資源要求時，就只能取消正在運行的任務并且回收資源，以便新提交任務的執行。本文提出了一種更為友好的任務搶占方法。同樣地，用戶提前為作業劃分好優先級，系統根據優先級向應用程序分配資源；不同的是，提交作業時用戶不需要提交固定的資源需求，作業不會出現排隊現象，任務運行時，系統收集節點上資源請求信息，根據給定的任務優先級給提出申請的任務進行排序，按排序順序依次分配任務的資源申請，這樣在資源不足時，優先級高的任務申請的資源會被優先滿足，低優先級的任務只能被分配剩余的資源。

如果任務每次的資源申請都能滿足，就會在實驗設定的deadline內完成任務，否則在搶占的任務完成后，對被搶占的任務進行資源補償。

2.5 改進算法偽代碼

改進的搶占式任務調度算法的偽代碼如下：

輸入 用戶設定的應用截止時間appDeadline；

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

3 實驗與結果分析

本文在5 個節點集群上對改進后的方法進行了評估。所有實驗都使用了帶有4 個CPU、12 GB 內存和500 GB 本地固態硬盤存儲的服務器，各軟件版本信息如表1 所示。

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

實驗首先測試改進后平臺的動態資源調度功能（見3.1節）；接下來，展示了任務搶占時的資源調度情況，描述了出現資源競爭時系統的調度結果（見3.2 節）；最后對比在不同負載下本文方法與傳統的調度策略的實驗結果（見3.3 節）。

3.1 動態資源調度實驗

為了評估算法如何動態分配CPU 內核，本文使用了來自兩個基準測試套件的8 個應用程序。其中aggr-by-key（以下簡稱abk）、aggr-by-key-int（簡稱abk-int）、group-by、sort-by-key（簡稱sbk）和sort-by-key-int（簡稱sbk-int）強調基本的聚合和排序功能，來自SparkPerf。KMeans、SVM 和PageRank 來自SparkBench，這三個應用是常見的具有迭代運算的例子，前兩個是用于分類的機器學習應用程序，第三個則是著名的網頁排名算法。前五個應用程序不包含分支或循環，后三個是迭代的，但是迭代次數在開始時通過參數配置。這意味著每個程序的所有執行都有相同的DAG。各個應用使用的數據集是使用配套的基準測試套件中提供的工具和按照表2 中的參數設置隨機生成的。

表2 測試數據集參數設置Tab.2 Test dataset parameter setting

實驗分為兩個步驟，首先使用Spark 來運行每個應用程序，分配給每個任務所有的可用資源，即4 臺worker 節點的16 個CPU 核心，把以這種方式提交的作業的執行時間設定為測試基線（testBase）。

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

表3 作業參數設置Tab.3 Job parameter setting

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

圖3 CPU動態分配過程Fig.3 CPU dynamic allocation process

表4 顯示了用不同實驗測試得到的控制精度的結果。表中顯示了在實驗過程中是否發生了違反截止時間的現象以及任務完成時間與截止時間之間誤差的最小值（errormin）、最大值（errormax）、平均值（errormed）和標準偏差（std）。

表4 截止時間測試的實驗結果Tab.4 Experiment results of deadline test

表4 實驗結果顯示，放寬截止時間為基準測試時間的20%時，不會出現違反截止時間的情況出現，當資源充足時，能夠嚴格地控制任務的完成時間在截止時間之內。當設定截止時間為基準測試時間時會出現違反截止時間現象，但是整體的平均誤差控制在1%左右。實驗結果還表明在調度計算密集型任務時的效果要比調度數據密集型任務時的效果更好，這是由于計算密集型任務對CPU 資源更為敏感。

3.2 搶占式任務調度實驗結果

為了描述搶占式任務調度的資源分配過程，提交Sparkperf 中的aggr-by-key 作為短作業，SparkBench 中的PageRank作為長作業，模擬出實際生產中搶占式調度的場景。

實驗結果如圖4 所示，圖4（a）是作業A 單獨運行時的資源利用情況，圖4（b）是提交任務A 搶占任務B 時兩個應用的資源分配情況。結果顯示優先級高的任務能搶占低優先級的任務，當搶占任務完成之后，被搶占的任務會被分配額外的資源來補償執行的損失。

圖4 搶占式調度資源分配實驗結果Fig.4 Results of preemptive scheduling resource allocation experiments

由圖4（b）所示：當任務B 提交后，節點同時接收來自任務A 與任務B 的資源申請，由于任務B 的優先級高，節點會優先分配資源給任務B 來滿足其截止時間，此時任務A 的申請得不到響應。當任務B 結束后，任務A 的申請才會得到響應，此時由于與期望執行進度相差很大，任務A 會申請大量的資源來補償之前執行進度的損失。

與其他的搶占式調度做對比實驗結果如圖5 所示：基于YARN 調度框架的搶占式調度，在響應延遲以及對長作業的執行進度的丟失都很嚴重；BiG-C 方法［29］用特有的方式，暫時掛起被搶占的長作業，從而避免了長作業執行進度的丟失，縮短了長作業的執行時間；而本文方法通過額外補償長作業的模塊，使長作業的執行時間更短。

圖5 本文方法與其他搶占式方法的執行時間對比實驗結果Fig.5 Comparison experimental results of execution time between proposed method and other preemptive methods

3.3 對比實驗

經過前面的兩個實驗，驗證了改進后框架動態調度資源的能力，以及本文算法的搶占效果。本實驗則進一步與其他傳統調度方法對比，模擬生成工作負載，分別在低負載和高負載環境下評估短作業的響應速度以及長作業的執行時間。

3.3.1 工作負載

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

為了進行調度效果的比較，分別配置以下幾種調度方法：

1）先進先出調度（FIFO）：程序以先進先出的順序執行任務，不需要額外設置。

2）資源預留調度（Reserve）：YARN 模式下配置了兩個隊列。為短作業保留40%的集群資源，為長作業隊列配置60%的群集容量。

3）搶占式任務調度（kill-base）：YARN 模式下capacity scheduler 用于強制隊列之間的共享，設置短作業默認40%的資源使用，搶占時可達到80%的資源使用。

4）本文方法：先進行預執行，得到在資源充足情況下應用的平均執行時間，將平均執行時間設置為截止時間（deadline），并將短作業標記為高優先級應用。

3.3.2 對比實驗結果及分析

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

圖6 低負載環境下作業執行時間的實驗結果Fig.6 Experimental results of job execution time in low load environment

在高負載下，由于短作業的資源預留低于峰值需求，因此Reserve 調度的效果會降低。圖7（a）顯示，kill-base 是高負載環境下表現最好的調度器，它通過搶占長作業的資源，始終將短延遲傳遞給短任務。本文方法也獲得了較好的效果，由于優先級的設置，當短作業和長作業同時申請資源時，會優先將資源分配給短作業，但長作業的一部分內存還會保留，所以調度效果不如kill-base。相比之下，FIFO 調度下短作業產生了很大的延遲，由于資源的不足，短作業需要等待長作業完成后才能進行調度。

對長作業來說。FIFO 調度在兩個場景下都實現了最好的調度結果，其次是Reserve 調度方法，調度效果都接近FIFO。圖7（b）顯示，調度結果最差的是kill-base 調度，由于需要始終滿足短作業的資源申請要求，即使在低負載情況下也會有長作業被取消。本文方法取得了與FIFO 相近的調度結果，相比于kill-base 的取消長作業釋放資源的搶占方式，本文方法會將長作業暫時掛起，等到短作業執行完畢后再將資源重新分配給長作業，并且會補償掛起時損失的執行進度，使長作業的平均執行時間縮短了35%左右。

圖7 高負載環境下作業執行時間的實驗結果Fig.7 Experimental results of job execution time in high load environment

實驗結果表明，在低負載時，集群資源充足，采用本文方法，短任務能被嚴格地控制在截止時間內完成以滿足服務質量。相較于其他的搶占式調度方法，本文方法在高負載環境下能有效地減輕被搶占作業受到的影響。

4 結語

在云計算環境中進行任務調度時，一個重要的問題就是如何調度在共享集群中具有不同服務質量要求的應用使響應時間和任務完成時間達到最小。本文通過修改Spark 調度框架，開發了基于截止時間的調度接口，提出并實現了一種基于動態資源調度的搶占式任務調度方法。通過實驗驗證了算法能實現基于優先級的搶占式調度，并且能夠額外補償被搶占任務的執行進度。由于實驗環境限制，本文簡化了在應用執行過程中影響應用完成時間的諸多因素，只對內存和CPU 等計算資源進行了調度，但在實際生產環境中，分配的資源還包括例如網絡帶寬、磁盤IO、緩存等是本文沒有考慮的。在未來的工作中，將嘗試使用容器技術對磁盤IO 和網絡帶寬進行限制，并綜合考慮這些因素對應用執行的影響，進一步提高算法的調度效果。