基于区组设计的Piggybacking编码构造

doi:10.16183/j.cnki.jsjtu.2024.203

上海交通大学学报 ›› 2026, Vol. 60 ›› Issue (1): 100-111.doi: 10.16183/j.cnki.jsjtu.2024.203

基于区组设计的Piggybacking编码构造

李瞳¹, 王静¹(), 张洁薇¹, 杨红志¹, 刘向阳²

¹ 长安大学信息工程学院, 西安 710064
² 西北工业大学电子信息学院, 西安 710129

收稿日期:2023-05-05 修回日期:2024-07-24 接受日期:2024-09-09 出版日期:2026-01-28 发布日期:2026-01-27
通讯作者: 王静 E-mail:jingwang@chd.edu.cn.
作者简介:李瞳(2000—),硕士生,从事网络编码及分布式存储编码等方面的研究.
基金资助:
国家自然科学基金(62001059);陕西省重点研发计划项目(2024GX-YBXM-068)

Construction of Block Design-Based Piggybacking Codes

LI Tong¹, WANG Jing¹(), ZHANG Jiewei¹, YANG Hongzhi¹, LIU Xiangyang²

¹ School of Information Engineering, Chang’an University, Xi’an 710064, China
² School of Electronics and lnformation, Northwestern Polytechnical University, Xi’an 710129, China

Received:2023-05-05 Revised:2024-07-24 Accepted:2024-09-09 Online:2026-01-28 Published:2026-01-27
Contact: WANG Jing E-mail:jingwang@chd.edu.cn.

摘要/Abstract

摘要：

现有Piggybacking编码在最大距离可分(MDS)码的基础上能够有效减小信息节点的修复带宽开销,但存在修复度大、校验节点修复带宽高等问题,同时忽略了实际分布式存储系统中数据冷热程度的差异.为此提出一种基于区组设计的Piggybacking编码构造,对热数据节点提供更高等级的保护,采用区组设计,对冷热数据节点进行非均匀分组,将热数据符号捎带到对应校验节点中,通过一定规则生成冷、热数据校验块和斜校验块.理论分析与实验仿真发现,与现有Piggybacking编码相比,基于区组设计的Piggybacking编码显著降低了故障节点的平均修复带宽率和平均修复度率;且相较于冷数据节点,热数据节点的修复带宽开销更低.

关键词: Piggybacking编码, 区组设计, 冷热数据, 修复带宽, 修复度

Abstract:

Based on maximum distance separable (MDS) codes, existing Piggybacking codes can reduce the repair bandwidth overhead of systematic nodes effectively, but there are still challenges such as larger repair degree, higher repair bandwidth of parity nodes, and the overlooking of differences in hot and cold data in the actual distributed storage systems. To address these issues, a Piggybacking construction based on block design is proposed, which can provide higher levels of protection for hot data nodes. Specifically, a block design is used to group hot and cold data nodes non-uniformly, in which hot data symbols are piggybacked into the corresponding parity nodes. Moreover, cold data parity blocks, hot data parity blocks, and slant parity blocks are generated according to specific rules. Theoretical analyses and experimental simulations show that, compared with existing Piggybacking codes, the proposed block design-based Piggybacking codes reduce the average repair bandwidth rate and average repair degree rate of the failed nodes significantly. Additionally, the repair bandwidth overhead of hot data nodes is much lower than that of cold data nodes.

Key words: Piggybacking codes, block design, cold and hot data, repair bandwidth, repair degree

中图分类号:

TN911.2

李瞳, 王静, 张洁薇, 杨红志, 刘向阳. 基于区组设计的Piggybacking编码构造[J]. 上海交通大学学报, 2026, 60(1): 100-111.

LI Tong, WANG Jing, ZHANG Jiewei, YANG Hongzhi, LIU Xiangyang. Construction of Block Design-Based Piggybacking Codes[J]. Journal of Shanghai Jiao Tong University, 2026, 60(1): 100-111.

图/表 8

图1

图2

图3

图4

图5

图6

图7

图8

参考文献 20

