一种面向容灾存储系统的重复数据删除方法

◆彭 刚



一种面向容灾存储系统的重复数据删除方法

◆彭 刚

（四川大学计算机学院 四川 610065）

针对海量数据的存储和备份存在大量的冗余数据，造成存储空间的巨大浪费问题，本文分析了现有的重复数据检测和删除技术，提出了一种面向容灾存储系统的重复数据删除方法——FWinnowing（Fast Winnowing ）。FWinnowing采用改进后的Winnowing动态分块算法对数据进行分块，使用MD5计算各个分块的数据指纹值，通过检索指纹库来判断指纹值是否已经存在，从而判断出该块所对应的数据是否重复，最终达到重复数据检测和删除的目的。本文对FWinnowing进行了实验验证，结果表明该方法相比较现有的重复数据检测和删除方法，有效地降低了网络传输流量并提高了重复数据检测率。

容灾备份；重复数据；FWinnowing

0 引言

市场调研机构IDC预计，未来全球数据总量年增长率将维持在50%左右，55%的数据需要进行容灾备份并且应用系统中有60%的数据是冗余的[1]。为了节省存储资源，降低网络数据传输带宽重复删除技术已成为一个热门的研究课题。基于目前该领域的研究成果，比较知名的重复数据删除技术应用有基于全文件检测的Windows2000单实例存储系SIS、基于定长分块检测的归档存储系统Venti、基于文件内容（不定长分块）检测的低带宽网络系统LBFS等[2]。以上各应用采取的文件分块算法存在不同程度的缺陷。为此，本文设计并实现一种面向容灾备份存储系统的更为有效的重复数据删除方法——FWinnowing。

1 方法应用场景

图1 灾备系统网络拓扑图

如图1所示，该图为灾备系统网络拓扑图。当备份发起时，装有灾备代理的客户端需要将不同时间点产生的备份文件进行分块，并且计算各个分块的MD5值作为各个分块的指纹值，并将各个分块指纹信息发送给服务器。服务器通过检索指纹库查找该指纹值是否存在。如果存在，表明该块数据为重复数据，仅需要将该数据块的索引记录到文件的元数据信息中；如果不存在，则需要将该数据块上传至服务器，并更新文件的元数据信息和数据块索引信息。当需要对文件进行恢复时，只需要找到文件的元信息，根据文件元信息并通过数据块索引文件找到指定的数据块进行文件重构即可恢复已经备份到服务器的文件。

2 方法采用的文件分块算法

文件分块算法按分块粒度大小主要分为：定长分块、可变长分块和滑块分块。定长分块算法对数据的插入和删除非常敏感，不能解决比特偏移问题，冗余数据删除率低；滑块分块算法会产生不定长的数据碎片[3]。因此，重复数据检测和删除技术通常采用可变长分块算法，实际应用中主要有CDC（Content-Defined Chunking）和Winnowing两种算法。

2.1CDC算法原理

