羅 鵬，龔 勛

（四川大學計算機學院，四川成都610065）

0 引 言

隨著社會信息化程度的不斷提高，各種形式的數(shù)據(jù)急劇膨脹［1］。因為數(shù)據(jù)量的快速增長，在網(wǎng)絡(luò)上出現(xiàn)了越來越多的數(shù)據(jù)密集型應(yīng)用，如何安全可靠及有效地存儲海量數(shù)據(jù)是云計算［2］的一個重要研究方向，而HDFS（hadoop distributed file system）［3，4］就是解決海量數(shù)據(jù)存儲問題的一個開源分布式文件系統(tǒng)。

HDFS有著高容錯性的特點，并且設(shè)計用來部署在低廉的硬件上。它提供高吞吐量來訪問應(yīng)用程序的數(shù)據(jù)，適合擁有超大數(shù)據(jù)集的應(yīng)用。為了避免機器故障給數(shù)據(jù)帶來毀滅性的災(zāi)難，HDFS將文件分塊，且每個數(shù)據(jù)塊以多個數(shù)據(jù)副本的形式存儲在多個數(shù)據(jù)節(jié)點上［5］。針對數(shù)據(jù)存放的問題，HDFS將每個數(shù)據(jù)節(jié)點以機架為單位進行組織，并添加到網(wǎng)絡(luò)拓撲中。在選擇數(shù)據(jù)節(jié)點時，默認存放第一個數(shù)據(jù)塊副本到本地機架，并隨機選擇遠端機架存放其他數(shù)據(jù)副本，從而減輕了網(wǎng)絡(luò)的負擔，同時也降低了數(shù)據(jù)的風險。

但是，HDFS在選擇數(shù)據(jù)存放節(jié)點時，沒有考慮到集群中數(shù)據(jù)節(jié)點性能、網(wǎng)絡(luò)狀況和存儲空間的差異性［6］，從而造成集群整體負載不均衡，數(shù)據(jù)節(jié)點的資源無法合理利用。因此，本文在綜合考慮每個數(shù)據(jù)節(jié)點CPU負載、內(nèi)存負載、網(wǎng)絡(luò)負載［7］和存儲空間負載［8］的基礎(chǔ)上，提出一種改進的數(shù)據(jù)存放策略。

1 HDFS數(shù)據(jù)存放策略

HDFS采用基于元數(shù)據(jù)服務(wù)器的組織結(jié)構(gòu)進行工作。名稱節(jié)點（namenode）負責存儲和管理文件系統(tǒng)的元數(shù)據(jù)，數(shù)據(jù)節(jié)點（datanode）負責存儲和管理數(shù)據(jù)［9］。當客戶端需要寫入數(shù)據(jù)時，客戶端先訪問名稱節(jié)點，請求寫數(shù)據(jù)操作。在通過名稱節(jié)點的權(quán)限檢查后，名稱節(jié)點選擇合適的節(jié)點，返回給客戶端。

1.1 機架感知［10］理論

由于大型HDFS實例一般運行在跨越多個機架的集群上，不同機架上的兩臺機器之間通信需要經(jīng)過交換機，在大多數(shù)情況下，同一個機架內(nèi)的兩臺機器間的帶寬會比不同機架的機器間的帶寬大。因此，名稱節(jié)點在選擇合適的數(shù)據(jù)節(jié)點時，為了提高網(wǎng)絡(luò)帶寬的利用率、保證數(shù)據(jù)的可靠性，應(yīng)用了機架感知的理論。該理論一個重要的前提是HDFS運行于一個具有樹狀網(wǎng)絡(luò)拓撲結(jié)構(gòu)的集群上。集群可以由多個數(shù)據(jù)中心組成，每個數(shù)據(jù)中心有多個機架，每個機架上有多個數(shù)據(jù)節(jié)點。

機架感知的網(wǎng)絡(luò)拓撲結(jié)構(gòu)示例圖如圖1所示。

圖1 機架感知的網(wǎng)絡(luò)拓撲結(jié)構(gòu)

圖1展示了兩個數(shù)據(jù)中心的網(wǎng)絡(luò)拓撲結(jié)構(gòu)。其中Di（i∈［1，2］）、Ri（i∈［1，4］）都是交換機，DNi（i∈［1，12］）是數(shù)據(jù)節(jié)點。

