摘要：Google于2004年公布了MapReduce論文，為數(shù)據(jù)領(lǐng)域工作者開啟了大數(shù)據(jù)算法之門。然而Google的大數(shù)據(jù)腳步顯然不止于此，其后公布了Percolator、Pregel、Dremel、Spanner等多篇論文。沒有止步的不僅是Google，很多公司也跟隨其腳步開發(fā)了很多優(yōu)秀的產(chǎn)品，雖然其中不乏模仿。

Mikio L. Braun柏林工業(yè)大學(xué)機(jī)器學(xué)習(xí)學(xué)博士后，TWIMPACT聯(lián)合創(chuàng)始人兼首席數(shù)據(jù)科學(xué)家。在其個(gè)人博客上總結(jié)了Google近幾年大數(shù)據(jù)領(lǐng)域的論文，并發(fā)表了自己的見解。

以下為譯文：

主流的大數(shù)據(jù)基本都是MapReduce的衍生，然而把目光聚焦到實(shí)時(shí)上就會發(fā)現(xiàn)：MapReuce的局限性已經(jīng)漸漸浮現(xiàn)。下面將討論一下自大數(shù)據(jù)開始，Google公布的大數(shù)據(jù)相關(guān)技術(shù)，以及這些技術(shù)的現(xiàn)狀。

MapReuce、Google File System以及Bigtable：大數(shù)據(jù)算法的起源

按時(shí)間算第一篇的論文應(yīng)該2003年公布的 Google File System，這是一個(gè)分布式文件系統(tǒng)。從根本上說：文件被分割成很多塊，使用冗余的方式儲存于商用機(jī)器集群上；這里不得不說基本上Google每篇論文都是關(guān)于“商用機(jī)型”。

緊隨其后的就是2004年被公布的 MapReduce，而今MapReuce基本上已經(jīng)代表了大數(shù)據(jù)。傳說中，Google使用它計(jì)算他們的搜索索引。而Mikio L. Braun認(rèn)為其工作模式應(yīng)該是：Google把所有抓取的頁面都放置于他們的集群上，并且每天都使用MapReduce來重算。

Bigtable發(fā)布于2006年，啟發(fā)了無數(shù)的NoSQL數(shù)據(jù)庫，比如：Cassandra、HBase等等。Cassandra架構(gòu)中有一半是模仿Bigtable，包括了數(shù)據(jù)模型、SSTables以及提前寫日志（另一半是模仿Amazon的Dynamo數(shù)據(jù)庫，使用點(diǎn)對點(diǎn)集群模式）。

Percolator：處理個(gè)體修改

Google并沒有止步于MapReduce。事實(shí)上，隨著Internet的指數(shù)增長，從零開始重算所有搜索索引變得不切實(shí)際。取而代之，Google開發(fā)了一個(gè)更有價(jià)值的系統(tǒng)，同樣支持分布式計(jì)算。

這也是其有趣的地方，特別是在對比常見的主流大數(shù)據(jù)之后。舉個(gè)例子，Percolator引入了事務(wù)，而一些NoSQL數(shù)據(jù)庫仍然在強(qiáng)調(diào)得到高擴(kuò)展性的同時(shí)你必須犧牲（或者不再需要）事務(wù)處理。

在2010年這篇 Percolator的論文中，Google展示了其網(wǎng)絡(luò)搜索是如何保持著與時(shí)俱進(jìn)。Percolator建立于已存類似Bigtable的技術(shù)，但是加入了事務(wù)以及行和表上的鎖和表變化的通知。這些通知之后會被用于觸發(fā)不同階段的計(jì)算。通過這樣的方式，個(gè)體的更新就可以“滲透”整個(gè)數(shù)據(jù)庫。

這種方法會讓人聯(lián)想到類似Storm（或者是Yahoo的S4）的流處理框架（SPF），然而Percolator內(nèi)在是以數(shù)據(jù)作為基礎(chǔ)。SPF使用的一般是消息傳遞而不是數(shù)據(jù)共享，這樣的話更容易推測出究竟是發(fā)生了什么。然而問題也隨之產(chǎn)生：除非你手動的在某個(gè)終端上儲存，否則你將無法訪問計(jì)算的結(jié)果。

