理解布隆过滤器

Posted by Planeter on 2021-10-29

考虑一下,我们现在有一张数据库表,已经做了缓存,但是可能有人想攻击数据库,故意请求不存在的数据。这就会导致缓存失效,每次请求都会查询数据库,给数据库带来很大压力。简言之就是穿透了数据缓存层,也就是所谓的数据穿透。如何解决这个问题?一种方案是设置过滤规则, 在数据库查询之前将数据进行过滤, 如果发现数据不存在, 则不再进行数据库查询, 以此来减小数据库的压力。

通常来说,判断某个元素在集合中是否存在时常常使用HashMap,O(1)的时间复杂度效率极高。然而,当数据量太大时,HashMap 所占用的空间也会很大。以搜索引擎爬虫为例,要防止重复爬取某个网页,需要维护一个存储已爬取URL的数据结构。如果用HashMap存储1亿个URL,每个URL地址 对应 9 字节, 负载因子为0.75,因此一个URL需要占用 12字节. 因此1亿个URL占用1.1GB,全球网络上有超过10亿个网站,超过500亿网页,也就是说需要550GB来存储。

那么,有没有一种数据结构既能快速判断元素在集合中的存在性,在数据量很大时,又占用空间相对较小的数据结构呢?

布隆过滤器很好的契合了这个需求。

在讨论布隆过滤器(Bloom Filter)前,先需要了解一下Bit-map,从某种意义上而言,布隆过滤器是Bit-map的扩展。

Bit-Map

概念

简言之,Bit-map将每个值映射为一个bit,并用该bit表示该值存在与否。Bit-map一般用来存储不重复的数据。

如图,每8位作为一个单元,共8*4=32位,被[0,31]的整形所映射

Bitmap

实例

以 Java int 为例,1个 int 占 4 字节,也就是32位。假如某实体类Student的id使用int类型,对应的表总共有1,000,000行。现在要另外存储所有id用来进行增删和排序。

  1. Bit-map能节省存储数据所需的空间。

    使用int数组存储因而占用的空间约为 (1,000,000*4/1024/1024/1024)≈3.814MB

    使用Bit-map存储而占用空间约为 (1,000,000/8/1024/1024/1024)≈0.119MB

  2. Bit-map可进行数据的增删。
    我们使用int数组arr来存储Bit-map,每个int有32位,可以表示32个数。因此arr[0]表示031,arr[1]表示3263,依次类推,对于十进制整数D,D/32可得到索引,D%32就知道它在该索引对应整形的哪一位。
    增:将待插入数据D转换为其在Bit-map对应位为1,其他位为0的int,然后与原Bit-map对应索引进行按位或操作。

    删:将待插入数据D转换为其在Bit-map对应位为0,其他位为1的int,然后与原Bit-map对应索引进行按位或操作。

  3. Bit-map可进行不重复数据的快速排序

    假设我们要对0-31内的4个元素(1,23,24,16,30)排序。首先需要32位(1 int),将所有位初始化为0后,插入所有元素。遍历Bit-map,将位为1的编号输出,即为排好的顺序。

Bloom Filter

Bloom Filter是如何运行的

Bloom filter 是一个数据结构,它可以用来判断某个元素是否在集合内,具有运行快速,内存占用小的特点。

而高效插入和查询的代价就是,Bloom Filter 是一个基于概率的数据结构:它只能告诉我们一个元素绝对不在集合内或可能在集合内

Bloom filter 的基础数据结构类似一个Bit-map。下表为一个15bit大的Bloom filter,表中的每一个空格表示一个比特, 空格下面的数字表示它的索引。

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14

相比于Bit-map的直接映射,Bloom Filter在映射值前,需要先使用多个不同的哈希函数对值进行哈希生成多个哈希值,然后都插入进去。

对“w2online”使用 Fnv 和 Murmur进行哈希得到6和7。

0 0 0 0 0 0 1 1 0 0 0 0 0 0 0
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14

通过对某字符串应用同样的哈希函数,然后看Bit-map里对应的位置是否为1的方式来判断一个元素是否在集合里。如果是,你只知道元素可能在里面, 因为这些对应位置有可能恰巧是由其他元素或者其他元素的组合所引起的。因此,布隆过滤器的缺点也很明显,那就是对于存在有误判的情况。

Bloom Filter的误判率

布隆过滤器的误判率受多种因素影响。首先,像HashMap的哈希冲突一样,布隆过滤器的误判率也与其大小有关。过小的布隆过滤器很快就会被填满,无法起到过滤作用,而越大的布隆过滤器则误报率越小。其次,哈希函数也与误判率有关。哈希函数越多则布隆过滤器被填满的速度越快,且查询效率越低;但是如果太少或者分布不均的话,布隆过滤器的误判率会上升。

对于过滤器大小m(bit),哈希函数数量k,以及数据量n,布隆过滤器的错误率会近似于 (1-e^(-kn/m))^k

除了有误判存在外,布隆过滤器还有一个缺点是不能删除数据。

Redis实现Bloom Filter

Redis支持Bitmap这种数据结构,且内存操作效率高,因而适合用来实现布隆过滤器。Redission api中提供了实现,底层还是Bitmap,就不赘述了.

参考资料