基于多目標(biāo)分解策略的副本布局算法研究*

邵必林，賀金能，邊根慶

1.西安建筑科技大學(xué)管理學(xué)院，西安 710055

2.西安建筑科技大學(xué)信息與控制工程學(xué)院，西安 710055

1 引言

隨著大數(shù)據(jù)和云計算的飛速發(fā)展，數(shù)據(jù)存儲作為其中關(guān)鍵性的一個環(huán)節(jié)也備受關(guān)注[1]。鑒于時代背景和運(yùn)用場景發(fā)生巨大轉(zhuǎn)變，傳統(tǒng)的存儲技術(shù)已經(jīng)逐漸不適用于云計算下分布式的環(huán)境，海量的數(shù)據(jù)、異構(gòu)的環(huán)境、高可靠性以及可用性需求都超出了傳統(tǒng)存儲技術(shù)的處理范圍，迫切需要新的技術(shù)方能滿足目前現(xiàn)狀的需求。由于同時具備加快訪問速度、提高可用性和可靠性等提升存儲系統(tǒng)效能的作用，副本技術(shù)已經(jīng)逐漸成為研究的熱點(diǎn)。

為了在分布式存儲系統(tǒng)中有效地發(fā)揮副本技術(shù)的優(yōu)勢，有兩個關(guān)鍵性的問題亟待解決：第一個問題是為每一個數(shù)據(jù)選取多少個副本是合適的；第二個問題是如何放置這些副本來滿足系統(tǒng)效能的要求。把這兩個相關(guān)聯(lián)的問題合稱為副本的布局問題。

研究人員針對這兩個問題展開了很多研究[2-9]。目前現(xiàn)有的副本布局策略大都是研究副本帶來的收益，比如高可靠性、高訪問效率、負(fù)載均衡等，但是沒有考慮到副本的創(chuàng)建和維護(hù)需要消耗系統(tǒng)資源。一方面要使用更多的副本來提高系統(tǒng)的效能，另一方面又要削減副本的數(shù)量來減少能量消耗，因此需要一個合理的副本布局策略平衡上述矛盾。當(dāng)前的副本策略在考慮副本布局問題時也沒有把數(shù)據(jù)中心的能量消耗作為一個主要的優(yōu)化目標(biāo)，只是單純優(yōu)化少部分效能指標(biāo)。目前數(shù)據(jù)中心能耗問題越來越突出，提出一種兼顧數(shù)據(jù)中心能耗的數(shù)據(jù)副本布局方案就顯得刻不容緩。

綜合上述問題，本文將基于分解的多目標(biāo)進(jìn)化算法（multi-objective evolutionary algorithm based on decomposition，MOEA/D）[10]運(yùn)用于求解副本布局的多目標(biāo)優(yōu)化問題上，提出了一種基于多目標(biāo)分解策略的副本布局算法（replica layout algorithm based on a multi-objective decomposition strategy，MDSRL），將平均文件不可用性、負(fù)載均衡、能量消耗作為三個優(yōu)化對象綜合進(jìn)行考慮，試圖找到合適的副本數(shù)和副本放置方案。MDSRL把這三個目標(biāo)分解成多個標(biāo)量子問題同時進(jìn)行優(yōu)化來得到一組折衷解，得到的解在三個目標(biāo)上都能取得比較不錯的表現(xiàn)。

本文的主要貢獻(xiàn)如下：

（1）構(gòu)建了文件可用性、負(fù)載均衡以及能量消耗三個目標(biāo)的目標(biāo)函數(shù)并建立了多目標(biāo)函數(shù)模型。

（2）設(shè)置了一種新的性能度量指標(biāo)超體積占比（hypervolume account,HVA），以度量不同算法所得的一組折衷解在收斂性和分布性上的優(yōu)劣情況。

（3）提出了一種基于多目標(biāo)分解策略的副本布局算法MDSRL,尋找到了一組在平均文件不可用性、負(fù)載均衡以及能量消耗上都有良好表現(xiàn)的折衷解，并且解的分布性和收斂性較好。

2 相關(guān)工作

副本技術(shù)在萬維網(wǎng)、P2P（peer to peer）系統(tǒng)、分布式系統(tǒng)以及云存儲系統(tǒng)中得到了廣泛的應(yīng)用[11-12]，甚至在物聯(lián)網(wǎng)中也逐漸被使用[13]。因此副本布局的研究被越來越多的學(xué)者所重視[14-15]。

