基于MapReduce模型的并行計(jì)算平臺(tái)設(shè)計(jì)

摘 要：現(xiàn)如今人們的生活已經(jīng)進(jìn)入了互聯(lián)網(wǎng)時(shí)代，每天網(wǎng)絡(luò)上都會(huì)形成海量的數(shù)據(jù)。對(duì)于互聯(lián)網(wǎng)企業(yè)而言，需要對(duì)大量的數(shù)據(jù)進(jìn)行系統(tǒng)分類，以便能夠找尋對(duì)自身有價(jià)值的信息。MapReduce是一款能夠用于大型計(jì)算機(jī)集群并發(fā)處理大量網(wǎng)絡(luò)數(shù)據(jù)的模型，本文對(duì)該模型進(jìn)行了系統(tǒng)的分析與研究，提出了一種更為通用且可擴(kuò)展的平臺(tái)。

關(guān)鍵詞：并行計(jì)算；MapReduce模型；平臺(tái)設(shè)計(jì)

中圖分類號(hào)：TP338.6 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1007-9599 （2013） 09-0000-02

隨著社會(huì)的不斷發(fā)展與進(jìn)步，互聯(lián)網(wǎng)已經(jīng)進(jìn)入了web2.0時(shí)代，這就意味著更多的普通用戶能夠更為方便自由的使用互聯(lián)網(wǎng)。對(duì)于互聯(lián)網(wǎng)企業(yè)而言，web2.0在給企業(yè)帶來海量數(shù)據(jù)的同時(shí)，也給企業(yè)數(shù)據(jù)收集帶來了更多挑戰(zhàn)。如何在大量的數(shù)據(jù)中收集對(duì)自身有價(jià)值的信息，成為企業(yè)發(fā)展的重中之重。并行計(jì)算思想的提出使得計(jì)算機(jī)計(jì)算速度以及處理能力有著顯著的提高。也就是說，同一個(gè)數(shù)據(jù)的計(jì)算與處理可以在多個(gè)處理器中同時(shí)進(jìn)行，把問題分解來提高處理速度。并行計(jì)算可以在一個(gè)包含多個(gè)處理器的超級(jí)計(jì)算機(jī)中進(jìn)行，也可以在互聯(lián)的多個(gè)計(jì)算機(jī)集群中進(jìn)行。世界知名互聯(lián)網(wǎng)企業(yè)Google公司每天均需要處理超過20PB的海量數(shù)據(jù)，這些大量數(shù)據(jù)的處理就是在該公司的高可擴(kuò)展性分布式秉性基礎(chǔ)框架上進(jìn)行的。MapReduce是Google海量數(shù)據(jù)處理框架，在集群環(huán)境下，通過對(duì)數(shù)據(jù)的散布（map）和規(guī)約（reduce）來進(jìn)行高并發(fā)計(jì)算。下面將分別介紹一下本文平臺(tái)的關(guān)鍵設(shè)計(jì)策略。

1 通用平臺(tái)策略

1.1 客戶端任務(wù)上傳

配置客戶端任務(wù)使用的是XML文檔，與通常使用的函數(shù)調(diào)用方式有著一定的區(qū)別。這樣用戶自定義任務(wù)就可以有多種表達(dá)方式，既可以是以編譯可運(yùn)行的類，或者jar包，還可以是一個(gè)shell命令或者Bash腳本，甚至于可以直接編輯為一個(gè)工作目錄。之所以這樣設(shè)計(jì)，就是為了能夠進(jìn)一步的擴(kuò)大該框架的適用性。

1.2 監(jiān)控用戶自定義任務(wù)

用戶自定義任務(wù)表達(dá)的多樣性，使得框架更加通用，但同時(shí)帶來了一個(gè)問題就是對(duì)任務(wù)執(zhí)行過程很難以實(shí)現(xiàn)實(shí)時(shí)監(jiān)控。所以只能夠?qū)θ蝿?wù)完成后所反饋的狀態(tài)碼來判斷任務(wù)是否已經(jīng)正確完成。就像是反饋系統(tǒng)一樣，如果反饋信息顯示正確完成，則進(jìn)入下一步驟；反饋信息顯示錯(cuò)誤，則重新執(zhí)行該任務(wù)。

