面向混部云失敗批處理作業(yè)的預測算法*

林偉偉，石 方，李毓睿，劉發(fā)貴，劉 捷，彭紹亮，王子駿

(1. 華南理工大學 計算機科學與工程學院， 廣東 廣州 510006； 2. 鵬程實驗室， 廣東 深圳 518066；3. 湖南大學 信息科學與工程學院， 湖南 長沙 410082； 4. 克萊姆森大學 計算學院， 美國 克萊姆森 29634)

2015 年，Google 發(fā)表論文介紹了Borg系統(tǒng)，其中就提到了在線服務(wù)作業(yè)與批處理作業(yè)的混合運行，也就是混部技術(shù)[1]。阿里巴巴作為全球最大的幾家互聯(lián)網(wǎng)公司之一，使用混部技術(shù)把集群混合起來，將不同類型的任務(wù)調(diào)度到相同的物理資源上，充分利用資源能力，極大降低成本。為了讓業(yè)界深入了解混部集群的特征，阿里巴巴在2018年發(fā)布了混部集群的負載數(shù)據(jù)集cluster-trace-v2018(Ali Trace 2018)[2]。

混部集群最主要的問題是：在同一硬件上分配的工作負載越多，每個工作負載受到彼此性能干擾的可能性越大。阿里巴巴的混部生產(chǎn)集群作為一個多租戶和多用途數(shù)據(jù)中心，其中的批處理作業(yè)具有高度分散的特點，由Fuxi調(diào)度器統(tǒng)一調(diào)度管理[3]，批處理作業(yè)執(zhí)行不成功的情況時有發(fā)生，這些執(zhí)行失敗的批作業(yè)將在集群中重復執(zhí)行，被標記為重調(diào)度作業(yè)。這些失敗作業(yè)消耗了不可忽視的資源，可能造成嚴重的性能障礙。因此，為了提高混部集群的可靠性和容錯性，預測失敗作業(yè)的發(fā)生是十分有必要的。為此，本文提出了一種用于預測失敗批處理作業(yè)的算法。本文的主要貢獻包括：

1)對失敗作業(yè)的重調(diào)度現(xiàn)象進行了深入分析，發(fā)現(xiàn)失敗作業(yè)不僅浪費了大量資源，而且會影響整個集群的工作狀態(tài)，預測失敗作業(yè)的發(fā)生十分有必要。

2)使用K-means聚類算法對批處理作業(yè)進行了聚類分析，發(fā)現(xiàn)不同資源負載類別的批處理作業(yè)發(fā)生失敗現(xiàn)象的風險不同。

3)提出了一個針對混部集群失敗作業(yè)預測算法，該算法包括特征工程以及基于LightGBM[4]的二層嵌套分類模型(two-layer nested classification model, TLNM)。首先通過分類預測LightGBM模型(classification prediction lightGBM-model, CPLM)將批處理作業(yè)分為四類，然后使用三種不同的異常預測LightGBM模型(anomaly prediction lightGBM-model, APLM)分別對三類批處理作業(yè)進行二分類預測，即預測該批處理作業(yè)是否會發(fā)生失敗。實驗表明，該模型能夠準確地預測出失敗批處理作業(yè)，且在時間性能方面優(yōu)于其他模型。

1 相關(guān)工作

混部集群在提升資源利用率的同時，也帶來了許多問題[5-8]，例如，批處理作業(yè)長期受到在線服務(wù)容器的資源擠壓，導致兩種不同類型的任務(wù)在資源分配上的不平衡問題。Liu等[9]研究了半集裝箱云的彈性和塑性。Chen等[10]在2018年對Ali Trace 2017進行了進一步的分析，采用K-means聚類算法對運行在阿里云集群中的負載進行了聚類，并研究了得出類別的屬性的共同特征，同時給出了哪幾類簇通常會分配到一臺物理機執(zhí)行。Guo[11]等的研究發(fā)現(xiàn)：在阿里巴巴的混部集群中，內(nèi)存似乎成了新的瓶頸，限制了資源使用效率的進一步提升。

