一种提高raid-6可扩展性的数据迁移方法

一种提高raid-6可扩展性的数据迁移方法
【技术领域】
[0001] 本发明属于计算机存储领域，具体设及一种提高RAID-6可扩展性的数据迁移方 法。
【背景技术】
[000引随着多盘故障的可能性的增长，RAID-6也受到了越来越多的关注。目前存在着大 量的基于多种可擦除编码技术的RAID-6的实现，MDS(MaximumDistanceS巧ar油le，最大 距离可分码）编码便是其中的一种传统编码。MDS编码通过提供一定量的冗余来实现应对 磁盘故障的保护。根据数据与检验的分布，MDS编码可W分为水平编码与垂直编码。
[000引然而，目前磁盘阵列中的已有的解决方案并不适用于RAID-6的扩展（向已有的磁 盘阵列中添加新的磁盘）。在寻找有效的解决方案，W有效地对基于MDS编码的RAID-6系统 进行扩展的问题上，研究人员面临着极大的挑战。首先，目前已有的针对RAID-0或RAID-5 的通用性的方案并不适用于多种多样的RAID-6的编码。例如，RDP与P-code中数据与检 验有着不同的布局，如图1与图2所示。因此扩展方案需要根据RDP或P-code的特性分别 进行设计。其次，传统的扩展方案是基于round-robin顺序的，但其较高的校验迁移、修改 与计算的代价使其不适用于RAID-6。原因之一在于RAID-6编码的校验布局十分复杂。另 一个原因在于扩展之后条带会发生戏剧性的变化。例如，任意数据元素的移动将会在与其 相关的校验元素上导致可达8次的额外的I/O操作。

【发明内容】

[0004] 本发明的目的在于提供一种提高RAID-6可扩展性的数据迁移方法，能够加速 RAID-6的扩展过程，减少迁移时间。
[0005] 为解决上述问题，本发明提供一种提高RAID-6可扩展性的数据迁移方法，包括：
[0006] 为扩展前编码矩阵的单个数据块与校验块定义不同的优先级；
[0007] 比较扩展前后的编码矩阵的陈列布局并寻找一个代价最小的方式改变扩展前的 使用中的条带的陈列布局，确定移动扩展前的使用中的条带中具有最高的移动优先级的数 据块与校验块；
[0008] 根据编码矩阵的条带中数据块的分布，确定选择一组条带中的一小部分条带W进 行后续平衡工作负载；
[0009] 根据确定的移动扩展前的使用中的条带中具有最高的移动优先级的数据块与校 验块和确定选择的一组条带中的一小部分条带为每个条带进行数据迁移。
[0010] 进一步的，在上述方法中，当所述编码矩阵为水平编码矩阵，比较扩展前后的编码 矩阵的陈列布局并寻找一个代价最小的方式改变扩展前的使用中的条带的陈列布局，确定 移动扩展前的使用中的条带中具有最高的移动优先级的数据块与校验块包括：
[0011] 标记扩展后的校验盘，其中，校验盘保留，扩展的磁盘均作为数据盘使用；
[0012] 标记扩展后的磁盘，其中，将m块磁盘添加到磁盘阵列中，新添加的磁盘被插在所 有数据磁盘的中间，m为正整数；
[0013] 进行行标记，其中，如果一个扩展前的使用中的条带包含了n,个数据行，则会在扩 展后的使用中的条带标记上相同的行标记，n,为正整数；
[0014] 进行特殊校验处理，W确定移动扩展前的使用中的条带中具有最高的移动优先级 的数据块与校验块。
[0015] 进一步的，在上述方法中，进行特殊校验处理，W确定移动扩展前的使用中的条带 中具有最高的移动优先级的数据块与校验块包括：
[0016] 如果水平校验块参加构成了斜向或反斜向校验块，那么水平链中数据块或校验块 有着比斜向或反斜向校验链中更高的优先级；
[0017] 相反地，如果斜向或反斜向校验块参与构成了水平校验块，那么斜向或反斜向校 验块中的数据块与校验块移动有着比水平链中更高的优先级。
[0018] 进一步的，在上述方法中，当所述编码矩阵为垂直编码矩阵，比较扩展前后的编码 矩阵的陈列布局并寻找一个代价最小的方式改变扩展前的使用中的条带的陈列布局，确定 移动扩展前的使用中的条带中具有最高的移动优先级的数据块与校验块包括：
[0019] 进行原始盘标记，其中，原始磁盘标识（ID)被保留，而扩展磁盘将用作数据盘；
[0020] 进行扩展盘标记，将m块盘加入一个阵列中，新加入的m块盘被标记为最后的m 列。
[0021] 进一步的，在上述方法中，所述条带中数据块的分布根据数据块分布的统计信息 得到。
[0022] 进一步的，在上述方法中，确定选择一组条带中的一小部分条带W进行后续平衡 工作负载中，水平编码矩阵的一小部分条带因为较高的迁移代价而进行平衡工作负载牺 牲。
[0023] 进一步的，在上述方法中，确定选择一组条带中的一小部分条带W进行后续平衡 工作负载中，垂直编码矩阵的一小部分条带为不作迁移的保留的条带。
[0024] 与现有技术相比，本发明根据对单个/多个条带的全局，实现数据迁移最小化和 校验的修改与计算，该方法通过减少修改校验的次数，异或计算的次数，总共的I/O操作的 次数W及迁移时间来加速RAID-6的扩展过程；该方法使I/O在磁盘阵列中的磁盘上均匀分 布，减少了迁移时间。
【附图说明】
[00巧]图1显示了畑P编码磁盘数从6到8的扩展示意图，其中，图1 (a)显示P= 5时RDP编码的行校验示意图，图1 (a)显示P= 5时RDP编码的斜校验示意图，图1 (C)显示P =7时RDP编码的行校验示意图，图1 (d)显示P= 7时RDP编码的斜校验示意图；
[0026] 图2说明了P-Code编码磁盘数从6扩展到7的示意图，其中，图2 (a)显示P= 7,p-1块磁盘时P-Code的垂直校验示意图，图2化）显示P=7,P块磁盘时P-Code的垂直 校验示意图；
[0027] 图3为总结不同优先级的数据的校验修改开销的示意图；
[002引图4是BlockO的数据移动情况示意图，其中，图4(a)为行校验示意图，图4(b)为 斜松验不意图；
[0029] 图5为总结扩展盘标记开销情况的示意图；
[0030] 图6是本发明一实施例（RDP编码）的基于优先级的迁移过程示意图，其中，图 6(a)为逻辑地址示意图，图6(b)为行校验示意图，图6(c)为斜校验示意图；
[0031] 图7是本发明一实施例（P-Code编码）的基于优先级的迁移过程示意图，其中，图 7(a)为逻辑地址示意图，图7(b)为垂直校验示意图；
[0032] 图8是本发明一实施例（RDP编码）的条带集中的数据分布示意图；
[0033] 图9是本发明一实施例（P-Code编码）的条带集中的数据分布示意图；
[0034] 图10是本发明一实施例伽P编码）的在负载平衡步骤中基于优先级的迁移过程 示意图，其中，图10(a)为逻辑地址示意图，图10化）为行校验示意图，图10(C)为斜校验示 意图；
[00巧]图11是本发明一实施例（P-Code编码）的在负载平衡步骤中基于优先级的迁移 过程示意图，其中，图11(a)为逻辑地址示意图，图11(b)为垂直校验示意图；
【具体实施方式】
[0036] 为使本发明的上述目的、特征和优点能够更加明显易懂，下面结合附图和具体实 施方式对本发明作进一步详细的说明。
[0037] 本发明提供一种提高RAID-6可扩展性的数据迁移方法，包括：
[0038] 步骤S1，优先级定义；为扩展前编码矩阵的单个数据块与校验块定义不同的优先 级；根据图3中总结的校验修改次数，我们定义了该方法中数据块与 校验块迁移的优先级， 更高的优先级意味着在I/O与校验计算上有更小的总开销，根据图3中各种优先级，我们可 W评估一次移动是否高效。例如，如图4所示，块0从磁盘2迁移到了磁盘0,而别的块都得 W保留而没有移动。W水平校验的观点来看（如图4(a)所示），块0依旧停留在原先的水 平校验链上且与其相关的校验P。不必变化。另一方面，考虑斜向校验（如图4(b)所示）， 块0依然与别的块共享同一校验链（例如，块11，14，Pi与Q。)，而且相关的校验元素会被保 留。因此，块0的移动不会改变任何校验并在扩展过程中有最高的优先级（优先级1);
[0039] 步骤S2,布局比较；比较扩展前后的编码矩阵的陈列布局并寻找一个代价最小的 方式改变扩展前的使用中的条带的陈列布局，确定移动扩展前的使用中的条带中具有最高 的移动优先级的数据块与校验块；其中，〇US(01dUsedStripe)为扩展前的使用中的条带， NUS(NewUsedStripe)为扩展后的使用中的条带；
[0040] 步骤S3,均衡检查：完成布局比较后，根据编码矩阵的条带中数据块的分布，确定 选择一组条带中的一小部分条带W进行后续平衡工作负载，该一步的数据块与校验块移动 的开销在可接受的范围内，尽管选择最高优先级的数据或校验移动能够最小化扩展过程的 开销，但是会导致不均衡的负载该一RAID系统中的一个严重的问题。为了解决该个问题， 负载平衡检查被用于实现平衡的负载；
[0041] 步骤S4,根据确定的移动扩展前的使用中的条带中具有最高的移动优先级的数据 块与校验块和确定选择的一组条带中的一小部分条带为每个条带进行数据迁移。布局比较 W及负载平衡检查步骤之后，一个综合的迁移策略能够被得出，之后系统可W开始数据迁 移过程。
[0042] 本发明提高RAID-6可扩展性的数据迁移方法的一优选的实施例中，对比扩展前 与扩展后的校验布局，我们提出了针对水平与垂直编码的不同的规则，由于水平与垂直编 码矩阵的不同，我们设计了不同的扩展方案并将分别讨论它们，
[0043] 当所述编码矩阵为水平编码矩阵，步骤S2,布局比较；比较扩展前后的编码矩阵 的陈列布局并寻找一个代价最小的方式改变扩展前的使用中的条带的陈列布局，确定移动 扩展前的使用中的条带中具有最高的移动优先级的数据块与校验块包括：
[0044] 标记扩展后的校验盘，其中，校验盘保留，扩展的磁盘均作为数据盘使用；
[0045] 标记扩展后的磁盘，其中，将m块磁盘添加到磁盘阵列中，新添加的磁盘被插在所 有数据磁盘的中间，m为正整数；
[0046] 进行行标记，其中，如果一个扩展前的使用中的条带包含了n,个数据行，则会在扩 展后的使用中的条带标记上相同的行标识（ID)，n,为正整数；
[0047] 进行特殊校验处理，其中，如果水平校验块参加构成了斜向或反斜向校验块，那么 水平链中数据块或校验块有着比斜向或反斜向校验链中更高的优先级，相反地，如果斜向 或反斜向校验块参与构成了水平校验块，那么斜向或反斜向校验块中的数据块与校验块移 动有着比水平链中更高的优先级。后续即可选择正确的具有最高的移动优先级的数据块与 校验块进行迁移。
[004引具体的，我们WRDP编码（一种水平编码）为例，分别将其从6块磁盘扩展到8块 磁盘和从6块磁盘扩展到7块磁盘，来展示在RAID-6中该扩展方案是如何工作的。例如， 如果我们希望将一个使用RDP编码的RAID-6阵列由6块磁盘扩展为8块磁盘，比较图1中 的布局，根据上述规则我们有如下的策略，
[0049] 校验盘标记；图1 (a)和1化）中的列4和5作为校验盘保留，列ID将变为列6和 7,如图1(c)和1(d)所示。
[0050] 扩展盘标记；根据图5所示，两块扩展盘被视为数据盘，若被标记为列2和3,则迁 移开销最小。
[005。 行标记海个0US中的行ID都被保留，由于增多了磁盘，条带的大小将会变大，包 含更多行，该在扩容过程该被称作幽灵行。
[0052] 特殊校验处理：水平链中数据与校验移动的优先级高于斜向或反斜向校验。
[0053] 数据与校验迁移：块2,6, 3,和13被选择进行迁移，如图6所示，而且所有的数据 块均在相同的校验布局下共享相同的校验。因此，所有的校验块都被保留，而且他们的移动 有着最高的有优先级。
[0054] 当所述编码矩阵为垂直编码矩阵，步骤S2,布局比较；比较扩展前后的编码矩阵 的陈列布局并寻找一个代价最小的方式改变扩展前的使用中的条带的陈列布局，确定移动 扩展前的使用中的条带中具有最高的移动优先级的数据块与校验块包括：
[00巧]进行原始盘标记，其中，原始磁盘标识（ID)被保留，而扩展磁盘将用作数据盘；
[0056] 进行扩展盘标记，将m块盘加入一个阵列中，新加入的m块盘被标记为最后的m 列。后续即可选择具有最高优先级的数据块与校验块迁移。具体的，我们WP-Code(垂直 编码）为例，分别将其从6块磁盘扩展到8块磁盘和从6块磁盘扩展到7块磁盘，来展示在 RAID-6中该扩展方案是如何工作的。例如，如果我们希望将一个使用P-Code的RAID-6阵 列从6盘扩展至7盘，通过和图2中的布局进行比较，根据W上的规则，我们有如下的策略，
[0057] 磁盘标记；如图7 (a)所示，原始列ID被保留，新的磁盘被标记为列6。
[005引行标记海个OUS中的行ID被保留。
[0059] 数据与校验迁移：块0和1被选择用于迁移，如图7化），他们有着最高的优先级而 且有S块校验任3，？4和Pg)在每个条带中均被修改。
[0060] 步骤S3,均衡检查中，首先我们在布局比较后获取数据块分布的统计信息。例如， 图8和图9显示了在RDP和P-Code中第二行（条带0)的数据分布情况。我们注意到条带 里每一列数据的个数扩展后会不平衡，不同的列有不同数量的数据块。
[0061] 对于水平和垂直编码，下面的方法可W用于实现一致的数据分布。
[00的]1)水平编码
[0063] 大多数的水平编码具有不对称的数据与校验分布，因此一小部分条带因为较高的 迁移代价而进行平衡工作负载牺牲（称作"牺牲的条带"）。在负载平衡检查的步骤中，该 部分的条带会被进行平衡工作负载，而且条带中部分的块会被迁移W实现平衡的负载。
[0064]。垂直编码
[0065] 大多数的垂直编码有着对称的数据块与校验块分布，每个条带中的数据元素都被 交替地迁移，而条带的一小部分不会移动（称为"保留的条带"）。
[0066] 水平编码中，为了计算牺牲与保留条带的百分比，我们将"条带集"定义为具有同 一数据分布的n,个条带，n,-个条带集里条带的个数。假设n是扩展后数据磁盘的数量， n。是扩容前数据元素的总数。n,可W被如下公式计算：
确定选择一组条带 中的一小部分条带进行平衡工作负载。因此在一个条带集中，每列数据元素的总数（表示 为nJ是
图8 (2)所示在每个条带集，一小部分条带被选择作为牺牲保留 的条带。例如，如图8所示，每个条带集包含了 =个条带
，其 中最后一个条带被选择作为牺牲的条带。
[0067] 在每一个条带集中，每一列需要包含8个数据元素
因此牺牲的条带（条带ID为2)中的数据分布是0, 2,4,4,4,4, 2 (例如，列0的数据元素个 数为nee-2X4 = 8-8 = 0)。
[006引垂直编码中，类似地，如图9所示，P-Code的条带大小是7，
而最后一个条带是保留条带。
[0069] 我们总结了在负载平衡步骤中基于优先级的 迁移过程，如图10和图11所示。因 此负载平衡检查步骤中的开销极小。
[0070] 步骤S4,根据确定的移动扩展前的使用中的条带中具有最高的移动优先级的数据 块与校验块和确定选择的一组条带中的一小部分条带为每个条带进行数据迁移中，RDP编 码扩展算法如下（畑P编码由n块磁盘扩展为n+m块磁盘，n=Pi+1，n+m=P2+1，Pi<P2， Pi和p2是质数）；
[00川获取或计算得出Sid，i，j，n,，nj勺值，新增的磁盘标记为"-^-3至n+y-4
[007引s'id= Sid(条带ID不变）
[0073] k = Sid% Hs
[0074] 若0《k《ns-riss-l (在布局比较中迁移的条带）贝IJ [007引若i+j《Pi_l则
[0076] i' = i，j' = j
[0077]否则i' = i, j' = j+m
[007引若ns-riss《k《n s-1 (在负载平衡检查中牺牲的条带）则[007引若（i = 1, 3, 5,…，Pi_l)且（j = 1, 3, 5,…，n+m-：3)贝Ij
[0080] i' = i，j' = j
[0081]否则i' = i, j' = j+m
[0082] 步骤S4,根据确定的移动扩展前的使用中的条带中具有最高的移动优先级的数据 块与校验块和确定选择的一组条带中的一小部分条带为每个条带进行数据迁移中，P-Code 编码扩展算法如下（P-Code编码由n块磁盘扩展为n+m块磁盘，n = Pi-l，n+m = P2，Pi《口2， Pi和p 2是质数）S' id= S id(条带ID不变）k = Sid% ris
[0083] 若0《k《ns-nrs-1 (在布局比较和负载平衡检查中迁移的条带）贝IJ
[0084] 若为迁移的数据块则基于round-robin顺序分布i'，j'（0含/''含^ ， n《j '《n+m-1)
[00财否则i'=i，j'=j，
[008引若k《n S-1 (负载平衡检查中保留的条带）则
[0087] i' = i, j' = jo
[0088] 其中，i，i'：扩展前/扩展后一个条带中的行ID，
[008引j，j'；扩展前/扩展后一个条带中的列ID，
[0090] Sid，Sid，：扩展前/扩展后的条带ID,
[0091] n^;-个条带集中被牺牲的条带数量（水平编码），
[0092] n,,;-个条带集中被保留的条带数量（垂直编码）。
[0093] 本方法提出了一种新的数据迁移方案W解决RAID-6的扩展，根据对单个/多个条 带的全局，实现数据迁移最小化和校验的修改与计算，该方法通过减少修改校验的次数，异 或计算的次数，总共的1/0操作的次数W及迁移时间来加速RAID-6的扩展过程；该方法使 1/0在磁盘阵列中的磁盘上均匀分布，减少了迁移时间。
[0094] 本说明书中各个实施例采用递进的方式描述，每个实施例重点说明的都是与其他 实施例的不同之处，各个实施例之间相同相似部分互相参见即可。
[0095] 专业人员还可W进一步意识到，结合本文中所公开的实施例描述的各示例的单元 及算法步骤，能够W电子硬件、计算机软件或者二者的结合来实现，为了清楚地说明硬件和 软件的可互换性，在上述说明中已经按照功能一般性地描述了各示例的组成及步骤。该些 功能究竟W硬件还是软件方式来执行，取决于技术方案的特定应用和设计约束条件。专业 技术人员可W对每个特定的应用来使用不同方法来实现所描述的功能，但是该种实现不应 认为超出本发明的范围。
[0096] 显然，本领域的技术人员可W对发明进行各种改动和变型而不脱离本发明的精神 和范围。该样，倘若本发明的该些修改和变型属于本发明权利要求及其等同技术的范围之 内，则本发明也意图包括该些改动和变型在内。
【主权项】
1. 一种提高RAID-6可扩展性的数据迀移方法，其特征在于，包括： 为扩展前编码矩阵的单个数据块与校验块定义不同的优先级； 比较扩展前后的编码矩阵的陈列布局并寻找一个代价最小的方式改变扩展前的使用 中的条带的陈列布局，确定移动扩展前的使用中的条带中具有最高的移动优先级的数据块 与校验块； 根据编码矩阵的条带中数据块的分布，确定选择一组条带中的一小部分条带以进行后 续平衡工作负载； 根据确定的移动扩展前的使用中的条带中具有最高的移动优先级的数据块与校验块 和确定选择的一组条带中的一小部分条带为每个条带进行数据迀移。2. 如权利要求1所述的提高RAID-6可扩展性的数据迀移方法，其特征在于，当所述编 码矩阵为水平编码矩阵，比较扩展前后的编码矩阵的陈列布局并寻找一个代价最小的方式 改变扩展前的使用中的条带的陈列布局，确定移动扩展前的使用中的条带中具有最高的移 动优先级的数据块与校验块包括： 标记扩展后的校验盘，其中，校验盘保留，扩展的磁盘均作为数据盘使用； 标记扩展后的磁盘，其中，将m块磁盘添加到磁盘阵列中，新添加的磁盘被插在所有数 据磁盘的中间，m为正整数； 进行行标记，其中，如果一个扩展前的使用中的条带包含了 1^个数据行，则会在扩展后 的使用中的条带标记上相同的行标识，为正整数； 进行特殊校验处理，以确定移动扩展前的使用中的条带中具有最高的移动优先级的数 据块与校验块。3. 如权利要求2所述的提高RAID-6可扩展性的数据迀移方法，其特征在于，进行特殊 校验处理，以确定移动扩展前的使用中的条带中具有最高的移动优先级的数据块与校验块 包括： 如果水平校验块参加构成了斜向或反斜向校验块，那么水平链中数据块或校验块有着 比斜向或反斜向校验链中更高的优先级； 相反地，如果斜向或反斜向校验块参与构成了水平校验块，那么斜向或反斜向校验块 中的数据块与校验块移动有着比水平链中更高的优先级。4. 如权利要求3所述的提高RAID-6可扩展性的数据迀移方法，其特征在于，当所述编 码矩阵为垂直编码矩阵，比较扩展前后的编码矩阵的陈列布局并寻找一个代价最小的方式 改变扩展前的使用中的条带的陈列布局，确定移动扩展前的使用中的条带中具有最高的移 动优先级的数据块与校验块包括： 进行原始盘标记，其中，原始磁盘标识被保留，而扩展磁盘将用作数据盘； 进行扩展盘标记，将m块盘加入一个阵列中，新加入的m块盘被标记为最后的m列。5. 如权利要求4所述的提高RAID-6可扩展性的数据迀移方法，其特征在于，所述条带 中数据块的分布根据数据块分布的统计信息得到。6. 如权利要求5所述的提高RAID-6可扩展性的数据迀移方法，其特征在于，确定选择 一组条带中的一小部分条带以进行后续平衡工作负载中，水平编码矩阵的一小部分条带因 为较高的迀移代价而进行平衡工作负载牺牲。7. 如权利要求5所述的提高RAID-6可扩展性的数据迀移方法，其特征在于，确定选择
【专利摘要】本发明提供了一种提高RAID-6可扩展性的数据迁移方法，根据对单个/多个条带的全局，实现数据迁移最小化和校验的修改与计算，该方法通过减少修改校验的次数，异或计算的次数，总共的I/O操作的次数以及迁移时间来加速RAID-6的扩展过程；该方法使I/O在磁盘阵列中的磁盘上均匀分布，减少了迁移时间。
【IPC分类】G06F12/08, G06F17/30
【公开号】CN104881372
【申请号】CN201510299943
【发明人】吴晨涛, 过敏意, 李颉, 何绪斌, 黄洵松, 孙耀航
【申请人】上海交通大学
【公开日】2015年9月2日
【申请日】2015年5月31日