Construction of locally piggybacking codes with lower repair bandwidth overhead

随着云计算的发展，数据海量化已经成为一种趋势^[1]，分布式存储系统因其在数据存储方面的可靠性和高效性，近年来已经被各大互联网公司广泛使用^[2]。然而，随着系统存储规模的增大，存储节点故障导致的数据失效越来越常见。在此背景下如何提高分布式存储系统的可靠性，采用性能更好的容错技术成为目前的研究热点。大部分容错技术都是通过增加冗余数据来提高系统的可靠性，产生冗余的方式最常见的有“复制”和“纠删码”策略^[3-5]。复制即存储数据的多个副本，最常见的为三副本复制，存储开销较大。相比于复制，纠删码策略有效降低了存储开销，但由于其（n, k）性质，发生节点故障时，需下载原文件大小的数据量，修复带宽开销过大。为了降低故障节点的修复带宽开销，寻找数据节点存储开销和修复带宽开销的最优权衡，2010年文献[6]使用信息流图将网络编码引入到分布式存储系统中，提出了节点存储开销与修复带宽开销的最优权衡曲线，进而提出最小存储再生（minimum storage regenerating, MSR）码和最小带宽再生（minimum bandwidth regenerating, MBR）码。相比纠删码，再生码能够有效降低故障节点的修复带宽，但对于MSR码来说，高码率意味着指数级的子条带数，计算复杂度较高。

针对上述问题，构造能对故障节点进行精确修复、高码率、低复杂度、低修复带宽开销的存储编码成为了研究热点。2013年，文献[7]首次提出了Piggybacking码，并于2017对其进行了进一步完善，其编码满足RBT （repair-by-transfer）属性^[8-9]，即修复故障节点期间下载的数据量与读取的数据量相同，同时能实现数据的精确修复。文献[10]提出一种可以高效修复信息节点的Piggybacking码，即REPB （repair efficient, piggybacking）码，信息节点的平均修复带宽率最低可达到${2 \mathord{\left/ {\vphantom {2 {(\sqrt r + 1)}}} \right. } {(\sqrt r + 1)}}$，但是子条带数不确定。文献[11]通过对信息节点进行分组，构造了一种子条带数等于奇偶校验节点数的Piggybacking码（shangguan piggybacking, SPB） ，降低了修复带宽开销。但是上述REPB和SPB都只能对信息节点进行高效修复。

2019年，文献[12-13]提出一种“one-to-one”的Piggybacking码（one-to-one pigggybacking, OOP），在进一步降低信息节点修复带宽的同时，考虑了奇偶校验节点的有效修复，但OOP只使用一个子条带对校验节点进行辅助修复，所以校验节点的修复性能依旧不佳。文献[1]构造的RSR-I*、RSR-II*和文献[10]构造的REPB*通过对子条带进行整合，将前一个子条带中校验节点的数据块捎带到后一个子条带的校验节点中，虽然提高了校验节点的修复性能，但导致子条带数目成倍增长，影响到系统的I/O性能。2020年，文献[14-15]通过牺牲容错能力，将信息节点和校验节点进行分层修复，提出双层Piggybacking （double-layered piggybacking, DPB）编码，但其对故障节点的修复度没有改善。2022年，文献[16]将子条带数与校验节点数设为相等值，以此为基础，利用OOP未充分利用到的校验节点进行捎带，进一步降低了修复带宽开销。

针对目前Piggybacking码存在的局限性，本文在Piggybacking框架中加入2个局部校验子条带，构造了一种具有较低修复带宽开销的局部Piggybacking码。所构造的局部Piggybacking码保留了MDS码的优点，加入局部特性，使得故障节点的修复带宽开销更小，同时构造Piggyback函数捎带对应的信息节点数据块，在保证其MDS容错性的同时提出了一种多节点故障的快速修复算法。与现有的Piggybacking码相比，本文构造的局部Piggybacking码在降低信息节点修复带宽开销和修复度的同时降低了校验节点的修复带宽开销，且可以实现双信息节点的快速修复。

1.   基础知识

1.1   Piggybacking框架