關(guān)于副本數(shù)量的選擇問題，已有許多學(xué)者對其進(jìn)行了深入的研究。目前現(xiàn)有的分布式文件系統(tǒng)采用的副本個數(shù)一般是固定的三個，這樣會導(dǎo)致需要更多的副本時達(dá)不到可用性需求，只需要較少副本時又會白白消耗系統(tǒng)能量。陶永才等[2]提出了一種動態(tài)副本管理機(jī)制（dynamic replica management scheme，DRM），在滿足可用性要求的情況下最小化副本數(shù)目。李帥等[3]提出了一種基于多訪問策略的副本動態(tài)更新算法（min-placement far servers first，MPFSF），通過對通信距離設(shè)置閾值來判斷是否增加和刪除副本。Qu等[4]提出了一種基于改進(jìn)馬爾科夫模型的動態(tài)副本管理策略（dynamic replica strategy based on improved Markov model,DRS），通過改進(jìn)的馬爾科夫模型對冷熱數(shù)據(jù)進(jìn)行分類，根據(jù)分類結(jié)果決定是否增加和減少副本個數(shù)。但是上述策略都沒有考慮如何平衡副本帶來的系統(tǒng)開銷和效能之間的矛盾。

云計算環(huán)境分布式存儲的副本放置問題是一個NP難問題。由于進(jìn)化算法（evolutionary algorithm，EA）可以同時在搜索空間搜索多個解，因此很適合求解NP難問題，研究者們嘗試使用進(jìn)化算法來選擇最合適的副本放置位置方案。Cui等[5]提出了基于蟻群算法的副本放置策略，通過遺傳算子不斷迭代來找到最合適的數(shù)據(jù)節(jié)點(diǎn)，實(shí)驗(yàn)證明該策略減少了數(shù)據(jù)傳輸費(fèi)用。羅四維等[6]提出了一種免疫優(yōu)化策略的副本放置算法，通過克隆選擇算子和記憶機(jī)制能夠選擇更加合適的副本放置節(jié)點(diǎn)，從而達(dá)到降低副本訪問開銷的目的。雖然已有的這些副本策略都在一定程度上優(yōu)化了系統(tǒng)的效能，但是針對的大都是單個目標(biāo)，并且只是單方面提高系統(tǒng)的效能，沒有從全局的角度考慮副本所帶來的能耗問題。

Hassan等[7]提出多目標(biāo)進(jìn)化算法（multi-objective evolutionary，MOE），將訪問延遲、存儲費(fèi)用以及系統(tǒng)可靠性作為三個要優(yōu)化的目標(biāo)，并用快速非支配排序遺傳算法（nondominated sorting genetic algorithm II，NSGA-II）[8]尋找一組折衷解，不過該算法沒有考慮到能耗和負(fù)載均衡兩個關(guān)鍵的指標(biāo)。Long等[9]提出了一種多目標(biāo)優(yōu)化的副本管理（multi-objective optimized replication management，MORM）算法，基于人工免疫算法對平均文件不可用性、服務(wù)時間、負(fù)載均衡、能耗以及延遲五個目標(biāo)進(jìn)行了優(yōu)化，但只是單純將五個目標(biāo)函數(shù)進(jìn)行線性加權(quán)，將多目標(biāo)轉(zhuǎn)化為單目標(biāo)進(jìn)行求解，方法容易實(shí)現(xiàn)但是很難對解的優(yōu)劣性進(jìn)行客觀評價。

綜合前人工作的不足之處，本文將分解策略引入副本布局問題的多目標(biāo)優(yōu)化中，提出了MDSRL算法。文件可用是副本技術(shù)的首要目標(biāo)，負(fù)載是否均衡將影響到系統(tǒng)的可靠性、穩(wěn)定性、吞吐量以及響應(yīng)時間，能耗問題在存儲系統(tǒng)中變得越來越突出，因此綜合考慮了平均文件不可用性、負(fù)載均衡和能耗三個目標(biāo)。分解策略能夠?qū)⑦@三個目標(biāo)分解成多個子問題同時進(jìn)行優(yōu)化，借助領(lǐng)域內(nèi)若干子問題提供的信息能夠快速找到一組在三個目標(biāo)上表現(xiàn)良好且分布性和收斂性較好的折衷解，并且實(shí)驗(yàn)證明了MDSRL算法能夠動態(tài)調(diào)整副本的個數(shù)，有效平衡了副本開銷和效能之間的矛盾。

相比于目前最優(yōu)的多目標(biāo)優(yōu)化算法MOE，本文所提出的算法考慮到了負(fù)載均衡和能耗兩個關(guān)鍵性指標(biāo)，并且本文所提出的算法在平均文件不可用性和能耗上能取得比MOE算法更好的表現(xiàn)，同時MDSRL得到的折衷解在分布性和收斂性上比MOE更好；相比于當(dāng)前優(yōu)化目標(biāo)個數(shù)最多的副本布局算法MORM，MDSRL并沒有優(yōu)化五個目標(biāo)，但是MDSRL在平均文件不可用性和負(fù)載均衡上比MORM取得更好的表現(xiàn)，同時在能耗問題上的表現(xiàn)隨著文件個數(shù)增多以后也能超過MORM，并且MORM不能得到一組折衷解，在某些目標(biāo)上的較大提升是以在其他目標(biāo)上的下降為代價，而MDSRL卻能得到一組折衷解。

