面向大數(shù)據(jù)分析作業(yè)的啟發(fā)式云資源供給方法*

吳悅文 , 吳 恒 , 任 杰 , 張文博 , 魏 峻,2, , 王 燾 , 鐘 華,2,

1(中國(guó)科學(xué)院 軟件研究所 軟件工程技術(shù)中心,北京 100190)2(天基綜合信息系統(tǒng)重點(diǎn)實(shí)驗(yàn)室(中國(guó)科學(xué)院 軟件研究所),北京 100190)3(中國(guó)科學(xué)院大學(xué),北京 100049)

云計(jì)算已成為大數(shù)據(jù)分析作業(yè)的主流運(yùn)行支撐環(huán)境,Gartner 數(shù)據(jù)顯示,超過半數(shù)的全球大型組織已使用云計(jì)算進(jìn)行大數(shù)據(jù)分析[1].其中,40%的大數(shù)據(jù)分析作業(yè)具有周期性處理相似規(guī)模數(shù)據(jù)的特點(diǎn),例如銷售額日統(tǒng)計(jì)等.相關(guān)研究表明,適合的云資源供給對(duì)于優(yōu)化大數(shù)據(jù)分析作業(yè)性能和節(jié)約成本具有重要意義.如Ernest[2]對(duì)比了云資源的人工選擇和優(yōu)化配置,大數(shù)據(jù)分析作業(yè)的性能會(huì)相差2 倍～3 倍,CherryPick[3]認(rèn)為:在相同的大數(shù)據(jù)分析作業(yè)性能前提下,云資源成本可能會(huì)相差12 倍.已有研究主要分為兩類:一類是模型驅(qū)動(dòng),面向特定的大數(shù)據(jù)分析框架進(jìn)行建模,如Elastisizer[4],MRTuner[5],Ernest;另一類是采用機(jī)器學(xué)習(xí)方法,具有與大數(shù)據(jù)分析框架松耦合的優(yōu)勢(shì),逐漸成為近年來研究的熱點(diǎn),典型工作如CherryPick.

然而,周期性作業(yè)的云資源供給面臨樣本少、搜索空間過大的問題,容易陷入局部最優(yōu)解.如圖1 所示,機(jī)器學(xué)習(xí)典型方法CherryPick 找到全局優(yōu)化解的樣本個(gè)數(shù)(縱軸)隨著云資源配置數(shù)量(橫軸)增加而增長(zhǎng),特別是在候選方案超過66 個(gè)時(shí)(CherryPick 實(shí)驗(yàn)上限).在本文,云資源配置是指主機(jī)個(gè)數(shù)和云主機(jī)類型(計(jì)算、內(nèi)存、網(wǎng)絡(luò))的選擇.

Fig.1 Samples for picking up global optimal of CherryPick (TeraSort)圖1 CherryPick 選出全局優(yōu)化解的采樣次數(shù)(TeraSort)

本文提出了大數(shù)據(jù)環(huán)境下基于負(fù)載分類的啟發(fā)式云資源供給方法RP-CH(resource provisioning based on classification and heuristic),基于云資源共享特點(diǎn),獲取其他大數(shù)據(jù)分析作業(yè)的運(yùn)行時(shí)監(jiān)測(cè)數(shù)據(jù)和云資源配置信息,建立大數(shù)據(jù)分析作業(yè)分類與優(yōu)化云資源配置的啟發(fā)式規(guī)則,并將該規(guī)則作用到貝葉斯優(yōu)化算法的收益函數(shù)AC(acquisition function),可減少貝葉斯優(yōu)化算法搜索空間,在小樣本下可快速收斂找到優(yōu)化的資源供給方案.

本文的主要貢獻(xiàn)如下.

(1) 設(shè)計(jì)面向大數(shù)據(jù)分析作業(yè)的分類器,建立大數(shù)據(jù)分析作業(yè)分類與優(yōu)化云資源配置的啟發(fā)式規(guī)則,通過計(jì)算新的大數(shù)據(jù)分析作業(yè)與歷史性能數(shù)據(jù)(CPU、內(nèi)存、磁盤和網(wǎng)絡(luò))的弗雷歇距離(Fréchet distance)[4],對(duì)新的大數(shù)據(jù)分析作業(yè)進(jìn)行歸類;

(2) 將啟發(fā)式規(guī)則通過貝葉斯優(yōu)化的AC函數(shù)進(jìn)行表示,其目的是在不影響優(yōu)化結(jié)果的前提下減少搜索空間,在樣本少、搜索空間大的場(chǎng)景下,解決冷啟動(dòng)和K階欺騙問題,提高小樣本下找到全局優(yōu)化解的概率;

(3) 通過實(shí)驗(yàn)驗(yàn)證RP-CH 在相同的小樣本下,相比于CherryPick,大數(shù)據(jù)分析作業(yè)的性能平均提升了58%,成本平均減少了44%.

本文第1 節(jié)為當(dāng)前相關(guān)工作的分類與總結(jié).第2 節(jié)闡述問題分析和研究思路.第3 節(jié)介紹啟發(fā)式規(guī)則的建立.第4 節(jié)介紹RP-CH 算法.第5 節(jié)為實(shí)驗(yàn),驗(yàn)證小樣本下資源供給的應(yīng)用性能和資源成本.第6 節(jié)對(duì)本文工作進(jìn)行總結(jié),并對(duì)未來工作進(jìn)行展望.

1 相關(guān)工作

