一种纠错参数无限制的阵列纠删码方法

一种纠错参数无限制的阵列纠删码方法
【技术领域】
[0001] 本发明设及计算机大容量存储领域，尤其是设及一种不间断的高容错磁盘阵列系 统。
【背景技术】
[0002] 中福在线即开型彩票是W计算机网络在线方式发行销售的即开型彩票，国际上统 称为视频彩票，是中国福利彩票的新型票种和国内唯一的视频彩票，其主要特点是，采用计 算机和通讯网络系统为发行载体，在投注终端上完成彩票销售，实现在线投兑，并使用中福 在线即开型彩票专用投注卡作为投注介质，记录彩票投注过程和中奖结果，实现即开、即 兑。福彩中屯、系统的稳定性、安全性需求也在不断增加，建设福彩中屯、容灾系统工程是一个 相当关键的环节。业务量的增长和业务模式的日趋多样性是使得不能单依靠磁带库的备份 来满足系统出现异常或灾难情况时业务支撑的要求；另一方面，电脑福利彩票销售系统已 经升级为"热线"系统，销售规模不断扩大，电脑系统的负荷与日俱增。一旦出现故障，如果 不能在短时间内恢复，将会造成严重的损失。因此，福彩中屯、迫切需要建设数据存储恢复系 统，提高对数据的分析处理能力，并且在主中屯、系统出现故障时，数据存储恢复系统能在数 据零丢失的情况下，于半小时内接管主中屯、系统的全部功能。因此，能够最大限度地支持数 据容灾而又最小程度地依赖硬件冗余的数据存储恢复系统意义重大。
[0003] 目前针对福利彩票行业还没有相关专用的数据存储备份系统，一般都是采用通 用的容灾备份系统，该些通用系统没有考虑到福利在线彩票系统的特点，存在W下几个缺 点：
[0004] 1)通用数据存储备份系统的功能较多，针对福利彩票在线系统数据备份该类较为 单一固定的应用，使用不方便；
[0005] 2)如果服务器发生数据丢失，整个数据恢复系统不能使用；
[0006] 3)数据存储备份系统维护困难。
[0007] 4)没有考虑到福利彩票行业的特殊性。
[0008] 磁盘阵列（RedundantArrayofInexpensiveDisks)，简称RAID,是高可靠性存 储系统的基础和关键部件。虽然RAID包含多块磁盘，但是在操作系统下是作为一个独立 的大型存储设备出现。人们在开发RAID时主要是基于W下设想，即几块小容量硬盘的价格 总和要低于一块大容量的硬盘，设计RAID系统的基本思想就是把多个相对便宜的硬盘组 合起来，成为一个磁盘阵列，使性能达到甚至超过一个价格昂贵、容量巨大的硬盘。虽然目 前该一设想还没有完全实现，RAID在节省成本方面的作用还不是很明显，但是RAID可W充 分发挥出多块硬盘的优势，实现远远超出任何一块单独硬盘的速度和吞吐量。除了性能上 的提高之外，RAID还可W提供良好的容错能力，当硬盘出现问题的情况时仍然可W继续工 作，不会受到损坏硬盘的影响。
[0009] 发明技术方案
[0010] 本发明的目的是实现一种基于编码的磁盘阵列系统，提供了对数据备份高效、可 靠的解决方案，在关键服务器上实现，把数据丢失损害降低到最低限度。
[0011] 本发明的技术方案；构造一个参数为（n-t,n-1,t, (n-t)xt/(n-l))的等重码， 也就是构造一个（n-t)X(n-1)的矩阵，使得每行恰好有t个1，而每列恰好为（n-t)Xt/ (n-1)个1，构造一个参数为（n，n-t，t/2+l)的垂直阵列码；码长为n，信息位为k，汉明距离 为（n-k)/化1。磁盘阵列中有n个磁盘，则将每个磁盘分为n个块。用其中编号为k=n-t 个块作为信息块，而余下的n-t,…，n-2,n-1的块作为校验块；
[0012] 编码过程为：
[001引令3。表示阵列中第i行第j列上的元素，把E码用一个矩阵A= [au]。《化。《拘 来表示；其中y。用于存储有效信息，称为信息元，而校验元[a i,j]n-t<i<n,0<j<n 由信息元根据如下步骤生成：
[0014] ①根据矩阵A，构造一个（n-t)X(n-1)的矩阵A'如下：
[0015]
[0016] ②生成一个等重码C(n-t,n-1,t, (n-t)Xt/ (n-1))，既在矩阵A' 上选择（n-t)Xt 个元素，我们把该些元素表示成Cu，具体表示如下：
[0017]
[0018] ⑨将该些元素随机的划分为t个集合，如下所示：
[0019] D。：[d。，。，d0，i'''d0，n-t-i]
[0020] [di,0, di,i…di,n-t-i]
[0021] ......
[002引Dk-i:[屯_1,。, dt_i, i'''dt_i,n-t-i]
[002引④E码的校验元au就可w由如下公式生成：
[0024]
i=11-k..-n-\,J= 0...n-l
[0025] 所述du所对应的是一个A'中的元素，要经过一个相对坐标变换才能够得到原始 矩阵A中所对应的元素；
[0026] 纠错过程为：
[0027] 阵列中存在m《t/2列删除错，按照如下步骤回复所有m列删除错：
[002引①将阵列中所有的校验元的状态标记为呵用'；
[0029] ②随机选择一个状态为'可用'的校验元au，检查它所校验的信息元 是否被删除。如果其中没有信息元被删除，那么将此校验元标记为'无用'；如果 其中有且仅有一个信息元被删除，同样将此校验元标记为'无用'，并且此被删除 的信息元则可由如下公式恢复：
[0030] ⑨重复第二步，直到阵列中不再有状态为'可用'的校验元，或者所有状态为'可 用'的校验元都校验了至少两个被删除的信息元。
[0031] 采用上述技术方案，作为阵列码的一种，E码的编译码过程中都只用到了异或运 算，而异或运算的时间复杂度远远低于有限域运算。因此E码的容错能力远远高于传统的 阵列码，其容错能力大约在几十该个数量级。
【附图说明】
[0032] 图1为E码磁盘阵列布局构成示意图。
[0033] 图2为文件切割规则示意图。
【具体实施方式】
[0034] 下面结合具体实施例作进一步详述：
[0035] 在E码中，数据将会存放在一个nXn的阵列中。具体到磁盘阵列中，假设磁盘阵 列中有n个磁盘，则将每个磁盘分为n个块。用其中编号为k=n-t个块作为信息块，而余 下的n-t，…，n-2,n-1的块作为校验块。
[0036] 一"1#~体的。=12，& = 8,心4感盘阵列实例如图1所示：E码就是一个参数 为（']乂兰厂+U，或者["知/2+口的阵列码，意味着B码的码长为"，能够容纳A 列的有效信息，用t=n-k列的校验信息获得t/2列的容错能力。
[0037] 在构造E码的过程中有一个关键的问题是要想办法构造一个二维等重码。等重 码是一个在通讯领域广泛讨论的编码，一个等重码是指一组有着相同汉明重量的向量， 而二维等重码则是一个在行和列两个维度上都有着相同汉明距离的矩阵。一个参数为 (n，m，i，j)的二维等重码是指一个n行m列的二进制矩阵，它每行有且仅有i个1，而每列 也有且仅有j个1。既行重恒等于i，列重恒等于j。因为它的每行和每列的重量是相等的， 由此，我们把该个基于等重码的全新的阵列码命名为E码。
[003引如果我们要构造一个参数为（n-t，n-l，t，（n-t)Xt/(n-l))的等重码，也就是构 造一个（n-t)X(n-1)的矩阵，使得每行恰好有t个1，而每列恰好为（n-t)Xt/(n-1)个1， 该样我们就可W构造一个参数为（n,n-t,t/2+1)的E码。
[0039]等重码的构造是E码构造的基础。若（n-t)Xt能够整除（n-1)，那么我们可W按 照如下步骤成功构造出一个参数为（n-t，n-l，t，（n-t)Xt/(n-l))的等重码：
[0040] 1.将（n-t)X(n-1)矩阵第0列至第t-1列的所有元素赋值为1，其他元素赋值为 0.
[0041]2.对j从t到n-1，计算矩阵第j列的列重量，若第j列的列重量小于（n-t)Xt/ (n-1)，那么必有 =0，ai，j，= 1 使得wei曲tj，〉(n-t)Xt/(n-l)，则赋值ai，j=l，ai，j，= 0。
[00创 3.重复第二步，直到矩阵每列的列重量均等于（n-t)xt/(n-l)，至此，我们得到 了参数为（n-t，n-l，t(n-t)Xt/(n-l))的等重码。
[00创机械地按照W上步骤进行就可W得到一个（n-t，n-l，t，（n-t)Xt/(n-l))等重 码，但是满足该样参数的等重码并不是唯一的。我们可W随机的交换所得到的等重码中的 某些行或某些列，该并不改变其等重的性质，却可W给我们更多的选择。
[0044] E码的编码过程
[0045] 令au表示阵列中第i行第j列上的元素，该样我们就可W把E码用一个矩阵A=
[aij]ci<i<n，。《拘来表示。其中i<n-t，cisu<n用于存储有效信息，称为信息元，而校验元 [au]n-t< Kn由信息元根据如下步骤生成：
[0046] 1.根据矩阵A，构造一个（n-t)X(n-1)的矩阵A'如下：
[0047]
[0048] 2.生成一个等重码C(n-t,n-1,t, (n-t)Xt/ (n-1))，既在矩阵A' 上选择（n-t )Xt 个素，我们把该些元素表示成Cu，具体表示如下：
[0049]
[0化日]3.将该些元素随机的划分为t个集合，如下所示：
[0051] D〇:[d0,0,d0,I...d0,n-t-i]
[0052] Di: [di，0,di，i…di，n-t-i]
[0化3] ......
[0054]Dk_i: [dt_i，0,d……dt_i，n-t-i]
[005引 4.E码的校验元au就可W由如下公式生成：
[00日6]
i二n-k'''n-\，j二Q…n-1
[0057] 有一点需要特别指出的是，du所对应的是一个A'中的元素，要经过一个相对坐 标变换才能够得到原始矩阵A中所对应的元素。
[0化引 E码的译码过程
[0059] 如果E码阵列中存在m《t/2列删除错，则我们可按照如下步骤回复所有m列删 除错：
[0060] 1.将阵列中所有的校验元的状态标记为呵用'；
[0061] 2.随机选择一个状态为'可用'的校验元au，检查它所校验的信息元是否被删除。 如果其中没有信息元被删除，那么将此校验元标记为'无用'；如果其中有且仅有一个信息 元被删除，同样将此校验元标记为'无用'，并且此被删除的信息元则可由如下公式恢复：
[0062]
i_{n -k)单i'，s丰j，
[0063] 3.重复第二步，直到阵列中不再有状态为'可用'的校验元，或者所有状态为'可 用'的校验元都校验了至少两个被删除的信息元。
[0064] 经过上述步骤，如果系统中所有被删除的信息元都得到了恢复，我们就认为此译 码过程成功。
[0065] 对我们的编码理论加W应用，不妨WE(31，10, 6)码举例说明。
[0066] 文件切割规则
[0067] 1、每个文件的大小不一定相同，并且也不一定是21的倍数，那么就W最大的文 件作为划分标准，分成21块，每块大小为sliceLength。当最大文件不为21的倍数时，贝U sliceLength=最大文件大小/21+1 ;
[0068] 2、W最大文件为划分标准，较小文件的不足最大文件部分全部用0填充，并且记 录下每个文件大小。
[0069] 不妨假设有31个文件，其中最大文件为20B，最小文件为15B。取最大文件为划分 标准，则每一块大小sliceLength= 20/21+1 = 1，即sliceLength= 1B，总共 21 块。编码 时假设所有文件大小相等，且都为sliceLength*21 = 21B，则最大文件最后1B为全0,最小 文件后面6B为全0.然后进行编码。如图2所示。
[0070] 文件操作规则
[0071] 1、校验码文件和数据文件分开，每个校验码文件大小为sliceLength*10,共31个 编码文件，存放于目录FileRecove^\^eckCodeFiles中（默认，可W更改路径）。上例中， 校验文件大小为10B。
[0072] 2、超出文件大小部分，按全0进行编码。
[0073] 3、当数据文件大小差异很大时，有可能出现校验码文件大小比某些数据文件还大 的情况。上例中，最小文件大小为15B，检验码文件为10B。假如最小文件为8B，校验码文 件也为10B，比最小文件还要大2B，该是因为分块时，SliceLength是按最大文件为标准划 分的。
[0074] 4、如果需要备份文件小于31时，如文件数n= 25时，则最后31-25 = 6个文件按 全0编码。即文件数可灵活选择，假如选择的文件大小一致，当文件数小于16个时，所需的 校验码文件总大小超过了 16个文件的总大小，空间冗余度甚至高于直接备份数据的空间 利用率，恢复效果也差于直接备份的恢复效果。
[0075] 5、具体编码规则：
[0076] 令au表示第i个文件的第j块数据，该样我们就可W把所有数据文件的所有数 据块用矩阵A = [au]。《i<n，Cl< j<n来表不。其中[a i, j]。< i<n-t，Cl< j<n用于存储有效倍息， 称为信息元，而校验元[au]"_t< y。由信息元根据如下步骤生成：
[0077] (1)根据矩阵A，构造一个（n-t)X(n-1)的矩阵A'如下：
[007引
[0079](2)生成一个等重码C(n-t，n-1，t，（n-t)Xt/ (n-1))，既在矩阵A'上选择 (n-t)Xt个元素，我们把该些元素表示成Cu，具体表示如下：
[0080]
[0081] (3)将该些元素随机的划分为t个集合，如下所示：
[0082] D。：[d。，。，d0，i'''d0，n-t-i]
[0083] Di:[di'0，di'i…di'n-t-i]
[0084] ......
[0085] Dk-i:[屯_1,。, dt_i, i'''dt_i,n-t-i]
[0086] (4)第i个校验文件的j数据块au就可W由如下公式生成：
[0087]
i二n-k..-n-l, j = 0...n-l[00能]文件恢复规则
[0089] 1、随机删除n个文件，按照E码译码算法进行恢复。
[0090] (1)如果有m《t/2个文件被损坏，则我们可按照如下步骤回复所有m个文件：
[0091] (2)将校验文件中所有的校验块的状态标记为'可用'；
[0092](3)随机选择一个状态为'可用'的校验块au，检查它所校验的信息元是否被删 除。如果其中没有信息元被删除，那么将此校验元标记为'无用如果其中有且仅有一个信 息元被删除，同样将此校验元标记为'无用'，并且此被删
[0093] (4)重复第二步，直到阵列中不再有状态为'可用'的校验元，或者所有状态为'可 用'的校验元都校验了至少两个被删除的信息元。
【主权项】
1. 一种纠错参数无限制的阵列纠删码方法E码，其特征在于构造一个参数为 (n-t，n-l, t, (n-t) Xt/(n-l))的等重码，也就是构造一个（n-t) X (n-1)的矩阵，使得每行 恰好有t个1，而每列恰好为（n-t) X V (n-1)个1，构造一个参数为（n，n-t，t/2+l)的垂直 阵列码；码长为n，信息位为k，汉明距离为（n-k)/2+1。磁盘阵列中有η个磁盘，则将每个 磁盘分为η个块。用其中编号为k = n-t个块作为信息块，而余下的n-t,…，η-2, n-1的块 作为校验块； 编码过程为： 令气」表示阵列中第i行第j列上的元素，把E码用一个矩阵A = [a i,^ ^ < n 来表示；其中用于存储有效信息，称为信息元，而校验元[ai;j]n_t ^ i <n, O ^ j<n 由信息元根据如下步骤生成： ① 根据矩阵A，构造一个（n-t)X (n-1)的矩阵A'如下： ② 生成一个等重码C (n-t, n-1,t, (n-t) X t/ (n-1))，既在矩阵A'上选择（n-t) X t个元 素，我们把这些元素表示成Cu，具体表示如下：③ 将这些元素随机的划分为t个集合，如下所示：④ E码的校验元au就可以由如下公式生成： n-k-l au = ?0d>-(n-tu i = n-k---n-l, j = 所述du所对应的是一个A'中的元素，要经过一个相对坐标变换才能够得到原始矩阵 A中所对应的元素； 纠错过程为： 阵列中存在m < t/2列删除错，按照如下步骤回复所有m列删除错： ① 将阵列中所有的校验元的状态标记为'可用'； ② 随机选择一个状态为'可用'的校验元检查它所校验的信息元是否 被删除。如果其中没有信息元被删除，那么将此校验元标记为'无用如果其 中有且仅有一个信息元被删除，同样将此校验元标记为'无用'，并且此被删除 的信息元则可由如下公式恢Ik1 ? di-{n-ns) i-{n-k)^i\ s^j' ③重复第二步，直到阵列中不再有状态为'可用'的校验元，或者所有状态为'可用'的 校验元都校验了至少两个被删除的信息元。
【专利摘要】本发明涉及计算机大容量存储领域，尤其是涉及一种不间断的高容错磁盘阵列系统。构造一个参数为(n-t,n-1,t,(n-t)×t/(n-1))的等重码，也就是构造一个(n-t)×(n-1)的矩阵，使得每行恰好有t个1，而每列恰好为(n-t)×t/(n-1)个1，构造一个参数为(n,n-t,t/2+1)的垂直阵列码；码长为n，信息位为k，汉明距离为(n-k)/2+1。磁盘阵列中有n个磁盘，则将每个磁盘分为n个块。用其中编号为k＝n-t个块作为信息块，而余下的n-t,…,n-2,n-1的块作为校验块。采用上述技术方案，作为阵列码的一种，E码的编译码过程中都只用到了异或运算，而异或运算的时间复杂度远远低于有限域运算。因此E码的容错能力远远高于传统的阵列码，其容错能力大约在几十这个数量级。
【IPC分类】G06F11/07, G06F3/06
【公开号】CN104881253
【申请号】CN201510269982
【发明人】吴德理, 孙宣东, 刘泽
【申请人】东莞天意电子有限公司
【公开日】2015年9月2日
【申请日】2015年5月25日