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

胡亞紅，吳寅超，朱正東

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

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

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

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

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

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

為減少存儲設備異構(gòu)的集群中作業(yè)的執(zhí)行時間，文獻[9]提出的任務調(diào)度策略根據(jù)存儲類型獲得對應存儲設備的讀取速度，同時考慮數(shù)據(jù)存儲的位置，以完成任務優(yōu)先級的計算[9]。

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

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

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

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

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

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

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

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

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

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

1 節(jié)點性能評價及資源調(diào)度算法

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

1.1 用戶作業(yè)類型的判定

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

(1)

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

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

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

1.2 節(jié)點性能優(yōu)先級的評價

異構(gòu)集群中的節(jié)點性能差別較大，有些節(jié)點適合處理CPU密集型作業(yè)，有些則適合運行內(nèi)存密集型作業(yè)。因此根據(jù)當前作業(yè)的類型自適應地分析節(jié)點性能很有必要。

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

P=αS+βD

(2)

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

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

(3)

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

(4)

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

1.3 節(jié)點性能優(yōu)先級影響因素權值的計算

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

圖1 節(jié)點性能優(yōu)先級評價指標體系層次結(jié)構(gòu)模型Fig.1 Hierarchical structure model for the node performance evaluation index system

1.3.1 針對CPU密集型作業(yè)

經(jīng)專家打分，靜態(tài)因素的四個影響因素的判斷矩陣是：

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

動態(tài)因素的四個影響因素經(jīng)專家打分，得到的判斷矩陣為：

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

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

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

因此α=0.5，β=0.5。

1.3.2 針對內(nèi)存密集型作業(yè)

經(jīng)專家打分，靜態(tài)因素的四個影響因素的判斷矩陣是：

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

動態(tài)因素的四個影響因素經(jīng)專家打分，構(gòu)造出的判斷矩陣為：

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

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

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

1.4 算法描述

NPARSA運行于Spark系統(tǒng)中的Master節(jié)點。各個worker節(jié)點實時采集自身的狀態(tài)信息，Master則利用Spark的心跳機制進行信息的收集，完成各節(jié)點實時優(yōu)先級的計算。算法1給出了NPARSA的實現(xiàn)。

算法1 節(jié)點性能自適應的資源調(diào)度算法

2 虛擬機實驗

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

2.1 實驗環(huán)境和數(shù)據(jù)集

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

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

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

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

2.2.1 單作業(yè)實驗

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

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

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

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

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

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

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

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

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

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

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

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

2.2.2 多作業(yè)并行實驗

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

圖6 并行運行的作業(yè)執(zhí)行時間對比Fig.6 Completion time comparison for parallel jobs

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

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

2.2.3 不同節(jié)點數(shù)目實驗

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

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

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

3 小規(guī)模物理集群實驗

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

表4 物理集群實驗節(jié)點配置

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

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

4 結(jié)論

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

為了進一步優(yōu)化NPARSA并驗證其有效性，后續(xù)的研究內(nèi)容包括：

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

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

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