靜態(tài)場景下HDFS副本放置的改進(jìn)策略

鮑敬源，趙 寧，汪 洋

（1.海裝武漢局駐武漢地區(qū)第二軍事代表處，湖北武漢 430064；2.武漢理工大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，湖北 武漢 430070；3.貝殼找房科技有限公司，北京 100089）

0 引言

云存儲系統(tǒng)［1-2］在大數(shù)據(jù)時(shí)代發(fā)揮著越來越重要的作用。作為云計(jì)算平臺Hadoop 的存儲模塊，HDFS 采取了多副本記憶數(shù)據(jù)檢測和快速恢復(fù)機(jī)制，其默認(rèn)的副本放置策略為機(jī)架感知（rack-aware），即動態(tài)感知集群拓?fù)浣Y(jié)構(gòu)的變化，默認(rèn)副本因子為3。該策略的缺點(diǎn)在于：沒有充分考慮異構(gòu)環(huán)境中各節(jié)點(diǎn)的差異（特別是在靜態(tài)場景下對時(shí)間要求不高），沒有根據(jù)節(jié)點(diǎn)情況充分優(yōu)化放置策略。針對這一問題，本文提出靜態(tài)場景下結(jié)合二進(jìn)制灰狼優(yōu)化算法的改進(jìn)版多目標(biāo)灰狼優(yōu)化算法，以集群讀取效率、整體負(fù)載均衡度、平均副本失效率為目標(biāo)函數(shù)進(jìn)行優(yōu)化，減小了陷入局部最優(yōu)的概率，增加了解的多樣性，從而以一定時(shí)間成本得出在上述3 項(xiàng)指標(biāo)上效果更好的方案。

1 相關(guān)工作

HDFS 副本放置分為靜態(tài)和動態(tài)兩種場景，前者即文件分批次處理，對時(shí)間要求不高，優(yōu)化空間較大；后者的文件請求隨機(jī)到達(dá)，請求頻率和規(guī)律具有不確定性。

1.1 靜態(tài)場景下的副本放置策略相關(guān)研究

此類場景通常是在集群上進(jìn)行預(yù)定的計(jì)算任務(wù)，因而可以提前獲得如文件熱度、任務(wù)功耗等諸多特征。基于這些特征，可以更有針對性地對數(shù)據(jù)塊作整體規(guī)劃，從而使任務(wù)執(zhí)行效率更高、耗時(shí)更短、節(jié)點(diǎn)利用率更均衡。這類方法對時(shí)效性要求不高，常采用啟發(fā)式算法搜索可行方案。

基于多目標(biāo)優(yōu)化的副本放置策略MORM［3］將副本放置視為多目標(biāo)優(yōu)化問題進(jìn)行處理，通過人工免疫算法，以副本放置表為個(gè)體，經(jīng)過交叉、突變得出新的個(gè)體，同時(shí)以平均文件失效率、平均服務(wù)時(shí)間、節(jié)點(diǎn)負(fù)載方差、能量消耗、訪問延遲5 項(xiàng)指標(biāo)對這些個(gè)體進(jìn)行評估及標(biāo)量化處理，得到可作為適應(yīng)度函數(shù)的一維向量，進(jìn)而選取多個(gè)目標(biāo)值都盡可能小的個(gè)體作為解決方案。該方法提供了處理這類問題一個(gè)非常好的思路，可以很好地平衡各個(gè)因素。PRPP［4］作為一種分塊副本放置策略，其目的是在符合HDFS 默認(rèn)的副本放置規(guī)則下，使得每個(gè)節(jié)點(diǎn)副本數(shù)量幾乎完全一致，但由于其前提是集群節(jié)點(diǎn)性能以及塊大小均相同（同構(gòu)環(huán)境），因此適應(yīng)性不佳。ISRPP［5］是SRPP［6］的改進(jìn)版，兩者都針對異構(gòu)環(huán)境，但SRPP 假設(shè)同一機(jī)架上的節(jié)點(diǎn)計(jì)算性能相同，而ISRPP 考慮了各節(jié)點(diǎn)的計(jì)算性能，并采用數(shù)字劃分的方法使得各節(jié)點(diǎn)分配到匹配自身計(jì)算能力的副本數(shù)。這種方法適用于分批次載入的數(shù)據(jù)集，由于其未引入高復(fù)雜度的算法，可應(yīng)用于實(shí)際場景。

