基于支持向量機(jī)的HDFS副本放置改進(jìn)策略

羅 軍，陳仕強(qiáng)

（重慶大學(xué)計(jì)算機(jī)學(xué)院，重慶400044）

基于支持向量機(jī)的HDFS副本放置改進(jìn)策略

羅 軍，陳仕強(qiáng)

（重慶大學(xué)計(jì)算機(jī)學(xué)院，重慶400044）

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

支持向量機(jī)；云存儲(chǔ)；副本放置策略；分布式文件系統(tǒng)；負(fù)載均衡；機(jī)架感知

1 概述

Hadoop是一個(gè)能夠?qū)Υ罅繑?shù)據(jù)進(jìn)行分布式處理的開源軟件框架，其思想來源于Google公司的Map Reduce框架［1］，分布式數(shù)據(jù)密集的并行應(yīng)用程序利用該框架能將大的任務(wù)和數(shù)據(jù)集分解成為更小的任務(wù)和數(shù)據(jù)集，并使這些任務(wù)在不同的分區(qū)中平行處理。Hadoop利用分布式文件系統(tǒng)HDFS來存儲(chǔ)這些數(shù)據(jù)，而HDFS的設(shè)計(jì)思想來自于Google的GFS［2］。

HDFS是一種能夠運(yùn)行在大量廉價(jià)硬件上的分布式文件系統(tǒng)［3］，它不僅具有分布式文件系統(tǒng)的大量?jī)?yōu)點(diǎn)，而且還做了許多改善：具有很高的容錯(cuò)性，對(duì)硬件性能要求不高，可以實(shí)現(xiàn)高吞吐量的數(shù)據(jù)訪問，特別適合運(yùn)用在超大規(guī)模數(shù)據(jù)集上。

為了能夠應(yīng)對(duì)超大量數(shù)據(jù)的存儲(chǔ)和提供較好的容錯(cuò)性能，分布式文件系統(tǒng)需要采用多副本策略，而且需要將多個(gè)副本分布在集群中的不同位置上，但如果副本放置的方式不當(dāng)將會(huì)極大影響系統(tǒng)的負(fù)載均衡，從而導(dǎo)致系統(tǒng)運(yùn)行效率低下。HDFS采用一種機(jī)架感知的策略來放置副本，默認(rèn)的副本數(shù)為3個(gè)。在放置多個(gè)副本時(shí)這種策略采用隨機(jī)的方式，會(huì)使整個(gè)集群負(fù)載失衡，文獻(xiàn)［4］利用數(shù)據(jù)在邏輯上的相關(guān)性，將HDFS改裝成應(yīng)用層可以自行控制數(shù)據(jù)要存放的節(jié)點(diǎn)集，使具有邏輯相關(guān)性的數(shù)據(jù)副本可以存在相同的幾個(gè)節(jié)點(diǎn)上，提升了對(duì)節(jié)點(diǎn)數(shù)據(jù)和副本的管理效率。文獻(xiàn)［5］提出一種根據(jù)節(jié)點(diǎn)文件訪問熱度來動(dòng)態(tài)調(diào)節(jié)其相應(yīng)的副本數(shù)，并且將集群的剩余空間也作為調(diào)節(jié)副本數(shù)的一項(xiàng)評(píng)價(jià)指標(biāo)。

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

2 HDFS架構(gòu)及其副本放置策略

2.1 原有副本放置策略

在分布式的文件系統(tǒng)架構(gòu)中，為了提高整個(gè)集群的性能，通常會(huì)將元數(shù)據(jù)與數(shù)據(jù)分離，以實(shí)現(xiàn)對(duì)元數(shù)據(jù)和數(shù)據(jù)的高效管理，其中元數(shù)據(jù)節(jié)點(diǎn)的職責(zé)是管理文件系統(tǒng)命名空間和文件的各種屬性，數(shù)據(jù)節(jié)點(diǎn)的職責(zé)是負(fù)責(zé)管理文件上的具體數(shù)據(jù)，并且直接處理來自客戶端的文件讀寫請(qǐng)求，HDFS采用了主從式的分布式架構(gòu)，圖1展示了HDFS的架構(gòu)。