CDC是由麻省理工学院的BenjieChen等人发表的论文《A Low-Bandwidth Network File System》中提出，主要解决了固定长度分块方法对插入位置敏感问题，并在重复数据删除领域得到广泛应用。CDC的定义：给定一个Rabin指纹算法f,选取滑动窗口长度为w，并选取两个正整数d和r(d

图2 CDC数据分块示意图

CDC可变分块重复数据检测技术已应用在P2P文件系统Pasta、Pastiche备份系统、Deep Store 归档存储系统。但是，该算法存在一定的局限性：滑动窗口指纹值不符合条件时（f（w）mod d的值始终不等于r），会导致分块过大，重复数据检测率很低；d和r设置的太小，导致额外存储分块信息的开销很大。

2.2 Winnowing算法原理

Winnowing算法在2003年由美国伊利诺斯大学的一位知名教授Saul Schleimer提出。该算法广泛用于检测两个文件中是否有相同的内容和是否存在剽窃现象。Winnowing算法首先设定参数k和w（k指进行哈希的字节数，w指滑动窗口的大小）将文档分成很多个长度为k的连续子串；其次，对文件每个子串通过公式（1）映射成一个整数，最终得到一个离散化的数值序列。

（b为基数，Tk表示滑动窗口中第k个字符，asc(Tk)表示该字符的ASCII值）

最后，使用滑动窗口扫描该数值序列，选取每个窗口内最小的哈希值，将其对应数据块在文件中得偏移量作为文件的分割点。该算法的示例图如图3：

图3 Winnowing算法示例图

Winnowing有效地克服了对数据的插入敏感问题，并且相对于传统的基于文件内容分块算法具有较好的稳定性[3]。但是仍然存在一定的不足：当基数b取值偏大时，可能造成基本数据溢出，此时需要构建新的存储结构，造成计算复杂度大降低计算性能；选取最小散列值时，如果选取策略不当可能会增加算法延时。

2.3FWinnowing算法原理

基于Winnowing算法的基础上，本文对Winnowing算法所采用的哈希值计算和最小散列值选取策略两方面加以改进，得到一种更加高效的FWinnowing算法，并应用于备份文件分块中。具体改进如下：

（1）哈希值计算方法的改进

首先对公式（1）加以改进，取基数b为2,并使用移位运算代替复杂乘法运算，提高算法运算效率，得到公式（2）如下：

根据哈希值计算规律发现，后一个子串哈希值计算可以在前一个哈希值的基础上进行两次移位运算和两次加法计算得到，如公式（3）所示：

改进后的哈希值计算方法，在公式（1）的基础上，大大降低了计算复杂度，节省了计算时间。

（2）最小散列值选取策略的改进

Winnowing算法中关于数据块分界点的选取只是提到选取滑动窗口中最小值作为数据块的分界点，但是对于每个滑动窗口中的数据都要经过整体排序找出最小值的话，这会增大时延，降低算法的执行效率。对此本文改进如下图4所示：

图4 FWinnowing最小散列值选取策略示例图

经过对Winnowing算法在哈希值计算和散列值选取策略两方面的改进后最终得到FWinnowing算法。FWinnowing的算法流程如图5所示：

图5 FWinnowing算法流程图

3 实验分析

3.1实验数据集

本文实验过程中，灾备客户端和灾备服务端采用双机直连的连接方式和100Mb/s网络环境。实验分别对多个相似数据集进行备份，通过统计不同重复数据删除方法在数据分块所消耗的时间以及数据传送过程中所产生的流量大小来验证方法的效能。实验数据集采用不同版本的Tomcat源码解压后的文件集，并对该文件集进行处理（消除空白行、大量空格等），具体如表1所示：

表1 实验数据集

3.2实验数据分析

本文对实验数据集进行备份，通过统计将备份数据上传至服务端所消耗的网络流量来衡量各个方法的重复数据检测和删除的执行效率。

图6是在设定备份文件分块大小区间（介于128B和1024B之间）情况下，比较CDC方法和FWinowing方法的重复数据检测率实验对比数据数据，结果显示FWinnow方法相比较CDC方法具有更好的重复数据检测率。图7是对备份数据经过CDC和FWinnowing两种不同方法的重复数据检测和删除后上传至灾备中心产生的网络流量对比数据。实验结果显示FWinnowing方法相对于CDC方法具有较低的网络流量。

图6 重复数据块检测率对比数据

图7 数据传输网络流量对比数据

4 结束语

本文从灾备存储系统对重复数据检测的需求现状出发，分析了现有的重复数据检测方法存在的不足，将Winnowing算法改进后得到的FWinnowing算法并应用在文件分块上，通过对比实验验证了FWinnowing方法相比较现有的方法拥有较低的网络流量和较好的重复数据检测率。因此，本文提出的重复数据删除方法为后续该领域的研究提供了有益的探索和借鉴。

[1]敖莉, 舒继武, 李明强.重复数据删除技术[J].Journal of Software, 2010.

[2]毕朝国, 徐小龙.一种云存储系统中重复数据删除机制[J].计算机应用研究, 2014.

[3]许艳艳, 雷迎春, 龚奕利.基于可变长分块的分布式文件设计与实现[J].体系结构与软件技术, 2016.

[4]马晓旭.基于云存储的灾难备份与恢复技术研究[D].四川大学, 2012.

[5]Bobbarjung DR, Jagannathan S, Dubnicki C. Improving duplicate elimination in storage systems. ACM Trans. on Storage, 2006.