面向Spark的批處理應(yīng)用執(zhí)行時(shí)間預(yù)測(cè)模型

李 碩，梁 毅

北京工業(yè)大學(xué) 信息學(xué)部，北京100124

Spark分布式內(nèi)存計(jì)算系統(tǒng)已被廣泛應(yīng)用于大數(shù)據(jù)處理的眾多場(chǎng)景中[1-2]。批處理應(yīng)用是Spark系統(tǒng)支撐的一類主要應(yīng)用，其特點(diǎn)是基于有向無(wú)環(huán)圖（Directed Acyclic Graph，DAG）計(jì)算模型對(duì)靜態(tài)數(shù)據(jù)集進(jìn)行并行處理。批處理應(yīng)用執(zhí)行時(shí)間預(yù)測(cè)是保證批處理應(yīng)用達(dá)到軟實(shí)時(shí)需求、指導(dǎo)Spark系統(tǒng)資源分配、應(yīng)用均衡決策以及保障批處理應(yīng)用服務(wù)質(zhì)量的基礎(chǔ)。然而，如何精確預(yù)測(cè)Spark批處理應(yīng)用執(zhí)行時(shí)間仍然是一個(gè)開(kāi)放的技術(shù)挑戰(zhàn)。

近年來(lái)，針對(duì)大數(shù)據(jù)系統(tǒng)的批處理應(yīng)用執(zhí)行時(shí)間預(yù)測(cè)研究工作可分為兩類，一是基于源代碼分析的執(zhí)行時(shí)間預(yù)測(cè)，二是選取相關(guān)因素構(gòu)建執(zhí)行時(shí)間預(yù)測(cè)模型。在基于源代碼分析預(yù)測(cè)的工作中，PACE系統(tǒng)及Pablo系統(tǒng)通過(guò)分析源碼中包含的每一類操作的執(zhí)行復(fù)雜度和執(zhí)行次數(shù)來(lái)預(yù)測(cè)應(yīng)用的執(zhí)行時(shí)間[3-4]。然而，這類方法屬于基于源代碼的白盒分析，不能適用于無(wú)法獲取源代碼的第三方批處理應(yīng)用。在選取相關(guān)因素構(gòu)建執(zhí)行時(shí)間預(yù)測(cè)模型的相關(guān)工作中，文獻(xiàn)[5]選取輸入數(shù)據(jù)規(guī)模作為相關(guān)因素，針對(duì)Hadoop批處理應(yīng)用，采用KNN方法構(gòu)建批處理應(yīng)用執(zhí)行時(shí)間預(yù)測(cè)模型。文獻(xiàn)[6-7]在上述基礎(chǔ)上又增加了資源分配規(guī)模作為相關(guān)因素來(lái)構(gòu)建預(yù)測(cè)模型，針對(duì)Hadoop批處理應(yīng)用，文獻(xiàn)[6]中應(yīng)用首先通過(guò)資源監(jiān)控模塊對(duì)應(yīng)用的計(jì)算及網(wǎng)絡(luò)資源進(jìn)行監(jiān)控，獲取到計(jì)算和網(wǎng)絡(luò)資源后，利用SVM模型對(duì)應(yīng)用的執(zhí)行時(shí)間進(jìn)行評(píng)估；文獻(xiàn)[7]針對(duì)Hadoop批處理應(yīng)用，利用LR模型來(lái)預(yù)測(cè)應(yīng)用的執(zhí)行時(shí)間，從而為任務(wù)調(diào)度奠定基礎(chǔ)。然而，既有基于相關(guān)因素建模的工作均采用針對(duì)不同批處理應(yīng)用統(tǒng)一建模的方法，且考慮因素較為單一。在Spark系統(tǒng)中，批處理應(yīng)用的計(jì)算具有多樣化特征，在相同的數(shù)據(jù)輸入規(guī)模和資源配置下，應(yīng)用執(zhí)行時(shí)間具有較大的差異；并且隨著輸入數(shù)據(jù)規(guī)模和資源配置的改變，不同應(yīng)用的執(zhí)行時(shí)間變化趨勢(shì)也差異較大。

針對(duì)上述問(wèn)題，本文提出了一種區(qū)分應(yīng)用特征的Spark批處理應(yīng)用執(zhí)行時(shí)間預(yù)測(cè)方法。該方法選擇典型的基準(zhǔn)程序測(cè)試集Hibench作為基礎(chǔ)，首先根據(jù)Spark系統(tǒng)中批處理應(yīng)用執(zhí)行原理選取分類方法影響因素，利用斯皮爾曼相關(guān)系數(shù)從中篩選出強(qiáng)相關(guān)指標(biāo)并構(gòu)建Spark批處理應(yīng)用執(zhí)行時(shí)間分類方法；然后在每一類批處理應(yīng)用中充分分析了影響應(yīng)用執(zhí)行時(shí)間的指標(biāo)并利用主成分分析法（PCA）和梯度提升決策樹(shù)算法（GBDT）對(duì)應(yīng)用執(zhí)行時(shí)間進(jìn)行預(yù)測(cè)；最后當(dāng)即席應(yīng)用到達(dá)之后，先判斷其所屬應(yīng)用類別繼而使用已構(gòu)建的預(yù)測(cè)模型來(lái)預(yù)測(cè)其執(zhí)行時(shí)間。實(shí)驗(yàn)結(jié)果表明，與采用統(tǒng)一預(yù)測(cè)模型相比，本文提出的基于分類的Spark批處理應(yīng)用執(zhí)行時(shí)間預(yù)測(cè)模型可使得預(yù)測(cè)結(jié)果的均方根誤差和平均絕對(duì)百分誤差平均降低32.1%和33.9%。

