一种再生码构造方法、文件重构方法及节点修复方法

摘要

本发明公开了一种再生码编码方法，包括获取组合设计和存储数据块；对区组排序并编号，统计元素出现的区组及位置，得到文件符号；对原文件进行编码，得到编码块；为每个编码块分配一个不同的文件符号；将每个元素一致的文件符号集合所对应的编码块放置在同一存储节点中，得到再生码。本发明还公开了一种基于所述的再生码构造方法的文件重构方法及节点修复方法。本发明提出的再生码构造方法参数限制宽松且能达到辛格尔顿上界，文件重构和节点修复过程运算简单，同时节点修复效率较高。

权利要求

1.一种再生码构造方法，其特征在于包括如下步骤：S1．获取组合设计和存储数据块；获取的组合设计具体为，选择满足组合条件的t‑设计，λ为t‑平衡数，表示任意t元子集均出现在λ个区组中，其中，记b为区组个数， ；

记r为元素重复度， ；

组合条件为：

；

其中，t为子集的元素数；v为设计的阶，具体为设计中不同元素的总数；m为区组容量，具体为一个区组中的元素个数；

获取的存储数据块具体为，设存储原文件大小为M ，将原文件拆分成个大小相等的数据块；

S2．对区组排序并编号，统计元素出现的区组及位置，得到文件符号；

S3．对数据块进行编码，得到编码块；

S4．为每个编码块分配一个不同的文件符号；

S5．将每个元素一致的文件符号集合所对应的编码块放置在同一存储节点中，得到再生码。

2.根据权利要求1所述的再生码构造方法，其特征在于步骤S2的文件符号设为 ，其中1≤i≤b，1≤j≤m，b为区组个数，m为区组容量；同时 表示元素h出现在第i个区组中的第j个位置；将区组编号记为B1,B2,…,Bb，对于区组Bi，将其中的元素由小到大顺序排列，位置编号记为{1,2,…,m}。

3.根据权利要求2所述的再生码构造方法，其特征在于步骤S3具体为利用双层编码策略对数据块进行编码；外层获得的MDS码构造如下：利用参数为 MDS码对 个数据块进行编码，获得b(m‑t+1)个编码块，其中b为区组个数，m为区组容量，t为子集的元素数，λ为t‑平衡数，表示任意t元子集出现在λ个区组；

内层获得的MDS码构造如下：将上述利用外层编码得到的b(m‑t+1)个编码块均分为b组，利用参数为(m,m‑t+1) MDS码对每组中的m‑t+1个编码块进行二次编码，最终得到bm个编码块。

4.根据权利要求3所述的再生码构造方法，其特征在于步骤S4具体包括，为上述获得的每一个编码块分配一个文件符号作为标识，不失一般性地，将 的前个文件符号 作为外层编码生成的冗余块的标识；将 的文件符号 作为内层编码生成的冗余块的标识，其中， 表示元素h出现在第i个区组中的第j个位置，m为区组容量。

5.根据权利要求4所述的再生码构造方法，其特征在于步骤S5具体包括，每当发现一个文件符号 ，若其元素h与之前的文件符号 不同，则分配一个新的存储节点并编号为h；对于每一个文件符号 ，若其元素h已分配存储节点，则将元素h相同的文化符号所对应的编码块存放到编码为h的存储节点中，则一个存储节点存储r个编码块，r为元素重复度；得到参数为[n,k=n‑t,d=n‑t+1]的再生码，n为节点个数，k为下载数据的个数，d为参与修复的节点个数，t为子集的元素数， 表示元素h出现在第i个区组中的第j个位置。

6.一种基于权利要求1 5之一所述的再生码构造方法的文件重构方法，其特征在于包~

括如下步骤：

A1．根据步骤S1 S5构造再生码；

~

A2．连接到存储节点；

A3．在下载当前编码块时，进行重构第一次判断；

A4．在完成一个编码块的下载后，进行重构第二次判断；

A5．利用内层及外层的MDS编码规则恢复原文件。