設(shè)rackid表示節(jié)點在網(wǎng)絡(luò)拓撲結(jié)構(gòu)中的路徑。如圖1所示，DN1的rackid＝/D1/R1/DN1。每個rackid中都包含了該節(jié)點的父節(jié)點以及每個層次的祖先節(jié)點。

為了衡量兩個節(jié)點的距離，HDFS采用了一個簡單的方法，兩個節(jié)點間的距離就是它們到最近的共同祖先的距離總和。通過機架感知的過程，名稱節(jié)點可以確定每個數(shù)據(jù)節(jié)點所屬的rackid，通過rackid可以計算數(shù)據(jù)節(jié)點之間的網(wǎng)絡(luò)距離。

設(shè)distance（rackid1，rackid2）表示rackid1與rackid2之間的網(wǎng)絡(luò)距離。

如圖1所示，distance（/D1/R1/DN1，/D1/R1/DN1）＝0（同一個節(jié)點）。

distance（/D1/R1/DN1，/D1/R1/DN2）＝2（同一機架上的不同節(jié)點）。

distance（/D1/R1/DN1，/D1/R2/DN4）＝4（同一數(shù)據(jù)中心不同機架上的節(jié)點）。

distance（/D1/R1/DN1，/D2/R3/DN7）＝6（不同數(shù)據(jù)中心的節(jié)點）。

1.2 數(shù)據(jù)存放策略

設(shè)數(shù)據(jù)塊的n個副本，分別存放在rackid為RACKID1，RACK－ID2，……，RACK－IDn的節(jié)點上（n∈N＊），distance（RACK－IDi，RACK－IDj）表示RACK－IDi與RACK－IDj的距離，其中i≤n，j≤n（i、j∈N＊）。

HDFS數(shù)據(jù)存放策略具體流程如下:

步驟1 如果Client是集群中的數(shù)據(jù)節(jié)點，那么Namenode選擇Client主機存放數(shù)據(jù)塊的第一個副本。

步驟2 如果Client不是集群中的數(shù)據(jù)節(jié)點，Namenode隨機選擇集群中的任意一個Datanode（數(shù)據(jù)節(jié)點）存放數(shù)據(jù)塊的第一個副本。

步驟3 Namenode計算distance（RACK－ID1，RACKIDk），其中k∈N＊，k≤n并且k≠1，隨機選擇與第一個副本存放節(jié)點不在同一個機架的數(shù)據(jù)節(jié)點作為第二個數(shù)據(jù)塊副本的存放節(jié)點。

步驟4 Namenode計算distance（RACK－ID2，RACKIDk），其中k∈N＊，k≤n，k≠1且k≠2，隨機選擇與第二個副本存放節(jié)點在同一個機架的數(shù)據(jù)節(jié)點作為第三個數(shù)據(jù)塊副本的存放節(jié)點。

步驟5 對多于3個副本的情況，Namenode為其它副本隨機選擇集群中的任意一個還沒有被選中Datanode作為數(shù)據(jù)塊副本存放節(jié)點。

以上情況，在每個Datanode選中后，如果出現(xiàn)節(jié)點存儲空間不足、網(wǎng)絡(luò)連接負載過重或者所在機架選擇的Datanode數(shù)量過多的問題，則重新選擇一個數(shù)據(jù)節(jié)點。

2 改進的數(shù)據(jù)存放策略

2.1 問題描述

HDFS的數(shù)據(jù)存放策略基于以下兩個基本原則:

原則1:存在兩個或兩個以上機架的情況下，如果數(shù)據(jù)塊副本數(shù)量多于1個，則數(shù)據(jù)塊副本至少分布在兩個不同的機架上。

原則2:選擇距離較近的數(shù)據(jù)節(jié)點，即“臨近原則”。HDFS的數(shù)據(jù)存放策略在保證以上兩個基本原則的基礎(chǔ)上仍存在以下問題:

（1）HDFS數(shù)據(jù)存放策略在選擇數(shù)據(jù)塊副本存放節(jié)點的算法上隨機性較大。

（2）HDFS數(shù)據(jù)存放策略雖然考慮了數(shù)據(jù)節(jié)點的網(wǎng)絡(luò)連接數(shù)，卻是在隨機選擇了數(shù)據(jù)節(jié)點之后再進行衡量，導致集群負載的均衡性不太理想。

基于上述問題，在保證原則1和原則2的前提下，本文提出一種綜合考慮數(shù)據(jù)節(jié)點負載，優(yōu)先選擇負載最小的數(shù)據(jù)節(jié)點作為副本存放節(jié)點的數(shù)據(jù)存放策略。

