存储系统重构优化技术研究

谢平

摘 要：目前海量存储系统规模逐渐增长，存储节点失效是普遍现象。因此存储系统的重构优化问题越来越受到研究人员的关注。综述了存储系统从数据布局和数据调度两个层面的重构技术研究进展和现状，同时对各种典型重构技术从原理、实现机制等方面进行了分析和归纳，并对比分析和总结了各种重构技术的适应场景。结合海量存储系统负载特征的复杂性和应用环境的复杂性等特点，指出了存储系统重构技术的未来研究方向。

关键词：纠删编码存储系统；重构技术；存储可靠性；数据可用性

中图分类号：TP311 文献标识码：A 文章编号：2095-1302（2017）05-0-04

0 引 言

当今社会正处于数据爆炸式增长的时代，网络技术提供商Cisco预测，从2013到2018年全球每个月的网络数据量将以21%的年增长速度上升，每月的网络数据量将从2013年的51 EB增长到2018年的132 EB，数据量几乎增长了3倍，并且到2016年，每个月的网络数据量已达91 EB[1]。企业数据中心面临海量数据存储的需求，因此数据中心需要廉价、可靠、高性能和高能效的数据存储系统。

现代存储系统采用一定的容错策略，通过重构技术确保存储的可靠性和数据可用性。一方面当一定存储节点失效时，通过重构技术可以恢复失效节点以确保存储可靠，另一方面考虑网络I/O负载的复杂性特征，为及时响应用户的数据访问请求，通过重构技术以确保数据的高效可用。重构技术是根据存储系统容错数据布局方案，采用一定I/O优化调度策略，以减少I/O开销与降低CPU计算开销为手段，实现可靠并快速获取用户数据为目的的优化过程。

1 纠删编码存储系统重构优化技术

图1所示为典型纠删编码存储系统的重构优化过程。在纠删编码存储系统中，将k个保存原始数据的磁盘经过编码计算操作，得到m个冗余磁盘；当存储系统中有不超过m个磁盘失效时，根据纠删编码的编码/解码计算规则，通过存活的数据磁盘和冗余磁盘恢复出失效磁盘，其存储效率为k/（k+m）。在纠删编码的设计中，重构性能是其最重要的设计目标之一，在真实存储环境下，重构性能通常由恢复失效磁盘所用的重构时间来衡量，重构时间越短则重构性能越好，反之亦然。在理论分析中，由于重构过程中的计算开销比I/O开销快多个数量级，因而在理论比较中其计算开销可以忽略不计，因此校验阵列编码的重构性能可以转化成以存取数据块的个数来衡量重构性能。目前校验阵列编码的重构优化技术在学术界和工业界引起了广泛关注，主要分为以下几种研究趋势。

1.1 最优重构链长策略

针对MDS编码随着存储系统规模的扩大，其重构性能逐渐降低的问题，研究者提出了许多新的Non-MDS编码以提升存储系统的重构性能，如WEAVER编码[2]，Hover编码[3]，Pyramid编码[4]，Stepped Combination编码[5]，Code-M编码[6]和V2-Code编码[7]。Non-MDS编码相对于MDS编码在校验链的构建机制上使用了更多的校验块，减少了生成一个校验块所需的数据块个数，因此在相同存储规模的系统中，Non-MDS编码缩短了校验链的长度。在重构过程中，Non-MDS编码获得了更短的重构链长，在重构一个失效块的情况下需要读取更少的数据块，提升重构性能；此外，Non-MDS编码的重构链的长度不随存储系统规模的增长而变化，即重构性能与RAID规模大小无关，然而对于MDS编码其重构链的长度随着存储系统规模的增长而变长，因此其重构性能会逐渐降低。故设计新型高容错能力的Non-MDS编码成为提高重构性能的一种研究趋势。

1.2 最优重构数据量策略

对于现有的容多错阵列编码中，单磁盘失效恢复是最常见的问题[8]，最初的重构策略便采用传统的恢复方式[9，10]，即所有失效块的重构只考虑读取一种校验链的方式，该方式需要读取所有数据块用于重构，因而增加了存取I/O的复杂度；然而容多错的编码通常包含多种校验链（如行校验链、斜校验链和反斜校验链），每一种校验链之间都存在共用块的情况，因此最大化共用块的个数将会减少读取重构所需的数据量，从而达到提升重构性能的目的，这种重构方式称为混合校验链重建方式。如RDOR算法针对RDP编码的单磁盘失效提出了寻找最少重建数据块的快速重建方案[11]；王等人基于最少重构数据量的思路实现了EVENODD编码单盘快速重构[12]；针对任意多容错纠删编码的单盘恢复问题，Khan等人提出了一种枚举恢复算法，即寻找最小重建数据量[13]；朱等人提出了一种替换恢复算法，加速了最少重构数据量的寻找过程，寻找到了次优的最少重构数据量[14]。