7.根据权利要求6所述的文件重构方法，其特征在于步骤A3的重构第一次判断具体包括，对于当前具有相同区组编号i0的文件符号 ，是否已经下载了m‑t+1个文件符号所代表的编码块， 表示元素h出现在第i0个区组中的第j个位置，m为区组容量；

若判断为是，则停止下载当前编码块；若判断为否，则下载当前编码块；步骤A4的重构第二次判断具体包括，判断是否已经下载了 个编码块；若判断为是，则停止下载过程，若判断为否，则继续下载过程，b为区组个数，t为子集的元素数，λ为t‑平衡数，表示任意t元子集出现在λ个区组中。

8.一种基于权利要求1 5之一所述的再生码构造方法的节点修复方法，其特征在于包~

括如下步骤：

B1．根据步骤S1 S5构造再生码；

~

B2．确定失效节点的序号；

B3．在组合设计中确定失效节点出现过的区组序号；

B4．从n‑t+1个节点中下载编码块，共下载r(m‑t+1)个编码块，r为元素重复度，n为节点个数，t为子集的元素数，m为区组容量；

B5．将步骤B4下载的r(m‑t+1)个编码块分成r组，每组的编码块具有相同的区组编号i；

B6．对每一组编码块利用内层获得的MDS码的编码规则恢复一个编码块；将r组编码块恢复出r个编码块；

B7．将恢复出的r个编码块存储到一个新的存储节点，并将此节点加入原存储系统中完成修复过程。

9.根据权利要求8所述的节点修复方法，其特征在于步骤B2具体为，从剩下的完好节点中对元素编号，记为{h1,...,hv‑1}，将元素编号与 设计中的元素对比，确定失效节点的序号h0；其中v为设计的阶，m为区组容量，λ为t‑平衡数；步骤B3的区组序号记为{i1,...,ir}；步骤B4的文件符号具体为 ，表示h0出现在第i个区组中的第j个位置，。

说明书

一种再生码构造方法、文件重构方法及节点修复方法

技术领域

[0001] 本发明具体涉及一种再生码构造方法、文件重构方法及节点修复方法。

背景技术

[0002] 在当今信息爆炸的时代，如何安全可靠地存储海量数据成为了亟需解决的问题。传统的文件存储系统已不能满足可用性和可扩展性等要求，分布式存储系统(Distributed 
Storage System)应运而生。该系统利用分布式技术，将存储节点通过网络联结起来形成一
个能存储海量数据的集群。分布式系统将数据文件分散放置于多个存储节点中，由于网络
故障或物理损坏，单个存储节点可能会失效，因此分布式系统必须引入冗余信息来保证可
靠性。常见的冗余策略有多副本策略和纠删码策略。多副本策略就是把原文件复制若干倍
后再存储，当有节点失效时，替换节点就可以直接从它的副本中复制数据，因此系统中只要
存在一个完整的数据副本，源文件就能正常使用；但这种方案存储效率和系统可靠性较低。
纠删码策略采用纠删码处理原始文件，常用的纠删码为(n, k)最大距离可分(Maximum 
Distance Separable, MDS)码，即将原始文件分成大小相等的k份，由这k份文件经线性编
码后生成n‑k份冗余信息，利用n个节点存储n个线性无关的编码块，终端用户可以通过连接
到任意k个节点恢复出原始文件。显然纠删码策略存储效率更高，但是实现也更复杂，应用
难度大。

[0003] 在分布式存储系统中，利用n个节点存储大小为B的原始数据，每个节点存储的数据量为α，终端用户从n个存储节点中的任意k个下载数据即可恢复出原始文件，该过程被称
为文件重构过程。当存储系统中有存储节点失效时，为了保证分布式系统的整体功能，需要
对该失效节点进行恢复，该过程被称为节点修复过程。

[0004] RS（Reed‑Solomon）码是一种常见的MDS码，RS码的节点修复过程为：先建立一个新的存储节点，再连接至k个节点下载数据并恢复出原始文件，利用原始文件经线性编码后再
向该新节点存储相应的数据。图1为现有技术中RS码修复过程示意图，易见，为恢复一个节
点中的存储信息而下载了k个节点的存储数据，修复节点时的数据传输量远大于节点的存
储量，即节点的修复过程需要浪费大量的网络带宽。

