基于分布式存儲系統(tǒng)的數(shù)據(jù)布局策略研究

趙媛媛，王珂，周瑤

（西安建筑科技大學(xué)，西安710055）

0 引言

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

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

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

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

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

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

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

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

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

2.2 系統(tǒng)模型

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

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

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

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

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

由此可得，系統(tǒng)負(fù)載變化即數(shù)據(jù)節(jié)點(diǎn)負(fù)載標(biāo)準(zhǔn)差：

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

2.3 算法步驟

該算法具體步驟如下：

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

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

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

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

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

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

本改進(jìn)策略的優(yōu)點(diǎn)主要有：

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

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

3 測試和分析

3.1 實(shí)驗(yàn)環(huán)境配置

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

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

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

實(shí)驗(yàn)軟件環(huán)境如表1。

表1

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

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

表2

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

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

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

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

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

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

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

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

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

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

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

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

4 結(jié)語

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