，， ，

(海軍航空大學(xué) 航空基礎(chǔ)學(xué)院，山東 煙臺 264001)

0 引言

資料顯示，針對分布式存儲系統(tǒng)的數(shù)據(jù)存儲策略的研究，國內(nèi)外研究者主要從數(shù)據(jù)可靠性、用戶訪問效率、存儲資源利用率及系統(tǒng)負(fù)載均衡4個方面進(jìn)行。分布式存儲主要涉及到如何確定數(shù)據(jù)副本系數(shù)和如何在集群系統(tǒng)中選擇數(shù)據(jù)副本存放的節(jié)點兩個方面的內(nèi)容。文獻(xiàn)[1-9]從不同的方面給出了多個動態(tài)副本改進(jìn)策略，這些改進(jìn)策略在副本管理的某些方面都有一定的效率提升，并且主要都是依據(jù)數(shù)據(jù)的歷史訪問情況來預(yù)測數(shù)據(jù)訪問熱度，進(jìn)而動態(tài)調(diào)整數(shù)據(jù)副本的相應(yīng)系數(shù)。但是，這些動態(tài)調(diào)整策略大部分都是基于文件進(jìn)行動態(tài)副本管理的，這樣就忽略了一種事實，即很多時候用戶感興趣的不是整個文件，而只是文件中的一部分?jǐn)?shù)據(jù)，即其中的一個數(shù)據(jù)塊或多個數(shù)據(jù)塊。因此，若是僅僅以文件為單位進(jìn)行動態(tài)副本調(diào)整，其效果并不理想，不僅會導(dǎo)致集群系統(tǒng)存儲資源利用率的降低，同時還會因為副本維護(hù)一致性增加而增加系統(tǒng)的系統(tǒng)開銷[10]。

1 基于文件的動態(tài)副本調(diào)整策略的不足

基于文件的動態(tài)副本調(diào)整策略主要是通過對文件的歷史訪問情況進(jìn)行分析，在此基礎(chǔ)上對文件的訪問趨勢進(jìn)行預(yù)測，進(jìn)而動態(tài)調(diào)整其相應(yīng)的副本系數(shù)。對于熱點數(shù)據(jù)，通過合理地增加其副本系數(shù)來提高其訪問并行度；而對于訪問頻率較低的數(shù)據(jù)，在保證其可靠性的前提下通適當(dāng)?shù)販p少其副本數(shù)，從而降低了維護(hù)其數(shù)據(jù)副本一致性帶來的系統(tǒng)開銷，進(jìn)而提高系統(tǒng)資源利用率[11]。事實情況，也是如此，在大多數(shù)情況下用戶感性趣的只是某個文件中的某一部分?jǐn)?shù)據(jù)，而非整個數(shù)據(jù)文件。因此，如果以文件為單位進(jìn)行副本系數(shù)動態(tài)調(diào)整，會帶來以下弊端：

1)集群系統(tǒng)存儲資源利用率降低。HDFS分布式文件系統(tǒng)中主要存儲的是大數(shù)據(jù)文件，僅僅因為某個大文件中的部分?jǐn)?shù)據(jù)塊訪問頻率較高，就將該整個文件被判斷為熱點文件，從而增加該其副本系數(shù)，這將大大浪費集群存儲資源，降低系統(tǒng)資源利用率。

2)數(shù)據(jù)副本一致性維護(hù)成本增加。數(shù)據(jù)副本的一致性是保證用戶能夠正確訪問到所請求的數(shù)據(jù)的重要因素。隨著熱點文件數(shù)據(jù)副本數(shù)量的增加，勢必會使副本管理難度增加，尤其是系統(tǒng)在維護(hù)數(shù)據(jù)副本一致性時所產(chǎn)生的消耗也會相應(yīng)增加。

因此，本文提出了一種基于熱點數(shù)據(jù)塊的動態(tài)副本調(diào)整策略，在一定程度上克服了基于文件的副本動態(tài)調(diào)整策略的弊端，保證數(shù)據(jù)可靠性的同時進(jìn)一步提升集群系統(tǒng)存儲資源的利用率，減少數(shù)據(jù)副本一致性維護(hù)的成本。

2 基于訪問率的熱點數(shù)據(jù)塊的判定