在云數(shù)據(jù)中心的失敗任務(wù)預測方面，Rosà[12-14]等分析了Google大數(shù)據(jù)集群中失敗任務(wù)帶來的影響，并且提出了一個神經(jīng)網(wǎng)絡(luò)分類器來預測這些失敗任務(wù)。此外，他們還開發(fā)了三種在線預測模型，這些模型可以將作業(yè)和事件在開始時分為四類。文獻[15]則著重于早期階段云任務(wù)的故障預測，提出了一種基于相似作業(yè)之間的關(guān)聯(lián)關(guān)系的故障預測方法，可以在較早的階段聯(lián)合預測任務(wù)的終止狀態(tài)。文獻[16]則使用極限學習機對Google集群的云作業(yè)進行失敗預測，可以根據(jù)作業(yè)到達的順序收集實時數(shù)據(jù)，預測作業(yè)狀態(tài)，并根據(jù)這些數(shù)據(jù)更新模型。Hemmat等[17]使用隨機森林分類器對云中違反服務(wù)等級協(xié)議的作業(yè)進行了預測。Shetty等[18]分析了谷歌的生產(chǎn)集群中的任務(wù)資源利用率并且基于XGBoost分類器對集群中的失敗作業(yè)進行了預測。Chen等[19]介紹了Google集群中失敗作業(yè)和失敗任務(wù)的統(tǒng)計特征，并嘗試將它們與調(diào)度約束、節(jié)點操作以及云中用戶的屬性相關(guān)聯(lián)，此外，他們還探索了早期故障預測和作業(yè)異常檢測的潛力。

2 研究背景

2.1 阿里云混部集群介紹

圖1描述了阿里巴巴公司的混部集群體系結(jié)構(gòu)。托管的任務(wù)由兩個調(diào)度程序協(xié)調(diào)管理：Sigma用于在線服務(wù)，而Fuxi用于批處理工作負載。其中在線服務(wù)作業(yè)運行于容器(Container)當中，而批處理作業(yè)則被Fuxi調(diào)度器拆解為批處理實例(Batch Instances)，這些實例直接運行于物理機之中。

圖1 阿里巴巴混部集群體系結(jié)構(gòu)Fig.1 Architecture of Alibaba′s co-located datacenter

2.2 失敗實例的重調(diào)度現(xiàn)象分析

在混部集群中，由于對共享資源的不可預測的干擾，當出現(xiàn)任何性能峰值時，出于對在線服務(wù)容器的資源保護，批處理作業(yè)可能會被延遲或驅(qū)逐。在阿里巴巴的集群中，當在線服務(wù)的性能受到影響時，F(xiàn)uxi的代理將首先暫停批處理實例，如果仍然存在干擾，則將這些實例重新安排到另一個主機上。失敗的實例將重試多次，直到成功完成為止。雖然批處理作業(yè)的失敗率只有0.081%，但失敗實例數(shù)達到了100萬個，且20%的失敗實例出現(xiàn)了多次重調(diào)度。此外，61%的失敗實例在運行一段時間后重新調(diào)度，38%的失敗實例在未運行的情況下重新調(diào)度，3%的失敗實例需要很長時間才能完成有向無環(huán)圖(directed acyclic graph, DAG)任務(wù)[11]。

表1列出了正常實例與失敗實例在平均中央處理器(central processing unit, CPU)消耗、平均內(nèi)存消耗和平均耗時之間的差異。通過對比表格中的數(shù)據(jù)可以發(fā)現(xiàn)，失敗實例的CPU消耗高出正常實例約20%，內(nèi)存消耗高出正常實例約150%，平均耗時約是正常實例的13倍。失敗實例的資源浪費情況不容忽視。

表1 正常實例與失敗實例對比

實例被重調(diào)度所浪費的CPU和內(nèi)存時間可以假設(shè)如下：

1)設(shè)T為instance_A被重調(diào)度浪費的時間。

2)設(shè)(Mem，Cpu)為instance_A運行成功時平均內(nèi)存、CPU消耗。

記TMem=T×Mem，TCpu=T×Cpu，那么向量(TMem,TCpu)為失敗實例所浪費的資源。

