羅四維，侯孟書，牛新征，呂孟婕

?

基于免疫優(yōu)化策略的副本放置算法

羅四維1，侯孟書1，牛新征1，呂孟婕2

(1. 電子科技大學計算機科學與工程學院 成都 611731；2. 中國民航總局第二研究所 成都 610000)

副本放置問題在云計算環(huán)境分布式存儲系統(tǒng)中是一個關鍵問題。針對現(xiàn)有副本放置算法存在的數(shù)據(jù)副本訪問開銷較大，節(jié)點負載不均衡的問題，提出了一種基于免疫優(yōu)化策略的副本放置算法。通過計算節(jié)點的親和度，并借助免疫優(yōu)化系統(tǒng)特有的克隆選擇和免疫記憶機制，對副本節(jié)點的評價和選擇更加合理?；贛atlab的仿真實驗證實該算法能夠降低分布式存儲系統(tǒng)的副本訪問開銷，均衡節(jié)點負載。

云計算; 分布式存儲; 免疫優(yōu)化策略; 副本放置

隨著計算技術、分布式存儲技術以及通信技術的迅猛發(fā)展，云計算作為一種新的計算范式出現(xiàn)在世人面前，它可以為用戶提供多種可配置的、可共享的資源，例如計算資源、存儲資源等[1-3]。云計算環(huán)境分布式存儲是以云計算為基礎發(fā)展而來，通過集群、網(wǎng)絡、虛擬化等技術，將網(wǎng)絡中各種同構、異構的存儲設備連接起來，作為一個整體存儲系統(tǒng)為用戶提供數(shù)據(jù)存儲和訪問服務[4]。由于其超大規(guī)模，高可擴展性，高可靠性等特點，受到學術界和工業(yè)界的廣泛關注。

傳統(tǒng)的存儲技術由于受自身應用背景和技術所限，不能勝任當前超大規(guī)模數(shù)據(jù)的存儲和處理任務。海量數(shù)據(jù)、異構設備性能和可靠性方面的差異，以及網(wǎng)絡狀態(tài)的波動性，使得數(shù)據(jù)出錯現(xiàn)象成為一種常態(tài)，從而導致數(shù)據(jù)可靠性的降低，極大地影響用戶訪問的服務質量。

副本技術是一種提高存儲系統(tǒng)可靠性和可用性的關鍵技術，廣泛應用于P2P系統(tǒng)、分布式系統(tǒng)以及云存儲系統(tǒng)中[5]。副本技術通過在多個不同的節(jié)點或者服務器上保存多個數(shù)據(jù)副本，在提高分布式存儲系統(tǒng)可用性和可靠性的同時，能夠優(yōu)化用戶訪問數(shù)據(jù)的性能，均衡系統(tǒng)負載。在副本技術中，如何優(yōu)化多個副本的放置位置，是解決用戶訪問性能優(yōu)化，副本之間的一致性維護，分布式存儲系統(tǒng)負載均衡等問題的關鍵。

云計算環(huán)境分布式存儲的副本放置問題是一個NP難問題。研究人員對此進行了大量的研究工作，取得了一定的成果。文獻[6]從QoS角度入手，提出了一種云計算環(huán)境下的排名框架模型，用來計算系統(tǒng)中各個節(jié)點的QoS值，并且依據(jù)值的高低進行排序，最后選取QoS值大的作為副本放置的節(jié)點。文獻[7]首先分析了節(jié)點的歷史訪問信息，并對應的賦予其一定的決策值，通過均衡系統(tǒng)節(jié)點的整體負載情況，選取合適的節(jié)點用于副本的放置。文獻[8]設計了一種近似的分布式算法用于解決副本放置問題，并且從理論上證明該算法是2-近似解決方案。文獻[9]提出了一個基于拓撲匹配的組件服務副本放置算法，該算法通過多規(guī)模聚類算法獲取拓撲結構，并利用譜聚類算法獲得節(jié)點的拓撲結構，最后利用貪心算法結合上述兩種拓撲結構，確定組件服務副本的最佳放置問題。

