讀完這100篇論文，你也是大數據高手！

科技 05-23

導讀

PayPal高級工程總監Anil Madan寫了這篇大數據的文章，一共有100篇大數據的論文，涵蓋大數據技術棧，全部讀懂你將會是大數據的頂級高手。當然主要是了解大數據技術的整個框架，對於我們學習大數據有莫大好處。

開源（Open Source）用之於大數據技術，其作用有二：一方面，在大數據技術變革之路上，開源在眾人之力和眾人之智推動下，摧枯拉朽，吐故納新，扮演著非常重要的推動作用。另一方面，開源也給大數據技術構建了一個異常複雜的生態系統。每一天，都有一大堆「新」框架、「新」類庫或「新」工具，猶如雨後春筍般湧出，亂花漸欲「迷」人眼。為了掌控住這些「新玩意」，數據分析的達人們不得不「殫精竭慮」地「學而時習之」。

無論你是一個大數據的佈道者，還是一個日臻成熟的技術派，亦或你還在大數據這條路上「小河才露尖尖角」，多花點時間，深入理解一下大數據系統的技術體系演進，對你都會有莫大益處。全方位地理解大數據體系結構中的各個組件，並掌握它們之間的微妙差別，可在處理自己身邊的大數據案例時，助你張弛有度，「恢恢乎，其於游刃必有餘地矣!」

在過去的幾年裡，我閱讀了很多不錯的大數據文獻，這些文獻陪我成長，助我成功，使我成為一個具備良好教育背景的大數據專業人士。在這裡，撰寫此文的目的，不限於僅僅和大家分享這些很不錯的文獻，更重要的是，藉此機會，想和大家一起，集眾人之智慧，破解大數據開源系統之迷宮。

需要提醒的是，下文提及到的100篇參考文獻（這些文獻中大多都是一些開創性的研究論文），將會為你提供結構性的深度剖析，絕非泛泛而談。我相信，這可從根本上幫助你深度理解大數據體系組件間的細微差別。但如果你打算「走馬觀花」般地快速過一遍，了解大數據為何物，對不起，這裡可能會讓你失望。

那麼，準備好了嗎？讓我們走起！

在介紹這100篇文獻之前，首先讓我們看一下大數據處理的關鍵架構層（如圖1所示）：

關鍵架構層

圖1：大數據處理的關鍵架構層

讀完這100篇論文，你也是大數據高手！

文件系統層：在這一層里，分布式文件系統需具備存儲管理、容錯處理、高可擴展性、高可靠性和高可用性等特性。

數據存儲層：由於目前採集到的數據，十之有七八為非結構化和半結構化數據，數據的表現形式各異，有文本的、圖像的、音頻的、視頻的等，因此常見的數據存儲也要對應有多種形式，有基於鍵值（Key-Value）的，有基於文檔（Document），還有基於列（Column）和圖表（Graph）的。如果採用單一的資料庫引擎，「一刀切式」的滿足所有類型的數據存儲需求，通常會嚴重降低資料庫管理的性能。因此，我們需要「兵來將擋，水來土掩」式的、多元的（Polyglot）【1】資料庫解決方案（這就好比，如果「兵來了」和「水來了」，都要「將」去擋，遇到「兵」時，「將」可以「酣暢淋漓」，而遇到「水」時，還用「將」去擋，那這個「將」估計就要「捨生取義」了。文獻【1】是一本有關NoSQL數據處理的圖書）

資源管理層：這一層是為了提高資源的高利用率和吞吐量，以到達高效的資源管理與調度目的。

資源協調層：在本層的系統，需要完成對資源的狀態、分布式協調、一致性和資源鎖實施管理。

計算框架層：在本層的計算框架非常龐雜，有很多高度專用的框架包含其內，有流式的，互動式的，實時的，批處理和迭代圖的（Batch and Iterative Graph，BSP）等。為這些計算框架提供支撐的是運行時引擎，如BDAS【2】(Spark) 和 Flink等（註：這裡的BDAS是指「Berkeley Data Analytics Stack」，即伯克利數據分析棧。文獻【2】為Spark核心作者Ion Stoica的講座幻燈片文檔）。

數據分析層：在這一層里，主要包括數據分析(消費)工具和一些數據處理函數庫。這些工具和函數庫，可提供描述性的、預測性的或統計性的數據分析功能及機器學習模塊。

數據集成層：在這一層里，不僅包括管理數據分析工作流中用到的各種適用工具，除此之外，還包括對元數據（Metadata）管理的工具。

操作框架層：這一層提供可擴展的性能監測管理和基準測試框架。

架構的演進

減少數據生產者和消費者之間的處理延遲，一直是現代計算構架不斷演進的主要動力。由此，誕生了實時和低延遲處理的計算構架，如Lambda和Kappa等，這類混合架構取長補短，架起傳統的批處理層和互動式層之間連接的橋樑。

Lambda【3】 -該架構是經典的大數據處理範式，是由南森?馬茲（Nathan Marz）提出的一個實時大數據處理框架。更多有關Lamda的信息，請讀者訪問Lambda官方網站。（註：文獻【3】是由James Kinley在輕博客網站Tumblr發表的一篇博文：Lambda 架構：構架實時大數據系統的原則）。

Kappa【4】-該計算構架可視為Lambda的一個強有力替代者，Kappa將數據處理的上游移至流式層（註：文獻【4】是一篇博客文章，作者是Jay Kreps是Linkedln的一名在線數據架構技術高管。Kreps認為，雖然Lambda構架的理念很有價值，但終究還是一個臨時解決方案。他設計了一個替代架構Kappa，是基於他在Linkedin構建Kafka和Samza的經驗設計而成）。