Piggybacking框架是一种在现有码的基础上，以现有码为基础码，将部分子条带的数据块经过Piggyback函数形成Piggyback块，之后将Piggyback块嵌入，以设计具有高码率、低子条带数、低修复带宽开销的Piggybacking码。基于存储效率、计算复杂度等多方面考虑，现有的Piggybacking码通常选取MDS码为基础码，同时为了保证其MDS属性，在捎带时只选取子条带之前的数据块形成Piggyback函数。图1为采用MDS码为基础码的Piggybacking框架中校验节点结构，其中，${{\boldsymbol{a}}_i}\left( {1 \leqslant i \leqslant \alpha } \right)$代表第i个子条带上存储的信息数据块，${\boldsymbol{P}}_j^{\text{T}}{{\boldsymbol{a}}_i}\left( {1 \leqslant j \leqslant r} \right)$为校验数据块，${g_{i,j}}({{\boldsymbol{a}}_1},{{\boldsymbol{a}}_2}, \cdots ,{{\boldsymbol{a}}_{i - 1}}) (i \ne 1)$为捎带的Piggyback函数。

DownLoad: Full-Size Img PowerPoint

当出现故障节点时，通过MDS码译码以及其中嵌入的Piggyback块进行修复即可。这一修复方式通过将部分MDS译码替换为Piggyback块译码减少了修复带宽开销。具体的衡量指标包括信息节点平均修复带宽率$\gamma _{}^{{\text{sys}}}$，校验节点平均修复带宽率$\gamma _{}^{{\text{par}}}$，信息节点平均修复度率${\Im ^{{\text{sys}}}}$以及校验节点平均修复度率${\Im ^{{\text{par}}}}$。定义${B_i}$为节点$i$故障时需要下载的数据块数目，定义${\eta _i}$为节点$i$故障时需要连接的节点数目，通用公式表示如下：

1.2   RSR-II码

RSR-II码以MDS码为基本码^[9]，其中信息节点的个数k可以取任意值，校验节点的个数$r \geqslant 3$，子条带的个数$\alpha {\text{ = }}2r - 3$，${\boldsymbol{P}}_i^{\text{T}}{{\boldsymbol{a}}_n},\; 1 \leqslant n \leqslant \alpha$为校验数据块，由k个信息数据块进行MDS编码生成。RSR-II码的基本思想为将前$(r - 1)$个子条带中信息节点的数据块捎带到后$(r - 1)$个子条带校验节点的数据块中，其中${{\boldsymbol{q}}_{i,j}}$,${{\boldsymbol{v}}_i}$和${{\boldsymbol{\hat v}}_i},\;\left( {2 \leqslant i \leqslant r,1 \leqslant j \leqslant r - 1} \right)$共同构成其Piggyback函数，且$\displaystyle\sum\limits_{j = 1}^{r - 1} {{{\boldsymbol{q}}_{i,j}}} = {{\boldsymbol{P}}_i},\forall i \in \{ 2, 3, \cdots r \}$，校验节点$i{\text{ }}(2 \leqslant i \leqslant r)$的存储情况如图2a所示。将所有信息节点的前$(r - 1)$个子条带中的数据块分为大小相等的集合，分别形成Piggyback函数，捎带到校验节点$i{\text{ }}(2 \leqslant i \leqslant r)$的后$(r - 1)$个子条带中，同时满足每个子条带只能捎带之前子条带中的数据块，以保证MDS属性。在后$(r - 1)$个校验节点中进行线性变换，用第$(r - 1)$个子条带的数据块减去最后$(r - 2)$个子条带中的数据块，得到如图2b所示的RSR-II编码结构。

DownLoad: Full-Size Img PowerPoint

2.   局部Piggybacking码的构造

2.1   具有较低修复带宽开销局部Piggybacking码的一般结构

