蔡燕冬，劉　艷，張慶磊（華僑大學(xué)　計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，福建　廈門　361021）

一種優(yōu)化的Hadoop副本放置策略*

蔡燕冬，劉艷，張慶磊
（華僑大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，福建廈門361021）

Hadoop分布式文件系統(tǒng)默認(rèn)采用三副本策略實(shí)現(xiàn)較為簡(jiǎn)單，未對(duì)數(shù)據(jù)節(jié)點(diǎn)負(fù)載進(jìn)行充分考慮。為了改善HDFS中集群負(fù)載的均衡性，提高數(shù)據(jù)節(jié)點(diǎn)的資源利用率，提出一種優(yōu)化的副本放置策略。該策略綜合考慮數(shù)據(jù)節(jié)點(diǎn)的實(shí)時(shí)負(fù)載信息和工作進(jìn)程數(shù)，選擇負(fù)載最小的節(jié)點(diǎn)存放數(shù)據(jù)。實(shí)驗(yàn)結(jié)果表明，與默認(rèn)策略相比，優(yōu)化的Hadoop副本放置策略能使副本分布更加合理，集群的均衡性更加良好，并能減少數(shù)據(jù)上傳響應(yīng)時(shí)間。

Hadoop；副本放置；實(shí)時(shí)負(fù)載；負(fù)載均衡

0　引言

HDFS副本放置策略設(shè)計(jì)是基于節(jié)點(diǎn)硬件性能同構(gòu)的基礎(chǔ)之上，其采用三副本冗余機(jī)制保證數(shù)據(jù)的安全性。整體的副本存儲(chǔ)策略如圖1所示。HDFS整體的副本放置策略的原則為：盡最大可能將其中兩個(gè)數(shù)據(jù)塊副本存儲(chǔ)在一個(gè)機(jī)架上，將另一個(gè)數(shù)據(jù)塊副本存儲(chǔ)在另一個(gè)機(jī)架上，很好地在帶寬資源及可靠性方面做了平衡［1］。然而默認(rèn)副本放置策略具有一定的局限性，已有不少的研究致力于優(yōu)化Hadoop的數(shù)據(jù)塊副本放置策略。參考文獻(xiàn)［2］從數(shù)據(jù)塊熱度的角度出發(fā)，讓經(jīng)常使用的數(shù)據(jù)塊擁有更多的副本以達(dá)到更高的并行處理效率。參考文獻(xiàn)［3］將數(shù)據(jù)塊副本更多地放置在性能較好的節(jié)點(diǎn)上，有效提升mapreduce的性能。參考文獻(xiàn)［4］從節(jié)點(diǎn)的網(wǎng)絡(luò)距離和節(jié)點(diǎn)負(fù)載兩方面進(jìn)行考慮，為HDFS的遠(yuǎn)程數(shù)據(jù)副本選擇最優(yōu)的存儲(chǔ)位置。參考文獻(xiàn)［5］則優(yōu)先讓使用率低的節(jié)點(diǎn)被選中作為存儲(chǔ)節(jié)點(diǎn)。受這些研究工作的啟發(fā)，本文提出一種優(yōu)化的Hadoop副本放置策略旨在提高集群節(jié)點(diǎn)負(fù)載的均衡性，最終達(dá)到提升數(shù)據(jù)傳輸效率的目的。

圖1　默認(rèn)副本放置策略

1　HDFS副本放置優(yōu)化策略

1.1HDFS副本放置策略的局限性

默認(rèn)HDFS副本放置策略的局限性主要體現(xiàn)如下：在選取副本存儲(chǔ)節(jié)點(diǎn)時(shí)采用了隨機(jī)方式，HDFS雖然也考慮了數(shù)據(jù)節(jié)點(diǎn)的工作接連數(shù)的負(fù)載信息，但相對(duì)簡(jiǎn)單，并且是在隨機(jī)選取存儲(chǔ)節(jié)點(diǎn)之后才做出判斷。這樣的副本放置方式將導(dǎo)致副本的分布隨意性大，特別在異構(gòu)環(huán)境中很有可能出現(xiàn)分配較多數(shù)據(jù)副本的節(jié)點(diǎn)是性能較差的節(jié)點(diǎn)，這些情況將進(jìn)一步造成有些節(jié)點(diǎn)具有很高的負(fù)載，有些節(jié)點(diǎn)卻處于空閑狀態(tài)造成數(shù)據(jù)傳輸效率的下降。

1.2優(yōu)化HDFS副本放置策略

