基于免疫优化策略的副本放置算法

罗四维，侯孟书，牛新征，吕孟婕



基于免疫优化策略的副本放置算法

罗四维1，侯孟书1，牛新征1，吕孟婕2

(1. 电子科技大学计算机科学与工程学院 成都 611731；2. 中国民航总局第二研究所 成都 610000)

副本放置问题在云计算环境分布式存储系统中是一个关键问题。针对现有副本放置算法存在的数据副本访问开销较大，节点负载不均衡的问题，提出了一种基于免疫优化策略的副本放置算法。通过计算节点的亲和度，并借助免疫优化系统特有的克隆选择和免疫记忆机制，对副本节点的评价和选择更加合理。基于Matlab的仿真实验证实该算法能够降低分布式存储系统的副本访问开销，均衡节点负载。

云计算; 分布式存储; 免疫优化策略; 副本放置

随着计算技术、分布式存储技术以及通信技术的迅猛发展，云计算作为一种新的计算范式出现在世人面前，它可以为用户提供多种可配置的、可共享的资源，例如计算资源、存储资源等[1-3]。云计算环境分布式存储是以云计算为基础发展而来，通过集群、网络、虚拟化等技术，将网络中各种同构、异构的存储设备连接起来，作为一个整体存储系统为用户提供数据存储和访问服务[4]。由于其超大规模，高可扩展性，高可靠性等特点，受到学术界和工业界的广泛关注。

传统的存储技术由于受自身应用背景和技术所限，不能胜任当前超大规模数据的存储和处理任务。海量数据、异构设备性能和可靠性方面的差异，以及网络状态的波动性，使得数据出错现象成为一种常态，从而导致数据可靠性的降低，极大地影响用户访问的服务质量。

副本技术是一种提高存储系统可靠性和可用性的关键技术，广泛应用于P2P系统、分布式系统以及云存储系统中[5]。副本技术通过在多个不同的节点或者服务器上保存多个数据副本，在提高分布式存储系统可用性和可靠性的同时，能够优化用户访问数据的性能，均衡系统负载。在副本技术中，如何优化多个副本的放置位置，是解决用户访问性能优化，副本之间的一致性维护，分布式存储系统负载均衡等问题的关键。

云计算环境分布式存储的副本放置问题是一个NP难问题。研究人员对此进行了大量的研究工作，取得了一定的成果。文献[6]从QoS角度入手，提出了一种云计算环境下的排名框架模型，用来计算系统中各个节点的QoS值，并且依据值的高低进行排序，最后选取QoS值大的作为副本放置的节点。文献[7]首先分析了节点的历史访问信息，并对应的赋予其一定的决策值，通过均衡系统节点的整体负载情况，选取合适的节点用于副本的放置。文献[8]设计了一种近似的分布式算法用于解决副本放置问题，并且从理论上证明该算法是2-近似解决方案。文献[9]提出了一个基于拓扑匹配的组件服务副本放置算法，该算法通过多规模聚类算法获取拓扑结构，并利用谱聚类算法获得节点的拓扑结构，最后利用贪心算法结合上述两种拓扑结构，确定组件服务副本的最佳放置问题。

遗传算法是一种建立在达尔文生物进化论基础之上的计算模型。由于其自然选择和遗传学机理等特点，遗传算法被广泛应用于组合优化、机器学习、最优搜索等领域，同时在副本放置问题中也能见到遗传算法的身影[10]。除此之外，与遗传算法一脉相承的粒子群优化算法、蚁群算法以及差分进化算法也被用于解决分布式系统中的副本放置问题[11-13]。

基于对现有研究成果分析可知，对副本位置的选择和确定仅仅考虑部分影响因素，如网络带宽利用率、与用户节点的距离、用户访问代价等，没有对副本放置问题形成整体的认识和考虑。因此，本文基于对遗传算法策略研究的延伸，提出了一种基于免疫优化策略的副本放置算法，通过计算节点的亲和度来确定最佳的副本放置位置，并且通过克隆选择，免疫记忆等独有的机制，使得副本放置位置的选择更加合理。

1 问题定义

针对云计算环境分布式存储的副本放置问题，本文首先从整体角度尝试给出该问题的数学定义，然后详细解释副本放置问题涉及的各种假设条件。

