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

doi:10.13190/j.jbupt.2021-026

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

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

余春雷^1,2, 王静³, 杨成福¹, 彭小利^1,2

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-lei^1,2, WANG Jing³, YANG Cheng-fu¹, PENG Xiao-li^1,2

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

摘要/Abstract

摘要： 针对分布式存储系统中数据被访问频率的不同,提出一种基于哈夫曼树的可变重复度的异构部分重复(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

中图分类号:

TP391.9

余春雷, 王静, 杨成福, 彭小利. 哈夫曼树的异构部分重复码构造[J]. 北京邮电大学学报, 2021, 44(6): 116-121.

YU Chun-lei, WANG Jing, YANG Cheng-fu, PENG Xiao-li. Construction of Heterogeneous Fractional Repetition Codes of Huffman Tree[J]. Journal of Beijing University of Posts and Telecommunications, 2021, 44(6): 116-121.

[1]	王静, 刘艳, 余春雷, 王秘, 刘向阳. 非均匀故障保护的分组修复码构造[J]. 北京邮电大学学报, 2019, 42(5): 75-82.
[2]	山蕊, 沈绪榜, 蒋林, 朱筠, 宋辉. 面向阵列处理器的分布式共享存储结构设计[J]. 北京邮电大学学报, 2017, 40(4): 9-15.
[3]	谢显中, 王柳苏, 黄倩, 马彬. 具有健康节点协作的高效多节点修复方案[J]. 北京邮电大学学报, 2014, 37(1): 52-56.
[4]	朱艺华, 田志坚, 池凯凯. 分布式存储系统中带宽最优的数据修复策略[J]. 北京邮电大学学报, 2013, 36(3): 25-29.
[5]	王燕滨陈勇林宝军. 基于循环矢量构造的精确修复MDS编码[J]. 北京邮电大学学报, 2012, 35(6): 34-37.
[6]	王宁林雪红林家儒. 网络编码的分布式存储系统理论分析[J]. 北京邮电大学学报, 2009, 32(3): 82-85.

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

Construction of Heterogeneous Fractional Repetition Codes of Huffman Tree

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 6

编辑推荐

Metrics

本文评价