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

楊俊杰　廖卓凡　馮超超

摘要：

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

關(guān)鍵詞：

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

中圖分類號(hào)：

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)入了一個(gè)信息爆炸型的時(shí)代，大數(shù)據(jù)處理的需求正在迅速增加，在科學(xué)、工業(yè)、商業(yè)等領(lǐng)域，信息處理量達(dá)到TB級(jí)甚至PB級(jí)已是正?，F(xiàn)象。因此，尋求優(yōu)秀的大數(shù)據(jù)處理模型對(duì)于處理數(shù)據(jù)密集型應(yīng)用是非常重要的。

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

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

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

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

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

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

1.1.1直連式存儲(chǔ)

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

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

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

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

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

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

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

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

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

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

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

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

1.3.1主控節(jié)點(diǎn)

主控節(jié)點(diǎn)主要負(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é)點(diǎn)需要存儲(chǔ)一些元數(shù)據(jù)（metadata），如文件的所有者和權(quán)限、文件到數(shù)據(jù)節(jié)點(diǎn)的映射關(guān)系等。除了管理命名空間，主控節(jié)點(diǎn)還要集中管理數(shù)據(jù)節(jié)點(diǎn)。通過對(duì)數(shù)據(jù)節(jié)點(diǎn)輪詢或接收來自數(shù)據(jù)節(jié)點(diǎn)的定期心跳（heartbeat）消息。除了管理命名空間，主控節(jié)點(diǎn)還要對(duì)數(shù)據(jù)節(jié)點(diǎn)輪詢或接收來自數(shù)據(jù)節(jié)點(diǎn)的定期心跳（heartbeat）來集中管理數(shù)據(jù)節(jié)點(diǎn)。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

MapReduce模型中，數(shù)據(jù)被Map端處理后產(chǎn)生的中間數(shù)據(jù)要被分配至Reduce端，Hadoop平臺(tái)默認(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í)，會(huì)使過多被數(shù)據(jù)分配至相同Reducer，造成數(shù)據(jù)失衡，Chen等[16]提出Map階段結(jié)束后，根據(jù)中間數(shù)據(jù)的key值的重復(fù)比例將比例較大的key增加一個(gè)次級(jí)key，并以隨機(jī)數(shù)賦值，根據(jù)次級(jí)key再進(jìn)行數(shù)據(jù)分配，如此可將過于集中的相同數(shù)據(jù)分至其他Reduce程序處理，避免數(shù)據(jù)分配失衡。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3總結(jié)與展望

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

走。

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

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

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

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

4結(jié)語

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

參考文獻(xiàn)：

[1]

程學(xué)旗，靳小龍，王元卓，等.大數(shù)據(jù)系統(tǒng)和分析技術(shù)綜述[J].軟件學(xué)報(bào)，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ì)算機(jī)學(xué)報(bào)，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ì)算機(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ì)算機(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ì)算機(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ì)算機(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ì)算機(jī)學(xué)報(bào)，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]

林彬，李?yuàn)檴?，廖湘科，?Seadown：一種異構(gòu)MapReduce集群中面向SLA的能耗管理方法[J].計(jì)算機(jī)學(xué)報(bào)，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)化存儲(chǔ)策略研究[J].計(jì)算機(jī)學(xué)報(bào)，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.