圖1 MapReduce的工作流

(4)MapReduce庫(kù)把所有具有相同中間key值I的中間value值集合在一起后傳遞給reduce函數(shù);

(5)用戶自定義的Reduce函數(shù)接受一個(gè)中間key的值I和相關(guān)的一個(gè)value值的集合。Reduce函數(shù)將這些value值合并成一個(gè)較小的value值的集合。正常的，每次Reduce函數(shù)調(diào)用只產(chǎn)生0或I個(gè)輸出value值?？梢酝ㄟ^(guò)一個(gè)迭代器把中間value值提供給Reduce函數(shù)，這樣就可以處理無(wú)法全部放入內(nèi)存中的大量的value值的集合。

2. Hadoop框架的工作機(jī)制

Hadoop是Apache軟件基金會(huì)(Apache SoftwareFoundation)組織下的一個(gè)開源項(xiàng)目，提供分布式計(jì)算環(huán)境下的可靠、可擴(kuò)展軟件。Hadoop平臺(tái)擁有自己的分布式文件系統(tǒng)(HDFS)，具體實(shí)現(xiàn)采用MapReduce模式。Hadoop采取文件備份的方式，為每份數(shù)據(jù)制作若干拷貝，擁有較高的安全可靠性。作為一個(gè)開源的分布式系統(tǒng)平臺(tái)，Hadoop除了擁有開源所帶來(lái)的更新速度快、應(yīng)用廣泛等優(yōu)勢(shì)外，還具有以下一些其它分布式云計(jì)算框架所共有的優(yōu)點(diǎn)：高度的可擴(kuò)展性、經(jīng)濟(jì)實(shí)用性、高速有效性、高可靠性。

