姜曉燕 帥天平

摘? 要： 本文研究源自于MapReduce模型系統(tǒng)的一類排序問題。給定兩臺恒速機和一批按列表到達的工件，每個工件包含兩類任務(wù)：Map 任務(wù)和Reduce任務(wù)。假設(shè)Map任務(wù)和Reduce任務(wù)都是不可中斷的，Map任務(wù)可以并行處理，即可以任意分割成若干小的任務(wù)并在兩臺機器上同時處理，而Reduce任務(wù)只可以在單臺機器上處理。一旦工件到達，必須為其指派機器和開工時間，目標(biāo)是使得這批工件的最后完工時間最小。對|Mj|≥|Rj|的情形， 我們證明了任意在線算法的競爭比不小于.

關(guān)鍵詞： MapReduce;在線排序;LS-G算法;競爭比

中圖分類號： O223? ? 文獻標(biāo)識碼： A? ? DOI：10.3969/j.issn.1003-6970.2019.01.002

0引言

目前，隨著全球信息產(chǎn)業(yè)在不斷融合發(fā)展，網(wǎng)絡(luò)資源與數(shù)據(jù)規(guī)模也在不斷增長，尤其是在科學(xué)研究（天文學(xué)、生物學(xué)、高能物理等）、計算機仿真、互聯(lián)網(wǎng)應(yīng)用、電子商務(wù)等領(lǐng)域，數(shù)據(jù)量呈現(xiàn)快速增長的趨勢，并由此產(chǎn)生了許多機遇[1]。

傳統(tǒng)的數(shù)據(jù)分析技術(shù)已經(jīng)越來越不適應(yīng)當(dāng)前密集型海量數(shù)據(jù)處理的需求。而近幾年興起的云計算（Cloud Computing），其實本質(zhì)上是一種新的提供資源按需租用的服務(wù)模式，是一種新型的互聯(lián)網(wǎng)數(shù)據(jù)中心（Internet Data Center，IDC）業(yè)務(wù)。

為了解決當(dāng)今處理海量數(shù)據(jù)的問題，Google 實驗室提出了云計算中的MapReduce[2]模型解決了這個問題，盡管MapReduce的分布式模型技術(shù)在模式上很簡單，但還存在許多問題，比如需要數(shù)據(jù)分析人員自行設(shè)計編寫Map與Reduce函數(shù)的具體細節(jié)，所以傳統(tǒng)的算法需要重新設(shè)計，才能更好地實現(xiàn)代碼向數(shù)據(jù)遷移這一目標(biāo)，由此傳統(tǒng)算法的Map Reduce排序成為一個研究熱點，而在本文中我們主要研究MapReduce排序算法的完工時間問題。

MapReduce系統(tǒng)在執(zhí)行任務(wù)的過程時，首先加工到達工件的Map任務(wù)，產(chǎn)生中間鍵值對，然后再加工相對應(yīng)的Reduce任務(wù)[7]。其實MapReduce講的就是“分而治之”的程序處理理念，把一個復(fù)雜的任務(wù)劃分為若干個簡單的任務(wù)分別來做。其執(zhí)行流程圖[7]如下：