MapReduce架構(gòu)下Reduce任務(wù)的調(diào)度優(yōu)化

冒佳明　王鵬飛　趙然

摘 要：MapReduce作業(yè)執(zhí)行過程包含Map和Reduce兩個階段，Reduce階段需要復(fù)制Map階段產(chǎn)生的中間數(shù)據(jù)到本地進行計算產(chǎn)生最終的輸出數(shù)據(jù)。其中，Reduce階段包括Sort，Shuffle和Reduce等3個子階段，Shuffle子階段通過網(wǎng)絡(luò)鏈路傳輸數(shù)據(jù)，花費的時間占Reduce階段的1/3以上，具有較大的優(yōu)化空間。文章提出了一種基于Reduce階段執(zhí)行鏈路分析的優(yōu)化節(jié)點選擇算法，通過合理選擇優(yōu)化節(jié)點，并部署相對應(yīng)的Reduce任務(wù)，降低節(jié)點間的數(shù)據(jù)傳輸開銷，減少對網(wǎng)絡(luò)帶寬資源的占用，加速Reduce任務(wù)的執(zhí)行，從而實現(xiàn)總體MapReduce作業(yè)的執(zhí)行優(yōu)化。

關(guān)鍵詞：MapReduce；網(wǎng)絡(luò)帶寬；Shuffle；優(yōu)化

Hadoop系統(tǒng)是MapReduce架構(gòu)的開源實現(xiàn)，由于其對海量數(shù)據(jù)進行分布式處理的能力，得到了各行業(yè)應(yīng)用領(lǐng)域的廣泛使用[1]。MapReduce架構(gòu)下的作業(yè)執(zhí)行主要包括兩個階段：規(guī)約的Map階段和映射的Reduce階段。其中，Reduce階段以Map階段的輸出作為自己的輸入。因此，需要將Map階段的結(jié)果傳輸?shù)絉educe任務(wù)的執(zhí)行節(jié)點，這一過程需要耗費一定的網(wǎng)絡(luò)帶寬資源。在數(shù)據(jù)中心環(huán)境下，網(wǎng)絡(luò)資源屬于較稀缺的資源，往往成為系統(tǒng)應(yīng)用的瓶頸。在Hadoop系統(tǒng)中，通過使用數(shù)據(jù)壓縮技術(shù)，將Map的輸出結(jié)果進行壓縮，再在Reduce節(jié)點進行解壓縮。然而，解壓過程也會引起一定的計算、時間開銷。

鑒于Hadoop平臺下作業(yè)調(diào)度算法在Reduce任務(wù)調(diào)度方面的不足，本文提出了一種新的任務(wù)調(diào)度算法，其基本思想在于選擇系統(tǒng)中的最優(yōu)節(jié)點，將特定的Reduce任務(wù)調(diào)度到最優(yōu)節(jié)點上，從而減少任務(wù)的中間數(shù)據(jù)傳輸時間，省去對數(shù)據(jù)中心帶寬資源的占用。其中最優(yōu)節(jié)點是指集群中通過網(wǎng)絡(luò)鏈路傳輸Map階段中間數(shù)據(jù)時經(jīng)過的跳數(shù)最少的節(jié)點。

Reduce任務(wù)調(diào)度算法不影響原有調(diào)度算法在作業(yè)調(diào)度層面的策略和優(yōu)勢[2-3]，但可以起到節(jié)約帶寬的作用。因此，可以適用于網(wǎng)絡(luò)資源較為緊缺的應(yīng)用場景中，該算法也一定程度上可以降低整個作業(yè)的執(zhí)行時間。

1 問題分析

MapReduce編程模型由Map和Reduce兩個階段構(gòu)成，Map階段讀取輸入數(shù)據(jù)并產(chǎn)生中間結(jié)果，Reduce階段則對中間結(jié)果進行分析，從而得出最終作業(yè)分析結(jié)果。

