數(shù)據(jù)密集型可擴展計算：數(shù)據(jù)庫前瞻 DISC: A DB perspective
隨著web2.0技術(shù)和數(shù)據(jù)托管服務(wù)的迅猛發(fā)展，生活中的各個領(lǐng)域，包括航空影像、醫(yī)療記錄、在線交易、社會網(wǎng)絡(luò)等產(chǎn)生的大量數(shù)據(jù)為現(xiàn)有的數(shù)據(jù)密集型計算帶來了全新的問題和挑戰(zhàn)。存儲于磁盤列陣中的數(shù)據(jù)以年均60%的速率增長 [1] 。2006年全球數(shù)據(jù)存儲需求為1610億GB，預(yù)計2010年將達到9880億GB。如何有效的管理和存儲如此巨額的數(shù)據(jù)為學術(shù)界和工業(yè)界都帶來了巨大的挑戰(zhàn)。隨著過去一段時間內(nèi)對并行計算的研究，傳統(tǒng)的并行計算模型使得系統(tǒng)的架構(gòu)和實現(xiàn)都變得更為復(fù)雜。例如，一個簡單的字數(shù)統(tǒng)計程序也需要運用成熟的分布式機制去處理調(diào)度、合作、失敗恢復(fù)等問題。因此，傳統(tǒng)的并行機制是不太可能滿足現(xiàn)有的數(shù)據(jù)應(yīng)用需求的。我們也能很明顯的看到，傳統(tǒng)的數(shù)據(jù)處理和計算方式成本高，效率低，從而無法適應(yīng)目前一些應(yīng)用的動態(tài)需求，如處理不斷變化的數(shù)據(jù)集以及數(shù)據(jù)密集型計算等。
目前工業(yè)界使用的一個比較理想的方法是建立一個大規(guī)模的計算機系統(tǒng)，它由成千上萬個甚至上百萬個低端計算機（稱之為節(jié)點）連接局域網(wǎng)組成。通過這種途徑，無論是數(shù)據(jù)并行（將數(shù)據(jù)拆分到大量的節(jié)點中處理）還是計算并行（并行的處理一系列的操作）都可以滿足現(xiàn)有用戶和應(yīng)用的需要。在這種環(huán)境下，資源可以動態(tài)的擴展和分配，數(shù)據(jù)也會被相應(yīng)的重新分配到擴展的硬件資源中處理，從而使得計算框架變得簡單有效。
MapReduce [3] 作為一種全新的軟件構(gòu)架，用于處理計算機群中的大規(guī)模數(shù)據(jù)集。MapReduce被證實是一種強大的技術(shù)，因為它簡化了大規(guī)模分布式計算的實現(xiàn)和配置，同時它使用了更加簡單的容錯機制，并保證了企業(yè)網(wǎng)絡(luò)中大量分布式計算的一致性。它通過各節(jié)點的并行計算有效的處理大規(guī)模的數(shù)據(jù)集。在MapReduce中，程序員需要提供他們自己的map和reduce函數(shù)。盡管它的結(jié)構(gòu)簡單，但現(xiàn)實世界中的很多問題其實都是可以用模型表示出來的，例如建立倒排索引和計算PageRank（網(wǎng)頁級別）。事實上，這種通過將巨額數(shù)據(jù)在成千上萬個節(jié)點并行運算以達到大型運算能力的方式已經(jīng)對現(xiàn)有的系統(tǒng)設(shè)計原理和傳統(tǒng)的系統(tǒng)經(jīng)濟帶來挑戰(zhàn)。
對于一個典型的操作，MapReduce處理存儲于DFS（分布式文件系統(tǒng)）中的數(shù)據(jù)，例如Google的GFS（Google文件系統(tǒng)）和Yahoo的HDFS（Hadoop分布式文件系統(tǒng)）[2]。在DFS中，數(shù)據(jù)被分割成同等大小的數(shù)據(jù)塊（通常是128M），并且這些數(shù)據(jù)快被分布到計算機群中的不同的節(jié)點中。對于某個特定的任務(wù)，MapReduce創(chuàng)建一系列的mapper和reducer。Mapper處理本地數(shù)據(jù)塊并產(chǎn)生一系列的鍵-值對（key-value pair）。這些鍵-值對接著被reducer進一步處理。Reducer將屬于同一個鍵的值結(jié)合起來并產(chǎn)生最終的結(jié)果。雖然Map-reduce的思路是簡單的，但它已經(jīng)解決了大量的現(xiàn)實問題，例如建立倒排索引和計算網(wǎng)頁級別。MapReduce一開始被設(shè)計為處理非結(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] 中被提出，它定義了一個merge函數(shù)去實現(xiàn)數(shù)據(jù)庫中的關(guān)系操作。
解決聯(lián)結(jié)操作的一個直接的方法是模擬排序合并聯(lián)結(jié)算法（sort-merge join）。對于數(shù)據(jù)表R聯(lián)結(jié)S，mapper從DFS中同時裝載兩個數(shù)據(jù)表中的數(shù)據(jù)，并根據(jù)聯(lián)結(jié)屬性排序。然螅???葑?頻絩educer中。當mapping這個過程結(jié)束之后，每一個reducer處理R和S的子數(shù)據(jù)集并使用本地的聯(lián)結(jié)算法（如nestedloop join）對這兩個表的子集進行聯(lián)結(jié)操作。對于每個大的數(shù)據(jù)基表，將數(shù)據(jù)從mapper傳到reducer會產(chǎn)生大量的開銷，從而增加了數(shù)據(jù)處理的成本。根據(jù) [4] 的研究，減小從mapper到reducer的中間數(shù)據(jù)集的大小會極大的提高性能。因此，減少網(wǎng)絡(luò)開銷（mapper到reducer的數(shù)據(jù)傳輸開銷），可以提高聯(lián)結(jié)操作的效率。目前的問題是我們?nèi)绾文軐⒀芯康?ldquo;優(yōu)化策略”加入到現(xiàn)有的MapReduce架構(gòu)中并且不影響其結(jié)構(gòu)的簡單性，在今后我們將會看到更多的研究成果。 #p#page_title#e#
總的來說，對MapReduce構(gòu)架的廣泛認同，以及越來越多的對軟件即服務(wù)（Software as a Service）的接受，使大家對分布式并行計算有了一個全新的定位和思考。從而開創(chuàng)了數(shù)據(jù)密集型計算（DISC -- data intensive scalable computing）和云計算等技術(shù) (cloud computing)，為生活的各個方面如商業(yè)、科學、醫(yī)療保障以及環(huán)境保護等方面做出重大的貢獻。同時，為很多重要的計算領(lǐng)域研究課題提供了基礎(chǔ)，包括編程模型、系統(tǒng)設(shè)計、分布式以及并行算法、計算模型、系統(tǒng)安全及應(yīng)用等。
參考文獻：
[1] http://www.thedigitalcloud.co.uk/journal/2007/5/30/dataexplosion-ahead.html
[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/
