基于熱點數據塊的動態副本調整策略

，， ，

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

0 引言

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

1 基于文件的動態副本調整策略的不足

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

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

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

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

2 基于訪問率的熱點數據塊的判定

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

2.1 計算數據塊訪問頻率

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

(1)

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

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

(2)

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

(3)

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

(4)

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

(5)

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

2.2 判定數據塊類型

研究發現，HDFS集群系統中用戶對數據的訪問規律接近于二八定律，即20%的數據占有80%的用戶數據訪問量[13]。依據此定律和上述計算出的數據塊訪問頻率，將訪問率前20%的數據塊判定為熱點數據塊，對其副本數量進行相應的增加，以提高用戶訪問效率；將訪問率后20%的數據塊判定為冷門數據塊，在保證其數據可用性的前提下對其副本數量進行適當地減少，以節省系統開銷；將剩余的數據即訪問率在中間60%的判定為正常數據塊，其副本數量在當前周期內保持不變，隨著訪問周期的推進，正常數據塊有可能會在將來某個訪問周期成為熱點數據或冷門數據。

表1 數據塊類型判定表

3 數據塊副本動態調整系數的確定

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

3.1 數據塊副本訪問頻率

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

(6)

3.2 數據塊副本調整閥值

副本調整閥值可分為增加閥值(Inc_th)和減少閥值(Dec_th)。為有效節省系統計算和內存資源，依據二八定律本文采用如下方法確定副本的調整閥值。

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

(7)

(8)

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

4 基于熱點數據塊的動態副本調整策略

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

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

圖1 基于熱點數據塊的動態副本調整策略流程圖

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

(9)

同時R的取值不能超過系統的最大副本系數。根據計算出的副本數量，創建新的數據塊副本，并依據相應的副本放置策略選擇最佳的數據節點DataNode放置新的副本。

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

(10)

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

5 實驗驗證與結果分析

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

5.1 小型集群實驗環境設計

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

5.2 實驗結果

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

表2 小型集群環境計算機配置

表3 數據準備及相關參數設置

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

由表4可以看出，數據塊B為熱點數據塊。該訪問情況下3種副本策略文件占用集群存儲空間情況如圖2所示，可以看出，不同的副本管理策略下，隨著訪問周期的不同文件所占集群存儲空間的變化是不同的。在固定副本管理策略中，文件所占的存儲空間固定不變；基于文件的副本調整策略使得當文件中的某個數據塊被頻繁訪問時，整個文件都將成為熱點文件，其所有數據塊的副本均有所增加，導致文件所占的集群存儲空間持續增加，只有當文件的所有數據塊均被判定為冷門數據塊時，系統文件默認副本系數才會變化，如在第6個訪問周期，副本系數變為2，整個文件存儲空間變為最??；而本文提出的基于熱點數據塊的動態副本調整策略，不會因為數據塊B的高訪問率，導致整個文件占用的存儲空間增加，對于熱點數據塊B，只增加該數據塊的副本數量，不會影響該文件其它數據塊的副本數量變化。實驗結果證明，本文提出的基于熱點數據塊的動態副本調整策略在集群存儲空間利用率方面優于基于文件的副本調整策略和固定副本調整策略。

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

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

圖3 3種策略數據訪問效率比較圖

6 小結

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