什么是分布式計(jì)算?簡單地說，分布式計(jì)算就是研究如何把一個需要非常巨大的計(jì)算能力才能解決的問題分成許多小的部分，然后把這些部分分配給許多計(jì)算機(jī)進(jìn)行處理，最后把這些計(jì)算結(jié)果綜合起來得到最終的結(jié)果。
為了形象起見，這里舉一個采用蒙特卡羅算法計(jì)算圓周率π的例子來具體說明什么是分布式計(jì)算。如圖1所示，假設(shè)有一個內(nèi)嵌圓形的正方形，圓的半徑為r，面積為S1，正方形的邊長為2r，面積為S2。
圖1 π的計(jì)算方法
分別計(jì)算圓形和正方形面積，則得到如下公式。
計(jì)算推導(dǎo)可得如下公式。
接下來，根據(jù)上述推導(dǎo)結(jié)果我們可將圓周率的計(jì)算轉(zhuǎn)換為以下計(jì)算任務(wù)。
(1)在正方形內(nèi)隨機(jī)生成一些點(diǎn)，假設(shè)其個數(shù)為x;
(2)計(jì)算這些點(diǎn)落在圓形內(nèi)的個數(shù)，假設(shè)計(jì)算結(jié)果為y;
(3)則圓周率π=4y/x。
顯然，x取值越大，圓周率的計(jì)算結(jié)果就越精確，但同時對計(jì)算資源的消耗也就越大。當(dāng)x大到一定程度時，單個計(jì)算機(jī)已經(jīng)無法在短時間內(nèi)完成任務(wù)了。為此，我們需要對其進(jìn)行拆分，得到以下分布式算法。
(1)在正方形內(nèi)隨機(jī)生成一些點(diǎn)，假設(shè)其個數(shù)為x;
(2)假設(shè)目前有m個計(jì)算機(jī)可用，則每個計(jì)算機(jī)分配的計(jì)算任務(wù)為x/m個點(diǎn)的隨機(jī)統(tǒng)計(jì);
(3)每個計(jì)算機(jī)分別計(jì)算這些點(diǎn)落在圓形內(nèi)的個數(shù)，并各自得到計(jì)算結(jié)果為y1、y2、y3…
(4)假設(shè)這m臺計(jì)算機(jī)中1臺為主計(jì)算機(jī)，主機(jī)算機(jī)匯總各計(jì)算機(jī)的計(jì)算結(jié)果，得到y(tǒng)=y1+y2+y3+…;
(5)圓周率π=4y/x。
這個例子很簡單，不過我想對于一個復(fù)雜的分布式計(jì)算任務(wù)來說，如何分配計(jì)算任務(wù)、計(jì)算過程中各計(jì)算節(jié)點(diǎn)間如何相互配合等問題可能還是挺難解決的。
的確如此，近來隨著Google公司提出采用MapReduce計(jì)算模型并取得不錯的應(yīng)用效果以來，針對MapReduce技術(shù)的研究和探討就變得越來越熱門，它也稱得上是云計(jì)算的標(biāo)志性技術(shù)之一了。
什么是MapReduce呢?
我們還是用一個具體的例子來說明什么是MapReduce吧，假設(shè)要對三個句子中每個英文單詞出現(xiàn)的次數(shù)進(jìn)行統(tǒng)計(jì)，圖2給出了采用MapReduce模型解決該問題的過程。
圖2 MapReduce的基本原理具體來說，處理過程如下。
(1)分配計(jì)算任務(wù)，計(jì)算機(jī)A、B、C得到句子1、2、3的map任務(wù);
(2)各計(jì)算機(jī)各自進(jìn)行map處理，例如計(jì)算機(jī)A對句子1進(jìn)行map處理后得到中間結(jié)果(map,1)、(is,1)、(good,1)，，這里將map、is和good稱為關(guān)鍵字，將關(guān)鍵字出現(xiàn)的次數(shù)(這里均為1)稱為中間值;
(3)以中間結(jié)果里面的關(guān)鍵字對中間結(jié)果進(jìn)行混排聚合處理(shuffle)，并分配reduce計(jì)算任務(wù)，例如計(jì)算機(jī)2得到對三個(is,1)進(jìn)行reduce處理的任務(wù);
(4)各計(jì)算機(jī)各自進(jìn)行reduce處理，得到統(tǒng)計(jì)結(jié)果，例如計(jì)算機(jī)2的reduce結(jié)果為(is,3)，即表示單詞is在三個句子中一共出現(xiàn)了三次。(5)匯總各計(jì)算機(jī)的結(jié)果即得到最終結(jié)果。
Google公司的MapReduce是怎么實(shí)現(xiàn)的?
如圖3所示，Google公司在其MapReduce工作模型中定義了用戶程序(User Program)、主服務(wù)器(Master)和工作服務(wù)器(worker)三種角色。
圖3 Google的MapReduce
當(dāng)用戶程序需要發(fā)起一次MapReduce計(jì)算任務(wù)時，整個處理流程如下。
(1)用戶程序調(diào)用MapReduce庫將輸入文件劃分為多個塊，每個塊的大小一般為16～64MB(可以定制)，然后啟動主服務(wù)器和相關(guān)工作服務(wù)器;
(2)主服務(wù)器將map和reduce任務(wù)分配給空閑的工作服務(wù)器，并把劃分好的輸入數(shù)據(jù)塊分配給各map任務(wù);
(3)map任務(wù)對輸入數(shù)據(jù)塊進(jìn)行處理，得到輸入對，然后將這些對傳遞給用戶編寫的map函數(shù)，經(jīng)處理后產(chǎn)生中間結(jié)果對;
(4)這些緩存在內(nèi)存中的中間結(jié)果對被周期性地寫入本地硬盤，同時map任務(wù)將存儲位置上報給主服務(wù)器，再由主服務(wù)器告知reduce任務(wù);
(5)當(dāng)reduce任務(wù)接收到主服務(wù)器關(guān)于中間結(jié)果的位置通知后，它就從指定位置讀取中間結(jié)果并同時以key為索引進(jìn)行排序和聚合處理;
(6)reduce任務(wù)對聚合后的中間結(jié)果調(diào)用用戶編寫的reduce函數(shù)進(jìn)行處理，處理結(jié)果被保存到輸出文件中，如果一個reduce任務(wù)中出現(xiàn)多個key索引時，它需要迭代處理所有的key索引;
(7)當(dāng)所有map和reduce任務(wù)都完成以后，主服務(wù)器負(fù)責(zé)通知用戶程序，用戶程序匯總各reduce任務(wù)的輸出文件得到最終結(jié)果，或者將這些輸出文件當(dāng)作下一輪MapReduce計(jì)算的輸入數(shù)據(jù)。
為什么Google公司提出MapReduce這種分布式模型后得到了這么多的關(guān)注呢?
這主要還是因?yàn)镚oogle公司采用這種模型解決了其實(shí)際問題，所以大家才會這么重視MapReduce技術(shù)的研究。
我們知道，Google公司最成功的應(yīng)用應(yīng)該算是其搜索引擎了，搜索引擎中的一個重要工作就是需要統(tǒng)計(jì)爬蟲程序搜集的海量網(wǎng)頁數(shù)據(jù)中各個單詞出現(xiàn)的次數(shù)。根據(jù)相關(guān)報道，Google搜集的網(wǎng)頁所占存儲空間超過400TB，假設(shè)一臺計(jì)算機(jī)以30MB/s的速度讀取這些數(shù)據(jù)，將會至少需要4個月的時間，而在其集群系統(tǒng)采用MapReduce方法后可以將該時間縮短到3個小時。
Hadoop的MapReduce又是怎樣的?
如圖4所示，Hadoop在其MapReduce模型中定義了用戶程序(ClientProgram)、作業(yè)服務(wù)器(Job Tracker)和任務(wù)服務(wù)器(Task Tracker)三種角色。
圖4 Hadoop的MapReduce
可以看出，Hadoop的MapReduce與Google的MapReduce非常相似，其作業(yè)服務(wù)器類似于Google的主服務(wù)器，任務(wù)服務(wù)器類似于Google的工作服務(wù)器。
實(shí)際上，Hadoop開源項(xiàng)目的MapReduce子項(xiàng)目也正是參考Google關(guān)于MapReduce的論文設(shè)計(jì)實(shí)現(xiàn)的，所以兩者如此相似也就不足為奇了。