目前,云資源供給方法的研究主要面向兩大主要應(yīng)用場(chǎng)景,即傳統(tǒng)服務(wù)類應(yīng)用和大數(shù)據(jù)分析應(yīng)用.由于兩種應(yīng)用類型的特征不同,相關(guān)工作關(guān)注的研究?jī)?nèi)容也有所區(qū)別.傳統(tǒng)服務(wù)類應(yīng)用(如Web 服務(wù)器、數(shù)據(jù)庫(kù)等)需要長(zhǎng)時(shí)間運(yùn)行(數(shù)月)在云服務(wù)器上,且資源需求的特征相對(duì)確定(如峰值),因此對(duì)于此類應(yīng)用,通常根據(jù)其資源需求做出資源使用的事前規(guī)劃,以提升應(yīng)用性能和云服務(wù)器的資源利用率;另一方面,大數(shù)據(jù)分析應(yīng)用相比于傳統(tǒng)服務(wù)類應(yīng)用,其運(yùn)行周期通常較短(幾分鐘～數(shù)小時(shí)),且資源需求的特征具有不確定性[6],因此對(duì)于此類應(yīng)用,通常根據(jù)數(shù)學(xué)模型進(jìn)行應(yīng)用的性能預(yù)測(cè)和估算,以匹配最優(yōu)云資源配置,進(jìn)而提升應(yīng)用性能和減小云資源成本.

面向大數(shù)據(jù)分析的云資源供給方法主要分為性能建模和機(jī)器學(xué)習(xí)兩類.

· 性能建模方法

通過分析計(jì)算框架運(yùn)行原理,采用如控制理論、排隊(duì)論等理論基礎(chǔ)來進(jìn)行性能預(yù)測(cè),并據(jù)此推薦資源供給方案.MRTuner[6]對(duì) Hadoop 系統(tǒng)內(nèi)部運(yùn)行原理進(jìn)行分析,并將 Hadoop 作業(yè)分解成 Producer-Transporter-Consumer 這3 個(gè)階段,根據(jù)控制理論分別估算作業(yè)各個(gè)階段的調(diào)度、計(jì)算和數(shù)據(jù)傳輸?shù)臅r(shí)間開銷,并最終匯總為作業(yè)的完成時(shí)間.Elastisizer[12]基于排隊(duì)論分析MapReduce 執(zhí)行過程中由于資源受限導(dǎo)致的作業(yè)等待現(xiàn)象,將MapReduce 作業(yè)劃分成多個(gè)批次執(zhí)行,通過日志分析、代碼插樁等手段收集數(shù)據(jù),最終精確估算作業(yè)分批次執(zhí)行的完成時(shí)間.此類方法基于運(yùn)行原理分解作業(yè),使得估算的準(zhǔn)確性較高;缺點(diǎn)在于方法需要對(duì)目標(biāo)系統(tǒng)有很深的理解,尤其在面對(duì)眾多大數(shù)據(jù)分析框架時(shí)難以復(fù)用同一個(gè)模型,難以應(yīng)對(duì)大數(shù)據(jù)分析框架多樣性特點(diǎn).

· 機(jī)器學(xué)習(xí)方法

對(duì)計(jì)算框架進(jìn)行抽象,收集通用數(shù)據(jù)并建立學(xué)習(xí)系統(tǒng),用于預(yù)測(cè)新作業(yè)的資源需求和性能.AROMA[7]收集作業(yè)執(zhí)行過程中底層資源計(jì)數(shù)器的數(shù)據(jù),采用聚類算法對(duì)作業(yè)的類型進(jìn)行聚類,將資源估算問題轉(zhuǎn)化為計(jì)算點(diǎn)到平面之間的距離.Ernest[8]面向分布式計(jì)算框架,根據(jù)統(tǒng)計(jì)分析將作業(yè)劃分成多對(duì)一、樹狀、多對(duì)多等3 種數(shù)據(jù)交互模式,并據(jù)此建立模型,利用離線分析過程的小規(guī)模采樣樣本對(duì)模型進(jìn)行參數(shù)學(xué)習(xí),從而獲得配置與性能之間的模型關(guān)系.CherryPick[2]提出了采用貝葉斯優(yōu)化算法來進(jìn)行資源推薦,只需記錄作業(yè)的完成時(shí)間和云資源配置,通過統(tǒng)計(jì)概率分析下一個(gè)潛在的更優(yōu)配置,并不斷迭代逼近最優(yōu)配置.此類方法通常采用跨平臺(tái)通用的數(shù)據(jù)如性能數(shù)據(jù)、交互模式作為特征,屏蔽了作業(yè)的執(zhí)行細(xì)節(jié),模型的通用性更強(qiáng).與此同時(shí),學(xué)習(xí)方法依賴于數(shù)據(jù)樣本的訓(xùn)練結(jié)果,而獲取足夠多數(shù)據(jù)樣本的成本過高.相關(guān)工作權(quán)衡利弊之后,往往采用小樣本和有限的迭代獲取數(shù)據(jù)[8,9],學(xué)習(xí)的結(jié)果容易陷入局部最優(yōu)解,準(zhǔn)確性難以保障.

本文提出了兩階段的云資源供給方法,即離線負(fù)載分類階段和在線搜索階段.與我們之前的研究工作[10]相比較,本文在負(fù)載分類的方法上有所改進(jìn),不再通過人工設(shè)置閾值的方式來劃分負(fù)載類型,而改為采用測(cè)算資源使用曲線的相似度,提升了系統(tǒng)對(duì)于負(fù)載變化的場(chǎng)景適用性.

綜上所述,已有研究采用機(jī)器學(xué)習(xí)的方法應(yīng)對(duì)大數(shù)據(jù)分析框架的多樣性特點(diǎn),但在小樣本下容易陷入局部最優(yōu)解.

2 問題分析和研究思路

2.1 問題定義

本文的目標(biāo)是根據(jù)作業(yè)的資源需求推薦優(yōu)化的云資源供給方案,在保障作業(yè)性能的同時(shí),盡可能降低資源成本.形式化地,大數(shù)據(jù)分析作業(yè)的資源供給問題可用如下公式定義.

