大數(shù)據(jù)存儲架構(gòu)和算法研究綜述

楊俊杰　廖卓凡　馮超超

摘要：

隨著大數(shù)據(jù)計算需求的增長，集群的處理速度需要得到快速的提升，然而目前大數(shù)據(jù)處理框架的處理性能已逐漸滿足不了這種快速增長的需求。由于集群的存儲架構(gòu)是分布式存儲，因此數(shù)據(jù)的存放在大數(shù)據(jù)處理過程中成為影響集群的處理性能的因素之一。首先，對當(dāng)今的分布式文件存儲系統(tǒng)的結(jié)構(gòu)進(jìn)行了介紹；接著，根據(jù)不同的優(yōu)化目標(biāo)，例如減少網(wǎng)絡(luò)負(fù)載、負(fù)載均衡、降低能耗和高容錯性等，對近年國內(nèi)外大數(shù)據(jù)存儲算法的研究進(jìn)行了總結(jié)，分析和對比了已有算法的優(yōu)點以及存在的問題；最后，對大數(shù)據(jù)存儲架構(gòu)和優(yōu)化算法設(shè)計的挑戰(zhàn)和未來研究方向作了展望。

關(guān)鍵詞：

大數(shù)據(jù)；數(shù)據(jù)部署；分布式文件系統(tǒng)；MapReduce；Hadoop

中圖分類號：

TP393

文獻(xiàn)標(biāo)志碼：A

Abstract：

With the growing demand of big data computing， the processing speed of the cluster needs to be improved rapidly. However， the processing performance of the existing big data framework can not satisfy the requirement of the computing development gradually. As the framework of the storage is distributed， the placement of data to be processed has become one of the key factors affecting the performance of the cluster. Firstly， the current distributed file system structure was introduced. Then the popular data placement algorithms were summarized and classified according to different optimization goals， such as network load balance， energy saving and fault tolerance. Finally， future challenges and research directions in the area of storage framework and algorithms were presented.

英文關(guān)鍵詞Key words：

big data； data placement； distributed file system； MapReduce； Hadoop

0引言

隨著互聯(lián)網(wǎng)的高速發(fā)展和迅速普及，我們已經(jīng)進(jìn)入了一個信息爆炸型的時代，大數(shù)據(jù)處理的需求正在迅速增加，在科學(xué)、工業(yè)、商業(yè)等領(lǐng)域，信息處理量達(dá)到TB級甚至PB級已是正常現(xiàn)象。因此，尋求優(yōu)秀的大數(shù)據(jù)處理模型對于處理數(shù)據(jù)密集型應(yīng)用是非常重要的。

相對于傳統(tǒng)的數(shù)據(jù)，人們將大數(shù)據(jù)的特征總結(jié)為5個 V，即數(shù)據(jù)量大（Volume）、速度快（Velocity）、類型多（Variety）、難辨識（Veracity）和價值密度低（Value）[1]。數(shù)據(jù)量大仍可以靠擴(kuò)展儲存在一定程度上緩解，然而要求及時響應(yīng)、數(shù)據(jù)多樣性和數(shù)據(jù)不確定性是傳統(tǒng)數(shù)據(jù)處理方法所不能解決的。

為了應(yīng)對這種大數(shù)據(jù)所帶來的困難和挑戰(zhàn)，諸多大型互聯(lián)網(wǎng)公司近幾年推出了各種類型的大數(shù)據(jù)處理系統(tǒng)。2004年，Google公司提出的MapReduce編程模型是面向大數(shù)據(jù)處理技術(shù)的具體實現(xiàn)，在學(xué)術(shù)界和工業(yè)界引起了很大反響[1]。隨后Apache基金會根據(jù)MapReduce模型開發(fā)出開源的大數(shù)據(jù)處理框架Hadoop在Yahoo！、IBM、百度等公司得到了大量的應(yīng)用和快速的發(fā)展[2]。然而，作為一個新興的技術(shù)，大數(shù)據(jù)處理技術(shù)在很多地方還存在著很多不足，如調(diào)用分布式的數(shù)據(jù)所造成的延遲、巨大的數(shù)據(jù)吞吐量與不相符的網(wǎng)絡(luò)速率所造成的網(wǎng)絡(luò)負(fù)載嚴(yán)重的問題等。因此，國內(nèi)外諸多學(xué)者們一直在找尋較好的數(shù)據(jù)存儲方法以加強(qiáng)大數(shù)據(jù)處理的綜合能力。本文首先對目前較為流行的大數(shù)據(jù)存儲結(jié)構(gòu)進(jìn)行了介紹，然后對近幾年的大數(shù)據(jù)存儲策略方面的優(yōu)化進(jìn)行了總結(jié)，最后對全文進(jìn)行了總結(jié)并提出對未來的展望。

1數(shù)據(jù)存儲結(jié)構(gòu)

1.1傳統(tǒng)集中式數(shù)據(jù)存儲

傳統(tǒng)互聯(lián)網(wǎng)數(shù)據(jù)的創(chuàng)造和使用多以企業(yè)為主，數(shù)據(jù)的種類較為單一，又多以結(jié)構(gòu)化數(shù)據(jù)為主，數(shù)據(jù)的管理以數(shù)據(jù)庫的形式存在；企業(yè)根據(jù)自身對數(shù)據(jù)需求的不同，制定適用于自身的數(shù)據(jù)庫模式（schema），而后才產(chǎn)生數(shù)據(jù)；數(shù)據(jù)僅作為一種處理對象，并不能用來輔助解決其他問題； 數(shù)據(jù)多是由企業(yè)自身來訪問，因此集中式存儲是比較合適的存儲方式[3]。

在互聯(lián)網(wǎng)快速發(fā)展的過程中，隨著網(wǎng)絡(luò)應(yīng)用的數(shù)據(jù)量的加大，企業(yè)已感覺到存儲的容量和性能逐漸落后互聯(lián)網(wǎng)發(fā)展的需求。在此背景下，一些滿足企業(yè)需求的數(shù)據(jù)存儲技術(shù)便應(yīng)運而生，可總結(jié)為直連式存儲、網(wǎng)絡(luò)附加存儲和存儲區(qū)域網(wǎng)絡(luò)三大類

1.1.1直連式存儲

直連式存儲（Direct Attached Storage， DAS）是指將外部存儲設(shè)備通過數(shù)據(jù)接口直接掛載在服務(wù)器的內(nèi)部總線上，存儲設(shè)備是整個服務(wù)器的一部分。這種存儲方式適用于一些對存儲要求不高的小型服務(wù)器，但由于存儲設(shè)備與服務(wù)服務(wù)器之間的連接通常使用小型計算機(jī)系統(tǒng)接口（Small Computer System Interface， SCSI），其傳輸速度較慢，且服務(wù)器的SCSI接口資源有限，隨著存儲需求的不斷增大和服務(wù)器運行速度的提升，存儲設(shè)備的輸入輸出將成為服務(wù)器的瓶頸。

1.1.2網(wǎng)絡(luò)附加存儲