綜上所述，本文所提出的算法在平均文件不可用性、負(fù)載均衡、能耗上都取得了相對不錯的表現(xiàn)，并且本文提出了一種新的折衷解的性能度量指標(biāo)方式，證明了本文所提出的算法比其他算法得到的折衷解在分布性和收斂性上更好。

3 系統(tǒng)模型和優(yōu)化目標(biāo)

3.1 問題定義

在云存儲系統(tǒng)的分布式集群中，假設(shè)有m個數(shù)據(jù)節(jié)點(diǎn)D1,D2,…,Dj,…,Dm，有n個文件F1,F2,…,Fi,…,Fn，需要存儲到這些數(shù)據(jù)節(jié)點(diǎn)上，副本布局策略就是將這n個文件合理部署到m個數(shù)據(jù)節(jié)點(diǎn)上，以使設(shè)定目標(biāo)函數(shù)的效能達(dá)到最優(yōu)。

根據(jù)上述對副本問題的定義，提出了基于多目標(biāo)分解策略的副本布局算法MDSRL，為不失一般性，現(xiàn)針對云存儲系統(tǒng)中的分布式場景做出如下假設(shè)：

（1）為了簡化問題，除了第一次寫入文件之后，后續(xù)對文件的訪問是“只讀”操作，并且對文件的每次訪問都是順序讀取的，不考慮其他訪問的形式。

（2）m個數(shù)據(jù)節(jié)點(diǎn)都是相互獨(dú)立且異構(gòu)的，節(jié)點(diǎn)存儲副本和請求訪問副本都是依賴于數(shù)據(jù)節(jié)點(diǎn)性能的，數(shù)據(jù)節(jié)點(diǎn)本身的性能指標(biāo)對于副本放置位置的選擇有著約束的作用。

（3）把文件作為一個整體考慮，但是對于更細(xì)的粒度比如文件塊，可以把每一個文件塊視作一個單獨(dú)的文件進(jìn)行處理，本文所提出的算法仍具有適用性。

3.2 多目標(biāo)優(yōu)化模型

副本的多目標(biāo)優(yōu)化問題可以由式（1）的數(shù)學(xué)模型所表示：

設(shè)Ω表示一個個體，Ω(i,j)為決策變量，在云存儲系統(tǒng)中，每個個體都表示n個文件的副本分配到m個數(shù)據(jù)節(jié)點(diǎn)的一種分配方案，因此每個個體都構(gòu)成了一個n×m階的矩陣，矩陣中的每個值采用二進(jìn)制的形式來表示，Ω(i,j)的值為1表示第i(i=1,2,…,n)個文件的副本存儲到了第j(j=1,2,…,m)個數(shù)據(jù)節(jié)點(diǎn)上，值為0表示未存儲。表1描述了個體的一個樣例。每一行表示了一個文件在不同數(shù)據(jù)節(jié)點(diǎn)之間的副本布局策略，每一行的和表示該行所代表的一個文件的副本因子。

Table 1 Binary representation of individual表1 個體的二進(jìn)制表示

當(dāng)一個個體滿足以下兩個約束條件（可行域）時稱之為可行解。

（2）每一個數(shù)據(jù)節(jié)點(diǎn)上所有文件的大小之和必須小于該數(shù)據(jù)節(jié)點(diǎn)的總?cè)萘?，即對?j∈{1,2,…,m}，都有，其中CPj表示數(shù)據(jù)節(jié)點(diǎn)的容量。

因此，當(dāng)一個個體只要不滿足上述約束條件的任意一個（不在可行域內(nèi)），該個體便是不可行解。

3.3 優(yōu)化目標(biāo)

多目標(biāo)優(yōu)化問題（multi-objective optimization problems，MOP）和單目標(biāo)優(yōu)化問題（single-objective optimization problem，SOP）的不同在于多目標(biāo)優(yōu)化往往得不到滿足所有目標(biāo)函數(shù)的全局最優(yōu)解，因?yàn)槟繕?biāo)之間可能存在相互沖突[16]，比如為了最小化文件不可用性需要創(chuàng)建更多的副本，但是更多副本數(shù)又會增加系統(tǒng)的能耗，與最小化系統(tǒng)能耗的目標(biāo)相矛盾。因此，本文試圖通過求得一組折衷的解來平衡沖突的目標(biāo)，從而得到在各個目標(biāo)上都表現(xiàn)良好的折衷方案。多目標(biāo)優(yōu)化所得的解是根據(jù)待優(yōu)化目標(biāo)的函數(shù)值來不斷迭代演化得到的，因此待優(yōu)化目標(biāo)的目標(biāo)函數(shù)表示決定了進(jìn)化的方向。下面將詳細(xì)給出平均文件不可用性（mean file unavailability，MFU）、負(fù)載均衡（load variance，LV）、能耗（energy consumption，EC）三個目標(biāo)函數(shù)的表示。

