恒速机上的MapReduce在线排序算法下界研究

姜晓燕 帅天平

摘  要： 本文研究源自于MapReduce模型系统的一类排序问题。给定两台恒速机和一批按列表到达的工件，每个工件包含两类任务：Map 任务和Reduce任务。假设Map任务和Reduce任务都是不可中断的，Map任务可以并行处理，即可以任意分割成若干小的任务并在两台机器上同时处理，而Reduce任务只可以在单台机器上处理。一旦工件到达，必须为其指派机器和开工时间，目标是使得这批工件的最后完工时间最小。对|Mj|≥|Rj|的情形， 我们证明了任意在线算法的竞争比不小于.

关键词： MapReduce;在线排序;LS-G算法;竞争比

中图分类号： O223    文献标识码： A    DOI：10.3969/j.issn.1003-6970.2019.01.002

0引言

目前，随着全球信息产业在不断融合发展，网络资源与数据规模也在不断增长，尤其是在科学研究（天文学、生物学、高能物理等）、计算机仿真、互联网应用、电子商务等领域，数据量呈现快速增长的趋势，并由此产生了许多机遇[1]。

传统的数据分析技术已经越来越不适应当前密集型海量数据处理的需求。而近几年兴起的云计算（Cloud Computing），其实本质上是一种新的提供资源按需租用的服务模式，是一种新型的互联网数据中心（Internet Data Center，IDC）业务。

为了解决当今处理海量数据的问题，Google 实验室提出了云计算中的MapReduce[2]模型解决了这个问题，尽管MapReduce的分布式模型技术在模式上很简单，但还存在许多问题，比如需要数据分析人员自行设计编写Map与Reduce函数的具体细节，所以传统的算法需要重新设计，才能更好地实现代码向数据迁移这一目标，由此传统算法的Map Reduce排序成为一个研究热点，而在本文中我们主要研究MapReduce排序算法的完工时间问题。

MapReduce系统在执行任务的过程时，首先加工到达工件的Map任务，产生中间键值对，然后再加工相对应的Reduce任务[7]。其实MapReduce讲的就是“分而治之”的程序处理理念，把一个复杂的任务划分为若干个简单的任务分别來做。其执行流程图[7]如下：