一种面向数据可用性和存储可靠性动态要求的自适应纠删码存储策略设计

李子天，邢 凯，2，龚海华

1(中国科学技术大学 计算机科学与技术学院，合肥 230027)

2(中国科学技术大学 苏州研究院，江苏 苏州 215123)

1 绪 论

随着计算机和互联网的飞速发展，Internet生成和处理的数据量迅速攀升.有研究[1]显示，过去两年中生成的数据已经占世界数据总量的90%.当前，典型数据中心的存储容量均为PB量级或以上，传统的存储集群越来越难以满足不断增长的存储需求.因此，如何实现一个快速且可靠的分布式存储系统，成为了目前存储系统研究的热点问题之一.

目前数据中心中经常使用的分布式文件系统有HDFS[2]和Ceph[3]等.对于这些分布式系统来说，由于存在着大量的节点，也就意味着节点故障是难以避免的，那么系统的容错性设计便成为了分布式存储系统研究的重要问题之一.目前成熟的分布式存储系统主要应用的是多副本技术，然而这种技术引入了大量的数据冗余，因而大大提高了存储的成本.

在此背景下，有学者提出将纠删码技术应用于分布式存储系统，从而在保证系统容错性的同时，大幅度降低数据的冗余度.纠删码是一种编码技术，它将原始数据分为n个数据块，并额外增加m个编码块.通过这n+m个数据块中的任意n个数据块，均可计算得到原始数据.即如果有任意小于等于m的数据块失效，仍然能通过计算还原原始数据.

然而在实际的数据中心中，分布式存储系统的节点需要动态地进行增加或移除，并且每个节点的存储介质常常是不同批次、不同型号的磁盘，因此在分布式存储系统中，每一个节点的速度和可靠性均不相同，传统上固定n个数据块和m个编码块的纠删码编码方案很难在这样的系统中达到比较好的性能.因此，在分布式存储系统的纠删码实现中考虑对象的可用性和存储设备的可靠性信息，可以更加有效地利用有限的存储设备，从而提升系统的性能，减少空间浪费.

2 相关工作

2.1 分布式存储系统中的存储备份策略

在以Ceph为代表的主流分布式存储系统中，数据的可靠性默认采用3副本的配置来保证，即将原始数据复制3份分别存储于不同的节点中.这种3副本方案将额外占用相当于原始数据的2倍存储空间，因而数据冗余度为200%.而作为目前被广泛使用的纠删码方案，里德-所罗门码(Reed-Solomon Code，即RS Code)[4]将原始数据切分为n个数据块，并按照一定的编码规则生成m个校验块.对于这n+m个编码块，其编码性质保证通过任意的n个编码块均能重建出所有数据.以n=4，m=2为例，其具有与3副本技术相同的容错能力，但数据冗余度仅为50%.然而在大规模集群环境下，磁盘、服务器和网络的错误已经成为常态，如Facebook的数据中心平均每天会发生50起机器不可用事件[5].当纠删码编码的存储系统发生数据丢失时，系统需要读取至少n块数据，通过计算重建丢失的数据.相比3副本的直接拷贝，占用了更多的磁盘带宽和网络带宽，也引入了额外的计算开销.根据Arafa等人[6]的研究，HDFS和Ceph的纠删码引擎均有明显的性能损失.因此纠删码的应用需要更加高效的方案，来通过更高的并行度解决传统的性能瓶颈问题.Ceph目前的纠删码存储引擎中，每个数据对象被分成n个数据块和m个编码块，每个块存储在一个OSD(Object Storage Device)中，块的顺序号作为对象的属性保存在对象中.因而Ceph的纠删码引擎需要在创建后端时预先定义数据块数n和编码块数m.这对于所有对象均采用相同的设置，没有动态地考虑存储需求.

2.2 RS Code纠删码编码技术

