一种异构分布式存储再生码变换原理

苗斌 宋苗苗 李文庆 王文彦 董国法 王晓燕 张可可 徐宇柘 管万春

摘要：再生码是一类分布式存储编码，由于在节点存储和修复带宽两方面均有效而被广泛研究。基于乘积矩阵（PM）理论的最小存储再生（PM-MSR）码是一类同构分布式存储再生码，具有最小的节点存储。提出一种再生码变换原理，能够根据PM-MSR码产生新的再生码，新的再生码用于异构分布式存储系统。严格证明了新再生码结构的数据重构和数据修复性质，并提供了编码实例。新的再生码与PM-MSR码具有相同的存储消耗和带宽消耗，但新的再生码具有更小的平均节点故障率，这对实际应用具有吸引力。

关键词：变换原理;再生码;异构分布式存储;数据重构;节点存储;对比分析

中图分类号：TN915.41-34

文献标识码：A

文章编号：1004-373X（2019）24-0104-04

0 引言

近年来，分布式存储已成为大规模数据存储的主流方案，如谷歌的分布式文件系统GFS（ Google File Sys-tem），亚马逊的EBS（ Elastic Block Store）[1]等。在一个分布式存储系统（DSS）中，数据被编码并分散地存储在多个存储节点来实现长久稳定的数据存储，这些存储节点通常单个是不稳定的，容易发生故障。为了维持系统稳定性，系统必须能够修复故障节点。

相比传统的两种故障修复策略，即复制[2]和纠删码技术[3]，再生码（RC）技术因在节点存储和修复带宽两方面都有效而受到广泛关注[4]。复制策略是最简单、最直接地增加冗余的方式，由于具有最小的修复带宽（即修复一个故障节点所需下载数据的总量）并且没有额外的计算消耗，因此应用在早期的很多实际DSSc4]，然而，复制要求的存储消耗是巨大的。作为复制策略的推广，纠删码能够提供更好的存储效率，即原始文件大小与存储空间的比率。然而，当修复故障节点时，采用纠删码会导致大量修复带宽。研究表明，在节点存储和修复带宽之间存在一个tradeoff，并且RC能够获得这个tradeoff曲线上的点[4]。

在这个存储一带宽tradeoff曲线上存在一個特殊点，称作最小存储再生（MSR）点，能够获得这个点的RC称为MSR码。文献[5]采用积矩阵（PM）理论来为同构DSS构建了MSR码结构。这里同构DSS指系统中的存储节点具有相同的性能参数，如节点存储容量、修复带宽等。异构系统包含具有不同特性的存储节点，应用实例包括P2P （Peer-to-Peer）云存储[6]，用于视频点播的互联网缓存系统[7-8]以及异构无线网络中的缓存系统[9]。关于异构DSS中的RC研究最近开始出现。文献[10]提出了扩展的PM （EPM）理论，并基于此设计了最优的异构RC结构，然而，提出的EPM理论以及异构RC结构局限于修复带宽异构的场景，并不确定能否用于存储异构DSS。文献[11]考虑一个存储和带宽均异构DSS，其中，系统中存在一个超级（ Super）节点，相比其他节点，这个超级节点具有更大的存储容量以及更高的稳定性和可得性，作者提供了这种系统的异构编码方案。

在文献[5]的基础上，考虑文献[11]中提出的超级节点模型，其中系统节点具有不同的存储容量和修复带宽，提出一种简单有效的编码变换原理，能够将文献[5]中构建的MSR码（同构RC）通过简单的变换得到新的RC，新的RC能够适用于存储和修复带宽均异构的超级节点模型。理论上证明了新RC的数据重构和数据修复性质。进一步，通过编码实例演示了新RC的数据修复过程。通过对比传统同构RC，即MSR码，提供了新的存储和带宽异构RC的性能分析。

1 系统模型

在同构系统中，一个（n，k，d，α，β）RC能够在一个含有n个存储节点的DSS中存储一个大小为B的数据文件，每个节点存储α个符号，这些符号来自大小为q的有限域Fq。要求一个合法用户（DC）能够连接n个节点中的k个并下载数据实现原始文件的重构，这个过程叫作数据重构。此外，当一个节点发生故障时，一个（n，k，d，a，β ）RC允许新的替换节点连接剩余n-l个存活节点中的d个节点（称作帮助节点）.并从每个帮助节点下载β个数据来修复故障节点。其中，β称为帮助节点的修复带宽，这个过程称为数据修复。修复一个故障节点所需的下载数据总量为d，β，称为总修复带宽γ，即γ=dβ（≥α）。

考虑超级节点系统[11]，其中包含1个超级节点，它具有更高的存储容量和修复带宽，标记其存储容量和修复带宽分别为αs和βs。此外，系统还包含h-l个普通节点，它们之间具有相同的存储容量和相同的修复带宽，标记每个普通节点的存储容量和修复带宽分别为αu和βu，并满足αs= 2au，βs=2βu。这样，系统整体上是一个存储异构，即αs≠αu，修复带宽也异构的系统，即βs≠βu。这种情况在实际中是有可能的，比如在一个P2P备份系统中，这个超级节点可能是服务器（ServiceProvider），它比其他的Peers具有更高的可得性，提供更大的容量和带宽。

当αs=au并且βs=βu时，考虑的系统模型就变成了一个同构系统，即每个节点的存储容量和修复带宽均相同。

2 存储和带宽异构编码变换原理

