摘 要： 針對傳統MapReduce框架中任務節點和工作節點的失效問題，提出了在配置備份節點的分層主從式MapReduce框架中加入單元集群的處理方法。在改進框架中，任務處理的最小單位是單元集群，當單元集群中的某個工作節點失效或者超過時間闕值時，子任務節點則選擇該單元集群中的空閑工作節點來分配任務，并且不需要重新傳輸任務文件分塊，這既節省了工作節點重選擇的時間，又降低了網絡傳輸的壓力。使用該框架針對不同數量的數據塊進行實驗，工作節點的災難恢復時間均可以節省25 ms左右，證明了單元集群的處理方法可以有效解決工作節點的失效問題。
關鍵詞： Hadoop架構；MapReduce框架；任務節點；工作節點；備份節點；節點失效；單元集群
隨著互聯網的迅猛發展，基于互聯網的數據蘊含著豐富的信息，云計算[1]就是在這樣一種對大規模計算能力的強烈需求環境下發展起來的。Hadoop[2]云計算平臺是Apache的一個分布式計算開源框架，其核心是MapReduce[3]和Hadoop Distribute File System[4]。
1 MapReduce框架簡介
MapReduce是一種處理海量數據的并行編程框架，其主要思想是將要執行的問題進行分割，數據被分割后通過Map函數的程序將數據映射到不同區塊，分配給PC集群來處理，再通過Reduce函數的程序將結果匯總，輸出要得到的結果。
1.1 算法流程
用戶程序調用MapReduce函數時會引起如下操作：
(1)利用MapReduce函數庫把輸入文件分成M塊，每塊大概16 MB～64 MB，并在集群中的Worker節點上執行程序的備份；
(2)Master節點找出空閑的Worker節點并為它們分配子任務；
(3)被分配到Map任務的Worker節點讀取已經分割好的文件塊，計算生成中間結果，中間結果暫時緩沖到內存；
(4)中間結果周期性地寫入本地，中間文件通過分區函數分成R個分區，并將它們在本地磁盤的位置信息發送給Master節點；
(5)被分配到Reduce任務的Worker節點根據Master提供的中間文件位置信息遠程讀取相應Worker節點的中間文件；
(6)執行Reduce，計算并輸出結果。
1.2 Hadoop中的MapReduce
Hadoop中對MapReduce的處理是在原算法中加入了兩個處理：Split(分割)和Shuffle(混合)，框架如圖1所示。
圖1中，Split過程可以看作是Input的再次分割，用以控制分塊的大小，Shuffle過程可以看作是在執行Map任務的Worker節點上執行本地的Reduce過程。
2 MapReduce框架的相關改進
2.1 MapReduce Online
MapReduce Online框架[5]將Map任務產生的中間數據在執行映射任務的Worker節點和執行規約任務的Worker節點間通過管道進行傳輸，使得下游數據元素可以在上游數據元素完成執行前開始消耗數據，增加了并行機會，提高了利用率，減少了響應時間。
2.2 Map-Balance-Reduce
Map-Balance-Reduce模型[6]針對MapReduce模型中存在的多個Reduce任務之間完成時間差別較大的問題而提出。通過添加Balance任務對Map任務處理完成的中間數據進行均衡操作，使分配到Reduce任務節點的數據比較均衡，從而確保Reduce任務的完成時間基本一致。
2.3 Shuffle階段的優化與重構
該方案在執行Map任務的Worker節點上壓縮產生的中間文件、重構遠程數據拷貝傳輸協議（從Http協議到UDT協議）以及Reduce端內存分配優化3個方面[7]來優化和重構Shuffle階段，從而達到提高MapReduce的計算性能。
3 傳統MapReduce框架中節點失效的問題
MapReduce框架不同于其他傳統系統框架設計的一點在于其將框架中的每個節點都當作一種不穩定的資源來對待，每個節點的失效都當作是一種系統常態并且有著相應的處理方式。
3.1 Master節點的失效問題
MapReduce框架中，唯一的Master節點管理數據分塊、Worker節點分配、記錄節點狀態以及選擇空閑節點等眾多事務，一旦Master節點失效，“重新執行”的操作對之前的工作是一種極大的浪費并且大大延長了任務執行時間，這對需要進行海量數據計算的系統是不能接受的。參考文獻[8]提出了“配置備份節點的分層主從式MapReduce框架”的解決方案，該方案可以在一定程度上緩解Master節點的任務壓力并且提高了Master節點的安全性，具體框架如圖2所示。
在這個MapReduce框架中，各個節點的工作職責是：
(1)主任務節點：主要對集群進行管理以及第一次任務的委派，在任務委派完之后不需要擔心任務的完成情況，只需要專心地完成與子任務節點的聯系，并對元數據進行管理，同時應對節點失效的問題。
(2)子任務節點：主要與用戶程序進行通信，完成用戶程序發出的任務并將結果返回給用戶程序；它們直接受主任務節點的管理，也直接管理工作節點，起到承上啟下的作用。
(3)工作節點：直接受子任務節點的管理，完成分配的任務。
3.2 Worker節點的失效問題
對于Worker節點的狀態判定，MapReduce框架是讓Master節點周期性地ping每個Worker節點，當無法得到Worker節點的應答時，Master節點就認為這個節點是失效的。可以將失效的Worker節點上的任務以及所處狀態處理措施分為4類，如表 1 所示。
針對Worker節點的失效問題，采用引入單元集群的處理方法，該方案可以方便Master節點對Worker節點的管理并降低Worker節點失效的影響。
4 改進型MapReduce框架設計
4.1 單元集群
在傳統MapReduce框架中，龐大的機器集群是進行Map任務和Reduce任務的計算資源，集群中除了Master節點之外的每個機器都可以是Worker節點。通常情況下，這個集群的數量是以萬為計數單位的。為了讓Master節點更好地管理這樣一個龐大的機器集群，引入了“單元集群”的概念。
4.1.1 基本概念
單元集群就是擁有X個Worker節點的一個小機器集群，整個機器集群由多個單元集群組成，單元集群從Master節點處接受X個任務，該單元集群中Worker節點也都獲取這X個任務所對應的文件分塊并將其存儲在自己的本地磁盤中，每個Worker節點執行這X個任務中其中一個，如節點1執行任務1，節點2執行任務2，…，節點X執行任務X。
Master節點對其管理的單元集群設置一個“任務執行時間闕值T”，單元集群中的Worker節點的3個狀態以及處理措施如下：
(1)正常狀態：正常執行完X個任務，然后開始向Mas-
ter節點請求新的任務或者接受其他單元集群的任務；
(2)超過時間闕值狀態：當單元集群中的Worker節點i執行當前任務i的時間超過了T，則啟動該單元集群中的空閑節點k執行任務i，因為該單元集群中的每個節點初始化時已經獲取了任務i對應的文件分塊，所以節點k可立即開始執行任務i。當節點k也超過時間闕值T時，處理方法一樣，直到該任務在任一節點上執行完成；
(2)失效狀態：當單元集群中的Worker節點j失效時，Master節點優先在該單元集群中尋找空閑節點（或已經執行完本身任務的節點）來執行這個失效節點j上的任務j，同樣也不需要進行文件分塊的重新獲取，如果失效節點j所在的單元集群中沒有空閑節點或已執行完任務的節點，Master節點就去尋找空閑的單元集群的Worker節點來執行該任務。
4.1.2 主要改進
單元集群的引入能夠很好地解決Worker節點失效和工作效率不高的問題，單元集群所帶來的優化如下：
(1)單元集群中的Worker節點失效或者執行時間超過闕值時，Master的處理方案是先從失效節點所在的單元集群中尋找合適的節點，節省了在整個機器集群中尋找合適節點的時間；
(2)單元集群中的節點在初始化時都獲取了X個任務文件分塊，正常工作的節點可以立即執行失效節點的任務而不需要重新獲取文件分塊，這降低了網絡傳輸的壓力，Worker節點失效或者執行時間超過闕值不會對系統效率有太大影響；
(3)Master節點的執行單位從單個節點變成單元集群，其只需要考慮單元集群的失效率和工作效率。只要單元集群中還有正常工作的Worker節點，Master節點就認為該單元集群仍然處于正常工作狀態。
4.1.3 單元集群的X的取值
首先，X不宜偏大，單元集群中的每個節點都需要存儲這個單元集群所要執行任務對應的文件分塊，節點過多會在初始化時網絡傳輸過多的文件分塊給每個節點，將增加每個節點的網絡傳輸壓力并且延長初始化時間從而降低系統執行效率。單元集群在未執行完成分配的所有任務之前是不接受其他單元集群任務的，X偏大就有可能導致單元集群的節點不能得到充分利用；其次，X不宜偏小，單元集群節點偏少時，若單元集群中出現節點失效或者運行效率低下的情況，且該單元集群中其他的節點也在執行自己的任務，而這個任務又不能及時交給其他單元集群去執行，則失效節點所負責的任務執行就會成為系統效率的瓶頸，從而導致整個系統的效率偏低，而且單元集群節點偏少也在一定程度上增大了單元集群的失效率。
4.2 改進框架設計
改進型MapReduce框架結合了“配置備份節點的分層主從式MapReduce框架”和“單元集群”，能夠同時解決Master節點和Worker節點失效問題，如圖3所示。
通過引入兩層Master節點來解決Master節點任務壓力過大的問題，通過對Worker節點采取單元集群的處理來解決其失效和效率不高的問題，以下通過實驗驗證這樣的改進框架設計是合理且有效的。
5 實驗結果分析
實驗所使用的測試系統是目前運用MapReduce最廣泛的搜索領域，但實驗中使用的測試數據相對于當前搜索網站所涉及的數據要簡單。
5.1 實驗環境
集群中主任務節點、子任務節點以及工作節點都使用相同的軟硬件，Hadoop為0.22.1版本，任務文件塊的數量設置為500、1 000、1 500，并且文件塊的大小設置為64 MB。
針對傳統框架，使用4臺PC來模擬Master節點、Worker節點以及客戶端，其中Master節點和客戶端安裝在一臺計算機上，另外3臺PC作為Worker節點使用。
針對改進框架，使用15臺PC來模擬主任務節點、子任務節點、工作節點、備份節點以及客戶端，取單元集群的X=5，主任務節點和客戶端安裝在一臺PC上，2個子任務節點安裝在2臺PC上，2個備份節點分別安裝在2臺PC上，另外10臺PC分別作為2個單元集群中的Worker節點。
5.2 實驗數據及結果分析
首先，在客戶端隨機生成50 000個整數(0～49 999)，在傳統框架下，將這些整數文件分成多個文件塊，并均分存儲到3個Worker節點上;若在改進框架下，將這些整數文件分成多個文件塊，并均分這些文件塊到2個單元集群上；然后，客戶端將一個MapReduce任務（搜索最大值）交給機器集群來進行實驗。
在傳統框架和改進框架下的運行結果如表2所示。
Worker節點的災難恢復時間是實驗重點關注的參數指標。節點的災難恢復時間包括：重新選擇節點、IP地址的遷移、網絡傳輸時間以及數據塊的遷移時間，在單元集群改進框架中，Worker節點的災難恢復時間只包括重新選擇節點和IP地址的遷移這兩部分時間。從表2可以看出改進框架相比較傳統框架，其Worker節點的災難恢復時間降低了25 ms左右。
通過測試數據可以得出：單元集群的改進框架與傳統框架相比，降低了Worker節點的災難恢復時間，從而在一定程度上解決了Worker節點的失效問題。
針對傳統MapReduce框架中存在的Master節點和Worker節點失效的問題，采用了在“配置備份節點的分層主從式MapReduce框架”中加入單元集群的方案，單元集群包括多個Worker節點，這些Worker節點上都備份了所在單元集群所要處理的所有任務文件分塊，當Worker節點失效或超過時間闕值時，Master節點會選擇其所在單元集群中的空閑節點來執行失效節點的任務，這不僅將單一Worker節點的失效問題轉移到單元集群上，而且也解決了當出現節點失效時還需要重新傳輸任務文件分塊的問題。單元集群的提出雖然在一定程度上解決了Master節點和Worker節點的失效問題，但是因為需要在初始化整個系統時多傳輸一部分任務文件分塊，這樣就犧牲了一部分的系統性能，并且在單元集群的X取值上并沒有一個特定的方案，只能通過大量的實驗測試才能得到合適的取值，這也是未來研究的一個方向。
參考文獻
[1] 陳康，鄭緯民.云計算：系統實例與研究現狀[J].軟件學報，2009，20(5)：1337-1348.
[2] WHITE T.Hadoop：the definitive guide[M].California：O′Reilly Media，2012.
[3] DEAN J，GHEMAWAT S.MapReduce: simplified data processing on large clusters[J].Communications of the ACM，2008，51(1)：107-113.
[4] BORTHAKUR D.HDFS architecture guide[DB/OL].Hadoop apache project.(2008-02-14).[2013-04-22].http://hadoop.apache.org/common/docs/current/hdfsdesign.pdf.
[5] CONDIE T，CONWAY N，ALVARO P，et al.MapReduce online[C].Proceedings of the 7th USENIX Conference on Networked Systems Design and Implementation，2010：21-21.
[6] 李玉林，董晶.基于Hadoop的MapReduce模型的研究與改進[J].計算機工程與設計，2012，33(8)：3110-3116.
[7] 彭輔權，金蒼宏，吳明暉，等.MapReduce中shuffle優化與重構[J].中國科技論文，2012，7(4)：241-245.
[8] 周一可.云計算下MapReduce編程模型可用性的研究與優化[D].上海：上海交通大學，2011.