一种可行的优化降级读性能RAID-6编码算法

来 燃 ，冯兴杰 ，王 晴 ，李 杰 ，焦文欢

（1.中国民航大学信息网络中心，天津 300300；2.天津市大学软件学院信息化部，天津 300387）

进入大数据时代[1]以来，数据规模不断扩大，数据价值日益增长，存储系统的性能和可靠性受到了严重挑战，特别是现代存储系统中设备的数量及容量都在呈指数级增长，数据中心发生磁盘失效以及扇区错误的概率越来越大[2]，存储系统需要在磁盘失效的情况下保障数据的可用性。

目前，用于提高存储系统数据可靠性的数据冗余技术主要分为多路镜像技术和纠删码技术两种。多路镜像技术具有数据可用性高、存储空间利用率低的特点，主要用于数据访问密集型存储系统[3]。纠删码技术在提高存储空间利用率的同时能够提供相同甚至高得多的数据容错能力[4]，RAID-6 MDS（maximum distance separable）编码因其容忍任意2块磁盘失效的能力以及较高的存储空间利用率，得到了学术界和工业界的广泛关注[5]。另一方面，存储系统中磁盘出错已成为一种常态，当磁盘因故障或网络堵塞等原因导致数据不能访问时，存储系统进入降级模式[6]，为了在降级模式下不影响用户的体验，需研究一种可靠的适用于降级读操作的RAID-6编码算法。

为了提高降级读性能，目前的研究主要针对单磁盘错误进行数据重构效率优化[7]。文献[8]提出了RDOR（row diagonal optimal recovery）算法，RDOR同时利用水平校验元素和对角校验元素对失效元素进行重构，不仅在降级模式下读取的数据元素总量最少，而且还实现了磁盘间的负载均衡。文献[9]将RDOR基于构造的优化算法推广到其它水平码中。然而，RDOR算法的思想不能完全适用于垂直码，文献[10]在X-码[11]的基础上提出了一种用于优化读取数据总量的MDRR（minimum disk read recovery）算法，但无法实现磁盘间的负载均衡。针对基于构造的优化算法适用性差的缺点，文献[12]提出一种基于深度优先搜索原理的单磁盘错误重构方法，从而减小降级操作读取的数据总量。文献[13]在已有纠删码的基础上，通过分组方式，将多个纠删码技术叠加构建，极大提高了重构过程的并行度，但存储利用率不高。文献[14]提出的STP算法在条带栈的应用场景下相比文献[12]在重构效率上有较大幅度提升。文献[15]通过压缩水平校验链的长度，有效提高了降级读性能，但负载均衡性能不佳。充分利用RDP码等水平码的优势，提出一种优化降级读性能的RAID-6编码算法。在X-码（垂直码）的基础上将X-码中数据元素的布局方式调整为水平方向，而校验元素的位置及其计算方法保持不变，有效减少了降级读操作所需要的额外I/O开销。

1 问题描述

当存储系统中的一块磁盘出现错误时，存储系统进入降级模式，此时前端用户的读请求操作有可能落在错误磁盘上，系统通过读取其他磁盘上存储的额外元素对用户请求中的失效数据元素进行重构，然后将所有请求的数据（包括可用数据元素和重构数据元素）返回给用户，以完成用户发出的读操作请求。在降级模式下，用户体验是存储系统的重要性能指标。

如图1所示，假设第2块磁盘出现错误（Ci，j表示第i行、第j列的数据元素），用户请求读取10个连续数据元素（从 C0，0开始），RDP 码[16]共需取回 12 个元素，而X-码共需取回16个元素。上述例子说明，由于连续数据元素更有可能共享相同的水平校验链，水平码在降级读操作时某些请求的数据元素会参与到失效元素的重构中，因而减小了降级读操作所造成的额外I/O开销。相比于垂直码，水平码在降级读操作时通常需要读取较少的元素。另一方面，校验链的长度也会影响到降级读性能，校验链的长度越长，当请求读取相同的数据元素时，需要取回的元素总量就越多。因此，如果能缩短水平码的校验链长度，将会进一步提高水平码的降级读性能。

图1 RDP码和X-码在降级读操作方面存在的问题（m=7）Fig.1 Problems of RDP code and X-code in degraded read operations（m=7）

2 研究方法

2.1 构建方法

图2为X-码和优化X-码的布局比较图，其中（X，Y）表示第X条对角校验链、第Y条反对角校验链上的数据元素。图中涉及的7条校验链分别用A～F表示。由图2（a）可以看出，X-码中相同对角校验链上的数据元素和校验元素分布在条带内的不同行上。首先，将X-码的反对角校验行和对角校验行调换位置。然后，在每个条块内部交换数据元素的位置，使得相同对角校验链上的数据元素共享同一水平校验链，进而得到如图2（b）所示的优化X-码布局图。

在优化X-码的构建过程中，每个条块内数据元素的位置相比X-码发生了移动，并且数据元素和校验元素的位置移动只发生在条块内部，这就保证了优化X-码的容错能力不变。优化X-码的构建布局可通过如下递归算法得到，伪代码如下所示。

图2 X-码、优化X-码布局比较Fig.2 Layout comparison between X-code and optimized X-code

输入：

对角校验链序列 M={0，1，2，3，4，5，6，7}

对角校验链个数p

输入数值X-码的所有数据元素组成的序列输出：

输出数值优化X-码的所有数据元素组成的序列

获取列（i*（p-2）+j）%p 中所有数据元素所在的对角校验链序号，进而找到对角校验链序列中不包含的元素m；

删除对角校验链序列中的元素m；

获取数据元素（（p-2）*（i-1）+k）所在的行 r和列c；