遺傳算法是一種建立在達爾文生物進化論基礎之上的計算模型。由于其自然選擇和遺傳學機理等特點，遺傳算法被廣泛應用于組合優(yōu)化、機器學習、最優(yōu)搜索等領域，同時在副本放置問題中也能見到遺傳算法的身影[10]。除此之外，與遺傳算法一脈相承的粒子群優(yōu)化算法、蟻群算法以及差分進化算法也被用于解決分布式系統(tǒng)中的副本放置問題[11-13]。

基于對現(xiàn)有研究成果分析可知，對副本位置的選擇和確定僅僅考慮部分影響因素，如網(wǎng)絡帶寬利用率、與用戶節(jié)點的距離、用戶訪問代價等，沒有對副本放置問題形成整體的認識和考慮。因此，本文基于對遺傳算法策略研究的延伸，提出了一種基于免疫優(yōu)化策略的副本放置算法，通過計算節(jié)點的親和度來確定最佳的副本放置位置，并且通過克隆選擇，免疫記憶等獨有的機制，使得副本放置位置的選擇更加合理。

1 問題定義

針對云計算環(huán)境分布式存儲的副本放置問題，本文首先從整體角度嘗試給出該問題的數(shù)學定義，然后詳細解釋副本放置問題涉及的各種假設條件。

定義 1 副本放置問題

基于以上對副本放置問題的定義，本文提出了一種基于免疫優(yōu)化策略的副本放置算法。不失一般性，針對云計算環(huán)境分布式存儲系統(tǒng)的場景，本文做了如下假設。

1) 整個分布式存儲系統(tǒng)的節(jié)點是異構的。節(jié)點訪問副本的能力基于節(jié)點自身的性能，因此節(jié)點本身的性能指標對于副本放置節(jié)點的選擇起著重要作用。

2) 云計算環(huán)境分布式存儲系統(tǒng)中節(jié)點的拓撲結構已知且位置固定。區(qū)別于移動互聯(lián)網(wǎng)和車載自組織網(wǎng)絡等節(jié)點位置動態(tài)變化的網(wǎng)絡，本文提出的副本放置算法針對拓撲結構已知以及節(jié)點位置固定的情況。

3) 為了簡化算法的運行，規(guī)定節(jié)點一次只能訪問一個數(shù)據(jù)副本。在以后的研究工作中，將拓展本文現(xiàn)有的算法，支持節(jié)點能夠并行訪問多個數(shù)據(jù)副本。

4) 由于云計算環(huán)境分布式存儲的節(jié)點錯誤常態(tài)特征，本文將節(jié)點失效的概率情況加入副本放置的考慮因素中。

5) 整個分布式存儲系統(tǒng)節(jié)點之間的網(wǎng)絡狀況良好，帶寬能夠滿足數(shù)據(jù)副本的訪問要求。由于網(wǎng)絡帶寬開銷測量的困難較大，本文用節(jié)點之間的二維空間距離來代替。

根據(jù)以上對云計算環(huán)境分布式存儲副本放置問題的定義和假設限定，本文能夠設計基于免疫優(yōu)化策略的副本放置算法。在接下來的部分將詳細闡述免疫優(yōu)化策略的來龍去脈，以及副本放置算法的具體流程。

2 基于免疫優(yōu)化策略的副本放置算法

在本節(jié)內(nèi)容中，基于免疫優(yōu)化策略提出一種新的適用于云計算環(huán)境分布式存儲的副本放置算法。本文首先簡要介紹免疫系統(tǒng)和優(yōu)化算法的來源和背景，然后給出副本放置算法相關的數(shù)學表達式，最后結合前一小節(jié)的數(shù)學語言，給出了副本放置算法具體步驟。

2.1 免疫系統(tǒng)和優(yōu)化算法

免疫系統(tǒng)，又稱為生物免疫系統(tǒng)，是一個具有高度進化特征的生物系統(tǒng)。它用來區(qū)分外部有害物質與自身組織的差異，與此同時保證生物有機體的穩(wěn)定性。免疫系統(tǒng)具有產(chǎn)生多樣抗體的能力，并且可以自我調(diào)節(jié)維持免疫平衡，最重要的是，它還具有一定的記憶功能。正因為這些特點，由此發(fā)展而來的免疫優(yōu)化算法[14]越來越受到研究人員的重視，免疫優(yōu)化算法的一般流程如圖1所示。

