圖1 MapReduce的工作流
(4)MapReduce庫把所有具有相同中間key值I的中間value值集合在一起后傳遞給reduce函數(shù);
(5)用戶自定義的Reduce函數(shù)接受一個中間key的值I和相關的一個value值的集合。Reduce函數(shù)將這些value值合并成一個較小的value值的集合。正常的，每次Reduce函數(shù)調(diào)用只產(chǎn)生0或I個輸出value值?？梢酝ㄟ^一個迭代器把中間value值提供給Reduce函數(shù)，這樣就可以處理無法全部放入內(nèi)存中的大量的value值的集合。
2. Hadoop框架的工作機制
Hadoop是Apache軟件基金會(Apache SoftwareFoundation)組織下的一個開源項目，提供分布式計算環(huán)境下的可靠、可擴展軟件。Hadoop平臺擁有自己的分布式文件系統(tǒng)(HDFS)，具體實現(xiàn)采用MapReduce模式。Hadoop采取文件備份的方式，為每份數(shù)據(jù)制作若干拷貝，擁有較高的安全可靠性。作為一個開源的分布式系統(tǒng)平臺，Hadoop除了擁有開源所帶來的更新速度快、應用廣泛等優(yōu)勢外，還具有以下一些其它分布式云計算框架所共有的優(yōu)點：高度的可擴展性、經(jīng)濟實用性、高速有效性、高可靠性。
HDFS采用Master/Slave架構，一個HDFS集群由一個命名節(jié)點((NameNode)和一組數(shù)據(jù)節(jié)點(DataNode)組成。命名節(jié)點是一個中心服務器，負責管理文件系統(tǒng)的名字空間(NameSpace)以及客戶端對文件的訪問。在集群系統(tǒng)中，一般在一個節(jié)點上運行一個數(shù)據(jù)節(jié)點，負責管理它所在節(jié)點上的數(shù)據(jù)存儲，并負責處理文件系統(tǒng)客戶端的讀寫請求，在命名節(jié)點的統(tǒng)一調(diào)度下進行數(shù)據(jù)塊的創(chuàng)建、刪除和復制。Hadoop還實現(xiàn)了 Google的MapReduce分布式計算模型，MapReduce把應用程序的總任務分割成許多子任務，每個子任務可以在任何集群節(jié)點(數(shù)據(jù)節(jié)點，通常也作為計算節(jié)點)上并行處理。HDFS創(chuàng)建了多份數(shù)據(jù)塊(Data Blocks)的副本(Replicas)，以保證各個子任務節(jié)點計算的可靠性((Reliability)。由于采用了分布式文件系統(tǒng)和 MapRedace模型，因此Hadoop框架具有高容錯性及對數(shù)據(jù)讀寫的高吞吐率，能自動處理失敗節(jié)點。圖2是Hadoop集群系統(tǒng)架構的示意圖。
由圖2可知，HDFS是由一個命名節(jié)點和多個數(shù)據(jù)節(jié)點組成的。數(shù)據(jù)節(jié)點存儲著文件系統(tǒng)的元數(shù)據(jù)，它的作用就像是文件系統(tǒng)的總指揮，維護文件系統(tǒng)命名空間、規(guī)范客戶對于文件的存取和提供對于文件目錄的操作，數(shù)據(jù)節(jié)點中存儲著實際的數(shù)據(jù)，負責管理存儲節(jié)點上的存儲空間和來自客戶的讀寫請求。數(shù)據(jù)節(jié)點也執(zhí)行塊創(chuàng)建、刪除和來自命名節(jié)點的復制命令。
云計算是并行計算、分布式計算和網(wǎng)格計算的發(fā)展。文中詳細地闡述了MapReduce的編程思想、工作原理、步驟和方法。探討了來自Apache開源的分布式計算平臺Hadoop的核心設計MapReduce編程模型，并通過算法實驗分析和研究了MapReduce模型的工作方式和應用方法。
3.算法實例
圖2 Hadoop集群系統(tǒng)的整體結構
3.1實驗環(huán)境
(1)硬件環(huán)境配里
根據(jù)上面分析的Hadoop架構體系，Hadoop集群可以分成兩大類角色：Master和Slave，前者主要配置NameNode和 JobTracker節(jié)點;后者配置DataNode和TaskTracker節(jié)點。例如在我們的實驗中，配置Hadoop集群一共有4臺PC，一臺部署為NameNode和JobTracker，另外兩臺部署為DataNode和TaskTracker。使用的操作系統(tǒng)為Fedora 8Linux，Java環(huán)境為jdk-1.6.0-14， Hadoop版本為Hadoop0.20，并在各節(jié)點的//etc/hosts文件中添加節(jié)點IP及對應機器名。
如果該臺機器作NameNode節(jié)點用，則需要在hosts文件中加上集群中所有機器的IP地址及其對應的機器名，例如在我們的實驗中，NameNode節(jié)點的/etc/hosts文件內(nèi)容如下：
202.115. 5 .0 lin-1
202.115 。 5 .1 lin-2
202.115. 5 .2 lin-3
202.115. 5. 3 lin-4
如果該臺機器作DataNode節(jié)點用，則只需要在hosts文件中加上本機IP地址和NameNode節(jié)點的IP地址，如：
202.115 .5.0 lin-1
202.115.5.1 lin-2
(2)建立SSH受信證書
在Hadoop啟動以后，Namenode通過SSH(SecureShell)來啟動和停止各個節(jié)點上的各和守護進程，這就需要在節(jié)點之間執(zhí)行指令的時候是不需要輸人密碼的方式，所以我們需要配置SSH使用無密碼公鑰認證的方式。
(3) Hadoop平臺搭建
①將Hadoop部署至其它主機。
②在Hadoop上格式化一個新的分布式文件系統(tǒng)。
③在Hadoop上啟動Hadoop進程。
④啟動完成之后，運行ps-ef命令應該可以看到Hadoop上啟動了2個新的Java進程(NameNode， JobTracker)，同時，我們可以到Hadoop2等機器上用ps-ef查看，這些機器上應該已經(jīng)啟動了2個新的java進程(DataNode，TaskTracker)
云計算是并行計算、分布式計算和網(wǎng)格計算的發(fā)展。文中詳細地闡述了MapReduce的編程思想、工作原理、步驟和方法。探討了來自Apache開源的分布式計算平臺Hadoop的核心設計MapReduce編程模型，并通過算法實驗分析和研究了MapReduce模型的工作方式和應用方法。
(4)運行Hadoop程序
1)編寫完成Map任務的程序，處理輸人的KeyValue對，輸出中間結果。
2)編寫完成Reduce任務的程序，對中間結果進行規(guī)約，輸出最終結果。
3)定義InputFormat和OutputFormat， InputFormat的主要職責是驗證輸人的類型是否符合配置類型;
OutputFormat的職責是驗證輸出目錄是否已經(jīng)存在和輸出結果類型是否符合配置類型，如果都成立，則輸出Reduce匯總后的結果。
3.2實驗結果分析
本實驗所用的節(jié)點均為同等配置，各節(jié)點名分別為master， slave01， slave02， slave03 ， master作為NameNode和JobTracker也參與了計算，所以它也作為DataNode和TaskTracker，而slave01- slave03既作為DataNode也作為TaskTracker。在搭建的Hadoop集群系統(tǒng)上運行了本文開發(fā)的并行隨機數(shù)發(fā)生器，實驗中線性比作為一個重要的衡量標準，定義如公式3-1：
結果數(shù)據(jù)如表1所示。
從上表的分析表明：
表1 單機與Hadoop集群性能對比表
(1)單機計算數(shù)據(jù)規(guī)模較大時，算法性能呈現(xiàn)明顯的下降趨勢。隨著輸入數(shù)據(jù)的成倍增長，單機提取算法處理這些輸入數(shù)據(jù)所消耗的時間以更快的速度增長。這是因為單機上隨著輸人數(shù)據(jù)的增長，機器上內(nèi)存等資源消耗過大，致使機器性能明顯下降，因而出現(xiàn)算法性能變“慢”的現(xiàn)象。
(2)輸入數(shù)據(jù)量小時，Hadoop集群上并行化算法的處理效率低于單機上非并行化算法的處理效率。這是因為Hadoop集群的啟動和交互需要消耗一定的資源。隨著輸人數(shù)據(jù)量的增大，Hadoop集群運行速度比單機運行速度明顯加快。這是因為隨著輸人數(shù)據(jù)量的增大，集群啟動與交互的消耗相對于實際業(yè)務邏輯的消耗比率大大降低，但是單機資源消耗過快，出現(xiàn)速度瓶頸。
(3)由此可見，MapReduce模型適用于解決具有高度內(nèi)在并行性的數(shù)據(jù)密集型并行計算問題。用戶只需分解出單個節(jié)點應完成的計算單元，按傳統(tǒng)串行算法寫出計算函數(shù)和數(shù)據(jù)收集函數(shù)，在Hadoop平臺下就可方便地進行并行計算。Hadoop平臺無需用戶掌握復雜的消息傳遞機制的并行程序設計方法，顯著簡化了并行計算的軟件開發(fā)難度，有助于普及并行計算。
4.結束語
本文介紹了云計算的定義和關鍵技術，對云計算環(huán)境下的MapReduce并行編程模式進行了研究，分析了MapReduce的編程思想，編程原理和步驟。研究了在架構Hadoop集群的數(shù)據(jù)分配方式，提出一種基于計算比率的數(shù)據(jù)分配機制，以提高MapReduce在架構Hadoop集群中的性能。研究為數(shù)據(jù)挖掘領域相關算法提供了可行的MapReduce化方案，實驗結果證明了上述方案的切實有效性。
