基于支持向量機的HDFS副本放置改進策略

羅 軍，陳仕強

（重慶大學計算機學院，重慶400044）

基于支持向量機的HDFS副本放置改進策略

羅 軍，陳仕強

（重慶大學計算機學院，重慶400044）

為實現超大規模數據的存儲并提高容錯性，Hadoop分布式文件系統（HDFS）采用一種機架感知的多副本放置策略。但在放置過程中沒有綜合考慮各節點服務器的差異性，導致集群出現負載失衡。由于放置時采用隨機方式，造成節點之間的網絡距離過長，使得傳輸數據會消耗大量時間。針對以上問題，提出一種基于SVM的副本放置策略。通過綜合考慮節點負載情況、節點硬件性能、節點網絡距離為副本找到最佳的放置節點。實驗結果表明，與HDFS原有的副本放置策略相比，該策略能更有效地實現負載均衡。

支持向量機；云存儲；副本放置策略；分布式文件系統；負載均衡；機架感知

1 概述

Hadoop是一個能夠對大量數據進行分布式處理的開源軟件框架，其思想來源于Google公司的Map Reduce框架［1］，分布式數據密集的并行應用程序利用該框架能將大的任務和數據集分解成為更小的任務和數據集，并使這些任務在不同的分區中平行處理。Hadoop利用分布式文件系統HDFS來存儲這些數據，而HDFS的設計思想來自于Google的GFS［2］。

HDFS是一種能夠運行在大量廉價硬件上的分布式文件系統［3］，它不僅具有分布式文件系統的大量優點，而且還做了許多改善：具有很高的容錯性，對硬件性能要求不高，可以實現高吞吐量的數據訪問，特別適合運用在超大規模數據集上。

為了能夠應對超大量數據的存儲和提供較好的容錯性能，分布式文件系統需要采用多副本策略，而且需要將多個副本分布在集群中的不同位置上，但如果副本放置的方式不當將會極大影響系統的負載均衡，從而導致系統運行效率低下。HDFS采用一種機架感知的策略來放置副本，默認的副本數為3個。在放置多個副本時這種策略采用隨機的方式，會使整個集群負載失衡，文獻［4］利用數據在邏輯上的相關性，將HDFS改裝成應用層可以自行控制數據要存放的節點集，使具有邏輯相關性的數據副本可以存在相同的幾個節點上，提升了對節點數據和副本的管理效率。文獻［5］提出一種根據節點文件訪問熱度來動態調節其相應的副本數，并且將集群的剩余空間也作為調節副本數的一項評價指標。

本文在這些方法的基礎上，提出一種基于SVM的副本放置策略模型。

2 HDFS架構及其副本放置策略

2.1 原有副本放置策略

在分布式的文件系統架構中，為了提高整個集群的性能，通常會將元數據與數據分離，以實現對元數據和數據的高效管理，其中元數據節點的職責是管理文件系統命名空間和文件的各種屬性，數據節點的職責是負責管理文件上的具體數據，并且直接處理來自客戶端的文件讀寫請求，HDFS采用了主從式的分布式架構，圖1展示了HDFS的架構。

圖1 HDFS架構

在HDFS集群中有一個名字節點和多個數據節點。名字節點作為主服務器的職責是管理文件系統的元數據，記錄對文件的操作，并維護文件系統中的塊和存儲位置等信息。數據節點作為從節點的任務是使用本地文件系統存儲塊數據，響應客戶端的請求，接收或者傳送數據［6］。HDFS文件存儲的單位是塊，并且塊的大小默認為64 MB，這比一般的磁盤塊要大很多，目的是為了配合大文件的存儲，以減小文件的尋址開銷。出于可靠性考慮，HDFS對每個塊進行冗余存儲，默認的副本數為3個。

由于元數據與數據的管理是分離的，因此對文件數據的讀寫操作并不需要通過元數據節點，這樣就提高了文件的讀寫效率。圖2為HDFS中文件的寫入過程。

圖2 HDFS文件寫入過程