其中,是以向量表示的作業(yè)特征和云資源配置的集合,作業(yè)特征主要指作業(yè)數(shù)據(jù)量大小,云資源配置包含主機(jī)個(gè)數(shù)、內(nèi)存大小、CPU核心數(shù)、磁盤帶寬、網(wǎng)絡(luò)帶寬等屬性;表示在配置下運(yùn)行作業(yè)的完成時(shí)間;表示配置下單位時(shí)間產(chǎn)生的費(fèi)用;Tmax為用戶的期望時(shí)間;C()表示在下運(yùn)行作業(yè)所需要的成本.則問題定義為在找到用戶期望時(shí)間Tmax內(nèi)的資源供給方案,同時(shí)該方案的C()成本最小.

2.2 研究思路

本文通過收集其他作業(yè)運(yùn)行時(shí)監(jiān)控和云資源配置信息,對(duì)目標(biāo)作業(yè)進(jìn)行分類,建立基于負(fù)載分類信息的啟發(fā)式規(guī)則,并將啟發(fā)式規(guī)則作用到貝葉斯優(yōu)化的AC函數(shù).形式化地,與啟發(fā)式規(guī)則結(jié)合的貝葉斯優(yōu)化RP-CH 的目標(biāo)函數(shù)見公式(2):

然而,如何建立啟發(fā)式規(guī)則,并實(shí)現(xiàn)基于啟發(fā)式規(guī)則的云資源供給算法面臨挑戰(zhàn),具體的分析如下所述.

1)啟發(fā)式規(guī)則的建立.啟發(fā)式規(guī)則建立在作業(yè)分類的基礎(chǔ)之上,作業(yè)分類的難點(diǎn)在于相同作業(yè)在不同云資源配置下執(zhí)行結(jié)果存在差異,單純統(tǒng)計(jì)作業(yè)的平均資源利用率難以做到準(zhǔn)確分類.如何對(duì)作業(yè)進(jìn)行分類,并建立作業(yè)分類信息與云資源供給優(yōu)化的啟發(fā)式規(guī)則面臨挑戰(zhàn);

2)啟發(fā)式規(guī)則的表示.傳統(tǒng)貝葉斯優(yōu)化算法在樣本少、搜索空間大時(shí)容易陷入局部最優(yōu)解是因?yàn)樗惴ù嬖诶鋯?dòng)和K階欺騙問題[11],本文的思路是通過啟發(fā)式規(guī)則減少樣本搜索空間,優(yōu)化樣本選擇.如何將啟發(fā)式規(guī)則表示為貝葉斯優(yōu)化采樣過程面臨挑戰(zhàn).

3 啟發(fā)式規(guī)則的建立

3.1 特征的選擇

相關(guān)研究表明[12],當(dāng)前企業(yè)內(nèi)部運(yùn)行的作業(yè),可根據(jù)作業(yè)負(fù)載的資源使用特征,將作業(yè)分為計(jì)算密集型作業(yè)、I/O 密集型作業(yè)和混合型作業(yè).計(jì)算密集型作業(yè)在作業(yè)執(zhí)行過程中存在大量的計(jì)算步驟,對(duì)于CPU 個(gè)數(shù)、CPU 主頻、內(nèi)存大小、CPU 內(nèi)存比率等與運(yùn)算相關(guān)的屬性比較敏感.如浮點(diǎn)運(yùn)算程序、天文運(yùn)算、圖形處理等等.I/O 密集型作業(yè)特點(diǎn)是運(yùn)行過程中需要進(jìn)行大量的數(shù)據(jù)交換、傳輸,主要操作為數(shù)值交換、節(jié)點(diǎn)間通信、數(shù)據(jù)的讀寫等,以網(wǎng)絡(luò)帶寬、磁盤大小、磁盤讀寫速度等為主要資源瓶頸的作業(yè),如簡(jiǎn)單排序、SQL 聚合等作業(yè).如果作業(yè)同時(shí)具備計(jì)算密集型特征和I/O 密集型特征,則定義為混合型作業(yè),如流式計(jì)算、數(shù)據(jù)清洗等作業(yè).研究表明:具有相似資源需求的數(shù)據(jù)分析型作業(yè)的性能表現(xiàn)相近[13],每一類作業(yè)都存在云資源優(yōu)化與云資源屬性之間的關(guān)聯(lián)關(guān)系,如對(duì)一個(gè)IO 密集型作業(yè)進(jìn)行云資源配置推薦,同時(shí)提高磁盤帶寬、磁盤大小、網(wǎng)絡(luò)帶寬等屬性,則會(huì)更快地找到全局優(yōu)化解.

本文的云資源供給場(chǎng)景建立在云資源共享的前提條件下.以亞馬遜、微軟、阿里云為代表的主流云計(jì)算平臺(tái)具有用戶共享云資源的特性,云服務(wù)供應(yīng)商可以通過運(yùn)行時(shí)監(jiān)測(cè)和日志分析獲取其他作業(yè)執(zhí)行的資源使用和配置信息.

相關(guān)領(lǐng)域的研究工作中,采用運(yùn)行時(shí)監(jiān)測(cè)和日志分析等手段優(yōu)化求解過程是一種主流的研究手段[14-16].

3.2 負(fù)載分類

本文通過分析作業(yè)負(fù)載的資源使用偏好對(duì)作業(yè)進(jìn)行分類.具體的步驟如圖2 所示,首先分析歷史作業(yè)負(fù)載的資源使用曲線,通過分類器分析多維資源的使用曲線(CPU、內(nèi)存、磁盤、網(wǎng)絡(luò)),并將作業(yè)分為計(jì)算密集型、IO 密集型和混合型這3 種類型;當(dāng)新作業(yè)執(zhí)行時(shí),分類器將比較資源使用曲線的相似度,并判斷新作業(yè)的類型;最終,作業(yè)分類知識(shí)將應(yīng)用到RP-CH 算法中.

Fig.2 An example of RP-CH’s task classification working process圖2 作業(yè)分類的基本原理