HDFS采用Master/Slave架構(gòu)，一個(gè)HDFS集群由一個(gè)命名節(jié)點(diǎn)((NameNode)和一組數(shù)據(jù)節(jié)點(diǎn)(DataNode)組成。命名節(jié)點(diǎn)是一個(gè)中心服務(wù)器，負(fù)責(zé)管理文件系統(tǒng)的名字空間(NameSpace)以及客戶端對(duì)文件的訪問(wèn)。在集群系統(tǒng)中，一般在一個(gè)節(jié)點(diǎn)上運(yùn)行一個(gè)數(shù)據(jù)節(jié)點(diǎn)，負(fù)責(zé)管理它所在節(jié)點(diǎn)上的數(shù)據(jù)存儲(chǔ)，并負(fù)責(zé)處理文件系統(tǒng)客戶端的讀寫請(qǐng)求，在命名節(jié)點(diǎn)的統(tǒng)一調(diào)度下進(jìn)行數(shù)據(jù)塊的創(chuàng)建、刪除和復(fù)制。Hadoop還實(shí)現(xiàn)了 Google的MapReduce分布式計(jì)算模型，MapReduce把應(yīng)用程序的總?cè)蝿?wù)分割成許多子任務(wù)，每個(gè)子任務(wù)可以在任何集群節(jié)點(diǎn)(數(shù)據(jù)節(jié)點(diǎn)，通常也作為計(jì)算節(jié)點(diǎn))上并行處理。HDFS創(chuàng)建了多份數(shù)據(jù)塊(Data Blocks)的副本(Replicas)，以保證各個(gè)子任務(wù)節(jié)點(diǎn)計(jì)算的可靠性((Reliability)。由于采用了分布式文件系統(tǒng)和 MapRedace模型，因此Hadoop框架具有高容錯(cuò)性及對(duì)數(shù)據(jù)讀寫的高吞吐率，能自動(dòng)處理失敗節(jié)點(diǎn)。圖2是Hadoop集群系統(tǒng)架構(gòu)的示意圖。

由圖2可知，HDFS是由一個(gè)命名節(jié)點(diǎn)和多個(gè)數(shù)據(jù)節(jié)點(diǎn)組成的。數(shù)據(jù)節(jié)點(diǎn)存儲(chǔ)著文件系統(tǒng)的元數(shù)據(jù)，它的作用就像是文件系統(tǒng)的總指揮，維護(hù)文件系統(tǒng)命名空間、規(guī)范客戶對(duì)于文件的存取和提供對(duì)于文件目錄的操作，數(shù)據(jù)節(jié)點(diǎn)中存儲(chǔ)著實(shí)際的數(shù)據(jù)，負(fù)責(zé)管理存儲(chǔ)節(jié)點(diǎn)上的存儲(chǔ)空間和來(lái)自客戶的讀寫請(qǐng)求。數(shù)據(jù)節(jié)點(diǎn)也執(zhí)行塊創(chuàng)建、刪除和來(lái)自命名節(jié)點(diǎn)的復(fù)制命令。

云計(jì)算是并行計(jì)算、分布式計(jì)算和網(wǎng)格計(jì)算的發(fā)展。文中詳細(xì)地闡述了MapReduce的編程思想、工作原理、步驟和方法。探討了來(lái)自Apache開源的分布式計(jì)算平臺(tái)Hadoop的核心設(shè)計(jì)MapReduce編程模型，并通過(guò)算法實(shí)驗(yàn)分析和研究了MapReduce模型的工作方式和應(yīng)用方法。

3.算法實(shí)例

圖2 Hadoop集群系統(tǒng)的整體結(jié)構(gòu)

3.1實(shí)驗(yàn)環(huán)境

(1)硬件環(huán)境配里

根據(jù)上面分析的Hadoop架構(gòu)體系，Hadoop集群可以分成兩大類角色：Master和Slave，前者主要配置NameNode和 JobTracker節(jié)點(diǎn);后者配置DataNode和TaskTracker節(jié)點(diǎn)。例如在我們的實(shí)驗(yàn)中，配置Hadoop集群一共有4臺(tái)PC，一臺(tái)部署為NameNode和JobTracker，另外兩臺(tái)部署為DataNode和TaskTracker。使用的操作系統(tǒng)為Fedora 8Linux，Java環(huán)境為jdk-1.6.0-14， Hadoop版本為Hadoop0.20，并在各節(jié)點(diǎn)的//etc/hosts文件中添加節(jié)點(diǎn)IP及對(duì)應(yīng)機(jī)器名。

如果該臺(tái)機(jī)器作NameNode節(jié)點(diǎn)用，則需要在hosts文件中加上集群中所有機(jī)器的IP地址及其對(duì)應(yīng)的機(jī)器名，例如在我們的實(shí)驗(yàn)中，NameNode節(jié)點(diǎn)的/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

如果該臺(tái)機(jī)器作DataNode節(jié)點(diǎn)用，則只需要在hosts文件中加上本機(jī)IP地址和NameNode節(jié)點(diǎn)的IP地址，如：

202.115 .5.0 lin-1

202.115.5.1 lin-2

(2)建立SSH受信證書

在Hadoop啟動(dòng)以后，Namenode通過(guò)SSH(SecureShell)來(lái)啟動(dòng)和停止各個(gè)節(jié)點(diǎn)上的各和守護(hù)進(jìn)程，這就需要在節(jié)點(diǎn)之間執(zhí)行指令的時(shí)候是不需要輸人密碼的方式，所以我們需要配置SSH使用無(wú)密碼公鑰認(rèn)證的方式。

(3) Hadoop平臺(tái)搭建

①將Hadoop部署至其它主機(jī)。

②在Hadoop上格式化一個(gè)新的分布式文件系統(tǒng)。

③在Hadoop上啟動(dòng)Hadoop進(jìn)程。

④啟動(dòng)完成之后，運(yùn)行ps-ef命令應(yīng)該可以看到Hadoop上啟動(dòng)了2個(gè)新的Java進(jìn)程(NameNode， JobTracker)，同時(shí)，我們可以到Hadoop2等機(jī)器上用ps-ef查看，這些機(jī)器上應(yīng)該已經(jīng)啟動(dòng)了2個(gè)新的java進(jìn)程(DataNode，TaskTracker)

云計(jì)算是并行計(jì)算、分布式計(jì)算和網(wǎng)格計(jì)算的發(fā)展。文中詳細(xì)地闡述了MapReduce的編程思想、工作原理、步驟和方法。探討了來(lái)自Apache開源的分布式計(jì)算平臺(tái)Hadoop的核心設(shè)計(jì)MapReduce編程模型，并通過(guò)算法實(shí)驗(yàn)分析和研究了MapReduce模型的工作方式和應(yīng)用方法。

(4)運(yùn)行Hadoop程序

1)編寫完成Map任務(wù)的程序，處理輸人的KeyValue對(duì)，輸出中間結(jié)果。

