基于KNN的HDFS副本放置策略研究

史愛武，張煜

（武漢紡織大學(xué)數(shù)學(xué)與計(jì)算機(jī)學(xué)院，武漢430200）

0 引言

由于本世紀(jì)信息化的蓬勃發(fā)展，互聯(lián)網(wǎng)上的數(shù)據(jù)呈爆炸式增長(zhǎng)，信息化迎來(lái)了第三次浪潮[1]。面對(duì)海量的文件數(shù)據(jù)，一個(gè)好的文件系統(tǒng)是支持大數(shù)據(jù)應(yīng)用的基礎(chǔ)。Hadoop作為GFS的開源實(shí)現(xiàn)，由于其強(qiáng)大的影響力在大數(shù)據(jù)行業(yè)的應(yīng)用越來(lái)越廣泛。Hadoop由許多元素組成，它的底層文件系統(tǒng)是HDFS，配合上層的MapReduce并行計(jì)算引擎，可以完成海量數(shù)據(jù)的并行計(jì)算。考慮到集群是由廉價(jià)設(shè)備組成，節(jié)點(diǎn)發(fā)生故障被認(rèn)為是常態(tài)。為此HDFS采用了在多個(gè)節(jié)點(diǎn)上存放副本的方式，來(lái)保障系統(tǒng)的容錯(cuò)性和高可用性[2]。若選擇的節(jié)點(diǎn)是集群上的一個(gè)子集，會(huì)導(dǎo)致新的更可能被引用的副本數(shù)據(jù)過于集中，降低了集群的可用性。若選擇的節(jié)點(diǎn)負(fù)載過高，又會(huì)影響文件的寫入速度。因此，副本的放置策略成為了一項(xiàng)值得研究的課題。

1 HDFS副本策略相關(guān)研究

HDFS集群是一個(gè)主/從體系結(jié)構(gòu)，由名稱節(jié)點(diǎn)以及眾多的數(shù)據(jù)節(jié)點(diǎn)組成[3]。名稱節(jié)點(diǎn)作為主節(jié)點(diǎn)負(fù)責(zé)存儲(chǔ)系統(tǒng)的名稱空間，數(shù)據(jù)節(jié)點(diǎn)則存儲(chǔ)系統(tǒng)的文件副本。當(dāng)客戶端上傳文件到集群中時(shí)，首先向名稱節(jié)點(diǎn)發(fā)送上傳請(qǐng)求。名稱節(jié)點(diǎn)同意上傳后，客戶端請(qǐng)求上傳文件的第一個(gè)Block。名稱節(jié)點(diǎn)根據(jù)副本放置策略選出滿足條件的副本放置節(jié)點(diǎn)，返回給客戶端。客戶端請(qǐng)求第一個(gè)節(jié)點(diǎn)上傳數(shù)據(jù)，節(jié)點(diǎn)依次跟后面的節(jié)點(diǎn)建立通信管道。數(shù)據(jù)沿著管道依次上傳，第一個(gè)Block上傳完成后，客戶端繼續(xù)請(qǐng)求上傳第二個(gè)block，直到文件的最后一個(gè)Block上傳完成。

HDFS具有機(jī)架感知功能，可以告知機(jī)器屬于哪個(gè)機(jī)架。機(jī)架感知的功能是通過編寫一個(gè)腳本，根據(jù)IP地址進(jìn)行計(jì)算實(shí)現(xiàn)的。機(jī)架感知可以感知集群的拓?fù)浣Y(jié)構(gòu)，從而計(jì)算兩個(gè)節(jié)點(diǎn)的距離，為副本放置位置的選擇提供依據(jù)。

名稱節(jié)點(diǎn)在選擇副本放置位置時(shí)，有一些前提需要滿足。首先，同一個(gè)Block在一個(gè)數(shù)據(jù)節(jié)點(diǎn)上的副本數(shù)不應(yīng)大于1。同時(shí)，同一個(gè)Block在一個(gè)機(jī)架上的副本數(shù)不大于2。以上這些前提，都是為了防止新的更有可能被引用的數(shù)據(jù)被放在集群的一個(gè)子集上。

