除了主要介绍spark，还有一些跟mapreduce对比的内容。

1 大数据处理框架概览

1.1 大数据处理框架的四层结构

1.1.1 用户层：数据输入、用户代码、配置参数

生成应用提交给计算框架
mr：driver负责设定输入输出数据类型，提交作业
spark：driver能产生数据、广播给task，收集task数据，在driver内计算结果等。

1.1.2 分布式数据并行处理层

把应用转化成计算任务，再分布式执行。

mr:map-shuffle-reduce
将分块数据进行map()，结果写入buffer，进行分区、排序、聚合，写到磁盘，reducetask拉取数据，也用buffer进行排序、归并，reduce()之后写到hdfs。

spark:分逻辑执行计划(rdd及数据依赖关系)，宽窄依赖分stage，物理执行计划(task)
spark没有明确的map task，reduce task，一个stage可以有多种task，而且一个job也可以有多个stage。

1.1.3 资源管理与任务调度层

一般就是yarn，mr还是spark都能跑，但是资源分配策略依赖于用户提交的资源需求和当前集群资源情况，不能根据应用的实际需求动态调整资源分配。

1.1.4 物理执行层

mr：一个task对应一个进程(jvm)，task内存用量就是jvm堆内存用量。
spark：一个task对应一个线程，一个jvm内的task共享内存空间，难以预测内存用量。

为什么这么设计呢？
=>方便task之间共享数据，不会重复加载，节省内存。
=>任务的启停，需要很多初始化之类的工作，进程比较影响效率，spark的设计是executor持有线程池。
=>也存在缺点，线程会形成资源竞争，多线程日志混乱等。

2 spark逻辑处理流程

2.1 组成

2.1.1 数据源(data blocks)

从hdfs,hbase甚至内存里的数据结构(parallelize)，流式处理还可以是网络流。

2.1.2 数据模型

mr里面是<K,V>形式的，只能map(K,V)或者reduce(K,list(V))，不灵活。
spark用的是rdd(resilient distributed datasets)

注：rdd与普通数据结构(比如list)比较

1. rdd是个逻辑概念，不占内存空间(除非缓存)，rdd中的数据是在内存里的，但是也只是在计算的时候，算完了就消失了，不会像list一样常驻内存。
2. rdd包含多个分区，不同分区由不同task处理。

2.1.3 数据操作

transformation：产生新的rdd(也说明了rdd的不可修改的性质)
action：不会产生rdd，可能有计算结果，可能进行了操作(foreachPartition)

2.1.4 计算结果处理

分executor和driver两种：
executor执行就是像foreachPartition这种，直接写出去或者怎样；
driver端处理就是先collect回来再进行最后汇总。

2.2 逻辑处理流程生成方法

需要解决三个问题：

1. rdd如何产生，产生啥样的rdd
2. rdd之间的数据依赖关系如何建立
3. rdd中的数据如何计算

2.2.1 rdd如何产生，产生啥样的rdd

transformation算子产生rdd呗，比如map join reduceByKey啥的
rdd种类很多，根据数据类型、计算逻辑、数据依赖划分的，比如常见的MapPartitionRDD，ShuffledRDD，ParallelCollectionRDD。

2.2.2 rdd之间的数据依赖关系如何建立

数据依赖关系要从两方面理解：一方面是rdd之间的关系，另一方面是rdd内部不同分区之间的关系。
one=>one、many=>one、many=>many 等等，情况太多太复杂，同时又考虑到物理执行阶段的便利性，总结了两种通用的依赖关系
图里红色的是宽依赖，黑色的是窄依赖

1 窄依赖

子rdd依赖于父rdd的分区的全部数据
图中四种情况的从左到右的例子：map，union，join(都是同样的partitioner)，cartesian

2 宽依赖

子rdd依赖于父rdd的分区的部分数据，比如图里，rdd2只需要rdd1的pid为1或者2的数据，不需要全部读取。

3 分区划分

水平划分：最开始的数据划分成block
hash划分：常用于shuffle阶段
range划分： 一般用于排序任务。为了估算数据边界，还得抽样，这样会产生额外的job。

2.2.3 rdd中的数据如何计算

