- 浏览: 358403 次
- 性别:
- 来自: 上海
文章分类
最新评论
-
希恩杰:
采样器的目的是啥?使数据均匀分布到所有分区?使key的数量均匀 ...
Hadoop深入学习:Hadoop全排序中的Sampler采样器 -
lawlietwf:
三篇文章中有两篇链接地址一样,po主看下
Hadoop中的快速排序算法 -
坏小四:
...
《Hbase权威指南》深入学习hbase:表,列族,列标识,版本和cell -
fbwfbi:
发现使用pika-0.9.13的版本依然出错:Tracebac ...
RabbitMQ:使用python发布/订阅消息 -
hehu158:
centos6.5 chmod +x qq2012.tra.g ...
CentOS 6.4安装qq2012
Hadoop深入学习:Hadoop全排序中的Sampler采样器
- 博客分类:
- Hadoop
在Partitioner组件的设计与实现中,我们已经了解过Partitioner组件的其中一个和全排序相关的实现类——TotalOrderPartitioner。
我们知道,在Hadoop中,最终的处理结果集中的数据,除非就由一个Reduce Task处理,否则结果数据集只是局部有序而非全排序。
这节我们来学习在Hadoop中进行全排序操作中除了TotalOrderPartitioner之外的另一个组件——采样器Sampler。
在新版本的Hadoop中,内置了三个采样器: SplitSampler,RandomSampler和IntervalSampler。这三个采样器都是InputSampler类的静态内部类,并且都实现了InputSampler类的内部接口Sampler,涉及的相关代码如下:
从上面的代码及注释中我们可以了解该采样器是如何对数据采样的。对于每一个分区,读取一条记录,将这条记录添加到样本集合中,如果当前样本数大于当前的采样分区所需要的样本数,则停止对这个分区的采样。如此循环遍历完这个分区的所有记录。
SplitSampler
我们首先着重来看一下SplitSampler采样器是如何对数据采样的,先看其取样处理逻辑代码:
IntervalSampler
再来看一下IntervalSampler采样器是如何来对数据采样的:
从上面的代码可以看到,该采样器和SplitSampler采样器很像。对于每一个分区,读取一条记录,如果当前样本数与已经读取的记录数的比值小于freq,则将这条记录添加到样本集合,否则读取下一条记录。这样依次循环遍历完这个分区的所有记录。
RandomSampler
RandomSampler是一个随机数据采样器,效率最低,其采样过程是这样处理的:
首先通过InputFormat的getSplits方法得到所有的输入分区;然后确定需要抽样扫描的分区数目,取输入分区总数与用户输入的maxSplitsSampled两者的较小的值得到splitsToSample;然后对输入分区数组shuffle排序,打乱其原始顺序;然后循环逐个扫描每个分区中的记录进行采样,循环的条件是当前已经扫描的分区数小于splitsToSample或者当前已经扫描的分区数超过了splitsToSample但是小于输入分区总数并且当前的采样数小于最大采样数numSamples。
每个分区中记录采样的具体过程如下:
从指定分区中取出一条记录,判断得到的随机浮点数是否小于等于采样频率freq,如果大于则放弃这条记录,然后判断当前的采样数是否小于最大采样数,如果小于则这条记录被选中,被放进采样集合中,否则从【0,numSamples】中选择一个随机数,如果这个随机数不等于最大采样数numSamples,则用这条记录替换掉采样集合随机数对应位置的记录,同时采样频率freq减小变为freq*(numSamples-1)/numSamples。然后依次遍历分区中的其它记录。
下面是几个采样器之间的比较:
当然,如果Hadoop内置的采样器不满足用户需求,那么用户可以完全编写自定义的采样器。
我们知道,在Hadoop中,最终的处理结果集中的数据,除非就由一个Reduce Task处理,否则结果数据集只是局部有序而非全排序。
这节我们来学习在Hadoop中进行全排序操作中除了TotalOrderPartitioner之外的另一个组件——采样器Sampler。
在新版本的Hadoop中,内置了三个采样器: SplitSampler,RandomSampler和IntervalSampler。这三个采样器都是InputSampler类的静态内部类,并且都实现了InputSampler类的内部接口Sampler,涉及的相关代码如下:
/** * Utility for collecting samples and writing a partition file for * {@link org.apache.hadoop.mapred.lib.TotalOrderPartitioner}. */ public class InputSampler<K,V> implements Tool { ... /** *采样器接口 */ public interface Sampler<K,V> { /** * 从输入数据几种获得一个数据采样的子集,然后通过这些采样数据在Map端由 * TotalOrderPartitioner对处理数据做hash分组,以保证不同Reduce处理数据的有序性。 * 该方法的具体采样逻辑由继承类实现。 * For a given job, collect and return a subset of the keys from the * input data. */ K[] getSample(InputFormat<K,V> inf, JobConf job) throws IOException; } /** * 分片数据采样器,即从N个分片中采样,效率最高 * Samples the first n records from s splits. * Inexpensive way to sample random data. */ public static class SplitSampler<K,V> implements Sampler<K,V> { ... } /** * 通用的随机数据采样器,按一定的频率对所有数据做随机采样,效率很低 * Sample from random points in the input. * General-purpose sampler. Takes numSamples / maxSplitsSampled inputs from * each split. */ public static class RandomSampler<K,V> implements Sampler<K,V> { ... } /** * 有固定采样间隔的数据采样器,适合有序的数据集,效率较随机数据采样器要好一些 * Sample from s splits at regular intervals. * Useful for sorted data. */ public static class IntervalSampler<K,V> implements Sampler<K,V> { ... } ... }
从上面的代码及注释中我们可以了解该采样器是如何对数据采样的。对于每一个分区,读取一条记录,将这条记录添加到样本集合中,如果当前样本数大于当前的采样分区所需要的样本数,则停止对这个分区的采样。如此循环遍历完这个分区的所有记录。
SplitSampler
我们首先着重来看一下SplitSampler采样器是如何对数据采样的,先看其取样处理逻辑代码:
/** * Samples the first n records from s splits. * Inexpensive way to sample random data. */ public static class SplitSampler<K,V> implements Sampler<K,V> { ... /** * From each split sampled, take the first numSamples / numSplits records. */ @SuppressWarnings("unchecked") // ArrayList::toArray doesn't preserve type public K[] getSample(InputFormat<K,V> inf, JobConf job) throws IOException { //通过InputFormat组件读取所有的分片信息,之前在InputFormat组件的学习中已学习过 InputSplit[] splits = inf.getSplits(job, job.getNumMapTasks()); ArrayList<K> samples = new ArrayList<K>(numSamples); //获得采样分区数,在最大采样数最大分区数和总分区数中选择较小的 int splitsToSample = Math.min(maxSplitsSampled, splits.length); //获取采样分区间隔 int splitStep = splits.length / splitsToSample; //计算获取每个分区的采样数 int samplesPerSplit = numSamples / splitsToSample; long records = 0; for (int i = 0; i < splitsToSample; ++i) { //获取第(i * splitStep)分片的RecordReader对象,并由该对象解析将数据解析成key/value RecordReader<K,V> reader = inf.getRecordReader(splits[i * splitStep], job, Reporter.NULL); K key = reader.createKey(); V value = reader.createValue(); while (reader.next(key, value)) {//向采样的空key和value中读入数据 //将采样的key加入samples数组 samples.add(key); key = reader.createKey(); ++records; if ((i+1) * samplesPerSplit <= records) {//判断是否满足采样数 break; } } reader.close(); } //返回采样的key的数组,供TotalOrderPartitioner使用 return (K[])samples.toArray(); } }
IntervalSampler
再来看一下IntervalSampler采样器是如何来对数据采样的:
public static class IntervalSampler<K,V> implements Sampler<K,V> { ... /** * 根据一定的间隔从s个分区中采样数据,非常适合对排好序的数据采样 * For each split sampled, emit when the ratio of the number of records * retained to the total record count is less than the specified * frequency. */ @SuppressWarnings("unchecked") // ArrayList::toArray doesn't preserve type public K[] getSample(InputFormat<K,V> inf, JobConf job) throws IOException { //通过InputFormat组件读取所有的分片信息 InputSplit[] splits = inf.getSplits(job, job.getNumMapTasks()); ArrayList<K> samples = new ArrayList<K>(); //获得采样分区数,在最大采样数最大分区数和总分区数中选择较小的 int splitsToSample = Math.min(maxSplitsSampled, splits.length); //获取采样分区间隔 int splitStep = splits.length / splitsToSample; long records = 0; long kept = 0; for (int i = 0; i < splitsToSample; ++i) { //获取第(i * splitStep)分片的RecordReader对象,并由该对象解析将数据解析成key/value RecordReader<K,V> reader = inf.getRecordReader(splits[i * splitStep], job, Reporter.NULL); K key = reader.createKey(); V value = reader.createValue(); while (reader.next(key, value)) {//向采样的空key和value中读入数据 ++records; if ((double) kept / records < freq) {//判断当前样本数与已经读取的记录数的比值小于freq ++kept; samples.add(key); key = reader.createKey(); } } reader.close(); } //返回采样的key的数组,供TotalOrderPartitioner使用 return (K[])samples.toArray(); } }
从上面的代码可以看到,该采样器和SplitSampler采样器很像。对于每一个分区,读取一条记录,如果当前样本数与已经读取的记录数的比值小于freq,则将这条记录添加到样本集合,否则读取下一条记录。这样依次循环遍历完这个分区的所有记录。
RandomSampler
RandomSampler是一个随机数据采样器,效率最低,其采样过程是这样处理的:
首先通过InputFormat的getSplits方法得到所有的输入分区;然后确定需要抽样扫描的分区数目,取输入分区总数与用户输入的maxSplitsSampled两者的较小的值得到splitsToSample;然后对输入分区数组shuffle排序,打乱其原始顺序;然后循环逐个扫描每个分区中的记录进行采样,循环的条件是当前已经扫描的分区数小于splitsToSample或者当前已经扫描的分区数超过了splitsToSample但是小于输入分区总数并且当前的采样数小于最大采样数numSamples。
每个分区中记录采样的具体过程如下:
从指定分区中取出一条记录,判断得到的随机浮点数是否小于等于采样频率freq,如果大于则放弃这条记录,然后判断当前的采样数是否小于最大采样数,如果小于则这条记录被选中,被放进采样集合中,否则从【0,numSamples】中选择一个随机数,如果这个随机数不等于最大采样数numSamples,则用这条记录替换掉采样集合随机数对应位置的记录,同时采样频率freq减小变为freq*(numSamples-1)/numSamples。然后依次遍历分区中的其它记录。
下面是几个采样器之间的比较:
当然,如果Hadoop内置的采样器不满足用户需求,那么用户可以完全编写自定义的采样器。
发表评论
-
CentOS 6.4 hadoop集成 Hbase Hive
2013-07-10 00:05 2354在之前的CentOS 5.4 hadoop集 ... -
CentOS 6.4 hadoop集成 Hbase Zookeeper
2013-07-09 22:41 2529再上一章中我们已经学习了Hadoop-1.0. ... -
CentOS 6.4 hadoop集成Hive
2013-07-09 01:58 2417在本节中,我们来学习如何安装Hive。在之前我 ... -
Hadoop深入学习:MapReduce Job中的Shuffle和sort
2013-07-06 22:30 1484... -
Hadoop深入学习:解析HDFS的写文件流程
2013-07-06 16:43 7308之前,我们 ... -
Hadoop深入学习:再谈MapReduce作业提交和执行
2013-07-03 22:00 2031在本章中,我们将来重温一下和Hadoop的作业 ... -
CentOS 6.4 安装伪分布式Hadoop 1.0.3
2013-07-02 00:52 2383在本章中学习如何在CentOS 6.4上安装配 ... -
Hadoop深入学习:Combiner
2013-07-04 00:03 10637在本节中,我们着重学习MapReduce编程模 ... -
Hadoop深入学习:MapReduce的Shuffle过程详解
2013-05-29 22:11 5190在本节中,我们再来仔细回顾一下MapRedu ... -
Hadoop深入学习:ReduceTask详解
2013-05-28 16:16 1538本节我们来着重学习ReduceTask的内部操 ... -
Hadoop深入学习:MapTask详解
2013-05-28 15:23 4571在本节中 ... -
Hadoop深入学习:MapReduce中的心跳机制
2013-05-28 13:13 3218在本节中,我们特别来学习一些有心跳(Heart ... -
Hadoop深入学习:MapReduce作业提交和初始化
2013-05-27 22:24 4519之前已经学过了MapReduce接口编程模型及 ... -
Hadoop深入学习:OutputFormat组件
2013-05-27 16:45 2622在本节中,我们着重来学习一下MapReduc ... -
Hadoop深入学习:Reduce组件详解
2013-05-27 15:59 1454在本节中我们主要来学习MapReduce编程接 ... -
Hadoop深入学习:Partitioner组件的设计与实现
2013-05-27 15:31 3435本节我们来学习MapReduce编程框架中的P ... -
Hadoop深入学习:Mapper组件详解
2013-05-26 22:29 2218本节我们主要学习MapReduce编程接口模型 ... -
Hadoop深入学习:InputFormat组件
2013-05-26 22:26 8519在本节里, ... -
Hadoop深入学习:MapReduce的序列化
2013-05-26 20:27 2140在学习MapReduce ... -
Hadoop深入学习:MapReduce的编程模型
2013-05-26 19:43 1616MapReduce的一个设计目标就是易用性,它 ...
相关推荐
Hadoop 技术内幕:深入解析Hadoop Common 和HDFS 架构设计与实现原理
Hadoop技术内幕:深入解析Hadoop Common 和HDFS 架构设计与实现原理 (大数据技术丛书) 原版书籍,非扫描版,使用kindle可以打开,也可以转换为epub使用ibooks打开
《Hadoop技术内幕:深入解析Hadoop Common和HDFS架构设计与实现原理》还从源代码实现中对分布式技术的精髓、分布式系统设计的优秀思想和方法,以及Java语言的编码技巧、编程规范和对设计模式的精妙运用进行了总结和...
除此之外,《Hadoop技术内幕:深入解析Hadoop Common和HDFS架构设计与实现原理》还从源代码实现中对分布式技术的精髓、分布式系统设计的优秀思想和方法,以及Java语言的编码技巧、编程规范和对设计模式的精妙运用进行...
### Hadoop技术内幕:深入解析MapReduce架构设计与实现原理 #### 一、Hadoop及其重要性 Hadoop是一个开放源代码的分布式计算框架,它能够处理大量的数据集,并通过集群提供高性能的数据处理能力。随着大数据时代的...
Hadoop硬实战:Hadoop in Practice
Hadoop技术内幕:深入解析MapReduce架构设计i与实现原理Hadoop技术内幕:深入解析MapReduce架构设计i与实现原理Hadoop技术内幕:深入解析MapReduce架构设计i与实现原理Hadoop技术内幕:深入解析MapReduce架构设计i与...
一、前言 我们小组主要对基于[hadoop的大规模数据排序算法、海量数据的生成做了一定的...第五阶段,对一些源代码进行分析,主要是排序算法中的sort. java, secondsort. java, terasort。下面的正文中将作出具体的介绍。
Hadoop技术内幕:深入解析YARN架构设计与实现原理(扫描版)Hadoop技术内幕:深入解析YARN架构设计与实现原理(扫描版)Hadoop技术内幕:深入解析YARN架构设计与实现原理(扫描版)
Hadoop技术内幕:深入解析MapReduce架构设计与实现原理(扫描版)Hadoop技术内幕:深入解析MapReduce架构设计与实现原理(扫描版)Hadoop技术内幕:深入解析MapReduce架构设计与实现原理(扫描版)
《Hadoop技术内幕深入解析YARN架构设计与实现原理》.(董西成).PDF
《hadoop技术内幕:深入解析yarn架构设计与实现原理》是“hadoop技术内幕”系列的第3本书,前面两本分别对common、hdfs和mapreduce进行了深入分析和讲解,赢得了极好的口碑,hadoop领域几乎人手一册,本书则对yarn...
《Hadoop权威指南》是大数据领域的一本经典著作,它深入浅出地介绍了Hadoop这一开源框架,如何处理和分析海量数据。这本书的第4版不仅进行了修订,还增加了新的内容,使其更适合当前大数据环境的需求。 Hadoop是...
《Hadoop技术内幕:深入解析...为了深入学习Hadoop MapReduce,读者需要获取这本书,并结合实际编程练习来加深理解和应用。对于想要从事大数据处理或已经在该领域工作的专业人士,这本书将是一份宝贵的参考资料。
Hadoop技术内幕:深入解析Hadoop Common和HDFS架构设计与实现原理(扫描版)
Hadoop技术内幕:深入解析MapReduce架构设计与实现原理
赠送jar包:hadoop-auth-2.6.5.jar 赠送原API文档:hadoop-auth-2.6.5-javadoc.jar 赠送源代码:hadoop-auth-2.6.5-sources.jar 包含翻译后的API文档:hadoop-auth-2.6.5-javadoc-API文档-中文(简体)-英语-对照版...
hadoop&spark:Hive是一个基于Hadoop的数据仓库平台.zip