節點實時性能自適應的集群資源分配算法*

胡亞紅，吳寅超，朱正東

(1. 浙江工業大學 計算機科學與技術學院(軟件學院)， 浙江 杭州 310023； 2. 西安交通大學 計算機科學與技術學院， 陜西 西安 710049)

Apache Spark是高性能的大數據處理框架，能夠高效地處理批數據和流式數據[1-3]。但Spark默認的資源分配算法僅匹配作業需求和節點的資源情況，不能夠保證為用戶作業分配到最優資源。資源分配和作業調度屬于NP-hard問題[4]，是當前的研究熱點。綜合考慮集群資源的異構性、節點負載的實時變化和用戶作業不同特點的資源分配算法，能夠有效提高集群性能、縮短作業的完成時間。

為了解決Spark在進行資源分配時未結合節點硬件性能的問題，Xu等提出了一個考慮集群資源屬性和作業特性的啟發式算法，能夠為作業分配到合適的資源[5]。

胡亞紅等提出的基于節點優先級的Spark動態自適應調度算法[6](Spark dynamic adaptive scheduling algorithm, SDASA)則是為了綜合處理集群的異構性和節點的實時性能。該算法中，節點的性能使用優先級來度量，節點的實時優先級根據節點的資源使用情況等工作狀態進行動態計算。

為保證所有作業都能夠在截止時間內完成，文獻[7]介紹了一個考慮作業價值密度和完成時間限制的硬實時調度算法截止時間及價值密度感知(deadline and value density aware, DVDA)算法[7]。但DVDA算法沒有考慮集群中節點的實時資源使用狀況。

針對電力供應受限的系統，文獻[8]分析了常用基于價值的任務調度方法的不足，提出需要在不同的電力供應狀態下選擇不同的能源分配方案，并在此基礎上，提出了基于價值的能耗感知啟發式任務調度算法。

為減少存儲設備異構的集群中作業的執行時間，文獻[9]提出的任務調度策略根據存儲類型獲得對應存儲設備的讀取速度，同時考慮數據存儲的位置，以完成任務優先級的計算[9]。

充分利用具有較高讀寫速度的緩存能夠縮短數據的讀寫時間，加快用戶作業的完成。文獻[10]描述了針對數據密集型任務的并行調度算法。該算法在考慮數據本地性、相關性和負載均衡的條件下，最小化任務的完成時間。此文獻對數據密集型負載進行了分析，但沒有討論其他類型負載的情況。

啟發式算法是解決調度問題的常用算法，Yu等提出使用野草算法(invasive weed optimization，IWO)完成異構集群中的任務調度，目標是最小化任務的完成時間。其中，IWO用于為每一個子作業分配優先級，最早完成時間 (earliest finish time，EFT)算法則為子作業分配最優的運行節點[11]。

由于資源分配問題的復雜性，越來越多的研究采用了機器學習的方法。文獻[12]討論了包含CPU-GPU的異構集群中多個任務共用GPU的任務調度問題?；贕PU上任務的細粒度劃分和任務間的關系，作者提出了基于深度強化學習和神經協同過濾的兩階段任務調度方法，給各任務分配最合適的節點[12]。

Hu 等在研究中發現，為用戶作業分配過多的資源不但會增加資源間的通信開銷，使得作業的完成時間 (job completion time，JCT) 不降反增，而且還造成其他作業無法獲得足夠資源[13]。為了解決資源過度分配問題，首先利用深度神經網絡(deep neural network，DNN) 尋找每個作業的最優集群配置；在獲得作業最優配置后，使用短作業優化算法為作業預分配集群資源；之后使用啟發式算法以平衡多個作業之間的資源分配，從而達到批作業完成時間最短的優化目標。

Spark默認資源調度方法沒有充分考慮計算資源和網絡資源之間的均衡。如果集群用于處理網絡密集型作業，則可能需要在節點間傳輸大量的數據，從而導致集群性能下降。針對該問題，Du等提出了一種任務完成時間感知的作業調度優化方法[14]。該算法首先進行任務完成時間的預測。再利用得到的任務執行時間，從非本地任務調度和網絡的傳輸時間兩方面進行優化。

目前常用的集群資源分配算法沒有綜合考慮節點的實時性能和待運行作業的特點，使得一些節點的性能優勢無法完全發揮，而部分作業的執行時間也沒有達到最優。下面以WordCount負載分別運行于配置不同的三個節點為例說明上述問題。節點配置如表1所示。

表1 WordCount運行時間對比實驗配置

