混部負載場景下離線負載資源調度策略研究

蘇超 梁毅

摘 要：混部負載是當前業界提高數據資源利用率的重要手段，其原理是將在線負載和離線負載共同放置于同一數據中心、共享資源，在保證在線負載服務質量的前提下，將空閑資源分配給離線負載。當前針對混部負載中離線負載的資源調度采用傳統的公平或者短作業優先等策略，并未考慮在線負載資源需求波動對離線負載運行的影響。為了達到進一步提升資源利用率和作業吞吐率的目的，提出基于負載完成時間預判的模擬退火資源分配策略。結果表明，該策略比公平策略和短作業優先策略在平均資源利用率上分別提高了7.8%和15.5%，在吞吐率上分別提高了38.2%和29.1%。

關鍵詞：混部負載;資源分配;模擬退火算法

DOI： 10. 11907/rjdk.191243

開放科學（資源服務）標識碼（OSID）：

中圖分類號：TP306

文獻標識碼：A

文章編號：1672-7800（2020）001-0064-04

0 引言

大數據中心資源利用率低下的問題一直備受關注[1-3]。為了進一步提升其資源利用率，業界提出了}昆部負載技術[4-5]，它是指將延遲敏感型的在線負載與關注作業吞吐率[6]的離線負載混合部署于同一數據中心。混部負載的目標是提升原有單負載數據中心的資源利用率，并且優先保障在線負載的SLO以及最小化相應延遲[7-8]。由于在線負載是延遲敏感型的[9-10]剛，且其資源需求量已經可以通過科學的方法（如：機器學習、時間序列分析等）較為準確地加以預測[11-12]，因此，如何將數據中心的剩余資源合理分配給既有離線負載尤為重要。

資源調度是保障數據中心負載執行效率及資源利用率的關鍵技術。目前，針對混部負載的資源調度主要集中于在線負載，通過機器學習、時間序列分析等方法預測在線負載的資源需求，進行準確的資源供給，以保障在線負載的服務質量[13-14]。然而，針對離線批處理負載的資源調度往往采用較為傳統的公平或者短作業優先等策略，并未考慮在線負載資源需求波動對離線負載運行的影響[15-16]，這導致離線批處理負載在運行過程中產生資源搶占或資源碎片現象，降低了離線負載的運行效率以及數據中心資源的有效利用率[17]。

針對上述問題，本文提出基于完成時間預測的離線負載資源調度策略。該策略首先通過回歸樹算法對數據中心既有離線負載完成時間進行建模和預判，并在已知在線負載資源需求的情況下，采用模擬退火的多目標組合優化啟發式算法對離線負載進行更為合理的資源分配[18-19]。實驗表明，該策略比傳統的公平策略和短作業優先策略在平均資源利用率上分別提高了7.8%和15.5%，在作業吞吐率上分別提高了38.2%和29.1%。

1 離線負載完成時間預測

為了合理利用數據中心的空閑資源，本文采用CART回歸決策樹算法對當前數據中心離線負載的完成時間進行預判。

1.1 關鍵因素選取

為了預測離線負載完成時間，首先分析離線負載相關原理，探究影響負載完成時間的關鍵因素，然后通過實驗加以驗證。

一個離線負載在分布式平臺中會被分為多個任務進行計算，CPU數量代表了離線負載在相同時間可以同時運行的任務數量，在一定范圍內，并行計算的任務越多，計算速度越快，負載完成時間越短。在計算過程中，內存不足會導致和磁盤頻繁交換數據，消耗大量時間，相反，如果內存資源充足，則會降低這部分的時間開銷。并且，大部分大數據離線負載的技術棧都基于Java，而內存不足會引起大規模的垃圾回收，導致其它進程和線程被阻塞，從而降低負載完成效率。此外，數據規模大小顯然是影響負載完成時間的，一個小規模的數據片和大規模的數據集在完成時間上有明顯差異。因此，本文提出在資源配置一定的數據中心，內存數量、CPU數量和數據規模是影響離線負載完成時間的3個關鍵因素，并通過以下幾組page_rank實驗加以說明，相關數據如表1所示。

通過實驗分析可知，當內存資源和數據規模固定時，負載完成時間隨著CPU資源數量的增大而減小;在CPU資源數量和數據規模一定的情況下，隨著內存資源的增大，負載完成時間也會延長;在資源配置不變的情況下，隨著數據規模的縮小，負載完成時間也明顯降低。因此，驗證了內存、CPU資源配置和數據規模是影響負載完成時間的關鍵因素。

1.2 CART回歸樹算法及應用建模

CART回歸樹是一種典型的二叉決策樹，可以用作回歸建模，其所選取的特征劃分標準是Gainσ，即平方誤差最小[20]。選擇具有最小Gain盯的屬性及其屬性值，作為當前未劃分的特征集合中的最優分裂屬性以及最優分裂屬性值。具體模型構建方法如下：

2 基于多目標優化的資源分配策略

2.1 模擬退火算法

面對目標優化算法中常見的局部最優問題，模擬退火算法應運而生。該算法基于固體降溫的思想，一個固體內部的分子從某一較高的初始溫度開始，到某一溫度停止，伴隨溫度的不斷下降，分子的活性趨于穩定。在搜索解的過程中可能會出現局部最優現象，但是模擬退火算法會繼續搜索，并以一定的概率接受搜索過程中出現的非最優解，伴隨著溫度降低，接受概率逐漸下降，直到某一溫度停止，搜索結束，獲得全局最優解。該算法將一次向較差解的移動看作一次溫度跳變的過程，并且以一定的概率接受這樣的移動。這里“一定的概率”的計算就是參考了金屬冶煉的退火原理，在溫度為，時，出現能量差為AE的降溫概率為P（AE），其計算表達式為：

