MapReduce计算框架中的高性能排序方法

摘要

本发明涉及一种MapReduce计算框架中的高性能排序方法。该方法在Map阶段按照partition分别构建缓冲链，移除partition本身进行排序的需要，并且对于每一个partition数据将按照块进行组织，降低了数据在内存中的拷贝以及文件IO方面的代价；在Map阶段不执行排序操作，在Reduce阶段以一个较大的缓冲池作为一次排序的基本单位，使得在排序的归并阶段总的归并路数是一个用户可调优的值。本发明通过一种混合的内存排序算法，优化了MapReduce框架中排序的两个阶段，基本消除了排序对于计算框架的性能影响，进而提升了计算框架的资源有效性，降低了集群的整体资源消耗。

主权项

一种MapReduce计算框架中的高性能排序方法，其步骤包括：1）Map Task从HDFS上读取文件，构造输入数据的key/value对；2）对输入数据执行用户自定义Map函数并输出中间结果的key/value对，并计算key所对应的partition；对内存中每个partition设置对应的缓冲链，将中间结果的key/value对首先计算长度，然后插入到缓冲链中；3）当内存无法放下所有中间结果的key/value对时，按照partition的顺序，输出所有缓冲链到本地文件；4）对经过上述步骤后在内存和本地磁盘上形成的一个或多个未排序的结果按照partition的顺序进行归并，输出成一个完整的按照partition进行分段的本地文件；5）Reduce Task通过AppMaster获得Map Task结束的信息，向负责该Map数据托管的进程发送http请求，拖取该Map输出的中间数据中属于该Reduce的部分，将这些数据根据其大小选择放于内存或放于本地磁盘；6）将内存或磁盘中的中间数据读入内存中的排序缓冲池，当排序缓冲池满时，对整个缓冲池进行排序；7）对于中间数据无法全部放在一个排序缓冲池中的情况，在排序后将数据写出到本地文件中。