醉染图书数据算法978751547

序1
前言3
章二次排序：简介19
二次排序问题解决方案21
MapReduce/Hadoop的二次排序解决方案25
Spark的二次排序解决方案29
第2章二次排序：详细示例42
二次排序技术43
二次排序的完整示例46
运行示例——老版本HadoopAPI50
运行示例——新版本HadoopAPI52
第3章0列表54
TopN设计模式的形式化描述55
MapReduce/Hadoop实现：键56
Spark实现：键62
Spark实现：非键73
使用takeOrdered()的Spark0解决方案84
MapReduce/Hadoop0解决方案：非键91
第4章左外连接96
左外连接示例96
MapReduce左外连接实现99
Spark左外连接实现105
使用leftOuterJoin()的Spark实现117
第5章反转排序127
反转排序模式示例128
反转排序模式的MapReduce/Hadoop实现129
运行示例134
第6章移动平均137
示例1：时间序列数据（价格）137
示例2：时间序列数据（URL访问数）138
形式定义139
POJO移动平均解决方案140
MapReduce/Hadoop移动平均解决方案143
第7章购物篮分析155
MBA目标155
MBA的应用领域157
使用MapReduce的购物篮分析157
Spark解决方案166
运行Spark实现的YARN脚本179
第8章共同好友182
输入183
POJO共同好友解决方案183
MapReduce算法184
解决方案1:使用文本的Hadoop实现187
解决方案2:使用ArrayListOfLongsWritable的Hadoop实现189
Spark解决方案191
第9章使用MapReduce实现引擎201
购买过该商品的顾客还购买了哪些商品202
经常一起购买的商品206
连接210
0章基于内容的电影225
输入226
MapReduce阶段1226
MapReduce阶段2和阶段3227
Spark电影实现4
1章使用马尔可夫模型的智能邮件营销.253
马尔可夫链基本原理254
使用MapReduce的马尔可夫模型256
Spark解决方案269
2章K-均值聚类282
什么是K-均值聚类?285
聚类的应用领域285
K-均值聚类方法非形式化描述：分区方法286
K-均值距离函数286
K-均值聚类形式化描述287
K-均值聚类的MapReduce解决方案288
K-均值算法Spark实现292
3章k-近邻296
kNN分类297
距离函数297
kNN示例298
kNN算法非形式化描述299
kNN算法形式化描述299
kNN的类Java非MapReduce解决方案299
Spark的kNN算法实现301
4章朴素贝叶斯315
训练和学习示例316
条件概率319
深入分析朴素贝叶斯分类器319
朴素贝叶斯分类器：符号数据的MapReduce解决方案322
朴素贝叶斯分类器Spark实现332
使用Spark和Mahout347
5章情感分析349
情感示例350
情感分数：正面或负面350
一个简单的MapReduce情感分析示例351
真实世界的情感分析353
6章查找、统计和列出大图中的所有三角形354
基本的图概念355
三角形的重要356
MapReduce/Hadoop解决方案357
Spark解决方案364
7章K-mer375
K-mer的输入数据376
K-mer应用376
K-merMapReduce/Hadoop解决方案377
K-merSpark解决方案378
8章DNA测序390
DNA测序的输入数据392
输入数据验393
DNA序列比对393
DNA测试的MapReduce算法394
9章Cox回归413
Cox模型剖析414
使用R的Cox回归415
Cox回归应用416
Cox回归POJO解决方案417
MapReduce输入418
使用MapReduce的Cox回归419
第20章Cochran-Armitage趋势检验426
Cochran-Armitage算法427
Cochran-Armitage应用432
MapReduce解决方案435
2章等位基因频率443
基本定义444
形式化问题描述448
等位基因频率分析的MapReduce解决方案449
MapReduce解决方案,阶段1449
MapReduce解决方案，阶段2459
MapReduce解决方案,阶段3463
染色体X和Y的特殊处理466
第22章T检验468
对bioset完成T检验469
MapReduce问题描述472
输入472
期望输出473
MapReduce解决方案473
Spark实现476
第章皮尔逊相关系数488
皮尔逊相关系数公式489
皮尔逊相关系数示例491
皮尔逊相关系数数据集492
皮尔逊相关系数POJO解决方案492
皮尔逊相关系数MapReduce解决方案493
皮尔逊相关系数的Spark解决方案496
运行Spark程序的YARN脚本516
使用Spark计算斯皮尔曼相关系数517
第24章DNA碱基520
FASTA格式521
FAST格式22
MapReduce解决方案：FASTA格式522
运行示例524
MapReduce解决方案:FAST格式28
Spark解决方案:FASTA格式533
Spark解决方案:FAST格式37
第25章RNA测序543
数据大小和格式543
MapReduce工作流544
RNA测序分析概述544
RNA测序MapReduce算法548
第26章基因聚合553
输入554
输出554
MapReduce解决方案（按单个值过滤和按平均值过滤）555
基因聚合的Spark解决方案567
Spark解决方案：按单个值过滤567
Spark解决方案：按平均值过滤576
第27章线回归586
基本定义587
简单示例587
问题描述588
输入数据589
期望输出590
使用SimpleRegression的MapReduce解决方案590
Hadoop实现类593
使用R线模型的MapReduce解决方案593
第28章MapReduce和幺半群600
概述600
幺半群的定义602
幺半群和非幺半群示例603
MapReduce示例：非幺半群606
MapReduce示例：幺半群608
使用幺半的Sark示例612
使用幺半群的结论618
函子和幺半群619
第29章小文件问题622
解决方案1：在客户端合并小文件6
解决方案2：用CombineFileInputFormat解决小文件问题629
解决方案634
第30章MapReduce的大容量缓存635
实现方案636
缓存问题形式化描述637
一个精巧、可伸缩的解决方案637
实现LRUMap缓存640
使用LRUMap的MapReduce解决方案646
3章Bloom过滤器651Bloom
过滤器质651
一个简单的Bloom过滤器示例653
Guava库中的Bloom过滤器654
MapReduce中使用Bloom过滤器655
附录ABioset659
附录BSparkRDD659
参考书目677

