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 结构等改进措施极大提升了底层执行引擎和效率。