图3为局部Piggybacking码的一般结构图，包括区域A、B、C共3个区域，其中区域A为信息数据块区域，区域B为全局校验块区域，区域C为局部检验块区域。将区域A中的数据块通过Piggyback函数形成Piggyback块，嵌入到区域B，区域C由区域A和区域B中的数据块通过分组生成局部校验块。设${a_{m,n}}\left( {1 \leqslant m \leqslant k,1 \leqslant n \leqslant \alpha } \right)$代表第m个节点的第n个子条带中存储的数据块，${{\boldsymbol{a}}_h}{\text{ = }}({a_{1,h}},{a_{2,h}}, \cdots ,{a_{k,h}})^{\mathrm{T}}$，${1 \leqslant h \leqslant 2r - 1}$为子条带h中存储的信息数据块，${{\boldsymbol{P}}}_{1},{{\boldsymbol{P}}}_{2},\cdots ,{{\boldsymbol{P}}}_{r}$表示r个长度为k的MDS编码向量。局部Piggybacking码的总条带数$\alpha = 2r - 1,r \geqslant 3$，其具体编码步骤如下：1）预留两个空闲子条带作为局部校验条带，即第r-1个和第2r−1个子条带。将信息节点的前r−2个子条带和第r+1到第2r−2个子条带分为两个局部组，生成局部校验块，分别存储在第r−1和第2r−1个子条带中。将第r个子条带的信息符号分为2部分，第1部分为前$\left\lceil {{k/2}} \right\rceil$个信息节点，第2部分为其余信息节点，分别生成局部校验块存放在第1个校验节点的第r−1个子条带和第2r−1个子条带，即图3中${x_1}$和${x_2}$所在位置。2）将信息节点的2个局部组以及对应的局部校验条带内的数据块进行循环错位放置，之后将前r−2个子条带中的信息数据块按照捎带规则捎带到后r−1个校验节点的第r到第2r−2个子条带中。3）具体捎带规则如下。

1） 将信息节点分为t+1个不相交的集合${A_x}$，前t个集合的大小为r-1，第t+1个集合的大小为$k - t\left( {r - 1} \right)$，即：

2） 定义长度为k的向量$\left\{ {{{\boldsymbol{q}}_{j,h}}} \right\}_{j = 1,h = 1}^{r - 2,r - 2}$和$\left\{ {{{\boldsymbol{g}}_{j,h}}} \right\}_{j = r - 1,h = 1}^{r - 1,r - 2}$，其中j代表集合${A_x}$中第j个信息节点，h代表第h个子条带。

3） 定义Piggyback函数$f_{j,h}^{} = {{\boldsymbol{q}}^{\text{T}}_{j,h}}{{\boldsymbol{a}}_h} = \displaystyle\sum\limits_{x = 1}^{t + 1} {{a_{\left( {x - 1} \right)\left( {r - 1} \right) + j + h - 1,h}}}$$(1 \leqslant j,h \leqslant r - 2)$，将$f_{j,h}^{}$附加到第j+2个校验节点的第h+r个子条带。令Piggyback函数$f_h^{} = {{\boldsymbol{g}}^{\text{T}}_{j,h}}{{\boldsymbol{a}}_h} = \displaystyle\sum\limits_{x = 1}^{t + 1} {{a_{\left( {x - 1} \right)\left( {r - 1} \right) + j + h - 1,h}}}$，将$f_h^{}$附加到第h+2个校验节点的第r个子条带。

4） 最后将除第1个以外校验节点的前r−2个子条带和第r+1到第2r−2个子条带分别作为1个局部组，生成局部校验块，局部组内部整体进行错位放置。

DownLoad: Full-Size Img PowerPoint

图3为具有较低修复带宽开销的局部Piggybacking码的一般性结构图。以（15, 10）MDS码作为基本码，子条带数目$\alpha = 2r - 1 = 9$为例。将信息节点和校验节点分为3个区域，进行编码生成局部校验块，按照上述捎带规则在多个区域间对信息符号进行捎带。具体操作如下：首先，将信息节点除预留条带外的前3个条带和后3个条带作为两个局部组，将信息符号按行生成局部校验块，存入预留的2个局部校验条带中。将第5个条带的信息符号分为两部分，分别生成局部校验块存入${x_1}$和${x_2}$所在位置。其次，将2个局部组和对应的局部校验条带内的所有数据块进行循环错位放置，之后将10个信息节点分为3组，分别为{1,2,3,4}，{5,6,7,8}，{9,10}。将第1,2,3条带与第6,7,8条带一一对应。将每组的第1个节点的信息符号捎带到第3个校验节点中，依次向剩余节点中捎带信息符号，然后将每组的第4个信息节点的信息符号捎带到后3个校验节点的第5个子条带中。最后，将第2,3,4,5个校验节点中1,2,3条带及6,7,8条带分为2个局部校验组生成局部校验块，存入剩余空闲子条带中，再将2个局部校验组内所有数据块及生成的局部校验块进行循环错位放置。最终构造如图4所示。