1.2 動態(tài)場景下的副本放置策略相關(guān)研究

此類場景類似于用戶對Web 服務(wù)器的訪問，需要實(shí)時(shí)對到達(dá)的寫請求進(jìn)行處理，因此需要?jiǎng)討B(tài)獲取節(jié)點(diǎn)的磁盤、CPU、內(nèi)存、網(wǎng)絡(luò)情況等信息，處理速度較快，并考慮了放置策略對之后任務(wù)執(zhí)行和數(shù)據(jù)訪問效果的影響。

Qu 等［7］提出基于馬爾可夫鏈的動態(tài)副本放置模型，首先利用基于文件訪問熱度的馬爾可夫模型調(diào)整文件副本因子，然后參考文件訪問的平穩(wěn)分布以及節(jié)點(diǎn)和機(jī)架的磁盤占用情況動態(tài)選擇放置節(jié)點(diǎn)，實(shí)驗(yàn)結(jié)果證明，該方法能使數(shù)據(jù)在節(jié)點(diǎn)間和機(jī)架內(nèi)更均勻地分布；Shithil 等［8］提出基于異構(gòu)環(huán)境的動態(tài)數(shù)據(jù)管理策略，從存儲情況和計(jì)算性能兩方面衡量節(jié)點(diǎn)，通過統(tǒng)計(jì)學(xué)中的z 值對節(jié)點(diǎn)的評估值進(jìn)行量化，并藉此為數(shù)據(jù)塊安排位置；袁麗娜［9］對5 個(gè)指標(biāo)進(jìn)行考量，包括磁盤容量、CPU 負(fù)載、內(nèi)存空閑率、磁盤I/O及網(wǎng)絡(luò)帶寬剩余量，通過線性加權(quán)得到綜合評價(jià)指標(biāo)，其系數(shù)通過變異系數(shù)法取得，改進(jìn)的放置策略減少了集群任務(wù)執(zhí)行時(shí)間，提升了集群的整體性能。

基于上述文獻(xiàn)的思路和成果，本文綜合考慮了副本失效率、節(jié)點(diǎn)負(fù)載程度以及讀取能力（HDFS 的讀寫策略是一次寫入、多次讀取，因此更偏重于讀取能力），因?yàn)槭嵌嗄繕?biāo)問題，引入二進(jìn)制的多目標(biāo)灰狼優(yōu)化算法并對其進(jìn)行了改進(jìn)。

2 副本放置改進(jìn)策略

2.1 靜態(tài)場景下默認(rèn)副本放置策略的不足

HDFS 默認(rèn)的副本策略在數(shù)據(jù)量大時(shí)容易出現(xiàn)的問題包括：數(shù)據(jù)節(jié)點(diǎn)負(fù)載不均、大量數(shù)據(jù)放置在處理能力弱的節(jié)點(diǎn)上，導(dǎo)致集群的任務(wù)執(zhí)行速度受限、吞吐量降低。這些問題主要由以下幾方面原因?qū)е拢孩匐S機(jī)選擇節(jié)點(diǎn)的方式?jīng)]有考慮到時(shí)間和空間的局部性原理，容易導(dǎo)致負(fù)載嚴(yán)重不均，增大節(jié)點(diǎn)失效機(jī)率；②Dai 等［4］提出將兩個(gè)節(jié)點(diǎn)放置在同一機(jī)架、另一節(jié)點(diǎn)放置在其它機(jī)架所導(dǎo)致的數(shù)據(jù)分布不均問題；③默認(rèn)副本策略沒有考慮到異構(gòu)環(huán)境中各節(jié)點(diǎn)存儲、計(jì)算、讀寫等性能的差異。