當有文件要寫入時，HDFS客戶端將請求發給名字節點，名字節點接收到請求時會先檢查文件是否已經存在，若不存在還需要檢查相關權限，如果成功則為這個請求的文件創建一個記錄。客戶端在寫入文件時，最初是將數據寫入到本地的臨時文件中，如果數據大小達到一個塊的大小時，客戶端便從名字節點得到一個有許多數據節點的列表，這些數據節點是用來存放副本的，接收數據是從第1個數據節點開始一部分一部分接收，并且在將這部分數據寫入的同時，還將這些數據傳給第2個數據節點，第2個數據節點也和第1個數據節點一樣開始寫入數據的同時并將數據傳給下一個節點，這種操作是以流水線的方式完成的［7］。

HDFS采用一種機架感知策略來組織集群，通過機架感知，名字節點可以獲得所有數據節點的網絡拓撲圖，同一個機架上的節點之間的網絡狀況比不同機架的要理想。HDFS設法將副本保存在同一機架和不同機架中，其中保存在同一機架中能夠減少網絡傳輸開銷，而放在不同機架中能提高數據安全性。HDFS默認采用的副本數為3，其存儲結構如圖3所示。

圖3 HDFS默認數據放置策略

在圖3中，第1個副本放置在和客戶端同一的節點上，第2個副本放置在與第1個副本同一機架的不同節點上，第3個副本隨機放置在不同機架的節點上。這種策略能夠減少機架之間的傳輸，從而提高文件的讀寫效率，又由于有副本存放在不同機架上，因此也提高了數據的可靠性和安全性。

2.2 原有副本放置策略的不足

雖然HDFS原有的副本放置策略簡單快捷，提高了整個集群的容錯性，但是這種策略在存放副本的時候沒有綜合考慮節點負載情況、節點硬件性能、節點網絡距離等因素，容易出現負載失衡。仍然有許多需要改進的地方：

（1）在選擇副本放置節點時沒有考慮節點的空間利用率，雖然HDFS提供了一個負載均衡的工具Balancer，它能夠將負載較多的節點上的數據轉移到負載較少的節點上，不過這個工具是在副本已經放置后手動觸發的，所以并沒有從源頭上減少集群負載失衡的發生，而且Balancer在平衡負載的過程中還浪費了大量網絡傳輸時間和網絡帶寬。

（2）沒有考慮節點服務器的硬件性能，在集群中不同節點的機器是異構的，在具有相同負載的情況下，其對數據的讀寫速率是不一樣的。

（3）沒有考慮節點之間的網絡距離，在將副本放置到不同節點時，距離越遠的節點需要的傳輸時間越長。

3 改進的副本放置策略

3.1 基本思想

HDFS在副本放置過程中沒有綜合考慮各節點服務器的差異性，這會導致集群出現負載失衡。而HDFS在選擇遠程機架節點放置副本時采用隨機方式，這有可能導致節點之間的網絡距離過長，使得在節點之間傳輸數據會消耗大量時間。針對以上問題，SRPM采用SVM解決。

首先SRPM對集群中的每個節點服務器的負載、磁盤轉速、CPU性能等硬件信息以及節點網絡距離進行特征提取。

然后SRPM將這些提取的特征值以節點為單位組成SVM的輸入數據，SVM根據輸入數據將節點分為兩類，一類是適合放副本的節點，一類是不適合放副本的節點。SRPM在適合放副本的節點中隨機選擇一個節點放置副本，這樣便能有效避免隨機選擇到不適合放置副本的節點的情況。

3.2 問題描述

SVM是建立在統計學習理論基礎上的一種數據挖掘方法，能非常成功地處理回歸問題（時間序列分析）和模式識別（分類問題、判別分析）等諸多問題［8］。SVM是通過尋找一種結構化風險最小的方式進行學習分類的，即使在樣本很少的情況下也能達到較好的分類效果［9］。

根據HDFS集群的特點，可以用一個有向圖G=（V，E，ψ）來表示HDFS集群，其中，頂點vi∈V表示HDFS集群中的節點；邊ei∈E表示節點中副本的流向；ψ（e）=（u，v）表示節點u上的數據在節點v上保存有副本；ψ（e）的值表示（u，v）之間的網絡距離，節點連線箭頭由u指向v。

假設現在有一節點u上的數據需要設置副本，該副本是否放置在另一節點v上可以表示為y=f（u，v，ψ），當y=+1表示u上的數據副本可以放置在節點v上，當y=-1表示u上的數據副本不能放置在節點v上。因此副本放置問題可以描述為在已知節點u，v和ψ的條件下，求解y=f（u，v，ψ）的值，y∈｛-1，1｝，可以看出該問題是一個典型的二分類問題，可以采用SVM的方法去解決。

