Construction of Block Design-Based Piggybacking Codes

doi:10.16183/j.cnki.jsjtu.2024.203

Abstract

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

CLC Number:

TN911.2

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.

Figures/Tables 8

Fig.1

Fig.2

Fig.3

Fig.4

Fig.5

Fig.6

Fig.7

Fig.8

References 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.