1.3 最优重构带宽策略

在分布式存储系统中，其重构过程中减少网络I/O开销是主要的优化目标，即最优重构带宽策略，以提供良好的网络存储性能。再生编码[15]基于最优重构带宽被提出，例如Exact Regenerating Codes提出精确恢复失效数据[16]；李等人基于再生码充分考虑了异构网络结构以及并行恢复算法遂提出了快速重建方案[17]；MCR和MBCR基于再生碼策略并发重建了多失效节点[18，19]；CHR在异构网络集群环境下，考虑节点的异构权重因子加速了RAID-6编码的存储系统单盘失效重构过程[20]。PM-RBT基于MSR再生编码，考虑在重构过程中确保最优网络通信开销、最优存储效率和可靠性的同时，实现了最小化磁盘I/O开销，从而加速了重构的实现[21]。

1.4 均衡重构负载的策略

在磁盘阵列的环境中，由于并行性存储I/O结构，影响存储系统重构性能的决定因素是瓶颈磁盘的性能，故罗等人提出了均衡重构I/O的恢复思路，即在重构过程中，从各存活磁盘读取用于重构的数据量要均衡，因此在RAID编码的阵列里，选择重构所需的数据块在各存活磁盘要均衡布局，最终实现最小化从单盘读取重构数据块的思路[22]。S2-RAID提出了一种新的RAID结构，该结构充分考虑了并行数据布局思路，在重构过程中确保重构所需的数据块能并行和均衡地从各存活磁盘读取，提升重构性能[23]。另外基于平衡I/O响应时间和磁盘重建时间的考虑，候等人提出了负载均衡的重建优化方案[24]。

1.5 重构I/O优化策略

在重构过程中充分优化重构I/O流，并减少用户I/O流对重构性能的影响，可以有效加速重构实现过程，因而各种重构I/O优化策略被提出以提升重构性能，例如SOR和DOR充分考虑了重构I/O的并行性加速了重构的实现[25，26]；Pro基于用户I/O存在存取局部性的特性，提出了基于用户I/O热度的重构算法，即在重构过程中优先考虑重构用户I/O访问最热的区域，以确保对用户I/O的及时响应，加速重构过程[27]；Workout采用写重定向策略，即分离用戶I/O流和重构I/O流，从而有效避免两者相互干扰，实现了加速重构过程的目的[28]，此外VDF和MCRO充分利用了高效的Cache策略，有效减少了重构I/O的数量，即减少对磁盘的存取次数，提升了重构性能[29，30]。

2 重构优化技术的分析与讨论

上面分别从重构数据布局和重构数据调度两个层面对纠删编码存储系统的重构技术进行了说明，表1对上述典型重构技术进行了对比和总结。

从表1典型重构技术的对比中可以发现：

（1）重构编码布局逐渐由最早的MDS纠删编码向重构性能更好的Non-MDS纠删编码发展，以及提供更好容错能力和重构性能的“Embed-RAID”编码转变[26]，例如RAID0+1和RAID1+0数据布局；

（2）重构调度策略逐渐由面向纠删编码的多线程、并行性SOR和DOR的重构技术向优化重构I/O流和用户I/O流存取特征的Pro和WorkOut重构策略转变，及减少重构I/O量的高效Cache策略MCRO和VDF发展；

（3）基于现有纠删编码，优化其编码/解码复杂度以减少重构数据量的RDOR、LDF和CoRec重构策略逐渐受到关注；

（4）现有纠删编码由面向并行阵列环境向分布式存储环境的应用方向发展，结合存储异质异构和网络I/O复杂性特征，研究再生编码重构策略。

3 结 语

本文从纠删编码存储系统数据布局和数据调度两个层面展开，围绕复杂的存储环境和应用环境面临的重构技术关键问题，考虑存储系统的异质异构以及复杂的用户I/O存取特征，结合并行性/分布式存储系统场景，分析、总结了现有重构优化技术。随着网络存储技术的深入发展，纠删编码的存储系统重构技术未来主要呈现以下发展趋势：

（1）面向云存储的重构策略。随着云存储技术的发展，结合空间位置特性和存储节点异质异构的特征，研究高容错能力和高效新型Non-MDS编码与应用于云存储系统的重构技术有待深入发展；

（2）多级纠删编码的重构策略。现有纠删编码为用户数据提供了单层可靠保障，并未考虑用户I/O需求级别，如何将用户数据存取优先级别与容错能力结合，提供多级纠删编码融合数据重构策略，将可有效提供更好的用户数据存取服务和容错能力；

