冒佳明　王鵬飛　趙然

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

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

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

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

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

1 問題分析

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

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

圖1 MapReduce基本工作原理

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

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

圖2 Reduce執(zhí)行過程

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

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

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

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

3 結(jié)語

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

[參考文獻(xiàn)]

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

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

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