Construction of substripe-added piggybacking codes

doi:10.11918/202406007

扩展子条带的piggybacking编码构造

doi: 10.11918/202406007

杨红志¹ ，王静¹ ，李瞳¹ ，张洁薇¹ ，刘向阳²

1. 长安大学信息工程学院，西安 710018

2. 西北工业大学电子信息学院，西安 710129

基金项目: 国家自然科学基金(62001059) ；陕西省重点研发计划(2024GY-YBXM-068)

详细信息

作者简介

杨红志(1998—)，男，硕士研究生；

王静(1982—)，女，教授，硕士生导师

通讯作者

王静，jingwang@chd.edu.cn

中图分类号: TN911

文献标识码: A

文章编号: 0367-6234(2025)09-0046-10

Construction of substripe-added piggybacking codes

YANG Hongzhi¹ ， WANG Jing¹ ， LI Tong¹ ， ZHANG Jiewei¹ ， LIU Xiangyang²

1. School of Information Engineering, Chang′an University, Xi′an 710018 , China

2. School of Electronics and Information, Northwestern Polytechnical University, Xi′an 710129 , China

摘要

为解决现有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编码的优化提供了有效方案。

关键词

分布式存储 / 最大距离可分码 / 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.

Keywords

distributed storage / maximum distance separable (MDS) codes / piggybacking codes / repair degree / repair bandwidth

1 piggybacking框架 2 扩展子条带的piggybacking编码构造 2.1 SAP框架结构 2.2 SAP具体构造 2.3 构造实例 3 修复分析 3.1 信息节点平均修复带宽率和平均修复度率 3.2 校验节点平均修复带宽率和平均修复度率 4 性能分析 4.1 存储开销 4.2 修复带宽开销 4.3 修复度率 5 结论

当今数字化时代，分布式存储系统（distributed storage systems，DSSs）因其成本低、效率高、安全性好、扩展性强等优势已成为海量数据存储的首选方案^[1-3]。对于DSSs这种超大规模存储集群，存储节点发生故障已经成为一种常态，因此需要存储冗余数据以保证系统存储的可靠性。传统的冗余机制包括三副本复制和纠删码^[4-6]。三副本复制虽易于实现，但存储开销过大；纠删码在保证相同可靠性的情况下，能大大提高存储效率，但其在修复故障节点时需下载原始文件大小的数据，修复带宽开销过高。

针对三副本复制和纠删码的上述局限性，Rashmi等^[7]于2013年首次提出piggybacking编码。在最大距离可分（maximum distance separable，MDS）码基础上，piggybacking编码通过线性组合部分子条带的数据块并将其嵌入至其他子条带，在保留MDS性质、高码率等优势的同时，克服了副本复制存储开销大及纠删码修复带宽开销过高的缺陷。目前，piggybacking编码已被应用于Hadoop分布式文件系统。

Rashmi等^[7-8]提出了3种具体的piggybacking编码方案，即RSR-I、RSR-II和RSR-III。其中，RSR-II可将信息节点的修复带宽开销减少至MDS码的50%，但其编解码复杂度高。Yuan等^[9]提出了保护（MDS only protected，MoP）子条带和捎带（piggybacking protected，PP）子条带组成的piggybacking编码，通过调节MoP子条带的比例，降低信息节点的修复带宽，但两者均未改善校验节点修复带宽高的问题。Li等^[10]、周悦等^[11]提出了一个子条带对应一个校验节点的piggybacking编码（one-to-one piggybacking，OOP）构造，该构造可进一步降低信息节点的修复带宽开销，而且还能对校验节点进行快速修复，但其修复度大且子条带数目较多。张璐^[12]、Sun等^[13-14]提出了双层piggybacking编码思想，当信息节点和校验节点的数目趋向无穷时，故障节点的平均修复带宽率趋于0，但其构造的piggybacking编码修复度大且牺牲了一部分容错能力。Jiang等^[15]通过在OOP构造中引入PP子条带和MoP子条带，提出了一种新的piggybacking编码，改善了校验节点修复带宽开销高和OOP子条带多的问题。Shi等^[16]将OOP码中没有充分利用的校验节点重新进行piggyback函数捎带，进一步降低了修复带宽。但上述piggybacking编码对于多节点同时故障的情况没有相应的快速修复算法。

针对上述piggybacking编码存在的不足，本文提出了一种扩展子条带的piggybacking编码（substripe-added piggybacking，SAP）构造方案。SAP在MDS码的基础上扩展子条带，将信息节点数据块分区均匀嵌入，校验节点数据块循环移位放置，旨在减少故障节点的修复带宽开销和修复度，探索一种具有较高修复效率的piggybacking编码，进而推动piggybacking编码在实际DSSs的应用。

1 piggybacking框架

基于基础码，piggybacking框架将部分子条带的数据块线性组合添加至其他子条带中，从而减少修复带宽开销。以系统MDS码作为基础码的piggybacking框架如图1所示。其中，k为信息节点的数量，r为校验节点数量，f为子条带数。对基础码中的信息数据块 a_u_，_v（1≤u≤k，1≤v≤f）进行MDS码编码，生成校验数据块f_m（a_v）（1≤m≤r，1≤v≤f）， a_v=（a_1，_v，a_2，_v，···，a_k_，_v）^T表示第v个子条带中的k个信息数据块。子条带中的数据块线性组合形成piggyback函数g_m_，_j（a₁，a₂，···，a_j_-1）（1≤m≤r，2≤j≤f），嵌入至其他子条带的校验数据块中组成piggybacking块f_m（a_v）+g_m_，_j（a₁，a₂，···，a_j_-1）。需要注意的是，同一节点的不同数据块不能嵌入至同一个piggyback函数中，且校验节点的数据块不能嵌入至同一校验节点的piggyback函数中。

