首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >DAG算法在hadoop中的应用

DAG算法在hadoop中的应用

作者头像
大数据和云计算技术
发布2018-03-08 09:48:32
2.3K0
发布2018-03-08 09:48:32
举报

大学里面数据结构里面有专门的一章图论,可惜当年没有认真学习,现在不得不再次捡起来。真是少壮不努力,老大徒伤悲呀!

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

本文参与 腾讯云自媒体分享计划,分享自微信公众号。
原始发表:2014-04-04,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 大数据和云计算技术 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档