基于非均匀循环编码的分组修复码构造

王 静，雷 珂，李家仪，田松涛，王相隆

(1. 长安大学信息工程学院 西安 710064；2. 山东科技大学数学与系统科学学院 山东 青岛 266590)

随着信息技术的快速发展，海量数据存储引起了广泛关注。当存储PB 级以及更高量级数据时，传统的集中式存储系统在存储容量、存储成本和扩展性等方面存在诸多瓶颈，尤其是价格昂贵的设备开销使其无法适应当前存储需求。分布式存储系统以其海量存储能力、高可用性、高可扩展性和低成本等优势成为海量数据的有效存储手段[1]。分布式存储系统将大量文件存储在多个廉价存储设备中，随着系统规模的扩大，存储节点故障时有发生，因此需引入冗余存储来提高节点故障时的存储可靠性。常用的冗余存储技术包括复制策略和纠删码策略[2-5]。

复制策略不需要编解码运算，操作简单易于实现，但存储开销过大。相比复制策略，纠删码策略虽然具有较低的存储开销和较强的容错性能，但在修复故障节点时需要下载文件大小的数据量，修复带宽开销过高。针对上述两种冗余存储技术的不足，文献[6]创造性地将网络编码技术应用于分布式存储，提出了再生码的概念，降低了故障节点的修复带宽开销。文献[7-9]发现节点存储开销和修复带宽开销之间的最优折中曲线，以及该曲线上的两个极值点，达到这些极值点的再生码分别称为最小存储再生(minimum storage regenerating, MSR)码和最小带宽再生(minimum bandwidth regenerating, MBR)码。在再生码的修复过程中，新生节点需要从存活节点中连接d个节点完成修复，磁盘I/O 开销过高。为此， 文献[10-12]提出了局部修复码(locally repairable code, LRC)，通过将原始数据块分组生成组编码块，降低了磁盘I/O 开销；文献[13-14]进一步分别研究了局部修复码的构造以及协作局部修复码。文献[15]针对局部修复码在修复全局校验块时成本过高以及组内多节点故障时无法修复的问题，提出分组修复码(group repairable codes, GRC)。文献[16]在分组修复码的基础上，基于跨条带重叠编码的思想提出重叠分组修复码(rotated group repairable codes, RGRC)，获得了更好的数据修复性能。

上述编码方式均为所有数据块和校验块提供了相同等级的故障保护。而在实际的分布式存储系统中，因磁盘磨损状况和使用情况的不同，节点故障概率也会有区别。考虑到节点间不均等的故障概率，文献[17]在局部修复码的基础上，提出基于非均匀故障保护的局部修复码(unequal failure protection based local reconstruction code, UFPLRC)，将数据块划分为大小不等的分组，分配易出错的数据块到较小的分组，从而使存储系统的整体修复性能和可靠性得到显著提高，但存在组内多个数据块失效时无法局部修复以及修复全局校验块成本过高的问题。

为了对实际分布式存储系统中高故障率节点提供更高等级的保护，本文提出一种基于非均匀循环编码的分组修复码(group repairable codes based on non-uniform cyclic coding, GRC-NCC)，通过减少高故障率节点的修复成本来改善故障节点的修复性能。具体地，根据故障率对存储节点进行分组，高故障率节点存储到小分组以提供更高等级保护。在此基础上，使用跨条带循环编码的思想生成组编码块和全局校验块，故障节点修复过程中相邻条带的编码可以提供部分解码数据，获得较低的数据传输量和修复成本。

1 分组修复码和重叠分组修复码

1.1 分组修复码

基于(n,k)最大距离可分(maximum distance separable, MDS)码，将文件分为大小相等的k个原始数据块，经过编码生成n=k+m个编码块。GRC的构造过程为：将MDS 码的k个数据块分为L组，记为Sl(l=1,2,···,L)，将m=m0+m1个编码块中的前m0个编码块作为GRC 的全局编码块，在数据块分组Sl(l=1,2,···,L)中 生成m1个 组编码块；m1个组编码块生成方式与MDS 码编码块生成方式相同，只需保持本组内编码系数不变，其余组编码系数置零即可；最后将GRC 码的m0个全局编码块视为一组，再生成一个组编码块。

