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

趙媛媛，王珂，周瑤

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

0 引言

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

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

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

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

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

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

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

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

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

2.2 系統(tǒng)模型

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

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

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

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

為了能夠觀察系統(tǒng)負(fù)載的變化情況，本文采用標(biāo)準(zhǔn)差LB 來(lái)表示混合存儲(chǔ)系統(tǒng)負(fù)載變化，通過(guò)標(biāo)準(zhǔn)差LB 可以觀察系統(tǒng)負(fù)載是否均衡。LB 的值越低，系統(tǒng)中數(shù)據(jù)節(jié)點(diǎn)間的負(fù)載越均衡。假設(shè)對(duì)于存儲(chǔ)在節(jié)點(diǎn)dnj上的數(shù)據(jù)fi的請(qǐng)求訪問(wèn)速率為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)差：

在本文中對(duì)于數(shù)據(jù)布局策略主要針對(duì)上述兩方面進(jìn)行設(shè)計(jì)，因此在上述公式中，獲得節(jié)點(diǎn)和數(shù)據(jù)之間的映射關(guān)系可對(duì)系統(tǒng)響應(yīng)時(shí)間和負(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ù)沒(méi)有分配完，則采用輪詢(xún)的方式分配到所有數(shù)據(jù)節(jié)點(diǎn)上。

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

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

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

3 測(cè)試和分析

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

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

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

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

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

表1

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

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

表2

3.2 請(qǐng)求數(shù)據(jù)量

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

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

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

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

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

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

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

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

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

圖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é)語(yǔ)

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