以下是该局部Piggybacking码的故障节点修复过程：1）单信息节点故障：若节点1发生故障，除第$r$个子条带之外的信息块可通过连接节点2,3,4,8,9,10,11，从这些节点中读取并下载下标相同的数据块，共24个数据块进行修复。第$r$个子条带的信息块${d_1}$可通过下载数据块${d_2}$,${d_3}$,${d_4}$,${d_5}$,${x_1}$进行修复，并额外连接了节点5和11。节点1的修复一共下载29个数据块，连接8个节点。2）单校验节点故障：若节点14发生故障，前4个数据块和后4个数据块通过连接节点12,13,14下载24个数据块进行修复，第5个数据块通过下载第$r$个子条带的所有信息数据块以及被嵌入到该故障节点的第5个数据块中Piggyback块所涉及的数据块共12个数据块进行修复。修复过程中共连接14个节点。3）多节点故障：若节点1,3同时故障，因节点1和3在一个局部组中存在2个下标相同的数据块，所以先下载第5,6,7个子条带中未失效的信息数据块和未嵌入Piggyback块的校验数据块，之后通过节点13中第6和第7个子条带的Piggyback块修复部分失效数据块，其余数据块利用局部校验条带进行修复。

DownLoad: Full-Size Img PowerPoint

2.2   特殊结构

图5为具有较低修复带宽开销的局部Piggybacking码的特殊结构图，即当k可以整除r−1时，此时令$t + 1 = k/(r - 1)$，$\left| {{A_x}} \right| = r - 1$，$x = 1,2,\cdots,t + 1$。

DownLoad: Full-Size Img PowerPoint

与局部Piggybacking码的一般结构相比，此构造，第1步对信息节点进行分组，第2步生成局部校验块，其余构造步骤与一般结构相同，如图5所示。在此结构中，每个集合的数据块和局部校验块在该集合进行错位循环放置。当节点故障时，仅需要在故障节点所在集合进行修复，无需连接其他集合的节点，可以在一定程度上减少信息节点的修复度及多个信息节点故障的修复复杂度。

以（13, 8）MDS码作为基本码，子条带数目$\alpha = 2r - 1 = 9$为例，将8个信息节点分为2组，分别为{1,2,3,4}，{5,6,7,8}。之后，将2个局部组和对应局部校验条带内的所有数据块进行循环错位放置。在$k = 8,r = 5$的一般结构中，信息节点1故障，修复时需连接节点2,3,4,6,7,8,9进行数据块的读取和下载，修复度为7；而在特殊结构中，当信息节点1故障时，仅需连接节点2,3,4,9即可修复故障节点，修复度仅为4。

3.   修复分析

3.1   单节点故障修复

局部Piggybacking码在单个信息节点故障时，统一利用局部校验块进行修复，在单个校验节点故障时，利用MDS性质和局部校验块进行混合修复。信息节点i$(1 \leqslant i \leqslant k)$故障的修复算法如下：1）下载信息节点中除第r个子条带以外的所有条带中与故障信息节点i下标相同的数据块，通过局部校验块进行修复；2）若$i \leqslant \left\lceil {\dfrac{k}{2}} \right\rceil$，需下载第r个子条带前$\left\lceil {\dfrac{k}{2}} \right\rceil$个数据块中未失效的数据块及${x_1}$，通过异或修复信息节点i的第r个条带中失效的数据块；否则下载后$k - \left\lceil {\dfrac{k}{2}} \right\rceil$个数据块中未失效数据块及${x_2}$通过异或进行修复。

定理1 局部Piggybacking码在单信息节点故障时的平均修复带宽率为：

证明：设第i个信息节点故障需要下载的数据块为${B_i}$，若$i \leqslant \left\lceil {\dfrac{k}{2}} \right\rceil$，需下载$2(r - 2)(r - 1) + \left\lceil {\dfrac{k}{2}} \right\rceil$个数据块，否则需下载$2(r - 2)(r - 1) + \left\lfloor {\dfrac{k}{2}} \right\rfloor$个数据块。共k个信息节点，原始数据块总量为$k\left( {2r - 3} \right)$，所以：

