网络备份中重复数据消重技术研究

郑轲　俞婷

摘 要：随着信息化建设的深入，数据信息量呈几何级增长，为解决数据大量重复而导致存储空间浪费，文章将重点研究重复数据消重的问题。文章首先给出了数据消重技术的原理，并对数据消重类别，数据指纹和数据划分进行了阐述，接着重点分析了数据消重领域中的变长分块算法，元数据索引和客户端与服务端交互等。

关键词：重复数据；消重；变长块；元数据；客户端；服务端

1 概述

科技的飞速发展正在加速产生大量高价值数据，虽然数据呈爆炸性增长，但重复数据存在信息处理和存储的各个环节。传统的数据保护技术如周期性备份、版本文件系统等更能加速重复数据的增长。为了抑制数据过快增长，重复数据删除已成为一个备受关注的研究课题。

2 消重技术

数据消重技术原理是将一个文件或多个文件分割成很多小块，利用一定的算法计算这些小块的数据指纹，数据指纹相同则说明数据块内容相同，存储时只需存储相同数据块的一份。

2.1 重复数据划分

重复数据删除通过重复数据检测技术来确定存储系统中重复的文件和数据块，重复数据删除主要有两种：（1）文件级重复数据删除；（2）数据块级重复数据删除，可以更进一步在文件内部搜索相同的数据块，保证数据块的唯一实例存储。重复数据消重框架图如图1所示，首先将文件切分成小块，并用SHA1算法计算每个小块的数据指纹，若数据指纹存在于指纹索引中，则删除该指纹对应的数据块，否则将数据块写到存储设备中。

2.2 数据指纹算法

目前文件内部重复数据检测普遍用Hash算法：首先对数据进行哈希，从而得到唯一的哈希值，哈希函数以MD5和SHA1算法最为流行，MD5生成一个128位的哈希值，SHA1生成一个160位的哈希值，在相同的硬件条件下，MD5的计算速度是227MB/S，而SHA1的计算速度是83MB/S，应根据实际的应用环境来选取适当的哈希函数。

2.3 数据块划分

基于文件内容数据块划分粒度小，它的切割长度在4-24K之间，数据分块算法主要有定长切分和CDC切分。定长分块算法优点是简单，但它对数据插入和删除敏感，处理低效。CDC变长分块可将文件或数据流分割成长度大小不等的数据块，实现变长分块需要滑动窗口，滑动窗口对文件数据计算数据指纹，如果指纹满足某个条件，则把窗口位置作为块的边界。

3 消重技术难点

重复数据删除主要有三方面指标：重删率，扩展性和吞吐率。重删率说明软件能挖掘出多少重复数据；扩展性是重删系统能否扩展到超大规模的数据量；吞吐率是系统处理数据的速度。这三个指标都很重要，同时优化其中两个比较容易，但优化三个标准很困难。

3.1 變长分块算法研究

尽管变长分块对数据序列不太敏感，但由于数据块边界点比较消耗CPU资源，从而影响重复数据删除性能。在实际中并不期望数据块划分得过大或过小，因此对基于滑动窗口技术的变长分块算法进行一些优化，让滑动窗口从数据块最小值地方开始滑动，如果滑动到数据块最大值地方还没有找到数据块的边界点，便硬性规定此处为数据块的一个边界点。对文件或数据流的划分用到一个48字节的滑动窗口，计算函数如下：

3.2 元数据块检索

重复数据删除的索引是最难设计的，好的索引必须有高扩展性，高吞吐率和高删重率，但现实情况中很难实现以上三个目标。在这里采用渐进式抽样索引，每T个指纹抽样一个指纹，这样索引就缩小到原来的1/T，这样做导致索引的命中率就减小到1/T，但是考虑到数据流的局部性：如果上一次备份A和B是连续出现的，那么这一次备份A/B非常可能仍是连续的，如果每次命中抽样指纹，就将该抽样指纹所属的容器里所有指纹读到缓存，那么接下来接收到的指纹虽然在索引未命中，但大多数会出现在缓存中，这就非常有效地提升了重删率。

3.3 客户端与服务端交互

在一个典型的C/S架构中，即使解决了索引问题，端到端的性能仍然会受限于客户端。典型的客户端按照以下顺序进行：（1）读取文件数据；（2）分块和计算指纹；（3）发送指纹到服务器，等待服务器的查询结果；（4）发送服务器未查询到的数据块。最后一点网络也非常可能成为全局性的瓶颈，为了满足性能需求，用TCP实现的RPC协议会保持多个TCP连接，为减少来回开销和提高吞吐率，所有RPC请求都异步。

4 消重应用领域

4.1 网络备份系统

重复数据删除技术为数据保护领域带来革命性的突破，有效改善磁盘数据保护的成本效益。现在基于磁盘的数据保护方案被广泛使用，并且在未来会继续增长，人们所要备份的数据越来越多，重复数据删除技术的出现，为存储容量最小化找到有效方法。

4.2 归档存储系统

由于参考数据数量不断增长，而法规遵从要求数据在线保留的时间更长，理想的归档存储系统应能满足长期保存归档数据的需求，并且总拥有成本要低于生产环境，重复数据删除技术通过消除冗余实现高效率的归档存储，从而实现最低成本。

4.3 异地容灾

在远程灾备系统中，需要将大量的数据迁移到异地系统中，随着数据量的不断增长，数据传输的压力越来越大，通过重复数据删除技术在数据传输前检测并删除重复的数据，可以有效减少传输的数据量，提高传输数据速度。

5 结束语

重复数据删除的关键是找到文件或数据流中的所有重复数据，以保证系统只存储元数据的唯一实例，这是消重系统的目标，但为了保证消重系统的高扩展性和高吞吐率，三方面的指标很难达到一个平衡点。一旦数据扩充到很大，系统的消重率，扩展性和吞吐率也将随之下降，为了提升一方面指标，必定会降低另一个或两个指标，文章在变长分块算法，元数据检索和客户端与服务端等方面做了一定的研究。

参考文献

[1]颜军.重复数据删除带来集群架构革命[J].计算机世界，2008.

[2]廖海生，赵跃龙.基于MD5算法的重复数据删除技术的研究与改进[J].计算机测量与控制，2010.

[3]什么是重复数据删除技术[EB/OL].重庆：赛迪网.2008.

作者简介：郑轲，嘉兴学院讲师，主要研究方向：数据安全。

俞婷（1988-），女，浙江嘉兴人，嘉兴学院助教，研究方向：网络教育，数据挖掘。