当前位置: 首页>>hadoop 1.0>> 阅读正文

Hadoop中TeraSort算法分析

Category: hadoop 1.0 View: 163,743 Author: Dong
, , ,

  • 评论 (2)
  • 引用通告 (4)
发表评论 发起引用

  • 1楼Ekans 回复

    Post: 2012-03-29 03:38

    Map阶段的排序都是Partition在Merge过程中完成的,Map函数完完全全就是照样子copy(Reduce函数同),所谓的加标签是partition的工作,博主给的图比较误导。
    另外Terasort没用用自带的那几种采样方式,而是自己实现了一种方式来进行采样,这样效率会高很多。

    [回复]

    Dong 回复:

    恩,Tearasort中自己实现的采样算法不一定高效,注意这里的“高效”有两层含义:(1)采样算法本身高效,因为采样是在client端做的(这意味着采样是单线程的,不能并发采样),采样结束后才会正式提交作业到JobTracker,所以采样时间不宜过长;(2)采样之后,按照采样得到的分片算法不会造成严重的数据不均衡,如果发生数据严重不均衡,会导致TeraSort十分低效。 而实际上,这两点是矛盾的,采样数据过少,样本数据不能代替整体数据分布,会导致数据严重倾斜,而采样数据过多,会导致采样时间过长,也是不可接受的。

    [回复]

  • 2楼arvin 回复

    Post: 2013-06-22 10:19

    LZ对terasort的描述算法有误吧,如果map task X和map task Y的数据切片(partition0 partition1)分别如下:
    X:
    22 11
    Y:
    44 33
    按照lz的描述,reduce阶段最终的输出就是:
    44 22 33 11

    [回复]

    Dong 回复:

    不是。

    [回复]

    arvin 回复:

    感谢回帖,“在map阶段,每个map task都会将数据划分成R个数据块(R为reduce task个数),其中第i(i>0)个数据块的所有数据都会比第i+1个中的数据大;在reduce阶段,第i个reduce task处理(进行排序)所有map task的第i块,这样第i个reduce task产生的结果均会比第i+1个大,最后将1~R个reduce task的排序结果顺序输出,即为最终的排序结果。”,首先,LZ给的图里,map task并没有第i块数据的概念;其次,上面这句话并没体现出是怎么数据保证全局有序的。在map阶段,TotalOrderPartition通过trie查找来确定mapper中某个record被送往哪个reducer,然后才由reducer进行局部排序,reducer中各个数据块的大小关系是在查找过程中才由trie来确定下来。另外,map阶段最好不好说第i个数据块和第i+1个数据块这种概念,只能说在map阶段,某个record被划分到第i个reduce中去。一言以蔽之,map阶段的TotalOrderPartition负责全局有序,在全局有序的前提下,reducer再来负责第i个数据块的局部有序,最终输出的便是有序数据集。

    [回复]

    Dong 回复:

    嗯,是的,这是我两年前的博客文章,那时候能力比较弱,表达的不是很清楚,不好意思。

    [回复]

    crazycat 回复:

    博主,我想知道,按照你这样说的话,reduce的输出是按照reduce的编号顺序进行输出的?可是我没有在任何一本书上看过这种说法啊

    [回复]

    Dong 回复:

    每个reduce task输出数据内部有序,且reduce task直接是有序的,也就是,reduce task0的最大值小于reduce task1的最小值,reduce task1的最大值,小于reduce task2的最小值,这个是应用程序自己实现的。

    [回复]

发表评论