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

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

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

然而,周期性作業(yè)的云資源供給面臨樣本少、搜索空間過大的問題,容易陷入局部最優(yōu)解.如圖1 所示,機器學習典型方法CherryPick 找到全局優(yōu)化解的樣本個數(shù)(縱軸)隨著云資源配置數(shù)量(橫軸)增加而增長,特別是在候選方案超過66 個時(CherryPick 實驗上限).在本文,云資源配置是指主機個數(shù)和云主機類型(計算、內(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ā)式云資源供給方法RP-CH(resource provisioning based on classification and heuristic),基于云資源共享特點,獲取其他大數(shù)據(jù)分析作業(yè)的運行時監(jiān)測數(shù)據(jù)和云資源配置信息,建立大數(shù)據(jù)分析作業(yè)分類與優(yōu)化云資源配置的啟發(fā)式規(guī)則,并將該規(guī)則作用到貝葉斯優(yōu)化算法的收益函數(shù)AC(acquisition function),可減少貝葉斯優(yōu)化算法搜索空間,在小樣本下可快速收斂找到優(yōu)化的資源供給方案.

本文的主要貢獻如下.

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

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

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

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

1 相關(guān)工作

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

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

· 性能建模方法

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

· 機器學習方法

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

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

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

2 問題分析和研究思路

2.1 問題定義

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

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

2.2 研究思路

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

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

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

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

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

3.1 特征的選擇

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

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

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

3.2 負載分類

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

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

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

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

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

為了解決云資源配置差異導致的相似度比較誤差問題,本文采用基于曲線形狀的相似度比較方法,其中,弗雷歇距離[20]應用廣泛,具有較強的噪聲容忍性.其原理是:基于曲線斜率比較形狀相似度,根據(jù)斜率的差值在離散的點中間插入新的點以解決噪聲問題,增加形狀相似度比較的準確性,對于噪聲引起的圖像平移和數(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 不同云資源配置下運行的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 算法中縮減搜索空間,并指導算法選擇下一個采樣點,選擇的特征見表1,其中,{CPU memory ratio,CPU speed,disk sxpeed,network4 speed}這4 個特征集合用于判斷該向量是否與作業(yè)分類信息相匹配,例如,計算密集型作業(yè)符合{高,高,低,低}的特征集合(IO 資源需求低以降低資源成本);特征Scale memoryratio用于判斷向量的云資源配置是否滿足作業(yè)數(shù)據(jù)規(guī)模的資源需求,例如,當Scale=40GB 的作業(yè)在總內(nèi)存≥40GB 的云資源配置方案中執(zhí)行效果更佳,取值范圍從0～50,表明本文實驗環(huán)境中賦予“數(shù)據(jù)規(guī)模/內(nèi)存比率”的上限是50,是因為當該值超過50 時,以Spark 為代表的內(nèi)存計算型Benchmark 可能因為內(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ù)表達式見公式(3):

其中,

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

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

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

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

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

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

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

算法的基本流程為:

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

2)運行作業(yè);

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

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

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

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

· 解決算法冷啟動問題

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

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

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

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

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

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

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

其中,AC(xt)為父節(jié)點所對應的收益值,AC(K)為先驗概率P(K)與所有這樣的K階結(jié)構(gòu)的AC值的乘積,先驗概率P(K)是高斯過程公式計算而來,不影響評分機制,在此不再贅述.K在不同的作業(yè)分類中有不同的取值,計算密集型取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)先級將被大幅度提升,當獲得作業(yè)分類知識后,能夠加速積木塊效應,使得算法向著指定方向收斂.

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

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

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

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

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

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

Fig.7 Comparing RP-CH with CherryPick on step initialization and get candidate圖7 RP-CH 與CherryPick 算法比較,包括算法啟動階段和選點階段

5 實驗及結(jié)果分析

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

5.1 實驗環(huán)境

· 測試基準程序:

實驗的測試基準見表4,覆蓋不同資源偏好、不同運行場景的8 個程序,分屬于HiBench[27]和SparkBench[28]測試基準.

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

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

Table 4 Benhmark applications表4 測試基準

· 資源供給方案

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

· 比較對象

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

· 評價指標

RP-CH 選擇以下指標作為算法有效性的評價指標.

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

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

5.2 RP-CH有效性驗證

本節(jié)通過多個實驗對RP-CH 的云資源供給有效性進行驗證.

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

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

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

Fig.8 Classify accuracy using 3 different algorithms圖8 3 個算法的準確性比較

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

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

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

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

· 實驗3:應用性能和資源成本驗證

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

如圖10(a)所示,縱軸的相對運行開銷越小,表示作業(yè)的性能越好.相對運行開銷是指算法推薦解與全局優(yōu)化解的比值,橫軸表示8 種基準測試程序,每一種測試程序運行20 次,柱狀圖上的誤差線下界表示10%統(tǒng)計結(jié)果,上界表示90%統(tǒng)計結(jié)果,實驗選擇算法6 次采樣所推薦的結(jié)果作為算法推薦解.從結(jié)果可以看出:RP-CH 對于多種類型的應用具有較好的推薦結(jié)果;6 次采樣平均值比全局優(yōu)化解的應用性能相差18%,其中,K-means 和Aggregation 的結(jié)果與全局優(yōu)化解的應用性能相差不到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é)果

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

6 總結(jié)與展望

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

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

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