1.3 任務(wù)可串行執(zhí)行

Map和Reduce是兩種任務(wù)操作，對(duì)于Map任務(wù)而言，其輸入文件需要進(jìn)行一定的劃分，把不同輸出文件的同一個(gè)分區(qū)進(jìn)行排序合并，然后再傳送給Reduce進(jìn)行操作。而Reduce的輸出則當(dāng)作一個(gè)結(jié)果文件來處理。實(shí)際上所執(zhí)行的任務(wù)是更加復(fù)雜，該框架允許將多對(duì)Map/Reduce任務(wù)串行執(zhí)行，也就是按照 [m1→r1→m2→r2→…→mn→rn]序列來執(zhí)行。

2 中間結(jié)果文件的處理策略

在Map階段多出現(xiàn)的中間結(jié)果文件經(jīng)過散布分區(qū)處理后，就成為下一個(gè)階段任務(wù)的輸入函數(shù)。通常默認(rèn)分區(qū)函數(shù)使用Hash（key）%R方法處理，但有時(shí)也可指定另外一種形式的分區(qū)函數(shù)。按照Map操作方式來運(yùn)算中間結(jié)果文件時(shí)，會(huì)產(chǎn)生大量的重復(fù)鍵，如將這種中間結(jié)果文件直接傳送至Reduce操作，必定會(huì)出現(xiàn)一系列的問題，所以必須對(duì)這些含有重復(fù)鍵的中間結(jié)果文件進(jìn)行處理。這里可以通過用戶自定義的合并方式，來對(duì)中間結(jié)果文件進(jìn)行一定范圍內(nèi)的規(guī)約。

3 容錯(cuò)機(jī)制中的超時(shí)重發(fā)策略

本框架容錯(cuò)機(jī)制使用超時(shí)重發(fā)策略，也就是說，Master周期性的ping各個(gè)SN，同時(shí)檢測(cè)他們當(dāng)前所處的狀態(tài)。一定時(shí)間范圍內(nèi)，Master未能接收到響應(yīng)信號(hào)，則該SN就視為發(fā)生故障，如果在改SN上還有未處理完成的Map或者Reduce任務(wù)，則將被置于空閑，已進(jìn)行重發(fā)操作；即使SN上的Map任務(wù)已經(jīng)執(zhí)行完成，也將進(jìn)行重發(fā)操作。

本文設(shè)計(jì)并行計(jì)算平臺(tái)可分為三個(gè)邏輯層，平臺(tái)總體框架如下圖所示?？蛻舳伺c調(diào)度執(zhí)行區(qū)二者之間，任務(wù)調(diào)度與執(zhí)行區(qū)各個(gè)節(jié)點(diǎn)直接的通信，均是按照TCP協(xié)議消息來執(zhí)行的，以完成層與層之間，節(jié)點(diǎn)與節(jié)點(diǎn)之間任務(wù)請(qǐng)求、文件信息、負(fù)載與節(jié)點(diǎn)狀態(tài)的傳送。因?yàn)榫W(wǎng)絡(luò)帶寬都是有一定限制的，所以平臺(tái)在設(shè)計(jì)時(shí)，將任務(wù)單元輸送至數(shù)據(jù)文件所處節(jié)點(diǎn)來執(zhí)行，以進(jìn)一步的降低網(wǎng)絡(luò)帶寬占用率。

4 分布式負(fù)載均衡與任務(wù)調(diào)度策略

分析并研究分布式負(fù)載均衡與任務(wù)調(diào)度問題，主要是為了能夠把企業(yè)內(nèi)部的各種服務(wù)器有機(jī)的聯(lián)合在一起，不同類型服務(wù)器所能夠承擔(dān)或執(zhí)行的任務(wù)有著非常大的區(qū)別，只有通過該策略處理，才能夠把這些不同服務(wù)器整合在一起，呈現(xiàn)出一個(gè)整體的分布式計(jì)算機(jī)集群。

