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

邵必林，賀金能，邊根慶

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

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

1 引言

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

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

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

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

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

（1）構(gòu)建了文件可用性、負(fù)載均衡以及能量消耗三個(gè)目標(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àn)維網(wǎng)、P2P（peer to peer）系統(tǒng)、分布式系統(tǒng)以及云存儲(chǔ)系統(tǒng)中得到了廣泛的應(yīng)用[11-12]，甚至在物聯(lián)網(wǎng)中也逐漸被使用[13]。因此副本布局的研究被越來(lái)越多的學(xué)者所重視[14-15]。

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

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

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

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

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

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

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

3.1 問(wèn)題定義

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

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

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

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

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

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

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

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

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

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

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

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

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

多目標(biāo)優(yōu)化問(wèn)題（multi-objective optimization problems，MOP）和單目標(biāo)優(yōu)化問(wèn)題（single-objective optimization problem，SOP）的不同在于多目標(biāo)優(yōu)化往往得不到滿足所有目標(biāo)函數(shù)的全局最優(yōu)解，因?yàn)槟繕?biāo)之間可能存在相互沖突[16]，比如為了最小化文件不可用性需要?jiǎng)?chuàng)建更多的副本，但是更多副本數(shù)又會(huì)增加系統(tǒng)的能耗，與最小化系統(tǒng)能耗的目標(biāo)相矛盾。因此，本文試圖通過(guò)求得一組折衷的解來(lái)平衡沖突的目標(biāo)，從而得到在各個(gè)目標(biāo)上都表現(xiàn)良好的折衷方案。多目標(biāo)優(yōu)化所得的解是根據(jù)待優(yōu)化目標(biāo)的函數(shù)值來(lái)不斷迭代演化得到的，因此待優(yōu)化目標(biāo)的目標(biāo)函數(shù)表示決定了進(jìn)化的方向。下面將詳細(xì)給出平均文件不可用性（mean file unavailability，MFU）、負(fù)載均衡（load variance，LV）、能耗（energy consumption，EC）三個(gè)目標(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上時(shí)，令Ω(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)和所連接鏈路的故障率初始時(shí)是隨機(jī)生成的。某個(gè)文件的一個(gè)副本不可用的情形是該副本所在數(shù)據(jù)節(jié)點(diǎn)出現(xiàn)故障或者連接該數(shù)據(jù)節(jié)點(diǎn)的鏈路發(fā)生故障。由于每個(gè)文件都有相應(yīng)的副本，并且每個(gè)副本都分布于不同的數(shù)據(jù)節(jié)點(diǎn)上，因此某個(gè)文件不可用當(dāng)且僅當(dāng)這一文件的所有副本都不可用。因?yàn)槊總€(gè)副本都是獨(dú)立同分布的，文件Fi不可用性可以由式（2）計(jì)算：

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

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

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

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

負(fù)載均衡能夠由負(fù)載變化來(lái)度量。由于標(biāo)準(zhǔn)差能夠衡量數(shù)據(jù)的離散程度并與數(shù)據(jù)的量綱一致，因此數(shù)據(jù)節(jié)點(diǎn)的負(fù)載變化可以用負(fù)載的標(biāo)準(zhǔn)差來(lái)表示，并作為衡量系統(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èn)速率和服務(wù)時(shí)間的乘積[17]，因此L(i,j)可以由式（5）計(jì)算而得：

其中，V(i,j)是訪問(wèn)數(shù)據(jù)節(jié)點(diǎn)Dj時(shí)對(duì)文件Fi讀請(qǐng)求的訪問(wèn)速率。如果該數(shù)據(jù)節(jié)點(diǎn)上不存在文件Fi，則讓V(i,j)=0。ST(i,j)為文件Fi在數(shù)據(jù)節(jié)點(diǎn)Dj上的服務(wù)時(shí)間，其計(jì)算方法如式（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)差計(jì)算公式得到，如式（9）所示：

3.3.3 能耗（EC）

可再生能耗（renewable energy consumption，RE）和制冷能耗（cooling energy consumption，CE）占據(jù)系統(tǒng)總能耗的很大一部分，其他的部分可以忽略不計(jì)[18]。因此為了在最大程度上縮減能耗，就必須最小化RE和CE。文獻(xiàn)[19]表明，服務(wù)器的能耗能夠通過(guò)功率消耗和使用率之間的近似線性關(guān)系來(lái)進(jìn)行較高準(zhǔn)確率的度量[19]。本文使用了文獻(xiàn)[9]中比較不同類型服務(wù)器的功耗圖，它通過(guò)服務(wù)器端的Java程序分別測(cè)得系統(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ù)器在不同級(jí)別的功耗

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

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

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

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

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

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

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

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

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

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