假设校验节点故障，修复算法如下：1）第1个校验节点故障，通过MDS性质修复，即下载所有原始信息数据块修复；2）其余校验节点故障，利用校验节点的局部校验块和MDS属性进行混合修复。

定理2 局部Piggybacking码在单校验节点故障时的平均修复带宽率为：

式中，$m = \left\{ {\begin{array}{*{20}{c}} {t + 1,}&{k = \left( {t + 1} \right)\left( {r - 1} \right)} \\ {t,}&{k \ne \left( {t + 1} \right)\left( {r - 1} \right)} \end{array}} \right.$

证明：设第i个校验节点，即第k+i个节点故障需要下载的数据块为${B_i}$。节点k+1故障，根据MDS性质，需要下载$k\left( {2r - 3} \right)$个数据块。其余校验节点故障，第r个条带以外的数据块利用局部校验块进行修复，一个节点需下载$2\left( {r - 1} \right)\left( {r - 2} \right)$个数据块进行修复，共r-1个节点。第r个条带的修复需根据MDS性质及Piggybacking框架的性质进行修复，共需下载$k + \left( {k + m} \right)\left( {r - 2} \right)$个数据块，其中$m = \left\{ {\begin{array}{*{20}{c}} {t + 1,}&{k = \left( {t + 1} \right)\left( {r - 1} \right)} \\ {t,}&{k \ne \left( {t + 1} \right)\left( {r - 1} \right)} \end{array}} \right.$。所以：

3.2   多节点故障修复

考虑到存储系统中2节点故障占比为1.87%，3个或更多节点故障占比仅为0.05%^[17]，所以本小节主要分析2节点故障的快速修复。对于多节点故障，当故障节点数大于等于3时，使用MDS码译码修复。当故障节点数为2时，分为以下3种情况：1) 2个故障节点都为校验节点时，使用MDS码译码；2) 2个故障节点为1个信息节点和1个校验节点时，修复方式同单节点修复方式；3) 2个故障节点都为信息节点时，若2个故障节点不存在下标相同的数据块，采用局部校验块修复；若2个故障节点在1个局部组中存在j个下标相同的数据块，$j \in \left\{ {1,2,\cdots,r - 2} \right\}$，具体修复方式如下：1) 先下载第$r$到第$r + j$个子条带中未失效信息数据块以及2个未附加其他信息符号的校验块，设相同下标位于前j个子条带的故障节点为故障节点1。2) 优先修复故障节点2的第1个失效数据块，之后故障节点1的前j个失效数据块利用Piggyback函数进行修复。3) 剩余失效数据块利用局部校验块进行修复。

定理3 设$Z = C_k^2$，${S_1} = \left\{ {\left[ {k - 2\left( {r - 2} \right) - 1} \right]k} \right\}/2$，$j \in \left\{ {1,...,r - 2} \right\}$，$k=\left(r-1\right)t+y,0＜y\le r-1$，${Q_1} = 4( r - 1 ) \left( {r - 2} \right) + k$，${Q_2} = \left( {j + 1} \right)k + 2\left( {r - 1 - j} \right)\left( {r - 2 - j} \right) + j( t + 1 ) +j\left( {r - 3} \right) + 2\left( {r - 1 - j} \right)\left( {r - 2} \right)$。

则2信息节点故障的最大修复带宽率：

证明：设两信息节点故障，共有Z（$Z = C_k^2$）种可能：

1) 2信息节点无下标相同数据块，共有${S_1}$种可能，此时修复2个故障信息节点的数据下载量为:

2) 2信息节点中含有2j个数据块下标相同，$j \in \left\{ {1,...,r - 2} \right\}$，共有$Z - {S_1}$种可能。因具体修复过程中利用MDS修复的数据块和利用局部校验修复的数据块在下载过程中存在对某些数据块的重复下载，而实际情况中我们不需要对下载过的数据块重复下载，所以本节不考虑重复情况，给出最大修复带宽：

令$k = \left( {r - 1} \right)t + y,0 < y \leqslant r - 1$

所以：

3.3   平均修复度率

