ISSN 1000-1239 CN 11-1777/TP

计算机研究与发展 ›› 2021, Vol. 58 ›› Issue (2): 305-318.doi: 10.7544/issn1000-1239.2021.20200383

所属专题: 2021大数据时代的存储系统与智能存储技术专题

• 系统结构 • 上一篇    下一篇



  1. (湖南大学信息科学与工程学院 长沙 410082) (
  • 出版日期: 2021-02-01
  • 基金资助: 

An Ant Colony Optimization Algorithms Based Data Update Scheme for Erasure-Coded Storage Systems

Li Qian, Hu Yupeng, Ye Zhenyu, Xiao Ye, Qin Zheng   

  1. (College of Computer Science and Electronic Engineering, Hunan University, Changsha 410082)
  • Online: 2021-02-01
  • Supported by: 
    This work was supported by the National Natural Science Foundation of China (61872130, 61572181), the Science and Technology Project of Hunan Provincial Department of Communications(201928), and the Key Research and Development Program of Changsha (kq1907103).

摘要: 由于纠删码具备高可用性和高存储空间有效性的特点,采用纠删码为大规模分布式存储系统提供数据持久性已成为事实标准.然而,纠删码的密集型更新操作将导致大量的数据传输和I/O开销.如何减少数据传输量,优化现有网络资源的利用率,以提高纠删码的更新效率,成为纠删码存储系统面临的重要挑战.然而,在多重服务质量(quality of service, QoS)指标下,目前对纠删码更新效率的优化研究很少.针对此问题,提出一种基于蚁群优化算法的多数据节点更新方案(ant colony optimization algorithm based multiple data nodes update scheme, ACOUS),采用2阶段数据更新方式以优化多数据节点更新过程.具体而言,基于多目标蚁群优化更新路由算法(multi-objective ant colony optimization update routing algorithm, MACOU)所构建的多目标更新树,2阶段数据更新方式能有效地进行数据增量收集和校验增量分发.大量的实验结果表明,在典型的数据中心网络拓扑结构下,与TA-Update方案相比,所提方案能够在保证算法收敛的前提下,以可忽略的计算开销为代价,将更新时延降低26%~37%.

关键词: 分布式存储系统, 数据更新, 纠删码, 蚁群优化, 更新时延

Abstract: Owing to the high availability and space-efficiency of erasure codes, they have become the de facto standard to provide data durability in large scale distributed storage systems. The update intensive workloads of erasure codes lead to a large amount of data transmission and I/O cost. As a result, it becomes a major challenge to reduce the amount of data transmission and optimize the use of existing network resources so that the update efficiency of the erasure codes could be improved. However, very little research has been done to optimize the update efficiency of the erasure codes under multiple QoS(quality of service) metrics. In this paper, the proposed update scheme, the ACOUS (ant colony optimization algorithm based multiple data nodes update scheme) employs a two-stage rendezvous data update procedure to optimize the multiple data nodes updates. Specifically, the two-stage rendezvous data update procedure performs the data delta collection and the parity delta distribution efficiently, based on a multi-objective update tree which is built by the MACOU(multi-objective ant colony optimization update routing algorithm). Under typical data center network topologies, extensive experimental results show that, compared with the traditional TA-Update scheme, the proposed scheme is able to achieve 26% to 37% reduction of update delay with convergence guarantee at the cost of negligible computation overhead.

Key words: distributed storage system, data update, erasure codes, ant colony optimization, update delay