DAG

什么是DAG

在Spark里每一个操作生成一个RDD，RDD之间连一条边，最后这些RDD和他们之间的边组成一个有向无环图，这个就是DAG。

Spark 为什么要构建DAG?

Spark会根据宽依赖窄依赖来划分具体的Stage，而依赖有2个作用：

• 用来解决数据容错的高效性；
• 其二用来划分stage。

RDD的依赖关系分为两种：窄依赖(Narrow Dependencies)与宽依赖(Wide Dependencies，源码中称为Shuffle Dependencies)

• 窄依赖
  每个父RDD的一个Partition最多被子RDD的一个Partition所使用（1:1 或 n:1）。例如map、filter、union等操作都会产生窄依赖；
  子RDD分区通常对应常数个父RDD分区(O(1)，与数据规模无关）。
• 宽依赖
  一个父RDD的Partition会被多个子RDD的Partition所使用，例如groupByKey、reduceByKey、sortByKey等操作都会产生宽依赖；（1:m 或 n:m）
  子RDD分区通常对应所有的父RDD分区(O(n)，与数据规模有关）

DAG的生成

原始的RDD通过一系列的转换就形成了DAG，有了计算的DAG图，Spark内核下一步的任务就是根据DAG图将计算划分成任务集，也就是Stage，这样可以将任务提交到计算节点进行真正的计算。Spark计算的中间结果默认是保存在内存中的，Spark在划分Stage的时候会充分考虑在分布式计算中可流水线计算（pipeline）的部分来提高计算的效率，而在这个过程中Spark根据RDD之间依赖关系的不同将DAG划分成不同的Stage(调度阶段)。对于窄依赖，partition的转换处理在一个Stage中完成计算。对于宽依赖，由于有Shuffle的存在，只能在parent RDD处理完成后，才能开始接下来的计算，因此宽依赖是划分Stage的依据。

Spark Works By DAG

Spark 执行时有下面所列的流程：

• 用户代码定义RDD的有向无环图
  RDD上的操作会创建新的RDD，并引用它们的父节点，这样就创建了一个图。

• 行动操作把有向无环图强制转译为执行计划
  当调用RDD的一个行动操作时，这个RDD就必须被计算出来。这也要求计算出该RDD的父节点。Spark调度器提交一个作业来计算出所有必要的RDD。这个作业会包含一个或多个步骤，每个步骤其实也就是一波并行执行的计算任务。一个步骤对应有向五环图中的一个或多个RDD，一个步骤对应多个RDD是因为发生了流水线执行。

• 任务于集群中调度并执行
  步骤是按顺序处理的，任务则独立的启动来计算出RDD的一部分。一旦作业的最后一个步骤结束，一个行动操作也就执行完了。

注：在一个给定的Spark应用中，由于需要创建一系列新的RDD，因此上述阶段会连续发生很多次