[1]	QI Y C, FENG D, HOU B B. Towards building reliable and cost-efficient distributed storage systems[J]. IEEE Access, 2020, 8: 157862-157877. doi: 10.1109/Access.6287639 URL
[2]	SINGAL S M, RAKESH N, MATAM R. Optimal storage and repair in distributed storage system[C]// 2017 7th International Conference on Cloud Computing, Data Science & Engineering-Confluence. Noida, India: IEEE, 2017: 461-465.
[3]	GAO X, XU P. Distributed storage system for small files[C]// 2021 2nd International Conference on Artificial Intelligence and Computer Engineering. Hangzhou, China: IEEE, 2021: 736-739.
[4]	RAJ P, SINHA S. Enhancing file recovery from distributed file systems (DFSs) using erasure coding and replication[C]// 2024 11th International Conference on Reliability, Infocom Technologies and Optimization (Trends and Future Directions). Noida, India: IEEE, 2024: 1-5.
[5]	XU F L, WANG Y J, MA X K. Online encoding for erasure-coded distributed storage systems[C]// 2017 IEEE 37th International Conference on Distributed Computing Systems Workshops. Atlanta, USA: IEEE, 2017: 338-342.
[6]	CHEN T T, ZHANG X D. Sparse and balanced MDS codes over small fields[J]. IEEE Transactions on Information Theory, 2022, 68(8): 5112-5125. doi: 10.1109/TIT.2022.3162524 URL
[7]	ZHONG L, HAN G J, HOU H X, et al. Optimizing repair-cost of locally repairable codes for hot data in cluster storage systems[C]// 2022 IEEE International Conference on Big Data. Osaka, Japan: IEEE, 2022: 3235-3241.
[8]	LUO G J, EZERMAN M F, LING S. Three new constructions of optimal locally repairable codes from matrix-product codes[J]. IEEE Transactions on Information Theory, 2023, 69(1): 75-85. doi: 10.1109/TIT.2022.3203591 URL
[9]	HAO J, SHUM K W, XIA S T, et al. Optimal locally repairable codes for parallel reading[J]. IEEE Access, 2020, 8: 80447-80453. doi: 10.1109/Access.6287639 URL
[10]	CHEN B, FANG W J, XIA S T, et al. Improved bounds and singleton-optimal constructions of locally repairable codes with minimum distance 5 and 6[J]. IEEE Transactions on Information Theory, 2021, 67(1): 217-231. doi: 10.1109/TIT.18 URL
[11]	YUAN S, HUANG Q. Generalized piggybacking codes for distributed storage systems[C]// 2016 IEEE Global Communications Conference. Washington D.C., USA: IEEE, 2016: 1-6.
[12]	SHI H, JIANG Z Y, HUANG Z Y, et al. Piggybacking codes: MDS array codes with linear sub-packetization to achieve lower repair bandwidth[C]// GLOBECOM 2023-2023 IEEE Global Communications Conference. Kuala Lumpur, Malaysia: IEEE, 2023: 7351-7356.
[13]	JIANG Z Y, SHI H, HUANG Z Y, et al. Toward lower repair bandwidth of piggybacking codes via jointly design for both data and parity nodes[C]// GLOBECOM 2023-2023 IEEE Global Communications Conference. Kuala Lumpur, Malaysia: IEEE, 2023: 7345-7350.
[14]	SUN R, ZHANG L, LIU J W. A new piggybacking design with low-repair bandwidth and complexity[J]. IEEE Communications Letters, 2021, 25(7): 2099-2103. doi: 10.1109/LCOMM.2021.3071855 URL
[15]	RASHMI K V, SHAH N B, RAMCHANDRAN K. A piggybacking design framework for read-and download-efficient distributed storage codes[C]// 2013 IEEE International Symposium on Information Theory. Istanbul, Türkiye: IEEE, 2013: 331-335.
[16]	RASHMI K V, SHAH N B, RAMCHANDRAN K. A piggybacking design framework for read-and download-efficient distributed storage codes[J]. IEEE Transactions on Information Theory, 2017, 63(9): 5802-5820.
[17]	SHANGGUAN C, GE G N. A new piggybacking design for systematic MDS storage codes[J]. Designs, Codes and Cryptography, 2019, 87(12): 2753-2770. doi: 10.1007/s10623-019-00650-9
[18]	LI G Y, LIN X, TANG X H. An efficient one-to-one piggybacking design for distributed storage systems[J]. IEEE Transactions on Communications, 2019, 67(12): 8193-8205. doi: 10.1109/TCOMM.26 URL
[19]	SHI H, HOU H X, HAN Y S, et al. New piggybacking codes with lower repair bandwidth for any single-node failure[C]// 2022 IEEE International Symposium on Information Theory. Espoo, Finland: IEEE, 2022: 2601-2606.
[20]	COLBOURN C J. CRC handbook of combinatorial designs[M]. Boca Raton, USA: CRC Press, 2010.

基于区组设计的Piggybacking编码构造

Construction of Block Design-Based Piggybacking Codes

RichHTML

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

图/表 8

参考文献 20

相关文章 1

编辑推荐

Metrics

本文评价