圖1 HDFS架構(gòu)

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

由于元數(shù)據(jù)與數(shù)據(jù)的管理是分離的，因此對(duì)文件數(shù)據(jù)的讀寫操作并不需要通過元數(shù)據(jù)節(jié)點(diǎn)，這樣就提高了文件的讀寫效率。圖2為HDFS中文件的寫入過程。

圖2 HDFS文件寫入過程

當(dāng)有文件要寫入時(shí)，HDFS客戶端將請(qǐng)求發(fā)給名字節(jié)點(diǎn)，名字節(jié)點(diǎn)接收到請(qǐng)求時(shí)會(huì)先檢查文件是否已經(jīng)存在，若不存在還需要檢查相關(guān)權(quán)限，如果成功則為這個(gè)請(qǐng)求的文件創(chuàng)建一個(gè)記錄?？蛻舳嗽趯懭胛募r(shí)，最初是將數(shù)據(jù)寫入到本地的臨時(shí)文件中，如果數(shù)據(jù)大小達(dá)到一個(gè)塊的大小時(shí)，客戶端便從名字節(jié)點(diǎn)得到一個(gè)有許多數(shù)據(jù)節(jié)點(diǎn)的列表，這些數(shù)據(jù)節(jié)點(diǎn)是用來存放副本的，接收數(shù)據(jù)是從第1個(gè)數(shù)據(jù)節(jié)點(diǎn)開始一部分一部分接收，并且在將這部分?jǐn)?shù)據(jù)寫入的同時(shí)，還將這些數(shù)據(jù)傳給第2個(gè)數(shù)據(jù)節(jié)點(diǎn)，第2個(gè)數(shù)據(jù)節(jié)點(diǎn)也和第1個(gè)數(shù)據(jù)節(jié)點(diǎn)一樣開始寫入數(shù)據(jù)的同時(shí)并將數(shù)據(jù)傳給下一個(gè)節(jié)點(diǎn)，這種操作是以流水線的方式完成的［7］。

HDFS采用一種機(jī)架感知策略來組織集群，通過機(jī)架感知，名字節(jié)點(diǎn)可以獲得所有數(shù)據(jù)節(jié)點(diǎn)的網(wǎng)絡(luò)拓?fù)鋱D，同一個(gè)機(jī)架上的節(jié)點(diǎn)之間的網(wǎng)絡(luò)狀況比不同機(jī)架的要理想。HDFS設(shè)法將副本保存在同一機(jī)架和不同機(jī)架中，其中保存在同一機(jī)架中能夠減少網(wǎng)絡(luò)傳輸開銷，而放在不同機(jī)架中能提高數(shù)據(jù)安全性。HDFS默認(rèn)采用的副本數(shù)為3，其存儲(chǔ)結(jié)構(gòu)如圖3所示。

圖3 HDFS默認(rèn)數(shù)據(jù)放置策略

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

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

雖然HDFS原有的副本放置策略簡(jiǎn)單快捷，提高了整個(gè)集群的容錯(cuò)性，但是這種策略在存放副本的時(shí)候沒有綜合考慮節(jié)點(diǎn)負(fù)載情況、節(jié)點(diǎn)硬件性能、節(jié)點(diǎn)網(wǎng)絡(luò)距離等因素，容易出現(xiàn)負(fù)載失衡。仍然有許多需要改進(jìn)的地方：