Pregel：可擴(kuò)展的圖計(jì)算

最終Google還需要挖掘圖數(shù)據(jù)，比如在線社交網(wǎng)絡(luò)的社交圖譜；所以他們開發(fā)了 Pregel，并在2010年公布其論文。

Pregel內(nèi)在的計(jì)算模型比MapReduce復(fù)雜的多：基本上每個(gè)節(jié)點(diǎn)都擁有一個(gè)工作者線程，并且對眾多工作者線程進(jìn)行迭代并行。在每一個(gè)所謂的“superstep”中，每一個(gè)工作者線程都可以從節(jié)點(diǎn)的“收件夾”中讀取消息和把消息發(fā)送給其它節(jié)點(diǎn)，設(shè)置和讀取節(jié)點(diǎn)相關(guān)值以及邊界，或者投票停止。線程會一直運(yùn)行，直到所有的節(jié)點(diǎn)都被投票停止。此外，還擁有Aggregator和Combiner做全局統(tǒng)計(jì)。

論文陳述了許多算法的實(shí)現(xiàn)，比如Google的PageRank、最短路徑、二分圖匹配等。Mikio L. Braun認(rèn)為，對比MapReduce或SPF，Pregel需要更多實(shí)現(xiàn)的再思考。

Dremel：在線可視化

在2010年，Google還公布了 Dremel論文。一個(gè)為結(jié)構(gòu)化數(shù)據(jù)設(shè)計(jì)，并擁有類SQL語言的交互式數(shù)據(jù)庫。然而取代SQL數(shù)據(jù)庫使用字段填補(bǔ)的表格，Dremel中使用的是類JSON格式數(shù)據(jù)（更準(zhǔn)確的說，使用Google Protocol buffer格式，這將加強(qiáng)對允許字段的限制）。內(nèi)部，數(shù)據(jù)被使用特殊格式儲存，可以讓數(shù)據(jù)掃描工作來的更高效。查詢被送往服務(wù)器，而優(yōu)秀的格式可以最大性能的輸出結(jié)果。

Spanner：全球分布

最后 Spanner—— 全球分布式數(shù)據(jù)庫；Google在2009年提出了Spanner遠(yuǎn)景計(jì)劃，并在2012年對外公布Spanner論文。Spanner的公布可以說是Google向大數(shù)據(jù)技術(shù)中添的又一把火，Spanner具有高擴(kuò)展性、多版本、全球級分布以及同步復(fù)制等特性。

跨數(shù)據(jù)中心的高擴(kuò)展性及全球分布會對一致性保障提出苛刻的需求 —— 讀寫的外部一致性和基于時(shí)間戳的全局讀一致性。為了保障這一點(diǎn)，Google引入了TrueTime API。TureTime API可以同步全球的時(shí)間，擁有一個(gè)TT.now（）的方法，將獲得一個(gè)絕對時(shí)間，同時(shí)還能得到時(shí)間誤差。為了保證萬無一失，TrueTime API具有GPS和原子鐘雙保險(xiǎn)。也只有這樣的機(jī)制才能讓全球范圍內(nèi)的并發(fā)處理得到保障。

大數(shù)據(jù)超越MapReduce

Google并沒有止步于MapReduce，他們在MapReduce不適用的地方開發(fā)新方法；當(dāng)然，對于大數(shù)據(jù)領(lǐng)域來說這是個(gè)福音。MapReduce不是萬能的；當(dāng)然，你可以更深入一步，比如說將磁盤數(shù)據(jù)移入內(nèi)存，然而同樣還存在一些任務(wù)的內(nèi)部結(jié)構(gòu)并不是MapReduce可以擴(kuò)展的。

在Google思路以及論文的啟發(fā)下，同樣涌現(xiàn)出一些開源項(xiàng)目，比如：Apache Drill、Apache Giraph、斯坦福GPS等等。

Google近年來每篇論文都有著深遠(yuǎn)的影響，同時(shí)大數(shù)據(jù)領(lǐng)域內(nèi)有很多人必然在翹首以盼Google的下一篇論文。

原文鏈接： Big Data beyond MapReduce: Google's Big Data papers （編譯/仲浩 審校/王旭東）

歡迎 @CSDN云計(jì)算 微博參與討論，了解更多云信息。