隨著大規(guī)模搜索引擎（如Google和Yahoo! ）、基因組分析（DNA測序、RNA測序和生物標志物分析）以及社交網(wǎng)絡（如Facebook 和Twitter) 的不斷發(fā)展，需要生成和處理的數(shù)據(jù)量已經(jīng)超過了千萬億字節(jié)。為了滿足如此龐大的計算需求，我們需高效、可伸縮的并行算法。MapReduce范式就是解決這些問題的一個框架。
　　MapReduce是一個軟件框架，可以采用并行、分布式方式處理GB、TB，甚至PB級的大數(shù)據(jù)集，同時它也是一個在商用服務器集群之上完成大規(guī)模數(shù)據(jù)處理的執(zhí)行框架。實現(xiàn)MapReduce 的方法有很多，不過這本書中我們主要關注Apache Spark 和MapReduce/ Hadoop。你將通過簡單而具體的示例來了解如何用Spark和Hadoop實現(xiàn)MapReduce。
　　這本書將為以下領域提供了基本分布式算法（分別用MapReduce、Hadoop和Spark實現(xiàn)），并按照這些領域組織本書的章節(jié)：
　　. 基本設計模式。
　　. 數(shù)據(jù)挖掘和機器學習。
　　. 生物信息、基因組和統(tǒng)計。
　　. 優(yōu)化技術。
　　MapReduce是什么？
　　MapReduce 是一種編程范式，可以利用集群環(huán)境的成百上千臺服務器實現(xiàn)強大的可伸縮性。MapReduce一詞最早源于函數(shù)式編程，由Google在一篇名為MapReduce: Simplified Data Processing on
　　Large Clusters 的文章中率先提出。Google的MapReduce[8]實現(xiàn)是一個專用解決方案，還沒有向公眾發(fā)布。
　　reduce():.(Key2,.[Value2])..[(Key3,.Value3)]
　　這本書中會使用map() 函數(shù)和reduce() 函數(shù)的非形式化表示，我會用中括號（[]）表示列表。
　　MapReduce 的核心概念是將輸入數(shù)據(jù)集映射到一個鍵-值對集合，然后對所有包含相同鍵的鍵-值對完成歸約。盡管基本概念很簡單，不過如果考慮以下方面，可以看到這個概念確實很強大、很有效：幾乎所有數(shù)據(jù)都可以映射到鍵-值對。
　　鍵和值可以是任意類型：String、Integer、FASTQ （用于DNA測序）、用戶自定義的定制類型，當然，也可以是鍵-值對本身。
　　MapReduce如何在一組服務器上擴展？MapReduce是如何工作的？關鍵在于，從概念上講，MapReduce 的輸入是一個記錄列表（每個記錄可以是一行或多行數(shù)據(jù)）。這些輸入記錄會劃分并傳遞到集群中的多臺服務器，由map() 函數(shù)使用。map() 計算的結(jié)果是一個鍵-值對列表。然后reduce() 函數(shù)取各個包含相同鍵的值集，將它們分別組合為一個值（或一個值集）。換句話說，map() 函數(shù)是由一組數(shù)據(jù)塊生成鍵-值對，reduce() 則是組合map()生成的數(shù)據(jù)輸出，從而能得到所需要的結(jié)果，而不是一組鍵-值對。
　　MapReduce 的主要優(yōu)點之一是它的不共享（shared-nothing ）數(shù)據(jù)處理平臺。這意味著所有映射器可以獨立地工作，而且映射器完成它們的任務時，歸約器也能獨立地開始工作（映射器或歸約器之間不共享任何數(shù)據(jù)或臨界區(qū)。如果有臨界區(qū)，這會減慢分布式計算的速度）�；�于這種不共享范式，我們可以很容易地編寫map() 函數(shù)和reduce() 函數(shù)，而且能輕松、有效地提高并行性。
　　為什么使用MapReduce?
　　前面我們討論過，MapReduce 的目標是通過增加更多的商用服務器來實現(xiàn)橫向擴容。這與縱向擴容是不同的（縱向擴容是為系統(tǒng)中的單個節(jié)點增加更多資源，如內(nèi)存和CPU）。縱向擴容可能成本很高，有時由于成本以及軟件或硬件限制等原因，可能根本無法增加更多的資源。有時人們會提出一些基于主存的新興算法來解決數(shù)據(jù)問題，但是由于主存是一個瓶頸，所以這些算法缺乏可伸縮性。例如，在DNA測序分析中，可能需要超過512GB的RAM，這非常昂貴，而且不具有可伸縮性。
　　如果要提高計算能力，可能需要把計算分布到多個機器上完成。例如，要完成500GB 樣本數(shù)據(jù)的DNA測序，可能需要一個服務器計算4天才能完成比對階段。利用MapReduce，60 臺服務器可以把計算時間銳減到2小時以內(nèi)。要處理大量的數(shù)據(jù)，必須能夠?qū)⑦@些數(shù)據(jù)劃分為小塊來進行處理，再組合得到最終的結(jié)果。MapReduce/Hadoop 和Spark/Hadoop 可以幫助你提高計算能力，你只需要寫兩個函數(shù)：
　　map() 和reduce() 。顯然，MapReduce 范式為數(shù)據(jù)分析領域提供了一個強大的新工具，近來，歸功于Hadoop 等開源解決方案，這個新工具得到了越來越多的關注。
　　基本說來，MapReduce提供了以下優(yōu)點：
　　.編程模型 基礎架構(gòu)。
　　. 能夠編寫在數(shù)百甚至上千臺機器上運行的程序。
　　. 自動并行化和分布
　　. 容錯（如果一臺服務器宕機，作業(yè)可以由其他服務器完成）。
　　.程序/作業(yè)調(diào)度、狀態(tài)檢查和監(jiān)控。
　　Hadoop和Spark
　　Hadoop（http://hadoop.apache.org/ ）是MapReduce應用實現(xiàn)的事實標準。它由一個或多個主節(jié)點和任意多個從節(jié)點組成。Hadoop提出數(shù)據(jù)中心就是計算機，通過提供map() 函數(shù)和reduce() 函數(shù)（由程序員定義），允許應用開發(fā)人員或程序員利用這些數(shù)據(jù)中心，從而簡化分布式應用。Hadoop 高效地實現(xiàn)了MapReduce 范式，很容易學習，這是一個可以處理TB甚至PB級大數(shù)據(jù)的強大工具。
　　在這本書中，大部分MapReduce 算法都采用實例的形式給出（已編譯的完整實用解決方案），并且在Java/MapReduce/Hadoop 和/或Java/Spark/Hadoop 中得到實現(xiàn)。Hadoop和Spark（http://spark.apache.org/ ）框架是開源的，允許我們在分布式環(huán)境中完成大數(shù)據(jù)量的計算和數(shù)據(jù)處理。
　　這些框架通過提供橫向擴容方法來支持可伸縮性，可以采用MapReduce 范式在數(shù)千臺服務器上運行密集型計算。與Hadoop的API相比，Spark的API提供了更高層的抽象。由于這個原因，只用一個Java驅(qū)動器類就可以描述Spark解決方案。
　　Hadoop和Spark是兩個不同的分布式軟件框架。Hadoop是一個MapReduce框架，在這個框架上可以運行支持map() 、combine() 和reduce() 函數(shù)的作業(yè)。MapReduce范式很適合單趟計算［先map() ，再reduce() ］，不過對于多趟算法效率則很低。Spark 不是一個MapReduce框架，不過很容易用來支持MapReduce框架的功能，它提供了一個適當?shù)腁PI 可以處理map() 和reduce() 功能。Spark并不限于先完成映射階段再完成歸約階段。Spark 作業(yè)可以是由映射和/或歸約/洗牌階段構(gòu)成的一個任意DAG（有向無環(huán)圖）。Spark程序可以使用Hadoop運行，也可以不使用Hadoop，另外Spark可以使用Hadoop分布式文件系統(tǒng)（Hadoop Distributed File System，HDFS）或者其他持久存儲來實現(xiàn)輸入/輸出。基本上，對于一個給定的Spark程序或作業(yè)，Spark引擎會創(chuàng)建將在集群上完成的任務階段所構(gòu)成的一個有向無環(huán)圖，Hadoop/MapReduce 則不同，它會創(chuàng)建由兩個預定義階段（映射和歸約）構(gòu)成的有向無環(huán)圖。注意，Spark創(chuàng)建的DAG可以包含任意多個階段。與Hadoop/ MapReduce相比，這使得大多數(shù)Spark作業(yè)都能更快地完成，因為簡單的作業(yè)只需要一個階段就可以完成，更復雜的任務也可以一起完成（包括多個階段），而不需要劃分為多個作業(yè)。前面已經(jīng)提到，相比于MapReduce/Hadoop，Spark的API提供了更高層的抽象。例如，Spark的幾行代碼可能等價于MapReduce/Hadoop的30～40行代碼。
　　盡管Hadoop和Spark等框架建立一個不共享范式基礎之上，不過它們確實也支持在所有集群節(jié)點上共享不可變的數(shù)據(jù)結(jié)構(gòu)。在Hadoop中，可以通過Hadoop的Configuration對象將這些值傳遞給映射器和歸約器。除了Broadcast只讀對象，Spark還支持只寫累加器。Hadoop和Spark為大數(shù)據(jù)處理提供了以下好處：
　　可讀性
　　Hadoop和Spark支持容錯（任何節(jié)點宕機不會丟失所需的計算結(jié)果）。
　　可伸縮性
　　Hadoop和Spark支持龐大的服務器集群。
　　分布式處理
　　在Spark和Hadoop中，輸入數(shù)據(jù)和處理是分布式的（可以全面支持大數(shù)據(jù)）。并行化
　　可以在節(jié)點集群上并行地執(zhí)行計算。
　　Hadoop 主要設計用于批處理，不過如果有足夠的內(nèi)存/RAM，Spark 可以用于近實時處理。要了解Spark RDDs（resilient distributed data sets，彈性分布式數(shù)據(jù)集）的基本用法，可以參考附錄B。
　　那么MapReduce/Hadoop的核心組件有哪些？
　　.輸入/輸出數(shù)據(jù)包括鍵-值對。一般地，鍵是整型、長整型和字符串，而值可以是幾乎任何數(shù)據(jù)類型（字符串、整型、長整型、句子、特殊格式的數(shù)據(jù)等）。
　　. 數(shù)據(jù)劃分到商用節(jié)點上，填充到數(shù)據(jù)中心。
　　.這個軟件會處理故障、重啟和其他意外中斷。這稱為容錯（fault tolerance），這也是Hadoop的一個重要特性。
　　Hadoop和Spark不只是提供了map() 和reduce() 功能，還提供了插件模型來實現(xiàn)定制記錄讀取、二次數(shù)據(jù)排序及更多其他功能。
　　圖P-2展示了Spark、YARN 和Hadoop HDFS之間關系的一個高層視圖。
　　圖P-2：MapReduce、Spark和HDFS之間的關系
　　從這個關系可以看到，使用HDFS （和非HDFS文件系統(tǒng)）運行MapReduce和Spark有很多方法。在這本書中，我會用到以下關鍵詞和術語：
　　.MapReduce表示一般的MapReduce框架范式。
　　.MapReduce/Hadoop表示使用Hadoop的一個特定的MapReduce框架實現(xiàn)。
　　.Spark 表示一個特定的Spark實現(xiàn)，它使用HDFS 作為持久存儲或計算引擎（注意，Spark可以在任何數(shù)據(jù)存儲庫上運行，不過這里我們主要強調(diào)Hadoop的HDFS）：
　　─Spark 可以脫離Hadoop 使用獨立的集群節(jié)點運行（可以使用HDFS、NFS或其他媒介作為持久數(shù)據(jù)存儲庫）。
　　─Spark也可以結(jié)合Hadoop，使用Hadoop的YARN 或MapReduce框架運行。
　　通過這本書，你會循序漸進地學習使用Hadoop 構(gòu)建MapReduce 應用所需的算法和工具。MapReduce/Hadoop 已經(jīng)成為處理大數(shù)據(jù)集（如日志數(shù)據(jù)、基因組序列、統(tǒng)計應用和社交圖譜）的理想編程模型。MapReduce 可以用于任何不需要緊耦合并行處理的應用。要記住，Hadoop主要設計用于MapReduce批處理，它并不是一個理想的實時處理解決方案。不要期望在2～5s時間內(nèi)從Hadoop得到答案，最小的作業(yè)也可能需要超過20s的時間。Spark是一個頂級Apache項目，非常適合近實時處理，如果有更多的RAM，它的表現(xiàn)將會更出色。利用Spark ，如果使用一個包括100個節(jié)點的集群運行一個大數(shù)據(jù)處理作業(yè)（如生物標志物分析或Cox回歸），完全有可能在25～35s內(nèi)處理2億條記錄。一般地，Hadoop作業(yè)會有15～20s的延遲，不過這取決于Hadoop集群的大小和配置。
　　MapReduce 實現(xiàn)（如Hadoop ）可以在一個龐大的商用計算機集群上運行，具有很好的可伸縮性。例如，一個典型的MapReduce計算過程可以在數(shù)百或數(shù)千臺機器上處理PB或TB 級的數(shù)據(jù)。程序員會發(fā)現(xiàn)
　　，MapReduce 很容易使用，因為它隱藏了并行化、容錯、數(shù)據(jù)分布和負載平衡等繁雜的細節(jié)，使程序員可以集中精力編寫兩個關鍵函數(shù)map() 和reduce()。
　　下面是MapReduce/Hadoop/Spark的一些主要應用：
　　. 查詢?nèi)罩咎幚怼?br />　　. 抓取、索引和搜索。
　　. 分析、文本處理情感分析。
　　. 機器學習（如馬爾可夫鏈和樸素貝葉斯分類器）。
　　. 推薦系統(tǒng)。
　　. 文檔聚類和分類。
　　. 生物信息學（比對、重新校準、生殖細胞采集和DNA/RNA測序）。
　　. 基因組分析（生物標志物分析以及回歸算法，如線性回歸和Cox回歸）。
　　本書內(nèi)容
　　這本書中每一章分別提出一個問題，然后通過一組MapReduce算法加以解決。MapReduce 算法/解決方案相當完整（包括MapReduce驅(qū)動器、映射器、組合器和歸約器程序）�？梢栽陧椖恐兄苯邮褂眠@些代碼（不過，有時可能需要剪切粘貼你需要的部分）。這本書沒有涉及MapReduce 框架的底層理論，而是著重于提供使用MapReduce/Hadoop 和Spark 解決大數(shù)據(jù)難題的實用算法和示例。這本書的主要內(nèi)容包括：
　　. 完成超大量交易的購物籃分析。
　　.數(shù)據(jù)挖掘算法［K-均值、K-近鄰（kNN）和樸素貝葉斯］。
　　.使用超大量基因組數(shù)據(jù)完成DNA測序和RNA測序。
　　. 樸素貝葉斯分類和馬爾可夫鏈實現(xiàn)數(shù)據(jù)和市場預測。
　　. 推薦算法和成對文檔相似性。
　　.線性回歸、Cox回歸和皮爾遜（Pearson）相關系數(shù)。
　　.等位基因頻率和DNA挖掘。
　　. 社交網(wǎng)絡分析（推薦系統(tǒng)、三角形計數(shù)，情感分析）。
　　你可以復制粘貼這本書中提供的解決方案，使用Hadoop 和Spark 構(gòu)建你自己的MapReduce 應用和解決方案。所有這些解決方案都經(jīng)過編譯和測試。如果你對Java 有一些了解（也就是說，可以讀寫基本的Java程序），想使用Java/Hadoop/Spark 編寫和部署MapReduce 算法，那么這本書是最適合不過的了。Jimmy Lin和Chris Dyer寫過一本好書[16]，其中對MapReduce 的一般內(nèi)容做了詳細討論。重申一次，這本書的目標是使用Hadoop 和Spark 提供具體的MapReduce 算法和解決方案。同樣地，這本書也不會詳細討論Hadoop 本身。這個內(nèi)容在Tom White 的書[31]中有詳細介紹，這也是一本絕妙的好書。
　　這本書不會介紹如何安裝Hadoop或Spark，這里假設你已經(jīng)安裝了這些框架。另外，所有Hadoop 命令都相對于Hadoop 的安裝目錄（$HADOOP_HOME 環(huán)境變量）執(zhí)行。這本書只展示使用MapReduce/Hadoop 和Spark的分布式算法。例如，我會討論API，介紹運行作業(yè)的命令行調(diào)用，另外會提供完整的實用程序（包括驅(qū)動器、映射器、組合器和歸約器）。
　　本書重點
　　這本書的重點是掌握MapReduce范式，并提出一些可以使用MapReduce/Hadoop 算法解決的具體問題。對于這里提出的每一個問題，我們會詳細介紹map() 、combine() 和reduce()函數(shù)，并提供完整的解決方案，包括：
　　. 客戶端，可以用適當?shù)妮斎牒洼敵鰠��?shù)調(diào)用驅(qū)動器。
　　.驅(qū)動器，明確map()和reduce()函數(shù)，并明確輸入和輸出。
　　.映射器類，實現(xiàn)map()函數(shù)。
　　.組合器類（如果需要），實現(xiàn)combine() 函數(shù)。我們會討論什么情況下有可能使用組合器。
　　.歸約器類，實現(xiàn)reduce()函數(shù)。
　　這本書的一個目標是提供一個循序漸進的指南，介紹如何使用Spark和Hadoop作為MapReduce算法的解決方案。另一個目標是展示如何將一個MapReduce作業(yè)的輸出作為另一個作業(yè)的輸入（這稱為MapReduce作業(yè)鏈或流水線）。
　　本書面向的讀者
　　這本書面向了解Java基礎知識并且想使用Hadoop和Spark 開發(fā)MapReduce 算法（數(shù)據(jù)挖掘、機器學習、生物信息技術、基因組和統(tǒng)計領域）和解決方案的軟件工程師、軟件架構(gòu)師、數(shù)據(jù)科學家和應用開發(fā)人員。前面已經(jīng)提到，這里假設你已經(jīng)了解Java 編程語言的基礎知識（例如，知道如何編寫類、由一個現(xiàn)有的類定義一個新類，以及使用while循環(huán)和if-then-else等基本控制結(jié)構(gòu)）。更具體地，這本書主要面向以下讀者：
　　.希望完成大數(shù)據(jù)分析（分類、回歸算法）的數(shù)據(jù)科學工程師和專業(yè)人員。這本書會采用一種實例的形式給出使用大數(shù)據(jù)應用分類和回歸算法的基本步驟。書中會詳細介紹map() 和reduce() 函數(shù)，展示如何將它們應用到實際數(shù)據(jù)，并說明在哪里應用基本設計模式來解決MapReduce 問題。對這些MapReduce 算法稍做修改就可以很容易地應用于其他行業(yè)（例如，修改輸入格式）。所有解決方案都已經(jīng)在Apache Hadoop/Spark 中實現(xiàn)，可以根據(jù)實際情況調(diào)整這些示例。
　　.希望設計機器學習算法（如樸素貝葉斯和馬爾可夫鏈算法）的軟件工程師和軟件架構(gòu)師。這本書會展示如何構(gòu)建模型，然后使用MapReduce 設計模式將模型應用到新的數(shù)據(jù)集。
　　.希望利用MapReduce使用數(shù)據(jù)挖掘算法（如K-均值聚類和k-近鄰算法）的軟件工程師和軟件架構(gòu)師。這里會給出詳細的示例，可以指導專業(yè)人員實現(xiàn)類似的算法。
　　.希望對生物醫(yī)療數(shù)據(jù)應用MapReduce算法（如DNA測序和RNA測序）的數(shù)據(jù)科學工程師。這本書會清楚地解釋生物信息學家和醫(yī)療人員可以采用的實用算法。這里提供了適用不同生物數(shù)據(jù)類型的主要回歸/分析算法。這些算法大多都已經(jīng)部署在實際的生產(chǎn)系統(tǒng)中。
　　.希望在MapReduce/分布式環(huán)境中應用最重要優(yōu)化的軟件架構(gòu)師。
　　在線資源
　　這本書有兩個配套網(wǎng)站：
　　https://github.com/mahmoudparsian/data-algorithms-book/ 在這個GitHub 網(wǎng)站上，可以找到源代碼（按章節(jié)組織）、shell 腳本（用于運行MapReduce/Hadoop 和Spark程序）、用于測試的示例輸入文件以及書中未涵蓋的一些額外內(nèi)容（包括附加的兩章）的相應鏈接。
　　http://mapreduce4hackers.com
　　在這個網(wǎng)站上可以找到額外的源文件（書中未提到）以及書中未涉及的另外一些內(nèi)容的鏈接。將來還會更全面地介紹MapReduce/Hadoop/Spark主題。
　　本書中使用的軟件
　　開發(fā)這本書中介紹的解決方案和示例時，我使用了表P-3列出的軟件和編程環(huán)境。表P-3：本書中使用的軟件/編程環(huán)境Java 編程語言 (JDK7) 1.7.0_67
　　操作系統(tǒng)：Linux CentOS 6.3
　　操作系統(tǒng)：Mac OS X 10.9
　　Apache Hadoop 2.5.0, 2.6.0
　　Apache Spark 1.1.0, 1.3.0, 1.4.0
　　Eclipse IDE Luna
　　這本書中的所有程序都使用Java/JDK7 、Hadoop 2.5.0 和Spark (1.1.0，1.3.0, 1.4.0)完成了測試。我們給出了不同操作系統(tǒng)環(huán)境（Linux和OS X）下的例子。對于所有示例和解決方案，我都使用了基本的文本編輯器（如vi、vim 和TextWrangler ），然后使用Java 命令行編譯器（javac）來完成編譯。
　　這本書中，我使用shell腳本（如bash腳本）來運行示例MapReduce/Hadoop 和Spark程序。以$或#字符開頭的代碼行表示必須在終端提示窗口（如bash）輸入這些命令。