一种由极大距离可分存储码生成最小存储再生码的一般方法

摘要

本发明公开了一种由极大距离可分存储码生成最小存储再生码的一般方法，所得的最小存储再生码适用于分布式存储系统。该转换方法所基于的极大距离可分存储码是非二元的，转换过程不改变原存储码的字母表大小。若该转换方法所基于的极大距离可分存储码的系统节点具有最佳存取性质，则转换后得到的最小存储再生码具有最佳存取性质。本发明有益效果是：（I）系统的存储开销非常小；（II）任意一个失效节点都能被最佳修复，修复失效节点的过程中只消耗最小的带宽资源；（III）若采用系统节点具有最佳I/O修复性质的MDS存储码作为基码,修复失效节点时I/O开销也最小。

说明书

技术领域

本发明涉及分布式存储系统领域，特别涉及一种适用于分布式存储系统的将 系统节点具有最佳修复性质的极大距离可分存储码转换成最小存储再生码的编码 技术。

背景技术

为提高分布式存储系统的可靠性，冗余是不可或缺的。一般来说，有两种增 加冗余的机制：复制和纠删。与重复码相比，在冗余量相同的情况下纠删码能提 供更多的可靠性，所以更具优势。而在所有的纠删码中，极大距离可分(MDS)码如 Reed-Solomon码因为在冗余量相同的情况下具有最大的纠删错误能力，被广泛用 于GoogleColossus、MicrosoftAzure等多个分布式云存储系统。通常，将源文件 均分成k份，采用一个(k+r,k)的MDS码进行编码后得到k+r份数据，然后分别 存放在k+r个独立的存储设备上，这些设备也被称为节点。

但是对于大型分布式云存储系统，各个节点的可靠性不高，失效现象经常发 生，节点失效会增加数据丢失的可能性、降低系统的可靠性，而其中单节点失效 高达98.08％。为了维持一定的冗余量，系统会频繁地进行节点修复，常用的修复 方式是从其它存活的节点中下载数据以修复该失效节点，这些节点也被称之为帮 助节点。在修复过程中，所下载数据的量被称为修复带宽，实际系统中为降低开 销，修复带宽应该最小化。然而，传统MDS存储码的修复方法是连接任意k个帮 助节点下载全部数据，从而重构源文件，然后再编码产生失效节点里的数据，相 应的修复带宽最大，这给分布式存储系统带来极大的开销。

文献"Networkcodingfordistributedstoragesystems,IEEETrans。onInformation Theory,vol。56,no。9,pp。4539-4551,September2010(基于网络编码的分布式存 储系统，IEEE信息论汇刊，第56卷，第9期，第4539-4551页，2010年9月)" 确定了存储编码的最小修复带宽，达到最小修复带宽的节点被称为具有最佳修复 性质，所有节点都具有最佳修复性质被称之为再生码，其中最重要是两类编码： 最小存储再生(MSR)码和最小修复带宽再生(MBR)码。

具体地，MSR编码将一份大小为kN个元素的源文件均分成k份，每份包含N 个元素，用长度为N的列向量f_i表示，0≤i<k.对原始数据编码后得到r份校验 数据，同样用长度为N的列向量f_i表示，k≤i<k+r。将这k+r份数据分别存放在 一个包含在k+r个节点的分布式存储系统中。一个(k+r,k)MSR码具有：(1)MDS 性质，即连接任意k个节点可以重构源文件，参见附图1；(2)最佳修复性质，即 一个失效节点的修复带宽为γ＝dN/(d-k+1)，这可以通过连接d(k≤d≤k+r-1)个帮 助节点个数，从每个帮助节点中下载N/(d-k+1)个元素实现，如附图2所示。

特别需要指出，上述文献中所构造的存储码是功能修复码，即代替失效节点 的新节点存储的数据可以与失效节点原来的数据不一样但在功能上等价；然而， 要求代替失效节点的新节点存储的数据与失效节点原来的数据完全一样的精确修 复MSR码，能在实际应用中减小系统的复杂度，因而更受实际系统欢迎。此外， 目前已知的精确修复MSR码都考虑d＝k+r-1的情形来最大的减小修复带宽。本 发明也考虑这一种情况。

实际的分布式存储系统通常要求所采用的MSR码的码率k/(k+r)尽可能地大以 减少存储开销，但是目前只有4类这样的MSR码，如"Repairoptimalerasurecodes throughhadamarddesigns,IEEETrans。onInformationTheory,vol。59,no。5,pp。 3021-3037,May2013(基于hadamard设计的最佳修复纠删码，IEEE信息论汇刊， 第59卷，第5期，第3021-3037页，2013年5月)"等等中的构造。此外，目前 存在一些对于码率大于1/2的MDS存储码，如文献"Aframeworkofconstructionsof minimalstorageregeneratingcodeswiththeoptimalaccess/updateproperty,IEEE Trans。onInformationTheory,vol。61,no。4,pp。1920-1932,April2015(一个具有 最佳存取/更新性质的MSR码的构造框架，IEEE信息论汇刊，第61卷，第4期， 第1920-1932页，2015年4月)"等等中的构造。而这类MDS存储码只能最佳修 复系统节点而不能最佳修复校验节点。