網(wǎng)絡(luò)附加存儲（Network Attached Storage， NAS）則將外部存儲設(shè)備與服務(wù)器通過網(wǎng)絡(luò)技術(shù)（如以太網(wǎng)）連接，存儲設(shè)備不再是服務(wù)器的一部分，而是網(wǎng)絡(luò)中的獨立節(jié)點。NAS雖然能解決接口資源的限制，但是因數(shù)據(jù)的存取轉(zhuǎn)移至網(wǎng)絡(luò)，反而會加重網(wǎng)絡(luò)的負(fù)載，而且隨著存儲容量的擴(kuò)展，性能會進(jìn)一步下降。

1.1.3存儲區(qū)域網(wǎng)絡(luò)

存儲區(qū)域網(wǎng)絡(luò)（Storage Area Network， SAN）是通過光纖交換機(jī)為存儲設(shè)備建立高速專用網(wǎng)絡(luò)，采用光纖通道（Fibre Channel， FC）技術(shù)將服務(wù)器和存儲設(shè)備相連接。這種結(jié)構(gòu)擴(kuò)展能力強(qiáng)，且允許任何服務(wù)器可連接到任何存儲陣列，實現(xiàn)了高速共享存儲；而且由于采用光纖接口，SAN還具有更高的帶寬。但由于光纖成本較高，且技術(shù)實現(xiàn)較復(fù)雜，會導(dǎo)致后期管理和升級成本較高。

1.2分布式數(shù)據(jù)存儲

傳統(tǒng)的集中式存儲對搭建和管理的要求較高。由于硬件設(shè)備的集中存放，機(jī)房的空間、散熱和承重等都有嚴(yán)格的要求；存儲設(shè)備要求性能較好，對主干網(wǎng)絡(luò)的帶寬也有較高的要求[4]。信息爆炸的時代，人們可以獲取的數(shù)據(jù)呈指數(shù)倍的增長，單純在固定某個地點進(jìn)行硬盤的擴(kuò)充在容量大小、擴(kuò)充速度、讀寫速度和數(shù)據(jù)備份等方面上的表現(xiàn)都無法達(dá)到要求；而且大數(shù)據(jù)處理系統(tǒng)的數(shù)據(jù)多是來自于客戶，數(shù)據(jù)的種類多，存儲系統(tǒng)需要存儲各種半結(jié)構(gòu)化、非結(jié)構(gòu)化的數(shù)據(jù)，如文檔、圖片、視頻等，因此大數(shù)據(jù)的存儲宜使用分布式文件系統(tǒng)來管理這些非結(jié)構(gòu)化數(shù)據(jù)。

分布式數(shù)據(jù)存儲，即存儲設(shè)備分布在不同的地理位置，數(shù)據(jù)就近存儲，帶寬上沒有太大壓力。可采用多套低端的小容量的存儲設(shè)備分布部署，設(shè)備價格和維護(hù)成本較低。小容量設(shè)備分布部署，對機(jī)房環(huán)境要求也較低。分布式數(shù)據(jù)存儲將數(shù)據(jù)分散在多個存儲節(jié)點上，各個節(jié)點通過網(wǎng)絡(luò)相連，對這些節(jié)點的資源進(jìn)行統(tǒng)一的管理。這種設(shè)計對用戶是透明的，系統(tǒng)為用戶提供文件系統(tǒng)的訪問接口，使之與傳統(tǒng)的本地文件系統(tǒng)操作方式類似。這樣的設(shè)計解決了傳統(tǒng)的本地文件系統(tǒng)在文件大小、文件數(shù)量等方面的限制。

傳統(tǒng)的分布式計算系統(tǒng)中通常計算節(jié)點與存儲節(jié)點是分開的。當(dāng)執(zhí)行計算任務(wù)時，首先要把數(shù)據(jù)從數(shù)據(jù)節(jié)點傳輸至計算節(jié)點（數(shù)據(jù)向計算遷移），這種處理方式會使外存文件數(shù)

據(jù)I/O訪問成為一個制約系統(tǒng)性能的瓶頸。為了減少大數(shù)據(jù)并行計算系統(tǒng)中的數(shù)據(jù)通信開銷，應(yīng)當(dāng)考慮將計算向數(shù)據(jù)靠攏和遷移。如MapReduce模型采用了數(shù)據(jù)/代碼互定位的技術(shù)方法，該方法讓計算節(jié)點首先盡量負(fù)責(zé)計算其本地存儲的數(shù)據(jù)，以發(fā)揮數(shù)據(jù)本地化特點；僅當(dāng)節(jié)點無法處理本地數(shù)據(jù)時，再采用就近原則尋找其他可用計算節(jié)點，并把數(shù)據(jù)傳送到該可用計算節(jié)點。

1.3分布式數(shù)據(jù)存儲的典型結(jié)構(gòu)

目前比較主流的分布式文件系統(tǒng)結(jié)構(gòu)是主/從（master/slave）體系結(jié)構(gòu)，如圖1所示，通常包括主控節(jié)點（或稱元數(shù)據(jù)服務(wù)器，通常會配置一個活動節(jié)點和一個備用節(jié)點以實現(xiàn)高可用性）、多個數(shù)據(jù)節(jié)點（或稱存儲節(jié)點）和各種大數(shù)據(jù)應(yīng)用或者終端用戶組成的客戶端。分布式存儲的目的是將大數(shù)據(jù)劃分為小數(shù)據(jù)，均勻分布至多個數(shù)據(jù)節(jié)點上，將數(shù)據(jù)的規(guī)模降到單個節(jié)點可以處理的程度。

1.3.1主控節(jié)點

主控節(jié)點主要負(fù)責(zé)管理文件系統(tǒng)名字空間（namespace）和管理客戶端的訪問。常見的命名空間結(jié)構(gòu)有經(jīng)典的目錄樹結(jié)構(gòu)如Hadoop分布式文件系統(tǒng)（Hadoop Distributed File System， HDFS）等，扁平化結(jié)構(gòu)如【淘寶分布式文件系統(tǒng)（Taobao Distributed File System， TFS）等。為了維護(hù)命名空間，主控節(jié)點需要存儲一些元數(shù)據(jù)（metadata），如文件的所有者和權(quán)限、文件到數(shù)據(jù)節(jié)點的映射關(guān)系等。除了管理命名空間，主控節(jié)點還要集中管理數(shù)據(jù)節(jié)點。通過對數(shù)據(jù)節(jié)點輪詢或接收來自數(shù)據(jù)節(jié)點的定期心跳（heartbeat）消息。除了管理命名空間，主控節(jié)點還要對數(shù)據(jù)節(jié)點輪詢或接收來自數(shù)據(jù)節(jié)點的定期心跳（heartbeat）來集中管理數(shù)據(jù)節(jié)點。

主控節(jié)點根據(jù)得到的消息可以驗證文件系統(tǒng)的元數(shù)據(jù)；若發(fā)現(xiàn)數(shù)據(jù)節(jié)點有故障，主控節(jié)點將采取修復(fù)措施，重新復(fù)制在該節(jié)點丟失的數(shù)據(jù)塊；若有新的數(shù)據(jù)節(jié)點加入或某個數(shù)據(jù)節(jié)點負(fù)載過高，主控節(jié)點會根據(jù)情況執(zhí)行負(fù)載均衡。

1.3.2數(shù)據(jù)節(jié)點

數(shù)據(jù)節(jié)點負(fù)責(zé)數(shù)據(jù)在集群上的持久化儲存。數(shù)據(jù)節(jié)點通常以機(jī)架的形式組織，機(jī)架通過交換機(jī)連接起來。數(shù)據(jù)節(jié)點響應(yīng)來自客戶端的讀寫請求，還響應(yīng)來自主控節(jié)點的刪除和復(fù)制命令。