来一条数据算一次，比如map
加载整个分区数据，进行计算，比如mapPartitions

2.3 编程模型角度与mr的比较

从编程模型角度：更具有通用性和易用性。

1. 通用性：数据格式随意，不必拘泥于mr的<K,V>形式；而且数据依赖关系也不只有shuffle这一种，不shuffle还能一块执行效率高；计算套路上也多种多样(算子多)，不是只有map和reduce。
2. 易用性：算子多，join reduceBykey啥的拿来就用；不用手动提交job，有action，像之前想把多个mr串起来还要再写个程序。

这一章还有一些算子的介绍，有需要的时候可以看看。

3 spark物理执行计划

3.1 spark物理执行计划生成方法

3.1.1 执行步骤

1. 根据action操作顺序划分job,一个action()一个job
2. 根据shuffleDependency将job划分stage，从后往前回溯rdd依赖关系，shuffle就切开
3. 根据分区计算将stage划分task，根据最后一个rdd的分区个数决定task个数。

3.1.2 存在问题

1 job stage task 计算顺序

job就看action的顺序
stage就看job内的划分，不依赖的可以并行，依赖的上游stage全部执行完了才能进行下游stage的计算
同一个stage内的task是并行计算的

2 task内部数据的存储与计算问题

尽量节省内存，流水线式的计算。
比如rdd.map().filter()，内存里一个record进来算完了filter再进来下一条record。当然有些比如mapPartitions()就得把数据全弄进内存，甚至还得用容器存个结果。

3 task间的数据传递与计算问题

shuffle write+shuffle read进行传输，上游task只写一个文件，不会像mr一样每个分区一个文件。

4 shuffle机制

4.1 面临的挑战

shuffle不只是上游给下游不同分区的数据传输，两边还都有聚合排序的操作，面临的挑战：

1. 计算的多样性：如图，groupByKey在下游需要把<K,V>聚合为<K,list(V)>，reduceByKey需要在上游做combine(所以shuffle传输数据量小，更快)，sortByKey需要下游做排序，需要有一个统一的shuffle框架。
2. 计算的耦合性：自定义的聚合函数和shuffle write/read是耦合的，比如最下面的例子，在shuffle write的时候要进行seqOp，read的时候要进行combOp。
3. 中间数据存储问题：计算这些自定义的函数的结果如何组织存放？内存装不下咋整？

4.2 shuffle设计思想

本节的名词定义：
上游=map stage=shuffle write阶段
下游=reduce stage=shuffle read阶段

4.2.1 数据分区和数据聚合问题

最基本的数据传输问题

1 数据分区问题

如何对map task输出结果尽心分区，保证reduce task可以获得数据？

先确定分区个数，很简单，不手动指定就是上游的最大分区数。
再来解决如何分区，根据map输出的<K,V> 中的key计算partition id，比如分两个分区，那就可以hash(Key)%2就是partition id了。

2 数据聚合问题

在shuffle read阶段，如何获取上游数据并按照Key进行聚合？

维护一个HashMap<Key,func(Val)>，来一条数据先去map里get，get到的v跟Val进行func操作，然后再更新map里这个key的val，get不到就直接插入key，func(val)这个数据。
这样既很快(来一个算一个)，又省内存(不然拿到整个分区的val再计算出map)。当然，如果是groupByKey这种不涉及聚合操作的，就跟整个分区数据都进来比就不快也不省内存。

4.2.2 map端combine功能

reduceBykey foldByKey agg…ByKey combineByKey这种算子在map端combine了就能减少shuffle数据量。同样地，可以维护一个HashMap，数据出来先在map里过一下，然后再输出分区文件。

4.2.3 sort问题

sortByKey sortBy需要排序

1 在哪进行sort？

shuffle read肯定是需要的，要把各个上游的数据放在一起全局排序的。map端排一下最好，这样再reduce端排序的时候能减小复杂度，上游并行起来肯定比下游一个任务快。

2 排序和聚合的顺序怎么定？

mr是先排序再聚合的，用一个类似Array的结构，排序完了也能直接顺序扫描聚合，缺点是需要较大内存来存储全部数据，而且效率低下，不能在线聚合(每条数据来了同时进行排序和聚合)。
spark用的是先聚合再排序，