重复数据删除技术在云存储中的应用

宋桂平

（河南测绘职业学院，河南 郑州 451464）

在大数据时代，要想整合数据资源、挖掘数据价值，首先要从海量数据中筛选、检索出目标数据。为了减轻这一工作量，必须要进行“数据瘦身”。而重复数据删除（De-duplication）就是一种常用的数据缩减技术。其中，数据块分块算法、指纹库查询等，都是重复数据删除中的核心技术。虽然重复数据删除技术已经得到广泛应用，但是仍然有一定的缺陷，例如会导致元数据增加，误删除数据恢复难度较大等。在这一背景下，探究云存储模式下重复数据删除技术的优化应用策略成为一项热门研究课题。

1 重复数据删除技术

1.1 重复数据删除的基本流程

重复数据删除大体包含5个步骤：第一步，选择需要存储或备份的文件，然后使用分块算法将整个文件分解成若干个独立的数据块，并对每个数据块进行命名、标记；第二步，使用哈希函数（hash）分别对各个数据块进行计算、处理，得到对应的hash 值，即指纹。若两个数据块相同，则其指纹能够完全匹配；第三步，将所得指纹与指纹库中已存指纹进行配对，判断该指纹是否存在。若不存在，则执行第四步；若存在，则执行第五步；第四步，将该指纹及其对应的数据块存储起来，同时更新元数据；第五步，直接更新元数据。从上述流程来看，重复数据删除技术的核心在于重复数据的检测、hash 指纹计算函数、指纹在指纹库中的查询。

1.2 重复数据检测技术

重复数据检测结果将会直接决定系统的重删率，同时选择不同的检测技术还会产生不同的性能开销。例如，选择固定分块算法，对系统性能要求不高，性能开销较小；相反，内容分块算法的重删率更高，并且性能开销的需求也更高。目前比较常用的重复数据检测技术有两大类，即相同数据检测、相似数据检测，具体又包含了若干技术，例如基于文件级分块、基于内容分块等。

本文主要使用到了固定长度分块和滑动窗口分块。其中，固定长度分块是将一份文件切割成若干个长度相同的数据块，其优势在于算法简单、元数据管理方便，在数据备份中常用这种算法。但是其缺点也比较明显，例如无法智能识别数据内容，对数据修改具有很高的敏感性，影响系统的重删率。滑动窗口分块是一种更高精度的重复数据检测方法，它融合了固定长度分块算法元数据易于管理的优点和CDC 算法对数据修改不具有较强敏感性的优点，综合应用效果更好。

2 重复数据删除技术在云存储中的应用

2.1 重复数据删除系统设计

基于云存储特点，设计的重复数据删除系统采用多数据节点的分布式系统，保证了数据重删与恢复的同时进行，以及实现元数据分治，以便于增强系统整体性能和降低元数据管理成本。系统基本架构如图1 所示。

图1 重复数据删除系统架构图

如图1 所示，该重复数据删除系统中包含2 台Nameserver、N 台Dateserver。其中，Client（客户端）与Nameserver 之间完成地址表信息交互，与Dateserver之间完成数据块、指纹等信息的交互。主、备Nameserver 之间保持数据同步，这样在主Nameserver 因故障停运或发生宕机后，可以直接从备Nameserver 中获取数据，防止数据丢失、保证系统正常运行。Nameserver 通过心跳的方式检测和Dateserver 的运行工况。

2.2 系统功能模块设计

2.2.1 客户端

客户端的功能包括读取文件信息、进行数据分块，以及数据块的hash 处理。由于每名用户可备份若干文件，因此需要采用“用户名+文件路径名”的方式，对文件进行标记，所得文件的标识符记为File_ID。在客户端备份的过程中，将读取信息后的文件进行分块。数据分块将直接决定重复数据删除系统的两个关键指标，即“重删率”和“吞吐率”。重删率取决于分块方式、分块大小。通常来说数据块期望越小，则重删率越高。但是不同类型的文件适用的分块方式也存在差异，例如小于10 MB 的图片文件，可选择固定分块算法；而对于1 GB 以上的视频文件，滑动窗口算法更为理想。

2.2.2 数据存储节点

数据存储节点（Dateserver）的主要功能有两个：其一是存储数据，其二是在指纹库中对新的指纹进行配对，判断有无重复。考虑到指纹库中存储着海量的指纹信息，因此指纹查询的速度也是决定重复数据删除系统性能的一项关键指标。由于采用的是分布式系统，因而能够以线性方式缩小单机指纹库的大小。假设某重复数据删除系统指纹库总容量为500 G，安装有200 台Dateserver，则单机指纹库容量仅为2.5 G，这样就能快速完成指纹查询任务。另外，在指纹库设计上也采用了双层结构，第一层是bioomfilter（布隆过滤器），本质上是一种高效的数据查询模块，主要用于快速判重；第二层是内存指纹cache，其作用是添加指纹计数器，简化了将指纹放入指纹库时的操作流程，提升系统性能。