從1.1節(jié)的分析可以看出，在默認(rèn)策略中，名字節(jié)點(diǎn)對(duì)于數(shù)據(jù)節(jié)點(diǎn)的狀態(tài)信息缺乏感知，無(wú)法做出更為精確的副本位置選取工作。為此，本文的優(yōu)化策略將重點(diǎn)考慮如下兩個(gè)評(píng)價(jià)指標(biāo)，增加名字節(jié)點(diǎn)副本放置節(jié)點(diǎn)選取的準(zhǔn)確性、合理性。

（1）節(jié)點(diǎn)實(shí)時(shí)負(fù)載：實(shí)時(shí)負(fù)載W由數(shù)據(jù)節(jié)點(diǎn)的多個(gè)指標(biāo)衡量，分別為磁盤IO負(fù)載、內(nèi)存負(fù)載、CPU負(fù)載、網(wǎng)絡(luò)負(fù)載。W的計(jì)算公式為：

W=λio×wio+λmem×wmem+λcpu×wcpu+λband×wband其中，wio、wmem、wcpu、wband分別代表了磁盤IO負(fù)載、內(nèi)存負(fù)載、CPU負(fù)載、網(wǎng)絡(luò)負(fù)載；λio、λmem、λcpu、λband則代表了衡量節(jié)點(diǎn)工作負(fù)載時(shí)的節(jié)點(diǎn)磁盤、內(nèi)存、CPU、網(wǎng)絡(luò)帶寬所占的比重，λio+λmem+λcpu+λband=1，λio、λmem、λcpu、λband∈［0，1］。權(quán)值的選取采用運(yùn)籌學(xué)中的層次分析法（Analytic Hierarchy Process，AHP）來(lái)確定。該方法適用于難以定量分析的決策性問(wèn)題。

（2）HDFS工作進(jìn)程：即數(shù)據(jù)節(jié)點(diǎn)HDFS寫入、讀取等工作的連接數(shù)。由于這些負(fù)載都是比值的關(guān)系，在異構(gòu)環(huán)境下有些節(jié)點(diǎn)可能由于性能較好，其某些實(shí)時(shí)負(fù)載處于較低水平，在節(jié)點(diǎn)性能嚴(yán)重不均衡時(shí)將導(dǎo)致集群大量副本存儲(chǔ)在個(gè)別高性能節(jié)點(diǎn)上。該負(fù)載信息能控制一個(gè)數(shù)據(jù)節(jié)點(diǎn)上進(jìn)行的HDFS工作進(jìn)程，抑制某個(gè)數(shù)據(jù)節(jié)點(diǎn)進(jìn)行過(guò)多的HDFS服務(wù)。

依據(jù)上述兩個(gè)指標(biāo)，某數(shù)據(jù)副本放置位置的選取的主要思想是：從指定的機(jī)架位置上隨機(jī)選取一定數(shù)量的數(shù)據(jù)節(jié)點(diǎn)集，然后從該集合中進(jìn)一步選取工作連接數(shù)低于集群平均工作連接數(shù)的數(shù)據(jù)節(jié)點(diǎn)集合，最后在該集合中選擇實(shí)時(shí)負(fù)載最小的節(jié)點(diǎn)作為副本位置放置節(jié)點(diǎn)。為方便下面的描述，該思想標(biāo)記為算法1。

整體上副本放置位置的選取依然遵循將副本盡量放在不同機(jī)架上以保證可靠性的原則，從最常見(jiàn)的3副本方案出發(fā)，其整體副本選取方案如下：

While還需選取的副本數(shù)＞0

if第一副本選取then

if客戶端節(jié)點(diǎn)是數(shù)據(jù)節(jié)點(diǎn)then

選擇該節(jié)點(diǎn)

else通過(guò)指定所有集群機(jī)架通過(guò)算法1去選取節(jié)點(diǎn)

else if第二副本選取then

指定除去第一副本所在機(jī)架外的所有機(jī)架通過(guò)算法1去選取節(jié)點(diǎn)

else if第三副本選取then

if第一、二副本所在節(jié)點(diǎn)在同一機(jī)架then

指定除去第二副本所在機(jī)架外的所有機(jī)架通過(guò)算法1去選取節(jié)點(diǎn)

else指定第二副本所在機(jī)架通過(guò)算法1去選取節(jié)點(diǎn)

1.3層次分析法的權(quán)值確定工作

美國(guó)運(yùn)籌學(xué)家Saaty教授提出的層次分析法是多屬性決策中的重要方法［6］。對(duì)于存在多個(gè)影響指標(biāo)的情況，評(píng)價(jià)各方案的優(yōu)劣程度的這類問(wèn)題可以使用AHP方法來(lái)解決。AHP方法的思想是把復(fù)雜問(wèn)題中的各種因素進(jìn)行分層，分層是有次序的，層次之間也是有聯(lián)系的，將每個(gè)層次的元素兩兩比較，并定量描述它們的相對(duì)重要性。最后使用數(shù)學(xué)方法計(jì)算權(quán)值，用權(quán)值反映每一層次元素的相對(duì)重要性次序。