具体地，(15, 8)GRC 编码过程如图1 所示。将8 个原始数据块D1,D2,···,D8平均分成两组，为每个组分别生成m1=2个 组编码块P1、P2和P3、P4。将(12, 8)MDS 码 的m0=2个 编 码 块Q1、Q2作 为GRC 的全局编码块，再将其视为一组生成一个组编码块Q3。

图1 (15, 8)GRC 编码示意图

1.2 重叠分组修复码

(k,p,q,m)R GRC 基于跨条带编码的思想，k表示原始数据块的个数，p表示组编码块的个数，q表示全局编码块的个数，m表示全局组编码块的个数。(k,p,q,m)RGRC 的构造过程如下：将大小为M的文件按照指定的数据块大小进行划分，然后根据块数划分为M/k个条带；每次读入两个条带，将条带内数据划分为k/p个组，为每个组生成一个组编码块；再将条带数据划分为q组，记为Gi(i=1,2,···,q)，其中第一个全局编码块由本条带内的数据块编码得到，第二个全局编码块由第二个条带提供G1组和第一个条带提供剩余组数据求得，依次类推。

具体地，(4, 2, 2, 1)RGRC 的编码过程如图2所示。首先读取两个条带，将条带内数据划分为D1、D2和D3、D4，为每个组生成一个组编码块P1和P2；再将条带数据划分为两组，记为G1和G2，第一个全局编码块Q1由本条带内的数据求得，第二个全局编码块Q2由 第二个条带提供G1组和第一个条带提供G2组 数据求得；最后将Q1、Q2视为一组生成一个组编码块Q3。

图2 (4, 2, 2, 1)RGRC 编码示意图

2 基于非均匀循环编码的分组修复码

2.1 节点故障率

节点故障率 τ是节点发生故障的频数，以每单位时间的节点故障数表示[17]。节点故障率与平均无故障时间(mean time to failure, MTTF)之间的关系为：

式中，MTTF 表示系统无故障运行的平均时间，为取所有从系统开始正常运行到发生故障之间的时间段的平均值。实际分布式存储系统中节点故障率并不相同，呈现非均匀分布的特征。

2.2 基于非均匀循环编码的分组修复码构造

基于非均匀循环编码的分组修复码构造算法具体步骤如下。

1) 根据节点故障率对存储节点进行非均匀分组，记为Gj(j=1,2,···,l)。

3) 将多个条带组合成条带集，MDS 码编码块个数为m=m0+m1。

4) 为 λ个高故障率分组生成m1个组编码块，其中第一个组编码块由本条带内数据块计算得到，剩余组编码块由本条带与相邻条带各提供一部分数据块计算得到；同时，m1个组编码块生成方式与MDS码编码块生成方式相同，只需保持本组内编码系数不变，其余组编码系数置为零即可。

5)对于l−λ个低故障率分组，分别异或组内数据生成一个组编码块。

6) 对MDS 码的前m0个编码块，保持第一个全局编码块不变，依旧由本条带内的数据求得，剩余的全局编码块则由上一条带提供G1组和本条带提供剩余组数据求得，依次类推，最后再将全局编码块视为一组生成一个组编码块。

(k,λm1,l−λ,m0+1)G RC-NCC 由l个大小不等分组内的个数据块、λm1+(l−λ)+1个局部校验块、m0个全局校验块组成，编码后共生成n=k+λm1+(l−λ)+m0+1个编码块。具体地，(6, 2,1, 3)GRC-NCC 编码过程如图3 所示。

图3 (6, 2, 1, 3)GRC-NCC 编码示意图