针对存储和修复带宽均异构的超级节点场景，将同构RC，即PM-MSR码C进行变换得到新的RC，标记为码C，具体的编码变换原理如下：

码C是在p=i时设计的，因此在码C中令βu=1，并令αu=a，这样编码变换原理的条件为：C中剩余的每1行分别对应h-l个普通节点中的每一个，即c1，c2表示存储在超级节点V1上的内容。ci（i∈[3，n]）表示存储在普通节点Vi-1上的数据，这样得到新的再生码C。码C的数据重构和数据修复性质将由下面两个定理给出。

定理1（数据重构）：在码C中，任意用户（DC）能够连接k个普通节点或者连接1个超级节点和k-2个普通节点，实现原始文件的重构。

證明：在码C中，任意k个普通节点对应原始码字矩阵C中除去前2行的任k行，这样，一个用户（DC）连接任意k个普通节点，等价于码c中这个DC连接除去节点V1和V2的任意k个节点，根据码c的数据重构性质（即任意k个节点可以实现原始文件的重构）可知，这个DC能够重构原始文件;另一方面，在码C中，超级节点对应原始码字矩阵c中前2行，一个DC连接1个超级节点和k -2个普通节点，等价于码C中这个DC连接节点Vi和V2以及其余任意k-2个节点，根据码C的数据重构性质可知，该DC能够实现原始文件重构。

定理2（数据修复）：在码C中，当一个普通节点发生故障时，新的替换节点能够连接任意d个存活的普通节点，并从每个普通节点下载βu=1个符号可以修复故障节点;新的替换节点也可连接1个超级节和任意d-2个存活的普通节点，并从超级节点下载βs=2个符号，从每个普通节点下载βu=1个符号，可以修复这个故障节点。

证明：在码C中，由于任意d个普通节点对应原始码字矩阵C中除去前2行的任意d行，一个故障的普通节点的替换节点连接任意d个普通节点并从每个普通节点下载βu=1个符号，等价于码C中这个替换节点连接除去节点Vi和V2的任意d个节点，并从每个节点下载β=1个符号，根据码c的数据修复性质（即任意d个存活节点可以实现故障修复），该替换节点能够修复这个故障节点;此外，在码C中，超级节点对应原始码字矩阵c中前2行，新的替换节点连接1个超级节和任意d-2个存活的普通节点，并从超级节点下载βs=2个符号，从每个普通节点下载βu=1个符号，这等价于码c中这个替换节点连接节点V1和V2以及其余任意d-2个存活的节点，并从节点V1和V2一共下载2β=2个符号，从其余每个节点下载p=i个符号，根据码C的数据修复性质，该替换节点能够实现故障节点的修复。

理论上，超级节点发生故障，等价于2个普通节点故障，通过完成2个普通节点的修复即可实现超级节点的修复。

3 讨论分析

通过对比传统同构再生码PM-MSR码C和存储带宽异构再生码C，在公式（1）下给出这两种编码的主要性能参数如表1所示。其中，假设普通节点单位时间的故障率为F，对于同构再生码C，平均节点故障率为fe =f;而对于码e，由于超级节点具有更高的稳定性和可靠性，因此可以假设超级节点的故障率为fs（

对比发现，码C和码C具有相同的总存储消耗以及修复一个故障节点的带宽消耗，然而，码C具有更小的平均节点故障率，因而在一段时间A内系统因修复故障维持稳定性而消耗的总修复带宽更小，这对实际应用具有吸引力。此外，码C可以具有更小的帮助节点个数，通常情况下，更少的帮助节点是更有利的，因为帮助修复故障节点会给存活节点带来额外的工作负担，更少的帮助节点表明修复一个故障节点需要的存活节点更少，这样引起系统的额外负担更小。

4 结论

基于乘积矩阵（PM）的最小存储再生码（PM-MSR）能够用于同构分布式存储系统，具有最小的节点存储。提出的异构再生码变换原理能够将PM-MSR码变换得到新的存储带宽异构再生码。理论上证明了这个异构再生码的数据重构和数据修复性质，并通过实例演示了这个异构再生码的故障修复过程。通过对比分析PM-MSR码，在相同的存储消耗和相同的修复一个故障节点的带宽消耗条件下，这个异构再生码具有更小的平均

参考文献

[1]齐凤林，宫庆媛，周扬州，等，分布式存储再生码数据修复的节点选择方案 [J].计算机研究与5发展 . 2015 （ z2） ： 68-74.

QI Fenglin， GONG Qingyuan， ZHOU Yangfan， et al. Hetero-geneity-aware node selection for data repair in distributed stor-age systems [J]. Journal of computer research and develop-ment. 2015（S2） ： 68-74.

[2] BHAGWAN R， MOORE D. SAVAGE S， et al. Replicationstrategies for highly available peer-to-peer storage [J]. Future di-rections in distributed computing， 2002， 2584（5） ： 153-158.

[3] WEATHERSPOON H， KUBIATOWICZ J D. Erasure codingvs. replication： a quantitative comparison [J]. Lecture notes incomputer science. 2002， 2429： 328-337.

[4] DIMAKIS A G. GODFREY P B， WU Y. et al. Network cod-ing for distributed storage systems [J]. IEEE transactions on in-formation theory. 2010. 56（9） ： 4539-4551.

[5] RASHMI K V. SHAH N B， KUMAR P V. Optimal exact-re-generating codes for distributed storage at the MSR and MBRpoints via a product-matrix construction [J]. IEEE transactionson information theory ， 2011， 57（ 8） ： 5227-5239.