4.1 服務(wù)器對(duì)任務(wù)的智能調(diào)度

這里按照任務(wù)粒度來進(jìn)行服務(wù)節(jié)點(diǎn)的選擇，因?yàn)榧词谷蝿?wù)類型相同，也會(huì)因?yàn)檩斎胛募笮〉牟煌鹆６鹊淖兓?。?duì)任務(wù)粒度還有影響的另一個(gè)因素就是服務(wù)節(jié)點(diǎn)硬件資源，特別是系統(tǒng)CPU核數(shù)。一般情況下，如果系統(tǒng)具有多核處理器，那么線程池將會(huì)加大執(zhí)行并發(fā)線程。所以實(shí)際運(yùn)行過程中，Map/Reduce任務(wù)單元往往會(huì)多于服務(wù)節(jié)點(diǎn)個(gè)數(shù)。

4.2 網(wǎng)絡(luò)均衡

網(wǎng)絡(luò)帶寬的固定使得其成為網(wǎng)絡(luò)系統(tǒng)最為珍貴的一部分，但是個(gè)服務(wù)器節(jié)點(diǎn)之間的通信有需要使用以太網(wǎng)，所以系統(tǒng)在實(shí)際使用過程中，必須要進(jìn)行一定的優(yōu)化，以減少對(duì)網(wǎng)絡(luò)的占有率。數(shù)據(jù)文件的本地化就是一種很好的優(yōu)化措施。當(dāng)系統(tǒng)中某一服務(wù)節(jié)點(diǎn)出現(xiàn)錯(cuò)誤時(shí)，需要進(jìn)行節(jié)點(diǎn)重新執(zhí)行操作時(shí)，優(yōu)先選擇同一網(wǎng)關(guān)下的節(jié)點(diǎn)，以開放網(wǎng)關(guān)限制。

5 任務(wù)調(diào)度與執(zhí)行層設(shè)計(jì)

該部分是整個(gè)并行計(jì)算的核心，計(jì)算是否能夠正確完成主要看此部分的設(shè)計(jì)是否科學(xué)合理。任務(wù)調(diào)度與執(zhí)行層分為主控節(jié)點(diǎn)——分派節(jié)點(diǎn)——服務(wù)節(jié)點(diǎn)三層架構(gòu)，可以分別進(jìn)行任務(wù)分解、分配、調(diào)度、實(shí)時(shí)監(jiān)控、平衡分配以及任務(wù)執(zhí)行與合并等操作。結(jié)構(gòu)上分為以上三個(gè)部分，但實(shí)際上，這些執(zhí)行不同任務(wù)的節(jié)點(diǎn)均處于同一臺(tái)服務(wù)器中。每個(gè)節(jié)點(diǎn)之間按照TCP協(xié)議相互通信。所需執(zhí)行的任務(wù)發(fā)送給系統(tǒng)中的分派節(jié)點(diǎn)，形成分派節(jié)點(diǎn)與主控節(jié)點(diǎn)之間的通信空間，并實(shí)時(shí)的向主控節(jié)點(diǎn)反饋當(dāng)前狀態(tài)，這個(gè)反饋信息即使主控節(jié)點(diǎn)的輸入。上述執(zhí)行過程完成后，系統(tǒng)將會(huì)把輸入信息文件按規(guī)定劃分為若干個(gè)單元，并選取一個(gè)服務(wù)節(jié)點(diǎn)執(zhí)行這些任務(wù)單元。分派節(jié)點(diǎn)把執(zhí)行的路徑，執(zhí)行的命令以及輸入文件的詳細(xì)信息打包發(fā)送給服務(wù)節(jié)點(diǎn)后，服務(wù)節(jié)點(diǎn)就通過工作線程進(jìn)行下一步的計(jì)算。此時(shí)，分派節(jié)點(diǎn)的主要作用就是實(shí)時(shí)監(jiān)控服務(wù)節(jié)點(diǎn)任務(wù)執(zhí)行狀態(tài)，以保證任務(wù)執(zhí)行能夠順利進(jìn)行。在分派節(jié)點(diǎn)按照順序?qū)⑷蝿?wù)逐一運(yùn)算完成后，將自動(dòng)切斷與主控節(jié)點(diǎn)之間的通信通道，并向分布式文件管理器發(fā)送清除中間結(jié)果信號(hào)，同時(shí)把最終的結(jié)果文件發(fā)送至系統(tǒng)指定位置。