圖1 免疫優(yōu)化算法的流程圖

從算法角度來看，免疫優(yōu)化算法具有分布式、自適應和高度并行化的特點，除此之外，由于免疫系統(tǒng)獨有特征，該算法同時也具有學習和記憶的能力。免疫優(yōu)化算法利用免疫系統(tǒng)的多樣性產(chǎn)生和維持機制保證了群體的多樣性，克服了遺傳算法存在的多峰函數(shù)尋優(yōu)過程中的早熟問題，使得最終能夠得到全局最優(yōu)解。

副本放置問題涉及副本的創(chuàng)建、分布，副本數(shù)量，放置位置的選擇以及副本節(jié)點失效等問題，牽一發(fā)而動全身。本文基于免疫優(yōu)化策略提出的副本放置算法，對于上述子問題都有涉及。根據(jù)群體之間的信息交互創(chuàng)建和分布副本；對于副本數(shù)量的確定可以根據(jù)經(jīng)驗的3-副本法則，也可以根據(jù)對分布式存儲系統(tǒng)實際運行效率和節(jié)點負載進行智能調(diào)整；副本放置位置的選擇根據(jù)節(jié)點的親和度值來確定；根據(jù)對節(jié)點未來一段時間可能失效的概率，自適應的調(diào)整副本放置位置的選擇。

綜上所述，基于免疫優(yōu)化策略的副本放置算法能夠從宏觀的角度入手，對副本放置及其相關問題做全盤考慮，形成整體解決方案，能夠較好地解決云計算環(huán)境分布式存儲系統(tǒng)中副本如何選擇節(jié)點放置的問題。

2.2 基于免疫優(yōu)化策略的副本放置算法

2.2.1 算法數(shù)學描述

基于第1節(jié)副本放置問題的定義和假設，并結合免疫優(yōu)化算法的核心思想，本文提出了基于免疫優(yōu)化策略的副本放置算法。在接下來的內(nèi)容中詳細闡述了該算法的數(shù)學描述及其含義：

首先，定義了算法的目標函數(shù)：

其次，給出了其余重要參數(shù)的表達式：

2.2.2 解的多樣性評價

1) 抗體與抗原之間的親和度

抗體與抗原之間的親和度大小表明節(jié)點作為副本放置位置的適合度。根據(jù)前一節(jié)定義的算法目標函數(shù)可以得到：

2) 抗體之間的親和度

抗體之間的親和度，表明解集合中抗體之間的相似性。相似度越高的抗體集，越能構成最優(yōu)集合。由于此處只考慮抗體之間的相似性，并沒有將順序加入影響因素。因此，本文借鑒了一種部分匹配的算法——位連續(xù)方法，用來計算抗體之間的親和度。

3) 抗體濃度

4) 個體期望繁殖概率

在免疫優(yōu)化算法中，對個體的評價是至關重要的。這里采用個體的期望繁殖概率作為評價個體的指標：

2.3 算法流程

根據(jù)圖1免疫優(yōu)化算法的一般流程，并結合副本放置問題的具體解決過程，本小節(jié)給出了基于免疫優(yōu)化策略副本放置算法的詳細步驟。

1) 對副本放置問題進行分析，選擇適合云計算環(huán)境分布式存儲場景的節(jié)點進行副本的放置。依據(jù)2.2.1節(jié)給出的數(shù)學表達式作算法的初始化工作。

2) 整個群體中個體總數(shù)為，隨機選取個抗體作為初始的抗體群，并且作為記憶群體的個體總數(shù)。

3) 依據(jù)式(9)對初始抗體群中的個體，計算其期望繁殖概率。

4) 依據(jù)期望繁殖概率的值，對初始抗體群中的個體進行降序排列，并選取前面?zhèn)€作為父代群體，另外選取前面?zhèn)€存入記憶群體中。

5) 判斷是否滿足結束條件。如滿足，則算法結束。如不滿足，則繼續(xù)。