本文從實(shí)時(shí)負(fù)載的實(shí)際情況出發(fā)進(jìn)行建模，如圖2所示。

圖2　實(shí)時(shí)負(fù)載模型

對(duì)準(zhǔn)則層的各個(gè)因素進(jìn)行兩兩對(duì)比，構(gòu)建判斷矩陣，如表1所示。

表1　判斷矩陣

對(duì)表1構(gòu)成的判斷矩陣通過(guò)合法的計(jì)算方式，求取其最大特征根λmax和歸一化的特征向量W。得到λmax=4.119，W=（0153，0.072，0.531，0.245）T，最后進(jìn)行判斷矩陣一致性檢驗(yàn)，發(fā)現(xiàn)其誤差值0.044小于閾值0.10，即通過(guò)判斷矩陣的一致性檢驗(yàn)，因此特征向量W的值是合理的，最終實(shí)時(shí)負(fù)載的權(quán)值確定為：λcpu=0.153、λmem=0.072、λio=0.531、λband=0.245。

2　實(shí)驗(yàn)與分析

優(yōu)化的HDFS副本放置策略的實(shí)驗(yàn)基于Hadoop-1.0.0。集群中存在兩種性能不同的計(jì)算機(jī)節(jié)點(diǎn)，分別標(biāo)識(shí)為性能A節(jié)點(diǎn)和性能B節(jié)點(diǎn)，其中A節(jié)點(diǎn)的主要硬件配置為：3.30GHz的Inter（R）Core（TM）i3-3220CPU，2GB DDR3的內(nèi)存，7 200rpm的500GB硬盤；B節(jié)點(diǎn)的主要硬件配置為：2.93GHz的Inter（R）Core（TM）2Duo（E7500）CPU，GB DDR3的內(nèi)存，4 500rpm的500GB硬盤。整個(gè)集群由1個(gè)機(jī)架組成，集群配置成1個(gè)名字節(jié)點(diǎn)、8個(gè)數(shù)據(jù)節(jié)點(diǎn)和1個(gè)客戶端的形式。其中性能A的數(shù)據(jù)節(jié)點(diǎn)編號(hào)為1、2、7、8，性能B的數(shù)據(jù)節(jié)點(diǎn)編號(hào)為3、4、5、6。實(shí)驗(yàn)中涉及的數(shù)據(jù)讀寫操作均通過(guò)客戶端發(fā)出。

圖3和圖4分別展示了在默認(rèn)策略和優(yōu)化策略下通過(guò)客戶端寫入1 000個(gè)數(shù)據(jù)塊時(shí)的副本分布情況。從圖3可以看出，在默認(rèn)策略下，副本放置位置是通過(guò)隨機(jī)算法獲取的，因此副本的分布顯得較為隨意，波動(dòng)性也比較大。副本的分布不具目的性，例如數(shù)據(jù)節(jié)點(diǎn)1和數(shù)據(jù)節(jié)點(diǎn)5，通過(guò)實(shí)驗(yàn)配置可知數(shù)據(jù)節(jié)點(diǎn)1在性能上比數(shù)據(jù)節(jié)點(diǎn)5要更優(yōu)越，然而數(shù)據(jù)節(jié)點(diǎn)1卻比數(shù)據(jù)節(jié)點(diǎn)5少存儲(chǔ)了100多個(gè)副本，這樣的分布顯然不太合理。而優(yōu)化策略下，副本的分布顯然更具目的性。如圖4所示，性能更好的1、2、7、8數(shù)據(jù)節(jié)點(diǎn)存儲(chǔ)的副本總量要多于性能較差的3、4、5、6數(shù)據(jù)節(jié)點(diǎn)。這是由于考慮了實(shí)時(shí)負(fù)載，性能更好的節(jié)點(diǎn)其負(fù)載程度相對(duì)較輕，存儲(chǔ)副本的概率較大。然而其總量上的區(qū)別還算合理，這是因?yàn)楸疚目紤]了另一個(gè)因素HDFS工作進(jìn)程，它能有效地限制一個(gè)節(jié)點(diǎn)進(jìn)行過(guò)量的操作。而且，整體的存儲(chǔ)情況是優(yōu)化策略要顯得更加均衡，這也是因?yàn)榭紤]了實(shí)時(shí)負(fù)載因素在無(wú)形中增加了低負(fù)載節(jié)點(diǎn)的工作量，減小了高負(fù)載節(jié)點(diǎn)的工作量，最終使優(yōu)化策略的副本分布看起來(lái)更加平衡。

圖3　默認(rèn)的副本放置策略副本分布

圖4　優(yōu)化的副本放置策略副本分布