P（△E）=e（AElkT）（3）

其中，k是一個常數，通常情況下取值為1，△E=Enew-Eold在計算過程中一直小于0。這種基于一定概率接受的準則也被稱為M etropolis準則。

該算法是一種通用性的優化算法，算法具有概率性的全局優化性能，其特點是可以比較快地找到問題的最優解。在資源調度問題上，需要快速地將資源對離線負載進行分配，因此該算法適用于本文的場景。

2.2 基于模擬退火的離線負載資源調度策略

本文提出的策略追求兩個目標，一是在每一批離線批處理作業完成時間△tall batch內，數據中心離線批處理作業的吞吐率TR最大;二是在每一批離線批處理作業完成時間△t all batch內，數據中心的平均資源利用率pr最高。問題形式化表達如下：

2.2.2 能量的定義

在資源分配過程中，每一種不同的資源分配方式所達到的資源使用效果也不盡相同。因此，為了評價每一種資源分配方式的優劣程度，需要定義評級函數，在組合優化算法中，評價函數是評價一個解是否達到最優指標。模擬退火計算過程中，每一個退火階段的評價函數就是當前溫度下的能量E，由問題建模的表達可知，評價函數應該從當前分配方式下的平均資源利用率和離線作業的吞吐率兩個方面進行評估和考量。因此，當前能量表達式如下：

在式（11）中，w1、w2是吞吐率權重和平均資源利用率權重，可以設置其具體值，本文設定w1= W2= 0.5。

2.2.3 產生函數的定義

在同一溫度下迭代K次搜索最優解的過程中，設定K值為25。根據已有的解和產生函數生成新的解。新解的產生方法是通過交替改變負載的節點分配方案和開始運行時間形成的，具體而言，首先通過隨機生成節點組合Li，形成新的解;持續5次后，隨機生成新的負載開始運行時間，然后重復改變節點組合過程，直至K次迭代結束。其中，負載開始時間的生成方法是在時刻t0到所有負載串行執行完成的結束時間fn之間隨機生成一個時間點。

離線作業資源分配策略具體流程如下：

過程1：離線作業資源分配策略

首先定義初始資源分配組方式、初始溫度等相關參數，M_free表示可分配的內存集合，C_free表示可分配的CPU集合，ET表示離線負載預期完成時間集合。然后定義一個初始資源分配策略，并判斷該分配方式是否符合資源約束條件，不符合則重新生成直至符合條件。從初始資源分配方式在每一個溫度下經過K次搜索，每一次都是按照產生函數中所描述的方式產生下一個解，并結合Metrop-olis準則和評價函數判斷并產生當前溫度的最優解。隨著溫度降低，搜索得到全局最優策略，也即本文探索的最佳資源分配方式。

3 性能評估

3.1 實驗環境及負載選取

實驗環境是由5個節點組成的Spark集群，其中一個節點為主節點，4個節點為從節點。每個節點的硬件配置、軟件環境如表2所示。

本文共選取了4個典型的離線負載作為數據中心既有的離線批處理作業，分別為PageRank＼KMeans、SVD++和ShortPath。

3.2 實驗結果與分析

對不同數據量的離線作業進行組合并分組實驗，分組情況如表3所示。

4 結語

本文針對混部負載中離線負載資源使用問題，提出了基于多目標組合優化的分配策略，實現了最大化當前資源利用率和最大化吞吐率兩個目標。實驗結果表明，與公平分配策略相比，本文提出的策略在平均資源利用率上平均提高了7.8%，在吞吐率方面平均提高了38.2%;與短作業優先策略相比，在平均資源利用率上平均提高了15.5%，在作業吞吐率方面平均提高了29.1%。下一步的研究方向是對資源進行細粒度劃分和更為合理的利用。

參考文獻：

[1]王晨晨，孫睿.淺析大數據的發展[J]中國市場，2018（ 27）：194，196.

[2] 陳興業.評估計算機系統性能的一種方法[J].華南工學院學報：自然科學版，1987（1）：16-22.

[3] DELIMITROU C，KOZYRAKIS C.Quasar： resource-efficient andQoS-aware cluster management [J]. ACM SIGPLAN Notices， 2014，49（4）：127-144.

[4] 李勇，張章，孟丹，等.面向混合負載的集群資源彈性調度[J].高技術通訊.2014（8）：782-790.

[5]JYOTHI S A. CURINO C， MENACHE I， et al.Morpheus： towards au-tomated SLOs for enterprise clusters[C].OSDI， 2016：1 17-134.

[6]SALEHI M A， JAVADI B， BUYYA R.Resource provisioning based onpreempting virtual machines in resource sharing environments [J].Concurrency and Computation： Practice&Experience， 2013： 1-21.

[7]NAWAZ M， ENSCORE JR E E，HAM I.A heuristic algorithm for them-machine， n-job flow-shop sequencing problem[J].Omega， 1983，11（1）：91-95.

[8]VERMA A， PEDROSA L，KORUPOLU M， et al.Large-scale clustermanagement at Coogle with Borg[C].Bordeaux： ACM Tenth EuropeanConference on Computer Systems， 2015.

[9]BANKOLE A A， AJILA S A.Cloud client prediction models for cloudresource provisioning in a multitier web application environment[C].IEEE International Symposium on Service Oriented System Engineer-ing， 2013：156-161.