深入理解大数据：大数据处理与编程实践

1.3.1　MapReduce的基本概念和由来 25
1.3.2　MapReduce的基本设计思想 26
1.3.3　MapReduce的主要功能和技术特征 28
1.4　Hadoop系统简介 30
1.4.1　Hadoop的概述与发展历史 30
1.4.2　Hadoop系统分布式存储与并行计算构架 31
1.4.3　Hadoop平台的基本组成与生态系统 33
1.4.4　Hadoop的应用现状和发展趋势 37
第2章　Hadoop系统的安装与操作管理 39
2.1　Hadoop系统安装方法简介 39
2.2　单机和单机伪分布式Hadoop系统安装基本步骤 39
2.2.1　安装和配置JDK 40
2.2.2　创建Hadoop用户 40
2.2.3　下载安装Hadoop 40
2.2.4　配置SSH 41
2.2.5　配置Hadoop环境 42
2.2.6　Hadoop的运行 43
2.2.7　运行测试程序 43
2.2.8　查看集群状态 44
2.3　集群分布式Hadoop系统安装基本步骤 44
2.3.1　安装和配置JDK 44
2.3.2　创建Hadoop用户 45
2.3.3　下载安装Hadoop 45
2.3.4　配置SSH 45
2.3.5　配置Hadoop环境 46
2.3.6　Hadoop的运行 48
2.3.7　运行测试程序 48
2.3.8　查看集群状态 49
2.4　Hadoop MapReduce程序开发过程 49
2.5　集群远程作业提交与执行 53
2.5.1　集群远程作业提交和执行过程 53
2.5.2　查看作业执行结果和集群状态 53
第3章　大数据存储——分布式文件系统HDFS 56
3.1　HDFS的基本特征与构架 56
3.1.1　HDFS的基本特征 57
3.1.2　HDFS的基本框架与工作过程 57
3.2　HDFS可靠性设计 60
3.2.1　HDFS数据块多副本存储设计 60
3.2.2　HDFS可靠性的设计实现 61
3.3　HDFS文件存储组织与读写 63
3.3.1　文件数据的存储组织 63
3.3.2　数据的读写过程 65
3.4　HDFS文件系统操作命令 68
3.4.1　HDFS启动与关闭 68
3.4.2　HDFS文件操作命令格式与注意事项 69
3.4.3　HDFS文件操作命令 69
3.4.4　高级操作命令和工具 77
3.5　HDFS基本编程接口与示例 83
3.5.1　HDFS编程基础知识 83
3.5.2　HDFS基本文件操作API 84
3.5.3　HDFS基本编程实例 87
第4章　Hadoop MapReduce并行编程框架 91
4.1　MapReduce基本编程模型和框架 91
4.1.1　MapReduce并行编程抽象模型 91
4.1.2　MapReduce的完整编程模型和框架 93
4.2　Hadoop MapReduce基本构架与工作过程 96
4.2.1　Hadoop系统构架和MapReduce程序执行过程 96
4.2.2　Hadoop MapReduce执行框架和作业执行流程 98
4.2.3　Hadoop MapReduce作业调度过程和调度方法 102
4.2.4　MapReduce执行框架的组件和执行流程 106
4.3　Hadoop MapReduce主要组件与编程接口 107
4.3.1　数据输入格式InputFormat 107
4.3.2　输入数据分块InputSplit 109
4.3.3　数据记录读入RecordReader 110
4.3.4　Mapper类 112
4.3.5　Combiner 114
4.3.6　Partitioner 115
4.3.7　Sort 116
4.3.8　Reducer类 119
4.3.9　数据输出格式OutputFormat 120
4.3.10　数据记录输出RecordWriter 122
第5章　分布式数据库HBase 123
5.1　HBase简介 123
5.1.1　为什么需要NoSQL数据库 123
5.1.2　HBase的作用和功能特点 125
5.2　HBase的数据模型 126
5.2.1　HBase的基本数据模型 126
5.2.2　HBase的查询模式 128
5.2.3　HBase表设计 129
5.3　HBase的基本构架与数据存储管理方法 132
5.3.1　HBase在Hadoop生态中的位置和关系 132
5.3.2　HBase的基本组成结构 133
5.3.3　HBase Region 133
5.3.4　Region Server 135
5.3.5　HBase的总体组成结构 138
5.3.6　HBase的寻址和定位 139
5.3.7　HBase节点的上下线管理 142
5.4　HBase安装与操作 145
5.4.1　安装一个单机版的HBase 145
5.4.2　HBase Shell操作命令 146
5.4.3　基于集群的HBase安装和配置 149
5.5　HBase的编程接口和编程示例 152
5.5.1　表创建编程接口与示例 152
5.5.2　表数据更新编程接口与示例 153
5.5.3　数据读取编程接口与示例 155
5.5.4　HBase MapReduce支持和编程示例 157
5.6　HBase的读写操作和特性 161
5.6.1　HBase的数据写入 161
5.6.2　HBase的数据读取 171
5.7　其他HBase功能 173
5.7.1　Coprocessor 173
5.7.2　批量数据导入Bulk Load 176
第6章　分布式数据仓库Hive 179
6.1　Hive的作用与结构组成 179
6.2　Hive的数据模型 181
6.2.1　Hive的数据存储模型 181
6.2.2　Hive的元数据存储管理 182
6.2.3　Hive的数据类型 183
6.3　Hive的安装 184
6.3.1　下载Hive安装包 184
6.3.2　配置环境变量 184
6.3.3　创建Hive数据文件目录 185
6.3.4　修改Hive配置文件 185
6.4　Hive查询语言——HiveQL 188
6.4.1　DDL语句 188
6.4.2　DML语句 189
6.4.3　SELECT查询语句 190
6.4.4　数据表操作语句示例 190
6.4.5　分区的使用 192
6.4.6　桶的使用 193
6.4.7　子查询 194
6.4.8　Hive的优化和高级功能 194
6.5　Hive JDBC编程接口与程序设计 196
第7章　Intel Hadoop系统优化与功能增强 200
7.1　Intel Hadoop系统简介 200
7.1.1　Intel Hadoop系统的主要优化和增强功能 200
7.1.2　Intel Hadoop的系统构成与组件 201
7.2　Intel Hadoop系统的安装和管理 202
7.3　Intel Hadoop HDFS的优化和功能扩展 202
7.3.1　HDFS的高可用性 203
7.3.2　Intel Hadoop系统高可用性配置服务 204
7.3.3　Intel Hadoop系统高可用性配置服务操作 206
7.3.4　自适应数据块副本调整策略 208
7.4　Intel Hadoop HBase的功能扩展和编程示例 211
7.4.1　HBase大对象存储（LOB） 211
7.4.2　加盐表 212
7.4.3　HBase跨数据中心大表 213
7.5　Intel Hadoop Hive的功能扩展和编程示例 216
7.5.1　开源Hive的不足 216
7.5.2　Intel Hadoop“Hive over HBase”优化设计 216
7.5.3　Hive over HBase的架构 216
第二部分　MapReduce的编程和算法设计
第8章　MapReduce基础算法程序设计 220
8.1　WordCount 220
8.1.1　WordCount算法编程实现 220
8.2　矩阵乘法 223
8.2.1　矩阵乘法原理和实现思路 223
8.2.2　矩阵乘法的MapReduce程序实现 224
8.3　关系代数运算 227
8.3.1　选择操作 227
8.3.2　投影操作 228
8.3.3　交运算 229
8.3.4　差运算 230
8.3.5　自然连接 231
8.4　单词共现算法 233
8.4.1　单词共现算法的基本设计 233
8.4.2　单词共现算法的实现 234
8.4.3　单词共现算法实现中的细节问题 235
8.5　文档倒排索引 237
8.5.1　简单的文档倒排索引 237
8.5.2　带词频等属性的文档倒排索引 239
8.6　PageRank网页排名算法 242
8.6.1　PageRank的简化模型 243
8.6.2　PageRank的随机浏览模型 244
8.6.3　PageRank的MapReduce实现 245
8.7　专利文献分析算法 249
8.7.1　构建专利被引用列表 250
8.7.2　专利被引用次数统计 251
8.7.3　专利被引用次数直方图统计 252
8.7.4　按照年份或国家统计专利数 254
第9章　MapReduce高级程序设计技术 256
9.1　简介 256
9.2　复合键值对的使用 257
9.2.1　把小的键值对合并成大的键值对 257
9.2.2　巧用复合键让系统完成排序 259
9.3　用户定制数据类型 262
9.3.1　Hadoop内置的数据类型 263
9.3.2　用户自定义数据类型的实现 263
9.4　用户定制数据输入输出格式 264
9.4.1　Hadoop内置的数据输入格式与RecordReader 265
9.4.2　用户定制数据输入格式与RecordReader 265
9.4.3　Hadoop内置的数据输出格式与RecordWriter 269
9.4.4　用户定制数据输出格式与RecordWriter 269
9.4.5　通过定制数据输出格式实现多集合文件输出 270
9.5　用户定制Partitioner和Combiner 271
9.5.1　用户定制Partitioner 272
9.5.2　用户定制Combiner 273
9.6　组合式MapReduce计算作业 274
9.6.1　迭代MapReduce计算任务 274
9.6.2　顺序组合式MapReduce作业的执行 275
9.6.3　具有复杂依赖关系的组合式MapReduce作业的执行 275
9.6.4　MapReduce前处理和后处理步骤的链式执行 276
9.7　多数据源的连接 278
9.7.1　基本问题数据示例 279
9.7.2　用DataJoin类实现Reduce端连接 279
9.7.3　用全局文件复制方法实现Map端连接 285
9.7.4　带Map端过滤的Reduce端连接 287
9.7.5　多数据源连接解决方法的限制 288
9.8　全局参数/数据文件的传递与使用 288
9.8.1　全局作业参数的传递 288
9.8.2　查询全局的MapReduce作业属性 290
9.8.3　全局数据文件的传递 291
9.9　关系数据库的连接与访问 292
9.9.1　从数据库中输入数据 292
9.9.2　向数据库中输出计算结果 292
第10章　MapReduce数据挖掘基础算法 295
10.1　K-Means聚类算法 295
10.1.1　K-Means聚类算法简介 295
10.1.2　基于MapReduce的K-Means算法的设计实现 297
10.2　KNN最近邻分类算法 300
10.2.1　KNN最近邻分类算法简介 300
10.2.2　基于MapReduce的KNN算法的设计实现 301
10.3　朴素贝叶斯分类算法 303
10.3.1　朴素贝叶斯分类算法简介 303
10.3.2　朴素贝叶斯分类并行化算法的设计 304
10.3.3　朴素贝叶斯分类并行化算法的实现 306
10.4　决策树分类算法 310
10.4.1　决策树分类算法简介 310
10.4.2　决策树并行化算法的设计 313
10.4.3　决策树并行化算法的实现 317
10.5　频繁项集挖掘算法 327
10.5.1　频繁项集挖掘问题描述 327
10.5.2 　Apriori频繁项集挖掘算法简介 328
10.5.3　Apriori频繁项集挖掘并行化算法的设计 329
10.5.4　Apriori频繁项集挖掘并行化算法的实现 331
10.5.5　基于子集求取的频繁项集挖掘算法的设计 335
10.5.6　基于子集求取的频繁项集挖掘并行化算法的实现 336
10.6　隐马尔科夫模型和最大期望算法 340
10.6.1　隐马尔科夫模型的基本描述 340
10.6.2　隐马尔科夫模型问题的解决方法 341
10.6.3　最大期望算法概述 345
10.6.4　并行化隐马尔科夫算法设计 345
10.6.5　隐马尔科夫算法的并行化实现 348
第11章　大数据处理算法设计与应用编程案例 352
11.1　基于MapReduce的搜索引擎算法 352
11.1.1　搜索引擎工作原理简介 353
11.1.2　基于MapReduce的文档预处理 354
11.1.3　基于MapReduce的文档倒排索引构建 356
11.1.4　建立Web信息查询服务 363
11.2　基于MapReduce的大规模短文本多分类算法 365
11.2.1　短文本多分类算法工作原理简介 365
11.2.2　并行化分类训练算法设计实现 366
11.2.3　并行化分类预测算法设计实现 369
11.3　基于MapReduce的大规模基因序列比对算法 371
11.3.1　基因序列比对算法简介 371
11.3.2　并行化BLAST算法的设计与实现 373
11.4　基于MapReduce的大规模城市路径规划算法 379
11.4.1　问题背景和要求 379
11.4.2　数据输入 380
11.4.3　程序设计要求 384
11.4.4　算法设计总体框架和处理过程 385
11.4.5　并行化算法的设计与实现 386
11.5　基于MapReduce的大规模重复文档检测算法 396
11.5.1　重复文档检测问题描述 396
11.5.2　重复文档检测方法和算法设计 397
11.5.3　重复文档检测并行化算法设计实现 401
11.6　基于内容的并行化图像检索算法与引擎 404
11.6.1　基于内容的图像检索问题概述 404
11.6.2　图像检索方法和算法设计思路 405
11.6.3　并行化图像检索算法实现 407
11.7　基于MapReduce的大规模微博传播分析 412
11.7.1　微博分析问题背景与并行化处理过程 413
11.7.2　并行化微博数据获取算法的设计实现 414
11.7.3　并行化微博数据分析算法的设计实现 416
11.8　基于关联规则挖掘的图书推荐算法 422
11.8.1　图书推荐和关联规则挖掘简介 422
11.8.2　图书频繁项集挖掘算法设计与数据获取 423
11.8.3　图书关联规则挖掘并行化算法实现 425
11.9　基于Hadoop的城市智能交通综合应用案例 432
11.9.1　应用案例概述 432
11.9.2　案例一：交通事件检测 433
11.9.3　案例二：交通流统计分析功能 435
11.9.4　案例三：道路旅行时间分析 435
11.9.5　案例四：HBase实时查询 436
11.9.6　案例五：HBase Endpoint快速统计 437
11.9.7　案例六：利用Hive高速统计 439
附　　录
附录A　OpenMP并行程序设计简介 442
附录B　MPI并行程序设计简介 448
附录C　英特尔Apache Hadoop*系统安装手册 457
参考文献 486

