MapReduce, Hadoop

5. MapReduce, Hadoop

四, 2008-09-25 15:27 — wea 1.何謂MapReduce?

-是一種軟體框架(software framework)
-這個軟體框架由Google實作出
-運行在眾多不可靠電腦組成的叢集(clusters)上
-能為大量資料做平行運算處理
-此框架的功能概念主要是映射(Map)和化簡(Reduce)兩種
-實作上可用C++、JAVA或其他程式語言來達成

2.何謂映射(Map)?

-從主節點(master node)輸入一組input，此input是一組key/value，將這組輸入切分成好幾個小的子部分，分散到各個工作節點(worker nodes)去做運算

3.何謂化簡(Reduce)?

-主節點(master node)收回處理完的子部分，將子部分重新組合產生輸出

4.MapReduce的Dataflow

-Input reader
-Map function
-Partition function
-Comparison function
-Reduce function
-Output writer
-上面的敘述可以下圖解釋

5.例子：

 引用自：http://blog.jteam.nl/wp-content/uploads/2009/08/MapReduceWordCountOverview1.png
附錄：
1.雲端運算核心技術 MapReduce

雲端運算的關鍵技術是 MapReduce，最早是由 Google 提出，後來也運用在開源的雲端技術 Hadoop 中。

和傳統開發模式相比，開發人員需要先分析問題的解決流程，找出可以利用平行運算來處理資料的部分，也就是那些能夠被切成小段分開來處理的資料，再針對可以採用平行處理的部分寫成 Map 程式。

有了 Map 程式之後，就可以使用大量機器用執行 Map 程式，分別同步處理分析每一段資料，再將每一個 Map 程式分析出來的結果，透過 Reduce 程式進行合併，最後則彙整出完整的結果。

MapReduce 的運作方式很像選舉開票，只要大家都遵守固定的開票程序，那由誰來開票其實都沒有影響。各投票所的開票任務就像是 Map 程式，負責處理少量資料，而 Reduce 程式就是中選會彙整投票結果的動作。

開發者將問題拆解成 MapReduce 的程式後，就可以交由雲端運算的平臺來執行Reduce程式，之後再合併。

2.雲端運算關鍵技術 MapReduce 的執行示意圖 

MapReduce 是雲端運算的關鍵技術，將要執行的問題，拆解成 Map 和 Reduce 的方式來執行，以達到分散運算的效果。

不論 Google 或 Yahoo 所採用的 MapReduce 執行概念相同，只是儲存的檔案系統不同 (Google 是 GFS，而 Yahoo 是 HDFS)。MapReduce 程式的執行過程如下：

1.將要執行的 MapReduce 程式複製到 Master 與每一臺 Worker 機器中。

2.Master 決定 Map 程式與 Reduce 程式，分別由哪些 Worker 機器執行。

3.將所有的資料區塊，分配到執行 Map 程式的 Worker 機器中進行 Map。

4.將 Map 後的結果存入 Worker 機器的本地磁碟。

5.執行 Reduce 程式的 Worker 機器，遠端讀取每一份 Map 結果，進行彙整與排序，同時執行 Reduce 程式。

6.將使用者需要的運算結果輸出。

引用自：http://p.blog.csdn.net/images/p_blog_csdn_net/sithlqf/EntryImages/20090906/implement.jpg

-------------------------------------------------------------------------------------------------------------------------------

1.Hadoop
 -本來是Apache.org在Lucene下的一個專案，由Dong Cutting所開發。
 -用來處理與保存大量資料的雲端運算平台。
 -Apache top-level 專案。
 -是一個開放源始碼的分散式計算系統的JAVA實作，可協助處理大規模的資料集(Data Sets)。
 -一套實現Google Map Reduce及GFS(Google File System)的工具。
 -Map就是將一個工作分到多個Node。
 -Reduce就是將各個Node的結果再重新結合成最後的結果。
 -運算的部分以Map Reduce為架構。
 -特色：分散式運算、運算加速及運算節點備援具穩定性。
 -使用的檔案系統：HDFS。
 -使用的儲存系統：Hbase。


