MapReduce是一种流行的批处理框架,用于大规模数据集的并行运算,其主要作用是分布式集群节点分析、保持数据局部原则、使数据更加真实有效.本文主要研究h台同类机,reduce任务可中断和不可中断的MapReduce在线排序模型,目标函数是极小化工件的最大完工时间.本文结构安排如下:第一章主要介绍排序问题的基本知识、MapReduce的基本概念.第二章主要研究h台同类机reduce任务可中断的在线MapReduce排序问题,工件以over list释放.目标函数是极小化工件的最大完工时间.在MapReduce排序模型中有两个假设:一是MapReduce排序的map任务可以并行加工,而reduce任务不可并行加工.二是必须得等一个工件中的map任务加工完成之后才可以加工reduce任务.本章仍沿用这种假设,即假设map任务可以无限分割,即可并行加工,而reduce任务不可并行加工,但在本章中,工件的reduce任务可以中断,该模型假设为只有当map任务完成之后才可以知道reduce任务的信息,所以在本章中设计的算法为工件到达之后先将所有map任务分到h台机器上,使得加工完map任务的h台机器的完工时间相等,对于reduce任务可中断的情况,我们采用了文[26]提出的McNaughton’s around rule这一方法,该方法得到的机器的完工时间为Cmax=max(?),本章利用该方法设计了一个近似算法,给出了近似算法的竞争比的上界为2―(?),其中S1 ≥ S2 ≥...≥sh,其sj是机器j的加工速度,k0为使得Tk/Bk(1 ≤k≤h)达到最大值的机器的编号,h是机器台数,其中Tk = |r1| + |r2| +...+ |rk|,Bk=s1 + s2+…+sk,|r1|≥|r2|≥ …≥ |rm|,|ri| 是第i长reduce任务的长度.第三章同样研究了h台同类机在线的MapReduce在线排序问题,与第二章不同的是:本章研究了 reduce任务不可中断的情况,工件以over list释放,目标为极小化工件的最大完工时间,同样假设一个工件的map任务完成之后才可以知道该工件reduce任务的信息,本章所采用的算法思想是:对于到达的工件将map任务放在h台机器上加工,使得加工完map任务的机器完工时间均相等,然后将reduce任务以LPT规则排序,依据经典排序的LPT规则,设计了近似算法,并得到了该近似算法的竞争比的上界.第四章是总结了全文主要内容,并对接下来的努力方向提供了参考.