一种数据编码方法、系统、设备以及介质与流程

1.本发明涉及raid领域，具体涉及一种数据编码方法、系统、设备以及存储介质。


背景技术：

2.raid主要利用数据条带、数据校验和镜像技术来获得较强的性能、更高的可靠性、较好的容错能力和较强的扩展性。根据不同的数据应用需求，可以运用或者组合运用这三种技术的策略和架构，所以按照不同的策略和架构，raid可以被分为不同的等级：raid 0,1,5,6,10。
3.其中，raid 0是最早出现的raid模式，即data stripping数据分条技术。raid 0是组建磁盘阵列中最简单的一种形式，只需要2块以上的硬盘即可，成本低，可以提高整个磁盘的性能和吞吐量。raid 0没有提供冗余或错误修复能力，但实现成本是最低的。
4.raid 0最简单的实现方式就是把n块同样的硬盘用硬件的形式通过智能磁盘控制器或用操作系统中的磁盘驱动程序以软件的方式串联在一起创建一个大的卷集。在使用中电脑数据依次写入到各块硬盘中，它的最大优点就是可以整倍的提高硬盘的容量。如使用了三块80gb的硬盘组建成raid 0模式，那么磁盘容量就会是240gb。其速度方面，和单独一块硬盘的速度完全相同。最大的缺点在于任何一块硬盘出现故障，整个系统将会受到破坏，可靠性仅为单独一块硬盘的1/n。
5.raid 1称为磁盘镜像，原理是把一个磁盘的数据镜像到另一个磁盘上，也就是说数据在写入一块磁盘的同时，会在另一块闲置的磁盘上生成镜像文件，在不影响性能情况下最大限度的保证系统的可靠性和可修复性上，只要系统中任何一对镜像盘中至少有一块磁盘可以使用，甚至可以在一半数量的硬盘出现问题时系统都可以正常运行，当一块硬盘失效时，系统会忽略该硬盘，转而使用剩余的镜像盘读写数据，具备很好的磁盘冗余能力。虽然这样对数据来讲绝对安全，但是成本也会明显增加，磁盘利用率为50％，以四块80gb容量的硬盘来讲，可利用的磁盘空间仅为160gb。另外，出现硬盘故障的raid系统不再可靠，应当及时的更换损坏的硬盘，否则剩余的镜像盘也出现问题，那么整个系统就会崩溃。更换新盘后原有数据会需要很长时间同步镜像，外界对数据的访问不会受到影响，只是这时整个系统的性能有所下降。因此，raid 1多用在保存关键性的重要数据的场合。
6.raid 5(分布式奇偶校验的独立磁盘结构)。它的奇偶校验码存在于所有磁盘上，其中的p0代表第0带区的奇偶校验值，其它的意思也相同。raid 5的读出效率很高，写入效率一般，块式的集体访问效率不错。因为奇偶校验码在不同的磁盘上，所以提高了可靠性。但是它对数据传输的并行性解决不好，而且控制器的设计也相当困难。对于raid 5来说，大部分数据传输只对一块磁盘操作，可进行并行操作。在raid 5中有“写损失”，即每一次写操作，将产生四个实际的读/写操作，其中两次读旧的数据及奇偶信息，两次写新的数据及奇偶信息。
7.raid 5只有一个parity stripe，一般命名为p。当进行编码时，设需要编码的数据分为n个stripe，每个命名为dn，则其关系表示为：
[0008][0009]
raid 5通过上式的设置，可以通过一个parity p实现上述任意一个数据块(d和p)发生错误时都可以进行纠错。
[0010]
raid 6是带两种分布存储的奇偶校验码独立磁盘结构。它是对raid 5的扩展，主要是用于要求数据绝对不能出错的场合。由于引入了第二种奇偶校验值，所以需要n+2个磁盘，同时对控制器的设计变得十分复杂，进一步提升了磁盘阵列的数据可靠性。需要更多的空间来存储校验值，同时在写操作中具有更高的性能损失。
[0011]
实现raid 6时需要同时支持两个parity strip：p和q，举例其关系为：
[0012][0013]
通过上式的设置，raid 6可以通过两个parity：p和q。当上述任意一个或两个数据块(d，p和q)发生错误时，都可进行纠错。
[0014]
然而在谷歌的分布式云服务器工作统计《availability in globally distributed storage systems》里提到，在现今的分布式云服务器工作环境中有37％的可能会出现同时有两个以上错误需要纠错的环境。这时普通的raid6就无法满足需求。


