2 德州学院 计算机系, 山东 德州 253000;
3 北京理工大学 北京市海量语言信息处理与云计算应用工程技术研究中心, 北京 100081
2 Department of Computer, Dezhou University, Dezhou 253000, China;
3 Beijing Engineering Research Center of Massive Language Information Processing and Cloud Computing Application, Beijing Institute of Technology, Beijing 100081, China
视频监控、连续数据保护(continuous data protection,简称CDP)、虚拟磁带库(virtual tape library,简称VTL)、备份(backup)、归档(archiving)等应用日益广泛,仅就视频监控系统而言,IMSResearch报告2012年市场总规模超过7.5亿美元,存储容量超过3.3EB.存储数据的快速增长,使该类存储系统的能耗急剧增加,对该类存储系统进行节能研究是及其必要的.该类存储系统具有特定的数据访问模式和存储特性,例如:以顺序数据访问为主,对随机性能要求不高;对数据的可靠性、存储空间要求较高;以写操作为主,读操作通常回放写操作,称该类存储系统为连续数据存储系统[1,2].
基于连续数据存储系统的存储特性,文献[1]提出了S-RAID 5节能磁盘阵列,根据存储应用的实际性能需求,提供合适的局部并行度,而不是像RAID 5那样全局并行.局部并行便于在保证性能需求的前提下,调度空闲磁盘,待机实现存储系统节能.在连续数据存储应用中,在满足性能需求及单盘容错条件下,S-RAID 5可获得显著的节能效果.文献[2]进一步从文件系统、元数据管理等方面对S-RAID 5进行了优化,有效提高了S-RAID 5的性能和节能效果.
但是,S-RAID 5的局部并行数据布局会导致S-RAID 5基本执行小写(small write)操作,也称读改写(read modify write),即:写新数据时,需要先读取对应的旧数据、旧校验数据,与新数据一起生成新校验数据后再写入新校验数据,严重影响了性能.与RAID 5等基本磁盘阵列相比,S-RAID 5的小写问题更加突出,原因如下[1,2]:
· S-RAID 5的数据布局及优化策略(如Cache策略、文件系统选择与优化),均以如下内容为目标:在充分长的时间内,把I/O访问集中在部分并行工作的磁盘上,从而调度其他磁盘待机节能;
· 即使有机会执行重构写,S-RAID 5通常依然会执行小写,因为执行重构写需要启动所有磁盘,会降低S-RAID 5的节能性.
实验测试结果表明,小写使S-RAID 5中的单盘有效写带宽的极限值(100%顺序写)不到其最大写带宽的一半.为了提供额定的写性能,S-RAID 5必须运行更多磁盘以弥补小写带来的性能损失,从而会消耗更多能量.因此,S-RAID 5的节能效率亟待提高.
已有的小写优化策略主要面向RAID 5[3,4]、RAID 6[5]等基本磁盘阵列,S-RAID 5的局部并行数据布局使已有研究难以有效解决其小写问题.舒继武等人[6]提出的DACO磁盘架构包括读、写、复合3种基本操作,其中,复合操作采用流水技术实现块级数据的读改写操作.容易推论,DACO磁盘能够解决S-RAID 5的小写问题.但该磁盘目前仍处于理论研究阶段,大规模的商业应用前景仍不明朗.
另一方面,连续数据存储应用以顺序访问为主,存在少量随机访问.对存储容量的需求,使磁盘成为首选的存储设备.根据磁盘存储特性可得:即使少量随机访问也会显著降低磁盘性能[7].因此,需要采取合适的措施减少随机访问,充分发挥磁盘的性能.
为此,我们提出一种面向连续数据存储的高效能盘阵——Ripple-RAID,采用了新的局部并行数据布局,并综合运用了以下策略,以实现高性能和高节能效率:
· 地址映射:把非顺序写转化为顺序写;
· 异地更新:把存储空间划分成若干个相等的存储区,其中之一作为影子区,更新存储区A(源存储区)时,数据实际写入影子区;影子区写满后,修改映射表使它取代存储区A;下一个循环中,存储区A作为影子区,缓存其他存储区的写数据,…,依此类推;
· 渐进生成校验数据:写数据与影子区已有校验数据(初始时无数据)一起生成新校验,随着影子区中数据的增加,校验数据的校验范围也逐渐扩大.生成新校验时无需读取旧数据,当采用流水方式读取影子区已有校验、写入新校验时,可消除读校验数据对性能的影响;
· 分段数据容错:联合影子区、源存储区实现数据恢复,可提供与RAID 5相同的单盘容错能力.
在单盘容错的条件下,Ripple-RAID保持了局部并行的节能性,又解决了局部并行带来的小写问题,具有突出的写性能和节能效率.实验结果表明:在80%顺序写负载下,当请求长度为512KB时,Ripple-RAID的写性能为S-RAID 5的3.9倍,是Hibernator、MAID写性能的1.9倍,PARAID、eRAID 5写性能的0.49倍;而比S-RAID 5节能20%,比Hibernator、MAID节能33%,比eRAID 5节能70%,比PARAID节能72%.连续数据存储中的读操作以数据回放(重复某时间段内的写操作)为主,因此,Ripple-RAID一般具有与写性能接近的读性能.
1 相关工作 1.1 节能研究现状大数据(big data)时代正在来临,全世界每天产生5万亿字节的数据,这些数据来自各类传感器、视频监控、医疗影像、社交网络等,数据的增长速度远超过摩尔定律的增长速度[8],由此导致存储能耗持续增长.在Dell PowerEdge 6650服务器中,存储系统能耗占总能耗的71%[9].在EMC Symmetrix 3000存储系统中,86%的能耗是磁盘驱动器产生的[10].存储系统节能研究是近年来存储领域内的热点问题,并取得一些重要的研究成果[9, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20].总结已有研究,节能策略可大致分为以下两类.
1.1.1 利用存储设备的空闲时间或负载变动情况节能现代磁盘一般具有读写、空闲和待机这3种工作模式,读写时,盘片全速旋转,进行寻道及数据传输;空闲时,盘片全速旋转但停止了寻道及数据传输;待机时,盘片也完全停止转动.不同模式下的功耗也不同,基本的节能算法是当磁盘空闲时间达到一定值后,把磁盘转入到低功耗的待机模式,当请求到来时再转入到读写模式,称为TPM(traditional power management)算法[11].
Gurumurthi等人[11]认为,在企业级工作负载中没有足够长的空闲时间供TPM算法利用,因此提出了DRPM (dynamic rotations per minute)算法:采用动态多转速磁盘,以平均响应时间和请求队列长度为指标,根据工作负载的变动情况动态调整磁盘转速以实现节能.
Carrera等人[12]通过实验进一步指出:对于性能要求严格的企业级工作负载,采用动态多转速磁盘是唯一可行的节能方法,并提出LD(load directed)算法:根据工作负载调整磁盘转速,当磁盘工作负载小于低速吞吐量的80%时,磁盘转入低速模式;大于该值时,转入高速模式.
Zhu等人[9]基于动态多转速磁盘技术,提出了Hibernator节能存储系统:存储系统由多个具有不同转速的RAID组成,在存储系统最小能耗和满足性能需求的约束下,利用线性规划方法优化配置了每个RAID中的磁盘数量和转速,并在各个不同转速的RAID之间动态迁移磁盘,以实现存储系统的最小能耗.
Weddle等人[13]根据特定工作负载的周期波动特性,借鉴汽车换挡原理,提出了PARAID节能磁盘阵列. PARAID采用倾斜式条带划分方式,在同一组磁盘中构建多级包含不同磁盘数的RAID 5,根据工作负载的变动情况,动态调度不同RAID 5的工作以实现节能.
1.1.2 为存储设备创造空闲时间“热”数据集中(popular data concentration,简称PDC)方法[14]根据数据的访问频率进行数据迁移,将访问频率较高的文件迁移到部分磁盘上,而将闲置文件集中到另外一些磁盘上,使闲置文件所在磁盘可长时间待机节能.在视频监控等连续数据存储应用中,数据的访问频率基本服从均匀分布,因此难以应用PDC方法实现节能.
MAID(massive arrays of idle disks)[15]使用少量额外磁盘始终运行,作为Cache盘保存经常访问的“热”数据,以减少对后端阵列的访问,使后端阵列具有较长的待机时间以实现节能.
在多数据卷存储系统中,Write Off-Loading方法[16]把待机数据卷(数据卷中的磁盘待机)的写请求暂时重定向到存储系统中某个合适的活动数据卷上,以延长待机数据卷的待机时间,降低磁盘启停的切换频率,并在适当时机恢复重定向的写数据.该方法不适合应用于以写操作为主的连续数据存储中.
Pergamum[17]针对归档存储系统,在每个存储节点添加少量NVRAM来存储数据签名、元数据等小规模数据项,从而使元数据请求以及磁盘间的数据验证等操作均可在磁盘待机状态下进行.归档系统的数据访问方式比较简单,如写一次、可能读、新写数据与旧数据不相关[17]等.该方法不适合一般的连续数据存储应用,如在视频监控系统中,当存储空间写满后,会删除最早的视频数据以容纳新数据,需要执行多次写操作.
Li等人提出的EERAID[18]将RAID内部的冗余信息、I/O调度策略、Cache管理策略结合起来,并采用NVRAM优化写操作,使冗余磁盘可长时间待机节能.在此基础上,该小组又提出了eRAID[19],利用RAID中的冗余特性来重定向I/O请求,进一步延长了冗余磁盘的待机时间,并将系统性能降低,控制在一个可接受的范围内.
毛波等人[20]提出一种绿色磁盘阵列GRAID,为RAID10增加了一个日志盘,周期性地更新镜像磁盘上的数据,将两次更新之间的写数据存放到日志盘和主磁盘上,从而能够关闭所有的镜像磁盘以降低能耗.GRAID适合对随机性能要求较高的存储应用.
综上,存储系统已有的节能研究主要面向以随机数据访问为主的数据中心,如联机事务处理(on-line transaction processing,简称OLTP)等,没有充分利用连续数据存储系统的存储特性,因此在连续数据存储中节能效果有限.连续数据存储系统存在着足够的节能优化空间,需要开展细粒度、针对性的节能研究.
1.2 节能研究的发展趋势存储领域正经历着巨大而深刻的变革,主要包括如下两个方面.
首先,以NAND Flash为代表的半导体存储器件开始大规模应用到存储领域,其他类型的存储器,如磁随机存储器(magnetic random access memory,简称MRAM)、相变存储器(phase change memory,简称PCM)等也日渐成熟.基于上述存储器的固态盘(solid state disk,简称SSD)已经成为一种重要的外存储器.
SSD具有突出的随机读写性能以及低功耗等特点,受限于存储单元集成度和单位存储价格,在可预见的将来,SSD难以在海量数据存储中彻底取代磁盘[21].磁盘技术仍在不断进步,通过采取各种有效的方法减小寻道时间,磁盘性能保持了40%的年增长率.磁盘的顺序读、写性能非常突出,如7 200转的希捷ST32000644NS磁盘,其最大持续数据传输率为140MB/s,与基于NAND FLASH的中端SSD相当[22].磁盘在存储容量方面更具突出优势,采用垂直记录技术后,2014年,记录密度从每平方英寸1.2增加到2.4万亿比特[22].
其次,大数据日益受到密切关注,大数据的4个特点[8],即数据量(volume)大、数据类型(variety)多、价值密度(value)低、处理速度(velocity)快,对云(cloud)中的存储服务——云存储提出了更严格的要求,既要具有海量存储空间,又要提供足够的存储性能.而目前的SSD、磁盘等外存储器,均无法单独满足以上存储需求.
因此,构建基于SSD与磁盘的混合[23]或分层存储系统[24],是节能研究的一个发展趋势.SSD主要面向随机性、波动性、突发性的工作负载;磁盘存储主要面向稳定的工作负载,或与SSD之间进行稳定的数据传输,以顺序数据访问为主,同时满足存储容量需求.可以预测:随着SSD更大规模地进入存储领域,云存储中SSD层的容量将逐渐扩大,进而成为主要存储层;而后端的磁盘阵列功能将逐渐退化为近似于备份、归档的功能,以顺序访问为主.因此,现在及未来的云存储需要一种面向顺序数据访问的高效能盘阵,在充分发挥磁盘性能的同时,具有更高的节能效率.
只有在满足性能需求的前提下进行节能研究才有意义.根据对平均响应时间、最大响应时间的敏感程度,文献[25]把存储应用分成不同的类型.存储应用性能需求的多样性,要求根据具体应用的存储特性、性能需求开展针对性的节能研究,这是存储系统节能研究的又一个发展趋势.基于存储系统节能研究的以上发展趋势,我们提出了一种面向连续数据存储的高效能盘阵Ripple-RAID.
2Ripple-RAID的实现Ripple-RAID的实现主要包括数据布局、写操作方法、数据恢复3方面内容,其中,写操作方法又包括地址映射、异地数据更新、基于流水渐进生成校验等内容.
2.1 数据布局设Ripple-RAID由N块磁盘组成,每个磁盘平均分成N+1个存储区(严格定义应为kN+1个存储区,k为大于0的整数,通常取1,这里以k=1为例进行说明),每个存储区称为Band.N个相同偏移量的Band组成一个Bank,共组成N+1个Bank,任取其一作为影子Bank(shadow Bank),其余为基本Bank.每个基本Bank包含1个校验Band、N-1个数据Band.在基本Bank i中,校验Band记为PBand i,位于磁盘N-1-i;第v个数据Band记为DBand(i,v),当i+v<N-1时,DBand(i,v)位于磁盘v,否则位于磁盘v+1.其中,0≤i<N,0≤v<N-1.PBand i的值由公式(1)通过异或运算求得:
${\rm{PBand}}\,i\, = \mathop \oplus \limits_{v = 0}^{N - 2} \,{\rm{DBand}}(i,v)$ | (1) |
图 1给出了一个包含5个磁盘的Ripple-RAID的总体数据布局.
令每个Band包含M个大小相等的Strip(也称Chunk,由一些地址连续的数据块组成),每个Bank中,相同偏移量的Strip组成一个条带(Stripe),这里的Strip,Stripe和RAID 5中Strip,Stripe的含义基本相同[26],但在Strip间的地址分配上明显不同.为表述方便,把PBand中的Strip称为PStrip.图 2给出了上述Ripple-RAID内基本Bank 0的数据组织方式.
为了提供合适的性能,Ripple-RAID采用如下局部并行数据来布局:把每个基本Bank中的N-1个数据Band平均分成P组,每组包含Q个.每组中偏移量相同的Strip能够被并行访问,每个Stripe中仅部分Strip提供并行性.如图 2所示,Bank 0包含2个组(group),每组含有2个数据Band(P=2,Q=2),其中,group 0包含DBand(0,0)和DBand(0,1),group 1包含DBand(0,2)和DBand(0,3).在group 0中,DBand(0,0)的Strip 1和DBand(0,1)的Strip 1并行工作,不像RAID 5那样,Stripe中所有Strip并行工作.
Ripple-RAID仅对基本Bank进行分组,影子Bank不参与分组,也不参与编址,对Ripple-RAID的上层应用是透明的.在组地址分配上,Ripple-RAID采用了适度的贪婪策略:在每个基本Bank中,序号相邻的组的逻辑地址相邻.如图 3所示,在Bank 0中,group 0与group 1的逻辑地址相邻.设NumBlkStrip为Strip包含的数据块数,则Bank i,group p,Band q中第m个Strip的逻辑地址见公式(2):
Stripi,p,q,m(addr)=NumBlkStrip(M×Q×P×i+M×Q×p+Q×m+q) (2)
这里,0≤p<P,0≤i<N,0≤q<Q,0≤m<M.
Ripple-RAID的数据布局和编址方式能够提供足够的并行度,并且对于连续数据存储应用,可保证I/O请求在很长的时间内集中在一个或几个group中(1个group可包括几个DBand,而Ripple-RAID中的DBand又足够大),其他多数磁盘有足够长的待机时间,可调度到待机模式以节约能耗.
需要阐明如下问题:在连续数据存储应用中,通过调整RAID 5中Strip的大小,不能获得与Ripple-RAID类似的节能效果.原因如下:
· 如果RAID 5的Strip足够大,执行读写请求时,单个磁盘的访问时间将被延长,在很长一段时间内仅有一个磁盘被访问,因而难以提供足够的并行性以满足性能需求;
· 如果RAID 5的Strip不足够大,则同一条带中的Strip在较短时间内会被频繁访问,没有机会调度磁盘待机节能,
在Ripple-RAID中,Strip大小没有限制,可以根据实际需要进行设置.
2.2 写操作方法Ripple-RAID的写操作方法综合运用了地址映射、异地数据更新、渐进生成校验等策略,生成校验数据时无需读取旧数据,当采用流水方式读取已有校验(与旧校验不同)、写入新校验时,可有效解决局部并行带来的小写问题.此外,地址映射把非顺序写转换成顺序写,又进一步提升了Ripple-RAID的写性能.
2.2.1 地址映射顺序数据访问能够充分发挥磁盘性能,如:日志文件系统(log-structured file system)[27]创建或改写文件时,新数据以顺序写方式添加到日志中;网络文件系统Zebra[28]把每个客户端的写数据组成一个连续的日志,条带化后,分布存储到各服务器上.以上方法均把多个小的、随机写操作转换为大的、顺序写操作,以提高存储系统的写性能.
连续数据存储系统非常适合进行地址映射.首先,该类系统以写操作为主,把非顺序写转换为顺序写后,可显著提高写性能和整体性能;其次,读操作以数据回放为主,即,重复以前某时间段内的写操作,如视频监控中的视频回放等,通常可获得与写性能接近的读性能.
常见的地址映射方法有单块映射和块组映射.单块映射需要记录每个数据块的映射关系,多块映射时效率不高,典型应用有NILFS[29]文件系统;块组映射以若干个连续数据块为单位进行映射,多块映射时效率高,但存在块组数据的“读写”问题,即,改写块组中部分数据时,需要读取其余未修改数据,与新数据一起重新进行地址映射,典型应用有HP AutoRAID[30],块组大小为64KB.
连续数据存储系统以写新数据为主,较少进行改写操作,适合采用块组映射.地址映射信息为存储容量的8/(1024xx),其中,8个字节(64位)记录一个块组地址,x为块组大小以KB为单位.当Ripple-RAID的存储容量为30TB、块组大小为64KB时,地址映射信息仅为3.67GB,适合采用SSD进行存储,运行时甚至可以完全调入内存,以加快读、写操作中的地址转换速度.
把非顺序写转换为顺序写,需要面对垃圾回收(garbage collection)[27]问题,垃圾存储空间是由改写操作产生的,在连续数据存储中,如视频监控、CDP、备份、归档等应用,改写的数据量不大,可在负载较轻时进行垃圾回收;如果追求性能,也可牺牲少量存储空间而忽略垃圾回收.
2.2.2 异地数据更新地址映射把非连续的虚拟地址映射为连续的物理地址,并在映射表中记录映射关系.其中,虚拟地址为应用程序发来的读写请求地址,物理地址为数据在Ripple-RAID内的存储地址(影子Band不参与编址).在此基础上,Ripple-RAID执行异地数据更新:向某物理地址写数据时,数据不直接写入该地址,而是写入其影子地址(影子Bank中与其偏移量相同的地址),并在适当时候修改映射表,令影子地址取代该物理地址.异地数据更新在NAND Flash中也有应用,因NAND Flash无法实现数据的就地改写[22].
假设Ripple-RAID由N块磁盘组成,划分出N+1个Bank,任取其中之一作为影子Bank,其余为基本Bank,则Ripple-RAID的异地数据更新过程如下:
(1) 向某基本Bank(称源Bank)写数据时,数据并不直接写入该Bank,而是写入影子Bank;
(2) 根据写入数据、本次循环中影子Bank中已写数据的校验数据,生成影子Bank的新校验数据;
(3) 如果影子Bank未写满,转到步骤(1);
(4) 否则,修改地址映射关系,令影子Bank取代源Bank,本次循环结束;
(5) 被取代的源Bank此时无映射关系,可在下一循环中作为影子Bank.
在以上写操作过程中,由于进行了地址映射,所以是依次向每个基本Bank顺序写入数据的,不会同时向两个基本Bank写数据,也不会在一个基本Bank未写满的情况下,向另外一个基本Bank写数据.
2.2.3 渐进式生成校验影子Bank的校验数据是根据本次循环中已写数据生成的,称为局部校验数据(不同于旧校验).写新数据时,可根据新数据、局部校验数据计算新校验数据,无需读取旧数据.随着写数据的增加,局部校验数据的校验范围也渐进扩大,直至扩展到整个影子Bank.局部校验数据的校验范围以及新数据的写入,如水中涟漪一样向前推进,因此,该盘阵命名为Ripple-RAID.
I. 相关流水(relevant pipeline)方式
渐进生成校验数据时无需读取旧数据,仅需读取局部校验数据,因此可增加一个辅助存储设备,与影子Bank中校验数据所在磁盘,以流水方式生成新校验(1个读局部校验数据,1个写新校验),此时,可有效消除读校验数据对写性能的影响.
图 4给出了一个Ripple-RAID的写操作示例,其中,每个Bank包含3个group,IParity (intermediate parity)为辅助存储设备,暂存影子Bank中的局部校验数据.与PBand容量相同,阴影部分为局部校验数据的校验范围,具体执行过程如下:
(1) 向任一基本Bank(称源Bank)的group 0写数据时,数据实际写入影子Bank的group 0,并生成group 0的校验,写入影子Bank的PBand,如图 4(a)所示;
(2) group 0写满后,向源Bank的group 1写数据时,数据实际写入影子Bank的group 1,并根据写数据、局部校验(group 0的校验,在影子Bank的PBand),生成新校验(group 0,group 1的校验),写入IParity,如图 4(b)所示;
(3) group 1写满后,向源Bank的group 2写数据时,数据实际写入影子Bank的group 2,并根据写数据、局部校验(group 0,group 1的校验,在IParity),生成新校验(group 0,group 1,group 2的校验),写入影子Bank的PBand,如图 4(c)所示;
(4) 影子Bank写满后,修改映射表,令其取代源Bank,而源Bank作为下一循环中的影子Bank.
为保证最后生成的校验数据写入影子Bank的PBand,需按如下规则流水:若影子Bank的group数为奇数,则首先向PBand写校验数据,如图 4(a)所示;否则,首先向IParity写校验数据.当IParity采用低功耗的SSD时,其能耗增加可以忽略.影子Bank中校验数据所在磁盘,与辅助存储设备一起进行流水,所以该流水方式称为相关流水.
II. 基于SSD的非流水方式
采用SSD作为IParity时,可不采用流水方式生成校验数据:从IParity读局部校验数据,新校验数据也写入IParity,直至写最后group数据时,从IParity读局部校验数据,并将新校验数据写入磁盘.影子Bank中校验数据所在磁盘大部分时间也可待机,节能效果将进一步得以提升,但生成校验时需要同时读、写IParity,对写性能有一定影响,称该方式为基于SSD的非流水方式.
III. 无关流水(irrelevant pipeline)方式
为使影子Bank中校验数据所在磁盘大部分时间也可待机,进一步提高节能效率的同时又不影响性能,可采用如下流水方式:设置两个辅助存储设备IParity 1和IParity 2,轮流从其中之一读局部校验数据,向另一个写新校验数据,直至生成影子Bank的最终校验数据,再将其写入磁盘.影子Bank中校验数据所在磁盘不参与流水,因此该流水方式称为无关流水.当IParity 1和IParity 2均采用低功耗的SSD时,其能耗增加可以忽略.
图 5给出了一个基于无关流水的Ripple-RAID写操作示例,其中每个Bank包含3个group,IParity 1和IParity 2为辅助存储设备,用于流水生成影子Bank的局部校验数据,容量与PBand相同,阴影部分为局部校验数据的校验范围.该写过程与相关流水方式相似,仅有几点不同之处:
(1) 向group 0写数据时,生成的局部校验(group 0的校验)写入IParity 1,如图 5(a)所示;
(2) 向group 1写数据时,根据写数据、局部校验(group 0的校验,在IParity 1),生成新校验(group 0,group 1的校验),写入IParity 2,如图 5(b)所示;
(3) 向group 2写数据时,根据写数据、局部校验(group 0,group 1的校验,在IParity 2),生成最终校验(group 0,group 1,group 2的校验),并把最终校验写入影子Bank的PBand,如图 5(c)所示.
2.3 数据容错性质1. Ripple-RAID具有单盘容错能力.
证明:假设Ripple-RAID包含N块磁盘,其中的N+1个Bank分为1个影子Bank和N个基本Bank,每个基本Bank包含N-1个数据Band(分成P组,每组Q个)和1个校验Band,Band大小均为M个Strip.按当前状态(是否正在被更新)把基本Bank分为活跃Bank(active Bank)和睡眠Bank(inactive Bank)两类,影子Bank的数据组织方式与活跃Bank相同.
由于地址映射后执行顺序写,因此在确定时间内,只有1个基本Bank被更新,即:只有1个活跃Bank,其余皆为睡眠Bank.为了便于理解,证明过程中给出了1个Ripple-RAID示例,包括7块磁盘,分为1个影子Bank和7个基本Bank,每个基本Bank中的数据Band分为3组,每组包含2个数据Band,即P=3,Q=2.
情况1:对于睡眠Bank,其任一条带Stripe m包含P×Q个Strip m,被平均分成P组,每组包含Q个,0≤m<M,如图 6所示,假设当前睡眠Bank为Bank 1.
根据Ripple-RAID的写过程,可得公式(3)成立,当根据公式(3)生成PStrip m后,直到该睡眠Bank成为活跃Bank之前,该条带中的P×Q个Strip m以及PStrip m均未被修改过,已建立的校验关系有效.因此,任一磁盘出现故障时,可根据公式(3)实现数据恢复.
情况2:对于活跃Bank,以最后一次局部并行写为分界线,分界线之前为已写区,其后为待写区.设分界线位于第p组中偏移量为m的Strip之后,0≤p<P,0≤m<M.例如,图 7中活跃Bank(假设为Bank 0)的分界线位于第1组(p=1)中偏移量为m的Strip之后(活跃Bank的已写区为正体,待写区为正体加粗).
I. 对于活跃Bank的已写区数据,由于对应的新数据及其校验数据全部写入影子Bank(斜体),所以在影子Bank中具有完整、有效的校验关系.对于影子Bank中的条带Stripe k,当0≤k≤m时,其校验关系见公式(4).
如图 7中影子Bank的Stripe 0所示,有2组(p+1=2)共4个(每组2个)Strip 0参与校验,×表示该数据未参与本条带校验运算.当m<k<M时,在影子Bank中存在条带Stripe k(仅当p≥1时存在该情况),其校验关系见公式(5).
如图 7中影子Bank的Stripe M-1所示,有1组(p=1)共2个(每组2个)Strip M-1参与校验.因此,当任一磁盘出现故障时,对于活跃Bank的已写区数据,可根据影子Bank中条带的位置,利用公式(4)或公式(5)实现数据的恢复.
II. 对于活跃Bank的待写区数据,当0≤k≤m时,条带Stripe k的校验关系见公式(6).
其中包括p+1组位于活跃Bank已写区的数据,如图 7中活跃Bank的Stripe 0所示,有2组(p=1)数据位于已写区.当m<k<M时,条带Stripe k的校验关系见公式(7).
其中包括p组位于活跃Bank已写区的数据,如图 7中活跃Bank的Stripe M-1所示,有1组(p=1)数据位于已写区.由于活跃Bank中已写区数据在校验关系建立后并没有被真正修改过(新数据被写入影子Bank的对应位置),公式(6)、公式(7)表示的校验关系仍然有效,因此,当任一磁盘出现故障时,对于活跃Bank的待写区数据,可根据活跃Bank中条带的位置,利用公式(6)或公式(7)实现数据的恢复.
综合情况1、情况2可得,Ripple-RAID具有单盘容错能力.Ripple-RAID的分界线(最后一次局部并行写位置)对于实现数据恢复至关重要,因此需要记录到元数据中,以保证数据恢复的正确执行.上述容错能力的证明过程也是Ripple-RAID的数据恢复过程,可得其数据恢复时间与RAID 5和S-RAID 5相当. □
3 实验测试 3.1 实验环境为了测试Ripple-RAID的性能和节能效果,利用Linux 2.6.26内核中的MD(multiple device driver)模块构建了一个Ripple-RAID的原型系统.监控进程Diskpm对磁盘进行节能调度,采用TPM调度算法,当磁盘空闲时间达到120s时,调度该磁盘待机.采用文献[2]中的Cache策略,以减少少量读操作对待机磁盘的访问.
基于典型的连续数据存储应用——视频监控进行了性能、节能测试.模拟了一个32路视频监控系统,采用D1视频标准(平均码率为2Mb/s),需要保存24h/天x30天的视频数据,数据量为20.74TB.每隔指定时间(实验中为10分钟)在存储设备上创建32个视频文件,分别保存该时间内的各路视频数据,视频数据以添加(append)方式写入视频文件,当存储空间不够时,删除最早存储的视频数据.
选取了几种典型的RAID节能方法与Ripple-RAID进行冗余磁盘、性能和节能比较,具体包括Hibernator,PARAID,eRAID 5,MAID以及S-RAID 5.功耗测量系统如图 8所示,包括1台运行Linux 2.6.26的存储服务器、磁盘阵列(类型及盘数需分别设定)、测控计算机、电流表以及电源等部分.存储服务器配置如下:Intel (R) Core (TM) i3-2100 CPU,8GB内存,主板型号为ASUS P8B-C/SAS/4L,主板上集成的LSI 2008 SAS存储控制器在背板上扩展出32个SAS/SATA盘位,选用2TB的希捷ST32000644NS磁盘.
磁盘功率测量如图 9所示,利用电流表测量磁盘工作电流,测控计算机负责设定电流采用频率,并在测量结束后读取测量值,电流表通过LAN线与测控计算机相连.采用GW PPE-3323高精度稳压电源为磁盘提供+5V和+12V电压,利用Agilent 34410A数字万用表分别测量并存储其电流值.最后,测控计算机根据电流、电压值计算出功率值及总功耗.
每种节能方法的功耗测量时间为24小时,电流采样频率为5Hz,Strip(也称Chunk)大小为64 KB.与S-RAID 5不同,由于在块层进行了地址映射,Ripple-RAID的节能效果对文件系统的选择不敏感.但为了公平比较,选择了相同的NILFS文件系统,该文件系统非常适合视频监控等连续数据存储应用.
3.2 冗余磁盘需要保存的视频数据量为20.74TB,所以需要11块容量为2TB的磁盘.考虑到文件系统对存储空间的额外消耗,约为存储空间的10%,取12块磁盘保存基本数据.
Ripple-RAID需要1块磁盘的校验数据,共需13块磁盘.当映射块组大小为64KB时,24TB (2TBx12)的存储空间需要2.93GB的地址映射信息(计算方法见第2.2.1节),采用镜像保护方式并取整为6GB;辅助存储设备IParity的容量与PBand相同,大小为140GB(2000GB/(13+1));影子Bank需求(N-1)/(N+1)块磁盘的存储空间,上述配置能够满足.
Hibernator把不同转速的磁盘组成不同的RAID,由于磁盘有运行和待机两种转速,需要构建2个RAID,分别处于运行和待机状态,并根据性能需求在2个RAID间迁移数据盘.因此,需要2个磁盘的校验信息,共需14块磁盘;PARAID中跨越磁盘数最少的逻辑RAID的节能效果最好,由于每级逻辑RAID都需要保存1份完整的存储数据,因此在最节能逻辑RAID中要保存12块磁盘的数据量,加上1块磁盘的校验信息,共需13块磁盘; eRAID 5需要1块盘的校验信息,共需13块磁盘;MAID由2个磁盘阵列组成,前端阵列保存“热”数据以减小对后端阵列的访问,全部数据保存在后端阵列中,前端阵列为由4块磁盘组成的RAID 5(原因见第3.3节),后端阵列为由13块磁盘组成的RAID 5,共需17块磁盘;S-RAID 5需要1块磁盘的空间存储校验信息,共需13块磁盘.
综上,配置以上节能RAID所需的冗余磁盘数,除MAID略高(5块)外,其余均为1或2块,Ripple-RAID接近但小于2块.此外,Ripple-RAID以相关流水生成校验时需要146GB(IParity及映射信息)的SSD,无关流水时需要286GB(IParity 1,IParity 2及映射信息)的SSD,不超过总存储容量的2%,在海量数据存储中是可以接受的.
3.3 性能测试32路D1标准的视频监控系统所需基本写带宽为8MB/s(32x2Mb/s),写性能要求不高.但是为了保证具有足够的性能裕量,要求每种节能方法至少提供3块磁盘(不包括校验数据所在磁盘)的并行度.对于Ripple-RAID与S-RAID 5,每个Bank中的12个DBand被分为4组,每组3个并行工作(P=4,Q=3);Hibernator需要把3块数据磁盘迁移到运行阵列,与校验盘组成RAID 5;对于MAID,取其前端阵列为4块磁盘(校验数据占1块磁盘的空间)组成的RAID 5.
Ripple-RAID分别以相关流水(1块SSD)、无关流水(2块SSD)方式生成校验数据,采用的SSD型号为PX- 160M3,容量为160GB.选取每种阵列的基本工作状态,也是最佳节能状态来测试性能.Ripple-RAID与S-RAID 5的测试逻辑地址范围指定在1个分组之内;Hibernator的测试对象为其运行阵列;MAID的测试对象为其前端阵列;PARAID的测试对象为其最节能的那一级RAID 5.
首先,利用Iometer测试写性能,测得各节能阵列在80%顺序写、随机写负载下的写性能,分别如图 10(a)、图 10(b)所示,Ripple-RAID具有突出的写性能,相关流水、无关流水时的写性能基本相同,统一记作Ripple-RAID.在80%顺序写负载下,当请求长度为512KB时,与并行盘数相同的节能阵列相比,Ripple-RAID的写性能分别为S-RAID 5的3.9倍,是Hibernator和MAID写性能的1.9倍;与12磁盘并行的PARAID和eRAID 5相比,Ripple- RAID的写性能达到了前两者的49%.
随机负载增加时,Ripple-RAID写性能会更加突出.在随机写负载下,其写性能远高于并行盘数相同的S-RAID 5、Hibernator以及MAID,而与12磁盘并行的PARAID和eRAID 5的写性能相当.Ripple-RAID突出的写性能得益于有效消除了局部并行带来的小写问题以及通过地址映射把非顺序写转换成了顺序写.S-RAID 5的写性能最低,主要是由于其局部并行数据布局带来的小写问题,严重影响了写性能.
Ripple-RAID读性能取决于地址映射后的数据分布情况,顺序读可被映射为随机读(概率大),随机读也可被映射为顺序读(概率小),因此难以给出准确的读性能对比测试.但可以给出Ripple-RAID中地址转换延迟对读性能的影响,我们做了一个地址平移变换,把所有读请求平行映射到另外一个读区间.
在此基础上,利用Iometer测试了读性能,各节能阵列在80%顺序读、随机读时的读性能分别如图 10(c)、图 10(d)所示,Ripple-RAID的读性能略低于并行盘数相同的S-RAID 5、Hibernator和MAID,是由于Ripple-RAID的地址转换引起一定的时间延迟;读性能远低于PARAID和eRAID 5,是由于Ripple-RAID提供了3磁盘的并行度,而后者均提供了12磁盘的并行度.
以上读性能测试结果,仅具有一定的参考价值.在实际的连续数据存储应用中,由于读操作以数据回放为主,如视频回放、利用CDP进行系统还原、读取归档数据等,一般会执行顺序读(重复某段时间内的写操作),此时,Ripple-RAID的读性能将与写性能接近,远高于以上测试结果.
Ripple-RAID采用流水技术渐进生成校验数据(如图 4、图 5所示),其中,新数据写入磁盘,导致Ripple-RAID的性能主要取决于磁盘性能.缓存新校验与写新数据并行.因此,把缓存新校验的SSD改成磁盘,不会显著影响其性能,采用SSD主要为了提高节能效率.
Ripple-RAID把磁盘存储区分成若干组,组内局部并行,组间可独立工作.对于读写混合型负载,容易解耦成独立的读写操作,具体如下:如果读写操作分别位于Ripple-RAID中可并行的组,则调度对应的组运行,此时,Ripple-RAID的总性能基本等于各组读、写性能之和;否则,先执行读操作,同时缓存写数据到相关设备(如低功耗的SSD),并在读操作结束后回迁写数据,此时,Ripple-RAID的性能等于该组的读、写性能.
综上,Ripple-RAID中单个分组的读、写性能能够反映Ripple-RAID的基本性能.为了进一步验证该分组方式能否满足性能需求,我们进行了实际数据读写测试.向Ripple-RAID写入视频数据,然后检验写入数据的正确性,同时进行视频回放.测试结果表明,该Ripple-RAID能够正确写入32路D1标准的视频数据以及正确回放记录的数据.为了避免直接从内存缓冲区读取回放数据,回放的是1小时以前的监控数据.
3.4 节能测试对上述Ripple-RAID、S-RAID 5、Hibernator、PARAID、MAID以及eRAID 5分别进行24小时节能测试,测试结果如图 11所示.Ripple-RAID的节能效果最好,采用无关流水生成校验数据时,24小时平均功耗约为2.4x106J,比S-RAID 5节能20%,比Hibernator和MAID节能33%,比eRAID 5节能70%,比PARAID节能72%;采用相关流水生成校验数据时,可节省1块SSD(160GB),性能与无关流水时基本相同,但功耗有所增加.此时,Ripple-RAID的功耗与S-RAID 5基本相同.
S-RAID 5的节能效果与Ripple-RAID接近,但写性能远低于Ripple-RAID,因此,其性能裕量远小于Ripple- RAID.与Hibernator相比,Ripple-RAID没有把存储空间划分为多个不同转速的子阵列,省略了子阵列间的磁盘迁移、数据重构过程.PARAID的能耗最高,表明该节能阵列不适合数据密集型存储应用,而适用于具有较多空闲存储空间的存储系统.与MAID相比,Ripple-RAID把存储数据直接写入局部并行的存储阵列,省略了前端数据缓冲过程及相关存储设备.eRAID 5主要面向随机数据访问,最多仅能节省1块磁盘的功耗(关闭校验数据所在磁盘).
4 磁盘状态转换的影响本节将从写、读两方面分析磁盘状态转换对性能、节能和存储设备寿命的影响.Ripple-RAID执行顺序写,可以预启动将要访问的待机磁盘来消除状态转换对写性能的影响.下面将分析写操作引起的状态转换对节能、存储设备寿命的影响.实验中的Ripple-RAID采用P=4,Q=3的分组方式,Band大小为140GB,group大小为420GB (140GBxQ).32路D1视频监控系统每小时产生28.8GB的数据,所以group的切换周期为420/28.8=14.6小时;磁盘状态转换周期(运行®待机®运行)为58小时(14.6xP).采用流水方式生成校验数据时,SSD的擦写周期为29小时(group切换周期x2),若SSD可擦写10万次,则其寿命为333年.保持以上配置不变,写带宽增加到200MB/s(原来的25倍),磁盘状态转换周期为2.3小时,SSD寿命为13年.
继续增大写带宽,单个Ripple-RAID将难以满足存储容量需求(S-RAID 5,Hibernator情况相同).以200MB/s为例,24小时的数据量为17TB,以12块2TB的磁盘构建RAID时(RAID中磁盘数一般为10块左右,若过多,则难以保证安全性),去除文件系统的消耗,有效存储空间约为21TB,仅能存储30小时的数据.连续数据存储系统一般需要较长时间保存数据,如我国规定:一般场所的视频监控数据保存15天,重要场所的监控数据保存30天以上.此时,需要采用多个RAID提供存储容量,分为两种情况:(1) 多个RAID并行,写带宽分配到各个RAID,单个RAID的写带宽将有所下降;(2) 多个RAID串行(交替工作),每个RAID中的磁盘状态转换周期依然会足够大.因此,可忽略写操作引起的状态转换对节能、存储设备寿命的影响.
连续数据存储系统以写操作为主,包含少量读操作,可分为如下两类:(1) 读取文件系统元数据、RAID配置信息等,数据量较小,读数据分布具有一定规律;(2) 数据回放时的读操作,数据量一般较大,读数据随机分布.采用文献[2]提出的优化策略,可有效消除第(1)类读操作引起的磁盘状态转换问题.第(2)类读操作的执行频率通常很低,并以顺序读为主(回放写操作),所引起的磁盘状态转换对性能、节能以及磁盘寿命的影响也可以忽略.
5 结论与展望针对视频监控、CDP、VTL、备份、归档等连续数据存储应用,本文提出一种高效能盘阵——Ripple-RAID,继承了S-RAID 5的局部并行思想,设计了新的数据布局,综合运用了地址转换、异地更新、基于流水技术渐进生成校验、分段数据恢复等策略,在单盘容错的前提下,既保持了局部并行的节能性,又有效消除了局部并行带来的小写问题.实验结果表明,Ripple-RAID具有突出的写性能和节能效率.连续数据存储中的读操作以数据回放为主,因此Ripple-RAID一般具有与写性能接近的、突出的读性能.
与S-RAID 5显著不同,Ripple-RAID对写数据的连续性没有要求,其地址映射机制能够把非连续数据映射为连续数据.对于非连续数据存储,如果优化后(如采用分层或混合存储)随机读操作频率很低,较少进行改写操作,则Ripple-RAID也是适用的.对Ripple-RAID可进一步分类与拓展:把上述采用类似RAID 5的分布校验、单盘容错的Ripple-RAID,称为Ripple-RAID 5;把采用类似RAID 4的集中校验、单盘容错的Ripple-RAID,称为Ripple-RAID 4;把采用类似RAID 6的分布校验、双盘容错(P+Q校验)的Ripple-RAID,称为Ripple-RAID 6.
[1] | Li X, Tan YA, Sun ZZ. Semi-RAID: A reliable energy-aware RAID data layout for sequential data access. In: Proc. of the 27th IEEE Symp. on Massive Storage Systems and Technologies (MSST). Washington: IEEE Computer Society, 2011. 1-11 . |
[2] | Li YZ, Sun ZZ, Ma ZM, Zheng J, Tan YA. S-RAID 5: An energy-saving RAID for sequential access based applications. Chinese Journal of Computers, 2013,36(6):1290-1301 (in Chinese with English abstract). |
[3] | Stodolsky D, Gibson G, Holland M. Parity logging: Overcoming the small write problem in redundant disk arrays. In: Proc. of the 20th Annual Int’l Symp. on Computer Architecture (ISCA). New York: ACM Press, 1993. 64-75 . |
[4] | Menon J, Roche J, Kasson J. Floating parity and data disk arrays. Journal of Parallel and Distributed Computing, 1993,17(1): 129-139 . |
[5] | Jin C, Feng D, Jiang H, Tian L. RAID6L: A log-assisted RAID6 storage architecture with improved write performance. In: Proc. of the 27th Symp. on Mass Storage Systems and Technologies (MSST). Washington: IEEE Computer Society, 2011. 1-6 . |
[6] | Li MQ, Shu JW. DACO: A high-performance disk architecture designed specially for large-scale erasure-coded storage systems. IEEE Trans. on Computers, 2010,59(10):1350-1362 . |
[7] | Shen YL, Xu L. Efficient disk I/O characteristics analysis method based on virtual machine technology. Ruan Jian Xue Bao/Journal of Software, 2010,21(4):849-862 (in Chinese with English abstract). http://www.jos.org.cn/1000-9825/3492.htm |
[8] | Zikopoulos P, Eaton C. Understanding Big Data: Analytics for Enterprise Class Hadoop and Streaming Data. New York: McGraw-Hill, 2011. 15-58. |
[9] | Zhu QB, Chen ZF, Tan L, Zhou YY, Kimberly K, John W. Hibernator: Helping disk arrays sleep through the winter. Operating Systems Review (ACM), 2005,39(5):177-190 . |
[10] | EMC Corporation. Symmetrix 3 000 and 5 000 enterprise storage systems product description guide. 2012. http://www.emc.com/collateral/software/symmetrix3000-and-5000.pdf |
[11] | Gurumurthi S, Sivasubramaniam A, Kandemir M, Franke H. DRPM: Dynamic speed control for power management in server class disks. In: Proc. of the 30th Int’l Symp. on Computer Architecture. New York: ACM Press, 2003. 169-179 . |
[12] | Carrera E, Pinheiro E, Bianchini R. Conserving disk energy in network servers. In: Proc. of the 17th Int’l Conf. on Supercomputing (ICS). New York: ACM Press, 2003. 86-97 . |
[13] | Weddle C, Oldham M, Qian J, Wang AA, Reiher P, Kuenning G. PARAID: A gear-shifting power-aware RAID. In: Proc. of the 5th USENIX Conf. on File and Storage Technologies (FAST). Berkeley: USENIX Association, 2007. 245-260. |
[14] | Pinheiro E, Bianchini R. Energy conservation techniques for disk array-based servers. In: Proc. of the 18th Int’l Conf. on Supercomputing (ICS). New York: ACM Press, 2004. 68-78 . |
[15] | Colarelli D, Grunwald D. Massive arrays of idle disks for storage archives. In: Proc. of the ACM/IEEE Conf. on Supercomputing. Los Alamitos: IEEE Computer Society, 2002. 1-11 . |
[16] | Narayanan D, Donnelly A, Rowstron A. Write off-loading: Practical power management for enterprise storage. In: Proc. of the 6th USENIX Conf. on File and Storage Technologies (FAST). Berkeley: USENIX Association, 2008. 253-267 . |
[17] | Storer M, Greenan K, Miller E, Voruganti K. Pergamum: Replacing tape with energy efficient, reliable, disk-based archival storage. In: Proc. of the 6th USENIX Conf. on File and Storage Technologies (FAST). Berkeley: USENIX Association, 2008. 1-16. |
[18] | Li D, Wang J. EERAID: Energy-Efficient redundant and inexpensive disk array. In: Proc. of the 11th ACM SIGOPS European Workshop. New York: ACM Press, 2004. 1-14 . |
[19] | Wang J, Zhu H, Li D. eRAID: Conserving energy in conventional disk-based RAID system. IEEE Trans. on Computers, 2008,57(4): 359-374 . |
[20] | Mao B. Research on data layout technologies for disk arrays [Ph.D. Thesis]. Wuhan: Huazhong University of Science & Technology, 2010 (in Chinese with English abstract). |
[21] | Narayanan D, Thereska E, Donnelly A, Elnikety S, Rowstron A. Migrating server storage to SSDs: Analysis of tradeoffs. In: Proc. of the 4th ACM European Conf. on Computer Systems. New York: ACM Press, 2009. 145-158 . |
[22] | Deng YH. What is the future of disk drives, death or rebirth. ACM Computing Surveys, 2011,43(3):23-49 . |
[23] | Chen F, Koufaty DA, Zhang X. Hystor: Making the best use of solid state drives in high performance storage systems. In: Proc. of the Int’l Conf. on Supercomputing (ICS). New York: ACM Press, 2011. 22-32 . |
[24] | Guerra J, Pucha H, Glider J, Wendy B, Raju R. Cost effective storage using extent based dynamic tiering. In: Proc. of the 9th USENIX Conf. on File and Storage Technologies (FAST). Berkeley: USENIX Association, 2011. 273-286. |
[25] | Guerra J, Belluomini W, Glider J, Gupta K, Pucha H. Energy proportionality for storage: Impact and feasibility. ACM SIGOPS Operating Systems Review, 2010,44(1):35-39 . |
[26] | The Storage Networking Industry Association. The 2012 SNIA dictionary. 2012. http://www.snia.org/education/dictionary |
[27] | Rosenblum M, Ousterhout JK. The design and implementation of a log-structured file system. ACM Trans. on Computer Systems, 1992,10(1):26-52 . |
[28] | Hartman JH, Ousterhout JK. The zebra striped network file system. ACM Trans. on Compute Systems, 1995,13(3):274-310 . |
[29] | Nippon Technology and Telephone Corporation. NILFS2. 2012. http://www.nilfs.org/en/download.html |
[30] | Wilkes J, Golding R, Staelin C, Sullivan S. The HP AutoRAID hierarchical storage system. ACM Trans. on Computer Systems, 1996,14(1):108-136 . |
[2] | 李元章,孙志卓,马忠梅,郑军,谭毓安.S-RAID 5:一种适用于顺序数据访问的节能磁盘阵列.计算机学报,2013,36(6):1290-1301. |
[7] | 沈玉良,许鲁.一种基于虚拟机的高效磁盘I/O特征分析方法.软件学报,2010,21(4):849-862. http://www.jos.org.cn/1000-9825/3492.htm |
[20] | 毛波.盘阵列的数据布局技术研究[博士学位论文].武汉:华中科技大学,2010. |