论文部分内容阅读
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]提出的McNaughtons around rule这一方法,该方法得到的机器的完工时间为Cmax=max{max K=1,2,……,h Tk/Bk,Tn/Bh}, 本章利用该方法设计了一个近似算法, 给出了近似算法的竞争比的上界为2?∑k0j=1sj/∑hj=1sj,其中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任务的长度. 第三章同样研究了?台同类机在线的MapReduce在线排序问题,与第二章不同的是: 本章研究了reduce任务不可中断的情况,工件以over list释放,目标为极小化工件的最大完工时间,同样假设一个工件的map任务完成之后才可以知道该工件reduce任务的信息,本章所采用的算法思想是: 对于到达的工件将map任务放在?台机器上加工, 使得加工完map任务的机器完工时间均相等,然后将reduce任务以LPT规则排序,依据经典排序的LPT规则,设计了近似算法,并得到了该近似算法的竞争比的上界. 第四章是总结了全文主要内容,并对接下来的努力方向提供了参考.