分布式块存储系统中高效纠删码重构技术研究

陈付 张淑萍

摘要：当前的海量存储压力导致三副本存储效率越来越难以满足需求。纠删码可以提供和三副本存储相同的可靠性，使用更少的存储容量和网络带宽。提出一种针对分布式块存储访问特点的纠删码故障处理方案——一种纠删码和热备副本相结合的方法，解决临时故障导致的退化读和退化更新问题，同时精细地控制永久故障延迟重构的时间点，减轻重构操作造成的对网络带宽的压力。实验结果表明，相对于传统纠删码，该方案可节省3倍带宽流量，存储成本只有三副本的50%。

关键词关键词：云存储；分布式块存储；纠删码；重构效率

DOIDOI：10.11907/rjdk.161381

中图分类号：TP301文献标识码：A文章编号文章编号：16727800（2016）007003303

0引言

云存储可提供不同接口类型的存储服务，如文件存储、对象存储和块存储。其中，块存储接口可以为云计算中的云主机提供云硬盘服务。在大规模数据存储系统中，设备故障越来越频繁，使人们对于确保数据可靠性的需求十分迫切。通常采用数据冗余容错技术来保护数据，但随着海量数据的存储压力与日俱增，分布式存储系统中保障数据可靠性的三副本技术的存储成本也越来越高[1]。现有分布式存储系统如微软WAS[2]、Facebook的F4[3]、HDFS等开始支持纠删码取代三副本技术，从而能够在保持高可靠性的同时，减轻海量数据存储压力。纠删码的缺陷在于重构效率低下，因此分布式块存储由于其高I/O密集和低访问延迟特性，必须要克服纠删码重构成本高的弊端。

1相关技术

1.1分布式块存储系统

块存储提供块存储设备接口，用户需要把块存储卷附加到虚拟机上之后才可以与其交互。面对极具弹性的存储需求和性能需求，单机或独立的SAN越来越难以满足企业需求。块存储在Scale-up的瓶颈下面临着Scale-out的需求，因此Scale-out的分布式块存储系统应运而生。企业级分布式块存储系统有Amazon EBS，开源系统有Ceph RBD[4]和Sheepdog[5]。

1.2纠删码容错技术

考虑一个有M个服务器节点的纠删码编码存储集群，将数据分割成数据段，然后在每个段上独立地使用纠删码进行编码。将一个纠删码方案表示为EC（n，k），EC（n，k）将一个数据段分割成了k个相同大小的未编码块，称为数据块，然后编码生成n-k个编码块，称为校验块。假设n

2方案设计

2.1临时故障与永久故障

存储系统面临着两种类型的节点故障：临时故障和永久故障。临时故障包括机器重启、软件升级等，永久故障包括机器崩溃、磁盘损坏等[9]。如果一个存储节点丢失数据，则发生了永久故障。为了维持系统的冗余级别，存储系统需要执行故障节点重构，即将丢失的数据修复并写入另一个新的存储节点。目前，很多研究是关于加快永久节点故障重构。另一方面，如果一个节点存储的数据并没有丢失，仅是暂时无法直接访问，则发生了临时故障。无永久数据丢失的临时故障占数据中心所有故障事件的90%[10]。

区分临时故障和永久故障，只对永久故障采用重构操作，这样既可以极大地减少存储系统中的重构次数，又避免了退化更新操作的高延迟。思路是当节点出现不可用的情况时，初步界定为临时故障，采用热备副本方法进行退化读和退化更新操作，尽量延迟对永久故障的判定时间；当确认出现永久故障时，进一步延迟重构操作，直到一个数据条带的几个块同时出现永久故障，或者临时故障较多，可能影响到数据的可用性和可靠性时，才开始进行重构操作。

2.2临时故障解决方案

为访问暂时不可用的数据，存储系统需要执行退化读操作，即从剩余存储节点读取数据并重建不可用的数据。同时，为了对无法直接访问的数据块进行更新，存储系统需要进行退化写操作。在更新操作对延迟不敏感的存储系统中，将更新操作进行阻塞直到能判断存储节点是永久故障还是临时故障（等待15分钟）。如果是永久故障则进行重构操作，并将更新数据写入到恢复后的节点；如果是临时故障，在节点可以重新访问之后直接将更新数据写入数据块节点[11]。但对于更新延迟比较敏感的分布式块存储系统，以前不重视的退化更新变得更为重要。

（1）退化读。当需要对不可用的数据块进行读操作时，从剩余的n-1个数据块和校验块中选取k个可用的块进行解码恢复操作，然后将恢复的数据块返回客户端。这些操作与标准的退化读操作一致，但不同的是将恢复的数据块保存到对应数据块节点的热备节点中作为副本存储。在该条带出现临时故障的节点一直不可用期间，将使用该副本替代原有节点的数据块来完成各项更新和读取操作。当原临时故障节点恢复正常可用时，如果数据块已有更新，则将副本上更新的数据块复制到原节点。接下来如果原节点的可用数据块发生更新，则将副本设为无效。

（2）退化更新。退化更新操作分为对数据块节点和校验块节点两种情况：①针对数据块节点：先进行退化读操作，恢复原有数据块，得到新数据块并写入到热备节点中形成副本，然后计算出新旧数据的更新差量，进行常规的更新操作来更新所有校验块；②针对校验块节点：首先获取校验块状态，如果处于可用状态，则进行常规更新操作，如果处于不可用状态，则利用更新后的数据块，计算相应的新校验块，并将新校验块写入对应的热备节点中形成副本。

2.3永久故障解决方案

