基于多目标分解策略的副本布局算法研究

doi:10.3778/j.issn.1673-9418.1908062

摘要/Abstract

摘要：

高效的副本布局是分布式存储系统可靠性的重要保障。数据副本既可以增加系统数据的可用性，又能够提高系统的负载均衡能力，但同时也会带来能量消耗问题。针对副本带来的效能提升和能耗之间的冲突，提出了一种基于多目标分解策略的副本布局算法（MDSRL）。将平均文件不可用性、负载均衡、能耗作为三个优化对象，并将多目标优化问题分解成多个标量子问题同时进行优化，每一个子问题的优化都借助相邻的若干个子问题的信息，经过多次迭代优化后，试图找出一组能够在这三个目标上都有良好表现的折衷解。实验表明MDSRL算法所求出的解在平均文件不可用性和能耗上比多目标进化算法（MOE）减少了3.11个百分点和2.3个百分点，在平均文件不可用性和负载变化上比多目标副本管理算法（MORM）减少了68.1个百分点和0.2个百分点，且解的分布性和收敛性更好。

关键词: 分布式存储, 多目标优化, 分解策略, 副本布局

Abstract:

The efficient replica layout is an important guarantee for distributed storage systems reliability. Data replica can increase system data availability, as well as improve the system load balance ability, but it also produces energy consumption problems simultaneously. Aiming at the conflicts between efficiency improvement and energy consumption replicas bring, replica layout algorithm based on a multi-objective decomposition strategy (MDSRL) is proposed. It regards the mean file unavailability, load balance and energy consumption as optimization objectives, decomposes multi-objective problems into multiple scalar problems and optimizes them simultaneously. The optimization of each scalar problem is based on the information of several adjacent scalar problems. After multiple iterations of optimization, this paper tries to find a set of tradeoff solutions that can perform well on all three objectives. Experiments demonstrate that the solutions obtained by the MDSRL algorithm are 3.11 and 2.3 percentage points less than the multi-objective evolutionary (MOE) algorithm in mean file unavailability and energy consumption, and are 68.1 and 0.2 percentage points less than the multi-objective replica management (MORM) algorithm in the mean file unavailability and load variance, and the solutions distribution and convergence are better.

Key words: distributed storage, multi-objective optimization, decomposition strategy, replica layout

邵必林，贺金能，边根庆. 基于多目标分解策略的副本布局算法研究[J]. 计算机科学与探索, 2020, 14(9): 1490-1500.

SHAO Bilin, HE Jinneng, BIAN Genqing. Research on Replica Layout Algorithm Based on Multi-objective Decomposition Strategy[J]. Journal of Frontiers of Computer Science and Technology, 2020, 14(9): 1490-1500.

参考文献

