DAG算法在hadoop中的应用

大学里面数据结构里面有专门的一章图论，可惜当年没有认真学习，现在不得不再次捡起来。真是少壮不努力，老大徒伤悲呀！什么是DAG（Directed Acyclical Graphs），先来看下教科书上的定义吧：如果一个有向图无法从某个顶点出发经过若干条边回到该点。让我们再来看看DAG算法现在都应用在哪些hadoop引擎中。

Tez:

Hortonworks开发的DAG计算框架，是从MapReduce计算框架演化而来的通用DAG计算框架，核心思想是将Map和Reduce两个操作进一步拆分，即Map被拆分成Input、Processor、Sort、Merge和Output， Reduce被拆分成Input、Shuffle、Sort、Merge、Processor和Output等，这样，这些分解后的元操作可以任意灵活组合，产生新的操作，这些操作经过一些控制程序组装后，可形成一个大的DAG作业，可以用来替换Hive/Pig等。

 

 

Oozie：

Oozie工作流是放置在控制依赖DAG（有向无环图 Direct Acyclic Graph）中的一组动作（例如，Hadoop的Map/Reduce作业、Pig作业等），其中指定了动作执行的顺序。我们会使用hPDL（一种XML流程定义语言）来描述这个图。

hPDL是一种很简洁的语言，只会使用少数流程控制和动作节点。控制节点会定义执行的流程，并包含工作流的起点和终点（start、end和fail节点）以及控制工作流执行路径的机制（decision、fork和join节点）。动作节点是一些机制，通过它们工作流会触发执行计算或者处理任务。Oozie为以下类型的动作提供支持： Hadoop map-reduce、Hadoop文件系统、Pig、Java和Oozie的子工作流。

 

Spark:

Resilient Distributed Dataset (RDD)弹性分布数据集 是Spark的最基本抽象,是对分布式内存的抽象使用，实现了以操作本地集合的方式来操作分布式数据集的抽象实现。RDD是Spark最核心的东西，它表示已被分区，不可变的并能够被并行操作的数据集合，不同的数据集格式对应不同的RDD实现。RDD必须是可序列化的。RDD可以cache到内存中，每次对RDD数据集的操作之后的结果，都可以存放到内存中，下一个操作可以直接从内存中输入，省去了MapReduce大量的磁盘IO操作。

元数据的结构是DAG（有向无环图），其中每一个“顶点”是RDD（包括生产该RDD的算子），从父RDD到子RDD有“边”，表示RDD间的依赖性。Spark给元数据DAG取了个很酷的名字，Lineage（世系）。

Spark程序的运行场景。它由客户端启动，分两个阶段：第一阶段记录变换算子序列、增量构建DAG图；第二阶段由行动算子触 发，DAGScheduler把DAG图转化为作业及其任务集。Spark支持本地单节点运行（开发调试有用）或集群运行。