Spark 中将 DAG 划分为 Stage 核心算法

Application 多个 job 多个 Stage：

Spark Application 中可以因为不同的 Action 触发众多的 job，一个 Application 中可以有很多的 job，每个 job 是由一个或者多个 Stage 构成的，后面的 Stage 依赖于前面的 Stage，也就是说只有前面依赖的 Stage 计算完毕后，后面的 Stage 才会运行。

划分依据：

Stage 划分的依据就是宽依赖，何时产生宽依赖，reduceByKey, groupByKey 等算子，会导致宽依赖的产生。

核心算法：(回溯算法)

从后往前回溯/反向解析，遇到窄依赖加入本 stage，遇见宽依赖进行 Stage 切分。

Spark 内核会从触发 Action 操作的那个 RDD 开始从后往前推，

首先会为最后一个 RDD 创建一个 stage，

然后继续倒推，如果发现对某个 RDD 是宽依赖，那么就会将宽依赖的那个 RDD 创建一个新的 stage，那个 RDD 就是新的 stage 的最后一个 RDD。

然后依次类推，继续倒推，根据窄依赖或者宽依赖进行 stage 的划分，

直到所有的 RDD 全部遍历完成为止。

将 DAG 划分为 Stage 剖析

从 HDFS 中读入数据生成 3 个不同的 RDD，通过一系列 transformation 操作后再将计算结果保存回 HDFS。

可以看到这个 DAG 中只有 join 操作是一个宽依赖，Spark 内核会以此为边界将其前后划分成不同的 Stage.

同时我们可以注意到，在图中 Stage2 中，从 map 到 union 都是窄依赖，这两步操作可以形成一个流水线操作，通过 map 操作生成的 partition 可以不用等待整个 RDD 计算结束，而是继续进行 union 操作，这样大大提高了计算的效率。

提交 Stages

调度阶段的提交，最终会被转换成一个任务集的提交，

DAGScheduler 通过 TaskScheduler 接口提交任务集，

这个任务集最终会触发 TaskScheduler 构建一个 TaskSetManager 的实例来管理这个任务集的生命周期，

对于 DAGScheduler 来说，提交调度阶段的工作到此就完成了。

而 TaskScheduler 的具体实现则会在得到计算资源的时候，进一步通过 TaskSetManager 调度具体的任务到对应的 Executor 节点上进行运算。