[0005] 为了降低修复过程中的修复带宽，文献[A. G. Dimakis, P. B. Godfrey, Y. Wu, M. J. Wainwright, and K. Ramchandran, “Network coding for distributed 
storage systems,” IEEE Trans. Inf. Theory, vol. 56, no. 9, pp. 4539–4551, 
Sep. 2010] 引入了网络编码的概念，即在修复失效节点时，取较多的节点参与修复，且参
与修复的节点先将本节点内的数据经过线性组合后再上传，这能极大地降低修复失效节点
的带宽消耗，该文使用信息流图对分布式存储系统进行建模，并对其进行最小割分析，如图
2所示。图2中S表示信息源，即原始数据。每个存储节点 由输入节点 、输出节点
和有向边 来表示，有向边上的权值为该节点的数据存储量，其值均为
α。DC (Data Collector)表示数据收集器，数据收集器DC收集任意k个节点的数据，就能恢
复原始数据；从d个节点获取数据，就能修复失效节点。对图2进行最小割分析，将信息源S和
数据收集者DC分开的曲线称为该信息流图的割，该曲线切过的所有有向边的权值和称为割
的值。根据最大流‑最小割定理，当最小割的值不小于信息源S中的原始数据量大小时，DC能
够恢复原始数据。基于对信息流图的最小割分析，Dimakis等人给出了单节点修复带宽γ和
单节点存储量α之间的折衷曲线，所谓再生码(Regenerating Codes)即α和γ取该折衷曲线
上的点时对应的编码。在折衷曲线上存在两类特殊的点，即数据存储量α最小值点和修复带
宽γ最小值点，分别对应于：最小存储再生码(Minimum‑Storage Regenerating, MSR)，称
为MSR编码(MSR Codes)，

[0006]

[0007] 最小带宽再生码(Minimum‑Bandwidth Regenerating, MSR)，称为MBR编码(MBR Codes)，

[0008]

[0009] 再生码的修复过程如下：新建节点从完好的存储节点中任选d个存储节点下载数据，每个节点下载的数据量为β，即再生码的修复带宽 ，且修复带宽随着d的增大而
减小，这是因为随着参与修复的辅助节点数目d的增加，每个节点修复时传输的数据量β变
小，且β变小的速度比d增大的速度更快，从而使总修复带宽减小。可见再生码的修复带宽优
于RS码，但再生码的修复过程中的节点访问数d>k。另外，修复节点需要对其存储的数据执
行随机线性网络编码操作，为了满足所有编码包是相互独立的，再生码的运算需要在一个
较大的有限域内进行。

[0010] 根据节点中存储的信息是否为校验信息，可以将节点分为：

[0011] 1）系统节点(Systematic Nodes)：系统节点存储的是未经编码的原始文件信息；

[0012] 2）校验节点(Parity Nodes)：校验节点存储的是经过编码后的文件信息，也就是冗余信息。

[0013] 根据修复后的节点数据是否与原失效节点数据相同可以将修复策略分为：

[0014] 1）功能修复(Functional Repair)：该修复方案修复后的节点数据与原失效节点数据不一定相同，但修复后生成的节点与其他节点组成的分布式存储系统仍具有MDS特性；

[0015] 2）精确修复(Exact Repair)：该修复方案下修复后的节点数据原失效节点数据相同；

