`

hadoop几种排序简介

 
阅读更多

在map reduce框架中,除了常用的分布式计算外,排序也算是比较重要的一环了。这形如sql查询中的排序数据一样重要。

 

 

一。无排序

当书写code 时,如果指定了mapred.reduce.tasks=0(same effect as setNumReduceTasks)。这样便达到目的。

产生的效果当然是只有一个part file,而且其中的entries是unorder.

 

 

二。默认排序(sort only in partition)

其实这也称”局部排序“。这种情况是产生若干个part files,并且各file内部是排序好的,但file之间没有内容排序之分。

 

 

三。全局排序

当你使用TotalOrderPartitioner来作partitioner时,便可以了(注意在mapreduce lib中已经删除了)。当然要更新 一下它的setPartitionFile(xx),以便它利用样本估算得出边界的几个参数(数量是reduces num - 1)。但通常会使用InputSampler.RandomSampler实现来取样。

具体的算法如下 :

/**
     * Randomize the split order, then take the specified number of keys from
     * each split sampled, where each key is selected with the specified
     * probability and possibly replaced by a subsequently selected key when
     * the quota of keys from that split is satisfied.
     */
public K[] getSample(InputFormat<K,V> inf, JobConf job) throws IOException {
      InputSplit[] splits = inf.getSplits(job, job.getNumMapTasks());
      ArrayList<K> samples = new ArrayList<K>(numSamples);
      int splitsToSample = Math.min(maxSplitsSampled, splits.length);  //取多少样本(splits)

      Random r = new Random();
      long seed = r.nextLong();
      r.setSeed(seed);
      LOG.debug("seed: " + seed);
      // shuffle splits;其实就 是随机交換splits达到混乱的效果显得更加均匀。
      for (int i = 0; i < splits.length; ++i) {
        InputSplit tmp = splits[i];
        int j = r.nextInt(splits.length);
        splits[i] = splits[j];
        splits[j] = tmp;
      }
      // our target rate is in terms of the maximum number of sample splits,
      // but we accept the possibility of sampling additional splits to hit
      // the target sample keyset
      for (int i = 0; i < splitsToSample ||
                     (i < splits.length && samples.size() < numSamples); ++i) {
        RecordReader<K,V> reader = inf.getRecordReader(splits[i], job,
            Reporter.NULL);
        K key = reader.createKey();
        V value = reader.createValue();
        while (reader.next(key, value)) {
          if (r.nextDouble() <= freq) {    // 概率要小于初始概率 
            if (samples.size() < numSamples) {  //未达到上限时直接添加样本
              samples.add(key);
            } else {
              // When exceeding the maximum number of samples, replace a
              // random element with this one, then adjust the frequency
              // to reflect the possibility of existing elements being
              // pushed out
              int ind = r.nextInt(numSamples); /// 否则更新某个样本元素
              if (ind != numSamples) {
                samples.set(ind, key);
              }
              freq *= (numSamples - 1) / (double) numSamples; //更新了之后降低后续更新概率,否则太频繁了。
            }
            key = reader.createKey();
          }
        }
        reader.close();
      }
      return (K[])samples.toArray();
    }
 

利用上述返回值,hadoop便 会得出此样本的比例情况。具体的算法我没有找到在哪里实现,但大概我认为是这样的:

1.利用当前100 / reduce num / 100来得出平均概率分布;

2.对样本进行排序

3.由低到高(相反也可以)逐个区间进行各种key占比例统计,当达到平均概率值(当然允许有偏差)时停止此区间的添加 ,并得到最大key作为第一个边界值 ;

4.同样道理处理其它keys

5.这样处理可能最后出现很多组边界值,所以得有一个优化算法再进一步筛选。

 

不过我尝试实现过,发现这种计算也是挺复杂 的,因为你不知道该什么时候结束;而且要记住不同情况下的边界值。

我认为hadoop也会设置一个offset值,并且限制优化次数。TODO 有空我会继续找源码看看。


 

四。分组(二次排序)

这个功用就类似于sql中的group by clause,就是对已经排序的数据再进一步key去重。

实现也是很简单的,过程大概是这样:

1.生成复合键;

之所以生成复合键,因为hadoop最終排序的是key而不是value.这个我有统计日志时就 过同样需求了。

即在通常的key后加入其它要grouping values。

 

2.利用复合键来排序;

这过程基本上是利用复合键中的所有参数进行,因为毕竟你最終目标是同key的只要一个(最大或最小 ,这是group特性)

当然你也要写个partitioner否则,原本相同key的去到不同的reduce中。

 

3.对复合键分组;

在这个Comparator中,要将过滤的条件写要里面即可。比如按照原key只要第一条数据:

return compsedKeyObject.key.compare(that.key)

这样在进入reduce前有相同的key便被过滤了。

 

 

另外,也有可能是三四组合,这样达到各part files之间有序,同时也达到了grouping的效果。

 

其实二次排序关键的是明白group来对key进行逻辑分组功能。

 

 

 

 

 

 

 

 

 

 

 

分享到:
评论

相关推荐

    hadoop介绍

    #### 一、Hadoop简介 **Hadoop** 是一个能够对大量数据进行分布式处理的软件框架,它最初由Nutch和Lucene之父Doug Cutting于2006年创建。有趣的是,“Hadoop”这个名字来源于Doug Cutting的儿子对他玩具大象的一种...

    新版Hadoop视频教程 段海涛老师Hadoop八天完全攻克Hadoop视频教程 Hadoop开发

    07-MR程序的几种提交运行模式.avi 08-YARN的通用性意义.avi 09-yarn的job提交流程.avi 第四天 常见mr算法实现和shuffle的机制 01-复习.avi 02-hadoop中的序列化机制.avi 03-流量求和mr程序开发.avi 04-...

    Hadoop权威指南,hadoop权威指南pdf,Hadoop

    该书详细讲解了Hadoop的生态系统,包括但不限于以下几个方面: 1. **Hadoop架构**:Hadoop主要由两个核心组件构成:HDFS(Hadoop Distributed File System)和MapReduce。HDFS是一种高容错性的分布式文件系统,能够...

    hadoop实验+作业.zip

    3. MapReduce编程:编写MapReduce程序处理数据,理解Mapper和Reducer的工作原理,以及中间键值对的分区和排序过程。 4. 性能优化:实验可能包括如何调整Hadoop参数以优化性能,如修改Map和Reduce的任务数量,设置...

    hadoop段海涛老师八天实战视频

    07-MR程序的几种提交运行模式.avi 08-YARN的通用性意义.avi 09-yarn的job提交流程.avi 第四天 常见mr算法实现和shuffle的机制 01-复习.avi 02-hadoop中的序列化机制.avi 03-流量求和mr程序开发.avi 04-...

    基于Hadoop的排序性能优化研究

    首先对基于Hadoop平台的几种高效的排序算法(Quicksort,Heapsort和Mergesort算法)进行了研究。再通过对Hadoop平台的几种现有的排序算法的分析比较,发现频繁的读写磁盘降低数据处理的效率,提出了一种优化现有排序...

    hadoop 入门

    - Shuffle与Sort:Mapper的输出被排序并分组,为Reducer准备输入。 - Reduce阶段:Reducer处理来自Mapper的键值对,执行聚合或汇总操作,产生最终结果。 2. **Hadoop 应用开发** 开发Hadoop应用通常涉及编写...

    Hadoop实现大矩阵乘法

    对于非常大的矩阵,传统的单机计算方法会面临内存和计算时间的限制,而Hadoop的MapReduce模型则提供了一种解决方案。 MapReduce是Hadoop的核心组件,它将复杂任务分解为可并行执行的map任务和reduce任务。在大矩阵...

    hadoop经典实战教程

    #### 一、Hadoop简介与生态系统 - **Hadoop概念**:Hadoop是一个能够对大量数据进行分布式处理的软件框架。它通过提供高可靠性和高扩展性的分布式计算能力,使得用户能够在廉价的商用硬件上处理PB级别的数据。 - **...

    Hadoop对文本文件的快速全局排序实现方法及分析

    Hadoop是一个开源框架,它允许在分布式环境中存储大量数据,并通过MapReduce模型运行并行运算。...通过上面介绍的几种方法,可以有效地对Hadoop中的Text文件进行快速全局排序,满足不同场景下的需求。

    Hadoop与 Oracle 数据库集成.pdf

    本文将详细介绍Hadoop与Oracle数据库集成的相关知识点,包括Hadoop与Oracle之间的几种主要集成方式及其应用场景。 #### 二、Hadoop与Oracle数据库集成的主要方式 ##### 1. Oracle Hadoop装载器 (Oracle Hadoop ...

    hadoop 运行原理分析

    从程序员的角度来看,使用Hadoop进行开发需要遵循以下几个步骤: 1. 定义Mapper类和Reducer类,分别处理输入数据和进行数据归约。 2. 定义Job,即整个MapReduce任务,包括输入输出格式、Mapper类、Reducer类以及...

    hadoop流量统计程序

    "hadoop流量统计程序"是基于Hadoop平台设计的一种工具,用于收集、处理和分析网络流量数据。这个程序能够帮助网络管理员或者数据分析人员有效地监控和理解网络活动,识别潜在的流量异常,以及优化网络资源的分配。 ...

    hadoop开源项目分析

    Hadoop的架构设计围绕着分布式计算的需求展开,主要包括以下几个核心组件: - **Hadoop Distributed File System (HDFS)** - **组成部分**: - **NameNode**:负责管理和维护文件系统的元数据,如文件名、权限和...

    hadoop简单示例源码

    3. **排序与分区**:经过map阶段后,数据会被按照键(年份)进行排序,并分配到不同的reduce任务中。这一步是MapReduce的关键部分,确保同一键的数据被送到同一个reducer。 4. **Reduce阶段**:`reduce()`函数接收...

    hadoop各种资料

    学习Hadoop时,你需要掌握以下几个关键概念: 1. **数据分片(Block)**:HDFS将大文件分割成多个块,并在集群中的多台机器上复制,以确保数据的可靠性和可用性。 2. **NameNode和DataNode**:NameNode是HDFS的元...

    Hadoop集群-WordCount运行详解.pdf

    1.3WordCount源码分析中,1.3.1特别数据类型介绍了Hadoop自定义的几种数据类型,它们在实现MapReduce程序中扮演重要角色。1.3.2旧的WordCount分析与1.3.3新的WordCount分析,从源码层面解读了旧版和新版的WordCount...

    hadoop的简单配置文件

    - **shuffle阶段**:数据的排序和分区,将map阶段的结果按照key进行排序,并分发到对应的reduce任务。 - **reduce阶段**:对map阶段的结果进行汇总,生成最终结果。 3. **配置文件详解**: - `conf`目录下的文件...

    深入云计算 Hadoop源代码分析

    为了提高Hadoop处理数据的效率,通常采用以下几种优化策略: 1. **本地化策略**:尽可能将计算任务调度到包含所需数据的节点上运行,减少网络传输延迟。 2. **数据压缩**:在不影响数据完整性的前提下,对数据进行...

    hadoop_join.jar.zip_hadoop_hadoop query_reduce

    通常,Hadoop中的Join可以分为几种类型:Bucket Join、Sort-Merge Join、Replicated Join和Map-Side Join等。每种Join策略都有其适用场景和优缺点。 `hadoop_join.jar`是一个针对Hadoop环境设计的Join查询工具,它...

Global site tag (gtag.js) - Google Analytics