對于數(shù)據(jù)文件的訪問情況而言，某個數(shù)據(jù)塊的以往周期的訪問次數(shù)有可能在某個周期某個時間段內(nèi)相對較高，但在此之后不斷下降，而其總體訪問次數(shù)相對于其他數(shù)據(jù)塊可能還是處于高水平。因此，對熱點數(shù)據(jù)塊的判定，不能僅僅依據(jù)其在某個時間段的歷史訪問次數(shù)或者平均訪問次數(shù)。同時，根據(jù)時間局部性原理和數(shù)據(jù)訪問規(guī)律可知，一般情況下，數(shù)據(jù)訪問規(guī)律在一段時間內(nèi)是今本是保持不變的，且最近被頻繁訪問的數(shù)據(jù)很有可能在接下來的一段時間內(nèi)還會被訪問到[12]?；谶@種數(shù)據(jù)訪問的局部性原理，本文提出了一種根據(jù)基于熱點數(shù)據(jù)塊的動態(tài)調(diào)整策略，通過對數(shù)據(jù)塊前N個歷史周期的訪問情況賦予不同的權(quán)重合理地計算機數(shù)據(jù)塊的預(yù)測訪問頻率，進(jìn)而更加準(zhǔn)確地對熱點數(shù)據(jù)塊做出判定。

2.1 計算數(shù)據(jù)塊訪問頻率

在名字節(jié)點(NameNode)上設(shè)置一個記錄數(shù)據(jù)塊訪問情況的三元組，主要包含：數(shù)據(jù)塊標(biāo)識(BID)，上一周期訪問頻率(Pre_F)，本周期訪問次數(shù)(N)。由于HDFS集群中存儲著海量的數(shù)據(jù)文件，如果對每個數(shù)據(jù)塊的所有歷史周期訪問情況都一一記錄下來，這將給NameNode節(jié)點帶來巨大的負(fù)擔(dān)。因此，為減輕NameNode節(jié)點的負(fù)載，這里只記錄數(shù)據(jù)塊上一周期的訪問頻率和當(dāng)前周期的訪問次數(shù)。接下來，通過設(shè)置平衡因子，對歷史訪問周期和當(dāng)前訪問周期賦予不同的權(quán)重，進(jìn)而計算出下一周期數(shù)據(jù)塊的訪問頻率。如果，數(shù)據(jù)塊下一周期預(yù)測頻率B_f表示，數(shù)據(jù)塊上一周期訪問頻率用B_fpre表示，數(shù)據(jù)塊當(dāng)前周期內(nèi)的訪問次數(shù)用M表示，訪問周期用T表示，平衡因子用τ。則數(shù)據(jù)預(yù)測訪問頻率的B_f計算方法如公式1所示。

(1)

其中：τ的取值范圍為0～1之間，其作用是來平衡當(dāng)前訪問周期和歷史訪問周期對預(yù)測頻率影響的權(quán)重。在設(shè)置權(quán)重時，遵循上述數(shù)據(jù)訪問的局部性原理，其值得設(shè)置要使得越是靠近當(dāng)前周期的歷史訪問周期的訪問頻率對預(yù)測訪問頻率影響越大；反之，越是久遠(yuǎn)的歷史周期的訪問情況對預(yù)測訪問頻率影響影響越小。即τ的取值越接近0，表示下一周期的訪問頻率預(yù)測更取決于當(dāng)前周期內(nèi)該數(shù)據(jù)塊的訪問情況；反之，τ的值越接近于1，則表示對數(shù)據(jù)塊下一周期的頻率預(yù)測更側(cè)重于其過往周期訪問情況即歷史訪問率。需要根據(jù)實際情況需求，合理地設(shè)置的值，以便準(zhǔn)確的預(yù)測數(shù)據(jù)塊下一周期的訪問情況，從而確定其是否為熱點數(shù)據(jù)塊，進(jìn)而合理地動態(tài)調(diào)整其副本系數(shù)。

根據(jù)公式(1)，可以得到數(shù)據(jù)塊第i個周期的訪問頻率B_Fi計算公式如下:

(2)

第i-1個周期的訪問頻率B_Fi計算公式如下:

(3)

將公式(3)代入公式(2)可得：

(4)

其中：B_F0表示數(shù)據(jù)塊被創(chuàng)建時的訪問頻率，因為數(shù)據(jù)塊剛被創(chuàng)建時，前期沒有歷史訪問情況，所以其值可置為0。因此，數(shù)據(jù)塊預(yù)測頻率的計算公式(4)可簡化為：

(5)