[0016] 3）混合修复(Hybrid Repair)：该修复方案对系统节点(存储未编码数据)进行精确修复，而对非系统节点(存储冗余数据）不需精确修复只需修复后使新的分布式系统仍满
足 MDS 特性即可。

[0017] 基于Dimakis等人提出的再生码，文献[C. Tian, B. Sasidharan, V. Aggarwal, V. A. Vaishampayan, and P. V. Kumar, “Layered exact‑repair regenerating codes 
via embedded error correction and block designs,” IEEE Trans. Inf. Theory, 
vol. 61, no. 4, pp. 1933–1947, Apr. 2015]提出了一种基于组合设计放置策略的精确
修复再生码。组合设计是一组满足某些特性的子集的集合（子集被称为区组）。一个给定的
区组设计由(X,B)指定，带有参数(r,n)，r≤n，即X是具有n个元素的集合，B是X的r元子集的
集合。在该文中主要使用了斯坦纳系(Steiner systems)和重复组合区组设计(Duplicated 
Combination Block Design, DCBD)这两种设计，实现了分布式存储系统参数限制为[n,k,
d=k=n‑1]，[n,k=n‑2,d=n‑1]和[n,k,d>k]的精确构造。这种构造比MSR码和MBR码之间的空
间共享性能更好，并且是实现这种性能的第一类编码。此外，该构造可以在参数限制为[n,
k,d=k=n‑1]的最优功能修复折衷曲线上达到不平凡的点，并且在高码率下渐近最优。但是
该文提出的构造方式对参数限制比较严格，只容许1 2个节点的失效，实用性不高。
~

发明内容

[0018] 本发明的目的之一在于提供一种再生码构造方法，该方法的构造过程简单，对参数限制更为宽松。

[0019] 本发明的目的之二在于还提供一种基于所述的再生码构造方法的文件重构方法。

[0020] 本发明的目的之三在于还提供一种基于所述的再生码构造方法的节点修复方法。

[0021] 本发明提供的这种再生码构造方法，包括如下步骤：

[0022] S1．获取组合设计和存储数据块；

[0023] S2．对区组排序并编号，统计元素出现的区组及位置，得到文件符号；

[0024] S3．对数据块进行编码，得到编码块；

[0025] S4．为每个编码块分配一个不同的文件符号；

[0026] S5．将每个元素一致的文件符号集合所对应的编码块放置在同一存储节点中，得到再生码。

[0027] 步骤S1，获取的组合设计具体为，选择满足组合条件的t‑设计 ，λ为t‑平衡数，表示任意t元子集均出现在λ个区组中，其中，

[0028] 记b为区组个数， ；

[0029] 记r为元素重复度， ；

[0030] 组合条件为：

[0031] ；

[0032] 其中，t为子集的元素数；v为设计的阶，具体为设计中不同元素的总数；m为区组容量，具体为一个区组中的元素个数；

[0033] 获取的存储数据块具体为，设存储原文件大小为M，将原文件拆分成个大小相等的数据块。

[0034] 步骤S2的文件符号设为 ，其中1≤i≤b，1≤j≤m，b为区组个数，m为区组容量；同时 表示元素h出现在第i个区组中的第j个位置；将区组编号记为B1,B2,…,Bb，对于区
组Bi，将其中的元素由小到大顺序排列，位置编号记为{1,2,…,m}。

[0035] 步骤S3具体为利用双层编码策略对数据块进行编码；外层获得的MDS码构造如下：

[0036] 利用参数为 MDS码对个数据块进行编码，获得b(m‑t+1)个编码块，其中b为区组个数，m
为区组容量，t为子集的元素数，λ为t‑平衡数，表示任意t元子集出现在λ个区组；

[0037] 内层获得的MDS码构造如下：

[0038] 将上述利用外层编码得到的b(m‑t+1)个编码块均分为b组，利用参数为(m,m‑t+1) MDS码对每组中的m‑t+1个编码块进行二次编码，最终得到bm个编码块。

[0039] 步骤S4具体包括，为上述获得的每一个编码块分配一个文件符号作为标识，不失一般性地，将 的前 个文件符号 作为外层编码生成的冗余
块的标识；将 的文件符号 作为内层编码生成的冗余块的标识，
其中， 表示元素h出现在第i个区组中的第j个位置，m为区组容量。

[0040] 步骤S5具体包括，每当发现一个文件符号 ，若其元素h与之前的文件符号不同，则分配一个新的存储节点并编号为h；对于每一个文件符号 ，若其元素h已分
配存储节点，则将元素h相同的文化符号 所对应的编码块存放到编码为h的存储节点
中，则一个存储节点存储r个编码块，r为元素重复度；得到参数为[n,k=n‑t,d=n‑t+1]的再
生码，n为节点个数，k为下载数据的个数，d为参与修复的节点个数，t为子集的元素数，
表示元素h出现在第i个区组中的第j个位置。

[0041] 本发明还提供一种包括上述再生码构造方法的文件重构方法，包括如下步骤：

[0042] A1．根据步骤S1 S5构造再生码；~

[0043] A2．连接到存储节点；

[0044] A3．在下载当前编码块时，进行重构第一次判断；

[0045] A4．在完成一个编码块的下载后，进行重构第二次判断；

[0046] A5．利用内层及外层的MDS编码规则恢复原文件。

[0047] 步骤A3的重构第一次判断具体包括，对于当前具有相同区组编号i0的文件符号，是否已经下载了m‑t+1个文件符号 所代表的编码块， 表示元素h出现在
第i0个区组中的第j个位置，m为区组容量；若判断为是，则停止下载当前编码块；若判断为
否，则下载当前编码块；

[0048] 步骤A4的重构第二次判断具体包括，判断是否已经下载了个编码块；若判断为是，则停止下载过程，若判断为否，则继续下载过程，b为区组个数，t为
子集的元素数，λ为t‑平衡数，表示任意t元子集出现在λ个区组中。

[0049] 本发明还提供了一种包括上述的再生码构造方法的节点修复方法，包括如下步骤：

[0050] B1．根据步骤S1 S5构造再生码；~

[0051] B2．确定失效节点的序号；

[0052] B3．在组合设计中确定失效节点出现过的区组序号；

[0053] B4．从n‑t+1个节点中下载编码块，共下载r(m‑t+1)个编码块，r为元素重复度，n为节点个数，t为子集的元素数，m为区组容量；

[0054] B5．将步骤B4下载的r(m‑t+1)个编码块分成r组，每组的编码块具有相同的区组编号i；

[0055] B6．对每一组编码块利用内层获得的MDS码的编码规则恢复一个编码块；将r组编码块恢复出r个编码块；

[0056] B7．将恢复出的r个编码块存储到一个新的存储节点，并将此节点加入原存储系统中完成修复过程。

[0057] 步骤B2具体为，从剩下的完好节点中对元素编号，记为{h1,...,hv‑1}，将元素编号与 设计中的元素对比，确定失效节点的序号h0；其中v为设计的阶，m为区组容
量，λ为t‑平衡数；步骤B3的区组序号记为{i1,...,ir}；步骤B4的文件符号具体为 ，表
示h0出现在第i个区组中的第j个位置， 。

[0058] 本发明提出的再生码构造方法参数限制宽松且能达到辛格尔顿上界，文件重构和节点修复过程运算简单，同时节点修复效率较高。

附图说明

[0059] 图1为现有技术中RS码修复过程示意图。

[0060] 图2为现有技术中分布式存储系统的信息流图。

[0061] 图3为本发明方法的再生码构造方法的流程示意图。

[0062] 图4为本发明方法的再生码构造方法的实施例存储编码示意图。

[0063] 图5为本发明方法的文件重构方法的流程示意图。

[0064] 图6为本发明方法的文件重构方法的实施例示意图。

[0065] 图7为本发明方法的节点修复方法的流程示意图。

[0066] 图8为本发明方法的节点修复方法的实施例示意图。

具体实施方式

[0067] 如图3为本发明方法的再生码构造方法的流程示意图。本发明提供的这种再生码构造方法，包括如下步骤：

[0068] S1．获取组合设计和存储数据块；获取的组合设计具体为，选择满足组合条件的t‑设计 ，λ为t‑平衡数，表示任意t元子集均出现在λ个区组中，其中，

[0069] 记b为区组个数， ；

[0070] 记r为元素重复度， ；

[0071] 组合条件为：

[0072]

[0073] 其中，t为子集的元素数；v为设计的阶，具体为设计中元素的种类数；m为区组容量，具体为一个区组中的元素个数；

[0074] 获取的存储数据块具体为，设存储原文件大小为M，将原文件拆分成相等大小的个数据块。

[0075] S2．对区组排序并编号，统计元素出现的区组及位置，得到文件符号；文件符号设为 ，其中1≤i≤b，1≤j≤m，b为区组个数，m为区组容量；同时 表示元素h出现在第i
个区组中的第j个位置；将区组编号记为B1,B2,…,Bb，对于区组Bi，将其中的元素先后顺序
排列，编号记为位置{1,2,…,m}。

[0076] S3．利用双层编码策略对数据块进行编码；外层获得的MDS码构造如下：

[0077] 利用参数为 MDS码对 个数据块进行编码，获得b(m‑t+1)个编码块，其中b为区组个数，m为区组容量，t为子集的元素
数，λ为t‑平衡数，表示任意t元子集出现在λ个区组；

[0078] 内层获得的MDS码构造如下：

[0079] 将上述利用外层编码得到的b(m‑t+1)个编码块均分为b组，利用参数为(m,m‑t+1) MDS码对每组中的m‑t+1个编码块进行二次编码，最终得到bm个编码块。

[0080] S4．为上述获得的每一个编码块分配一个文件符号作为标识，不失一般性地，将的前 个文件符号 作为外层编码生成的冗余块的标识；将
的文件符号 作为内层编码生成的冗余块的标识，其中， 表示
元素h出现在第i个区组中的第j个位置，m为区组容量。

[0081] S5．将每个元素一致的文件符号集合所对应的编码块放置在同一存储节点中，得到再生码。具体包括，每当发现一个文件符号 ，若其元素h与之前的文件符号 不同，
则分配一个新的存储节点并编号为h；对于每一个文件符号 ，若其元素h已分配存储节
点，则将元素h相同的文化符号 所对应的编码块存放到编码为h的存储节点中，则一个
存储节点存储r个编码块，r为元素重复度；得到参数为[n,k=n‑t,d=n‑t+1]的再生码，n为节
点个数，k为下载数据的个数，d为参与修复的节点个数，t为子集的元素数。

[0082] 在具体实施方式中，给出一个参数M=39，n=8，d=7，k=6的存储编码实例，如图4为本发明方法的再生码构造方法的实施例存储编码示意图。具体为如下步骤：

[0083] 步骤（1）、该分布式存储系统取得39个初始数据块（该处的数据块是指将原文件经过步骤S1后获得），利用步骤S3中的双层编码策略进行编码，得到56个编码块。

[0084] 该参数为[n=8,k=6,d=7] 分布式存储系统，是基于2‑(8,4,3)设计来构建的，

[0085] 2‑(8,4,3)进排序后如下：{{0,1,2,3},{0,1,2,4},{0,1,5,6},{0,2,5,7},{0,3,4,5},{0,3,6,7},{0,4,6,7},{1,2,6,7},{1,3,4,6},{1,3,5,7},{1,4,5,7},{2,3,4,7},
{2,3,5,6},{2,4,5,6}}。

[0086] 步骤（2）、统计其内元素出现的区组及位置，结果如下：

[0087] ,

[0088]

[0089] ；

[0090] 步骤（3）、为56个编码块各分配一个文件符号 ，其中 表示元素h出现在第i个区组中的第j个位置。

[0091] 步骤（4）、双层编码策略具体如下，内层编码利用参数为(4, 3)的MDS码进行编码，不失一般性地令每个区组中的最后一个文件符号所对应的编码块作为校验块，那么可得

[0092]

[0093] …

[0094]

[0095] 外层编码利用参数为(42, 39)的MDS进行编码。在本实施例中，不失一般性地令所对应的编码块作为校验块，那么可得

[0096]

[0097]

[0098] 。

[0099] 在本实施例中，为了保证校验符号之间相互独立，文件符号前的系数如x，x2，x3等为范德蒙矩阵不同行的数据。同时模加法运算均是在有限域内进行，本实施例将有限域设
置为GF（43）。

[0100] 步骤（5）、为不同的元素分配不同的存储节点，该实施例中共由0 7个元素，则需创~
建8个存储节点；将每个h一致的符号 所对应的编码块放置在同一存储节点中，那么一
个存储节点存储7个编码块，最终得到如图4所示的存储编码。

[0101] 如图5为本发明方法的文件重构方法的流程示意图。基于所述再生码构造方法的文件重构方法包括如下步骤：

[0102] A1．根据步骤S1 S5构造再生码；~

[0103] A2．连接到存储节点；

[0104] 文件重构方法主要利用步骤S3生成的外层参数为的MDS码提供的冗余信息；原始数据块数目为
，即增加了 个冗余块，因此，在文件重构过程中需要收集
个不同的编码块。在本实施方式中，最多取n‑t个存储节点，用于下载
数据。

[0105] A3．在下载当前编码块时，进行重构第一次判断；步骤A2的重构第一次判断具体包括，对于当前具有相同区组编号i0的文件符号 ，是否已经下载了m‑t+1个文件符号
所代表的编码块， 表示元素h出现在第i0个区组中的第j个位置，m为区组容量，
若判断为是，则停止下载当前编码块，若判断为否，则下载当前编码块；

[0106] A4．在完成一个编码块的下载后，进行重构第二次判断；步骤A3的重构第二次判断具体包括，判断是否已经下载了 个编码块，若判断为是，则停止下载
过程，若判断为否，则继续下载过程，b为区组个数，t为子集的元素数，λ为t‑平衡数，表示任
意t元子集均出现在λ个区组中；

[0107] A5．利用内层及外层的MDS编码规则恢复原文件；具体为已下载到个编码块时，若同一区组中编码块数目少于m‑t+1个，那么利用外层
MDS编码规则恢复编码块；若同一区组中编码块数目为m‑
t+1个，那么利用内层(m, m‑t+1) MDS编码规则恢复编码块。

[0108] 并不是每一次重构操作都需n‑t个存储节点传输数据，而是只需下载不同的编码块即可结束文件传输过程，进而开始文件重构操作。

[0109] 具体实施方式中，给出一个M=39，n=8，d=7，k=6的文件重构实例，如图6为本发明方法的文件重构方法的实施例示意图。具体说明如下：

[0110] 步骤1)、在本实施例中，连接至Node 0 Node 5这6个节点进行文件重构操作。~