6) 根據(jù)步驟4)的結果，對抗體群體進行選擇、交叉、變異等免疫操作，產(chǎn)生新群體，和記憶群體共同構成新群體。

7) 轉至步驟3)。

3 模擬實驗和分析

為了模擬和驗證本文提出的基于免疫優(yōu)化策略的副本放置算法，利用Matlab工具對該算法進行了實現(xiàn)和驗證。實驗配置環(huán)境包括：處理器為Intel (R) Core(TM) i5-2410M@2.3 GHz，內(nèi)存為8 GB DDR3 SDRAM，硬盤為250 G SSD，工具為Matlab R2011b 64 bit，操作系統(tǒng)是Windows 10/64 bit。為了使實驗結果更具說服力，仿真實驗采用了全國34個省會城市的詳細坐標(北緯，東經(jīng))并進行規(guī)范化處理，用于代表分布式存儲系統(tǒng)中不同節(jié)點的位置信息。

表1 仿真實驗相關參數(shù)

圖2和圖3給出了在是否考慮節(jié)點可能失效的前提下，基于免疫優(yōu)化策略的副本放置算法的收斂曲線圖。從圖中所示的結果可知，與未考慮節(jié)點失效的副本放置情況相比，在副本放置問題中將節(jié)點可能發(fā)生失效的因素加入考慮范疇，并不會影響副本放置算法的收斂情況。算法能夠在不影響副本放置節(jié)點選擇效率的前提下，保證用戶對副本訪問開銷的最小化。

圖4和圖5顯示了在是否考慮節(jié)點失效的前提下，分布式存儲系統(tǒng)中節(jié)點的分布情況以及最終選取的副本放置節(jié)點的位置。從兩圖中可以看出，對于副本放置節(jié)點的選取結果完全不同。如果節(jié)點自身性能受限，無法滿足用戶對于副本的訪問要求，那么該節(jié)點也就沒有資格被選為副本放置的位置；與此同時，如果節(jié)點在未來一段時間內(nèi)可能失效，那么該節(jié)點同樣不能提供副本的訪問服務，選擇該節(jié)點作為副本放置的位置也就沒有任何意義?；诿庖邇?yōu)化策略的副本放置算法綜合考慮了以上兩種影響情況，使得副本放置節(jié)點的選擇更加全面，合理。并且在副本放置節(jié)點的選擇過程中，從副本整體訪問開銷著手，副本放置節(jié)點一旦確定，其整體開銷必然最小化，這樣便均衡了用戶對于副本放置節(jié)點的訪問頻率，均衡了節(jié)點負載。

圖2 未考慮節(jié)點失效概率的算法收斂曲線

圖3 考慮節(jié)點失效概率的算法收斂曲線

圖4 未考慮節(jié)點失效概率的副本節(jié)點選擇情況

圖5 考慮節(jié)點失效概率的副本節(jié)點選擇情況

4 結束語

副本放置問題不僅在分布式系統(tǒng)中是一個關鍵研究課題，同時在云計算和分布式存儲系統(tǒng)也扮演著重要角色。副本放置的位置對分布式存儲系統(tǒng)的性能，可靠性以及負載均衡都有著很大的影響。針對云計算環(huán)境下分布式存儲的副本放置問題，本文提出一種基于免疫優(yōu)化策略的副本放置算法，能夠選取最佳的副本放置節(jié)點，仿真試驗結果驗證了算法的有效性，能夠降低用戶訪問副本的整體開銷。

[1] U.S. Department of Commerce. Maryland: The NIST definition of cloud computing[S]// National Institute of Standards and Technology, 2011.

[2] ARMBRUST M, FOX A, GRIFFITH R, et al. Above the clouds: a berkeley view of cloud computing[R]. Berkeley: Electrical Engineering and Computer Sciences in University of California Berkeley, 2009.

[3] BUYYA R, CHEE S Y, VENUGOPAL S, et al. Cloud computing and emerging IT platforms: Vision, hype, and reality for delivering computing as the 5th utility[J]. Future Generation Computer Systems, 2009, 25(6): 599-616.

[4]王意潔, 孫偉東, 周松, 等. 云計算環(huán)境下分布存儲關鍵技術[J]. 軟件學報, 2012, 23(4): 962-986.