在2.x版本的Hadoop中，HDFS的默認(rèn)副本放置策略如下所述。如果客戶端位于數(shù)據(jù)節(jié)點(diǎn)上，則將第一個(gè)副本放置在本地計(jì)算機(jī)上，否則放置在一個(gè)隨機(jī)的數(shù)據(jù)節(jié)點(diǎn)。第二個(gè)副本放在另一個(gè)機(jī)架上的數(shù)據(jù)節(jié)點(diǎn)上。第三個(gè)副本放置在不同于第二個(gè)副本所在機(jī)架的另一個(gè)機(jī)架的數(shù)據(jù)節(jié)點(diǎn)上。其流程如圖1所示。

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

2 優(yōu)化的副本放置策略

2.1 存在的問題及改進(jìn)思路

HDFS的默認(rèn)副本放置策略較為簡(jiǎn)單，只在一定程度上兼顧了副本的本地性和容錯(cuò)性。由于選取節(jié)點(diǎn)具有隨機(jī)性，若隨機(jī)選擇的節(jié)點(diǎn)負(fù)載過重，會(huì)影響HDFS的文件寫入速度，不利于集群的負(fù)載均衡。為了解決Hadoop在放置副本時(shí)的負(fù)載均衡問題，趙磊等人[4]提出了一種負(fù)載量化模型，選擇低負(fù)載的節(jié)點(diǎn)放置副本。陳仕強(qiáng)等人[5]提出了SRPM模型，可以考慮各節(jié)點(diǎn)服務(wù)器的差異性，選出合適的副本放置節(jié)點(diǎn)。袁麗娜[6]提出了一種基于性能的副本負(fù)載均衡改進(jìn)策略，通過自定義的負(fù)載能力模型對(duì)節(jié)點(diǎn)負(fù)載進(jìn)行評(píng)估。

以上負(fù)載模型雖然權(quán)重計(jì)算方式不一樣，但都屬于線性模型，無(wú)法發(fā)現(xiàn)組合特征與負(fù)載的關(guān)系。為改善這一問題，提出了一種基于KNN的副本放置策略模型KRPM（KNN Replica Placement Model）。該策略中，選用CPU使用率、內(nèi)存使用率、磁盤使用率、磁盤I/O使用率和網(wǎng)絡(luò)帶寬使用率這5個(gè)特征，通過使用訓(xùn)練的KNN回歸模型，對(duì)節(jié)點(diǎn)的寫入速度進(jìn)行預(yù)測(cè)。若隨機(jī)選擇的節(jié)點(diǎn)預(yù)測(cè)值小于集群的平均值，則重新隨機(jī)選擇，直到選擇到符合條件的數(shù)據(jù)節(jié)點(diǎn)。

2.2 文件寫入性能衡量指標(biāo)

為了找到符合條件的數(shù)據(jù)節(jié)點(diǎn)，需要通過數(shù)據(jù)節(jié)點(diǎn)的一些性能衡量指標(biāo)對(duì)節(jié)點(diǎn)的寫入速度進(jìn)行預(yù)測(cè)。通常來(lái)說(shuō)，機(jī)器的寫入速度會(huì)受到CPU、內(nèi)存、硬盤、網(wǎng)絡(luò)等方面的影響。本文選取以下五個(gè)指標(biāo)作為評(píng)估節(jié)點(diǎn)寫入速度的特征：

（1）CPU使用率。節(jié)點(diǎn)的CPU使用率的高低，可以反映機(jī)器運(yùn)行程序的負(fù)載程度。機(jī)器的CPU使用率越高，說(shuō)明機(jī)器上執(zhí)行的任務(wù)越多，對(duì)放置新副本的速度也會(huì)有負(fù)面影響。這里使用P1來(lái)代表節(jié)點(diǎn)的CPU使用率。

（2）內(nèi)存使用率。程序運(yùn)行需要將代碼和數(shù)據(jù)放入內(nèi)存，內(nèi)存的使用率也能反映機(jī)器的負(fù)載程度。數(shù)據(jù)塊在以管道方式傳到節(jié)點(diǎn)上的過程中，是分為一個(gè)個(gè)Packet傳輸?shù)?，每個(gè)Packet會(huì)先存入內(nèi)存再寫入硬盤。因此，內(nèi)存使用率也可以影響副本的放置速度。

（3）磁盤使用率。副本是需要寫入到硬盤中的，當(dāng)磁盤空間使用率不高時(shí)，幾乎不影響文件的寫入速度。而當(dāng)磁盤空間使用率過高，既容易對(duì)集群的負(fù)載均衡造成影響，也會(huì)很大程度上影響副本放置速度。