（1）在選擇副本放置節(jié)點(diǎn)時(shí)沒有考慮節(jié)點(diǎn)的空間利用率，雖然HDFS提供了一個(gè)負(fù)載均衡的工具Balancer，它能夠?qū)⒇?fù)載較多的節(jié)點(diǎn)上的數(shù)據(jù)轉(zhuǎn)移到負(fù)載較少的節(jié)點(diǎn)上，不過這個(gè)工具是在副本已經(jīng)放置后手動(dòng)觸發(fā)的，所以并沒有從源頭上減少集群負(fù)載失衡的發(fā)生，而且Balancer在平衡負(fù)載的過程中還浪費(fèi)了大量網(wǎng)絡(luò)傳輸時(shí)間和網(wǎng)絡(luò)帶寬。

（2）沒有考慮節(jié)點(diǎn)服務(wù)器的硬件性能，在集群中不同節(jié)點(diǎn)的機(jī)器是異構(gòu)的，在具有相同負(fù)載的情況下，其對(duì)數(shù)據(jù)的讀寫速率是不一樣的。

（3）沒有考慮節(jié)點(diǎn)之間的網(wǎng)絡(luò)距離，在將副本放置到不同節(jié)點(diǎn)時(shí)，距離越遠(yuǎn)的節(jié)點(diǎn)需要的傳輸時(shí)間越長(zhǎng)。

3 改進(jìn)的副本放置策略

3.1 基本思想

HDFS在副本放置過程中沒有綜合考慮各節(jié)點(diǎn)服務(wù)器的差異性，這會(huì)導(dǎo)致集群出現(xiàn)負(fù)載失衡。而HDFS在選擇遠(yuǎn)程機(jī)架節(jié)點(diǎn)放置副本時(shí)采用隨機(jī)方式，這有可能導(dǎo)致節(jié)點(diǎn)之間的網(wǎng)絡(luò)距離過長(zhǎng)，使得在節(jié)點(diǎn)之間傳輸數(shù)據(jù)會(huì)消耗大量時(shí)間。針對(duì)以上問題，SRPM采用SVM解決。

首先SRPM對(duì)集群中的每個(gè)節(jié)點(diǎn)服務(wù)器的負(fù)載、磁盤轉(zhuǎn)速、CPU性能等硬件信息以及節(jié)點(diǎn)網(wǎng)絡(luò)距離進(jìn)行特征提取。

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

3.2 問題描述

SVM是建立在統(tǒng)計(jì)學(xué)習(xí)理論基礎(chǔ)上的一種數(shù)據(jù)挖掘方法，能非常成功地處理回歸問題（時(shí)間序列分析）和模式識(shí)別（分類問題、判別分析）等諸多問題［8］。SVM是通過尋找一種結(jié)構(gòu)化風(fēng)險(xiǎn)最小的方式進(jìn)行學(xué)習(xí)分類的，即使在樣本很少的情況下也能達(dá)到較好的分類效果［9］。

根據(jù)HDFS集群的特點(diǎn)，可以用一個(gè)有向圖G=（V，E，ψ）來表示HDFS集群，其中，頂點(diǎn)vi∈V表示HDFS集群中的節(jié)點(diǎn)；邊ei∈E表示節(jié)點(diǎn)中副本的流向；ψ（e）=（u，v）表示節(jié)點(diǎn)u上的數(shù)據(jù)在節(jié)點(diǎn)v上保存有副本；ψ（e）的值表示（u，v）之間的網(wǎng)絡(luò)距離，節(jié)點(diǎn)連線箭頭由u指向v。

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

但是傳統(tǒng)的SVM在對(duì)大規(guī)模的數(shù)據(jù)集進(jìn)行處理時(shí)需要消耗大量時(shí)間［9］，這是因?yàn)樵赟VM的算法中需要處理二次規(guī)劃問題，當(dāng)訓(xùn)練規(guī)模過于龐大的時(shí)候會(huì)導(dǎo)致求解時(shí)間過長(zhǎng)［10］。

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