節點1和節點2的區別在于磁盤的性能，節點2的I/O性能優于節點1。節點2和節點3的CPU速度不同，節點2的CPU性能更好。眾所周知，WordCount負載對于節點的CPU性能較為敏感。對比相同的WordCount負載在3個節點的執行時間，可以清楚地看出節點3的運行時間比節點2的長了72.11%，主要原因就是節點3的CPU性能較差。而WordCount在節點1和2的運行時間僅有2%的差別，也說明了WordCount對節點的I/O性能不敏感。因此為用戶作業選擇適合其特點的節點非常有必要。

目前考慮節點與作業類型匹配的研究不是很多。文獻[15]考慮了節點的任務執行特點，使用作業和節點的匹配差異程度作為資源分配的依據。該文中：作業的類型由用戶提供，分為計算密集型和內存密集型。節點的負載由其CPU分量、內存分量和系統其他分量表示。資源分配的基本思想是將CPU利用率低、內存利用率高的節點分配給計算密集型作業；將內存利用率低的節點分配給計算密集型作業。使用該算法時，若是用戶對作業不夠了解，則其指定的作業類型會不準確。另外，節點負載的影響分量考慮得不是非常全面。它主要考慮的是CPU分量、內存分量，其他如磁盤容量等統一歸屬于其他分量，因而不能對除了CPU和內存以外的分量進行更為有效的處理。

本文提出的節點實時性能自適應的集群資源分配算法(node real-time performance adaptive cluster resource scheduling algorithm，NPARSA) 旨在綜合考慮節點的實時處理性能優先級和用戶作業的特點，為作業分配最適合的節點，從而縮短作業運行時間，提升集群的性能。

1 節點性能評價及資源調度算法

NPARSA根據用戶作業的類型自適應地進行節點優先級評價指標權值的選擇，從而計算出各個節點處理此作業的性能優先級。

1.1 用戶作業類型的判定

CPU密集型作業和內存密集型作業是常見類型的用戶作業，它們對于集群有著不同的資源需求。作業的類型可以使用運行作業需要的CPU核數和內存數量進行判定，式(1) 給出了作業類型的判定方法。

(1)

作業的類型使用變量J進行判定。Mr是用戶要求為作業提供的內存數量，而用戶要求提供給作業的CPU核數用變量Cr表示。為了選擇合理的J閾值以區分作業類型，本文進行了大量的實驗。實驗分別使用Spark默認調度算法和NPARSA運行相同的作業，計算出在不同J閾值下NPARSA能夠產生的系統性能提升百分比，實驗結果見表2。

表2 不同J閾值下集群性能提升效果

對表2進行分析發現，當J閾值為1.1時，NPARSA能夠得到最好的效果。因此，將作業類型J的閾值定為1.1。當一個作業的J值大于1.1時，判定該作業為內存密集型，否則判定為CPU密集型作業。NPARSA將根據作業的類型自適應地選擇節點優先級計算時需要的權值。

1.2 節點性能優先級的評價

異構集群中的節點性能差別較大，有些節點適合處理CPU密集型作業，有些則適合運行內存密集型作業。因此根據當前作業的類型自適應地分析節點性能很有必要。

節點性能P由其靜態性能指標和動態性能指標表示，可以使用式 (2) 計算得到。

P=αS+βD

(2)

式中：S表示節點的靜態性能指標；D表示節點的動態性能指標；α和β為對應的權值，且α+β=1。

S=α1Cs+α2Ms+α3Sts+α4Sps

(3)

D=β1Cd+β2Md+β3Spd+β4Std

(4)

其中：節點靜態和動態性能各評價指標的權值α1+α2+α3+α4=1，β1+β2+β3+β4=1。

1.3 節點性能優先級影響因素權值的計算

層次分析法 (analytic hierarchy process，AHP) 是將定量分析和定性分析結合的方法，常用于權值計算。使用AHP確定影響節點性能優先級各因素的權值，圖1給出了節點性能優先級評價指標體系的層次結構模型。請專家針對CPU密集型和內存密集型作業的特點，分別對各影響因素進行評分。這樣，NPARSA就能夠根據當前需要處理作業的類型自適應地進行節點實時性能優先級的計算。

圖1 節點性能優先級評價指標體系層次結構模型Fig.1 Hierarchical structure model for the node performance evaluation index system

1.3.1 針對CPU密集型作業

經專家打分，靜態因素的四個影響因素的判斷矩陣是：

