什么是分布式計(jì)算

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

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

圖1 π的計(jì)算方法

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


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


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

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

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

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

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

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

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

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

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

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

這個(gè)例子很簡(jiǎn)單，不過(guò)我想對(duì)于一個(gè)復(fù)雜的分布式計(jì)算任務(wù)來(lái)說(shuō)，如何分配計(jì)算任務(wù)、計(jì)算過(guò)程中各計(jì)算節(jié)點(diǎn)間如何相互配合等問(wèn)題可能還是挺難解決的。

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

什么是MapReduce呢?

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

圖2 MapReduce的基本原理具體來(lái)說(shuō)，處理過(guò)程如下。

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

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

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

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

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

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

圖3 Google的MapReduce

當(dāng)用戶(hù)程序需要發(fā)起一次MapReduce計(jì)算任務(wù)時(shí)，整個(gè)處理流程如下。

(1)用戶(hù)程序調(diào)用MapReduce庫(kù)將輸入文件劃分為多個(gè)塊，每個(gè)塊的大小一般為16～64MB(可以定制)，然后啟動(dòng)主服務(wù)器和相關(guān)工作服務(wù)器;

(2)主服務(wù)器將map和reduce任務(wù)分配給空閑的工作服務(wù)器，并把劃分好的輸入數(shù)據(jù)塊分配給各map任務(wù);

(3)map任務(wù)對(duì)輸入數(shù)據(jù)塊進(jìn)行處理，得到輸入對(duì)，然后將這些對(duì)傳遞給用戶(hù)編寫(xiě)的map函數(shù)，經(jīng)處理后產(chǎn)生中間結(jié)果對(duì);

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

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

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

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

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

這主要還是因?yàn)镚oogle公司采用這種模型解決了其實(shí)際問(wèn)題，所以大家才會(huì)這么重視MapReduce技術(shù)的研究。

我們知道，Google公司最成功的應(yīng)用應(yīng)該算是其搜索引擎了，搜索引擎中的一個(gè)重要工作就是需要統(tǒng)計(jì)爬蟲(chóng)程序搜集的海量網(wǎng)頁(yè)數(shù)據(jù)中各個(gè)單詞出現(xiàn)的次數(shù)。根據(jù)相關(guān)報(bào)道，Google搜集的網(wǎng)頁(yè)所占存儲(chǔ)空間超過(guò)400TB，假設(shè)一臺(tái)計(jì)算機(jī)以30MB/s的速度讀取這些數(shù)據(jù)，將會(huì)至少需要4個(gè)月的時(shí)間，而在其集群系統(tǒng)采用MapReduce方法后可以將該時(shí)間縮短到3個(gè)小時(shí)。

Hadoop的MapReduce又是怎樣的?

如圖4所示，Hadoop在其MapReduce模型中定義了用戶(hù)程序(ClientProgram)、作業(yè)服務(wù)器(Job Tracker)和任務(wù)服務(wù)器(Task Tracker)三種角色。



圖4 Hadoop的MapReduce

可以看出，Hadoop的MapReduce與Google的MapReduce非常相似，其作業(yè)服務(wù)器類(lèi)似于Google的主服務(wù)器，任務(wù)服務(wù)器類(lèi)似于Google的工作服務(wù)器。

實(shí)際上，Hadoop開(kāi)源項(xiàng)目的MapReduce子項(xiàng)目也正是參考Google關(guān)于MapReduce的論文設(shè)計(jì)實(shí)現(xiàn)的，所以?xún)烧呷绱讼嗨埔簿筒蛔銥槠媪恕?br>

985大學(xué) 211大學(xué) 全國(guó)院校對(duì)比 專(zhuān)升本