文档章节

MapReduce排序过程

牧师-Panda
 牧师-Panda
发布于 2017/04/29 11:12
字数 2023
阅读 41
收藏 0

MapReduce中的数据流动

  • 最简单的过程: map - reduce
  • 定制了partitioner以将map的结果送往指定reducer的过程: map - partition - reduce
  • 增加了在本地先进行一次reduce(优化)的过程: map - combine - partition - reduce

Partition的概念和使用

得到map产生的记录后,他们该分配给哪些reducer来处理呢?hadoop默认是根据散列值来派发,但是实际中,这并不能很高效或者按照我们要求的去执行任务。例如,经过partition处理后,一个节点的reducer分配到了20条记录,另一个却分配到了10W万条,试想,这种情况效率如何。又或者,我们想要处理后得到的文件按照一定的规律进行输出,假设有两个reducer,我们想要最终结果中part-00000中存储的是”h”开头的记录的结果,part-00001中存储其他开头的结果,这些默认的partitioner是做不到的。所以需要我们自己定制partition来选择reducer。自定义partitioner很简单,只要自定义一个类,并且继承Partitioner类,重写其getPartition方法就好了,在使用的时候通过调用Job的setPartitionerClass指定一下即可。

MapReduce基于key的全排序的原理

    如何使用mapreduce来做全排序?最简单的方法就是使用一个partition,因为一个partition对应一个reduce的task,然而reduce的输入本来就是对key有序的,所以很自然地就产生了一个全排序文件。但是这种方法在处理大型文件时效率极低,因为一台机器必须处理所有输出文件,从而完全丧失了mapreduce所提供的并行架构的优势。

    如果是分多个partition呢,则只要确保partition是有序的就行了。首先创建一系列排好序的文件;其次,串联这些文件(类似于归并排序);最后得到一个全局有序的文件。比如有1000个1-10000的数据,跑10个ruduce任务,如果进行partition的时候,能够将在1-1000中数据的分配到第一个reduce中,1001-2000的数据分配到第二个reduce中,以此类推。即第n个reduce所分配到的数据全部大于第n-1个reduce中的数据。这样,每个reduce出来之后都是有序的了,我们只要concat所有的输出文件,变成一个大的文件,就都是有序的了。

    这时候可能会有一个疑问,虽然各个reduce的数据是按照区间排列好的,但是每个reduce里面的数据是乱序的啊?当然不会,不要忘了排序是MapReduce的天然特性 — 在数据达到reducer之前,mapreduce框架已经对这些数据按key排序了。

    但是这里又有另外一个问题,就是在定义每个partition的边界的时候,可能会导致每个partition上分配到的记录数相差很大,这样数据最多的partition就会拖慢整个系统。我们期望的是每个partition上分配的数据量基本相同,hadoop提供了采样器帮我们预估整个边界,以使数据的分配尽量平均

在Hadoop中,patition我们可以用TotalOrderPartitioner替换默认的分区,然后将采样的结果传给他,就可以实现我们想要的分区。在采样时,可以使用hadoop的几种采样工具,如RandomSampler,InputSampler,IntervalSampler。

在map阶段,根据预先定义的patition规则进行分区,map首先将输出写到缓存中,当缓存内容达到阈值时,将结果spill到硬盘,每一次spill都会在硬盘产生一个spill文件,因此一个map task可能会产生多个spill文件。

接下来进入shuffle阶段,当map写出最后一个输出,需要在map端进行一次merge操作,按照partition和partition内的key进行合并和排序,此时每个partition内按照key值整体有序。

然后开始第二次merge,这次是在reduce端,在此期间数据在内存和磁盘上都有,其实这个阶段的merge并不是严格意义上的排序,只是将多个整体有序的文件merge成一个大的文件,最终完成排序工作。

取样和Partition过程详解

面对大量的数据,为了partition均匀,需要先取样:

1.根据所有数据键值对的数目、所有数据split的数目以及设定的每个split取样数目进行取样,比如原有100亿条数据,10个split,对每个split取样1W条,则总共10W个样本;

2.将10W个样本进行全排序,根据reducer的数量n,取出间隔平均的n-1个样本;

3.将这n-1个样本写入二进制文件(默认是 _partition.lst,是一个SequenceFile);

4.将上述二进制文件写入DistributedCache(所有mapper和reducer共享)。

接下来PartitionerClass来读取这个共享的二进制文件,根据这n-1个key生成一个类似于B-树的Tire树,可以加快查找(以空间换取时间),将所有的map输出根据这n-1个不同范围内的key输出到不同partition,这样可以保证第i个partition输出的键值对都比第i+1个partition的键值对的key小。然后每个partition进行一下局部排序即可,从而达到所有的key全局有序。

Trie树,又称单词查找树或键树,是一种树形结构,哈希树的变种。典型应用是用于统计和排序大量的字符串(但不仅限于字符串),所以经常被搜索引擎系统用于文本词频统计。它的优点是:最大限度地减少无谓的字符串比较,查询效率比哈希表高。它有3个基本特性:

  • 根节点不包含字符,除根节点外每一个节点都只包含一个字符。
  • 从根节点到某一节点,路径上经过的字符连接起来,为该节点对应的字符串。
  • 每个节点的所有子节点包含的字符都不相同。

