一种广域网环境下的分布式冗余删除存储系统

由于数字信息的爆炸式增长，现今的大规模网络应用中所存储的数据规模，可以到达上百太字节甚至拍字节的数量级。而传统的存储系统，由于缺乏足够的可扩展性，无法适应日益增长的需求。以Amazon S3[1]为代表的广域网环境下的分布式存储系统凭借其规模的可扩展性、数据的可靠性、服务的可用性、系统的可管理性以及低廉的使用成本等巨大优势，已经在构建网络应用时被广泛认可。

广域网环境下的分布式存储系统将分布在广域网上的资源整合在一起，为网络应用提供存储服务平台。来自不同网络应用和用户的数据存储其中，这些海量的数据中存在着大量的冗余。这些冗余数据不仅在存储时占据了存储系统大量的存储空间，并且在被传输到存储系统的过程当中，浪费了大量的网络用户、网络应用和存储系统的网络带宽资源，使存储系统的资源利用率和整体性能受到严重影响。

本文提出一种在广域网环境下的采用冗余数据删除技术的分布式存储系统原型——AegeanStore。在AegeanStore中采用客户端相关的冗余数据删除技术。该技术通过客户端和服务器端的合作，不仅可提高存储设备的利用率，而且可减轻客户端和服务器之间的网络负载压力，从而进一步提高存储系统的可扩展性和整体性能并且进一步降低其成本。

1 冗余数据删除技术

冗余数据删除技术是将数据集中的冗余数据发现并去除的应用技术，可以分为两大类：相同数据删除和相似数据删除[2]。

1.1 相同数据删除技术

相同数据删除技术首先将数据划分为数据块，然后使用具有抗碰撞特性[3]的哈希函数计算每一个数据块的哈希值作为该数据块的数字指纹，再通过比较数据块的数字指纹来发现相同的数据块。目前，最常用的相同数据删除技术是基于内容的划块(CDC)算法[4]，其流程如图1所示。

CDC算法存在3个参数，一是目标可变数据块的预期大小S，二是滑动窗口的大小W，三是一个小于S的自然数M。当使用CDC算法处理一个文件时，从文件头开始以每次一字节的步长向后滑动窗口，使用哈希函数计算滑动窗口内部的哈希值H；将H mod S与M进行比较，如果不同，则滑动窗口；如果相同，则发现数据块边界，然后用具有抗碰撞特性的哈希函数计算该数据块的数字指纹；最后，将获得的数字指纹到索引中查找，如果存在则发现冗余数据块，否则说明该数据块是新的，需要存储到系统当中。

1.2 相似数据删除技术

相似数据删除技术分为两个阶段，相似数据检测和相似数据编码：

(1)相似数据检测，首先要定义数据的特征值，该特征值的特点是保证具有相同或相似的特征值的数据具有相同或相似的内容。在提取数据的特征值之后，通过特征值的比较获得相似的数据。常用的相似数据检测技术包括基于Shingle的检测技术[5]。

(2)相似数据编码是在使用相似数据检测，获得具有相似性的数据集之后，在该数据集上采用的编码技术，用于减小该数据集所占用的存储空间。常用的相似数据编码技术包括基于Diff的相似编码技术[6]等。

2 AegeanStore的体系结构

AegeanStore体系结构如图2所示。AegeanStore由客户端、应用服务、文件系统服务、索引服务和数据块服务5个部分组成。

当客户端需要将文件数据存储到应用服务时，首先调用本地冗余数据删除工具，运行数据块划分算法，将要上传的文件分成数据块，并计算每个数据块的数字指纹，然后将这些数字指纹发送给应用服务；应用服务接收到文件上传请求后，记录应用相关信息，再将请求转发给文件服务；文件服务记录文件的元信息(包括文件属性，例如文件的大小、修改时间等,以及文件的冗余数据删除信息，如文件所有组成数据块的数字指纹等)，再将请求转发给索引服务；索引服务进行块的数字指纹查询工作，将结果返回给文件服务；文件服务将结果通过应用服务返回给客户端；客户端按照返回结果，只将未出现在数据块服务中的数据块上传；最后，当所有新数据块都存储到数据块服务中之后，文件服务将新数据块的信息更新到索引服务当中。下面将分别介绍5个部分的设计与实现。

2.1 客户端

客户端是为某个应用服务开发，运行在使用该应用服务的用户的网络终端上的程序。程序通过响应用户输入并且同该应用服务进行消息交换，使用户能够使用该应用服务提供的服务。AegeanStore的客户端除了完成传统网络应用的客户端的响应用户输入、网络消息交换、身份验证、数据传输等任务之外，还要在冗余数据删除技术中，完成重要的任务：因为AegeanStore使用冗余数据删除技术的目标是减少冗余数据在网络传输时造成的浪费，所以冗余数据删除中的可变数据块划分和计算每个数据块的数字指