`
san_yun
  • 浏览: 2652087 次
  • 来自: 杭州
文章分类
社区版块
存档分类
最新评论

hadoop mapreduce的1TB排序

 
阅读更多

1、1TB(或1分钟)排序的冠军 
作为分布式数据处理的框架,集群的数据处理能力究竟有多快?或许1TB排序可以作为衡量的标准之一。 

1TB排序,就是对1TB(1024GB,大约100亿行数据)的数据进行排序。2008年,Hadoop赢得1TB排序基准评估第一名,排序1TB数据耗时209秒。后来,1TB排序被1分钟排序所取代,1分钟排序指的是在一分钟内尽可能多的排序。2009年,在一个1406个节点组成的hadoop集群,在59秒里对500GB完成了排序;而在1460个节点的集群,排序1TB数据只花了62秒。 

这么惊人的数据处理能力,是不是让你印象深刻呢?呵呵 

下面我们来看看排序的过程吧。 


2、排序的过程 

1TB的数据?100亿条数据?都是什么样的数据呢?让我们来看几条: 

Java代码  收藏代码
  1. .t^#\|v$2\         0AAAAAAAAAABBBBBBBBBBCCCCCCCCCCDDDDDDDDDDEEEEEEEEEEFFFFFFFFFFGGGGGGGGGGHHHHHHHH  
  2. 75@~?'WdUF         1IIIIIIIIIIJJJJJJJJJJKKKKKKKKKKLLLLLLLLLLMMMMMMMMMMNNNNNNNNNNOOOOOOOOOOPPPPPPPP  
  3. w[o||:N&H,         2QQQQQQQQQQRRRRRRRRRRSSSSSSSSSSTTTTTTTTTTUUUUUUUUUUVVVVVVVVVVWWWWWWWWWWXXXXXXXX  
  4. ^Eu)<n#kdP         3YYYYYYYYYYZZZZZZZZZZAAAAAAAAAABBBBBBBBBBCCCCCCCCCCDDDDDDDDDDEEEEEEEEEEFFFFFFFF  
  5. +l-$$OE/ZH         4GGGGGGGGGGHHHHHHHHHHIIIIIIIIIIJJJJJJJJJJKKKKKKKKKKLLLLLLLLLLMMMMMMMMMMNNNNNNNN  
  6. LsS8)|.ZLD         5OOOOOOOOOOPPPPPPPPPPQQQQQQQQQQRRRRRRRRRRSSSSSSSSSSTTTTTTTTTTUUUUUUUUUUVVVVVVVV  
  7. le5awB.$sm         6WWWWWWWWWWXXXXXXXXXXYYYYYYYYYYZZZZZZZZZZAAAAAAAAAABBBBBBBBBBCCCCCCCCCCDDDDDDDD  
  8. q__[fwhKFg         7EEEEEEEEEEFFFFFFFFFFGGGGGGGGGGHHHHHHHHHHIIIIIIIIIIJJJJJJJJJJKKKKKKKKKKLLLLLLLL  
  9. ;L+!2rT~hd         8MMMMMMMMMMNNNNNNNNNNOOOOOOOOOOPPPPPPPPPPQQQQQQQQQQRRRRRRRRRRSSSSSSSSSSTTTTTTTT  
  10. M^*dDE;6^<         9UUUUUUUUUUVVVVVVVVVVWWWWWWWWWWXXXXXXXXXXYYYYYYYYYYZZZZZZZZZZAAAAAAAAAABBBBBBBB  



描述一下:每一行,是一条数据。每一条,由2部分组成,前面是一个由10个随即字符组成的key,后面是一个80个字符组成的value。 

排序的任务:按照key的顺序排。 

那么1TB的数据从何而来?答案是用程序随即生成的,用一个只有map,没有reduce的MapReduce job,在整个集群上先随即生成100亿行数据。然后,在这个基础上,再运行排序的MapReduce job,以测试集群排序性能。 


3、排序的原理 

先说明一点,熟悉MapReduce的人都知道:排序是MapReduce的天然特性!在数据达到reducer之前,mapreduce框架已经对这些数据按键排序了。 

所以,在这个排序的job里,不需要特殊的Mapper和Reducer类。用默认的 
IdentityMapper和IdentityReducer即可。 

既然排序是天然特性,那么1TB排序的难点在哪里呢??答:100亿行的数据随即分散在1000多台机器上,mapper和reducer都是Identity的,这个难点就在MapReduce的shuffle阶段!关键在如何取样和怎么写Partitioner。 

好在这个排序的源代码已近包含在hadoop的examples里了,下面我们就来分析一下。 


4、取样和partition的过程 

面对对这么大量的数据,为了partition的更均匀。要先“取样”: 

1) 对Math.min(10, splits.length)个split(输入分片)进行随机取样,对每个split取10000个样,总共10万个样 
2) 10万个样排序,根据reducer的数量(n),取出间隔平均的n-1个样 
3) 将这个n-1个样写入partitionFile(_partition.lst,是一个SequenceFile),key是取的样,值是nullValue 
4) 将partitionFile写入DistributedCache 

接下来,正式开始执行MapReduce job: 
5) 每个map节点: 
          a.根据n-1个样,build一棵类似于B-数的“索引树”: 
                    * 每个非叶子节点,都有256个子节点。 
                    * 不算根节点的非叶子节点有1层,加上根节点和叶子节点,共3层。 
                    * 非叶子节点代表key的“byte path” 
                    * 每个叶子节点代表key的前2个bytes path 
                    * 叶子节点上,保存的是partition number的范围,有多少个reducer就有多少partition number 

          b.前缀相同的key,被分配到同一个叶子节点。 
          c.一个子节点上,可能有多个reducer 
          d.比第i个样小的key,被分配到第i个reducer,剩下的被分配到最后一个reducer。 

6) 针对一个key,partition的过程: 

          a. 首选判断key的第1个byte,找到第1层非叶子节点 
          b. 再根据key的第2个byte,叶子节点 
          c. 每个叶子节点可能对应多个取样(即多个reducer),再逐个和每个样比较,确定分配给哪一个reducer 


5、图解partition的“索引树” 

对上面的文字描述可能比较难理解,etongg 同学建议我画个图。所有才有了下面这些文字。感谢etongg和大家对本帖的关注。 

“索引树”的作用是为了让key快速找到对应的reducer。下图是我画的索引树示意图: 




对上面的图做一点解释: 
1、为了简单,我只画了A、B、C三个节点,实际的是有256个节点的。 
2、这个图假设有20个reducer(下标0到19),那么我们最终获得n-1个样,即19个样(下标为18的为最后一个样) 
3、图中的圆圈,代表索引树上的节点,索引树共3层。 
4、叶子节点下面的长方形代表取样数组。红色的数字代表取样的下标。 
5、每个节点都对应取样数组上的一个下标范围(更准备的说,是对应一个partition number的范围,每个partition number代表一个reducer)。这个范围在途中用蓝色的文字标识。 


前面文中有一句话: 
比第i个样小的key,被分配到第i个reducer,剩下的被分配到最后一个reducer 

这里做一个小小的纠正,应该是: 
小于或者等于第i个样的key,被分配到第i个reducer,剩下的被分配到最后一个reducer。 

下面开始partition: 
如果key以"AAA"开头,被分配到第“0”个reducer。 
如果key以"ACA"开头,被分配到第“4”个reducer。 
如果key以"ACD"开头,被分配到第“4”个reducer。 
如果key以"ACF"开头,被分配到第“5”个reducer。 

那么, 
如果key以"ACZ"开头,被分配到第几个reducer?? 
答案是:被分配到第“6”个reducer。 

同理, 
如果key以"CCZ"开头,被分配到第“19”个reducer,也就是最后一个reducer。 


6、为什么不用HashPartitioner? 


还需要再说明的一点: 
上面自定义的Partitinoner的作用除了快速找到key对应的reducer,更重要的一点是:这个Partitioner控制了排序的总体有序! 

上文中提到的“排序是MapReduce的天然特性!”这句话有点迷惑性。更准确的说,这个“天然特性”只保证了:a) 每个map的输出结果是有序的; b) 每个reduce的输入是有序的(参考下面的图)。而1TB的整体有序还需要靠Partitioner的帮助! 


Partitioner控制了相似的key(即前缀相同)落在同一个reducer里,然后mapreduce的“天然特性”再保证每个reducer的输入(在正式执行reduce函数前,有一个排序的动作)是有序的! 


这样就理解了为什么不能用HashPartitioiner了。因为自定义的Partitioner要保证排序的“整体有序”大方向。 


另外,推荐一篇关于partitioner博文:Hadoop Tutorial Series, Issue #2: Getting Started With (Customized) Partitioning 

再贴《Hadoop.The.Definitive.Guide》中一张图,更有利于理解了: 
 

*** THE END *** 

分享到:
评论

相关推荐

    Hadoop_MapReduce教程

    - Hadoop MapReduce 特别适合处理 TB 或 PB 级别的数据集。 - 如搜索引擎索引构建、社交网络数据分析等。 **2. 实时数据分析** - 虽然 MapReduce 主要用于批处理,但也可以用于实时数据流处理,如通过 Hadoop ...

    Hadoop MapReduce教程.pdf

    **MapReduce**是Google提出的一种编程模型,用于大规模数据集(多TB甚至PB)的并行运算,设计目标是为非专业程序员提供一种简单的并行程序开发方式。Hadoop则是Apache基金会开发的一个开源框架,其核心组件包括HDFS...

    基于 Hadoop 平台,使用 MapReduce 编程,统计NBA球员五项数据.zip

    MapReduce 是一种编程模型,用于大规模数据集(大于 1TB)的并行计算。它的基本思想是将大任务分解为小任务(映射阶段),然后在多台机器上并行处理这些小任务,最后再将结果合并(化简阶段)。在这个案例中,我们...

    Hadoop MapReduce

    Hadoop MapReduce是一个用于处理大数据集的软件框架,它能够将应用程序以并行方式运行在成千上万的商用硬件节点上,同时保证了高可靠性与容错能力。它适用于处理多个TB级别的数据集。 在这个框架中,一个MapReduce...

    大数据--Hadoop MapReduce

    MapReduce是Google提出的一种编程模型,用于大规模数据集(多TB甚至PB)的并行运算。MapReduce将复杂的、运行于大规模集群上的并行计算过程高度地抽象到了两个函数:Map 和 Reduce。 1. **Map阶段**: - 将输入的...

    hadoop mapreduce

    Hadoop MapReduce是一个软件框架,旨在轻松编写能够在大量商用硬件构成的大型集群(成千上万的节点)上并行处理海量数据集(多TB数据集)的应用程序,并以可靠、容错的方式运行。MapReduce框架的核心思想是将一个大...

    Hadoop-2.8.0-Day05-MapReduce编程-课件与资料.zip

    MapReduce是Google提出的一种编程模型,用于大规模数据集(大于1TB)的并行计算。本资料主要针对Hadoop MapReduce编程进行深入讲解,适合于对大数据技术感兴趣的开发者和学习者。 首先,MapReduce的工作原理分为两...

    Hadoop技术内幕 深入解析MapReduce架构设计与实现原理[董西成][带书签].pdf 百度网盘下载

    MapReduce是一种编程模型,用于大规模数据集(通常大于1TB)的并行运算。它的设计理念非常简洁明了:把复杂的任务分解为一系列可以并行处理的小任务。具体来说,MapReduce将数据处理过程分为两个阶段:Map阶段和...

    mapreduce.pdf

    **MapReduce** 是一种编程模型,用于大规模数据集(大于1TB)的分布式计算,它极大简化了开发人员处理海量数据的工作。MapReduce的核心思想是将复杂的、大数据量的计算过程分解成两个基本阶段:Map(映射)和Reduce...

    Hadoop技术内幕:深入解析MapReduce架构设计i与实现原理

    1. **MapReduce概念**:MapReduce是一种编程模型,用于大规模数据集(大于1TB)的并行计算。它将大型任务拆分为小部分,由集群中的多台机器并行处理,最后再将结果合并。 2. **Map阶段**:在这个阶段,原始数据被...

    2020最新-02_第二阶段 hadoop体系之离线计算.txt

    MapReduce是一种编程模型,用于大规模数据集(大于1TB)的并行运算。概念"Map(映射)"和"Reduce(归约)",是它们的主要思想,均为函数式编程语言领域的重要概念,通过扩展,用以进行大数据计算。MapReduce通过将...

    hadoop基本流程与mapReduce应用开发.pdf

    Hadoop 是一个开源的分布式计算框架,主要由HDFS(Hadoop Distributed File System)和MapReduce两大部分组成。Hadoop的设计理念是“移动计算而非移动数据”,它将计算任务分散到数据所在的节点上,以应对大数据量...

    基于mapreduce词权重计算.zip

    它是由Google提出的一种编程模型,用于大规模数据集(大于1TB)的并行计算。Hadoop是实现MapReduce的主要开源框架,它是Apache软件基金会的一个项目,旨在提供可靠、可扩展的数据存储和分布式计算能力。本压缩包...

    尚硅谷大数据技术之Hadoop

    Hadoop是Apache软件基金会开发的一个分布式计算项目,它为大规模数据集(大于1TB)提供了高容错性的分布式存储和计算能力。本课程通过笔记和代码实例,帮助学习者理解并掌握Hadoop的核心概念和技术。 在Hadoop的...

    Hadoop权威指南 第二版(中文版)

     在Apache Hadoop上的TB字节数量级排序  使用Pig和Wukong来探索10亿数量级边的 网络图  测量社区  每个人都在和我说话:Twitter回复关系图  degree(度)  对称链接  社区提取 附录A 安装Apache Hadoop  先决...

    Hadoop权威指南---中文版

    - **Apache Hadoop的1TB排序**:讨论了Hadoop在1TB排序挑战中的表现。 #### 十六、Apache Hadoop的安装 - **安装指南**:提供了详细的步骤来安装Apache Hadoop。 #### 十七、Cloudera的Hadoop分发包 - **Cloudera...

Global site tag (gtag.js) - Google Analytics