恒速機(jī)上的MapReduce在線排序算法下界研究

姜曉燕 帥天平

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

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

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

0引言

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

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

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

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