靜態因素權值向量W=[0.113，0.641，0.073，0.173]T，計算得到對應的一致性比率(consistency ratio, CR)的取值為 0.017，通過一致性檢驗。因此各個靜態因素的權值如下：CPU核數為0.173、內存大小為0.641、磁盤容量為0.113、CPU速度為0.073。

動態因素的四個影響因素經專家打分，得到的判斷矩陣為：

動態因素權值向量W=[0.344，0.422，0.156，0.078]T，計算得到CR為0.008，也通過一致性檢驗。則各個動態因素的權值如下：CPU剩余率為0.422、內存剩余率為0.344、磁盤讀寫速度為0.156、磁盤剩余率為0.078。

[5]李俊林：《建立高校高層次人才跟蹤服務管理機制的研究》，《河北工業大學學報》（社會科學版）2011年第2期。

式(2)中的靜態性能指標和動態性能指標對應的判斷矩陣為：

因此α=0.5，β=0.5。

1.3.2 針對內存密集型作業

經專家打分，靜態因素的四個影響因素的判斷矩陣是：

靜態因素權值向量W=[0.138，0.513，0.275，0.074]T， CR為0.003 9，通過一致性檢驗。各個靜態因素的權值如下：CPU核數為0.138、內存大小為0.513、磁盤容量為0.275、CPU速度為0.074。

動態因素的四個影響因素經專家打分，構造出的判斷矩陣為：

動態因素權值向量W=[0.110，0.442，0.262，0.186]T，CR值為0.023，通過一致性檢驗。各個動態因素的權值如下：CPU剩余率為0.110、內存剩余率為0.442、磁盤讀寫速度為0.262、磁盤剩余率為0.186。

α，β取值與CPU密集型作業的計算方法相同，均為0.5。

當需要處理的用戶作業為CPU密集型時，NPARSA使用1.3.1節給出的動靜態因素對應的權值；而當需要處理的用戶作業為內存密集型時，NPARSA則會自適應地選擇1.3.2節給出的動靜態因素對應的權值。

1.4 算法描述

NPARSA運行于Spark系統中的Master節點。各個worker節點實時采集自身的狀態信息，Master則利用Spark的心跳機制進行信息的收集，完成各節點實時優先級的計算。算法1給出了NPARSA的實現。

算法1 節點性能自適應的資源調度算法

2 虛擬機實驗

首先在虛擬機上運行NPARSA，以考察其有效性。

2.1 實驗環境和數據集

實驗中共使用四個虛擬機節點，分別作為Spark系統中的主節點和從節點，節點配置見表3。

為了構建異構環境，各節點的內存容量、CPU核數或磁盤的讀寫速度有所不同。其中主節點的內存較大；從節點2的CPU僅有1核。為了使節點的I/O性能有一定的差異，從節點3的存儲采用了HDD，而其他節點硬盤為SSD。

本文采用的實驗數據來源于BigDataBench[16]，選用了WordCount、Sort、K-means和PageRank四種常用的CPU密集型和內存密集型負載。

2.2 實驗結果及分析

2.2.1 單作業實驗

本實驗的工作負載為WordCount、Sort、K-means和PageRank。其中WordCount、K-means和PageRank要求CPU核數為4，內存為4 GB，屬于CPU密集型負載；Sort要求CPU核數為4，內存為8 GB，是內存密集型負載。

WordCount和Sort實驗中，Spark的資源調度算法分別使用Spark默認調度算法、SDASA[6]、文獻[15]描述的算法(為方便描述，稱為Difference算法)和NPARSA。實驗結果如圖2和圖3所示。

圖2 WordCount作業完成時間比較Fig.2 Comparison of the completion time of WordCount

圖3 Sort作業完成時間比較Fig.3 Comparison of the completion time of Sort

從圖2可以看出，與Spark默認調度算法相比，NPARSA將WordCount作業時間平均縮短了8.33%。與NPARSA動態調整節點優先級相同，SDASA也是結合節點的資源狀態，實時調整集群中各個節點的優先級，但是SDASA沒有考慮用戶作業類型。與SDASA相比，NPARSA將系統性能平均提升了3.45%。與Difference算法進行對比，當WordCount數據量為2 GB時，NPARSA性能略低于Difference算法。但隨著數據量的增加，NPARSA有著更優的表現，系統性能平均提升0.51%。

從圖3可以看出，當運行Sort作業時，NPARSA的表現優于所有的對比算法。與Spark默認算法、SDASA和Difference算法相比，使用NPARSA的作業執行時間平均縮短了9.87%、4.88%和6.22%。