对于单信息节点故障，考虑第r个子条带的修复方式与其他子条带的修复方式不同，在$r \ne 3$且$k \geqslant 2\left( {r - 1} \right)$的情况下，得到信息节点的修复度率如下。

定理4 局部Piggybacking码信息节点的修复度率为：

证明：当k为偶数且$\dfrac{k}{2} \geqslant 2(r - 2) + 1$时，因结构中存在第r个子条带信息数据块失效时的修复方式与其他子条带不同，将信息节点平均分为2部分（奇数时2部分的修复度最大最小值不一样），在信息节点中，存在修复度最小为$\dfrac{k}{2}$，修复度最大为$\dfrac{k}{2} + r - 2$，整个过程一共包含$4\left[ {\left( {\dfrac{k}{2} + r - 2} \right) - \left( {\dfrac{k}{2}} \right) + 1} \right]$个节点。所以：

当k为偶数且$\dfrac{k}{2}＜2(r-2)+1$时，在信息节点中，存在修复度最小值为$2\left( {r - 2} \right) + 1$，修复度最大值为$\dfrac{k}{2} + r - 2$，节点的修复度变化情况和上述情况相同，整个过程包含$4\left[ {\left( {\dfrac{k}{2} + r - 2} \right) - \left(2\left( {r - 2} \right) + 1\right)} \right]$个节点。所以：

$k$为奇数的情况证明过程与上述同理。

定理5 局部Piggybacking码校验节点的修复度率为：

证明：第1个校验节点故障，需连接前k个信息节点，下载所有信息数据块。其余节点，除第r个条带以外的数据块，访问除第1个校验节点以及故障节点以外的$r - 2$个校验节点，第r个条带中的数据块恢复需要访问前k个信息节点，所以局部Piggybacking码校验节点的修复度率为${\Im ^{{\text{par}}}}{\text{ = }} \dfrac{{k + \left( {r - 1} \right)\left( {k + r - 2} \right)}}{{kr}}$。

4.   性能比较

4.1   存储开销

假设文件大小为M，将M分为$\alpha k$个未经编码的原始信息数据块（其中$\alpha$为子条带数，$k$为节点个数），所以框架中的每个数据块的大小均为$M/\alpha k$，RSR-II码、SPB码等现有的Piggybacking码的存储开销为${\alpha _1} = {M /k}$。本文构造的局部Piggybacking码的存储开销为${\alpha _2} = \dfrac{{\left( {2r - 1} \right)M}}{{\left( {2r - 3} \right)k}}$，所以相比现有的几种Piggybacking编码，本文所构造的局部Piggybacking码的存储开销的增加率为$2/{2r - 3}$。图6为本文构造的局部Piggybacking码的存储开销增加率与子条带数目之间的关系。在仿真过程中，取M=2 000 Mb，k=100, $10 \leqslant \alpha \leqslant 50$。通过图6可以看出，因在本文构造中，一个显著的特点是引入的局部校验子条带数不随k、r的变化而变化，所以随着子条带数的增大，增加的局部校验块与原始信息数据块的比值越来越小。当子条带数目为50时，存储开销的增加率为0.04，趋近于0。所以条带数增加到一定量时，局部校验子条带带来的存储开销变得极其微小，几乎可以忽略不计，从而在改善修复带宽开销的同时，尽可能地保持了存储效率。

DownLoad: Full-Size Img PowerPoint

4.2   修复带宽率

针对信息节点故障时的平均修复带宽率${\gamma ^{{\text{sys}}}}$和校验节点故障的平均修复带宽率${\gamma ^{{\text{par}}}}$，将本文构造的局部piggybacking码与现有的piggybacking码进行比较分析。为了更好地进行对比，设置OOP的条带数为$\left\lfloor {\sqrt {r - 1} + r - 1} \right\rfloor$，在进行信息节点的平均修复带宽率对比时，设置RSR-I的子条带数为2，RSR-II的子条带数为$2r - 3$，SPB的子条带数为$r$。这样的设置旨在精选出Piggybacking码在性能上表现出色的情况，作为基准，与本文构造的Piggybacking码进行全方位的对比。RSR-I和RSR-II信息节点的修复带宽率不随其结构的增加而改变，但其校验节点的修复带宽率会发生变化，所以在校验节点的平均修复带宽率对比时，设置RSR-I的子条带数为6，RSR-II的子条带数为$2\left( {2r - 3} \right)$，而SPB并未对校验节点进行捎带，所以SPB校验节点平均修复带宽率为1。