RS Code是在存储系统中较为常用的一种纠删码算法.RS Code是一种基于有限域的编码算法，给定n个数据块(Data Block)D1，D2,…,Dn，和一个正整数m，RS Code根据n个数据块生成m个编码块(Code block)C1、C2,…,Cm.对于任意的n和m，从n个数据块和m个编码块中任取n块就能解码出原始数据，即RS Code最多容忍m个数据块或者编码块同时丢失.RS Code以word为编码和解码单位，大的数据块拆分到字长为w(取值一般为8或者16位)的word，然后对word进行编解码，数据块的编码原理与word编码原理相同.此处变量Di、Ci将代表一个word.

把输入数据视为向量D=(D1,D2,…,Dn)T，编码后数据视为向量C=(D1,D2,…,Dn,C1,C2,…,Cm)T，RS Code可视为矩阵运算G×D=C，其中G是编码矩阵(或称为生成矩阵、分布矩阵，Distribution Matrix)，编码矩阵需要满足任意n×n子矩阵可逆.为方便数据存储，编码矩阵上部是单位阵(n行n列)，下部是m行n列矩阵.下部矩阵常可以选择范德蒙矩阵或柯西矩阵.

范德蒙矩阵的任意的子方阵均为可逆方阵.一个m行n列的范德蒙矩阵定义为：

其中ai均不相同，且不为0.

柯西矩阵的任意一个子方阵都是奇异矩阵，存在逆矩阵.而且柯西矩阵在迦罗华域上的求逆运算，相比于比范德蒙矩阵复杂度更低.范德蒙矩阵求逆运算的复杂度为O(n3)，而柯西矩阵求逆运算的复杂度仅为O(n2).另外通过有限域转换，将GF(2w)域中的元素转换成二进制矩阵，将乘法转换为位运算，降低了乘法运算复杂度.柯西矩阵的定义为：

其中xi和yi都是迦罗华域GF(2w)中的元素.

RS Code最多能容忍m个数据块被删除.假设D2、D5丢失，从编码矩阵G中删掉丢失的数据块或编码块对应的行组成矩阵G1.由于G1是可逆的，则G1×(G1)-1=I为单位矩阵.数据恢复过程如图1所示，即左乘(G1)-1矩阵可恢复原始数据D.

图1 纠删码编码和解码示意Fig.1 Erasure code encoding and decoding

2.3 纠删码编码的改进方法

目前的研究中，对纠删码编码的一个改进方向是优化编码矩阵运算.利用柯西矩阵代替范德蒙矩阵，由于柯西矩阵的求逆运算复杂度更低，且运算为有限域GF(2w)上的运算，更加容易优化，因此速度会有较大提升.另有研究通过GPU加速RS Code的计算，Liu等[7]提出了一种基于GPU的擦除编码实现G-CRS，它采用Cauchy Reed-Solomon(CRS)代码来克服擦除编码的性能瓶颈.通过对现代GPU架构(如Maxwell和Pascal)的大量实验评估了G-CRS的性能，并与其他最先进的编码库进行了比较，结果显示，G-CRS的吞吐量比大多数其他编码库快10倍.Fan等[8]提出了一种同时计算数据块和编码块的解码方案.Zhou等[9]提出将优化矩阵设计、优化计算调度、减少相同异或操作、高速缓存管理和矢量化等技术共同结合，来提高编码效率.

对纠删码编码的另一个方向则是改善编码策略.对于纠删码编码、解码和分布式数据检索可能导致的分层请求增加响应时间，EC-Store[10]提出了在纠删码存储系统中进行数据访问和数据移动的策略，可显著减少数据检索时间.EC-Store是一个基于工作负载访问模式的数据访问和移动动态策略的系统，通过使用两个基准测试工作负载的详细评估，EC-Store产生的存储开销远远低于多备份，同时实现了比多备份和纠删码存储系统更好的性能.在存储设备的利用率方面，Kadekodi等[11]提出大规模集群存储系统通常由异构的存储设备混合组成，不同存储设备之间存在可靠性差异.HeART通过观察磁盘的属性估计磁盘的长期数据可靠性.通过此信息来尽可能减少备份数据的存储.Xiang等[12]提出通过综合考虑延时和磁盘开销来对纠删码编码进行优化.

