讀懂這100篇論文，你也能成為大數據專家

02-12

今天在網上閑逛，無意間發現了這一篇好文，原文作者是PayPal高級工程總監Anil Madan，文章對當前大數據領域用到的一些技術、框架等都做了一遍梳理。通過閱讀本文，可以對當前大數據領域有一個很好的認識，如果需要深入了解某項技術，可以閱讀文章中所給的文章或論文的相關鏈接，都是不可多得的好資源。

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

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

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

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

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

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

關鍵架構層

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

文件系統層：在這一層里，分散式文件系統需具備存儲管理、容錯處理、高可擴展性、高可靠性和高可用性等特性。
數據存儲層：由於目前採集到的數據，十之有七八為非結構化和半結構化數據，數據的表現形式各異，有文本的、圖像的、音頻的、視頻的等，因此常見的數據存儲也要對應有多種形式，有基於鍵值（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 和 Spark RDD【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 年公布。CSDN 網站亦有文獻【39】的中文解讀：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 系統擴展性差、不支持多計算框架等問題。對國內用戶而言，原文獻下載鏈接可能會產生 404 錯誤，這裡提供一個新文獻：由 2011 年剝離自雅虎的 Hadoop 初創公司 Hortonworks 給出的官方文獻【43】new，閱讀該文獻也可對 YARN 有較為深入的理解。CSDN 亦有對 YARN 詳細解讀的文章：更快、更強——解析 Hadoop 新一代 MapReduce 框架 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 演算法，很簡單」。弄得你都來不及做深思狀，摘要就完了。這…，這…，完全顛覆了我們常用的「三段論式（提問題、解問題、給結論）」的論文摘要寫法啊。

後來，隨著分散式系統的不斷發展壯大，Paxos 演算法開始大顯神威。Google 的 Chubby 和 Apache 的 Zookeeper，都是用 Paxos 作為其理論基礎實現的。就這樣， Paxos 終於登上大雅之堂，它也為 Lamport 在 2013 年獲得圖靈獎，立下汗馬功勞。從 Lamport 發表 Paxos 演算法的小案例，我們可以看出：彪悍的人生，不需要解釋。牛逼的論文，就可以任性！

Chubby【51】– 該文獻的作者是谷歌工程師 Mike Burrows。Chubby 系統本質上就是前文提到的 Paxos 的一個實現版本，主要用於谷歌分散式鎖服務。（註：原文鏈接會出現 404 錯誤，CSDN 網站有 Chubby 論文的下載鏈接）。

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 的最早的學術論文（註：對於國內用戶，點擊原文獻鏈接可能會產生 404 錯誤，CSDN 網站有 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】，文章討論了基準測試的最新技術進展以及所面臨的幾個主要挑戰。

譯者寄語：

在你邁步於大數據的旅途中，真心希望這些文獻能助你一臂之力。但要知道，有關大數據的文獻，何止千萬，由於個人精力、能力有限，有些領域也不甚熟稔，故難免會掛一漏萬。如有疏忽，漏掉你的大作，還請你海涵。最後，希望這些文獻能給你帶來「學而時習之，不亦樂乎」的快感！

譯者介紹：張玉宏，博士。2012 年畢業於電子科技大學，現執教於河南工業大學。中國計算機協會（CCF）會員，ACM/IEEE 會員。主要研究方向為高性能計算、生物信息學，主編有《Java 從入門到精通》一書。

英文原文：linkedin