2.2 改進(jìn)的靜態(tài)副本放置策略模型

假設(shè)有m 個(gè)參數(shù)p1,p2…pm，n 個(gè)以p1,p2…pm為自變量的目標(biāo)函數(shù)f1,f2…fn，k 個(gè)約束條件（等式或不等式約束）C1,C2…Ck，則多目標(biāo)優(yōu)化問題可表示為：

由于多個(gè)目標(biāo)函數(shù)構(gòu)成的向量無法直接比較，NSGAII 算法［10］規(guī)定了一種非支配排序方法：向量是第i維為1、其余為0 的單位向量；對于兩個(gè)k 維向量，如果對所有的i∈1,…,k都有，而且存在至少一個(gè)i∈1,…,k，使得，則稱支配，否則構(gòu)成非支配關(guān)系。對于一個(gè)向量集合S，如果某個(gè)向量v→不被任何集合中的向量支配，則這樣的向量構(gòu)成pareto 邊界。

通常認(rèn)為多目標(biāo)優(yōu)化的最優(yōu)解集是通過上述非支配排序或標(biāo)量化的方式比較目標(biāo)函數(shù)，最終在pareto 邊界中取得的。具體優(yōu)化方法一般分為兩種：①啟發(fā)式算法。例如NSGA-II 中采用的遺傳算法、Ferreira 等［11］提出的多目標(biāo)模擬退火算法等，利用了啟發(fā)式算法搜索能力強(qiáng)、復(fù)雜度可控的特點(diǎn)；②結(jié)合強(qiáng)化學(xué)習(xí)方法［12］。強(qiáng)化學(xué)習(xí)［13］通過智能體（agent）做出動作并收到環(huán)境的反饋，藉此調(diào)整行動方案，從而適應(yīng)環(huán)境，找到最佳策略。通過引入多目標(biāo)函數(shù)，可使策略搜索和更新過程中對每個(gè)目標(biāo)都有所關(guān)注，適用于解決狀態(tài)空間有限的優(yōu)化問題。

灰狼優(yōu)化算法［14］是近年來提出的一種受生物學(xué)啟發(fā)［15-17］的優(yōu)化算法，原算法適用于連續(xù)的適應(yīng)度函數(shù)（即目標(biāo)函數(shù)）。如Emary 等［18］提出一種二進(jìn)制的灰狼優(yōu)化算法，將適應(yīng)度函數(shù)的定義域變?yōu)殡x散空間。多目標(biāo)灰狼優(yōu)化算法［19］改善了原算法穩(wěn)定性不佳、傾向于陷入局部最優(yōu)的問題。崔明朗等［20］提出兩條改進(jìn)策略：①引入個(gè)體對周圍個(gè)體的觀察，更有可能跳出局部最優(yōu)；②使用冪函數(shù)而非線性函數(shù)調(diào)整控制參數(shù)，使算法的搜尋過程更加穩(wěn)定。

實(shí)驗(yàn)結(jié)果表明，多目標(biāo)灰狼優(yōu)化算法的結(jié)果集傾向于聚集在很小的范圍內(nèi)，其個(gè)體多樣性差，具有易陷入局部最優(yōu)的缺點(diǎn)。經(jīng)過分析，本文得出結(jié)論：該算法的狼群位置更新主要受3 匹頭狼影響，如果3 匹頭狼都處在某局部最優(yōu)點(diǎn)附近，狼群極有可能陷入該局部最優(yōu)。本文認(rèn)為可能導(dǎo)致該問題的因素之一為：Archive 集合僅包含pareto 前沿的個(gè)體，在出現(xiàn)優(yōu)勢個(gè)體的情況下，Archive 集合中的多個(gè)個(gè)體被淘汰，個(gè)體總數(shù)減少，更容易出現(xiàn)陷入局部最優(yōu)情況。對此，本文提出改進(jìn)算法以增大頭狼選擇范圍，豐富灰狼的個(gè)體多樣性，以減少算法陷入局部最優(yōu)的概率。