WANG Yi-jie, SUN Wei-dong, ZHOU Song, et al. Key technologies of distributed storage for cloud computing[J]. Journal of Software, 2012, 23(4): 962-986.

[5] ALLCOCK B, BESTER J, BRESNAHAN J, et al. Data management and transfer in high-performance computational grid environments[J]. Parallel Computing, 2002, 28(5): 749-771.

[6] ZHENG Z, ZHANG Y, LYU M R. CloudRank: a QoS-drive component ranking framework for cloud computing[C]// 2010 29th IEEE Symposium on Reliable Distributed Systems. New Delhi: IEEE Press, 2010: 184-193.

[7] CHANG R S, CHANG H P, WANG Y T. A dynamic weighted data replication strategy in data grids[C]// IEEE/ACS International Conference on Computer Systems and Applications. Doha: IEEE, 2008: 414-421.

[8] ZAMAN S, GROSU D. A distributed algorithm for the replica placement problem[J]. IEEE Transactions on Parallel and Distributed Systems, 2011, 22(9): 1455-1468.

[9] 吳嘉軒, 代鈺, 張斌, 等. 基于拓撲匹配的組件服務副本放置算法[J]. 電子科技大學學報, 2015, 44(6): 905-910.

WU Jia-xuan, DAI Yu, ZHANG Bin, et al. Component service replicas placement algorithm based on the topology matching[J]. Journal of University of Electronic Science and Technology of China, 2015, 44(6): 905-910.

[10] GOYAL N, MITTAL P. Comparative analysis of generic algorithm, particle swarm optimization and ant colony optimization for TSP[J]. Artificial Intelligent Systems and Machine Learning, 2012, 4(4): 202-206.

[11] LIM T, HARON H. Performance comparison of genetic algorithm, differential evolution and particle swarm optimization towards benchmark functions[C]//Proc de IEEE Conference on Open Systems (ICOS). Kunching: IEEE, 2013: 41-46.

[12] PHAN T, RANGANATHAN K, SION R. Evolving toward the perfect schedule: Co-scheduling job assignments and data replication in wide-area systems using a genetic algorithm[C]//Proc Job Scheduling Strategies for Parallel Processing. Cambridge, MA, USA: Springer, 2005: 173- 193.

[13] WANG L, SIEGEL H J, ROYCHOWDHURY V P, et al. Task matching and scheduling in heterogeneous computing environments using a genetic-algorithm-based approach[J]. Journal of Parallel and Distributed Computing, 1997, 47(6): 8-22.

[14] FARMER J, PACKARD N, PERELSON A. The immune system, adaptation and machine learning[J]. Phys D: Nonlinear Phenom, 1986, 22(4): 187-204.

編 輯 蔣 曉

Data Replica Placement Algorithm Based on Immune Optimization Strategy

LUO Si-wei1, HOU Meng-shu1, NIU Xin-zheng1, and Lü Meng-jie2

(1. School of Computer Science and Engineering, University of Electronic Science and Technology of China Chengdu 611731; 2. The Second Research Institute of Civil Aviation Administration of China Chengdu 610000)

The problem of replica placement is a key issue of distributed storage systems in cloud computing. Aiming at the uneven load among nodes and the high costs of replicas access, we propose a novel replica placement algorithm based on the immune optimization strategy. Through the computation of affinity of nodes, and with the help of clonal selection and immune memory mechanisms, the proposed algorithm can comprehensively evaluate and select the nodes for replica placement. Several simulations and conducted based on Matlab, and the results show that the algorithmpresented is able to reduce the cost of replica access, and makes the load between nodes more balanced.

cloud computing; distributed storage; immune optimization strategy; replica placement

TP393

A

10.3969/j.issn.1001-0548.2017.05.017

2016-07-02；

2016-12-13

國家自然科學基金面上項目(61472067, 61300192)；國家科技支撐計劃(2013BAH33F02)；四川省科技計劃項目(2013GZ0006)；中央高?；究蒲袠I(yè)務費(ZYGX2014J052)

羅四維(1989-)，男，博士生，主要從事云計算環(huán)境分布式存儲方面的研究.