整套大数据学习资料(视频+笔记)百度网盘无门槛下载:http://www.edu360.cn/news/content?id=3377

8.2.3. 全排序

hadoop 小红牛 57℃ 0评论

如何用Hadoop产生一个全局排序的文件?最简单的方法是使用一个分区(a single partition)但该方法在处理大型文件时效率极低,因为一台机器必须处理所有输出文件,从而完全丧失了MapReduce所提供的并行架构的优势。

事实上仍有替代方案:首先,创建一系列排好序的文件其次,串联这些文件最后,生成一个全局排序的文件。主要的思路是使用一个partitioner来描述输出的全局排序。例如,可以为上述文件创建4个分区,在第一分区中,各记录的气温小于-10℃,第二分区的气温介于-10℃0之间,第三个分区的气温在010之间,最后一个分区的气温大于10

该方法的关键点在于如何划分各个分区。理想情况下,各分区所含记录数应该大致相等,使作业的总体执行时间不会受制于个別reducer。在前面提 到的分区方案中,各分区的相对大小如下所示。

气温范围

<-1O℃

[-10℃,0℃)

[0℃,10℃)

≥10

记录所占的比例

11%

13%

17%

59%

 

显然,记录没有被均匀划分。只有深入了解整个数据集的气温分布才能建立更均匀的分区。写一个MapReduce作业来计算落入各个气温桶的记录数,并不困难。例如,图8-1显示了桶大小为1℃时各桶的分布情况,各点分别对应一个桶。

获得气温分布信息意味着可以建立一系列分布非常均匀的分区。但由于该操作需要遍历整个数据集,因此并不实用。通过对键空间进行采样,就可较为均匀地划分数据集。采样的核心思想是只査看一小部分键,获得键的近似分布,并由此构建分区。幸运的是,Hadoop已经内置了若干采样器,不需要用户自己编写。

InputSampler类实现了Sampler接口,该接口的唯一成员方法(即getSampler)有两个输入参数(一个InputFormat对象和一个Job对象),返回一系列样本键:

public interface Sampler<K, V> {
    K[] getSample(InputFormat<K, V> inf, Job job)
     throws IOException, InterruptedException;
}

该接口通常不直接由客户端调用,而是由InputSampler类的静态方法writePartitionFile()调用,目的是创建一个顺序文件来存储定义分区的键。

public static <K, V> void writePartitionFile(Job job, Sampler<K, V> sampler) throws IOException, ClassNotFoundException, InterruptedException

blob.png 

8-1.天气数据集合的气温分布

顺序文件由TotalOrderPartitioner使用,为排序作业创建分区。范例8-8整合了上述内容。

 

范例8-8.调用TotalOrderPartitioner按IntWritable键对顺序文件进行全局排序

public class SortByTemperatureUsingTotalOrderPartitioner extends Configured implements Tool {
    @Override
    public int run(String[] args) throws Exception {
        Job job = JobBuilder.parselnputAndOutput(this, getConf(), args);
        if (job == null) {
            return -1;
        }
        job.setInputFormatClass(SequenceFileInputFormat.class);
        job.setOutputKeyClass(IntWritable.class);
        job.setOutputFormatClass(SequenceFileOutputFormat.class);
        SequenceFileOutputFormat.setCompressOutput(job, true);
        SequenceFileOutputFormat.setOutputCompressorClass(job, GzipCodec.class);
        SequenceFileOutputFormat.setOutputCompressionType(job,CompressionType.BLOCK);
        job.setPartitionerClass(TotalOrderPartitioner.class);
         
        InputSampler.Sampler<IntWritable, Text> sampler = new InputSampler.RandomSampler<IntWritable, Text>(0.1, 10000, 10);
        InputSampler.writePartitionFile(job, sampler);
         
        // Add to DistributedCache
        Configuration conf = job.getConfiguration();
        String partitionFile =TotalOrderPartitioner.getPartitionFile(conf);
        URI partitionUri = new URI(partitionFile + "#" + TotalOrderPartitioner.DEFAULT_PATH);
        DistributedCache.addCacheFile(partitionUri, conf);
        DistributedCache.createSymlink(conf);
        return job.waitForCompletion(true) ? 0 : 1;
    }
public static void main(String[] args) throws Exception {
        int exitCode = ToolRunner.run(
            new SortByTemperatureUsingTotalOrderPartitioner(), args);
        System.exit(exitCode);
    }
}

该程序使用RandomSampler以指定的采样率均匀地从一个数据集中选择样本。在本例中,采样率被设为0.1RamdomSampler的输入参数还包括最大样本数和最大分区(本例中这两个参数分别是1000010,这也是InputSampler作为应用程序运行时的默认设置),只要任意一个限制条件满足,即停止采样。采样器在客户端运行,因此,限制分片的下载数量以加速采样器的运行就尤为重要。在实践中,采样器的运行时间仅占作业总运行时间的一小部分。

为了和集群上运行的其他任务共享分区文件,InputSampler需将其所写的分区文件加到分布式缓存中(参见8.4.2节)。

以下方案别以-5.6℃、13.9℃和22.0℃为边界得到4个分区。易知,新方案比旧方案更为均匀。

气温范围

<5.6℃

[ -5.6℃, 13.9℃)

[13.9℃, 22.0℃)

≥22.0℃

记录所占的比例

29%

24%

23%

24%

 

输入数据的特性决定如何挑选最合适的采样器。以SplitSampler为例,它只采样一个分片中的前n条记录。由于并未从所有分片中广泛采样,该采样器并不适合已经排好序的数据。

另一方面,IntervalSample以一定的间隔定期从分片中选择键,因此对于已排好序的数据来说是一个更好的选择。RandomSampler是优秀的通用采样器。如果没有采样器可以满足应用需求(记住,采样目的是创建大小近似相等的一系列分区),则只能写程序来实现Sampler接口。

InputSampler类和TotalOrderPartitioner类的一个好特性是用户可以自由定义分区数,该值通常取决于集群上reducer槽的数量(该值需稍小于reducer槽的总数,以应付可能出现的故障)。由于TotalOrderPartitioner只用于分区边界均不相同的时候,因而当键空间较小时,设置太大的分区数可能会导致数据冲突。

以下是运行方式:

% hadoop jar hadoop-examples.jar SortByTemperatureUsingTotalOrderPartitioner \

-D mapred.reduce.tasks=30 input/ncdc/all-seq output-totalsort

该程序输出30个已经内部排好序的分区。且分区i中的所有键都小于分区 i+1中的键。


转载请注明:全栈大数据 » 8.2.3. 全排序

喜欢 (0)or分享 (0)
发表我的评论
取消评论

表情

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址