在對(duì)作業(yè)負(fù)載進(jìn)行資源使用曲線的相似度比較時(shí),相關(guān)工作[17]通過操作系統(tǒng)底層的性能計(jì)數(shù)器收集數(shù)據(jù),將性能數(shù)據(jù)分別轉(zhuǎn)化成一組點(diǎn)集,并分別對(duì)點(diǎn)集計(jì)算基于最長(zhǎng)公共子序列(longest common subsequence,簡(jiǎn)稱LCSS)的距離,最終計(jì)算出來的距離數(shù)值成為作業(yè)類型判斷的標(biāo)準(zhǔn).

資源使用曲線相似度比較的難點(diǎn)是考慮云資源配置差異的影響.如圖3 所示,展示了阿里云云計(jì)算平臺(tái)中在不同云資源配置下運(yùn)行HiBench 的TeraSort,WordCount,SQL Aggregation 作業(yè)的結(jié)果,其中可明顯看出:TeraSort 和WordCount 的配置1 執(zhí)行比配置2 執(zhí)行的完成時(shí)間更長(zhǎng),曲線差異表現(xiàn)為時(shí)間軸上的圖像平移,SQL Aggregation 的兩次執(zhí)行結(jié)果的差異表現(xiàn)為局部數(shù)值上的縮放.由此可見:在比較數(shù)據(jù)分析型負(fù)載的資源使用曲線時(shí),需要統(tǒng)籌考慮云資源配置差異的時(shí)間翹曲距離(canonical warping distance)[18].

如圖4 所示,橫軸表示多種資源,縱軸表示距離,距離越小表示曲線越相似.相關(guān)工作中[19]采用基于點(diǎn)集相似度的計(jì)算方法LCSS,則結(jié)果將產(chǎn)生較大的誤差.如圖4(a)所示,LCSS 的結(jié)果顯示,TeraSort 和WordCount 的各種資源使用的距離總和更小,判斷兩者相似度更高.而實(shí)際上,TeraSort 在不同云資源配置下的兩次執(zhí)行應(yīng)該更相似,但由于云資源配置差異導(dǎo)致的圖像平移和局部數(shù)據(jù)縮放現(xiàn)象,如圖3(a)和圖3(d)所示:TeraSort 在兩種不同配置下的圖像差異,使得LCSS 方法出現(xiàn)較大的誤差.

為了解決云資源配置差異導(dǎo)致的相似度比較誤差問題,本文采用基于曲線形狀的相似度比較方法,其中,弗雷歇距離[20]應(yīng)用廣泛,具有較強(qiáng)的噪聲容忍性.其原理是:基于曲線斜率比較形狀相似度,根據(jù)斜率的差值在離散的點(diǎn)中間插入新的點(diǎn)以解決噪聲問題,增加形狀相似度比較的準(zhǔn)確性,對(duì)于噪聲引起的圖像平移和數(shù)值縮放有較好的效果.圖4(b)展示了Fréchet 算法的結(jié)果,最終判斷2 次TeraSort 執(zhí)行的資源曲線更相似,修正了云資源配置差異造成的誤差.

Fig.3 CPU utilization of TeraSort,WordCount and SQL Aggregation tasks during different configurations圖3 TeraSort,WordCount,SQL Aggregation 不同云資源配置下運(yùn)行的CPU 曲線圖

Fig.4 Distances for CPU,disk and network resources圖4 資源曲線的CPU、磁盤和網(wǎng)絡(luò)距離比較

3.3 啟發(fā)式規(guī)則

在獲取作業(yè)分類信息的基礎(chǔ)之上,通過啟發(fā)式規(guī)則構(gòu)建作業(yè)分類和云資源配置的關(guān)聯(lián)關(guān)系,用于RP-CH 算法中縮減搜索空間,并指導(dǎo)算法選擇下一個(gè)采樣點(diǎn),選擇的特征見表1,其中,{CPU memory ratio,CPU speed,disk sxpeed,network4 speed}這4 個(gè)特征集合用于判斷該向量是否與作業(yè)分類信息相匹配,例如,計(jì)算密集型作業(yè)符合{高,高,低,低}的特征集合(IO 資源需求低以降低資源成本);特征Scale memoryratio用于判斷向量的云資源配置是否滿足作業(yè)數(shù)據(jù)規(guī)模的資源需求,例如,當(dāng)Scale=40GB 的作業(yè)在總內(nèi)存≥40GB 的云資源配置方案中執(zhí)行效果更佳,取值范圍從0～50,表明本文實(shí)驗(yàn)環(huán)境中賦予“數(shù)據(jù)規(guī)模/內(nèi)存比率”的上限是50,是因?yàn)楫?dāng)該值超過50 時(shí),以Spark 為代表的內(nèi)存計(jì)算型Benchmark 可能因?yàn)閮?nèi)存不足而崩潰[21].

Table 1 System features selected from for building heuristic rules表1 特征向量 中用于構(gòu)建啟發(fā)式規(guī)則的特征

Table 1 System features selected from for building heuristic rules表1 特征向量 中用于構(gòu)建啟發(fā)式規(guī)則的特征

啟發(fā)式規(guī)則的函數(shù)表達(dá)式見公式(3):

其中,

·rate1代表云資源配置與作業(yè)負(fù)載分類的匹配程度,rate1由4 維的資源特征組成,由于負(fù)載的資源特征與云資源配置之間的匹配關(guān)系難以用單一規(guī)則進(jìn)行約束,因此本文設(shè)計(jì)了一個(gè)多維的啟發(fā)式規(guī)則,如圖5所示,橫軸代表4維資源,縱軸代表具體的資源配置(high,medium,low通過閾值控制,本文中設(shè)置為75%～100%,25%～75%,0～25%),圖中帶數(shù)值的元素(圓、三角和方形)代表云資源配置與負(fù)載的匹配度,例如:當(dāng)且作業(yè)屬于計(jì)算密集型時(shí),則rate1=(1-1+1+0)/4=0.25;

·rate2代表云資源配置與作業(yè)規(guī)模的匹配程度,對(duì)于大數(shù)據(jù)分析作業(yè)而言,數(shù)據(jù)規(guī)模與資源配置(可理解為數(shù)據(jù)處理能力)之間的關(guān)系將直接影響到作業(yè)性能,因此需要量化該指標(biāo)的影響[22];