当确定一个设备出现永久故障时，一般会立即触发重构操作。但由于纠删码有很强的可靠性，能够容忍多节点同时故障，因而可采用一种延迟重构的方法。延迟重构方式的基本思想是降低重构频次，减少重构消耗的网络带宽，同时不对可用性产生较大影响。可以采用的延迟方案有：

（1）对所有故障块进行延迟重构。在网络存储环境中提出的一种解决方案是延迟故障块的重构，直到一个条带的可用块数目达到给定的恢复阈值r。例如，对于CRS（15，10），r=13，系统将等待出现一个条带中有两个块出现故障时才触发条带的重构。使用CRS（15，10）编码延迟重构的数据，永久丢失的概率大约等同于原始的CRS（14，10）进行即时恢复的数据丢失概率，因为恢复操作都是在仅有13个块可用时进行。

延迟重构有两个主要优点：①恢复两个块的网络成本和恢复一个块成本相近，即恢复一个块需要读10个块写入1个块（总共11x带宽），而恢复两个块需要读10个块写入2个块（总共12x带宽，或者平均每次恢复6x）；②如果一个块由于临时故障而不可用，如网络消耗，延迟恢复可以使其有更多时间恢复到正常可用状态，从而避免了多余的修复。

系统模拟表明将重构阈值减少1可能会极大地增大退化条带的数目。例如，对于CRS（15，10），重构阈值r=12，导致30%的存储条带处于退化状态。另一方面，增加修复的阈值到r=13，能够帮助减少退化条带的数目，但会失去原来节省的网络带宽。

（2）结合临时故障的精细延迟重构。下面进一步提出了与临时故障处理相结合的更精细化的延迟重构方案。将存储系统中一个编码条带的故障程度表示为R，节点上出现临时故障的编码条带比例为p%，有：R=∑ni=1r×（1-×p%）（1）这里的表示每个编码条带中已经进行退化读或更新操作产生热备副本的比例。公式（1）将编码条带组的临时故障和永久故障情况进行统一考虑，更加全面地对数据块丢失概率和网络恢复流量两者之间进行权衡。其中：γ=1节点处于永久故障状态

p%节点处于临时故障状态（2）将阈值表示为limit，这里的limit可以动态地自适应调整，当R≥limit时则开始重构操作：limitz + a = lim itZ + δ

lim itZ -（3）当进行了一次正常的重构恢复操作时，即将limit值渐进地增加δ（一个小增量）；当出现由于延迟重构而造成数据丢失的事件时，则惩罚性突变减少（一个大增量）。这里的初始阈值limit0是一个经验初值，对于CRS（15，10）可配置为2或3。

3方案评估

3.1评估方案

评估一种重构方案在减少修复带宽、对系统可用性和可靠性影响等方面的作用是非常困难的，这里使用一个在GitHub开源的分布式存储系统模拟器DS-SIM来估计修复带宽和系统可用性如何受故障事件、编码方式和重构方案等因素影响。

DS-SIM的输入包括硬件配置规格说明、存储系统组件故障和重构分布的统计性质、编码方案，模拟器返回稳态和网络带宽利用的即刻值、退化条带数目等。模拟参数如表1所示。

表1模拟系统参数参数数值总数据量4PB磁盘容量2T每个主机的磁盘数20每个机架的主机数20修复带宽容量650TB/每天运行周期10年迭代次数25，0003.2评估结果

对3种方案进行了比较，包括：三副本、CRS（15，10）和采用高效重构的NRS（15，10）。

。

4结语

针对分布式块存储系统的访问特点，本文设计了一种高效的纠删码重构技术。对临时故障和永久故障分别设计了相应的解决方案，即对临时故障采用一种纠删码和热备副本相结合的故障处理方法，解决了临时故障导致的退化读/更新问题，并从时间维度分散了永久故障的重构成本，提升了重构效率。同时精细地控制永久故障延迟重构的时间点，在不影响读写性能和数据可靠性的前提下，减少故障节点重构次数，从而极大地减轻了重构操作对网络带宽和磁盘造成的压力。使用DS-SIM模拟器的评估结果表明，该重构方案相对于原有的CRS方案减少了3倍的修复带宽流量，同时对系统的可用性和可靠性影响很小；相对于三副本方案，该方案提高了系统的存储效率与可靠性。

参考文献：

[1]RASHMI K， NAKKIRAN P.Having your cake and eating It too：jointly optimal erasure codes for I/O，storage， and networkbandwidth[C]. USENIX Association，2015：8194.

[2]MURALIDHAR S， LLOYD W.f4：facebook's warm BLOB storage system[C].OSDI. USENIX Association，2014：383398.

[3]HUANG C， SIMITCI H，XU Y.Erasure coding in windows azure storage[C].ATC. USENIX Association，2012：2.

[4]WEIL S A， BRANDT S A.Ceph：a scalable，highperformance distributed file system[C].OSDI，2010：307320.

[5]刘磊.分布式块存储系统节能技术研究[D].武汉：华中科技大学，2013.

[6]罗象宏，舒继武.存储系统中的纠删码研究综述[J].计算机研究与发展，2012， 49（1）：234240.

[7]LI X，ZHENG Q，QIAN H.Toward optimizing cauchy matrix for cauchy reedsolomon code[J].IEEE Communications Letters，2009：603605.

[8]PLANK J S， LUO J.A performance evaluation and examination of opensource erasure coding libraries for storage[C].CFST.2009：253265.

[9]RASHMI K V，SHAH N B.A hitchhiker's guide to fast and efficient data reconstruction in erasurecoded data centers[J].Acm SCCR，2014：331342.

[10]郑清吉.安全存储系统中纠删码技术研究[D].上海：上海交通大学，2009.

[11]朱云锋.分布式存储系统中基于纠删码的容错技术研究[D].长沙：国防科学技术大学，2014.