Mahmoud Parsian，计算机科学博士，是一位热衷于实践的软件专家，作为开发人员、设计人员、架构师和作者，他有30多年的软件开发经验。目前领导着Illumina的大数据团队，在过去15年间，他主要从事Java(服务器端)、数据库、MapReduce和分布式计算的有关工作。Mahmoud还著有《JDBC Recipes》和《JDBC Metadata，MySL，and Oracle Recipes》等书（均由Apress出版）。

随着大规模搜索引擎（如Google和Yahoo! ）、基因组分析（DNA测序、RNA测序和生物标志物分析）以及社交网络（如Facebook 和Twitter) 的不断发展，需要生成和处理的数据量已经超过了千万亿字节。为了满足如此庞大的计算需求，我们需高效、可伸缩的并行算法。MapReduce范式就是解决这些问题的一个框架。
MapReduce是一个软件框架，可以采用并行、分布式方式处理GB、TB，甚至PB级的大数据集，同时它也是一个在商用服务器集群之上完成大规模数据处理的执行框架。实现MapReduce 的方法有很多，不

过这本书中我们主要关注Apache Spark 和MapReduce/ Hadoop。你将通过简单而具体的示例来了解如何用Spark和Hadoop实现MapReduce。
这本书将为以下领域提供了基本分布式算法（分别用MapReduce、Hadoop和Spark实现），并按照这些领域组织本书的章节：
. 基本设计模式。

. 数据挖掘和机器学习。

. 生物信息、基因组和统计。

. 优化技术。


MapReduce是什么？
MapReduce 是一种编程范式，可以利用集群环境的成百上千台服务器实现强大的可伸缩。MapReduce一词早源于函数式编程，由Google在一篇名为“MapReduce: Simplified Data Processing on

Large Clusters ”的文章中率先提出。Google的MapReduce[8]实现是一个专用解决方案，还没有向公众发布。
3



reduce():.(Key2,.[Value2]).→.[(Key3,.Value3)]

这本书中会使用map() 函数和reduce() 函数的非形式化表示，我会用中括号（[]）表示列表。
在图P-1中，输入数据划分为小块（这里有5个输入分区），每个小块分别发送给一个映器。各个映器会生成任意数目的键-值对。映器的输出如表P-1所示。
表P-1：映器的输出


K1  V11
K2  V21
K1  V12
K2  V22
K2  V

在这个例子中，所有映器只生成两个的键：K1, K2。所有映器的工作完成时，这些键会经过排序、洗牌、分组，然后发送给归约器。，归约器将生成所需的输出。对于这个例子，我们

有两个归约器，分别用K1, K2键标识（见表P-2）。
表P-2：归约器的输入
键值
K1 V11, V12 K2 V21, V22, V
一旦所有映器的工作完成，归约器就会开始它们的执行过程。每个归约器创建的输出可以包含任意数目的新键-值对（可以0个，也可以多个）。
编写map() 函数和reduce() 函数时，要确保解决方案是可伸缩的。例如，如果使用了某种数据结构（如List、Array或HashMap），而这种数据结构不能方便地存放在商用服务器的内存中，这个解决方