if数据元素（q*p+c）所在的对角校验链为m且数

据元素（r*p+c）所在的对角校验链不为m；

then

交换数据元素（q*p+c）和（r*p+c）的位置；

2.2 双盘失效恢复

从优化X-码的构建过程可以看出，优化X-码是在X-码的基础上，通过调整X-码中每个逻辑磁盘上元素的位置，使连续数据元素共享相同水平校验链而得到的。和X-码一样，优化X-码的容错能力仍为2，即在任意2块磁盘并发失效的情况下，优化X-码都可以重构出所有失效的数据元素。不失一般性，假设磁盘2和磁盘3出现故障，磁盘2和磁盘3上的数据元素和校验元素可通过如图3所示方法恢复。

图3 双盘失效重构示例（m=6）Fig.3 Donble disk concurrent failures recovery intance（m=6）

图3是优化X-码双盘失效重构的例子，首先通过水平校验链或对角校验链分别计算出两个起始数据元素A和G，然后根据与数据元素A处于相同对角校验链上的其它元素的异或和计算出数据元素B，由于数据元素B和数据元素C处在相同的水平校验链上，因此数据元素C也可以恢复出来。按照此方法可以恢复所有失效元素，元素的恢复序列为A→B→C→D→E→F，G→H→I→J→K→L，元素M和N分别通过对应的水平校验链或对角校验链恢复出来。

2.3 特性分析

1）存储效率 优化X-码由（m-2）×m个数据元素和2m个校验元素构成，其存储效率为（m-2）×m/（m × m）=（m-2）/m，满足RAID-6 MDS的最优存储效率。

2）编码计算复杂度 优化X-码的每个校验元素由m-2个数据元素计算得到，于是编码所有的校验元素所需的异或操作次数为2m×（m-3），平均每个数据元素的异或操作次数为2m×（m-3）/（（m-2）×m）=2-2/（m-2），满足RAID-6 MDS的最优编码计算复杂度。

3）解码计算复杂度 优化X-码的每个条块包含m个元素，当2块磁盘并发故障时，失效元素的总数为2m，而恢复一个失效数据元素需对应校验链上m-2个存活元素的（m-3）次异或操作次数，于是优化X-码的解码计算复杂度为2m×（m-3）/2m=m-3，满足RAID-6 MDS的最优解码计算复杂度。

4）更新计算复杂度 优化X-码中每个数据元素只属于一个水平校验链和一个对角校验链，并且校验元素之间彼此独立，对于每个数据元素的更新，优化X-码只需更新两个校验元素，满足RAID-6 MDS的最优更新计算复杂度。

3 仿真结果及分析

为了评估优化X-码在降级读操作下的性能，主要关注降级读操作下的平均I/O惩罚因子p，假设L表示前端用户需要读取数据元素的个数，L′表示实际读取元素的个数，则I/O惩罚因子p=L′/L。为此进行如下实验：由于RAID-6编码包含k（k表示数据磁盘的个数）种不同的故障情况，对于每种故障情况，产生一组随机数（S，B，F），如表1所示。其中S为读操作的起始数据元素，B为读取数据元素的长度，F为执行F次起始于数据元素S且读取长度为B的降级读操作次数，计算所有故障情况下降级读操作的平均I/O惩罚因子。

表1 随机读模式(S,B,F)Tab.1 Random read mode(S,B,F)

按照上述实验方法，分别计算X-码、RDP码和优化X-码在不同磁盘数目下的平均I/O惩罚因子，如图4所示。可以看出，使用优化X-码计算出的平均I/O惩罚因子比X-码、RDP码都要小，而X-码的平均I/O惩罚因子最大，进一步说明水平码在降级读操作中的优势。同时，优化X-码的水平校验链长度比RDP码小，读取相同长度的数据元素需要较少的额外I/O开销，因此计算出的平均I/O惩罚因子比RDP码小。

图4 降级读操作下的平均I/O惩罚因子与磁盘数量的关系图Fig.4 Relationship between average I/O penalty factor and disks number under degraded reads

为分析降级读操作下不同读取长度对平均I/O惩罚因子的影响，分别计算不同读取长度下的平均I/O惩罚因子，如图5所示。当读取长度恰好为整个条带时，降级读操作不会带来任何惩罚（p=1）。当读取长度小于整个条带时，随着读取长度的增大，平均I/O惩罚因子会逐渐减小并趋近于1。相比于X-码、RDP码，优化X-码在相同读取长度下的平均I/O惩罚因子最小，特别地，当B=10时，优化X-码相对于X-码和RDP码分别减少了约30%和10%的元素读取。

图5 降级读操作下的平均I/O惩罚因子随读取长度变化曲线图（k=7）Fig.5 Changing trend of average I/O penalty factor with various reading length under degraded reads（k=7）

4 结语

针对传统RAID-6纠删码存储系统在降级模式下读操作性能不足的问题，提出一种优化降级读性能的RAID-6编码算法。充分利用水平码中连续数据元素更有可能共享相同水平校验链的优点，将X-码中对角校验链上的数据元素布局方式调整为水平方向，保持校验元素的位置及其计算方法不变，有效减小了降级读操作的额外I/O开销。优化X-码不仅具有最佳存储效率，而且在编解码计算复杂度以及更新效率上都达到了理论最优。仿真结果表明，该方法在磁盘数量相同的情况下降级读性能优于RDP码和X-码。然而，以上研究只针对单磁盘错误下的降级读性能进行了优化，随着存储规模不断扩大，多磁盘错误的概率会越来越大，下一步将重点研究多磁盘并发失效下的降级读性能优化技术。