以一個特定的實例(數(shù)據(jù)集中的ins_63835109)為例，圖2為ins_63835109失敗實例的生命周期示意。它首先在服務(wù)器m_1718上以時間戳373 421進行調(diào)度，然后在沒有完成的情況下運行609 s。之后，它被重新調(diào)度到服務(wù)器m_177，并在時間戳374 031處開始運行，執(zhí)行時間為1 196 s。那么374 031-373 421=610 s即為失敗實例浪費的時間。ins_63835109的(Mem，Cpu)=(0.31，58)，此實例由于重新調(diào)度而延遲了約10 min，所浪費的資源向量(TMem,TCpu)=(189.1,35 380)。

圖2 失敗實例的生命周期示意(以ins_63835109為例)Fig.2 Life of a failed instance (take ins_63835109 as an example)

圖3和圖4代表了失敗實例所浪費的內(nèi)存和CPU資源的累積分布函數(shù)(cumulative distribution function, CDF)圖。由圖可以觀察到，大約超過一半的失敗實例的內(nèi)存資源浪費在100以上、CPU資源浪費在20 000以上(內(nèi)存資源浪費量和CPU資源浪費量為標準化數(shù)值，每100內(nèi)存表示消耗了一整臺服務(wù)器的內(nèi)存總量，每100CPU表示消耗了1個CPU核心)，并且大多數(shù)失敗實例浪費了大量資源。這種資源浪費在超大型數(shù)據(jù)中心是不容忽視的。雖然重調(diào)度這種動態(tài)機制保護了在線服務(wù)作業(yè)的性能，但它犧牲了批量作業(yè)的性能，間接地限制了資源效率。

圖3 內(nèi)存資源浪費CDF圖Fig.3 CDF of the memory wasted

圖4 CPU資源浪費CDF圖Fig.4 CDF of the CPU wasted

2.3 不同類別批處理作業(yè)的失敗現(xiàn)象分析

作為數(shù)據(jù)分析的一部分，本文對Ali Trace 2018中的批處理作業(yè)進行基于K-means的聚類與分析。本文發(fā)現(xiàn)了四種不同類型的批處理作業(yè)資源特征形式，而且不同類別批處理作業(yè)運行失敗的風險也不同。

如表2所示，將批處理作業(yè)的平均耗時、CPU消耗、內(nèi)存消耗與實例數(shù)量作為批處理作業(yè)聚類特征。在K=2，…，10中，取K=4時輪廓系數(shù)最高，為0.99。因此將批處理任務(wù)數(shù)據(jù)歸為4類，每類批處理作業(yè)的資源負載特征如表2所示。

表2 不同類別批處理作業(yè)資源消耗特征

表3中列出了批處理作業(yè)各個資源畫像類別中的失敗作業(yè)數(shù)量與占比(失敗作業(yè)表示該作業(yè)中有實例發(fā)生了重調(diào)度)。在4類批處理作業(yè)畫像中，短時間運行的輕量級作業(yè)(類-2)是不會發(fā)生失敗的；類-0由于簇內(nèi)作業(yè)數(shù)量多，發(fā)生的失敗作業(yè)數(shù)量也多，但是失敗作業(yè)占比不到1%；類-1屬于重量型作業(yè)，運行時間久、資源消耗多、實例數(shù)量多，因此約有3.3%的作業(yè)存在失敗的情況；類-3屬于長時間運行的輕量級作業(yè)，約有47%的作業(yè)存在失敗的情況。

表3 不同資源畫像批處理作業(yè)的失敗現(xiàn)象

3 TLNM與基于TLNM的預測算法

為了提高混部云的可靠性與錯誤容忍性，本文提出了一個基于LightGBM的TLNM，并將TLNM應(yīng)用在混部云的失敗批處理作業(yè)預測中，實現(xiàn)了一個基于TLNM的混部云的失敗批處理作業(yè)預測算法。

3.1 TLNM核心思想