[0111] 步骤2)、Node 0需下载所有数据，Node 1需下载所有数据，Node 2需下载所有数据，Node 3中下载除文件符号 对应的编码块外的所有数据，Node 4中下载除 对应
的编码块外的所有数据，Node 5中下载除 对应的编码块外的所有数据，至此共下载39
个编码块，数据下载过程结束。

[0112] 步骤3)、利用外层(42, 39)MDS编码规程进行文件恢复。由于

[0113]

[0114]

[0115]

[0116] 而从Node 0 Node 5下载的数据缺少 所代表的的的编码块，所以~
从 中消去其余编码块后结果如下：

[0117]

[0118]

[0119]

[0120] 步骤4)、编码过程中将有限域设置为GF（43），且 线性无关，那么利用上述三式能将 所代表的编码块恢复出来。那么至此，所有编码块均已得
到。

[0121] 如图7为本发明方法的节点修复方法的流程示意图，基于所述再生码构造方法的节点修复方法，包括如下步骤：

[0122] B1．根据步骤S1 S5构造再生码；~

[0123] B2．确定失效节点的序号；具体为，从剩下的完好节点中对元素编号，记为，将元素编号与 设计中的元素对比，确定失效节点的序号h0；节点修
复方法根据步骤S3的内层参数为(m,m‑t+1)的MDS码提供的冗余信息，由于内层参数为(m,
m‑t+1)的MDS码只有t‑1个数据符号作为冗余信息，因此共需下载r(m‑t+1)个编码块。