.　　第7章Intel Hadoop系统优化与功能增强，介绍Hadoop Intel系统优化与功能增强以及Intel Hadoop系统的安装管理，然后详细介绍和解读Intel Hadoop系统HDFS的高级功能扩展、HBase的高级功能扩展与编程示例以及Hive的高级功能扩展与编程示例。
　　第8章MapReduce 基础算法程序设计，介绍MapReduce的基础算法设计，包括WordCount、矩阵乘法、关系代数运算、单词共现算法、文档倒排索引、PageRank网页排名算法以及专利文献分析算法设计方法和编程实现。本章所有算法均有完整实现代码供下载学习。
　　第9章MapReduce高级程序设计技术，介绍MapReduce高级程序设计技术，包括复合键值对的使用、用户定制数据类型、用户定制输入输出格式、用户定制Partitioner和Combiner、组合式MapReduce计算作业、多数据源的连接、全局参数/数据文件的传递与使用以及关系数据库的连接与访问技术。
　　第10章MapReduce数据挖掘基础算法，介绍基于MapReduce的机器学习和数据挖掘并行化算法设计方法和编程实现，包括K-Means聚类算法、最近邻分类算法、朴素贝叶斯分类算法、决策树分类算法、频繁项集挖掘算法以及隐马尔科夫模型和最大期望算法。本章所有算法均有完整实现代码供下载学习。
　　第11章 大数据处理算法设计与应用编程案例，介绍大数据处理算法与基本应用编程案例的算法设计和编程实现，包括基于MapReduce的搜索引擎算法、基于MapReduce的大规模短文本多分类算法、基于MapReduce的大规模基因序列比对算法、基于MapReduce的大规模城市路径规划算法、基于MapReduce的大规模重复文档检测算法、基于内容的并行化图像搜索算法与引擎、基于MapReduce的大规模微博传播分析、基于关联规则挖掘的图书推荐算法、以及基于Hadoop的城市智能交通综合应用案例。
　　本书由南京大学计算机系PASA大数据实验室黄宜华教授担任主编、并负责全书内容的组织和编审，Intel公司大数据软件部首席工程师苗凯翔担任副主编。其余作者主要来自南京大学计算机系PASA大数据实验室以及Intel公司大数据软件部；此外，北京神州立诚科技有限公司也参加了部分章节的编写。
　　本书第1章由黄宜华、周珊编写完成，第2章由仇红剑编写完成，第3章由赵頔编写完成，第4章由黄宜华、沈仪和赵博编写完成，第5章由姜伟华、杜竟成编写完成，第6章由萧少聪、韩小姣编写完成，第7章由陈建忠、王星宇、王毅、Manoj Shanmugasundaram编写完成，第8章由唐云、金磊编写完成，第9章由黄宜华编写完成，第10章由金磊、赵頔、仇红剑、顾荣编写完成，第11章由顾荣、赵博、韦永壮、笪庆、陈虎、李相臣、彭岳、王刚、姬浩、张同宝、陈新江编写完成。
　　衷心感谢Intel公司大数据软件部参编工程师在本书写作过程中的共同努力和辛苦付出！特别感谢Intel公司Evelyn Yan（颜历）、Kally Wang（王星宇）、Yale Wang（王毅）在本书写作过程中所做的大量组织协调工作！也感谢本团队所在南京大学计算机系PASA大数据实验室所有参编作者的辛苦努力和付出！感谢机械工业出版社华章分社在本书编写和出版过程中的大力支持和帮助！
　　Google中国公司大学合作部在过去的几年中为我们开设大数据技术课程给予了大力的支持和帮助，在此，谨向Google中国公司表示衷心的感谢！同时也要衷心感谢清华大学郑纬民教授和陈康副教授，他们为2009年Google公司的技术培训提供了全部课件并进行了主讲，使我们获益匪浅，该课件也为后期本课程的建设提供了良好的基础。此外，也要衷心感谢南京大学计算机软件新技术国家重点实验室，早在2010年即投入100万元资助购建了一个科研教学专用的MapReduce大数据并行处理集群，为几年来本团队的教学科研和本系其他诸多课题组的研究工作提供了良好的计算设施和条件。
　　本书是国内第一本经过多年课堂教学实践后撰写而成的大数据处理和并行编程技术书籍，因此，本书非常适合于高等院校作为MapReduce大数据并行处理技术课程教材使用，同时也很适合于高等院校学生作为自学MapReduce并行处理技术的参考书。与此同时，由于本书包含很多来自业界实际产品的深度技术内容，并包括了丰富的算法设计和编程实战案例，因此本书也非常适合于作为IT和其他应用行业专业技术人员从事大数据处理应用开发和编程工作时的参考手册。
　　书中第8章和第10章全部算法设计的程序代码都经过本团队完整编程实现并运行通过，源码可在与本书配套的南京大学PASA大数据实验室（PASA：Parallel Algorithms，Systems，and Applications）网站上下载：http://pasa-bigdata.nju.edu.cn/links.html。
　　由于作者水平有限，书中难免会有不准确甚至错误之处。不当之处敬请读者批评指正，并将反馈意见发送到邮箱：feedback_bigdata@163.com，以便我们再版时修正错误。
　　
　　南京大学计算机科学与技术系PASA大数据实验室
　　黄宜华
　　2014年3月18日，于南京
　　

