基于Petersen图的部分重复码

余春雷，刘笃晋，朱华伟，杨佳蓉

（1.四川文理学院智能制造学院，四川 达州 635002；2.政务数据安全达州市重点实验室，四川 达州 635002；3.长安大学信息工程学院，陕西 西安 710064）

0 引 言

当今社会是一个互联网高速发展的时代［1］，近年来，我国数字经济创新发展逐年上升，人工智能、大数据、信息技术的快速发展给数据的存储带来了新的挑战。随着大数据应用的爆发性增长［2］，此前传统的存储系统设计已经无法满足大数据应用的需要。如何保证数据的可靠性和稳定性［3-4］等问题出现在存储厂商的面前。应用设备智能互联、数字化转型、高性能存储和云计算等技术的发展加速了大数据相关技术的进步［5］，而作为实现大数据价值的关键环节，数据存储与管理技术也日新月异，引领着大数据技术的变革［6-7］。

目前，大数据存储涉及介质、数据结构、数据连接控制等关键技术，存储机制正由集中式向分布式存储系统方向转变［8］。HDFS（Hadoop Distributed File System）是目前典型的分布式存储系统［9］，HDFS 架构如图1所示。

图1 HDFS架构

受大数据特征和应用场景影响，大数据存储与管理技术发展多样化且具有针对性，多基于分布式存储系统。分布式存储架构通过横向扩展，将分散的存储资源构成虚拟存储设备，具备多副本高可用、低成本大容量等优势［10］，多副本经常采用的技术是三副本［11-12］。多副本存在的缺陷是存储开销大［13］，为了降低存储开销，纠删码策略被应用到分布式存储系统中，使系统具有更好的容错性［14］。典型的纠删码有里所（Reed-Solomon，RS）码和磁盘阵列码［15-17］，它们都可以保证数据的可靠性，完成对故障的数据快速修复。纠删码通过少量的存储开销保证系统的冗余性，但是增加了其修复带宽开销。

针对多副本策略和纠删码策略等局限性［18-19］，文献［20］提出了再生码（Regenerating Codes）的编码方式。再生码是一类特殊的纠删码，经证明修复故障节点时，只需要连接相应节点就可以修复数据，但是再生码在处理数据中心的分层性质方面的效果仍然有限［21］；同时修复局部性高［22］，因为修复时需要连接多个节点。目前，再生码的研究包括最小存储再生MSR（Minimum Storage Regenerating）码和最小带宽再生MBR（Minimum Bandwidth Regenerating）码［23-25］。

为了解决修复分布式存储系统故障节点出现的修复过程复杂的问题，部分重复（Fractional Repetition，FR）码［26］的概念在基于MBR 码的基础上被提了出来。外部最大距离可分（Maximum Distance Separable，MDS）码和内部重复码是FR 码的构造算法的核心过程。 FR 码无需进行有限域运算，同时也可以降低节点存储开销［27］。因此，部分重复码被广泛研究。本文提出一种基于Petersen 图边染色［28］（Petersen Edge Coloring Based FR）码的构造算法，称为PECBFR 码。PECBFR 码可以随机访问模式下的系统存储容量，达到理论上的最优。此外，与分布式存储系统中的里所码以及简单再生码（Simple Regenerating Codes，SRC）相比，在系统修复故障节点时，提高了故障节点修复效率，保障了数据的可靠性和稳定性。

1 基础知识

1.1 系统模型

本文分布式存储系统用（n，k，d）来表示，其中分布式存储系统的节点总数用n表示，重构原文件所需最少节点数用k表示，修复一个失效节点所需的可用节点数用d表示，并且在分布式存储系统（n，k，d）中满足k≤d≤n-1。当系统中出现节点失效时，系统需要从其他存活节点下载数据对失效节点进行修复，下载的数据量β=1。同时，修复模型采用确定性修复方式。因此，修复完成以后节点的存储容量保持不变还是为d。在这种系统模型的修复方式下，分布式存储系统的存储容量用CMBR表示，存储容量表示任意选择k个分布式存储系统中存活节点能获得的最大文件大小。当从每个存活节点下载数据β=1 时系统的存储容量为：

1.2 边染色

把图G的边集划分成m个非空子集，即，i，j= 1，2，…，m，Ei∩Ej= ∅，i≠j，把Ei中的边用第i种颜色上色就是图G边染色。无环非空图G中边的r染色（edge r-coloring）中π是指r种颜色1，2，…，r对边集E（G）中元素的一种分配，使得相邻2 条边所染颜色不同。换句话说，G中边的r染色是映射：

使得对每个i(i= 1，2，…，r)，π-1(i)是匹配或者空集。若令：

1.3 部分重复码

定义1在（n，k，d）系统中，（n，d，θ，ρ）部分重复码可以由n个子集的集合N={N1，…，Nn}表示［29］，ρ是数据块的重复度，每个子集中的符号均属于符号集[n]={ 1，2，…，θ}。该（n，d，θ，ρ）部分重复码的构造过程满足如下条件：