5.1 主控節(jié)點(diǎn)

主控節(jié)點(diǎn)是整個(gè)系統(tǒng)中最重要也是最中心的管理節(jié)點(diǎn)，該節(jié)點(diǎn)的主要作用就是任務(wù)的管理調(diào)度、對(duì)出現(xiàn)計(jì)算錯(cuò)誤的節(jié)點(diǎn)進(jìn)行處理以及均衡整個(gè)系統(tǒng)負(fù)載等主控任務(wù)。

（1）任務(wù)的管理調(diào)度

對(duì)系統(tǒng)中不同服務(wù)節(jié)點(diǎn)處的負(fù)載狀態(tài)進(jìn)行收集后，動(dòng)態(tài)的分派調(diào)度Map任務(wù)和Reduce任務(wù)，并將調(diào)度信息發(fā)送至工作中的服務(wù)節(jié)點(diǎn)。同時(shí)還要實(shí)時(shí)監(jiān)控不同任務(wù)當(dāng)前的執(zhí)行狀態(tài)，以便于向用戶進(jìn)行反饋。遇見需要忽略的損壞數(shù)據(jù)時(shí)，按照任務(wù)要求來執(zhí)行。

（2）處理發(fā)生錯(cuò)誤或者失效的節(jié)點(diǎn)和任務(wù)的異常狀態(tài)

Map節(jié)點(diǎn)失效：對(duì)各個(gè)節(jié)點(diǎn)的監(jiān)控遵循心跳協(xié)議，一旦發(fā)現(xiàn)異常狀態(tài)，則執(zhí)行重選節(jié)點(diǎn)操作，以成功執(zhí)行Map任務(wù)。當(dāng)系統(tǒng)計(jì)算能力還有一定剩余時(shí)，可以執(zhí)行備份任務(wù)。

Reduce節(jié)點(diǎn)失效：與Map節(jié)點(diǎn)失效時(shí)所實(shí)行的策略相同，通過分布式文件系統(tǒng)的復(fù)制存儲(chǔ)功能，來確保Map任務(wù)所輸出的中間文件是可靠的。

任務(wù)執(zhí)行發(fā)生異常：系統(tǒng)發(fā)生該情況時(shí)，可以即時(shí)執(zhí)行備份任務(wù)，以取代發(fā)生異常情況的任務(wù)。

（3）服務(wù)節(jié)點(diǎn)處負(fù)載均衡功能

對(duì)系統(tǒng)中每個(gè)節(jié)點(diǎn)所連接的網(wǎng)絡(luò)、CPU、占用內(nèi)存以及磁盤大小、任務(wù)粒度等負(fù)載信息進(jìn)行收集，以進(jìn)行系統(tǒng)任務(wù)調(diào)度操作，保證服務(wù)節(jié)點(diǎn)處的負(fù)載均衡。

5.2 分派節(jié)點(diǎn)

分派節(jié)點(diǎn)在系統(tǒng)中所承擔(dān)的主要任務(wù)就是生成輸入數(shù)據(jù)以及配置MapReduce任務(wù)，同時(shí)承擔(dān)著發(fā)送任務(wù)執(zhí)行請(qǐng)求信號(hào)至Master的任務(wù)。

（1）數(shù)據(jù)劃分：按照不同數(shù)據(jù)類型將不同輸入數(shù)據(jù)進(jìn)行合理劃分，同時(shí)控制任務(wù)粒度，以進(jìn)一步的優(yōu)化系統(tǒng)任務(wù)調(diào)度過程。

（2）調(diào)試代碼：幫助用戶更為方便的調(diào)試MapReduce程序，并反饋系統(tǒng)日志以及任務(wù)執(zhí)行狀態(tài)等信息。

5.3 服務(wù)節(jié)點(diǎn)