但是傳統的SVM在對大規模的數據集進行處理時需要消耗大量時間［9］，這是因為在SVM的算法中需要處理二次規劃問題，當訓練規模過于龐大的時候會導致求解時間過長［10］。

為了解決SVM在處理大規模數據時的問題，常用的解決方法主要有2種：（1）在不改變工作集的情況下提高訓練速度；（2）減小工作集［11］，如常用的LIBSVM采用工作集方法。

本文采用了LIBLINEAR，一種繼承自LIBSVM能夠對大規模數據進行線性分類的工具，實驗表明LIBLINEAR的訓練速度非常快，例如對于一個6× 105條的數據訓練只需要幾秒鐘，而用常規的LIBSVM則需要幾個小時［12］。

3.3 節點特征選取

在整個分布式集群中，文件的讀寫效率會受到多種因素的影響，如節點服務器中磁盤的讀寫速度、CPU性能、內存大小以及節點之間的網絡距離都會影響到數據的讀寫速率，所以如果數據副本放置過程中沒有綜合考慮這些因素將會導致嚴重的負載失衡問題，本文將從以下5個因素提取特征：

（1）相對負載率

在數據寫的過程中，數據節點的磁盤利用率是影響整個集群負載均衡的重要因素之一，這是因為整個集群是建立在大量廉價設備上，不同的數據節點有著不同的磁盤容量，所以對于不同的節點應該區別對待，對于磁盤容量大的數據節點應該存儲更多的數據，而較小的只需要存儲較小的數據即可，針對集群里節點之間的差異性，可以用相對負載來衡量：

其中，λDNi為節點相對負載，當λDNi＞1時表示節點的負載率大于整個集群的平均負載率，當λDNi＜1時表示節點的負載率小于整個集群的平均負載率；P（DNi）表示節點的負載率：

其中，DNi（use）表示節點已使用的磁盤容量；DNi（total）表示節點的磁盤總容量，節點的磁盤總容量為一個固定值，單位為GB。

P（DNaverage）表示整個集群的平均負載率：

其中，n為整個集群的數據節點數。

（2）網絡距離

節點網絡距離表示存放數據的節點與要存放該數據副本節點之間的網絡拓撲距離，網絡距離的大小會對數據的讀寫時間造成很大的影響。如果網絡距離過長，那么數據的讀寫時間也就會變得很長，本文中在同一機架中節點之間的網絡距離為0，節點網絡距離可用以下公式表示：

其中，L（DNij）表示節點i和節點j的網絡距離；NetLength（DNi，DNj）表示節點i和節點j所在機架之間的網絡拓撲距離，即兩機架之間的交換機或路由器數目。

（3）磁盤性能

節點服務器磁盤性能也是影響集群節點文件讀寫快慢的重要因素之一，磁盤性能指標可以用以下公式表示：

其中，D（DNi）表示節點服務器磁盤的量化性能值；Size表示磁盤容量；R表示磁盤轉速；Cache表示緩存大小；Vdata表示磁盤的數據傳輸率；表示平均尋道時間，即磁盤磁頭移動到數據所在磁道時所用的時間。

（4）CPU性能

CPU的性能在很大程度上決定了計算機的性能，衡量CPU性能指標有多個，可以用以下公式來衡量：

其中，W（DNi）表示CPU的量化性能值；f表示CPU的主頻；Cache表示CPU的緩存大小；NUM表示CPU的核心數量；Vbus表示CPU的總線速度。

（5）內存

對于經常被訪問的數據，節點可以把這些數據放入內存中，這樣能顯著提高數據的訪問速度。因此，節點內存的大小對負載均衡的效果也有顯著影響。衡量內存性能采用下式：

其中，M（DNi）表示內存的量化性能值；V表示內存速度，即存取一次數據所需要的時間；Size表示內存的大小；Bandw idth表示內存的帶寬；CAS表示等待時間，即指從讀命令有效開始到輸出端可以提供數據為止的一段時間，等待時間越短表示內存性能更好。

3.4 算法描述

算法思想：假設副本數為3，用SVM將各節點服務器依據各節點特征值分成2類：（1）適合放置副本的節點；（2）不適合放置副本的節點。在適合放置副本的節點中選一個節點作為副本放置的最佳節點。