1）每个节点存储d个数据块，即

2）[n]中的每个元素都出现于N中ρ个不同的子集。

在（n，d，θ，ρ）FR 码的构造过程中，其中参数满足θρ=nd。首先将原文件分割为m个数据块，如图2 所示，分别为数据块m0～m8，其次通过MDS 码对m0～m8进行编码，产生m0～m8、P9等编码数据块，P9为校验块数据块，保护数据的可靠性。然后采用复制策略，对m0～m8、P9等编码数据块复制ρ份，最后通过部分重复码的内部构造算法把所有的数据块存储在n个节点里。可以看出，在构造的FR 码中，任意选择2 个存储节点相同的数据块只有一个。随机连接3 个存储节点，可以获得的不同数据块是9 个，根据定义可知该FR 码率为9。此外，由式（1）可计算出该分布式存储系统的存储容量为9，因此在（n，k，d）系统中所构造的FR码是最优的。

图2 部分重复码构造过程

1.4 故障节点修复方法

确定性修复可以精准地恢复出故障节点的数据［30］，并且修复好的数据完好无损，这就是确定修复的特点。功能性修复是对数据进行间接修复，修复好的数据不是损失的直接数据，但是可以通过修复好的数据解码恢复出原来损失的数据。功能性修复照样保证了数据可靠性，恢复出来的节点仍具有修复性质，只是需要通过解码来完成恢复数据。

确定性修复与功能性修复如图3 所示。假设系统中节点N1出现故障时，这时存储在N1节点的数据块A和数据块B失效，如图3（a）所示，采用确定性修复的方式修复，通过分布式存储系统中其他的存活节点如节点N2、N3、N4提供数据块进行解码对故障节点进行修复，修复完成以后，跟N1节点毁坏前存储数据块是一样的，确定性修复可以精准地恢复原来损失的数据。如图3（b）所示，也是对故障节点进行修复，但采用功能性修复。与确定性修复对比可知，功能性修复修复成功的N0节点存储的数据跟N1有着很大差别，但是功能性修复也能够保证系统数据稳定性和可靠性，系统的容错能力保持不变。

图3 确定性修复与功能性修复

2 基于Petersen图的部分重复码构造

为了提高分布式存储系统中故障节点的修复效率，本文提出一种基于Petersen 图染色的部分重复码设计，称PECBFR 码。PECBFR 码在分布式存储系统修复故障节点时，能够快速地修复故障节点。通过染色链路构造的部分重复码，在修复局部性、修复复杂度、修复带宽开销方面相较于分布式存储系统中的常见编码算法都有较大的性能提升。构造步骤如下：

步骤1对Petersen 图的边进行染色，得到不同颜色的边e1，e2，…，el(1 ≤l≤μ) 。Petersen 图中的每个顶点vi(1 ≤i≤n)视为分布式存储系统中需要存储的数据块di(1 ≤i≤n)。

步骤2对原始数据块k采用MDS 编码，总共得到n个数据块，确定分布式存储系统中FR 码构造过程每个数据块di(1 ≤i≤n)的重复度ρ。

步骤3在染色的Petersen图中，任意选择3条颜色不同相邻的边组成的链路，且满足每条链路通过链路Li(1 ≤i≤210 )的集合构造部分重复码的内部重复码。

步骤4把每条链路Li(1 ≤i≤210 )视为部分重复码的存储节点Ni，对每条Li链路中对应顶点的数据块进行存储。

具体地，Petersen 图中边4 色可染，记χ(G)= min{r：G中边r色可染}，称为G的边色数（edge chromatic number）。由定义，若χ(G)=r，则G中边的任何r染色π=（E1，E2，…，Er）中每个Ei都是非空的匹配。换言之，G的边色数χ(G)是G中边不交匹配的最小数目，即χ(G)≥Δ(G)，所以Petersen 图中边4 色可染。根据边染色定理，对Petersen 图中所有的边进行染色，同时标记出每条边的颜色。如图4 所示，每种数字表示一种颜色。

图4 Petersen图的边4染色

部分重复码外部采用（10，8）MDS 编码，即产生2个编码校验块。然后确定部分重复码数据块的重复度ρ=2。接下来在图4中任意选择3条颜色不同相邻的边组成的链路Li，如表1所示为每条链路经过的顶点。

表1 Petersen图链路数据表

最后把每条链路Li（1≤i≤5）视为部分重复码对应的存储节点Ni（1≤i≤5），对每条Li链路中对应顶点的数据块进行存储，这样一种基于Petersen 图边染色的部分重复码构造完成，如图5 所示。从以上定理可以看出，PECBFR 码率可以超出系统存储容量，即Rc（k）＞CMBR。参数为（5，3，4）分布式存储系统的FR 码可以基于Petersen 图边染色来进行构造，每个数据块的重复度ρ=2。在图5 构造的部分重复码中，任意选择3个存储节点，可获取至少9 个不同的编码数据块，因此，Rc（3）=9。通过公式（1）可知，该系统的容量仅为9。因此，基于Petersen图边染色的PECBFR码算法的系统具有更大存储容量，存储效率高。

