分布式存储系统中的混合冗余容错编解码方法及系统

摘要

本发明公开了一种分布式存储系统中的混合冗余容错编解码方法包括：判断当前输出网络状况的好坏；若当前输出网络状况良好，采用Reed-Solomen纠删码编码方式对数据进行编码；若当前输出网络状况不好，则采用非线性自修复码编码方式；对采用不同编码方式编码得到的数据，采用相对应的解码方式对数据进行解码。本发明还公开了一种分布式存储系统中的混合冗余容错编解码系统，包括：判断网络状况模块，Reed-Solomen纠删码编解码模块，非线性自修复码编解码模块。本发明提供的分布式存储系统中的混合冗余容错编解码方法和系统，根据不同网络状况采取不同的容错方式，降低对存储和网络带宽的要求，通过解决少量编码信息重构问题，较大程度降低丢包导致的数据重组困难。

说明书

技术领域

本发明涉及分布式存储系统技术领域，特别是指一种分布式存储系统中的混合冗余容错编解码方法及系统。

背景技术

目前常用的容错技术主要有基于复制(replication)的容错技术和基于纠删码(erasurecode)的容错技术。前者需要的存储开销巨大，后者是一类源于信道传输的编码技术，因为能够容忍多个数据帧的丢失，被引入到分布存储领域，使得基于纠删码的容错技术成为能够容忍多个数据块同时失效的、最常用的基于编码的容错技术。采用纠删码进行容错的步骤如下：

第一步，数据分块，把待存储的数据对象分割成若干大小相等的数据块；

第二步，数据块编码，对上述数据块进行编码，得到一些编码后的编码块，依据编码方式的不同可以分为Reed-Solomon码、奇偶阵列码(parityarraycode)、奇偶校验码(parity-checkcode)和低密度奇偶校验码(low-densityparity-checkcode)等类型；

其中常用的Reed-Solomon编码是一种前向纠错的信道编码，对由校正过采样数据所产生的多项式有效，编码过程首先在多个点上对这些多项式求冗余，然后将其传输或者存储，对多项式的这种超出必要值的采样使得多项式超定(过限定)，当接收器正确的收到足够的点后，它就可以恢复原来的多项式，即使接收到的多项式上有很多点被噪声干扰失真；

Reed-Solomen纠删码是目前应用最广泛的多进制码，能纠正随机错误和突发错误。其特点是：首先在相同的编码冗余度下，具有很强的纠正随机错误和突发错误的能力；其次在编码效率相同的情况下，纠错能力是最强的，可获得较大的编码增益；再次，它在短码和中等码长的情况下接近限，而且它与数据交织技术结合后，能大大提高纠突发错误的性能；最后，它具有严格的代数结构，体现为线性循环多项式。

第三步，数据解码，读取数据时只要获得任意足够数量的编码后的数据块，就可以解码得到原始数据。

基于复制的容错技术简单直观，易于实现和部署，当数据失效以后，基于复制的容错技术只需要从其他副本下载同样大小的数据即可进行修复，但需要为每个数据对象创建若干同样大小的副本，存储空间开销巨大。

纠删码容错技术针对有损信道进行信息重建，能够把多个数据块的信息融合到较少的冗余信息中。其优点是存储空间利用率高，缺点在于对数据的读写操作要分别进行编码和解码操作，导致对分布式系统的计算能力和网络要求较高，且纠删码并不重构已损编码信息；此外当数据失效以后则需要下载至少k个同样大小的数据块才能解码恢复原始数据，要占用更多的网络带宽资源，给数据中心中本来就比较紧张的带宽资源带来了巨大的压力，也给数据的读取带来很大的性能损失，维护丢失冗余的代价限制了基于纠删码的容错技术的应用和推广。

发明内容

有鉴于此，本发明的目的在于提出一种存储空间开销小、对网络带宽要求低并能够降低数据重构困难的分布式存储系统中的混合冗余容错编解码方法及系统。

