布隆过滤器在重复数据删除中的应用

开篇：润墨网以专业的文秘视角，为您筛选了一篇布隆过滤器在重复数据删除中的应用范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！

摘要：重复数据删除技术是一种数据缩减技术，它可以减少对物理存储空间的需求，从而满足日益增长的数据存储需求。该文将Bloom过滤器应用于重复数据删除技术中，加入两级fingerprint映射表，经过多个高效率的散列函数的计算，以引入较小的“假阳性错误率”为代价，增大磁盘的空余量。

关键词：布隆过滤器；重复数据删除；数据指纹；假阳性错误

中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2014）08-1793-03

1 重复数据删除和布隆过滤器的概念

1.1 重复数据删除技术的定义[1]

重复数据删除是一种数据缩减技术，通常用于基于磁盘的备份系统，旨在减少存储系统中使用的存储容量。它的工作方式是在某个时间周期内查找不同文件中不同位置的重复可变大小数据块。重复的数据块用指示符取代。高度冗余的数据集（例如备份数据）从数据重复删除技术的获益极大；用户可以实现10比1至50比1的缩减比。而且，重复数据删除技术可以允许用户的不同站点之间进行高效，经济的备份数据复制。

重复数据删除技术支持在已有的磁盘设备上存储更多的备份数据。因此采用“重复数据删除”技术可以增加保存备份数据的时间，减少数据中心的消耗，降低成本。

1.2 Bloom过滤器

1.2.1 Bloom过滤算法

Bloom过滤算法[2]，是由巴顿布隆于 1970年提出的，它实现的基础是一个很长的二进制位向量和一系列随机散列函数。Bloom Filter是一种基于散列的查找算法，用于查找一个元素是否在集合中，并用“1”（可能存在），“0”（不存在）来表示，将Kb的空间降到Bit的数量级，减少了磁盘的存储压力。前面之所以将“1”表示成可能存在，是因为随着新数据的不断插入，fingerprint映射表的的“1”越来越多，那么假如新插入的数据从未出现在源数据中，但他的几个映射位都置“1”，这时该算法的缺点就出现了，也就是“假阳性错误率”，在增加了错误率这个因素之后，Bloom Filter通过允许少量的错误来节省大量的存储空间。

1.2.2 Bloom算法的原理

下面介绍bloom过滤器的结构与实现原理[3]：

当原数据为空，那么fingerprint映射表也为空，则状态位都置“0”，如图1。

新插入的数据块a经过MD5计算后，将其结果再经过bloom算法中的n个hash函数（此时n=4）计算后生成4个“1”，那么fingerprint中的某4位将被置“1”，如图2。

当有新数据块继续要插入时，如果通过上面方法计算后的fingerprint中的某4位已经置“1”，那么进行第二级bloom算法的计算，但只要有fingerprint映射表中的某一位没有被置“1”，那么新插入的数据就没有在原数据中出现，将“0”位置“1”，如图3。

2 重复数据的删除

重复数据删除技术的性能受多方面因素的影响：对何种数据应用重复删除，何时、何地进行消重，以及如何进行消重，其实现过程主要包括：文件数据块化、数据块指纹化、数据块指纹的管理。

2.1 文件数据块化

重复数据删除的首要任务就是将文件数据块化，其数据分块的主要算法有三种：定长切分（FPS）、变长切分（CDC）以及滑动切分算法（SB）。

2.2 数据块指纹化

数据块指纹化是指将已切分的数据块经过Hash算法计算得到指纹的过程。MD5是计算机安全领域广泛使用的hash函数，MD5值是128位的，正好满足数据指纹小的要求，理想情况下不同数据块的指纹是不同的，但是hash函数中hash值之间的“碰撞”是必不可少的，那么尽量减少冲突将需要更多的计算。

虽然经过MD5计算的hash值的“碰撞”率很低，但是只要有一个例外发生，如果实现不做任何处理，那么可能导致数据块的丢失。下面以图4为例介绍该系统如何消除冲突的过程。

其实现过程如下：

1）将待处理的数据块bk1进行MD5计算得到数据指纹fp1

2）将fp1与fingerprint比较，判断是否发生碰撞，如果没有冲突，说明该数据块在源文件中未出现，将fp1写入fingerprint，并将数据块写入源文件。

3）如果发生碰撞，那么将fingerprint中相同的fp1’对应的数据块bk1’与bk1比较，如果数据块相同，证明是重复数据，则不做处理。