輸入 各節點服務器提取的特征值

輸出 可以放置副本的最佳節點

算法偽代碼如下：

4 實驗與結果分析

4.1 改進策略的具體實現

為了檢驗改進策略的有效性，在Hadoop1.1.2中重寫了HDFS的Replication Target Chooser類，該類主要負責副本放置，當有數據存儲的時候就會調用ReplicationTargetChooser類。首先在該類初始化構造方法中將LibLinear引入進來，并根據NetworkTopology類的clusterMap對象獲取集群中所有的節點，并獲得各節點的負載情況，節點的硬件信息包括磁盤讀寫速度、內存大小及CPU性能以及節點之間的網絡距離，利用SVM進行分類預測，將上述分類結果按放置策略的優先順序從高到低排列。其次在Rep licationTargetChooser類中對節點進行選擇時會分別調用3個方法，分別為chooseLocalNode方法，即選擇本地節點，chooseLocalRack，即選擇本地機架方法，chooseRemoteRack，即選擇遠程機架方法。在這3個方法中重寫其隨機選擇的方式，改用SVM分類結果較好的節點。

4.2 實驗環境

為了驗證改進的副本放置策略模型的有效性，在Hadoop1.1.2集群上進行了改進策略模型的相關實驗，并與HDFS原有的副本放置策略模型做了比較。實驗操作系統采用CentOs6.4，JDK采用jdk1.6，通過虛擬機搭建了4個機架，每個機架5個節點，每個節點的容量為20 GB，在Hadoop集群中網絡為樹形拓撲結構，其中葉節點為節點服務器，非葉節點為路由器或交換機。在該樹形拓撲結構中子節點到父節點的網絡距離為1，兩節點服務器的網絡距離為這兩節點到其最近公共祖先節點的距離之和，其網絡拓撲距離如表1所示。

表1 Hadoop集群的網絡拓撲距離

4.3 性能分析

在實驗中，為了驗證改進策略在網絡距離上的效果，首先只在機架1中的節點1提交數據，該數據共有200塊，其中每塊大小為64 MB，集群默認的副本數為3，該提交數據存放在非機架1上的副本塊數為200，而在機架1上的副本塊數為400。假設初始時各節點都是空載狀態。

若原有的副本放置策略、數據副本塊數分布如圖4和圖5所示，如果采用改進的副本放置策略其分布如圖6和圖7所示。

圖4 原有策略下數據塊副本在本地機架的分布

圖5 原有策略下數據塊副本在遠端機架的分布

圖6 改進策略下數據塊副本在本地機架的分布

圖7 改進策略下數據塊副本在遠端機架的分布

由于改進的副本放置策略考慮了網絡距離的影響，因此在放置副本時如果各節點負載相差不大的情況下改進的副本放置策略模型會優先考慮網絡距離較近的機架上的節點。在本實驗中，改進的副本放置策略相比于HDFS原有的副本放置策略其平均距離縮短了17.3%。

在比較了網絡距離的效果后，為了驗證節點硬件性能對集群負載的效果，分別在4個機架上的一個數據節點上提交了500個數據塊，其中每個數據塊大小都為64 MB。提交開始時，各數據節點都是空載狀態。

采用默認的副本放置策略和改進的副本放置策略的結果如圖5所示，其中縱坐標表示每個節點的負載率，即每一個節點已使用的容量與該節點總的容量的比值。

從圖8中可以看出，通過4次提交數據塊后，改進的策略模型中各節點的相對負載相比于原有的策略模型要均衡得多，改進的策略模型有效改善了集群的負載均衡。

圖8 數據節點的負載率比較

表2展示了4次提交過程中的時間開銷，即從文件提交到完成總的開銷。由于改進的策略模型需要通過SVM算法尋找最優的副本放置處，這樣就會增加一定的時間開銷，但在改進的策略模型中，數據節點之間的距離也是算法的參考指標之一，所以在放置副本時改進的策略模型會優先考慮距離近的節點放置，這樣就減少了副本放置的時間，改進策略模型相對于原有策略模型的時間開銷差距并不是很大。

表2 2種策略的時間開銷比較m s

5 結束語