根据节点故障率将存储节点划分为大小不等的l=2 个 分组，记为G1和G2。将MDS 码中k0=2个数据块存入第1 个分组G1，剩余k0+2=4个数据块存入第2 个分组G2。再将4 个条带组合成条带集，为λ=1个 高故障率分组生成m1=2个 组编码块p1和p2，其中p1由 组内数据计算得到，p2由组内前半段数据与上一条带中后半段数据计算得到。对由D3、D4、D5、D6组 成的l−λ=1个低故障率分组，异或组内数据生成一个组编码块p3。对 MDS 码的前m0=2个 编码块，保持第一个全局编码块q1不变，由本条带内的数据求得。剩余的全局编码块q2由 上一条带提供G1组 和本条带提供G2组数据求得。再将全局编码块q1和q2视为一个分组，生成一个组编码块q3。

2.3 故障节点修复

2.3.1 单节点故障

在GRC-NCC 编码方案中，单节点故障均可进行组内修复。下面分别以图3 中高故障率分组节点D1、低故障率分组节点D3以 及全局校验节点q1故障为例，对采用GRC-NCC 编码的单节点故障修复进行说明。

高故障率分组节点D1发生故障时，可通过节点D2与p1完成修复，总共传输8 个数据块。进一步地，节点D1也 可通过节点D2与 两个组编码节点p1、p2混合修复，如图4 所示，只需传输6 个数据块，且混合修复算法的优势随着条带数的增多更为明显。当低故障率分组节点D3故障时，可通过节点D4、D5、D6和组编码节点p3完成修复。当全局校验节点q1故 障时，可通过剩余的全局校验节点q2和组编码节点q3进行局部修复，从而减少修复成本。

图4 (6, 2, 1, 3)GRC-NCC 单节点故障修复

2.3.2 多节点故障

在GRC-NCC 编码方案中，多节点故障修复可分为组内修复与全局修复两种，修复原则是先组内修复，组内不可修复时再全局修复。下面分情况进行讨论：

1) 多个故障节点分别位于不同修复组内时，可分别在不同修复组内进行单节点修复。

2) 多个故障节点均位于高故障率分组内时，若故障节点数目不大于组编码节点数目m1，则可在组内完成修复；否则，将使用全局修复。全局修复中，若故障节点数目不大于编码节点(包括组编码节点与全局编码节点)数目，使用全局完成修复，否则无法成功修复。

3) 多个故障节点均位于低故障率分组内时，此时故障节点数目大于组编码节点数目，则在该故障情况下无法进行组内修复，只能采用全局修复。若故障节点数目不大于编码节点数目，使用全局修复，否则无法成功修复。

4) 其他多节点故障修复情况。对可使用组内完成修复的修复组先使用组内修复，再使用全局修复。全局修复完成后，修复条件可能会发生变化，此时若还可使用组内修复则继续进行组内修复，组内修复不可进行时再使用全局修复。重复以上过程，直至所有故障节点均修复成功。

以图3 中高故障率分组节点D1、D2、p1、p2全部故障以及全局编码节点q1、q2发生故障为例，说明采用GRC-NCC 编码方案无法成功修复故障节点的情况。首先在高故障率分组中，节点D1、D2以及组编码节点p1、p2全部故障，无法进行组内修复；其次全局校验分组中的全局编码节点q1、q2故障，故障节点数目大于未故障组编码节点数目，也不能进行组内修复；最后考虑全局修复，由于全局编码节点q1、q2故 障，则节点D1、D2不能被修复，故在该故障情况下无法成功修复。

图3 中高故障率分组发生两节点故障时，仍可进行组内修复，减少修复成本；当高故障率分组节点全部故障时，可使用全局修复完成所有故障节点的修复，为高故障率节点提供了更高等级的保护。低故障率分组发生两节点故障，修复过程中相邻条带的编码可为对方提供一部分解码数据，减少数据的传输量。如图5 所示低故障率分组节点D3和p3故障时，首先通过剩余数据节点与全局校验节点q2修复第一条带与第三条带中对应节点D3的数据块，所用数据块以 Δ表示；再通过剩余数据节点与全局校验节点q1修 复第0 条带与第2 条带中对应节点D3的数据块，所用数据块以 ○表示；最后通过已修复的节点D3和 节点D4、D5、D6实现组编码节点p3的修复。可见，GRC-NCC 编码方案为高故障率节点提供更有效保护的同时，也考虑了使用跨条带循环编码的思想以减少低故障率节点的修复成本。

