MapReduce排序问题

向右看齐 2023-01-18 12:23 98阅读 0赞

排序是MapReduce的灵魂，MapReduce在Map和Reduce的两个阶段当中，都在反复地执行排序。

在MapReduce中有两种排序方式，分别是快速排序和归并排序——

快速排序：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

归并排序：归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法，该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。

**MapReduce过程中的几次排序**

在MapReduce的shuffle过程中通常会执行三次排序，分别是：

Map的溢写阶段：根据分区以及key进行快速排序

Map的合并溢写文件：将同一个分区的多个溢写文件进行归并排序，合成大的溢写文件

Reduce输入阶段：将同一分区，来自不同Map task的数据文件进行归并排序

此外，在MapReduce整个过程中，默认是会对输出的KV对按照key进行排序的，而且是使用快速排序。

Map输出的排序，其实也就是上面的溢写过程中的排序。

Reduce输出的排序，即Reduce处理完数据后，MapReduce内部会自动对输出的KV按照key进行排序。

**MapReduce如何执行排序**

在Map端：

每个Map任务都有一个环形的内存缓冲区用于存储任务输出。缓冲区达到一定的阈值(默认80%)，一条后台线程便开始把内容溢出(spill)到磁盘。每次内存缓冲区达到溢出阈值，就会新建一个溢出文件(spill file)。

在写磁盘之前，线程首先根据数据最终要传的Reduce把数据划分成相应的分区(partition)。在每个分区中，后台线程按键进行内存中排序(排序是在Map端进行的)。如果有combiner函数就会在排序后的输出上运行，为了让Map输出结果更加紧凑。

在任务完成之前，溢出文件被合并成一个已分区且已排序的输出文件。如果溢出文件多于设置的数量，combiner就会在输出文件写到磁盘之前再次运行。

在Reduce端：

复制阶段，如果Map的输出相当小，会被复制到Reduce任务的JVM内存中；否则Map输出被复制到磁盘。随着磁盘上副本增多，后台线程会将它们合并为更大的、排好序的文件。

排序阶段，准确的说是合并阶段。复制完成Map的输出后，将合并Map输出，维持其顺序排序。最后一趟的合并来自内存和磁盘片段。

Reduce阶段，执行Reduce任务，把最后一趟合并的数据直接输入Reduce函数，从而省略了一次磁盘往返行程。

发表评论取消回复

表情：

评论列表（有 0 条评论，98人围观）

还没有评论，来说两句吧...

相关阅读

相关 MapReduce - A - 排序 - TreeSet

题目： > 求评分(平均值)最高的前10的电影id？(输出:moveid 平均分) > 思路： > Map中获取数据，键：电影好，值：电影信息类（实现Comp...

刺骨的言语ヽ痛彻心扉/ 2024年04月18日 14:12/ 0 赞/ 11 阅读

相关 MapReduce排序问题

排序是MapReduce的灵魂，MapReduce在Map和Reduce的两个阶段当中，都在反复地执行排序。在MapReduce中有两种排序方式，分别是快速排序和归并排序—

向右看齐/ 2023年01月18日 12:23/ 0 赞/ 99 阅读

相关 MapReduce中的排序

哪些阶段存在排序 1. 在MapReduce的shuffle阶段共有三次排序，分别是： Map的溢写（spill）阶段：根据分区及key进行快速排序；

青旅半醒/ 2022年12月05日 10:12/ 0 赞/ 107 阅读

相关 MapReduce排序

> 一、键排序 > > 原数据：两列分别是品牌、销售额 > > Hino 3153 > Toyota 177649 > Buick 296183 >

- 日理万妓/ 2022年09月21日 15:22/ 0 赞/ 112 阅读

相关 mapreduce的全排序问题

关于全排序的问题 Tom White的书中提出的数据取样方法，最近学习了一下，下面做个比较，以防后患！！主要思想就是在要排序的所有数据中随机取出一定量的数据

刺骨的言语ヽ痛彻心扉/ 2022年09月18日 02:00/ 0 赞/ 104 阅读

相关 mapreduce二次排序

本代码几乎涵盖mapreduce的全部过程 package secondarSort; import java.io.DataInput;

Myth丶恋晨/ 2022年07月16日 04:22/ 0 赞/ 117 阅读

相关 MapReduce实现分组排序

MapReduce实现分组排序以某次竞赛为例，分别进行如果实现：取每组中男生前三名成绩和女生前三名成绩按照年龄分组降序输出所有人的成绩等

绝地灬酷狼/ 2022年06月08日 10:52/ 0 赞/ 208 阅读

相关 MapReduce TopN问题

分析：利用MapReduce如何实现类似Wordcount的TopN问题数据源： 1 A 10 2 A 40 3 B

女爷i/ 2022年06月03日 07:13/ 0 赞/ 121 阅读

相关 hadoop_mapreduce_排序

在执行job时会进行排序，实则是对k2进行排序自定义类在Java的排序需要实现Comparable接口。自定义类在Mapreduce的排序需要实现WritableCom

太过爱你忘了你带给我的痛/ 2022年05月25日 06:26/ 0 赞/ 196 阅读

相关 MapReduce中的排序

hadoop的计算模型就是map/reduce，每一个计算任务会被分割成很多互不依赖的map/reduce计算单元，将所有的计算单元执行完毕后整个计算任务就完成了。因为计算单元

阳光穿透心脏的1/2处/ 2021年12月09日 03:17/ 0 赞/ 184 阅读