ISSN 
-
随着计算技术、分布式存储技术以及通信技术的迅猛发展，云计算作为一种新的计算范式出现在世人面前，它可以为用户提供多种可配置的、可共享的资源，例如计算资源、存储资源等[1-3]。云计算环境分布式存储是以云计算为基础发展而来，通过集群、网络、虚拟化等技术，将网络中各种同构、异构的存储设备连接起来，作为一个整体存储系统为用户提供数据存储和访问服务[4]。由于其超大规模，高可扩展性，高可靠性等特点，受到学术界和工业界的广泛关注。
传统的存储技术由于受自身应用背景和技术所限，不能胜任当前超大规模数据的存储和处理任务。海量数据、异构设备性能和可靠性方面的差异，以及网络状态的波动性，使得数据出错现象成为一种常态，从而导致数据可靠性的降低，极大地影响用户访问的服务质量。
副本技术是一种提高存储系统可靠性和可用性的关键技术，广泛应用于P2P系统、分布式系统以及云存储系统中[5]。副本技术通过在多个不同的节点或者服务器上保存多个数据副本，在提高分布式存储系统可用性和可靠性的同时，能够优化用户访问数据的性能，均衡系统负载。在副本技术中，如何优化多个副本的放置位置，是解决用户访问性能优化，副本之间的一致性维护，分布式存储系统负载均衡等问题的关键。
云计算环境分布式存储的副本放置问题是一个NP难问题。研究人员对此进行了大量的研究工作，取得了一定的成果。文献[6]从QoS角度入手，提出了一种云计算环境下的排名框架模型，用来计算系统中各个节点的QoS值，并且依据值的高低进行排序，最后选取QoS值大的作为副本放置的节点。文献[7]首先分析了节点的历史访问信息，并对应的赋予其一定的决策值，通过均衡系统节点的整体负载情况，选取合适的节点用于副本的放置。文献[8]设计了一种近似的分布式算法用于解决副本放置问题，并且从理论上证明该算法是2-近似解决方案。文献[9]提出了一个基于拓扑匹配的组件服务副本放置算法，该算法通过多规模聚类算法获取拓扑结构，并利用谱聚类算法获得节点的拓扑结构，最后利用贪心算法结合上述两种拓扑结构，确定组件服务副本的最佳放置问题。
遗传算法是一种建立在达尔文生物进化论基础之上的计算模型。由于其自然选择和遗传学机理等特点，遗传算法被广泛应用于组合优化、机器学习、最优搜索等领域，同时在副本放置问题中也能见到遗传算法的身影[10]。除此之外，与遗传算法一脉相承的粒子群优化算法、蚁群算法以及差分进化算法也被用于解决分布式系统中的副本放置问题[11-13]。
基于对现有研究成果分析可知，对副本位置的选择和确定仅仅考虑部分影响因素，如网络带宽利用率、与用户节点的距离、用户访问代价等，没有对副本放置问题形成整体的认识和考虑。因此，本文基于对遗传算法策略研究的延伸，提出了一种基于免疫优化策略的副本放置算法，通过计算节点的亲和度来确定最佳的副本放置位置，并且通过克隆选择，免疫记忆等独有的机制，使得副本放置位置的选择更加合理。
-
针对云计算环境分布式存储的副本放置问题，本文首先从整体角度尝试给出该问题的数学定义，然后详细解释副本放置问题涉及的各种假设条件。
定义1 副本放置问题
给定一个云计算环境分布式存储系统的场景，系统节点总数为$ N $，所有节点通过分布式的方式组织，节点集合$ R $代表该存储系统中数据副本的数目，每个节点$ i\in N $最多保存一份数据的副本。问题定义如下：找到一个算法得到节点集合$ S $，例如$ S\subseteq N $，使得节点集合$ S $能够处理数据副本的访问服务，并且保证副本访问整体开销最小化，同时存储系统负载均衡。
基于以上对副本放置问题的定义，本文提出了一种基于免疫优化策略的副本放置算法。不失一般性，针对云计算环境分布式存储系统的场景，本文做了如下假设。
1) 整个分布式存储系统的节点是异构的。节点访问副本的能力基于节点自身的性能，因此节点本身的性能指标对于副本放置节点的选择起着重要作用。
2) 云计算环境分布式存储系统中节点的拓扑结构已知且位置固定。区别于移动互联网和车载自组织网络等节点位置动态变化的网络，本文提出的副本放置算法针对拓扑结构已知以及节点位置固定的情况。
3) 为了简化算法的运行，规定节点一次只能访问一个数据副本。在以后的研究工作中，将拓展本文现有的算法，支持节点能够并行访问多个数据副本。
4) 由于云计算环境分布式存储的节点错误常态特征，本文将节点失效的概率情况加入副本放置的考虑因素中。
5) 整个分布式存储系统节点之间的网络状况良好，带宽能够满足数据副本的访问要求。由于网络带宽开销测量的困难较大，本文用节点之间的二维空间距离来代替。
根据以上对云计算环境分布式存储副本放置问题的定义和假设限定，本文能够设计基于免疫优化策略的副本放置算法。在接下来的部分将详细阐述免疫优化策略的来龙去脉，以及副本放置算法的具体流程。
-
在本节内容中，基于免疫优化策略提出一种新的适用于云计算环境分布式存储的副本放置算法。本文首先简要介绍免疫系统和优化算法的来源和背景，然后给出副本放置算法相关的数学表达式，最后结合前一小节的数学语言，给出了副本放置算法具体步骤。
-
免疫系统，又称为生物免疫系统，是一个具有高度进化特征的生物系统。它用来区分外部有害物质与自身组织的差异，与此同时保证生物有机体的稳定性。免疫系统具有产生多样抗体的能力，并且可以自我调节维持免疫平衡，最重要的是，它还具有一定的记忆功能。正因为这些特点，由此发展而来的免疫优化算法[14]越来越受到研究人员的重视，免疫优化算法的一般流程如图 1所示。
图 1 免疫优化算法的流程图
从算法角度来看，免疫优化算法具有分布式、自适应和高度并行化的特点，除此之外，由于免疫系统独有特征，该算法同时也具有学习和记忆的能力。免疫优化算法利用免疫系统的多样性产生和维持机制保证了群体的多样性，克服了遗传算法存在的多峰函数寻优过程中的早熟问题，使得最终能够得到全局最优解。
副本放置问题涉及副本的创建、分布，副本数量，放置位置的选择以及副本节点失效等问题，牵一发而动全身。本文基于免疫优化策略提出的副本放置算法，对于上述子问题都有涉及。根据群体之间的信息交互创建和分布副本；对于副本数量的确定可以根据经验的3-副本法则，也可以根据对分布式存储系统实际运行效率和节点负载进行智能调整；副本放置位置的选择根据节点的亲和度值来确定；根据对节点未来一段时间可能失效的概率，自适应的调整副本放置位置的选择。
综上所述，基于免疫优化策略的副本放置算法能够从宏观的角度入手，对副本放置及其相关问题做全盘考虑，形成整体解决方案，能够较好地解决云计算环境分布式存储系统中副本如何选择节点放置的问题。
-
基于第1节副本放置问题的定义和假设，并结合免疫优化算法的核心思想，本文提出了基于免疫优化策略的副本放置算法。在接下来的内容中详细阐述了该算法的数学描述及其含义：
首先，定义了算法的目标函数：
$$ \text{Functio}{{\text{n}}_{C}}=\sum\limits_{i\in N}{\sum\limits_{j\in {{M}_{i}}}{\frac{1}{\text{Per}{{\text{f}}_{i}}}}}{{d}_{ij}}{{C}_{ij}} $$ (1) 其次，给出了其余重要参数的表达式：
$$ i, j\in \left[1, 2, \cdots, N \right] $$ (2) $$ {{d}_{i, j}}=\sqrt{{{({{x}_{i}}-{{x}_{j}})}^{2}}+{{({{y}_{i}}-{{y}_{j}})}^{2}}} $$ (3) $$ {{M}_{i}}\text{=}\left\{ i, j|\, {{d}_{i, j}}\le \text{Dist}, \, i\ne j \right\} $$ (4) $$ {{C}_{i, j}}, \, {{L}_{j}}\, \in \left[0, 1 \right] $$ (5) $$ \sum\limits_{j\in {{M}_{i}}}{{{C}_{i, j}}=1} $$ (6) $$ \sum\limits_{j\in {{M}_{i}}}{{{L}_{i}}=R} $$ (7) 式(1) 定义了副本访问的代价计算函数，其中$ \text{Per}{{\text{f}}_{i}} $表示节点本身的性能指标。基于免疫优化策略的副本放置算法要保证整体副本访问代价最小化，因此该表达式取得最小值的节点即选择成为副本放置的节点。式(2) 定义了分布式存储系统中节点的编号，并且节点总数为$ N $。式(3) 定义了任意两个节点在平面空间上的距离。式(4) 定义了集合$ M $，对于给定的节点$ i $，集合$ M $表示与该节点之间距离小于距离阈值$ \text{Dist} $的节点集。式(5) 中$ {{C}_{i}}_{j} $的取值如果为1，则节点$ i $由节点$ j $提供副本访问，如果取值为0，则表示节点$ i $不由节点$ j $提供副本访问。式(6) 的意义是，在距离阈值范围内，只有一个节点用于副本的放置。式(7) 说明所有副本放置节点数目与最初定义的副本数目均为$ R $。
-
针对每一轮算法产生的抗体集群，需要对解集合中各个抗体进行多样性评价，其中对于个体的评价是以期望繁殖率$ P $为标准的。
1) 抗体与抗原之间的亲和度
抗体与抗原之间的亲和度大小表明节点作为副本放置位置的适合度。根据前一节定义的算法目标函数可以得到：
$$ \begin{matrix} \begin{matrix} \text{Functio}{{\text{n}}_{A}}\text{=} \\ \ \frac{1}{\text{Functio}{{\text{n}}_{C}}+\text{MaxVal}\sum\limits_{i\in N}{\min \left\{ (\sum\limits_{j\in {{M}_{i}}}{\text{failure}})-0.03,0 \right\}}}\ \\ \end{matrix} \\ \end{matrix} $$ (8) 此处为抗体与抗原之间的亲和度计算函数。分母的后一项表示，如果节点在未来的一段时间$ T $内可能失效的概率大于预先设定的节点失效概率阈值，那么该节点被选择为副本放置的可能性将大大降低。
2) 抗体之间的亲和度
抗体之间的亲和度，表明解集合中抗体之间的相似性。相似度越高的抗体集，越能构成最优集合。由于此处只考虑抗体之间的相似性，并没有将顺序加入影响因素。因此，本文借鉴了一种部分匹配的算法——R位连续方法，用来计算抗体之间的亲和度。
3) 抗体浓度
抗体浓度$ {{C}_{A}} $表明解群体中相似群体所占总群体的比例大小。根据抗体之间的亲和度可知相似抗体的整体数目，并且群体中个体总数已知，很容易得到抗体浓度。
4) 个体期望繁殖概率
在免疫优化算法中，对个体的评价是至关重要的。这里采用个体的期望繁殖概率作为评价个体的指标：
$$ P\text{=}\alpha \frac{\text{Functio}{{\text{n}}_{A}}}{\sum{\text{Functio}{{\text{n}}_{A}}}}\text{+}(1-\alpha )\frac{{{C}_{A}}}{\sum{{{C}_{A}}}} $$ (9) 个体的期望繁殖概率由抗体与抗原间的亲和度，以及抗体浓度共同决定，此处$ \alpha $作为一个常数，表示种群的多样性评价参数，用来调节两个因素的影响程度。
-
根据图 1免疫优化算法的一般流程，并结合副本放置问题的具体解决过程，本小节给出了基于免疫优化策略副本放置算法的详细步骤。
1) 对副本放置问题进行分析，选择适合云计算环境分布式存储场景的节点进行副本的放置。依据2.2.1节给出的数学表达式作算法的初始化工作。
2) 整个群体中个体总数为N，随机选取m个抗体作为初始的抗体群，并且m作为记忆群体的个体总数。
3) 依据式(9) 对初始抗体群中的个体，计算其期望繁殖概率P。
4) 依据期望繁殖概率P的值，对初始抗体群中的个体进行降序排列，并选取前面N个作为父代群体，另外选取前面m个存入记忆群体中。
5) 判断是否满足结束条件。如满足，则算法结束。如不满足，则继续。
6) 根据步骤4) 的结果，对抗体群体进行选择、交叉、变异等免疫操作，产生新群体，和记忆群体共同构成新群体。
7) 转至步骤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中已经详细给出，用于指导算法运行的具体流程。对于分布式存储系统中节点的失效概率，本文采取如下的处理方法：在未来的一段时间$ T $内，为每个节点随机分配一个可能的失效概率值failure，并且其取值范围为[0.01, 0.05]，该取值范围为经验取值，可以根据实际分布式存储系统中节点的历史情况重新定义。其中，$ T $表示的是某次用户访问副本时间开销的最大值，该值用来保证副本节点确定之后，用户在访问相应节点的副本过程中，节点发生不会发生失效的情况。
表 1 仿真实验相关参数
参数 取值 种群规模 50 记忆库规模 5 交叉概率 0.5 变异概率 0.4 多样性评价参数 0.9 选择操作 轮盘赌选择机制 交叉操作 单点交叉 变异操作 随机选择变异位置 图 2和图 3给出了在是否考虑节点可能失效的前提下，基于免疫优化策略的副本放置算法的收敛曲线图。从图中所示的结果可知，与未考虑节点失效的副本放置情况相比，在副本放置问题中将节点可能发生失效的因素加入考虑范畴，并不会影响副本放置算法的收敛情况。算法能够在不影响副本放置节点选择效率的前提下，保证用户对副本访问开销的最小化。
图 2 未考虑节点失效概率的算法收敛曲线
图 3 考虑节点失效概率的算法收敛曲线
图 4和图 5显示了在是否考虑节点失效的前提下，分布式存储系统中节点的分布情况以及最终选取的副本放置节点的位置。从两图中可以看出，对于副本放置节点的选取结果完全不同。如果节点自身性能受限，无法满足用户对于副本的访问要求，那么该节点也就没有资格被选为副本放置的位置；与此同时，如果节点在未来一段时间内可能失效，那么该节点同样不能提供副本的访问服务，选择该节点作为副本放置的位置也就没有任何意义。基于免疫优化策略的副本放置算法综合考虑了以上两种影响情况，使得副本放置节点的选择更加全面，合理。并且在副本放置节点的选择过程中，从副本整体访问开销着手，副本放置节点一旦确定，其整体开销必然最小化，这样便均衡了用户对于副本放置节点的访问频率，均衡了节点负载。
图 4 未考虑节点失效概率的副本节点选择情况
图 5 考虑节点失效概率的副本节点选择情况
-
副本放置问题不仅在分布式系统中是一个关键研究课题，同时在云计算和分布式存储系统也扮演着重要角色。副本放置的位置对分布式存储系统的性能，可靠性以及负载均衡都有着很大的影响。针对云计算环境下分布式存储的副本放置问题，本文提出一种基于免疫优化策略的副本放置算法，能够选取最佳的副本放置节点，仿真试验结果验证了算法的有效性，能够降低用户访问副本的整体开销。
Data Replica Placement Algorithm Based on Immune Optimization Strategy
-
摘要: 副本放置问题在云计算环境分布式存储系统中是一个关键问题。针对现有副本放置算法存在的数据副本访问开销较大，节点负载不均衡的问题，提出了一种基于免疫优化策略的副本放置算法。通过计算节点的亲和度，并借助免疫优化系统特有的克隆选择和免疫记忆机制，对副本节点的评价和选择更加合理。基于Matlab的仿真实验证实该算法能够降低分布式存储系统的副本访问开销，均衡节点负载。Abstract: 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.
-
Key words:
- cloud computing /
- distributed storage /
- immune optimization strategy /
- replica placement
-
表 1 仿真实验相关参数
参数 取值 种群规模 50 记忆库规模 5 交叉概率 0.5 变异概率 0.4 多样性评价参数 0.9 选择操作 轮盘赌选择机制 交叉操作 单点交叉 变异操作 随机选择变异位置 
下载: 导出CSV
-
[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. http://www.educause.edu/library/resources/above-clouds-berkeley-view-cloud-computing [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. doi: 10.1016/j.future.2008.12.001 [4] 王意洁, 孙伟东, 周松, 等.云计算环境下分布存储关键技术[J].软件学报, 2012, 23(4):962-986. http://www.cnki.com.cn/Article/CJFDTOTAL-YDLG201604010.htm 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. http://www.cnki.com.cn/Article/CJFDTOTAL-YDLG201604010.htm [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. doi: 10.1016/S0167-8191(02)00094-7 [6] ZHENG Z, ZHANG Y, LYU M R. CloudRank:a QoS-drive component ranking framework for cloud computing[C]//201029th 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. doi: 10.1109/TPDS.2011.27 [9] 吴嘉轩, 代钰, 张斌, 等.基于拓扑匹配的组件服务副本放置算法[J].电子科技大学学报, 2015, 44(6):905-910. http://www.cnki.com.cn/Article/CJFDTOTAL-DKDX201506019.htm 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. http://www.cnki.com.cn/Article/CJFDTOTAL-DKDX201506019.htm [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. http://i-scholar.in/index.php/CiiTAISML/article/view/107386 [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. http://www.sciencedirect.com/science/article/pii/S0743731597913927 [14] FARMER J, PACKARD N, PERELSON A. The immune system, adaptation and machine learning[J]. Phys D:Nonlinear Phenom, 1986, 22(4):187-204. http://www.sciencedirect.com/science/article/pii/016727898690240X -
点击查看大图
图(5) / 表(1)
计量
- 文章访问数: 5438
- HTML全文浏览量: 1902
- PDF下载量: 116
- 被引次数: 0