以下介紹該方法所用到的符號及概念定義（假設(shè)集群由m 個(gè)相互獨(dú)立的數(shù)據(jù)節(jié)點(diǎn)D1,D2…Dm組成，這些節(jié)點(diǎn)需要存儲n 個(gè)數(shù)據(jù)塊b1,b2…bn）。

（1）副本失效。無可用副本導(dǎo)致訪問失敗的幾率。首先定義每個(gè)節(jié)點(diǎn)的失效率為fD1,fD2…fDm，然后引入副本放置表，如表1 所示，b1有3 份副本分別在D1、D2和D4。

Table 1 Placement of replicas表1 副本放置表

引入Φ(i,j)=1（表1 中第i行第j列的值）表示bi的副本在Dj上存在，否則函數(shù)值為0。bi的副本失效率為：

其中，Π*表示忽略零因子的連乘符號，假如表1 中fD2=0.005，fD4=0.001，則fb2=(1× 0.005) × (1× 0.001)=5 × 10-6。平均副本失效率定義為：

（2）磁盤相對負(fù)載標(biāo)準(zhǔn)差。假設(shè)第i個(gè)節(jié)點(diǎn)的已用空間為Usedi，總空間為Capi，則該節(jié)點(diǎn)的磁盤使用率為DUi=Usedi/Capi。集群空間使用率為：

第i個(gè)節(jié)點(diǎn)的相對負(fù)載率為RLi=DUi/TUi，該指標(biāo)大于1 的節(jié)點(diǎn)處于過載狀態(tài)，應(yīng)進(jìn)行數(shù)據(jù)轉(zhuǎn)移以使數(shù)據(jù)分布更加均勻。由此得到磁盤相對負(fù)載標(biāo)準(zhǔn)差為：

該指標(biāo)反映了集群整體的數(shù)據(jù)分布均衡度。

（3）讀取評價(jià)因子。假設(shè)第i個(gè)節(jié)點(diǎn)的磁盤讀取速度為RSi，第j個(gè)數(shù)據(jù)塊大小為Sj，則讀取時(shí)間為：

由此得到，第j個(gè)數(shù)據(jù)塊的塊讀取速度bRSj=Sj/RTj。

讀取評價(jià)因子REF 為塊讀取速度倒數(shù)的均值，即：

副本放置策略必須滿足以下兩個(gè)約束條件：

條件1：每個(gè)數(shù)據(jù)塊副本數(shù)不得小于2。

條件2：數(shù)據(jù)塊副本大小之和不大于所在數(shù)據(jù)節(jié)點(diǎn)容量。

2.3 算法描述

2.3.1 灰狼優(yōu)化算法

原始的灰狼優(yōu)化算法應(yīng)用于連續(xù)的解空間，且目標(biāo)函數(shù)只有一個(gè)。灰狼群體被劃分為4 個(gè)等級，α、β 和δ 為3 匹頭狼，其余狼稱為ω，它們的更新圍繞著頭狼進(jìn)行。首先定義灰狼與獵物的距離：

2.3.2 二進(jìn)制灰狼優(yōu)化算法更新方式

假設(shè)有m 個(gè)節(jié)點(diǎn)、n 個(gè)數(shù)據(jù)塊，則個(gè)體是大小為m×n 的布爾向量，存儲了數(shù)據(jù)塊的副本個(gè)數(shù)和存放位置。區(qū)別于原版灰狼優(yōu)化算法［14］，本文方法中的個(gè)體以二進(jìn)制形式保存，并按照二進(jìn)制灰狼算法［18］中介紹的方式進(jìn)行更新。

