基于纠删码相似性的raid-6可扩展方法
【技术领域】
[0001] 本发明设及一种基于纠删码相似性的RAID-6可扩展方法。
【背景技术】
[0002] 随着存储系统中多盘同时出错的几率越来越高，冗余磁盘阵列，尤其是能支持双 盘同时失效的RAID-6阵列，受到了人们广泛关注。传统的RAID-6实现是基于各种纠删码 技术，而其中的一类称之为最大距离可分编码（MD巧的技术，在RAID-6系统中更为流行。 MDS编码可W被归类为水平编码和垂直编码。现有的RAID-6编码；RAID-6编码的实现很 多是基于纠删码。纠删码还可W细分为两类；最大距离可分码（MD巧与非最大距离可分码 (non-MD巧。在RAID-6中，最大距离可分编码又可W细分为两类；水平编码和垂直编码。水 平编码包括了Reed-Solomon Code, X-Code，皿P，H-Code，EVEN孤D，畑P等等。
[0003] RAID-6调整规模所期望具有的特点：在调整磁盘阵列的规模时，我们需要通过移 动一些数据，使得在调整过后，数据在磁盘上的分布仍然均匀。在数据迁移的过程中，我们 更希望在各个磁盘上保持均匀的工作负载，并且移动尽可能少的数据块和校验块。该里总 结出六点在调整阵列规模中，我们希望调整算法能达到的特性：
[0004] 1)数据均匀分布，每个磁盘具有相同数量的数据块和校验块，从而保持负载均 衡；
[0005] 2)最少的数据/校验块移动。增加m块磁盘的理论最少移动数量为^，而减 m + n 少m块磁盘的理论最少移动数为;
[0006] 3)快速寻址，在完成磁盘调整规模后，块在阵列中的物理地址仍然可W用很小的 代价计算出来；
[0007] 4)最少校验盘修改与计算。在扩容中，一次数据块移动会带来其原有校验块的修 改，W及新位置所对应的校验块的修改，因此该一部分代价应当尽可能小；
[000引 5)支持双向扩展。一个理想的阵列规模调整算法，应当同时支持增加磁盘和减少 磁盘；
[0009] 6)最小颗粒度。任何情况下能支持增加或减少一块磁盘。
【发明内容】
[0010] 本发明的目的在于提供一种基于纠删码相似性的RAID-6可扩展方法，能够支持 灵活的磁盘阵列规模扩展。
[0011] 为解决上述问题，本发明提供一种基于纠删码相似性的RAID-6可扩展方法，包 括：
[0012] 对于任意一种MDS编码，假定它的名称为Code-X，支持P+X块磁盘，P为质数， 1《X《2,按照W下规则为Code-X扩展m块磁盘，Im I《3;
[001引若-1《x+m《2,则从当前的MDS编码Code-x出发，分m次扩展，每次扩展出一 块磁盘，最终我们会得到Spwm-Code，扩展的路径是Code-X-Sp+x-Code-Spw-Code-… 一Sp+x+m-Code，其中，Sp+y-Code表示P+X块磁盘的校验盘的编码，Sp+w-Code表示P+X+1块 磁盘的校验盘的编码，Sp+y+m-Code表示p+x+m块磁盘的校验盘的编码；
[0014] 若x+m< -1或者x+m> 2,找到一个新的P'满足-1《x+m-(p-p'）《2,从P+X 块磁盘扩展到P' +X块磁盘，再从当前的P' +X块磁盘出发，分m次扩展，每次扩展出一块磁 盘。
[0015] 进一步的，在上述方法中，对于Sp_i-Code的校验盘的编码方式如下；
[0016]
[0017] 其中，0《i《p-2,0《j<n，n表示扩展前磁盘阵列的数量，n为正整数，Cy表 示磁盘阵列中第i行第i列的校验块，Ci，p_2_i磁盘阵列中第i行第p-2-i列的校验块，CU 表示磁盘阵列中第i行第j列的数据块或校验块，?表示磁盘阵列中第〈p-3-i-j〉 P行第j列的数据块或校验块。
[0018] 进一步的，在上述方法中，Sp_i-Code解码的方程如下：
[0019]
[0020] 其中，失效的磁盘编号为fi，需要恢复的块为。
[0021] 进一步的，在上述方法中，对于Sp-Code的校验盘的编码方式如下；
[0022]
[0023]其中，Ci，p_i表示磁盘阵列中第i行第P-1列的校验块，Ci，p_2_i磁盘阵列中第i行第 p-2-i列的校验块，Cu表示磁盘阵列中第i行第j列的数据块或校验块，.表示磁 盘阵列中第〈p-3-i-j〉P行第j列的数据块或校验块，〈p-3-i-j〉P表示将p-3-i-j的值对P取模。
[0024] 进一步的，在上述方法中，Sp-Code解码的方程如下：
[0025]
[0026] 进一步的，在上述方法中，Sp+1-Code的校验盘的编码方式如下；
[0027]
[00測其中，Ci，p表示磁盘阵列中第i行第p列的校验块，Ci，p_H磁盘阵列中第i行第p-i-1列的校验块，Cu表示磁盘阵列中第i行第j列的数据块或校验块，表示磁 盘阵列中第〈p-3-i-j〉P行第j列的数据块或校验块。
[0029] 进一步的，在上述方法中，Sp+1-Code的解码方式如下；
[0030]
[003U 与现有技术相比，本发明通过对于任意一种MDS编码，假定它的名称为Code-X， 支持P+X块磁盘，P为质数，1《X《2,按照W下规则为Code-X扩展m块磁盘，|m|《3， 若-1《x+m《2,则从当前的MDS编码Code-X出发，分m次扩展，每次扩展出一块磁盘，最终 我们会得到Sp+x+m-Code，扩展的路径是Code-X-Sp+x-Code-Spwi-Code-------Sp+^+"-Code, 其中，Sp+,-Code表示p+x块磁盘的校验盘的编码，Spw-Code表示p+x+1块磁盘的校验盘的 编码，Spwm-Code表示p+x+m块磁盘的校验盘的编码；若x+m< -1或者x+m> 2,找到一个 新的P'满足-1《x+m-(p-p'）《2,从P+X块磁盘扩展到P'+X块磁盘，再从当前的P'+X块 磁盘出发，分m次扩展，每次扩展出一块磁盘，能够支持灵活、高效的磁盘阵列规模扩展
【附图说明】
[0032] 图1是本发明一实施例的基于纠删码相似性的RAID-6可扩展方法的S层结构 图；
[0033] 图2是本发明一实施例的S-code的解码方式示意图；
[0034] 图3是本发明一实施例的从Sp_i-Code到Sp-Code之间的扩容示意图。
【具体实施方式】
[0035] 为使本发明的上述目的、特征和优点能够更加明显易懂，下面结合附图和具体实 施方式对本发明作进一步详细的说明。
[0036] 本发明提供一种基于纠删码相似性的RAID-6可扩展方法，包括：
[0037] 对于任意一种MDS编码，假定它的名称为Code-X，支持P+X块磁盘，P为质数， 1《X《2,按照W下规则为Code-X扩展m块磁盘，ImI《3 ;
[003引若-1《x+m《2,则从当前的MDS编码Code-X出发，分m次扩展，每次扩展出一 块磁盘，最终我们会得到Sp+x+m-Code，扩展的路径是Code-X - Sp+y-Code - Sp+x+1-Code -… 一Spwm-Code，其中，Sp+x-Code表示P+X块磁盘的校验盘的编码，Spwi-Code表示P+X+1块 磁盘的校验盘的编码，Sp+,+m-Code表示p+x+m块磁盘的校验盘的编码；
[0039] 若x+m< -1或者x+m> 2,找到一个新的P'满足-1《x+m-(p-p'）《2,从P+X 块磁盘扩展到P' +x块磁盘，再从当前的p' +x块磁盘出发，分m次扩展，每次扩展出一块磁 盘。具体的，对于任意一种MDS编码（假定它的名称为Code-X，支持P+X块磁盘），我们按 照W下规则为其扩展m块磁盘：
[0040] (1)如果-1《x+m《2,我们就分m次扩展，每次扩展出一块磁 盘。我们从当前的MDS编码出发，最终我们会得到Spwm-Code，而扩展的路径是： Code-X-Sp+x-Code-Sp+x+i-Code------ 8口+打。-Code
[0041] (2)如果x+m< -1或者x+m> 2，我们需要找到一个新的P'满 足-1《x+m-(p-p'）《2。首先，我们从P+X块磁盘扩展到P' +X块磁盘，该一过程完全在基 于Code-X完成，现有的一些方法可W帮助加速该一步骤。
[0042] 本发明的基于纠删码相似性的RAID-6可扩展方法的一优选的实施例中，Sp_i-Code 的校验盘的编码方式如下：
[0043]
[0044] 其中，0《i《p-2,0《j<n，n表示扩展前磁盘阵列的数量，n为正整数，Cy表 示磁盘阵列中第i行第i列的校验块，磁盘阵列中第i行第p-2-i列的校验块，Cy表 示磁盘阵列中第i行第j列的数据块或校验块，隶示磁盘阵列中第〈p-3-i-j〉P 行第j列的数据块或校验块。
[0045] 本发明的基于纠删码相似性的RAID-6可扩展方法的一优选的实施例中，Sp_i-Code 解码的方程如下：
[0046]
[0047] 其中，失效的磁盘编号为fi，需要恢复的块为Cy1。
[0048] 本发明的基于纠删码相似性的RAID-6可扩展方法的一优选的实施例中，对于 Sp-Code的校验盘的编码方式如下；
[0049]
[0050] 其中，Ci，p_i表示磁盘阵列中第i行第P-1列的校验块，Ci，p_2_i磁盘阵列中第i行第 p-2-i列的校验块，Cu表示磁盘阵列中第i行第j列的数据块或校验块，表示磁 盘阵列中第〈p-3-i-j〉P行第j列的数据块或校验块。
[0化1] 本发明的基于纠删码相似性的RAID-6可扩展方法的一优选的实施例中，Sp-Code 解码的方程如下：
[0化2]
[005引本发明的基于纠删码相似性的RAID-6可扩展方法的一优选的实施例中，Sp+1-Code的校验盘的编码方式如下：
[0054]
[005引其中，Ci，p表示磁盘阵列中第i行第P列的校验块，Ci，p_H磁盘阵列中第i行第p-i-1列的校验块，Cu表示磁盘阵列中第i行第j列的数据块或校验块，表示磁 盘阵列中第〈p-3-i-j〉P行第j列的数据块或校验块，〈p-3-i-j〉P表示将p-3-i-j的值对P取模。
[0056] 本发明的基于纠删码相似性的RAID-6可扩展方法的一优选的实施例中，Sp+1-Code 的解码方式如下：
[0057]
[0058] 详细的，为了克服RAID-6系统的调整规模问题，本发明提出一种统一化管理MDS 编码W及支持双向扩展（增加/减少磁盘）的框架。图1展示了该方法的=层结构，最上 层是管理层，然后是中间编码层，最下面是MDS编码仓库。
[0059] 管理层（ManagementLayer,ML)包括了一个统一管理MDS编码的用户接
口，W及 实现阵列规模调整的代码。管理层提供的接口包括提供MDS编码的信息，化及提供增加磁 盘/减少磁盘的操作。
[0060] 中间编码层（IntermediateCodeLayer,ICL)包括了中间可扩展编码（Seal油le IntermediateCode,S-Code)，该套编码是RAID-6系统在磁盘数量为p-1, P, P+1, P+2四种 情形时的解决方案，即四种MDS编码，其中P是一个质数。
[0061] 下面我们把该四种编码分别记作Sp-i-Code，Sp-Code，Sp+i-Code和Sp+2-Code。该四 种S-Code之间有着极为相似的设计，因此在它们之间相互转换的代价很小。每一种S-Code 都可W与一种现实系统中的MDS编码对应，于是我们通过易于相互转化的S-Code，将多种 不同的MDS编码联系在一起。
[0062] MDSCodeRepository，MCR)包括了一些现有的MDS编码方案，例如EVEN0孤，RDP， H-Code，皿P等。当一个新的MDS编码加入到编码仓库中时，它与中间编码联系将被建立起 来。
[0063] 所述磁盘扩展的过程，我们先定义两种类型的扩展，一种叫高效扩展（下称肥， 化曲Efficien巧），另一种叫低效扩展（下称LE，LowEfficiency)。肥能W很少的代价实 现在MDS编码之间的双向扩展，该些代价包括数据迁移量，校验修改量，计算量，等等。
[0064] 中间编码层；在该一部分，我们介绍在该方法用于将MDS编码联系起来的中间编 码S-Code。适用于不同磁盘数量的S-Code之间有很强的相似性。该四种中间编码的适用 磁盘数量和设计思路如下（设P为一个质数）：
[0065] Sp_i-Code;适用于p-1块磁盘（一种皿P编码的变种）
[0066] Sp-Code;适用于P块磁盘（缩减版的Sp+1-Code)
[0067]Sp+1-Code;适用于P+1块磁盘（一种H-Code的变种）
[0068] Sp+2-Code;适用于P+1块磁盘（即EVEN0DD编码）
[0069] 如图2所示，编码与解码：假设Cu表示磁盘阵列中第i行第j列的数据块或校验 块，其中0《i《p-2,0《j<n。
[0070]Sp_i-Code的校验盘的编码方式如下；
[0071]
[0072] Sp_i-Code解码的方程如下（假设失效的磁盘编号为fi，需要恢复的块为C",);
[0073]
[0074] 对于Sp-Code的校验盘的编码方式如下；
[0075]
[0076]Sp-Code的解码方式如下；
[0077]
[007引Sp+1-Code的校验盘的编码方式如下；
[0079]
[0080] Sp+1-Code的解码方式如下；
[0081]
[00間对于S-Code的观察：仔细研究上述几种S-Code之间的相似性，我们可w得出W下 观察结果：
[008引 1)数据块数量的改变对于固定的质数P，Sk-Code(p-1《k《P+2)，即有k个磁 盘的S-Code，在每个编码条带中，数据块的数量为（p-1)X化-2)，而校验块的数量恒定为 2(p-l);
[0084] 2)校验链长度的改变；校验链定义为一个校验块的计算所设及到的其他数据块 或校验块的集合。当S-Code的磁盘数量改变时，校验链的长度也随之发生改变；
[0085] 3)校验块生成的复杂性的改变由于校验链的长度随磁盘数量增加，其编码的复杂 性也增加。
[0086] 统一化用户管理接口：统一化用户管理接口可W提供该方法中MDS编码的信息， W及提供增加、删除MDS编码的流程。它提供的MDS编码信息包含了编码名称，提供磁盘的 数量，编码与解码的方程，等等。添加一个编码的算法描述如下：
[0087]
[008引高效扩展与低效扩展：假设磁盘阵列中，总的数据量为B，根据RAID-0的扩展结 果，在n块磁盘的基础上增加m块磁盘，能达到数据分布均衡的最小移动数据的量为mB/ (n+m)。相似地，从n块磁盘中减少m块磁盘，为了达到数据分布均衡，最少的数据移动量为 |m|B/n。
[0089] 在RAID-6中，等量与两块磁盘的容量用作校验块，而实际数据块占据了n-2块磁 盘，因此最优的数据或校验移动在增加和减少m块磁盘时，分别变成1118八11-2+111)和|m|B/ (n-2)，由此可W算出，增加或减少一块磁盘时，需要移动的数据总量约为：
[0090]
[0091] 由该一等式，我们给出高效扩展（肥）的定义：
[0092] 定义1 ;对于任意两个编码Code-Xl与Code-X2,假设该两种编码分别支持p+xi 和P+X2块磁盘，并且-1《X X2,IX1-X2I《1，如果数据块与校验块在任意一个转 换方向上（Code-Xl扩展到Code-X2,或Code-X2缩减到Code-Xl)需要的移动量不超过B/ (p-Xi+2)，那么它们之间的转换就被认为是高效扩展，反之则是低效扩展。
[0093] 扩展算法；该方法中的扩展算法来自于不同MDS编码的格局上的差异。两种编码 的差异越小，扩展算法就会越简单。参考图3,下述算法2描述了该一快速转换的具体步骤 (在第一列增加一个空磁盘，然后将其余磁盘的数据移过来，从而保证数据分布的均衡）。
[0094]
[0095] 综上所述，如何能让基于MDS编码的RAID-6磁盘阵列拥有良好的扩展能力，是当 下人们所面临的一个重大挑战，为了应对该个挑战，我们提出了一整套框架，用于扩展基于 MDS编码的RAID-6冗余磁盘阵列，它统一地管理多种MDS编码，W此来达到更高的扩展性， 在该个框架中，我们还设计了一系列中间编码，该些中间编码相互间非常容易转换，同时具 有各个MDS编码的特性，成为将该些MDS编码联系在一起的纽带，本发明能支持灵活、高效 的磁盘阵列规模扩展，与传统的RAID扩展方案相比，该方法减少了多达44. 1 %的10数量， 减少95. 2%的时间消耗，将数据迁移速度提升了 20倍。
[0096] 本说明书中各个实施例采用递进的方式描述，每个实施例重点说明的都是与其他 实施例的不同之处，各个实施例之间相同相似部分互相参见即可。
[0097] 专业人员还可W进一步意识到，结合本文中所公开的实施例描述的各示例的单元 及算法步骤，能够W电子硬件、计算机软件或者二者的结合来实现，为了清楚地说明硬件和 软件的可互换性，在上述说明中已经按照功能一般性地描述了各示例的组成及步骤。该些 功能究竟W硬件还是软件方式来执行，取决于技术方案的特定应用和设计约束条件。专业 技术人员可W对每个特定的应用来使用不同方法来实现所描述的功能，但是该种实现不应 认为超出本发明的范围。
[009引显然，本领域的技术人员可W对发明进行各种改动和变型而不脱离本发明的精神 和范围。该样，倘若本发明的该些修改和变型属于本发明权利要求及其等同技术的范围之 内，则本发明也意图包括该些改动和变型在内。
【主权项】
1. 一种基于纠删码相似性的RAID-6可扩展方法，其特征在于，包括： 对于任意一种MDS编码，假定它的名称为Code-X，支持p+x块磁盘，p为质数， I < X < 2,按照以下规则为Code-X扩展m块磁盘，I m I < 3 : 若-I < x+m< 2,则从当前的MDS编码Code-X出发，分m次扩展，每次扩展出一块 磁盘，最终我们会得到Sp+x+m_Code，扩展的路径是Code-X - Sp+x_Code - Sp+x+1_Code -… -Sp+；￡+m_Code，其中，Sp+x_Code表不p+x块磁盘的校验盘的编码，S p+x+「Code表不p+x+1块 磁盘的校验盘的编码，Sp+x+m_Code表示p+x+m块磁盘的校验盘的编码； 若x+m < -1或者x+m > 2,找到一个新的p'满足-1彡x+m-(p-p'）彡2,从p+x块磁 盘扩展到P' +X块磁盘，再从当前的P' +X块磁盘出发，分m次扩展，每次扩展出一块磁盘。2. 如权利要求1所述的基于纠删码相似性的RAID-6可扩展方法，其特征在于，对于 Slrt-Code的校验盘的编码方式如下：其中，0彡i彡p-2,0彡j <η，η表示扩展前磁盘阵列的数量，η为正整数，表示磁 盘阵列中第1行第1列的校验块，（^1)_2_1磁盘阵列中第1行第？-2-1列的校验块，（：^表示 磁盘阵列中第i行第j列的数据块或校验块，表示磁盘阵列中第<p-3-i-j>pS 第j列的数据块或校验块，<p-3-i-j>p表示将p-3-i-j的值对p取模。3. 如权利要求2所述的基于纠删码相似性的RAID-6可扩展方法，其特征在于， Slrt-Code解码的方程如下：其中，失效的磁盘编号为，需要恢复的块为ciifl。4. 如权利要求3所述的基于纠删码相似性的RAID-6可扩展方法，其特征在于，对于 Sp-Code的校验盘的编码方式如下：其中，Ci^1表示磁盘阵列中第i行第p-Ι列的校验块，CUii磁盘阵列中第i行第p-2-i 列的校验块，Cu表示磁盘阵列中第i行第j列的数据块或校验块，表示磁盘阵列 中第<p-3-i-j>p行第j列的数据块或校验块。5. 如权利要求4所述的基于纠删码相似性的RAID-6可扩展方法，其特征在于，S p-Code 解码的方程如下：6. 如权利要求5所述的基于纠删码相似性的RAID-6可扩展方法，其特征在于， Sp+1-Code的校验盘的编码方式如下：其中，Ci;p表示磁盘阵列中第i行第p列的校验块，C 磁盘阵列中第i行第p-i-1 列的校验块，表示磁盘阵列中第i行第j列的数据块或校验块，表示磁盘阵列 中第<p-3-i-j>p行第j列的数据块或校验块。7. 如权利要求6所述的基于纠删码相似性的RAID-6可扩展方法，其特征在于， Sp+1-Code的解码方式如下：
【专利摘要】本发明提供了一种基于纠删码相似性的RAID-6可扩展方法，本发明提出了一整套框架，用于扩展基于MDS编码的RAID-6冗余磁盘阵列，它统一地管理多种MDS编码，以此来达到更高的扩展性，在这个框架中，我们还设计了一系列中间编码，这些中间编码相互间非常容易转换，同时具有各个MDS编码的特性，成为将这些MDS编码联系在一起的纽带，本发明能支持灵活、高效的磁盘阵列规模扩展，与传统的RAID扩展方案相比，该方法减少了多达44.1％的IO数量，减少95.2％的时间消耗，将数据迁移速度提升了20倍。
【IPC分类】G06F3/06, G06F12/02
【公开号】CN104881365
【申请号】CN201510291852
【发明人】吴晨涛, 过敏意, 李颉, 何绪斌, 黄洵松, 冯博
【申请人】上海交通大学
【公开日】2015年9月2日
【申请日】2015年5月31日