· 參數(shù)θ1和θ2為rate1和rate2的影響因子.通過大量實(shí)驗(yàn)驗(yàn)證θ1:θ2=2:1 時(shí),啟發(fā)式規(guī)則的效果最佳,具體實(shí)驗(yàn)結(jié)果在后文第5.2 節(jié).

Fig.5 Heuristic rules based on jobs classification圖5 基于負(fù)載分類匹配度的啟發(fā)式規(guī)則

4 啟發(fā)式規(guī)則的表示

RP-CH 將啟發(fā)式規(guī)則作用到貝葉斯優(yōu)化的采樣過程中,通過作業(yè)負(fù)載的分類信息,強(qiáng)化匹配區(qū)間的樣本選擇,達(dá)到算法快速收斂的目的.RP-CH 的基本計(jì)算模型與貝葉斯優(yōu)化相似,通過不斷地迭代執(zhí)行進(jìn)行優(yōu)化,每次執(zhí)行即為一次算法采樣過程,在RP-CH 中加入了作業(yè)分類和啟發(fā)式規(guī)則應(yīng)用的步驟,算法基本流程如圖6 所示.

Fig.6 RP-CH workflow圖6 RP-CH 流程圖

算法的基本流程為:

1)采用啟發(fā)式規(guī)則結(jié)合作業(yè)的分類信息(通過首次執(zhí)行獲得)進(jìn)行初始選點(diǎn);

2)運(yùn)行作業(yè);

3)收集并分析作業(yè)負(fù)載的資源使用數(shù)據(jù),與系統(tǒng)中其他作業(yè)比較相似度,對(duì)該作業(yè)進(jìn)行分類;

4)啟發(fā)式規(guī)則結(jié)合AC函數(shù)從候選集中選出新的采樣點(diǎn),若新采樣點(diǎn)符合選點(diǎn)目標(biāo),則結(jié)束算法迭代過程;否則,進(jìn)入步驟2).偽代碼見表2.

Table 2 RP-CH algorithm表2 RP-CH 算法

RP-CH 的改進(jìn)在于作業(yè)分類信息和啟發(fā)式規(guī)則的應(yīng)用,其目的在于解決第2.2 節(jié)提到的貝葉斯優(yōu)化算法的兩個(gè)局限性,即冷啟動(dòng)問題和K階欺騙問題,以下介紹RP-CH 如何解決這兩個(gè)問題.

· 解決算法冷啟動(dòng)問題

貝葉斯優(yōu)化通過已知采樣點(diǎn)的AC函數(shù)運(yùn)算,估算候選采樣點(diǎn)的值,貝葉斯優(yōu)化算法啟動(dòng)需要n≥3 個(gè)初始選點(diǎn)以獲得足夠的計(jì)算空間(標(biāo)準(zhǔn)差通過協(xié)方差矩陣表示),因此在算法啟動(dòng)階段,貝葉斯優(yōu)化或隨機(jī)選擇采樣點(diǎn),或根據(jù)規(guī)則在指定采樣區(qū)間選點(diǎn),在本文場(chǎng)景中,由于樣本少(6 次采樣)且搜索空間大,算法隨機(jī)采樣的效果難以保障,導(dǎo)致算法冷啟動(dòng)問題.為此,本文的RP-CH 在算法啟動(dòng)階段運(yùn)用已知的啟發(fā)式規(guī)則,表示為貝葉斯優(yōu)化的超參數(shù)設(shè)置,加強(qiáng)算法在特定區(qū)間的選點(diǎn)以優(yōu)化算法的啟動(dòng)階段.貝葉斯優(yōu)化的AC函數(shù)主要由均值和標(biāo)準(zhǔn)差兩部分組成:均值越大,代表該候選點(diǎn)離最值越近;標(biāo)準(zhǔn)差越大,代表該候選點(diǎn)未探索程度越高.Snoek[23]的論文介紹了AC函數(shù)的多種評(píng)分策略,其中應(yīng)用最廣泛的是貪心策略(expected improvement,簡(jiǎn)稱EI).

CherryPick 的貝葉斯優(yōu)化采用的基于貪心策略的EI函數(shù),形式化地,EI函數(shù)的表達(dá)式如公式(4)所示:

其中,xt表示下一個(gè)采樣點(diǎn),ACEI(xt)表示該點(diǎn)的收益值,表示已有采樣點(diǎn)的均值,表示已有采樣點(diǎn)的方差,j是人工設(shè)定的超參數(shù).由于沒有下一個(gè)采樣點(diǎn)的額外特征描述,在函數(shù)啟動(dòng)階段會(huì)浪費(fèi)資源進(jìn)行全局采樣,導(dǎo)致算法啟動(dòng)較慢.

為此,RP-CH 通過算法的首次執(zhí)行獲取作業(yè)的分類信息,通過公式(3)的啟發(fā)式規(guī)則對(duì)候選點(diǎn)xt進(jìn)行評(píng)分,并作用到EI函數(shù)的超參數(shù)中.形式化地,結(jié)合啟發(fā)式規(guī)則的EI函數(shù)的表達(dá)式見公式(5):

解決K階欺騙問題:貝葉斯優(yōu)化由遺傳算法演變而來,在計(jì)算過程中,難以避免特征從低維變換開始導(dǎo)致的搜索空間爆炸問題,CherryPick 論文指出:其搜索開銷是性能建模方法Ernest 的4 倍,求解時(shí)間是性能建模方法Ernest 的10 倍以上.然而,本文在掌握了作業(yè)的分類信息之后,能夠采用解決遺傳算法K階欺騙問題的思想[24],加速計(jì)算過程.K階欺騙問題是指特征之間存在內(nèi)部關(guān)聯(lián)關(guān)系,當(dāng)算法在非K階空間中搜索,將導(dǎo)致算法效率下降[25].如計(jì)算密集型作業(yè)對(duì)CPU 個(gè)數(shù)、CPU 主頻、內(nèi)存大小、CPU 內(nèi)存比率同時(shí)進(jìn)行調(diào)整,更可能獲得優(yōu)化結(jié)果.因此,特征集U{cpu,cpu_speed,mem,cpu_mem_ratio}是提升搜索效率的K階搜索空間.