案就不具有可伸缩。需要说明，map() 和reduce() 函数都在基础的商用服务器中执行，这些商用服务器可能至多有32GB 或64GB RAM （注意，这只是一个例子。如今的服务器可能已经有256GB 或

512GB RAM ，接下来几年中基础服务器可能甚至有1TB 的RAM）。因此，可伸缩是MapReduce的核心。如果你的MapReduce解决方案不能很好的伸缩，就不能称为一个MapReduce 解决方案。在这里，我

们谈到可伸缩时，是指“横向扩容”（scaling out ），横向扩容表示在系统中增加更多商用节点。MapReduce 主要考虑横向扩容（而不是纵向扩容（scaling up ），这表示为单个节点增加
前言｜ 5

资源，比如内存和CPU）。例如，如果DNA测序需要3台服务器用60小时完成，横向扩容到50台类似的服务器时，可以在不到2小时的时间内完成同样的DNA测序。
MapReduce 的核心概念是将输入数据集映到个键-值对集合，然后对所有包含相同键的键-值对完成归约。尽管基本概念很简单，不过如果考虑以下方面，可以看到这个概念确实很强大、很有效：
.几乎所有数据都可以映到键-值对。

.键和值可以是任意类型：String、Integer、FAST （用于DNA测序）、用户自定义的定制类型，当然，也可以是键-值对本身。


MapReduce如何在一组服务器上扩展？MapReduce是如何工作的？关键在于，从概念上讲，MapReduce 的输入是一个记录列表（每个记录可以是一行或多行数据）。这些输入记录会划分并传递到集群中

的多台服务器，由map() 函数使用。map() 计算的结果是一个键-值对列表。然后reduce() 函数取各个包含相同键的值集，将它们分别组合为一个值（或一个值集）。换句话说，map() 函数是由一组

数据块生成键-值对，reduce() 则是组合map()生成的数据输出，从而能得到所需要的结果，而不是一组键-值对。
MapReduce 的主要优点之一是它的“不共享”（shared-nothing ）数据处理平台。这意味着所有映器可以独立地工作，而且映器完成它们的任务时，归约器也能独立地开始工作（映器或归约器

之间不共享任何数据或临界区。如果有临界区，这会减慢分布式计算的速度）。基于这种“不共享”范式，我们可以很容易地编写map() 函数和reduce() 函数，而且能轻松、有效地提高并行。
MapReduce的简单解释
如何给出MapReduce 的一个简单解释？设我们想要统计一个图书馆的藏书数量，这个图书馆拥有1000个书架，我们要把的结果报告给图书管理员。下面给出两种可能的MapReduce解决方案：
.方案1（使用map()和reduce()）：─map():.聘请1000个工人；每个工人统计一个书架的藏书数量。

─reduce(): 所有工人集合在一起，把他们各自的统计结果汇总起来（向图书管理员报告他们的统计结果）。

.方案2 （使用map(),.combine()和reduce()）：─map(): 聘请1110 个员工（1000名工人，100位经理，10位主管（每位主管负责管理10个经理，每个经理要管理10名工人）；每个工人负责统计一个

书架，将结果报告给他的经理。


─combine(): 每个主管负责的10个经理将各自的统计结果汇总报告给这位主管。─reduce(): 所有主管集合起来，把他们各自的统计结果汇总起来（向图书管理员报告他们的统计结果）。
什么时候使用MapReduce
MapReduce 永远适用吗？定的。设我们得到了大数据，如果可以划分这个数据，每个分区能独立地进行处理，就可以考虑使用MapReduce 算法。例如，由于图算法采用迭代方法，所以

MapReduce并不是很适合。不过，如果要对大量数据完成分组或聚集，MapReduce范式就适用。要想使用MapReduce来处理图，可以考虑Apache Giraph（http://giraph.apache.org/ ）和Apache

Spark GraphX（https://spark.apache.org/ graphx/）项目。
下面这些情况也不适合使用MapReduce：
. 一个值的计算依赖于之前计算的值。比如，斐波那契数列就是一个很好的例子，其中每个值都是前两个值之和：
F(k.+.2).=.F(k.+.1).+.F(k)
.数据集很小，完全可以在一台机器上计算。这种情况下，作为一个reduce(map(data))操作来完成，而不需要经过整个MapReduce执行过程。

. 需要同步来处理共享数据。