如式(5)所示，i越大表示該訪問周期離當(dāng)前周期越，近由于介于0和1之間，所以τk-1的值就越大，因此，其對數(shù)據(jù)塊預(yù)測訪問頻率的影響也就越大；反之，i越小，表示該訪問周期離當(dāng)前周期越遠(yuǎn)，所以τk-1的值就越小，因此，其對數(shù)據(jù)塊訪問頻率的影響也就越小。這正與前面所述的局部訪問性原理相符。

2.2 判定數(shù)據(jù)塊類型

研究發(fā)現(xiàn)，HDFS集群系統(tǒng)中用戶對數(shù)據(jù)的訪問規(guī)律接近于二八定律，即20%的數(shù)據(jù)占有80%的用戶數(shù)據(jù)訪問量[13]。依據(jù)此定律和上述計算出的數(shù)據(jù)塊訪問頻率，將訪問率前20%的數(shù)據(jù)塊判定為熱點數(shù)據(jù)塊，對其副本數(shù)量進(jìn)行相應(yīng)的增加，以提高用戶訪問效率；將訪問率后20%的數(shù)據(jù)塊判定為冷門數(shù)據(jù)塊，在保證其數(shù)據(jù)可用性的前提下對其副本數(shù)量進(jìn)行適當(dāng)?shù)販p少，以節(jié)省系統(tǒng)開銷；將剩余的數(shù)據(jù)即訪問率在中間60%的判定為正常數(shù)據(jù)塊，其副本數(shù)量在當(dāng)前周期內(nèi)保持不變，隨著訪問周期的推進(jìn)，正常數(shù)據(jù)塊有可能會在將來某個訪問周期成為熱點數(shù)據(jù)或冷門數(shù)據(jù)。

表1 數(shù)據(jù)塊類型判定表

3 數(shù)據(jù)塊副本動態(tài)調(diào)整系數(shù)的確定

數(shù)據(jù)塊副本系數(shù)的動態(tài)調(diào)整范圍不能太大也不能過小。如果副本系數(shù)過大，雖然可以在一定程度上提升數(shù)據(jù)訪問的可用性和并行度，但同時也會大大增加系統(tǒng)副本維護(hù)消耗，從而降低存儲資源的利用率；如果副本系數(shù)過小，則無法保證數(shù)據(jù)的可用性和可靠性[14-16]。因此，合理地確定副本系數(shù)的動態(tài)調(diào)整的范圍或者閥值是關(guān)鍵。

3.1 數(shù)據(jù)塊副本訪問頻率

如前所述，每個數(shù)據(jù)塊的訪問頻率可通過(2)計算出，并且計算出的這個訪問頻率是整個數(shù)據(jù)塊的訪問頻率。由于在HDFS中，數(shù)據(jù)塊是以多副本的方式存儲的，并且用戶對某個數(shù)據(jù)塊的訪問請求將盡可能地均勻分布在該數(shù)據(jù)塊的所有副本上。所以，假設(shè)某數(shù)據(jù)塊的副本數(shù)量為n，則該數(shù)據(jù)塊每個副本的訪問頻率則為：

(6)

3.2 數(shù)據(jù)塊副本調(diào)整閥值

副本調(diào)整閥值可分為增加閥值(Inc_th)和減少閥值(Dec_th)。為有效節(jié)省系統(tǒng)計算和內(nèi)存資源，依據(jù)二八定律本文采用如下方法確定副本的調(diào)整閥值。

依據(jù)(6)計算出的數(shù)據(jù)塊副本的訪問頻率，對所有該數(shù)據(jù)塊的所有副本訪問頻率求平均，得到Rep_fava即數(shù)據(jù)塊副本平均訪問頻率，然后將增加閥值Inc_th設(shè)定為數(shù)據(jù)塊副本平均訪問頻率的2倍，將減少閥值Dec_th設(shè)定為數(shù)據(jù)塊副本平均訪問頻率的1/2。假設(shè)數(shù)據(jù)塊副本系數(shù)為n，則Inc_th和Dec_th的計算公式如(7)，(8)所示：

(7)

(8)

采用此方法確定的副本調(diào)整閥值不能完全符合二八定律，但是由于HDFS集群系統(tǒng)中數(shù)據(jù)的訪問規(guī)律也只是近似符合二八定律，并且該計算方法能夠迅速得到結(jié)果，因此，本文采用了該方法來確定副本調(diào)整閥值。

4 基于熱點數(shù)據(jù)塊的動態(tài)副本調(diào)整策略