本文采用了LIBLINEAR，一種繼承自LIBSVM能夠?qū)Υ笠?guī)模數(shù)據(jù)進(jìn)行線性分類的工具，實(shí)驗(yàn)表明LIBLINEAR的訓(xùn)練速度非?？欤鐚?duì)于一個(gè)6× 105條的數(shù)據(jù)訓(xùn)練只需要幾秒鐘，而用常規(guī)的LIBSVM則需要幾個(gè)小時(shí)［12］。

3.3 節(jié)點(diǎn)特征選取

在整個(gè)分布式集群中，文件的讀寫效率會(huì)受到多種因素的影響，如節(jié)點(diǎn)服務(wù)器中磁盤的讀寫速度、CPU性能、內(nèi)存大小以及節(jié)點(diǎn)之間的網(wǎng)絡(luò)距離都會(huì)影響到數(shù)據(jù)的讀寫速率，所以如果數(shù)據(jù)副本放置過程中沒有綜合考慮這些因素將會(huì)導(dǎo)致嚴(yán)重的負(fù)載失衡問題，本文將從以下5個(gè)因素提取特征：

（1）相對(duì)負(fù)載率

在數(shù)據(jù)寫的過程中，數(shù)據(jù)節(jié)點(diǎn)的磁盤利用率是影響整個(gè)集群負(fù)載均衡的重要因素之一，這是因?yàn)檎麄€(gè)集群是建立在大量廉價(jià)設(shè)備上，不同的數(shù)據(jù)節(jié)點(diǎn)有著不同的磁盤容量，所以對(duì)于不同的節(jié)點(diǎn)應(yīng)該區(qū)別對(duì)待，對(duì)于磁盤容量大的數(shù)據(jù)節(jié)點(diǎn)應(yīng)該存儲(chǔ)更多的數(shù)據(jù)，而較小的只需要存儲(chǔ)較小的數(shù)據(jù)即可，針對(duì)集群里節(jié)點(diǎn)之間的差異性，可以用相對(duì)負(fù)載來衡量：

其中，λDNi為節(jié)點(diǎn)相對(duì)負(fù)載，當(dāng)λDNi＞1時(shí)表示節(jié)點(diǎn)的負(fù)載率大于整個(gè)集群的平均負(fù)載率，當(dāng)λDNi＜1時(shí)表示節(jié)點(diǎn)的負(fù)載率小于整個(gè)集群的平均負(fù)載率；P（DNi）表示節(jié)點(diǎn)的負(fù)載率：

其中，DNi（use）表示節(jié)點(diǎn)已使用的磁盤容量；DNi（total）表示節(jié)點(diǎn)的磁盤總?cè)萘浚?jié)點(diǎn)的磁盤總?cè)萘繛橐粋€(gè)固定值，單位為GB。

P（DNaverage）表示整個(gè)集群的平均負(fù)載率：

其中，n為整個(gè)集群的數(shù)據(jù)節(jié)點(diǎn)數(shù)。

（2）網(wǎng)絡(luò)距離

節(jié)點(diǎn)網(wǎng)絡(luò)距離表示存放數(shù)據(jù)的節(jié)點(diǎn)與要存放該數(shù)據(jù)副本節(jié)點(diǎn)之間的網(wǎng)絡(luò)拓?fù)渚嚯x，網(wǎng)絡(luò)距離的大小會(huì)對(duì)數(shù)據(jù)的讀寫時(shí)間造成很大的影響。如果網(wǎng)絡(luò)距離過長(zhǎng)，那么數(shù)據(jù)的讀寫時(shí)間也就會(huì)變得很長(zhǎng)，本文中在同一機(jī)架中節(jié)點(diǎn)之間的網(wǎng)絡(luò)距離為0，節(jié)點(diǎn)網(wǎng)絡(luò)距離可用以下公式表示：

其中，L（DNij）表示節(jié)點(diǎn)i和節(jié)點(diǎn)j的網(wǎng)絡(luò)距離；NetLength（DNi，DNj）表示節(jié)點(diǎn)i和節(jié)點(diǎn)j所在機(jī)架之間的網(wǎng)絡(luò)拓?fù)渚嚯x，即兩機(jī)架之間的交換機(jī)或路由器數(shù)目。

