基于纠删码的云存储数据可靠性保障

王芳芳

摘要摘要：云存储系统由于其系统复杂性和业务特征，使数据可靠性受到严重挑战。针对云计算环境下带数据去重的云存储系统的内部数据保护问题，提出一种基于纠删码的数据可靠性保障机制，采用多种纠删编码算法及配置方法对去重数据块进行编码保护。该机制具有良好的综合性能与可扩展性。

关键词关键词：云存储；数据可靠性；纠删码；数据去重

DOIDOI：10.11907/rjdk.1431041

中图分类号：TP309.2

文献标识码：A文章编号文章编号：16727800（2015）004013702

0引言

云存储是云计算服务商提供的一种IaaS模式的基础服务，其通过硬件集群、高速内联网络以及分布式文件系统等资源和技术，将大量设备中的存储资源整合成一个整体，共同对外提供基于网络的数据存取服务。它的业务特点是向外界提供统一、透明的数据操作接口，将所有的分布式存储细节都封装在系统内部[1]。

目前多数云存储系统（网盘、云空间等）为控制系统规模，降低系统建设和管理成本，均采用了数据去重技术来压缩数据量。鉴于其它种类云存储系统的数据保护要求较为简单，现有机制已经能够很好地满足需要。因此，本文针对这种带数据去重的云存储系统，对如何保障其内部数据可靠性进行了研究。

针对去重系统的数据可靠性保障，传统做法包括使用更加可靠的底层存储设施（如RAID阵列），以及对重要的数据块保留更多副本[2]。前者部署方便，对上层透明，但是容错能力差、恢复过程慢；后者容错能力强、恢复过程快，但空间占用多、带宽消耗量大、成本高。因此，这两种技术仅对小规模存储系统以及数据量不太大的核心业务较为实用。对于云存储这种大规模分布式存储系统而言，由于其节点数量和数据规模极其庞大，如果每个节点都采用高端设备，或者系统整体采用复制冗余机制，均会导致整体成本的极大增长，使建设和使用这类系统变得难以承受，从而失去实用性[3]。相对于各类本地存储系统，云存储系统内部的数据重要性高但活跃度较低，因此有条件在系统内使用较为复杂的纠删码来保护数据，以便在存储成本和可靠性间达到更好的平衡。为此，本文采用多种不同的纠删码算法及配置方法对去重数据块进行静态编码，并提出了基于纠删码的云存储系统数据可靠性保障机制（Reliability Guarantee Mechanism for Deduplication Cloud Storage，RGMDCS）。

1纠删码选取

1.1ReedSolomon编码

ReedSolomon编码（下称RS编码）是目前使用最广泛的纠删码之一。RS编码同时具有MDS属性和系统属性，因此它编码生成的n个编码数据片段包含m个原始数据片段以及n-m个校验数据片段，其中任意片段丢失后均可使用任意m个存留的片段来恢复。

RS编码的编码过程可由式（1）描述：

1.2Tornado编码

Tornado编码不具有MDS属性，但具有系统属性。Tornado编码的编解码操作计算开销较小，而且用到的节点数目也较少。因此，Tornado编码比传统的MDS纠删码具有更快的运算速度，其数据修复过程需要更小的数据传输量，非常适合大规模的分布式存储系统。

2静态密码策略

2.1设计方案

考虑到云存储系统面对的数据具有复杂性和多样性，RGMDCS系统采用了Rabin Fingerprinting算法对数据进行变长分块。然而，相关研究表明，若使用变长分块算法对文件进行分块去重，由于数据块大小不同且都比较小（通常为几十字节到几百KB），在存储节点中将数据块直接存储会大大增加设备中的磁盘碎片，导致其访问效率低下，造成系统性能产生较大程度下降[4]。针对这一矛盾，RGMDCS将多个变长的数据包打包成较大的定长对象（Object，一般为几MB）进行存储和管理，定长对象的大小根据不同的应用场景和相关实践来配置。数据块（Chunk）是存储节点的最小数据访问单元，通过对应的数据块标识符（Chunk ID）进行访问。根据数据块的不同大小，各个定长对象包含不同数量的数据块。当从服务接口接收到新的数据块时，存储节点先将积攒的变长数据块打包成固定大小的对象。如果定长对象当前所剩空间不够放置后续数据块，则剩余空间填0（Padding），后续数据块新开一个对象继续放置。随后存储节点对这些对象进行分组并用纠删编码算法对分组进行编码，生成编码对象组（包含原始对象和校验对象），最后将编码对象组内的所有对象分布到不同的节点上存储。

2.2系统业务流程

