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

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

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

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

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

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

參考文獻：

[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/