1 Spark批處理應(yīng)用的執(zhí)行時(shí)間特征分析

1.1 Spark基本原理

在Spark中，RDD（Resilient Distributed Datasets）是分布式海量數(shù)據(jù)集的抽象表達(dá)，用以表示Spark應(yīng)用在數(shù)據(jù)處理過(guò)程中所產(chǎn)生的分布存儲(chǔ)于多個(gè)計(jì)算節(jié)點(diǎn)的數(shù)據(jù)。每個(gè)計(jì)算節(jié)點(diǎn)保存RDD的一部分，稱為RDD分片。Spark計(jì)算模型如圖1所示[8]。

在一個(gè)Spark應(yīng)用中，根據(jù)計(jì)算邏輯的不同，可存在一個(gè)或多個(gè)作業(yè)。作業(yè)執(zhí)行時(shí)，調(diào)度器會(huì)依據(jù)當(dāng)前作業(yè)對(duì)RDD的操作類型將作業(yè)劃分為多個(gè)階段（Stage），并構(gòu)建DAG圖來(lái)對(duì)作業(yè)中的計(jì)算邏輯進(jìn)行描述。Spark作業(yè)中存在依賴關(guān)系的Stage間串行執(zhí)行，一個(gè)Stage內(nèi)部包含多個(gè)任務(wù)來(lái)并行處理RDD數(shù)據(jù)。在DAG調(diào)度中劃分Stage的依據(jù)是RDD之間的依賴關(guān)系，RDD之間的依賴關(guān)系分為窄依賴和寬依賴。窄依賴指父RDD的每個(gè)分區(qū)只被子RDD的一個(gè)分區(qū)所使用，例如圖1中RDD1與RDD4間的操作。寬依賴指父RDD的每個(gè)分區(qū)都可能被多個(gè)子RDD分區(qū)所使用，例如RDD2與RDD3間操作。

圖1 Spark計(jì)算模型

任務(wù)是Spark應(yīng)用執(zhí)行的基本單元，Spark中任務(wù)的執(zhí)行過(guò)程為如下幾個(gè)階段：數(shù)據(jù)拉取、數(shù)據(jù)聚集、數(shù)據(jù)合并、數(shù)據(jù)計(jì)算、數(shù)據(jù)存儲(chǔ)。Spark任務(wù)執(zhí)行過(guò)程如圖2所示：首先對(duì)任務(wù)所需數(shù)據(jù)進(jìn)行遠(yuǎn)程拉取，任務(wù)每一批次拉取的數(shù)據(jù)會(huì)被放入用以進(jìn)行數(shù)據(jù)聚合的操作的內(nèi)存緩沖區(qū)中，當(dāng)緩沖區(qū)內(nèi)數(shù)據(jù)規(guī)模超過(guò)閾值時(shí)，將緩沖區(qū)內(nèi)數(shù)據(jù)溢寫至磁盤。數(shù)據(jù)在被不斷拉取的過(guò)程中也不斷進(jìn)行聚集。接著讀取本地?cái)?shù)據(jù)至內(nèi)存中并進(jìn)行聚合操作。任務(wù)所需全部數(shù)據(jù)進(jìn)行聚集完成后，合并后的數(shù)據(jù)被立即計(jì)算，計(jì)算結(jié)果寫入內(nèi)存緩沖器或溢寫到磁盤中，當(dāng)全部數(shù)據(jù)計(jì)算完畢，將數(shù)據(jù)進(jìn)行合并，該任務(wù)執(zhí)行結(jié)束。任務(wù)執(zhí)行過(guò)程中，Shuffle的性能高低直接影響Spark批處理應(yīng)用執(zhí)行時(shí)間。由上文可知，Spark作業(yè)中存在依賴關(guān)系的Stage間串行執(zhí)行，不同Stage的數(shù)據(jù)傳輸操作稱為Shuffle[9]。Shuffle過(guò)程中，上一個(gè)Stage的每個(gè)任務(wù)將自己處理的當(dāng)前分區(qū)中的數(shù)據(jù)相同key寫入一個(gè)分區(qū)文件中，接著下一個(gè)Stage的任務(wù)從上一個(gè)Stage的所有任務(wù)所在的節(jié)點(diǎn)上將屬于自己的分區(qū)數(shù)據(jù)拉取過(guò)來(lái)。從中可以看出，Spark任務(wù)執(zhí)行過(guò)程是一個(gè)大量消耗內(nèi)存資源、CPU資源、網(wǎng)絡(luò)IO以及磁盤IO的過(guò)程。