2.3 系统数据分配策略

该系统中包含若干台Dateserver，并且每一台Dateserver 中存储的数据都是相互独立的。基于这一特点，在系统数据分配上选择了一致性哈希算法。其分配原理是将Dateserver 中的数据尽量平均分配至每个节点上，以实现负载均衡。将Dateserver 中的数据值设定为a，则数据分配流程：基于hash 函数分别计算每一个数据块对应的hash 值。沿着顺时针的方向，将该数据块分散到第一个大于该hash 值的a 对应的Dateserver上。由于一致性哈希拥有较好的可扩展能力，因此当系统中任意一个Dateserver 的增加或失效，只会影响到它相邻的两个节点，而不会对系统中其他节点产生影响。

3 重复数据删除系统应用测试

3.1 测试环境

该系统测试环境配置如下：使用Ubuntu12.2 系统，内核为Linux3.5.0-17，Intel（R）Xeon（R）CPU E5-2603（4 核，主频2.0 GHz），64 G 内存，1 TB 磁盘和1 Gpbs 网卡。

3.2 测试内容及结果

3.2.1 分块算法性能测试

该部分采用了对比测试，选择一个大小为20 M、内容无重复的文档作为样本，分别使用固定分块算法、滑动窗口算法、改进的滑动窗口算法进行测试。测试内容分为两项，第一是对原始文档进行备份，测试一次备份情况下3 种算法的性能及重删率。第二是在该文件中间随机位置添加1个字节，然后再使用3 种算法进行备份。测试第二次备份时各算法的性能与重删率。其中，重删率（f）的计算公式：

式（1）中，Data1 为重复数据删除前文件数据量，Data2为新增数据量。测试结果如图2、图3 所示。

图2 文件无重复度情况下3 种算法比较

图3 在文件中加入一个字节第二次备份3 种算法比较

结合图2 可以发现，在文档文件重删率较低（接近于0）时，选择滑动窗口算法的系统性能较差，吞吐率仅有0.9 MB/s。相比之下，选择固定长度分块算法，系统性能得到了明显改善，吞吐率达到39.5 MB/s，两者之间差距明显。而改进后的滑动窗口算法性能一般，吞吐率为26.3 MB/s。而在图3 中，随着文档文件重删率的增加，3 种算法下系统性能差异逐渐缩小。在文档修改度较小的情况下，第二次备份时运用改进的滑动窗口算法、滑动窗口算法，都能获得较高的重删率，后者甚至接近100%。另外，相比于固定长度分块算法，在上述两种算法下由于文件中大部分数据块并不需要写入磁盘，因此他们的吞吐率也要略高。

基于上述测试数据可得：在数据无重复或重复度很小的情况下，固定分块算法性能表现较好，改进的滑动窗口算法性能一般，而滑动窗口算法性能较差；在数据重删率较高的情况下，滑动窗口与改进的滑动窗口算法性能较好，并且两者差距不明显，固定分块算法性能稍差。综合来看，在重复数据删除系统设计和运行中使用改进的滑动窗口算法效果最好。

4 结束语

本文设计的一种分布式重复数据删除系统，可根据不同类型的文件选择合适的分块算法，其中基于滑动窗口的改进算法，在图片、视频等文件的重复数据删除中均表现出较好的系统性能。当系统中多台客户端同时备份时，随着数据节点的增加，系统吞吐率也随之上升，重复数据删除系统的性能得到改善。

3.2.2 系统备份和恢复性能

该测试的对象主要是指纹库与多台Dateserver。选择一个4.1 GB 的视频文件，重复度基本为0。测试分为两部分，第一次选择1 台Client、1 台Nameserver、1台Dateserver，将视频文件分割成若干1 MB 大小的数据块，测试备份时系统性能及重删率。第二次选择6 台Client，1 台Nameserver，并分别在1、2、3、4 台Dateserver下测试系统性能。结果如图4、图5 所示。

图4 单机备份和恢复性能

在图4 中，使用大数据块固定长度分块方式，系统针对视频文件的备份性能与恢复性能均有良好表现。在图5 中，使用1 台Dateserver 时，受到网络带宽的限制，系统备份与恢复性能较差；当2 台Dateserver 投入使用时，系统性能有明显改善；当3 台、4 台Dateserver投入使用时，系统性能均依次提升。

图5 多机备份和恢复性能