CherryPick 中算法在演化過程中搜索空間為所有特征的全體集合,樣本特征在低維度變化時(shí),搜索空間中的樣本數(shù)量呈指數(shù)增長(zhǎng),雖然最終能通過遺傳算子的積木塊效應(yīng)[26]累積成高階搜索空間,但是大多數(shù)時(shí)候直到種群規(guī)模達(dá)到上限(求解時(shí)間超時(shí))仍未獲得最優(yōu)解,導(dǎo)致結(jié)果準(zhǔn)確性不足.

表3 比較了K階欺騙時(shí)算法的搜索空間和效率,當(dāng)面對(duì)4 階欺騙問題時(shí),RP-CH 算法求解效率比CherryPick提升了16 倍.假設(shè)算法的最大種群規(guī)模為200(求解時(shí)間約20 分鐘),則CherryPick 在面對(duì)高階欺騙時(shí)難以獲得全局最優(yōu)解.為此,RP-CH 算法結(jié)合啟發(fā)式規(guī)則對(duì)搜索空間的數(shù)據(jù)進(jìn)行篩選,通過啟發(fā)式規(guī)則加速K階積木塊的形成.形式化地,啟發(fā)式規(guī)則見公式(6):

其中,AC(xt)為父節(jié)點(diǎn)所對(duì)應(yīng)的收益值,AC(K)為先驗(yàn)概率P(K)與所有這樣的K階結(jié)構(gòu)的AC值的乘積,先驗(yàn)概率P(K)是高斯過程公式計(jì)算而來,不影響評(píng)分機(jī)制,在此不再贅述.K在不同的作業(yè)分類中有不同的取值,計(jì)算密集型取U{cpu,cpu_speed,mem,cpu_mem_ratio},混合型取U{cpu_mem_ratio,scale_mem_ratio},IO 密集型取U{disk_speed,network_speed,disk_size}.公式(6)的好處在于K階搜索空間的優(yōu)先級(jí)將被大幅度提升,當(dāng)獲得作業(yè)分類知識(shí)后,能夠加速積木塊效應(yīng),使得算法向著指定方向收斂.

Table 3 Comparing RP-CH with CherryPick of K-Order building block’s population scale and runtime表3 K 階欺騙的搜索空間比較

綜上所述,RP-CH 主要在貝葉斯優(yōu)化算法初始化階段和后續(xù)選點(diǎn)階段結(jié)合了啟發(fā)式算法,旨在解決貝葉斯優(yōu)化的冷啟動(dòng)和K階欺騙問題.

圖7 展示了計(jì)算密集型作業(yè)在RP-CH 和CherryPick 算法初始化和后續(xù)采樣階段的比較,其中,橫坐標(biāo)表示配置方案的總內(nèi)存大小,縱坐標(biāo)表示作業(yè)的完成時(shí)間,虛線actual表示作業(yè)實(shí)際的資源成本曲線,曲線表示算法預(yù)測(cè)的作業(yè)負(fù)載的資源成本曲線,斜線標(biāo)注的區(qū)間表示符合高斯過程的95%置信區(qū)間,為當(dāng)前迭代的收益函數(shù),表示算法的第n次采樣.

RP-CH 作業(yè)分類信息的實(shí)際應(yīng)用如圖7(b)和圖7(d)所示,配置方案的總內(nèi)存從小到大增加的過程中,根據(jù)主流云計(jì)算平臺(tái)(阿里云)的配置規(guī)格分為large,xlarge 和2xlarge 這3 類,每個(gè)配置規(guī)格又細(xì)分為IO 密集型、混合型和計(jì)算密集型這3 個(gè)區(qū)間,便于觀察啟發(fā)式規(guī)則的效果.

Cherry Pick 的初始化階段如圖7(a)所示,為了保障選點(diǎn)的全局性,初始化3 個(gè)點(diǎn)一定會(huì)選擇總內(nèi)存的極小值、極大值和中值.RP-CH 則通過啟發(fā)式規(guī)則,將計(jì)算密集型作業(yè)快速收斂到與作業(yè)分類信息相匹配的區(qū)間,如圖7(b)所示,此時(shí),RP-CH 更有可能獲得比Cherry Pick 更好的初始化結(jié)果.