圖2 Spark任務(wù)執(zhí)行過(guò)程

1.2 Spark批處理應(yīng)用的執(zhí)行時(shí)間可分類特征分析

本節(jié)基于具有代表性的Spark批處理應(yīng)用量化分析輸入數(shù)據(jù)規(guī)模和資源配置對(duì)應(yīng)用執(zhí)行時(shí)間的影響，驗(yàn)證Spark批處理應(yīng)用的執(zhí)行時(shí)間具有可分類特性。首先選取了HiBench基準(zhǔn)測(cè)試程序集中9個(gè)典型批處理應(yīng)用：PageRank、Wordcount、Sort、Terasort、Kmeans、Bayes、Nweight、LR以及LiR，對(duì)批處理應(yīng)用的執(zhí)行時(shí)間進(jìn)行分析。圖3～5分別給出了不同輸入數(shù)據(jù)規(guī)模、CPU和內(nèi)存配置下，Spark批處理應(yīng)用的執(zhí)行時(shí)間比較。

圖3 不同輸入數(shù)據(jù)規(guī)模下Spark批處理應(yīng)用執(zhí)行時(shí)間

圖4 不同CPU配置下Spark批處理應(yīng)用執(zhí)行時(shí)間

圖5 不同內(nèi)存配置下Spark批處理應(yīng)用執(zhí)行時(shí)間

綜上可觀測(cè)到：（1）在相同的輸入數(shù)據(jù)規(guī)模與資源量配置下，應(yīng)用間的執(zhí)行時(shí)間具有明顯的差異。對(duì)于所有應(yīng)用，例如當(dāng)輸入數(shù)據(jù)規(guī)模均為2 GB時(shí)，Kmeans、PageRank、Nweight、LR、LiR的執(zhí)行時(shí)間達(dá)到2 000 s，Wordcount、Terasort、Bayes的執(zhí)行時(shí)間約1 000 s，而Sort的執(zhí)行時(shí)間僅約200 s。雖然不同應(yīng)用的執(zhí)行時(shí)間各不相同，但這些應(yīng)用的執(zhí)行時(shí)間呈現(xiàn)較為明顯的值域分布。（2）變動(dòng)應(yīng)用輸入數(shù)據(jù)規(guī)模或資源配置情況下，批處理應(yīng)用執(zhí)行時(shí)間的分類具有穩(wěn)定性。例如Kmeans、PageRank、Nweight、LR、LiR應(yīng)用在不同的數(shù)據(jù)規(guī)模、資源配置下運(yùn)行，執(zhí)行時(shí)間呈現(xiàn)出相似的變化趨勢(shì)特征。由此可推斷，應(yīng)用執(zhí)行時(shí)間的分類結(jié)果基本不受應(yīng)用輸入數(shù)據(jù)規(guī)模和資源配置的影響，Spark批處理應(yīng)用執(zhí)行時(shí)間具有可分類的特征。

2 Spark批處理應(yīng)用執(zhí)行時(shí)間分類方法

本章給出Spark批處理應(yīng)用執(zhí)行時(shí)間的分類方法。由于HiBench基準(zhǔn)測(cè)試程序集涵蓋了Spark主要應(yīng)用領(lǐng)域中的核心數(shù)據(jù)操作，具有全面性和普遍性。因此本文仍選取1.2節(jié)中9個(gè)典型批處理應(yīng)用作為測(cè)試應(yīng)用：PageRank、Wordcount、Sort、Terasort、Kmeans、Bayes、Nweight、LR以及LiR，上述應(yīng)用代表圖計(jì)算、智能搜索、機(jī)器學(xué)習(xí)等多個(gè)領(lǐng)域的核心數(shù)據(jù)處理操作。依據(jù)上述應(yīng)用，首先選取影響分類的指標(biāo)，然后基于所選指標(biāo)給出應(yīng)用分類方法。

2.1 備選指標(biāo)的選取

顯然，作為Spark批處理應(yīng)用分類的指標(biāo)應(yīng)該具有穩(wěn)定性，即所選取的指標(biāo)在不同的輸入數(shù)據(jù)規(guī)模和資源配置下，應(yīng)呈現(xiàn)出較為穩(wěn)定的量值，以保證應(yīng)用分類的準(zhǔn)確性。依據(jù)Spark批處理應(yīng)用的運(yùn)行特征，分別從Spark應(yīng)用的計(jì)算特征和對(duì)資源使用的特征進(jìn)行指標(biāo)選取。

由1.1節(jié)Spark應(yīng)用的運(yùn)行特點(diǎn)可知，Spark應(yīng)用的執(zhí)行過(guò)程是一個(gè)大量消耗CPU、內(nèi)存、磁盤I/O和網(wǎng)絡(luò)I/O資源的過(guò)程。將根據(jù)上述特點(diǎn)在應(yīng)用層和系統(tǒng)層選取影響Spark批處理應(yīng)用執(zhí)行時(shí)間的備選指標(biāo)[10-11]。