（3）磁盤性能

節(jié)點(diǎn)服務(wù)器磁盤性能也是影響集群節(jié)點(diǎn)文件讀寫快慢的重要因素之一，磁盤性能指標(biāo)可以用以下公式表示：

其中，D（DNi）表示節(jié)點(diǎn)服務(wù)器磁盤的量化性能值；Size表示磁盤容量；R表示磁盤轉(zhuǎn)速；Cache表示緩存大?。籚data表示磁盤的數(shù)據(jù)傳輸率；表示平均尋道時(shí)間，即磁盤磁頭移動(dòng)到數(shù)據(jù)所在磁道時(shí)所用的時(shí)間。

（4）CPU性能

CPU的性能在很大程度上決定了計(jì)算機(jī)的性能，衡量CPU性能指標(biāo)有多個(gè)，可以用以下公式來衡量：

其中，W（DNi）表示CPU的量化性能值；f表示CPU的主頻；Cache表示CPU的緩存大?。籒UM表示CPU的核心數(shù)量；Vbus表示CPU的總線速度。

（5）內(nèi)存

對(duì)于經(jīng)常被訪問的數(shù)據(jù)，節(jié)點(diǎn)可以把這些數(shù)據(jù)放入內(nèi)存中，這樣能顯著提高數(shù)據(jù)的訪問速度。因此，節(jié)點(diǎn)內(nèi)存的大小對(duì)負(fù)載均衡的效果也有顯著影響。衡量?jī)?nèi)存性能采用下式：

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

3.4 算法描述

算法思想：假設(shè)副本數(shù)為3，用SVM將各節(jié)點(diǎn)服務(wù)器依據(jù)各節(jié)點(diǎn)特征值分成2類：（1）適合放置副本的節(jié)點(diǎn)；（2）不適合放置副本的節(jié)點(diǎn)。在適合放置副本的節(jié)點(diǎn)中選一個(gè)節(jié)點(diǎn)作為副本放置的最佳節(jié)點(diǎn)。

輸入 各節(jié)點(diǎn)服務(wù)器提取的特征值

輸出 可以放置副本的最佳節(jié)點(diǎn)

算法偽代碼如下：

4 實(shí)驗(yàn)與結(jié)果分析

4.1 改進(jìn)策略的具體實(shí)現(xiàn)

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

4.2 實(shí)驗(yàn)環(huán)境

為了驗(yàn)證改進(jìn)的副本放置策略模型的有效性，在Hadoop1.1.2集群上進(jìn)行了改進(jìn)策略模型的相關(guān)實(shí)驗(yàn)，并與HDFS原有的副本放置策略模型做了比較。實(shí)驗(yàn)操作系統(tǒng)采用CentOs6.4，JDK采用jdk1.6，通過虛擬機(jī)搭建了4個(gè)機(jī)架，每個(gè)機(jī)架5個(gè)節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)的容量為20 GB，在Hadoop集群中網(wǎng)絡(luò)為樹形拓?fù)浣Y(jié)構(gòu)，其中葉節(jié)點(diǎn)為節(jié)點(diǎn)服務(wù)器，非葉節(jié)點(diǎn)為路由器或交換機(jī)。在該樹形拓?fù)浣Y(jié)構(gòu)中子節(jié)點(diǎn)到父節(jié)點(diǎn)的網(wǎng)絡(luò)距離為1，兩節(jié)點(diǎn)服務(wù)器的網(wǎng)絡(luò)距離為這兩節(jié)點(diǎn)到其最近公共祖先節(jié)點(diǎn)的距離之和，其網(wǎng)絡(luò)拓?fù)渚嚯x如表1所示。

表1 Hadoop集群的網(wǎng)絡(luò)拓?fù)渚嚯x