SummingBird【5】-這是一個參考模型，用來橋接在線處理模式和傳統處理模式。Summingbird是由Twitter（推特）公司用Scala語言開發的、並開源的大規模數據處理框架，支持開發者以批處理模式（基於Hadoop）或流處理模式（基於Storm），或混合模式（即前兩種模式的組合）以統一的方式執行代碼。（註：文獻【5】是Summingbird的主要設計者Oscar Boykin、Sam Ritchie等人於2014年發表於知名期刊PVLDB中論文，其中論文的二作Sam Ritchie大有來頭，他是計算機科學界的傳奇人物、C語言和Unix的設計者Dennis Ritchie的侄子）。

在你尚未深入了解下面的各個具體的框架層次之前，建議你認真閱讀一下下面的幾篇非常有價值的文獻，它們幫為你「惡補」一下諸如NoSQL（非結構化）數據存儲、數據倉庫大規模計算及分布式系統等相關領域的背景知識：

計算中心即計算機【6】（Data center as a computer）-文獻【6】是威斯康星大學-麥迪遜分校Mark D. Hill教授主編的一個論文集式的圖書，在這本圖書中，收集了很多有關數據倉庫大規模計算的論文（註：將數據中心視為一台計算機，與傳統的高性能計算機有很大不同。計算中心的實例將以虛擬機或者容器的形式存在，計算資源的配置對於用戶而言是透明的，這樣就大幅降低系統部署的複雜度、並提高資源使用的靈活性）。

非結構化（NOSQL）數據存儲【7】– 文獻是由Rick Cattell撰寫的論文，論文討論了可擴展的結構化數據的、非結構化的（包括基於鍵值對的、基於文檔的和面向列的）數據存儲方案（註：NOSQL是支撐大數據應用的關鍵所在。事實上，將NOSQL翻譯為「非結構化」不甚準確，因為NOSQL更為常見的解釋是：Not Only SQL（不僅僅是結構化），換句話說，NOSQL並不是站在結構化SQL的對立面，而是既可包括結構化數據，也可包括非結構化數據）。

NoSQL學位論文【8】-該文獻是德國斯圖加特傳媒大學Christof Strauch撰寫的學位論文，該論文對分布式系統和第一代非結構化系統提供了非常系統的背景知識介紹。

大規模數據管理【9】-文獻是加拿大阿爾伯塔大學的研究人員撰寫的一篇綜述，討論了大數據應用程序的大規模數據管理系統，傳統的資料庫供應商與新興的互聯網企業，它們對大數據管理需求是不同的。文章的討論範圍涵蓋很廣，數據模型、系統結構及一致性模型，皆有涉及。

最終一致性（Eventual Consistency）【10】：論文討論了分布式系統中的各種不同的一致性模型。（註：原文給出的鏈接可能有誤，因為根據所提供的鏈接下載而來的論文是關於「MapReduce中日誌處理的Join演算法」的綜述文章，與「最終一致性」的討論議題無關。這裡推薦2篇新的相關論文：（1）綜述文章：資料庫最終一致性：最新的進展【10】new1；（2）微軟研究人員2013年發表於SIGMOD的文章：「最終一致性的反思（Rethinking Eventual Consistency）【10】new2」。）

CAP理論【11】-文獻以「CAP理論十二年回顧：」規則」已經變了」為題，探討了CAP理論及其演化，是篇非常不錯的介紹CAP理論的基礎性論文（註：論文作者Eric Brewer是加州大學伯克利分校的知名計算機科學學者。該文首發於《Computer》雜誌，隨後又被InfoQ和IEEE再次發表。CAP理論斷言，任何基於網路的數據共享系統，最多只能滿足數據一致性（Consistency，C）、可用性（Availability ，A）、分區（Partition，P）容忍性這三要素中的兩個要素。但通過顯式處理分區，系統設計師可做到優化數據的一致性和可用性，進而取得三者之間的妥協與平衡）。

在過去，在大規模數據處理上，傳統的並行資料庫管理系統（DBMS）和基於Map Reduce（映射-規約，以下簡稱MR）的批處理範式之間，曾發生激烈辯論，各持己見。並行資料庫管理系統的支持者【12】（註：由耶魯大學、微軟和麻省理工學院的研究人員於2009年發表在SIGMOD的一篇文章）和另外一篇文獻【13】（註：2010年發表於《美國計算機學會通訊》上的論文：「MapReduce和並行資料庫管理系統，是朋友還是敵人？」），被MR的擁躉者【14】（註：發表於美國計算機學會通訊的論文：MapReduce:一個彈性的數據處理工具）狠狠地給批駁了一番。

然而，令人諷刺的是，從那時起，Hadoop社區開始引入無共享的（Shared-Nothing）的MPP（大規模並行處理）風格的大數據處理模式，文獻「Hadoop上的SQL【15】」，便是例證。要知道，MPP是並行資料庫管理系統（DBMS）的靈魂，這樣，Map Reduce繞了一大圈，又似回到它當初離開的地方。

文件系統層

由於文件系統層關注的焦點，開始向「低延時處理」方向轉移，所以傳統基於磁碟存儲的文件系統，也開始向基於內存計算的文件系統轉變——這樣做，會大大降低I / O操作和磁碟序列化帶來的訪問開銷。Tachyon 和 SparkRDD【16】就是朝這個方向演化的範例（註：這裡RDD指的是彈性分布式數據集（Resilient Distributed Datasets），它是一種高度受限的共享內存模型，文獻【16】由伯克利大學加州分校的Matei Zaharia等撰寫的，他們提出了一種面向內存集群運算的容錯抽象模型）。