定义 1 副本放置问题

基于以上对副本放置问题的定义，本文提出了一种基于免疫优化策略的副本放置算法。不失一般性，针对云计算环境分布式存储系统的场景，本文做了如下假设。

1) 整个分布式存储系统的节点是异构的。节点访问副本的能力基于节点自身的性能，因此节点本身的性能指标对于副本放置节点的选择起着重要作用。

2) 云计算环境分布式存储系统中节点的拓扑结构已知且位置固定。区别于移动互联网和车载自组织网络等节点位置动态变化的网络，本文提出的副本放置算法针对拓扑结构已知以及节点位置固定的情况。

3) 为了简化算法的运行，规定节点一次只能访问一个数据副本。在以后的研究工作中，将拓展本文现有的算法，支持节点能够并行访问多个数据副本。

4) 由于云计算环境分布式存储的节点错误常态特征，本文将节点失效的概率情况加入副本放置的考虑因素中。

5) 整个分布式存储系统节点之间的网络状况良好，带宽能够满足数据副本的访问要求。由于网络带宽开销测量的困难较大，本文用节点之间的二维空间距离来代替。

根据以上对云计算环境分布式存储副本放置问题的定义和假设限定，本文能够设计基于免疫优化策略的副本放置算法。在接下来的部分将详细阐述免疫优化策略的来龙去脉，以及副本放置算法的具体流程。

2 基于免疫优化策略的副本放置算法

在本节内容中，基于免疫优化策略提出一种新的适用于云计算环境分布式存储的副本放置算法。本文首先简要介绍免疫系统和优化算法的来源和背景，然后给出副本放置算法相关的数学表达式，最后结合前一小节的数学语言，给出了副本放置算法具体步骤。

2.1 免疫系统和优化算法

免疫系统，又称为生物免疫系统，是一个具有高度进化特征的生物系统。它用来区分外部有害物质与自身组织的差异，与此同时保证生物有机体的稳定性。免疫系统具有产生多样抗体的能力，并且可以自我调节维持免疫平衡，最重要的是，它还具有一定的记忆功能。正因为这些特点，由此发展而来的免疫优化算法[14]越来越受到研究人员的重视，免疫优化算法的一般流程如图1所示。

图1 免疫优化算法的流程图

从算法角度来看，免疫优化算法具有分布式、自适应和高度并行化的特点，除此之外，由于免疫系统独有特征，该算法同时也具有学习和记忆的能力。免疫优化算法利用免疫系统的多样性产生和维持机制保证了群体的多样性，克服了遗传算法存在的多峰函数寻优过程中的早熟问题，使得最终能够得到全局最优解。

副本放置问题涉及副本的创建、分布，副本数量，放置位置的选择以及副本节点失效等问题，牵一发而动全身。本文基于免疫优化策略提出的副本放置算法，对于上述子问题都有涉及。根据群体之间的信息交互创建和分布副本；对于副本数量的确定可以根据经验的3-副本法则，也可以根据对分布式存储系统实际运行效率和节点负载进行智能调整；副本放置位置的选择根据节点的亲和度值来确定；根据对节点未来一段时间可能失效的概率，自适应的调整副本放置位置的选择。

综上所述，基于免疫优化策略的副本放置算法能够从宏观的角度入手，对副本放置及其相关问题做全盘考虑，形成整体解决方案，能够较好地解决云计算环境分布式存储系统中副本如何选择节点放置的问题。

2.2 基于免疫优化策略的副本放置算法

2.2.1 算法数学描述

基于第1节副本放置问题的定义和假设，并结合免疫优化算法的核心思想，本文提出了基于免疫优化策略的副本放置算法。在接下来的内容中详细阐述了该算法的数学描述及其含义：

首先，定义了算法的目标函数：

其次，给出了其余重要参数的表达式：

2.2.2 解的多样性评价

1) 抗体与抗原之间的亲和度

抗体与抗原之间的亲和度大小表明节点作为副本放置位置的适合度。根据前一节定义的算法目标函数可以得到：

2) 抗体之间的亲和度