. 所有输入数据都可以放在内存中。

. 一个操作依赖操作。

. 基本计算是处理器型操作。

不过，很多情况下MapReduce都很适用，如：

. 必须处理大量输入数据（例如，对大量数据完成聚集或计算统计结果）。

. 需要利用并行分布式计算、数据存储和数据本地化。

. 可以独立地完成很多任务而无需同步。

. 可以利用排序和洗牌。

. 需要容错，不能接受作业失败。


MapReduce不是什么
MapReduce是实现分布式计算的一项开创技术，不过这个技术还蒙着很多神秘的面纱，这里就来揭开它的一些面纱：

.MapReduce 不是一个编程语言，而是一个框架，可以使用Java 、Scala 和编程语言在这个框架上开发分布式应用。

.MapReduce的分布式文件系统不能取代关系型数据库管理系统（如MySL 或Oracle ）。一般地，MapReduce 的输入是纯文本文件（一个映器输入记录可以有一行或多行）。

.MapReduce 框架主要设计用于批处理，所以不要期望能够在几秒钟内迅速得到结果。不过，如果适当地使用集群，确实可以得到近实时的响应。

.并不能把MapReduce作为所有软件问题的解决方案。


为什么使用MapReduce?
前面我们讨论过，MapReduce 的目标是通过增加更多的商用服务器来实现“横向扩容”。这与“纵向扩容”是不同的（纵向扩容是为系统中的单个节点增加更多资源，如内存和CPU）。纵向扩容可能成

本很高，有时由于成本以及软件或硬件限制等原因，可能根本无法增加更多的资源。有时人们会提出一些基于主存的新兴算法来解决数据问题，但是由于主存是一个瓶颈，所以这些算法缺乏可伸缩

。例如，在DNA测序分析中，可能需要超过512GB的RAM，这昂贵，而且不具有可伸缩。
如果要提高计算能力，可能需要把计算分布到多个机器上完成。例如，要完成500GB 样本数据的DNA测序，可能需要一个服务器计算4天才能完成比对阶段。利用MapReduce，60 台服务器可以把计算时

间锐减到2小时以内。要处理大量的数据，必须能够将这些数据划分为小块来进行处理，再组合得到的结果。MapReduce/Hadoop 和Spark/Hadoop 可以帮你提高计算能力，你只需要写两个函数：

map() 和reduce() 。显然，MapReduce 范式为数据分析领域提供了一个强大的新工具，近来，归功于Hadoop 等开源解决方案，这个新工具得到了越来越多的关注。
基本说来，MapReduce提供了以下优点：
.编程模型+基础架构。

. 能够编写在数百甚至上千台机器上运行的程序。

. 自动并行化和分布

. 容错（如果一台服务器宕机，作业可以由服务器完成）。

.程序/作业调度、状态检查和监控。


Hadoop和Spark
Hadoop（http://hadoop.apache.org/ ）是MapReduce应用实现的事实标准。它由一个或多个主节点和任意多个从节点组成。Hadoop提出“数据中心就是计算机”，通过提供map() 函数和reduce() 函

数（由程序员定义），允许应用开发人员或程序员利用这些数据中心，从而简化分布式应用。Hadoop 高效地实现了MapReduce 范式，很容易学习，这是一个可以处理TB甚至PB级大数据的强大工具。
在这本书中，大部分MapReduce 算法都采用实例的形式给出（已编译的完整实用解决方案），并且在Java/MapReduce/Hadoop 和/或Java/Spark/Hadoop 中得到实现。Hadoop和Spark

（http://spark.apache.org/ ）框架是开源的，允许我们在分布式环境中完成大数据量的算和据处理。
这些框架通过提供“横向扩容”方法来支持可伸缩，可以采用MapReduce 范式在数千台服务器上运行密集型计算。与Hadoop的API相比，Spark的API提供了更高层的抽象。由于这个原因，只用一个

Java驱动器类就可以描述Spark解决方案。
Hadoop和Spark是两个不同的分布式软件框架。Hadoop是一个MapReduce框架，在这个框架上可以运行支持map() 、combine() 和reduce() 函数的作业。MapReduce范式很适合单趟计算［先map() ，再

reduce() ］，不过对于多趟算法效率则很低。Spark 不是一个MapReduce框架，不过很容易用来支持MapReduce框架的功能，它提供了一个适当的API 可以处理map() 和reduce() 功能。Spark并不限于

