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 条评论
登录 后参与评论

相关文章

来自专栏CSDN技术头条

Apache Spark作为编译器:深入介绍新的Tungsten执行引擎

《Spark 2.0技术预览:更容易、更快速、更智能》文中简单地介绍了Spark 2.0相关技术, 本文将深入介绍新的Tungsten执行引擎。Apache S...

1915
来自专栏大数据和云计算技术

flink二三事(2):起家的技术

上一篇聊到flink的历史,请看上篇 flink两三事 ----(1)历史。 可以说基本上是起了个大早,赶了个晚集,但是flink能做今天这种热度,没有被spa...

4025
来自专栏灯塔大数据

每周学点大数据 | No.68 Hadoop 实践案例——等值连接

No.68 Hadoop 实践案例——等值连接 Mr. 王 :我们再来看看另一个非常常见的例子。很多时候,我们关心的数据来自多个表。比如在某学校的教务系统中,有...

41010
来自专栏苦逼的码农

加锁还是不加锁,这是一个问题

上次我说过, 我们这个线程的世界是个弱肉强食的地方, 大家为了争抢资源大打出手,时不时闹出些内存数据互相被覆盖的事故, 给人类带了无穷的烦恼。

1165
来自专栏大数据挖掘DT机器学习

大数据工程师(开发)面试题(附答案)

MapReduce 1. 不指定语言,写一个WordCount的MapReduce 我:最近刚学了scala,并且就有scala版本的WordCount,刚好学...

1K3
来自专栏Albert陈凯

Hadoop数据分析平台实战——050MapReduce结构以及编程模型介绍(做过MR程序略过)离线数据分析平台实战——050MapReduce结构以及编程模型介绍(做过MR程序略过)

离线数据分析平台实战——050MapReduce结构以及编程模型介绍(做过MR程序略过) MapReduce结构介绍 MapReduce(YARN)是Hadoo...

2757
来自专栏铭毅天下

Elasticsearch词频统计实现与原理解读

有了分词,开发中会遇到,某个索引的文档集合中,共有多少XX关键词? 这就引发出了词频统计的问题。 社区问题:

1543
来自专栏挖掘大数据

Spark和RDD究竟该如何理解?

1.Spark的核心概念是RDD (resilient distributed dataset),指的是一个只读的,可分区的分布式数据集,这个数据集的全部或部分...

2300
来自专栏决胜机器学习

设计模式专题(二十二) ——享元模式

设计模式专题(二十二)——享元模式 (原创内容,转载请注明来源,谢谢) 一、概述 享元模式(Flyweight)是运用共享技术,有效地支持大量细粒度的对象。享...

3017
来自专栏大数据技术学习

大数据初学 或Java工程师怎么转大数据?大数据基础技术学习路线图

1.数据在体量方面很大,比如说文字,有各种各样的来源,有电子书|实体书|杂志|报刊等,它们的数据大吧。

1660

扫码关注云+社区