图1Piggybacking框架

Fig.1Piggybacking framework

对于故障节点的修复：如果故障节点上的失效数据块没有作为piggyback函数嵌入至其他数据块，则可以利用MDS码译码恢复；如果失效数据块作为piggyback函数嵌入至其他数据块，则只需下载嵌入的piggyback函数中其他没有丢失的数据块和对应piggybacking块即可进行修复。piggybacking编码的主要目的是通过减少MDS码译码的方式增加piggybacking块译码，从而减小故障节点的修复带宽开销。平均修复带宽率和平均修复度率可表示为:

(1)

(2)

\{\begin{matrix} γ^{a l l} = \frac{k γ^{s y s} + r γ^{p a r}}{k + r} \\ η^{a l l} = \frac{k η^{s y s} + r η^{p a r}}{k + r} \end{matrix}

(3)

式中：γ^sys、γ^par和γ^all分别为信息节点、校验节点和节点总的平均修复带宽率； η^sys、η^par和η^all分别为信息节点、校验节点和节点总的平均修复度率；γ_i（1≤i≤n，n=k+r）为修复带宽，即节点i故障时，修复节点i需读取和下载的数据块数量；η_i（1≤i≤n，n=k+r）为修复度，即节点i故障时，修复节点i需连接的节点数量。

2 扩展子条带的piggybacking编码构造

本节先介绍SAP框架结构和具体构造，然后阐述f=6时SAP的构造实例。文中所有SAP构造的基础码均采用（n，k，f）MDS码，且满足

k ⩾ r ⌊ f / 2 ⌋

。

2.1 SAP框架结构

图2为

k = r ⌊ f / 2 ⌋

时SAP框架结构，分为6个区域，即A~F。令

τ = ⌈ f / 2 ⌉ ， τ_{1} = ⌊ f / 2 ⌋

。子条带s_i（1≤i≤f+1）为第i个子条带，s_f₊₁为扩展子条带，主要由区域C、F组成。将区域E中的校验数据块从上至下、从左至右复制，置于扩展子条带的前k行，形成区域C，确保区域E中的校验节点发生故障时能进行快速修复。区域A中的信息数据块线性组合形成piggyback函数g_m_，_j（a₁，a₂，···，a_τ），嵌入至区域E中形成piggybacking块f_m（a_v）+g_m_，_j（a₁，a₂，···，a_τ），嵌入至扩展子条带的后r行形成区域F，保证区域A中丢失数据块的快速修复，减少相应数据块的修复带宽开销。将第τ-1个子条带的校验数据块循环移位置于第τ个子条带，第τ-3个子条带的校验数据块循环移位置于第τ-2个子条带，以此类推，完成前τ个子条带的嵌入，形成区域D。区域B则不进行任何操作，以保证该区域发生节点故障时，丢失数据块采用MDS码译码恢复。

图2SAP框架结构

Fig.2SAP framework structure

2.2 SAP具体构造

为了便于理解和表达，将

k ⩾ r ⌊ f / 2 ⌋

时SAP的具体构造同样拆分为6个区域A~F。

区域A、B包含所有原始信息数据块，而且没有进行任何嵌入操作。

区域C进行嵌入操作，具体过程如下：

将子条带s_i（τ+1≤i≤f）的校验数据块复制，然后置于扩展子条带s_f₊₁的前k行中（k≥rτ₁），形成区域C。当k=rτ₁时，校验数据正好全部嵌入；当k＞rτ₁时，扩展子条带s_f₊₁的前k行存在空位，以0填充。依据嵌入过程，区域C中包含的k个数据块从上至下依次为（f₁（a_τ₊₁），···，f_r（a_τ₊₁），···，f₁（a_f），···，f_r（a_f），0，···，0）^T。

区域D的具体构造过程如下：

1）将子条带s_τ_-1的第i（2≤i≤r）个校验数据块嵌入至子条带s_τ的第i-1个校验数据块，子条带s_τ_-1第1个校验数据块嵌入至子条带s_τ的第r个校验数据块。同样的方法，完成子条带s_τ_-3对子条带s_τ_-2的嵌入。

2）如果τ为偶数，前τ个子条带按照1）中的方式完成嵌入；如果τ为奇数，第1个子条带不进行操作，剩余τ-1个子条带按照1）中的方式完成嵌入。区域D的通式表达式为

D = \{\begin{matrix} f_{1} (a_{1}) & \dots & f_{1} (a_{τ - 3}) & f_{1} (a_{τ - 2}) + f_{2} (a_{τ - 3}) & f_{1} (a_{τ - 1}) & f_{1} (a_{τ}) + f_{2} (a_{τ - 1}) \\ f_{2} (a_{1}) & \dots & f_{2} (a_{τ - 3}) & f_{2} (a_{τ - 2}) + f_{3} (a_{τ - 3}) & f_{2} (a_{τ - 1}) & f_{2} (a_{τ}) + f_{3} (a_{τ - 1}) \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ \\ f_{r} (a_{1}) & \dots & f_{r} (a_{τ - 3}) & f_{r} (a_{τ - 2}) + f_{1} (a_{τ - 3}) & f_{r} (a_{τ - 1}) & f_{r} (a_{τ}) + f_{1} (a_{τ - 1}) \end{matrix}\}

(4)

将区域A中的信息数据块均匀地嵌入至区域E、F。嵌入过程需满足同一节点的信息数据块不能嵌入至同一piggyback函数中的嵌入规则。嵌入完成后的区域E、F称为信息嵌入区域。具体嵌入过程如下：

1）令β_τ_（_i_-1）+_j=a_i_，_j（1≤i≤k，1≤j≤τ），将{β₁，···，β_kτ}按照从左至右、从上至下的顺序嵌入至子条带s_i（τ+1≤i≤f+1）的后r行组成的区域中。如果该区域嵌入已满，余下的数据从第1个位置重新嵌入，直至区域A中的信息数据块全部嵌入，每个位置的所有嵌入数据块之和为一个piggyback函数g_m_，_j（a₁，a₂，···，a_τ）。

2）令

t_{l 1} = ⌊k τ / r (τ_{1} + 1)⌋ ， t_{h 1} = ⌈k τ / r (τ_{1} + 1)⌉

，t₁=kτ-rt_l₁（τ₁+1）。依据嵌入规则，当t_h₁≠t_l₁时，可以确定信息嵌入区域piggyback函数中包含t_h₁个数据块的piggyback函数有t₁个。所以，按照从左至右、从上至下的顺序，第t₁+1个位置开始piggyback函数

g_{m ， j} (a_{1} ， a_{2} ， \dots ， a_{τ}) = \overset{t_{l 1} - 1}{\underset{i = 1}{Σ}} β_{i r (τ_{1} + 1) + t_{l 1} + 1}

，信息嵌入区域的通式表达式为

\begin{matrix} {E ∣ F} = \{\begin{array}{ccccc} f_{1} (a_{τ + 1}) + g_{1, τ + 1} (a_{1}, a_{2}, \dots, a_{τ}) & f_{1} (a_{τ + 2}) + g_{1, τ + 2} (a_{1}, a_{2}, \dots, a_{τ}) & \dots & f_{1} (a_{f}) + g_{1, f} (a_{1}, a_{2}, \dots, a_{τ}) & g_{1, f + 1} (a_{1}, a_{2}, \dots, a_{τ}) \\ f_{2} (a_{τ + 1}) + g_{2, τ + 1} (a_{1}, a_{2}, \dots, a_{τ}) & f_{2} (a_{τ + 2}) + g_{2, τ + 2} (a_{1}, a_{2}, \dots, a_{τ}) & \dots & f_{1} (a_{f}) + g_{2, f} (a_{1}, a_{2}, \dots, a_{τ}) & g_{2, f + 1} (a_{1}, a_{2}, \dots, a_{τ}) \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ \\ f_{r} (a_{τ + 1}) + g_{r, τ + 1} (a_{1}, a_{2}, \dots, a_{τ}) & f_{r} (a_{τ + 2}) + g_{r, τ + 2} (a_{1}, a_{2}, \dots, a_{τ}) & \dots & f_{1} (a_{f}) + g_{r, f} (a_{1}, a_{2}, \dots, a_{τ}) & g_{r, f + 1} (a_{1}, a_{2}, \dots, a_{τ}) \end{array}\} = \\ \{\begin{array}{ccccc} f_{1} (a_{τ + 1}) + \sum_{i = 0}^{t_{h 1} - 1} β_{i r (τ_{1} + 1) + 1} & f_{1} (a_{τ + 2}) + \sum_{i = 0}^{t_{h 1} - 1} β_{i r (τ_{1} + 1) + 2} & \dots & f_{1} (a_{f}) + \sum_{i = 0}^{t_{h 1} - 1} β_{i r (τ_{1} + 1) + τ_{1}} & \sum_{i = 0}^{t_{h 1} - 1} β_{i r (τ_{1} + 1) + τ_{1} + 1} \\ f_{2} (a_{τ + 1}) + \sum_{i = 0}^{t_{h 1} - 1} β_{i r (τ_{1} + 1) + τ_{1} + 2} & f_{2} (a_{τ + 2}) + \sum_{i = 0}^{t_{h 1} - 1} β_{i r (τ_{1} + 1) + τ_{1} + 3} & \dots & f_{1} (a_{f}) + \sum_{i = 0}^{t_{h 1} - 1} β_{i r (τ_{1} + 1) + 2 τ_{1} + 1} & \sum_{i = 0}^{t_{h 1} - 1} β_{i r (τ_{1} + 1) + 2 (τ_{1} + 1)} \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ \\ f_{r} (a_{τ + 1}) + \sum_{i = 0}^{t_{l 1} - 1} β_{i r (τ_{1} + 1) + (r - 1) (τ_{1} + 1) + 1} & f_{r} (a_{τ + 2}) + \sum_{i = 0}^{t_{l 1} - 1} β_{i r (τ_{1} + 1) + (r - 1) (τ_{1} + 1) + 2} & \dots & f_{1} (a_{f}) + \sum_{i = 0}^{t_{l 1} - 1} β_{i r (τ_{1} + 1) + r τ_{1} + r - 1} & \sum_{i = 0}^{t_{l 1} - 1} β_{i r (τ_{1} + 1) + r (τ_{1} + 1)} \end{array}\} \end{matrix}

(5)

定理本文构造的SAP满足（n，k）性质，即任意n-k个节点故障，均能从剩余的k个节点恢复原始数据。

证明依据具体构造过程，子条带s₁没有进行嵌入操作，保持MDS结构，所以子条带s₁满足（n，k）性质。τ为偶数时，子条带s₂中捎带的数据块为子条带s₁中的校验数据块，而子条带s₁的数据块均能恢复，所以进行一次异或操作，子条带s₂同样能恢复与s₁相同的结构，即子条带s₂满足（n，k）性质。以此类推，其他子条带也均满足（n，k）性质。而扩展子条带中的数据是校验数据的复制，在前面子条带恢复中均可得到，即对SAP整体（n，k）性质不影响。综上所述，SAP满足（n，k）性质。

2.3 构造实例

本节介绍（n，k，f）=（16，12，6）SAP的构造过程，其中子条带s₇为扩展子条带。首先，将区域A中的信息数据块a_u_，_v（1≤u≤12，1≤v≤3）按照从左至右、从上至下的顺序复制，形成piggyback函数；其次，采用同样的方式嵌入至区域E的校验数据块 f_m（a_v）（1≤m≤4，4≤v≤6）和扩展子条带s₇的后r行区域F中；最后，将区域E中的校验数据块f_m（a_v）（1≤m≤4，4≤v≤6）复制置于扩展子条带s₇的前k行区域C中，将区域D中的校验数据块进行循环移位嵌入，即将f_m（a₂）（1≤m≤4）等数据块错位嵌入至f_m（a₃）（1≤m≤4）等数据块中。（n，k，f）=（16，12，6）SAP的编码过程完成，编码结果如图3所示，区域E、F中piggyback函数具体展示见式（6）。

图3（n，k，f）=（16，12，6）SAP编码

Fig.3(n, k, f) = (16, 12, 6) SAP coding

\begin{matrix} {E ∣ F} = \{\begin{array}{llll} f_{1} (a_{4}) + \sum_{i = 0}^{2} β_{16 i + 1} & f_{1} (a_{5}) + \sum_{i = 0}^{2} β_{16 i + 2} & f_{1} (a_{6}) + \sum_{i = 0}^{2} β_{16 i + 3} & \sum_{i = 0}^{2} β_{16 i + 4} \\ f_{2} (a_{4}) + \sum_{i = 0}^{1} β_{16 i + 5} & f_{2} (a_{5}) + \sum_{i = 0}^{1} β_{16 i + 6} & f_{2} (a_{6}) + \sum_{i = 0}^{1} β_{16 i + 7} & \sum_{i = 0}^{1} β_{16 i + 8} \\ f_{3} (a_{4}) + \sum_{i = 0}^{1} β_{16 i + 9} & f_{3} (a_{5}) + \sum_{i = 0}^{1} β_{16 i + 10} & f_{3} (a_{6}) + \sum_{i = 0}^{1} β_{16 i + 11} & \sum_{i = 0}^{1} β_{16 i + 12} \\ f_{4} (a_{4}) + \sum_{i = 0}^{1} β_{16 i + 13} & f_{4} (a_{5}) + \sum_{i = 0}^{1} β_{16 i + 14} & f_{4} (a_{6}) + \sum_{i = 0}^{1} β_{16 i + 15} & \sum_{i = 0}^{1} β_{16 i + 16} \end{array}\} = \\ \{\begin{array}{cccc} f_{1} (a_{4}) + a_{1, 1} + a_{6, 2} + a_{11, 3} & f_{1} (a_{5}) + a_{1, 2} + a_{6, 3} + a_{12, 1} & f_{1} (a_{6}) + a_{1, 3} + a_{7, 1} + a_{12, 2} & a_{2, 1} + a_{7, 2} + a_{12, 3} \\ f_{2} (a_{4}) + a_{2, 2} + a_{7, 3} & f_{2} (a_{5}) + a_{2, 3} + a_{8, 1} & f_{2} (a_{6}) + a_{3, 1} + a_{8, 2} & a_{3, 2} + a_{8, 3} \\ f_{3} (a_{4}) + a_{3, 3} + a_{9, 1} & f_{3} (a_{5}) + a_{4, 1} + a_{9, 2} & f_{3} (a_{6}) + a_{4, 2} + a_{9, 3} & a_{4, 3} + a_{10, 1} \\ f_{4} (a_{4}) + a_{5, 1} + a_{10, 2} & f_{4} (a_{5}) + a_{5, 2} + a_{10, 3} & f_{4} (a_{6}) + a_{5, 3} + a_{11, 1} & a_{6, 1} + a_{11, 2} \end{array}\} \end{matrix}

(6)

由图3和式（6）可以看出，区域A中丢失的信息数据块利用区域E和F中的piggybacking块进行修复，区域B中丢失的信息数据块则利用MDS码译码修复，区域C中丢失的校验数据块在进行区域B中丢失信息数据块修复的同时重新编码修复。假设节点1发生故障，a_1，4通过下载a_2，4，···，a_12，4和f₂（a₄）利用MDS码译码修复。a_1，5、a_1，6与a_1，4的修复方式相同。a_1，1、a_1，2和a_1，3分别被嵌入至子条带s₄、s₅和s₆的第1个校验数据块上，下载相应的piggybacking块和其中未丢失的数据块进行恢复。扩展子条带丢失的f₁（a₄）利用已经恢复的a_1，4和恢复a_1，4时下载的a_2，4，···，a_12，4重新编码修复。节点1修复完成，共计下载45个数据块，连接12个节点。

区域D校验节点中丢失的嵌入数据块可利用piggybacking块修复，没有嵌入的丢失校验数据块则进行MDS码重新编码修复。区域E和F中的丢失数据块直接在区域A和C中下载，即可完成修复。假设节点13发生故障，利用MDS码编码得到数据块f₁（a₁）、f₁（a₃）和f₄（a₃）。然后，在节点14下载数据块f₂（a₂）并与数据块f₁（a₃）进行异或操作，以恢复丢失数据块f₁（a₃）+f₂（a₂）。同理，通过在节点16下载数据块f₄（a₃）+f₁（a₂）并与数据块f₄（a₃）进行异或操作，以恢复f₁（a₂）。其他丢失数据块在区域A和C中下载原始数据块进行异或操作以恢复。完成节点13的修复，共计下载33个数据块，连接14个节点。其他单节点故障的修复与上述描述相似。最后，依据式（1）~（3）得出γ^sys=0.597、γ^par=0.444、γ^all=0.559、η^sys=1.042、η^par=1.167、η^all=1.073。

若图3中有多个节点同时发生故障，假设其中多个故障节点中包含一个或多个信息节点时，均需利用MDS码译码恢复故障节点信息，没有其他快速修复算法，共计需下载72个数据块。当多个故障节点均为校验节点时，可利用快速修复方法，只需要下载子条带s_i（1≤i≤3）中所有信息数据块和在扩展子条带s₇中下载失效的校验数据块即可完成修复。例如，当两个校验节点13和14同时发生故障，下载42个数据块即可完成修复。

3 修复分析

3.1 信息节点平均修复带宽率和平均修复度率

对于单信息节点故障，丢失的数据块存在3种不同情况，分别对应数据块位于区域A、B和C。由上述SAP框架结构及构造实例中信息节点修复过程分析可知：区域A中丢失数据块可利用信息嵌入区域的piggybacking块进行修复，k个信息节点共计需下载t₁

t_{h 1}^{2}

+（r（τ₁+1）-t₁）

t_{l 1}^{2}

个数据块；区域B中丢失的数据块可利用MDS码译码修复，需下载kτ₁个数据块；区域C中丢失的数据块，在区域B进行MDS码译码的同时可进行重新编码修复。所以，信息节点平均修复带宽率为

γ^{s y s} = \frac{k^{2} τ_{1} + t_{1} t_{h 1}^{2} + (r (τ_{1} + 1) - t_{1}) t_{l 1}^{2}}{k^{2} f}

(7)

推论1 对于单节点故障，当τ=τ₁时，信息节点最小平均修复带宽率

m i n γ_{τ = τ_{1}}^{s y s}

=1/2+1/（4r）；当τ≠τ₁时，信息节点最小平均修复带宽率

m i n γ_{τ \neq τ_{1}}^{s y s}

=（r+2）/（3r）。

证明信息节点平均修复带宽率

γ^{sys} = \frac{k^{2} τ_{1} + t_{1} t_{h 1}^{2} + (r (τ_{1} + 1) - t_{1}) t_{l 1}^{2}}{k^{2} f}

，当τ=τ₁，即f=2τ₁时，

γ_{τ = τ_{1}}^{s y s} = \frac{k^{2} τ_{1} + t_{1} t_{h 1}^{2} + (r (τ_{1} + 1) - t_{1}) t_{l 1}^{2}}{k^{2} \times 2 τ_{1}} ⩾ \frac{k^{2} τ_{1} + {(k τ_{1})}^{2} / (r (τ_{1} + 1))}{k^{2} \times 2 τ_{1}} = 1 / 2 + τ_{1} / (2 r (τ_{1} + 1))

(8)

对1/2+τ₁/（2r（τ₁+1））中τ₁求偏导可知，1/2+τ₁/（2r（τ₁+1））随τ₁的减小而减小，所以当τ₁=1时，

m i n γ_{τ = τ_{1}}^{s y s}

=1/2+1/（4r）。

同理，当τ≠τ₁时，

m i n γ_{τ \neq τ_{1}}^{s y s}

=（r+2）/（3r）。

修复故障节点区域B、C中丢失的数据块共计需连接k-1个节点。对于修复区域A中丢失的数据块，如果区域A中同一行丢失的数据块嵌入至信息嵌入区域的同一行时，需要额外连接1个节点；如果不在同一行时，则需要额外连接2个节点。所以当τ≠τ₁即τ=τ₁+1时，

η_{τ \neq τ_{1}}^{s y s}

；当τ=τ₁时，令

t_{l 3} = ⌊\frac{k}{τ_{1} + 1}⌋ ， t_{3} = k - t_{l 3} (τ_{1} + 1)

。当t₃=0时，修复区域A中k个信息节点共需额外连接2τ₁t_l₃个节点；当t₃≠0时，修复区域A中k个信息节点共需额外连接2τ₁t_l₃+2t₃-1个节点。所以，信息节点平均修复度率为

η^{sys} = \{\begin{matrix} \frac{k (k - 1) + 2 τ_{1} t_{l 3}}{k^{2}}, τ = τ_{1} 且 t_{3} = 0 \\ \frac{k (k - 1) + 2 τ_{1} t_{l 3} + 2 t_{3} - 1}{k^{2}}, τ = τ_{1} 且 t_{3} \neq 0 \\ 1, τ \neq τ_{1} \end{matrix}

(9)

3.2 校验节点平均修复带宽率和平均修复度率

对于单校验节点故障，丢失的数据块也存在3种不同情况，分别对应数据块位于区域D、E和F。区域E中丢失的校验数据块，直接在区域C中下载即可修复，r个校验节点共计需下载rτ₁个数据块；当τ为奇数，下载奇数子条带的所有信息数据块和嵌入的校验数据块即可修复区域D中丢失的数据块，r个校验节点共计需下载r（k（τ+1）/2+τ-1）个数据块。下载区域A中尚未下载的信息数据块即可修复区域E和F中丢失的数据块，r个校验节点共计需下载k（τ-1）/2个数据块；当τ为偶数，修复方式类似。所以，校验节点平均修复带宽率为

γ^{p a r} = \{\begin{matrix} \frac{r (k (\frac{τ + 1}{2}) + τ - 1 + τ_{1}) + \frac{k (τ - 1)}{2}}{r k f}, τ 为 奇 数 \\ \frac{r (k \frac{τ}{2} + τ + τ_{1}) + \frac{k τ}{2}}{r k f}, τ 为 偶 数 \end{matrix}

(10)

推论2 单节点故障时，校验节点最小平均修复带宽率min γ^par=1/4+1/（4r）。

证明 τ为奇数时，校验节点平均修复带宽率

γ^{par} = \frac{r (k (\frac{τ + 1}{2}) + τ - 1 + τ_{1}) + \frac{k （ τ - 1 ）}{2}}{r k f}

。当τ=τ₁即f=2τ₁时，有

\frac{\partial (γ^{p a r})}{\partial τ_{1}} = \frac{k k r (1 - r)}{{(r k \times 2 τ_{1})}^{2}} < 0

(11)

所以，γ^par随着τ₁的增大而减小。SAP构造是以k≥rτ₁为前提的，所以，当τ₁趋向无穷时，k也应趋向无穷，有

m i n γ^{p a r} = \underset{τ_{1} \to \infty ， k \to \infty}{l i m} γ^{p a r} = 1 / 4 + 1 / （ 4 r ）

。其他情况证明类似，不再阐述。

同时，由上述校验节点故障修复过程可推出校验节点平均修复度率η^par=（k+2）/k。

假设t（2≤t≤r）个校验节点同时故障，子条带s_i（1≤i≤τ）中丢失的校验数据块需利用MDS码重新编码修复，共需下载kτ个数据块。而子条带s_i（τ+1≤i≤f）丢失的校验数据块，在扩展子条带s_f₊₁中直接下载即可，共计需下载tτ₁个校验数据块。其他嵌入数据块，在进行前两步修复的同时已经进行下载。所以，t个校验节点同时故障时，校验节点的平均修复带宽率γ^par_t=（kτ+tτ₁）/（kf）。

4 性能分析

为了探究SAP的性能，将SAP与现有piggybacking编码RSR-I、RSR-II和OOP分别从存储开销、修复带宽开销和修复度率3个维度进行对比。

4.1 存储开销

在piggybacking编码RSR-I、RSR-II和OOP中，系统会将大小为M的原始文件分割成k份，每份长度为f，此时节点存储开销α₁=M/k。本文构造的SAP扩展了1个子条带，所以每份长度为f+1，则节点存储开销α₂=（f+1）M/（kf）。因此，与piggybacking编码RSR-I、RSR-II和OOP相比，本文构造的SAP节点存储开销增加率为1/f。图4为节点存储开销增加率随子条带数f的变化曲线。由图4可知，节点存储开销增加率随f的变化呈指数递减，当f趋向无穷大时，节点存储开销的增加可以忽略不计。

4.2 修复带宽开销

从信息节点平均修复带宽率γ^sys、校验节点平均修复带宽率γ^par、节点总的平均修复带宽率γ^all以及多校验节点故障修复带宽率γ^part方面，将本文构造的SAP与RSR-I、RSR-II和OOP进行比较。

图5为修复带宽率对比曲线。其中，RSR-I、OOP的子条带数f=6，RSR-II的子条带数f=2（2r-3）。由于本文构造的SAP分f为奇数和偶数两种情况，同时，为了保证对比的准确性，SAP子条带数的选择与对比编码相近，分别取f=6和f=7。由图5（a）可以看出，SAP的 γ^sys曲线整体位于其他piggybacking编码的下方。当f=7时，无论编码参数取何值，γ^sys均小于对比的piggybacking编码。但当f=6时，在n=20、k=15等参数下，会出现SAP的γ^sys大于OOP或RSR-II的情况，主要原因是当r=5时，

\sqrt{r - 1}

为整数，达到OOP信息节点平均修复带宽率的最优条件。并且，随着r的增大，RSR-II子条带数增大，使其对校验节点的嵌入更加高效，从而导致上述情况出现。由图5（b）可以明显看出，SAP的γ^par优于其他piggybacking编码，说明SAP达到了减少校验节点修复带宽开销的目的。由图5（c）看出， γ^all也优于其他piggybacking编码，说明SAP具有较低的修复带宽开销。

图4存储开销增加率随f的变化曲线

Fig.4Curve of storage overhead increase rate with f

图6为最小平均修复带宽率随校验节点数r的变化曲线。可以看出，piggybacking编码的最小平均修复带宽率均随r的增大而减小。这是因为校验节点r越大，piggyback函数中包含的数据块越少，修复故障节点时下载的数据块就越少。由图6（a）可以发现：在r的取值范围内，当τ≠τ₁时，SAP的min γ^sys曲线一直处于其他piggybacking编码曲线的下方；但当τ=τ₁时，从r=5开始，SAP的min γ^sys大于OOP码。这是因为从r=5开始，

\sqrt{r - 1}

/（r-1）≤1/2，即OOP的MDS码译码的子条带数少于总子条带数的一半，当τ=τ₁时，SAP需要进行的MDS码译码的子条带数正好等于总子条带数的一半，即从r=5开始出现SAP的min γ^sys大于OOP的情况。图6（b）中，SAP的min γ^par一直低于其他piggybacking编码的min γ^par。

图5修复带宽率对比曲线

Fig.5Comparison curve of repair bandwidth rate

图6最小平均修复带宽率对比曲线

Fig.6Comparison curve of minimum average repair bandwidth rate

t（2≤t≤r）表示SAP中校验节点同时发生故障的个数。piggybacking编码RSR-I、RSR-II和OOP均通过下载所有信息数据块重新编码进行恢复，修复带宽率为1^[10]，SAP只需下载子条带s_i（1≤i≤τ）的所有信息数据块进行重新编码修复，其他丢失校验数据块可在扩展子条带s_f₊₁中直接下载即可完成快速修复。图7为不同piggybacking编码在f=7时，多校验节点故障的修复带宽率对比曲线。可以看出：SAP中多校验节点故障的修复带宽率随着故障节点数目t的增大而增大，随着信息节点数目k的增大而减小；相比于其他的 piggybacking编码，SAP在多校验节点故障时显著地降低了修复带宽率，以t=2时降低的修复带宽开销最大。

图7多校验节点故障修复带宽率对比曲线

Fig.7Comparison curve of repair bandwidth rates for multiple parity node failures

4.3 修复度率

表1为RSR-II、OOP和SAP关于子条带数、平均修复度率及最小平均修复带宽率的对比。由表1可以发现，RSR-II和OOP的子条带数受校验节点数r的影响，而SAP的子条带数可自由选取，所以SAP的子条带数选取更加灵活，且少于RSR-II和OOP的子条带数量。图8为SAP与RSR-II和OOP平均修复度率对比曲线。由表1中η^sys公式和图8（a）对比可以发现，RSR-II和OOP的η^sys随k的增大呈递减趋势，随r的增大呈递增趋势；而SAP的η^sys不受r的影响且小于现有的piggybacking编码，所以，当k保持不变，随r的增大，SAP的η^sys将更加低于RSR-II和OOP的η^sys。由图8（b）可以看出，在r=2和r=3时，RSR-II和OOP的η^par小于SAP的η^par。原因是当RSR-II和OOP的第1个校验节点故障时，只能利用MDS编码恢复，需要下载全部的信息数据块。此情况下连接的节点数较少，所以在校验节点r较小时，出现了平均修复度率较低的情况。但随r的增大，修复度率也出现上升趋势。例如，在k相同时，从r=4开始，SAP的η^par低于RSR-II和OOP。

表1piggybacking编码对比

Tab.1Comparison of piggybacking coding

图8平均修复度率对比曲线

Fig.8Comparison curve of average repair degree rate

5 结论

1）SAP编码扩展了一个子条带，尽管增加了节点存储开销，但节点存储开销增加率随子条带数的增加呈指数递减趋势。因此，存储开销的增加可以忽略不计。

2）在信息节点平均修复带宽率方面，SAP编码整体低于RSR-I、RSR-II和OOP。同时，SAP编码在校验节点平均修复带宽率和节点总的平均修复带宽率方面显著优于RSR-I、RSR-II和OOP，显示出其在整体修复带宽开销方面的优势。SAP编码显著降低了多校验节点故障修复带宽率，特别是在校验节点故障数t=2的情况下，SAP编码的修复带宽开销降幅最大。

3）SAP编码信息节点修复度率始终低于RSR-II和OOP。然而，在校验节点数r=2和r=3时，SAP编码的校验节点修复度率高于RSR-II和OOP。但随着校验节点数的增加，这一趋势发生逆转，SAP编码的校验节点修复度率也低于RSR-II和OOP。

4）SAP编码在修复带宽开销和修复度率方面均优于RSR-II和OOP，特别是在多校验节点故障情况下表现尤为显著。通过扩展子条带，SAP编码克服了RSR-II和OOP的不足，具有重要的理论意义和应用价值。

图1Piggybacking框架

Fig.1Piggybacking framework

下载: 全尺寸图片

图2SAP框架结构

Fig.2SAP framework structure

下载: 全尺寸图片

图3（n，k，f）=（16，12，6）SAP编码

Fig.3(n, k, f) = (16, 12, 6) SAP coding

下载: 全尺寸图片

图4存储开销增加率随f的变化曲线

Fig.4Curve of storage overhead increase rate with f

下载: 全尺寸图片

图5修复带宽率对比曲线

Fig.5Comparison curve of repair bandwidth rate

下载: 全尺寸图片

图6最小平均修复带宽率对比曲线

Fig.6Comparison curve of minimum average repair bandwidth rate

下载: 全尺寸图片

图7多校验节点故障修复带宽率对比曲线

Fig.7Comparison curve of repair bandwidth rates for multiple parity node failures

下载: 全尺寸图片

图8平均修复度率对比曲线

Fig.8Comparison curve of average repair degree rate

下载: 全尺寸图片

表1piggybacking编码对比

Tab.1Comparison of piggybacking coding

下载: 全尺寸图片

图1Piggybacking框架

Fig.1Piggybacking framework

图2SAP框架结构

Fig.2SAP framework structure

图3（n，k，f）=（16，12，6）SAP编码

Fig.3(n, k, f) = (16, 12, 6) SAP coding

图4存储开销增加率随f的变化曲线

Fig.4Curve of storage overhead increase rate with f

图5修复带宽率对比曲线

Fig.5Comparison curve of repair bandwidth rate

图6最小平均修复带宽率对比曲线

Fig.6Comparison curve of minimum average repair bandwidth rate

图7多校验节点故障修复带宽率对比曲线

Fig.7Comparison curve of repair bandwidth rates for multiple parity node failures

图8平均修复度率对比曲线

Fig.8Comparison curve of average repair degree rate

表1piggybacking编码对比

Tab.1Comparison of piggybacking coding

图1Piggybacking框架

Fig.1Piggybacking framework

图2SAP框架结构

Fig.2SAP framework structure

图3（n，k，f）=（16，12，6）SAP编码

Fig.3(n, k, f) = (16, 12, 6) SAP coding

图4存储开销增加率随f的变化曲线

Fig.4Curve of storage overhead increase rate with f

图5修复带宽率对比曲线

Fig.5Comparison curve of repair bandwidth rate

图6最小平均修复带宽率对比曲线

Fig.6Comparison curve of minimum average repair bandwidth rate

图7多校验节点故障修复带宽率对比曲线

Fig.7Comparison curve of repair bandwidth rates for multiple parity node failures

图8平均修复度率对比曲线

Fig.8Comparison curve of average repair degree rate

表1piggybacking编码对比

Tab.1Comparison of piggybacking coding

SIDDIQA A, KARIM A, GANI A. Big data storage technologies:a survey[J]. Frontiers of Information Technology and Electronic Engineering,2017,18(8):1040. DOI:10.1631/FITEE.1500441

BLINOVA O, KUPRIKOV O, FARKHADOV M. Analysis of frameworks and technologies for solving big data storage and processing problems in distributed systems[C]//2023 IEEE International Conference on Information, Control,and Communication Technologies(ICCT). Astrakhan: IEEE,2023:1. DOI:10.1109/ICCT58878.2023.10347069

YAVARI E, ESMAEILI M. Locally repairable codes:joint sequential-parallel repair for multiple node failures[J]. IEEE Transactions on Information Theory,2020,66(1):222. DOI:10.1109/TIT.2019.2940975

LI Jun, LI Baochun. Demand-aware erasure coding for distributed storage systems[J]. IEEE Transactions on Cloud Computing,2021,9(2):532. DOI:10.1109/TTC.2018.2885306

PAPAILIOPOULOS D S, DIMAKIS A G, CADAMBE V R. Repair optimal erasure codes through Hadamard designs[C]//49th Annual Allerton Conference on Communication, Control,and Computing, Allerton 2011. Monticello: IEEE,2011:1382. DOI:10.1109/Allerton.2011.6120328

DIMAKIS A G, GODFREY P B, WU Y,et al. Network coding for distributed storage systems[J]. IEEE Transactions on Information Theory,2010,56(9):4539. DOI:10.1109/TIT.2010.2054295

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(ISIT). Istanbul: IEEE,2013:331. DOI:10.1109/ISIT.2013.6620242

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. DOI:10.1109/TIT.2017.2715043

YUAN Shuai, HUANG Qin, WANG Zulin. A repair-efficient coding for distributed storage systems under piggybacking framework[J]. IEEE Transactions on Communications,2018,66(8):3245. DOI:10.1109/TCOMM.2018.2805347

LI Guiyang, LIN Xing, TANG Xiaohu. An efficient one-to-one piggybacking design for distributed storage systems[J]. IEEE Transactions on Communications,2019,67(12):8193. DOI:10.1109/TCOMM.2019.2941933

周悦, 李贵洋, 韩鸿宇, 等. 一种均衡分配的修复校验节点的Piggybacks捎带设计[J]. 电子学报,2021,49(4):812.ZHOU Yue, LI Guiyang, HAN Hongyu,et al. A balanced-allocation Piggybacks adding design for repairing parity nodes[J]. Acta Electronica Sinica,2021,49(4):812. DOI:10.12263/DZXB.20200056

张璐. 分布式存储系统中piggybacking框架的设计[D]. 西安: 西安电子科技大学,2021.ZHANG Lu. Design of piggybacking framework in distributed storage system[D]. Xi′an: Xidian University,2021. DOI:10.27389/d.cnki.gxadu.2021.001745

SUN Rong, LI Xin, ZHANG Lu,et al. Distributed storage codes based on double-layered piggybacking framework[J]. IEEE Access,2020,8:150447. DOI:10.1109/ACCESS.2020.3002824

SUN Rong, ZHANG Lu, LIU Jingwei. A new piggybacking design with low-repair bandwidth and complexity[J]. IEEE Communications Letters,2021,25(7):2099. DOI:10.1109/LCOMM.2021.3071855

JIANG Zhengyi, HOU Hanxu, HAN Yunxiang,et al. An efficient piggybacking design with lower repair bandwidth and lower sub-packetization[C]//2021 IEEE International Symposium on Information Theory(ISIT). Melbourne: IEEE,2021:2328. DOI:10.1109/ISIT45174.2021.9518037

SHI Hao, HOU Hanxu, HAN Yunxiang,et al. New piggybacking codes with lower repair bandwidth for any single-node failure[C]//2022 IEEE International Symposium on Information Theory(ISIT). Espoo: IEEE,2022:2601. DOI:10.1109/ISIT50566.2022.9834881

Publication Statement

Journal Subscription

1 piggybacking框架

2 扩展子条带的piggybacking编码构造

3 修复分析

4 性能分析

5 结论