发明内容

本发明的目的在于提供一种由系统节点具有最佳修复性质的MDS存储码转换 成MSR码的一般方法。

本发明的上述目的这样实现的，一种将系统节点具有最佳修复性质的MDS存 储码转换成MSR码的一般方法，包括以下步骤：

(1)选择系统节点具有最佳修复性质的节点容量为N的(k+r,k)MDS存储码 C₁作为基码；

(2)产生r个码C₁的实例，得到节点容量为rN的(k+r,k)MDS存储码C₂；

(3)利用r个置换分别对C₂中每个实例的校验节点进行置换从而得到节点 容量为rN的(k+r,k)MDS存储码C₃；

(4)对于0≤j≠l<r，将C₃实例j节点l上的数据与实例l节点j上的数据 做两个线性无关的线性组合并分别代替C₃中实例j节点l与实例l节点 j的数据，从而得到节点容量为rN的(k+r,k)MSR码C₄。

在本发明的将系统节点具有最佳修复性质的MDS存储码转换成MSR码的一 般方法中，所述的基码C₁是非二元的。

在本发明的将系统节点具有最佳修复性质的极大距离可分存储码转换成MSR 码的一般方法中，所述的r个置换是{0,1,…,r-1}上的置换。

在本发明的将系统节点具有最佳修复性质的极大距离可分存储码转换成MSR 码的一般方法中，在修复基码C₁和MSR码C₄的某个存储节点时，所连接的帮助 节点个数为k+r-1。

在本发明的将系统节点具有最佳修复性质的极大距离可分存储码转换成MSR 码的一般方法中，中间产生的码C₂，C₃和转换后的码C₄，其系统节点存储的数据 完全一样。

在本发明的将系统节点具有最佳修复性质的极大距离可分存储码转换成MSR 码的一般方法中，修复所述的MSR码C₄的系统节点j时，修复方法与作为基码 C₁的MDS存储码对应的节点j时修复方法相同.

在本发明的将系统节点具有最佳修复性质的极大距离可分存储码转换成MSR 码的一般方法中，修复所述的MSR码的校验节点j时，下载剩下k+r-1的节点中 的第rj到rj+r-1个元素。

本发明有益效果是：(I)系统的存储开销非常小；(II)任意一个失效节点都 能被最佳修复，修复失效节点的过程中只消耗最小的带宽资源；(III)若采用系统 节点具有最佳I/O修复性质的MDS存储码作为基码,修复失效节点时I/O开销也 最小。

下面结合附图对本发明进行详细说明。

附图说明

图1是采用MDS码的分布式存储系统的编码、存储、重构源文件、修复单个 节点的示意图；

图2是现有技术中MSR码的修复单个节点失效的示意图；

图3是现有技术中MSR码存储节点的数据示意图；

图4是本发明过程中间码C₂存储节点的数据示意图；

图5是本发明过程中间码C₃校验节点的数据示意图；

图6是本发明生成的MSR码C₄校验节点的数据示意图；

图7是本发明产生的MSR码的一个例子；

图8是本发明生成MSR码C₄产生的流程图。

具体实施方式

本发明所提出的MSR码，由系统节点具有最佳修复性质的节点容量为N的 (k+r,k)MDS存储码C₁转换而来。

假定采用码C₁的存储系统的系统节点与校验节点所存储的数据分别为f_i′，0≤ i<k和g_j′，0≤j<r，其中f_i′是长度为N的列向量，A_i,i是N阶非 奇异方阵，且系统节点i的数据f_i′可通过下载S_i,jf_j′，0≤j≠i<k和S_i,k+lg_l′，0≤l< r恢复出来，其中S_i,j和S_i,k+l是N/r×N的矩阵。则所提出的MSR码的生成与修复、 重构按下述方法进行.

MSR码的生成：

1.把一份大小为krN的文件分成r份子文件，每份子文件的大小为kN，对每 一份子文件都按照基码C₁编码方式进行编码得到r个实例，这些实例构成节点容 量为rN的(k+r,k)MDS存储码，记为C₂，记子文件l编码后存放在系统节点i和 校验节点j上的数据分别为和其中0≤l，j<r，0≤i<k，则可以通过0≤j≠i<k和0≤s<r恢复出来。C₂码的结构见附图4。