系統(tǒng)中的服務(wù)節(jié)點(diǎn)是實(shí)際執(zhí)行任務(wù)的部分。所有需要執(zhí)行的任務(wù)按照順序被切分為相同大小的任務(wù)單元，初始輸入數(shù)據(jù)同樣被切分為相同大小塊，每一個(gè)服務(wù)節(jié)點(diǎn)中，被切分的任務(wù)單元就運(yùn)行于相同大小的數(shù)據(jù)塊之上。假設(shè)當(dāng)前運(yùn)行的任務(wù)單元不是整個(gè)任務(wù)單元的尾部，則所輸出的文件將直接當(dāng)作下一任務(wù)單元的輸入數(shù)據(jù)。服務(wù)節(jié)點(diǎn)的另一個(gè)作用就是定期收集系統(tǒng)的負(fù)載信息，以便于按時(shí)發(fā)送給Master。具體過程是：

（1）對(duì)系統(tǒng)Map任務(wù)實(shí)施調(diào)度來處理輸入和輸出數(shù)據(jù)

輸入數(shù)據(jù)的讀?。涸诒緳C(jī)中或者分布式文件系統(tǒng)中讀取需要處理的Map輸入數(shù)據(jù)。

系統(tǒng)Map任務(wù)調(diào)度：通過對(duì)Map任務(wù)的調(diào)度，來實(shí)時(shí)監(jiān)控任務(wù)當(dāng)前的執(zhí)行狀態(tài)，并實(shí)時(shí)將狀態(tài)信息發(fā)送至Master。

輸出數(shù)據(jù)的切分：將Map所輸出的數(shù)據(jù)按照分區(qū)函數(shù)的規(guī)定來進(jìn)行切分，每個(gè)切分?jǐn)?shù)據(jù)集合輸入至Reduce。

（2）調(diào)度本機(jī)Reduce任務(wù)來處理輸入和輸出數(shù)據(jù)

預(yù)排列過程：Map分區(qū)數(shù)據(jù)經(jīng)過合并后輸入至Reduce之前，可以對(duì)數(shù)據(jù)順序進(jìn)行排列，包括外部和內(nèi)部?jī)煞N排列。

調(diào)度執(zhí)行Reduce任務(wù)：系統(tǒng)調(diào)度Reduce任務(wù)，來實(shí)時(shí)監(jiān)控當(dāng)前任務(wù)執(zhí)行的狀態(tài)，并實(shí)時(shí)將狀態(tài)信息發(fā)送至Master。

（3）調(diào)度Combine任務(wù)

Map/Reduce任務(wù)間可以另外輸入一個(gè)合并流程，并通過Map任務(wù)機(jī)在處理輸出數(shù)據(jù)，例如將相同的key進(jìn)行合并，以此來降低對(duì)網(wǎng)絡(luò)帶寬的占有率。

以上對(duì)本文并行計(jì)算平臺(tái)進(jìn)行了較為詳細(xì)的描述，該平臺(tái)現(xiàn)已經(jīng)在實(shí)驗(yàn)中驗(yàn)證了其實(shí)際性能。在今后的工作中，將繼續(xù)對(duì)該平臺(tái)的各項(xiàng)性能進(jìn)行更為細(xì)致的研究，以進(jìn)一步的完善平臺(tái)的通用性以及高速海量數(shù)據(jù)處理能力。

參考文獻(xiàn)：

[1]遲學(xué)斌.高性能并行計(jì)算.http：//lssc.cc.ac.cn/.

[2]Jeffery Dean，Sanjay Ghemawat.MapReduee：Simplified Data Processing on Large Clusters. OSDI04： Sixth Symposium on Operating System Design and Implemeniation，San Francisco，CA，2004.

[3]Luiz A.Barroso， Jeffrey Dean， and Urs Holzle. Web search for a Planet：The Google cluster architecture. IEEE Micro，2003，3：22-28.

[作者簡(jiǎn)介]邵偉（1969-），女，漢族，副教授，碩士，研究方向：計(jì)算機(jī)應(yīng)用技術(shù)。