北京邮电大学学报

  • EI核心期刊

北京邮电大学学报 ›› 2021, Vol. 44 ›› Issue (6): 116-121.doi: 10.13190/j.jbupt.2021-026

• 研究报告 • 上一篇    下一篇

哈夫曼树的异构部分重复码构造

余春雷1,2, 王静3, 杨成福1, 彭小利1,2   

  1. 1. 四川文理学院 智能制造学院, 达州 635002;
    2. 智能制造产业技术研究院, 达州 635002;
    3. 长安大学 信息工程学院, 西安 710064
  • 收稿日期:2021-03-04 出版日期:2021-12-28 发布日期:2021-12-28
  • 通讯作者: 王静(1982—),女,教授,E-mail:jingwang@chd.edu.cn. E-mail:jingwang@chd.edu.cn
  • 作者简介:余春雷(1992—),男,硕士生.
  • 基金资助:
    国家自然科学基金项目(62001059);陕西省重点研发计划项目(2021GY-019);智能制造产业技术研究院开放基金项目(ZNZZ2106)

Construction of Heterogeneous Fractional Repetition Codes of Huffman Tree

YU Chun-lei1,2, WANG Jing3, YANG Cheng-fu1, PENG Xiao-li1,2   

  1. 1. Intelligent Manufacturing Institute, Sichuan University of Arts and Science, Dazhou 635002, China;
    2. Intelligent Manufacturing Industry Technology Research Institute, Dazhou 635002, China;
    3. School of Information Engineering, Chang'an University, Xi'an 710064, China
  • Received:2021-03-04 Online:2021-12-28 Published:2021-12-28

摘要: 针对分布式存储系统中数据被访问频率的不同,提出一种基于哈夫曼树的可变重复度的异构部分重复(HVFR)码,将不同访问频率的数据块作为哈夫曼树带有确定权值的叶子节点,构造哈夫曼树并确定数据块的重复度,利用成对平衡设计构造异构部分的重复码,能够提高热数据的并行访问速度和系统存储效率. 性能分析和实验结果表明,与里所码以及简单再生码相比,HVFR码可以显著减少故障节点的修复时间及修复局部性,提高热数据的并行访问速度,达到负载均衡,且计算复杂度低.

关键词: 分布式存储, 冷热数据, 部分重复码, 哈夫曼树

Abstract: Considering access frequency differences of data in distributed storage systems, a heterogeneous variable fractional repetition (HVFR) code based on Huffman tree is proposed. First, taking the data blocks with different access frequencies as the weighted leaf nodes of the Huffman tree, the Huffman tree is constructed and the duplication of the data blocks is determined. Then, the pairwise balanced design is used to construct heterogeneous fractional repetition codes. Performance analysis and experimental results show that, compared with reed-solomon codes and simple regenerating codes, HVFR codes can significantly reduce the repair time and repair locality of the failed nodes, improves the parallel access speed of the hot data, and achieves load balance with low computation complexity.

Key words: distributed storage, hot and cold data, fractional repetition code, Huffman tree

中图分类号: