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

，， ，

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

0 引言

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

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

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

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

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

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

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個歷史周期的訪問情況賦予不同的權重合理地計算機數(shù)據(jù)塊的預測訪問頻率，進而更加準確地對熱點數(shù)據(jù)塊做出判定。

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

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

(1)

其中：τ的取值范圍為0～1之間，其作用是來平衡當前訪問周期和歷史訪問周期對預測頻率影響的權重。在設置權重時，遵循上述數(shù)據(jù)訪問的局部性原理，其值得設置要使得越是靠近當前周期的歷史訪問周期的訪問頻率對預測訪問頻率影響越大；反之，越是久遠的歷史周期的訪問情況對預測訪問頻率影響影響越小。即τ的取值越接近0，表示下一周期的訪問頻率預測更取決于當前周期內(nèi)該數(shù)據(jù)塊的訪問情況；反之，τ的值越接近于1，則表示對數(shù)據(jù)塊下一周期的頻率預測更側重于其過往周期訪問情況即歷史訪問率。需要根據(jù)實際情況需求，合理地設置的值，以便準確的預測數(shù)據(jù)塊下一周期的訪問情況，從而確定其是否為熱點數(shù)據(jù)塊，進而合理地動態(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ù)塊預測頻率的計算公式(4)可簡化為：

(5)

如式(5)所示，i越大表示該訪問周期離當前周期越，近由于介于0和1之間，所以τk-1的值就越大，因此，其對數(shù)據(jù)塊預測訪問頻率的影響也就越大；反之，i越小，表示該訪問周期離當前周期越遠，所以τ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ù)量進行相應的增加，以提高用戶訪問效率；將訪問率后20%的數(shù)據(jù)塊判定為冷門數(shù)據(jù)塊，在保證其數(shù)據(jù)可用性的前提下對其副本數(shù)量進行適當?shù)販p少，以節(jié)省系統(tǒng)開銷；將剩余的數(shù)據(jù)即訪問率在中間60%的判定為正常數(shù)據(jù)塊，其副本數(shù)量在當前周期內(nèi)保持不變，隨著訪問周期的推進，正常數(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)副本維護消耗，從而降低存儲資源的利用率；如果副本系數(shù)過小，則無法保證數(shù)據(jù)的可用性和可靠性[14-16]。因此，合理地確定副本系數(shù)的動態(tài)調(diào)整的范圍或者閥值是關鍵。

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

如前所述，每個數(shù)據(jù)塊的訪問頻率可通過(2)計算出，并且計算出的這個訪問頻率是整個數(shù)據(jù)塊的訪問頻率。由于在HDFS中，數(shù)據(jù)塊是以多副本的方式存儲的，并且用戶對某個數(shù)據(jù)塊的訪問請求將盡可能地均勻分布在該數(shù)據(jù)塊的所有副本上。所以，假設某數(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ù)據(jù)塊副本平均訪問頻率的2倍，將減少閥值Dec_th設定為數(shù)據(jù)塊副本平均訪問頻率的1/2。假設數(shù)據(jù)塊副本系數(shù)為n，則Inc_th和Dec_th的計算公式如(7)，(8)所示：

(7)

(8)

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

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

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

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

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

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

(9)

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

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

(10)

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

5 實驗驗證與結果分析

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

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

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

5.2 實驗結果

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

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

表3 數(shù)據(jù)準備及相關參數(shù)設置

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

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

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

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

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

6 小結

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