式中，rand是從正態(tài)分布中獲取的［0，1］范圍內(nèi)的隨機(jī)數(shù)。計(jì)算公式如下：

其中，t為當(dāng)前迭代次數(shù)，Maxiter為最大迭代次數(shù),屬于區(qū)間為［0，1］的隨機(jī)向量，維度與個(gè)體相同。x2和x3的計(jì)算類似于x1，僅將上述符號中的α 替換為β 和δ 即可。接下來有：

crossover 為3 個(gè)布爾向量的混合函數(shù)：

以上就是個(gè)體更新過程，更新完成后檢查新個(gè)體是否符合約束條件，如不符合則重新更新，直到產(chǎn)生符合條件的新個(gè)體為止。

2.3.3 多目標(biāo)灰狼優(yōu)化算法不同點(diǎn)

（1）頭狼選擇。灰狼種群中最優(yōu)的3 匹狼定義為α、β和δ，由于目標(biāo)函數(shù)有3 個(gè)，不能用一般的方法為個(gè)體排序。多目標(biāo)灰狼優(yōu)化算法中設(shè)置了非支配種群Archive，在初始種群生成后（每個(gè)生成個(gè)體必須符合約束條件，否則需要重新生成）和每次個(gè)體更新完成后，更新Archive：

若Archive 中的個(gè)體數(shù)為0，則對種群中每個(gè)個(gè)體與其他個(gè)體進(jìn)行非支配排序，如果個(gè)體不被任何其他個(gè)體支配，則將其加入Archive 中。如果Archive 中的個(gè)體超過設(shè)定上限，則執(zhí)行網(wǎng)格策略（在后文介紹），去掉多出的個(gè)體后加入新個(gè)體。

若Archive 中已有個(gè)體，則將種群中更新后的個(gè)體與Archive 中的每個(gè)個(gè)體作非支配排序，如果：①更新后的個(gè)體被Archive 中的任意個(gè)體支配，則不能加入Archive；②更新后的個(gè)體支配Archive 中的個(gè)體集合S，則將該個(gè)體加入Archive，并踢出集合S 中的個(gè)體；③更新后的個(gè)體不被Archive 中的任意個(gè)體支配，則加入Archive。

（2）網(wǎng)格策略。將Archive 中的個(gè)體按同一維度i 的兩個(gè)極值構(gòu)成區(qū)間，將該區(qū)間等距離劃分為n 組，每個(gè)個(gè)體第i 維目標(biāo)函數(shù)值落在的區(qū)間號∈［0，1，…，n-1］記為個(gè)體在第i 維的網(wǎng)格坐標(biāo)，以此得到個(gè)體的網(wǎng)格向量，向量相同的兩個(gè)個(gè)體處于同一網(wǎng)格中。每當(dāng)要從Archive中刪除個(gè)體時(shí)，從個(gè)體數(shù)最多的網(wǎng)格中隨機(jī)踢出個(gè)體。以上說明了Archive，即非支配種群的產(chǎn)生和更新，下面敘述頭狼（即α、β 和δ）的選擇。

采用輪盤賭的方式按順序選擇α、β 和δ，每個(gè)個(gè)體被選定的概率如下：

其中,Ni為個(gè)體所在網(wǎng)格的個(gè)體總數(shù)，c 是大于1 的常數(shù)。

2.3.4 改進(jìn)的多目標(biāo)灰狼優(yōu)化算法

本文基于上述多目標(biāo)灰狼算法提出以下改動：

（1）將Archive 集合分成layer1 和layer2，其中l(wèi)ayer1 中存儲最優(yōu)個(gè)體，layer2 中存儲次優(yōu)個(gè)體。加入懲罰因子p∈（0，1），用于調(diào)節(jié)次優(yōu)個(gè)體被選為頭狼的概率：屬于layer2的個(gè)體被選定的概率需要在原概率基礎(chǔ)上乘以（1-p），使得次優(yōu)個(gè)體在可能被選為頭狼的同時(shí)，避免因其過多地影響狼群位置的更新而導(dǎo)致收斂速度變慢。