2)編寫完成Reduce任務(wù)的程序，對(duì)中間結(jié)果進(jìn)行規(guī)約，輸出最終結(jié)果。

3)定義InputFormat和OutputFormat， InputFormat的主要職責(zé)是驗(yàn)證輸人的類型是否符合配置類型;

OutputFormat的職責(zé)是驗(yàn)證輸出目錄是否已經(jīng)存在和輸出結(jié)果類型是否符合配置類型，如果都成立，則輸出Reduce匯總后的結(jié)果。

3.2實(shí)驗(yàn)結(jié)果分析

本實(shí)驗(yàn)所用的節(jié)點(diǎn)均為同等配置，各節(jié)點(diǎn)名分別為master， slave01， slave02， slave03 ， master作為NameNode和JobTracker也參與了計(jì)算，所以它也作為DataNode和TaskTracker，而slave01- slave03既作為DataNode也作為TaskTracker。在搭建的Hadoop集群系統(tǒng)上運(yùn)行了本文開發(fā)的并行隨機(jī)數(shù)發(fā)生器，實(shí)驗(yàn)中線性比作為一個(gè)重要的衡量標(biāo)準(zhǔn)，定義如公式3-1：

結(jié)果數(shù)據(jù)如表1所示。

從上表的分析表明：

表1 單機(jī)與Hadoop集群性能對(duì)比表

(1)單機(jī)計(jì)算數(shù)據(jù)規(guī)模較大時(shí)，算法性能呈現(xiàn)明顯的下降趨勢(shì)。隨著輸入數(shù)據(jù)的成倍增長(zhǎng)，單機(jī)提取算法處理這些輸入數(shù)據(jù)所消耗的時(shí)間以更快的速度增長(zhǎng)。這是因?yàn)閱螜C(jī)上隨著輸人數(shù)據(jù)的增長(zhǎng)，機(jī)器上內(nèi)存等資源消耗過(guò)大，致使機(jī)器性能明顯下降，因而出現(xiàn)算法性能變“慢”的現(xiàn)象。

(2)輸入數(shù)據(jù)量小時(shí)，Hadoop集群上并行化算法的處理效率低于單機(jī)上非并行化算法的處理效率。這是因?yàn)镠adoop集群的啟動(dòng)和交互需要消耗一定的資源。隨著輸人數(shù)據(jù)量的增大，Hadoop集群運(yùn)行速度比單機(jī)運(yùn)行速度明顯加快。這是因?yàn)殡S著輸人數(shù)據(jù)量的增大，集群?jiǎn)?dòng)與交互的消耗相對(duì)于實(shí)際業(yè)務(wù)邏輯的消耗比率大大降低，但是單機(jī)資源消耗過(guò)快，出現(xiàn)速度瓶頸。

(3)由此可見，MapReduce模型適用于解決具有高度內(nèi)在并行性的數(shù)據(jù)密集型并行計(jì)算問(wèn)題。用戶只需分解出單個(gè)節(jié)點(diǎn)應(yīng)完成的計(jì)算單元，按傳統(tǒng)串行算法寫出計(jì)算函數(shù)和數(shù)據(jù)收集函數(shù)，在Hadoop平臺(tái)下就可方便地進(jìn)行并行計(jì)算。Hadoop平臺(tái)無(wú)需用戶掌握復(fù)雜的消息傳遞機(jī)制的并行程序設(shè)計(jì)方法，顯著簡(jiǎn)化了并行計(jì)算的軟件開發(fā)難度，有助于普及并行計(jì)算。

4.結(jié)束語(yǔ)

本文介紹了云計(jì)算的定義和關(guān)鍵技術(shù)，對(duì)云計(jì)算環(huán)境下的MapReduce并行編程模式進(jìn)行了研究，分析了MapReduce的編程思想，編程原理和步驟。研究了在架構(gòu)Hadoop集群的數(shù)據(jù)分配方式，提出一種基于計(jì)算比率的數(shù)據(jù)分配機(jī)制，以提高M(jìn)apReduce在架構(gòu)Hadoop集群中的性能。研究為數(shù)據(jù)挖掘領(lǐng)域相關(guān)算法提供了可行的MapReduce化方案，實(shí)驗(yàn)結(jié)果證明了上述方案的切實(shí)有效性。

wanglin