（3）面向负载特征的重构策略。借鉴统计学与数据挖掘领域的技术，进一步分析和挖掘数据集的特性，考虑新型存储器件性能以及数据的合理布局与调度，提供良好用户服务的数据重构策略；

（4）多失效节点的重构策略。目前的重构策略主要基于单失效节点，然而随着存储规模的扩大，同时重构多失效节点的策略有待开发，其中优化多失效节点的重构I/O流将是主要的目标。

目前数据的组织模式已由以计算为中心向存储为中心的层面转变，基于存储的研究越来越受到科研人员的关注。总的来讲，计算机的存储研究呈现出大容量、网络化、高容错性和高效性趋势。因此可以预见，未来对于分布式高性能计算和存储系统的重构研究将成为主要方向。

参考文献

[1] Cisco全球网络数据流量预测分析：The Zettabyte Era—Trends and Analysis[EB/OLE]. http：//www.cisco.com/c/en/us/solutions/collateral/service-provider/visual-networking-index-vni/VNI_Hyperconnectivity_WP.html

[2] Hafner， J. L. Weaver codes： Highly fault tolerant erasure codes for storage systems[C].In Proceedings of the 4th USENIX Conference on File and Storage Technologies.Berkeley，CA，USA， USENIX，2005： 16-26.

[3] Hafner J L. HoVer erasure codes for disk arrays[C].2006 International Conference on Dependable Systems and Networks. IEEE， 2006： 217-226.

[4] Huang C， Chen M， Li J. Pyramid codes： Flexible schemes to trade space for access efficiency in reliable data storage systems[J]. 2007 Sixth IEEE International Symposium on Network Computing and Applications. IEEE， 2007，9（1）： 79-86.

[5] Greenan K M， Li X， Wylie J J. Flat XOR-based erasure codes in storage systems： Constructions， efficient recovery， and tradeoffs[J]. Mass Storage Systems and Technologies，2010，2（1）： 1-14.

[6] Wan S， Cao Q， Xie C， et al.Code-m： A non-mds erasure code scheme to support fast recovery from up to two-disk failures in storage systems[J].2010 IEEE/IFIP International Conference on Dependable Systems and Networks. IEEE， 2010，23（5）： 51-60.

[7] Xie Ping， Huang Jianzhong， Cao Qiang， et al. V2-Code： A new non-MDS array code with optimal reconstruction performance for RAID-6[C].2013 IEEE International Conference on Cluster Computing （CLUSTER13）. IEEE， 2013： 1-8.

[8] Pinheiro E， Weber W D， Barroso L A. Failure Trends in a Large Disk Drive Population[C]. In Proceedings of the 2007 USENIX Conference on File and Storage Technologies. USENIX， 2007： 17-23.

[9] Blaum M， Brady J， Bruck J， et al. EVENODD： An efficient scheme for tolerating double disk failures in RAID architectures[J]. Acm Sigarch Computer Architecture News， 1995， 22（2）： 245-254.

[10] Corbett P F， English R， Goel A， et al. Row-diagonal parity for double disk failure correction[C].In Proceedings of the 3rd USENIX Conference on File and Storage Technologies. USENIX， 2004： 1-14.

[11] Xiang L， Xu Y， Lui J， et al. A hybrid approach to failed disk recovery using RAID-6 codes： Algorithms and performance evaluation[J]. ACM Transactions on Storage， 2011， 7（3）： 11

[12] Wang Z， Dimakis A G， Bruck J. Rebuilding for array codes in distributed storage systems[C]. 2010 IEEE GLOBECOM Workshops， 2010： 1905-1909.

[13] Khan O， Burns R， Plank J， et al. In search of I/O-optimal recovery from disk failures[C].In Proceedings of the 3rd USENIX conference on Hot topics in storage and file systems. USENIX Association， 2011： 6.

[14] Zhu Y， Lee P P C， Hu Y， et al.On the speedup of single-disk failure recovery in xor-coded storage systems：Theory and practice[J].Mass Storage Systems and Technologies，2012，22（5）：1-12.

[15] Dimakis A G， Godfrey P B， Wu Y， et al.Network coding for distributed storage systems[J]. IEEE Transactions on Information Theory， 2010， 56（9）： 4539-4551.

[16] Rashmi K V， Shah N B， Kumar P V， et al.Explicit construction of optimal exact regenerating codes for distributed storage[C].Allerton 2009：47th Annual Allerton Conference on Communication， Control， and Computing. IEEE， 2009： 1243-1249.

[17] Li J， Wang X， Li B. Pipelined regeneration with regenerating codes for distributed storage systems[C]. 2011 International Symposium on Network Coding. IEEE， 2011： 1-6