應(yīng)用層首先可以獲取最直觀的性能觀察指標(biāo)，本文選取的應(yīng)用層指標(biāo)如表1所示。

表1 應(yīng)用層備選指標(biāo)信息

從應(yīng)用層的角度看，影響批處理應(yīng)用執(zhí)行時(shí)間的因素包括算子規(guī)模、算子類型的比例以及數(shù)據(jù)的變化規(guī)律。算子的規(guī)模和算子的比例可以體現(xiàn)應(yīng)用的算法復(fù)雜度，其中窄依賴算子主要與計(jì)算操作相關(guān)，寬依賴算子涉及I/O通訊和內(nèi)存操作。數(shù)據(jù)變化規(guī)律可以通過(guò)輸入數(shù)據(jù)、中間數(shù)據(jù)以及輸出數(shù)據(jù)的比例得出。顯然，這些指標(biāo)僅與應(yīng)用本身有關(guān)，與輸入數(shù)據(jù)規(guī)模和資源配置無(wú)關(guān)。

從系統(tǒng)的角度來(lái)說(shuō)，與Spark批處理應(yīng)用執(zhí)行時(shí)間相關(guān)的資源包括CPU、內(nèi)存、磁盤和網(wǎng)絡(luò)。因此，本文選取的系統(tǒng)層指標(biāo)如表2所示。

表2 系統(tǒng)層備選指標(biāo)信息

Spark批處理應(yīng)用執(zhí)行過(guò)程會(huì)消耗計(jì)算資源、內(nèi)存資源、網(wǎng)絡(luò)和磁盤IO，對(duì)應(yīng)著計(jì)算行為、訪存行為以及通信行為。因此計(jì)算訪存比和計(jì)算通信比可以直觀反映出Spark批處理應(yīng)用的行為特征。已知應(yīng)用消耗的計(jì)算資源、訪存資源和通信資源只與應(yīng)用本身的操作算子有關(guān)，并且隨著輸入數(shù)據(jù)規(guī)模的變化，應(yīng)用所消耗的上述資源也會(huì)出現(xiàn)相同的變化趨勢(shì)。因此，計(jì)算訪存比和計(jì)算通信比具有穩(wěn)定性。

2.2 強(qiáng)相關(guān)指標(biāo)的篩選

在進(jìn)行后續(xù)分析之前，為了降低分類方法的復(fù)雜度，選用斯皮爾曼相關(guān)系數(shù)（Spearman’s rank correlation coefficient）作為相關(guān)性分析的方法，從備選指標(biāo)中選擇與應(yīng)用執(zhí)行時(shí)間相關(guān)性最強(qiáng)的指標(biāo)。斯皮爾曼相關(guān)系數(shù)是分析兩個(gè)變量間相關(guān)性的常用方法[12]。斯皮爾曼相關(guān)系數(shù)計(jì)算公式為：

其中，N表示觀測(cè)值的總數(shù)量，di=xi-yi，其中元素xi、yi分別為Xi在X中的排行以及Yi在Y中的排行。

本文采用控制變量法，分別變化上述備選指標(biāo)，得到Hibench中9個(gè)典型應(yīng)用在上述條件下的執(zhí)行時(shí)間。根據(jù)所得數(shù)據(jù)集，分別計(jì)算每個(gè)指標(biāo)與應(yīng)用執(zhí)行時(shí)間的斯皮爾曼相關(guān)系數(shù)。首先對(duì)每個(gè)指標(biāo)集合和應(yīng)用執(zhí)行時(shí)間集合X、Y中的所有值進(jìn)行排序，同時(shí)為升序或者降序，然后將對(duì)應(yīng)元素的排行相減得到一個(gè)排行差分的集合d，然后帶入公式（1）進(jìn)行計(jì)算。其中，與應(yīng)用執(zhí)行時(shí)間相關(guān)系數(shù)較大的性能數(shù)據(jù)如表3所示。

表3 強(qiáng)相關(guān)性能指標(biāo)

選擇斯皮爾曼相關(guān)系數(shù)值大于0.5的備選指標(biāo)作為與應(yīng)用執(zhí)行時(shí)間具有較強(qiáng)的相關(guān)性的指標(biāo)。根據(jù)該標(biāo)準(zhǔn)，本文選取了如下的指標(biāo)作為Spark批處理應(yīng)用執(zhí)行時(shí)間分類方法的特征指標(biāo)：MIA、OIA、NO、WDOR、NDOR以及CCR。

2.3 Spark批處理應(yīng)用執(zhí)行時(shí)間的分類方法

