蘇超 梁毅

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

關(guān)鍵詞：混部負(fù)載;資源分配;模擬退火算法

DOI： 10. 11907/rjdk.191243

開放科學(xué)（資源服務(wù)）標(biāo)識碼（OSID）：

中圖分類號：TP306

文獻(xiàn)標(biāo)識碼：A

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

0 引言

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

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

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

1 離線負(fù)載完成時間預(yù)測

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

1.1 關(guān)鍵因素選取

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

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

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

1.2 CART回歸樹算法及應(yīng)用建模

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

2 基于多目標(biāo)優(yōu)化的資源分配策略

2.1 模擬退火算法

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

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

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

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

2.2 基于模擬退火的離線負(fù)載資源調(diào)度策略

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

2.2.2 能量的定義

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

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

2.2.3 產(chǎn)生函數(shù)的定義

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

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

過程1：離線作業(yè)資源分配策略

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

3 性能評估

3.1 實驗環(huán)境及負(fù)載選取

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

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

3.2 實驗結(jié)果與分析

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

4 結(jié)語

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

參考文獻(xiàn)：

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

[2] 陳興業(yè).評估計算機系統(tǒng)性能的一種方法[J].華南工學(xué)院學(xué)報：自然科學(xué)版，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] 李勇，張章，孟丹，等.面向混合負(fù)載的集群資源彈性調(diào)度[J].高技術(shù)通訊.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.