有向无环图(DAG)

1. 目的

有向无环图(DAG – Directed Acyclic Graph)是一组顶点和边,顶点代表RDD,边代表要在RDD上应用的操作。在DAG中,每条边都是从前面到后面的顺序。在调用Action时,将创建的DAG提交给DAG Scheduler,它将DAG进一步分解为阶段(Stage)。

本章将介绍DAG是什么,为什么需要DAG,DAG如何在RDD中工作,在Spark中如何创建DAG以及它如何帮助实现容错。DAG是Spark和MapReduce之间的显著区别。

2. 什么是DAG

DAG是一个没有循环的有限有向图,它有很多顶点和边,其中每个边从一个顶点指向另一个顶点。它包含一系列顶点,使得每个边都从该序列中的较早部分指向较晚部分。DAG操作可以比MapReduce计算框架做更好的全局优化,使复杂的工作变得清晰。

DAG Scheduler根据应用的各种转换将RDD分成多个阶段,每个阶段都由基于RDD分区的任务组成,这些任务将并行执行相同的计算。

3. 为什么需要DAG

Hadoop MapReduce的限制成为在Spark中引入DAG的关键。MapReduce的计算分三步进行:

1)从HDFS读取数据。

2)应用“map”和“reduce”操作。

3)计算结果被写回到HDFS。

每个MapReduce操作都是彼此独立的,Hadoop不知道接下来的MapReduce是什么,中间结果会放在HDFS文件系统中。ReduceTask需要等待所有MapTask都完成后才可以开始。复杂的计算需要大量的Job完成,Job之间的依赖关系是由开发者自己管理的。

而在Spark中,形成了连续计算阶段的DAG(有向无环图)。以这种方式,执行计划被优化,例如:最大限度地减少Shuffle数据。

4. DAG如何在RDD中工作

在Spark中,所有RDD的转换都是延迟求值的。RDD的转换操作会生成新的RDD,新的RDD的数据依赖于原来的RDD的数据,每个RDD又包含多个分区。那么一段程序实际上就构造了一个由相互依赖的多个RDD组成的DAG,并通过在RDD上执行动作将这个DAG作为一个Job提交给Spark执行。

在一个作业提交给DAG Schedule前,要先构建RDD操作的DAG,有了DAG,Spark内核下一步的任务就是根据DAG将计算划分成Stage,这样可以将任务提交到计算节点进行真正的计算。Spark计算的中间结果默认是保存在内存中的,Spark在划分Stage的时候会充分考虑在分布式计算中可流水线计算(Pipeline)的部分来提高计算的效率,而在这个过程中,主要的根据就是RDD的依赖类型。根据不同的转换操作,RDD的依赖可以分为窄依赖(Narrow Dependency)和宽依赖(Wide Dependency)两种类型。窄依赖指的是生成的RDD中每个分区只依赖于父RDD(s) 固定的分区。宽依赖指的是生成的RDD的每一个分区都依赖于父 RDD(s) 所有分区。窄依赖典型的操作有map, filter, union等,宽依赖典型的操作有groupByKey, sortByKey等。可以看到,宽依赖往往意味着Shuffle数据,这也是Spark划分Stage的主要边界。对于窄依赖,Spark会将其尽量划分在同一个Stage中,因为它们可以进行流水线计算。

由于宽依赖必须等RDD的父RDD分区数据全部准备好之后才能开始计算,因此Spark让父RDD将结果写在本地,完全写完之后,通知后面的RDD。后面的RDD则首先去读之前的本地数据作为输入,然后进行运算。宽依赖分为两个阶段(Stage)去做:

1)需要把结果Shuffle到本地,例如reduceByKey,首先要聚合某个key的所有记录,才能进行下一步的reduce计算。

2)读入数据进行处理。

同一个Stage里面的Task是可以并发执行的,下一个Stage要等前一个Stage计算完成。

5. DAG容错

DAG图中,RDD分宽依赖和窄依赖,在宽依赖的RDD数据丢失后,要重新计算所有父分区,窄依赖的RDD数据丢失后则只要把丢失的父RDD分区重新计算即可。

6. DAG的优点

1)比MapReduce这样的计算框架有更好的全局优化,执行速度比MapReduce快。

2)有助于实现容错。

有向无环图(DAG)
滚动到顶部