基于上述目的本发明提供的分布式存储系统中的混合冗余容错编解码方法包括：

判断当前输出网络状况的好坏；

若当前输出网络状况良好，则采用Reed-Solomen纠删码编码方式对数据进行编码；

若当前输出网络状况不好，则采用非线性自修复码编码方式对数据进行编码；

对采用不同编码方式编码得到的数据，采用相对应的解码方式对数据进行解码。

在一些实施方式中，所述判断当前输出网络状况的好坏的步骤包括：

确定判断阀值，反复测试多组网络带宽和响应时间数据，算出网络状况值的平均值，以该平均值作为判断阀值，其中单次网络状况值＝网络带宽/响应时间；

对比判断当前输出网络状况好坏，将当前网络状况值与所述判断阀值比较，当前网络状况值大于所述判断阀值时，判定输出网络状况良好，当前网络状况值小于所述判断阀值时，判定输出网络状况不好。

在一些实施方式中，所述采用非线性自修复码编码方式对数据进行编码和解码的步骤包括：

数据分块，将目标数据分割成若干大小相等的数据块；

通过构建非线性多项式对数据块进行循环编码；

构建新的空间基，将每个数据块通过构建非线性多项式获得的相应编码信息在此空间基上进行映射得到编码矢量；

若编码矢量丢失，通过对数据块和编码矢量之间关系构建牛顿多项式，计算得到全部原始数据；

若编码矢量没有丢失，通过对编码矢量解码获得原始数据。

在一些实施方式中，所述所述数据分块的步骤包括：

定义目标数据分块个数N，单个数据块B_j，j∈[1,N]，j为整数；

则所述目标数据B＝{B₁,B₂,…,B_N}。

在一些实施方式中，所述通过构建非线性多项式对数据块进行循环编码步骤包括：定义码本c；

确定编码的目标是对所有数据块B_j通过码本c映射得到L维的编码矢量V＝(v₁,v₂,…,v_L)，L>N，即v_j＝c*B_j；

构建非线性多项式，其中k为网络节点的个数；

码本c＝(p(α₁),p(α₂),…,p(α_L))，其中α_i为B_i,i∈[1,N]，i为整数，中的非零元素，实现循环编码。

在一些实施方式中，所述空间基是2^M，则B＝{B₁,B₂,…,B_N}∈2^M，其中M是单个数据块的尺寸。

本发明提供还提供一种分布式存储系统中的混合冗余容错编解码系统，其特征在于，包括：

判断网络状况模块，用于判断网络状况的好坏；

Reed-Solomen纠删码编解码模块，用于网络状况良好时通过对数据进行编码、解码，恢复原始数据；

非线性自修复码编解码模块，用于网络状况不好时通过对数据进行编码、解码，恢复原始数据。

在一些实施方式中，所述判断网络状况模块包括：

响应时间测试模块，用于测试网络的响应时间；

带宽能量测试模块，用于测试网络带宽能量值，并与响应时间作比计算得出网络状况值。

在一些实施方式中，所述非线性自修复码编解码模块包括：

数据分块模块，将目标数据分割成若干大小相等的数据块；

非线性多项式循环编码模块，用于对数据块编码，获得相应的可映射数据块的编码信息；

构建空间基模块，用于将每个数据块通过相应的编码信息在该空间基上进行映射得到编码矢量；

解码模块，用于通过解码获得原始数据。

在一些实施方式中，所述解码模块包括：

牛顿多项式差值解码模块，用于所述编码矢量丢失时，通过对所述数据块和所述编码矢量关系构建牛顿多项式，计算得出全部原始数据；

编码矢量解码模块，用于所述编码矢量没有丢失时对所述编码矢量进行解码。

从上面所述可以看出，本发明提供的分布式存储系统中的混合冗余容错编解码方法和系统通过采用非线性自修复码与Reed-Solomen纠删码混合的容错方式：

在网络状况较好时，采用Reed-Solomen纠删码；