（2）個(gè)體加入Archive 的過程變?yōu)槿缦虏襟E：個(gè)體首先嘗試加入layer1，如果成功，將layer1 中被支配個(gè)體的集合移入layer2，否則個(gè)體加入layer2。

（3）Archive 中個(gè)體數(shù)超過上限時(shí)，淘汰策略修改如下：從個(gè)體數(shù)最多的網(wǎng)格中踢出個(gè)體時(shí)，如果個(gè)體屬于layer2，將以懲罰因子p 的概率被踢出，否則將以（1-p）/10 的概率被踢出。這樣做是為了保護(hù)layer1 中的最優(yōu)個(gè)體，使其被踢出的機(jī)率更小。

算法偽代碼如下：

3 實(shí)驗(yàn)結(jié)果

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

實(shí)驗(yàn)仿真平臺為CloudSim4.0，主機(jī)硬件配置如下：CPU為六核Intel（R）Xeon（R）E5-2603 1.60GHz（64G 內(nèi)存，1T 硬盤）；操作系統(tǒng)為CentOS Linux release 7.5.1804；Java 環(huán)境為JDK1.8。

仿真集群中的節(jié)點(diǎn)在CPU 性能、硬盤配置、內(nèi)存大小及失效率方面表現(xiàn)各異。節(jié)點(diǎn)之間較大的配置差異有助于更好地模擬異構(gòu)環(huán)境，從而令默認(rèn)策略與本文提出改進(jìn)策略之間的差異更明顯，優(yōu)缺點(diǎn)對比更清晰。

3.2 改進(jìn)多目標(biāo)灰狼優(yōu)化算法實(shí)驗(yàn)

第一組實(shí)驗(yàn)將原版多目標(biāo)灰狼優(yōu)化算法與上文提出的改進(jìn)多目標(biāo)灰狼優(yōu)化算法作對比。實(shí)驗(yàn)參數(shù)包括：狼群數(shù)量為30，Archive 上限為30，迭代總次數(shù)為1 000。為評價(jià)多目標(biāo)優(yōu)化算法的效果，本文引入兩個(gè)指標(biāo)：

（1）GD（Generational Distance），用來衡量結(jié)果集中個(gè)體到Pareto 前沿的最小距離，如式（21）所示，其中Ps是Pareto 前沿，S 是優(yōu)化算法的結(jié)果集。GD 主要用于評價(jià)算法收斂程度，其值越小，優(yōu)化的結(jié)果越接近Pareto 前沿。

（2）IGD（Inverted Generational Distance）是對GD 作反向映射得到的指標(biāo)，用于衡量Pareto 前沿到結(jié)果集的最小距離，如式（22）所示。IGD 指標(biāo)對結(jié)果集的收斂程度和豐富程度進(jìn)行了綜合評價(jià)，IGD 越小，則算法得到的結(jié)果有更高的精度與更佳的個(gè)體多樣性。

上式在實(shí)際運(yùn)算中應(yīng)作離散化處理，在Pareto 前沿上均勻取值，構(gòu)成離散的Ps集合，然后計(jì)算式（23）。

GD 指標(biāo)的缺點(diǎn)在于無法評估結(jié)果集的多樣性，也即結(jié)果集分布在Pareto 前沿附近的范圍大小；IGD 指標(biāo)的缺點(diǎn)在于其對異常值不敏感，當(dāng)多個(gè)較優(yōu)結(jié)果出現(xiàn)時(shí)即可得到較優(yōu)的IGD 值。因此，本文從GD 和IGD 兩方面評價(jià)多目標(biāo)優(yōu)化算法，以更全面地反映算法效果。本節(jié)采用DTLZ2 測試函數(shù)（有3 個(gè)目標(biāo)函數(shù)）進(jìn)行實(shí)驗(yàn)，以驗(yàn)證改進(jìn)的多目標(biāo)灰狼優(yōu)化算法對于本文提出模型的適用性。DTLZ2 函數(shù)表示如下：

