DAG

DAG是有向无环图（Directed Acyclic Graph）的简称。在大数据处理中，DAG计算常常指的是将计算任务在内部分解成为若干个子任务，将这些子任务之间的逻辑关系或顺序构建成DAG（有向无环图）结构。 DAG在分布式计算中是非常常见的一种结构，在各个细分领域都可以看见它，比如Dryad,FlumeJava和Tez，都是明确构建DAG计算模型的典型，再如流式计算的Storm等系统或机器学习框架Spark等，其计算任务大多也是DAG形式出现的，除此外还有很多场景都能见到。

DAG计算的三层结构：

• 最上层是应用表达层，即是通过一定手段将计算任务分解成由若干子任务形成的DAG结构，其核心是表达的便捷性，主要是方便应用开发者快速描述或构建应用。

• 中间层是DAG执行引擎层，主要目的是将上层以特殊方式表达的DAG计算任务通过转换和映射，将其部署到下层的物理机集群中运行，这层是DAG计算的核心部件，计算任务的调度，底层硬件的容错，数据与管理信息的传递，整个系统的管理与正常运转等都需要由这层来完成。

• 最下层是物理机集群，即由大量物理机器搭建的分布式计算环境，这是计算任务最终执行的场所。

常见框架包括了：

• Dryad是微软的批处理DAG计算系统，其主要目的是为了便于开发者便携地进行分布式任务处理。Dryad将具体计算组织成有向无环图，其中图节点代表用户写的表达式应用逻辑，图节点之间的边代表了数据流动通道。Dryad在实时以共享内存，TCP连接以及临时文件的方式来进行数据传递，绝大多数情况下采用临时文件的方式。

• FlumeJava是Google内部开发的DAG系统，考虑到很多任务是需要多个MR任务连接起来共同完成的，而如果直接使用MR来完成会非常烦琐，因为除了完成MR任务本身外，还需要考虑如何衔接MR及清理各种中部结果等琐碎工作。

• Tez是Apache孵化项目，其本身也是一个相对通用的DAG计算系统，最初提出Tez是为了改善交互数据分析系统Stinger的底层执行引擎，Stinger是Hive的改进版本，最初底层的执行引擎是Hadoop和MR任务形成的DAG任务图，Tez是它的升级版，效率更高。Tez通过消除Map阶段中间文件输出到磁盘过程以及引入Reduce-Reduce结构等改进措施极大提升了底层执行引擎和效率。