4.1 基本定義

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

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

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

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

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

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

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

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

定義4設(shè)解集X是Pareto前沿面的近似解集，是目標(biāo)空間的一個(gè)參考點(diǎn)，對(duì)于任意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)椴煌乃惴ㄉ傻慕饧遣煌模詒*不同將導(dǎo)致在不同方法上生成的解集無(wú)法進(jìn)行優(yōu)劣性比較。因此本文將結(jié)合切比雪夫方法中的參考點(diǎn)z*來(lái)進(jìn)行綜合評(píng)判，新的度量指標(biāo)超體積占比HVA的計(jì)算如式（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越大，說(shuō)明解集X越好。

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

4.2 算法流程

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

算法1MDSRL

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

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

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

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

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

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

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

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

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

為了模擬和驗(yàn)證本文所提出基于多目標(biāo)分解策略的副本放置算法MDSRL的有效性，本章完成了一系列的模擬實(shí)驗(yàn)，利用Python3對(duì)該算法進(jìn)行了實(shí)現(xiàn)和驗(yàn)證，處理器為Intel?CoreTMi5-7400M@3 GHz，內(nèi)存為8 GB DDR4 SDRAM，硬盤(pán)為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個(gè)數(shù)據(jù)節(jié)點(diǎn)之間的指派問(wèn)題。提出的MDSRL算法中使用到的參數(shù)值如表3所示。在模擬實(shí)驗(yàn)中，由于假設(shè)的是“只讀”操作，因此不用考慮數(shù)據(jù)的一致性怎么維護(hù)以及寫(xiě)操作所帶來(lái)的開(kāi)銷。為了能夠更好模擬云系統(tǒng)的訪問(wèn)行為，根據(jù)Xie等[20]提出的偽負(fù)載生成器建立一個(gè)符合文件訪問(wèn)規(guī)律的負(fù)載生成器，能夠生成文件和請(qǐng)求。

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算法解決分布式存儲(chǔ)系統(tǒng)中副本的多目標(biāo)優(yōu)化問(wèn)題，同時(shí)和前面提到的MOE和MORM算法進(jìn)行對(duì)比，圖2展示了這三個(gè)算法的最后一代個(gè)體在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只能生成一個(gè)最優(yōu)解，這是因?yàn)镸ORM將多目標(biāo)優(yōu)化轉(zhuǎn)化為了單目標(biāo)優(yōu)化，但是單目標(biāo)優(yōu)化通常只會(huì)產(chǎn)生單個(gè)最優(yōu)解，而MDSRL采用的MOEA/D和MOE采用的NSGA-II都是多目標(biāo)進(jìn)化算法，因此能夠得到一組折衷解。從圖2中可以看出，相比MOE，MDSRL能夠?qū)ふ业礁蛹杏诘捉歉浇膫€(gè)體，即那些具有低平均文件不可用性、低負(fù)載變化和低能耗的個(gè)體。這能夠在一定程度上說(shuō)明MDSRL能夠比MOE取得更好的一組折衷解。為了更加精準(zhǔn)地度量MDSRL和MOE生成的一組折衷解的優(yōu)劣程度，本文采用上文中提出的HVA指標(biāo)進(jìn)行評(píng)判，它能夠?qū)DSRL和MOE生成的一組折衷解的收斂性和多樣性進(jìn)行評(píng)價(jià)，HVA值越大，說(shuō)明生成的一組折衷解的收斂性和多樣性越好。圖3是MDSRL和MOE的HVA值隨文件總數(shù)變化時(shí)發(fā)生改變的折線圖。

Fig.3 HVA comparison圖3 HVA值比較

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

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

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)行動(dòng)態(tài)變化。從前面的實(shí)驗(yàn)結(jié)果分析可知，相比直接固定副本的個(gè)數(shù)，動(dòng)態(tài)調(diào)整文件的副本數(shù)目能夠有效提高系統(tǒng)的效能。

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

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

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

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

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

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

Fig.6 Efficiency comparison圖6 效能比較

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

6 結(jié)束語(yǔ)

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