文字比较晦涩,引用一张示意图:

  • 图中假设有n=20,即有20个reducer(下标0到19),那么我们最终获得n-1个样,即19个样(下标为18的为最后一个样);
  • 图中的圆圈,代表单词查找树上的节点;
  • 叶子节点下面的长方形代表取样数组,红色的数字代表取样的下标;
  • 每个节点都对应取样数组上的一个下标范围(更准备的说,是对应一个partition number的范围,每个partition number代表一个reducer)。这个范围在图中用蓝色的文字标识。

则小于或者等于第i个样的key,被分配到第i个reducer,剩下的被分配到最后一个reducer。具体的partition的过程:

如果key以”AAA”开头,被分配到第“0”个reducer。

如果key以”ACA”开头,被分配到第“4”个reducer。

如果key以”ACD”开头,被分配到第“4”个reducer。

如果key以”ACF”开头,被分配到第“5”个reducer。

如果key以”EDZ”开头,被分配到第“19”个reducer。

换句话说,使每个partitioner局部有序的方法,就是根据key值hash的原理,只不过所用的数据结构使得性能有所提升。

本文转载自:http://blog.csdn.net/zr459927180/article/details/51249177

牧师-Panda
粉丝 33
博文 146
码字总数 180044
作品 0
浦东
私信 提问
大数据教程(9.1)流量汇总排序的mr实现

上一章我们有讲到一个mapreduce案例——移动流量排序,如果我们要将最后的输出结果按总流量大小逆序输出,该怎么实现呢?本节博主将分享这个实现的过程。 一、分析 首先,要实现这个功能,我...

em_aaron
2018/12/01
44
0
【Hadoop】- MapReduce 框架详细介绍

MapReduce 简介 说明: 通过由普通机器组成的集群对大量数据集进行并行处理可依靠的容错软件框架。 MapReduce作业可以将数据集分割为Map任务并行处理的数据块,框架对对Map过程产生的数据进行...

ZeroneLove
02/24
24
0
跟A君学大数据(三)--利用MapReduce对多文件数据进行排序

版权声明:本博客所有的原创文章,转载请注明出处,作者皆保留版权。 https://blog.csdn.net/anLA_/article/details/88747102 先来一个小插曲 MapReduce Job中的全局数据 在MapReduce中如何保...

6点A君
03/22
0
0
[转]MapReduce:超大机群上的简单数据处理

MapReduce:超大机群上的简单数据处理 摘要 MapReduce是一个编程模型,和处理,产生大数据集的相关实现.用户指定一个 map函数处理一个key/value对,从而产生中间的key/value对集.然后再指定一个r...

穿越星辰
2011/04/22
174
0
从分治算法到 MapReduce

从分治算法说起 要说 MapReduce 就不得不说分治算法,而分治算法其实说白了,就是四个字 分而治之 。其实就是将一个复杂的问题分解成多组相同或类似的子问题,对这些子问题再分,然后再分。直...

终日而思一
2018/11/23
38
0

没有更多内容

加载失败,请刷新页面

加载更多

OSChina 周六乱弹 —— 早上儿子问我他是怎么来的

Osc乱弹歌单(2019)请戳(这里) 【今日歌曲】 @凉小生 :#今日歌曲推荐# 少点戾气,愿你和这个世界温柔以待。中岛美嘉的单曲《僕が死のうと思ったのは (曾经我也想过一了百了)》 《僕が死の...

小小编辑
今天
783
11
Excption与Error包结构,OOM 你遇到过哪些情况,SOF 你遇到过哪些情况

Throwable 是 Java 中所有错误与异常的超类,Throwable 包含两个子类,Error 与 Exception 。用于指示发生了异常情况。 Java 抛出的 Throwable 可以分成三种类型。 被检查异常(checked Exc...

Garphy
今天
15
0
计算机实现原理专题--二进制减法器(二)

在计算机实现原理专题--二进制减法器(一)中说明了基本原理,现准备说明如何来实现。 首先第一步255-b运算相当于对b进行按位取反,因此可将8个非门组成如下图的形式: 由于每次做减法时,我...

FAT_mt
昨天
6
0
好程序员大数据学习路线分享函数+map映射+元祖

好程序员大数据学习路线分享函数+map映射+元祖,大数据各个平台上的语言实现 hadoop 由java实现,2003年至今,三大块:数据处理,数据存储,数据计算 存储: hbase --> 数据成表 处理: hive --> 数...

好程序员官方
昨天
7
0
tabel 中含有复选框的列 数据理解

1、el-ui中实现某一列为复选框 实现多选非常简单: 手动添加一个el-table-column,设type属性为selction即可; 2、@selection-change事件:选项发生勾选状态变化时触发该事件 <el-table @sel...

everthing
昨天
6
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部