類似于磁盤的結(jié)構(gòu)，在數(shù)據(jù)節(jié)點中也有塊（block）的概念，這是數(shù)據(jù)讀寫的最小單位，不過這里的塊是一個很大的單元，在很多文件系統(tǒng)中通常為64MB，如google的GFS、HDFS和TFS等。對于小文件的儲存，可以將多個文件儲存在一個塊中，并建立索引，提高空間利用率；對于大文件的儲存，則會將數(shù)據(jù)劃分為多個數(shù)據(jù)塊，并作為獨立的單元進(jìn)行儲存。

為了保證數(shù)據(jù)的安全性和容錯性，分布式文件系統(tǒng)會存儲多個數(shù)據(jù)副本在數(shù)據(jù)節(jié)點上。當(dāng)數(shù)據(jù)不可用時，可調(diào)用存放在其他節(jié)點上的副本。在HDFS系統(tǒng)中，副本的基本存儲策略是：在任務(wù)運行的節(jié)點上存儲第一個副本；在任務(wù)所在機(jī)架內(nèi)的其他節(jié)點中的某一節(jié)點存儲第二個副本；在集群的其他機(jī)架中的某一節(jié)點存儲第三個副本。

1.4分布式存儲系統(tǒng)存在的挑戰(zhàn)

雖然計算向數(shù)據(jù)遷移的方法在很大程度上提升了大數(shù)據(jù)集群的處理性能，但這種處理方式仍存在很多問題，性能仍然有很大的提升空間，如數(shù)據(jù)副本的存儲造成的數(shù)據(jù)冗余過多，執(zhí)行負(fù)載平衡或副本失效時進(jìn)行的數(shù)據(jù)遷移產(chǎn)生的巨大的網(wǎng)絡(luò)開銷等。隨著數(shù)據(jù)密集型的應(yīng)用和大數(shù)據(jù)處理需求的急劇增長，以及處理框架仍不成熟，數(shù)據(jù)的存儲策略成為了影響處理性能的重要因素，如何改進(jìn)數(shù)據(jù)的存儲策略來提升處理框架已成為當(dāng)今學(xué)術(shù)界的研究熱門。目前，分布式存儲系統(tǒng)存在的挑戰(zhàn)主要體現(xiàn)在如何減少跨數(shù)據(jù)節(jié)點的網(wǎng)絡(luò)傳輸、如何在保證負(fù)載均衡的同時提升處理性能，以及如何在保證可靠性的前提下節(jié)約能耗等問題[4]。

2大數(shù)據(jù)集群中數(shù)據(jù)存儲優(yōu)化

根據(jù)上述分布式存儲的基本架構(gòu)和所存在的挑戰(zhàn)可知，大數(shù)據(jù)處理系統(tǒng)在存儲方面仍有很大的改進(jìn)空間，改進(jìn)數(shù)據(jù)的存儲策略已成為提升大數(shù)據(jù)處理系統(tǒng)的性能的熱點方向。大數(shù)據(jù)服務(wù)提供者可根據(jù)其所關(guān)注的重點不同，如數(shù)據(jù)傳輸、負(fù)載平衡、運營開銷、運行效率等方面可以制定側(cè)重點不同的優(yōu)化方案。

在眾多的大數(shù)據(jù)處理模型中，MapReduce以它良好的性價比和可擴(kuò)展性、易于理解、易于使用，且能提供良好的數(shù)據(jù)處理性能等優(yōu)點，受到大數(shù)據(jù)服務(wù)提供者廣泛的歡迎并迅速得到應(yīng)用[1]。MapReduce已成為一種經(jīng)典的大數(shù)據(jù)處理模型。因此本文歸納的存儲策略優(yōu)化算法皆以MapReduce模型為基礎(chǔ)。

2.1減少網(wǎng)絡(luò)負(fù)載的優(yōu)化

根據(jù)集群計算的特性，系統(tǒng)所運行的任務(wù)與之所需的數(shù)據(jù)可能不在同一處理節(jié)點上，此時便需要通過網(wǎng)絡(luò)來進(jìn)行數(shù)據(jù)的傳輸。然而根據(jù)如今的硬件水平，網(wǎng)絡(luò)的傳輸速度遠(yuǎn)遠(yuǎn)小于計算機(jī)的處理和輸入輸出的速度，這會成為拖慢大數(shù)據(jù)集群作業(yè)的瓶頸。因此減少集群計算網(wǎng)絡(luò)傳輸，增強(qiáng)數(shù)據(jù)的本地化存儲是一種有效的改善集群處理能力的方法。

2.1.1根據(jù)數(shù)據(jù)相關(guān)性的存儲優(yōu)化

數(shù)據(jù)相關(guān)性是指某些任務(wù)所需要的數(shù)據(jù)具有某些特點（如使用頻率、大小、與其他數(shù)據(jù)同時使用等），若盡可能將相關(guān)性高的數(shù)據(jù)存放在計算節(jié)點，則在計算時直接從本地硬盤調(diào)取，無需占用網(wǎng)絡(luò)資源。Zhao等[6]對數(shù)據(jù)傳輸?shù)牧髁坑嬎惴椒ㄟM(jìn)行了數(shù)學(xué)建模，提出當(dāng)任務(wù)需要的數(shù)據(jù)分布在不同的節(jié)點時，根據(jù)存儲在各節(jié)點數(shù)據(jù)大小，通過數(shù)學(xué)計算得出一種將所有數(shù)據(jù)移動到同一節(jié)點且使用網(wǎng)絡(luò)流量最少的移動方案。然而這一算法只考慮了無數(shù)據(jù)副本的系統(tǒng)，并沒有考慮數(shù)據(jù)多副本的情況，而多數(shù)分布式存儲都需要通過數(shù)據(jù)副本來增強(qiáng)容錯性，因此此算法并不能廣泛適用。對于這個問題，Yu等[7]研究數(shù)據(jù)需求基本相同的同類任務(wù)，預(yù)測出此類任務(wù)的固定需求，記為一個需求模式。在運行前，使用超圖劃分算法將此模式所需的數(shù)據(jù)移動至負(fù)載較小的節(jié)點，當(dāng)有數(shù)據(jù)副本時，選擇數(shù)據(jù)選擇副本中路徑最短的一個，減少跨節(jié)點的數(shù)據(jù)調(diào)用。比起文獻(xiàn)[6]算法，此算法研究了無數(shù)據(jù)副本和有數(shù)據(jù)副本兩種情況，擴(kuò)展了算法的適用范圍。Jalaparti等[8]指出大數(shù)據(jù)作業(yè)有許多是重復(fù)的，有相同的資源需求，因此可以提前預(yù)測此類任務(wù)的資源需求，確定所需集群機(jī)架的數(shù)量。在預(yù)測的作業(yè)到達(dá)時間先后順序下，按照所需機(jī)架數(shù)量降序排列分配負(fù)載最輕的機(jī)架，這樣便同時增強(qiáng)了數(shù)據(jù)存儲和任務(wù)調(diào)度的本地化程度。這種增強(qiáng)數(shù)據(jù)本地化的算法對于規(guī)模分布較集中的計算集群比較適用，而對于一些大規(guī)模、分布廣泛的計算集群來說，數(shù)據(jù)過于本地化的放置可能意味著若本地數(shù)據(jù)不能使用時，調(diào)用數(shù)據(jù)副本可能是跨越全球的數(shù)據(jù)傳輸，反而加重了網(wǎng)絡(luò)負(fù)載。Chen等[9]考慮了分布全球的大型計算集群的數(shù)據(jù)存儲，設(shè)計了一個固定層數(shù)的樹形拓?fù)浣Y(jié)構(gòu)來描述集群的結(jié)構(gòu)，上層非葉子節(jié)點代表互聯(lián)網(wǎng)、路由器、交換機(jī)、集群機(jī)架、計算機(jī)等硬件，葉子節(jié)點代表存儲的數(shù)據(jù)。文獻(xiàn)[9]中提出了一種被稱為副本平衡樹（Replica Bananced Tree， RBT）的樹形結(jié)構(gòu)，這種樹形結(jié)構(gòu)可將數(shù)據(jù)副本均勻放置在遍布全球的集群中；又提出了副本相關(guān)性樹（Replica Similarity Tree， RST），通過數(shù)據(jù)相關(guān)系數(shù)（Data Dependency Value， DDV）公式計算，將所有數(shù)據(jù)劃分為相關(guān)性最小的兩個子節(jié)點，子節(jié)點繼續(xù)計算和劃分，直至計算至葉子節(jié)點。這種存儲方法同時減少了全球范圍內(nèi)相同數(shù)據(jù)被調(diào)用時的網(wǎng)絡(luò)傳輸和相關(guān)性較強(qiáng)的不同數(shù)據(jù)同時被調(diào)用的網(wǎng)絡(luò)傳輸。