Google文件系統（GFS）【17】-該文獻是分布式文件系統的奠基之作，著名的Hadoop 分布式文件系統（HDFS），亦脫胎於GFS，基本上可視為GFS的一個簡化實現版（註：文獻【17】提出了一個可擴展的分布式文件系統GFS，可用於大型分布式數據密集型應用。文獻認為，組件故障是常態而不是異常。其所提出的GFS，著眼在幾個重要的目標，比如性能、可伸縮性、可靠性和可用性。GFS的新穎之處，並不在於它採用了多麼令人驚艷的技術，而在於它能利用所提出的方案，採用廉價的商用機器，來構建高效的分布式文件系統。有用的創新，才是真的創新，GFS做到了！）。

Hadoop 文件系統【18】-該文獻由雅虎公司的計算機科學家Konstantin Shvachko等人聯合撰寫的，論文給出了HDFS的進化歷史背景及其架構的設計內涵，是了解Hadoop技術的經典之作。

Ceph文件系統【19】-Ceph是HDFS有力的替代者【20】（註：Ceph文件系統是加州大學聖克魯茲分校（USSC）博士生Sage Weil博士期間的一項有關存儲系統的研究項目。初出茅廬，略有小成。之後，在開源社區的推動下，Ceph逐漸羽翼漸豐，風雲叱吒，功成名就，逐漸發展成為一個 Linux系統下 PB 級分布式文件系統。文獻【19】是Weil本人在2006年頂級會議OSDI發表的有關Ceph的開山論文。文獻【20】則是Weil率領他的一幫小夥伴們再次發文強調，Ceph是HDFS強有力的替代者）。

Tachyon【21】–是一個高容錯的分布式內存文件系統，其設計的核心內涵是，要滿足當下「低延遲」的數據處理要求（註：Tachyon是在內存中處理緩存文件，允許文件以訪問內存的速度在集群框架中進行可靠的共享，類似於Spark。Tachyon的吞吐量比HDFS高出100倍。Spark框架雖然也提供了強大的內存計算能力，但其沒有提供內存文件的存儲管理能力，而Tachyon則彌補了Spark的不足之處。文獻【21】是伯克利大學加州分校和麻省理工學院的研究者聯合撰寫的，發表在2014年的 SoCC國際會議上，論文一作UC Berkeley AMP實驗室博士生李浩源，他亦是Spark核心開發人員之一）。

文件系統的演化歷程，其實也見證了文件格式和壓縮技術的發展歷程。下面的參考文獻，可以讓你了解到，「面向行」或「面向列」存儲格式各自的優缺點，並且還可讓你瞭然文件存儲技術發展的新趨勢——嵌套式的面向列的存儲格式，這種存儲格式可極大提高大數據的處理效率。

當前，在文件系統階段，數據管理的最大挑戰之一就是，如何處理大數據中的數據冗餘。糾刪碼（Erasure code）是很有創意的冗餘保護機制，它可以減少三倍的冗餘副本，還不會影響數據的可恢復性與可用性。

面向列存儲 vs. 面向列存儲【22】—該文獻是是2008年發表於SIGMOD的一篇論文，該文對數據的布局、壓縮及物化（materialization）策略都做了很不錯的綜述。

RCFile【23】-這是由Facebook數據基礎設施小組和俄亥俄州立大學的華人學者共同提出的文件存儲格式，他們走了一個「中庸之道」，充分吸取面向列和面向行存儲模式的優點，揚長避短，提出了一種混合的數據存儲結構PAX（註：目前這種以行/列混合存儲技術已成功應用於 Facebook 等國內外大型互聯網企業的生產性運行體系）。

Parquet【24】– 這是一種面向行的存儲格式，其設計理念源於谷歌 Dremel論文（註：Parquet主要用於 Hadoop 的生態系統中。文獻【24】是Julien Dem在Github發表的一篇博客文章）。

ORCFile【25】–這是一種被Hive（一種基於Hadoop的數據倉庫工具）採用的、面向列存儲的改進版存儲格式（註：文獻【25】是2014年發表於頂會SIGMOD的一篇學術論文）。

壓縮技術【26】-這是是一篇闡述在Hadoop生態系統下的常見壓縮演算法的綜述性文章，文章對常見的壓縮演算法和其適用場景以及它們的優缺點，做了非常不錯的歸納總結。

糾刪碼技術（Erasure code）【27】-這是一篇是田納西大學EECS系教授James Plank撰寫的、有關存儲系統糾刪碼技術的入門級的文獻。有關糾刪碼改進技術的闡述，讀者可參閱來自南加州大學和Facebook的7名作者共同完成的論文《XORing Elephants: 面向大數據的新型糾刪碼技術【28】》（註：文獻【28】的作者開發了糾刪碼家族的新成員——基於XOR的本地副本存儲LRC，該技術是面向Hadoop生態系統的，可顯著減少修複數據時的I/O操作和存儲開銷）。

數據存儲層

寬泛地講，據對一致性（consistency）要求的強弱不同，分布式數據存儲策略，可分為ACID和BASE兩大陣營。ACID是指資料庫事務具有的四個特性：原子性（Atomicity）、一致性（Consistency）、隔離性（Isolation）、持久性（Durability）。ACID中的一致性要求比較強，事務執行的結果必須是使資料庫從一個一致性狀態變到另一個一致性狀態。而BASE對一致性要求較弱，它的三個特徵分別是：基本可用（Basically Available）, 軟狀態/柔性事務（Soft-state，即狀態可以有一段時間的不同步）, 最終一致性（Eventual consistency）。BASE還進一步細分基於鍵值的，基於文檔的和基於列和圖形的 – 細分的依據取決於底層架構和所支持的數據結構（註：BASE完全不同於ACID模型，它以犧牲強一致性，獲得基本可用性和柔性可靠性，並要求達到最終一致性）。

