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

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

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

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

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

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

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

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

1 相關工作

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

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

2 研究背景

2.1 阿里云混部集群介紹

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

圖1 阿里巴巴混部集群體系結構Fig.1 Architecture of Alibaba′s co-located datacenter

2.2 失敗實例的重調度現象分析

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

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

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

實例被重調度所浪費的CPU和內存時間可以假設如下：

1)設T為instance_A被重調度浪費的時間。

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

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

以一個特定的實例(數據集中的ins_63835109)為例，圖2為ins_63835109失敗實例的生命周期示意。它首先在服務器m_1718上以時間戳373 421進行調度，然后在沒有完成的情況下運行609 s。之后，它被重新調度到服務器m_177，并在時間戳374 031處開始運行，執行時間為1 196 s。那么374 031-373 421=610 s即為失敗實例浪費的時間。ins_63835109的(Mem，Cpu)=(0.31，58)，此實例由于重新調度而延遲了約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代表了失敗實例所浪費的內存和CPU資源的累積分布函數(cumulative distribution function, CDF)圖。由圖可以觀察到，大約超過一半的失敗實例的內存資源浪費在100以上、CPU資源浪費在20 000以上(內存資源浪費量和CPU資源浪費量為標準化數值，每100內存表示消耗了一整臺服務器的內存總量，每100CPU表示消耗了1個CPU核心)，并且大多數失敗實例浪費了大量資源。這種資源浪費在超大型數據中心是不容忽視的。雖然重調度這種動態機制保護了在線服務作業的性能，但它犧牲了批量作業的性能，間接地限制了資源效率。

圖3 內存資源浪費CDF圖Fig.3 CDF of the memory wasted

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

2.3 不同類別批處理作業的失敗現象分析

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

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

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

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

表3 不同資源畫像批處理作業的失敗現象

3 TLNM與基于TLNM的預測算法

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

3.1 TLNM核心思想

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

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

(a) CPLM

圖6 TLNM組織架構Fig.6 Architecture of TLNM

3.2 基于TLNM的預測算法

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

算法1 混部特征提取算法

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

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

4 實驗評估

4.1 主要評估指標

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

表4 混淆矩陣

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

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

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

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

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

4.2 混部特征提取算法實驗

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

表5 TLNM算法在不同數據集上的表現

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

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

圖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算法與其他分類器的對比

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

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

表6 TLNM算法的混淆矩陣

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

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

5 結論

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