BloomFilter(布隆过滤器) vs CuckooFilter(布谷鸟过滤器)

BloomFilter vs CuckooFilter

(一)BloomFilter(布隆过滤器)

1.原理

  1. 将元素通过哈希函数散射到一个很长的二进制向量的3个位置,空间效率和查询时间都远远超过一般的算法
  2. BloomFilter可以很方便地检索一个元素是否存在集合中:对该元素进行哈希,判断3个标志位是否都是1,如果存在非1的位,那么该元素一定不在BloomFilter中;但是如果3个标志位都是1,只能说明这个元素可能存在于BloomFilter中,不能100%确定,需要进一步地判断(比如查询DB)。

2.应用场景:海量URL去重

布隆过滤器BloomFilter最主要的应用场景应该是海量URL去重与存储,搭配位图法的使用可以获得极大的效率提升,同时也能提高空间利用率。

一、如何对海量的URL进行去重?
1.将URL直接存入数据库 —— 极不推荐,DB读写效率太低。
2.将URL存入HashSet —— 读取速度为O(1),但是占用内存空间。比如Redis中的Set数据结构
3.将URL进行一次MD5/SHA-1单向Hash加密后,存入数据库/HashSet。
4.位图(Bit-Map)法:建立一个BitSet,将每一个URL经过一个Hash函数映射到某一位。但是使用该方法要求URL的基数非常大,否则的话可能会因为频繁的Hash碰撞而导致误判断,同时Hash算法也应该选好,降低碰撞概率比如Redis中的HyperLogLog数据结构
5.Bloom Filter(中文名为“布隆过滤器”):Bloom Filter的本质其实还是位图法,只不过它对同一个URL采用了3个不同的Hash函数进行映射,只要3个位置上有一个位置没有元素,就说明该URL没有重复,这样就可以大大降低碰撞概率。

二、如何对URL进行有效的记录?
1.网页数量大的情况下,可以通过BloomFilter进行压缩。
2.可以用Redis替代关系型数据库。


3.BloomFilter的缺点

(1)不支持逆向操作(即删除)

这是BloomFilter最大的痛点,在一个动态的系统中,流水数据是非常大的,BloomFilter添加过的元素不能被删除(因为Hash函数的不可逆特性),这样就会使得过滤器内的垃圾元素越来越多,这些占用了位置却无实际效益,会使得BloomFilter误判率越来越高,最终不得不重建BloomFilter
BloomFilter的变种CountingBloomFilter采用了计数器替代指纹的方式,使得它支持删除操作,但是为了保持这些计数器,会引入巨大的额外开销。

但值得说明的是,虽然CuckooFilter支持删除,但是其功能十分鸡肋,完全无法使用。如果想要CuckooFilter支持删除操作,那么就不允许相同元素插入kb+1次,其中k是Hash函数的个数2,b是单个位置上的座位4。

(2)查询性能弱(内存跨度大)

BloomFilter使用多个不同的Hash函数探测位图中的不同点,这些点在内存上跨度十分大,会导致CPU缓存命中率低。

CuckooFilter采用的是特殊的Hash算法,通过一个Hash算法得到的点,可以极便利地找出另一个Hash算法确定的点。

(3)空间效率低

CuckooFilter采用了同一个位点挂载多个座位的方法,所以空间利用率会比BloomFilter高很多。
但是CuckooFilter要求位图的长度必须是2的指数(因为必须要通过特殊的Hash函数达到快速定位,类似于HashMap必须是2的指数长度原因)。

(4)判断元素存在时存在一定的误判率(True Negative)

如果BloomFilter判断不存在的元素,它一定不会存在于BloomFilter中;但是BloomFilter判断存在的元素,由于哈希碰撞的关系,可能其实不存在于BloomFilter中,也就是说判断元素存在时会存在一定的误判率


(一)CuckooFilter(布谷鸟过滤器)

1.Cuckoo哈希算法