[0124] B3．在组合设计中确定失效节点出现过的区组序号，依次记为 ；

[0125] B4．从n‑t+1个节点中下载编码块，对应文件符号具体为 ， 表示h出现在第i个区组中的第j个位置，共下载r(m‑t+1)个编码块；

[0126] B5．将步骤B4下载的r(m‑t+1)个编码块分成r组，每组的编码块具有相同的区组编号i；

[0127] B6．对每一组编码块利用内层获得的MDS码的编码规则恢复一个编码块；将r组编码块恢复出r个编码块；

[0128] B7．将恢复出的r个编码块存储到一个新的存储节点，并将此节点加入原存储系统中完成修复过程。

[0129] 对于一个t‑设计 ，即共有v个不同的元素，每个区组有m个元素，任意t个元素相遇λ次（即出现在同一个区组中）。在编码过程的步骤S3中，内层参数为(m,m‑t+1)
的MDS码提供t‑1份冗余信息，那么对于属于同一个区组的编码块能容忍t‑1个编码块的失
效。进一步地，整个存储系统能容忍t个节点的失效，共失效tr个编码块，该过程中失效的编
码不能只由内层(m,m‑t+1) MDS码提供的冗余信息进行恢复，而还必须依赖于外层参数为
的MDS码来进行恢复；其中内层(m,m‑t+1)MDS码能为这
tr个失效编码块提供 份冗余信息，外层  
MDS码能为这些冗余文件提供 份冗余信息，因此利用这 份
冗余信息能恢复这失效的tr个编码块。