對于熱點數(shù)據(jù)塊，依據(jù)計算出的數(shù)據(jù)塊增加閥值(Inc_th)增加其副本數(shù)量，以提高用戶訪問量，均衡數(shù)據(jù)節(jié)點DataNode的負(fù)載；對于冷門數(shù)據(jù)塊則依據(jù)計算出的數(shù)據(jù)塊減少閥值(Dec_th)減少其副本數(shù)量，在保證數(shù)據(jù)可用性的前提下，降低副本一致性維護(hù)消耗、節(jié)省系統(tǒng)存儲開銷。本文設(shè)計的基于熱點數(shù)據(jù)塊的數(shù)據(jù)塊動態(tài)副本調(diào)整策略如圖1所示。

步驟1：根據(jù)各數(shù)據(jù)塊訪問頻率計算出其相應(yīng)的數(shù)據(jù)塊副本增加閥值(Inc_th)和減少閥值(Dec_th)。

圖1 基于熱點數(shù)據(jù)塊的動態(tài)副本調(diào)整策略流程圖

步驟2：將數(shù)據(jù)塊副本訪問頻率Rep_f與其副本增加閥值(Inc_th)進(jìn)行比較，如果Rep_f>Inc_th,則表示該數(shù)據(jù)塊副本訪問負(fù)載過重，可能會導(dǎo)致其所在的數(shù)據(jù)節(jié)點DataNode負(fù)載過重，從而造成性能瓶頸。因此，需要增加其副本數(shù)量，假設(shè)需要的副本數(shù)量為R，則應(yīng)滿足：

(9)

同時R的取值不能超過系統(tǒng)的最大副本系數(shù)。根據(jù)計算出的副本數(shù)量，創(chuàng)建新的數(shù)據(jù)塊副本，并依據(jù)相應(yīng)的副本放置策略選擇最佳的數(shù)據(jù)節(jié)點DataNode放置新的副本。

步驟3：將數(shù)據(jù)塊副本訪問頻率Rep_f與其副本減少閥值(Dec_th)進(jìn)行比較，如果Rep_f

(10)

同時R的取值不能小于系統(tǒng)的最小副本系數(shù)。同樣，根據(jù)計算出的副本數(shù)量，依據(jù)相應(yīng)的副本放置策略選擇最佳的數(shù)據(jù)節(jié)點DataNode刪除副本。

5 實驗驗證與結(jié)果分析

由于本文主要針對數(shù)據(jù)訪問效率和集群存儲資源利用率兩方面的改進(jìn)提出了基于熱點數(shù)據(jù)塊的動態(tài)副本調(diào)整策略，所以改進(jìn)策略效果的驗證實驗的設(shè)計主要從上述兩個方面進(jìn)行。并將實驗結(jié)果與HDFS固定副本策略和基于文件的動態(tài)副本調(diào)整策略進(jìn)行比較分析，以驗證本文設(shè)計的基于熱點數(shù)據(jù)塊的動態(tài)副本調(diào)整策略的有效性。

5.1 小型集群實驗環(huán)境設(shè)計

選取實驗室8臺機器部署HDFS，機器配置如表2所示。其中，192.168.2.253作為NameNode,其余7臺作為DataNode,并依據(jù)IP將其分布在兩個rack(機架)中，機架內(nèi)部使用百兆以太網(wǎng)。

5.2 實驗結(jié)果

采用默認(rèn)副本系數(shù)3，對隨機生成的100個文件中選取其中一個大小為256M(共4塊)的文件，對其進(jìn)行7個周期的訪問測試，各數(shù)據(jù)塊各周期訪問頻率情況如表4所示。

表2 小型集群環(huán)境計算機配置

表3 數(shù)據(jù)準(zhǔn)備及相關(guān)參數(shù)設(shè)置

表4 大小為256M的文件各數(shù)據(jù)塊5個周期訪問頻率表