機器學習技術(shù)被廣泛應(yīng)用于根據(jù)數(shù)據(jù)特征對異常點進行分類。一方面，線性分類器如支持向量機(support vector machine, SVM)或邏輯回歸(logistic regression, LR)適合于表現(xiàn)(近似)線性關(guān)系的系統(tǒng)；另一方面，決策樹(decision tree, DT)、隨機森林(random forest, RF)和LightGBM等非線性分類器可以更好地對復雜系統(tǒng)建模。由于系統(tǒng)的高度非線性和不穩(wěn)定性，本文開發(fā)了TLNM來提高分類精度。本文選擇批處理作業(yè)進行失敗預測，主要出于以下三個考慮：①批處理實例數(shù)據(jù)量較大，訓練模型耗時過長，且不具有代表性；②通過數(shù)據(jù)分析發(fā)現(xiàn)，失敗批處理作業(yè)中的某個實例一旦發(fā)生重調(diào)度現(xiàn)象，將會導致該批處理作業(yè)中其他實例也發(fā)生重調(diào)度；③批處理作業(yè)作為混部集群中各個實例的代表，可以由Fuxi調(diào)度器進行實時數(shù)據(jù)采集，可以設(shè)計實時預測系統(tǒng)。

前文第2節(jié)討論了不同類別的批處理作業(yè)所表現(xiàn)出的失敗現(xiàn)象，其中短時間運行的輕量級作業(yè)中并沒有出現(xiàn)失敗作業(yè)，而其他畫像中的失敗作業(yè)比例有很大不同。因此， TLNM的核心思想是對批處理作業(yè)進行多分類后，再進行失敗預測。TLNM中有四個子模型，分別是一個CPLM和三個APLM，如圖5和圖6所示。其中CPLM和APLM獨立工作：首先將批處理作業(yè)按照畫像不同進行分類，這是一個多分類問題；然后按照不同的資源畫像類別調(diào)用不同的APLM進行第二次預測，這是一個二分類問題。為了避免過度擬合偏差，通過一個由20%的作業(yè)證組成的獨立驗證集來交叉驗證預測的準確性。

(a) CPLM

圖6 TLNM組織架構(gòu)Fig.6 Architecture of TLNM

3.2 基于TLNM的預測算法

由于混部云中存在混部干擾，而混部云的數(shù)據(jù)集無法充分暴露出混部干擾情況，因此需要構(gòu)造一個完整的特征數(shù)據(jù)集來配合TLNM進行失敗任務(wù)預測。本小節(jié)提出一個針對阿里云失敗作業(yè)的預測算法，包括針對阿里云的混部特征提取算法(特征工程)和TLNM預測。算法1是混部特征提取算法的偽代碼描述。以Ali Trace 2018為例，首先根據(jù)batch_instance表格中的machine_id字段找到該實例所運行的物理機ID；再根據(jù)該machine_id匹配machine_usage表格和container_usage表格，從這兩個表格中找到本文需要的特征數(shù)據(jù)；然后將本文找到的物理機狀態(tài)數(shù)據(jù)與容器的運行狀態(tài)數(shù)據(jù)結(jié)合，形成當前實例的混部特征數(shù)據(jù)；最后再根據(jù)當前實例的混部特征數(shù)據(jù)中的job_name字段，將實例的混部特征數(shù)據(jù)整理成批處理作業(yè)的混部特征數(shù)據(jù)。該算法的時間復雜度為O(t·N),t為每個實例所需要的處理時間。

算法1 混部特征提取算法

圖7 基于TLNM的預測Fig.7 TLNM based prediction

如圖7所示，本文首先對混部云數(shù)據(jù)集進行混部特征提取，制作出混部特征數(shù)據(jù)集作為TLNM的輸入數(shù)據(jù)集，然后對混部特征數(shù)據(jù)集進行基于TLNM預測算法的分類預測。算法2是基于TLNM的預測算法偽代碼描述，TLNM首先使用混部特征數(shù)據(jù)集中的部分字段(批處理作業(yè)的平均耗時、CPU消耗、內(nèi)存消耗與實例數(shù)量)進行批處理作業(yè)分類預測，然后再對分類后的批處理作業(yè)分別進行異常預測，得到預測結(jié)果，即失敗作業(yè)集。該算法的時間消耗主要在模型的訓練上，因此該算法的時間復雜度為O(nlogn·m·d)，其中n是訓練樣本個數(shù)，m是特征個數(shù)，d為梯度提升迭代決策樹(LightGBM也是其中一種)的深度。