在网络状况不佳时，采用非线性自修复码，通过已损编码信息的少量本地相关编码信息或片段对其进行重构，提高维护数据冗余的效率。

采用两种编解码混合的容错技术，减少了网络传输数据量，同时也明显减少参与数据恢复运算的数据量和重建时间，可较大程度的降低丢包导致的数据重组困难。

附图说明

图1为本发明实施例提供的分布式存储系统中的混合冗余容错编解码方法示意图；

图2为本发明实施例提供的非线性自修复码编解码示意图；

图3为本发明实施例提供的分布式存储系统中的混合冗余容错编解码系统示意图；

具体实施方式

为使本发明的目的、技术方案和优点更加清楚明白，以下结合具体实施例，并参照附图，对本发明进一步详细说明。

如图1所示，本发明提供的分布式存储系统中的混合冗余容错编解码方法的一个实施例包括：

步骤101，判断当前输出网络状况的好坏

步骤102a，若当前输出网络状况良好，则采用Reed-Solomen纠删码编码方式对数据进行编码；

步骤102b，若当前输出网络状况不好，则采用非线性自修复码编码方式对数据进行编码；

步骤103，对采用不同编码方式编码得到的数据，采用相应的解码方式对数据进行解码。

采用两种编解码混合的容错技术，减少了网络传输数据量，同时能够明显减少参与数据恢复运算的数据量和重建时间。

进一步，判断当前输出网络状况的好坏的步骤101包括：

确定判断阈值，定义单次网络状况值＝网络带宽(bps)/响应时间(ms)，步骤101a，反复测试多组网络带宽(bps)能量数据，步骤101b，反复测试多组响应时间(ms)数据，通过计算得到多个网络状况值，算出网络状况值的平均值，以该平均值作为判断阈值；

对比判断当前输出网络状况好坏，将当前网络状况值与所述判断阈值比较，当前网络状况值大于所述判断阈值时，判定输出网络状况良好，当前网络状况值小于所述判断阈值时，判定输出网络状况不好。

更进一步，如图2所示，当网络状况不好，采用非线性自修复码编码方式对数据进行编码和解码的步骤包括：

步骤201，数据分块，将目标数据分割成若干大小相等的数据块，定义码本c，定义目标数据分块个数N，数据块B_j，j∈[1,N]，j是整数，则全部编码数据B＝{B₁,B₂,…,B_N}，通常一个网络数据包的结构包括版本号、包头长度等信息。B_j数据块是将除了信息之外的数据部分平均分割，简单说就是矩阵。例如共1024B数据，平分成4块，就是按顺序每256B视作一块B_j，网络共有K个节点。

步骤202，通过构建非线性多项式对所述数据块进行循环编码，确定编码的目标是对每个数据块B_j，通过一个相同的码本c映射得到L维的编码矢量V＝(v₁,v₂,…,v_L)，其中L>N，即v₁＝c*B₁，v_j＝c*B_j，码本c通过非线性多项式计算得到；

p定义为c＝(p(α₁),p(α₂),…,p(α_L))，其中k为网络节点的个数，其中α_i为B_i,i∈[1,N]，i为整数，中的非零元素，则α_i也是矩阵。

步骤203，对全部数据块构建新的空间基为2^M，则有B＝{B₁,B₂,…,B_N}∈2^M，M为单个数据块的尺寸，将每个数据块B_j通过上一步计算得到的相应的码本c在所述空间基上进行映射，得到L维的编码矢量V＝(v₁,v₂,…,v_L)。

步骤204，一般情况下，通过码本c，对从编码端获得的编码矢量V＝(v₁,v₂,…,v_L)，进行解码，得到每个数据块B′_j＝c·v_j，其中B′_j为解码端与B_j相对应的数据块，在编码矢量没有任何丢失的情况下B′_j＝B_j。步骤205，在网络状况不好的条件下，编码矢量V可能会丢失，因此需要通过牛顿多项式插值进行相应部分的解码。假设某个编码矢量v_i丢失，则对L维的编码矢量V＝(v₁,v₂,v_i-1,v_i+1…,v_L)进行牛顿多项式插值来解码的具体方法为：