RGMDCS系统的服务接口接收到客户提交的待存文件后，其分块逻辑则会使用Rabin Fingerprinting算法将文件切割成互不重叠的变长数据块，再使用特定的哈希算法对数据块内容进行计算，用得到的结果值作为数据块标识符，并将这些标识符传给业务处理模块。业务处理模块将数据块标识符与元数据管理模块中所有已知数据块的标识符进行比较。如果标识符已经存在，则该数据块属于重复数据块，无需存储，只需对其在Chunk_Table中的Chunk_RC属性加以操作；如果标识符不存在，则该数据块属于新数据块，业务处理模块将该数据块的初始属性信息作为一条新记录保存到元数据管理模块的Chunk_Table中。待积累了一批新数据块之后，业务处理模块询问资源管理模块，由资源管理模块根据系统当前整体情况挑选一个合适的存储节点负责这批数据块的存储操作，业务处理模块最后通知各服务接口将相应的数据块传输到该节点。当一个文件的数据全部保存完毕之后，业务处理模块将文件的属性信息及其与数据块的映射关系保存到元数据管理模块中的File_Table中。

存储节点在接收到一批新的数据块后，先将它们打包成定长对象，随后根据编码管理模块的指挥，将若干个定长对象分成一组，然后执行特定的纠删编码算法（RS编码或Tornado编码），生成若干个编码对象（合称为一个编码对象组，包含了原始对象和校验对象）。随后，存储节点在资源管理模块的指挥下将编码对象组内的各个对象分散到包括自身在内的不同节点上存储（每个节点最多保存同一个编码对象组中的一个对象）。完成此操作后，存储节点将数据块与对象的映射关系以及对象的分组、编码和存储信息提交到元数据管理模块，由其保存至Object_Group_Table和Group_Table中。

实际上，在云存储这种大规模分布式存储系统中，某些存储节点之间存在着一定关联性，例如相近的物理位置、共享的供电设施和网络链路等，导致它们很可能同时或连续失效，这样的节点集合称作错误域。针对这一情况，RGMDCS的资源管理模块在为一个编码对象组挑选不同节点进行存储时，会挑选分布在不同机柜、不同供电及网络区域的那些节点，以降低某个错误域内多个节点同时或连续失效对数据造成的损失。此外，对于同一个或同一批文件所属的新数据块，其打包并分组编码生成的编码对象组会被资源管理模块尽可能地调度到同一组节点存储。这样做可有效地减少文件所依赖的节点数，增强了数据可靠性。

2.3数据修复过程

RGMDCS系统采用动态分布式并行修复机制：当资源管理模块检测到某个存储节点失效时，从一个源数据管理模块查询该节点包含的所有对象信息，然后调度系统内多个健康节点同时开展修复工作。这样能够均衡系统负载，加快数据修复过程，减少修复过程中数据丢失的可能性，从而进一步增强系统的数据可靠性。

如图1所示，当存储节点SN（a1）失效时，其所存的对象<1，1>和<2，n>丢失。为了修复这两个对象，系统分别随机选择SN（a2）和SN（am）作为修复的目标节点。SN（a2）和SN（am）收到修复任务后，分别从对象组1和对象组2中并行地读取修复所需要的对象，然后依靠纠删编码算法修复丢失的对象并保存在自身中。最后各目标节点通知元数据管理模块更新Group_Table中相应的编码对象组信息，将新修复对象的位置指向自己。

2.4动态负载均衡

除了保障数据可靠性，RGMDCS系统的分布式动态修复机制还可以实现系统的动态负载均衡。如图2所示，在SN（a1）节点发生超载时，可以通过纠删编码算法由其它轻载节点上的对象计算出该超载节点上的对象，进而将对象副本临时存放在这些轻载节点上并对外提供服务，从而减轻超载节点的负担。RGMDCS系统的这种动态负载均衡操作对过载节点完全透明，整个过程无需其参与。

3结语

采用静态密码策略的RGMDCS系统是一个分布式、可扩展的系统，其数据分块操作由各服务接口完成，每个存储节点都可以进行数据块的打包、分组、编码、存储、读取、删除和修复操作，所以系统的负载被均衡到各节点上，每个节点的I/O和计算资源都可以被充分利用。因此，该方案具有良好的综合性能和可扩展性。

参考文献参考文献：

[1]ARMBRUST M，FOX A，GRIFFITH R，et al.A view of cloud computing[J].Communications of the ACM，2010，53（4）：5058.

[2]LIU CHUANYI，LU YINGPING，DU DAVID，et al.ADMAD： applicationdriven metadata aware deduplication archival storage system[C].25th IEEE Conference on Mass Storage System and Technology，2008：2935.

[3]TANNER R.A recursive approach to low complexity codes[J].IEEE Transactions on Information Theory，2006，27（5）：533547.

[4]顾瑜，刘川意，孙林春，等.带重复数据删除的大规模存储系统可靠性保证[J].清华大学学报：自然科学版，2010，50（5）：739744.

责任编辑（责任编辑：黄健）