2.2 改進策略

定義1 存放成本用于衡量一個數(shù)據(jù)節(jié)點存放數(shù)據(jù)塊副本的優(yōu)先程度，數(shù)據(jù)節(jié)點負載越大，存放成本越高，優(yōu)先程度越低。

定義2 負載因子用于計算數(shù)據(jù)節(jié)點存放成本的參數(shù)，包括CPU負載、內(nèi)存負載、網(wǎng)絡(luò)負載和存儲空間負載。

數(shù)學模型如下:

設(shè)數(shù)據(jù)節(jié)點的集合DN＝｛DN1，DN2，DN3，…，DNm｝，DNi為該集合的任一數(shù)據(jù)節(jié)點，DNi∈DN，m為HDFS集群中數(shù)據(jù)節(jié)點的數(shù)量。數(shù)據(jù)節(jié)點DNi的CPU負載為CPUi，平均值為DNi的內(nèi)存負載為Memi，平均值為DNi的網(wǎng)絡(luò)負載為Neti，平均值為DNi最近k次CPUi負載的集合CPUi＝｛CPUi1，CPUi2，…，CPUik｝，DNi最近k次Memi負載的集合Memi＝｛Memi1，Memi2，…，Memik｝，DNi最近k次Neti負載的集合Neti＝｛Neti1，Neti2，…，Netik｝，則

其中，k的值，本文默認為5，即計算最近5次的負載因子的平均值。

設(shè)WCPU、WMem、WNet、WS分別表示數(shù)據(jù)節(jié)點的CPU、內(nèi)存、網(wǎng)絡(luò)、存儲空間負載的權(quán)值系數(shù)。DNi的存儲空間負載為Si。

數(shù)據(jù)節(jié)點DNi的存放成本Ci可定義為

其中，WCPU、WMem、WNet、WS的具體值，需要通過實驗的測試結(jié)果，選擇最優(yōu)化的一組權(quán)值系數(shù)。

2.3 算法描述

步驟1 Datanode每間隔60s，采集CPU運行時間，CPU空閑時間，內(nèi)存總量，內(nèi)存使用量，網(wǎng)絡(luò)上行流量、網(wǎng)絡(luò)下行流量，以及存儲空間的使用信息。

步驟2 計算間隔時間內(nèi)CPU利用率、網(wǎng)絡(luò)帶寬利用率，以及在采集時間點時內(nèi)存的利用率、存儲空間的利用率。并計算近5次CPU利用率、網(wǎng)絡(luò)帶寬利用率和內(nèi)存利用率的平均值。

Datanode處理流程如圖2所示。

步驟4 Namenode收到Datanode發(fā)送的心跳包，根據(jù)公式（4），計算數(shù)據(jù)塊副本存放成本。

步驟5 在Client向Namenode發(fā)送寫數(shù)據(jù)請求時，Namenode選擇最優(yōu)數(shù)據(jù)節(jié)點，返回給Client。

Namenode選擇數(shù)據(jù)塊副本存放節(jié)點的偽代碼如下所示:（注:numOf Replication表示副本數(shù)量，且副本數(shù)量大于1的情況下，數(shù)據(jù)節(jié)點不能被重復(fù)選擇）

在選擇一個數(shù)據(jù)塊副本的存放節(jié)點時，由于改進后的策略，需要在機架上選擇存放成本最低的Datanode，而原始的HDFS策略只是在機架上隨機選擇Datanode存放數(shù)據(jù)塊副本。對于有N個節(jié)點的數(shù)據(jù)中心，前者的計算量正比于數(shù)據(jù)中心的節(jié)點數(shù)量，后者的計算量也與數(shù)據(jù)中心節(jié)點存在線性關(guān)系，兩者的復(fù)雜度都為O（N）。

圖2 Datanode處理流程

3 實 驗

3.1 實驗環(huán)境

實驗的拓撲結(jié)構(gòu)如圖3所示，HDFS分布式文件系統(tǒng)搭建在A、B、C這3個機架上。slave1與master位于機架A，slave1負責測試數(shù)據(jù)的上傳。slave2與slave3位于機架B，slave4與slave5位于機架C。其中，名稱節(jié)點是機器master，slave1～slave5是數(shù)據(jù)節(jié)點。

圖3 實驗拓撲

6個測試機器的軟硬件配置和安裝環(huán)境如下:

虛擬機:VMware Workstation 7.1.2 build－301548

操作系統(tǒng):32位的CentOS 5.4系統(tǒng)

Java運行環(huán)境:JDK 1.6.0＿20

分布式環(huán)境:Hadoop 0.20.203.0

CPU:2.93GHZ

內(nèi)存:1GB

網(wǎng)絡(luò)帶寬:100 Mb/s

3.2 實驗內(nèi)容及結(jié)果分析

3.2.1 可行性驗證

在本實驗中，分別獲取了HDFS在兩種策略下，處理不同大小的上傳數(shù)據(jù)所耗費的時間。實驗中的時間開銷是通過多次測試，獲取的平均值。實驗數(shù)據(jù)通過位于機架A的slave1進行上傳，數(shù)據(jù)大小包括:256MB，512MB，1GB，2GB，3GB。結(jié)果如圖4所示。

圖4 兩種策略的時間開銷對比

由于本實驗采取3個副本存放數(shù)據(jù)，所以在兩種策略中，第一個副本都是存放在本地（即slave1）上。如圖4所示，在測試數(shù)據(jù)為256MB時，兩種策略的時間開銷基本相同，隨著測試數(shù)據(jù)量的增多，兩者時間開銷的差距逐漸增大。改進的策略相比HDFS策略，后者在數(shù)據(jù)節(jié)點較少的情況下，由于隨機的選擇數(shù)據(jù)存放節(jié)點，容易導致部分數(shù)據(jù)節(jié)點網(wǎng)絡(luò)負載偏重，而其他數(shù)據(jù)節(jié)點空閑，從而出現(xiàn)數(shù)據(jù)副本在節(jié)點間傳輸相對偏慢的情況，而前者綜合考慮了每個數(shù)據(jù)節(jié)點的負載，使得集群的網(wǎng)絡(luò)帶寬等資源得到更合理的利用。由此可說明改進的數(shù)據(jù)存放策略是可行的。

3.2.2 比較負載的均衡性

本實驗分別比較在兩種策略下，整個集群所有數(shù)據(jù)節(jié)點的CPU負載、內(nèi)存負載、網(wǎng)絡(luò)負載和存儲空間負載的均衡性。實驗中，slave1上傳1G的測試數(shù)據(jù)，并在圖5～圖8中，列出了各個數(shù)據(jù)節(jié)點在兩種策略中的各項平均負載值的對比。圖9通過式（4）計算每個數(shù)據(jù)節(jié)點的平均存放成本值，從整體上，可以看出在兩種策略下，整個集群負載的均衡性。

（1）CPU負載

圖5 CPU平均負載對比

（2）內(nèi)存負載

圖6 內(nèi)存平均負載對比

（3）網(wǎng)絡(luò)負載

圖7 網(wǎng)絡(luò)平均負載對比

（4）存儲空間負載

圖8 存儲空間負載對比

（5）數(shù)據(jù)節(jié)點平均存放成本比較

圖9 數(shù)據(jù)節(jié)點平均存放成本對比

通過反復(fù)實驗，參考CPU負載、內(nèi)存負載、網(wǎng)絡(luò)負載、存儲空間負載的統(tǒng)計結(jié)果，根據(jù)各項負載因子的負載能力，波動情況及其重要性，分別設(shè)置WCPU＝0.1，WMem＝0.2，WNet＝0.3，WS＝0.4。

由于數(shù)據(jù)節(jié)點slave1作為上傳測試數(shù)據(jù)的客戶端，根據(jù)兩種策略的算法，slave1會存儲所有數(shù)據(jù)塊的第一個副本，所以slave1的負載在所有數(shù)據(jù)節(jié)點中是最高的。

slave2與slave3、slave4與slave5分別在同一個機架，根據(jù)兩種策略的算法，slave2與slave3、slave4與slave5被選中的概率是相等的，所存儲的數(shù)據(jù)量也是相同的。因此，從圖5～圖8可以看出，同一個機架上的數(shù)據(jù)節(jié)點負載情況是基本一致的。

改進后的數(shù)據(jù)存放策略相比原始的HDFS數(shù)據(jù)存放策略，由于處理實驗數(shù)據(jù)耗費時間相對較少，所以，如圖5～圖8所示，從整個集群來看，CPU平均負載，內(nèi)存平均負載，網(wǎng)絡(luò)平均負載，前者的數(shù)值更高。