針對K-means和PageRank負載，實驗分別在使用Spark默認調度算法、SDASA和NPARSA的Spark集群中運行。K-means負載的實驗結果如圖4所示。

圖4 K-means作業完成時間比較Fig.4 Comparison of the completion time of K-means

從圖4可以看出，執行K-means作業時，與Spark默認算法相比，NPARSA將作業的執行效率平均提升13.95%；和SDASA相比，平均提升7.85%。

圖5給出了對PageRank負載進行的實驗結果。實驗中數據集的Page數目分別為260、270、280、290和2100。實驗結果表明，相對于Spark默認算法和SDASA，NPARSA完成作業的時間平均縮短了17.46%和6.75%。

圖5 PageRank作業完成時間比較Fig.5 Comparison of the completion time of PageRank

從圖2～5不難看出，無論是運行WordCount、K-means、PageRank這樣的CPU密集型作業，還是Sort這類內存密集型作業，NPARSA的表現都較為優秀。并且隨著作業數據量的增大，使用NPARSA能夠更加有效地縮短作業的執行時間，提升集群效率。

2.2.2 多作業并行實驗

為考察當多個作業并行運算時NPARSA的性能，進行了WordCount和Sort兩類任務的并行運行實驗，圖6給出了實驗結果。

圖6 并行運行的作業執行時間對比Fig.6 Completion time comparison for parallel jobs

可以看到，當多個負載并行執行時，與Spark默認調度算法相比，NPARSA將作業的平均執行時間縮短了10.84%；與Difference算法相比，作業平均執行時間也減少了1.74%。

從上述實驗結果可以看出，因為節點的實時性能是根據所要處理作業的類型計算的，NPARSA能夠給每個作業分配合適的集群資源，從而提高了集群的性能，縮短了作業的完成時間。

2.2.3 不同節點數目實驗

為了測試集群中節點的數目對于NPARSA性能的影響，本節修改了虛擬機實驗中的節點數目，刪除了原四節點集群中的Slave1，構建的新集群中僅包含三個節點。在此三節點集群上使用2.2.1節描述的方式運行PageRank，得到的實驗結果如圖7所示。

圖7 三節點集群中PageRank作業完成時間比較Fig.7 Comparison of the completion time of PageRank in the cluster with 3 nodes

通過分析計算，在三節點集群中，NPARSA完成PageRank作業的時間比Spark默認算法和SDASA平均縮短11.71%和4.28%。在四節點集群中，完成同樣數量的PageRank作業，NPARSA完成作業的時間比Spark默認算法和SDASA平均縮短17.46%和6.75%。因此可以看出，隨著集群中節點數目的增加，NPARSA的優勢可以得到更好的體現。

3 小規模物理集群實驗

為了避免虛擬機實驗的偏差，進一步驗證NPARSA的有效性，搭建了一個小規模的物理集群，完成了PageRank負載的對比實驗。集群中有三個節點，其中一個是主節點，兩個從節點，節點的配置如表4所示。為了使集群具有異構性，三個節點在CPU速度、核數、內存大小和磁盤讀寫速度上配置不同。

表4 物理集群實驗節點配置

實驗中PageRank的Page數目分別為260、270、280、290、2100和2110。實驗運行7次，取各次運行結果的平均值作為實驗結果，如圖8所示。從圖8中可以看出，在物理集群實驗中，NPARSA仍能比Spark默認調度算法和SDASA有更為良好的表現，其完成PageRank作業的平均時間比Spark默認算法減少了37.39%，比SDASA減少了11.93%。

圖8 物理集群中PageRank作業完成時間比較Fig.8 Comparison of the completion time of PageRank running in a physical cluster

4 結論

為了給每一個用戶作業分配最適合其特點的節點，本文提出了NPARSA。NPARSA在計算節點的實時優先級時，會根據當前作業的類型自適應地選擇節點優先級評價體系中各指標的權值。虛擬機實驗和小規模的物理集群實驗結果均表明，與Spark默認調度算法、SDASA和Difference算法相比，NPARSA能夠減少用戶作業的執行時間。

為了進一步優化NPARSA并驗證其有效性，后續的研究內容包括：

1) 采用深度學習的方法對更多種用戶作業的類型，如I/O密集型、網絡密集型等進行準確判斷，從而使算法可以更好地為更多類型的作業進行有效的資源分配。

2)增加節點靜態和動態資源影響因素，如CPU的最大頻率、內存的帶寬等，以便更加全面準確地衡量節點的實時性能。

3) 在大規模的物理集群上進行實驗，進一步驗證算法的可擴展性。