先完成映阶段再完成归约阶段。Spark 作业可以是由映和/或归约/洗牌阶段构成的一个任意DAG（有向无环图）。Spark程序可以使用Hadoop运行，也可以不使用Hadoop，另外Spark可以使用Hadoop

分布式文件系统（Hadoop Distributed File System，HDFS）或者持久存储来实现输入/输出。基本上，对于一个给定的Spark程序或作业，Spark引擎会创建将在集群上完成的任务阶段所构成的一

个有向无环图，Hadoop/MapReduce 则不同，它会创建由两个预定义阶段（映和归约）构成的有向无环图。注意，Spark创建的DAG可以包含任意多个阶段。与Hadoop/ MapReduce相比，这使得大多数

Spark作业都能更快地完成，因为简单的作业只需要一个阶段就可以完成，更复杂的任务也可以一起完成（包括多个阶段），而不需要划分为多个作业。前面已经提到，相比于MapReduce/Hadoop，

Spark的API提供了更高层的抽象。例如，Spark的几行代码可能等价于MapReduce/Hadoop的30～40行代码。
尽管Hadoop和Spark等框架建立一个“不共享”范式基础之上，不过它们确实也支持在所有集群节点上共享不可变的数据结构。在Hadoop中，可以通过Hadoop的Configuration对象将这些值传递给映

器和归约器。除了Broadcast只读对象，Spark还支持只写累加器。Hadoop和Spark为大数据处理提供了以下好处：
可读
Hadoop和Spark支持容错（任何节点宕机不会丢失所需的计算结果）。可伸缩
Hadoop和Spark支持庞大的服务器集群。


分布式处理
在Spark和Hadoop中，输入数据和处理是分布式的（可以全面支持大数据）。并行化
可以在节点集群上并行地执行计算。
Hadoop 主要设计用于批处理，不过如果有足够的内存/RAM，Spark 可以用于近实时处理。要了解Spark RDDs（resilient distributed data sets，弹分布式数据集）的基本用法，可以参考附录B。
那么MapReduce/Hadoop的核心组件有哪些？
.输入/输出数据包括键-值对。一般地，键是整型、长整型和字符串，而值可以是几乎任何数据类型（字符串、整型、长整型、句子、特殊格式的数据等）。

. 数据划分到商用节点上，填充到数据中心。

.这个软件会处理故障、重启和意外中断。这称为容错（fault tolerance），这也是Hadoop的一个重要特。


Hadoop和Spark不只是提供了map() 和reduce() 功能，还提供了插件模型来实现定制记录读取、二次数据排序及更多功能。
图P-2展示了Spark、YARN 和Hadoop HDFS之间关系的一个高层视图。

图P-2：MapReduce、Spark和HDFS之间的关系
从这个关系可以看到，使用HDFS （和非HDFS文件系统）运行MapReduce和Spark有很多方法。在这本书中，我会用到以下关键词和术语：
.MapReduce表示一般的MapReduce框架范式。

.MapReduce/Hadoop表示使用Hadoop的一个特定的MapReduce框架实现。

.Spark 表示一个特定的Spark实现，它使用HDFS 作为持久存储或计算引擎（注意，Spark可以在任何数据存储库上运行，不过这里我们主要强调Hadoop的HDFS）：

─Spark 可以脱离Hadoop 使用独立的集群节点运行（可以使用HDFS、NFS或媒介作为持久数据存储库）。─Spark也可以结合Hadoop，使用Hadoop的YARN 或MapReduce框架运行。
通过这本书，你会循序渐进地学习使用Hadoop 构建MapReduce 应用所需的算法和工具。MapReduce/Hadoop 已经成为处理大数据集（如日志数据、基因组序列、统计应用和社交图谱）的理想编程模型

。MapReduce 可以用于任何不需要紧耦合并行处理的应用。要记住，Hadoop主要设计用于MapReduce批处理，它并不是一个理想的实时处理解决方案。不要期望在2～5s时间内从Hadoop得到，

的作业也可能需要超过20s的时间。Spark是一个很好Apache项目，适合近实时处理，如果有更多的RAM，它的表现将会更出色。利用Spark ，如果使用一个包括100个节点的集群运行一个大数据处

理作业（如生物标志物分析或Cox回归），完全有可能在25～35s内处理2亿条记录。一般地，Hadoop作业会有15～20s的延迟，不过这取决于Hadoop集群的大小和配置。
MapReduce 实现（如Hadoop ）可以在一个庞大的商用计算机集群上运行，具有很好的可伸缩。例如，一个典型的MapReduce计算过程可以在数百或数千台机器上处理PB或TB 级的数据。程序员会发现