2.1.2通過修改大數(shù)據(jù)處理模型的網(wǎng)絡(luò)優(yōu)化

由于大數(shù)據(jù)的發(fā)展時間不長，現(xiàn)有的大數(shù)據(jù)處理模型如MapReduce仍然在不斷發(fā)展中，通過對大數(shù)據(jù)處理模型的優(yōu)化可以提升模型的處理能力，無需分析數(shù)據(jù)的特點進(jìn)行特殊的優(yōu)化，適用性較廣。Wang等[10]研究了MapReduce 框架中Shuffle階段先排序還是先歸并的問題，得出了【兩種不同處理順序的數(shù)據(jù)傳輸量計算方法，根據(jù)任務(wù)Map階段的具體結(jié)果特征選擇數(shù)據(jù)傳輸量較低的Shuffle方式，提升了運行效率。Wang等[10]研究了MapReduce 框架中Shuffle階段“先排序還是先歸并？”的不同處理順序下的數(shù)據(jù)傳輸量，然后選擇數(shù)據(jù)傳輸量較小的一種順序作為Shuffle階段的處理順序。這種根據(jù)任務(wù)Map階段的具體結(jié)果特征來選擇數(shù)據(jù)傳輸量較低的Shuffle方式，提升了運行效率。此算法雖然在一定程度上減少了數(shù)據(jù)的傳輸，但是依然無法改變Shuffle階段需要同時將中間數(shù)據(jù)傳輸至Reduce任務(wù)，這一并行操作仍會帶來巨大的網(wǎng)絡(luò)負(fù)載。對于此問題，Yu等[11]借鑒了操作系統(tǒng)的虛擬內(nèi)存段頁式管理原理，提出了一個三級段表，將Shuffle過程以段表形式存儲而不進(jìn)行實際的數(shù)據(jù)傳輸，當(dāng)Reduce程序需要數(shù)據(jù)時再通過段表查詢和傳輸所需數(shù)據(jù)，將數(shù)據(jù)的傳輸分散開，降低了Shuffle過程的網(wǎng)絡(luò)負(fù)載。

2.2保持負(fù)載均衡的優(yōu)化

負(fù)載均衡即將收到的處理任務(wù)請求分?jǐn)偟蕉鄠€處理節(jié)點執(zhí)行，根據(jù)處理節(jié)點的目前的性能為之分配合適的任務(wù)，以達(dá)到最小化任務(wù)的完成時間[12]，最后將處理結(jié)果返回至用戶。但是大數(shù)據(jù)集群中存在一些不均衡因素，如不平衡的計算、不平衡的數(shù)據(jù)分配、不平衡的硬件等，這些因素可能會導(dǎo)致某些處理節(jié)點工作負(fù)荷重，而另一些節(jié)點空閑，造成效率下降和資源浪費。

Hadoop平臺內(nèi)置了一個名為Balancer的存儲負(fù)載均衡程序[13]，其主要原理是統(tǒng)計所有數(shù)據(jù)節(jié)點的空間利用率并求出節(jié)點的平均利用率。數(shù)據(jù)節(jié)點對比自身的利用率與平均利用率，先在機(jī)架內(nèi)進(jìn)行平衡，再在機(jī)架間進(jìn)行平衡。平衡時將負(fù)載較多的節(jié)點中的數(shù)據(jù)轉(zhuǎn)移至負(fù)載較少的節(jié)點，從而達(dá)到空間利用率上的平衡。然而這樣的負(fù)載平衡僅僅從儲存空間利用率這單一方面考慮，并沒有考慮其他因素，不當(dāng)?shù)氖褂梅炊赡軙又刎?fù)載不均衡的程度。

2.2.1均衡復(fù)雜度不同的計算

計算的不均衡即分配至各個處理節(jié)點的任務(wù)計算復(fù)雜度不相同，因此可能造成許多節(jié)點等待一個計算較復(fù)雜的節(jié)點，造成資源的浪費。Xie等[14]對任務(wù)的調(diào)度進(jìn)行了改進(jìn)，在每一個處理節(jié)點上構(gòu)造了一個任務(wù)隊列，任務(wù)會被分配在存有所需數(shù)據(jù)副本的節(jié)點之中隊列最短的一個，減少節(jié)點負(fù)載不均的情況。對于MapReduce 模型下，Map和Shuffle階段持續(xù)時間長而Reduce階段卻很短這種計算不平衡情況，Le等[15]設(shè)計先執(zhí)行部分作業(yè)樣本，根據(jù)樣本Map階段后的結(jié)果中key的頻率來預(yù)測此key整體頻率，根據(jù)頻率高低分配負(fù)載不同的選擇處理節(jié)點進(jìn)行Shuffle，加快Shuffle階段的處理速度。

2.2.2均衡數(shù)據(jù)的分配

MapReduce模型中，數(shù)據(jù)被Map端處理后產(chǎn)生的中間數(shù)據(jù)要被分配至Reduce端，Hadoop平臺默認(rèn)的數(shù)據(jù)分配函數(shù)partitioner是靜態(tài)哈希算法，即將Map端結(jié)果〈key，value〉與Reduce階段處理程序Reducer的數(shù)目作為變量輸入partitioner函數(shù)，將key的哈希值用Reducer數(shù)目取模，得出該數(shù)據(jù)被分配的Reducer，這樣可以保證相同的key值分配在相同的reduce程序。然而當(dāng)某些數(shù)據(jù)重復(fù)出現(xiàn)頻率比其他多時，會使過多被數(shù)據(jù)分配至相同Reducer，造成數(shù)據(jù)失衡，Chen等[16]提出Map階段結(jié)束后，根據(jù)中間數(shù)據(jù)的key值的重復(fù)比例將比例較大的key增加一個次級key，并以隨機(jī)數(shù)賦值，根據(jù)次級key再進(jìn)行數(shù)據(jù)分配，如此可將過于集中的相同數(shù)據(jù)分至其他Reduce程序處理，避免數(shù)據(jù)分配失衡。

