赞
踩
排序贯穿于Map任务和Reduce任务,是MapReduce非常重要的一环,排序操作属于MapReduce计算框架的默认行为,不管流程是否需要,都会进行排序。在MapReduce计算框架中,主要用到了两种排序方法:快速排序和归并排序
快速排序:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据比另外一部分的所有数据都小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此使整个数据成为有序序列。
归并排序:归并排序在分布式计算里面用的非常多,归并排序本身就是一个采用分治法的典型应用。归并排序是将两个(或两个以上)有序表合并成一个新的有序表,即把待排序序列分为若干个有序的子序列,再把有序的子序列合并为整体有序序列。
Map任务和Reduce任务的三次排序
第一次排序(快速排序)
当map函数产生输出时,会首先写入内存的环形缓冲区,当达到设定的阈值,在刷写磁盘之前,后台线程会将缓冲区的数据划分成相应的分区。在每个分区中,后台线程按键进行内排序。
第二次排序(归并排序)
在Map任务完成之前,磁盘上存在多个已经分好区,并排好序的、大小和缓冲区一样的溢写文件,这时溢写文件将被合并成一个已分区且已排序的输出文件。由于溢写文件已经经过第一次排序,所以合并文件时只需要再做一次排序就可使输出文件整体有序。
第三次排序(归并排序)
在shuffle阶段,需要将多个Map任务的输出文件合并,由于经过第二次排序,所以合并文件时只需要再做一次排序就可使输出文件整体有序 。
在这3次排序中第一次是在内从缓冲区做的排序,使用的算法是快速排序,第二次排序和第三次排序都是在文件合并阶段发生的,使用的是归并排序。
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。