图5 FR码编码方案

3 性能分析

本章主要对基于Petersen图边染色的PECBFR码算法跟分布式存储系统中常见的编码算法进行比较。在存储开销、修复局部性、修复复杂度、修复带宽开销等性能方面进行比较，如表2 所示。为了量化好比较，具体地文件大小M=1500 Mb，SRC的子文件数f=5。

表2 编码方案的性能分析

3.1 修复带宽开销

表2 为几种常见编码方案在修复带宽开销跟修复局部性的性能分析。修复带宽开销是：故障节点的修改过程中下载的数据量。当单节点故障时，（n，k）RS 码修复时需要靠原文件修复故障节点，所以带宽开销为M，验证了（n，k）RS 存储效率高，但是修复带宽开销比较大的问题。在（n，k，f）SRC 编码方案中，修复故障节点，需要从其他数据节点下载f个数据块，编码方案中节点存储的数据块为f+1，并且数据块的大小是M/fk，因此（n，k，f）SRC 的修复带宽开销为（f+1）M/k［13］；可以看出（n，k，f）SRC 牺牲了存储开销，减少了修复带宽开销。基于Petersen 图边染色的PECBFR码算法，大小为M的文件先被分割为k份，每一份文件大小为M/k，4 个数据块存储在PECBFR 码的每个节点。因此，PECBFR码修复带宽开销为4M/k。PECBFR 码在存储开销跟修复带宽开销做出了最优的选择。图6所示为各种编码修复带宽开销对比。

图6 修复带宽开销对比

3.2 修复局部性

修复局部性指故障节点修复时需要连接的节点数，连接的节点数越多，修复局部性就越高，对网络通信质量的要求就高。如表2所示，分别给出了（n，k，f）SRC、（n，k）RS码、三副本以及PECBFR 码的修复局部性［13］，可以看出，三副本修复局部性为1，修复局部性最低。（n，k，f）SRC 的修复局部性为10，低于（n，k）RS码高于三副本跟PECBFR 码。（n，k）RS 码的修复局部性是最高的为k，三副本以高昂的存储开销换取了较低的修复局部性。基于Petersen 图边染色的PECBFR码算法的修复局部性为4。如图7 所示，为各种编码单节点故障的修复局部性分析图。PECBFR 码在存储开销跟修复局部性做出了最优的选择。PECBFR码在修复单节点故障时的修复局部性比RS码和SRC都要低。当出现两节点故障时，PECBFR 码与RS 码和SRC的修复局部性一样。

图7 修复局部性比较

3.3 修复复杂度

本节对于RS 码、SRC、PECBFR 码3 种编码的修复复杂度进行分析。RS码需要经过k2-1次有限域加法运算跟k2+k次有限域乘法运算才能修复故障节点，因此，O（2k2+k-1）是RS 码在修复单节点故障时的修复复杂度。对于SRC，（f-1）（f+1）次异或运算需要被系统运算执行才能修复故障节点，所以修复复杂度为O（f2-1）［29］。对于PECBFR 码，直接通过复制数据就可以进行修复，不需要经过其他复杂运算。由此可见，基于Petersen 图边染色的PECBFR 码算法具有较低的修复复杂度，当出现故障节点时，PECBFR 码算法能够快速修复故障节点。

3.4 节点修复选择度

对MDS码来说，系统可以在n-1个存活节点中任意选择k个存储节点修复失效节点。因此，MDS 码存在种修复方案，本文称这种可选修复的方案数为该节点的修复选择度。采用PECBFR 码的编码方案时，PECBFR 码中对外部MDS编码产生的每个编码数据块复制ρ个副本，然后存储在不同节点上。假设PECBFR 码节点的存储容量为T时，采用PECBFR 码的节点修复选择度为（ρ-1）T。如图8 所示，给出了PECBFR 码采用重复度ρ=3 时，PECBFR 码的存储容量T与节点修复选择度之间的关系。可以看出，PECBFR 码在故障节点失效时，存在多种修复方案，并且随着节点存储容量越大，修复方案越多。

图8 ρ=3时节点修复选择度与存储容量之间的关系

4 结束语

本文提出的一种基于Petersen 图边染色的PECBFR 码算法，通过染色链路构造的部分重复码，在修复局部性、修复复杂度、修复带宽开销等方面相较于分布式存储系统中的常见编码算法都有较大的性能提升。除此之外，如果随着数据块规模扩大，可以采用本文中多个算法存储模型对数据进行存储，具有可扩展性，更加具有发展前景和应用背景。