隨著web2.0技術(shù)和數(shù)據(jù)托管服務(wù)的迅猛發(fā)展，生活中的各個(gè)領(lǐng)域，包括航空影像、醫(yī)療記錄、在線交易、社會(huì)網(wǎng)絡(luò)等產(chǎn)生的大量數(shù)據(jù)為現(xiàn)有的數(shù)據(jù)密集型計(jì)算帶來(lái)了全新的問(wèn)題和挑戰(zhàn)。存儲(chǔ)于磁盤列陣中的數(shù)據(jù)以年均60%的速率增長(zhǎng) [1] 。2006年全球數(shù)據(jù)存儲(chǔ)需求為1610億GB，預(yù)計(jì)2010年將達(dá)到9880億GB。如何有效的管理和存儲(chǔ)如此巨額的數(shù)據(jù)為學(xué)術(shù)界和工業(yè)界都帶來(lái)了巨大的挑戰(zhàn)。隨著過(guò)去一段時(shí)間內(nèi)對(duì)并行計(jì)算的研究，傳統(tǒng)的并行計(jì)算模型使得系統(tǒng)的架構(gòu)和實(shí)現(xiàn)都變得更為復(fù)雜。例如，一個(gè)簡(jiǎn)單的字?jǐn)?shù)統(tǒng)計(jì)程序也需要運(yùn)用成熟的分布式機(jī)制去處理調(diào)度、合作、失敗恢復(fù)等問(wèn)題。因此，傳統(tǒng)的并行機(jī)制是不太可能滿足現(xiàn)有的數(shù)據(jù)應(yīng)用需求的。我們也能很明顯的看到，傳統(tǒng)的數(shù)據(jù)處理和計(jì)算方式成本高，效率低，從而無(wú)法適應(yīng)目前一些應(yīng)用的動(dòng)態(tài)需求，如處理不斷變化的數(shù)據(jù)集以及數(shù)據(jù)密集型計(jì)算等。

        目前工業(yè)界使用的一個(gè)比較理想的方法是建立一個(gè)大規(guī)模的計(jì)算機(jī)系統(tǒng)，它由成千上萬(wàn)個(gè)甚至上百萬(wàn)個(gè)低端計(jì)算機(jī)（稱之為節(jié)點(diǎn)）連接局域網(wǎng)組成。通過(guò)這種途徑，無(wú)論是數(shù)據(jù)并行（將數(shù)據(jù)拆分到大量的節(jié)點(diǎn)中處理）還是計(jì)算并行（并行的處理一系列的操作）都可以滿足現(xiàn)有用戶和應(yīng)用的需要。在這種環(huán)境下，資源可以動(dòng)態(tài)的擴(kuò)展和分配，數(shù)據(jù)也會(huì)被相應(yīng)的重新分配到擴(kuò)展的硬件資源中處理，從而使得計(jì)算框架變得簡(jiǎn)單有效。

        MapReduce [3] 作為一種全新的軟件構(gòu)架，用于處理計(jì)算機(jī)群中的大規(guī)模數(shù)據(jù)集。MapReduce被證實(shí)是一種強(qiáng)大的技術(shù)，因?yàn)樗?jiǎn)化了大規(guī)模分布式計(jì)算的實(shí)現(xiàn)和配置，同時(shí)它使用了更加簡(jiǎn)單的容錯(cuò)機(jī)制，并保證了企業(yè)網(wǎng)絡(luò)中大量分布式計(jì)算的一致性。它通過(guò)各節(jié)點(diǎn)的并行計(jì)算有效的處理大規(guī)模的數(shù)據(jù)集。在MapReduce中，程序員需要提供他們自己的map和reduce函數(shù)。盡管它的結(jié)構(gòu)簡(jiǎn)單，但現(xiàn)實(shí)世界中的很多問(wèn)題其實(shí)都是可以用模型表示出來(lái)的，例如建立倒排索引和計(jì)算PageRank（網(wǎng)頁(yè)級(jí)別）。事實(shí)上，這種通過(guò)將巨額數(shù)據(jù)在成千上萬(wàn)個(gè)節(jié)點(diǎn)并行運(yùn)算以達(dá)到大型運(yùn)算能力的方式已經(jīng)對(duì)現(xiàn)有的系統(tǒng)設(shè)計(jì)原理和傳統(tǒng)的系統(tǒng)經(jīng)濟(jì)帶來(lái)挑戰(zhàn)。

        對(duì)于一個(gè)典型的操作，MapReduce處理存儲(chǔ)于DFS（分布式文件系統(tǒng)）中的數(shù)據(jù)，例如Google的GFS（Google文件系統(tǒng)）和Yahoo的HDFS（Hadoop分布式文件系統(tǒng)）[2]。在DFS中，數(shù)據(jù)被分割成同等大小的數(shù)據(jù)塊（通常是128M），并且這些數(shù)據(jù)快被分布到計(jì)算機(jī)群中的不同的節(jié)點(diǎn)中。對(duì)于某個(gè)特定的任務(wù)，MapReduce創(chuàng)建一系列的mapper和reducer。Mapper處理本地?cái)?shù)據(jù)塊并產(chǎn)生一系列的鍵-值對(duì)（key-value pair）。這些鍵-值對(duì)接著被reducer進(jìn)一步處理。Reducer將屬于同一個(gè)鍵的值結(jié)合起來(lái)并產(chǎn)生最終的結(jié)果。雖然Map-reduce的思路是簡(jiǎn)單的，但它已經(jīng)解決了大量的現(xiàn)實(shí)問(wèn)題，例如建立倒排索引和計(jì)算網(wǎng)頁(yè)級(jí)別。MapReduce一開(kāi)始被設(shè)計(jì)為處理非結(jié)構(gòu)化的數(shù)據(jù)。為了將它應(yīng)用于關(guān)系型數(shù)據(jù)，它需要有效的支持關(guān)系型操作，如聯(lián)結(jié)（join）操作。將這種結(jié)構(gòu)應(yīng)用于關(guān)系型數(shù)據(jù)的研究最早在 [4] 中被提出，它定義了一個(gè)merge函數(shù)去實(shí)現(xiàn)數(shù)據(jù)庫(kù)中的關(guān)系操作。

        解決聯(lián)結(jié)操作的一個(gè)直接的方法是模擬排序合并聯(lián)結(jié)算法（sort-merge join）。對(duì)于數(shù)據(jù)表R聯(lián)結(jié)S，mapper從DFS中同時(shí)裝載兩個(gè)數(shù)據(jù)表中的數(shù)據(jù)，并根據(jù)聯(lián)結(jié)屬性排序。然螅???葑?頻絩educer中。當(dāng)mapping這個(gè)過(guò)程結(jié)束之后，每一個(gè)reducer處理R和S的子數(shù)據(jù)集并使用本地的聯(lián)結(jié)算法（如nestedloop join）對(duì)這兩個(gè)表的子集進(jìn)行聯(lián)結(jié)操作。對(duì)于每個(gè)大的數(shù)據(jù)基表，將數(shù)據(jù)從mapper傳到reducer會(huì)產(chǎn)生大量的開(kāi)銷，從而增加了數(shù)據(jù)處理的成本。根據(jù) [4] 的研究，減小從mapper到reducer的中間數(shù)據(jù)集的大小會(huì)極大的提高性能。因此，減少網(wǎng)絡(luò)開(kāi)銷（mapper到reducer的數(shù)據(jù)傳輸開(kāi)銷），可以提高聯(lián)結(jié)操作的效率。目前的問(wèn)題是我們?nèi)绾文軐⒀芯康?ldquo;優(yōu)化策略”加入到現(xiàn)有的MapReduce架構(gòu)中并且不影響其結(jié)構(gòu)的簡(jiǎn)單性，在今后我們將會(huì)看到更多的研究成果。 #p#page_title#e#

         總的來(lái)說(shuō)，對(duì)MapReduce構(gòu)架的廣泛認(rèn)同，以及越來(lái)越多的對(duì)軟件即服務(wù)（Software as a Service）的接受，使大家對(duì)分布式并行計(jì)算有了一個(gè)全新的定位和思考。從而開(kāi)創(chuàng)了數(shù)據(jù)密集型計(jì)算（DISC -- data intensive scalable computing）和云計(jì)算等技術(shù) (cloud computing)，為生活的各個(gè)方面如商業(yè)、科學(xué)、醫(yī)療保障以及環(huán)境保護(hù)等方面做出重大的貢獻(xiàn)。同時(shí)，為很多重要的計(jì)算領(lǐng)域研究課題提供了基礎(chǔ)，包括編程模型、系統(tǒng)設(shè)計(jì)、分布式以及并行算法、計(jì)算模型、系統(tǒng)安全及應(yīng)用等。

參考文獻(xiàn)：

[1] http://www.thedigitalcloud.co.uk/journal/2007/5/30/dataexplosion-ahead.html

[2] http://hadoop.apache.org.

[3] J. Dean and S. Ghemawat. MapReduce: simplified data processing on large clusters. Commun. ACM,

2008.

[4] D. DeWitt, E. Paulson, E. Robinson, J. Naughton, J. Royalty, S. Shankar, and A. Krioukov. Clustera: an integrated computation and data management system. VLDB, 2008.

原文：http://ooibc.blog.163.com/blog/static/103968235200931334237449/