.　　图1-1摩尔定律
　　1）提升计算机处理器字长。随着计算机技术的发展，单处理器字长也在不断提升，从最初的4位发展到如今的64位。处理器字长提升的每个发展阶段均有代表性的处理器产品，如20世纪70年代出现的最早的4位Intel微处理器4004，到同时代以Intel 8008为代表的8位处理器，以及20世纪80年代Intel推出的16位字长80286处理器，以及后期发展出的Intel 80386/486/Pentium系列为主的32位处理器等。2000年以后发展至今，出现了64位字长的处理器。目前，32位和64位处理器是市场上主流的处理器。计算机处理器字长的发展大幅提升了处理器性能，推动了单处理器计算机的发展。
　　2）提高处理器芯片集成度。1965年，戈登·摩尔（Gordon Moore）发现了这样一条规律：半导体厂商能够集成在芯片中的晶体管数量大约每18～24个月翻一番，其计算性能也随着翻一番，这就是众所周知的摩尔定律。在计算技术发展的几十年中，摩尔定律一直引导着计算机产业的发展。
　　3）提升处理器的主频。计算机的主频越高，指令执行的时间则越短，计算性能自然会相应提高。因此，在2004年以前，处理器设计者一直追求不断提升处理器的主频。计算机主频从Pentium开始的60MHz，曾经最高可达到4GHz～5GHz。
　　4）改进处理器微架构。计算机微处理器架构的改进对于计算性能的提升具有重大的作用。例如，为了使处理器资源得到最充分利用，计算机体系结构设计师引入了指令集并行技术（Instruction-level Parallelism，ILP），这是单处理器并行计算的杰出设计思想之一。实现指令级并行最主要的体系结构技术就是流水线技术（Pipeline）。
　　在2004年以前，以上这些技术极大地提高了微处理器的计算性能，但此后处理器的性能不再像人们预期的那样能够继续提高。人们发现，随着集成度的不断提高以及处理器频率的不断提升，单核处理器的性能提升开始接近极限。首先，芯片的集成度会受到半导体器件制造工艺的限制。目前集成电路已经达到十多个纳米的极小尺度，因此，芯片集成度不可能无限制提高。与此同时，根据芯片的功耗公式P=CV2f（其中，P是功耗；C是时钟跳变时门电路电容，与集成度成正比；V是电压，f是主频），芯片的功耗与集成度和主频成正比，芯片集成度和主频的大幅提高导致了功耗的快速增大，进一步导致了难以克服的处理器散热问题。而流水线体系结构技术也已经发展到了极致，2001年推出的Pentium4（CISC结构）已采用了20级复杂流水线技术，因此，流水线为主的微体系结构技术也难以有更大提升的空间。
　　由图1-2可以看出，从2004年以后，微处理器的主频和计算性能变化逐步趋于平缓，不再随着集成度的提高而提高。如图1-3a所示，在2005年以前，人们预期可以一直提升处理器主频。但2004年5月Intel处理器Tejas和Jayhawk（4GHz）因无法解决散热问题最终放弃，标志着升频技术时代的终结。因此，随后人们修改了2005年后微处理器主频提升路线图，基本上以较小的幅度提升处理器主频，而代之以多核实现性能提升，如图1-3b所示。
　　2.?多核计算技术成为必然发展趋势
　　2005年，Intel公司宣布了微处理器技术的重大战略调整，即从2005年开始，放弃过去不断追求单处理器计算性能提升的战略，转向以多核微处理器架构实现计算性能提升。自此Intel推出了多核/众核构架，微处理器全面转入了多核计算技术时代。多校计算技术的基本思路是：简化单处理器的复杂设计，代之以在单个芯片上设计多个简化的处理器核，以多核/众核并行计算提升计算性能。
　　图1-2微处理器芯片集成度与主频、功耗、性能的演变趋势图
　　图1-32005年前后人们预期的主频提升路线图
　　（注：插图引自Edward L. Bosworth，The Power Wall，2010）
　　自Intel在2006年推出双核的Pentium D处理器以来，已经出现了很多从4核到12核的多核处理器产品，如2007年Intel推出的主要用于个人电脑的4核Core 2 Quad系列以及2008～2010年推出的Core i5和i7系列。而Intel服务器处理器也陆续推出了Xeon E5系列4-12核的处理器，以及Xeon E7系列6-10核处理器。
　　除了多核处理器产品外，众核处理器也逐步出现。NVIDIA GPU是一种主要面向图形处理加速的众核处理器，在图形处理领域得到广泛应用。2012年年底Intel公司发布了基于集成众核架构（Intel? MIC Architecture，Intel? Many Integrated Core Architecture）的Xeon Phi协处理器，这是一款真正意义上通用性的商用级众核处理器，可支持使用与主机完全一样的通用的C/C++编程方式，用OpenMP和MPI等并行编程接口完成并行化程序的编写，完成的程序既可在多核主机上运行，也可在众核协处理器上运行。众核计算具有体积小、功耗低、核数多、并行处理能力强等技术特点和优势，将在并行计算领域发挥重要作用。众核处理器的出现进一步推进了并行计算技术的发展，从而使并行计算的性能发挥到极致，更加明确地体现了并行计算技术的发展趋势。
　　3.?大数据时代日益增大的数据规模迫切需要使用并行计算技术
　　随着计算机和信息技术的不断普及应用，行业应用领域计算系统的规模日益增大，数据规模也急剧增大。
　　全球著名的互联网企业的数据规模动辄达到数百至数千PB量级，而其他的诸如电信、电力、金融、科学计算等典型应用行业和领域，其数据量也高达数百TB至数十PB的规模。如此巨大的数据量使得传统的计算技术和系统已经无法应对和满足计算需求。巨大的数据量会导致巨大的计算时间开销，使得很多在小规模数据时可以完成的计算任务难以在可接受的时间内完成大规模数据的处理。超大的数据量或计算量，给原有的单处理器和串行计算技术带来巨大挑战，因而迫切需要出现新的技术和手段以应对急剧增长的行业应用需求。
　　1.1.2并行计算技术的分类
　　并行计算技术发展至今，出现了各种不同的技术方法，同时也出现了不同的分类方法，包括按指令和数据处理方式的Flynn分类、按存储访问结构的分类、按系统类型的分类、按应用的计算特征的分类、按并行程序设计方式的分类。
　　1.?Flynn分类法
　　1966年，斯坦福大学教授Michael J. Flynn提出了经典的计算机结构分类方法，从最抽象的指令和数据处理方式进行分类，通常称为Flynn分类。Flynn分类法是从两种角度进行分类，一是依据计算机在单个时间点能够处理的指令流的数量；二是依据计算机在单个时间点能够处理的数据流的数量。任何给定的计算机系统均可以依据处理指令和数据的方式进行分类。图1-4所示为Flynn分类下的几种不同的计算模式。
　　图1-4Flynn分类法
　　1）单指令流单数据流（Single Instruction stream and Single Data stream，SISD）：SISD是传统串行计算机的处理方式，硬件不支持任何并行方式，所有指令串行执行。在一个时钟周期内，处理器只能处理一个数据流。很多早期计算机均采用这种处理方式，例如最初的IBM PC机。
　　2）单指令流多数据流（Single Instruction stream and Multiple Data stream，SIMD）：SIMD采用一个指令流同时处理多个数据流。最初的阵列处理机或者向量处理机都具备这种处理能力。计算机发展至今，几乎所有计算机都以各种指令集形式实现SIMD。较为常用的有，Intel处理器中实现的MMXTM、SSE（Streaming SIMD Extensions）、SSE2、SSE3、SSE4以及AVX（Advanced Vector Extensions）等向量指令集。这些指令集都能够在单个时钟周期内处理多个存储在寄存器中的数据单元。SIMD在数字信号处理、图像处理、多媒体信息处理以及各种科学计算领域有较多的应用。
　　3）多指令流单数据流（Multiple Instruction stream and Single Data stream，MISD）：MISD采用多个指令流处理单个数据流。这种方式实际很少出现，一般只作为一种理论模型，并没有投入到实际生产和应用中。
　　4）多指令流多数据流（Multiple Instruction Stream and Multiple Data Stream，MIMD）：MIMD能够同时执行多个指令流，这些指令流分别对不同数据流进行处理。这是目前最流行的并行计算处理方式。目前较常用的多核处理器以及Intel最新推出的众核处理器都属于MIMD的并行计算模式。
　　2.按存储访问结构分类
　　按存储访问结构，可将并行计算分为以下几类：
　　1）共享内存访问结构（Shared Memory Access）：即所有处理器通过总线共享内存的多核处理器，也称为UMA结构（Uniform Memory Access，一致性内存访问结构）。SMP（Symmetric Multi-Processing，对称多处理器系统）即为典型的内存共享式的多核处理器构架。图1-5即为共享内存访问结构示意图。
　　2）分布式内存访问结构（Distributed Memory Access）：图1-6所示为分布式内存访问结构的示意图，其中，各个分布式处理器使用本地独立的存储器。
　　图1-5共享内存访问结构 图1-6分布式内存访问结构
　　3）分布共享式内存访问结构（Distributed and Shared Memory Access）：是一种混合式的内存访问结构。如图1-7所示，各个处理器分别拥有独立的本地存储器，同时，再共享访问一个全局的存储器。
　　分布式内存访问结构和分布共享式内存访问结构也称为NUMA结构（Non-Uniform Memory Access，非一致内存访问结构）。在多核情况下，这种内存访问架构可以充分扩展内存带宽，减少内存冲突开销，提高系统扩展性和计算性能。
　　3.?按系统类型分类
　　按并行计算系统类型，可将并行计算分为以下类型：
　　1）多核/众核并行计算系统（Multi-Core/Many-Core）或芯片级多处理系统（Chip-level
　　Multiprocessing，CMP）。
　　2）对称多处理系统（Symmetric Multi Processing，SMP），即多个相同类型处理器通过总线连接、并共享存储器构成的一种并行计算系统。
　　3）大规模并行处理系统（Massive Parallel Processing，MPP），以专用内联网连接一组处理器形成的一种并行计算系统。
　　4）集群（Cluster），以网络连接的一组普通商用计算机构成的并行计算系统。
　　5）网格（Grid），用网络连接远距离分布的一组异构计算机构成的并行计算系统。
　　4.?按应用的计算特征分类
　　按应用的计算特征，可将并行计算分为以下类型：
　　1）数据密集型并行计算（Data-Intensive Parallel Computing），即数据量极大、但计算相对简单的并行计算。
　　2）计算密集型并行计算（Computation-Intensive Parallel Computing），即数据量相对不大、但计算较为复杂的并行处理。较为传统的高性能计算领域大部分都是这一类型，例如三维建模与渲染、气象预报、生命科学等科学计算。
　　3）数据密集与计算密集混合型并行计算，具备数据密集和计算密集双重特征的并行计算，如3D电影渲染等。
　　5.?按并行程序设计方式分类
　　按并行程序设计方式，可将并行计算分为以下几类：
　　1）共享存储变量方式（Shared Memory Variables）：这种方式通常被称为多线程并行程序设计。多线程并行方式发展至今，应用非常广泛，同时也出现了很多代表性的并行编程接口，包括开源的和一些商业版本的并行编程接口，例如最常用的有pthread，OpenMP，Intel TBB等。其中，pthread是较为低层的多线程编程接口；而OpenMP采用了语言扩充的方法，简单易用，不需要修改代码，仅需添加指导性语句，应用较为广泛；而Intel TBB是一种很适合用C++代码编程的并行程序设计方法，提供了很多方便易用的并行编程接口。本书的附录A将较为详细地介绍OpenMP的技术特点和编程方法。共享存储变量方式可能引起数据的不一致性，从而导致数据和资源访问冲突，因此一般都需要引入同步控制机制。
　　2）消息传递方式（Message Passing）：从广义上来讲，对于分布式内存访问结构的系统，为了分发数据实现并行计算、随后收集计算结果，需要在各个计算节点或者计算任务间进行数据通信。这种编程方式有时候可狭义地理解为多进程处理方式。最常用的消息传递方式是MPI（Message Passing Interface，消息传递并行编程接口标准）。MPI广泛应用于科学计算的各个领域，并体现了其高度的可扩展性，能充分利用并行计算系统的硬件资源，发挥其计算性能。具体有关MPI技术的介绍，请阅读本书的附录B：MPI并行程序设计简介。
　　3）MapReduce并行程序设计方式：Google公司提出的MapReduce并行程序设计模型，是目前主流的大数据处理并行程序设计方法，可广泛应用于各个领域的大数据处理，尤其是搜索引擎等互联网行业的大规模数据处理。本书后续重点探讨的数据处理技术正是基于这种方式的并行程序设计技术。
　　4）其他新型并行计算和编程方式：由于MapReduce设计之初主要致力于大数据的线下批处理，因而其难以满足高实时性和高数据相关性的大数据处理需求。为此，近年来，逐步出现了多种其他类型的大数据计算模式和方法。这些新型计算模式和方法包括：实时流式计算、迭代计算、图计算以及基于内存的计算等。
　　1.1.3并行计算的主要技术问题
　　依赖于所采用的并行计算体系结构，不同类型的并行计算系统在硬件构架、软件构架和并行算法方面会涉及到不同的技术问题，但概括起来，主要包括以下技术问题。
　　1.?多处理器/多节点网络互连技术
　　对于大型的并行处理系统，网络互连技术对处理器能力影响很大。典型的网络互连结构包括共享总线连接、交叉开关矩阵、环形结构、Mesh网络结构、互联网络结构等。
　　2.?存储访问体系结构
　　存储访问体系结构主要研究不同的存储结构以及在不同存储结构下的特定技术问题，包括共享数据访问与同步控制、数据通信控制和节点计算同步控制、Cache的一致性、数据访问/通信的时间延迟等技术问题。
　　3.?分布式数据与文件管理
　　并行计算的一个重要问题是，在大规模集群环境下，如何解决大规模数据的存储和访问管理问题。在大规模集群环境下，解决大数据分布存储管理和访问问题非常关键，尤其是数据密集型并行计算，数据的存储访问对并行计算的性能至关重要。目前比较理想的解决方法是提供分布式数据和文件管理系统，代表性的系统有Google GFS（Google File System）、Lustre、HDFS（Hadoop Distributed File System）等。这些分布式文件系统各有特色，适用于不同领域。
　　4.?并行计算的任务划分和算法设计
　　并行计算的任务分解和算法设计需要考虑的是如何将大的计算任务分解成子任务，继而分配给各节点或处理器并行处理，最终收集局部结果进行整合。一般有算法分解和数据划分两种并行计算形式，尤其是算法分解，可有多种不同的实现方式。
　　5.?并行程序设计模型和语言
　　根据不同的硬件构架，不同的并行计算系统可能需要不同的并行程序设计模型、方法和语言。目前主要的并行程序设计语言和方法包括共享内存式并行程序设计、消息传递式并行程序设计、MapReduce并行程序设计以及近年来出现的满足不同大数据处理需求的其他并行计算和程序设计方法。而并行程序设计语言通常可以有不同的实现方式，包括：语言级扩充（即使用编译指令在普通的程序设计语言中增加一些并行化编译指令，如OpenMP提供C、C++、Fortran语言扩充）、并行计算库函数与编程接口（使用函数库提供并行计算编程接口，如MPI、CUDA等）以及能提供诸多自动化处理能力的并行计算软件框架（如Hadoop MapReduce并行计算框架等）。
　　6.?并行计算软件框架设计和实现
　　现有的OpenMP、MPI、CUDA等并行程序设计方法需要程序员考虑数据存储管理、数据和任务划分、任务的调度执行、数据同步和通信、结果收集、出错恢复处理等几乎所有技术细节，非常繁琐。为了进一步提升并行计算程序的自动化并行处理能力，编程时应该尽量减少程序员对很多系统底层技术细节的考虑，使得编程人员能从底层细节中解放出来，更专注于应用问题本身的计算和算法实现。目前已发展出多种具有自动化并行处理能力的计算软件框架，如Google MapReduce和Hadoop MapReduce并行计算软件框架，以及近年来出现的以内存计算为基础、能提供多种大数据计算模式的Spark系统等。
　　7.?数据访问和通信控制
　　并行计算目前存在多种存储访问体系结构，包括共享存储访问结构、分布式存储访问结构以及分布共享式存储访问结构。不同存储访问结构下需要考虑不同的数据访问、节点通信以及同步控制等问题。例如，在共享存储访问结构系统中，多个处理器访问共享存储区，可能导致数据访问的不确定性，从而需要引入互斥信号、条件变量等同步机制，保证共享数据访问的正确性，同时需解决可能引起的死锁问题。而对于分布式存储访问结构系统，数据可能需要通过主节点传输到其他计算节点，由于节点间的计算速度不同，为了保证计算的同步，需要考虑计算的同步问题。
　　8.?可靠性与容错性技术
　　对于大型的并行计算系统，经常发生节点出错或失效。因此，需要考虑和预防由于一个节点失效可能导致的数据丢失、程序终止甚至系统崩溃的问题。这就要求系统考虑良好的可靠性设计和失效检测恢复技术。通常可从两方面进行可靠性设计：一是数据失效恢复，可使用数据备份和恢复机制，当某个磁盘出错或数据损毁时，保证数据不丢失以及数据的正确性；二是系统和任务失效恢复，当某个节点失效时，需要提供良好的失效检测和隔离技术，以保证并行计算任务正常进行。
　　9.?并行计算性能分析与评估
　　并行计算的性能评估较为常用的方式是通过加速比来体现性能提升。加速比指的是并行程序的并行执行速度相对于其串行程序执行加速了多少倍。这个指标贯穿于整个并行计算技术，是并行计算技术的核心。从应用角度出发，不论是开发还是使用，都希望一个并行计算程序能达到理想的加速比，即随着处理能力的提升，并行计算程序的执行速度也需要有相应的提升。并行计算性能的度量有以下两个著名的定律：
　　1）Amdal定律：在一定的程序可并行化比例下，加速比不能随着处理器数目的增加而无限上升，而是受限于程序的串行化部分的比例，加速比极限是串行比例的倒数，反映了固定负载的加速情况。Amdal定律的公式是：
　　其中，S是加速比，P是程序可并行部分的比例，N是处理器数量。图1-8所示是在程序不同的可并行化比例下、在不同处理器数量下的加速比，由图示结果可见，在固定的程序可并行化比例下，加速比提升会有一个上限，处理器数量的增加并不能无限制地带来性能提升。
　　图1-8Amdal定律在程序不同的可并行化比例和不同处理器数量下的加速比
　　2）Gustafson定律：在放大系统规模的情况下，加速比可与处理器数量成比例地线性增长，串行比例不再是加速比的瓶颈。这反映了对于增大的计算负载，当系统性能未达到期望值时，可通过增加处理器数量的方法应对（如图1-9和1-10所示）。
　　图1-9Gustafson定律：处理器与工作负载
　　图1-10Gustafson定律：处理器与运行时间
　　1.2大数据处理技术简介
　　1.2.1大数据的发展背景和研究意义
　　近几年来，随着计算机和信息技术的迅猛发展和普及应用，行业应用系统的规模迅速扩大，行业应用所产生的数据呈爆炸性增长。动辄达到数百TB甚至数十至数百PB规模的行业/企业大数据已远远超出了现有传统的计算技术和信息系统的处理能力，因此，寻求有效的大数据处理技术、方法和手段已经成为现实世界的迫切需求。百度目前的总数据量已超过1000PB，每天需要处理的网页数据达到10PB～100PB；淘宝累计的交易数据量高达100PB；Twitter每天发布超过2亿条消息，新浪微博每天发帖量达到8000万条；中国移动一个省的电话通联记录数据每月可达0.5PB～1PB；一个省会城市公安局道路车辆监控数据三年可达200亿条、总量120TB。据世界权威IT信息咨询分析公司IDC研究报告预测：全世界数据量未来10年将从2009年的0.8ZB增长到2020年的35ZB（1ZB=1000EB=1000000PB），10年将增长44倍，年均增长40%。
　　早几年人们把大规模数据称为“海量数据”，但实际上，大数据（Big Data）这个概念早在2008年就已被提出。2008年，在Google成立10周年之际，著名的《自然》杂志出版了一期专刊，专门讨论未来的大数据处理相关的一系列技术问题和挑战，其中就提出了“Big Data”的概念。
　　随着大数据概念的普及，人们常常会问，多大的数据才叫大数据？其实，关于大数据，难以有一个非常定量的定义。维基百科给出了一个定性的描述：大数据是指无法使用传统和常用的软件技术和工具在一定时间内完成获取、管理和处理的数据集。进一步，当今“大数据”一词的重点其实已经不仅在于数据规模的定义，它更代表着信息技术发展进入了一个新的时代，代表着爆炸性的数据信息给传统的计算技术和信息技术带来的技术挑战和困难，代表着大数据处理所需的新的技术和方法，也代表着大数据分析和应用所带来的新发明、新服务和新的发展机遇。
　　由于大数据处理需求的迫切性和重要性，近年来大数据技术已经在全球学术界、工业界和各国政府得到高度关注和重视，全球掀起了一个可与20世纪90年代的信息高速公路相提并论的研究热潮。美国和欧洲一些发达国家政府都从国家科技战略层面提出了一系列的大数据技术研发计划，以推动政府机构、重大行业、学术界和工业界对大数据技术的探索研究和应用。
　　早在2010年12月，美国总统办公室下属的科学技术顾问委员会（PCAST）和信息技术顾问委员会（PITAC）向奥巴马和国会提交了一份《规划数字化未来》的战略报告，把大数据收集和使用的工作提升到体现国家意志的战略高度。报告列举了5个贯穿各个科技领域的共同挑战，而第一个最重大的挑战就是“数据”问题。报告指出：“如何收集、保存、管理、分析、共享正在呈指数增长的数据是我们必须面对的一个重要挑战”。报告建议：“联邦政府的每一个机构和部门，都需要制定一个‘大数据’的战略”。2012年3月，美国总统奥巴马签署并发布了一个“大数据研究发展创新计划”（Big Data R & D Initiative），由美国国家自然基金会（NSF）、卫生健康总署（NIH）、能源部（DOE）、国防部（DOD）等6大部门联合，投资2亿美元启动大数据技术研发，这是美国政府继1993年宣布“信息高速公路”计划后的又一次重大科技发展部署。美国白宫科技政策办公室还专门支持建立了一个大数据技术论坛，鼓励企业和组织机构间的大数据技术交流与合作。
　　2012年7月，联合国在纽约发布了一本关于大数据政务的白皮书《大数据促发展：挑战与机遇》，全球大数据的研究和发展进入了前所未有的高潮。这本白皮书总结了各国政府如何利用大数据响应社会需求，指导经济运行，更好地为人民服务，并建议成员国建立“脉搏实验室”（Pulse Labs），挖掘大数据的潜在价值。
　　由于大数据技术的特点和重要性，目前国内外已经出现了“数据科学”的概念，即数据处理技术将成为一个与计算科学并列的新的科学领域。已故著名图灵奖获得者Jim Gray在2007年的一次演讲中提出，“数据密集型科学发现”（Data-Intensive Scientific Discovery）将成为科学研究的第四范式，科学研究将从实验科学、理论科学、计算科学，发展到目前兴起的数据科学。
　　为了紧跟全球大数据技术发展的浪潮，我国政府、学术界和工业界对大数据也予以了高度的关注。央视著名“对话”节目2013年4月14日和21日邀请了《大数据时代——生活、工作与思维的大变革》作者维克托·迈尔-舍恩伯格，以及美国大数据存储技术公司LSI总裁阿比分别做客“对话”节目，做了两期大数据专题谈话节目“谁在引爆大数据”、“谁在掘金大数据”，国家央视媒体对大数据的关注和宣传体现了大数据技术已经成为国家和社会普遍关注的焦点。
　　而国内的学术界和工业界也都迅速行动，广泛开展大数据技术的研究和开发。2013年以来，国家自然科学基金、973计划、核高基、863等重大研究计划都已经把大数据研究列为重大的研究课题。为了推动我国大数据技术的研究发展，2012年中国计算机学会（CCF）发起组织了CCF大数据专家委员会，CCF专家委员会还特别成立了一个“大数据技术发展战略报告”撰写组，并已撰写发布了《2013年中国大数据技术与产业发展白皮书》。
　　大数据在带来巨大技术挑战的同时，也带来巨大的技术创新与商业机遇。不断积累的大数据包含着很多在小数据量时不具备的深度知识和价值，大数据分析挖掘将能为行业/企业带来巨大的商业价值，实现各种高附加值的增值服务，进一步提升行业/企业的经济效益和社会效益。由于大数据隐含着巨大的深度价值，美国政府认为大数据是“未来的新石油”，对未来的科技与经济发展将带来深远影响。因此，在未来，一个国家拥有数据的规模和运用数据的能力将成为综合国力的重要组成部分，对数据的占有、控制和运用也将成为国家间和企业间新的争夺焦点。
　　大数据的研究和分析应用具有十分重大的意义和价值。被誉为“大数据时代预言家”的维克托·迈尔-舍恩伯格在其《大数据时代》一书中列举了大量详实的大数据应用案例，并分析预测了大数据的发展现状和未来趋势，提出了很多重要的观点和发展思路。他认为：“大数据开启了一次重大的时代转型”，指出大数据将带来巨大的变革，改变我们的生活、工作和思维方式，改变我们的商业模式，影响我们的经济、政治、科技和社会等各个层面。
　　由于大数据行业应用需求日益增长，未来越来越多的研究和应用领域将需要使用大数据并行计算技术，大数据技术将渗透到每个涉及到大规模数据和复杂计算的应用领域。不仅如此，以大数据处理为中心的计算技术将对传统计算技术产生革命性的影响，广泛影响计算机体系结构、操作系统、数据库、编译技术、程序设计技术和方法、软件工程技术、多媒体信息处理技术、人工智能以及其他计算机应用技术，并与传统计算技术相互结合产生很多新的研究热点和课题。
　　大数据给传统的计算技术带来了很多新的挑战。大数据使得很多在小数据集上有效的传统的串行化算法在面对大数据处理时难以在可接受的时间内完成计算；同时大数据含有较多噪音、样本稀疏、样本不平衡等特点使得现有的很多机器学习算法有效性降低。因此，微软全球副总裁陆奇博士在2012年全国第一届“中国云/移动互联网创新大奖赛”颁奖大会主题报告中指出：“大数据使得绝大多数现有的串行化机器学习算法都需要重写”。
　　大数据技术的发展将给我们研究计算机技术的专业人员带来新的挑战和机遇。目前，国内外IT企业对大数据技术人才的需求正快速增长，未来5～10年内业界将需要大量的掌握大数据处理技术的人才。IDC研究报告指出，“下一个10年里，世界范围的服务器数量将增长10倍，而企业数据中心管理的数据信息将增长50倍，企业数据中心需要处理的数据文件数量将至少增长75倍，而世界范围内IT专业技术人才的数量仅能增长1.5倍。”因此，未来十年里大数据处理和应用需求与能提供的技术人才数量之间将存在一个巨大的差距。目前，由于国内外高校开展大数据技术人才培养的时间不长，技术市场上掌握大数据处理和应用开发技术的人才十分短缺，因而这方面的技术人才十分抢手，供不应求。国内几乎所有著名的IT企业，如百度、腾讯、阿里巴巴和淘宝、奇虎360等，都大量需要大数据技术人才。
　　1.2.2大数据的技术特点
　　大数据具有五个主要的技术特点，人们将其总结为5V特征（见图1-11）：
　　1）Volume（大体量）：即可从数百TB到数十数百PB、甚至EB的规模。
　　2）Variety（多样性）：即大数据包括各种格式和形态的数据。
　　3）Velocity（时效性）：即很多大数据需要在一定的时间限度下得到及时处理。
　　4）Veracity（准确性）：即处理的结果要保证一定的准确性。
　　5）Value（大价值）：即大数据包含很多深度的价值，大数据分析挖掘和利用将带来巨大的商业价值。
　　传统的数据库系统主要面向结构化数据的存储和处理，但现实世界中的大数据具有各种不同的格式和形态，据统计现实世界中80%以上的数据都是文本和媒体等非结构化数据；同时，大数据还具有很多不同的计算特征。我们可以从多个角度分类大数据的类型和计算特征。
　　1）从数据结构特征角度看，大数据可分为结构化与非结构化/半结构化数据。
　　2）从数据获取处理方式看，大数据可分为批处理与流式计算方式。
　　3）从数据处理类型看，大数据处理可分为传统的查询分析计算和复杂数据挖掘计算。
　　4）从大数据处理响应性能看，大数据处理可分为实时/准实时与非实时计算，或者是联机计算与线下计算。前述的流式计算通常属于实时计算，此外查询分析类计算通常也要求具有高响应性能，因而也可以归为实时或准实时计算。而批处理计算和复杂数据挖掘计算通常属于非实时或线下计算。
　　5）从数据关系角度看，大数据可分为简单关系数据（如Web日志）和复杂关系数据（如社会网络等具有复杂数据关系的图计算）。
　　6）从迭代计算角度看，现实世界的数据处理中有很多计算问题需要大量的迭代计算，诸如一些机器学习等复杂的计算任务会需要大量的迭代计算，为此需要提供具有高效的迭代计算能力的大数据处理和计算方法。
　　7）从并行计算体系结构特征角度看，由于需要支持大规模数据的存储和计算，因此目前绝大多数大数据处理都使用基于集群的分布式存储与并行计算体系结构和硬件平台。MapReduce是最为成功的分布式存储和并行计算模式。然而，基于磁盘的数据存储和计算模式使MapReduce难以实现高响应性能。为此人们从分布计算体系结构层面上又提出了内存计算的概念和技术方法。
　　1.2.3大数据研究的主要目标、基本原则和基本途径
　　1.?大数据研究的主要目标
　　大数据研究的主要目标是，以有效的信息技术手段和计算方法，获取、处理和分析各种应用行业的大数据，发现和提取数据的深度价值，为行业提供高附加值的应用和服务。因此，大数据研究的核心目标是价值发现，而其技术手段是信息技术和计算方法，其效益目标是为行业提供高附加值的应用和服务。
　　2.?大数据研究的基本特点
　　大数据研究具有以下几方面的主要特点：
　　1）大数据处理具有很强的行业应用需求特性，因此大数据技术研究必须紧扣行业应用需求。
　　2）大数据规模极大，超过任何传统数据库系统的处理能力。
　　3）大数据处理技术综合性强，任何单一层面的计算技术都难以提供理想的解决方案，需要采用综合性的软硬件技术才能有效处理。
　　4）大数据处理时，大多数传统算法都面临失效，需要重写。
　　3.?大数据研究的基本原则
　　大数据研究的基本原则是：
　　1）应用需求为导向：由于大数据问题来自行业应用，因此大数据的研究需要以行业应用问题和需求为导向，从行业实际的应用需求和存在的技术难题入手，研究解决有效的处理技术和解决方案。
　　2）领域交叉为桥梁：由于大数据技术有典型的行业应用特征，因此大数据技术研究和应用开发需要由计算技术人员、数据分析师、具备专业知识的领域专家相互配合和协同，促进应用行业、IT产业与计算技术研究机构的交叉融合，来提供良好的大数据解决方法。
　　3）技术综合为支撑：与传统的单一层面的计算技术研究和应用不同，大数据处理是几乎整个计算技术和信息技术的融合，只有采用技术交叉融合的方法才能提供较为完善的大数据处理方法。
　　4.?大数据研究的基本途径
　　大数据处理有以下三个基本的解决途径：
　　1）寻找新算法降低计算复杂度。大数据给很多传统的机器学习和数据挖掘计算方法和算法带来挑战。在数据集较小时，很多在O(n)、O(nlogn)、O(n2)或O(n3)等线性或多项式复杂度的机器学习和数据挖掘算法都可以有效工作，但当数据规模增长到PB级尺度时，这些现有的串行化算法将花费难以接受的时间开销，使得算法失效。因此，需要寻找新的复杂度更低的算法。
　　2）寻找和采用降低数据尺度的算法。在保证结果精度的前提下，用数据抽样或者数据尺度无关的近似算法来完成大数据的处理。
　　3）分而治之的并行化处理。除上述两种方法外，目前为止，大数据处理最为有效和最重要的方法还是采用大数据并行化算法，在一个大规模的分布式数据存储和并行计算平台上完成大数据并行化处理。
　　1.2.4大数据计算模式和系统
　　MapReduce计算模式的出现有力推动了大数据技术和应用的发展，使其成为目前大数据处理最成功的主流大数据计算模式。然而，现实世界中的大数据处理问题复杂多样，难以有一种单一的计算模式能涵盖所有不同的大数据计算需求。研究和实际应用中发现，由于MapReduce主要适合于进行大数据线下批处理，在面向低延迟和具有复杂数据关系和复杂计算的大数据问题时有很大的不适应性。因此，近几年来学术界和业界在不断研究并推出多种不同的大数据计算模式。
　　所谓大数据计算模式，是指根据大数据的不同数据特征和计算特征，从多样性的大数据计算问题和需求中提炼并建立的各种高层抽象（Abstraction）和模型（Model）。传统的并行计算方法主要从体系结构和编程语言的层面定义了一些较为底层的抽象和模型，但由于大数据处理问题具有很多高层的数据特征和计算特征，因此大数据处理需要更多地结合其数据特征和计算特性考虑更为高层的计算模式。
　　根据大数据处理多样性的需求，目前出现了多种典型和重要的大数据计算模式。与这些计算模式相适应，出现了很多对应的大数据计算系统和工具，如表1-1所示。
　　表1-1大数据计算模式及其对应的典型系统和工具
　　大数据计算模式 典型系统和工具
　　大数据查询分析计算 HBase，Hive，Cassandra，Premel，Impala，Shark，Hana，Redis，等
　　批处理计算 MapReduce，Spark，等
　　流式计算 Scribe，Flume，Storm，S4，Spark Steaming，等
　　迭代计算 HaLoop，iMapReduce，Twister，Spark，等
　　图计算 Pregel，Giraph，Trinity，PowerGraph，GraphX，等
　　内存计算 Dremel，Hana，Redis，等
　　1.?大数据查询分析计算模式与典型系统
　　由于行业数据规模的增长已大大超过了传统的关系数据库的承载和处理能力，因此，目前需要尽快研究并提供面向大数据存储管理和查询分析的新的技术方法和系统，尤其要解决在数据体量极大时如何能够提供实时或准实时的数据查询分析能力，满足企业日常的管理需求。然而，大数据的查询分析处理具有很大的技术挑战，在数量规模较大时，即使采用分布式数据存储管理和并行化计算方法，仍然难以达到关系数据库处理中小规模数据时那样的秒级响应性能。
　　大数据查询分析计算的典型系统包括Hadoop下的HBase和Hive、Facebook公司开发的Cassandra、Google公司的Dremel、Cloudera公司的实时查询引擎Impala；此外为了实现更高性能的数据查询分析，还出现了不少基于内存的分布式数据存储管理和查询系统，如Apache Spark下的数据仓库Shark、SAP公司的Hana、开源的Redis等。
　　2.?批处理计算模式与典型系统
　　最适合于完成大数据批处理的计算模式是MapReduce，这是MapReduce设计之初的主要任务和目标。MapReduce是一个单输入、两阶段（Map和Reduce）的数据处理过程。首先，MapReduce对具有简单数据关系、易于划分的大规模数据采用“分而治之”的并行处理思想；然后将大量重复的数据记录处理过程总结成Map和Reduce两个抽象的操作；最后MapReduce提供了一个统一的并行计算框架，把并行计算所涉及到的诸多系统层细节都交给计算框架去完成，以此大大简化了程序员进行并行化程序设计的负担。
　　MapReduce的简单易用性使其成为目前大数据处理最成功的主流并行计算模式。在开源社区的努力下，开源的Hadoop系统目前已成为较为成熟的大数据处理平台，并已发展成一个包括众多数据处理工具和环境的完整的生态系统。目前几乎国内外的各个著名IT企业都在使用Hadoop平台进行企业内大数据的计算处理。此外，Spark系统也具备批处理计算的能力。
　　3.?流式计算模式与典型系统
　　流式计算是一种高实时性的计算模式，需要对一定时间窗口内应用系统产生的新数据完成实时的计算处理，避免造成数据堆积和丢失。很多行业的大数据应用，如电信、电力、道路监控等行业应用以及互联网行业的访问日志处理，都同时具有高流量的流式数据和大量积累的历史数据，因而在提供批处理计算模式的同时，系统还需要能具备高实时性的流式计算能力。流式计算的一个特点是数据运动、运算不动，不同的运算节点常常绑定在不同的服务器上。
　　Facebook的Scribe和Apache的Flume都提供了一定的机制来构建日志数据处理流图。而更为通用的流式计算系统是Twitter公司的Storm、Yahoo公司的S4以及Apache Spark Steaming。
　　4.?迭代计算模式与典型系统
　　为了克服Hadoop MapReduce难以支持迭代计算的缺陷，工业界和学术界对Hadoop MapReduce进行了不少改进研究。HaLoop把迭代控制放到MapReduce作业执行的框架内部，并通过循环敏感的调度器保证前次迭代的Reduce输出和本次迭代的Map输入数据在同一台物理机上，以减少迭代间的数据传输开销；iMapReduce在这个基础上保持Map和Reduce任务的持久性，规避启动和调度开销；而Twister在前两者的基础上进一步引入了可缓存的Map和Reduce对象，利用内存计算和pub/sub网络进行跨节点数据传输。
　　目前，一个具有快速和灵活的迭代计算能力的典型系统是Spark，其采用了基于内存的RDD数据集模型实现快速的迭代计算。
　　5.?图计算模式与典型系统
　　社交网络、Web链接关系图等都包含大量具有复杂关系的图数据，这些图数据规模很大，常常达到数十亿的顶点和上万亿的边数。这样大的数据规模和非常复杂的数据关系，给图数据的存储管理和计算分析带来了很大的技术难题。用MapReduce计算模式处理这种具有复杂数据关系的图数据通常不能适应，为此，需要引入图计算模式。
　　大规模图数据处理首先要解决数据的存储管理问题，通常大规模图数据也需要使用分布式存储方式。但是，由于图数据具有很强的数据关系，分布式存储就带来了一个重要的图划分问题（Graph Partitioning）。根据图数据问题本身的特点，图划分可以使用“边切分”和“顶点切分”两种方式。在有效的图划分策略下，大规模图数据得以分布存储在不同节点上，并在每个节点上对本地子图进行并行化处理。与任务并行和数据并行的概念类似，由于图数据并行处理的特殊性，人们提出了一个新的“图并行”（Graph Parallel）的概念。事实上，图并行是数据并行的一个特殊形式，需要针对图数据处理的特征考虑一些特殊的数据组织模型和计算方法。
　　目前已经出现了很多分布式图计算系统，其中较为典型的系统包括Google公司的Pregel、Facebook对Pregel的开源实现Giraph、微软公司的Trinity、Spark下的GraphX，以及CMU的GraphLab以及由其衍生出来的目前性能最快的图数据处理系统PowerGraph。
　　6.?内存计算模式与典型系统
　　Hadoop MapReduce为大数据处理提供了一个很好的平台。然而，由于MapReduce设计之初是为大数据线下批处理而设计的，随着数据规模的不断扩大，对于很多需要高响应性能的大数据查询分析计算问题，现有的以Hadoop为代表的大数据处理平台在计算性能上往往难以满足要求。随着内存价格的不断下降以及服务器可配置的内存容量的不断提高，用内存计算完成高速的大数据处理已经成为大数据计算的一个重要发展趋势。例如，Hana系统设计者总结了很多实际的商业应用后发现，一个提供50TB总内存容量的计算集群将能够满足绝大多数现有的商业系统对大数据的查询分析处理要求，如果一个服务器节点可配置1TB～2TB的内存，则需要25～50个服务器节点。目前Intel Xeon E-7系列处理器最大可支持高达1.5TB的内存，因此，配置一个上述大小规模的内存计算集群是可以做到的。
　　1.2.5大数据计算模式的发展趋势
　　近几年来，由于大数据处理和应用需求急剧增长，同时也由于大数据处理的多样性和复杂性，针对以上的典型的大数据计算模式，学术界和工业界不断研究推出新的或改进的计算模式和系统工具平台。目前主要有以下三方面的重要发展趋势和方向：Hadoop性能提升和功能增强，混合式大数据计算模式，以及基于内存计算的大数据计算模式和技术。
　　1.?Hadoop性能提升和功能增强
　　尽管Hadoop还存在很多不足，但由于Hadoop已发展成为目前最主流的大数据处理平台、并得到广泛的使用，因此，目前人们并不会抛弃Hadoop平台，而是试图不断改进和发展现有的平台，增加其对各种不同大数据处理问题的适用性。目前，Hadoop社区正努力扩展现有的计算模式框架和平台，以便能解决现有版本在计算性能、计算模式、系统构架和处理能力上的诸多不足，这正是目前Hadoop2.0新版本“YARN”的努力目标。目前不断有新的计算模式和计算系统出现，预计今后相当长一段时间内，Hadoop平台将与各种新的计算模式和系统共存，并相互融合，形成新一代的大数据处理系统和平台。
　　2.?混合式计算模式
　　现实世界大数据应用复杂多样，可能会同时包含不同特征的数据和计算，在这种情况下单一的计算模式多半难以满足整个应用的需求，因此需要考虑不同计算模式的混搭使用。
　　混合式计算模式可体现在两个层面上。一个层面是传统并行计算所关注的体系结构与低层并行程序设计语言层面计算模式的混合，例如，在体系结构层，可根据大数据应用问题的需要搭建混合式的系统构架，如MapReduce集群+GPU-CUDA的混合，或者MapReduce集群+基于MIC（Intel Xeon Phi众核协处理系统）的OpenMP/MPI的混合模型。
　　混合模型的另一个层面是以上所述的大数据处理高层计算模式的混合。比如，一个大数据应用可能同时需要提供流式计算模式以便接收每天产生的大量流式数据，这些数据得到保存后成为历史数据，此时会需要提供基于SQL或NoSQL的数据查询分析能力以便进行日常的数据查询分析；进一步，为了进行商业智能分析，可能还需要进行基于机器学习的深度数据挖掘分析，此时系统需要能提供线下批处理计算模式以及复杂机器学习算法的迭代计算模式；一些大数据计算任务可能还直接涉及到复杂图计算或者间接转化为图计算问题。因此，很多大数据处理问题都需要有多种混合计算模式的支持。此外，为了提高各种计算模式处理大数据时的计算性能，各种计算模式都在与内存计算模式混合，实现高实时性的大数据查询和计算分析。
　　混合计算模式之集大成者当属UC Berkeley AMPLab研发、现已成为Apache开源项目的Spark系统，其涵盖了几乎所有典型的大数据计算模式，包括迭代计算、批处理计算、内存计算、流式计算（Spark Streaming）、数据查询分析计算（Shark）以及图计算（GraphX），提供了优异的计算性能，同时还保持与Hadoop平台的兼容性。
　　3.?内存计算
　　为了进一步提高大数据处理的性能，目前已经出现一个基本共识，即随着内存成本的不断降低，内存计算将成为最终跨越大数据计算性能障碍、实现高实时高响应计算的一个最有效的技术手段。因此，目前越来越多的研究者和开发者在关注基于内存计算的大数据处理技术，不断推出各种基于内存计算的计算模式和系统。
　　内存计算是一种在体系结构层面上的解决方法，因此可以适用于各种不同的计算模式，从基本的数据查询分析计算，到批处理计算和流式计算，再到迭代计算和图计算，都可以基于内存计算加以实现，因此我们可以看到各种大数据计算模式下都有基于内存计算实现的系统，比较典型的系统包括SAP公司的Hana内存数据库、开源的键值对内存数据库Redis、微软公司的图数据计算系统Trinity、Apache Spark等。
　　1.2.6大数据的主要技术层面和技术内容
　　大数据是诸多计算技术的融合。从大的方面来分，大数据技术与研究主要分为大数据基础理论、大数据关键技术和系统、大数据应用以及大数据信息资源库等几个重要方面。
　　从信息系统的角度来看，大数据处理是一个涉及整个软硬件系统各个层面的综合性信息处理技术。从信息系统角度可将大数据处理分为基础设施层、系统软件层、并行化算法层以及应用层。图1-12所示是从信息处理系统角度所看到的大数据技术的主要技术层面和技术内容。
　　图1-12从信息处理系统角度看大数据的主要技术层面与技术内容
　　1.?基础设施层
　　基础设施层主要提供大数据分布存储和并行计算的硬件基础设施和平台。目前大数据处理通用化的硬件设施是基于普通商用服务器的集群，在有特殊的数据处理需要时，这种通用化的集群也可以结合其他类型的并行计算设施一起工作，如基于众核的并行处理系统（如GPU或者Intel新近推出的MIC），形成一种混合式的大数据并行处理构架和硬件平台。此外，随着云计算技术的发展，也可以与云计算资源管理和平台结合，在云计算平台上部署大数据基础设施，运用云计算平台中的虚拟化和弹性资源调度技术，为大数据处理提供可伸缩的计算资源和基础设施。
　　2.?系统软件层
　　在系统软件层，需要考虑大数据的存储管理和并行化计算系统软件。
　　（1）分布式文件系统与数据查询管理系统
　　大数据处理首先面临的是如何解决大数据的存储管理问题。为了提供巨大的数据存储能力，人们的普遍共识是，利用分布式存储技术和系统提供可扩展的大数据存储能力。
　　首先需要有一个底层的分布式文件系统，以可扩展的方式支持对大规模数据文件的有效存储管理。但文件系统主要是以文件方式提供一个最基础性的大数据存储方式，其缺少结构化/半结构化数据的存储管理和访问能力，而且其编程接口对于很多应用来说还是太底层了。传统的数据库技术主要适用于规模相对较小的结构化数据的存储管理和查询，当数据规模增大或者要处理很多非结构化或半结构化数据时，传统数据库技术和系统将难以胜任。现实世界中的大数据不仅数据量大，而且具有多样化的形态特征。据统计，现实世界80%的数据都是非结构化或半结构化的。因此，系统软件层还需要研究解决大数据的存储管理和查询问题。由于SQL不太适用于非结构化/半结构化数据的管理查询，因此，人们提出了一种NoSQL的数据管理查询模式。但是，人们发现，最理想的还是能提供统一的数据管理查询方法，能对付各种不同类型的数据的查询管理。为此，人们进一步提出了NewSQL的概念和技术。
　　（2）大数据并行计算模式和系统
　　解决了大数据的存储问题后，进一步面临的问题是，如何能快速有效地完成大规模数据的计算。大数据的数据规模之大，使得现有的串行计算方法难以在可接受的时间里快速完成大数据的处理和计算。为了提高大数据处理的效率，需要使用大数据并行计算模型和框架来支撑大数据的计算处理。目前最主流的大数据并行计算和框架是Hadoop MapReduce技术。与此同时，近年来人们开始研究并提供不同的大数据计算模型和方法，包括高实时低延迟要求的流式计算，具有复杂数据关系的图计算，面向基本数据管理的查询分析类计算，以及面向复杂数据分析挖掘的迭代和交互计算等。在大多数场景下，由于数据量巨大，大数据处理通常很难达到实时或低延迟响应。为了解决这个问题，近年来，人们提出了内存计算的概念和方法，尽可能利用大内存完成大数据的计算处理，以实现尽可能高的实时或低延迟响应。目前Spark已成为一个具有很大发展前景的新的大数据计算系统和平台，正受到工业界和学术界的广泛关注，有望成为与Hadoop并存的一种新的计算系统和平台。
　　3.?并行化算法层
　　基于以上的基础设施层和系统软件层，为了完成大数据的并行化处理，进一步需要考虑的问题是，如何能对各种大数据处理所需要的分析挖掘算法进行并行化设计。
　　大数据分析挖掘算法大多最终会归结到基础性的机器学习和数据挖掘算法上来。然而，面向大数据处理时，绝大多数现有的串行化机器学习和数据挖掘算法都难以在可接受的时间内有效完成大数据处理，因此，这些已有的机器学习和数据挖掘算法都需要进行并行化的设计和改造。
　　除此以外，还需要考虑很多更贴近上层具体应用和领域问题的应用层算法，例如，社会网络分析、分析推荐、商业智能分析、Web搜索与挖掘、媒体分析检索、自然语言理解与分析、语义分析与检索、可视化分析等，虽然这些算法最终大都会归结到底层的机器学习和数据挖掘算法上，但它们本身会涉及到很多高层的特定算法问题，所有这些高层算法本身在面向大数据处理时也需要考虑如何进行并行化算法设计。
　　4.?应用层
　　基于上述三个层面，可以构建各种行业或领域的大数据应用系统。大数据应用系统首先需要提供和使用各种大数据应用开发运行环境与工具；进一步，大数据应用开发的一个特别问题是，需要有应用领域的专家归纳行业应用问题和需求、构建行业应用和业务模型，这些模型往往需要专门的领域知识，没有应用行业领域专家的配合，单纯的计算机专业专业技术人员往往会无能为力，难以下手。只有在领域专家清晰构建了应用问题和业务模型后，计算机专业人员才能顺利完成应用系统的设计与开发。行业大数据分析和价值发现会涉及到很多复杂的行业和领域专业知识，这一特征在今天的大数据时代比以往任何时候都更为突出，这就是为什么我们在大数据研究原则中明确提出，大数据的研究应用需要以应用需求为导向、领域交叉为桥梁，从实际行业应用问题和需求出发，由行业和领域专家与计算机技术人员相互配合和协同，以完成大数据行业应用的开发。
　　1.3MapReduce并行计算技术简介
　　1.3.1MapReduce的基本概念和由来
　　1.?什么是MapReduce
　　MapReduce是面向大数据并行处理的计算模型、框架和平台，它隐含了以下三层含义：
　　1）MapReduce是一个基于集群的高性能并行计算平台（Cluster Infrastructure）。它允许用市场上普通的商用服务器构成一个包含数十、数百至数千个节点的分布和并行计算集群。
　　2）MapReduce是一个并行计算与运行软件框架（Software Framework）。它提供了一个庞大但设计精良的并行计算软件框架，能自动完成计算任务的并行化处理，自动划分计算数据和计算任务，在集群节点上自动分配和执行任务以及收集计算结果，将数据分布存储、数据通信、容错处理等并行计算涉及到的很多系统底层的复杂细节交由系统负责处理，大大减少了软件开发人员的负担。
　　3）MapReduce是一个并行程序设计模型与方法（Programming Model & Methodology）。它借助于函数式程序设计语言Lisp的设计思想，提供了一种简便的并行程序设计方法，用Map和Reduce两个函数编程实现基本的并行计算任务，提供了抽象的操作和并行编程接口，以简单方便地完成大规模数据的编程和计算处理。
　　2.?MapReduce的由来
　　MapReduce最早是由Google公司研究提出的一种面向大规模数据处理的并行计算模型和方法。Google公司设计MapReduce的初衷主要是为了解决其搜索引擎中大规模网页数据的并行化处理。Google公司发明了MapReduce之后首先用其重新改写了其搜索引擎中的Web文档索引处理系统。但由于MapReduce可以普遍应用于很多大规模数据的计算问题，因此自发明MapReduce以后，Google公司内部进一步将其广泛应用于很多大规模数据处理问题。到目前为止，Google公司内有上万个各种不同的算法问题和程序都使用MapReduce进行处理。
　　2003年和2004年，Google公司在国际会议上分别发表了两篇关于Google分布式文件系统和MapReduce的论文，公布了Google的GFS和MapReduce的基本原理和主要设计思想。2004年，开源项目Lucene（搜索索引程序库）和Nutch（搜索引擎）的创始人Doug Cutting发现MapReduce正是其所需要的解决大规模Web数据处理的重要技术，因而模仿Google MapReduce，基于Java设计开发了一个称为Hadoop的开源MapReduce并行计算框架和系统。自此，Hadoop成为Apache开源组织下最重要的项目，自其推出后很快得到了全球学术界和工业界的普遍关注，并得到推广和普及应用。
　　MapReduce的推出给大数据并行处理带来了巨大的革命性影响，使其已经成为事实上的大数据处理的工业标准。尽管MapReduce还有很多局限性，但人们普遍公认，MapReduce是到目前为止最为成功、最广为接受和最易于使用的大数据并行处理技术。MapReduce的发展普及和带来的巨大影响远远超出了发明者和开源社区当初的意料，以至于马里兰大学教授、2010年出版的《Data-Intensive Text Processing with MapReduce》一书的作者Jimmy Lin在书中提出：MapReduce改变了我们组织大规模计算的方式，它代表了第一个有别于冯·诺依曼结构的计算模型，是在集群规模而非单个机器上组织大规模计算的新的抽象模型上的第一个重大突破，是到目前为止所见到的最为成功的基于大规模计算资源的计算模型。
　　1.3.2MapReduce的基本设计思想
　　面向大规模数据处理，MapReduce有以下三个层面上的基本设计思想。
　　1.?对付大数据并行处理：分而治之
　　一个大数据若可以分为具有同样计算过程的数据块，并且这些数据块之间不存在数据依赖关系，则提高处理速度的最好办法就是采用“分而治之”的策略进行并行化计算。MapReduce采用了这种“分而治之”的设计思想，对相互间不具有或者有较少数据依赖关系的大数据，用一定的数据划分方法对数据分片，然后将每个数据分片交由一个节点去处理，最后汇总处理结果。
　　2.?上升到抽象模型：Map与Reduce
　　（1）Lisp语言中的Map和Reduce
　　MapReduce借鉴了函数式程序设计语言Lisp的设计思想。Lisp是一种列表处理语言。它是一种应用于人工智能处理的符号式语言，由MIT的人工智能专家、图灵奖获得者John McCarthy于1958年设计发明。
　　Lisp定义了可对列表元素进行整体处理的各种操作，如：
　　 （add#（1 2 3 4）#（4 3 2 1））将产生结果：#（5 5 5 5）
　　Lisp中也提供了类似于Map和Reduce的操作，如：
　　 （map'vector#+#（1 2 3 4）#（4 3 2 1））
　　通过定义加法map运算将两个向量相加产生与前述add运算同样的结果#（5 5 5 5）。
　　进一步，Lisp也可以定义reduce操作进行某种归并运算，如：
　　 （reduce#'+#（1 2 3 4））通过加法归并产生累加结果10。
　　（2）MapReduce中的Map和Reduce
　　MPI等并行计算方法缺少高层并行编程模型，为了克服这一缺陷，MapReduce借鉴了Lisp函数式语言中的思想，用Map和Reduce两个函数提供了高层的并行编程抽象模型和接口，程序员只要实现这两个基本接口即可快速完成并行化程序的设计。
　　与Lisp语言可以用来处理列表数据一样，MapReduce的设计目标是可以对一组顺序组织的数据元素/记录进行处理。现实生活中，大数据往往是由一组重复的数据元素/记录组成，例如，一个Web访问日志文件数据会由大量的重复性的访问日志构成，对这种顺序式数据元素/记录的处理通常也是顺序式扫描处理。图1-13描述了典型的顺序式大数据处理的过程和特征：
　　图1-13典型的顺序式大数据处理过程和特征
　　MapReduce将以上的处理过程抽象为两个基本操作，把上述处理过程中的前两步抽象为Map操作，把后两步抽象为Reduce操作。于是Map操作主要负责对一组数据记录进行某种重复处理，而Reduce操作主要负责对Map的中间结果进行某种进一步的结果整理和输出。以这种方式，MapReduce为大数据处理过程中的主要处理操作提供了一种抽象机制。
　　3.?上升到构架：以统一构架为程序员隐藏系统层细节
　　MPI等并行计算方法缺少统一的计算框架支持，程序员需要考虑数据存储、划分、分发、结果收集、错误恢复等诸多细节；为此，MapReduce设计并提供了统一的计算框架，为程序员隐藏了绝大多数系统层面的处理细节，程序员只需要集中于应用问题和算法本身，而不需要关注其他系统层的处理细节，大大减轻了程序员开发程序的负担。
　　MapReduce所提供的统一计算框架的主要目标是，实现自动并行化计算，为程序员隐藏系统层细节。该统一框架可负责自动完成以下系统底层相关的处理：
　　1）计算任务的自动划分和调度。
　　2）数据的自动化分布存储和划分。
　　3）处理数据与计算任务的同步。
　　4）结果数据的收集整理（sorting，combining，partitioning，等）。
　　5）系统通信、负载平衡、计算性能优化处理。
　　6）处理系统节点出错检测和失效恢复。
　　1.3.3MapReduce的主要功能和技术特征
　　1.?MapReduce的主要功能
　　MapReduce通过抽象模型和计算框架把需要做什么（What need to do）与具体怎么做（How to do）分开了，为程序员提供了一个抽象和高层的编程接口和框架，程序员仅需要关心其应用层的具体计算问题，仅需编写少量的处理应用本身计算问题的程序代码；如何具体完成这个并行计算任务所相关的诸多系统层细节被隐藏起来，交给计算框架去处理：从分布代码的执行，到大到数千、小到数个节点集群的自动调度使用。
　　MapReduce提供了以下的主要功能：
　　1）数据划分和计算任务调度：系统自动将一个作业（Job）待处理的大数据划分为很多个数据块，每个数据块对应于一个计算任务（Task），并自动调度计算节点来处理相应的数据块。作业和任务调度功能主要负责分配和调度计算节点（Map节点或Reduce节点），同时负责监控这些节点的执行状态，并负责Map节点执行的同步控制。
　　2）数据/代码互定位：为了减少数据通信，一个基本原则是本地化数据处理，即一个计算节点尽可能处理其本地磁盘上所分布存储的数据，这实现了代码向数据的迁移；当无法进行这种本地化数据处理时，再寻找其他可用节点并将数据从网络上传送给该节点（数据向代码迁移），但将尽可能从数据所在的本地机架上寻找可用节点以减少通信延迟。
　　3）系统优化：为了减少数据通信开销，中间结果数据进入Reduce节点前会进行一定的合并处理；一个Reduce节点所处理的数据可能会来自多个Map节点，为了避免Reduce计算阶段发生数据相关性，Map节点输出的中间结果需使用一定的策略进行适当的划分处理，保证相关性数据发送到同一个Reduce节点；此外，系统还进行一些计算性能优化处理，如对最慢的计算任务采用多备份执行、选最快完成者作为结果。
　　4）出错检测和恢复：以低端商用服务器构成的大规模MapReduce计算集群中，节点硬件（主机、磁盘、内存等）出错和软件出错是常态，因此MapReduce需要能检测并隔离出错节点，并调度分配新的节点接管出错节点的计算任务。同时，系统还将维护数据存储的可靠性，用多备份冗余存储机制提高数据存储的可靠性，并能及时检测和恢复出错的数据。
　　2.?MapReduce的主要技术特征
　　MapReduce设计上具有以下主要的技术特征：
　　1）向“外”横向扩展，而非向“上”纵向扩展
　　即MapReduce集群的构建完全选用价格便宜、易于扩展的低端商用服务器，而非价格昂贵、不易扩展的高端服务器。对于大规模数据处理，由于有大量数据存储需要，显而易见，基于低端服务器的集群远比基于高端服务器的集群优越，这就是为什么MapReduce并行计算集群会基于低端服务器实现的原因。
　　2）失效被认为是常态
　　MapReduce集群中使用大量的低端服务器，因此，节点硬件失效和软件出错是常态，因而一个良好设计、具有高容错性的并行计算系统不能因为节点失效而影响计算服务的质量，任何节点失效都不应当导致结果的不一致或不确定性；任何一个节点失效时，其他节点要能够无缝接管失效节点的计算任务；当失效节点恢复后应能自动无缝加入集群，而不需要管理员人工进行系统配置。MapReduce并行计算软件框架使用了多种有效的错误检测和恢复机制，如节点自动重启技术，使集群和计算框架具有对付节点失效的健壮性，能有效处理失效节点的检测和恢复。
　　3）把处理向数据迁移
　　传统高性能计算系统通常有很多处理器节点与一些外存储器节点相连，如用存储区域网络（Storage Area，SAN Network）连接的磁盘阵列，因此，大规模数据处理时外存文件数据I/O访问会成为一个制约系统性能的瓶颈。为了减少大规模数据并行计算系统中的数据通信开销，代之以把数据传送到处理节点（数据向处理器或代码迁移），应当考虑将处理向数据靠拢和迁移。MapReduce采用了数据/代码互定位的技术方法，计算节点将首先尽量负责计算其本地存储的数据，以发挥数据本地化特点，仅当节点无法处理本地数据时，再采用就近原则寻找其他可用计算节点，并把数据传送到该可用计算节点。
　　4）顺序处理数据、避免随机访问数据
　　大规模数据处理的特点决定了大量的数据记录难以全部存放在内存，而通常只能放在外存中进行处理。由于磁盘的顺序访问要远比随机访问快得多，因此MapReduce主要设计为面向顺序式大规模数据的磁盘访问处理。为了实现面向大数据集批处理的高吞吐量的并行处理，MapReduce可以利用集群中的大量数据存储节点同时访问数据，以此利用分布集群中大量节点上的磁盘集合提供高带宽的数据访问和传输。
　　5）为应用开发者隐藏系统层细节
　　软件工程实践指南中，专业程序员认为之所以写程序困难，是因为程序员需要记住太多的编程细节（从变量名到复杂算法的边界情况处理），这对大脑记忆是一个巨大的认知负担，需要高度集中注意力；而并行程序编写有更多困难，如需要考虑多线程中诸如同步等复杂繁琐的细节。由于并发执行中的不可预测性，程序的调试查错也十分困难；而且，大规模数据处理时程序员需要考虑诸如数据分布存储管理、数据分发、数据通信和同步、计算结果收集等诸多细节问题。MapReduce提供了一种抽象机制将程序员与系统层细节隔离开来，程序员仅需描述需要计算什么（What to compute），而具体怎么去计算（How to compute）就交由系统的执行框架处理，这样程序员可从系统层细节中解放出来，而致力于其应用本身计算问题的算法设计。
　　6）平滑无缝的可扩展性
　　这里指出的可扩展性主要包括两层意义上的扩展性：数据扩展和系统规模扩展性。理想的软件算法应当能随着数据规模的扩大而表现出持续的有效性，性能上的下降程度应与数据规模扩大的倍数相当；在集群规模上，要求算法的计算性能应能随着节点数的增加保持接近线性程度的增长。绝大多数现有的单机算法都达不到以上理想的要求；把中间结果数据维护在内存中的单机算法在大规模数据处理时很快失效；从单机到基于大规模集群的并行计算从根本上需要完全不同的算法设计。奇妙的是，MapReduce在很多情形下能实现以上理想的扩展性特征。多项研究发现，对于很多计算问题，基于MapReduce的计算性能可随节点数目增长保持近似于线性的增长。
　　1.4Hadoop系统简介
　　1.4.1Hadoop的概述与发展历史
　　Hadoop系统最初的源头来自于Apache Lucene项目下的搜索引擎子项目Nutch，该项目的负责人是Doug Cutting。2003年，Google公司为了解决其搜索引擎中大规模Web网页数据的处理，研究发明了一套称为MapReduce的大规模数据并行处理技术，并于2004年在著名的OSDI国际会议上发表了一篇题为“MapReduce:Simplified Data Processing on Large Clusters”的论文，简要介绍MapReduce的基本设计思想。论文发表后，Doug Cutting受到了很大启发，他发现Google MapReduce所解决的大规模搜索引擎数据处理问题，正是他同样面临并急需解决的问题。因而，他尝试依据Google MapReduce的设计思想，模仿Google MapReduce框架的设计思路，用Java设计实现出了一套新的MapReduce并行处理软件系统，并将其与Nutch分布式文件系统NDFS结合，用以支持Nutch搜索引擎的数据处理。2006年，他们把NDFS和MapReduce从Nutch项目中分离出来，成为一套独立的大规模数据处理软件系统，并使用Doug Cutting小儿子当时呀呀学语称呼自己的玩具小象的名字“Hadoop”命名了这个系统。2008年他们把Hadoop贡献出来，成为Apache最大的一个开源项目，并逐步发展成熟，成为一个包含了HDFS、MapReduce、HBase、Hive、Zookeeper等一系列相关子项目的大数据处理平台和生态系统。
　　Hadoop开源项目自最初推出后，经历了数十个版本的演进。它从最初于2007年推出的Hadoop-0.14.X测试版，一直发展到2011年5月推出了经过4500台服务器产品级测试的最早的稳定版0.20.203.X。到2011年12月，Hadoop又在0.20.205版基础上发布了Hadoop1.0.0，该版本到2012年3月发展为Hadoop1.0.1稳定版。1.0版继续发展，到2013年8月发展为Hadoop1.2.1稳定版。
　　与此同时，由于Hadoop1.X以前版本在MapReduce基本构架的设计上存在作业主控节点（JobTracker）单点瓶颈、作业执行延迟过长、编程框架不灵活等较多的缺陷和不足，2011年10月，Hadoop推出了基于新一代构架的Hadoop0.23.0测试版，该版本系列最终演化为Hadoop2.0版本，即新一代的Hadoop系统YARN。2013年10月YARN已经发展出Hadoop2.2.0稳定版。
　　1.4.2Hadoop系统分布式存储与并行计算构架
　　图1-14展示了Hadoop系统的分布式存储和并行计算构架。从硬件体系结构上看，Hadoop系统是一个运行于普通的商用服务器集群的分布式存储和并行计算系统。集群中将有一个主控节点用来控制和管理整个集群的正常运行，并协调管理集群中各个从节点完成数据存储和计算任务。每个从节点将同时担任数据存储节点和数据计算节点两种角色，这样设计的目的主要是在大数据环境下实现尽可能的本地化计算，以此提高系统的处理性能。为了能及时检测和发现集群中某个从节点发生故障失效，主控节点采用心跳机制（Heartbeat）定期检测从节点，如果从节点不能有效回应心跳信息，则系统认为这个从节点失效。
　　图1-14Hadoop系统分布式存储与并行计算构架
　　从软件系统角度看，Hadoop系统包括分布式存储和并行计算两个部分。分布式存储构架上，Hadoop基于每个从节点上的本地文件系统，构建一个逻辑上整体化的分布式文件系统，以此提供大规模可扩展的分布式数据存储功能，这个分布式文件系统称为HDFS（Hadoop Distributed File System），其中，负责控制和管理整个分布式文件系统的主控节点称为NameNode，而每个具体负责数据存储的从节点称为DataNode。
　　进一步，为了能对存储在HDFS中的大规模数据进行并行化的计算处理，Hadoop又提供了一个称为MapReduce的并行化计算框架。该框架能有效管理和调度整个集群中的节点来完成并行化程序的执行和数据处理，并能让每个从节点尽可能对本地节点上的数据进行本地化计算，其中，负责管理和调度整个集群进行计算的主控节点称为JobTracker，而每个负责具体的数据计算的从节点称为TaskTracker。JobTracker可以与负责管理数据存储的主控节点NameNode设置在同一个物理的主控服务器上，在系统规模较大、各自负载较重时两者也可以分开设置。但数据存储节点DataNode与计算节点TaskTracker会配对地设置在同一个物理的从节点服务器上。
　　Hadoop系统中的其他子系统，例如HBase、Hive等，将建立在上述HDFS分布式文件系统和MapReduce并行化计算框架之上。
　　1.4.3Hadoop平台的基本组成与生态系统
　　Hadoop系统运行于一个由普通商用服务器组成的计算集群上，该服务器集群在提供大规模分布式数据存储资源的同时，也提供大规模的并行化计算资源。
　　在大数据处理软件系统上，随着Apache Hadoop系统开源化的发展，在最初包含HDFS、MapReduce、HBase等基本子系统的基础上，至今Hadoop平台已经演进为一个包含很多相关子系统的完整的大数据处理生态系统。图1-15展示了Hadoop平台的基本组成与生态系统。
　　图1-15Hadoop平台的基本组成与生态系统
　　1.?MapReduce并行计算框架
　　MapReduce并行计算框架是一个并行化程序执行系统。它提供了一个包含Map和Reduce两阶段的并行处理模型和过程，提供一个并行化编程模型和接口，让程序员可以方便快速地编写出大数据并行处理程序。MapReduce以键值对数据输入方式来处理数据，并能自动完成数据的划分和调度管理。在程序执行时，MapReduce并行计算框架将负责调度和分配计算资源，划分和输入输出数据，调度程序的执行，监控程序的执行状态，并负责程序执行时各计算节点的同步以及中间结果的收集整理。MapReduce框架提供了一组完整的供程序员开发MapReduce应用程序的编程接口。
　　2.?分布式文件系统HDFS
　　HDFS（Hadoop Distributed File System）是一个类似于Google GFS的开源的分布式文件系统。它提供了一个可扩展、高可靠、高可用的大规模数据分布式存储管理系统，基于物理上分布在各个数据存储节点的本地Linux系统的文件系统，为上层应用程序提供了一个逻辑上成为整体的大规模数据存储文件系统。与GFS类似，HDFS采用多副本（默认为3个副本）数据冗余存储机制，并提供了有效的数据出错检测和数据恢复机制，大大提高了数据存储的可靠性。
　　3.?分布式数据库管理系统HBase
　　为了克服HDFS难以管理结构化/半结构化海量数据的缺点，Hadoop提供了一个大规模分布式数据库管理和查询系统HBase。HBase是一个建立在HDFS之上的分布式数据库，它是一个分布式可扩展的NoSQL数据库，提供了对结构化、半结构化甚至非结构化大数据的实时读写和随机访问能力。HBase提供了一个基于行、列和时间戳的三维数据管理模型，HBase中每张表的记录数（行数）可以多达几十亿条甚至更多，每条记录可以拥有多达上百万的字段。
　　4.?公共服务模块Common
　　Common是一套为整个Hadoop系统提供底层支撑服务和常用工具的类库和API编程接口，这些底层服务包括Hadoop抽象文件系统FileSystem、远程过程调用RPC、系统配置工具Configuration以及序列化机制。在0.20及以前的版本中，Common包含HDFS、MapReduce和其他公共的项目内容；从0.21版本开始，HDFS和MapReduce被分离为独立的子项目，其余部分内容构成Hadoop Common。
　　5.?数据序列化系统Avro
　　Avro是一个数据序列化系统，用于将数据结构或数据对象转换成便于数据存储和网络传输的格式。Avro提供了丰富的数据结构类型，快速可压缩的二进制数据格式，存储持久性数据的文件集，远程调用RPC和简单动态语言集成等功能。
　　6.?分布式协调服务框架Zookeeper
　　Zookeeper是一个分布式协调服务框架，主要用于解决分布式环境中的一致性问题。Zookeeper主要用于提供分布式应用中经常需要的系统可靠性维护、数据状态同步、统一命名服务、分布式应用配置项管理等功能。Zookeeper可用来在分布式环境下维护系统运行管理中的一些数据量不大的重要状态数据，并提供监测数据状态变化的机制，以此配合其他Hadoop子系统（如HBase、Hama等）或者用户开发的应用系统，解决分布式环境下系统可靠性管理和数据状态维护等问题。
　　7.?分布式数据仓库处理工具Hive
　　Hive是一个建立在Hadoop之上的数据仓库，用于管理存储于HDFS或HBase中的结构化/半结构化数据。它最早由Facebook开发并用于处理并分析大量的用户及日志数据，2008年Facebook将其贡献给Apache成为Hadoop开源项目。为了便于熟悉SQL的传统数据库使用者使用Hadoop系统进行数据查询分析，Hive允许直接用类似SQL的HiveQL查询语言作为编程接口编写数据查询分析程序，并提供数据仓库所需要的数据抽取转换、存储管理和查询分析功能，而HiveQL语句在底层实现时被转换为相应的MapReduce程序加以执行。
　　8.?数据流处理工具Pig
　　Pig是一个用来处理大规模数据集的平台，由Yahoo!贡献给Apache成为开源项目。它简化了使用Hadoop进行数据分析处理的难度，提供一个面向领域的高层抽象语言Pig Latin，通过该语言，程序员可以将复杂的数据分析任务实现为Pig操作上的数据流脚本，这些脚本最终执行时将被系统自动转换为MapReduce任务链，在Hadoop上加以执行。Yahoo!有大量的MapReduce作业是通过Pig实现的。
　　9.?键值对数据库系统Cassandra
　　Cassandra是一套分布式的K-V型的数据库系统，最初由Facebook开发，用于存储邮箱等比较简单的格式化数据，后Facebook将Cassandra贡献出来成为Hadoop开源项目。Cassandra以Amazon专有的完全分布式Dynamo为基础，结合了Google BigTable基于列族（Column Family）的数据模型，提供了一套高度可扩展、最终一致、分布式的结构化键值存储系统。它结合了Dynamo的分布技术和Google的Bigtable数据模型，更好地满足了海量数据存储的需求。同时，Cassandra变更垂直扩展为水平扩展，相比其他典型的键值数据存储模型，Cassandra提供了更为丰富的功能。
　　10.?日志数据处理系统Chukwa
　　Chukwa是一个由Yahoo！贡献的开源的数据收集系统，主要用于日志的收集和数据的监控，并与MapReduce协同处理数据。Chukwa是一个基于Hadoop的大规模集群监控系统，继承了Hadoop系统的可靠性，具有良好的适应性和扩展性。它使用HDFS来存储数据，使用MapReduce来处理数据，同时还提供灵活强大的辅助工具用以分析、显示、监视数据结果。
　　11.?科学计算基础工具库Hama
　　Hama是一个基于BSP并行计算模型（Bulk Synchronous Parallel，大同步并行模型）的计算框架，主要提供一套支撑框架和工具，支持大规模科学计算或者具有复杂数据关联性的图计算。Hama类似Google公司开发的Pregel，Google利用Pregel来实现图遍历（BFS）、最短路径（SSSP）、PageRank等计算。Hama可以与Hadoop的HDSF进行完美的整合，利用HDFS对需要运行的任务和数据进行持久化存储。由于BSP在并行化计算模型上的灵活性，Hama框架可在大规模科学计算和图计算方面得到较多应用，完成矩阵计算、排序计算、PageRank、BFS等不同的大数据计算和处理任务。
　　12.?数据分析挖掘工具库Mahout
　　Mahout来源于Apache Lucene子项目，其主要目标是创建并提供经典的机器学习和数据挖掘并行化算法类库，以便减轻需要使用这些算法进行数据分析挖掘的程序员的编程负担，不需要自己再去实现这些算法。Mahout现在已经包含了聚类、分类、推荐引擎、频繁项集挖掘等广泛使用的机器学习和数据挖掘算法。此外，它还提供了包含数据输入输出工具，以及与其他数据存储管理系统进行数据集成的工具和构架。
　　13.?关系数据交换工具Sqoop
　　Sqoop是SQL-to-Hadoop的缩写，是一个在关系数据库与Hadoop平台间进行快速批量数据交换的工具。它可以将一个关系数据库中的数据批量导入Hadoop的HDFS、HBase、Hive中，也可以反过来将Hadoop平台中的数据导入关系数据库中。Sqoop充分利用了Hadoop MapReduce的并行化优点，整个数据交换过程基于MapReduce实现并行化的快速处理。
　　14.?日志数据收集工具Flume
　　Flume是由Cloudera开发维护的一个分布式、高可靠、高可用、适合复杂环境下大规模日志数据采集的系统。它将数据从产生、传输、处理、输出的过程抽象为数据流，并允许在数据源中定义数据发送方，从而支持收集基于各种不同传输协议的数据，并提供对日志数据进行简单的数据过滤、格式转换等处理能力。输出时，Flume可支持将日志数据写往用户定制的输出目标。
　　1.4.4Hadoop的应用现状和发展趋势
　　Hadoop因其在大数据处理领域具有广泛的实用性以及良好的易用性，自2007年推出后，很快在工业界得到普及应用，同时得到了学术界的广泛关注和研究。在短短的几年中，Hadoop很快成为到目前为止最为成功、最广泛接受使用的大数据处理主流技术和系统平台，并且成为一种大数据处理事实上的工业标准，得到了工业界大量的进一步开发和改进，并在业界和应用行业尤其是互联网行业得到了广泛的应用。由于在系统性能和功能方面存在不足，Hadoop在发展过程中进行了不断的改进，自2007年推出首个版本以来，目前已经先后推出数十个版本。
　　但是，由于其最初面向高吞吐率线下批处理的设计目标，以及起初系统构架设计上的诸多先天性的不足，尽管Hadoop开源社区一直致力于不断改进和完善系统，但是Hadoop1.X以前版本一直存在不少广为诟病的缺陷，包括主控节点单点瓶颈易造成系统拥堵和失效，作业执行响应性能较低难以满足高实时低延迟数据查询分析处理需求，固定的Map和Reduce两阶段模型框架难以提供灵活的编程能力、难以支持高效的迭代计算、流式计算、图数据计算等不同的计算和编程模式。
　　为此，在Hadoop0.20版本推出之后，Hadoop开源社区开始设计全新构架的新一代Hadoop系统，并于2011年10月推出了基于新一代构架的Hadoop0.23.0测试版，该版本后演化为Hadoop2.0版本，即新一代的Hadoop系统YARN。YARN构架将主控节点的资源管理和作业管理功能分离设置，引入了全局资源管理器（Resource Manager）和针对每个作业的应用主控管理器（Application Master），以此减轻原主控节点的负担，并可基于Zookeeper实现资源管理器的失效恢复，以此提高了Hadoop系统的高可用性（High Availability，HA）。YARN还引入了资源容器（Resource Container）的概念，将系统计算资源统一划分和封装为很多资源单元，不再像此前版本那样区分Map和Reduce计算资源，以此提高计算资源的利用率。此外，YARN还能容纳MapReduce以外的其他多种并行计算模型和框架，提高了Hadoop框架并行化编程的灵活性。
　　与此同时，由于Hadoop系统和框架对于不同大数据计算模式支持能力上的不足，在Hadoop开源社区之外，人们在不断研究推出可支持不同的大数据计算模式的系统。其中，目前最广为关注的当数加州大学伯克利分校AMP实验室（Algorithms，Machines，and People Lab）研究开发的Spark系统，该系统可广泛支持批处理、内存计算、流式计算、迭代计算、图数据计算等众多计算模式。然而，由于Hadoop系统在大规模数据分布存储和批处理能力，以及在系统的可扩展性和易用性上仍然具有不少其他系统所难以具备的优点，并且由于近几年来业界和应用行业在Hadoop开发和应用上已有大量的前期投入和上线应用系统，以及Hadoop所形成的包含各种丰富的工具软件的完整生态环境，同时也随着Hadoop自身向新一代系统的演进和不断改进，在今后相当长一段时间内，Hadoop系统将继续保持其在大数据处理领域的主流技术和平台的地位，同时其他各种新的系统也将逐步与Hadoop系统相互融合和共存。
　　在开源Hadoop系统发展的同时，工业界也有不少公司基于开源的Hadoop系统进行一系列的商业化版本开发，他们针对开源系统在系统性能优化、系统可用性和可靠性以及系统功能增强方面进行大量的研究和产品开发工作，形成商业化的发行版。最广为大家熟知的是Hadoop系统的创始者组织成立的Cloudera公司，研究开发了Hadoop商业发行版CDH，并在美国诸多的行业得到很好的推广应用。Intel公司自2009年以来也研究开发了Intel发行版Hadoop系统IDH，在中国诸多大型应用行业得到了良好的推广应用，本书第7章将详细介绍Intel Hadoop系统在性能优化和功能增强方面的主要技术内容和使用方法。