由于各種類型的特征指標(biāo)的量綱不同，數(shù)值差異性較大。為了減少不同量綱的數(shù)值差異帶來(lái)的影響，本文首先對(duì)指標(biāo)數(shù)據(jù)進(jìn)行歸一化預(yù)處理，把所有的樣本指標(biāo)數(shù)據(jù)轉(zhuǎn)化為（0，1）之間的數(shù)值。本文選用均值漂移聚類算法對(duì)應(yīng)用執(zhí)行時(shí)間進(jìn)行分類[13]。均值漂移聚類算法通過(guò)將中心點(diǎn)的候選集更新為滑動(dòng)窗口內(nèi)點(diǎn)的均值來(lái)確定每個(gè)類簇的中心點(diǎn)。與K-means算法相比，均值漂移聚類會(huì)自動(dòng)發(fā)現(xiàn)類簇的數(shù)量，但是需要用戶首先設(shè)置好半徑值r。隨后，在迭代過(guò)程中尋找到能夠使評(píng)價(jià)函數(shù)E最小的分類方式，計(jì)算方法如下：

式中，Pj表示類簇i的某個(gè)數(shù)據(jù)點(diǎn)，Oi表示類簇i的中心點(diǎn)，k為類簇個(gè)數(shù)，a為手動(dòng)設(shè)置的權(quán)重，使得加號(hào)前后兩部分在統(tǒng)一的數(shù)量集。

根據(jù)前文所述的均值漂移聚類算法可知，該算法中有如下的關(guān)鍵要素：樣本的定義和生成、數(shù)據(jù)點(diǎn)距離的計(jì)算方法選取和半徑值的設(shè)置。在樣本的生成過(guò)程中，本文采用控制變量的方法，變化2.1節(jié)中與應(yīng)用執(zhí)行時(shí)間強(qiáng)相關(guān)的指標(biāo)，尋找在當(dāng)前的指標(biāo)組合下，該批處理應(yīng)用的執(zhí)行時(shí)間。最終，模型中訓(xùn)練樣本集的形式化定義如下：

其中，xij表示第i個(gè)樣本的第j個(gè)特征屬性的特征值，m是樣本的個(gè)數(shù)，n是特征指標(biāo)的個(gè)數(shù)，yi表示在特征集{xi1,xi2,…,xin}下的應(yīng)用執(zhí)行時(shí)間。

對(duì)于數(shù)據(jù)點(diǎn)間距離的計(jì)算，常見(jiàn)的計(jì)算方法有曼哈頓距離、切比雪夫距離、歐式距離以及標(biāo)準(zhǔn)化歐氏距離等。然而曼哈頓距離、切比雪夫距離和歐式距離這三種距離計(jì)算方法都存在明顯的問(wèn)題：未考慮各個(gè)指標(biāo)的量綱和數(shù)量級(jí)的差異。而本文提出的分類方法中特征指標(biāo)的量綱和數(shù)量級(jí)差異明顯，例如輸出數(shù)據(jù)與輸入數(shù)據(jù)比例的均值（OIA）與算子個(gè)數(shù)（NO）會(huì)有較大量級(jí)差異。因此，本文采用標(biāo)準(zhǔn)化歐氏距離來(lái)消除量綱和數(shù)量級(jí)對(duì)距離計(jì)算的影響。標(biāo)準(zhǔn)歐氏距離計(jì)算公式如式（3）所示：

其中，sk為兩個(gè)數(shù)據(jù)點(diǎn)間第k個(gè)特征值的標(biāo)準(zhǔn)差。

篩選出影響分類方法的強(qiáng)相關(guān)指標(biāo)共有6個(gè)，又選取標(biāo)準(zhǔn)化歐式距離作為數(shù)據(jù)點(diǎn)間距離的計(jì)算方法。因此在一個(gè)6維空間里，兩點(diǎn)間的距離區(qū)間為[0,6]，約為[0，2.5]。因此，本文在設(shè)置半徑值r時(shí)，分別設(shè)置半徑值從0變化到2.5，步長(zhǎng)為0.05。選取有代表性的輸入數(shù)據(jù)規(guī)模和資源配置進(jìn)行測(cè)試，運(yùn)行均值漂移聚類后計(jì)算聚類劃分評(píng)價(jià)函數(shù)E的值，結(jié)果如圖6所示。

圖6 不同半徑值下的評(píng)價(jià)函數(shù)值

從圖6中能夠看出，當(dāng)半徑值從0.05升高到0.5時(shí)，隨著半徑值的增加，E值呈下降趨勢(shì)；當(dāng)半徑值從0.5升高為1.5時(shí)，E值呈波動(dòng)趨勢(shì)；當(dāng)半徑值從1.5升高為2.5時(shí)，E值呈上升趨勢(shì)。其中當(dāng)半徑值為1.5時(shí)，E值處于最低值。這是因?yàn)楫?dāng)半徑為0時(shí)，每個(gè)數(shù)據(jù)點(diǎn)各自為一類，類簇?cái)?shù)量k值最大，使得E值很大；隨著半徑值增大，雖類簇?cái)?shù)量k減小，但每類中非中心點(diǎn)到對(duì)應(yīng)類簇中心點(diǎn)距離和增大，因此E值呈現(xiàn)波動(dòng)變化；當(dāng)半徑值從1.5升高為2.5時(shí)，每類中非中心點(diǎn)到對(duì)應(yīng)類簇中心點(diǎn)距離和大幅度增大，E值呈上升趨勢(shì)。