3 基于文件可用性的纠删码存储策略设计

3.1 基于对象存储的自适应纠删码分布式文件系统设计

现有的基于纠删码的分布式文件系统均采用确定的数据块和校验块数量，在存储系统初始化后，如果需要进行调整，只能重新创建新的存储池.根据不同类型的存储设备(比如机械硬盘和固态硬盘)具有不同的可用性定义，本文基于每个对象的可用性需求，以及每个存储设备的可靠性定义，单独为每个对象计算数据块和校验块的存储方式，并依据系统的实时状态，计算得出最快的存储节点集合，从而实现基于可用性定义的高效对象存储.

现有的模型中均假设pdj和tf(n+m)均为常数，从而给出了确定性的编码方案.我们通过动态地计算pdj和tf(n+m)来确定更加适合当前分布式存储系统的纠删码编码方案，从而更加快速地将数据存储于分布式存储系统.

以此策略设计的对象存储为基础，构建的分布式文件系统框架如图2所示，基于纠删码实现一个对象存储，并以对象存储为基础，在其上应用典型的文件存储、块存储和数据库存储系统，满足不同的分布式存储需求，实现高性能高可用的分布式文件系统设计.

图2 基于纠删码对象存储的分布式文件系统设计Fig.2 Design of distributed file system based on erasure coded object storage

3.2 不同类型的数据及其可用性

在分布式存储系统中，对象持久性是代表了数据的可用性的一个参量，其数值取决于数据的重要性.在各大分布式存储提供商的服务等级协议(Service Level Agreement，即SLA)中均对一年期对象持久性做出了保障.

表1 不同服务提供商给出的对象持久性保证Table 1 Object persistence guarantees given by different service providers

3.3 数据可用性和磁盘故障率的关系

要根据存储设备的可用性计算对象的持久性，在目前的分布式存储系统的磁盘模型中，假设了每块磁盘的故障率最大为pd，那么可以推导得出至少有n块磁盘不发生故障的概率为：

但在实际情况中，每块磁盘故障率不同，与磁盘型号和磁盘使用时间相关.根据Ma等人[13]的研究，磁盘损坏的概率可用重分配的扇区数(Reallocated Sectors)来定量描述.我们可以根据磁盘的S.M.A.R.T.信息[14]得知重分配的扇区数，以下记作NRS.为了计算该块重分配扇区数为NRS的磁盘的故障率，我们统计数据中心中所有的磁盘，记：

1)该数据中心同型号所有磁盘中所有重分配扇区数为NRS的磁盘数量为nall

2)该数据中心同型号损坏磁盘中所有重分配扇区数为NRS的磁盘数量为nfail

则根据贝叶斯定理我们可以得到这块重分配扇区数为NRS的磁盘的故障率预测值：

b)‖Sd‖=k

3.4 基于存储速度的节点选择策略

存储设备速度主要反映在磁盘对当前要进行的读写操作所需要的时间上.磁盘的读写时间主要有3部分组成：队列等待时间、读写延迟和数据写入时间.队列等待时间tqueue主要来源于系统负载，当磁盘读写请求过多，超过了磁盘本身的服务能力，读写请求便会被操作系统放入等待队列，从而产生队列等待时间，通过更好的调度更平均地分配各个存储节点的任务量可以有效地减少队列等待时间.读写延迟tlatency主要来源于本地磁盘寻道或远程磁盘建立连接等过程，通过优化调度算法、采用就近节点进行调度等方案可以有效地减少读写延迟.而数据写入时间仅仅取决于数据量和磁盘本身的性能，除了减少数据冗余或更换更高规格磁盘之外，这部分时间难以进行优化.因此总的磁盘读写时间td可以表示为：