[18] Hu Y， Xu Y， Wang X， et al. Cooperative recovery of distributed storage systems from multiple losses with network coding[J]. IEEE Journal on Selected Areas in Communications， 2010， 28（2）： 268-276.

[19] Kermarrec A M， Le Scouarnec N， Straub G. Repairing multiple failures with coordinated and adaptive regenerating codes[C].2011 International Symposium on Network Coding. IEEE， 2011： 1-6.

[20] Zhu Y， Lee P P C， Xiang L， et al. A cost-based heterogeneous recovery scheme for distributed storage systems with RAID-6 codes[C].2012 42nd Annual IEEE/IFIP International Conference on Dependable Systems and Networks， 2012： 1-12.

[21] K. V. Rashmi， Preetum Nakkiran， Jingyan Wang，et al. Having Your Cake and Eating It Too： Jointly Optimal Erasure Codes for I/O， Storage and Network-bandwidth[C]. In Proceedings of the 2015 USENIX Conference on File and Storage Technologies. USENIX， 2015：81-94.

[22] Luo X， Shu J.Load-Balanced Recovery Schemes for Single-Disk Failure in Storage Systems with Any Erasure Code[C]. 2013 42nd International Conference on Parallel Processing， 2013： 552-561.

[23] Wan J， Wang J， Yang Q， et al.S2-RAID：A new RAID architecture for fast data recovery[C]. 2010 IEEE 26th Symposium on Mass Storage Systems and Technologies， 2010： 1-9.

[24] Hou R Y， Menon J， Patt Y N. Balancing I/O response time and disk rebuild time in a RAID5 disk array[C].In Proceeding of the Twenty-Sixth Hawaii International Conference on System Sciences. IEEE， 1993： 70-79.

[25] Holland M， Gibson G A， Siewiorek D P. Architectures and algorithms for on-line failure recovery in redundant disk arrays[J].Distributed and Parallel Databases， 1994， 2（3）： 295-335.

[26] Holland M， Gibson G A， Siewiorek D P. Fast， on-line failure recovery in redundant disk arrays[C].The Twenty-Third International Symposium on Fault-Tolerant Computing， 1993： 422-431.

[27] Tian L， Feng D， Jiang H， et al. PRO： A Popularity-based Multi-threaded Reconstruction Optimization for RAID-Structured Storage Systems[C].In Proceedings of the 2007 USENIX Conference on File and Storage Technologies. USENIX， 2007：277-290.

[28] Wu S， Jiang H， Feng D， et al. WorkOut： I/O Workload Outsourcing for Boosting RAID Reconstruction Performance[C]. In Proceedings of the 2009 USENIX Conference on File and Storage Technologies. USENIX 2009： 239-252.

[29] Shenggang Wan， Xubin He， Jianzhong Huang，et al.An Efficient Penalty-Aware Cache to Improve the Performance of Parity-Based Disk Arrays under Faulty Conditions[J].IEEE Transactions on Parallel Distributed Systems，2013，24（8）： 1500-1513.

[30] Xu L， Bruck J. X-code： MDS array codes with optimal encoding[J].IEEE Transactions on Information Theory， 1999， 45（1）： 272-276.

[31] Xie T， Wang H. MICRO： A multilevel caching-based reconstruction optimization for mobile storage systems[J].IEEE Transactions on Computers， 2008， 57（10）： 1386-1398.

[32] Guide P. Multiple （Nested） RAID Levels[EB/OL]. http：//www.pcguide.com/ref/hdd/perf/raid/levels/mult.htm

[33] Jin C， Jiang H， Feng D， et al. P-Code： A new RAID-6 code with optimal properties[C].In Proceedings of the 23rd international conference on Supercomputing. ACM， 2009： 360-369.

[34] Li M， Shu J， Zheng W. GRID codes： Strip-based erasure codes with high fault tolerance for storage systems[J]. ACM Transactions on Storage， 2009， 4（4）： 1-22.

[35] Shiyi Li， Xubin He， Shenggang Wan， et al. Exploiting Decoding Computational Locality to Improve the I/O Performance of an XOR-Coded Storage Cluster under Concurrent Failures[J]. SRDS 2014（1）： 125-135.

[36] Shiyi Li，Qiang Cao，Shenggang Wan，et al.PPM： A Partitioned and Parallel Matrix Algorithm to Accelerate Encoding/Decoding Process of Asymmetric Parity Erasure Codes[C]. International Conference on Parallel Processing，2015：460-469.

[37] Jianzhong Huang， Er-wei Dai， Changsheng Xie， et al.CoRec： A Cooperative Reconstruction Pattern for Multiple Failures in Erasure-Coded Storage Clusters[C].International Conference on Parallel Processing，2015： 470-479.