在數據存儲層，還有很多類似的系統和某些系統的變種，這裡，我僅僅列出較為出名的幾個。如漏掉某些重要系統，還請諒解。

BASE

鍵值存儲（Key Value Stores）

Dynamo【29】– 這是由亞馬遜工程師們設計的基於鍵值的高可用的分布式存儲系統（註：Dynamo放棄了數據建模的能力，所有的數據對象採用最簡單的Key-value模型存儲，可簡單地將Dynamo理解為一個巨大的Map。Dynamo是犧牲了部分一致性，來換取整個系統的高可用性）。

Cassandra【30】 – 這是由Facebook工程師設計的一個離散的分布式結構化存儲系統，受亞馬遜的Dynamo啟發，Cassandra採用的是面向多維的鍵值或面向列的數據存儲格式（註：Cassandra可用來管理分布在大量廉價伺服器上的巨量結構化數據，並同時提供沒有單點故障的高可用服務）。

Voldemort【31】 –這又是一個受亞馬遜的Dynamo啟發的分布式存儲作品，由全球最大的職業社交網站LinkedIn的工程師們開發而成（註：Voldemort，這個在《哈利·波特》中常被譯作「伏地魔」的開源資料庫，支撐起了LinkedIn的多種數據分析平台）。

面向列的存儲（Column Oriented Stores）

BigTable【32】 –這是一篇非常經典的學術論文，闡述了面向列的分布式的數據存儲方案，由谷歌榮譽出品。（註：Bigtable是一個基於Google文件系統的分布式數據存儲系統，是為谷歌打拚天下的「三駕馬車」之一，另外兩駕馬車分別是分布式鎖服務系統Chubby和下文將提到的MapReduce）。

HBase【33】 –目前還沒有有關Hbase的定義性論文，這裡的文獻提供了一個有關HBase技術的概述性文檔（註：Hbase是一個分布式的、面向列的開源資料庫。其設計理念源自谷歌的 BigTable，用Java語言編寫而成。文獻【33】是一個有關Hbase的幻燈片文檔）。

Hypertable【34】–文獻是一個有關「Hypertable」的技術白皮書，對該數據存儲結構做了較為詳細的介紹（註：Hypertable也是一個開源、高性能、可伸縮的資料庫，它採用與Google的Bigtable類似的模型）。

面向文檔的存儲（Document Oriented Stores）

CouchDB【35】– 這是一款面向文檔的、開源數據存儲管理系統（註：文獻【35】是一本Apache CouchDB的400多頁的官方文檔）。

MongoDB【36】 –是目前非常流行的一種非關係型(NoSQL)資料庫（註：文獻【36】是一個有關MongoDB的白皮書，對MongoDB結構做了很不錯的介紹）。

面向圖（Graph）的存儲

Neo4j【37】 –文獻是Ian Robinson等撰寫的圖書《Graph Databases（圖資料庫）》（註：Neo4j是一款目前最為流行的高性能NoSQL 圖資料庫，它使用圖來描述數據模型，把數據保存為圖中的節點以及節點之間的關係。這是最流行的圖資料庫）。

Titan【38】 –文獻是有關Titan的在線文檔（Titan是一款Apache許可證框架下的分布式的開源圖資料庫，特別為存儲和處理大規模圖而做了大量優化）。

ACID

我注意到，現在很多開源社區正在悄悄發生變化，它們開始「亦步亦趨」地跟隨谷歌的腳步。這也難怪，谷歌太牛，跟牛人混，近牛者牛 —— 下面4篇文獻，有3篇來自於谷歌的「神來之筆」，他們解決了全球分布一致的數據存儲問題。

Megastore【39】 –這是一個構建於BigTable之上的、高可用的分布式存儲系統，文獻為有關Megastore的技術白皮書（註：Megastore在被谷歌使用了數年之後，相關技術信息才在2001年公布。中文解讀：Google Megastore分布式存儲技術全揭秘）。

Spanner【40】–這是由谷歌研發的、可擴展的、全球分布式的、同步複製資料庫，支持SQL查詢訪問。（註：Spanner的「老爹」是Big Table，可以說，沒有「大表」這個爹，就不可能有這個強有力的「扳手」兒子。它是第一個把數據分布在全球範圍內的系統，並且支持外部一致性的分布式事務）。

MESA【41】–亦是由谷歌研發的、跨地域複製(geo-replicated)、高可用的、可容錯的、可擴展的近實時數據倉庫系統（註：在2014年的VLDB 大會上，谷歌公布了他們的分析型數據倉庫系統MESA，該系統主要用於存儲Google互聯網廣告業務相關的關鍵衡量數據。文獻【41】是VLDB的會議論文）。

CockroachDB【42】–該系統是由Google前工程師Spencer Kimball領導開發的Spanner 的開源版本（註：這個項目的綽號是「螳螂（Cockroach）」，其寓意是「活得長久」，因為蟑螂是地球上生命力最強的生物之一，即使被砍下頭顱，依然還能存活好幾天！文獻【42】是代碼託管網站GitHub上對Cockroach的說明性文檔）。

資源管理器層（Resource Managers）