式中，m=12，DTLZ2 的pareto 前沿是圓心位于原點(diǎn)、半徑為1 的球面在x、y、z 正半軸的部分。本節(jié)同樣以GD 和IGD 指標(biāo)衡量原始算法和改進(jìn)算法在DTLZ2 上的效果，實(shí)驗(yàn)結(jié)果表明，當(dāng)懲罰因子p=0.7 時(shí)效果較好，因此以下實(shí)驗(yàn)均取該值。表2、表3 分別展示了原始算法和改進(jìn)算法在DTLZ2 上GD 與IGD 值的均值、最大值、最小值及方差。在GD 值方面，改進(jìn)算法的均值、最大值和最小值均優(yōu)于原始算法，IGD 值也同樣如此。只是改進(jìn)算法的方差大于原始算法，這是由于改進(jìn)算法的個(gè)體多樣性優(yōu)于原始算法，所以在穩(wěn)定性方面稍差。

Table 2 GD values of the DTLZ2 test function of original and improved algorithm表2 原始算法與改進(jìn)算法在DTLZ2 上的GD 值比較

Table 3 IGD values of the DTLZ2 test function of original and improved algorithm表3 原始算法與改進(jìn)算法在DTLZ2 上的IGD 值比較

3.3 靜態(tài)副本放置策略改進(jìn)方法實(shí)驗(yàn)

第二組實(shí)驗(yàn)是測試基于多目標(biāo)灰狼優(yōu)化算法的副本放置策略，應(yīng)用場景是分批次的數(shù)據(jù)存儲。首先使用算法計(jì)算出Archive 集合中的多個(gè)副本放置策略，算法參數(shù)如下：種群數(shù)量為50，Archive 集合上限為10，迭代次數(shù)為500次，懲罰因子p 取0.7。向集群中寫入500 個(gè)數(shù)據(jù)塊，大小均為64MB，每個(gè)數(shù)據(jù)塊有若干個(gè)副本，放置策略符合約束條件。因此，算法中個(gè)體模型為500×11 的二進(jìn)制矩陣將作為長度為5 500 的二進(jìn)制序列進(jìn)行處理，按照稀疏矩陣存儲可大幅減少空間占用。默認(rèn)與改進(jìn)策略相對負(fù)載率對比如圖1 所示。

Fig.1 Relative load of default and improved strategy圖1 默認(rèn)與改進(jìn)策略相對負(fù)載率對比

由圖1 可知，改進(jìn)策略圍繞著相對負(fù)載率為1 的直線上下浮動，而默認(rèn)策略的波動非常大。從統(tǒng)計(jì)學(xué)的角度來看，默認(rèn)策略的相對負(fù)載率極差為1.142，而改進(jìn)策略只有0.169；在標(biāo)準(zhǔn)差方面，默認(rèn)策略為0.349，而改進(jìn)策略為0.054。以容量最大的節(jié)點(diǎn)2、3、7 為例，原策略的相對負(fù)載率分別為0.491、0.767、0.690，大量空間沒有被利用，而改進(jìn)策略為0.967、0.932、0.958。再以容量最小的節(jié)點(diǎn)0、1、6、8為例，在原策略下，其相對負(fù)載率為1.395、1.319、1.426、1.196，屬于超載狀態(tài)，而改進(jìn)策略下對應(yīng)值為1.092、1.058、1.023、1.040，使用情況優(yōu)于默認(rèn)策略。不僅整體的數(shù)據(jù)負(fù)載均衡程度更高，而且每個(gè)節(jié)點(diǎn)的相對負(fù)載率更接近，集群的數(shù)據(jù)塊副本總數(shù)也更少。默認(rèn)策略中副本因子為3，500 個(gè)數(shù)據(jù)塊共生成了1 500 個(gè)副本，而改進(jìn)策略中每個(gè)數(shù)據(jù)塊最低有2 個(gè)副本。經(jīng)統(tǒng)計(jì)，改進(jìn)策略的副本總數(shù)為1 384 個(gè)，比默認(rèn)策略更節(jié)省空間。

