大数据处理框架Apache Spark设计与实现（全彩）

近年来，以Apache Spark为代表的大数据处理框架在学术界和工业界得到了广泛的使用。本书以Apache Spark框架为核心，总结了大数据处理框架的基础知识、核心理论、典型的Spark应用，以及相关的性能和可靠性问题。本书分9章，主要包含四部分内容。第一部分 大数据处理框架的基础知识（第1～2章）：介绍大数据处理框架的基本概念、系统架构、编程模型、相关的研究工作，并以一个典型的Spark应用为例概述Spark应用的执行流程。第二部分 Spark大数据处理框架的核心理论（第3～4章）：介绍Spark框架将应用程序转化为逻辑处理流程，进而转化为可并行执行的物理执行计划的一般过程及方法。第三部分 典型的Spark应用（第5章）：介绍迭代型的Spark机器学习应用和图计算应用。第四部分 大数据处理框架性能和可靠性保障机制（第6～9章）：介绍Spark框架的Shuffle机制、数据缓存机制、错误容忍机制、内存管理机制等。

许利杰现任中国科学院软件研究所副研究员、硕士生导师，于中科院软件所获得博士学位。当前主要从事大数据系统方面的研究工作，已在国际权威会议如VLDB、ICDCS、IPDPS、ISSRE、ICAC等发表论文10余篇，主持多项国家自然科学基金，以及华为、京东、联想等企业的合作研发项目。曾为Apache Spark和Hadoop修复多个内核代码严重错误，编写的SparkInternals技术文档被社区广泛关注，获得四千多颗星。博士期间曾在微软亚洲研究院、阿里巴巴、腾讯担任客座研究学生。目前还担任中国计算机学会系统软件专委会委员、中国科学院青年创新促进会会员。方亚芬现任中国科学院软件研究所工程师，于南开大学获得学士学位、中科院软件所获得硕士学位。当前主要从事大数据系统、操作系统方面的研发工作，参与多项国家自然科学基金、国家重点研发计划，以及华为、腾讯、中国邮政等企业的合作研发项目。曾在阿里巴巴等担任客座研究学生，目前是华为openEuler社区树莓派项目负责人。