MapReduce模型中，一個作業(yè)向集群申請計算資源，這樣的資源稱為slot。slot可分為Map slot和Reduce slot，可供一個Map或Reduce任務(wù)使用，通常一個大數(shù)據(jù)作業(yè)申請用于Map或Reduce的slot是固定的。當(dāng)Map任務(wù)或Reduce任務(wù)的運行順序不當(dāng)時，可能造成Reduce任務(wù)等待Map任務(wù)的結(jié)果而用于Reduce的slot空閑，從而造成計算資源浪費。針對這一情況，Tang等[17]改進(jìn)了約翰遜法則[18]來求得最短運行時間的任務(wù)順序，又進(jìn)一步循環(huán)測試得出一個作業(yè)用于Map和Reduce的slot的最佳分配比例。然而這里尋找最佳slot的分配比例使用的是枚舉法，尋找效率較低。針對此問題，Yao等[19]對一個作業(yè)申請的Map和Reduce slot資源需求和運行時間進(jìn)行數(shù)學(xué)建模，以Map和Reduce程序同時結(jié)束為目標(biāo)，使用動態(tài)規(guī)劃思想計算出最佳的slot分配方案。

與上述觀點相反，Grandl等[20]提出了資源平等分配有時并不是最優(yōu)的分配算法。由于資源的平等分配，某些大數(shù)據(jù)作業(yè)分配到的計算資源不足以一次完成所有任務(wù)，仍需要第二次甚至更多次資源分配，這樣不僅影響作業(yè)的完成時間，再次進(jìn)行資源分配和處理時，之前已完成的部分仍在占用存儲資源等待后續(xù)數(shù)據(jù)。文獻(xiàn)[20]中根據(jù)大數(shù)據(jù)作業(yè)的資源需求，構(gòu)造并解決了一個裝箱問題，進(jìn)行合理的資源分配，減少資源的再分配次數(shù)，縮短任務(wù)處理時間。

2.2.3均衡因硬件不同造成的性能差異

由于如今的大數(shù)據(jù)處理框架如Hadoop可以部署在廉價機(jī)器上，且代碼是開源的，對硬件有很好的適應(yīng)性，當(dāng)集群中處理機(jī)的硬件性能有差異時，便形成了異構(gòu)系統(tǒng)。這種異構(gòu)系統(tǒng)節(jié)點之間的處理能力不同，但分配的數(shù)據(jù)量是相同的，這是分布式文件系統(tǒng)的默認(rèn)策略。處理能力強(qiáng)節(jié)點很快就完成本地數(shù)據(jù)處理，閑置下來。之后，調(diào)度器為它們分配遠(yuǎn)程的任務(wù)，這些任務(wù)會經(jīng)過網(wǎng)絡(luò)的傳輸，這不可避免地增加耗時。魏文娟等[21]制定了一個標(biāo)準(zhǔn)化測試，得出各個異構(gòu)節(jié)點的處理速率，求出節(jié)點間的相對處理速率，根據(jù)相對速率按比例分配數(shù)據(jù)分塊數(shù)進(jìn)行存儲和運行。這里的相對速率是通過標(biāo)準(zhǔn)化測試得到的固定值，而在實際運行時，由于任務(wù)的計算復(fù)雜度以及負(fù)載狀況不同，此時計算出的固定速率與實際速率可能會有較大誤差，并不能代表節(jié)點真實的處理速率。Wang等[22]以單位時間內(nèi)處理數(shù)據(jù)塊的量為評價標(biāo)準(zhǔn)，使用馬爾可夫鏈來實時預(yù)測節(jié)點的處理性能，動態(tài)選擇合適的存儲節(jié)點。

2.3降低集群能耗的優(yōu)化

2010年美國的數(shù)據(jù)中心的用電量已占美國總用電量的2%，并且以15%的速度逐年上升[23]。能源的開銷已占數(shù)據(jù)中心日常運行開銷的42%[24]，已經(jīng)成為網(wǎng)絡(luò)公司和數(shù)據(jù)中心運營的重要經(jīng)濟(jì)支出。因此無論從經(jīng)濟(jì)方面還是環(huán)保方面來說，降低集群的能源開銷已經(jīng)成為大數(shù)據(jù)服務(wù)供應(yīng)商著重考慮的問題。

2.3.1休眠數(shù)據(jù)節(jié)點

廖彬等[25]將集群機(jī)架內(nèi)部劃分為活躍區(qū)和休眠區(qū)，并對休眠區(qū)節(jié)點進(jìn)行休眠處理。定義閾值SleepCount和ActiveCount：一個文件在時間周期內(nèi)訪問次數(shù)小于閾值SleepCount，算法則會減小該文件的活動數(shù)據(jù)塊的數(shù)量；相反如果訪問次數(shù)大于閾值A(chǔ)ctiveCount，則增加活動數(shù)據(jù)塊的數(shù)量。算法在達(dá)到節(jié)能目的的同時保證了數(shù)據(jù)塊的可用性。DeryaCavdar等[26]提出檢測集群資源（如CPU、內(nèi)存、網(wǎng)絡(luò)等）在空閑時和運行時的功率，通過休眠時和運行時的功率，使用動態(tài)規(guī)劃思想來找到一條使用能耗最低的數(shù)據(jù)傳輸路徑，減少不必要的能源消耗。以上算法都僅從休眠節(jié)點或減少數(shù)據(jù)傳輸路徑長度，這些單一角度來節(jié)約能耗，雖有一定成效，但無法確定整體節(jié)能效果是否最優(yōu)。文獻(xiàn)[27-28]對大數(shù)據(jù)處理模型的各個階段進(jìn)行細(xì)致的分析，建立完整詳細(xì)的能耗計算模型。利用能耗模型，GuZeng等[27]詳細(xì)定義了數(shù)據(jù)中心服務(wù)器數(shù)量、數(shù)據(jù)在本地傳輸開銷、數(shù)據(jù)在網(wǎng)絡(luò)中傳輸開銷、激活一個服務(wù)器能源開銷、數(shù)據(jù)的備份數(shù)量、任務(wù)到達(dá)率、最大響應(yīng)時間等多種變量，得出一個能耗計算公式，將能耗的最小化問題轉(zhuǎn)換成求解一個混合整數(shù)非線性規(guī)劃問題（MINLP），全面地考慮了集群中可以影響能耗的各個因素。

2.3.2延緩非緊急任務(wù)