第一代Hadoop的生態系統，其資源管理是以整體單一的調度器起家的，其代表作品為YARN。而當前的調度器則是朝著分層調度的方向演進（Mesos則是這個方向的代表作），這種分層的調度方式，可以管理不同類型的計算工作負載，從而可獲取更高的資源利用率和調度效率。

YARN【43】– 這是新一代的MapReduce計算框架，簡稱MRv2，它是在第一代MapReduce的基礎上演變而來的（註：MRv2的設計初衷是，為了解決第一代Hadoop系統擴展性差、不支持多計算框架等問題。這裡提供一個新文獻：由2011年剝離自雅虎的Hadoop初創公司Hortonworks給出的官方文獻【43】new，閱讀該文獻也可對YARN有較為深入的理解。

Mesos【44】–這是一個開源的計算框架，可對多集群中的資源做彈性管理（註：Mesos誕生於UC Berkeley的一個研究項目，現為Apache旗下的一個開源項目，它是一個全局資源調度器。目前Twitter、 Apple等國外大公司正在使用Mesos管理集群資源，國內用戶有豆瓣等。文獻【44】是加州大學伯克利分校的研究人員發表於著名會議NSDI上的學術論文）。

資源協調層

這些計算框架和調度器之間是鬆散耦合的，調度器的主要功能就是基於一定的調度策略和調度配置，完成作業調度，以達到工作負載均衡，使有限的資源有較高的利用率。

調度器（Schedulers）

作業調度器，通常以插件的方式載入於計算框架之上，常見的作業調度器有4種：

計算能力調度器【45】（Capacity Scheduler）-該文獻是一個關於計算能力調度器的指南式文檔，介紹了計算能力調度器的不同特性。

公平調度器【46】（FairShare Scheduler） -該文獻是Hadoop的公平調度器設計文檔，介紹了公平調度的各項特徵（註：公平調度是一種賦予作業資源的方法，它提供了一個基於任務數的負載均衡機制，其目的是讓所有的作業隨著時間的推移，都能平均的獲取等同的共享資源）。

延遲調度【47】（Delayed Scheduling） –該文獻是加州大學伯克利分校的一份技術報告，報告介紹了公平調度器的延遲調度策略。

公平與能力調度器【48】（Fair & Capacity schedulers ）–該文獻是一篇關於雲環境下的Hadoop調度器的綜述性論文。

協調器（Coordination）

在分布式數據系統中，協調器主要用於協調服務和進行狀態管理。

Paxos【49】 –文獻【49】是經典論文「The Part-Time Parliament（兼職的議會）【50】」的簡化版。

