新RAID架构下的RAID组成算法设计

对于一个底层使用RAID技术实现的存储系统而言，其可靠性的最重要标志就是RAID重构时间，时间越短，重构完成前再次坏盘的概率越低。
早期存储系统大多使用FC盘且容量仅为几十个G，因此重构时间较短，重构中再次坏盘的概率低。
但随着近年来硬盘容量的快速增长，硬盘读写速度受磁盘转速等多方面影响增长缓慢，已无法满足系统对重构时间的要求。
为此出现了一些新RAID的架构设计，比如华为的RAID2.0、宏杉的CRAID、HP的RAID设计等，基本都是将原有的磁盘分成多个小块，再使用小块组建各个RAID，这些RAID技术的实现，如果仅仅是某个小块有损坏，恢复每一个RAID的数据非常快，但是在整盘都坏掉时，想减少RAID重构时间，就要从重构的数据量上下手。

理论上RAID重构时间 = 数据量 ÷ 硬盘读写速度，而硬盘读写速度能发挥多少依赖于RAID技术的实现，那么在RAID技术不变的情况下，可以有如下方案：
1. 减少重构数据量：与预留空间成反比关系，预留空间越多，重构数据量越少，即以空间换时间；
2. 增加RAID重构并发数：

RAID的重构速度受限于组建RAID中的各个磁盘的读写带宽，以一个RAID重构速度100MB/s为例，实际测试过程中，如果多个RAID中的磁盘有交集，即使多个RAID一起并发重构，也无法减少整体的RAID重构时间，反而会将100MB/s的速度均分到多个RAID中去。所以，增加RAID重构并发数，需要RAID组建算法的支持，其核心思想就是坏掉一块磁盘，多个RAID可以并发做重构操作，而每个RAID除了被拔掉的那块盘有交集，其他无任何交集，即有且仅有一个交集的多个RAID可以并发重构。

基于上述介绍，本文中的算法设计以提高RAID并发重构来减少重构时间，设计时需要考虑：
1. 空间利用率尽可能多；
2. 以RAID5为例，一块物理磁盘异常，可以触发两两并发重构，甚至更多的并发重构，使得理论上减少一半以上的重构时间；
3. 理想状态下，组建的方式可以通过计算公式表达出来。

为了便于查找规律，以6块物理磁盘，RAID5宽度为3举例说明。

先参考下图：


如左侧所示，每一行同样颜色的物理磁盘组建1个RAID5设备，假设拔掉物理磁盘1，则编号0-9的RAID5处于降级状态；
如右侧所示，每个RAID5设备在上面的组合中可以找到3个RAID5设备，有且仅有一个交集。

假设额外还有两个空闲物理磁盘，在上述物理磁盘1异常时，可以选择如下方式进行重构：1和0、2和6、3和9、4和5、7和8。
每个RAID设备可以有3个选择，显然并不是随便选择就一定能找成功的，如下：
当1和0、4和6被选择后，则2只能和7；
    A  3选择5；1-7全部出现，而8只能选择1、4、7，则8无选择，失败；
    B  3选择9；0、1-4全部出现，而5只能选择0、3、4，则5无选择，失败。

6块物理磁盘，按照每个RAID宽度为3组合，以磁盘1固定，则共有C₅²=10种组合方式，上图已经显示了6块物理磁盘时的全部组合，
更进一步的，当磁盘个数达到22时，则会有C₂₁¹⁰=352716种组合方式，显然在没有找到规律前，没有一定的算法支撑，很难从这里面找到两两并发重构的组合。

通过进一步编写代码，并对组合结果进行排序后，发现了一个奇怪的现象(前面有颜色的为1，白色为0)，
如下图（6个磁盘的RAID组合图）：

如下图（8个磁盘的RAID组合图）：

从上面两个图可以看到，左右半边的数字刚好相反。
以磁盘个数为8，RAID宽度4为例，后三列按照：000、001、010、011、100、101、110、111来排列，转换成十进制即为0-7，左边后三列正好相反；
另外还可以看到，以第一列为例，当第一列的磁盘损坏，以行号为RAID编号，0和7、1和6、2和5、3和4可两两并发重建。

至此能够达到两两并发重建的组合方式的规律已经找到：
1. RAID宽度为N，组建RAID的磁盘个数为N*2(不算热备盘)，则组合个数为2^N-1；
2. 以磁盘1为参照物，第一行与倒数第一行匹配，第二行和倒数第二行匹配，以此类推；
3. RAID的组合左右两边对称，只看后半边，其每一行的组合方式为0~2^N-1-1，完全可以根据行号计算出当前行的组合方式；
4. 以不同的磁盘为参照物，某个RAID要找其对应的RAID组合方式，只需要先将上述的数字左移，求得左移后的匹配组合数字，然后再右移就可以得到。

通过上述算法，如果再预留更多的磁盘空间，即减少磁盘利用率，那么某个盘坏掉时，RAID的整盘重构时间可以大大减少。