我们知道,自然界中的布谷鸟会将自己的蛋产在别的鸟的巢中,让别的鸟来帮忙孵化,而布谷鸟的体型较大,会将原住民挤出巢穴摔死。
Cuckoo哈希算法(布谷鸟哈希算法)就得名于此,最简单的Cuckoo哈希算法会采用两个哈希函数,将新添加的元素映射到数组的两个位置,如果两个位置中有一个为空,则可以存放该元素,否则新元素就从两个位置中会随机挑选一个老元素踢走,自己占据该位置。而被挤走的老元素会查看自己对应的另一个位置有没有元素,如果没有则直接存放,否则就踢走原有元素。一直重复该步骤,直到所有元素都找到了位置存放为止。
不难看出,上述步骤中有几个问题没有解决:

  1. 如果数组过于拥挤,元素被踢来踢去许多次还没有停下来,就会非常影响插入元素的效率 —— Cuckoo哈希算法会设置一个阈值,如果超过这个次数元素位置尚未被确定,则认为数组已经满了,需要扩容,重新放置所有元素。
  2. 另一个小概率事件是循环挤兑:3个不同元素通过Cuckoo哈希算法得到的位置完全一样,它们会相互挤兑,超过阈值后,Cuckoo哈希算法会误判数组已经满了(实则没有),导致扩容。但3个不同元素经过两次hash得到的位置还是一样的概率太低,除非算法实在太差。

基础的Cuckoo算法的空间利用率并不高,大概在50%,到达此百分比,就会很快出现超过阈值的情况。所以需要进行优化。


优化

  1. 增加Hash函数,不必非是2个:这样可以使得可选择的位置增加,减少碰撞;
  2. 在数组的同一个位置挂载多个座位解决Hash冲突:这样的话,如果Hash冲突,可以不必挤兑,而是一人一座,除非座满;

相当于加链法。

  1. 综合以上方法,如:使用4个Hash函数,每个位置放2个座位

2.CuckooFilter

不同于Cuckoo哈希算法直接存储具体元素,CuckooFilter存储的是元素的指纹信息(几个bit),这样做牺牲了精确性,换来了空间效率。
但是,由于存储的是指纹信息,所以难免会存在误判率,这不可避免。
CuckooFilter选用的是两个特殊的Hash函数通过一个位置可以轻松地计算出另一个对偶位置;同时一个位置可以挂载多个座位

1
2
3
4
5
6
7
8
9
10
11
//传统的2个Hash函数
//只知道指纹fp和其中一个位置p1,是无法直接计算出p2的
fp = fingerprint(x)
p1 = hash1(x) % l
p2 = hash2(x) % l

//CuckooFilter中特殊的2个Hash函数
//知道指纹cf_fp和其中一个位置p2,可以直接通过异或(^)算出p2
cf_fp = fingerprint(x)
p1 = hash(x) //不取模的原因是,Cuckoo哈希算法要求数组长度为2的指数,进行异或时,直接保留低n位即可:p_ = p & oxff
p2 = p1 ^ hash(cf_fp)

致命弱点:重复元素的插入

目前为止CuckooFilter都表现得很好,但是试想一些,CuckooFilter提供2个Hash函数、4个座位,也就是8个位置,我们对同一个元素进行重复的9次插入,到第9个元素时,座位已经满了,它们之间就会进行循环挤兑
也就是说,如果想要CuckooFilter支持删除操作,那么就不允许相同元素插入kb+1次,其中k是Hash函数的个数2,b是单个位置上的座位4。
在一个系统中,确保同一个元素不被插入指定次数所耗费的代价是极其恐怖的!

-------------本文结束感谢您的阅读-------------

本文标题:BloomFilter(布隆过滤器) vs CuckooFilter(布谷鸟过滤器)

文章作者:DragonBaby308

发布时间:2020年01月25日 - 13:14

最后更新:2020年02月01日 - 14:38

原始链接:http://www.dragonbaby308.com/bloomfilter/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。

急事可以使用右下角的DaoVoice,我绑定了微信会立即回复,否则还是推荐Valine留言喔( ఠൠఠ )ノ
0%