Rabin指纹算法在重复数据检测中的应用

摘 要：Rabin指纹算法计算效率高、随机性好,可将数据更改对连续指纹序列的影响限制在局部范围内,广泛应用于重复数据检测领域.分析了Rabin指纹在有限域GF（2n）上的运算原理,得出滑动窗口移动时定长字符序列的数字指纹快速计算公式.用伪代码描述了Rabin指纹算法在重复数据检测中的应用,并用VC++语言进行了算法实现,在普通计算机上提取Word文档、程序源代码和BMP图像等三类文件作为测试数据集,测试结果表明算法是有效的.

关 键 词：存储系统；重复数据检测；Rabin指纹；基于内容分块；有限域

中图分类号：TP309文献标识码：A文章编号：1009-3044（2013）21-4918-03

Rabin指纹算法[1]由美国哈佛大学教授拉宾（Rabin）提出,具有计算效率高、结果对任意数据呈现出均匀分布的特点,常用于进行快速比较并识别出重复数据,在很多领域有着广泛的应用.文献[2]利用通过计算邮件正文的Rabin指纹实现高速网络环境下的实时垃圾邮件检测.文献[3]基于Rabin指纹方法实现URL的去重,提高检索速度.文献[4]在对Web页面并行采集过程中利用Rabin指纹实现网页的识别.文献[5]利用改进的Rabin指纹算法实现对大规模分布式网络中恶意代码特征码的自动提取.

重复数据检测和删除技术能够消除存储系统中的冗余数据,降低用户的磁盘采购费用,减少在网络中传输的数据量,为企业和个人节约在人力、设备、资源、资金等方面的开销,带来良好的经济效益.Rabin指纹算法常用在基于内容分块（ContentDefinedChunking,CDC）[6]的重复数据检测中,以便实现文件中数据的分块,在LBFS[7]、Pastiche[8]、DeepStore[9]等归档或存储系统中得到广泛应用.国内也对Rabin指纹在重复数据检测和删除中的应用进行了一些研究,文献[10]提出一种并行层次化的重复数据删除算法,文献[11]实现了一个基于重复数据删除的多用户文件备份系统,文献[12]实现了一个基于因果关系的数据去重结构CABDedupe,文献[13]提出了一种基于重复数据删除的Oracle数据库备份系统.

1技术原理

CDC方法采取一个数据滑动窗口从文件的开头向尾部滑动,逐一计算出滑动窗口内数据块的Rabin指纹,如果指纹值跟某个预设的值相同,则将该窗口的开始位置作为数据块的分割点.当窗口滑动到文件末尾时,文件分块结束.对于划分的每一个数据块计算出其哈希值,以便进一步检测它是否重复数据块.CDC方法可以将数据更新对数据块边界划分的影响控制在更新位置附近的少数几个块内,保持其他数据块不变,适合应用于更新频繁的数据集.为了避免产生过大的块,一般要规定数据块大小的上限.为了避免产生过小的块,可以规定数据块大小的下限.

以文件类型为作为分类项目,对比数据块最大容量分别为64、256、512、1024、4096时的重复数据检测率,结果如图3所示.可见数据块越大,意味着检测粒度更粗,重复数据检测率将会下降,每类文件的在数据分块大小分别取不同值的表现排序基本是一致的.

3.2磁盘利用率测试

磁盘利用率是数据实际容量与占用空间的比值,用于衡量磁盘空间的实际使用比例.磁盘空间是以簇为基本单位进行分配的（如在NTFS文件系统为4KB）,比如某个数据块只有3000字节,但它实际上要占用4096字节的磁盘空间,因此这个数据块对磁盘空间的利用率只有73%.对于采用了重复数据删除技术的存储系统,由于很多数据块的容量可能不是簇的整数倍,造成磁盘空间无法完全利用,将会抵消重复数据删除的效果.

以文件类型为作为分类项目,对比数据块最大容量分别为64、256、512、1024、4096时的磁盘利用率,结果如图4所示.可见随着数据块的增大,磁盘利用率将会略有下降,由于数据块分块大小不一的原因,导致约有10%到15%的磁盘空间无法利用,一定程度上抵消了重复数据消冗的效果.

4结论

实验仅在小数据集上进行,实际生产中使用的存储系统中的数据分块粒度会更大些,一般在4KB至128KB之间,但系统中的重复数据比例也将会更多,两方面产生的影响相互抵消,因此实验测试结果与实际存储环境不会有大太差距,实际上很多公开报道的重复数据删除系统的数据指标也与本实验结果相近.该文的工作结果具有实际指导意义.

以Rabin指纹作为数据块划分依据的重复数据检测方法适合应用于更新频繁的数据集,已被国内外很多存储系统所采用.近年来,随着数据信息的爆炸性增长,企业对存储的需求越来越大,已从前几年的TB级上升到PB级,甚至EB级.由于网络共享手段的日益普及,人们交流数据的机会大大增加,以网络硬盘为代表的网络存储系统中充斥着大量的重复数据.重复数据检测和删除技术的应用必将能带来巨大的效益.

[12]谭玉娟.数据备份系统中数据去重技术研究[D].武汉：华中科技大学,2012.

[13]李向前.一种基于重复数据删除的Oracle数据库备份系统[J].电脑知识与技术,2013（01）：5-7+14.