MapReduce的基本執(zhí)行流程如圖1所示。其中，Map函數(shù)讀取一個初始數(shù)據(jù)，然后計算產(chǎn)生中間數(shù)據(jù)的鍵/值對的集合，由MapReduce系統(tǒng)將具有相同Key的中間Values合并在一起，并且將這些中間數(shù)據(jù)定期存儲在本地磁盤上，然后將這些數(shù)據(jù)傳送給Reduce函數(shù)。Reduce函數(shù)讀取Map輸出的中間數(shù)據(jù)，在本地節(jié)點計算產(chǎn)生最終的結(jié)果，并將結(jié)果寫入全局的Hadoop分布式文件系統(tǒng)（Hadoop Distributed File System ，HDFS）中。

圖1 MapReduce基本工作原理

對于Reduce階段，其過程包括3個子階段，分別是：Shuffle子階段、Sort子階段、Reduce子階段，具體執(zhí)行過程如圖2所示。其中，Shuffle子階段從每一個運行Map任務(wù)的節(jié)點上將屬于自己處理的數(shù)據(jù)分片并通過網(wǎng)絡(luò)傳輸?shù)竭\行Reduce任務(wù)的節(jié)點內(nèi)存中，當(dāng)內(nèi)存緩沖滿時再溢寫到本地磁盤中去；Sort子階段在Shuffle復(fù)制完所有Map輸出期間，循環(huán)對Map的輸出數(shù)據(jù)進行歸并排序，以保證數(shù)據(jù)整體的有序性。Reduce子階段對已排序輸出的數(shù)據(jù)中的每個鍵迭代地調(diào)用Reduce函數(shù)，執(zhí)行用戶編寫的Reduce函數(shù)代碼，產(chǎn)生最后的輸出數(shù)據(jù)，并寫入最終的HDFS中。

通過進一步地分析，在Reduce的執(zhí)行過程中，Shuffle子階段一般占用長的時間，這主要是因為這一階段需要通過網(wǎng)絡(luò)傳輸數(shù)據(jù)，而且網(wǎng)絡(luò)鏈路的情況不穩(wěn)定，且網(wǎng)絡(luò)帶寬已經(jīng)成為網(wǎng)絡(luò)中的瓶頸資源，對數(shù)據(jù)的傳輸時間有很大的影響；Reduce子階段需要的時間次之，因為這一階段需要將最終結(jié)果寫入HDFS中，且每個數(shù)據(jù)塊需要存儲一定數(shù)量的副本，需要花費較長的時間；Sort子階段需要的時間最短，因此，這3個子階段所占Reduce階段的時間比例并不是Hadoop平臺默認情況下的各占1/3。因此，基于各子階段的實際時間占比，可以進一步優(yōu)化Reduce執(zhí)行過程的時間開銷。

圖2 Reduce執(zhí)行過程

2 優(yōu)化節(jié)點選擇算法思想

由于磁盤和非易失存儲器（Non-Volatile Memory，NVM）的存儲介質(zhì)不同，數(shù)據(jù)存儲在不同介質(zhì)上的性能差異較大，所以針對此問題我們設(shè)計了相應(yīng)的數(shù)據(jù)部署方案。假設(shè)所有的數(shù)據(jù)原本均存儲在磁盤中，設(shè)定初始數(shù)據(jù)塊的標簽表示Label=N，并且以讀寫、冷熱和生存周期標簽為遷移標準。