將算法的另外兩個(gè)優(yōu)化評價(jià)目標(biāo)（平均副本失效率和讀取評價(jià)因子）應(yīng)用于數(shù)據(jù)塊隨機(jī)讀取任務(wù)。圖2 的橫軸表示隨機(jī)讀取數(shù)據(jù)塊的數(shù)量（每塊64MB），縱軸為任務(wù)耗時(shí)。可以發(fā)現(xiàn)，隨著數(shù)據(jù)塊數(shù)量的增加，任務(wù)耗時(shí)的增速也有所提高，這是由于讀取工作量增大后，副本訪問失效次數(shù)增加，訪問到讀取速度較低節(jié)點(diǎn)的概率也增大，這兩點(diǎn)體現(xiàn)了讀取評價(jià)因子和平均副本失效率。當(dāng)隨機(jī)訪問數(shù)據(jù)塊數(shù)量在50～200 之間時(shí)，兩種策略差別不大，但當(dāng)數(shù)據(jù)塊數(shù)量大于200 時(shí)，改進(jìn)策略逐漸顯示了其優(yōu)勢，在數(shù)量為200、300、400、500 時(shí)，改進(jìn)策略的耗時(shí)較默認(rèn)策略分別減少了31.8%、44.7%、42.2%、45.4%。當(dāng)數(shù)量增大到300 以上時(shí)，改進(jìn)策略的耗時(shí)幾乎只有默認(rèn)策略的一半。

Fig.2 Time taken to complete random read tasks圖2 隨機(jī)讀取數(shù)據(jù)塊任務(wù)完成時(shí)間比

綜合以上兩組實(shí)驗(yàn)可以看出，本文提出的改進(jìn)多目標(biāo)灰狼優(yōu)化算法所生成的副本放置策略基本達(dá)到了使3 個(gè)目標(biāo)函數(shù)（平均副本失效率、相對負(fù)載率標(biāo)準(zhǔn)差及讀取評價(jià)因子）值都盡可能低的目的。

4 結(jié)語

本文針對HDFS 默認(rèn)副本放置策略存在的未綜合考慮節(jié)點(diǎn)性能，從而可能導(dǎo)致負(fù)載不均衡的問題，進(jìn)行了以下研究工作：改進(jìn)了基于二進(jìn)制多目標(biāo)灰狼優(yōu)化算法的副本放置策略，綜合考慮了副本失效率、集群整體讀取性能和集群負(fù)載均衡3 項(xiàng)因素。實(shí)驗(yàn)結(jié)果顯示，本文方法可行、有效，具有不易陷入局部最優(yōu)、解更具多樣性的特點(diǎn)，且負(fù)載均衡度更佳，數(shù)據(jù)塊隨機(jī)讀取耗時(shí)更短，改善了靜態(tài)場景下HDFS 默認(rèn)副本放置策略未考慮節(jié)點(diǎn)差異、優(yōu)化不充分的問題。基于當(dāng)前工作，后續(xù)會開展以下幾個(gè)方向的研究：①采用帶權(quán)重的標(biāo)量化方法代替目前的多目標(biāo)策略，通過權(quán)值調(diào)節(jié)不同目標(biāo)函數(shù)的重要程度；②引入更多節(jié)點(diǎn)性能評估指標(biāo)，如能量消耗等，同時(shí)細(xì)化網(wǎng)絡(luò)模型，以更好地反映節(jié)點(diǎn)之間的網(wǎng)絡(luò)狀態(tài)。