2.产生r个{0,1,…,r-1}上的置换，记为p₀，p₁，。。。，p_r-1。对于上一步骤中 的矩阵S_i,j，(a)若对任意的0≤i<k，存在矩阵S_i使得S_i,j＝S_i对所有的0≤j≠i< k+r都成立，则这r个置换是任意的{0,1,…,r-1}上的置换；(b)否则这r个置换 需满足

p_i(j)＝p_j(i),0≤i，j<r，

这里p_l将作用在实例l上的r个校验点中数据，0≤l<r。

保持码C₂中校验数据系统节点的数据不变，仅通过上述置换调整其校验数据 的位置来生成码C₃，记码C₃实例l中存放在校验节点j上的数据为其中0≤ l，j<r，

$h_j^{\left(l\right)}=g_{p_l\left(j\right)}^{\left(l\right)},0\le l,j<r,$

码C₃校验节点的结构见附图5。

3.通过仅修改码C₃中的校验数据来生成节点容量为rN的(k+r,k)MSR码C₄， 记码C₄校验节点j上存放的数据为

$f_{k+j}=\left(\begin{array}{c}{f}_{k+j}^{\left(0\right)}\\ .\\ .\\ .\\ f_{k+j}^{(r-1)}\end{array}\right),0\le j<l,$

其中是一个长度为N的列向量，通过码C₃中的校验数据按以下方式 得到

其中

{θ_j,l,θ_l,j}＝{1,a},0≤j≠l＜r,a∈F_q{0,1}。

MSR码C₄校验节点的结构见附图6。

MSR码的修复：

1.修复MSR码C₄的系统节点i(0≤i<k)的数据f_i时，下载和 0≤s<k，0≤j,l<r。

(a)若对任意的0≤i<k，存在矩阵S_i使得S_i,j＝S_i对所有的0≤j≠i<k+r都 成立，则可根据

$\left(\begin{array}{c}{S}_i{f}_{k+j}^{\left(l\right)}={\theta }_{j,l}{S}_i{h}_j^{\left(l\right)}+S_i{h}_l^{\left(j\right)}\\ S_i{f}_{k+l}^{\left(j\right)}={\theta }_{l,j}{S}_i{h}_l^{\left(j\right)}+S_i{h}_j^{\left(l\right)}\end{array}\right)$

和

得到0≤j,l<r，再根据是的置换可进一步得到0 ≤j,l<r，从而通过基码C₁的系统节点i的修复方法可恢复出f_i。

(b)若不然，对0≤j≠l<r，根据

$\left(\begin{array}{c}{S}_{i,k+p_l\left(j\right)}{f}_{k+j}^{\left(l\right)}={\theta }_{j,l}{S}_{i,k+p_l\left(j\right)}{h}_j^{\left(l\right)}+S_{i,k+p_l\left(j\right)}{h}_l^{\left(j\right)}={\theta }_{j,l}{S}_{i,k+p_l\left(j\right)}{g}_{p_l\left(j\right)}^{\left(l\right)}+S_{i,k+p_l\left(j\right)}{g}_{p_j\left(l\right)}^{\left(j\right)}\\ S_{i,k+p_j\left(l\right)}{f}_{k+l}^{\left(j\right)}={\theta }_{l,j}{S}_{i,k+p_j\left(l\right)}{h}_l^{\left(j\right)}+S_{i,k+p_j\left(l\right)}{h}_j^{\left(l\right)}={\theta }_{l,j}{S}_{i,k+p_j\left(l\right)}{g}_{p_j\left(l\right)}^{\left(j\right)}+S_{i,k+p_j\left(l\right)}{g}_{p_l\left(j\right)}^{\left(l\right)}\end{array}\right)$

以及p_l(j)＝p_j(l)可得到0≤j≠l<r，结合0≤l<r，因为 p₀，p₁，。。。，p_r-1是置换，它们对应着所有的0≤j,l<r，从而通过基码C₁的系统节点i的修复方法可恢复出f_i。

2.修复MSR码C₄的校验节点j(0≤j<r)的数据f_k+j时，通过下载0≤l ≠j<r和0≤i<k，可利用

$\begin{array}{cc}{f}_{k+j}^{\left(l\right)}={\theta }_{j,l}{f}_{k+l}^{\left(j\right)}-(a-1)\underset{i=0}{\overset{k-1}{\Sigma }}{A}_{p_j\left(l\right),i}{f}_i^{\left(j\right)},& 0\le l\ne j<r\end{array},$

和

$f_{k+j}^{\left(j\right)}=\underset{i=0}{\overset{k-1}{\Sigma }}{A}_{p_j\left(j\right),i}{f}_i^{\left(j\right)},0\le j<r$

计算出0≤l<r，即f_k+j。

MSR码的重构：

