面向大數據分析作業的啟發式云資源供給方法*

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

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

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

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

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

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

本文的主要貢獻如下.

(1) 設計面向大數據分析作業的分類器,建立大數據分析作業分類與優化云資源配置的啟發式規則,通過計算新的大數據分析作業與歷史性能數據(CPU、內存、磁盤和網絡)的弗雷歇距離(Fréchet distance)[4],對新的大數據分析作業進行歸類;

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

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

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

1 相關工作

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

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

· 性能建模方法

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

· 機器學習方法

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

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

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

2 問題分析和研究思路

2.1 問題定義

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

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

2.2 研究思路

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

然而,如何建立啟發式規則,并實現基于啟發式規則的云資源供給算法面臨挑戰,具體的分析如下所述.

1)啟發式規則的建立.啟發式規則建立在作業分類的基礎之上,作業分類的難點在于相同作業在不同云資源配置下執行結果存在差異,單純統計作業的平均資源利用率難以做到準確分類.如何對作業進行分類,并建立作業分類信息與云資源供給優化的啟發式規則面臨挑戰;

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

3 啟發式規則的建立

3.1 特征的選擇

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

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

相關領域的研究工作中,采用運行時監測和日志分析等手段優化求解過程是一種主流的研究手段[14-16].

3.2 負載分類

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

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

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

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

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

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

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、磁盤和網絡距離比較

3.3 啟發式規則

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

Table 1 System features selected from for building heuristic rules表1 特征向量 中用于構建啟發式規則的特征

Table 1 System features selected from for building heuristic rules表1 特征向量 中用于構建啟發式規則的特征

啟發式規則的函數表達式見公式(3):

其中,

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

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

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

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

4 啟發式規則的表示

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

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

算法的基本流程為:

1)采用啟發式規則結合作業的分類信息(通過首次執行獲得)進行初始選點;

2)運行作業;

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

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

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

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

· 解決算法冷啟動問題

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

5 實驗及結果分析

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

5.1 實驗環境

· 測試基準程序:

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

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

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

Table 4 Benhmark applications表4 測試基準

· 資源供給方案

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

· 比較對象

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

· 評價指標

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

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

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

5.2 RP-CH有效性驗證

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

· 實驗1:作業分類的有效性驗證

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

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

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

· 實驗2:參數調節驗證

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

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

Fig.9 Tunning θ1:θ2 with 1:1,2:1 and 1:2.Bars show 10th and 90th percentile圖9 參數調節效果對比,誤差線表示10%和90%結果

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

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

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

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

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

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

6 總結與展望

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

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

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