目 录
第 1 章 大数据处理框架概览 ．．．．．．．．．．．．．．．．．．．．．2
1．1 大数据及其带来的挑战 ．．．．．．．．．．．．．．．．．．．．．2
1．2 大数据处理框架 ．．．．．．．．．．．．．．．．．．．．．．．．3
1．3 大数据应用及编程模型 ．．．．．．．．．．．．．．．．．．．．．4
1．4 大数据处理框架的四层结构 ．．．．．．．．．．．．．．．．．．．5
1．4．1 用户层 ．．．．．．．．．．．．．．．．．．．．．．．．．． 7
1．4．2 分布式数据并行处理层 ．．．．．．．．．．．．．．．．．．．11
1．4．3 资源管理与任务调度层 ．．．．．．．．．．．．．．．．．．．13
1．4．4 物理执行层 ．．．．．．．．．．．．．．．．．．．．．．．．15
1．5 错误容忍机制 ．．．．．．．．．．．．．．．．．．．．．．．．．17
1．6 其他大数据处理框架 ．．．．．．．．．．．．．．．．．．．．．．18
1．7 本章小结 ．．．．．．．．．．．．．．．．．．．．．．．．．．．18
1．8 扩展阅读 ．．．．．．．．．．．．．．．．．．．．．．．．．．．18
第 2 章 Spark 系统部署与应用运行的基本流程 ．．．．．．．．．．．．．20
2．1 Spark 安装部署 ．．．．．．．．．．．．．．．．．．．．．．．．20
2．2 Spark 系统架构 ．．．．．．．．．．．．．．．．．．．．．．．．21
2．3 Spark 应用例子 ．．．．．．．．．．．．．．．．．．．．．．．．24
2．3．1 用户代码基本逻辑 ．．．．．．．．．．．．．．．．．．． ．24
2．3．2 逻辑处理流程 ．．．．．．．．．．．．．．．．．．．．．．． 28
2．3．3 物理执行计划 ．．．．．．．．．．．．．．．．．．．．．．． 32
2．3．4 可视化执行过程 ．．．．．．．．．．．．．．．．．．．．．． 34
2．4 Spark 编程模型 ．．．．．．．．．．．．．．．．．．．．．．．．38
2．5 本章小结 ．．．．．．．．．．．．．．．．．．．．．．．．．．．39
第 3 章 Spark 逻辑处理流程 ．．．．．．．．．．．．．．．．．．．41
3．1 Spark 逻辑处理流程概览 ．．．．．．．．．．．．．．．．．．．．41
3．2 Spark 逻辑处理流程生成方法 ．．．．．．．．．．．．．．．．．．43
3．2．1 根据应用程序如何产生 RDD，产生什么样的 RDD ．．．．．．．．． 44
3．2．2 如何建立 RDD 之间的数据依赖 关系．．．．．．．．．．．． 44
3．2．3 如何计算 RDD 中的数据 ．．．．．．．．．．．．．．．．．． 49
3．3 常用 transformation() 数据操作 ．．．．．．．．．．．．．．．．50
3．4 常用 action() 数据操作 ．．．．．．．．．．．．．．．．．．86
3．5 对比 MapReduce，Spark 的优缺点．．．．．．．．．．．．．．．98
3．6 本章小结 ．．．．．．．．．．．．．．．．．．．．．．．．．99
3．7 扩展阅读 ．．．．．．．．．．．．．．．．．．．．．．．．．100
第 4 章 Spark 物理执行计划 ．．．．．．．．．．．．．．．．．．．101
4．1 Spark 物理执行计划概览 ．．．．．．．．．．．．．．．．．．101
4．2 Spark 物理执行计划生成方法 ．．．．．．．．．．．．．．．．105
4．3 常用数据操作生成的物理执行计划．．．．．．．．．．．．．．．113
4．4 本章小结 ．．．．．．．．．．．．．．．．．．．．．．．．．121
4．5 扩展阅读 ．．．．．．．．．．．．．．．．．．．．．．．．．121
第 5 章 迭代型 Spark 应用 ．．．．．．．．．．．．．．．．．．．123
5．1 迭代型 Spark 应用的分类及特点．．．．．．．．．．．．．．．123
5．2 迭代型机器学习应用 SparkLR ．．．．．．．．．．．．．．．．124
5．2．1 应用描述 ．．．．．．．．．．．．．．．．．．．．．．．．124
5．2．2 算法原理 ．．．．．．．．．．．．．．．．．．．．．．． 125
5．2．3 基于 Spark 的并行化实现 ．．．．．．．．．．．．．．．． 129
5．2．4 深入讨论 ．．．．．．．．．．．．．．．．．．．．．．． 131
5．3 迭代型机器学习应用――广义 线性模型．．．．．．．．．．．．132
5．3．1 算法原理 ．．．．．．．．．．．．．．．．．．．．．．． 132
5．3．2 基于 Spark 的并行化实现 ．．．．．．．．．．．．．．．． 136
5．3．3 深入讨论 ．．．．．．．．．．．．．．．．．．．．．．． 139
5．4 迭代型图计算应用――PageRank ．．．．．．．．．．．．．．．140
5．4．1 应用描述 ．．．．．．．．．．．．．．．．．．．．．．． 140
5．4．2 基于 Spark 的并行化实现 ．．．．．．．．．．．．．．．． 143
5．4．3 深入讨论 ．．．．．．．．．．．．．．．．．．．．．．． 149
5．5 本章小结 ．．．．．．．．．．．．．．．．．．．．．．．．．151
第 6 章 Shuffle 机制 ．．．．．．．．．．．．．．．．．．．．．．153
6．1 Shuffle 的意义及设计挑战 ．．．．．．．．．．．．．．．．．153
6．2 Shuffle 的设计思想 ．．．．．．．．．．．．．．．．．．．．155
6．2．1 解决数据分区和数据聚合问题 ．．．．．．．．．．．．．．．156
6．2．2 解决 map() 端 combine问题 ．．．．．．．．．．．．．．． 158
6．2．3 解决 sort 问题 ．．．．．．．．．．．．．．．．．．．．． 158
6．2．4 解决内存不足问题 ．．．．．．．．．．．．．．．．．．．． 159
6．3 Spark 中 Shuffle 框架的设计 ．．．．．．．．．．．．．．．160
6．3．1 Shuffle Write 框架设计和实现 ．．．．．．．．．．．．．．． 161
6．3．2 Shuffle Read 框架设计和实现 ．．．．．．．．．．．．． 166
6．4 支持高效聚合和排序的数据 结构．．．．．．．．．．．．．．170
6．4．1 AppendOnlyMap 的原理 ．．．．．．．．．．．．．．．．． 171
6．4．2 ExternalAppendOnlyMap ．．．．．．．．．．．．．．．．173
6．4．3 PartitionedAppendOnlyMap ．．．．．．．．．．．．．． 176
6．4．4 PartitionedPairBuffer ．．．．．．．．．．．．．．．． 176
6．5 与 Hadoop MapReduce 的 Shuffle 机制对比．．．．．．．．．177
6．6 本章小结 ．．．．．．．．．．．．．．．．．．．．．．．．179
第 7 章 数据缓存机制 ．．．．．．．．．．．．．．．．．．．．．．180
7．1 数据缓存的意义 ．．．．．．．．．．．．．．．．．．．．．．180
7．2 数据缓存机制的设计原理 ．．．．．．．．．．．．．．．．．．181
7．2．1 决定哪些数据需要被缓存 ．．．．．．．．．．．．．．．．181
7．2．2 包含数据缓存操作的逻辑处理流程和物理执行计划 ．．．．． 184
7．2．3 缓存级别 ．．．．．．．．．．．．．．．．．．．．．．． 186
7．2．4 缓存数据的写入方法 ．．．．．．．．．．．．．．．．．．189
7．2．5 缓存数据的读取方法 ．．．．．．．．．．．．．．．．．． 191
7．2．6 用户接口的设计 ．．．．．．．．．．．．．．．．．．．． 192
7．2．7 缓存数据的替换与回收方法 ．．．．．．．．．．．．．．．．．193
7．3 与 Hadoop MapReduce 的缓存机制进行对比．．．．．．．．．．．．197
7．4 本章小结 ．．．．．．．．．．．．．．．．．．．．．．．．．．198
第 8 章 错误容忍机制 ．．．．．．．．．．．．．．．．．．．．．．199
8．1 错误容忍机制的意义及挑战 ．．．．．．．．．．．．．．．．．．199
8．2 错误容忍机制的设计思想 ．．．．．．．．．．．．．．．．．．．201
8．3 重新计算机制 ．．．．．．．．．．．．．．．．．．．．．．．．201
8．3．1 重新计算是否能够得到与之前一样的结果 ．．．．．．．．．． 202
8．3．2 从哪里开始重新计算 ．．．．．．．．．．．．．．．．．．．204
8．3．3 重新计算机制小结 ．．．．．．．．．．．．．．．．．．．．207
8．4 checkpoint 机制的设计与实现 ．．．．．．．．．．．．．．．．207
8．4．1 哪些数据需要使用 checkpoint机制 ．．．．．．．．．．．． 207
8．4．2 checkpoint 数据的写入及接口 ．．．．．．．．．．．．．．．210
8．4．3 checkpoint 时机及计算顺序 ．．．．．．．．．．．．．．．．212
8．4．4 checkpoint 数据的读取 ．．．．．．．．．． ．．．．．．．213
8．4．5 checkpoint 数据写入和读取的实现细节 ．．．．．．．．．． 213
8．4．6 checkpoint 语句位置的影响．．．． ．．．．．．．．．．216
8．4．7 cache + checkpoint ．．．．．．．．．．．．．．．．．． 220
8．5 checkpoint 与数据缓存的区别 ．．．．．．．．．．．．．．．225
8．6 本章小结 ．．．．．．．．．．．．．．．．．．．．．．．．．226
第 9 章 内存管理机制 ．．．．．．．．．．．．．．．．．．．．．．227
9．1 内存管理机制问题及挑战 ．．．．．．．．．．．．．．．．．227
9．2 应用内存消耗来源及影响因素 ．．．．．．．．．．．．．．228
9．2．1 内存消耗来源 1：用户代码 ．．．．．．．．．．．．．． 229
9．2．2 内存消耗来源 2：Shuffle 机制中产生的中间数据 ．．．．．．230
9．2．3 内存消耗来源 3：缓存数据 ．．．．．．．．．．．．．． 231
9．3 Spark 框架内存管理模型 ．．．．．．．．．．．．．．．．．．232
9．3．1 静态内存管理模型 ．．．．．．．．．．．．．．．．．．．． 233
9．3．2 统一内存管理模型 ．．．．．．．．．．．．．．．．．．．． 234
9．4 Spark 框架执行内存消耗与管理．．．．．．．．．．．．．．．．237
9．4．1 Shuffle Write 阶段内存消耗及管理 ．．．．．．．．．．．． 239
9．4．2 Shuffle Read 阶段内存消耗及管理 ．．．．．．．．．．．．． 245
9．5 数据缓存空间管理 ．．．．．．．．．．．．．．．．．．．．．．．249
9．5．1 RDD 缓存数据 ．．．．．．．．．．．．．．．．．．．．．．． 250
9．5．2 广播数据 ．．．．．．．．．．．．．．．．．．．．．．．．． 253
9．5．3 task 的计算结果 ．．．．．．．．．．．．．．．．．．．．． 254
9．6 本章小结 ．．．．．．．．．．．．．．．．．．．．．．．．．．256
参考文献 ．．．．．．．．．．．．．．．．．．．．．．．．．．．．258