4.3 性能分析

在實(shí)驗(yàn)中，為了驗(yàn)證改進(jìn)策略在網(wǎng)絡(luò)距離上的效果，首先只在機(jī)架1中的節(jié)點(diǎn)1提交數(shù)據(jù)，該數(shù)據(jù)共有200塊，其中每塊大小為64 MB，集群默認(rèn)的副本數(shù)為3，該提交數(shù)據(jù)存放在非機(jī)架1上的副本塊數(shù)為200，而在機(jī)架1上的副本塊數(shù)為400。假設(shè)初始時(shí)各節(jié)點(diǎn)都是空載狀態(tài)。

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

圖4 原有策略下數(shù)據(jù)塊副本在本地機(jī)架的分布

圖5 原有策略下數(shù)據(jù)塊副本在遠(yuǎn)端機(jī)架的分布

圖6 改進(jìn)策略下數(shù)據(jù)塊副本在本地機(jī)架的分布

圖7 改進(jìn)策略下數(shù)據(jù)塊副本在遠(yuǎn)端機(jī)架的分布

由于改進(jìn)的副本放置策略考慮了網(wǎng)絡(luò)距離的影響，因此在放置副本時(shí)如果各節(jié)點(diǎn)負(fù)載相差不大的情況下改進(jìn)的副本放置策略模型會(huì)優(yōu)先考慮網(wǎng)絡(luò)距離較近的機(jī)架上的節(jié)點(diǎn)。在本實(shí)驗(yàn)中，改進(jìn)的副本放置策略相比于HDFS原有的副本放置策略其平均距離縮短了17.3%。

在比較了網(wǎng)絡(luò)距離的效果后，為了驗(yàn)證節(jié)點(diǎn)硬件性能對(duì)集群負(fù)載的效果，分別在4個(gè)機(jī)架上的一個(gè)數(shù)據(jù)節(jié)點(diǎn)上提交了500個(gè)數(shù)據(jù)塊，其中每個(gè)數(shù)據(jù)塊大小都為64 MB。提交開始時(shí)，各數(shù)據(jù)節(jié)點(diǎn)都是空載狀態(tài)。

采用默認(rèn)的副本放置策略和改進(jìn)的副本放置策略的結(jié)果如圖5所示，其中縱坐標(biāo)表示每個(gè)節(jié)點(diǎn)的負(fù)載率，即每一個(gè)節(jié)點(diǎn)已使用的容量與該節(jié)點(diǎn)總的容量的比值。

從圖8中可以看出，通過4次提交數(shù)據(jù)塊后，改進(jìn)的策略模型中各節(jié)點(diǎn)的相對(duì)負(fù)載相比于原有的策略模型要均衡得多，改進(jìn)的策略模型有效改善了集群的負(fù)載均衡。

圖8 數(shù)據(jù)節(jié)點(diǎn)的負(fù)載率比較

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

表2 2種策略的時(shí)間開銷比較m s

5 結(jié)束語

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

［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ī)理論與算法研究綜述［J］.電子科技大學(xué)學(xué)報(bào)，2011，40（1）：2-10.

［9］ 范昕煒.支持向量機(jī)算法的研究及其應(yīng)用［D］.杭州：浙江大學(xué)，2003.

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

［11］ 李紅蓮，王春花，袁保宗，等.針對(duì)大規(guī)模訓(xùn)練集的支持向量機(jī)的學(xué)習(xí)策略［J］.計(jì)算機(jī)學(xué)報(bào)，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

羅 軍，陳仕強(qiáng).基于支持向量機(jī)的HDFS副本放置改進(jìn)策略［J］.計(jì)算機(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-），男，副教授、碩士，主研方向：數(shù)據(jù)庫(kù)技術(shù)，系統(tǒng)建模及設(shè)計(jì)；陳仕強(qiáng)，碩士研究生。

2014-07-21

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