3.3.1 平均文件不可用性（MFU）

文件的可用性要考慮到數(shù)據(jù)節(jié)點(diǎn)的失效率以及該數(shù)據(jù)節(jié)點(diǎn)的鏈路失效率。Ω(i,j)為決策變量，當(dāng)文件Fi放置到數(shù)據(jù)節(jié)點(diǎn)Dj上時，令Ω(i,j)等于1，否則為0，設(shè)pj為數(shù)據(jù)節(jié)點(diǎn)Nj(1 ≤j≤m)發(fā)生故障的概率，設(shè)μj為數(shù)據(jù)節(jié)點(diǎn)Dj(1 ≤j≤m)連接的鏈路出現(xiàn)故障的概率，設(shè)數(shù)據(jù)節(jié)點(diǎn)和所連接鏈路的故障率初始時是隨機(jī)生成的。某個文件的一個副本不可用的情形是該副本所在數(shù)據(jù)節(jié)點(diǎn)出現(xiàn)故障或者連接該數(shù)據(jù)節(jié)點(diǎn)的鏈路發(fā)生故障。由于每個文件都有相應(yīng)的副本，并且每個副本都分布于不同的數(shù)據(jù)節(jié)點(diǎn)上，因此某個文件不可用當(dāng)且僅當(dāng)這一文件的所有副本都不可用。因?yàn)槊總€副本都是獨(dú)立同分布的，文件Fi不可用性可以由式（2）計算：

其中，∏*表示為非零元素（即Fi存在于數(shù)據(jù)節(jié)點(diǎn)Dj上）的累積乘。

一個系統(tǒng)數(shù)據(jù)可用是當(dāng)且僅當(dāng)所有的文件都可用，而文件可用性P(Fi)可由得到。因此系統(tǒng)數(shù)據(jù)可用性（system availability，SA）的計算如式（3）所示：

為了和多目標(biāo)優(yōu)化問題中大多數(shù)優(yōu)化目標(biāo)保持一致的優(yōu)化方向，最大化系統(tǒng)可用性可以轉(zhuǎn)化為最小化平均文件不可用性。因此，平均文件不可用性的目標(biāo)函數(shù)MFU的計算如式（4）所示：

3.3.2 負(fù)載變化（LV）

負(fù)載均衡能夠由負(fù)載變化來度量。由于標(biāo)準(zhǔn)差能夠衡量數(shù)據(jù)的離散程度并與數(shù)據(jù)的量綱一致，因此數(shù)據(jù)節(jié)點(diǎn)的負(fù)載變化可以用負(fù)載的標(biāo)準(zhǔn)差來表示，并作為衡量系統(tǒng)負(fù)載均衡的標(biāo)準(zhǔn)。負(fù)載的標(biāo)準(zhǔn)差值越小，表明負(fù)載均衡能力越強(qiáng)，根據(jù)文獻(xiàn)[17]，數(shù)據(jù)節(jié)點(diǎn)Dj上文件Fi的負(fù)載L(i,j)值等于其訪問速率和服務(wù)時間的乘積[17]，因此L(i,j)可以由式（5）計算而得：

其中，V(i,j)是訪問數(shù)據(jù)節(jié)點(diǎn)Dj時對文件Fi讀請求的訪問速率。如果該數(shù)據(jù)節(jié)點(diǎn)上不存在文件Fi，則讓V(i,j)=0。ST(i,j)為文件Fi在數(shù)據(jù)節(jié)點(diǎn)Dj上的服務(wù)時間，其計算方法如式（6）所示：

其中，Si是文件Fi的大小，TSj是數(shù)據(jù)節(jié)點(diǎn)Dj的傳輸速率。

數(shù)據(jù)節(jié)點(diǎn)Dj的負(fù)載可以由在其上所有文件的負(fù)載之和得到，如式（7）所示：

那么，系統(tǒng)的平均負(fù)載就可進(jìn)一步表示為式（8）：

負(fù)載變化目標(biāo)函數(shù)LV可以由標(biāo)準(zhǔn)差計算公式得到，如式（9）所示：

3.3.3 能耗（EC）