（4）磁盤I/O使用率。當(dāng)磁盤I/O較高，說(shuō)明磁盤已經(jīng)在進(jìn)行大量的讀寫操作了。若此時(shí)再將副本放置在該節(jié)點(diǎn)上，會(huì)極大程度影響數(shù)據(jù)塊的寫入速度。因此，磁盤I/O使用率是影響副本放置速度的很大一個(gè)因素。

（5）網(wǎng)絡(luò)帶寬使用率。數(shù)據(jù)塊在節(jié)點(diǎn)中的傳輸是通過網(wǎng)絡(luò)完成的，節(jié)點(diǎn)網(wǎng)絡(luò)負(fù)載較大會(huì)影響數(shù)據(jù)的傳輸，降低文件寫入速度。

2.3 KNN回歸模型

KNN（K-Nearest Neighbor）法即K最鄰近法，最初由Cover和Hart于1968年提出，是一個(gè)理論上比較成熟的方法，也是最簡(jiǎn)單的機(jī)器學(xué)習(xí)算法之一[7]。該方法的思路非常簡(jiǎn)單直觀：如果一個(gè)樣本在特征空間中的K個(gè)最相似（即特征空間中最鄰近）的樣本中的大多數(shù)屬于某一個(gè)類別，則該樣本也屬于這個(gè)類別。因此，它的核心思想是，如果一個(gè)樣本在特征空間中的K個(gè)最相鄰的樣本中的大多數(shù)屬于某一個(gè)類別，則該樣本也屬于這個(gè)類別，并具有這個(gè)類別上樣本的特性。KNN算法不僅可以用于分類，還可以用于回歸。通過找出一個(gè)樣本的k個(gè)最近鄰居，將這些鄰居的某個(gè)（些）屬性的平均值賦給該樣本，就可以得到該樣本對(duì)應(yīng)屬性的值。

KNN方法思路簡(jiǎn)單，易于理解，易于實(shí)現(xiàn)，無(wú)需估計(jì)參數(shù)。該算法的一個(gè)不足之處是計(jì)算量較大，因?yàn)閷?duì)每一個(gè)待分類的文本都要計(jì)算它到全體已知樣本的距離，才能求得它的K個(gè)最近鄰點(diǎn)。為了提高副本放置策略的放置效率，需要模型具有相對(duì)快的計(jì)算速度。KNN方法易于實(shí)現(xiàn)，且用來(lái)評(píng)估的特征只有5個(gè)，可以滿足快速評(píng)估的需求。模型的調(diào)優(yōu)過程如圖2所示。

圖2 模型調(diào)優(yōu)流程

使用Hadoop基準(zhǔn)測(cè)試工具生成數(shù)據(jù)集，按照4:1的比例隨機(jī)分成訓(xùn)練集和測(cè)試集。P1-P5分別代表CPU使用率、內(nèi)存使用率、磁盤使用率、磁盤I/O使用率和網(wǎng)絡(luò)帶寬使用率，S代表副本放置速度（Mb/s）。樣本坐標(biāo)格式如（P1，P2，P3，P4，P5，S）。使用歐氏距離來(lái)計(jì)算待預(yù)測(cè)特征與訓(xùn)練樣本特征間的距離，即：

在根據(jù)一組數(shù)據(jù)的特征（P1，P2，P3，P4，P5）計(jì)算預(yù)測(cè)值S時(shí)，先計(jì)算其與所有訓(xùn)練樣本的距離d。將結(jié)果按照升序排序，并取出距離最小的前K個(gè)，計(jì)算它們S值的平均值，作為預(yù)測(cè)值。

分別取K=1到K=20，對(duì)測(cè)試集所有樣本進(jìn)行評(píng)估，并計(jì)算誤差。采用均方誤差作為誤差評(píng)估指標(biāo)，誤差越小，說(shuō)明預(yù)測(cè)效果越好。

針對(duì)K的不同取值，使用交叉驗(yàn)證的方式獲取平均誤差。得出當(dāng)K=6時(shí)，獲得最小均方誤差。

2.4 新的副本放置策略

從第1節(jié)的分析可以得知，默認(rèn)的副本放置策略可能會(huì)選擇到負(fù)載較高的節(jié)點(diǎn)，影響副本的寫入效率。通過KNN回歸模型，系統(tǒng)可以對(duì)節(jié)點(diǎn)副本放置速度進(jìn)行預(yù)測(cè)。在新的副本放置策略中，名稱節(jié)點(diǎn)首先依舊隨機(jī)選擇一個(gè)數(shù)據(jù)節(jié)點(diǎn)，再使用預(yù)測(cè)模型對(duì)該節(jié)點(diǎn)的副本寫入速度進(jìn)行預(yù)測(cè)。若其寫入速度低于集群平均值，繼續(xù)比對(duì)下一個(gè)節(jié)點(diǎn)，直到選擇的節(jié)點(diǎn)滿足要求，副本放置節(jié)點(diǎn)選擇完成。流程如圖3所示。

