- 浏览: 156445 次
- 来自: ...
文章分类
- 全部博客 (151)
- Liferay.in.Action (3)
- 集群 (12)
- web (5)
- jna (2)
- 数据库 (7)
- Terracotta (11)
- xml (1)
- Hibernate (3)
- Jdbc (2)
- DDD (10)
- nosql (7)
- 云存储 (3)
- 云产品 (7)
- 云计算 (26)
- Hadoop (11)
- 虚拟化 (5)
- REST (3)
- 程序人生 (11)
- google (2)
- 安全应用 (5)
- LDAP (0)
- 安全技术 (5)
- android (4)
- 网络妙语 (1)
- HTML5 (1)
- 搜索引擎 (1)
- 架构设计 (5)
- redis (3)
- Cassandra (2)
最新评论
-
liwanfeng:
情况是这样的,你的文件我觉得还是比较小,我现在需要处理的XML ...
dom4j处理大文件
作者 yunsamzhang
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亿条数据?都是什么样的数据呢?让我们来看几条:
- .t^#\|v$2\ 0AAAAAAAAAABBBBBBBBBBCCCCCCCCCCDDDDDDDDDDEEEEEEEEEEFFFFFFFFFFGGGGGGGGGGHHHHHHHH
- 75@~?'WdUF 1IIIIIIIIIIJJJJJJJJJJKKKKKKKKKKLLLLLLLLLLMMMMMMMMMMNNNNNNNNNNOOOOOOOOOOPPPPPPPP
- w[o||:N&H, 2QQQQQQQQQQRRRRRRRRRRSSSSSSSSSSTTTTTTTTTTUUUUUUUUUUVVVVVVVVVVWWWWWWWWWWXXXXXXXX
- ^Eu)<n#kdP 3YYYYYYYYYYZZZZZZZZZZAAAAAAAAAABBBBBBBBBBCCCCCCCCCCDDDDDDDDDDEEEEEEEEEEFFFFFFFF
- +l-$$OE/ZH 4GGGGGGGGGGHHHHHHHHHHIIIIIIIIIIJJJJJJJJJJKKKKKKKKKKLLLLLLLLLLMMMMMMMMMMNNNNNNNN
- LsS8)|.ZLD 5OOOOOOOOOOPPPPPPPPPPQQQQQQQQQQRRRRRRRRRRSSSSSSSSSSTTTTTTTTTTUUUUUUUUUUVVVVVVVV
- le5awB.$sm 6WWWWWWWWWWXXXXXXXXXXYYYYYYYYYYZZZZZZZZZZAAAAAAAAAABBBBBBBBBBCCCCCCCCCCDDDDDDDD
- q__[fwhKFg 7EEEEEEEEEEFFFFFFFFFFGGGGGGGGGGHHHHHHHHHHIIIIIIIIIIJJJJJJJJJJKKKKKKKKKKLLLLLLLL
- ;L+!2rT~hd 8MMMMMMMMMMNNNNNNNNNNOOOOOOOOOOPPPPPPPPPPQQQQQQQQQQRRRRRRRRRRSSSSSSSSSSTTTTTTTT
- M^*dDE;6^< 9UUUUUUUUUUVVVVVVVVVVWWWWWWWWWWXXXXXXXXXXYYYYYYYYYYZZZZZZZZZZAAAAAAAAAABBBBBBBB
.t^#\|v$2\ 0AAAAAAAAAABBBBBBBBBBCCCCCCCCCCDDDDDDDDDDEEEEEEEEEEFFFFFFFFFFGGGGGGGGGGHHHHHHHH 75@~?'WdUF 1IIIIIIIIIIJJJJJJJJJJKKKKKKKKKKLLLLLLLLLLMMMMMMMMMMNNNNNNNNNNOOOOOOOOOOPPPPPPPP w[o||:N&H, 2QQQQQQQQQQRRRRRRRRRRSSSSSSSSSSTTTTTTTTTTUUUUUUUUUUVVVVVVVVVVWWWWWWWWWWXXXXXXXX ^Eu)<n#kdP 3YYYYYYYYYYZZZZZZZZZZAAAAAAAAAABBBBBBBBBBCCCCCCCCCCDDDDDDDDDDEEEEEEEEEEFFFFFFFF +l-$$OE/ZH 4GGGGGGGGGGHHHHHHHHHHIIIIIIIIIIJJJJJJJJJJKKKKKKKKKKLLLLLLLLLLMMMMMMMMMMNNNNNNNN LsS8)|.ZLD 5OOOOOOOOOOPPPPPPPPPPQQQQQQQQQQRRRRRRRRRRSSSSSSSSSSTTTTTTTTTTUUUUUUUUUUVVVVVVVV le5awB.$sm 6WWWWWWWWWWXXXXXXXXXXYYYYYYYYYYZZZZZZZZZZAAAAAAAAAABBBBBBBBBBCCCCCCCCCCDDDDDDDD q__[fwhKFg 7EEEEEEEEEEFFFFFFFFFFGGGGGGGGGGHHHHHHHHHHIIIIIIIIIIJJJJJJJJJJKKKKKKKKKKLLLLLLLL ;L+!2rT~hd 8MMMMMMMMMMNNNNNNNNNNOOOOOOOOOOPPPPPPPPPPQQQQQQQQQQRRRRRRRRRRSSSSSSSSSSTTTTTTTT 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学习笔记之在Eclipse中远程调试Hadoop+0700错误的处理
2012-08-01 00:15 0原文 http://www.blogjava.net/y ... -
数据网格 Data Grid和NoSQL相同和区别-异同
2012-07-31 15:21 0原文 http://www.jdon.com/4372 ... -
Google在新的内容索引系统中放弃MapReduce
2012-07-31 10:30 827原文 http://www.hadoopor.co ... -
微软展开“大数据”蓝图,推进Hadoop至Azure和Windows Server
2012-07-31 10:13 883原文 http://www.iteye.com/news/23 ... -
Hadoop分布式文件系统:架构和设计要点
2012-07-31 10:07 665摘自 http://www.blogjava.net/ ... -
淘宝数据魔方技术架构解析
2012-07-31 10:09 745原文 http://www.programmer.com.c ... -
Apache Hadoop 2.0 Alpha 版发布
2012-07-30 16:10 1855原文 http://www.iteye.com/news/25 ... -
MongoDB Hadoop Connector 1.0 正式版发布
2012-07-30 16:01 880原文 http://www.iteye.com/news/24 ... -
VMware发布开源项目Serengeti,支持云中部署Apache Hadoop
2012-07-30 15:55 775原文 http://www.iteye.com/news/25 ... -
NOSQL数据库大比拼
2012-07-24 14:46 780原文 http://www.jdon.com/3971 ... -
NoSQL数据库探讨之一 - 为什么要用非关系数据库?
2012-07-23 10:50 596NoSQL数据库探讨之一 - ... -
mongodb 应用场景
2012-07-23 10:29 150324 Use Cases24.1 适合场景 Archivin ... -
Hadoop概念及其用法专家讲解
2010-11-08 22:12 1199原文 http://developer.51cto.com/a ... -
开源框架Hadoop实现分布式计算
2010-11-08 22:04 850原文 http://developer.51cto ... -
用 Linux 和 Apache Hadoop 进行云计算
2010-10-31 19:53 984原文 http://www.ibm.com/dev ... -
NoSQL数据库笔谈
2010-10-27 22:56 1199原著作者 颜开 http://www.yankay.com/w ... -
Mongo和Couch对比
2010-10-25 22:38 1062原文 http://www.jdon.com/jive ...
相关推荐
Hadoop 大数据方向 mapreduce计算中的二次排序,讲解透彻
hadoop分区二次排序示例,对基站数据,按电话号码升序、到达时间降序进行排序
hadoop学习笔记-shuffle和排序 shuffle是指将map输出作为输入传给reduce的过程。
hadoop分区二次排序代码示例,包含基站数据集,对基站数据,按电话号码升序、到达时间降序进行排序,只需打包成jar,即可在hadoop集群中运行
Hadoop大作业排序代码 由于 MapReduce 中对 key 进行比较和排序,而 key 可以是任何实 现了 Writable 接口的类。 在 java 中,要实现类的大小比较可以实现 Comparable 接口并通 过重写 compareTo 方法来实现。 在 ...
Hadoop平台技术 排序操作案例.docx 学习资料 复习资料 教学资源
在windows环境下开发hadoop时,需要配置HADOOP_HOME环境变量,变量值D:\hadoop-common-2.7.3-bin-master,并在Path追加%HADOOP_HOME%\bin,有可能出现如下错误: org.apache.hadoop.io.nativeio.NativeIO$Windows....
NULL 博文链接:https://xjward.iteye.com/blog/1816821
英文的,讲解hadoop1.x与hadoop2.x配置异同
hadoop1升级到hadoop2具体步骤及方法
01_hadoop_hdfs1分布式文件系统01 02_hadoop_hdfs1分布式文件系统02 03_hadoop_hdfs1分布式文件系统03 04_hadoop_hdfs1分布式文件系统04 05_hadoop_hdfs1分布式文件系统05 06_hadoop_hdfs1分布式文件系统06 07_...
提供hadoop1-2-1源码,以及hadoop mapreduce例子
主要介绍了hadoop二次排序的原理和实现,本文通过实例代码给大家介绍的非常详细,具有一定的参考借鉴价值,需要的朋友可以参考下
04-hadoop的自定义排序实现.avi 05-mr程序中自定义分组的实现.avi 06-shuffle机制.avi 07-mr程序的组件全貌.avi 08-textinputformat对切片规划的源码分析.avi 09-倒排索引的mr实现.avi 10-多个job在同一个...
hadoop1.x环境搭建及其入门,如需获取更多hadoop资源
在单机环境下按多关键字对大数据排序需要较长的执行时间,为了提高按多关键字对大数据排序的效率,根据Hadoop的MapReduce模型,给出了两种基于Hadoop的多关键字排序方法。方法一在Reduce函数中使用链式基数排序算法...
Hadoop集群·CentOS安装配置(第1期) Hadoop集群·机器信息分布表(第2期) Hadoop集群·VSFTP安装配置(第3期) Hadoop集群·SecureCRT使用(第4期) Hadoop集群·Hadoop安装配置(第5期) Hadoop集群·JDK和SSH无...
Hadoop构建数据仓库实践1——王雪迎
《Hadoop大数据开发实战》教学教案—01初识Hadoop.pdf《Hadoop大数据开发实战》教学教案—01初识Hadoop.pdf《Hadoop大数据开发实战》教学教案—01初识Hadoop.pdf《Hadoop大数据开发实战》教学教案—01初识Hadoop.pdf...
在Hadoop1.x 时代,Hadoop中的MapReduce同时处理业务逻辑运算和资源的调度,耦合性较大。 在Hadoop2.x时代,增加了Yarn。Yarn只负责资源的调度,MapReduce 只负责运算。 Hadoop3.x在组成上没有变化Hadoop ...