可再生能耗（renewable energy consumption，RE）和制冷能耗（cooling energy consumption，CE）占據(jù)系統(tǒng)總能耗的很大一部分，其他的部分可以忽略不計[18]。因此為了在最大程度上縮減能耗，就必須最小化RE和CE。文獻(xiàn)[19]表明，服務(wù)器的能耗能夠通過功率消耗和使用率之間的近似線性關(guān)系來進(jìn)行較高準(zhǔn)確率的度量[19]。本文使用了文獻(xiàn)[9]中比較不同類型服務(wù)器的功耗圖，它通過服務(wù)器端的Java程序分別測得系統(tǒng)CPU負(fù)載從10%到100%的功耗，圖1中描述了本文中數(shù)據(jù)節(jié)點(diǎn)所使用的不同服務(wù)器的功耗隨著負(fù)載率變化的曲線。

Fig.1 Power consumption by selected servers at different load levels圖1 服務(wù)器在不同級別的功耗

負(fù)載率的計算如式（10）所示：

式中，L*(j)是數(shù)據(jù)節(jié)點(diǎn)Dj上的峰值負(fù)載，其實(shí)際負(fù)載率可以由轉(zhuǎn)化為目前在Dj上所有文件的容量在整個節(jié)點(diǎn)的容量占比來進(jìn)行計算，如式（11）所示：

設(shè)ERE(j)為數(shù)據(jù)節(jié)點(diǎn)Dj的計算機(jī)設(shè)備所消耗的可再生能源。ERE(j)的計算如式（12）所示：

其中，Pmax(j)表示數(shù)據(jù)節(jié)點(diǎn)Dj在處于負(fù)載率為100%時所消耗的功率，而Pidle(j)表示數(shù)據(jù)節(jié)點(diǎn)Dj處于負(fù)載率為0時所消耗的功率。因此，系統(tǒng)中數(shù)據(jù)節(jié)點(diǎn)所消耗的總功率如式（13）所示：

系統(tǒng)的能耗有一部分會轉(zhuǎn)化為熱能。設(shè)Γ表示數(shù)據(jù)節(jié)點(diǎn)的性能系數(shù)（coefficient of performance，COP）。COP越高，表示數(shù)據(jù)節(jié)點(diǎn)的冷卻系統(tǒng)效率更高。COP主要取決于室內(nèi)和室外的溫度兩個因素（Tin和Tout）。Γ的計算如式（14）所示：

在本文中,設(shè)Tout=36，Tin=26。設(shè)ECE(j)表示數(shù)據(jù)節(jié)點(diǎn)Nj的制冷能耗，那么有：

每個數(shù)據(jù)節(jié)點(diǎn)的制冷能耗之和就是系統(tǒng)總的制冷能耗。因此，總的制冷能耗可以用式（16）表示：

那么，系統(tǒng)總的能耗（system energy consumption，SEC）就由系統(tǒng)總的可再生能耗和總的制冷能耗之和所表示，可以由式（17）計算而得：

因此，能耗目標(biāo)函數(shù)EC可用式（18）表示：

4 基于多目標(biāo)分解策略的副本布局算法

4.1 基本定義

定義1一個多目標(biāo)優(yōu)化問題可以描述如下：

這里Ω是決策空間，F(xiàn):Ω→Rt包含t個實(shí)值目標(biāo)函數(shù)，Rt被稱為目標(biāo)空間?？蓪?shí)現(xiàn)的目標(biāo)集合被定義為{F(x)|x∈Ω}。

定義2對于最小化多目標(biāo)問題，對于n個目標(biāo)分量fi(x)，i=1～n，任意給定兩個決策變量xa、xb，如果有以下兩個條件成立，則稱xa支配xb,表示為xa?xb。

（1）對于?i∈{1,2,…,n}，都有fi(xa)≤fi(xb)成立。

（2）?i∈{1,2,…,n}，使得fi(xa)＜fi(xb)成立。

如果對于一個決策變量x*∈Ω是Pareto最優(yōu)解，當(dāng)且僅當(dāng)不存在決策變量x∈Ω使得x?x*。Pareto最優(yōu)解集是所有Pareto最優(yōu)解的集合，帕累托前沿指的是Pareto最優(yōu)解集對應(yīng)的目標(biāo)函數(shù)值的向量空間。

定義3切比雪夫數(shù)學(xué)模型如下：

z*=是參考點(diǎn)，對于任意i=1,2,…,t,,對于每一個Pareto最優(yōu)解x*就存在一個權(quán)重向量λ使得其為此問題的最優(yōu)解，因此通過改變權(quán)重向量就能獲得不同的Pareto最優(yōu)解。

定義4設(shè)解集X是Pareto前沿面的近似解集，是目標(biāo)空間的一個參考點(diǎn)，對于任意i=1,2,…,t,，它被解集X中所有目標(biāo)向量支配。那么關(guān)于參考點(diǎn)r*的超體積（hypervolume，HV）指的是被解集X所支配且以參考點(diǎn)r*為邊界的目標(biāo)空間的體積，如式（21）所示：