4 實驗評估

4.1 主要評估指標

接受者操作特性(receiver operating characteristic, ROC)分析是一種直觀評估一個或多個分類器準確性的方法，并且不受不平衡數(shù)據(jù)集的影響。如表4的混淆矩陣所示，如果進行預測，會出現(xiàn)四種情況，即：實例是正類并且也被預測成正類，即為真正類TP(true positive)；實例是負類而被預測成正類，稱之為假正類FP(false positive)；實例是負類且被預測成負類，稱之為真負類TN(true negative)；實例是正類而被預測成負類，稱之為假負類FN(false negative)。

表4 混淆矩陣

1)TPR=TP/(TP+FN)表示當前分到正樣本中真實的正樣本占所有實際正樣本的比例，即召回率；

2)FPR=FP/(FP+TN)表示當前被錯誤分到正樣本類別中真實的實際負樣本占所有負樣本總數(shù)的比例；

3)精確率=TP/(TP+FN)，它的含義是在所有被預測為正的樣本中實際為正的樣本的概率。

對于ROC來說，橫坐標就是FPR，縱坐標就是TPR，當 TPR越大，而FPR越小時，說明分類結(jié)果是較好的。在樣本不均衡的情況下， ROC曲線仍然能較好地評價分類器的性能，這是ROC的一個優(yōu)良特性，也是一般ROC曲線使用更多的原因。除了ROC曲線的圖形化評價外，還可以通過測量曲線下的面積(area under curve, AUC)來量化分類器的準確性。從直觀上看，AUC越接近1，分類器就越準確，一個完美分類器的AUC等于1。

在本節(jié)的實驗評估中，本文主要參考ROC曲線、AUC和召回率來證明TLNM在對比的分類器中具有最好的性能。

4.2 混部特征提取算法實驗

為了說明特征工程的重要性，本文評估了TLNM算法在不同的特征數(shù)據(jù)集上的表現(xiàn)。本次實驗使用的兩個數(shù)據(jù)集分別為表2所示的批處理作業(yè)四個特征(平均CPU消耗、平均內(nèi)存消耗，平均耗時和實例數(shù)量)構(gòu)成的數(shù)據(jù)集與混部特征數(shù)據(jù)集。表5所示為經(jīng)過混部特征提取算法的數(shù)據(jù)集與普通批處理作業(yè)數(shù)據(jù)集實驗效果對比結(jié)果。通過混部特征提取算法之后，將預測的AUC值從0.62提升到0.98，召回率從0.37提高到0.95。

表5 TLNM算法在不同數(shù)據(jù)集上的表現(xiàn)

除了對比TLNM算法在不同數(shù)據(jù)集上的表現(xiàn)之外，本文還使用SHAP[20]工具來對特征重要度進行了進一步解釋。SHAP是基于Python開發(fā)的一個“模型解釋”包，可以解釋任何機器學習算法的輸出。其名稱來源于SHapley Additive exPlanation，作者在合作博弈論的啟發(fā)下構(gòu)建了一個加性的解釋模型，所有的特征都視為“貢獻者”。對于每個預測樣本，模型都產(chǎn)生一個預測值，SHAP value就是該樣本中每個特征所分配到的數(shù)值。SHAP value最大的優(yōu)勢是能反映出樣本中每一個特征值對預測結(jié)果的影響力，而且還表現(xiàn)出影響的正負性。

圖8所示為混部特征數(shù)據(jù)集中各個特征的SHAP value。其中對模型預測結(jié)果影響最大的特征為批處理作業(yè)的運行時間(run_time)，影響最低的兩個特征分別為容器數(shù)量(container_num)和物理機內(nèi)存利用率百分比(machine_mem_util_percent)。出于篇幅考慮，在此并未對每個特征的含義加以說明。圖9繪制了各個特征對算法輸出的影響，由點構(gòu)成，每個點有三個含義：①點的豎直坐標是說明它屬于哪個特征；②點的顏色代表了這個特征的數(shù)值是高還是低；③水平位置代表了這個特征在某一行數(shù)據(jù)里是提高預測值還是降低預測值。比如run_time行中最右側(cè)的紅點，說明了運行時間長的某個特征點，預測效果的SHAP value為0.75左右，提高了預測值。通過SHAP分析可以發(fā)現(xiàn)，對算法影響最大的是run_time這個特征，值的大小與預測的結(jié)果呈正相關(guān)性。