3 Spark批處理應(yīng)用執(zhí)行時(shí)間預(yù)測(cè)模型

第1章證明了常見(jiàn)的Spark批處理應(yīng)用具有可分類的特征，并從應(yīng)用層和系統(tǒng)層篩選出強(qiáng)相關(guān)指標(biāo)構(gòu)建分類方法，接下來(lái)將在每一類應(yīng)用中首先利用PCA來(lái)提取影響應(yīng)用執(zhí)行時(shí)間的主成分，然后利用GBDT來(lái)建立Spark批處理應(yīng)用執(zhí)行時(shí)間預(yù)測(cè)模型。

3.1 預(yù)測(cè)模型的備選指標(biāo)選取

首先根據(jù)1.1節(jié)Spark應(yīng)用執(zhí)行流程來(lái)篩選出所有可能影響應(yīng)用執(zhí)行時(shí)間的參數(shù)。根據(jù)Spark應(yīng)用執(zhí)行流程可以看出，影響應(yīng)用執(zhí)行時(shí)間的配置參數(shù)主要包括應(yīng)用屬性、Shuffle相關(guān)、內(nèi)存管理、執(zhí)行行為和資源調(diào)度等，因此本文列舉出備選配置參數(shù)集如表4所示。

3.2 預(yù)測(cè)模型的構(gòu)建

在樣本的生成過(guò)程中，變化應(yīng)用的輸入數(shù)據(jù)規(guī)模以及配置參數(shù)的組合，尋找在當(dāng)前輸入數(shù)據(jù)規(guī)模以及配置參數(shù)下，該批處理應(yīng)用的執(zhí)行時(shí)間。最終，模型中訓(xùn)練樣本集的形式化定義如下，對(duì)于每一類應(yīng)用L，樣本數(shù)據(jù)集可以表示為：

其中，xij表示為類別L中第i個(gè)樣本的第j個(gè)特征屬性的取值，m是樣本的個(gè)數(shù)，n是特征指標(biāo)的個(gè)數(shù)，yi表示在特征取值{xi1,xi2,…,xin}下的應(yīng)用執(zhí)行時(shí)間。

接下來(lái)本文首先對(duì)分類結(jié)果中的每個(gè)應(yīng)用類別進(jìn)行參數(shù)精簡(jiǎn)，得到精簡(jiǎn)參數(shù)集合，然后將每個(gè)應(yīng)用類別的精簡(jiǎn)參數(shù)集合和輸入數(shù)據(jù)規(guī)模進(jìn)行組合，選取適當(dāng)?shù)念A(yù)測(cè)理論工具進(jìn)行預(yù)測(cè)。由于目前影響批處理應(yīng)用執(zhí)行時(shí)間的參數(shù)多樣，且不同的參數(shù)之間的聯(lián)系也非常復(fù)雜，PCA非常適用于這種特征量多樣的數(shù)據(jù)集。PCA主要是利用降維的思想，把數(shù)據(jù)從高維空間映射到低維空間，同時(shí)使低維數(shù)據(jù)能夠最大限度地保留高維數(shù)據(jù)的方差信息[14-15]。首先將樣本中的特征值按列組成m×n的矩陣，為了避免計(jì)算結(jié)果受指標(biāo)量綱和數(shù)量級(jí)的影響，需對(duì)上述矩陣進(jìn)行標(biāo)準(zhǔn)化處理，計(jì)算相關(guān)矩陣并求取相關(guān)矩陣的特征根、特征向量、貢獻(xiàn)率和累積貢獻(xiàn)率。累積貢獻(xiàn)率表示前k個(gè)主成分從所有備選指標(biāo)中提取出的信息量。在本文的實(shí)驗(yàn)中，前5個(gè)主成分包含總信息量的90%，說(shuō)明前5個(gè)主成分足以說(shuō)明問(wèn)題。因此選擇5個(gè)主成分作為Spark批處理應(yīng)用執(zhí)行時(shí)間預(yù)測(cè)模型的主成分。

表4 預(yù)測(cè)模型的備選參數(shù)集

GBDT是一種模型樹(shù)，具有強(qiáng)大的預(yù)測(cè)能力。核心是在每一次迭代中，后一個(gè)弱分類器訓(xùn)練的是前一個(gè)弱分類器的誤差，且沿著最大下降梯度的方向[15]。GBDT調(diào)參時(shí)間短，預(yù)測(cè)準(zhǔn)確率較高，且不容易出現(xiàn)過(guò)擬合現(xiàn)象?？蓪BDT視為一個(gè)將多個(gè)弱分類器線性組合后對(duì)數(shù)據(jù)進(jìn)行預(yù)測(cè)的算法，該模型可以表示為：

其中，b(x;γm)為基函數(shù)（即單個(gè)弱分類器），γm為基函數(shù)的參數(shù)（即弱分類器中特征的權(quán)重向量），βm為基函數(shù)的系數(shù)（即弱分類器在線性組合時(shí)的權(quán)重），f(x)就是基函數(shù)的線性組合。

