刘靖宇,李萧言,李浩鹏,李 娟,武优西
(河北工业大学 人工智能与数据科学学院，天津 300401)
独立磁盘冗余阵列(Redundant Arrays of Independent Disks,RAID)将多个磁盘组合[1],形成统一的逻辑存储设备,实现并行工作以提高存储系统的性能、容量和可靠性[2].随着大数据时代的深入[3],数据指数型增长对RAID的存储能力和I/O带宽提出更高的要求和挑战,提高RAID的可扩展性成为存储系统迫切需要解决的重要问题[4].对于RAID系统的扩展有替换和扩容两种基本策略,替换策略是用新的容量更大的磁盘阵列整体代替旧阵列,数据迁移量大,迁移时间长,无法为用户提供高质量服务响应,且旧磁盘阵列没有充分利用.鉴于这种策略的种种不足,通常选择使用扩容策略,即在现有RAID阵列中增加新磁盘,从而形成具有更大容量和I/O带宽的新磁盘阵列[5].
RAID存储技术经过多年的发展,形成了RAID0,RAID1,RAID4,RAID5等扩容策略应用良好的存储系统.然而在大规模存储系统中,多个磁盘发生故障的可能性更高.RAID1采用的镜像技术具有高数据可靠性但是空间利用率仅有50%,RAID0,RAID4和RAID5无法在多个磁盘失效的情况下提供数据保护.而RAID6采用的双奇偶校验使磁盘阵列在充分利用存储空间的基础上,提高了存储系统的容错能力,被广泛部署在现代存储集群和数据中心,其中以基于最大距离可分码(Maximum Distance Separated,MDS)实现的RAID6最为典型[6].不同于布局相对统一的低层级RAID,基于MDS编码实现的RAID6具有多样性和复杂性,扩容过程中数据布局变化大,使扩容方案的研究面临极大的挑战.
RAID6系统扩容时,为了使新磁盘阵列负载均衡需要迁移部分数据到新磁盘[7].数据迁移会造成额外的磁盘I/O来维持RAID6的双奇偶校验布局,保证存储系统的高可靠性.高效的RAID6扩容方案应在短时间内完成数据重组,且具备数据迁移量少,扩容开销低等特点[8].
目前提出了多种RAID6 MDS阵列码,为RAID0,RAID4和RAID5设计的扩容方案不能适用于这些复杂多样的RAID6编码,因此需要根据各RAID6编码的特点,设计具有针对性的有效扩容方案.N-Code[9]是一种具有最佳存储效率,编解码计算复杂度和更新复杂度的MDS RAID6编码,本文主要解决N-Code RAID6扩容问题.
本文提出一种提高N-Code RAID6可扩展性的新型数据重组方案Cross-Scale.不同于现有研究中的单一扩容方案,该方案根据磁盘阵列剩余空间动态选择扩容方法.本文的主要贡献有:1)定义了扩容阈值,将每个磁盘的剩余空间与扩容阈值作比较选择不同的策略,以适应任意磁盘阵列状态;2)根据N-Code的编码特点提出了阵列标准化策略,使扩容后阵列维持原编码布局;3)提出了快速数据迁移策略来减少奇偶校验更新的开销,提高扩容效率.
2.1 现有扩容方案
传统的基于轮询访问的RR[10]是最简单且应用范围最广的扩容方案,但是重新分布所有数据导致其有接近100%的数据迁移率.Goel Ashish等人提出的SCADDAR[11]利用伪随机函数将计算出的迁移后地址为新磁盘的数据块移动,解决了RR方案中迁移开销高的问题,但是连续多次扩容不能保证数据均匀分布,降低了扩容后的访问性能.Zheng等人提出的FastScale[12]针对RAID0提出将划定的平行四边形区域中的数据迁移到新磁盘,不再要求扩容后的数据满足轮询访问,为之后的扩容方案设计提供了新思路.此外,研究者针对具有相对统一布局的RAID4和RAID5系统提出了多种扩容方案,例如USR4和ISM[13],这些方案在布局简单的低层级RAID上应用良好,但直接应用于复杂多样的RAID6系统时,会带来巨大的扩容开销.
Wang等人提出的SDM[14]针对RAID6提出了一种条带级扩容方案,它将磁盘阵列划分为条带集,其中各条带分别采用了不同的数据迁移方法,根据扩容后的编码布局决定数据移动的位置.近年来根据不同RAID6编码的特点提出了具有针对性的扩容方案.其中Zhang等人提出的RS6是基于横向编码RDP提出的扩容方案[15],RS6为了维持RAID6的编码布局提出了阵列标准化方法,根据最佳迁移参数确定新盘增加的位置和数据迁移区域.数据移动时要充分利用原校验链,采用PiggyBack技术[16]更新校验值,使校验值更新的开销最小.HCS[17]和HS6[18]都是基于H-Code提出的扩容方案,其中Xia等人提出的HCS通过对比扩容前后的阵列选择需要调整位置的对角数据块迁移到相应位置,在扩容过程中不需要更新校验值.Yuan等人提出的HS6体现了最少数据迁移量和快速扩容等特性,最大程度保留了原有的校验数据.Zhang等人提出的Xscale和Jin等人提出的DEC分别基于纵式编码X-Code和D-Code设计了扩容方案,二者划定迁移区域,将其中的数据只迁移到新磁盘,最小化数据迁移量[19,20].
2.2 N-Code编码布局
N-Code是一种RAID6 MDS阵列码,其编码阵列满足(p-1)×(p+1)的布局,p为大于2的质数,水平校验块和对角校验块组成形如字母N的简单几何结构,使布局具有中心对称的特点.校验块分为两个类型:水平校验块放置在中间的p-1个磁盘,对角校验块均匀分布在第一个和最后一个磁盘,数据块分散在所有的逻辑磁盘中.图1为p=5时的一个N-Code编码阵列,相同字母标记的块属于同一校验链,图1(a)所示为水平校验链,图1(b)所示为对角校验链.
图1 p=5时一个N-Code编码阵列Fig.1 Layout and construction rules of N-Code with p=5
2.3 研究动机
通过分析现有的RAID6扩容方案,扩容方案的设计存在两个方面的问题:
1)RAID6扩容方案通常通过条带拼接来维持原编码阵列,逻辑拼接空白条带的方法,校验值更新少,可以大幅度减少扩容的开销,但需要磁盘具有一定的冗余空间[21];多条带之间逻辑拼接的方法没有磁盘冗余空间的限制,但增加了方案设计的难度且扩容开销大.现有方案应用单一的条带拼接方法,缺乏对磁盘剩余空间的定量分析,适用的磁盘阵列状态受到限制.
2)现有的扩容方案中,校验块部署在特定条带或者特定磁盘中,数据迁移时仅考虑数据块的移动即可.而N-Code的校验块分布在所有磁盘上,没有专用的校验盘,扩容时还需考虑校验块的部署,特殊的布局还导致磁盘间紧密耦合,给扩容方案的设计带来困难.
为解决以上问题,本文提出一种基于N-Code编码的快速扩容方案Cross-Scale,提高扩容效率的同时保持了N-Code原编码布局.
Cross-Scale方案中提出了扩容阈值的定义,根据扩容阈值与各磁盘阵列剩余空间的关系选择不同的扩容策略.下面详细介绍Cross-Scale方案的工作原理.
3.1 扩容阈值
为了确定磁盘在何种状态下可以采用拼接空白条带的方式来减少扩容开销,提出了扩容阈值的概念.在磁盘阵列中,每个磁盘划分为大小相同的D个磁盘块,简称块.定义扩容阈值CT(Capacity Threshold)为一个磁盘块数(D)与第t次扩容后一个编码阵列增加的条带数(Sad)占第t次扩容时一个编码阵列条带总数(St)的比值的乘积,如公式(1)所示:
(1)
若磁盘阵列从6块盘(p=5)增加到8块盘(p=7),每个编码阵列中的条带数由4条增加到6条,Sad=2,St=6,那么扩容阈值CT=D×2/6=1/3D.
扩容前将检查旧磁盘阵列中每个磁盘中的空白块数量,第i个磁盘中的空白块数量记为Ti,存储在一个数组中,通过遍历数组,找到阵列中空白块剩余最少的磁盘dmin,磁盘dmin的空白块数为Tmin.若Tmin超过阈值CT,则说明整个磁盘阵列有超过CT条空白条带,即可以采用拼接空白条带的方法.Cross-Scale方案在0≤Tmin RAID6扩容时,随着参数p的改变,编码阵列中的磁盘数与条带数均会改变,扩容前需要确定新磁盘增加的位置和新增条带的位置,这个过程称为阵列标准化. 在一个(p-1)×(p+1)的N-Code编码阵列中,共有p×(p+2)种组合方式.N-Code的编码阵列具有中心对称的特点,则共有p×((p+1)/2+1)个不重复的组合方式.由于N-Code没有专门存放校验块的磁盘,因此扩容时不仅要对数据块进行处理,还要考虑校验块是否满足编码布局.现有的可以应用于N-Code的扩容方案有一大部分扩容开销来源于维持N-Code原编码布局,为了减少这部分扩容开销,Cross-Scale在各种组合方式中选择与扩容后编码布局最相近的组合,即在增加磁盘和条带后选择符合扩容后编码规则最多块数的组合方式. 表1 不同组合方式下符合编码规则的块数Table 1 Number of blocks conforming to coding rules in different combinations 通过取不同p值进行分析,N-Code在其磁盘阵列1/2处增加磁盘且在各编码阵列1/2处增加条带时可以有效减少扩容开销. 对于磁盘的增加,若原磁盘阵列中共有m个磁盘,其中第i个磁盘的磁盘号为di(0≤i≤m-1).增加的新磁盘数为n,编码第t次扩容时的参数p为pt,则n为pt与pt-1的差.这n个新磁盘的原始数据在加入磁盘阵列前将被清零,这个清零操作不会占用扩容时间.新磁盘增加后则根据公式(2)和公式(3)为磁盘阵列重新调整磁盘编号. 第j(0≤j≤n-1)块新磁盘的盘号dj,则: (2) (3) 如图2左图所示,原磁盘阵列有6块磁盘,增加2块新磁盘.此时pt-1=5,若旧磁盘盘号小于3则盘号不变,其它旧磁盘盘号分别增加2,新磁盘盘号经计算分别为3和4. 图2 0≤Tmin 对于编码阵列中的条带,目前已知条带增加的位置,下面介绍增加哪些条带以及如何增加条带. Cross-Scale通过条带拼接的方式来维持N-Code的编码布局,在磁盘的逻辑视图操作,实际上并不会产生数据迁移.磁盘阵列中,所有磁盘上具有相同块号的块构成一个条带(Stripe),一个编码阵列中包含了p-1个Stripes,这部分Stripes的集合称为Set.条带拼接时将部分Stripes逻辑拼接到其它Set中,这部分Stripes称为拼接条带. 情况1.当0≤Tmin 通过旧编码阵列的逻辑条带号Vt-1计算扩容所需的参数,其中L为St-1和St的最小公倍数,一个Region中包含L个Stripes,Region是该条件下扩容的基本单位,各Region中的条带拼接方法是相同的.r为各Region的编号,lr是一个Region中的逻辑条带号,s是一个Region中的Set编号,ls是一个Set中的逻辑条带号.扩容前每个Region中有L/St-1个Sets,扩容后每个Region中有L/(St-1+Sad)个Sets,前L/(St-1+Sad)个Sets保留,调整保留Sets中条带的逻辑条带号为拼接条带的加入提供位置,其余(L/St-1-L/(St-1+Sad))个Sets中Stripes为拼接条带,首先调用Grouping算法将拼接条带分组,再逻辑拼接到保留Set中,最后获得扩容后新阵列的逻辑条带号Vt.SplicingS算法表述如算法1所示. 算法1.SplicingS 输入:扩容次数t,第t-1次扩容的逻辑条带号Vt-1,编码阵列条带数St-1,扩容增加的条带数Sad 输出:阵列标准化后的逻辑条带号Vt 1.L←lcm(St-1,St-1+Sad); 2.r←Vt-1/L; 3.lr←Vt-1modL; 4.s←lr/St-1; 5.ls←lrmodSt-1; 6. IF(s 7. 扫描被保留的Set; 8. IF(ls 9.Vt←r×L+lr+Sad×s; 10. ELSE 11.Vt←r×L+lr+Sad×(s+1); 12. END IF 13.ELSE 14.Grouping() 15.将条带拼接到保留Set中; 16.END IF 17.RETURNVt; SplicingS算法中调用的条带组合算法Grouping将拼接条带分组,该算法使拼接条带具有中心对称的布局,使阵列标准化后对角校验块分布的位置满足编码布局,具体内容如下: 首先获取一个Region中全部拼接条带,一方面自上而下遍历拼接条带盘号为0的块,每找到n/2个存储对角校验值的块,则将这些块所在的条带分为一小组.另一方面自下而上遍历拼接条带中盘号为m+n-1的块,操作与前者相同.最后将组号相同的小组合并成一个组.分组后第一块和最后一块盘中的对角校验块均匀分配,每组拼接条带中各有n/2个条带中的对角校验块来自第一块和最后一块磁盘.Grouping算法表述如算法2所示. 算法2.Grouping 输入:拼接条带集Setsp,编码阵列条带数St-1,扩容增加的条带数Sad,原磁盘数m,增加磁盘数n 输出:条带分组G 1. 将一个Region中所有拼接条带集Setsp合并为Setsum; 2.i←0;j←0;k←0; 3. 自上而下扫描Setsum中盘号为0的块; 4. WHILE(d0==P)DO 5. 将其所在的条带每Sad/2个分为一组,g1[i]←lr; 6. END WHILE 7. 自下而上扫描Setsum中盘号为m+n-1的块; 9. 将其所在的条带每Sad/2个分为一组,g2[j]←lr; 10. END WHILE 11.G[k]←g1[i]∪g2[j]; 12.RETUENG; 如图2所示,在0≤Tmin 情况2.当CT≤Tmin≤D时,条带拼接在空白条带与原条带之间进行,通过算法SplicingB实现,算法中拼接条带增加到保留Set中的位置与SplicingS算法相同,区别在于拼接条带是否包含数据.具体内容如下: 通过旧编码阵列的逻辑条带号Vt-1计算扩容所需的参数,其中s为扩容前各Set的编号,ls是一个Set中的逻辑条带号.将dmin中第一个空白块所在的水平条带记为lmin,lmin之前的条带根据算法调整逻辑条带号,为拼接条带的加入提供位置,lmin之后的条带每n条按顺序分为一组,组号为g,逻辑拼接到与其组号g具有相同Set编号s的保留Set中.如图3所示,调整保留Set中原条带的逻辑条带号,为每组2个拼接条带提供加入的位置,若此时d1为空白块最少的磁盘dmin,从d1第1个空白块所在的stripe开始,每2个stripes顺序分为一组,依次拼接到保留Set中.SplicingB算法表述如算法3所示. 图3 CT≤Tmin≤D时阵列标准化Fig.3 Normalizing operation when CT≤Tmin≤D 算法3.SplicingB 输入:扩容次数t,第t-1次扩容的逻辑视图Vt-1,编码阵列条带数St-1,增加条带数Sad 输出:条带拼接后的逻辑视图Vt 1.s←Vt-1/St-1; 2.ls←Vt-1modSt-1; 3. 从dmin中找到第一个空白块,其行号记作lmin,将lmin后的条带每n条分为一组,组号为g从0至lmin/St-1-1; 4.WHILEVt-1!=DO 5. IF(Vt-1 6. IF(ls 7.Vt←Vt-1+Sad×s; 8. ELSE 9.Vt←Vt-1+Sad×(s+1); 10. END IF 11. ELSE 12. 根据组号g将条带拼接到保留Set中; 13. END IF 14.END WHILE 15.RETURNVt; 数据迁移分为校验块迁移和数据块迁移.阵列标准化之后各Set中数据迁移方式是相同的.下面以一个Set为例介绍数据迁移方式. 校验块迁移只发生在0≤Tmin 图4 从p=5到p=7的数据迁移示意图Fig.4 Data migration during scaling from p=5 to p=7 算法4.MovingP 输入:阵列标准化后逻辑行号Vt,扩容前数据磁盘号db 1. IF(lr∈G)THEN 2. IF(P &&lr∈gu)THEN 3. 水平校验块盘号db循环调整为{m/2,(m+n)/2-1}; 4. END IF 5. IF(P &&lr∈gd)THEN 6. 水平校验块盘号db循环调整为{(m+n)/2,m/2+n-1}; 7. END IF 8. END IF 对于数据块,Cross-Scale方案中根据算法MovingD将数据块迁移.数据块迁移按照两个基本规则进行,以减少检验值的更新:1)数据块迁移始终保持在同一行中进行;2)尽可能多的将数据块移动到原来的对角校验链中. 为方便描述,在一个Set中以拼接条带为横坐标带,新增加的磁盘为纵坐标带,将Set视为4个象限.权衡保留校验链数量和数据迁移量,0≤Tmin 算法5.MovingD 输入:阵列标准化后的逻辑行号Vt,扩容前数据的磁盘号db,数据迁移区域边长e 1. 扫描编码阵列,根据数据迁移区域找到需要迁移的块; 2. IF(数据块位于第3象限)THEN 3.db′ ←(db+n)mod(m+n); 4. END IF 5. IF(数据块位于第1象限)THEN 6.db′ ←(db-n)mod(m+n); 7. END IF 本节对Cross-Scale方案的性能进行分析,并在1.60GHz CPU和2GB RAM的Ubuntu14.0 32位系统上采用磁盘模拟器Disksim进行仿真实验.所模拟的单个磁盘容量为128GB,条带内数据块的大小为64KB,整个仿真过程处于离线模式下.实验中将6块盘组成的RAID6 N-Code在不同数据量的条件下扩容5次,从影响扩容效率的各项因素论证Cross-Scale方案的性能优于目前可以应用于N-Code的扩容方案RR,SCADDAR和SDM.实验图中以整数元组(m,n)表示原始磁盘数量和增加磁盘数量,①表示数据量为D-2CT,②表示数据量为D-CT,③表示数据量为D. 数据迁移率的定义为: (4) RR将所有数据重新布局,产生了巨大的迁移成本.SCADDAR和SDM的大部分数据仅在原磁盘和新磁盘之间迁移,所以数据迁移率低于RR,但由于N-Code的校验块分布在所有磁盘上,没有专用的校验盘,因此需额外迁移数据来维持校验快的布局.不同扩容方案在多次扩容过程中的数据迁移率如图5所示. 图5表明,Cross-Scale方案在不同程度上降低了扩容时的数据迁移率.在写入磁盘的数据量为D时,与其它3种方案相比降低了30.43%～97.40%的数据迁移率,因为只需将划定的迁移区域中的数据块和校验块迁移,而且数据只在原磁盘和新磁盘之间迁移.若写入磁盘的数据量为D-2CT和D-CT,此时CT≤Tmin≤D,进一步分析发现,当n≥(m-2)/2时,数据迁移只发生在原磁盘和新磁盘之间,因此数据迁移率明显低于其它3种方案.而当n<(m-2)/2时,部分数据在原磁盘之间迁移,因此Cross-Scale的数据迁移率存在接近SCADDAR和SDM的情况,但是由划定的迁移区域可知,当CT≤Tmin≤D时一个编码阵列中需迁移((m-2)/2)2+(m-2)/2个数据块,由公式(4)可得其数据迁移率RdCT≤Tmin≤D,如公式(5)所示.由公式(5)可知数据迁移率随着m的增大而减小,即随着磁盘阵列增大,其数据迁移率在不断降低.另外,降低数据迁移率可以减少数据移动产生的I/O,但整个扩容过程的开销由多个因素影响,Cross-Scale方案在最终结果中呈现最优. 图5 数据迁移率比较Fig.5 Comparison of data migration ratio (5) 扩容开销分为I/O操作和XOR操作两部分.在I/O操作方面,扩容过程中的I/O操作来自数据迁移和更新校验值带来的数据读写,不同扩容方案下的I/O操作数如图6所示. 图6 磁盘I/O操作数比较Fig.6 Comparison of the number of disk I/Os 图6表明,Cross-Scale方案在不同扩容情况下其I/O操作数均小于其它3种方案,减少了6.74%～73.37%的I/O操作数.原因在于,RR需要迁移所有的数据块,随着磁盘阵列的扩大,相应需要迁移的数据块增多,I/O操作数明显增长.SCADDAR和SDM虽然降低了数据迁移率,但在更新校验值时需要额外读出其它数据块.而Cross-Scale方案在写入磁盘的数据量为D-2CT和D-CT时,保留了全部原校验链,没有奇偶校验更新,只有数据块迁移,不需要额外读出迁移区域外的数据块,因此减少了I/O操作.当写入磁盘的数据量为D时,每个编码阵列中有2e条校验链采用PiggyBack技术,通过减少更新校验值时额外读出的数据而减少I/O操作次数. (6) 一个校验链中若有bk个有效数据,生成一个校验值则需要bk-1次XOR操作.那么两种扩容方案生成单校验值需要的XOR操作为NXOR1和NXOR2: (7) (8) 因此,若Ns1 图7 XOR操作数比较Fig.7 Comparison of the number of XOR operations calculation 图7表明,当写入磁盘的数据量为D-2CT和D-CT,Cross-Scale消除了XOR操作;当写入磁盘的数据量为D,与其它3种扩容方案相比Cross-Scale减少了6.13%～85.11%的XOR操作数.原因在于,RR和SCADDAR在数据迁移率时未考虑保留原校验链,均需更新全部校验值,且RR校验链数少于SCADDAR,因此具有RR更多的XOR操作.SDM在扩容过程中校验链的数量保持不变且根据水平校验链迁移数据块,但是牺牲了一部分条带来维持负载均衡,增加了对角校验值的修改率.而对于Cross-Scale,当CT≤Tmin≤D时,由于拼接的是空白条带,没有来自其它编码阵列的数据,因此经数据迁移之后所有的校验链保持原链,避免了XOR操作;当0≤Tmin 扩容时间受XOR操作数和I/O操作数影响,其中一个磁盘I/O耗时在毫秒级,相比微秒级的XOR操作对扩容时间的影响更明显.与其它扩容方案相比,Cross-Scale在每次扩容过程中都具有良好的性能,与RR,SCADDAR,SDM相比减少了6.81%～73.39%的扩容时间.不同扩容方案下的扩容时间如图8所示. 图8 扩容总时间比较Fig.8 Comparison of total scaling time 在写入的数据量低于扩容阈值时,0≤Tmin 本文提出一种针对N-Code的扩容方案Cross-Scale.方案中定义了扩容阈值,根据扩容阈值与磁盘阵列剩余空间的关系,选择不同阵列标准化策略和快速数据迁移策略来维持原编码布局,减少奇偶校验更新的开销,提高扩容效率.通过数学分析和仿真实验证明与现有的轮询迁移方案相比,减少了扩容过程中的数据迁移率、XOR操作和I/O操作数,最终缩短了扩容时间,并进一步证明了在磁盘剩余容量充足的情况下选择最佳扩容方案的必要性和有效性.3.2 阵列标准化
3.3 数据迁移
4.1 数据迁移率
4.2 扩容开销
4.3 扩容时间