大數(shù)據(jù)任務(wù)中，存在一些非緊急的任務(wù)，這些任務(wù)雖然不要求完成時間最小，但是規(guī)定了最晚開始時間。延緩這些非緊急任務(wù)的執(zhí)行，可減輕集群的計算負(fù)載，達(dá)到減少能耗的目的。Mashayekhy等[29]為Map端和Reduce端接受的任務(wù)建立了兩個執(zhí)行隊列，通過任務(wù)的最晚開始時間和資源需求，以及目前集群個處理節(jié)點的負(fù)載情況，將Map任務(wù)和Reduce任務(wù)綜合排序分別建立隊列，放置在最佳的處理節(jié)點運行。Chen等[30]以租用公共云計算集群（如Amazon的AWS）中如何節(jié)省成本的問題為例進(jìn)行，進(jìn)一步對這種非緊急任務(wù)的能耗計算進(jìn)行研究，分析了Map和Reduce階段的開銷并建立數(shù)學(xué)模型，對有成本有限制的作業(yè)和處理時間有限制的作業(yè)兩種類型分別構(gòu)造線性規(guī)劃，根據(jù)具體作業(yè)類型求得最佳的Map和Reduce的slot分配數(shù)量。

2.3.3節(jié)能與性能的平衡

除了不必要的能源浪費之外，集群的計算性能和能耗節(jié)約其實是相互矛盾的兩個方面，要求節(jié)能則可能意味著對集群處理能力的妥協(xié)。林彬等[31]將利用率較低、甚至空轉(zhuǎn)的節(jié)點進(jìn)行關(guān)閉；而對于數(shù)據(jù)完整性和性能影響問題，文中令集群機(jī)架內(nèi)數(shù)據(jù)副本順序存放，機(jī)架間數(shù)據(jù)副本隨機(jī)存放，減少因關(guān)閉節(jié)點造成數(shù)據(jù)完整性被破壞的概率；同時還引入了關(guān)閉節(jié)點對集群的影響衡量指標(biāo)，即關(guān)閉節(jié)點后能耗降低值與響應(yīng)時間增加值的比值，比值越大表示節(jié)能越有效，關(guān)閉節(jié)點時選擇比值大的節(jié)點，直到數(shù)據(jù)完整性被破壞。這種考慮性能

與節(jié)能的想法比較簡單，但對數(shù)據(jù)的完整性和容錯性等方面損傷較大。MinYoon等[28]研究了性能和節(jié)能兩個問題的矛盾關(guān)系，對計算性能和能源消耗建立了數(shù)學(xué)模型，從性能和節(jié)能兩個角度分別構(gòu)造了兩個線性規(guī)劃，通過找到兩個線性規(guī)劃的帕累托最優(yōu)點，使得性能和節(jié)能兩方面達(dá)到一個平衡點。

2.4其他因素的數(shù)據(jù)存儲優(yōu)化

另有其他因素諸如集群可靠性、容錯性、大數(shù)據(jù)處理框架的處理效率等都可作為提升大數(shù)據(jù)處理能力優(yōu)化的研究方向。

當(dāng)集群中的處理節(jié)點有突發(fā)故障，集群的部分甚至全部處理能力會下降或完全癱瘓，如何避免和處理故障是保證集群可用性的關(guān)鍵。Hadoop雖然提供了“推測執(zhí)行策略”，即在作業(yè)運行過程中，不對運行慢的任務(wù)進(jìn)行修復(fù)，而是啟動一個相同任務(wù)來替代。這種簡單的故障處理方式雖然簡單，但是要以增加不必要的系統(tǒng)負(fù)載為代價。Xu等[32]提出當(dāng)系統(tǒng)負(fù)載較低時，使用默認(rèn)推測執(zhí)行策略；當(dāng)系統(tǒng)負(fù)載較高時，采用改進(jìn)的微軟Mantri差錯預(yù)測算法[33]，進(jìn)行問題的檢測和任務(wù)轉(zhuǎn)移。Mantri算法假定任務(wù)的處理速度是恒定的，以平均處理速度為判斷節(jié)點是否有問題的標(biāo)準(zhǔn)。然而，在MapReduce中，一個任務(wù)的處理會經(jīng)歷若干個階段，如map、combine、copy、sort和reduce等，不同的處理階段由于任務(wù)難度和運行環(huán)境的不同，處理速度是有區(qū)別的，若使用平均處理速度作為判斷標(biāo)準(zhǔn)，勢必會出現(xiàn)判斷錯誤。Chen等[34]分析了以往故障預(yù)測算法的不足，并且提出分階段計算任務(wù)處理速度的指數(shù)加權(quán)移動平均數(shù)（Exponentially Weighted Moving Average， EWMA）作為判斷標(biāo)準(zhǔn)，并對比任務(wù)在原節(jié)點、轉(zhuǎn)移至同一機(jī)架不同節(jié)點和轉(zhuǎn)移至不同機(jī)架三種處理方式預(yù)計的完成時間，選取最優(yōu)的轉(zhuǎn)移策略。

網(wǎng)絡(luò)可靠性也是影響集群效果的一大因素，以往的網(wǎng)絡(luò)狀態(tài)檢測是進(jìn)行抽樣檢測，因此一些不良的通信會刻意回避檢測，F(xiàn)ontugne等[35]將網(wǎng)絡(luò)狀態(tài)的異常檢測轉(zhuǎn)化為一個普通大數(shù)據(jù)作業(yè)始終運行，對網(wǎng)絡(luò)進(jìn)行實時檢測。對通信數(shù)據(jù)的源IP地址和目的IP地址進(jìn)行哈希運算來選擇通信路徑，為網(wǎng)絡(luò)流量分流。宋寶燕等[36]使用范德蒙糾刪碼來檢測和糾正出錯的數(shù)據(jù)，增強(qiáng)了數(shù)據(jù)的容錯性，同時減少了數(shù)據(jù)副本的數(shù)量，降低了存儲空間的冗余。

2.5數(shù)據(jù)存儲策略優(yōu)化的分析與總結(jié)

由于MapReduce模型在大數(shù)據(jù)處理領(lǐng)域被廣泛使用，占據(jù)主流地位，本文通過對近幾年來大數(shù)據(jù)集群數(shù)據(jù)存儲策略的研究，基于MapReduce處理模型對存儲策略的優(yōu)化算法及特點進(jìn)行總結(jié)。如表1所示，目前數(shù)據(jù)存儲策略的研究主要集中在減少網(wǎng)絡(luò)負(fù)載、保證負(fù)載平衡和節(jié)約開銷三個目標(biāo)。而且在實際應(yīng)用中，使用者可能不只有單一的優(yōu)化目標(biāo)，而是有多目標(biāo)共同優(yōu)化的需求，然而這些優(yōu)化之間可能是相互矛盾的。例如，為了節(jié)約能源而休眠或關(guān)閉部分節(jié)點時，會使大部分任務(wù)都集中分配在活躍的節(jié)點，造成負(fù)載的不平衡；而為了負(fù)載平衡，需要進(jìn)行數(shù)據(jù)副本的遷移時，又會造成大量的網(wǎng)絡(luò)開銷。由此可見，目前大部分?jǐn)?shù)據(jù)存儲算法的優(yōu)化目標(biāo)單一。如果使用者要根據(jù)自身的具體需求進(jìn)行多目標(biāo)優(yōu)化，必須設(shè)計一種各方面都較為平衡的綜合存儲策略。

3總結(jié)與展望