GBDT算法中典型的損失函數(shù)包括均方差損失函數(shù)、絕對(duì)損失函數(shù)、Huber函數(shù)和分位數(shù)函數(shù)。本文分別選取有代表性的輸入數(shù)據(jù)規(guī)模和資源配置來(lái)測(cè)試不同損失函數(shù)的預(yù)測(cè)精度，從而選出最合適的損失函數(shù)。測(cè)試結(jié)果如表5所示。

表5 GBDT在不同損失函數(shù)下的預(yù)測(cè)精度

由表5可知，絕對(duì)損失函數(shù)的預(yù)測(cè)精度最好，因此本文選擇絕對(duì)損失函數(shù)作為GBDT的損失函數(shù)。

3.3 即席應(yīng)用的類別匹配

本小節(jié)將介紹針對(duì)用戶提交的即席Spark批處理應(yīng)用如何進(jìn)行類別匹配。即席應(yīng)用的類別匹配流程如算法1所示。

算法1即席應(yīng)用的類別匹配

輸入：輸入數(shù)據(jù)集合DS={ds1,ds2,…,dsn}批處理應(yīng)用分類結(jié)果中類簇中心點(diǎn)集合O={O1,O2,…,Om}。

輸出：即席應(yīng)用所屬類簇。

1.i=0,j=0,MinDis=∞

2.F=[]//用于收集Spark批處理應(yīng)用執(zhí)行時(shí)間分類方法特征指標(biāo)的集合

3.Whilei＜ndo

F[]i=collectFeature(dsi)//收集即席應(yīng)用在輸入數(shù)據(jù)集dsi下分類方法的特征指標(biāo)4.end While

5.P=mean(F)//計(jì)算上述特征指標(biāo)值的均值，得到數(shù)據(jù)點(diǎn)P

6.Whilej＜mdo//找到距離數(shù)據(jù)點(diǎn)P最短的類簇中心點(diǎn)Oj

7.d=calDistance(P,Oj)//計(jì)算數(shù)據(jù)點(diǎn)P和類簇中心Oj的距離

8. Ifd＜MinDis

9.MinDis=d

10.end If

11.end While

12.returnj

當(dāng)用戶提交新的Spark應(yīng)用時(shí)，首先將該應(yīng)用運(yùn)行在一組小規(guī)模輸入數(shù)據(jù)集DS={ds1,ds2,…,dsn}下，對(duì)于每個(gè)輸入數(shù)據(jù)集dsi，分別收集Spark批處理應(yīng)用執(zhí)行時(shí)間分類方法的特征指標(biāo)MIA、OIA、NO、WDOR、NDOR、CCR。隨后分別計(jì)算這些指標(biāo)的均值作為最終的特征指標(biāo)，生成數(shù)據(jù)點(diǎn)P，隨后對(duì)于分類方法中各個(gè)類簇的中心點(diǎn)Oj分別根據(jù)公式（3）計(jì)算距離d。最終，將使距離d最小的類別j作為該應(yīng)用的類別。

4 性能評(píng)測(cè)

4.1 評(píng)價(jià)指標(biāo)

為了評(píng)估Spark批處理應(yīng)用執(zhí)行時(shí)間預(yù)測(cè)模型的性能，本文選擇均方根誤差（RMSE）和平均絕對(duì)百分誤差（MAPE）來(lái)衡量模型的預(yù)測(cè)精度。其中，均方根誤差（RMSE）對(duì)預(yù)測(cè)誤差中的特大誤差非常敏感，平均絕對(duì)百分誤差（MAPE）可以衡量模型相對(duì)誤差。其計(jì)算公式如下所示：

其中，N為樣本數(shù)量，y?i為批處理應(yīng)用執(zhí)行時(shí)間預(yù)測(cè)值，yi為批處理應(yīng)用執(zhí)行時(shí)間真實(shí)值。

4.2 效果評(píng)價(jià)

本文選取隨機(jī)森林算法（RF）、交替最小二乘（ALS）、支持向量機(jī)（SVM）、詞頻統(tǒng)計(jì)（Wordcount）以及K均值聚類（Kmeans）作為Spark批處理應(yīng)用來(lái)評(píng)價(jià)本文提出的預(yù)測(cè)模型的性能。首先在變化輸入數(shù)據(jù)規(guī)模與資源配置下，進(jìn)行本文提出的預(yù)測(cè)模型與KNN、SVM、LR算法的性能對(duì)比[2-3，7]；然后在固定輸入數(shù)據(jù)規(guī)模與資源配置前提下，對(duì)本文提出的預(yù)測(cè)模型與無(wú)分類前提下、無(wú)PCA前提下的預(yù)測(cè)模型進(jìn)行性能對(duì)比。

首先在固定資源量下，改變應(yīng)用的輸入數(shù)據(jù)規(guī)模分別為500 MB、1 GB、2 GB、4 GB，進(jìn)行若干次實(shí)驗(yàn)，得到各評(píng)價(jià)指標(biāo)值如表6所示。