(註：兩篇文獻的作者均是萊斯利·蘭伯特（Leslie Lamport），此君是個傳奇人物，科技論文寫作常用編輯器LaTex，其中「La」就是來自其姓「Lamport」的前兩個字母。Lamport目前是微軟研究院首席研究員，2013年，因其在分布式計算理論領域做出的傑出貢獻，榮獲計算機領域最高獎——圖靈獎。

牛人的故事特別多，Lamport亦是這樣。就這兩篇文獻而言，Lamport的奇聞軼事都值得說道說道。光看其經典論文題目「The Part-Time Parliament（兼職的議會）【50】」，或許就讓讀者「一頭霧水」，這是一篇計算機科學領域的論文嗎？和讀者一樣感覺的可能還有期刊編輯。其實，早在1990年時，Lamport就提出Paxos演算法，他虛構了一個希臘城邦Paxos及其議會，以此來形象比喻說明該演算法的流程。論文投出後，期刊編輯建議Lamport，將論文用更加嚴謹的數學語言重新進行描述一下。可Lamport則認為，我的幽默，你不懂！拒絕修改。時隔八年之後的 1998年，Paxos演算法才被伯樂期刊《ACM Transactions on Computer Systems》發表。由於Paxos演算法本身過於複雜，且同行不理解自己的「幽默」，於是，2001年Lamport就用簡易語言撰寫這篇文章，重新發表了該論文的簡化版【49】，即「Paxos made simple（Paxos變得簡單）」。簡化版的摘要更簡單，就一句話：「Paxos演算法，用簡易英語說明之，很簡單」，如果去掉中間的那個無故緊要的定語從句，就是「Paxos演算法，很簡單」。弄得你都來不及做深思狀，摘要就完了。這…，這…，完全顛覆了我們常用的「三段論式（提問題、解問題、給結論）」的論文摘要寫法啊。

Chubby【51】– 該文獻的作者是谷歌工程師Mike Burrows。Chubby系統本質上就是前文提到的Paxos的一個實現版本，主要用於谷歌分布式鎖服務。

Zookeeper【52】 –這是Apache Hadoop框架下的Chubby開源版本。它不僅僅提供簡單地上鎖服務，而事實上，它還是一個通用的分布式協調器，其設計靈感來自谷歌的Chubby（註：眾所周知，分布式協調服務開發困難很大，分布式系統中的多進程間很容易發生條件競爭和死鎖。ZooKeeper的開發動力就是減輕分布式應用開發的困難，使用戶不必從零開始構建協調服務）。

計算框架（Computational Frameworks）

運行時計算框架，可為不同種類的計算，提供運行時（runtime）環境。最常用的是運行時計算框架是Spark和Flink。

Spark【53】 –因Spark日益普及，加之其具備良好的多計算環境的適用性，它已對傳統的Hadoop生態環境，形成了嚴峻的挑戰（註：Spark是一個基於內存計算的開源的集群計算系統，其目的在於，讓數據分析更加快速。Spark是由加州大學伯克利分校的AMP實驗室採用Scala語言開發而成。Spark的內存計算框架，適合各種迭代演算法和互動式數據分析，能夠提升大數據處理的實時性和準確性，現已逐漸獲得很多企業的支持，如阿里巴巴、百度、網易、英特爾等公司均是其用戶）。

Flink【54】 –這是一個非常類似於Spark的計算框架，但在迭代式數據處理上，比Spark更給力（註：目前大數據分析引擎Flink，已升級成為Apache頂級項目）。

Spark和Flink都屬於基礎性的大數據處理引擎。具體的計算框架，大體上，可根據採用的模型及延遲的處理不同，來進行分門別類。

批處理（Batch）

MapReduce【55】– 這是谷歌有關MapReduce的最早的學術論文。

MapReduce綜述【56】 –這是一篇過時、但依然值得一讀的、有關MapReduce計算框架的綜述性文章。

迭代式（BSP）

Pregel【57】–這又是一篇谷歌出品的大手筆論文，主要描述了大規模圖處理方法（註：Pregel是一種面向圖演算法的分布式編程框架，其採用的是迭代式的計算模型。它被稱之為Google後Hadoop時代的新「三駕馬車」之一。另外兩駕馬車分別是：「互動式」大數據分析系統Dremel和網路搜索引擎Caffeine）。

Giraph【58】 – 該系統建模於谷歌的Pregel，可視為Pregel的開源版本，它是一個基於 Hadoop架構的、可擴展的分布式迭代圖處理系統。

GraphX【59】 –這是一個同時採用圖並行計算和數據並行的計算框架（註：GraphX最先是加州大學伯克利分校AMPLab實驗室的一個分布式圖計算框架項目，後來整合到Spark中，成為其中的一個核心組件。GraphX最大的貢獻在於，在Spark之上提供一棧式數據解決方案，可方便高效地完成圖計算的一整套流水作業）。

Hama【60】– 是一個構建Hadoop之上的基於BSP模型的分布式計算引擎（註：Hama的運行環境需要關聯 Zookeeper、HBase、HDFS 組件。Hama中最關鍵的技術，就是採用了BSP模型(Bulk Synchronous Parallel，即整體同步並行計算模型，又名大同步模型)。BSP模型是哈佛大學的計算機科學家Viliant和牛津大學的BillMcColl在1990年聯合提出的，他們希望能像馮·諾伊曼體系結構那樣，架起計算機程序語言和體系結構間的橋樑，故又稱作橋模型(Bridge Model)。

開源圖處理系統【61】（Open source graph processing ）-這是滑鐵盧大學的研究人員撰寫的綜述性文獻，文獻【61】對類Pregel（Pregel-like）的、基於BSP模型的圖處理系統進行了實驗性的比較。

流式（Streaming）

流式處理【62】（Stream Processing）- 這是一篇非常棒的、有關面向大數據實時處理系統的綜述性文章。

Storm【63】 – 這是一個大數據實時處理系統（註：Storm有時也被人們稱為實時處理領域的Hadoop，它大大簡化了面向龐大規模數據流的處理機制，從而在實時處理領域扮演著重要角色。文獻【63】是Twitter工程師們在2014年發表於SIGMOD上的學術論文）。

Samza【64】 -這是一款由Linkedin公司開發的分布式的流式數據處理框架（註：所謂流式數據，是指要在處理單位內得到的數據，這種方式更注重於實時性，流式數據有時也稱為快數據）。

Spark流【65】（Spark Streaming） -該文獻是加州大學伯克利分校的研究人員於2013年在著名操作系統會議SOSP上發表的學術論文，論文題目是《離散流：容錯大規模流式計算》（註：這裡的離散流是指一種微批處理構架，其橋接了傳統的批處理和互動式處理。Spark Streaming是Spark 核心API的一個擴展，它並不會像Storm那樣逐個處理數據流，而是在處理前，按時間間隔預先將其切分為很多小段的批處理作業）。

互動式（Interactive）

Dremel【66】–這又是一篇由谷歌出品的經典論文，論文描述了如何處理「互動式」大數據的工作負載。該論文是多個基於Hadoop的開源SQL系統的理論基礎（註：文獻【66】寫於2006年，「捂」藏4年之後，於2010年公佈於眾。文章針對MR互動式查詢能力不足，提出了Dremel，闡述了Dremel的設計原理，並提供了部分測試報告）。

Impala【67】 –這是一個大規模並行處理（MPP）式 SQL 大數據分析引擎（註：Impala像Dremel一樣，其借鑒了MPP（Massively Parallel Processing，大規模並行處理）並行資料庫的思想，拋棄了MapReduce這個不太適合做SQL查詢的範式，從而讓Hadoop支持處理互動式的工作負載。本文作者阿尼爾?馬丹在LinkedIn上的博客原文，在此處的「MPI」系「MPP」筆誤，讀者可參閱文獻【67】發現此問題）。

Drill【68】–這是谷歌 Dremel的開源版本（註：Drill是一個低延遲的、能對海量數據（包括結構化、半結構化及嵌套數據）實施互動式查詢的分布式數據引擎）。

Shark【69】 –該文獻是2012年發表於SIGMOD的一篇學術論文，論文對Spark生態系統上的數據分析能力，給出了很深入的介紹（註：Shark是由加州伯克利大學AMPLab開發的大數據分析系統。Shark即「Hive on Spark」的含義，本質上是通過Hive的HQL解析，把HQL翻譯成Spark上的RDD操作。然後通過Hive的元數據獲，取資料庫里的表信息。HDFS上的數據和文件，最後會由Shark獲取，並放到Spark上運算。Shark基於 Scala語言的運算元推導，可實現良好的容錯機制，對執行失敗的長/短任務，均能從上一個「快照點（Snapshot）」進行快速恢復）。

Shark【70】–這是另外一篇很棒的於2013年發表在SIGMOD的學術論文，其深度解讀在Apache Hive之上SQL訪問機制（註：這篇文獻描述了如何構建在Spark上構建SQL引擎——Shark。更重要的是，文章還討論了之前在 Hadoop/MapReduce上實施SQL查詢如此之慢的原因）。

Dryad【71】– 文獻討論了使用有向無環圖(Directed Acycline Graph，DAG)來配置和執行並行數據流水線的方法（註：Dryad是一個通用的粗顆粒度的分布式計算和資源調度引擎，其核心特性之一，就是允許用戶自己構建DAG調度拓撲圖。文獻【71】是微軟於2007年在EuroSys國際會議上發布的學術論文）。

Tez【72】 –其核心思想來源於Dryad，可視為利用Yarn(即MRv2)對Dryad的開源實現（註：Apache Tez是基於Hadoop Yarn之上的DAG計算框架。由Hadoop的二東家Hortonworks開發並提供主要技術支持。文獻【72】是一個關於Tez的簡要介紹文檔）。

BlinkDB【73】–可在抽樣數據上實現互動式查詢，其呈現出的查詢結果，附帶有誤差標識。（註：BlinkDB 是一個用於在海量數據上運行互動式 SQL 查詢的大規模並行查詢引擎。BlinkDB允許用戶通過適當降低數據精度，對數據進行先採樣後計算，其通過其獨特的優化技術，實現了比Hive快百倍的互動式查詢速度，而查詢進度誤差僅降低2~10%。

BlinkDB採用的策略，與大數據佈道師，維克托·邁爾-舍恩伯格在其著作《大數據時代》中提到的觀點，「要全體，不要抽樣」，恰恰相反。

基於常識，我們知道：多了，你就快不了。好了，你就省不了。對大數據處理而言，也是這樣。英特爾中國研究院院長吳甘沙認為，大體量、精確性和速度快，三者不可兼得，頂多取其二。如果要實現在大體量數據上的「快」，就得想辦法減少數據，而減少數據，勢必要適度地降低分析精確性。

事實上，大數據並不見得越「大」越好，有時候一味的追求「大」是沒有必要的。例如，在醫療健康領域，如果來監控某個病人的體溫，可穿戴設備可以一秒鐘採集一次數據，也可以一分鐘採集一次數據，前者採集的數據總量比後者「大」60倍，但就監控病人身體狀況而言，意義並不是太大。雖然後者的數據忽略了人體在一分鐘內的變化，監控的精度有所下降，但對於完成監控病人健康狀態這一目的而言，是可以接受的。）

實時系統（RealTime）

Druid【74】 –這是一個開源的分布式實時數據分析和存儲系統，旨在快速處理大規模的數據，並能做到快速查詢和分析（註：文獻【74】是2014年Druid創始人Eric Tschetter和中國工程師楊仿今等人在SIGMOD上發表的一篇論文）。

Pinot【75】 –這是由LinkedIn公司出品的一個開源的、實時分布式的 OLAP數據分析存儲系統，非常類似於前面提到的Druid，LinkedIn 使用它實現低延遲可伸縮的實時分析。（註：文獻【75】是在GitHub上的有關Pinot的說明性文檔）。

數據分析層（Data Analysis）

數據分析層中的工具，涵蓋範圍很廣，從諸如SQL的聲明式編程語言，到諸如Pig的過程化編程語言，均有涉及。另一方面，數據分析層中的庫也很豐富，可支持常見的數據挖掘和機器學習演算法，這些類庫可拿來即用，甚是方便。

工具（Tools）

Pig【76】 –這是一篇有關Pig Latin非常不錯的綜述文章（註：Pig Latin原是一種兒童黑話，屬於是一種英語語言遊戲，形式是在英語上加上一點規則使發音改變，讓大人們聽不懂，從而完成孩子們獨懂的交流。文獻【76】是雅虎的工程師們於2008年發表在SIGMOD的一篇論文，論文的題目是「Pig Latin：並不是太老外的一種數據語言」，言外之意，他們發明了一種數據處理的「黑話」——Pig Latin，一開始你可能不懂，等你熟悉了，就會發現這種數據查詢語言的樂趣所在）。

Pig【77】 – 這是另外一篇由雅虎工程師們撰寫的有關使用Pig經驗的論文，文章介紹了如果利用Pig在Map-Reduce上構建一個高水準的數據流分析系統。

Hive【78】 –該文獻是Facebook數據基礎設施研究小組撰寫的一篇學術論文，介紹了Hive的來龍去脈（註：Hive是一個建立於 Hadoop 上的數據倉庫基礎構架。它用來進行數據的提取、轉化和載入（即Extract-Transform-Load ，ETL），它是一種可以存儲、查詢和分析存儲在 Hadoop 中的大規模數據的機制）。

Hive【79】–該文獻是另外一篇有關Hive的值得一讀的好論文。論文作者來自Facebook數據基礎設施研究小組，在這篇論文里，可以幫助讀者理解Hive的設計理念。

Phoenix【80】 –它是 HBase 的 SQL 驅動（註：Phoenix可將 SQL 查詢轉成 HBase 的掃描及相應的動作。文獻【80】是關於在Hbase上部署SQL的幻燈片文檔）。

Map Reduce上的連接（join）演算法【81】–該文獻介紹了在Hadoop環境下的各種並行連接演算法，並對它們的性能作出系統性評測。

Map Reduce上的連接演算法【82】 –這是威斯康星大學和IBM研究團隊撰寫的綜述性文章，文章對在Map Reduce模型下的各種連接演算法進行了綜合比較。

庫（Libraires）

MLlib【83】–這是在Spark計算框架中對常用的機器學習演算法的實現庫，該庫還包括相關的測試和數據生成器（註：文獻【83】是MLlib的一個幻燈片說明文檔）。

SparkR【84】–這是AMPLab發布的一個R開發包，為Apache Spark提供輕量級的前端（註：R是一種廣泛應用於統計分析、繪圖的語言及操作環境。文獻【84】是有關SparkR的幻燈片文檔）。

Mahout【85】 –這是一個功能強大的數據挖掘工具，是一個基於傳統Map Reduce的分布式機器學習框架（註：Mahout的中文含義就是「馭象之人」，而Hadoop的Logo正是一頭小黃象。很明顯，這個庫是幫助用戶用好Hadoop這頭難用的大象。文獻【85】是有關Mahout的圖書）。

數據集成層（Data Integration）

數據集成框架提供了良好的機制，以協助高效地攝取和輸出大數據系統之間的數據。從業務流程線到元數據框架，數據集成層皆有涵蓋，從而提供全方位的數據在整個生命周期的管理和治理。

攝入/消息傳遞（Ingest/Messaging）

Flume【86】 –這是Apache旗下的一個分布式的、高可靠的、高可用的服務框架，可協助從分散式或集中式數據源採集、聚合和傳輸海量日誌（註：文獻【86】是Apache網站上有關Flume的一篇博客文章）。

Sqoop【87】–該系統主要用來在Hadoop和關係資料庫中傳遞數據（註：Sqoop目前已成為Apache的頂級項目之一。通過Sqoop，可以方便地將數據從關係資料庫導入到HDFS，或反之亦可。文獻【87】是有關Sqoop的幻燈片說明文檔）。

Kafka【88】 –這是由LinkedIn開發的一個分布式消息系統（註：由Scala編寫而成的Kafka，由於可水平擴展、吞吐率高等特性，得到廣泛應用。文獻【88】是LindedIn的工程師們在2011年發表於NetDB的會議論文）。

ETL/工作流

ETL是數據抽取（Extract）、清洗（Cleaning）、轉換（Transform）、裝載（Load）的過程，是構建數據倉庫的重要一環。

Crunch【89】–這是Apache旗下的一套Java API函數庫，它能夠大大簡化編寫、測試、運行MapReduce 處理工作流的程序（註：文獻【89】是有關Crunch的幻燈片解釋文檔）。

Falcon【90】– 這是Apache旗下的Falcon大數據管理框架，可以幫助用戶自動遷移和處理大數據集合（註：文獻【90】是一份關於Falcon技術預覽報告）。

Cascading【91】 –這是一個架構在Hadoop上的API函數庫，用來創建複雜的可容錯的數據處理工作流（註：文獻【91】是關於Hadoop上的Cascading的概論和技術隨筆）。

Oozie【92】–是一個工作流引擎，用來協助Hadoop作業管理（註：Oozie字面含義是馴象之人，其寓意和Mahout一樣，幫助用戶更好地搞定Hadoop這頭大象。文獻【92】是Apache網站上有關Oozie的官方文檔）。

元數據（Metadata）

HCatalog【93】– 它提供了面向Apache Hadoop的數據表和存儲管理服務（註：Apache HCatalog提供一個共享的模式和數據類型的機制，它抽象出表，使用戶不必關心數據怎麼存儲，並提供了可操作的跨數據處理工具。文獻【93】是Apache網站有關Hcatalog的官方說明文檔）。

序列化（Serialization）

Protocol Buffers【94】 –由Google推廣的一種與語言無關的、對結構化數據進行序列化和反序列化的機制（註：Protocol Buffers可用於通訊協議、數據存儲等領域的語言及平台無關、可擴展的序列化結構數據格式。文獻【94】是有關Protocol Buffers幻燈片文檔）。

Avro【95】 –這是一個建模於Protocol Buffers之上的、Hadoop生態系統中的子項目（註：Avro本身既是一個序列化框架，同時也實現了RPC的功能）。

操作框架（Operational Frameworks）

最後，我們還需要一個操作性框架，來構建一套衡量標準和測試基準，從而來評價各種計算框架的性能優劣。在這個操作性框架中，還需要包括性能優化工具，藉助它來平衡工作負載。

監測管理框架（Monitoring Frameworks）

OpenTSDB【96】 –這是構建於HBase之上的實時性能評測系統（註：文獻【96】提供了OpenTSDB的簡要概述，介紹了OpenTSDB的工作機理）。

Ambari【97】– 這是一款基於Web的系統，支持Apache Hadoop集群的供應、管理和監控（註：文獻【97】闡述了Ambari架構的設計準則）。

基準測試（Benchmarking）

YCSB【98】 –該文獻是一篇使用YCSB對NoSQL系統進行性能評估的期刊論文（註：YCSB是雅虎雲服務基準測試（Yahoo! Cloud Serving Benchmark）的簡寫。見名知意，它是由雅虎出品的一款通用雲服務性能測試工具）。

GridMix【99】 –該系統通過運行大量合成的作業，對Hadoop系統進行基準測試，從而獲得性能評價指標（註：文獻是Apache網站有關GridMix的官方說明文檔）。

最後一篇文獻是有關大數據基準測試的綜述文章【100】，文章討論了基準測試的最新技術進展以及所面臨的幾個主要挑戰。