趙媛媛，王珂，周瑤

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

0 引言

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

1 傳統(tǒng)的數(shù)據(jù)布局策略及其缺陷

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

在現(xiàn)有的布局策略中，Round-Robin[2]策略較為簡單，但是對數(shù)據(jù)布局公平性和自適應性方面表現(xiàn)較差，SLAS 策略[3]在Round-Robin 策略的基礎(chǔ)上考慮到了系統(tǒng)規(guī)模的擴展，但是需要遷移的數(shù)據(jù)量較大。在同構(gòu)存儲環(huán)境中，一致性Hash 策略[4]雖然能夠解決遷移數(shù)據(jù)量大的問題，但是這種策略不適用于異構(gòu)存儲環(huán)境?；诰垲惡鸵恢滦訦ash 布局算法[5]在一定程度上降低了定位的時空復雜度，但是這種布局算法較為復雜。為了避免一致Hash 的異構(gòu)擴展所引入大量虛擬節(jié)點造成了空間的浪費，引入設備容量的權(quán)重提出了線性方法和對數(shù)方法，然而這種策略公平性較低，需要定位數(shù)據(jù)的時間也長。在異構(gòu)存儲環(huán)境中，基于動態(tài)區(qū)間映射的數(shù)據(jù)布局算法需要較高的時空復雜度去定位數(shù)據(jù)對象，不適用于大量存儲設備的存儲系統(tǒng)。啟發(fā)式算法中的SP、HP 和SOR 策略雖然考慮了數(shù)據(jù)特性，但是卻沒有考慮到數(shù)據(jù)布局的公平性和自適應性，無法動態(tài)適應系統(tǒng)規(guī)模的增長。

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

2 數(shù)據(jù)布局算法的改進

2.1 改進的數(shù)據(jù)布局算法

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

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

2.2 系統(tǒng)模型

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

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

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

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

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

由此可得，系統(tǒng)負載變化即數(shù)據(jù)節(jié)點負載標準差：

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

2.3 算法步驟

該算法具體步驟如下：

（1）計算數(shù)據(jù)節(jié)點平均負載-lb；

（2）根據(jù)平均負載將數(shù)據(jù)節(jié)點進行分組；

（3）將數(shù)據(jù)按照大小進行排序；

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

（5）將數(shù)據(jù)按照Greedy 方式分配到小于平均負載的節(jié)點上；

（6）如果數(shù)據(jù)沒有分配完，則采用輪詢的方式分配到所有數(shù)據(jù)節(jié)點上。

本改進策略的優(yōu)點主要有：

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

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

3 測試和分析

3.1 實驗環(huán)境配置

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

本文實驗基于Hadoop 環(huán)境，測試環(huán)境由實驗室多臺計算機構(gòu)成Hadoop 分布式系統(tǒng)，配置包括一個主節(jié)點和5 個從節(jié)點，節(jié)點之間通過局域網(wǎng)連接。

實驗硬件配置為：主節(jié)點：八核CPU，內(nèi)存8GB，硬盤500TB，從節(jié)點配置：四核CPU，內(nèi)存4GB，硬盤250GB。

實驗軟件環(huán)境如表1。

表1

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

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

表2

3.2 請求數(shù)據(jù)量

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

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

圖1 系統(tǒng)響應時間變化

圖2 數(shù)據(jù)節(jié)點負載變化

3.2 數(shù)據(jù)節(jié)點數(shù)量

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

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

圖4 顯示了三種策略在系統(tǒng)負載方面的變化，隨著數(shù)據(jù)節(jié)點數(shù)的增加，SP 策略對于系統(tǒng)負載沒有較大的優(yōu)化，SOR 策略和改進策略則呈現(xiàn)明顯的下降趨勢，而改進策略相較于SOR 策略負載均衡方面要更好一些。

圖3 系統(tǒng)響應時間變化

圖4 系統(tǒng)負載變化

因此，從上述分析結(jié)果可以看出，隨著數(shù)據(jù)節(jié)點數(shù)的增多，SP 策略在負載方面表現(xiàn)比較差，改進策略在數(shù)據(jù)節(jié)點數(shù)不同的系統(tǒng)中都表現(xiàn)比其他兩種策略要好。

4 結(jié)語

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