優(yōu)化節(jié)點選擇算法對每一個有空閑Reduce Slot的節(jié)點計算相應(yīng)的鏈路長度和Shuffle階段執(zhí)行時間，獲得所有Map中間數(shù)據(jù)經(jīng)過的傳輸鏈路的長度和，通過比較在不同節(jié)點調(diào)度Reduce任務(wù)時的鏈路情況，選擇具有最小值執(zhí)行時間的節(jié)點（即最優(yōu)節(jié)點），調(diào)度Reduce任務(wù)到該選中節(jié)點上執(zhí)行，減少了Shuffle子階段獲得中間數(shù)據(jù)時對帶寬資源的消耗和傳輸?shù)臅r間開銷，進而減少了單個作業(yè)的執(zhí)行時間。這主要是因為數(shù)據(jù)傳輸時經(jīng)過的鏈路的數(shù)目和數(shù)據(jù)經(jīng)過的路由器的數(shù)目通常情況下是線性的關(guān)系：在各段鏈路網(wǎng)絡(luò)傳輸速率相同的情況下，經(jīng)過的鏈路長度越短，數(shù)據(jù)在物理鏈路上傳播時消耗的時間也會減少，在這一階段花費的時間就越短；并且經(jīng)過的鏈路段數(shù)少時，經(jīng)過的路由器數(shù)目就少，消耗的帶寬也會減少；從而單個作業(yè)的執(zhí)行時間也會減少。

優(yōu)化節(jié)點選擇算法屬于調(diào)度模型的第3個層次，可將其嵌入已有的FIFO，Capacity Scheduler和Fair Scheduler等任務(wù)調(diào)度算法中。若將其嵌入FIFO中，F(xiàn)IFO只有一個作業(yè)隊列，不需要第一級選擇隊列的調(diào)度，第二級選擇作業(yè)的調(diào)度利用FIFO原有的先來先服務(wù)的調(diào)度策略，這樣可以保持FIFO簡單易實現(xiàn)等的優(yōu)勢，并且在第三級調(diào)度時，Map任務(wù)的調(diào)度策略也沿用原來的，在調(diào)度Reduce任務(wù)時應(yīng)用本文中的調(diào)度算法選擇最優(yōu)的節(jié)點將作業(yè)的Reduce任務(wù)分配給該節(jié)點。若將其嵌入Capacity Scheduler中，類似的，其第一、第二級調(diào)度策略依舊沿用計算能力調(diào)度算法原來的機制，這樣可以保留計算能力調(diào)度算法在作業(yè)并發(fā)執(zhí)行方面的優(yōu)勢，然后在第三級調(diào)度時Map任務(wù)調(diào)度機制不變，Reduce任務(wù)調(diào)度算法使用本文中的調(diào)度算法，以求盡量減少Shuffle階段需要的時間。若將其嵌入Fair Scheduler中時，第一級和第二級的調(diào)度策略沿用公平調(diào)度算法，可以保留公平調(diào)度算法在公平性方面的優(yōu)勢，同時在第三級調(diào)度時Map任務(wù)的調(diào)度策略也不做改變，即盡力滿足數(shù)據(jù)本地性，而在調(diào)度選中的作業(yè)池中的特定的作業(yè)的Reduce任務(wù)時，將本文的算法嵌入進去，可以最大程度減少Shuffle階段的鏈路傳輸時間。

3 結(jié)語

文章提出了一種針對MapReduce架構(gòu)的Reduce任務(wù)優(yōu)化調(diào)度方法。其核心在于分析Reduce各子階段的真實時間占比，并采用優(yōu)化節(jié)點選擇算法來優(yōu)化Reduce子階段的執(zhí)行，降低對集群帶寬的使用，減少數(shù)據(jù)傳輸量，縮短Reduce任務(wù)的執(zhí)行時間。

[參考文獻]

[1]王少亞.Haboop在企業(yè)中的應(yīng)用現(xiàn)狀分析[J].商場現(xiàn)代化，2013（18）：84.

[2]賴海明.MapReduce作業(yè)調(diào)度算法分析與優(yōu)化研究[D].杭州：杭州電子科技大學(xué)，2012.

[3]曹丙瑞.Hadoop平臺作業(yè)調(diào)度算法研究與改進[D].石家莊：河北經(jīng)貿(mào)大學(xué)，2015.