由表4可以看出，數(shù)據(jù)塊B為熱點數(shù)據(jù)塊。該訪問情況下3種副本策略文件占用集群存儲空間情況如圖2所示，可以看出，不同的副本管理策略下，隨著訪問周期的不同文件所占集群存儲空間的變化是不同的。在固定副本管理策略中，文件所占的存儲空間固定不變；基于文件的副本調(diào)整策略使得當(dāng)文件中的某個數(shù)據(jù)塊被頻繁訪問時，整個文件都將成為熱點文件，其所有數(shù)據(jù)塊的副本均有所增加，導(dǎo)致文件所占的集群存儲空間持續(xù)增加，只有當(dāng)文件的所有數(shù)據(jù)塊均被判定為冷門數(shù)據(jù)塊時，系統(tǒng)文件默認(rèn)副本系數(shù)才會變化，如在第6個訪問周期，副本系數(shù)變?yōu)?，整個文件存儲空間變?yōu)樽钚。欢疚奶岢龅幕跓狳c數(shù)據(jù)塊的動態(tài)副本調(diào)整策略，不會因為數(shù)據(jù)塊B的高訪問率，導(dǎo)致整個文件占用的存儲空間增加，對于熱點數(shù)據(jù)塊B，只增加該數(shù)據(jù)塊的副本數(shù)量，不會影響該文件其它數(shù)據(jù)塊的副本數(shù)量變化。實驗結(jié)果證明，本文提出的基于熱點數(shù)據(jù)塊的動態(tài)副本調(diào)整策略在集群存儲空間利用率方面優(yōu)于基于文件的副本調(diào)整策略和固定副本調(diào)整策略。

圖2 3種策略存儲空間占用大小比較圖

對于數(shù)據(jù)訪問效率，以數(shù)據(jù)塊B為主要測試對象，隨著不同周期訪問頻率的變化，3種策略下其平均響應(yīng)時間情況如圖3所示?？梢钥闯?，在第1個周期，由于數(shù)據(jù)塊訪問頻率較低，還沒有達(dá)副本增加的條件，因此，基于文件和基于本文提出的熱點數(shù)據(jù)塊的動態(tài)策略的響應(yīng)時間和原HDFS固定副本策略的平均響應(yīng)時間不但沒有減少，反而略高。這是由于動態(tài)副本調(diào)整策略每個周期都會對文件或數(shù)據(jù)塊進(jìn)行訪問頻率的計算，從而進(jìn)行相應(yīng)的熱點判斷，這會耗費一部分時間。之后隨著訪問頻率的增加，3種策略的響應(yīng)時間均會達(dá)到一個最大值，這主要是由于隨著訪問頻率的不斷增加，會開始進(jìn)行副本增加操作，這同樣會占用一部分系統(tǒng)資源。接下來，增加后的副本開始分擔(dān)相應(yīng)的數(shù)據(jù)訪問請求，因此，動態(tài)副本調(diào)整策略的響應(yīng)時間的優(yōu)勢凸現(xiàn)出來，而本文提出的基于熱點數(shù)據(jù)塊的響應(yīng)效率優(yōu)勢更加明顯。

圖3 3種策略數(shù)據(jù)訪問效率比較圖

6 小結(jié)

本文在總結(jié)分析基于文件的動態(tài)副本調(diào)整策略不足的基礎(chǔ)上，提出了一種基于熱點數(shù)據(jù)塊的動態(tài)副本調(diào)整策略。該策略在時間局部性原理前提下，通過對數(shù)據(jù)塊的歷史訪問周期的訪問率賦予不同的權(quán)重進(jìn)而預(yù)測出數(shù)據(jù)塊下一周期的訪問頻率。然后根據(jù) HDFS 中數(shù)據(jù)訪問規(guī)律近似二八定律這一特點，依據(jù)計算出的數(shù)據(jù)塊預(yù)測訪問頻率，對數(shù)據(jù)塊進(jìn)行熱點和非熱點判定，從而將數(shù)據(jù)塊分為熱點數(shù)據(jù)塊、正常數(shù)據(jù)塊和冷門數(shù)據(jù)塊三類。對于熱點數(shù)據(jù)塊通過增加該數(shù)據(jù)塊的副本系數(shù)以增加訪問并行度提高用戶訪問效率，同時在保證最低可靠性前提下對非熱點數(shù)據(jù)塊的副本系數(shù)進(jìn)行適當(dāng)?shù)慕档鸵怨?jié)省集群存儲資源和減少因副本一致性維護(hù)所帶來的系統(tǒng)開銷。實驗結(jié)果表明，在數(shù)據(jù)訪問效率和集群存儲資源利用率兩方面，本文提出的基于熱點數(shù)據(jù)塊的動態(tài)副本調(diào)整策略與HDFS固定副本策略和基于文件的動態(tài)副本策略相比有了明顯提升。下一步，將對增加的副本的數(shù)據(jù)一致性維護(hù)進(jìn)行深入研究，以在盡量減少系統(tǒng)消耗的基礎(chǔ)上保證數(shù)據(jù)的一致性。