本文對大數(shù)據(jù)處理系統(tǒng)的主流文件存儲結(jié)構(gòu)進(jìn)行了簡介，并總結(jié)了近幾年來國內(nèi)外學(xué)者們對存儲策略的優(yōu)化所作的貢獻(xiàn)。從當(dāng)前的研究結(jié)果來看，通過調(diào)整數(shù)據(jù)的存儲策略從而提升系統(tǒng)性能的做法仍有很大的發(fā)展空間。在大數(shù)據(jù)處理需求急劇膨脹的時代下，大數(shù)據(jù)處理系統(tǒng)仍有很長的路要

走。

根據(jù)集群存儲的特點和要求，未來數(shù)據(jù)存儲算法的研究可以有以下幾種趨勢：

1）通過本文的總結(jié)歸納，不難發(fā)現(xiàn)，目前學(xué)者們對數(shù)據(jù)存儲算法的研究大多數(shù)都著重于調(diào)整數(shù)據(jù)以配合已有的存儲系統(tǒng)，并沒有多少對存儲系統(tǒng)本身的設(shè)計進(jìn)行的優(yōu)化。這種優(yōu)化方向有很大的局限性，它只適用于特定的作業(yè)需求，而且可能會與其他優(yōu)化方向產(chǎn)生矛盾。若對現(xiàn)有的存儲系統(tǒng)進(jìn)行優(yōu)化，整體提升存儲系統(tǒng)的性能，當(dāng)優(yōu)化足夠好時則可無需針對數(shù)據(jù)特性設(shè)計不同的數(shù)據(jù)存儲算法。對存儲系統(tǒng)的優(yōu)化可以作為未來研究的重點方向。

2）本地化、負(fù)載均衡和節(jié)能這幾個目標(biāo)是優(yōu)化算法常見的研究方向，實際應(yīng)用中同時要求多目標(biāo)同時優(yōu)化的要求也很常見。然而目前的優(yōu)化算法優(yōu)化目標(biāo)單一，少有可以滿足多目標(biāo)同時優(yōu)化。鑒于性能與節(jié)能、節(jié)能與負(fù)載均衡、負(fù)載均衡與數(shù)據(jù)本地化等多個優(yōu)化方向之間的矛盾關(guān)系逐漸凸顯，探索出可滿足多目標(biāo)同時優(yōu)化的需求得到平衡和優(yōu)化的方法是一個非常迫切需要解決的問題。

3）目前的大數(shù)據(jù)處理框架多用于進(jìn)行海量數(shù)據(jù)批量地分析與處理，適用于先存儲后計算，針對的是高吞吐量的作業(yè)，存儲的優(yōu)化算法也大多針對批處理或可預(yù)測特性的數(shù)據(jù)的存儲。而在未來，需要將實時接受的大數(shù)據(jù)處理請求在秒級內(nèi)完成處理的情況將成為常態(tài)，這將成為未來大數(shù)據(jù)處理的發(fā)展趨勢，然而這方面的存儲優(yōu)化算法尚未有過多的研究，需要增強(qiáng)對此的關(guān)注和研究。

4結(jié)語

隨著信息化時代的迅速發(fā)展，信息的數(shù)據(jù)規(guī)模和復(fù)雜度的快速增長對現(xiàn)有的數(shù)據(jù)處理能力提出了挑戰(zhàn)。合理的數(shù)據(jù)存儲算法是影響大數(shù)據(jù)處理框架的一個關(guān)鍵因素。本文首先對主流的大數(shù)據(jù)集群存儲架構(gòu)和算法進(jìn)行了總結(jié)，然后對數(shù)據(jù)存儲的優(yōu)化算法進(jìn)行了歸納和分析，最后對數(shù)據(jù)存儲算法研究的挑戰(zhàn)和發(fā)展進(jìn)行了展望。從文中可以看出，目前數(shù)據(jù)放存儲算法在針對單一目標(biāo)的優(yōu)化上已有很好的效果，但對于提升大數(shù)據(jù)處理系統(tǒng)整體性能方面的研究，仍有較大的探索空間。不過大數(shù)據(jù)還是一個正在發(fā)展的研究方向，未來大數(shù)據(jù)處理系統(tǒng)的性能得到大幅度提升是必然的。

參考文獻(xiàn)：

[1]

程學(xué)旗，靳小龍，王元卓，等.大數(shù)據(jù)系統(tǒng)和分析技術(shù)綜述[J].軟件學(xué)報，2014，25（9）：1889-1908.（CHENG X Q， JIN X L， WANG Y Z， et al. Survey on big data system and analytic technology [J]. Journal of Software， 2014，25（9）：1889-1908.）

[2]

王元卓，靳小龍，程學(xué)旗.網(wǎng)絡(luò)大數(shù)據(jù)：現(xiàn)狀與展望[J].計算機(jī)學(xué)報，2013，36（6）：1125-1138.（WANG Y Z，JIN X L，CHENG X Q. Network big data： present and future[J]. Chinese Journal of Computers， 2013， 36（6）： 1125-1138.

[3]

孟小峰，慈祥.大數(shù)據(jù)管理：概念、技術(shù)與挑戰(zhàn)[J].計算機(jī)研究與發(fā)展，2013，50（1）：146-169.（MENG X F， CI X. Big data management： concepts， techniques and challenges [J]. Journal of Computer Research and Development， 2013， 50（1）： 146-169.）

[4]

張濱，陳吉榮，樂嘉錦.大數(shù)據(jù)管理技術(shù)研究綜述[J].計算機(jī)應(yīng)用與軟件，2014，31（11）：1-5.（ZHANG B， CHEN J R， LE J J. Overview on big data management technology research [J]. Computer Applications and Software， 2014， 31（11）： 1-5.）

[5]

ZICARI R V. Big data： challenges and opportunities [J]. Big Data Computing， 2014： 103-128.

ZICARI R V. Big data： challenges and opportunities [EB/OL]. [20160108]. http：//gotocon.com/dl/gotoaar2012/slides/RobertoV.Zicari_BigDataChallengesAndOpportunities.pdf.

[6]

ZHAO Q， XIONG C， ZHAO X， et al. A data placement strategy for dataintensive scientific workflows in cloud [C]// Proceedings of the 2015 15th IEEE/ACM International Symposium on Cluster， Cloud and Grid Computing. Washington， DC： IEEE Computer Society， 2015： 928-934.

[7]

YU B， PAN J. Locationaware associated data placement for geodistributed dataintensive applications [C]// Proceedings of the 2015 IEEE Conference on Computer Communications. Piscataway， NJ： IEEE， 2015：603-611.

[8]

JALAPARTI V， BODIK P， MENACHE I， et al. Networkaware scheduling for dataparallel jobs： plan when you can [C]// SIGCOMM 15： Proceedings of the 2015 ACM Conference on Special Interest Group on Data Communication. New York： ACM， 2015： 407-420.

[9]

CHEN W， PAIK I， LI Z. Topologyaware optimal data placement algorithm for network traffic optimization [J]. IEEE Transactions on Computers， 2016，65（8）：2603-2617.

[10]

WANG J， QIU M， GUO B， et al. Phasereconfigurable shuffle optimization for Hadoop MapReduce [J]. IEEE Transactions on Cloud Computing， 2015（99）：1.

[11]

YU W， WANG Y， QUE X， et al. Virtual shuffling for efficient data movement in MapReduce [J]. IEEE Transactions on Computers， 2015， 64（2）：556-568.

[12]

BUYYA R. High Performance Cluster Computing： Architectures and Systems [M]. Upper Saddle River， NJ： Prentice Hall， 1999， 1： 823.