抗体之间的亲和度，表明解集合中抗体之间的相似性。相似度越高的抗体集，越能构成最优集合。由于此处只考虑抗体之间的相似性，并没有将顺序加入影响因素。因此，本文借鉴了一种部分匹配的算法——位连续方法，用来计算抗体之间的亲和度。

3) 抗体浓度

4) 个体期望繁殖概率

在免疫优化算法中，对个体的评价是至关重要的。这里采用个体的期望繁殖概率作为评价个体的指标：

2.3 算法流程

根据图1免疫优化算法的一般流程，并结合副本放置问题的具体解决过程，本小节给出了基于免疫优化策略副本放置算法的详细步骤。

1) 对副本放置问题进行分析，选择适合云计算环境分布式存储场景的节点进行副本的放置。依据2.2.1节给出的数学表达式作算法的初始化工作。

2) 整个群体中个体总数为，随机选取个抗体作为初始的抗体群，并且作为记忆群体的个体总数。

3) 依据式(9)对初始抗体群中的个体，计算其期望繁殖概率。

4) 依据期望繁殖概率的值，对初始抗体群中的个体进行降序排列，并选取前面个作为父代群体，另外选取前面个存入记忆群体中。

5) 判断是否满足结束条件。如满足，则算法结束。如不满足，则继续。

6) 根据步骤4)的结果，对抗体群体进行选择、交叉、变异等免疫操作，产生新群体，和记忆群体共同构成新群体。

7) 转至步骤3)。

3 模拟实验和分析

为了模拟和验证本文提出的基于免疫优化策略的副本放置算法，利用Matlab工具对该算法进行了实现和验证。实验配置环境包括：处理器为Intel (R) Core(TM) i5-2410M@2.3 GHz，内存为8 GB DDR3 SDRAM，硬盘为250 G SSD，工具为Matlab R2011b 64 bit，操作系统是Windows 10/64 bit。为了使实验结果更具说服力，仿真实验采用了全国34个省会城市的详细坐标(北纬，东经)并进行规范化处理，用于代表分布式存储系统中不同节点的位置信息。

表1 仿真实验相关参数

图2和图3给出了在是否考虑节点可能失效的前提下，基于免疫优化策略的副本放置算法的收敛曲线图。从图中所示的结果可知，与未考虑节点失效的副本放置情况相比，在副本放置问题中将节点可能发生失效的因素加入考虑范畴，并不会影响副本放置算法的收敛情况。算法能够在不影响副本放置节点选择效率的前提下，保证用户对副本访问开销的最小化。

图4和图5显示了在是否考虑节点失效的前提下，分布式存储系统中节点的分布情况以及最终选取的副本放置节点的位置。从两图中可以看出，对于副本放置节点的选取结果完全不同。如果节点自身性能受限，无法满足用户对于副本的访问要求，那么该节点也就没有资格被选为副本放置的位置；与此同时，如果节点在未来一段时间内可能失效，那么该节点同样不能提供副本的访问服务，选择该节点作为副本放置的位置也就没有任何意义。基于免疫优化策略的副本放置算法综合考虑了以上两种影响情况，使得副本放置节点的选择更加全面，合理。并且在副本放置节点的选择过程中，从副本整体访问开销着手，副本放置节点一旦确定，其整体开销必然最小化，这样便均衡了用户对于副本放置节点的访问频率，均衡了节点负载。

图2 未考虑节点失效概率的算法收敛曲线

图3 考虑节点失效概率的算法收敛曲线

图4 未考虑节点失效概率的副本节点选择情况

图5 考虑节点失效概率的副本节点选择情况

4 结束语

副本放置问题不仅在分布式系统中是一个关键研究课题，同时在云计算和分布式存储系统也扮演着重要角色。副本放置的位置对分布式存储系统的性能，可靠性以及负载均衡都有着很大的影响。针对云计算环境下分布式存储的副本放置问题，本文提出一种基于免疫优化策略的副本放置算法，能够选取最佳的副本放置节点，仿真试验结果验证了算法的有效性，能够降低用户访问副本的整体开销。

[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]王意洁, 孙伟东, 周松, 等. 云计算环境下分布存储关键技术[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)；中央高校基本科研业务费(ZYGX2014J052)

罗四维(1989-)，男，博士生，主要从事云计算环境分布式存储方面的研究.