太阳城集团

  • / 6
  • 下载费用:30 金币  

基于动态标记优先值的MAPREDUCE数据本地化方法.pdf

关 键 词:
基于 动态 标记 优先 MAPREDUCE 数据 本地化 方法
  专利查询网所有资源均是用户自行上传分享,仅供网友学习交流,未经上传用户书面授权,请勿作他用。
摘要
申请专利号:

CN201510585360.7

申请日:

2015.09.14

公开号:

CN105224612A

公开日:

2016.01.06

当前法律状态:

授权

有效性:

有权

法律详情: 授权|||实质审查的生效IPC(主分类):G06F 17/30申请日:20150914|||公开
IPC分类号: G06F17/30 主分类号: G06F17/30
申请人: 成都太阳城集团工程大学
发明人: 杨玉琴; 陈麟
地址: 610225 四川省成都市西南航空港经济开发区学府路1段24号
优先权:
专利代理机构: 成都信博专利代理有限责任公司 51200 代理人: 崔建中
PDF完整版下载: PDF下载
法律状态
申请(专利)号:

太阳城集团CN201510585360.7

授权太阳城集团号:

||||||

法律状态太阳城集团日:

太阳城集团2018.12.07|||2016.02.03|||2016.01.06

法律状态类型:

授权|||实质审查的生效|||公开

摘要

太阳城集团本发明提供了一种基于动态标记优先值的MapReduce数据本地化方法,包括以下步骤:将各计算节点上的本地化数据块初始化标记值为2n,计算各计算节点本地化数据块的数量;按照各计算节点的数据块数量进行升序排序;依次从数据块数量最少的计算节点开始,将每个计算节点上的数据块的后续备份数据块的标记值减去一个确定的数DecS;优先选择标记值最大的数据块进行调度;任务调度后,再次调整每个计算节点的数据块数量,并进行升序排序,排序后进行标记值调整,最终完成数据处理。本发明通过标记数据块并设置不同优先值,从而提升作业的数据本地化程度,进而提升MapReduce上作业的执行效率和减少作业的带宽占用率。

权利要求书

权利要求书
1.  一种基于动态标记优先值的MapReduce数据本地化方法,其特征在于:包括以下步骤;
设一个集群中拥有n个计算节点,各计算节点的名称为T1,T2,…,Ti,…,Tn,某个在集群上运行的作业拥有m个数据块且各数据块的名称为B1,B2,…,Bx,…,Bm,数据块默认冗余数为3,则Bx有三个存储的数据块Bx1、Bx2、Bx3;
将各计算节点上的本地化数据块初始化标记值为2n,计算各计算节点本地化数据块的数量,不妨设Ti上有本地化数据块CLTi个;
按照各计算节点的数据块数量进行升序排序,不妨设一种升序序列为INC1,INC2,…,INCp,…,INCj,…,INCk,…,INCn,其中,位置INCj对应CLTi个数据块,且对应计算节点Ti;
依次从INC1对应的计算节点开始,直到INCn对应的计算节点,将每个计算节点上的数据块的后续备份数据块的标记值减去一个确定的数DecS,DecS的值由位置INCj确定,位置INCj对应DecS的值n-j+1;
在任务调度过程中,若调度本地化的数据块,则优先选择标记值最大的数据块,若本地没有数据块,则优先选择本机架位置INC数值高的计算节点上标记值高的数据块进行拷贝;
每个数据块得到调度后,再次调整每个计算节点的数据块数量,当某个数据块Bx1被调度后,该数据块及其备份数据块Bx2、Bx3所在的三个计算节点上的数据块数量都减去1,之后进行升序排序,排序后再进行标记值调整;设数据块Bx2对应的计算节点为Ts,在调度数据块Bx2之前,计算节点Ts上的数据块数量为CLTs,对应的位置为INCk,调度之后,Ts对应位置为INCp,4种调整分别为:第一、计算节点Ts上的本地数据块在位置INCp到INCk-1对应的计算节点的备份数据块的标记值都减去n-p+1;第二、位置INCp到INCk-1对应的计算节点上的数据块在计算节点Ts上的标记值都加n-r+1(r∈[p,k-1]),计算节点Tr是与计算节点Ts上的数据块有相同数据块的计算节点;第三、从位置INCp到INCk-1对应的计算节点上的数据块的后续备份数据块的标记值都加1;第四、计算节点Ts本地其他数据块对应的在INCk位置之后的计算节点上的数据块的标记值需要再次加上p-k,p-k=(n-k+1)-(n-p+1);
标记值调整后继续下一次任务调度,任务调度后继续下一次标记值调整,直到所有计算任务全部完成。