圖3 基于KNN的放置策略

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

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

為了驗(yàn)證新的副本放置策略的效果，設(shè)計(jì)實(shí)驗(yàn)進(jìn)行驗(yàn)證。實(shí)驗(yàn)通過虛擬機(jī)搭建3個(gè)機(jī)架，每個(gè)機(jī)架3個(gè)節(jié)點(diǎn)。節(jié)點(diǎn)安裝CentOS 7操作系統(tǒng)，系統(tǒng)安裝Ha?doop 2.7.2。集群配置及環(huán)境如表1所示。

表1 Hadoop集群配置

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

由于策略在放置副本時(shí)考慮了節(jié)點(diǎn)的文件寫入速度，所以在統(tǒng)計(jì)集群寫入性能前，先讓集群部分節(jié)點(diǎn)開始執(zhí)行排序任務(wù)。Hadoop自帶有測(cè)試程序測(cè)試集群性能。TeraSort是測(cè)試Hadoop的一個(gè)有效的排序程序。實(shí)驗(yàn)數(shù)據(jù)由程序中的TeraGen程序生成，之后由Tera?Sort對(duì)數(shù)據(jù)排序。TestDFSIO主要用于測(cè)試集群的I/O性能。

先使用TeraGen生成數(shù)據(jù)，再使用TeraSort使集群進(jìn)入負(fù)載狀態(tài)，同時(shí)使用TestDFSIO測(cè)試HDFS寫性能。實(shí)驗(yàn)進(jìn)行三次，相比默認(rèn)放置策略，實(shí)驗(yàn)結(jié)果如圖4和圖5所示。

圖4 TestDFSIO寫任務(wù)執(zhí)行時(shí)間

圖5 TeraSort任務(wù)執(zhí)行時(shí)間

由上圖可知，在TestDFSIO測(cè)試中，改進(jìn)策略的文件寫入時(shí)間少于默認(rèn)策略。在TeraSort測(cè)試中，改進(jìn)策略的排序性能也較默認(rèn)策略優(yōu)秀。實(shí)驗(yàn)結(jié)果說(shuō)明改進(jìn)的策略在副本放置效率上優(yōu)于默認(rèn)的放置策略，可以提高集群的文件寫入性能。并且改進(jìn)后的策略在執(zhí)行排序任務(wù)的效率上也較默認(rèn)策略高，說(shuō)明它對(duì)系統(tǒng)的負(fù)載均衡也起到了正面作用。

4 結(jié)語(yǔ)

本文分析了Hadoop默認(rèn)放置策略，并針對(duì)默認(rèn)策略在選擇放置副本節(jié)點(diǎn)時(shí)，未考慮節(jié)點(diǎn)的負(fù)載問題，提出了改進(jìn)的策略。新的策略使用KNN算法來(lái)預(yù)測(cè)節(jié)點(diǎn)的寫入速度，從側(cè)面實(shí)現(xiàn)了對(duì)節(jié)點(diǎn)負(fù)載的預(yù)測(cè)。使用交叉驗(yàn)證，可以得到合理的模型參數(shù)K。實(shí)驗(yàn)證明，基于KNN的副本放置策略在集群進(jìn)行文件寫入的任務(wù)中，花費(fèi)了更短的時(shí)間。這說(shuō)明新的策略能夠較好的預(yù)測(cè)節(jié)點(diǎn)的文件寫入速度，并選擇合理的節(jié)點(diǎn)進(jìn)行副本放置，利于集群的負(fù)載均衡并提高集群性能。

新的策略是基于默認(rèn)副本放置策略的改進(jìn)，節(jié)點(diǎn)負(fù)載情況是通過節(jié)點(diǎn)文件寫入速度來(lái)反映的。然而由于磁盤空間在用盡前對(duì)文件寫入速度影響不大，因此節(jié)點(diǎn)的文件寫入速度只能反映集群的部分負(fù)載情況。當(dāng)集群副本分布不均衡時(shí)，仍需要啟動(dòng)Balancer來(lái)遷移副本完成集群的數(shù)據(jù)均衡。