4）如果经过比较数据块不同，那么将fp1与bk1写入相应的fingerprint与文件。

3.3 内存消耗的计算与原数据块大小的关系

一级Bloom Filter 所需的Finger Print 和二级Bloom Filter 所需的Finger Print的大小。初步计算100GB的存储数据需要大约25MB的内存空间，其中hash函数的个数为8个。计算如下：100GB / 8KB （原数据）= 12.5 * 10^9（个数据块），12.5 * 10^9 * 2 * 8（bit） = 25 MB（内存空间）内存空间也就是一级fingerprint的大小。经过一级bloom filter计算以后，”假阳性”错误率减少至少60%，所以二级bloom filter还需1 / 3的fingerprint的大小。

3.4 Hash函数的个数与“假阳性错误率”的关系

Bloom Filter要靠多个哈希函数将集合映射到位数组中，那么应该选择几个哈希函数才能使元素查询时的错误率降到最低呢？这里有两个互斥的理由：如果哈希函数的个数多，那么在对一个不属于集合的元素进行查询时得到0的概率就大；但另一方面，如果哈希函数的个数少，那么位数组中的0就多。本系统将设置几组hash函数进行实验，分别计算出各组hash函数对“假阳性”错误率的影响，从而选择最有hash函数的个数。分别为一级bloom filter设置4个hash函数、6个、8个hash函数进行实验。除次之外，“假阳性”错误率还与位向量长度和filter里的keys的数量有关。

3.5 Hash映射函数的设计

判断一个元素是否存在于一个指定集合中，可能并不需要把所有集合元素的原始信息都保存下来，我们只需要记住“存在状态”即可，这往往仅仅需要几个bit就可表示。Hash函数可将一个元素映射成一个位数组中一个点，为了降低碰撞率可采用多个hash函数将元素映射成多个点。这样一来，只要看看几个位点是0或1 就可以判断某个元素是否存在于集合当中。既不能无限制的增加hash函数的个数以减少碰撞率，所以各个hash映射函数的设计是个重要的问题，如果几个hash函数不是均匀分布，那么只会增加查询的开销，反而降低插入或删除的效率，降低性能。

在原fingerprint的基础上建立一级fingerprint和二级fingerprint，相当于经过三级fingerprint的计算来减少假阳性错误率的发生。一个hash函数设计如下：

一级fingerprint的输入N = MD5计算的结果 = 128Bit = 27，

一级fingerprint的长度 = 128Bit，二级fingerprint的长度 = 25MB，这里分配225Byte = 32MB的大小空间，也就是需要内存的空间。

过程描述：

1）取一级128位的MD5_KEY的前7位，取其值的结果将一级fingerprint的相应那一位置“1”。

2）若一级fingerprint的某一位已经置“1”，那么将MD5_KEY置“1”的那一位开始的25的值计算出来作为二级fingerprint的映射位，并把二级fingerprint相应的那一位置“1”，如果取MD5_KEY的25位时取到末尾仍不够25位，那么从MD5_KEY开始部位继续取，直到取到25位。如：前7位二进制表示为：1100111其值为103，那么如果从第103位取到第127位正好是25位，所以当前7位的值大于等于103时，将从开始处取M位（0

3）Hash的扩展，将前7位从0位开始变成从n位，n >= 0，这样会产生N个hash函数。或者从第127位向前取，相当于取MD5_KEY的质数再进行一级、二级bloom算法。

4 结束语

本文讨论了bloom算法在重复数据删除技术中的应用，通过高效率的散列函数的计算得到数据指纹，当有新数据要查找时，直接在指纹映射表中进行，很大程度上减少了内存的消耗，提高了检索的效率，但面对很大数量级的数据，不同数据块的指纹会出现“碰撞”，我们通过设计多级哈希函数来映射指纹，经过多层fingerprint的过滤，最后一层出现的“碰撞”的几率已经很少，然后再通过数据块之间的逐位的比较，从根本上消除了“碰撞”，保证了用户数据的安全性。

参考文献：

[1] 敖莉，舒继武，李明强.重复数据删除技术[J].软件学报， 2010，21（5）.

[2] Bloom B H..Space/time trade-offs in hash coding with allowable errors[C].Commun. ACM， 1970，13（7）：422426.

[3] 谢鲲，闵应骅，张大方，等.分档布鲁姆过滤器的查询算法[J].计算机学报，2007，30 （4） ：597-607.