扩展子条带的piggybacking编码构造

Construction of substripe-added piggybacking codes

摘要:

为解决现有piggybacking编码存在的修复度大、校验节点修复带宽高以及无法实现多节点快速修复等问题,提出一种扩展子条带的piggybacking编码(substripe-added piggybacking,SAP)构造方案。SAP构造在最大距离可分(maximum distance separable,MDS)码的基础上扩展子条带,将信息节点数据块分区均匀嵌入,校验节点数据块循环移位放置。通过理论推导,确定SAP信息节点和校验节点平均修复带宽率、平均修复度率。最后,将SAP与RSR-I、RSR-II和OOP就存储开销、修复带宽开销和修复度3个方面进行对比。结果表明:与RSR-I、RSR-II和OOP相比,扩展子条带的piggybacking编码不仅实现了修复度最优,而且在保证信息节点修复带宽开销较低的同时,明显降低了校验节点的修复带宽开销,且能快速修复多校验节点故障,明显改善了多校验节点故障修复带宽过高的不足。本文提出的SAP编码显著提升了piggybacking编码的数据恢复效率,尤其针对多校验节点故障,给出了一种快速修复算法,为piggybacking编码的优化提供了有效方案。

Abstract:

To address the issues of large repair degree, high repair bandwidth of parity nodes, and the inability to achieve fast repair of multiple nodes in existing piggybacking codes, a construction scheme of substripe-added piggybacking (SAP) codes is proposed in this paper. Based on maximum distance separable (MDS) codes, the proposed SAP codes extend the substripe, embed the data blocks of the information nodes by region regularly, and place the data blocks of the parity nodes using cyclic shifts. Through theoretical derivations, the average repair bandwidth rates and average repair degree rates of information nodes and parity nodes in SAP are determined. Finally, SAP is compared with RSR-I, RSR-II, and OOP in terms of three aspects: storage overhead, repair bandwidth overhead, and repair degree. The results show that, compared with RSR-I, RSR-II, and OOP, the SAP coding scheme not only achieves optimal repair degree but also significantly reduces parity node repair bandwidth while maintaining low information node repair bandwidth. Additionally, it enables rapid repair of multiple parity node failures, effectively addressing the issue of excessively high repair bandwidth in multiple parity node failures. The SAP coding proposed in this paper significantly improves the data recovery efficiency of piggybacking codes. In particular, a fast repair algorithm is provided to address multiple parity node failures, offering an effective approach for optimizing the piggybacking codes.