圖8 模型中各個特征的SHAP valueFig.8 SHAP values for each feature in model

圖9 每個特征對模型輸出的影響Fig.9 Impact of each feature on the model output

4.3 TLNM算法與其他分類器的對比

在本小節(jié)中，通過比較TLNM算法和其他常用分類器(RF、SVM、LR、DT)在混部特征數(shù)據(jù)集上的表現(xiàn)，以說明TLNM算法的優(yōu)勢所在。從圖10可以清楚地看出，TLNM算法的ROC曲線明顯高于其他分類器，且AUC最高，不僅AUC接近1(取值0.978)，而且與其他分類器之間的AUC也存在明顯的差距。除了TLNM算法之外，第二好的分類器是RF，AUC指標為0.878，其次是DT。DT與RF的AUC相近，兩者具有可比性。召回率方面，TLNM的召回率明顯高于其他分類器，在高度不平衡的數(shù)據(jù)集中精確預測出所有可能運行失敗的批處理作業(yè)。TLNM算法在測試數(shù)據(jù)集上預測結(jié)果的混淆矩陣如表6所示，在4 153個失敗作業(yè)中準確預測出了3 948個失敗作業(yè)，但是錯誤地把正常的48 859個批處理作業(yè)也當成了失敗作業(yè)。

(a) TLNM算法與其他分類器ROC曲線(a) TLNM algorithm versus different classifiers on ROC curves

表6 TLNM算法的混淆矩陣

表7列出了TLNM算法與不同分類器在訓練時的時間性能，所有訓練均在同一臺服務(wù)器(Intel (R) Xeon(R) CPU E5-2620 v2 @ 2.10 GHz，112 GB內(nèi)存)上進行。在時間性能方面，TLNM算法中所有的模型訓練時間總計為72.36 s，優(yōu)于其他所有分類器。DT的訓練時間為158.19 s，是時間性能表現(xiàn)第二佳的模型?；ㄙM最高的模型是SVM，訓練時間達到1 381.72 s。

表7 不同分類器的時間性能對比

5 結(jié)論

在一個超大型數(shù)據(jù)中心中，作業(yè)運行失敗的現(xiàn)象時有發(fā)生，本文對批處理作業(yè)的失敗現(xiàn)象進行了深入分析，結(jié)果發(fā)現(xiàn)重調(diào)度現(xiàn)象會造成大量資源浪費。此外，為了更準確地預測出混部集群中的失敗現(xiàn)象，對批處理作業(yè)進行了基于K-means的聚類分析，將批處理作業(yè)分為4個類別，發(fā)現(xiàn)不同類別的批處理作業(yè)發(fā)生失敗現(xiàn)象的風險不同。在此基礎(chǔ)上，提出了一種用于預測混部集群中批處理作業(yè)失敗現(xiàn)象的二層嵌套分類模型TLNM，并開發(fā)了基于TLNM的混部云失敗作業(yè)預測算法。評估結(jié)果表明，與其他分類器(LR、SVM、DT、RF)相比，TLNM算法的分類結(jié)果更優(yōu)，AUC值達到最高的0.978，召回率也達到最高的0.951?？偟膩碚f，本文的研究有助于提高混部集群的資源利用率和錯誤容忍性，本文的預測算法允許調(diào)度系統(tǒng)做出主動決策。例如，基于本文預測算法的資源感知調(diào)度可以進行資源優(yōu)化，通過在預測服務(wù)器上標記出可能發(fā)生失敗現(xiàn)象的批處理作業(yè)，可以提前調(diào)整批處理作業(yè)的優(yōu)先級或者暫停該作業(yè)，以優(yōu)化超大規(guī)?；觳考旱馁Y源配置。