最后本文通過(guò)客戶端寫入200、500、1 000個(gè)數(shù)據(jù)塊，對(duì)比數(shù)據(jù)傳輸?shù)臅r(shí)間，結(jié)果如圖5所示。從圖5可以看出由于優(yōu)化副本策略考慮了節(jié)點(diǎn)的實(shí)時(shí)負(fù)載，在一定程度上避開(kāi)了實(shí)時(shí)負(fù)載繁忙的節(jié)點(diǎn)，有效地均衡了節(jié)點(diǎn)的負(fù)載，并有目的地適當(dāng)提高了性能較高節(jié)點(diǎn)的使用，充分發(fā)揮其性能優(yōu)勢(shì)，最終實(shí)現(xiàn)了縮短存儲(chǔ)型數(shù)據(jù)寫入時(shí)間的目的。

圖5　數(shù)據(jù)寫入響應(yīng)時(shí)間對(duì)比

3　結(jié)論

本文分析了HDFS默認(rèn)副本放置策略的局限性，并據(jù)此提出了一種優(yōu)化的副本放置策略，該策略綜合考慮了實(shí)時(shí)負(fù)載和HDFS工作進(jìn)程數(shù)，有效提高了副本的合理分布。通過(guò)實(shí)驗(yàn)表明，相比于默認(rèn)策略，優(yōu)化的副本放置策略具有更明確的目的性，盡量選擇了最低實(shí)時(shí)負(fù)載節(jié)點(diǎn)，避開(kāi)了高負(fù)載節(jié)點(diǎn)的存儲(chǔ)，最終提升了副本傳輸?shù)臅r(shí)間。本文還通過(guò)科學(xué)的AHP方法確定了實(shí)時(shí)負(fù)載的權(quán)值，更加精確了實(shí)時(shí)負(fù)載的評(píng)估準(zhǔn)確性。

［1］WHITE T.Hadoop：The definitive guide［M］.O′Reilly Media，Inc.，2012.

［2］ABAD C L，Lu Yi，CAMPBELLR H.Dare：adaptive data replication for efficient cluster scheduling［C］.Proceedings of the 2011 IEEE International Conference on Cluster Computing，USA：IEEE Computer Society，2011：159-168.

［3］Xie Jiong，Yin Shu，Ruan Xiaojun，etal.Improving mapreduce performance through data placement in heterogeneous hadoop clusters［C］.2010 IEEE International Symposium on Parallel Distributes Processing，Workshops and Phd Forum（IPDPSW），Atlanta：IEEE Press，2010：1-9.

［4］林偉偉.一種改進(jìn)的Hadoop數(shù)據(jù)放置策略［J］.華南理工大學(xué)學(xué)報(bào)（自然科學(xué)版），2012，36（1）：152-158.

［5］邵秀麗，王亞光，李云龍，等.Hadoop副本放置策略［J］.智能系統(tǒng)學(xué)報(bào)，2013，8（6）：489-496.

［6］徐玖平，吳巍.多屬性決策的理論與方法［M］.北京：清華大學(xué)出版社，2006.

An improved replica placement strategy in Hadoop

Cai Yandong，Liu Yan，Zhang Qinglei
（College of Computer Science＆ Technology，Huaqiao University，Xiamen 361021，China）

Hadoop distributed file system applies default three copies of the random replica placement strategy without taking into account full load of Datanodes.To improve the cluster load balabcing of HDFS and the resource utilization of Datanodes，an improved replica placement strategy is proposed.The strategy considers real-time load of Datanodes and the number of the work process to select the minimum load Datanode storing data.Experiment shows that compared with default three copies of the random replica placement strategy，the improved strategy optimizes the balancing of cluster load and reduces I/O response time.

Hadoop；replacement of replica；real-time load；load balancing

TP391.41，TP911

A

1674-7720（2015）16-0021-03

蔡燕冬，劉艷，張慶磊.一種優(yōu)化的Hadoop副本放置策略［J］.微型機(jī)與應(yīng)用，2015，34（16）：21-23.

2015-03-19）

蔡燕冬（1990-），男，碩士研究生，主要研究方向：計(jì)算機(jī)存儲(chǔ)、計(jì)算機(jī)網(wǎng)絡(luò)。

劉艷（1976-），女，博士，副教授，主要研究方向：計(jì)算機(jī)存儲(chǔ)、網(wǎng)絡(luò)存儲(chǔ)系統(tǒng)、數(shù)據(jù)管理。

張慶磊（1989-），男，碩士研究生，主要研究方向：計(jì)算機(jī)存儲(chǔ)、計(jì)算機(jī)網(wǎng)絡(luò)。

國(guó)家自然科學(xué)青年基金項(xiàng)目（61202106）