超體積能夠在某種程度上綜合反映解集的收斂性和多樣性，HV值越大表明生成的解越好。用超體積的量化指標(biāo)能夠看到在一種算法上生成解集的好壞。因?yàn)椴煌乃惴ㄉ傻慕饧遣煌?，所以r*不同將導(dǎo)致在不同方法上生成的解集無法進(jìn)行優(yōu)劣性比較。因此本文將結(jié)合切比雪夫方法中的參考點(diǎn)z*來進(jìn)行綜合評判，新的度量指標(biāo)超體積占比HVA的計算如式（22）所示：

HV(X,z*)是關(guān)于參考點(diǎn)z*的HV，HVA指的是解集X關(guān)于參考點(diǎn)r*的HV值占其關(guān)于參考點(diǎn)z*和r*的HV值之和的比例，HVA越大，說明解集X越好。

定義5根據(jù)種群個數(shù)N，MDSRL將多目標(biāo)優(yōu)化問題分解為N個子問題，同時生成N組均勻分布的權(quán)重向量，一個權(quán)重向量的鄰域被定義為離它最近的幾個權(quán)重向量的集合，通過鄰域的信息來更新權(quán)重向量獲得不同的Pareto最優(yōu)解。通過切比雪夫模型能夠?qū)areto近似的子問題轉(zhuǎn)化為標(biāo)量子問題，不斷逼近參考點(diǎn)來獲得更好的Pareto最優(yōu)解。

4.2 算法流程

MDSRL的算法結(jié)構(gòu)是基于MOEA/D算法的，下面是算法的詳細(xì)過程：

算法1MDSRL

步驟1在第1代時，先隨機(jī)生成N個個體作為初始的種群P。由于個體是隨機(jī)創(chuàng)建的，它可能不滿足之前所定義的容量約束和完整性約束條件，因此要進(jìn)行可行性檢查和做相應(yīng)的修復(fù)來滿足約束條件，使得所有產(chǎn)生的個體都是可行解。同時要產(chǎn)生一組均勻分布的權(quán)重向量代表各個子問題的進(jìn)化方向。

步驟2根據(jù)每個個體權(quán)重向量之間歐氏距離的大小來選取最近的T個個體作為鄰域，把初始種群中個體在三個目標(biāo)函數(shù)上的最小值作為參考點(diǎn)Z*，最大值作為參考點(diǎn)R*。

步驟3從鄰域中隨機(jī)選擇兩個個體K、L并使用遺傳算子交叉和變異操作進(jìn)行處理，對交叉變異后的子代進(jìn)行可行性檢查，修復(fù)不可行的個體，利用子代中的兩個個體與Z*和R*中的函數(shù)值比較，更新Z*和R*，然后在子代中找出非支配解β。

步驟4采用切比雪夫方法使得個體不斷向著參考點(diǎn)Z*逼近，使得解不斷向著最優(yōu)的方向進(jìn)化。同時將每次得到非支配解β與外部種群中的解進(jìn)行比較，從EP中移除所有被β支配的解，如果EP中的向量都不支配β，那么將β加入到EP中。

步驟5遍歷種群中的個體，不斷更新鄰域解、Z*、R*以及EP的值。

步驟6若gen≤G，則gen=gen+1，把步驟4中得到的種群作為新的種群，然后轉(zhuǎn)步驟3；否則達(dá)到停止條件，算法結(jié)束。

4.3 MDSRL的時間復(fù)雜度分析

對于給定的數(shù)據(jù)節(jié)點(diǎn)集D={D1,D2,…,Dj,…,Dm}，文件集F={F1,F2,…,Fi,…,Fn}，設(shè)初始種群中的個體數(shù)為N，最大代數(shù)為G，生成初始種群共花費(fèi)了O(Nn+Nm)的時間復(fù)雜度，尋找相鄰的若干個個體的時間復(fù)雜度花費(fèi)為O(N2),尋找參考點(diǎn)Z*和R*用了O(N)的時間，交叉變異操作花費(fèi)了O(mn)的時間復(fù)雜度，更新領(lǐng)域解花費(fèi)了2O(3T)的時間復(fù)雜度，更新EP花費(fèi)了O(N)的時間復(fù)雜度，由于遺傳代數(shù)為G，因此MDSRL算法的最壞時間復(fù)雜度為O(Nn+Nm)+O(N2)+O(N)+(O(mn)+2O(3T)+O(N))NG=O(GN2+GNmn+GNT+N(m+n)+N2)。由于G、N、T都是事先配置的常量，不算在時間的復(fù)雜度中，因此MDSRL的最壞時間復(fù)雜度為O(mn)。