图7给出了节点的平均修复带宽率，可以看出，本文构造的局部Piggybacking码同时显著降低了信息节点和校验节点的修复带宽率，这是因为本文构造引入了局部修复组的思想。由图7a可以看出，本文构造的局部Piggybacking码在节点取值个数较小时，修复带宽率就相对较低。这是因为在信息节点修复过程中仅使用局部校验块进行修复。由图7b可知，本文构造的校验节点修复带宽率整体随节点个数的增加而降低。这是因为校验节点修复时虽然利用了局部的思想，但第r个子条带中的数据块的修复依旧取决于MDS译码和Piggyback函数。

DownLoad: Full-Size Img PowerPoint

图8给出了本结构在双信息节点故障时的修复带宽率。现有的Piggybacking算法并未提出2信息节点故障时的快速修复算法，默认其2节点故障修复时采用MDS修复，即修复带宽率为1。本结构下的双信息节点采用顺序修复，在$r \ne 3$且$k > 2\left( {r - 1} \right)$的情况下，修复过程利用MDS译码、Piggybacking译码以及局部修复相结合。图8给出了双信息节点不存在数据块下标相同情况下的修复带宽率Q1，及存在部分下标相同情况下的修复带宽率Q2。为了便于比较，这里只选取编码参数j=r−2时Q2的边界曲线。由图8可以看出，相比现有Piggybacking算法采用MDS译码，本文提出的局部Piggybacking码显著改善了双信息节点的修复带宽率性能。

DownLoad: Full-Size Img PowerPoint

4.3   修复度率

表1给出了现有的几种Piggybacking码和本文构造的局部Piggybacking码关于子条带数和修复度率的对比，其中局部Piggybacking码信息节点修复度率由定理4给出。从表1可以看出，现有的Piggybacking码信息节点的平均修复度率与k成反比，与r成正比。

Piggybacking编码	子条带数$\alpha$	修复度率
		信息节点$\Im _{}^{{\text{sys}}}$	校验节点${\Im ^{{\text{par}}}}$
RSR-II	$(2r - 3)\tau$	$\dfrac{{k + r - 1}}{k}$	$\dfrac{{k + (r - 1)(k + r - 1)}}{{rk}}$
OOP	$\sqrt {r - 1} + r - 1$	$\dfrac{{k + r - 1}}{k}$	$\dfrac{{k + (r - 1)(k + r - 1)}}{{rk}}$
SPB	$r$	$\dfrac{{(k + r)k - \displaystyle\sum\limits_{l = 1}^L {l{\varphi _l}} }}{{{k^2}}}$	1
局部Piggybacking码	$2r - 1$	$\Im _{}^{{\text{sys}}}$	$\dfrac{{k + \left( {r - 1} \right)\left( {k + r - 2} \right)}}{{kr}}$

 | Show Table

DownLoad: CSV

图9给出了信息节点和校验节点平均修复度率的仿真结果。与SPB、RSR-II以及OOP相比，本文所构造的局部Piggybacking码信息节点的平均修复度率显著降低，且最高降低了61.7%。SPB码的校验节点修复带宽率恒为1，而本文所构造的局部Piggybacking码因校验节点的第r个子条带并未生成可以进行局部修复的校验块，所以每个校验节点故障修复时都需要连接所有的信息节点，以至于修复度率大于SPB码的修复度率，但与RSR-II码和OOP相比，其修复度率更低。

DownLoad: Full-Size Img PowerPoint

5.   结束语

分布式存储系统中Piggybacking编码作为一种实用方法，显著降低了故障节点的修复带宽开销。但现有Piggybacking码大部分聚焦在信息节点的快速修复，而校验节点及多节点故障的修复依旧存在修复带宽开销较大的问题。为此，本文引入局部修复的思想，增加2个局部校验条带，同时通过对信息节点进行分组，采用局部组内按序匹配的方式进行捎带，构造的局部Piggybacking码对信息节点的修复度率和修复带宽率都具有显著改善，且同时降低了校验节点的修复带宽率。