1。若连接k个系统节点，则可得到源文件。

2.若连接k-1个系统节点和1个校验节点，假定i是没有被连接到的系统节 点，j是已连接到的校验节点,其中0≤i<k,0≤j<r，则f_i可以通过以下步骤计 算：

(a)利用从系统节点连接到的数据0≤l≠i<k和从校验节点连接到的数 据结合码C₁的MDS性质，可计算出进一步可计算出0≤s<r，从而可得0≤s<r。

(b)对所有的0≤s≠j<r，根据已连接的数据和在步骤(a)中计算出的通过计算出即则利用从系统节点已连接的数据0≤j≠i<k以及刚得到的结合码C₁的MDS性质，可计算出这样就 得到了k个系统节点上的全部数据，从而重构出源文件.

3。若连接k-t个系统节点和t个校验节点，其中1<t<r,假定是没 有被连接到的系统节点，是已连接到的校验节点，其中 0≤i₀＜…＜i_t-1＜k,0≤j₀＜…＜j_t-1＜r。令

I＝{i₀,i₁,…i_t-1},J＝{j₀,j₁,…j_t-1}

则可以通过以下步骤算出：

(a)对u,s∈J且u≠s通过方程组

$\left(\begin{array}{c}{f}_{k+u}^{\left(s\right)}={\theta }_{u,su}{h}^{\left(s\right)}+h_s^{\left(u\right)}\\ f_{k+s}^{\left(u\right)}={\theta }_{s,u}{h}_s^{\left(u\right)}+h_u^{\left(s\right)}\end{array}\right)$

计算出再根据即对任意的s∈J，已得到即u∈J。

(b)若s∈J,根据步骤(a)中得到的u∈J以及从系统节点连接到的数据 i∈{0,1,…,k-1}J，结合码C₁的MDS性质，可计算出系统数据从而能计算出即对所有的l∈{0,1,…,r-1}J。

(c)若，根据上一步骤中得到的以及从校验节点连接到的数据通 过计算出即s∈J，再结合从系统节点连接的数据 i∈{0,1,…,k-1}I以及码C₁的MDS性质，可计算出系统数据

具体实施例

给定r＝3，令和分别表示一个系统节点具有最佳修复性 质的节点容量为N的(k+3,k)MDS存储码C1的一个实例，0≤l<3。且系统数据可通过0≤s<k，0≤j<3来恢复。经过步骤1-3之后，可得到 如图7所示的节点容量为rN的(k+3,k)MSR码。这里步骤2中的置换设置为

p_i(j)＝(i+j)mod3,0≤i,j＜3。

参看图7，若连接节点2到节点k+1来重构源文件，从波浪线标出的数据中， 可以得到和与下划线标出的数据以及系统节点的数据 2≤i＜k再结合基码的MDS性质算出i＝0,1。根据这些数据进 一步计算出和最后从虚线标出的数据中减掉和之后得到和 结合系统节点的数据2≤j＜k以及基码的MDS性质可以算出到此，源文件重构完毕。通过连接其他k个节点来重构源文件的情况类似。

参看图7，若修复系统节点i，0≤i＜k，通过下载0≤j,l<3可以 算出0≤j,l<3，再根据基码的修复规则恢复系统节点i。

参看图7，若修复校验节点0，下载0≤j≠k＜k+3。根据和 基码的编码规则计算出即再通过

$\left(\begin{array}{c}{f}_k^{\left(1\right)}={\mathrm{ag}}_1^{\left(1\right)}+g_1^{\left(0\right)}={\mathrm{af}}_{k+1}^{\left(0\right)}-(a-1)g_1^{\left(0\right)}\\ f_k^{\left(2\right)}={\mathrm{ag}}_2^{\left(2\right)}+g_2^{\left(0\right)}={\mathrm{af}}_{k+2}^{\left(0\right)}-(a-1)g_2^{\left(0\right)}\end{array}\right)$

可以算出即校验节点0可以被修复。类似的，校验节点i可以通过下载 0≤j≠k+i＜k+3来修复。

参看图4，它是一个以系统节点具有最佳修复性质的节点容量为N的(k+r, k)MDS存储码C₁作为基码，合成该基码的r个实例得到的节点容量为rN的(k+r, k)MDS存储码C₂的结构示意图。

参看图5，它是将图4的存储码C₂，即r个存储码C₁的实例中的每个实例中 存放在校验节点上的数据做一个置换，而得到的节点容量为rN的(k+r,k)MDS存 储码C₃的校验节点结构示意图。

参看图6，它给出了图5中MDS存储码C₃中校验节点数据的修改规则，经 过该修改后得到新的节点容量为rN的(k+r,k)MSR码C₄的校验节点结构示意图。

参看图8，它给出了本发明生成MSR码C₄的流程图。