说明书

说明书基于动态标记优先值的MapReduce数据本地化方法
技术领域
本发明涉及计算机大规模数据运算,尤其是MapReduce运算领域,特别涉及一种基于动态标记优先值的MapReduce数据本地化方法。
背景技术
MapReduce计算框架作为Hadoop平台的核心组件,Hadoop平台所有计算任务都是在MapReduce上完成的,所以Hadoop平台的计算效率和吞吐量与MapReduce的作业执行效率和吞吐量息息相关。
在Hadoop平台,MapReduce分布式计算框架是搭建在以冗余形式存储数据块的分布式文件系统HDFS上,HDFS以数据块的形式存储用户数据并且数据块默认冗余数为3,也就是说一个作业对应的文件大小为100个数据块(在HDFS中,数据块默认大小为64MB)时,在HDFS中存储太阳城集团该作业的数据块数目为300。
数据本地化是一种在本地获取计算数据的过程,数据本地化程度高,能减少计算节点的计算等待太阳城集团,同时也能减少数据拷贝量,从而达到高效利用集群网络带宽的目的。由于存储数据的节点和参加计算的节点是重合的,所以MapReduce可以利用这种冗余形式的数据块来提升分布式计算任务的数据本地化程度。原始的MapReduce任务调度方法在接受计算节点的任务请求时,为了提升计算任务的数据本地化程度,优先选择该计算节点的本地任务,次之是本机架的任务,最后是本数据中心的任务。
然而,这种数据本地化方法并不能实现高程度的数据本地化,主要原因有:1)一个作业的数据块在各计算节点上分布相对不均匀;2)各计算节点的计算性能有差异,并不完全是同构的机器。在原始的调度方法中,MapReduce认为集群中的机器是同构的,且没有考虑数据块分布的不均衡性;3)每个计算节点在选取本地数据块时没有一个优先顺序。数据块有冗余备份,可能导致本地化任务的恶性抢占。
发明内容
本发明所要解决的技术问题是提供一种基于动态标记优先值的MapReduce数据本地化方法,该方法综合考虑数据块的分布状况和计算节点的异构差异性,在调度本地化任务的时候给出一个优先级,解除本地化任务分配中的恶性抢占问题。
为解决上述技术问题,本发明采用的技术方案是:
一种基于动态标记优先值的MapReduce数据本地化方法,包括以下步骤;
设一个集群中拥有n个计算节点,各计算节点的名称为T1,T2,…,Ti,…,Tn,某个在集群上运行的作业拥有m个数据块且各数据块的名称为B1,B2,…,Bx,…,Bm,数据块 默认冗余数为3,则Bx有三个存储的数据块Bx1、Bx2、Bx3;
将各计算节点上的本地化数据块初始化标记值为2n,计算各计算节点本地化数据块的数量,不妨设Ti上有本地化数据块CLTi个;
按照各计算节点的数据块数量进行升序排序,不妨设一种升序序列为INC1,INC2,…,INCp,…,INCj,…,INCk,…,INCn,其中,位置INCj对应CLTi个数据块,且对应计算节点Ti;
依次从INC1对应的计算节点开始,直到INCn对应的计算节点,将每个计算节点上的数据块的后续备份数据块的标记值减去一个确定的数DecS,DecS的值由位置INCj确定,位置INCj对应DecS的值n-j+1;
在任务调度过程中,若调度本地化的数据块,则优先选择标记值最大的数据块,若本地没有数据块,则优先选择本机架位置INC数值高的计算节点上标记值高的数据块进行拷贝;
每个数据块得到调度后,再次调整每个计算节点的数据块数量,当某个数据块Bx1被调度后,该数据块及其备份数据块Bx2、Bx3所在的三个计算节点上的数据块数量都减去1,之后进行升序排序,排序后再进行标记值调整。设数据块Bx2对应的计算节点为Ts,在数据块Bx2调度之前,计算节点Ts上的数据块数量为CLTs,对应的位置为INCk,调度之后,Ts对应位置为INCp,4种调整分别为:第一、计算节点Ts上的本地数据块在位置INCp到INCk-1对应的计算节点的备份数据块的标记值都减去n-p+1;第二、从位置INCp到INCk-1对应的计算节点上的数据块在计算节点Ts上的标记值都加n-r+1(r∈[p,k-1]),计算节点Tr是与计算节点Ts上的数据块有相同数据块的计算节点;第三、位置INCp到INCk-1对应的计算节点上的数据块的后续备份数据块的标记值都加1;第四、计算节点Ts本地其他数据块对应的在位置INCk之后的计算节点上的数据块的标记值需要再次加p-k,p-k=(n-k+1)-(n-p+1);
标记值调整后继续下一次任务调度,任务调度后继续下一次标记值调整,直到所有计算任务全部完成。
与现有技术相比,本发明的有益效果是:通过标记数据块并设置不同优先值,从而提升作业的数据本地化程度,进而提升MapReduce的作业执行效率和减少作业的带宽占用率,最终提升Hadoop集群的整体吞吐率。
具体实施方式
本发明的目的在于通过提升数据本地化程度来进一步提升Hadoop平台的吞吐率以及MapReduce作业的执行效率。通过动态设定标记值来改变本地化任务的调度优先级从而提升数据本地化程度。提升数据本地化程度,减少需要远程传输的数据块数量,就可减少了计算节点的计算等待太阳城集团。另外,由于减少了非本地化任务,一个作业网络带宽的使用量也减少 了,从而使得MapReduce集群的并发度可以提升,进而提升Hadoop平台的整体吞吐率。本发明提出的基于动态标记优先值的数据本地化调度方法在同构或异构集群上均可工作。
基于动态标记优先值的MapReduce数据本地化方法的整体思路是,通过对各计算节点的本地化数据块进行动态升序排序,在初始阶段,排在前面的计算节点拥有相对少的本地化数据块,一段太阳城集团后,排在前面的将会是计算速度和本地化数据块不成正相关的计算节点。本发明方法尽最大可能不破坏排在相对靠前的计算节点的本地化数据块,通过动态地给各节点的数据块打标记值的方式来决定各计算节点的本地化任务调度优先权,最终实现提升数据本地化的目的。
一种基于动态标记优先值的MapReduce数据本地化方法,包括以下步骤;
步骤一、设一个集群中拥有n个计算节点,各计算节点的名称为T1,T2,…,Ti,…,Tn,某个在集群上运行的作业拥有m个数据块且各数据块的名称为B1,B2,…,Bx,…,Bm,数据块默认冗余数为3,则Bx有三个存储的数据块Bx1、Bx2、Bx3;
步骤二、将各计算节点上的本地化数据块初始化标记值为2n,计算各计算节点本地化数据块的数量,不妨设Ti上有本地化数据块CLTi个;
步骤三、按照各计算节点的数据块数量进行升序排序,不妨设一种升序序列为INC1,INC2,…,INCp,…,INCj,…,INCk,…,INCn,其中,位置INCj对应CLTi个数据块,且对应计算节点Ti;
步骤四、依次从INC1对应的计算节点开始,直到INCn对应的计算节点,将每个计算节点上的数据块的后续备份数据块的标记值减去一个确定的数DecS,DecS的值由位置INCj确定,位置INCj对应DecS的值n-j+1;
在集群各计算节点都是同构的情况下,INCn对应的计算节点是最不可能存在非本地化任务的计算节点,因为该计算节点上的数据块最多,反之,INC1对应的计算节点上的本地化数据块最少。在原始的调度方法中,如果INC1对应的计算节点不能每次都先得到调度,取得本地数据块进行处理,其本地数据块可能被其他计算节点所抢占(恶性抢占)。从数据块的升序序列可以看出,越往后的INC对应的计算节点在本地化出现的概率递增,非本地化出现的概率递减。为了保护数据块数量少的计算节点的数据块不被抢占,依次从INC1对应的节点开始,将该节点上的数据块的后续备份数据块的标记值减去一个确定的数DecS(DecreasetheprioritxofSelection),其目的是其他后续计算节点在选择本地化的任务时不会优先选择这类数据块。DecS的值由位置INCj唯一确定,例如,位置INCj的DecS数值为n-j+1,位置INC1上数据块在后续计算节点上的备份数据块的标记值都需要减去n。经过一轮计算之后,除了INC1对应的计算节点上的数据块的标记值都为2n外,其他后续INCj值对应的计算节点上的 数据块的标记值都是从2n到1的相对散列的标记值。例如,一个数据块Bx(x∈[1,m])有三个备份分别为Bx1,Bx2和Bx3,不妨设Bx1落在位置INC1对应的计算节点上,Bx2落在INCj对应到计算节点上,Bx3落在INCn对应的计算节点上,所以Bx1的标记值为2n,Bx2的标记值为n=2n-(n-1+1)=2n-n,其中,n-1+1是INC1的DecS值,Bx3的标记值为j-1=2n-n-(n-j+1),即Bx3的标记值除了要减去INC1的n,还要减去INCj的n-j+1。
步骤五、在任务调度过程中,若调度本地化的数据块,则优先选择标记值最大的数据块,若本地没有数据块,则优先选择本机架位置INC的数值高的计算节点上标记值高的数据块进行拷贝。各计算节点的升序排序位置一直在变动,例如,Bx1被调度处理后,Bx2和Bx3都不能被其所在的计算节点调度,所以其对应计算节点的数据块数量发生变化,从而改变整体升序排序。
步骤六、每个数据块得到调度后,再次调整每个计算节点的数据块数量,当某个数据块Bx1被调度后,该数据块及其备份数据块Bx2、Bx3所在的三个计算节点上的数据块数量都减去1,之后进行升序排序,排序后再进行标记值调整。设数据块Bx2对应的计算节点为Ts,在调度数据块Bx2前,计算节点Ts上的数据块数量为CLTs,对应的位置为INCk,调度之后,计算节点Ts对应位置为INCp。
当位置INCk对应的计算节点上一个数据块被调度处理后,假设Bx1被处理,则相应的备份数据块Bx2和Bx3都会被认为没用了,这三个数据块所在的三个计算节点的数据块数量都减1,它们在INC升序序列中的位置都要做出调整,即向前移动。从步骤四可以知道,3个备份数据块的标记值是由相互之间的位置关系决定,第一个备份数据块的标记值一直为2n,第二个备份数据块的标记值是2n减去第一个数据块所在计算节点的DecS,第三个备份数据块的标记值是2n减去第一个数据块所在计算节点的DecS,再减去第二个数据块所在计算节点的DecS。当计算节点Ts的对应的升序排序位置发生改变时,在位置INCp与INCn之间的计算节点的DecS都会发生改变,从而影响到在这些计算节点上的数据块的标记值。
现将4种调整情况详述如下。
1)、计算节点Ts上的本地数据块在位置INCp到INCk-1对应的计算节点的备份数据块的标记值都减去n-p+1。设有3个备份数据块Bx1,Bx2,Bx3(x∈[1,m])没被调度,如果在计算节点Ts对应的升序排序位置存在一个备份数据块Bx2,在INCp到INCk-1范围的计算节点也存在相同的备份Bx1和Bx3,数据块被调度后,计算节点Ts所在升序排序位置前移,此时,Ts的DecS值变成n-p+1,所以Bx1和Bx3的标记值需要减去(n-p+1)。
2)、位置INCp到INCk-1对应的计算节点上的数据块在计算节点Ts上的标记值都加n-r+1, 其中r∈[p,k-1],计算节点Tr是与计算节点Ts上的数据块有相同数据块的计算节点。
3)、在位置INCp与INCk-1之间对应的计算节点上的数据块的后续备份数据块的标记值都加1。若一个数据块在位置INCp到INCk-1之间,它的两个备份数据块都在位置INCk之后,那么,位置INCk之后的计算节点的数据块的标记值只需要加一次1;若有两个数据块在位置INCp到INCk-1之间,另一个备份数据块在位置INCk之后,那么,在位置INCk之后的计算节点上的数据块的标记值就需要加两次1;若3个数据块都在位置INCp与INCk-1之间,则这三个数据块中,排在靠后的两个备份数据块加1。
4)、计算节点Ts其他本地数据块在位置INCk之后的备份数据块的标记值需要再次加上p-k,p-k=(n-k+1)-(n-p+1)。其中,p-k小于0说明计算节点Ts上的本地化数据块在后续调度中显得更稀缺和重要,不希望被后续计算节点所抢占。计算节点Ts在升序排序中向前移动,移动之前的DecS为(n-k+1),移动之后为(n-p+1),因此,在计算节点Ts移动之后,排在位置INCk后面的节点的相同备份数据块需要加上由于位置变化带来的DecS差值p-k。
动态调整后,靠前的计算节点是计算性能较好或者是本地数据块相对较少的计算节点,这些计算节点上的数据块的备份数据块在升序排序中相对靠前,即标记值较小,因此,这些计算节点上的数据块会得到保护,从而提升数据本地化程度。标记值调整后继续下一次任务调度,任务调度后继续下一次标记值调整,即不断重复步骤五和步骤六,直到所有计算任务全部完成。

太阳城集团本文
本文标题:基于动态标记优先值的MAPREDUCE数据本地化方法.pdf
链接地址:http://zh228.com/p-6397428.html
太阳城集团我们 - 网站声明 - 网站地图 - 资源地图 - 友情链接 - - 联系我们

copyright@ 2017-2018 zhuanlichaxun.net网站版权所有
经营许可证编号:粤ICP备17046363号-1 
 


收起
展开
葡京赌场|welcome document.write ('');