初始化結(jié)束后,CherryPick通過AC(計(jì)算下一個(gè)候選點(diǎn)作為算法采樣點(diǎn),如圖7(c)所示.由于實(shí)際曲線actual比較復(fù)雜,CherryPick的采樣有可能陷入局部最優(yōu)解.而RP-CH 通過啟發(fā)式規(guī)則改變了算法的選點(diǎn)位置,達(dá)到快速收斂的效果,如圖7(d)所示,虛線AC()函數(shù)為原始AC函數(shù),實(shí)線為加入啟發(fā)式規(guī)則的AC函數(shù).

Fig.7 Comparing RP-CH with CherryPick on step initialization and get candidate圖7 RP-CH 與CherryPick 算法比較,包括算法啟動(dòng)階段和選點(diǎn)階段

5 實(shí)驗(yàn)及結(jié)果分析

本文在阿里云計(jì)算平臺(tái)上對(duì)RP-CH 進(jìn)行實(shí)驗(yàn)驗(yàn)證,選用了240 種資源供給方案;采用主流的2 種工業(yè)級(jí)測(cè)試基準(zhǔn)共計(jì)8 種應(yīng)用.實(shí)驗(yàn)1 驗(yàn)證作業(yè)負(fù)載資源分類的有效性,比較了3 種相似度匹配算法;實(shí)驗(yàn)2 驗(yàn)證啟發(fā)式規(guī)則參數(shù)調(diào)節(jié)的效果;實(shí)驗(yàn)3 與CherryPick 進(jìn)行比較,驗(yàn)證相同小樣本下,云資源供給的應(yīng)用性能和資源成本.

5.1 實(shí)驗(yàn)環(huán)境

· 測(cè)試基準(zhǔn)程序:

實(shí)驗(yàn)的測(cè)試基準(zhǔn)見表4,覆蓋不同資源偏好、不同運(yùn)行場(chǎng)景的8 個(gè)程序,分屬于HiBench[27]和SparkBench[28]測(cè)試基準(zhǔn).

(1) HiBench:由Intel 推出的面向大數(shù)據(jù)的基準(zhǔn)測(cè)試套件,既涵蓋以TeraSort,WordCount 等為代表的微基準(zhǔn)測(cè)試,也包括主流的機(jī)器學(xué)習(xí)、類SQL、網(wǎng)絡(luò)搜索、流式計(jì)算等測(cè)試基準(zhǔn),本文中,數(shù)據(jù)規(guī)模微基準(zhǔn)測(cè)試為30G,其他測(cè)試選擇程序默認(rèn)配置的Huge 規(guī)模;

(2) SparkBench:由IBM 推出的Spark 基準(zhǔn)測(cè)試套件,測(cè)試類型包括機(jī)器學(xué)習(xí)、圖計(jì)算、類SQL 和流式計(jì)算.本文中,測(cè)試參數(shù)的設(shè)置依據(jù)SparkBench 論文[3],控制數(shù)據(jù)規(guī)模在20G～30G 之間,在此不一一闡述.

Table 4 Benhmark applications表4 測(cè)試基準(zhǔn)

· 資源供給方案

阿里云提供了豐富的云主機(jī)系列和云主機(jī)規(guī)格,本文選擇通用型、計(jì)算型、內(nèi)存型這3 個(gè)系列共計(jì)48 種配置規(guī)格,每種配置規(guī)格分別對(duì)應(yīng)5 種云主機(jī)個(gè)數(shù)(2,4,6,8,10),共計(jì)240 種資源供給方案.

· 比較對(duì)象

RP-CH 的主要比較對(duì)象為CherryPick,CherryPick 采用貝葉斯優(yōu)化進(jìn)行云資源配置選擇,其貢獻(xiàn)在于將貝葉斯優(yōu)化應(yīng)用到云資源配置優(yōu)化場(chǎng)景,對(duì)比性能建模方法,解決了場(chǎng)景通用性問題.

· 評(píng)價(jià)指標(biāo)

RP-CH 選擇以下指標(biāo)作為算法有效性的評(píng)價(jià)指標(biāo).

(1) 作業(yè)性能:在小樣本場(chǎng)景下,使用算法推薦資源供給方案運(yùn)行作業(yè)的完成時(shí)間;

(2) 資源成本:在小樣本場(chǎng)景下,使用算法推薦資源供給方案運(yùn)行作業(yè)的資源成本.

5.2 RP-CH有效性驗(yàn)證

本節(jié)通過多個(gè)實(shí)驗(yàn)對(duì)RP-CH 的云資源供給有效性進(jìn)行驗(yàn)證.

· 實(shí)驗(yàn)1:作業(yè)分類的有效性驗(yàn)證

本實(shí)驗(yàn)驗(yàn)證了作業(yè)的負(fù)載分類器的算法選擇問題,選取了3 種主流的相似度比較算法歐式距離Euclidean、最長(zhǎng)公共子序列LCSS 和弗雷歇距離Fréchet 進(jìn)行分類有效性的比較.在經(jīng)過多種負(fù)載類型的實(shí)驗(yàn)后,選擇誤差率最低的算法作為負(fù)載分類器的核心算法.實(shí)驗(yàn)結(jié)論為:本文將作業(yè)負(fù)載的資源使用曲線的相似度作為作業(yè)分類標(biāo)準(zhǔn).在比較了3 種主流相似度匹配算法后,可知弗雷歇距離更適合本文場(chǎng)景,3 組實(shí)驗(yàn)的平均誤差率為2%.

圖8 為弗雷歇距離、最長(zhǎng)公共子序列、歐氏距離這3 種主流相似度匹配算法的比較結(jié)果,實(shí)驗(yàn)選取了3 個(gè)不同資源偏好的基準(zhǔn)測(cè)試,在120 個(gè)不同配置方案中運(yùn)行,對(duì)算法結(jié)果進(jìn)行統(tǒng)計(jì).采用弗雷歇距離在計(jì)算密集型分類時(shí)只出現(xiàn)1 次判斷錯(cuò)誤,因?yàn)榛鶞?zhǔn)測(cè)試中的計(jì)算密集型作業(yè)特征非常明顯,CPU 保持持續(xù)高利用率,真實(shí)運(yùn)行環(huán)境中,可能因作業(yè)特征不同而效果存在差異.

Fig.8 Classify accuracy using 3 different algorithms圖8 3 個(gè)算法的準(zhǔn)確性比較

· 實(shí)驗(yàn)2:參數(shù)調(diào)節(jié)驗(yàn)證

本實(shí)驗(yàn)旨在驗(yàn)證第3.3 節(jié)中啟發(fā)式規(guī)則的參數(shù)設(shè)置問題,通過公式(3)的描述我們可知:參數(shù)θ1和θ2分別代表了云資源供給方案對(duì)于“作業(yè)類型的匹配度”和“作業(yè)數(shù)據(jù)規(guī)模的匹配度”,兩者的取值將影響作業(yè)分類的效果.因此,本實(shí)驗(yàn)驗(yàn)證了3 種不同的參數(shù)設(shè)置,從中選取優(yōu)化效果最好的設(shè)置作為候選設(shè)置.