图5 (6, 2, 1, 3)GRC-NCC 中低故障率分组两节点故障修复

3 性能分析

本节主要分析GRC-NCC 的存储开销、修复局部性、修复带宽开销和容错能力，并与RS 码和RGRC 进行比较。由于修复带宽开销和修复局部性依赖于节点故障，故分别讨论了单节点故障和多节点故障的情况。

3.1 存储开销

本文采用文献[18]中定义的存储开销，存储编码数据块需要的存储空间与存储原始数据块存储空间的比值。依据上述存储开销的定义，(n,k)RS码和(k,λm1,l−λ,m0+1)GRC-NCC 的存储开销分别为：

根据 (k,λm1,l−λ,m0+1)GRC-NCC 构造过程得m0+m1=n−k，则可直接比较RS 码和GRC-NCC的存储开销。对于 (k,λm1,l−λ,m0+1)GRC-NCC，其存储开销为：

因λ ≥1，m1≥1且l≥2，可推断出：

因此，相比于RS 码，GRC-NCC 没有达到最优的存储开销。

3.2 修复单故障节点

修复单故障节点时，RS 码的修复局部性和修复带宽开销分别为k和n。

除RS 码外，RGRC 和GRC-NCC 的构造使得故障节点可能位于局部组或全局校验组，因此综合考虑两种情况，讨论RGRC 和GRC-NCC 在单节点故障情况下的修复局部性和修复带宽开销。首先分析RGRC 和GRC-NCC 在单节点故障情况下的修复局部性。修复局部性是指故障节点修复过程中连接的存活节点数目。

在(k,λm1,l−λ,m0+1)GRC-NCC 中，故障节点可以位于局部组，包括高故障率分组和低故障率分组，也可以位于全局校验组。当故障节点位于第i(i=0,1,···,l−1)个局部组时，修复单故障节点需要连接k0+2i个 存活节点，其中；当故障节点位于全局校验组时，该故障节点的修复局部性为m0，则GRC-NCC 的修复局部性为：

对于 (k,p,q,m)RGRC，当单故障节点位于局部组时，修复局部性为k/p；当单故障节点位于全局校验组时，修复局部性为q/m，所以RGRC 的修复局部性为：

为方便比较，设定RGRC 和GRC-NCC 中分组数目及全局校验节点个数均为2。图6 为单节点故障时，RS 码、RGRC 和GRC-NCC 的修复局部性曲线。从图6 可以看出，随着存储节点数目k的增加，RS 码、RGRC 和GRC-NCC 的修复局部性也随之线性增加，且提出的GRC-NCC 的修复局部性最小，RS 码的修复局部性最大。

图6 单节点故障情况下的修复局部性

进一步分析修复单节点故障的带宽开销。修复带宽开销是修复故障节点时需要下载的数据量的大小。当GRC-NCC 的单故障节点位于局部组时，修复带宽开销为w1=(k0+2i)n/k；当单故障节点位于GRC-NCC 的全局校验组时，修复带宽开销为w2=m0n/k；考虑到k=，n=k+λm1+l−λ+m0+1，则GRC-NCC 的修复带宽开销为：

下面讨论RGRC 的修复带宽开销。当RGRC的单故障节点位于局部组时，修复带宽开销为=(k+p+q+m)/p；当单故障节点位于全局校验组时，修复带宽开销为=q(k+p+q+m)/km。因此，RGRC的修复带宽开销为：

取n=k+4，假定RGRC 和GRC-NCC 中分组数目及全局校验节点个数均为2，RS 码、RGRC和GRC-NCC 的修复带宽开销的性能如图7 所示。由图可知，GRC-NCC 的修复带宽开销最小，RGRC次之，RS 码的修复带宽开销最大。

图7 单节点故障情况下的修复带宽开销

3.3 修复多故障节点

修复多故障节点时，RS 码的修复局部性和修复带宽开销仍分别为k和n。对于RGRC 和GRCNCC，当多个故障节点分别位于不同分组时，均可通过组内完成修复，因此主要讨论同组发生多节点故障的情况。