HDFS原有的副本放置策略在副本放置過程中會導致集群負載失衡并且影響數據讀寫效率，針對以上問題，本文利用SVM提出了一種改進的副本放置策略SRPM。首先SRPM對集群中的每個節點服務器的負載、磁盤轉速、CPU性能等硬件信息以及節點網絡距離進行特征提取，然后SRPM利用提取的特征值將節點分類，最后SRPM在較優一類節點中選取適合放置副本的節點，實驗結果證明，改進的策略模型可更好地實現負載均衡。下一步工作是進一步改進節點尋優方式，以減少其時間消耗。

［1］ Dean J，Ghemawat S.M ap Reduce：Simplified Data Processing on Large Clusters［J］.Communications of ACM，2008，51（1）：107-113.

［2］ Ghem awat S，Gobioff H，Leung S.The Google File System［J］.ACM SIGOPS Operating System s Review，2003，37（5）：29-43.

［3］ Shvachko K，Shvachko K，Kuang H，et al.The Hadoop Distributed File System［Z］.2010.

［4］ Eltabakh M Y，Tian Yuanyuan，Ozcan F，et al. CoHadoop：Flexible Data Placement and Its Exploitation in Hadoop［J］.Proceedings of VLDB Endow，2011，4（9）：575-585.

［5］ Khaneghah E M，Mirtaheri S L，Grandinetti L，et al.A Dynamic Replication Mechanism to Reduce Responsetime of I/O Operations in High Performance Computing Clusters［C］//Proceedings of International Conference on Social Computing.Berlin，Germ any：Springer，2013：110-130.

［6］ Kala K A.A Review on Hadoop-HDFS Infrastructure Extensions［C］//Proceedings of IEEE Conference on Information&Communication Technologies.Washington D.C.，USA：IEEE Press，2013：132-137.

［7］ Azzedin F.Towards a Scalable HDFS Architecture［Z］. 2013.

［8］ 丁世飛，齊丙娟，譚紅艷.支持向量機理論與算法研究綜述［J］.電子科技大學學報，2011，40（1）：2-10.

［9］ 范昕煒.支持向量機算法的研究及其應用［D］.杭州：浙江大學，2003.

［10］ 文益民，王耀南，呂寶糧，等.支持向量機處理大規模問題算法綜述［J］.計算機科學，2009，36（7）：20-25.

［11］ 李紅蓮，王春花，袁保宗，等.針對大規模訓練集的支持向量機的學習策略［J］.計算機學報，2004，26（5）：715-719.

［12］ Fan Rongen，Chang Kaiwei，Hsieh C，et al.LIBLINEAR：A Library for Large Linear Classifica-tion［J］.Journal of Machine Learning Research，2008，9（8）：1871-1874.

編輯 顧逸斐

Im p roved Strategy of HDFS Replica Placement Based on Support Vector Machine

LUO Jun，CHEN Shiqiang
（College of Computing Science，Chongqing University，Chongqing 400044，China）

A multiple copies of a rack awareness placement strategy is adopted in the Hadoop Distributed File System（HDFS）to cope with the storage of very large scale data and improve the fault tolerance.However，the HDFS does not consider the difference of each node server，which can result in load imbalance of clusters.Meanwhile，HDFS chooses remote rack node to place replica randomly，which may lead to a long distance between nodes，so that the transmission of data between nodes consumes a lot of time.To solve the aforementioned problems，this paper proposes an improved strategy of HDFS replica placement based on SVM.It can find the best node for replica by considering the disk utilization of each node，the node's hardware performance and network distance of nodes.Experimental results show that the proposed strategy effectively improves the load balancing in HDFS compared with the existing method used in HDFS system.

Support Vector Machine（SVM）；cloud storage；replica placement policy；Distributed File System（DFS）；load balancing；rack awareness

羅 軍，陳仕強.基于支持向量機的HDFS副本放置改進策略［J］.計算機工程，2015，41（11）：114-119.

英文引用格式：Luo Jun，Chen Shiqiang.Improved Strategy of HDFS Replica Placement Based on Support Vector Machine［J］.Computing Engineering，2015，41（11）：114-119.

1000-3428（2015）11-0114-06

A

TP301.6

10.3969/j.issn.1000-3428.2015.11.020

羅 軍（1961-），男，副教授、碩士，主研方向：數據庫技術，系統建模及設計；陳仕強，碩士研究生。

2014-07-21

2014-11-12 E-m ail：chensqs@foxmail.com