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

Mikio L. Braun柏林工業大學機器學習學博士后，TWIMPACT聯合創始人兼首席數據科學家。在其個人博客上總結了Google近幾年大數據領域的論文，并發表了自己的見解。

以下為譯文：

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

MapReuce、Google File System以及Bigtable：大數據算法的起源

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

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

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

Percolator：處理個體修改

Google并沒有止步于MapReduce。事實上，隨著Internet的指數增長，從零開始重算所有搜索索引變得不切實際。取而代之，Google開發了一個更有價值的系統，同樣支持分布式計算。

這也是其有趣的地方，特別是在對比常見的主流大數據之后。舉個例子，Percolator引入了事務，而一些NoSQL數據庫仍然在強調得到高擴展性的同時你必須犧牲（或者不再需要）事務處理。

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

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

Pregel：可擴展的圖計算

最終Google還需要挖掘圖數據，比如在線社交網絡的社交圖譜；所以他們開發了 Pregel，并在2010年公布其論文。

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

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

Dremel：在線可視化

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

Spanner：全球分布

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

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

大數據超越MapReduce

Google并沒有止步于MapReduce，他們在MapReduce不適用的地方開發新方法；當然，對于大數據領域來說這是個福音。MapReduce不是萬能的；當然，你可以更深入一步，比如說將磁盤數據移入內存，然而同樣還存在一些任務的內部結構并不是MapReduce可以擴展的。

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

Google近年來每篇論文都有著深遠的影響，同時大數據領域內有很多人必然在翹首以盼Google的下一篇論文。

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

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