技术实现要素：

[0015]
有鉴于此，为了克服上述问题的至少一个方面，本发明实施例提出一种数据编码方法，包括以下步骤：
[0016]
获取预先配置的纠删位数以及数据盘的数量；
[0017]
根据所述纠删位数和所述数据盘的数量生成纠删矩阵，其中纠删矩阵的第一行中前纠删位数的元素的值为1，其余值为0，其余行在所述第一行的基础上将前纠删位数的元素向右依次平移一位得到；
[0018]
将所述纠删矩阵和数据盘中的数据块矩阵相乘以得到检验块；
[0019]
将校验块保存到相应的数据盘。
[0020]
在一些实施例中，还包括：
[0021]
响应于若干个数据块错误，利用所述纠删矩阵和所述校验块恢复错误的若干个数据块。
[0022]
在一些实施例中，利用所述纠删矩阵和所述校验块恢复错误的若干个数据块，进一步包括：
[0023]
根据错误的数据块的位置从所述纠删矩阵中搜索对应列并组成恢复矩阵；
[0024]
从所述恢复矩阵按照预设规则选择若干行并确定选择的行对应的校验块；
[0025]
将所述恢复矩阵进行消元运算以得到单位矩阵，并利用对应的校验块执行同样的消元运算以得到恢复后的若干个数据块。
[0026]
在一些实施例中，从所述恢复矩阵按照预设规则选择若干行，进一步包括：
[0027]
从第一行开始选择含有1的行，并顺序向下，直至选择得到的每列都具有1，且各行之间不同。
[0028]
基于同一发明构思，根据本发明的另一个方面，本发明的实施例还提供了一种数
据编码系统，包括：
[0029]
获取模块，配置为获取预先配置的纠删位数以及数据盘的数量；
[0030]
生成模块，配置为根据所述纠删位数和所述数据盘的数量生成纠删矩阵，其中纠删矩阵的第一行中前纠删位数的元素的值为1，其余值为0，其余行在所述第一行的基础上将前纠删位数的元素向右依次平移一位得到；
[0031]
计算模块，配置为将所述纠删矩阵和数据盘中的数据块矩阵相乘以得到检验块；
[0032]
保存模块，配置为将校验块保存到相应的数据盘。
[0033]
在一些实施例中，还包括恢复模块，配置为：
[0034]
响应于若干个数据块错误，利用所述纠删矩阵和所述校验块恢复错误的若干个数据块。
[0035]
在一些实施例中，恢复模块还配置为：
[0036]
根据错误的数据块的位置从所述纠删矩阵中搜索对应列并组成恢复矩阵；
[0037]
从所述恢复矩阵按照预设规则选择若干行并确定选择的行对应的校验块；
[0038]
将所述恢复矩阵进行消元运算以得到单位矩阵，并利用对应的校验块执行同样的消元运算以得到恢复后的若干个数据块。
[0039]
在一些实施例中，恢复模块还配置为：
[0040]
从第一行开始选择含有1的行，并顺序向下，直至选择得到的每列都具有1，且各行之间不同。
[0041]
基于同一发明构思，根据本发明的另一个方面，本发明的实施例还提供了一种计算机设备，包括：
[0042]
至少一个处理器；以及
[0043]
存储器，所述存储器存储有可在所述处理器上运行的计算机程序，其特征在于，所述处理器执行所述程序时执行如上所述的任一种数据编码方法的步骤。
[0044]
基于同一发明构思，根据本发明的另一个方面，本发明的实施例还提供了一种计算机可读存储介质，所述计算机可读存储介质存储有计算机程序，所述计算机程序被处理器执行时执行如上所述的任一种数据编码方法的步骤。
[0045]
本发明具有以下有益技术效果之一：本发明提出的方案能够对纠删位数可配置，并根据不同的纠删位数配置校验条带的生成方式，不同错误纠错需求下，并不需要经过复杂的解码运算，仅需要调用不同的数据块进行异或即可得到相应的恢复。
附图说明
[0046]
为了更清楚地说明本发明实施例或现有技术中的技术方案，下面将对实施例或现有技术描述中所需要使用的附图作简单地介绍，显而易见地，下面描述中的附图仅仅是本发明的一些实施例，对于本领域普通技术人员来讲，在不付出创造性劳动的前提下，还可以根据这些附图获得其他的实施例。
[0047]
图1为本发明的实施例提供的数据编码方法的流程示意图；
[0048]
图2为本发明的实施例提供的数据编码系统的结构示意图；
[0049]
图3为本发明的实施例提供的计算机设备的结构示意图；
[0050]
图4为本发明的实施例提供的计算机可读存储介质的结构示意图。
具体实施方式
[0051]
为使本发明的目的、技术方案和优点更加清楚明白，以下结合具体实施例，并参照附图，对本发明实施例进一步详细说明。
[0052]
需要说明的是，本发明实施例中所有使用“第一”和“第二”的表述均是为了区分两个相同名称非相同的实体或者非相同的参量，可见“第一”“第二”仅为了表述的方便，不应理解为对本发明实施例的限定，后续实施例对此不再一一说明。
[0053]
根据本发明的一个方面，本发明的实施例提出一种数据编码方法，如图1所示，其可以包括步骤：
[0054]
s1，获取预先配置的纠删位数以及数据盘的数量；
[0055]
s2，根据所述纠删位数和所述数据盘的数量生成纠删矩阵，其中纠删矩阵的第一行中前纠删位数的元素的值为1，其余值为0，其余行在所述第一行的基础上将前纠删位数的元素向右依次平移一位得到；
[0056]
s3，将所述纠删矩阵和数据盘中的数据块矩阵相乘以得到检验块；
[0057]
s4，将校验块保存到相应的数据盘。
[0058]
本发明提出的方案能够对纠删位数可配置，并根据不同的纠删位数配置校验条带的生成方式，不同错误纠错需求下，并不需要经过复杂的解码运算，仅需要调用不同的数据块进行异或即可得到相应的恢复。
[0059]
在一些实施例中，在步骤s2中，可以根据当前配置的纠删位数生成纠删矩阵，然后在与数据盘中的数据块相乘即可得到校验块。
[0060]
例如，基于数据位数d(即数据盘的数量)构建编码矩阵m。以有6个数据块进行编解码运算为例，则需要构建一个6*6的矩阵，如下所示：
[0061][0062]
在数据块矩阵m中，每一列代表一个数据盘中的数据块，例如第一列代表数据盘1的数据块序列d0，依次类推，第二列代表数据盘2的数据块序列d1，第三列代表数据盘3的数据块序列d2，第四列代表数据盘4的数据块序列d3，第五列代表数据盘5的数据块序列d4，第六列代表数据盘6的数据块序列d5。
[0063]
然后根据配置的纠删位数生成纠删矩阵，即基于需要纠错的个数n，在m矩阵中顺序填1。顺序的方式为：从第一行连续填入n个1，然后从第二行起隔1个0，顺序填入n个1，第三行起，隔2个0，顺序填入n个1，并依次类推，完成整个m矩阵的构建。
[0064]
例如对于上述m矩阵编码后得到的纠删矩阵为：
[0065][0066]
在一些实施例中，若配置的纠删位数为5，则所得到的纠删矩阵为：
[0067][0068]
最后，利用纠删矩阵和d序列进行矩阵乘加运算，得到编码的parity序列。
[0069][0070]
其中，第一行代表第一校验块，即这样得到的6个parity stripe的pi，可以恢复d和pi中的任意三个错误。
[0071]
在一些实施例中，还包括：
[0072]
响应于若干个数据块错误，利用所述纠删矩阵和所述校验块恢复错误的若干个数据块。
[0073]
在一些实施例中，利用所述纠删矩阵和所述校验块恢复错误的若干个数据块，进一步包括：
[0074]
根据错误的数据块的位置从所述纠删矩阵中搜索对应列并组成恢复矩阵；
[0075]
从所述恢复矩阵按照预设规则选择若干行并确定选择的行对应的校验块；
[0076]
将所述恢复矩阵进行消元运算以得到单位矩阵，并利用对应的校验块执行同样的消元运算以得到恢复后的若干个数据块。
[0077]
在一些实施例中，从所述恢复矩阵按照预设规则选择若干行，进一步包括：
[0078]
从第一行开始选择含有1的行，并顺序向下，直至选择得到的每列都具有1，且各行之间不同。
[0079]
具体的，先基于错误元素选择列构建新的子矩阵m
′
.以错误元素为任意的0、2、4为例，则基于m所构建的m
′
为：
[0080][0081]
此时所得到的m
′
为针对待恢复数据的编码有效矩阵。接着从m
′
矩阵中选择三行，构建出矩阵秩等于需要恢复数据量的子矩阵，在m
′
中，即是选择秩为3的子矩阵。
[0082]
选择的方案，按照顺序即可，即是从第一行选择含有1的行，然后顺序向下，直至选择得到每列都具有1，且各行之间不同的子矩阵，此时的子矩阵秩为3。
[0083]
以上述为例，顺序选择得到的子矩阵s为：
[0084][0085]
分别对应的行为0、2、3行。
[0086]
此时得到的s秩为3，则一定可以使用s对应的parity stripe进行针对0，2，4错误的数据块进行解码。
[0087]
解码方法也基于s矩阵。
[0088]
以上述s矩阵为例，可知第一行[1 1 0]代表p0,第二行[0 1 1]代表p2，第三行[0 0 1]代表p3.列向量中，第一列到第三列，分别代表了d0，d2，d4,因此为求得d0,d2,d4.首先对其进行求逆的消元运算，可得：
[0089][0090]
则依次可得到：
[0091][0092]
以其对应的parity stripe进行解码可得：
[0093][0094]
可知，对于通过存活数据块和parity stripe直接可以恢复的数据块，如上述的d0,d2，可以直接进行运算恢复。
[0095]
对于通过存活数据块和parity stripe无法直接恢复的，可以利用公式(6)的s矩阵，基于矩阵关系，利用矩阵中的行进行相互的异或运算，得到其恢复计算关系式。
[0096]
以上述为例，即是d4的关系式。以d4为例，即是通过矩阵行之间的异或运算，消掉除了d4以外所有对应的位置的1，然后基于剩余的信息，进行异或运算。
[0097]
同样方法适用于除了恢复全部信息外的所有错误数据数量情况。
[0098]
例如对于同样为n＝6为例，对错误数据恢复最复杂的5进行验证如下：
[0099]
所得到的纠删阵m为：
[0100][0101]
以错误需要恢复的数据块为0、1、2、4、5为例。
[0102]
此时构建的s矩阵为：
[0103][0104]
可知得到的解为：
[0105][0106]
验证可恢复。
[0107]
当恢复错误数据数量情况为1时，所得到的raid算法为raid 1。
[0108]
以总数据量为n为例，当错误量大于1小于n时，本方法具有明显优势。
[0109]
本算法的存储有效率是50％，即是需要耗费和存储数据块一样多的容量保存所生成的校验块。
[0110]
编码的复杂度随着需要纠错的数据数量变化而变化，当纠错数据数量为k时，每数据块异或运算的时间损耗为t，n个数据块的时间损耗te为：
[0111]
te＝(k-1)*t*n
[0112]
同样环境下，纠错的时间损耗td为：
[0113]
td＝2k*t
[0114]
可知本方法可以实现任意数量错误的解码功能，编码和解码的速度都具有明显的优势。并且无需通过伽罗华域等映射算法进行复杂的矩阵运算，即可完成编解码。
[0115]
本发明提出的方案，可针对不同的纠错位数需求，配置校验条带的生成方式，针对2以上的错误纠错需求，数据存储比例不变，所改变的仅仅是编码和解码的复杂度。不同错误纠错需求下，并不需要经过复杂的解码运算，仅需要调用不同的数据块进行异或即可得到相应的恢复。
[0116]
基于同一发明构思，根据本发明的另一个方面，本发明的实施例还提供了一种数据编码系统400，如图2所示，包括：
[0117]
获取模块401，配置为获取预先配置的纠删位数以及数据盘的数量；
[0118]
生成模块402，配置为根据所述纠删位数和所述数据盘的数量生成纠删矩阵，其中纠删矩阵的第一行中前纠删位数的元素的值为1，其余值为0，其余行在所述第一行的基础上将前纠删位数的元素向右依次平移一位得到；
[0119]
计算模块403，配置为将所述纠删矩阵和数据盘中的数据块矩阵相乘以得到检验块；
[0120]
保存模块404，配置为将校验块保存到相应的数据盘。
[0121]
在一些实施例中，还包括恢复模块，配置为：
[0122]
响应于若干个数据块错误，利用所述纠删矩阵和所述校验块恢复错误的若干个数据块。
[0123]
在一些实施例中，恢复模块还配置为：
[0124]
根据错误的数据块的位置从所述纠删矩阵中搜索对应列并组成恢复矩阵；
[0125]
从所述恢复矩阵按照预设规则选择若干行并确定选择的行对应的校验块；
[0126]
将所述恢复矩阵进行消元运算以得到单位矩阵，并利用对应的校验块执行同样的消元运算以得到恢复后的若干个数据块。
[0127]
在一些实施例中，恢复模块还配置为：
[0128]
从第一行开始选择含有1的行，并顺序向下，直至选择得到的每列都具有1，且各行之间不同。
[0129]
基于同一发明构思，根据本发明的另一个方面，如图3所示，本发明的实施例还提供了一种计算机设备501，包括：
[0130]
至少一个处理器520；以及
[0131]
存储器510，存储器510存储有可在处理器上运行的计算机程序511，处理器520执行程序时执行如上的任一种数据编码方法的步骤。
[0132]
基于同一发明构思，根据本发明的另一个方面，如图4所示，本发明的实施例还提供了一种计算机可读存储介质601，计算机可读存储介质601存储有计算机程序指令610，计算机程序指令610被处理器执行时执行如上的任一种数据编码方法的步骤。
[0133]
最后需要说明的是，本领域普通技术人员可以理解实现上述实施例方法中的全部或部分流程，可以通过计算机程序来指令相关硬件来完成，程序可存储于一计算机可读取存储介质中，该程序在执行时，可包括如上述各方法的实施例的流程。
[0134]
此外，应该明白的是，本文的计算机可读存储介质(例如，存储器)可以是易失性存储器或非易失性存储器，或者可以包括易失性存储器和非易失性存储器两者。
[0135]
本领域技术人员还将明白的是，结合这里的公开所描述的各种示例性逻辑块、模块、电路和算法步骤可以被实现为电子硬件、计算机软件或两者的组合。为了清楚地说明硬件和软件的这种可互换性，已经就各种示意性组件、方块、模块、电路和步骤的功能对其进行了一般性的描述。这种功能是被实现为软件还是被实现为硬件取决于具体应用以及施加给整个系统的设计约束。本领域技术人员可以针对每种具体应用以各种方式来实现的功能，但是这种实现决定不应被解释为导致脱离本发明实施例公开的范围。
[0136]
以上是本发明公开的示例性实施例，但是应当注意，在不背离权利要求限定的本发明实施例公开的范围的前提下，可以进行多种改变和修改。根据这里描述的公开实施例的方法权利要求的功能、步骤和/或动作不需以任何特定顺序执行。此外，尽管本发明实施例公开的元素可以以个体形式描述或要求，但除非明确限制为单数，也可以理解为多个。
[0137]
应当理解的是，在本文中使用的，除非上下文清楚地支持例外情况，单数形式“一个”旨在也包括复数形式。还应当理解的是，在本文中使用的“和/或”是指包括一个或者一个以上相关联地列出的项目的任意和所有可能组合。
[0138]
上述本发明实施例公开实施例序号仅仅为了描述，不代表实施例的优劣。
[0139]
本领域普通技术人员可以理解实现上述实施例的全部或部分步骤可以通过硬件来完成，也可以通过程序来指令相关的硬件完成，程序可以存储于一种计算机可读存储介质中，上述提到的存储介质可以是只读存储器，磁盘或光盘等。
[0140]
所属领域的普通技术人员应当理解：以上任何实施例的讨论仅为示例性的，并非旨在暗示本发明实施例公开的范围(包括权利要求)被限于这些例子；在本发明实施例的思路下，以上实施例或者不同实施例中的技术特征之间也可以进行组合，并存在如上的本发明实施例的不同方面的许多其它变化，为了简明它们没有在细节中提供。因此，凡在本发明实施例的精神和原则之内，所做的任何省略、修改、等同替换、改进等，均应包含在本发明实施例的保护范围之内。