如圖9 所示,縱軸的相對(duì)運(yùn)行開銷越小,表示作業(yè)的性能越好.相對(duì)運(yùn)行開銷是指算法推薦解與全局優(yōu)化解的比值,橫軸表示8 種基準(zhǔn)測(cè)試程序,每一種測(cè)試程序運(yùn)行20 次,柱狀圖上的誤差線下界表示10%統(tǒng)計(jì)結(jié)果,上界表示90%統(tǒng)計(jì)結(jié)果,實(shí)驗(yàn)選擇算法6 次采樣所推薦的結(jié)果作為算法推薦解.從結(jié)果可以看出:當(dāng)啟發(fā)式表達(dá)函數(shù)中參數(shù)設(shè)置成θ1:θ2=2:1,算法運(yùn)行效果更優(yōu).

Fig.9 Tunning θ1:θ2 with 1:1,2:1 and 1:2.Bars show 10th and 90th percentile圖9 參數(shù)調(diào)節(jié)效果對(duì)比,誤差線表示10%和90%結(jié)果

實(shí)驗(yàn)結(jié)論為:驗(yàn)證了啟發(fā)式表達(dá)函數(shù)(3)中的參數(shù)賦值.若以6 次采樣為終止條件,則θ1:θ2=2:1 時(shí)采樣結(jié)果比θ1:θ2=1:1 和θ1:θ2=1:2 優(yōu)化了20%～35%.

· 實(shí)驗(yàn)3:應(yīng)用性能和資源成本驗(yàn)證

本實(shí)驗(yàn)驗(yàn)證RP-CH 對(duì)于大數(shù)據(jù)分析作業(yè)在應(yīng)用性能和資源成本上的優(yōu)化效果.實(shí)驗(yàn)從測(cè)試基準(zhǔn)HiBench和SparkBench 中選擇了8 個(gè)具有代表性的測(cè)試程序,在阿里云的240 個(gè)候選云資源配置方案中進(jìn)行實(shí)驗(yàn).實(shí)驗(yàn)的比較對(duì)象為CherryPick.

如圖10(a)所示,縱軸的相對(duì)運(yùn)行開銷越小,表示作業(yè)的性能越好.相對(duì)運(yùn)行開銷是指算法推薦解與全局優(yōu)化解的比值,橫軸表示8 種基準(zhǔn)測(cè)試程序,每一種測(cè)試程序運(yùn)行20 次,柱狀圖上的誤差線下界表示10%統(tǒng)計(jì)結(jié)果,上界表示90%統(tǒng)計(jì)結(jié)果,實(shí)驗(yàn)選擇算法6 次采樣所推薦的結(jié)果作為算法推薦解.從結(jié)果可以看出:RP-CH 對(duì)于多種類型的應(yīng)用具有較好的推薦結(jié)果;6 次采樣平均值比全局優(yōu)化解的應(yīng)用性能相差18%,其中,K-means 和Aggregation 的結(jié)果與全局優(yōu)化解的應(yīng)用性能相差不到5%.圖10(b)顯示了RP-CH 和CherryPick 采樣結(jié)果的資源成本比較,RP-CH 資源成本平均減少44%.

Fig.10 Comparing RP-CH with alternative solutions.Bars show 10th and 90th percentile圖10 RP-CH 與候選方案比較,誤差線表示10%和90%結(jié)果

實(shí)驗(yàn)結(jié)論為:若以6 次采樣為終止條件,則RP-CH 的結(jié)果相比于CherryPick 平均提升作業(yè)性能58%,資源成本平均減少44%.

6 總結(jié)與展望

綜上所述,本文實(shí)現(xiàn)了大數(shù)據(jù)環(huán)境下基于負(fù)載分類的啟發(fā)式云資源供給方法RP-CH.首先,通過作業(yè)負(fù)載的資源使用曲線的相似度比較,對(duì)作業(yè)進(jìn)行分類;然后,基于分類信息的啟發(fā)式規(guī)則改進(jìn)貝葉斯優(yōu)化算法的AC函數(shù),解決小樣本下貝葉斯優(yōu)化的局部最優(yōu)解問題.經(jīng)過實(shí)驗(yàn)驗(yàn)證,RP-CH 比CherryPick 的作業(yè)性能平均提升58%,成本平均減少44%.

對(duì)于本文所提出的方法本身,仍然存在一定可提升的優(yōu)化空間.如:在對(duì)于流式計(jì)算作業(yè)時(shí),由于流式計(jì)算實(shí)時(shí)接收數(shù)據(jù)的特性,導(dǎo)致預(yù)測(cè)結(jié)果誤差較大;啟發(fā)式規(guī)則的參數(shù)調(diào)節(jié)需設(shè)計(jì)大量實(shí)驗(yàn),驗(yàn)證參數(shù)調(diào)節(jié)的場(chǎng)景適應(yīng)性;在解決冷啟動(dòng)問題時(shí),可評(píng)估其他收斂策略如局部貪婪策略的效果;貝葉斯算法本身有一些優(yōu)化工作,如通過貝葉斯網(wǎng)絡(luò)求解等.由于不是本文關(guān)注重點(diǎn),考慮在將來的工作中繼續(xù)研究.

隨著機(jī)器學(xué)習(xí)技術(shù)的發(fā)展,對(duì)于數(shù)據(jù)量少、樣本獲取成本高的場(chǎng)景下,會(huì)有更多更好的算法被提出.實(shí)際上資源供給問題,關(guān)注點(diǎn)本身不在于算法實(shí)現(xiàn),其關(guān)鍵問題是資源的使用預(yù)測(cè).假如能夠準(zhǔn)確實(shí)現(xiàn)預(yù)測(cè)作業(yè)在某一配置下的運(yùn)行時(shí)間,那么自然可以選擇出最優(yōu)的配置方案.同時(shí),本文的研究工作可用于輔助資源調(diào)度、廠商資源定價(jià)、系統(tǒng)運(yùn)維、可靠性保障等相關(guān)場(chǎng)景.