基于分布式存儲系統的數據布局策略研究

趙媛媛，王珂，周瑤

（西安建筑科技大學，西安710055）

0 引言

隨著互聯網和物聯網在生活中的不斷普及和完善，網絡社交媒體的數據呈現幾何增長的狀態，大數據已融入到各個領域，成為企業最重要的生產因素，決定了企業以后的發展。如何有效對大數據進行存儲和管理來更深層次的挖掘和利用數據中的信息已成為當前需要解決的一個重要問題。分布式存儲系統成為目前存儲大數據的主要方式。然而，隨著存儲數據量越來越多，原有的存儲系統中設備不斷進行更替，系統規模的不斷擴大，人們對于數據存儲有了更高的要求，需要設計一個可靠的數據管理方法來根據系統存儲規模的變化來動態調整數據布局，保證系統在處理過程中能夠快速地對數據進行存儲并且使得系統負載保持均衡，這對于系統性能的提升至關重要。

1 傳統的數據布局策略及其缺陷

數據布局策略是指為了達到存儲目標，將數據通過某種映射機制來指派到合適的存儲節點中。在存儲系統中，存儲目標在一定程度上決定了其所采用的數據布局策略。對于分布式存儲系統來說，數據布局策略在系統響應、訪問速率和負載均衡等方面有著更高的要求。數據布局的標準有以下幾點：公平性、冗余、自適應性以及時空有效性[1]，在研究數據布局方面，為了提高系統性能，通常從降低系統平均響應時間、提高可用性和可靠性、保證系統負載均衡這幾個方面來進行考慮。

在現有的布局策略中，Round-Robin[2]策略較為簡單，但是對數據布局公平性和自適應性方面表現較差，SLAS 策略[3]在Round-Robin 策略的基礎上考慮到了系統規模的擴展，但是需要遷移的數據量較大。在同構存儲環境中，一致性Hash 策略[4]雖然能夠解決遷移數據量大的問題，但是這種策略不適用于異構存儲環境。基于聚類和一致性Hash 布局算法[5]在一定程度上降低了定位的時空復雜度，但是這種布局算法較為復雜。為了避免一致Hash 的異構擴展所引入大量虛擬節點造成了空間的浪費，引入設備容量的權重提出了線性方法和對數方法，然而這種策略公平性較低，需要定位數據的時間也長。在異構存儲環境中，基于動態區間映射的數據布局算法需要較高的時空復雜度去定位數據對象，不適用于大量存儲設備的存儲系統。啟發式算法中的SP、HP 和SOR 策略雖然考慮了數據特性，但是卻沒有考慮到數據布局的公平性和自適應性，無法動態適應系統規模的增長。

基于對上述策略的分析，本文在對數據文件進行布局時，主要考慮數據傳輸時間和負載均衡方面的問題。

2 數據布局算法的改進

2.1 改進的數據布局算法

在數據布局算法中，針對系統性能進行布局的啟發式算法主要包括SP、HP 和SOR 三種策略。SP 策略[6]通過最小化磁盤上數據的服務時間來提高系統性能，將服務時間接近的數據采用Greedy 算法分配到同一磁盤上，對大小數據進行分類存儲，然而熱點數據的集中存放卻容易造成磁盤訪問過熱，Lee 在SP 的基礎上進一步提出了動態布局算法HP[7]，對成批到達的每一批數據采用SP 策略進行分配。SOR 策略[8]則克服了SP 算法中數據集中存放而造成的磁盤訪問過熱的問題，通過輪詢方式對數據進行分配，然而這種算法卻沒有對大小數據進行分離。

本節在SP 和SOR 策略的基礎上進行改進，根據數據節點負載的情況來對數據文件進行分配，基本思路是：首先獲取數據節點的負載情況，根據平均負載將節點劃分為兩類，將請求數據按照大小進行降序排列，首先，先將數據通過Greedy 的方式存放到比平均負載低的這一類節點上，然后，再將剩余數據采用輪詢方式存放到所有節點上。這種處理方式避免了數據的集中存放，另一方面提高了數據節點利用率，更好地實現系統負載均衡。

2.2 系統模型

在分布式存儲系統中通常利用主節點的數據布局來對數據進行合理分配，客戶端對存儲在數據節點的數據進行訪問，在一定程度上數據布局策略影響著系統的響應時間和負載。在設計數據布局策略時首先需要構建數據指派模型，即對數據和節點之間建立映射關系。

數據節點和數據之間的映射關系用決策函數φ(i,j)來表示，如果數據fi存儲在節點dnj上，則φ(i,j)=1，反之為 0。由于數據只存儲在單個節點上，因此

數據請求的響應時間包括等待時間和服務時間，其中服務時間為ti，等待時間為節點上正在等待處理的所有請求的服務時間，假設該節點上有請求集合Q 等待處理，那么等待時間，其中，rest(t)為當前節點正在處理請求的剩余時間，wri為等待處理的請求。

本文主要從系統響應時間和負載情況兩個方面來研究數據布局策略對系統性能的影響。系統對請求的處理速度在一定程度上影響著系統性能，數據的合理放置有利于降低系統的響應時間。設tij為數據fi在節點dnj上的服務時間，則因此系統的平均響應時間為：

