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

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

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

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

1 通用平臺策略

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

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

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

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

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

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

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

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

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

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

本文設(shè)計并行計算平臺可分為三個邏輯層，平臺總體框架如下圖所示。客戶端與調(diào)度執(zhí)行區(qū)二者之間，任務(wù)調(diào)度與執(zhí)行區(qū)各個節(jié)點直接的通信，均是按照TCP協(xié)議消息來執(zhí)行的，以完成層與層之間，節(jié)點與節(jié)點之間任務(wù)請求、文件信息、負(fù)載與節(jié)點狀態(tài)的傳送。因為網(wǎng)絡(luò)帶寬都是有一定限制的，所以平臺在設(shè)計時，將任務(wù)單元輸送至數(shù)據(jù)文件所處節(jié)點來執(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)出一個整體的分布式計算機(jī)集群。

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

這里按照任務(wù)粒度來進(jìn)行服務(wù)節(jié)點的選擇，因為即使任務(wù)類型相同，也會因為輸入文件大小的不同而引起粒度的變化。對任務(wù)粒度還有影響的另一個因素就是服務(wù)節(jié)點硬件資源，特別是系統(tǒng)CPU核數(shù)。一般情況下，如果系統(tǒng)具有多核處理器，那么線程池將會加大執(zhí)行并發(fā)線程。所以實際運(yùn)行過程中，Map/Reduce任務(wù)單元往往會多于服務(wù)節(jié)點個數(shù)。

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

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

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

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

5.1 主控節(jié)點

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

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

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

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

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

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

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

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

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

5.2 分派節(jié)點

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

（1）數(shù)據(jù)劃分：按照不同數(shù)據(jù)類型將不同輸入數(shù)據(jù)進(jìn)行合理劃分，同時控制任務(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é)點

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

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

輸入數(shù)據(jù)的讀取：在本機(jī)中或者分布式文件系統(tǒng)中讀取需要處理的Map輸入數(shù)據(jù)。

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

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

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

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

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

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

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

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

參考文獻(xiàn)：

[1]遲學(xué)斌.高性能并行計算.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.

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