RGRC 无论是修复局部组还是全局校验组的多故障节点，都必须采用全局修复，因此RGRC 的修复局部性为k，修复带宽开销为k+p+q+m。

对于GRC-NCC，当高故障率分组发生多节点故障，且假设故障节点个数不大于m1时，仍可进行组内修复，修复局部性为k0+2i(i=0,1,···,λ−1)；当低故障率分组或全局校验组发生多节点故障时，此时需采用全局修复，修复局部性为k。所以GRC-NCC 的修复局部性为：

取RGRC 和GRC-NCC 中分组数目及全局校验节点个数为2 时，得到图8 所示的多节点故障时的修复局部性和存储节点数k的关系。从图中得知，GRC-NCC 修复多节点故障时的修复局部性最小。

图8 多节点故障情况下的修复局部性

当高故障率分组发生多节点故障时，GRC-NCC的修复带宽开销为w1=(k0+2i)n/k；当 低故障率分组或全局校验组发生多节点故障时，其修复带宽开销为w2=n。所以GRC-NCC 的修复带宽开销为：

设定n=k+4，RGRC 和GRC-NCC 中分组数目及全局校验节点个数为2，多节点故障时几种码的修复带宽开销和存储节点数k的关系如图9 所示，其中GRC-NCC 修复多节点故障时的修复带宽开销最小。

图9 多节点故障情况下的修复带宽开销

实际分布式存储系统中，多节点故障导致数据不可用占据了较少数情况。而对于GRC-NCC 而言，多个故障节点同时位于低故障率分组的可能性更小，因此若只考虑高故障率分组发生多节点故障的情况，则GRC-NCC 的修复局部性为k0+2i(i=0,1,···,λ−1)，修复带宽开销为 (k0+2i)n/k。图10和图11 分别给出了此种情况下各种码的修复局部性和修复带宽开销随存储节点数k的变化曲线。从图中可以得知，GRC-NCC 具有更优的修复局部性和修复带宽开销。

图10 高故障率分组多节点故障情况下的修复局部性

图11 高故障率分组多节点故障情况下的修复带宽开销

3.4 容错能力

容错能力是指分布式存储系统可以容忍节点故障且保证数据不丢失的能力，是分布式存储系统的一个重要因素[19]。具体地，一个(10, 6)RS 码可以容忍任意4 个节点故障。对于(6, 2, 2, 1)RGRC 和(6, 2, 1, 3)GRC-NCC 来说，两种编码均能恢复任意3 错，因此下面主要讨论故障节点数大于3 时，两种编码方式的容错能力。

当故障节点数为4 时，统计(6, 2, 2, 1)RGRC不可修复情况的数目为，计算其容4错能力为：

(6, 2, 1, 3)GRC-NCC 容4 错能力为：

当故障节点数为5 时，(6, 2, 2, 1)RGRC 和(6,2, 1, 3)GRC-NCC 容5 错能力分别为：

(6, 2, 2, 1)RGRC 最多能容忍5 个节点故障，其容6 错能力为0；而(6, 2, 1, 3)GRC-NCC 容6 错能力为：

图12 给出了(10, 6)RS 码、(6, 2, 2, 1)RGRC和(6, 2, 1, 3)GRC-NCC 在不同故障节点数目情况下的容错能力，其他k和故障节点数目情况下同理。通过上述分析对比可得，相比于其他两种编码方式，GRC-NCC 的容错能力更好，同时可以容忍更多的节点故障。

图12 容错能力对比

4 结束语

实际分布式存储系统中节点故障率不同，而现有的纠删码大多都是为节点提供相同等级的保护，这使得高故障率节点没有得到更高等级的保护。针对该问题，本文提出一种基于非均匀循环编码的分组修复码GRC-NCC，根据节点故障率对存储节点进行非均匀分组，同时使用跨条带循环编码的思想，减少故障修复过程的数据传输量。与RS 码和RGRC 相比，GRC-NCC 具有更好的修复局部性和修复带宽开销性能，且在多节点故障修复过程中性能更优，同时容错性能也更好。