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支持本地单节点运行(开发调试有用)或集群运行。

原文发布于微信公众号 - 大数据和云计算技术(jiezhu2007)

原文发表时间:2014-04-04

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏xingoo, 一个梦想做发明家的程序员

[大数据之Spark]——快速入门

本篇文档是介绍如何快速使用spark,首先将会介绍下spark在shell中的交互api,然后展示下如何使用java,scala,python等语言编写应用。...

1909
来自专栏Spark学习技巧

Spark SQL用UDF实现按列特征重分区

解决问题之前,要先了解一下Spark 原理,要想进行相同数据归类到相同分区,肯定要有产生shuffle步骤。

941
来自专栏包子铺里聊IT

【最火大数据 Framework】五分钟深入 Spark 运行机制

上篇文章,我们简要介绍了 MapReduce 框架的局限和 Spark 横空出世的土壤。今天,我们就来详细介绍 Spark 的内部原理和它强大功能的背后设计。...

36512
来自专栏牛肉圆粉不加葱

Spark Task 的执行流程③ - 执行 task

创建、分发 Task一文中我们提到 TaskRunner(继承于 Runnable) 对象最终会被提交到 Executor 的线程池中去执行,本文就将对该执行过...

681
来自专栏Albert陈凯

3.3RDD的转换和DAG的生成

3.3 RDD的转换和DAG的生成 Spark会根据用户提交的计算逻辑中的RDD的转换和动作来生成RDD之间的依赖关系,同时这个计算链也就生成了逻辑上的DAG...

2997
来自专栏Spark生态圈

[spark] DAGScheduler划分stage源码解析

Spark Application只有遇到action操作时才会真正的提交任务并进行计算,DAGScheduler 会根据各个RDD之间的依赖关系形成一个DAG...

1292
来自专栏xingoo, 一个梦想做发明家的程序员

Spark Stage切分 源码剖析——DAGScheduler

Spark中的任务管理是很重要的内容,可以说想要理解Spark的计算流程,就必须对它的任务的切分有一定的了解。不然你就看不懂Spark UI,看不懂Spark...

2168
来自专栏大数据

Zzreal的大数据笔记-SparkDay05

Spark Streaming SparkStreaming部分没做知识点的笔记,直接从代码上理解它的用法。后面整理Storm的时候会与SparkStreami...

2146
来自专栏Spark学习技巧

必读|spark的重分区及排序

前几天,有人在星球里,问了一个有趣的算子,也即是RepartitionAndSortWithinPartitions。当时浪尖也在星球里讲了一下,整个关于分区排...

982
来自专栏鸿的学习笔记

spark的一些小总结

首先,DAG是MR的迭代模型。其中一个优点是,DAG可以做全局的优化,而Hadoop的MR没有意识到这点。

942

扫码关注云+社区