2.Hadoop 簡史
 2003 年   2 月-Google 撰寫第一個 MapReduce 程式庫。
 2003 年 10 月-Google 發表Goofle File System (GFS) 論文。
 2004 年 12 月-Google 發表 MapReduce 論文。
 2005 年   7 月-Doug Cutting 在 Nutch 開始採用 MapReduce 實作。
 2006 年   2 月-Hadoop 程式碼從 Nutch 移至 Lucene 子專案。
 2006 年 11 月-Google 發表 Bigtable 論文。
 2007 年   2 月-Mike Cafarella 發佈第一個 Hbase 程式碼。
 2007 年   4 月-Yahoo! 在 1000 個節點叢集上執行 Hadoop。
 2008 年   1 月-Hadoop 成為 Apache 頂層專案。


3.Hadoop Distributed File System
 -簡稱HDFS。
 -在分散式儲存環境中，提供單一的目錄系統。
 -資料以Write-once-read-many 存取，一旦建立、寫入，就不允許修改。
 -每個檔案被分割成許多block，每個block複製許多複本(replica)，並分散儲存於不同的DataNode上。
 -NameNode：負責維護HDFS的檔案名稱空間 (File System Namespace)。
 -DataNode：實際儲存檔案區塊(Blocks)的伺服器。

 引用自：http://images.cnblogs.com/cnblogs_com/wayne1017/HDFSArch.JPG


4.Hbase
 -以 Hadoop 的 HDFS 為基礎， 提供類 Bigtable 功能。
 -類似表格的資料結構。
 -適用於數量龐大的一般伺服器上，來儲存Petabytes級的資料。
 -不是關聯式(Relational)資料庫系統。
 -表格(Table)只有一個主要索引 (primary index) 即 row key。
 -不提供 join。
 -不提供 SQL語法。


附錄：


Hadoop簡介

Hadoop 是什麼？它本來是Apache.org在Lucene下的一個專案，由Dong Cutting所開發，而在Lucene的發展歷史中，在搜尋引擎的應用上因Google的走紅，而使Dong Cutting也參考了由Google所發表的MapReduce和GFS ( Google File System ) 的發表論文後 ( Google是用這兩樣技術進行電腦的聯合運算，也就是雲端運算技術 )，在Hadoop專案中，將MapReduce及GFS進行了兩方面的實作，從這個開發原始碼的應用，使得大型機器在快速運算的能力延伸到了多台機器的 聯合運算，並且利用分散式的架構概念及日漸成熟的PC運算，達到和大型主機類似的功能。

Hadoop 的專案圖象是一頭大象，在Hadoop的專案網頁裡有它功能的介紹：「Hadoop is a software platform that lets one easily write and run applications that process vast amount of data.」一開始就點明了它用來處理程式在大量檔案的處理。而這個Hadoop專案所要應付和解決的方案是什麼呢？在網頁的簡介下也說明的很清楚：

1. Hadoop can reliably store and process petabytes.用來處理大量的資料和儲存的能力。

2. It distributes the data and processing across clusters of commonly available computers.These clusters can number into                  the thousands of nodes.將資料和處理程序分散到可以使用的電腦上，並且這些電腦的數 量可以達到上千台之多。

3. By distributing the data, Hadoop can process it in parallel on the nodes where the data is located. This make it extremely                rapid. 借由分散檔案的處理，Hadoop可以平行的運算這些檔案，並且使得檔案的處理 變的可以快速的回應。

4. Hadoop automatically maintains multiple copies of data and automatically redeloys computing tasks based on failures.這一個機制使得Hadoop成為可以信賴的運算和放置資料的平台，它可以將運算的程式 和放置的資料在每一個可以運行的node間進行複製和自動化的備份，可以避免執行中的程式或存放的資 料，因為電腦的硬體或系統的上的損壞而使程式消失或檔案損毀。