，MapReduce 很容易使用，因为它隐藏了并行化、容错、数据分布和负载平衡等繁杂的细节，使程序员可以集中精力编写两个关键函数map() 和reduce()。
下面是MapReduce/Hadoop/Spark的一些主要应用：
. 查询日志处理。

. 抓取、索引和搜索。

. 分析、文本处理情感分析。

. 机器学习（如马尔可夫链和朴素贝叶斯分类器）。

. 系统。

. 文档聚类和分类。

. 生物信息学（比对、重新校准、生殖细胞采集和DNA/RNA测序）。

. 基因组分析（生物标志物分析以及回归算法，如线回归和Cox回归）。


本书内容
这本书中每一章分别提出一个问题，然后通过一组MapReduce算法加以解决。MapReduce 算法/解决方案相当完整（包括MapReduce驱动器、映器、组合器和归约器程序）。可以在项目中直接使用这些

代码（不过，有时可能需要剪切粘贴你需要的部分）。这本书
前言｜ 11


没有涉及MapReduce 框架的底层理论，而是着重于提供使用MapReduce/Hadoop 和Spark 解决大数据难题的实用算法和示例。这本书的主要内容包括：
. 完成超大量交易的购物篮分析。

.数据挖掘算法［K-均值、K-近邻（kNN）和朴素贝叶斯］。

.使用超大量基因组数据完成DNA测序和RNA测序。

. 朴素贝叶斯分类和马尔可夫链实现数据和市场预测。

. 算法和成对文档相似。

.线回归、Cox回归和皮尔逊（Pearson）相关系数。

.等位基因频率和DNA挖掘。

. 社交网络分析（系统、三角形，情感分析）。


你可以复制粘贴这本书提的解决方案，使用Hadoop 和Spark 构建你自己的MapReduce 应用和解决方案。所有这些解决方案都经过编译和测试。如果你对Java 有一些了解（也就是说，可以读写基

本的Java程序），想使用Java/Hadoop/Spark 编写和部署MapReduce 算法，那么这本书是不过的了。Jimmy Lin和Chris Dyer写过一本好书[16]，其中对MapReduce 的一般内容做了详细讨论。重

申一次，这本书的目标是使用Hadoop 和Spark 提供具体的MapReduce 算法和解决方案。同样地，这本书也不会详细讨论Hadoop 本身。这个内容在Tom White 的书[31]中有详细介绍，这也是一本绝妙

的好书。
这本书不会介绍如何安装Hadoop或Spark，这里设你已经安装了这些框架。另外，所有Hadoop 命令都相对于Hadoop 的安装目录（$HADOOP_HOME 环境变量）执行。这本书只展示使用

MapReduce/Hadoop 和Spark的分布式算法。例如，我会讨论API，介绍运行作业的命令行调用，另外会提供完整的实用程序（包括驱动器、映器、组合器和归约器）。
本书重点
这本书的重点是掌握MapReduce范式，并提出一些可以使用MapReduce/Hadoop 算法解决的具体问题。对于这里提出的每一个问题，我们会详细介绍map() 、combine() 和reduce()函数，并提供完整的

解决方案，包括：
. 客户端，可以用适当的输入和输出参数调用驱动器。

.驱动器，明确map()和reduce()函数，并明确输入和输出。

.映器类，实现map()函数。

.组合器类（如果需要），实现combine() 函数。我们会讨论什么情况下有可能使用组合器。

.归约器类，实现reduce()函数。
这本书的一个目标是提供一个循序渐进的指南，介绍如何使用Spark和Hadoop作为MapReduce算法的解决方案。另一个目标是展示如何将一个MapReduce作业的输出作为另一个作业的输入（这称为

MapReduce作业链或流水线）。
本书面向的读者
这本书面向了解Java基础知识并且想使用Hadoop和Spark 开发MapReduce 算法（数据挖掘、机器学习、生物信息技术、基因组和统计领域）和解决方案的软件、软件架构师、数据科学家和应用

开发人员。前面已经提到，这里设你已经了解Java 编程语言的基础知识（例如，知道如何编写类、由一个现有的类定义一个新类，以及使用while循环和if-then-else等基本控制结构）。
更具体地，这本书主要面向以下读者：
.希望完成大数据分析（分类、回归算法）的数据科学和专业人员。这本书会采用一种实例的形式给出使用大数据应用分类和回归算法的基本步骤。书中会详细介绍map() 和reduce() 函数，展