5 模擬實(shí)驗(yàn)和分析

為了模擬和驗(yàn)證本文所提出基于多目標(biāo)分解策略的副本放置算法MDSRL的有效性，本章完成了一系列的模擬實(shí)驗(yàn)，利用Python3對該算法進(jìn)行了實(shí)現(xiàn)和驗(yàn)證，處理器為Intel?CoreTMi5-7400M@3 GHz，內(nèi)存為8 GB DDR4 SDRAM，硬盤為128 GB SSD，操作系統(tǒng)是Windows 10/64 bit。

5.1 實(shí)驗(yàn)參數(shù)設(shè)置

表2描述了實(shí)驗(yàn)中所采用的數(shù)據(jù)節(jié)點(diǎn)的配置參數(shù)。根據(jù)Long等[9]的工作，本文模擬了文件在8個數(shù)據(jù)節(jié)點(diǎn)之間的指派問題。提出的MDSRL算法中使用到的參數(shù)值如表3所示。在模擬實(shí)驗(yàn)中，由于假設(shè)的是“只讀”操作，因此不用考慮數(shù)據(jù)的一致性怎么維護(hù)以及寫操作所帶來的開銷。為了能夠更好模擬云系統(tǒng)的訪問行為，根據(jù)Xie等[20]提出的偽負(fù)載生成器建立一個符合文件訪問規(guī)律的負(fù)載生成器，能夠生成文件和請求。

Table 2 Data node configurations表2 數(shù)據(jù)節(jié)點(diǎn)配置

Table 3 MDSRL configurations表3 MDSRL的配置

5.2 實(shí)驗(yàn)結(jié)果分析

本文的實(shí)驗(yàn)是用MDSRL算法解決分布式存儲系統(tǒng)中副本的多目標(biāo)優(yōu)化問題，同時和前面提到的MOE和MORM算法進(jìn)行對比，圖2展示了這三個算法的最后一代個體在MFU-LV-EC三維空間坐標(biāo)上的分布圖。

Fig.2 MFU-LV-EC objective space圖2 MFU-LV-EC目標(biāo)空間

從圖2中可以發(fā)現(xiàn)MDSRL和MOE都能夠生成一組折衷解，但是MORM只能生成一個最優(yōu)解，這是因?yàn)镸ORM將多目標(biāo)優(yōu)化轉(zhuǎn)化為了單目標(biāo)優(yōu)化，但是單目標(biāo)優(yōu)化通常只會產(chǎn)生單個最優(yōu)解，而MDSRL采用的MOEA/D和MOE采用的NSGA-II都是多目標(biāo)進(jìn)化算法，因此能夠得到一組折衷解。從圖2中可以看出，相比MOE，MDSRL能夠?qū)ふ业礁蛹杏诘捉歉浇膫€體，即那些具有低平均文件不可用性、低負(fù)載變化和低能耗的個體。這能夠在一定程度上說明MDSRL能夠比MOE取得更好的一組折衷解。為了更加精準(zhǔn)地度量MDSRL和MOE生成的一組折衷解的優(yōu)劣程度，本文采用上文中提出的HVA指標(biāo)進(jìn)行評判，它能夠?qū)DSRL和MOE生成的一組折衷解的收斂性和多樣性進(jìn)行評價，HVA值越大，說明生成的一組折衷解的收斂性和多樣性越好。圖3是MDSRL和MOE的HVA值隨文件總數(shù)變化時發(fā)生改變的折線圖。

Fig.3 HVA comparison圖3 HVA值比較

從圖3可以看出，MDSRL的HVA值始終保持穩(wěn)定而且十分接近于1，這能夠說明隨著文件總數(shù)的增加，MDSRL生成的一組解的均勻性和收斂性始終較好，而MOE算法的HVA值隨著文件總數(shù)的增加并不穩(wěn)定，并且始終比MDSRL的HVA值低，這說明MOE生成的折衷解在均勻性和收斂性上沒有MDSRL好，并且隨著文件總數(shù)的增加，解的均勻性和收斂性不能得到保證。