[1] Wang Y J, Sun W D, Zhou S, et al. Key technologies of distributed storage for cloud computing[J]. Journal of Software, 2012, 23(4): 962-986. 王意洁, 孙伟东, 周松, 等. 云计算环境下的分布存储关键技术[J]. 软件学报, 2012, 23(4): 962-986.
[2] Tao Y C, Ba Y, Shi L, et al. Management mechanism of dynamic cloud data replica based on availability[J]. Journal of Chinese Computer Systems, 2018, 39(3): 490-495. 陶永才, 巴阳, 石磊, 等. 一种基于可用性的动态云数据副本管理机制[J]. 小型微型计算机系统, 2018, 39(3): 490-495.
[3] Li S, Dang X, Wang X, et al. Replica update strategy and algorithms for replica placement[J]. Journal of Frontiers of Computer Science and Technology, 2016, 10(11): 1633-1640.李帅, 党鑫, 王旭, 等. 副本放置中的更新策略及算法[J]. 计算机科学与探索, 2016, 10(11): 1633-1640.
[4] Qu K Y, Meng L M, Yang Y. A dynamic replica strategy based on Markov model for hadoop distributed file system (HDFS)[C]//Proceedings of the 4th International Conference on Cloud Computing and Intelligence Systems, Beijing, Aug 17-19, 2016. Piscataway: IEEE, 2016: 337-342.
[5] Cui L Z, Zhang J H, Yue L X, et al. A genetic algorithm based data replica placement strategy for scientific applications in clouds[J]. IEEE Transactions on Services Computing, 2015, 11(4): 727-739.
[6] Luo S W, Hou M S, Niu X Z, et al. Data replica placement algorithm based on immune optimization strategy[J]. Journal of University of Electronic Science and Technology, 2017, 46(5): 741-746. 罗四维, 侯孟书, 牛新征, 等. 基于免疫优化策略的副本放置算法[J]. 电子科技大学学报, 2017, 46(5): 741-746.
[7] Hassan O A H, Ramaswamy L, Miller J A, et al. Replication in overlay networks: a multi-objective optimization approach[C]//Proceedings of the 4th International Conference on Collaborative Computing: Networking, Applications and Worksharing, Orlando, Nov 13-16, 2008. Berlin, Heidelberg: Springer, 2008: 512-528.
[8] Deb K, Pratap A, Agarwal S, et al. A fast and elitist multi-objective genetic algorithm: NSGA-II[J]. IEEE Transactions on Evolutionary Computation, 2002, 6(2): 182-197.
[9] Long S Q, Zhao Y L, Chen W. MORM: a multi-objective optimized replication management strategy for cloud storage cluster[J]. Journal of Systems Architecture, 2014, 60(2): 234-244.
[10] Zhang Q F, Li H. MOEA/D: a multiobjective evolutionary algorithm based on decomposition[J]. IEEE Transactions on Evolutionary Computation, 2007, 11(6): 712-731.
[11] Hamrouni T, Slimani S, Charrada F B. A survey of dynamic replication and replica selection strategies based on data mining techniques in data grids[J]. Engineering Applications of Artificial Intelligence, 2016, 48: 140-158.
[12] Wu X G. Data sets replicas placements strategy from cost-effective view in the cloud[J]. Scientific Programming, 2016(11): 1-13.
[13] Shao Y L, Li C L, Tang H L. A data replica placement strategy for IoT workflows in collaborative edge and cloud environments[J]. Computer Networks, 2019, 148: 46-59.
[14] Xie J D, Wu J G. Asynchronous round-based strategy for replica placement[J]. Journal of Frontiers of Computer Science and Technology, 2018, 12(8): 1339-1349. 谢纪东, 武继刚. 间隔执行的异步副本放置策略[J]. 计算机科学与探索, 2018, 12(8): 1339-1349.
[15] Grace R K, Manimegalai R. Dynamic replica placement and selection strategies in data grids-a comprehensive survey[J]. Journal of Parallel and Distributed Computing, 2014, 74(2): 2099-2108.
[16] Lin C, Chen Y, Huang J W, et al. A survey of models and solutions of multi-objective optimization for QoS in services computing[J]. Chinese Journal of Computers, 2015, 38(10): 1907-1923. 林闯, 陈莹, 黄霁崴, 等. 服务计算中服务质量的多目标优化模型与求解研究[J]. 计算机学报, 2015, 38(10): 1907-1923.
[17] Zhu Y Q, Yu Y, Wang W Y, et al. A balanced allocation strategy for file assignment in parallel I/O systems[C]//Proceedings of the 5th International Conference on Networking, Architecture, and Storage, Macau, China, Jul 15-17, 2010. Washington: IEEE Computer Society, 2010: 257-266.
[18] Phan D H, Suzuki J, Carroll R, et al. Evolutionary multiobjective optimization for green clouds[C]//Proceedings of the 14th Annual Conference Companion on Genetic and Evolutionary Computation, Philadelphia, Jul 7-11, 2012. New York: ACM, 2012: 19-26.
[19] Kusic D, Kephart J O, Hanson J E, et al. Power and performance management of virtualized computing environments via lookahead control[J]. Cluster Computing-The Journal of Networks Software Tools and Applications, 2009, 12(1): 1-15.
[20] Xie T, Sun Y. A file assignment strategy independent of workload characteristic assumptions[J]. ACM Transactions on Storage, 2009, 5(3): 10.