【转】大数据【五十九】Map Reduce中的排序

一。排序的分类

排序贯穿于Map任务和Reduce任务，是MapReduce非常重要的一环，排序操作属于MapReduce计算框架的默认行为，不管流程是否需要，都会进行排序。在MapReduce计算框架中，主要用到了两种排序方法：快速排序和归并排序

快速排序：

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

归并排序：

    归并排序在分布式计算里面用的非常多，归并排序本身就是一个采用分治法的典型应用。归并排序是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个有序的子序列，再把有序的子序列合并为整体有序序列。
在map任务和reduce任务的过程中，一共发生3次排序操作。

二。mapperReducer中的排序

    在这3次排序中第一次是在内从缓冲区做的排序，使用的算法是快速排序，第二次排序和第三次排序都是在文件合并阶段发生的，使用的是归并排序

第一次排序

     当map函数产生输出时，会首先写入内存的环形缓冲区，当达到设定的阈值，在刷写磁盘之前，后台线程会将缓冲区的数据划分成相应的分区。在每个分区中，后台线程按键进行内排序。

    一旦缓冲区内容达到阈值（mapreduce.map.io.sort.spill.percent,默认0.80，或者80%），就会会锁定这80%的内存，并在每个分区中对其中的键值对按键进行sort排序，具体是将数据按照partition和key两个关键字进行排序，排序结果为缓冲区内的数据按照partition为单位聚集在一起，同一个partition内的数据按照key有序。

第二次排序

    在Map任务完成之前，磁盘上存在多个已经分好区，并排好序的、大小和缓冲区一样的溢写文件，这时溢写文件将被合并成一个已分区且已排序的输出文件。由于溢写文件已经经过第一次排序，所以合并文件时只需要再做一次排序就可使输出文件整体有序。

    当整个map任务完成溢出写后，会对磁盘中这个map任务产生的所有临时文件（spill文件）进行归并（merge）操作生成最终的正式输出文件。此时的归并是将所有spill文件中的相同partition合并到一起，并对各个partition中的数据再进行一次排序（sort），生成key和对应的value-list

第三次排序

     在shuffle阶段，需要将多个Map任务的输出文件合并，由于经过第二次排序，所以合并文件时只需要再做一次排序就可使输出文件整体有序 。

   当属于该reducer的map输出全部拷贝完成，则会在reducer上生成多个文件（如果拖取的所有map数据总量都没有内存缓冲区，则数据就只存在于内存中），这时开始执行合并操作，即磁盘到磁盘merge，Map的输出数据已经是有序的，Merge进行一次合并排序，所谓Reduce端的sort过程就是这个合并的过程，采取的排序方法跟map阶段不同，因为每个map端传过来的数据是排好序的，因此众多排好序的map输出文件在reduce端进行合并时采用的是归并排序，针对键进行归并排序。

文章转载：https://blog.****.net/IqqIqqIqqIqq/article/details/81710369

参考：大数据【五十二】【转】MapReduce的shuffle过程详解（分片、分区、合并、归并。。。）

三。自己百度百科的内容：

【归并排序】百度百科   

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

归并排序原理

归并排序具体工作原理如下（假设序列共有n个元素）：

将序列每相邻两个数字进行归并操作（merge)，形成floor(n/2+n%2)个序列，排序后每个序列包含两个元素

将上述序列再次归并，形成floor(n/4)个序列，每个序列包含四个元素

重复步骤2，直到所有元素排序完毕