将所述数据块和所述编码矢量之间的关系用n次牛顿多项式表示为：

$>\left(\begin{array}{c}{B^{\prime }}_n\left(x\right)=c·\{a_1\left(x-v_1\right)+a_2\left(x-v_1\right)\left(x-v_2\right)+\mathrm{...}\\ +a_i\left(x-v_1\right)\left(x-v_2\right)\mathrm{...}\left(x-\frac{v_{i-1}+v_{i+1}}{2}\right)\mathrm{...}\\ +a_n\left(x-v_1\right)\left(x-v_2\right)\mathrm{...}\left(x-v_n\right)\}\end{array}\right)$>

其中a₁…a_n，为待求解系数，n∈[1,N]，n为整数，n为B′_n的个数，B′_n(x)表示编码矢量为x时对应的数据块，则有：

$>a_1=\frac{c·v_2-c·v_1}{v_2-v_1}$>

$>{\alpha }_2=\frac{\frac{c·v_3-c·v_1}{v_3-v_1}-\frac{c·v_2-c·v_1}{v_2-v_1}}{v_3-v_1}$>

..........

以此类推可以得到全部a_n，代入上式可以得到B′_n的全部值。如图3所示，本发明还提供分布式存储系统中的混合冗余容错编解码系统包括：

判断网络状况模块301，用于判断网络状况的好坏；

非线性自修复码编解码模块302，用于网络状况不好时通过对数据进行编码、解码，恢复原始数据；

Reed-Solomen纠删码编解码模块303，用于网络状况良好时通过对数据进行编码、解码，恢复原始数据。

在一些实施方式中，判断网络状况模块301包括：

响应时间测试模块301a，用于测试网络的响应时间；

带宽能量测试模块301b，用于测试网络带宽能量值，并与所述响应时间作比计算得出网络状况值。

在一些实施方式中，非线性自修复码编解码模块302包括：

数据分块模块302a，用于将目标数据分割成若干大小相等的数据块；

非线性多项式循环编码模块302b，用于对所述数据块编码，获得相应的可映射所述数据块的编码信息；

构建空间基模块302c，用于将每个数据块通过相应的所述编码信息在所述空间基上进行映射得到编码矢量；

解码模块302d，用于通过解码获得原始数据。

在一些实施方式中解码模块302d包括：

牛顿多项式差值解码模块302d₁，用于所述编码矢量丢失时，通过对所述数据块和所述编码矢量关系构建牛顿多项式，计算得出全部原始数据；

编码矢量解码模块302d₂，用于所述编码矢量没有丢失时对所述编码矢量进行解码。

从上面所述可以看出，本发明提供的分布式存储系统中的混合冗余容错编解码方法和系统通过采用两种编解码混合的容错技术和判断网络状况模块、Reed-Solomen纠删码编解码模块、非线性自修复码编解码模块减少了网络传输数据量，同时参与数据恢复运算的数据量和重建时间能够明显减少。

采用牛顿多项式差值解码模块，通过已损编码信息的少量本地相关编码信息或片段对其进行重构，提高维护数据冗余的效率，解决少量丢失编码信息重构问题，可较大程度的降低丢包导致的数据重组困难。

所属领域的普通技术人员应当理解：以上任何实施例的讨论仅为示例性的，并非旨在暗示本公开的范围(包括权利要求)被限于这些例子；在本发明的思路下，以上实施例或者不同实施例中的技术特征之间也可以进行组合，并存在如上所述的本发明的不同方面的许多其它变化，为了简明它们没有在细节中提供。因此，凡在本发明的精神和原则之内，所做的任何省略、修改、等同替换、改进等，均应包含在本发明的保护范围之内。