图因子分解的故障节点快速修复
作者:
作者单位:

作者简介:

通讯作者:

中图分类号:

基金项目:

陕西省重点研发计划(2021GY-019), 智能制造产业技术研究院开放基金(ZNZZ2106)


Fast Repair of Faulty Nodes Based on Graph Factorization
Author:
Affiliation:

Fund Project:

  • 摘要
  • |
  • 图/表
  • |
  • 访问统计
  • |
  • 参考文献
  • |
  • 相似文献
  • |
  • 引证文献
  • |
  • 增强出版
  • |
  • 文章评论
    摘要:

    为了提高分布式存储系统中故障节点的修复效率, 提出一种新的部分重复(fractional repetition, FR)码的构造算法. 该算法利用完全图的因子分解进行构造, 称为CGFBFR (complete graph factorization based FR)码. 该算法首先对完全图进行因子分解, 分解完成以后确定完全图的因子分解个数, 根据需要存储数据块的重复度来选择完全图的因子个数, 将完全图选中的因子所有顶点当做分布式存储系统中需要存储的数据块, 然后对选中因子图的边进行标记, 标记的边当做分布式数据节点进行存储. 最后根据选中的因子的顶点和边生成编码矩阵, 在分布式存储系统中按照编码矩阵中的数据对数据块分别进行存储. 实验仿真结果显示, 本文提出的一种新的部分重复码构造算法, 与分布式存储系统中的里所(reed-solomon, RS)码、简单再生码(simple regenerating codes, SRC)以及最新的循环可变部分重复(variable fractional repetition, VFR)码相比, 在系统修复故障节点时, 能够快速地修复故障节点, 有效降低了故障节点的修复带宽开销、修复局部性、修复复杂度, 而且构造过程简单, 同时可以灵活选择构造参数, 广泛适用于分布式存储系统中.

    Abstract:

    To improve the efficiency of repairing faulty nodes in a distributed storage system, this study proposes a new construction algorithm for fractional repetition (FR) codes. The algorithm resorts to the factorization of the complete graph for node construction, and the nodes constructed are referred to as complete graph factorization based FR (CGFBFR) nodes. Specifically, the complete graph is factorized, and the number of factors generated from the complete graph after the factorization is completed is determined. The number of factors of the complete graph is selected according to the repetition degrees of the data blocks that need to be stored. All the vertices of the selected factors of the complete graph are regarded as the data blocks that need to be stored in the distributed storage system. Then, the edges of the selected factor graph are marked and stored as distributed data nodes. Finally, an encoding matrix is generated with the vertices and edges of the selected factors, and the distributed storage system stores the data blocks respectively according to the data in the encoding matrix. The experimental simulation results show that compared with the Reed-Solomon (RS) codes, the simple regenerating codes (SRCs), and the latest cyclic variable FR (VFR) codes in the distributed storage system, the codes generated by the new FR code construction algorithm proposed in this study can quickly repair the faulty node when the system repairs the node. The proposed algorithm can be widely applied to distributed storage systems as it reduces the repair bandwidth overhead, repair locality, and repair complexity of the faulty node, provides a simple construction process, and allows flexible selection of construction parameters.

    参考文献
    相似文献
    引证文献
引用本文

余春雷,王娥,刘星,谢锐,冉彪.图因子分解的故障节点快速修复.计算机系统应用,2023,32(2):394-399

复制
分享
文章指标
  • 点击次数:
  • 下载次数:
  • HTML阅读次数:
  • 引用次数:
历史
  • 收稿日期:2022-06-15
  • 最后修改日期:2022-09-07
  • 录用日期:
  • 在线发布日期: 2022-11-04
  • 出版日期:
您是第位访问者
版权所有:中国科学院软件研究所 京ICP备05046678号-3
地址:北京海淀区中关村南四街4号 中科院软件园区 7号楼305房间,邮政编码:100190
电话:010-62661041 传真: Email:csa (a) iscas.ac.cn
技术支持:北京勤云科技发展有限公司

京公网安备 11040202500063号