什么是分布式計算

什么是分布式計算?簡單地說，分布式計算就是研究如何把一個需要非常巨大的計算能力才能解決的問題分成許多小的部分，然后把這些部分分配給許多計算機進行處理，最后把這些計算結(jié)果綜合起來得到最終的結(jié)果。

為了形象起見，這里舉一個采用蒙特卡羅算法計算圓周率π的例子來具體說明什么是分布式計算。如圖1所示，假設(shè)有一個內(nèi)嵌圓形的正方形，圓的半徑為r，面積為S1，正方形的邊長為2r，面積為S2。

圖1 π的計算方法

分別計算圓形和正方形面積，則得到如下公式。


計算推導(dǎo)可得如下公式。


接下來，根據(jù)上述推導(dǎo)結(jié)果我們可將圓周率的計算轉(zhuǎn)換為以下計算任務(wù)。

(1)在正方形內(nèi)隨機生成一些點，假設(shè)其個數(shù)為x;

(2)計算這些點落在圓形內(nèi)的個數(shù)，假設(shè)計算結(jié)果為y;

(3)則圓周率π=4y/x。

顯然，x取值越大，圓周率的計算結(jié)果就越精確，但同時對計算資源的消耗也就越大。當x大到一定程度時，單個計算機已經(jīng)無法在短時間內(nèi)完成任務(wù)了。為此，我們需要對其進行拆分，得到以下分布式算法。

(1)在正方形內(nèi)隨機生成一些點，假設(shè)其個數(shù)為x;

(2)假設(shè)目前有m個計算機可用，則每個計算機分配的計算任務(wù)為x/m個點的隨機統(tǒng)計;

(3)每個計算機分別計算這些點落在圓形內(nèi)的個數(shù)，并各自得到計算結(jié)果為y1、y2、y3…

(4)假設(shè)這m臺計算機中1臺為主計算機，主機算機匯總各計算機的計算結(jié)果，得到y(tǒng)=y1+y2+y3+…;

(5)圓周率π=4y/x。

這個例子很簡單，不過我想對于一個復(fù)雜的分布式計算任務(wù)來說，如何分配計算任務(wù)、計算過程中各計算節(jié)點間如何相互配合等問題可能還是挺難解決的。

的確如此，近來隨著Google公司提出采用MapReduce計算模型并取得不錯的應(yīng)用效果以來，針對MapReduce技術(shù)的研究和探討就變得越來越熱門，它也稱得上是云計算的標志性技術(shù)之一了。

什么是MapReduce呢?

我們還是用一個具體的例子來說明什么是MapReduce吧，假設(shè)要對三個句子中每個英文單詞出現(xiàn)的次數(shù)進行統(tǒng)計，圖2給出了采用MapReduce模型解決該問題的過程。

圖2 MapReduce的基本原理具體來說，處理過程如下。

(1)分配計算任務(wù)，計算機A、B、C得到句子1、2、3的map任務(wù);

(2)各計算機各自進行map處理，例如計算機A對句子1進行map處理后得到中間結(jié)果(map,1)、(is,1)、(good,1)，，這里將map、is和good稱為關(guān)鍵字，將關(guān)鍵字出現(xiàn)的次數(shù)(這里均為1)稱為中間值;

(3)以中間結(jié)果里面的關(guān)鍵字對中間結(jié)果進行混排聚合處理(shuffle)，并分配reduce計算任務(wù)，例如計算機2得到對三個(is,1)進行reduce處理的任務(wù);

(4)各計算機各自進行reduce處理，得到統(tǒng)計結(jié)果，例如計算機2的reduce結(jié)果為(is,3)，即表示單詞is在三個句子中一共出現(xiàn)了三次。(5)匯總各計算機的結(jié)果即得到最終結(jié)果。

Google公司的MapReduce是怎么實現(xiàn)的?

如圖3所示，Google公司在其MapReduce工作模型中定義了用戶程序(User Program)、主服務(wù)器(Master)和工作服務(wù)器(worker)三種角色。

圖3 Google的MapReduce

當用戶程序需要發(fā)起一次MapReduce計算任務(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ù)塊進行處理，得到輸入對，然后將這些對傳遞給用戶編寫的map函數(shù)，經(jīng)處理后產(chǎn)生中間結(jié)果對;

(4)這些緩存在內(nèi)存中的中間結(jié)果對被周期性地寫入本地硬盤，同時map任務(wù)將存儲位置上報給主服務(wù)器，再由主服務(wù)器告知reduce任務(wù);

(5)當reduce任務(wù)接收到主服務(wù)器關(guān)于中間結(jié)果的位置通知后，它就從指定位置讀取中間結(jié)果并同時以key為索引進行排序和聚合處理;

(6)reduce任務(wù)對聚合后的中間結(jié)果調(diào)用用戶編寫的reduce函數(shù)進行處理，處理結(jié)果被保存到輸出文件中，如果一個reduce任務(wù)中出現(xiàn)多個key索引時，它需要迭代處理所有的key索引;

(7)當所有map和reduce任務(wù)都完成以后，主服務(wù)器負責通知用戶程序，用戶程序匯總各reduce任務(wù)的輸出文件得到最終結(jié)果，或者將這些輸出文件當作下一輪MapReduce計算的輸入數(shù)據(jù)。

為什么Google公司提出MapReduce這種分布式模型后得到了這么多的關(guān)注呢?

這主要還是因為Google公司采用這種模型解決了其實際問題，所以大家才會這么重視MapReduce技術(shù)的研究。

我們知道，Google公司最成功的應(yīng)用應(yīng)該算是其搜索引擎了，搜索引擎中的一個重要工作就是需要統(tǒng)計爬蟲程序搜集的海量網(wǎng)頁數(shù)據(jù)中各個單詞出現(xiàn)的次數(shù)。根據(jù)相關(guān)報道，Google搜集的網(wǎng)頁所占存儲空間超過400TB，假設(shè)一臺計算機以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ù)器。

實際上，Hadoop開源項目的MapReduce子項目也正是參考Google關(guān)于MapReduce的論文設(shè)計實現(xiàn)的，所以兩者如此相似也就不足為奇了。