[0130] 在具体实施方式中，给出一个M=39，n=8，d=7，k=6的节点修复实例，如图8为本发明方法的节点修复方法的实施例示意图。具体说明如下：在本实施例中，令Node 0失效，那么
具体修复过程如下：

[0131] 步骤一、由于Node 1 Node 7节点完好，那么失效节点的元素编号为0；~

[0132] 步骤二、该分布式存储系统是基于2‑(8,4,3)设计的，那么元素0出现过的区组序号有{1,2,3,4,5,6,7}。

[0133] 步骤三、从7个存储节点中下载 所代表的文件，

[0134]

[0135] ，则共下载了21个编码块。

[0136] 步骤四、将所下载的编码块分为7组，每组中的编码块 具有相同的区组编号i，分组后如下

[0137] 。

[0138] 步骤五、对于对每一组均利用内层参数为(4, 3)的MDS码的编码规则恢复出一个编码块，例如在第1组中 ，且 已获得，那么经过异或操
作后即可恢复 。类似地对每一组均进行上述恢复操作，最终能获得
，而这正是失效节点中的编码块。

[0139] 步骤六、将上述7个编码块存储至一个新的存储节点，并将此节点加入原分布式存储系统中。至此，节点修复过程完成。

[0140] 总结本发明提出的码字与Chao Tian提出的码字相关参数，如下表所示：

[0141]

[0142] 证明利用上述编码方案生成的[n,k=n‑t,d=n‑t+1]分布式存储系统能达到辛格尔顿界，即dmin= n‑k+1，证明过程如下：

[0143] Ⅰ．根据编码过程中的步骤S5，将所有具有相同h的 所表示的编码块存储至同一节点中，那么一个节点中存储的文件数 ，r为元素重复度；并且为每一个不同的元
素h分配一个新的存储节点，那么存储系统的总节点数n=v。

[0144] Ⅱ．编码过程的步骤S3，由于存在双层MDS编码，那么该分布式系统中能存储的数据块数目 ，其中 。

[0145] Ⅲ．根据 。根据节点修复过程，一个节点失效需连接至 个节点进行修复。

[0146] Ⅳ．辛格尔顿界的左式：

[0147] 左式=n‑(n‑t)+1=t+1

[0148] 辛格尔顿界的右式：

[0149]

[0150] 由于v≥m>0，所以上式

[0151]

[0152] Ⅴ．由于编码过程的步骤S1中，选择的t‑设计需要满足的要求是，因此辛格尔顿界右式=t+1。

[0153] Ⅵ．由于左式=右式，因此证毕。