邵必林，賀金能，邊根慶

1.西安建筑科技大學管理學院，西安 710055

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

1 引言

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

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

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

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

本文的主要貢獻如下：

（1）構建了文件可用性、負載均衡以及能量消耗三個目標的目標函數并建立了多目標函數模型。

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

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

2 相關工作

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

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

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

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

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

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

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

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

3.1 問題定義

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

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

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

（2）m個數據節(jié)點都是相互獨立且異構的，節(jié)點存儲副本和請求訪問副本都是依賴于數據節(jié)點性能的，數據節(jié)點本身的性能指標對于副本放置位置的選擇有著約束的作用。

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

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

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

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

Table 1 Binary representation of individual表1 個體的二進制表示

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

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

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

3.3 優(yōu)化目標

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

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

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

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

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

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

3.3.2 負載變化（LV）

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

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

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

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

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

負載變化目標函數LV可以由標準差計算公式得到，如式（9）所示：

3.3.3 能耗（EC）

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

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

負載率的計算如式（10）所示：

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

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

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

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

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

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

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

因此，能耗目標函數EC可用式（18）表示：

4 基于多目標分解策略的副本布局算法

4.1 基本定義

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

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

定義2對于最小化多目標問題，對于n個目標分量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)解，當且僅當不存在決策變量x∈Ω使得x?x*。Pareto最優(yōu)解集是所有Pareto最優(yōu)解的集合，帕累托前沿指的是Pareto最優(yōu)解集對應的目標函數值的向量空間。

定義3切比雪夫數學模型如下：

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

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

超體積能夠在某種程度上綜合反映解集的收斂性和多樣性，HV值越大表明生成的解越好。用超體積的量化指標能夠看到在一種算法上生成解集的好壞。因為不同的算法生成的解集是不同的，所以r*不同將導致在不同方法上生成的解集無法進行優(yōu)劣性比較。因此本文將結合切比雪夫方法中的參考點z*來進行綜合評判，新的度量指標超體積占比HVA的計算如式（22）所示：

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

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

4.2 算法流程

MDSRL的算法結構是基于MOEA/D算法的，下面是算法的詳細過程：

算法1MDSRL

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

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

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

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

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

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

4.3 MDSRL的時間復雜度分析

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

5 模擬實驗和分析

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

5.1 實驗參數設置

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

Table 2 Data node configurations表2 數據節(jié)點配置

Table 3 MDSRL configurations表3 MDSRL的配置

5.2 實驗結果分析

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

Fig.2 MFU-LV-EC objective space圖2 MFU-LV-EC目標空間

從圖2中可以發(fā)現(xiàn)MDSRL和MOE都能夠生成一組折衷解，但是MORM只能生成一個最優(yōu)解，這是因為MORM將多目標優(yōu)化轉化為了單目標優(yōu)化，但是單目標優(yōu)化通常只會產生單個最優(yōu)解，而MDSRL采用的MOEA/D和MOE采用的NSGA-II都是多目標進化算法，因此能夠得到一組折衷解。從圖2中可以看出，相比MOE，MDSRL能夠尋找到更加集中于底角附近的個體，即那些具有低平均文件不可用性、低負載變化和低能耗的個體。這能夠在一定程度上說明MDSRL能夠比MOE取得更好的一組折衷解。為了更加精準地度量MDSRL和MOE生成的一組折衷解的優(yōu)劣程度，本文采用上文中提出的HVA指標進行評判，它能夠對MDSRL和MOE生成的一組折衷解的收斂性和多樣性進行評價，HVA值越大，說明生成的一組折衷解的收斂性和多樣性越好。圖3是MDSRL和MOE的HVA值隨文件總數變化時發(fā)生改變的折線圖。

Fig.3 HVA comparison圖3 HVA值比較

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

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

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

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

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

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

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

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

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

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

Fig.6 Efficiency comparison圖6 效能比較

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

6 結束語

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