对于分布式存储系统来说，特别是地理分布的分布式存储系统，由于受网络环境波动的影响，延时tlatency和带宽bandwidth是实时发生变化的，我们在计算总的磁盘读写时间td时，需要动态采集延时tlatency和带宽bandwidth.在On-demand ARECS算法中，我们把每次数据读写时的延时tlatency和带宽bandwidth参数进行保存，以便下次进行数据写入时使用.

对于分布式系统，每个节点的读写操作可以独立于其他节点进行，因此可以实现并行读写，则总的读写时间自然取决于最慢速节点读写所需要的时间：

其中tcalc为纠删码编码所耗费的CPU时间.根据Liu等人的研究[15]，纠删码的编码效率在块数提高时急剧上升，因此我们尽量选择数目适中的编码块和校验块数，在数据量一定的前提下，选择n+m更小的编码块方案可以显著地降低纠删码编码时间，从而提升系统的性能.

对于较大的对象，我们可以将其分为多个块，不同块之间可以并行进行存储，从而提高存储效率，因此易证得将数据分为r块{b1,b2,…,br}的总读写时间为：

3.5 损坏节点更换对模型的影响

然而在实际的数据中心中，每天均有专人负责损坏磁盘的更换和数据重建，因此磁盘更换和重建不可能需要一年时间完成，我们假设磁盘更换和重建时间为tr年.因此模型中公式实际上表现为更换磁盘并重建数据这一周期内的情况：

显然节点可靠性应达到或超过对象的持久性意味着f(n,m)≥0.而编码块m块数越少，数据冗余度和存储延迟越快，因此m应取满足约束f(n,m)≥0的最小值：

4 实验与分析

4.1 Tahoe-LAFS实验环境

为了验证动态选择存储节点和编码方案的策略On-demand ARECS，我们在Tahoe-LAFS[16]上实现了On-demand ARECS算法.Tahoe-LAFS是一个开源的分布式文件系统，其基于zfec纠删码编码库进行实现.Tahoe提供3种不同的节点：

1)介绍节点：介绍节点与所有存储服务节点和存储客户节点保持连接，从而将各节点介绍给其他节点.

2)存储节点：存储节点负责存储由纠删码编码的块.

3)客户节点：客户节点负责连接到存储节点，接受并处理客户的上传、下载数据的请求.

Tahoe在默认情况下针对所有数据均采用(n+m,n)=(10,3)的纠删码编码策略.Tahoe将文件先进行加密，然后分为若干数据单元，每个单元独立进行编码.Tahoe将每单元分为n块，然后通过编码矩阵由这n块数据生成m个校验块，然后将这n+m个块分别存储于独立的存储服务器中.在选取存储服务器的过程中，Tahoe会从所有剩余足够存储空间的节点中随机选取n+m个不同节点.

我们对Tahoe进行了修改，实现了On-demand ARECS算法，动态确定编码方案和存储节点.根据Pinheiro等人的研究[17]，使用时间为一年的磁盘pd=1.7%，而三年磁盘的pd=8.6%.我们基于KVM虚拟化集群，部署了一个37个节点的分布式文件系统实验环境，如表2和图3所示，其中Storage Server A和Storage Server B在3个存储集群中平均分布，即每个集群均各有6个两类节点，共有36个存储节点和1个客户节点.

表2 不同存储节点的配置Table 2 Configuration of different storage nodes

为了保证各集群之间的独立性，我们将3个存储集群分别布置于伦敦、法兰克福和阿姆斯特丹，客户节点布置于纽约，从而避免单个机房由于不可抗力发生损坏.这可以最大限度的保证我们模型中的对事件独立性的假设.

由于我们的模型中考虑到了不同节点间的延迟问题，因此我们于真实Internet的环境进行测试，以期得到更加贴近实际应用的实验数据.图3中各个节点间均通过Internet进行连接，并标注了实验过程中测量到的各节点之间平均延迟(RTT)和平均带宽的一个典型值.

图3 Tahoe-LAFS实验集群示意Fig.3 Tahoe-LAFS experimental cluster schematic