示如何将它们应用到实际数据，并说明在哪里应用基本设计模式来解决MapReduce 问题。对这些MapReduce 算法稍做修改就可以很容易地应用于行业（例如，修改输入格式）。所有解决方案都已

经在Apache Hadoop/Spark 中实现，可以根据实际情况调整这些示例。

.希望设计机器学习算法（如朴素贝叶斯和马尔可夫链算法）的软件和软件架构师。这本书会展示如何构建模型，然后使用MapReduce 设计模式将模型应用到新的数据集。

.希望利用MapReduce使用数据挖掘算法（如K-均值聚类和k-近邻算法）的软件和软件架构师。这里会给出详细的示例，可以指导专业人员实现类似的算法。

.希望对生物医疗数据应用MapReduce算法（如DNA测序和RNA测序）的数据科学。这本书会清楚地解释生物信息学家和医疗人员可以采用的实用算法。这里提供了适用不同生物数据类型的主要回

归/分析算法。这些算法大多都已经部署在实际的生产系统中。

.希望在MapReduce/分布式环境中应用重要化的软件架构师。


这本书设你已经对Java和Hadoop HDFS 有基本的了解。如果需要进一步熟悉Hadoop和Spark，下面这些书可以提供你需要的背景知识：
.Hadoop: The Definitive Guide，Tom White 著 (O’Reilly)

.Hadoop in Action，Chuck Lam著 (Manning Publications)

.Hadoop in Practice，Alex Holmes著 (Manning Publications)

.Learning Spark，Holden Karau, Andy Konwinski, Patrick Wendell 和Matei Zaharia 著(O’Reilly)


在线资源
这本书有两个配套：
https://itu.com/mahmoudparsian/data-algorithms-book/ 在这个GitHub 上，可以找到源代码（按章节组织）、shell 脚本（用于运行MapReduce/Hadoop 和Spark程序）、用于测试的示例输

入文件以及书中未涵盖的一些额外内容（包括附加的两章）的相应链接。
http://mapreduce4hackers.com
在这个上可以找到额外的源文件（书中未提到）以及书中未涉及的另外一些内容的链接。将来还会更全面地介绍MapReduce/Hadoop/Spark主题。
本书中使用的软件
开发这本书中介绍的解决方案和示例时，我使用了表P-3列出的软件和编程环境。
表P-3：本书中使用的软件/编程环境

Java 编程语言 (JDK7)  1.7.0_67
操作系统：Linux CentOS  6.3
操作系统：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 E  Luna

这本书中的所有程序都使用Java/JDK7 、Hadoop 2.5.0 和Spark (1.1.0，1.3.0, 1.4.0)完成了测试。我们给出了不同操作系统环境（Linux和OS X）下的例子。对于所有示例和解决方案，我都使用了

基本的文本编辑器（如、m 和TextWrangler ），然后使用Java 命令行编译器（javac）来完成编译。
这本书中，我使用shell脚本（如bash脚本）来运行示例MapReduce/Hadoop 和Spark程序。以$或#字符开头的代码行表示必须在终端提示窗口（如bash）输入这些命令。

本书使用约定
以下是本书中使用的排版约定：
斜体（Italic）指示新术语、URL、email地址、文件名和文件扩展名。
等宽字体（Constant.width）用于程序代码清单，以及在段落中用来指示程序元素，如变量或函数名、数据库、数据类型、环境变量、语句和关键字。

这表示一个一般说明。
使用代码示例
前面已经提到，可以从以下网址下载补充材料（包括代码示例、练习等），https://itu. com/mahmoudparsian/data-algorithms-book/和http://www.mapreduce4hackers.com 。
这本书的目的就是要帮你完成实际工作。一般来讲，如果本书提供了示例代码，完全可以在你的程序和文档中使用这些代码，不需要联系我们来得到许可，除非你直接复制了大部分的代码。例如，

如果你在编写一个程序，使用了本书中的多段代码，这并不需要得到许可。但是出售或发行O’Reilly 示例代码光盘则需要得到许可。回答问题时如果引用了这本书的文字和示例代码，这不需要得到

许可。但是如果你的产品的文档借用了本书中的大量示例代码，则需要得到许可。
我们希望但不严格要求标明引用出处。引用信息通常包括书名、作者、出版商和ISBN。例如，“Data Algorithms by Mahmoud Parsian (O’Reilly). Copyright 2015 Mahmoud Parsian, 978-1-491-

