董的部落格：《疊代式mapreduce架構介紹》網址:http://dongxicheng.org/mapreduce/iterative-mapreduce-intro/
小e的分享：《疊代式MapReduce解決方案》：http://www.wikieno.com/2012/02/iterative-mapred-summary-haloop/
1.概述
對于傳統的MapReduce架構，每個map task讀取一個block，結果會寫回到本地磁盤。每個reduce task會從map task所在節點讀取資料，最終結果寫到HDFS。這個過程雖然會降低性能，但提高了可靠性。
傳統MapReduce不支援顯示疊代，是以又許多改進型MapReduce，用于支援疊代開發。如Twister, Haloop. 更多疊代式作業以及在Hadoop上的實作方法，請參見Apache開源項目Mahout 以及它的論壇。
2.疊代式作業
在資料挖掘，資訊檢索等領域，有很多算法需要多次疊代，本節介紹兩個常見的作業，一個是PageRank，另一個是SSSP（Single Source Shortest Path）。PageRank是一個非常有名的網頁重要性衡量因素，它是一個多次疊代的過程，如下圖所示，每次疊代，PageRank由兩個作業MR1和MR2完成，這樣疊代多次，直到相鄰的兩次疊代中PR之差小于某一個門檻值。
單源最短路徑問題實際上也是多次疊代的過程，主要思想是：設G=(V,E)是一個帶權有向圖，R是G的鄰接矩陣。整個算法始終把圖中頂點集合V分成兩組，第一組為已求出最短路徑的頂點集合（用S表示，初始時S中隻有一個源點，在每次疊代中求得一條最短路徑 , 并将該路徑的另一頂點加入到集合S中，直到全部頂點都加入到S中，算法就結束了），第二組為其餘未确定最短路徑的頂點集合（用U表示）。在每次疊代中，從U中選擇一個目前路徑最短的頂點，轉存到S中，直到U為空。
3、 技術難點
從PageRank和SSSP的整個計算過程可以看出：
（1） 輸入資料都動态資料和靜态資料兩部分組成。對于PageRank， L屬于靜态資料，而R屬于動态資料；對于SSSP，R屬于靜态資料，S和U屬于動态資料。傳輸動态資料是不可避免的，而靜态資料可以采用某種政策避免重複傳輸。怎樣避免傳輸靜态資料？
（2） 每次疊代，如果所有task重複重新建立，代價将非常高。怎樣重用task以提高效率（task pool）？
（3） 每次疊代，資料怎麼樣存儲？如果總是寫磁盤，代價将非常高。
（4） 何時疊代終止，怎樣改變程式設計模型，允許使用者指定合适終止疊代.
4.疊代式MapReduce架構
Haloop是在Hadoop基礎上擴充而來的，其架構如下：
Haloop進行的改進有：
（1） 提供了一套新的程式設計接口，以友善使用者進行疊代式程式開發。
（2） master node（jobtracker）包含一個循環控制子產品，它不斷的啟動map-reduce計算知道滿足疊代終止條件。
（3） 設計了新的Task scheduler，以便更好的利用data locality特性。
（4） 資料在各個task tracker會被緩存（cache）和建索引（index）。
下面介紹技術創新點：
（1） Hadoop 将所有疊代式任務抽象為：
，其中R0是初始輸入，L是每次疊代不變的資料，Ri是第i次疊代産生的結果。主要程式設計接口是：
SetFixedPointThreshold：設定兩次疊代的終止條件，即距離差是否達到某一個門檻值
setMaxNumOfIterations：設定疊代次數
setIterationInput：設定變化的輸入資料
AddInvariantTable：設定不變的輸入資料
（2） Loop-aware 任務排程。Haloop在第一次疊代時會将不變的輸入資料儲存到該計算節點上，以後每次排程task，盡量放在固定的那些節點上（locality）。這樣，每次疊代，不變的資料就不必重複傳輸了。
（3） Cache和Index。Map task的輸入與輸出，Reduce task的輸出都會被建索引和緩存，以加快資料處理速度。其中，緩存是指資料被寫到本次磁盤，以供下一輪循環疊代時直接使用。
總體上說，Haloop比Twister抽象度更高，支援更多的計算，同時，由于是在Hadoop基礎上修改上，因而繼承了Hadoop的很多優點。
5、 總結
目前在疊代式MapReduce研究方面，還處于發展階段。Twister和Haloop的模型抽象度不夠高，支援的計算有限。
6、 參考資料
（1） Twister首頁：http://www.iterativemapreduce.org/
（2） Twister論文：Twister: A Runtime for Iterative MapReduce
(http://www.iterativemapreduce.org/hpdc-camera-ready-submission.pdf)
（3） Haloop首頁：http://code.google.com/p/haloop/
（4） Haloop論文：HaLoop: Efficient Iterative Data Processing on Large Clusters（http://www.ics.uci.edu/~yingyib/papers/HaLoop_camera_ready.pdf）
原創文章，轉載請注明： 轉載自董的部落格
本文連結位址: http://dongxicheng.org/mapreduce/iterative-mapreduce-intro/