圖9展示了slave1～slave5所有數(shù)據(jù)節(jié)點的平均存放成本。從圖中可以看出，slave1的平均存放成本是最高的，slave2與slave3、slave4與slave5平均存放成本是基本相同的。改進的數(shù)據(jù)存放策略相比HDFS數(shù)據(jù)存放策略，由于綜合的考慮了每個數(shù)據(jù)節(jié)點的性能差異，所以在數(shù)據(jù)節(jié)點的選擇過程中避免了連續(xù)多次選擇性能較低的節(jié)點，更好的利用了集群的網(wǎng)絡(luò)資源，以及各個數(shù)據(jù)節(jié)點的本地資源。如圖9所示，改進后的策略，集群負載的均衡性得到了很好的優(yōu)化。

4 結(jié)束語

文中介紹了HDFS分布式文件系統(tǒng)數(shù)據(jù)存放的相關(guān)內(nèi)容。針對HDFS的數(shù)據(jù)存取策略沒有考慮節(jié)點的差異性導致節(jié)點負載不均的問題，提出了改進的方法。該方法綜合考慮了節(jié)點的CPU負載，內(nèi)存負載，網(wǎng)絡(luò)負載和存儲空間負載，通過設(shè)置負載因子的權(quán)值提高HDFS的數(shù)據(jù)存放性能。

本文的不足是沒有對負載因子權(quán)值的選取進行更深入的研究。權(quán)值的選取與HDFS運行環(huán)境相關(guān)，所以需要結(jié)合實際情況反復(fù)進行實驗，才能得出更加精確的數(shù)據(jù)存放策略，進一步提高HDFS分布式文件系統(tǒng)數(shù)據(jù)存放的性能。

［1］Wade.IDC's latest research report:“Digital Universe in 2020”［EB/OL］.［2012－12－26］.http://info.chinabyte.com/487/12496987.shtml（in Chinese）.［Wade.IDC最新調(diào)研報告:“2020年的數(shù)字宇宙”［EB/OL］.［2012－12－26］.http://info.chinabyte.com/487/12496987.shtml.］

［2］CHEN Kang，ZHEN Weimin.Cloud computing:System instances and current research［J］.Journal of Software，2009，20（5）:1337－1348（in Chinese）.［陳康，鄭緯民.云計算:系統(tǒng)實例與研究現(xiàn)狀［J］.軟件學報，2009，20（5）:1337－1348.］

［3］Apache.Apache Hadoop［EB/OL］.［2013－07－10］.http://hadoop.apache.org/.

［4］Dhruba Borthakur.HDFS architecture guide［EB/OL］.http://archive.cloudera.com/cdh4/cdh/4/mr1/hdfs＿design.pdf，2008.

［5］Rahman R，Alhajj R，Barker K.Replica selection strategies in data grid［J］.Journal of Parallel and Distributed Computing，2008，68（12）:1561－1574.

［6］Tom White.Hadoop:The definitive guide［M］.2nd ed.ZHOU Minqi，WANG Xiaoling，transl.Beijing:Tsinghua University press，2011（in Chinese）.［Tom White.Hadoop權(quán)威指南［M］.2版.周敏奇，王曉玲，譯.北京:清華大學出版社，2011.］

［7］LIN Weiwei.An improved data placement strategy of Hadoop［J］.Journal of South China University of Technology（Natural Science Edition），2012，40（1）:152－158（in Chinese）.［林偉偉.一種改進的Hadoop數(shù)據(jù)放置策略［J］.華南理工大學學報（自然科學版），2012，40（1）:152－158.］

［8］ZHOU Jingli，ZHOU Zhengda.Improved data distribution strategy for cloud storage system［J］.Journal of Computer Applications，2012，32（2）:309－312（in Chinese）.［周敬利，周正達.改進的云存儲系統(tǒng)數(shù)據(jù)分布策略［J］.計算機應(yīng)用，2012，32（2）:309－312.］

［9］WANG Yijie，SUN Weidong，ZHOU Song，et al.Key technologies of distributed storage for cloud computing［J］.Journal of Software，2012，23（4）:962－986（in Chinese）.［王意潔，孫偉東，周松，等.云計算環(huán)境下的分布存儲關(guān)鍵技術(shù)［J］.軟件學報，2012，23（4）:962－986.］

［10］Apache.Rack aware HDFS proposal［EB/OL］.https://issues.apache.org/jira/secure/attachment/12345251/，2008.