為了能夠觀察系統負載的變化情況，本文采用標準差LB 來表示混合存儲系統負載變化，通過標準差LB 可以觀察系統負載是否均衡。LB 的值越低，系統中數據節點間的負載越均衡。假設對于存儲在節點dnj上的數據fi的請求訪問速率為vij，因此，該數據fi在節點dnj上的負載為lbij=vij×tij，數據節點dnj的負載為，系統的平均負載為

由此可得，系統負載變化即數據節點負載標準差：

在本文中對于數據布局策略主要針對上述兩方面進行設計，因此在上述公式中，獲得節點和數據之間的映射關系可對系統響應時間和負載均衡進行分析，判斷該布局是否滿足負載均衡條件。

2.3 算法步驟

該算法具體步驟如下：

（1）計算數據節點平均負載-lb；

（2）根據平均負載將數據節點進行分組；

（3）將數據按照大小進行排序；

（4）初始化決策變量aij；

（5）將數據按照Greedy 方式分配到小于平均負載的節點上；

（6）如果數據沒有分配完，則采用輪詢的方式分配到所有數據節點上。

本改進策略的優點主要有：

（1）在數據存放時，確保數據節點負載保持均衡，根據數據大小進行升序排序，保證了小型數據的性能，同時也降低數據節點因大型數據存儲而造成的等待，提高了系統性能。

（2）當負載小于平均負載的節點放置完之后，通過輪詢的方式在所有的數據節點上放置數據，避免數據集中放置造成的單個節點重載，提高磁盤利用率。

3 測試和分析

3.1 實驗環境配置

為了使系統環境達到實驗要求，本文采用VMware Workstation 作為模擬平臺搭建Hadoop 集群環境，通過對虛擬機的內存、存儲容量、處理器核心數目配置來達到系統實驗環境要求。

本文實驗基于Hadoop 環境，測試環境由實驗室多臺計算機構成Hadoop 分布式系統，配置包括一個主節點和5 個從節點，節點之間通過局域網連接。

實驗硬件配置為：主節點：八核CPU，內存8GB，硬盤500TB，從節點配置：四核CPU，內存4GB，硬盤250GB。

實驗軟件環境如表1。

表1

本文通過數據量和數據節點兩個因素對三種策略進行了對比實驗，觀察系統響應時間和負載情況的表現。在每次實驗中對同一組數據進行了5 次重復實驗，盡可能排除由于運行異常對響應時間的影響，并采用平均值來反映不同因素對系統性能的影響。

實驗通過對客戶端請求數據量，數據節點數和請求數據大小三個參數進行調控來比較三種策略在不同條件下對系統響應時間和負載的影響情況。具體設置如表2 所示。

表2

3.2 請求數據量

請求數據量反映了系統接收到多個數據請求時的處理能力。在該實驗中設定數據節點數為8，請求的數據大小服從100～500MB 的隨機分布。實驗結果從系統響應時間和系統負載兩方面來進行觀察。實驗結果如圖1-2。

從圖1 可以看出，隨著請求數據數量的增多，系統響應時間也越來越長，改進策略相較于SP 和SOR 策略系統響應時間短，表明系統可以同時處理大量的數據請求；對于系統負載來說，圖2 中SP 策略由于采用Greedy 算法來存放數據，使得數據節點存放的數據過多導致負載過重，而SOR 策略和改進策略隨著請求數據量的增多，節點之間負載更均衡。

圖1 系統響應時間變化

圖2 數據節點負載變化

3.2 數據節點數量

在本次實驗中，通過設置不同的數據節點數來比較三種策略對系統性能的影響，實驗中默認采用100個大小服從100～500MB 隨機分布的請求數據來進行實驗。實驗結果如圖3-4。

從圖3 的實驗結果可以看出，隨著數據節點個數的增多，系統響應時間明顯降低，因為隨著數據節點數的增多，每個節點處理的數據量減少，系統處理性能提升。從三種策略的實驗結果對比來看，SP 和SOR 策略處理時間降低幅度較大，當節點數增多時，這兩種策略對于系統性能提升較為明顯，而對于本改進策略來說，在系統響應時間方面表現比另外兩個策略要好。

圖4 顯示了三種策略在系統負載方面的變化，隨著數據節點數的增加，SP 策略對于系統負載沒有較大的優化，SOR 策略和改進策略則呈現明顯的下降趨勢，而改進策略相較于SOR 策略負載均衡方面要更好一些。

圖3 系統響應時間變化

圖4 系統負載變化

因此，從上述分析結果可以看出，隨著數據節點數的增多，SP 策略在負載方面表現比較差，改進策略在數據節點數不同的系統中都表現比其他兩種策略要好。

4 結語

本文針對現有布局策略中存在的問題進行分析，從系統響應時間和負載均衡兩方面考慮分布式存儲的系統性能，基于SP，SOR 策略提出了改進數據布局策略，并通過實驗驗證了該改進策略的有效性，通過利用數據節點的存儲能力，解決在客戶端訪問頻繁的情況下磁盤過熱的問題，最后通過與SP 和SOR 策略進行比較，驗證本改進算法的可行性，結果表明，該布局策略相較其他兩種策略對系統性能的提升效果要好。