技术特征：
1.一种数据编码方法，其特征在于，包括以下步骤：获取预先配置的纠删位数以及数据盘的数量；根据所述纠删位数和所述数据盘的数量生成纠删矩阵，其中纠删矩阵的第一行中前纠删位数的元素的值为1，其余值为0，其余行在所述第一行的基础上将前纠删位数的元素向右依次平移一位得到；将所述纠删矩阵和数据盘中的数据块矩阵相乘以得到检验块；将校验块保存到相应的数据盘。2.如权利要求1所述的方法，其特征在于，还包括：响应于若干个数据块错误，利用所述纠删矩阵和所述校验块恢复错误的若干个数据块。3.如权利要求2所述的方法，其特征在于，利用所述纠删矩阵和所述校验块恢复错误的若干个数据块，进一步包括：根据错误的数据块的位置从所述纠删矩阵中搜索对应列并组成恢复矩阵；从所述恢复矩阵按照预设规则选择若干行并确定选择的行对应的校验块；将所述恢复矩阵进行消元运算以得到单位矩阵，并利用对应的校验块执行同样的消元运算以得到恢复后的若干个数据块。4.如权利要求3所述的方法，其特征在于，从所述恢复矩阵按照预设规则选择若干行，进一步包括：从第一行开始选择含有1的行，并顺序向下，直至选择得到的每列都具有1，且各行之间不同。5.一种数据编码系统，其特征在于，包括：获取模块，配置为获取预先配置的纠删位数以及数据盘的数量；生成模块，配置为根据所述纠删位数和所述数据盘的数量生成纠删矩阵，其中纠删矩阵的第一行中前纠删位数的元素的值为1，其余值为0，其余行在所述第一行的基础上将前纠删位数的元素向右依次平移一位得到；计算模块，配置为将所述纠删矩阵和数据盘中的数据块矩阵相乘以得到检验块；保存模块，配置为将校验块保存到相应的数据盘。6.如权利要求5所述的系统，其特征在于，还包括恢复模块，配置为：响应于若干个数据块错误，利用所述纠删矩阵和所述校验块恢复错误的若干个数据块。7.如权利要求6所述的系统，其特征在于，恢复模块还配置为：根据错误的数据块的位置从所述纠删矩阵中搜索对应列并组成恢复矩阵；从所述恢复矩阵按照预设规则选择若干行并确定选择的行对应的校验块；将所述恢复矩阵进行消元运算以得到单位矩阵，并利用对应的校验块执行同样的消元运算以得到恢复后的若干个数据块。8.如权利要求7所述的系统，恢复模块还配置为：从第一行开始选择含有1的行，并顺序向下，直至选择得到的每列都具有1，且各行之间不同。9.一种计算机设备，包括：
至少一个处理器；以及存储器，所述存储器存储有可在所述处理器上运行的计算机程序，其特征在于，所述处理器执行所述程序时执行如权利要求1-4任意一项所述的方法的步骤。10.一种计算机可读存储介质，所述计算机可读存储介质存储有计算机程序，其特征在于，所述计算机程序被处理器执行时执行如权利要求1-4任意一项所述的方法的步骤。

技术总结
本发明公开了一种数据编码方法，包括以下步骤：获取预先配置的纠删位数以及数据盘的数量；根据所述纠删位数和所述数据盘的数量生成纠删矩阵，其中纠删矩阵的第一行中前纠删位数的元素的值为1，其余值为0，其余行在所述第一行的基础上将前纠删位数的元素向右依次平移一位得到；将所述纠删矩阵和数据盘中的数据块矩阵相乘以得到检验块；将校验块保存到相应的数据盘。本发明还公开了一种系统、计算机设备以及可读存储介质。本发明提出的方案能够对纠删位数可配置，并根据不同的纠删位数配置校验条带的生成方式，不同错误纠错需求下，并不需要经过复杂的解码运算，仅需要调用不同的数据块进行异或即可得到相应的恢复。块进行异或即可得到相应的恢复。块进行异或即可得到相应的恢复。


技术研发人员：吴睿振 王凛
受保护的技术使用者：山东云海国创云计算装备产业创新中心有限公司
技术研发日：2021.11.29
技术公布日：2022/3/8