[13]

劉琨，肖琳，趙海燕.Hadoop中云數(shù)據(jù)負(fù)載均衡算法的研究及優(yōu)化[J].微電子學(xué)與計算機(jī)，2012，29（9）：18-22.（LIU K， XIAO L， ZHAO H Y. Research and optimize of cloud data load balancing in hadoop [J]. Microelectronics & Computer， 2013， 29（9）： 18-22.

[14]

XIE Q， LU Y. Priority algorithm for neardata scheduling： throughput and heavytraffic optimality [C]// Proceedings of the 2015 IEEE Conference on Computer Communications. Piscataway， NJ： IEEE， 2015： 963-972.

[15]

LE Y， LIU J， ERGUN F， et al. Online load balancing for MapReduce with skewed data input [C]// Proceedings of the 2014 IEEE Conference on Computer Communications. Piscataway， NJ： IEEE， 2014： 2004-2012.

[16]

CHEN Q， YAO J， XIAO Z. LIBRA： lightweight data skew mitigation in MapReduce [J]. IEEE Transactions on Parallel & Distributed Systems， 2015， 26（9）： 2520-2533.

[17]

TANG S， LEE B S， HE B. Dynamic job ordering and slot configurations for MapReduce workloads [J]. IEEE Transactions on Services Computing， 2016， 9（1）： 4-17.

[18]

JOHNSON S M. Optimal two and threestage production schedules with setup times included [J]. Naval Research Logistics Quarterly， 1954， 1（1）：61-68.

[19]

YAO Y， WANG J， SHENG B， et al. Selfadjusting slot configurations for homogeneous and heterogeneous Hadoop clusters [J]. IEEE Transactions on Cloud Computing， 2015（1）：1.

YAO Y， WANG J， SHENG B， et al. Selfadjusting slot configurations for homogeneous and heterogeneous Hadoop clusters [EB/OL]. [20160109]. http：//www.cs.umb.edu/～shengbo/paper/tcc15.pdf.

[20]

GRANDL R， ANANTHANARAYANAN G， KANDULA S， et al. Multiresource packing for cluster schedulers [C]// SIGCOMM 14： Proceedings of the 2014 ACM Conference on SIGCOMM. New York： ACM， 2014：455-466.

[21]

魏文娟，王黎明.異構(gòu)Hadoop集群下的比例數(shù)據(jù)分配策略[J].計算機(jī)應(yīng)用與軟件，2015，32（6）：316-319.（WEI W J， WANG L M. Proportional data placement strategy in heterogeneous hadoop clusters [J]. Computer Applications and Software， 2015， 32（6）： 316-319.）

[22]

WANG B， JIANG J， YANG G. ActCap： accelerating MapReduce on heterogeneous clusters with capabilityaware data placement [C]// Proceedings of the 2015 IEEE Conference on Computer Communications. Piscataway， NJ： IEEE， 2015： 1328-1336.

[23]

KOOMEY J. Growth in data center electricity use 2005 to 2010 [J]. A report by Analytical Press， completed at the request of The New York Times， 2011： 9.

KOOMEY J. Growth in data center electricity use 2005 to 2010 [EB/OL]. [20151104]. http：//cs.bennington.edu/courses/f2013/cs4125.01/koomeydatacenterelectuse2011finalversion.pdf.

[24]

HAMILTON J. Cooperative Expendable Microslice Servers （CEMS）： low cost， low power servers for Internetscale services[C]// Conference on Innovative Data Systems Research. 2009.

HAMILTON J. Cooperative Expendable Microslice Servers （CEMS）： low cost， low power servers for Internetscale services [EB/OL]. [20151104]. http：//database.cs.wisc.edu/cidr/cidr2009/JamesHamilton_CEMS.pdf.

[25]

廖彬，于炯，張?zhí)眨?基于分布式文件系統(tǒng)HDFS的節(jié)能算法[J].計算機(jī)學(xué)報，2013，36（5）：1047-1064.（LIAO B， YU J， ZHANG T， et al. Energyefficient algorithms for distributed file system HDFS [J].Chinese Journal of Computers， 2013， 36（5）： 1047-1064.

[26]

CAVDAR D， CHEN L Y， ALAGOZ F. Green MapReduce for heterogeneous data centers [C]// Proceedings of the 2014 IEEE Global Communications Conference. Piscataway， NJ： IEEE， 2014： 1120-1126.

[27]

ZENG D， GU L， GUO S. Cost minimization for big data processing in geodistributed data centers [M]// Cloud Networking for Big Data. Berlin： Springer， 2015：314-323.

ZENG D， GU L， GUO S. Cost minimization for big data processing in geodistributed data centers [J]. IEEE Transactions on Emerging Topics in Computing， 2014， 2（3）： 314-323.

[28]

YOON M S， KAMAL A E. Optimal dataset allocation in distributed heterogeneous clouds [C]// Proceedings of the 2014 IEEE Globecom Workshops. Piscataway， NJ： IEEE， 2014： 75-80.

[29]

MASHAYEKHY L， NEJAD M M， GROSU D， et al. Energyaware scheduling of MapReduce jobs [C]// Proceedings of the 2014 IEEE International Congress on Big Data. Washington， DC： IEEE Computer Society， 2014：32-39.

[30]

CHEN K， POWERS J， GUO S， et al. CRESP： towards optimal resource provisioning for MapReduce computing in public clouds [J]. IEEE Transactions on Parallel & Distributed Systems， 2014， 25（6）：1403-1412.

[31]

林彬，李姍姍，廖湘科，等.Seadown：一種異構(gòu)MapReduce集群中面向SLA的能耗管理方法[J].計算機(jī)學(xué)報，2013，36（5）：977-987.（LIN B， LI S S， LIAO X K， et al. Seadown： SLAaware sizescaling power management in heterogeneous MapReduce cluster [J]. Chinese Journal of Computers， 2013， 36（5）： 977-987.

[32]

XU H， LAU W C. Optimization for speculative execution in a MapReducelike cluster[C]// Proceedings of the 2015 IEEE Conference on Computer Communications. Piscataway， NJ： IEEE， 2015： 1071-1079.

[33]

ANANTHANARAYANAN G， KANDULA S， GREENBERG A， et al. Reining in the outliers in MapReduce clusters using Mantri [C]// OSDI 10： Proceedings of the 9th USENIX Conference on Operating Systems Design and Implementation. Berkeley， CA： USENIX Association， 2010：265-278.

[34]

CHEN Q， LIU C， XIAO Z. Improving MapReduce performance using smart speculative execution strategy [J]. IEEE Transactions on Computers， 2014， 63（4）： 954-967.

[35]

FONTUGNE R， MAZEL J， FUKUDA K. Hashdoop： a MapReduce framework for network anomaly detection [C]// Proceedings of the 2014 IEEE Conference on Computer Communications Workshops. Piscataway， NJ： IEEE， 2014： 494-499.

[36]

宋寶燕，王俊陸，王妍.基于范德蒙碼的HDFS優(yōu)化存儲策略研究[J].計算機(jī)學(xué)報，2015，38（9）：1825-1837.（SONG B Y， WANG J L， WANG Y. Optimized storage strategy research of HDFS based on Vandermonde code [J]. Chinese Journal of Computers， 2015， 38（9）： 1825-1837.