值得注意的是，在Internet上，由于不同机房间链路的拥挤程度不同，节点间RTT与节点间带宽并不完全成负相关关系，地理位置较远的两个节点，若选择较优的数据链路，同样可以达到较大的带宽.比如测试环境中伦敦节点到法兰克福节点的RTT高于其到阿姆斯特丹节点的RTT，但在长时间传输数据的过程中，测得的带宽则是伦敦节点到法兰克福节点更高.

4.2 不同磁盘故障率模型的数据冗余度对比

在图4中我们可以看出，在部分特殊情况下，比如n=21到n=24区间中，针对我们的实验环境，On-demand ARECS得到了和固定磁盘故障率均选取了m=5的编码方案.这是因为，在实际的分布式存储中，我们需要对编码块的数量进行向上取整，也就是说，只要我们计算得到的4

但对于绝大多数情况来说，通过实验我们可以得到，使用On-demand ARECS模型计算磁盘故障率，相比于传统算法均降低了数据的冗余度.如图4所示，在n=1到n=30区间中，数据冗余度平均降低了18%.由于On-demand ARECS算法需要针对存储系统的实时信息动态选取编码算法，因此选取平均性能更好的动态磁盘故障率模型，能有效地减小数据冗余.

图4 不同磁盘故障率模型的数据切分数与冗余度关系Fig.4 Relationship between data block numbers and redundancy of different hard disk failure rate models

4.3 On-demand ARECS算法的文件存储速度对比

我们在Tahoe-LAFS实验环境中实现了On-demand ARECS算法.在上述实验环境中，我们针对10MB、50MB和200MB三种文件大小进行了实验，测试了不同分块情况(n+m,n)下文件传输时间如图5所示.

图5 不同数据分块数的存储时间表现Fig.5 Storage time performance of different number of data blocks

根据图5可以看出，当n较小时，数据冗余度较高，每个分块数据量更大，data_size更大导致存储时间较慢，当n过大时，由于纠删码编解码tcalc时间更长，同时选择的慢速节点更多，bandwidth更小，同样导致文件存储时间更长.特别地，针对本文测试环境的分布式存储系统来说，选取n=16左右存储耗时最短.故而是否选择了合适的编码方案，会很大程度上影响存储系统的存储延迟.On-demand ARECS算法通过动态选取最优的储存节点和编码方案，从而减小数据的存储延时.

我们在Tahoe-LAFS上还分别实现了On-demand ARECS算法、原始的多备份方案以及目前的纠删码方案，针对10M、50M和200M大小的文件进行了实验，实验结果如图6所示.在实验中，On-demand ARECS算法选取了n=16且m=4的编码方案，共采用了20个节点存储数据块.原始纠删码算法选取了n=10且m=3的编码方案，共采用了13个节点存储数据块.而多备份方案则直接存储了4份原始数据的备份.

图6 On-demand ARECS算法和多备份、固定纠删码算法存储延时对比Fig.6 Comparison of storage delay between On-demand ARECS algorithm and multiple backup and fixed erasure coding algorithms

根据实验结果显示，依据分布式存储系统的节点状况动态选择存储节点和编码方案，虽然在实验环境中使用了更多的节点存储数据，但由于提高了系统的并行度，因此写入性能有着较为明显的改善，写入时间平均降低了46%，相比原始的多备份方案和目前的纠删码方案均有显著提升.并且相对于大文件来说，这种提升效果更为明显.

5 结 论

本文针对现有的分布式存储系统中的纠删码方案做出了总结，并针对在数据中心中多种不同种类、不同批次的磁盘共存的特点，提出了一种动态选择存储节点和编码方案的策略On-demand ARECS.我们在Tahoe-LAFS上实验了On-demand ARECS，相对于传统编码方案，On-demand ARECS节约了平均18%的存储空间，并将存储所用时间降低了46%.我们未来将研究如何更加高效地做到纠删码重建，使其能更大限度地减少数据中心内部的数据传输.