90618-7”。
如果你认为在使用代码示例时超出了合理使用范围或者上述许可范围，可以随时联系我们：permissions@oreilly.com 。
Safari.图书在线
Safari图书在线（www.safaribooksonline.com ）是一个应需而变的数字图书馆，通过图书和视频方式提供世界作者在技术和商业领域积累的专家经验。技术专家、软件开发人员、Web 设计人员

和企业以及有创意的专业人员都使用Safari 图书在线作为其主要资源来完成研究、解决问题、深入学习和资质培训。
Safari图书在线为机构、部门和个人提供了多种产品组合和定价程序。
订阅者可以在一个可以快捷搜索的数据库中访问多家出版社提供的成千上万种图书、培训视频和正式出版前手稿，如O’Reilly Media 、Prentice Hall Professional 、Addison-Wesley

Professional 、Microsoft Press 、Sams 、e、Peachpit Press 、Focal Press 、Cisco Press 、John Wiley & Sons 、Syngress 、Morgan Kaufmann 、IBM Redbooks 、Packt 、Adobe Press、

FT Press 、Apress、Manning、New Riders 、McGraw-Hill 、Jones & Bartlett 、Course Technology 以及数十家出版公司。关于Safari图书在线的更多信息，请访问我们的在线。
如何联系我们
美国：
O’Reilly Media，Inc.
1005 Gravenstein Highway North
Sebastopol，CA 95472
中国：
北京市西城区西直门南大街2 号成铭大厦C 座807 室（100035）
奥莱利技术咨询（北京）有限公司
我们为本书提供了网页，该网页上面列出了勘误表、范例和任何附加的信息。您可以访问如下网页获得：
http://oreil.ly/data_algorithms
要询问技术问题或对本书提出建议，请发送邮件至：
bookquestions@oreilly.com
要获得更多关于我们的书籍、会议、资源中心和O’Reilly 网络的信息，请参见我们的：
http://www.oreilly.com.cn
http://www.oreilly.com


致谢
致各位读者：感谢你们读这本书。衷心希望这本书对你有用，能为你提供帮。
感谢我的O’Reilly编辑Ann Spencer ，感谢你在这个图书项目中对我的信任，重新组织章节时提供的莫大支持，还要感谢对这个新书名的建议（原先我的书名是《MapReduce for Hackers》）。另外

，还要感谢Mike Loukides（O’Reilly Media 内容策略部副总裁）对这个项目的信任和支持。
此外，感谢我的编辑Marie Beaugureau ，作为O’Reilly的数据和开发编辑，长久以来他一直耐心地与我共同战斗，在这个项目的每个阶段都无私地支持着我。Marie 的意见和建议有用，也

很有建设。
还要特别感谢我的文字编辑Rachel Monaghan ，感谢她在图书编辑方面的卓越见识和极为中肯的意见和建议。正是因为有她，这本书才更为通俗易懂。另外，还要感谢产品编辑Matthew Hacker ，因为

他出色的工作，这本书才得以顺利制作发行。感谢Rebecca Demarest（O’Reilly 绘图）和Dan Fauxsmith （O’Reilly 发行服务主管）对这本书的美化。另外，我还要感谢Rachel Head（校对）、

Judith McConville（索引）、David Futato （内文设计）和Ellie Volckhausen （封面设计）。
感谢我的技术审校Cody Koeninger 、Kun Lu 、Neera Vats 、Dr. Phanendra Babu 、Willy Bruns和Mohan Reddy 。你们的意见中肯，我尽可能地采纳了你们的建议。特别感谢Cody提供的详细反

馈。
特别要感谢Jay Flatley（Illumina首席执行官），你提供了一个无与伦比的机会和环境来解开基因组的奥秘。感谢我亲爱的朋友Saeid Akhtari（NextBio 首席执行官）和Satnam Alag博士（Illumina

工程部副总裁），感谢你们过去5年对我的信任和支持。
感谢我永远的朋友Ramachandran Krishnaswamy 博士（我的博士导师），感谢他悉心的指导和为我的计算机科学研究工作提供的良好环境。
感谢我的父母（妈妈Monireh Azemoun 和爸爸Bagher Parsian ）把教育当作他们的要务。感谢他们一直以来的默默支持。感谢我的哥哥Ahmad Parsian 博士帮我理解数学要义。感谢我的妹妹

Nayer Azam Parsian 让我体会到友爱和关怀。
，但绝不是不重要，要感谢我亲爱的家人（Behnaz、Maral 和Yaseen ）在写这本书的过程中，你们的鼓励和支持对我的意义无以言表。
对本书的建议和问题
如果你对这本书中描述的问题和解决方案有想法，我乐于收到有关的反馈和建议。