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

史愛武，張煜

（武漢紡織大學數學與計算機學院，武漢430200）

0 引言

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

1 HDFS副本策略相關研究

HDFS集群是一個主/從體系結構，由名稱節點以及眾多的數據節點組成[3]。名稱節點作為主節點負責存儲系統的名稱空間，數據節點則存儲系統的文件副本。當客戶端上傳文件到集群中時，首先向名稱節點發送上傳請求。名稱節點同意上傳后，客戶端請求上傳文件的第一個Block。名稱節點根據副本放置策略選出滿足條件的副本放置節點，返回給客戶端。客戶端請求第一個節點上傳數據，節點依次跟后面的節點建立通信管道。數據沿著管道依次上傳，第一個Block上傳完成后，客戶端繼續請求上傳第二個block，直到文件的最后一個Block上傳完成。

HDFS具有機架感知功能，可以告知機器屬于哪個機架。機架感知的功能是通過編寫一個腳本，根據IP地址進行計算實現的。機架感知可以感知集群的拓撲結構，從而計算兩個節點的距離，為副本放置位置的選擇提供依據。

名稱節點在選擇副本放置位置時，有一些前提需要滿足。首先，同一個Block在一個數據節點上的副本數不應大于1。同時，同一個Block在一個機架上的副本數不大于2。以上這些前提，都是為了防止新的更有可能被引用的數據被放在集群的一個子集上。

在2.x版本的Hadoop中，HDFS的默認副本放置策略如下所述。如果客戶端位于數據節點上，則將第一個副本放置在本地計算機上，否則放置在一個隨機的數據節點。第二個副本放在另一個機架上的數據節點上。第三個副本放置在不同于第二個副本所在機架的另一個機架的數據節點上。其流程如圖1所示。

圖1 HDFS的默認副本放置策略

2 優化的副本放置策略

2.1 存在的問題及改進思路

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

以上負載模型雖然權重計算方式不一樣，但都屬于線性模型，無法發現組合特征與負載的關系。為改善這一問題，提出了一種基于KNN的副本放置策略模型KRPM（KNN Replica Placement Model）。該策略中，選用CPU使用率、內存使用率、磁盤使用率、磁盤I/O使用率和網絡帶寬使用率這5個特征，通過使用訓練的KNN回歸模型，對節點的寫入速度進行預測。若隨機選擇的節點預測值小于集群的平均值，則重新隨機選擇，直到選擇到符合條件的數據節點。

2.2 文件寫入性能衡量指標

為了找到符合條件的數據節點，需要通過數據節點的一些性能衡量指標對節點的寫入速度進行預測。通常來說，機器的寫入速度會受到CPU、內存、硬盤、網絡等方面的影響。本文選取以下五個指標作為評估節點寫入速度的特征：

（1）CPU使用率。節點的CPU使用率的高低，可以反映機器運行程序的負載程度。機器的CPU使用率越高，說明機器上執行的任務越多，對放置新副本的速度也會有負面影響。這里使用P1來代表節點的CPU使用率。

（2）內存使用率。程序運行需要將代碼和數據放入內存，內存的使用率也能反映機器的負載程度。數據塊在以管道方式傳到節點上的過程中，是分為一個個Packet傳輸的，每個Packet會先存入內存再寫入硬盤。因此，內存使用率也可以影響副本的放置速度。

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

（4）磁盤I/O使用率。當磁盤I/O較高，說明磁盤已經在進行大量的讀寫操作了。若此時再將副本放置在該節點上，會極大程度影響數據塊的寫入速度。因此，磁盤I/O使用率是影響副本放置速度的很大一個因素。

（5）網絡帶寬使用率。數據塊在節點中的傳輸是通過網絡完成的，節點網絡負載較大會影響數據的傳輸，降低文件寫入速度。

2.3 KNN回歸模型

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

KNN方法思路簡單，易于理解，易于實現，無需估計參數。該算法的一個不足之處是計算量較大，因為對每一個待分類的文本都要計算它到全體已知樣本的距離，才能求得它的K個最近鄰點。為了提高副本放置策略的放置效率，需要模型具有相對快的計算速度。KNN方法易于實現，且用來評估的特征只有5個，可以滿足快速評估的需求。模型的調優過程如圖2所示。

圖2 模型調優流程

使用Hadoop基準測試工具生成數據集，按照4:1的比例隨機分成訓練集和測試集。P1-P5分別代表CPU使用率、內存使用率、磁盤使用率、磁盤I/O使用率和網絡帶寬使用率，S代表副本放置速度（Mb/s）。樣本坐標格式如（P1，P2，P3，P4，P5，S）。使用歐氏距離來計算待預測特征與訓練樣本特征間的距離，即：

在根據一組數據的特征（P1，P2，P3，P4，P5）計算預測值S時，先計算其與所有訓練樣本的距離d。將結果按照升序排序，并取出距離最小的前K個，計算它們S值的平均值，作為預測值。

分別取K=1到K=20，對測試集所有樣本進行評估，并計算誤差。采用均方誤差作為誤差評估指標，誤差越小，說明預測效果越好。

針對K的不同取值，使用交叉驗證的方式獲取平均誤差。得出當K=6時，獲得最小均方誤差。

2.4 新的副本放置策略

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

圖3 基于KNN的放置策略

3 實驗與分析

3.1 實驗環境

為了驗證新的副本放置策略的效果，設計實驗進行驗證。實驗通過虛擬機搭建3個機架，每個機架3個節點。節點安裝CentOS 7操作系統，系統安裝Ha?doop 2.7.2。集群配置及環境如表1所示。

表1 Hadoop集群配置

3.2 實驗結果分析

由于策略在放置副本時考慮了節點的文件寫入速度，所以在統計集群寫入性能前，先讓集群部分節點開始執行排序任務。Hadoop自帶有測試程序測試集群性能。TeraSort是測試Hadoop的一個有效的排序程序。實驗數據由程序中的TeraGen程序生成，之后由Tera?Sort對數據排序。TestDFSIO主要用于測試集群的I/O性能。

先使用TeraGen生成數據，再使用TeraSort使集群進入負載狀態，同時使用TestDFSIO測試HDFS寫性能。實驗進行三次，相比默認放置策略，實驗結果如圖4和圖5所示。

圖4 TestDFSIO寫任務執行時間

圖5 TeraSort任務執行時間

由上圖可知，在TestDFSIO測試中，改進策略的文件寫入時間少于默認策略。在TeraSort測試中，改進策略的排序性能也較默認策略優秀。實驗結果說明改進的策略在副本放置效率上優于默認的放置策略，可以提高集群的文件寫入性能。并且改進后的策略在執行排序任務的效率上也較默認策略高，說明它對系統的負載均衡也起到了正面作用。

4 結語

本文分析了Hadoop默認放置策略，并針對默認策略在選擇放置副本節點時，未考慮節點的負載問題，提出了改進的策略。新的策略使用KNN算法來預測節點的寫入速度，從側面實現了對節點負載的預測。使用交叉驗證，可以得到合理的模型參數K。實驗證明，基于KNN的副本放置策略在集群進行文件寫入的任務中，花費了更短的時間。這說明新的策略能夠較好的預測節點的文件寫入速度，并選擇合理的節點進行副本放置，利于集群的負載均衡并提高集群性能。

新的策略是基于默認副本放置策略的改進，節點負載情況是通過節點文件寫入速度來反映的。然而由于磁盤空間在用盡前對文件寫入速度影響不大，因此節點的文件寫入速度只能反映集群的部分負載情況。當集群副本分布不均衡時，仍需要啟動Balancer來遷移副本完成集群的數據均衡。