圖4描述了MDSRL、MOE和MORM生成的最終解相比開始初始化生成的解在三個目標(biāo)上效能的平均提升比例。由于初始化得到的是一組解，而MDSRL以及MOE最后生成的也都是一組解，因此取這些解的平均值，然后再與MORM得到的一個最優(yōu)解進(jìn)行比較?？梢钥闯鯩DSRL在平均文件不可用性上以及能耗上優(yōu)于MOE，但是在負(fù)載均衡上稍遜于MOE。MDSRL在平均文件不可用性和負(fù)載均衡上優(yōu)于MORM，但是在能耗上稍遜于MORM。另外，從圖4中可以看到MORM在平均文件可用性上的提升比例為負(fù)數(shù)，這是因?yàn)镸ORM對目標(biāo)函數(shù)進(jìn)行線性加權(quán)時沒有對目標(biāo)函數(shù)進(jìn)行歸一化并且采用的權(quán)重比例相同，這會導(dǎo)致數(shù)量級高的目標(biāo)函數(shù)實(shí)際的權(quán)重更大。由于能耗的數(shù)量級是最大的，導(dǎo)致MORM在能耗上的表現(xiàn)比MDSRL和MOE更好，但是在文件可用性和負(fù)載均衡上表現(xiàn)比MDSRL和MOE都差，甚至在文件可用性上的效能提升比例為負(fù)數(shù)，這是因?yàn)槲募捎眯缘臄?shù)量級最小。減少能耗是以增大平均文件不可用性為代價，導(dǎo)致不能生成一個折衷解。

Fig.4 Efficiency of performance improvement圖4 效能提升比例

圖5將提出的三種算法在副本因子上進(jìn)行了比較，發(fā)現(xiàn)相比現(xiàn)有的分布式文件系統(tǒng)都將副本因子設(shè)置為3，MDSRL、MOE和MORM都是根據(jù)文件自身的特征進(jìn)行動態(tài)變化。從前面的實(shí)驗(yàn)結(jié)果分析可知，相比直接固定副本的個數(shù)，動態(tài)調(diào)整文件的副本數(shù)目能夠有效提高系統(tǒng)的效能。

Fig.5 Comparison of replication factor圖5 副本因子比較

圖6（a）到圖6（c）分別描述了三種算法在平均文件不可用性、負(fù)載變化和能耗三個目標(biāo)的效能比較情況。

圖6（a）描述了MDSRL能夠比MOE和MORM取得更小的平均文件不可用性，相比MOE和MORM，它分別減少了3.11個百分點(diǎn)和68.1個百分點(diǎn)的平均文件不可用性。

圖6（b）描述了MDSRL在負(fù)載變化目標(biāo)方面稍遜于MOE，稍優(yōu)于MORM，它比MOE增加了1.3個百分點(diǎn)，比MORM減少了0.2個百分點(diǎn)。

圖6（c）描述了MDSRL在能耗方面優(yōu)于MOE，稍遜于MORM，它比MOE減少了2.3個百分點(diǎn)的能量消耗，比MORM多了0.8個百分點(diǎn)的能量消耗，當(dāng)文件個數(shù)越來越多的時候，MDSRL的能耗反而會比MORM少，可見隨著文件個數(shù)的增加，MDSRL的節(jié)能效果更明顯。從圖6（c）可以看出，當(dāng)文件個數(shù)達(dá)到300個時，MDSRL比MORM減少了0.9個百分點(diǎn)的能量消耗。

從圖6（a）到圖6（c），可以觀察到MDSRL比MOE在平均文件不可用性以及能耗上能夠取得更好的效能，在平均文件不可用性以及負(fù)載均衡上比MORM更優(yōu)，在文件個數(shù)較少的時候比MORM在能耗上效能略差，但是當(dāng)文件總數(shù)增多之后能夠在能耗上取得比MORM更好的效能。

Fig.6 Efficiency comparison圖6 效能比較

綜上所述，MDSRL在三個目標(biāo)上至少有兩個目標(biāo)比MOE和MORM更優(yōu)，在另一個目標(biāo)上稍遜或者基本相當(dāng)，因此MDSRL在三個目標(biāo)上都能取得不錯的表現(xiàn)，且所求的一組折衷解在分布性和收斂性上更好。

6 結(jié)束語

本文主要考慮包括副本因子和副本放置策略在內(nèi)的副本布局問題，為了解決副本帶來的效能提升和能耗之間的沖突，提出了一種基于多目標(biāo)分解策略的副本布局算法MDSRL，對平均文件不可用性、負(fù)載均衡、能耗三個目標(biāo)進(jìn)行優(yōu)化，利用分解策略將多目標(biāo)優(yōu)化問題分解成多個標(biāo)量子問題同時進(jìn)行優(yōu)化，試圖尋找一組在這三個目標(biāo)上都能取得良好效果的折衷解。實(shí)驗(yàn)結(jié)果表明，MDSRL至少在兩個目標(biāo)上都能取得比MOE和MORM更好的表現(xiàn)，且生成的折衷解的分布性和收斂性更好。當(dāng)多目標(biāo)個數(shù)多于三個時，種群中非支配解的個數(shù)急劇增加，很難得到一組在各個目標(biāo)上都表現(xiàn)良好的折衷解，因此在未來的工作中將進(jìn)一步研究超高維多目標(biāo)的副本布局優(yōu)化模型，以探尋更合適的副本布局多目標(biāo)優(yōu)化算法。