表6 不同預(yù)測(cè)模型在改變輸入數(shù)據(jù)規(guī)模下的預(yù)測(cè)精度

由表6可知，在固定資源配置、變換輸入數(shù)據(jù)規(guī)模的條件下，本文提出的預(yù)測(cè)模型在所有測(cè)試應(yīng)用的各組數(shù)據(jù)集上均比KNN獲得了較低的RMSE和MAPE，經(jīng)計(jì)算可得，與KNN相比，本文提出的預(yù)測(cè)模型使得RMSE和MAPE最大降低25.7%和28.5%。

然后在固定輸入數(shù)據(jù)規(guī)模與CPU資源下，改變應(yīng)用的內(nèi)存資源分別為1 GB、2 GB、3 GB，進(jìn)行若干次實(shí)驗(yàn)，得到各評(píng)價(jià)指標(biāo)值如表7所示。

表7 不同預(yù)測(cè)模型在改變內(nèi)存資源下的預(yù)測(cè)精度

由表7可知，在固定輸入數(shù)據(jù)規(guī)模與CPU資源，改變內(nèi)存資源的條件下，本文提出的預(yù)測(cè)模型在所有測(cè)試應(yīng)用的各組數(shù)據(jù)集上均比SVM和LR獲得了較低的RMSE和MAPE，經(jīng)計(jì)算可得，與SVM和LR相比，本文提出的預(yù)測(cè)模型使得RMSE和MAPE最大降低50.1%和47%。

最后在固定輸入數(shù)據(jù)規(guī)模與內(nèi)存資源下，改變應(yīng)用的CPU資源分別為2cores、3cores、6cores，進(jìn)行若干次實(shí)驗(yàn)，得到各評(píng)價(jià)指標(biāo)值如表8所示。

表8 不同預(yù)測(cè)模型在改變CPU資源下的預(yù)測(cè)精度

由表8可知，在固定輸入數(shù)據(jù)規(guī)模與內(nèi)存資源，改變CPU資源的條件下，本文提出的預(yù)測(cè)模型在所有測(cè)試應(yīng)用的各組數(shù)據(jù)集上均比SVM和LR獲得了較低的RMSE和MAPE，經(jīng)計(jì)算可得，與SVM和LR相比，本文提出的預(yù)測(cè)模型使得RMSE和MAPE最大降低47.2%和41.3%。

前面已經(jīng)進(jìn)行了本文提出的預(yù)測(cè)模型與常見(jiàn)預(yù)測(cè)模型的性能對(duì)比，接下來(lái)將驗(yàn)證本文提出的預(yù)測(cè)模型中的分類方法和PCA方法的性能效果，即在固定輸入數(shù)據(jù)規(guī)模與資源配置下，驗(yàn)證本文提出的預(yù)測(cè)模型與無(wú)分類前提下的預(yù)測(cè)模型PG（PCA-GBDT）、無(wú)PCA前提下的預(yù)測(cè)模型MSRG（Mean Shift-Random-GBDT）的性能對(duì)比，得到各評(píng)價(jià)指標(biāo)值如圖7、8所示。

圖7 PG、MSRG與本文方法的均方根誤差

圖8 PG、MSRG與本文方法的平均絕對(duì)百分誤差

由圖7、8可知，在相同輸入數(shù)據(jù)規(guī)模與資源配置下，與PG和MSRG相比，本文提出的預(yù)測(cè)模型均獲得了更低的RMSE和MAPE。與PG相比，本文提出的預(yù)測(cè)模型使得RMSE和MAPE最大降低39.6%和35.5%；與MSRG相比，本文提出的預(yù)測(cè)模型使得RMSE和MAPE最大降低42.5%和37.7%。

綜上所述，不管是KNN、SVM、LR模型，還是未分類前提下的PCA-GBDT模型、未PCA下的MSRG模型，本文提出的考慮了不同應(yīng)用特征的批處理應(yīng)用執(zhí)行時(shí)間預(yù)測(cè)模型的預(yù)測(cè)精度均高于上述預(yù)測(cè)模型。實(shí)際結(jié)果表明，與上述預(yù)測(cè)模型相比，本文提出的基于分類的Spark批處理應(yīng)用執(zhí)行時(shí)間預(yù)測(cè)模型可使得均方根誤差和平均絕對(duì)百分誤差平均降低32.1%和33.9%。

5 結(jié)論與展望

本文提出了一種考慮不同應(yīng)用特征的Spark批處理應(yīng)用執(zhí)行時(shí)間預(yù)測(cè)模型，并充分分析了影響應(yīng)用執(zhí)行時(shí)間的指標(biāo)，同時(shí)評(píng)估了批處理應(yīng)用執(zhí)行時(shí)間預(yù)測(cè)模型的實(shí)際效果。通過(guò)與KNN、SVM、LR模型、未分類前提下的PCA-GBDT模型、未PCA下的MSRG模型進(jìn)行性能對(duì)比可知，本文提出的面向Spark批處理應(yīng)用的執(zhí)行時(shí)間預(yù)測(cè)模型的預(yù)測(cè)精度更高。